（计算机应用技术专业论文）基于概念格扩展模型的关联规则挖掘.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 ) 是数据库和人工智能领域研究的热点课题，其中关联规则挖掘是重要的分 支。经典的和其它挖掘算法在时空性能方面和结果展现方面还存在些不 足。 概念格是通过概念的内涵和外延及泛化和例化之间的关系来表示知识， 因而适用于从数据库中挖掘规则问题的描述。在概念格的内涵中引入等价关 系而得到的概念格扩展模型，能更清晰的表示概念内涵之间的关系，更有利 于知识提取。 本文探讨了基于概念格扩展模型的关联规则提取，主要：【作如下： ( 1 ) 概念格模型的扩展与实现：通过引入量化和相对约减两种方法， 使从格中提取规则更方便：概念外延的量亿表示压缩了外延的空间，内涵的 相对约简压缩了内涵的空间存储规模，因而提高了空间性能，并给出了相应 概念格的构造算法。 ( 2 ) 基于概念格扩展模型的关联规则挖掘研究与实现：提出了基于概 念格扩展模型的关联规则挖掘算法，并通过实验对算法的正确性及时间和空 间性能进行了验证。 关键字：数据挖掘：概念格扩展模型：关联规则 】、，i i n i n ga s s o c i a t i o nr u l e sb a s e do n t h ee x t e n d e dm o d eo fc o n c e p tl a t t i c e 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 n d a t a b a s e s ( k d d )i st h e h o ts u b j e c tt h a t d a t a b a s e sa n da r t i n c i a li n t e l l i g e n c ef i e l da r es t u d i e d m i n i n ga s s o c i a t i o nt u l e si s a ni 抽p o r t a n tb r a n c ho fk d d t h e r ea r ep r o b l e m sa b o u tt i m ea n ds p a c ea n d p r o b l e m sa b o u ts h o wt h er e s u l t si nt h ec l a s s i c a la n do t h e ra l g o r i t h m so fm 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 er e p r e s e n t sk n o w l e d g ew i t ht h er e l a t i o nb e t w e e nt h e i n t e n s i o n sa n dt h ee x t e n s i 6 n s o fc o n c e p t s ，a n dt h er e l a t i o nb e t w e e nt h e g e n e r a l i z a t i o na n dt h es p e c i a l i z a t i o nb e t w e e nc o n c e p t s ，t h u si ti sa ne 伍c i e n t t o o lf b rk d d b yi n 打o d u c i n ge q u i v a l e n ti n t e n s i o ni n t og 0 1 0 i sc o n c e p tl a t t i c e ， t h ee x t e n d i n gm o d e lo fc o n c e p tl a t t i c ei sg o t t e nw h i c hr e p r e s e mt h ek n o w l e d g e m o r ec l e a r l ya n dd i s t i n c t l y t h em e t h o d so fh o wt om i n i n ga s s o c i a t i o nr u l e sb ye x t e n d e dm o d e l c o n c e p ti se x p a t i a t e di nt l l i sd i s s e n a t i o n t h ec o n t e n t si sa sf b l l o w - ( 1 )t h em e t h o do fe x t e n da n dr e a l i z a t i o na b o u tc o n c e p tl a t t i c e ： q u a n t i t a t i v e ，a n dr e l a t i v er e d u c e da r ei m r o d u c e d ，m o r ec o n v e n i e md i s c o v e r r u l e s ，q u a n t i t a t i v ei sr e d u c et h es p a c eo fe x t e n t s ，r e l a t i v er e d u c e dr e d u c et h e s p a c eo fi n t e n t s ， t h o s el e ti th a sb e t t e rs p a c ep e r f o r m a n c e t h ea l g o r i t h mo f g e n e r a t ee x t e n d e dc o n c e p tl a t t i c ei sg i v e ni nt h i sd i s s e r t a t i o n ( 2 ) t h er e s e a r c ha n da l g o r i t l l l no fm i n i n ga s s o c i a t i o nr u l e si ne x t e n d e d c o n c e p tl a t t i c e ： t h ea 1 9 0 r i t h mo fm i n i n ga s s o c i a t i o nr u l e si s g i v e ni nt h e d i s s e r t a t i o n f i n a l l y ，t h er e s u l t so fe x p e r i m e n to ft h ea l g o “t h ma b o u ts p a c ea n d t i m ep e r f o r m a n c ei sp r o v i d e d 1 ( e y w o r d s ：d a t am i n i n g ：e x t e n d e dc o n c e p tl a t t i c e ；a s s o c i a t i o nr u l e s 合肥工业大学 本论文经答辩委员会全体委员审查，确认符合 合肥工业大学硕士学位论文质量要求。 答辩委员会签名 工作单位 黟洳争 珍舻缈矿 名，够净绉 姥嬲 宠卵勘一胖秽产 别吼锏栌桫孑 移孱 红坎 多心j 瞧 j 劢妒氓 撇 躺许阳 女弑 钏丕 ， 席 员 主 委 独创性声明 本人声明所呈交的学位论文是本人在导师指导f 进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得佥壁王些盍堂或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示谢意。 学位论文作者签名：j 。晚签字日蟛哆年；彤日 学位论文版权使用授权书 本学位论文作者完全了鼹垒墼至些盍堂有关摆留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本 人授权盒起至些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段僳存、汇编学位论文。 j 保密的学位论文在解密后适用本授权书) 学位论文作者签名 签字日期：年月日 学位论文作者毕业后去向 工作单位： 通讯地址： 导师签名 签字日期 缛f r - 日 慨咖乃影 邮编：彩卯。7 | 致谢 本论文的研究工作是在导师胡学钢教授的悉心指导下完成的。在近三年 的研究生生活中，导师不仅在研究工作上给予谆谆教导和大力支持，还在学 习和生活上给予关怀和帮助，使我不仅能顺利完成学业，而且受益非浅。恩 师的言传身教让我明白了科研工作的真谛，更让我明白了做人的道理。在此， 特向恩师致以最衷心的感谢。 此外，还特别感谢在本论文完成过程中给予我帮助的老师和同学，感谢 孙莹、唐志军、郭亚光的真诚相特，感谢张晶老师的大力支持感谢吴共庆 老师的教导。同时也对我的亲人、朋友所给予的精神、生活和学习上的鼓励、 关怀、支持和帮助表示最诚挚的谢意! 刘凡 2 0 0 5 4 9 绪言 随着信息技术的发展和广泛应用。全球范围内数据库中的数据量 急剧增大；信息高速公路的发展和广泛应用使得整个社会变成了信息化 的网络世界，数据量的增长更为迅猛。有些公司经过多年积聚下来的商 业数据目前已经超过数百万乃至数亿条记录：有些面向科学研究数据库 的数据量也非常惊人，比如，记录天体信息的数据库容量达到数个t b 字节。全球商业、企业、科研机构和政府部门在过去若- f 年的时间里积 累了海量的、以不同形式存储的数据资料。虽然数据库系统提供了对数 据的管理和简单豹处理功能，人们可以在这些数据之上进行商业分析和 科学研究，但数据资料如此庞大而且十分繁杂，因此要从中发现有价值 的信息或知识，达到为决策服务的目的，对人工处理来说是非常困难的。 人们需要能够对数据进行较高层次处理的技术，从中找出规律和模式， 以帮助人们更好地利用数据进行决策和研究。数据库的知识发现( k d d ) 技术让人们有能力最终认识数据的真正价值，即蕴藏在数据中的信息和 知识。k d d 指的是从大型数据库或数据仓库中提取人们感兴趣的知识， 这些知识是隐含的、事先未知的、潜在有用的信息。 k d d 是实用性很强的技术，是目前国际上数据库和信息决策领域 的前沿研究方向之一，它可以帮助人们对数据进行更深层次的分析，引 起了学术界和工业界的广泛关注。一+ 些国际上高级别的工业研究实验室 和众多的学术单位都在这个领域开展了各种各样的研究计划，大量的 研究原型和应用系统纷纷出现。k d d 可以用在信息管理、查询响应、决 策支持、图象处理和过程控制等许多方面。 1 本文的主要工作 本文的研究工作源于上述背景，借助概念格扩展模型进行知识发现。 概念格是根据二元关系建立起来的概念层次结构，反映的是对象与属性 之间的联系以及概念之间的泛化和例化关系，在概念层次结构上容易建 立数据之间的依赖或因果关系模型。在信息检索、软件工程和k d d 等 领域，概念格已经显示出一定的应用价值。而概念格有其局限性，因此 我们对它进行了扩展一一提出了扩展概念格模型，不仅使其以更简洁的 形式表达更丰富的信息，而且规则提取更方便、更丰富。 2 本文的内容与组织 本文主要由七章组成。 第一一章是全文的绪论，本章对k d d 进行了较为全面的综述。首先 介绍了k d d 的含义和k d d 处理过程模型，主要评述了作为k d d 关键 环节啊一数据挖掘的基本任务和基本方法，最后讨论了k d d 的应用和 面临的挑战。 第二章介绍了关联规则的定义，研究方向、新的发展、当前应用， 较为详细的分析了最重要和有影响力的几种关联规则的提取方法。 第三章详细描述了概念格( g c l ) 的提出、定义、和概念格的构造 算法。讨论了其发展前景。 第四章解释了概念格扩展模型( e c l ) 。首先介绍了扩展概念格的 基本思想、有关术语、性质及其与概念格之间的关系，解释了概念格与 粗糙集合的关系，以及概念格扩展模型的规则提取。 第五章是全文的重点。解释了概念格扩展模型的关联规则挖掘算 法，提出量化概念格扩展模型的关联规则挖掘算法，以及相对约简概念 格扫碾模型的关联规则挖掘算法，并附以挖掘算法的伪码。 第六章给出了实现各种算法的效果。 第七章是全文的总结，并在概念格扩展模型的发展和应用前景提出 了一些观点。 第一章数据库知识发现 随着数据库技术的成熟和应用的普及，人类积累的数据量以指数级 速度迅速增长。进入九十年代，伴随着因特网的出现和发展，以及随之 而来的企业内部网和企业外部网以及虚拟私有网的产生和应用，将整个 世界联成一个小小的地球村，人们可以跨越时空地在网上交换数据信息 和协同工作。这样，展现在人们面前的已不是局限于本部门、本单位和 本行业的庞大数据库，而是浩瀚无垠的信息海洋，数据洪水正向人们滚 滚涌来，已超出人们分析和利用数据的能力范围。于是，相对于“数据 过剩”和“信息爆炸”，奈斯伯特( j o h n n a i s b e t t ) 惊呼“w ea r ed r o w n i n g i n i n f o r m a t i o n ，b u ts t a r v i n g f o rk n o w l e d g e l l j i ( 人类正被数据淹没，却饥 渴于知识) 。 面临浩渺无际的数据，人们呼唤从数据汪洋中来一个去粗取精、去 伪存真的技术。数据库知识发现( 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 ) 2 3j 及其核心技术数据挖掘( d a t am i n i n g ，d m ) 【4 l 便应运而生 了。有效地利用和处理大量的数据成为当前世界共同关心的问题。 1 1k d d 1 1 1k d d 的概述 1 1 1 1k d d 的产生背景 专家系统是人工智能领域中获得最成功应用的分支，它的出现标志 着人工智能进入了知识处理的时代。然而，其发展却遇到了很大的困难， 其中最突出的是知识获取这一“瓶颈”问题。为了把知识工程师和领域 专家从繁重的劳动中解放出来，从相关领域的原始数据中自动发现知识 便成了人们孜孜以求的目标。 另一方面，随着计算机的迅速普及和数据库技术的迅猛发展，数据 库管理系统被广泛应用于社会各部门，数据库中存储的数据量急剧增大。 大量信息在给人们带来方便的同时也带来了一大堆问题：第一是信息过 量，难以消化；第二是信息真假难以辨识；第三是信息安全难以保证： 第四是信息形式不一致，难以统一处理。人们开始考虑：“如何才能不 被信息淹没，而是从中及时发现有用的知识、提高信息利用率? ” 面对新的挑战，数据库知识发现( k n o w l e d g ed i s c d v e r yi nd a t a b a s e s ， k d 螨，又称数据挖掘( d a t am i n i n g ，d m ) 技术应运雨生，并显示出强大的 生命力。 f r i e d m a n 列举了激发数据挖掘的开发、应用和研究兴趣的四个主要 的技术理由： 超大规模数据库的出现，例如商业数据仓库和计算机自动收 集的数据记录； 先进的计算机技术。例如更快和更大的计算能力和并行体系 结构： 对巨大量数据的快速访问： 对这些数据应用精深的统计方法的能力。 数据挖掘与传统的数据分析( 如查询、报表、联机应用分析) 的本质 区耵是数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数 据挖掘所得到的信息应具有预先未知性、有效性和可实用性三个特征。 目前k d d 的主要研究内容包括基础理论、发现算法、数据仓库、可 视化技术、定性定量互换模型、知识表示方法、发现知识的维护和再利 用、半结构化和非结构化数据中的知识发现以及w e b 挖掘等。 1 1 1 2k d d 定义及其特点 一、k d d 定义 虽然人们给k d d 下过很多定义，但随着k d d 研究的不断深入，人 们对k d d 的理解越来越全面，对k d d 的定义也不断修改，目前k d d 还没有个统一的定义，下面是对k d d 的比较公认的定义h 6 i ： k d di s “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 y i n gv a l i d ，n o v e l ，p o t e n t i a l l y u s e f u l ，a n du l t i m a t e l vu n d e r s t a n d a b l ed a t t e m si nd a t a ”，即k d d 是从大量 数据中提取出有效的、新颖的、有潜在作用的、可信的、并能最终被人 理解的模式的非平凡的处理过程。 下面对这个定义作详细的解释： 数掘：数据是指一个事实的集合。如数据库中的记录，这也是k d d 处理的最常用的数据形式。 模式：用语言来描述数据子集的特性。只有比列举子集中所有元素 的描述方法更为简单时，我们才可称之为模式。如：“如果成绩在8 l 一9 0 之间，则成绩优良”可称为一个模式，而“如果成绩为8 l 、8 2 、8 3 、8 4 、 8 5 、8 6 、8 7 、8 8 、8 9 或9 0 ，则成绩优良”就不能称为一个模式。 玻e 理过程：k d d 是一个多步骤的处理过程，包括数据预处理、模式 4 提取、知识评估及过程优化。 可信：k d d 过程从数据中所发现的模式必须有一定的征确性，否则 k d d 就毫无作用。可以通过新增数据来检验模式的i f 确性。 新颖性：经过k d d 提取出的模式必须是新颖的，至少对系统来说 应该如此。模式是否新颖可以通过两个途径来衡量：其一是得到的数据， 通过对比当前得到的数据和以前的数据或期望得到的数据之间的比较来 判断该模式的新颖程度；其二是通过其内部所包含的知识，通过对比发 现的模式与已有的模式的关系来判断。 潜在作用：提取出的模式应该是有意义的。 易于理解：k d d 的一个目标就是将数据库中隐含的模式以容易理解 的形式表现出来，从而帮助人们更好地了解数据库中所包含的信息。 二、k d d 的特点 由以上可以看出，k d d 是从数据库中提取有价值知识的过程，是数 据库技术和机器学习等学科的交叉学科。数据库技术侧重于对数据存储 处理的高效率方法的研究，而机器学习则侧重于从数据中提取知识。 k d d 利用数据库技术对数据进行前端处理，而利用机器学习方法从处理 后自勺r 数据中提取有用的知识。k d d 与其他学科也有很强的联系，如统计 学、数学和可视化技术等。 既然k d d 和机器学习都是从数据中提取知识，那么两者有什么区 别呢? k d d 是从现实世界中存在的一些具体数据中提取知识，这些数据 在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 1 1 - 3k d d 任务 在实践中k d d 的两个基本任务是预测和描述。预测指的是预测未 知的感兴趣的变量的值或发现某些实例未来的行为模式：描述是指寻找 可以理解的描述数据的好的模式。预测和描述可以通过下列方法实现。 九分类( c l a s s i f l c a t i o n ) ：分类的目的是指将数据归于一系列己知类中 的某一类的过程。是学会一个分类函数或分类模型( 也称作分类器) ，该 模型能把数据库中的数据项映射到给定类别中的某一个。给定一训练数 据集( 类别已知的客体集) ，以及基于训练集中数据的特性建立的分类模 型，堤从该分类模型中生成一系列的分类规则，这些分类规则可用于对 其他未来的数据进行分类，从而可以更好地理解数据库中的每一类。例 如，关于疾病的分类规则可以从已知病例( 训练集) 提取出来，然后结 合新病员的症状，可用于对新病员进行诊断。关于申请贷款者的分类， 银行可以根据分类对以后的贷款申请者决定是否给于贷款。 九聚类( c l u s t e r i n g ：是根据客体属性对+ 系列未分类客体进行类别的 识别，把一组个体按照相似性归成若干类别，即“物以类聚”。目的是使 得属于同一类别的个体之间的距离尽可能的小而不同类别的个体间的距 离尽可能的大。一旦聚类得以确定，各个客体就作相应的聚类标记，并 概括同一聚类中的各个客体的共同特性，从而形成类别描述。例如， 系列的新疾病可以根据其症状的相似性进行分组，从而形成基本类别， 同一类别中各疾病的共同症状便可用于描述该组疾病。 九特征( c h a r a c t e r i z a t i o n ) ：是指将与任务相关的数据集概括或抽象为某 个关系称之为泛化关系( g e n e r a l i z e dr e l a t i o n ) 。该关系可用于提取特征 规则( c h a r a c t e r i z a t i o nr u l e s ) 。特征规则可以在多层概念级上表示称之为 目标类的数据集特征。例如，某种疾病的各种症状可以概括为一系列的 特征规则。 九 区分( d is c r i m i n a t i o n ) ：是指发现分辨目标类( t a r g e tc l a s s ) 与对照 类( c o n t r a s t i n gc l a s s e s ) 的特征与性质。从这些分辨目标类与对照类的 特性中，可以发现一系列的区分规则( d is c r i m i n a t i o nr u l e s ) 。例如， 为了将某种疾病与其他种类的疾病区分开，区分规则应能概括该疾病不 同于其他种类疾病的症状。 九关联规则发现( a s s o c i a t i o n r u l e s m i n i n g ) ：是指发现客体的出现的潜 在依赖关系。关联规则形如“a 。 a ： a ，斗b 。 b ： b ，”，意味着 在目标数据中客体b ，b 。b 。倾向于同客体a a ：a ，一起出现。例如，规则： 面包十牛奶岭黄油( 5 ，4 0 ) 指出在购买面包和牛奶的顾客中有4 0 的人同时还要购买黄油。这里，4 0 为关联规则的可信度，而5 为关联 规则的支持度。 九序贯模式发现( s e q u e n t i a lp a t t e r n sm i n i n g ) ：是指在多个数据序列中 发现共同的行为模式。例如，对某顾客序列数据库d 序贯模式发现问 题就是在该数据库中寻找所有的频繁序列或所有的最长频繁序列。 r ，a g r a w a l 称最长频繁序列为序贯模式( s e q u e n t i a lp a t t e r n ) 。 天 情节发现( e p i s o d e sm i n i n g ) ：是指在事件序列中发现频繁情节 ( f r e q u e n te p i s o d e s ) 。所谓情节是指在给定长度的时间区间内出现的事 件的有序集合，而频繁情节是指在事件序列中具有一定出现频率的情节。 如果在事件序列中发现了频繁情节，就可以生成描述或预测该序列的行 为。 九偏离发现( d e v i a t i o n m i n i n g ) ：是指在与时间相关数据库中某客体的 偏离模式的发现与评估。客体的期望行为通常由用户给定或根据假设( 如 平均、线性增长) 计算得知。例如发现某些股票在某段时间内其行为不 同与大多数股票的发展趋势。 1 1 2k d d 的处理过程模型 人们进行的关于k d d 的研究是为了将知识发现的研究成果应用f 实际数据处理中，为科学的决策提供支持。然而，目前所进行的关于k d d 的研究。大多只着眼于对数据挖掘阶段的研究，而忽视了其他方面的研 究。事实上，k d d 首先是一个处理过程，如果仅仅着重于数据挖掘，可 能就看不到在实际工作中。数据处理过程中的数据提取、组织和显示方 式的难度。数据挖掘所完成的工作对于整个知识发现的过程来说，只是 其中的一部分，因此对k d d 中其它阶段及处理过程的研究也是非常重 要的。 目前人们对整个处理过程并没有给出非常清楚的划分，而建立合适 的处理过程模型能将各个处理阶段有机地结合在一起，以便于人们开发 及使用k d d 应用系统。比较有代表性的模型有三种邛i ： 第一种是u s a m a m f a y y a d 等人给出的多处理阶段模型。 第二种是g e o r g eh j o h n 给出的多处理阶段模型。 第三种是b r a c h m a n & a n a n d 提出的以用户为中心的处理模型。 为了使k d d 能更好地应用于实践，下面以第一种面向多阶段处理 过程的k d d 处理过程模型为例进行简要地说明。本文后面有关的讨论 也是针对这种模型进行论述的。 图1 1 是u s a m af a y y a d 等人给出的处理模型。该处理模型把k d d 过程分为九个处理阶段：任务理解、数据选择、数据预处理、数据规约、 k d d 目标确定、挖掘算法确定、数据挖掘、模式解释，评价及知识表示 合并。 l 一一一一一一* 图11k d d 的处理过程模型 1 任务理解：了解k d d 相关领域的有关情况，包括实际应用中的 预备知识和目标，熟悉有关的背景知识，并弄清楚用户的要求。 2 数据选择：根据用户要求从任务相关数据库中提取与k d d 要求 相关的数据，k d d 主要从这些数据中进行知识提取。在此过程中，会使 用一些数据库操作对数据进行处理，建立一个目标数据集。 3 数据预处理：主要是对阶段2 产生的数据进行再加工，检查数 据的完整性和一致性，利用统计方法等对丢失的数据进行填补，去除噪 音数据和空白数据域，考虑时间顺序和数据变化等。 4 数据转换：对经过预处理的数据，根据知识发现的任务对数据 进行再处理，主要通过投影或数据库中的其他操作减少数据量或找到数 据的不变模式。 j 确定k d d 目标： 根据用户要求，确定k d d 发现的知识类型， 因为对k d d 的不同要求，会在具体的知识发现过程中采用不同的知识 发现算法。 6 ，确定知识发现算法：根据阶段5 所确定的任务，选择合适的数 据挖掘算法，包括选取合适的模型和参数，并使得挖掘算法与整个k d d 的评判标准相一致。 7 数据挖掘：运用选定的挖掘算法，搜索或产生一个特定的感兴 趣的模式或数据集，从数据中提取出用户所需要的知识，这些知识可以 用某种特定的方式表示或使用一些常用的表示方式，如产生式规则等。 8 模式解释评价：对发现的模式进行解释，去掉多余的不切题意 的模式，转换成某个有用的模式，以便于用户理解。在此过程中，为了 取得更为有效的知识，可能会返回前面处理中的某些步骤，以便反复提 取，从而提取出更有效的知识。 9 知识表示合并：将发现的知识以用户可理解的方式呈现给用户 或合并到系统中，也包含对知识的一致性检查。 在e 述的每个处理阶段，在对挖掘的知识进行评测后，根据结果可 以决定是否重新进行某些处理过程，在处理的任意阶段都可以返回到前 面的蔗个阶段进行再处理。 1 1 3k d d 的发展现状 目前，k d d 已经广泛用予多个领域，但每个领域又有其特定的应用问 题和应用背景，下面就应用最集中的几个领域给以简要的说明。 一、金融业 1 、数据清理、金融市场分析和预测 财经分析依赖各种来源的数据，其中可能包含错误信息或丢失信息， 有时还表达相互矛盾的信息。因此，对数据进行清理或联机验证十分重 要，以便更有效地进行金融市场分析和预测。 2 、帐户分类、银行担保和信用评估 硷融业务的利润和风险是共存的。为了保证以最小的风险获得最大 的利润，必须对帐户进行科学的分析和归类，并进行信用评估。 3 、从股票交易的历史数据中得到股票交易的规律或规则。 二、医疗保健 医疗保健行业有大量数据需要处理。分析病历和病人的行为特征， 以及用于药方管理，安排治疗方案，判断药方的有效性，预测医疗保健 费用。 三、市场业 市场业应用k d d 技术进行市场定位和消费者分析? 辅助制定市场策 略，对客户的历史数据进行分析，得出产品的购买趋势。 四、零售业 霹售业是最早应用k d d 技术的行业，目前主要应用于销售预测、库 存需求、零售点选择和价格分析，分析客户的购买行为和习惯，分析商 场的销售商品的构成。 五、制造业 制造业应用k d d 技术进行零部件故障诊断、资源优化、生产过程分 析、以及生产过程的优化等。 六、司法 k d d 技术可应用于案件调查、诈骗监测、洗钱认证、犯罪组织分析， 可以给司法工作带来巨大收益。 七、保险业 l 、保险金的确定：对受险人的分类有助于确定适当的保险金额度。 利用数据挖掘，可以有助r 确定不同行业、不同年龄段、处于不同社会 层次人的保险金。 2 、险种关联分析：分析购买某种保险的人是否同时购买了另一种保 险。 3 、预测什么样的顾客将会购买新险种。 八、工程与科学 k d d 技术可应用于各种工程与科学数据分析。 九、通信网络警报处理中的应用 一个通信网络可以看成是由互相连接的部件组成：交换器，传输设 备等。每个部件又包含一些子部件。分析的层次不同，部件的数目也不 相同。 1 1 4k d d 的挑战 k d d 的研究和应用将面临着许多的挑战，简要归纳如下： 一、更大规模的数据库 目前数据库的规模越来越大，这就要求能有更高效的算法、更好的 近似方法和更强的并行处理能力。 二、更高的维数 现在的数据库不仅规模大，而且可能有大量的字段，使得问题的维 数较高，因而使得模型归纳中的搜索空间规模产生了组合爆炸。应尽量 减少问题的有效维数。 三、多变的数据和知识 迅速多变的数据可能使先前发现的规则无效，而且在给定应用中的 数据库中所测得的变量可能随着时间的推移而被修改、删除或增加。这 要求算法要有更大的灵活性。 四、属性之间的复杂关系 结构化的属性或值属性之间的关系以及成熟的数据库中知识表示 方法，要求算法能够有效地使用这样的信息。 五、模式的可理解性 要使挖掘结果有意义，就应该为人类所理解。可采用图形表示、规 则结构、自然语言以及数据和知识的可视化等方式把结果提供给用户。 六、用户交互和先验知识 虽然自动化是k d d 的目标之一，但由于应用问题的多样性，使得 k d d 应用离不开用户的参与。当前许多k d d 方法和工具并非是真正交 互式的，除了一些简单的方法外，还不能较为方便地使用先验知识。 七、与其它系统的集成 单一的系统能力有限，难以全面地解决实际问题。应该把多个系统 结合在一起，最大限度地挖掘知识，同时也要与其他系统如：d b m s 、 可视化工具等集成，达到更好的效果。 1 。2 数据挖掘 1 2 1 数据挖掘与k d d 数据挖掘( d a t am i n i n g ) 是从大型数据库或数据仓库中提取人们 感兴趣的知识，这些知识是隐含的、事先未知的、潜在的、有用的信息， 其广义的定义是从存放在数据库、数据仓库或其他信息库中的大量数据 中挖掘有趣的知识过程。 许多人把数据挖掘视为数据痒知识发现( k d d ) 同义词。而另一些 人则是把数据挖掘视为k d d 过程的一个基本步骤。数据挖掘步骤可以 与用户或知识库交互，把有趣的模式提供给用户，或作为新知识存放在 知识库中。根据这个观点，数据挖掘只是整个知识发现过程中的一步， 并且是最重要的一步，因为它能发现隐藏的模式。本文采用这一观点。 1 2 2 数据挖掘 日前较为常用的数据挖掘方法和模型大致有以下几种，现分别简要 介绁。 一、概念格 w 川cr 等提出了根据二元关系建立相应概念格或g a l o i s 格的基本 思想，它本质上描述了对象与属性之问的联系，表明了概念之间泛化与 例化的关系。概念格的非形式化定义为：给定上下文( c o n t e x t ) 为三元组 t = ( o ，d ，r ) ，其中o 是对象集合，d 是性质集合，r 是0 和d 之间的二 元关系，则存在唯一的偏序集合与之对应，并且这个偏序集合产生一种 格结构，这种由上下文所诱导的格就称为概念格。x r x l 表示。中的个 元素x 与d 中一个元素x 之间有关系r 。格中每个结点是一个序偶( 即概 念) ，记为( a ，b ) ，其中a p ( o ) ，b p ( d ) ，p ( 0 ) 是o 的幂集，p ( d ) 是d 的幂集，称a 为概念的外延( e x t e n s i o n ) ，称b 为概念的内涵( i n t e n s i o n ) 。 概念格是一种完备的概念层次结构。在信息检索、数字图书馆、软件工 程、知识分类、类的设计、网络管理和k d d 等领域，概念格已经显示 出一定的应用价值【钆”“，”】。 二、关联规则发现 关联规则是形如：“购买面包和黄油的顾客中，有9 0 的人同时也 买了牛奶”( 面包+ 黄油一牛奶) 一种规则。关联规则发现的任务是： 给定一个事务数据库d ，求出所有满足最小支持度( m in s u p ) 和最小可 信度( m i n c o n f ) 的关联规则。 三、粗糙集方法 粗糙集理论是一种研究不精确、不确定性知识的数学工具，由波兰 科学家z p a w l a k 在1 9 8 2 年首先提出。知识工程研究中，一直存在着信 息的含糊性( v a g u e n e s s ) 等问题。含糊性有三种：术语的模糊性，如高 矮；数据的不确定性，如噪音引起的；知识自身的不确定性，如规则的 前后件间的依赖关系并不是完全可靠的。人工智能的基础理论之一 经典逻辑不足以解决这些不确定性问题。为此，人们提出了一些解决方 法，包括统计方法、模糊集理论以及d e m p s t e r s h a f f e r 证据理论，但这 些方- 法都有一些内在缺陷或限定范围。例如，基于统计的方法在理论上 还难以令人信服，而模糊集方法则存在一个本质问题即如何确定成员隶 属度。相比之下，粗糙集方法则有几个优点：不需要预先知道的额外信 息，如统计中要求的先验概率和模糊集中要求的隶属度：算法简单，易 于操作。 粗糙集对不精确概念的描述是通过上近似( u p p e ra p p r o x i m a t i o n ) 和下近似( l o w e ra p p r o x i m a t i o n ) 这两个精确概念来实现的。一个概念 ( 或集合) 的下近似指的是其中的元素肯定属于该概念：一个概念( 或 集合) 的上近似指的是其中的元素可能属于该概念。 四、分类 分类的目的是学会一个分类函数或分类模型( 也常常称作分类器) ， 该模型能把数据库中的数据项映射到给定类别中的某一个。要构造分类 器，需要有一个训练样本数据集作为输入。训练集由一组数据库记录或 元组构成，每个元组是一个由有关字段( 又称属性或特征) 值组成的特 征向量，除了这些外，训练样本还有一个类别标记。一个具体样本的形 式可为：( v l ，v 2 ，v 。；c ) ，其中v 表示字段值，c 表示类别。 分类器的构造方法有统计方法、机器学习方法、神经网络方法等。 五、聚类 聚类是把一组个体按照相似性归成若干类别，即“物以类聚”。它的 目的是使得属于同一类别的个体之间的距离尽可能的小而不同类别上的 个体间的距离尽可能的大。聚类方法包括统计方法、机器学习方法、神 经网络方法和面向数据库的方法。 六、决策树 决策树方法的起源是概念学习系统c l s ，然后发展到i d 3 方法而为 高潮，最后又演化为能处理连续属性的c 4 。5 ，有名的决策树方法还有 c a r t 和a s s i s t a n t 。决策树构造的输入是一组带有类别标记的例子，构 造的结果是一棵树。树的内部节点一般表示为一个逻辑判断，如形式为 ( a = v 。) 的逻辑判断，其中a 。是属性，v i 是该属性的某个属性值；树的边 是逻辑判断的分支结果。树( i d 3 ) 的内部节点是属性，边是该属性的所 有取值，有几个属性值，就有几条边。树的叶子节点都是类别标记。 构造决策树的方法是采用自上而下的递归构造。以多叉树为例，它 的构造思路是，如果训练例子集合中的所有例子是同类的，则将之作为 叶子节点，节点内容是该类别标记。否则，根据某种策略选择一个属性， 按照属性的各个取值，把例子集合划分为若干子集合，使得每个子集上 的所有例子在该属性上具有同样的属性值。然后再依次递归处理各个子 集。这种思路实际上就是“分而治之”( d i v i d ea n dc o n q u e r ) 的道理【1 3 l 。 另外，还有其他一些方法，神经网络、遗传算法、模糊数学、统计 学、贝叶斯算法等。 1 3 本章小结 本章介绍了数据库知识发现，其内容包括k d d 定义、过程、方法、 模式、发展和原型系统；数据挖掘的定义、知识的表现形式、方法等， 其实质是挖掘出用户所感兴趣的、潜在的知识或模式。广义的数据挖掘 是指从大量的数据中发现隐藏的、内在的和有用的知识或信息的过程： 狭义的数据挖掘则是指知识发现中的一个关键步骤，是一个挖掘有用模 式或建立模式的重要环节。数据挖掘是对数据集全面而深刻认识的基础 上，对数据内在和本质的高度抽象与概括，也是对数据的认识从感性认 识到理性认识的升华。此外，还简要说明了k d d 和数据挖掘的发展前景 和应用领域，进一步对未来数据挖掘的方向和挑战进行了展望。 第二章关联规则及其发现 关联规则挖掘是当前数据挖掘研究的主要内容之一，侧重于发现数 据中不同项目间的关系。关联规则是r a k e s ha g r a w a l 等人提出的数据挖 掘领域中的一个重要课题，它揭示数据间的相互关系。关联规则挖掘就 是从一组给定的数据项以及交易集合( 每条交易是一个数据项的集合) 中，分析出数据项集在交易集合中出现的频度关系。 2 1 关联规则的定义 令卜【i i ，i 2 ，i 3 ，i 。】是n 个不同项目的集合( i t e m s e t ) ， 事务 ( t r a n s a c t i o n ) 可表示为 t i d ， ) ，其中t i d 为事务表 示号。全局唯一，d 为事务数据库，其中每个事务t 是i 中的一些项目 的集合。关联规则就是一个如x j y 的逻辑蕴含式，其中x c t y c t 且 x n y = g 。若事务数据库d 中有s 的事务包含x u y ，则关联规则的支 持度可定义为s u p p o r t ( x y ) = s u p p o r t ( x u y ) = s ；若事务数据库中包含x 的事务中同时也包含y ，则关联规则x j y 的可信度( c o n f i d e n c e ) 町定 义为c o n 靠d e n c e ( x ：y ) = s u p p o r t ( x u y ) s u p p o r t ( x ) ) e 为了有效挖掘关联规则，必须给定最小支持度( m i n s u p p o r t ) 和最 小可信度( m i n c o n f i d e n c e ) 。挖掘关联规则就是求解所有支持度和可信 度均分别超过最小支持度和最小可信度的规则，即要求满足： s u p p o r t ( x j y ) 三m i n s u p p o n ，c o n f i d e n c e ( x j y ) m i n c o n f i d e n c e 的规则 x j y 。因此求解可以分解为两个子问题：( 1 ) 从事务数据库d 中找出所 有的频繁项目集：( 2 ) 利用频繁项目集生成不低于最小可信度的关联规 则。 挖掘关联规则的算法已经有很多，比较重要的有r a k e s ha g r a w a l 等 人提出的a p r i o r i 算法，r a m a k r i s h n a nsr i k a n t 等人提出的挖掘定量关联规 则的算法。 由于实际数据库中存在许多相关性较弱的属性，使所挖掘出的关联 规则可能存在大量冗余和错误，并可能毫无联系。另一方面是舰则的组 合爆炸。采用不确定系数法约简相关性较弱的属性能有效地解决该问 题。不确定系数法由用户选择相关性，以消除对问题求解相关性较弱的 属性，达到简化求解的目的。 挖掘关联规则的算法允许用户随时调整最小支持度( 阈值) ，以得出 合理的结果，如果中间结果已经令人满意，用户也可以随时终止算法的 执行。 2 2 关联规则提取方法的研究方向 2 2 r 提取方法的研究方向 1 、挖掘关联规则的般步骤 r t a g r a w a l 等人首先提出了关联规则的采掘问题并给出了解决此问 题最原始的算法a i s 之后，该问题得到了国际人工智能和数据库等领域 学者的密切关注，提出了多种的算法。所有的采掘算法不论它是采用什 么数据结构，其复杂程度、效率如何，可以分为如下几个步骤。 a ，预处理与采掘任务有关的数据。根据具体问题的要求对数据库进 行相应的操作，从而构成规格化的数据库d 。 b ，针对d ，求出所有满足最小支持度的项集，即频繁项集。由于一 般情况下我们所面临的数据库都比较大，所以此步是算法的核心。 ，生成满足最小置信度的规则，形成规则集r 。 d ，解释并输出r 。 2