机器学习及应用第9章-降维课件

1、第09章 降维k-近邻学习主成分分析低维嵌入SVD分解9.1 引言降维（Dimensionality Reduction，DR）是指采用线性或者非线性的映射方法将高维空间的样本映射到低维空间中。降维获得低维空间下的数据等价表示，实现高维数据的可视化呈现。等价的低维数据更方便存储、处理、计算和使用。降维能够去除数据噪声、降低算法开销。降维还可应用于文本分类和数据压缩等领域。降维可以得到原始数据的简化表示以加速后续处理或者改进输出结果，因此它已经成为很多算法数据进行预处理的重要手段。9.1.1 降维的概念9.1 引言9.1 引言降维方法可分为线性降维和非线性降维两大类。线性降维假设构成数据集的各变

2、量间独立无关。 主成分分析（Principal Component Analysis，PCA） 独立成分分析（Independent Component Analysis，ICA） 线性判别分析（Linear Discriminant Analysis，LDA）非线性降维方法，也称之为流形学习方法（Manifold Learning），其目标是从高维采样数据中恢复低维流形结构，不改变数据本身的拓扑特性。 基于保持全局结构信息，如等距离映射算法ISOMAP 关注局部结构信息，如LLE、LE、HLLE9.1.2 常见算法分类9.2 k-近邻学习k-近邻(k-Nearest Neighbor，kNN

3、)：给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的k个实例，即k个邻居。如果这k个实例的多数属于某个类，就把该输入实例分类到这个类中。9.2.1 算法实现kNN算法计算流程如下: 计算每个样本点与测试点的距离； 排序后取距离值最小的k个样本点作为k-近邻； 获取k-近邻的分类标签并计算各分类出现的次数； 找出出现次数最多的分类，返回该值作为测试点的分类结果。9.2 k-近邻学习实例代码 9.2 k-近邻学习运行效果：左下角两个点属于B类用蓝色点标识，右上角两个点属于A类用红色标识。取k值为3时通过kNN算法计算，距离测试点（0.2, 0.1）最近的三个点中的两个点都是蓝

4、色，因此测试点也是蓝色，属于B类。这样的实现方式适合样本数量和特征数量比较少的情况。假设样本数量为N、特征数量为M，该算法时间复杂度是 。面对大样本和特征数较多的情况，使用KD树、球树训练数据。以KD树为例，搜索时间复杂度为 ，适合于样本数量远大于特征数量的kNN搜索。9.2 k-近邻学习sklearn.neighbors模块集成了k-近邻相关的类，KNeighborsClassifier用做kNN分类树，KNeighborsRegressor用做kNN回归树。KNeighborsClassifier类的实现原型如下：9.2.2 算法实例class sklearn.neighbors.KNei

5、ghborsClassifier(n_neighbors=5, weights=uniform, algorithm=auto, leaf_size=30, p=2, metric=minkowski, metric_params=None, n_jobs=1, *kwargs)：主要参数如下：n_neighbors：整型，默认参数值为5。邻居数k值。weights：字符串或回调函数，默认参数值为uniform。预测时的权重有：9.2 k-近邻学习uniform：所有近邻样本权重都一样；distance：权重和距离成反比；callable，即回调函数：该函数的输入是距离数组，输出是同样大小的权

6、重数组。algorithm：计算近邻的算法，包括如下四种：auto，根据传递给fit方法的参数值，尝试选择最优算法；ball_tree，球树实现（BallTree）；kd-tree，KD树实现（KDTree）；brute，暴力实现。leaf size：整型，默认参数值为30。定义构建KD树或球树时叶子结点数量的阈值。这个值会影响构建和查询的速度，以及树的存储空间。 metric：字符串或回调函数，默认参数值为minkowski。给定树的距离度量方法。p：整型，默认参数值为2。定义闵可夫斯基距离中的p值。9.2 k-近邻学习实例代码 9.2 k-近邻学习在这个例子中，使用鸢尾花iris数据集作为

7、训练数据集，提取该数据集的前两个特征值以简化样本。首先创建近邻分类的实例并对数据进行拟合，同时绘制了分类的边界，将不同分类点以不同的颜色显示出来。最后将训练数据集中的数据用不同颜色的散点显示出来。9.2 k-近邻学习kNN算法本身简单有效，能处理大规模的数据分类，尤其适用于样本分类边界不明显的情况。计算量较大且运行时需要大量内存：对每一个待分类数据都要计算它到全体已知样本的距离，才能求得它的k个最近邻点。kNN算法的三个基本要素：（1）k值的选择：通过交叉验证的方式求出最合适的k值，默认取值为5。（2）分类决策规则：通常采用多数表决决定。在类域间分布不平衡的情况下，采用为k个邻居分配不同权值的

8、方法来改进。（3）距离度量方法。9.2.3 算法关键9.3 主成分分析通过某种线性投影，将高维的数据映射到低维的空间中表示，并期望在所投影的维度上数据的方差最大，以此使用较少的数据维度，同时保留住较多的原数据点的特性。PCA是丢失原始数据信息最少的一种线性降维方式，可以将PCA应用在数据压缩、数据可视化、提升机器学习速度等场景中。9.3.1 算法思想 PCA是将n维特征向量映射到r维上（ ），映射的过程要求每个维度的样本方差最大化，达到尽量使新的r维特征向量之间互不相关的目的。这些数据中拥有方差最大的r个维度被称为主成分。假设有样本数据集 ，每个样本有n个特征： 。处理过程如下：9.3 主成分

9、分析计算样本均值生成去中心化的样本，得到中心化矩阵： , 其中 ， ，计算S的协方差矩阵： ，即 使用SVD奇异值分解方法计算协方差矩阵的特征值和特征向量。 调用方法：linalg.svd()， 矩阵 中的特征值排序，选择其中最大的r个，将其对应特征向量作为 列向量组成降维矩阵 。将样本点投影到选取的特征向量 上，降维后的数据为： 9.3 主成分分析我们使用贡献率来判断选择主成分的个数。贡献率是指选取的r个特征值总和占全部特征值总和的比重，一般应取85%以上。公式如下：9.3.2 算法实例scikit-learn提供了主成分分析相关的类sklearn.decomposition，其函数原型如下

10、：class sklearn.decomposition.PCA(n_components=None, copy=True, whiten=False, svd_solver=auto, tol=0.0, iterated_power=auto, random_state=None)9.3 主成分分析主要参数如下：n_components：整型，浮点型，None或者字符串。保留的主成分个数，亦即保留下来的特征个数n。copy：布尔值类型，默认参数值为False。若为True，将原始训练数据复制一份，算法运行后原始训练数据的值不会有任何改变；若为False，则在原始数据上进行降维计算，运行PCA

11、算法后原始训练数据的值会改变。whiten：布尔值类型，默认参数值为False。白化，使得每个特征具有相同的方差。从转换后的信号中删除一些信息，提高下游估计值的预测精度。svd_solver：字符串。可以取值auto，full，arpark，或randomized。以三维的球型数据集为原始数据对象，通过降维方法把它降成二维数据：9.3 主成分分析实例代码 9.3 主成分分析运行结果如下： n_components=2.000000主成分方差比例： 0.98318212 0.00850037主成分方差： 3.78483785 0.03272285n_components=0.950000主成分方

12、差比例： 0.98318212主成分方差： 3.78483785n_components=0.990000主成分方差比例： 0.98318212 0.00850037主成分方差： 3.78483785 0.03272285n_components=mle主成分方差比例： 0.98318212主成分方差： 3.78483785首先使用scikit提供的make_blobs方法，在指定样本点数量、特征数量、中心点、范围等基础上生成三维球型数据；当n_components=2时，将数据降维到二维，即保留2个主成分；当n_components=0.95时，表示不直接指定降维的维度，而指定降维后的主成分

13、方差占总方差值的比例为95%以上。此时只保留了1个主成分，其方差为3.78483785、方差占比98.3%。当n_components=mle，与保留2个主成分的效果一致。9.3 主成分分析当n_components=0.99时，表示指定降维后的主成分方差占总方差值的比例为99%以上。此时保留了2个主成分，其方差分别为3.78483785和0.3272285，方差占比为98.3%和0.85%，方差占比之和为99.2%。使用mplot3d实现三维数据可视化，并利用mplotlib将降维后的数据显示出来。对比两幅图可以很清楚地看到，PCA降维的过程保留了原始三维图中的4个聚类。9.4 低维嵌入传统

14、的线性降维方法，如主成分分析PCA，在把高维数据映射到低维空间时通常不能保留原高维数据的内在非线性结构和特征。非线性的方法如LLE、hessian局部线性嵌入算法HLLE等应运而生。它们的优点是具有较少的参数需要设置，而且使用非迭代方法求解从而可以避免陷入局部极小。9.4.1 算法原理 LLE算法基本思想是把整个非线性流形分为许多个小块，这些小块由各数据点与它的k个邻居点构成，每个小块可以看作是拥有局部线性结构的。每个数据点和它的k个邻居点的线性组合系数称为重构权重。LLE认为所有数据点降到低维后邻居关系不变，包括重构权重也不变。因此将小块数据线性降维后，再把它们拼接起来，即可构成高维数据的低

15、维表示。9.4 低维嵌入9.4 低维嵌入9.4.2 算法实例流形学习库在sklearn.manifold包中。里面实现的流形学习算法包括：多维尺度变换（MDS）算法、等距映射（ISOMAP）算法、拉普拉斯特征映射（LE）算法以及局部线性嵌入（LLE）算法。LLE算法对应的类是LocallyLinearEmbedding，其函数原型如下： class sklearn.manifold.LocallyLinearEmbedding(n_neighbors=5, n_components=2, reg=0.001, eigen_solver=auto, tol=1e-06, max_iter=100

16、, method=standard, hessian_tol=0.0001, modified_tol=1e-12, neighbors_algorithm=auto, random_state=None, n_jobs=1主要参数如下： 9.4 低维嵌入n_neighbors：整型。搜索样本的近邻的个数，默认是5。n_components：整型。流形学习降维到的维数，维度降到2-3维可用于可视化呈现。reg：浮点型。正则化常量，乘以距离矩阵的局部协方差矩阵的迹。eigen_solver：字符串，可以取值arpack，dense和auto。其含义如下：auto：算法会为输入数据尝试选择最好的特

17、征分解的方法；dense：使用标准非稀疏矩阵特征分解方法；arpack：用于稀疏和非稀疏的矩阵分解，但在稀疏矩阵分解时速度更快。method：字符串，可以取值 standard， hessian， modified和ltsa。 standard：使用标准的局部线性嵌入算法； hessian： 使用Hessian eigenmap算法； modified：使用改进的局部线性嵌入算法；ltsa：使用局部切线空间对齐算法。neighbors_algorithm：字符串，可以取值 auto， brute，kd-tree和ball-tree。9.4 低维嵌入实例代码 9.4 低维嵌入使用sklearn生

18、成的生成瑞士卷曲线数据集，样本点数量为1500。接下来调用manifold包中的locally_linear_embedding类实现LLE算法。最后对原始数据、降维结果分别做可视化呈现。LLE算法对k值选取非常敏感，只有选取了合适的k值参数才能获得较好效果。 (a) 原始瑞士卷数据(b) K=10时LLE降维效果(c) K=20时LLE降维效果(c) K=80时LLE降维效果9.4 低维嵌入9.4.3 算法评价9.5 SVD分解矩阵分解技术能从复杂数据中提取重要的特征信息。它将原始矩阵表示成两个或多个矩阵的乘积，能够用相对较小的数据集来表示原始数据集，其他数据则被视作噪声或冗余信息，从而提高

19、运算效率和推荐精度。奇异值分解（Singular Value Decomposition，SVD）作为常见的矩阵分解技术，也常应用于降维。9.5.1 SVD算法原理9.5 SVD分解9.5 SVD分解9.5 SVD分解9.5.2 算法实例例1 SVD算法实现。利用线性代数工具箱 numpy.linalg的svd函数，实现代码如下：二维数组输入数据data，SVD函数输出3个矩阵U、S和V，其中U和V是正交矩阵，S由输入矩阵data的奇异值组成。使用np.diag(S)函数生成完整的奇异值矩阵，将U、S、V三个矩阵相乘还原出来的结果数据，可以看到它和原始矩阵data是十分接近的。9.5 SVD分

20、解U: -0.44721867 0.53728743 0.00643789 -0.50369332 -0.35861531 -0.24605053 -0.86223083 -0.14584826 -0.29246336 0.40329582 0.22754042 -0.10376096 -0.20779151 -0.67004393 0.3950621 -0.58878098 -0.50993331 -0.05969518 0.10968053 0.28687443 -0.53164501 -0.18870999 0.19141061 0.53413013S: 17.71392084 0. 0

21、. 0. 0. 6.39167145 0. 0. 0. 0. 3.09796097 0. 0. 0. 0. 1.32897797V: -0.57098887 -0.4274751 -0.38459931 -0.58593526 0.22279713 0.51723555 -0.82462029 -0.05319973 -0.67492385 0.69294472 0.2531966 -0.01403201 0.41086611 0.26374238 0.32859738 -0.80848795U*S*V: 5.00000000e+00 5.00000000e+00 1.38777878e-15

22、 5.00000000e+00 5.00000000e+00 2.39391840e-15 3.00000000e+00 4.00000000e+00 3.00000000e+00 4.00000000e+00 1.09634524e-15 3.00000000e+00 -5.55111512e-16 1.94289029e-16 5.00000000e+00 3.00000000e+00 5.00000000e+00 4.00000000e+00 4.00000000e+00 5.00000000e+00 5.00000000e+00 4.00000000e+00 5.00000000e+0

23、0 5.00000000e+00运行结果9.5 SVD分解9.5 SVD分解降序索引： 0 2 1降序的距离数组： 0.93401972 0.4508519 0.25244701运行结果如下经过SVD分解降维处理以后，与测试用户最相似的用户是第一行用户，可以将他评价过的物品推荐给测试用户。9.5 SVD分解9.5 SVD分解实例代码 9.5 SVD分解(9, 4.1039196647197578), (6, 4.077571965028409), (4, 4.0607093807694685)运行结果如下，表示按照影片相似度，优先推荐第9个、第6个、第4个影片。9.5 综合实例作为无监督学习的

24、一种应用，如果碰到特征维度较高的训练样本，可以考虑使用PCA特征降维方法获取低维度的样本特征，从而实现数据降维和压缩的目的。接下来以手写体数字图像识别为例来说明PCA算法的使用。9.6.1 PCA主成分分析9.6 综合实例实现代码 9.6 综合实例实现代码（续上） 9.6 综合实例手写体数字图像识别实现过程首先，使用sklearn中自带的手写数字数据集load_digits获得手写数字图像数据并存于digits变量中。利用train_test_split方法分割数据，并随机选取80%数据作为训练样本x_train，20%作为测试样本y_train；从sklearn.preprocessing里

25、导入数据标准化模块StandardScaler，对训练和测试的特征数据进行标准化。然后，分别训练两个以支持向量机分类器SVC为基础的手写数字图像识别模型，其中一个模型使用原始维度即64维的像素特征识别，另一个采用PCA降维重构之后的低维特征来识别图像特征，其中n_components设置为10，也就是将64维降到10维。预测出分类结果后，分别比较两个模型的准确率评分以及分类报告。最后，展示前100个测试样本数据以及PCA降维后的SVC分类结果9.6 综合实例The Accuracy of SVC is 0.988888888889classification report of SVC pre

26、cision recall f1-score support 0 1.00 1.00 1.00 29 1 0.98 1.00 0.99 46 2 1.00 0.97 0.99 37 3 1.00 1.00 1.00 39 4 0.96 1.00 0.98 25 5 0.97 0.97 0.97 37 6 0.98 1.00 0.99 41 7 1.00 1.00 1.00 29 8 1.00 0.98 0.99 44 9 1.00 0.97 0.98 33avg / total 0.99 0.99 0.99 360运行结果如下The Accuracy of PCA_SVC is 0.95classification report of PCA_SVC precision recall f1-score support 0 1.00 1.00 1.00 29 1 0.98 0.98 0.98 46 2 1.00 1.00 1.00 37 3 0.91 0.82 0.86 39 4 1.00 0.96 0.98 25 5 0.92 0.95 0.93 37