层次聚类ppt课件

层次聚类,1,目 录,层次聚类方法简介 簇间距离度量方法 层次聚类方法存在的不足 层次聚类的MATLAB实现 仿真结果 结论,2,一.层次聚类方法简介,层次聚类就是通过对数据集按照某种方法进行层次分解，直到满足某种条件为止。按照分类原理的不同，可以分为凝聚和分裂两种方法。层次凝聚的代表是AGNES算法，层次分裂的代表是DIANA算法。一个完全层次聚类的质量由于无法对已经做的合并或分解进行调整而受到影响。但是层次聚类算法没有使用准则函数，它所含的对数据结构的假设更少，所以它的通用性更强。 下面介绍这两种方法。,3,一.层次聚类方法简介,1. 凝聚的层次聚类 凝聚的层次聚类是一种自底向上的策略。它从每个对象形成自己的簇开始，并且迭代的把簇合并成越来越大的簇，直到所有的对象都在一个簇中，或者满足某个终止条件。该单个簇成为层次结构的根。在合并步骤，它找出两个最接近的簇，并且合并它们，形成一个簇。因为每次迭代合并两个簇，其中每个簇至少包含一个对象，因此凝聚方法最多需要n次迭代。 凝聚的层次聚类算法过程如图所示：,4,一.层次聚类方法简介,2. 分裂的层次聚类 分裂的层次聚类与凝聚的层次聚类相反，采用自顶向下的策略。它从把所有对象置于一个簇中开始，该簇是层次结构的根。然后，它把根上的簇划分成多个较小的簇，并且递归地把这些簇划分成更小的簇，划分过程继续，直到最底层的簇都足够凝聚或者仅包含一个对象，或者簇内的对象都充分相似。分裂的层次聚类算法过程如图所示：,5,二.簇间距离度量方法,无论使用凝聚方法还是使用分裂方法，一个核心问题是度量两个簇之间的距离，其中每个簇一般是一个对象集。在凝聚和分裂的层次聚类之间，我们又依据计算簇间的距离的不同，4个广泛采用的簇间距离度量方法如下，其中 是两个对象或点p和p之间的距离。 （1）单连锁（single linkage）,又称最近邻（nearest neighbor）方法。指两个不一样的簇之间任意两点之间的最近距离。这里的距离是表示两点之间的相异度，所以距离越近，两个簇相似度越大。这种方法最善于处理非椭圆结构。却对于噪声和孤立点特别的敏感，取出距离很远的两个类之中出现一个孤立点时，这个点就很有可能把两类合并在一起。距离公式如下。,6,二.簇间距离度量方法,（2）全连锁（comlpete linkage），又称最远邻（furthest neighbor）方法。指两个不一样的簇中任意的两点之间的最远的距离。它面对噪声和孤立点很不敏感，趋向于寻求某一些紧凑的分类，但是，有可能使比较大的簇破裂。距离公式如下所示。 (3)组平均方法(grou Paverage linkage)，定义距离为数据两两距离的平均值。这个方法倾向于合并差异小的两个类，产生的聚类具有相对的鲁棒性。距离公式如下所示。,7,二.簇间距离度量方法,（4）平均值方法(centroid linkage),现计算各个类的平均值，然后定义平均值之差为两类的距离。距离公式如下所示。 其中 是两个类， 为对象 和 之间的距离, ， 分别为 , 的对象个数， ， 分别为类 的平均值。,8,三.层次聚类方法存在的不足,在凝聚的层次聚类方法和分裂的层次聚类的所有的方法中，都需要用户提供所希望所得到的聚类的单个数量和阈值作为聚类分析的终止条件，但是对于复杂的数据来说这个是很难事先判定的。尽管层次聚类的方法实现的很简单，但是偶尔会遇见合并或分裂点的抉择的困难。这样的抉择是特别关键的，因为只要其中的两个对象被合并或者分裂，接下来的处理将只能在新生成的簇中完成。已形成的处理就不能被撤消，两个聚类之间也不能交换对象。如果在某个阶段没有选择合并或分裂的决策，就非常可能会导致不高质量的聚类结果。而且这种聚类方法不具有特别好的可伸缩性，因为他们合并或分裂的决策需要经过检测和估算大量的对象或簇。,9,三.层次聚类方法存在的不足,层次聚类算法由于要使用距离矩阵，所以它的时间和空间复杂性都很高，几乎不能在大数据集上使用。层次聚类算法只处理符合某静态模型的簇忽略了不同簇间的信息而且忽略了簇间的互连性（互连性指的是簇间距离较近数据对的多少）和近似度（近似度指的是簇间对数据对的相似度）。,10,四.层次聚类的MATLAB实现,这里使用平均值方法(centroid linkage)来实现酒瓶颜色的聚类。 1.重要代码介绍 （1）数据标准化处理： %将数据进行标准化变换 Q1=zscore(X1); （2）利用欧拉距离函数计算样本间距离 %计算样本间的距离 Y1=pdist(Q1,euclid)%欧拉距离 （3）用两类间距离定义为类重心间的距离 Z1=linkage(Y1,centroid);%用两类间距离定义为类重心间的距离,11,四.层次聚类的MATLAB实现,%层次聚类 clear X1=1739.94 1675.15 2395.96 373.3 3087.05 2429.47 1756.77 1652 1514.98 864.45 1647.31 2665.9 222.85 3059.54 2002.33 877.88 2031.66 3071.18 1803.58 1583.12 2163.05 2352.12 2557.04 1411.53 401.3 3259.94 2150.98 363.34 3477.95 2462.86 1571.17 1731.04 1735.33 104.8 3389.83 2421.83 499.85 3305.75 2196.22 2297.28 3340.14 535.62 2092.62 3177.21 584.32 1418.79 1775.89 2772.9 1845.59 1918.81 2226.49,2205.36 3243.74 1202.69 2949.16 3244.44 662.42 1692.62 1867.5 2108.97 1680.67 1575.78 1725.1 2802.88 3017.11 1984.98 172.78 3084.49 2328.65 2063.54 3199.76 1257.21 1449.58 1641.58 3405.12 1651.52 1713.28 1570.38 341.59 3076.62 2438.63 291.02 3095.68 2088.95 237.63 3077.78 2251.96; %数据转化 %将数据进行标准化变换 Q1=zscore(X1); %计算样本间的距离 Y1=pdist(Q1,euclid)%欧拉距离 D=squareform(Y1) Z1=linkage(Y1,centroid);%用两类间距离定义为类重心间的距离 T1=cluster(Z1,4) %形成聚类,2.MATLAB完整程序：,12,四.层次聚类的MATLAB实现,plot3(X1(:,1),X1(:,2),X1(:,3),*,MarkerSize,8); grid; %变颜色 hold on; for t=1:length(T1) if(T1(t)=1) plot3(X1(t,1),X1(t,2),X1(t,3),Marker,*,Color,r); elseif(T1(t)=2) plot3(X1(t,1),X1(t,2),X1(t,3),Marker,*,Color,b); elseif(T1(t)=3) plot3(X1(t,1),X1(t,2),X1(t,3),Marker,*,Color,g); elseif(T1(t)=4) plot3(X1(t,1),X1(t,2),X1(t,3),Marker,*,Color,y);,end end hold on; xlabel (X); ylabel (Y); zlabel (Z); title(训练数据); xlabel(样本); ylabel(类间距离); title(训练数据); X2=1702.8 1639.79 2068.74 1877.93 1860.96 1975.3 867.81 2334.68 2535.1 1831.49 1713.11 1604.68 460.69 3274.77 2172.99 2374.98 3346.98 975.31 2271.89 3482.97 946.7 1783.64 1597.99 2261.31 198.83 3250.45 2445.08 1494.63 2072.59 2550.51 1597.03 1921.52 2126.76,13,四.层次聚类的MATLAB实现,1598.93 1921.08 1623.33 1243.13 1814.07 3441.07 2336.31 2640.26 1599.63 354 3300.12 2373.61 2144.47 2501.62 591.51 426.31 3105.29 2057.8 1507.13 1556.89 1954.51 343.07 3271.72 2036.94 2201.94 3196.22 935.53 2232.43 3077.87 1298.87 1580.1 1752.07 2463.04 1962.4 1594.97 1835.95 1495.18 1957.44 3498.02 1125.17 1594.39 2937.73 24.22 3447.31 2145.01 1269.07 1910.72 2701.97 1802.07 1725.81 1966.35 1817.36 1927.4 2328.79 1860.45 1782.88 1875.13; figure;,%数据转化 %将数据进行标准化变换 Q2=zscore(X2); %计算样本间的距离 Y2=pdist(Q2,euclid)%欧拉距离 D1=squareform(Y2) Z2=linkage(Y2,centroid);%用两类间距离定义为类重心间的距离 T2=cluster(Z2,4) %形成聚类 plot3(X2(:,1),X2(:,2),X2(:,3),*,MarkerSize,8); grid; %变颜色 hold on; for t=1:length(T2) if(T2(t)=1) plot3(X2(t,1),X2(t,2),X2(t,3),Marker,*,Color,r); elseif(T2(t)=2) plot3(X2(t,1),X2(t,2),X2(t,3),Marker,*,Color,b); elseif(T2(t)=3),14,四.层次聚类的MATLAB实现,plot3(X2(t,1),X2(t,2),X2(t,3),Marker,*,Color,g); elseif(T2(t)=4) plot3(X2(t,1),X2(t,2),X2(t,3),Marker,*,Color,y); end end hold on; xlabel (X); ylabel (Y); zlabel (Z); title(测试数据); xlabel(样本1); ylabel(类间距离1); title(测试数据); box on,15,五.仿真结果,程序运行完之后，出现如图的聚类结果：,16,五.仿真结果,程序运行完之后在命令窗口出现如下运行结果：,T1 = 1 3 1 2 3 2 1 4 3 3 1 3 3 4 4 2 1,4 4 1 1 4 3 4 2 1 3 3 3 T2 = 1 1 2 1 4,3 3 1 4 2 1 1 2 3 4 3 4 1 4 3 3 1 1 2,2 4 2 1 1 1,从结果中可以看出聚类结果完全正确。,17,六.总结,层次聚类方法是聚类分析中应用很广泛的一种方法，它是根据给定的簇间距离度量为准则，构造和维护一棵由簇和子簇形成的聚类树，直至满足某个终结条件为止。其中簇间距离度量方法有最小距离、最大距离、平均值距离和平均距离四种。层次聚类算法算法简单、而且能够有效地处理大数据集，但是它一旦一组对象合并或者分裂，它已做的处理便不能撤消和更改，如果某一步没有很好的做好合并或分裂的决定，则可能会导致低质量的聚类效果。 最大和最小度量代表了簇间距度量的两个极端。它们趋向对离群点和噪声数据过分敏感。 使用均值距离和平均距离是对最大和最小距离之间的一种折中方法，而且可以克服离群点敏感性问题。 层次聚类方法尽管简单，但经常会遇到合并或分裂点选择的困难。一旦一组对象合并或分裂，下一步的处理将对新生成的簇进行。 不具有很好的可伸缩性，因为合并或分裂的决定需要检查和估算大量的对象或簇。 类间距离的定义方法不同，会使分类结果不太一致.实际问题中常用几种不同的方法进行计算，比较其分类结果，从而选择一个比较切合实际的分类。,18,