（应用数学专业论文）godin算法的改进和fca在智能搜索引擎中的应用.pdf

y 7 3 9 0 7 河南大学硕士学位论文第1 页 摘要 传统的搜索引擎在进行搜索时会带来一些问题，比如查询信息过多或者不容 易找到查询的相关信息等，解决这问题的有效方法是研究智能搜索引擎，进行 智能化查询。由于形式概念分析中的概念格有良好的数学性质、适合批处理和能 表示概念之间的关系等特点，我们认为概念格模型是解决搜索引擎进行智能搜索 问题时的一种非常理想的工具。考虑到需要处理大量的数据，我们应用了分布式 概念格模型。本文的目的也就是分析概念格的数学模型，研究其数学性质，对概 念格的构造算法进行探讨，为概念格的分布式存储和并行运算提供理论基础，从 而进一步将概念格应用于智能搜索引擎。 本文内容如下： ( 1 ) 介绍了传统搜索引擎的缺陷，以及引入智能搜索引擎的必要性和可行性， 并且认为可以将概念格模型应用于智能搜索引擎的开发。 ( 2 ) 介绍了概念格的数学基础，包括与概念格模型相关的序论和格论中的一 些定义。给出了两类概念格的建造算法，即批处理算法和渐进式构造算法，并就 经典的批处理算法如b o r d a t ，c h e i n 算法，经典的渐进式构造算法j 1 1 g o d i n 算法做了 详细介绍，而且给出了改进的g o d i n 算法。 ( 3 ) 给出了分布式概念格的数学模型，重点讨论了在分布式概念格的数学模 型下，外延独立的两个同域概念格的并运算，研究高效的合并两个同域概念格的 算法。并对概念格的算法级并行构造作了介绍，介绍了并行计算的特点与现状， 并详细分析了一种并行构造算法。 ( 4 ) 就如何从不同的数据源中抽取出形式背景作了简单的探讨，主要对关系 数据表和x m l 两种类型的数据来抽取形式背景，详细介绍了关系型数据和x m l 类 型的数据的形式背景抽取方法。 ( 5 ) 针对基于f c a 的智能搜索引擎作了探讨，分析搜索引擎的特点以及智能 下雌c ：了 第1 i 页河南大学硕士学位论文 搜索引擎的引入的必要性和把f c a 应用于智能搜索引擎的可行性，找出f c a 应用于 智能搜索引擎中所要解决的两个关键问题并给出解决方案。 关键词：形式概念分析，概念格，分布式概念格，智能搜索引擎 河南大学硕士学位论文第1 i l 页 a b s t r a c t u s i n gt h et r a d i t i o n a ls e a r c he n g i n e sm a y c a a s es o m ep r o b l e m s s u c ha ss c a n n i n g t o om u c hi r r e l e v a n ti n f o r m a t i o no r s c a n n i n gl i t t l er e l e v a n ti n f o r m a t i o n ，i no r d e r t os o l v e t h e s ep r o b l e m s ，w et r yt of r e ds o m ee f f i c i e n tw a y s t h eo p t i m a lw a yi su s i n gi n t e l l i g e n t s e a r c he n g i n e i nf o r m a lc o n c e t pa n a l y s e ，c o n c e p tl a t t i c eh a sg o o dm a t h e m a t i c a l c h a r a c t e r sa n di ss u i t a b l ef o rb a t c h i n ga n dc a nb ed e n o t e dr e l a t i o n sb e t w e e n c o n c e p t s ， s oc o n c e p tl a t t i c em o d e li sa na d m i r a b l et o o lw h i l ed o i n gs e a r c ho ni n t e l l i g e n ts e a r c h e n g i n e c o n s i d e r i n gt h a tw eh a v et op r o c e s sal o to fd a t a , w ec h o o s et h ed i s t r i b u t e d c o n c e p tl a t t i c em o d e l t h ea i m o ft h i sp a p e ri st oi n t r o d u c et h em a t h e m a t i c a lm o d e l so f c o n c e p tl a t t i c e ，s t u d y i t sm a t h e m a t i c a l p r o p e r t i e s ，d i s c u s s t h el a t t i c ec o n s t r u c t i o n a l g o r i t h m s ，a n dp r o v i d em a t h e m a t i c a lf o u n d a t i o nf o ri t sd i s t r i b u t e ds t o r a g ea n dp a r a l l e l p r o c e s s i n g f o l l o w i n gt h e s es t e p s ，w ew i l ld os o m ep r e p a r a t o r ys e a r c ho l li n t e l l i g e n t s e a r c he n g i n e ( 1 ) t h ed e f e c t si nt h et r a d i t i o n a ls e a r c he n g i n es y s t e ma r ei n t r o d u c e di n c l u d i n gt h e n e c e s s a r i t ya n dt h ep o s s i b i l i t yo ft h ei n t e l l i g e n ts e a r c he n g i n e i ta l s oa p p e a r st h a t c o n c e p tm o d e lc a r tb er e a d i l ya p p l i e dt o t h ed e v e l o p m e n to ft h ei n t e l l i g e n ts e a r c h e n g i n e ( 2 ) i n t r o d u c e t h em a t h e m a t i c a lf o u n d a t i o n so ft h e c o n c e p t l a t t i c ea n ds o m e d e f i n i t i o n si nl a t t i c et h e o r y 聃s a m ea sc o n c e p tm o d e lr e l a t e do r d e rt h e o r y w eg i v et w o k i n d so fl a t t i c ec o n s t r u c t i o na l g o r i t h m s ：b a t c ha l g o r i t h m sa n di n c r e m e n t a la l g o r i t h m s t h ed e t a i l so fc l a s s i c a lb a t c ha l g o r i t h m s ，s u c ha sb o r d a ta n dc h e i na l g o r i t h m s ，a n d c l a s s i c a li n c r e m e n t a la l g o r i t h m ss u c ha sg o d i na l g o r i t h m sa r ei n t r o d u c e dp a r t i c u l a r l y , m o r e o v e r , p r o p o s e a l li m p r o v e dg o d i n a l g o r i t h m ( 3 ) w eb u i l dam a t h e m a t i c a lm o d e lo f d i s t r i b u t e dc o n c e p tl a t t i c ea n dd i s c u s st h e 第1 v 页河南大学硕士学位论文 u n i o no p e r a t i o nt oc o m b i n et w oe x t e n t i o n i n d e p e n d e n ts a m ef i e l dl a t t i c e s ，a n db e s i d e s ， i n t r o d u c e c o n c e p t l a t t i c e a l g o r i t h m s a n di t s p a r a l l e lc o n s t r u c t i o n a l s o ，g i v e a d e s c r i p t i o no f t h ec h a r a c t e r sa n dt h ea c t u a l i t yo f p a r a l l e lc a l c u l a t ew i t l la ne x h a u s t i v e a n a l y s i so f o n e o f t h e p a r a l l e lc o n s t r u c t i o na l g o r i t h m s ( 4 ) d i s c u s sh o w t oe x t r a c tf o r m a lc o n c e p tf r o md i f f e r e n td a t as o u r c e s m a i n l y f r o mr e l a t i o nd a t ab a s et a b l e sa n dx i v l l ( 5 ) d i s c u s st h ei n t e l l i g e n ts e a r c he n g i n eb a s e do n f c a a n a l y z i n g t h ec h a r a c t e r so f t h er o u t i n es e a r c he n g i n e sa n dt h en e e e s s a r i t yo ft h ei n t r o d u c t i o no ft h ei n t e l l i g e n t s e a r c he n g i n e ，f u r t h e r m o r et h ep o s s i b i l i t yo ft h ea p p l i c a t i o no ft h ef c at oi t 。f i n do u t t h es o l u t i o n so ft h et w ok e yp r o b l e m sw h i l ef c ai sa p p l i e dt ot h ei n t e l l i g e u ts e a r c h e n g i n e k e y w o r d s , f o r m a lc o n c e p ta n a l y s i s ，c o n c e p tl a t t i c e , d i s t r i b u t e dc o n c e p t l a t t i c e ，i n t e l l i g e n ts e a r c he n g i n e 河南大学硕士学位论文第1 页 第一章引言 本章首先介绍了传统搜索引擎的工作方式、智能搜索引擎的引入、概念格的 简单介绍、形式概念分析( f o r m a lc o n c e p t a n a l y s i s ，缩写为f c a ) 技术在智能搜 索引擎中的应用。然后给出本文所要做的主要工作：即分析概念格的构造算法， 并提出一种改进算法，建立概念格的分布式模型，以及b c a 应用于智能搜索引擎 时的两个关键问题及其解决方法。 1 1 智能搜索引擎的引入 席卷而来的i n t e r n e t ( 因特网) 正将全世界的丰富信息资源带到每一个人的 面前，从爆炸性增长的数字信息中迅速地获得用户需要的信息变得越来越困难， 这给搜索技术提供了一个广阔的舞台。为了帮助用户顺利检索和查找所需的网络 信息，一大批搜索引擎应运而生。网络搜索引擎的硖究与开发已成为当今网络信 息检索的热点，搜索引擎技术越来越引起人们的关注。搜索引擎已日益成为人们 只常生活中必不可少的一部分，成为人们在信息海洋中进行“大海捞针”的工具。 然而目前搜索引擎又面临一系列的挑战，如网络信息量迅猛增加，人工已经无法对 它们进行有效的分类、索引和利用；简单的关键词搜索。返回的信息量过大，己 经让用户无法承担；网络信息组织的无序性；信息有用性评价困难；网络信息日 新月异的更变；信息媒体的多样化：带宽等其它因素的制约，这些都给因特网信 息的获取造成了极大的阻碍。这就给了智能搜索引擎出现的机遇，也给了它发展 的空间。现在已经出现了能初步满足用户需求的智能搜索引擎，并在不断的壮大。 1 1 1 传统搜索引擎的缺陷 搜索引擎是一种浏览和检索网络中所有信息的工具。一般说来，搜索引擎都是 通过某种界面跟用户交互，接受用户查询特定信息的请求，然后对用户查询请求 进行分析，并在i n t e r n e t 后台的索引数据库中不断进行匹配，挑出符合条件的信 息，同时按照匹配程度的高低对结果进行排序，最后将排序后的结果返回给用户。 用户最关心的是搜索结果是否能够满足自己的需要，尤其是当搜索引擎可以 获得的信息资源非常多的情况下。目前采取的一种常见的策略是将用户的查询请 求分解成若干关键字，根据这些关键字计算信息和用户请求的匹配程度，从而挑 第2 页河南大学硕士学位论文 出若干匹配的文档，不同的搜索引擎采取的匹配策略是不同的，从而也使不同的 搜索引擎的搜索效率也是不同的。 传统的搜索引擎一般使用两种技术来实现这种对信息的检索。一种是使用网 站分类技术，即把网站进行树状的归类，登录的网站至少属于一个类别，并对每 个站点都有简略的描述。由于使用了人( 专家) 来对网站进行归纳和分类，它为网 络信息导航带来了极大的方便，广受人们的欢迎。但是它具有成本较高、对网站 的描述过于简略、不能深入网站的内部细节等缺陷，因此用户查询不到网站内部 的重要信息，造成了信息丢失。另一种是使用全文检索技术，全文检索技术处理 的对象是文本，它能够对大量文档建立由字( 词) 到文档的倒排索引，在此基础上， 用户使用关键词来对文档进行查询时，系统将给用户返回含该关键词的数据。全 文检索已是一个很成熟的技术，它能够解决对数据细节的检索问题。从理论上说， 网络数据中出现了某个关键词，就能够使用全文检索的关键词匹配把该数据查出 来，但是这又导致产生了新的缺陷，即返回的信息太多。更严重的是，除了综合 性的搜索引擎站点有这个现象之外，现在较大的站点对自身内部信息的检索也会 返回大量的查询结果。它还有两个会给检索带来很大的困难、也是很关键的问题， 即词汇的“忠实表达”问题和词汇的“表达差异”问题，它们虽然不太直观，但 确是在检索中的深层次的问题。目前在大多数搜索引擎中的全文检索使用的都是 基于关键词匹配，基于关键词匹配的搜索技术有较大的局限性。首先，它不能区 分同形异义；其次，不能联想到关键词的同义词。 由于现在大多数网站使用的是传统的关系数据库对信息进行组织和存储，因 此其使用的搜索引擎也是基于关系数据库的，这种传统的关系数据库非常擅长处 理结构化的数据，而且经过长期的发展，其功能现在已经相当的完善，但其对于 非结构化的数据的处理能力则很弱。它无法处理在用户看来是非常普通的常识性 知识，更不能处理随着用户不同而变化的个性化知识，随地域不同丽变化的区域 性知议以及随着领域不同而变化的专业性知识等”1 。 从上面的分析可以看出，传统搜索引擎所使用的技术都难以解决用户“找信 息难”的问题。造成这种困难的实质在于搜索引擎缺乏知识处理能力和理解能力， 对要检索的信息仅仅采用机械的关键词匹配来实现，把信息检索从目前基于关键 词层面提高到基于知识( 或概念) 层面，是解决问题的根本和关键，即将搜索引挈 智能化，这就是我们所讲的智能搜索引擎。这是未来搜索引擎发展的趋势。 1 1 2 概念格及其在搜索引擎中的应用 概念格，也称为g a l o i s 格，它是由w i l i er z j ：1 9 8 2 年首先提出吲，用于概念的 河南大学硕士学位论文第3 页 发现、排序和显示。作为序论和格论与实际应用结合的产物，概念格直都被认 为是进行数据分析的有力工具，对概念格模型的研究具有很重要的理论意义【7 l 【 。 由于概念格有良好的数学性质和适合批处理等特点 2 4 1 1 3 5 】，概念格对于解决并行分 布式数据挖掘中存在的数据的分布式存储与并行处理问题，可以说是非常理想的 工具。 概念格的每个节点是一个形式概念，由两部分组成：外延，即概念所覆盖的 实例；内涵，即概念的描述，该概念覆盖实例的共同特征【5 6 1 。另外，概念格通过 h a s s e 图生动和简洁地体现了这些概念之间的泛化和特化关系。并且概念格在信息 检索、数字图书馆、软件工程和知识发现等方面得到了一定的应用。在知识发现 领域，概念格可以从关系数据中构造出来，然后从概念格上可以提取各种类型的 知识，如蕴含规则、关联规则、分类规则等等；在软件工程领域，概念格可以从 类库的规范说明上构造，从而对类库结构的可视化以及类库的重构和优化提供支 持；在知识工程领域，概念格可以用于知识库的重新结构化；在信息检索方面， 概念格可以实现对信息的有机组织并过虑掉无用的信息。而且，有人指出概念格 将会在生物和生命科学领域有重大应用。 目前，已经有了一些构造概念格的算法，这些算法主要可以分为两大类：批 处理算法和渐进式算法，在应用概念格的过程中，由于所要处理的数据大多数情 况下都是大批量的，所以概念格的构造效率始终是人们关注的问题，人们对此进 行了广泛的研究，提出了各种不同的构造算法。这些算法主要可以分为两大类： 批处理算法和渐进式算法，批处理算法的思想是首先生成所有概念，然后根据它 们之间的直接前驱一后继关系，生成边( 格结点的偏序关系) ，完成概念格的构造， 例如b o r d a t 的算法，o s h a m 算法，c h e i n 算法。g a n t e r 的算法，n o u r i n e 的算法等； 渐进式算法的思想首先初始化概念格为空，将当前要插入的对象和现有格中所有 的形式概念作交运算，根据交的结果不同采取不同的行动，典型的算法有g o d i n ， c a p i n e t o 和t b h o 的算法。国内对上述的有些算法做了一些改进，例如改进了的 b o r d a t 算法挖掘关联规则、扩展概念格的渐进式构造算法，基于索引树的概念格渐 进式构造算法等。渐进式算法被认为是比较有前途的一类。在渐进式构造概念格 的算法中，g o d i n 所提出的算法取得了良好的效果。本文中提出一种算法，该算法 对g o d i n 算法做了一些改进，减少了部分情况下的时间复杂度。 基于分布式概念格模型的知识发现可以得到很广泛的应用，其中的一个应用 就是语义w e b 方面。语义w e b 的一个重要应用就是智能搜索引擎。如前所述，搜索 引擎是一种能够通过i n t e r n e t 接受用户的查询指令，并向用户提供符合其查询要求 的信息资源网址的系统。它是一些在w e b 中主动搜索信息( 网页上的单词和特定的 描述内容) 并将其自动索引的w e b 网站，其索引内容存储在可供检索的大型数据库 第4 页河南大学硕士学位论文 中，建立索引和目录服务。一些搜索引擎搜索网页的每个单词，而另一些搜索 引擎则只搜索网页的前二百至五百个单词。当用户输入关键词( k e y w o r d ) 查询时， 该搜索引擎会告诉用户包含该关键词信息的所有网址，并提供通向该网络的链按。 搜索引擎既是用于检索的软件又是提供查询、检索的网站。 搜索引擎有3 个标准：查准率，查全率，搜索速度。其中的查准率是一个比较 重要的标准，也是用户最关心的问题。大部分的搜索引擎按照用户输入的关键词 进行查询时，仅仅是按照逻辑条件进行字符串匹配，然后查询出用户需要的信息。 显然，用这种方式进行搜索，查准率不太高，因为纯粹的字符串匹配并没有考虑 到字符串的本身含义，换句话说，也就是关键词本身是个概念。如果从概念的角 度进行搜索，可以过滤掉许多内容与关键词无关的信息，查准率将会大大提高， 并且可以搜索到许多与关键词在概念上相关的信息，大大提高了搜索的知识面。 智能搜索引擎可以提高查准率和查全率。搜索速度也是一个很重要的标准，这很 大程度上取决于搜索时采用的算法。将f c a 应用于智能搜索引擎系统中时，需要 解决两个关键的问题。第一个问题是从搜索结果中抽取出形式背景，第二个是如 何将搜索结果生成概念格并显示给用户，以方便用户分类查看。智能搜索引擎的 工作原理是建立在搜索时所要处理的对象是一个概念这一基础之上的，那么抽取 概念是非常重要的，本文的重点就是如何构造形式背景、如何生成形式概念、对 形式概念的运算以及构造出智能搜索引擎的模型，从而为智能搜索引擎的开发打 下基础。 1 2 本文的研究内容与安排 本文的主要研究内容是如何从不同的数据源中抽取出形式背景、对概念格构 造算法( g o d i n 算法) 进行改进，以及将f c a 应用于智能搜索引擎时要解决的问题 等。 本文的组织如下： 第二章介绍了概念格的数学基础，给出了两类概念格的建造算法，即批处理 算法和渐进式构造算法，并就经典的批处理算法如b o r d a t ，c h e i n 算法，经典的渐进 式构造算法如g o d i n 算法做了详细介绍，并给出一种改进的算法和一种快速构造算 法( 基于索引树的构造算法) 。 第三章中针对随着数据量增大产生的概念格的时间复杂性和空间复杂性问 题，提出了用高性能并行计算机的计算与存储能力来解决这一问题。但就数据分 布式存储与并行处理本身来说，如何合理有效地组织数据的分布式存储与并行处 理无论在理论上还是在技术上都有许多问题需要研究。本文给出了分布式概念格 河南大学硕士学位论文第5 页 的数学模型，重点讨论了在分布式概念格的数学模型下，外延独立两个同域概念 格的并运算。并对概念格的算法级并行构造作了介绍，介绍了并行计算的特点与 现状，并详细分析了一种并行构造算法，最后给出对并行算法具体实现的构想。 第四章就如何从不同的数据源中抽取出形式背景作了简单的探讨主要对关 系数据表和x m l 两种类型的数据来构造形式背景，详细介绍了关系型数据和x v l l 类 型的数据的形式背景抽取方法。 第五章就基于f c a 的智能搜索引擎作了探讨，分析搜索引擎的特点以及智能 搜索引擎的引入的必要性和把f c a 应用于智能搜索引擎的可行性，找出f c a 应用于 智能搜索引擎中所要解决的两个关键问题并给出解决方案。 第六章是全文的总结，并展望了在未来时间内应当完善的问题。 第6 页河南大学硕士学位论文 第二章概念格模型的基础 在哲学中，概念被理解为由外延和内涵两个部分所组成的思想单元。基于概 念的这一哲学理解，德国的w i l l er 教授【38 】提出了形式概念分析理论，用于概念的 发现、排序和显示。在形式概念分析中，概念的外延被理解为属于这个概念的所 有对象的集合，而内涵则被认为是所有这些对象所共有的特征( 或属性) 集，这 实现了对概念的哲学理解的形式化。而概念格作为形式概念分析中核心的数据结 构，本质上描述了对象和特征之间的联系，表明了概念之间的泛化与例化关系， 其相应的h a s s e 图则实现了对数据的可视化。作为序论和格论与实际应用结合的产 物，概念格模型的研究具有重要的理论意义。 2 - l 概念格模型的数学基础 概念格模型是序论和格论与实际应用结合的产物，这罩首先给出序论和格论 中的一些基本定义酊。 2 1 1 序论中的基本定义 定义2 1 设a 是一个集合，如果a 上的一个关系r ，对于v x ，y ，z a ，满足如 下条件： x r x ( 自反性) x r y ，y r x jx = y ( 反对称性) x r y ，y r z x r z ( 传递性) 则称r 是a 上的一个偏序关系，把它记为“”。序偶 a ，9 称为偏序集。 定义2 2设 a ，p 为偏序集，对于b a ，如有a e a ，且对b 的任意元素x ，都 满足x a ，则称a 为子集b 的上界。同理，且对b 的任意元素x ，都满足a x ，则称a 为子集b 的下界。 定义2 3 设 a ，9 为偏序集，b c _ a ，a 为b 的任一上界，若对b 的所有上界y 均有a ( y ，则称a 为b 的最小上界( 上确界s u p r e m u m ) ，记s u p ( b ) 。同样，若b 为b 的任一下界，若对b 的所有下界z 均有痤b ，则称b 为b 的最大下界( 下确界i n f i m u m ) ， 记为i n f ( b ) 。 河南大学硕士学位论文第7 页 2 1 2 格论中的基本定义 定义2 4 设 是一个偏序集，如果a 中任意两个元素都有最小上界和最 大下界，则称 a 9 为格。 定义2 5 设 a ，9 是一个格，如果在a 上定义两个二元运算v 和 ，使得对于 任意的a ，b e a ，a v b 等于a 和b 的最小上界，a a b 等于a 和b 的最大下界，那么，就称 为由格 a ，9 所诱导的代数系统。二元运算v 和a 分别称为并运算和交运 算。 通常用a v b 来代替s u p ( 如b ) ，a a b 来代替i n f ( a ，b ) ) 。类似地分别用v b 和 b 来代替s u p ( b ) 和i n f ( b ) 。 定义2 6 设 a ，是一个偏序集如果对于任意非空的集合s g a ，都存在有v s ， 则 a ，9 被称为是一个完全并半格，类似地，如果对于任意非空的集合s _ c a 都存在 有a s ，则 a ，p 被称为是一个完全交半格。如果 a ，既是完全并半格，也是完 全交半格，则它是一个完全格。 2 1 3 形式概念分析的理论基础 形式概念分析通常由形式背景这一基本概念开始。在形式概念分析中形式背 景被定义为一个三元组k j m ，d ，i ) ，其中u 和d 是集合，而i 是u 和d 间的二元关系， i p i c u d ，u s n d 的元素分别被称为对象域和特征域，而o l d ( 即( o ，d ) e i ) 被读作 对象0 具有特征d 。在形式背景k 中，在u 的幂集和d 的幂集之间可以定义两个映射f 和g 如下： 可d l u ：厂( d i ) = d f v x d l ( x r d ) v d l d ：g ( d i ) = x i v d d l ( 艽尺d ) ) 它们被称为u 的幂集和d 的幂集之间的g a l o i s 联接。来自p ( u ) p ( d ) 的二元组( 0 1 d 1 ) ，如果满足两个条件0 1 = 甙d i ) 及d l - - - f ( o i ) ，贝f j 它被称为是形式背景k 的一个形式 概念。本文中对于给定的概念c ，其内涵和外延也可以分别用i n t e n t ( c ) l f i e x t e n t ( c ) 来表示。k 的所有形式概念的集合被标记为c s ( k ) 。 c s ( k ) 上最重要的结构是由亚概念。超概念关系( 又称为泛化一例化关系，或前 驱后继关系) 产生的，其定义如下：给定形式概念( o l ，d 1 ) 和( 0 2 ，d 2 ) ，如果0 1 0 2 ( 等价于d 2 g d l ) ，则形式概念( o l ，d 1 ) 是形式概念( 0 2 ，d 2 ) 的亚概念( 也称为后继) ， 形式概念( 0 2 ，d 2 ) 是形式概念( 0 l d 1 ) 的超概念( 也称为前驱) ，记为( o l ，d 1 ) 氧0 2 ， 第8 页河南大学硕士学位论文 d 2 ) 。 亚概念一超概念关系是c s ( k ) 上的偏序关系，因为它满足自反性、反对称性和 传递性。通过这个关系，得到一个偏序集盟( k ) c s ( k ) ， ) ，因为对于c s ( k ) 任意非 空子集s ，s 中的任意两个形式概念都有最小上界和最大下界，所以偏序集至鲞( k ) 是一个完全格，被称为形式背景k 的概念格，记为l ( k ) 。 概念格上的基本定理：设k = ( u ，d ，i ) 为一形式背景，l ( k ) = ( c s ( k ) ，s ) 是形式背 景k 的概念格，那么l ( k ) 为一个完全格，对f f - c s ( 1 0 的任意非空予集，其最小上界 s u p ( l ( k ) ) 和最大下界i n f ( l ( k ) ) 分别为： v ( x ，g ( x ，) ) = ( g ( ，( v x ，) ) ，( - 3 9 ( x ，) ) | e | 3 目 ie j a ( x ，g ( x 瑚= ( n x 。，厂( g ( v g ( x ，) ) ) ) i e ， ，e ， 拒。 概念格可以图形化表示为有标号的线图( 1 a b e l l e dl i n ed i a g r a m ) 。生成图的方法 如下：如果c i c 2 ，且格中没有元素c 3 使得c 1 c l 的节点c 3 ， 有i n t e m ( c 3 ) n f ( x * ) i n t e r s e c t i o n ；则c l 被称为是一个产生于格节点。 一个更新格节点c 显然不是一个产生子格节点，因为 i n t e r s e c t i o n = d l n f ( x ) = d i 。如果l 中的一个概念节点既不是更新格节点也不是产生 子格节点，则它被称为是一个不变节点。 对于r 中的任意一个节点c ，如果不存在l 中的某个节点c 1 满足 i m e m ( c 1 ) = i n t e n t ( c ) ，则c 被称为一个新生节点：否则它被称为一个继承节点。如果 c i 是一个产生子格节点，节点( e x t e n t ( q ) u x * ) ，i n t e n t ( q ) c 、f ( x + ) ) 显然是”中的一 个新生节点，它被称为是由c 1 产生的新生的节点。 对于产生子格节点，有如下几个定理： 定理2 1 给定概念格l ，和要插入的新对象x ，l 中的节点c i 是一个产生子格 节点当且仅当 ( 1 ) - ，( i n t e n t ( c 。) 量f ( x + ) ) 且 ( 2 ) 一3 c 2 b e f o r e ( g ) ( i n t e n t ( c 2 ) = i n t e n t ( c 1 ) nf ( x + ) ) b e f o r e ( c 一表示所有先于c ，被访问的格节点和所有先t e l 被生成的新生格 节点的集合。访问顺序是按照l 中格节点的内涵从, b n 大的顺序访问的，这样就能 保证c 1 的前驱节点先被访问到，从而满足产生子格节点的定义。 定理2 2 如果c l 是产生子节点，它对应的新生格节点为c 。，则l 中满足 i n t e n t ( c 2 ) _ 3 i n t e n t ( c ) 的概念c 2 必然满足i m e n t ( c z ) i n t e r i t ( c 1 ) 。 河南大学硕士学位论文第1 3 页 定理2 2 说明了对于某个对于某个新增节点，除了其产生子外，所有的其它旧 节点都不可能成为其子节点。 定理2 3 对于两个新生格节点分别是c 。l 和c 。c w 2 ，如果 h n 韵l ( c 睇w f ) c i 丑e 吼( 岛。w 2 ) ，则c 。? 必然是先于c r 船被生成的。 定理2 3 说明了对于某个新增节点c 。，任何先于c 。c w 被生成的新增节点都不可 能成为其子节点。 可以用表2 1 来表示插入对象x 时对概念格的更新操作。 节点类型外延内涵父节点子节点 更新节点c增加x 不变不变可能增加某些由 满足c ， c 的产 生子c ，所生成 的新节点，并且 去除产生子：宵点 ( 当产生子是c 的子节点时) 产生子节不变不变增加新节点，并且如不变 点c果新节点在c 和c 的 一个父节点之间时， 去除这个父节点 非产生子不变不变不变 不变 廿点 新生节点 e x t e n t ( c ) u x 3i n t e n t ( c ) c 、f ( x + )可能增加某些满足 增加产生子以及 ( 其产生c 1 c 子为c )某些由满足c 2 c 2 的节点c 2 。c i = ( 0 l ，d 1 ) 为产生子 格节点，存在i n t e n t ( c 2 ) n f l x * ) = d ln ，( x + ) ，那么c 2 不是产生子格节点，相应的不 能产生新生格节点。更新格节点则比较简单，直接修改格节点的外延集即可。这 就完成了格节点的生成。 可以证明，新生格节点的父节点必然是某个新生格节点或者更新格节点，这 就大大简化了确定与新生格节点具有父子关系的格节点的过程。由文献【1 5 可知， 对于一个新生格节点，它所对应的产生予格节点必定是它的一个孩子，这个新生 格节点可能不存在另外的孩子( 这种情况适用于f l 二l s u p ( l ) 这个格节点生成的新生格 节点) ，如果存在另外的孩子的话，那么，该新生格节点的另外的孩子一定是新生 格节点。这样，当更新整个格的边信息时，只需在更新格节点、产生子格节点和 新生格节点之间寻找具有父子关系的格节点，并产生相应的边信息插入到原来的 边信息集合中。由前面叙述知，边信息的更新过程中，有可能产生不满足条件的 边( 格中不存在个格节点的两个子节点之间存在父子关系) ，在寻找和新生格节 点具有父子关系的格节点过程中，本文采用的算法是巧妙利用图的深度优先遍历 算法( 见下文算法描述) ，可以保证不会产生不满足条件的边的情况。这就可以减 少检查不满足条件的边所依附的格节点的范围，只需检查更新格节点即可，判断 更新格节点的子节点集合中的任意两个子节点是否存在父子关系，不妨设边集合 为c c d g ，c u p d 为更新格节点，它的子节点集合为c h d l ( c u p d ) ，对于任意c i ，c j c h d ( c u p d ) ，如果存在( c i - - c j ) c e d g ，则从c c d g 除去边( c u p d c ：i ) 。这便完成了边的 更新的过程。 第1 6 页河南大学硕士学位论文 2 3 2 算法改进及描述 ( 1 ) 深度优先遍历算法，用来寻找新生格节点的子节点；实现方法是通过增 加格节点的说明信息：内涵集合中的元素个数和父节点信息。其中，内涵集合中 的元素个数用来说明该新生格节点在所有新生格节点中的“地位”，辅助找出该新 生格节点的子节点( 因为该新生格节点的所有子节点的内涵集合的元素个数都小 于该新生格节点的内涵元素个数) ：父节点信息用来说明该新生格节点的父节点情 况，通过添加父节点信息并继承父节点的父节点信息( 如，g 的父节点信息是 g ，g ，6 ) ，g 又是的父节点，那么& 的父节点信息为 岛，易，gg ，避免产生 不满足条件的边。例如，对某一新生格节点g 。，在寻找其予节点的过程中，找出 有一格节点满足是其子节点的条件，但是发现c 的父节点信息中已经存在g 。，则 不产生边。一。 本算法实现格构造时，前端使用c 撑n e t ，生成的格节点信息和边信息分别保 存在后端的m ss q ls e r v e r 数据库中。 p r o c e d u r ed e p t h ( n o d e ) n d 如为保存在数据库中的一条保存格节点信息的记录： 找出节点n o d e 的父节点信息： 从数据表的新生格节点和更新格节点中找出内涵集合元素个数大于n o d e 的 内涵集合元素个数，返回集合c o 州b d e ，并按内涵集合中的元素个数从小到大排序 i f ( c o l n o d e l e n g t h 1 ) c o n o d e l e n g t h 表示集合的长度 ( 直接返回； f o r ( i n t i = 0 ：j c o l n o d e l e n g t h ： + ) 取出c o l n o d e j 的父节点信息： i f( c o l n o d o 力的父节点信息已经包含了节点n o d e ) 跳出此次循环： ) e l s ei f ( n o d e 是c o l n o d e i 的父节点) 添加边( 打。幽一c o 眦出 扪： 修改c o n o d e e i 的父节点信息： 河南大学硕士学位论文第1 7 页 d e p t h ( c o l n o d e i ) ； f ( 2 ) g o d i n 算法改进实现。设原始概念格中的i n f ( d 元素为6 ，特殊处理矗 与新增对象胖的特征集f ( 胖) 的交集运算f ( 斛) f 3i n t e n t ( c 。) ；然后对格中剩余元 素的内涵集合中内涵元素个数从小到大进行排序，依次取出元素与蜴，作运算 i n t e n t ( c j ) nf ( 肿) ，判断e 的相应类型，作相应的操作。利用数据库的排序和出 错处理，减轻了大量的查找和判断过程，从而提高了算法的性能。 输入：形式背景( z 口励所对应的原始概念格信息，新增对象一和：特征集 f ( 一) 输出：形式背景( x u 胖) ，口励所对应的概念格胁信息 从中读取所有格节点信息，并按内涵元素个数从小到大排序，返回集合 c o l l ； 取出c o l l ，的第一个元素g 因为是完全格，i n f ( l ) 一定为内涵元素个数最小的格节点：