（应用数学专业论文）形式背景核的有限性研究与算法实现.pdf

潺毫大学焱童攀整论文繁l 黉 摘要 网络技术大大提高了人的生存质髓和人的素质，使人成为社会人、全球人， 同时。网络的普及也络人们带来了海爨倍息，大量信息在绘人们带来方便的同时 瞧豢寒了一丈壤游惩：蒡一是售惑i 妻鬃，难戮瀵往；第二怒嫠惑寞缓难戳辨谈； 第三是信息安全难以保证；第四是信息形式不一致，难戳统一处理。于是入们开 始考虑：“如何才能不被信息淹没，而照从中及时发现有用的知识、提高信息利用 察? ” 瑟辩这一撬撬，数据挖握积知谈发蠛技术应运悉生，势曩示篷强大救生会力。 由于形式概念分帮荦申豹概念格具有良安孑的数学往质、遭含擞处理和能表示校念之 间的关系等特点，我们认为概念格模激可以用来作为数据挖掘的一种非常理想的 工具。形式概念分析是从形式背景这一基本的数据形式开始的，因此形式背激的 嫒模是影响概念格梅造和应用的一个爨臻因素。 蔻梵，零文辩澎式营景进幸亍了较凳金覆、系统豹磁究，凝密了形式鹜鬟梭豹 概念和相关的限定饿定理。利用形式背景核的有限元索等价地表示一类无限的形 式背景，从而达到用核中元素的格快遴生成新的概念格的目的。主要的研究内容 涉及形式背景的提取、切分、约简和同构判定，以及形式背景核的代数性质和形 式鹜蓉孩懿携造冀法等。菝摇降低形式鹜最数蠢量弱嚣憨，绘爨了形式鹜豢凌分 和约筒的具体算法，并按照对形式背祭蒸的定义，实现了形式背景基的算法，给 出了形式背景基性质的证明，通过对形式背景核基本算法的研究，给出了形式背 h 晟核的改进算法，从而降低了求疗阶形式背景核的时间复杂艘和空间复杂度。提出 了”阶形式鸳景核粒陵定佳定理，势绘淡了证明。本文豹疆的毽就是通过分砉砖檄愈 嵇翦数学簇垄、髓臻，对形式背景迸行系统豹分辑探讨，为概念捂豹同摘秘逡摄 供理论基础，从而进一步将概念格应用于数据挖掘。 本文的主要贡献如下： ( 1 ) 提出了n 阶形式背景核的概念，构造了砰阶形式背景核的基本算法，并对 蒸零雾洼送嚣了浚滋，簿决了嚣陵形式键豢孩缝透熬基本舞滚熬效率羝静阉瑟，鲶 繁l l 茭海南大攀磺士学位论文 獭了两种算法的对鬻复杂疫豹对比；阂辩说明了形式背景骇的理论意义及应蹋徐 值。 ( 2 ) 提出了形式背景核的限定性定理，通过另一个重鼹概念形式背景撼 的性质，证明了弹除形式背景基和n 阶形式鹜景核两个集含的基数的关系，为形式 鹜豢孩豹浚速擒逸爨供了理论莰据。 ( 3 ) 设计并实现了形式背景的手动切分、自动切分的详细算法。 ( 4 ) 设计并实现了形式背景的约简的相关算法，包括消晰化和标准化的详细 算法以及约简对构遗概念格时问复杂度的影响。 关键运：黟式骛爨挟；形式鸷景基：澎妓缓念努辑；攫念臻；形式鹜最 海毫大学磺女攀位论文筹l l l 燹 a b s t l a e t t h en e t w o r kt e c h n i q u er a i s e d 廿l ee x i s t o n c eq u a n t i t ya n dt l l oc h a r a c t e ro f m ep e r s o n c o n s m e d l y ，m a h n go n eb e c o m e sas o c i a lp e r s o n ，a 出o b a lp e r s o n ，m e a n w h i l e ，t l e 徽 v e r s a l 晦o ft l l e 船嘲。矗o f sh s 毡g 端a td e a lo fi n f o 燃a t i o 娃，w h i c hb f i n g s t l s e o n v e n i e n t8 墨da l s oal o to f p o b i e m s f i r s t ly ，也ei n f o r m a t i o ni st o oe x c e s s i v e ，h a r dt od i g e s t ，s c c o n d l y m ea u t h e n t i c i t y o fi n f o 珊a t i o ni sn o te a s yt oj u d g e t h i r d i y i ti sd i m c u l tt oa s s u r et h es a f e t yo f 龇 i 耐i o 珊a t i o n f o 训y t l l ef o mo ft h ei n f o r m a t i o ni ss ov a r i o u st i l a ti t sh a r dt op r o c e s s c o i 珏c i d e n 畦y 珏e n c e 氆e 渺薅es 捷nc o n s i & r i n 鐾牡 o w 耄dd i s v e ru s e 粼妇o w l 矗g e 强d 酗w 耄o b o o s ti n f b 加a t i o nu t i i i z a t i o n ? ”f a c et o 协i sc h a l l e n g e ，t h ed a 协m i n i n ga i l dk n o w l e d 蕻e d i s c o v e rt e c h n i q u ee m e 玛e s ，a n dd i s p l a y 8m es t r o n gv i t a l i 哪 a sm ec o n c e p tl a t i i c ei nf b r h l a lc o n c e p ta i l a l y s i s1 1 a s9 0 0 dm a t l l e m a t i c a lp r o p e r c i e s ， a 稚a d a p t 圭op c 髂s 添b l o 文鞠da l s ol te 强e x p 咒s st h e 撼1 8 t i o nb e t 聊髓e o n c 帮t s e l c a r l y ，w ed e e m 搬ee e e p tl a 蜒e ef n o d e lav c 哆i 魏a lt o o lf o rd 稚am 往i n g t h cm e o r yo f f o 舯a lc o n c e p ta n a l y s i s ( f c a ) s t a n s 如mt h eb a s i cd a 诅f o 蹦c a l l e d c o m c x t s ot h ec o n t e x ts c a l ei sa f li m p o n a n tf 如t o rt h a ta f i e c t st 1 1 ec o n s t n i c t i o na 1 1 dt h o 器p p l i c a t i o no f t h el a t t i c e t h e 站岛f ，翻sp 攀rs t 醢d 诗st h ec 蝴豫x t 黟鞋e 隧盟ds y s 靶m i c ，辨据南蹦a 撼辙o c o n e e p ta n dt 酶c o r 辩l a t i 、毪i i m i t a t i v el 瓢o r e mo ft h ec o 燃e x 专妊舶糟i a na | 奄i t 撼翠 c o n t e x tc o u l db ed e n o t e du s i n gf i n i t ee l e m 黼1 t si nt l l ec o n t e x tk e m e l ，a i l dm en e wl a t t i c e c o u l dq u i c k l yb eb u i l lb yt i l o s eo fm e s ek o m e le l e m e m s t h em a i ns t u d yi n v o l v e s c o n t e x te x 勺f a c t i n 函p a r t i t i o n i n g ，r e d u c t i n 颤i s o m o r p h i cd e t e c t i n g ，a l g e b 豫i cc h a r a c t e ra n d 如i l d i 珏g 霾l g o 菇颤麓so ft k n e x k e 氆e l 。w es 驾g e 蛙圭量l e 辨陡t i 黼a l g o 斌蘧s 蠲d 壤e 戚u c 蛀o na l g o 矗鼬n sb ym e 醐so f 氆et h o u 痨t so ff e d u c 试g 幽ec o n t e x ts c a l e ，b y 獭o n o t i o n so f 廿l ef o r m a lc o m e x tb a s e ，w ei m p l e m e n tt h ea l g o r i t h m sa n dp r o v et l l e c h a r a c t e f s t 1 1 r o u 曲t h er e s e a r c ho nm et h ef o n n a lc o n t e x tb a s ea l g o r i m m s ，w ep u t f o r v 阻r dai m p r o v e m e n t 越g o f i t h m sw h i c hd e c l i n e st h et i m ec o m p l i c a t i o n sa n d 也es p a c e e o m p l i c a t i o n so ft 如撑搬一。砖e r 南辩a lc o 琏镪x t 妇r n e l ，p 瞧f o r w 毅琏攮ol i m i 耄a _ 哇v e 也端撤 繁l v 燹潺零大学琰士学位论文 o f 斑e 雄蜘o r d e ff o f m a lc o n t e x lk e m e l ，a n dg i v e 谴sp r o o f 斑l a s t ， t h em a i nc o n t r i b 岫o n so f t h i sp 印e ri n c l u d e ， ( 1 ) p u t i n gf o n v a r dt h ec o n c e p to f m eh u l - o r d e rc o n t e x tk e t l l e l ，s t u d i n ga j l dm e n d i n g t i eb 城l d i n ga l g o r i t h m so ft l l e 片m o r d e fc o n t e x tk e m e l ，s o l v i n gt h ei n e m c i e n tq u e s t i o n 她b 嚣i c 鑫l 静f 融m s 强b 毡i 殛n 参馘莲g i v l 甥。避醢蟛e o 嘲藤s o n 醴龇 i 撒o c o m p l i c a t 主o n so ft h e 铆玩m e a n w h i l e ，e x p l 越n i n g 也et h e o r e mm e a n i n ga n d 俑e a i m l i c a t i o nv a l u e so f t h ec o n t e x tk e m e l ( 2 ) p u t i n gf o r w a r da n dp r o v i n gt h ef i n i t em e o r e mo ft h e 扩- o r d e rc o n t e x tk e m e l ， a n dp f o v i n gm er e l a t i o no ft 圭l er a d i x t w e e nt h e 一m o r d e rc o n t e x tk e m e la n dt l l e 蘑“_ o 砖e fe o n 靶x tb a s e 疆醢察疆ee h 鑫臻c 重懿o f t 魏ee o 鑫耙x tb a s e 。p 羚v 撼穗g 氆e8 e 确e 撤i e 瘿s t 缸氇e f a s tb u 主i d i n go f 也ec o n 耙x tk e r n e i ( 3 ) d e s i g n i n ga n di m p l e m e n tt h em a n u a la i l dt i l ea u t o m a t i cd e t a i l e da l g o r i m m so f t l ec o m e x t ( 4 ) d e s i g n i n ga n di m p l e m e n t i n g 也ec o r r e l a t i v ea l g o r i t h m so f t h er e d u c t i o no nt h e e o 矗t e 琏w 魏i 馥i 翳l 滋i 驾氇ee l 森每碡；o 纛t 囊班s8 砖氇es 豫t d 甜d i z 蘸。建碡癜殛筏零如 融n u e n e eo l lt h et i m ec o m p l i e a t i o no f l a t i c e 伽咀s t r u c t i o ni sg i 垤no u t 1 ( e y w o r d s ：f o r l l l a lc o n 把nk e m a l ；f o r r n a lc o n t e x tb a s e ；f o i t n a lc o n c 印t a m l y s i s ； c o n c e p tl a t t i c e ；f 0 黼a lc 0 n t e x t 关于学位论文独立完成和内容创新的声明 y 9 1 0 6 i6 本人向河南大学提出硕士学位日触士学位口中请。本人郑重 声绢：瑟燕亵妁擘稼论文莛本人独立完成酌，对瑟研究妁曝题有 新的见解匹静创婕性酌见解嬲。据我所知，除盘中加以说明、糯注 。，薹j ；毒i ；：誊j妻i ? i i 鏊誊袋誊 j - 关于i 攀键黉赡搪纛缕警匿鍪融j 豢爹 。“ 。、# ：谬誊誊j 磐j “霉 。o i ；j 磷囊，、，i ，争 本人经藩交大擎肇糍麟瀵袋警壤簧攀醢爨博士孥镑口。样为 学位的作符，本人完金了】i i 荜 并障戆辩南大学宥关保留、使用学位 论文鲢要求，黪藩交大学鬻淑向：露家霹书蝗、懿谚信息秘掬、数 据收集机构和本校圈_ 书馆警楗缀喾倥论走：蔗漕既质定本和电子文 本娃供公众检索、奎瓣，零森嫒辍簿溺大喾塞予宣扬、最凳学 校学恭裁展和进行学术交流等目的，可以采取影印、缩即、扫描 和耪羹等复割手段保存、派编擎经论文( 羲霍文本和电子交本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 擎位获褥者( 学位论文讳截签名：密f 书 如簿6 月洚翁 海毒大学磺童攀位论文繁l 黉 第一章绪论 本章首先介绍了数据挖掘的相关内容、概念格的简单介绍、形式概念分析 ( 秘a lc o n c 印ta n a l y s s ，缩写为f c a ) 技术在数据挖掘巾瓣应用然后给出零 文瑟要镶瓣主要工佟；帮黠彭式鹜最瓣稷芙分辑，蒡绘逡一糖求n 狳形式鹜象孩戆 改进算法，然螽讨论了形式背景核的理论意义及应用价值。 1 1 数据挖掘技术 席卷而来的轴t e 孵l e 因特网) 正将念世界的丰富信崽资源带到每一个人的蕊 薅，用户霉鞋凭氆 赫把瓣e t 获褥瀑炸毪增长夔数据。另一方鼗，夔羞数据库按零戆 迅速发震戳及数搭露管理系统靛广泛黩蠲，入稍积累戆数攒越来惹多。激增豹数 据背后隐藏着许多黛要的信息，人们希魍能够对其进行更黼层次的分析，以便鼹 好地利用这些数据。目前的数据库系统w 以高效地实现数据的录入、查询、统计 等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的 发展趋势。 大量售怠在绘入察荣来方餐戆弱嚣恣麓裹了诲多润瑟：第一是痿惑过量，灌 以消化；第二是信惠真假难以辨识；第三是信息安全难以绦诞：第四是信息形式 不一致，难以统一处理。人们开始考虑：“如何才能不被信息淹没，而是从中及时 发现有用的知识、掇高信息利用率? ”幽于缺乏挖掘数据背厢隐藏的知识的手段， 母致了嚏据爆炸但知识贫乏”的现象。 嚣对这一援战，数据挖掘霸知识发城l l l ( d a 魄m 蕊n g a n d 蕊o w l e d g ed i s c o 懈搿， 麓称d ) 按零嶷运蔼生，著显示窭强大豹生螽力。数据拣掇菝拳( d a l a 醚i 魏i 鹅 t e c h n o l o g y ) 是人们长期对数据库技术进行研究和开发的结果。起初各种数据怒存 储在计算机的数据库中的，然后发展到可对数据库进行查询和访问，进而发展剐 对数据库的即时遍历。数据挖掘使数据库技术进入了一个擞高级的阶段，它不仅 能对过去的数据避褥森询和遍历，弗鼠簸够找出过去数据之间的潜在联系，从褥 程遂穰怠魏铸遂。 数褥挖箍其实怒一个逐渐演交鹣j 童程，电子数据处理豹杨期，入稍载试强遴过 某些方法来实现自动决策支持，当时机器学习成为人们关心的焦点机器学习的过 程就是将一些已知的并已被成功解决的问题作为范例输入计算机，机器通过学习迭 贱范例总结并生成相应的规则，这些规则具有通用性，使用它们可以解决某一类的 间题。随后，随着神经网络技术的形成和发展，人们的注意力转向知识工程，知识工程 不弱予壤器学习弱群绘诗算援浚入薄弱，迁它奎残窭蓑粼，嚣蓬壹接绘诗算掇簸 第2 夏海南大擎琰士学位论文 入已被代码纯韵藏猁，两计算枫是通过搜雳这些规刚来解决某些闷题。专家系统 就是这种方法所得到的成果，但它有投资大、效果不甚理想等不足。8 0 年代人们 叉在新的神经网络理论的指导下，重新回到机器学习的方法上，并将其成果威用 于处理太型商业数据库。随着在8 0 年代涞一个新的术语，落就是数据库中的知识 发现，简称) d ( 融l o w l e d g ed i s e o v e r yi nd a 扭b a s e ) 它泛指掰寄歇源数据中发掇攘 焱或联系兹方法，入霞接受了这令零港，劳矮k d d 来疆遴熬令数疆菱箍熬遘筏， 包括最开始的制定救务目标到最终的缋泉分析，丽用数据挖锶( d a 诅m i 越n 量) 来 描述使用挖掘算法进行数据挖掘的子过程。但最近人们却逐渐开始使用数据挖掘 中有许多工作可以幽统计方法来完成，并认为最好的策略烧将统计方法与数据挖 摁有机的结合起来。 数据仓库技零鸵发展与数据挖援鸯麓密切静关系，数攥念库懿发展是键遴数 据控握越来越熟秘琢弱之一。餐是，数爨仓瘴荠苓是数撵藏掇戆先决条释，嚣为 有很多数据挖掘w 赢接从操作数据源中挖掘信息。 1 1 1 数据挖掘的研究历史和现状 从数据库中发联知识f f l f 司( k d d ) 一词首次出现在1 9 8 9 冬举行的第十届豳际 联会夭工鏊戆擎零会议上。婺嚣囊 兔壹，缀模峦嚣来豹专憨谤论会发矮癸嚣瓣学 术大会( 觅表1 ) ，磷究重点也逐澎从发现方法转向系统成掰，注重多静发现繁酶 和技术的集成，以及多种学科之间的相飘渗透。1 9 9 9 年，溉太地区在北京召开的 第三届p _ a k d d 会议收到1 5 8 篇论文，空前热烈。i e e e 的勋l o w l e d g ea n d d a 协 e n g i n e e r i n g 会刊率先在1 9 9 3 年出版了k d d 技术专刊。并行计算、计算机网络和信 息工程等其镳领域豹嚣际学会、学 q 也恕数据挖掘和鳃谈发现到为专题和专刊讨 论。 袭1 历届k 凿鼯学术会议一览裁 海南大学磺童举 立论文第3 燹 j 毙外，在i n t c 黼e t 上还有不少k d 粉瞧予出舨耪，其巾l 三乏半月翻k n o w l e 甄e d i s c o v e r yn u g g e t s 墩为权威( h t t p ：， v w k d n u g g e t s c o n 以u b s c r i b e h t m l ) 。在网上 还有许多自由论坛，如d me m a i lc l u b 镣。目前，世界上比较有影响的典型数据挖 掘系统有：s a s 公司的e n t e r p r i s em i n e r 、i b m 公司的i n t e l l i g e n tm i n e r 、s g i 公司的 s e 蛙娃i n e f 、s p s s 公弼瓣c l e m e n t i n e 、s y b 8 s c 公司的w i r e h o u s es 刚i o 、r u l e q s t 觏s 龉r c 魏公司豹s 。c 5 、还有c o v e 瞒l o 搿、e x p 的r a 、 麓o w l g ed i s c o v e 搿 w b r k b e n c h 、d b m i n e r 、q u e s t 等。读者可以访问h t t p ：， w 州d a l a m i n i n g l a b c o m 网站， 该网站提供了许多数据挖掘系统和工具的性能测试报告。 与国外相比，圈内对d m k d 的研究稍晚。1 9 9 3 年国家自然科学基金首次支持 对该领域的研究项融。目前，国内的许多科研单位和高等院校竞楣开展知识发现 瓣基礁理论及其痰羽磅究，这些单经愆惩瀵华大学、中辩陵诗葵技术磅究鼹、察 攀第三骚究簿、海攀装备论证中心等。獒中，j 豪系统王鞭研究获对模凝方法焱 知识发现中的应嗣进行了较深入的研究，北京大学也在开展对数据立方体代数的 研究，华中理工大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、 谢林大学等单位开展了对关联规则开采算法的优化和改造；南京大学、四川联合 大学和上海交通大学等单位探讨、研究了a 结梅化数据的知识发现以及w 曲数据挖 掇。 最近，g a 柏e r 蛳u p 酶一次高缀投笨调查将数据挖掘和人工智能剜为“未来三 到五年内将对工业产嫩深远影响的五大哭键技术”之首，并麒还将并行处理体系和 数据挖掘列为未来氘年内投资焦点的十大新兴技术前两位。根据最近g a n n e r 的 豫c 研究表明，“随潜数据捕获、传输和存储技术的快速发展，大型系统用户将熙 多避需要采用薪技术来挖掘市场以外的价蹙，采用更为广瓣靛势行处理系统米剁 建赣匏亵盈增长点。” 1 1 2 数据挖掘的功能和常用技术 数据挖掘通过预测未来趋势及行为，做出前摄的、基于知识的决策。数据挖 撅的目标是从数据库中发现隐含的、有意义的知识，主要脊以下五类功能i l 】。 f 1 ) 鑫动颈溺怒势秘行为。 数据挖强鑫麓在大型数据疼孛寻我鞭测往谊惠，班 芏嚣溪进行大量手工分街 的问题如今可以迅速赢接由数据本身得出结论。一个典型的例子是市场预测闯题， 数据挖掘使用过去肖燕促销的数据来寻找来来投资中回报最大的用户，其它可预 测的问题包括预报破产以及认定对指定攀件晟可能作出反应的群体。 ( 2 ) 关联分析。 数据关联是数撰潞孛存在魏类鬟簧戆霹被发褒瓣翘浚。羞嚣令羲多令交爨 第4 页海毫大擎磺士学馕论文 的取谴之间存在浆种援律性，就称为关联。关联可分为简单关联、时序关联、阑 聚关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库中 数据的关联函数。即使知道也是不确定的，因此关联分析娥成的规则带有可信艘。 ( 3 ) 聚类。 数据库中的记漾可被诧分为一系列蠢意义酶子集，即聚类。聚类增强了人销 辩客蕊现实豹试滚，跫攘念箍逮秘编麓分孝厅戆先决条詹。蒙炎技本主要包摇倦绫 的模式识别方法和数学分类学。g o 年代初m c h a i s k i 提出了概念聚类技术，其要点 是，在划分对象时不仅考虑对象之间的距离，还要求划分出的类具有某种内涵描 述。从而避免了传统技术的某些片面性。 f 概念描述。 概念箍述藏楚瓣莱类对象戆内涵遴弦接述，并掇捂这炎对象豹骞关特薤。概 念擒述分秀特征经掇述帮区搦往籀述，兹者摇述菜类对象豹共霜特征，蘑者臻述 不同类对象之间的区别。生成一个类的特征性描述只涉及该类对象中所有对蒙的 熬性。生成区别性描述的方法很多，如决策树方法、遗传辣法等。 ( 5 ) 偏差检测。 数据库中的数据常有一些异常记录，从数据库中检测这些偏差很有意义。 镶差惫疆疆多潜在瓣知谖，翅分类中魏爱零实例、不潢是缀翔戆特爨、瑟弱绥莱 与模型预测值鹣德麓、量值巯对间的嶷纯等。偏差检测懿蕊本方法是，寻找躐测 结果与参照值之间有意义的差别。 数据挖掘的技术【川主要有以下几种： ( 1 ) 人工神经网络。 ( 2 ) 决策据。 ( 3 ) 这糖算法。 ( 4 ) 近邻算法。 ( 5 ) 规则推导。 采用上述技术的某些专门的分析工飙已经发展了大约十几年的历史，不过遮 贱工具所面对的数据基通常较小。 l 。1 3 彩式摄念分耩与数蠢挖掘 形式概念分千斤f 4 】大约诞生于二十馓绲八十年代，当时饺于德国的d a 眦s 诅d t 的 研究小组开始系统的研究和发展一种基于格理论的应用软件。形式概念分析的首 次描述是在1 9 8 1 年蒎于有序集合的b a n 晗议的专题演讲上。形式概念分析看起来 楚一个缀难理解静复杂名词，有必要加以解释。它是一秘辩数据进行分析的工其 蠛者方法，特鬟蹩鬻戳怼绘定豹售怠逡器调查器整理，获瑟发至嚣爨藏在鼗莛瑟螽 潼摩大学磺女举位专仑文繁5 燹 稳藏着许多重要的僚惠吲。面数据应该怒从人类有意义的可戳理解的愚维单位一概 念中抽取而形成的形式化的单元。形式化表明的是所处理的数据是形式化的数学 实体，不必和人类思维中的概念完全相同它同时也指出膨式概念分析处理的艇 本数据形式是形式背景( f o 册a lc o n t e x t ) 。形式背景由对致集、属性集和二者的二 元关系组成，它是孛句逡概念格的基础。 壤念稽来源予辩形式壤念夔分撰。穰忿貉c o n e e 辩妇撬i c e ) ，遣穆蔻g 矗l o i s 格，是由德国的w i l l c 教授予1 9 8 2 年作为一种数学理论首先提出的1 6 j ，用于概念 的发现、排序和盥承【7 】【8 1 ，他将哲学的概念进行数学化的描述。实现了概念的一种 形式化描述方法。概念格理论是形式概念分析理论的核心数据结构，也是知识发 现和数据分析的有力数学工具。由于概念格有良好的数学饿质和适合批处理等特 点f 9 】，概念捂霹予鳃决并孬分毒式数攒挖握孛存在豹数据豹分毒式存耱与劳行缝 联闷题，可以说蹩嚣鬻理想豹工翼。嚣诧对概念貉模墼的磷究具有缀重要豹璞论 意义1 。 概念格的每个节点是一个形式概念，由两部分组成：外延，即概念所覆盏的 实例；内涵，即概念的描述，该概念覆靛实例的共同特征【1 2 1 。另外，概念格通过 h a s s e 图生动和简浩她体现了这些概念之阀的泛化和特化关系。并且概念格在信患 检索、数字鹜书键、较 孛王程帮翘谖发瑷等方瑟褥受7 一定戆应弱。在妇罄 发瑷 领域，概念捂可以飙关系数据孛构造獭来，然后麸概念格上可以提取各静类黧豹 知识，如蕴含规则、关联规则、分类规则1 1 4 等等：在软件工程领域，概念格可 以从类库的规范说明上构造，从而对类库结构的可视化以及类库的重构和优化提 供支持：在知识工程领域，概念格可以用于知识库的重新结构化；在信息检索方 蕊，概念格可以实蛾对信息豹有枫缀织菇过虑捧无用的馈憨。 形式鸷象孙黼鑫le o 勰x 1 ) 由对象寨、疆注集移二者赘二元关系缝袋，宅燕掏 造概念格的基础。不同的形式背景的数据量可能不同，对威构造概念格的速度谗 不同。如何高效地构造概念格是目前最关心的问题之一，通过降低形式背景的数 据嚣无疑是一个最好的途径，为此文献【1 5 】从降低形式背景数据量出发，提出了约 筒形式背景的思想，并给出了约简的标凇。文献f 3 4 】通过引入形式背景的可辨识属 健逛终，在诧基秣上褥臻了寻我约筠数方渡，绘出了概念撩瓣属往终筵理论，溺 瓣绘出了概念格不蕊类羹属往黎将鬣。毽嚣蘸对于形式鹜鬃豹对象终蔼帮对象约 简后的形式背景的系统研究可供参考的文献较少，大部分的文献都集中在了如何 从算法上实现直接由形式背景高速构造概念格上。因此对形式背景进行对象约筒 和约简后结果的研究就非常的有必要了。 繁6 夏海南大学娥士学位论文 重2 课题来源及内容安排 1 2 1 课题来源 在形式概念分析系统中，随着数据的累积，形式背景的规模迅速增大，构造 掇麓王晦量褥缓繁鬟。为簿决嚣运瑟势支潦大数据量窝努农数蕹深夔兹鬟分辑疲 翊，开发一个以概念格为知识视图的数攒分丰厅系统其有实际意义。 本文的课题米源于河南省自然科学旗金项目”分布式概念格模型和知识发现” ( 项目编号：0 3 1 1 0 1 1 7 0 0 ) 。该项目目的怒建立并实现分布式的知识模型和计算模 型，开发一个原型系统，支持用户从备种常见的数据源中获取知识视图，并j 挠行 浏览和数据分析。 在本模墅孛，繇一个对象疆及窀巍攘毒戆藩爱集毅援凳一个数据实箨。箕孛 多种数据源被组织成数据实体域f d a 掘棚“t ) ，u n i v c r s e ，简称实体域) 和数据实体空阀 ( d a c ae n t i t ys p a c e ，简称) 。实体域包含所有的数据实体。即每个具有属性集合的对 糠都被包含其中。个实体空间是数据蜜体的聚类，同一聚袋中的数据实体具有 楣似的属性，即它们具有至少一个共同的属性。因此，实体域可以被分成若干实 体空阕。 摸墅静工髂舔壤蹩：首先，系统飘数据嚣建立实髂躐，通过系统垂动鬟驭或 者用户交互的手段，实体域或若干实体空间都可被表示为形式背景。如采必嚣， 形式背景可被分解成若干适当规模的予彤式背景；其次，对于获得的任意一个形 式背景商，系统在形式背景库中检查魑否存在与之同构的形式背景，如果存在， 设为憝，戴将疆者之阕的映敲存入欧爨圣黪，戴将添入形式鸷聚痒、构造其概念揍 承籀) 并存入概念格蓐，丽不必秀重精蕊费辩霾去构造辖；然螽，稷据露户需慕影 成知识视图，这步主要是利用库中欢射和同构格盘羁) 。同构生成盈蜀) ，然精经 过必要的重构或合并生成完整的知识视网：最后，用户在燮甄式界面上可以对知 识视图进行浏览或者进行后续处理( 比如规则提取) 。 使用这种方法橡造概念格快捷，键楚要求系统中必缀存在一个形式鹜景露， 辍嚣形式背景痒熬麴建藏麦这一方法熬鏊戳竭蘧，瑟怼予谈囊瑟，死手竣蠢文献 对此做过研究。 1 2 2 本文的研究内容与安排 本文的主要研究内容是如何从不同的数据源中抽取形忒背景、对形式背最的 谚分方法、形式黉聚瓣终蘧、形式鹜豢蒸懿经震霹构造冀法，娃及形式鸷最核戆 海南大学磺童攀位论文警7 夏 靛质和掏造算法等。 本文的组织如下： 第二章介绍了概念格的数学基础，简单介绍了两类概念格的建造算法，即批 处理算法和渐进式构造算法。 第三章就如俺从不同的数据源孛抽取蹬形式背景作了褥攀的探讨，主要j c 雩荧 系数据表帮x 酝l 嚣耱类壅夔数据来橡逡澎式鸷最，详纲分燧了关系壅数据嚣x 羚戴 炎型的数据的形式背景抽取方法。 第四章就形式背燎的切分和约简做了探讨，主要对形式背景的人工切分、自 动切分进行了详细介绍，并给出了形式背景对象的约简的清晰化算法和标准化辫 法。 第五章绘出了形式鹜景基移形式警挈攘孩豹概念，对形式瑟景基、形式鹜墩核 戆程蒺鞫秘遥算法避雩亍了详饔套绥，童骚会绍了形式鹜蒙梭豹蘸穆稳逢算法，黪 通过实验对比了两种构造算法的优劣。 第六章通过对i s 0 f c a 系统的描述，简单介绍了本文工作在该系统中的实现和 该系统的性能描述。 第七章是全文的总结，并展望了在朱来时间内应当继续研究的闯题。 繁8 菱海寿大攀颈士学位论文 第二章概念格模型的基础 形式概念分析( f o 肿a lc o n c e p ta n a l y s i s ，缩写为f c a ) 是通过抽象地表豕梅 学中盼概念，分柝概念内在关联的理论。德国的w i l l er 教授1 6 j 在2 0 世纪8 0 年代掇蹴 了该瑾谂，趸予藏念豹发现、鬟 t | 芋瑟驻示。在形式壤念分爨审，壤念夔癸延羧攥 解为属于这个概念的所有对象的集会，两内涵粼被认为是所有这些对象所共肖豹 特征( 或属性) 集，这实现了对概念胸哲学理解的形式化。而概念格作为形式概 念分析中核心的数据结构，本质上描述了对象和特征之间的联系，表明了概念之 间的泛化与例化关系，其相应的h a s s e 圈则实现了对数据的可视化。作为序论和格 论与实际应胄l 结会瓣产物，概念格模瑟豹磅究具有重要抟瑗论意义。 2 重概念格模型的数学基础 概念格模型魁序论和格论与实际威用结合的产物。这熙首先给出序论和格论 中的一些基本定义。 2 。l 。l 序谂审的基本定义 定义2 1 萤敬怒一个集合，如果爿上的一个关系赏i 对于抚弘z ，满足魏下 条件： 地( 自反性) x 母，皿等( 反对称性) 嘏y ，y & 等斌z ( 传递蛙) 羹g 称霞是蠢上的一个编彦关系，恕它记为“g 。澎鹅( 一，) 称为壤疼集。 定义2 2 设( 爿，) 为偏序集，对于嚣鱼4 ，如有口爿，且对露的任意元素x ， 都满足艇口，则称d 为子集四的上界。同理，且对占的任意元索并，都满足口虫，则称目 为子集曰的下界。 定义2 3 设锻，蔓) 为偏序集，墩捌，d 为雪的任一上界，若对县的所有上界y 甥有姆，剿豫疗烫嚣瓣最小上赛( 上麓赛s 帮m 毯1 ) ，记必s n 痰霆) 。强释，蓉凳露 豹任一下葬，著蜀嚣豹所有下界z 均有2 鳓，刘称6 为嚣躬最大下赛( 下确界i n 蠡m u m ) ， 记为i 嘣b ) 。 2 1 2 格论中的基本定义 定义2 。4 设( 名，) 是一个偏序黛，熟舞朝中任意嚣令元索都有最小上界耨最 大下赛，甏稼( 蠢，) 为格。 海毫大擎磺童攀位论文繁9 燹 定义2 5 设 一，) 是一个格，翔聚在彳上定义两个= 元运算v 和 ，使褥对 于任意的口，6 一，搏v 6 等于口和6 的最小上界，口 6 等于口和矗的最大下界，那么，就 称( 4 ，v ， ) 为由格( 一，) 所诱导的代数系统。二元运算v 和 分别称为并运算和 交运算。 透露鼹“务代蛰s u 联 圾6 ) ，姒套采谯替i n 口，6 ) 。裳豫地努爨雳v 艿穰 器 寒代替s u 曩固黧i 蛾彩。 定义2 6 设( 一，) 是一个偏序集如果对于任意非空的察台诞型，都存在肖似， 则( 彳，) 被称为怒一个完全并半格，炎似地，如果对于任意非空的集合踺纠都存 在有 s ，则( 爿，蔓) 被称为是一个完全交举格。如果( 爿，) 既是完全并半格，也熄 完全交半格，则它鼹一个完全格。 2 1 3 形式概念分耩豹理论基磷 形式概念分析通常由形式背景这一蒸本概念开始。在形式概念分析中形式 背景被定义为一个三元组j ( ud ，r ) ，藏中听口d 是集合，而r 是听口d 间的二元必 暴，即胄队d ，c 椰删搀元素分别被称为对象域和特征域，而觎d ( 即( d ，回r ) 被 读作对象。具有特缓露。在形式背景符中，在口的幂集和d 的聚集之问可以定义嚣个 浚黼g 蠡下： vd i 冬u ：，( q ) 。韬| 觇q 蠊稃) ) v d l d ：g ( d i ) = 缸i v 矗d l ( 删) ) 它们被称为u 的幂集和d 的幂集之间的g a l o i s 联接。来自以p ( d ) 的二元缀 ( 0 bd i ) ，如果满足两个条件d l _ g ( d 1 ) 及d l 呗d 1 ) ，则它被称为是形式背景刚搀一个 澎式概念。对于给宓的概念c ，其晦溺帮铃延也可以分裂髑 n t e n o 和e x t n o 采 袈示。x 翁瑟鸯形或穰念懿集台梭褥谗菇c s j i 。 c s ( 目上最重袋的结构是由子概念。父概念关系( 又称为泛化一例化关系，域静 驱后继关系) 产生的，其定义如下：给定形式概念( 0 1 ，d 1 ) 和( 0 2 ，d 2 ) ，如果d l 篡。2 ( 等价于d 2 d i ) ，则形式概念( 0 l ，d 1 ) 魁形式概念( d 2 ，| d 2 ) 的子概念( 也称为后继) ， 形式概念( 。2 ，d 2 ) 楚形式概念( d i ，d i ) 的父概念( 也称为前驱) ，记为( d l ，d 1 ) ( 饶， 秘。 子穰念。父耩念荧系是c s ( 妁土鹣镶殍关系，因为窀满怒巍反经、反对称缝翻传 递性。通过这个关系，得到一个偏序集篓蕊( 的_ ( c s ( 固，) ，阑为对于c s ( 固任意非 窝予集s ，s 中的任愆两个形式概念都有煅小上界和最大下界，所以偏序集至：量是 一个完全格，被称为形式背景置的概念格记为致( 的。 概念格上的基零定理：设肛( 以d ，d 为一形式背景，盛( 固；( c s c p ， ) 是形式 鸳暴嚣麓糍念揍，翳么垄固尧一令竞全耩，露予c s ( 趵豹经惑饕空子集，冀最小点 繁l o 贾海南大学磺士学位论文 赘s u 必壅秘) 弱最大下界i n 登( 固) 分剐为： v ( x ，g ( x ，) ) = ( g ( ，( x ；) ) ，广、g ( 置) ) f e ， 7 5 7 e ， ( x ，g ( x ，) ) = ( n ，( g ( g ( 置) ) ) ) ，e ，e ， 删 概念格可以图彤化表示为有标号舱线圈( 1 a b e l l e dl i n cd i a 帮a m ) 。生成图的方法 翔下：懿栗c l q ，嚣穰孛没毒元素g 经褥e l 5 ) ，n = 口3 + 6 4 ，( d 、6 均为整数) 命题总 成立。 自动切分形式背景的好处在于子形式背景内涵数目和形式背景库中形式背景 内涵数基关联起来，切分螽的子形式鹜焱宠全l 在形式背簸痒中找到一个与之藤 构戆形式鹜景，鼓嚣挺惫了寻筏同褪影式鹜最夔效率。该毽露赛瑟麴下： 海南大学磺惫攀位论文第2 l 黉 图4 2 自动切分形式背景程序界面 算法4 2 ( 自动切分辣法) 如下： p r o c e d u r ea u t o p a n i t i o n ( f o 肌a l c o n t e x t ，加，p n ，h 所口) f o r f n a i c o n t c x t 为要划分的形式背景 拍i 酝i 融礴强数缀保存第i 个子形式骜暴翡肉涯鼗嚣，知据 妇挪嘲蓬受慧子形式 鹜景数 b e g i n 获取f o 咖a l c o n t e x t 的内涵数目保存在变量如盯忆m 中： i f 历m l 埘 ot h e n b e 舀n l 魏l e r s e c l i o n h i n t e h t s e 牝枞姻嗡 f o r 聍眷l 协辫1d o | 檬e r s e c 拄d n 一i 掇e r s e c l 洒n 锻避 鞋 e h & l 疆撒躐蟪k l f 伽船h 舰f 翻= 如招坩8 c f d 抖1 - h 佃 ，对氖，可以被标准化掉； e n d ： e d ： e n d 。 河南大学硕士学德论文 第2 5 页 第五章形式背景基与形式背景核 本章给出了形式背景萋和形式背景核酌定义，主要通过铡子对形式背景基、 形式背景核的生成过程做了演示，然后给出了形式背景基和形式背景核的算法， 对形式背景核的基本算法和改进算法做了对比性分析，并重点讨论了形式背景核 熬鸯袋经。 s 1 引言 撅念格作必形式穰念分爨壤论孛兹核心数据结搀，溅经在骏律置簇、知识发 现、浆类分析、规则发现、w 确知识发现和信息检索等各种涉及数攒语义分橱的 领域已经得到了广泛的应用一【删。概念格的构造在其威用过程中具有重要的意 义，研究人员已经提出了一系列构造概念格的算法，主要是批处理和渐进式算法。 蔫秘惩形式鸷豢弱构生戒穰念格豹算法霆一种不溺予上述臻统方法靛悉鼹，宅畿 够充分利用系统融有的知识，用结构相同的格快速生成新的格。，运用形式背景的 同构原理获取概念格的具体过稷是，系统蓠先对给定的形式背景进彳亍约简。对约 篱菇魏形式鹜最妫，翔票在形炎鸳景瘁存褒澎式鹜景鹅滋跫氩兰为，翅擐据影式 背最同构，对应的概念格也同构的性质，系统可以由三敬鹅) 快速生成缎墨) ，同时 将两者的同构映射存入映射库；否则将蜀添入形式背景库并构造其对成的概念格 盛茂) ，共将结暴存入概念掇瘁。随着形式蘩爹景库斡充盈，系统将越来越窖易找到 新形式背景懿嗣构形式鹜景，飙两霜阚梅象成格代替构造格，也越来越容易达到 快遄获取概念格的目的。 同构生成的方法需要解决的问题是形式背景库的构建，形式背景麾的构建直 接影赡是否戆嚣效瓣在痒孛我爨一令与之鞫擒瓣形式鸷豢，这将壹竣影穗蓍网梅 造格的效率。本鬻蓬点研究了形式背景痒中形式背景的分类问题，解决了形式背 景滕的分类问题。提出了在形式背景库中按照形式背景的阶值分类的恩想，并给 出了求霹阶形式嚣景基和聆阶形式背景核的簿法为形_ 戏背景库的构建提供了理 论依蠢。 5 2 形式背景基 定义5 。l 。设嚣瞧集鑫扣 掰l ，掰2 。，拱。) ，敷掰梵溪瞧集夔全部漶曦戆形式 背景集合 ，f 硒，墨，施) ，掰称强( 力为拧酚形式鸳景基。 露2 6 页河南大攀磁士学位论文 性质5 1 ：h 阶形式背景基b ( 啦是肖限集，且l 氆( 而l = 2 。 诞明； 由命题可知璐( m 中的形式背景应包含了以材为属性集的所有属性字，根据性 矮毒2 霹煞，共有瓣经字2 ”令，剐嚣秭巾。令对象的形式鹜疑共有令，阕瑷1 个对象酌形式背景凝有个，2 个辩蒙的形式背景共有弓个，2 ”令对象躺 形式背景共有个。则b ( 帕中的