（通信与信息系统专业论文）聚类分析中若干关键技术及其在电信领域的应用研究.pdf

北京邮电大学博士学位论文 聚类分析中若干关键技术及其在电信领域的应用研究 摘要 数据库中的知识发现( 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 ，k d d ) 是从 数据集中识别出有效的、新颖的、潜在有用的，以及最终可理解的模式 的非平凡过程。数据挖掘是k d d 过程中的核心步骤，它的目的是运用 特定的数据挖掘算法，从数据库中提取出用户感兴趣的知识，并以一定 的方式表示出来，如树、表、规则和图等。 作为主要的数据挖掘任务之一，聚类分析是将物理或抽象对象的集 合分组成为由类似的对象组成的多个类的过程。这一过程的准则是最大 化类内对象的相似性，同时最小化类间对象的相似性。本文重点研究了 聚类分析中的若干关键技术和算法，同时探讨了它们在电信领域的应用 可能。 第一章对数据挖掘技术进行概述，主要讨论了知识发现的基本概念、 数据挖掘的产生、发展以及数据挖掘算法可以实现的功能，主要包括： 概念类描述、分类和预测、聚类分析、频繁模式关联规则挖掘、孤立 点分析以及序列和时序分析等。同时，文中还给出了数据挖掘技术在电 信领域的应用。最后阐述了本文研究的主要创新点和组织结构。 在第二章中，首先介绍了聚类分析的基本概念，包括聚类的定义， 聚类算法有效性的评价准则，以及对聚类分析算法的典型要求；然后讨 论了几类主要的聚类分析算法以及它们各自的代表算法，包括基于划分 的算法、基于层次的算法、基于密度的算法、基于网格的算法和基于模 型的算法。 第三章首先分析了聚类中心点初始化的必要性，以及现有的三类聚 类中心点初始化算法：在此基础上，融合了基于网格的聚类算法和基于 密度的聚类算法的基本思想，提出了基于复合近邻的聚类中心点初始化 算法c n i c c 和基于方向指针的聚类中心点初始化算法d p 。 北京邮电大学博士学位论文 第四章重点研究了高维数据的子空间聚类算法。文中首先给出了高 维数据的实例，并从三个方面分析了它们的特点，探讨了高维数据对传 统的聚类算法所带来的影响；在此基础上，研究了现有的可交叠子空间 聚类算法、不可交叠子空间聚类算法和其它类型的子空间聚类算法，分 析了它们各自的优缺点。结合图论中的极大团理论，提出了基于极大团 的高维子空间聚类算法：摒弃了传统的类a p d o r i 搜索策略，提出了采用 属性聚类的高维子空间聚类算法，在真实数据集和人工数据集上的实验 结果证明了算法的有效性。 第五章研究了孤立点检测的方法。首先介绍了现有的几类孤立点检 测方法：基于统计的方法、基于深度的方法、基于偏差的方法、基于距 离的方法和基于密度的方法，分别讨论了它们各自的优缺点。在此基础 上，提出了两种在特征空间中完成孤立点检测问题的方法：基于双半径 密度差异的孤立点检测算法和采用距离分布聚类的孤立点检测方法。前 者通过考察数据空间内任一点的双邻域半径与邻域半径内的密度差异来 有效识别孤立点，同时采用抽样技术进一步提高算法效率；后者将孤立 点检测问题重定位在转换空间中，通过考察距离分布差异获取孤立点。 实验结果证明了这两种方法对孤立点数据的实际检测效果。 第六章主要对约束聚类问题进行了研究。以多种形式所表现的约束 能够指导聚类过程，影响聚类结果。文中首先介绍了约束条件的不同类 型，其次分析了约束条件给聚类过程所带来的收益及问题，指出了约束 条件所引起的失真是影响聚类精度的根本原因。在此基础上，提出了最 小化失真的约束聚类算法m d k m 。 以文中所提出的新算法为基础，第七章中给出了聚类分析技术在电 信帐务数据上进行客户关系管理中的应用实例。 第八章对论文进行了总结，介绍了本文的主要内容及主要贡献，并 对进一步的研究和需要进行的完善进行了总结。 关键词：数据挖掘、聚类分析、聚类中心、子空间聚类、孤立点检测、 约束聚类 北京邮电大学博士学位论文 r e s e a r c h0 nc l u s l l 删n ga n a iy s i sa n dn 忑a p p u c _ n o n si n t e l e c o m 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 ( k d d ) i sas p e c i a lp r o c e s s t o e x t r a c t v a l i d , n o v e l ，u s e f u lp o t e n t i a l l y a n du n d e r s t a n d a b l e u l t i m a t e l y k n o w l e d g eo rp a t t e r n sf r o md a t a b a s e d a t am i n i n gi st h ee s s e n t i a ls t e po f k d d ，w h e r ei n t e l l i g e n tm e t h o d sa r ea p p l i e di no r d e rt oe x t r a c td a t ap a t t e r n s o ni 1 舱r i n t e r e s t ，e x p l a i na n dv i s u a l i z ed a t am i n i n gr e s u l t sb yk n o w l e d g e r e p r e s e n t a t i o nt e c h n i q u e s ，s u c ha st r e e s ，t a b l e s ，r u l e s ，g r a p h s c l u s t e ra n a l y s i si so n eo ft h em o s ti m p o r t a n tf u n c t i o n so fd a t am i n i n g , a n dc l u s t e r i n gi st h ep r o c e s so fg r o u p i n gas e to fp h y s i c a lo ra b s t r a c to b j e c t s i n t oc l a s s e so fs i m i l a ro b j e c t s ac l u s t e ri sac o l l e c t i o no fd a t ao b j e c t st h a ta r e s i m i l a rt oo n ea n o t h e rw i t h i nt h es a l e 吧c l u s t e ra n da r ed i s s i m i l a rt ot h e o b j e c t s i no t h e rc l u s t e r s 1 n h i st h e s i sf o c u s e so n k e yt e c h n i q u e sa n d a l g o r i t h m so fc l u s t e ra n a l y s i sa n dt h e i ra p p l i c a t i o n si nt e l e c o r m c h a p t e ro n er e v i e w st h ec o n t e n to fd a t am i n i n g6 e l d i tf o c u s e so nt h e b a s i cc o n c e p to fk n o w l e d g ed i s c o v e r ya n dt h eb i r t h , e v o l u t i o no fd a t am i n i n g f i r s t l y t h e nt h em a i nf u n c t i o n so fd a t am i n i n ga r ed i s c u s s e d ，i n c l u d ec o n c e p t o rc l a s sd e s c r i p t i o n , c l a s s i f i c a t i o na n dp r e d i c t i o n ，c l u s t e ra n a l y s i s ，f r e q u e n t p a t t e r no ra s s o c i a t i o nr u l ea n a l y s i s ，o u t l i e ra n a l y s i sa n ds e q u e n c eo rt i m e s e r i e s a n a l y s i s m o r e o v e f ，t h ea p p l i c a t i o n s o fd a t a m i n i n gt e c h n i q u ei n t e l e c o ma r ep r o p o s e d f i n a l l y , t h em a i nc o n t e n ta n da r c h i t e c t u r eo ft h i st h e s i s i sa l s od e s c r i b e d t h eb a s i cc o n c e p to fc l u s t e ra n a l y s i si sd i s c u s s e di nc h a p t e rt w o ，i n c l u d e 北京邮电大学博士学位论文 t h ed e f m i t i o no fc l u s t e r a n a l y s i s ，m a i n e v a l u a t i o nc r i t e r i aa n db a s i c r e q u i r e m e n to fc l u s t e r i n ga l g o r i t h m t h e nv a r i o u sa l g o r i t h m sa n dt h e i rm o s t r e p r e s e n t a t i v ea l g o r i t h m sa r ep r o p o s e d ：p a r t i t i o n i n gm e t h o d , h i e r a r c h i c a l m 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 d m e t h o d c h a p t e r t h r e ef i r s ts t u d i e st h e r e q u i r e m e n t s o fc l u s t e rc e n t e r s i n i t i a l i z a t i o na n dt h ec u r r e n ta l g o r i t h m s t h e nt w om e t h o d sf o ri n i t i a l i z i n g c l u s t e rc e n t e r sb a s e do nc o m p o s i t en e i g h b o ra n dd i r e c t i o np o i n t e ra r e p r o p o s e d , w h i c hi n t e g r a t eb o t hg r i d b a s e d a n dd e n s i t y b a s e d c l u s t e r i n g a l g o r i t h m c h a p t e r f o u r i n v e s t i g a t e ss u b s p a c ec l u s t e r i n ga l g o r i t h m s f o r h i g h - d i m e n s i o n a ld a t a f i r s t , t h ei n s t a n c e so fh i g h - d i m e n s i o n a ld a t aa r e p r o p o s e d t h e i rc h a r a c t e r i s t i ca n dt h ei n f l u e n c eo nt r a d i t i o n a lc l u s t e r i n g m e t h o d sa r es t u d i e d t h e nt h r e e a p p r o a c h e so fs u b s p a c 2c l u s t e r i n g a r e i n t r o d u c e d ：o v e r l a p p i n gs u b s p a c ec l u s t e r i n g ，n o n - o v e r l a p p i n gs u b s p a c e c l u s t e r i n g a n do t h e r s u b s p a c ec l u s t e r i n g m o r e o v e r , t w o m e t h o d sf o r s u b s p a c ec l u s t e r i n ga r ep r o p o s e d o n ei sb a s e do nt h et h e o r yo fm a x i m u m c l i q u e ；t h eo t h e ri sb a s e do na t t r i b u t ec l u s t e r i n g , a n di td i s c a r d st h es e a r c h s t r a t e g yl i k ea p r i o r i e x p e r i m e n t so nb o t hr e a la n ds y n t h e s i sd a t a s e t sp r o v e t h ev a l i d i t y c h a p t e rf i v em a k e sr e s e a r c h e so no u t l i e rd e t e c t i o na l g o r i t h m s f i r s t , c u r r e n to u t l i e rd e t e c t i o nm e t h o d sa r er e v i e w e d ，i n c l u d i n gt h es t a t i s t i c a l a p p r o a c h ，t h ed e p t h - b a s e da p p r o a c h ，t h ed e v i a t i o n - b a s e da p p r o a c h ，t h e d i s t a n c e - b a s e da p p r o a c ha n dt h ed e n s i t y b a s e da p p r o a c h t h ec h a r a c t e r i s t i c o ft h o s ea l g o r i t h m si sd i s c u s s e d t h e nt w om e t h o d sf o ro u t l i e rd e t e c t i o ni n f e a t u r es p a c ea r ep r o p o s e d ：t h eo u t l i e rd e t e c t i o nm e t h o db a s e do nd i f f e r e n c e o fd o u b l er a d i u sd e n s i t ya n dt h em e t h o dt h r o u g hd i s t a n c ed i s t r i b u t i o n c l u s t e r i n g t h ef o r m e rd e t e c t so u t l i e rb yc o m p a r i n gt h ed e n s i t yd i f f e r e n c eo f t h ed o u b l er a d i u sa n dt h er a d i u so f e a c hp o i n ti nd a t as p a c e ，w h i l es a m p l i n g t e c h n i q u e sa r eu s e dt of u r t h e ri m p r o v ee f f i c i e n c y ；t h el a t t e rr e d e f i n e st h e p r o b l e mb yc l u s t e r i n gi nt h ed i s t r i b u t i o nd i f f e r e n c es p a c er a t h e rt h a nt h e o r i g i n a lf e a t u r es p a c e t h ee f f e c to ft h et w om e t h o d sh a sb e e nv a l i d a t e db y 北京邮电大学博士学位论文 e x p e r i m e n t s c h a p t e rs i xm a k e sr e s e a r c h e so f fc o n s t r a i n e dc l u s t e r i n g c o n s t r a i n t so f v a r i o u sf o r m sc o u l dg u i d e c l u s t e r i n gp r o c e s s a n d i m p r o v ec l u s t e r i n g p e r f o r m a n c e b e s i d e so fd i f f e r e n tt y p e so fc o n s t r a i n t s , t h ea d v a n t a g ea n d d i s a d v a n t a g eo fa d d i n gc o n s t r a i n t st oc l u s t e r i n ga r ed i s c u s s e d t h e nt h e c o n c l u s i o nt h a td i s t o r t i o nc a u s e db yc o n s t r a i n ts e t si st h er a d i c a lr e a s o nt o i n f l u e n c eo f ft h ea c c u r a c yo fc o n s t r a i n tc l u s t e r i n ga l g o r i t h m si sd e p i c t e d a n d a l s o ，m i n i m i z e dd i s t o r t i o nm e t h o df o rk - m e a n si sp r e s e n t e d b a s e do nt h en e wa i g u r i t h m si nt h i st h e s i s ，c h a p t e rs e v e nf o c u s e so nt h e a p p l i c a t i o n s o fc l u s t e r a n a l y s i s i nt e l e c o mc u s t o m e r r e l a t i o n s h i p m a n a g e m e n t c h a p t e re i g h tm a k e sac o n c l u s i o no ft h er e s e a r c ha n dp u t sf o r w a r dt h e f i l t i l r er e s e a r c hi nt h i sf i e i d k e yw o r d s ：d a t am i n i n g , c l u s t e ra n a l y s i s , c l u s t e rc e n t e r , s u b s p a c e c l u s t e r i n g , o u t l i e rd e t e c t i o n , c o n s t r a i n e dc l u s t e r i n g 北京邮电大学博士学位论文 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成 果尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意 申请学位论文与资料若有不实之处，本人承担一切相关责任 本人签名：唑 e i 剪i ；型! ：丝 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学学校有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学 校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段 保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论文 注释：本学位论文不属于保密范围，适用本授权书 本人签名： 导师签名：i t , l l ：幽：垒兰 北京邮电大学博士学位论文 第一章绪论 本章首先阐明了本文所选课题的研究背景及研究价值，对数据挖掘技术进行了 概述，主要讨论了知识发现的基本概念、数据挖掘的产生、发展以及数据挖掘技术 可以实现的功能，主要包括：概念，类描述、分类和预测、聚类分析、频繁模式，关联 规则挖掘、孤立点分析、序列分析和时序分析等。此外，本章还论述了数据挖掘技 术在电信行业的重要应用，包括数据多维分析、异常模式识别、以及聚类和分类技 术在电信领域的应用。最后总结了本文的主要研究工作和创新点。 1 1知识发现的基本概念 在人类从工业社会向信息社会演进的今天，知识正在成为创新的核心，知识创 新成为知识经济发展的最主要的动力源泉。从数据到信息，从信息到知识已经成为 耳熟能详的格言。数据是事物、概念或指令的一种形式化的表示形式，以适用于人 工或自然方式进行通信、解释或处理：信息是根据表示数据所用的约定，赋予数据 的意义；而知识是人类在实践的基础上产生又经过实践检验的对客观实际的可靠反 映。在过去的数十年中，存储数据的爆炸性增长业已激起对新技术和自动信息处理 工具的需求，以便将海量的数据转化为有用的信息和知识知识发现( k d d k n o w l e x l g cd i s c o v e r y i nd a t a b a s c ) 正是在这种背景下应运而生的一个技术体系。 在1 9 8 9 年8 月美国底特律召开的第十一届人工智能联合会议的专题讨论会上首 次出现k d d 这个术语，f a y y a d 指出。k d d 是从数据集中识别出有效的、新颖的、 潜在有用的，以及最终可理解的模式的非平凡过程”【1 1 其中，数据集是一组事实 f ( 如关系数据库中的记录) 模式是一个用语言l 来表示的一个表达式e ，它可用来 描述数据集f 的某个子集f e ，e 作为一个模式要求它比对数据子集f e 的枚举要简单 ( 即所用的描述信息量要少) 。过程在k d d 中通常是指多阶段的处理，涉及数据准备、 模式搜索、知识评价以及反复的修改求精；该过程要求是平凡的，意思是要有一定 程度上的智能性、自动性( 仅仅给出所有数据的总和不能算是一个知识发现过程) 。有 效性是指发现的模式对于新的数据仍保持有一定的可信度。新颖性要求发现的模式 应该是新的。潜在有用性是指发现的知识将来有实际效用，如用于决策支持系统里 可提高经济效益。最终可理解性要求发现的模式能被用户所理解，目前它主要是体 现在所发现知识的简洁性上。有效性、新颖性、潜在有用性和最终可理解性综合在 一起成为兴趣性【2 1 。 北京邮电大学博士学位论文 t h = f 知识发现是一门受到来自各种不同领域的研究者关注的交叉性学科，因此 导致了它有很多种不同的术语名称。除了k d d 外，还有如下几种名称： 。数据挖 掘一( d a t am i n i n g ) 、“知识抽取”( k n o w l e d g ee x t r a c t i o n ) 、“信息发现”( i n f o r m a t i o n d i s c o v e r y ) 、。智能数据分析”( i n t e l l i g e n t d a t aa n a l y s i s ) 、“探索式数据分 析一( e x p l o r a t o r y d a t aa n a l y s i s ) 、。信息收获”( i n f o r m a t i o nh a r v e s t i n g ) 和“数据考 古”( d a aa r c h e o l o g y ) 等等。 许多人把数据挖掘视为k d d 的同义词，而国际上流行的观点则认为数据挖掘只 是知识发现过程中的一个基本步骤，知识发现的过程如图1 - - 1 所示，由以下步骤组 成【2 】： 图1 - - 1 知识发现过程示意图 1 数据准备 数据准备可分为三个子步骤：数据选取抽样、数据预处理和数据转换。数据选 取抽样的目的是确定发现任务的操作对象，即目标数据，它是根据用户的需要从原 始数据库中抽取的一组数据。数据预处理一般包括消除噪声、推导计算缺值数据、 2 北京邮电大学博士学位论文 消除重复记录、完成数据类型转换等。数据转换的主要目的是消减数据维数又称降 维，即从初始特征中找出真正有用的特征以减少数据挖掘时要考虑的特征个数。 2 数据挖掘 数据挖掘阶段首先要确定挖掘的任务或目的是什么，如数据归纳、分类、聚类、 关联规则发现或序列模式发现等确定了挖掘任务后，就要决定使用什么样的挖掘 算法。在选择算法时一般考虑两个因素：一是不同的数据有各自的特点，因此需要 用与之适宜的算法来建模：二是用户或实际运行系统的要求，例如用户所期望的知 识类型 3 结果解释和评估 数据挖掘阶段揭示出来的模式，经过用户或机器的评估，可能存在冗余或无关 的模式，需要将其剔除；也有可能该模式不满足用户的要求，这时则需要整个发现 过程退回到发现阶段之前，如重新选取数据、采用新的数据变换方法、设定新的数 据挖掘参数值，甚至换一种挖掘算法。另外，k d d 由于最终是面向人类用户的，因 此可能要对发现的模式进行可视化，或者把结果转换为用户易懂的另一种表示 这里所说的知识发现，不是要发现放之四海而皆准的普遍真理，也不是要发现 不为人知的自然科学定理和数学理论，更不是所谓的机器定理证明。知识发现过程 中所产生的知识都是相对的，是具有特定前提和约束条件、面向特定领域的，同时 要求是易于被用户所理解的知识表示。因此，知识发现过程不仅追求技术上的合理 性和科学性，同时要考虑实际的应用效果 1 2数据挖掘的产生 任何技术的产生总是有一定的技术背景。数据挖掘技术的提出和被普遍接受缘 于计算机及周边技术的发展为其提供了研究和应用的技术基础。历经了十几年的发 展，包括基于统计学，人工智能等在内的理论与技术性成果已经被成功地应用到商 业分析和处理中这些应用从某种程度上为数据挖掘技术的提出和发展起到了极大 地推动作用。数据挖掘系统的核心模块技术和算法都离不开这些理论和技术的支持。 从某种意义上讲，这些理论本身发展和应用为数据挖掘提供了有价值的理论和应用 积累。例如数理统计是一个有几百年发展历史的应用数学学科，至今仍然是应用数 学中最重要、最活跃的学科之一。如今强大有效的数理统计方法和工具，已成为信 息咨询业的基础。 另一方面，随着数据库技术的发展和i n t c r n c t 的迅速普及，人们所面对的数据量 3 北京邮电大学博士学位论文 急剧增长，无论商业、企业、科研机构或政府部门都积累了大量的、以不同形式存 储的数据资料。自二十世纪六十年代以来，数据库和信息技术已经系统地从原始的 文件处理演化到复杂的、功能强大的数据库系统。七十年代以来，数据库系统的研 究和开发已经从层次和网状数据库系统发展到开发关系数据库系统、数据建模工具、 索引和数据组织技术。八十年代中期以来，数据库技术的特点是广泛接受关系技术， 研究和开发新的、功能强大的数据库系统。这些数据库使用了先进的数据模型，如 扩充关系模型、面向对象模型、对象一关系模型和演绎模型：包括空间的、时间的、 多媒体的、主动的和科学的数据库、知识库、办公信息库在内的面向应用的数据库 系统百花齐放，涉及分布性、多样性和数据共享问题被广泛研究。然而，在拥有海 量数据的同时对我们对数据中所蕴涵的信息和知识缺乏充分的理解和应用，依靠传 统的数据库对数据进行查询，检索等分析手段不能帮助用户从数据中提取带有结论 性的有用信息，已经远不能满足数据分析和处理的要求。虽然基于数据仓库的联机 分析处理 3 4 5 6 1 1 7 1 1 8 1 1 9 1 0 l a p ( o n - a n a l y s i sp r o c e s s ) 技术具有总结、概括和聚 集的功能，支持多维分析和决策，但它不能进行更深层次的数据分析，数据库中蕴 含的丰富知识，得不到充分的发掘和利用。此外，当前的专家系统技术通常依赖用 户或者领域专家人工地将知识输入数据库。而这一过程不仅常有错误和偏差，而且 耗时费力因此，人们迫切需要更强有力的数据分析方法和技术以解决。数据丰富 而信息贫乏”这一迫在眉睫的尴尬问题，以帮助人们从繁杂的数据中找到有用的信 息，发现其中存在的关系和规则，实现决策的智能化和自动化，从而带来商业上巨 大的价值信息。利用挖掘工具进行数据分析，可以发现重要的数据模式，对商务决 策、知识库、科学和医学研究做出了巨大贡献。数据和信息之问的鸿沟要求系统地 开发数据挖掘工具，将数据坟墓转换成知识。金块” 总的来说。数据挖掘就是从数据中提取人们感兴趣的知识的过程，这些知识是 隐含的、有效的、新颖的、潜在有用的以及最终可理解的模式。数据挖掘充分利用 了机器学习、数理统计、人工智能、模糊逻辑、神经网络、进化计算等理论和方法， 它是应用需求推动下多种学科融合的结果【1 0 】。从商业角度来看，数据挖掘可以描述 为：按企业既定业务目标，对大量的企业数据进行探索和分析，揭示隐藏的、未知 的或验证已知的规律性，并进一步将其模型化的先进有效的方法。 1 3数据挖掘的功能 数据挖掘功能用于指定数据挖掘任务中需要寻找的模式类型从数据分析的角 4 北京邮电大学博士学位论文 度来看，数据挖掘目标一般分为两种：描述式数据挖掘和预测式数据挖掘。描述式 数据挖掘以简洁概要的方式描述数据，并刻画数据库中数据的一般性特征；预测式 数据挖掘则对当前数据进行分析，建立相对应的一个或一组模型并试图预测新数 据集的行为。一般来说，为了适应不同用户的相异需求，数据挖掘系统应能够挖掘 多种类型的模式。数据挖掘功能以及它们可以发现的模式类型介绍如下1 1 1 l ： 1 3 1 概念类描述 用户常常需要抽象的有意义的描述，因此用汇总的、简洁的、精确的方式描述 每个类或概念是必要的。将数据和类或概念相关联，经过归纳的抽象概念描述能够 概括大量的关于类的信息这种描述被成为概念类描述( c o n c e p t c l a s sd e s c r i p t i o n ) 描述可以通过如下三种方式完成：1 1 数据特征化( d a t ac h a r a c t e r i z a t i o n ) ，是一般地汇总 所研究类的过程：劲数据区分，是将所研究类与一个或多个比较类进行比较的过程； 3 ) 数据特征化和比较，是上述两个过程的有机结合 数据特征的输出可以有多种形式，例如饼图、条形图、曲线、多维数据立方体 和包括交叉表在内的多维表数据区分的输出形式类似于特征描述，所不同的是， 区分描述中包含比较度量。 1 3 2 分类和预测 分类是数据挖掘的一项重要技术，目前在商业上的应用最为广泛分类的目的 是提出一个分类函数或分类模型( 常常被称为分类器) ，该模型能把数据库中的数据 项映射到给定类别中的某一个它通常是一个两步的过程，第一步，建立一个模型， 描述预定的数据类集和概念集。通过分析由属性描述的数据库元组来构造模型。假 定每个元组属于一个预定义的类，由一个称作类标号属性的属性来确定对于分类， 数据元组也称作样本、实例或对象为建立模型而被分析的数据元组形成训练数据 集。由于提供了每个训练样本的类标号，该步也称作有指导的学习第二步，使用 模型进行分类首先评估模型的预测准确率，要达到这一目的可采用多种方法。模 型在给定测试集上的准确率是正确被模型分类的测试样本的百分比。对于每个测试 样本，将已知的类标号与该样本的学习模型类预测比较。如果认为模型的准确率可 以接受，就可以用它对类标号未知的数据元组组成对象进行分类。 预测和分类是两种不同的概念，预测是构造和使用模型评估无标号样本类，或 评估给定样本可能具有的属性值或值区间。在这种观点下，分类和回归是两类主要 的预测问题。预测的目的是从历史数据记录中自动指导出对给定数据的推广描述， 北京邮电大学博士学位论文 从而能对未来数据进行预测。和回归方法不同的是，分类的输出是离散的类别值， 而回归的输出则是连续数值。 1 3 3聚类分析 聚类是根据数据的不同特征，将其划分为不同的簇的过程。它的目的是使得属 于同一个类别的个体之间的距离尽可能的小，而不同类别上的个体问的距离尽可能 的大。聚类方法包括统计方法、机器学习方法、神经网络方法和面向数据库的方法。 在统计方法中，聚类是多元数据分析的三大方法之一( 其它两种是回归分析和判 别分析) 。它主要研究基于几何距离的聚类，如欧氏距离、明考斯基距离等。传统的 统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、 有重叠聚类和模糊聚类等。这种聚类方法是一种基于全局比较的聚类，它需要考察 所有的个体才能决定类的划分，因此它要求所有的数据必须预先给定，而不能动态 增加新的数据对象。聚类分析方法不具有线性的计算复杂度，难以适用于数据库非 常大的情况。 在机器学习中聚类称作无监督或无教师归纳，因为和分类学习相比，分类学习 的例子或数据对象有类别标记，而要聚类的例子则没有标记需要由聚类学习算法 来自动确定在神经网络中，有一类无监督学习方法一自组织神经网络方法，如 k o h o n e n 自组织特征映射网络、竞争学习网络等等。在数据挖掘领域里，见报道的 神经网络聚类方法主要是自组织特征映射方法，m m 在其发布的数据挖掘白皮书中 就特别提到了使用此方法进行数据库聚类分割【2 1 1 3 4频繁模式关联规则挖掘 关联分析( a s s o c i a t i o na n a l y s i s ) 用来发现关联规l i j ( a s s o c i a t i o nr u l c l ，这些规则展示 属性一值频繁地在给定数据集中一起出现的条件。关联规则挖掘的研究是近几年研 究较多的数据挖掘方法，在数据挖掘的各种方法中的应用也最为广泛关联规则发 现的主要对象是事务数据库，其中针对的应用是售货数据。也称为货篮数据。在数 据库的知识发现中，关联规则就是描述这种在一个事务中物品之间同时出现的规律 的知识模式更确切的说，关联规则通过量化的数字描述物品甲的出现对物品乙的 出现有多大的影响0 2 。 1 3 j 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致。这些 数据对象被称；( o u t l i e r ) 大部分数据挖掘方法将孤立点视为噪声或异常而过 6 北京邮电大学博士学位论文 滤。然而，在一些应用中，罕见的事件可能比正常出现的模式更令人感兴趣，如欺 诈检测问题中孤立点数据分析称作孤立点挖掘( o u t l i e rm i n i n g ) 孤立点探测和分析 是一项重要的数据挖掘任务，被称为孤立点挖掘1 n 1 1 1 3 1 1 1 4 1 1 1 5 1 。孤立点挖掘有着广 泛的应用，它不仅能够用于欺诈检测，例如探测不寻常的信用卡使用或电信服务。 此外，它还可以在市场分析中可用于确定极低或极高收入的客户的消费行为，或者 在医疗分析中用于发现对于多种治疗方式的不寻常反应。 详细的孤立点分析方法见第五章 1 3 6序列分析和时序分析 序列分析和时序分析是用来说明数据中的序列信息和时间相关的序列的分析 【1 5 1 1 1 6 1 1 1 7 】序列数据库是指由有序事件序列组成的数据库，它可以有时问标记也 可以没有时间标记。例如，w e b 页面遍历就是一种序列数据时序数据库是指由随 时间变化的序列或事件组成的数据库，序列值通常是在等时间间隔测得的数据。时 序数据库的应用很广泛，例如，股票市场的每日波动，化学实验中按等时间间隔测 得的反应物的状态数据，气象观测中的风速的变化数据等等时序数据库也是一种 序列数据库 关于序列数据库和时序数据库的挖掘，主要包括趋势分析，相似性搜索，与时 间有关数据的序列模式挖掘和周期模式挖掘等。趋势分析一般包括对以下四种主要 的变化或成分的分析：长期或趋势变动( 1 0 n g - t e r mo f t r e n dm o v c m e d t ) 、循环变动或循 环变化( c y c l i cm o v e m e n to rc y c l i cv a r i a t i o n ) 、季节性变动或季节性变化( s e a s o n a l m o v e m e n to rs e a s o n a lv a r i a t i o n ) 和非规则或随机变动( i r r e g u l a ro rr a n d o mm o v e m e n t ) 通过对它们的系统分析，人们可以在较合理的情况下，制定出长期或短期的预测。 通常数据库查询是要找出符合条件的精确数据，而相似性搜索与之不同，它需要找 出与给定的查询序列最接近的数据序列，包括子序列匹配( s u b s c q u e n m a t c h i n g ) 和整 体序列匹配( w h o l es e q u e n c em a t c h i n g ) 。子序列匹配是找出与给定序列相似的所有数 据序列，而整体序列匹配是要找出彼此间相似的序列时序分析中的相似性搜索已 经在股票数据分析、医疗诊断分析等领域得到广泛的应用序列模式挖掘是指挖掘 相对时间或其他模式出现频率高的模式。由于很多商业交易，电传记录和天气数据 等都是时间序列数据，序列模式挖掘已经应用于在针对目标市场、客户吸引和气象 预报等的数据分析中周期分析是指对周期模式的挖掘，即在时序数据库中找出重 复出现的模式。周期模式挖掘可以应用于诸如季节，潮汐和行星轨道等具有周期性 的领域中。 北京邮电大学博士学位论文 1 4数据挖掘在电信行业的重要应用 随着电信技术的飞速发展以及三网融合的大势所趋，电信运营商提供给消费者 的不再是单一的传统本地和长途话音业务。数字化语音、传真、无线通信、图像、 电子邮件、计算机和网络数据传输以及其他形式的数据传输，都是当今电信网络服 务内容的组成部分。电信网、计算机网和广播电视网的三网融合，使电信服务从内 容到形式都发生了翻天覆地的变化。随着大量的通信和计算技术被人们广泛关注、 研究以及引进，电信市场日益饱和，运营商之间的竞争也日渐激烈。在这种形势下， 经营决策者迫切需要一种技术，可以帮助使用者更加深刻的理解电信业务、识别电 信客户消费模式、捕捉欺诈行为、充分利用资源以及提高服务质量。数据挖掘在电 信领域的应用主要包含以下几个方面 1 1 1 , 1 4 1数据多维分析：统计与查询 电信数据本身具有多维性的特点，单个分析用数据表所包含的维度甚至达到上 千个对此类数据进行多维分析有助于深入洞察用户行为、数据通信情况、系统负 载、资源使用等等。例如，分析人员希望经常查看有关呼叫源、呼叫目标、呼叫量 和使用模式等方面的图表。出于处理效率和灵活性的考虑，运营商的计费管理系统 通常由多个零散的低维数据表组成，这种情况下，手工利用s o l 语句进行逻辑整合 非常困难。数据收集及存储技术发展到今天，电信数据以数据仓库的形式存储，管 理者能够方便的进行o i a p 分析和其它可视化工具的应用o l a p 允许用户以交互 方式浏览数据仓库内容，并对其中数据进行多维关联分析，且能及时地从变化和不 太完整的数据中提取出与企业经营活动密切相关的信息。例如：0 u ”能对不同时期、 不同地域的商业数据中变化趋势进行对比分析。 1 4 2 异常模式识别：探测电信欺诈 在中国，电信行业的欺诈行为每年给运营商带来数以亿计的损失因此，识别 潜在的欺诈者和他们的非典型的使用模式，检测想利用营销活动优惠套取业务终端 的行为，以及发现需要引起注意的异常模式，都是非常重要的。利用国际长途结算 费用的三天时延在月底拨打然后丢弃s “卡、从被恶意篡改过的自动拨出设备( 如 传真机) 发出的周期性呼叫、五月和十月漫游费用周期性突跃等，这些都是异常模 式的典型行为表现。通过多维分析、聚类分析和孤立点检测，可以发现许