（计算机软件与理论专业论文）蚁群算法的聚类分析研究及在hrm中的应用.pdf

四川大学硕士学位论文 蚁群算法的聚类分析研究及在h r m 中的应用 计算机软件与理论专业 研究生翁怀荣指导教师张洪伟 随着网络技术和数据库技术的快速发展，计算机已经能够存储大规模的海量 的数据，另一方面，传统的数据分析处理工具如管理信息系统对这些数据只能 进行表层的处理，而更深层次的数据分析能力却不尽如人意，这样，数据供给 能力和数据分析能力间的矛盾日益突出，因此迫切需要一种能够对数据进行深 层次加工的自动化技术。由此。数据挖掘技术应运而生。聚类分析作为数据挖 掘中的一个重要课题，它是将数据区分为自然的群体，并给出每个群体特征描 述的一种数据挖掘方法，是数据挖掘和知识发现的一种基本方法。聚类分析是 在无先验知识无指导下进行数据无监督分类的一种数据挖掘技术通过先进算 法的恰当采用，发掘潜藏的有价值的信息，提高数据分析和解释的质量，也为 后续其它数据分析和整理工具对数据的再处理或理解提供科学的判断依据。因 此，研究如何提高聚类分析算法的性能具有重要意义 聚类分析的算法很多，比较著名的有模糊卜均值算法、肛中心点算法、c 均 值算法、f c m 算法等。蚁群算法是最近几年才提出的一种新的生态类优化算法， 其主要特点是正反馈、分布式计算。初步的研究表明，它是一种基于种群的鲁 棒性较强的算法，具有许多优良的性质，为求解复杂的组合优化问题提供了一 种新思路。本文根据蚁群算法的最新研究，对蚁群算法进行了改进，引入随机 扰动和蚂蚁的感觉知觉特征，并与k _ 均值算法相结合，提出了一种新的聚类算 法：改进蚁群算法，并建立了改进蚁群算法的聚类分析模型通过仿真实验表 明，当模式样本和分类数很大时，改进蚁群算法的聚类分析在解决多聚类问题 比传统聚类算法更有效。 四川大学碗士学位论文 在将理论技术应用到实践方面，本文在分析了中国企业现有的绩效评估体系 现状以及现有绩效评估方法缺陷的基础上，根据本人参与开发h 跚系统的经验， 将基于改进蚁群算法的聚类分析方法应用于员工绩效评估中，具体做法为：根 据员工的各种绩效评估指标，首先建立员工绩效评估的聚类分析模型，然后采 用改进蚁群算法对员工进行聚类。通过聚类，从而对公司的员工有效地进行分 类，有了这些分类，就能为人事规划和人事调整提供有效的决策支持。 本文首先简要介绍了聚类分析的原理、发展、聚类分析方法，阐述了聚类分 析的应用。然后阐述了基本蚁群算法的原理，分析了基本蚁群算法的优点及不 足，并阐述了现有的几种改进方法。有了以上的理论基础，提出了改进蚁群算 法( i a c a ) 以及基于i a c a 的聚类分析模型，并给出了相应的算法流程和实现， 并进行了仿真实验，和其他聚类分析算法进行了比较。之后，本文在第三章简 要介绍了人力资源管理理论和绩效评估理论，分析了现有的几种绩效评估方法 及其它们的优点和缺陷。并结合本人的项目开发经验，将改进蚁群聚类算法应 用在员工绩效评估系统中，并在第四章实现了一个完整的基于改进蚁群算法聚 类分析的员工绩效评估系统。通过大量的数据测试以及结果分析发现，本文提 出在基本蚁群算法的基础上引入随机扰动和感觉知觉特征的改进蚁群算法 ( i a c a ) ，在聚类过程中，能够很好地避免算法出现停滞，并能够避免算法陷入 局部最优，从而更好地达到全局优化的目的，使聚类的整体性能达到优化。进 而应用在员工绩效评估系统中，为绩效评估员工分类提供了一种科学、客观的 依据 文章最后对整个算法和系统的开发设计工作做了总结，提出了下一步的工 作，并提出了一些展望。该系统已成功应用于国内某大型集团公司，为该公司 的员工绩效评估员工分类提供了一个更新的、更公平公正的解决方案。 关键词：数据挖掘，聚类分析，蚁群算法，改进蚁群算法( i a c a ) ，人力资源管 理( h r m ) ，绩效评估 凹川大字坎士字位论文 c l u s t e r i n gp r o b l e m b a s e do na n t c o l o n ya l g o r i t h m a n di t sa p p l i c a t i o ni nh r m m a j o rc o m p n t 盯s o f t w a r e & t h e o r y s t u d e n t ：h u a k o n gw e n gt u t o r ：p r o f ih o n g w e iz h a n g a b s t r a e t ： a l o n gw i t hf a s td e v e l o p m e n to fn e t w o r kt e c h n o l o g ya n dd a t a b a s et e c h n o l o g y ， t h ec o m p u t e rc a ns a v et h el a r g e - s c a l ed a t a o nt h eo t h e rh a n d ，t h et r a d i t i o n a ld a t a a n a l y s i st o o l ss u c ha st h em a n a g e m e n ti n f o r m a t i o ns y s t e mc a no n l yp r o c e e dw i t h s u r f a c eo ft h ed a t a , a n dt h ed e 印d a t ap r o c e e d i n gc a p a b i l i t yi sn o tw e l l t h ec o n f l i c t b e t w e e nt h ec a p a b i l i t yo ft h ed a t as u p p l ya n dt h ec a p a b i l i t yo ft h ed a t aa n a l y s i si s m o r ea n dm o r e ：p r o m i n e n t s oak i n do fa u t o m a t i z a t i o nt e c h n o l o g yi si m m i n e n t l y n e e d e dt od e e p l yp r o c e e dw i t ht h ed a t a a tt h i st i m e ，t h et e c h n o l o g yo fd a t am i n i n g h a sb e e np u tf o r w a r d a so n eo ft h em o s ti m p o r t a n td o m a i no fd a t am i n i n g , c l u s t e r i n ga n a l y s i s c l a s s i f i e st h ed a t ai n t on a t u r a lc o m m u n i t i e sa n dg i v ee a c h c o m m u n i t yc h a r a c t e r i s t i cd e s c r i p t i o n c l u s t e r i n ga n a l y s i si so n eo ft h eb a s i c m e t h o d s o ft h ed a t am i n i n ga n dk n o w l e d g ef m d i n ga n di ti san o n - s u r v e i l l a n c ed a t a c l a s s i f i c a t i o nm e t h o d b yu s i n gt h ea d v a n c e da l g o r i t h m , w ec a nf i n dt h eu s e f u l i n f o r m a t i o na n di m p r o v et h eq u a l i t yo fd a t aa n a l y s i sa n de x p l a i n t h i si n f o r m a t i o n c a nh et h ef o u n d a t i o no fo t h e rd a t aa n a l y s i st o o l sf o rr e a n a l y z i n gt h ed a t a b e c a u s e o ft h e ；| b o v er e a s o n s , i t sv e r ys i g n i f i c a f i v ef o ru st or e s e a r c hh o wt oi m p r o v et h e p e r f o r m a n c e o ft h ec l u s t e r i n ga n a l y s i sa l g o r i t h m t h e r ea r cm a n y c l u s t e r i n ga n a l y s i sa l g o r i t h m s t h ef a m o u sa l g o r i t h m sa r et h e s e ： k - m e a n sa l g o r i t h m , k - c e n t e ra l g o r i t h m , c - m e a u sa l g o r i t h m , f c ma l g o r i t h ma n ds o o i la n tc o l o n ya l g o r i t h mi san e we c o t y p i o o p t i m i z a t i o na l g o r i t h ma n di t s 四川大学硕士学位论文 c h a r a c t e r i s t i c sa r e p o s i t i v ef e e d b a c k a n dd i s t r i b u t e dc o m p u t i n g i t si n d i c a t e dt h a ta n t c o l o n ya l g o r i t h mi sar o b u s ta l g o r i t h ma n di th a sm a n ye x c e l l e n tc h a r a c t e r s t h i s a l g o r i t h mg i v e s 惦an e wm e t h o dt os o l v et h ec o m p l i c a t e do p t i m i z a t i o np r o b l e m s a c c o r d i n gt ot h en e w l yr e s e a r c ho fa n tc o l o n ya l g o r i t h m ，a ni m p r o v e da n tc o l o n y a l g o r i t h mi sp u tf o r w a r di nt h i sa r t i c l e i m p r o v e da n tc o l o n ya l g o r i t h m ( i a c a ) i m p o r t sr a n d o md i s t u r b i n ga n dt h ef e e l i n gc h a r a c t e ro ft h ea n t sa n dc o m b i n e s w i t h t h ek - m e a n sm e t h o d t h e nt h ea u t h o re s t a b l i s h e sac l u s t e r i n ga n a l y s i sm o d e l ，w h i c h b a s e do ni a c a a c c o r d i n gt ot h er e s u l to ft h ee x p e r i m e n t , i ti sp r o v e dt h a tt h e c l u s t e r i n ga n a l y s i sm e t h o dw h i c hb a s e do ni a c ai s m o r ee f f e c t i v et h a nt h e t r a d i t i o n a l c l u s t e r i n ga n a l y s i sa l g o r i t h m sw h e nt h es t y l e b o o ka n dt h en u m b e ro f c a t e g o r i e sa r el a r g e b e c a u s ei a c ai sa ne f f e c t i v ea l g o r i t h m ，t h ea u t h o ru s e dt h i sa l g o r i t h mt os o l v e e m p l o y e e s p e r f o r m a n c ee v a l u a t i o ni no n ec o m p a n y w i t ht h ee x p e r i e n c e st h a tt h e a u t h o r sd e v e l o p i n gt h e s y s t e m o fh r ma n dt h e a n a l y s i s e s o ft h ec u r r e n t p e r f o r m a n c e e v a l u a t i o nm e t h o d ，an e wp e r f o r m a n c ee v a l u a t i o nm e t h o di sp u t f o r w a r di nt h i sp a p e r t h i sm e t h o di sa ne m p l o y e ep e r f o r m a n c ee v a l u a t i o nc l u s t e r i n g m o d e l ，w h i c hb a s e do ni m p r o v e da n tc o l o n ya l g o r i t h m t h ed e t a i lm e t h o d i st h a t ： a tf i r s t ，a c c o r d i n gt oe v e r yk i n do fe m p l o y e e sp e r f o r m a n c ee v a l u a t i o ni n d e x ，t h e e m p l o y e ep e r f o r m a n c e e v a l u a t i o n c l u s t e r i n g m o d e li se s t a b l i s h e d t h e nt h e e m p l o y e e sa r ec l u s t e r e da n dc l a s s i f i e db yu s i n gi m p m v e da n tc o l o n ya l g o r i t h m a n d t h ec l a s s i f i c a t i o nr e s u l tc a no f f e rd e c i s i o ns u p p o r tf o rp e r s o n n e lp r o g r a ma n d a d j u s t i n g i nt h i sa r t i c l e ，t h ea u t h o ri n t r o d u c e st h ep r i n c i p l e so ft h ec l u s t e r i n ga n a l y s i sa n d a n tc o l o n ya l g o r i t h m t h ep r i n c i p l e si n c l u d e st h ec l u s t e r i n gt h e o r y , t h ec l u s t e r i n g m e t h o d sa n dt h e i ra p p l i c a t i o n s ，t h et h e o r ya n di t sc h a r a c t e r i s t i c so fa n tc o l o n y a l g o r i t h ma n ds o m ei m p r o v e da n tc o l o n ya l g o r i t h m b a s e do na b o v et h e o r i e s , t h e n e wc l u s t e r i n ga n a l y s i sm e t h o d , w h i c hb a s e do ni m p r o v e da n tc o l o n ya l g o r i t h m ，i s p u tf o r w a r di nt h i sp a p e r , w h i c hi sn a m e di a c a f o rs h o r t t h e nt h ea u t h o rr e a l i z e s t h ei m p r o v e da n tc o l o n ya l g o r i t h m ( i a c a ) a n dd e s i g na ne m u l a t o r w i t ht h e e m u l a t o r , t h ei a c ai sc o m p a r e dw i t ho t h e rc l u s t e r i n ga n a l y s i sa l g o r i t h m s i n 四川大学硕士学位论文 c h a p t e r3 ，t h ea u t h o ri n t r o d u c e st h eh u m a nr o s o u r e om a n a g e m e r i tt h e o r i e sa n d e x p a t i a t e so nt h ef i x e dp o s i t i o no ft h ep e r f o r m a n c ee v a l u a t i o ni nh u m a nr e s o u l c e m a n a g ef i r s t l y , a n dt h e na n a l y s e st h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h ec u r r e n t p e r f o r m a n c e e v a l u a t i o nm e t h o d s a f t e rt h a t , t h ei n t e g r a n t k n o w l e d g eo f t h e e m p l o y e ep e r f o r m a n c ee v a l u a t i o nc l u s t e r i n gm o d e li se x p a t i a t e d i nc h a p t e r4 t h e a u t h o rr e a l i z e sa c o m p l e t ee m p l o y e ep e r f o r m a n c ee v a l u a t i o ns y s t e m a c c o r d i n gl a r g e n u m b e r so fd a t at e s ta n dr e s u l ta n a l y s i s ，i ti sp r o v e dt h a tt h ei m p r o v e da n tc o l o n y a l g o r i t h mw h i c hi sb a s e do n a n tc o l o n ya l g o r i t h ma n di m p o r t e dr a n d o m p e r t u r b a t i o n a n dc h a r a c t e r i s t i c so fs e n s a t i o na n dc o n s c i o u s n e s sc a na v o i di b es t a g n a t i o no ft h e a l g o r i t h m , a v o i dt h ep a r ts u p e r i o ra n da t t a i nt h eo v e r a l le x c e l l e n to p t i m i z a t i o n s oi t e a rm a k et h ew h o l ec a p a b i l i t yo fi a c at oa t t a i no p t i m i z a t i o n t h e ni ti sa p p l i e di n e m p l o y e ep e r f o r m a n c ee v a l u a t i o ns y s t e ma n d p r o v i d e dak i n do fs c i e n c e , o b j e c t i v e w a yf o re m p l o y e ep e r f o r m a n c ee v a l u a t i o na n dc l a s s i f i c s t i o n f i n a l l y , t h i sp a p e rs u m m a r i e st h ew h o l ew o r ka n dp u t sf o r w a r dt h ef u r t h e rw o r k a n de x p e c t a t i o n t h ee m p l o y e ep e r f o r m a n c ee v a l u a t i o ns y s t e mh a sb e e ns u c c e e d e d t oa p p l yi no n el a r g eg r o u pc o m p a n ya n dg i v et h ee m p l o y e e sa e q u i t a b l es o l u t i o nf o r e m p l o y e e s p e r f o r m a n c ee v a l u a t i o na n de m p l o y e e s c l a s s i f i c a t i o n k e y w o r d s ：d a t am i n i n g , c l u s t e r i n ga n a l y s i s ，a n tc o l o n ya l g o r i t h m ，i m p r o v e da n t c o l o n ya l g o r i t h m ( i a c a ) , h u m a nr e s o u r c em a n a g e m e n t ( a r m ) ，p e r f o r m a n c e e v a l u a t i o n 四川大学硕士学位论文 1 引言 近年来，科学技术飞速发展，带动人类社会进入了一个高速文明的时期特 别是2 0 世纪9 0 年代以来，计算机技术、信息技术和互联网技术的迅猛发展， 人们在生产生活的各个领域都积累了十分丰富的数据，这些海量的数据不仅促 进了数据库技术的发展，也使人们获得大量的数据变得轻而易举然而，另一 方面，面对大规模的海量数据，人们不再满足于数据的查询和处理，迫切希望 能够对这些数据进行进一步的分析，找出数据之间的关联性，并从中提出有用 的信息，以帮助人们进行决策分析和科学研究等。要达到这些要求，传统的数 据库技术显然是无能为力了，因此，人们迫切需要一种能够智能自动地把数据 转换成有用的信息和知识的技术和工具于是，人们结合数据库，统计学和机 器学习等技术理论，提出用数据挖掘技术来解决这一问题。这样，数据挖掘技 术应运而生，并逐渐成为计算机科学领域研究的热点，吸引了很多专家学者研 究，显示出了强大的生命力聚类分析作为数据挖掘技术中的一个重要课题， 近年来也越来越受到研究学者的关注它是将数据区分为自然的群体，并给出 每个群体特征描述的一种数据挖掘方法，是数据挖掘和知识发现的一种基本方 法 1 1 问题的提出 “物以类聚，人以群分”，聚类分析也正是基于这个出发点的一种数据分析 处理技术。概括来讲，聚类分析是在无先验知识无指导下进行数据无监督分类 的一种数据挖掘技术通过先进算法的恰当采用，发掘潜藏的有价值的信息， 提高数据分析和解释的质量，也为后续其它数据分析和整理工具对数据的再处 理或理解提供科学的判断依据聚类分析是一种重要的数据分析技术，同时， 聚类分析作为数据挖掘的一个重要研究方向，现在已经在很多领域中得到广泛 的应用，如电子商务、市场营销、生物学、模式识别，图形图像等领域通过 聚类分析，能够发现数据的分布模式以及数据之间的相互联系在市场营销上， 聚类分析能帮助销售人员通过客户的基本信息和购买能力来对客户进行有效的 l 四川大学硕士学位论文 分类，划分出不同的客户群并提取出相应盼客户群特征。在生物学上，聚类分 析可以动植物进行分类，得到不同的生物种群，获得对种群固有结构的认识。 要得到一个好的聚类效果，要根据不同样本的要求选择一个最佳的算法，目 前，对聚类分析算法的研究有很多，有传统聚类算法也有现代聚类算法比较 著名的有划分法如模糊k _ 均值算法、k 中心点算法，基于密度的方法如0 p t i c s 算法，模糊聚类发如c 均值f c m 算法等。 蚁群算法是最近几年才提出的一种新的生态类优化算法，是2 0 世纪9 0 年代 初由意大利学者d o f i g 等提出来的，他们称之为蚁群系统( a n tc o l o n ys y s t e l n a c s ) 。它是依照蚂蚁觅食以及蚂蚁筑巢原理，设计出的一个群体智能算法其 主要特点是正反馈、分布式计算。初步的研究表明，它是一种基于种群的鲁棒 性较强的算法，具有许多优良的性质，为求解复杂的组合优化问题提供了一种 新思路。本文在分析了其他聚类算法的优缺点之后，根据蚁群算法的最新研究， 对蚁群算法进行了改进，引入随机扰动和蚂蚁的感觉知觉特征，并与k _ 均值算 法相结合，提出了一种新的聚类算法：改进蚁群算法，并建立了改进蚁群算法 的聚类分析模型通过实验和实际应用结果表明，当模式样本和分类数很大时， 改进蚁群算法的聚类分析在解决多聚类问题比传统聚类算法更有效。 1 2 本文的主要工作 本文对蚁群算法聚类分析模型进行了较深入的研究，主要提出了改进蚁群算 法，并给出了算法流程和实现，同时进行了基于改进蚁群算法的聚类分析业务 建模，实现了一个采用改进一群算法的员工绩效评估系统。具体所做的工作如 下： 在理论方面，详细阐述了聚类分析和蚁群算法的原理，并针对几种蚁群 算法方法的缺点，引入了随机扰动策略和蚂蚁的感觉知觉特征，然后结 合k 均值聚类分析方法，提出了一种新的聚类方法：基于改进蚁群算 法的聚类分析方法，并设计了基于改进蚁群算法的聚类分析模型，同时 给出了具体的算法步骤和算法实现，最后进行了仿真实验分析，将本文 算法和k - 均值算法、模糊c 均值( f c m ) 算法、基本蚁群算法等聚类分 析算法进行比较。实验结果表明，将i a c a 算法用于聚类，比传统聚类 2 四川大学硕士学位论文 算法聚类结果更优，速度更快，并且算法与初始聚类中心无关，并且可 以避免算法停滞和陷入局部最优，从而得到全局最优解。 根据之前提出的基于改进蚁群算法的聚类分析模型，利用计算机语言和 数据库技术，将该模型应用于员工绩效评估，对企业员工进行分类，将 其转换为一个真正实用的员工绩效评估系统：首先进行了系统架构设 计，然后设计了员工绩效评估系统数据库，之后进行了系统详细设计， 最后编码实现并成功应用到国内一家大型企业集团，取得了很好的效 果。 1 3 论文结构 本文共分5 章，全文组织结构如下： 第一章，引言，简要介绍了聚类分析的背景，国内外研究历史和现状，采用 蚁群算法进行聚类分析的优点，以及本文所做的主要工作 第二章，首先介绍了聚类分析的概念，阐述了聚类分析的基本知识，接着分 析了各种聚类分析算法的优点和不足，并重点叙述了k - 均值算法的流程和步骤。 接着介绍了一种新的生态优化类算法一蚁群算法的基本原理、研究现状、优点 和不足，并阐述了一些改进方法。然后根据笔者最近两年的研究提出了种新 的方法：改进蚁群算法( i a c a ) 并设计了改进蚊群算法的聚类分析模型，给 出了算法流程和实现，并进行了仿真实验，和其他聚类分析算法进行了对比。 第三章，首先阐述了将基于改进蚁群算法的聚类分析模型应用于绩效评估的 原因，然后简要介绍了人力资源管理基本理论，论述了绩效评估在人力资源管 理中的地位和重要性，阐明了绩效评估的相关理论，最后介绍了现有绩效评估 方法及其优缺点，并提出了本文的改进之处。 第四章，首先阐述了怎样确定绩效评估指标，然后依托改进蚁群算法的算法 实现，将其应用到员工绩效评估分类中，采用a s p 技术、c o m 组件技术和s q l s e r v e r 数据库开发实现了员工绩效评估系统。 第五章，对本文的所有工作进行了总结，并提出了展望。 以下是全文组织结构图： 3 四川大学硕士学位论文 4 四川大学硕士学位论文 图1 - 1 全文组织结构图 2 基于改进蚁群算法的聚类分析研究 2 1 聚类分析 2 1 1 数据挖掘概述 数据挖掘，英文名为d a t am i n i n g ，简称d m ，它是一种决策支持过程，主 要基于人工智能、机器学习、统计学技术，高度自动化地分析企业原有的数据， 做出归纳性的推理，从中挖掘出潜在模式，预测客户的行为，帮助企业的决策 者调整市场策略以减少风险，作出正确的决策。随着公司数据库的猛增，特别 是数据仓库的出现，原有的数据库工具已无法满足用户的需求，用户不仅需要 一般的查询和报表工具，更需要的是那些能够帮助他们从浩如烟海的数据中提 取出高质量信息( 预测性) 的工具，数据挖掘的出现和发展正好符合了这一潮 流。它也是当前数据库和信息决策领域的最显眼研究方向之一 数据挖掘的定义有很多，而以w j f r a w l e y ，g p i a t e t s k y s h a o p i r o 等人提出 的定义嘲比较为大家所认可，其定义如下；数据挖掘，就是从大型数据库的数据 中提取人们感兴趣的知识，这些知识是隐含的、事先未知的潜在有用的信息， 提取的知识表示为概念( c o n c e p t s ) 、模式( p a t t e r n s ) 、规则( r u l e s ) 、规律 ( r e g u l a t i o n s ) 等形式 数据挖掘的任务主要有：数据约简、分类和预测、聚类分析、关联分析、多 层数据概括、时序模式、偏差分析以及离差分析等。而作为本文研究的重点， 聚类分析在数据挖掘技术中占有非常重要的地位。 2 1 2 聚类分析概念 “物以类聚，人以群分”，聚类是人类一项最基本的认识活动。通过适当 聚类，事物才能便于研究，事物的内部规律才可能为人类所了解掌握。 聚类是一个将数据集划分为若干组或若干类的过程，并使得同一个组内的数 5 四川大学硕士学位论文 据对象具有较高的相似度，而不同组之间的数据对象相似却很小。相似或不相 似的度量是基于数据对象描述的取值来确定的。通常就是利用各对象间的距离 来进行描述。将一群物理的或抽象的对象，根据它们之间的相似程度，分为若 干组，其中相似的对象构成一组，这一过程就称为聚类过程，一个聚类，又称 簇，就是由彼此相似的一组对象所构成的集合，不同聚类中的对象通常是不相 似的。在许多应用中，一个聚类中所有对象常常被当作一个对象来进行处理或 分析。 聚类分析。1 是按照不同对象之间的差异，根据每个样本对象的各种特征，通 过无监督训练将样本按类似性分类，把相似性大的样本归为一类，并占据特征 空间的一个局部区域，每个局部区域的聚合中心又起着相应类型代表的作用。 聚类分析是一种典型的组合优化问题。通常用于将某些具有一定特征的各个个 体进行分类。聚类分析的数学模型如下： 已知模式样本集忸 有n 个样本和k 个模式分类冬，j 1 , 2 ，。k ，每个样本 有d 个特征指标，由此得到一个样本矩阵x 如下： x _ z ux 1 2 z nx 盟 x - lx d x “ x x _ 为了对它们进行分类，矩阵x 中，每一行为一个样本，x n ，工。z 。为第i 个样本的d 个特征指标，以每个模式样本到各自聚类中心的距离之和达到最小 为标准，其目标函数为： n 面嘻到x - m i i q 1 叩轰弘2 ) 其中k 为聚类数目，胁表示第j 类样本( s i ) 的均值向量，y l t = l ，表 示模式样本i 只能分配给一个聚类中心。其设置规则为：若模式样本i 分配第j 聚类中心，则均一1 ，否则，0 四川大学硕士学位论文 聚类分析是一种重要的人类行为。早在孩童时期，一个人就是通过不断完善 潜意识中的分类模式，来学会识别不同物体，如：猫和狗，动物和植物等。聚 类分析己被应用到许多领域，其中包括：模式识别、数据分析、图象处理和市场 分析等。通过聚类，人可以辨识出空旷和拥挤的区域，进而发现整个的分布模 式，以及数据属性之问所存在有价值的相关联系。 2 1 3 聚类分析研究的历史和现状 数据聚类正在蓬勃发展，有贡献的领域包括数据挖掘、统计学、机器学习、 空间数据库技术、生物学，以及市场营销。由于数据库中收集了大量的数据， 聚类分析已经成为数据挖掘研究领域中一个非常活跃的研究课题。 在数据挖掘领域，研究工作集中在为大型数据库的有效和实际的聚类分析寻 找适当的方法。活跃的研究主题集中在聚类方法可伸缩性、方法对聚类复杂形 状和类型的数据的有效性、高维聚类分析技术，以及针对大型数据库中混合数 值和分类数据的聚类方法 聚类分析作为统计学的一个分支，已被广泛地研究了多年，主要集中在基于 距离的聚类分析。例如：基于k 均值、k - m c t h o d ( k 中心点) 和其他一些方法的 聚类分析工具已经被加入到许多统计分析软件包或系统中，例如s - p l u s ，s p s s ， 以及s a s 。在机器学习领域，聚类是无指导学习的一个例子。与分类不同，聚 类和无指导学习不依赖预先定义的类和带类标号的训练实例。由于这个原因， 聚类是观察式学习，而不是示例式学习在概念聚类中，一组对象只有当它们 可以被一个概念描述时才形成一个簇，这不同于基于几何距离类度量相似度的 传统聚类。 在已有的应用中，随着涉及领域和问题的深入，对不同空间分布数据的研究 也已十分广泛，如何应用到具体的领域中并带来良好的效果，成为现实不可忽 视的问题。因而，基于理论的研究成果，在不同领域的实施、改进和创新也在 进行当中 2 1 4 聚类分析的步骤 一般来说，聚类分析要分成以下三个步骤：特征提取、聚类算法选择、参数 7 四川大学硕士学位论文 x l l x ” x 1 x 1 工2 1 x x mi 其中o z g 量l 【工一 x 正 x - j 2 1 5 聚类分析算法 聚类分析算法的选择取决于数据类型、聚类目的和应用领域。由于聚类分析 是一种富有挑战性的研究领域，因此它的一些应用对聚类分析算法提出了很多 特殊的要求，主要有以下几点： 8 四川大学硕士学位论文 1 可伸缩性。指算法除了能够处理小数据量之外，同样能够处理大数据量 的数据库对象，因此，这就要求算法的时间复杂度不能太高。 2 处理不同类型数据的能力。指算法不仅能够处理数值型数据，同时也要 能够处理其他非数值型的数据如二元类型、序数类型、枚举类型等。 3 能发现任意形状的聚类。数据库中的聚类可能是任意形状的，因此要求 算法有能够发现任意形状的聚类的能力 4 参数的弱依赖性。很多聚类算法都要求用户输入一些参数，如：聚类数 目、支持度等这些参数的值对聚类分析的结果影响很大。然而，另一 方面，这些参数又很难确定。一个好的算法应该对参数设置有一个比较 好的解决办法。 5 能够处理噪声数据现实中的数据库大部分都包含有孤立点、空缺、未 知数据或者错误的数据，一个好的聚类分析算法应该尽量避免对这些数 据的敏感性，从而得到好的聚类结果 6 输入记录的顺序无关性。不管输入记录的顺序如何，一个好的算法应该 能够得到相同的结果 7 高维性。一个好的算法不仅对二维，三维数据能够得到较好的聚类结果， 在高维空间中聚类数据对象是非常有挑战性的，也应该能够得到较好的 结果。 8 基于约束的聚类。在算法的具体应用中往往都有很多额外条件约束，一 个好的聚类算法能够在考虑这些约束的情况下，依然有较好的表现。 9 可解释性和可用性。聚类的结果最终都是要面向用户的，而用户希望聚 类结果是可解释的、可理解的、可用的。因此，聚类可能需要和特定的 语义解释和应用相联系。 聚类分析算法有很多，主要可以分成以下几大类：划分法、层次法、基于密 度的方法、基于网格的方法、基于模型的方法和模糊聚类算法等哪： 1 划分法( p a r t i t i o n i n gm e t h o d s ) 给定一个有n 个对象或元组的数据集，划分法将构造k 个分组，每一个分组 就代表一个聚类，k n 。而且k 个分组满足下列条件：( 1 ) 每个分组至少包含一个 数据纪录；( 2 ) 每个数据纪录属于且仅属于一个分组。对于给定的k ，算法首先 给出一个初始的分组方法，以后通过反复迭代的方法改变分组，使得每次改进之 9 四川大学硕士学位论文 后的分组方案都较前一次好。一个好的划分的一般标准是：同一分组中的对象尽 可能“接近”或“相关”，而不同分组中的对象尽可能“远离”或。无关”使 用这个基本思想的算法主要有k 一均值算法( 也g q k - m e a n s 算法) ，k - 中心点算法， c l a r a n s ( c l u s t e r i n gl a r g ea p p l i c a t i o nb a s e du p o nr a n d o m i z e ds e a r c h ) 算法等o ，启发式划分方法。 2 层次法( h i e r a r c h i c a lm e t h o d s ) 层次的方法对给定数据对象集合进行层次的分解，直到某种条件满足为止 根据层次的分解如何形成，层次的方法可以分为凝聚法和分裂法凝聚法，也 称为自底向上的方法，一开始将每个对象作为一个单独的分组，在接下来的迭 代中，相继地合并相近的对象或分组，直到所有的分组合并为一个，或者达到 一个终止条件为止分裂法，也称为自顶向下的方法，一开始将所有的对象置 于一个分组中，在迭代的每一步中，一个分组分裂为更小的组，直到最终每个 对象在单独的一个分组中，或者达到一个终止条件为止。代表算法有：b i r c h ( b a l a n c e di t e r a t i v er e d u e i n ga n dc l u s t e r i n gu s i n gh i e r a r c h i e s ) 算法， c u r e ( c l u s t e r i n gu s i n gr e p r e s e n t a t i v e s ) 算法，c h a m e l e o n 算法等”1 。b i r c h 算法是自上而下的算法，c u r e 算法是自下而上的算法。 3 基于密度的方法( d e n s i t y b a s e dm e t h o d s ) 绝大多数划分方法基于对象之间的距离进行聚类，这样的方法只能发现球状 的分组。基于密度的方法与其它方法的根本区别是：它不是基于各种各样的距离 的，而是基于密度的。这样就能克服基于距离的算法只能发现“球形”聚类的缺 点。这个方法的指导思想是，只要一个区域中的点的密度大过某个阈值，就把它 加到与之相近的聚类中去，继续进行聚类。d b s c a n ( d e n s i t y b a s e ds p a t i a l c l u s t e r i n go fh p p l i e a t i o n sw i t hn o i s e ) 算法，o p r r i c s 算法，d e n c l u e 算法啪 是其中比较有代表性的算法。 4 基于网格的方法( g r i d - b a s e dm e t h o d s ) 基于网格的方法首先将数据空间划分成为有限个数目的单元( c e i l ) ，形成 一个网格结构，所有的处理都是以单个的单元为对象，在这个网格结构上进行。 这样处理的突出的优点就是处理速度很快，其处理时间与目标数据库中记录的 个数无关的，它只与量化空间中某一维的单元数目有关。代表算法有：s t i n g 算 法，c l i q u e 算法，w a v e _ c 叫s t e r 算法o 四川大学坝士学位论文 5 基于模型的方法( m o d e l - b a s e dm e t h o d s ) 基于模型的方法给每一个聚类假定一个模型，然后去寻找能很好满足这个模 型的数据集。这个模型可能是数据点在空间中的密度分布函数或者其