（信号与信息处理专业论文）可信关联规则挖掘算法研究.pdf

j鬟耋重琴；，蚌弘一 s t u d yo fm i n i n ga l g o r i t h m sf o r c r e d i b l ea s s o c l t i o nr u l e s b y b ox i a o s u p e r v i s o r ：p r o f j u ng u o p i 己e s e n t e dt ot h ef a c u i t y o ft h eu 聪e r s n ”yo fp o s t s & t e l e c o m m ，n i c a t i o n s i nc a n d i d a c yf o rt h ed e g r e e o fd o c t o ro fp h i l o s o p h y r e c o m m e n d e df o ra c c e p t a n c e b y t h es c h o o l o f i n f o r n 【6 i = r i o na n dc o m 仉玲i i c j 6 i t l 0 ne _ n g i n e e r i n g a p r i l2 0 0 9 产0、1j 创新性声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 宣遮日期：苎竺f ：! ： 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。 本学位论文不属于保密范围，适用本授权书。 本人签名：盘遗 剔醛轹j 牛l 日期：坐2 ：5 ：! 竺 日期： 鲨里2 i ：! 北京邮电大学博上学位论文摘要 可信关联规则挖掘算法研究 摘要 关联规则挖掘是数据挖掘领域中一个重要研究内容。传统的关联 规则挖掘算法大都基于支持度一置信度框架，利用支持度去除非频繁 项集，利用置信度得到较为有效的关联规则。对支持度分布严重倾斜 的数据集挖掘时，人们发现现有算法无法选择合适的支持度阈值。若 将最小支持度设置较高，会遗漏支持度较低但令人感兴趣的规则，若 设置较低，则挖掘结果会含有大量虚假规则，对用户没有实际意义。 本论文针对上述问题，围绕如何得到可信有效的关联规则展开研 究，创新点和主要工作如下： 1 提出可信关联规则的概念 可信关联规则中各个项目的支持度处于同一数量级，一个项目的 出现很强的暗示了规则中其他项目也会出现，甚p 规则中的各个项目在 很大程度上是同现的。挖掘这种规则时，可以忽略支持度阈值，因此 可同时得到频繁模式和非频繁模式。对于可信关联规则的兴趣度量， 本文提出基于可信度的度量，并引入基于距离测度的度量及h 置信度 等。实验结果表明，可信关联规则在很多数据集中都会存在，其可信 程度远远大于传统的关联规则，可广泛应用到诸多领域。 2 提出基于极大团挖掘可信关联规则的m a x c l i q u e m i n i n g 算法 m a x c l i q u e m i n i n g 算法采用邻接矩阵产生2 项可信集，不需要对 数据库进行多次扫描，就能利用极大团思想产生所有可信关联规则， 提高时间性能。该算法可以挖掘基于可信度、提升度、余弦度量以及 相关度度量的可信关联规则，对于不同度量，算法只在生成2 项可信 集时有所区别，后续挖掘过程完全一致。实验结果表明，本算法在倾 斜支持度分布的数据集中挖掘可信关联规则具有较高的效率和准确 性。 3 提出统一挖掘超团模式和极大超团模式的h h c p g r o w t h 算法 超团模式和极大超团模式都是基于h 置信度度量的可信关联规 北京邮电大学博士学位论文摘要 则的特定类型。挖掘两种模式的标准算法是完全不同的。本文提出基 于f p t r e e 的h h c p g r o w t h 算法统一了两种模式的挖掘。算法采用了 递归挖掘思想，无需保存大量候选项集。除了应用传统的最小支持度 剪枝策略外，还引入最大支持度剪枝、项目自剪枝以及剩余项目剪枝 等策略，减少遍历和递归的次数。本文证明了剪枝策略的有效性和算 法的正确性。实验结果表明，h h c p g r o w t h 算法与传统的超团模式挖 掘算法和极大超团模式挖掘算法相比，具有更高的效率，尤其在大数 据集或低支持度条件下更为显著。 4 制作并发布可作为告警关联分析和研究使用的标准告警数据 集 采集了某省移动公司g p r s 网络管理系统及某设备生产商模拟 网管理系统部分时段的告警数据。这些真实数据经过预处理，去除噪 声和敏感信息后，被转换为可进行直接挖掘的标准数据格式。告警数 据集在网站上提供免费下载，可作为告警关联分析和研究使用的标准 数据集。 关键词：可信关联规则数据挖掘极大团超团模式告警关联分 析可信度 一 p ， s t u d yo fm i n i n ga l g o r i t h m sf o r c r e d ib l ea s s o c i a t i o nr u l e s a b s t r a c t 1 h ea s s o c i a t i o n - r u l em i n i n g ( a r m ) p r o b l e mi sa l li m p o r t a n ts t u d y t a s ki nt h ed a t am i n i n gf i e l d m o s tt r a d i t i o n a la i 蝴a l g o r i t h m sa r eb a s e d o nt h ef r a m e w o r ko f s u p p o r ta n dc o n f i d e n c e t h ei n f r e q u e n ti t e r ns e t s 撒 p r u n e db ym i n i m u ms u p p o r t ，a n dt h em o r ec o n f i d e n ta s s o c i a t i o nr u l e sa r e p r o d u c e db ym i n i m u mc o n f i d e n c e h o w e v e r , w ef o u n di ti sh a r dt os e l e c t t h ea p p r o p r i a t es u p p o r tt h r e s h o l df o rd a t a s e t sw i t hh i 曲s k e w e ds u p p o r t d i s t r i b u t i o nb yt h ec u r r e n tm i n i n ga l g o r i t h m s i ft h et h r e s h o l di st o oh i g h ， m a n ys t r o n ga f f i n i t yp a t t e m sw i t hl o ws u p p o r t si t e m sa r em i s s e d b u ti f t h et h r e s h o l di st o ol o w , m a n yf a l s er u l e sa r ep r o d u c e d w h i c hh a v en o r e a lm e a n i n gt ot h eu s e r i nt h i st h e s i s ，w es t u d i e dh o wt op r o d u c et h ec r e d i b l e ，c o n f i d e n ta n d v a l i da s s o c i a t i o nr u l e s t h ei n n o v a t i o n sa r ed e s c r i b e da sf o l l o w s ： 1 p r o p o s et h ec o n c e p to fc r e d i b l ea s s o c i a t i o nr u l e ( c a 鼬 t h ei t e r n si nac a ra r ei nt h es i m i l a rs u p p o r t t h ep r e s e n c eo fo n e i t e ms t r o n g l yi m p l i e st h ep r e s e n c eo fo t h e ri t e m si nt h es a m er u l e ，t h a ti s ， t h ei t e r n si nas a m er u l ea r et h ec o o c c u r r e n c e w h e nm i n i n gs u c hr u l e s t h es u p p o r tt h r e s h o l dc a nb ei g n o r e d ，s ot h ef r e q u e n ta n di n f r e q u e n t p a t t e r n sc a nb ep m d u c e dt o g e t h e r t om e a s u r ec a r s ，t h ec r e d i b i l i t yi s p r o p o s e dw h i c hr e p r e s e n t st h ec o - o c c u r r e n c ed e g r e eo ft h ei t e m si nt h e s a m er u l ea n ds u c ha st h em e a s u r e sb a s e do nt h ed i s t a n c em e a s u r ea n d h - c o n f i d e n c ea r ea l s od e s c r i b e d t h ee x p e r i m e n t a lr e s u l t ss h o wt h e r ea r e m a n yc a r s i nk i n d so fd a t a s e t sa n dt h e i rc r e d i b i l i t ya n dc o n f i d e n c eb o t h e x c e e dt r a d i t i o n a la s s o c i a t i o nr u l e s s oc a r sc a nb ea p p l i e dt om a n y f i e l d s 2 p r e s e n tm a x c l i q u e m i n i n ga l g o r i t h mf o rc a rb a s e do nm a x i m a l c l i q u e t h ea l g o r i t h mc r e a t e s2 一i t e mc r e d i b l es e t sb ya d j a c e n c ym a t r i xa n d t h e ng e n e r a t e sa l lr u l e sb a s e do nm a x i m a lc l i q u ew i t h o u ts c a n n i n gt h e d a m s e t sm a n yt i m e s m a x c l i q u e m i n i n ga l g o r i t h mc a nm i n et h ec a r s b a s e do nn o to n l yc r e d i b i l i t ym e a s u r eb u ta l s ol i f t ，c o s i n ea n dc o r r e l a t i o n m e a s u r e o n l yt h ec r e a t i o no f2 - i t e mc r e d i b l es e t si sd i f f e r e n ta m o n g t h e s em e a s u r e s o u re x p e r i m e n t a lr e s u l t ss h o wt h ee f f e c t i v e n e s sa n d a c c u r a c yo ft h i sm e t h o d ，e s p e c i a l l yf o rt h ed a m s a sw i t hs k e w e ds u p p o r t d i s t r i b u t i o n 3 p r e s e n t h h c p g r o w t ha l g o r i t h m o fu n i f i e d m i n i n g f o r h y p e r c l i q u ep a t t e r n sa n d m a x i m a lh y p e r c l i q u ep a t t e r n s h y p e r c l i q u ep a t t e r n ( h p ) a n dm a x i m a lh y p e r c l i q u ep a a e m ( m h p ) a r et w os p e c i a lt y p e so fc a r sb a s e do nh - c o n f i d e n c e t h es t a n d a r d a l g o r i t h m sm i n i n gt h et w ok i n d so fp a t t e r n sa r ed i f f e r e n t i nt h i sp a p e r , w ep r e s e n taf a s ta l g o r i t h mc a l l e dh y b r i dh y p e r c l i q u ep a r e r ng r o w t h ( h h c p g r o w t h ) b a s e do nf p - t r e e ，w h i c hu n i f i e st h em i n i n gp r o c e s s e so f t h et w op a t t e r n s 乃ea l g o r i t h ma d o p t sr c c u r s i v em i n i n gm e t h o dw i t h o u t s a v i n gam a s so fc a n d i d a t eg e n e r a t i o n b e s i d e st h et r a d i t i o n a lm i n i m u m s u p p o r tp r u n i n g ，t h ea l g o r i t h me x p l o i t ss o m ee f f i c i e n tp r u n i n gs t r a t e g i e s s u c ha sm a x i m u ms u p p o r tp r u n i n g ，i t e ms e l fp r u n i n ga n dr e m a i n i n gi t e m p r u n i n g ，w h i c hc a nr e d u c et h en u m b e ro fr e c u r s i o na n dt r a v e r s a l i ti s p r o v e dt oi n d i c a t et h ee f f e c t i v e n e s so ft h es t r a t e g i e sa n dt h ev a l i d i t yo f t h ea l g o r i t h m t h ee x p e r i m e n t a lr e s u l t ss h o wt h a th h c p g r o w t hi sm o r e e f f e c t i v et h a nh pa n dm h p m i n i n ga l g o r i t h m s ，e s p e c i a l l yf o rl a r g e - s c a l e d a t a s e t so ra tl o wl e v e l so fs u p p o r t 4 d i s t r i b u t e 也es t a n d a r da l a r md a t a s e t sf o ra l a r mc o r r e l a t i o n a n a l y s i sa n ds t u d y i no u ts t u d y , w ec o l l e c ts o m ep e r i o d so fa l a r m sf r o mag r p s n e t w o r km a n a g e m e n ts y s t e mo fap r o v i n c em o b i l ec o r p o r a t i o na n da s i m u l a t i v en e t w o r km a n a g e m e n ts y s t e mo fa ne q u i p m e n tv e n d o r t h e s e r e a la l a r md a t aa r et r a n s f o r m e dt ot h es t a n d a r dd a t af o r m a tf o rm i n i n g a f t e rp r e p r o c e s s i n g ，d e n o i s i n ga n df i l t e r i n gs e n s i t i v ei n f o r m a t i o n t h e s e d a t a s e t sc a nb ed o w n l o a d e df r e e l yo nt h e 朊6a n du s e da st h es t a n d a r d d a t a s e t sf o ra l a r mc o r r e l a t i o na n a l y s i sa n ds t u d y i v 一 _ 、j 一 ， ：， ； j k e yw o r d s ：c r e d i b l ea s s o c i a t i o nr u l e ( c a r ) d a t am i n i n g m a x i m a lc l i q u e h y p e r c l i q u ep a t t e r n a l a r mc o r r e l a t i o na n a l y s i s c r e d i b i l i t y 摹 t 以 目录 第一章绪论1 1 1 论文的研究背景和意义l 1 2 数据挖掘概述3 1 2 1 数据挖掘的概念。3 1 2 2 数据挖掘的任务。4 1 2 3 数据挖掘的应用领域o 6 1 2 4 数据挖掘的挑战- 7 1 2 5 关联规则挖掘8 1 3 论文主要研究内容1 l 1 4 论文结构安排。：13 本章参考文献15 第二章关联规则挖掘定义及主要算法2 0 2 1 问题定义2 0 2 2 数据分布2 3 2 2 1 水平数据分布2 3 2 2 2 垂直数据分布2 3 2 3 关联规则挖掘算法2 5 2 3 1 关联规则挖掘算法分类2 5 2 3 1a p r i o d 算法基本原理2 7 2 3 3f p - g r o w t h 算法基本原理2 8 2 3 4 序列模式挖掘算法3l 2 4 本章小结3 2 本章参考文献3 3 第三章可信关联规则及其兴趣度度量3 7 3 1 传统关联规则的局限性3 7 3 1 1 网络告警数据特点分析3 7 3 1 2 网络告警标准数据集3 9 3 1 3 挖掘倾斜分布数据集的局限性分析4 0 3 2 可信关联规则概念4 1 3 3 可信度度量性质。4 3 3 4 可信关联规则的其他兴趣度度量4 5 3 4 1 提升度度量4 5 3 4 2 相关度度量4 6 3 4 3 向量夹角余弦度量“。4 7 3 4 4h - 置信度度量与超团模式。4 8 3 4 5 各种度量的比较。5 0 3 5 本章小结。5 1 本章参考文献o 5 2 第四章基于极大团挖掘可信关联规则_ 。5 5 4 1 用邻接矩阵求2 项可信集。5 5 4 2 由i - 项可信集生成( k + 1 ) - 项可信集5 8 4 3 基于极大团的可信关联规则挖掘算法6 3 4 3 1 算法描述。6 3 4 3 2 求解极大团的改进算法6 5 4 3 3 算法性能分析6 7 4 4 实验结果分析6 8 4 4 - 1 数据集及实验环境描述6 8 4 4 2m a x c l i q u e m i n i n g 算法挖掘结果分析6 9 4 4 3m a x c l i q u e m i n i n g 算法与其他算法的比较。7 0 4 5 基于其他度量挖掘可信关联规则7 0 4 5 1 基于提升度度量产生2 一项可信集邻接矩阵7 1 4 5 2 基于余弦度量产生2 项可信集邻接矩阵7 3 4 5 3 基于相关度度量产生2 一项可信集邻接矩阵7 4 4 5 4 实验结果分析7 6 4 6 本章小结7 7 本章参考文献7 9 h 毒 t 第五章基于f p - t r e e 挖掘超团模式和极大超团模式8 0 5 1 基于f p - t r e e 挖掘超团模式。8 0 5 2 基于f p - t r e e 统一挖掘超团模式和极大超团模式8 7 5 3h h c p - g r o v v t h 算法分析8 9 5 4 实验结果分析：9 0 5 3 1 数据集及实验环境描述9 0 5 3 2h h c p 岣r o v v t h 算法挖掘结果分析9 0 5 3 3h h c p _ g 帕v v t h 与h y p e r c l i q u em i n e r 性能比较。9 2 5 3 4h h c p - g v v t h 与h y b n d 性能比较。9 3 5 5 本章小结9 4 本章参考文献_ 。9 5 第六章结束语9 7 6 1 本文的总结9 7 6 2 下一步工作9 8 致谢1 0 0 博士期间发表的论文1 0 1 i i i l 簟 r、；蠹尹-o 北京邮电大学博r 上学位论文第一章绪论 第一章绪论 随着数据生成和收集技术的进步，各个行业和领域都会产生海量数据集。人 们相信其中存在很多有价值的信息和知识，然而这也向我们提出了挑战如何 找到这些潜在有用的信息和知识? 为了解决上述问题，人们提出了数据挖掘 ( d a t am i i l i n 曲技术【啦】。关联规则挖掘是数据挖掘中的一项基础性工作，旨在发现 数据中强关联特征的有趣模式，也可以应用于分类、聚类、预测、相似模式查找 和周期模式挖掘等数据挖掘任务中。自从a g r a w a l 等人t 3 , 4 1 提出关联规则发现算 法之后，该问题得到了众多学者的广泛研究，不断有新的研究成果出现。人们尝 试从各种途径出发寻找各类有趣的模式，提出了多种多样的算法。本章首先阐述 了论文的研究背景和意义，然后对数据挖掘技术和关联规则挖掘的基本概念进行 介绍，最后论述了论文的主要研究内容和结构安排。 1 1 论文的研究背景和意义 随着计算机网络技术和软件技术的不断发展，人们生成和收集各种数据变得 越来越容易，各个行业和领域都会产生海量数据集。例如零售企业的详细销售记 录，地球轨道卫星每时每刻收集的地表、海洋、大气观测数据，医院里所有病人 的病情记录，网络上传输的流量数据、全球股票数据等。人们相信这些数据中存 在很多有价值的信息和知识。 上世纪7 0 年代以后关系数据库技术日渐成熟，人们能够将大量数据有效地 组织和存储，并通过对数据简单查询和统计分析得到少量信息。但是随着数据积 累的不断增长，人们迫切需要透过数据表面去挖掘蕴含于其中的丰富知识。从而， 如何从杂乱无章的海量数据中找到潜在有用的信息和知识成为学术界所面临的 一个挑战。 数据挖掘技术便是在这种背景下产生的。作为一门新兴的数据分析技术，数 据挖掘是数据库技术、人工智能技术、机器学习、神经网络、统计学、模式识别、 高性能计算和数据可视化等技术相结合的产物，目前已吸引了众多的研究者。数 据挖掘使得人们可以对海量数据进行更深层次分析，不仅提高了人们对于数据的 北京邮电大学博士学位论文第一章绪论 理解能力，而且可以透过数据表面提取更多有价值的信息和知识，这些信息可以 广泛应用于商务管理、生产控制、市场分析和科学研究等领域。 关联规则挖掘是数据挖掘中的一项基础性的工作，旨在发现数据中强关联特 征的有趣模式。a g r a w a l 等人【3 】于1 9 9 4 年开创性地提出了关联规则挖掘问题，旨 在发现大型超市中顾客购买的不同商品之间的联系，分析顾客的购物习惯，帮助 零售商制定营销策略。此后，关联规则挖掘被广泛地应用到众多领域，如w e b 挖掘、通信告警分析、文档分析、网络入侵检测、序列分析、生物信息学及地球 科学研究等。关联规则挖掘方法大都基于支持度置信度框架，即首先利用支持 度获得频繁项集或称为频繁模式，然后利用置信度得到比较可靠的关联规则。由 于利用置信度筛选可靠的规则相对简单，而挖掘频繁项集是一个n p 问题，因此， 人们将主要研究目标集中在如何快速得到频繁模式的问题上。 然而现实世界中的数据千变万化，对某些数据集进行挖掘时，人们发现无法 选择合适的最小支持度阈值。例如，在挖掘具有倾斜支持度分布( s k e w e ds u p p o r t d i s t r i b u t i o n ) 的数据集时，若将阈值设置较高，将会遗漏支持度较低但令人感兴 趣的规则；若将阈值设置较低，则挖掘结果会含有大量虚假规则，其中所包含项 目的支持度处于不同数量级，对用户没有实际意义。我们在进行网络告警关联性 分析时就发现，很多低支持度的关联规则置信度较高，对于人们预防网络重大故 障具有重要意义，而很多高支持度和置信度的规则反而是毫无用途的虚假规则。 事实上，这类问题已经引起了人们的注意。很多研究者开始关注关联规则的 评估问题，提出很多客观的评估方法，这些方法统称为兴趣度度量。人们希望利 用合理的度量表达关联规则的可信程度或有效性。b r a i n 等人【5 】提出基于提升度 的度量，但这种度量方法很难确定有效的阈值。o m i e c i n s k i 于2 0 0 3 年曾提出 a 1 1 c o n f i d e n c e 兴趣度度量方法【6 】，x i o n g 在此基础上又提出h - c o n f i d e n c e 兴趣度 度量【。7 1 ，这些新的度量方法都旨在减少虚假规则的产生。将这些度量结合到频繁项 集的产生过程，可以大大压缩生成的候选项集数量，并能挖掘出强亲密度关联模 式。但这些方法大都仍然基于a p r i o d 算法，不但多次扫描数据库，而且需要判 别每个侯选项的兴趣度，因此时间性能偏低。徐前方等也曾提出一种基于相关度 统计的关联规则挖掘算法【8 】，可以同时挖掘出频繁项和非频繁项的关联规则，但 需要进行大量的相关度计算。 2 f 8 毒 北京邮电人学博士学位论文 第一章绪论 由此，论文围绕如何得到可信有效的关联规则展开研究，重点研究了一下几 个问题：1 ) 创新性地提出了可信关联规则这一概念并给出了几种度量方法，使 得我们可以摆脱支持度的限制，对频繁模式和非频繁模式统一挖掘；2 ) 给出基 于极大团的方法挖掘可信关联规则，并提出和证明若干相关命题，用以分析和论 证算法的正确性；3 ) 提出了使用f p - t r e e 的快速算法统一挖掘一类特定类型的可 信关联规则超团模式和极大超团模式。实验表明，可信关联规则在很多数据 集中都会存在，其可信程度远远大于传统的关联规则，论文提出的各种挖掘算法 较传统的挖掘方法在性能和效率上都有提高，可广泛应用到诸多领域中，具有很 好的应用前景。 1 2 数据挖掘概述 1 2 1 数据挖掘的概念 或 数据挖掘就是从大量数据中挖掘有价值的信息和知识。与统计分析、人工智 能、机器学习不同的是，数据挖掘所要处理的是大量的未经加工的原始数据【吻。 从本质上来说，数据挖掘是一个对原始大量数据进行加工、分析、抽取的过程， 目的是获得有价值的信息和知识。 与数据挖掘有着同样内涵的另外一个概念是数据库中的知识发现 ( 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 ) 。很多人认为两者是同义词例， 也就是说数据挖掘的过程本身就是从数据中发现知识。也有些人认为知识发现过 程包含了若干步骤，而数据挖掘可看作其中的一个基本步骤。 广1 广 数据集成模式评估与 敞据清理f 刁 与选择- b 叼据挖鸳曰知识表示- l r 7 u 融据清理f 1 图1 - 1 知识发现过程 图1 1 给出了知识发现过程的各个步骤。由于数据存放在多种不同类型的数 据库、信息存储库或数据仓库中，因此首先要进行数据清理，去除噪声和不一致 数据，将这些数据源组合在一起并提取出与挖掘任务相关的数据。然后将筛选出 3 ， 北京邮电大学博士学位论文第一章绪论 的数据变换成适合挖掘的统一形式并进行数据挖掘，得到挖掘结果。最后，将挖 掘结果根据某种兴趣度度量，识别出可以表示为知识的真正有趣的模式，并使用 可视化和知识表示技术，向用户提供挖掘得到的知识。 数据挖掘涉及多种学科的相关技术，包括数据库技术、人工智能技术、机器 学习、神经网络、统计学、模式识别、高性能计算和数据可视化等。其中数据库 技术是数据挖掘的基础，因为数据库为数据挖掘提供数据来源，同时数据挖掘为 数据库提供了智能化的分析手段。 并非所有的信息发现任务都被视为数据挖掘。例如，使用数据库管理系统查 找个别的记录或通过因特网搜索引擎查找特定的w e b 页面，这些都是信息检索 ( i n f o r m a t i o nr e t r i e v a l ) 领域的任务【1 0 1 。与数据挖掘的区别在于它们主要依赖传 统的计算机技术和数据的明显特征来创建索引结构，从而有效的组织和检索信 息。 与机器学习等其他人工智能技术相比，数据挖掘也具有其自身特点：首先， 数据挖掘处理的是大规模数据集，算法的可扩展性通常是衡量数据挖掘算法的主 要指标。第二，数据挖掘系统一般要具有多种不同的挖掘工具，可以从同一海量 数据集中发现不同类型的知识。第三，数据挖掘系统能够发现各种粒度( 即不同 抽象层次) 的知识。第四，数据挖掘通常并不产生精确的结果，而是基于概率的 统计规律，这意味着有些被发现的模式并非对数据集中的所有数据都成立，通常 每个被发现的模式都带有一个确定性或可信性度量。 1 2 2 数据挖掘的任务 一般而言，数据挖掘任务可以分为描述和预测两大类。描述性挖掘任务描述 数据的一般性质；预测性挖掘任务对当前数据进行推断，以做出预测。具体来说， 常见的数据挖掘任务有以下几类【l 】。 1 2 2 1 概念描述 人们常常将数据的部分性质抽象表示为一定的概念和类。概念描述即是用汇 总的、简洁的、准确的方式描述每个类和概念。概念描述可以通过数据特征化或 数据区分来实现。数据特征化是目标数据的一般特征或特性的汇总，而数据区分 是将目标类对象的一般特征与一个或多个对比类对象的一般特征作比较【l l , 1 2 】。 4 北京邮电大学博上学位论文第一章绪论 1 2 2 2 关联规则挖掘 关联规则挖掘的目标是从指定数据中发现关联规则。关联规则反映不同属性 值集合在指定数据集中同时出现的可能性。关联规则挖掘通常分为两个步骤进 行。第一步，从指定数据集中找出所有出现频率超过最小支持度阈值的频繁模式； 第二步，从频繁模式中得到关联规则。第一步是关联规则挖掘中最困难、最关键 的一步。关联规则挖掘最初用于购物篮分析【3 1 ，目前已广泛应用于各个领域。 1 2 2 3 分类和预测 分类是用一个函数或模型，把各个类标号未知的数据项映射到预定义的类 中，从而得到这些数据的类标号。分类挖掘的关键是导出用于分类的函数或模型。 人们对于这一问题的研究由来已久，提出了许多用于导出分类模型的方法，包括 决策树分类方法【1 3 】、统计方法、神经网络方法【1 4 1 、粗糙集( r o u g hs e t s ) 1 5 】方法等。 预测分析是对类标号未知的数据项预测其可能的类标号，也可以通过预测分析估 计出一组数据中的某些丢失数据的可能值，或一个数据集合中某种属性值的分布 情况。一般是利用数理统计的方法，找出所要预测的属性并根据相似数据的分析 估算属性值的分布情况 1 2 2 4 聚类分析 聚类分析同样是将未知类标号的数据项进行归类的过程。聚类分析与分类挖 掘不同。分类挖掘的各种类标号是己知的，其目标是判定类标号未知的数据项所 属的真正标号。而聚类分析中类标号是未知的，事先并不知道指定的数据集会被 划分为哪几个类，甚至可能不知道类标号的数目。聚类分析的目标是按照一定的 原则形成类标号，并将指定的数据集划分到各个类中。这个原则就是聚类结果应 使每个类内部对象间的相似性尽可能大，而不同类对象间的相似性尽可能小。在 具体实现中，一般用计算对象属性的距离( 欧几里德距离、曼哈顿距离等) 来体现 对象间的相似度。 1 2 2 5 孤立点分析 数据库中包含的一些数据对象可能与数据的一般行为不一致，或者不遵循总 的数据模型，这样的数据称为孤立点。在通常的数据挖掘应用中需要将孤立点排 除掉，然而在一些特殊的应用( 如欺诈检测) 中，孤立点反而成为挖掘的目标。 孤立点分析大致有统计1 6 1 、基于距离17 】和基于偏型1 8 1 三种方法。 5 北京邮电大学博十学位论文 第一章绪论 1 2 2 6 趋势分析 趋势分析描述对象行为随时间变化的趋势和规律，它是对时态数据挖掘的总 称。趋势分析自然包括概念描述、关联规则、分类与预测、聚类以及孤立点分析 针对时态数据的应用，但它也包括时态数据挖掘特有的任务，如周期模式匹配和 相似性查找等【1 9 1 。 1 2 3 数据挖掘的应用领域 数据挖掘技术的应用领域非常广泛，在政府管理决策、商业运营决策、科学 研究和工业企业决策支持等各个领域都能应用数据挖掘技术。以下列举了一些常 见的应用领域。 ( 1 ) 商业管理 通过对顾客交易的数据进行分析可以有效地对顾客群体进行划分，预测不同 群体的购买行为和需求大小，进行有针对性的营销设计。运用模式识别和聚类分 析的方法，通过提取客户资料，对客户和它们对几种不同商品的兴趣进行聚类分 析，可以发现潜在客户的具体特征，从而对这些潜在客户进行相应的促销宣传 2 0 2 h o ( 2 ) 网站管理 网站是电子商务的基础平台，大型网站每日都有数以万计的访问量，如何合 理安排网站组织结构，是一个非常困难的任务。通过应用数据挖掘可以从用户的 访问信息中发现有价值的知识，从而指导网站设计者更新网站结构与内容。这样 可以更好地与客户进行交流，发现潜在客户，改进客户关系管理，提高网络营销 效率。这些有价值的信息也可以帮助设计人员制作针对个性化用户或用户群的访 问界面，开展有针对性的电子商务以满足访问者的需求【2 2 2 3 1 。 ( 3 ) 信息安全 在电子商务中，电子交易是其中的一个重要组成部分，而信用卡又在电子交 易中扮演了重要的角色。通过运用数据挖掘中的离群数据挖掘方法或聚类方法总 结正常交易行为和诈骗行为之间的关系，获取诈骗行为的一些特性。利用这些知 识去分析和判断现有交易中具有诈骗的倾向，如发现某项业务符合这些特征时， 可以向决策人员提出警掣2 4 1 。 ( 4 ) 金融证券 ， ? 砖 基 北京邮电大学博十学位论文第一章绪论 数据挖掘技术已广泛地应用于银行和金融市场。金融市场中的数据挖掘主要 应用于改进预测市场波动的能力、建立预测模型以识别出历史上曾引起市场波动 的因素所具有的模式、进行投资分析增加收入、以及减少商业欺诈所造成的损失。 典型的应用有贷款偿还预测和客户信用政策分析，股票预测，客户保持以及实时 营销等【2 s , 2 6 1 。 ( 5 ) 科学研究 利用数据挖掘技术可以处理海量数据。例如在生物d n a 分析【2 7 1 、新药的药 理分析和治疗机理以及天文学研究等领域，都可以找到数据挖掘技术的应用空 间。 1 2 4 数据挖掘的挑战 面对不同类型的数据集及新的挖掘任务，传统的数据分析技术常常遇到很多 困难，这也引发了人们对数据挖掘的深入研究。具体来说，数据挖掘面临的挑战 主要有以下几点2 8 】： “ ( 1 ) 可伸缩 数据挖掘算法不仅可以处理小数据集，还要能够处理海量数据集，因此算法 必须是可伸缩的( s c a l a b l e ) 。很多处理过程可能涉及指数性搜索问题，因此数据 挖掘算法需要研究特定的搜索策略以提高挖掘效率。可伸缩有时需要实现新的数 据结构，以有效的方式访问相关记录。 ( 2 ) 高维性 目前的数据集往往具有数以千计的属性。传统的为低维数据开发的数据分析 技术通常不能很好的处理这样的高维数据。另外，对于某些数据分析算法，随着 维度的增加，计算复杂性往往也会迅速增加。 ( 3 ) 异种数据和复杂数据 通常，传统的数据分析方法只能处理包含相同类型属性的数据集。随着数据 挖掘在商务、科学、医学和其他领域的作用越来越大，越来越需要能够处理异种 属性的技术。近年来已出现了各种复杂数据对象，如半结构化文本和超链接的 w e b 页面集、具有序列和三维结构的d n a 数据、包含地球表面不同位置上的时 间序列测量值的气象数据等，挖掘这类数据应当考虑数据中的联系，如时间和空 间的自相关性、图的连通性、半结构化文本和x m l 文档中元素的父子关系等。 7 北京邮电大学博士学位论文第