﻿ 基于信息熵的对象加权概念格
«上一篇
 文章快速检索 高级检索

 智能系统学报  2020, Vol. 15 Issue (6): 1097-1103  DOI: 10.11992/tis.202006043 0

### 引用本文

ZHANG Xiaohe, CHEN Degang, MI Jusheng. Object-weighted concept lattice based on information entropy[J]. CAAI Transactions on Intelligent Systems, 2020, 15(6): 1097-1103. DOI: 10.11992/tis.202006043.

### 文章历史

1. 华北电力大学 控制与计算机工程学院，北京 102200;
2. 河北师范大学 数学科学学院，河北 石家庄 050024

Object-weighted concept lattice based on information entropy
ZHANG Xiaohe 1, CHEN Degang 1, MI Jusheng 2
1. School of Control and Computer Engineering, North China Electric Power University, Beijing 102200, China;
2. College of Mathematics and Information Science, Hebei Normal University, Shijiazhuang 050024, China
Abstract: In the era of big data, it is becoming increasingly difficult to construct concept lattices due to the increasingly large scale of data. To objectively reflect hidden information, redundant objects and attributes should be deleted and data size should be reduced to construct simple concept lattices, thus, facilitating users to acquire knowledge efficiently. In this study, to prevent subjective factors, the information entropy of an attribute in the formal context is used to obtain a single attribute weight and the attribute weight of the object is, then, calculated using the mean value method and the importance deviation of the object is calculated by standard deviation. By setting the attribute weight, object weight, and object importance deviation threshold, an object-weighted concept lattice is constructed. An example is provided to verify the effectiveness of this method in removing redundant concepts and simplifying the construction of concept lattices.
Key words: formal context    context    information entropy    granular computing    concept lattice    decision rules    weight value    data mining

1 预备知识

 $f(X) = \{ a \in A:{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \forall x \in X,{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} (x,a) \in I\}$
 $g(B) = \{ x \in U:{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \forall a \in B,{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} (x,a) \in I\}。$

 $({X_{\rm{1}}},{B_{\rm{1}}}) \leqslant ({X_2},{B_2})$

 $({X_{\rm{1}}},{B_{\rm{1}}}) \vee ({X_{\rm{2}}},{B_{\rm{2}}}){\kern 1pt} = (g{\kern 1pt} f({X_{\rm{1}}} \cup {X_{\rm{2}}}{\rm{), }}{B_{\rm{1}}} \cap {B_{\rm{2}}})$
 $({X_{\rm{1}}},{B_{\rm{1}}}) \wedge ({X_{\rm{2}}},{B_{\rm{2}}}){\kern 1pt} = ({X_{\rm{1}}} \cap {X_{\rm{2}}}{\rm{, }}fg({B_{\rm{1}}} \cup {B_{\rm{2}}}))$

 $H(a) = - \sum\limits_{i = 1}^{{n}} {P(a/{x_i})} {\log _2}P(a/{x_i})$

2 对象加权概念格 2.1 对象权重及对象重要度偏差

$\forall x \in U$ $f(x) = \{ {a_{{s_1}}},{a_{{s_2}}}, \cdots ,{a_{{s_t}}}\} {\kern 1pt} {\kern 1pt} {\kern 1pt}$ ，对象 $x$ 的权重定义为

 $d(x) = \frac{{\displaystyle\sum\limits_{j = 1}^t {w{\kern 1pt} {\kern 1pt} {\kern 1pt} ({a_{{s_j}}})} }}{t}$

 $D(x) = \sqrt {\frac{1}{{t - 1}}\sum\limits_{j = 1}^t {{{(w{\kern 1pt} {\kern 1pt} ({a_{{s_j}}}) - d(x))}^2}} }$

2.2 对象加权概念格及其构造

1) for $1 \leqslant i \leqslant \left| A \right|$ do

2) $w({a_i}) = \dfrac{{H({a_i})}}{{\displaystyle\sum\limits_{i = 1}^{\left| A \right|} H{\kern 1pt} {\kern 1pt} {\kern 1pt} ({a_i}) }}$

3) end for

4) initialize $d'({x_j}) = 0$

5) for $1 \leqslant i \leqslant \left| A \right|$ $1 \leqslant j \leqslant \left| U \right|$ do

6) if $({x_j},{a_i}) \in I$ then

7) $d'({x_j}) \leftarrow w({a_i})$

8) end if

9) compute $d({x_j}) = \dfrac{{d'({x_j})}}{{\left| {f({x_j})} \right|}}$

10) $D({x_j}) = \sqrt {\dfrac{1}{{\left| {f({x_j})} \right| - 1}}\displaystyle\sum {{{(w{\kern 1pt} {\kern 1pt} ({a_i}) - d({x_j}))}^2}} }$

11) end for

12) if $w({a_i}) < \alpha$ $d({x_j}) < \beta$ or $D({x_j}) > \delta$ then

13) delete ${x_j}$ ${a_i}$

14) end if

15) ${F_D} = (U/{x_j},A/{a_i},I')$

16) return $L({F_D})$

2.3 基于对象强加权概念格的决策规则提取

 $U/{R_D} = \{ {[x]_D}:\!\!\!\!\!{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} x \in U\} {\rm{ = \{ }}{D_1}{\rm{,}}{D_2}, \cdots ,{D_r}{\rm{\} }}$

$(U,A,I,D,J)$ 为决策形式背景，则由形式背景 $F = (U,A,I)$ 能够获得子形式背景 ${F_D} = ({U_D},{A_D},$ ${I_D})$ ，进一步可构造对象强加权概念格，记为 $L({U_D},{A_D},{I_D})$ 。称 $(X,B)\in L({U}_{D},{A}_{D},{I}_{D})$ 为条件概念。

$X{\text{、}}B$ 均为非空集合，如果有 $\dfrac{{\left| {X \cap {D_k}} \right|}}{{\left| X \right|}} = 1$ ，则称 $\left( {X,B} \right) \Rightarrow ({D_k},{T_k})$ 为决策形式背景的粒决策规则。简记为 $B \Rightarrow {T_k}$

1) compute $L({F_D})$

2) $\forall x,y \in U$

3) for $1 \leqslant k \leqslant \left| D \right|$ do

4) if ${d_k}(x) = {d_k}(y)$ then

5) $(x,y) \in {R_D}$

6) end if

7) $U/{R_D} = \{ {[x]_D}: x \in U\} {\rm{ = \{ }}{D_1}{\rm{,}}{D_2}, \cdots ,{D_r}{\rm{\} }}$

8) end for

9) compute $({D_t},{T_t})$

10) for all $(X,B) \in L({F_D})$ $1 \leqslant t \leqslant r$ do

11) if $\dfrac{{\left| {X \cap {D_t}} \right|}}{{\left| X \right|}}{\rm{ = 1}}$ then

12) $\left( {X,B} \right) \Rightarrow ({D_t},{T_t})$

13) end if

3 实验和分析 3.1 应用举例

1)直接构造概念格

 Download: 图 1 由F=( U，A，I )构造的概念格 Fig. 1 Concept lattice of $F = (U,A,I)$

2)对象加权概念格

 ${H_{\rm{1}}}(a) = - {P_{\rm{1}}}(a) \times {\log _2}{P_{\rm{1}}}(a) = {\kern 1pt} = - \frac{5}{6} \times {\log _2}\frac{5}{6} = 0.219\;2$

${P_{\rm{1}}}(b) = \dfrac{4}{6}$ ${H_{\rm{1}}}(b){\kern 1pt} {\kern 1pt} = - \dfrac{4}{6} \times {\log _2}\dfrac{4}{6} = 0.389\;9$

${P_{\rm{1}}}(c) = \dfrac{1}{6}$ ${H_{\rm{1}}}(c){\kern 1pt} {\kern 1pt} = - \dfrac{1}{6} \times {\log _2}\dfrac{1}{6} = 0.430\;8$

${P_{\rm{1}}}(d) = \dfrac{2}{6}$ ${H_{\rm{1}}}(d){\kern 1pt} {\kern 1pt} = - \dfrac{2}{6} \times {\log _2}\dfrac{2}{6} = 0.528\;3$

${P_{\rm{1}}}(e) = \dfrac{3}{6}$ ${H_{\rm{1}}}(e){\kern 1pt} {\kern 1pt} = - \dfrac{3}{6} \times {\log _2}\dfrac{3}{6} = 0.5$

 $H(A) = {H_{\rm{1}}}(a) + {H_{\rm{1}}}(b) + {H_{\rm{1}}}(c) + {H_{\rm{1}}}(d) + {H_{\rm{1}}}(e) = {\rm{2}}{\rm{.068\;2}}。$

 ${d_{\rm{1}}}(1) = \frac{{{w_{\rm{1}}}(a){\rm{ + }}{w_{\rm{1}}}(b)}}{2} = 0.{\rm{15}}$
 ${d_{\rm{1}}}(2) = \frac{{{w_{\rm{1}}}(a){\rm{ + }}{w_{\rm{1}}}(d){\rm{ + }}{w_{\rm{1}}}(e)}}{{\rm{3}}} = 0.2$
 ${d_{\rm{1}}}({\rm{3}}) = \frac{{{w_{\rm{1}}}(a){\rm{ + }}{w_{\rm{1}}}(b) + {w_{\rm{1}}}(c){\rm{ + }}{w_{\rm{1}}}(e)}}{{\rm{4}}} = 0.1{\rm{87\;5}}$

${d_{\rm{1}}}({\rm{4}}) = {w_{\rm{1}}}(a) = 0.11$ (小于β，故该对象冗余需删去)

 ${d_{\rm{1}}}({\rm{5}}) = \frac{{{w_{\rm{1}}}(b){\rm{ + }}{w_{\rm{1}}}(e)}}{2} = 0.{\rm{215}}$
 ${d_{\rm{1}}}({\rm{6}}) = \frac{{{w_{\rm{1}}}(a){\rm{ + }}{w_{\rm{1}}}(b) + {w_{\rm{1}}}(d)}}{{\rm{3}}} = 0.183\;{\rm{3}}。$

 Download: 图 2 由 ${F_d} = ({U_d},{A_d},{I_d})$ 构造的概念格 Fig. 2 Concept lattice of ${F_d} = ({U_d},{A_d},{I_d})$

3)对象强加权概念格

 ${D_{\rm{1}}}({\rm{1}}) = \sqrt {{{({w_{\rm{1}}}(a) - {d_{\rm{1}}}({\rm{1}}))}^2} + {{({w_{\rm{1}}}(b) - {d_{\rm{1}}}({\rm{1}}))}^2}} {\rm{ = 0}}{\rm{.057}}$
 ${D_{\rm{1}}}({\rm{2}}) = \sqrt {\frac{{{{({w_{\rm{1}}}(a) - {d_{\rm{1}}}({\rm{2}}))}^2} + {{({w_{\rm{1}}}(d) - {d_{\rm{1}}}({\rm{2}}))}^2} + {{({w_{\rm{1}}}(e) - {d_{\rm{1}}}({\rm{2}}))}^2}}}{{{\rm{3}} - 1}}} {\rm{ = 0}}{\rm{.078}}$

 ${D_{\rm{1}}}({\rm{3}}) = \sqrt {\frac{{{{({w_{\rm{1}}}(a) - {d_{\rm{1}}}({\rm{3}}))}^2} + {{({w_{\rm{1}}}(b) - {d_{\rm{1}}}({\rm{3}}))}^2} + {{({w_{\rm{1}}}(c) - {d_{\rm{1}}}({\rm{3}}))}^2} + {{({w_{\rm{1}}}(e) - {d_{\rm{1}}}({\rm{3}}))}^2}}}{{{\rm{4}} - 1}}} {\rm{ = 0}}{\rm{.056}}。$
 ${D_{\rm{1}}}({\rm{5}}) = \sqrt {{{({w_{\rm{1}}}(b) - {d_{\rm{1}}}({\rm{5}}))}^2} + {{({w_{\rm{1}}}(e) - {d_{\rm{1}}}({\rm{5}}))}^2}} {\rm{ = 0}}{\rm{.035}}。$
 ${D_{\rm{1}}}({\rm{6}}) = \sqrt {\frac{{{{({w_{\rm{1}}}(a) - {d_{\rm{1}}}({\rm{6}}))}^2} + {{({w_{\rm{1}}}(b) - d({\rm{6}}))}^2} + {{({w_{\rm{1}}}(d) - {d_{\rm{1}}}({\rm{6}}))}^2}}}{{{\rm{3}} - 1}}} {\rm{ = 0}}{\rm{.07}}。$

 Download: 图 3 由 ${F_D} = ({U_D},{A_D},{I_D})$ 构造的概念格 Fig. 3 Concept lattice of ${F_D} = ({U_D},{A_D},{I_D})$

4)粒决策规则提取

 $\{ b,e\} \Rightarrow \{ 1\}$
 $\{ b,c,e\} \Rightarrow \{ 1\}$
 $\{ b,d\} \Rightarrow \{ 0\}$

 $\{ b,e\} \Rightarrow \{ 1\}$
 $\{ b,d\} \Rightarrow \{ 0\}$

 $\{ a,d\} \Rightarrow \{ 0\}$
 $\{ b,e\} \Rightarrow \{ 1\}$
 $\{ a,d,e\} \Rightarrow \{ 0\}$
 $\{ a,b,d\} \Rightarrow \{ 0\}$
 $\{ a,b,c,e\} \Rightarrow \{ 1\}$

 $\{ a,d\} \Rightarrow \{ 0\}$
 $\{ b,e\} \Rightarrow \{ 1\}$

3.2 实验分析

4 结束语

 [1] WILLE R. Restructuring lattice theory: an approach based on hierarchies of concepts[M]//RIVAL I. Ordered Sets. Dordrecht: Springer, 1982: 445−470. (0) [2] SUTTON A, MALETIC J I. Recovering UML class models from C++: a detailed explanation[J]. Information and software technology, 2007, 49(3): 212-229. DOI:10.1016/j.infsof.2006.10.011 (0) [3] 黄微, 高俊峰. 基于概念格的Web学术信息搜索结果的二次组织[J]. 现代图书情报技术, 2010(5): 8-12. HUANG Wei, GAO Junfeng. A second organization of academic retrieved results based on concept lattice[J]. New technology of library and information service, 2010(5): 8-12. (0) [4] 沈夏炯, 叶曼曼, 甘甜, 等. 基于概念格的信息检索及其树形可视化[J]. 计算机工程与应用, 2017, 53(3): 95-99. SHEN Xiajiong, YE Manman, GAN Tian, et al. Information retrieval based on concept lattice and its tree visualization[J]. Computer engineering and applications, 2017, 53(3): 95-99. DOI:10.3778/j.issn.1002-8331.1507-0017 (0) [5] MISSAOUI R, GODIN R, BOUJENOUI A. Extracting exact and approximate rules from databases[C]//Proceedings of SOFTEKS Workshop on Incompleteness and Uncertainty in Information Systems. Berlin, Heidelberg: Springer, 1993: 209−222. (0) [6] 康向平, 苗夺谦. 一种基于概念格的集值信息系统中的知识获取方法[J]. 智能系统学报, 2016, 11(3): 287-293. KANG Xiangping, MIAO Duoqian. A knowledge acquisition method based on concept lattice in set-valued information systems[J]. CAAI transactions on intelligent systems, 2016, 11(3): 287-293. (0) [7] LIU Yong, KANG Xiangping, MIAO Duoqian, et al. A knowledge acquisition method based on concept lattice and inclusion degree for ordered information systems[J]. International journal of machine learning and cybernetics, 2019, 10(11): 3245-3261. DOI:10.1007/s13042-019-01014-4 (0) [8] 张功亮, 陈钰, 周茜, 等. 基于领域本体的信息语义相关检索[J]. 计算机工程, 2011, 37(20): 33-35, 38. ZHANG Gongliang, CHEN Yu, ZHOU Xi, et al. Information semantic relativity retrieval based on domain ontology[J]. Computer engineering, 2011, 37(20): 33-35, 38. DOI:10.3969/j.issn.1000-3428.2011.20.012 (0) [9] 刘保相, 孟肖丽. 基于关联分析的气象云图识别问题研究[J]. 智能系统学报, 2014, 9(5): 595-601. LIU Baoxiang, MENG Xiaoli. The study on nephogram recognition based on relational analysis[J]. CAAI transactions on intelligent systems, 2014, 9(5): 595-601. (0) [10] 陈湘, 吴跃. 基于概念格挖掘GIS中的关联规则[J]. 计算机应用, 2011, 31(3): 686-689. CHEN Xiang, WU Yue. Mining association rules of geographic information system based on concept lattice[J]. Journal of computer applications, 2011, 31(3): 686-689. DOI:10.3724/SP.J.1087.2011.00686 (0) [11] WU Weizhi, LEUNG Y, MI Jusheng. Granular computing and knowledge reduction in formal contexts[J]. IEEE transactions on knowledge and data engineering, 2009, 21(10): 1461-1474. DOI:10.1109/TKDE.2008.223 (0) [12] MI Jusheng, WU Weizhi, ZHANG Wenxiu. Approaches to knowledge reduction based on variable precision rough set model[J]. Information sciences, 2004, 159(3−4): 255-272. (0) [13] MI Jusheng, LEUNG Y, WU Weizhi. Approaches to attribute reduction in concept lattices induced by axialities[J]. Knowledge-based systems, 2010, 23(6): 504-511. DOI:10.1016/j.knosys.2010.03.007 (0) [14] CHEN Jinkun, LI Jinjin. An application of rough sets to graph theory[J]. Information sciences, 2012, 201: 114-127. DOI:10.1016/j.ins.2012.03.009 (0) [15] CHEN Jinkun, MI Jusheng, XIE Bin, et al. A fast attribute reduction method for large formal decision contexts[J]. International journal of approximate reasoning, 2019, 106: 1-17. DOI:10.1016/j.ijar.2018.12.002 (0) [16] SHAO Mingwen, LEUNG Y, WU Weizhi. Rule acquisition and complexity reduction in formal decision contexts[J]. International journal of approximate reasoning, 2014, 55(1): 259-274. DOI:10.1016/j.ijar.2013.04.011 (0) [17] LI Jinhai, MEI Changlin, LV Yuejin. Knowledge reduction in decision formal contexts[J]. Knowledge-based systems, 2011, 24(5): 709-715. DOI:10.1016/j.knosys.2011.02.011 (0) [18] LI Jinhai, MEI Changlin, LV Yuejin. Knowledge reduction in real decision formal contexts[J]. Information sciences, 2012, 189: 191-207. DOI:10.1016/j.ins.2011.11.041 (0) [19] LI Jinhai, MEI Changlin, WANG Junhong, et al. Rule-preserved object compression in formal decision contexts using concept lattices[J]. Knowledge-based systems, 2014, 71: 435-445. DOI:10.1016/j.knosys.2014.08.020 (0) [20] QI Jianjun, WEI Ling, YAO Yiyu. Three-way formal concept analysis[C]//Proceedings of the 9th International Conference on Rough Sets and Knowledge Technology. Shanghai: Springer, 2014: 732−741. (0) [21] REN Ruisi, WEI Ling. The attribute reductions of three-way concept lattices[J]. Knowledge-based systems, 2016, 99: 92-102. DOI:10.1016/j.knosys.2016.01.045 (0) [22] WEI Ling, LIU Lin, QI Jianjun, et al. Rules acquisition of formal decision contexts based on three-way concept lattices[J]. Information sciences, 2020, 516: 529-544. DOI:10.1016/j.ins.2019.12.024 (0) [23] LI Junyu, WANG Xia, WU Weizhi, et al. Attribute reduction in inconsistent formal decision contexts based on congruence relations[J]. International journal of machine learning and cybernetics, 2017, 8(1): 81-94. DOI:10.1007/s13042-016-0586-z (0) [24] 张继福, 张素兰, 郑链. 加权概念格及其渐进式构造[J]. 模式识别与人工智能, 2005, 18(2): 171-176. ZHANG Jifu, ZHANG Sulan, ZHENG Lian. Weighted concept lattice and incremental construction[J]. Pattern recognition and artificial intelligence, 2005, 18(2): 171-176. DOI:10.3969/j.issn.1003-6059.2005.02.008 (0) [25] 张素兰, 郭平, 张继福. 基于信息熵和偏差的加权概念格内涵权值获取[J]. 北京理工大学学报, 2011, 31(1): 59-63. ZHANG Sulan, GUO Ping, ZHANG Jifu. Intension weight value acquisition of weighted concept lattice based on information entropy and deviance[J]. Transactions of Beijing Institute of Technology, 2011, 31(1): 59-63. (0)