Research on Drift Calculation of Concept Lattice for Sliding Window Method

doi:10.3778/j.issn.1673-9418.2006063

Abstract

Abstract:

Concept lattice is an effective tool for data analysis and rule acquisition. In recent years, the application and research of concept lattice has gradually become an important research direction in the field of data analysis. With the development of information technology, stream data have become an important part of big data, and the concept drift in stream data mining has become a hot topic in machine learning. The construction of dynamic concept lattice is an important research task of concept lattice theory, but the research of concept lattice drift in streaming data environment has not been carried out. To solve the problem of concept lattice drift in stream data environment, the drift calculation method of concept lattice based on sliding window method is proposed in this paper. First, the stream data in the sliding window are modeled. Then, in the sliding window, this paper conducts inference research separately for five phenomena, i.e. the same inflow and outflow concepts, different inflow and outflow concepts, partial intersection of inflow and outflow concepts, inflow concept including outflow concept, and the outflow concept including the inflow concept. Finally, based on the above model reasoning, a concept lattice construction algorithm based on sliding window method is proposed, and an example is given to illustrate the effectiveness and efficiency of the algorithm.

Key words: concept lattice, stream data, concept drift, sliding window, dynamic concept

摘要：

概念格是一种数据分析和规则获取的有效工具，近年来概念格的应用和研究已逐渐成为数据分析领域的一个重要研究方向。当前随着信息技术的发展，流数据成为了大数据的重要组成部分，流数据知识挖掘中普遍存在的概念漂移已经成为近年来机器学习领域的热点问题。动态概念格的构造是概念格理论研究的重要研究任务，但是在流数据环境中进行概念格的概念漂移研究在学术界还没有展开。针对流数据环境中概念格的漂移问题，提出了一种面向滑动窗口法的概念格漂移计算方法。首先对滑动窗口中的流数据进行建模；然后对滑动窗口中的流入流出概念相同、流入流出概念不同、流入流出概念部分相交、流入概念包含流出概念和流出概念包含流入概念这五种现象分别进行推理研究；最后基于上述模型理论推理，提出面向滑动窗口法的概念格构造算法，并用实例说明了该算法的有效性和高效性。

关键词: 概念格, 流数据, 概念漂移, 滑动窗口, 动态概念

XU Jilin, XU Jianfeng, LIU Long, WU Fangwen. Research on Drift Calculation of Concept Lattice for Sliding Window Method[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(6): 1145-1154.

徐霁琳, 徐健锋, 刘龙, 吴方文. 面向滑动窗口法的概念格漂移计算研究[J]. 计算机科学与探索, 2021, 15(6): 1145-1154.

References

[1] WILLE R. Restructuring lattice theory: an approach based on hierarchies of concepts[C]//Proceedings of the NATO Advanced Study Institute, Banff, Aug 28-Sep 12, 1981. Berlin, Heidelberg: Springer, 1982: 445-470.
[2] GANTER B, WILLE R. Formal concept analysis: mathematical foundations[M]. Berlin, Heidelberg: Springer, 1999.
[3] ZHANG J L, WU X, ZHONG J M, et al. Roll-up and drill-down building algorithms of layered concept lattice[J]. Pattern Recognition and Artificial Intelligence, 2018, 31(4): 310-321.
张家录, 吴霞, 钟嘉鸣, 等. 分层概念格的上卷和下钻构造算法[J]. 模式识别与人工智能, 2018, 31(4): 310-321.
[4] CAI Y, CHEN H M. A parallel algorithm for constructing concept lattice based on hierarchical concept under Map-Reduce[J]. Journal of University of Science and Technology of China, 2018, 48(4): 275-283.
蔡勇, 陈红梅. MapReduce环境下基于概念分层的概念格并行构造算法[J]. 中国科学技术大学学报, 2018, 48(4): 275-283.
[5] ZHU W J, WANG D X, YUAN H C. Improved optimization algorithm of weighted concept lattice[J]. Sensors and Microsystems, 2017, 36(4): 153-156.
朱文君, 王德兴, 袁红春. 构造概念格的权值优化改进算法[J]. 传感器与微系统, 2017, 36(4): 153-156.
[6] YUE X W, PENG S, QIN K Y. Attribute reduction methods of formal context based on object (attribute) oriented concept lattice[J]. Computer Science, 2020, 47(S1): 436-439.
岳晓威, 彭莎, 秦克云. 基于面向对象(属性)概念格的形式背景属性约简方法[J]. 计算机科学, 2020, 47(S1): 436-439.
[7] LIN Y D, LI J J, ZHANG C L. Attribute reductions of fuzzy-crisp concept lattices based on matrix[J]. Pattern Recognition and Artificial Intelligence, 2020, 33(1): 21-31.
林艺东, 李进金, 张呈玲. 基于矩阵的模糊-经典概念格属性约简[J]. 模式识别与人工智能, 2020, 33(1): 21-31.
[8] MA J M, HU L L. Attribute reductions of interval-set concept lattices for decision formal contexts[J]. Pattern Recognition and Artificial Intelligence, 2018, 31(7): 581-590.
马建敏, 胡玲玲. 决策形式背景上区间集概念格的属性约简[J]. 模式识别与人工智能, 2018, 31(7): 581-590.
[9] WEN Y X, WANG J H. Research on a fast method for extracting rules based on horizontal splitting[J]. CAAI Transactions on Intelligent Systems, 2016, 11(4): 526-533.
温云霞, 王俊红. 横向拆分形势背景下的快速规则提取方法[J]. 智能系统学报, 2016, 11(4): 526-533.
[10] HU X K, WANG J H. Research on rule extraction method based on compatibility fuzzy concept[J]. CAAI Transactions on Intelligent Systems, 2016, 11(3): 352-358.
胡小康, 王俊红. 基于相容模糊概念的规则提取方法[J]. 智能系统学报, 2016, 11(3): 352-358.
[11] ZENG L C, ZHANG Z P, ZOU L G. Fast algorithm for incremental construction of concept lattice[J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(11): 1862-1870.
曾利程, 张祖平, 邹力耕. 增量式快速构建概念格算法[J]. 计算机科学与探索, 2018, 12(11): 1862-1870.
[12] WANG C Y, WANG L M, ZHANG Z. Algorithm of maintaining concept lattice based on binary relation decrement[J]. Computer Science, 2016, 43(S2): 35-41.
王春月, 王黎明, 张卓. 基于二元关系消减的概念格维护算法[J]. 计算机科学, 2016, 43(S2): 35-41.
[13] ZHANG L, ZHANG H L, YIN L H, et al. Theory and algorithms of attribute decrement for concept lattice[J]. Journal of Computer Research and Development, 2013, 50 (2): 248-259.
张磊, 张宏莉, 殷丽华, 等. 概念格的属性渐减原理与算法研究[J]. 计算机研究与发展, 2013, 50(2): 248-259.
[14] JIANG Q, ZHANG Z, WANG L M. Algorithms of constructing concept lattice based on deleting multiple attributes synchronously[J]. Journal of Chinese Computer Systems, 2016, 37(4): 646-652.
姜琴, 张卓, 王黎明. 基于多属性同步消减的概念格构造算法[J]. 小型微型计算机系统, 2016, 37(4): 646-652.
[15] MA Y, MA W S. Construction of multi-attributes decrement for concept lattice[J]. Journal of Software, 2015, 26(12): 3162-3173.
马垣, 马文胜. 概念格多属性渐减式构造[J]. 软件学报, 2015, 26(12): 3162-3173.