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

1、系统聚类法的基本思想系统聚类法的基本思想 先将n个样品各自看成一类，然后规定样品之间的“距离”和类与类之间的距离。选择距离最近距离最近的两类合并成一个新类，计算新类和其它类（各当前类）的距离，再将距离最近的两类合并。这样，每次合并减少一类，直至直至所有的样品都归成一类为止所有的样品都归成一类为止。 （1）确定数据点之间的距离计算方法（2）确定数据分类后类与类之间距离的计算方法PdistY = pdist（X） 计算样品对的欧式距离。输入参数X是n p的矩阵，矩阵的每一行对应一个样品，每一列对应一个变量。输出参数Y是包含n(n-1)/2个元素的行向量，用(i,j)表示第i个样品和第j个样品构成的

2、样品对，则Y中的元素依次是(2, 1), (3, 1), , (n, 1), (3, 2), , (n, 2), , (n, n-1)Y = pdist（X, metric）输入参数metric指定计算距离的方法，metric为字符串，可用的字符串如下表所示。MetricMetric参数值参数值说明说明euclidean欧式距离seuclidean标准化欧式距离mahalanobis马哈拉诺比斯距离cityblock绝对值距离minkowski闵可夫斯基距离chebychev切比雪夫距离Y = pdist（X, minkowski, p）计算样品对的闵可夫斯基距离，输入参数p为闵可夫斯基距离计

3、算中的指数，默认情况下，指数为2SquareformZ = 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是原始数

4、据中观测样品的个数。Z矩阵每一行对应一次并类，第i行上前两个元素为第i次并类的两个类的类编号，初始类编号为1n，以后每形成一个新类，类编号从n+1开始逐次增加1.Z矩阵的第i行中的第3个元素为第i次并类时的并类距离Z = linkage（y, method）利用method参数制定的方法创建系统聚类树，method是字符串，可用的字符串如下所示MethodMethod参数值参数值说明说明average类平均法centroid重心法complete最长距离法median中间距离法single最短距离法ward离差平方和法weighted可变类平均法Z = linkage（y, method, m

5、etric）metric用来指定计算点与点之间距离的方法MetricMetric参数值参数值说明说明euclidean欧式距离seuclidean标准化欧式距离mahalanobis马哈拉诺比斯距离cityblock绝对值距离minkowski闵可夫斯基距离chebychev切比雪夫距离Dendrogram函数H = dendrogram（Z）由系统聚类树矩阵Z生成系统聚类树形图。输入参数Z是由linkage函数输出的系统聚类树矩阵。输出参数H是树形图中线条的句柄值向量，用来控制线条属性。H = dendrogram（Z， p）生成一个树形图，通过输入参数p来控制显示的叶节点数。H = den

6、drogram（, orientation, orient）通过设定orientation参数及参数值orient来控制聚类树形图的方向和放置叶节点标签的位置，可用参数如下所示参数值参数值说明说明top从上至下，叶节点标签在下方，为默认情况bottom从下至上，叶节点标签在上方left从左至右，叶节点标签在右边right从右至左，叶节点标签在左边H = dendrogram（, labels, S）通过一个字符串数组或字符串元胞数组设定每一个观测值的标签。当树形图中显示了全部的叶节点时，叶节点的标签记为相应观测的标签；当树形图中忽略了某些节点时，只包含单个观测的叶节点的标签记为相应观测的标签。

7、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

8、= （d1, d2, , d n(n-1)/2 ）,d中元素依次是样本对（2，1），（3,1），（n, 1），（3,2），（n，2）, ，（n，n-1)中初次并类时的并类距离，称为cophenetic距离cophenetic相关系数 是指y与d之间的线性相关系数()()()()()()()1 211 21 22211n nkkkn nn nkkkkyyddcyydd-=-=-=轾轾犏犏-犏犏犏犏臌臌邋()()1 2121n nkkyyn n-=-()()1 2121n nkkddn n-=-c = cophenet（Z, Y）在上述调用中，cophenet函数用pdist函数输出的Y和link

9、age函数输出的Z计算系统聚类树的cophenetic相关系数。输出参数c为Cophenetic相关系数inconsistent函数用来计算系统聚类树矩阵Z中每次并类得到的链接的不一致系数，其调用格式如下Y = inconsistent（Z）Y = inconsistent（Z，d）参数Y是一个(n-1)*4的矩阵，各列的含义如下列序号列序号说明说明1计算设计的所有链接长度（即并类距离）的均值2计算涉及的所有链接长度的标准差3计算涉及的链接个数4不一致系数不一致系数可用来确定最终的分类个数。在并类过程中，若某一次并类对应的不一致系数较上一次有大幅增加，说明该次并类效果不好，而它上一次的并类效果

10、使比较好的，不一致系数增加的幅度越大，说明上一次并类效果越好。在使得类的个数尽量少的前提下，可参照不一致系数的变化，确定最终的分类数。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，

11、 param1， val1， param2， val2， ）参数名参数名参数值参数值含义含义distancePdist函数所支持的metric参数的取值指定距离的计算方法linkageLinkage函数所支持的method参数的取值指定系统聚类方法cutoff正实数指定不一致系数或距离的阈值maxclust正整数指定最大类数 系统聚类法是一种比较成功的聚类方法。然而当样本点数量十分庞大时，则是一件非常繁重的工作，且聚类的计算速度也比较慢。比如在抽样调查中，有4万人就其出行方式偏好作了回答，希望能迅速将他们分为几类。这时，采用系统聚类法就很困难，而动态聚类法就会显得方便，适用。 动态聚类使用于大

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

13、如我们要把图中的点分成两类。快速聚类的步骤： 1、随机选取两个点 和 作为凝聚点。 2、对于任何点 ，分别计算 3、若 ，则将 划为第一类，否则划给第二类。于是得图（b）的两个类。 )1 (1x)1 (2xkx),(),()1(2)1(1xxdxxdkk和),(),()1(2)1(1xxdxxdkkkx4、分别计算两个类的重心，则得 和 ，以其为新的凝聚点，对空间中的点进行重新分类，得到新分类。)2(1x)2(2x (b) 任取两个凝聚点 (c) 第一次分类 (d) 求各类中心 （a）空间的群点 (e) 第二次分类优点：计算量小，方法简便，可以根据经验，先作主观分类。缺点：结果受选择凝聚点好坏

14、的影响，分类结果不稳定。 凝聚点就是一批有代表性的点，是欲形成类的中心。凝聚点的 选择直接决定初始分类，对分类结果也有很大的影响，由于凝聚点 的不同选择，其最终分类结果也将出现不同。故选择时要慎重通 常选择凝聚点的方法有： (1) 人为选择人为选择，当人们对所欲分类的问题有一定了解时，根据经验，预先确定分类个数和初始分类，并从每一类中选择一个有代表性的样品作为凝聚点。 (2) 重心法重心法 将数据人为地分为A类，计算每一类的重心，将重心作为凝聚点。 (3) 密度法密度法以某个正数d为半径，以每个样品为球心，落在这个球内的样品数(不包括作为球心的样品)称为这个样品的密度。计算所有样品点的密度后，

15、首先选择密度最大的样品为第一凝聚点。然后选出密度次大的样品点，若它与第一个凝 聚点的距离大于2d ，则将其作为第二个凝聚点；否则舍去这点。这样，按密度由大到小依次考查，直至全部样品考查完毕为止此方法中，d要给得合适，太大了使凝聚点个数太 少，太小了使凝聚点个数太多。 (4) 人为地选择一正数d，首先以所有样品的均值作为第一凝聚点。然后依次考察每个样品，若某样品与已选定的凝聚点的距 离均大于d，该样品作为新的凝聚点，否则考察下一个样本。第一，选择凝聚点第一，选择凝聚点；第二，初始分类；第二，初始分类；对于取定的凝聚点，视每个凝聚点为一类，将每个样品根据定义的距离向最近的凝聚点归类。第三，修改分类

16、第三，修改分类得到初始分类，计算各类的重心，以这些重心作为新的凝聚点，重新进行分类，重复步骤2，3，直到分类的结果与上一步的分类结果相同，表明分类已经合理为止。动态聚类法的基本步骤：动态聚类法的基本步骤：例：某汽车4s店5位店员的月销售量和受教育程度如下表：售货员12345销售量（辆）11688教育程度12320对这5位店员分类。29505026495351341.选择凝聚点选择凝聚点 1 5325d为最大。可选择2和5作为凝聚点。计算各样品点两两之间的距离，得到如下的距离矩阵502613494对于取定的凝聚点，视每个凝聚点为一类，将每个样品根据定义的距离，向最近的凝聚点归类。1 G1 G2

17、1 3 4得到初始分类为：1G 2 , 1：2G5 , 4 , 3：2.2.初始分类初始分类25. 052.4025. 018.4025.2754. 315.4956. 025.5124. 3计算G1和G2的重心：G1的重心（1,1.5），G2的重心（7.33,1.67） G1 G212345得到分类结果：1G 2 , 1：2G5 , 4 , 3：3.3.修改分类修改分类以这两个重心点作为凝聚点，再按最小距离原则重新聚类修改前后所分的类相同，故可停止修改。 2 , 15 , 4 , 3和。 5个售货员可分为两类Kemans函数IDX = kmeans(X, k)将n个点分为k类。输入参数X为n

18、*p矩阵，矩阵的每一行对应一个点，每一列对应一个变量。输出参数IDX是一个n*1的向量，其元素为每个点所属类的类序号。IDX， C = kmeans(X, k)返回k个类的类重心坐标矩阵C，C是一个k*p的矩阵，第i行的元素为第i类的类重心坐标。IDX, C, sumd = kmeans(X, k)返回类内距离和（即类内个点与类重心之间的距离之和）向量sumd，sumd是一个1*k的向量，第i个元素为第i类的类内距离之和。Silhouette函数Silhouette函数用来根据cluster, clusterdata或者kmeans函数的聚类结果绘制轮廓图，从轮廓图上可以看出每个点的分类是否合

19、理。轮廓图上第i个点的轮廓值是()( )( )min,1,2,.,max,minbaS iinab-=轾臌a是第i个点与同类的其他点之间的平均距离，b为一个向量，其元素是第i个点与不同类的类内各点之间的平均距离，如b的第k个元素就是第i个点与第k类各点之间的平均距离。轮廓值S(i)的取值范围为-1, 1，S(i)取值越大，说明第i个点的分类越合理，当S(i)1和初始隶属度矩阵U（0）=（uik（0）。（2）通过下式计算第l步的聚类中心V（l）()()()()()1111,1,2,.,nmlikklkinmlikkuxvicu-=-=（3）修正隶属度矩阵U（l），计算目标函数J（l）()()2111,1,2,., ;1,2,.,clllmikikjkjuddic kn-=()()()()()( )()( )211,ncmlllllikikkiJUVud=邋()()llikkidxv=-（4）对给定的隶属度终止容限0ue或者达到最大迭代步长，停止迭代，否则l=l+1，转至（2）经过以上步骤的迭代后，可以求得最终的隶属度矩阵U和聚类中心V，使得目标函数J（U， V）的值达到最小。根据最终的隶属度矩阵U中元素的取值可以确定所有样品的归属，当 1maxjkiki cuu=将样品xk归为第j类fcmcenter, U, obj_fcn =