一种基于遗传算法的聚类集成方法

ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ　ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　一种基于遗传算法的聚类集成方法　王丙景，高茂庭　ＷＡＮＧ　Ｂｉｎｇｊｉｎｇ，ＧＡＯ　Ｍａｏｔｉｎｇ　上海海事大学信息工程学院，上海２０１３０６　Ｃｏｌｌｅｇｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｓｈａｎｇｈａｉ　Ｍａｒｉｔｉｍｅ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ　２０　１　３０６，Ｃｈｉｎａ　ＷＡＮＧ　Ｂｉｎｇｊｉｎｇ，ＧＡＯ　Ｍａｏｔｉｎｇ．Ｎｅｗ　ｍｏｄｅｌ　ｆｏｒ　ｃｌｕｓｔｅｒｉｎｇ　ｅｎｓｅｍｂｌｅ　ｂａｓｅｄ　ｏｎ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，２０１３，４９（８）：１６４—１６８．　Ａｂｓｔｒａｃｔ：Ｃｌｕｓｔｅｒｉｎｇ　ｅｎｓｅｍｂｌｅ　ａｌｇｏｒｉｔｈｍｓ　ｒｅｑｕｉｒｅ　ｈｉｇｈｅｒ　ｄｉｆｆｅｒｅｎｃｅｓ　ａｍｏｎｇ　ｃｌｕｓｔｅｒｉｎｇ　ｃｏｍｐｏｎｅｎｔｓ，ｗｈｉｃｈ　ｉｎｄｕｃｅ　ｈｉｇｈｅｒ　ｃｏｍ—　ｐｌｅｘｉｔｙ　ｄｕｒｉｎｇ　ｔｈｅ　ｇｅｎｅｒａｔｉｎｇ　ｐｈａｓｅ　ｏｆ　ｃｌｕｓｔｅｒｉｎｇ　ｃｏｍｐｏｎｅｎｔｓ．Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａ　ｎｅｗ　ｍｏｄｅｌ　ｆｏｒ　Ｃｌｕｓｔｅｒｉｎｇ　Ｅｎｓｅｍｂｌｅ　ｂａｓｅｄ　ｏｎ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ（ＣＥＧＡ），ｗｈｉｃｈ　ｄｏｅｓ　ｎｏｔ　ｎｅｅｄ　ｔｏ　ｃｏｎｓｉｄｅｒ　ｔｈｅ　ｄｉｆｆｅｒｅｎｃｅｓ　ｂｅｔｗｅｅｎ　ｃｌｕｓｔｅｒｉｎｇ　ｃｏｍｐｏｎｅｎｔｓ，ｂｕｔ　ｔｒａｎｓｌａｔｅｓ　ｃｌｕｓｔｅｒｉｎｇ　ｉｎｔｏ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｏｆ　ｃｌｕｓｔｅｒｉｎｇ　ｃｏｍｐｏｎｅｎｔｓ　ｂｙ　ｃａｌｃｕｌａｔｉｎｇ　ｔａｒｇｅｔ　ｆｕｎｃｔｉｏｎ，ａｎｄ　ｏｐｔｉｍｉｚｅｓ　ｔｈｅ　ｇｒｏｕｐｉｎｇ　ｏｆ　ｃｌｕｓｔｅｒｉｎｇ　ｃｏｍｐｏｎｅｎｔｓ　ｂｙ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ．ＣＥＧＡ　ｓｅｔｓ　ｔｈｅ　ｆｉｎａｌ　ｏｐｔｉｍａｌ　ｃｈｒｏｍｏｓｏｍｅ　ｔｏ　ｂｅ　ｔｈｅ　ｒｅｓｕｌｔ　ｏｆ　ｃｌｕｓｔｅｒｉｎｇ　ａｎｄ　ｉｔｓ　ｃｏｍｐｌｅｘｉｔｙ　ａｎｄ　ａｐｐｌｉｃａｔｉｏｎ　ａｒｅ　ａｌｓｏ　ａｎａｌｙｚｅｄ．Ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｄｅｍｏｎｓｔｒａｔｅ　ｔｈｅ　ｅｆｆｅｃｔｉｖｅｎｅｓｓ　ｏｆ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｍｅｔｈｏｄ　ｏｎ　ｓｅｖｅｒａｌ　ＵＣ１　ｄａｔａｓｅｔｓ．　Ｋｅｙ　ｗｏｒｄｓ：ｃｌｕｓｔｅｒ　ｅｎｓｅｍｂｌｅｓ；ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ；ｃｌｕｓｔｅｒｉｎｇ　ｃｏｍｐｏｎｅｎｔｓ　摘要：聚类集成算法通常对聚类成员差异性要求较高，导致算法在生戍聚类成员阶段计算复杂度提高。针对该问题提　出了一种基于遗传算法的聚类集成方法ＣＥＧＡ，不考虑聚类成员的差异性，而是利用目标函数将聚类问题转化为聚类成员　的优化问题，充分利用遗传算法内在的并行性和全局寻优能力，对聚类成员进行优化组合，并以得到的最优染色体作为聚　类集成最终结果。分析了ＣＥＧＡ的复杂度及适用范围，并利用ＵＣＩ数据库中部分数据集进行实验，实验结果表明这种聚　类集成方法的有效性。　关键词：聚类集成；遗传算法；聚类成员　文献标志码：Ａ　中图分类号：ＴＰ１８１　ｄｏｉ：１０．３７７８￣．ｉｓｓｎ．１００２—８３３１．１１０９—０１９０　ｌ　引言　重取样技术　。这种技术虽然能提高聚类的效果，但同时　聚类集成　是指综合多种不同基聚类算法或同一种基　却增加了生成聚类成员的计算成本。　聚类算法的多个版本来解决同一个聚类问题，可以显著地　文献［７］将遗传算法用于聚类集成，并将聚类成员集作　提高聚类算法的泛化能力。聚类集成在保护私有信息、知　为目标，利用基于信息理论的准则函数计算染色体与聚类　识重用和分布式汁算中有着重要的应用　。　成员的距离，在随机产生的染色体种群中找到一个与所有　设数据集Ｄ＝｛ｄ　，ｄ　一，ｄ　｝包含ｎ个数据对象，聚类集　聚类成员距离和最小的聚类结果。但其中存在两个问题；　成的过程　Ｌ般包括两个步骤：首先，对数据集Ｄ执行　次　（１）聚类成员结果不可能是完全正确的　’　。，将不完全正确　聚类算法，得到　个聚类结果，仃＝　，　，…，　｝，７ｇ，（以　的聚类成员作为目标所产生的最优染色体，其聚类结果不　一定是最好的。（２）其初始种群由随机产生的染色体组成，　下称聚类成员）为第ｉ次的聚类结果；然后，采用合适的一　这种初始群体是杂乱的，必定需要多次进化，大大增加进　致性方法Ｆ对Ｊｒ７中的聚类结果进行整合得到一个新的一　化时间。针对以上问题，本文提出一种基于遗传算法的聚　致性结果７／＂　。　类集成方法ＣＥＧＡ（Ｃｌｕｓｔｅｒｉｎｇ　Ｅｎｓｅｍｂｌｅ　ｍｏｄｅｌ　ｂａｓｅｄ　ｏｎ　在聚类集成中，聚类成员的差异性通常被认为是影响　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ），将聚类成员集合作为遗传算法的初始　集成最终结果的重要关键因素之一　，近年来出现了许多通　种群，将聚类结果综合评价指数ＯＣＱ　作为目标函数，得到　过提高聚类成员差异性来改善聚类效果的方法，如Ｂａｇｇｉｎｇ　的最优染色体为聚类集成最终结果。这样既避免了聚类　基金项日：上海海事大学校基金项目（Ｎｏ．２０１０００９２）。　作者简介：王丙景（１９８７一），男，硕士研究生，主要研究领域为数据挖掘；高茂庭（１９６３　），男，博士，教授，ＣＣＦ高级会员，主要研究领域为　数据挖掘、数据库与管理信息系统。Ｅ—ｍａｉｌ：ｗａｎ　ｉｎ舀ｉｎｇ１９８７＠１６３．ｔｏｍ　收稿日期：２０１１—０９—１３　修回日期：２０１１－１１—０２　文章编号：１００２—８３３１（２０１３）０８—０１６４—０５　ＣＮＫＩ出版Ｈ期：２０１２－０１－１６　ｈｔｔｐ：／／ｗｗｗ．ｃｎｋｉ．ｎｅｔ／ｋｃｍｓ／ｄｅｔａｉｌ／１１．２１２７．ＴＰ．２０１２０１１６．０９２８．０５１．ｈｔｍｌ　王丙景，高茂庭：一种基于遗传算法的聚类集成方法　成员的差异性分析，同时聚类结果综合评价指数客观地分　析聚类结果质量，使进化朝着聚类效果好的方向发展，提　高了聚类效果。　本文在生成聚类成员时没有对差异性作具体要求，主　要是基于以下两点：（１）生成的聚类成员要作为遗传算法的　初始种群（详见３．３．１节），种群中每个染色体要表示成一个　完整的聚类结果，这要求每个聚类成员必须包含数据集中　全部的数据对象，而类似Ｂａｇｇｉｎｇ的重取样技术得到聚类　成员并不能包含所有的数据对象。（２）遗传算法中的进化　理论完全可以体现出聚类成员差异性，在最极端的情况　下，生成的Ⅳ个聚类成员都相同时，可以利用突变函数使　种群出现新的染色体，经过进化仍然可以得到最优的聚类　结果。　２遗传算法基本原理　遗传算法是模拟生物进化规律的一种随机化搜索方　法，其直接对结构对象进行操作，具有内在的并行性和全　局寻优能力；采用概率化的寻优方法，能自动获取和指导　优化的搜索空间，自适应地调整搜索方向［１０－１１］￣　遗传算法的基本步骤包括：　步骤１选择编码方式，设定交叉率、突变率，以及进化　代数Ｇｅｎ＝Ｏ。　步骤２初始化种群得到Ｐ（Ｇｅｎ）。　步骤３根据目标函数计算种群中每个染色体的适应度。　步骤４　Ｇｅｎ＝Ｇｅｎ＋ｌ。　步骤５若Ｇｅｎ到达设定的条件，则转向步骤１１，否则　转向步骤６。　步骤６从Ｐ（Ｇｅｎ一１）中选出两个成员，选出的概率与　染色体的适应度成正比。　步骤７按照预先设定的杂交率，从每个选中染色体的　一个随机确定的点上进行杂交。　步骤８按照预选设定的变异率，从每个选中染色体上　随机确定一个点，把相应的位值改变。　步骤９选择新产生的个体和Ｐ（Ｇｅｎ一１）群体中适应度　大的染色体组成种群Ｐ（Ｇｅｎ）。　步骤１０转到步骤３。　步骤１１输出种群Ｐ（Ｇｅｎ）中适应度最高的个体，算法　停Ｉ匕。　３基于ＧＡ的聚类集成　聚类集成中最困难的是找到一个一致性函数将聚类成　员进行整合，目前存在许多一致性函数，如投票法、超图划　分、基于共协矩阵的证据积累、概率积累等。本文将遗传　算法作为一致性函数，利用遗传算法全局搜索能力找到最　优的聚类结果。　ＣＥＧＡ算法的主要思想：在对数据集执行Ｈ次聚类算　法（如Ｋ－ｍｅａｎｓ），生成　个聚类成员刀＝｛７ｇ　，７ｇ　一，７ｇ　｝后，　基聚类得到的聚类成员并不完全正确　，可以将聚类成员量　化为式（１）：　７ｇ　＝｛Ｄ　，Ｄ『Ｆ）　（１）　其中，Ｄ　表示第ｆ个聚类成员中聚类正确的数据对象集合，　Ｄ　表示第ｆ个聚类成员中聚类错误的数据对象集合，且Ｄ　Ｕ　Ｄ　＝Ｄ。当算法对Ｄ　进行交叉或突变时，目标函数会得　到适应度较差的染色体；当算法对Ｄ　进行交叉或突变时，　目标函数会得到适应度较好的染色体，利用精英选择函　数，使种群保留适应度较高的染色体，种群的进化集中在　适应度较高的染色体上，得到适应度最好的染色体作为最　终的聚类结果。　３．１　ＣＥＧＡ算法基本框架　ＣＥＧＡ算法遵循一般聚类集成的两大阶段：聚类成员　生成阶段和聚类成员集成阶段，在聚类成员生成阶段加入　聚类成员簇标号统一算法。ＣＥＧＡ算法的基本框架如下：　聚类成员生成阶段：对原始数据集执行Ⅳ次聚类算法　（比如Ｋ－ｍｅａｎｓ），得到初始聚类成员Ｈ　＝　，　，…，７ｇ　ｒ｝；　利用最大覆盖法ｕ　对初始聚类成员簇标号进行统一，得到　聚类成员集合，７＝｛７ｇ　，　…，７ｒ　｝。　聚类成员集成阶段：将仃＝　，７ｇ　．．，　｝作为遗传算　法的初始种群，根据第２章介绍的遗传算法步骤进行进化，　得到最优染色体为最终聚类结果。　ＣＥＧＡ算法流程如图１所示。　对原始数据集执行日次Ｋ－ｍｅａｎｓ聚类　Ｉ　生成初始聚类成员集合　』　统一初始聚类成员簇标号　ｊ　生成聚类成员集合　』　初始化种群、令Ｇｅｎ＝Ｏ　ｌ　根据目标函数计算个体适应度　●　ｔ　１　Ｉ突变产生新个体　Ｉ保存最优个体Ｉ　Ｉ变异产生新个体　●　产生下一代种群、令Ｇｅｎ＝Ｇｅｎ＋ｌ　否　＼　／　Ｉ是　选择最优个体为最终聚类结果　图１　ＣＥＧＡ算法流程图　３．２聚类成员生成阶段　在这一阶段，采用常用的Ｋ－ｍｅａｎｓ算法来生成聚类成　员，在对原始数据集Ｄ＝｛　，ｄ　，…，　执行　次聚类（参数　为后），得到聚类成员集合Ｈ　＝｛　，７ｇ　，…，丌Ⅳ　｝，仃　为日×ｎ　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　二维数组，其中：　７ｔ　＝｛ｃ　，ｃ　…，ｃ　ｉ∈［１，刎　（２）　ＯＣＱ聚类综合评价指数　是Ｊｉ　Ｈｅ等人提出的，将聚类　密集性和聚类分离性结合的一种聚类相对评价方法。ＯＣＱ　定义为：　ＯＣＱ（１ｆ）＝ｌ一（　・Ｃｍｐ＋（１一　）・Ｓｅｐ）　（５）　ｃ　，／ｌ∈［１，，ｚ］为第　次聚类结果中第　个数据对象所属的簇标　号，１≤Ｃ．ｉ≤ｋ。　然而，由此得到的聚类成员Ｊｒ７　中，　（ｆ∈【１，ＨＩ）与　，　其中，Ｃｍｐ表示聚类密集性，Ｓｅｐ表示聚类分离性。　为平　衡系数，且０＜　＜１，用来权衡聚类密集性和聚类分离性的　比重。不同的数据集取不同的　值。Ｃｍｐ定义为：　（，　［１，Ｈ］，ｌ，≠ｉ）没有可比性，不能直接用于遗传算法进行优　化。例如，对于聚类成员　＝［１，１，１，３，３，２，２，１］和７９２ｆ＝　【２，２，２，１，１，３，３，２］来说，虽然它们的内容不一样，但它们　表示同一种聚类结果，因此，必须对聚类成员簇标号进行　ｃ　＝吉砉　（６）　其中，ｃ是聚类个数，Ｄｅｖ（ｃ　）是类ｃ　的方差，Ｄｅｖ（Ｄ）是类　统一。周志华等提出的最大覆盖法对聚类成员簇标号进　行统一，认为有对应关系的聚类簇集所覆盖的相同对象的　个数应该是最大的。两个聚类成员７／＂　和７ｔ＂　分别把原数据　集划分为尼个簇集，分别用聚类标记｛ｃ　ｃ　…，ｃ　和　｛ｃ　ｃ　…，ｃ　表示。首先，将这两个聚类成员中每一　对簇集ｃ　和ｃ　所覆盖的相同对象的个数记录在ｋ×ｋ的　ＯＶＥＲＬＡＰ矩阵中，然后，选择其中覆盖相同对象个数最大　的簇集建立对应关系，并将其结果从ＯＶＥＲＬＡＰ矩阵中移　除。重复以上过程，直到所有簇集都建立了对应关系为止。　此时，聚类成员集合变化如式（３）：　Ｈ　＝｛７ｒ１　，　２　，‘一，丌　｝　仃＝｛丌１，丌２，…，７Ｃ　｝　（３）　其中，　＝｛ｃ　，ｃ　，…，ｃ　｝，ｉ∈［１，Ｈ］，Ｃ，ｔ为统一后的簇标号　（非簇集）。　３．３聚类成员集成阶段　在聚类成员集成阶段，引入遗传算法，将聚类成员集　合作为遗传算法的初始种群，聚类结果综合评价指数ＯＣＱ　（Ｏｖｅｒａｌｌ　Ｃｌｕｓｔｅｒ　Ｑｕａｌｉｔｙ）作为目标函数引导种群进化，设　定与代数相关的突变率和杂交率。然而，简单遗传算法不　是全局收敛的，带有最优个体保留的遗传算法才是全局收　敛的　。因此，加入精英选择函数来保留适应度最高的染　色体，使算法具有全局收敛性，同时提高进化速率。下面　介绍各项参数的具体内容。　３．３．１染色体编码　聚类成员集合采用实数编码方式进行编码，实数编码　可以有效地缩短染色体长度，实数编码计算方便，避免了　不　进制之间的转换，降低计算复杂度。每个聚类成员作　为一条染色体，聚类成员中簇标号为染色体基因　。很显　然，原始数据集中数据对象的个数为染色体长度。式（４）　表示一条染色体：　：｛ｃ　，ｃ　，…，ｃ：｝，ｉ∈［１，　］　（４）　其中，Ｃ　为统一后的簇标号。　３．３．２　目标函数　遗传算法的目标函数非常重要，目标函数引导群体的　进化方向，使染色体向着有利于问题解决的方向发展。聚　类问题的解是要找到一个聚类结果，使相似的数据对象划　分到同一簇，相异的数据对象划分到不同簇。采用聚类结　果综合评价指数来计算每条染色体的聚类效果并返回一　个适应度。　Ｄ的方差。函数Ｄｅｖ（Ｘ）定义为：　。ｅｖ（　）　：ｉ１　Ｎ：　２，；　，　ｘ　，　ｘ－））　　（７）　其中，Ⅳ是数据集　中的数据对象个数，　＝　∑　，　（　，　）　是Ｘ　和　．的距离。根据聚类结果应保证类内相似性最大　的原则，为了使簇内数据尽可能更加紧凑，聚类密集性应　越小越好。Ｓｅｐ定义为：　，　Ｃ　Ｃ　ｄ　，Ｘ）　Ｓｅｐ　一，：　‘　］　（８）　其中，　是高斯常量，为方便计算，通常设２　＝１，Ｘ　和Ｘ，　分别是类Ｃ．与Ｃ．的聚类中心。根据聚类结果应保证类间　相似性最小的原则，为了使簇间数据尽可能更加分开，聚　类分离性应越小越好。由Ｃｍｐ和Ｓｅｐ的定义可知，聚类结　果综合评价指数ＯＣＱ值越大，表明聚类效果越好。　３．３．３　没定杂交函数及突变雨数　在进化过程中，算法经常会收敛到局部最优点，达不　到全局最优的效果，为此，增加了与进化代数相关的交叉　率和突变率　。　，以提高算法的全局搜索能力。　杂交函数定义如式（９）：　ＰＣｔＰｃｆＧｅｎ１＝ｅｍｐ，Ｐｃｔｅｍｐ　“　（９）　其中，Ｐｃ　。＝Ｐｃ　×２‘－Ｇ　柏　，Ｐｃ…为预没的最大交　叉率，尸ｃ…为预设的最小的交叉率，确保交叉率介于最小　值与最大值之间变化。　突变函数定义如式（１０）：　Ｐｒｏｔｅｍｐ＇ＰｍｔＪｐ　ｍｌ　尸　（Ｇｅｎ）＝ｅ　Ｐ　（１０）　其中，Ｐ　。　１　×尸　…，　一尸　．　分别　为预设定的突变率的最大值和最小值。　算法中种群的进化关键在突变函数的处理，利用突变　函数的随机性对错误聚类的数据进行重新分类。如某个体　编码为｛１，１，１，２，２，２，３，３，３，１｝，即第１、２、３、１０个数据被　分为一簇，第４、５、６个数据被分为一簇，第７、８、９个数据被　分为一簇，而正确的分类结果编码为｛１，１，１，２，２，２，３，３，　３，３｝，这时利用突变函数对第１０个数据编号进行突变，当　突变正确时，染色体适应度会提高，算法保存最优个体，重　王丙景。高茂庭：一种基于遗传算法的聚类集成方法　复进化直至最优染色体适应度不在变化。虽然依靠突变　函数进化种群有一定的盲目性，但实验表明只要目标函数　正确，适当提高算法的突变率和种群大小，进化速率和进　化结果是乐观的。　４．２　对比算法　实验采用标准Ｋ－ｍｅａｎｓ、ＳＯＭ、ＳＣＥ　和ＣＥＧＡ算法进　行实验对比。　标准Ｋ－ｍｅａｎｓ算法的目标是将包含Ⅳ个对象的数据集　３．３．４精英选择函数　为保存种群进化过程中产生的最优个体，在算法中增　加了精英选择函数　，即将种群中适应度最高的　个个体　直接选入下一代，来保存优良基因。精英选择在本实验中　尤为重要，对适应度高的个体进行进化可以有效地减少遗　传算法进化代数从而提高进化速率。实验表明，当　大小　分为　个簇，使同一簇内具有较高的相似度，而不同簇问相　似度较低。算法先任意选择　个对象作为初始的簇中心，　再计算每个对象与各个簇中心的距离并将其赋给最近的　簇，更新簇的平均值，不断重复此过程直到准则函数收敛。　ＳＯＭ（自组织特征映射）是由输入层和竞争层构成的　双层神经网络。输入层由Ⅳ个神经元构成，用于接受外部　为种群数量的２％～１０％时，进化效果最好。　３－３．５算法复杂度分析　算法设定原始数据Ｄ包含ｎ个数据对象，每个数据对　象有ｍ个属性，原始数据集有　个簇，一次基聚类需ｔ次循　环，基聚类成员个数为Ｈ。由ＣＥＧＡ算法步骤，绝大部分处　理都集中在适应度的计算上，算法在产生聚类成员阶段的　计算复杂度为Ｏ（ｋｎｔＨｍ），聚类成员簇标号统一过程的计　算复杂度为０（Ｈｋｎ），进化阶段计算复杂度为０（ＭａｘＧｅｎ×　Ｈｘｋ×，ｚ　ｘｍ）。综上，ＣＥＧＡ算法计算复杂度为Ｏ（ＭａｘＧｅｎ×　Ｈ×　ｎ　）　４实验与结果分析　４．１数据集和评价标准　实验采用ＵＣＩ（Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｃａｌｉｆｏｒｎｉａ，Ｉｒｖｉｎｅ）的机器　学习库中的部分数据集作为实验数据集。表１给出了这些　数据的样本、属性和类别数量。　表１　实验数据集的样本、属性和类别数量　选用的聚类结果评价标准是Ｍｉｃｒｏ－ｐｒｅｃｉｓｉｏｎ　标准，使　用此标准测试聚类结果正确率。其计算公为：　＝　其中，ａ　表示对数据某一类分类正确的数量，Ⅳ表示数据　集中数据对象的数量，　表示此数据集和中的类别的数　量。为了更好地衡量聚类的正确率，要进行重复的实验，　采用平均正确率来衡量聚类将更准确。所以使用式（１２）　计算　：　．　，　ｋ　（１２）　其中，　为重复实验的次数，本文选为１０次。　输入模式，即Ⅳ维数据向量。竞争层（输出层）通常排列成　一个１维或２维的平面阵列，由　个神经元构成，用于将输　入层的节点映射到竞争层节点上。输入层的所有节点和　竞争层所有节点用权值Ｗ进行连接，且连接权值在网络训　练过程中动态更新。　ＳＣＥ（半监督聚类集成）旨在将半监督学习和聚类集成　相结合来提高聚类效果。ＳＣＥ是阐述聚类成员与聚类集成　结果变量之间的依赖关系的贝叶斯网络，先采用一部分数　据作为训练数据来确定整个数据集的初始化参数ａ和ｂ，根　据ＳＣＥ的ＥＭ算法找到最优的ａ和ｂ使得聚类成员中最大　对数似然　估计，最后通过参数将聚类成员转化成聚类　集成结果。　４．３实验结果　表２给出了标准Ｋ．ｍｅａｎｓ、ＳＯＭ、ＳＣＥ和ＣＥＧＡ算法聚　类成功率的对比结果。在九个数据集中，ＣＥＧＡ有７次表　现良好，仅在Ｐｉｍａ和Ｗｄｂｃ数据集上稍微落后于ＳＣＥ。但与　单一的聚类算法相比，ＣＥＧＡ能大幅提高聚类的成功率。　表２各算法在数据集　的聚类　成功率对比结果　（％）　本文还设计了另外一组实验，在聚类成员生成阶段，　ＣＥＧＡ与Ｂａｇｇｉｎｇ、Ｂｏｏｔｓｔｒａｐ及Ｓｕｂｓａｍｐｌｉｎｇ在五个数据集　上的性能比较。Ｂａｇｇｉｎｇ、Ｂｏｏｔｓｔｒａｐ和Ｓｕｂｓａｍｐｌｉｎｇ是三种　典型的取样技术，在聚类集成中常被用于生成差异性较大　的数据集，在差异性较大的数据集上应用基聚类算法产生　多样性的聚类成员。ＣＥＧＡ没有考虑聚类成员的差异性，　只需考虑基聚类算法。为了更好地衡量四种算法的性能，　基聚类算法统一为标准Ｋ－ｍｅａｎｓ算法。图２给出了在相同　的硬件和软件环境下各算法在聚类成员生成阶段性能比　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　较的结果。横轴代表实验数据集，纵轴代表算法生成聚类　成员所花费的时间（单位：ｍｓ）。　数据集　图２　ＣＥＧＡ与常用采样技术存聚类　成员生成阶段的性能比较　由图２可以得出，三种取样技术在提高聚类成员的差　异性的同时也增加了算法的复杂度，ＣＥＧＡ可以明显提高　生成聚类成员的效率。　４．４　ＣＥＧＡ的进化　图３和图４分别是当最大和最小突变率均为０＿３时，　ＣＥＧＡ在Ｉｒｉｓ和Ｐｉｍａ数据集上的进化情况。图５和图６分别　是当最大和最小突变率均为Ｏ．０２时，ＣＥＧＡ在Ｉｒｉｓ和Ｐｉｍａ　数据集上的进化情况。横轴代表进化代数，纵轴代表适应　度值。　０．８４８　０．８４６　｜　０ｌ８４４　８４２　０．８４０　』　ｉ　Ｏ．８３８　０　１００　２００　３００　４００　５００　进化代数　图３　ＣＥＧＡ在Ｉｒｉｓ数据集卜进化最大　突变率和最小突变率均为０．３　／０　－　　。０．５２６　一　‘　，　ｊ型　０＿５２４　，　０．５２２　，　Ｕ　ｌＵＵ　２００　ｊ００　４００　，ＵＵ　进化代数　图４　ＣＥＧＡ在Ｐｉｍａ数据集上进化最大　突变率和最小突变率均为０．３　从图３、４和图５、６中的种群进化速率对比情况可以得　出，在聚类问题中适当提高突变率可以使种群进化速率明　显提高，通过增加突变率达到了提高种群进化速率的目的。　０．７４３　０　趔　ｏｌ７４２　９　１ｌ璺１　０．７４２　８　０　ｌ００　２００　３００　４００　５００　进化代数　图５　ＣＥＧＡ存Ｉｒｉｓ数据集卜进化最大　突变率和最小突变率均为０．０１　０．４１４　４　０．４１４　２　趔０．４１４　０　蜊０．４１３　６　－　・　一　０　４１３　４　０．４１３　２　　ｌ０　１００　２００　３００　４００　５００　进化代数　图６　ＣＥＧＡ在Ｐｉｍａ数据粜【：进化最大　突变率和最小突变率均为０．０１　５结束语　本文提出了基于遗传算法的聚类集成算法，无需考虑　聚类成员的差异性，着重体现遗传算法作为一致性函数在　集成中的全局寻优的功能，在遗传算法中增加了精英选择函　数，并适当提高突变率以增加进化速率。实验表明ＣＥＧＡ具　有较高的正确性和高效性。需要指出的是，算法在Ｍａｇｉｃ０４　数据集上取得了不错的聚类效果，但是其运行时问却相对　较长，这是由于算法将聚类成员作为染色体，当数据集中　数据量很大时，种群的染色体长度会相应地变长，进而利　用突变进行进化的效率会降低，从而导致进化时间增长。　实验中的对于大型的数据集可考虑将数据集划分为相互　重叠的数据子集，对数据子集分别进行聚类集成，利用重　叠信息进行整合，这是以后需要做的工作。　参考文献：　［１］Ｔｏｐｃｈｙ　Ａ，Ｊａｉｎ　Ａ　Ｋ，Ｐｕｎｃｈ　Ｗ．Ｃｌｕｓｔｅｒｉｎｇ　ｅｎｓｅｍｂｌｅｓ：ｍｏｄｅｌｓ　ｏｆ　ｃｏｎｓｅｎｓｕｓ　ａｎｄ　ｗｅａｋ　ｐａｒｔｉｔｉｏｎ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｐａｔｔｅｒｎ　Ａｎａｌｙｓｉｓ　ａｎｄ　Ｍａｃｈｉｎｅ　Ｉｎｔｅｌｌｉｇｅｎｃｅ．２００５，２７（１２）：　１８６６—１８８１．　［２］王红军，李志蜀．基于隐含变量的聚类集成模型［Ｊ］ｌ软件学报，　２００９，２０（４）：８２５．８３３．　［３］Ｚｈｏｕ　Ｚｈｉｈｕａ，Ｔａｎｇ　Ｗｅｉ．Ｃｌｕｓｔｅｒｅｒ　ｅｎｓｅｍｂｌｅ［Ｊ］．Ｋｎｏｗｌｅｄｇｅ—Ｂａｓｅｄ　Ｓｙｓｔｅｍｓ，２００６，１９（１）：７７—８３．　［４］Ｈａｎｓｅｎ　Ｌ　Ｋ，Ｓａｌａｍｏｎ　Ｐ．Ｎｅｕｒａｌ　ｎｅｔｗｏｒｋ　ｅｎｓｅｍｂｌｅｓ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｐａｔｔｅｒｎ　Ａｎａｌｙｓｉｓ　ａｎｄ　Ｍａｃｈｉｎｅ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，　１９９０，ｌ２（１０）：９９３—１Ｏ０１．　（下转２６５页）　梁军，肖　琳，张立洋，等：ＲＥＳＴ风格人力资源类互联网应用系统设计与优化　Ｍｅｄｉａ，２００７．　２０１３，４９（８）　２６５　６结束语　随着信息技术的不断发展，人力资源类互联网应用系　［６］毛力锐，蔡鸿明，徐博艺，等．基于ＲＥＳＴ面向资源的企业集成　平台框架［Ｊ］＿计算机工程，２０１０，３６（２）：２５４．２５６．　［７］Ｍａｚｚｅｔｔｉ　Ｐ，Ｎａｔｉｖｉ　Ｓ，Ｃａｒｏｎ　Ｊ．ＲＥＳＴｆｕｌ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｏｆ　ｇｅｏ—　ｓｐａｔｉａｌ　ｓｅｒｖｉｃｅｓ　ｆｏｒ　ｅａｒｔｈ　ａｎｄ　ｓｐａｃｅ　ｓｃｉｅｎｃｅ　ａｐｐｌｉｃａｔｉｏｎｓ［Ｊ］．　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｊｏｕｒｎａｌ　ｏｆ　Ｄｉｇｉｔａｌ　ＥａＣｈ，２００９，２（１）：４０—６１．　统的技术也在不断进步。本文提出了基于ＲＥＳＴ架构风格　的人力资源类互联网应用系统的设计方法及基于缓存服　务器的缓存优化方案，为构建高效、松耦合、易扩展的ＲＥＳＴ　风格人力资源互联网应用系统提供了可行性方案。接下　来还可以在缓存算法和缓存替换算法方面进行深入研究。　［８］毛峰，刘婷，刘义仁，等．基于ＲＥＳＴ面向资源的地理信息服务　设计［Ｊ］．计算机工程，２０１１，３７（８）：２３８．２４０．　［９］陈赞，胡坚，汪超亮，等．基于ＲＥＳＴ　Ｗｅｂ　Ｓｅｒｖｉｃｅｓ的分布式遥　感数据检索技术研究［Ｊ］ｌ计算机工程与设计，２０１０，３１（１４）：　３２０７—３２０９．　参考文献：　【１】刘佳音．我国人力资源信息网站的现状与发展【Ｊ］．情报科学，　２００４，２２（６）：７２８—７３３．　［１０］程冬梅，王瑞聪，刘燕，等ｌ基于ＲＥＳＴ架构风格的物联网服务　平台研发［Ｊ］．计算机工程与应用，２０１２，４８（１４）：７４—７８．　［１１］张歆爽．一种物联网资源共享平台的数据建模与实现［Ｄ】．北　京：北京邮电大学，２０１２．　［１２］黄锦川．ＲＥＳＴ风格服务在Ａｎｄｒｏｉｄ平台上的研究与应用［Ｄ】．　成都：西南交通大学，２０１０．　［２］许卓明，栗明，董逸生．基于ＲＰＣ和基于ＲＥＳＴ的ｗｅｂ服务交互　模型比较分析［Ｊ］．计算机工程，２００３，２９（２０）：６－８．　［３］王建斌，胡小生，李康君，等．ＲＥＳＴ风格和基于ＳＯＡＰ的Ｗｅｂ—　Ｓｅｒｖｉｃｅｓ的比较与结合［Ｊ］．计算机应用于软件，２０１０，２７（９）：　２９７—３００．　【４］Ｆｉｅｌｄｉｎｇ　Ｒ　Ｔ．Ａｒｃｈｉｔｅｃｔｕｒａｌ　ｓｔｙｌｅｓ　ａｎｄ　ｔｈｅ　ｄｅｓｉｇｎ　ｏｆ　ｎｅｔｗｏｒｋ—　ｂａｓｅｄ　ｓｏｆｔｗａｒｅ　ａｒｃｈｉｔｅｃｔｕｒｅｓ［Ｄ］．Ｉ￣ｉｎｅ，Ｃａｌｉｆｏｒｎｉａ：Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｃａｌｉｆｏｒｎｉａ，２０００．　［１３］基于ＲＥＳＴ架构风格的Ｗｅｂ　２．０实现［Ｊ］．计算机系统应用，　２００９，１８（７）．１６５—１６８．　［１４】黄宁海．基于ＲＥＳＴ的轻量级Ｊ２ＥＥ架构实现【Ｄ］．杭州：浙江大　学，２００８．　［５］Ｒｉｃｈａｒｄｓｏｎ　Ｌ，Ｒｕｂｙ　Ｓ．ＲＥＳＴｆｕｌ　ｗｅｂ　ｓｅｒｖｉｃｅｓ［Ｍ］．ｉｓ．１．］：Ｏ’Ｒｅｉｌｌｙ　（上接１６８页）　［５］Ｔｕｍｅｒ　Ｋ，Ｇｈｏｓｈ　Ｊ．Ｅｒｒｏｒ　ｃｏｒｒｅｌａｔｉｏｎ　ａｎｄ　ｅｒｒｏｒ　ｒｅｄｕｃｔｉｏｎ　ｉｎ　［１１］Ｈｏｌｌａｎｄ　Ｊ　Ｈ．Ａｄａｐｔａｔｉｏｎ　ｉｎ　ｎａｔｕｒａｌ　ａｎｄ　ａｒｔｉｉｆｃｉａｌ　ｓｙｓｔｅｍ［Ｄ］．　Ａｎｎ　Ａｒｂｏｒ：Ｔｈｅ　Ｕｎｉｖｅｒｓｉｙ　ｏｆ　Ｍｉｔｃｈｉｇａｎ　Ｐｒｅｓｓ，１９７５．　ｅｎｓｅｍｂｌｅ　ｃｌａｓｓｉｉｆｅｒｓ［Ｊ］．Ｃｏｎｎｅｃｔｉｏｎ　Ｓｃｉｅｎｃｅ，１９９６，８（３）：３８５—４０３．　［６］Ｂｒｅｉｍａｎ　Ｌ．Ｂａｇｇｉｎｇ　ｐｒｅｄｉｃａｔｏｒｓ［Ｊ］．Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ，１９９６，２４　（２）：１２３—１４０．　［１２］唐伟，周志华．基于Ｂａｇｇｉｎｇ的选择性聚类集成［Ｊ】．软件学报，　２００５，１６（４）：４９６—５０２．　［Ｉ３】恽为民，席裕庚．遗传算法的全局收敛性和计算效率分析［Ｊ］．　控制理论与应用，１９９６，１３（４）：４５５．４６０．　【１４］Ｓｒｉｎｉｖａｓ　Ｍ，Ｐａｔｕａｉｋ　Ｌ　Ｍ．Ａｄａｐｔｉｖｅ　ｐｒｏｂａｂｉｌｉｔｉｅｓ　ｏｆ　ｃｒｏｓｓｏｖｅｒ　ａｎｄ　ｍｕｔａｔｉｏｎ　ｉｎ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｓｙｓｔｅｍｓ，Ｍａｎ　ｆａｎｄ　Ｃｙｂｅｒｎｅｔｉｃｓ，１９９４，２４（４）：６５６・６６７．　［７］罗会兰．聚类集成关键技术研究［Ｄ］．浙江：浙江大学，２００７．　［８］Ｗａｎｇ　Ｈｏｎｇｊｕｎ，Ｑｉ　Ｊｉａｎｈｕａｉ．Ｓｅｍｉ—ｓｕｐｅｒｖｉｓｅｄ　ｃｌｕｓｔｅｒ　ｅｎｓｅｍｂｌｅ　ｂａｓｅｄ　ｏｎ　ｂｉｎａｒｙ　ｓｉｍｉｌａｒｉｔｙ　ｍａｔｒｉｘ［Ｃ］／／Ｔｈｅ　２ｎｄ　ＩＥＥＥ　ＩＣＭＥ．　Ｃｈｅｎｇｄｕ：［ｓ．ｎ．］，２０１０，４：２５１—２５４．　【９】Ｈｅ　Ｊ，Ｔａｎ　Ａ，Ｔａｎ　Ｃ．Ｍｏｄｉｉｅｄ　ＡＲＴ　２：ａ　ｇｒｏｗｉｆｎｇ　ｎｅｔｗｏｒｋ　ｃａｐａｂｌｅ　ｏｆ　ｇｅｎｅｒａｔｉｎｇ　ａ　ｆｉｘｅｄ　ｎｕｍｂｅｒ　ｏｆ　ｎｏｄｅｓ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｎｅｕｒａｌ　Ｎｅｔｗｏｒｋｓ，２００４，１５（３）：７２８．７３７．　［１０】Ｂｕｅｋｌａｎｄ　Ｍ．ＡＩ　ｔｅｃｈｎｉｑｕｅｓ　ｆｏｒ　ｇａｍｅ　ｐｒｏｇｒａｍｍｉｎｇ［Ｍ］．Ｃｉｎ—　ｃｉｎｎａｔｉ：Ｐｒｅｍｉｅｒ　Ｐｒｅｓｓ。２００２：８９．１１７．　［１５］欧阳森，王建华．一种新的改进遗传算法［Ｊ］．计算机工程与应　用，２００３，３９（１１）：１３－１５．　［１６］王红军，李志蜀．基于贝叶斯网络的半监督聚类集成模型［Ｊ］．　软件学报，２０１０，２１（１１）：２８１４．２８２５．　（上接２３０页）　［４］吴国平．数字图像处理原理［Ｍ］．武汉：中国地质大学出版社，　２００７．　通过进化方法自动调节阈值以达最优。同时，去噪过程中　对采样图像的多次扫描也影响了其处理速度，其算法有待　优化。对于最终提取的光条中心曲线，尚需添加样条插　值、曲线拟合等技术以消除局部非连续与曲线平滑性不够　等不足，其处理步骤尚需改善。另外，求差分割对测量场　［５］周明全，耿国华，韦娜．基于内容的图像检索［Ｍ］．北京：清华大　学出版社，２００２．　【６］徐要刚．热态大锻件尺度的在线测量技术研究［Ｄ］．上海：上海　交通大学，２００９．　［７］王志凌基于双ＣＣＤ的大锻件尺寸测量的实验研究［Ｄ］．秦皇岛：　燕山大学，２００６．　［８］Ｚｈａｎｇ　Ｌｉｍｅｉ，Ｑｉａｏ　Ｌｉｓｈａｎ，Ｃｈｅｎ　Ｓｏｎｇｃａｎ．Ｇｒａｐｈ—ｏｐｔｉｍｉｚｅｄ　ｌｏ－　景的特殊要求也决定该算法在应用上具有较大的局限性，　这均为今后相关研究需要改善之处。　参考文献：　［１］王鹏．线结构光三维自动扫描系统关键技术的研究［Ｄ］．天津：　天津大学，２００８．　ｃａｌｉｔｙ　ｐｒｅｓｅｒｖｉｎｇ　ｐｒｏｊｅｃｔｉｏｎｓ［Ｊ］．Ｐａｔｔｅｒｎ　Ｒｅｃｏｇｎｉｔｉｏｎ，２０　１　０，４３　（６）：１９９３—２００２．　［９徐要刚．９］激光测距法测量大锻件尺寸［Ｊ］．机械设计与研究，２００８，　２４（６）：９４—９７．　［２］曹建农．图像分割方法研究［Ｍ］．西安：西安地图出版社，２００６．　［３］吴庆阳．线结构光三维传感中关键技术研究【Ｄ］．成都：四川大　学，２００６．　［１Ｏ］贺俊吉，张广军．结构光三维视觉检测中光条图像处理方法　研究［Ｊ］ｌ北京航空航天大学学报，２００３，２９（７）：５９３．５９７．