（计算机软件与理论专业论文）基于扩展概念格的多数据源分类知识融合问题研究.pdf

基于扩展概念格的多数据源分类知识融合问题研究 摘要 数据挖掘领域里，分类问题一直以来都是的一个重要研究分支。在当前多 数据源数据日益普及的情况下，对数据挖掘领域中分类问题的研究也提出了新 的挑战，例如如何从多个数据源中提取出分类知识，并加以有效的融合。因此， 研究一种有效的多数据源分类知识融合方法己成为当前数据库中知识发现的一 个重要的研究方向。 概念格，是一种通过概念间的内涵和外延以及例化和泛化的关系来表示知 识的模型。在概念格的内涵中引入等价关系，便可得到概念格的扩展模型，即 扩展概念格，这种模型更加有利于分类知识的提取。本文的主要研究内容如下： 1 采用基于扩展概念格的方式，首先在每个数据源上建立对应的扩展概念 格，然后从中提取出所需的分类知识，再加以有效的融合。文中涉及到了两种 方式的知识表现形式：分类规则和分类子格，和与它们相对应的两种融合机制。 对于这两种融合机制所得到的分类知识的完备性，都在文中给与了理论证明和 实验验证。 2 。对概念格扩展模型采用预剪枝的策略，来抑制过拟合现象的出现。概念 格扩展模型具有较高的模型复杂度，一方面使其能够对训练数据集进行十分准 确的分类，另一方面有会使得它很容易引起模型“过度拟合”现象的出现，从 而影响到分类器在实际测试数据上的准确率；对此文中采用了对格进行预剪枝 的方法。阻止格中部分不必要的分支的出现，从而降低模型的复杂度，避免模 型过度拟合现象的出现。 3 在上述研究工作的基础上，实现了基于多扩展概念格的分类知识发现原 型系统。 关键词：数据挖掘，k d d ，概念格，多数据源，分类子格 i l l t h er e s e a r c ho nm u l t i - d a t a s o u r e ec l a s s i f i c a t i o na m a l g a m a t i o nb a s e do n t h ee x t e n d i n go fc o n c e p tl a t t i c e a b s t r a c t c l a s s i f i c a t i o nh a sa l w a y sb e e na ni m p o r t a n ts u b - b r a n c ho fd a t am i n i n g n o w a d a y s ，m o r ea n dm o r em u l t i d a t a s o u r c ed a t ac o m i n gi n t op e o p l e sd a i l yl i f e ， a n dt h i sa l s ob r i n g sn e wc h a l l e n g ei n t od a t am i n i n gf i e l d ，s u c ha sh o wt od i s c o v e r y k n o w l e d g ef r o mt h i sk i n do fd a t aa n da m a l g a m a t et h e me f f e c t i v e l y t h e r e f o r e ，t h e r e s e a r c ho nh o wt o a m a l g a m a t e c l a s s i f y k n o w l e d g ee f f i c i e n t l y f r o m m u l t i d a t a s o u r c ec o m e st ob eai m p o r t a n td i r e c t i o no nt h i sf i e l d c o n c e p tl a t t i c ei s am o d e l ，w h i c hr e p r e s e n t st h ek n o w l e d g ew i t ht h er e l a t i o n b e t w e e nt h ei n t e n s i o n sa n dt h ee x t e n s i o no 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 b yi n t r o d u c i n ge q u i v a l e n t i n t e n s i o ni n t oc o n c e p tl a t t i c e ，w eg o tt h ee x t e n d i n gf o r m a lo fc o n c e p tl a t t i c e ( e c l ) ，w h i c hi sa ne f f i c i e n tt o o lt od i s c o v e r yc l a s s i f i c a t i o nr u l e s t h ec o n t e n to ft h e d i s s e r t a t i o ni sa sf o l l o w s ： 1 a l lm e a s u r e sm e n t i o n e di st h i sa r t i c l ew e r eb a s e do ne x t e n d i n gf o r m a lo f c o n c e p tl a t t i c e f i r s t l y , b u i l de c l m o d e lr e s p e c t i v e l yr e f e r r i n gt oe a c hs i t e ；a f t e r t h a t ，e x t r a c tk n o w l e d g ef r o me a c hm o d e l ；f i n a l l y , a m a l g a m a t i n gt h e me f f e c t i v e l y t w ok i n d so fc l a s s i f yk n o w l e d g e ，c l a s s i f yr u l e sa n dc l a s s i f ys u b l a t t i c e ，w e r eu s e d h e r ea n dt h e i rc o r r e s p o n d e dm e t h o d sa r ei m p r o v e db o t hb yt h e o r ya n de x p e r i m e n t s 2 e e lh a sah i g hm o d e lc o m p l e x i t y o no n eh a n d ，t h i sf e a t u r ec o u l de n s u r e t h et r a i n i n gs e tb e e nc l a s s i f i e dv e r yp r e c i s i o n ，o nt h eo t h e rh a n d ，i ta l s oo f t e nc a u s e m o d e lo v e r f i t t i n g ，w h i c hw o u l dh u r tt h ep e r f o r m a n c eo ft h ec l a s s i f i e r ，s ow et a k e t h em o d e lp r e p r u n i n gt e c h n i q u ei n t o t h i sa r t i c l e ，a n dp r e v e n tt h eu n n e c e s s a r y s u b - b r a n c h sa p p e a r a n c e t h e r e f o r e ，t or e d u c et h ec o m p l e x i t yo ft h em o d e la n d a v o i dt h em o d e l so v e r f i t t i n g 3 b a s e do nt h ew o r ks t a t e da b o v e ，ap r o t o t y p es y s t e mt h a tc a nu t i l i z em u l t i - e x t e n d i n gc o n c e p tl a t t i c e c l a s s i f i c a t i o nk n o w l e d g ed i s c o v e r y i nd a t a b a s ei s i m p l e m e n t e d k e y w o r d s ：d a t am i n i n g ，k d d ，c o n c e p tl a t t i c e ，m u l t i d a t a s o u r c e ，c l a s s i f y s 1 】b i ，a t t i c e 图 图 图 图 图 图 图 1 1k d d 的处理过程模型 1 2 典型地数据挖掘系统结构 插图清单 3 1 c o n t e x t l 建出的格弦含了l 1 ) 3 2c o n t e x t 2 建出的格( 蕴含了l 2 ) 3 3 分类子格融合后的结果一一格l 1 2 3 4c o n t e x t 建出的格( 蕴涵了l ) 5 1m e c lc k d 系统功能模块图 v i i i 2 4 2 7 2 7 2 8 2 8 4 0 表格清单 表3 1 上下文c 表3 2r u l e s ( l 1 1 ，r u l e s ( l 2 ) 及r u l e s ( l 1ul 2 ) 表3 3r u l e s ( l 1ul 2 ) 与r u l e s ( l ) 结果对比， 表3 4 两种融合方法的结果比较 表4 1 训练数据集s 表4 2 测试数据集t 表4 3 分类子格预剪枝前后的误分类率比价 表4 4e c lc p 与l a t t i c ep n 的比较 i x 2 4 2 4 2 5 2 9 3 1 3 2 3 7 3 8 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 金鳇王些盍堂 或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 学位论文作者签名：_ 三弓马签字日期：园缈，年4 月始曰 学位论文版权使用授权书 本学位论文作者完全了解盒罂王些盔堂有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授 权盒鳇王些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 马7 马 签字日期：文耐年4 月。2 9 日 学位论文作者毕业后去向 工作单位： 通讯地址： i l 导师签名： 签字e t 期 电话： 邮编： 卯口? 彤 日 致谢 值此论文完成之际，我谨向我的导师胡学钢教授表示真挚的谢意! 在近三 年的硕士研究生学习中，自始至终都得到了胡老师悉心的指导，所取得的点滴 进步，无不浸透着胡老师的心血。胡老师严谨的治学态度，踏实的工作作风都 是我学习的榜样，不仅在学术上，在做人、处事的原则上，胡老师更是给我指 明了前进的方向。胡老师知识渊博，治学严谨，对闯题有敏锐的洞察力，我的 硕士论文中本身就倾注了胡老师大量的心血。没有他的指导和帮助，没有他对 我论文反复修改和精心提炼，我是不可能顺利完成我的毕业论文的。 同时在这里，我要十分感谢计算机与信息学院的王浩教授，在我攻读硕士 期间，他了我大量的指导、关怀和帮助，并提出了许多宝贵的意见，令我在成 长的路上受益匪浅。 除此之外。我还要感谢我的师姐张玉红，师兄王德必、吴共庆、唐志军等， 与他们一起对数据挖掘的课题进行讨论，集思广益，对我论文的构思有很大的 帮助；感谢合肥工业大学人工智能与数据挖掘研究室每个成员对我的关怀和帮 助，没有这个团结、上进的集体就没有我今天的成绩。 感谢计算机与信息学院的王新生老师、徐静老师为我所付出的辛勤工作! 最后，我要衷心的感谢我的家人，是他们几十年来一直默默地给与我无尽 的关怀和帮助。这种支持不但使我能够顺利地完成学业，也将激励着我在今后 的日子里不断的前进。 v 作者：马冯 2 0 0 6 年4 月 第一章绪论 1 1 k d d 及数据挖掘简介 近年来，随着计算机技术的飞速发展，计算机的处理和存储能力得到了不 断的提高，伴随着数据库技术的不断发展，尤其是数据仓库技术的出现，各行 各业的数据库中几乎都存储着数以亿计的记录，大规模的数据库已经变得越来 越普遍了。然而，目前人们收集和存储数据的能力已经大大超过了对其分析和 综合处理的能力，。从如此大量的数据中，获取有用的知识变得越来越困难了， 这就是被j o h nn a i s b e t t 称之为“信息丰富而知识贫乏”( d r o w n i n gi ni n f o r m a t i o n b u ts t a r v i n gf o rk n o w l e d g e ) 的窘境。因此，如何对大量的数据进行有效地分析、 利用和处理，成为当前的世界共同关注的一个重要研究课题。 随着数据库技术、人工智能、统计和并行计算等技术的发展和融合，数据 库知识发现( k n o w l e d g e d i s c o v e r y i n d m a b a s e s ，k d d ) 【2 ，3 ，4 】便酝酿而生。知识 发现可以简单的描述为从数据中发现有用知识的整个过程，当前的知识发现主 要基于数据库技术、并行算法、统计方法和机器学习等多种方法综合进行知识 发现。知识发现分为若干个过程，通常把其中使用专门算法从数据中提取模式， 然后再通过解释和评价模块转化成用户可以理解的知识的过程称之为数据挖 掘：而在某些应用领域，对数据挖掘与k d d 并不加以严格的区分，将两者视 为同一概念加以使用。 1 1 1k d d 及数据挖的概念 k d d 一词是在1 9 8 9 年于美国底特律市召开的第1 1 届国际人工智能联合会 议上首次提出的，这届学术会议上举行了以k d d 为主题的学术讨论，随后相 继在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年举行了k d d 的专题讨论会。以后每年都召开 国际及亚太地区的k d d 会议。目前，i j c a i 、a a a i 、v l d b 等代表人工智能与 数据库技术研究最高水平的国际学术会议上，和k n o w l e d g ea n di n f o r m a t i o n s y s t e m s ，i e e ec o n c u r r e n c y 等著名杂志对k d d 的研究都占有较大的比例，k d d 已经成为当今计算机科学与技术领域研究、应用的热点领域之一。随着k d d 在国际上的兴起，我国也积极地开展了相应的研究和应用。目前国内许多学术 会议，也都将k d d 列为重要的研究方向，其中有数据库学术会议、机器学习 会议等。 随着对k d d 的深入研究以及k d d 在许多领域广泛而成功的应用，众多的 学者根据自己的对k d d 的认识和理解，给出了很多定义，而其中被公认为比 较完整、深刻和全面的是由f a y y a d 在1 9 9 6 年的会议论文f r o md a t am i n i n gt o k n o w l e d g e d i s c o v e r y ) ) 【l 】中对k d d 给出的定义： “t h en o n t r i v i a lp r o c e s so f i d e n t i f y i n gv a j 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 d u l t i m a t e l yu n d e r s t a n d a b l ep a t t e r n si nd a t a ” 即k d d 是从大量数据中提取出有效的、新颖的、有潜在作用的、可信的、 并能最终被人理解的模式的非平凡的处理过程。 可以看出，k d d 是从数据库中提取有价值知识的过程，进行k d d 的研究 是为了将知识发现的研究成果应用于实际数据处理中，为科学的决策提供支持。 一般认为，从实际数据到发现潜在知识的整个k d d 过程分为以下几个步骤： 数据准备，数据选择，数据预处理，数据转换，确定k d d 目标，确定知识发 现算法，数据挖掘，模式解释与评价，知识表示【5 】。 一般将k d d 中进行知识发现的阶段称为数据挖掘( d a t am i n i n g ，d m ) 【6 1 ， 目前关于k d d 的研究大多着眼于对数据挖掘步骤的研究。某些应用领域对数 据挖掘与k d d 不加区分地使用，某种意义上二者可看作同一个概念。 啊 敷_ 匪本中知识裳规瞬处理过拄横整 图1 1k d d 的处理过程模型 1 1 2k d d 的过程和任务 k d d 的过程包括许多阶段，其中包含数据清理与集成、选择和变换、数据 挖掘、模式评估与表示、形成知识，如图1 ，1 所示。 k d d 过程中的数据清理主要用于消除噪声或不致数据；数据集成主要是 多种数据源的组装和集成，可能需要集成的数据处于不同的位置或不同数据格 式；数据选择从数据库中检索与分析任务相关的数据；数据变换的目的是将来 自各种数据源的数据变换成适合挖掘的形式；数据挖掘根据不同的任务，使用 有关方法发现其中的知识，如各种规则：等价规则，蕴涵规则，关联规则等： 模式评估主要目的在于根据某种兴趣度度量，识别表示知识的真正有趣的模式， 从整个知识发现的过程看。模式评估在评价模式的同时对所发现的知识进行优 化，力求提交给用户的知识最实用，最有价值。知识表示阶段使用可视化和知 2 识表示技术，向用户提交挖掘的结果，为用户的易理解考虑，这个阶段主要采 用可视化或者是相关的显示化的技术。 k d d 的任务主要有两类：预测和描述。预测指的是预测未知的感兴趣的变 量或发现某些实例未来的行为模式；描述是指寻找可以理解的描述数据的好的 模式i “。预测和描述之间的分界不明显( 某些预测模型可用于描述，在某种程 度上是可理解的) ，但理解两者的不同对理解整个发现目标是有用的。特定问题 的数据挖掘的预测和描述是相当重要的。预测和描述可以通过下列方法实现： 1 分类( c l a s s i f i c a t i o n ) ：分类是数挖掘中最为重要的研究分支之。分类 的含义就是指从一组以致的、己经具有类别的训练数据中，提取出一个分类模 型( 分类器) ，然后把该分类模型( 分类器) 应用于数据库中的那些有待进行类 别判断的数据上，从而实现对它们的分类。如今分类问题被广泛应用于银行信 贷，疾病诊断等多个领域。目前常用的分类模型( 分类器) 主要有决策树，神 经网络，统计方法，遗传算法等。其中决策树是应用最广泛的方法之，面这 要归功于其准确率高和计算量相对小的特点。本文主要研究基于多概念格扩展 模型的分类，研究结果表明，基于概念格分类在知识质量上有很大优势。 2 聚类( c l u s t e r i n g ) ：聚类简单的说就是“物以类聚”，即对一系列未分 类客体依据客体属性集进行类别的识别，按照其相似性分成若干类别聚类豹目 的是使属于同一类别的个体之间的距离尽可能的小而不同类别的个体间的距离 尽可能的大，即聚类应该使类内个体问的相似性最大，而类别间的相似性最小。 聚类和分类最大的区别在于，分类是在已知“标记”的前提下，对未知对象划 分类别，而聚类则是根据现有“无标记”对象的特性，对他们进行划分，然后 再“贴上标记”。 3 关联规则( a s s o c i a t i o nr u l e s ) ：关联规刚是指数据对象之间的相互依赖关 系，而发现关联规则的任务就是从数据库中发现那些确信度和支持度都大于绘 定值的强规则。关联规则的发现，目前已经从单一概念层次发展到多个概念层 次上的发现。在概念层次上的不断深入，使发现的关联规则能提供更具体的信 息，这实际上是逐步深化发现知识的过程。常见的关联规则发现算法有a i s ， s e t m ，a p r i o r i ，d h p 等。关联规则挖掘的研究在最近几年1 一直是数据挖掘界 中异常热门的课题之一。 4 序列模式( s e q u e n t i a l p a t t e r n s ) ：序列模式是指在多个数据序列中发现共 同的行为模式。序列模式发现算法的框架与之前龌到的发现关联规则十分相似。 在序列模式发现算法的过程中，包括了候选频繁情节的生成和在事件序列中识 别候选情节两个过程，而这两个过程组成了一步迭代。序列模式发现算法就是 这样不断地多次迭代，直至不能再产生频繁情节为止。例如，对序列数据库中 的某顾客，序列模式就是指能在该数据库中寻找到的所有的最长频繁序列。 5 偏离发现( d e v i a t i o nm i n i n g ) ：是指数据库中客体与常规或期望模式的 偏离发现或谬估。客体的期望行为通常由用户给定或根据假设( 如平均、线性 增长) 计算得知。例如网络中的服务器上发现某些站点访问方式在某段时间内 其行为不同于大多数其它站点的一种特殊情况。 1 1 3 数据挖掘系统的构成 数据挖掘系统至少要有前文所述的数据挖掘的一般过程，因此必须具备相 关的构件( 见图1 2 ) ：数据预处理构件、数据挖掘引擎、模式评估构件、知识 库构件羽。 知识库 数据库数据仓库 图1 2 典型地数据挖掘系统结构 l 数据预处理：主要是将不同形式的数据经过集成、转换为可以被数据挖 掘引擎所能识别和使用的数据，为挖掘准备数据。在这个阶段，除了完成多种 数据的集成外，还要进行数据的预处理工作，将噪声和异常数据尽力删除，并 把所要进行挖掘的数据表示成种合适的数据形式，便于挖掘。 2 数据挖掘引擎：接受处理过的数据，根据挖掘任务的要求选用合适的挖 4 掘算法，从数据中提取有用的模式。 生成和对知识库中先验知识的利用。 法。 这个阶段的主要任务是完成算法、模式的 同时为了提高效率，利用先验知识优化算 3 模型评估：模式的有效性、新颖性、有价值和可理解性是评价模式的标 准。如前所述，通常使用兴趣度概念来刻画，兴趣度在挖掘过程中可以是用户 和挖掘引擎的交互接口，用户通过它控制挖掘集中到有趣的模式上。有时直接 将该构件集成在挖掘引擎中，提高挖掘的效率。 4 知识库：知识库是经过专家和用户的检验和认可的模式。可以在新的挖 掘任务中使用和进化。 该系统的核心在于数据挖掘引擎和模式评估模块的设计，用户通过各个模 块的接口控制或者是约束模块的行为来达到挖掘的效率和精度要求。 1 1 4 数据挖掘所面临的挑战 经过近十多年的发展，k d d 在研究和应用方面取得丰硕的成果，但依然面 临来自研究和应用方面的挑战。在k d d 的研究领域中，随着数据的激增和数 据形式的不断发展，必须解决下列问题： 1 数据库的多样性问题 关系的和复杂的数据类型的处理。由于关系数据库和数据仓库已经广泛应 用，因而数据库中可能包括复杂的数据对象、超文本和多媒体数据、空间数据、 时间数据或事务数据等。由于数据不同，数据挖掘任务不同，实现所有的挖掘 任务的通用方法是不现实的。而各种挖掘系统都是根据数据类型和挖掘任务来 决定挖掘系统。 2 数据挖掘的性能问题 数据挖掘由于面向的是大规模数据库，因而算法的运算量较大，因此，改 进算法的时间和空间性能一直是一个重要问题。当前较常用的方法有并行的挖 掘、分布式的挖掘和增量挖掘方法以及利用先验知识来提高挖掘的效率和精度。 3 数据的预处理问题 噪声数据和不完全数据的存在，使得数据集合呈现过分拟合的状态，在此 之上而进行的挖掘必然受到影响，使得挖掘的效率和精度得不到保障，因此必 须在预处理的过程中予以删除。 4 先验知识的应用 利用背景知识指导挖掘过程，并使发现的模式以简捷的形式表达。先验知 识的运用可以提高挖掘的速度和准确率，同时，先验知识来自于过去的实际数 据，需要适应现在的数据和进一步地调整。 1 2 多数据源数据挖掘思想的引入 当前大量的数据几乎都是来自与多个不同的数据源，这一特点给数据挖掘 领域提出了新的挑战，很多研究者尝试各种途径来解决这难题，其中高性能 计算机和多数据源环境被认为具有很好的应用前景。本文引入多数据源数据挖 掘的思想，探讨基于多个扩展概念格的分类问题研究。 1 2 1 多数据源数据挖掘的提出 随着信息化的逐步深入，计算机和数据库等相关技术的不断发展，数据库 发生了新的变化，它们主要表现在以下三个方面： 1 数据量的剧增。例如美国劳伦斯国家实验室的粒子碰撞试验每年产生的 数据容量高达一万盘三十o b 的磁带；美国n a s a 发射的用于地球观测的人造 卫星每年都向地面返回一千零一十五字节数据；美国数字图书馆的数据以每年 一千零一十二字节的速度增长。所有这样都表明的当今数据库中数据的急剧膨 胀。 2 数据复杂度的迅速增长。出现了各种各样复杂的数据类型，如视频数据、 音频数据、多媒体数据、甚至是“行为”数据等。 3 多数据源数据库的不断增加。随着远程通信基础设施的迅速发展，特别 是i n t e r n e t 与w e b 技术的出现，多数据源数据库的不断增加，需要对分布在不 同地理位置的、甚至是不同应用领域的数据库进行数据综合、分析等。如n a s a 地球观测系统从不同的卫星上收集的数据分散存储在不同的地理位置。这就对 多数据数据挖掘这个领域提出了新的挑战。 数据挖掘领域中，针对上述这些特点出现了大量的、新的挑战性问题 2 2 , 2 3 】。 尽管当前关于数据挖掘的理论和应用研究发展迅速，但仍然不能很好的满足数 据飞速变化的需要。目前对上述三个特征的研究中，对2 的研究相对较少，大 多都集中在l 和3 上。 传统数据挖掘方法中，数据是常驻内存的，这一特点在处理有1 0 t 2 字节容 量的大规模数据库时便成为了制约其进一步研究的一个瓶颈。【c o h e n9 5 中提 到c 4 5 算法的时间复杂度大致为o ( n 3 ) ，如果在1 5 0 m h z 的处理器上，对5 0 0 ，0 0 0 条记录进行运算的话，将要花费7 9 年的时间； p r o v o s t & a r o n i s9 6 对7 0 ，0 0 0 条记录进行规则提取，其串行算法是不现实的，因为所需时间太长。c p u 的速 度、内存和i o 带宽限制成为当前大规模数据挖掘面临的主要挑战。虽然进行 数据抽样在一定程度上可提高时间效率，但这种方法以信息丢失为代价，故导 致了模型准确率的损失。为此，在保持一定准确率的前提下，提高数据挖掘方 法的效率是大规模数据挖掘必须要解决的问题。而本文的研究工作中，有相当 一部分，就是针对这个问题展开的。 与此同时，并行、分布式计算环境在计算机硬件系统和计算机有线、无线 通信的飞速发展下得到普遍的应用，多处理并行机和i n t e r n e t ，i n t r a n e t ，局域 网，无线网络等都是计算机硬件系统和计算机有线、无线通信的飞速发展的结 果。这些计算环境都有不同的分布数据存储和多节点计算资源，多数据源数据 挖掘的任务之一即是要合理的管理、利用这些资源。 6 基于这种背景，国内外的专家学者致力于对多数据源数据挖掘这一领域的 研究，并取得了一定的成果。目前这方面的研究主要集中在两个方面： 1 ) 借助分布式的硬件平台强大的并行计算能力进行数据挖掘或是提出数据 挖掘中相关任务的并行算法。这些平台包括共享内存系统，分布式内存系统， 工作站网络，内存系统群组成的混合系统等。 2 ) 将数据或任务进行划分，借助于高速网络连接的各计算机或工作站进行 知识发现。这种方法也应用于异构数据库的知识发现中。 某种程度上，两种方法互相借鉴、促进。在实际应用中，前者经常作为后 者的一个组成部分一。 1 2 2 多数据源数据挖掘的研究现状 当前大部分的算法都是在每个数据节点运行相同或不同的挖掘算法，产生 局部模型然后对各局部模型进行融合，最终产生一个全局模型。这种方法成 功与否，很大程度上依赖于融合过程【2 5 】的质量。一般来讲，局部模型仅能对其 本地数据进行知识发现，反映了本地数据的特性，但缺少全局知识的信息。因 此，许多算法还需要从各局部数据中提取部分数据，形成一个集中的“全局数 据集合”来支持整合过程，因此从这点来说，各节点间最小的数据交互量的大 小对算法的成功与否起着很重要的作用。 多数据源数据挖掘自提出以来一童受到国内外专家、学者的关注，并在数 据挖掘的各个方向如分类、关联规则，聚类等展开了积极的研究，并取得了相 应的成果。下面简单的介绍一下各个方向的研究概况。 1 多数据源的分类模型( 分类器)一般的多数据源数据库包括同构型和 异构型两种。大多数多数据源分类模型( 分类器) 采用“合唱学习”的整和策 略来提高分类模型的准确率。多数据源分类模型( 分类器) 首先在各个数据源 上产生多个模型( 基础分类器) ，而各个数据源中的数据集一般都是是同构的， 然后再组合基础分类器以提高准确率，一般采用“投票”方案( 加权或者非加 权) 。“r e c t a l e a r n i n g ”框架是一个比较著名的“合唱学 - j ”方案，它提供了一 种从同种多数据源中挖掘分类模型( 分类器) 的方法。在这个方法中，监督学 习技巧被应用于局部数据集上的分类模型( 分类器) 挖掘，随后透过局部学习 概念来产生个数据集，并依据这个数据集来生成最终的分类模型( 分类器) 。 m e t a l e a r n i n g 之所以被称为典型的代表，是因为它展示了多数据源挖掘算 法的两个重要特征：高并行性能和低通信负载。所有的基础分类器在各个节点 上同时独立产生，然后和校验集一块被收集到中心节点上。其通信负载与传递 整个源数据的并行算法比起来可以忽略。 2 分布式关联规则挖掘c o u n td i s t r i b u t i o n ( c d ) 和d a t ad i s t r i b u t i o n ( d d ) 是两个典型的分布式关联规则挖掘算法，它们是由r a g r a w a l 和j c s h a f e r 在 1 9 9 6 年提出的1 26 1 ，但这两个算法都在一定程度上存在着问题。因此此，一种新 的算法i n t e l l i g e n td a t ad i s t r i b u t i o n ( i d d ) 算法便应运而生了，它是由e u i h o n g h a n ，g e o r g ek a r y p i s 以及v i p i nk u m a r 等人提出的，用以改进d d 算法。然而， i d d 算法的通信量依然随着交易记录的个数线性增长。为了克服这一缺陷，他 们又提出了一种组合了c d 算法和i d d 算法的优点的新算法一一h y b r i d d i s t r i b u t i o n ( h d ) 算法，并取得了较好的结果。 3 分布式聚类分布式聚类算法大多致力于以并行方式执行聚类算法，有 两种途径：第一种是通过聚合方法提供近似的距离度量标准；第二种通过数据 广播提供精确的距离度量【1 9 2 7 2 8 1 。 目前较为成熟的多数据源数据挖掘系统有：j a m 2 纠，p a p y r u s 2 0 ，3o 】等。其中 j a m ( j a v a a g e n t sf o r m e t a 1 e a r n i n g ) 是由c o l u m b i a 大学开发，使用j a v aa p p l e t s 技术。j a m 是第一个使用m e t a 1 e a r n i n g 方法的系统，支持多种引导式学习算法。 该系统现用于对金融信息系统中欺诈和非法入侵等行为的侦测。 一般地，分布式处理方法是用准确率来换取速度的，因为其是在局部数据 而不是全局数据上运行算法【c h a n & s t o l f o9 4 】， c h a n & s t o l f o9 3 】，准确率自 然会降低。本文将把多数据源数据挖掘的臆想应用于概念格的分类求解过程中， 试图实现对多数据源的分类知识进行提取并加以有效的融合，从而获得适用与 全局的分类知识。 1 3 本文的课题来源和内容组织 1 3 1 本文的课题来源 本文的课题来源于安徽省自然科学基金课题( 编号0 5 0 4 2 0 2 0 7 ) 和合肥工 大科研发展基金课题( 编号0 5 0 5 0 4 f ) 资助。 1 3 2 本文的内容组织 本文的内容组织如下： 第一章简述数据库中的知识发现的产生背景以及发展前景，详细阐述了 其中的分类问题，并引入了多数据源数据挖掘的思想。最后说明本文的研究重 点和课题来源，并简要给出文章的组织结构。 第二章介绍本文所采用的概念格扩展模型，给出其相关术语，并讨论了 模型的性质以及构造方法，这是全文的理论基础。 第三章讨论了基于多概念格扩展模型进行分类融合问题求解的方法。提 出面向多数据源分类问题求解时，利用概念格自身对提取分类知识时的完备性， 来实现各个站点上的分类知识的完备型融合；并通过两种不同的知识表现形式： 规则集合和概念子格，实现了这种融合的方法。 第四章将过度拟合的思想引入概念格扩展模型的分类过程，并对概念格 扩展模型进行了剪枝，通过这种方法，在保证准确率可以接收的条件下，提升 算法的空间性能。重点讨论了概念格扩展模型剪枝的评价标准，已经剪枝后所 能够达到的效果。 第五章介绍了基于概念格扩展模型的分类知识发现系统m c lc d d 。该系 统由数据预处理、概念格的处理、分类知识提取、知识表示和用户界面等模块 组成。基于本文的研究内容，重点介绍了分类知识提取和知识表示模块。 第六部分全文的总结，对本文的主要研究工作进行简要的阐述和说明， 并对下一步的工作进行了展望和探讨。 1 4 小结 本章主要介绍了k d d 和数据挖掘的背景知识，并介绍了当前该领域的研 究现状。接着重点阐述了数据挖掘中的分类问题，给出分类的定义，以及目前 用于分类的常用方法，并引入了多数据源数据挖掘的思想。最后，给出了本文 主要内容和组织结构。 9 第二章概念格及其扩展模型 2 1 概念格的数学模型 2 1 1 代数格 格论形成于1 9 3 5 年左右，是代数学的一个重要分支，此处我们简称其为代 数格。由于代数格式概念格的数学原型，因此我们在介绍概念格前，先简要介 绍一下代数格的一些基本概念1 3 2 】。 定义2 1设a 是一个集合，如果a 上的一个关系r ，对于v x ，y ，z e a ，满 足如下条件：x r x ( 自反性) x r y ，y r x j x = y( 反对称性) x r y ，y r z j x r z ( 传递性) 则称r 是a 上的一个偏序关系，把它记作“”。序偶 称为偏序集。 定义2 2设 为偏序集且b a 为一个子集，如有a e a ，且对b 的 任意元素x ，都满足x a ，则称a 为子集b 的上界。同理，且对b 的任意元素 x ，都满足a x ，则称a 为子集b 的下界。 定义2 3设 为偏序集且b c _ a 为一个子集，a 为b 上的任一上界， 若对于b 的所有上界y 均有a y ，则称a 为b 的最小上界( 上确界s u p e r m u m ) ， 记作s u p ( b ) 。同样若b 为b 上的任一下界，若对于b 的所有下界z 均有z b ， 则称b 为b 的最大下界( 下确界i n f i m u m ) ，记作i n f ( b ) 。 定义2 4设 为偏序集，如果a 中任意两个元素都有最小上界和最 大下界，则称 为格。 定义2 5设 是一个格，如果在a 上定义两个二元运算v 和八，使 得对于任意的a ，b e a ，a v b 等于a 和b 的最小上界，a 八b 等于a 和b 的最大下界， 那么，就称 为由格所诱导的代数系统。二元运算v 和分别称为并 运算和交运算。 通常，我们用a v b 来代替s u p ( a ，b ) ) ，a a b 来代替i n f ( a ，b ) ) 。类似的分别 用v b 和八b 来代替s u p ( b ) 和i n f ( b ) 。 定义2 6 设 是一个偏序集如果对于任意非空的集合s c _ a ，都存在 有vs 则 被称为是一个完全并半格，类似地，如果对于任意非空的集合 s c _ a 都存在有八s 则 被称为是一个完全交半格。如果 既是完全并 半格完全交半格，则它是一个完全格。 2 1 2 概念格 在形式概念分析中，数据集是以形式背景( c o n t e x t ) 的形式给出的，有关 概念格和e c l 的详细描述请参见文献5 3 1 ，1 5 ，1 6 1 ，这里只简要地介绍一些基本的 概念。 定义2 7 ：已知形式背景c = ( o ，d ，r ) ，其中o 是对象集合，d 是属性 集合，r 是o 和d 之间的一个二元关系，则存在唯一的偏序关系与之对应，并 且这个偏序关系产生一个格结构，这种由c 所诱导的格就称为一个概念格( 或 g a l o i s 格，简记为g c l ) 。 定义2 8 ：设c l = ( a 1 ，b 1 ) 和c 2 = ( a 2 ，b 2 ) 是格中的两个概念，其中 的偏序关系“”定义为c l c 2 铮b 2 c _ b l 铮a l c a 2 。此时称c l 是c 2 的子概念 ( s u b，2 是c 1 的超概念 ) 。并且如果不存在概念c = ( a ，b ) _ c o n c e p t ) c ( s u p e rc o n c e p t 使得c 1 c c 2 成立，则定义c 1 ，c 2 为直接子概念直接超概念( i m m e d i a t e s u b c o n c e p ti m m e d i a t es u p e r c o n c e p tr e l a t i o n 】，记作c i c 2 。 定义2 9 ：每一概念( a ，b ) 描述了一组对象及其公共的特征。属性b b 称为该概念所支持的属性，对象a a a 称为该概念所覆盖的对象。而且，每个概 念( a ，b ) p ( o ) p ( d ) 对于关系r 是完备的，即概念必须是最大扩展的，这 是概念格的完备性( c o m p l e t e n e s s ) 。 概念格是一个完全概念格，因此，对于概念格中的任意结点子集，都存在 唯一的最大下界和最小上界。给定概念格l 中的一个概念族c = ( a 。，b 。) ( t l ) 有最大下界 和 最小 上界，我们 分别用 i n f d = 吨j 4 ，( 【且) ”) s u p o = ( u 4 ) ”，u 县) 来表示。 一艘粜说，一个规范的形畿背景敦其概念格可以得到大量的关联规则。 用图形方式表示概念格是传播知识和建立透明的高层次的有效方法。知识的各 种连接和解释可以通过各种概念格的哈斯图( h a s s e ) 来实现可视化。概念格的 哈斯图是根据这种概念格偏序关系产生的，即如果c 1 c 2 ，则哈斯图中就对应 条从c 1 到c 2 的边。 2 2 概念格的扩展模型 概念格是一种完备的层次结构，揭示了概念泛化与例化及内涵与外延之间 的关系，适用于从数据库中提取知识问题的描述。然而，概念格中概念的内涵 表示不能清晰地反映出内涵间的关系，且由于所表示的关系不是约简形式，一 定程度上影响了知识的求解。文【8 】通过在概念格中引入等价内涵关系而得到概 念格的扩展模型，( e x t e n d e dm o d e lo fc o n c e p tl a t t i c e ，简称e c l ) ，使表示形 式更为直观、简洁，更有助于数据分析与数据库知识发现问题的描述。下面对 概念格的扩展模型作简单的介绍。 定义2 1 0 ：对形式背景( 0 ，r ，d ) 中的概念( a ，b ) ，如果b 1 c a 满足b l = a ， 则称b l 为a 的一个等价内涵组，记作e q u ( a ) = b l i b l ca i 且b 1 k a 。 定义2 1 1 ；称从形式背景( 0 ，r ，d ) 得到的二元组( a ，b ) 为一个基本概 念，其中，a e p ( o ) ，b p ( d ) ，并且b e q u ( a ) 。a 和b 分别称为概念的 外延和一组内涵。每一个基本概念描述了一组对象及其所共有的一组特征。称 形式背景中的基本概念c l _ ( a ，bl ) 和c 2 = ( a ，b 2 ) 为两个等价的基本概念， 简称等价概念，b i ，b 2 为等价内涵。等价概念反映了同一概念的不同描述形式。 定义2 1 2 ：若一个概念的内涵不存在等价内涵，则称该概念为单一概念。 若一个概念的内涵b 1 存在多个等价的内涵b 2 ，b k ，则称这一概念为多重 概念。概念( a ，e q u ( a ) = b 1 ，墩) ) 称为扩展概念，简称概念。特别地， 称包含所有对象的概念为全概念，而空集所对应的概念为空概念。 定义2 1 3 ：形式背景c = ( o ，d ，r