一种基于最小张树的属性聚类算法

2001年2月系统工程理论与实践第2期　文章编号:100026788(2001)022*******一种基于最小张树的属性聚类算法彭春华,程乾生(北京大学数学科学学院信息科学系,北京100871)摘要:　结合图论中的最小张树方法,提出了相似度以及接触度两个概念,并以此为基础建立了一种属性聚类算法Λ文中就几个具体问题,将其与FCM及A K M等方法进行比较,以便分析其聚类效果Λ很明显,我们所介绍的方法弥补了其它方法的一些不足,并能在一定程度上解决实际问题Λ关键词:　最小张树;属性聚类;相似度;接触度中图分类号:　O213 αA n A ttribu te C lu stering A lgo rithm Based onM in i m um Spann ing T reePEN G Chun2hua,　CH EN G Q ian2sheng(Schoo l of M athem atcal Sciences,Pek ing U n iverity,Beijing100871)Abstract:　Com b in ing w ith the m ethod of m in i m um spann ing tree in Graph theo ry,w ep resen t tw o concep ts of si m ilarity and con tact degree in th is paper,and bu ild a newattribu te clu stering algo rithm based on them.W e compare the app roach w ith som eo ther m ethods such as FC M and A K M,in several p rob lem s fo r analyzing it’seffectiveness.It is obvi ou s that the app roach w e in troduced here m akes up a lo ss ofo ther m ethods and cou ld pactically so lve p rob lem s in a certain ex ten t.Keywords:　m in i m um spann ing tree;attribu te clu ster;si m ilarity;con tact degree1　引言无监督聚类分析是模式识别领域里的一个重要的研究内容Λ聚类分析的思想是在缺乏先验知识的条件下,将样本集X={x1,x2,…,x N}中的样本依照某一相似度准则分到模式类C1,C2,…,C K中去Ζ将x i分到模式类C k中的要求是x i与C k之间的相似度要明显大于x i与其它模式类之间的相似度Ζ由于研究的问题比较复杂,特别是当模式类的数目不能确切知道以及模式类之间存在覆盖的情况下,聚类的效果就会变得比较差Ζ因此人们一直试图找到一种适用性较强的聚类算法Ζ传统的聚类分析方法有最近邻法、层次聚类法、K均值法以及ISODA TA算法等[1]Λ此外也有文献介绍利用图论中的最小张树进行聚类分析的方法[2]Λ这些传统的聚类分析方法由于采用欧氏距离准则,且在聚类中要求固定模式类的数目(ISODA TA算法也要求事先给定预期的模式类数目),又绝少考虑到模式类之间相互覆盖的情形,因而在应用中受到了很大的限制Λ如图1a、图2a、图3a三种情况就是传统聚类方法难于解决的典型问题Λ近年来,人们不断提出新的思想和方法,将聚类分析扩充到更深更广的领域Λ其中模糊聚类构成了一个十分重要的分支领域Λ模糊聚类的思想是建立在Zadeh的模糊理论基础上的Λ由于计算样本属于某模式类的隶属度取值范围为[0,1],因而利用超平面或超曲面划分目标空间时,自然就考虑了模式类之间重叠的情况Λ结合了模糊理论的传统聚类分析方法有FC M算法、Fuzzy ISODA TA算法等等[3]Λα收稿日期:1999203224资助项目:国家自然科学基金这里我们注意到,不管是传统的聚类分析方法还是结合了模糊理论的聚类方法,都是研究样本点与模式类的类中心的相似度Λ也就是说每个模式类只有一个代表点一类中心Λ依据这样的相似准则(不考虑使用加权欧氏距离的情况),所形成的模式类类边界在空间上看是一个以类中心为球心的超球面Λ为弥补这一缺陷,有文章提出以超椭球面代替超球面并在实际问题中得到应用[4]Λ另外,诸如神经网络[5]、遗传算法[6]等方法也纷纷引入到聚类分析当中Λ而且诸多方法的综合[7]以及提出新的基于概率分布密度的准则函数[8]等都给予我们很大的启发Λ文献[9]介绍的A K M 算法因为采用稳态准则函数的缘故,在聚类是可以较好地避免噪声或野值的影响,所以也能取得良好的效果Λ我们在本文介绍的新属性聚类方法源自传统聚类里的最小张树法(A ttribu te C lu ster of M in i m um Spann ing T ree ,简称A C M ST ),并以相似度和接触度的概念建立了一个新的分类准则Λ正是由于应用了属性集和属性测度理论[10],该方法避免了模糊聚类的一些不足,同时又能对分类给以较清晰的解释Λ为了分析方法的有效性,我们就几个实例将其与FC M 、ISODA TA 算法进行了比较,效果较好Λ2　最小张树与属性聚类211　最小张树(M i n i m u m Spann i ng Tree )[11]定义1　一个无向图G 记作G =(V ,E ),其中V 是一个非空集合,它的元素称为图的结点,E 是V 中的无序偶集合,它的元素称为图的边Ζ定义2　边不重复但结点可以重复的路径称为简单路径Ζ结点不重复的路径称为基本路径Ζ定义3　如果无向图G =(V ,E )任意两点之间至少有一条路径,则称G 是连通图Ζ否则称为非连通图或分离图Ζ定义4　连通不含回路的无向图称为无向树,简称为树Ζ设T =(V ,E )为一棵无向树,v ∈V ,若d (v )=1,则称v 为T 的树叶;若d (v )Ε2,则称v 为分支点Ζ定义5　对图G =(V ,E )的每条边e 附加上一个实数w (e ),称w (e )为边e 上的权ΖG 连同附加在个边上的权称为带权图,记作G =(V ,E ,W )Ζ定义6　设无向连通带权图G =(V ,E ,W ),T 是G 的一棵生成树ΖT 各边的权之和称为T 的权,记作W (T )ΖG 的所有生成树中权最小的生成树称为G 的最小生成树(最小张树)ΖK ru skal 算法:设n 阶无向连通带权图G =(V ,E ,W )有m 条边,将m 条边按权从小到大顺序排列,设为e 1,e 2,…,e m Ζ取e 1在T 中,然后依次检查e 2,e 3,…,e m ,若e j 与T 中的边不构成回路,则取e j 在T 中,否则弃去e j Ζ这样构造的树为最小张树Ζ212　属性聚类(A ttr ibute Cluster )[12]设8为研究对象空间,F 为属性空间,{C 1,C 2,…,C K }为F 的分割,即∪Kk =1C k =F ,C i ∩C j =<(i ≠j ,Πi ,j )ΖC i 与C j 之间的距离为d (C i ,C j )=d ij ,C i 与C j 之间的相似度为S (C i ,C j )=s ij ,则C i 与C j 能明显区别的条件是f (d ij )・s ij ΦΚ,Κ为某阈值Ζ其中f (t )是[0,+∞)上正的非增有界函数Ζ样本x i 与C k 类的相似度由S (x i ,C k )=1 C k ∑x j ∈C kS (x i ,x j ),S (x i ,x j )∈[0,1]Ζ式中x j ∈C k 表示x j 属于C k 类, C k 表示属于C k 类中样本的数目Ζ设样本x i 与C k 类的距离度量为d (x i ,C k ),如果f (d (x i ,C k 3)) S (x i ,C k 3)=m ax k =1,2,…,K f (d (x i ,C k )) S (x i ,C k )>Κ(1)Κ为某阈值,则将x i 划分到C k 3类中,否则拒绝划分x i 样本Ζ结合属性测度,我们可以将式(1)的划分准则改为下式,设Λ(x i ∈C k )=Λik =f (d (x i ,C k )) S (x i ,C k )∑K j =1f (d (x i ,C j )) S (x i ,C j ),　i =1,2,…,N(2)如满足Λ(x i ∈C k 3)=m ax k =1,2,…,K Λ(x i ∈C k )>Κ,Κ∈[0,1),则将x i 划分到C k 3类中Ζ可以看出,当x i 与C k 之间的相似度S (x i ,C k )恒等于1,f (t )=f -1时,属性聚类便成为传统聚类中的最小近邻法Ζ13第2期一种基于最小张树的属性聚类算法3　AC M ST 算法(A ttr ibute Cluster of M i n i m u m Spann i ng Tree )311　基本概念我们将模式类C k 表示为C k =(X k ,T k ,L k ,p k ),k =1,2,…,K Ζ其中X k 是属于C k 类的样本的集合;T k 是由X k 构成的最小张树;L k 是T k 的树叶集,有Πv ∈L k ,d (v )=1;p k 是C k 类的边缘密度Ζ规定C K +1为拒绝判别类,则有∪K +1k =1X k =X ={x 1,x 2,…,x N },X i ∩X j =<(i ≠j ),ΠX i ,X j <X Ζ定义7　样本x i ∈X 所处空间位置的平均样本密度p (x i )=m +1V (Εi )(3)V (Εi )是以x i 为中心,Εi 为半径,包容了除x i 以外的m (m =3～5)个样本的最小超球体的容积Ζ对于平面点图的情形,可取V (Εi )=Π(Εi )2,Εi >0Ζ则样本x i 可表示成x i ={X m i ,p (x i )},其中X m i 是离x i 最近的m 个样本的集合,满足m ax x j ∈X m i ‖x i -x j ‖ΦΕi定义C k 类的边缘密度为p k =1L k∑x j ∈L k p (x j )(4)L k 表示L k 中树叶的数目Ζ定义8　类间相似度(Si m ilarity ):设对ΠC k ,C l 类,已知它们的边缘密度分别为p k ,p l Ζ则C k 与C l 两类的相似度为S (C k ,C l )=exp -12(p k -p l )2p k p l(5) 定义9　类间接触度(Con tact D egree ):设对ΠC k ,C l 类,已知它们的树叶集分别为L k ,L l Ζ令s =m in L k , L l ,再不重复地找出s 个最小距离对(a 1,b 1),(a 2,b 2),…,(a s ,b s ),其中{a 1,a 2,…,a s }ΑL k ,{b 1,b 2,…,b s }ΑL l ,并满足‖a 1-b 1‖Φ‖a 2-b 2‖Φ…Φ‖a s -b s ‖Ζ已知两类的平均密度为pθk ,l =(p k +p l ) 2Ζ若满足‖a i -b i ‖ΦV -1(1 pθk ,l ),则称a i 与C l 类完全接触或b i 与C k 类完全接触Ζ可以定义样本a i 与C l 类以及b i 与C k 类的接触度为D c (a i ,C l )=D c (b i ,C k )=exp {1-V (‖a i -b i ‖) pθk ,l },‖a i -b i ‖>V -1(1 p θk ,l )1,‖a i -b i ‖ΦV -1(1 p θk ,l )(6)定义C k 与C l 类之间的接触度为D c (C k ,C l )=1s ∑s i =1Dc (a i ,C l )=1s ∑s i =1Dc (b i ,C k )(7)312　模式类合并准则如果C k ,C l 类同属一类的测度ΛC k ,C l =[D c (C k ,C l ) S (C k ,C l )]1 2∑l ≠k [D c (C k ,C l ) S (C k ,C l )]1 2满足最大属性测度准则[12],即ΛC k ,C l =m ax j ≠k ,j =1,2,…,KΛC k ,C j ,且ΛC k ,C l >Κ,Κ∈[0,1)Ζ则将C k ,C l 类合并为C k 3类,否则拒绝合并C k ,C l 类Ζ设C k 3=(Xk 3,T k 3,L k 3,p k 3),其中X k 3=X k ∪X l ,T k 3是X k 3中样本构成的最小张树,L k 3是T k 3的树叶集,p k 3是C k 3类的边缘密度Ζ313　AC M ST 算法过程Step 1　初始化:令K =N ,即每一个样本集中的样本自成一类,有X k =L k ={x k },p k =p (x k )Ζ规定C K +1是拒绝判别类,在初始的时刻为空集Ζ确定合并阈值ΚΖStep 2　计算X k ,k =1,2,…,K 类中任两个样本点x i ,x j 之间的相似度23系统工程理论与实践2001年2月S =(x i ,x j )=exp -12(p (x i )-p (x j ))2p (x i ) p (x j )以及根据相似度、距离所确定的权(x i ,x j ,x i ≠x j 形成边e (x i ,x j )的权)w (e (x i ,x j ))=S (x i ,x j )‖x i -x j ‖我们以C k 类内各边的权遵照K ru skal 算法构造出最小张树,并得到该最小张树的树叶集,再按照(3)、(4)式计算出每一类的边缘密度ΖStep 3 按照(5)、(6)、(7)式计算出任两类之间的相似度和接触度ΖStep 4 依模式类合并准则,将满足合并准则的同属属性测度最大的两类合并在一起,返回S tep 3,K =K -1Ζ若任两类都不满足模式类合并准则或K 等于期望类别数,终止算法Ζ4　AC M ST 算法与其它几种聚类算法的比较图1(a )图1(b )图1(a )中样本点共1784个,分为两类,类内样本数比例接近1∶2Λ从样本分布可以看出,两类的类中心比较近Λ如果采用传统基于类中心分类的聚类算法将很难把两类分开,而应用A C M ST 算法结果就比较理想,见图1(b )Λ图2(a )图2(b )33第2期一种基于最小张树的属性聚类算法图2(a )中样本总数1788个,两类类内样本数比例约为1∶1Λ由于两不同类之间无法简单地进行线性划分,实验中我们采用了A C M ST 算法对其进行聚类,效果见图2(b )Λ图3(a )图3(b )图3(a )共有样本1793个,分为比例悬殊的两类(数目比约为10∶1)Λ我们知道,采用空间距离判据的模式聚类方法适用于类间距较大,且类内样本数目接近的聚类问题Λ对于象图3(a )这样的问题,再应用仅基于距离判据的传统聚类方法,显然是不合适的Λ图3(b )是应用A C M ST 算法得到的结果Λ三种算法的结果列于表格1中Λ表1方 法A CM ST 算法ISODA TA 算法FCM 算法图1(a )聚类正确率99.38%58.5%51.26%图2(a )聚类正确率99.33%62.1%65.79%图3(a )聚类正确率99.16%74.86%58.56%以上三个例子代表了三种典型聚类问题Λ而A C M ST 算法并没有因为问题的改变降低聚类效果,这多少也反映了该算法的广泛适用性Λ5　结论本文介绍的基于最小张树的属性聚类算法结合了属性聚类以及最小张树方法的特点,能够以较高的精确度进行聚类分析Λ同文中列举的其它几种聚类算法相比,它有较强的适用性Λ只是由于在算法初始化时,要用3～5个点来计算每样本点坐标的平均样本密度,因此A C M ST 算法在处理稀疏点阵图时会遇到一些困难Λ虽然提出一种十全十美的算法是件不容易的事,但是人们一直希望能有种优秀的聚类算法以解决模式识别领域里的大多数问题Λ我们同样抱有相同的想法,并为此进行深入研究进而提出更新更好的算法Λ参考文献:[1]　M oh rir P S .Pattern 2R ecogn iti on T ran sfo rm s [M ].John W iley &Son s Inc .,N ew Yo rk ,1992.[2]　Sing 2T ze Bow .Pattern R ecogn iti on :A pp licati on to L arge D ata 2set P rob lem s [M ].M arcel D ekker ,Inc .,N ew Yo rk and Basel ,1984.(下转第42页)[10]　J iang Changjun,W u Zhehu i.N et operati on s[J].J of Compu t Sci and T echno l,1992,7(4),333～344.[11]　J iang Changjun.N et operati on s(2)[J].J of Compu t Sci and T echno l,1995,10(6):509～517.[12]　蒋昌俊.Petri网的动态不变性[J].中国科学(E),1997,27(6):567～573.[13]　蒋昌俊,郑应平,疏松桂.基于行为表达式的任意随机Petri网的品质分析[J].自动化学报,1997,23(3):370～376.[14]　Berthelo t G,Rozenger G.Check ing p roperties of nets u sing tran sfo rm ati on s[A].A dvances in Petrinets[C].N ew Yo rk:Sp ringer2V erlag,1985.[15]　L ee K H,Favrel J.H ierarch ical reducti on m ethod fo r analysis and decompo siti on of Petri nets[J].IEEE T ran s.on system s,m an and cybernetics,1985,15(2):272～280.[16]　L ee K H,Favrel J,Bap tiste P.Generalized Petri net reducti on m ethod[J].IEEE T ran s,onsystem s,m an and cybernetics,1987,17(2):297～303. =(上接第34页)[3]　Sankar K Pal,M ajum der D K D.Fuzzy M athem atical A pp roach to Pattern R ecogn iti on[M].W ileyEastern L td.,1986.[4]　Isak Gath,D an Hoo ry.Fuzzy clu stering of elli p tic ring2shaped clu sters[J].Pattern R ecogn iti onL etters,1995,16(7):727～741.[5]　Srikan th R,Petry F E,Kou tsougeras C.Fuzzy elastic clu stering[A].P roc Second In ternat Conf onFuzzy system(Fuzzy2IEEE)[C].San F rancisco,CA,1993:1179～1182.[6]　Srikan th R,et al.A variab le2length genetic algo rithm fo r clu stering and classificati on[J].PatternR ecogn iti on L etters,1995,16(8):789～800.[7]　Chen C L P,L u Y.Fuzzy:A fuzz2based concep t fo rm ati on system that in tegrates hum ancatego rizati on and num erical clu stering[J].IEEE tran s.on System s,M an,and Cybernetics,1997, 27(1):79～94.[8]　H erb in M,Bounel N,V au tro t P.A clu stering m ethod based on the esti m ati on of the p robab ilityden sity functi on and on the skeleton by influence zones:A pp licati on to i m age p rocessing[J].Pattern R ecogn iti on L etters,1996,17(11):1141～1150.[9]　程乾生1属性均值聚类[J]1系统工程理论与实践,1998,18(9):124～126.[10]　程乾生1属性集理论与模糊数学、模式识别、人工智能[A]1中国工业与应用数学学会第三次大会文集[C].北京:清华大学出版社,1994:6～14.[11]　Be’la Bo lloba’s.Graph T heo ry:A n In troducto ry Cou rse[M].Sp ringer2V erlag,N ew Yo rk,1979.[12]　程乾生1属性识别理论模型及其应用[J].北京大学学报(自然科学版),1997,33(1):12～20.。