数据挖掘（第2版） 课件 第5章 聚类

高级大数据人才培养丛书之一，大数据挖掘技术与应用数据挖掘（第二版）5.1什么是聚类分析?第五章

聚类5.2聚类方法分类5.3

k均值聚类5.4

层次聚类of432高级大数据人才培养丛书之一，大数据挖掘技术与应用5.5密度聚类5.1

什么是聚类分析？第五章聚类簇：一个数据对象的集合。聚类是将对象集合中的对象分类到不同的类或者簇这样的一个过程，使得同一个簇中的对象有很大的相似性，而不同簇间的对象有很大的相异性。簇内的相似性越大，簇间差别越大，聚类就越好。聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现，聚类方法的好坏还取决与该方法是能发现某些还是所有的隐含模式。按照聚类的主要思路的不同，聚类可以分为：划分聚类、层次聚类、基于密度的聚类、基于网格的聚类、基于模型的聚类。5.1

什么是聚类分析？第五章聚类聚类典型的应用市场销售。帮助市场人员发现客户中的不同群体，然后用这些知识来开展一个目标明确的市场计划。保险。对购买了汽车保险的客户，标识哪些有较高平均赔偿成本的客户。城市规划。根据类型、价格、地理位置等来划分不同类型的住宅。对搜索引擎返回的结果进行聚类，使用户迅速定位到所需要的信息。对用户感兴趣的文档（如用户浏览过的网页）聚类，从而发现用户的兴趣模式并用于信息过滤和信息主动推荐等服务。数据挖掘对聚类的典型要求：可伸缩性能够处理不同类型的属性能发现任意形状的簇在决定输入参数的时候，尽量不需要特定的领域知识；能够处理噪声和异常对输入数据对象的顺序不敏感能处理高维数据能产生一个好的、能满足用户指定约束的聚类结果结果是可解释的、可理解的和可用的5.1

什么是聚类分析？第五章聚类5.2

第五章

聚类5.1什么是聚类分析?5.3

k均值聚类5.4

层次聚类of436高级大数据人才培养丛书之一，大数据挖掘技术与应用5.5密度聚类聚类方法分类5.2

聚类方法分类第五章聚类按照聚类方法的主要思路的不同，聚类方法分为：划分聚类层次聚类基于密度的聚类基于网格的聚类基于模型的聚类5.3

第五章

聚类5.1什么是聚类分析?5.2聚类方法分类5.4

层次聚类of438高级大数据人才培养丛书之一，大数据挖掘技术与应用5.5密度聚类k均值聚类5.3

k均值聚类第五章聚类对于给定的数据集，划分聚类方法首先创建一个初试划分，然后采用一种迭代的重定位技术，尝试通过对象在划分间的移动来改进划分，直到使评价聚类性能的评价函数的值达到最优为止。划分聚类方法以距离作为数据集中不同数据间的相似性度量，将数据集划分成多个簇。划分聚类方法是最基本的聚类方法，属于这样的聚类方法、k中心点（k-medoids）等。有k均值（k-means）k中心点（k-medoids）5.3

k均值聚类第五章聚类划分聚类方法的主要思想

给定一个包含n个数据对象的数据集，划分聚类方法将数据对象的数据集进行k个划分，每个划分表示一个簇(类)，并且k≤n，同时满足两个条件：每个簇至少包含一个对象，每个对象属于且仅属于一个簇。对于给定k，划分聚类方法首先给出一个初始的划分，然后采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分，使得每一次改进之后的划分方案都较前一次更好。好的划分是指同一簇中的对象之间尽可能“接近”，不同簇中的对象之间尽可能“远离”。5.3

k均值聚类第五章聚类划分聚类方法的评价函数评价函数着重考虑两方面，即每个簇中的对象应该是紧凑的，各个簇间的对象的距离应该尽可能远。实现这种考虑的一种直接方法就是观察聚类C的类内差异w(C)和类间差异b(C)。类内差异衡量类内的对象之间的紧凑性，类间差异衡量不同类之间的距离。类内差异可以用距离函数来表示，最简单的就是计算类内的每个对象点到它所属类的中心的距离的平方和。类间差异定义为类中心之间距离的平方和。5.3

k均值聚类第五章聚类k均值聚类的算法思想(1)从包含n个数据对象的数据集中随机的选择k个对象，每个对象代表一个簇的平均值或质心或中心；(2)对剩余的每个数据对象点根据其与各个簇中心的距离，将它指派到最近的簇；(3)根据指派到簇的数据对象点，更新每个簇的中心；(4)重复指派和更新步骤，直到簇不发生变化，或直到中心不发生变化，或度量聚类质量的目标函数收敛。

5.3

k均值聚类第五章聚类k均值算法输入：所期望的簇的数目k，包含n个对象的数据集D输出：k个簇的集合①从D中任意选择k个对象作为初始簇中心；②repeat③将每个点指派到最近的中心，形成k个簇；④重新计算每个簇的中心；⑤计算目标函数E；⑥until目标函数E不再发生变化或中心不再发生变化；5.3

k均值聚类第五章聚类Python实现对鸢尾花数据集k均值聚类可使用sklearn.cluster中的KMeans模型来实现k均值算法：sklearn.cluster.KMeans(n_clusters=8,init='k-means++',n_init=10,max_iter=300,tol=0.0001,precompute_distances='auto',n_jobs=1)n_clusters：整形，缺省值为8，拟打算生成的聚类数。init：簇质心初始值的选择方式，有k-means++、random、以及一个ndarray三种可选值。n_init：用不同的初始化质心运行算法的次数，多运行几次以选择一个较好的聚类效果，默认是10precompute_distances：预计算距离，计算速度快但占用更多内存。5.3

k均值聚类第五章聚类KMeans模型的属性cluster_centers_：输出聚类的质心，数据形式是数组。labels_：输出每个样本点对应的类别。inertia_：float型，每个点到其簇的质心的距离的平方和KMeans模型的方法fit(X)：在数据集X上进行k-means聚类。predict(X)：对X中的每个样本预测其所属的类别。fit_predict(X)：计算X的聚类中心，并预测X中每个样本的所属的类别，相当于先调用fit(X)再调用predict(X)。score(X[,y])：X中每一点到聚类中心的距离平方和的相反数。5.3

k均值聚类第五章聚类使用k-means对鸢尾花数据集聚类fromsklearn.datasetsimportload_irisfromsklearn.clusterimportKMeansimportmatplotlib.pyplotaspltimportnumpyasnpimportmatplotlibfromsklearn.cross_validationimporttrain_test_split#交叉验证iris=load_iris()#加载数据

target=iris.target#提取数据集中的标签（花的类别）set(target)#查看数据集中的标签的不同值，{0,1,2}iris['feature_names']#查看数据的特征名['sepallength(cm)','sepalwidth(cm)','petallength(cm)','petalwidth(cm)']5.3

k均值聚类第五章聚类使用k-means对鸢尾花数据集聚类data=iris.data#提取数据集中的特征数据X=data[:,[0,2]]#提取第1列和第3列，即花萼与花瓣长度y=iris.target#获取类别属性数据label=np.array(y)#转换数据类型index_0=np.where(label==0)#获取类别为0的数据索引#按选取的两个特征绘制散点plt.scatter(X[index_0,0],X[index_0,1],marker='o',color='red',edgecolors='k',label='label0')index_1=np.where(label==1)#获取类别为1的数据索引plt.scatter(X[index_1,0],X[index_1,1],marker='*',color='purple',label='label1')5.3

k均值聚类第五章聚类使用k-means对鸢尾花数据集聚类index_2=np.where(label==2)#获取类别为2的数据索引plt.scatter(X[index_2,0],X[index_2,1],marker='+',color='blue',label='label2')plt.xlabel('sepallength',fontsize=15)plt.ylabel('petallength',fontsize=15)plt.legend(loc='lowerright')plt.show()#显示按鸢尾花数据集的两个特征绘制的散点图5.3

k均值聚类第五章聚类使用k-means对鸢尾花数据集聚类X_train,X_test,y_train,y_test=train_test_split(X,y,random_state=1)kms=KMeans(n_clusters=3)#构造k均值模型,设定聚类数为3kms.fit(X_train)#在数据集X_train上进行k-means聚类label_pred=kms.labels_#获取聚类标签#绘制k-means结果x0=X_train[label_pred==0]x1=X_train[label_pred==1]x2=X_train[label_pred==2]plt.scatter(x0[:,0],x0[:,1],color='red',marker='o',edgecolors='k',label='label0')5.3

k均值聚类第五章聚类使用k-means对鸢尾花数据集聚类plt.scatter(x1[:,0],x1[:,1],color='blue',marker='*',edgecolors='k',label='label1')plt.scatter(x2[:,0],x2[:,1],c="k",marker='+',label='label2')>>>plt.xlabel('sepallength',fontsize=15)>>>plt.ylabel('petallength',fontsize=15)>>>plt.legend(loc='lowerright')>>>plt.show()#显示鸢尾花数据集k-means聚类的结果5.3

第五章

聚类5.1什么是聚类分析?5.2聚类方法分类5.3

k均值聚类of4321高级大数据人才培养丛书之一，大数据挖掘技术与应用5.5密度聚类k均值聚类5.3

k均值聚类5.4层次聚类5.4层次聚类第五章聚类层次聚类原理层次聚类是通过递归地对数据对象进行合并或者分裂，直到满足某种终止条件为止。根据层次分解是自底向上（合并）还是自顶向下（分裂）形成，层次聚类方法分为凝聚型聚类方法和分裂型聚类方法。自底向上的凝聚层次聚类输入：n个对象，终止条件簇的数目k输出：k个簇1：将每个对象当成一个初始簇2：Repeat3：根据两个簇中最近的数据点找到最近的两个簇4：合并两个簇，生成新的簇的集合5：Until达到定义的簇的数目5.4层次聚类第五章聚类使用AGNES算法将表格中的数据聚为2个簇。序号属性1属性21112123214225346357448455.4层次聚类第五章聚类使用AGNES算法将表格中的数据聚为2个簇。步骤最近的簇距离选取最近的两个簇合并后的新簇11{1}、{2}{1,2}、{3}、{4}、{5}、{6}、{7}、{8}21{3}、{4}{1,2}、{3,4}、{5}、{6}、{7}、{8}31{5}、{6}{1,2}、{3,4}、{5,6}、{7}、{8}41{7}、{8}{1,2}、{3,4}、{5,6}、{7,8}51{1、2}、{3、4}{1,2,3,4}、{5,6}、{7,8}61{5、6}、{7、8}

{1,2,3,4}、{5,6,7,8}5.4层次聚类第五章聚类自顶向下的分裂层次聚类首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终止条件，例如达到了某个希望的簇数目，或者两个最近的簇之间的距离超过了某个阈值。经典的分裂层次聚类算法以DIANA算法为代表。簇间距离度量方法1）簇间最小距离是指用两个簇中所有数据点的最近距离代表两个簇的距离。2）簇间最大距离是指用两个簇所有数据点的最远距离代表两个簇的距离。5.4层次聚类第五章聚类自顶向下的分裂层次聚类簇间距离度量方法3）簇间均值距离是指用两个簇各自中心点之间的距离代表两个簇的距离。4）簇间平均距离用两个簇所有数据点间的距离的平均值代表两个簇的距离。最小最大度量代表了簇间距离度量的两个极端，它们趋向对离群点或噪声数据过分敏感。使用均值距离和平均距离是对最小和最大距离之间的一种折中方法，而且可以克服离群点敏感性问题。尽管均值距离计算简单，但是平均距离也有它的优势，因为它既能处理数值数据又能处理分类数据。5.4层次聚类第五章聚类Python实现簇间最大距离的凝聚层次聚类算法importpandasaspdimportnumpyasnpnp.random.seed(150)features=['f1','f2','f3']#设置特征的名称labels=["s0","s1","s2","s3","s4"]#设置数据样本编号X=np.random.random_sample([5,3])*10#生成一个(5,3)的数组#通过pandas将数组转换成一个DataFrame类型df=pd.DataFrame(X,columns=features,index=labels)5.4层次聚类第五章聚类Python实现簇间最大距离的凝聚层次聚类算法print(df)#查看生成的数据运行上述代码得到的输出结果如下：f1f2f3s09.0858392.5797168.776551s17.3896556.9807655.172086s29.5210969.1364450.781745s37.8232051.1366546.408499s40.7976302.3196603.8595155.4层次聚类第五章聚类Python实现簇间最大距离的凝聚层次聚类算法下面使用scipy库中spatial.distance子模块下的pdist函数来计算距离矩阵，将矩阵用一个DataFrame对象进行保存。pdist：计算两两样本间的欧氏距离，返回的是一个一维数组squareform：将数组转成一个对称矩阵fromscipy.spatial.distanceimportpdist,squareformdist_matrix=pd.DataFrame(squareform(pdist(df,metric='euclidean')),columns=labels,index=labels)print(dist_matrix)#查看距离矩阵在上述代码中，基于样本的特征f1、f2和f3，使用欧几里得距离计算了两两样本间的距离，运行上述代码得到的结果如下：5.4层次聚类第五章聚类Python实现簇间最大距离的凝聚层次聚类算法

s0s1s2s3s4s00.0000005.93619810.3487723.0470239.640502s15.9361980.0000005.3352695.9891848.179458s210.3487725.3352690.0000009.92672511.490870s33.0470235.9891849.9267250.0000007.566738s49.6405028.17945811.4908707.5667380.0000005.4层次聚类第五章聚类Python实现簇间最大距离的凝聚层次聚类算法下面通过scipy的linkage函数，获取一个以簇间最大距离作为距离判定标准的关系矩阵。fromscipy.cluster.hierarchyimportlinkage#linkage()以簇间最大距离作为距离判断标准，得到一个关系矩阵#linkage()返回长度为n-1的数组，其包含每一步合并簇的信息，n为数据集的样本数row_clusters=linkage(pdist(df,metric='euclidean'),method="complete")print(row_clusters)#输出合并簇的过程信息输出结果如下：5.4层次聚类第五章聚类Python实现簇间最大距离的凝聚层次聚类算法输出结果如下：[[0.3.3.047022522.][1.2.5.335268652.][4.5.9.64050243.][6.7.11.490869655.]]每一行的格式是[idx1,idx2,dist,sample_count]。在第一步[0.3.3.047022522.]中，linkage()决定合并簇0和簇3，因为他们之间的距离为3.04702252，为当前最短距离。这里的0和3分别代表簇在数组中的下标。在这一步中，一个具有两个实验样本的簇（该簇在数组中的下标为5）诞生了。5.4层次聚类第五章聚类Python实现簇间最大距离的凝聚层次聚类算法#将关系矩阵转换成一个DataFrame对象clusters=pd.DataFrame(row_clusters,columns=["label1","label2","distance","samplesize"],index=["cluster%d"%(i+1)foriinrange(row_clusters.shape[0])])print(clusters)输出结果如下：label1label2distancesamplesizecluster10.03.03.0470232.0cluster21.02.05.3352692.0cluster34.05.09.6405023.0cluster46.07.011.4908705.0结果的第一列表示合并过程中新生成的簇，第二列和第三列表示被合并的两个簇，第四列表示的是两个簇的欧氏距离，最后一列表示的是合并后的簇中的样本的数量。第五章

聚类5.1什么是聚类分析?5.2聚类方法分类5.3

k均值聚类of4334高级大数据人才培养丛书之一，大数据挖掘技术与应用5.4层次聚类5.5密度聚类5.5

密度聚类第五章聚类密度聚类原理基于密度的聚类方法以数据集在空间分布上的稠密程度为依据进行聚类，无需预先设定簇的数量，特别适合对于未知内容的数据集进行聚类。基于密度的聚类方法的代表算法为DBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise，具有噪声的基于密度的聚类）算法。基于密度聚类方法的基本思想是：只要一个区域中的点的密度大于某个阈值，就把它加到与之相近的聚类中去，对于簇中每个对象，在给定的半径的ε邻域中至少要包含最小数目（MinPts）个对象。5.5

密度聚类第五章聚类DBSCAN聚类算法所用到的基本术语对象的

邻域：给定对象半径为

内的区域称为该对象的

邻域。核心对象：如果给定对象

邻域内的样本点数大于等于MinPts，则称该对象为核心对象。如下图中，设定

=1、MinPts=5，q是一个核心对象。MinPts:数据对象的

邻域中至少包含的对象数目。直接密度可达：如果p在q的

邻域内，而q是一个核心对象，则称对象p从对象q出发是直接密度可达的。5.5

密度聚类第五章聚类密度可达如果存在一个对象链p1,…,pn,q=p1,p=pn，使得pi+1是从pi关于

和MinPts是直接密度可达的，则对象p是从对象q关于

和MinPts密度可达的 密度相连如果存在对象o∈D，使对象p和q都是从o关于

和MinPts密度可达的，那么对象p和q是关于

和MinPts密度相连的pqop=pnq=p1p25.5

密度聚类第五章聚类DBSCAN算法

5.5

密度聚类第五章聚类Python实现DBSCAN密度聚类sklearn.cluster库提供了DBSCAN模型来实现DBSCAN聚类，其语法格式如下。DBSCAN(eps=0.5,min_samples=5,metric='euclidean',algorithm='auto',leaf_size=30,p=None,n_jobs=1)参数说明如下：eps：ε参数，float型，可选，用于确定邻域大小。min_samples：int型，MinPts参数，用于判断核心对象。metric：string型，用于计算特征向量之间的距离，可以用默认的欧氏距离，还可以自己定义距离函数。algorithm:{'auto','ball_tree','kd_tree','brute'}，最近邻搜索算法参数，默认为auto，brute是蛮力实现，kd_tree是kd树实现，ball_tree是球树实现，auto则会在三种算法中做权衡，选择一个最好的算法。5.5

密度聚类第五章聚类Python实现DBSCAN密度聚类DBSCAN(eps=0.5,min_samples=5,metric='euclidean',algorithm='auto',leaf_size=30,p=None,n_jobs=1)参数说明如下：leaf_size：int型，默认为30，控制kd树或者球树中叶子中的最小样本个数。这个值越小，则生成的kd树或者球树就越大，层数越深，建树时间越长，反之，则生成的kd树或者球树会小，层数较浅，建树时间较短。p：最近邻距离度量参数。只用于闵可夫斯基距离和带权重闵可夫斯基距离中p值的选择，p=1为曼哈顿距离，p=2为欧式距离。n_jobs：整型，指定计算所用的进程数。若值为-1，则用所有的CPU进行运算。若值为1，则不进行并行运算，这样方便调试。5.5

密度聚类第五章聚