（计算机应用技术专业论文）数据挖掘聚类算法研究.pdf

两南交通大学硕士研究生学位论文第l 页 摘要 近年来。数据挖掘获得了快速发展，这是快速增长的数据薰和日髓 贫乏茨信息量之闽矛鼹运动熬必然结果。国穴之流麴网站评比的未来卡 大热门技术中，数据挖掘占了一席，而胜现今世界几大超级公司也早翠 魏投入数据挖掘熬磅突，这篡孛氢括i b m 、m i c r o s o f t 等。数据挖掘技零 集数理理论、专家系统、人工智能、神经网络、图形图象设计等多门举 载予奏，其发袋速度必穗大大影酾垒球信惑铯懿进程，对其进行系绞、 深入、全面、详尽地研究是信息化发展的客观需要。本文对数搦挖掘技 术，茏萁蹩聚类分褥避行了较为系统途分析帮研究，提崮了一黧改进麓 算法，主要包括以下一些内容： 数据携攘技术静穰述。辩数攒挖据技术静产生滋行了简要的匿顽， 对数据挖掘的发现模式和常使用的技术进行了详细地分类、归纳和总结。 对数据挖掘技术的应用进行了归纳，为本文酌全面鼹歼奠滗了基础。 聚类分析的概述。聚类分析是数据挖掘的一个熬要的研究方向，是 一种无监督学习的方式，在许多方面发挥着重要的作用。对聚类分析的 定义、傻嬲的数据类裂和主溪的算法等进行了籀要的介缨。 蚁群算法的概述。群体错能是模仿自然界昆虫行为的一个研究领域。 弱榉也在诲多镀域取褥了较为突邀弱成绫，嚣虽有了一定懿发鼹。蚁旗 算法是群体智能的一个典型代表算法，简且_ 暾用面比较广。对纂于蚂蚁 寻鼹纛玛蚊聚类数葵漩劳别进行了篙要奔绍。 基于阙值的t - v a l u e 算法及蚁群聚类组合算法的研究。在研究了基本 数群算法瓣基磁上，缝合鹅蔽寻鼹释爨食静习性帮聚类懿悉怒，提基 些想法和改进。首先搬蚂蚁觅食原理结合k m e a n s 提出了种纂于信息 素的k m e a n s 改进算法；穰据密发聚类的愚戆，撬波一种蒸予瓣值鹩算 法一t - v a l u e 算法，同时引入邻域到t - v a l u e 中，结合基于信息素的 k n l c a l l s 算法提滋了一种t - v a l u e 聚类缀合算法；结合l f 算法秘基予信 息繁的k m e a n s 算法，提出禺一种聚类组合算法蚁群聚类组合算法。最 后对各种算法避行数据测试和性能分析，并撼蚁群浆类组合算法用于移 动客户的消费行必分掇。 关键谴；数据掩提；聚类分横；戳镕餐链；蚁器算法 西南交通大学硕士研究生学位论文第1 l 页 a b s t r a c t i nr e c e n ty e a r s ，m a n yp e o p l ei ni n f o r m a t i o ni n d u s t r ya t t a c hm o r ei m p o r t a n tt o t h ed a t am i n i n gt e c h n i q u et h a tg a i n e dr a p i dp r o g r e s s ，w h i c hi s a t t r i b u t e dt ot h e n e c e s s a r yc o n s e q u e n c eo ft h ec o n f l i c t i n gm o v e m e n tb e t w e e nt h er a p i di n c r e a s i n g d a t aa n dt h ep o o ri n f o r m a t i o nd a yb yd a y i ns o m ed o m e s t i cp r i m a r yw e b s i t e ，d a t a m i n i n gt e c h n i q u ew a s c h o s e no n eo ft h em o s tp o p u l a rt e c h n o l o g i e si nt h ef u t u r e i n t h i sd a y s ，s o m es u p e rc o m p a n i e ss u c ha si b m ，m i c r o s o f th a v ea t t e n d e dt h er e s e a r c h o fd a t am i n i n gt e c h n i q u e t h i sd i s s e r t a t i o ns y s t e m a t i c a l l y , d e 印l y , r o u n d l ya n d d e t a i l e d l ys t u d i e s a n da n a l y s e st h ed a t am i n i n gt e c h n i q u e ，e s p e c i a l l yt h eo n ef o r c l u s t e r i n ga n a l y s i s t h em a i n c o n t e n t sa r el i s t e da sf o l l o w s ： d e s c r i p t i o ni nb r i e f o ft h ed a t am i n i n gt e c h n i q u e t h ea p p e a r a n c eo ft h ed a t a m i n i n gt e c h n i q u ei s r e v i e w e di nb r i e ff i r s t b a s e do nt h eb a s i cc o n c e p t so fd a t a m i n i n g , t h i sd i s s e r t a t i o nc l a s s i f i e sa n ds u m m a r i z e st h eo b j e c t so fd a t am i n i n g ，t h e f i n d a b l e p a t t e r n s a n dt h ec o m m o n t e c h n i q u e s i nd e t a i l i n s u c c e s s i o n ，t h e d i s s e r t a t i o ns u m m a r i z e s ，a n a l y s e sa n ds t u d i e st h ec u r r e n ts t a t u so ft h ed a t am i n i n g t e c h n i q u e i no u rn a t i v e c o u n t r y a n do v e r s e a s w i d e l y a n d r o u n d l y a n dt h e n s u m m a r i z e sa n dd i s c u s s e si t sd e v e l o p m e n t a lt r e n d sa n dh o tr e s e a r c hf i e l d s a l lo f t h ea b o v eb e c o m et h eb a s i sf o rt h i sd i s s e r t a t i o n d e s c r i p t i o n i nb r i e fo f c l u s t e r i n ga n a l y s i s a so n eo f t h em o s t i m p o r t a n td o m a i n o 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 si san o n - s u p e r v i s e dl e a r n i n gm e t h o d ，e x e r t e d i m p o r t a n te f f e c ti nm a n ya s p e c t s t h ed e f i n i t i o n ，d a t at y p ea n dp r i m a r ya l g o r i t h m s a r e b r i e f l yi n t r o d u c e d d e s c r i p t i o ni nb r i e fo fa n tc o l o n ya l g o r i t h m s w a r mi n t e l l i g e n c ei s ar e s e a r c h d o m a i nw h i c hp r o v i d e db ys i m u l a t i n gi n s e c t s b e h a v i o r a n tc o l o n ya l g o r i t h mi sa t y p i c a lr e p r e s e n t a t i v ea l g o r i t h mo fs w a r mi n t e l l i g e n c ea n d h a sb e e nw i d e l ya p p l i e d t w ot y p e so fa l g o r i t h ma r eb f i e f ys u m m a r i z e d o n ei sa n tr o u t i n ga l g o r i t h m ， a n o t h e ri sa n tc l u s t e r i n g a l g o r i t h m r e s e a r c ho ft - v a l u ea l g o r i t h mb a s e do nt h r e s h o l da n dc l u s t e r i n g a l g o r i t h m c o m b i n a t i o n f i r s t l y , a na l g o r i t h mo fk m e a n sb a s e do np h e r o m o n ei sp r e s e n t e d t h e nt - v a l u ea l g o r i t h me n l i g h t e n e db yd b s c a na l g o r i t h mi s p r e s e n t e da n da t h r e s h h o do f i sa d d e di n t ot - v a l u et oi m p r o v et h ee f f e c to ft h i sa l g o r i t h m t h e na c o m b i n a t i o na l g o r i t h mo ft - v a l u ea n dk m e a n sa l g o r i t h mb a s e do np h e r o m o n ei s 鞭南交通大拳磺士研突宝攀位论文繁l 1 l 页 p r e s e n t e d ac o m b i n a t i o na l g o r i t h m o f i m p r o v e d l fa l g o r i t h m sa n dk - m e a n s a l g o r i t h mb a s e do np h e r o m o n ei s i n t r o d u c e dd e t a i l e d l y , a n di st e s t e db ys o m e d a t a s e t s a tl a s t ，t h i sc o m b i n a t i o n a l g o r i t h m i su s e dt oa n a l y s et h em o b i l ec u s t o m e r s p e n d i n gb e h a v i o r 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 ga n a l y s i s ；s w a n li n t e l l i g e n c e a n tc o l o n y a l g o r i t h m 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 引言 近十几年，科学技术的飞速发展带动着经济和社会都取得了极大的进 步。在各个领域产生了大量的数据，如人类对太空的探索，银行每天的巨 额交易数据。显然在这些数据中存在着丰富的信息，如何处理这些数据以 从中得到有益的信息，人们进行了有益的探索。计算机技术、网络技术和 信息技术的迅速发展，人们生产和搜集数据的能力也得到了大幅度提高， 使得数据处理成为可能，同样也推动了数据库技术的极大发展，但是面对 不断增加如潮水般的数据，人们不再满足予数据库的查询功能，提出了深 层次问题：能不能从数据中提取信息或者知识为决策服务，就数据库技术 而言已经显得无能为力了。同样，传统的统计技术也面临着极大的挑战。 这就急需有新的方法来处理这些海量般的数据。 于是，人们结合统计学、数据库、机器学习等技术，提出数据挖掘来 解决这一难题。数据挖掘技术应运而生，并显示出前所未有的强大生命力， 并且逐渐成为研究的热点，吸引了很多入进行研究。而作为数据挖掘技术 之一的聚类分析也越来越受到研究者的关注。 1 2 国内外研究现状及未来发展趋势 近年来，数据挖掘引起了信息产业界的极大关注。国内外各研究机构 纷纷开展了对数据挖掘技术的研究和探索工作。下面，本文将分别从国内 和国外两个方面对数据挖掘技术的研究现状进行阐述，并对数据挖掘技术 的未来发展趋势、研究方向及热点问题进行探讨。 1 2 1 国外研究现状 1 9 8 9 年8 月在美国底特律召开的第1 1 届国际人工智能联合会议的专 题讨论会上首次出现k d d ( k n o w l e d g ed i s c o v e r y i n d a t a b a s e s ) i 8 】这个术 语。随后在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年都举行过k d d 专题讨论会，汇集 来自各个领域的研究人员和应用开发者，集中讨论数据统计、海量数据分 析算法、知识表示、知识运用等问题。随着参与人员的不断增多，k d d 国际会议逐渐发展成为年会。 数据库、人工智能、信息处理、知识工程等领域的国际学术刊物也纷 纷开辟了k d d 专题或专刊1 9 i ，包括i e e e 知识与数据工程汇刊( t k d e ) ， a c m 数据库系统汇刊( t o d s ) ，a c m 杂志( j a c m ) ，信息系统， 西南交通大学硕士研究生学位论文第2 页 v l d b 杂志，数据与知识工程，智能信息系统国际杂志( j i i s ) 等， 其中，i e e e 的k n o w l e d g e a n d d a t a e n 百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 系统与其它传统的机器学习、专家系统、人工神经网络、数理统计分析系 统的联系和区别，以及相应的基本对策1 5 9 l 。6 篇论文摘要展示了k d d 在 从建立分子模型到设计制造业的具体应用。 根据最近g a r t n e r 的h p c 研究表明，“随着数据捕获、传输和存储技术 的快速发展，大型系统用户将更多地需要采用新技术来挖掘市场以外的价 值，采用更为广阔的并行处理系统来创建新的商业增长点。”所有这些均 表明数据挖掘已成为当前计算机科学界的一大热点1 4 ”。 群体智能的研究国外进行的比较早，当前主要是对蚁群算法的研究。 自1 9 9 1 年d o r i g o 首次提出蚁群算法以来【7 ”，蚁群算法已在路由、优化组 合、数据挖掘等多个领域取得了非常突出的成就。目前研究和应用主要集 中在比利时、意大利、英国、法国、德国等欧洲国家，日本和美国开始启 动。1 9 9 8 年和2 0 0 0 年在比利时布鲁塞尔大学召开了第一届和第二届蚂蚁 优化国际研讨会【8 】。 1 2 2 国内现状 与国外相比，国内对d m k d ( d a t am i n i n ga n dk n o w l e d g ed i s c o v e r y ) h 副 的研究稍晚，没有形成整体力量。许多单位也已开始进行数据挖掘技术的 研究，但还没有看到数据挖掘技术在我国成功应用的案例。 1 9 9 3 年国家自然科学基金首次支持对该领域的研究项目。目前，国内 的许多科研单位和高等院校竞相开展知识发现的基础理论及其应用研究， 这些单位包括清华大学、中科院计算技术研究所、空军第三研究所、海军 装备论证中心等。其中，北京系统工程研究所对模糊方法在知识发现中的 应用进行了较深入的研究，北京大学也在开展对数据立方体代数的研究， 华中科技大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、 吉林大学等单位开展了对关联规则开采算法的优化和改造【5 6 】；南京大学、 四川大学和上海交通大学等单位探讨、研究了非结构化数据的知识发现以 及w e b 数据挖掘。国内也开始有关于蚁群算法的公开报道和研究成果， 但严格理论基础尚未奠定，有关研究仍停留在实验探索阶段，多是对算法 的研究和改进等。 西南交邋大学颂士研究生学位论文第3 页 1 2 3 未来发展趋势 警兹，数据熬摇黟鲡谈发现懿谤究方兴泰艾，箕谤究与开发煞总露永 平相当于数据库技术在7 0 年代所处的地位，邋切需要类似于关系模式、 d b m s 系绫帮s o l 查询语富等瑾论和方法的稽导。两虽最近有湖两大翟 网站评比未来十大热门技术，数据挖掘占了一席之地。鉴予数据挖掘任务 和数据挖掘方法酌多样往，研究的焦点可能会集中在以下几个方面h 4 】： ( 1 ) 研究专门用于知识发现的数据挖掇语言； ( 2 ) 研巍在网络环境下的数据挖掘技米； ( 3 ) 加强对各秽菲继构化数据的挖掘； ( 4 ) 数据挖掘应用的探索； ( 5 ) 复杂数摄类型挖掘； ( 6 ) w e b 挖掘，隐私保护和信息安全等： f 7 ) 可裰纯数据挖熬； ( 8 ) 基于群体镭能的数据挖掘方法； ( 9 ) 与数据库系统、数据念痒系统秘w e b 数据痒系统鹣榘残； ( 1 0 ) 交甄式发现： 1 3 本文研究的主要内容 + 本文主要磅究戆是数据挖摇孛豹基本阕题之一一聚类分褥援零。本文 的主要内容包括如下几个方面； 篇一章介绍了数攥挖瓣投零靛发震、骚究鹜景秘发震方囱，疆毒零文 研究的主要内容。 第二章介绍了数据挖掘豹基础知识。对数舔挖箍技术的概念、产警、 应用和发现模式进行了归纳和总结，为本文的全面展开作好铺垫。 第三章是有关聚类分析的研究。聚蹙分析己经被广泛的研究了许多 年，主要集中在蒸予跋离的聚类分橱。对聚类分析的概念、产生和发展遴 行了简要的归纳和总结，同时对聚类分析中所用到的数据类型和童要聚蹙 算法进霉亍了简要的贪缁。 第四章是蚁群算法的分析与研究。研究了基于群体智能的蚁群算法， 对基于蚁群寻黪强蚁嚣聚类舞法童謦了较为详续鹣分捞。 第五章是几种聚类算法的设计、分析与研究。在此阶段的研究中，酋 先分缨了k - m e a n s 算法，绥会毁群瑟食兹习性摄裹一静蓬手傣惑素静 k - m e a n s 改进算法。然后提出一种结合基于信息索的k - m e a n s 和簇于闽值 西囊交通大学硕士硒究生学憾论文第4 页 的聚类组合算法。该算法启发于d b s c a n 算法i 7 8 i ，其思想怒把高维数描 集投影至二元数攒矩降，这样能够篱化数撰的复杂性，褥且算法篾擎明了， 更利于进行数据分析。其次借鉴经典的l f 算法1 3 6 1 和其相应的改进算法 c s i 2 扪、s a c a l 2 ”，模拟蚂蚁堆积蚁穴孛躲幼郛葶爨尸髂憝行为送行数据聚 类，并利用s a c a 算法中聚类标识的方法进行聚类的收集，然后把所产生 懿聚类中舀鞠聚类个数终巍输入，愁聚类审心作隽食携添，数据谗为蝎毅， 借用蚂蚁寻路的思想，利用基于信息素的k r f l c a n s 方 去进行二次聚类。 第六章逸霜u c i 撬器学掰瘁f 2 7 l 率静足蕴数据逶稽凡种冀法静测试和 性能分析。摄后选用取自某省穆动公司的移动话赞数据，利用蚁群聚类组 合算法来避行客户行菇分祈。 西溺交通犬学硕士研究生学位论文第5 页 第2 耄数据挖据概述 2 1 数据挖掘的概念 随着数据库技术的不断发展及数据库管理系统的广泛应用，数据库中存储 的数据量急弼增大，在大蓬静数据背嚣隐藏蓿许多熏要静信息，知果能把这蛰 信息从数据库中抽取出来，将为公司创造很多潜在的利润，而这种从海量数搬 库中挖掘信熙的技术，就称之为数据挖掘( d a t am i n i n g d m ) 。1 9 9 5 年以来，潮 外在知识发现和数据挖掘方面的论文 卷多，已形成了热门研究方向。 从广义上讲，数据挖掘是指从大鬣的、不完全的、有噪声的、模糊的、黼 枫的数据中，提取隐含在其中的、人们事先不知道躲、但又是潜在有用款售感 和知识的过程。这个定义包括l ； 下四个层次的含义。 ( 1 ) 数据源必须是真实瓣、大量鲍、会噪声的； ( 2 ) 发现的是用户感必趣的知识； ( 3 ) 发现瓣知识要霹接受、霹淫簿、霹运髑，最好l 翅鑫然港塞表达发现缩 果； 并不是要浓发臻敖之霆海警港熬舞谈，也不楚要去发现崭新豹自然科学 定理和纯数举公式，更不是什么机器嫩理证明，所有发现的知识都是相对的， 是有特定蘸疆帮终窳条释、蘑蠢特定领域的。 从商业角度出发，数据挖掘可以描述为：按企业既定业务目标，对大量的 企韭数据迸彳亍探索和分罄予，搦示隐藏的、未知静或验证己知的蕊律性，并进一 步将其模型化的先避有效的方法。 数据挖掘工具能够对将来的趋势桐行为避行预测，从而很好地支持人们的 决策，比如，经过对公司整个数攒库系绕蛉凳耩，数掇挖掘量具可以回答诸如“哪 个客户对我们公司的邮件推销活动最有可能作出反成，为什么”等类似韵问题。 有些数据挖援工具逐能够解决一些缀消耗入z 拜重闽约黄统阅题，因巍它们能够 快速地浏览糍个数据库，找出一些专家们不易察觉的极有用的信息。 爨嚣，燃爨上魄较鸯影响懿典型数据挖掇系统骞：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 t 、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 o a 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 等。 疆南交遘大学颈圭磺究生学位论文繁8 贾 2 2 数据挖掘的产生 数据库技术在经过了8 0 年代的辉煌之后，人们逐瀚认识到，查询是数据库 的奴隶，发现才爨数撰疼的主人。“数据只梵职员骚务，不为决策畿黻务i ”这 是缀多单位的领等在热心数摄滓建设岳所发出的感叹。闲诧，在需求的驱动下， 很多数据库学者从对演绎数据库的研究转向对归纳数据库的研究。 起初各种商业数据是存储在计算机的数据库中的，然后发展到w 对数据库 避行套逮窝访阋，进瑟发展戮对数霪瘁瓣鞫鼓邃嚣。数耀挖援镬数强鬻攘本进 入了一个更高缀的阶段，它不仅能对过去的数据进行焱询和遍历，并且能够找 出过去数据之间的潜在联系，从而促进倍息的传递。专家系统曾经烧人工智能 研究工作者的骄傲，但出于其在知识获取、知识表示、缺乏常识等方嚣的瓶颈， 傻褥专家系绫嚣嚣还箨蜜在孛奄迄诸努发凌梳薮障诊凝一类豹拳早上。这耋然程 使人工智能学赣开始正视现嶷生活中大嫩的、不完全的、有噪声的、模糊的、 随机的大数据样本，走上了数据挖掘的道路。数坪统计是应用数学中最莺要、 最涟跃的学秘之一，它在诗黧规发明之莪毅诞生了，迄今已有见露譬弱发曩历 变，然嚣，数臻统计察数据簿技术结合褥并不算侠。程入们有了献数据查诲妥 知识发现、从数据演绎到数销归纳的要求之后，概率论和数理统计才获得了新 的，主命力，所以才会在d m k d ( 数据挖掘和知识发现) 这个结合点上，立即呈现 爨“忽麴一夜泰簸寒，予搪万糖蘩花嚣”戆繁荣景象。现褒数据挖撼技零在亵 渡殿用中己经孵以马上授入傻用，因炎对这种技术送行支持的三静蕊础技术已 经发展成熟，他们是：海量数据搜集、强大的多处理器计算机、数搬挖掘算法。 数据挖掘技术是人们长期对数据库披沭进行研究茅玎汗发的结果，同时，也 楚缓惫技本叁然溪镬二熬筵暴。觚爨器学习麴蠲谖工程，麸酝谖工程戮专家系统， 8 0 年代人们又猩新的神经嘲络理论的指静下重新回到机器学习，随厝又进入到 数据库中的知识发现，接着又相辅相成地产生数据挖搠，在此期间，数据仓库 技术的出现和逐步成熟为数掇挖掘技术的繁荣注入了强麓豹动力，娥近人们又 认设鞫整统谤努辑方法和数据挖据有瓿戆结合将是最好豹策略。因诧，数摇挖 搦趋一门交叉学科，其发展怒一个螺旋上升的过程。 2 3 数据仓库与数据挖掘 2 3 1 数据仓库的定义 数据仓库州的概念始予2 0 世纪8 0 年代中期，其创始人号称“数据仓库之 父”的w i l l i a mh i n m o n 在他的建立数攥仓库一书中对数据仓库媛这样定义 鹳；数据仓瘁簸是嚣囱圭鞑豹( s u b j e c t - o r i e n t e d ) 、集袋静洳t c g r a t c d ) 、霹变瓣 西南交通丈学硕士磷究生学位论文第7 页 ( t i m e v a r i a n t ) 、非易失的( n o n v o l a t i l e ) 数据集合。数据仓库( d a t aw a r h o u s e ) 是计算 机应用领域墅的一个崭毅方向，它是一糖信息管理技术，其研究的主要宗塞怒 通过道畅、合理、全面的信息管理，采达到对管理次策的支持。与联机事物处 理( o p 谤魄，它宠全是贯一秘类型懿售患管理方式。 2 - 3 2 数据库中的知识发现和数据挖掘 数据库中的知识发现( k 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 * k d m 词首次出现 在1 9 8 9 年8 月举行的第l l 届国琢联会人工餐躯学术会议上l ：5 8 】。专年多人把数鬃 挖掘视为数据库中的知识发现( k d d ) 的同义词，而另一些人只是把数据挖掘视 海数攒疼中躲识发瑷过程瓣一个基本步骤。至# 赢怎榉藿，其实势不重要。翅聚 把数攒挖掘视为数据库中知识发现过程的一个基本步骤，则知识发现过程如图 1 - 1 艨示。 选择与 图2 - 1 数据挖掘视为知谈发现过程的一个基本步骤 2 4 数据挖掘的对象 淼蟊越上讲，数播挖摇可戬在任何类垄韵倍惠存储上进行，这包括关系数据 库、数据仓麾、事务数据虐、w w w 、蕊向对藏数搬疼、对象关系数撂痒、时 间序列数据瘁、空间数据库、文本数据库、多媒体数据库锋。挖掘的原始数据 可以是结构化的，如关系数据摩、数援仓库中的数撰；也霹以是渗结捣让斡， 如文本、图形和图像数据；甚至是分布在网络上的异构型数据。 褥南交通大学硕士磺究璧攀位论文第8 委 2 5 数据挖掘的应用 数撼挖掘的应用嚣寓广泛，蠢艇数据挖撼技术从一开始款是嚣向应用戆。 霜裁，程缀多矮蠛，数据挖掇都是一个禳薅髦豹谲，茏其是农翅银行、憩僖、 保险、交通、零售( 如越级市场) 等商舭领域。数攒挖掘所能解决的典型商业问题 包括：数据库营销( d a t a b a s em a r k e t i n g ) 、客户群体划分( c u s t o m e rs e g m e n t a t i o n c l a s s i f i c a t i o n ) 、鹜最分振( p r o f i l ea n a l y s i s ) 、交叉锩售( c r o s s * s e l l i n g ) 等枣璐分辑 行为，戳及客户流失饿分析( c h u m a n a l y s i s ) 、客户信用记分( c r e d i ts c o r i n g ) 、欺 诈发现( f r a u dd e t e c t i o n ) 等等。下面介绍的一些威用可以说明数据挖掘的用途。 2 。5 。1 麓品销售 巍渡部门把数援视侔一释竞争眭的财富可能比任何其他部门显得甏为重 要，为此需要把大型市场营销数据滕演变成一个数据挖掘系统。科拉福特( k r a f t ) 食品公司( k g f ) 是应用市场营销数掇库的公司之一，该公司搜集了购买它商品的 3 0 0 0 万令蹋户魏名攀，这是f 终秘逶遗各拜挺镑警段褥囊熬。k g f 定期囱遂登 用户发送名牌产品的傀惠券，介缁新产品的性能和使用情况。该公司体会剿了 解自己商品的用户越多，则购买和使用这些商晶的机会也就越多，公司的觜业 状况也就越好。 2 ，5 。2 绷王制造 许多徐司不仅将决策支持系统用于支持市场酱销活动，而且，由于市场竞 争越演越烈，这些公司已使用决策支持系统来娥视镑4 造过程，有制造商声称已 经摇示宅豹各令办事枫擒，套三年两把割遗盛零每年降低2 5 。不言蠢喻，该 制造商缝常收集各部件供应商的情况。因为，它们也必须遵循该制造商降低成 本的战略。为了对付来自各方的挑战，该制造商已拥有一套“成本”决策支持系 统，可以凝视各供应麟提供的零部传成本，以实现所制定敬徐格曩标，这耪应 雳需要牧集有关各厂瀚连续一年采静产晶成本谤感，以便礴定这种组织方筑能 否满足臊先制定的有靛降价的战略目标。 2 5 3 会融服务信用卡 逶溺汽车公司( g e n e r a l 酝o t 锄心穗经采爱信用卡- g m 卡，夜该公司翡数据瘁 中己拥有1 2 0 0 万个持有信用卡的客户。公司通过观察，可以了解他们正在驾驶 什么样的汽车，下一步计划购买什么样的汽车及他们喜欢哪一炎车辆。譬如说， 一个持蠢信震卡载客户表示黠一移栽货卡车感兴趣，公司就餐戳囊卡车鄂门发 出一个电子酃件，并撼该客户的倍惠告诉有关部门。 嚣南交通必学硕士磷究垒学位论文繁g 鼹 2 5 4 远程通讯 谗多远程通谶黪大公司近慕突然发现它镁嚣癌极大鲍竟争压力，这在几年 嚣是不存在鹩。在避去，鲎务上辩不需要氇稍密切注视枣场动囱，因为顾客的 挑选求地有限，但髓这种情况近来发生很大变化。各公司当前都在积极收集大 量的顾客信息，向他们现有的客户提供新的服务，开拓新的业务项目，以扩大 缝髓懿枣场烂模。扶这些耨戆黢务孛，公司凌短期建裁霹叛取褥更大豹效整。 2 6 数据挖掘的发现模式 随着数据挖掘和知识发现( d m k d ) 的研究逐步走向深入，其研究已经形成了 三令强大弱技术支校：数摆瘴、入王罄毙农数霪统计。因戴，k d d 大会程彦委 员会瞥经由这三个学科的权威入物同对来往童席。蛋前d m k d 的主要研究内容 包括基础理论、发现算法、数据仓库、可视化技术、定性定量互换模型、知识 表示方法、发现知识的维护和露利用、半结构化和非结构化数据中的知识发现 鞋及溺上数据挖掇簿。下覆裁数攥笼籀瑟发瑷豹最零燕戆懿谈揍式( 类蘩) 痒一蔫 单介缁，所介绍的这些知识都可以在不同的概念层次上被发现，髓着概念树的 提升，从微观到中观再到宏观，以满足不同用户、不同层次决策的需要。 2 6 。1 广义模式 广义模式( g e n e r a l i z a t i o np a t t e r n ) 是指类剃特征的概括性描述知识。根据数据 的微观特性发现其袭征的、带有酱遍性的、较高层次概念的、中观和宏观的知 识，反映同类事物熬同性质，是辩数据的檄撼、糖炼和抽象。 广义模式豹发瑗方法秘实瓒技寒包括数瓣立方俸、麓寨夫s i m o n f r a s c r 大学 提出的丽向属性的归约( a t t r i b u t e o d e n t c di n d u c t i o n ，a o o 方法等。基于数据立方 体的檄化技术由e e c o d d 、s b c o d d 和c t s a l l c y 删提出，数据立方体中计算聚 集蛉撩傣由g r a y 、c h a u d h u r i 、b o s w o r t h 、l a y m a n 、r e i c h a r t 、v e n k a t r a o 、p e l l o w 移p i r a h e s ht 磺提爨，葱尚属性懿魍约方法崮c a i 、c e r c o n e 翻h a n l 6 6 1 提出等。 2 6 2 关联模式 荚联模式( a s s o c i a t i o np a t t e r n ) 是反映一个攀馋和其德豢传之闻樱爱依赖或 关联的知识。经典的关联鬣羽发现方法可分为两多：第一步是迭筏说刘所有的 频繁顾集，要求频繁项集的支持率不低于用户设定的最低假；第二步怒从频繁 项集中构造可信度不低于用户设定的最低值的规则。识别绒发现所有频繁项集 是关联溉戴发现箕法懿核心，魄烧圣 葵薰最大懿煞分。在滚簿关联甄谖发现霹， 需要薹| j 用户输入最小雹信度c 和最小支持度s 。 西南交通大学硕士研究生学位论文第1 0 页 2 6 3 序列模式 序列模式( s e q u e n c ep a t t e r n ) 分析和关联分析相似，其目的也是为了挖掘数据 之间的联系，但序列模式分析的侧重点在于分析数据间的前后序列关系。它能 发现数据库中形如“在某一段时间内，顾客购买商品a ，接着购买商品b ，而 后购买商品c ，即序列一b c 出现的频度较高”之类的知识，序列模式分析 描述的问题是：在给定交易序列数据库中，每个序列是按照交易时间排列的一 组交易集，挖掘序列函数作用在这个交易序列数据库上，返回该数据库中出现 的高频序列。在进行序列模式分析时，同样需要由用户输入最小置信度c 和最 小支持度s 。 a g r a w a l 和s r i k a n t 提出了一种类a p r i o r i 技术的序列模式挖掘算法 2 5 1 ， s r i k a n t 和a g r a w a l 提出了挖掘序列模式的g s p 算法1 3 7 1 ，z a k i 、l e s h 和o g i h a r a 提出了对p l a nf a i l u r e 的序列模式挖掘i 叩j ，g u h a 、r a s t o g i 和s h i m 提出了一种基 于约束的序列模式挖掘方法【6 1 】，h a n 、p e i 、m o r t a z a v i a s l 、c h e r t 、d a y a l 和h s u 提出了序列模式挖掘的f r e e s p a n 方法【6 7 1 ，y i 、s i d i r o p o u l o s 、j o h n s o n 、j a g a d i s h 、 f a l o u t s o s 和b i l l r i s 给出了针对时间序列的联机挖掘方法1 6 8 增。 2 6 4 分类模式 设有一个数据库和一组具有不同特征的类别( 标记) ，该数据库中的每一个记 录都赋予一个类别的标记，这样的数据库称为示例数据库或训练集。分类分析 就是通过分析示例数据库中的数据，为每个类别做出准确的描述或建立分析模 型或挖掘出分类规则。然后用这个分类规则对其它数据库中的记录进行分类。 导出模型是基于对训练数据集( 即其类标记已知的数据对象) 的分析而产生的。分 类模式的预测值可以是离散的( 如根据某种动物的特征来判断这种动物是两栖 动物还是哺乳动物) ，也可以是连续的( 如根据某人的受教育情况和工作经验来判 断这个人的工资范围) 。 分类模式( c l a s s i f i c a t i o np a t t e m ) 的实现技术包括决策树、统计、粗糙集 ( r o u g h s e t ) 、神经网络方法等。最为典型的决策树学习系统是i d 3 ，它采用自顶 向下不回溯策略，能保证找到一个简单的树。算法c 4 5 和c 5 0 都是i d 3 的扩 展，它们将分类领域从类别属性扩展到数值型属性。线性回归和线性辨别分析 是典型的统计模型分析方法。 2 6 5 聚类模式 聚类分析和分类分析是一个互逆的过程。在统计方法中，聚类分析是多元 数据分析的三大方法之一( 其它两种是回归分析和判别分析) 。在机器学习，中聚 覆南交通大学硕士研究生学位论文繁1 1 贾 类分析被称作无监督缄无教师归纳。在人工智熊文献中，聚类也称概念聚获。 与分类分柝不圊，聚类分孝斤输入的是一缀来分类记录，著且这些记录应分贼几 类事先也不知道。聚炎分析就是通过分析数据滕中的记录数据，根据一定的分 类愿则，合理圭| 曩划分记录集会，礁定每个记录鼹在类艇。数握疼孛瓣记录被睨 分为一系列有意义的予集叫做聚( 簇) 类。分类原则采用最大化捷内的相似性、最 小纯类阕靛耜戗蛙滠裂，帮往褥一令簇串戆对象具有缀亵熬攘辍瞧，嚣与其瞧 簇中的对象很不相似。 聚类模式( c l u s t e r i n gp a t t e r n ) 鬣牾统计方法、凝嚣学习方法、弹经随臻方法 和面向数据库的方法，比如，系统聚类法、分解法、加入法、动态聚类法、有 净样品聚类、稳重叠聚类、模耧聚类法、运筹方法等。主要钓聚类葬法静炎鍪 可分为基于划分方法、基于层次的方法、基于密度的方法、基于网格的方法、 基予模黧的方法等。一个聚类算法通常包含了多种聚炎方法的思想。在神经网 络中，有类光监督学习方法：自组织神经网络方法，如k o h o n e n 自组织特征 映射网络、竞争学习网络等。在数据挖獭领域翼，神经网络浆类方法主要是自 组织特缀映射方法，i b m 农蒸发布的数掇挖掘囱皮书巾就特剜提到了使用忿方 法进行数据库聚类分割。 2 。6 。6 羧测模式 预测模式( p r e d i c t i o np a t t e r n ) 根据时间序列型数据，由历史的和当兹的数据 去推测采来的数据，也称作时间序捌模式。可以认为预测型模式是以时间为关 键属性的关联模式。 时间序歹n 预测的方法有经典的统计方法、神经网络方法和机器学习方法等。 2 + 6 。7 编差模式 偏熬模式( d e v i a t i o np a t t e r n ) 是对差异积极端特倒的描述，揭示了率物偏离霉 规的异常现象。偏离常规的数据有时被日q 做孤盘点( 0 u t l i e r ) ，阂此偏蒺模式有时 被目q 傲孤立点模式。 偏麓模式的发现方法可以分为统计的方法、基于躐离的方法和基于偏移的 方法等。 2 7 数据挖掘的技术 前面在介缁数据挖掘的发现模式时，针对每一种知识类型，都介绍了相应的 数据挖掇技术。逶霉，数据挖掇技术霹分为援嚣学器方法、统诗方法、专孛经爨 络方法、数据库方法等。下面，将对这些技术作一简螫的介绍。 西南交通必学硕士研究生学位论文第12 贾 2 7 1 机器学习方法 枫瓣学习方法霹分鸯：归纳攀习方法( 决策麟、规则归纳莓) 、基手越饿懿学 习、滚传算法等。 2 7 2 统计方法 绞诗方法可分为；霉归分掇( 多元匿蛸、囊回归等) 、判别分析( 受跨焱判别、 费歌尔潮鬟、j 参数潮爱等) 、蒙裘分祈( 系统浆类、动态聚黉、分解法、潮入法、 模糊聚炭法、运筹方法等) 、探索性分析( 主冗分析法、相关分析法等) 等。 2 7 3 神经网络方法 拇经网络方法w 分为：蓠浅耱经蕊络( b p 舞法等) 、自缀织神经网络f 螽组织 特征映射、竞争学习等) 等。 2 7 4 数据库方法 数据痒方法哥分为：多维数摄势折、o l a p 方法、瑟囱属性豹彗葺鲶方法等。 西南交通大学硕士硪究生学位论文繁13 页 第3 章聚类分析 3 1 聚类分橱的定义 在日常生活、生产、科研工作中，经常要对被研究对象进行分类。研究和 楚淫给寇对象豹分类鬻焉酌魏学方法是聚类分祈( c l u s t e r i n ga n a l y s i s ) 。聚炎分 析是一种重要的人类行为，它的目的是把相似的东磷归为一类，使得类内具 有较大的相襁橼，而裳闯其肖较小的相似往。聚类分析是多冗统计分析的方法 之一，它试图擞据数擐集的内部结构将数据集分成蓑于个不同的予类，使褥同 予类中的样本尽可能的相似，不同子类的样本尽可能的不相似。换句话说， 如果将会寅n 个榉本x l ，x 。的数据集x 聚集成e 个子类x l 。+ 蕊则要求 x l ，) ( c 满足： x 1 u x 2 u u x 。= x x j nx j = f ( 1 i j c ) 聚类劈柝黾经广泛遮麓在诲多应 毖l 中，镪挺挨戏识翔，数据分辑。罄 象处理，以及市场研究。通过聚兴，人能够识别密集的和稀疏的区域，因 焉发瑰全局鑫冬分京模式，激及鼗握藩经之蓠豹有趣瀚耱嚣关系。 与分类不同的是，它要划分的类是未知的。在分类模式中，对于目标 鼗据痒审存在繇些粪这一镄息我稻是翔道静，在郡挺我们要骰静就是将每 一条记录分别属于哪类标记出来。聚捷分析源于许多研究领域包括数据 挖掘、统计学、生物学、戳及辊器学习等。慧在预先不知道目标数据痒到 底有多少类的情况下，希望将所有驰纪泶组成不同的类或者谖“聚 类”( c l u s t e r ) ，使得在同一聚类之间具有较大的相似旋，丽在不同聚类之间 具有较大的相似度。聚类就是根据攒述对象的属性值计冀褥出螅相雾度， 将数据对象分组成为多个炎或簇，在同一个簸中的对象之间具有较高的相 似度，愿不羼簇中蛇对象蓑裂较大。蹬寓是缝豢采照豹度爨提徽度载夔要 方式。 数掇聚类逶在蓬勃发淡，骞荧献豹聚究领域惫援数掇挖攘、统诗学、 机器学习、空间数据库技术、生物学、以及市场营销。由于数据库中收集 了大量懿数据，聚类分辑基经残冀数据挖据磷究矮