第5章 聚类分析2

5.2 聚类准则函数在样本相似性度量的基础上，聚类分析还需要一定的准则函数， 才能把真正属于同一类的样本聚合成一个类型的子集，而把不同类的 样本分离开来。如果聚类准则函数选得好，聚类质量就会高。同时， 聚类准则函数还可以用来评价一种聚类结果的质量，如果聚类质量不 满足要求，就要重复执行聚类过程，以优化结果。 在重复优化中，可 以改变相似性度量，也可以选用新的聚类准则。1误差平方和准则（最常用的）假定有混合样木X = x ,x ,., x ，采用某种相似性度量，X被聚合成1 2 nc个分离开的子集X,X,., X，每个子集是一个类型，它们分别包含n,n , n 个样本n , n , n12c为了衡量聚类的质量，采用误差平方和 J 聚类准则函数，定义为 c一 m II2jJ =为卫II xckj = 1 k = 1式中m为类型w中样木的均值：m =丄目x，j = 1,2,., cjjj njj j=1m是c个集合的中心，可以用来代表c个类型。jJ 是样本和集合中心的函数。在样本集 X 给定的情况下， J 的取值cc取决于c个集合中心。丿描述n个试验样木聚合成c个类型时，所产生的 c总误差平方和。 J 越小越好。c最小方差划分：寻找 J 最小的聚类结果，也就是在误差平方和准则 c下的最优结果。误差平方和准则适用于各类样本比较密集且样本数目悬殊不大的样本分布。例如：上图的样本分布，共有3个类型，各个类型的样本数目相差不多（10个左右）。类内较密集，误差平方和很小，类别之间距离远。注意：如果不同类型的样本数目相差很大，采用误差平方和准则， 有可能把样本数目多的类型分开，以便达到总的 J 最小。如下图所示： cG）正确分类（b）错误分类下面进一步说明上述问题：例如：有5个样木，如下图所示xx e w , x e w1 4 1 5 2A准则错厲聚婪的示例虚线为正确类型区分域，实线为采用误差平方和最小准则时的类虚线划分时：别区分。w : X = x , x , x , x m = Y x = (0,0)T1 1 1 2 3 4 1 4 kw : X = x m = x = ( 2,0 )T22525c1= 工 II x - m II2 + 工 II x - m II2 = 4 k1k2xk G X1xk G X 2实线划分时：1=(-,0)T313m =乙 x22=(1.5,0) tXk G X 2c2= y II x - mk81II2 + 乙 II x 一 m II2 =+=k 23219=3.176xkG X1Xk G X 2所以J J1如果按误差平方和准则聚类将得到错误结果。2加权平均平方距离和准则定义：加权平均平方距离和准则j眾P . S*。jj j=1式中：S *是类内样木间平均平方距离。j工工IIx 一 Z2，所有的样木之间距离的平均值。n (n - 1)jjx e X x e XjjX 中的样本个数 njX中的样木两两组合共有叮nj 一D种。 j 2工工II x X|2表示所有样木之间距离之和。x e X x e X jjP为w类的先验概率，可以用样木数目n和样木总数目n来估计。jP= j因此：nj=1. S*jj5个样本，如上图所示用J重新讨论误差平方和准则中所举例子。x x e w x e w x = (0,-1)T x = (0,1)T1415212x = (一 1,0)Tx = (1,0)Tx = (2,0)T345虚线划分时：w :X =x,x ,x ,x 1 1 1w :X =x 225=04 J =l15实线划分时8-x = 2.133:X1=x,x ,x 123S*11(4 + 2 + 2)=3l2:X2= X 4, X 5S * = 1 (1) = 121虽然3 一x+一x1= 25，但已较接近所以，当各类样本数目相差悬殊时，使J Jl 2 l1用加权平均平方距离和准则，要比使用误差平方和准则容易得到正确1 _S * =(4 + 2 + 2 + 2 + 2 + 4)=-16聚类结果。同丿一样，丿越小，样木类内越密集。以聚合中心为极大值cl的局部区域密度越高，聚类结果越好。3类间距离和准则J =工（m 一 m）T （m 一 m） b j j j=1加权类间距离和：类间距离和可用于描述聚类结果的类间距离分布状态。它定义为：=为 P - （m 一 m）T （m 一 m）b j j jj=1mj n j j j =1式中，m为w类型的样木均值向量：m =丄目x，j = 1,2,. cjjm为全部样木的均值向量：m = 1 x。nkk = 1P为w类型的先验概率，可以用笃来估计。j j n对于两类问题w / w，类间距离常用J = （m 一 m ） T （m 一 m ）计算。1 2 b 1 2 1 2两类问题的加权类间距离和：1 Y1J = n - (m - m)T (m - m) = (n - mT - m - n - mT - m + n - mT - m - n - mT - mb njjjn 1111122222代入上式，有：1J =bnn n ,、 n n z、i 2 (mT 一 mT )m +12(mT 一 mT )mn 1 2 1 n 1 2 2n n z、，i 2 (m 一 m ) t (mn 1 2一 m ) = P - P - J2 1 2 b类间距离和准则描述不同类型之间的分离程度，所以 J 的值越大，表示各类之间分离性好，聚类质量高。4散射矩阵为了对聚类质量有一个全面的描述和考核标准，可以通过散射矩阵引导出一些准则函数，它们不但反映同类样本的聚集程度，而且也反映不同类之间的分离程度。假定混合样木集X的n个样木被聚集成c个类型的子集X，每个子j集有n个样木，则类内散射矩阵S定义为： jwS =P Swj jj=1其中S为某一个类型的类内散射矩阵：1 vS = L (x(j) - m )(x(j) - m )T j nkj kjx(j)表示类型w的第k个样木，j = 1,2,., c kj类间散射矩阵 S 定义为：b S =工 P (m - m)(m - m)Tbjjjj=1P n / njj式中，m为各类型的均值向量，m为全部样木的均值向量，。n /“)j为各类型先验概率。定义全部样木的总散射矩阵S为:tnk = 1 S = -1 (m - m)(m - m) tkk上述3个散射矩阵有如下关系;=S + Swb证明：C n 1 vj= i -(m(j) 一 m)(m(j) 一 m)Tnnj =1j k =1k= 工 P 卫 (m( j) - m )(m( j) - m )T + (m - m)(m - m)T kjkjjjZc1P - S + 乙 P - (m 一 m)(m 一 m)T j jjjjj =1j =1=S + Swb这一结果表明，对于给定的混合样本集，类内散射的减少，将导致类间散射的增加。对某一聚类结果，类内散射越小越好，类间散射越大越好。利用SSSwb可以定义如下的4个聚类准则：t 表示矩阵的迹，也就是对角线元素之和，为行列式。14时考虑了类内的散射和类间散射，为了得到好的聚类结果，它们的值越大越好。为了便于计算，考虑到矩阵的迹和行列式的旋转不变性，我们总wb可以找到一个正交矩阵U，使Ut ( S -1 S )U = Awb(S 一 1S )是d X d维的对称矩阵，U是d X d维正交归一化矩阵，A是以特 征值九(i = 1,2,.,d)为对角线的对角矩阵。则有：iJ = X X1ii 二 1j = n x2ii 二 1又由于：S-1S = S-1(S+ S ) = I + S-1S，I为d x d维单位矩阵。w t w w b w bUT (S -1S )U = UT (I + S -1S )U = I + Aw t w b所以：J = X (1 + X )3ii 二 1J = n (1 + X )4ii 二 1因此，只要求出(S-1S )的特征值，就很容易求得JJ。若JJ足w b 1 4 1 4够大，则聚类质量好；若较小，在则聚类质量差，应该重新聚类。