聚类分析

1聚类分析2主要内容：一、距离聚类的概念二、相似性测度和聚类准则三、基于距离阈值的聚类算法四、层次聚类法五、动态聚类法六、聚类结果的评价3一、距离聚类的概念有n个特征值则组成n维向量，称为该样本的特征向量。它相当于特征空间中的一个点，以特征空间中，点间的距离函数作为模式相似性的测量，以“距离”作为模式分类的依据，距离越小，越“相似”。T21],....,,[nxxxX1.概念：“物以类聚”聚类分析：根据模式之间的相似性对模式进行分类，是一种非监督分类方法。2．相似性的含义注意：聚类分析是否有效，与模式特征向量的分布形式有很大关系。选取的特征向量是否合适非常关键。例：酱油与可乐。4复习：已知向量，则：321yyyY232313322212312121321321TyyyyyyyyyyyyyyyyyyyyyYY二、相似性测度和聚类准则相似性测度：衡量模式之间相似性的一种尺度。如：距离。1相似性测度2232221321321TYYYyyyyyyyyy51）欧氏距离（Euclid，欧几里德）——简称距离设X1、X2为两个n维模式样本，T112111],....,,[nxxxXT222212],....,,[nxxxX2121),(XXXXD)()(21T21XXXX22122111)()(nnxxxx注意：A）各特征向量对应的维上应当是相同的物理量；注意物理量的单位。(D_Distance)距离越小，越相似。欧氏距离定义为：某些维上物理量采用的单位发生变化，会导致对同样的点集出现不同聚类结果的现象。6b(5,0)d(4,5)c(1,4)a(0,1)12345012345(a))mm(1x)mm(2xB）解决方法：使特征数据标准化，使其与变量的单位无关。d(0.4,5)c(0.1,4)a(0,1)123450123b(0.5,0)(b))mm(2x)cm(1xb(5,0)c(1,0.4)d(4,0.5)a(0,0.1)123012345)cm(2x)mm(1x(c)7对n维向量：,nxx1Xnmm1M2）马氏距离(Maharanobis)平方表达式：式中，X：模式向量；M：均值向量；C：该类模式总体的协方差矩阵。)()(1T2MXCMXD}{22112211TnnnnmxmxmxmxmxmxEEMXMXC(M_Mean)(C_covariance)8nnnnnnnnmxmxEmxmxEmxmxEmxmxEmxmxEmxmxEmxmxE112222112211221111112212222121212211nnnkkjkn表示的概念是各分量上模式样本到均值的距离，也就是在各维上模式的分散情况。越大，离均值越远。2jk优点：排除了模式样本之间的相关影响。当C=I时，马氏距离为欧氏距离。91x2xiXjX当m=2时，明氏距离为欧氏距离。n维模式样本向量Xi、Xj间的明氏距离表示为：式中，xik、xjk分别表示Xi和Xj的第k个分量。mnkmjkikjimxxD11),(XX22111),(jijijixxxxDXX街坊欧氏3）明氏距离(Minkowaki)当m=1时：nkjkikjixxD11),(XX称为“街坊”距离(“Cityblock”distance)。当k=2时：图示104）汉明(Hamming)距离jknkikjihxxnD121),(XX设Xi、Xj为n维二值（1或－1）模式样本向量，则两个模式向量的各分量取值均不同：Dh(Xi,Xj)=n；全相同：Dh(Xi,Xj)=0式中，xik、xjk分别表示Xi和Xj的第k个分量。汉明距离：5）角度相似性函数||||||||),(TjijijiSXXXXXX是模式向量Xi，Xj之间夹角的余弦。116）Tanimoto测度用于0，1二值特征的情况，jijjiijijiSXXXXXXXXXXTTTT),(数中占有的特征数目的总和中共有的特征数目jijiXXXX,相似性测度函数的共同点都涉及到把两个相比较的向量Xi，Xj的分量值组合起来，但怎样组合并无普遍有效的方法，对具体的模式分类，需视情况作适当选择。12聚类准则：根据相似性测度确定的，衡量模式之间是否相似的标准。即把不同模式聚为一类还是归为不同类的准则。确定聚类准则的两种方式：1）阈值准则：根据规定的距离阈值进行分类的准则。2）函数准则：利用聚类准则函数进行分类的准则。聚类准则函数：在聚类分析中，表示模式类间相似或差异性的函数。它应是模式样本集{X}和模式类别的函数。可使聚类分析转化为寻找准则函数极值的最优化问题。一种常用的指标是误差平方之和。cSj,,2,1j,2聚类准则13聚类准则函数：cjjSXjJ12MX式中：c为聚类类别的数目，jSXjjNXM1jS为属于集的样本的均值向量，jNjS为中样本数目。J代表了分属于c个聚类类别的全部模式样本与其相应类别模式均值之间的误差平方和。适用范围：适用于各类样本密集且数目相差不多，而不同类间的样本又明显分开的情况。14例1：类内误差平方和很小，类间距离很远。可得到最好的结果。类长轴两端距离中心很远，J值较大，结果不易令人满意。1（a）2x1xM11M22M33O1x（b）2x2M2M11O152x（b）2M2M111xO错误分类例2：另一种情况有时可能把样本数目多的一类分拆为二，造成错误聚类。原因：这样分开，J值会更小。正确分类2x（a）2M2M111xO16三、基于距离阈值的聚类算法1）问题：有N个待分类的模式，要求按距离阈值T分类到以为聚类中心的模式类中。NXXX,,,21,,21ZZ2）算法描述①任取样本Xi作为第一个聚类中心的初始值，如令Z1=X1。②计算样本X2到Z1的欧氏距离，若，定义一新的聚类中心Z2=X2；否则X2∈以Z1为中心的聚类。1221ZXDTD21(T_threshold)1近邻聚类法17……依此类推，直到将所有的N个样本都进行分类。③假设已有聚类中心Z1、Z2，计算和，1331ZXD2332ZXD若且，则建立第三个聚类中心Z3=X3；TD31TD32否则X3∈离Z1和Z2中最近者（最近邻的聚类中心）。3）算法特点B）优点：计算简单。（一种虽粗糙但快速的方法）A）局限性：很大程度上依赖于第一个聚类中心的位置选择、待分类模式样本的排列次序、距离阈值T的大小以及样本分布的几何性质等。18用先验知识指导阈值T和起始点Z1的选择，可获得合理的聚类结果。否则只能选择不同的初值重复试探，并对聚类结果进行验算，根据一定的评价标准，得出合理的聚类结果。对结果验算，类内各样本点间距离方差之和太大减小T，修改中心Z。2T1T1T4）算法讨论图5选取不同阈值和聚类中心时得到的不同聚类结果192最大最小距离算法（小中取大距离算法）1）问题已知N个待分类的模式，分类到聚类中心对应的类别中。NXXX,,,21,,21ZZ2）算法描述①选任意一模式样本做为第一聚类中心Z1。②选择离Z1距离最远的样本作为第二聚类中心Z2。③逐个计算各模式样本与已确定的所有聚类中心之间的距离，并选出其中的最小距离。例当聚类中心数k=2时，计算11ZXiiD22ZXiiDmin(Di1,Di2)，i=1，…，N（N个最小距离）20⑥将样本按最近距离划分到相应聚类中心对应的类别中。Nii,,2,1,X⑤重复步骤③④，直到没有新的聚类中心出现为止。④在所有最小距离中选出最大距离，如该最大值达到的一定分数比值(阈值T)以上，则相应的样本点取为新的聚类中心，返回③；否则，寻找聚类中心的工作结束。21ZZ10,},...,2,1),,max{min(2121ZZNiDDii若（θ：用试探法取为一固定分数，如1/2。）则Z3存在。为使聚类中心更有代表性，可取各类的样本均值作为聚类中心。例k=2时思路总结：先找中心后分类；关键：怎样开新类，聚类中心如何定。21例3对图示模式样本用最大最小距离算法进行聚类分析。135791357X1X4X3X5X8X9X7X10X2X6x1x2①选Z1=X1②距Z1最远，选为Z2。计算T。③对应最小距离中的最大值，且T，选作Z3。结果：Z1=X1；Z2=X6；Z3=X7。④用全体模式对三个聚类中心计算最小距离中的最大值，无T情况，停止寻找中心。⑤聚类80212121ZZT10个最小距离中，X7对应的距离T,73XZ③22四层次聚类法（HierarchicalClusteringMethod）（系统聚类法、分级聚类法）思路：每个样本先自成一类，然后按距离准则逐步合并，减少类数。1算法描述①N个初始模式样本自成一类，即建立N类：计算各类之间（即各样本间）的距离，得一N×N维距离矩阵D(0)。“0”表示初始状态。)0(,),0(),0(21NGGG(G_Group)23②假设已求得距离矩阵D(n)（n为逐次聚类合并的次数），找出D(n)中的最小元素，将其对应的两类合并为一类。由此建立新的分类：),1(),1(21nGnG。③计算合并后新类别之间的距离，得D(n+1)。④跳至第2步，重复计算及合并。结束条件：①取距离阈值T，当D(n)的最小分量超过给定值T时，算法停止。所得即为聚类结果。②或不设阈值T，一直到将全部样本聚成一类为止，输出聚类的分级树。242问题讨论：类间距离计算准则KHDDKHKHHKXXXX,,minHK①最短距离法如H、K是两个聚类，则两类间的最短距离定义为：：H类中的某个样本XH和K类中的某个样本XK之间的欧氏距离。KHDXX,DHK：H类中所有样本与K类中所有样本之间的最小距离。25IHDDIHIHHIXXXX,,minJHDDJHJHHJXXXX,,min如果K类由I和J两类合并而成，则HJHIHKDDD,min得到递推公式：√HKIJHIDHJD②最长距离法KHDDKHKHHKXXXX,,max若K类由I、J两类合并而成，则IHDDIHIHHIXXXX,,maxJHDDJHJHHJXXXX,,maxHJHIHKDDD,max有：26③中间距离法介于最长与最短的距离之间。如果K类由I类和J类合并而成，则H和K类之间的距离为④重心法将每类中包含的样本数考虑进去。若I类中有nI个样本，J类中有nJ个样本，则类与类之间的距离递推式为222412121JIJHIHKHDDDD2222)(JIJIJIJHJIJIHJIIKHDnnnnDnnnDnnnD27定义类间距离的方法不同，分类结果会不太一致。实际问题中常用几种不同的方法，比较分类结果，从而选择一个比较切合实际的分类。22JHJIJIHJIIKHDnnnDnnnD⑤类平均距离法KjHijiKHKHdnnD212jid：H类任一样本Xi和K类任一样本Xj之间的欧氏距离平方。若K类由I类和J类合并产生，则递推式为28T10,2,1,3,0XT20,1,0,3,1XT31,0,0,3,3XT40,2,0,1,1XT51,2,1,2,3XT60,1,1,1,4X例：给出6个五维模式样本如下，按最短距离准则进行系统聚类分类。计算各类间欧氏距离：解：（1）将每一样本看作单独一类，得：11)0(