概念格分布处理及其框架下的知识发现研究

《概念格分布处理及其框架下的知识发现研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、上海大学博士学位论文摘要概念格以其良好的数学性质己成功地应用于知识发现等诸多领域，但由于概念格自身的完备性，构造概念格的时间复杂度一直是影响形式概念分析应用的主要障碍。概念格应用的前提是概念格的构造。现在概念格的渐进式构造算法表现出了更强的生命力和适应性。但目前基本上都是属于基于对象的渐进式算法，而基于属性的构造算法未见报告。实际上，形式背景中数据的变化应该包括两个方面：一是对象的增减，二是属性的增减。增加属性可能使原来不能区分的对象能够区分，删除属性就可能使原来属于不同类的对象变为同一类。通过对概念格中概念之间的相互关系的了解

2、，和对象和属性之间相互关系的研究，本文提出并实现了基于属性的概念格构造算法，特别是基于属性的渐进式生成算法。它不仅为概念格的生成提供了一种新的方法，而且解决了在己构造好概念格的前提下，增加属性所带来的概念格更新问题，另外，它也为分布式存储的形式背景的概念格横向合并提供了基础。随着处理的形式背景的增大，构造概念格的时空复杂度也会随着急剧增大。研究采用新的方法和手段来构造概念格，就成为概念格研究的主要内容之～。现在已经提出的构造概念格的多种算法基本上是针对单个概念格的。采用分治策略来构造概念格是解决这一问题的有效途径。概念格的分布处

3、理就是通过形式背景的拆分，形成分布存储的多个子背景，然后同时构造相应的子概念格，荐由子概念格的合并得到所需的概念格。由于概念格是其形式背景中的概念间关系的表现形式，它和对应的形式背景是一一对应的。因此，对概念格的分布处理必然涉及到形式背景的拆分、合并等处理。本文从形式背景的并置和叠置出发，定义了两种类型的形式背景和概念格；并对不一致背景的处理进行了研究：证明了横向合并的子形式背景的概念格和子背景所对应的子概念格的横向并是同构的；结合子概念格中概念间固有的泛化一特化关系，继承已有的概念格渐进式构造的算法，并对其进行改造，形成能满足

4、多个子概念格合并处理要求的算法。数据挖掘是自动从数据中提取出人们感兴趣的潜在的可用信息和知识，并将提取出来的信息和知识表示成概念、规则和模式。关联规则是发现知识的主要形式。提取关联规则的主要步骤是频繁项集的获取，而一个事务数据库中频繁项集的数量往往很庞大，从频繁项集中提取的规则就会很多，且存在大量的冗余。为了缩减频繁项集的数目同时也不丢失有用信息，现在采用用频繁封闭项集来提取最小无冗余的关联规则。V上海大学博士学位论文本文通过对现有利用频繁封闭项提取规则算法的仔细研究和分析，结合概念格的特点，对基于概念格提取最小无冗余关联规则进

5、行了较深入的研究。为了便于提取最小无冗余关联规则，定义了量化封闭项集格，发现了提取最小无冗余关联规则的关键是找出格中每个节点的项集所对应的同交易的频繁项集集合中的最小项集的集合，并给出采用幂集和差集两种方案分别获取该最小项集的集合SLIT的算法；给出了从量化封闭项集格直接提取最小无冗余的关联规则的算法。为了进一步减少所提取规则的数量，以满足用户的特定需要，本文还提出了全局简洁关联规则的概念，并给出了利用概念格提取全局简洁关联规则的算法。目前研究关联规则提取的工作很多，但研究规则的更新的工作相对较少。实际上，规则的更新问题和规则的

6、提取问题一样，也是知识发现研究的重要环节。本文为了实现对最小无冗余的关联规则的更新，对量化封闭项集格的结构作了进一步的扩充，提出了量化规则格，实现了在概念格更新的同时，对最小无冗余关联规则所对应的最小项集集合SLIT的更新。由于量化规则格和格节点对应的具有相同交易集的最小项集是渐进生成的，因此，它非常适合于从动态数据库中提取最小无冗余的关联规则弗且可方便地实现规则的渐增更新。利用概念格的分布处理，把形式背景进行拆分，分别构造相应的部分概念格，然后进行部分概念格合并，得到完整概念格，再提取出相应的关联规则是从概念格中获取知识的一种

7、有效手段：同样，先从部分概念格中分别提取出规则，然后直接进行规则的合并处理，也是获取知识的一种更直接更有效的手段。本文也在这方面做了一定的探索，分别给出了其框架图，并对部分规则集如何核查其在全局数据库中的有效性和最终有效规则的集成等问题做了一定的研究，并给出了简单实例以验证其正确性。关键词：概念格，形式背景，部分格，并置和叠置，分治策略，频繁封闭项集，同交易项集，最小无冗余规则，简洁规则，量化封闭项集格，量化规则格，部分有效规则，最终有效规则V1上海大学博士学位论文ABSTRACTTheconceptlatticeswithth

8、efavorablemathematicpropertieshavebeensuccessfullyappliedinalotoffieldssuchasKnowledgeDiscovery,butthetimecomplexityofbuildingconce