形式背景的内积约简

doi:10.11772/j.issn.1001-9081.2022030328

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (4): 1079-1085.DOI: 10.11772/j.issn.1001-9081.2022030328

所属专题：数据科学与技术

形式背景的内积约简

王清(), 高秀巍, 谢业海, 刘贵龙

北京语言大学信息科学学院，北京 100083

收稿日期:2022-03-21 修回日期:2022-07-05 接受日期:2022-07-11 发布日期:2023-01-11 出版日期:2023-04-10
通讯作者: 王清
作者简介:高秀巍（1991—），女，辽宁鞍山人，博士研究生，主要研究方向：粗糙集、形式概念分析；
谢业海（1984—），男，海南琼中人，博士研究生，主要研究方向：粗糙集、形式概念分析；
刘贵龙（1962—），男，江西广昌人，教授，博士，主要研究方向：形式概念分析、粗糙集、计算智能、数据挖掘。
基金资助:
国家自然科学基金资助项目(61972052)

Inner product reduction in formal context

Qing WANG(), Xiuwei GAO, Yehai XIE, Guilong LIU

School of Information Science，Beijing Language and Culture University，Beijing 100083，China

Received:2022-03-21 Revised:2022-07-05 Accepted:2022-07-11 Online:2023-01-11 Published:2023-04-10
Contact: Qing WANG
About author:GAO Xiuwei， born in 1991， Ph. D. candidate. Her research interests include rough set， formal concept analysis.
XIE Yehai， born in 1984， Ph. D. candidate. His research interests include rough set， formal concept analysis.
LIU Guilong， born in 1962， Ph. D.， professor. His research interests include formal concept analysis， rough set， computational intelligence， data mining.
Supported by:
National Natural Science Foundation of China(61972052)

摘要/Abstract

摘要：

形式概念分析是知识表示与挖掘的重要工具，而形式背景是形式概念分析中的基本概念之一。针对形式背景中对象集在给定属性集内是否拥有相同属性的问题，同时也为解决如何在计算中消除无关属性的问题，提出了新的属性约简类型，即内积约简。首先在形式背景中给出了内积概念；然后利用关系系统的约简理论和方法定义内积约简，并提出了基于差别矩阵的内积约简算法，以得到形式背景下的全部约简，在此基础上，通过交运算可以得到约简核；当属性增加时，设计了增量内积约简算法。最后结合传染病网络探索内积约简的应用，在模拟案例中属性数量从6个约简到2个。模拟结果表明，内积约简具有可行性和可解释性，达到了知识约简目的。

关键词: 内积约简, 形式背景, 差别矩阵, 增量内积约简, 传染病网络

Abstract:

Formal concept analysis is an important tool for knowledge representation and mining， and formal context is one of the basic concepts in formal concept analysis. A new attribute reduction — inner product reduction was proposed to solve the problem of whether the object set in the formal context has the same attribute in a given attribute set， and also to solve the problem of how to eliminate irrelevant attributes in the calculation. Firstly， the concept of inner product was given in formal context. Then， the reduction theory and method in relation system were used to define the inner product reduction， and the inner product reduction algorithm based on discernibility matrix was proposed to obtain all the reduction results in the formal context， and the reduction core was obtained through the intersection operation based on the results. In addition， when attributes increased， an incremental inner product reduction algorithm was designed. Finally， the application of inner product reduction was explored in infectious disease network. In the simulated case， 6 attributes were reduced to 2 attributes. Simulation outcomes demonstrate that the inner product reduction method is feasible， interpretable， and successful in achieving the knowledge reduction goal.

Key words: inner product reduction, formal context, discernibility matrix, incremental inner product reduction, infectious disease network

中图分类号:

TP18

王清, 高秀巍, 谢业海, 刘贵龙. 形式背景的内积约简[J]. 计算机应用, 2023, 43(4): 1079-1085.

Qing WANG, Xiuwei GAO, Yehai XIE, Guilong LIU. Inner product reduction in formal context[J]. Journal of Computer Applications, 2023, 43(4): 1079-1085.

图/表 9

表1 背景一（U，A，I）

Tab. 1 Formal context 1 （U，A，I）

$U$	$a 1$	$a 2$	$a 3$	$a 4$
$x 1$	1	0	1	1
$x 2$	0	1	1	0
$x 3$	1	0	1	0
$x 4$	0	0	0	1

表1 背景一（U，A，I）

Tab. 1 Formal context 1 （U，A，I）

$U$	$a 1$	$a 2$	$a 3$	$a 4$
$x 1$	1	0	1	1
$x 2$	0	1	1	0
$x 3$	1	0	1	0
$x 4$	0	0	0	1

表2 背景二（U，A，I）

Tab. 2 Formal context 2 （U，A，I）

$U$	$a 1$	$a 2$	$a 3$	$a 4$	$a 5$	$a 6$
$x 1$	1	0	1	1	1	0
$x 2$	0	1	1	0	1	1
$x 3$	1	0	1	0	0	1
$x 4$	0	0	0	1	0	0

表2 背景二（U，A，I）

Tab. 2 Formal context 2 （U，A，I）

$U$	$a 1$	$a 2$	$a 3$	$a 4$	$a 5$	$a 6$
$x 1$	1	0	1	1	1	0
$x 2$	0	1	1	0	1	1
$x 3$	1	0	1	0	0	1
$x 4$	0	0	0	1	0	0

表3 差别矩阵

Tab. 3 Discernibility matrix

$U$	$x 1$	$x 2$	$x 3$	$x 4$
$x 1$	$M 1, 3, 4, 5$	$M 3, 5$	$M 1, 3$	$M 4$
$x 2$		$M 2, 3, 5, 6$	$M 3, 6$	$∅$
$x 3$			$M 1, 3, 6$	$∅$
$x 4$				$M 4$

表3 差别矩阵

Tab. 3 Discernibility matrix

$U$	$x 1$	$x 2$	$x 3$	$x 4$
$x 1$	$M 1, 3, 4, 5$	$M 3, 5$	$M 1, 3$	$M 4$
$x 2$		$M 2, 3, 5, 6$	$M 3, 6$	$∅$
$x 3$			$M 1, 3, 6$	$∅$
$x 4$				$M 4$

表4 背景三（U，A1，I1）

Tab. 4 Formal context 3 （U，A1，I1）

$U$	$a 1$	$a 2$	$a 3$	$a 4$	$a 5$	$a 6$	$a 1 +$	$a 2 +$
$x 1$	1	0	1	1	1	0	1	0
$x 2$	0	1	1	0	1	1	0	1
$x 3$	1	0	1	0	0	1	0	0
$x 4$	0	0	0	1	0	0	0	1

表4 背景三（U，A1，I1）

Tab. 4 Formal context 3 （U，A1，I1）

$U$	$a 1$	$a 2$	$a 3$	$a 4$	$a 5$	$a 6$	$a 1 +$	$a 2 +$
$x 1$	1	0	1	1	1	0	1	0
$x 2$	0	1	1	0	1	1	0	1
$x 3$	1	0	1	0	0	1	0	0
$x 4$	0	0	0	1	0	0	0	1

表5 新差别矩阵

Tab. 5 New discernibility matrix

$U$	$x 1$	$x 2$	$x 3$	$x 4$
$x 1$	$M 1, 3, 4, 5, M 1 +$	$M 3, 5$	$M 1, 3$	$M 4$
$x 2$		$M 2, 3, 5, 6, M 2 +$	$M 3, 6$	$M 2 +$
$x 3$			$M 1, 3, 6$	$∅$
$x 4$				$M 4, M 2 +$

表5 新差别矩阵

Tab. 5 New discernibility matrix

$U$	$x 1$	$x 2$	$x 3$	$x 4$
$x 1$	$M 1, 3, 4, 5, M 1 +$	$M 3, 5$	$M 1, 3$	$M 4$
$x 2$		$M 2, 3, 5, 6, M 2 +$	$M 3, 6$	$M 2 +$
$x 3$			$M 1, 3, 6$	$∅$
$x 4$				$M 4, M 2 +$

表6 背景四（U，A，I）

Tab. 6 Formal context 4 （U，A，I）

$U$	$a 1$	$a 2$	$a 3$	$a 4$	$a 5$	$a 6$
$x 1$	1	0	1	1	1	0
$x 2$	0	1	1	0	1	1
$x 3$	1	0	1	0	0	1
$x 4$	0	0	0	1	0	0

表6 背景四（U，A，I）

Tab. 6 Formal context 4 （U，A，I）

$U$	$a 1$	$a 2$	$a 3$	$a 4$	$a 5$	$a 6$
$x 1$	1	0	1	1	1	0
$x 2$	0	1	1	0	1	1
$x 3$	1	0	1	0	0	1
$x 4$	0	0	0	1	0	0

图1 传染病网络图

Fig. 1 Infectious disease network diagram

图2 约简结果1

Fig. 2 Reduction result 1

图3 约简结果2

Fig. 3 Reduction result 2

参考文献 29

1	PAWLAK Z. Rough Sets： Theoretical Aspects of Reasoning about Data， TDLD 9［M］. Dordrecht： Springer， 1991：9-42. 10.1007/978-94-011-3534-4_7
2	张文修，梁怡，吴伟志. 信息系统与知识发现［M］. 北京：科学出版社， 2003： 42-55.
	ZHANG W X， LIANG Y， WU W Z. Information System and Knowledge Discovery［M］. Beijing： Science Press， 2003：42-55.
3	MI J S， WU W Z， ZHANG W X. Approaches to knowledge reduction based on variable precision rough set model［J］. Information Sciences， 2004， 159（3/4）： 255-272. 10.1016/j.ins.2003.07.004
4	YANG Y Y， CHEN D G， DONG Z. Novel algorithms of attribute reduction with variable precision rough set model［J］. Neurocomputing， 2014， 139： 336-344. 10.1016/j.neucom.2014.02.023
5	LIU G L. Assignment reduction of relation decision systems［C］// Proceedings of the 2017 International Joint Conference on Rough Sets， LNCS 10313. Cham： Springer， 2017：384-391.
6	CHEN D G， WANG C Z， HU Q H. A new approach to attribute reduction of consistent and inconsistent covering decision systems with covering rough sets［J］. Information Sciences， 2007， 177（17）： 3500-3518. 10.1016/j.ins.2007.02.041
7	WANG C Z， SHAO M W， SUN B Q， et al. An improved attribute reduction scheme with covering based rough sets［J］. Applied Soft Computing， 2015， 26： 235-243. 10.1016/j.asoc.2014.10.006
8	LIU G L， HUA Z， ZOU J Y. Local attribute reductions for decision tables［J］. Information Sciences， 2018， 422： 204-217. 10.1016/j.ins.2017.09.007
9	SKOWRON A， RAUSZER C. The discernibility matrices and functions in information systems［M］// SŁOWIŃSKI R. Intelligent Decision Support： Handbook of Applications and Advances of the Rough Sets Theory， TDLD 11. Dordrecht： Springer， 1992： 331-362. 10.1007/978-94-015-7975-9_21
10	PAWLAK Z， SKOWRON A. Rough sets and Boolean reasoning［J］. Information Sciences， 2007， 177（1）： 41-73. 10.1016/j.ins.2006.06.007
11	LIU G L， LI L， YANG J T， et al. Attribute reduction approaches for general relation decision systems［J］. Pattern Recognition Letters， 2015， 65： 81-87. 10.1016/j.patrec.2015.06.031
12	LIU G L， HUA Z， CHEN Z H. A general reduction algorithm for relation decision systems and its applications［J］. Knowledge-Based Systems， 2017， 119： 87-93. 10.1016/j.knosys.2016.11.027
13	樊鑫，陈红梅. 基于差别矩阵和mRMR的分步优化特征选择算法［J］. 计算机科学， 2020， 47（1）：87-95. 10.11896/jsjkx.181202320
	FAN X， CHEN H M. Stepwise optimized feature selection algorithm based on discernibility matrix and mRMR［J］. Computer Science， 2020， 47（1）：87-95. 10.11896/jsjkx.181202320
14	刘凯，谭安辉，顾沈明. 基于辨识矩阵的不完备多粒度约简［J］. 模式识别与人工智能， 2020， 33（9）：799-810.
	LIU K， TAN A H， GU S M. Incomplete multi-granulation reduction based on discernibility matrix［J］. Pattern Recognition and Artificial Intelligence， 2020， 33（9）：799-810.
15	李磊涛，张楠，童向荣，等. 基于差别矩阵的区间值决策系统β分布约简［J］. 计算机应用， 2021， 41（4）：1084-1092.
	LI L T， ZHANG N， TONG X R， et al. β-distribution reduction based on discernibility matrix in interval-valued decision systems［J］. Journal of Computer Applications， 2021， 41（4）：1084-1092.
16	徐伟华，孔子默，陈曜琦. 含属性加权模糊序决策信息系统的近似约简［J］. 南京大学学报（自然科学）， 2022， 58（2）：255-263.
	XU W H， KONG Z M， CHEN Y Q. Approximate reduction of fuzzy ordered decision information system with attribute weighting［J］. Journal of Nanjing University （Natural Science）， 2022， 58（2）：255-263.
17	WILLE R. Restructuring lattice theory： an approach based on hierarchies of concepts［M］// RIVAL I. Ordered Sets： Proceedings of the NATO Advanced Study Institute held at Banff， Canada， August 28 to September 12， 1981， ASIC 83. Dordrecht： Springer， 1982： 445-470. 10.1007/978-94-009-7798-3_15
18	GANTER B， WILLE R. Formal Concept Analysis： Mathematical Foundations［M］. Berlin： Springer， 1999：23-35. 10.1007/978-3-642-59830-2_1
19	张文修，魏玲，祁建军. 概念格的属性约简理论与方法［J］. 中国科学E辑：信息科学， 2005， 35（6）： 628-639. 10.1360/122004-104
	ZHANG W X， WEI L， QI J J. Attribute reduction theory and method in concept lattice［J］. Science in China Series E： Information Sciences， 2005， 35（6）： 628-639. 10.1360/122004-104
20	WEI L， PAN A B. Attribute characteristics of object oriented concept lattices based on the join-irreducible elements［C］// Proceedings of the 2012 IEEE International Conference on Granular Computing. Piscataway： IEEE， 2012：531-535. 10.1109/grc.2012.6468642
21	WU W Z， LEUNG Y， MI J S. Granular computing and knowledge reduction in formal contexts［J］. IEEE Transactions on Knowledge and Data Engineering， 2009， 21（10）： 1461-1474. 10.1109/tkde.2008.223
22	SINGH P K， CHERUKURI A K， LI J H. Concepts reduction in formal concept analysis with fuzzy setting using Shannon entropy［J］. International Journal of Machine Learning and Cybernetics， 2017， 8（1）： 179-189. 10.1007/s13042-014-0313-6
23	汪秋分，李进金，卞洪亚. 面向对象概念格的属性约简方法［J］. 重庆理工大学学报（自然科学）， 2020， 34（5）：256-262.
	WANG Q F， LI J J， BIAN H Y. Attribute reduction method of object-oriented concept lattice［J］. Journal of Chongqing University of Technology （Natural Science）， 2020， 34（5）：256-262.
24	岳晓威，彭莎，秦克云. 基于面向对象（属性）概念格的形式背景属性约简方法［J］. 计算机科学， 2020， 47（6A）：436-439.
	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（6A）：436-439.
25	魏玲，曹丽，祁建军，等. 形式概念分析中的概念约简与概念特征［J］. 中国科学：信息科学， 2020， 50（12）： 1817-1833. 10.1360/n112018-00272
	WEI L， CAO L， QI J J， et al. Concept reduction and concept characteristics in formal concept analysis［J］. SCIENTIA SINICA Informationis， 2020， 50（12）： 1817-1833. 10.1360/n112018-00272
26	CHAN C C. A rough set approach to attribute generalization in data mining［J］. Information Sciences， 1998， 107（1/2/3/4）： 169-176. 10.1016/s0020-0255(97)10047-0
27	杨明. 一种基于改进差别矩阵的属性约简增量式更新算法［J］. 计算机学报， 2007， 30（5）： 815-822. 10.3321/j.issn:0254-4164.2007.05.012
	YANG M. An incremental updating algorithm for attribute reduction based on improved discernibility matrix［J］. Chinese Journal of Computers， 2007， 30（5）： 815-822. 10.3321/j.issn:0254-4164.2007.05.012
28	刘超，王磊，杨文，等. 属性集变化条件下集值决策信息系统的增量属性约简方法［J］. 计算机应用， 2022， 42（2）：463-468.
	LIU C， WANG L， YANG W， et al. Incremental attribute reduction method for set-valued decision information system with variable attribute sets［J］. Journal of Computer Applications， 2022， 42（2）：463-468.
29	SALATHÉ M， KAZANDJIEVA M， LEE J W， et al. A high-resolution human contact network for infectious disease transmission［J］. Proceedings of the National Academy of Sciences of the United States of America， 2010， 107（51）： 22020-22025. 10.1073/pnas.1009094108

[1]	李磊涛, 张楠, 童向荣, 岳晓冬. 基于差别矩阵的区间值决策系统β分布约简[J]. 计算机应用, 2021, 41(4): 1084-1092.
[2]	孔贺庆, 张楠, 岳晓冬, 童向荣, 于天佑. 基于多特定决策类的不完备决策系统正域约简[J]. 计算机应用, 2019, 39(5): 1252-1260.
[3]	高灿苗夺谦张志飞张红云. 粗糙集信度一致属性约简[J]. 计算机应用, 2012, 32(04): 1067-1069.
[4]	时百胜. 基于结构化属性集的规则学习[J]. 计算机应用, 2010, 30(8): 2010-2012.
[5]	赖桃桃冯少荣张东站. 基于改进差别矩阵的核增量式更新算法[J]. 计算机应用, 2009, 29(09): 2477-2480.
[6]	黄治国孙伟吴海涛. 基于差别矩阵的约简树构造方法[J]. 计算机应用, 2008, 28(6): 1457-1459.
[7]	曾小宁肖水晶. 一种增量更新算法在数据挖掘中的应用[J]. 计算机应用, 2007, 27(6): 1403-1406.

形式背景的内积约简

Inner product reduction in formal context

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 29

相关文章 7

编辑推荐

Metrics