（计算机应用技术专业论文）关联规则评价方法研究.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 ) 是当前 人工智能、数据库技术等学科的一门十分活跃的研究领域。数据挖掘( d a t a m i n i n g ，d m ) 是k d d 的一个重要步骤，是从数据中提取人们感兴趣的、潜在的、 可用的知识，并将其表示成用户可理解的形式。 关联规则挖掘( a s s o c i a t i o nr u l e sm i n i n g ) 是数据挖掘的一个重要分支， 用以发现所有满足最小支持度和最小可信度的强关联规则。关联规则的挖掘通 常是对大规模数据进行处理，产生的规则数目较大，并且挖掘的结果不一定能 真正反映现实领域的知识和满足用户的需求。因此，对挖掘结果的验证和评价 是关联规则挖掘中不可缺少的环节。 现有的关联规则评价方法主要有两大类；客观评价方法和主观评价方法。 客观评价方法中主要使用支持度和可信度两种评价标准。但在实际应用中，仅 用支持度和可信度对关联规则进行评价是不够的。因此，有必要对支持度一可 信度评价模型进行改进，增加评价标准，以挖掘出更加有效、更令用户满意的 关联规则。为此，本文归纳了当前所使用的几种客观和主观评价方法，并对它 们进行了比较研究。 本文所做的研究工作如下： 1 、对传统的关联规则评价模型进行深入的分析和比较，并对其所存在的问 题进行了讨论。 2 、提出了频繁模式的新颖性概念和基于客观度量与主观度量的综合评价方 法，强化了对关联规则的评价。 3 、在固定支持度阈值设置基础上，讨论了可变支持度设置的方法，并进行 了比较分析。 4 、对自动支持度阈值设置方法展开了讨论，对有关概念进行扩展，并对有 关文献中的计算公式进行了补充证明和改进。 关键词：数据挖掘，关联规则，评价方法 s t u d y o nm e t l l o d so fe v a l u a t i o nf o rt h ea s s o c i a t i o nr u l e s a b s t r a c t k n o w l e d g ed i s c o v e r y i nd a 协b a s e s ( k d d ) i sav e r ya c t i v ef i e l da m o n gt h es u b j e c t so f t h ed 撕b a s e st e c h n i q u e ，也ea n i f i c i a li n t c l l i g e n c e ，e t c d a t am i n j n gi sa n i m p o r t a l l ts t e p o f k d d ，c a i ld i s c o v e r yk n o “e d g e 舶mm ed a t a b 舔e s nc a i lb eu n d e r s t o o db yu s e r sa n di s i n t e r e s t 血v a l i d a n d p o t e 嘶a i l yu s e 如1 a s s o c i a t i o nr 山e sm i n i n g ，a ni m p o 衄1 tb m c ho fd a 协m i n i n gi s 廿l e s t r o n g a s s o c i a t i o n 九n e s 也a tc a ns 8 t i s 匆a l lt l l em i f l i m u ms u p p o r tt l l r e s h o l da n dt l l em i n i m m c o n 矗d e n c et l l r c s h o l d m i i l i n gt h ea s s o c i a t i o nm l e so f e n e e d s d e a l i n g 谢也l a 唱es c a l ed a t a a sar e s l l l t 廿l en 啪b e ro ft l l em l e si sl a r g ea i l dn o ta l lm e c o n s e q u e n c e sc a nr e a l l yf e n e c t t h ek n o w l e d g eo fr e a l i s t i cf i e l d s 趾dm e e tm eu s e r s n e e d s t h e r e f o r e ，“i sn e c e s s a r yt o e v a l u a t et l l er e s l l l t so f t l l ea s s o c i a t i o ni 沁l c sm i l l i n g t h ec u i r e n te v a i 删o nm e m o d s 曲o u t 雒s o c i a t i o nn l l e sm a i n l yc o n s i s to f 也e o b j e c t i v e a 1 1 ds u b j e c d v ee v a i 删o nm e m o d s h lo b j e c t i v ee v a l u a t i o n ，也e r ea r em a i n l yt w oe v a l u a t i o n 翻t e r i a ：s u p p o r ta n dc o n f i d e n c e i nt h ea c t u a la p p l i 谢o n ，i “sn o te n o u 曲t oe v a l u a t et l l e a s s o c i a t i o nr u l e s0 n l yu s i n gs u p p o na n dc o i l f i d e n c e s o ，i ti s n e c e s s a r yt oi m p r o v et h e s u p p o r t c o i d e n c em o d e la n di n c r e a s et h ee v a | u a t i o ns t a n d a r ds oa st om i n et l l em o r e s a t i s 玲i n ga n de 佑d e n t 弱s o c i a t i o nm l e s t h i sd i s s e n a t i o nc o n c l u d c st h ec u r r e n to b j e c t j v e a n d 娜b j e c t i v ee v a l u 砒i o nm e 山o d a n da l s om a k e ss o m er e s e a r c h 、v o r ki sa sf o l l o w s ： 1 a n a l y z e s 锄dc o m p a r e s t h et r a m t i o n a lm o d e l0 f 邵s o c i 撕o nm l e se v a l u a t i o na n da l s o d i s c u s st h ee x i 鳓n g p r o b l 衄髓 2 p r e s e n t sc o n c e p t o f 丘_ c q u e n tm o d e l a i m c o m p 辑h e n s i v ee v a l 僦i o nm 幽d c o m b i n e d t h c o b j e c t i v e a n d s u b j e c t i v em e 嬲u r c m e n t s ，、v ! h i c h e n h a n c e st i l ee v a l u a t i o na b o u t a s s o c i a t i o nm i e s 3 a t 血eb a s i so f s e t t 血gu p t l l ef i x e dt l i r e s h o l da b o u tg u p p o n ，d i s c u s st l l em 甜i o d so f s e n i n gu p 伽e v a r i 西b l es u p p o r ta n dc o m p a r a t i v c l y 删y z et h e m 4 d i s c 璐st l l em e t i l o d so f s e t c i n gu p 廿l e 鲫t o m a t i c t l l 他s h o l dd b o m s u p p o n ，e m a 唱et h e r e l 撕v ec o n c e p t s ，a n di m p r o v es o m ef 砷l u l 鸹i ns o m er c l a t i v ed o c u m e n t s k e y w o r d s ：d a t a m i n i n g ，a s s o c i a t i o nr u l e s ，e v a l u a t i o nm e m o d 合肥工业大学 本论文经答辩委员会全体委员审查，确认符合合肥 工业大学硕士学位论文质量要求。 导师： 工作单位、职称) 勿雕 多1 级覆 咿掣吖 碉 1 0 刀剑1 钇 图表目录 图1 ，1k d d 的处理过程 图2 1 候选项集和频繁项集的产生 图3 1 计算w 。的示意图 图3 ，2 概念分层的示意图 图4 1 关联规则的评价过程 表2 1 某商店的销售事务数据库 表3 ，l 牛奶和咖啡的销售统计表t 表3 2 交易中的所有可能的关联规则一 表3 3 交易中的所有可能的关联规则( 新兴趣度定义下) 表3 4 慢性细菌性前列腺炎诊断门诊记录 表4 1 一个交易数据库( d ) - ，掩钾 巧巧”抄叭 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 盒胆王些盔堂或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示谢意。 学位论文作者签名- 嚷孑耳目签字眺捌可月日 学位论文版权使用授权书 本学位论文作者完全了解盒胆王些盔堂有关保留、使用学位论文的规定，有 权保留并向国家有关部f 1 或机构送交论文韵复印件和磁盘，允许论文被查阅和借 阅。本人授权盒避兰些盔堂可以将学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学一名：亥坞 签字日期：膨6 月孑日 学位论文作者毕业后去向： ，、 工作单位：善镞锹铴瑾杜 通讯地址：魁谚专冶准咯7 一j 考 导师签名 签字日期：为年多月；日 电话t o 骚1 弓d 6 0 弧 邮编：一；，护口d 致谢 本文是在我的导师胡学钢教授的悉心指导下完成的。在课题的确定、课题 的研究及论文撰写等方面，胡老师均给予了精心指导、热情鼓励和大力支持。 胡老师为人正直、治学严谨、诲人不倦的品质使我铭记不忘，受益匪浅。在此 论文完成之际，由衷感谢我的导师胡学钢教授，谨向胡老师表示最诚挚的敬意! 同时，真诚感谢计算机学院的各位老师，特别是王浩老师，他们的教诲为本文 的研究提供了借鉴和指导：感谢班主任杨孙梅老师的关心和支持；感谢研究生 院和学位办的领导和老师们，在我的研究生课程学习和论文撰写期间，给予我 的大力支持。 感谢我的家人，他们一直给我精神上的鼓励和生活上的关心，给了我克服 困难的信心和不断进取的动力。 感谢所有曾经给予我关心和帮助的人! 作者；窦祥圜 2 0 0 5 年6 月 第一章数据挖掘概述 本章首先介绍了数据挖掘的定义、现状及发展趋势，对数据挖掘的过程、 方法和技术以及数据挖掘的基本任务作了简要的说明。 1 1 引言 随着计算机技术的飞速发展，计算机的数据处理能力和数据存储能力不断 提高，越来越多的数据被存储到计算机的中，人们所面临的是迅速扩张的数据 海洋。为更好管理和应用这些数据，数据库及数据仓库技术应运而生。它为有 效地收集和存储数据提供了方便，也为数据的分析和管理提供了有力的手段。 快速增长的海量数据收集、存放在大型和大量的数据库中，人们必须借助于强 有力的工具才能理解和利用这些数据。然而，与日益成熟的数据库管理技术和 软件工具相比，人们所依赖的数据分析工具却无法有效地为决策者提供决策支 持所需要的相关知识，从而形成了“信息丰富而知识贫乏”的窘境。因此，有 效地利用和处理大量的数据是当今计算机技术领域一个重要的研究课题。 尽管传统的数据库管理系统( d b m s ) 提供了比较完善的存取和查询功能， 但仍不能满足人们对大量数据进行知识的抽取、发现数据问隐藏的依赖关系， 从而为决策提供科学的支持。由于决策者缺乏从海量数据中提取有价值知识的 工具，因此重要的决策常常不是基于数据库中丰富的数据，而是基于决策者的 直觉。但这常常会有偏差和错误，并且耗时、费用高。利用数据挖掘工具进行 数据分析，可以发现数据库中重要的数据模式，从而为决策提供有价值的知识。 数据库知识发现( k n o w l e 她ed i s c o v e r y i n d a t a b a s e s ，k d d ) ， 和数据挖 掘( d a t am i n i n g ，d m ) “1 正是在这种情况下产生和发展起来的一种新型数据分 析技术，成为近年来人工智能和数据库应用等领域的研究热点。 本章首先对数据挖掘的有关概念作了简要的介绍，然后对数据挖掘的方法、 任务和相关技术进行概要性的说明，并提出本文的研究内容和组织安排，最后 对本章作总结。 1 2 k d d 的定义及发展 1 2 1k d d 的定义 数据挖掘( d m ) ，又称为数据库中的知识发现( k d d ) 。许多人将数据挖掘同 数据库中的知识发现视作同一概念，也有人将数据挖掘视为数据库中知识发现 的一个过程。目前比较公认、比较完整、深刻和全面的一个定义是由德国人 f a y y a d z 等人在1 9 9 6 年发表的论文f r o m d a t am i n i n gt ok n o w l e d g ed i s c o v e r y 一文中“将k d d 定义为：“t h en o n t r i v i a lp r o c e s so fi d e n t i f v i n g v a l i d ，n o v e l ，p o t e n t i a l l yu s e f u l ，a n du l t i m a t e l yu n d e r s t a n d a b l ed a t t e r n s i nd a t a 。”即k d d 是从大量的数据中提取出有效的、新颖的、有潜在价值的、可 信的、并能最终被人理解的模式的非凡的处理过程。在有些文献中也将它称为 数据开采、知识提取、数据模式分析、数据考古等1 。 数据挖掘的结果必须是事先未知的，这些信息的表现形式有：规则、概念、 规律及模式等等，它可帮助决策者分析历史数据及当前数据，从中发现隐藏的 关系和模式，进而预测未来可能发生的行为。下面对概念中的有关名词作一解 释。 数据：是数据挖掘的对象。原则上讲，数据挖掘可以在任何类型的数据存 储上进行。包括关系数据库、数据仓库、事务数据库和w w w 等。在进行数据挖掘 前一般要对原始数据进行清理、集成、选择和变换，使之成为具有规范格式的 数据，以便挖掘。 模式：是指根据用户的不同需求( 兴趣) ，在挖掘过程中产生的、易于识别 和表示的知识表示形式，是用某种规范形式表现的数据的子集。 潜在价值：指数据挖掘所提取的知识应该是有意义的，能对决策提供支持 的。 新颖性：数据挖掘所提取的知识相对于已发现的知识的差别。它包括两个 方面，一是所提取的知识是先前没有的或是与所期望的模式不同：二是所提取 的知识同以前的知识有某种关联。 可理解性：数据挖掘的目的是将数据库中隐含的知识模式以容易理解的形 式表现出来，从而帮助人们更好地去理解数据库中所包含的信息，进步为决 策提供支持。 处理过程：k d d 的过程一般包括数据清理、数据集成、数据选择、数据变换、 数据挖掘、模式评估、知识表示。 1 2 2k d d 的发展及研究现状 k d d 与d m 是人工智能、机器学习与数据库技术相结合的产物。k d d 一词首次 出现在1 9 8 9 年8 月在美国底特律召开的第十一届国际联合人工智能学术会议上。 随着k d d 在学术界和工业界的影响越来越大，k d d 组委会于1 9 9 5 年把专题讨论会 更名为国际学术会议，并于1 9 9 5 年在加拿大的蒙特利尔召开了第一届k d d 国际学 术会议。由于有人经常将数据库中的数据比喻为矿床，因此数据挖掘( d m ) 一 词很快就被流行开。k 叻国际学术会议以后每年举行一次“1 。迄今为止，由美 国人工智能协会主办的k d d 国际研讨会已经召开了7 次，规模由原来的专题讨论 会发展到国际学术大会”1 。第一本关于k d d 的国际学术杂志d a t am i n i n g a n d k n 删1 e d g ed i s c d v e r y 也于1 9 9 7 年3 月创刊发行。亚太地区于1 9 9 7 年在新加坡 首次召开了k d d 国际学术研讨会( p a k 叩) 。 目前，在i j c a i 、a a a i 、v l d b 、a c m s i g m o d 等代表人工智能与数据库技术 研究最高水平的国际学术会议上对k d d 的研究都占有很大的比例，k d d 已经成为 当令计算机科学与技术研究的热点领域之一。近几年，我国的研究人员纷纷加 入到该领域中来，国内的许多学术会议，如数据库学术会议、机器学习学术会 议等，也都将k d d 列为重要的研究方向”。 此外，数据库、人工智能、信息处理、知识工程等领域的学术刊物也纷纷 开辟了k d d 专题或专刊。i e e e 的k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊领先在 1 9 9 3 年出版了k d d 技术专刊。所发表的论文代表了当时k d d 研究的最新成果和动 态，全面地论述了k d d 系统方法论、挖掘结果的评价、k d d 系统设计的逻辑方法， 集中讨论了鉴于数据库动态性冗余、高噪声和不确定性，与其它传统的机器学 习、专家系统、人工神经网络、数理统计分析系统的联系和区别等。1 9 9 8 年a c m ( a s s o c i a t i o nf o rc o m p u t i n gm a c h i n e r y ) 正式成立了k d d 的特别兴趣小组 s i g k d d ( s p e c i a li n t e r e s tg r o u po nk n o w l e d g ed i s c o v e r yi nd a t a b a s e sa n d d a t am i n i n g ) ，其宗旨是综合各相关研究领域的共同兴趣和努力，迎接从大型 数据库中开采出有用知识的挑战。 不仅如此，在i n t e r n e t 上还有不少k d d 的电子出版物，其中以半月刊 k n o w l e d g ed i s c o v e r yn u g g e t s 最为权威。如要免费订阅，可以通过指定的网站 发送一份电子邮件即可，还可以下载各种各样的数据挖掘工具软件和典型的样 本数据仓库，供人们测试和评价。 随着k d d 研究逐步走向深入，人们越来越清楚地认识到k d d 的研究主要有3 个技术支柱，即数据库技术、人工智能和数理统计。研究的重点也逐渐从发现 策略转向到系统应用，且注重多种发现策略的集成，以及多种学科之间的相互 渗透。k d d 已经成当今计算机科学界的一大热点。 然而，目前数据挖掘技术的研究还很不成熟，其应用还存在较大的局限性， 存在的主要问题有“”： i 、数据输入形式的多样性。应用中经常需要对一些半结构化、非结构化的 数据形式如文本、图形、数学公式、图像或w w w 资源等进行挖掘操作，但目前 的数据挖掘工具一般只能提供对数值型的结构化数据的处理，对数据中存在 缺损或噪声的情况也没有有效的处理方法。 2 、数据挖掘算法的有效性与可测性。数据挖掘的对象向更大型的数据库、 更高的维数、属性之间更复杂的关系等方向发展。更多的记录和属性意味着更 大、更高维的援索空间，从而导致组合爆炸；属性之间的关系变得更为复杂( 如 表现为层次结构) ，会大大提高知识搜索的代价。 3 、用户参与和领域知识。有效的决策过程往往需要多次交互和多次反复， 要求数据挖掘的结果准确地描述数据挖掘的要求，并易于表达。能实现在多 抽象层次上交互挖掘知识。目前许多知识发现系统和工具缺乏与用户的交互， 难以有效利用已有领域知识。 4 、证实技术的局限。数据挖掘使用特定的分析方法或逻辑形式发现知识。 如归纳方法。僵系统可髓无法去交互证实所发现的知识的正确和正确的程度， 使得发现的知识没有普遍性而不能成为真正有用的知识。 5 、知识的表达和解释机制。许多应用中重要的是用户能够理解发现的知识。 这要求知识的表达不仅限于数字或符号，而是更易于理解的方式。如图形、 自然语言和可视化技术等。同时，只有当数据挖掘系统能提供更好的解释机制 用户才能更有效地评价这些知识，并且区分出哪些是真正有用的知识，哪些 只是常识性的知识或异常情况。 6 、知识的维护和更新。新的知识发现可能导致以前发现的知识失效，因 此知识需要动态维护和及时更新。目前研究采用增量更新的方法、数据快照和 时间戳等方法来维护已有的知识。 7 、隐私和安全性。数据挖掘能从不同角度、不同抽象层次上观察数据，这 将影响到数据挖掘的私有性和安全性。通过研究数据挖掘导致的数掘菲法侵入， 可改进数据库安全方法，以避免信息泄露。 8 、支持的局限、与其他系统的集成。目前的数据挖掘系统尚不能支持多种 平台。一些产品是基于p c 的，一些是面向大型主机系统的，还有一些是面向 客户机朋臣务器环境的。另外，由于功能单一的发现系统的适应范围限制，要 充分发挥系统的作用，应该和数据库、知识库、专家系统、决策支持系统、可 视化工具、网络技术等进行有机地集成。 1 3 k d d 的处理过程 研究k d d 是为了将数据挖掘的结果应用于实际数据的处理，为科学地决策 提供支持。数据挖掘是k d d 的中的一个重要过程。目前对k d d 的研究主要集 中在对数据挖掘的研究上，而忽视了其他方面的研究。事实上，k d d 整个处理 过程的每一个阶段应该是一个有机的整体，如果仅侧重于数据挖掘，就会影响 k d d 的效率和结果的可靠性。因此，对k d d 的整个处理过程研究是非常重要 的。 有关k d d 的处理过程主要有以下三种模型1 2 川3 3 1 ： 第一是u s a m a m f a y y a d 等人提出的多处理阶段模型； 第二是g e o r g e h j o l l n 提出的多处理阶段模型： 第三是b r a c h m a n & a n a n d 提出的以用户为中心的处理模型。 下面以第一种模型为例来说明k d d 的主要处理步骤，图1 1 给出了此模型 的示意图。 图1 1k d d 的处理过程 识 l 、数据准备 数据准备又可以分为三个子步骤：数据的选取、数据预处理和数据变换。 数据选取的目的是确定发现任务的操作对象，即目标数据。它是根据用户的需 要从源数据库中抽取的一组数据。数据预处理主要针对数据选取阶段产生的数 据进行加工，消除噪音、推导计算缺值数据、消除重复记录、完成数据类型的 转换( 如将连续值数据转换为离散的数据，以便于符号归纳，或是将离散型的 转换为连续型值，以便于神经网络归纳) 等。当数据挖掘的对象是数据仓库时， 一般来说，数据预处理已经在生成数据仓库时完成了。数据变换的主要目的消 减数据维数或降维( d i m e n s i o nr e d u c t i o n ) ，即从初始特征中找出真正有用的特 征以减少数据挖掘时要考虑的特征和变量个数。 2 、数据挖掘 数据挖掘首先要确定挖掘的任务，如数据总结、分类、聚类、关联规则发 现、序列模式发现等。在确定任务后。就要决定采用何种挖掘算法。同样的挖 掘任务可以采用不同的挖掘算法来实现。在选择挖掘算法时应考虑以下两个问 题：一是根据数据的不同特点来选择与之对应的挖掘算法；二是要考虑用户和 实际运行系统的要求，有的用户可能想得到描述性的、容易理解的知识，而有 的用户可能想得到前瞻性的或是预测性的知识。完成上述准备工作后，就可以 通过挖掘算法来实施挖掘操作了。 3 、结果的表示与评价 数据挖掘阶段发现出来的模式，经过用户、专家或机器的评价，可能存在 冗余或无关的模式，也可能不满足用户的要求。因此，需要对所发现的模式进 行解释，去掉多余或无关的模式。有时为了得到有效的知识，需要重新进行整 个挖掘过程，如重新选取数据、采用新的数据变换方法，设定新的数据挖掘参 数，甚至换一种挖掘算法。另外，数据挖掘的最终结果是面向用户的，因此可 能还要对所发现的模式进行可视化，或是将结果转换成用户容易接受的表示形 式，如将分类决策树转换成规格化的“i f t h e n ”形式。 1 4 k 叻的基本任务 数据挖掘的任务就是发现隐藏在数据中的模式“”。它所发现的模式一 般可分为两大类：描述型( d e s c r i p t i v e ) 的模式和预测型( p r e d i c t i v e ) 模式“”1 。 描述型的模式是对当前数据中存在的事实做规范的描述，它所揭示的是当前数 据的一般特性；预测型模型则是以时间为关键参数，对于时间序列型数据，根 据其历史和当前的值去预测其未来的值。根据模式的特征，预测和描述可以通 过下面的任务来完成。 l 、分类分析( c l a s s i f i c a t j o n ) 分类就是构造一个分类模型，把具有某些特征的数据项映射到某个给定的 类别上。这个过程分为两步：模型的创建和模型的使用。模型的创建是指通过 对训练数据集的学习建立分类模型；模型使用是指使用分类模型对测试数据和 新的数据进行分类。其中的训练数据集是带有类标号的，也就是在分类之前， 要划分的类别是已经确定的，通常分类模型是以分类规则、决策树或数学表达 式的形式给出的。 分类模式往往表现为一棵树，从树根开始搜索，沿着数据满足的分支走。 走到树叶时就能确定类别。已有许多数据分类方法，如决策树方法、统计方法 及粗糙集方法等。m e t h a 、a g r a w a l 、r i s s a n e n 等人开始研究面向数据库的分类 方法。j h a n 等人在他们开发的知识发现系统d b m i n e r 中采用了基于概括的决 策树方法，该方法集成了面向属性的归纳和决策归纳技术。 2 、关联规则( a s s o c i a t i o nr u l e s ) 关联模式是数据项之间存在的关联规则，是在同一事件中出现不同项之间 的相关性，例如客户在一次购买活动中所购买的不同商品之间的关联性。在数 据挖掘领域，对于关联模式的研究开展得比较深入，人们提出了多种关联规则 挖掘算法，如a p r i o r i 、d h p 、p a r t i t i o n 、s a m p l i n g 、f p g r o 讯h 等算法”。 这些算法能够发现数据库中形如“8 0 的客户在一次购买活动中购买x 商品的 同时也购买y 商品”之类的知识。有关关联规则挖掘的内容将在第二章作详细 介绍。 3 、聚类分析( c l u s t e r i n g ) 聚类就是根据数据的属性对一系列未分类数据进行类别划分，把一组个体 按照相似性分成若干个类或簇，即“物以类聚”。其目的是使类间的数据差别尽 可能大，类内的数据差别尽可能小，即“最小化类问的相似性，最大化类内的 相似性”原则。与分类模式不同的是聚类中要划分的类别是未知的，它是不依 赖于预先定义的类和带类标号的训练数据集的非监督学习( u n s u p e r v i s e d l c a r n i n g ) ，无需背景知识，其中类的数量由系统按照某种性能指标自动确定。 聚类分析的方法有很多，其中包括系统聚类法、分解法、加入法、动态聚类法、 模糊聚类法、运筹方法等。采用不同的聚类方法，对于相同的记录集合可能有 不同划分结果。 4 、回归分析( r e g r e s s i o n ) 回归模式的函数定义与分类模式相似，主要差别在于分类模式采用离散预 测值( 例如类标号) ，而回归模式则采用连续的预测值。它通过具有已知值的变 量来预测其他变量的值。在最简单的情况下，回归采用的是类似于线性回归的 标准统计技术。但在大多数现实世界中的问题是不能用简单的线性回归所能预 测的。如商品的销售量、股票价格、产品合格率等，很难找到简单有效的方法 来预测，因为要完全地描述这些事件的变化需要上百个变量，而且这些变量本 身往往都是非线性的。为此学术界提出了很多试图解决这个问题方法。如逻辑 回归、决策树和神经网络等。 5 、序列模式分析( s e q u e n t i a l ) 序列模式分析和关联规则分析相似它是描述基于时间或其他序列的经常 发生的规律或趋势，并对其进行建模。它能发现数据库中形如“在某一段时间 内，7 5 的顾客购买商品a ，接着购买商品b ，然后又购买商品c ，即序列a b c 出现的频度较高”之类的知识。序列模式将关联模式和时间序列模式 结合起来，重点考虑数据之间在时间维上的关联性。在进行序列模式挖掘时主 要有以下几个问题值得注意：首先是序列的持续时间，也就是某个时间序列的 有效时间或者是用户选择的一个时间段；其次是时间折叠窗口，即在某一段时 间内发生的事件可以被看作是同时发生的：最后是所发现的模式时问间隔。 6 、偏差分析( d e v i a t i o n ) 偏差分析是指对差异或极端特例的描述如聚类划分外的偏离值。在大多 数据挖掘方法中都是将这些偏差信息作为噪声而丢掉，然而在一些实际应用中， 这种罕见的数据可能比正常的数据更有价值。比如网络的入侵检测和信用卡的 欺诈检测等。我们可在通过这些异常数据的偏差来分析其中的原因，以便对其 采用相应的措施。 1 5 k d d 的常用方法 k d d 是一门新兴的研究领域，其技术基础是人工智能( a r t i f i c i a l i n t e l j i g e n c e ) 。它借鉴了信息论、数理逻辑、进化计算、神经计算和统计学等理 论和算法，在此介绍几种主流的方法。 l 、统计分析方法 统计分析方法是利用统计学、概率论的原理对数据库中的各属性进行统计 分析，从而找出其中的关系和规律。统计分析方法是最基本的数据挖掘方法之 一m 1 。常用的统计分析方法有【2 3 2 4 l ： 判别分析法：建立一个或多个翔别函数，并确定一个判别标准，然后对未 知属性的对象根据观测值将其划分归为已知类别中的一类。 因子分析法：用较少的综合变量来表达多个观察变量。根据相关性大小把 变量分组，使得各组内的变量之间相关性较高，不同组变量的相关性较低。 相关分析和回归分析法：相关分析是用相关关系来度量变量间的相关程度。 回归分析是用数学方程来表示变量间的数量关系，方法有线性回归和非线性回 归。 偏最小二乘回归法：是一种新型的多元统计数据分析方法，它主要研究的 是多因变量对多自变量的回归建模，特别当各变量内部高度线性相关时，用偏 最小二乘回归法更有效。另外，偏最小二乘回归较好地解决了样本个数少于变 量个数等问题。 在数据挖掘中，统计分析方法适用于分类挖掘和聚类挖掘。 2 、粗集方法 粗集( r o u g hs e t ) 理论的特点是不需要预先给定某些特征或属性的数量描 述，而是直接从给定问题出发，通过不可分辨关系和不可分辨类确定问题的近 似域，从而找出该问题中的内在规律。粗集理论同模糊集、神经网络、证据理 论等其它理论均成为不确定性计算的一个重要分支。”“ 粗集理论是由波兰华沙理工大学的z p a w i a k 教授于1 9 8 2 年提出的一种研 究不完整、不确定知识和数据的表达、学习及归纳的理论方法，现已成为数据 挖掘研究中的最有力工具，也是最有发展前途的。粗集理论采用了上近似集合 ( u p p e ra p p r o x i m a t i o n s ) r + 、下近似集合( 1 0 w e ra p p r o x i m a t i o n s ) r 和边界 ( b o u n d a r yw g i o n ) b n 。来定义粗糙集，即 r f x ) = u y u r ：y n x 由) 一一上近似 r 。( x ) = u y u ，r ：y x ) 一一下近似 b n r - r ( x ) 一凡( x ) 一一边界。 粗糙集合理论可以用于分类，发现不准确数据或噪声数据内在的联系。找 出可以描述给定数据集中所有概念的属性子集是个n p 一难题。在给定的现实世 界数据中，往往有些类不能被可用的属性区分，则可以用粗糙集合来近似地定 义这些类。根据目前已有的绘定问题的知识，将问题的论域进行划分，然后对 划分后的每一个组成部分确定其对某一概念的支持度，即肯定支持此概念或不 支持此概念和模糊概念。上述情况分别用3 个近似集合来表示。即将知识定义 为对事物的分类能力。这种能力分别由上近似集、下近似集、等价关系等概念 来体现2 ”。 目前，基于粗集的数据挖掘在以下方面有待深化“。 ( 1 ) 粗集和其它软计算方法的进一步结合问题； ( 2 ) 粗集知识采掘的渐增算法； ( 3 ) 粗集基本运算的并行算法及硬件实现，将大幅度改善数据挖掘的效 率。 已有的粗集软件适用范围还很有限；决策表中的实例数量和属性数量受 限制；面对大量的数据，有必要设计高效的启发式简化算法或研究实时性较好 的并行算法： ( 4 ) 扩大处理属性的类型范围，实际数据库的属性类型是多样的，既有离 散属性，也有连续属性：既有字符属性，也有数值属性。粗集理论只能处理离散 属性，因此，需要设计连续值的离散算法。 3 、遗传算法 遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 是一种基于生物进化过程的组合优化 方法，它是生物学和计算机相结合的产物，由美国密西根大学的d jh o l l a n d 教 授和他的同事们在1 9 7 5 年首次提出的”。根据适者生存的原则模拟自然界的 生命进化机制，形成当前群体适合的规则组成新群体，以及这些规则的后代。 基于这些思想，根据遗传算法的最适合模型，并进一步对数据模型进行优化。 由于遗传算法是一种弱算法，具有高效性和灵活性的特点，在数据挖掘中也用 于评估其他算法的的适应度。 遗传算法擅长于数据聚类，通过事件的类比和空间上的类比，可以把大量 繁杂的信息数据进行系统化、条理化，从而找出数据之间的内在关系，得出有 用的概念和模式。再建立数据模式时。将遗传算法与神经网络相结合，可以更 好地提高模型的适应性。因此遗传算法广泛应用于自动控制、机器学习、模式 识别和组合优化等领域。 4 、神经网络 神经网络( n e u r a ln e t w o r k ) 是由多个神经元按照某种方式相互连接形成， 靠网络状态对外部输入信息的动态响应来处理信息，网络的信息分布式存储于 连接权系数中，使网络具有很强的容错性和鲁棒性。神经网络的核心是结构和 算法，例如h o p f i e l d 网就是以结构见长，而b p ( b a c kp r o p a g a t i o n ) 网是以算 法见长。 神经网络和基于符号的传统a i 技术相比，具有直观性、并行性和抗噪声 性。目前，已出现了许多网络模型和学习算法，主要用于分类、优化、模式识 别、预测和控制等领域。在数据挖掘领域，主要采用前向神经网络提取分类规 则。 神经网络模拟人的形象直觉思维，其中，最大的缺点是“黑箱”性，人们难 以理解网络的学习和决策过程。因此，有必要建立“白化”机制，用规则解释 网络的权值矩阵，为决策支持和数据挖掘提供说明，使从网络中提取知识成为 自动获取的手段。通常有两种解决方案： ( 1 ) 建立一个基于规则的系统辅助。神经网络运行的同时，将其输入和输 出模式给基于规则的系统，然后用反向关联规则完成网络的推理过程。这种方 法把网络的运行过程和解释过程用两套系统来实现，开销大，不够灵活； ( 2 ) 直接从训练好的网络中提取分类规则。这是当前数据挖掘使用得比较 多的方法。 从网络中采掘规则，主要有以下倾向： ( 1 ) 网络结构分解的规则提取。它以神经网络的隐层结点和输出层结点为 研究对象，把整个网络分解为许多单层子网的组合。这样研究较简单的子网， 便于从中挖掘知识。f u 的k t 算法和t 0 w e l l 的m o f m 算法是有代表性的方 法。k t 方法的缺点是通用性差，且当网络比较复杂时，要对网络进行结构的剪 枝和删除冗余结点等预处理工作。 ( 2 ) 神经网络的非线性映射关系提取规则。这种方法直接从网络输入和输 出层数据入手，不考虑网络的隐层结构，避免了基于结构分解的规则提取算法 的不足。s e s t i t o 等人的相似权值法，以及c s w 算法( 将网络输入扩展到连续取 值) ，是其中的两种典型算法。 当然，在数据挖掘领域，将神经网络用于数据挖掘，重点要解决好以下两个 问题：一是降低训练时间，二是挖掘结果的可理解性。 5 、决策树方法 决策树( d e c i s i o nt r e e ) 是一个类似于流程图的树型结构，其中树的每一个内 部节点代表对一个属性的测试，其分支代表测试的每一个结果；树的每一个叶 子节点代表一个类别。决策树通过一系列的规则对数据进行分类。目前许多基 于规则进行归纳的商用数据挖掘系统都是采用决策树方法。 决策树方法起源于概念学习系统c l s ( c o n c e p tl e a r n i n gs y s t e m ) ，然后发 展到i d 3 方法，最后发展为能处理连续属性的c 4 5 ，主要用于基于数据的属性 值进行归纳分类。c l s 的思路是找出最有分辨能力的属性，把数据库划分为多 个子集( 对应树的一个分枝) ，构成一个分技过程，然后对每一个子集递归调用 分枝过程，直到所有子集包含同一类型的数据。最后得到的决策树能对新的例 子进行分类。c l s 的不足是它处理的学习问题不能太大。为此，q u i n l a n 提出 了著名的i d 3 学习算法，通过选择窗口来形成决策树。 从示例学习最优化的角度分析，理想的决策树分为3 种：叶子数最少； 叶子结点深度最小；叶结点数最少且叶子结点深度最小。寻找最优决策树 已被证明是n p 困难问题。i d 3 算法借用信息论中韵互信息( 信息增益) ，从单 一属性分辨能力的度量，试图减少树的平均深度，却忽略了叶子数目的研究。 其启发式函数并不是最优的，存在的主要问题有： ( 1 ) 互信息的计算依赖于属性取值的数目多少，而属性取值较多的属性并 不一定最优； ( 2 ) i d 3 是非递增学习算法； ( 3 ) i d 3 决策树是单变量决策树( 在分枝结点上只考虑单个属性) ，许多复 杂概念的表达困难，属性问的相互关系强调不够，容易导致决策树中子树的重 复或有些属性在决策树的某一路径上被检验多次： ( 4 ) 抗噪声性差，训练例子中，正例和反例的比例较难控制。针对上述问题， 出现许多较好的改进算法，s c h l i m m e r 和f i s h e r 设计了i d 4 递增式算法通过 修改i d 3 算法，在每个可能的决策树结点创建一系列表，每个表由未检测属性 值及其示例组成，当处理新例时，每个属性值的正例和反例递增计量。在i d 4 的基础上，u t g o f f 提出了i d 5 算法，它抛弃了旧的检测属性下面的予树从下 面选择属性构造树。此外，还有许多算法使用了多变量决策树的形式，著名的 c 4 5 系统也是基于决策树的。 除上述方法外，还有把数据与结果转化表达成可视化形式的可视化技术、 云模型方法和归纳学习等方法伸 。 16 k d d 的应用领域及发展前景 1 6 1k d d 的应用领域 数据挖掘技术虽然出现的比较晚，但由于其巨大的潜在利用价值，发展速 度十分迅猛，目前已经出现了很多实用产品。从早期在商业领域到当前的电子 商务领域，数据挖掘技术已经广泛应用于很多领域，但每个领域的应用都有其 特定的应用背景。 l 、数据挖掘在商业零售业中的应用 商业零售业是数据挖掘应用较为活跃的一个领域。对于销售商来说，了解 客户的购买习惯和趋势是非常重要的。通过关联规则的挖掘，分析客户对商品 的需求情况，发现客户潜在的需求特征，有目的地开展广告和营销业务，调整 商品价格和货架设计，以刺激商品的销售，扩大销售范围和销售规模，从而增 加销售量。 2 、数据挖掘在金融业中的应用 金融领域的数据相对比较完整、可靠和高质量，这有利于系统化的数据分 析和数据挖掘。数据挖掘在这一领域的应用较为成熟，也取得了较好的预期效 果和经济效益。通过分析金融市场波动因素，建立预测模型，进行投资分析和 预测，提高对市场波动的适应能力，为投资决策提供科学的依据。例如，贷款 偿付预测和客户信用政策分析对银行业务是相当重要的。有很多因素会对贷款 偿还效能和客户信用等级计算产生不同程度的影响。数据挖掘的方法，如特征 选择和属性相关性计算，有助于识别重要因素，剔除非相关因素。例如，与贷 款偿还风险相关的因素包括贷款率、贷款期限、负债率、偿还与收入比例、客 户收入水平、受教育程度、居住地区、信用历史等等。分析客户偿还的历史信 息可以发现偿还与收入