（计算机软件与理论专业论文）在数据挖掘中概念格的理论研究.pdf

硕士学位论文 摘要 知识是人类认识客观世界的结果，同时也是指导人们行为的准则，在知识经 济的时代里知识是社会发展的重要动力，是决定生产力发展的主要因素，特别是 随着时代的发展，环境的变化，认识的深入，人们必须不断的获取与发现新的知 识，人们有各种获得知识与发展知识的手段，而其中最重要的一种手段是从数据 库中进行数据挖掘。 随着i n t e r n e t 技术的日益普及，“丰富的数据与贫乏的知识”问题变得日渐 突出，而数据挖掘如何从大量的数据中智能地、自动地抽取出有价值的知识和信 息，因而成为当前人工智能中非常活跃的研究领域。概念格是近年来获得飞速发 展的数据分析的有力工具，用来发现数据中隐藏的知识模式。因此，研究概念格 的基本理论以及将其应用于知识发现有着非常重要的意义。本文主要研究概念格 的基本理论和基于概念格的知识发现。在概念格与粗糙集的关系方面，由于概念 格与粗糙集在数据分析方面有相似之处，并且粗糙集的一些概念包括等价类，上、 下近似等都可以通过概念格来表示。本文论述了概念格与粗糙集之间的联系，建 立了它们之间的的关系。在概念格的代数性质方面，本文给出了形式背景下概念 集合上的元素之间的二元运算，使通常意义下的概念格成为带有算子的概念格， 证明了概念格为代数意义下的格，并研究了其代数性质，为概念格的进一步研究 提供了理论基础和新的研究方法。在基于概念格的规则提取方面，数据挖掘尤其 是规则挖掘可以看作是一个形成概念的过程和发现概念之间关系的过程。概念 格反映了对象与属性之间的精确关系，而模糊概念格反映了概念与属性之间的不 确定联系，在现实生活中，人类认识的大量概念都是模糊的，因此研究模糊概念 格对于实际决策有着重要的意义。对概念格本身及其应用进行了一些研究，但是， 知识发现正处于发展阶段，概念格理论在知识发现中的应用还有许多问题值得研 究。本文的研究工作是一个尝试，相关工作还有待进一步深入。 关键词：数据挖掘；概念格；粗糙集；代数系统 在数据挖掘中概念格的理论研究 a b s t r a c t n o w a d a y sw i t ht h ew i d eu s eo ft e c h n o l o g yo fi n t e r n e t ，t h ep r o b l e mo f “a d e q u a t e d a t aa n ds c a r c i t y k n o w l e d g e ”h a sb e c o m ei n c r e a s i n g l y d i s t i n c t k n o w l e d g ed i s c o v e r ys t u d yh o wt og a i nv a l u a b l ea n di n f o r m a t i o ni n t e l l e c t i v e l ya n d a u t o m a t i c a l l yf r o mam a s so fd a t a ，s oi th a sb e e nav e r ya c t i v es t u d y i n gf i e l di n a r t i f i c i a li n t e l l i g e n t c o n c e p tl a t t i c ea n da p p l i e di ti nk n o w l e d g ed i s c o v e r yh a v e i m p o r t a n ts i g n i f i c a n c e t h i st h e s i sm a i n l yd e a l sw i t ht h eb a s i ct h e o r ya n dt e c h n o l o g yo fk n o w l e d g e b a s e do nc o n c e p tl a t t i c e c o n c e p tl a t t i c e a n dr o u g hs e th a v em a n yc o m m o nc h a r a c t e r i s t i c si nd a t a a n a l y s i s a n ds o m ec h a r a c t e r so fr o u g hs e ts u c ha se q u i v a l e n tc l a s s ，u p p e ra n du n d e r a p p r o x i m a t ea l lc a nb er e p r e s e n t e db yc o n c e p tl a t t i c e i nt h i sp a p e r t h ea s s o c i a t i o n a n dt h e i rr e l a t i o nb e t w e e nc o n c e p tl a t t i c ea n dr o u g hs e ta r ed e s c r i b e d i nt h ea s p e c to ft h ea l g e b r a i cp r o p e r t i e so fc o n c e p tl a t t i c e ，t h ep a p e rs u g g e s t sa b i n a r yo p e r a t i o nb e t w e e nt h ee l e m e n t sf o rt h es e to fa l lc o n c e p t si nf o r m a lc o n t e x t ， w h i c ht u r n st h ec o n c e p tl a t i c ei ng e n e r a ls i g n i f i c a n c ei n t ot h o s ew i t ho p e r a t o r s w e a l s op r o v e dt h a tc o n c e p tl a t i c ei sal a t i c ei na l g e b r a i cs i g n i f i c a n c ea n ds t u d i e di t s a l g e b r a i cp r o p e r t i e s t h e s er e s u l t sp r o v i d e dt h e o r e t i c a lf o u n d a t i o na n d an e wm e t h o d f o rf u r t h e rs t u d yo fc o n c e p tl a t i c e w eh a v ed o n es o m es t u d yi nc 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 ，b u tk n o w l e d g e d i s c o v e r yi si nb o o m i n gs t a g ea n dt h e r ea r em a n yp r o b l e m sw o r t hs t u d y i n go nt h e a p p l i c a t i o no fc o n c e p tl a t t i c e o u rw o r ki sj u s tab e g i n n i n g ，a n dr e l a t e dw o r kn e e d s t 0b ef u r t h e rd e v e l o p 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 ，r o u g hs e t ，a 1 9 e b r a i c s y s t e m i i 硕士学位论文 插图索引 图2 1 1 具有3 个元素的所有偏序集的h a s s e 图7 图2 2 2 两个偏序集的直接积的例子7 图2 2 具有5 个元素的格图8 图2 3 一个伽罗瓦连接的例子9 图4 1 表4 1 的形式背景对应的概念格的h a s s e 图1 5 图5 1 1 两个完全格的直接积2 0 图5 1 2 正则影射2 1 图6 3 形式背景所建的概念格4 2 i l l 兰州理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成 果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体己经发表 或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律后果由本人承担。 作者签名： 违支惰 日期： 月? g 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向 国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权兰 州理工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密囤。 ( 请在以上相应方框内打“”) 作者签名维纠痔 导师签名：芦 一 多 日期： 日期： 年 月2 寥日 年r 目氐b 吖0、 硕士学位论文 1 1 数据挖掘技术概述 第1 章绪论 随着数据库技术和数据库管理系统的广泛应用，全球范围内数据库中的数据 量急剧增大，电子化数据越来越多，信息高速公路的发展和广泛应用使得整个社 会变成了信息化的网络世界，数据量的增长更为迅猛。有些公司经过多年积聚下 来的商业数据目前己经超过数百万乃至数亿条记录：有些面向科学研究数据库的 数据量也非常惊人，比如，记录天体信息的数据库容量达到数个t b 字节。全球 商业、企业、科研机构和政府部门在过去若干年的时问里积累了海量的、以不同 形式存储的数据资料，现今社会人们正生活在数据的海洋中，各式各样的数据让 人们眼花缭乱，这些数据中蕴含着大量的知识，人们正面临“数据丰富而知识贫 乏”的问题，人们渴望的是那些有用的知识，但是怎样才能快速有效地从海量的 数据中得到那些知识呢? 虽然数据库系统提供了对数据的管理和简单的处理功 能，人们可以在这些数据之上进行商业分析和科学研究，但数据资料如此庞大而 自一十分繁杂，因此要从中发现有价值的信息或知识，达到为决策服务的目的， 对人工处理来说是非常困难的。人们需要能够对数据进行较高层次处理的技术， 从中找出规律和模式，以帮助人们更好地利用数据进行决策和研究 数据挖掘技术是人工智能数据库和统计理论的结合技术，具有较为广泛的 应用前景【专家预测数据挖掘在未来十年内会有革命性进展，是个性化w e b ， 个人偏好分析，实时识别和分析用户信息的关键技术。 数据挖掘的目的是从数据中找出有意义的模式。模式可以是一组规则，聚类， 决策树，依赖网络或其他方式表示的知识。一般来说，一个典型的数据挖掘过程 可以分成四个阶段，即数据预处理，建模，模型评估及模型应用。数据预处理阶 段主要包括数据的理解，属性选择，连续属性离散化，数据中的噪声及丢失值处 理。实例选择等。建模包括学习算法的选择，算法参数的确定等。模型评估进行 模型的训练和测试，对得到的模型进行评价。这三个阶段是循环往复的过程，直 到得到用户满意的模型为止。在得到满意的模型后，就可以运用此模型对新数据 进行解释。数据挖掘过程是交互的和领域相关，需要用户特别是领域专家的参 予。一般一种发现算法不可能适合所有的挖掘问题的需要。一种算法可能只适合 特定的问题。例如，决策树分类比较适合于发现高维空间的结构但是并不适合于 决策类间的边界是由二次多项式描述的问题。因此，没有通用的数据挖掘算法 为特定问题挑选一个特定的合适的算法是困难的，但是已经有了一些相关研究。 在数据挖掘中概念格的理论研究 1 9 9 5 年举办了国际第一届知识发现与数据挖掘学术会议，会议上明确定义了 知识发现。 目前知识发现和数据挖掘己成为研究的热点和焦点，一批用于知识发现和数 据挖掘的系统被开发出来，在商业、经济、金融、管理等领域都取得了应用性的 成果。国际知识发现研究知名学者加拿大s i m o nf r a s t e r 大学的h a nj i a w e i 教授 领导的课题组开发了数据挖掘原型系统d b m i n e r t 0 1 。这是一个交互式，多层次 挖掘系统，可以从数据库中挖掘不同层次知识，包括一系列的挖掘功能：概括、 特征、分类、预测等等。在该系统中提供了一种交互式的类s q l 语言一一数据挖掘 查询语言d m q l ，能与关系数据库平滑集成，实现了基于c s 结构的u n i x 和w i n n t 版本。由i b m 公司a l m a d e n 研究中心的r a g r a w a l 等人研究开发的多任务数据挖掘 系统q u e s t 面向大型数据库系统，包括关联规则、分类规则、序列模式和相似序 列等。 本文要研究的是概念格的理论，尤其是概念格的代数性质，并将概念格和粗 糙集相结合，进行初步的探索。 1 2 课题背景 经过十多年国内外工作者共同努力，数据挖掘技术的研究与应用已取得了 很大的成果，已经成为越来越重要的技术。有很多用于数据挖掘的方法无论是在 理论上还是实际应用上都已经很成熟了，其中包括决策树，r o u g h 集等等。近些 年来随着人们对概念格理论的进一步认识以及它在数据挖掘中作，的进一步广泛 和深入，该理论的研究己经越来越受到国内外学者的重视，因此本文将概念格的 理论作为研究重点，并尝试着探讨概念格和粗糙集之间的联系。 概念格也被称为形式概念分析，在形式概念分析中，概念的外延被理解为属 于这个概念的所有对象的集合，而内涵则被认为是所有这些对象所共有的特征 ( 或属性) 集合，这实现了对概念的哲学理解的形式化。而概念格作为形式概念分 析中核心的数据结构，本质上描述了对象和特征之间的联系，表明了概念之间的 泛化与例化关系，其相应的h a s s e 图则实现了对数据的可视化。作为序论和格论 与实际应用结合的产物，概念格模型的研究具有重要的理论意义。目前国际国内 对概念格的数学性质、与粗糙集合之间的关联等方面做了大量研究，取得了一系 列重要成果，并已在数据分析、信息检索和知识发现等方面得到了广泛的应用 2 - s 。但是，概念格构造的时间复杂性和空间复杂性问题始终是困扰其应用的一 大难题。国内外的研究人员虽然已经提出了一系列概念格构造算法，但现有的算 法大多都是考虑数据库对象方向的渐增更新问题，而对属性方向的渐增更新问题 未见报道。也就是说现有的算法不适应于形式背景在属性方向上的更新需要。因 此，研究基于属性的概念格构造算法是有意义的。概念格构造算法可以分为两类： 2 硕士学位论文 渐进式算法和批处理算法。渐进式算法表现出了更强的生命力，但其结果仍然不 能令人满意，其原因就在于这些算法基本上都是串行的，而生成的概念格所采用 的都是集中式存储模式。采用分治策略来构造和存储概念格是有效地解决这一问 题的主要途径。由于概念格有良好的数学性质和层次结构等特点，因此，概念格 的分布处理模式，是解决上述问题是非常理想的工具。通过对形式背景( c o n t e x t ) 的分割，形成多个子背景，然后再对子背景分布构造其子格，最后再进行子格的 合并形成完整概念格，在这方面国际上只有p v a l t c h e v 等作了一些尝试，通过枚 举两个子格概念之间的组合，计算出其对应的全局格概念。但由于一个部分格的 概念对另一部分格的概念是遍历计算，会产生较大的重复，从而影响了 p v a i t c h e v 所提算法的效率。研究如何进行有效概念格的分布处理具有现实的意 义。从数据库中提取规则是知识发现的主要内容，现已出现了大量提取规则的算 法。规则一般都是从频繁项集中提取的，而频繁项集的数量是很庞大的，且从中 提取的规则还存在着大量的冗余规则。为了缩减频繁项集的数目，减小提取规则 的搜索空间同时也不丢失有用信息，现在提出了用频繁封闭项集来提取关联规 则。从事务数据库中提取频繁封闭项集的方法有c l o s e ，c h a r m 等多种。其中c l o s e ， c h a r m 算法需多次扫描原事务数据库，且需产生候选项集，但数据库增加事务时 就需重新处理。c l o s e t 虽只对数据库扫描次，也无需产生候选集，但它也不适 应数据库更新的要求。而基于概念格的关联规则提取算法与传统的算法相比也具 有相当的优点。从格中提取无冗余规则的最小集合，对用户获取有用的知识，降 低所需的时空复杂度是有益的，但这方面还很不完善。而如何和概念格分布处理 相结合，目前未见有相关的研究报告。研究概念格分布处理的相关算法，将为实 际应用提供有效方法：研究把概念格的分布处理和规则提取相结合，利用概念格 和对应的最小无冗余规则的关系，并且利用多概念格的合并直接得到完整格及其 对应的规则集合，将极大地降低规则提取所需的时间和空间开销。因此，研究概 念格分布处理及其在概念格分布处理框架下的获取有用的知识，具有重要的理论 意义和实用价值。 形式概念分析几乎同时提出的是粗糙集理论。五十年代以后人们尝试着用各 种方法进行数据挖掘，比如神经网络方法，统计学习方法，遗传算法，支持向量 机方法等，但是这些方法得到的知识是人们不能直接理解的隐性知识，而粗糙集 和概念格方法得到的知识是人们可以理解的关联规则，这些关联规贝符合人们的 经验，更适合在管理决策中应用。因此二十多年来，粗糙集方法和概念格方法得 到了迅速的发展。 1 3 国内外研究现状和发展趋势 1 9 9 9 年由g a n t e r 和w i l l e 教授所著的形式概念分析一书从本质上分析 在数据挖掘中概念格的理论研究 了形式背景和概念格自身的各种特点以及概念之间的关系，概念格的分解，构造 和度量等等有关概念格的基础知识，为国内外学者研究概念格在各个领域提供了 理论基础。 国外的主要研究成果如下：一些基于概念格的分类统：s a h a l n i 开发的 r u l e a r n e r 系统，它首先根据属性构造出概念格，然后从格中提取出分类规则用 于支持对象的分类：n j i w o u a 等设计的l e g a l e 系统使用学习参数来生成半格一 概念格的一部分，从而有效地控制了概念格的空间复杂性，然后采用投票的方式 对新对象的分类进行群体决策。g o d i n 等描述了基于概念格模型的概念形成方法， 主要提出了从概念格中提取出蕴涵规则的算法，并使用了关系数据库中函数依赖 的理论结果来处理规则的蕴含问题，但是这种蕴涵规则是一种确定性规则，不具 备描述概率规则的能力和抗噪音能力。为了提高规则发现的鲁棒性进行了扩展， 提出了从概念格中提取近似规则( 又称为概率蕴涵规则) 的算法。p a s q l l i e r 等研 究了关联规则的提取问题，他们的工作是以己经发现了所有的频繁项集作为基础 的，提出了用于提取确定性关联规则的d e q u e n n e g u i g l l e 基，以及用于近似关联 规则的适当基和结构基。h o t b 研究了基于概念格的概念聚类方法，并实现了一些 学习系统，包括o s h a m 和i o s h a m ，其中i n c o s h a m 在o s h a m 系统基础上增加了渐进式 学习的能力。o s h a m 系统将三种关于概念的不同观点( 即经典的、原型的和示例 的观点) 组合起来，并使用了一种灵活的匹配过程( 组合了逻辑的、门限的和最近 邻的条件) 来允许系统改进它自身的推理性能，从而可以对未知的实例进行灵活 的预测。w i l l e 教授认为在有些时候仅考虑一个形式背景是不足够的，并指出需 要引入背景网络的形式方法，还提出了不同形式背景之问的四种不同的操作：并 置，下置，融合以及级连。以w i l i e 所提出的多背景为理论依据，以不同形式背 景的对象集和属性集之问的关系为基础，研究了在概念格框架结构下对结构化 ( 复杂) 对象所进行的概念学习和规则提取，还对学习所得到的概念和规则进行了 解释。 在国内取得成果主要包括胡可云等人提出了利用概念格进行分类和无冗余 规则的提取，谢志鹏等人提出利用概念格的层次关系提取关联规则，刘宗田等提 出的利用容差关系建立广义概念格提取近似规则，合肥工业大学的胡学钢等人也 在一般概念格的基础上提出了扩展概念格、约简概念格、相对约筒格和量化概念 格的定义，并利用这些非经典概念格进行高效的规则提取。赵奕等人针对概念格 与r o u g h 集之间的联系，把二者有机的结合在一起提出了r o u g h 概念格，并在此基 础上提取蕴含规则。侯锦等提出了利用概念格进行r o u g h 集理论中重要的组成部 分一属性约简。此外还包括一些概念格构造和维护算法的研究等等。 目前已经有了一些建造概念格的算法： a 批处理算法( b a t c ha l g o r i t h m ) ；如b o r d a t 的算法h 1 、g a n t e r 的算法哺1 、 4 硕士学位论文 c h e i n 的算法”1 、n o u r i n e 的算法。 b o r d a t 的算法；格g 从最顶端的结点开始建造。接着生成所有结点的所有 子结点并连接到它的父结点，然后对每个子结点递归重复该过程。该算法的关键 在于生成子结点的过程。 g a n t e r 的算法：该算法没有生成h a s s e 图，但是其按包含拓扑排序的方式 有利于生成图。 c h e i n 的算法：它是一个自底向上算法，格是从底开始一层一层向上建造的。 此算法看起来简单明了，但是在实际应用中会在同层，下层中产生大量的冗余对 因此效率较差。该算法没有生成图。但是其逐层生成的方式很容易进行连接。 n o u r i n e 的算法：其与以上三种算法都不一样，n o u r i n e 生成概念格时，使 用概念外延的补集作为基本的操作单位。但是该算法的复杂度低于b o r d a t 算法， g a n t e r 算法。 b 增量算法：其基本思想都是将当前要插入的对象和格中所有的概念交。 根据交的结果采取不同的行动。典型的算法有6 0 d i n 算法h 1 、a p i n e t o “们算法和 t b h o “1 算法。 c 。领域知识的添加：领域知识可以动态的添加进格中，格也可以以只插入 规则的方式形成。 1 9 8 2 年波兰学者p a w l a k 提出了粗糙集的概念，它的基本思想是通过案 例库的分类归纳提出概念和规则。通过案例库的条件特征变量将案例库分类而形 成概念，并通过生成的概念去研究目标特征，从而得到关联规贝l j 。目前，粗糙集 的理论研究主要集中在数学性质及代数结构，粗集理论的扩展研究，粗糙逻辑， 高效的约简算法研究，以及粗糙集与其它算法相结合的研究方面。 1 4 研究工作及成果 本文对概念格作了全面的分析，重点包括概念格的基础理论、概念格的构造、 概念格的分解、概念格在k d d 中的应用以及概念格与r o u g h 集之间的关系，同时还 分析了最近出现的几种非经典类型概念格( 扩展概念格，约简概念格，广义概念 格等) 。研究了它们的具体定义，构造以及在k d d 中应用等等。经过深入的研究取 得以下成果： ( 1 ) 概念格是有力的进行数据分析的工具，快速有效的构造概念格对于以后 的分析起着极其重要的作用。目前己经有了很多构造概念格的算法，它们之间有 类似的地方：也有不同之处。本人通过认真的学习研究对现有的算法进行了综述， 指出了它们各自的优缺点，并在此基础上根据它们的不足提出了创新性的改进措 施，提出了一个快速有效的渐进式建格的方法，并给出了相应的算法。另外还对 概念格的维护作了研究，以渐进式构造概念格的思想为基础提出了种有效的概 5 在数据挖掘中概念格的理论研究 念格维护的算法。 ( 2 ) 大型复杂的概念格在分析时比较费力，无论是建格还是提取规则都很困 难，这就需要对其进行分解，分解后得到的小型的概念格才有利于分析。国内的 学者在概念格的构造方面的研究的较多，但在概念格的分解方面的研究相对少一 些，因此本人仔细研究文献中介绍的四种概念格的分解方法，对它们各自的特点 进行了总结。 ( 3 ) 与概念格理论同时产生的是粗糙集理论，粗糙集和概念格一样是数据分 析和知识发现的有力工具。 粗糙集有其自身的优点，国内外研究r o u g h 的水平也突飞猛进。概念格和 r o u g h 集之间存在着一定的联系，如何把它们更好的联系在一起用在实际应用中 成为了最近热门的课题。本人经过深入的研究分析，对r o u g h 集的属性约简进行 了必要的探索和改进。 另外，概念格和粗糙集都是建立在分类基础上的，因此两种理论虽然有不同 之处，但又有共性。利用粗糙集理论的方法研究概念格理论，利用概念格理论研 究粗糙集，相互借鉴，相互促进，推动了概念格和粗糙集理论的共同发展，本文 根据概念格和r o u g h 集之间存在的关系提出了一种基于概念格的全新的条件属 性及值约简的算法。这种算法可以一次性地快速找到属性的绝对约简。 6 硕士学位论文 第2 章序理论 形式概念分析( 概念格) 是基于数学序理论的，特别是完全格理论，所以在 介绍概念格之前我们有必要先介绍一下数学中的序理论，同时我们也将简单介绍 一下概念格中所需要的数学基础，但是由于篇幅所限我们仅介绍一些重要的概念 和基本的定理。在第一节中我们介绍偏序集，第二节介绍完全格，这两节是后面 章节的基础。 2 1 偏序集 定义2 1 1 - 集合膨与之间的二元关系r 是有序二元组伽，n ) 的集合，其中 m m ，n ，即尺m ，这里的是笛卡儿乘积，打) 只，我们也常记 作：m 砌。如果m = ，则我们说r 是定义在膨上的。我们还用r 。1 表示r 的逆 关系。即： 蜀 r 一= o ，掰) ：o n ，露) 耐。 定义2 1 2 如果定义在集合m 上的一个二元关系r ，对于所有的元素 z ，y ，z e m ，都满足下列条件，则称r 是一个偏序关系( 简称序) ： ( 1 ) x r x ( 自反性) ( 2 ) 坶且y r x 辛工一y ( 反对称性) ( 3 ) 田且y r z 抛 ( 传递性) 对于偏序关系r ，我们经常使用符号来表示( 对于r ，使用符号来表示) ， 如果x s y 而且工y ，则写作工y 。通常读作x 墨y 为“x 小于或等于y ”。偏序 集( m ，) 是一个有序二元组，它由一个集合m 与定义在m 上的一个偏序关 系s 组成。 例1 ：设集合掰是所有实数的集合9 l ，若其上的偏序关系是通常的s 关系， 则( 筑，) 是一个偏序集。 定义2 1 3 ：如果口 b ，且不存在满足口c t b 的元素c ，那么口称为b 的一个 下元，在这种情况下，b 是口的一个上元，记作：4 b 。 每个有限偏序集( m ，) 都能够用一个h a s s e ( 哈斯) 图来表示。肘中的 元素用h a s s e 图中的小圆圈表示，如果x , y e m 满足x 竺竺罗伯” “5 嫩弋夕j 钆饥8 r 刀，f a ，b ，c ，d 图4 1 ( 表4 1 的形式背景对应的概念格的h a s s e 图) 对于形式背景k i ( u ，d ，r ) ，令h t - 阮，x ) 和h ：i ( 邑，k ) 是l ( r ) 中的元素， 若按照q n 也- ( x x n x ：，k u k ) 和玩u 也- ( 置u 置，x n k ) 来定义概念的交和 并运算是不合适的，因为按照上述方法作成的概念的交与并不一定能得到一个新 的概念。例如，在根据表4 1 所建的h a s s e 图4 1 中，对于“2 ，5 ，6 ，6 ) 及( 4 ，6 ，d ) ， 虽然有( 亿5 ，6 n 4 6 ， 6 ) u p ) 一( 6 ，p ，d ) 及( 6 u 3 ，毋，伽，b ，d n c ) ) i ( 3 ，5 ，田，乃) ，但是( 6 ，p ，d ) 和( 3 ，5 ，田，刀) 不是概 念，下面我们给出概念的交与并的一个合理的定义。 4 2 二元关系的建立 定义4 1 ：设l ( k ) 为k 一，d ，尺) 形式背景上的概念集合，q 一隅，x ) 及 h ：一( z ：，k ) 为( k ) 上的两个概念，规定： u 日：一( g 伐n k ) ，k n y p 1 6 硕士学位论文 致n 也一伐n 五，( 墨n x ：) ) 下面来证明定义中的u 巩与啊n 凰为概念 定理4 1 ：只n h 2 和日1 u 巩是l ( k ) 中的一个元素，即为k 一，d ，r ) 的一个 概念。 证明：v y 嘶u k ) ，有y k 或y k 。当) ，kh 寸，( 墨n z ：) 墨，显 然有x r y 成立，同理，) ，k 时，也有x r y 成立。敌对v y u k ) 总有 y ，( 五n x 2 ) 。 因此 k u k ，( 五n x ：) ( 4 1 ) 反过来，慨( 五u x ：) ，有x e 五或石以，因为，v y n e ) ，即y e y , r y k 时，结论r a y 是成立的，因此x e 9 0 1 n k ) ，从而： 五u 邑g n e ) ( 4 2 ) 要证明珥n 以一( 墨n 五，瓴n 石：) ) 为概念， 只要证明 g ( ，( 墨n 易) ) 一j r l n 邑即可 由于g ( ，( 五n 邑) ) 一仁u ：v y ，( 墨n j r 2 ) ，r a y ，令z g ( ，( 墨n 五”时，及 x u e ，( 墨n x ：) 成立，所以y e a r ) ，艺时，总有x r y 成立因为g ) 一五， 从而x e 五，同理x g x ，因此x 皈n 工2 ) ，所以有g ( f ( x 1 n x d ) ( 墨n x z ) 。 反过来，对于x n x ：) ，v y ，( 五n 五) ，由，( 五n x ：) 的定义，有x r y 成 立是显然的。因此有x g ( ，( 置n x d ) ，从而，g ( ，( 置n 毛) ) 2 ( 墨n x ：) 证明了 g ( ，( 五n 邑) )= 佤n 易)，故有佤n 五，( 五n 毛) ) 为概念， 即 ( 墨n 五，( 墨n 邑) ) 晖) 再来证明日u 也一( g 伐n k ) ，k n k ) 为概念， 同样只需要证明 ( g ( x n 艺) ) 一k n k 即可。令y x n k ，慨g n k ) 。由g ( x n k ) 的定 义，有坶成立，也即，y f ( g n k ) ) ，因此x n k ， 伐n k ) ) 另一方面，对于y e f ( g n k ) ) 及慨g 瓴n k ) ，坶成立是显然的由 ( 4 2 ) 的定义，五u 邑c g n k ) ，所以当z 置或工x 2 时，对于y ，国n k ) ) ， 总有x r y 成立。又由，隅) 一k ，g ) - 墨，和，阮) 一e ，g 瓴) - 五推知y e t , n k ， 从而，0 n k ) ) x n k 因此n 一隅n 邑，( 五n j r 2 ) ) 也为概念证毕 推论4 1 ：形式背景下概念集合l 僻) 对于运算n 和u 是封闭的，从而 ( 饭) ，n ，u ) 作成了具有二元算子“n ”和“u ”的代数系统n x n 。 4 3 概念格的代数性质 定理4 2 ：代数系统( ( k ) ，n ，u ) 中的元素珥一( 墨，x ) ，以一( 而，k ) 及 h 3 一( 墨，e ) 满足下列运算律： 1 7 在数据挖掘中概念格的理论研究 ：以n h l 一h 。，q u q 一皿； k ：1 1 3 也一h 2 n 置，q u 巩一h 2 u 只 岛 ( h i n h 2 ) n h 3 一q n ( 也n 只) ( q u h 2 ) u 也一只u 似2 u h 3 ) l 4 ：h i n ( h i u h 2 ) 一q q u ( h 1 n h 2 ) a h 证明：由定义直接可得厶和厶是显然成立的。 因为： ( 幂等律) ( 交换律) ( 结合律) ( 吸收律) 下面首先证明厶是成立的。 慨n h 2 ) n 也一佤n x 2 ，瓴n x 2 ) ) n 阢，k ) 一“墨n x 2 ) n 邑，( 墨f i x 2 n 也) ) = ( 置n 五n x 3 ，( 置i 1 x 2n x 3 ) ) 又因为： n n 也) 一慨，k ) n ( z ：n 五，( 易n 置) ) 一( 墨n 0 ，2 n 邑) ，( 墨n ( x ：n x 3 ) ) ) 一( 墨n 置n 邑，( 五n x 2 n 墨” 所以( q n ) n 只- h 1 n ( 日：n 地) 再由： ( 髓u h 2 ) u h 3 一( 五，x ) u ( 占( en e ) ，kn e ) 一( g ( xn ( en ，；) ) ，xn ( en e ) ) 一( g ( x n k n k ) ，k n k n k ) 及 ( 1 u h 2 ) u 日，一( g ( k n k ) ，k n k ) u ( 邑，k ) = ( g ( ( xn k ) n k ) ，( xn e ) n 巧) ) 一( g ( xn kn 巧) ，k1 3 kn 匕) 因此有：( h 1u 也) u 弘一qu 慨u 日3 ) ，从而岛成立。 下面我们来证明l 成立： h 1n o u 日：) 一( 置，x ) n 0 ( xn k ) xn k ) 一( a - 1a g 伐n k ) ，( 墨c l g ( xn k ) ) ) 因为f ( x 1 ) 一x ，有五g 瓴n k ) ，所以 ( x 1 f i g ( k n e ) ，隅n g ( k n k ) 一( x i ，l ( x o ) 一( x l ，y ) 一h 1 即h 1 n ( i - 1 1 u h 2 ) - 皿。 又有：h 1 u ( q n 日：) - ( 五，x ) u 隅n x 2 ，f ( x l f i x ：) ) 一( 占( x n ，( 五f i x ：) ) ，k n ，( 墨n 邑) ) 一( g 瓴) ，k ) 一( 五，x ) 硕士学位论文 一h 1 从而l 成立。证毕。 定理4 3 ：设l ( k ) 为形式背景k 一( u ，d ，r ) 下的概念格，令髓一佤，k ) 及 h ：一( x ：，e ) 是l ( k ) 中的元素( 概念) ，则最小上界l u b q ，h 2 = h 1 u h 2 ， 最大上界g 1 b 噩，日2 ) = 皿n h 2 证明：设h 一( z ，】，) = l u b q ，日： ，那么有皿s h 与h 2 s 日成立，从而y c _ r , 与y e ，因此y k n k ，故有( g ( x n k ) ，x n e ) s h ，又因为k n e x 与x n e k ，有以s ( g n k ) ，x n e ) 与h 2 五( g 嘶n k ) k n k ) ，由于h 为最小上 界，因此有h 量( g 瓴n k ) ，x n k ) - h 1 u h ：，证得h 一珥u 日2 ，同理可证得 g j 占 h i ，h 2 一h 1 n 日2 证毕 定理4 4 ：形式背景k 一，d ，r ) 下的概念格工( k ) 为代数意义下的格，它具有 代数格的所有性质。 由于概念格是代数意义下的格，定理成立是显然的。同时我们有如下的推论。 推论4 2 ：形式背景k 一，d ，r ) 下的概念格l ( k ) 是一个完备格，它的任何子 集有最大下界和最小上界。 定理4 5 ：形式背景k - ，d ，r ) 下的概念格l ( k ) 是有单位元1 和零元0 的格 证明：令0 - ( 妒，d ) ，1 - ，声) ，v h l 一( 置，x ) 工僻) ，由 珥n ( u ，庐) 一( g n o ) ，kr i d ) 一( g ) ，x ) 一( x i ，x ) - 及 珥n ( u ，妒) - ( x 1 n u ，厂( 置n ( ，) ) 一隅，( 墨) ) 一( 墨，k ) - 皿 故0 和1 分别是犯僻) ，n ，u ) 的零元和单位元。证毕。 定理4 6 ：对于概念格弛僻) ，n ，u ) 中的任何两个元素q 一佤，k ) 及 h 2 一( x 2 ，k ) ，如果f ( x l n x ：) - y , u k ，g n k ) 一五u x 2 ，则( k ) ，n ，u ) 是分配 格。 证明：由条件有( x l ，x ) u ( x 2 ，k ) 一( 墨u x ：，k n k ) 及 佤，x ) n 0 ，2 ，k ) 一( 五f i x ：，x u k ) ，从而： h i n ( h 2u h ，) - ( x 。，x ) n “工2 ，k ) u ( 邑，e ) ) 一( x l ，x ) n ( x ：u 蜀，k n 巧) 一( x l n ( 如u 蜀) ，x u 睨n k ) ) - ( 1 3 五) u ( 墨n 五) ，u k ) n u k ) ) 且：( 匾n h ：) u o n 峨) - ( 墨n x 2 ，k u e ) u ( 墨n 蜀，x u k ) - “墨n x ：) t j ( x ln 毛) ，( xu k ) n ( ku 墨” 所以有：q n q ，2 u 凰) 一( 4 c l h 2 ) u 溉n h 3 ) 同理可证得：日1 u ( 也n 皿) - ( h i u h ：) n 慨u h 3 ) 证毕 定理4 7 ：l ( k ) 为形式背景k 一，d ，r ) 下的概念格，q 一( 墨，x ) 及 吃- ( x 2 ，匕) 是l 僻) 中的元素( 概念) ，则下列的命题是等价的： 在数据挖掘中概念格的理论研究 a ) h 1 墨h 2 b ) q n h 2 一只；q u h 2i h 2 证明：a ) 成立时，由k k 与置邑有： ( 墨，k ) n ( k ，k ) 一( x i n x 2 ，k n k ) - ( 置，( 墨) ) 一佤，k ) 一h 1 及：( 墨，k ) u ( 邑，k ) 一( g n k ) ，( x n k ) ) 一( g 暖) ，k ) 一( x ：，k ) - h 2 所以有b ) 成立； 当b ) 成立时，由h 1 n h 2 一q 静( x i ，k ) 一隅n x 2 ，( x 1 n 石：) ) ， 另夕h ：由( k u k ) ，( 墨n 石：) 一x 可知：x u k c y 。因此k k ，从而： h t s h 2 。所以证得a ) 是成立的。证毕。 4 4 小结 本章给出的概念格上的二元运算，为研究概念格上的同态与同构奠定了理论 基础，对分析形式背景的概念之间的联系提供了新的工具，也为建造概念格提供 了新的途径。 2 0 硕士学位论文 第5 章概念格的分解 现实活中我们遇到的需要处理的数据信息往往是很庞大的，其对应的形式背 景及概念格无论从规模还是复杂度上都是很难处理的，这时我们就有必要对共进 行分解处理。关于概念格的分解即是把一个复杂的概念格分解成为几个简单的部 分。概念格的分解必须通过某种原则来进行，常见的四种分解方法，它们是子直 接分解，a t l a s 分解，替代分解，子张量分解。在对概念格进行分解对应该首先 注意概念格的规模，类型以及分解的目的。针对不同的概念格不同的分解目的进 行分解，才能产生事半功倍的效果。在本章中将介绍一下每种方法的特点以及理 论基础。同时对其中的子直接分解和a t l a s 分解作了深入的研究，给出了这两种 分解方法的具体算法，并且在子直接分解的基础上提出了基于用户兴趣的最简子 直i 妾分解的概念以及相应的算法。 5 1 子直分解 子直接分解是一种以同余关系为基础的概念格的分解方法。这种方法简单易 懂，分解效果好，有利于后续工作的进行。为了更好的理解子直接分解这种分解 方法的特点和介绍具体的算法，下面来看一下相关的理论基础。 5 1 1 理论基础 定义5 1 ：设r 是任意的一个指标集，一组完全格叱) 。的直接积被定义为 x v , ：- ( 形，) ，其中 ) 日s 以) 日：营只，对于所有f r 的都成立。格k ，t e t 日目 是积的因子。对于s e t ，存在影射以：k k ，其中以妣) 培) _ t 这个影射 日 叫做正则影射 定义5 2 ：一组完全格的一个完全子直接积是它们的直接积的一个完全子 格，其因子上的典型影射都是满射。 例5 1 ：看一个直接积的例子： i f 卜： vv v l 在数据挖掘中概念格的理论研究 图5 1 1 两个完全格的直接积 其上的正则影射表示为： a b c d b d v v 1 v 图5 1 2 正则影射 定义5 3 ：一个完全格v 的完全同余关系是上的一个等价关系0 ，对于指标 集t ，其满足x , o y , ，t e t 黟( ) 口( 只) 和( v 薯) p ( v 只) 。我们定义为包含的等价 日l q 日日 类。 因子格v o ：一 陋p i 茗n 有这样的序关系f x e 引y p ：一x o ( x ) ，) (