用改进的RPCL算法提取聚类的最佳数目.doc

上海大学学报JOURNAL OF SHANGHAI UNIVERSITY1999年 第5卷 第5期 Vol.5 No.5 1999用改进的RPCL算法提取聚类的最佳数目李昕郑宇江芳泽摘要:对于传统的K平均算法来说,如何选择适当类的数目是一个难以解决的问题.有人提出了次胜者受罚的竞争学习(rival penalized competitive learning : RPCL)算法试图来解决这一问题.但是,当数据类有重叠以及输入矢量含有非独立项时,RPCL算法的性能不能令人满意.本文提出了一种结合全协方差矩阵的RPCL算法,并逐步删除那些只包含少量训练数据的类.这种算法,我们称之为改进的RPCL算法.我们用改进的RPCL算法来确定高斯混合分布类的数目,并将其与原来的RPCL进行比较.实验证明,改进的RPCL算法比原来的RPCL算法能够更好地表征类.关键词:聚类;RPCL算法;竞争学习中图分类号:TN 912.34文献标识码:AAn Improved RPCL Algorithm for ClusteringLI XinJIANG Fang-ze(School of Automation, Shanghai University, Shanghai 200072, China);ZHENG Yu(Department of Computer, Shanghai Maritime University, Shanghai 200135, China)Abstract: Selecting an appropriate number of clusters is a problem in the classical K-means algorithm. The rival penalized competitive learning(RPCL) algorithm is designed to solve this problem. But its performance is not satisfactory when the data have overlapped clusters and the input vectors contain dependent components. This paper addresses this problem by incorporating full covariance matrices into the original RPCL algorithm. The resulting algorithm, referred to as the improved RPCL algorithm, progressively eliminates the units whose clusters contain only a small portion of the training data. The improved algorithm is applied to determine the number of clusters of a Gaussian mixture distribution. The results show that the covariance matrices in the improved RPCL algorithm have a better representation of the clusters than those of the original RPCL algorithm.Key words: clustering; RPCL algorithm; competition learning聚类是将多维空间内的数据集合分成多个有意义的子群或类的过程.它在很多领域都有着非常重要的应用,尤其是在语音、图像识别等方面.多年来,人们提出过许多种聚类的方法1,其中最著名的是K平均法,它在每次迭代过程中将对象归入相距中心最近的一类,同时重新计算类的中心.这种方法计算简单、有效,但其缺点是需事先确定类的数目.然而在许多场合,这个数目是未知的.为了解决这一问题,Xu和Krzyzak2提出了一种称为次胜者受罚的竞争学习(rival penalized competitive learning:RPCL)规则,来自动决定类的适当数目.它的基本思想是:对每个输入而言,不仅竞争获胜单元的权值被修正以适应输入值,而且对次胜单元采用惩罚的方法,使之远离输入值.但是,当数据类有重叠时,RPCL算法的性能不能令人满意.在这种情况下,算法对竞争获胜单元及次胜单元的学习率的变化非常敏感.这是因为RPCL算法用欧氏距离(Euclidean distance)来作为距离量度,在输入矢量含有非独立项时对数据集的描述能力变差的缘故.本文提出在RPCL算法中以全协方差矩阵代替对角协方差矩阵的方法,我们称之为改进的RPCL算法.它的优点在于在类互相重叠时以及输入矢量含有非独立项时仍能够找出适当类的数目.1RPCL算法及其改进设x为待聚类集合中的任一元素,每一单元的输出值为i,它的权值矢量为i,i=1,k,RPCL算法由以下四步组成3:第一步:随机初始化权值矢量iki=1并设t=1.第二步:从数据集中随机选择样本x,从i=1,k,使(1)这里,c表示获胜单元,r表示次胜单元,这里是i=1的次数.第三步:由下式修改权值矢量i,(2)这里,0c(t),r(t)1分别是竞争获胜单元和次胜单元的学习率.第四步:t值加1,如果t时,将单元i删除,由所剩下单元组成的权值矢量作为类的中心.这样,通过RPCL算法可以自动地确定一个适当类的数目.但是,当类互相重叠时,它的性能会很快下降,这是因为在这种情况下,算法对竞争获胜单元和次胜单元的学习率非常敏感.而当输入矢量包含非独立项时,问题会更严重.我们认为,之所以出现这种情况,是因为用欧氏距离作为RPCL算法中的距离量度并非好的选择.我们提出用一组协方差矩阵jkj=1来作为距离量度,这样,式(2)中的欧氏距离就被马氏距离(Mahalanobis distance:(x-j)T-1j(x-j)所代替.需要指出的是,当jkj=1是单位矩阵时,改进的RPCL算法就简化为原来的RPCL算法.改进的RPCL算法开始时要在竞争学习网络中选择一个大的单元数目,这个数目应该大于输入数据集中预计的类的数目.每次迭代之后,我们要测定每个类中包含的样本数,然后将只含有少量样本的单元删除.这是因为这些单元中包含的样本数太少,不能可靠地估计出协方差矩阵.我们称之为“冗余单元”.改进的RPCL算法的步骤如下:第一步:设定类的中心数目初始值,这个值应大于数据集中的可能类的数目.用K邻近算法初始化矩阵jkj=1,同时设定删除冗余单元的阈值.将计数器p值设为零.第二步:设计数器t=0,从数据集中随机选取样本x.从i=1,k,使(3)这里,c表示获胜单元,r表示次胜单元,i值的计算与RPCL算法相同.(b) 按式(2)修改权值j.(c) t值加1,如果tT,则转第二步(a);否则转第三步.第三步:对每一个样本,找出它最近的中心,然后将它分配到相关的类中.第四步:对每一个类,测定它包含的样本数.如果该数与总的样本数之比低于阈值,则将该中心(单元)删除.第五步:对单元删除以后的中心数目k进行修改,如果k不变(即没有单元被删除),则p=p+1.第六步:如p=2,终止;否则,转第二步.2实验及结果在这个实验中,我们用4个互相重叠的高斯类,每个类包含100个样本.这4个高斯分布的协方差矩阵为(0.9,0.2,0.2,0.6),(0.7,0.0,0.0,0.7),(0.5,-0.2,-0.2,1.0)和(0.7,0.1,0.1,0.5),均值矢量为(-1.0,1.0),(1.0,-1.0),(-1.0,-1.0)和(1.0,1.0)(见图1(a).我们设定学习率c和r分别为0.006和0.0004,阈值设为0.1.我们用均值和协方差矩阵分别等于(5.0,5.0)和(2.0,0.0,0.0,2.0)的高斯分布来随机初始化权值矢量.(a) 样本的分布(b) 由原来的RPCL算法确定的中心(c) 由改进的RPCL算法确定的中心图1训练样本的分布及不同RPCL算法所确定的中心数Fig.1The training samples and centers identified by the original and the improved RPCL algorithm将初始单元数分别设为4、5和10,分别运行原来的RPCL算法和改进的RPCL算法100次.表1和表2列出了由原来的RPCL算法和改进的RPCL算法所确定的中心数目的频率分布.结果显示,当起始中心数为4、5和10时,改进的RPCL算法成功地确定中心数为4的比率分别为77%、41%和48%.而相同情况下由原来的RPCL算法确定中心数为4的比率分别为12%、31%和4%.由改进的RPCL算法可以根据中心数的频率分布准确地定出正确的中心数目,而原来的RPCL算法则不行(表格中粗体所对应的中心位置为最后确定的中心数目).表1由原来的RPCL算法所确定的中心数的频率分布(100次)Tab.1Frequency distributions (based on 100 runs) of the number of centers identified by the original RPCL algorithm初始的中心数目最后的中心数目123456789104048412-50069310-100004553110000表2由改进的RPCL算法所确定的中心数的频率分布(100次)Tab.2Frequency distributions (based on 100 runs) of the number of centers identified by the improved RPCL algorithm初始的中心数目最后的中心数目123456789104012277-58984134-100315483130000图1(b)和1(c)展示了由RPCL算法和改进的RPCL算法确定的中心情况.很明显,由改进的RPCL算法所确定的中心很靠近实际的4个类的矩心,而原来的RPCL算法则丢失了一个类.同时也可由协方差矩阵所形成的等潜线(图中的圆和椭圆)看出,改进的RPCL算法的全协方差矩阵比原来的RPCL算法的对角协方差矩阵具有更好的训练数据的映射能力.当每个类中的样本数增加到500时(见图2(a),就可获得如表3和表4中所列出的结果.结果显示,当起始中心数为4、5和10时,改进的RPCL算法成功地确定中心数为4的比率分别为86%、45%和42%,而原来的RPCL算法确定中心数为4的比率分别为3%、29%和6%.(a) 样本的分布(b) 由原来的RPCL算法确定的中心(c) 由改进的RPCL算法确定的中心图2训练样本的分布及不同RPCL算法所确定的中心数Fig.2The training samples and centers identified by the original and the improved RPCL algorithm表3由原来的RPCL算法所确定的中心数的频率分布(100次)Tab.3Frequency distributions (based on 100 runs) of the number of centers identified by the original RPCL algorithm初始的中心数目最后的中心数目12345678910400973-50070291-100006483015100表4由改进的RPCL算法所确定的中心数的频率分布(100次)Tab.4Frequency distributions (based on 100 runs) of the number of centers identified by the improved RPCL algorithm初始的中心数目最后的中心数目123456789104311086-543124536-1011104232121100图2(b)和图2(c)展示了由RPCL算法和改进的RPCL算法确定的中心情况.其结果与图1中的结果类似. 在另一实验中,我们用3个高斯分布类,每个类包含500个样本.3个高斯分布的协方差矩阵分别为(0.5,0.2,0.2,0.3),(0.3,0.0,0.0,0.3)和(0.5,-0.2,-0.2,1.0),均值矢量为(-1.0,1.0),(0.0,-1.0)和(1.0,-1.0).和上次实验一样,设学习率c=0.006,r=0.0004,并设阈值为0.1.结果如表5和表6.表5由原来的RPCL算法所确定的中心数的频率分布(100次)Tab.5Frequency distributions (based on 100 runs) of the number of centers identified by the original RPCL algorithm初始的中心数目最后的中心数目12345678910307822-50089110-1000792100000表6由改进的RPCL算法所确定的中心数的频率分布(100次)Tab.6Frequency distributions (based on 100 runs) of the number of centers identified by the improved RPCL algorithm初始的中心数目最后的中心数目12345678910384349-511265814-101122612400000图3(b)和图3(c)展示了由原来的RPCL算法和改进的RPCL算法确定的中心情况.可以看出,即使原来的RPCL算法能成功地确定中心数为3,它所确定的中心位置也不如改进的RPCL算法所确定的那么准确.这主要是因为欧氏量度的限制所决定的. (a) 样本的分布(b) 由原来的RPCL算法确定的中心(c) 由改进的RPCL算法确定的中心图3训练样本的分布及不同RPCL算法所确定的中心数Fig.3The training samples and centers identified by the original and the improved RPCL algorithm3结论对于传统的K平均算法而言,选择适当的类的数目是一个难以解决的问题.次胜者受罚的竞争学习(RPCL)算法试图解决这一问题,但是,当数据集有类重叠时,它的性能不能令人满意.