（计算机应用技术专业论文）模糊形式背景下基于阈值的概念格的构造和属性约简.pdf

摘要 概念格是近年来获得快速发展的数据分析的有力工具之一。它通过h a s s e 图 表现出概念之间的泛化和例化关系，已在知识工程、数据挖掘、信息检索、软件 工程和数字图书馆等领域得到广泛的应用。目前的形式概念分析主要基于经典的 形式背景来进行的，即形式背景中对象和属性的二元关系的取值为o 和l ，然而 在许多实际问题中对象和属性的二元关系是模糊的、不确定的，是一个模糊集合。 模糊集理论能够分析和处理模糊的信息，已成功地应用到许多研究领域。对模糊 形式背景的研究更加符合实际需要，具有重要的理论意义和应用价值。 本文的主要工作有： 通过对模糊形式背景的研究，给出了基于阈值的模糊形式背景的概念格的构 造方法。即通过设置阈值，将模糊形式背景转化为基于o 、1 值的经典形式背景， 并采用了自底向上的方法构造概念格，构造格的方法是对c h e i n 方法的改进， c h e i n 方法会在底层产生大量的重复结点，并且没有生成h a s s e 图，而本文在改 进后，可在底层避免产生大量的重复结点，并最终生成h a s s e 图，通过设置不同 的阈值，可以得到不同的概念格，进而得到不同精度的知识。 讨论了在已构造好的概念格的基础上进行属性约简的问题。通过h a s s e 图， 采用按层次对图中的每一个概念进行遍历，并对概念中的每一个属性进行判断， 看它属于绝对必要属性、相对必要属性还是绝对不必要属性，本文给出了基于概 念的属性判定定理；通过属性约简，可以约去大量冗余的属性，更加快速地进行 规则提取和知识发现。 本文最后研究了关于形式背景的合成问题。根据它们合并前后的变化，提出 了四个类型的概念，不变概念、合并概念、更新概念、新增概念，并对这四个概 念做出了说明，最后，给出了形式背景合成的算法。 【关键字】：概念格；模糊形式背景；阈值；属性约简；合成 a b s t r a c t c o n c e p tl a t t i c ei so n eo fe f f e c t i v et o o l sf o rd a t aa n a l y s i st h a ti sf a s td e v e l o p i n gi n r e c e n ty e a r s i tr e p r e s e m st h eg e n e r a la n ds p e c i a lr e l a t i o n s h i pa m o n gc o n c e p t s ，a n dh a s b e e nw i d e l yu s e di nk n o w l e d g ee n g i n e e r i n g ，d a t am i l l i n g ；i n f o r m a t i o nr e t r i e v a l ， s o f t w a r ee n g i n e e r i n g ，d i g i t a ll i b r a r ya n do t h e rd i s c i p l i n e a tp r e s e m ，f o r m a lc o n c e p t a n a l y s i si sa n a l y z e dm a i n l yb a s e do nc l a s s i c a lf o r m a lc o n t e x t ，n a m e l yt h ev a l u eo f t h e b i n a r yr e l a t i o n s h i pb e t w e e no b j e c t sa n da t t r i b u t i o n s i s0o r1 h o w e v e r , i nm a n y p r a t i c a lp r o b l e m s ，t h eb i n a r yr e l a t i o n s h i pi sv a g u ea n du n c e r t a i n ，i saf u z z ys e t t h e t h e o r yo ff u z z ys e tc a l la n a l y s i sa n dp r o c e s sf u z z yi n f o r m a t i o na n di sa p p l i e dt om a n y r e s e a r c hf i e l d ss u c c e s s f u l l y i tm e e t sp r a t i c a lr e q u i r e m e n tt or e s e a r c ho nf u z z yf o r m a l c o n t e x ta n dh a si m p o r t a n tt h e o r e t i c a lm e a n i n ga n dp r a c t i c a li m p o r t a n c e t h em a i nc o n t r i b u t i o n so f t h i st h e s i sa l el i s t e da sf o l l o w s ： f i r s t l y , w ep r e s e n tan e wc o n s t r u c t i o nm e t h o do fc o n c e p tl a t t i c eo ff u z z yf o r m a l c o n t e x tt h r o u g ht h r e s h o l da c c o r d i n gt ot h er e s e a r c ho ff u z z yf o r m a lc o n t e x t t h a ti s ，i t t u r n sf u z z yf o r m a lc o n t e x ti n t oc e r t a i nf o r m a lc o n t e x tt h r o u g ht h r e s h o l d w eu s et h e m e t h o df r o mb o t t o mt ot o pa n di m p r o v et h em e t h o do fc h e i na l g o r i t h m t h em e t h o d o fc h e i np r o d u c e sag r e a to fd u p l i c a t e dn o d ea n dd o n tc r e a t eh a s s eg r a p h a f t e r i m p r o v i n g ，i tc a na v o i dp r o d u c i n gag r e a to f d u p l i c a t e dn o d ea n dt r e a th a s s eg r a p h a c c o r d i n gt od i f f e r e n tt h r e s h o l d ，w ec a l lo b t a i nd i f f e r e n tl a t t i c ea n dd i f f e r e n tp r e c i s i o n l e v e lk n o w l e d g e s e c o n d l y , w ed i s c u s sa t t r i b u t er e d u c t i o nm e t l l o d w h e nt h ec o n c e p tl a t t i c ei s c o n s t r u c t e d b yt h eh a s s eg r a p h ，w ea c c e s se a c hn o d eb yh i e r a r c m c a lt r a v e l ，a n d d e c i d et h ea t t r i b u t eo fe a c hc o n c e p t b a s e db nt h ec o n c e p t ，w eg i v et h ep r o p o s i t i o na n d m e t h o dt oj u d g ew h e t h e ra na t t i b u t ei si n d i s p e n s a b l e ，r e l a t i v ei n d i s p e n s a b l eo r d i s p e n s a b l e f u r t h e r m o r e ，w es h o w a t t r i b u t er e d u c t i o nm e t h 6 j lw h e nt h ec o n c e p tl a t t i c e i sc o n s t r u c t e d b y t h ep r o p o s e da t t r i b u t er e d u c t i o n ，w ec a nr e d u c eag r e a fd e a lo f r e d u n d a n ta t t r i b u t e sa n do b t a i nt h er u l e sa n dk n o w l e d g em o r eq u i c k l y f i n a l l y , w ed i s c u s st h ei n t e g r a t i o no ft w of o r m a lc o n t e x t s a c c o r d i n gt o t h e c h a n g ef r o mb e g i n n i n gt oe n do fi n t e g r a t i o n ，t h e r e a lef o u rt y p e so fc o n c e p t ： u n c h a n g e d c o n c e p t ，m e r g i n gc o n c e p t ，m o d i f i e dc o n c e p ta n dn e wc o n c e p t w ep r e s e n t t h ep r o o fa n di l l u s t r a t i o nt ot h ei n t e g r a t i o na l g o r i t h m 【k e y w o r d 】：c o n c e p tl a t t i c e ；f o r m a lc o n t e x t ；f u z z y s e t ；a t t r i b u t er e d u c t i o n ； i n t e g r a t i o n 2 独创性声明 本人声明所呈交的论文是我个入在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写的研究成果， 也不包含为获得江西财经大学或其他教育机构的学位或证书所 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名： 耻曰期：丝监 关于论文使用授权的说明 本人完全了解江西财经大学有关保留、使用学位论文的规 定，即：毕校有权保留送交论文的复印件，允许论文被查阅和借 阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印 或其他复制手段保存论文 ( 保密的论文在解密后遵守此规定) 签名噶千垒盘导师签名：机日期：业 引言 引言 概念格，也称为g a l o i s 格，又叫形式概念分析，是近年来快速发展的数据分 析的有力工具之一。在哲学中，概念被理解为外延和内涵两部分所组成的思想单 元，基于概念的这一哲学理解，德国数学家趼如于1 9 8 2 提出了形式概念分析【l 】。 主要用于数学分析工具并应用于决策分析，关联规则发现等方面。概念格的每个 节点都是一个形式概念，由两部分组成：外延和内涵。所谓外延，就是概念所覆 盖的实例，即我们通常所说的对象；内涵，就是概念的描述，即该概念实例所具 有的共同特征。因此，概念格在本质上描述了对象与属性之间的联系，概念格分 析的数据一般用形式背景来描述，是特殊的信息系统。， 在知识发现的过程中，建造与应用概念层次结构进行知识获取具有很多的优 势，而概念格对应的h a s s e 图正好体现这种概念层次结构。概念格通过h a s s e 图生 动和简洁地体现了这些概念之间的泛化和例化关系。从数据集中( 概念格中称为 形式背景) 生成概念格的过程实际上是一种概念聚类过程，应用于许多机器学习 的任务，例如，知识发现、关联规则发现等。 因此，概念格作为一种具有极大潜力和有效的知识发现工具，备受研究者的 广泛关注。概念格体现了概念的外延和内涵的统一，通过分析概念节点的对象和 属性之间的联系以及概念之间的泛化与例化关系，可以发现数据集中潜在的概念 以及反映概念之间关系的关联、分类和聚类知识。目前，形式概念分析被广泛应 用于知识工程、数据挖掘、信息检索、软件工程、数据图书馆等领域中。 对于概念格的研究在国内外都得到了广泛的关注，取得了很多研究成果。对 它的研究主要包括格的构造算法【2 别，概念格的修剪【1 0 小】，关联规则提取【1 6 。2 2 1 ，数 据挖掘2 3 2 4 1 和知识发现【2 5 2 7 】等。近年来，概念格文与粗糙集【2 s 3 、模糊集【3 2 删进 行融合，来解决一些不精确的、模糊的信息。关于概念格的构造算法目前有很多， 主要分成两类：一类是批处理算法，如b o r d a t 【2 】，c h e i n 3 等- ；另一类是增量算法， 如g o d i n 7 j 算法，动态的生成概念格，但至今缺乏生成适合大型数据库又具有较低 复杂度的生成算法。概念格的扩展模式，关联规则发现、分类规则提取，和其它 分类器相比，概念格上提取的规则具有相当或更好的效果。主要应用在超市数据 挖掘、入侵检测、日志挖掘、软件工程、数字图书馆、原形系统的设计与开发等 方面。目前在国内外学术界，概念格以其独特的优势得到越来越多的学者的关注， 然而这仍然是一个潜在发展的领域，在很多方面都有进一步探讨的空间。 最初的形式概念分析主要基于经典的形式背景来进行的，即形式背景中对象 和属性的二元关系的取值为0 和1 ，然而在许多实际问题中对象和属性的二元关系 模糊形式背景下基于阈值的概念格的构造和属性约衙 具有各种类型的取值，如模糊值、实数值、区间值等，对这些类型的概念格的研 究更加符合实际需要，具有重要的理论意义和应用价值。近几年来，国内外的一 些学者对基于模糊值、实数值、区间值类型的形式背景的形式概念分析进行了一 些推广研究。国外的b u r u s c o 把f c a 的模型推广到了模糊形式背景上去【) 副；同时， b e l o h l a v e k 【3 6 3 引，基于隐含算子研究了模糊形式背景上的模糊概念；更进一步地， g e o r g e s c u 和p o p e s c u l 3 9 4 0 】对模糊f c a 讨论了更一般的方法；j a o u a 和e l l o u m i 把模 糊二元关系推广到了实集二元关系引进了实伽罗华联结1 ；y a h i a 提出了单边概念 格模型【4 2 】。 国内也有很多学者对进行了研究，如张文修等提出了变精度概念格模型，指 出单边概念格模型是变精度概念格模型的一种特例【4 3 】。有些学者研究了由蕴涵算 子构造模糊概念格。比如k l e e n e - d i e n e s l u k a s i e w i c z 蕴涵算子m j ，l u k a s i e w i c z 蕴 涵算子构造【4 5 1 。对于不同的问题，蕴涵算子的选择是十分重要的，选用不同的模 糊蕴涵算子进行计算，所得的结果会不相同。刘瑞新在他的论文中重点描述了基 于不同蕴涵算子的模糊概念格算法的实现、相关的算子及其定义，并且在程序中 选择不同的蕴涵算子时，该算法可以实现自动切换【4 6 】。另外，还有些学者利用模 糊集中的截运算再利用经典概念格的构造方法来讨论模糊概念格的构造，例如， 陈继华，罗从文讨论了一种区间值模糊概念格构造方法【4 7 】，刘宗田等提出模糊形 式背景中属性隶属度值的窗口截取方法；定义了模糊概念的模糊参数。和入，给 出了模糊概念格渐进式构造算法【4 & 4 9 。 ， 本论文研究的内容主要有以下几点：1 、，模糊形式背景下概念格的构造。本文 通过设置阈值，将模糊形式背景转化为经典形式背景，并给出了一种模糊形式背 景下基于阈值的概念格的构造方法。为模糊概念格的进一步研究提供一种新的方 法。2 、概念格的属性约简。以张文修的概念格约简理论为基础，给出了新的约简 理论和方法。3 、形式背景的合成。讨论了对于两个形式背景的合成后，对应的两 个已构造好的概念格的合成。文中给出了二些理论和合成的方法，它进一步扩充 了概念格理论，对概念格的研究和应用都有着重要的意义。 根据研究内容，本文基分为5 章：第l 章介绍相关的背景知识，包括概念格 和模糊集的基本概念和一些相关的性质；第2 章讲述了模糊形式背景下概念格的 构造，介绍了模糊形式背景的概念，给出了模糊形式背景下基于阈值的概念格的 构造方法；第3 章为概念格的属性约简，讨论了一种新的属性约简理论和方法： 第4 章为形式背景的合成；给出了概念格合成的一些性质及合成方法。第5 章， 总结了本文并提出下一步的研究工作。 2 1 预备知识 i 预备知识 1 1概念格 1 1 1 基本概念 定义1 1 【5 0 1 设 h ，是_ 个偏序集，如果日中任意两个元素都有最小上界和 最大下界，则称 ) 口； 2 a 是绝对不必要属性铮( 口“一 口) ) = ，。且晓= 口； 3 a 相对必要属性营( 口”一 口) ) = 口且瓯日 在介绍下面的定理之前，我们先设定由形式背景构成( u ，a ，r ) 概念格中，它 的最顶点是( u ，矽) 。如果某个属性集yc _ x ，而y 为所有的对象拥有的话，那么这 个概念格的最顶点为缈，】，) ，那么这个属性集】，可以从这个概念格中约去，使得这 个概念格的顶点成为，) 。因为所有的概念都具有属性集y ，那么这个属性集y 对概念的区分没有意义，所以不影响原始形式背景上的概念及其层次结构，所以 可以预先约去。 定理3 5 设三为形式背景( u ，彳，r ) 的个概念格，( x ，】，) l ，并且它的最大 界是( u ，矽) 。如果】，的基数为1 的话，也就是说只有一个属性，那么这个属性一定 是核心属性。 证：因为y 的基数为1 ，也就是说只有一个属性( 假设为口) ，如果去除这个属 性的话就是空集，而空集所对应的对象是u ，也即口= x ，口”= x = 口， ( a ”一 口 ) = = u 显然，u x ，也即( a ”一 a ) ) a 。根据定理3 4 中的l 得知 a 是核心属性。 ，、 定理3 6 设三为形式背景( u ，彳，r ) 的一个概念格，( z ，y ) l ，如果y 的基数 不为1 ，但是它的超概念是( u ，矽) ，那么对于】，中的每个属性都是相对必要属性。 证：首先，对于，) 的每个子概念，它们的属性是互不相交的。也即是每个 子概念之间没有公共的属性。如果有哪两个子概念有公共的属性，设为何，那么 这两个子概念的父概念就不是( u ，) ，而是( 日”，日) 。 其次，对于v 口三】，口= ，= x 。因为】，中的所有属性是同层次概念所没有 的。假如a 所对应的对象除了x ，还有x 的话，那么( x ，y ) 的超概念就是 ( x u z ，口) ，而不是( u ，) 。那么口”= x = 】，( 口”一 口) ) + = ( y 一 口) ) 。我们可以 把它看作除口后其余属性的并，用u b , 表示。即( 口”一 口) ) = ( _ y 一 口) ) = ( u 6 ) = n 巧= n 工- x 。 再者，对于v g a y ，假设g 3a ，那么根据概念格性质中的( 1 ) 得g ”c 口“， 而口”= x = y ，而g ”所对应的是同一层次另一概念的属性集，通过前面我们知道， 它们的属性集是互不相交的，所以g ”ca ”不成立，从而假设不成立。 由上得知，在么中找不到这样的一个属性，使得g a ，g 3 口成立，也即 3 概念格的属性约简 e = 。而谚= u 口。所以可以得知y 中的每个属性都是相对必要属性。 我们知道，概念格是一个自顶向下的有向图。对于概念格的属性约简，我们 可以对这个图采用自顶向下层次遍历的方法对它的每个概念进行约简。根据上面 的两条定理，我们可以得到最初的绝对必要属性和相对必要属性。对于其余概念 的属性我们可以根据以下定理判断。 我们在判断下面概念的属性时，假设这个概念为，功l ，会有一些属性是 在它的父节点已经判断好的属性，我们设为k ，对于这部分属性，不需要再判断了。 剩下的那部分未判断的属性，我们设为k ，对于这部分属性的判断有如下定理。 定理3 7 设三为形式背景( u ，a ，尺) 的一个概念格，( z ，】，) 三，对于v y e ， 如果( y 一 力) x 的话，那么，y 为核心属性：如果( 】，一 j ，) ) = x ，并且，( x ，y ) 只有一个父节点的话，y 为相对必要属性，否则为绝对不必要属性。 证：首先我们证明k 中的任一属性y ，除了它的子节点外，其它的与它同层 的节点都没有的。因为如果其它同层的某个节点的属性包含k 中的一个属性的话， 那么它必然和该节点有一个共同的父节点，而它所有父节点的属性在之前就已经 判断过，也即它属于x 。即y + = x ，y ”= x i - - - y ，那么( y ”一) ) = ( 】，一 y ) ) ， 如果叮一 少) ) + x ，也即( y ”二 y ) y ，那么根据定理3 - 4 中的1 可知，。y 是核心 属性。 如果( y 一( 力) 。= ，并且( x ，聊只有一个父节点( z 。，】，i ) ，首先我们要求出g ， 即真包含于y 。的属性的集合。属性】，分为z ，e ，由前面我们可知，k 中的任意属 性都的牛操作的结果都是x ，即等于y ，也就是说不会真包含于y 。我们由概念 格的性质得知，要真包含y ，即真包含z 的节点是祖先节点的对象，但我们只要 考虑这些对象所对应的属性，而在这些节点中，它的父节点就包含了其所有属性， 所以在这罩我们只需要考虑父节点，假设为( 彳，y ，对于v y y ，那么 y 】厂， y ) 2y ”= x 3x = y 。，也即y 一3y 。，即g ，= y ，那么g ：= y ”予x x = y 。， 也就是说，g ：y 。，根据定理5 中的3 得知y 是相对必要属性。 如果( 】，一( y ) ) = x ，并且( x ，y ) 有多个父节点，假设为( x l ，i ) ，( z ，) ( ，) ，这个证明与上一个类似，唯一不同的是它有多个父节点，那么g ，= u z ， 。 i = l g ；= ( uy ) = nf = n z ，根据定理1 ，我们可知nz ，是( z ，i ) ，( z ，巧) ( z ，巧) 对象的下界，即x ，即g ：= x7 - y + ，从定理3 4 中的2 得知y 是绝对不必要 ， 属性。 定理3 8 设为形式背景( u ，彳，r ) 的一个概念格，( x ，n l ，如果它有多个 父节点的话，e 就为绝对不必要属性；如果它只有一个父节点的话，且e 的基数 为1 ，e 为核心属性，如果k 的基数大于1 的话，那么k 为相对必要属性。 模糊形式背景下基于阈值的概念格的构造和属性约衙 ， 证：如果( z ，y ) 有多个父节点的话，那么，根据概念格下确界的定义： ( z ，z 。) 三( n z ，( u r ) ”) ，我们要以看出，u 鬈。实际上就是定理中已判断的属性z ， 。 1j 。1i f f i l f = ( uf ) = nz = x ，而对于v y 。e ，y 一= x ，这在前面己说明。 i = if l i 。 ( 誓u y 9 = 耳n y r = x n x = x ，我们可以一个个属性添加进去，最后留下一个属 性y k ，也即( y 一 y ) ) = 彳成立，由于它有多个父节点，根据3 - 7 得知，y 为绝对 不必要属性。而这个y 是e 中任意的，也即k 为绝对不必要属性： 如果它只有一个父节点的话，设为( z ，y i ) ，那么誓，e 中的巧实际上就是y ， 因为判断好的的属性实际上都是父节点的属性，所以y = y 。+ k 。如果e 的基数为1 ， 即五只有一个属性，设为y ，那么y = j ，+ y ，而j ，= x ，y 木事= y ，这个可以根据 前面的来得到。那么( y 木一抄) ) + = ( 】，一 y ) ) 木= y 。串= x x = y + ， 也即 ( y