（计算机系统结构专业论文）改进蚁群算法在聚类分析中的应用研究.pdf

重庆大学硕士学位论文 中文摘要 摘要 由信息技术、网络技术的飞速发展所导致的“数据爆炸但知识贫乏”的现象 日益严重，应运而生的数据挖掘( d a t am i n i n g ) 技术在这一环境下得到了蓬勃 的发展，越来越显示出其强大的生命力。国内主流网站评比的未来十大热门技 术中，数据挖掘技术占了一席之地。而且现今世界几大超级公司也早早的投入 到数据挖掘技术领域的研究中来了。这其中包括i b m 、m i c r o s o f t 等等。数据挖 掘是一个多学科交叉的研究领域，涉及到了数据库技术、人工智能、机器学习、 统计学、知识获取、生物计算等等许多跨行业的学科的理论和技术，其发展必 将大大地影响全球信息化的进程。因此对数据挖掘技术进行全面的、系统的、 深入的研究是信息化发展的客观需求。本文对数据挖掘技术，尤其是聚类分析 进行了较为深入的研究与分析，并且提出了一些改进的算法。本文主要包含了 以下几个方面的内容： 数据挖掘中聚类分析的概述。首先对数据挖掘的概念、数据挖掘系统作了 介绍，然后介绍了数据挖掘的分类、过程、数据挖掘的主要问题。随后对数据 挖掘技术中的一个重要组成部分聚类分析进行了阐述说明，主要介绍了聚类 分析的定义、进行聚类所使用的方法、数据类型以及聚类结果的度量标准。 蚁群算法的概述。群体智能算法是人们通过观察自然界生物群体抽象出来 的仿生类算法，而蚁群算法作为生物群体智能算法的代表在求解复杂优化问题， 尤其是离散优化问题方面展现出了优异的性能和巨大的发展潜力。本文从基本 蚁群的生物学原理和系统学特征出发，介绍了基本蚁群算法的数学模型和实现 方法，并分析了基本蚁群算法的时间空间复杂度问题。 基于改进蚁群算法的聚类组合方法。在研究了基本蚁群聚类模型、经典l f 算法以及引入了信息熵的l f 算法的基础上，提出了改进的单蚁群聚类算法 ( s a c a ) ，然后提出一种利用速度类型各异的单蚁群以$ a c a 并行聚类，然后 将产生的结果用超图模型组合成超图，最后利用基于蚁群算法的图划分算法对 超图进行划分的多蚁群聚类组合方法：m a c c a 。最后对m a c c a 进行数据测 试和性能分析。 关键词：数据挖掘，聚类分析，蚁群算法，s a c a 算法，m a c c a 算法 重庆大学硕士学位论文英文摘要 a b s t r a c t t h ef a s t d e v e l o p m e n to fi n f o r m a t i o na n dn e t w o r kt e c h n o l o g yc a u s e st h e p h e n o m e n o no f i n f o r m a t i o ne x p l o d i n g b u tk n o w l e d g ep o o l i tb e c o m e sm o r ea n d m o r et o u g hd a yb yd a y i no r d e rt os o l v et h i sp r o b l e m ，d a t am i n i n gw a sp u tf o r w a r d a san e wt e c h n o l o g y , d a t am i n i n gg r e wu pv i g o r o u s l ya n df a s ti nt h es p e c i f i c e n v i r o n m e n t a n di td e m o n s t r a t e di t ss t r o n gv i t a l i t yi nd i f f e r e n tc i r c u m s t a n c e s i n s o m ep r i m a r yw e b s i t e s ，d a t am i n i n gw a sc h o s e na so n eo ft h em o s tp o p u l a r t e c h n o l o g i e si nt h ef u t u r e n o w a d a y s ，m o r ea n dm o r ec o m p a n i e se s p e c i a l l ys u p e r o n e ss u c ha si b ma n dm i c r o s o f td e v o t e dm a n yr e s o u r c e st od i v i n gi n t od a t am i n i n g d a t am i n i n gi sat e c h n o l o g yo fm u l t i p l ed i s c i p l i n e s i ti si n v o l v e di nm a n ys u b j e c t s s u c ha s d a t a b a s e ， a r t i f i c i a l i n t e l l i g e n c e ，s t a t i s t i c s ，k n o w l e d g e d i s c o v e r y , b i o l o g y - c o m p u t i n ga n ds oo u t h ed e v e l o p m e n to fd a t am i n i n gw o u l da f f e c tt h e p r o c e s so f 百o b a li n f o r m a t i o ng r e a t l y s oi ti sn e c e s s a r yt od i v ei n t od a t am i n i n g s y s t e m a t i c a l l y , r o u n d l ya n dd e e p l y t h i sd i s s e r t a t i o ns t u d i e da n da n a l y z e dd a t a m i n i n gd e e p l y , e s p e c i a l l yt h ec l u s t e r i n ga n a l y s i s ，w h i c ht a k e sag r e a tp a r to fd a t a m i n i n gr e s e a r c h e s a n ds o m ei d e a sa n di m p r o v e m e n t sa r ep r o p o s e da f t e r w a r d t h e m a i nc o n t e n t so f t h i sd i s s e r t a t i o na r el i s t e da sf o l l o w s ： d e s c r i p t i o no fc l u s t e r i n ga n a l y s i si nd a t am i n i n g t h ec o n c e p t so fd a t am i n i n g a n dd a t am i n i n gs y s t e ma r ei n t r o d u c e da tt h eb e g i n n i n g t h e nt h ec l a s s i f i c a t i o n ， p r o c e s sa n dm a i nt a s k so fd a t am i n i n ga r ei n t r o d u c e db r i e f l y a so n eo ft h em o s t i m p o r t a n tp o r t i o n si nt h er e s e a r c ho f 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 si sm a i n l yu s e d t od i s c o v e rt h ev a l u a b l ed a t ad i s t r i b u t i o na n dd a t am o d ei nt h ep o t e n t i a ld a t a c l u s t e r i n ga n a l y s i s ，i n c l u d i n gi t sd e f i n i t i o n ，m e t h o d s ，d a t at y p e sa n dt h es t a n d a r d s o f m e a s u r i n gt h er e s u l t sa r ep r e s e n t e da sw e l l d e s c r i p t i o no fb a s i ca n tc o l o n ya l g o r i t h m ( a c a ) t h ei n t e l l i g e n tc o l o n y a l g o r i t h m s ，w h i c ha r ea b s t r a c t e df r o mn a t u r a lb i o l o g i cc o l o n i e s ，a r eo n l yas l i c eo f b i o n i ca l g o r i t h m st h a tg e n e r a t e db yl o n gt e r mo b s e r v a t i o n a sar e p r e s e n t a t i v e b i o n i ca l g o r i t h m ，a c as h o w sg r e a tp e r f o r m a n c ea n dt r e m e n d o u sp o t e n t i a lo f e v o l u t i o ni n s o l v i n gc 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 ，e s p e c i a l l y d i s c r e t e o p t i m i z a t i o np r o b l e m s i nt h i sd i s s e r t a t i o n ，b a s i ca c ai s d e s c r i b e df r o mi t s b i o l o g i c a lt h e o r i e sa n dc h a r a c t e r i s t i c so fs y s t e mt oi t sm a t h e m a t i c a lm o d e la n d i m p l e m e n t a t i o n a tl a s t ，t h et e m p o r a la n ds p a t i a lc o m p l e x i t i e sa r ea n a l y z e da sw e l l 重庆大学硕士学位论文英文摘要 c l u s t e r i n gc o m b i n a t i o nm e t h o db a s e do ni m p r o v i n ga c a o nt h eb a s i so f l e a r n i n gb a s i c a n tc o l o n yc l u s t e r i n gm o d e l ，l fa l g o r i t h ma n dl fa l g o r i t h mb a s e do n e n t r o p y , s i n g l ea n t c o l o n yc l u s t e r i n ga l g o r i t h m ( s a c a ) i sb r o u g h tf o r w a r d t h e n m u l t i p l ea n t - c o l o n i e sc l u s t e r i n gc o m b i n a t i o na l g o r i t h m ( m a c c a ) i si n t r o d u c e d a sw e l l i t sm a i nt h e o r yi st h a ta f t e rp a r a l l e l i z e dr u n n i n gs e v e r a ls a c aa td i f f e r e n t v d o c i ws t y l e s ，t h er e s u l t sa r et r a n s f o r m e dt oah y p e r g r a p hb yt h eh y p c r g r a p hm o d e l ， a n da tl a s tt h eh y p e r g r a p hi sc o m p a r t m e n t a l i z e db yg r a p h - d i v i s i o na l g o r i t h mb a s e d o na n t c o l o n ya l g o r i t h m t h em a c c at e s t r e s u l t so ff u n c t i o n a l i t i e sa n d p e r f o r n l a n c ea r ep r e s e n ta sw e l l 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 ，s a c a ， m a c c a i l l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重废太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名夕料 学位论文版权使用授权书 本学位论文作者完全了解重庆太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重废太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( ) 。 ( 请只在上述一个括号内打“4 ”) 学位论文作者签名：纺玮 签字日期： 岬年占月牛日 导师签名：窘考口h 签字日期：矽亏年6 月铲日 重庆大学硕士学位论文 1 绪论 1 绪论 1 1 引言 人们在日常生活中经常会遇到这样的情况：超市的经营者希望将经常被同 时购买的商品放在一起增加销售额；保险公司想知道购买保险的客户一般具有 哪些特征；医学研究人员希望能从已有的成千上万份病历中找出某种疾病的病 人所具有的共同点，从而为至于这种疾病提供一些帮助等等。对于这些问题， 现有的信息管理系统中的数据分析工具无法给出解决方法。因为无论统计、查 询或报表，其处理方式都是对特定数据进行简单的数字处理，而不能对这些数 据所包含的内在信息进行提取，而随着数据量的激增，人们越来越希望系统能 够提供更高层次的数据分析功能，从而更好地去支持决策或科研工作。正是为 了满足这种要求，数据挖掘技术应运而生。 目前属于据挖掘的主要研究内容包括基础理论、发现算法、数据仓库、可 视化技术、定性定量互换模型、知识表示方式、发现知识的维护和再利用、半 结构化和非结构化数据中的知识发现以及网上数据挖掘等。数据挖掘和知识发 现的研究已经形成了三根强大的技术支柱：数据库、人工智能和数理统计。因 此，数据挖掘是一个借助数理统计技术和人工智能以及知识工程等领域的研究 成果构建自己的理论体系，是一个交叉学科领域。这些学科的发展为数据挖掘 的研究提供了新的机遇和挑战，而作为数据挖掘技术之一的聚类分析技术也越 来越受到研究者们的关注。 同时，自然界中的许多自适应优化现象不断给人以启示：生物体和自然生 态系统可以通过自身的演化就使得许多在人类看来高度复杂的优化问题得到完 美的解决。近些年来，一些经典的数学规划原理截然不同的、试图通过模拟自 然生态系统机制以求解复杂优化问题的仿生优化算法相继出现( 如遗传算法、 蚁群算法、微粒群算法、人工免疫算法、人工鱼群算法、混合蛙跳算法等) ，大 大丰富了现代优化技术，也为那些传统最优化技术难以处理的组合优化问题提 供了切实可行的解决方案。伴随着模拟自然与生物机理为特征的仿生优化算法 时代的悄然兴起，一些仿生优化算法已在经典的n p c 问题的求解和实际应用 中显示出强大的生命力和进一步发展的潜力。 1 2 国内外研究状态以及未来发展的趋势 1 2 1 国外研究状态 k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ) 【3 1 】一词首先出现在1 9 8 9 年8 月 重庆大学硕士学位论文 1 绪论 在美国底特律举行的第十一届国际联合人工智能学术会议上。随后在1 9 9 1 年、 1 9 9 3 年和1 9 9 4 年都举行过k d d 专题讨论会，汇集来自各个领域的研究人员和 应用开发者，集中讨论了数据统计、海量数据分析算法、知识表示、知识运用 等问题。到目前为止，由美国人工智能协会主办的k d d 国际研讨会已经召开 了8 次，规模由原来的专题研讨会发展到国际学术大会，研究重点也逐渐从发 现方法转向到系统应用，注重多种发现策略和技术的集成，以及多种学科之间 的相互渗透，1 9 9 9 年，亚太地区在北京召开的第三届p a k d d 会议收到1 5 8 篇 论文，空前热烈。i e e e 的k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊率先在1 9 9 3 年 出版了k d d 技术专刊，所发表的5 篇论文代表了当时k d d 研究的最新成果和 动态，较全面的论述了k d d 系统方法论、发现结果的评价、k d d 系统设计的 逻辑方法，讨论了鉴于数据库的动态性冗余、高噪声和不确定性、k d d 系统与 其他传统的机器学习、专家系统、人工神经网络、数理统计分析系统的联系和 区别，以及相应的基本对策【4 2 1 。并行计算、计算机网络和信息工程等其他领域 的国际学会、学刊也把数据挖掘和知识发现列为专蹶和专刊讨论，甚至到了脍 炙人口的程度【3 ”。 g a r t n e rg r o u p 的一次高级技术调查显示数据挖掘和人工智能列为“未来三 到五年内将对工业产生深远影响的五大关键技术”之首，并且还将并行处理体系 和数据挖掘列为未来五年内投资焦点的十大新兴技术前两位。m e t ag r o u p 曾 做出这样的评论：“全球重要的企业、组织会发现，到2 1 世纪数据挖掘技术将 是他们商业成功与否的至关重要的影响因素”【4 ”。 群体智能的研究在国外进行的比较早，目前主要是对蚁群算法的研究。自 1 9 9 1 年d o r i g o 首次提出蚁群算法以来，蚁群算法已经在组合优化、路由、数 据挖掘等多个领域取得了非常突出的成就，显示出这个算法具有较强的鲁棒性、 优良的分布式计算机、易于与其他方法结合的优点【2 】【3 1 。国际著名的顶级学术 刊物( ( n a t u r e曾多次对蚁群算法的研究成果进行报道， f u t u r eg e n e r a t i o n c o m p u t e rs y s t e m s ) ) 和 i e e et r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n ) 分别于 2 0 0 0 年和2 0 0 2 年出版了蚁群算法特刊，在比利时布鲁塞尔大学每两年召开一 次的蚂蚁优化国际研讨会进一步促进了这一智能计算领域的学术交流，从而使 这种新兴的仿生优化算法展现出勃勃生机，其应用范围完全可与遗传算法相媲 美。目前研究和应用的区域主要集中在比利时、意大利、英国、法国、德国等 欧洲国家，日本和美国也开始启动对蚁群算法的研究和应用【3 ”。 1 2 2 国内研究现状 与国外相比，国内对d m k d ( d a t a m i m n ga n d k n o w l e d g e d i s c o v e r y ) 的研 究稍晚，没有形成整体力量【1 6 i 。许多单位也已开始进行数据挖掘技术的研究， 2 重庆大学硕士学位论文 1 绪论 但还没有看到数据挖掘技术在我国成功应用的案例。 1 9 9 3 年国家自然科学基金首次支持我们对该领域的研究项目。目前，国内 的许多科研单位和高等院校竞相开展知识发现的基础理论及其应用研究，这些 单位包括清华大学、中科院计算技术研究所、空军第三研究所、海军装备论证 中心等。其中，北京系统工程研究所对模糊方法在知识发现中的应用进行了较 深入的研究，北京大学也在开展对数据立方体代数的研究，华中科技大学、复 旦大学、浙江大学、中国科技大学、中科院数学研究所、吉林大学等单位开展 了对关联规则开采算法的优化和改进；南京大学、四川联合大学和上海交通科 技大学等单位探讨、研究了非结构化数据的知识发现以及w e b 数据挖掘。 目前国内也开始有关于蚁群算法的公开报道，但是有关研究很多还只是停 留在试验探索阶段，尚未能提出一个完善的理论分析，对它的有效性也没有给 出严格的数学解释。但是，从目前模糊控制所碰到的情况看，理论上的不完善 并不妨碍应用，又是应用还会超前于理论，并推动理论的研究，蚁群算法也是 如此。 1 2 3 未来的发展趋势 当前，d m k d 研究方兴未艾。虽然数据挖掘的前景很好，但就目前来看这 一热门技术还处于初级探索阶段，更多地停留在理论研究上，而且这种研究是 漫长而不可完全预知的，在应用方面还不是很完善。所以以下几个方面将是未 来比较重要的数据挖掘研究方向【1 4 】【1 5 】： 研究在网络环境下的数据挖掘技术( w e bm i n i n g ) ，特别是在因特网上建 立数据挖掘服务器，并且与数据库服务器配合，实现w e bm i n i n g ； 加强对各种非结构化数据的开采( d a t a m i n i n g f o r a u d i o & v i d e o ) ，如对 文本数据、图形数据、视频图像数据、声音数据乃至综合多媒体数据的开采； 研究数据挖掘和数据仓库相结合的方式，数据挖掘与数据仓库一体化的 研究； 寻求数据挖掘过程中的可视化方法，使知识发现的过程能够被用户理解， 也便于在知识发现的过程中进行人机交互； 发现语言的形式化描述，即研究专门用于知识发现的数据挖掘语言，也 许会像s q l 语言一样走向形式化和标准化； 知识的维护更新。 同时，在蚁群算法创立的十多年来，无论在算法理论还是在算法应用方面 都取得了很多突破性的进展。尤其是近几年来，研究人员和研究成果均呈几何 级数增长，初步统计结果表明，2 0 0 0 年蚁群算法的相关学术论文不足2 0 0 篇； 而到了2 0 0 6 年6 月，蚁群算法的相关学术论文已经突破了1 6 0 0 篇，其应用范 重庆大学硕士学位论文 1 绪论 围几乎涉及到各个优化领域，而且还出现了蚁群算法仿生硬件。关于蚁群算法 在今后的研究方向，主要涉及以下几个方面【4 1 4 5 l ： 蚁群算法的模型改进：现在人们已经针对不同的具体问题提出了许多不 同类型的改进蚁群算法，但是这些改进的蚁群算法往往不具有很强的普适性， 而且自然界中的真实蚂蚁还有许多其他智能行为，所以蚁群算法模型还有很大 的改进空间； 蚁群算法的理论分析：蚁群算法是一种概率搜索算法，所以从数学上对 其正确性和可靠性进行证明相对于确定性算法而言比较困难，并且在蚁群算法 理论研究中，关于初始化参数选择问题、信息素分配问题、收敛速度问题都需 要进行很大功夫的研究分析； 蚁群算法的并行实现：从本质上来说，蚁群算法应以分布式的协同优化 计算方式为特征，但在串行计算机上对蚁群算法进行的模拟并不能真正体现蚁 群算法的本质特征，因此，开展蚁群算法的并行机研究也是一个研究方向； 蚁群算法的硬件实现：仿生硬件是并行计算环境下的产物，蚁群算法的 硬件实现时仿生硬件研究领域中的一个新的分支，但是在蚁群算法仿生硬件在 电路设计、其可靠性、可测试性、普适性、硬件规范等方面还需要进一步研究； 蚁群算法的智能融合：现在蚁群算法与遗传算法、人工神经网络、微粒 群算法、人工免疫算法已经有初步的融合，但是很多都是针对具体问题进行的 初步尝试，并且根据解决的问题不同，在融合策略上也有很大的差异，因此应 该在现有研究成果上继续进行深入研究，努力探索蚁群算法与一种或者几种仿 生算法相融合的统一机制； 蚁群算法在更多领域以及更深领域的应用：纵向而言，蚁群算法的应用 深度还不够，横向而言，蚁群算法的应用领域还需要进一步的拓展，所以不管 是蚁群算法的应用领域还是应用深度，都有很广阔的研究前景。 1 3 论文研究的内容和组织 本文的主要内容是研究作为数据挖掘技术重要组成部分的聚类分析技术和 适用于求解复杂的组合优化问题的蚁群算法，以及利用改进的蚁群算法在聚类 分析领域中的应用。 本文的结构是按照如下的方式进行组织的： 第l 章介绍了数据挖掘技术以及蚁群算法的产生、发展、国内外的研究现 状以及未来发展的趋势，同时提出本文研究的主要内容。 第2 章概述了数据挖掘的基础知识以及有关聚类分析技术的介绍。在关于 数据挖掘基础知识介绍中，包括了基本概念、挖掘技术的分类、常用的挖掘方 4 重庆大学硕士学位论文1 绪论 法以及挖掘的任务。为本文的全面展开做好了铺垫。同时，在有关聚类分析技 术的介绍中，主要对聚类分析的定义和聚类分析的度量标准作了简要的归纳和 总结。同时摘要的介绍了目前比较常用的物种聚类分析方法和聚类分析中常用 的数据类型。 第3 章是对蚁群算法进行分析和研究。在从深层意义上分析了蚁群算法机 制原理的基础上，讨论了基本蚁群算法的系统学特征，随后给出了基本蚁群算 法的数学模型和具体实现步骤。最后对基本蚁群算法的时间复杂性和空间复杂 性分别进行了分析。该章内容是对基本蚁群算法的机理分析，是深入理解蚁群 算法、利用蚁群算法展开研究工作的基础。 第4 章是基于改进蚁群算法的聚类分析算法的设计、分析、研究和评价。 本章首先对基本的蚁群聚类模型进行分析，随后对l f 算法以及基于信息熵的 蚁群聚类算法进行分析，然后对一种单蚁群聚类算法进行改进，通过模拟多蚁 群的协作性能，将运动速度各异的多个单蚁群独立且并行的进行聚类分析，并 将其聚类结果组合为超图，然后再用蚁群算法对超图进行二次划分。最后对改 进的应用与聚类分析蚁群算法进行实验并评价。 第5 章是对本文主要研究的内容和创新的内容作了总结，同时给出了进一 步的研究方向。 5 重庆大学硕士学位论文2 数据挖掘技术中的聚类分析 2 数据挖掘技术中的聚类分析 近年来，数据库的数量和单个数据库的规模都大大增加了。如何从庞大、 复杂的数据中提取出潜在的知识和有用的、可理解的模式以及空间数据库中的 空间关系，如何对以惊人速度增长的数据量进行解释和分析。人们需要能够对 数据进行更高层次的处理，以帮助人们更好的利用数据进行决策和研究，数据 挖掘技术应运而生。 聚类分析则是一种重要的人类行为，它的目的是把相似的东西归为一类， 使得类内具有较大的相似性，而类间具有较小的相似性。聚类分析是多元统计 分析的方法之一，它试图根据数据集的内部结构将数据集分成若干个不同的子 类，使得同一子类中的样本尽可能的相似，不同子类的样本尽可能的不相似。 聚类分析已经广泛的用在许多应用中，同时它是数据挖掘中的主要技术之一。 2 1 数据挖掘技术 2 1 1 数据挖掘概念 数据挖掘，英文是d a t am i m n g 。目前对数据挖掘技术一种比较公认的定义 是w j f r a w l e y ，gp i a t e t s k y o s h a p i r o 等人提出的：数据挖掘，就是从大量的、 不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先 不知道的、但又是潜在有用的知识和信息的过程【l ”。这个定义包含两个层次的 含义：( 1 ) 数据源必须是真实的、大量的、含有噪声的；( 2 ) 这些知识是隐含 的、事先未知的潜在有用信息，提取的知识表示为概念( c o n c e p t s ) 、规则 ( r u l e s ) 、规律( r e g u l a r i t i e s ) 等，最好能用自然语言表达的形式。而更广义 的说法是：数据挖掘意味着在一些事实或观察数据的集合中寻找模式的决策支 持过程。模式是一个用语言l 来表示的一个表达式e ，它可以用来描述数据集 合f 中数据的特性，e 所描述的数据是集合f 的一个子集f e 。e 作为一个模式 要求它比列举数据子集f e 中所有元素的描述方法简单。数据挖掘的对象不仅是 数据库，也可以是文件系统，或其他任何组织在一起的数据集合，例如w w w 信息资源。目前发展的热点是数据挖掘技术和数据仓库技术的结合。数据仓库 中包含了大量历史数据，这些数据是经过了规范化并且面向主题的组织的，在 数据仓库中进行数据挖掘是最容易的。 从数据挖掘的定义可以看出，作为一个学术领域，数据挖掘和数据库中知 识发现k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 具有很大的重合度，大部分学 者认为数据挖掘和知识发现是等价的概念，人工智能( a j ) 领域习惯称k d d ， 6 重庆大学硕士学位论文 2 数据挖掘技术中的聚类分析 而数据库领域习惯称数据挖掘。数据挖掘从理论和技术上继承了知识发现领域 的成果，同时又有着独特的内涵。数据挖掘更着眼于设计高效的算法以达到从 巨量数据中发现知识的目的。数据挖掘充分利用了机器学习、人工智能、模糊 逻辑、人工神经网络、分形几何的理论和方法。 从商业角度出发，数据挖掘可以描述为：按照企业既定业务目标，对大量 的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进 一步将其模型化的先进有效的方法。 目前，世界上比较有影响的典型数据挖掘系统有：s a s 公司的e n t e r p r i s e m 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 缸e h o u s es t u d i o 、r u l e q u e s tr 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 yw o r k b e n c h 、d b m i n e r 、q u e s t 等很多系统。 数据挖掘系统地输入是数据库的数据、信息分析员的指导以及存储在挖掘 系统知识库中的知识和规则。选择的数据在各种挖掘模块中处理，生成辅助模 式和关系。然后进行评价，通过与分析员交互以期发现令人感兴趣的模式。有 的还要加入知识库中，以便后继的抽取和评价，关于数据挖掘的逻辑模型可以 参照下图2 1 所示： 图2 1 数据挖掘逻辑模型 f i g2 1l o g i c a lm o d e lo f d a t am i n i n g 与数据挖掘关系密切的研究领域包括归纳学习( i n d u c t i v el e a r n i n g ) 、机器 学习( m a c h i n el e a r n i n g ) 和统计( s t a t i s t i c s ) 分析。特别是机器学习被认为和 7 重庆大学硕士学位论文2 数据挖掘技术中的聚类分析 数据挖掘的关系最密切。二者的主要区别在于：数据挖掘的任务是发现可以理 解的知识，而机器学习关心的是提高系统的性能，因此训练神经网络来控制一 根倒立棒是一种机器学习过程，但不是数据挖掘；数据挖掘的主要对象是大型 的数据集合，如数据仓库，但一般来说机器学习处理的数据集合要小得多，因 此效率问题对数据挖掘是至关重要的。 2 1 2 数据挖掘的分类 从不同的视角看，数据挖掘技术有几种分类方法：根据发现知识的种类分； 根据挖掘的数据库的种类分类和根据采用的技术分类。 根据挖掘的数据库分类 数据挖掘给予的数据库类型有：关系型( r e l a t i o n a l ) 、事务性 ( t r a n s a c t i o n a l ) 、面向对象型( o b j e c t e d o r i e n t e d ) 、主动型( a c t i v e ) 、空间型 ( s p a t i a l ) 、时间型( t e m p o r a l ) 、文本型( t e x t u a l ) 、多媒体( m u l t i m e d i a ) 、 异质( h e t e r o g e n e o u s ) 数据库和遗留( l e g a c y ) 系统等。 根据采用的技术分类 1 ) 人工神经网络：它从结构上模仿生物神经网络，是一种通过训练来学习 的非线性预测模型。可以完成分类、聚类、特征挖掘等多种数据挖掘任务。 2 ) 决策树：用树形结构来表示决策集合。这些决策集合通过对数据集的分 类产生规则。典型的决策树方法有分类回归树( c a i 盯) ，典型的应用是分类规 则的挖掘。 3 ) 遗传算法：是一种新的优化技术，基于生物进化的概念设计了一系列的 过程来达到优化的目的。这些过程有基因组合、交叉、变异和自然选择。为了 应用遗传算法，需要把数据挖掘任务表达为一种搜索问题而发挥遗传算法的优 化搜索能力。 4 ) 最邻近技术：这种技术通过k 个最与之相近的历史纪录的组合来辨别 新的记录。有时也称这种技术为k 最邻近方法。这种技术可以用作聚类、偏差 分析等挖掘任务。 5 ) 规则归纳：通过统计方法归纳、提取有价值的i f - t h e n 规则。规则归纳 的技术在数据挖掘中被广泛使用，例如关联规则的挖掘。 根据发现模式的种类分类 1 ) 关联规则挖掘；它要做的是从用户指定的数据库挖掘出满足一定条件的 依赖性关系。关联规则形如“饥一a 2 ，支持度= j ，可信度= c ”，其中s 和c 是 用户指定的支持度和可信度的阈值。这种关联规则挖掘可以在不同的抽象概念 层次上进行。例如r l “尿布一啤酒，支持度= 5 ，可信度= 5 0 ”与r 2 “婴儿用 品类一饮料类，支持度= 2 5 ，可信度= 8 0 ”相比，r 2 在更高的抽象层次上， 重庆大学硕士学位论文2 数据挖掘技术中的聚类分析 更为宏观，因而有较大的支持度和可信度，更适合高层决策需要。 2 ) 总结( s u m m a r i z a t i o n ) 规则挖掘：它要做的是从用户指定的数据库中 挖掘出( 以不同的角度或在不同的层次上的) 平均最d 最大值、总和、百分 比等等。挖掘结果用交叉表，特征规则，统计的曲线图表等等。 3 ) 分类( c l a s s i f i c a t i o n ) 规则挖掘：它做的是已知训练数据的特征和分类 结果，为每一个类找到一个合理的描述或模型，然后再用这些分类的描述或模 型来对未知的新的数据进行分类。 4 ) 聚类( c l u s t e r i n g ) 规则挖掘：它又称为无指导的分类( u n s u p e r v i s e d c l a s s i f i c a t i o n ) ，其宗旨在于实事求是地( 而不是按照人的主观认识) 按被处理 对象的特征分类，有相同特征的对象被归为一类，它与分类规则挖掘的区别在 于分类是基于训练数据的，而聚类直接对数据进行处理。 5 ) 预测( p r e d i c t i o n ) 分析：当分类的工作偏向于插入漏掉的数据，预测 数据分类或发展的趋势时，这时的工作就被称作预测分析。 6 ) 趋势( t r e n d ) 分析：趋势分析又叫时间序列分析，它是从相当长的时 间内的发展趋势中发现规律和趋势的。 7 ) 偏差分析( d e v i a t i o n ) 分析：偏差分析又叫比较分析，它将找出一系列 判别式的规则，以区别用户设定的两个不同类。 2 1 3 数据挖掘的过程 数据挖掘过程一般由3 个主要的阶段组成：数据准备、挖掘操作、结果表 达和解释。 数据准备阶段：这个阶段又可进一步分成3 个子步骤：数据集成、数据 选择、数据预处理。数据集成将多文件或多数据库运行环境中的数据进行合并 处理，解决语意模糊性、处理数据中的遗漏和清洗脏数据等。数据选择的目的 是辨别出需要分析的数据集合，缩小处理范围，提高数据挖掘的质量。预处理 是为了克服目前数据挖掘工具的局限性。 数据挖掘阶段：这个阶段进行实际的挖掘操作。包括要点有： 1 ) 首先决定如何产生假设，是让数据挖掘系统为用户产生假设，还是用户 自己对数据库中可能包含的知识提出假设。前一种称为发现型 ( d i s c o v e r y - d r i v e n ) 的数据挖掘；后一种称为验证型( v e r i f i c a t i o n d r i v e n ) 的 数据挖掘； 2 ) 选择合适的工具； 3 ) 挖掘知识的操作； 4 ) 证实发现的知识。 结果表述和解释阶段：根据最终用户的决策目的对提取的信息进行分析， 9 重庆大学硕士学位论文2 数据挖掘技术中的聚类分析 把最有价值的信息区分出来，并且通过决策支持工具提交给决策者。因此，这 一步骤的任务不仅是把结果表达出来( 例如采用信息的可视化方法) ，还要对信 息进行过滤处理。如果不能令决策者满意，需要重复以上数据挖掘的过程。 整个过程可以用下图2 2 表示： 图2 2 数据挖掘视为知识发现过程的一个基本步骤 f i g2 2d a t am i n i n gi sa b a s i cp r o c e s so f k n o w l e d g ed i s c o v e r y 2 1 4 数据挖掘的主要问题 数据挖掘的主要问题主要在以下几方面： 挖掘方法和用户交互问题：这反映所挖掘的知识类型、在多粒度上挖掘 知识的能力、领域知识的使用、特定的挖掘和知识显示。 性能问题：这包括数据挖掘算法的有效性、可伸缩性和并行处理。为了 有效地从数据库的大量数据中提取信息，数据挖掘算法必须是有效的和可伸缩 的。换句话说，对于大型数据库，数据挖掘算法的运行时间必须是可预计的和 可接受的。另一方面，许多数据库的大容量、数据的广泛分布和一些数据挖掘 算法的计算复杂性是促进开发并行和分布式数据挖掘算法的因素。这些算法将 数据划分成各部分，这些部分可以并行处理，然后合并每部分的结果。此外， 有些算法将数据挖掘过程的高花费导致了对增量数据挖掘算法的需求。增量算 法与数据库更新结合在一起，而不必重新挖掘全部数据，这种算法渐增的进行 知识更新，修正和加强先前业已发现的知识。 关于数据库类型的多样性问题：数据存储方式多种多样，这包括关系数 1 0 重庆大学硕士学位论文2 数据挖掘技术中的聚类分析 据库、数据仓库、事务数据库、高级数据库系统、空间数据库、文本数据库、 多媒体数据库、异种数据库和遗产数据库等多种数据库类型，在此基础上进行 数据挖掘系统的开发是重要的。由于数据类型的多样性和挖掘的目标不一样， 指望一个系统挖掘所有类型的数据是不现实的。为挖掘特定类型的数据，应当 构造特定的数据挖掘系统，这样，对于不同类型的数据，我们可能有不同的数 据挖掘系统。另一方面，从具有不同数据语义的结构化、半结构化的和非结构 化的不同数据源发现知识，对数据挖掘提出了巨大挑战。 以上问题是数据挖掘技术未来发展的主要需求和挑战。在近年来的数据挖 掘研究和发展中，一些挑战业已受到一定程度的关注，并考虑到了各种需求， 而一些仍处在研究阶段。然而，涉及这些问题将继续刺激进一步的研究和改进。 2 2 聚类的概念及形式描述 聚类是数据挖掘中的一种主要技术，是把一组个体按照相似性归成若干类 别，即“物以类聚”。它的主要目的是使的属于同一类别的个体之间的距离尽可 能的小，而不同类别上的个体间的距离尽可能的大。聚类和分类根本上的不同 是：分类问题中，我们知道训练例的分类属性，而在聚类中，就需要我们在训 练例中找到这个分类属性值。聚类方法包括统计方法、机器学习方法、神经网 络方法和面向数据库的方法。 在统计方法中，聚类称聚类分析，它是多元数据分析的三大方法之一( 其 它两种是回归分析和判别分析) 。它主要研究基于几何距离的聚类，如欧氏距离、 明考斯基距离等，传统的统计聚类分析方法包括系统聚类法、分解法、加入法、 动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。 在机器学习中聚类称作无监督或无教师归纳。因为和分类学习相比，分类 学习的例子或数据对象有类别标记，而要聚类的例子则没有标记，需要由聚类 学习算法来自动确定。机器学习领域中的概念聚类算法通过符号属性来进行聚 类，并得出聚类的概念描述。当聚类对象可以动态增加时，概念聚类则称是概 念形成。所以概念聚类由两部分组成； 发现合适的类； 形成对每个类的描述。 在神经网络中，有一类无监督学习方法：自组织神经网络方法，如k o h o n c n 自组织特征映射网络、竞争学习网络等等。神经网络中的s o m 方法通过反复 的学习来聚类数据，它由输入层和竞争层组成。输入层由n 个输入神经元组成， 竞争层由t n n = m 个输出神经元组成，且形成一个二维平面阵列。输入层各