解决过拟合问题有三种思路：加数据、正则化、降维，降维的思路来自于维度灾难

已知一个正方形边长为2R2R2R，则面积为22R22^{2}R^{2}22R2，对应最大内接圆的面积为π⋅R2\pi \cdot R^{2}π⋅R2；一个正方体边长为2R2R2R，则体积为23R32^{3}R^{3}23R3，对应最大内接球的体积为43π⋅R3\begin{aligned} \frac{4}{3}\pi \cdot R^{3}\end{aligned}34​π⋅R3​。因此，对于更高维度DDD，对应超正方体，我们可以认为它的体积为2DRD2^{D}R^{D}2DRD，超球体它的体积为C⋅RDC \cdot R^{D}C⋅RD，就有

lim⁡D→+∞C⋅RD2DRD=0 \lim\limits_{D \to +\infty}\frac{C \cdot R^{D}}{2^{D}R^{D}}=0

D→+∞lim​2DRDC⋅RD​=0

其中CCC为常数

也就是，在高维空间中的数据点大多分布在立方体的边缘，数据集更加稀疏

我们也可以计算一个D(D→∞)D(D \to \infty)D(D→∞)维空间，半径为111的超球体的体积，以及该超球体与半径为1−ϵ(0<ϵ<1)1-\epsilon(0<\epsilon <1)1−ϵ(0<ϵ<1)的超球体间球壳的体积之差，发现二者体积都为111，也就是在球壳内部是几乎没有体积的，这也能说明在高维空间中的数据点大多分布在立方体的边缘，数据集更加稀疏

降维{直接降维:特征选择线性降维:PCA,MDS非线性降维:流形{IsomapLLE 降维\left\{\begin{aligned}&直接降维:特征选择\\&线性降维:PCA,MDS\\&非线性降维:流形\left\{\begin{aligned}&Isomap\\&LLE\end{aligned}\right.\end{aligned}\right.

降维⎩⎨⎧​​直接降维:特征选择线性降维:PCA,MDS非线性降维:流形{​IsomapLLE​​

虽然白班推导里没有，但大概根据自己的理解写了一下决策树的笔记

关于k近邻法（KNN），这个我有一点没太看明白，可能需要看一下源码，晚一点再发笔记，这里只能先撂下了

下周应该会发关于sklearn使用的一点笔记，主要是关于决策树的，最近把决策树看完了

这里有个关于决策树的疑问，关于决策树CART算法剪枝，Breiman等人证明：可以用递归的方法对树进行剪枝，将α从小到大排列，0=α0<α1<⋯<αn<+∞0=α0<α1<⋯<αn<+∞0=α0<α1<⋯<αn<+∞，产生一系列的区间，剪枝得到的子树序列对应着区间α∈[αi,αi+1)，i=0,1,...,nα∈[αi,αi+1)，i=0,1,...,nα∈[αi,αi+1)，i=0,1,...,n的最优子树序列{T0,T1,T2,...,Tn}\{T_0,T_1,T_2,...,T_n\}{T0​,T1​,T2​,...,Tn​},序列中的子树是嵌套的（即T1T_1T1​是T0T_0T0​的子树、T2T_2T2​是T1T_1T1​的子树）根据这个原理，是否我们只需要计算每一个枝条最下面的叶结点的α\alphaα，然后对比，谁小剪谁