第9章-降维

人民邮电出版社李克清主编《机器学习》教材配套课件学习目标学习目标第09章降维k-近邻学习主成分分析低维嵌入SVD分解人民邮电出版社李克清主编《机器学习》教材配套课件9.1引言降维（DimensionalityReduction，DR）是指采用线性或者非线性的映射方法将高维空间的样本映射到低维空间中。降维获得低维空间下的数据等价表示，实现高维数据的可视化呈现。等价的低维数据更方便存储、处理、计算和使用。降维能够去除数据噪声、降低算法开销。降维还可应用于文本分类和数据压缩等领域。降维可以得到原始数据的简化表示以加速后续处理或者改进输出结果，因此它已经成为很多算法数据进行预处理的重要手段。9.1.1降维的概念人民邮电出版社李克清主编《机器学习》教材配套课件9.1引言人民邮电出版社李克清主编《机器学习》教材配套课件9.1引言降维方法可分为线性降维和非线性降维两大类。线性降维假设构成数据集的各变量间独立无关。•主成分分析（PrincipalComponentAnalysis，PCA）•独立成分分析（IndependentComponentAnalysis，ICA）•线性判别分析（LinearDiscriminantAnalysis，LDA）非线性降维方法，也称之为流形学习方法（ManifoldLearning），其目标是从高维采样数据中恢复低维流形结构，不改变数据本身的拓扑特性。•基于保持全局结构信息，如等距离映射算法ISOMAP•关注局部结构信息，如LLE、LE、HLLE9.1.2常见算法分类人民邮电出版社李克清主编《机器学习》教材配套课件9.2k-近邻学习k-近邻(k-NearestNeighbor，kNN)：给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的k个实例，即k个邻居。如果这k个实例的多数属于某个类，就把该输入实例分类到这个类中。9.2.1算法实现kNN算法计算流程如下:•计算每个样本点与测试点的距离；•排序后取距离值最小的k个样本点作为k-近邻；•获取k-近邻的分类标签并计算各分类出现的次数；•找出出现次数最多的分类，返回该值作为测试点的分类结果。人民邮电出版社李克清主编《机器学习》教材配套课件9.2k-近邻学习实例代码人民邮电出版社李克清主编《机器学习》教材配套课件9.2k-近邻学习运行效果：•左下角两个点属于B类用蓝色点标识，右上角两个点属于A类用红色标识。取k值为3时通过kNN算法计算，距离测试点（0.2,0.1）最近的三个点中的两个点都是蓝色，因此测试点也是蓝色，属于B类。•这样的实现方式适合样本数量和特征数量比较少的情况。假设样本数量为N、特征数量为M，该算法时间复杂度是。面对大样本和特征数较多的情况，使用KD树、球树训练数据。以KD树为例，搜索时间复杂度为，适合于样本数量远大于特征数量的kNN搜索。()ONM(log())OMN人民邮电出版社李克清主编《机器学习》教材配套课件9.2k-近邻学习sklearn.neighbors模块集成了k-近邻相关的类，KNeighborsClassifier用做kNN分类树，KNeighborsRegressor用做kNN回归树。KNeighborsClassifier类的实现原型如下：9.2.2算法实例classsklearn.neighbors.KNeighborsClassifier(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.2k-近邻学习‘uniform’：所有近邻样本权重都一样；‘distance’：权重和距离成反比；[callable]，即回调函数：该函数的输入是距离数组，输出是同样大小的权重数组。•algorithm：计算近邻的算法，包括如下四种：’auto’，根据传递给fit方法的参数值，尝试选择最优算法；’ball_tree’，球树实现（BallTree）；’kd-tree’，KD树实现（KDTree）；‘brute’，暴力实现。•leafsize：整型，默认参数值为30。定义构建KD树或球树时叶子结点数量的阈值。这个值会影响构建和查询的速度，以及树的存储空间。•metric：字符串或回调函数，默认参数值为’minkowski’。给定树的距离度量方法。•p：整型，默认参数值为2。定义闵可夫斯基距离中的p值。人民邮电出版社李克清主编《机器学习》教材配套课件9.2k-近邻学习实例代码人民邮电出版社李克清主编《机器学习》教材配套课件9.2k-近邻学习在这个例子中，使用鸢尾花iris数据集作为训练数据集，提取该数据集的前两个特征值以简化样本。首先创建近邻分类的实例并对数据进行拟合，同时绘制了分类的边界，将不同分类点以不同的颜色显示出来。最后将训练数据集中的数据用不同颜色的散点显示出来。人民邮电出版社李克清主编《机器学习》教材配套课件9.2k-近邻学习kNN算法本身简单有效，能处理大规模的数据分类，尤其适用于样本分类边界不明显的情况。计算量较大且运行时需要大量内存：对每一个待分类数据都要计算它到全体已知样本的距离，才能求得它的k个最近邻点。kNN算法的三个基本要素：•（1）k值的选择：通过交叉验证的方式求出最合适的k值，默认取值为5。•（2）分类决策规则：通常采用多数表决决定。在类域间分布不平衡的情况下，采用为k个邻居分配不同权值的方法来改进。•（3）距离度量方法。9.2.3算法关键人民邮电出版社李克清主编《机器学习》教材配套课件9.3主成分分析通过某种线性投影，将高维的数据映射到低维的空间中表示，并期望在所投影的维度上数据的方差最大，以此使用较少的数据维度，同时保留住较多的原数据点的特性。PCA是丢失原始数据信息最少的一种线性降维方式，可以将PCA应用在数据压缩、数据可视化、提升机器学习速度等场景中。9.3.1算法思想PCA是将n维特征向量映射到r维上（），映射的过程要求每个维度的样本方差最大化，达到尽量使新的r维特征向量之间互不相关的目的。这些数据中拥有方差最大的r个维度被称为主成分。假设有样本数据集，每个样本有n个特征：。处理过程如下：rn12{,,...,}mXxxx12[,,...,]1iiiinxxxxim，人民邮电出版社李克清主编《机器学习》教材配套课件9.3主成分分析•计算样本均值生成去中心化的样本，得到中心化矩阵：,其中，，•计算S的协方差矩阵：，即•使用SVD奇异值分解方法计算协方差矩阵的特征值和特征向量。调用方法：linalg.svd()，矩阵中的特征值排序，选择其中最大的r个，将其对应特征向量作为列向量组成降维矩阵。•将样本点投影到选取的特征向量上，降维后的数据为：1212,,,,,,mmSSSSxμxμxμ12n=μ，，，11mjijixm1jn1TCOVmSS1Tmiii=1COVmSS,,TSVDCOVUΣVnrUnrUmrmnnrZSU人民邮电出版社李克清主编《机器学习》教材配套课件9.3主成分分析我们使用贡献率来判断选择主成分的个数。贡献率是指选取的r个特征值总和占全部特征值总和的比重，一般应取85%以上。公式如下：9.3.2算法实例11=riinii贡献率scikit-learn提供了主成分分析相关的类sklearn.decomposition，其函数原型如下：classsklearn.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算法后原始训练数据的值会改变。•whiten：布尔值类型，默认参数值为False。白化，使得每个特征具有相同的方差。从转换后的信号中删除一些信息，提高下游估计值的预测精度。•svd_solver：字符串。可以取值’auto’，’full’，’arpark’，或’randomized’。以三维的球型数据集为原始数据对象，通过降维方法把它降成二维数据：人民邮电出版社李克清主编《机器学习》教材配套课件9.3主成分分析实例代码人民邮电出版社李克清主编《机器学习》教材配套课件9.3主成分分析运行结果如下：n_components=2.000000主成分方差比例：[0.983182120.00850037]主成分方差：[3.784837850.03272285]n_components=0.950000主成分方差比例：[0.98318212]主成分方差：[3.78483785]n_components=0.990000主成分方差比例：[0.983182120.00850037]主成分方差：[3.784837850.03272285]n_components=mle主成分方差比例：[0.98318212]主成分方差：[3.78483785]首先使用scikit提供的make_blobs方法，在指定样本点数量、特征数量、中心点、范围等基础上生成三维球型数据；当n_components=2时，将数据降维到二维，即保留2个主成分；当n_components=0.95时，表示不直接指定降维的维度，而指定降维后的主成分方差占总方差值的比例为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低维嵌入传统的线性降维方法，如主成分分析PCA，在把高维数据映射到低维空间时通常不能保留原高维数据的内在非线性结构和特征。非线性的方法如LLE、hessian局部线性嵌入算法HLLE等应运而生。它们的优点是具有较少的参数需要设置，而且使用非迭代方法求解从而可以避免陷入局部极小。9.4.1算法原理LLE算法基本思想是把整个非线性流形分为许多个小块，这些小块由各数据点与它的k个邻居点构成，每个小块可以看作是拥有局部线性结构的。每个数据点和它的k个邻居点的线性组合系数称为重构权重。LLE认为所有数据点降到低维后邻居关系不变，包括重构权重也不变。因此将小块数据线性降维后，再把它们拼接起来，即可构成高维数据的低维表示。人民邮电出版社李克清主编《机器学习》教材配套课件9.4低维嵌入低维嵌入（LLE）算法大致如下：（1）假设数据由n个m维样本点𝒙