《一种基于相容关系的聚类算法.doc》由会员分享，可在线阅读，更多相关《一种基于相容关系的聚类算法.doc（10页珍藏版）》请在三一文库上搜索。
1、一种基于相容关系的聚类算法Clustering on compatible relation WAN Ren-xia, WANG Li-xin, LIU Zhen-wen, SU Xiao-ke (College of Information Science & Technology, Donghua University, Shanghai 201620, China) Abstract: Cluster analysis had played a very important role in data mining. This paper proposed a new algorithm
2、based on compatible relation. The new algorithm grouped objects by the maximum compatible clusters and permited one object belonging to several different clusters while every cluster had its exclusive members, which gained a different clustering result from the traditional cluster algorithms. The ex
3、periments get a consistent result. Key words：cluster; compatible relation; compatible subset 0 引言 ?年来,对数据集上的聚类算法已有了广泛的研究。总体来说，传统聚类算法可以划分为硬聚类和模糊聚类两大类1。硬聚类算法将数据集划分为不相交的几个数据子集，每个数据子集代表一个类簇，而模糊聚类更多的是关注于簇中心及各个数据与所有簇中心隶属关系的变化，分析每个数据点隶属于各个簇的程度。本文提出了一种基于数据点间关系度量的聚类算法，该算法依据数据点间关系程度进行聚类，得到了不同于传统算法的聚类结果。基于真实数据
4、集的实验分析表明新算法具有比传统算法更为合理的聚类效果。 1 相关工作 ?统的聚类是指将数据对象分组成为若干个类，使得在同类中的对象间具有较高的相异度，而不同类中的对象差别较大。相异度是根据描述对象的属性值来计算的，而距离是其经常采用的度量方式。在聚类分析中，许多基于内存的聚类算法选择如下两种有代表性的数据结构:a)数据矩阵。它用P个属性来表示n个对象，表现形式是xijnp。其中xij表示对象i在属性j上的取值。b)相异度矩阵。它用来存储n个对象两两间的相异性，表现形式是D(i,j)nn。其中D(i,j)是对象i与对象j间相异性的量化表示，其值越小，两个对象就越接近，且D(i,j)0，D(i,
5、i)=0，D(i,j)=D(j,i)。从数据对象间的关系角度上来说，相异度只是对数据对象之间的离散关系的一种分析，这只是数据对象间关系分析的一种，而实际上数据对象的关系可能会比较复杂，甚至有些关系是不可以用相异度来衡量的，如对操场上的学生按朋友关系分组。 ?南?2，3研究了利用偏序关系和偏序集进行分层聚类的问题，提出了PoClustering算法，该算法在基因分组的实验中表现出更好的分类效果。 ?南?4研究了利用相异度的正交变换对具有三角不等式特性的高维数据的聚类问题，并通过误差评价边界来降低聚类的计算复杂度和提升其可扩展性。 ?南?5利用压缩相异度的方法来扩展K-modes算法，并利用启发式
6、的方法来改进相异度的简单匹配。 ?南?6研究了利用相异度平滑的技术来对二元变量聚类的方法。通过收缩评价的思想来过滤噪声数据，从而达到平滑相异度矩阵的目的。 ?南?7通过定义关系和多值对象属性及类型多样性的拓扑测度来构建一类特殊的相异度模型，并基于此模型完成自动分类的目标。 ?南?8介绍了等价相异度矩阵的性质，并给出了等价相异度矩阵的逐次平方求解方法和基于相异度矩阵的聚类算法。 ?鲜鲅芯恐饕?还是基于对象间相异或相似关系，其聚类结果也往往都是些类球形的簇。总体来说，基于数据对象间非相异或相似关系的研究还较少见报道；从现有的聚类技术来看，各种聚类方法也都没有很好地利用相异度的性质。本文研究基于相容
7、关系的聚类问题，并对相异度聚类的性质和方法作了进一步探讨。 2 对象集上的相容关系 ?1 设D是对象集S上的关系度量，(0)是已给定的阈值，满足： a) D是自反的（即当且仅当xS，有D(x,x)）。 b) D是对称的（即当且仅当x,yS，如果D(x,y)，则D(y,x)）。 ?疚某?D为S上的一个相容关系，S是关系D下一个相?菁?。 ?欢愿拍罴涞南嗨贫仁侵杆?们共享信息的程度2，因而相异度可以理解为两概念间最小的差异信息程度。由于相异测度中，对于对象i、j总有D(i, i)=0, D(i, j)=D(j, i)成立，相异性是对象间的一种特殊的相容关系。 ?2 设C是对象集S的一个子集，D是S
8、上的一个关系，如果C是关系D下的一个相容集，则称C是关系D下S的一个相容子集。 ?惫叵凳窍嘁於仁保?此时对象集可以看做是一些相容子集的合集。这是因为对象集总能由单个对象构成的单点集的合集构成，而单点集v总是相容的（因为D(v, v)=0）。 ?3 设在关系D下C是对象集S的一个相容子集，如果不存在另一个相容子集C，使得C是C的一个真子集，则C是S的一个极大相容子集。 ?理1 设S是任意一个对象集，D是S上的一个关系，C是关系D下S的一个相容子集，则必存在一个极大相容子集CD，使得 CCD。 ? S=a1,a2,an，构造相容子集系列C0C1?吉?C2?肌?。其中C0=C且Ci+1=Ciaj。其
9、中j满足ajCi，而 aj与Ci中各对象都有相容关系的最小足标。 ?捎诙韵蠹?S所含对象的个数 |S|=n，至多经过 n-|C|步就使这个过程终止，而此序列的最后一个相容子集即为所要找的极大相容子集。 证毕。 ?理2 设S是任意一个对象集，如果在S上定义一个关系D，则存在此关系下S的惟一一个极大相容子集的集合，使得所有这些相容子集的并集等于S。 ? 若在关系D下，对象集S上的每个相容子集都是单点集，则单点集即为S的极大相容子集；若存在相容子集，由定理1必存在包含此相容子集的极大相容子集。设S1,S2,，Sm是关系D下S所有的极大相容子集的集合。如果存在对象aiS但aimk=1Sk，若ai构成相
10、容单点集ai，则ai即为S的一个极大相容子集，这与S1,S2,Sm是关系D下S所有的极大相容子集的集合矛盾；若存在包含ai的一个S的极大相容子集S，则S必属于S1,S2,Sm，这又与aimk=1Sk矛盾。所以关系D下S一定存在极大相容子集的集合，使得所有这些相容子集的并集等于S。 ?绻?关系D下S存在另一极大相容子集的集合S1,S2,Sl且S=mk=1Sk，证明S1，S2，Sm=S1,S2,Sl。 ?环辽?Sj(j1,2,l)为不同于任意Si(i=1,2,m)的任意一极大相容子集， S为Sj与S1,S2,Sm中的Si1,Si2,Sim0的交集，即S=SjSi1=SjSi2=SjSim0。记Sj
11、-S=aj1,aj2,ajr，不妨设aj1Si1，aj2Si2，由于aj1、aj2同属于极大相容子集Sj，aj1aj2S是一相容子集；由于Si1是包含 aj1S的一极大相容子集，aj2Si1,同理可得aj3Si1，ajrSi1，即aj1,aj2,ajrSi1，所以Saj1,aj2,，ajrSi1，即SjSi1，而Sj是S的一极大相容子集,Sj=Si1。这与“不妨设Sj(j1,2,l)为不同于任意Si(i=1,2,m)的任意一极大相容子集”的假设矛盾，从而证明了极大相容子集的集合存在的惟一性。证毕。 3 基于相容关系的聚类 ?缮鲜龆?理2可知，对于任意一个给定的对象集和一关系度量，对象集的每个极
12、大相容子集就是一个基于此关系的对象分组（即对象簇），由此可得到如下基于相容关系的聚类?惴? 3.1 相容关系的聚类算法 ?惴?Comp-clustering ?淙耄?D关系度量；S对象集； 阈值 ?涑觯?SC相容簇 SC=;Cnew= while S do ?xS；Cnewx S=S-x； S(x)=y|D(y,x) and D(x,y),yS； while S(x) do zS(x);Cnewz;S(x)=S(x)-z; S=S-Cnew; while S do if(wS, for all uCnew such that D(w,u) and D(u,w) then Cneww； end
13、if S=S-w; end while S if !CSC, such that CnewC then SCCnew;Cnew=; end if end whileS(x) end whileS return SC ?绫?1所示，给定对象集A, B, C, D, E, F, G的相异度矩阵（其中表示两对象间没有相异度值），阈值取值为1, 2, 3, 4, 5的结果如表2 所示。 3.2 算法的图表示 ?导噬希?给定任一相容集S是可以用有向加权的图G=V, E, W来表示，其中图G中顶点集V的每个点对应S中一个对象，E中每条边e=x, y的权值w表示对象x与对象y之间的关系度量值D(x, y)与
14、D(y, x)中较小的那一个。由此，从对象集S中求每个极大相容子集等价于从相应的图G找最大完全子图。 ?1为表1对应的无向加权图，则聚类结果如图2所示。图2中，加粗的黑线表示公共边，同线型的边代表同一个类族。 4 实验结果与分析 ?了进一步了解Comp-clustering算法的聚类效果，笔者采用一个包含20个数据点的数据集S 20（图3）对新算法进行了聚类效果的实验测试。 4.1 实验设置 ?疚氖笛槠教渲萌缦拢?CPU为Intel Pentium 2.2 GHz，内存为512 MB, 操作系统为Windows XP Professional Edition, 所用代码均用7.0编程实现。 4
15、.2 聚类效果分析 ?了得到较好的聚类效果，首先考察该数据的相异度的频度分布情况，如图4所示。 从图4中可以看出，相异度在0.20.6的数据量保持在70%左右，因此实验时分别选取相异度值 为0.2、0.4、0.6,其聚类效果如图5所示。 ?梢钥闯觯?本文的算法与传统的硬聚类和模糊聚类有明显的不同：Comp-clustering允许同一个对象属于多个簇，这点不同于传统的硬聚类算法；同时，各个簇又都必须有自己独有的对象，这又明显不同于模糊聚类及其变体9。 5 结束语 ?疚奶岢隽艘恢只?于数据对象间关系的聚类算法，并通过实验演示了该算法的聚类效果，进一步表明该算法具有不同于传统算法的聚类效果。新算法对于对象间具有相容关系的对象集的聚类将表现出其可靠的合理性。该新算法在聚类前须指定划分水平，不同的会得到不同的聚类效果。然而在聚类前指定划分水平要比预先指定聚类簇数的传统聚类算法难以操作得多，如何指定一个合适的划分水平尚需要进一步的研究；另外，分层聚类在不同粒度的数据分析方面有着重要的意义，如何构建基于新算法的分层聚类也有待于深入讨论。这些都是下一步需要开展的工作。