（电路与系统专业论文）基于自然计算的模糊聚类新算法研究[电路与系统专业优秀论文].pdf

摘要 数据挖掘技术是近年来国际上在信息决策领域最前沿和最活跃的研究方向之 一。作为数据挖掘的一种强有力的分析工具，聚类分析得到了人们的广泛关注。 聚类分析是多元统计分析的方法之一，也是统计模式识别中非监督模式分类的一 个重要分支，近二十年来得n t 迅猛的发展，有许多聚类分析新算法不断被提出。 自然计算是目前新兴的一类计算方法，它以自然界，特别是生物体的功能、 特点和作用机理为基础设计出的计算模型。它具有自适应、自组织、自学习等能 力，能够解决传统计算方法难于解决的许多复杂问题，因而近年来成为研究的热 点，并在诸多领域中得到了广泛的应用。 针对现有聚类分析算法在数据挖掘应用中存在的不完善甚至严重不足之处， 本文结合自然计算方法，对传统模糊聚类算法进行较为系统的改造和革新，主要 探讨了有关具有混和属性特征数据的聚类算法目标函数的定义以及优化方法，提 出了适合大数据集的网络结构聚类新算法，扩展了聚类分析的应用范围，并构造 了适合于数据挖掘的新的聚类有效性函数。实验结果表明，本文提出的一系列有 关模糊聚类分析的新思想和新方法都取得了良好的效果。 归纳起来，本文的研究成果主要表现在以下几个方面： 1 定义了一个新的相异性匹配测度，修正了传统聚类算法的目标函数类 散布矩阵的迹，将数据集中不同属性特征相结合，构成新的聚类目标函数，使得 其能够适合混合类属特征的数据，并利用遗传算法对其进行优化，克服传统的模 糊“均值( f k m ) 算法对原型初始化敏感的缺点，使得算法能够以较高的概率收 敛到全局最优解。 2 利用人工免疫系统中著名的克隆选择算法改进遗传算法，避免了遗传算法 中可能出现的早熟现象，同时由于基于克隆算子的克隆选择算法是群体搜索策略， 本质上固有并行性和搜索变化的随机性，在搜索中不易陷入局部极值，最终能以 概率1 获得问题的全局最优解，而且收敛速度比遗传算法更快，因此更加适合大 数据集的聚类分析。 3 结合人工免疫系统中免疫网络理论，提出用免疫网络来进行聚类分析，由 于所获得的网络神经元代表了数据子集中的典型样本，因而可以用来产生相应的 数据子集；通过最小生成树对获得的网络神经元的连接权进行分析，最终自动解 决了f k m 类型算法需要事先输入类别数以及聚类原型必须一致的难题。 4 借鉴生物免疫系统的免疫应答中禁忌克隆的现象，提出禁忌克隆算法，并 与克隆选择算法相结合，形成基于克隆算法的网络结构聚类分析新算法。由于新 算法将克隆选择与禁忌克隆相结合，使得到的网络即具有免疫的特异性又具有免 疫耐受性，因此具有有效的清晰网络结构，从而使网络结构聚类算法对数据集边 界点以及噪声点不再敏感。 5 利用免疫系统中有限资源理论，设计了一种模糊识别球，使其作用范围随 刺激水平的变化而变化，通过对b 细胞的竞争，将刺激水平低的识别球清除，使 网络对模糊边界点不敏感，从而能够代表各类的典型样本，使得到的网络具有清 晰的结构，同时大大提高运算效率，解决了网络规模随迭代次数以及运行时问随 数据量呈指数增长这一难题，使基于网络结构的聚类算法更适合大数据集聚类分 析。 6 由于对聚类分析而言，聚类有效性问题经常可以转化为最佳类别数k 的自 动确定。所以我们提出划分模糊度这一新概念，同时兼顾数据集的模糊划分信息 和几何结构信息，将模糊划分熵与划分模糊度相结合，定义了一种修正的划分模 糊度作为聚类有效性函数。这种新的聚类有效性函数不仅能够有效地分析数值型 数据分类结果的合理性，而且对类属型数据也是有效的。并基于此，提出两种分 别适合于数值型数据和类属型数据的参数优选方法。 本文的工作受到国家自然科学基金和国家“8 6 3 ”计划的资助。 关键词：数据挖掘，模糊聚类分析，自然计算，数值特征，类属特征，克隆选择 禁忌克隆，模糊识别球，聚类有效性 a b s t r a c t i nr e c e n ty e a r s ，d a t am i n i n gi sb e c o m i n goneo ft h em o s ta d v a n c e da n da c t i v e r e s e a r c ht o p i c si nt h ef i e l do ft h ei n f o r m a t i o nd e c i s i o n m a k i n gi nt h ew o r l d a sa n e f f e c t i v et o o lo fd a t am i n i n g ，c l u s t e ra n a l y s i si sa t t r a c t i n gw i d ea r e n t i o n c l u s t e r i n gi s o n eo fm e t h o d so fm u l t i v a r i a n ts t a t i s t i c a la n a l y s i s ，a n doneo fi m p o r t a n tb r a n c h e so f u n s u p e r v i s e dc l a s s i f i c a t i o ni ns t a t i s t i c a lp a t t e r nr e c o g n i t i o n i nt h er e c e n tt w od e c a d e s ， c l u s t e ra n a l y s i si sm a d er a p i dd e v e l o p m e n t ，a n dm a n yn e wa l g o r i t h m sh a v e b e e n p r o p o s e df o rv a r i o u sa p p l i c a t i o n s n a t u r e i n s p i r e dc o m p u t a t i o ni s an o v e lc o m p u t i n gm e t h o d ，w h i c hi sm o d e l e d b a s e do nt h ef u n c t i o n s ，c h a r a c t e r i s t i c sa n dm e c h a n i s mo fo r g a n i s mi nn a t u r e i th a s a d a p t i v e ，s e l g o r g a n i z e da n ds e l f - l e a r n i n ga b i l i t i e s ，w h i c hc anb eu s e dt os o l v em a n y c o m p l e xp r o b l e m s s o ，n a t u r e i n s p i r e dc o m p u t a t i o ni sb e c o m i n gr e s e a r c hh o t s p o t ，a n d h a sb e e nw i d e l yu s e di ns o m ea p p l i c a t i o n s t oo v e r c o m et h ef a u l t i n e s s ，e v e ns e r i o u sd r a w b a c k so ft h ea v a i l a b l ec l u s t e r i n g a l g o r i t h m sf o rt h ea p p l i c a t i o n s i nd a t am i n i n g ，b yc o m b i n i n gt h en a t u r e - i n s p i r e d c o m p u t a t i o n ，t h et r a d i t i o n a lc l u s t e ra n a l y s i sa l g o r i t h m sa r es y s t e m a t i c a l l yi m p r o v e da n d i n n o v a t e di nt h i st h e s i s t h ee m p h a s i si sp u to nt h ed e f i n i t i o na n do p t i m i z a t i o nm e t h o d o ft h eo b j e c t i v ef u n c t i o no ft h ec l u s t e r i n ga l g o r i t h mf o rm i x e da t t r i b u t e sd a t as e t a n da n e wc l u s t e r i n ga l g o r i t h mw i t hn e t w o r ks t r u c t u r ei sp r o p o s e df o rl a r g e s c a l ed a t as e t s ， w h i c he x t e n d st h ea p p l i c a t i o nr a n g e so fc l u s t e ra n a l y s i s i na d d i t i o n ，an o v e lc l u s t e r v a l i d i t yf u n c t i o ni sd e v e l o p e df o rd a t am i n i n g t h ee x p e r i m e n t a lr e s u l t si l l u s t r a t et h e e f f e c t i v e n e s sa n dg o o dp e r f o r m a n c eo ft h ep r o p o s e dn e wi d e a sa n dn e wm e t h o d so n f u z z yc l u s t e ra n a l y s i s i ns u m ，t h em a i nr e s e a r c hf r u i t sa c h i e v e di nt h i st h e s i sa r eg i v e na sf o l l o w s w i t ht h ed e f i n i t i o no fan e wm a t c h i n gd i s s i m i l a r i t ym e a s u r e ，a no b j e c t i v ef u n c t i o n o fc l u s t e r i n ga l g o r i t h mi sd e v e l o p e db ym o d i f y i n gt h ec o m m o nc o s tf u n c t i o n ，i e ，t h e t r a c eo ft h ew i t h i nc l u s t e rd i s p e r s i o nm a t r i x ，w h i c hi ss u i t a b l ef o ra n a l y s i so fd a t as e t s w i t hm i x e da t t r i b u t e s t h eg e n e t i ca l g o r i t h m s ( g a ) i se m p l o y e dt oo p t i m i z et h e d e v e l o p e do b j e c t i v ef u n c t i o nf o ro v e r c o m i n gt h ed r a w b a c ko ft h et r a d i t i o n a lf u z z y k m e u n s ( f k m ) a l g o r i t h m ，f e ，s e n s i t i v i t yt ot h ei n i t i a l i z a t i o n t h eg a - b a s e dc l u s t e r i n g a l g o r i t h mc a nc o n v e r g et ot h eg l o b a lo p t i m aw i t hah i g hp r o b a b i l i t y t oa v o i dt h ep r e m a t u r ep h e n o m e n o no ft h eg aa l g o r i t h m ，t h ec l o n a ls e l e c t i o n a l g o r i t h m ( c s a ) i na r t i f i c i a l i m m u n es y s t e m ( a i s ) i se m p l o y e dt o o p t i m i z et h e d e v e l o p e do b j e c t i v ef u n c t i o no fc l u s t e ra n a l y s i s s i n c et h ec s ab e l o n g st ot h e p o p u l a t i o ns e a r c hs t r a t e g yw i t hi n t r i n s i cp a r a l l e l i s ma n ds t o c h a s t i cs e a r c hm e c h a n i s m i t canc o n v e r g et ot h eg l o b a lo p t i m aw i t hp r o b a b i l i t yo f1a n dw i t hh i g h e rs p e e do v e rt h e g a b a s e da l g o r i t h m s o ，t h ec s a b a s e dc l u s t e r i n ga l g o r i t h mi ss u i t a b l ef o r t h e l a r g e s c a l ed a t as e t s b yc o m b i n i n gt h ea r t i f i c i a li m m u n en e t w o r k ( a i n ) t h e o r yi na i s ，a 1 1a i n b a s e d c l u s t e r i n ga l g o r i t h mi sp r e s e n t e df o ra u t o m a t i c a l l yo b t a i n i n gt h en u m b e ra n dt y p eo ft h e c l u s t e rp r o t o t y p e s s i n c et h en e wa l g o r i t h mcand e t e c ts o m en e u r o u sa st h et y p i c a l s a m p l e s ，t h eo b t a i n e dn e u r o n sc anb eu s e dt op a r t i t i o nt h ed a t as e ti n t os u b s e t s t h e nb y a n a l y z i n gt h ec o n n e c t e dw 毛i g h t sa m o n gt h en e u r o n sw i t ht h em i n i m a ls p a n n i n gt r e e ( m s t ) ，t h ef i n a lc l u s t e r i n gr e s u l tw i l lb ea c h i e v e da u t o m a t i c a l l yw i t hp r o p e rc l u s t e r n u m b e ra n dp r o t o t y p e s f o l l o w i n goneo ft h ei m m u n ea d j u s t m e n tm e t h o d si nb i o l o g yi m m u n es y s t e m ，f e ， f o r b i d d e nc l o n e ，an e wc l o n a lo p e r a t o r , f o r b i d d e nc l o n ei sp r o p o s e d b yc o m b i n i n gt h e f o r b i d d e nc l o n ea n dt h ec s a ，ac l o n a l o p e r a t o r - b a s e dc l u s t e r i n ga l g o r i t h mw i t h n e t w o r ks t r u c t u r ei sf o r m e d s i n c et h en e wa l g o r i t h mh a sb o t ht h ec h a r a c t e r i s t i c so f i m m u n ep a t i e n c ea n dt h ei m m u n es p e c i a l i t y , i tc a l lc o n s t r u c ta ne f f e c t i v ec l e a rn e t w o r k s t r u c t u r e ，w h i c hm a k e st h ec l u s t e r i n ga l g o r i t h mi n s e n s i t i v et ot h eb o u n d a r yp o i n t sa n d t h en o i s ep o i n t s i m i t a t i n gt h er e s o u r c e l i m i t e dt h e o r yi ni m m u n es y s t e m ，an o v e lc l u s t e r i n gm e t h o d w i t hf u z z yn e t w o r ks t r u c t u r eb a s e do nl i m i t e dr e s o u r c ei sd e v e l o p e dt or e a l i z et h e a u t o m a t i o no fc l u s t e ra n a l y s i sw i t h o u tp r i o r ii n f o r m a t i o n i nt h en e w a l g o r i t h m ，af u z z y a r t i f i c i a lr e c o g n i t i o nb a l l ( a r b ) i sd e s i g n e d ，w h o s ee f f e c tr a n g ei sv a r i o u sw i t ht h e e x c i t a t i o nl e v e l b yt h ec o m p e t i t i o no ft h ebc e l l s ，t h ea r bw i t hl o we x c i t a t i o nl e v e l w i l lb ee l i m i n a t e d i nt h eo n eh a n d ，i tc a no b t a i nac l e a rn e t w o r ks t r u c t u r ea n dm a k et h e n e t w o r ks t r u c t u r ei n s e n s i t i v et ot h ef u z z yb o u n d a r ys a m p l e s i nt h eo t h e rh a n d ，i tc a n i m p r o v et h ec o m p u t a t i o n a le f f i c i e n c yg r e a t l y , w h i c hs o l v e st h ed i f f i c u l t yo ft h e e x p o n e n t i a li n c r e a s i n go ft h en e t w o r ks c a l ea n dt h ec p ut i m ew i t ht h ei t e r a t i o n g e n e r a t i o na n dd a t aa m o u n t f o rt h ec l u s t e ra n a l y s i sp r o b l e m ，t h ec l u s t e rv a l i d i t yc a nb eo f t e nc o n v e r t e dt ot h e d e t e r m i n a t i o no ft h eo p t i m a lc l u s t e rn u m b e r , k f o rt h i sp u r p o s e ，an e wc o n c e p t ，f u z z y p a r t i t i o nd e g r e ei sp r o p o s e d ，w h i c hc a nr e f l e c tb o t ht h ef u z z yp a r t i t i o ni n f o r m a t i o na n d t h eg e o m e t r i cs t r u c t u r ei n f o r m a t i o no ft h ed a t as e t b yc o m b i n i n gt h ef u z z yp a r t i t i o n e n t r o p ya n dt h ef u z z yp a r t i t i o nd e g r e e ，am o d i f i e df u z z yp a r t i t i o nd e g r e ei sd e f i n e da sa c l u s t e rv a l i d i t yf u n c t i o n t h ep r o p o s e dc l u s t e rv a l i d i t yf u n c t i o nc a ne f f e c t i v e l ya n a l y z e n o to n l yt h en u m e r i ca t t r i b u t e sd a t as e t s ，b u ta l s ot h ec a t e g o r i c a la t t r i b u t e sd a t a s e t s b a s e d0 1 3 t h ed e f i n e df u n c t i o n ，t w om e t h o d so fp a r a m e t e ro p t i m a lc h o i c er r ep r o p o s e d f o rt h en u m e r i ca t t r i b u t e sd a t as e t sa n dc a t e g o r i c a la t t r i b u t e sd a t as e t sr e s p e c t i v e l y k e yw o r d s ：d a t am i n i n g ，f u z z yc l u s t e ra n a l y s i s ，n a t u r e i n s p i r e dc o m p u t a t i o n ，n u m e r i c a t t r i b u t e s ，c a t e g o r i c a la t t r i b u t e s ，c l o n a ls e l e c t i o na l g o r i t h m ，f o r b i d d e n c l o n e ，f u z z ya r t i f i c i a lr e c o g n i t i o nb a l l ，c l u s t e rv a l i d i t y 独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处， 本人签名：銮瞳 本人承担一切相关责任。 日期呈! ! 主! ! ! 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密在一年解密后适用本授权书。 本人签名 导师签名 日期如牟。，o - ，o 第一章绪论 1 第一章绪论 本章主要介绍了本文研究的背景及意义，概述了模糊聚类理论以及自然计算的研究进展 和现状，分析了在数据挖掘申，模糊聚类算法存在的主要问题和本文的研宄方向，列举了本 文研究的主要成果和创新点，最后给出全文的内容安排。 1 1 研究背景及意义 近十几年来，随着计算机技术的迅猛发展，人们获取与采集数据的能力大大 提高，信息量以前所未有的速度迅速增长。例如：在商品中我们广泛使用条形码， 科学研究和政府部门中运用电子化事务处理技术，以及数据收集工具和技术的多 元化( 从文本扫描到卫星遥感) 等等。除此之外，互联网的发展更是为我们带来 了海量的数据和信息。 但存储在各种数据媒介中的海量的数据，在缺乏强有力的分析工具的情况下， 已经远远地超出了人的理解和概括能力。例如，纽约时报在6 0 年代每份报纸 只有1 0 - - 2 0 版，而现在已经扩张至1 0 0 2 0 0 版，最高时曾达1 5 7 2 版；我国北 京青年报每份也有1 6 4 0 版；而市场营销报已达1 0 0 版。然而在现实社会中， 人均日阅读时间通常为3 0 4 5 分钟，大约只能浏览一份2 4 版的报纸。为此，这 种大量的原始数据和对功能强大的数据分析工具的需求共存的局面，被有的人描 述为“胖数据，瘦信息”( d a t ar i c hb u ti n f o r m a t i o np o o r ) 。许多的数据库也就成了 “数据坟墓”( d a t at o m b ) 换言之，这些数据很少被再访问。 面对海量的数据，数据挖掘技术应运而生并得到快速的发展，成为目前国际 数据库和信息决策领域最前沿、最活跃的研究方向之一，引起了学术界和工业界 的广泛关注。 数据挖掘( d a t am i n i n g ) 就是指从大量的、不完全的、有噪声的、模糊的、 随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有 用的信息和知识的过程。 那么什么是知识呢? 从广义上理解，数据、信息也是知识的表现形式，但是 人们更把概念、规则、模式、规律和约束等看作知识。人们把数据看作是形成知 识的源泉，好像从矿石中采矿或淘金一样。原始数据可以是结构化的，如关系数 据库中的数据；也可以是半结构化的，如文本、图形和图像数据；甚至是分布在 网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的：可以 2西安电子科技大学博士论文：基于自然计算的模糊聚类新算法研究 是演绎的，也可以是归纳的。发现的知识可以被用于信息管理，查询优化，决策 支持和过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门交叉学 科，它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提 供决策支持。在这种需求牵引下，汇聚了不同领域的研究者，尤其是数据库技术、 人工智能技术、数理统计、可视化技术、并行计算等方面的学者和工程技术人员， 投身到数据挖掘这一新兴的研究领域，形成新的技术热点。 一个典型的数据挖掘系统的体系结构如图1 1 1 所示。 数据清 图1 1 1一个典型的数据挖掘系统 其中，数据库、数据仓库或者其他一些信息存储媒介是数据挖掘的工作对象；服 务器主要是响应数据挖掘引擎的请求，提取相应的数据：知识库主要用来指导挖 掘的过程，以及用来评价挖掘出来的候选模式；模式评价模块主要是根据一定的 度量标准来与数据挖掘模块交互，以使得数据挖掘向着我们感兴趣的方向进行： 图形用户界面主要是为方便用户与数据挖掘系统的交互，由用户提出挖掘任务、 指定重要的挖掘参数以及由当前返回的结果指导进行更进一步的挖掘工作；数据 挖掘引擎是整个系统的核心部分，可以由以下模块组成：分类模块、关联规则模 块、聚类分析模块、时序模块和异常分析模块等。 作为数据挖掘的一种有效工具，聚类分析引起了人们的广泛关注，也得到了 许多成功的应用。但由于数据挖掘中所需处理的数据具有一些特殊的特性，分别 第一苹绪论 3 表现在数据量巨大、分布模式不同以及数据特征有数值型和非数值型之分等方面， 所以现有的聚类算法很少能够同时兼顾上述几个要求，本文研究的就是在大数据 集情况下混合属性特征的数据聚类问题，希望本文的工作能为聚类分析在数据挖 掘中的应用起到积极的促进作用。 在展开讨论之前，首先让我们对聚类问题作一简单介绍： 1 聚类分析的基本概念 聚类( c l u s t e r i n g ) 就是按照一定的要求和规律对事物进行区分和分类的过程， 在这一过程中没有任何关于类别的先验知识，也没有教师的指导，仅靠事物间的 相似性作为类属划分的准则，因此属于无监督分类的范畴。聚类分析( c l u s t e r i n g a n a l y s i s ) 卿 是指用数学的方法研究和处理给定对象的分类。“人以群分，物以类聚”， 聚类是一种重要的人类行为，早在孩提时代，一个人就通过不断地改进下意识中 的聚类模式来学会如何区分猫和狗，或者动物和植物。聚类也是一个古老的问题， 它伴随着人类社会的产生和发展而不断深化，人类要认识世界就必须区别不同的 事物并且认识事物间的相似性2 89 1 。 聚类分析是多元统计分析的一种，也是非监督模式识别的一个重要分支。它 把一个没有类别标记的样本集按某种准则划分成若干个子集( 类) ，使相似的样本 尽可能归为一类，而不相似的样本尽量划分到不同的类中。 传统的聚类分析是一种硬划分，它把每个待辨识的对象严格地划分到某类中， 具有非此即彼的性质，因此这种类别划分的界限是分明的。而实际上大多数对象 并没有严格的属性，它们在性态和类属方面存在羞中介性，具有亦此亦彼的性质， 因此适合进行软划分。模糊集理论1 2 6 3 】的提出为这种软划分提供了有力的分析工 具，人们开始用模糊的方法来处理聚类问题，并称之为模糊聚类分析。由于模糊 聚类得到了样本属于各个类别的不确定性程度，表达了样本类属的中介性，即建 立起了样本对于类别的不确定性描述，更能客观地反映现实世界，从而成为聚类 分析研究的主流田。 2 聚类分析的数学模型 设x = x 。，x ：，x 。 是待聚类分析的对象的全体( 称为论域) ，z 中的每个对 象( 称为样本) 墨( 1 s i sh ) 常用有限个参数值来刻划，每个参数值刻划曩的某个 特征。于是对象溉就伴随着一个向( 矢) 量p ( x 。) = 0 ，x m ，j ，。) ，其中x a ( 1 j ) 是x ，在第j 个特征上的赋值，p ( 而) 称为而的特征向量或模式矢量。聚类分析就是 分析论域中的”个样本所对应的模式矢量问的空间距离及分散情况，按照各样 本间的距离远近关系把x 。，x ：，x 。划分成t 个不相交的模式子集z l ，而，以，并 要求满足下列条件： 4西安电子科技大学博士论文：基于自然计算的模糊聚类新算法研究 l u 噩u u x k = ；x i n x j = o ，1 i k ( 1 1 1 ) 样本x 们s 门) 对子集( 类) 置( 1 i 七) 的隶属关系可用隶属函数表示为： e 班峋= 怙嚣 坨， 其中，隶属函数必须满足条件w f 地。也就是说，要求每一个样本能且只能隶 属于某一类，同时要求每个子集( 类) 都是非空的。 2 h 岍砉w 一撒队舌n w 刺， 1 在模糊聚类中，样本集x 被划分成f 个模糊子集j i ，牙2 ，兄，而且样本的隶 属函数”f 从 o ，1 ) 二值扩展到【0 ，1 区间，满足条件： u ks u p p ( x ，) = x ；w 矿 0 ，1 ；圭w 口= 1 ，v ，；0 量膏 玎，v i ( 1 1 4 ) - ii = 1 j = i 其中s u p p 表示取模糊集合的支撑集【l ”j 。 3 聚类分析研究的意义 虽说数据挖掘出现的时间不长，但是其发展速度异常迅猛。从数据库中发现 知识( k n o w l e d g e d i s c o v e r ya n d d a t a m i n i n g ，k d d ) 一词首次出现在1 9 8 9 年举行 的第十一届国际联合人工智能学术会议上。到目前为止，由美国人工智能协会主 办的k d d 国际研讨会已经召开了1 3 次，规模由原来的专题讨论会发展到国际学 术大会，研究重点也逐渐从发现方法转向系统应用，注重多种发现策略和技术的 集成，以及多种学科之间的相互渗透。i e e e 的k n o w l e d g ea n d d a t a e n g i n e e r i n g 会 刊率先在1 9 9 3 年出版了k d d 技术专刊。 此外，在i n t e r n e t 上还有大量的k d d 电子出版物，其中以半月刊k n o w l e d g e d i s c o v e r yn u g g e t s 最为权威( h t t p ：l w w w k d n u g g e t s c o r n s u b s c r i b e h t m l ) 。在网上还 有许多自由论坛，如d me m a i lc l u b 等。目前，世界上比较有影响的典型数据挖 掘系统有：s a s 公司的e n t e r p r i s em i n e r 、i b m 公司的i n t e l l i g e n tm i n e r 、s g i 公司 的s e t m i n e r 、s p s s 公司的c l e m e n t i n e 、s y b a s e 公司的w a r e h o u s es t u d i o 、r u l e q u e s t r e s e a r c h 公司的s e e 5 、还有c o v e r s t o r y 、e x p l o r a 、k n o w l e d g ed i s c o v e r y w o r k b e n c h 、d b m i n e r 、q u e s t 等。 第一章绪论 5 与困外相比，国内对数据挖掘的研究稍晚，没有形成整体力量。1 9 9 3 年国家 自然科学基金首次支持复旦大学朱扬勇教授对浚领域的研究项目。目前，国内的 许多科研单位和高等院校竞相丌展知识发现的基础理论及其应用研究，这些单位 包括清华大学、中科院计算技术研究所、空军第三研究所、海军装备论证中心等。 其中，北京系统工程研究所对模糊方法在知识发现中的应用进行了较深入的研究， 北京大学也在丌展对数据立方体代数的研究，华中理工大学、复旦大学、浙江大 学、中国科技大学、中科院数学研究所、吉林大学等单位开展了对关联规则开采 算法的优化和改造：南京大学、四川联合大学和上海交通大学等单位探讨、研究 了非结构化数据的知以发现以及w e b 数据挖掘。 然而作为数据挖掘中的重要分支和有效工具，聚类分析并非一个新领域，它 早已被应用在其它学科中。d u b e s 和j a i n 关于聚类分析的综述包括了从7 7 份杂志 和4 0 奉书中摘取出来的2 5 0 条引文1 2 ”j ，如此巨大的文献量说明了聚类分析的重 要性和交叉学科性，也足以说明它的发展及应用前景的广阔性。 同时，国际和国内的学者都对聚类分析的研究非常重视，i e e e 的会刊中模式 分析与机器智能( 队m i ) 、系统、人和控制( s m c ) 、模糊系统( f s ) 、神经网络 ( n n ) 、信号处理( s p ) 等杂志中几乎每期都有讨论聚类分析问题的文章。从9 2 年开始的l j | i e e e 和神经网络理事会共同主办的f u z z i e e e 会议，每两年召丌一 次，每次至少山3 到4 个专题讨论浆类和模糊聚类分析的研究进展和发展现状。 另外，我国作为模糊数学研究的大国，不仅在基础理论研究上取得了丰硕的成果， 而且在模糊聚类等的应用研究上亦令人瞩目，比如基于模糊聚类的天气预报、矿 藏识别和医学诊断等等。在这样的背景下，研究( 模糊) 聚类分析的意义也就不 言而i 喻了。 1 2 聚类理论研究进展及现状 由上一节的介绍可知，随着模糊集理论的不断发展和深化，用模糊的手段处 理聚类分析问题已经逐渐成为本领域研究的主流。最早系统地表述和研究模糊聚 类问题的是著名学者r u s p i n i1 2 1 7 1 1 2 1 9 1 1 2 1 8 1 ，他率先定义了模糊划分的概念。利用这一 概念，人们相继提出了多种模糊聚类分析方法，比较典型的有：基于相似性关系 和模糊关系的方法【2 3 2 】【2 6 4 【1 4 】、基于模糊等价关系的传递闭包方法【7 0 】1 2 ”1 、基于模糊 图沦的最大树方法2 6 5 l 2 8 】【2 5 ”、以及基于数据集的凸分解、动态规划和难以辨识关 系等方法f 2 6 】7 5 1 【j 8 j 】。然而，上述方法均不能适用于大数据量的情况，难以满足实时 性要求较高的场合，因此在实际中应用并不广泛，现在这些方面的研究已经逐步 减少了。 6蛐安电子科技人学博二e 论文：基于自然计算的模糊聚类新算法刈f 究 实际中受到人们普遍欢迎的是基于目标函数的模糊聚类方法，该方法把聚类 归结成一个带约束的非线性规划问题，通过优化求解获得数据集的模糊划分和聚 类。这类方法设计简单、解决问题的范围广，还可以转化为优化问题两借助经典 数学的非线性规划理论求解，并易于计算机实现。因此，随着计算机的应用和发 展，基于目标函数的模糊聚类算法成为新的研究热点。 为了使研究的算法能够针对数据挖掘的应用，我们首先将兴趣集中在基于目 标函数的模糊聚类上。以下，从目标函数的演化、算法的实现途径、有效性度量 方式等三个方而综述这类方法的研究进展及现状。 1 模糊聚类目标函数的演化 山上一仃介绍的模糊聚类的数学模型可知，对于一组给定的样本集x ，模糊 聚类分析可以很容易获得它的一个模糊七- 划分：= 坳1 1 i 女；1 s ，h 。但是， 要保证划分的有意义，则需要依据问题的需要定义合适的划分准则，比如常用的 相似( 异) 性准则d ( ) 。假定每个模糊子集臂，( 1 i k ) 都形成一个模式p ，( 常被 称作聚类原型) ，则样本x ，与模糊子集岩，的相似性可以通过它与聚类原型p ，间的 失真度d 。= d ( x j , p ) 来度量，从而确定最优模糊划分矩阵。不过，除了聚类原 型的类型需要事先指定以外，有关原型的参数事先是无法得知的，需在聚类过程 中逐步形成。 这样，为了保证聚类的结果能使“物以类聚”，就以极小化的每类样本与该类 模式叫的失真度构造模糊聚类的目标函数，然后通过优化该目标函数获得样本集 的最佳模糊“划分w = 1 i 和每类的模式p = 协，1s ，k 。常见的模糊聚类目标 函数形式如下，为一带约束的非线性函数： 。伊) 厶2 砉砉( 峋尸- d 2 ( 胁) + f ，“，( 峋) e c c ，2 ， 其中，f 为惩罚项，厂( ) e c 为约束条件，口为加权指数。这样以来，模糊聚类 的目标函数就由参量集 w ，d ( ) ，尸，口，x 丽确定。 b e z d e k 在研究中发现，对于不同的应用背景，最优的d 值可以在1 1 口5 的 范围内寻找【2 。在不做特殊要求时，可选用该区间的中值口= 2 。所以，在本文中， 一般情况下，我们不对a 的取值进行讨论。以下，我们分别从模糊划分矩阵、相 似性准则聚类原型以及数据集这几个角度来概述目标函数的演化过程。 ( 1 ) 对模糊划分矩阵的研究 传统聚类分析是一种硬划分，嘞 q l 为样本。类属的指示函数。为了表达 模式问的相近信息，人们引入了模糊划分的概念，令 o ，l 】，并满足冬。峋= 1 ， 第一章绪论 7 但这种隶属度只能表示样本在类问的分享程度，而无法反映其典型性，所以 k r i s h n a p u r a m 趼”研等提出可能性划分的概念，放松了该约束。为了结合硬聚类和 模糊聚类的优点，s e l i m 和i s m a i l 2 2 4 】在1 9 8 4 年又提出了半模糊划分的概念，只保 留划分矩阵中较模