（计算机应用技术专业论文）形式概念分析理论的研究及其在数据挖掘中的应用.pdf

鞍山科技大学硕士论文 摘要 摘要 在过去的数十年中，我t 1 产生和收集数据的能力已经迅速提高。此外， 作为全球信息系统的万维网的流行，已经将我们淹没在数据和信息的汪洋 大海中，并且迫切需要将这些数据转换成有用的信息和知识。数据库知识 发现是从大量数据中提取有效的、新颖的、有潜在作用的、可信的、并能 最终被人理解的模式的处理过程。概念格是近年来获得飞速发展的数据分 析的有利工具，用来发现数据中隐藏的知识模式。因此，研究概念格的基 本理论以及将其应用于知识发现有着非常重要的意义。本文在以下几方面 做了深入的研究并且取得了创新性的成果。 ( 1 ) 生成概念和概念格是形式概念分析中的必要工作，本文列举了一些 经典的渐进式概念格生成算法，包括基于对象和基于属性的算法。最后作 者提出了一种新的基于属性的渐进式递归算法，并用实验证明了该算法的 高效性。 ( 2 ) 发现频繁项集是数据挖掘中最重要的工作之一，本文在介绍了几种 挖掘策略后，作者提出一种基于属性分组的频繁项集挖掘算法，其挖掘策 略与前两种有所不同，与a p r i o r i 算法的实验比较说明该算法对于大型数据 库是非常有效的。 ( 3 ) 一个形式背景中形式概念的个数是随背景的大小而指数级增长的， 因而背景稍大概念的数目就非常多。对他们的处理、存储及传输就十分困 难。本文提出了一种全新的基于粒计算的概念格分解与合成的方法。 ( 4 ) r o u g h 集理论与形式概念分析的结合是当今十分热门的话题，本文 将介绍用f c a 来解决r o u g h 集理论中的一个核心问题一属性值约简的方 法。另外，文中还给出了利用上下箭头关系约简形式背景的方法，以便能 够快速的构造概念格。 关键词：形式背景，概念格，频繁项集，粗糙集，知识发现 蔓坐翌茎查兰璺主垒壅 茎盔塑墨 a b s t r a c t o u rc a p a b i l i t i e so fb o t hg e n e r a t i n ga n dc o l l e c t i n gd a t ah a v e b e e ni n c r e a s i n g r a p i d l yi nt h el a s ts e v e r a ld e c a d e s i na d d i t i o n ，p o p u l a ru s e o ft h ew o r l dw i d e w e ba sag l o b a li n f o r m a t i o ns y s t e mh a sf l o o d e du sw i t hat r e m e n d o u sa m o u n t o fd a t aa n di n f o r m a t i o n t h e r ei si m m i n e n tn e e dt ot u r ns u c hd a t ai n t ou s e f u l i n f o r m a t i o na n dk n o w l e d g e k n o w l e d g ed i s c o v e r yi nd a t a b a s ei st h en o n t r i v i a l p r o c e s s o f i d e n t i l y i n gv a l i d ，n o v e l ，p o t e n t i a l l y u s e f u la n d u l t i m a t e l y u n d e r s t a n d a b l ep a t t e r n si nd a t a c o n c e p tl a t t i c ei s ap o w e r f u lt o o lf o rd a t a a n a l y s i s ，u s e d t oe x t r a c th i d d e nk n o w l e d g ep a t t e r ni nd a t a t h e r e f o r e ， s t u d y i n gt h eb a s i ct h e o r yo fc o n c e p tl a t t i c e a n da p p l i e di ti nk n o w l e d g e d i s c o v e r yh a v ei 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 sf o c u s e so nt h ef o l l o w i n g a s p e c t sa n dh a so b t a i n e dt h ec r e a t i v er e s e a r c hr e s u l t s ( 1 ) t h eg e n e r a t i o no fc o n c e p t sa n dc o n c e p tl a t t i c e si s a ne s s e n t i a lt a s k f o rf o r m a lc o n c e p ta n a l y s i s t h i st h e s i ss h o w ss e v e r a lt r a d i t i o n a la l g o r i t h m s t h a ta r eb a s e do ni n s e r t i n go b j e c t sa n db a s e do ni n s e r t i n ga t t r i b u t e s i nt h el a s t ， t h i st h e s i sp r e s e n t san e wi n c r e m e n t a la l g o r i t h mc a l l e da t t r i b u t e b a s e df a s t i n c r e m e n t a lb u i l d i n ga l g o r i t h mo fc o n c e p tl a t t i c e r e s u l t so fe m p i r i c a lt e s t s a r eg i v e ni no r d e rt oc o m p a r et h ep e r f o r m a n c eo ft h ei n c r e m e n t a la l g o r i t h mt o t o wo t h e ra l g o r i t h m s ( 2 ) d i s c o v e r yf r e q u e n ti t e m s e t si so n eo ft h em o s ti m p o r t a n tt a s k si nd a t a m i n i n g a f t e rd i s c r i b i n gt h es t r a t e g yo fs e v e r a l n o t i c e a b l ea l g o r i t h m s ，t h i s t h e s i sp r o p o s e sa ne f f i c i e n ta l g o r i t h mo fm i n i n ga s s o c i a t i o nr u l e sb a s e do n d i v i d i n ga t t r i b u t e s ( a r m a b a ) t h i sm i n i n gs t r a t e g yi sd i f f e r e n tf r o mo t h e rt w o m e t h o d s e x p e r i m e n t sc o m p a r i n ga r m a b at oa no p t i m i z e dv e r s i o no fa p r i o r i s h o w e dt h a ta r m a b ai sv e r ye f f i c i e n tf o rm i n i n gl a r g ed a t a b a s e ( 3 ) s i n c el a t t i c e s c a ng r o we x p o n e n t i a l l yl a r g ew i t ht h ei n c r e a s i n g c o n t e x t ，i ft h ec o n t e x ti ss l i g h t l yl a r g e ，t h en u m b e ro ff o r m a lc o n c e p ti sv e r y b i g i ti ss od i f f i c u l tt od e a lw i t h ，s t o r ea n dt r a n s m i tw i t ht h e m t h i st h e s i s i n t r o d u c e sa na p p r o a c ht od e c o m p o s ea n dc o m p o s et h ec o n c e p tl a t t i c eb a s e d o ng r a n u l ec o m p u t i n g 鞍山科技大学硕士论文 英文摘要 ( 4 ) t h ec o n n e c t i o nb e t w e e nt h et h e o r i e so fr o u g hs e ta n df o r m a lc o n c e p t a n a l y s i si s av e r ya c t i v et o p i c c u r r e n t l y i nt h i st h e s i s ，w ew i l lu s ef o r m a l c o n c e p ta n a l y s i st os o l v et h em a i np r o b l e mi nt h er o u g hs e t t h ep r o b l e mo f a t t r i b u t ev a l u er e d u c t i o n ，i na d d i t i o n ，t h i st h e s i s a l s op r o p o s e saa p p r o a c h u s i n ga r r o wr e l a t i o nt or e d u c ef o r m a lc o n t e x tf o rb u i l d i n gc o n c e p tl a t t i c e r a p i d l y k e yw o r d s ：f o r m a lc o n t e x t , c o n c e p tl a t t i c e ，f r e q u e n ti t e m s e t s ，r o u g hs e t ， k n o w l e d g ed i s c o v e r y i i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得鞍山科技大学或其它教育机构的学位或证书而使用过的材料，与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 关于论文使用授权的说明 本人完全了解鞍山科技大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅：学校可以 公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文。 ( 保密的论文在解密后应遵守此规定) 签名：查z 凯导师签名： 马 七曼 日期：u 。；幻 鞍山科技大学硕士论文 第一章引言 1 1 。谋题的讲究背景 第一章5 引：言 矗s 擎聋手( ；瞽免：6 薄礼事磊的数癌库轻巢ji 荔遣兰率爹年耐爰庭苫饔液 ，、v n ：二， 、 。，t 。，、：i ! j 、o，、?4：，、-f ，1 p0 3f ，：1j i ： 为计算机信息素统与应再素统附核一i l 技术莉重要基础。近宰来，随着钎算、 机技未的发展_ 及：应用的普1 及，数据处理在计算机应用中所占比重的上升：一 。i ，；! 。1 ，、? ：_ _ ：；+ ! 。? 、i ：r ：jp j j ：1 i ：、 。： 1 + ? ：；一- j + ，。? ：。 一：、t j t 扣；l ? ，一u ，一：。2 - 数据库技术得到了迅猛的发展。随着衽会各领域中信息酌数字化，特别是 t、i 一i 11 、o i ? ；。二“t “： i “r ：t 】，：、 电子商务等失数据量业务的发展，数据库技术及网络通讯己成为重要的基 、。j l “i f ；- 、! ，jr + ，；、! i !。c - ：、：- ：? ：“，+ ：一- ? ，： 础领域，、许多领域己离不开这两个基本手段。事实上，“由于现代技术的发 庭，崔；献美获：菽蓿意爵菇。岛头买甜越：谧￥矗_ 年来：火锅莉甬猪意。菝米叠 声莉趣羹数。杀的蘸另+ 芙痞凌建篙， 、凳薮个薮杀锋被角j 手高韭管趋j ：蔹府 公、科学研究和工程开发等，这一势头仍将持续发展下去。煮遗1 薇纛芝亮 信息爆炸的时代，信息过量几乎成为人人需要面对的鲤曼。警碧熙鼗孥尹尹 隐藏着许多重要的信息，人们希望能够进行更高层次的分析，以便更好地 刊用这些数埋? j 县剪的数据库零莓曩以巽_ 毒效地、实现数据的录入、耷询、 每吨筹功。镌 但莠娑发现数提中存耷的：巷系和摆则_ 君鹫根蔫搏有的数据 预：测毒毒- 螅鹫羼稗羚：? 哮乏坞每墼辫莺：后隐藏的知识的手段，导致了。“数 埚垮害# 粤翘识，楚乏。? ! 斡毋萋? ；：_ j 以前人们采用传统的基于统计学原理的数据分析技术对数据进行处 理，而这种人工方法对于现在存储的海量数据处理起来显然力雨从心。j 那 么就迫切的霞要一种借助于计算机系统来自动分析和处理隐藏在海量数 据背后有用佶凰的方法和技术。，在由信息时代向知 谚 时代过渡的历史：条件 下： 在巨大的商业利益驱动币，；知识发现( k d d ) 的崭新研瑰领域诞生了。 数据挖掘( d a t am i n i n g ) 就是从大量的、。不完全的、0 j 有噪芦酌i 。模糊的、随 机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的 鞍山科技大学硕士论文第一章射言 信息和知识的过程。 在哲学中，概念被理解为由外延和内：涵两衾部分所组成的思想单元。 基于概念的这一哲学理解，德国的w i l l e 教授于1 9 8 2 年提出了形式概念分 析这一理论“】，用于概念的发现、排序和显示。自从形式橛念分析被提出 、i ，! t “ 一，；t 以后，形式概念分析及其概念格已经被证明是进行知识发现和数据分析的 有效工具。概念格的每个结点被称为是一个概念，由两部分组成：概念的 外延和内涵。概念的外延表示为属于这个概念的所有对象的集合，而概念 的内涵表示所有这些对象共有的属性的集合。概念格及其h a s s e 图体现了 内涵与外延的统一，表明了概念问泛化和特化的关系。作为形式概念分析 核心数据结构的概念格是进行提取规则知识的一个很好的平台，而生成概 、5， t 念格的过程就是概念聚类的过程。国内外很多专家已经在研究如何运用概 念格结构以便进行快速、高效的挖掘知识。作为数据分析和知识处理的形 式化工具，概念格已被广泛的应用于软件工程、知识工程、数据挖掘和信 息检索等领域 2 - 6 1 。 1 2 国内外研究现状 形式概念分析是1 9 8 2 年由w i l l e 教授提出的，当初仅仅是作为一种数 学格理论。由于概念格特殊的表现形式和广泛的应用空间，经过多年的发 展，许多领域专家将形式概念分析引入到相关领域，形式概念分析在许多 领域得到了应用。目前国内外学者对于形式概念分析的研究主要集中在几 个方面： ( 1 ) 概念格的建造： 概念格的建造对于后期的知识表示和规则提取是至关重要的，而概念 格的变化往往是呈指数级增长的，所以很多专家学者致力于发现一种快 速、高效的建格算法。概念格的建格算法分成两类：批处理算法和增量算 法。批处理算法根据构造格的不同方式可分3 类，即从顶向上算法，自底 向上算法，枚举算法。从顶向下算法首先构造格的最上层节点，再逐渐往 鞍山科技大学硕士论文 第一章引言 下，t 例如b 6 r d h t 的算法i ? d s h a m 算法 8 1 ；“自底向上算法则相反首先；、 构造底部的节谯，再向上扩展k4 如- c h e i h 的算法一9 l ：c ，枚举算法则是按照贯， 定顺序枚举格的所有节浦；，! 然后每生成j h a s s e 图，唧各节晦之间的关系；，1 i 如：g a z i t e r 算法0 9 i ，j n o i i f i n e 算法! 等：。、增量算法的思想是将当前要插入的j ： 对t 象和、格：中所有概- 念相。交，根据交的1 结果采。取不同的行动，主要唷 g o d i n ( ”】，c a p i n e l ：o t 1 2 1 和：t j b , ：h 6 t ”1 的算法。i j a d d i n t e n t j 算法：4 1 是丢种新的队二 递归的方式来渐进生：成格的算法它得优势是减少i 节点的 比较j 次数、还 有针对概念，格的叠置和并置情况的构造算法卅i ：概念格的并行构造算法 等? 7 1 ：另外j + 国内卜些专家也提出了_ j 些快速算法。如李云等提出了基于 属性的概念格渐进式生成算法；谢志鹏、刘宗田等提出了i 基于树状组织；j 的概念格快速渐进式生成算祛( t 9 1 ，j 对于分布式存储和并行处理等情况李- 云、刘宗田等提出了多概念格j 的横向合并算法删，邹先霞等提出：了 种基“ 于粗糙集理论的概念格构造方法 2 1 1 等。；：- ij ：t ：、：“一；2 ：2j “j ；：! ( 2 ) 概念格的简化及扩广： ：-e p r ；：， 对于大型数据库而言；仅仅靠。种快速的概念格生成算法是：不够的， 而人们往往只对支持度大于某一闽值的知识感兴趣；、这对于生成整。个概念 格无疑是一种资源浪费。g e r i l 提出了? 冰山概念格黝的概念 2 2 1 ，t 冰：山概 念格是一个概念聚类方法；，非常适合于大型数据库。它们也作为频繁项集 的浓缩表示：以用来计算关联规则、i 冰山概念格只显示整个概念格的上面部一 分，即只显示支持度：大于指定词值的概念各节点i ：概念格是极其重要r 的用 于数据分析的正具，- 近些年来国内j 外：学。者对其结构和特点作了深入的研， 究，在它、的基础止根据不同的需求对它进行改进提出了几种新型的概念 格，包括模糊概念格l 玎j ，扩展概念格( 2 4 1 ，约简概念格【2 5 】，量化概念格卿，5 加权概念格，等。这些扩广的概念格结构对于特殊领域体现了强大的应 用价值。 童；! ! 。t ：+ 0 置：二，； ( 3 ) 规则提取及相关系统： t ，：+ ；j f 。： 4 ：! 一 j i i oj i一，。 g o d i n 提出了一种增量式概念格建造方法呻】，并在此基础上提出在概 ， 1 ：i j ：、 ：r ，o ；1 ： ： 、；： 念格上提取蕴含规则的算法。其基本思路是系统生成当前节点的所在幂 3 ： 鞍山科技大学硕士论文第一章引言 集；并检查其。是否包含在其父节点中，若没霄则生成该集合为前件的规则。 s a h m n i 开发的r u l e a r n e r 系统i ，它首先根据属性构造出概念格，然后 从格中提取出分类规则用于支持对象的分类。h o t b 研究了基于概念格的 概念聚类方法1 1 3 1 ，并实现了一些学习系统，包括o s h a m 和i n c o s h a m 。 t o s c a n a 系统是w i l l e 所在研究所发展的一个基于概念格的数据分析系 统，该系统的特别老处在于它能对现有的概念格韵：某个概念进行进一步求 精，而获得个嵌。套的概念格。国内也有很多专家提出了许多规则提取算 法，如胡可云、王志海等提出的在概念格上提取分类和关联规则的集成算 法印1 和概念格上规则提取的一般算法与渐进式算法1 3 0 。该算法使用改进的 b o r d a t 建格算法作为基础。和其他算法不同，该算法在建格时将决策属性 和其他属性同样对待，并从格上生成具有任意指定后件的分类或关联规 则：梁吉业等提出了基于概念格的规则产生集挖掘算法】。谢志鹏，刘宗 田等也提出了基于概念格的关联规则发现”2 3 ”。 ( 4 ) 概念格与r o u g h 集的结合： 这方面也是最近比较热门的研究领域。粗糙集理论是波兰科学院院士 z p a w l a k 教授于1 9 8 2 年提出的弹，多年来人们一直试图将这两种理论结 合起来。1 9 9 3 年r e k e n t 首先研究了“粗糙概念分析” 3 5 1 ，1 9 9 6 年r e k e n t 又将这一理论进一步发展啡1 ，1 9 9 9 年j s a p u e r 及j s d e o g u n 等也进一步研 究了这些问题 3 7 1 ，2 0 0 4 年邹先霞等研究了基于粗糙集的概念格构造方法 ”，2 0 0 3 年王俊红等研讨了概念格与r o u g h 集之间的联系 3 8 1 。2 0 0 4 年 y y y a o 对这两种理论做了更深刻的比较研究 3 9 1 ，还研究了粗糙集中的形 式概念 4 0 1 及粗糙集在形式概念中的应用”，这两个上世纪末的重要理论的 结合迄今仍是人么关心的课题。 1 3 本文的内容组织 本文将着重讨论概念格的渐进式生成算法以及关联规则中频繁项集的 挖掘方法，并详细介绍了形式概念分析与r o u g h 集在数据约简方面的联系。 鞍山科技大学硕士论文 第_ 章引言 全文组织如下： 商 囊黛! ：i i 公薏：罨：、嚣轷晕- - - - - - - 袋, , , x 第一章引言，介绍了知识发现和形式概念分析的研究背景，国内外数 据挖掘和概念格理论的研究背景，利用概念格进行知识发现的研究现状以 i i ，：谢：j ：t 衙：“ “ ：。i ：、：卜n ：? j ：灯，。、1 ；i 弩夸考鸭冬。瓷慧搀f = j 叫：- ! k 1 。_ 一、。：e 、t ：刊t j i 二：小 。第 字形式撅盒分瓶咆碧诠基础j 本孝，盒钽万、席；警谂? k 形式蜒鸯禽蛳： 的基础理跄：；二多值背景和后面。耄节所用到的理论知识。? 门+ 。净 、t ：幔 i 磊兰章概念格渐进式蟹成算法，：本毒讨论i 了几种渐进式生成豫念格酌 彝谣，痒甜弄绍7 l 硅箕诵jd 6 d i ：算癌_ 。善于属催的概豁壁试算法j ，j 并在 此1 基础上提出了一种新的基于属性概念格的递归生成算法，最一给出几种 ；：i ! j f 1 ，。! f f - ： - ：tj j j 一 ”：，：”l ? ： ：f1 ”、，；j ：k 算法的实验比较，经过实验验证该算法是快速有效的。 第四章频繁项集挖掘，介绍了挖掘关联规则频繁项篝扎分痧法，：琏： 中包括传统的a p r i o r i 算法、利用概念格的封闭闭项集算法和作者提出的 一种新的利用矩阵存储信息的高效关联规则挖掘算法，最后，零中给i 出了 算法的实验比较。 螽孟毒薇惫捂躺分觯鸟各赢，兹式概念酾芬解与合成起形式概念分析 中一朱非常量蛰韫氟娄莳高运i 本章菇若了生# 鍪薪“孚扭钎蠡诵概 格分解与：9 感夸婆a：一。j ：。j ， i ! _ 、i s i 二 v 、第六章形式龌佥分析与r o u g h 寒中，的约苘! j ：介。绍了担糙集基础珲论、。： 形式概念分析。中形式背景的约简并首次描述了用概念格工具进彳亍j i 叩g 蛉 集中的值约简。 m i m 、 j 、：1 j ! 13 ：，认 。第毛t 誊缮莱。语，。本蔓薪毵 瘫崩绪知迸二步l 研、嵬方莳0 i ：j i i ? 巍，；， t ，l j o j ，璁! ； ；：j ：一。j 二， 鞍山科技大学硕士论文第二章形式概念分析理论基础 第二章形式概念分析理论基础 ， 自从w i l l e 教授首先提出形式概念分析以来，形式概念分析及其概念 格已经被证明是进行知识发现和数据分析的有效工具。概念格的每个结点 被称为是一个概念，由两部分组成：概念的外延和内涵。概念的外延表示 为属于这个概念的所有对象的集合，而概念的内涵表示所有这些对象共有 的属性的集合。概念格及其h a s s e 图体现了内涵与外延的统一，表明了概 念间泛化和特化的关系。形式概念分析理论正以其独特的优势吸引着越来 越多计算机科学领域研究人员的注意，它已经从原来单一的数学领域发展 到了许多其他的科学领域。 2 1 序理论基础 2 1 1 半序集 形式概念分析是基于数学的序理论的，特别是基于关于完全格的理论。 然而，本节我们将对一些相关的数学基础知识做回顾。然而由于篇幅所限， 我们只能对最重要的序理论方面的知识做简要介绍。 定义2 1 集合m 与之间的二元关系j r 是有序二元组( m ，n ) 的集合， 其中m 。m ，n n ，即r m n ，这里的是笛卡尔积，( m ，n ) r ，我 们也常写作m r n 。如果m = n ，则我们说r 定义在m 上。我们还用r 。表示 r 的逆关系。即：r = ( 玎，m ) i ( 1 r l ，h ) r ) 。 定义2 2 如果定义在集合m 上的个二元关系月，对于所有的元素 x ，y ，z m ，都满足下列条件的话，那么我们称r 是一个偏序关系( 或者简 称为序) ： ( 1 ) x r x ( 自反) ( 2 ) x r y 且y r x jx = y ( 反对称) ( 3 ) x r y 且y r z jx r z( 传递) 对于偏序关系r ，我们经常使用符号来表示( 对于r ，使用符号来表 示) ，如果x y 而且x y ，则我们写作x y 。一个集合m 及其上的序形 成的有序二元组( m ，) 称为半序集。 6 鞍山科技大学硕士论文第= 章形式概念分析理论基础 例2 1 设集合m 是某个集合x 的幂集2 。，若其j ；傅摩羲黍是曼罩s ；，c 当且仅当s 。s 2 ，则( 2 x , ) 是一个半序集。 + “1 、謇墨。2 、个专慝每m ，j 守；的覃食乖萝。誓妒：如罨或毒譬2 譬者 y ，x 之1 盛立尊， 餮z ，? 巷可电的，：虿则憨眷莓万；可，比的，。：棚嚣i 够，) 、t 够_ 食盂謇t 专的任腰毋誊謦乒鼍比嗨：则l 称蕊矿亍篝，为篝一徊另一食子集 中的售哽霉毒郝芦。不可些昀t 则骛警食子集为辈譬。，。i；： 定义2 4 两个半序集( m ，) 及( ，) 之间的映射伊：膨斗称为l 鳄 碍。的，、当对所氨尊声，：引m ；，、帮。声、，薯年甲令妒( z ) 等p 钳如孚1 9 再。滞足 ：j 。i ，、r 一：t 1 ：l - jl _ 、 t：。i 妒( x ) t p ( y ) x s y ，则称9 为序嵌入嗨：警时僻擎然是兽譬。食双射尊 序嵌入，称为( 序) 同构。 ：j 。，一。 j ，：蹙别莺枣：只毒双秽的序；謦全蕉鹱缳霉早同均，而双譬嗨、保置映射不 一定是同构要说明一个保序映射是同构，必须说明其逆映射存在，而且也 是保序的。 + 7 ，i - 一、， 。 + i 定义2 5 ，两个半序集( m ，) 及( m ：，) 的直接乘积( 简称直接积) 定义 卜l ；i1 i j - ：，：! i-i 一 一 t 。：。 为：背撑謇i m “x m 。z ? ) 。_ 这导弹! j m j 厅，的j ? 是9 ，i ：l 手( y ；y z ) ：篡：- 等? 母 x ：y ：，还可以将这个定义推广到任意多个半序集；如果r 是_ _ 1 _ 索引集， 、 一 ：lr-lj_，_ 、 + l+ 而且( m t ，) 孳蚩：雪拳( i r ) 掣j 鋈i 修，：等) ：= 答m j 宇，箨号，蚤m r 甲莳s 毛 ( r ，) j 昭等( _ ：，- ：) 一印警( v t f ：可) ( x rs 墨) ：? 叶j jy x 弋一屉伯甸 jj 声一： 0 一， ：f ， f ：，? ! ：j：! ： ? ： ，”t 三：。； ， + j ： 、图2 1 两个半序集的直积实例 ， 定义2 6 令( m ，) 是一个半序集，a 是吖的子集，m 中的元素一 个元素s 满足v a a 都有s ，口，则称s 是4 的_ 企下界。对偶她，若m 中的1 个元素s 满足v a 暑a 都有s a ，则称s 是a 的_ 个上界。如果一 的所焉下是组成印。集怠专真最杰秀誊，g ! 餮警岔季紊丸4 的忑确晷，田作： i n f 4 ，零a ? ，对强地? 士界集令凹最尘季誊憨为上确- ：界i 霹俘母写，一譬v 4 。 如果彳= x ，y ) ，则用工 y 来表示i n f 4 ，用x v y 来表示s u p 、爿。下确界和 上确界经常也称为交和并。 鞍山科技大学硕士论文 第二章形式概念分析理论基础 2 ：2 2 竞全格及相关性质 定义2 7 一个半序集v # ( v ，) ，如果y 中任两个元素x ，y 的上确界x v y 及下确界x a y 都存在，则称y 是一个格。如果对y 的任何子集置上确界 v x 及下确界 z 都存在，则称矿是完全格。每个完全格矿都存在最大元 素vv ，称其为单位元，记作i ，。对偶的还有最小元素 矿称其为零元，记 作0 ，。 、 如果对y 中的元素都定义了上确界和下确界运算的话，那么我们也可 以用这些运算来重新建立序关系，即 x y x = x a y * v y = y 。 如果7 是二个索引集，且x ：= x ，l f t ) 是矿的一个子集，那么我们也可以 用v 。，t 来代替v x ，用八。来代替八z 。 上确界和下确界运算是满足结合律的，对于我们所熟悉的结合律的特 殊情况，即，x ( y az ) = ( x a y 认z 和x v ( y v z ) = ( x v y ) v z ，如果 工，l t n 是 y 的子集的集合，那么这两个结合律的特殊情况能被推广为： v ( v x ，) = v ( u 一) 而且对偶地有八( 八一) = 八( u x ，) 。 ler“!rl e r t e t 命题2 1 若对于一个半序集的每个子集，其下确界都存在的话，则这 个半序集是完全格。 证明令x 是半序集的任意一个子集，因为已经假设它的下确界存在， 所以只要证明x 的上确界一定存在就可以了。设x 的所有上界组成的集合 是s ，由于s 也是半序集的一个子集，所以它也应该有下确界( 即使s 是 空集也成立) ，记这个下确界为5 。因为工中的每个元素都是s 的下界，所 以x 中的每个元素都小于或等于s ，于是s 就是x 的上界，而且显然是上 确界。 定义2 8 对于完全格矿的一个元素v ，我们定义 v 。：= v 往v iz v ，v + - 扛v lv x ) 。 如果v v 。，即v 不是严格小于它的那些元素的上确界，则称v 是上确界不 可约的；如果v v ，即v 不是严格大于它的那些元素的下确界，则称v 是下确界不可约的。 用以叻表示所有上确界不可约元素的集合，用坝功表示所有下确界不 鞍山科技大学硕士论文 第二章形式概惫分析理论基础 可约元素的集合。 j ；孵豁企穗i 、 如果集合矿的每个元素都是段x v ) 的某个子集的上确界，则x 称 为，在v 申，是上确界稠密的。对偶地，如果集合矿的每个乖素都是坝x v ) 昀某愈焉拳嗨忑穆界j “，则誊称为声宴是忑碲参观密f ! q 、一强、_ _ k 吖。 命题2 2 有限格的一个元素v 是上确界不可约的，当且仅当它有且仅 有一个下近邻。v 是下确界不可约的，当且仅当它有且仅有个上近邻。 上确界稠密子集包含了所有上确界不可约元素。下确界稠密子集包含了所 有下确界不可约元素。反之，在j 个有限格中，集合以 是上确界稠密的，。 旭即是正确界稠密的。i 证明：。v 是上确界不可约的。当且仅当v v ，这显然与v 是小于v 的最 +jj_：j：?-t_ ；“二： 大季李篙终_ 碡，尊v 慧乒：、肇：譬粤忑零：。对侵氇? 辱。下卵餐万曩冬畸： 则必亨唯尊占誓批? h 。一。，j ：、。| ；：、_ ：。o 小_ 。：i 、 ，由于士砷罗弯再约印季零不是隹伊不包拿声的冬；拿的士磅哥，! ：爆以上 确界稠密子集中必然包含寓们j ：蓼姆挚了磅野不可约吞素也_ 毒彗包含耷、 下确界嗣李于集中- ，：、 一 ：，! ： 因为以功以外蟹每食季零v 帮是比它严格较小元素的士矛：担零些它 严格较小的元煮拿属于：0 _ “则j 宣是以功一个子集魄士羁；，莓碎。訾严格较 小元素中还有不属于以功的，那么这些耍素芦是；善_ 些严格。簿，j 、元素p 勺上 界，则v 也捶是这訾较小羁零的圭界。却是这些元：素全碍于j 曩 ，则v 也 是以中一食子集的上界。幸果这些元素季有不属于以n 的，则再重复上 面的分析a 由于矿是有限的，所以最终总会得v 是以功中某食于篝的士界? ： 所融以印是上磅墨穆密的。遐据对绨，旭一是确界碉奄印：。：。i 定义2 9 两个完全格v 和，w 之间的个映射9 ：矿寸w ，如果对于v 的每个子集x ，都满足 v ! ? i 一。 ： 。 。：i 妒( v x ) = v 伊( x ) 的话，那么称声为保上确界映射，也称其2 为v 射：对偶地：如臬对牛v 的 每个子集x ，都满足 。( 八x ) 叭匆( z ) 一 的话，那么移妒为保- 下确多映射，也移，其为八射如罘妒既是保上确界映 黟子母粤下确哥咚慰魄译：跫争黪伊母亭舍椅同套譬完舍同态f ， 每介保上确，界，映射，特别是每个完金同态都_ 定是保序映射。反之， 任何一个裹拿格之间的，序同构孰必然是一个格同构，即，。一个双射的完全， 同态。 9 鞍山科技大学硕士论文。第二章形式概念分析理论基础 2 2 概念格理论 i 定义2 1 0 一个形式背景k = ( g ，m ，) 是由两个集合g 和m 以及g 与m 问的关系组成。g 的元素称为对象，m 的元素称为背景的属性；( g ，m ) ， 或g l m 表示对象g 具有属性m 。 。” 定义2 1 l 设a 是对象集合g 的一个子集，我们定义 ，( 爿) # 朋m i v g 爿，g i m ) 口中对象共同属性的集合) ? 相应的设b 是属性集合m 的二个子集，我们定义 g ( 8 ) ：= g g i v m b ，g l m ( 具有b 中所有属性的对象的集合) 二“ 定义2 1 2 背景( g ，肘，) 上的一个形式概念是二元组( 爿，西：其中 a g ，b m ，而且满足f ( a ) = b ，g ( b ) = a 。我们称a 是概念口，口) 的外延； 口是概念口，b ) 的内涵。用b ( g ，m ，) 表示背景( g ，m ，) 上的所有概念的集合。 命题。2 3 如果( g ，m ，) 是一个背景ja ，a ，a ：g 是对象的集合， 口，b ，b ，j j l ：f 是属性的集合，那么下列式子成立： 1 ) a c a 2j f ( a 2 ) f ( a i ) 1 ，) 8 l b 2j g ( 岛) g ( 马) 2 ) a g ( ，( 爿) ) 2 ) b 厂( g ( b ) ) 3 ) 厂( 爿) = ，( g ( 厂( 一”) 3 ) g ( b ) = g ( ( g ( b ) ) ) 4 ) 爿g ( b ) b c ，( 爿) a b 量i 。 。一般两个外延的并集不一定还是外延，同样一般两个内涵的并集也不 一定是内涵。不过任何数量外延的交( 内涵的交) 却一定还是外延( 内涵) ， 即有以下命题： 命题2 4 若，是一个索引集，而且对每个，t ，a ，g 都是对象的集合， 则f ( u a ，) = n ，( 4 ，) ，此结论对属性集合也成立。 证明m ，( u 彳，) v g u a f ，g m 营v t t ，v g a ，g l m r rr e r 甘v t t ，m f ( a ，) 车，”m f ( a ，) 。 t e t 定义2 1 3 如果( 爿。，且) 和似：，3 2 ) 是一个背景的两个概念，而且a 。a ：， 那么我们称( 4 ，b j ) 是( 4 ，8 2 ) 的子概念，( 彳：，8 2 ) 是( 彳，旦) 的超概念或父概 念，并记作( 4 。，e ) ( 一：，b 2 ) ，关系称为是概念的层次序( 或者简称为序) 。 若不存在概念( 一，b ，) 满足( 爿，目) ( 呜，b ) ( 爿：，晚) 且( 4 ，b ) ( 一，马) ， 1 0 鞍山科技大学硕士论文第二章形式概念分析理论基础 ( 4 ，岛) ( a 2 ，b ：) ，那么称( a i , b 1 ) 是( 彳：，岛) 的直接子概念，( 彳：，点：) 是( 4 。，县) 的直接父概念，并记作( 4 ，马) ( 一2 ，b ：) 。半序集壁( g ，m ，) = ( b ( g ，m ，j ) ，) 是 _ 个完全格，称它为背景( g ，m ，j ) 的概念格。 一、 定、义2 1 4 对于个对象g 辱q ，我们用，( g ) 代替瓜 g ) ) 米表示对象g 的对象内涵；， m m ig l m ) ，相摩的用g ( 彤) 代替g ( 枷) ) 来表示属性m 的属 性外延： g g lg l m ) 。用符号，g 表示对象概念( g ( ，( g ) ) ，( g ) ) ， 照毒忝属 性概念( g ( 朋) ，( g ( m ) ) ) 。 ，、；j ?。，： 例2 2 下面给出形式背景和其对应概念格的例子，分别如表2 1 和图 2 2 所示。 。_ ， ! 。 t 、j ! ! 1 i - 一 1 表2 i i _ ：个形式背景。i 、 a c g h ： ， 一 口6de fg + h l 5 父：。叉 l ： h ： r1 2 r ： 3 、，i： 1? 4x 5 ， 一j 6 7 、 。 8 x 圈2 2 表2 1 所示背景的概念格 鞍山科技大学硕士论文第二章形式概念分析理论基础 2 3 多值背景 “属性”不仅用于表示对象可能有或可能没有的那些性质，即只取 y e s ，n o 。两个值的性质，还有可能是代表可以取多个值的性质。例如“颜 色”、“重量”、“性别”、“成绩”等属性就是可以取多值的。我们称它们为 “多值属性”， 定义2 1 5 一个多值背景( g ，m ，d 是由集合g ，m ，矽及它们之 间的一个三元关系h 即，g m w ) 组成，而且下式成立： ( g ，m ，w ) ，及( g ，m ，v ) ，j w = v g 的元素称为对象，m 的元素称为( 多值) 属性，的元素称为属性的值。 ( g ，m ，w ) ，我们读作“对象g 的m 属性具有值w ”，如果w 有聍个元素， 则( g ，m ，矽，d 就：称为是玎值背景。多值属性可以看作是从g 到的一 个部分映射，即如果( g ，r n ，蝴，则可以看作r a ( g ) = w 。属性m 的域定义为： d o m ( m ) ：= g g i ( g ，m ，w ) j ，对于某些w w ，如果d o m ( m ) = g ，则称m 是 完全的。如果一个多值背景的所有属性都是完全的，则称这个多值背景是 完全的。 象单值背景那样，多值背景也可以用表格来表示。表格的每行是一 个对象，每一列是一个属性，位于g 行，m 列交叉处的项就是对象g 在属 性m 上取的值，即m ( g )