基于内涵亏值的概念格渐进式构建

doi:10.11772/j.issn.1001-9081.2017.01.0222

计算机应用 ›› 2017, Vol. 37 ›› Issue (1): 222-227.DOI: 10.11772/j.issn.1001-9081.2017.01.0222

基于内涵亏值的概念格渐进式构建

吴杰¹, 梁妍², 马垣¹

1. 辽宁科技大学软件学院, 辽宁鞍山 114051;
2. 辽宁科技大学应用技术学院, 辽宁鞍山 114051

收稿日期:2016-06-14 修回日期:2016-08-22 出版日期:2017-01-10 发布日期:2017-01-09
通讯作者: 吴杰
作者简介:吴杰(1981-),男,山东蓬莱人,讲师,博士研究生,主要研究方向:数据库与数据挖掘、形式概念分析;梁妍(1982-),女,辽宁鞍山人,讲师,硕士,主要研究方向:数据库与数据挖掘、形式概念分析;马垣(1941-),男,北京人,教授,博士,主要研究方向:数据库与数据挖掘、形式概念分析。
基金资助:
国家自然科学基金资助项目（61273019）；辽宁科技大学青年基金资助项目（2014QN21）。

Incremental formation of concept lattice based on intent waned value

WU Jie¹, LIANG Yan², MA Yuan¹

1. School of Software, University of Science and Technology Liaoning, Anshan Liaoning 114051, China;
2. School of Applied Technology, University of Science and Technology Liaoning, Anshan Liaoning 114051, China

Received:2016-06-14 Revised:2016-08-22 Online:2017-01-10 Published:2017-01-09
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61273019), the Youth Fund of University of Science and Technology Liaoning (2014QN21).

摘要/Abstract

摘要： 为了避免构建概念格时的繁琐过程，提高概念格构建的效率，提出了一种基于内涵亏值通过查找顶元素来快速渐进式生成概念格的新方法。首先，形式化地定义了顶元素、旧概念、产生概念、新概念、产生子概念、内涵亏值集合、剩留父概念、超集删除与正则队列；提出了概念格元素是否为顶元素的判定定理并给出了其证明；其次，在原概念格的正则队列中依次取概念元素，经超集删除后得到剩留父概念；最后，从剩留父概念查找其所在等价类的顶元素，逐步生成新概念格的正则队列。理论分析时间复杂度较基于属性的渐进式概念格生成（CLIF_A）算法与FastAddIntent算法有效降低，在实验例证对比中，概念数目大于150时，所用时间远少于对比算法。实验结果表明该算法方法简单，构建效率较对比算法明显提高。

关键词: 概念格, 内涵亏值, 顶元素, 超集删除, 正则队列

Abstract: Concerning the tedious process during the construction of concept lattice, to improve the efficiency of building concept lattices, a new incremental method of constructing concept lattice based on intent waned value by seeking top elements was proposed. Firstly, top element, original concept, produced concept, new concept, producer concept, the set of intent waned values, reminded parent concept, superset delete and regular queue were formally defined; the judging theorem and proof whether the concept elements were top elements were given. Secondly, the elements were extracted from the regular queue of the original lattice in due order and the reminded parent concepts were got after superset delete. Finally, the top elements were found from the equivalent classes of the reminded parent concepts and the regular queue of the new lattice was gradually generated. Time complexity was effectively reduced compared with the Attribute-based Concept Lattice Incremental Formation (CLIF-A) algorithm and the FastAddIntent algorithm by theory analysis. In comparison with simulated experiments, the time consumption of the proposed algorithm was far less than the comparative approaches in large size of population. The simulation results show that the proposed algorithm is simple, and can effectively improve the time performance, meanwhile provides better performance in construction efficiency.

Key words: concept lattice, intent waned value, top element, superset delete, regular queue

中图分类号:

TP18

吴杰, 梁妍, 马垣. 基于内涵亏值的概念格渐进式构建[J]. 计算机应用, 2017, 37(1): 222-227.

WU Jie, LIANG Yan, MA Yuan. Incremental formation of concept lattice based on intent waned value[J]. Journal of Computer Applications, 2017, 37(1): 222-227.

参考文献

[1] WILLE R. Restructuring lattice theory:an approach based on hierarchies of concepts[C]//ICFCA' 09:Proceedings of the 7th International Conference on Formal Concept Analysis. Berlin:Springer, 2009:445-470.
[2] LINDIG C. Fast concept analysis[M]//Working with Conceptual Structures Contributions to ICCS 2000. Aachen, Germany:Shaker Verlag, 2000:152-161.
[3] STUMME G, TAOUIL R, BASTIDE Y, et al. Fast computation of concept lattices using data mining techniques[C]//Proceedings of the 7th International Workshop on Knowledge Representation Meets Databases.[S.l.]:VLDB Endowment, 2010:129-139.
[4] 陈震,张娜,王甦菁.一种基于概念矩阵的概念格生成算法[J].计算机科学,2010,37(9):180-183.(CHEN Z, ZHANG N, WANG S J. New algorithm of generating concept lattice based on concept-matrix[J]. Computer Science, 2010, 37(9):180-183.)
[5] GODIN R, MISSAOUI, R, ALAOUI H. Incremental concept formation algorithm based on Galois (concept) lattices[J]. Computational Intelligence, 1995, 11(2):246-267.
[6] 谢志鹏,刘宗田.概念格的快速渐进式构造算法[J].计算机学报,2002,25(5):490-496.(XIE Z P, LIU Z T. A fast incremental algorithm for building concept lattice[J]. Chinese Journal of Computers, 2002, 25(5):490-496.)
[7] 李云,刘宗田,沈夏炯,等.基于属性的概念格渐进式生成算法[J].小型微型计算机系统,2004,25(10):1768-1771.(LI Y, LIU Z T, SHEN X J, et al. Attribute-based incremental formation algorithm of concept lattice[J]. Journal of Chinese Computer Systems, 2004, 25(10):1768-1771.)
[8] 李云,刘宗田,徐晓华,等.多概念格的横向合并算法[J].电子学报,2004,32(11):1849-1854.(LI Y, LIU Z T, XU X H, et al. Horizontal union algorithm of multiple concept lattices[J]. Acta Electronica Sinica, 2004, 32(11):1849-1854.)
[9] 刘群,冷平,孙凌宇.基于对象和属性交叉的渐进式概念格生成算法[J].计算机工程,2009,35(7):59-60.(LIU Q, LENG P, SUN L Y. Incremental concept lattice formation algorithm based on alternate object and attribute[J]. Computer Engineering, 2009, 35(7):59-60.)
[10] 刘耀华,周文,刘宗田.一种区间数分解与定标算法及其扩展形式背景的概念格生成方法[J].计算机科学,2009,36(10):213-216.(LIU Y H, ZHOU W, LIU Z T. Interval scaling algorithm and its concept lattice construction from extended formal context[J]. Computer Science, 2010, 37(9):180-183.)
[11] 屈文建,谭光兴,邱桃荣.运用全1矩阵的概念格生成算法[J].小型微型计算机系统,2012,33(3):558-564.(QU W J, TAN G X, QIU T R. New algorithm of generating concept lattice using universal matrix[J]. Journal of Chinese Computer Systems, 2012, 33(3):558-564.)
[12] 姚佳岷,杨思春,李心磊,等.双序渐进式概念格合并算法[J].计算机应用研究,2013,30(4):1038-1040.(YAO J M, YANG S C, LI X L, et al. Incremental double sequence algorithm of concept lattice union[J]. Application Research of Computers, 2013, 30(4):1038-1040.)
[13] 徐敏政,何宗宜,刘亚虹,等.双向渐进式概念格生成算法[J].小型微型计算机系统,2014,35(1):172-176.(XU M Z, HE Z Y, LIU Y H, et al. Bidirectional incremental formation algorithm of concept lattice[J]. Journal of Chinese Computer Systems, 2014, 35(1):172-176.)
[14] ZOU L G, ZHANG Z P, LONG J, et al. A fast incremental algorithm for constructing concept lattices[J]. Expert Systems with Applications, 2015,42(9):4474-4481.
[15] 马垣,曾子维,迟呈英,等.形式概念分析及其新进展[M].北京:科学出版社,2011:11-31.(MA Y, ZENG Z W, CHI C Y, et al. Formal Concept and it's New Progress[M]. Beijing:Science Press, 2011:11-31.)
[16] 梁妍,吴杰,马垣,等.基于概念格亏值的共轭对方法研究[J].计算机工程与设计,2014,35(1):171-176.(LIANG Y, WU J, MA Y, et al. Research on method of conjugate pairs based on waned values from concept lattice[J]. Computer Engineering and Design, 2014, 35(1):171-176.)

基于内涵亏值的概念格渐进式构建

Incremental formation of concept lattice based on intent waned value

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李明霞, 刘保相, 张春英. 基于压缩理论的区间概念格参数优化模型[J]. 计算机应用, 2016, 36(11): 2945-2949.
[2]	张茹, 张春英, 王立亚, 刘保相. 区间概念格的纵向合并算法[J]. 计算机应用, 2015, 35(11): 3213-3217.
[3]	郭晓波赵书良赵娇娇刘军丹. 基于概念格的多值属性关联规则可视化[J]. 计算机应用, 2013, 33(08): 2198-2203.
[4]	姚佳岷杨思春. 改进的本体概念相似度计算模型[J]. 计算机应用, 2013, 33(06): 1579-1586.
[5]	杨丽王宇辉徐扬. 程度化语言值链上的语言真值概念格及其应用[J]. 计算机应用, 2012, 32(09): 2523-2526.
[6]	陈湘吴跃. 基于概念格挖掘GIS中的关联规则[J]. 计算机应用, 2011, 31(03): 686-689.
[7]	郭显娥王俊红. 多维概念格与关联规则发现[J]. 计算机应用, 2010, 30(4): 1072-1075.
[8]	何小卫牛海峰许黎明马跃. 基于趋势概念格的决策规则挖掘[J]. 计算机应用, 2009, 29(4): 1106-1109.
[9]	王俊红梁吉业曲开社. 基于优势关系的信息系统与形式概念分析[J]. 计算机应用, 2009, 29(2): 539-541.
[10]	马洋张继福张素兰. 基于剪枝的约束概念格的渐进式构造算法[J]. 计算机应用, 2009, 29(05): 1397-1400.
[11]	谭喆. 一种基于索引的概念格分布式构造方法[J]. 计算机应用, 2009, 29(05): 1409-1411.
[12]	赵涓涓陈俊杰刘嘉琳许伟忠. 以本体为核心的图像情感语义检索模型[J]. 计算机应用, 2009, 29(05): 1430-1436.
[13]	李江华杨书新刘利峰. 基于概念格的文本聚类[J]. 计算机应用, 2008, 28(9): 2328-2330.
[14]	李云徐涛田素方李拓. 带兴趣度的序列概念格模型及其构造[J]. 计算机应用, 2008, 28(3): 726-728.
[15]	唐娟杜亚军王可亮. 一种基于形式概念分析的问答系统答案抽取的研究[J]. 计算机应用, 2007, 27(3): 653-655.