基于概念格的不完备信息系统最简规则提取算法

概念格是以概念为元素的偏序集,通常可以对形式背景描述的完备信息系统进行分析和处理,然而在多数情况下信息系统是不完备的,粗糙集理论是一种刻画不完整、不确定性问题的有效方法.针对此问题,从粗糙集的角度出发,基于概念格理论定义一种描述不完备信息系统的增广形式背景,在此基础上,定义并讨论极概念和极概念格及其相关性质,进而提出增广形式背景的极概念生成算法.为了获得更加简洁的决策规则,同时提出一种新的无冗余属性的决策规则获取算法.通过实例计算和UCI数据集的对比实验,表明了所提出算法的可行性和有效性,特别地,当信息系统完备时极概念将退化为经典的概念.     

决策蕴涵上的推理规则和推理过程研究

形式概念分析是用于概念分析和可视化的偏序集理论。决策蕴涵是形式概念分析在决策情形下的知识表示。已有研究从逻辑角度分析了决策蕴涵,并给出了完整的语义描述和语构描述,其中在语构方面已经有一个完备的推理规则集,即扩增推理规则和合并推理规则。在此基础上,提出了新的推理规则——后件合并推理规则,证明了其合理性,以及与扩增推理规则组成的推理规则集的完备性和无冗余性;通过研究扩增推理规则和后件合并推理规则的性质,给出了使用这两条推理规则从完备集推导其对应封闭集的有效方法等理论结果,为进一步的算法研究与应用以及更深入的理论研究工作奠定基础。     

一种基于概念格的规则提取方法及其应用

概念格是规则提取的一种有效工具.在已知一个形式背景的所有概念,而无需知道其格结构的前提下,首先定义了每类样本集合的规则集和普通属性集,然后给出了一个基于普通属性集在冗余的规则集中提取出每类样本集合普遍适用的一个产生规则的算法,从而可进一步生成相应规则子集.最后,该方法被应用于无线电C波段信号的规则提取,实验结果证明了该方法的可行性和有效性.     

基于决策背景的决策蕴涵规范基

主要给出决策背景下的决策蕴涵基,通过不确定的分组阈值对决策背景进行分组,找到每个分块的决策背景下的决策蕴涵规范基,并证明了每个分块上的决策蕴涵集是完备、无冗余和最优的;也证明了每个决策背景分块上的决策蕴涵基的集合在整个决策背景上也是完备、无冗余和最优的。在生成决策背景的决策蕴涵规范基的过程中,优化了最小生成子算法;同时也给出了基于决策背景的决策蕴涵规范基的生成算法。实验表明,通过分组策略和算法的优化改进,可以很好地抑制冗余决策蕴涵规范基的生成,使决策蕴涵规范基更为有效和紧凑。     

不完备形式背景中的知识获取方法

重点讨论了不完备形式背景中的相容概念以及基于相容概念的相容规则获取方法,同时给出了相应的构造算法。为了压缩规模庞大的相容规则集合,提出了一条推理规则来减少生成冗余相容规则的数目,最终得到一个完备的无冗余的相容规则集合。通过参数的设定可以满足不同用户的实际需求,实例证明该方法是有效的。该方法不仅为不完备形式背景的处理提供了一条新的途径,同时也为更深入的研究奠定了基础。     

概念粒计算系统的数学模型

文中在两个完备格之间引入了外延内涵算子与内涵外延算子,构建了概念粒计算系统,证明了由该系统生成的全体概念集合是具有最大元与最小元的格.此概念粒计算系统不仅包括了由形式背景形成的概念格以及由L模糊形式背景形成的L模糊概念格,也包括了3种变精度概念格,即概念的外延与内涵分别为经典集与经典集、经典集与模糊集、模糊集与经典集.最后在概念粒计算系统中,给出了概念粒迭代计算方法,并证明了它在某种意义下的最优性.     

不完备形式背景下近似概念格的公理化方法

提出了由两个完备形式背景构造不完备形式背景的方法.基于完备形式背景公理化的方法得到了近似概念格的公理组,并给出了近似概念格的构造方法,其发展了不完备形式背景下近似概念格的理论.     

横向拆分形势背景下的快速规则提取方法

概念格是进行数据挖掘和规则提取的一种有效工具。目前已经提出的概念格上的规则提取方法大多是针对整个形式背景,得到的规则数目较多,规则集规模较大,且这种规则结构不便于两个规则集的合并。针对这个问题,本文提出一种伪规则的概念,并给出渐近式获取伪规则的方法;同时证明了通过伪规则集,用户可以根据自己的兴趣有选择地从伪规则集合中产生出所需的蕴含规则;提出了将两个伪规则集进行合并的方法,从而用户可以通过拆分合并的思想来获取规则集;最后通过实验分析验证了算法的有效性。     

概念格的内涵缩减与数据库推理依赖

值依赖是数据库推理问题研究的一个新课题.首先介绍了形式背景和概念格,提出了值依赖的形式概念模型.将数据属性的安全敏感级别引入到值依赖研究中,提出推理依赖及α极大推理依赖概念,并建立了形式概念格的内涵缩减与数据库推理依赖之间的关系.进一步证明了由概念格的内涵缩减推导出数据库中完备的、无冗余的α极大推理依赖集.最后提出并实例验证了发现数据库中全部推理依赖集的算法.推理依赖是关系数据库中最重要的属性依赖关系之一,其研究对检测和消除数据库推理通道具有十分重要的意义.     

D型概率决策形式背景下的规则获取

基于不确定性决策问题,提出一种D型概率决策形式背景,并针对D型概率决策形式背景定义“△”算子,获得概率形式概念,构造相应的概念格。又定义了D型概率决策形式背景的协调性,在协调的背景上进行规则获取。进一步,剔除冗余规则,简化规则集。最后,给出概率概念格生成及规则获取算法,以便于计算机的实现。     

概念格在入侵检测中的应用研究

为了发现潜在的、有效的入侵检测规则,提高入侵检测系统的检测率,将概念格与入侵检测技术相结合提出了一种基于概念格理论的入侵检测系统.系统通过对收集的数据进行预处理、数据规范化,使用属性约简得到最小属性集构建概念格,同时分析概念间的蕴涵关系,获得非冗余的分类规则.基于概念格的入侵检测模型与其它检测方法相比要求的训练数据获取简单,实验结果表明,使用该模型减少了实现分类的运算量,提高了入侵检测的检测率,有效控制了检测的误检率.     

基于概念格的组规则产生集的算法研究

数据挖掘中传统的关联规则生成算法产生的关联规则集合相当庞大,其中很多规则可由其它规则导出。使用闭项集可以减少规则的数目,而概念格节点间的泛化和例化关系非常适用于规则的提取。目前几种基于概念格的规则提取算法局限于得到准确支持度、信任度的无冗余规则。提出了一种在概念格上挖掘出能推导出所有满足最小支持度、信任度规则的规则产生集算法,文中称之为组规则产生集算法,减少了规则的规模。在此基础上进一步给出了组规则产生集的存储数据结构并用其导出一般规则产生集的算法。     

概念格上规则产生集的算法研究与应用

用传统的规则生成算法产生的关联规则集合相当庞大,其中很多规则可由其它规则导出。使用闭项集可以减少规则的数目,而概念格节点间的泛化和例化关系非常适用于规则的提取。目前几种基于概念格的规则提取算法局限于得到准确支持度、信任度的无冗余规则。提出了一种在概念格上挖掘出能推导出所有满足最小支持度、信任度规则的规则产生集算法,文中称之为组规则产生集算法,减少了规则的规模,提高了挖掘效率,进一步给出了组规则产生集的存储数据结构和根据应用需要用其导出单一后项规则的算法。     

概念格上无冗余关联规则的提取算法NARG

在数据挖掘中,关联规则是很有价值的一类规律。普通的挖掘算法会产生大量的规则,尤其是当最小支持度和最小可信度减少时,关联规则的数目急剧上升。如何对规则进行约减而又不丢失数据信息是消除冗余关联规则的关键。根据概念格的理论和冗余关联规则的性质,提出在概念格上提取无冗余关联规则的NARG算法。该算法可以得到最小的无冗余的关联规则集,而且不丢失任何信息,可有效提高关联规则生成的效率。     

Study of decision implications based on formal concept analysis

In this paper, the notions of decision table and decision rule in Rough Set Theory are introduced naturally into Formal Concept Analysis as decision context and decision implication. Since extracting decision implications directly from decision context takes time, we present an inference rule called α-decision inference rule to eliminate the superfluous decision implications. Moreover, based on the inference rule we introduce the notion of α-maximal decision implication and prove that the set of all α-maximal decision implications is complete (α-complete) and non-redundant (α-non-redundant). Finally, we present a method to generate the set.     

一种基于概念格的决策规则挖掘算法

概念格作为形式概念分析理论中的一种核心数据结构已经在众多的领域取得了广泛而成功的应用。从概念格上可以提取各种类型的知识,如蕴含规则、关联规则、分类规则等。利用概念格的所有节点的完备性特点,提出了一种基于概念格的新的决策规则挖掘算法,同时给出了规则的支持度。最后通过实例验证了算法的有效性。     

基于改进概念格的无冗余关联规则提取

在介绍概念格相关理论的基础上,提出改进概念格构造算法——Godin算法,在构造概念格的同时增加索引链表,有利于概念格的剪枝。把量化概念格、剪枝概念格与改进算法相结合,给出基于该改进算法的无冗余关联规则提取算法,并证明改进算法和无冗余规则提取算法的正确性和有效性。     

FP-tree上频繁概念格的无冗余关联规则提取

为解决经典关联规则生成算法挖掘效率低及形成规则冗余性大的问题,提出在FP-tree基础上直接生成频繁概念格并提取无冗余关联规则的算法。其建格过程根据FP-tree频繁项目头表中各项的索引可分别独立进行,由支持度计数约束进行结点的筛选,形成频繁概念格的Hasse图,图中结点包含频繁项集及其支持度计数信息,通过对全部叶子结点的扫描可生成无冗余关联规则。通过实例验证该算法行之有效。     

Knowledge Discovery in Complex Objects

Learning concepts and rules from structured (complex) objects is a quite challenging but very relevant problem in the area of machine learning and knowledge discovery. In order to take into account and exploit the semantic relationships that hold between atomic components of structured objects, we propose a knowledge discovery process, which starts from a set of complex objects to produce a set of related atomic objects (called contexts). The second step of the process makes use of the concatenation product to get a global context in which binary relations of individual contexts coexist with relations produced by the application of some operators to individual contexts. The last step permits the discovery of concepts and implication rules using the concept lattice as a framework in order to discover and interpret nontrivial concepts and rules that may relate different components of complex objects. This paper focuses on two main steps of the knowledge discovery process, namely data mining and interpretation.     

基于概念格的语言真值不确定性推理*

利用概念格来实现不确定性推理的过程中,给出了一个具体的语言真值格蕴涵代数的完备结构;作为概念格的扩充理论,提出了用于处理不确定性信息的语言真值概念格,并基于语言真值概念格给出了内逼近不确定性推理规则和外逼近不确定性推理规则,进而验证了这两种规则的还原性。