（控制理论与控制工程专业论文）基于关联规则的数据挖掘可视化系统的实现.pdf

武汉理工人学硕士学位论文 摘要 随着当今时代信息的爆炸性增k ，数据的丰富带米了对强有力的数据分析工具的需 求。事实上，重要的决定常常不是基于数据库中信息丰富的数据，而是基于决策者的直 觉，而决策者缺乏从海量数据中提取有价值知识的工具。数据挖掘工具可以进行数据分 析，发现重要的模式，对商务决策，知识库。科学和医学研究做山重大贡献。数据和信 息之间的鸿沟要求系统开发数据挖掘工具将数据坟墓转换成知识“金矿”。 零售业作为数据挖掘的主要应用领域，积累了大量的销售数据。顾客购买历史记录， 货物进出消费与服务记录等。其数据量在不断的迅速膨胀，特别是由于日益增长的 w e b 或电子商务上的商业方式的方便和流行。这种发展趋势更体现了对一个强有力的数 据挖掘工具的需求。 本文的目的是实现一个基于关联规则数据挖掘可视化系统。系统提供了一个友好的 集成化可视界面，以指导用户交互的完成关联规则数据挖掘任务。系统将数据挖掘过程 分成数据源选择、数据预处理、数据分析、挖掘算法、模式表达几个部分。在进行数据 挖捌的过程中刚户可以分别与之交互，体现了系统的灵活性以及提高了数据挖掘的质量。 系统充分利删了数据库管理系统( s q ls e r v e r 2 0 0 0 ) 的部分工具如商洵分析、数据转换 等功能进行数据预处理工作实现了系统与关系数据库系统的一定程度的耦合。系统前 端采t 4v i s u a lb a s i c 提供一个可视的交互界面，通过调用执行存储过程、d t s 包和a d o 数据访问等方式屏蔽后台复杂的数据处理过程，为用户提供了一个友好的可视数据挖掘 任务的交互环境。系统以一个网络交易数据库为例，说明了本文实现的数据挖掘系统的 可行性，有用性及有效性，并将可视化技术融入其中，在数据分析以及知识的可视化表 达方面做出了一定的有意义的研究。数据挖拥：具中要实现的一个微重要的功能就是对 交易数据库中的商品进行分析，发现顾客购买商品之间的关联性。井将这种关联性以表 格的形式直观、简洁的展现在蚪| 户面前，以帮助分析决策，为零售业带来效益。 关键字：数据挖掘系统、关联规则、可视化、交易数据库 武汉理1 i 大学硕七学位论文 a b s t r a c t t h ee x p l o s i o no fi n f o r m a t i o nn o w a d a y sh a sb r o u g h tt h eh e a v yd e m a n do f p o w e r f u ld a t aa n a l y z e r st h a tc a l lh e l pt h ed e c i s i o n m a k e r sg e tu s e f u li n f o r m a t i o n h i d d e nb e l o wd a t a d a t am i n e r sw i l lm a k eg r e a tc o n t r i b u t i o n st ov a r i o u sf i e l d sl i k e b u s i n e s s ，r e p o s i t o r y , s c i e n c ea n dm e d i c i n ee t cb ya n a l y z i n gd a t aa n dd i s c o v e r i n g i m p o r t a n tp a t t e r n s o fd a t a t h eg u l fb e t w e e nd a t aa n dk n o w l e d g ec a l l sf o r p o w e r f u ld a t aa n a l y z e r s ，w i t hw h i c hw e c a nt u r nd a t a t o m b si n t og o l dk n o w l e d g e a sam a i na p p l i c a t i o nf i e l do fd a t am i n i n g ，r e t a i l i n gh a ss t o r e dh u g ea m o u n t o fd a t ao ns a l e s ，c u s t o m e rs h o p p i n gh i s t o r ye t c a n dt h ea m o u n to fd a t ai ss t i l l r i s i n g , e s p e c i a l l yw i t ht h ep o p u l a r i t ya n dc o n v e n i e n c eo fw e bs h o p p i n ga n d e l e c t r o n i cb u s i n e s s i nt h et h e s i s ，ad a t am i n i n gv i s u a l i z a t i o ns y s t e mh a sb e e ni m p l e m e n t e df o r t h e d i s c o v e r yo fa s s o c i a t i o nr u l e si naw e bt r a n s a c t i o nd a t a b a s e t h es y s t e mh i g h l y i n c o r p o r a t e sd a t as o u r c es e l e c t i o nm o d u l e ，d a t ap r e t r e a t m e n tm o d u l e ，d a t a e x p l o r a t i o nm o d u l e ，d a t am i n i n gm o d u l ea n dk n o w l e d g er e p r e s e n t a t i o nm o d u l e ， a n dm a k e sd a t ap r e t r e a t m e n tb yt a k i n gt h ea d v a n t a g eo fs o m et o o l so fr c l a t i o n a l d a t a b a s el i k eq u e r y , a n dd a t at r a n s f o r m a t i o n t h ep l a t f o r mi si m p l e m e n t e dw i t h v i s u a lb a s i ct h a tp r o v i d e sa f r i e n d l yi n t e r a c t i v ei n t e r f a c et ot h eu s e qw h i l ea l lt h e t r a n s a c t i o nd a t ai ss t o r e di nt h er e l a t i o n a ld a t a b a s e t h es y s t e mc o m p l e t e l yp r o v e s t h ed a t am i n e rf e a s i b l e ，v a l u a b l ea n de f f e c t i v eb ys e t t i n ga ne x a m p l eo faw e b t r a n s a c t i o nd a t a ，a n de m b e d ss o m ev i s u a l i z a t i o nt e c h n i q u e si n t oi tt or e a l i z es o m e i n t e r e s t i n gi n v e s t i g a t i o no nd a t av i s u a l i z a t i o na n dk n o w l e d g er e p r e s e n t a t i o n t h e m o s ti m p o r t a n tf u n c t i o no ft h i ss y s t e mi st oa n a l y s i st h ei t e m si nt h et r a n s a c t i o n d a t a b a s e ，a n dt of i n da s s o c i a t i o nr u l e sa m o n gt h ei t e m so ns a l e ，t h e nr e p r e s e n t s t h e mi nas i m p l ea n di n t u i t i o n i s t i cw a yt oh e l pd e c i s i o n s - m a k i n g k e y w o r d s ：d a t am i n i n gs y s t e m ，a s s o c i a t i o nr u l e s ，v i s u a l i z a t i o n ，t r a n s a c t i o n d a t a b a s e 武汉理一r = 火学硕士学位论文 1 1 背景 第1 章绪论 随着计算机技术和i n t e r n e t 技术的迅速发展，数据资源日益丰富。但是 数据资源中蕴含的知识却远远没有得到充分的挖掘和利用，“数据丰富而信息 贫乏”“1 的问题至今还很严重。如何将数据的最大价值挖掘出来，从中获得 更多的信息，已成为当务之急。近年来兴起的知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ) 和数据挖掘( d a t am i n i n g ) 技术就是在这种需求的基础上发展起 来的。 数据挖掘是从一个新的角度将数据库技术，机器学习，统计学等领域集 合起来，从更深层次中发掘存在于数据内部的有效的，新颖的，具有潜在效 用的乃至最终可理解的模式”1 。数据挖掘能预测未来趋势和行为，使商务活 动具有前瞻性，有助于企业做出基于知识驱动的决策。数据挖掘所提供的自 动的预期分析，已经远远超出由典型决策支持系统工具对过去实践所作的回 顾性分析的范围。数据挖掘可以解决传统上需花费很多时间解决的商务问题， 它能搜索整个数据库并查找隐藏的模式，找出那些专家可能错过的预测信息 ( 幻 。 数据挖掘技术已经在多个领域取得令人满意的应用。如在金融投资领域、 信用评估领域、网络管理领域和销售领域等等。 近年来，数据挖掘概念已经延伸的非常广泛，涉及的数据种类日益多样 化，给数掘挖掘提l 上j 了许多挑战性的课题，包括需进一步研究的新应用的探 索和处理复杂数据类型的新方法，算法的可伸缩性，基于约束的挖掘和可视 化方法，数据挖掘与数据仓库和数据库系统的集成，数据挖掘语言的标准化， 以及数据隐私保护与安全。 关联规则分析作为一种非常重要的零售业数据挖掘的方法，自1 9 9 3 年 亟堡堡王盔堂塑主堂焦坠塞 a g r a w a l 首次提出以来取得了巨大的进展，该领域的研究在国际上也受到普 遍的重视。关联规则挖掘算法已经被广泛应用于零售业的购物篮分析，在识 别顾客购买行为、发现顾客购买模式和趋势、提高货晶销量比率、设计更好 的货品运输与分销策略、减少商业成本等方面起到非常重要的作用“。 本文的研究工作就是基于以上背景，主要目的就是对数据挖掘进行深入 研究的基础上，建立一个基于关联规则的挖掘零售业数据的可视化系统。该 系统提供了一个和用户交互的可视化环境，并以一个网络交易数据库为例， 对原始数据进行了数据抽取、数据采样、数据转换等一些预处理工作之后， 采用经典a p r i o r i 算法挖掘，并基本实现了数据的可视分析部分以及挖掘的 规则结果可视化部分，加强了用户和数据以及数据挖掘的结果之间的联系。 1 2 意义 希望能让计算机自动智能的分析数据库中的大量数据以获取信息是推 动挖掘型工具产生并发展的强大动力。数据挖掘，即从大型数据库中挖掘出 隐藏的预测性的信息，是一个大有潜力的功能强大的新技术，它能帮助公司 挖掘数据仓库中最重要的信息。数据挖掘工具预测未来的趋势和行为，使商 业能作一些知识驱动的预先决定。数掘挖掘是通过对过去的事件进行分析来 提供自动的预测分析。数掘挖掘工具能回答商业问题，要解决这些商业问题 以往都是非常耗时的。数据挖掘搜索数据库，寻找隐含的模式，发现专家可 能忽略的预测信息，因为这些信息常常是他们未能预测到的。大多数公司已 经搜集并且精化了这些数据。确切的说，数据挖掘是一种决策支持过程，它 主要基于a i 、机器学习、统计学等技术，高度自动的分析企业原有的数据， 做出归纳性的推理，从中挖掘出潜在的模式，预测客户行为，帮助企业的决 策者调整市场策略，减少风险，做出j 下确的决策l 】。 数据挖掘的任务是从大量数据中发现知识，知识是人类认识的成果或结 晶，包括经验和理论知识。从工程角度定义，知识是有助于解决问题的有格 式复用的信息。在传统的决策支持系统中，知识库中的知识和规则是由专家 2 亟堡垄! 二丕望堕堂垡鲨奎 或程序员建立的，是由外部输入的，而数据挖掘任务是发现大量数据中尚未 发现的知识，是从系统内部自动获取知识的过程，对于那些决策者明确了解 的信息，可以用查询、联机分析处理或其他工具直接获取，比如“列出各个 子公司在上个月的销售情况”，而另外一些隐藏在大量数据中的关系、趋势， 即使是管理这些数据的专家也是没有能力发现的。这些信息对于决策者可能 又是至关重要的，现在就让数据挖掘来对付这类任务吧。 数据采样、数据可视分析、模型可视分析是知识发现过程中的不可缺少 的环节，只有采用数据采样技术，爿能提高数据挖掘的速度，否则算法执行 的时间是难以忍受的，数据可视分析能找出数据的潜在关系，分析各个属性 与挖掘主题之间的关系，为对数据进一步的处理和挖掘做准备。模型可视将 挖掘的结果解释给用户，用户只有理解模型，才能信任模型，从而利用模型 进行预测。 1 。3 本文的贡献及结构的安排 本文所要实现的是基于关联规则的数据挖掘可视化系统。系统提供一个 数据挖掘过程的交互环境，以可视化的方式指导用户完成基于关联规则的数 据挖掘任务。其中数据挖掘中的数据源可以是来自关系数据库或外部文件； 在将实际的数据应用到数据挖掘的算法中去之前，需要对数据进行如下的预 处理：1 、数据采样实际生活中的交易数据量往往很大，可能是成千上万条 甚至是更多。而算法处理的数据毕竟只能是少量的、有一定代表性的，这就 需要在原始数据库中采样一部分数据来进行研究。2 、特征选择转换由于我 们面对的是大型多维关系数据库，实际的数据库中可能包含多个属性如购买 日期、交易序号、商品号、购买商品数量、商品价格等等，而根据系统所采 用的算法，需要将原始数据转化成算法所需的形式对原始数据库进行特征 选择，并转换生成所需的交易数据库。在数据挖掘工具的实现中，本文对数 据库中的数据提供了分析方法，用直观的图形可视的方法展示数据中的信息 分布及各数据中的相互联系，使用户尽可能多的了解数据的一些统计信息。 垫堡堡王丕堂堕堂垡堡塞 数据挖掘算法用v c 4 - + 实现，在与系统的结合方面，采用组件的形式嵌入， 通过c o m 接口，将数据源、规则结果等作为参数传递，用可视化的图形方 法表示出了挖掘的结果。系统还实现了用户与算法中的某些参数如最小支持 度、最小置信度等之间的可视化交互；最后在模型的可视化方面，使用图表 的形式将数据挖掘算法输出的结果文件展示在用户的面前，并允许用户做简 单的交互。 本文是这样布局的：第二章对数据挖掘的相关知识进行了分析研究，涉 及数据挖掘的定义及其任务；数据挖掘的处理过程、分类和主要模式，并重 点论述了作为数据挖掘的主要模式之一的关联规则发现j 包括规则推导、关 联规则模型以及经典关联规则算法a p r i o r i ；第三章是系统的设计与实现部 分，论述了系统模型、系统实现的功能以及按功能将数据挖掘任务划分的不 同的模块：预处理模块、数据可视模块、关联规则挖掘算法模块以及最后生 成模型的可视化表达模块。按照系统的总体框架，用v b 设计实现了一个数 据挖掘可视化系统，利用可视界面来进行用户和数据挖掘任务之问的交互。 第四章论述数据挖掘可视化，分成两个部分：数据可视化和数据挖掘过程中 用到的相关的可视化技术，如挖掘结果的可视化等；系统主要实现了其中的 数据可视化和数据挖掘结果的可视化。第五章是结论部分，在总结了本文的 工作后。也对作者未完成的工作做出了展望。 武汉理工大学硕士学位论文 第2 章数据挖掘相关知识的分析研究 2 1 数据挖掘和知识发现 由于k d d 是- - i 1 受到来自各种不同领域的研究者关注的交叉性学科，它 充分利用了机器学习、人工智能、模糊逻辑、人工神经网络、集合分型的理 论和方法，因此导致了很多不同的术语名称，除了k d d 称呼外，主要还有 如下若干种称法：“数据挖掘”( d a t am i n i n g ) 、“知识抽取”( i n f o r m a t i o n e x t r a c t i o n ) 、“信息发现”( i n f o r m a t i o nd i s c o v e r y ) 、“知识发现”( k n o w l e d g e d i s c o v e r y ) 、“智能数掘分析”( i n t e l l i g e n td a t aa n a l y s i s ) 、“探索式数据分析” ( e x p l o r a t o r yd a t aa n a l y s i s ) 等等。其中，最常用的术语式“k d d ”和“数据挖 掘”。数据挖掘和知识发现具有很大的重合度，相对来讲，数据挖掘主要流行 于统计界、数据分析、数据库和管理信息系统界，而k d d 则主要流行于人 工智能习；f j j l 器学习界。一种较为普遍的观点认为：数据挖掘是知识发现过程 中的一个步骤，是k d d 中专门符合发现知识的核心环节”。 2 ，1 。1 知识发现的定义及其任务 知识发现是所谓“数据挖掘”的一种更广义的说法，即从大量数据中提 取可信的、新颖的、有效的并能被人理解的模式的处理过程，这种处理过程 是一种高级的处理过程1 7 l 。 我们可以从以下几个方面来理解： 数据数据是指一个有关事实f 的集合，它是用来描述事物有关方面的 信息，一般来说，这些数据都是准确无误的。 模式对于集合f 中的数据，可以用语言l 来描述其中数掘的特性。 可信：通过k d d 从当前数据所发现的模式必须有一定的正确程度，否 则k d d 就毫无作用，可以通过新增数据来验证模式的正确性，我们用c 表示 模式e 的可信度 e 武汉理工大学硕士学位论文 c = c ( e ，j 1 ) 其中f 是e 所描述的数据集合。 新颖：经过k d d 提取出的模式必须是新颖的，至少对系统来说应该如此。 模式是否新颖可以通过两个途径来衡量，其一是得到的数据，通过对比当前 得到的数据和以前的数据或期望得到的数据之间的比较来判断该模式的新颖 程度：其二是通过其内部所包含的知识，通过对比发现的模式与已有的模式 的关系来判断。通常我们可以用一个函数来表示模式的新颖程度n ( e ，f 1 ， 该函数的返回值是逻辑值或是对模式e 的新颖程度的个判断数值。潜在作 用：提取出的模式应该是有意义的，这可以通过某些函数的值来衡量。用“表 示模式e 的有作用程度，h u ( e ，f ) 。 潜在作用提取出的模式应该是有意义的，这可以通过某些函数的值来衡 量。用“表示模式e 的有作用程度。h - u ( e ，f ) 可被人理解：k d d 的一个目标就是将数据库中隐含的模式以容易被人理解 的形式表现出来，从而帮助人们更好的了解数据库中所包含的信息。当然一 个模式是否容易被人理解，这本身就很难衡量，比较常用的方法是对其简单 程度进行衡量。我们假定模式e 的简单度( 可理解度) s 可用函数s 陋，f ) 来 衡量。 非繁琐的处理过程：k d d 是一个多步骤的处理过程，包括数据预处理、 模式提取、知识评估及过程优化。它是对数据进行更深层处理的过程，并不 是仅仅对数据进行简单的数学运算或查询，而是找出隐藏在数据背后的性能 吸，正是从这个意义上，我们况这个过程是非平凡的n o n t r i v i a l 过程。 2 1 2 数据挖掘处理过程 数据挖掘是指一个完整的过程，该过程从大型数据库中挖掘先前未知的 有效的，可实用的信息，并使用这些信息做出决策或丰富知识。 数据挖掘环境可示意如下图： 武汉理一r 火学硕士学位论文 知识 数据挖掘一般由3 个主要阶段组成：数据准备、挖掘操作、结果表达和 解释。下图展示了数据挖掘的一般过程和步骤。1 ： 图2 2 知识发现的基本过程和主要步骤 数掘挖掘并不是一个单向的线性过程，它可以描述为这3 个阶段反复过 程。其中在数据准备阶段需要进行的工作有： 数据选择提取与数据挖掘相关的领域的数据从集成后的逻辑数据库 中选择能表现数据特征的属性，它的目的是辨别出需要分析的数据集合，缩 小处理范围，提高数据挖掘的质量；在此过程中，会利用一些数据库操作对 数据进行处理，产生目标数据集。 数据预处理对目标数掘集进行再加工，检查数据的完整性及数据的一 垫堡垄王套堂堕堂垡鲨塞 致性，对其中的噪音数据进行处理，提取模型所必需的信息，处理丢失的数 据域。这个过程还可能包台对原始数据集的缩减工作，如通过投影或数据库 中的其他操作减少数据量。 数据转换将预处理后的数据转换成适合于数据挖掘的形式。 挖掘操作选择合适的数据挖掘算法，这包括选取合适的模型和参数， 并使得数据挖掘算法与整个数据挖掘的评判标准相一致。再运用选定的挖掘 算法，从数据中提取用户所需要的知识，这些知识可以用一种特定的方式表 示或使用一些常用的表示方式，如分类规则和分类树，回归，聚类，序列模 型，相依性和在线分析等。 模式解释和知识评价对发现的模式进行解释，在数据挖掘阶段发现出 来的模式，经过用户或机器的解释藕i 评估可能存在冗余或无关的模式。这 时需要将其剔除；也有可能模式不满足用户要求，这时则需要整个挖掘过程 退回到挖掘阶段之前，如重新选取数据、采用新的数据变换方法、设定新的 数据开采参数值，甚至换一种挖掘算法( 如当挖掘任务是分类时，有多种分 类方法，不同的方法对不同的数据有不同的效果) ，以得到最终有利于决策的 正确的知识。另外，数据挖掘由于最终是丽向用户的。必须将发现的知识以 用户能了解的方式呈现给用户。 在挖掘一个实际的数据实例中既可能包括以上全部步骤也可能根据实 际需要只完成一部分步骤。如果我们从方法学的角度来看，数据挖掘将变得 较为容易理解。我们可以采用以下的几个主要的步骤来进行： 1 ) 数据准备 实际上，数据挖掘足个过程，而数据准备则为这个过程的核心。例如， 如果你想知道有谁会响应一个直销活动，你就需要了解以前做过响应的客户 的资料。如果你有他们的名单和地址，你应该认识到这些数据虽然对客户来 说是独一无二的，但却并不是最适合进行数据挖掘的数据。 进行数据准备时我们将遇到的问题可能有： 获取数据通常我们在进行数据挖掘时有几种访问数据的方 武汉理工人学硕士学位论文 法：访问数掘仓库；通过基于事务的关系数据库或基于p c 的数 据库访问数据：通过数据转换工具访问数据；用查询工具访问数 据；从平而文件。访问数据等 限定数据范围进行数据挖掘时通常要遇到的一个问题就是 要限定数据的范围。比如，一个交易数据库可能包含以下数据域： c u s t o m e r _ id ，f i r s t n a m e ，l a s t n a m e ，a d d r e s s 等。由于 c u s t o m e ri d 域是唯一的，而且在具有唯一性的域中没有特定的 模式可以发现，因此不应当对这样的域进行挖掘。类似的，对于 f i r s t n a m e ，l a s t r l = l m e ，a d d r e s s 这些域，由于它们也具有唯一 性，因此同样没有特定的模式可以发现。 数捌质量数据很少是1 0 0 干净的。因1 1 l 很有必要了解赖以做 出决策的数掘的质量。实际上，数据挖掘是一种典型的“垃圾入 垃圾出”，即数据的质量越好则挖掘的结果就越精确。如在我们 分析的数据集中呵能存在着冗余数据、错误的或不一致的数据、 打字错误、过时数据、术语定义的变化等需要进行清理。 数据分组有时候为了降低模型的复杂性并减少计算时间需 要对数据分组。 数据导出通常情况下，有些有价值的信息是从已有的数据中 导出的。比如己知某个顾客购买商品的数量q u a n t i t y 和商品的 单价u n i tp r i c e 可以推导出该顾客一个购物的消费： s u m = q u a n t i t y u n i tp r i c e 。导出一个数据字段可以采样不同的 方法：可以在关系数据库中通过s o l 语句导出新的数据字段，也 可以使用查询工具导出新的数据字段，此外，如果样本数据集比 较小，还可以使用e x c e l 及数学运算函数导出新的数据字段。 2 ) 定义主题 在准备好了需要挖掘的数据集后，接下来需要确定数据挖掘研究的范 围。定义主题涉及以下几个方而的事情： 武汉理t 大学硕+ 学位论文 了解主题的局限性在准备和表示数据时总是有一定目的或 目标的。即使在不需要因变量的无监督挖掘或聚类分析中，选择 数据的方法本身已经表明了所关注的内容，但是没有必要指定特 定的挖掘目标。例如，如果数据描述的是背部剧痛病人的手术情 况，那么研究目标就很可能围绕着获取更详细的手术情况而展开 的；如果数据质量较差，则需要确定从什么地方开始进行数据挖 掘。数据挖掘是一个不断提高的过程，通过理解数据集，能更好 的掌握如何提高数据的可靠性；如果已经建立了模型，可能还会 提出新的问题，继续使用数据挖掘工具；研究完成后没有发现任 何新的信息，还需要继续进行数据挖掘。 选择良好的主题良好的研究主题使我们能自如的向别人解 释如何根据这一研究结果提出可能的解决方案：或者建立一些工 作的基础，根据这个基础可能找到满足要求的途径。 主题的类型在实际应用领域中的挖掘方向可能有：数据趋势 分析、分类聚类和可视化研究、收益分析、风险预测等。挖掘方 向既可以用于理解为什么会出现某些条件，也可以用于对一组将 导致某一结果的条件进行预测。 需要分析的因素无论是聚类分析，还是对数据做可视化观 察，或是分类研究，选择要分析的元素的过程都是相同的。可能 需要在数据挖掘的过程中才能确定哪些因素才是真正重要的。 数据抽样数据挖掘并不总是要求用全部的数据进行建模。我 们w 以先从少量数批丌始然后逐步增j j l l 数据量，也可以先丌丁少 量抽样数据建立模型。然后再用全部数据对模型加以验证。 3 ) 读入数据并建立模型 在准备好婴挖掘的数掘集并确定挖掘的同标后，接下来就是用数据挖 掘工具读入数据集并从中构造出一个模型。衡量一个数据挖掘模型是否 适用有3 个重要的衡量指标：模型的准确性、可理解性、性能。 垫堡翌：! ：丕堂堕堂焦望塞 4 ) 理解模型 数据挖掘模型可以从不同方向进行理解。无论使用哪种模型，模型都 会告诉用户什么信息与特定结果具有关联关系。输入数据对特定结果具 有影响并不意味着它们之间一定具有因果关系。例如眼睛为褐色与篮球 运动员之间可能具有某种联系，但跟睛为褐色并不成为导致某个人是一 名篮球运动员的原因：如果对分析的数据集进行分组，不同的划分数据 的方法会产生不同的结果；最后为了评价模型对数据集的预测有多少准 确性需要对模型进行验证。 5 )预测 预测是一个相当直接的过程，即针对一组输入数据就是否会出现某一 结果做出预测。用模型进行预测，除了会产生与挖掘目标相关的结果外， 还可能产生其他的一些信息如：其他候选结果、获选边际率、理解产生 预测结果的原因等。 2 1 3 数据挖掘的分类 数据挖掘作为k d d 中最核心的部分，是采用机器学习、数学统计等方法 进行知识学习的阶段。数据挖掘的两个目标是预测和描述，预测是指用些 变量或数据库的若干已知字段预测其它感兴趣的变量或字段的未知的或未来 的值；描述是指找到描述数据的可理解模式。 从不同的角度看，数据挖掘技术有几种分类方法1 7 】：根据发现知识的分 类；根据挖掘的数据库的种类分类和根据采用的技术分类。 根据发现的知 j 的利一类分类 这种分类方法有：总结( s u m m a r i z a t i o n ) 规则挖掘、特征( c h a r a c t e r i z a t i o n ) 规则挖掘、关联( a s s o c i a t i o n ) 规则挖掘、分类( c l a s s i f i c a t i o n ) 规则挖掘、 聚类( c l u s t e r i n g ) 规则挖赫n 趋势( t r e n d ) 分析、偏差( d e v i a t i o n ) 分析、 模式( p a t t e r na n a l y s i s ) 等，如果以挖掘知识的抽象层次划分，又有原始层次 ( p r i m i t i v el e v e l ) 的数据挖掘、高层次( h i g hl e v e l ) 的数据挖掘和多层次 武汉理1 ：大学硕士学位论文 ( m u l t i p l el e v e l ) 的数据挖掘等。 根据挖掘的数据库分类 数据挖掘基于的数据库类型有：关系型( r e l a t i o n a l ) 、事务型 ( t r a n s a c t i o n a l ) 、面向对象型( o b j e c t e d o r i e n t e d ) 、主动型( a c t i v e ) 、空间 型( s p a t i a l ) 、时间型( t e m p o r a l ) 、文本型( t e x t u a l ) 、多媒体( m u l t i m e d i a ) 、 异质( h e t e r o g e n e o u s ) 数据库和遗留( l e g a c y ) 系统及网络( w e b ) 等。 根据采用的技术分类 最常用的数据挖掘技术足：人工神经网络它从结构上模仿生物神经网 络，是一种通过了解训练来学习的非线性预测模型。可以完成分类、特征挖 掘等数据挖掘任务。神经网络方法中。可以细分为：前向神经网络( b p 算法 等) 、自组织神经网络( 自组织特征映射、竞争学习等) 等。 统计方法，可细分为：回归分析( 多元回归、自回归等) 、判别分析( 贝 叶斯判别、费歇尔判别、非参数判别等) 、聚类分析( 系统聚类、动态聚类等) 、 探索性分析( 主元分析法、相关分析法等) 等： 机器学习，可细分为：归纳学习方法( 决策树、规则归纳等) 、基于范 例学习、遗传算法等，其中遗传算法是一种新的优化技术，基于生物进化的 概念设计了一系列的过程来达到优化的目的。这些过程基因组合、交叉、变 异和自然选择，为了应用遗传算法，需要把数据挖掘任务表达为一种搜索问 题而发挥遗传的优化搜索能力： 数据库方法主要是多维数据分析或o l a p 方法，对数据库进行在线分析； 面向属性的归纳方法。 2 1 4 关联规则发现 关联规则挖掘就是从大量的数掘中挖掘出有价值描述数据项之间相互关 系的有关知识i ”。随着收集和存储在数据库中的数据规模越来越大，人们对 从这些数据中挖掘相应的关联知识越来越有兴趣。例如：从大量的商业交易 记录中发现有价值的关联知u 就可帮助进行商品目录的设计、交叉营销或帮 婴堡堡：! ：叁堂堕堂壁堡塞 助进行其它有关的商业决策。 挖掘关联知识的一个典型应用实例就是市场购物分析。根据被放到一个 购物篮的内容记录数据而发现的( 被购买) 商品之问所存在的关联知识无疑 将会帮助商家分析顾客的购买习惯。根据不同的标准对关联规则挖掘方法还 可进行分类1 4 1 ：根据所处理的具体值分为布尔型关联规则和定量关联规则： 根据规则中数掘的维数分为单维关联规贝和多维关联规则：根据规则描述内 容所涉及的抽象层次分单层次关联规则和多层次关联规则，以及根据关联规 则所涉及的关联特性来进行分类划分。 2 1 4 1 规则推导 规则推导是无监督学习系统中的知识发现的最为普遍的一种类型( 5 ”。这 可能是因为它和人们提及数据挖掘也即在大型数据库中挖掘“知识金矿”时 和人们的想象最为接近。这里的“知识金矿”可能是一条感兴趣的规则 告诉你数据库中你不知道的、可能不能详细解释清楚的东西。 基于数据的规则推导能从数据中系统的发现所有可能的模式，并将准确 度和重要性加入到其中来告诉用户一个模式的价值以及它再次发生的可能 性。般来讲，这些规则相当简单，比如通过扫描顾客的购物篮中的交易数 据可能会发现数据库中的如下一些有趣的关联： 如果顾客购买了百吉饼，同时购买奶油干酪的可能性是9 0 ，这种模式 出现在购物篮中的概率为3 。 如果顾客购买了一株活的植物，那么他同时购买植物肥料的可能性是 6 0 ，并且两种商同时出现的概率为6 。 从数据库中发现的规则经抽取后呈现给用户是基于规则的准确度以及它 们应用的频度俐。 在规则推导系统中规则具有这样的简单形式：“如果a 和b 和c 那么d ”。 为了使发现的规则有用，还需要将如下的信息加入到其中： 准确度规则是正确的可能性有多大? 武汉理：l ：人学硕十学位论文 频度规则应用的可能性有多大? 数据库中的模式以规则的形式表达出来并不意味着在任何时刻都是正确 的。f 如其他的些数据挖掘算法要求的一样，识别并解释出规则的不确定 性电很重要，这也即是准确度的含义。而规则的频度则与规则在数据库中的 覆盖程度或者应用程度有关。我们还要注意的是，即使从规则推导系统中得 到的模式是以“如果那么”的形式表达的，和许多的因果关系的表达式的 形式是致的，但这并不意味着规则的左边导致规则右边的出现。 规则本身包含两个部分1 2 6 l 。规则的左边叫规则前件，规则的右边叫规则 后件。规则前件可能包含个条件或者多个条件，并且所有的条件必须成立 以确保后件以指定的概率成立。一般规则后件只有一个条件而不是多个条件。 从数据库r f l 挖掘的规则既f i - i i 于更好的理解数据所反映出来的商业问 题，也能用来将实际的预测与一些预先确定的预测目标相对照，因为规则包 含前件和后件，它们具有以下几个方面的商业用途【5 3 】： 关注规则前件在这种情况下将具有一定价值的规则前件组合在一起展 现给用户。比如一个商店可能需要了解前件包含了铁钉、螺钉的规则来判断 放弃这些低利润的商品是否会对其它利润高的商品产生影响。如购买铁钉的 顾客可能会购买价格高的铁锤，而如果没有铁钉他也许不会购买铁锤。 关注规则后件具有一定价值的规则后件能用来推断与后件有关的因素 以及影响后件的因素。比如用户可能对规则后件中包含咖啡的所有规则感兴 趣。这些规则可能影响咖啡的购买行为，并且店主可能会根掘这些规则确定 将哪些商品与咖啡摆放在一起以提高这些商品与咖啡的销量，或者咖啡的生 产商也可以利用这些规则米确定怎么样发放优惠券。 关注准确度有时对用户一而言，产生的规则的准确度才是最重要的。准 确度达到了8 0 或9 0 的规则表示挖掘出的规则前件和后件之间的关系比较 密切，h p 使它们在数据库中的支持度很低，仅仅只出现有限次。比如某个规 则只有0 1 的支持度，置信度为9 5 ，即在一千条交易中只出现一次但很可 能是正确的。如果出现的这一次能带来很高的利润，那么它也是有价值的。 1 4 亟堡堡二! 二- 人! ：堡堂丝堡塞 关注支持度有时用户可能需要了解哪些是最常见的或者是最具应用性 的规则。通过寻找以支持度排序的规则用户可以迅速的发现数据库中最普遍 的规律。 关注兴趣度当规则的支持度与置信度都很高并且偏离了常规时这些规 则就是有趣的。以一些度量兴趣度的方法来排列规则的方法有很多，这样就 可以在支持度与准确度之问折衷。 规则推导系统经常用来发现模式与进行无监督学习，让任何规则推导系 统产生所有可能的规则很容易，但是很难提出一种将那些最有用的规则( 可 能有成千上万条) 呈现给最终用户。当一些有趣的规则被挖掘出来以后，它 们可能被用来找出许多不同的预测值之问的关系而不是仅仅一种定义好的预 测目标。基于这个原因，除了规则的兴趣度，通常很难指定一个测量值比 如不容易确定如果顾客购买早餐香肠6 0 的情况下会同时购买鸡蛋的经济价 值。 2 1 4 2 关联规则挖掘模型 定义1 关联规则挖掘的数据集记为d ( 一般为事务数据库) ， d ； t l , i 一2 ，“，f 。 ，t 一，2 ，f ，) ，t t 一1 , 2 ，h ) 称为事务 ( t r a n s a c t i o n ) ，f ( m = 1 , 2 ，p ) 称为项目( i t e m ) 。 定义2 设，= f 。，i ：，i 。 是d 中全体项目组成的集合，i 的任何子集x 称为d 中的项目集( i t e m s e t ) ，l x i ；k 称为集合x 为k 项目集( k i t e m s e t ) 。设t i 和x 分别为d 中的事务和项目集，如果x t 。，称事务f 。包含项目集x 。每 一个事务都有一个惟的标t ! 符，称为t i d 。 定义3 数据集d 中包含项目集x 的事务数称为项目集x 的支持数，记 为d 。项目集x 的支持度记为s u p p o r t ( x ) ： s u pp o r t ( x ) - 斋x1 0 0 ( 2 - 1 ) i “l 其中蚓是数据集d 的事务数，若s u p p o n ( x ) 不小于用户指定的最小支持 丛丛堡! ：奎堂堕堂垡鲨墨 度m i n s u p p o r t ) ，则称x 为频繁项目集，简称频集( 或大项目集) ，否则称x 为 非频繁项目集，或小项目集。 定理1 设x 、y 是数据集d 中的项目集： ( 1 ) 若x y ，则s u p p o r t ( x ) 芑s u p p o r t f y ) 。( 2 2 ) ( 2 ) 若z y 。如果x 是非频集，则y 也是非频集。 ( 3 ) 若x y 若y 是频集，则x 也是频集。 定义4 若x 、y 为项目集，且x n y ；中，蕴含式工一y 称为关联规则， x 、y 分别称为关联规则x y 的前提和结论。项目集xu y 的支持度称为 关联规则x y 的支持度。记做： s u p p o f l ( x y ) ，s u p p o r t ( x y ) = s u p p o r t ( x u y )( 2 3 ) 关联规则x y 的置信度记做，c o n f i d e n c e ( jy 1 ： c d n f i d e n c e ；y ) 。盟掣黑磐1 0 0 ( 2 4 ) s u p p u r l 、 l 通常用户根据挖掘需要指定的最小置信度记为m i n c o n f i d e n c e 。 支持度和置信度是描述关联舰则的两个重要概念，前者用于衡量关联规则在 整个数据集中的统计重要性，后者用于衡量关联规则的可信程度。 定义5 若s u p p o r t ( x y ) ) - m i n s u p p o r t ，且 c o n f i d e n c e ( x j y ) a m i n c o n f i d e n c e ，则称关联规则z j y 为强规则，否则称 关联规则x y 为弱规则。 关联规则挖掘的任务就足要挖掘出d 中的所有强规则。它可以划分为以 下两个子问题： ( 1 ) 根据最小支持嫂找 数据集dr ”的所有频集。 ( 根据频集和最小置信度产生关联规则。 第一个问题的任务是迅速高效的找出d 中全部频集，是关联规则挖掘中 的核心问题。第二个问题则1 1 1 ( 2 2 ) 1 1 ( 2 4 1 求解，相对比较容易、直接。 武汉理：i ：人学硕十学位论文 2 1 4 3 关联规则算法m 。 发现所有的有充分支持度和嚣信度的关联规则，可以将这个问题分解成 以下两步： ( 1 )寻找那些事务的支持度超过最小支持度的项目的所有组合，把这 些组合称为大项目集，其它组合称为小项目集。 ( 2 )用大项1 7 集产生需要的规则。一般的想法是，如果说a b c d 和a b 是大项目集，那么我们能计算比率r = 支持数( a a c d ) 支持数0 钮) ， 从而确定是否有规则。仅当r 苫m i n c o n f i d e n c e 时爿有此规则。注 意此规则有最小支持度，因为a b c d 是大项目集。 发现所有大项目集的算法在数据上进行了多次遍历。在每次遍历中，从 大项目集的一个种子集合开始，并用这个种子集合产生新的潜在的大项目集， 称为候选项目集。在遍历数据的时候寻找对这些候选项目集有价值的支持。 在遍历的最后，确定候选项目集中的哪些确实是大项目集，然后它们变成下 一次遍历的种予。这个进程持续直到找不到新的大项目集。 以下是a p r i o r i 算法和它的相关过程的伪代码：算法的第一次遍历仅仅计 算每个项目的具体值的数量，以确定大型1 项集。随后的遍历，第k 次遍历， 包括两个阶段。首先，使用在第k - 1 次遍历中找到的大项集t 一和a p r i o r i - g e n 函数产生候选项集c 。接着扫描数据库，计算c 。中候选的支持度。用h a s h 树可以有效的确定c 。中包含在一个给定的事务t 中的候选。 输入：事务数据库d ；最小支持度闽值m i n s u p 输出：di ：1 1 的频繁项集l l l = 加d f r e q u e n t 一1 一i t e m s e t s ( d ) ； f o r ( k = 2 ；t l m ；忌+ + ) c t = a p r i o r i g e n ( l 一”m i n s u p ) ； f