（计算机软件与理论专业论文）基于概念格的数据挖掘的研究与实现.pdf

摘要 随着i n t e r n e t 的广泛应用，导致庞大的数据库日益增多，为了从这些数据 中提取出对数据库拥有者有价值的信息，数据挖掘这门学科应运而生。目前数据 挖掘技术之所以被认为具有令人兴奋的研究前景，是因为它能够获得广泛的应 用。 1 9 9 3 年，i b wa l m a d e nr e s e a r c hc e n t e r 的p , a k e c ha g r a w a l 等人首先提出 关联规则挖掘。关联规则是数据挖掘众多功能中的一种，也是目前最重要，最活 跃，最为广泛应用的数据挖掘方法之一，这使得关联规则作为数据挖掘的一种重 要模式，一直倍受广泛的关注。 概念格是从数据中进行概念发现的一种数学工具，可通过h a s s e 图表现出概 念之间的层次关系，概念格作为一种用于数据分析的形式化的工具，已在信息检 索、数字图书馆、软件工程和知识发现等方面得到应用，备受国内外学者的重视。 本文主要关注基于概念格的数据挖掘的研究，重点是基于索引链表的相对约 简概念格( 简称相对约简格) 的关联规则的挖掘，内容主要涉及基于索引链表的 相对约简格的建造及在此基础上的关联规则的挖掘。 文章首先讨论了数据挖掘的研究现状及基本任务方法，重点讨论了关联规则 算法的研究，经典算法a p r i o r i 的实现，优化，以及应用领域和关联规则挖掘中 需要注意的事项。 在此基础上，以基于索引链表的相对约简格模型为基础，分析了基于索引链 表的相对约简格与关联规则之间的关系，描述了基于索引链表的相对约简格进行 关联规则挖掘的理论框架，讨论了基于索引链表的相对约简概念格结构生成频繁 概念格的思想，并给出构造算法及基于索引链表的相对约简格的关联规则挖掘算 法的实现，并与经典关联规则算法a p r i o r i 进行对比，通过实验证明了算法的正 确性及优越性，尤其在处理大型数据库中的优势。 关键词：数据挖掘，关联规则，概念格 西北大学信息科学与技术学院硕士研究生论文 a b s t r a c t a b s t r a c t a l o n gw i t hw i d e s p r e a da p p l i c a t i o ni ni n t e r n e t ，l e a d i n gt ol a r g e d a t a b a s eb e c a m em o r ea n dm o r e ，i no r d e rt oo b t a i nv a l u a b l ei n f o r m a t i o n f o rt h eo w n e ro fd a t a b a s ef r o mt h ed a t a , d a t am i n i n ga r i s ea tt h eh i s t o r i c m o m e n t b e c a u s ed a t am i n i n gg a i n sm o r ea p p l i c a t i o n ，a tp r e s e n ti th a s e x c i t i n gs t u d yp r o s p e c t i n1 9 9 3 r a k e c ha g r a w a la ti b ma l m a d e nr e s e a r c hc e n t e rm a k e s a s s o c i a t i o nr u l e sm i n i n g a s s o c i a t i o nr u l e si so n eo fm a n yf u n c t i o na t d a t am i n i n g ，i sm o r ei m p o r t a n t ，m o r ea c t i v e ，m o r ew i d e s p r e a da p p l i c a t i o n w a y ，s oi ta sf o ra ni m p o r t a n tp a t t e r na td a t am i n i n g 。i sd o u b l yp a i dc l o s e a t t e n t i o n c o n c e p tl a t t i c ei sam a t h e m a t i c si m p l e m e n tf o u n d e dw i t hc o n c e p t i o n f r o md a t a ；i tc a ns h o wa l l a r r a n g e m e n to fi d e a sr e l a t i o nb e t w e e n c o n c e p t i o n sw h i c hi sp a s s e db yh a s s e a sf o ra ni m p l e m e n tw h i c hi sp u t t e d i n t ou s ea td a t aa n a l y z e ，i ti su s e dw i d e l ya ti n f o r m a t i o nr e t r i e v a l ，a t f i g u r e1i b r a r y ，s o f t w a r ee n g i n e e r i n ga n dk n o w l e d g ef i n d i n ge c ta n di s t a k e ns e r i o u s l yb ys c h o l a ro fh o m ea n da b r o a d t h i sp a p e r f o c u si so nd a t am i n i n gb a s e do nc o n c e p tl a t t i c ea n d t h ek e yi st h ea s s o c i a t i o nr u l e sb a s e do nc o n c e p tl a t t i c er r e c l ( r r e c l l a t t i c e ) o ft h el i s ti n d e x ，t h ec o n t e x tw a si n v o l v e dw i t hg e n e r a t i o no f c o n c e p tl a t t i c eb a s e do nl i s ti n d e xa n do nt h i sb a s i so ft h em i n i n g a s s o c i a t i o nr u l e s f i r s to ft h ep a p e rd is c g s s e st h er e s e a r c ha n dt h eb a s i ct a s k so f d a t am i n i n g ，t h ef o c u s e so fd i s c u s s i o na r et h ea s s o c i a t i o nr u l e sa l g o r i t h m a ，t h er e a l i z a t i o na n do p t i m i z a t i o no ft h ec l a s s i c a la l g o r i t h ma p r i o r i ， a n dt h en e e dt op a ya t t e n t i o ni na s s o c i a t i o nr u l e sa n da p p l i c a t i o nf i e l d s o nt h e s eb a s i s ，t h ep a p e ra n a l y s i st h er e l a t i o n s h i pb e t w e e n r r e c ll a t t i c eb a s e do nl i s ti n d e xa n da s s o c i a t i o nr u l e s a n dd e s c r i b e s 西北大学信息科学与技术学院硕士研究生论文 a b s 眺a t h et h e o r e t i c a lf r a m e w o r ko ft h ea s s o c i a t i o nr u l e st h a tb a s e do nr r e c l l a t t i c eo ft h el i s ti n d e x t h ep a p e rd i s c u s s e si d e a t h a tg e n e r a t e s f r e q u e n tc o n c e p tl a t t i c eb yt h em o d e lo ft h er r e c ll a t t i c eb a s e do nl i s t i n d e x c o n s t r u c t i o na l g o r i t h mg i v e n ，a n dr e a l i z e dt h ea s s o c i a t i o nr u l e s b a s e do nr r e c ll a t t i c eo ft h el i s ti n d e x ，c o m p a r i s o nw i t ha p r i o r it h a t i 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 ，b yt h ee x p e r i m e n t s ，p r o v e d t h ea l g o r i t h m st h ec o r r e c t n e s sa n ds u p e r i o r i t y 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 ，c o n c e p tl a t t i c e 西北大学信息科学与技术学院硕士研究生论文 i i i 西北大学学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻 读学位期问论文工作的知识产权单位属于西北大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被 查阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学 位论文。同时，本人保证，毕业后结合学位论文研究课题再撰写的文 章一律注明作者单位为西北大学。 保密论文待解密后适用本声明。 学位论文作者签名：经i 墨 指导教师签名： 妒7 年月一日w 年 盏9 查坚! l 月钾吕 ? 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，本论文不包含其他人已经发表或撰写过的研究成果，也不包含 为获得西北大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者签名：喀f ；毫 渺7 年厂月一日 1 研究背景及意义 绪论 近年来，随着网络的不断传播，带动了信息技术的发展，大量激增的数据 迫切需要转化为有用的知识，如果能把这些知识从大量的数据中抽取出来，就可 以为社会、企业创造出更多潜在的财富和利润，而就目前而言，各个行业的竞争 日趋激烈，因此如何更好的组织管理和利用信息变得尤为重要。数据挖掘概念就 是从这样的商业角度开发出来的，并且已经成为决策支持的新技术。 数据挖掘是实用性很强的技术，是目前国际上数据库和信息决策领域的前 沿研究方向之一，它可以帮助人们对数据进行更深层次的分析，引起了学术界和 工业界的广泛关注。一些国际高级别的工业研究实验室和众多的学术单位都在这 个领域开展了各种各样的研究计划，大量的研究原型和应用系统纷纷出现。数据 挖掘可以用在信息管理、查询响应、决策支持、图像处理和过程控制等许多方面。 数据挖掘技术是人工智能，数据库和统计理论的结合技术，具有较为广泛 的应用前景。数据挖掘技术从一开始就是面向应用的，它不仅是面向特定数据库 的简单检索查询，而且要对这些数据进行微观、甚至是宏观的统计、分析和推理， 从而为解决实际问题起到指导作用，发现事件问的相互关联，利用原有的数据对 未来活动进行预测等等。 数据挖掘是一门交叉学科，涉及数据库、人工智能、数理统计等多方面知识， 而其算法是决定挖掘效率和市场竞争力的关键因素之一，因此，本文在对数据挖 掘技术进行全面研究的同时，主要对数据挖据中的关联规则算法进行研究，并提 出一种基于概念格的关联规则的构造方法。 关联规则模式是数据挖掘中比较重要的一种知识模式。关联规则是形如 x j y 的规则，其中x 、y 称为项目集。且x n y 为空集。在数据库中若有j 的实例同时包含工和y ( 或s 的实例包含x u y ) 则关联规则x j y 的支持率 为s 若c 的包含项目集x 的事务也包含项目集y ，则关联规则x j y 的置 信度为c o , 。一般来说，需要找出的是支持率和置信度分别大于或等于用户指定 的最小支持率( m i n s u p ) 和最小置信度( m i n c o n f ) 的关联规则。由二元关系导出的 西北大学信息科学与技术学院硕士研究生论文 l 概念格作为一种非常有用的形式化工具，体现了概念内涵和外延的统一，反映了 对象与特征之间的联系以及概念的泛化与特化的关系，因此非常适于发现数据潜 在的规则。 概念格( c o n c e p tl a t t i c e ) 是根据二元关系提出的一种概念层次结构，是 数据分析与规则提取的一种有效工具。基于概念格理论的知识发现的理论研究和 应用近年来受到重视。目前，基于概念格数据挖掘的研究主要集中在：用概念格 改进知识发现过程，快速建格算法、格的修正和扩展技术的研究等。 本文在此背景下参考了大量的文献，对基于概念格的数据挖掘的关联规则的 方法进行了研究和改进，并通过实验对比取得了较好的效果，对其应用也有一定 的启发与借鉴意义。 2 本文主要组织框架 本文的主要研究了一些基于概念格的数据挖掘的关联规则方法，主要内容包 括： 第一部分是全文的序论，本章对数据挖掘进行了较为全面的综述。主要对数 据挖掘技术以及工具的研究，首先对数据挖掘技术和知识发现的概念进行了详细 的叙述，然后具体研究了数据挖掘技术的分类及相应的算法。 第二部分是关联规则算法的研究。首先介绍了关联规则算法的概念，然后结 合不同的关联规则类型研究相应的挖掘算法，重点针对经典频繁项集a p r i o r i 算 法进行了研究。 第三部分就概念格理论及其研究现状进行了讨论，并给出实例。并对概念格 的构建算法进行了研究、分析。 第四部分是全文的核心，首先讨论了概念格与关联规则的关系，在此基础上 讨论了基于索引链表的相对约简格的关联规则挖掘算法，并给出具体实现基于索 引链表的相对约简格的构建和基于索引链表的相对约简格的关联规则挖掘算法， 并通过实验验证了算法的正确性和优越性。 最后，是全文的总结，并对基于概念格的数据挖掘模型的发展和应用前景提 出了一些观点。 西北大学信息科学与技术学院硕士研究生论文 2 第一章数据挖掘 1 i 数据挖掘技术概述 第一章数据挖掘 i n t e r n e t 的广泛应用，导致庞大的数据库日益增多。这已经发生在人类耕耘 的几乎所有领域，从普通的( 比如超市业务数据、信用卡使用记录、电话呼叫清 单以及政府统计数据) 到不太普通的( 比如天体图像、分子数据库和医疗记录) 那么，能否从这些数据中提取出对数据库拥有者有价值的信息呢? 毫无疑问，人 们对这个问题的兴趣在不断增长，而且已经形成了致力于这个任务的一门学科， 称为“数据挖掘( d a t a m i n i n g ) ”。数据挖掘就是对观测到的数据集( 经常是很庞 大的) 进行分析，目的是发现未知的关系和以数据拥有者可以理解并对其有价值 的新颖方式来总结数据。 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提 取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。一 个典型的数据挖掘系统如图i 1 所示。 数据 图i 1 数据库、数据仓库或其他信息库：它表示数据挖掘的对象是由一个( 或一组) 西北大学信息科学与技术学院硕士研究生论文 3 第一章数据挖掘 数据库、数据仓库、电子表格或其他类型的信息库组成。通常需要使用数据清洗 和数据集成操作，对这些数据对象进行初步的处理。 数据库或数据仓库服务器：根据用户的挖掘请求，数据库或数据仓库服务器 负责提取相关数据。知识库：这是领域知识，这些知识将用于指导数据挖掘的搜 索过程，或者用于帮助对挖掘结果的评估。挖掘算法中所使用的用户定义的阈值 就是最简单的领域知识。 数据挖掘引擎：这是数据挖掘系统最基本的部分，由一组功能模块组成，用 于特征化、关联、分类、聚类分析以及演变和偏差分析。 模式评估模块：该模块可根据趣味标准( i n t e r e s t i n g n e s sm e a s u r e s ) ，协助 数据挖掘模块聚焦挖掘更有意义的模式知识。模式评估模块也可以与挖掘模块集 成在一起，这依赖于所用的数据挖掘方法的实现。 图形用户界面：该模块在用户和数据挖掘系统之间通信，允许用户与系统交 互。一方面用户通过该模块将自己的挖掘要求或任务提交给挖掘系统，以及提供 挖掘搜索所需要的相关知识：另一方面系统通过该模块向用户展示或解释数据挖 掘的结果或中间结果。此外，该模块也可以帮助用户浏览数据对象内容与数据定 义模式、评估所挖掘的模式知识，以及以多种形式展示挖掘出的模式知识 1 1 1 数据挖掘的历史背景 数据挖掘技术是人们长期对数据库技术进行研究和开发的结果。起初各种商 业数据是存储在计算机的数据库中的，然后发展到可对数据库进行查询和访问， 进而发展到对数据库的即时遍历，数据挖掘使数据库技术进入了一个更高级的阶 段，它不仅能对过去的数据进行查询和遍历，并且能够找出过去数据之间的潜在 联系，从而促进信息的传递数据挖掘是一个逐渐演变的过程。电子数据处理的 初期，人们就试图通过某些方法来实现自动决策支持，当时机器学习成为人们关 心的焦点。机器学习的过程就是将一些已知的并已被成功解决的问题作为范例输 入计算机，机器通过学习这些范例总结并生成相应的规则，这些规则具有通用性， 使用它们可以解决某一类的问题。随后，随着神经网络技术的形成和发展，人们 的注意力转向知识工程，知识工程不同于机器学习那样给计算机输入范例，让它 生成出规则，而是直接给计算机输入已被代码化的规则，而计算机是通过使用这 西北大学信息科学与技术学院硕士研究生论文 4 第一章数据挖掘 些规则来解决某些问题。专家系统就是这种方法所得到的成果，但它有投资大、 效果不甚理想等不足。8 0 年代人们又在新的神经网络理论的指导下，重新回到 机器学习的方法上，并将其成果应用于处理大型商业数据库。在8 0 年代末出现 一个新的术语，它就是数据库中的知识发现，简称k d d ( 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 ) 它泛指所有从源数据中发掘模式或联系的方法，人们接受了这个术 语，并用k i ) d 来描述整个数据发掘的过程，包括最开始的制定业务目标到最终的 结果分析，而用数据挖掘( d a t am i n i n g ) 来描述使用挖掘算法进行数据库中的 知识发现的子过程。但最近人们逐渐开始发现数据挖掘中有许多工作可以由统计 方法来完成，并认为最好的策略是将统计方法与数据挖掘有机的结合起来。 研究数据挖掘的历史，可以发现数据挖掘的快速增长是和商业数据库的空前 速度增长分不开的，并且九十年代较为成熟的数据仓库正同样广泛地应用于各种 商业领域。从商业数据到商业信息的进化过程中，每一步前进都是建立在上一步 的基础上的。下表1 1 给出了数据进化的四个阶段，从中可以看到，第四步进化 是革命性的，因为从用户的角度来看，这一阶段的数据库技术已经可以快速地回 答商业上的很多问题了。 进化阶段时间段生产厂家技术支持产品特点 数据收集6 0 年代m m 、c d c 等磁带提供静态历史数 据 数据访问8 0 年代 o r c a l 、s y b a s e 、 关系数据库、在记录中动态 i e i m 、i n f o r m i x 等s q l历史数据信息 p i l o t 、c o m s h a r e 、联机分析处提供回溯的动 数据仓库9 0 年代 a r b o r 、c o g n o s 等 理态的历史数据 p i l o t 、l o c k h e e d 、多处理系统、可提供预测性 数据挖掘2 1 世纪 m m 、s g i 等海量系统信息 表1 1 特别要指出的是，数据挖掘技术从一开始就是面向应用的。它不仅是面向特 定数据库的简单检索查询调用，而且要对这些数据进行微观、中观乃至宏观的统 ， 计、分析、综合和推理，以指导实际问题的求解，发现事件间的相互关联，甚至 西北大学信息科学与技术学院硕士研究生论文 5 第一章数据挖掘 利用已有的数据对未来的活动进行预测。例如加拿大b c 省电话公司要求加拿大 s i m o n f r a s e r 大学k d d 研究组，根据其拥有十多年的客户数据，总结、分析并提 出新的电话收费和管理办法，制定既有利于公司又有利于客户的优惠政策。这样 一来，就把人们对数据的应用，从低层次的末端查询操作，提高到为各级经营决 策者提供决策支持。这种需求驱动力，比数据库查询更为强大。同时需要指出的 是，这里所说的知识发现，不是要求发现放之四海而皆准的真理，也不是要去发 现崭新的自然科学定理和纯数学公式，更不是什么机器定理证明。所有发现的知 识都是相对的，是有特定前提和约束条件、面向特定领域的，同时还要能够易于 被用户理解，最好能用自然语言表达发现结果。因此，数据挖掘的研究成果是很 有实际应用价值的 1 1 2 数据挖掘的研究现状 k d d 一词首次出现在1 9 8 9 年8 月举行的第l l 届国际联合人工智能学术会议 上。迄今为止，规模由原来的专题讨论会发展到国际学术大会，人数由二三十人 发展到七八百人，研究重点也逐渐从发现方法转向系统应用，并且注重多种发现 策略和技术的集成，以及多种学科之间的相互渗透。其他内容的专题会议也把数 据挖掘和知识发现列为议题之一，成为当前计算机科学界的一大热点。 此外，数据库、人工智能、信息处理、知识工程等领域的国际学术刊物也纷 纷开辟了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 技术专刊，所发表的5 篇论文代表了当时k d d 研究的最新 成果和动态，较全面地论述了k d d 系统方法论、发现结果的评价、k d d 系统设计 的逻辑方法，集中讨论了鉴于数据库的动态性冗余、高噪声和不确定性、空值等 问题，k d d 系统与其它传统的机器学习、专家系统、人工神经网络、数理统计分 析系统的联系和区别，以及相应的基本对策。随着数据挖掘研究逐步走向深入， 人们越来越清楚地认识到，数据挖掘的研究主要有3 个技术支柱，即数据库、 人工智能和数理统计。 目前，国外数据挖掘的发展趋势及其研究方面主要有：对知识发现方法的研 究迸一步发展，如近年来注重对b a y e s 方法以及b o o s t i n g 方法的研究和提高； 传统的统计回归法在k d d 中的应用；k d d 与数据库的紧密结合。在应用方面包括： 西北大学信息科学与技术学院硕士研究生论文 6 第一章数据挖掘 k d d 商业软件工具不断产生和完善，注重建立解决问题的整体系统，而不是孤立 的过程。用户主要集中在大型银行、保险公司、电信公司和销售业。国内从事数 据挖掘研究的人员主要在大学，也有部分在研究所和公司。所涉及的研究领域很 多，一般集中于学习算法的研究、数据挖掘的实际应用以及有关数据挖掘理论方 面的研究。 一份最近的g a r t n e r 报告中列举了在今后3 年5 年内对工业将产生重要影 响的5 项关键技术，其中k i ) d 和人工智能排名第一。同时，这份报告将并行计算 机体系结构研究和k d d 列入今后5 年内公司应该投资的l o 个新技术领域。从这 我们不难看出，数据挖掘的研究和应用受到了学术界和实业界越来越多的重视。 相信在不久的将来，数据挖掘技术必将给我们的生活带来巨大的变化。 1 1 3 数据挖掘的概念 从技术上来说，数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声 的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜 在有用的信息和知识的过程。还有很多和这一术语相近似的术语，如从数据库中 发现知识、数据分析、数据融合( d a t af u s i o n ) 以及决策支持等。人们把原始数 据看作是形成知识的源泉，就像从矿石中采矿一样原始数据可以是结构化的， 如关系数据库中的数据，也可以是半结构化的，如文本、图形、图像数据，甚至 是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学 的：可以是演绎的，也可以是归纳的。发现了的知识可以被用于信息管理、查询 优化、决策支持、过程控制等，还可以用于数据自身的维护因此，数据挖掘是 一门很广义的交叉学科，它汇聚了不同领域的研究者，尤其是数据库、人工智能、 数理统计、可视化、并行计算等方面的学者和工程技术人员。 从商业角度来说，数据挖掘也是一种新的商业信息处理技术，其主要特点是 对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中 提取辅助商业决策的关键性数据。 简而言之，数据挖掘其实是一类深层次的数据分析方法。数据分析本身已经 有很多年的历史，只不过在过去数据收集和分析的目的是用于科学研究，另外， 由于当时计算能力的限制，对大数据量进行分析的复杂数据分析方法受到很大限 西北大学信息科学与技术学院硕士研究生论文 7 第一章数据挖掘 制。现在，由于各行业业务自动化的实现，商业领域产生了大量的业务数据，这 些数据不再是为了分析的目的而收集的，而是由于纯机会的商业运作而产生。分 析这些数据也不再是单纯为了研究的需要，更主要是为商业决策提供真正有价值 的信息，进而获得利润。但所有企业面临的一个共同问题是：企业数据量非常大， 而其中真正有价值的信息却很少，因此从大量的数据中经过深层分析，获得有利 于商业运作、提高竞争力的信息，就像从矿石中淘金一样，数据挖掘也因此而得 名。 因此，数据挖掘可以描述为：按企业既定业务目标，对大量的企业数据进行 探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的 先进有效的方法。 1 1 4 数据挖掘的范围 追根溯源，数据挖掘”这个名字来源于它有点类似于在山脉中挖掘有价值的 矿藏。在商业应用里，它就表现为在大型数据库里面搜索有价值的商业信息。这 需要对巨量的材料进行详细地过滤，并且需要智能且精确地定位潜在价值的所 在。对于给定了大小的数据库，数据挖掘技术可以用它如下的超能力产生巨大的 商业机会： 自动趋势预测 数据挖掘能自动在大型数据库里面找寻潜在的预测信息。传统上需要很多专 家来进行分析的问题，现在可以快速而直接地从数据中间找到答案。一个典型的 利用数据挖掘进行预测的例子就是目标营销。数据挖掘工具可以根据过去邮件推 销中的大量数据找出其中最有可能对将来的邮件推销作出反应的客户 自动探测以前未发现的模式 数据挖掘工具扫描整个数据库并辨认出那些隐藏着的模式，比如通过分析零 售数据来辨别出表面上看起来没联系的产品，实际上有很多情况下是一起被售出 的情况。 数据挖掘技术可以让现有的软件和硬件更加自动化，并且可以在升级的或者 新开发的平台上执行当数据挖掘工具运行于高性能的并行处理系统上的时候，它 能在数分钟内分析一个超大型的数据库。这种更快的处理速度意味着用户有更多 西北大学信息科学与技术学院硕士研究生论文 第一章数据挖掘 的机会来分析数据，让分析的结果更加准确可靠，并且易于理解。此外，数据库 可以由此拓展深度和广度。深度上，允许有更多的列存在以往，在进行较复杂 的数据分析时，专家们限于时间因素，不得不对参加运算的变量数量加以限制， 但是那些被丢弃而没有参加运算的变量有可能包含着另一些不为人知的有用信 息现在，高性能的数据挖掘工具让用户对数据库能进行通盘的深度编历，并且 任何可能参选的变量都被考虑进去，再不需要选择变量的子集来进行运算了。广 度上，允许有更多的行存在。更大的样本让产生错误和变化的概率降低，这样用 户就能更加精确地推导出一些虽小但颇为重要的结论。 1 1 5 数据挖掘与传统分析方法的区别 数据挖掘与传统的数据分析( 如查询、报表、联机应用分析) 的本质区别是数 据挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信 息应具有先未知，有效性和实用性三个特征。先前未知的信息是指该信息是预先 未曾预料到的。既数据挖掘是要发现那些不能靠直觉发现的信息或知识，甚至是 违背直觉的信息或知识，挖掘出的信息越是出乎意料，就可能越有价值在商业应 用中最典型的例子就是一家连锁店通过数据挖掘发现了小孩尿布和啤酒之间有 着惊人的联系 1 2 数据挖掘的任务、方法 1 2 1 数据挖掘的任务 数据挖掘技术的目标是从大量的数据中，发现隐藏其后的规律或数据间的关 系，从而服务于决策。主要任务如下： 1 数据总结 数据总结又称数据约简，目的是对数据进行浓缩，给出它的紧凑描述。最简 单的数据总结方法是计算出数据库的各个字段上的求和值、平均值、方差值等统 计值，或者用直方图、饼状图等图形方式表示。数据挖掘主要关心从数据泛化的 角度来讨论数据总结。数据泛化是一种把数据库中的有关数据从低层次抽象到高 层次上的过程。为了不遗漏任何可能有用的数据信息，数据库中所包的数据或信 西北大学信息科学与技术学院硕士研究生论文 9 第一章数据挖掘 息总是最原始、最基本的信息，但人们有时希望能从较高层次的视图上处理或浏 览数据，因此需要对数据进行不同层次上的泛化以适应挖掘目的要求。数据泛化 目前主要有两种技术：多维数据分析方法和面向属性的归纳方法 多维数据分析方法是一种数据仓库技术，也称作联机分析处理( o l a p ) 。数 据仓库是面向决策支持的、集成的、稳定的、不同时间的历史数据集合。在数据 分析中经常要用到诸如求和、总计、平均、最大、最小等汇集操作，这类操作的 计算量特别大。因此一种很自然的想法是，把汇集操作结果预先计算并存储起来， 以便于决策支持系统使用。存储汇集操作结果的地方称作多维数据库。多维数据 分析技术已经在决策支持系统中获得了成功的应用，如著名的s a s 数据分析软件 包司使用了多维数据分析技术。 多维数据分析方法进行数据总结，针对的是数据仓库，数据仓库存储静态 的历史数据。为了处理联机数据，研究人员提出了一种面向属性的归纳方法。它 的思路是，直接对用户感兴趣的数据视图( 用一般的s q l 查询语言即可获得) 进行 泛化，而不是像多维数据分析方法那样预先将泛化数据存储在数据仓库中，方法 的提出者对这种数据泛化技术称之为面向属性的归纳方法。原始关系经过泛化操 作后得到的是一个泛化关系，它从较高的层次上总结了在较低层次上的原始关 系。有了泛化关系后，就可以对它进行各种深入的操作而生成满足用户需要的知 识。 2 数据分类 分类的目的是找到一个分类函数或分类模型，该模型能把数据库中的数据项 映射到给定类别中的某一个。分类目的是从历史数据纪录中自动推导出对给定数 据的推广描述，从而能对未来数据进行预测。要构造分类器需要有一个训练样本 数据集作为输入。训练集由一组数据库记录或元组构成，每个元组是一个由有关 字段( 又称属性或特征) 值组成的特征向量。分类器的构造方法有统计方法、机器 学习方法、神经网络方法等等。 统计方法包括贝叶斯法和基于事例的学习，对应的知识表示为判别函数和原 型事例。机器学习方法包括决策树法和规则归纳法。神经网络方法主要是b p 算 法( 前向反馈神经网络) ，b p 算法本质上是一种非线性判别函数。 分类应用的实例很多。例如，我们可将连锁超市网点分为好、一般和较差三 西北大学信息科学与技术学院硕士研究生论文 1 0 第一章数据挖掘 种类型，并以此分析这三种类型超市网点的各种属性，特别是位置、盈利情况等 属性，并决定他们分类的关键属性及相互间的关系。此后就可以根据这些关键属 性对每一个预期的超市网点进行分析，从而给管理者提供决策信息。 3 聚类 聚类是把一组个体按照相似性归成若干类别，即“物以类聚”它的目的是使 得属于同一类别的个体之间的距离尽可能的小，而不同类别上的个体间的距离尽 可能的大。聚类方法也主要包括统计方法、机器学习方法，神经网络方法。 在统计方法中，聚类称聚类分析，它是多元数据分析的三大方法之一( 其它两 种是回归分析和判别分析) 。它主要研究基于几何距离的聚类，如欧式距离、明 考斯基距离等。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动 态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。这种聚类方法是一种基于 全局比较的聚类，它需要考察所有的个体才能决定类的划分，因此它要求所有的 数据必须预先给定，而不能动态增加新的数据对象。 机器学习中聚类称作无监督归纳，因为和分类学习相比，分类学习的例子或 数据对象有类别标记，而要聚类的例子则没有标记，需要由聚类学习算法来自动 确定很多人工智能文献中，聚类也称概念聚类，因为这里的距离不再是统计方 法中的几何距离，而是根据概念的描述来确定的。当聚类对象可以动态增加时， 概念聚类则称是概念形成。 在神经网络中，有一类无监督学习方法：自组织神经网络方法。 4 关联规则发现 挖掘关联规则主要是针对事务型数据库，特别是售货数据，由于条形码技术 的发展，零售部门可以利用前端收款机收集存储大量的售货数据，如果对这些历 史事务数据进行分析，则可对顾客的购买行为提供极有价值的信息。例如，可以 帮助如何摆放货架上的商品，把顾客经常同时买的商品放在一起，帮助规划市场， 减少库存，对市场变化提供预测。由此可见，从事务数据中发现关联规则，对于 改进零售业等商业活动的决策非常重要。在事务数据库中存在非常多的关联规 则。本文介绍的改进a p r i o r i 算法是关联规则挖掘的重要方法。其主要原理是在 事务数据库数据矩阵化的基础上产生频繁集，然后由基于支持度、置信度及兴趣 度的评价系统产生合理的关联规则。 西北大学信息科学与技术学院硬士研究生论文 第一章数据挖掘 1 2 2 数据挖掘的方法 1 数理统计 数理统计是应用数学中最重要，数理统计是应用数学中最重要、最活跃的学 科之一，它在计算机发明之前就诞生了，迄今己有几百年的发展历史。如今相当 强大有效的数理统计方法和工具，已成为信息咨询业的基础。一旦人们有了从数 据查询到知识发现、从数据演绎到数据归纳的要求，概率论和数理统计就获得了 新的生命力，所以才会在数据挖掘和知识发现( d m k d ) 这个结合点上，立即呈现 出”忽如一夜春风来，千树万树梨花开”的繁荣景象。一向以数理统计工具和可 视化计算闻名的美国s a s 公司，领先宣布进入数据挖掘行列 2 机器学习 机器学习算法在很多应用领域被证明很有实用价值。它从不同的学科吸收 概念，包括人工智能、概率和统计、计算复杂性、信息论、心理学和神经生物学、 控制论以及哲学。 机器学习在以下几方面特别有用： 1 ) 数据挖掘问题，即从大量数据中发现可能包含在其中的有价值的规律； 2 ) 在某些困难的领域中，人们可能不具有开发出高效的算法所需的知识 ( 如，从图像库中识别人脸) ； 3 ) 计算机程序必须动态的适应变化的领域。 3 神经网络 神经网络越来越受到人们的关注，因为它为解决大复杂度问题提供了一种相 对来说比较有效的简单方法。神经网络可以很容易的解决具有上百个参数的问题 ( 当然实际生物体中存在的神经网络要比我们这里所说的程序模拟的神经网络要 复杂的多) 。神经网络常用于两类问题：分类和回归。 神经网络是模拟人类部分形象思维的能力。特别是可以利用人工神经网络解 决人工智能研究中所遇到的一些难题。人工神经网络理论的应用已经渗透到多个 领域，在计算机视觉、模式识别、智能控制、非线性优化、自适应滤波信息处理、 机器人等方面都取得了可喜的进展。 尽管神经网络的模型很多，但在数据挖掘中最为广泛使用的是反向传播网 络。反向传播网络( b a c k p r o p a g a t i o n ) 通过重复在网络中前后传递样本记录的方 西北大学信息科学与技术学院硕士研究生论文 1 2 第一章数据挖掘 式进行学习。 4 可视化 现代的数据可视化( g a t av i s u a l i z a t i o n ) 技术指的是运用计算机图形学和 图像处理技术，将数据换为图形或图像在屏幕上显示出来，并进行交互处理的理 论、方法和技术。它涉及到计算机图形学、图像处理、计算机辅助设计、计算机 视觉及人机交互技术等多个领域。 近年来，随着网络技术和电子商务的发展，提出了信息可视化( i n f o r m a t i o n v i s u a l i z a t i o n ) 的要求。我们可以通过数据可视化技术，发现大量金融、通信和 商业数据中隐含的规律，从而为决策提供依据。这已成为数据可视化技术中新的 热点 1 3 本章小结 本章介绍了数据挖掘的历史，研究现状、挖掘的范围、任务分类和方法等。 数据挖掘是人们对于藏在数据库中的知识发现的过程。它是对学科的交叉应用。 由于它能给决策者提供更具说服力、更可靠的决策信息，因此越来越得到人们的 重视，已成为当今计算机应用研究的热点。 西北大学信息科学与技术学院硕士研究生论文 第二章关联规则算法研究 第二章关联规则算法研究 1 9 9 3 年，i b ma l m a d e nr e s e a r c hc e n t e r 的r a k e c ha g r a w a l 等人首先提出 关联规则挖掘。关联规则是数据挖掘众多功能中的一种，也是目前最为重要和广 泛应用的数据挖掘方法之一关联规则是数据中一种简单但很实用的规则。最初 提出关联规则的动机是针对购物篮分析问题提出的，其目的是为了发现交易数据 库中不同商品之间的联系规则。例如，关联规则挖掘可用于发现交易数据库中不 同商品( 项) 之间的联系，从而找出顾客购买商品的行为模式，进而把它应用于 商品货架设计、货存安捧以及根据购买模式对用户进行分类等。我们通常会提出 这样的问题，“购买牛奶的顾客同时购买面包的可能性有多大? ”，“购买计算机 的顾客大多在哪个年龄段? ”等，这些都是属于关联规则数据挖掘需要解决的问 题。因此，关联规则反映了大量数据中项集之间的有趣联系之后诸多的研究人 员对关联规则的挖掘问题进行了大量研究。他们的工作涉及到关联规则的挖掘理 论探索、原有算法的改进和新算法的设计、并行关联规则挖掘 ( p a r a l l e l a s s o c i a t i o nr u l em i n i n g ) 以及数量关联规则挖掘( q u a n t i t i v e a s s o c i a t i o nr u l e m i n i n g ) 等问题。在提高挖掘规则算法的效率、适应性、可用 性以及应用推广等方面，许多学者进行了不懈的努力。 2 1 关联规则的基本概念及模型 定义2 1 1 关联规则挖掘的数据集记为d ( d 一般为事务数据库) ， d = f l ，乞，) ，f i = “，岛，) ( 七- - i ，2 ，开) 为一条事务；t k 中的元素 f ，= u = l ，2 ，办称为项目( i t e m ) 。 定义2 l2 设，= 毡，毛，f _ 是d 中全体项目组成的集合，的任何子集x 称为d 中的项目集( i t e m s e t ) ，l x 卜七称集合x 为| | 一项目集。设f t 和石分别 为d 中的事务和项目集，如果x f i ，则称事务f i 包含项目集z 定义2 1 3 数据集d 中包含项目集石的事务数称项目集x 的支持数，记 为吒项目集x 的支持度，记做：s u p p o r t ( x ) ， 西北大学信息科学与技术学院硕士研究生论文 第二章关联规则算法研究 s u p p o ，f ( x ) = 吒l d 其中i d i 是数据集d 的事务数。 若s u p p o r t ( x ) 不小于用户指定的最小支持度( 记作：m i n s u p p o r t ，简记为： m s ) ，则称x 为频繁项集f r e q u e n ti t e m s e t ( 或大项集) ，否则称x 为非频繁项 集( 或小项集) 。 定理2 1 1 设工、y 是数据集d 中的项目集， ( 1 ) 若x y ，则s u p p o ，f ( x ) _ s u p f o r t ( y ) ( 2 ) 若z j ，如果z 是非频繁项集，则j ，也是非频繁项集 ( 3 ) 若x y ，若y 是频繁项集，则z 也是频繁项集 由上述定义可知定理2 1 1 成立是显然的 定义2 1 4 若石、y 为项目集，且x n y = m ，蕴涵式x 】，称为关联规则 项目集( x u y ) 的支持度称为关联规则x y 的支持度，记做：飙| p 册州d s u p p o ( x jy ) = s u p p o r t ( x u y ) 关联规则z 等j ，的置信度记做：c o n f i d e n c e ( z jn ， c o n f i d e n c e ( z = ，y ) = s u p p o r t ( x u y ) s u p p o r t ( x ) 通常用户根据挖掘需要指定的最小置