（计算机软件与理论专业论文）基于形式概念集的分类规则挖掘算法研究.pdf

郑州大学硕士学位论文 摘要 目前，利用形式概念分析来进行数据挖掘的研究得到了相关学者的广 泛关注。他们提出了相应的概念格构造算法，并利用形式概念分析进行其 它方面的研究。在利用形式概念分析进行分类规则挖掘的时候，大多数方 法都是先生成形式背景对应的完备概念格，这些完备概念格的构造方法大 都基于经典的概念格构造算法，如增量式算法、批处理算法等。当完备概 念格构造完之后，再从这种偏序的结构中将那些适于作为分类规则的格节 点提取出来，进而得到整个形式背景的分类规则。 但是，由于构造完备概念格的复杂性及构造过程中产生的大量冗余， 这种方法往往具有较高的时间和空间复杂度，因而影响了效率。针对这些 问题，本文提出了一种f c c r m 算法，它采用类标号分割的方法来降低形式 背景的规模，通过对每一类标号的形式背景按照属性划分，生成单属性形 式概念，并由这些形式概念的最大概念以及它们的下覆盖来获取全部的格 节点，获得分类规则。该算法避免了构造完备概念格时格之间的复杂关系， 只生成全部的概念节点，并且在生成所有形式概念的同时进行预剪枝，缩 小了生成概念集的规模。 在分类器的构造上，本文将分类规则赋予权值，然后在分类器中采用 投票的方式对未分类数据进行分类，并根据规则加入对训练数据的判断结 果的反馈机制。这种方法强化了那些具有强分类能力的规则，提高了分类 的正确率。本文还对分布式数据挖掘在概念集成时采用的方法进行了研 究，并给出了一个模型。 最后，实现了本文中提出的算法，并通过实验进行验证。实验结果表 明：该算法在性能上有了很大改进，通过形式概念集获取的规则对于样本 集是完备的。实验还测试了数据集大小以及稠密程度对算法性能的影响。 关键词：数据挖掘，分类，形式概念分析，概念格，形式概念，元学习 郑州大学硕士学位论文 a b s t r a c t n o w a d a y s ，d a t am i n i n gw i t hf o r m a lc o n c e p ta n a l y s i sh a sb e e nd r a w na w i d e s p r e a d a t t e n t i o no fs c h o l a r s s o m eo ft h e m h a v ea l r e a d yr a i s e d c o r r e s p o n d i n ga l g o r i t h m sa n dh a v eb e e nu s i n gf o r m a lc o n c e p ta n a l y s i sf o r o t h e rr 鹤e a r c h m o s ta l g o r i t h m sf i r s t l yc r e a t ec o m p l e t ec o n c e p tl a t t i c er e l a t e d t ot h ef o r m a lc o n t e x tw h e nm i n i n gc l a s s i f ym l e s 丽t hf o r m a lc o n c e p ta n a l y s i s ， a n dm o s to ft h ec o n s t r u c t i o nm e t h o d sf o rc o m p l e t ec o n c e p tl a t t i c ea r eb a s e d o ns o m ec l a s s i c a lc o n c e p tl a t t i c ec o n s t r u c t i o na l g o r i t h m s ，s u c ha si n c r e m e n t a l a l g o r i t h m , p a t c ha l g o r i t h ma n ds oo n a f t e rt h ec o n s t r u c t i o no fc o m p l e t e c o n c e p tl a t t i c e ，i te x t r a c t st h el a t t i c en o d e sw h i c ha r ep r o p e rf o rc l a s s i f yr u l e s f r o mt h ep a r t i a lr e l a t i o n s h i ps t r u c t u r e ，t h e no b t a i nt h ec l a s s i f yr u l e so ft h e w h o l ef o r m a lc o n t e x t h o w e v e r ,a s t h ec o m p l e t ec o n c e p tl a t t i c ec o n s t r u c t i n gi sv e r y c o m p l i c a t e d , al a r g en u m b e ro fr e d u n d a n tw i l lb ep r o d u c e di nt h ep r o c e s so f c o m p l e t ec o n c e p tl a t t i c e sc o n s t r u c t i n g , t h e r e f o r e , t h i sm e t h o da l w a y sh a sa 1 l i g ht i m ec o m p l e x i t ya n ds p a c ec o m p l e x i t y , t h u si tw i l lr e d u c et h ee f f i c i e n c y ，n l ep a p e rg a v ea na l g o r i t h mn a m e df c c r r n i tr e d u c e st h es c a l eo ft h ef o r m a l c o n t e x tb yu s i n gc l a s sl a b e ld i v i d i n gm e t h o dw h i c hi sb a s e do nf o r m a lc o n c e p t , i no r d e rt oo b t a i nt h ec l a s s i f i c a t i o nr u l e so fs a m p l ed a t as e t b yc l a s s i f y i n gt h e e a c hl a b e l sc o n t e x ta c c o r d i n gt ot h e i ra t t r i b u t e s ，w ec r e a t es i n g l ea t t r i b u t e f o r m a lc o n c e p t s ，t h e no b t a i na l lt h el a t t i c e sn o d e sb yt h eb i g g e s tc o n c e p t so f t h e s es i n g l ea t t r i b u t ef o r m a lc o n c e p ta n dt h e i r s u c c e s s o r f i n a l l y t h e c l a s s i f i c a t i o nr u l e sw i l lb eo b t a i n e d t h ea l g o r i t h ma v o i d st h ec o m p l i c a t e d r e l a t i o n so fc o n c e p tl a t t i c e m e a n w h i l e , t h ep r e - p r u n i n gm e t h o du s e di nt h e a l g o r i t h mr e d u c e st h es i z eo ft h ef o r m a lc o n c e p t s i nt h ec o n s t r u c t i o no f c l a s s i f i e r , t h ec l a s s i f i c a t i o nr u l e si nt h i sa r t i c l ew i l l b eg i v e nt h ew e i g h tv a l u e t h e n , b yv o t i n gi nc l a s s i f i e r , i tw i l lc l a s s i f yt h e 郑州大学硕士学位论文 u n c l a s s i f i e dd a t a , a n da d dt h ef e e d b a c km e c h a n i s ma c c o r d i n gt ot h ej u d g e r e s u l t t h i sm e t h o dh a se n h a n c e dt h er u l e sw h i c hh a v es t r o n gc l a s s i f i c a t i o n a b i l i t y , a n di m p r o v e dt h ec l a s s i f i c a t i o nc o r r e c tr a t e t h ep a p e rg i v eam e t h o d u s e di nt h ec o u l e eo fc o n c e p ti n t e g r a t i n gi nd i s t r i b u t e dd a t am i n i n g , a n dg a v e as t u d ym o d e l f i n a l l y , t h ep a p e rr e a l i z e dt h ea l g o r i t h mp r o p o s e d ，a n dv e r i f i e di tb y e x p e r i m e n t s t h ee x p e r i m e n t a lr e s u l t ss h o wt h a t ：t h ep e r f o r m a n c , o ft h e a l g o r i t h mh a sb e e ng r e a t l yi m p r o v e d , a n dt h er u l e so b t a i n e df r o mf o r m a l c o n c e p t sa r ec o m p l e t ef o rs a m p l es e t s e x p e r i m e n t a la l s ot e s tt h ed a t as e ts i z e a n dt h ee f f e c to np e r f o r m a n c eb yd a t as e ts c a l ea n dd e n s i t y k e y w o r d s ：d a t am i n i n g , c l a s s i f i e r , f o r m a lc o n c e p ta n a l y s i s ，c o n c e p tl a t t i c e s ， f o r m a lc o n c e p t ，m e t a - l e a r n i n g 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均 已在文中以明确方式标明。本声明的法律责任由本人承担。 学位论文作者： 木历冉 日期：) 0 0 辟岁月27 日 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品，知识产权归属郑州大学 根据郑州大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部门 或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权郑州大学 可以将本学位论文的全部或部分编入有关数据库进行检索，可以采用影印、缩印 或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学位论文 或与该学位论文直接相关的学术论文或成果时，第一署名单位仍然为郑州大学。 保密论文在解密后应遵守此规定。 学位论文作者：乖勿冉日期：加矽年岁月2 9 日 郑州大学硕士学位论文 1 1 研究背景 第一章引言 近年来，随着信息技术的飞速发展，数据库技术得到了迅速的发展和广 泛的应用，社会生活的各个领域、各个行业几乎都在使用数据库产品。，7 数据 库的广泛使用直接导致了大量数据的产生，比如金融保险行业的大量数据、 网络中的w e b 数据、移动通信中的通话数据、零售贸易中的交易数据、医疗 数据、统计数据、天文数据、还有文本数据、多媒体数据等等，这些数据大 部分被有效地存储在数据仓库中，它们的规模往往非常惊人。要理解这些数 据已经超出了人的能力，而采用传统的数据分析工具来分析这些数据已经远 远不能满足人们的需要，因而造成了一种“数据丰富，但信息匮乏州的困境， 这些存储于数据仓库的海量数据也成为了“数据坟墓 。为了充分的利用这些 海量数据，并从中获取有用的信息，数据挖掘技术便应运而生。 数据挖掘( d a t am i n i n g ，d m ) ，就是从大量数据中获取有效的、新颖的、 潜在有用的、最终可理解的模式的非平凡过程，简单的说，数据挖掘就是从 大量数据中提取或“挖掘”知识n 1 。数据挖掘技术作为数据库技术的延伸和发 展，它属于交叉学科，涉及多个学科的知识，包括统计学、机器学习、高性 能计算、模式识别、神经网络、信息检索等等。数据挖掘的任务通常包括： 挖掘频繁模式和关联规则、分类和预测、聚类分析、离群点分析、以及文本 和w e b 数据等。 分类是数据挖掘中的一项重要任务，它是可以用于提取描述重要数据类 并预测未来的数据趋势的模型。分类问题在模式识别和机器学习的很多领域 都得到了广泛的研究，并且商业领域很多也应用了分类技术，比如信用卡的 欺诈检测嘲1 等。数据挖掘中的分类技术通常都要构造一个分类模型( 通常称 为分类器) 来预测未知类别数据的类标号，其中的分类器构造过程就是知识 获取的过程，它通常是有- d , 部分训练集通过训练得到的。数据挖掘中常用 的分类方法有：决策树分类( d e c i s i o nt r e ec l a s s i f i e r ) 、贝叶斯分类( b a y e s i a n c l a s s i f i e r ) 、神经网络分类( n e u r a ln e t w o r kc l a s s i f i e r ) 等。 郑州大学硕士学位论文 近些年来，形式概念分析( f o r m a lc o n c e p t m a l y s i s ，f c a ) 作为一种有 效的数学分析方法被广泛应用于数据挖掘领域，并成为学者研究的热点。形 式概念分析是德国的w i l l c 教授等人于1 9 8 2 年提出的乜，朝，并被广泛地应用于 不同的领域，比如：社会学、医学、计算机科学、数学、工业工程等。它是 以数学化的概念和概念层次为基础的应用数学方法，可以用于数据分析、知 识表示和信息管理等领域，目前已经在信息科学中取得了很多成功的应用。 作为形式概念分析的核心数据结构，概念格已经成为人们研究的热点。 1 2 研究现状 目前人们对数据挖掘的研究很多是集中在应用方面的，通常都是采用数据 挖掘中的一些方法来建立一个模型，然后通过这个模型来解决一些实际的问 题。比如，采用主成分分析建立一个d e m a c 模型来进行天文分类h 1 ，通过移动 a g e n t 技术搭建一个混合结构服务于电子商务环境嘲，基于多a g e n t 系统的交 互学习嗍，采用l m 、l i d s 及d l m 模型对连锁超市数据库进行关联规则挖掘口1 ， 利用a d a c o s t 算法在信用卡的冲突检测应用嘲，在p 2 p 网络上的挖掘睁1 等等。 分类规则的研究有一些集中在分类器的构造上面，比如基于遗传算法的机器 学习系统x c s n 们等。 形式概念分析的研究多集中在概念格的构造、优化及概念格的应用等方 面。在概念格的构造上，人们已经提出了很多种构造格的方法，根据构造方 法的不同可以将它们分为三大类：批处理算法、增量算法、并行算法。几乎 所有的算法都可以归入到这三大类中，目前提出的其它一些算法也主要是在 这些算法的基础上进行的改进和优化。对于特定的任务，学者们还提出了很 多简化概念格的方法来解决，比如，i c e b e r g 格m j 妇、p s e u d o 格n 羽等，这些格 都是完备概念格的一部分，而这一部分半格已足够解决特定问题。 从概念格的应用上来说，人们已经提出了很多利用概念格进行关联规则、 分类规则或者其它特征模式挖掘的算法。利用概念格来获取分类规则也是人 们研究的一个方向，目前也有很多采用概念格来进行分类规则挖掘的算法， 这些算法过程往往分为两个步骤：概念格的获取和分类规则的获取。在概念 格的获取步骤上往往都是对传统的算法进行一些局部修改，或者是生成 2 郑州大学硕士学位论文 p s e u d o 格、半格等，还有一些算法在概念格构造的过程中加入了一些其它的 方法，比如概念相似度等。这些算法的提出丰富了概念格的应用，体现了概 念格在模式提取方面的优势。 1 3 研究内容 在构造形式背景的概念格时，由于需要构造概念格中的所有概念节点，并 生成概念节点之间的偏序关系，而概念节点之间的关系又非常的错综复杂， 因此它是一个非常费时且非常复杂的过程，往往需要很大的时间和空间复杂 度。而对于概念格的应用来说，很多时候并不需要整个完备概念格，而只是 需要其中的某一部分或者某一方面，比如，在使用概念格进行频繁项集挖掘 的时候n4 旧，只需要其中那些具有频繁项的概念，那些非频繁的概念则可以在 构造的过程中通过剪枝去除。所以我们在利用概念格的时候可以只选择需要 的部分进行构造，避免冗余，以提高效率。 同时，在构造概念格的时候，形式背景的规模也会对构造效率产生影响， 许多学者采用降低形式背景规模的方法来降低概念格构造的复杂性也取得了 很好的效果n 阳。形式背景可以按照属性或者对象采用并置或者叠置的方法来 划分，不同的情况适用不同的划分方式，这一问题将在后文中详细说明。 对于由概念格获取分类规则这个问题，因为分类规则本身只和形式背景产 生的形式概念有关，概念之间的关系对分类规则不产生影响，所以我们可以 选择只构造形式背景的全部形式概念，也就是产生形式概念集，而无须再去 建立形式概念之间的序关系。而在形式概念集的构造过程中，本文从分治的 思想作为切入点，通过对形式背景按类标号进行分割，将形式背景划分为多 个小的子形式背景，降低它的规模。在形式概念集的构造中加入剪枝的思想， 对那些概念外延小于概念支持度的形式概念提前结束它的增长，一定程度上 提高了效率。 通过样本数据集获取的分类规则虽然可以进行预测，但是如果直接使用这 些规则来做预测是十分低效的，会产生很多的错误。目前，也有很多学者提 出了一些具有成长能力的分类器系统，比如l c s 系统n 刀等，它基于优胜劣汰 的思想，采用报酬回馈的方式来强化那些分类能力强的规则，淘汰那些不具 3 郑州大学硕士学位论文 有竞争力的规则，从而提高了分类器的性能。在数据挖掘中还常常采用加权 和投票的方法来提高挖掘结果的效率。本文从分类规则本身出发，综合以上 的几种方法，在通过样本数据集产生分类规则集之后，根据样本数据对这些 规则进行加权，并在做预测的时候采用投票的方式进行，并将最终结果反馈 给整个分类器系统，从而提高了效率和准确率。 由于数据量的日益增大，并且数据的存储出现了分布存储的特征，因此使 得分布式的数据挖掘成为了当前数据挖掘研究的重要研究课题。分布式数据 挖掘就是挖掘存储在各个分站点上的分布式数据中的频繁模式，并通过站点 之间的通信将各个分布式站点的挖掘结果集成在一起。它主要包括分站点挖 掘和模式集成这两个方面。分站点上的挖掘可以采用各种挖掘技术，而集成 的方式也很多，元学习n 胡的方法就是其中之一。本文将简要介绍利用形式概 念集在分站点上进行分类规则挖掘，并采用元学习的方法进行规则集成。 1 4 论文结构及主要内容 本文共分为六章，按照如下的方式组织内容： 第一章，引言。介绍了课题的研究背景、研究现状以及研究内容。 第二章，相关知识介绍。介绍了形式概念分析中的一些基本概念，以及常 用的概念格构造算法。 第三章，基于形式概念集的分类规则算法。介绍了一些由概念格获取分类 规则的方法，并详细介绍了采用形式概念集进行分类规则挖掘的算法，然后 给出了一个实例详细介绍了这一构造过程。 第四章，分类器构造研究。介绍了对构造出的分类规则做进一步的处理， 构造一个高效的分类器，然后介绍了分布式情况下采用元学习的方法来进行 知识综合的内容，给出了一个构造模型。 第五章，实验及分析。对本文中提出的一些算法和构造方法通过实验进行 了验证，并分析了实验数据及实验过程中产生的问题。 第六章，总结与展望。本章总结了全文的内容，提出了一些需要完善的问 题，并给出了下一步的工作方向。 4 郑州大学硕士学位论文 第二章相关知识介绍 “概念”的基本观点是由哲学理论中的概念发展而来的。人类在认知的 过程中，把所感觉的事物的共同特点抽象出来并加以概括，就称为概念。在 哲学中，概念被理解为由外延和内涵两个部分组成的思想单元。w i l l e 教授将 这一思想引入到数学理论中，提出了形式概念分析，( f o r m a lc o n c e p ta n a l y s i s ， f c a ) 。在f c a 中，概念的外延被理解为属于这个概念的所有对象的集合， 内涵则被理解为所有这些对象所共有的特征或者属性集。 2 1 形式概念分析的基本知识 人们对于自然界事物的描述通常是由两部分构成的，事物的名称和事物 所具有的属性。同样，数据库系统在对事物进行描述的时候，通常也是使用 这种方法。关系数据库是由大量的关系表来组成的，而每一个表都包含一组 属性，并存放有大量的元组，关系表中的每个元组表示一个对象。 为了使说明更具有一般性，我们选取一些实际的数据值作为例子。如表 2 - 1 所示，这是从u c i 数据集n 鲫b a l a n c e - s c a l e 中随机抽取的几个样本数据。 b a l a n c e s c a l e 数据集就可以称为是一个关系表。 表2 - 1 样本数据b a l a n c e s c a l e 示例 c nl wl dr wl 其中，表2 - 1 中的各个属性的值域如下：c n ( c l a s sn a m e ) = l ，b ，r ) ， l w ( l e f i - w e i g h t ) = 1 ，2 ，3 ，4 ，5 )，l d ( l e t t - d i s t a n c e = 1 , 2 ，3 ，4 ，5 ) ， 5 l 2 3 l l 2 5 2 5 2 3 l 2 l l b r r l i 2 3 4 5 6 郑州大学硕士学位论文 r w ( r i g h t - w e i g h t ) = 1 ，2 ，3 ，4 ，5 ) ，r d ( r i g h t - d i s t a n e e ) = 1 ，2 ，3 ，4 ，5 。每个属性的 含义分别是：所属的类名，左侧重量，左侧距离，右侧重量，右侧距离。这 些都是它们的自然属性。表中第一列表示的是元组的标号，每个元组代表一 条记录。 而在形式概念分析中，处理的对象通常是形式背景( f o r m a lc o n t e x t ) ， 形式背景与关系表的形式类似，但是它们所代表的含义不同。下面我们对形 式背景做详细的介绍，形式背景的定义如下：7 定义2 1 形式背景：一个形式背景是三元组k ( o ，a ，i ) ，其中o 为 对象集合，a 为属性集合，i 是o 与a 之间的一个二元关系。对于一个对象0 g o ，属性a a ，用o l a 或( o ，a ) i 表示对象o 具有属性a ；用( o ，a ) 正i 表示对象o 不具有属性a 。 我们知道，形式背景是一种二元关系，因此表2 1 中的样本数据所对应 的二元关系如表2 2 所示： 表2 - 2 表2 - 1 中数据集所对应的形式背景 表2 2 中的属性l 、b 和r 为数据集中c n 属性的各个值，其余属性项 类似，都是表2 - 1 中各个属性的值。表中值为“一表示该元组含有此属性。 对于一个形式背景k ( o ，a ，i ) ，我们定义如下的两个关于形式背景的 函数f ( x ) 、g ( y ) 。函数f ( x ) 和g ( y ) 表明，k 中的对象和属性之间具 有对应的关系。 定义2 2 口1 假设x 是对象o 的一个子集，y 是属性a 的一个子集，我 们定义两个函数： 6 郑州大学硕士学位论文 f ( x ) = a e a i v o e x ，o l a ，( x 中对象共同属性的集合) ； g ( y ) = o eo lva e y ，o l a ，( y 中属性共同对象的集合) 。 定义2 2 中的函数f ( x ) 表示：对对象集合x 做f 操作，它的结果 为这些对象x 具有的共同属性的集合。函数g ( y ) 表示：对属性集合y 做g 操作，它的结果为这些对象y 具有的共同对象的集合。这两个定义 在后面将会使用到。 2 2 概念格中的一些定义 在这一节中，我们给出一些概念格中的相关定义，这些是我们后面内容 的理论基础。 2 2 1 形式概念与概念格 概念格是f c a 中的核心数据结构，它是一种偏序结构。为了得到概念格 的定义，我们首先给出形式概念及概念格的定义： 定义2 3 封闭性：一个对象集x c _ o ，如果存在着x = g ( f ( x ) ) ，那么 称这个对象集x 是封闭的；同样，一个属性集y _ c a ，如果存在y - ( g ( y ) ) ， 那么称这个属性集y 是封闭的。 定义2 4 口1 形式概念：一个形式概念是一个二元组c ( x ，y ) ，其中x _ c o ，y - a ，而且满足f ( x ) - y ，g ( y ) x 。称x 是概念( x ，y ) 的外 延，y 是概念( x ，y ) 的内涵。 根据形式概念的定义，可以看出，概念c ( x ，y ) 中的概念外延x 和概 念内涵y 都是封闭的。 有了形式概念的定义，我们可以给出概念格的定义，如下所示： 定义2 5 口】概念格：对于形式背景k ( o ，a ，i ) 所产生的所有概念集 合c k ，以及c k 上的偏序关系所导出的有序集l - ( c x ，) ，称为形式背景 k 的概念格。通常用b ( o ，a ，i ) 来表示形式背景k 所产生的概念格。 定义2 6 形式概念集：构成概念格所有的形式概念的集合就是它的形式 概念集。 为了直观表示，以及方便下文叙述，我们首先给出一个形式背景所对应 7 郑州大学硕士学位论文 的概念格的例子。我们用k 来表示表2 2 中的形式背景， f l ，2 ，3 ，4 ，5 ， 6 ，7 是该形式背景的对象集合o ， l ，b ，r ，l w l ，l w 2 ，l w 3 ，l w 4 ，l w 5 ， l d i ，l m ，l d 3 , l d 4 ，l d 5 ，r w t ，r w 2 ，r w 3 ，r w 4 ，r w 5 ，r d i ，r d 2 ，1 ；t d | 3 ， r m ，r m 是它的属性集合a 。为了叙述的方便，在下文中我们将用1 2 3 这样 的格式来表示对象集合 l ，2 ，3 ) ，用l r w 3 r d 2 来表示属性集合 l ，r w 3 ，e - 0 2 。 下面我们给出表2 2 中的形式背景对应的概念格，如下图所示： 0 2 3 4 5 6 7 a 】 1 1 5 ：l 司 1 2 6 ：l l 税j 【2 5 6 ， 4 5 7 ，r l 2 6 7 ，k ， 3 7 。烁 l ，l l ；c l m p , m r d i ) ( 5 ：r i , w 2 r w 4 l d i r d 3 6 ，u 乌溉啊r 锅j 让：u 矗丑伪r i ，2 i 删l i 喃) i ，r k b i 嘲r ，薅 3 ，乱仍l 了：r k d 憾零碗 图2 1 表2 2 中的形式背景所对应的概念格 图2 1 中每个节点代表一个概念，一个概念由概念外延和概念内涵组成， 比如节点 4 5 7 ，r ，它的概念外延就是4 5 7 ，概念内涵是r 。概念之间的连线 表示概念之间的偏序关系。 2 2 2 概念格中的其它定义 下面给出概念格中的其它一些定义，这些定义是对概念格中的格节点和 节点之间关系的描述，定义如下： 定义2 7 引父( 子) 概念：对于概念格中两个不同节点c l ( x l ，y 1 ) ， c 2 ( x 2 ，y 2 ) ，如果c 卜 ，它的格底概念是 1 2 f ，l b r l w l l w 2 l w 3 l w 4 l w s l d i l d 2 l d 3 l 0 4 l d s r w i r w 2 r w 3 r w 4 r w 5 r m r d 2 r d 3 r m r d 5 ) ) ，它们都是唯一的。 2 3 概念格构造的常用算法 概念格的构造过程实际上是概念聚类的过程。目前已经提出了很多概念 格的构造算法，这些算法按照构造方法的不同大致可以分为三类嘲：批处理 算法、增量算法和并行算法。在接下来的部分，我们介绍这几类算法以及每 一类算法中的代表算法。 ( 1 ) 批处理算法( b a t c ha l g o r i t h m ) 9 郑州大学硕士学位论文 批处理算法是概念格构造算法中最常见的，批处理算法主要完成两项任 务：生成所有的格节点；建立格之间的关系。根据构造方式的不同，可以将 它分为三类：自顶向下构造算法、自底向上构造算法和枚举算法。 自项向下的构造算法先构造概念格的格项概念，然后再向下逐渐构造下 层的节点，比较有代表性的算法有以下几种：b o r d a t 算法船，t i t a n i c 算法蚴， n e x t c l o u r s e 算法。 自底向上算法和自顶向下算法刚好相反，它首先构造概念格的格底概念， 然后再向上扩展，最后构造格项概念，它的代表性算法是：c h e i n 算法。 枚举算法则是按照一定的顺序枚举格中的所有节点，然后再生成格之间 的关系，它的代表性算法有：g a n t e r 算法，n o u r i n e 算法嘲 ( 2 ) 增量算法( i n c r e m e n t a la l g o r i t h m ) 增量算法也叫做渐进式构造算法，目前提出的增量算法也有很多种，虽 然这类算法在具体的构造上有所不同，但是它们都有一个共同的特点，那就 是：首先构造一个很小的形式背景的概念格，然后将其余的形式背景元组逐 渐插入到已经构造好的概念格中，在插入的过程中，将待插入的元组与格中 所有的形式概念做比较，根据它们相交的结果采取不同的措施。不同算法之 间的区别主要在于生成格之间关系的不同。比较典型的算法有g o d i n 汹3 算法， c a p i n c t o 1 算法。 ( 3 ) 并行算法( p a r e l l e la l g o r i t h m ) j e k e n g u e 、e v a l t c h e v 和c t d j a m e g n i 在前人的基础上，于2 0 0 5 年提 出了一种概念格的并行构造算法d & c 汹1 。概念格的并行构造算法与上面两类 方法不同，它主要是基于p c a m 的思想。p c a m 就是划分( p a r t i t i o n i n g ) 、通 讯( c o m m u n i c a t i o n ) 、聚集( a g g l o m e r a t i o n ) 、映射( m a p p i n g ) 这几个并行 处理步骤。在划分阶段，根据分布式站点的个数将形式背景按照属性项进行 平均分割，然后平均分配到各个分布式站点上；通讯的功能就是负责各个分 布式站点之间的联系、交互；聚集在整个p c a m 中起着重要的作用，它负责 将两个分布式站点所形成的子概念格整合在一起形成一个新的子概念格，这 个过程不断的进行；最终的映射阶段就是获得了整个形式背景的概念格。 其它的一些并行算法还有：基于n c x t c l o s u r e 算法的并行算法 1 0 郑州大学硕士学位论文 p a r a l l e l n e x t c l o s u r e 驯，刘宗田等人还对概念格的分布式处理进行了研究m 3 1 1 。 2 4 分类规则挖掘介绍 2 4 1 分类规则挖掘的概念 分类，通常来说是在已有的数据( 通常称为训练样例、训练集) 上构造 一个目标函数或者分类模型，该函数( 或者模型) 能够将那些未知类别的数 据归入到某个特定的类别中。 分类规则挖掘是基于归纳学习的思想，通过研究已知其类别的诸多对象， 发现对象属性与其类别间的关系，即分类规则。分类规则挖掘是数据挖掘最 重要的研究领域之一。它主要研究一组已知其类别的数据对象( 训练数据集) 的属性与其类别间的关系，发现其规律( 分类规则) ，以用来对未知类别的数 据对象做出类别判断。 2 4 2 分类规则挖掘的方法 在进行分类规则挖掘时，通常经过以下两个步骤：( 1 ) 建立一个对数据 集的描述模型；( 2 ) 通过这个模型对未知数据进行分类。 分类规则的获取通常都需要有一个训练数据集，也称为训练样例，该训 练样例具有完整的属性描述和类别。模型的建立过程就是对这个训练集的学 习过程，由分类算法对训练数据进行学习得到的描述模型通常称为分类器， 它是描述数据集合和概念集合的模型。一般情况下是采用一些学习算法来进 行的，常用的分类算法有：决策树分类算法嘲，决策树分类中的常用算法就 是i d 3 算法和c 4 5 算法；贝叶斯分类算法溉3 妇，基于神经网络的算法嘶1 等。 通常在获取描述模型( 分类器) 之后，需要对这个模型进行验证。一般 来说，就是用分类器对未知类别的数据进行分类。目前，很多学者在进行分 类规则挖掘的时候也给出了很多的分类器模型，这些模型通常来说各有各的 特点，但是一般的评价一个分类器优劣的尺度有下面几个：分类正确率、计 算复杂度、模型的简洁度等。这些尺度，对于一个特定的分类器来说，它通 常并不能符合全部，而只是具有某个特征，并且这些尺度往往是不能同时满 郑州大学硕士学位论文 足的。因此，在实际应用的时候，要根据待解决的问题构造合适的分类器。 2 5 几种基于概念格的分类规则挖掘算法 目前已经提出了一些基于形式概念分析的分类规则挖掘算法嘲，比如： g r a n d 3 ，l e g a l 蚓，g a l o i s 绷，r u l e a r n e r 捌，c i b l e 伽， c b a l a t t i e e h ，j p d s & n j v h 幻和c l n n c l n b 删等。它们使用不同的策略来进 行训练和分类。下面简单介绍一下这些算法。 ( 1 ) c b a l a t t i c e 算法 c b a l a t t i e e 算法是基于增量概念格构造的分类规则挖掘算法。对于一个 大的数据集对应的形式背景，它首先选择其中一小部分，并将这一部分形式 背景按照类标号进行分割，然后通过概念扩展构造一个伪格结构。最后通过 自下而上地遍历这个伪格结构，并将每一路径上遇到的概念内涵做并运算来 获取分类规则。 ( 2 ) g r a n d 算法 g r a n d 算法一种使用假格来进行学习并产生相应的规则的算法。在学 习阶段，它采用增量算法构造样本集对应的形式背景( o ，a ，i ) 的假格， 然后它通过这种假格来产生分类规则集，在规则集产生的过程中，它采用蚁 群算法来探测所有的子节点。 ( 3 ) r u l e a r n e r 算法 r u l e a r n e r 算法与g r a n d 算法类似，它们都在学习阶段产生了一个 假格，并以此假格来构造分类规则。不同的是，r u l e a r n e r 算法对形式背景处 理的时候忽略了它的类标号，而且它使用几个标签来选择最佳的节点。 r u l e a r n e r 算法与g r a n d 算法都在它们的父节点那里使用了很小一部分 属性来搜索规则，但是覆盖了很多的对象。 ( 4 ) l e g a l 算法 l e g a l 算法在学习阶段产生了一个只有一部分上形式概念的半格，并产 生规则，这是该算法一个很大的优点，但是它的不足之处是，只能进行二元 分类，并且在学习阶段和分类的阶段都需要2 个参数。它只能对未分类数据 1 2 郑州大学硕士学位论文 进行正反这两种属性的判断。 ( 5 ) g a l o i s 算法 g a l o i s 算法在学习阶段产生概念格，在执行阶段对未分类的对象进行分 类。它在学习阶段的结果只有概念格，并且忽略了类标号。在执行阶段，对 于每一个未分类的对象，它搜索概念格中的所有形式概念，并将那些概念外 延是对象属性子集的概念选择出来，利用它们进行分类。 ( 6 ) j p d s & n j v 算法 j p d s & n j v 算法在学习阶段产生一个形式背景的平凡概念格，该概念格 忽略类标号的值。在分类阶段，它采用相似形式概念对形式背景( o ”，a ， 1 3 ) 中的对象进行分类，算法搜索每一个对象的相似概念，并给出它的类标号。 2 6 本章小结 在本章中，首先给出了f c a 的一些基础知识：形式背景、形式概念，概 念格，形式概念集等，然后给出了一个具体的形式背景例子，并通过它所对 应的概念格说明了概念格中的一些其他的定义和性质。这是本文的理论基础。 在第3 小节中介绍了一些常用的经典概念格构造算法，包括：批处理算法、 增量算法和并行算法，并给出了它们的代表算法。在第4 节中介绍了分类及 分类规则的基本知识。在第5 节中介绍了目前提出的一些通过概念格获取分 类规则的算法，并对其中的几种算法进行了介绍。 1 3 郑州大学硕士学位论文 第三章基于形式概念集的分类规则算法 通常那些由形式概念分析来获取分类规则的方法，都是首先构造出形式 背景的完备概念格，然后通过提取概念格中的格节点来得到分类规则的。但 是，这种方法由于会产生很大的冗余，从而影响构造的规则获取的效率。本 文从形式概念集构造出发，提出了一种基于形式概念集的分类规则挖掘算法。 3 1 形式概念集的构造 3 1 1 基于类标号的形式背景划分 在进行数据挖掘的时候，尤其是对于那些数据量比较大的情况，往往都 需要耗费大量的时间。如果采用分治的思想，在不改变最终结果的情况下将 数据集按照它的某一种性质进行分割，使它成为多个小的数据集，然后对这 些小的数据集分别进行处理，往往是能够降低挖掘时的规模，从而提高挖掘 的效率。 因此，在构造形式背景的概念格的时候，降低形式背景k 的规模是一个 非常有效的降低概念格构造复杂度的方法。那么如何降低形式背景k 的规模 呢? 无非是将形式背景按对象或者按属性进行分割。在形式概念分析中，对 形式背景按对象进行自然分割称为形式背景的并置，对形式背景按属性进行 分割称为形式背景的叠置口，它们的定义如下： 定义3 1 m 1 并置：令k i = ( o ，a l ，1 1 ) ，k e = ( o ，a e ，1 2 ) 是两个具有 相同对象集o 的子形式背景，则形式背景k _ ( o ，a iu a 2 ，i lu 1 2 ) ，称为形 式背景k l 和k 2 的并置，即k - k l ik 2 ，其中，a ln a 2 = 1 2 i ，i ln1 2 = 1 2 i 。 定义3 2 叠置：令k l = ( o l ，a ，1 1 ) ，k 2 = ( 0 2 ，a ，1 2 ) 是两个具有 相同属性集a 的子形式背景，则形式背景k 予( ( o lu 0 2 ) ，a ，i lu 1 2 ) ，称为 形式背景k l 和k 2 的叠置，即k k l k 2 ，其中，o l n 0 2 = o ，i l o l 2 = 1 2 l 。 根据以上的定义我们可以知道，并置是按照属性项将形式背景进行横向 的划分，分割后的各个子形式背景，它们具有相同的对象集和不同的属性集， 1 4 郑州大学硕士学位论文 并且属性之间没有交集，属性的并集与原形式背景相同；而叠置是按照对象 将形式背景进行纵向的划分，划分后的各个子形式背景，它们具有相同的属 性集和不同的对象集，并且对象之间没有交集，对象的并集就是分割前的形 式背景。 对于分类规则来说，最终经过挖掘得到的规则是与类标号相关的，而对 于那些不同类标号的对象来说，它们在形式背景中是不相交的。因此，本文 先对形式背景k 按照类标号进行横向的划分，来减小形式背景的规模。 通过划分可以降低形式背景的规模，但是对形式背景的划分要建立在划 分后的形式背景与原来的形式背景等价的基础上，如果划分后的形式背景得 到的分类规则集与原形式背景得到的规则集不同，则这种划分就没有任何意 义。因此，我们首先通过引理来证明这种形式背景的划分与其它通过构造完 备概念格获取的规则，在规则集上是等价的。 引理3 - 1 通过按类标号划分构造出的形式概念集与完备概念格构造的 形式概念集，它们所对应的分类规则集是等价的。 证明：令k l = ( o l ，a ，i i ) ，k 2 - - ( 0 2 ，a ，1 2 ) ，类标号 l i 、l 2 ) e a ， 并且对