（计算机应用技术专业论文）关联规则及相关数据挖掘技术研究.pdf

摘要 摘要 数据挖掘是从海量数据库中发现入们感兴趣的、隐藏的、前所未知的知识。 它涉及数据库、人工智能、机器学习、模式识别、知识工程、面向对象、信息检 索和可视化等一系列技术。经过十多年的发展，它已成为关系数据库中最有前景 的研究和应用领域之一。关联规则是数据挖掘的重要模式之，它的研究有着极 其重要的理论与实际意义。 a p d o d 算法是挖掘布尔关联规则的经典算法，而该算法在空间和时间复杂 度上有着难以克服的局限性，存在多次扫描数据库和产生大量候选集的性能瓶 颈。本文提出了一种基于链表变换的算法，详细地描述了链表的构造、插入和变 换操作及由这些操作产生频繁集的整个过程。该算法只需扫描两次数据库就可发 现所有频繁集，且不需产生大量的候选集，另外因完成链表变换的基本操作已有 高级语言函数库的良好支持，故算法具有很高的效率。实验表明，所提新算法在 一定数据集范围内相对于a p f i o f i 算法具有优越性。 由频繁集生成用户感兴趣的且具有价值的规则，是关联规则算法研究的重要 内容。基于支持度和置信度的框架模型有可能生成支持度和置信度都很高，但却 是用户不感兴趣的规则。本文在分析经典兴趣度模型的基础上，提出了一种新的 兴趣度模型来消除虚假规则的误导。实验表明新的兴趣度模型与经典兴趣度模型 具有一致的结果，但相对于经典兴趣度模型具有更好的粒度，更有利于挖掘否定 项的关联规则。 本文研究了关联规则生成过程中可能出现的规则组合指数爆炸的问题，通过 在支持度和置信度框架中引入兴趣度改进函数来使阀题得以解决。本文最后根据 简单匹配的思想，定义了两个规则的距离，从而实现了用聚类算法对生成的规则 做整理，使用户得到更清晰的信息。 关键词： 数据挖掘；关联规则；a p d o f f ：兴趣度 a b s t r a c t i i i i a b s t r a c t d a t am i n i n gi sat e c h n i q u et h a td i s c o v e r st h ei n t e r e s t i n g ，h i d d e n ，a n du l l k n o w n k n o w l e d g ef r o ml a r g ed a t a i th a se m e r g e da so n eo ft h em o s tp r o m i s i n ga r e a sf o r d a t a b a s er e s e a r c ho v e rt h ep a s td e c a d e + d a t am i n i n gi n v o l v e s a l l i n t e g r a t i o no f t e c h n i q u e sf r o md 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 ，p a t t e r nr e c o g n i t i o n ， 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 ，i n f o r m a t i o nr e t r i e v a l ，h i 曲p e r f o r m a l i c ec o m p u t i n ga n dv i s u a l i z a t i o n a p r i o r ia l g o r i t h mi su s e dt of i n db o o l e a n a s s o c i a t i o nr u l e s ，b u ti ti sv e r yc o s t l y i nt h ec o m p l e x i t yo fs p a c ea n dt i m e i nt h i st h e s i s ，w ei n t r o d u c ean e wa l g o r i t h m b a s e so na r r a y l i s t p a r t i c u l a rd e s c r i p t i o no ft h ea r r a y l i s t sc o n s t r u c t i o na n dt r a n s f o r m i sp r e s e n t e di nt h ep a p e r t h i sa l g o r i t h mo n l yn e e d st os c l m tt h ed a t a b a s et w ot i m e s f u r t h e r m o r e ，n oc a n d i d a t es e t sa r eg e n e r a t e d a l m o s ta l lt h ef u n c t i o n so f t h ea r r a y l i s t a r es u p p o r t e db yt h el i b r a r i e so fm o d e r np r o g r a m m i n gl a n g u a g e o u re x p e r i m e n t s h a v ep r o v e dt h a ti ti sm o r ee f f i c i e n tt h a na p r i o r i h o wt os e l e c t i n t e r e s t i n ga n dv a l u a b l er u l e s a r ei m p o r t a n tf a c t o r so fr u l e s g e n e r a t i n g t h e r ei sl i m i t a t i o ni ns u p p o r ta n dc o n f i d e n c ef r a m e w o r k t h u san e w i n t e r e s tm e a s u r em o d e li sg i v e ni nt h i st h e s i s ，w h i c hi su s e dt op r u n et h eu n i n t e r e s t i n g r u l e sa n dm i n er u l e sw i t hn e g a t i v ei t e m s i nt h ec o t l r s eo f m i n i n g ，t h en u m b e ro f r u l e sw i l ls o a rb e c a u s eo f t h ec o m b i n 8 t i o n o f i t e m s t oa v o i dt h i ss c e n a r i o ，w ei n t r o d u c en e wc o n s t x a i n t si m p r o v e m e n tf u n c t i o n i nc o n c l u s i o n ，t h i sp a p e ra n a l y z e st h ec l a s s i c a la s s o c i a t i o nr u l e sa l g o r i t h m sa n d c r e a t e sn e wm i n i n gt h e o r e t i c m o d e l s ，d e s i g n sas e r i e so fn e wa l g o r i t h m sb a s e do n s u c ht h e o r i e s e x p e r i m e n tr e s u l t si n d i c a t et h e i rh i g h e rp e r f o r m a n c ei nr a n g eo f d a t a s e t s k e y w o r d s ：d a t am i n i n g ；a s s o c i a t i o nr u l e s ；a p r i o r i ；i n t e r e s tm e a s u r e i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其它 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文曾作了明确的说明并表示了谢意。 签名目簸：面j 。5 、d 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允、午论文被查阅和借阅：学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其它复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：丝导师签名日期：迹加 第1 章绪论 第1 章绪论 随着计算机和通信技术的迅速发展，大型数据库系统得到广泛应用，企业积 累的数据量急剧增加。据有关资料统计【1 】，其数据量以每月1 5 ，每年5 3 倍的 幅度增加。j o h nn a i s b i t t 在他的首部著作大趋势m e g a t r e n d s t 2 1 中就提到：“人 类正被信息淹没，却饥渴于知识”。激增的数据背后隐藏着许多重要的信息，人 们希望能够对其进行更高层次的分析，以便更好地利用这些数据。 目前的关系数据库系统所能做到的只是对数据库中已有的数据进行存取，人 们只能看到这些数据的一些表面的东西，而不能看到隐藏在这些数据背后的更重 要的信息，即关于这些数据的整体特征的描述和发展趋势的预测等等，而后一种 信息对决策过程具有重要的意义。这样就淹没了包含的知识，造成了资源的浪费 - “。因此，如何从海量的数据中提取有用的知识成为当务之急。 用数据库管理系统来存储数据，用机器学习的方法来分析数据，挖掘大量数 据背后的知识，这两者的结合促成了数据库中的知识发现( k d d ：k n o w l e 如e d i s c o v e r yi nd a t a b a s e s ) 。f a y y a d 、p i a t e t s k y s h a p i r o r 和s m y t h 对k d d 作了 比较具有代表性的定义“1 ：“k d d 是从数据集中识别出有效的、新颖的、潜在有 用的，以及最终可理解的模式的非平凡过程。”数据挖掘是i c d d 最核心的部 分，是采用机器学习、统计等方法进行知识学习的阶段。 1 1 课题背景 9 0 年代中期以来，数据挖掘与知识发现技术在欧美形成了研发高潮，是近 年来软件开发市场的热点，许多行业如通信、金融、零售、制造业等大量利用数 据挖掘工具来协助其业务活动，一些软件开发商，基于市场的需求开发了名目繁 多的数据挖掘和知识发现工具和软件，如q u e s t 是由i b m a l m a d e n 研究中心开发 的数据控制系统，它可以从大型数据库中发现关联规则、分类规则、序贯模式等。 目前，数据挖掘和知识发现的应用十分广泛，从政府管理、商业经营、工业企业 决策支持、市场销售预测、金融投资、社会保险、医学、天文、地质以及科学研 究等各个领域都可应用到数据挖掘。g a r t e r g r o u p 的一次高级技术调查将数据挖 北京工业大学工学硕士学位论文 掘和入工智能列为未来3 5 年内对工业产生深远影响的五大关键技术之首，并且 还将并行处理体系和数据挖掘列为未来五年内投资焦点的十大新兴技术的前两 位。勿容置疑，数据挖掘的研究和应用具有很大的挑战性。象其它新技术的发展 历程一样，数据挖掘也必然经过概念提出、概念接受、广泛研究和探索、逐步应 用和大量应用等阶段。从目前的现状看，大部分学者认为数据挖掘的研究仍然处 于广泛研究和探索阶段。一方面，数据挖掘的概念已经被广泛接受。在理论上， 一批具有挑战性和前瞻性的问题被提出，吸引越来越多的研究者。数据挖掘的概 念从被提出后，其经济价值已经显现出来，而且被众多商业厂家所推崇，形成了 初步的市场。大多数学者赞成这样的观点：数据挖掘在商业上的成功不能期望通 用的辅助开发工具，而应该是数据挖掘概念与特定领域商业逻辑相结合的纵向解 决方案( v e r t i c a ls o l u t i o n ) 。 分析目前的研究和应用现状，数据挖掘的研究工作主要是围绕如下几个方面 展开的： ( 1 ) 挖掘算法的效率和可扩展性。目前数据库数据量大，维数商。使得数据 挖掘的搜索空间增大，发现知识的盲目性提高。如何充分利用领域的知识，剔除 与发现任务无关的数据，有效地降低问题的维数，设计出高效率的知识发现算法 是下一步发展的重点，它包括领域知识对行业或企业知识挖掘的约束与指导、商 业逻辑有机嵌入数据挖掘过程等关键课题。 ( 2 ) 数据挖掘理论与算法研究。经过十几年的研究，数据挖掘已经在继承和 发展相关基础学科( 如模式识别、机器学习、统计学等) 已有成果方面取得了可 喜的进步，探索出了许多独兵特色的理论体系。但是，这决不意味着数据挖掘理 论的探索已经结束，恰恰相反它留给了研究者丰富的理论课题。一方面，在这些 大的理论框架下有许多面向实际应用目标的挖掘理论等待探索和刨新。另一方 面，随着数据挖掘技术本身和相关技术的发展，新的挖掘理论的诞生是必然的， 而且可能对特定的应用产生推动作用。新理论的发展必然促进新的挖掘算法的产 生，这些算法可能扩展挖掘的有效性，如针对数据挖掘的某些阶段、某些数据类 型、大容量源数据集等更有效，可能提高挖掘的精度或效率，可能融合特定的应 用目标，如c r m 、电子商务等。因此，对数据挖掘理论和算法的探讨将是长期 而艰巨的任务。 第l 晕缮论 ( 3 ) 数据的时序性。在应用领域的数据库中，数据在不断地更新，随着时间 的推移，原先发现的知识将的有用性将降低。我们需要随时问逐步修正发现模式 来指导新的发现过程。 ( 4 ) 数据挖掘系统的构架与交互式挖掘技术。虽然经过多年的探索，数据挖 掘系统的基本构架和过程已经趋于明朗，但是受应用领域、挖掘数据类型以及知 识表达模式等的影响，在具体的实现机制、技术路线以及各阶段或部件( 如数据 清洗、知识形成、模式评估等) 的功能定位等方面仍需细化和深入研究。由于数 据挖掘是在大量的源数据集中发现潜在的、事先并不知道的知识，因此和用户交 互式进行探索性挖掘是必然的。这种交互可能发生在数据挖掘的各个不同阶段， 从不同角度或不同粒度进行交互。所以怠好的交互式挖掘( i n t e r a c t i o nm i n i n g ) 也是数据挖掘系统成功的前提。 ( 5 ) 数据挖掘语言与系统的可视化问题。对o l t p ( o n l i n et r a n s a c t i o n p r o c e s s i n g ) 应用来说，结构化查询语言s q l 已经得到充分发展，并成为支持数 据库应用的重要基石。但是，对于数据挖掘技术而言，由于诞生的较晚，加之它 相比o l t p 应用的复杂性，开发相应的数据挖掘操作语言仍然是件极赋挑战性 的工作。可视化要求已经成为目前信息处理系统的必不可少技术。对于一个数据 挖掘系统来说，它更显得更为重要。可视化挖掘除了要和良好的交互式技术结合 外，还必须在挖掘结果或知识模式的可视化、挖掘过程的可视化以及可视化指导 用户挖掘等方面进行探索和实践。 ( 6 ) 互联网上知识的发现。w w w 正日益普及，从中可以找到很多新的知 识，已有一些资源发现工具来发现含有关键字的文本，但对在w w w 上发现知 识的研究相对不多。加拿大的h a r t 等人提出利用多层次结构化的方法，通过对 原始数据的一般化，构造出多层次的数据库。例如可将w w w 上的图象描述而 不是图象本身存储在高层数据库中，现在的问题是如何从复杂的数据( 例如多媒 体数据) 中提取有用的信息。对多层数据库的维护，及如何处理数据的异类性和 自主性等等。 1 2 论文研究的主要内容 1 2 1 论文研究的主要问题 北京工业太学工学硕上学位论文 关联规则挖掘的研究是近几年研究较多的数据挖掘方法，在数据挖掘的各种 方法中它的应用也最为广泛。最为著名的关联规则挖掘方法是由美国学r a g r a w a l 提出的a p r i o r i 算法“。该算法主要是用于从大规模商业数据中挖掘关联规 则。最近也有独立于a p r i o r i 的频集方法的工作“1 “，以避免频集方法的一些缺陷， 探索挖掘关联规则的新方法。同时随着o l a p ( o n - l i n ea n a l y t c a lp r o c e s s i n g ) 技术的成熟和应用，将o l a p 和关联规则结合。”也成了一个重要的方向。也有一 些工作注重于对挖掘到的模式的价值进行评估，他们提出的模型提供了一些值得 考虑的研究方向。 基于频集的a p r i o r i 算法的最大优点是算法思路比较简单，是以一种递归的 统计为基础，剪切生成频繁集。但是a p r i o r i 方法自身有难以克服的缺陷： ( 1 ) 产生大量的中间项候选集：a p r i o r i g e n 函数是由l n 中的项集作条件 连接，所产生候选k 一项集的数量呈几何级数增加。有学者通过试验研究表明： 当长度为1 的频繁集有1 0 0 0 0 个的时候，长度为2 的候选集个数将会超过1 0 7 。 在要生成一个长规则模式的时候，要产生的候选集的数量将大到难以想像( 为了 发现长度1 0 0 的频繁模式，则必须产生2 “个候选) 。 ( 2 ) 难以发现低频度信息：由于频集法使用了最小支持度m i n s u p ，因而就 难以对支持度小于m i n s u p 的事件进行分析，而有些小概率事件有可能有较大信 息价值；然而，如果阀值m i n - s u p 取得很低，那么将产生大量的中间候选集和频 繁集，进而，效率就成了一个很难处理的问题。 ( 3 ) 多次反复扫描数据库：由于该算法要找出包含每一个候选集的数据库事 务，因此要求多次扫描整个交易数据库，对于挖掘长模式尤其如此( 挖掘k 阶项 集需要扫描k 次数据库) 。当数据库存放大量事务数据，其效率将十分低下，同 时也给系统带来很大的i o 负载。 ( 4 ) 基于支持度一置信度框架的a p r i o r i 算法由于只用支持度和置信度这两 个标准来衡量关联规则，在实际中会因高支持度而挖掘出带有欺骗性的虚假规 则。如一学校中，5 0 的学生玩篮球，7 0 的学生吃糕点，而3 0 的学生既玩篮球 也吃糕点。若m i n s u p = 2 0 ，m i n c o n f = 6 0 ，用a p r i o r i 算法可产生( 玩篮球) = ( 吃 糕点) 的关联规则，置信度为6 0 ，而实际上有7 0 的学生吃糕点。如将这样的规 则提交给用户，就会作出玩篮球是吃糕点的主要原因的错误分析。这是由于部分 第1 苹绪论 属性( 吃糕点) 出现频率太高所引起的。 ( 5 ) 规则组合爆炸，导致计算量指数增加，提交用户的规则总数激增，用户 难以理解。属性集i = o 一，i 。) ，若从i 中任取r k 个属性i 。，i 。有s u p ( i ) 与 s u p ( 。，t ) 相差很小( 例如：若对于任意t t ，t 要么支持i ， 要么对于i 中任 何属性都不支持，那么s u p ( i ) 与s u p ( i ，i 。) 相等) ，那么如果规删j x u l l ) _ y 满足m i n s u p 和m i n c o n f 约束，则就会有2 “1 个规则( 前集为x 与i 子集的并， 后集都为满足条件。规则太多，从而对y 的预测分析产生困难。这是由i ，i 。 间有很强的关联性引起的。 ( 6 ) 基于支持度一置信度的a p r i o r i 算法只能挖掘出“正面”的规则，如某顾 客可能购买项集中的一些项，而不能挖掘出可能不够买某些项的规则。如能挖掘 出“牛奶”= ”面包”的关联规则，但不能挖掘出“买了牛奶的顾客不会买纯净水” 的规则，因此a p r i o r i 算法虽然排除了一些无兴趣的规则，还往往会产生一些对 用户来说不感兴趣的规则和丢失一些有兴趣的规则。所以必须寻找新的方法或改 进匕述方法。 1 2 2 论文的主要工作与结构 数据挖掘是近年兴起的多学科相互融合的应用技术，广泛地应用于各个领 域，特别是金融业、商业管理、市场分析以及科学研究等领域，引起了企业界 和学术界的极大关注，形成了诸多的研究热点。本文主要研究关联规则的挖掘 算法及相关技术，本文的主要工作如下： 1 对数据挖掘技术产生的背景和对象做概括性的综述，介绍数据挖掘技术 的内容、流程和当前用于数据挖掘的理论。 2 对关联规则的经典定义给出了详细的描述，并详细归纳了关联规则的基 本性质，为探索新的挖掘算法提供理论指导。对不同类型的关联规则给予了简 单的介绍。 3 在研究经典挖掘算法( a p r i o r i 算法) 的特征和性能并分析了其不足的 基础上，结合现有的理论研究成果，本文从如下几方面对算法进行了改进探索： ( 1 ) 针对a p r i o r i 算法产生大量的中间项候选集和多次反复扫描数据库的 北京工业大学工学硕士学位论文 不足，本文提出了种新的基于链表数据结构( a , r a y l i s t ) 的算法。用该数据结构 存储事务项目集，通过构造、插入、变换算法，最终将输出频繁项集。该算法 不需要产生候选项集，从而相对于a p r i o r i 算法大大减少了存储空间的消耗。 该算法只需扫描2 次数据库，而a p r i o r i 算法发现k 阶频繁项集要扫描k 次数据 库，因而该算法大大地减少了y o 操作。 ( 2 ) 基于支持度一置信度框架的h p r i o r i 算法由于高支持度而挖掘出带有欺 骗性的虚假规则的不足，如同其他改进算法一样，本文引入了兴趣度。在分析 了经典兴趣度模型的不足的基础上，借鉴数据挖掘决策树算法( i d 3 ) 的思想， 本文在兴趣度模型中利用信息论的理论来衡量规则的有趣性，提出了一种新的 兴趣度模型，并通过实例来证明其正确性和较好的粒度。 f 3 1 针对a p r i o r i 算法不能挖掘有价值的“负规则”的不足，结合本文给出 的兴趣度模型，本文探讨了负规则的概念，正负规则兴趣度，支持度，置信度之 间的数学关系，给出了在考虑负规则的基础上挖掘完整有效的关联规则的流程和 算法。 ( 4 ) 本文分析了经典a p r i o r i 算法规则指数爆炸的问题，在考虑兴趣度的基 础上引入了置信度、兴趣度的改进度函数，只有该规则的子规则能显著提高原规 则的置信度和兴趣度时，才将子规则提交给用户。 ( 5 ) 在海量数据的实际挖掘过程中生成的关联规则数目仍然是惊人的。通过 寻找规则的相似性，利用这种相似性，可以给最终决策者提供更加简洁明了的结 果。本文结合k 一中心点算法，提出了将生成的规则聚类的算法。 1 3 小结 本章介绍了数据挖掘研究的理论意义和技术背景、论文的选题依据、研究 背景以及论文的主要研究方向、课题开展的工作等等。数据挖掘是近年兴起的 多学科相互融合的应用技术，广泛地应用于各个领域，引起了企业界和学术界 的极大关注，形成了诸多的研究热点。本文主要对关联规则及其相关挖掘算法 进行了深入研究，研究了经典挖掘算法( a p r i o r i 算法) 的特征和性能，在分 析其不足的基础上，结合现有的理论研究成果，对算法做了改进探索。 第2 章数据挖掘技术概述 第2 章数据挖掘技术概述 1 9 9 5 午，往加拿凡召丌了筇 膳知以发现( k d d ) 和数抓汁窆掘( d a t a m i n i n g ， d m 、幽际学术会议。由于数据库中的数据被形象地喻为矿庶，因此数据挖掘 词报快流传：h = 来。明确数据挖掘的概念、对象、任务等基本问题，是我们，i ：展数 据挖掘理论和实际应用研究的基础。 2 1 数据挖掘的概念 1 9 9 5 年以来，圆外在数据挖掘知识发现方面的论丈非常多，已彤成了热1 1l 研 究方向。数据挖掘足知识发现最关谜的步骤，也是技术难点所在。研究k d d 的 人员中夫部分都往研宄数据挖掘技术。由于知识发现过程中各部分之间的紧密相 关性和d i 技术的核心作用，通常不严格区分k d d 和d m ，两者互为使用。 数据挖掘被定义为从大量的、不完全的、有噪声的、模糊的、随机的数据中 提取隐含在其中的、人们事先不知道的、但潜在有用的信息和知识的过程。数据 挖掘作为一门交叉性学科，融合了人工智能、数据库、模式识别、机器学习、统 计学和数据可视化等多个领域的理论和技术。数据挖掘作为一种技术，它的生命 周期正处于沟坎( c h a s m ) 阶段，需要人们花时间和精力去研究、开发，逐步成 熟，并最终为人们所接受“1 。 2 2 数据挖掘的对象和任务 根据信息存储格式，用于挖掘的对象有关系数据库、面向对象数据库、数据 仓库、文本数据源、多媒体数据库、空间数据库、时态数据库、异质数据库以及 i n t e r n e t 等“。数据挖掘的任务主要是关联规则、聚类分析、分类、预测、时 序模式和偏差分析等。 关联规则( a s s o c i a t i o nr u l e s ) 挖掘是由r a g r a w a l l 等人首先提出的 1 3 2 。 两个或两个以上变量的取值之间存在某种规律性，就称为关联。数据关联是数据 库中存在的一类重要的、可被发现的知识。关联分为简单关联、时序关联和因果 关联。关联分析的目的是找出数据库中隐藏的关联网。一般用支持度和置信度两 北京工业大学工学硕士学位论文 i i i i i i i1 1 个阀值来度量关联规则的相关性，还不断引入兴趣度、相关性“等参数，使得所 挖掘的规则更符合需求。 聚类( c l u s t e r i n g ) 是把数据按照相似性归纳成若干类别，同类中的数据 彼此相似，不同类中的数据相异，聚类分析可以建立宏观的概念，发现数据的分 布模式，以及可能的数据属性之间的相互关系。 分类( c l a s s i f i c a t i o n ) 就是找出一个类别的概念描述，它代表了这类数据的 整体信息，即该类的内涵描述，并用这种描述来构造模型，一般用规则或决策树 模式表示。分类是利用训练数据集通过一定的算法而求得分类规则。分类可被用 于规则描述和预测。 预测( p r e d i c a t i o n ) 是利用历史数据找出变化规律，建立模型，并由此模型 对未来数据的种类及特征进行预测“”。预测关心的是精度和不确定性，通常用预 测方差来度量。 时序模式( t i m e s e r i e sp a t t e r n ) 是指通过时间序列搜索出的重复发生概率 较高的模式。与回归分析一样，它也是用己知的数据预测未来的值，但这些数据 的区别是变量所处时间的不同。 偏差分析( d e v i a t i o n ) 在偏差中包括很多有用的知识，数据库中的数据存 在很多异常情况，发现数据库中数据存在的异常情况是非常重要的。偏差检验的 基本方法就是寻找观察结果与参照之间的差别。 2 3 数据挖掘常用的技术 由上面介绍可知，数据挖掘是- - j 崭新的交叉学科，与其他学科的理论知识 不断渗透，而产生新的算法，下面介绍近几年常用于数据挖掘的理论方法。 ( 1 ) 模糊( f u z z y ) 方法 美国控制论专家和数学家查德( z a d e h ) 发表的论文“模糊集合”( f u z z y s e t s ) “，标志着模糊数学的诞生。模糊集合和模糊推理是模糊方法的数学基础， 模糊理论以不确定的的事物为研究对象，是经典集合理论的扩展。隶属度函数是 模糊集合的特征函数，是模糊概念的核心，它的取值范围从普通 0 ，i ) 的两个值 扩充到 0 ，1 闭区间内的连续值，隶属度函数的定义如下： 设给定域u ，u 到 0 ，1 闭区间的任一映射。， 第2 覃数据挖掘技术概述 i l l l l ：u 【o ，1 ，“ d ( “) “u ( 2 - 1 ) 都确定u 的个模糊子集a ，v 是a 的隶属度函数，心( “) 是u 对a 的隶属度， 表征u 属于a 的程度。其实模糊集合并不是一个集合，因为其核心是隶属度函数， 如同概率中的随机变量，所以更确切地应该称其为模糊函数。 模糊推理就是由前提( a 。) ，依规则( i f a t h e nb ) 推理，得到结论( b ) 。 规则是一种蕴含关系，推理中将前提和规则结合是一种合成关系。在模糊方法中 关系就是模糊集合，找关系便是找隶属度函数。模糊逻辑系统已用于许多特别是 基于规则的分类系统中，在基于规则的分类系统引入模糊逻辑，就可以定义“模 糊”阀值或边界，可以避免原系统固有的缺陷：对于连续值，由陡峭的截断从而 可能获得一个更合理的分类结果。 ( 2 ) 粗糙集( r o u g hs e t s ) 理论 r o u g h 集理论是由波兰华沙理工大学的z p a w l a k 教授于1 9 8 2 年提出的一种 研究不完整性和不确定知识和数据的表达形式，学习和归纳的理论方法“”，现已 成为d m k d d 研究中的最有力工具，也是最有发展前途的。r o u g h 集理论采用上 近似集合r + 和下近似集合融来定义r o u g h 集“”，即 r ( x ) = u ( y u r ：y n x 引( 2 2 ) 凡( x ) = u y u r ：y x )( 2 3 ) 其中，u 是全域，x c _ u 是目标集合，r 是u 上的等价关系，y u r 表示y 是u 上按等价关系r 做成的等价类。上近似集合可理解为所有那些与x 有交的等价类 的并集，下近似集合可理解为所有那些被包含在x 里面的等价类的并集。 上近似集合和下近似集合之间的差称为x 的r 边界线集，可表示为： b n = r ( x ) 一凡( x ) 。它是那些通过等价关系r 既不能在x 上分类，也不能在x 上分 类的元素的集合。从语义角度来看，m ( x ) 至x _ c 时( x ) ，介于r 。( x ) 和r ( x ) 之间 的集合簇均属r o u g h 集，而上下近似集合则是该空间的两个极限。在r o u g h 逻辑 推理中，不必涉及隶属度函数，这样的软计算技术有助于知识获取瓶颈的突破， r o u g h 集理论的核心特点是无需提供问题所需处理的数据集合以外的任何先验信 息。这也可能是因为其无法获得客观事实的足够支持。 r o u g h 集理论可以用于分类，发现不准确数据或噪声数据内在的联系。找出 北京工业太学工学硕士学位论文 可以描述给定数据集中所有概念的最小属性子集是个n p 一难问题。 ( 3 ) 云( c l o u d ) 理论 云理论是李德毅教授于1 9 9 5 年提出的用于处理不确定性的一种新理论“。 作为处理模糊性问题的主要问题，f u z z y 集理论提出了隶属度函数来刻画模糊事 物的亦此亦彼性；然而，一旦用精确的隶属度函数来描述模糊集，之后的模糊推 理等环节就不再有模糊性了。这就是传统模糊集理论的不彻底性。针对这一问题 李德毅教授在传统模糊集理论和概率统计的基础上提出了定性定量不确定性转 换模型一云模型，把定性概念的模糊性和随机性完全集成到起，构成定性和定 量相互间的映射，作为知识表示的基础“”。在数据挖掘中，云理论常和r o u g h 集 理论相结合。前者研究的是数据的模糊性和随机性，为定量定性间的不确定性转 换提供模型；而后者强调的是数据的不完备性和不可分辨性，但其处理方法是确 定性的，要求属性值是定性值。所以两者具有某种互补性。 ( 4 ) 证据理论 证据理论又称d e m p s t e r s h a f e r 理论，是经典概率论的扩充，经s h a f e r 进一步发展，形成处理不确定信息的证据理论。该理论的一个重要贡献是划清了 不确定和不知的界限。a n a n d 等于1 9 9 4 年提出了一个基于证据理论的通用数据 挖掘框架e d m ( d a t a b a s em i n i n gb a s e do ne v i d e n c et h e o r y ) 。“。由于证据理 论在处理不确定性方面的优点，加之e d m 的开发和应用，使得基于证据理论的方 法在数据挖掘中具有潜在的应用性。 ( 5 ) 遗传算法( g e n e t i ca l g o r i t h m s ，g h ) 遗传算法最先由j o h nh o l l a n d 于1 9 7 5 年提出。”。它模拟生物的进化和遗传， 借助选择( s e l e c t i o n ) 、交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 操作，使要解 决的问题从初步逐步逼近最优解，解决了许多全局优化问题。 遗传算法易于并行，已广泛用于分类和优化问题。在数据挖掘中，还可用于 评估其他挖掘算法的合适度。 ( 6 ) 串经元网络方法 神经元网络由于本身良好的鲁棒性、自组织性自适应性、并行处理、分布存 储和高度容错等特性非常适合解决数据挖掘的问题，因此近年来它越来越受到人 们的关注。典型的神经元网络模型主要分3 大类：一是以感知机、b p 反向传播 第2 苹数据挖掘技术概述 m l i i i 模型、函数型网络为代表的，用于分类、预测和模式识别的前馈式神经元网络模 型；以h o p f i e l d 的离敬模型和连续模型为代表的，分别用于联想记忆和优化计 算的反馈式神经元网络模型；以a r t 模型、k o h o l o n 模型为代表的，用于聚类的 自组织映射方法。神经元网络方法的缺点是“黑箱”陛，人们难以理解网络的 学习和决策过程。 2 4 数据挖掘的一般( 商业) 过程 数据挖掘产生于应用，且应面向于应用。数据挖掘的交叉产业标准过程 ( c r o s s i n d u s t r yp r o c e s sf o rd a t am i n i n g ，c r i s p - d m ) 是当今数据挖掘业 界通用流行的标准之一，是s p s s ( s t a t i s t i c a lp r o d u c ta n ds e r v i c e s o l u t i o n s ) 、n c r ( n a t i o n a lc a s hr e g i s t e r ) 和d a i m l e rc h r y s l e r3 家公司在 1 9 9 6 年制定的，它强调的是数据挖掘在商业中的应用，解决商业存在的问题， 而不是把数据挖掘局限在研究领域。c r i s p d m 参考模型包括：商业理解、数 据理解、数据准备、建立模型、模型评估和模型发布( 如图2 一l 所示) 。“。 图2 一lc r i s p - d m 参考模型 f i g 2 - lp h a s eo f t h ec r l s p o d mp r o c e s sm o d e l 2 5 数据挖掘系统设计应注意的问题 越来越多的软件供应商加入到数据挖掘这一领域的竞争。用户如何正确评价 一个商业软件，以及选择合适的软件成为数据挖掘成功应用的关键所在。 评价一个数据挖掘软件主要应从以下四个主要方面汹1 ： 北京工业大学工学硕士率位论文 i i i 一 i 舅皇! ! 皇曼! ! ! ! ! 皇烹烹! ! 苎! 皇曼曼曼 ( 1 ) 计算性能：如该软件能否在不同的商业平台上运行，软件的架构，能否 连接不同的数据源，操作大数据集时，性能变化是线性的还是指数的，算法的效 率，是否基于组件结构易于扩展，运行的稳定性等。 ( 2 ) 功能性：如软件是否提供足够多样的算法，能否避免挖掘过程黑箱化? 软件提供的算法能否应用于多种类型的数据? 用户能否调整算法和算法的参 数? 软件能否从数据集随机抽取数据建立预挖掘模型? 能否以不同的形式表现 挖掘结果等? ( 3 ) 可用性：如用户界面是否友好，软件是否易学易用，软件面对的用户， 初学者，高级用户还是专家? 错误报告对用户调试是否有很大帮助，软件应用的 领域，是专攻某一专业领域还是适用多个领域等。 ( 4 ) 辅助功能：如是否允许用户更改数据集中的错误值或进行数据清洗， 是否允许值的全局替代? 能否将连续数据离散化? 能否根据用户制定的规则从 数据集中提取子集? 能否将数据中的空值用某一适当均值或用户指定的值代 替? 能否将一次分析的结果反馈到另一次分析中? 等等。 2 6 数据挖掘技术的应用 数据挖掘的应用非常广泛，下面简要介绍一些的应用可以说明数据挖掘的用 途。 2 6 1 通信行业中的应用 随着国市场竞争的日趋激烈，通信运营商的经营模式逐渐从“技术驱动”向 “市场驱动”和“客户驱动”转化。这就要求运营商要采取以客户为中心的策略，根 据客户的实际需求提供多样化、层次化、个性化的服务解决方案。因此，客户关 系管理( c r m ) 成了通信运营商增加收入和利润，提高客户满意度、忠诚度的 有效工具。在客户关系管理的流程中，为了准确、及时她进行经营决策，必须充 分获取并利用相关的数据信息对决策过程进行辅助支持。数据挖掘技术就是实现 这一目标的重要手段。数据挖掘技术在通信行业客户关系管理的主要应用如下： 客户消费模式分析。客户消费模式分析( 如固话话费行为分析) 是对客户 历年来长话、市话、信息台的大量详单、数据以及客户档案资料等相关数据进行 第2 章数据挖掘技术概述 i i 关联分析，结合客户的分类，可以从消费能力、消费习惯、消费周期等诸方面对 客户的话费行为进行分析和预测，从而为固话运营商的相关经营决策提供依据。 客户市场推广分析。客户市场推广分析( 如优惠策略预测仿真) 是利用数据 挖掘技术实现优惠策略的仿真，根据数据挖掘模型进行模拟计费和模拟出账，其 仿真结果可以揭示优惠策略中存在的问题，并进行相应的调整优化，以达到优惠 促销活动的收益最大化。 客户欠费分析和动态防欺诈。通过数据挖掘，总结各种骗费、欠费行为的内 在规律，并建立一套欺诈和欠费行为的规则库。当客户的话费行为与该库中规则 吻合时，系统可以提示运营商相关部门采取措施，从而降低运营商的损失风险。 客户流失分析。根据已有的客户流失数据，建立客户属性、服务属性、客户消费 情况等数据与客户流失概率相关联的数学模型，找出这些数据之间的关系，并给 出明确的数学公式。然后根据此模型来监控客户流失的可能性，如果客户流失的 可能性过高，则通过促销等手段来提高客户忠诚度，防止客户流失的发生。这就 彻底改变了以往通信运营商在成功获得客户以后无法监控客户流失、无法有效实 现客户关怀的状况。 2 6 2 金融行业中的应用 随着国内银行卡业务的逐步完善，部分银行的卡业务逐渐体现出发行数量 大、客户众多、交易频繁、交易信息全面等特点，客观上具备了进行多维数据分 析和数据挖掘的条件。 银行卡市场分析和预测。利用数据挖掘工具分析直销数据以及风险和增益 数据，自动发现用户群及其银行卡使用模式。挖掘工具能自己找出有意义的用户 群。这些信息可以帮助市场部经理或企业主管提高促销活动的效果策划新的市场 营销。 银行卡客户关系管理。利用数据挖掘工具，对客户行为数据库进行分析，寻 找客户减少的模式，识别喜欢新产品的用户群。这些模式可以帮助客户关系管理 人员提高客户忠诚度。 信用卡风险分析。利用挖掘工具发现高风险组的使用模式及其信用卡透支行 为。挖掘工具能自动找出这些客户群并可预见高透支率行为，然后利用预测模型 北京工业大学工学硕士学位论文 来估计当前信用卡用户的风险度。 银行金融服务分析。利用挖掘工具发现基于簇或地理位置的用户使用产品的 模式。映射发现系统找出按地区分布的用户使用模式，而数据挖掘工具则按用户 对各种渠道的使用频率进行聚类分析。 2 6 3 商品销售中的应用 商业部门把数据视作一种竞争性的财富可能比任何其他部门显得更为重要， 为此需要把大型市场营销数据库演变成一个数据挖掘系统。科拉福特( k r a f t ) 食品公司( k g f ) 是应用市场营销数据库的公司之一，该公司搜集了购买它商品 的3 0 0 0 万个用户的名单，这是( k g f ) 通过各种促销手段得到的。k g f 定期 向这些用户发送名牌产品的优惠券，介绍新产品的性能和使用情况。该公司体会 到了解自己商品的用户越多，则购买和使用这些商品的机会也就越多，公司的营 业状况也就越好。 2 6 4 制造行业中的应用 许多公司不仅将基于数据挖掘的决策支持系统用于支持市场营销活动，而 且，由于市场竞争越演越烈，这些公司己使用决策支持系统来监视制造过程，有 制造商声称已经指示它的各个办事机构，在三年内把制造成本每年降低2 5 。 不言而喻，该制造商经常收集各部件供应商的情况。因为，它们也必须遵循该制 造商降低成本的战略。为了对付来自各方的挑战，该制造商已拥有一套”成本” 决策支持系统，可以监视各供应商提供的零部件成本，以实现所制定的价格目标。 2 7 小结 本章系统地归纳了数据挖掘技术的概念、对象和任务以及近几年常用的方 法和理论。从商业和技术角度阐述了数据挖掘的概念和内容，阐述了数据挖掘研 究的理论基础及其在通信，金融等领域愈来愈重要的实际应用价值。本章也对数 据挖掘的主要研究热点与应用进行了分析。总之，数据挖掘的研究和应用将是一 个长期而艰苦的工作，具有强大的生命力。 第3 章关联规则及其经典算法 第3 章关联规则及其经典算法 关联规则的主要研究对象是交易数据库，其主要目标就是发现交易数据库中 交易项目之间是否存在某些关联关系【2 6 】。国内外许多研究人员对关联规则的