（系统科学专业论文）概念格理论在数据挖掘中的若干问题研究.pdf

国防科学技术大学研究牛院学位论文 摘要 概念格是根据数据集中对象与属性之| 日j 的二：元关系建立的一种概念层次结 构，生动简洁地体现了概念之间的泛化和特化关系。它是由德国数学家w i l lr 于 1 9 8 2 年提出的，目前已被广泛应用于数据挖掘、信息检索、软件工程等领域。本 文的工作主要集中在：概念格的基本理论以及应用到数据挖掘中，本文期望在这 些方面做更多的探索，_ 方面充分挖掘概念格的应用潜力，另一方面寻找新的数 据挖掘算法。 本文主要讨论了下面几个问题： 1 、在概念格理论中，改进了以往的属性约简问题，极大地去除了冗余计算， 提高了约简效率。 2 、讨论了概念格的建造问题，提出了基于属性矩阵的建造算法，该算法把相 同的对象看作是一个整体，提高了建造的效率。同时该算法是一种基于属 性约简的，在建造的同时进行约简，有效的避免了先建造再约简的烦琐过 程。 3 、将概念格用于规则提取，主要包括关联规则和分类规则。提取算法是基于 概念格的思想，但是避免了建格的过程，是一种快速算法，并将规则进行 文本分类，实验结果令人满意。 4 、将概念格应用于文本聚类中，作为天然的聚类工具，本文给出了聚类算法 以及需要解决的几个问题。将图像数据转化为形式背景，利用概念格进行 图像关联规则提取。 最后，本文对概念格理论在数据挖掘中的应用进行了总结，对进一步的研究 方向进行了展望。 关键词：概念格数据挖掘属性约简分类规则关联规则文本聚类 第1 页 国防科学技术大学研究生院学位论文 a b s t p a c t c o n c e p tl a t t i c ei sak i n do fc o n c e p t u a lh i e r a r c h i c a ls t r u c t u r eb a s e do nt h eo b j e c t a n da t t r i b u t er e l a t i o ni nd a t as e t i te x p r e s s e st h eg e n e r a la n ds p e c i a lr e l a t i o nb e t w e e n c o n c e p t sv i v i d l y c o n c e p tl a t t i c ew a sp r e s e n t e db yg e r m a nm a t h e m a t i c i a nw i l l ra n d h a sa l r e a d yb e e nu s e di nd a t am i n i n g ，i n f o r m a t i o nr e t r i e v a la n ds o f t w a r ee n g i n e e r i n g t h em a i nw o r ko ft h i sp a p e ri st h et h e o r yo fc o n c e p tl a t t i c ea n di t sa p p l i c a t i o ni nd a t a m i n i n g w ew a n tt oe x p l o r es o m e t h i n gi nt h i sa r e a , o no n eb e h a l f , d i gt h ep o t e n t i a l a b i l i t yo fc o n c e p tl a t t i c e sa p p l i c a t i o n , o nt h eo t h e rb e h a l f , a n df i n ds o m en e wd a t a m i n i n ga l g o r i t h m s t h ei n n o v a t i o no ft h i sa r t i c l e ： 1 、i m p r o v et h ea t t r i b u t er e d u c t i o ni nc o n c e p tl a t t i c et h e o r ys i n c ei te l i m i n a t e st h e r e d u n d a n tc o m p u t a t i o nm a x i m a l l ya n ds p e e dt h er e d u c t i o ne f f i c i e n c y 2 、w ed i s c u s st h eb u i l d i n go fc o n c e p tl a t t i c ew h i c hi sc o r et o p i ci nt h et h e o r yo f c o n c e p tl a t t i c ea n dp u tf o r w a r dab u i l d i n gm e t h o db a s e do na t t r i b u t em a t r i x t h i s a l g o r i t h mc o n s i d e r st h es a m eo b j e c t sa saw h o l ea n di m p r o v e st h eb u i l d i n g e f f i c i e n c y a tt h es r n l et i m e ，t h ep r o c e s so fb u i l d i n gi sa l s ot h ep r o c e s so fa t t r i b u t e r e d u c t i o n ，t h u sa v o i dt h er e d u n d a n tp r o c e s sb e t w e e nb u i l d i n ga n dr e d u c t i o n 3 、a p p l yt h ec o n c e p tl a t t i c et oe x t r a c tr u l e si n c l u d i n gc l a s s i f i c a t i o na n da s s o c i a t i o n r u l e s t h ea l g o r i t h mi sb a s e do nt h ei d e ao f c o n c e p tl a t t i c e ，b u ti ta v o i dt h eb u i l d i n g t i m ec o n s u m i n ga n d 伽b ec o n s i d e ra saq u i c kt i m ea l g o r i t h m t h er e s u l to ft h e e x p e r i m e n tw eu s et h er u l e st oc l a s s i f yi sd e s i r a b l e 4 、w eu s ec o n c e p tl a t t i c et oc l u s t e rd o c u m e n t sw h i c hi so n eo ft h ei n n o v a t i o n so ft h e p a p e r a san a t u r a lt o o lt oc l u s t e r ，c o n c e p tl a t t i c es t i l lh a ss o m eb i gp r o b l e m st o t a c k l e ；w ep u tf o r w a r dt h e s ep e a n u t sa n dc r a c ks o m eo ft h e m l a s t l y ，w et r a n s f e r t h ei m a g ed a t at of o r m a lc o n t e x tw h i c ht h er u l ee x t r a c t i o na l g o r i t h mw ed i s c u s s e d c a l lb eu s e d a tl a s t ，t h i sp a p e rc o n c l u d e st h eb a s i ct h e o r yo fc o n c e p tl a t t i c ea n di t sa p p l i c a t i o n i nd a t am i n i n g ，a tt h es a l l et i m e ，p r o s p e c tn e wd i r e c t i o n sa b o u tt h ef u t u r ew o r k k e yw o s ：c o n c e p tl a t t i c e ；d a t am i n i n g ；a t t r i b u t er e d u c t i o n ；c l a s s i f i c a t i o n r u l e ；a s s o c i a t i o nr u l e ；d o c u m e n tc l u s t e r i n g 第2 页 国防科学技术人学研究生院学何论文 图表目录 表2 1 形式背景( u ，a ，i ) 8 图2 1 概念格的h a s s e 图8 表2 2 例2 1 的可辨识属性矩阵1 0 图2 2 概念格约简后的h a s s e 图1 1 图2 3 属性格的赋权h a s s e 图1 2 表3 1 形式背景( u ，a ，i ) 1 4 表3 2 ( u ，a ，i ) 的属性矩阵1 4 图3 1 实验结果1 8 表4 1 形式背景( d ，i ，r ) 2 2 表4 2 ( d ，i ，r ) 的属性矩阵2 2 表4 3 ( d ，i ，r ) 的关联规则2 2 表4 4 实验数据2 4 表4 5 由实验数据得到的结果2 4 图4 1 产生极大频繁项集所需时间2 5 表4 6 文档形式背景，a ，d 2 7 图4 2l i ：u ，a ，i ) 的概念树表示2 8 图4 3 计算机类建立的概念树2 9 表4 7 每类5 0 篇文档2 9 表4 8 每类1 0 0 篇文档2 9 表5 1 文档形式背景( d ，t ，r ) 3 2 图5 1 概念格的h a s s e 表示3 2 图5 2 产生概念格的x m l 文档3 6 表5 2 概念格的聚类结果3 6 图5 3e l u s t o 的聚类结果3 7 表5 3图像的元数据及一些可视属性的形式背景3 8 图5 4g a l i c i a 生成的概念格3 9 表5 4 ( d ，i ，r ) 的关联规则4 0 表5 5图像形式背景的属性矩阵4 0 第1 i i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研究成果尽 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表和撰写过的研 究成果，也不包含为获得国防科学技术大学或其它教育机构的学位或证书而使用过的材料与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目：趣盒整理诠垄数量撞握主煎羞王闽基班究 学位论文作者签名：赵塑! 竖日期：2 0 0 7 年1 1 月1 3 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留，使用学位论文的规定本人授权国防科学技术 大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允许论文被查阅和借 阅；可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存，汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文作者签名：翅亟蝗 作者指导教师签名：害色纽 日期：2 0 0 7 年1 1 月1 3 日 日期：2 0 0 7 年1 1 月15 日 国防科学技术大学研究生院学位论文 第一章引言 在哲学中，概念被理解为由外延和内涵所组成的思想单元。基于概念的这一 哲学理解，德国数学家w i l l er 于1 9 8 2 年首次提出了形式概念分析( f o r m a jc o n c e p t a n a l y s i s ) i l 捌用于概念的发现，排序和显示。形式概念分析，也称概念格，是一种 基于概念和概念层次的数学化表达的一种理论，是应用数学的一个分支。概念格 是知识的一种表现模型 2 1 ，依据知识体在内涵和外延上的依赖或因果关系，建立概 念层次结构，因此，在应用形式概念分析理论时，需要用数学的思维方式进行概 念数据分析和知识的处理。概念格作为一种具有极大潜力的有效的知识发现工具， 备受人工智能工作者的广泛关注。目前，概念格正在被广泛应用于机器学习，模 式识别，专家系统，计算机网络，数据分析，决策分析，数据挖掘等领域1 4 5 7 1 。然 而，这仍是一个年轻并在高速发展的领域。 1 1 研究背景 形式概念分析的基础是形式背景，一个由对象集u ，属性集a 以及u 与a 之 间的二元关系i 构成的三元组，a ，i ) 。在形式背景基础上，获得形式概念( ) ( ， b ) ，其中，x 称为概念的外延，是属于这个概念的所有对象的集合；而b 称为内 涵，是所有这些对象所具有的属性( 或特征) 集。概念是外延与内涵的统一体。 这种描述实现了对概念的哲学理解的形式化郾l 。 所有的概念同它们之间的泛化例化关系构成一个概念格。概念格的每个节 点是一个形式概念。概念格结构模型是形式概念分析理论中的核心数据结构。它 本质上描述了对象和特征之间的联系，表明了概念之间的泛化和例化关系，其相 应的h a s s e 图则实现了对数据的可视化。因此，概念格被认为是进行数据分析的有 力工具。 概念格理论的研究主要集中在以下几个方面【8 】： 1 、概念格的建造。从数据集( 概念格中称为形式背景) 中生成概念格的过程实质 是一种概念聚类的过程。对于同一批数据，所生成的概念格是一样的，这也是 概念格的优点之一。 2 、扩展概念格模型，而且粗糙集也可同时应用，粗糙集和概念格之间的结合是现 在的研究热点，另外从实际问题中构建形式背景也是应用概念格模型的第一 步。 3 、概念格的简化。在最坏的情况下，概念格中的节点是按指数增长的。所以在非 常大的数据集的情况下，在控制概念格中的节点的增长上是必须的。概念格的 第3 页 国防科学技术人学研究生院学位论文 翰化【! 1 指对概念格的修剪以控制概念格中节点的增长。 4 、规则提取。和其他分类器相比，概念格上提取的规则更具有相当或更好的分类 效果。由于形式概念分析是以概念格的形式使数据有机的组织起来，概念格节 点反映了概念内涵与外延的统一，节点间关系体现了概念之间的泛化和例化关 系，因此非常适合于用来发现规则型知识。 5 、应用。概念格已成功的应用于数字图书馆及文献检索，软件工程，知识发现等 领域，而且已取得了良好的经济效益和社会效益1 4 i 引。另外，基于概念格进行 软匹配的个性化搜索引擎【9 】，文本聚判6 j 等也是近年来研究的热点。 1 2 数据挖掘研究的内容概述 数据挖掘，是从大量的数据中挖掘出有用的信息，即从大量的、不完全的、 有噪声的、模糊的、随机的实际应用中发现隐含的、规律的、人们事先未知的， 但又是潜在有用的并且最终可理解的知识包括模型、规律、规则、模式、约束等， 潜在理解的信息和知识的非平凡过程i l o l 。事先未知的信息是指该信息是预先未曾 预料到的，或称新颖性。新颖性要求发现的模式应该是从前未知的，该信息是未 曾预料到的。数据挖掘就是要发现那些不能靠直觉发现的信息或知识，甚至是违 背直觉的信息或知识。挖掘出的信息越是出乎意料，就可能越有价值。所挖掘有 用性是指发现的知识将来有实际效用，即这些信息或知识对于所讨论的业务或研 究领域是有效的、有实际价值和可实现的。 数据挖掘也常被称为知识发现( k n o w l e d g ed i s c o v e r y ，k d ) ，1 9 8 9 年，在第1 1 届国际人工智能的专题研讨会上，学者们首次提出了基于数据挖掘的知识发现 ( k n o w l e d g ed i s c o v e r y i nd a t ab a s e ，k d d ) 概念1 1 2 1 。19 9 5 年在美国计算机年会上，一 些学者开始把数据挖掘视为数据库知识发现的一个基本步骤或把两者视为近义词 讨论。数据挖掘有如下三个特剧1 1 j ： 数据挖掘的数据量常常是巨大的。因此，如何高效地存取数据，如何根据一 定应用领域找出数据关系即高效率算法以及是使用全部数据还是一部分随机或有 目的地选择出数据子集，都成为数据挖掘工作者要考虑的问题。 数据挖掘面临的数据常常是为其他目的而收集好的数据。这就为数据挖掘提 出了一个问题，即收集数据，可能有一个或几个重要的变量未被收集，而这些变 量在后来做数据挖掘时被证明是有用的，甚至是至关重要的。也就是说，未知性 和不完全性将始终伴随数据挖掘的过程。 数据挖掘的令一个特点是数据挖掘工作者常常不愿把先验知识预先嵌入算法 内，因为这样就等于做“假设检验”。数据挖掘常常要求算法主动性地提示一些 数据内在的关系。 第4 页 国防科学技术大学研究生院学位论文 数扼：挖掘是一一fj 交叉学科，融合了数抛库、人工智能、机器学刊、统计学等 多个领域的理论和技术。数据库、人工智能和数理统计是数据挖掘的三根强大的 技术支柱。数据挖掘研究的主要内容主要纠j ： 1 、分类和聚类。分类和聚类是数据挖掘中一项非常重要的任务，目自订在商业上应 用最多。分类的目的是提出一个分类函数或分类模型，该模型能把数据库中数 据项映射到给定类别中的某一个。分类和回归都可以用于预测，和回归方法不 同的是，分类的输出是离散的类别值，而回归的输出则是连续值。聚类是根据 数据的不同特征，将其划分为不同的数据类。它的目的是使得属于同一类别的 个体之间的距离尽可能的小，而不同类别上的个体间的距离尽可能的大。聚类 方法包括统计方法、机器学习方法、神经网络方法和面向数据库的方法。 2 、相关性分析。相关性分析的目的是发现特征之间或数据之间的相互依赖关系。 数据相关性关系代表一类重要的可发现的知识。这类知识可被其他模式抽取算 法使用，常用的技术有回归分析、关联规则、信念网络等。 3 、偏差分析。如分类中的反常实例、例外模式、观测结果对期望值的偏离以及量 值随时间的变化等。其基本思想就是寻找观察结果与参照量之间的有意义的差 别。 1 3 概念格在数据挖掘中的研究现状 目前，概念格的研究取得了很大的发展和丰富，概念格理论正在被广泛应用 于机器学习，模式识别，数据挖掘，信息检索和软件工程等领域。在国内方面主 要是以西安交通大学的张文修教授为首的粗糙集与概念格研究团队，他们的研究 既涉及理论又有许多关于应用方面的文章 7 , 8 , 1 3 , 1 4 。自从1 9 9 5 ，国际会议 ( i n t e r n a t i o n a lc o n f e r e n c eo nc o n c e p t u a ls t r u c t u r e s ) 开始讨论有关概念格的理论和应 用( l n a i9 5 4 ，1 11 5 ，1 2 5 7 ，1 4 5 3 ，1 6 4 0 ，1 8 6 7 ，2 1 2 0 ，2 3 9 3 ，2 7 4 6 ，3 1 2 7 ) 。由于 概念格理论和应用研究的迅速发展，从2 0 0 3 年起，i c f c a ( i n t e m a t i o n a lc o n f e r e n c e o nf o r m a lc o n c e p tl a t t i c e ) 每年召开一次。2 0 0 3 在德国的d a r i n s t a d t 召开( l n a i 2 3 4 6 ) ，2 0 0 4 在澳大利亚的s y d n e y 召开( l n a i2 9 6 1 ) ，2 0 0 5 在法国的l e n s 召开( l n a i 3 4 0 3 ) ，2 0 0 6 在德国的d r e s d e n 召开( l n a i31 2 4 ) 。 ， 与传统的数据挖掘算法相比，概念格模型在半结构化和无结构的文本数据以 及w e b 数据上具有较好的效果，近年来在这方面的研究成果很多，但大都是在建 造概念格上，而挖掘关联规则的算法依然是传统的a p r i o r 算法及其改进算法，概 念格模型在规则提取方面已经具有了高效的算法，这些算法在关联规则、分类规 则【1 9 2 0 l 和决策规则的挖掘上要比传统的挖掘工具具有优势；另外，在文本、图像 分类、聚类方面，包括文本表示以及租糙集和概念格理论的融合 1 7 , b 】进行文本、 第5 页 国防科学技术大学研究生院学何论文 图像聚类和文献检索。 在今后的概念格研究中，增进概念格在知识表达过程中的表达能力是其中的 一个。这需要将它的研究范围从高度结构化的数据扩展到半结构化甚至是无结构 的数据上来l l6 。，以便于处理更加复杂的任务，比如，应用于语义网络。转向分析 无结构数据特别是文本数据时，主要的挑战是在实际应用概念格前如何处理数据， 以降低数据的内在的复杂性( 比如，通过聚类方法) ，通过这种方式，在处理无 结构的数据时，可以降低处理的时间，同时能够产生更加精确的、更适合阅读的 概念格。 1 4 本文的工作及内容组织 本文的主要工作集中在探索概念格的基本理论及其在数据挖掘中的应用。具 体内容包括概念格模型的属性约简，高效的建造算法及其概念格模型在分类规则、 关联规则提取中的应用，最后将这些算法应用到文本数据和图像数据上。目前虽 然有些学者在这方面进行了研究，但所做的工作还是比较少，相关的参考文献和 应用背景也比较缺乏，本文期望在这些方面做些初步的探索，一方面充分挖掘概 念格的应用潜力，另一方面寻找新的数据挖掘算法。 本文其余部分组织如下： 第二章介绍概念格理论的基础知识和属性约简方法，由于现有的约简算法的 复杂度较大，重复计算较多，本章提出了基于赋权图的约简方法，极大的去除了 冗余计算。 第三章研究了概念格理论的核心内容概念格的建造算法，由于传统的渐 进式算法忽略了对象之间的联系，本章利用粗糙集的分类思想将相同属性的对象 看作是同一个对象，利用属性矩阵的性质在建造概念格的同时进行属性约简，有 效的避免了重复计算的烦琐过程。 第四章介绍了基于概念格的规则提取，包括关联规则和分类规则的快速提取 算法。在关联规则提取中，利用概念格提取规则的思想，利用属性矩阵寻找极大 频繁项集，不需要建造概念格，提高了规则提取的效率；利用扩展概念格模型进 行分类规则的提取，该模型较经典的模型简单，而且提取的规则也有很好的分类 能力。 第五章将规则挖掘算法应用于文本和图像数据中。探索将概念格应用于文本 聚类和图像关联规则提取中，将文本和图像数据转化为形式背景，然后利用挖掘 算法进行规则提取。 最后结论部分是对本文的总结和未来研究工作的展望。 第6 页 国防科学技术大学研究生院学位论文 第二章概念格的属性约简方法研究 概念格作为知识的一种刻画方式，我们希望从中获得更多简洁的知识，以张 文修教授为首的学者们提出了概念格的属性约简理论( l s j 3 , 1 4 , 2 0 1 ，概念格属性约简就 是在保持对象集不变的前提下，寻找最小的属性集，它能够完全确定形式背景上 的概念及其层次结构，也就是说由这个最小属性集确定的概念格与全体属性集确 定的概念格同构。概念格属性约简使得形式背景中隐含知识的发现变得更容易， 也使得这些知识的表示变得更简单。它进一步扩充了概念格理论，对概念格理论 的研究和应用都有重要意义。 本章中，第一部分介绍了概念格理论的基本知识，在第二部分中，首先介绍 了概念格属性约简的理论和基本方法，然后提出了利用属性格的赋权图来进行约 简，该方法相比区分矩阵较为简单，避免了不必要的计算，是一种实用的约简方 法。 2 1 概念格理论简介 在概念格理论中，用形式背景( f o r m a lc o n t e x t ) 表示所要分析的数据，进而可以 从形式背景中提取出不同层次的概念以及概念之间的关系。首先介绍形式背景的 定义。 定义2 1 【1 1 形式背景是一个三元组m ，a ，i ) ，其中，u 是对象的集合，a 是 属性的集合，i 是u 和d 之间的二元关系，对于v x u ，y a ，若x 具有属性y ， 则x 与y 是有关的，记为毋。 二元形式背景是指属性值域为o 和1 的信息系统，现在研究的概念格一般都 是从二元形式背景中建立起来。对于形式背景，a ，d ，在对象集x u 和属性 集b _ c 彳上分别定义算子“一 1 3 】： ：2 u _ 2 ，x = f a l a e 彳， v x e x ，x l a l ：2 - - - ) 2 u ，b = f x i z u ，v a b ，x l a ) ( 2 1 ) 定义2 2 旧设( u ，a ，i ) 是一个形式背景，如果一个二元组( ) ( ，b ) 满足x = b ， 且x = b ，则称( x ，b ) 是一个形式概念，简称概念。其中x 称为概念的外延，b 称为概念的内涵。 对于形式背景，a ，i ) ，可以得到以下基本性质【8 】( ，五，x u 且 堆，垦，bs a ) ： 第7 页 国防科技术大学研冤生院字傅论文 ( 1 ) x i x 2jz x i ，b i b 2j 巧研； ( 2 ) x x ”，b gb “； ( 3 ) x = x ，b = b ： ( 4 ) x 垦b bex ； ( 5 ) ( x 。u x ：) = x inx ；，( 届ub ) = 研r 、反； ( 6 ) ( x 厂、置) 2x ? u 蔓，( 蜀n 垦) 研u 巧； ( 7 ) ( ”，x ) 和( ，b ”) 都是概念。 用l ( u ，a ，) 表示形式背景，a ，i ) 的全体概念。定义l ( u ，a ，) 上的偏序关 系“ 为：( 五，蜀) ( x ：，岛) 置五( 铮蜀2 岛) 。其中，( 五，届) 叫做( 五，岛) 的亚概念，( 五，垦) 叫做( 五，局) 的超概念。所有概念的偏序集记为l ( u ，a ，) ，称 为概念格【8 l 。 例2 1 下表是一形式背景，其中对象集合u - 1 ，2 ，3 ，4 ) ，属性集合a = a ， b ，c ，d ) 。该形式背景共有六个概念：( 1 ，a b d c ) ，( 2 4 ，a b c ) ，( 1 3 ，d ) ，( 1 2 4 ，a b ) ， ( u ，f 2 j ) 和( f 2 j ，a ) ，概念格的h a s s cn 如- f - 表2 1 形式背景( u ，a ，i ) u | aabcde 1 l 1 01i 211lo0 3o0o10 4111o0 f c 5 ( u ，f 2 j ) ( 1 2 4 ，a b ) f c 4 f c l ( 1 ，a b d e ) f c 6 ( a ，a ) 图2 1 概念格的h a s s e 图 若( 五，且) 和( 五，垦) 是概念，定义： 第8 页 国防科学技术入。 - 7 - 研冤生阮掌何论文 ( 五，且) ( x ：，b ) = ( 一n x ：，( 置u 岛) ” ， ( k ，蜀) v ( 置，岛) = ( ( 五u 五) ”，蜀n 岛) ， ( 2 2 ) 则( x 。，蜀) ( 五，岛) 和( x 。，且) v ( t ，岛) 也是概念，例如，在上例中 ( l ，3 9 1 1 ，( d u 口，b ，d ，p ) ) ”) = ( l ： 口，b ，d ，p ) ， ( ( 2 ，4 u 1 ，2 ，4 ) ”， 口，b , c ) n 口，引= ( l 2 ，4 ， 口 6 ) ) 。 从而工( u ，a ，) 是格，并且是完备格【3 1 。概念格生动地描述了隐含于数据中的 概念之间的泛化和特化关系，其中每个概念都是对象( 外延) 与属性( 内涵) 的 统一体。对于形式背景，a ，i ) ，如果( 五，骂) 是( 砭，岛) 的亚概念，( 砭，岛) 是 ( x l ，骂) 的超概念，那么( 五，蜀) 则具有较少的外延，更多的内涵，它更具体，是 ( 五，岛) 的特化；( 五，岛) 则具有较少的内涵，更多的外延，它更抽象，是( 五，旦) 的泛化。 2 2 概念格的属性约简 2 2 1 属性约简的基本概念 定义2 3 t 8 1 设l ( u ，4 ，五) 和l ( u ，4 ，厶) 是两个概念格，如果对于任意 ( x ，动l ( u ，4 ，厶) ，总存在( x ，b ) l ( u ，4 ，) ，使得x = x ，则称l ( u ，4 ，) 细 于l ( u ，4 ，厶) ，记作l ( u ，4 ，五) l ( u ，4 ，厶) ，如果l ( u ，4 ，) l ( u ，4 ，厶) ，且 l ( u ，4 ，厶) l ( u ，4 ，五) 那么称这两个概念格同构，记作l ( u ，4 ，) 兰l ( u ，4 ，厶) 。 定理2 1 嗍设，a ，i ) 是形式背景，v d 彳，d a ，总有 l ( v ，a ，) 三( u ，d ，厶) ( 2 3 ) 定理2 2 【8 1 设( u ，a ，i ) 是形式背景，如果存在属性集合d a ，使得 l ( u ，d ，厶) 兰l ( u ，a ，i ) ( 2 4 ) 则称d 是，a ，i ) 协调集。若进一步v d d ，满足( u ，a ，) ，马= b ，c ，d ) 。 夕夕 f c i ( 1 ，a d ) ( 2 4 ，a c ) f c 2 v f c 6 ( 9 ，日) f c i ( 1 ，a d )( 2 4 ，a c ) f c 2 v f c 6 ( a ，岛) 图2 2 概念格约简后的h a s s e 图 2 2 3 基于赋权图的属性约简 第1 1 页 国防科学技术大学研究牛院学位论文 定义2 8 ( x ，e ) l ( u ，a ，j r ) ( f - 1 ，2 ) ，设( x 。，岛) ( 墨，岛) ，即b i2 岛 ( 营五置) 。如果v ( x ，b ) r ( u ，a ，) ，b 2c b 。je b ，则( 局，垦) 称为父子 关系。 显然，在概念格的h a s s e 图中，两个上下直接相连的概念，其内涵构成了父子 关系，父子关系不具有自反性、传递性。 定义2 , 9 设l ( u ，a ，) 是一个概念格，其中的每个概念的属性集合的偏序关系 定义为蜀岛蜀垦( 营x ，2x ：) ，( x i ，马) ，( 置，岛) l ( u ，a ，) 。所有的属性 集合组成的格叫做原概念格的属性格，记为a l ( u ，a ，i ) 。 在本节中，我们用c 表示所有核心属性的集合，g 是属性格的h a s s e 图中的权 值，即g = = e 一目i ( e ，色) 是父子关系 ，n 是所有绝对不必要属性集合，r 是相对必要属性集合，显然a = c u r u 。 例2 3 ( 续例2 1 ) 例2 1 的形式背景属性格的赋权h a s s e 图如下。 a 八 a ，b ，d ，e a ，b ，c ) 纽历 d )( a ，b 沃么 a 图2 3 属性格的赋权h a s s e 图 其中g = c ) ， d ，e ， a ，b ，e ， d ， a ，b ) ) 。类似定义2 6 ，有 定义2 1 0 定义概念格三( u ，a ，) 的区分函数为 厂( ) = 咿a ( 。流) ( 2 9 ) 区分函数厂( ) 可以转化为最小析取范式的形式，其中的每一项都是原概念格 的属性约简。 在例2 3 中，厂( ) = d ( 口v 6 ) c ( d v p ) ( 口v 6 v f ) = ( 口 c d ) v ( 6 c d ) 从而约简的集合为 a ，c ，d ) 和 b ，c ，d ) ，这比辨识函数的化简( 2 8 ) 较为简单。 定理2 4 设三( u ，a ，) 是一个概念格，在其属性格中，以下性质成立： 第1 2 页 国防科学技术大学研究生院学位论文 ( 1 ) 如果= 口) ，则a 为核心属性。 ( 2 ) 设b = 蜀，垦，玩 ( 局g ，忍n c = a ，i = l ，2 ，m ) ，如果骂n e = a ， 则有r = 蜀u 岛u u 吃， 若b a ，属性约简的个数为 栉= l 蜀i i 逸i i 玩i ，若召= f 2 j ，只有一个约简集合c 。 证明根据吸收律，( 2 ) 显然。只证( 1 ) ，事实上，形，= 口) 营j ( z ，置) ， ( x ，色) l ( u ，a ，i ) ，置一哆= 口) ，即( e ，哆) 是父子关系。根据区分函数的定义， 对任一个约简集合d 有d 口 ，从而a 为核心属性。 定理2 4 给出了寻找核心属性和相对必要属性的一种方法，权值集合g 中的所 有单元素集合的并构成了核心属性集合c 。在例2 3 中，c = c u a = k 梆。对 于相对必要属性，如果er 、君，彩，用耷= j 9 in 君，替代零和b ，这样最终得到r = 曩u 砬u u e ( 耳n 刀) = o ，f ) 。在上例中b = a ，b ) ， a ，b ，e ) ，从而 r = 和，6 n a ，b ，e ) = 和，6 ) ，即最终的约简集合是 a ，c ，d ) 和 b ，c ，d ) 。 事实上，计算赋权图的权值较计算区分矩阵要简单许多，赋权图中的权值只 在两个相邻的两个概念中计算，而区分矩阵则要计算一些冗余的集合，例如 v ( 五，忍) l ( u ，a ，) ( 待l ，2 ，3 ) ，如果( 五，骂) ( 五，岛) ( 五，马) ， 显然 d 豇愆( ( 五，且) ，( 五，马) ) 三d ( ( 五，置) ，( 互，岛) ) ，根据区分函数的计算公式及吸 收律易知，d 捃彤( ( 五，且) ，( 五，马) ) 会被( ( 五，局) ，( 五，垦) ) 吸收，从而 腑搿( ( 五，垦) ，( 墨，马) ) 并不需要计算。 2 3 本章小结 本章介绍了概念格的基本知识和属性约简的基本理论及方法，在概念格的属 性约简中，由于计算区分矩阵的复杂度较大，存在冗余计算，提出了基于赋权图 的属性约简方法，该方法比利用区分矩阵进行约简较为简单，是一种实用的约简 方法。一般意义下的概念格约简就是寻找最小的属性集，它能够完全确定形式背 景上的概念及其层次结构；对于决策形式背景，同样可以研究概念格约简，即在 条件属性中寻找一个最小的属性集，可以完全确定由原来形式背景所确定的知识， 即属性蕴含规则。当形式背景的数据量比较大时，本节的算法仍不是高效的，如 何对形式背景进行高效而自动的约简仍是一个值得研究的课题。 第1 3 页 周防科学技术大学研究乍院学位论文 第三章概念格的建造算法研究 在概念格的应用过程中，概念格的构造效率始终是一大难题。概念格的构造 过程实际上是概念聚类的过程，是应用形式概念分析的前提。通常，概念格的大 小是数量级上的，而且要处理的数据又多数是海量的，因而概念格构造算法始终 是形式概念分析中的一个主要问题。在各种不同的构造算法中，渐进式算法1 2 卜2 3 】 被认为是比较有前途的一类，其中g o d i n l 2 l l 所提的算法及其一些改进的算法取得了 较好的效果，其基本思想就是将当前要插入的对象和格中所有的概念做交运算， 根据交的结果采取不同的操作。 渐进式算法忽略了对象之间的联系，本章利用粗糙集的分类思想提出了形式 背景的属性矩阵这一概念，并在属性矩阵的基础上给出了一种构造概念格的算法， 该方法把具有相同属性的对象看作是一个整体，并且在约简的同时进行建造，避 免了重复计算，提高了构造效率。 3 1 基于属性矩阵的建造算法 定义3 1 设形式背景叫，a ，i ) 的对象集u 关于等价关系i 的划分为 q ，g ，q ，该形式背景的属性矩阵必= ( 岛) 。定义为 岛= qr 、q ，( f ，j = l ，2 ，m ) ( 3 1 ) 例3 1 表3 1 是一个形式背景，其中u = l ，2 ，3 ，4 ，5 ，6 ，a - a ，b ，c ，d ， e ，cg ，h ，i 。u 在a 下产生一个分划叫a = ，其中c i = ( 1 ，4 ， c 2 = 2 ，5 ，c 3 = 3 ，g = 6 。该形式背景的属性矩阵如表3 2 。 表3 1 形式背景( u ，a ，d u aa b cdef g h l 11010010l0 210l000101 31oo loolol 4l010o10l0 5l0100o10l 6o100l010 o 表3 2 刑，a ，i ) 的属性矩阵 qc 2c 3c 4 c l a ，c ，h ) 第1 4 页 国防科学技术大学研究生院学位论文 c 2 孔c ) a c ，g ，i c 3 a a ，i 也g ，i ) c 4 o g ) g b ，e ，g 定义3 2 设( u ，a ，i ) 为一形式背景，b a ，如果科v ，使x = b 成立，则 称b 为( u ，a ，i ) 的一个概念属性。 显然，属性矩阵中的任一元素均为概念属性，另外v ( x ，b ) l ( u ，a ，i ) ，则曰 为一个概念属性。类似地，锻u ，如果3 b a 使x = b 成立，则称x 为，a ， i ) 的一个概念对象。 定理3 1 形式背景，a ，i ) 的所有概念属性关于集合的交是封闭的。 证明设置，垦彳为概念属性，即甄，五u ，使且= z ，垦= z ，从而 有bn 岛= zn z = ( 五u k ) ，又五u 五u ，故蜀r 、岛为一个概念属性。 定理3 2 形式背景( u ，a ，d 的所有概念属性所形成的集合 = b c _ ai 弘c _ u ，x = b 与l ( u ，a ，i ) 中所有概念的属性所形成的集合 甲= b ai u ，( x ，b ) l ( u ，a ，) 相等。 证明显然甲，下证甲2 。事实上，v b e ，冬u ，有x = b 。若 不存在x c _ u ，使x db ，则有b = x ，从而( j ，b ) l ( u ，4 ，) ，即b 、王，：否 则，为简记，不妨设只存在五，五c _ u ，有f = b ，f2 曰，令x = 五u 砭u ， 则有x = f n x ：- - b ，又矿= 五u 五= x ，故( x ，召) 三( u ，4 j ) ，即b e e f 。 定理3 3 形式背景，a ，i ) 的属性矩阵m = ( 置，1 具有以下几个性质： 、7 ，肘x 肘 ( 1 ) 属性矩阵膨对角线上的元素是每列中最大( 包含关系) 的集合； ( 2 ) 属性矩阵m 中唯一出现并且不被其它元素所包含的集合及其概念对象形 成一个概念，即如果不存在曰。m 使得bc b 。，则有( ，b ) l ( u ，a ，i ) ； ( 3 ) 所有概念属性所形成的集合 o = b i b 必或了犀，垦，最( 骂m ，i = 1 ，2 ，刀) ，使b = n ：矗 ： ( 4 ) 喝m ，岛= qn q ， 如果j 辱，m 且哆，= q 广、c3 岛， f ， l ，2 ，聊) ，则有( x ，岛) l ( u ，a ，i ) ，其中 x = m 【c u q ) u ( g u q ) 。 证明性质( 1 ) 显然，( 2 ) 由定理3 2 的证明过程即得。下i i ( 3 ) 和( 4 ) 。 第1 5 页 国防科学技术人学研究生院学位论文 对( 3 ) ，事实上，v b 中，e t x u ，有= b ，令x = u ：c ，若甩= 2 ，则 有b m ；若门3 ，不妨设胛= 3 ，显然有 b = ( c 。u qu q ) = ( qn q ) r 、( qn q ) = 骂：nb 2 ，； 以下证( 4 ) ，v 色m ，为简记，不妨设只存在一个哆，满足( 4 j 中的条件，那 么x = c ，u qu e u c ? ，只证( x ，色) l ( u ，a ，) 。又或= x 显然， 而 x = ( c j n q ) n ( qn g ) = b , j n b , ，= 色，从而得证。 属性矩阵m 是对称矩阵，因而