（计算机软件与理论专业论文）基于特征加权的改进hopfield神经网络解决划分聚类问题.pdf

中山大学硕士学位论文基于特征加权的改进h o p f i e l d 神经网络解决划分聚类闻题 论文题目： 专业： 硕士生： 指导教师： 基于特征加权的改进h o p f i e l d 神经网络解决划分聚类问题 计算机软件与理论 张金华 王甲海副教授 摘要 聚类分析是发现数据内有用信息的一种有效手段，具有着重要的研究意义和 应用前景。划分聚类问题( p c 问题) 是备受关注和挑战的重要研究方向之一， 因此，寻求快速、有效的方法解决划分聚类问题是十分必要的。研究证明，划分 聚类问题是一种n p 难的组合优化问题。近几十年来，h o p f i e l d 神经网络被广泛 应用于解决划分组合优化问题并取得了良好的效果。2 0 0 8 年，w a n g 提出了一种 s t o c h a s t i co p t i m a lc o m p e t i t i v eh o p f i e l dn e u r a ln e t w o r k ( s o c h n n ) 方法求解划 分聚类问题，并能较k - m e a n s ，g a , g p s o ，d e 等先前的聚类方法获得更好的结果。 然而s o c h n n 方法却存在着一个缺陷：它没考虑数据特征对聚类的不同贡献， 聚类结果受着噪声特征的干扰。 本文提出了一种基于特征加权机制的s o c h n n 神经网络聚类方法，并采用 不同加权机制探讨改进算法的性能。与原方法相结合的两种不同特征加权机制， 一种是自动特征加权机制，其算法效率高只需用户输入一个参数；另一种是特征 自适应机制，权值计算自适应且无参数。特征加权减少了不相关和冗余噪声特征 的影响，提高了聚类的质量。仿真实验表明，改进后的s o c h n n 网络，可以检 测出噪声特征，比起原方法在性能及现实意义上有着很大的提高。新方法不仅保 留了s o c h n n 方法的优点，还引入了新机制特征加权，是一种颇具优势的划 分聚类算法。 关键词：划分聚类问题、s o c h n n 、自动特征加权机制、特征自适应加权机制 中山大学硕士学位论文 基予特征加权的改进h o p f i e l d 神经网络解决划分聚类问题 t i t l e ： a ni m p r o v e dh o p f i e l dn e t w o r kb a s e do nf e a t u r e w e i g h t i n gf o r p a r t i t i o n a lc i u s t e r m gp r o b l e m m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：j i n h u az h a n g s u p e r v i s o r ：a p r o f j i a h a iw a n g a b s t r a c t c l u s t e r i n ga n a l y s i si s a l le f f e c t i v e a p p r o a c h o ff i n d i n gt h e m e a n i n g f u l i n f o r m a t i o nw i t h i nd a t as e t s , n o wi th a sg r e a tr e s e a r c hm e a n i n ga n da p p l i c a t i o n p e r s p e c t i v e p a r t i t i o n a lc l u s t e r i n gp r o b l e m ( p cp r o b l e m ) i so n eo ft h em o s th o t c o n c e r n e da n dc h a l l e n g e dr e s e a r c ht o p i c s a n di ti sn e c e s s a r yt os e a r c haf a s ta n d e f f e c t i v ea l g o r i t h mf o rp cp r o b l e m s o m er e l a t e dr e s e a r c h e sp r o v e dt h a tp cp r o b l e m s w e r en p - h a r dc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s h o p f i e l dn e t w o r kh a sb e e n w i d e l ya p p l i e dt os o l v ec o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m sa n dp r o v e de f f i c i e n tf o r d e c a d e s i n2 0 0 8 ，w a n gp u tf o r w a r dan o v e lp a r t i t i o n a lc l u s t e r i n gm e t h o d ：s t o c h a s t i c o p t i m a lc o m p e t i t i v eh o p f i e l dn e u r a ln e t w o r k ( s o c h n n ) ，w h i c hp e r f o r m a n c e s b e t t e rt h a np r e v i o u sm e t h o d s ，s u c ha sk - t i t a n s ，g g p s o ，d ee t c b u ts o c h n n a p p r o a c hh a so n es h o r t c o m i n g ：i td o e sn o tt a k ei n t oa c c o u n tt h ec o n t r i b u t i o no f d i f f e r e n td a t af e a t u r e s t h ec l u s t e r i n gq u a l i t yi si n f l u e n c e db yt h en o i s ef e a t u r e s t h i sp a p e rp r e s e n t sa l li m p r o v e ds o c h n nm e t h o dc o m b i n e dw i t hf e a t u r e w e i g h t i n gf o rp cp r o b l e m i nd e t a i lw er e s p e c t i v e l yu s ct w od i f f e r e n tf e a t u r e w e i g h t i n gm e c h a n i s m st oi m p r o v e i t s p e r f o r m a n c e o n ei sa u t o m a t i cf e a t u r e w e i g h t i n gm e c h a n i s m 沁聊t h ea l g o r i t h mk e e p sh i g he f f i c i e n c ya n do n l yn e e d s o n ep a r a m e t e r a n o t h e ri sf e a t u r ew e i g h ts e l f - a d j u s t m e n tm e c h a n i s m ( f w s a ) r d o e sn o tr e q u i r eu s e 岱t oe n t e ra p a r a m e t e rs u b j e c t i v e l yb u t 咖w e i g h ta u t o m a t i c a l l y b yf e a t u r ew e i g h t i n g ，t h en e wa l g o r i t h m sc a ni m p r o v et h eq u a l i t yo fr e s u l t sb y r e d u c i n gi r r e l e v a n ta n dr e d u n d a n ti 舱i s yf e a t u r e s a n de x p e r i m e n t ss h o wt h a tt h e i m p r o v e dm e t h o d sc a l lg e tb e t t e rr e s u l t st h a ns o c h n n ，a n da l s oc a nd e t e c tn o i s y 中山大学硕士学位论文 基于特征加权的改进h o p f i e l d 神经网络解决划分聚类问题 f e a t u r e s ，s om o r em e a n i n g f u li nr e a lw o r d t h ei m p r o v e dm e t h o d sn o to n l yr e t a i nt h e a d v a n t a g e so fs o c h n nm e t h o d ，b u ta l s o i n t r o d u c ean e wa p p r o a c h - - - f e a t u r e w e i g h t i n g t h e ya r ep r o m i s i n gp a r t i t i o n a lc l u s t e r i n gm e t h o d s k e yw o r d s ：p a r t i t i o n a lc h s t e r i i l gp r o b l e m , s o c h n n ，a f w ( a u t o m a t i cf e a t u r e w e i g h t i n gm e c h a n i s m ) ，f w s a ( f e a t u r ew e i g h ts e l f - a d j u s t m e n tm e c h a n i s m ) i v 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：二毯 金1 日期：2 qf q ：厶。墨 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：苏仓缂 日期：z o l o 年占月乡日。 中山大学硕士学位论文 基于特征加权的改进h o p f i e l d 神经网络解决划分聚类问题 1 1 课题背景及意义 i i 1 聚类问题 第一章前言 聚类的研究已经有了很长一段历史。如今，聚类的应用已经广泛渗透到诸多 领域，如模式识别、机器学习、统计学、生物学、地理学等f 。几十年来，聚类 由于其自身的重要性及与其他方向的交叉性，使得越来越受人们的重视，已成为 相当热门且备受注目的研究方向之一。 聚类问题是工程领域中的一种常见问题，它在数据挖掘、模式识别等领域具 有重要的作用。由于现实中数据呈现出来的各种各样结构及拥有不同的数据规模 程度，使得无法产生一种通用的聚类技术普遍适用于揭示不同数据的内在结构规 律。如今已经研究出有许多聚类技术，并可大致分为层次聚类、划分聚类、基于 密度、网格和模型的聚类等f 锄。目前已有许多种聚类算法，如文献【3 l ，且主要的 聚类方法一般集中在层次聚类和划分聚类。本文研究的是基于划分聚类算法。 划分聚类问题是这样定义的【2 】：给定刀个数据对象的数据集和所需生成的k 个簇，找出簇中对象最相似且不同簇间的对象差异最大的k 个最优划分，并满足 每组至少包含一个对象，每个对象必须只属于一组。求得各个数据点到各中 心点的距离最小的最优划分问题，显然是一个典型的组合优化问题，且相关研究 证明聚类问题是一种n p 难问题【4 1 。从问题定义不难看出，虽然问题描述很简单， 但最优组合的求解却很难。其主要原因是实际聚类可能有矿七! 种划分方式，且 随着问题规模的不断扩大，指数和阶层的存在将导致“组合爆炸一【5 】问题，如此 大的计算量将难以令人承受。因此，寻找一种有效的优化算法解决划分聚类问题 非常有实际应用价值和意义。 许多学者意识到这个问题，并进行了相关的研究【6 l ，如今已经产生了许多划 分聚类方法，其中一些方法尝试结合了其他优秀思想形成了功能更强的新混合聚 类算法。根据数据内部复杂多维的结构情况及采用探寻规则的方法不同，划分聚 类算法很难进行统一归类，但是简单来说，包括了经典的划分聚类方法、基于智 i 中山大学硕士学位论文基于特征加权的改进h o p f i e l d 神经网络解决划分聚类问题 能思想的聚类方法及其他混合聚类方法等。 其中最广泛使用的划分聚类算法是k - m e a n s 方法，它简洁、快速，能对大型 数据集进行高效划分，然而它还是存在一些不足【2 】之处： 通常终止于一个局部最优解； 只适合数值型的数据集； 适合发现凸形的结果簇。 针对划分聚类问题的特点及不足之处，很多改进方案被提出并取得了一定的 效果。 另一方面，划分聚类问题也是一种典型组合优化问题。在海量的划分可能中 求得一个最优划分，智能优化算法给问题的求解带来了新的思路。目前，许多基 于计算智能的算法如遗传算法( g a ) 7 - 1 0 l 、粒子群算法( p s o ) 11 - 1 6 、差分演化算法 ( d e ) 1 3 】、蚁群算法( a c o ) 1 7 - 2 0 】、模糊理论( f t ) 2 1 - 2 4 1 、和人工神经网络( 砧州) 2 5 , 2 6 】 等纷纷用来求解聚类问题，并取得了不错的结果。总的来说，基于智能思想的聚 类算法其工作方式一般是为p c 问题重新建立相应的目标函数及结构模型，将生 物群体共同寻优的过程与问题的求解对应起来。 近来，h o p f i e l d 神经网络也被用于求解划分聚类问题。2 0 0 8 年底，一种改进 的h o p f i e l d 神经网络算法s o c h n n 2 5 】被用来求解p c 问题，文中定义了新的网 络模型、能量函数和神经元的输入规则。最后为了验证新方法的效果，仿真实验 同其他许多优秀方法进行了对比，结果表明了新算法较先前的k m e a n s ，g ap s o ， c p s o 和d e 等聚类方法要更优，可见，此方法是可行有效的。 然而，上述算法仍然存在一些缺陷：聚类结果没有考虑噪声属性的影响【1 5 】， 解的质量还不算很好。实际聚类的一个有趣现象是：很多聚类现象经常发生在一 个有意义的特征子空间 2 n ，不同的特征对聚类的贡献程度往往是不同的。如 果所有的属性一视同仁，则重要属性对聚类的贡献很难显现出来。因此，研究一 种既高效又具有现实意义的聚类方法是十分必要的。 1 1 2 特征加权机制 近来，特征加权是一个越来越热门的研究方向，也是实际聚类工作中越来越 关注的问题。目前，已经有许多有关特征加权的理论【2 7 - 3 7 。一些研究表明，经历 2 中山大学硕士学位论文 基于特征加权的改进h o p f i e l d 神经网络解决划分聚类问题 特征加权步骤的聚类过程，能够大大降低无关数据维的影响提高聚类的效率由 于数据各属性对聚类贡献程度往往不同，高贡献的特征有利于数据簇的发现，聚 类分析中需要降低噪声属性的影响来提高聚类的质量。因此，进行特征加权的研 究是有意义的。 随着数据的日益多元化和处理数据的方法不同，实际已无法产生一种通用的 特征加权方法可以处理不同的数据，但总的来说，所有方法的研究大多都是基于 数据特征对聚类的不同贡献程度来寻找合适的权值组合，其最终目的也都是尽量 减低不相关或冗余的噪声数据特征的干扰。 对特征加权机制的研究直到现在，许多学者进行了相关的研究，并提出了不 同的特征加权方法，如d e v a n e yr a m l 9 9 7 t 2 9 1 ，d y 和b r o d l e y 2 0 0 0 t 3 0 1 ，k i m 2 0 0 0 t 3 n ， b r u s c 0 2 0 01 3 2 1 ，d a s h 2 0 0 2 3 ”，l a w 2 0 0 4 3 4 1 ，h u a n 9 2 0 0 5 t 3 5 1 ，t s a i 2 0 0 8 1 3 6 1 等。所有特征 加权办法，它们各自的效果和适用面均不相同，很难进行一一归类。最早解决数 据特征加权问题的是1 9 8 4 年d w s a r b o 等人提出的一种s y n c l u s 3 7 l 方法。其中， 本文主要介绍两种有效的加权方法。一种是h u a n g 等人【3 习于2 0 0 5 年提出的自动 特征加权机制。机制保持了原算法的简洁快速特性，并能通过自动特征加权作用 取得了高精度的解。另外一种是2 0 0 8 年t s a i 等人【3 6 】提出的特征自适应机制，它 能使得重要特征的权值更大些。新方法不需要用户输入参数值，其所得解的精度 有很大程度的提高。 关于特征加权算法的研究解决了许多数据处理方面的问题，因而具有非常重 要的理论意义和现实意义。本文将针对一种h o p f i e l d 神经网络方法s o c h n n 的 一些缺陷，尝试引入特征加权机制对其进行改进，并采用了自动特征加权机制1 3 5 1 和特征自适应机制【3 6 1 两种加权策略测试新改进方法的效果，希望改进策略能够 帮助神经元考虑数据特征的贡献因素来竞争，最后能够在一定程度上降低了噪声 属性的影响获得更好的聚类结果。 1 2 本论文的主要工作和组织结构 本论文的主要工作是：在深入分析和探讨随机最优竞争h o p f i e l d 神经网络 聚类算法s o c h n n 模型及特征加权机制的思想和特点基础上，提出了基于特征 加权的改进h o p f i e l d 神经网络聚类算法。本文提出的改进算法，采用两种特征 3 中山大学硕士学位论文 基于特征加权的改进h o p f i e l d 神经网络解决划分聚类问题 加权机制对s o c h n n 网络分别进行改进，一种是自动特征加权机制a f w ，另外 一种是特征自适应机制f w s a ，两种机制将采用不同权值计算策略来解决噪声数 据特征的问题。本文所做工作希望改进后的h o p f i e l d 神经网络聚类方法通过新机 制的作用，既能保留原算法优势，同时还能降低噪声特征的影响。 下面章节中，本文分别提出两种新的聚类方法来测试改进策略的有效性，为 聚类问题分别给出了对应的目标函数、网络模型和实现步骤。仿真实验部分，将 分别采用人工构造的含噪声数据集和u c i 标准测试数据集进行测试，最后引入 了多种客观评价准则评判各算法的聚类结果。 本论文的组织结构如下： 第一章：简述课题的研究背景和意义，以及本论文的主要研究工作。 第二章：综述求解划分聚类问题的研究成果。首先概要介绍聚类相关知识， 接着描述了一些代表性的聚类方法。 第三章：详细介绍本文基于的h o p f i e l d 神经网络聚类方法一s o c h n n 。本 章首先简要回顾h o p f i e l d 网络相关理论基础和一种改进离散h o p f i e l d 网络模型 o c h o m ，然后介绍s o c h n n 网络的特色及在p c 问题上的新应用，最后深入分 析了s o c h n n 方法优势同时也指出算法一些缺陷。 第四章：本文针对s o c h n n 方法的缺陷，尝试用特征加权机制对其进行改 进，并具体引入两种加权机制验证改进策略的有效性。本章主要提出了两个基于 特征加权的改进h o p f i e l d 神经网络聚类方法s o c h n n a f w 和s o c h n n f w s a ， 并分别介绍了新方法的工作原理，网络模型及算法运行步骤。 第五章：仿真实验。两种改进方法分别对人工构造的含噪声数据集和u c i 的标准测试数据集进行实验。构造数据的实验中，新方法将从参数的影响、网络 稳定性和实验结果来分析新聚类算法的性能；u c i 标准测试数据集中，将分别采 用原方法文献中的四组实验数据集和新增两个较难处理的数据集进行实验。 第六章：总结与展望。总结全文，概述本文的研究成果，并提出新的展望。 4 中山大学硕士学位论文基于特征加权的改进h o p f i c i d 神经网络解决划分聚类问题 2 1 概述 第二章聚类算法综述 对聚类分析的相关研究已经有几十年的历史。聚类源于许多重要研究领域的 交叉如数据挖掘、机器学习、模式识别等，并且在客户分类、信息安全、基因识 别、数据处理、照片分析、图像识别等众多领域得到广泛应用【2 1 ，因而得到许多 学者的广泛研究。 目前聚类算法已经有许多种，然而方法各式各样，有的相互重叠，因而很难 进行简单归类。但大体上，聚类方法可以分为划分聚类方法、层次聚类方法、基 于密度、基于网格和其他混合聚类方法等 本文致力于研究划分聚类算法。本章首先简要描述聚类问题的定义，然后介 绍两种经典的划分聚类方法和目前流行的几种基于计算智能的聚类方法。 2 2 聚类相关知识 2 2 1 聚类问题的定义 聚类问题是一个无先验知识的无监督分类过程，关于它的准确定义学术界还 没有一个统一标准，但大都是基于以下主要思想：将无先验知识的待处理数据对 象划分成簇，其中，同一簇中的对象是相似的，不同簇间的对象相差最大。 这里，聚类问题可以形式地描述如下【5 l ： 给定个d 维的数据对象，以及要生成的簇的数目k 。假定簇集合表示为 g = g l ，9 2 ，g r ，其中，每个簇都不为空，各簇之间没有交集且各簇所含的对 象总数等于原数据集内的对象总数。 设( g ) = 厂( 蜀，岛，缸) 是聚类问题的目标函数，则问题的求解化为： o p t i m i z e f ( g ) ( 2 - 1 ) 6 可以看出，聚类是寻找一个最优数据对象划分的过程。随着数据规模的不断 增加，传统聚类方法很难在一个多项式时间内得到最优划分。有研究证明聚类问 s 中山大学硕士学位论文 基于特征加权的改进h o p f i e l d 神经网络解决划分聚类问题 题是一个n p 难组合优化问题 4 1 ，因而可以结合智能优化的思想来解决。 2 2 2 一般遵循的步骤 聚类是一个将无先验知识的数据集划分为若干类或簇的过程，其结果使得同 一簇数据对象之间的相似度较高，而不同簇数据对象之间的相似度较低，即聚类 的关键就是把相似的事物聚集在一起。 结合文献【1 ，2 捌可以归纳出聚类一般遵循的步骤： 数据准备：包括数据特征的标准化和降维。 特征选择和提取：选择贡献最大的特征，尽可能多的包含聚类相关信息。 相似性度量：用于度量两个特征之间是如何“相似 或“不相似 ，例如 常用的欧氏距离反应了两个属性特征的相似程度。 聚类算法：已经选择了合适的相似性度量方法后，接着需要选择特定的 聚类算法，揭示出数据集中的内在簇结构。 结果评估：对聚类结果进行评估，评估主要包括有三种：外部有效性的 评估、内部有效性评估和相关性测试评估。 其中第二步骤是本文主要的改进思想来源。在特征提取中，冗余特征作用的 最小化和有效特征作用的最大化是特征加权的主要目的。 2 2 3 数据对象度量方法 聚类分析中遇到的数据类型是多种多样的，经常出现的数据变量类型有区间 标度变量、二元变量、标称型、序数型和比例标度型等。对于不同的类型，对象 间的相异度有着不同的度量方法。文献【2 】中介绍了两种常用的度量方法： ( 1 ) 区间标度变量 区间标度变量是一个粗略线性标度的连续变量。典型的例子包括体积和高 度，经度和纬度，以及大气温度。一般而言，选用的单位越小，变量可能的值域 就越大，这样对聚类结果的影响就越大。因此为了避免聚类结果对单位选择的依 赖，数据应当标准化。标准化处理后，对象间的相异度是基于距离来计算的，其 中最常用的距离度量方法是欧氏距离，相关定义为： 6 中山大学硕士学位论文基于特征加权的改进h o p f i e l d 神经网络解决划分聚类问题 d ( i ，j ) = 埘再。一乃。1 2 + l 毛：一乃：1 2 + + 1 一场1 2 ( 2 - 2 ) 这里= ( i ，五2 ，) 和咒( 只。，咒2 ，) 是两个d 维的数据对象。在 此使用欧氏距离要特别注意数据对象各数值的选取，应有效地反映类别属性的特 征。 ( 2 ) 标称变量 标称变量可以具有多个状态值。例如：c o l o r 是一个标称变量，它有五个状 态：红色、白色、黄色、绿色和蓝色。 假设个标称变量的状态数目是m 每一个状态值可以用字母、符号或者一 组整数来表示，则两个对象i 和，之间的相异度可以用简单匹配方法来计算： 啦) = 等( 2 - 3 ) 这里m 是匹配数，即f 和_ 取值相同的变量数目，而p 是全部变量的数目。 由于大多数聚类方法是基于距离的，h o p f i e l d 神经网络划分聚类方法也是基 于欧氏距离，因而本文采用数据对象度量方法主要是第一种方式。 2 2 4 常用评判标准 为了测试给定数据对象的聚类效果，目前已经提出了许多种聚类评判标准。 文献 1 3 , 1 4 描述了两种常用的无监督聚类评价标准：分别是均方误差标准s e ( s q u a r e de r r o rc r i t e r i o n ) 和方差比率标准v r c ( v a r i a n c er a t i oc r i t e r i o n ) 。 对于聚类问题，先假设给定有，个d 维的数据对象集合和需要将它们划分 的簇数目k 。其中各个簇的中心点为c = c l ，乞，c x ，第f 个数据对象的第d 维数据取值为勘。 ( 1 ) s e ( s q u a r e de r r o rc r i t e r i o n ) 均方误差标准s e 也即各个簇中数据对象问的欧几里得( e u c l i d e a n ) 距离。它 一般目标为：对于给定的数据集，通过聚类最终得到一个具有最小s e 值的簇划 分，并保证同一簇内的对象距离最小。 s e 公式中，各个簇中数据对象间的距离表现为各数据对象与对应簇中心之 间的均方距离，具体计算如公式( 2 - 4 ) 。 7 中山大学硕士学位论文 基于特征加权的改进h o p f i d d 神经网络解决划分聚类问题 ( 2 4 ) 因此基于s e 标准，通常定义聚类的优化问题为： m i n i m i z es e ( c ) ( 2 ) v r c ( v a r i a n c er a t i oc r i t e r i o n ) 方差比标准v r c ，它的一般目标是最大化各个簇间数据对象的距离，最小 化各个簇中数据对象间的距离。 v r c 公式中，簇间数据对象的距离通过s e i n t e r ( c ) 计算，即每个簇的中心 点与全局数据中心点的均方距离；簇内数据对象的距离同s e 标准运算规则。 s e i n t 盱( c ) ：k 力( q - c o ) ，( q - c o ) 七= l 其中， 城= 琵l n ， 弘面矿 p 5 ) 一a j 其中( 刀一k ) 为s e i n t e r ( c ) 的自由度，( k - 1 )s e ( c ) 的自由度。 2 3 聚类算法研究 没有任何一种聚类算法可以普遍揭示不同数据内部固有的结构【3 3 1 。目前对 划分聚类算法的研究已经有几十年的历史，根据聚类聚积规则的不同，聚类算法 也不尽相同，各有各的优势。 有研究已经证实，聚类问题是一种n p 难的组合优化问题。为了达到全局最 优，聚类需要穷举所有可能的划分。计算智能技术的兴起为诸如聚类等组合优化 8 、i _ 、 材 c一 嘞 ，一一 p ， 一 ， d 描k 麒厅瑚 = 、- ， c ，j 一， es 厶 i i 厶 = 铅 中山大学硕士学位论文基于特征加权的改进h o p f i e l d 神经网络解决划分聚类问题 问题的求解带来了希望。目前已有许多如g aa c o ，p s o d e 和模糊理论等智能 优化方法用来求解划分聚类问题。 本节首先介绍几种经典聚类算法及相关研究，然后介绍基于智能优化思想的 聚类算法。其中，经典算法以k - m e a n s 算法、k 中心点算法为例，首先阐明了算 法的基本思想、操作流程、优点及不足，然后综述一些代表性的改进方法。对于 基于计算智能的聚类方法，本文主要讨论了基于神经网络、基于粒子群、基于蚁 群和模糊理论等相关聚类算法。 2 3 1k - m e a n s 算法及改进 ( 1 ) k - m e a n s 算法 1 9 6 7 年，m a c q u n 首次提出了k 均值聚类算法( k - m e a n s ) 3 9 1 。此算法根 据欧几里得公式计算出各个簇中数据对象间的相似程度，过程简洁、高效。 根据文献【2 1 ，下面简要回顾下经典k - m e a n s 算法的核心内容。 k m e a n s 聚类过程中，以k 为输入参数，目的把力个数据对象的集合分成k 个聚簇，其算法流程具体如下： 随机选择k 个数据对象做为簇的初始中心点； 对剩余的对象，根据其与各个簇中心的距离将它赋给最近的簇； 在新产生的k 个簇的基础上，更新各个簇的中心值； 重复，不断迭代直到均值不再发生变化或者平方误差准则函数收敛； 总结k - m e a n s 算法的一些优点主要表现为：算法思路简单、易于实现，且收 敛速度快，能适应大规模的数据集聚类问题。 从上分析可以看出，经典的k - m e a n s 聚类算法非常简洁高效，能够很大程度 上帮助聚类分析工作，但是算法本身具有的缺陷还是给具体的聚类工作带来了一 些遗憾。传统的k - m e a n s 算法主要存在着以下缺陷： k m e a n s 只能对数值型属性进行处理，不能处理离散型和分类型属性； 需事先给出k 值( 簇的个数) ； 聚类结果受初始中心点选择的影响： 对噪声及孤立点数据比较敏感，是一种硬划分的过程； 是一个贪心算法，结果通常收敛到一个局部最优解； 9 中山大学硕士学位论文 基于特征加权的改进h o p f i e l d 神经网络解决划分聚类问题 只适用于解决聚类结果为凸形、球形和密度较集中的数据集。 但作为一种启蒙思想，其经典的聚类处理方法还是给后来的聚类算法研究带 来很大启发，许多算法就以其为基础作了进一步改进，并取得了不错效果。 ( 2 ) 算法的改进 由于经典k - m e a n s 算法简单、高效，许多学者进行了进一步研究，分别解决 了算法中的一些缺陷。下面介绍一些典型的改进算法： 针对k - m e a n s 算法只能处理数值型数据问题，1 9 9 9 年，h u a n g 等人提出适合 于分类对象数据的k - m o d e s 算法。k m o d e s 改进了k - m e a n s 算法的第一个不足， 并且对其进行3 点扩展：引入了处理分类对象的新的相异性度量方法( 简单的相 异性度量匹配模式) ；使用m o d e s 代替m e a n s ；使用基于频度的方法修正m o d e s 以使聚类的代价函数值最小化。 2 0 0 2 年s u n l 4 1 】等人运用迭代初始点求精的方法改进k - m o d e s 算法中初始 m o d e s 的确定问题，相关实验表明，新方法能够产生更高精度和可靠程度的聚类 结果，同时不足之处为对更大、更复杂的数据集，但算法的可伸缩性和适应性不 是很好。 其他改进方法中，行小帅【4 2 】等人2 0 0 3 年提出了一种新的聚类算法一基于免 疫规划的k m e a n s 聚类算法。文中将免疫规划算法的两个特点全局搜索能力和 对不良基因进行组合模式免疫，与k m e a n s 算法的快速迭代优点相结合，形成一 种具有免疫功能的新型k - m e a n s 算法。最后仿真结果表明，该算法不仅有效地克 服了经典k m e a n s 聚类算法易陷入局部极小值的缺点，而且明显地避免了对初始 化取值敏感性问题，同时也有较快的收敛速度。 目前特征加权策略对聚类的重要作用已经得到了证樊2 1 ，并出现了一些特征 选择方法：如用进化思想进行特征选择，也有根据聚类目标数据的特点进行特征 选择等。基于聚类过程中结果簇往往出现在维空间的某个子集中【 1 思想的启发， 许多文献尝试引入特征加权改进k - m e a n s 算法。 2 0 0 5 年，h u a n g l 3 5 】等人针对特征重要性问题提出了自动特征加权的k - m e a n s 聚类算法。针对k - m e a n s 算法对待所有特征都平等这一缺陷，h u a n g 等人在文中 提出一种自动加权的方法，它需要用户输入一个参数，聚类过程中均方距离越大， 计算的相应维权值越小；反之，距离越小，相应维权值越大，符合了各维对聚类 l o 中山大学硕士学位论文基于特征加权的改进h o p f i e l d 神经网络解决划分聚类问题 的贡献程度赋予权值。文中仿真实验表明，算法能够分配合适的特征权值，并且 有效地解决了传统k - m e a n s 算法中的噪声特征问题，可见特征加权过程对聚类还 是非常重要的。 2 0 0 8 年，c h i e h - y u a nt s a i 和c h u a n g c h e n gc h i u 两人【3 6 1 提出了一种特征加权 自适应机制改进k - m e a n s 算法。他们也在经典k - m e a n s 基础上，引入一种新的特 征加权机制帮助聚类降低噪声属性的影响。新机制f w s a 不需用户输入任何参 数，操作中只需在整个算法中增加一个计算权值的步骤。此机制的核心思想是根 据最小化簇内的对象距离和最大化簇间的对象距离两者比值推导出一个目标优 化函数，用比值大小说明簇中对象的相似程度和簇问对象的相异程度。在其权值 公式中，这个比值也决定了下一步权值变化量，并决定着下一步新权值的更新。 文中仿真实验表明新方法不但保持了k m e a n s 原有的简洁快速性，并在几组测试 数据集上结果表现比另一种方法更好些。新的k - m e a n s 方法也降低了噪声特征的 干扰，获得了更高质量的解。 其他优秀的改进方法还有很多，这里就不再赘述了。 2 3 2k 中心点算法及改进 经典的划分聚类方法中，针对k - m e a n s 算法不能很好处理存在噪声和异常数 据情况，于是有了k 中心点算法。但k 中心点算法计算代价比较高，其时间复杂 度为d l 气( n - k ) 2l ，因而不能很好地扩展到大型数据库上去。 下面先介绍下k 中心点算法的核心思捌2 】： 首先为每个簇任意选择一个代表对象( 作为中心点) ； 剩余的对象根据其与代表对象的距离分配到最近的一个簇； 根据代价函数值重复地选择合适的非代表对象替换代表对象以提高聚类 质量，其中使用代价函数评估聚类的质量。 关于k 中心点算法的研究，文章 2 1 对其做了一些归纳。 p a m ( p a r t i t i o n a la r o u n dm e d o i d s ，围绕中心点的划分) 算法是典型的尺中 心点算法之一。由于中心点不像均值那样容易受离群点或其他极端值影响，对于 噪声和孤立点数据，它比k - m e a n s 算法鲁棒性更好。然而p a m 算法有它的局限 性：对小规模数据效果很好，不适用大型数据库，算法伸缩性较差对此，有一 中山大学硕士学位论文 基于特征加权的改进h o p f i c l d 神经网络解决划分聚类闯题 些算法对它做了改进。 针对p a m 方法的不足，种基于抽样的方法c l a r a 4 3 】被提出。它的主要 思路是：不考虑整个数据集合而选择实际数据的- d , 部分作为代表，然后用p a m 方法选择中心点。c l a r a 能够处理的数据集规模比p a m 大，但当抽样时如果 没有选中最佳中心点，此方法的效果就不是很好。 为了改进c l a r a 算法的聚类质量和可伸缩性，c l a r a n s ( c l u s t e r i n gl a r g e a 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 ) 算法4 4 】被提出了。整个c l a r a n s 的聚类过程可以描述为对一个图的搜索，最后图中的每个节点就是一个潜在解也 即k 个中心点的集合。与c l a r a 不同的是，在任何时候都不把自身局限于任何 样本，它将抽样技术和p a m 结合起来，根据对象属于某个簇的程度发现最自然 的簇，同时能检测出离群点。总的来说，c l a r a n s 的优点是能够探测孤立点， 缺点是c l a r a n s 算法计算复杂度为o ( n 2 ) ，而且算法聚类的质量取决于所用的 抽样方法。 当然，k 中心点相关改进算法并不是完善的，还需要进一步的研究。 2 3 3 基于神经网络的方法 聚类问题被看待成n p 难的组合优化问题，因此解决此问题的智能优化算法 引起了很多学者的广泛研究。迄今为止，神经网络的研究已经获得了许多方面的 进展和成果，并且提出了许多模型和众多的改进算法。 神经网络技术在聚类分析的应用首先起源于k o h o n e n 的两项工作【4 5 舶】，分 别是学习矢量化( l e a n i n gv e c t o rq u a n t i z a t i o n , l v q ) 和自组织特征映射 ( s e l f - o r g a n i z i n gf e a t u r em a p ，s o m ) 。参照文献 2 , 4 5 , 4 6 1 ，现对两种技术分析如下： l v q 4 5 】是一种自适应数据聚类方法，它基于对那些具有类标签信息数据的训 练。尽管是一种有监督训练方法，l v q 采用的主要还是无监督数据聚类技术， 通过对数据集进行预处理后最终获得聚类的中心。l v q 算法的基本思想是把待 处理的数据对象划分为k 个互不相交的组，并为每个组分配初始数据对象，根 据已知类标签信息的数据通过无监督与自适应学习方式来修正对象的分配指标。 当网络收敛时，这些指标基本反映出了数据对象分布情况。 s o m l 4 6 网络具有能保持拓扑结构、能无监督学习和能可视化等优点，目前 1 2 中山大学硕士学位论文基于特征加权的改进h o p f i e l d 神经网络解决划分聚类问题 已被广泛应用于众多数据处理领域，也是一种有效的聚类分析方法。在使用s o m 模型聚类时，竞争层神经元个数肘应预先指定，然而这种网络结构上的制约大 大影响着网络的收敛速度，实际往往需要进行若干次不同的仿真训练才能最终确 定适合的网络结构。 图2 - 1s o m 网络拓扑结构 为此，有学者提出了在训练过程中动态确定网络形状和单元数目的解决方 案，对s o m 网络的聚类性能有了较大的提高。上述神经网络模型能够有效地解 决一些聚类问题，所以其他神经网络模型也可应用于求解划分聚类问题1 2 5 2 6 1 。 2 0 0 8 年底w a n g 等人提出了一种随机优化竞争h o p f i e l d 神经网络模型【2 5 1 来 解决划分聚类问题。h o 西e i d 神经网络经过多次爬山的作用，大大提高了原网络 获得高质量解的能力。对于划分聚类问题，文中新定义了一个网络模型。模型中 神经元被划为与数据点数目 对应的r 个组，每组神经元对应到k 个簇。神经 元的输入根据数据点距离簇中心的值是否最小来判断，神经元的输出根据数据点 指派到相应簇中判断。模型中新引入一种爬山机制解决网络易陷于局部最优解的 问题。整个算法不但保持了h o p f i e l d 神经网络梯度下降的特性，而且多次爬山的 作用使得处于劣势的神经元也能参与竞争，帮助网络避免收敛于局部最优解。 上述算法固然好，然其相关机制还需作进一步改善。算法聚类过程中，不相 关的数据特征和重要数据特征被平等对待。对于那些噪声特征干扰很严重的数据 集则无法摆脱噪声的影响，所以其聚类结果当然也不会很好。针对这个问题，基 于聚类过程特征选择的启发，本文尝试为s o c h n n 方法也引入特征加权机制， 中山大学硕士学位论文 基于特征加权的改进h o p f i e l d 神经网络解决划分聚类问题 通过不同的权重来区别不同特征的贡献，帮助神经网络摆脱噪声特征的影响。特 征加权机制能够帮助神经网络聚类方法避免噪声特征的干扰，尽可能地提高聚类 的效率。 其他的神经网络聚类方法中，文献闭对现有聚类算法进行简要综述基础上， 提出了一种综合性的基于竞争学习的新型神经网络聚类方法。此方法综合了其他 算法的一些优势，显示出了更强的功能。大量仿真实验也表明了新算法是一种有 潜力的聚类方法。 2 3 4 基于蚁群( a c o ) 的聚类算法 群体智能的思想起源于对生物群体间相互协作活动的研究。蚁群算法就是根 据蚂蚁如何进行群体交流启发而来。 大量研究发现，蚂蚁之间通过一种叫外激素( p h e r o m o n