概念格的属性渐减原理与算法研究

渐进式算法是概念格构造的一类重要算法,但大多关注于形式背景中对象或属性增加的情况.而当形式背景的属性减少时,已有的算法则需要重新构造概念格,较为费时.针对这一情况,研究了属性消减后从原概念格渐进式产生新概念格的理论和算法,并且算法时间复杂度较低.首先分析了原概念格和新概念格中节点间的映射关系以及从原概念格到新概念格中边(节点间的前驱-后继关系)的变化规律.在此基础上,提出了自顶向下和自底向上两种渐进式的概念格属性渐减算法.算法能够对原有概念格直接进行修改来得到新的概念格,避免了从形式背景重新构造概念格,时间复杂度降低为O(‖ L ‖·G ‖·‖M ‖).实验及分析表明,当属性减少时,能比传统算法节省大量的运行时间.     

基于属性的概念格快速渐进式构造算法

提出了一种新的基于属性的概念格快速渐进式构造算法,通过不断地渐增属性来构造概念格。以往的渐进式算法嘟是基于对象的,当数据库属性数目发生变化时,需要重新构造概念格。该算法不但解决了这个问题,而且提供了一种渐进式构造概念格的新方法和思路。给出了该算法的实例,用来说明形式背景在新添加属性后概念格的更新过程。实例与实验表明基于属性的概念格快速渐进式构造算法是快捷有效的。     

一种基于直积运算的概念格合并算法

现有的渐进式概念格构造算法,不能有效利用已有的概念格.当形式背景的属性数目发生变化时,需要以单个属性或属性集合为对象,重新构造概念格.为此,提出了一种基于已有概念格的概念格合并算法,对已有概念格做直积运算,通过直积格和总格的映射关系,自底向上直接构造出总概念格.这个算法适用于属性交集为空的形式背景的合并.     

概念特化的概念格更新构造算法

概念格是形式概念分析中的核心数据结构,概念格应用的瓶颈之一是其构造效率. 针对形式背景的某个属性分解为多个新属性得到更加特化的概念,给出了一种基于概念特化的渐进式更新构造算法. 该算法利用分解后的新属性及其相应的形式背景,构造出的概念格与原概念格的某个子概念格作比较,来更新构造概念格,从而减少了比较次数,提高了更新构造的效率. 以天体光谱数据作为形式背景,实验验证了该算法的正确性和有效性.     

基于对象和属性交叉的渐进式概念格生成算法

在分析人类概念形成机理的基础上,提出一种基于对象和属性交叉渐进式概念格生成算法,从空概念格开始,逐个地将形式背景中的对象和属性交叉插入到概念格中,实现对概念格的渐进式构造。该算法能渐进式地有效构造概念格,解决了以往渐进式概念格生成算法针对属性和对象交叉渐增更新需要重新构造概念格的问题。     

基于属性的概念格快速渐进式构造算法优化

文章提出一种基于属性的概念格快速渐进式构造算法,主要解决传统算法存在执行时间长和准确率低等问题。首先,该算法引入单属性权值、多属性权值、阈值设定3个内容,并对其进行优化。其次,利用信息熵和偏好修正系数,对单属性权值获取进行调整,从原始数据中获取多属性权值。最后,通过阈值设定衡量多属性的重要性,同时约束条件获取合理的属性权值取值结果。实验结果表明,该算法优化后生成的概念数量小于原概念格中概念的总数,执行时间更短,准确率更高。     

基于对象和属性交叉渐进模糊概念格生成算法

在人类的认知过程中,真实的形式背景总是模糊和不确定的,并伴随着对象和属性交叉渐增更新。在分析人类概念形成机理的基础上,提出了一种基于对象和属性交叉渐进式模糊概念格生成算法。该算法从空概念格开始,逐个地将形式背景中的对象和属性交叉插入到模糊概念格中,实现对模糊概念格的渐进式构造。实验及分析表明该算法不仅能有效地渐进式构造模糊概念格,而且解决了以往渐进式概念格生成算法,针对属性和对象交叉渐增更新需要重新构造概念格的问题。     

基于属性的概念格渐进式生成算法

提出了一种新的基于属性的渐进式概念格生成算法 ,通过不断地渐增属性来构造概念格 .该算法不仅为概念格的构造提供了一种新的方法 ,还解决了在已构造好概念格的前提下 ,增加属性所带来的概念格更新问题 .给出了算法的实现方法 ,并结合实例说明了概念格的更新过程 .试验表明 ,在通常情况下 ,基于属性的渐进式概念格生成算法的性能往往更优越     

概念格的对象渐减更新算法

为解决访问控制中的删除某个对象后重新构造概念格耗时的问题,对概念进行了分类,深入研究了概念格中删除对象后各个概念以及边的变化,分析了概念之间及边之间的联系和规则,在此基础上提出一种概念格的对象渐减更新算法.该算法采用渐进式构造方法,不需要重新构造概念格,而且是在原概念格的基础上采用广度优先遍历的顺序对概念格进行调整,进...     

树状结构组织的属性优先的概念格渐进式算法

通过对概念格渐进式构造过程的分析,采用树结构对概念格节点进行组织,研究了利用这种树状组织的渐进式生成属性优先的概念格的构造算法。并结合实例说明了概念格的树结构组织在属性优先的渐进式生成概念格时,能有效地缩小产生子格节点的搜索范围和新增格节点的父节点和子节点的搜索范围,从而能快速生成概念格。     

基于属性度的属性排序算法

形式概念分析是一种从形式背景进行数据分析和规则提取的强有力工具。属性拓扑作为一种新型的形式背景表示方法,直观地描述了属性之间的关联。利用属性拓扑可以更方便直观地计算形式概念和概念格。经过对现有属性拓扑的算法与流程的研究,分析了现有属性排序算法的特异性和层次局限性,通过结合度的概念,提出了一种属性衡量的新方式--属性度,并提出了基于属性度的属性排序算法。这种排序算法得到的结果更加灵活,消除了属性排序的层次局限性,对父属性的查找有明显的优势,为基于属性拓扑中的属性排序方法提供了指引方向。     

INCREMENTAL CONCEPT FORMATION ALGORITHMS BASED ON GALOIS (CONCEPT) LATTICES

The Galois (or concept) lattice produced from a binary relation has proved useful for many applications. Building the Galois lattice can be considered a conceptual clustering method because it results in a concept hierarchy. This article presents incremental algorithms for updating the Galois lattice and corresponding graph, resulting in an incremental concept formation method. Different strategies are considered based on a characterization of the modifications implied by such an update. Results of empirical tests are given in order to compare the performance of the incremental algorithms to three other batch algorithms. Surprisingly, when the total time for incremental generation is used, the simplest and less efficient variant of the incremental algorithms outperforms the batch algorithms in most cases. When only the incremental update time is used, the incremental algorithm outperforms all the batch algorithms. Empirical evidence shows that, on the average, the incremental update is done in time proportional to the number of instances previously treated. Although the worst case is exponential, when there is a fixed upper bound on the number of features related to an instance, which is usually the case in practical applications, the worst-case analysis of the algorithm also shows linear growth with respect to the number of instances.     

概念格的属性约简与属性特征

主要研究了基于不可约元的概念格的属性约简以及属性约简集的构造。首先给出了概念格中不可约元的判定方法。基于交不可约元,提出了一种概念格的属性约简方法。分析了对概念格的属性约简起不同作用的属性特征,并分别得到了不同类型属性的充分必要条件。最后,利用属性特征讨论了属性约简集的构造。     

构造概念格的权值优化改进算法

针对基于信息熵与偏差的加权概念格在合并加权概念子格时,所得多属性内涵集权值较其整体在形式背景中的实际权重偏大,权重取值阈值的设置受主观因素干扰导致合并后的概念格规模过大的问题,提出了一种构造概念格的权值优化改进算法.以多属性内涵集在形式背景中的整体信息熵来设置其权值;采用方差计算各概念结点属性内涵集权值的阈值区间,克服了主观意识对阈值设置的影响;通过剪除不满足阈值区间的冗余概念结点,缩小了构造概念格的整体规模,减少了构造概念格的时间消耗.实验结果表明:对比基于信息熵与偏差的加权概念格减少了9.87％的冗余结点,构造整体概念格的时间消耗减少了7.36％,有效提高了加权概念格的构造效率.     

A Group Incremental Reduction Algorithm with Varying Data Values

Attribute reduction based on rough set theory has attracted much attention recently. In real‐life applications, many decision tables may vary dynamically with time, e.g., the variation of attributes, objects, and attribute values. The reduction of decision tables may change on the alteration of attribute values. The paper focuses on dynamic maintenance of attribute reduction when varying data values of multiple objects. Incremental mechanisms for knowledge granularity are proposed first, which aims to update attribute reduction effectively. Then, a group incremental reduction algorithm with varying data values is developed. When attribute values of multiple objects have been replaced by new ones in decision table, the proposed incremental algorithm can find the new reduct in a much shorter time. The time complexity analysis and experiments on different data sets from UCI have validated that the proposed incremental algorithms are efficient and effective to update the reduction with the variation of attribute values.     

基于一一映射的概念格属性约简算法*

首先给出了基于一一映射的概念格不同类型属性的等价刻画定理,在此基础上得到了一种新颖的概念格属性约简算法;最后通过实例表明了该约简算法的可行性与有效性。     

基于粒化单调的不完备混合型数据增量式属性约简算法

增量式属性约简是一种针对动态数据集的新型属性约简方法。然而目前的增量式属性约简很少有对不完备混合型的信息系统进行研究。针对这类问题提出一种属性增加时的增量式属性约简算法。在不完备混合型信息系统下引入邻域容差关系。基于邻域容差关系的粒化单调性,提出信息系统属性增加时邻域容差条件熵的增量式更新方法,并提出了不完备混合型信息系统下的邻域容差条件熵增量式属性约简算法。实验分析表明了该算法的有效性。