三支概念的构建算法

doi:10.3969/j.issn.1001-2400.2017.01.013

西安电子科技大学学报

三支概念的构建算法

汪文威;祁建军

(西安电子科技大学计算机学院，陕西西安 710071)

收稿日期:2015-12-16 出版日期:2017-02-20 发布日期:2017-04-01
通讯作者: 祁建军(1970-)，男，副教授，E-mail：qijj@mail.xidian.edu.cn
作者简介:汪文威(1991-)，男，西安电子科技大学硕士研究生，E-mail：wwwangxd@163.com
基金资助:
国家自然科学基金资助项目(11371014，11071281)；陕西省自然科学基础研究计划资助项目(2014JM8306)

Algorithm for constructing three-way concepts

WANG Wenwei;QI Jianjun

(School of Computer Science and Technology, Xidian Univ., Xi'an 710071, China)

Received:2015-12-16 Online:2017-02-20 Published:2017-04-01
Contact: QI Jianjun

摘要/Abstract

摘要：

新发展出的三支概念分析理论目前还没有具体的三支概念构建算法．针对此问题，提出了一种构建三支概念的算法CbO3C． CbO3C借鉴形式概念分析中构建形式概念的CbO算法的思想，并通过使用基于部分闭包的正则检测和失效正则检测进行剪枝，使用约简条件排除非核心的三支概念，使用位操作实现集合运算等技术来提高效率，降低内存开销．文中对UCI数据和随机数据进行了实验．实验结果表明，算法可以准确、有效地计算出给定形式背景的所有核心三支概念．

关键词: 三支概念分析, 形式概念分析, 形式背景, 算法

Abstract:

The theory of three-way concept analysis is newly developed, but so far there is no concrete algorithm for constructing three-way concepts. In order to solve this problem, a three-way concept construction algorithm named CbO3C is firstly proposed in this paper. The CbO3C adopts the idea of the construction algorithm CbO of formal concepts in formal concept analysis. At the same time, in order to improve the efficiency and lower the memory overhead, the CbO3C employs the partial closure canonicity test and inherited failure test to reduce the repeated computations of three-way concepts, applies the reduction condition to filter the non-core three-way concepts, and implements set operations on the basis of bits. The experiments with UCI and random data sets show that the CbO3C can correctly and efficiently calculate all core three-way concepts of a formal context.

Key words: three-way concept analysis, formal concept analysis, formal contexts, algorithms

汪文威;祁建军. 三支概念的构建算法[J]. 西安电子科技大学学报, 2017, 44(1): 71-76.

WANG Wenwei;QI Jianjun. Algorithm for constructing three-way concepts[J]. Journal of Xidian University, 2017, 44(1): 71-76.

参考文献

［1］ WILLE R. Restructuring Lattices Theory: an Approach Based on Hierarchies of Concepts ［C］//Lecture Notes in Computer Science: 5548. Berlin: Springer Verlag, 2009: 314-339.
［2］黄健斌, 姬红兵. 基于模糊概念格的Web搜索结果聚类算法［J］. 西安电子科技大学学报, 2005, 32(6): 856-860.
HUANG Jianbin, JI Hongbing. A Web Search Results Clustering Algorithm Based on Fuzzy Concept Lattices ［J］. Journal of Xidian University, 2005, 32(6): 856-860.
［3］ POELMANS J, IGNATOV D I, KUZNETSOV S O, et al. Formal Concept Analysis in Knowledge Processing: a Survey on Applications ［J］. Expert Systems with Applications, 2013, 40(16): 6538-6560.
［4］ SKOPLJANAC-MACINA F, BLASKOVIC B. Formal Concept Analysis-Overview and Applications ［C］//Procedia Engineering: 69. Amsterdam: Elsevier Ltd, 2014, 69: 1258-1267.
［5］ ANDREWS S. A ‘Best-of-Breed’ Approach for Designing a Fast Algorithm for Computing Fixpoints of Galois Connections ［J］. Information Sciences, 2015, 295: 633-649.
［6］ KRAJCA P, OUTRATA J, VYCHODIL V. Advances in Algorithms Based on CbO ［C］//CEUR Workshop Proceedings: 672. Tilburg University: Sun SITE Central Europe CEUR-WS, 2010: 325-337.
［7］ YAO Y. An Outline of a Theory of Three-way Decisions ［C］//Rough Sets and Current Trends in Computing. Berlin: Springer Verlag, 2012: 1-17.
［8］ YAO Y. Rough Sets and Three-way Decisions ［C］//Lecture Notes in Computer Science: 9436. Berlin: Springer Verlag, 2015: 62-73.
［9］ YU H, WANG G Y, HU B Q, et al. Methods and Practices of Three-Way Decisions for Complex Problem Solving ［C］//Lecture Notes in Computer Science:9436. Berlin: Springer Verlag, 2015: 255-265.
［10］ LIU D, LIANG D C, WANG C C. A Novel Three-way Decision Model Based on Incomplete Information System ［J］. Knowledge-based Systems, 2016, 91: 32-45.
［11］ QI J J, WEI L, YAO Y Y. Three-Way Formal Concept Analysis ［C］//Lecture Notes in Computer Science: 8818. Berlin: Springer Verlag, 2014: 732-741.
［12］ QI J J, QIAN T, WEI L. The Connections between Three-way and Classical Concept Lattices ［J］. Knowledge-based Systems, 2016, 91: 143-151.
［13］ LI M Z, WANG G Y. Approximate Concept Construction with Three-way Decisions and Attribute Reduction in Incomplete Contexts ［J］. Knowledge-based Systems, 2016, 91: 165-178.
［14］ LI J H, REN Y, MEI C L, et al. A Comparative Study of Multigranulation Rough Sets and Concept Lattices via Rule Acquisition ［J］. Knowledge-based Systems, 2016, 91: 152-164.
［15］ REN R S, WEI L. The Attribute Reductions of Three-way Concept Lattices［J］. Knowledge-based Systems, 2016, 99: 92-102.
［16］ GANTER B, WILLE R. Formal Concept Analysis: Mathematical Foundations ［M］. Berlin: Springer, 1999.
［17］ GAJDOS P, SNASEL V. A New FCA Algorithm Enabling Analyzing of Complex and Dynamic Data Sets ［J］. Soft Computing, 2014, 18(4): 683-694.

[1]	翟畅,林中朝,赵勋旺,张玉. 一种使用八叉树的半空间MLFMA区域分解算法[J]. 西安电子科技大学学报, 2021, 48(6): 144-150.
[2]	张宇鹏,吴自力,陈鸣,张璐璐. 面向交叉微服务链的任务调度优化[J]. 西安电子科技大学学报, 2021, 48(6): 32-39.
[3]	杜文占,余志勇,杨剑,姜海滨. 改进NSGA-II算法及监测天线部署优化研究[J]. 西安电子科技大学学报, 2021, 48(5): 239-248.
[4]	张飞,马时平,张立朝,何林远,仇祝令,韩永赛. 空间可靠性和相关滤波器联合学习的跟踪算法[J]. 西安电子科技大学学报, 2021, 48(5): 167-177.
[5]	李明,胡江平,曹晓莉. 异构传感网成本优化的节点部署策略[J]. 西安电子科技大学学报, 2021, 48(4): 11-19.
[6]	杨仲平,周青松,张剑云. 区域能量聚焦技术中超稀疏阵列优化算法[J]. 西安电子科技大学学报, 2021, 48(4): 57-63.
[7]	马悦,张玉梅. 面向多接入边缘计算的VNFM分布式部署方案[J]. 西安电子科技大学学报, 2021, 48(4): 20-26.
[8]	王波,邓科. DB-SMOTE及多层堆叠用于心律失常识别[J]. 西安电子科技大学学报, 2021, 48(4): 136-143.
[9]	何诗洋,李晖,李凤华. SM4算法的FPGA优化实现方法[J]. 西安电子科技大学学报, 2021, 48(3): 155-162.
[10]	刘天宇,王翥. 一种多样性控制的多目标粒子群算法[J]. 西安电子科技大学学报, 2021, 48(3): 106-114.
[11]	李兴华,蔡觉平,李晓龙,王峰,闫振华. T-NTRU物联网动态接入认证技术[J]. 西安电子科技大学学报, 2021, 48(3): 188-196.
[12]	杨旭,周德俭,宋微,陈小勇. 一种考虑复杂约束的线缆束路径规划方法[J]. 西安电子科技大学学报, 2021, 48(3): 197-204.
[13]	曹艺,蔡晓东. 一种有效的困难样本学习策略[J]. 西安电子科技大学学报, 2021, 48(3): 99-105.
[14]	周建宇,位寅生,许荣庆. 一种改进模糊C均值聚类的电离层杂波分类方法[J]. 西安电子科技大学学报, 2021, 48(2): 35-41.
[15]	叶涛,韦永壮,李灵琛. KNOT认证加密算法的零和区分器分析[J]. 西安电子科技大学学报, 2021, 48(1): 76-86.

三支概念的构建算法

Algorithm for constructing three-way concepts

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10