1、第08章 聚类p距离计算pk-Means聚类p密度聚类p层次聚类8.1 引言n 聚类就是将集合划分成由类（相）似的对象组成的多个类的过程。n 聚类分析是研究（样品或指标）分类问题的一种统计分析方法。n 聚类所要求划分的类是未知的，一般把它理解为无监督学习。而分类算法是有训练样本的，属于监督学习。8.1.1 聚类的概念8.1 引言8.1.2 典型应用n 聚类可以帮助市场分析人员从客户基本信息库中发现不同的客户群；n 在生物学上，聚类可以根据生物基因结构，推导出植物和动物的物种分类，从而获得对生物种群固有结构的认识；n 聚类还能从地球观测数据库中找到地形、地貌等地理特征相似的区域，提供生物物种或病
2、虫害预警信息；n 根据房屋的类型、价值和地理位置等信息对城市房屋进行聚类分组，为客户提供房屋资产评估服务。8.1 引言n 划分聚类：大部分方法是基于距离的聚类算法。例如：k-MEANS、k-MEDOIDS、CLARANS等。n 层次聚类：例如：BIRCH、CURE、CHAMELEON等。层次聚类可采用“自底向上”或“自顶向下”方案。在“自底向上”方案中，初始时每一个数据纪录都被视作一个单独的簇，接着再把那些相互邻近的簇合并成一个新的簇，直到所有的记录都在一个簇或者满足某个终止条件为止。n 密度聚类：该方法是基于（结点）密度的聚类算法，主要算法有：DBSCAN、OPTICS、DENCLUE等。只
3、要一个区域中的点的密度大过某个阀值，就把它加到与之相近的聚类中去。n 网格聚类：主要算法有：STING、CLIQUE、WAVE-CLUSTER。将数据空间按某种特征（属性）划分成网格，聚类处理以网格（单元）为基本单位。8.1.3 常见算法分类8.1 引言n 高维数据集中存在大量无关的属性，所有维中存在簇的可能性几乎为零；n 高维空间中数据较低维空间中数据分布稀疏，其中数据间距离几乎相等是普遍现象，而传统聚类方法是基于距离进行聚类的，因此在高维空间中无法基于距离来构建簇。n 高维聚类分析已成为聚类分析的一个重要研究方向，也是聚类技术的难点。数据收集变得越来越容易，导致数据库规模越来越大、复杂性越
4、来越高，如各种类型的贸易交易数据、Web文档、基因表达数据等，它们的维度（属性）通常可以达到成百上千维，甚至更高。8.1.4 聚类算法中存在的问题8.2 距离计算n 大多数聚类分析是以相似性计算为基础的，同一个聚类中的个体模式相似，不在同一聚类中的个体模式则相异。目前，相似性距离的计算都是基于向量的，也就是计算两个向量的距离，距离越近相似度越大。下面，我们介绍几种常见的距离计算方法。8.2.1 闵可夫斯基距离n 闵可夫斯基距离（Minkowski Distance）是一种常见的方法，用于衡量数值点之间距离。假设 ，是n 维空间的两个向量，那么，闵可夫斯基距离定义为：12,nxxxX12,ny
5、yyY1dist,nppkkkxyX Y8.2 距离计算n 闵可夫斯基距离计算举例如下：n 欧氏距离（Euclidean Distance）最初用于计算欧几里德空间中两个点的距离。假设 ，是n 维空间的两个向量，它们之间的欧几里德距离是：import numpy as npx=np.random.random(10)y=np.random.random(10)dist=np.linalg.norm(x-y,ord=4)#闵科夫斯基距离，此时p=48.2.2 欧氏距离12,nxxxX12,ny yyY21dist,nkkkxyX Yn n=2 欧几里德距离就是平面上两个点的距离。如果将欧氏距离看
6、作物品相似程度，那么距离越近就越相似，也就是说距离越小，相似度越大。8.2 距离计算n 欧氏距离计算举例如下：import numpy as npimport scipy.spatial.distance as dis X=np.vstack(x,y)#向量x，y在前面例子中已经赋值。下同dist=dis.pdist(X,metric=euclidean)#欧几里得距离8.2.3 曼哈顿距离121212dist,P Pxxyy8.2 距离计算8.2.4 切比雪夫距离dist=np.linalg.norm(x-y,ord=np.inf)#切比雪夫距离，此时p=n 切比雪夫距离计算Python语句
7、如下：dist=np.linalg.norm(x-y,ord=1)#曼哈顿距离，此时p=1n 曼哈顿距离计算Python语句如下：12,nxxxX12,ny yyY111dist,limmaxknkiiiiki nixyxy X Y8.2 距离计算n 皮尔逊相关系数（Pearson Correlation Coefficient）即相关分析中的相关系数r，一般用于计算两个定距变量间联系的紧密程度，它的取值在-1，+1之间。8.2.5 皮尔逊相关系数dist=1-dis.pdist(X,metric=correlation)#调用scipy计算相关系数n 当相关系数为0时，X和Y两变量无关系；当
8、X的值增大，Y也增大，正相关关系，相关系数在0.00与1.00之间；当X的值增大，Y减小，负相关关系，相关系数在-1.00与0.00之间。相关系数的绝对值越大，相关性越强，相关系数越接近于1和-1，相关度越强，相关系数越接近于0，相关度越弱。公式如下：n 皮尔逊相关系数计算Python语句如下：2222cov,()()()(,)()()()()xyx yE xyE x E yx y=E xE xE yE y r8.2 距离计算n 余弦相似度就是两个向量之间的夹角的余弦值。假设8.2.6 余弦相似度dist=1-dis.pdist(X,metric=cosine)#余弦系数n 余弦相似度计算Py
9、thon语句如下：12(,.,)nxxxX12(,)ny yyY是n 维空间的两个向量，它们之间的余弦相似度是：cos XYX Yn 余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。相比距离度量，余弦相似度更加注重两个向量在方向上的差异，而非距离或长度。n 夹角余弦取值范围为-1,1。夹角余弦越大表示两个向量的夹角越小，夹角余弦越小表示两向量的夹角越大。当两个向量的方向重合时夹角余弦取最大值1，当两个向量的方向完全相反夹角余弦取最小值-1。8.2 距离计算n Jaccard系数主要用于计算符号度量或布尔值度量的个体间的相似度，只关心个体间共同具有的特征是否一致这个问题。
10、假设集合 和，两个集合的杰卡德相似系数表示如下：8.2.7 杰卡德相似系数dist=dis.pdist(X,metric=jaccard)#杰卡德相似距离n 杰卡德相似距离计算Python语句如下：,JABA BAB8.3 k-Means聚类n k-Means算法是最经典的基于划分的聚类算法。所谓基于划分的方法是将样本集组成的矢量空间预先初始化，划分为多个区域，每个区域有一个区域中心，对于每个样本，可以建立一种样本到区域中心的映射。通过不断的迭代，不断的重新定位，从一个组移动到另一个组来进行划分。不同的映射方式产生不同的基于划分的聚类算法，k-means算法要求样本点与中心点的欧几里得距离最小
11、。8.3.1 算法思想(a)初始质心(b)簇分配并更新质心(c)最终更新结果8.3 k-Means聚类n k-Means算法计算过程如下：（1）导入数据：收集并准备数值型矩阵作为原始数据集；（2）创建初始质心：指定聚类数k，从原始数据集中随机选取k个对象作为初始质心；（3）分配：计算数据集中每个对象到所有质心的距离，并将数据点分配到距离最接近的质心，从而形成簇分配矩阵；（4）重新计算质心：计算簇中所有点的均值，并将均值作为新的质心。（5）反复执行（3）和（4），直至质心不再移动。8.3.2 辅助函数n 计算欧氏距离def distEclud(vecA,vecB):return np.linal
12、g.norm(vecA-vecB,ord=2)8.3 k-Means聚类n 数据导入：从文本文件中读入数据到矩阵def loadFile(path):dataList=fr=open(path,r,encoding=UTF-8)record=fr.read()fr.close recordList=record.splitlines()for line in recordList:if line.strip():dataList.append(list(map(float,line.split(t)recordmat=np.mat(dataList)return recordmat8.3 k-
13、Means聚类n 构建k个随机质心def randCents(dataSet,k):n=np.shape(dataSet)1 cents=np.mat(np.zeros(k,n)for j in range(n):minCol=min(dataSet:,j)maxCol=max(dataSet:,j)cents:,j=np.mat(minCol+float(maxCol-minCol)*np.random.rand(k,1)return cents8.3 k-Means聚类8.3.3 编程实现k-Means算法def kMeans(dataset,k):m=np.shape(dataset)0
14、 ClustDist=np.mat(np.zeros(m,2)cents=randCents(dataset,k)clusterChanged=True while clusterChanged:clusterChanged=False for i in range(m):DistList=distEclud(dataseti,:,centsjk,:)for jk in range(k)minDist=min(DistList)minIndex=DistList.index(minDist)if ClustDisti,0!=minIndex:clusterChanged=True ClustD
15、isti,:=minIndex,minDist for cent in range(k):ptsInClust=datasetnp.nonzero(ClustDist:,0.A=cent)0 centscent,:=np.mean(ptsInClust,axis=0)return cents,ClustDist8.3 k-Means聚类n 主函数如下（假定数据文件为testdata.txt）：Path_file=testdata.txtrecordMat=loadFile(path_file)k=4cents,distMat=kMeans(recordMat,k)for indx in ran
16、ge(len(distMat):if distMatindx,0=0:plt.scatter(recordMatindx,0,recordMatindx,1,c=red,marker=o)if distMatindx,0=1:plt.scatter(recordMatindx,0,recordMatindx,1,c=blue,marker=o)if distMatindx,0=2:plt.scatter(recordMatindx,0,recordMatindx,1,c=cyan,marker=o)if distMatindx,0=3:plt.scatter(recordMatindx,0,r
17、ecordMatindx,1,c=green,marker=o)x=centsi,0 for i in range(k)y=centsi,1 for i in range(k)plt.scatter(x,y,s=80,c=yellow,marker=o)plt.show()8.3 k-Means聚类n 经过三次迭代之后k-Means算法收敛，形成四个聚类中心。运行结果：8.3 k-Means聚类8.3.4 sklearn中的k-Means方法class sklearn.cluster.KMeans(n_clusters=8,init=k-means+,n_init=10,max_iter=30
18、0,tol=0.0001,precompute_distances=auto,verbose=0,random_state=None,copy_x=True,n_jobs=1,algorithm=auto)n scikit-learn模块提供了k-Means聚类方法，原型为：n 主要参数包括：n_clusters：整型，可选，默认参数值为8，聚类数量。init：k-means+，random或者ndarray之一，默认为k-means+。k-means+：以一种巧妙的方式选择k-均值聚类的初始集群中心，以加快收敛速度。random：从初始质心的数据中随机选取 k 观察(行)。ndarray：给
19、出形状(n_clusters,n_features)的初始中心。8.3 k-Means聚类n_init：整型，默认参数值为10。用不同的初始化质心运行算法的次数。由于k-Means是结果受初始值影响的局部最优的迭代算法，因此需要多跑几次以选择一个较好的聚类效果。max_iter：整型，默认参数值为300，最大的迭代次数。tol：浮点型，默认参数值为0.0001，最小容忍误差，当误差小于tol就会退出迭代。algorithm：可以是auto，full或者elkan之一，默认参数值为auto。full适合于EM类算法；elkan适合于三角形不等式，但暂不支持稀疏数据；而当设置为auto时，稠密数据
20、用elkan，稀疏数据用full。random_state：整型，RandonState实例或None，默认参数值为None。具体如下：int：该参数用于设置随机数发生器的种子；RandonState instance：该参数是一个随机数发生器；None：使用np.random作为随机数发生器。8.3 k-Means聚类n 示例程序8.3 k-Means聚类n 运行结果8.3 k-Means聚类8.3.5 算法评价首先，在样本分配聚类阶段，需要计算kn次欧氏距离，其中k是指聚类个数，n是样本个数，时间复杂度为O（kn）；其次，在更新聚类中心阶段，时间复杂度为O（n）。如果迭代次数为t，则算法的
21、计算复杂度为O(knt)。因此k-means针对样本个数n具有线性的计算复杂度，是一种非常有效的大数据聚类算法。n k-means算法时间复杂度n k-means算法缺点分析：聚类个数k依赖于用户参数的指定；基于距离的聚类算法只能发现球状簇，很难发现其他形状的簇；初始中心随机选取，导致结果波动较大，稳定性较差。简单有效的改进方式是k-means+算法，该算法能够有效产生初始的聚类中心。8.3 k-Means聚类8.3.6 算法改进k-Means+22XDPDxxxx8.4 密度聚类8.4.1 算法思想n 基于密度的聚类算法，此类算法能够发现任意形状的聚类，也可以用于寻找数据中的噪声；n 密度聚
22、类可以通过样本分布的紧密程度决定；n 算法的目的就是过滤低密度区域的样本点即噪声数据，发现高密度区域的样本点；n 密度聚类算法已经成功应用于城市规划、城市建设、选址等多个研究领域。n 根据密度的不同定义，有DBSCAN、密度峰值聚类、OPTICS等。8.4.2 DBSCAN算法n DBSCAN是典型的密度聚类算法，它利用两个参数和m描述样本点的紧密程度。对于任一样本点，在其半径的区域范围内所包含的样本点数量（包括其自身）就是该点的密度。8.4 密度聚类核心点：以该点为圆心，半径为区域内（即该点的邻域）至少包括m个样本点。边界点：该点的邻域内包括的样本点个数少于m，但是在某核心点的邻域内。噪音点
23、：既不是核心点，也不是边界点的点n DBSCAN算法发现聚类的过程将所有点标记标记为核心点、边界点以及噪音点，比如：红色为核心点，黄色为边界点，蓝色为噪声点；将任意两个距离小于的核心点融合融合为同一个聚类；将任意核心点的邻域内的边界点也放到与之相同的聚类中；从这个过程来看，DBSCAN算法的本质是寻找聚类并不断扩展聚类的过程。8.4 密度聚类DBSCAN算法流程8.4 密度聚类DBSCAN算法流程8.4 密度聚类n 算法实现8.4 密度聚类n 算法实现（续上）n 聚类效果8.4 密度聚类8.4.3 密度峰值聚类n 所有紧密相连的样本点被低密度区域分割，而且这些低密度区域的点距离其它高密度区域都
24、比较远，算法的目的就是过滤低密度区域的样本点（即噪声数据），发现高密度区域的样本点。()ijcijddn 局部密度，其中，10()=ijcijcijcdddddd这里 是指样本点i和样本点j之间的距离，叫做截断距离(由用户事先指定)。用于统计以 样本点i为中心，为半径的样本点个数。ijdcdicd8.4 密度聚类8.4 密度聚类8.5 层次聚类n 层次聚类又叫系统聚类，是对给定的数据集进行层次似的分解，直到某种条件满足为止。自底向上或自顶向下聚类分割均可。n 基本思想是：先将各个样本归为一类，然后计算各类之间的相似度。寻找最为相似的两类并合并成一类，生成聚类树，如下图所示。重新计算新类与各旧类
25、之间的相似度。经过不断的计算合并，直到所有样本合为一类为止。8.5.1 层次聚类思想8.5 层次聚类n 类别之间的相似度计算假设有两个聚类u和v，u中包括 个样本点 ，v中包括 个样本点 。聚类u是由类s和类t合并而成，v是样本空间中u以外的任何一个聚类。以下是计算新类u和旧类v之间距离d(u,v)的几种方法：最小距离法：认为最近两点的距离越小，其所属的两个类间的相似度就越大。缺点在于：会使得两个距离较远的分类合并到一起，仅仅因为其中个别点距离较近，而形成松散的聚类。最大距离法：用两类之间最远两点的距离表示，又叫完全连接法。平均距离法：两类之间的距离用它们之间所有点的平均距离表示。离差平方和法
26、：同类样本的离差平方和应当较小，不同类间的离差平方和较大。距离公式计算如下，其中u011,uu uu011,vv vvv222(,),vsvtvd u vd v sd v td s tTTTvTst8.5 层次聚类n scikit-learn提供了层级聚类算法的模型AgglomerativeClustering，其函数原型为：8.5.2 层次聚类实现class sklearn.cluster.AgglomerativeClustering(n_clusters=2,affinity=euclidean,emory=None,connectivity=None,compute_full_tree
27、=auto,linkage=ward,ooling_func=)n 主要参数包括：n_clusters：整型，默认参数值为2，指定待聚类数量。affinity：字符串或可调用函数，默认参数为euclidean，用于计算连接距离的方法。memory：None，字符串或joblib对象，设置缓存聚类树计算结果的目录路径，默认为不缓存。8.5 层次聚类connectivity：array-like或可调用函数，用于指定连接矩阵，也可以是来自于如kneighbors_graph方法计算返回的矩阵结果。compute_full_tree：布尔型或auto，在构造第n_clusters个树时终止。link
28、age：可以是ward，complete或 average，默认参数值为ward，用于指定连接算法标准。n 主要属性如下：labels：array n_samples，每个样本点的簇标记；n_leaves_：整型，层次树的叶子结点数量；n_components：整型，连接图中连通分量的估计值；children：array-like，其大小为(n_nodes-1,2)，每个非叶子结点的孩子结点。n 实现示例：（转下一页）8.5 层次聚类n 聚类效果如下：8.6 综合实例n 示例代码：8.6.1 聚类算法性能比较8.6 综合实例n 示例代码：（续上）8.6 综合实例n 示例代码：（续上）8.6 综
29、合实例n 聚类效果：8.6 综合实例n k-Means聚类算法简单有效它发现的聚类个数k依赖于用户参数的指定对初始中心的选取非常敏感，稳定性较差基于距离的k-Means聚类算法只能发现球状簇，很难发现其他形状的簇。n DBSCAN算法能够发现任意形状的聚类，也能有效处理异常数据，经常使用于对空间数据的聚类。缺点在于：首先它对参数邻域半径及半径内最少点数量非常敏感，不同的取值将产生不同的聚类结果。其次，它直接对整个数据集进行聚类操作。当数据量非常大时，必须有大内存量支持，I/O消耗也很大，聚类过程的大部分时间用在区域查询操作上。8.6.2 算法总结8.6 综合实例n 层次聚类层次聚类中的距离和规则容易定义，限制少。虽然不需要确定分类数，但是一旦一个分裂或者合并被执行，操作不能撤销、结果不能修正，会带来低质量的聚类结果。该算法时间复杂度大，并不适合大数据集的使用。n 算法比较算法名称算法名称聚类参数聚类参数使用场景使用场景cluster形状形状k-Means簇的个数平面几何；样本空间较大；簇的数量不太多；中等大小的簇；簇大小均匀球状或凸型DBSCAN邻域的大小非平面几何；样本空间较大；中等大小的簇；簇大小不均匀。任意形状层次聚类层次聚类簇的个数；连接类型；距离计算方法样本空间较大；簇的数量多；非欧几里得距离；球状或凸型
