机器学习算法与实践 课件 第9、10章 聚类算法、数据降维

第九章聚类算法

无监督学习（UnsupervisedLearning）是指在样本标记信息未知的情况下，通过对样本的学习来找到数据本身的内在性质和规律。无监督学习可以用于数据分析或者监督学习的前处理，主要包含聚类（Clustering）、降维（DimensionalityReduction）、概率估计（ProbabilityEstimation）等。

其中聚类应用最为广泛，其基本思想是将样本中“相似”的样本聚为相同的类或簇，“不相似”的样本聚为不同的类。19.1聚类概述相似或者不相似的定义和标准不是固定的，而是根据数据本身的性质决定。依据形状聚类依据颜色聚类

依据不同的策略，可以设计不同的聚类算法，主要包括原型聚类、层次聚类以及密度聚类。29.1.1相似度1.样本相似度

常用的有距离（Distance）（闵可夫斯基距离（MinkowskiDistance）、马哈拉诺比斯距离（MahalanobisDistance））、相关系数（CorrelationCoefficient）、夹角余弦等。

聚类的核心概念是相似度，其度量方式有很多种，并直接影响聚类结果的好坏，具体哪一种更好取决于问题本身的特性。39.1.1相似度（1）闵可夫斯基距离（MinkowskiDistance）

49.1.1相似度

（2）马哈拉诺比斯距离（MahalanobisDistance）59.1.1相似度

（3）相关系数(相关系数绝对值越接近1表示样本越相似；越接近0表示样本越不相似)

（4）夹角余弦(夹角余弦的数值越接近1表示样本越相似；越接近0表示样本越不相似)69.1.1相似度（5）VDM（ValueDifferenceMetric）距离

79.1.1相似度（6）加权距离（WeightedDistance）

89.1.1相似度2.类（或簇）的相似度或距离

99.1.2

性能度量

聚类算法的性能度量是一种“有效性指标（ValidityIndex）”，评估类内样本的相似度，不同类别之间的相似度，用以评价聚类结果以及聚类算法的好坏。

109.1.2

性能度量

显然，DBI指数越小越好，DI指数越大越好119.2

原型聚类

129.2

原型聚类

算法流程：139.2

原型聚类

149.3

密度聚类

假设聚类结构可以通过样本分布的紧密程度确定，以数据集在空间分布上的稠密程度为依据进行聚类。

此类算法无需预先设定类别数量，因此适合于未知内容的数据集，代表算法有DBSCAN、OPTICS、DENCLUE等(本节只讨论DBSCAN)主要思想：

逐步检查数据集中的每个样本，如果其邻域内的样本点总数小于某个阈值，那么定义该点为低密度点；反之，如果大于该阈值，则称其为高密度点。如果一个高密度点在另外一个高密度点的邻域内，就直接把这两个高密度点划分为一个类别；如果一个低密度点在一个高密度点的邻域内，则将该低密度点加入距离它最近的高密度点的类别中；不在任何高密度点邻域内的低密度点，被划入异常点类别，直到最终处理整个数据集。基本概念：159.3

密度聚类DBSCAN算法

其核心是找到样本点的全部密集区域，并把这些密集区域当作不同的类别。如下图所示：

利用“邻域”（Neighborhood）的半径和最少点数（Minpoints，简记为Minpts）两个参数刻画样本分布的紧密程度。169.3

密度聚类将样本点分为以下三类：

179.3

密度聚类非密度相连（Non-densityConnected）：如果两个点不属于密度相连关系，则两个点非密度相连。进一步定义四种样本点的关系：

189.3

密度聚类

任意选择一个没有类别的核心对象作为种子，然后找到所有这个核心对象能够密度可达的样本集合，即为一个类别。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合，这样就得到另一个聚类簇，这样的得到都肯定是密度相连的，一直运行到所有核心对象都有类别为止。DBSCAN方法199.3

密度聚类

20

例：如下图所示：

9.3

密度聚类

219.3

密度聚类

229.3

密度聚类

239.3

密度聚类

249.3

密度聚类

259.3

密度聚类（2）可以在聚类的同时发现异常点，对数据集中的异常点不敏感。主要优点：主要缺点：（1）如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，这时DBSCAN聚类一般不适合。

269.4

层次聚类(假设类别之间存在层次结构，将样本聚到层次化的类别中)聚合（Agglomerative）/自下而上（Bottom-up）聚类——本节重点分裂（Divisive）/自上而下（Top-down）聚类

每个样本各分到一个类，之后将距离相近的两类合并，建立一个新的类别，重复此操作直到满足停止条件，得到层次化的类别。

将所有的样本分到一个类，之后将已有类中相距最远的样本分到两个新的类，重复此操作直到满足停止条件，得到层次化的类别。279.4

层次聚类Agglomerative聚类算法基本流程：

距离尺度：最短距离、最长距离、平均距离、Ward方差等对应算法：“单链接（Single-linkage）”、“全链接（Complete-linkage）”、“单链接（Average-linkage）”

、“Ward链接（Ward-linkage）”等289.4

层次聚类例：单链接Agglomerative聚类算法步骤：

299.4

层次聚类

309.4

层次聚类图解示例：Agglomerative聚类算法可在不同层次上对数据集进行划分，形成一个树状的聚类结构，可以指定类别数也可不指定。但Agglomerative聚类算法的时间和空间复杂度较高，不适合解决大型数据集聚类问题。319.5

本章小结

DBSCAN算法，不需要指定类别的数量，聚类的形状可以是任意的，能找出数据中的噪音，对噪音不敏感，算法应用参数少。但对于密度不均匀的样本集、聚类间距差相差很大的样本集，聚类质量较差，一般不适合。Agglomerative聚类算法可在不同层次上对数据集进行划分，形成一个树状的聚类结构，可以指定类别数也可不指定。但Agglomerative聚类算法的时间和空间复杂度较高，不适合解决大型数据集聚类问题。其次，对于三种算法，通过不同案例，分别介绍了手工实现和调包实现两种代码实现方式。32第十章数据降维

数据降维是缓解维数灾难常用方法之一，是将原始数据映射到低维子空间，以达到降低维度的目的，这个过程中数据的特征发生了本质的变化，新的子空间的特征不再是原来的特征，因此不存在完全无损的降维方法，区别只是损失多少的问题.

针对研究对象，我们通常会收集一系列特征属性，对研究对象进行分析，属性越多，越有利于细致研究分析。但是随着属性增多，也会增加后续数据处理的运算量，带来较大的处理负担。3310.1

数据降维概述

数据降维方法从不同角度可以分为不同的类别，根据数据的特性划分，有线性降维和非线性降维；根据是否利用数据的监督信息划分，有无监督降维、有监督降维和半监督降维；根据是否保持数据的结构划分，有全局保持降维、局部保持降维和全局与局部保持一致降维等。需要根据特定的问题选择合适的数据降维方法.

本章主要介绍常见的两种数据降维技术：主成分分析（PrincipalComponentAnalysis，简称PCA）、线性判别分析（LinearDiscriminantAnalysis，简称LDA）。3410.2

主成分分析35

主成分分析（PrincipalComponentAnalysis，PCA）主要用于发现数据中变量之间的关系，是数据分析的有力工具，是一种常用的无监督学习方法，其原理是通过通过正交变换将一组可能存在相关性的变量转换为一组线性不相关的变量，转换后的这组变量叫主成分，它是原特征的线性组合，其个数通常小于原始变量的个数。10.2

主成分分析PCA算法原理：（1）由于样本的属性特征维数较高，相互之间存在关联关系.为了消除相关性，对原始属性进行线性线性组合，找到一组彼此不相关的属性特征；（2）在新的属性特征中，删除一些不重要的特征，保留较少特征数，同时保证损失较小.利用线性代数的知识对此进行解释：

3610.2.1

PCA算法原理

37

10.2.1

PCA算法原理38

对于二维降一维问题，只需要找到一个基向量就够了，即方差最大化就够了。但对于更高维的问题，还有其他基向量需要求解.10.2.1

PCA算法原理39

例如，三维降二维，第一个基向量通过方差找到，第二个如果也利用方差，那么它与第一个基向量几乎重合.我们希望第二个基向量与第一个线性无关，而协方差可以表示样本某两个属性的相关性.当协方差为0时，表示样本的某两个属性独立。

由上述讨论知，我们希望单个属性上方差最大，两两属性间协方差为0。为将二者统一，我们考虑协方差矩阵。10.2.1

PCA算法原理

那么同样地，可以推广至更高维。40

10.2.1

PCA算法原理若要找到一组新的正交基，使得在这组基下的样本集的协方差矩阵为对角阵，并且为了找到最大方差，对角线上元素应从大到小排列。

4110.2.1

PCA算法原理

利用特征值分解利用奇异值（SVD）分解

4210.2.1

PCA算法原理那么此时

SVD降维与特征值降维虽然原理一致，但不需要计算协方差矩阵，节省了计算量。4310.2.1

PCA算法原理贡献率

对于利用SVD实现的降维，我们可以利用奇异值衡量，将上面两个公式中的特征值替换为对应的奇异值即可。

4410.2.2

特征值分解降维利用特征值和特征向量实现PCA算法基本步骤：

4510.2.3

奇异值分解降维利用SVD实现PCA算法基本步骤：

4610.3线性判别分析(LinearDiscriminantAnalysis，简称LDA)LDA是一种经典的线性学习方法、分类算法，也是一种有监督降维方法。基本思想将数据投影到低维空间上，并且希望投影后的数据点满足：同一类别尽可能“接近”，不同类别尽可能“远离”。4710.3线性判别分析(LinearDiscriminantAnalysis，简称LDA)算法原理(以二分类问题为例)：

4810.3线性判别分析

4910.3线性判别分析二分类问题（1）广义Rayleigh商

5010.3线性判别分析（2）类内散度

5110.3线性判别分析

那么投影后的两类样本的方差和为

定义类内散度矩阵为5210.3线性判别分析（3）类间散度

（4）LDA模型（