（计算机应用技术专业论文）基于概念格模型的分布式关联规则挖掘研究.pdf

基于概念格模型的分布式关联规则挖掘研究 摘要 分布式关联规则挖掘研究是为解决分布式环境下的关联规则挖掘问题而出 现的新课题，具有重要的理论和实际意义。概念格通过概念的内涵和外延之间 的关系以及泛化和例化之间的关系来表示数据和知识，因而适用于关联规则发 现的问题研究。然而，由于格结构的完备性致使格的规模随数据库规模的增长 而快速增长，一定程度上影响了概念格模型在知识发现研究领域中的应用。本 文在对概念格及其扩展模型进行研究的基础上，着重研究了基于剪枝概念格模 型的分布式挖掘关联规则问题。 论文主要工作如下： ( 1 ) 在深入研究概念格上数据和知识表示的基础上，着重讨论了概念格剪 枝模型的相关理论，并给出了相应的剪枝格构造算法。 ( 2 ) 比较研究了基于剪枝概念格上频繁项集表示与基于a p r i o r i 性质的频繁 项集表示方法，发现前者能够更加简洁地表示频繁项集、更加精确地反映原始 数据库中的关联信息。 ( 3 ) 研究了利用剪枝格模型从多数据源上提取关联规则问题；给出相应的 算法u m p l ，并用实验证明了算法的有效性和正确性。 ( 4 ) 实现了基于概念格的关联规则挖掘原型系统。 关键词：数据挖掘概念格 关联规则分布式挖掘 r e s e a r c ho nd i s t r i b u t e da s s o c i a t i o nr u l e sm i n i n g b a s e do nc o n c e p tl a t t i c e s a b s t r a c t d i s t r i b u t e da s s o c i a t i o nr u l e sm i n i n g ，e m e r g i n gf o rs o v l i n gt h ea s s o c i a t i o n r u l e sm i n i n gi nd i s t r i b u t e de n v i r o n m e n t ，i so n eo ft h em o s ta c t i v et o p i ci nt h ek d d f i e l d ，w h i c hi ss i g n i f i c a n ti nt h e o r ya n da p p l i c a t i o n c o n c e p tl a t t i c er e p r e s e n t sd a t a a n dk n o w l e d g eb yt h er e l a t i o n sb e t w e e n tt h ee x t e n s i o na n di n t e n s i o no fc o n c e p t ， a n db yt h eg e n e r a l i z a t i o n s p e c i a l i z a t i o nr e l a t i o n s h i pb e t w e e nc o n c e p t s ，w h i c hi s s u i t a b l ef o rt h es t u d yo fa s s o c i a t i o nr u l e sm i n i n g t h em a t u r i t yo ff r a m e w o r ko f l a t t i c e ，l e a d i n gu pt ot h er a p i d l yi n c r e a s eo fs i z eo fl a t t i c ea l o n gw i t ht h ei n c r e a s e o fd a t a b a s e ss i z e ，i m p e d e sc o n c e p tl a t t i c e st h ea p p l i c a t i o ni nk d d b a s e do n s t u d y i n gt h ec o n c e p tl a t t i c ea n di t se x t e n s i o n ，t h ed i s t r i b u t e dm i n i n go fa s s o c i a t i o n r u l e sb a s e do np r u n e dc o n c e p tl a t t i c e sw a sd i s c u s s e di nt h i sd i s s e r t a t i o n t h em a i np o i n t so ft h i sd i s s e r t a t i o na r el i s t e da sf o l l o w i n g ： ( 1 ) b a s e do ns t u d y i n gt h er e p r e s e n t a t i o no fd a t aa n dk n o w l e d g eb a s e do n c o n c e p t ，t h ep r u n e dc o n c e p tl a t t i c em o d e l ( p c l ) i sd i s c u s s e di n d e t a i l t h e c o r r e s p o n d i n gf o r m a t i o na l g o r i t h mo fp c li sg i v e nt o o ( 2 ) c o m p a r i n gt h er e p r e s e n t a t i o no ff r e q u e n ti t e m s e t sb a s e do np r u n e dc o n c e p t l a t t i c ea n da p r i o r i l i k em o d e l t h et h e o r ya n a l y s i ss h o w st h ef o r m e ri sm o r e c o n c i s ea n dm o r ee x a c ti nr e p r e s e n t a t i o no fa s s o c i a t i o ni no r i g i n a ld a t a s e t ( 3 ) s t u d yt h ea s s o c i a t i o nr u l e sm i n i n gf r o mm u l t i p l ed a t as o u r c e sb a s e do n p r u n e dc o n c e p tl a t t i c e s ，a n dt h ec o r r e s p o n d i n ga l g o r i t h mu m p li sp r o v i d e d t h e e x p e r i m e n t a le v i d e n c es h o w st h ev a l i d i t yo ft h i sa l g o r i t h m ( 4 ) t h ep r o t o t y p es y s t e mt h a ti su s e dt om i n i n ga s s o c i a t i o nr u l e sb a s e do n c o n c e p tl a t t i c ei si 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 ，c 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 ，d i s t r i b u t e dm i n i n g 插图清单 图l 一1 数据挖掘是知识发现过程中的一个重要步骤2 图卜2 小波变换实现数据挖掘结构图g 图21 例2 1 的哈斯图1 3 图2 2 上f 文2 - 1 对应概念格的哈斯图1 6 圈23 上下文22 对应的概念格l 22 的哈斯图1 9 图2 4 上r 文2 - 3 对应的概念格l 2 3 的哈斯图2 0 图2 5 上下文2 1 对应的e c l 2 1 的哈斯图2 2 图3 一l 由交易数据库3 1 产生的项格2 9 图4 - 1 分布式挖掘系统的功能结构示意图3 9 图42 上下文23 对应的剪枝概念格p l 2 4 的哈斯图一4 7 图4 - 3 融合多剪枝格的导出琐集数与全局剪枝格上导出项集的比较5 0 图4 - 4u m p l 与a pr 【o r i 算法产生全局频繁集耗费时间比较5 0 图45 规则表示规模的减少5 l 图4 - 6 规则的丢失程度5 1 图5 一la r m 子系统功能模块图5 4 图5 2b c l k d d 系统土界面一5 5 巨j 一3 规则提取菜单一5 6 图5 - 4 集中式挖掘接口5 6 图5 - 5 分布式挖掘接口，5 7 图56 保存挖掘结果界面5 8 表格清单 表2 1 上r 文2 1 1 5 表2 - 2 上下文2 - 2 1 9 表23 上下文2 - 3 一 1 9 表3 一l 交易数据库3 1 2 8 表3 2 购买钢笔和圆珠笔的2 2 相依表3 3 表4 1u m p l 算法与全局剪枝格上频繁项集数量及a p r i o r i 算法时间比较5 0 独创性声明 本人声明所阜交的学位论文是本人在导师指导r 进行的研究r 作及取得的研究成果。据我所 知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得盒魍些太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签字 签字日期：p 锯，月，日 学位论文版权使用授权书 本学位论文作者完全了解金丝工些盘堂有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金胆王些太 堂一可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权一b ) 学位论 签字目 学 工 通 器璐 致谢 在论文完成之际，首先感谢合肥工业大学给我这个学习和提高的机会，特 别是我的导师胡学钢教授三年来对我的悉心指导，借此机会向导师表示衷心的 感谢! 在学习和论文的写作过程中，胡教授给予了我极大的关怀和帮助，从论文 题目的确定、实施方案的制定、具体工作的进展以及最后论文的撰写与修改， 无不渗透着导师的智慧和心血。胡教授渊博的知识、丌阔的视野、分析洞察问 题的能力，都使我受益匪浅。 我要感谢计算机与信息学院人工智能与数据挖掘实验室的老师和同学们， 感谢他们在学习和生活中对我的真诚的帮助，与他们在一起学习生活的点点滴 滴都是愉快而难忘的。尽管我们即将分开，奔赴各自的工作岗位，但是在这三 年中建立起来的友谊如同一杯美酒，随着时间的流逝将越存越浓! 感谢0 4 级与 0 5 级的师弟师妹们，感谢实验室每一个成员对我的关心和帮助! 感谢合肥工业大学计算机学院及研究生院的各位老师，感谢他们在我的论 文工作中给予我的无私的指导和帮助以及在生活上给我的关怀和照顾。 在整个研究生学习阶段，我的工作单位给予了我很大的支持和鼓励，对此 表示诚挚的谢意。 作者：徐勇 2 0 0 6 年5 月 第一章绪论 我们被数据一一科学数据、医疗数据、人口统计数据、财经数据和市场数 据一一淹没，人们没有时间看数据，人类的关注已经成为一种宝贵的资源j 。 2 0 世纪以来，计算机与信息科学、技术的迅速发展，特别是在数据库技术、人 工智能、机器学习、以及计算机硬件等方面所取得的令人吃惊的飞速进步，大 大地推动了商用数据库与信息产业的发展。随之，海量数据的收集、存储成为 可能，但随着人们所获得的数据量的不断增多，人们的注意力越发成为一种宝 贵的资源，人们常常埋没于大量的数据中，却又无法得到足够多的有用知识。 “数据丰富，但信息贫乏! ”【l 】成为这一状况的真实写照。特别是在严重依赖 数据分析的领域中，面对海量和结构复杂的原始数据源，无论是从时间意义上 还是从空间意义上，传统的数据分析方法已经很难满足人们对获取隐藏在数据 背后的内在联系和信息的需要。正是在这种情况下，产生了对能更加有效、更 加强壮地进行数据分析的理论和方法的需求；人们希望有一种新的技术和工具 来帮助人们完成对大量原始数据的分析任务，进而获得人们所需要的有用知识。 这些技术和工具正是知识发现( 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 1k d d 的提出 111k d d 的产生背景 在过去的数十年中，人类产生和收集数据的能力已经迅速提高，起作用的 因素包括如商业事务、政府事务、农业生产和科学研究过程的信息化；条形码 ( b a rc o d e s ) 在大部分商业产品中的广泛使用；快速、高性能和廉价的存储设备： 更好的数据库管理系统和数据仓库技术等信息技术和数据存贮技术的发展。被 有效存储起来的数据爆炸性的增长已激起对新的数据分析技术和自动分析工具 的需求，丁f 是在这种客观需要的推动下，数据库中知识发现( k d d ) 技术应运而 生，并得到迅速发展，越来越显示出其强大的生命力，成为数据库研究、开发 和应用最活跃的分支之一；2 0 世纪9 0 年代开始更是有了突飞猛进的发展，成 为目前涉及人工智能、数据库理论与技术、电子商务等学科的一个非常活跃的 研究领域；在商务管理、生产控制、市场分析、工程设计和科学探索等方面表 现出很好的应用前景，例如加拿大b c 省电话公司要求加拿大s i m o n f r a s e 大学 的k d d 研究组，对其拥有的十多年的客户数据进行分析。该研究组在科学分 析的基础上，提出了新的电话收费和管理办法，制定了既有利于公司又有利于 客户的新政策。经过几十年的发展，知识发现研究的重点逐渐从发现方法转向 系统应用，并且注重多种发现策略和技术的集成，多种学科之间的相互交叉渗 透；随着其后的不断发展，形成为一个建立在数据库技术的基础上，结合人工 智能、机器学习、统计学、神经网络等多种学科技术的具有很强生命力的新研 究领域。特别需要指出的是，数据挖掘技术从一开始就是面向应用的。它不仅 是面向特定数据库的简单查询，而且要对这些数据库进行微观和宏观的分析和 推理，企图发现事件发生的背后所隐藏的规律、模式等有用信息，以指导实际 问题的求解、对未来活动进行预测等。k d d 是一个交叉学科，它从其它诸如： 人工智能、机器学习、数据库、统计学、神经网络等学科吸取营养。因此，统 计学方法、神经网络方法、模糊论方法等都对k d d 过程产生了影响：这种影 响依赖于给定的数据挖掘任务、所挖掘的数据类型等因素。 112k d d 的概念 简单地说，知识发现就是从大量数据中发现、提取有用的知识。数据库中 知识发现k d d 【】2 ，j ，4 jj 一词首次出现于1 9 8 9 年8 月在美国底特律市召开的第1 1 届国际人工智能联合会议上。数据库中知识发现的概念是指从数据集中提取出 隐含的、事先未知的、存在潜在效用、并能被人理解的模式的一个非平凡过程， 简称知识发现或k d d ( 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 ) 6 1 。该术语是指从数据 库中寻找知识的全部过程，而且强调特定数据挖掘方法的“高层”应用；许多 人也把数据挖掘视为k d d 的另一个常用术语，因为数据挖掘步骤是知识发现 过程中非常重要的一个步骤；数据挖掘这一术语应用于统计人员，数据分析员 和m i s 领域，而大部分人工智能和机器学习研究人员使用术语k d d 。本文中 作者有时就用数据挖掘这个名词来代替知识发现以强调前者在后者中的地位。 k d d 是指从数据库中发现有用知识的全部过程，而数据挖掘是指从数据中 抽取模式的算法应用，是知识发现过程中的一个重要步骤。该过程往往是交互 和不断重复的，包括特定数据挖掘方法或算法重复应用和对由这些算法所产生 模式的解释。知识发现过程如图1 1 所示。 图1 - 1 数据挖掘是知识发现过程中的一个重要步骤 从图中我们可以看出，k d d 过程形成知识的过- n n n g n 如下几个步骤， 它们是数据预处理( 包括数据清理、数据集成、数据选择、数据变换) 、数据挖 掘、模式评估、知识表示。其中数据挖掘是基本的步骤，它使用一定的方法提 取数据模式，通过评估进而得到知识。 对于知识发现的概念及知识发现过程，我们可以这样来归纳理解其内涵： 知识存在于数据中。数据是事实的集合( 例如，交易数据库中的事务) ， 称数据d 中的一个表达模式e ( e d ) 为知识。 知识必须挖掘。知识以某种隐含的方式存在于数据中，使得其不能被直接 清晰地表达和转移；必须通过一定的手段，才能将其明确化，以显示的方式出 现在用户面前。 知识是可以被挖掘的。尽管存在于数据中的知识不能够被数据拥有者直接 感受、理解和使用，但是这些知识是一定可以通过某种方法、工具将其显示化。 知识必须是有用的、可被理解的。针对不同的应用场合，不同的用户，知 识呈现出不确定性，只有那些对特定用户来说是有用的，且可以被用户理解的 部分才可以被特定用户称为知识。 1 1 3k d d 的研究现状 1 9 8 9 年8 月，在美国底特律召开的第1 1 届国际人工智能联合会议的专题讨 论会上首次出现k d d 这个术语。随后在1 9 9 l 、1 9 9 3 和1 9 9 4 年都举行了k d d 专题讨论会，汇集来自各个领域的研究人员和应用开发者，集中讨论数据统计、 海量数据分析算法、知识表示、知识运用等问题。随着参与人员的不断增多，国 际k d d 组委会于1 9 9 5 年把专题讨论会更名为国际学术大会，并在加拿大蒙特 利尔市召开了第一届知识发现和数据挖掘国际学术会议( k d d 9 5 ) ，以后每年 召开一次，规模由原来的专题讨论会发展为国际学术大会，参加人数也是逐年 增多，2 0 0 6 年第1 2 届国际k d d 会议( k d d 2 0 0 6 ) 将于2 0 0 6 年8 月在美国费 城召开。亚太地区也于1 9 9 7 年在新加坡组织召开了第一次规模较大的k d d 学 术研讨会( p a k d d - 9 7 ) ，此后p a k d d 每年召开一次，2 0 0 6 年第1 0 届亚太知 识发现与数据挖掘会议( p a k d d 2 0 0 6 ) 于4 月9 1 2 日在新加坡召开。还有 其它一些内容的专题会议也把数据挖掘和知识发现列为议题之一，成为当前计 算机科学界的一大热点。此外，数掘库、人工智能、信息处理、知识工程等领 域的国际学术刊物也纷纷开辟了k d d 专题或专刊。近年来，国际上k d d 领域 的研究重点逐渐从发现方法转向系统应用，更加注重多种发现策略和技术的集 成，以及多种学科之间的相互渗透。目前也有多家软件公司研制成功了他们的 数据挖掘软件产品，不少软件已在北美、欧洲等国得到应用。在我国，也有许 多单位逐步开展数据挖掘方面的研究，但还没有看到数据挖掘技术在我国成功 应用的案例。 1 2k d d 的研究内容 1 2 1k d d 的本质 在数据挖掘作为一门学科出现之前，人类也已经掌握了其它一些数据分析 理论和方法，存在其它一些的数据分析工具，如统计分析方法等。但正如上文 所述，随着数据源的不断膨胀和数据结构的日益复杂，传统的数据分析方法在 很多场合已不能满足客观需要。尽管我们在很多方面已具有了相当高的信息化 程度，如去超市购物，顾客的个人信息或者消费信息被及时地记录在p c 机中； 当患者去稍大一点规模的医院就医时，你的就诊信息也被长期地记录在医院的 患者资料库中。但是在当今信息化程度达到一定的水平、数据容量已经达到万 亿字节规模的同时，人们又不得不面临着信息社会的一类尴尬问题：一方面规 模庞大、纷繁复杂的数据体系让使用者漫无头绪、无从下手，长期以来这些花 大钱做出来的数据库，只是在这样一种指导思想下一一因为反正不贵，而且说 不定哪一天会有用一一为了搜集而搜集起来的；另外一方面，在这些大量数据 的背后却隐藏着很多具有决策意义的有价值的信息。那么，如何发现这些有用 的知识，使之为管理决策、科学研究、经营战略等服务呢? 计算机科学的介入 给出的回答是：知识发现。 上一小节我们已经给出了知识发现的较为中肯的定义了，也知道了知识发 现是用来从大规模和复杂结构的数据中寻找有用信息的途径，那么知识发现同 样作为数据分析的工具，它的本质与其它数据分析方法( 如统计学、数学等) 有 何不同呢? 知识发现得出来的知识是人们事先未知的、但却有用的知识：反过 来说，显而易见的知识不是知识发现的结果，事先已知的、但却需要“验证” 的知识也不是知识发现的结果。知识发现的本质在某种程度上可以说是：很“偶 然地”发现非预期但却很有价值的信息。当然，这种“偶然”的背后存在着必 然，即任何一个知识发现过程的目的必然是要发现知识，而不是另有目的，无 论所发现的知识的类型是什么、它的价值如何。知识发现，既不是要求发现放 之四海而皆准的真理或崭新的自然科学定理，也不是利用计算机来进行定理证 明，更不是去发明知识。所有发现的知识都是相对的，是有特定前提和约束条 件、面向特定领域的，同时还要能够易于被用户理解。 知识发现是在无任何先验指导下开展工作的，而不是事先知道了该数据集 中“可能”存在某种知识，通过一定的分析来验证这种可能是否确定。至少在 目前情况下，在某种程度上可以说知识发现是一种退而求其次的工作，即知识 发现是为了不让那些由于其它目的和用途而积累下来的数据长期被闲置，为了 让这些耗费了相当成本收集起来的数据能够得到充分的利用而进行的一项“无 任何回报期望”的工作而已。 12 2k d d 的理论基础 尽管坚实的和系统的理论基础对于知识发现非常重要，因为它给知识发现 技术的开发、评价和实践提供一个一致的框架，但是有关知识发现的理论基础 研究目前还没有成熟。由于知识发现是一个涉及多个学科领域的学科，这些 学科包括计算机、数学、统计、经济学等，知识发现从如此多个学科汲取营养。 从而，这些学科的理论对知识发现理论的发展有着重要的影响。如统计理论在 知t 发现学习理论上的贡献一贝叶斯网络i 7 弗j 。贝叶斯网络是一个带有概率注 释的有向无环图。这种概率图模型能表示变量之间的联合概率分布( 物理的或贝 叶斯的) ，分析变量之间的相互关系，利用贝叶斯定理提示的学习和推断功能， 可以实现预测、分类、聚类、因果分析等知识发现任务。早在2 0 世纪8 0 年代， 贝叶斯网络就成功地应用于专家系统，成为表示不确定性专家知识和推理的一 种方法。知识发现兴起后贝叶斯网络模型日益受到重视，成为研究知识发现的 一个重要工具。 1 2 3k d d 的研究对象、任务和目的 从宏观上来看，数据挖掘是一门进行数据分析的学科。毫无疑问，数据挖 掘研究的对象是大规模的数据。但是客观上数据挖掘面临的数据往往又不是为 特定数据挖掘任务而专门搜集的。绝大多数情况下，当数据被以各种各样的形 式保存起来时，是另有目的的，而并不是设计来给大家挖掘的。这是数据挖掘 技术与其它数据分析技术重要的不同点之一。数据挖掘处理的数据主要表现出 以下几个特征： 数据规模。对于有些数据分析工具来说，如果数据集包含几千条数据就可能 会很大了，但是对于数据挖掘来说，其处理的数据往往包含几百万条记录甚至 几十亿条记录。 数据来源。如前所述，数据挖掘处理的数据并不是为了挖掘而积累下来的， 而是为其它需要而产生的附带结果。这就导致数据挖掘面对的数据的质量较低， 存在噪音、丢失关键数据等问题。 数据类型。数据挖掘处理的数据结构往往并非是特意为某种特定数据挖掘任 务而设计的，因此在同一次数据挖掘过程中，数据可能包括除数值型数据以外， 还存在文本数据、多媒体数据、图像数据、w e b 数据。原始数据既可能是结构 化的、半结构化的、也可能是非结构化的。 数据质量。包括数据污染和数据完整性等。数据污染、丢失、不完整性在很 多数据库中特别是商业数据库中特别突出，因为如果数据库不是精心设计的， 那么数据可能会包含其它噪音数据、某些重要的特征可能丢失。导致数据污染、 丢失的原因可能是操作者的疏漏，实际系统或测量的失效，也可能是数据收集 过程在时间上的修正而导致的。 所有这些因素都导致数据挖掘的处理对象是大规模的和复杂结构的数据。 从内容上来说，这些数据毫无疑问是与问题相关的，与最终发现出来的知识也 是紧密相关的。但是，这些数据与问题和最终将要获取的知识的联系又不是能 够简单地用“相关”来描述。即在利用数据挖掘技术进行数据分析之前若就已 经知道从这些数据中可能会获得什么类型的知识、甚至什么具体的知识，分析 人员进一步进行数据分析需要做的仅仅只是验证这种事先猜测是否正确而已的 话，那么这种数据分析过程不能称之为数据挖掘过程，这些数据也不是数据挖 掘的处理对象。比如，在研究肺癌疾病成因问题上，研究人员可能会事先从大 量的病例中搜集了相关的数据，包括肺癌患者吸烟与否、非肺癌患者吸烟与否 等，这种事先带有一定目的或者说指导原则而搜集起来的数据不是数据挖掘处 理的对象。同样，这种分析过程也不能称为数据挖掘过程。 原则上说，数据挖掘是在有了数据之后才兴起来的一门学科，其直接的功 能是进行数据的转换，将原始的、大量的、“杂乱”的数据中包含的信息转化 为更加简洁的形式，以利于人的理解。数据挖掘过程可以也应该是在任何类型 的数据上展开。包括数据的存储方式也可以是多种多样的，如关系数据库，数 据仓库，空间数据库，文本数据库，多媒体数据库等。但作为一门进行数据分 析的学科，数据挖掘与其它数据分析理论和方法又存在着很多的不同。 数据的选择。如前所述，数据挖掘从某种程度上来说是在大量的数据中偶 然发现了一些有用的信息。那么由此可以推断，在事先已经知道存在特定具体 知识的那些数据中进行知识的确认或量化则不是数据挖掘的任务。同样可以说， 这一类的数据将不会成为数据挖掘处理的对象。一般来说，作为数据挖掘处理 对象的数据将是那些表面上看似无关、但实际上却包含了有用信息的数据。如： 啤酒与尿布。 数据污染与丢失。由于绝大部分的数据库在建造时都另有目的，并不是设 计来给大家挖掘的，所以数据的质量自然就不会十分理想，不能够十分符合特 定数据挖掘任务的需要。正因为这个原因，在数据挖掘过程中数据的污染和丢 失，从理论上来说是无法避免的。对此，人们可以做到的只能是寻找一个尽可 能好的对策，以最大限度地减少其负面影响。 误判断。和其它数据分析方法一样，数据挖掘也存在对挖掘结果的误判断问 题。具体地包括：挖掘的结果可能是错误的和可能丢失重要的f 确内容；还有 可能由于挖掘的结果规模过大，无法对规则进行筛选、甄别和剔除，导致对挖 掘结果的误理解。 概括地说数据挖掘的任务和目的就是在数据中寻找有用的模式。这些模式类 型一般可以分为两类：描述和预测。描述性挖掘任务刻划数据库中数据的一 般特征；预测性挖掘任务则是在当前数据上进行推断，以进行预测。在知识发 现系统中，按照模式的实际作用，我们可以将k d d 任务和所能发现的模式类 6 型分为以下几类： 概念或类描述。概念描述就是对某对象类的内涵进行概括或描述，指出其 特征。概念描述分为数据区分性描述和数据特征化描述，区分性描述是指将目 标类对象的一般特征与一个或多个对比类对象的一般特征进行比较描述不同类 对象之间的区别。而后者是通过归纳目标数据的一般特征而描述同类对象间的 共同点。 分类。分类是找出描述并区分数据类或概念的模型，以便能够使用模型预测 类标记未知的对象类。分类规则挖掘过程通常分为二个步骤：第一步，通过对 训练数据集的分析形成学习模型；第二步是首先使用测试数据评估分类规则的 准确率，若模型被认为是可接受的，则可以进而利用模型对新的类标号未知的 数据集进行分类。 关联分析。关联分析是指发现大量数据集合中项集之间有趣的关联或相关关 系，展示属性值频繁地在给定数据集中一起出现的条件，通俗地说就是挖掘数 据库中一组对象之间某种关联关系的规则，这种关联关系可以是诸如“同时发 生”、“形如a j b 的蕴涵式”。由此可知，关联规则挖掘首先找出频繁项集， 然后由频繁项集产生关联规则。大量数据之间的关联规则在决策分析领域或商 业管理方面是有用的，然而并非所有的关联规则都是有趣的；并且一般认为关 联规则可以作为进一步探查的切入点，而不应当直接用于没有进一步分析或领 域知识的预测。 聚类。聚类分析问题的基本特征就是将具有相似属性的一些目标对象化归为 同一个集合；也就是说，在对数据集进行分析时，训练数据中对象的类标记未 知，我们可以通过聚类产生这种类标记。类标记的产生是根据“最大化类内对 象的相似性，最小化类间对象的相似性”的原则进行分组，形成对象的聚类。 这里所形成的对象聚类可以视为对象类，由此导出类规则。它又称为无指导的 分类，与分类不同的地方在于聚类规则挖掘是直接针对原始数据进行的，而分 类规则挖掘则是基于类标记已知的数据。 时间序列模式分析( 可与关联分析相合并，此模式主要是加入时间因素的前 后关联分析) 。时间序列模式根据对随时间变化的对象分析，建立模型描述对象 的变化规律和趋势，这类分析的重要特点是考虑时间因素。在一定程度上时间 序列模式分析与关联模式分析相类似，但时间序列模式侧重考虑数据之间在时 间影响下的关系。 孤立点分析。在大量的数据中可能包含这样一类数据，他们与其它绝大多 数数据的行为或特征不一致。这些数据对象称为孤立点，其行为可以称为有偏 差的行为。偏差分析主要就是寻找出原始数据中的这些孤立点、描述出其偏差 行为特征。然后进行分析，判断这些孤立点的产生是由于操作或误差所导致， 还是由于其它原因所导致。偏差分析有着广泛的应用，如用于欺诈监测，探测 不寻常的信用卡使用或电信服务；医疗分析中用于发现对多种治疗方式的不寻 常的反应。 尽管数据挖掘的任务可以按照挖掘模式类型主要分为如上几种类型，但是无 论何种类型的知识，其发现过程都是以用户需求为导向的。任何数据挖掘活动 都是为了寻找对用户而言是有趣的模式。除此之外，数据挖掘没有其它任何的 目的。 1 2 4 知识的度量、表示形式和可视化 在数据挖掘过程中，通过一定的挖掘算法挖掘产生大量的模式，但只有那 些对用户有用的模式才是最终令人感兴趣的、可以被称之为知识的模式。如何 设计恰当的模式价值度量准则和方式是数据挖掘研究中的重要课题之一。知识 的度量标准可以分为两大类，一类是客观标准；另一类是主观标准。客观标准 指的是度量方法能否准确反映数据中客观存在的规律、模式，如数据问存在的 关联、变化趋势等客观特征。而主观标准则指在用户参与挖掘过程时，能否适 时地将用户的主观选择有机地结合到挖掘过程中，使得挖掘出来的规则是具有 客观规律的模式和符合主观选择的那些模式的交集。前者的主要依据是模式的 形式和数据库中的数据，属于数据驱动；而后者由于要考虑用户的参与等人为 因素的影响，属于用户驱动 9 】。对于一个具体的知识度量方法，如果其在客观 上具有有效性、最终可理解性：而在主观上具有意外性、实用性，则认为该度 量方法是一个较好的度量方法。其中： 有效性指该度量方法对于在新的数据集上进行的挖掘过程也是适用的。即对 于不同的挖掘过程，只要挖掘出来的知识是相同的则都可以使用该度量方法。 最终可理解性一方面是指度量方法本身是用户可以理解的，从理论来说是 正确的；另一方面则是指通过使用该度量方法得到的规则，从理论角度分析是 正确的，从表现形式角度来说是足够简洁的，在用户可以接受理解的范围之内。 意外性通俗地解释是若所获得的模式能使用户感到出乎意料，则该模式可以 称之为具有意外特性的模式，进一步可以称为知识。 实用性。由于数据挖掘算法处理的数据规模较大，挖掘得到的知识规模较大， 从而往往会导致二次挖掘等问题的出现。所以一个好的知识度量方法，不仅能 够将用户感兴趣的知识筛选出来，更重要的是能够将用户“最”感兴趣的那一 更小规模的部分筛选出来，仅仅提交在实践行动中可以接受的最实用的那部分 知识给用户。 在数据挖掘研究过程中，不仅最终挖掘出来的知识的类型是多种多样的， 其表现形式也是各不相同的。知识的表现形式包括自然语言描述、形式化描述、 图形描述等方式。在过去的数据挖掘研究中，人们着重研究的是算法的效率和 应用等问题，而对于挖掘最终结果的表现形式考虑的则较少，以致在一定程度 上影响了挖掘过程的整体质量。如：在关联分析中用规则的形式表现数据之间 的关联关系，可能会由于关联规则的数量很多，影响了用户对规则的判断和使 用。如果考虑用其它的表现形式( 如集合方式、图形方式) 来代替规则表达方式， 则有可能在不减少知识数量的同时，达到提高知识可理解性和实用性。同时也 间接地提高了数据挖掘过程的质量。因此，知识的表现形式和数据挖掘系统的 可视化是作者以后将要研究的一个重要内容。 13k d d 的方法与工具 从目前数据挖掘的研究现状来看，数据挖掘采用的方法主要是发现驱动的 方法。这类方法在不带有任何先验假设的前提下，通过一定的工具和手段从数 据中自动地提取信息。这些工具和手段主要包括： ( 一) 粗糙集合( r o u g hs e t s ) 理论。粗集理论是由波兰华沙理工大学的p a w l a k z 教授于1 9 8 2 年提出的一种研究不确定性问题的理论方法，是一种重要的知识 发现方法。它的主要优势之一是它不需要任何预备的或额外的有关数据的先验 信息，它根据问题的描述对论域进行划分，通过引入不可分辩关系定义了上、 下近似等概念。粗集理论可以用于分类，发现不确定数据或噪声数据中内在的 联系。 ( 二) 概念格模型 1 0 , t i i 。w i l l er 于1 9 8 2 年提出的形式概念分析是一种支持 数据分析的有效工具，广泛应用于软件工程、机器学习等领域。概念格作为形 式概念分析中核心的数据结构，本质上描述了对象和属性之间的联系，表明了 概念问的泛化与例化关系，其相应的h a s s e 图则实现了对数据的可视化。概念 格模型可以用于多种类型的规则提取问题研究。 ( 三) 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ) 。神经网络是一种人脑仿真的 数据分析模式，用输入变量与数值来自我学习，并根据学习经验所得之知识不 断调整参数，以期得到数据的较好的表示模式。 图卜2 小波变换实现数据挖掘结构图 ( 四) 小波理论1 “。由于小波变换具有数学显微镜的特点和带有滤波的特性， 因而特别适合于非平稳信号的处理，将它应用于数据挖掘领域是十分有效的。 随着小波理论的不断完善，它必将与数据挖掘技术珠联璧合，天衣无缝。小波 理沦应用于数据挖掘领域的结构模型如图1 2 所示。 1 4k d d 的面临的挑战及研究热点 知识发现是当前涉及人工智能、数据库理论与技术、统计学以及电子商务 等学科的一个非常活跃的研究与应用领域。鉴于数据、数据挖掘任务和数据挖 掘方法的多样性，数据挖掘面临着许多挑战。如：更大规模数据库上的知识发 现问题；知识的评价和模式理解；挖掘过程中用户的交互等问题。 目前，数据挖掘的研究热点主要有数据挖掘语言的设计，高效而实用的数 据挖掘方法和系统的开发，以及应用数据挖掘技术解决实际应用问题等。 15k d d 的应用和发展趋势 数据挖掘可以应用在包括商务、金融、通讯、制造业在内的许多领域。如 在零售业领域，通过分析销售资料挖掘顾客的消费习性，由交易记录找出顾客 偏好的商品组合，或是找出流失顾客的特征以及推出新产品的时机等。在制造 业领域，可以将数据挖掘应用于产品质量控制方面，找出影响产品质量最大的 因素以改进生产过程。 目前数据挖掘的研究重点已经从提出概念和发现方法，转向数据挖掘方法 创新和在特定领域的应用上，研究过程也更加注重多学科之间的相互渗透。因 此未来数据挖掘的研究趋势将表现在如下几个方面 1 ： 应用的探索。早期的数据挖掘应用主要集中在帮助企业提升竞争能力。随 着数据挖掘研究的不断深入，数据挖掘技术也日益探索其他应用范围，如生物 医学、金融分析和电信领域。此外随着电子商务和电子市场逐渐成为零售业的 主流因素，数据挖掘也不断扩展其在商业领域的应用面。通用数据挖掘系统在 处理特定应用问题时有其局限性，因此目前的一种趋势是开发针对特定应用领 域的数据挖掘系统。 可视化数据挖掘。可视化挖掘是从大量数据中发现知识的有效途径。研究 和开发可视化数据挖掘系统将有助于推进数据挖掘成为数据分析的基本工具。 数据挖掘中的隐私保护和信息安全。随着数据挖掘工具和电信与计算机网 络的同益普及，数据挖掘要面对的一个重要问题是隐私保护和信息安全。需要 进一步开发有关方法，以便在适当的信息访问和挖掘过程中确保隐私保护与信 息安全。 1 6 本文的主要内容与结构安排 本文的研究来源于安徽省自然科学基金课题( 项目编号0 5 0 4 2 0 2 0 7 ) 一一“基 于概念格的分布式知识发现的关键问题研究”和合肥工业大学科研发展基金课 题( 项目编号0 5 0 5 0 4 f ) 一“基于概念格的半结构化数据中知识发现的关键 问题研究”。 本文论述了基于概念格模型的分布式关联规则挖掘问题。 第二章将简要介绍概念格的一些基本理论。 第三章介绍了关联规则挖掘的基本概念与理论，并着重研究了大规模数据库 中关联规则的度量问题。 第四章研究了基于多剪枝格上的关联规则提取问题，着重研究了多剪枝格上 频繁项集和关联规则的表示与挖掘。并给出了多剪枝格上规则提取的算法、实 验结果及分析。 第五章简要介绍了e c l k d d 原型系统的重要组成部分，关联规则挖掘a r m 子系统。 最后对本文所做的研究工作进行总结，并展望了下一步的研究方向。 第二章概念格与扩展概念格 概念格 1 0 , 13 , 14 是反映对象与属性问联系及泛化与例化关系的一种完备的概 念层次结构。由信息系统可建立相应的概念结构描述。在从大规模数据库中获 取知识的学习过程中，建造和运用概念层次结构具有许多优点 1 5 , 1 6 , 17 1 。在概念 层次结构上容易建立数据之间的依赖或因果关系的模型，对于全域中对象间关 系具有清晰、简明的描述。概念层次结构并非仅限于一般的树形结构，w i l l e r 等提出了根据二元关系来建造相应概念格或称为g a l o i s 格的基本思想【10 ，“j ，这 种特殊形式的格结构及相应的h a s s e 图就反映了一种概念层次结构，从本质上 描述了对象与属性之间的联系，表明了概念泛化与例化之间的关系。实践证明， 由一二维关系生成的概念格是一种非常有用的结构，这种格结构最终形成一个 概念的等级层次结构，在信息管理与知识发现等领域，已经显示出一定的应用 价值。 本章概述了形式概念分析的基本理论及其应用，介绍了现有的概念格构造 算法及格上的规则提取方法。 2 1 关系代数中的相关理论 格论”形成于1 9 3 5 年左右，是代数学的一个重要分支，而且在近世解析几 何、半序空间等方面都有重要作用。 定义2 1 设a 是一个集合，r g a a ，若r 是自反的、反对称的和传递的， 则称r 是a 上的一个偏序关系。 定义2 2 设r 是a 上的一个偏序关系，集合a 是关于r 的偏序集，用序 偶 表示。 通常偏序关系r 用符号表示。如asb ，读为a 在b 前。 定义2 3 哈斯图( h a s s e 图) 。为直观形象起见，有限偏序集也可用图形表示， 这种图形又称为哈斯图。 哈斯图的画法如下。设有偏序集( a ，) ，则其中： a 中的每个元素用小圆圈或元素字符本身表示； 自反性不在图上表示出来； 对x a 、y a ，如果ysx ，且不存在z a ，使得ysz ，z x ，则x 和 y 用一条直线连接，x 在y 上方； 所有的直线不画箭头。 例2 1 设集合a = 1 ，2 ，3 ，4 ，6 ，9 ，1 2 ，18 ，3 6 ，并设s 为整除关系， 则偏序集( a ，) 的哈斯图为： 图2 一l 例2 1 的哈斯图 定义2 4 最大下界和最小上界。设有偏序集( a ，! ) ，x 、y 是a 中任意两 个元素。对元素a e a ，如果a 三x 且asy ，而且对任何a e a 有a sx 且a 兰y 推出a ! a ，则称a 是x 和y 的最大下界；对元素b 如果x b 且y 茎b ，而且对 任何b e a 有xsb 且ysb 推出bsb ，则称b 是x 和y 的最小上界。 例2 2 在例2 1 中元素6 和9 的最大下界为3 ，最小上界为1 8 。 定义2 5 设有偏序集( a ，冬) ，若a 中任意两个元素都有最小上界和最大下 界，则称偏序集( a ，s ) 为格。 例2 3 设p ( s ) 是给定集合s 的幂集，( p ( s ) ，) 是一个偏序集。由于p ( s ) 中的任意两个元素s l ，s 2 ，它们的最大下界为s lns 2