可区分惩罚控制竞争学习算法.docx

《可区分惩罚控制竞争学习算法.docx》由会员分享，可在线阅读，更多相关《可区分惩罚控制竞争学习算法.docx（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第 27 卷 第 5 期模式识别与人工智能Vol 27 No 52014 年 5 月P AIMay2014可区分惩罚控制竞争学习算法*张锋赵杰煜朱绍军( 宁波大学 信息科学与工程学院 宁波 315211)摘 要 竞争学习在聚类分析中是一种重要的学习方式，次胜者惩罚竞争学习( PCL) 算法虽能自动选择合理的 类别数，但其性能对学习率和惩罚率的取值较敏感，其变种惩罚控制竞争学习( PCCL) 算法将所有的竞争单元当 成冗余单元进行惩罚也不合理 文中提出一种可区分惩罚控制竞争学习算法( DPCCL) 算法中获胜单元的学习率 会在迭代过程中自适应调整 同时该算法使用一种可区分惩罚控制机制来区分竞争单

2、元中的冗余单元和正确单 元，给予冗余单元较重惩罚，正确单元轻微惩罚，使得算法能自动确定正确类别数和中心点位置 最后通过实验对 比分析证明 DPCCL 算法的聚类效果比 PCL 算法和 PCCL 算法更准确关键词 聚类分析，竞争，胜者惩罚竞争学习( PCL) ，可区分的惩罚控制机制 中图法分类号 TP 181Discriminative ival Penalization Controlled Competitive Learning AlgorithmZHANG Feng，ZHAO Jie-Yu，ZHU Shao-Jun( College of Information Science and

3、Engineering，Ningbo University，Ningbo 315211)ABSTACTCompetitive learning is an important approach for clustering analysis The rival penalized competitive learning ( PCL) algorithm has the ability of selecting the correct number of clusters automatically，but its performance is sensitive to the selecti

4、on of learning rate and de-learning rate In fact， it is unreasonable that all the rival units are treated as redundant units to be penalized in the variant algorithm called rival penalization controlled competitive learning ( PCCL) In this paper，a discriminative rival penalization controlled competi

5、tive learning ( DPCCL) is presented The learning rate of winning units adaptively adjusts during iteration in the proposed method Meanwhile，a discriminative penalization controlled mechanism is used to discriminate the redundant units and the correct units in the rival units The correct units and re

6、dundant units are given a slight penalization and a heavier penalization respectively，which makes this algorithm get exact number of clusters and reasonable centre of clusters The experimental result demonstrates that compared with PCL and PCCL，DPCCL achieves more accurate performance* 国家自然科学基金项目(No

7、 61175026)、国家“十二五”科技支撑计划项目(No 2012BAF12B11)、科技部国际科技合作专项项目 (No 2013DFG12810)、浙江省自然科学基金重大项目(No D1080807)、浙江省国际科技合作专项项目(No 2013C24027)资助 收稿日期:2013 07 19;修回日期:2014 10 21作者简介 张锋( 通讯作者) ，男，1988 年生，硕士研究生，主要研究方向为模式识别、图形图像技术 zhang431705 sina com 赵杰煜，男，1965 年生，教授，博士生导师，主要研究方向为机器学习、计算机视觉 朱绍军，男，1984 年生，博士研 究生，主

8、要研究方向为模式识别、机器学习5 期张 锋 等:可区分惩罚控制竞争学习算法427Key WordsCluster Analysis，Competitive Learning，ival Penalized Competitive Learning( PCL)，Discriminative Penalization Controlled Mechanism1引言竞争学习( Competitive Learning) 作为机器学习法(ival Penalization Controlled Competitive Learning， PCCL)17，该算法在 PCL 的基础上引入竞争单 元的惩罚控制

9、机制来解决惩罚率的选取问题，它在中的一种非监督学习方法，在许多领域中被广泛使彩色图像分割18中也取得较好的效果 Ma 等19通用，如向量量化1、自组织映射2等，特别是在聚类 分析中，竞争学习是一种有效的学习方式3 4竞争学习通常会遇到死单元问题:只有获胜单 元才会进行权值调整，其他单元不会调整，这样会使 某些单元始终得不到更新机会而成为死单元5 解 决此类问题可通过减少获胜次数较多的单元学习 率，使其他单元有机会得到更新6，即后来的良知策 略7 频率敏感竞争学习算法( Frequency Sensitive Competitive Learning，FSCL)8是在良知策略基础上 研究出来的

10、在给定真实类别数的情况下，FSCL 算 法可获得较好的聚类效果无监督学习中，类别数的选择对聚类效果影响 较大 为解决类别数选取问题，在 FSCL 算法的基础 上，徐雷等9提出次胜者惩罚竞争学习算法 ( ival Penalized Competitive Learning，PCL) ，该算法在节 点更新中添加一种对竞争单元的惩罚机制:对于每 个输入样本，不仅要调整获胜单元的权值向量，而且 要将竞争单元的权值向量用一个较小的参数进行惩 罚( 下文均将该参数称为惩罚率) ，将其驱离数据区 域，从而使算法有自动确定类别数的能力 这种自动 确定类别数的能力被用于 Markov 模型估计状态序 列和模型

11、参数，使 Markov 模型能自动决定正确的状 态数10以及图像处理和模式识别中的带状线检测 和细化问题11贝叶斯阴阳和谐学习理论( Bayesian Yin-Yang， BYY) 不仅可用于参数估计，而且可用来解决混合模 型中密度函数个数选择问题，类别数的确定类似于 混合高斯模型中模型个数的确定 因此 PCL 算法 的类别个数选择能力可理解为贝叶斯阴阳和谐学习 理论的模型个数选择能力12 近年来，将贝叶斯阴 阳和谐学习理论用于自动确定模型数的研究较为广 泛13 15PCL 算法虽能自动确定类别数，但仍然存在 一些问题16:1) 算法中学习率和惩罚率的取值都要 依赖经验值，缺乏对这两个参数的适

12、当控制;2 ) 算 法收敛性缺少数学理论上的证明随后研究人员提出次胜者惩罚控制竞争学习算过构造代价函数求导分析，对 PCL 算法的收敛性进行理论证明但 PCL 及其变种 PCCL 中存在的一个共同 缺点是算法中学习率总设为一个固定的常数 根据 随机梯度下降算法20 21，合理的取值方式应该随着 迭代过程不断改变 PCCL 算法引入的惩罚控制机 制将所有的竞争单元看作冗余单元进行惩罚，这种 方式过于武断 因此本文提出一种可区分惩罚控制 竞 争 学 习 算 法 ( Discriminative ival Penalization Controlled Competitive Learning，DP

13、CCL) :1) 根据随机梯度下降算法在线更新方式，将学 习率从设为固定值的方式改为自适应调整，使得获 胜单元的学习率随着获胜次数增多而减小，可让正 确单元更易趋近真正的中心位置;2) 提出一种可区分惩罚控制机制 将竞争单元 中的冗余单元和正确单元区分对待，使正确单元受 到轻微惩罚，减少错罚的影响，使冗余单元受到较重 惩罚而远离数据区域，以此得到正确类别数2 PCL 和 PCCL 的优缺点2 1 PCL 算法PCL 算法的基本思想如下: 假定有来自 K 个 类的 n 个样本x1 ，x2 ，xn ，其中每个样本都是 p 维的数据 从样本集中随机选定 k 个样本作为种子 单元 m1 ，m2 ，mk

14、 ，每个单元 mi 是一个 p 维的矢量 在算法开始时，从数据集中随机选取 k 个样本作为初始种子单元，对于每个输入样本 xt ，都要计算 其到每个种子单元的距离，距离最近的单元即为获 胜单元，距离次近的被当作竞争单元 距离度量使用 欧氏距离，文中所涉及的距离都将使用欧氏距离PCL 算法不仅要更新与样本距离最近的获胜单元的权矢量 mc ，使获胜单元向样本靠近，而且要以一 个比学习率更小的惩罚率来调整竞争单元的权矢量 mr ，使其逐渐远离输入样本算法 1 PCL 算法428模式识别与人工智能27 卷step 1随机从样本集 x1 ，x2 ，xn 中选择 一个样本 xt ，计算该样本到各单元的输出

15、 ui 如下:( xt ;mc ，mr ) =min(mr mc ，xt mc )，mr mc ui =21，c = i，c xt mc 2 1， r = j，r xt mr k2= minj xt mj j = 1k2= min j xt mj j = 1，jc(2)其中，使用欧氏距离来度量它们之间的距离 实际 上，式(2) 中的分子通常是小于等于分母的，因此( xt ;mc ，mr ) 的取值在 0 到 1 之间 整个 PCCL 算 法过程如下0，其他其中，njj =k，(1)算法 2PCCL 算法step 1从样本集中随机选取一个样本 xt ，根据 式(1) 计算得到获胜单元 mc 和竞

16、争单元 mr step 2根据下面的公式更新获胜单元 mc 和竞 争单元 mr :njj = 1mc= c ( xt mc )，mc 为获胜单元，mr 为竞争单元，nj 表示第 j 个种子单mr = c ( xt ;mc ，mr )( xt mr )元在前面输入的所有样本中获胜的累积次数，j 表 示第 j 个种子单元的获胜频率step 2调整获胜单元和竞争单元的权矢量，= cmr )min(mr mc ，xt mc )(xtmr mc 其他单元的权矢量不变对于每个输入样本都执行这两个迭代步骤直到nnewold满足预先设定的停止条件c= nc + 1，虽然 PCCL 算法用这种惩罚机制回避惩罚率

17、mnewoldi= mi+ mi ，c ( xt mi )，i = c的选取，但算法中学习率 c仍设为固定值 因此，本mi = r ( xt mi )，i = r文对学习率取值方式进行改进，使其能自适应调整通过研究发现PCCL算法的惩罚控制机制也存在其中，c 是获胜单元学习率，r 是竞争单元的惩罚 率，其中 0 r c 1 对所有输入样本，反复执行以上步骤，直到满足预先设定的迭代次数，算法停 止运行根据算法可知，每个类只会将最近的种子单元 吸引向类中心，并阻止其他较近的种子单元靠近该类中心 因此，PCL 算法能够自动确定数据集的类 别数然而，PCL 算法中的学习率和惩罚率是需要 靠先验值来确定

18、的，选取不当就得不到正确的类别数 对于不同的问题，先验值要经过反复的试验才能得到，且耗时太长，也较大地限制了 PCL 算法的适 用性 因此 Cheung17 提出 PCCL 算法来解决竞争问题，竞争单元全部被当成冗余单元进行惩罚，这种 方式太武断，因为竞争单元既可能是其他某类的正 确中心单元，也可能是要驱离的冗余单元，而冗余单 元受到的惩罚强度理应比其他正确中心单元受到的惩罚强度更大3 可区分的惩罚控制竞争学习3 1 学习率自适应调整在 K-Means 算法中，给定一个样本集 P = xi ，i = 1，2，n 为了计算出 k 个中心点，可通过最小化量化误差( 样本和中心单元之间平均距离) 来

19、实 现，如下式:defdef 1 2单元惩罚率的选取问题E( ) L( xi ，) min( xi k ) 2 2PCCL 算法该算法的惩罚控制机制为给定的一个输入 xt ，ii2k将离样本 xi 最近中心点的下标表示为 Si ()，得这里用函数 f 表示两者之间的欧氏距离 当 f( mr ，E( ) = i 1 ( x ) 2 ，2iSi( )mc ) f( xt ，mc ) 时，则认定这种情况为获胜单元和竞争单元间的竞争激烈，此时竞争单元受到的全额 惩罚为 r = c 当 f( mr ，mc ) f( xt ，mc ) 时，竞争单 元受到的惩罚随着 f( mr ，mc ) 距离的增加而减小

20、，该惩罚控制机制表示为r = c ( xt ;mc ，mr )，其中，Si ( ) = 1，2，k根据梯度下降算法得到在线更新算法为L( xi ，) = t，t ( xt k )， 若 k = Si ( )k =0，其他5 期张 锋 等:可区分惩罚控制竞争学习算法4292通常，t 需满足t = !，t收敛21 22 !才能保证率 c 等值的全额惩罚，落在圈外的竞争单元受到的 惩罚强度与其到获胜单元的远近程度成比例，如图ii最大期望 ( Expectation Maximization，EM) 算 法是通过引入一个隐变量使优化问题更简单，因此 可在 K-Means 算法中引入一个隐变量，然后使用

21、 EM 算法进行优化21 其中隐变量 S ( ) 表示样本 x 所属类别的标签，Si ( ) = 1，2，k 通常，EM 所求的是隐变量在其分布上的期望值 而这里只对使代价 函数最小的隐变量值感兴趣，即在当前 值已知的 条件下，求出使 Q( ，) 最小化的下一个新值 ， 如此反复迭代，直到找到一个最优的 使 Q( ，)1( a) 所示 然而竞争单元 mr 可能没有落在该圆内，而是落在样本 xt 右边的 mr 处，根据式(2) 会使该竞 争单元受到的惩罚强度因为 mr mc 较大而比 应受惩罚强度减小近一半 这样可能无法使竞争单 元远离数据样本因此将该惩罚控制机制直接改为以样本为圆心，mc xt

22、 为半径的圆作为惩罚区域，直接使用获胜 单元、竞争单元分别到样本的欧氏距离的比值x m 22Disatio =tc 全局最小，即def 12xt mr 来度量它们之间的竞争程度，通常竞争单元不会落Q( ，) i( xi S ( ) ) ，2i在圆内区域，因此 Disatio 取值区间为(0，1，如图其中， 是当前参数值， 是要求的新值，通过求导Q( ，) / k = 0，得 1 1( b) 所示k = Nk i:k = Si( )xi ，(3)其中，Nk 表示分配给 k 的样本个数 k = Si ( ) 表示样本 xi 所属的类别标签根据式(3) ，可在 K-Means 算法中相应引入一 个变

23、量 nk 来表示当前分配给 k 的样本个数，在线更 新算法相应变为kn = 1， 当 k = s( xi ，)0， 其他( a) PCCL( b) DPCCL图 1对应 PCCL 和 DPCCL 的惩罚控制机制ikiFig 1Penalization controlled mechanisms corresponding ( 1 x )， 当 k = s( x ，)nk =k0，其他其中，s( xi ，) 表示当前样本 xi 所属的类别该算法相当于一个指定学习率为 1 / nk 的在线梯度下降算法 本文将其引入以取代原来的学习率 取值为某个固定值的方式，同时为防止算法开始时 学习率过大，在分母

24、中加入一个常数项: 1 to PCCL and DPCCL当获胜单元距离竞争单元较近时，竞争单元应受到较重惩罚，而此时由于这两个单元到样本的距 离相差不大，距离比值 Disatio 也会较大;当这两个 单元分别在样本两侧且到样本距离相近时，竞争单元受到的惩罚力度也应较 大，而此时距离比值 Disatio 也较大 因此可使用距离比值 Disatio 来反nc =c+ const 映获胜单元和竞争单元之间的竞争程度为对比方便，本文初始学习率与 PCCL 算法实 验中学习率取值一 致，因 此 将 常 数 项 const 设 为 1 000，那么初始学习率为 0 001 在算法迭代过程 中，随着获胜次

25、数增加，该种子单元的学习率逐渐减小，种子点向中心位置移动的距离越来越小，这样可 使种子单元更易找到正确的类别中心位置3 2可区分的惩罚控制机制在 PCCL 算法中，惩罚控制机制可看作是以 mc 为圆心，mc xt 为半径的圆作为完全惩罚区 域，只有落在该区域内的竞争单元才会受到与学习此外，发现 PCCL 算法中将竞争单元完全作为冗余单元进行惩罚也不合理，因为与获胜单元竞争 的可能是其他某类的正确单元，若对这样的竞争单元的施加惩罚强度太大，会使它们偏离中心位置 在 PCCL17 算法中，竞争单元的更新学习公式为mr = mr r ( xt ;mc ，mr )( xt mr ) 相比原来 PCL

26、算法将参数 r 设为某个常数，PCCL 将惩罚方式改为 r = c ( xt ;mc ，mr ) ，通过( xt ;mc ，mr ) 的变化来控制施加给竞争单元的惩罚430模式识别与人工智能27 卷力度 这样虽然可以根据距离来动态调整惩罚力度，mj 越小，表示两者越接近，相应的表示似然函数2但是也不够全面 距离只能度量两个单元的远近程度，无法判断与获胜单元竞争的是位于其他类中的 正确单元，还是该类边缘处的一个冗余单元 例如，人类社会关系中，不能仅根据一个人当前的表现来 决定其品格好坏，还要考虑其过去的行为表现，这样才不至于因为一时疏忽给将来造成损失 因此，判断一个竞争单元是否可能成为某个类的正

27、确中心单元 也要考虑其前期的表现因为样本是随机抽取的，样本越密集的区域中P( x j ) 也越大 选择乘积最小的作为获胜单元等同于选择后验概率最大的作为决策 对于区分竞争单元中的正确单元和冗余单元问题，可将其看成贝叶斯两类分类问题来分析两种判 决带来的风险损失，选择风险损失较小的作为判决 结果假定有一个竞争单元 m，现在要判断其是正确 单元还是冗余单元 其中，( 1 m) 表示竞争单元被抽取到的次数越多 竞争单元获胜次数越多，前期判决为正确单元时的条件风险，( 2m) 表示竞争获得学习的次数也越多，越靠近吸引它的样本密集 区域，学习程度越大，最后趋于成熟，移动到中心位置，成为正确中心单元 因此

28、竞争单元的获胜次数能 间接反映出它自身的前期表现，这种信息可成为区 分出冗余单元和正确单元的辅助信息根据贝叶斯决策理论，为使总风险最小化，每次 都要选择一个使风险最小化的决策 同样，在对竞争 单元进行惩罚时，也要选择一个风险最小的惩罚力度，保留趋向正确的种子单元，消除趋向冗余的种子 单元，让数据模型组织结构更加简单，使算法执行效率更高 而在 PCCL 算法中做此决策时仅依靠距离 关系 ( xt ;mc ，mr ) 的变化来决定惩罚力度太牵强，单元判决为冗余单元时的条件风险 根据贝叶斯风险决策，可得( 1 m) = 11 P( 1 m) + 12 P( 2 m)，(5)( 2 m) = 21 P

29、( 1 m) + 22 P( 2 m)，(6) 其中，行为 1 对应于判决为 1 ( 正确单元) ，行为 2 对应于判决为 2 ( 冗余单元) ij = ( i j ) 表示当实际类别为 j 时误判为 i 所引起的损失 将上面两个等式相减可得( 2 m) ( 1 m) =( 21 11 ) P( 1 m) ( 12 22 ) P( 2 m) 为计算简单，设定 11 = 22 ，12 = 21 当竞争 单元的获胜次数较多时，根据式(4) 有 P( 1 m) 存在将正确单元错判成冗余单元的风险 这种风险P( 2 m) ，得到 ( 2m) ( 1m) ，因此判决会导致正确单元也遭受与冗余单元一样的惩

30、罚，使正确单元徘徊在所在类的中心周围而无法逼近 因此，为使错判风险最小化，降低错判造成的聚类结果不理想，应将可能是其他类的中心单元的竞 争单元保留下来 但不可能每个竞争单元都会成为 其他类的中心单元，因此就必须从竞争单元中找出 有可能成为其他类中心单元的正确单元在贝叶斯理论中，贝叶斯分类并不把一个对象 绝对地指派给某一类，而是通过计算得出属于某一类的概率，将具有最大概率的类作为该对象所属的 类 其中贝叶斯后验概率公式如下:P( x j ) P( j )为 1 ，即将获胜次数较多的竞争单元判决为正确单 元所产生的风险更小基于贝叶斯决策理论的最小化风险考虑，本文 提出一种可区分的惩罚控制机制，以区

31、分竞争单元 中的正确单元和冗余单元，并分别给予对应的惩罚强度 将获胜次数多的竞争单元判决为正确单元，施加一个微弱的惩罚，使其保留下来作为待定中心单 元进行学习;将获胜次数较少的竞争单元判决为冗 余单元，施加一个相对较强的惩罚，让其远离样本，慢慢消亡 综合考虑上述因素，最后将 PCCL 算法中惩罚控制修改为P( j x) =，(4)P( x) = Disatio，其中，分母 P( x) 是用来保证各类别的后验概率总和为 1，因此可把 P( x) 仅看成一个标量因子 那么 后验概率主要是由先验概率和似然函数的乘积所决其中， =1，nr + const定 同理，可将对该类样本获胜概率最大的种子单元

32、作为该类的中心单元Disatio =xt mc ，2trx m 2根据贝叶斯理论，对式(1) 可理解为 j 表示第 j个种子单元在当前时刻前的累积获胜概率，因此可 将 j 作为先验概率;样本和种子单元的距离 xt nr 表示竞争单元获胜的次数，const 用以设置初始学 习率大小相比 PCL 算法和 PCCL 算法中让所有竞争5 期张 锋 等:可区分惩罚控制竞争学习算法431单元的惩罚率 r 为同一个值，这样的好处是可根据 各个单元在每次迭代过程中的学习程度决定其作为 竞争单元时受到的惩罚强度大小，减少人工设定的 干预，使竞争更自由 种子单元获胜次数越多，代表前面学习的样本数越多，学习程度越大

33、，越会陷入样 本包围的类空间中，更有可能成为该类中心单元 当据集和 UCI 数据集 本文将 PCL 和 PCCL 中的学 习率设为 c = 0 001，将 PCL 中的惩罚率设为 r= 0 000 1 ，与原文一致4 1混合高斯数据集实验本文使用的混合高斯数据集包含 4 个类，总共600 个数据点，其中 4 个类分别由 4 个不同的高斯，如图 2 ( a) 所示 4 种不同形状的样本群这类种子单元成为竞争单元时，由于 nr 较大，惩罚因子 变小，使它受到的惩罚强度 变弱，让其在所在类的样本空间中的坐标位置有一个微小偏移作为 惩罚，不会对其最后成为中心单元造成太大影响 反 之，种子单元获胜次数越

34、少，学习程度越小，被样本吸引移动的次数也较少，当其成为竞争单元时，由于 nr 较小，惩罚因子 相比前者更大，受到的惩罚强度 也比前者大，向远处的偏移量较大 随着惩罚次数增加，会使其慢慢远离样本区域，成为冗余单元，最 终消亡 这种思想可看作是对 Kohonen 提出的 LVQ2 算法23 在无监督化情况下的一种拓展本文改进的算法过程描述如下算法 3 可区分惩罚控制竞争学习算法step 1 从样本集 x1 ，x2 ，xn 中随机选择 一个样本 xt ，根据下式计算样本到各个中心单元的 距离 ( xt ，mj ):分布生成分别代表 4 个不同的类，各类之间相互交叉，且每个 类的密度都不同，与其他类样

35、本相比，用实心点标记 的样本更松散，其中空心的“ ”表示随机选取的 6 个样本作为聚类的初始种子单元对上述高斯产生的 600 个样本分别使用 PCL、 PCCL 和 DPCCL 进行聚类实验 实验中，取迭代 次数为 100，得到的聚类结果如图 2 ( b) ( f) 所示， ( b) ( d) 是 3 种算法聚类结果的总体分布图，( e) 和( f) 分别为( c) 和( d) 放大后的局部细节图从图 2( b) 中看出 PCL 算法将 600 个样本聚 成 6 个类，比原始类别数多 2 个 从图 2 ( c) 可见 PCCL 似乎是将两个单元踢出样本区域，然 而从 PCCL 聚 类结果的局部

36、细节图 2 ( e ) 中 可 看 出 PCCL 算法的右上角有少量的“”形样本点，这几 个样本点所属的中心单元就是右上方不远处的空心tj“”点 造成这种状况的原因如下:在最后一次迭代( xt ，mj ) =njknii = 1x m 2 (7)开始时，这些样本被分配给该种子点，后来随着六角 星形和三角形数据的中心点确定，这个种子点被当 成冗余单元进行惩罚被驱离数据区，因此离样本较step 2根据上一步得到的距离度量，找出距离最小的前两个单元，即获胜单元和竞争单元 根据 下式进行更新学习:远 PCCL 最终真正去除一个冗余单元，比 PCL 算 法效果好图 2( d) 是本文提出的 DPCCL

37、聚类结果，它能mnewoldoldj= mj+ pj，t ( xt mj ) ，正确地将 600 个样本聚成 4 个类，另外 2 个冗余单nnewold其中，pj，t =c= nc + 1，c ，若 j = c ， 若 j = r元远离数据区域 从局部细节图 2 ( f) 可见 4 个种子点都在中心位置 从图 2 可看出，只有本文算法可将 这 600 个数据点聚成 4 个类，与真实类别数一致因为每个算法确定的类别数可能不同，所以不0，其他c = arg min j ( xt ) ，r = arg min j ( xt )，jjc2能用聚类误差平方和来度量算法性能 为进一步评价各个算法的准确率，

38、采用 3 种常用的评价指标:调 整后的兰德索引 ( Adjusted and Index，AI)22、 = 1 xt mc ，r trn + constx m 2c=1 nc + const调 整 后 的 互 信 息 ( Adjusted Mutual Information， AMI)24和 V-measure25 这 3 种聚类评价指标都是step 3对每个样本进行上述迭代更新，直到满足预先给定的迭代条件为止4实验与结果分析实验所使用的数据集为混合高斯生成的随机数在已知正确分类信息的前提下对聚类算法的聚类结 果进行评价的有效指标表 1 是对上述 3 种算法在该数据集上聚类结果 的 3 种评

39、价指标统计平均值，算法中 K 分别取 5 个 不同的值，针对每个 K 值统计 20 次，共统计 100 次聚类结果的评价指标平均值432模式识别与人工智能27 卷( a) 数据集与初始种子单元( b) PCL 的聚类结果( c) PCCL 的聚类结果( a) Dataset and initial seed units( b) Clustering result of PCL( c) Clustering result of PCCL( d) DPCCL 的聚类结果( d) Clustering result of DPCCL( e) PCCL 的局部细节图( e) Local detaile

40、d view of PCCL( f) DPCCL 的局部细节图( f) Local detailed view of DPCCL图 2 聚类结果Fig 2 Clustering results表 1 3 种评价指标统计平均值Table 1 Statistical average of 3 kinds of evaluation indexAMIAIV-measurePCL0 5588155780 5491657670 530726291PCCL DPCCL0 5846280270 6535821730 6060122440 6487976230 5980410170 6342955105由表

41、1 发现，针对每行，每种算法的聚类结果的3 种评价指标值都相近，说明 3 种评价指标对聚类结果评价的一致性; 针对每列，本 文算 法 的 AI、 AMI 和 V-measure 评价指标是最好的 因此，在混合 高斯数据集上本文的 DPCCL 算法的聚类准确性 更好4 2UCI 机器学习数据库实验本文选用 UCI 机器学习数据库中的 6 个聚类算 法测试数据集进行测试 表 2 列出这 6 个数据集的 样本数、类别数和属性数为评价各个算法的性能，下面采用 AI、AMI 及 V-measure 对 PCL、PCCL 和 DPCCL 算法在这两 个数据集上的聚类结果分别进行评价和对比分析实验中的初始节点数目 K 取 5 个不同的值，针 对每个 K 值各算法均执行 20 次，每次迭代周期为100 最后统 计 100 次 聚 类 结 果 的 AI、AMI 和 V- measure 这 3 种评价指标的平均值进行比较 图 3 分 别是这 3 种评价指标对 3 个算法在 6 个数据集上的聚类准确率直方图表 2 6 个测试数据集Table 2 6 testing datasets数据集样本数类别数属性数Iris15034Seeds21037Breast-cancer69929Soybean47435Segment210719 Ye