带对象结构信息形式背景的概念知识发现与演化

doi:10.12263/DZXB.20211559

电子学报 ›› 2023, Vol. 51 ›› Issue (1): 11-17.DOI: 10.12263/DZXB.20211559

带对象结构信息形式背景的概念知识发现与演化

闫梦宇¹^,², 李金海¹^,², 刘文奇¹^,², 张文修³

^1.昆明理工大学数据科学研究中心, 云南昆明 650500
^2.昆明理工大学理学院, 云南昆明 650500
^3.西安交通大学数学与统计学院, 陕西西安 710049

收稿日期:2021-11-22 修回日期:2022-06-30 出版日期:2023-01-25
- 通讯作者:
- 李金海
- 作者简介:
- 闫梦宇　女，1994年5月出生于山东省枣庄市.现为昆明理工大学系统科学专业博士研究生.主要研究方向为形式概念分析、复杂网络、概念认知学习等.E-mail: yanmengyu2016@163.com
  李金海（通讯作者）　男，1984年1月出生于江西省上饶市.2012年毕业于西安交通大学数学与统计学院.现为昆明理工大学数据科学研究中心教授、博士生导师.主要研究方向为概念格、粗糙集、粒计算、概念认知学习等.
- 基金资助:
- 国家自然科学基金 (11971211)

Conceptual Knowledge Discovery and Evolution in Formal Context with Object Structure Information

YAN Meng-yu¹^,², LI Jin-hai¹^,², LIU Wen-qi¹^,², ZHANG Wen-xiu³

^1.Data Science Research Center, Kunming University of Science and Technology, Kunming, Yunnan 650500, China
^2.Faculty of Science, Kunming University of Science and Technology, Kunming, Yunnan 650500, China
^3.School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an, Shaanxi 710049, China

Received:2021-11-22 Revised:2022-06-30 Online:2023-01-25 Published:2023-02-23
- Corresponding author:
- LI Jin-hai
- Supported by:
- National Natural Science Foundation of China (11971211)

摘要/Abstract

摘要：

形式概念分析是数据处理和知识发现的有力工具，然而仅利用形式概念分析中的传统方法已不能满足大数据环境的需求，这是因为大量数据不仅包括对象-属性信息，还有对象与对象之间的结构信息，因此扩展形式概念分析进行数据处理与知识发现是一个重要的研究课题.基于此，本文定义了带对象结构信息形式背景，并在形式概念的基础上引入连通性提出全局结构信息形式概念和局部结构信息形式概念（统称为结构信息形式概念），进而讨论基于结构信息形式概念的知识发现问题；由于现实中数据的动态变化及信息的传播与扩散是不可避免的，又进一步探讨了当带对象结构信息形式背景对象结构矩阵或连接矩阵发生变化时结构信息形式概念的演化规律，根据不同情况分别给出了对应的算法并对它们的时间复杂度进行分析；此外，通过实验表明了结构信息形式概念动态更新方法的可行性与有效性.

关键词: 形式概念分析, 结构信息形式概念, 知识发现, 概念演化, 动态更新

Abstract:

Formal concept analysis is a powerful tool for data processing and knowledge discovery. However, only using the traditional methods in formal concept analysis cannot meet the needs of big data environment since most data not only contain object-attribute information but also the structure information between objects. As a result, it is an important research topic to extend formal concept analysis for data processing and knowledge discovery. Based on the above analysis, this paper puts forward the notion of a formal context with object structure information. And then, the global structural information and local structural information formal concepts are proposed (collectively called structural information formal concepts) by combining with connectivity. Meanwhile, the problem of knowledge discovery on the basis of structural information formal concepts is discussed. Considering the fact that the dynamic changes of data and the dissemination or diffusion of information in our daily life are inevitable, we further explore the evolution rules of structural information formal concepts when a formal context with object structure information is updated gradually. Algorithms are developed for updating different structural information formal concepts when object structure matrix or connection matrix changes, and their time complexity are also analyzed. In addition, we conduct some experiments to show the feasibility and effectiveness of the proposed structural information formal concept updating methods.

Key words: formal concept analysis, structural information formal concept, knowledge discovery, concept evolution, dynamic updating

中图分类号:

TP182

闫梦宇, 李金海, 刘文奇, 等. 带对象结构信息形式背景的概念知识发现与演化[J]. 电子学报, 2023, 51(1): 11-17.

Meng-yu YAN, Jin-hai LI, Wen-qi LIU, et al. Conceptual Knowledge Discovery and Evolution in Formal Context with Object Structure Information[J]. Acta Electronica Sinica, 2023, 51(1): 11-17.

图/表 4

表1 带对象结构信息形式背景真实数据集及其参数

	数据集	对象结构矩阵规模	连接矩阵规模	带对象结构信息形式背景规模	$\| G \|$	$\| M \|$
1	SimVis	256 $×$ 256	256 $×$ 205	461	256	205
2	SAGT	161 $×$ 161	161 $×$ 725	886	161	725
3	J Med Syst	452 $×$ 452	452 $×$ 792	1 244	452	792
4	MIRAGE	360 $×$ 360	360 $×$ 1 531	1 891	360	1 531
5	USENIX ATC	479 $×$ 479	479 $×$ 1 445	1 924	479	1 445
6	ICHIT	521 $×$ 521	521 $×$ 2 216	2 737	521	2 216
7	IEEE RTAS	735 $×$ 735	735 $×$ 2 421	3 156	735	2 421
8	Seville	816 $×$ 816	816 $×$ 3 112	3 928	816	3 112
9	ICVS	606 $×$ 606	606 $×$ 3 450	4 056	606	3 450
10	ACM SIGCSE Bulletin	1 042 $×$ 1 042	1 042 $×$ 3 814	4 856	1 042	3 814
11	ACM Trans.Math.Softw	1 870 $×$ 1 870	1 870 $×$ 9 751	11 621	1 870	9 751
12	IEEE Softw	4 828 $×$ 4 828	4 828 $×$ 16 383	21 211	4 828	16 383

表1 带对象结构信息形式背景真实数据集及其参数

	数据集	对象结构矩阵规模	连接矩阵规模	带对象结构信息形式背景规模	$\| G \|$	$\| M \|$
1	SimVis	256 $×$ 256	256 $×$ 205	461	256	205
2	SAGT	161 $×$ 161	161 $×$ 725	886	161	725
3	J Med Syst	452 $×$ 452	452 $×$ 792	1 244	452	792
4	MIRAGE	360 $×$ 360	360 $×$ 1 531	1 891	360	1 531
5	USENIX ATC	479 $×$ 479	479 $×$ 1 445	1 924	479	1 445
6	ICHIT	521 $×$ 521	521 $×$ 2 216	2 737	521	2 216
7	IEEE RTAS	735 $×$ 735	735 $×$ 2 421	3 156	735	2 421
8	Seville	816 $×$ 816	816 $×$ 3 112	3 928	816	3 112
9	ICVS	606 $×$ 606	606 $×$ 3 450	4 056	606	3 450
10	ACM SIGCSE Bulletin	1 042 $×$ 1 042	1 042 $×$ 3 814	4 856	1 042	3 814
11	ACM Trans.Math.Softw	1 870 $×$ 1 870	1 870 $×$ 9 751	11 621	1 870	9 751
12	IEEE Softw	4 828 $×$ 4 828	4 828 $×$ 16 383	21 211	4 828	16 383

图1 数据集1~12结构信息形式概念计算方法耗时对比

图2 数据集1~12数据规模增加情况与网络概念动态更新方法的耗时增加情况对比

图3 数据集1~12对象结构信息类型改变前后的概念演化耗时对比

参考文献 20

1	FAWLEY W J, PIATETSKY-SHAPIRO G, MATHEUS C J. Knowledge discovery in databases: An overview[J]. AI Magazine, 1992, 13(3): 3-16.
2	CERCONE N, TSUCHIYA M. Special issue on learning and discovery in knowledge-based databases-introduction[J]. IEEE Transactions on Knowledge and Data Engineering, 1993, 5(6): 901-902.
3	WILLE R. Restructuring lattice theory: An approach based on hierarchies of concepts[C]//Ordered Sets. Dordrecht: Reidel, 1982: 445-470.
4	张文修, 梁怡, 吴伟志. 信息系统与知识发现[M]. 北京: 科学出版社, 2003.
	ZHANG Wen-xiu, LEUNG Yee, WU Wei-zhi. Information Systems and Knowledge Discovery[M]. Beijing: Science Press, 2003. (in Chinese)
5	胡可云, 陆玉昌, 石纯一. 基于概念格的分类和关联规则的集成挖掘方法[J]. 软件学报, 2000, 11(11): 1478-1484.
	HU Ke-yun, LU Yu-chang, SHI Chun-yi. An integrated mining approach for classification and association rule based on concept lattice[J]. Journal of Software, 2000, 11(11): 1478-1484. (in Chinese)
6	ZHANG Q, SHI C Y, NIU Z D, et al. HCBC: A hierarchical case-based classifier integrated with conceptual clustering[J]. IEEE Transactions on Knowledge and Data Engineering, 2019, 31(1): 152-165.
7	KAYTOUE M, KUZNETSOV S O, NAPOLI A, et al. Mining gene expression data with pattern structures in formal concept analysis[J]. Information Sciences, 2011, 181(10): 1989-2001.
8	TONELLA P. Using a concept lattice of decomposition slices for program understanding and impact analysis[J]. IEEE Transactions on Software Engineering, 2003, 29(6): 495-509.
9	张文修, 魏玲, 祁建军. 概念格的属性约简理论与方法[J]. 中国科学E辑: 信息科学, 2005, 35(6): 628-639.
	ZHANG Wen-xiu, WEI Ling, QI Jian-jun. Attribute reduction theory and approach to concept lattice[J]. Science China Series E: Information Sciences, 2005, 35(6): 628-639. (in Chinese)
10	魏玲, 曹丽, 祁建军, 等. 形式概念分析中的概念约简与概念特征[J]. 中国科学: 信息科学, 2020, 50(12): 1817-1833.
	WEI Ling, CAO Li, QI Jian-jun, et al. Concept reduction and concept characteristics in formal concept analysis[J]. Scientia Sinica Informationis, 2020, 50(12): 1817-1833. (in Chinese)
11	李金海, 米允龙, 刘文奇. 概念的渐进式认知理论与方法[J]. 计算机学报, 2019, 42(10): 2233-2250.
	LI Jin-hai, MI Yun-long, LIU Wen-qi. Incremental cognition of concepts: Theories and methods[J]. Chinese Journal of Computers, 2019, 42(10): 2233-2250. (in Chinese)
12	米允龙, 李金海, 刘文奇, 等. MapReduce 框架下的粒概念认知学习系统研究[J]. 电子学报, 2018, 46(2): 289-297.
	MI Yun-long, LI Jin-hai, LIU Wen-qi, et al. Research on granular concept cognitive learning system under MapReduce framework[J]. Acta Electronica Sinica, 2018, 46(2): 289-297. (in Chinese)
13	智慧来. 面向异构数据分析的形式概念分析扩展模型[J]. 电子学报, 2013, 41(12): 2451-2455.
	ZHI Hui-lai. Extended model of formal concept analysis oriented for heterogeneous data analysis[J]. Acta Electronica Sinica, 2013, 41(12): 2451-2455. (in Chinese)
14	张涛, 任宏雷, 洪文学, 等. 基于属性拓扑的可视化形式概念计算[J]. 电子学报, 2014, 42(5): 925-932.
	ZHANG Tao, REN Hong-lei, HONG Wen-xue, et al. The visualizing calculation of formal concept that based on the attribute topologies[J]. Acta Electronica Sinica, 2014, 42(5): 925-932. (in Chinese)
15	翟岩慧, 李德玉, 曲开社. 决策蕴涵规范基[J]. 电子学报, 2015, 43(1): 18-23.
	ZHAI Yan-hui, LI De-yu, QU Kai-she. Canonical basis for decision implications[J]. Acta Electronica Sinica, 2015, 43(1): 18-23. (in Chinese)
16	QI J J, WEI L, CHEN Y P. Correlation analysis between objects and attributes[C]//Proceedings of 4th Rough Sets and Knowledge Technology. Berlin: Springer, 2009: 594-600.
17	RAGHAVAN V, HAFEZ A. Dynamic data mining[C]// Proceedings of 13th International Conference on Industrial Engineering Applications of AI & Expert Systems. New York: Springer, 2000: 220-229.
18	PEDRYCZ W, HOMENDA W. Building the fundamentals of granular computing: A principle of justifiable granularity[J]. Applied Soft Computing, 2013, 13 (10): 4209-4218.
19	张清华, 吕功勋, 陈玉洪, 等. 基于字符型属性值更新的动态三支决策模型[J]. 电子学报, 2019, 47(2): 344-350.
	ZHANG Qing-hua, LV Gong-xun, CHEN Yu-hong, et al. A dynamic three-way decision model based on the updating of character attribute values[J]. Acta Electronica Sinica, 2019, 47(2): 344-350. (in Chinese)
20	马垣, 马文胜. 概念格多属性渐减式构造[J]. 软件学报, 2015, 26(12): 3162-3173.
	MA Yuan, MA Wen-sheng. Construction of multi-attributes decrement for concept lattice[J]. Journal of Software, 2015, 26(12): 3162-3173. (in Chinese)

[1]	张清华, 吕功勋, 陈玉洪, 谢秦. 基于字符型属性值更新的动态三支决策模型[J]. 电子学报, 2019, 47(2): 344-350.
[2]	孙小兵, 李云, 李必信, 文万志. 形式概念分析在软件维护中的应用综述[J]. 电子学报, 2015, 43(7): 1399-1406.
[3]	张涛, 任宏雷, 洪文学, 李慧. 基于属性拓扑的可视化形式概念计算[J]. 电子学报, 2014, 42(5): 925-932.
[4]	张磊, 张宏莉, 韩道军, 沈夏炯. 基于概念格的RBAC模型中角色最小化问题的理论与算法[J]. 电子学报, 2014, 42(12): 2371-2378.
[5]	智慧来. 面向异构数据分析的形式概念分析扩展模型[J]. 电子学报, 2013, 41(12): 2451-2455.
[6]	杨彬;徐宝文;许蕾. 基于概念内涵最小生成子的伪内涵计算方法[J]. 电子学报, 2008, 36(11): 2125-2131.
[7]	强宇, 刘宗田, 林炜, 时百胜, 李云. 模糊概念格在知识发现的应用及一种构造算法[J]. 电子学报, 2005, 33(2): 350-353.
[8]	王云岚;李增智;屈科文. 基于候选项集个数上阶的增量式关联规则更新算法[J]. 电子学报, 2004, 32(5): 731-734.
[9]	苏晓红;郭茂祖;王亚东;张田文. 基于偏最小二乘回归分析的混色数据学习算法研究[J]. 电子学报, 2001, 29(3): 429-431.

带对象结构信息形式背景的概念知识发现与演化

Conceptual Knowledge Discovery and Evolution in Formal Context with Object Structure Information

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 4

参考文献 20

相关文章 9

编辑推荐

Metrics