摘 要： 针对K-Modes算法的不足，提出了一种基于信任值的分类属性聚类算法TrustCCluster，该算法不需预先给定聚类个数，聚类结果稳定且不依赖于初始值的选取。在真实数据上验证了TrustCCluster聚类算法，并与K-Modes和P-Modes算法进行了对比，实验结果表明TrustCCluster算法是有效、可行的。
关键词： 信任值；聚类；K-Modes算法；P-Modes算法
聚类分析是一种非常重要的数据挖掘技术,已经被广泛应用于网络入侵检测、模式识别、图像处理、空间数据分析等领域。传统聚类算法可以分为基于划分的方法(如K-Means)[1]、基于层次的方法(如AGNES)[2]、基于密度的方法(如DBSCAN)[3]、基于网格的方法(如STING)[4]、基于模型的方法(如SOM)[5]等。
K-Means算法是一种基于划分的典型算法，具有描述容易、实现简单且快速等优点。但K-Means算法只能处理数值属性。为克服这一局限，Huang等人提出了一种适合于处理分类属性数据的K-Modes算法[6-7]。该算法对于每个分类属性采用取值频度最大的属性值——模(mode)来表示类的对应“中心”，但这种表示难以准确反映类中对象的取值情况,导致距离计算不准确,并且当某个属性取值频度最大的属性值多于一个时，mode值不唯一。P-Modes算法[8]基于粗糙集理论，提出了一种新的距离度量方法，该距离度量在度量同一分类属性下两个属性值之间的差异时,克服了简单0-1匹配差异法的不足，既考虑了它们本身的异同，又考虑了其他相关分类属性对它们的区分性。
K-Modes、P-Modes算法都是在K-Means算法基础上产生的一种针对分类属性的距离度量方法，和K-Means算法一样存在以下几点不足：(1)需要预先给定聚类个数K；(2)算法对初始值的选取依赖性极大；(3)算法容易陷入局部最优解。针对以上算法的不足，结合P-Modes的度量方法本文提出了一种基于信任值的分类属性聚类算法TrustCCluster，该算法无需预先给定聚类个数，聚类结果稳定，不依赖于初始值的选取，具有更高的聚类精度。
1.2 算法描述
TrustCCluster算法具体步骤如下：
(1)计算信任值
所有数据点信任值初始值为0，遍历数据集中所有数据点，若任意两个数据点xi、xj(1≤i，j≤n)的距离d(xi，xj)<半径阀值R，则xi、xj的信任值都加1，否则不变。
(2)按信任值大小对所有数据点进行降序排序
(3)聚类形成簇
①i=1(i为数据点的序号)；
②若xi未被访问过，则xi作为新生成簇Cluster的中心,否则转步骤⑥；
③j=i；
④如果d(xi，xj)<R且xj未被访问过，则将xj加到簇Cluster中并将xj标记为已访问过；
⑤j加1，若j≤n，转步骤④；
⑥i加1，若i≤n，转步骤②；
⑦结束。
如图1所示，在半径阀值为R时，形成了3个簇，簇1的中心是信任值为4的点，一共包含5个点，簇2中心是信任值为3的点，包含3个点（不包括相交部分的点），簇3只包含1个点。
(4)合并簇
假设步骤(3)中，聚类形成M个簇。对于生成的M个簇，如果任意两个簇Clusteri、Clusterj的共享信任值Share≥(Clusteri.sonNum+Clusterj.sonNum)×Q，sonNum为簇的成员数即簇包含的数据点数，Q为给定的比例阈值，0<Q≤1，则这两个簇合并形成新的簇。可知簇合并关系R’是自反、对称、传递的，最终形成的簇是关系R’对M个簇的一个等价划分。
如图1所示，如果Q≤1/（5+3）=0.125，则簇1和簇2会合并成一个新的簇。
(5)输出聚类结果
算法代码如下：
//Step 1计算信任值
for(i=1；i<n；i++)
for(j=i+1；j≤n；j++)
{
if(d(xi，xj)<R)
{
xi.trust++；
xj.trust++；
}
}
//Step 2按信任值排序
sort(dataSet)；
//Step 3聚类形成簇
for(i=1；i≤n；i++)
{
if(visit[i] == false)
{
for(j=i；j≤n；j++)
{ //找出生成簇的成员
//判断xj和簇clusterNum中心的距离是否<R
if(!visit[j]&& d(clusterNum,xj)<R)
{
Cluster[clusterNum].sonNum++；
visit[j]=true；
}
visit[i] = true;
}
}
}
// Step 4合并簇
for(i=1; i≤clusterNum; i++)
for(j=i+1; j≤clusterNum;j++)
{ //Matrix[M][M]为关联矩阵，所有元素初始值为0
if(Share>=(Cluster[i].sonNum+ Cluster[j].sonNum)*Q)
{//共享信任值Share≥阀值，则关联矩阵的项为1
Matrix[i][j]=1；
Matrix[j][i]=1；
}
}
DFSMergeCluster();//DFS搜索求无向图连通分量，
即进行簇合并
1.3 算法分析
(1)TrustCCluster算法需要设定两个参数：半径阈值R和比例阈值Q。虽然TrustCCluster算法比K-Modes算法多了一个参数，却可以在预先不知道聚类个数K的情况下进行聚类。
(2)算法求出所有数据的信任值并排序，参数确定后，聚类结果也就确定，与初始数据点的选取顺序无关。
(3)信任值越大，表明数据点中心作用越大。算法求出所有数据的信任值并按信任值从大到小进行排序，聚类结果具有全局性。
(4)算法的步骤(3)中只能发现一些近似球形的小簇，但在步骤(4)中进行的簇合并操作，可形成非球形的大簇。
(5)时间复杂度分析。
算法首先根据定义2、3计算所有属性(假设第k个属性)下任意两个属性值之间的距离d(xik，xjk)，然后将其值存到数组DisAttr[k][i][j]中，以便计算距离d(xi，xj)时使用。计算距离d(xi，xj)的时间复杂度为O(Psn+Ps2n+P2s3n)=O((Ps+Ps2+P2s3)n)，s=max|Vl|，1≤l≤P。由于对于大数据集n>>s，n>>P，所以复杂度是线性O(n)的。
步骤(1)中计算信任值的时间复杂度为O(n(n-1)/2)，步骤(2)如果采用快速排序，则时间复杂度为O(nlgn)，步骤(3)聚类形成簇的时间复杂度为O(n(n+1)/2)，步骤(4)合并簇的时间复杂度为O(m2)，m为步骤(3)中生成的簇的个数(n>>m)。
所以TrustCCluster算法的时间复杂度为O(n2)。
2 实验结果
为了验证本文算法的有效性，在UCIMachine Learning Repository 提供的Soybean和Congressional Vote数据集上进行了测试，并与K-Modes 、P-Modes算法进行了对比，结果表明本文算法聚精度更高。实验所用编程环境为VC++6.0。
为比较聚类结果，定义聚类精度r：
Congressional Votes数据集记录了美国国会1984年435个国会议员的投票情况。每条记录为一个议员在16个属性上的表决情况,并有一个分类标志Republican或Democrat，用以表明对应的议员所属党派。每条记录由16个属性描述，每个属性仅取3个值(y表示同意，n表示不同意，?表示不表态)。TrustCCluster在4/5E≤R≤5/4E，3/5T≤Q≤3/2T时随机运行100次。K-Modes、P-Modes算法的初始聚类个数为K=3，初始点随机选取，运行100次。三种算法聚类结果比较如表2所示。可以看出在适当参数下，TrustCCluster算法最大聚类精度和平均聚类精度都要高于另外两种算法。
本文提出了一种基于信任值的分类属性聚类算法TrustCCluster，相对于K-Modes、P-Modes，TrustCCluster 算法具有如下优点：不需预先给定聚类个数；聚类结果不依赖于初始值的选取；可以发现非球形的簇；聚类精度更高。
TrustCCluster算法的时间复杂度为O(n2)，不适合大规模数据的聚类，只支持分类属性数据。如何使TrustCCluster算法应用于大规模数据的聚类，并且能处理混合型数据，以及更合理地选择参数R和Q是需进一步研究的问题。
参考文献
[1] MACQUEEN J.Some methods for classification and analysis of multivariate observations[C].Proc 5th Berkeley Symposium Mathematics Statist and Probaility，1967：281-297.
[2] KAUFMAN J，ROUSSEEUW P J.Finding groups in data：an introduction to cluster analysis[M].New York：John Wiley&Sons，1990.
[3] ESTER M，KRIEGEL H P，SANDER J，et al.A density-based algorithm for discovering clusters in large spatial databases[C].Proc.of 1996 Intl.Conf.on Knowledge Discovery and Data Mining，Portland，OR.1996：226-231.
[4] WANG W，YANG J，MUNTZ R.STING：A statistical information grid approach to spatial data mining[C].Proc of 1997 Intl.Conf.on Very Large Databases，Athens，Greece. 1997：186-195.
[5] KOHONEN T.Self-organized formation of topologically correct feature maps[J].Biological Cybernetics，1982，43(1)：59-69.
[6] Huang Zhexue.Clustering large data sets with mixed numeric and categorical values[C].Proc of PAKDD 97.Singapore：World Scientific，1997：21-35.
[7] Huang Zhexue.Extensions to the K-means algorithm for clustering large data sets with categorical values[J].Data Mining and Knowledge Discovery，1998，2(3)：283-304.
[8] 梁吉业，白亮，曹付元.基于新的距离度量的K-Modes聚类算法[J].计算机研究与发展，2010，47(10)：1749-1755.