（计算机软件与理论专业论文）动力学背景下的聚类算法研究.pdf

郑州大学硕士学位论文 攘要 摘要 随着的计算机技术、数据库技术和网络技术的迅速发展，我们己置身于一个 数据爆炸的时代我们迫切需要新的、强有力的数据分析方法和技术以解决“数 据丰富，但信息贫乏”的尴尬局面。 数据挖掘指从大型数据库或数据仓库中挖掘出隐含的、未知的、新颖的、极 有潜在应用价值的信息它融合了数据库、人工智能、机器学习、统计学、高性 能计算等众多领域的理论和技术的研究成果。聚类分析已经成为数据挖掘中的一 个非常活跃的研究方向。目前主要的聚类算法有基于划分的方法、基于层次的方 法、基于密度的方法、基于网格的方法和基于模型的方法，或是这些方法的组合 和改进。目前大部分聚类算法都是基于距离( 或密度) 的静态的聚类算法。 引入其它学科的背景知识为我们提出新的聚类方法和技术提供了新的思路。 在前人研究的基础上，我们把数据对象置入物理学的动力学背景中，把数据对象 抽象为物理粒子，将牛顿万有引力和牛顿运动定律的思想引入到聚类分析中，沿 着物理粒子之间相互作用的万有引力一粒子受力运动发生位移变化一粒子通 过学习不断修正自己的速度和位置这个研究主线对聚类算法进行了更进一步的研 究和探讨。 本文提出了基于层次的万有引力聚类算法( i - i g b c a ) 、基于网格的万有引力聚 类算法( g g b c a ) ，两算法反映了比较密集的数据对象拥有较高的聚类能力，这样 就修正了聚类标准仅和距离有关的不足；通过考察空间物理粒子受力运动引起位 移的变化，提出了基于运动的万有引力聚类算法( m g b c a ) ，把位移作为聚类的重 要标准，数据对象的聚类过程表现为物理粒子不断向聚类中心运动的过程。 最后介绍了运动的、会学习的、模糊的智能聚类算法一粒子群模糊聚类算 法【f p s o ) ，从而使聚类过程由孤立、静止的过程转化为相互联系的、运动的，通 过学习不断改进的智能聚类过程。通过性能分析和结果对比实验，证明以上算法 提高了执行速度和聚类效果，更真实的反映了事物的自然本质，提高了聚类质量。 关键字：数据挖掘，聚类分析，万有引力，网格聚类，粒子群聚类算法 郑州大学硕士学位论文 a b s t r a c t a b s t r a c t a l o n g 丽m t h ec o m p u t e rt e c h n o l o g y , t h ed a t a b a s et e c h n o l o g ya n dt h en e t w o r k t e c h n o l o g yr a p i dd e v e l o p m e n t , w eh a v eb e e np l a c e di n t oad a t a - e x p l o s i o nt i m e w e n e e ds o m en e wa n dp o w e r f u ld a t aa n a l y s i sm e t h o d sa n dt e c h n o l o g i e su r g e n t l yt o s o l v et h ee m b a r r a s s i n gs i t u a t i o no f d a t am c h & i n f o r m a t i o np o o r 1 1 d a t ai 龇a gm o f l n st of i n dt h eh i d d e n , u n k n o w n , n o v e li n f o r m a 6 0 n 诵l h a p p l i c a t i o nv a l u ef r o mt h el a r g e - s c a l ed a t a b a s e so rt h ed a t aw a r e h o u s e s i tr e l a t e d w i t ht h ed a t a b a s e , t h ea r t i f i c i a li n t a l l i g e n o o , t h em a c h i n el e a r n i n g , s t a t i s t i c s , t h e h i g h - p e r f o r m a n c ec o m p u t a t i o na n d8 0o nt h em u l t i t u d i n o u sd o m a i nt h e o r i e sa n dt h e t e c h n i c a lr e s e a r c hr e s u l t s c l u s t e r i n ga n a l y s i sa l r e a d yb c c a l n e 缸e 嘶e m e l ya c t i v e r e s e a r c h 撕i nt h ed a t am i n 岵m o s ti m p o r t a n tc l u s t e r i n ga l g o r i o a n sh a v eb e e n d i v i d e di n t op a t l i t i o n - b a s e dm e t h o d , h i e r a r c h y - b a s e dm e t h o d , d e n s i t y - b a s e dm e t h o d , g r i d - b a s e dm e t h o d , m o d e l - b a s e dm e t h o da n ds oo n , o rt h e s em e t h o d sc o m b i n a t i o n s a n di t si m p r o v e m e n ta tp r e s e n t t h e s ea l g o r i t h m sa t ea h n o s tb a s e do nt h ed i s t a n c e ( o r d e n s i t y ) b e t w e e nt h et w oo b j e c t st h a ti sas t a t i cc l u s t e r i n gs t a n d a r d i n t r o d u c i n gt h eb a c k g r o u n dk n o w l e d g eo f t h eo t h e rs u b j e c t s 删d eu ss o i n o n e wi d e a so nc l u s t e r i n gs t a n d a r d s b a s e do nt h ep r e d e c e s s o rr e s e a r c hr e s u l t s ，w e p l a c e dt h ed a t ao b j e c t si n t ot h ed y n a m i c sk n o w l e d g eo fp h y s i c sb a c k g r o u n d t h i s a r t i c l ea b s t r a c t st h ed a t ao b j e c t sa st h ep h y s i c a lp a r t i c l e st h o s ea t ea t t r a c t e db yo t h e r p a r t i c l e sa n dm o v i n ga b i d i n gb yt h en e w t o n sl a wo fg r a v i t a t i o na n dt h en e w t o n s l a wo fm o t i o n f o l l o w i n gt h er e s e a r c hc l u eo ft h ei n t e r a c t i o ng r a v i t yo ft h ep h y s i c a l p 枷d e 争专t h ec h a n g e so ft h ep a r t i c l e sd i s p l a c c m e n t - - - 哼r e v i s i n gt h es p e e da n d t h ep l a c et h r o u g hl e a r n i n gc o n s t a n t l y , w eg oo nw i t ht h ef u r t h e rr e s e a r c ha n d d i s c u s s i o no nt h ec l u s t e r i n ga l g o r i t h m s w ep r o p o s et w oc l u s t e r i n ga l g o r i t h m sh g b c a ( ac l u s t e r i n ga l g o r i t h mb a s e d 0 nt h eh i e r a r c h y & g r a v i t a t i o n ) a n dg g b c a ( a d n s t e r i n ga l g o r i t h mb a s e do nt h e 鲥d & g r a v i t a t i o n ) t h ed e n s eo b j e c t sh a v eah i g h e rp r i o r i t yo nc l u s t e r i n g , s ot h a ti tc a bg e t b e t t e re f f e c tt h a nt h eo n l yc l u s t e r i n gs t a n d a r do fd i s t a n c e - r e l a t e da l g o r i t h r a s t h r o u g h c o m p a r i n ga n di i l s p c c 恤坞o nt h ed i s p l a c e m e n tc h a n g i n go f p a r t i c l e si np h y s i c a ls p a c e , i i 郑州大学硕士学位论文 w ep r o p o s em g b c a ( ac l u s t e r i n ga l g o r i t h mb a s e do nt h em o t i o n & g r a v i t a t i o n ) r e g a r dd i s p l a c e m e n ta sa ni m p o r t a n tc l u s t e r i n gs t a n d a r d , d a t ao b j e c t sc l u s t e r i n g p r o c e s sa c t sa st h ep a r t i c l e sm o v i n gt ot h ec l u s t e rc e n t e r s f i n a l l yw ei n t r o d u c e da c l u s t e r i n ga l g o r i t h mw h i c hc a ns t u d y , m o v i n gw i t hf u z z yi n t e u i g e n c e - l 叩s o | f u z z yp a r t i c l es v a n n so p t m f i z a t i o n ) t h ep r o p o s a lc l u s t e r i n ga l g o r i t h m si m p r o v et h e c l u s t e r i n ge f f e c tb e t t e rt h a nt h o s ea l g o r i t h m sw h o s ec l u s t e r i n gs t a n d a r dj u s tr e l a t e d w i t hd i s t a n c e , t h u sl e a dt o t h ei s o l a t e , s t a t i cg a t h e r p r o c e s sb e f o r e t h en e w a l g o r i t h m s 缸粗s f 嘞mt h eg a t h e rp r o c e s si n t oar e l a t e d , m o v i n ga n di n t e l l i g e n c e p r o c e s st h a ti m p r o v e dt h r o u g ht h es t u d yu n c e s s i n g l y t h ep e r f o r m a n c ea n a l y s i sa n d t h er e s u l t so fc o n u a s te x p o r i m e n ts h o w e dt h a tt h en e wa l g o r i t h m sh a v ee n h a n c e d c l u s t e r i n ge f f e c ta n dt h es p e e do f c a r y i n go u t t h er e s u l t sr e f l e c tt h en a t u r a lr e l a t i o n e s s e n c eo f d a l ao b j e c t s ，i m p r o v et h ec l u s t e r i n gq u a l i t y k e yw o r d s ：d a t am i n i n g , c l u s t e r i n g , g r a v i t a t i o n ，g b c a , p s o i i l 郑州大学硕士学位论文 第一章绪论 第一章绪论 1 1 数据挖掘的研究现状 我们正处于一个数据爆炸的现代社会，随着计算机技术、数据库技术的迅速 发展和i n t e m c t 的广泛普及，人们所需要处理的数据急剧地膨胀：商业、工业、 科研机构和政府部门都积累了大量的以不同形式存储的数据资料面对浩如烟海 的数据，人们茫然不知所措，人们迫切需要新的强有力的数据分析方法和技术以 解决“数据丰富，但信息贫乏( d a t ar i c h i n f o r m a t i o np o o r ) ”的尴尬局面。 随着计算机软硬件技术的迅猛发展，人们渴望根据现有的数据来预测未来的 发展趋势以辅助决策的智能化、自动化数据挖掘( d a t am i n i a g ) 技术应运而生并 显示出了它的强大威力。它帮助人们从繁杂的数据中挖掘出有用的信息、规则、 模式，成为指导人们更好实践的知识，给人们带来了巨大的信息价值。 数据挖掘，又称知识发现( k n o w l o d g ed i s c o v e r y i nd a t a b a s o ，k d d ) ，是指从 大型数据库或数据仓库中提取隐含的、未知的、新颖的、极有潜在应用价值的信 息或模式。它融合了数据库、人工智能、机器学习、统计学、高性能计算等多个 领域的理论和技术，是极有发展前途的一个研究领埘“ 面对海量的数据，首要的任务是将它们合理的归类。对同一类中的数据对象 可以采取相同的策略和措旋，这对我们认识世界，提高工作效率有重要作用。为 此聚类分析已经成为数据挖掘中的一个非常活跃的研究方向，在数据挖掘、统计 学、市场营销、社会统计、地震分析、城市规划、机器学习、生物学、空间数据 库等方面有广泛应用。聚类就是根据某种相似性标准将数据对象分成类或簇，使 每个类内的数据对象尽可能相似，不同聚类内的数据对象之间的差异尽可能大。 相似性和差异性可以用不同定义的相似度和相异度来衡量。 聚类就是寻找隐藏在数据集中的不同的数据模型，是一个对聚类结果无任何 先验知识的无监督的学习过程，能够实现数据空间的盲分类。相似度可以从距离、 密度、概率、网格等方面加以考察。空间距离可以直观地反映簇的形状、大小和 位置，它把空间距离相近的各个数据对象划分到同一个聚类中，比较适合处理数 值属性的数据；基于密度的聚类算法则比较适合于图形图像处理；基于连通度的 郑州大学硕士学位论文 第一章绪论 聚类算法适合于类似图或树的结构类型的数据；基于网格聚类算法比较适合于空 间坐标系中的数据点以及多维多属性的数据 2 1 。 常见的聚类方法主要有以下几类：基于划分的方法、基于层次的方法、基于 密度的方法、基于网格的方法和基于模型的方法。典型的基于划分的方法主要包 括：k - 平均法( k - m e a n s ) 、k - 中心点法( k - m e d i a ) 、c l a r a n s ；基于层次的方法 主要包括：凝聚的层次聚类方法、分裂的层次聚类方法；基于密度的方法主要包 括：d b s c a n 。o p t i c s 、d e n c l u e ；基于网格的方法主要包括：s t i n g ，w a v e c l u s t e r ，c l i q u e ；基于模型的方法主要包括：c o b w e b 、神经网络算法等p 】 目前大多数聚类算法都是以上五种基本算法的改进和组合。 1 2 本文的研究内容 以往大部分的聚类算法都是把各种数据对象抽象成多维空间中的数据点，空 间中数据点的每一维都表示数据对象的个属性分量，数据的属性都被量化为数 值型变量。目前大部分聚类算法都是从数据对象的空闯位置关系来考虑划分的， 由于数据点的距离坐标能直观地反映数据对象的位置、大小、稠密和形状等重要 信息，所以现有的绝大多数算法都直接或间接地采用距离作为聚类的标准，对距 离也有不同的定义形式。空间距离接近的数据对象有较大的相似度，应聚为一类。 空间距离较远的数据对象在位置、大小、稠密、形状上可能有较大差异，一般应 划分为不同的类。 聚类增强了人们对客观现实的认识，是概念描述和偏差分析的先决条件。 m c h a l s k i 提出了概念聚类技术的要点。在划分对象时不仅考虑对象之间的距离， 还要求划分出的类具有某种内涵描述，从而避免传统聚类算法的某些片面性” 4 1 。 引入其它学科的背景知识为我们提出新的聚类算法提供了丰富的研究空间，各种 各样的聚类算法层出不穷：如人工智能聚类 5 1 、神经网络聚类 o q 、蚁群聚类 7 1 、 遗传聚类嘲、免疫聚类 9 1 、粒子群聚判1 0 1 、等密度线聚判1 1 1 、退火技术聚类【1 2 1 、 内聚力聚类1 3 1 、模糊聚类【1 4 】【堋、数据场聚类1 0 3 1 7 l 等等。 我们把数据对象置入物理学背景中，引入物理学科中的动力学背景知识对数 据挖掘聚类算法进行了更深一步的研究和探讨，沿着物理粒子之间相互作用的万 有引力粒子受力运动发生位移变化_ 粒子通过学习不断修正速度和位置 2 郑州大学硕士学位论文第一章绪论 这个主线展开研究，希望对大家的研究学习有一定的启发。 牛顿第一定律认为：任何两个物体之间都存在相互吸引的万有引力，力的大 小和物体的质量成正比，和物体之间的距离成反比。我们把万有引力的思想引入 到聚类分析中，把数据对象抽象为物理粒子，提出了基于层次的万有引力聚类算 法( i - i o b c a ) ，为了提高聚类效率提出了基于网格的万有引力的聚类算法( g g b c a ) 使得聚类算法标准不再仅仅和数据对象之间的距离有关，而且和数据对象的质量 ( 爪数) 有关，体现了数据对象越多，质量越大，引力也就越大，质量比较大的数 据对象拥有较大的凝聚聚类能力( 这在社会学中常称为强者恒强的“羊群效应”， 能够很好地模拟股民买卖股票的交易行为) ，这样就修正了聚类的标准仅和距离 有关的不足 牛顿运动定律认为：物体受到外力的作用会产生加速度，进而引起速度和位 移的改变，为此本文在前人研究的基础提出基于运动的万有引力聚类算法 ( m o b c a ) ，把位移作为聚类的重要标准，数据对象的聚类过程表现为数据点不 断向聚类中心运动的过程。该算法在处理低维空间数值属性的数据集时效果明 显。在处理5 维以上的聚类问题时，效率下降，结果不是十分理想。为了解决多 维和运算复杂等问题最后介绍了模糊的、运动的、会学习的智能聚类算法睫 子群模糊聚类算法( f p s o ) ，从而使孤立、静止的聚类过程转化为相互影响的、运 动的、通过学习不断改进的智能聚类过程，这对我们预澳4 股票价格走势有很好的 启示作用。通过性能分析和结果对比分析，实验证明以上改进算法在一定程度上 提高了执行速度和聚类效果，更真实的反映了事物的自然本质，提高了聚类质量。 1 3 本文的结构 本文分七章，第一章绪论，分别介绍了数据挖掘和聚类分析的研究现状、本 文研究的主要内容和本文的结构安排；第二章详细介绍数据挖掘的用到的数据类 型、距离定义和数据挖掘的处理过程；第三章聚类分析主要介绍了以后章节要用 到的类间距离定义、聚类的应用领域、主要的聚类方法和改进方向；第四章提出 了基于层次的万有引力聚类算法( h g b c a ) 及其改进算法基于网格的万有引力的 聚类算法( g g b c a ) ，提出了将万有引力作为聚类标准的思想，并结合网格聚类 思想提高了执行效率，最后给出了算法的形式化描述和聚类试验对比结果；第五 郑州大学硕士学位论文 第一章绪论 章基于运动的万有引力的聚类算法( m g b c a ) ，把数据对象置入物理学科的动力 学背景中，把数据对象抽象为物理粒子，将牛顿运动定律的思想引入到聚类分析 中，刻画了物理粒子在其它粒子万有引力的作用下向核心粒子运动，一旦运动到 核心粒子的阈值内则聚为一类的动态聚类思想；第六章阐述了粒子群聚类算法 口s o ) 和模糊聚类算法( f c m ) 以及它们的组合粒子群模糊聚类算法( f p s o ) ，将 p s o 的收敛速度快，f c m 局部寻优效果好的优点有机结合，使聚类过程转化为 快速的、准确的、运动的、通过学习不断改进的智能聚类过程；第七章对全文做 出总结，指出了以后的努力方向和尚需完善的地方，对本文的不足提出了改进意 见，并对以后的研究方向迸行了展望。 4 郑州大学硕士学位论文第二章数据挖掘概述 第二章数据挖掘概述 2 1 数据挖掘产生的背景 2 1 1 数据膨胀的时代 我们正处于一个数据爆炸的时代，大量数据扑面而来：北京青年报目前 是1 6 4 0 版；市场营销报也由6 0 年代的1 0 2 0 版扩张至现在的1 0 0 - 一2 0 0 版，纽约时报最高曾达1 5 7 2 版，按人均日阅读时间通常为3 0 分钟，一天浏 览一份2 4 版的报纸来计算，我们读完这份报纸需要6 3 天t 1 8 11 纽约时报的新 闻已经早过时了，那时纽约时报也该改名叫纽约“晚”报了! 这只是数 据膨胀的一个缩影。 随着计算机和通信技术的迅速发展，大型数据库系统得到广泛应用，各行 各业产生和收集数据的能力已经迅速提高，看见看不见的数据已把我们层层包 围据有关资料统计，数据量以每月1 5 、每年5 3 倍的幅度增加。随着计算机 技术和i n t e r n e t 的迅猛发展，人们已被数据的海洋淹没，面对给人们带来价值的 大量数据，人们不得不考虑以下几个闯题： 数据过量，难以消化和保存； 数据真假难以辨识； 数据安全难以保证； 数据形式不一致，难以统一处理。 数据库技术对数据的保存和处理起了基础性的重要作用。 2 1 2 数据库的发展历程 人们对数据的占有欲是无止境的，特别是计算机存储技术和网络技术的发展 大大拓宽了人们收集数据的范围和容量。数据库是目前组织和存储数据最有效方 法之一，它是数据挖掘的准备和基础，让我们简单回顾一下数据库的发展历程。 6 0 年代，为了适应信息的电子化要求，信息技术从简单的文件处理系统向有 郑州大学硕士学位论文第二章数据挖掘概述 效的数据库系统发展。7 0 年代，数据库系统的三个主要模式一层次、网络和 关系型数据库的研究和开发取得了重要进展。8 0 年代，关系型数据库及其相关 的数据模型工具、数据索引及数据组织技术被广泛采用，并且成为整个数据库市 场的主导。8 0 年代中期开始，关系数据库技术和新兴技术的结合成为数据库研 究和开发的重要标志。进入9 0 年代，分布式数据库在理论上趋于成熟，分布式 数据库技术得到了广泛应用。 从数据模型上看，诸如扩展关系、面向对象、对象关系( o b j e c t - r e l a t i o n ) 及 演绎模型等被应用到数据库系统中从应用的数据类型上看，包括空间、时态、 多媒体以及w e b 等新型数据成为数据库应用的重要数据源事务数据库 ( t r a n s a c t i o nd a t a b a s e ) 、主动数据库( a c t i v ed a t a b a s e ) 、知识库( k n o w l e d g eb a s e ) 、 办公信息库0 n f o r m a t i o ab a s e ) 等技术也得到蓬勃发展。分布式数据库( d i s t r i b u t e d d a t a b a s e ) 晦j 透明性、并发控制、并行处理等方面迅速发展。目前，由于各种新兴 技术与数据库技术的有机结合，使数据库领域中的新内容、新应用、新技术层出 不穷，形成了庞大的数据库家族，为数据挖掘技术的产生准备了条件 2 1 3 数据挖掘技术的产生 传统的数据分析方法和技术只适用于对小规模数据库作一些简单的分析，面 对快速增长的海量数据和比较复杂的高层分析任务，过去所采用的数据分析方法 已显得无能为力，人工去整理、处理和理解如此大量的数据源已经存在效率和准 确性等问题。在这些海量的数据中，往往蕴含有丰富的、对人类活动有指导意义 的知识，而现有的数据库系统只能进行数据录入、查询、统计等事务性的处理过 程，总而言之目前数据库的应用都是以实时查询处理技术为基础的，查询只是数 据库内容的选择性输出，是对数据库的被动使用。因此它距人们所期望的智能分 析预测、决策支持自动化等高级应用仍有很大距离。 如何发现这些数据内部隐含的规则和规律? 如何及时地从庞大数据中挖掘 有用的知识、提高数据利用率? 新的需求推动新的技术的诞生，面对这一挑战， 站在成熟的数据库技术这个巨人肩膀上的数据挖掘技术( d a t am i n i n g ) 走上了历 史的舞台，担负起改变“数据丰富而信息贫乏( d a t a 黜c h & i n f o r m a t i o np o o r ) ”的 历史重任。 6 郑州大学硕士学位论文 第二章数据挖掘概述 g a r m e r g r o u p 将数据挖掘列为“未来三到五年内将对工业产生深远影响的五 大关键技术”之首，并且还将并行处理体系和数据挖掘列为未来五年内投资焦点 的十大新兴技术的前两位。最近g a l l i l e r 的h p c 研究表明：“随着数据捕获、传 输和存储技术的快速发展，大型系统用户将更多地需要采用新技术来挖掘市场以 外的价值，采用更为广阔的并行处理系统来创建新的商业增长点。” 2 2 数据挖掘技术 2 2 1 数据挖掘技术的概念 数据挖掘( d a t a m i n i n g ) 是一个多学科交叉的研究领域，它融合了数据库 ( d a t a b a s e ) 技术、人工智能( a r t i f i c i a li n t e l l i g e n c e ) 、机器学习( m a c h i n el e a r n i n g ) 、 知识工程( k n o w l e d g ee n g i n e e r i n g ) 、面向对象方法( o b j e c t - o r i e n t e dm e t h o d ) 、统计 学( s t a t i s t i c s ) 、信息检索0 n f o r m a t i o nr e t r i e v a l ) 、高性能计算( h i g h - p e r f o r m a n c e c o m p u t i n g ) 以及数据可视化( d a t av 娅u d i z a f i o n ) 等最新技术的研究成果。被信息产 业界认为是数据库系统最重要的前沿阵地之一，是信息产业最有前途的交叉学 科。 数据挖掘既然这么重要，那么到底什么是数据挖掘? 数据挖掘又称知识发现 k d d ( i c n o w l e d g ed i s c o v e r y i nd a t a b a s e s ) ，1 9 8 9 年8 月在美国底特律举行的第十 一届国际联合人工智能学术会议上，首次出现k d d 这个术语；随后在1 9 9 1 年、 1 9 9 3 年和1 9 9 4 年都举行过k d d 专题讨论会，汇集来自各个领域的研究人员和 应用开发者，集中讨论数据统计、海量数据分析算法、知识表示、知识运用等问 题随着参与人员的不断增多，k d d 国际会议逐渐发展成为年会。由于各个研 究领域的研究者的观点和背景不同，对数据挖掘的定义至今仍未统一，比较代表 性的有如下定义【1 9 1 ： 数据挖掘是一个确定数据中有效的，新的，可能有用的并且最终能被理解的 模式的重要过程。年a y y a d 数据挖掘是一个从大型数据库中提取以前未知的，可理解的，可执行的信息 并用它来进行关键的商业决策的过程。z e k l l l i l l 数据挖掘是用在知识发现过程中，来辨识存在于数据中的未知关系和模式的 7 郑州大学硕士学位论文第二章数据挖掘概述 一些方法。_ f 1 l z 掇 数据挖掘是发现数据中有益模式的过程。- j o m 数据挖掘是我们为那些未知的信息模式而研究大型数据集的一个决策支持 过程。p a r s a y e 被广泛接受的定义是：数据挖掘( d a t am i n i n g ) 是指从存放在数据库、数据仓 库或其他信息库中的大量数据中提取隐含的、未知的、新颖的、有效的、有潜在 应用价值的知识或模式的过程。 数据是指有关事实的集合，记录和事物有关的原始信息。模式是一个用语言 来表示的一个表达式，它可用来描述数据集的某个子集。知识，是对数据包涵的 信息更抽象的描述对大量数据进行提取分析的过程，包括数据准备、模式搜索、 知识评价以及反复的修改求精。该过程要求是非平凡的，意思是要有一定程度的 智能性、自动性；有效的是指发现的模式对于新的数据仍保持有一定的可信度； 新颖的要求发现的模式应该是新的；潜在有用性是指发现的知识将来有实际效 用，如用于决策支持系统里可提高经济效益；最终可理解性要求发现的模式能被 用户理解。 2 2 2 数据挖掘的主要功能 数据挖掘是从大量数据中发现有趣的模式，不同的用户对模式有不同的要 求。数据挖掘任务主要可分为对数据的描述和预测，描述是为了刻画数据集中的 数据的一般特性，预测任务是在当前数据上进行推断，以对未来发展趋势进行预 测。 数据挖掘的主要功能可概括如下：概念描述和可视化( d e s c r i p t i o na m v i s u a l i z a t i o n ) 、相关性分组，关联分析( a f f i n i t yg r o u p i n go ra s s o c i a t i o nr u l 神、分类 预测( c l a s s i f i c a t i o np r e d i c t i o n ) 、聚类分析( c l u s t e r i n ga i l a l y s i s ) 、孤立点分析( o u t l i e r a n a l y s i s ) 、估值演变分析( e s t i m a t i o na n a l y s i s ) t 2 0 。 1 、概念描述和可视化 数据库中通常存放大量的细节数据。然而，用户通常希望以简洁的描述形式 观察汇总的数据集，即对数据进行归约、概化或图形描述等。这种数据描述可以 提供一类数据的概貌，或将它与对比类相区别，如可将无穷的实数描述为正数、 郑州大学硕士学位论文 第二章数据挖掘概述 负数和零。此外，用户希望方便、灵活地以不同的粒度和从不同的角度描述数据 集。对目标数据的一般特征进行汇总。这种描述性数据挖掘称为概念描述，可以 以饼图、条图、曲线、多维立方体等多种形式输出结果。 2 、相关性分组关联分析 关联分析就是从大量数据中发现目标对象之间有趣的关联或相关联系。随着 大量数据不停地收集和存储，许多业界人士对于从他们的数据库中挖掘关联规则 越来越感兴趣。广泛用于购物篮分析和事物数据分析，为商务决策的制定提供依 据【2 1 】吲 3 、分类和预测 分类和预测是两种数据分析形式，主要用于提取描述重要数据类的模型或预 测数据未来的趋势，主要用到判定树方法和神经网络方法如可以建立一个分类 模型，对参加保险的客户进行分类，以降低骗保的风险；也可以通过建立分类模 型，对客户群进行分类，采取有针对性的一对一营销模式，降低广告投入的盲目 性嘲。 4 、聚类分析 根据最大化类内相似性、最小化类间相似性的原则进行聚类，使得在同一个 类中的对象具高度的相似性，而与其它类中的对象有很大的相异性。聚类形成的 每个类可以看作一个对象类，由它可以导出聚类规则，实现样本空间的盲分类【2 4 】。 聚类也便于将观察到的内容组织成分层结构，把类似的事件组织在一起。 5 、孤立点分析 数据库中可能包含一些特殊的数据对象，它们与数据的一般行为或模式不一 致。这些数据对象就是孤立点( o u t l i e r ) 。许多数据挖掘算法视孤立点为噪声或异 常而将其抛弃，以减少它们对挖掘结果的影响。但在一些应用中孤立点本身却包 含着非常重要的信息。在许多商业领域中，孤立点事件具有显著的商业价值，如 客户流失、银行的信用卡欺诈、电信中移动话费拖欠以及医学中特殊病情的征兆 等。通过数据挖掘中的孤立点分析可以迅速准确地甄别这些异常事件，减少损失 瞄】。 6 、估值演变分析 数据演变分析描述行为随时间变化的规律和趋势，并对其建模。包括时问序 列数据分析、序列周期模式匹配和基于类似性的数据分析。如可以从股票交易 9 郑州大学硕士学位论文 第二章数据挖掘概述 数据中挖掘出整个股票市场和特定公司的股票演变规律，以帮助预测股票价格的 未来走向，为股票投资者提供决策依据唧【2 町。 2 2 3 数据挖掘的应用领域 数据挖掘技术从一开始就是面向商业应用的，数据挖掘成功解决了如下典型 的商业问题： 数据库营销a t a b u em 破e t i n o 客户群体划分( c u s t o m 订s e g m 删o n c l 勰s i 丘c a 抽n ) 背景分析口r o m ea n a l y s 动 交叉销售( c r o 眦g ) 客户流失性分析( c h 啪a n a l y s i s ) 客户信用记分( c r e d i ts c o m o 欺诈发现舢dd 曲e c i i o n ) 等等。 目前数据挖掘已经突破商业领域，在证券、银行、电信、保险、交通、零售 等领域，甚至在n b a 比赛的赛场上，数据挖掘都成为战胜对手的秘密武器。所 以说数据挖掘的应用领域非常广泛，在不同的应用领域，数据挖掘具有不同的研 究方向和挖掘功能，人们往往开发出相应的功能模型系统嵌入到相应的应用系统 中： 在证券系统中嵌入神经网络预测功能 在欺诈检测系统中嵌入欺诈行为的识别模型 在客户关系管理系统中嵌入客户群分类功能或客户行为分析功能 在机器维护系统中嵌入监测或识别难以定性的设备故障功能 在数据库营销中嵌入选择最可能购买产品的客户功能 在机场管理系统中嵌入旅客人数预测、货运优化功能 在基因分析系统中嵌入d n a 识别功能 在制造生产系统中嵌入质量控制功能等 数据挖掘技术的实际应用领域十分丰富，比较常见的有：客户细分、客户保 留、目标营销、客户拓展、欺诈检测、购物篮分析、信用打分、信用风险评估、 投资组合管理、行情分析、安全管理、客户盈利能力分析、资源管理、利润分析、 1 0 郑州大学硕士学位论文 第二章数据挖掘概述 交叉销售、增量销售、客户服务自动化活动分析、销售预测、收入预测、需求预 测、理赔分析、业绩分析、商店选址、库存控制、流程质量控制、故障分析、处 方分析等等嘲 2 3 数据挖掘的处理对象 2 3 1 数据挖掘的过程模型 数据挖掘技术是一种新的信息处理技术，其主要特点是对数据库中的大量业 务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助决策的关键性数 据k d n u g g e s t s ( w w w k d n u g g e t s c o m s o a ) 集中介绍的几百个流行的数据挖掘系 统，目前市面上也设计和实现了很多数据挖掘系统。比较著名的有： i b m ：“h 嘲l i 鲫tm i n e r ( 智能矿工) ” t a n d e m ：“r e l a t i o n a ld a t am i n 喇关系数据矿工) ” a n g o s ss o r w a r e ：“k n o w l e d g es e e d e r ( 知识搜索者) ” t h i n k i n gm a c h i n e sc o q ) o r a f i o n ：“d a r w i n t m ” n c o v m t as o f t w a r e ：“a s i c ” i s ld e c i s i o ns y s t e m si n o , ：“c l e m e n f i n e ( 克莱f - d 、柑橘) ” d a t a m i n dc o r p o r a t i o n ：“d a t am i n dd a t ac r t m c h e r ” s i l i c o ng r a p h i c s ：“m i n es e t ” c a l i f o m i as c i e n t i f i cs o r w a r e ：“b r a i nm a k e r ” w i z s o f lc o r p o r a t i o n ：“w i zw h y ” l o c k h e e d c o r p o r a t i o n ，“r e c o n ” s a sc o r p o r a t i o n ：“s a se n t e r p d s em i l l e r ” 上海复旦大学的朱建秋教授将数据挖掘模型划分为两种类型，一种是 f a y y d 过程模型，一种是c r i p d m 过程模型。绝大多数实用的数据挖掘系统都 是基于f a y y d 过程模型，该过程可分为：问题定义、数据抽取、数据预处理、数 据挖掘、结果的表现和解释以及5 个阶段的循环迭代过程划。 郑州大学硕士学位论文 第二章数据挖掘概述 2 3 2 数据预处理 圈2 - 1f a y y d 数据挖掘过程 不完整的、含噪声的、不一致的数据是现实世界大型数据库的共同特点。数 据预处理的质量直接关系到后期挖掘的真实性和准确性。数据的预处理包括数据 清洗、数据集成、数据变换和数据归约四个步骤。 数据清洗通常是指通过填写空缺值，平滑噪声数据，识别删除孤立点来 “清洗”数据： 数据集成是将多个数据源中的数据结合起来存放在一个数据存储中，注 意避免属性的冗余和重复； 数据变换是通过平滑、聚集、概化、规范化处理，将数据转换成适合挖 掘的形式； 数据归约是将数据原始值用区间或较高层次的概念替换，删除不相关的 属性，这样可以在接近保持原数据完整性的基础上，简化对数据的操作， 并产生近似相同的分析结果【1 1 2 3 3 处理对象的数据结构 我们经常要用到以下两种数据结构：数据矩阵( d a t am a t r i x ) 和相异度矩阵 ( d i s s i m i l a r i t y m a t r i x ) 。将数据对象用矩阵表示，计算机可以方便处理。 郑州大学硕士学位论文 第二章数据挖掘概述 1 、数据矩阵：假设有n 个需要处理的数据对象，每个对象有p 个属性，如 有n 个同学，每个同学用年龄、性别、身高、民族等p 个属性来刻划其特征，则 我们就可以用一个n p 的矩阵来表示数据对象： x l lx l f z i p 工i l x t f x 驴 x n 1 x 唾x 哪 2 、相异度矩阵：存储n 个对象之间的相异程度，我们就可以用一个n x n 的 矩阵来表示。由于自己和自己相同所以d ( i ，i ) = 司，对象i 和对象j 越相似j ) 越接 近于0 ，对象i 和对象j 差异越大d ( i j ) 的值也就越大： 常用的相异性度量有：距离、向量夹角、匹配比率等。 2 3 4 变量的类型及相异度的计算 由于变量的测量单位不同，聚类的结果也不同，所以必须注意数据的标准化 问题，我们经常遇到的变量主要有如下几种类型，可以通过如下相应公式计算相 异度d ( i j ) ，使它的值映射在【o ，l 】区问，使原来的有单位的度量值转化为无单位 的值，并保持相对的大小关系： l 、间隔变量( i n t e r v a ls c a l e d v a r i a b l e ) ：常用的标准化方法是计算平均绝对偏 差s f 和计算标准化的度量值z _ s e 。o r e ， 1 m f = 2 - ( x l f + x 2 f - i - + x n f ) s f ：1 ( ix l f m f i + 1x 2 f m f i + l x n f m f l ) 咒 on vo ：赠 乃 d o 3 ；2 o 7 1 i i n v n v do珊瑚；撕 郑州大学硕士学位论文 第二章数据挖掘概述 z 矿= 2