交通数据处理-第三章-聚类分析2

聚类分析2系统聚类法的基本思想

先将n个样品各自看成一类，然后规定样品之间的“距离”和类与类之间的距离。选择距离最近的两类合并成一个新类，计算新类和其它类（各当前类）的距离，再将距离最近的两类合并。这样，每次合并减少一类，直至所有的样品都归成一类为止。系统聚类法回顾（1）确定数据点之间的距离计算方法（2）确定数据分类后类与类之间距离的计算方法系统聚类法回顾PdistY=pdist（X）计算样品对的欧式距离。输入参数X是nхp的矩阵，矩阵的每一行对应一个样品，每一列对应一个变量。输出参数Y是包含n(n-1)/2个元素的行向量，用(i,j)表示第i个样品和第j个样品构成的样品对，则Y中的元素依次是(2,1),(3,1),…,(n,1),(3,2),…,(n,2),…,(n,n-1)系统聚类法的相关函数Y=pdist（X,metric）输入参数metric指定计算距离的方法，metric为字符串，可用的字符串如下表所示。系统聚类法的相关函数Metric参数值说明‘euclidean’欧式距离‘seuclidean’标准化欧式距离‘mahalanobis’马哈拉诺比斯距离‘cityblock’绝对值距离‘minkowski’闵可夫斯基距离‘chebychev’切比雪夫距离Y=pdist（X,‘minkowski’,p）计算样品对的闵可夫斯基距离，输入参数p为闵可夫斯基距离计算中的指数，默认情况下，指数为2系统聚类法的相关函数SquareformZ=squareform(y)Z=squareform(y,‘tomatrix’)y=squareform(Z)y=squareform(Z,‘tovector’)前两种调用时把pdist函数输出的距离向量y转为距离矩阵Z，而后两种调用则是把距离矩阵Z转换为pdist函数输出的距离向量y。系统聚类法的相关函数Linkage函数Z=linkage（y）利用最短距离法创建一个系统聚类树。输入参数y是样品对距离向量，是包含n(n-1)/2个元素的行向量，通常是pdist函数的输出。输出Z是一个系统聚类树矩阵，它是(n-1)*3的矩阵，这里的n是原始数据中观测样品的个数。Z矩阵每一行对应一次并类，第i行上前两个元素为第i次并类的两个类的类编号，初始类编号为1~n，以后每形成一个新类，类编号从n+1开始逐次增加1.Z矩阵的第i行中的第3个元素为第i次并类时的并类距离系统聚类法的相关函数Z=linkage（y,method）利用method参数制定的方法创建系统聚类树，method是字符串，可用的字符串如下所示系统聚类法的相关函数Method参数值说明‘average’类平均法‘centroid’重心法‘complete’最长距离法‘median’中间距离法‘single’最短距离法‘ward’离差平方和法‘weighted’可变类平均法Z=linkage（y,method,metric）metric用来指定计算点与点之间距离的方法系统聚类法的相关函数Metric参数值说明‘euclidean’欧式距离‘seuclidean’标准化欧式距离‘mahalanobis’马哈拉诺比斯距离‘cityblock’绝对值距离‘minkowski’闵可夫斯基距离‘chebychev’切比雪夫距离Dendrogram函数H=dendrogram（Z）由系统聚类树矩阵Z生成系统聚类树形图。输入参数Z是由linkage函数输出的系统聚类树矩阵。输出参数H是树形图中线条的句柄值向量，用来控制线条属性。系统聚类法的相关函数H=dendrogram（Z，p）生成一个树形图，通过输入参数p来控制显示的叶节点数。系统聚类法的相关函数H=dendrogram（…,‘orientation’,‘orient’）通过设定’orientation’参数及参数值’orient’来控制聚类树形图的方向和放置叶节点标签的位置，可用参数如下所示参数值说明‘top’从上至下，叶节点标签在下方，为默认情况‘bottom’从下至上，叶节点标签在上方‘left’从左至右，叶节点标签在右边‘right’从右至左，叶节点标签在左边H=dendrogram（…,‘labels’,S）通过一个字符串数组或字符串元胞数组设定每一个观测值的标签。当树形图中显示了全部的叶节点时，叶节点的标签记为相应观测的标签；当树形图中忽略了某些节点时，只包含单个观测的叶节点的标签记为相应观测的标签。系统聚类法的相关函数Cophenet函数Cophenet函数用来计算系统聚类树的cophenetic相关系数Cophenetic相关系数反映了聚类效果的好坏，cophenetic相关系数越接近于1，说明聚类效果越好，可通过Cophenetic相关系数对比各种不同的距离计算方法和不同的系统聚类法的聚类效果系统聚类法的相关函数cophenetic相关系数对给定的样本观测矩阵X，用y=（y1,y2,…,yn(n-1)/2）表示由pdist函数输出的样本的距离向量，用（i，j）表示由第i个样本和第j个样本构成的样本对，则y中的元素依次是样本对（2，1），（3,1），…，（n,1），（3,2），…，（n，2）,…，（n，n-1)的距离设d=（d1,d2,…,dn(n-1)/2）,d中元素依次是样本对（2，1），（3,1），…，（n,1），（3,2），…，（n，2）,…，（n，n-1)中初次并类时的并类距离，称为cophenetic距离系统聚类法的相关函数cophenetic相关系数是指y与d之间的线性相关系数c=cophenet（Z,Y）在上述调用中，cophenet函数用pdist函数输出的Y和linkage函数输出的Z计算系统聚类树的cophenetic相关系数。输出参数c为Cophenetic相关系数系统聚类法的相关函数inconsistent函数用来计算系统聚类树矩阵Z中每次并类得到的链接的不一致系数，其调用格式如下Y=inconsistent（Z）Y=inconsistent（Z，d）参数Y是一个(n-1)*4的矩阵，各列的含义如下系统聚类法的相关函数列序号说明1计算设计的所有链接长度（即并类距离）的均值2计算涉及的所有链接长度的标准差3计算涉及的链接个数4不一致系数不一致系数可用来确定最终的分类个数。在并类过程中，若某一次并类对应的不一致系数较上一次有大幅增加，说明该次并类效果不好，而它上一次的并类效果使比较好的，不一致系数增加的幅度越大，说明上一次并类效果越好。在使得类的个数尽量少的前提下，可参照不一致系数的变化，确定最终的分类数。系统聚类法的相关函数Clusterdata函数调用了pdist、linkage和cluster函数，用来由原始眼根数据矩阵X创建系统聚类，T=clusterdata（X，cutoff）T=clusterdata（X，param1，val1，param2，val2，…）输出参数T包含n个元素的列向量，其元素为相应观测所属类的类序号。Curfoo为阈值。Clusterdata函数T=clusterdata（X，cutoff）T=clusterdata（X，param1，val1，param2，val2，…）系统聚类法的相关函数参数名参数值含义‘distance’Pdist函数所支持的metric参数的取值指定距离的计算方法‘linkage’Linkage函数所支持的method参数的取值指定系统聚类方法‘cutoff’正实数指定不一致系数或距离的阈值‘maxclust’正整数指定最大类数动态聚类法（快速聚类法/k均值聚类法）

系统聚类法是一种比较成功的聚类方法。然而当样本点数量十分庞大时，则是一件非常繁重的工作，且聚类的计算速度也比较慢。比如在抽样调查中，有4万人就其出行方式偏好作了回答，希望能迅速将他们分为几类。这时，采用系统聚类法就很困难，而动态聚类法就会显得方便，适用。动态聚类使用于大型数据。动态聚类法

基本思想：选取若干个样品作为凝聚点，计算每个样品和凝聚点的距离，进行初始分类，然后根据初始分类计算其重心，再进行第二次分类，一直到所有样品不再调整为止。K均值聚类法又称为快速聚类法，其基本步骤为1.选择K个样品作为初始凝聚点（聚类种子），或者将所有样品分为k个初始类，然后将k个类的重心（均值）作为初始凝聚点。2.对除初始凝聚点之外的所有样品逐个归类，将每个样品归入离他最近的凝聚点所在的类，该类的凝聚点更新为这一类目前的均值，直至所有样品都归类。重复步骤2，直至所有样品不能再分配位置K均值聚类法选择凝聚点分类修改分类分类是否合理分类结束YesNo

用一个简单的例子来说明动态聚类法的工作过程。例如我们要把图中的点分成两类。快速聚类的步骤：

1、随机选取两个点和作为凝聚点。

2、对于任何点，分别计算

3、若，则将划为第一类，否则划给第二类。于是得图（b）的两个类。4、分别计算两个类的重心，则得和，以其为新的凝聚点，对空间中的点进行重新分类，得到新分类。

(b)任取两个凝聚点(c)第一次分类(d)求各类中心

（a）空间的群点(e)第二次分类动态聚类法

优点：计算量小，方法简便，可以根据经验，先作主观分类。缺点：结果受选择凝聚点好坏的影响，分类结果不稳定。选择凝聚点和确定初始分类

凝聚点就是一批有代表性的点，是欲形成类的中心。凝聚点的选择直接决定初始分类，对分类结果也有很大的影响，由于凝聚点的不同选择，其最终分类结果也将出现不同。故选择时要慎重．通常选择凝聚点的方法有：

(1)人为选择，当人们对所欲分类的问题有一定了解时，根据经验，预先确定分类个数和初始分类，并从每一类中选择一个有代表性的样品作为凝聚点。

(2)重心法将数据人为地分为A类，计算每一类的重心，将重心作为凝聚点。(3)密度法以某个正数d为半径，以每个样品为球心，落在这个球内的样品数(不包括作为球心的样品)称为这个样品的密度。计算所有样品点的密度后，首先选择密度最大的样品为第一凝聚点。然后选出密度次大的样品点，若它与第一个凝聚点的距离大于2d，则将其作为第二个凝聚点；否则舍去这点。这样，按密度由大到小依次考查，直至全部样品考查完毕为止．此方法中，d要给得合适，太大了使凝聚点个数太少，太小了使凝聚点个数太多。

(4)人为地选择一正数d，首先以所有样品的均值作为第一凝聚点。然后依次考察每个样品，若某样品与已选定的凝聚点的距离均大于d，该样品作为新的凝聚点，否则考察下一个样本。第一，选择凝聚点；第二，初始分类；对于取定的凝聚点，视每个凝聚点为一类，将每个样品根据定义的距离向最近的凝聚点归类。第三，修改分类得到初始分类，计算各类的重心，以这些重心作为新的凝聚点，重新进行分类，重复步骤2，3，直到分类的结果与上一步的分类结果相同，表明分类已经合理为止。动态聚类法的基本步骤：例：某汽车4s店5位店员的月销售量和受教育程度如下表：售货员12345销售量（辆）11688教育程度12320对这5位店员分类。选择凝聚点1②③④⑤①②③④为最大。可选择2和5作为凝聚点。计算各样品点两两之间的距离，得到如下的距离矩阵对于取定的凝聚点，视每个凝聚点为一类，将每个样品根据定义的距离，向最近的凝聚点归类。1②G1⑤G2134得到初始分类为：：：2.初始分类计算G1和G2的重心：G1的重心（1,1.5），G2的重心（7.33,1.67）G1G212345得到分类结果：：：3.修改分类以这两个重心点作为凝聚点，再按最小距离原则重新聚类修改前后所分的类相同，故可停止修改。和。

5个售货员可分为两类Kemans函数IDX=kmeans(X,k)将n个点分为k类。输入参数X为n*p矩阵，矩阵的每一行对应一个点，每一列对应一个变量。输出参数IDX是一个n*1的向量，其元素为每个点所属类的类序号。K均值聚类法的相关函数[IDX，C]=kmeans(X,k)返回k个类的类重心坐标矩阵C，C是一个k*p的矩阵，第i行的元素为第i类的类重心坐标。[IDX,C,sumd]=kmeans(X,k)返回类内距离和（即类内个点与类重心之间的距离之和）向量sumd，sumd是一个1*k的向量，第i个元素为第i类的类内距离之和。K均值聚类法的相关函数Silhouette函数Silhouette函数用来根据cluster,clusterdata或者kmeans函数的聚类结果绘制轮廓图，从轮廓图上可以看出每个点的分类是否合理。轮廓图上第i个点的轮廓值是K均值聚类法的相关函数a是第i个点与同类的其他点之间的平均距离，b为一个向量，其元素是第i个点与不同类的类内各点之间的平均距离，如b的第k个元素就是第i个点与第k类各点之间的平均距离。轮廓值S(i)的取值范围为[-1,1]，S(i)取值越大，说明第i个点的分类越合理，当S(i)<0时，说明第i个点的分类不合理，还有比目前分类更合理的方案。K均值聚类法的相关函数Silhouette的调用格式Silhouette（X,clust）根据样本观测值矩阵X和聚类结果clust绘制轮廓图。输入参数X是一个n*p的矩阵，矩阵的每一行对应一个观测，每一列对应一个变量。Clust是聚类结果，可以是由每个观测值所属的类序号构成的数值向量，也可以是由类名称构成的字符矩阵或字符串元胞数组。默认情况下，Silhouette函数会采用平方欧式距离K均值聚类法的相关函数s=Silhouette（X,clust）返回轮廓值向量s，它是一个n*1的向量，其元素为相应点的轮廓值。此时不绘制轮廓图。[s,h]=Silhouette（X,clust）绘制轮廓图，并返回轮廓值向量s和图形句柄h。x=[1,2,6,8,11]';在很多分类过程中，分类对象之间没有明确的界限，往往具有亦此亦彼的情况。例如好与坏之间没有明确的界限，我认为某个人是好人，别人未必这么认为；高与矮之间也没有明确的界限，多高的人才算是高，可能每个人都有每个人的判断。诸如此类的问题，如果用传统的聚类方法进行分类，把每个待分类的对象严格地划分到某个类中，这也存在一定的不合理性。借助L.A.Zadeh提出的模糊集理论，人们开始应用模糊的方法来处理聚类，并称之为模糊聚类分析。模糊C均值聚类法模糊聚类分析作为无监督机器学习的主要技术之一，是用模糊理论对重要数据分析和建模的方法，建立了样本类属的不确定性描述，能比较客观地反映现实世界，它已经有效地应用在大规模数据分析、数据挖掘、矢量量化、图像分割、模式识别等领域，具有重要的理论与实际应用价值，随着应用的深入发展，模糊聚类算法的研究不断丰富。在众多模糊聚类算法中，模糊C-均值（FCM）算法应用最广泛且较成功，它通过优化目标函数得到每个样本点对所有类中心的隶属度，从而决定样本点的类属以达到自动对数据样本进行分类的目的。把n个向量xi（i=1,2,…,n）分为c个模糊组，并求每组的聚类中心，使得非相似性指标的价值函数达到最小。用模糊划分，使得每个给定数据点用值在0，1间的隶属度来确定其属于各个组的程度。与引入模糊划分相适应，隶属矩阵U允许有取值在0，1间的元素。不过，加上归一化规定，一个数据集的隶属度的和总等于1给定观测数据矩阵X的每一行为一个样品（或观测），每一列为一个变量的n个观测值。模糊聚类将n个样品划分为c个类（2≤c≤n）.记V={v1；v2；…；vc}为c个类的聚类中心，其中vi=（vi1,vi2,…,vip）记U=(uik)c*n为隶属度矩阵，其中元素uik表示第k个样本属于第i类的隶属度定义目标函数U=(uik)c*n为隶属度矩阵显然，J（U,V）表示了各类中样品到聚类中心的加权平方距离之和，权重是样品xk属于第i类的隶属度的m次方，模糊C均值聚类法德聚类准则是求U，V，使得J（U,V）取最小值。（1）确定类的个数c，幂指数m>1和初始隶属度矩阵U（0）=（uik（0））。（2）通过下式计算第l步的聚类中心V（l）（3）修正隶属度矩阵U（l），计算目标函数J（l）（4）对给定的隶属度终止容限或者达到最大迭代步长，停止迭代，否则l=l+1，转至（2）