（基础数学专业论文）微粒群优化算法及其在高维数据聚类的应用研究.pdf

微粒群优化算法及其在高维数据聚类的应用研究 摘要 高维数据聚类是数据挖掘领域中的重点和难点。数据挖掘的基本起始点是 假设将一个数据对象表示为一个高维特征向量，比如文本文档。传统的聚类算 法对高维数据的聚类质量由于维数灾难问题而大大降低。当特征维数增长时， 数据对象在高维空间中分布非常稀疏，数据对象之间趋向于等距是普遍现象。 在高维数据集中，对一个簇而言，通常存在着大量不相关或是冗余的特征；而 不同簇之间的相关特征子集又是不一样的。因而，在高维数据集中，发现在所 有维中存在簇的可能性几乎为零。聚类这类高维数据集的技术一般称为子空间 聚类或投影聚类，其目的在于从不同的特征子集中发现簇。然而，许多子空间 或投影聚类算法的性能也随着子空间规模增长而迅速下降。并且，有些算法需 要用户提供一些领域知识帮助调节它们的参数，比如维内数值的最大距离、输 入参数的阈值、数据最小密度等，而这些参数往往很难设置。 为了避免微粒群算法( p a r t i c l es w a r mo p t i m i z a t i o n ：p s o ) 在全局优化中陷入局部 极值，本论文首先设计了更加有效的微粒群优化算法变种。论文分析了标准p s o 算法早熟收敛的原因，提出了自适应扩散混合变异机制微粒群算法( p a r t i c l es w a r m o p t i m i z a t i o nb a s e do na d a p t i v ed i f f u s i o na n dh y b r i dm u t a t i o n ：i n f o r m p s o ) 。结合生物 群体信息扩散的习性，设计了一个考虑微粒分布和迭代次数的函数，自适应调整微粒 的“社会认知”能力，提高种群的多样性；模拟了基因自组织和混沌进化规律，引入克 隆选择使群体最佳微粒g b e s t 实现遗传微变，局部增值，具有变异确定性；利用l o g i s t i c 序列指导g a e s t 随机漂移，进一步增强逃离局部极值能力。基于种群的随机状态转移 过程，证明了新算法具有全局收敛性。与其它几种p s o 变种相比，复杂基准函数仿真 优化结果表明，新算法收敛速度快，求解精度高，稳定性好，能有效抑制早熟收敛。 其次，特殊目标函数以及编码设计使得改进的微粒群算法更适合高维数据 聚类，改进的微粒群优化算法用于求解高维数据聚类存在的两个问题。第一问题是 给定高维数据集中的聚类数目k ，如何确定软投影聚类中的变量加权问题。该 v 微粒群优化算法及其在高维数据聚类的应用研究 问题的主要思路是为每个簇寻找一组变量权值，一般被转化为服从许多等式约 束的非线性连续函数优化问题。针对于这一问题，我们设计了一个微粒群优化 算法( p a r t i c l es w a r mo p t i m i z a t i o nf o rt h ev a r i a b l ew e i g h t i n gp r o b l e m ：p s o v w ) 寻求软投影聚类高维数据的最优变量权值。高质量的聚类结果往往需要合适的 目标函数以及高效的搜索策略。p s o v w 中，我们使用了一个特殊的意m e a n s 目 标加权函数，该函数倾向于计算每一类在各自相关维的类内方差和而不是不相 关维的类内方差和。在优化的目标函数中，新算法同时使用了非正规化的编码 来表示变量权值。这种编码将软投影聚类中原本的变量权值问题的受限于等式 约束的搜索空间转换成一个冗余的封闭空间，大大便利了搜索进程。跟其它软 投影聚类算法相比，p s o v w 采用p s o 最小化给定的目标函数，因而算法对聚类 中心的初始值更不敏感。在算法产生的合成数据集和u c i 数据库的实例试验中， p s o v w 被证明能大大提高聚类质量。 高维数据聚类存在的第二个问题是聚类过程中如何自动确定聚类数目，该 问题也被视为界约束内一个非线性连续函数的优化问题。针对于该问题，我们 设计了( a u t o m a t i e a l l yd e t e r m i n i n gt h en u m b e ro fc l u s t e r su s i n gp a r t i c l es w a r m o p t i m i z a t i o n ：a u t o p s o ) 。特殊编码设计允许a u t o p s o 在迭代中能够表示具备不同 聚类数目的划分，而d a v i e s b o u l d i n ( d b ) 这个聚类有效性函数用于评价一个数 据集不同划分的质量。我们在合成的高维数据集上测试了a u t o p s o 的性能，并 将实验结果与其他聚类算法进行比较，实验结果表明，微粒群优化算法自动聚 类高维数据具备可行性以及广泛的应用前景。 。 关键词：微粒群优化算法；早熟收敛；高维数据；软投影聚类；自动确定聚类 数日 微粒群优化算法及其在高维数据聚类的应用研究 a b s t r a c t c l u s t e r i n gh i g h - d i m e n s i o n a ld a t ai sa l li m p o r t a n tb u td i f f i c u l tt a s ki nv a r i o u sd a t am i n i n g a p p l i c a t i o n s af u n d a m e n t a ls t a r t i n gp o i n tf o rd a t am i n i n gi st h ea s s u m p t i o nt h a tad a t a o b j e c t ，s u c ha st e x td o c u m e n t ，c a l lb er e p r e s e n t e da sah i g h d i m e n s i o n a lf e a t u r ev e c t o r t r a d i t i o n a lc l u s t e r i n ga l g o r i t h m ss t r u g g l ew i t hh i g h d i m e n s i o n a ld a t ab e c a u s et h eq u a l i t y o fr e s u l t sd e t e r i o r a t e sd u et ot h ec u r s eo fd i m e n s i o n a l i t y a st h en u m b e ro ff e a t u r e s i n c r e a s e s ，d a t ab e c o m e sv e r ys p a r s ea n dd i s t a n c em e a s u r e si nt h ew h o l ef e a t u r es p a c e b e c o m em e a n i n g l e s s u s u a l l y , i nah i g h d i m e n s i o n a ld a t as e t ，s o m ef e a t u r e sm a yb e i r r e l e v a n to rr e d u n d a n tf o rc l u s t e r sa n dd i f f e r e n ts e t so ff e a t u r e sm a yb er e l e v a n tf o r d i f f e r e n tc l u s t e r s t h u s ，c l u s t e r sc a no f t e nb ef o u n di nd i f f e r e n tf e a t u r es u b s e t sr a t h e rt h a n t h ew h o l ef e a t u r es p a c e c l u s t e r i n gf o rs u c hd a t as e t si sc a l l e ds u b s p a c ec l u s t e r i n go r p r o j e c t e dc l u s t e r i n g , a i m e da tf i n d i n gc l u s t e r sf r o md i f f e r e n tf e a t u r es u b s p a c e s o nt h e o t h e rh a n d ，t h ep e r f o r m a n c eo fm a n ys u b s p a c e p r o j e c t e dc l u s t e r i n ga l g o r i t h m sd r o p s q u i c k l yw i t ht h es i z eo ft h es u b s p a c e si nw h i c ht h ec l u s t e r sa r ef o u n d a l s o ，m a n yo ft h e m r e q u i r ed o m a i nk n o w l e d g ep r o v i d e db yt h eu s e rt oh e l ps e l e c ta n dt u n em e i rs e r i n g s ，l i k e t h em a x i m u md i s t a n c eb e t w e e nd i m e n s i o n a lv a l u e s ，t h et h r e s h o l do fi n p u tp a r a m e t e r sa n d t h em i n i m u md e n s i t y , w h i c ha r ed i f f i c u l tt os e t d e v e l o p i n ge f f e c t i v ep a r t i c l es w a r mo p t i m i z a t i o n ( p s o ) f o rc l u s t e r i n gh i g l a d i m e n s i o n a l d a t ai st h em a i nf o c u so ft h i st h e s i s f i r s t ，i no r d e rt oi m p r o v et h ep e r f o r m a n c eo ft h e c o n v e n t i o n a lp s oa l g o r i t h m ，w ea n a l y z et h em a i nc a u s e so ft h ep r e m a t u r ec o n v e r g e n c e a n dp r o p o s ean o v e lp s oa l g o r i t h m ，c a l li n f o r m p s o ，b a s e do np r i n c i p l e so fa d a p t i v e d i f f u s i o na n dh y b r i dm u t a t i o n i n s p i r e db yt h ep h y s i c so fi n f o r m a t i o nd i f f u s i o n ，w ed e s i g n af u n c t i o nt oa c h i e v eab e t t e rp a r t i c l ed i v e r s i t y , b yt a k i n gi n t oa c c o u n tt h e i rd i s t r i b u t i o na n d t h en u m b e ro fe v o l u t i o n a r yg e n e r a t i o n sa n db ya d j u s t i n gt h e i r “s o c i a lc o g n i t i v e a b i l i t i e s b a s e do ng e n e t i cs e l f - o r g a n i z a t i o na n dc h a o se v o l u t i o n , w eb u i l dc l o n a ls e l e c t i o ni n t o i n f o r m p s ot oi m p l e m e n tl o c a le v o l u t i o no ft h eb e s tp a r t i c l ec a n d i d a t e ，g b e s t ，a n dm a k e u s eo fal o g i s t i cs e q u e n c et oc o n t r o lt h er a n d o md r i f to fg b e s t t h e s et e c h n i q u e sg r e a t l y v l i 微粒群优化算法及其在高维数据聚类的应用研究 c o n t r i b u t et ob r e a k i n ga w a yf r o ml o c a lo p t i m a t h eg l o b a lc o n v e r g e n c eo ft h ea l g o r i t h mi s p r o v e du s i n gt h et h e o r e mo fm a r k o vc h a i n e x p e r i m e n t so no p t i m i z a t i o no fu n i m o d a la n d m u l t i m o d a lb e n c h m a r kf u n c t i o n ss h o wt h a t ，c o m p a r i n gw i t hs o m eo t h e rp s ov a r i a n t s ， i n f o r m p s oc o n v e r g e sf a s t e r , r e s u l t si nb e t t e ro p t i m a , i sm o r er o b u s t ，a n dp r e v e n t sm o r e e f f e c t i v e l yt h ep r e m a t u r ec o n v e r g e n c e t h e n , s p e c i a lt r e a t m e n t so fo b j e c t i v ef u n c t i o n sa n de n c o d i n gs c h e m e sa r ep r o p o s e dt o t a i l o rp s of o rt w o p r o b l e m sc o m m o n l ye n c o u n t e r e di ns t u d i e sr e l a t e dt oh i g h d i m e n s i o n a l d a t ac l u s t e r i n g t h ef i r s tp r o b l e mi st h ev a r i a b l ew e i g h t i n gp r o b l e mi ns o f tp r o j e c t e d c l u s t e r i n gw i t hk n o w nt h en u m b e ro fc l u s t e r s 豇w i t ht h ep r e s e tn u m b e ro fc l u s t e r s 岛t h e p r o b l e ma i m sa tf i n d i n gas e to fv a r i a b l ew e i g h t sf o re a c hc l u s t e ra n di sf o r m u l a t e da sa n o n l i n e a rc o n t i n u o u so p t i m i z a t i o n p r o b l e ms u b j e c t e d t ob o u n dc o n s t r a i n t s an e w a l g o r i t h m ，c a l l e dp s o v w , i sp r o p o s e dt oa c h i e v eo p t i m a lv a r i a b l ew e i g h t sf o rc l u s t e r s i n p s o v w , w ed e s i g nas u i t a b l ek - m e a n so b j e c t i v ew e i g h t i n gf u n c t i o n ，i nw h i c hac h a n g eo f v a r i a b l ew e i g h t si s e x p o n e n t i a l l yr e f l e c t e d w ea l s ot r a n s f o r mt h eo r i g i n a lc o n s t r a i n e d v a r i a b l ew e i g h t i n gp r o b l e mi n t oa p r o b l e mw i t hb o u n dc o n s t r a i n t s ，u s i n gan o n - n o r m a l i z e d r e p r e s e n t a t i o no fv a r i a b l ew e i g h t s ，a n dw eu t i l i z eap a r t i c l es w a r mo p t i m i z e rt om i n i m i z e t h eo b j e c t i v ef u n c t i o ni no r d e rt oo b t a i ng l o b a lo p t i m at ot h ev a r i a b l ew e i g h t i n gp r o b l e mi n c l u s t e r i n g o u re x p e r i m e n t a lr e s u l t so nb o t hs y n t h e t i ca n dr e a ld a t as h o wt h a tt h ep r o p o s e d a l g o r i t h mg r e a t l yi m p r o v e sc l u s t e rq u a l i t y i na d d i t i o n ，t h er e s u l t so ft h en e wa l g o r i t h ma r e m u c hl e s sd e p e n d e n to nt h ei n i t i a lc l u s t e rc e n t r o i d s t h el a t t e rp r o b l e ma i m sa ta u t o m a t i c a l l yd e t e r m i n i n gt h en u m b e ro fc l u s t e r sk a sw e l l 嬲 i d e n t i f y i n gc l u s t e r s a l s o ，i ti sf o r m u l a t e da san o n l i n e a ro p t i m i z a t i o np r o b l e mw i t hb o u n d c o n s t r a i n t s f o rt h ep r o b l e mo fa u t o m a t i c a ld e t e r m i n a t i o no f 毛w h i c hi st r o u b l e s o m et o m o s tc l u s t e r i n ga l g o r i t h m s ，ap s o a l g o r i t h mc a l l e da u t o p s oi sp r o p o s e d as p e c i a lc o d i n g o fp a r t i c l e si si n t r o d u c e di n t oa u t o p s ot or e p r e s e n tp a r t i t i o n sw i t hd i f f e r e n tn u m b e r so f c l u s t e r si nt h es a m ep o p u l a t i o n t h ed bi n d e xi se m p l o y e d 硒t h eo b j e c t i v ef u n c t i o nt o m e a s u r et h eq u a l i t yo f p a r t i t i o n sw i t hs i m i l a ro rd i f f e r e n tn u m b e r so fc l u s t e r s a u t o p s oi s c a r r i e do u to nb o t hs y n t h e t i ch i g h d i m e n s i o n a ld a t a s e t sa n dh a n d c r a f t e dl o w d i m e n s i o n a l v i i i 微粒群优化算法及其在高维数据聚类的应用研究 d a t a s e t sa n di t s p e r f o r m a n c ei sc o m p a r e dt o o t h e rs e l e c t e d c l u s t e r i n gt e c h n i q u e s e x p e r i m e n t a lr e s u l t si n d i c a t e t h a tt h e p r o m i s i n gp o t e n t i a lp e r t a i n i n g t oa u t o p s o a p p l i c a b i l i t yt oc l u s t e r i n gh i g h - d i m e n s i o n a ld a t aw i t h o u tt h ep r e s e tn u m b e ro fc l u s t e r s 疋 k e yw o r d s ：p a r t i c l es w a r mo p t i m i z a t i o n ；p r e m a t u r ec o n v e r g e n c e ；h i g h - d i m e n s i o n a ld a t a ； s o f tp r o j e c t e dc l u s t e r i n g ；a u t o m a t i c a l l yd e t e r m i n i n gt h en u m b e ro fc l u s t e r s i x 厦门大学学位论文原创性声明 本人呈交的学位论文是本人在导师指导下，独立完成的研究成 果。本人在论文写作中参考其他个人或集体已经发表的研究成果，均 在文中以适当方式明确标明，并符合法律规范和厦门大学研究生学 术活动规范( 试行) 。 另外，该学位论文为( ) 课题( 组) 的研究成果，获得() 课题( 组) 经费或实验室的 资助，在() 实验室完成。( 请在以上括号内填写课 题或课题组负责人或实验室名称，未有此项声明内容的，可以不作特 别声明。) 声明人( 签名) ：詈据耳 删铋月之e t 厦门大学学位论文著作权使用声明 本人同意厦门大学根据中华人民共和国学位条例暂行实施办 法等规定保留和使用此学位论文，并向主管部门或其指定机构送交 学位论文( 包括纸质版和电子版) ，允许学位论文进入厦门大学图书 馆及其数据库被查阅、借阅。本人同意厦门大学将学位论文加入全国 博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和 摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于： () 1 经厦门大学保密委员会审查核定的保密学位论文， 于年月日解密，解密后适用上述授权。 () 2 不保密，适用上述授权。 ( 请在以上相应括号内打“ 或填上相应内容。保密学位论文 应是已经厦门大学保密委员会审定过的学位论文，未经厦门大学保密 委员会审定的学位论文均为公开学位论文。此声明栏不填写的，默认 为公开学位论文，均适用上述授权。) 声明人( 签名) ： 年月日 名 1 獬 n 聪厢 1 微粒群优化算法及其在高维数据聚类的应用研究 第一章绪论 1 1研究目的 高维数据聚类是数据挖掘领域的重点和难点。数据挖掘的基本假设是一个 数据对象可表示为一个高维特征向量。超高维数据已成为现代信息工程的主 要特点之一。文本挖掘中，一个文本数据集可表示为一个矩阵，每一行表示一 个文档，每一列代表一个关键词。因而，文本数据集的维数也就是关键词数目， 通常是几千几万维。高维数据聚类另外一个应用是保险公司客户潜力预测【1 】， 对于保险公司而言，将客户群分组有利于帮助预测哪些潜在客户将购买其保险 产品。高维数据聚类还有许多类似应用，比如信用分析、银行客户破产预测、 网页挖掘、基因序列分析和预测蛋白质功能等。 聚类高维数据是聚类分析的一大难点，因为高维数据聚类需要用较低维的 特征空间去拟合超高维数据的数据对象，不同聚类存在着各自的特征子空间， 并且，它们的特征子集是可重叠的。譬如，在一个文本数据集中，某个特定主 题的文档一般可用一个关键词子集来描述；有关于“电子”这一主题的文档， 可用关键词电子、信号、电路等来刻画；而描述主题“运动员 的关键词子集 是不会与“电子的关键字子集有交集，却有可能与描述另一主题“体育 的 关键词子集重叠。 维数灾难问题大大降低了传统的聚类方法聚类高维数据的质量。当特征维 数增长时，数据对象在高维空间中分布非常稀疏，传统聚类方法基于所有维上 的距离的聚类变得毫无意义；其次，高维数据集存在大量无关的属性特征，数 据对象之间趋于等距是普遍现象，因而所有维中存在簇的可能性几乎为零。当 不同簇之间的相关特征集合完全不一样时，这种距离相等的情况更是加剧。实 微粒群优化算法及其在高维数据聚类的应用研究 际上，对一个簇而言，通常存在着大量不相关或是冗余的特征：而不同簇之间 的相关特征子集又是不一样的。因而，高维数据聚类更应该是在不同特征子空 间发现簇，而不是在所有维度空间去寻找簇。 聚类上述这类数据称为子空间聚类或投影聚类，它们尝试在不同子空间发 现聚类。一般的子空间聚类技术在于发现有效分离聚类的特征子空间，例如 2 ，3 ，4 。子空间聚类算法搜索到的聚类通常是可重叠的，而投影聚类则将数 据集划分不交叉的聚类，例如 6 ，7 ，8 。投影聚类通常在不同特征子空间搜索 聚类，每一子空间一般是以几个基向量( 主轴) 来表示。( 目前现有研究文献 中，有关于子空间聚类和投影聚类这两个概念的界线是不一样的。) 然而，许 多子空间投影聚类算法的性能随着子空间规模增长而迅速下降 9 】。并且，有 些算法需要用户提供专门的领域知识来调节设置它们的输入参数，必如维内数 值的最大距离 5 、输入参数的阈值 6 ，7 、数据最小密度 2 ，3 等，而这些参 数往往很难设置。 近年来，不少研究学者提出了软投影聚类算法，即通过赋予每一聚类一个 最优变量权值向量来识别聚类 1 0 ，1 1 ，1 2 ，1 3 。软投影聚类算法通过迭代最小 化某个目标函数，数据对象之间的距离是在整个维度空间进行的，但是该维 度空间是被加权的。变量权值转换了距离，使得高维空间中聚类中的数据对象 被重塑成密度高的超球体，因而容易被聚类算法有效识别。软投影聚类算法依 赖于搜索策略和评测标准来驱动。因此，如何定义一个有效的目标函数以及如 何高效地搜索到最优变量权值是软投影聚类的两大问题。 高维数据聚类的另一难点是给定一数据集，如何自动确定聚类数目。目前， 大多数子空间聚类算法需要聚类数目作为输入参数，而当数据集的结构未知 时，往往很难确定正确的聚类数目。在聚类分析中，已有一些聚类算法 1 4 ，1 7 ， 1 8 ，1 9 ，2 0 提出如何自动获得聚类数目，然而，它们均不适合于高维子空间 数据聚类。综上所述，高维子空间数据本身固有的一些属性，必如稀疏性和数 据对象的等距性等，使得高维变量空间中聚类的识别非常困难。因此，非常有 2 微粒群优化算法及其在高维数据聚类的应用研究 必要去分析和设计新型有效的算法来聚类高维数据。 对于上述高维数据聚类存在的两个问题，我们通过微粒群优化算法获得其 数值解。微粒群优化算法是一种基于群智能的启发式算法，近期得到研究学者 的大量关注。对于许多优化问题，传统p s o 算法及其变种在合理的运算时间内， 以相对稳定的收敛特性可产生高质量的解。因而，它们被有效地应用到各个优 化领域。近年来，一序列的文献集中在p s o 的应用上，比如神经网络训练 4 5 、 电力和电压控制 4 6 、任务分配 4 7 、单机排程问题 4 8 以及自动钻井问题 4 9 等。本论文中，传统微粒群优化算法被改进以提高其性能，使得更适合优化上 述的两个问题。 1 2 研究进展 1 2 1 微粒群优化算法相关研究 自p s o 算法在1 9 9 5 年被提出后，由于概念简单，易于实现，计算高效， 吸引了众多学者的极大关注。然而，当解决复杂优化问题时，p s o 算法也存在 早熟收敛问题，因此，学者们致力于从p s o 的各个方面来提高其性能，产生了 许多有趣的变种。主要分为以下三类。 第一类是通过调整p s o 速度更新公式中的已有参数或引入不同的参数提 高其性能。e b e r h a r t 等 2 5 在p s o 算法中引入一个惯性权值参数，以平衡算法 的全局和局部搜索能力。他们提出该惯性权值随迭代过程线性递减，即著名的 p s o w 算法。他们认为，大的惯性权值有利于全局搜索，而小的惯性权值则对 局部搜索有利；在算法初期，微粒应该侧重于全局搜索，而在迭代后期，侧重 于局部寻优。该理论使得后来的文献都引用p s ow 算法。在文献 2 6 ，他们 又提出一种模糊的方法非线性改变惯性权值。c l c r c 等 2 7 通过分析p s o 的收 敛行为，引入另一参数收缩因子。收缩因子保证p s o 收敛，且收敛速度更快。 除了随迭代次数变化而变化的惯性权值，f a n 等人在文献 2 8 1 引入随迭代过程 3 微粒群优化算法及其在高维数据聚类的应用研究 线性递减的最大飞行速度v m a x 。 第二类是致力于设计不同类型的拓扑来提高算法性能。k e n n e d y 等在文献 2 9 ，3 0 3 发现小邻域p s o 在复杂优化问题上可获得较好性能，而大邻域p s o 则在简单问题优化上取得较好性能。s u g a n t h a n 等 3 5 发展一个动态可调整的 邻域。首先，微粒的邻域是微粒本身，然后，微粒的邻域逐渐动态变大，直至 包含整个种群。在文献 3 1 ，h u 和e b e r h a r t 提出了另一个动态邻域方法，每 个微粒总是将其k 个距离最近微粒作为邻域。p a r s o p o u l o s 等提出了u p s o 3 2 】， 将全局和局部邻域结合一起。k e n n e d y 等在文献 3 3 】引入f i p s ，提出用微粒的 邻域代替p b e s t 和g b e s t 更新速度。每个微粒对其邻域的影响基于其适应度值 和邻域规模被加权。v e e r a m a c h n e n i 等设计了f d r p s o 3 4 ，设计最近邻域交互， 当更新一个微粒的速度时，分别更新其每一维，并且选择该微粒的邻域，若其 比微粒更优秀，则替代微粒的g b e s t 更新微粒。 第三类是将p s o 和其它搜索技术相结合，形成混合p s o 提高算法性能， 进化算子如精英选择算子被引入使得p s o 保留最优微粒 3 6 ；交叉算子被引入 提高种群的多样性e 3 7 ，3 8 以及变异算子 3 9 被引入增加微粒逃离局部最优的 能力。 4 0 引入小生境防止冲突机制避免微粒在移动过程中过分接近其它微 粒，保持群体多样性。 4 1 发展了当微粒太靠近其它微粒时，重新初始化该微 粒，增强逃离局部最优能力。负熵值 4 2 被用来防止早熟收敛现象。 2 2 发展 了一p s o ，其中，种群被分为很多小种群，哺育算子被采用在小种群内部或者 不同小种群之间提高种群多样性。c p s 0 - h 4 4 采用一维种群单独搜索一维的 最优值，这些搜索的结果再被一全局种群整合，这个方法有效改善多峰函数的 优化性能。 1 2 2 软投影聚类算法相关研究 假设一数据集的聚类数目已知，软投影聚类为每一类的每一维变量分配一 个权值，然后在加权的维度空间找到聚类，这就是变量加权问题。通常，与一 4 微粒群优化算法及其在高维数据聚类的应用研究 个聚类紧密相关的变量子集可获得大权值，这意味着这些变量对于该类的形成 贡献非凡。对于一个聚类而言，不相关的变量只能获得小权值。因而，一数据 对象的类属成员关系不单单依赖于聚类中心，且依赖于变量权值。并且，聚类 后，每个聚类可通过权值识别其最相关变量集合。 近年来，一些软投影聚类算法已被相继提出来识别聚类，同时为聚类选择 相关变量。c d o m e n i c o n i 等人 5 4 ，5 5 提出了l a c 算法2 0 0 7 年，作者在最新的 l a c 算法中使用了一个新型目标函数以及变量权值更新方式，他们的工作与 e w k m ( 2 0 0 7 ) 非常相似。在2 0 0 7 年的l a c 中，为了解决聚类结果对初始聚类 中心敏感，作者也提出选择足够分离的数据对象做为初始聚类中心。此外，他 们亦发展了一种综合聚类结果的方法来克服调节参数h 的困难。然而，他们的 初始化过程需要计算高维数据在所有维数空间上的距离，而软投影距离的基本 假设则是数据对象在所有维上的距离是不可靠的，况且，是否这种初始化进程 提高了l a c 聚类性能尚未明确。 在文献【5 6 】， j o s h u az h u a n g 等人提出了最小化另外一个目标函数的 w - k - m e a n s 算法w - k - m e a n s 算法是k m e a n s 算法的直接扩展。w 七m e a n s 为每 一维分配一权值，尽量在加权的变量空间里最小化聚类内部距离的累加。其变 量权值的更新依赖于参数1 3 的数值，此外，w - k m e a n s 算法没有使用一个有效 的局部搜索策略，所以，通常w - k - m e a n s 算法不能识别嵌在变量子空间的聚类。 因而，这个算法不适合聚类高维数据，因为这一类型数据集中的每一聚类通常 均有自己的相关变量子集。 l i p i n gj i n g 等人在文献 5 7 】提出了一种熵加权k - m e a n s 算法( e w k m ) ，这种 算法也是采用与w - k - m e a n s 和l a c 算法相似的迭代过程来获得最终的变量权 值。e w k m 的目标函数由两部分组成，一是聚类内部距离累加，二是权值熵。 该函数描述如下e w k m 的目标函数公式( 3 9 ) 非常依赖参数y 值的选择。若丫 值太小，则熵部分对函数值影响微弱；若丫值太大，则熵部分对目标函数值的 影响又太大。因而，丫通常是经验取值，且面向特定应用取值的。 5 微粒群优化算法及其在高维数据聚类的应用研究 1 2 3 自动确定聚类数目相关研究 聚类分析的一大基本难点是决定聚类数目。现存的许多著名的聚类算法往 往需要用户输入聚类数目，而在实际生活中，数据集的结构通常是未知而又复 杂的，提供一个合适的聚类数目非常的困难。这种情况下，在聚类过程中如何 自动决定聚类数目是聚类算法的一大挑战。 对于给定一个目标函数，随机搜索算法通常能达到其最优或近优解，由于 这一良好的搜索性能，有效地自动确定聚类数目的方法之一是进化技术。在这 一方向上，遗传算法( g a ) 被频繁运用于自动聚类。通常，g a 中染色体编码 聚类结果有两种方式，基于划分的编码和基于聚类中心的编码。基于划分的编 码将第f 个基因表示第i 个数据对象的类属关系，是数据对象的聚类成员关系 的一种直接表示。然而，这种直接表示方法使得聚类搜索空间非常庞大，且很 难发展有效的搜索算子。由于这一重大缺陷，许多研究者选择使用基于聚类中 心的编码方式，其主要思想源自于著名的k m e a n s 算法。每个染色体被表示成 为具有固定聚类数目的聚类中心，每个数据对象然后可被分配隶属于距离最近 的聚类中心所代表的聚类。 文献 i s ，1 6 中，b a n d y o p a d h y a y 和m a u l i k 发展了一个遗传算法求解聚类问 题。该算法中，种群的一个个体被编码为一个可变长度的实数串，用于表示聚 类中心所对应的坐标。个体f 可被编码为长度为朋岛的实数串，其中，m 代表 数据集的变量数目而觑代表第i 个个体的聚类数目。特别的交叉和变异算子也 被发展适合于可变长度的实数编码。他们又于2 0 0 2 年在文献提出一种固定长 度的串编码可变聚类数目划分的方法，这种固定长度的串由实数和一种特殊的 符号撑组成，实数代表聚类中心坐标。这两个遗传算法被作者证明能够进化聚 类数目的同时有效识别聚类。然而，他们的实验测试集趋向于球形而又低维的 数据集。 t s e n g 和y a n g 7 2 于2 0 0 1 年提出了另一算法自动求解聚类问题。他们的算 6 微粒群优化算法及其在高维数据聚类的应用研究 法分为两个阶段，最近邻聚类阶段和遗传聚类阶段。在最近邻聚类阶段，数据 集被分裂为很多规模小的聚类；在遗传聚类阶段，小的聚类被合并成大类。他 们的遗传聚类算法能够自动搜索一个合适的聚类数目，适用于聚类含有紧致 的、球形的聚类的数据集。该算法也被应用于大数据集高维聚类，譬如，2 0 ，0 0 0 维。然而，他们的算法不能识别互相嵌套或是部分重叠的聚类数据集。 对于聚类问题，l a i 于2 0 0 5 年【7 3 】设计了层次遗传聚类算法。该算法中， 每个个体由两种类型基因组成，控制基因和参数基因。控制基因编码成二进制 数，该二进制数中，1 的个数代表聚类数目。参数基因则编码为实数，代表聚 类中心坐标。参数基因受控制基因控制，若控制基因为l ，则对应的参数基因 生效；否则，则失效。 l i n 等又于2 0 0 5 年 7 4 】提出了另一个遗传算法。该算法中，个体是用二进 制编码而不是实数编码来表示可变聚类数目。该算法直接从数据集里选择聚类 中心，通过预先构建一个查询表格节省数据对象之间距离计算来加速适应度的 评估，并且提出了适合该算法中编码的遗传算子。该算法已被作者证明可稳定 地确定聚类数目和识别聚类。 在文献【7 5 中，l i n 等又发展了一个遗传算法自动求解聚类。他们引用了文 献 1 5 中同样的编码来表示聚类中心的坐标，同时为新算法设计了两个新型的 遗传算子，噪声选择和吸收分支变异。该算法被证明能自动识别聚类数目。 文献【1 7 ，7 1 】中，h a n d l e 等设计了一个多目标遗传聚类算法m o c k 来解决 聚类问题。他们采用基于图论连接的编码 7 1 】，每个个体由刀个基因组成。其 中，n 是数据集中数据对象的规模，第f 个基因从区间【l ，玎】中随机取整数值， 这意味着数据对象i 和，有一连接，属于同一个聚类。m o c k 优化两个互补聚 类目标函数，聚类内部紧致性和连接性。m o c k 能够自动进化和评估数据集中 聚类数目。在复杂形状的二维数据集，譬如，球形、椭球形、长形以及大量重 叠聚类的数据集上，m o c k 能够获得高质量的聚类结果。然而，它却不易应用 7 微粒群优化算法及其在高维数据聚类的应用研究 到高维子空间数据。 1 3 研究目标和研究内容 本文在综合分析高维数据聚类问题的发展现状及存在的不足后，通过研究和改进 p s o 算法并将其应用到到高维数据聚类问题中，解决该问题中的两大难点问题：软投 影聚类中的变量加权及自动确定聚类数目。 论文主要工作有以下三点： 1 ) 为了克服传统微粒群算法早熟收敛问题，本文提出了一个微粒群优化算法 变种。在分析了标准p s o 算法早熟收敛的原因的基础上，我们提出了自适应扩 散混合变异机制微粒群算法( i n f o r m p s o ) 。结合生物群体信息扩散的习性，设计 了一个考虑微粒分布和迭代次数的函数，自适应调整微粒的“社会认知”能力，提 高种群的多样性；模拟了基因自组织和混沌进化规律，引入克隆选择使群体最佳 微粒g b e s t 实现遗传微变，局部增值，具有变异确定性；利用l o g i s t i c 序列指导 g b e s t 随机漂移，进一步增强逃离局部极值能力。基于种群的随机状态转移过程， 证明了新算法具有全局收敛性。与其它几种p s o 变种相比，复杂基准函数仿真优 化结果表明，新算法收敛速度快，求解精度高，稳定性好，能有效抑制早熟收敛 2 ) 我们设计一个微粒群优化算法( p s o