（计算机应用技术专业论文）基于量化规则格的关联规则挖掘及其分布处理研究.pdf

蔡俊杰：基于量化规则格的关联规则挖掘及其分布式处理研究 i 摘要 形式概念分析自1 9 8 2 年由德国的晰u c 教授提出以后，近年来被广泛用于软 件工程、知识发现、信息检索等领域。概念格是形式概念分析中的核心数据结构， 通过h a s s e 图来表现出概念之间的层次关系。基于概念格直接产生关联规则的时空 复杂度非常高，从概念格中提取关联规则的一般过程是分两步进行，先构造概念 格，然后扫描概念格来挖掘关联规则，计算过程的瓶颈在于概念格的规模随形式背 景扩大呈指数级增长，提取规则的效率比较低下。本文主要围绕量化规则格和关联 规则的优化提取做了相关研究，提出两种规则挖掘算法，简化规则挖掘步骤，并且 实现了最小无冗余关联规则的分布获取。主要研究工作包括： ( 1 ) 提出了量化规则格，一种基于概念格的扩展模型。在渐增构格过程中能产 生每个概念所对应的最小项集集合( s l i t ) ，从s l i t 中可以直接推导出精确规则和 近似规则，无须重新扫描整个格结构，计算速度和复杂性优于基于普通概念格的规 则挖掘算法。 ( 2 ) 提出了一种基于量化规则格的规则渐增更新算法。对给定概念的s l i t ，可 以直接推导出精确规则，结合其对应的子概念s l i t ，可以推导出近似规则，从而 使整个规则挖掘过程整合在对概念的渐增更新中。 ( 3 ) 提出了一种基于量化规则格的关联规则分布获取算法。分布计算是提高性 能的有效方法，通过对规则挖掘过程的步骤分解，给出了关联规则分布式提取方 案，使最终的全局关联规则由部分关联规则合并计算产生。 ( 4 ) 扩展了p 2 p - m p i 平台。采用j a v a m p i 语言在深腾1 8 0 0 机群系统上实现了 本文算法，同时给出了相关分析。 关键字：形式概念分析，量化规则格，关联规则，分布处理，p 2 p m p i i i 扬州大学硕士学位论文 a b s t r a c t t h ef o r m a lc o n c e p ta n a l y s i sh a sb e e ng r e a t l ya p p l i e dt om a n yf i e l d s , s u c h 翘s o t t w a r e e n g i n e e r i n g , s c i e n t i f i cd i s c o v e r ya n di n f o r m a t i o nr e l r i e v a li nr e c e n ty e a r ss i n c ei tw a s p r e s e n t e db yp r o f e s s o rw i l l e c o n c e p tl a t t i c e , w h i c h 啪i l n c o v c rt h er e l a t i o n s h i pb e t w e e n c o n c e p t st h r o u g hi - i a s s ed i a g r a ma n de x l z a e tt h ea s s o c i a t i o nr u l e sd i r e c t l y , i st h ec o l eo f f o r m a lc o n c e p ta n a l y s i s d u et ot h et i m ea n ds p a c ec o m p l e x i t yo f m i n i n ga s s o c i a t i o nr u l e s f r o mc o n p tl a t t i e e , t l a i sp a p e ri sd e c r e a s i n gt h et i m eo f m i n i n gr u l e s t h eg e n e r a lm e t h o d i nt h ep r e c e d e n ts t u d i e sa sf o l l o w s , t h ef i r s ts t e pi st oc o n s i l l l c tc o n c e p tl a t t i c ea n da n o t h e r i st ow o r ko u ta s s o c i a t i o nr u l e sf r o mc o n c e p tl a t t i c e , b u tt h ec r i t i c a ls t e pi st h et h a ts c o p eo f c o n c e p tl a t t i c ei si n c r e a s i n gs h a r p l yb ye x p o n e n t , i na c c o r d a n c ew i t hf o r m a lc o n t 吼w h i c h c a nr e d u c et ot h el o we f f e c t i v e n e s so fc a l c u l a t i o n t h i sp a p e rp u tf o r w a r dan e wm e t h o d w h i c hc o u l di n t e g r a t et h ef o r m e rt w os t e p si n t oo l l es t e pa n di se a s i l yt ob ee x c c l l t , c d t h e m a i nb o d yo f t h i st h e s i si n c l u d e s ： ( 1 ) f i r s t l y , t h i sp a p e rp r e s e n t sq u a n t i t a t i v er u l el a t t i c e , 趾e x t e n d e dm o d a lb a s e d0 1 1 t h ec o n c e p tl a t t i c e t h ep r o c e s so fi n c r e m e n to fc o i k a l l c tl a t t i c ec o u l db r i n go u ts l i t s r e s p 洲v e l yw h i c h 黜d i r e c t l yc a l c u l a t et h ee x a c tr u l ea n da p p r o x i m a t er u l ew i t h o u t r e p e a t e d l ys e a m i n g t h ew h o l el a t t i c es u u c t u r ea n dt a k ea d v a n t a g e s0 1 1t h el l o t m a lm e t h o d i nt e r m so f t h ee a l c i i l a t i n gs p c e da n dc o m p l e x ( 2 ) s e c o n d l y , t h i sp a p e rp r e s e n t san e wa l g o r i t h mi nc a l c u l a t i n gl a t t i c ew h i c hc a n , d i r e c t l ya n dp r e c i s e l y c x l r a c tt h ee x a c tr u l e sa c c o r d i n gt ot h eg i v e ns l i ta n da l s o e x t r a c ta p p r o x i m a t er u l ea sw e l la c c o r d i n gt ot h es u b - c o n c e p to f s l i t ( 3 ) t h i r d l y , t h i sp a p e rp r e s e n t st h ea c c e s st oac a l c u l a t i o na l g o r i t h mb a s e d0 1 1t h e a p p r o x i m a t er u l eo fq u a n t i t yl a t t i c e t h ep a r a l l e lc a l c u l a t i o ni sa l le f f e c t i v ew a yt os p e e d u pt h ee f f e c t i v e n e s st h r o u g ha n a l y z i n gt h ec a l c u l a t i o ns t e p sa n dg r a d i n ga n a l y s i s , w h i e l a c o u l dm i xu pt h ep a r t i a la s s o c i a t i o nr u l e si n t ot h ew h o l ea s q o e i a t i o nr u l e su l t i m a t e l y ( 4 ) f i n a l l y ，t h i sp a p e re n l a r g e dt h ep l a t f o r mo fp 2 p - m p ia n da c h i e v e dt h el l e w a l g o r i t h m sb yu t i l i z i n gj a v a m p io ns h e n g t e n g1 8 0 0d u s t e rs y s t e m s o m es p e c i f i c a n a l y s i s e s 船a l s od i s c u s s e di n t h i sp a p e r k e y w o r d s ：f o r m a lc o n e e p ta n a l y s i s ，q u a n t i t a t i v er u l el a t t i c e ，a s s o c i a t i o n r u l e ，d i s t r i b u t e dp r o c e s s i n g ，p 2 p m p i 蔡俊杰：基于量化规则格的关联规则挖掘及其分布式处理研究 1 绪论 二十一世纪是一个高速发展的时代，是一个信息的时代。随着科学技术的发 展，各行各业都有了飞跃发展。与此同时，各个领域产生了大量的数据：人口数 据、财务数据、医疗数据、科学数据、银行交易数据等，我们正被这些数据所淹 没。如何从庞大的数据中过滤掉冗余的信息，如何对这些数据加以分析利用从而得 到有用的信息，人们正越来越深入的探索着这些问题。如今，随着计算机性能突飞 猛进的增长，从每秒几百次运算到每秒几万次运算，再发展到今天每秒有上万亿次 的运算，数据的高效处理变的越来越有可能。同时，数据库技术，人工智能，机器 学习等智能化研究领域都有了深入的研究，也为数据的分析提供强有力的解决方 案。但是，随着研究的深入，常规的技术分析已经越来越落后。人们不满足于数据 的表层信息，更倾于与挖掘数据背后隐藏的深层内容。于是，人们希望有一种新的 技术和工具来协助完成对大量原始数据的分析任务，进而获得人们所需要的有用知 识。这些技术和工具正是知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s ek d d ) t l - q 这一 新兴领域的研究主题。 本章简要介绍知识发现和数据挖掘的基本知识并回顾目前的研究现状以及概念 格在数据挖掘中的应用，确定课题的意义和主要研究内容。 1 1 知识发现和数据挖掘 简单来说，知识发现就是从大量数据中发现、提取有用的知识。数据库中知识 发现k d d 一词首次出现在1 9 8 9 年8 月在美国底特律市召开的第l l 届人工智能联合会 议上。数据中知识发现的概念是指从数据集中提取出隐含的、事先未知的、存在潜 在效用、并能被人理解的模式的一个非平凡的过程，简称知识发现或 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 ) 。该术语是指从数据库中寻找知识的全部过 程，而且强调特定数据挖掘方法的“高层”应用，许多人也把数据挖掘视为k d d 的另 一个常用术语，因为数据挖掘步骤是知识发现过程中非常重要的一个步骤，数据挖 掘这一术语应用于统计人员，数据分析员和m i s 领域，而大部分人工智能和机器学 习研究人员使用术语k d 矾 2扬州大学硕士学位论文 1 1 1k d d 的过程 k d d 的过程是交互的、重复的，包括大量由用户决利羽的阶段。b r a e h m a n 和 a n a n d ( 1 9 9 6 ) 给出了一个实际强调这一过程的交互式特性的k d d 过程观点嘲，各阶段 如下： i 确立目标：知识发现的目的是要在大量数据库中发现有用的令人感兴趣的 信息，因此发现何种知识成为整个过程中第一个也是最重要的阶段。这就 需要应用领域和相关先验知识的理解开发，从用户的观点认识k d d 过程的 目标。 2 数据选择：数据选择的目的是发现任务的操作对象，即选择数据集，建立 目标数据。 3 数据预处理：这一阶段的操作主要包括清除噪音，收集模型所需要的信息 或对噪音的解释，处理缺省数据域的决策策略，对时间序列和己知变化的 解释。 4 数据转换：依据k d d 的任务目标发现表示数据的有用特征。在特定条件 下，使用维数化简或转化方法减少变量的有效数量。 5 为i ( d d 过程的目标选择合适的数据挖掘任务，如概括、分类、回归、聚类 等等。 6 选择数据挖掘算法：选择数据中搜索模式的方法，包括确定哪些模式和参 数可能是合适的，为k d d 过程的最终目标选择相适应的数据挖掘算法。 7 数据挖掘：搜索以特定表示形式表示的感兴趣的模式或这样的一组表示 集；分类规则或树、回归、聚类等。用户可通过正确地执行前面各阶段的 工作有效地辅助数据挖掘算法。 8 解释发现的模式：可能要返回到前面( 1 ) 到( 7 ) 段的任意一个上面，以做进 一步的循环。这一步也可能包括提取模式或模型的可视化，或所提取模式 的数据的可视化。 9 合并发现的知识：将这些知识合并到另一个系统中，以便进一步的工作， 或简单地将其文档化，呈报给感兴趣的部门，这也包括检查、求解与原有 知识可能的冲突。 蔡俊杰：基于量化规则格的关联规则挖掘及其分布式处理研究 3 模式解释 知识评价、 图1 1k d d 过程图示 k d d 过程各阶段的基本流程如图1 1 所示，以往大多数k d d 的工作都集中在第 七阶段，即数据挖掘阶段，然而，其他各阶段对实践中l ( d d 的成功应用具有同样的 重要性。 1 1 2 数据挖掘的概念、功能和方法 数据挖掘是k d d 过程中的一个核心步骤，是从数据中提取模式的特定算法应 用。数据挖掘的历史虽然比较短，但从2 0 世纪9 0 年代以来，它的发展速度很快，加 上它是多学科的产物，目前还没有一个完整的定义，人们提出了多种数据挖掘的定 义，例如有如下几种定义： 1 在大量相关数据基础之上进行数据探索和建立相关模型的先进方法。 2 使用模式识别技术、统计和数学技术，在大量的数据中发现有意义的新关 系、模式和趋势的过程。 3 数据挖掘就是在大型数据库中寻找有意义、有价值信息的过程。 一般认为：数据挖掘就是从海量的数据中挖掘出有潜在价值的信息的技术，这 些信息是可以为企业带来利益或者为科学研究寻找突破口。数据挖掘的目的是从数 据中找出有意义的模式。模式可以是一组规则、聚类、决策树、依赖网络或其他方 式表示的知识。而在描述性领域的后期，数据挖掘的目标是利用大型数据集中在未 口觚 4扬州大学硕士学位论文 知模式和关系获得对所分析系统的理解。对特定数据挖掘的应用，预测和描述的相 对意义有相当大的变化，预测和描述的目标都是通过数据挖掘技术来实现的。数据 挖掘的当前功能如下： 1 分类：按照分析对象的属性、特征，建立不同的组类来描述事务。例如： 银行部门根据以前的数据将客户分成不同的类别，现在就可以根据这些类 别来区分新申请贷款的客户，以采取相应的贷款方案。 2 聚类：识别分析内在的规则，按照这些规则把对象分成若干类。例如：将 贷款申请人分为高度风险申请者，中度风险申请者，低度风险申请者。 3 关联规则和序列模式的发现：关联是某种事物发生时其他事物会发生的一 种联系。例如：每天购买啤酒的人也有可能购买香烟，相互之间比重有多 大，可以通过关联的支持度和可信度来描述。与关联不同，序列是一种纵 向的联系。例如：今天银行调整利率，明天股市的变化。 4 预测：把握分析对象发展的规律，对未来的趋势做出预见。例如：对未来 经济发展的判断。 5 偏差的检测：对分析对象的少数的、极端的特例的描述，揭示内在的原 因。例如：在银行的1 0 0 万笔交易中有5 0 0 例的欺诈行为，银行为了稳健经 营，就要发现这5 0 0 例的内在因素，减小以后经营的风险。 基于数据挖掘的上述功能划分，在k d d 的研究中出现了各种各样的不同数据挖 掘方法，总体上可以分为如下几类： ( 一) 统计模式识别方法【1 0 】 统计模式识别方法指运用数理统计方法，在样本空间中抽取出模式。 1 几何分类：利用样本空间的几何分布状况，找到类与类之间的分割曲面， 在此基础上进行分类或聚类。其优点是不依赖于条件分布密度。 2 概率分类法：利用贝叶斯法则从样本数据中获得各个模式的后验概率，应 用后验概率和风险函数求出具有最小风险的贝叶斯模式分类器，其缺点是 分类器的性能受主观知识的影响比较大。 3 动态聚类方法：聚类分析是在训练集中无指导信号情况下根据样本数据自 身特点的分布特征来进行分类。 4 贝叶斯网：是一种描述对象之间的概率关系的有向非循环图模型，在数据 挖掘中主要用于发现对象间的因果关系。网中每个结点表示变量或状态， 蔡俊杰：基于量化规则格的关联规则挖掘及其分布式处理研究 5 有向弧表示节点间的依赖关系。 ( 二) 面向符号的机器学习方法 机器学习方法是采用人工智能技术来实现机器从客观世界中的学习。归纳学习 是机器学习中最核心，最成熟的分支，旨在从大量的经验数据中归纳抽取一般的判 定规则和模式。归纳学习可以发现分类聚类，归纳描述等模式。归纳学习又可以分 为有导师学习和无导师学习。有导师学习是事先有外部导师将训练例子分类，然后 对这些带有导师信号的训练例子进行学习，依据其策略可分为以a q 为代表的覆盖 算法和以i d 3 1 1 l 为代表的分治算法；无导师学习事先训练例子的分类并不知道，算 法通过学习能够对它进行聚类。 ( 三) 神经网络方法 人工神经网络是一种典型的面向连接的学习技术。常用的人工神经网络有多种 模型，就k d d 而言有b p 网【1 2 1 和k o h o n e n 网【1 3 1 应用最为广泛。b p 网是由r 呦e l h a r t 等人 在1 9 8 5 年提出，b p 网采用多层前向的拓扑形状，由输入层，中间层和输出层组成。 b p 网的学习策略为有导师学习，其学习过程有两部分组成：训练数据的正向传播和 误差信号的反向传播，并且此过程不断迭代，使的信号误差达到允许的范围之内。 k o h o n e n 网络是由一个全互连的神经元阵列形成的无导师自组织和自学习网络，采 用前向拓扑结构，其结构为两层神经单元：输入层和竞争输出层，且两层间全互 连，其基本思想是通过调整从输入结点到竞争层上结点的连接权值，建立向量量化 器。k o h o n e n 网是一种逐步形成特征映射的算法。 ( 四) 粗集理论和方法【1 4 j 粗集理论和方法在k d d 中的应用主要表现在知识约筒、属性相关分析、规则 学习和决策表推导等。粗糙集理论的特点是不需要预先给定某些特征或属性的数量 描述，无需事先提供领域知识，而是直接从给定问题的描述集合出发，采用严格的 数学手段和方法处理含有不确定性因素的数据。通过不可区分关系和不可区分族集 确定给定问题的近似空间，从而找出该问题中的内在规律。 ( 五) 数据库技术 数据库技术是近年来发展比较成熟的领域，其中o l a p 1 习和数据仓库与k d d 关 系密切。数据仓库是一种为了实现决策支持的数据模型，存储决策所需信息的语义 一致的数据存储机制：数据仓库为数据挖掘提供了良好的基础和平台。数据仓库的 主要功能是o l a p 。o l a p 与k d d 相比更多地依赖于用户地问题和指导，并且它往 6扬州大学硕士学位论文 往只用于对数据的总体描述。面向属性的归纳( a o c ) f 1 6 j 由韩家炜提出，该方法采 用概念树爬升技术来实现从关系表中归纳出高层次的总结性规则。 ( 六) 形式概念分析技术f 1 7 】 形式概念分析o r m a lc o n c e p ta n a l y s i s ，f c a ) 大约诞生于二十世纪八十年代， 其首先描述是在1 9 8 1 年关于有序集合的b a n f f 会议的专题演讲上【l 刃。此后，数以 百计的相关论文开始出版和发表，甚至包括一篇研究格理论的数学基础的书籍。当 时，位于德国的d a r m s t a d t 研究小组开始系统地研究和开发一种基于格理论的应用 软件，该小组一直从事多达上百个基于格理论的应用软件研究，此研究小组先前的 部分成员已经建立了一个小的原型系统，并进一步使其逐步实用化。 f c a 是一种对数据进行分析的工具或者方法，特别是可以对给定的信息进行调 查和处理。而数据应该是从人类有意义的可以理解的思维单位概念中抽取而形成 的形式化的单元，形式化表明的是所处理的数据是形式化的数学实体，不必和人类 思维中的概念完全相同，它同时也指出形式概念分析处理的基本数据形式是形式背 景，形式背景是人类背景知识中的- d , 部分。形式概念分析以序论( o r d e r t h e o r y ) 尤 其是以完全格理论( t h et h e o r yo fc o m p l e t e 哳l i c e ) 【2 0 l 为基础，具有严密的数学基 础。f c a 根据哲学中的“概念”论述，通过对概念的外延和内涵进行抽象，形式化地 描述概念，对概念及其相互关联进行严格的分类和界定，进而表达“知识，支持相 关领域的研究和应用。 自8 0 年代f c a 提出至今，f c a 已经广泛地应用于心理学、精神病学、生物和社 会科学、市政工程、医学和计算机科学等各个领域的研究。作为一种数学理论， f c a 成为许多前沿科学的研究热点，人们希望通过对它的深入探索来发现解决问题 的新途径，而数据挖掘则成为f c a 应用的主要阵地之一。f c a 为数据挖掘的研究提 供了一个楣当的框架，由f c a ：支撑的许多数据挖掘方法已经被发布并且数量还在增 多。 数据挖掘是数据库技术的自然延伸和发展，它建立在已有的数据库技术基础 上。而通常采用的方法可以分为两大类：一类是统计学方法，常用的技术有概率分 析、相关性分析、聚类分析和判别分析；另一类是人工智能中机器学习方法，常用 的有判定树、神经网络等。基于概念格的形式概念分析的理论研究和应用今年来开 始受到重视。目前，基于概念格的知识发现研究主要集中在：用概念格改进k d d 过 程，加速构造概念格的建格算法、概念格的修正与扩展技术的研究等。概念格还被 蔡俊杰：基于量化规则格的关联规则挖掘及其分布式处理研究 7 证明是分析复杂数据的有效工具。此外，信息科学中的许多成熟方法也被应用到数 据挖掘中，比如粗糙集和模糊集方法可用于分类，还有基于网格的各种聚类算法挖 掘等等。数据挖掘使用了统计学、机器学习和信息学的若干概念，比如支持度、置 信度和信息熵等。可视化技术应用在数据挖掘中，可以直观地表示数据，使人们能 够快速地指导挖掘过程，理解挖掘结果。依赖于所挖掘的数据类型或给定的数据挖 掘应用。数据挖掘系统也可能集成空间数据分析、信息检索、模式识别、图像分 析、信号处理、计算机图形学、w e b 技术、经济、商业、生物、信息学或心理学领 域的技术。 1 1 3 概念格在数据挖掘中的应用 关联规则能有效描述数据之间的内在联系，是知识表示的有效形式，也是数据 挖掘研究的核心内容之一。形式概念分析以概念格为有力工具，将数据之间的关系 通过格节点的特化和例化关系体现出来，并且在概念之间满足数学上的完备性。所 以概念格非常适合作为规则发现的基础性数据结构用来发现规则型的知识。 目前，概念格已经被广泛应用于数据挖掘中关联规则的提取，取得的成果已经 很多，国内外学者基于概念格提取关联规则方面都有深入的研究。g o d i n r 等【2 l l 提 出了基于概念格模型提取蕴涵规则的方法。他们首先由形式背景构造概念格，再从 格中产生连接规则，最后再去掉冗余的蕴涵规则。他把蕴涵规则分为连接蕴涵规则 ( c o n j u n c t i o ni m p l i c a t i o nr u l e s ) 和分离蕴涵规则( d i s j u n c t i v ei m p l i c a t i o nr u l e s ) ，并给 出了蕴涵规则的确定算法。但蕴涵规则属于确定性的规则( 精确规则) ，不具备描述 概率规则( 近似规则) 的能力。m i s s a o u i r 等 2 2 1 对 2 1 进行了扩展，提出了从概念格 中提取近似规则的算法。在国内，王志海等在文瞄l 中提出了概念格中提取规则的 一般算法和渐进式算法。他们把概念格中的节点根据其双亲节点个数的不同，分为 只有一个双亲节点、两个双亲节点和d 个双亲节点的情况，分别给出了其中规则的 提取原则。胡可云等唧】提出了概念格节点中对象用对象的势来代替，并用概念格 来渐进产生最大项集集合，再提取规则的算法。赵奕等【2 5 】针对 2 4 中的一些不 足，提出了一种改进的递增修正规则挖掘的算法，以适应实际数据不断递增或递减 更新时的要求，并记录概念格节点在数据中出现的频率值，在无需构造全格的情况 下提取规则。谢志鹏等阴提出了利用内涵缩减来提取关联规则，试图减少提取规 则的数目。 8扬州大学硕士学位论文 由于提取出的规则很多具有依赖关系，也就是说在提取的规则中许多是冗余 的，虽然可以再进行冗余规则的去除，但毕竟耗费时间和空间。因此，人们又开始 研究提取无冗余规则的问题。y b a s t i d e 等【2 7 】提出了一种最小无冗余关联规则的定 义，并提出了基于a p r i o r i 算法 2 s 2 9 1 的改进算法，通过提取频繁封闭项集来获取最 小无冗余关联规则的算法；n p a s q u i c r 等即魄出了由封闭项集构成格，再提取关联 规则的思想，p e t k ov a l t c h e v 等 3 t , 3 2 1 提出了利用概念格获取频繁封闭项集的算法框 架和相应的算法；针对y b a s t i d e 等定义的最小无冗余关联规则，文章【3 3 】通过改变 格的结构，形成所谓的量化封闭项集格，并提出采用多种方法直接从量化封闭项集 格中求取最小封闭项集，以达到提取这种规则的目的。 1 2 论文的主要研究内容 i 2 1 论文研究目的及创新点 国内外基于概念格模型的知识发现研究己成为k d d 研究中的重要课题。国外 已经提出了多种概念格的快速构造算法，研究了基于概念格模型的知识表示、规则 发现，并将概念格模型成功应用到软件工程、数据挖掘、信息检索等各个领域。目 前，在形式概念分析中，虽然围绕概念格进行的理论和应用研究已经很广泛。但一 些瓶颈问题也变的越来越明显。在2 0 0 6 g f c a 国际会议中提出的1 3 个未解问题中， 如何在大数据集上进行形式概念分析的问题已经被明确化，即在有限的时间内如何 处理1 0 0 0 0 行1 0 0 0 0 列的形式背景，并能有效提取出满足用户需求的关联规则。本文 围绕这个问题，开展了基于概念格上关联规则挖掘的一些研究，对构格算法进行一 些扩展和补充，首次提出了基于量化规则格的关联规则的分布式挖掘算法，并采用 p 2 p m i 技术，用j a v a m p 瞎言验证了本文提出的算法。 本文的创新点如下： i 提出了量化规则格理论。扩展了概念格模型，以便高效提取关联规则。 2 提出了基于量化规则格的关联规则渐增更新算法。优化规则挖掘过程，减 少概念格扫描时间。 3 提出了基于量化规则格的关联规则分布式挖掘算法。该算法在基于g o d i n 算法的规则提取上提高了计算效率。 4 扩展了p 2 p - m p i 系统，使用j a v a m p i 并行语言实现本文算法。 蔡俊杰：基于量化规则格的关联规则挖掘及其分布式处理研究 9 1 2 2 论文的内容组织 第一章绪论简要介绍知识发现的历史背景、知识发现中的理论方法和技术问 题，详细阐述了知识发现的过程，并且对知识发现中的核心技术数据挖掘以及数据 挖掘的总体结构、一般方法给出了基本介绍并阐述了概念格在数据挖掘中的作用， 结尾说明了本文研究的目的、创新点以及论文的组织结构。 第二章对概念格的数学理论做一些阐述，从数学角度分析了一些概念格的特 性，同时给出构造概念的数学方法。提出了量化规则格( 一种基于概念格的扩展模 型) 。在渐增构格过程中产生每个概念所对应的最小项集集合( s l i t ) ，从s l i t 中可 以直接推导出精确规则和近似规则，无须重新扫描整个格结构，计算速度和复杂性 优于普通概念格规则挖掘算法。 第三章提出了一种基于量化规则格的规则渐增更新算法，对给定概念的s l i t ， 可以直接提取出最小无冗余精确规则，结合其对应的子概念s l i t ，可以提取出最小 无冗余近似规则，从而使规则挖掘过程整合在概念的渐增更新中。 第四章分析了基于量化规则格挖掘最小无冗余关联规则的效率问题，提出采用 分布式算法来加速规则提取，全局关联规则由部分关联规则合并计算产生。并给出 相关算法实例和实验分析。 第五章介绍了本文所使用的技术平台p 2 p m p i ，其独特的平台架构和易用性为 高性能计算提供了技术支持，并在深腾1 8 0 0 集群系统上实现了本文的算法思想。 第六章结束语，总结了本文的主要内容，并给出了进一步的研究工作和展望。 1 0扬州大学硕士学位论文 2 概念格和量化规则格 概念格是形式概念分析中核心基础，由德国的l 乙w n l c 教授于1 9 8 2 年提出跚。 发展至今已经被应用于许多领域，如软件工程口5 蚓、r e b 挖掘 3 7 1 等。本章主要介绍 概念格的基本内容，涵盖概念格中的基本概念、数学理论。然后将详细介绍为便于 提取关联规则而提出的核心数据结构量化规则格及其构造技术。 2 1 概念格 概念是人类进行思维的最基本的单位，是用来组织成为诸如判断、结论等更为 复杂思想的基础，是人类进行知识表述的一种有效手段，是一个哲学的范畴。对概 念的这种理解源于古希腊哲学，发展于十七世纪的近代学院派，进一步发展成德国 标准，最终成为了世界标准。由于概念是思维的基本单位，因此我们不难理解为何 概念会成为人工智能的一个重要组成部分。在知识表示、知识管理、机器学习、专 家系统等不同的领域，研究者们从不同的角度和观点来分析概念，形成了对概念的 不同形式化描述方法。 2 1 1 概念格的基本概念 f c a 的数学基础是由b i 瑚1 0 俨川提出的，b i r l 血 团鲷明了格结构和偏序间的相互 对应关系。他指出一个格可以根据对象集和属性集间的每一个二元关系来构建，通 过所得到的格可以洞察原始数据关系的结构。下面简单介绍下相关数学基础。 定义2 1 集合x 上的关系r 如果是自反的、非对称的、传递的，则称r 在x 上是偏序 的或称r 是集合x 上的偏序关系，而称集合x 为r 的偏序集。一般，我们用符号“s ”表 示偏序，而序偶“( 4 s ) 表示偏序集。 定义2 2 设集合x 上有一个偏序关系“s ”且设y 是x 的一个子集，如果存在一个元 素x x ，对每个y 】，均有y 】，则称x 是y 的上界，如果均有工s y ，则称x 是y 的下界。 定义2 3 设集合x 上有一个偏序关系“”且设y 是x 的一个子集，如果工x 是y 的 上界，且对每一个y 的上界a 均有x s 口，则称x 是y 的最小上界( 或称上确界 s u p r 瑚m u m ) ，记作s u p ( y ) ；如果工x 是y 的下界，且对每一个y 的下界b 均有 蔡俊杰：基于量化规则格的关联规则挖掘及其分布式处理研究 1 1 b x ，则称x 是y 的最大下界( 或成为下确界i n f t m u m ) ，记作i n f ( v ) 。 定义2 4 设集合x 上有一个偏序关系“”且设y 是x 的一个子集，如果x x 是y 的 上界，且对每一个y 的上界a 均有x a ，则称x 是y 的最小上界( 或称上确界 s u p r e m u m ) ，记作s u p ( v ) ；如果x x 是y 的下界，且对每一个y 的下界b 均有 b x ，则称x 是y 的最大下界( 或成为下确界i n a m u m ) ，记作i r l f m 。 定义2 5 格是一个偏序集，其中任意两个元素所构成的子集都有上确界和下确界。 记x ，y 的上确界为x v y = , u p ( i x ，j ， ) ，下确界为x a y = i n f ( x ，力。集合p 上的偏序关 系“”所构成的偏序集如它是格，可写成为( ，v ，a ) 。若p 中元素有限，则称p 为有 限格。 代数格中以偏序关系为基础，集合元素之间存在上确界和下确界所构成的代数 结果称为格，可以用h a s s e 图表示这种具有上、下确界的代数结构。 基于b i r k h o f f 对格理论的贡献，德国的1 l w i l i e 教授在1 9 8 2 年作为一种数学理论 首先引入了概念格( c o n c e p tl a t t i c e ) ，奠定了f c a 的理论基础，将哲学的概念进行数 学化的描述，实现了概念的一种形式化描述方法，1 l w i l i e 首先提出根据二元关系 系统来构造相应概念格( g a l o i s 格) 的思想，也称为形式概念分析，就是以格中的每 个节点表示一个形式概念，其中概念的外延代表相应的一组对象，内涵则为这组对 象所具有的公共特征( 属性) 印删。与概念格所对应的h a s s e 图则形象地揭示了概念 间的泛化和例化的关系，反映出一种概念层次结构( c o n c e p th i e r a c h y ) ，实现了对数 据的可视化【4 1 4 2 】，非常适用于从数据库中进行知识发现的描述，从而成为数据分析 和规则提取的一种有效工具。 f c a 中的一种重要关系就是超概念和子概念关系，定义为一种自顶向下的推 进，即从具有较大外延、较小内涵的更为广泛的概念到具有较小外延、较大内涵的 相对例化的概念的次序。形式概念间通过这样的超概念和子概念关系相互关联构成 了一种层次结构。称为概念格。换句话说，概念格是所给定的形式上下文的全部形 式概念的有序集。概念格理论是f c a 理论的核心数据结构，被认为是知识发现和数 据分析的有力数学工具。 在形式概念分析中，数据集是以形式背景( c o n t e x t ) 的形式给出的，有关概念 格的详细描述参见文献1 4 3 , 4 4 ，本节简要介绍一些基本概念。 已知形式背景c ；( o ，d ，r ) ，其中o 是对象集合，d 是属性集合，r 是o 和d 之间的 一个二元关系，则存在唯一的偏序关系与之对应，并且每个偏序关系产生一个格结 1 2扬州大学硕士学位论文 构，这种由c 所诱导的格就称为概念格或c r a l o i s 格，简记为g a l o i sc o n c e p t l a t t i c e ( g c l ) 。 定义2 6o c l 中的每个结点( a ，b ) 是一个二元组( 称为概念) ，其中 a p ( o ) b d d ) ，p ( o ) 和p ) 分别表示对象和属性的幂集，a 和b 按如下运算关系 建立连接： 爿= 切烈然小，v g e a ( 2 - 1 ) b = 括d 职m ，锄b ( 2 2 ) 并且a = b ，b f f i a ，a 和b 分别称为概念的外延( e x t e n s i o n ) 和内涵( i n t e n s i o n ) ， 分别用d c t e m ( c ) 和h e i n ( c ) 来表示。 设c l f f i ( a i ，b 1 ) 和c 2 = ( a 2 , b 2 ) 是格中的两个概念，其中偏序关系“”定义为 c t c 2 b 2s 蜀。此时称c i 是c 2 的子概念( s u b _ c o n c e p t ) ，c 2 是c l 的超概念 ( s u p e t _ c o n c e p t ) 。并且如果不存在概念c 书，b ) 使得a ic 4 c 以成立，定义 c l c 2 为直接子概念( i m m e d i a t e _ s u b c o n c e p t ) 或直接超概念 ( i m m 比a t e _ s u p e r c o n c e p t ) 。 每一概念b ) 描述了一组对象及其公共的特征。属性b b 称为该概念所支持 的属性，对象a 彳称为该概念所覆盖的对象。而且，每个概念 0 ，b ) ep ( d ) p ( d ) ( a b ) 对于关系r 是完备的，即概念必须是最大扩展的，这是概 念格的完备性。 概念格是一个完全概念格，因此对于概念格中的任意结点子集，都存在唯一的 最大下界和最小上界。给定概念格l 中的一个概念族c = “，b l x t e l ) 有最大下界 和最大上界，我们分别用 i n i ( c ) = ( 肚( 望马) ”) ( 2 - 3 ) 和 s u p ( c ) = ( ( 旦4 ) ”，o 马) ( 2 - 4 ) 来表示。 概念格中概念的外延集合a 和内涵集合b 之间存在对偶关系，给定c i - = ( a i , b 1 ) 和 c 2 f f i ( a 2 , b 2 ) 。则有c isc 2 铮易c 置；又b 2cb i a tc 以， 从而 q l 时，i t e m 仍为d i f f 加入后的最小项集。得 证。 s l i t 中所有保持不变的项形成不变最小项集集合，记为s l i tk e e p ：除不变 项集外的项集称为更新项集，记为s l i t _ u p d t 。 定理2 6 设节点c 对应的最小项集集合为s l i t ，与新增直接父节点d k tp a r e n t ( c ) 的 项集差d i f f o 对于任一项i t e m es l i t _ u p & ，如果i t e m a d i f f = 西，则对于每个元素 团、妇 群 蔡俊杰：基于量化规则格的关联规则挖掘及其分布式处理研究 1 9 e l e m d i 每i t e m n e w = i t e m u e l e m ，若在s l i tk e e p 中不存在i t e n m e w 的子集项，即 i t e m es l i t _ k e e p j | 满足i t e m c i t c m n e w ，贝l j l t e m n e w 为新增的最小项集。 例如，在图2 3 ( a ) 中，节点c 原具有两个直接父节点，其s l i t = a b ，a c ，现 新增一个直接父节点，其和节点c 的项集差为c d ，由于a cnc d = c 西，那么a c ： 是s l i t 中的不变最小项集。a bnc d = d ，那么将形成新项集i t e n m e w l = a bu g - - a b e 和i t e m n e w 2 = a b u d = a l x l ，但由于a c c a b c ，a cc z a b d ，所以i t g m a n c w 2 = a b d 为新增 的最小项集。这时节点c 的s l i t 就更新为 a c ，a b d 。 格中节点新增父节点( 增加节点连线) 的处理过程为： p r o c e d u r ea d dl i n e ( i c d ：子节点项集，i p t ：父节点项集，s l i t ：子节点对应的最小 项集集合) s l i tn e w = d s l i t _ k e e p = ，t d i f f = - i c d 、i p t f o rs l i t 中的每个项集i t e md o t e m p = i t e m n d i f f i f t e m p 矿t h e ns l i tk e e p 2 s l i tk c e p u i t e m ) e n d i f e n d f o r s l i t _ u l k i t = s l i t 、s l i t _ k e e p f o rs l i t 的每个项集ant i t e m ld o f o rd i f f 中的每个元素e l e md o i t e n m e w = i t e m lue l c m i fs l i t _ k e e p t 妒且s l i t _ k e e p 的每个项集i t e m 2 岱i t e m n e wt h e n s l i t _ n e w = s l i t _ n e w u i t e n m e w e 闻d b d 】排 日叮d f o r s l i t = s l i t _ n e w o s l i t _ k - p r e n 瓜ns l r r ( 二) 删除节点连线处理 设节点c 的项集为a b