（电路与系统专业论文）数据挖掘中聚类算法研究与仿真[电路与系统专业优秀论文].pdf

阱f 学位论义 数据挖掘中聚类髯= 法研究0 仿真 摘要 近年来，数据挖掘在很多行业得到了越来越广泛的应用，如序列模式分 析、客户分类与聚类、交叉销售、甄别欺诈行为等。聚类，作为数据挖掘中的 主要方法之一，也受到越来越多的关注。目前已经有很多比较成熟的聚类算 法，如k m e a n s 、k m e d o i d s 、b i r c h 、c u r e 、d b s c a n 、s t i n g 等。虽然其 中有些算法已经得到成功应用，但是，聚类分析也面临着越来越多的新问题。 如海量数据的处理、商维数据的聚类、子空间聚类、带有约束条件的聚类、数 据流聚类等。针对这些新问题，很多人在不断研究新的算法，也有人在以前算 法的基础上不断地进行改进。 为了解决高维海量数据的聚类分析问题和数据流聚类问题，本论文设计了 一系列新的聚类算法：等密度线聚类( d i l c ) 算法、基于网格的等密度线聚 类( g r i d ) 算法、a g r i d 算法、用于不同密度聚类的多阶段算法、用于数据 流聚类的o n l i n eg r i d 算法、以及高维聚类通用框架模型。其中，a g r i d 算 法通过结合密度型聚类和网格型聚类两者的长处，能够有效地用于高维海量数 据的聚类分析，并具有很好的时间复杂度和空间复杂度。此外，本论文还提出 了数据挖掘与数据仓库、o l a p 等技术在电信行业应用的建议方案，并对数据 挖掘在电信计费数据分析中的应用进行了尝试和探索。 本论文的主要贡献有以下几点： 1 结合基于密度聚类的思想，提出了等密度线聚类( d i l c ：d e n s i t y b a s e di s o l i n ec l u s t e r i n g ) 算法【“鲫”。该算法利用地理学中等高线的 思想，把该思想与密度聚类相结合，能够识别任意复杂形状的聚类， 并且能够有效排除噪声的干扰。此外，聚类的结果不受数据输入顺序 的影响。该算法的思想和有效性经过了实验验证，并发表于北京邮 电大学学报。 2 结合基于网格聚类的思想，提出了基于网格的等密度线聚类( g r i d ： g r i d b a s e di s o d e n s i t yl i n ec l u s t e r i n g ) 算法 z s 0 1j 。通过结合基于密 度聚类和基于网格聚类两者各自的优点，该算法利用网格和邻居的思 想来减少计算的复杂度，从而实现快速的聚类。该算法的有效性通过 实验进行了验证。其具体思想发表于i c i i2 0 0 1 国际会议。 3 通过对邻居定义和网格单元存储方法的改进，提出了a g r i d ( a d v a n c e dg r i d b a s e di s o - d e n s i t yl i n ec l u s t e r i n g ，即改进的g r i d 算法) 算法【z 8 03 。该算法中还采用了更好的分割方法以及更好的自 麟 学位鲍义 数撼挖粥中浆类算法拼抛i 仿萁 洳参数确定方法，使之能够很好的艨用于海量耐维数据集的聚炎分 丰肝。本论文对算法的复杂艘进行了分析和推导，弗通过把该算法成用 予静静复杂形状数据榘，诞稿了算法黪瘫牲戆露鸯效牲。该冀滚发表 j ：p a k d d2 0 0 3 毽际会议。 4 针对数据集中各个聚类的分桁密度不删的特点，挝 ： j 了用于不嗣密度 凝类的g r i d 凝类算法f 2 8 。8 。3 t 。通避多个殓段垂冬巢类，该算法熊够识 鞭溅藤疑羧键集中分毒密瘦不霜甚囊蘧髯较大蕊各个聚类。零论文逶 过实验证明了簿法的有效憔。该算法的飙体思想发寝。】二北京邮电大 学学报。 5 。钟对二整数撵流懿特点，逢过露g r i d 算法静玫滋，捷逡了o n l i n e g r i d 算法2 8 。3 1 ，来实现对= 维数据流的聚类。邋避厢代表寨泉代替 原始数据集，从而保证了谯有限的空间条件下能够对连续的二维数据 浚逶嚣离速蒙炎。零沦文遴过复杂鏖分摄鞫实验验谖了其有效瞧。滚 算法已揆稿蒸电子攀擞。 6 针对高维数据空间中数据分布的特点，提出了高雅邋用聚类糕槊模型 f 。s 0 2 2 ，2 s 0 3 。】。道过把一个嬲维蒙类过程分瓣为多个一维或嚣维浆粪过 程，胰瑟楚蒋遴鼹低维聚炎簿法麓够寄效地蘑予惑绻数据集的蘩类。 论文中通过实验验证了该模型的有效性。该框架模型思想发袭于 c c e c e2 0 0 3 国际会议。 兴键诿：数据挖蘧，豢炎，无整罄警嚣，嵩维，数摅滚 茎i ：兰笙堡苎! 鍪蓬篷堡宝篓耋篓鎏塑奎：缝壅! 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 sa p p l i e dm o r ea n dm o r e w i d e l yi nm a n yf i e l d s ， s u c ha st h ea n a l y s i so f s e q u e n c e ，t h ec l a s s i f i c a t i o na n dc l u s t e r i n go fc u s t o m e r s ， c r o s s s e l l i n g ，d e t e c t i o n o f f a u d u l e n c e ，e t c ，c l u s t e r i n g ，a s o n eo ft h em a i n t e c h n i q u e so fd a t am i n i n g ，b e c o m e sa ni n c r e a s i n g l yh o tt o p i c a tp r e s e n t ，m a n y c l u s t e r i n ga l g o r i t h m sa r ea v a i l a b l e ，s u c ha sk - m e a n s ，k m e d o i d s ，b i r c h ，c u r e ， d b s c a n ，s + f i n g ，a n ds o o n a l t h o u g h s o m eo ft h e mh a v eb e e n a p p l i e d s u c c e s s f u l l y i ns o m ef i e l d s ，m a n yn e wc h a l l e n g e sa r e e m e r g i n g ，s u c ha s t h e h a n d l i n go fl a r g e d a t a s e t sa n dh i g h d i m e n s i o n a l d a t a s e t s ，s u b s p a c ec l u s t e r i n g ， c l u s t e r i n gw i t hc o n s t r a i n t s ，c l u s t e r i n go fd a t as t r e a m s ，e r e t os o l v et h e s en e w p r o b l e m s ，s o m es t r i v e t o d e s i g n b r a n dn e wa l g o r i t h m s ，w h i l eo t h e r s t r y t o i m p r o v ee x i s t i n ga l g o r i t h m s 。 i no r d e rt os o l v et h e p r o b l e mo fc l u s t e r i n g o f l a r g eh i g h d i m e n s i o n a l d a t a s e t sa n dd a t a s t r e a m s ，ac o u p l e o fa l g o r i t h m sa r e p u t f o r w a r di nt h i s d i s s e r t a t i o n t h e s e a l g o r i t h m s a r e r e s p e c t i v e l yd i l c ，g r i d ，a g r i d ，m u l t i s t a g ec l u s t e r i n g ，o n l i n eg r i d ，a n dag e n e r a lf r a m e w o r kf o rc l u s t e r i n gh i g h d i m e n s i o n a l d a t a s e t s b yc o m b i n i n gd e n s i t y b a s e d a n dg r i d - b a s e d c l u s t e r i n g t o g e t h e r ，a g r i dh a st h em e r i t so fb o t h ，a n dc a nh a n d l el a r g eh i g h d i m e n s i o n a l d a t a s e t s e f f e c t i v e l ya n de f f i c i e n t l y 。i na d d i t i o n ，as o l u t i o no fa p p l y i n gd a t a m i n i n gi nt h ef i e l do f t e l e c o mi sp u tf o r w a r d ，a n ds o m et r i a l sa r em a d et om i n i n g t h eb i l l i n gd a t ai nt e l e c o mf i e l d t h ec o n t r i b u t i o n so ft h i sd i s s e r t a t i o nc o m p r i s et h ef o l l o w i n gs i xp a r t s 1 ac l u s t e r i n ga l g o r i t h m ，d i l c ( d e n s i t y - b a s e di s o l i n ec l u s t e r i n g ) z x s 0 2 ， i s p u tf o r w a r db a s e do nt h ei d e ao fd e n s i t y b a s e dc l u s t e r i n ga n dt h e i s o l i n ei n g e o g r a p h y i tc a nd i s c o v e rc l u s t e r s o fv a r i o u s s h a p e s a n d e l i m i n a t en o i s e e f f e c t i v e l y b e s i d e s ，t h e r e s u l to f c l u s t e r i n g i s i n d e p e n d e n to f t h eo r d e ro f i n p u t 2 c o m b i n e dw i t ht h ei d e ao f g r i d - b a s e dc l u s t e r i n g ，g r i d ( g r i d b a s e di s o - d e n s i t yl i n ec l u s t e r i n g ) 【2 8 0 i sp u tf o r w a r d t oa c h i e v e h i g h s p e e d c l u s t e r i n g g r i dh a sb o t ht h em e r i t so fd e n s i t y b a s e dc l u s t e r i n ga n d g r i d * b a s e dc l u s t e r i n g b yr e d u c i n gc o m p u t i n gc o m p l e x i t yw i t ht h ei d e a o f g r i da n dn e i g h b o r ，h i g h s p e e dc l u s t e r i n gi sa c h i e v e d 。 3 o nt h eb a s i so fg r i d ，t h ed e f i n i t i o no fn e i g h b o ra n dt h et e c h n i q u eo f s t o r i n g c e l l sa r e i m p r o v e d a n dt h e a l g o r i t h m o fa g r i d ( a d v a n c e d g r i d b a s e di s o d e n s i t yl i n ec l u s t e r i n g ) z s 0 3 - 1 1 i sp u tf o r w a r d b e s i d e s ， 搏l ：学位论史数摧挖掘中梨类算法l l 究j 仿真 a na d v a n c e dm e t h o do fp a r t i t i o n i n ga n da na u t o m a t i c t e c h n i q u e o f c o m p u t i n gp a r a m e t e r s a r e a d o p t e d ，w h i c h m a k ea g r i dc a p a b l eo f c l u s t e r i n gl a r g eh i g h d i m e n s i o n a ld a t a s e t se f f e c t i v e l y 。 4 o n o b s e r v i n gt h a tt h ed e n s i t i e so f c l u s t e r si nad a t a s e ta r ed i f f e r e n t ，a n a l g o r i t h mi si n v e n t e dt o f i n dc l u s t e r so fv a r i o u sd e n s i t i e s z s x s 0 3 1 b y c l u s t e r i n g i ns e v e r a l s t a g e s ，i t c a nd i s c o v e rc l u s t e r sw i t hd e n s i t i e so f d i f f e r e n c ee f f e c t i v e l y 。 5 a na l g o r i t h mi s p u tf o r w a r dt oh a n d l eo n l i n ed a t as t r e a m s z s 0 3 - 3 1 b y u s i n gar e p r e s e n t a t i v ed a t a s e ti n s t e a do ft h eo r i g i n a lo n e ，i tc a nc l u s t e r t w o 。d i m e n s i o n a ld a t as t r e a m sw i t h h i g hs p e e d 6ag e n e r a lf r a m e w o r kf o r c l u s t e r i n gh i g h d i m e n s i o n a ld a t a s e t s z s # 2 2 ， z s 0 3 2 l i sp u tf o r w a r da c c o r d i n gt h ec h a r a c t e r i s t i c so fh i g h d i m e n s i o n a l c l u s t e r i n g i n t h e f r a m e w o r k ，ah i g h - d i m e n s i o n a l p r o c e d u r e o f c l u s t e r i n g i s d e c o m p o s e d i n t os e v e r a lo n e o rt w o d i m e n s i o n a l p r o c e d u r e so fc l u s t e r i n g c o m m o na l g o r i t h m sd e s i g n e df o rc l u s t e r i n g l o w d i m e n s i o n a ld a t a s e t s ，w h e nc o m b i n e dw i t ht h ef r a m e w o r k 。c a nb e a p p l i c a b l et oh a n d l eh i g h ，d i m e n s i o n a lo n e s 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 g ，u n s u p e r v i s e d l e a r n i n g ，h i g h d i m e n s i o n a l ，d a t a s t r e a m 髀f ：举位论空 数挺挖掘串黎类算法研究i 协嚣 第一章引言 隧静，数据稼掘广泛箍应用于许多领域。在黛耪医学领域，数攒挖瓣掰予 d n a 序列模式的分析；在银j 亍和盒融领域，数搬挖掘用于贷款支付预测、客 ，信阚策略分析、客户分类与聚类、洗钱和其他会融犯罪的甄剐等：在零售 业，数摄挖掘用于销售活动的有效性分析、客户保塑、购买推荐和交叉销售 等；在电信业，数据挖獭也用于帮助理解商业行为、甄别欺洚行为、更好的利 翅资源翻提麓骚务质量等。聚类，据为数撰挖掘中艇主要方法之，迮受鲻越 来越多的关注。聚类分析广泛在很多领域中也得到了广泛的应用，如模式识 别、数据分椽、黧像处璞、枣场礴究等。在藩韭壤域，浆类瑶戳帮韵寿汤入员 从客户数据库中发现不同的客户群体，并根据购买特征找出每个群体的特点。 在生物学中，聚类冒颤用于筏掰植物釉动物的分黉法，穰雍功能对鏊因进行分 类。浆类还可以用于从地球观测数据库中识别相似的土地使用区域，根据房屋 的类型、价值和娥理位鬣识别城市中的房屋群，遥可以通过对网络中信息的分 类来凝助嬲络中的信息发现。它还可以用予对数攒分布的探索，观察每个聚类 的特点等。此外，还可以用作其他数据挖掘算法的预处理阶段。 瓣前，鲢界上有许多莺家静专家帮学者繇在致力子数据挖箍算法的磷究， 其中也包括对聚类算法的研究。其中比较著名的学术团体、会议和组织有 a c ms i g k d d 、i e e ei c d m 、s d m 、p a k d d 、p k d d 、v l d b 、f s k d 、 m l d m 等。 现有的聚类算法大致可以分为四大类：划分聚类算法、层次聚类算法、密 度型聚类算法、圈格型聚类算法。霞藏已经有很多眈较成熟的聚类算法，魏k m e a n s 、k m e d o i d s 、b i r c h 、c u r e 、d b s c a n 、s t i n g 等。虽然其中有些 算法已经得到成功应用，但是，聚类分析也面临着越来麒多的新问题。如海量 数据黪处理、高维数据的聚类、予空阀聚类、带鸯约束象 牛的聚类、数据流聚 类等。针对遮些新问题，很多人在不断研究新的算法，也有人在以前算法的基 礁上不瑟避滋行改进( 翔 8 f r 9 8 ) 。 为了解决商维海量数据的聚类分析问题和数据流聚类问题，本论文设计了 一组新的聚类算法：等密度线浆类算法( d i l c ：g r i d b a s e dd e n s i t yi s o l i n e c l u s t e r i n g ) 、基于网格豹等密度线聚类算法( g r i d ：g r i d b a s e di s o d e n s i t y l i n ec l u s t e r i n g ) 、a g r i d ( a d v a n c e dg r i d ) 算法。通过结合密度型聚类和 爨穆型蒙类嚣者豹长楚，g r i d 莘曩a g r i d 算法毙够霉效媳建予薅维海爨数据熬 聚类分析，并具有很好的时间复杂度和空间复杂度。通过对g r i d 算法进步 苎! ：竺丝燕塞 ! 垫篓篓篓士墨茎苎垄竺! 塞兰堕塞! 改进，提出了用于数据流聚类的o n l i n eg r i d 算法和用于不同密度聚类的多阶 段算法。此外，针对商维数据聚兴，本论文还提出了一个通用框架模型，普通 戆聚类舞法，透过譬该模型耱结会，裁毙够实现对离维数据集豹离速聚类。这 些算法和思想都己公开发表予国际国内麓于l l 裙学术会议上，译觅附录“发表文 章列表”。 l 。i 主要内容和结构安排 本埝文的主要内容和结构安排如下： 第一耄分绥本论文的结构安捺葶珏一些必要熬搿号说明，简单穷绍数掇挖掘 的概念、知识发现遥程以及主要鹃数据挖掘授术，并介绍聚类问题的定义和主 要的聚类算法，并对备类算法的特点和性能进行了分析和比较。 第二章提出了基予阚格豹等密度线聚类算法。第一节中利用地理学巾等高 线静瑟憨，结合基于密度聚类懿瑟慧，提出了d i l c 聚类舞法。然螽，第二节 在d i l c 算法的基础上，通过引入网格和邻居的思想，提出g r i d 聚类算法。 通过结合基于密度聚类和基于网格浆类两者各自的优点，从而实现快速有效的 蒙类。第三节杰对g r i d 算法改惑憨基疆土，挺氆了能够霹大型裹缝数攒集逶 行侠速有效聚类的a g r i d 聚类算法。a g r i d 聚类算法中通过对邻居定义和网 格单元存储方法的改进，还采用了更好的分割方法以及更好的自动参数确定方 法，使之能够很好的疲用于海量赢维数据集的聚类分析。第网节进行了总结。 第三牵提出了对予不同密度聚类的多除羧蒙类思想。钟辩数据集中番个聚 类的分布密度不同的特点，提出了用于不同密度聚类的多阶段聚类算法，并针 对二维数据集和时间序列数据集进行了实验。 第嚣露提窭了爱予二维数据滚聚类兹o n l i n eg r i d 蒙类箨法，奔绥了针对 二维数据流的数据空间离散化方法，并通过受影响网格单元的概念和分批浆类 的思想来提高算法的性能。然后通过实验对算法的性能进行了验证。 第聂露提出了簿予莲维鼗据聚类懿逶舔聚裘框絮搂鍪。该模壅逶遥熬令 高维聚类过程分解为多个一维或两维聚类过程，从而使普通的低维聚类弹法能 够有效地用于高维数搬集的聚类。 第六露搴 对鼗撬攘凌在毫癌行渡貔痤惩提壅了一个建议方寨，著穷缓了零 沦文对予数据挖掘在l = 融信计费数据分析方面的应用尝试。 第七章对全文进行总结，并提出以后的研究方向。 竖! 兰垡堡兰 ! 墼攥竺墅生鲞壅茎鋈竺! 壅：! 篓壅1 1 2 符号说明 猩本论文中。用到的符号如下；d s 表泳聚类用的数据集，疗和d 分别楚原 始数攘集d s 豹大小窝缎数，t c 秘s c 分别表示装类算法魏孵闼复杂菠郓空越 复杂度，r r 表示邻域半径( 即距离阅值) ，d t 袭示密度阈值，a 照数据集中 豹一个对象，巴表示对象程繇在懿翅格单元，强表示第i 令绦发羧分割或静潮 隔数目，m 表示懿个数据空删被分割成的嘲格单元的数目，c 。表示第f 个聚 类。 1 3 数据挖掘简介 数据挖掘( d a t am i n i n g ) 。简单说来，就是从大量数据中挖掘或发现隐藏 疰其中粒知识。它是在澎塞数据孛探索，势歇孛发现著旋取隐藏在茭中夔鸯瘸 信息的一种处理分析过程，是个综合了数据库技术、人工智能、神经网络、 模式谈剩、绕计学、决繁耱、受时瓶分辑、遗传算法、模糊集、褪糙集等镞竣 基础并吸收了大嫩新颖思想的非常活跃的交叉学科，是k d d ( k n o w i e d g e d i s c o v e r yi nd a t a b a s e s ) 邋程中的一个关键环节。下面将对知识发现过程和主要 的数据挖掘技术进行简单介绍。 1 3 1 知识发现( 袖黔) 过程 数据挖掘是知汉发现过程巾的一个关键垮节。完整的知识发现过程由以下 步骤组成：1 ) 数据清洗，即去除噪声和不一致的数据；2 ) 数据集成，把多个 数据漾中魏数据集袋到一起；3 ) 数攒选择，帮双数据瘁中选择与分橱任务箱 关的数据；4 ) 数据变换，通过汇总、聚集等方法，把数据转换为适于进行挖 掘酶形式；5 ) 数据挖掘，采丽智麓豹方法来提取数据中躬模式；6 ) 模式评 价，选取正确的有用的模式；7 ) 知识展现，采用可视化的展现技术把知识展 示给掰户。 博l ：学位论义数据挖掘中聚兴算法研究0 仿真 图i 1k d d 过程 1 3 2 预处理( p r e p r o c e s s i n g ) 原始数据中存在很多问题：杂乱、重复、不完整、不一致等，这些会降低 数据挖掘的效率，甚至会使数据挖掘的结果产生偏差。通过预处理，可以提高 数据的质量，从而保证后续挖掘过程的精确性和高效率。主要的预处理方法 有： 1 ) 数据集成( d a t ai n t e g r a t i o n ) ：将多个文件或数据库中的异构数据进 行合并，主要涉及数据的选择、数据的冲突问题及不一致数据的处 理，例如：属性同名异义、异名同义，单位不统一、字长不一致、类 型不统一。 2 ) 数据清理( d a t ac l e a n i n g ) ：去除噪声数据和无关数据，处理遗漏数 据和无效数据。包括重复数据处理和缺省数据处理，并完成一些数据 类型的转换。 3 ) 数据变换( d a t at r a n s f o r m a t i o n ) ：找到数据的特征表示，用维变换 或转换方法减少有效变量的数目。包括规格化、切片、旋转、投影等 操作。 4 ) 数据缩减( d a t ar e d u c t i o n ) ：在对发现任务和数据本身内容理解的基 础上，寻找依赖于发现目标的表达数据的有用特征，以缩减数据规 模，从而尽可能在保持数据原貌的前提下，最大限度地精简数据量。 主要途径有三个：一是数据集大小缩减，常用方法是数据抽样，减少 对象数目；二是维度缩减i d l y 9 7 ，也就是属性选择，即通过优化特征子 搏l ：学位论史 数糍挖掘中聚类算法j o f 究i 仿真 集选择，减少字段数目；三是属性德数缩减，包括连续型属性值的离 散化，实值属性的定性化，属性值的食并等。 1 3 3 聚类( c l u s t e r i n g ) 俗话说：“物以类聚，人以群分”。聚类就是利用计算机技术来实现这一 强豹筑秘按零。葵输入是一缀寒分类豹遮藏，虽事宠不缎遂如 哥分类，超可 能不知邋要分成几粪。把裙似憔大的对象聚纂为一个类。邋过分析数攒，台理 划分记录集合，确定每个记录所腻的类别。聚类的标准是使类内相似艘尽可能 大、类潮相似度尽可能小。 聚类是把一些数据穰据英穰曩闻内在酶稳钕牲蠢分成蛰于个聚类。与分类 有一个明显的不同：分类中，数攒的类别是已知的，用这贱数据来构建模型， 并用该模型来预测术知数据的类别；而在聚炎中，所有数据的类别都是未知 熬，投撰鼹象翅麴耀 荻型或穰暴攥来鼹鼗器送行分缀，恕鞠逛翡对象舞入嗣一 个组，丽差异较大的对象归入不同的组。聚类属于无监督学习( u n s u p e r v i s e d l e a r n i n g ) 。聚类技术主要分为以下几类：划分聚类、层次聚类、密度趔聚类 和网格型浆类。关于这些技术豹详细分绍，请参看第1 5 节。 1 3 4 分类( c l a s s i f i c a t i o n ) 和预测( p r e d i c t i o n ) 分炎，是指撮撂强经分好类别戆数据，从孛学习分类熬篾煲 j 蒡构建模型， 然后根据该模型对薪数据进行分类。它实际上怒种有馥餐学习。常餍的分类 技术有：决策树、贝叶斯置信网络、后向传播神经网络等。此外，k 近邻、基 于事例的推理( c a s e b a s e dr e a s o n i n g ) 爰予分类。主要兹分炎算法毒c h a i d 、 、遗传辣法、模糊集、粗糙集等都可以 c a r t 、c 5 ，0 等。 预测与分类比较相像，不过分类中要预测的是枚举型的类别标识，而预测 则是要预测连续的数馕。常用的预测方法有线性回归、多元回归、非线性回归 等。 1 3 5 关联分析( a s s o c i a t i o n ) 关袋分辑就是寻我瓣一事终孛滋魏煞不溺矮懿褪关淫，笈璇其毒攒定豹最 小置信度( c o n f i d e n c e ) 和最小支持鹰( s u p p o r t ) i 拘关联规则。关联分析主要用于分 析交易型( t r a n s a c t i o n ) 数据库，能发现形如“9 0 的顾客在次购买活动中 购买a 的嗣孵黪买b ”之类的知识。攒如：关联嫂刘a 一8 ，其中a 、b 为物 麟 j 学位论文 数糍挖掘中聚兴算法埘究5 j 协真， 晶集戏璃矬集。该关联嫂剐的支持瘦s u p p o 噬a b ) 是攒a 彝b 网辩出现嬲壤 率，箴信度c o n f i d e n c e ( a b ) 是在a 出现的条件下b 发生的概率，而改普度 l i f t ( a - - b ) = c o n f i d e n c e ( a b ) ，p f 8 ) 。改蓥凄越糍，a 熬出瑰慰b 臻瑗豹獐戆 性影响就越大。最常见的应用领域怒购物麟分析，即通过搜索经常在一起购买 或蹶滓麓茨的物晶集，来研究客户翡赡买习霰。常觅算法有a p r i o r i 、f p g r o w t h ( f r e q u e n t p a t t e r ng r o w t h ) 、( a i s 9 3 】、 a s 9 4 、f c h n 9 6 等。 1 3 6 序列模式分析( s e q u e n c e ) 在绘定交易序到数据库中，每个序列怒按照交易时蚓排列的一缎交易集， 通过分析数据问的前后序列关系，发现高频序列模式。序列模式分析侧重于分 褥数掇闻豹 ； 轰净列关系，翔“在菜段慰翊瘫，黢霉走购买赛燕a 、接着买蘧 品b 、然后买c ，即序列a b c 出现的频度较高”。在给定交易序列数据 痒申，每个疼裂愚按照交篡辩瓣撩到靛一缀交荔集，蔼黪舞模式分丰蓐裁是簧援 出该数据库中出现的高频序列。序列模式分析也要求用户输入最小鼹信度和晟 小支持度。 1 3 7 时间序列分析( t i m es e r i e s ) 时间序列预测，就怒对数值型数据，根据其历史数值，对其将来一段时间 内的数篷进毒亍预测。一般说亲，预测郄嚣要商足够长时翘的历史数摄积累，在 分析挖掘历史数据内在规律和趋势的凝础之上，才能有效地进行预测。时间序 裂分褥瓣内容毽撬：一；趋势粒镳差分辑，发瑷交纯趋势、彦列模式、裙篷冀序 列、偏差数据，如用于股市分析等。二：周期性分析，在随时间变化的数据 孛，等我周麓性交纯或者季节憔变证麓律。 1 4 聚类问题介绍 ：i 醺几年来，数据挖撅成为越来越热的一个研究方向，而聚炎( c l u s t e r i n g ) 撵为数据挖掇的主簧方法之一，也越来越g | 起人们豹关溶。所谓聚类，就是把 大量的d 维数据对象个) 聚集成k 个聚类( 肛 ) ，使同一聚类内对象的相 耘毪尽露麓最大，嚣不同聚类痰对象瓣穗 矬经尽骛达囊袋，l 、。魄就是滋，影袋 粱类之后，同一个浆类内对象具有很黼的相似性，而且与不属予该聚类的对象 有遥然的差辩( 都不籀骰) 。象类与势类稻眈，分类算法分析静是类潮己知的 数据集，而聚类算法则分析的是类别来知的数据。 蚺l ：学位沦义数据控掘中聚类算法i i i l _ 究i 仿真 聚必的输入是一缎未分类的记录，而且事先也不知道鼹分成几类，它通过 分析数据。根据一您的分类准则，合理划分记渌集合，从丽确定每个融录所属 静类别。不同豹聚类算法孛，用于接述相识幢的函数也有掰不同，有的采雳欢 氏距离躐骂氏距离，霄的采用向爨必角静余弦，也有的采用其他的度餐方法。 当预先不知道类溅数目，或糟用参数估计和非参数估计难以分辨不同类型 的类概率密度函数时，藏需要晨用聚类分析。有些聚类分丰厅簿法可以自动地确 定类羹熬数嚣k ，两不必竣预妥拜k 为藩提条馋，氇可浚绘定k 作为算法鲍终壹 条件。糟没有给定k ，那么如何在聚类过程中囱动地确定k ，这是聚类分析中 的一个关键问题。 采臻不嚣熬聚类方法，弱一令趟录集会霹毵有不弱翁鲻分缝象。聚类豹结 果与特征选取也有报大关系。例如对入进行聚炎：可以根据身高分类，可以根 据肤色分类，也可以根据年龄分炎。选取不同的特征，就会产生不同的结果。 现鸯斡凝粪算法大致可戳分热嚣大类：趔分聚类算法、爨次聚类算法、密 度型聚激算法、网格嬲聚类算法。下面将奔绍聚类闯题的基本概念、对聚类算 法的要求、相似性度爨方法、类的质心和半径镣进行介绍，并简单介绍备种聚 类算法。 1 4 1 聚类问题定义 文献 b e r o 对聚类翘题的定义如下：在数据空阉0 中，数攒集x 由许多数据 点( 或数糖对象) 缝成，数据点薯= 魄l ，一，嘞) a 。鼍的每个属性( 或特征、 或维度) x i l 既可以是数值型的，也可以是枚举型的。数据熊相当于摄一个 n x d 矩降。假设数据集中有个个对象五，i = 1 ，n 。浆类的最终题的是 整数豢繁菇麓努麓k 今分割，i = l , - - , k ，毽搿能有些对蒙不属于荏侮一个分 割，这些就是噪声c 。所有这贱分割与噪声的并集就是数据集x ，并且这 些分割之阃没有交集，即 x = c t u u e i u c 。，c 。心c ! = 囝。 这些分割e 就是聚类。 就终，氇寿大提如了模凝聚类虢愚想。在攫擞聚类中，每个霹象不秀仪j 鏊 予单个聚燕，而是戬不间的隶属度瘸子多个聚类。 博i ：学位沦文救据挖娴中聚兴，l = 法研究与仿真) 1 4 2 对聚类算法的要求 数据挖掘中对聚类算法的典型要求包括以下几点h k0 】： 1 ) 可伸缩性：许多算法对于较小的数据集能够很好地进行聚类，但是， 大型数据集中可能包含有几百万、几千万乃至更多的对象。虽然通过 抽样可以减少要处理的数据量，但是抽样会对聚类的结果带来影响甚 至会产生错误的结果。因此，可伸缩性好的聚类算法是很有必要的。 2 ) 能够处理混合型数据：许多算法是设计来对数值型( n u m e r i c a l ) 数据 进行聚类的。然而，在许多应用中待聚类的数据可能是二值型 ( b i n a r y ) 、枚举型( c a t e g o r i c a l 或n o m i n a l ) 、序数型( o r d i n a l ) ， 也可能是上述各种类型数据的混合。 3 ) 识别任意形状的聚类：很多聚类算法中采用了欧式距离( e u c l i d e a n d i s t a n c e ) 或街区距离( m a n h a t t a nd i s t a n c e ) 度量来确定聚类，而这些 距离度量倾向于识别大小与密度都相差不大的球形聚类。然而，聚类 可能是各种形状的，如线形、环形、凹形、及其他各种复杂不规则形 状。这就要求聚类算法要能够识别任意形状的聚类。 4 ) 在确定输入参数时需要的相关领域内的知识最少：许多聚类算法要求 用户输入一定的参数( 如类别数或一定的度量阈值等) ，而聚类结果 对输入的参数非常敏感。而这些参数往往很难确定，尤其对于高维数 据集更是如此。这不仅对用户带来了难题，而且还使聚类的结果难以 控制。 5 ) 能够处理噪声：现实世界的很多数据中都包含一些异常数据或错误数 据，有些聚类算法对这些数据非常敏感，并可能会产生错误的聚类结 果。 6 ) 对输入顺序不敏感：有些聚类算法对数据的输入顺序非常敏感，例 如，对于同一个数据集，用不同的顺序输入到某个算法中，就可能会 产生完全不同的聚类结果。 7 ) 对高维数据的处理：数据库或数据仓库中的数据可以有几十乃至成百 上千个维度或属性。许多聚类算法只擅长处理低维数据，如二维或三 维数据。在高维数据空间中，数据可能非常稀疏并且高度扭曲，因 此，高维空间中数据的聚类是一个很大的挑战。 8 ) 带有约束条件的聚类：在现实世界中的一些应用中，可能需要在一些 约束条件下来进行聚类分析。例如一个城市中自动柜员机位置的选 麟l ? 掌往论文 数撂挖掘孛聚炎舞洼掰究傣囊 糍，藏嚣簧在对家庭分露进撂聚类酵，考虑城带孛河漉、公路翘、每 个地区消费者的需求等约束条件。 9 ) 碟理勰毪秘可燕羧：焉产麓望聚炎熬缀暴是霹敬解释、瑟手璎辫劳其 有可用性。业就魁说，聚类可能需要与具体的谮义解释和具体应用结 会程起，其薅应用豹4 定基撂孵毙会影穗妥聚类算法翘选择。 l 。4 3 攘似性度爨方法 浆类时要根据对象之间的相似度把相似的对裂放入同个聚类中，丽爿i 相 骰的对象秘入不丽的聚类。所黻，裙钕度鲍度萤，直接决定着聚类的结袋。对 于数值型数据和枚举型数搬，度羹的方法也不相同。 对于数值类登的属性，有两种相似陡度量方法：鼹离相似度和角度稆似 度。距离相似度主黉有以下三种： 一 i ) 欧氏距离( e u c l i d e a n ) ：d s f ，) = 、1 一属1 2 d 2 ) 街区距离( m a n h a t t a n ) ：d i s t ( c t ，) = k 一 ；l 3 ) 明氏距离( m i n k o w s k y ) ： 嗷( 哪) ；豳磁卅r 毛扭l 有时也用两个向量夹角的余弦来表示它们的相似度，这就是角度相似度。 a b 。0 8 口2 h a i i i i b i i 对于枚举型数据，可以用相同属性值的数目作为相似性度量，也可以用相 同属性值的数日与不同属性值数鞭豹比德作为梗似性度楚。例擞，有鹾耪汽 车，g 。( s p o r t s ，b l u e ，g m ，f o u r d r i v e n ) ，c 2 = ( f a m i l y ，r e d ，g m ，t w o - d r i v e n ) ，它 们摆问属性馕的数爨为l ，薅不周壤性毽躬数曩怒3 。所以，若瘸提同属牲值 的数目作为相似往度量，那么它们的相似度s i r e ( c ；，c 2 ) = l ；若用相同属饿值的 数舅与不间属性饭数目豹比值作为鞠似性度量，那么它们的樱 娃度 曲 ( q ，c 2 ) = l 3 。 关予鞠曩冀程菠爨方法懿喜葶缨穷缨，谤参蔸文献 g r 0 2 。 辫 ：学位论文教妊挖掘巾聚类算法蟛究j 仿真 1 4 4 聚类的质心、半径、直径 在聚类过程中，鬻翅劐聚类豹矮心、半经、童径等壤念，它翻豹定义分别 如下： q 质，l , ( c e n t r o i d ) ：m = 型二 直径：d = f ( q m ) 2 v 可而 f ( p 一窜) 2 1 而可 其中，c 是聚类，p 翻g 是c 审豹对象，楚c 孛对象熬数基。 1 5 主要的聚类算法 主要魏蒙类算法霹羰分为激下尼耪：矮努蒙类、墨次蘩类、密疫型蒙类葙 网格型聚类。下面对遮些主要的聚类算法一一进行介绍，并进行简单的分析和 比较。 1 5 1 划分聚类( p a r t i t i o n i n gc l u s t e r i n g ) 划分聚类算法把数据点集分为个划分，每个划分作为个聚类。它般 麸一个耪娩划分开始，然爱逶过蘩笺豹控裁策醛，捷某个激粼丞数最魏织，孬 每个聚类由其质心来代表( k m e a n s 算法) ，绒者由该聚类中最靠近中心的一 个对象来代表( k m e d o i d s 算法) 。划分聚类算法收敛速度快，缺点在于它倾 向于识别髓形分布大小相近密度棚近熬聚类，不能发现分布形状比较复杂黔聚 类，它要求类巍数嚣k 霹淤合瑾壤髂诗，莠显秘始中心静选撵秘臻声对会对聚 类结果产生很大影响。 主要的划分聚类辫法有k m e a n s 、e m 、k m e d o i d s 、c l a r a 、c l a r a n s 等。下瑟对这些算法一一遴孬奔绥。 搏 ：学位论戈 数搬挖辅中聚类算法科究j 仿真 1 5 1 。1k - m e a n s 算法 k m e a n s 算法蓠先随机选择k 个对象，每个对象代表一个聚类的质心。对 于其余豹每一个对象，稷豢该霹象与各聚类缓，0 之蓠魏疑凑，凳宅分熬蠲毒之 最相似的聚类中。然后，计算每个聚类的新质心。重复上述过程，直到准则函 数会聚。通常采用的准则函数是平方误差准则函数( s q u a r e d e r r o r c r i t e r i o n ) ，郅 e = ：，p e c2。,ip-m,i e 是一个数据集中所有对象的误差平方和，p 是一个对象，埘，是聚炭的 q 原瞳即驴街。 k - m e a n s 聚类雾浚的具体步骤魏下： 1 ) 从数据集中选择k 个质心q 、c 2 、g 作为初始的聚类中心； 2 ) 把每个对象分配到与之最相似的聚合。每个聚合用其中所有对象的均 毽寒代表，“最耀议”裁是撞距离最小。对于每个点，找凄一个矮 心c ，使它与间的距离d ( ，c ，) 最小，并把分配到第，组： 3 ) 把所有的点都分配到相应的组之后，熬新计算每个级的质心c ； 4 ) 缀环撬行第2 ) 步移第3 ) 步，壹至l 数攥翡翅分不褥发生交纯。