（计算机应用技术专业论文）概念格分布处理及其框架下的知识发现研究.pdf

辽宁科技走学硕士论文摘要 摘要 概念格也称为g a l o i s 格，是形式概念分析理论中的核心数掘结构，它 利用二元关系建立一种概念| b j 的层次关系，是进行数据分析和规则提取的 有效工具。随着研究深入。形式概念分析越来越多地被应用到数据挖掘、 信息检索、软件工程等方面，已经成为当前计算机科学领域的一个热门研 究课题。围绕这个背景，本文开展以下研究： 概念格以其良好的数学性质已成功地应用于知识发现等诸多领域。但 由于概念格自身的完备性，构造概念格的时1 日j 一直是影响形式概念分析应 用的主要障碍。本文详细分析了现有各种建格算法的利弊，结合各自的特 点，提出了一种新的剪枝策略来构造概念格，动念形成剪枝条件，避免了 概念格构造过程中部分无效闭包的生成。 随着处理的形式背景的增大，构造概念格的时空复杂度也会随之急剧 增加。采用分治策略来构造概念格是解决这一问题的有效途径。本文基于 概念格闭包系统划分的思想，提出了一种新的概念格并行构造算法，把概 念格对应的闭包系统划分为多个独立的子闭包系统然后分别进行概念的 计算。 从数据库中提取规则是知识发现的主要内容，如何减少冗余规则的提 取，降低搜索空间，是当今k d d 研究总的一个热门课题。本文基于概念 格闭包系统划分的思想，把概念格的分布处理应用于数据挖掘领域中频繁 项集的计算，以保持原有信息不变为根本，对事务数据库进行拆分，在每 个子事务数据库内进行频繁项集的计算。 概念之问的关系是有序的，通过所对应的h a s s e 图，可以形象地揭示 概念间的泛化和特化关系，反映概念间的层次结构。然而在生成每个概念 前，对形式背景中的对象集合或属性集合的每个元素，在未规定字典序| ； ， 是不可比的，本文从这一点着手，把概念视为形式背景中的最大“矩形”， 研究了概念格中概念信息的图形化，并用之于概念格中相关定理的证明。 对手写数字串的识别首要的一个任务就是要把数字串拆分成单个数 字，本文基于类的划分，把聚类分析的思想应用于数字串的拆分。 关键词：概念格；构造算法；闭包系统；频繁项集；概念矩形 辽宁科技大学硕士论文a b s t t a c t a b s t r a c t c o n c e p tl a t t i c ea l s ok n o w na sg a l o i sl a t t i c e ，t h ec o r ed a t as t r u c t u r eo f f o r m a lc o n c e p ta n a l y s i s ，i sae f f e c t i v et o o lo fd a t aa n a l y s i sa n de x t r a c t i o n r u l e sw h i c hu s e sab i n a r yr e l a t i o nt oe s t a b l i s hah i e r a r c h i c a ls t r u c t u r eo f c o n c e p t s w i t ht h ed e v e l o p m e n to ft h er e s e a r c ho fc o n c e p tl a t t i c e ，i th a sb e e n u s e dw i d e l yi nk n o w l e d g ed i s c o v e r yi nd a t a b a s e ，i n f o r m a t i o nr e t r i e v a l ，a n d s o f t w a r ee n g i n e e r i n ga n db e c o m ean o t a b l er e s e a r c ht o p i ci nc o m p u t e rs c i e n c e d o m a i n b a s e do nt h eb a c k g r o u n d ，t h i s p a p e rc a r r i e d o u tt h ef o l l o w i n g s t u d i e s ： c o n c e p tl a t t i c ei s h a sb e e ns u c c e s s f u l l ya p p l i e di nm a n yf i e l d ss u c ha s k n o w l e d g ed i s c o v e r yb y i t sm a t h e m a t i c a ln a t u r e ，b u tb e c a u s eo fi t s c o m p r e h e n s i v e n e s s ，t h ec o n s t r u c t i v et i m eo ft h ec o n c e p tl a t t i c eh a sa l w a y s b e e nt h em a i no b s t a c l eo ft h ea p p l i c a t i o no ft h ec o n c e p tl a t t i c e t h i sp a p e r d i s c u s s e si nd e t a i lt h ee x i s t i n gc o n c e p tl a t t i c es t r u c t u r ea l g o r i t h ma n dp r e s e n t s an e wb a t c ho fc o n c e p tl a t t i c e s p r u n i n ga l g o r i t h m ，b a s e do nt h e c o n c e p t l a t t i c eb a t c hg e n e r a t i o na l g o r i t h mt h r o u g hb a t c ht e c t o n i cp r o c e s sa n a l y s i s w i t ht h ei n c r e a s i n go ft h ec o n t e x t ，t h et i m ec o m p l e x i t ya n dt h es p a c e c o m p l e x i t yo ft h ec o n s t r u c t i o no fc o n c e p tl a t t i c e w i l lb e d r a m a t i c a l l y i n c r e a s e da c c o r d i n g l y e x p l o r i n gt h eu s eo fn e wm e t h o d sa n dm e a n st ot h e c o n c e p to fl a t t i c es t r u c t u r eh a sb e c o m et h em a i nt o p i co ft h ec o n c e p tl a t t i c e b e i n gd i f f i r e n tf r o mt h et h ee x i s t i n gc o n c e p tl a t t i c ec o n s t r u c ta l g o r i g h m s ， u s i n gt h es t r a t e g yo fd i v i d ea n dc o n q u e ri sa ne f f e c t i v ew a yt os o l v et h i s p r o b l e m a f t e rt h ed i s c u s s i n gi nd e t a i lo ft h ep a r a l l e lc o n s t r u c ta l g o r i t h mo f c o n c e p tl a t t i c e ，t h i sp a p e rp r e s e n t san e wc o n c e p tl a t t i c ep a r a l l e lc o n s t r u c t a l g o r i t h m sb a s e do nt h et h ei d e a o ft h ed i v i d i n go ft h ec l o s u r es y s t e mo f c o n c e p tl a t t i c e t h ec o r r e s p o n d i n gc l o s u r es y s t e mo ft h ec o n c e p tl a t t i c ei s d i v i d e di n t oan u m b e ro fi n d e p e n d e n tc l o s u r es y s t e ma n dp r o c e e dt ot h e c a l c u l a t i o no ft h ec o n c e p t e x t r a c t i n gf r o mt h ed a t a b a s eo fk n o w l e d g ed i s c o v e r yr u l e si st h em a i n c o n t e n ta n dh o wt or e d u c er e d u n d a n c yr u l e se x t r a c t i o na n dt h es e a r c hs p a c ei s ah o tr e s e a r c ht o p i ci nt h ek d d t h i sp a p e rp r e s e n t san e wa s s o c i a t i o nr u l e i l 兰主翌苎查兰丝主笙墨垒堕! 竺【- m i n i n ga l g o r i t h mb a s e do i l t h ed i v i d i n go fc o n c e p tl a t t i c e t h i sa l g o r i t h m m a i n t a i n st h eo r i g i n a lu n c h a n g e di n f o r m a t i o no ft h ed a t a b a s ea st h eb a s i ca n d c a l c u l a t e sf r e q u e n ti t e m s e t si ne a c ho fd a t a b a s e t h e r e l a t i o n s h i p b e t w e e nt h e c o n c e p t s i s o r d e r l y ，r e v e a l s t h e g e n e r a l i z a t i o n a n ds p e c i a lr e l a t i o n s h i po ft h ec o n c e p t sa n dr e f l e c t s t h e c o n c e p to fh i e r a r c h i c a ls t r u c t u r et h r o u g ht h eh a s s ed i a g r a m h o w e v e r ，e a c ho f t h ee l e m e n t si nt h es e to ft h eo b j e c t so ra t t r i b u t e si si n c o m p a r a b l eb e f o r e p r e s c r i b i n gt h el e x i c o g r a p h i c a lo r d e r c o n s i d e r i n gt h ec o n c e p ti nt h ec o n t e x t a st h em a x i m a l “r e c t a n g l e ”，t h i sp a p e rs t u d i e dt h eg r a p h i c so ft h ec o n c e p t a n du s e di ti nt h ep r o o f so ft h ec o r r e l a t i v et h e o r e m s k e yw o r d s ：c o n c e p tl a t t i c e ；c o n s t r u c t i n ga l g o r i t h m ； c l o s u r es y s t e m ；f r e q u e n ti t e m s ；c o n c e p tr e c t a n g l e ； i i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得辽宁科技大学或其它教育机构的学位或证书而使用过的材料，与 我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确 的说明并表示了谢意。 一型卜帐一 关于论文使用授权的说明 本人完全了孵辽宁科技大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅：学校 可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手 段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：袒导9 韦签名： 辽宁科技大学硕士论文 第一章绪论 1 1 课题的背景和意义 第一章绪论 数掘收集和数据存储技术的快速进步使得各组织机构可以积累海量 数据。然而，提取有用的信息已经成为巨大的挑战，很多数据还没束得及 很好地利用，便已经被丢弃或过时了。而且通常，由于数据量太大，对这 些数据只进行传统的简单数据查询等操作已经无法满足人们对知识的需 求，在另外一些情况下。需要回答的问题不能使用已有的传统数据分析技 术来解决。人们更希望计算机能帮助自己分析数据、理解数据，帮助自己 从丰富的数据集合中发现对自己有用的隐藏的信息知识。于是，从数据库 中发现有用的知识即知识发现( k d d ) 1 1 ，2 】成为了十分热门的研究领域。它是 数据库技术、人工智能、机器学习、神经网络、统计学、模式识别、知识 库系统、知识获取等多种学科的交叉领域，它能够帮助人们从丰富的数据 中提取出有意义的知识柬，用以帮助人们做出决策。 形式概念分析理论【3j 是2 0 世纪8 0 年代德国的w i l l e 教授首先提出的， 概念是人类进行知识表达的一种手段。数据库知识发现过程就是将数掘库 中蕴涵的知识形式化成有用概念的过程，每个形式概念由两部分组成：外 延。即概念所覆盖的对象；内涵，即对象的属性描述。定义了概念j 日j 的格 序关系后建立了概念格，也称为g a l o i s 格，其生动而简洁地体现了概念知 识间的泛化和特化关系，得到数据间的依赖或因果关系。因此，概念格被 认为是进行数据分析的有力工具，可以将其与数据库等相关理论相结合， 来应用于数据库知识发现操作4 , 5 , 6 , 7 , 8 】，如发现事务数据库中的关联舰则或 分类规则o 等知识是非常有意义的。形式概念分析除了在知识发现领 域中的应用外，还已经在面向对象程序设计、信息检索、w e b 服务管理i l 副 和软件工程i i 列等其它领域得到了很成功的应用。 1 2 国内外研究现状、水平和发展趋势 1 2 1k d d 的研究现状 k d d 是数掘库领域中最重要的课题之一，国际上第一次关于数据挖掘 与知识发现的研讨会于1 9 8 9 年在美国的底特律召开，在此会议上第一次提 出了知识发现一词。1 9 9 5 年举办了国际第一届知识发现与数据挖掘学术会 辽宁科技大学硕士论文第一章绪论 议i l4 1 ，会议上明确定义了知识发现。 目前k d d 和d m 已成为研究的热点和焦点，一批用于知识发现系统 被开发出来，在商业、经济、金融、管理等领域都取得了应用性的成果。 国际知识发现研究知名学者加拿大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 ! ”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 2 概念格的研究现状 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 系统l ”j ， 它首先根据属性构造出概念格，然后从格中提取出分类规则用于支持对象 的分类；n j i w o u a 等设计的l e g a l e 系统使用学习参数来生成半格概 念格的一部分f j 3 l ，从而有效地控制了概念格的空间复杂性，然后采用投票 的方式对新对象的分类进行群体决策。 g o d i n 等描述了基于概念格模型的概念形成方法l j 矾，主要提出了从概 念格中提取出蕴涵规则的算法，并使用了关系数掘库中函数依赖的理论结 果来处理规则的蕴含问题，但是这种蕴涵规则是一种确定性规则，不具备 描述概率规则的能力和抗噪音能力。为了提高规则发现的鲁棒性进行了扩 展，提出了从概念格中提取近似规则( 又称为概率蕴涵规则) 的算法。 p a s q l l i e r 等研究了关联规则的提取问题【1 7 l ，他们的工作是以己经发现了 所有的频繁项集作为基础的，提出了用于提取确定性关联规则的 d e q u e n n e g u i g l l e 基，以及用于近似关联规则的适当基和结构基。 2 辽宁科技大学硕士论文第一章绪论 h o t b 研究了基于概念格的概念聚类方法【l “，并实现了一些学习系统， 包括o s h a m 和i n c 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 教授认为在有些时候仅考虑一个形式背景是不足够的i i7 1 , 并指 出需要引入背景网络的形式方法，还提出了不同形式背景之问的四种不同 的操作：并置，下置，融合以及级连。以w i l l e 所提出的多背景为理论依 据，以不同形式背景的对象集和属性集之间的关系为基础，研究了在概念 格框架结构下对结构化( 复杂对象) 所进行的概念学习和规则提取，还对学 习所得到的概念和规则进行了解释。 1 2 3 发展趋势 2 0 0 2 年第l5 届欧洲人工智能委员会组成了形式概念分析在数据库中 的知识发现( f c a k d d ) i 作组，这个工作组的主要目的是带领那些数据分 析，机器学习等领域对概念格有兴趣的学者一起研究有关基于概念格的数 据挖掘的算法、概念格的剪枝、概念格的构造、不同类型数据的概念格在 实践中的应用等等。在会议上他们提出了以下几个问题供研究讨论： 1 利用概念格理论来形式化k d d 任务。 2 基于概念格的有效的知识挖掘方法。 3 建格算法的可靠性和复杂性。 4 概念格的构造和剪枝。 5 格尺寸的约简，包括近似值，扩充，不可约简元素等等。 6 概念格的注释和它的结构。 7 冰山概念格。 8 画格的算法。 9 不同类型的数据概念格的应用。 1 0 基于概念格的知识表示和模式。 1 1 概念格在真实世界中的应用。 1 2 k d d 的哲学基础。 这1 2 个方面正是涵盖了概念格理论本身及在k d d 中的应用研究的主 辽宁科技戈学硕士论文 第一章绪论 要方向。2 0 0 4 年召开的第二届f c a k d d 会议，会议上讨论的论文也正是体 现人们在这几年罩在这个领域取得的成就。随着人们逐渐对形式背景及其 概念格的迸一步了解，对其理论有了更深一层的认知，会逐渐认识到它在 社会各个领域的作用。随着对它的研究及应用的进一步深入，它的优势也 会一步步豹展现出来，因此这个领域的研究j j 景是非常广阔的。 1 3 本文取得的研究成果 在认真学习研究大量文献资料的基础上，取得了如下的一些研究成 果： 概念格是进行数据分析有力的工具，快速有效地构造概念格对于以后 的分析起着极其重要的作用。通过对当前多种构造算法的仔细研究与比 较，结合其各自的优点，提出了一种新的概念格构造算法：在空间复杂度 增加不大的前提下，动态形成剪枝条件，避免概念格构造过程中无效闭包 的生成。实验证明，该算法快捷高效。 大型复杂的概念格在分析时比较费力，这就需要对其进行分解。在详 细介绍当前两种概念格分布计算的思想后，指出了它们的不足之处，然后 基于闭包系统分解的思想，对概念格闭包系统进行划分，提出了一种全新 分治策略来分布构造概念格，进行并行计算。该算法对原有概念格分解后 不会造成信息的增减，减小概念计算的搜索空间。对相关定理加以证明后 并用实验证明陔算法的可行住和高效性。 在k d d 中，概念格在关联规则的提取方面应用得最多，而提取关联规 则必不可少的一步就是求全部的频繁项集。本文从概念格的分布处理出 发，提出一个基于概念格闭包系统划分的关联规则挖掘算法，用分治的思 想来缓解关联规则提取的瓶颈问题。该算法以划分闭包系统为基础，以保 持原有信息不变为根本，对事务数据库进行拆分，在每个子事务数据库内 进行频繁项集的计算，实例证明，该算法的效果明显。 概念之问的关系是有序的，通过所对应的h a s s e 图，可以形象地揭示 概念间的泛化和特化关系，反映概念间的层次结构。然而在生成每个概念 前对形式背景中的对象集合的每个元素或属性集合的每个元素在未规 定字典序f ； ，是不可比的，本文从这一点着手，把概念视为形式背景中的 最大“矩形”，研究了概念格中概念信息的图形化，用之于概念格中相关 定理的图形化证明。 对手写数字串的识别首要的一个任务就是要把数字串拆分成单个数 字，本文基于类的划分，把聚类分析的思想应用于数字串的拆分。 4 辽宁科技大学硕士论文 第一章绪论 1 4 本文的组织结构 全文共分为七章，其组织结构如下： 第一章绪论。叙述了课题的研究背景和意义，国内外研究现状、发 展趋势及本文所取得的研究成果和组织结构。 第二章形式概念分析理论综述。首先介绍了形式概念分析理论基础 的格理论的一些基本知识，如偏序集，完全格，伽罗华连接等概念；然后 介绍了形式概念分析理论中的一些概念和定理，如形式背景，形式概念及 概念格等的相关概念和定理，最后介绍了一下代表性的非经典概念格。 第三章概念格构造算法的研究。首先介绍了形式背景相应的概念格 的构造算法；在此基础上，结合已有算法各自的特点，提出了一种新的概 念格快速生成算法，在空间复杂度增加不大的情况下，通过对概念生成过 程中节点的讨论，采取相应措施，减少了无效节点闭包的运算次数，对概 念树进行了有效的剪枝，降低了部分情况下的时间复杂度，提高了概念格 的构造效率。并用实验对算法进行了比较，验证了本文算法的高效性。 第四章概念格并行构造算法研究。首先详细总结了当前概念格的分 布处理的两种思想，分别介绍其基本原理，然后基于偏序集上闭包系统分 解为多个子闭包系统的思想，也采用分治策略，对闭包系统划分为子闭包 系统的判定定理进行了证明，提出了一个新的概念格分布处理算法。试验 表明，该算法和直接用形式背景来构造概念格的算法相比，效果显著。 第五章基于概念格分布处理的规则发现研究。首先介绍了数据挖掘 产生的背景，数据挖掘的主要过程及功能：接着介绍了数据挖掘历面临的 主要问题，基于概念格并行构造这个框架，提出一种新的解决办法，即基 于闭包系统划分的分布式数据挖掘，并就此建立并行分布式数据挖掘的体 系结构；通过建立分布式概念格的数学模型，来解决并行分布式数据挖掘 中的并行处理问题。 第六章概念信息的图形化描述及相关定理图形化证明。概念格是一 种二元关系，描述了对象和特征之间的联系，概念格所对应的h a s s e 形象 地揭示了概念间的泛化和特化关系，反映出一种概念层次结构、概念之间 是有序关系的：然而对于同一个形式背景而言，构造的概念格是唯一的， 即不受数据或属性排列次序的影响。本章基于概念信息的图形化特点。对 概念的图形化研究做了一点尝试，并用得出的结论对建格算法中使用的定 理进行了证明。 辽宁科技大学硕士论文第一章绪论 第七章总结。总结了本文的创新性成果，介绍了本课题需要进一步 深入研究的热点方向。 附 录基于聚类分析的数字串拆分。简要介绍该方法的基本原理、 运行步骤和实验效果。 6 辽宁科技大学硕士论文 第二章形式概念分析理论综述 第二章形式概念分析理论综述 2 1 什么是形式概念 什么是形式概念? 这是进行形式概念分析理论及其应用研究首先应 该解决的问题。本文从如下两个角度去理解形式概念分的含义，进而理解 形式概念分析要解决的主要任务。 首先，从数学的角度理解形式概念分析。对于任意两个集合之间的某 种二元关系r ，形式概念分析提供了一个与r 一一对应的、无冗余的格对r 进行可视化，从而提供了一种一般的分析二元关系的数学方法。 形式概念分析理论是基于g a r r e tb i r k h o f f 的格理论建立起来的 3 ，其 基本思想是：对于任意给定的两个集合，考查任意一个在这两个集合之间 的二元关系，通过给出一个在集合的幂集之间的一个g a l o i s 连接，可以得 到一个新的集合，进一步可以得到一个半序集，b i r k h o f f 证明了这个半序 集是一个完备格；另一方面，根据这个完备格，认可以得到原来的二元关 系。因此，由形式概念分析得到的结果结构话地描述了原有的二元关系。 其次，从哲学的角度理解形式概念分析。哲学中，概念被理解为由外 延和内涵两个部分组成的思想单元。任何一个概念都是在某一个特定的背 景环境下建立起来的，这个环境中的某些子集构成了概念的外延，同时在 这个环境下考察的所有特性的某个子集构成这个概念的内涵；内涵是在外 延中的所有个体在这个环境中所有的共性，同时外延是内涵中的所有特性 在这个环境中的所有的共例。同一个环境中可能会产生有多个不同的概 念。这些概念都是从一个最大的、“包罗万象”的概念通过加入对某些特 性的考虑得到的。显然，在这个背景环境中，概念的内涵越丰富，这个概 念的外延就越小，因此概念不断特化的最终结果一定是所有的概念归结到 一个“具有所有的属性”的、最小的概念中来，这个最小的概念可能在这 个环境下没有任何实例。上述思想给我们的一个启示是：各学科、各技术 之间总会存在某种联系、或是相似性，从而使不同学科、不同技术之间的 互相借鉴成为可能，同时也说明了交叉学科存在的可能性。 形式概念分析分别对考察的背景环境、该环境下的概念、及概念之间 的关系等进行了形式化的描述，并使用概念格来描述这一形式化过程的结 果。同时概念格也是本体论的重要表示方法之一；概念格的生成过程体现 辽宁科技大学硕士论文第二章形式概念分析理论综述 了本体论的查找过程。 总之，形式概念分析提供了对二元关系的结构化描述，是一种一般的 分析二元关系的数学方法，其核心数据结构一一概念格，是一种重要的知 识表示方法。 德国的r w i l l e 教授于1 9 8 2 年发表了一篇有关概念格理论的文章，其 中第一次提出了形式概念分析理论( f c a ) ，反映了概念的哲学理解，用其 核心数据结构中的节点来表示概念，准确而简洁地描述了概念i 日j 的层次关 系。随着研究的深入，f c a 已经成为一种重要的知识表示方法，成为处理 和组织大规模数据的有效工具，被看成是概念知识处理( c k p ) 的数学框 架，概念知识处理是属于计算机科学领域的一种理论，它的目的是提供方 法和工具用于获取、推理和表示知识，使得这些过程和人类实现交互式的 沟通。形式概念分析理论f 以其独特的优势吸引着越来越多计算机科学领 域研究人员的注意，它已经从原来单一的数学领域发展到了计算机科学领 域。 本章将介绍形式概念分析理论的一些基本知识，由于形式概念分析理 论涉及到有关格序理论的一些知识，所以本章首先给出了序理论的一些基 本定义，然后给出了形式概念分析理论中的核心数据结构一一概念格的相 关概念和定理，最后介绍了一些典型的非经典概念格。 2 2 序和格的基本理论 2 2 1 偏序集 定义2 1集合x 与y 之间的二元关系r 是有序二元组( x ，y ) 的集合， 其中x x ，y ey ，即r 量x ，这罩的是笛卡尔积，( x ，y ) r ，也常写 作x r y 。如果x = y ，则称尺定义在x 上。还用r 。表示r 的逆关系。即： r 一= ( y ，x ) j i g , y ) er 。 定义2 2如果定义在集合肘上的一个二元关系s ，对于所有的元素 _ r ，y ，z m ，满足下列条件，那么二元关系称为肘上的偏序关系： x s x ( 自反性) x y 且y s 工工= y ( 反对称性) 工s y 且y z x sz ( 传递性) 有偏序关系s 的集合肼被表示为( m ，) ，被称为偏序集。 8 辽宁科技大学硬士论文第z - 章形式概念分析理论综述 任意集合x 的所有子集的集合( 幂集) v ( x 1 以元素集合势的大小关 系为偏序关系，是偏序集。实数集合r ，以通常的关系为偏序关系，则 f r ，s ) 是一个偏序集。 定义2 3 设肘是一个偏序集，如果a s 6 且a 手b ，则记4 t b 。如果4 6 ， 且不存在满足口c c t 6 的元素c ( a ，b ，c e p ) ，那么称口为b 的一个下近邻，b 是 口的一个上近邻，写作口 b 。 定义2 4 设p 是一个偏序集，有q p 。q 是一个序理想，如果只要 有x e q ，y e p 和y s 工总有y e q 。对偶地，q 是一个序过滤，如果只要有 x q ，y e p 和x y 总有y q 。 定义2 5 设尸是一个偏序集，x ，y e p ，由x 到y 的一个长度为n 的极 大链是序列x = 砭 _ a ( t a ) ( 函爿2 9 4 v a = v ( v 4 ) ；彳2 等4 = a a = 全( 八4 ) ； 定义2 1 0 设x 是集合，工是x 的子集簇，若对集合的任意交封闭 v i j ，4 三0 4 l 则称三是( x 上的) 一个闭包系统，集族上中的元素称为闭集。 给定任意子集a x ，集合n b 三 卅量b ，容易看出，这是l 中包含a 的最小集合，称为a 的闭包。 定理2 2 如果u 是g 上的一个闭包系统，那么仍，x - n 爿u i x a 定义了一个g 上的闭包算子。反之，闭包算子驴的所有像的集合 = 妒鼻j g 卜一定是一个闭包系统。 定义2 1 1 两个半序集( m 。，) 和( m 2 ，) 的( 直接) 积定义为半序集 ( x m 2 ，s ) ，满足( 五，x 2 ) ( y l ，y 2 ) 营而j ，i 而且心- y 2 。 可以将这个定义推广到任意数量半序集的乘积：如果r 是一个索引集， 而且( m ，) ，f t 是半序集，那么 0 辽宁科技大学硕士论文 第二章形式概念分析理论综述 x ( m ，s ) 一f 肼，l ，满足( ) 。s ( 只) 。一s y , ，v t e t 。 t e t、f 日 2 2 2 完全格 定义2 1 2 设偏序集p = ( p ，s ) ，如果任意x ，y p 总满足上确界工v y e p 且下确界x y e p ，那么偏序集p t ( p ，s ) 是一个格。如果对于p 的任意一个 子集x ，总是存在上确界v x 和下确界a x 的话，那么称p 是完全格。每 个完全格p 都有一个最大元素v p ，称其为格的单位元，用1 ，表示。对偶 地，最小元素0 ，称为零元。 如果对p 中的元素都定义了上确界和下确界运算，那么可以由这些运 算来重新建立序关系，即x s y 。x z y xv y = y 。如果丁是一个索引 集，且x k l f r ) 是p 的一个子集，那么也可以用￥t 来代替v x ，用全t 来代替八x 。 上确界和下确界运算满足结合律，即x ( y z ) 一扛一y ) z 和 x v ( yv z ) - ( x v y ) vz ，如果 置i t s ： ) 是p 的子集的集合，那么这两个结合 律的特殊情况能被推广为： ￥( v 墨) = v ( g 置) 而且对偶地有全( 八五) 一a ( g 墨) 。 定义2 1 3 一个完全格被称作为分配的，如果分配规则 x ( ) ，vz ) - ( x ) ，) v b z ) 和x v ( y a , z ) 一仁v y ) 一o v z ) 对于所有的y ，z e l 成立。 定义2 1 4 一个偏序集( p ；s ) 被称为一个并半格( 交半格) ，如果p 的任 何子集s 的上确界( 下确界) 存在。 定义2 1 5 格l 的一个非空子集肘被称为的一个子格，如果口，b e m 有av b e m 和aa 6 m 。 定义2 1 6 设l 是一个格。一个元素x 是并不可约的，如果对于所有 的4 ，b e l ，a 工和b c x ，都有av b 工。对偶地可定义交不可约。用j ( ) 表 示的并不可约元素的集合，用肘( ) 表示的交不可约元素的集合。 零元的上近邻( 如果它们存在，被称为原子) 总是并不可约的，单位 元的下近邻( 称为伴同原子) 总是交不可约的。 定义2 1 7 一个集合p l 被称为中并稠密或上确界稠密，如果对于 辽宁科技大学硕士论文第二章形式概念分析理论综述 每个a l 存在a p 满足a = v a ；对偶地，它是交稠密或下确界稠密，如 果对于每个a l 存在a p 满足口= 八a 。 设是一个有限格。每个上中的上确界稠密子集包含所有的并不可约 元素，每个下确界稠密子集包含所有的交不可约元素。集合j ( l 1 是上确界 稠密，m ( l 1 是下确界稠密。因此，每个中的元素是并不可约元素的并， 也是交不可约元素的交。对于所有的a l ，a = v x j ( l ) l x s a ，且对于 所有的d l ，a = a x m ( l ) i a s x 。 定义2 1 8 设两个完全格m 和之间的一个映射舻：m 一，如果 v x m ，都满足妒( v x ) = v c o ( x ) ，那么称妒为保上确界映射，也称其为v 射。对偶地，如果跗至m ，都满足o , ( a x ) = a q , ( x ) ，那么称妒为保下确界 映射，也称其为八射。如果舻既是保上确界映射又是保下确界映射，那么 称妒是完全格同态或完全同态。 每个保上确界映射，特别是每个完全同念都一定是保序映射。反之， 任何一个完全格之阳j 的序同构就必然是一个格同构，即，一个双射的完全 同态。 2 2 3 伽罗华连接 定义2 1 9 设p 和q 两个偏序集， 两个偏序集之间的一个伽罗华连接， p ls p 2 等印i ( o p 2 q l q 2 熠i 螂2 p sg , q o p 且q ( p l f f q 有映射妒：p 呻q 和：q 斗p 被称作这 如果这对映射满足： 这两个映射是互相对偶伴随的。 定理2 3 一对映射( 妒，p ) 是伽罗华连接当且仅当：p q j q q 印 2 3 形式概念分析理论的相关概念和定理 定义2 2 0 形式背景是三元组k = ( g ，m ，i ) ，由集合g 、集合m 和它们 阃的关系，组成。其中g g 中元素称为对象。g 是对象的集合，胁m 中 元素称为属性，m 是属性的集合。 定义2 2 1 对于一个对象集合x g ，定义x = 埘m i v g x ，g l m ， 相应地，对于一个属性集合y 肼，定义y = g g i v m y ，g l m a 定义2 2 2 形式背景k = ( g ，m ，i ) 的一个形式概念是( x ，y ) ，其中 1 2 辽宁科技太学硕士论文 第二章形式概念分析理论综述 x c _ g ，y c _ m ，且满足z = l ，和y ，。z 。对于一个对象g e g ，那么g l n , 就 表示对象占具有属性m 。称x 是形式概念( x ，y ) 的外延，y 是形式概念( j ，y ) 的内涵，c l ( 或c ( c ，m ，) ) 表示背景k 的所有概念的集合，c ：、碟是 背景k 的所有概念的外延、内涵的集合。 定义2 2 3 形式背景定一( g ，m ，j ) ，如果任意满足 函 = 占： 的任何两个 元素，9 2 ，g ：g 都有g 。= g ：，而且对偶的任意两个满足 ) = ) 的元素 ，1 1 ，研：掰，都有g l g ：，则称形式背景k 是净化的。 定义2 2 4 净化形式背景k t ( g ，m ，) ，给定集合x c _ m ，属性聊岳x ， 但扣 乍j ，称臃产生的属性概念( 所) ， 所 ”) 是 一可约的属性概念。这样 的属性是可以删除的。对偶她，给定集合x c _ g ，对象g 譬g ，但任 。g 7 ， 称g 产生的属性概念 话 。， g 是v 一可约的对象概念。这样的对象是可以 删除的。如果每个属性概念都是八一不可约的，每个对象概念都是v 不可 约的，则称此背景k 是约简的。 定理2 4 设k - ( g ，m ，) 是一个背景，石，x 1 ，五_ c g 是对象的集合， y ，x ，k c m 是属性的集合，那么下列式子成立： x i c _ x ：一z ：，k 艺一x ( 参z 石，l ，尘y x x ”，y ；y ” x c _ y y x x x y z 任意数量的外延( 内涵) 的交集总是一个外延( 内涵) 。下面的式子成立 ( 岩x 一口x ，( 吕_ ) ，一2 匕 定义2 2 5 如果( 置，k ) 和( x ：，k ) 是k = ( g ，m ，) 中的两个概念，如果 x - x ：( 等价表述x 2 k ) ，那么称( 置，k ) 是( ：，k ) 的子概念，或( 以，e ) 是 ( x ，x ) 的超概念( 双亲概念或父概念) ，并记作( x 。，k ) s ( x ：，k ) 。也称( ，k ) 小于( 或更详细于) ( x ：，e ) ，或( x ：，k ) 大于( 或更一般于) ( 墨，k ) 。关系 s 称为是概念的层次序( 或者简称为序) 。偏序集l ( g ，m ，；) 称为背景 辽宁科技大学硕士论文第二章形式概念分析理论综述 k = ( g ，m ，) 的概念格( 或伽罗华格) a 定理2 5 背景k = ( g ，m ，) 的概念格l ( c ，m ，；) ( z ( x ) ) 是一个完全 格，其概念上确界和下确界分别如下式所示： 厂一、 x ( _ ，r ) 2 u x 川n y ， 企( _ ，r ) = f o - ，( 昌r ) ) 定义2 2 6 一个对象g g 的对象概念是概念( ，g 。) ，这罩g 是g 的对 象内涵 m mj g l m ) 。g 的对象概念被表示为，( g ) ，是外延包含g 的最小概 念。相应地，( m 7 ，m 。) 是一个属性m m 的属性概念，m 是m 的属性外延 g g i g l m 。脚的属性概念被表示为u ( m ) ，是内涵包含m 的最小概念。g 的对象概念和研的属性概念也用下面的表达式描述： ，( g ) = 八 ( x ，j ，) e c ( 6 ，m ，) l g x ，u ( m ) = v ( x ，y ) c ( g ，m ，) i m ey 。 2 4 概念格扩展研究介绍 概念格是极其重要的用于数据分析的工具，近些年来国内外学者对其 结构和特点作了深入的研究，在它的基础上根据不同的需求对它进行改 进，提出了几种新型的概念格，包括扩展概念格，约简概念格，量化概念 格，广义概念格，r o u g h 概念格，模糊概念格等等。这些概念格都有它们 自身的优点，下面我们简单介绍一下其中一些非经典概念格的基础定义和 主要特点。 2 4 1 扩展概念格 利用概念格提取关联规则，分类规则等是概念格的重要应用之一。为 了更加快速有效的提取规则，合肥工业大学胡学钢等人提出了扩展概念格 的概念格构造形式。 定义2 2 7 设( a ，b ) 是形式背景k = ( g ，m ，) 的一个一般概念，如果存在 b i ( 爿) 且g ( 局) = a ，则称b i 为b 的一个等价属性组，简称等价组，用 e q u ( a 1 表示a 的所有的等价组组成的等价簇，即 e q u (