Python数据挖掘与机器学习第2版 课件 第 8 章 聚类

Python数据挖掘与机器学习第8章聚类第8章聚类本章内容聚类分析K-Means聚类层次聚类基于密度的聚类其他聚类方法聚类评估10十一月20242第8章聚类3无监督学习（UnsuperviseLearning）着重于发现数据本身的分布特点。与监督学习（SupervisedLearning）不同，无监督学习不需要对数据进行标记。从功能角度讲，无监督学习模型可以发现数据的“群落”，同时也可以寻找“离群”的样本。另外，对于特征维度非常高的数据样本，同样可以通过无监督学习进行数据降维，保留最具有区分性的低维度特征。聚类是一个将数据对象集划分为多个组或簇的过程，使得簇内的数据对象具有很高的相似性，但不同簇间的对象具有很高的相异性。第8章聚类4聚类算法分类随着聚类分析技术的蓬勃发展，目前已有很多类型的聚类算法。但很难对聚类方法进行简单的分类，因为这些类别的聚类可能重叠，从而使得一种方法具有一些交叉的特征。一般而言，聚类算法被划分为以下几类：1.划分方法2.基于层次的方法3.基于密度的方法4.局域网格的方法K-Means聚类聚类分析中最广泛使用的算法为K-Means聚类算法。10十一月20245给定一个n个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个簇，k<=n，而且满足：（1）每个组至少包含一个对象；（2）每个对象属于且仅属于一个组。划分时要求同一个聚类中的对象尽可能地接近或相关，不同聚类中的对象尽可能地远离或不同。K-Means算法是一个迭代的优化算法，最终使得下面均方误差最小。

K-Means聚类K-Means算法：10十一月20246用于划分的K-Means算法，其中每个簇的中心都用簇中所有对象的均值来表示。K-Means聚类模型所采用的迭代算法直观易懂且非常实用。但是具有容易收敛到局部最优解和需要预先设定簇的数量的缺陷。K-Means聚类7K=2随机划分更新聚类中心更新聚类中心指派对象类标号Loopifneeded初始数据集k均值算法的评论优点：可扩展性较好，算法复杂度为O(nkt)，其中n为对象总数，k是簇的个数，t是迭代次数。经常终止于局部最优解k均值算法的评论缺点只有当簇均值有定义的情况下，k均值方法才能使用。（某些分类属性的均值可能没有定义）用户必须首先给定簇数目不适合发现非凸形状的簇，或者大小差别很大的簇对噪声和离群点数据敏感k均值算法实现fromsklearn.datasetsimportload_irisfromsklearn.clusterimportKMeansiris=load_iris()#加载数据集X=iris.dataestimator=KMeans(n_clusters=3)#构造K-Means聚类模型estimator.fit(X)#数据导入模型进行训练label_pred=estimator.labels_#获取聚类标签print(label_pred)#显示各个样本所属的类别标签[111111111111111111111111111111111111111111111111110020000000000000000000000002000000000000000000000020222202222220022220202022002222202222022202220220]11/10/2024k均值方法的变种k均值方法有些变种，他们的区别在于不同的初始k个均值的选择不同的相异度计算不同的计算簇均值的策略k均值方法的变种聚类分类数据的方法：k众数（mode）方法用众数来替代簇的均值采用新的相异性度量处理分类对象采用基于频率的方法更新簇的众数可以集成k均值和k众数方法，对具有数值和分类值的数据进行聚类K-Means聚类K-Means算法改进：1.K-means++算法K-means算法初始时随机选取数据集中K个点作为聚类中心，不同的初始聚类中心可能导致完全不同的聚类结果。K-means++算法初始的聚类中心之间的相互距离要尽可能的远。10十一月202413K-Means聚类K-Means算法改进：2.ISODATA算法ISODATA的全称是迭代自组织数据分析法，是在K-means算法的基础上，增加对聚类结果的“合并”和“分裂”两个操作，当属于某个类别的样本数过少时则删除该类，当属于某个类别的样本数过多、分散程度较大时，把这个类分裂为两个子类别。10十一月202414K-Means聚类K-Means算法改进：3.MiniBatch-KMeansMiniBatch-KMeans是一种能尽量保持聚类准确性但能大幅度降低计算时间的聚类模型。MiniBatch-KMeans聚类每次迭代并不采用所有样本，而是每次等量采样获得小的样本集并把小样本集中的样本划归到距离最近的中心所在的簇，然后进行聚类中心点的更新。与K-Means算法相比，簇中心点的更新是在每个小的样本集上。MiniBatch-KMeans可以大大减少算法运行时间，但产生的聚类效果只是略低与K-Means算法，适合于极大数据量的聚类分析。10十一月2024153.层次聚类算法原理层次聚类（HierarchicalClustering）就是按照某种方法进行层次分类，直到满足某种条件为止。层次聚类主要分成两类：凝聚：从下到上。首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者满足某个终结条件。分裂：从上到下。首先将所有对象置于同一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终止条件。10十一月2024163.层次聚类簇间距离度量1.最短距离法（最大相似度）最短距离被定义为两个类中最靠近的两个对象间的距离为簇间距离。2.最长距离法（最小相似度）最长距离被定义为两个类中最远的像个对象间的距离为簇间距离。10十一月2024173.层次聚类簇间距离度量3.类平均法计算两类中任意两个对象间的距离的平均值作为簇间距离4.中心法定义两类的两个中心点的距离为簇间距离。10十一月2024183.层次聚类分裂层次聚类DIANA分裂的层次聚类方法使用自顶向下的策略把对象划分到层次结构中。从包含所有对象的簇开始，每一步分裂一个簇，直到仅剩单点簇或者满足用户指定的簇数为止。DIANA算法是典型的层次分裂聚类算法。DIANA算法中用到如下两个定义：簇的直径：计算一个簇中任意两个数据点之间的欧式距离，选取距离中的最大值作为簇的直径。平均相异度：两个数据点之间的平均距离。10十一月2024193.层次聚类DIANA算法描述：10十一月2024203.层次聚类凝聚层次聚类AGNES凝聚的层次聚类方法使用自底向上的策略把对象组织到层次结构中。开始时以每个对象作为一个簇，每一步合并两个最相似的簇。AGNES算法是典型的凝聚层次聚类，起始将每个对象作为一个簇，然后根据合并准则逐步合并这些簇。两个簇间的相似度由这两个不同簇中距离最近的数据点的相似度确定。聚类的合并过程反复进行直到所有对象最终满足终止条件设置的簇数目。10十一月2024213.层次聚类凝聚层次聚类AGNES10十一月2024223.层次聚类凝聚层次聚类AGNES10十一月2024233.层次聚类凝聚层次聚类AGNES10十一月2024243.层次聚类层次聚类应用Python中层次聚类的函数是AgglomerativeClustering()，最重要的参数有3个：n_clusters为聚类数目，affinity为样本距离定义，linkage是类间距离的定义，有3种取值：ward：组间距离等于两类对象之间的最小距离average：组间距离等于两组对象之间的平均距离complete：组间距离等于两组对象之间的最大距离10十一月2024254基于密度的聚类Generateclustersofarbitraryshapes.Robustagainstnoise.NoKvaluerequiredinadvance.Somewhatsimilartohumanvision.26划分和层次方法旨在发现球状簇，很难发现任意形状的簇。4基于密度的聚类基于密度的聚类算法的主要思想是：只要邻近区域的密度（对象或数据点的数目）超过某个阈值

，就把它加到与之相近的聚类中。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。基于密度的聚类算法代表算法有：DBSCAN算法、OPTICS算法及DENCLUE算法等。

10十一月2024274基于密度的聚类两个参数:Eps:邻域最大半径MinPts:在Eps邻域中的最少点数定义1（Eps邻域）

给定一个对象

p，p的Eps邻域

NEps（p）定义为以

p为核心，以Eps为半径的d维超球体区域，即：其中，D为d维实空间上的数据集，dist(p,q)表示D中的2个对象p和q之间的距离。284基于密度的聚类DBSCAN算法涉及2个参数5个定义：10十一月2024292个参数:Eps:邻域最大半径MinPts:在Eps邻域中的最少点数5个定义见表:定义内容Eps邻域给定一个对象

p，p的Eps邻域

NEps（p）定义为以

p为核心，以Eps为半径的d维超球体区域核心点与边界点对于对象p∈D，给定一个整数MinPts，如果p的Eps邻域内的对象数满足|NEps(p)|≥MinPts

，则称p为(Eps，MinPts)条件下的核心点；不是核心点但落在某个核心点的Eps邻域内的对象称为边界点4基于密度的聚类10十一月202430直接密度可达给定

(Eps，MinPts)，如果对象p和

q同时满足如下条件：p∈NEps(q)；|NEps(q)|≥MinPts

（即q是核心点），则称对象

p是从对象

q出发，直接密度可达的密度可达给定数据集D，当存在一个对象链

p1，p2，p3，…，pn，

其中

p1=q，

pN=

p，对于

pi∈D，如果在条件(Eps，MinPts)下pi+1从pi

直接密度可达，则称对象p从对象q在条件

(Eps，MinPts)下密度可达密度相连如果数据集D中存在一个对象o，使得对象p和q是从o在

(Eps，MinPts)条件下密度可达的，那么称对象p和q在

(Eps，MinPts)条件下密度相连定义2（核心点与边界点）

对于对象p∈D，给定一个整数MinPts，如果p的Eps邻域内的对象数满足|NEps(p)|≥MinPts

，则称p为(Eps，MinPts)条件下的核心点；不是核心点但落在某个核心点的Eps邻域内的对象称为边界点。

CorePointNoisePointBorderPoint4基于密度的聚类4基于密度的聚类定义3（直接密度可达）

如图所示，给定(Eps，MinPts)，如果对象

p和

q同时满足如下条件：p∈NEps(q)；|NEps(q)|≥MinPts

（即q是核心点），

则称对象

p是从对象

q出发，直接密度可达的。定义4（密度可达）

如图所示，给定数据集D，当存在一个对象链

p1，p2，p3，…，pn，

其中

p1=q，

pN=

p，对于

pi∈D，如果在条件(Eps，MinPts)下

pi+1从pi

直接密度可达，则称对象p从对象q在条件(Eps，MinPts)下密度可达。密度可达是非对称的，即p从q密度可达不能推出q也从p密度可达。

4基于密度的聚类定义5（密度相连）

如图所示，如果数据集D中存在一个对象o，使得对象p和q是从o在(Eps，MinPts)条件下密度可达的，那么称对象p和q在(Eps，MinPts)条件下密度相连。密度相连是对称的。4基于密度的聚类4基于密度的聚类35pqdirectlydensityreachablepqdensityreachableoqpdensityconnected4基于密度的聚类DBSCAN算法描述：10十一月202436输入：Eps、MinPts和包含n个对象的数据库。

输出：基于密度的聚类结果。

方法：（1）任意选取一个没有加簇标签的点p；（2）得到所有从p关于

Eps和

MinPts密度可达的点；（3）如果p是一个核心点，形成一个新的簇，给簇内所有对象点加簇标签；（4）如果p是一个边界点，没有从p密度可达的点，DBSCAN将访问数据库中的下一个点；（5）继续这一过程，直到数据库中所有的点都被处理。-邻域寻找聚类，将具有足够高密度的区域划分为簇，并可以在带有“噪声”的空间数据库中发现任意形状的聚类。但是，DBSCAN算法对用户设置的参数敏感，Eps和MinPts的设置会影响聚类的效果。针对这一问题，OPTICS（OrderingPointstoIdentifytheClusteringStructure）算法被提出，它通过引入核心距离和可达距离，使得聚类算法对输入的参数不敏感。

4基于密度的聚类10十一月202437DBSCAN需要对数据集中的每个对象进行考察，通过检查每个点的4基于密度的聚类算法实现课本例8-3利用sklearn实现：11/10/2024importnumpyasnpimportmatplotlib.pyplotaspltfromsklearn.clusterimportDBSCANfromsklearnimportdatasetsiris=datasets.load_iris()data=iris.datadbscan=DBSCAN(eps=0.4,min_samples=10,metric='euclidean')dbscan.fit(data)label_pred=dbscan.labels_5其他聚类方法除了常用的划分聚类、层次聚类和密度聚类方法之外，还有一些聚类方法如网格聚类方法STING、概念聚类COBWEB和模糊聚类方法等。1.STING算法STING（StatisticalInformationGrid_basedMethod）是一种基于网格的多分辨率的聚类技术，它将输入对象的空间区域划分成矩形单元，空间可以用分层和递归方法进行划分。这种多层矩形单元对应不同的分辨率，并且形成一个层次结构，每个高层单元被划分为低一层的单元。有关每个网格单元的属性的统计信息（如均值、最大值和最小值）被作为统计参数预先计算和存储。10十一月2024395其他聚类方法除了常用的划分聚类、层次聚类和密度聚类方法之外，还有一些聚类方法如网格聚类方法STING、概念聚类COBWEB和模糊聚类方法等。2COBWEB概念聚类是机器学习中的一种聚类算法。大多数的概念聚类方法采用了统计学方法，在决定概念或聚类时使用概率度量。COBWEB算法即简单增量概念聚类算法，以一个分类树的形式创建层次聚类，它的输入对象用分类属性-值对进行描述。10十一月2024405其他聚类方法3模糊聚类10十一月202441模糊C均值聚类（FuzzyC-means，FCM）融合了模糊理论的精髓。相较于K-means的硬聚类，FCM聚类提供了更加灵活的聚类结果，它对每个对象和每个簇赋予一个权值，指明对象属于该簇的程度（隶属度）。5其他聚类方法3模糊聚类10十一月202442采用拉格朗日乘数法，求解得到参数的更新值：5其他聚类方法3模糊聚类10十一月202443输入：数据样本X输出：每个样本属于的隶属度及聚类中心过程：（1）设置初始值：算法迭代时目标函数的精度阈值，模糊度和迭代的最大次数;(2)初始化聚类中心和隶属度矩阵;(3)使用公式8.9-8.10更新隶属度矩阵

和聚类中心

;(4)加入

或迭代次数

结束迭代过程，否则转步骤（3）;5其他聚类方法Python中提供了模糊运算的包scikit-fuzzy，简称skfuzzy，初次使用时需要安装。skfuzzy中包含了FCM聚类方法：center,u,u0,d,jm,p,fpc=cmeans(x.T,m=2,c=k,error=0.5,maxiter=1000)其中的主要参数u是最终的隶属度矩阵，u0是初始化隶属度矩阵，d是每个数据到各个中心的欧式距离矩阵，jm是目标函数优化，p是迭代次数，fpc是评价指标，0表示最差、1最好。11/10/20245其他聚类方法11/10/20245其他聚类方法11/10/20245其他聚类方法11/10/20245其他聚类方法11/10/20245其他聚类方法11/10/2024在sklearn中利用GaussianMixture方法实现高斯混合聚类，主要参数有n_components、covariance_type和max_iter。其中，n_components表示高斯混合模型的个数，即要聚类的个数，默认值为1；max_iter代表最大迭代次数，默认值为100；covariance_type代表协方差类型。X,lables_true=make_blobs(n_samples=n_samples,centers=centers,cluster_std=0.8,random_state=71)gmm=GaussianMixture(n_components=3,random_state=23)gmm.fit(X)gmm_labels=gmm.predict(X)gmm_silhouette_score=silhouette_score(X,gmm_labels)print("高斯混合模型聚类性能:")print("轮廓系数:{:.4f}".format(gmm_silhouette_score))5其他聚类方法11/10/20245其他聚类方法11/10/20245其他聚类方法11/10/20246.聚类评估聚类评估用于对在数据集上进行聚类的可行性和被聚类方法产生的结果的质量进行评估。聚类评估主要包括以下任务：1.估计聚类趋势2.确定数据集中的划分簇数3.测定聚类质量10十一月2024536.聚类评估1聚类趋势的估计10十一月202454如果D是均匀分布的，H接近0.5.6.聚类评估2聚类簇数的确定找出正确的簇数依赖于数据集分布的形状和尺度，也依赖于用户要求的聚类分辨率。有许多估计簇数的可能方法。这里简略介绍几种简单但流行和有效的方法。10十一月2024556.聚类评估10十一月202456拐点法基于如下观察：增加簇数有助于降低每个簇的簇内方差之和。这是因为有更多的簇可以捕获更细的数据对象簇，簇中对象之间更为相似。然而，如果形成太多的簇，则降低簇内方差和的边缘效应可能下降，因为把一个凝聚的簇分裂成两个簇只能使簇内方差和的稍微降低。因此，一种选择正确的簇数启发式方法是使用簇内方差和关于簇数曲线的拐点。6.聚类评估10十一月202457肘方法的核心思想是：随着聚类数K的增大，样本划分会更加精细，每个簇的聚合程度会逐渐提高，那么误差平方和SSE自然会逐渐变小。并且，当K小于真实聚类数时，由于K的增大会大幅增加每个簇的聚合程度，故SSE的下降幅度会很大，而当K到达真实聚类数时，再增加K所得到的聚合程度回报会迅速变小，所以SSE的下降幅度会骤减，然后随着K值的继续增大而趋于平缓，也就是说SSE和K的关系图是一个手肘的形状，而这个肘部对应的K值就是数据的真实聚类数。6.聚类评估聚类质量的测定1.外在方法有许多度量（如熵、纯度、精度、召回率和F度量）用来评估分类模型的性能。对于分类，度量预测的类标号与实际类标号的对应程度。但是这些度量通过使用簇标号而不是预测的类标号，不需要做较大的改变。兰德系数RI和ARI：

10十一月20