﻿ 不完备数据中面向特征值更新的增量特征选择方法
«上一篇
 文章快速检索 高级检索

 智能系统学报  2021, Vol. 16 Issue (3): 493-501  DOI: 10.11992/tis.202006045 0

### 引用本文

TANG Rong, LUO Chuan, CAO Qian, et al. Incremental approach for feature selection in incomplete data while updating feature values[J]. CAAI Transactions on Intelligent Systems, 2021, 16(3): 493-501. DOI: 10.11992/tis.202006045.

### 文章历史

Incremental approach for feature selection in incomplete data while updating feature values
TANG Rong , LUO Chuan , CAO Qian , WANG Sizhao
College of Computer Science, Sichuan University, Chengdu 610065, China
Abstract: In practical application, data often exhibits incomplete and dynamic characteristics. For the feature selection problem in dynamic incomplete data, an incremental feature selection method based on the tolerance rough set model and information entropy theory is proposed. First, the update patterns of conditional partition and decision classification are established based on the variation of feature values in incomplete information systems. The incremental computing mechanism of incomplete tolerance information entropy as the evaluation criterion of feature importance is built subsequently. Such an incremental mechanism is integrated into the iterative calculation of feature importance during the heuristic search of optimal feature subset, and an incremental feature selection algorithm for dynamic variation of feature values is developed. Finally, the effectiveness and efficiency of the proposed incremental algorithm are verified on several standard UCI datasets in terms of classification accuracy, decision performance, and computing efficiency.
Key words: feature selection    dimensional reduction    rough set    information entropy    incomplete data    missing values    heuristic search    incremental learning

1 基本概念

 ${\rm{IND}}(P) = \{ (x,y) \in U \times U|\forall a \in P,f(x,a) = f(y,a)\}$

${\rm{IND}}(P)$ 是具有自反性、对称性与传递性的等价关系。等价关系 ${\rm{IND}}(P)$ 将论域 $U$ 划分为等价类的集合，表示为 $U/{\rm{IND}}(P) = \{ {[x]_P}|x \in U\}$ ，其中 ${[x]_P} =$ $\{ y|(x,y) \in {\rm{IND}}(P)\}$ 。为了处理含有缺失值的不完备决策系统，Kryszkiewicz提出一种新的二元关系 $T(P),P \subseteq C$ ，定义为

 $\begin{array}{l} T(P) = \{ (x,y) \in U \times U|\forall a \in P,f(x,a) = f(y,a) \vee \\ \quad\quad\quad f(x,a) = * \vee f(y,a) = *\} \end{array}$

$T(P)$ 是具有自反性和对称性，但不具有传递性的相容关系。在P下任意一个对象 $x \in U$ 的相容类定义为 ${T_P}(x) = \{ y \in U|(x,y) \in T(P)\}$ $U/T(P)$ 表示相容类集合 $\{ T(P)|x \in U\}$ $U/T(P)$ 中构成论域 $U$ 上的一个覆盖，对于论域中任意一个对象 $x \in U,{T_P}(x) \ne \text{Ø}$ ，并且 ${ \cup _{x \in U}}{T_P}(x) = U$ 。给定一个不完备决策系统 ${\rm{IDS}} = (U,C \cup \{ d\} ,V,f)$ ，决策属性 $d$ 将对象分类为 $m$ 个确定互斥的子集 $U/d = \{ {D_1},{D_2}, \cdots ,{D_m}\}$ 。目标决策概念 ${D_i} \in U/D$ 的上、下近似集定义为

 $\begin{array}{l} \quad\underline {{\rm{apr}}} ({D_i}) = \{ x \in U|{T_P}(x) \subseteq {D_i}\} \\ \overline {{\rm{apr}}} ({D_i}) = \{ x \in U|{T_P}(x) \cap {D_i} \ne \text{Ø}\} \end{array}$

 $H(d|P) = - \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^m {\frac{{|{T_P}({x_i}) \cap {D_j}|}}{{|U|}}{\log_2} } } \frac{{|{T_P}({x_i}) \cap {D_j}|}}{{|{T_P}({x_i})|}}$ (1)

 ${\rm{sig}}(a,P,d) = H(d|P) - H(d|P - \{ a\} )$
2 不完备数据集中特征值更新的增量特征选择

 $\begin{array}{l} U/T'(P) = \{ {{T'}_P}({x_i})|i = 1,2, \cdots ,p,p + 1, \cdots ,\\ \quad\quad\quad q,q + 1, \cdots ,k, k + 1, \cdots ,n\} \end{array}$

 $U/d = \{ {D'_j}|j = 1,2, \cdots ,{q_1},{q_1} + 1, \cdots ,{q_2},{q_2} + 1, \cdots ,m\}$

 $\begin{array}{l}\quad\quad\quad\quad\quad\quad\quad \left|{{T}^{\prime }}_{P}({x}_{i})\cap {D}^{\prime }\right|=\\ \left\{\begin{array}{*{20}{l}}|{T}_{P}({x}_{i})\cap {D}_{j}|,\quad 1\leqslant j\leqslant {q}_{1}\\ \begin{array}{l}|{T}_{P}({x}_{i})\cap {D}_{j}|-|{T}_{P}^-({x}_{i})\cap {D}_{j}|-\\ |{T}_{P}({x}_{i})\cap {D}_{j}^-|+|{T}_{P}^-({x}_{i})\cap {D}_{j}^-|,\end{array}\quad {{q}_{1}+1\leqslant j\leqslant {q}_{2}}\\ |{T}_{P}({x}_{i})\cap {D}_{j}|-|{T}_{P}^-({x}_{i})\cap {D}_{j}|-\\ \begin{array}{l}|{T}_{P}({x}_{i})\cap {T}_{P}^-({x}_{i})|+|{T}_{P}^-({x}_{i})\cap {D}_{j}^-|+\\ |{T}_{P}^+({x}_{i})\cap {D}_{j}^+|\end{array},\quad{q}_{2}+1\leqslant j\leqslant m \end{array}\right.\end{array}$

 $\begin{array}{l} \quad\quad\quad\quad\quad\quad\quad|{{T'}_P}({x_i}) \cap {{D'}_j}| = \\ \left\{ {\begin{array}{*{20}{l}} {|{T_P}({x_i}) \cap {D_j}|,}\quad{1 \leqslant j \leqslant {q_1}} \\ \begin{array}{l} \!\!\!\!\!|{T_P}({x_i}) \cap {D_j}| - |T_P^ - ({x_i}) \cap {D_j}| - \\ \!\!\!\!\!|{T_P}({x_i}) \cap D_j^ - | + |T_P^ - ({x_i}) \cap D_j^ - |, \\ \end{array} \quad{{q_1} + 1 \leqslant j \leqslant m} \end{array}} \right. \end{array}$

 ${H'_U}(d|P) = {H_U}(d|P) + \varDelta$

 $\begin{split}\varDelta =-{\displaystyle\sum\limits_{i=p+1}^{q}{\displaystyle\sum\limits_{j=1}^{m}\dfrac{|{{T}^{\prime }}_{P}({x}_{i})\cap {{D}^{\prime }}_{j}|}{\left|U\right|}\mathrm{log_2}\dfrac{|{{T}^{\prime }}_{P}({x}_{i})\cap {{D}^{\prime }}_{j}|}{|{{T}^{\prime }}_{P}({{x}^{\prime }}_{i})|}+}}\\ {\displaystyle\sum\limits_{i=p+1}^{n}{\displaystyle\sum\limits_{j=1}^{m}\dfrac{|{T}_{P}({x}_{i})\cap {D}_{j}|}{\left|U\right|}}} \mathrm{log_2}\dfrac{|{T}_{P}({x}_{i})\cap {D}_{j}|}{|{T}_{P}({x}_{i})|}+\quad\quad\\ {\displaystyle\sum\limits_{i=q+1}^{n}{\displaystyle\sum\limits_{j={q}_{1}+1}^{m}\Bigg(\frac{|{T}_{P}^-({x}_{i})\cap {D}_{j}|+|{T}_{P}({x}_{i})\cap {D}_{j}^-|}{\left|U\right|}}}- \quad\quad\\ \dfrac{|{T}_{P}^-({x}_{i})\cap {D}_{j}^-|+|{T}_{P}({x}_{i})\cap {D}_{j}|+|{T}_{P}^+({x}_{i})\cap {D}_{j}^+|}{\left|U\right|}\Bigg) \cdot \quad\\ \mathrm{log_2}\dfrac{|{{T}^{\prime }}_{P}({x}_{i})\cap {D}^{\prime }|}{|{{T}^{\prime }}_{P}({x}_{i})|}\quad\quad\quad\quad\quad\quad\quad\quad\end{split}$

1)初始化特征子集 $A = {\rm{RED}}$

2)根据特征值更新对象集合 $\Delta U$ 更新后 $U/d =$ $\{ {D'_i},{D'_2},\;\cdots ,\;{D'_m}\} ,U/T'(C) = \{ {T'_C}({x_1}),\;{T'_C}({x_2}), \;\cdots ,\; {T'_C}({x_n})\}$ $U/T'(A) = \{ {T'_A}({x_1}),{T'_A}({x_2}), \cdots ,{T'_A}({x_n})\}$ ，计算 $T_P^ - ({x_i})$ $T_P^ + ({x_i})$ $D_j^ -$ $D_j^ +$

3)计算 ${H'_U}(d|C)$ ${H'_U}(d|A)$

4)如果 ${H'_U}(d|C) \ne {H'_U}(d|A)$ 进入7)，否则进入5)；

5)当 ${H'_U}(d|C) \ne {H'_U}(d|A)$ 时，对任意 $a \in C - A$ ，计算 ${\rm{sig}}(a,A \cup \{ a\} ,d)$ ，并且选择其中拥有最大 ${\rm{sig}}(a,A \cup \{ a\} ,d)$ $a$ $A = A \cup \{ a\}$

6)对任意特征 $a \in A$ 计算 ${\rm{sig}}(a,A,d)$ ,如果 ${\rm{sig}}(a,A,d) = 0$ ，则 $A = A - \{ a\}$

7)返回A

3 实验及分析

3.1 分类精度分析

3.2 决策性能分析

6种评估函数中，特征集合 $C$ 下不完备决策系统 ${\rm{IDS}} = (U,C \cup \{ d\} ,V,f)$ 近似准确评估函数定义为

 ${a_C}(F) = \frac{{\displaystyle\sum_{{D_j} \in U/D} {|{{\underline {{\rm{apr}}} }_C}({D_j})|} }}{{\displaystyle\sum_{{D_j} \in U/D} {|{{\overline {{\rm{apr}}} }_C}({D_j})|} }}$

 ${c_C}(D) = \frac{{\displaystyle\sum\nolimits_{{D_j} \in U/D} {|{{\underline {{\rm{apr}}} }_C}({D_j})|} }}{{|U|}}$

 $\alpha ({\rm{IDS}}) = \frac{1}{m}\sum\limits_{{N_i}}^m {\frac{1}{{{N_i}}}} \sum\limits_{j = 1}^{{N_i}} {\frac{{|{X_i} \cap {D_j}|}}{{|{X_i}|}}}$

 $\beta ({\rm{IDS}})=\frac{1}{m}[1-\frac{4}{\left|{X}_{i}\right|}{\sum\limits_{j=1}^{{N}_{i}}|{X}_{i}\cap {D}_{j}|\mu ({Z}_{ij})(1-\mu ({Z}_{ij}))}]$

 $\gamma ({\rm{IDS}}) = \sum\limits_{j = 1}^n {\frac{{|{D_j}|}}{{{N_j}|U|}}\sum\limits_{k = 1}^{{N_j}} {\frac{{|{X_k} \cap {D_j}|}}{{|U|}}} }$

 $\vartheta ({\rm{IDS}}) = \frac{1}{{|U|}}\sum\limits_{i = 1}^m {\frac{{|{X_i}|}}{{|U|}}}$

3.3 效率分析

 Download: 图 1 算法HFS-CE-IDS与算法IFS-CE-IDS计算时间比较 Fig. 1 Computational time comparison between HFS-CE-IDS and IFS-CE-IDS

4 结束语

 [1] KWAK N, CHOI C H. Input feature selection by mutual information based on Parzen window[J]. IEEE transactions on pattern analysis and machine intelligence, 2002, 24(12): 1667-1671. DOI:10.1109/TPAMI.2002.1114861 (0) [2] SLOWINSKI R, VANDERPOOTEN D. A generalized definition of rough approximations based on similarity[J]. IEEE transactions on knowledge and data engineering, 2000, 12(2): 331-336. DOI:10.1109/69.842271 (0) [3] KRYSZKIEWICZ M. Rough set approach to incomplete information systems[J]. Information sciences, 1998, 112(1/2/3/4): 39-49. (0) [4] PARTHALÁIN N M, SHEN Qiang. Exploring the boundary region of tolerance rough sets for feature selection[J]. Pattern recognition, 2009, 42(5): 655-667. DOI:10.1016/j.patcog.2008.08.029 (0) [5] MENG Zuqiang, SHI Zhongzhi. Extended rough set-based attribute reduction in inconsistent incomplete decision systems[J]. Information sciences, 2012, 204: 44-69. DOI:10.1016/j.ins.2012.04.004 (0) [6] GRZYMALA-BUSSE J W, CLARK P G, KUEHNHAUSEN M. Generalized probabilistic approximations of incomplete data[J]. International journal of approximate reasoning, 2014, 55(1): 180-196. DOI:10.1016/j.ijar.2013.04.007 (0) [7] QIAN Yuhua, LIANG Jiye, PEDRYCZ W, et al. An efficient accelerator for attribute reduction from incomplete data in rough set framework[J]. Pattern recognition, 2011, 44(8): 1658-1670. DOI:10.1016/j.patcog.2011.02.020 (0) [8] DAI Jianhua. Rough set approach to incomplete numerical data[J]. Information sciences, 2013, 241: 43-57. DOI:10.1016/j.ins.2013.04.023 (0) [9] YANG Xibei, YANG Jingyu, WU Chen, et al. Dominance-based rough set approach and knowledge reductions in incomplete ordered information system[J]. Information sciences, 2008, 178(4): 1219-1234. DOI:10.1016/j.ins.2007.09.019 (0) [10] LIANG Jiye, XU Zongben. The algorithm on knowledge reduction in incomplete information systems[J]. International journal of uncertainty, fuzziness and knowledge-based systems, 2002, 10(1): 95-103. DOI:10.1142/S021848850200134X (0) [11] QIAN Yuhua, LIANG Jiye, WANG Feng. A new method for measuring the uncertainty in incomplete information systems[J]. International journal of uncertainty, fuzziness and knowledge-based systems, 2009, 17(6): 855-880. DOI:10.1142/S0218488509006303 (0) [12] DAI Jianhua, WANG Wentao, XU Qing. An uncertainty measure for incomplete decision tables and its applications[J]. IEEE transactions on cybernetics, 2013, 43(4): 1277-1289. DOI:10.1109/TSMCB.2012.2228480 (0) [13] ZHAO Hua, QIN Keyun. Mixed feature selection in incomplete decision table[J]. Knowledge-based systems, 2014, 57: 181-190. DOI:10.1016/j.knosys.2013.12.018 (0) [14] RAGHAVAN V, HAFEZ A. Dynamic data mining[C]//Proceedings of the 13th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems. New Orleans, Louisiana, USA, 2000. (0) [15] LI Tianrui, RUAN Da, GEERT W, et al. A rough sets based characteristic relation approach for dynamic attribute generalization in data mining[J]. Knowledge-based systems, 2007, 20(5): 485-494. DOI:10.1016/j.knosys.2007.01.002 (0) [16] XU Yitian, WANG Laisheng, ZHANG Ruiyan. A dynamic attribute reduction algorithm based on 0-1 integer programming[J]. Knowledge-based systems, 2011, 24(8): 1341-1347. DOI:10.1016/j.knosys.2011.06.007 (0) [17] QIAN Jin, DANG Chuangyin, YUE Xiaodong, et al. Attribute reduction for sequential three-way decisions under dynamic granulation[J]. International journal of approximate reasoning, 2017, 85: 196-216. DOI:10.1016/j.ijar.2017.03.009 (0) [18] YANG Yanyan, CHEN Degang, WANG Hui, et al. Incremental perspective for feature selection based on fuzzy rough sets[J]. IEEE transactions on fuzzy systems, 2018, 26(3): 1257-1273. DOI:10.1109/TFUZZ.2017.2718492 (0) [19] LANG Guangming, CAI Mingjie, FUJITA H, et al. Related families-based attribute reduction of dynamic covering decision information systems[J]. Knowledge-based systems, 2018, 162: 161-173. DOI:10.1016/j.knosys.2018.05.019 (0) [20] WEI Wei, WU Xiaoying, LIANG Jiye, et al. Discernibility matrix based incremental attribute reduction for dynamic data[J]. Knowledge-based systems, 2018, 140: 142-157. DOI:10.1016/j.knosys.2017.10.033 (0) [21] ZENG Anping, LI Tianrui, LIU Dun, et al. A fuzzy rough set approach for incremental feature selection on hybrid information systems[J]. Fuzzy sets and systems, 2015, 258: 39-60. DOI:10.1016/j.fss.2014.08.014 (0) [22] LIANG Jiye, WANG Feng, DANG Chuangyin, et al. A group incremental approach to feature selection applying rough set technique[J]. IEEE transactions on knowledge and data engineering, 2014, 26(2): 294-308. DOI:10.1109/TKDE.2012.146 (0) [23] SHU Wenhao, SHEN Hong. Incremental feature selection based on rough set in dynamic incomplete data[J]. Pattern recognition, 2014, 47(12): 3890-3906. DOI:10.1016/j.patcog.2014.06.002 (0) [24] XIE Xiaojun, QIN Xiaolin. A novel incremental attribute reduction approach for dynamic incomplete decision systems[J]. International journal of approximate reasoning, 2018, 93: 443-462. DOI:10.1016/j.ijar.2017.12.002 (0) [25] WANG Feng, LIANG Jiye, DANG Chuangyin. Attribute reduction for dynamic data sets[J]. Applied soft computing, 2013, 13(1): 676-689. DOI:10.1016/j.asoc.2012.07.018 (0) [26] 刘吉超, 王锋, 宋鹏. 缺失数据的维数增量式特征选择[J]. 计算机工程与应用, 2019, 55(17): 95-99. LIU Jichao, WANG Feng, SONG Peng. Dimension incremental feature selection algorithm for missing data[J]. Computer engineering and applications, 2019, 55(17): 95-99. DOI:10.3778/j.issn.1002-8331.1806-0029 (0) [27] 钱进, 朱亚炎. 面向成组对象集的增量式属性约简算法[J]. 智能系统学报, 2016, 11(4): 496-502. QIAN Jin, ZHU Yayan. An incremental attribute reduction algorithm for group objects[J]. CAAI transactions on intelligent systems, 2016, 11(4): 496-502. (0) [28] QIAN Yuhua, DANG Chuangyin, LIANG Jiye, et al. On the evaluation of the decision performance of an incomplete decision table[J]. Data & knowledge engineering, 2008, 65(3): 373-400. (0)