﻿ 决策蕴含简化算法研究

# 决策蕴含简化算法研究Simplification of Implication on Decision-Making

Abstract: As the size of data table grows, the concepts generated become larger in number, which make de-cision-making more complex. The majority of references focused on acquisition of decision rules based on decision formal context which was given. This paper focuses on simplification of implication on decision-making for the first time, makes use of computer simulating the procedures of human thought, via computing the covers of object set, computes decision formal context, which forms the basis of this paper, non-redundant limitary decision implication with more simplified form is deduced compared to decision rules meanwhile, which is beneficial to decision makers; secondly, puts forward judging theorems of handling redundant limitary decision implications and generating decision formal context with demonstration in order to make decision-making simplified; subsequently, proposes an algorithm and discusses the time complexity. Comparing with other algorithms on runtime and ability of classification, experimental results show that the proposed method approves feasibility and accuracy. In the end, it draws a conclusion and discusses open issues.

1. 引言

2. 概念格理论基础

$A\subset X$$B\subset Y$，则：

${A}^{\ast }=\left\{y|\forall x\in A,I\left(x,y\right)=1\right\}$

${B}^{\ast }=\left\{x|\forall y\in B,I\left(x,y\right)=1\right\}$

$〈A,B〉$ 是一个概念当且仅当 $A={B}^{*}$$B={A}^{*}$。其中A为概念的外延，B为概念的内涵。

$B\subseteq {B}_{1}$ 并且没有 $〈{A}_{2},{B}_{2}〉$ 满足 $B\subseteq {B}_{2}\subseteq {B}_{1}$，则 $〈{A}_{1},{B}_{1}〉$$〈A,B〉$ 的后继。

$\forall a\in Y$$〈{a}^{\ast },{a}^{\ast \ast }〉$ 为基于属性的概念。

${Y}_{1}\subseteq Y$$〈{Y}_{1}^{\ast },{Y}_{1}^{\ast \ast }〉$ 为形式概念。

${X}_{1}\subseteq X$$〈{X}_{1}^{\ast \ast },{X}_{1}^{\ast }〉$ 为形式概念。

3. 非冗余限制决策蕴含相关理论

$L\left(I\right)=\left(\left(X,Y,I\right),\le \right)$ 为基于条件属性的概念格， $L\left({I}_{1}\right)=\left(\left(X,T,J\right),\le \right)$ 为基于决策属性的概念格，若 $\forall 〈A,B〉\in L\left(I\right)$$〈C,D〉\in L\left({I}_{1}\right)$，满足 $A\subseteq C$，且 $C\ne X,C\ne \varnothing$，则称 $B\to D$ 是一个规则，B为规则的前置条件，D为规则的结论。若 $A=C$，则称 $B\to D$ 为强规则；若 $A\subset C$，则称为弱规则。若存在，有，则规则为冗余规则。

，满足，且，则有强规则，弱规则，且弱规则为冗余规则。

，且，规则为非冗余规则，则不存在，满足，也不存在，满足，否则为冗余规则。

，满足，且不，满足，使，为使决策过程简单，则

，满足，且，有，则

，若，则为X的一个覆盖。

，满足，则

，满足，则为F的约简。

4. 决策蕴含简化方法及属性约简算法

(1) 生成条件概念

(2) 求X的覆盖

;/*按eno降序对概念进行快速排序*/

;;

for (i=2;i 1;i++)

{;

if() {no=i;; break;}

}/*数组t存决策属性*/

(3) 生成决策背景

while()

{for(k=1;; k++)

; j++; k++/*二维数组DC存决策背景*/

}

(4) 生成决策概念

(5) 调用最小闭标生成算法

(6) 生成限制决策蕴含

for each

for each

if()

{;

;/*结构体数组LDI存限制决策蕴含，其有三个成员，存前置条件，存结论，存前置条件中属性的个数*/

break;

}

(7) 冗余限制决策蕴含处理

for each

for each

{if(in && in)m++;

if()

} /*前置条件和结论是其它限制决策蕴含的并集的限制决策蕴含为冗余限制决策蕴含*/

(8) 限制决策蕴含输出

for each

Output:;

5. 实验分析

Table 1. Formal context

Table 2. Concepts based on formal context

Figure 1. The concept lattice based on conditional attributes

Table 3. Concepts after sorted and minimal closed label

Table 4. Decision formal context

Table 5. Concepts based on decision-making attributes

Figure 2. The concept lattice based on decision-making attributes

Table 6. Comparison with rules

Figure 3. Running efficiency

Table 7. Decision formal context after reduction

Table 8. Conditional concepts after reduction

Table 9. Comparison with ability of classification

6. 总结

NOTES

*通讯作者。

[1] Wille, R. (1982) Restructuring Lattice Theory: An Approach Based on Hierarchies of Concepts. In: Rival, Ordered Sets, Springer, Reidel, Dordrecht, 445-470.
https://doi.org/10.1007/978-94-009-7798-3_15

[2] Berry, A. and Sigayret, A. (2004) Representing a Concept Lattice by a Graph. Discrete Applied Mathematics, 144, 27-42.
https://doi.org/10.1016/j.dam.2004.02.016

[3] Skowron, A. and Rauszer, C. (1992) The Discernibility Matrices and Functionsin Information Systems. In: Intelligent Decision Support. Handbook of Applications and Advances of the Rough Sets Theory, Springer, Dordrecht, 331-340.
https://doi.org/10.1007/978-94-015-7975-9_21

[4] Sabita Mahapatra, S. (2010) Attribute Selection in Marketing: A Rough Set Approach. IIMB Management Review, 22, 6-24.
https://doi.org/10.1016/j.iimb.2010.03.001

[5] 李进金, 张燕兰, 吴伟志, 等. 形式背景与协调决策形式背景属性约简与概念格生成[J]. 计算机学报, 2014. 37(8): 1768-1772.

[6] 张文修, 魏玲, 祁建军. 概念格的属性约简理论与方法[J]. 中国科学E辑信息科学, 2005, 35(6): 628-639.

[7] 王霞, 张文修. 概念格的属性约简与属性特征[J]. 计算机工程与应用, 2008, 44(12): 1-4.

[8] Qian, W.B. and Shu, W.H. (2018) Attribute Reduction in Incomplete Ordered Information Systems with Fuzzy Decision. Applied Soft Computing Journal, 73, 242-253.
https://doi.org/10.1016/j.asoc.2018.08.032

[9] Mao, H. (2017) Representing Attribute Reduction and Concepts in Concept Lattice Using Graphs. Soft Computing, 21, 7293-7311.
https://doi.org/10.1007/s00500-016-2441-2

[10] Zhou, J.-Q. and Nie, H.-M. (2018) Research on Attribute Reduc-tion Algorithm in Covering Granular Computing Model. Proceedings of the 2018 International Conference on Machine Learning and Cybernetics, Chengdu, 15-18 July 2018, 15-18.
https://doi.org/10.1109/ICMLC.2018.8527018

[11] Thuy, N.N. and Wongthanavasu, S. (2020) A New Approach for Reduction of Attributes Based on Stripped Quotient Sets . Pattern Recognition, 97, Article ID: 106999.
https://doi.org/10.1016/j.patcog.2019.106999

[12] Li, J.H., Kumar, C.A., Mei, C., et al. (2017) Comparison of Reduction in Formal Decision Contexts. International Journal of Approximate Reasoning, 80, 100-122.
https://doi.org/10.1016/j.ijar.2016.08.007

[13] 魏玲, 祁建军, 张文修. 决策形式背景的概念格属性约简[J]. 中国科学 E 辑: 信息科学 2008, 38(2): 195-208.

[14] Li, J., Huang, C., Mei, C., et al. (2016) An Intensive Study on Rule Acquisition in Formal Decision Contexts Based on Minimal Closed Label Concept Lattices. Intelligent Automation & Soft Computing, 8, 1-13.

[15] 郭松涛, 李金海, 吕跃进, 等. 决策形式背景的启发式属性约简算法[J]. 计算机工程与应用, 2012, 48(10): 21-23.

[16] Wang, C., He, D.D., Wang, L., et al. (2016) Research on Attribute Reduction Based on Concept with Introducer. ICNC-FSKD 2016, Changsha, 1318-1323.
https://doi.org/10.1109/FSKD.2016.7603369

[17] Wang, C. and Yu, X. (2014) Research on Attribute Reduction Based on L-context. ICNC-FSKD 2014, Xiamen, 450-455.
https://doi.org/10.1109/FSKD.2014.6980875

[18] Wang, C., Yu, X., Xu, C., et al. (2013) Research on Computing the Covers of a Given Concept. Applied Mechanics and Materials, Switzerland, 496-500.
https://doi.org/10.4028/www.scientific.net/AMM.467.496

[19] 王璨, 侯洪凤, 郭文书, 等. 基于决策规则的属性约简算法研究[J]. 山西大学学报(自然科学版), 2016, 39(3): 349-356.

[20] 张文修, 仇国芳, 吴伟志. 粗糙集属性约简的一般理论[J]. 中国科学E辑: 信息科学, 2005, 35(12): 1304-1313.

[21] 宫玺. 概念格的构造、约简及形式概念分析的应用[D]: [硕士学位论文]. 辽宁: 辽宁科技大学, 2008: 25-34.

[22] 张文修, 仇国芳. 基于粗糙集的不确定决策[M]. 北京: 清华大学出版社, 2005: 75-100.

[23] 郑丽英, 王庆荣, 刘丽艳. 面向属性的粗集数据挖掘方法研究[J]. 兰州理工大学学报, 2005, 31(2): 88-91.

Top