机器学习算法与实践 课件 第9章 聚类算法

第九章聚类算法

无监督学习（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算法，不需要指定类别的数量，聚类的形状可以是任意的，能找出数据中的噪音，对噪音不敏感，算法应用参数少。但对于密度不均匀的样本集、聚类间距差相差很大的样本集，聚类质量较差，一般不适合