三支概念的构建算法

doi:10.3969/j.issn.1001-2400.2017.01.013

Abstract

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

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

References

［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]	ZHANG Yupeng,WU Zili,CHEN Ming,ZHANG Lulu. Optimization of task scheduling oriented to cross microservice chains [J]. Journal of Xidian University, 2021, 48(6): 32-39.
[2]	LIU Tianyu,WANG Zhu. Diversity controlled multiobjective particle swarm optimization [J]. Journal of Xidian University, 2021, 48(3): 106-114.
[3]	ZHOU Ji,XU Mengying,WANG Jiaojiao,LU Yi. Improved scheme for spectrum allocation in cognitive wireless sensor networks [J]. Journal of Xidian University, 2020, 47(3): 80-85.
[4]	YANG Luhui,LIU Guangjie,ZHAI Jiangtao,LIU Weiwei,BAI Huiwen,DAI Yuewei. Improved algorithm for detection of the malicious domain name based on the convolutional neural network [J]. Journal of Xidian University, 2020, 47(1): 37-43.
[5]	SU Qin, GU Zongjing, LIN Zhongchao, ZHAO Xunwang, ZHANG Yu. Analysis of scattering characteristics of the one-thousand-wavelength object using the parallel IE-NDDM [J]. Journal of Xidian University, 2018, 45(6): 7-13.
[6]	LIU Yang;LI Jiaqiao;WANG Fan;WANG Zengbin;SHI Sha. RNA secondary structure prediction using the quantum genetic algorithm [J]. Journal of Xidian University, 2018, 45(4): 112-117.
[7]	JIANG Xuesong;JIANG Shugang;ZHANG Yu;ZHAO Xunwang. Parallel FDTD computation of million cores with the domestically-made many-core supercomputer [J]. Journal of Xidian University, 2017, 44(6): 65-69+128.
[8]	YUAN Haobo;WU Zhengguo;HOU Jianqiang;DANG Xiaojie. Accurate optimization algorithm for the antenna phase center [J]. Journal of Xidian University, 2017, 44(5): 64-68.
[9]	YANG Wei;LIU Hongqing;LI Yong;ZHOU Yi. Joint estimation algorithms based on LMS and RLS in the presence of impulsive noise [J]. Journal of Xidian University, 2017, 44(2): 165-170.
[10]	JIANG Shugang;LIN Zhongchao;ZHANG Yu;WEI Bing;ZHAO Xunwang. Parallel FDTD computation of hundred thousand cores on a home-made supercomputer [J]. J4, 2015, 42(5): 86-91.
[11]	WEN Honghang;GE Jianhua;XU Tangwen. Low complexity method for PAPR reduction of OFDM signals [J]. J4, 2015, 42(5): 188-193.
[12]	LIN Zhongchao;CHEN Yan;ZHANG Yu;JIANG Shugang;ZHAO Xunwang;L Zhaofeng. Study of the parallel higher-order MoM on a domestically-made CPU platform [J]. J4, 2015, 42(3): 43-47.
[13]	LI Zhijin;ZHOU Jie;QIAO Jie;WU Wenjuan. Dimensions estimating and the dimension-reducing algorithms for the adaptive multi-dimension division code [J]. J4, 2014, 41(6): 148-154.
[14]	DAI Cai;WANG Yuping;HE Xiaoguang. New ranking method for many-objective problems [J]. J4, 2014, 41(6): 89-94.
[15]	HU Qian;WU Muqing;GUO Song;PENG Li. Random cache placement strategy for content-centric networking [J]. J4, 2014, 41(6): 131-136+187.

Algorithm for constructing three-way concepts

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 10