2. 巢湖学院 网络与分布式研究所, 合肥 238000
2. Institute of Networks and Distributed System, Chaohu University, Hefei 238000, China
粗糙集理论[1-2]是模糊信息系统中处理不精确、非完备、非协调信息等典型的数学工具.目前, 已成功应用于数据挖掘、机器学习、规则生成、故障诊断、风险预测等领域[3-7].
属性约简是粗糙集理论研究的核心内容之一, 旨在保持区分能力不变的情况下, 剔除冗余的属性, 用最少的属性代替原有样本, 从而达到约简的效果.近年来, 粗糙集研究者们提出了多种属性重要性的度量方法, 并以此为基础设计很多启发式属性约简算法.对于启发式属性约简算法可归纳为两类:代数观和信息观.前者以不可分辨关系为基础, 研究属性对论域中确定分类子集的影响, 以代数式方式定义属性重要性, 主要算法有基于正区域算法[8-10]和基于差别矩阵算法[11-13].后者从信息粒度考虑, 研究属性对论域中不确定分类子集的影响、有效度量知识的粒度大小.
信息熵是由香农于1948年提出的度量物质状态变化的概念[14], 后来逐渐被研究者们引入粗糙集中, 用于不确定性信息度量.相应地, 基于熵的属性约简也应运而生[15-21].王国胤[15]给出了基于条件信息熵的属性约简算法; 杨明[16]提出了"基于条件信息熵的近似约简", 算法依据实际应用的需要有效地对冗余属性进行取舍, 可有效增强抗噪声、抗干扰的能力, 对基于条件信息熵的决策表属性约简起到了完善和补充作用; 张清华[17]根据模糊熵及模糊度能度量不确定性的特点, 提出了在决策系统中修正条件信息熵和相对模糊熵的概念, 根据熵在知识粒度细分过程中表现的单调性, 证 明两种熵的合理性, 利用向前添加算法得到熵的约简算法, 为其他信息熵约简质量提供了参考.
现有的基于熵的属性约简方法, 多数仅从信息论的角度度量属性重要性, 很少有人有效结合代数观来定义属性重要性.王国胤在文献[15]中指出并证 明了代数观与信息论定义的属性重要性具有较强的互补性:代数观考虑确定分类子集的影响, 而信息论考虑不确定分类子集的影响.属性重要性度量方法的客观性, 直接影响到属性约简结果及系统的时间消耗.为了快速、准确找到最重要的属性, 有必要综合考虑多种因素, 有机结合代数观及信息论的特点, 定义一种更加全面的属性重要性度量方法.另外, 现有的基于熵的属性约简算法有较高的时间复杂度, 还有待于进一步改进.
针对上述问题, 文献[19]提出了近似决策熵, 有效结合代数观下的近似精度与信息论下的条件熵, 得到了一种较全面的属性重要性度量方法.为进一步探究客观、全面的度量方法, 本文提出了一种新的代数观下的信息熵模型-近似边界精度信息熵, 有效地结合了代数观与信息论的特点.首先在代数观下计算正区域对边界精度的影响, 提出并证 明了近似边界精度与近似精度具有相同单调性, 同时还提出了有放大作用的"修正的近似边界精度"; 其次, 从信息论角度考虑, 以文献[17]的相对模糊熵为基础, 提出了相对信息熵和增强信息熵概念, 证 明了本文提出的两种信息熵的单调性与合理性, 同时比相对模糊熵具有放大属性重要的作用; 然后, 将修正近似边界精度与两种熵相融合, 产生了新的约简方法; 最后, 通过实验与6种同类算法在约简时间和约简剩余属性数方面进行了比较, 并将约简结果在SVM分类器上利用径向基核进行了相关参数设定, 通过十折交叉法进行了分类精度的验证.
本文基于近似边界精度信息熵提出相对信息熵约简算法(Approximate Boundary Accuracy Entropy, ABAE)及增强信息熵约简算法(ABAE’).在约简过程中, 由于近似边界精度相对信息熵及增强信息熵呈现非严格单调情况, 从而为算法的合理性提供依据.同时, 新模型在同等条件下衡量属性重要性时, 比文献[17]的相对模糊熵有明显的放大作用, 为新算法能够快速选择出最重要的属性提供有效的途径.由于本文算法充分考虑了确定分类和不确定分类对约简的影响, 所以新的信息熵模型更全面; 本文的实验数据分析有力证实了新模型下的约简算法的可行性、有效性.另外, 根据实验还可得知, 新的信息熵模型下的优势(时间性能及约简质量)及存在的不足(受离群率高低的影响较大), 可为属性约简的算法选择提供合理的参考.
1 粗糙集相关概念定义1 给定决策表
$ \begin{equation} {\rm ind}(B)=\{(x, y)\in U^2\vert \forall b\in B, f(x, b)=f(y, b)\}, \end{equation} $ | (1.1) |
其中, 关系ind
性质1 给定决策表
证 明 (1)若
(2) 另外, 假设
综合(1)(2)所得,
(3)
定义2 给定决策表
$ \overline {B(X)} =\{x\in U\vert [x]_B \cap X\ne \varnothing \}\;=\bigcup \{[x]_B \in U/B\vert [x]_B \cap X\ne \varnothing \}, $ | (1.2) |
$ \underline{B(X)}=\{x\in U\vert [x]_B \subseteq X\}=\bigcup \{[x]_B \in U/B\vert [x]_B \subseteq X\}. $ | (1.3) |
显然, 粗糙集的上、下近似集将论域分割成正区域、负区域及边界域, 其中, 正区域POS
定义3 给定决策表
$ \begin{align} \alpha _B (X)=\frac{\left| {\underline{B(X)}} \right|}{\left| {\overline {B(X)} } \right|}. \end{align} $ | (1.4) |
定义4 给定决策表
$ \begin{equation} \beta _B (X)=\frac{\left| {{\rm POS}_B (X)} \right|}{\left| {{\rm BND}(X)} \right|}. \end{equation} $ | (1.5) |
性质2 给定决策表
证 明
$ \begin{align*} \beta _B (X)=\frac{\left| {{\rm POS}_B (X)} \right|}{\left| {{\rm BND}(X)} \right|} =\frac{\left| {\underline{B(X)}} \right|}{\left| {\overline {B(X)} } \right|-\left| {\underline{B(X)}} \right|} =\dfrac{\textstyle{{\left| {\underline{B(X)}} \right|} \over {\left| {\overline {B(X)} } \right|}}}{1-\textstyle{{\left| {\underline{B(X)}} \right|} \over {\left| {\overline {B(X)} } \right|}}} =\frac{\alpha _B (X)}{1-\alpha _B (X)}. \end{align*} $ |
(1) 当
(2)
综合(1)(2),
为了计算范围统一, 且控制在[0
定义5 给定决策表
性质3 给定决策表
证 明 (1)因
(2)
定义6[17] 给定决策表
$ \begin{equation} E'(D_B )=\sum\limits_{j=1}^n {\sum\limits_{i=1}^m {\left| {X_i } \right|\frac{\left| {X_i \cap Y_j } \right|}{\left| {X_i } \right|}} } \Big(1-\frac{\left| {X_i \cap Y_j } \right|}{\left| {X_i } \right|}\Big), \end{equation} $ | (2.1) |
修正条件信息熵的等价形式为
$ \begin{align} H'(D_B )=&-\sum\limits_{i=1}^n {\vert X_i \vert } \times \sum\limits_{j=1}^m \Big[\frac{\vert X_i \cap X_j \vert }{\vert X_i \vert }lb\frac{\vert X_i \cap X_j \vert }{\vert X_i \vert } \nonumber\\ &+\Big(1-\frac{\vert X_i \cap X_j \vert }{\vert X_i \vert }\Big)lb\Big(1-\frac{\vert X_i \cap X_j \vert }{\vert X_i \vert }\Big)\Big]. \end{align} $ | (2.2) |
定义7 给定决策表
$ \begin{equation} {\rm AE}(D_B )=\left\{\!\! {\begin{array}{l} \displaystyle\sum\limits_{j=1}^m \sum\limits_{i=1}^n \left| {X_i } \right| \Big[ {{1-P(Y_j \vert X_i )} \Big/ {\overline P(Y_j \vert X_i)}}\Big], \;\;\;\;0\le P(Y_j \vert X_i )\le \dfrac{1}{2}, \\[4mm] \displaystyle\sum\limits_{j=1}^m \sum\limits_{i=1}^n \left| {X_i } \right|\Big[ {{1-\overline {P(Y_j \vert X_i )} } /{P(Y_j \vert X_i )}} \Big], \;\;\;\;\dfrac{1}{2}<P(Y_j \vert X_i )\le 1 \end{array}} \right. \end{equation} $ | (2.3) |
为决策属性
$ \begin{equation} {\rm AE}(D_B )=\left\{\!\! {\begin{array}{l} \displaystyle\sum\limits_{j=1}^m \sum\limits_{i=1}^n \left| {X_i } \right|\Big[ 1-{\dfrac{\left| {X_i \cap Y_j } \right|}{\left| {X_i } \right|}} \Big/ \Big(1-\dfrac{\left| {X_i \cap Y_j } \right|}{\left| {X_i } \right|} \Big)\;\Big], \;\;\;\;0\le \dfrac{\left| {X_i \cap Y_j } \right|}{\left| {X_i } \right|}<\dfrac{1}{2}, \\ \displaystyle \sum\limits_{j=1}^m \sum\limits_{i=1}^n {\left| {X_i } \right|} \Big[1-{ \Big(1-\dfrac{\left| {X_i \cap Y_j } \right|}{\left| {X_i } \right|} \Big)}\Big/\dfrac{\left| {X_i \cap Y_j } \right|}{\left| {X_i } \right|}\; \Big], \;\;\;\;\dfrac{1}{2}\le \dfrac{\left| {X_i \cap Y_j } \right|}{\left| {X_i } \right|}\le 1. \end{array}} \right. \end{equation} $ | (2.4) |
定理1 给定决策表
证 明 设某等价关系在
(1) 当
$ \begin{align*} {\rm AE}(D_{B_i } )=&{\rm AE}(D_{B_{i+1} } )+\left| {X_k \cup X_l } \right|\times \sum\limits_{j=1}^m \Big[1-\dfrac{\left| {(X_k \cup X_l )\cap Y_j } \right|}{\left| {X_k \cup X_l } \right|} \Big/ \Big(1-\dfrac{\left| {(X_k \cup X_l )\cap Y_j } \right|}{\left| {X_k \cup X_l } \right|}\Big) \Big] \\ &-\left| {X_k } \right|\sum\limits_{j=1}^m \Big[1\!-\!\dfrac{\left| {X_k \cap Y_j } \right|}{\left| {X_k } \right|} \!\Big/\! \Big(1\!-\!\dfrac{\left| {X_k \cap Y_j } \right|}{\left| {X_k } \right|}\Big) \Big]\!\!-\!\! \left| {X_l } \right|\sum\limits_{j=1}^m \Big[1\!-\!{\dfrac{\left| {X_l \cap Y_j } \right|}{\left| {X_l } \right|}} \!\Big/\! \Big(1\!-\!\dfrac{\left| {X_l \cap Y_j } \right|}{\left| {X_l } \right|}\Big)\Big], \\ {\rm AE}_\Delta =&{\rm AE}(D_{B_i } )-{\rm AE}(D_{B_{i+1} } ) \\ =&\displaystyle\sum\limits_{j=1}^m \Big[\left| {X_k \cup X_l } \right|\times \Big(1-\dfrac{\left| {(X_k \cup X_l )\cap Y_j } \right|}{\left| {X_k \cup X_l } \right|}\Big/ \Big(1-\dfrac{\left| {(X_k \cup X_l )\cap Y_j } \right|}{\left| {X_k \cup X_l } \right|}\Big)\Big)\\ &- \left| {X_k } \right|\times \Big(1-\dfrac{\left| {X_k \cap Y_j } \right|}{\left| {X_k } \right|} \Big/\Big(1-\dfrac{\left| {X_k \cap Y_j } \right|}{\left| {X_k } \right|}\Big)\Big) \\ & -\left| {X_l } \right|\times \Big(1-\dfrac{\left| {X_l \cap Y_j } \right|}{\left| {X_l } \right|}\Big(1-\dfrac{\left| {X_l \cap Y_j } \right|}{\left| {X_l } \right|}\Big)\Big)\Big] \\ =&\left| {X_k \cup X_l } \right|\times \Big(1-\dfrac{\left| {(X_k \cup X_l )\cap Y_j } \right|}{\left| {X_k \cup X_l } \right|-\left| {(X_k \cup X_l )\cap Y_j } \right|}\Big) \\ & - \left| {X_k } \right|\times \Big(1-\dfrac{\left| {X_k \cap Y_j } \right|}{\left| {X_k } \right|-\left| {X_k \cap Y_j } \right|}\Big) - \left| {X_l } \right|\times \Big(1-\dfrac{\left| {X_l \cap Y_j } \right|}{\left| {X_l } \right|-\left| {X_l \cap Y_j } \right|}\Big). \end{align*} $ |
因为
设
$ \begin{align*} {\rm AE}_\Delta &=\sum\limits_{j=1}^m {\Big[{-(x+y)\times \dfrac{ax+by}{x+y-ax-by}+x\times \dfrac{ax}{x-ax}+y\times \dfrac{by}{y-by}} \Big]} \\ &=\sum\limits_{j=1}^m {\dfrac{(ax+by)[xb(1-a)+ya(1-b)]}{(x+y-ax-by)\cdot (1-a)\cdot (1-b)}\ge 0}. \end{align*} $ |
(2) 当
$ \begin{align*} {\rm AE} (D_{B_{i+1} })=&\sum\limits_{j=1}^m {\sum\limits_{i=1}^n {\left| {X_i } \right|} \Big[1-\Big(1-\dfrac{\left| {X_i \cap Y_j } \right|}{\left| {X_i } \right|}\Big)\Big/ {\dfrac{\left| {X_i \cap Y_j } \right|}{\left| {X_i } \right|}} \Big]} =\sum\limits_{j=1}^m \sum\limits_{i=1}^n {\left| {X_i } \right|} \Big(2-\dfrac{\vert X_i \vert }{\vert X_i \cap Y_j \vert }\Big), \\ {\rm AE}(D_B )=&{\rm AE}(D_{Bi+1} )+\left| {X_k \cup X_l } \right|\times \sum\limits_{j=1}^m \Big(2-\dfrac{\vert X_k \cup X_l \vert }{\vert (X_k \cup X_l )\cap Y_j \vert }\Big) \\ & - \left| {X_k } \right|\sum\limits_{j=1}^m \Big(2-\dfrac{\vert X_k \vert }{\vert X_k \cap Y_j \vert }\Big) - \left| {X_l } \right|\sum\limits_{j=1}^m \Big(2-\dfrac{\vert X_l \vert }{\vert X_l \cap Y_j \vert }\Big), \\ {\rm AE}_\Delta =&{\rm AE}(D_{B_i } )-AE(D_{B_{i+1} } ) \\ &=\sum\limits_{j=1}^m \Big[{\dfrac{\vert X_k \vert ^2}{\vert X_k \cap Y_j \vert }+\dfrac{\vert X_l \vert ^2}{\vert X_l \cap Y_j \vert }-\dfrac{\vert X_k \cup X_l \vert ^2}{\vert (X_k \cup X_l )\cap Y_j \vert }} \Big]. \end{align*} $ |
设
$ \begin{align*} {\rm AE}_\Delta =\sum\limits_{j=1}^m \Big[ {\dfrac{x}{a}+\dfrac{y}{b}-\dfrac{x+y}{ax+by}} \Big] =\sum\limits_{j=1}^m \dfrac{xy(a-b)^2}{ab(ax+by)}\ge 0. \end{align*} $ |
综合(1)(2)得,
由于上述在求相对信息熵时, 每次要判断
定义8 给定决策表
$ \begin{equation} {\rm AE}'(D_B )=\sum\limits_{j=1}^m \sum\limits_{i=1}^n {\left| {X_i } \right|} \Big[1-\dfrac{\left| {X_i \cap Y_j } \right|}{2\left| {X_i } \right|}\Big/\Big(1-\dfrac{\left| {X_i \cap Y_j } \right|}{2\left| {X_i } \right|}\Big) \Big] \end{equation} $ | (2.5) |
为决策属性
定理2 在论域
证 明
$ \begin{align*} {\rm AE}'(D_B)=&{\rm AE}'(D_{B_{i+1} } )+\left| {X_i \cup Y_j } \right|\times \sum\limits_{j=1}^m \Big[1-\dfrac{\left| {X_i \cap Y_j } \right|}{2\left| {X_i } \right|} \Big/ \Big(1-\dfrac{\left| {X_i \cap Y_j} \right|}{2\left| {X_i } \right|}\Big) \Big] \\ &- \left| {X_k } \right|\sum\limits_{j=1}^m \Big[1-\dfrac{\left| {X_k \cap Y_j } \right|}{2\left| {X_k } \right|} \Big/ {\Big(1-\dfrac{\left| {X_k \cap Y_j } \right|}{2\left| {X_k } \right|}\Big)} \Big] \\ & - \left| {X_l } \right|\sum\limits_{j=1}^m \Big[1-\dfrac{\left| {X_l \cap Y_j } \right|}{2\left| {X_l } \right|} \Big/\Big(1-\dfrac{\left| {X_l \cap Y_j } \right|}{2\left| {X_l } \right|}\Big) \Big], \\ {\rm AE}'_\Delta =&\sum\limits_{j=1}^m \Big[\left| {X_k } \right|\Big({\dfrac{\left| {X_k \cap Y_j } \right|}{2\left| {X_k } \right|}}\Big/\Big(1-\dfrac{\left| {X_k \cap Y_j } \right|}{2\left| {X_k } \right|}\Big)\Big)+\left| {X_l } \right|\Big(\dfrac{\left| {X_l \cap Y_j } \right|}{2\left| {X_l } \right|} \Big/ \Big(1-\dfrac{\left| {X_l \cap Y_j } \right|}{2\left| {X_l } \right|}\Big)\Big) \\ &-{\dfrac{\left| {(X_k \cup X_l )\cap Y_j } \right|\cdot \left| {X_k \cup X_l } \right|}{2\left| {X_k \cup X_l } \right|}} \Big/\Big(1-\dfrac{\left| {(X_k \cup X_l )\cap Y_j } \right|}{2\left| {X_k \cup X_l } \right|}\Big)\Big]. \end{align*} $ |
设
$ \begin{align*} {\rm AE}'_\Delta \!=\!\sum\limits_{j=1}^m \Big(\dfrac{ax}{2-a} +\dfrac{by}{2-b}-\dfrac{(x+y)(ax+by)}{2x+2y-ax-by}\Big) \!=\!\sum\limits_{j=1}^m {\dfrac{2xy(a-b)^2}{(2x+2y-ax-by)(2-a)(2-b)}} \!\ge\! 0. \end{align*} $ |
所以, AE
性质4 给定决策表
证 明 由定义[6]、定义[8]可知
$ \begin{align*} {\rm AE}'(D_B )-E(D_B )=\;& \sum\limits_{j=1}^m {\sum\limits_{i=1}^n {\left| {X_i } \right|} \Big[1-\dfrac{\left| {X_i \cap Y_j } \right|}{2\left| {X_i } \right|} \Big/\Big(1-\dfrac{\left| {X_i \cap Y_j } \right|}{2\left| {X_i } \right|}\Big) \Big]} \\ &-\sum\limits_{j=1}^m {\sum\limits_{i=1}^n \left| {X_i } \right|\cdot \dfrac{\left| {X_i \cap Y_j } \right|}{\left| {X_i } \right|}} \Big(1-\dfrac{\left| {X_i \cap Y_j } \right|}{\left| {X_i } \right|}\Big) \\ =&\sum\limits_{j=1}^m \sum\limits_{i=1}^n {\left| {X_i } \right|} \Big(\Big[1-\dfrac{\left| {X_i \cap Y_j } \right|}{2\left| {X_i } \right|} \Big/\Big(1-\dfrac{\left| {X_i \cap Y_j } \right|}{2\left| {X_i } \right|}\Big) \Big] \\ &-\dfrac{\left| {X_i \cap Y_j } \right|}{\left| {X_i } \right|}\Big(1-\dfrac{\left| {X_i \cap Y_j } \right|}{\left| {X_i } \right|}\Big)\Big). \end{align*} $ |
设
定义9 给定决策表
$ \begin{align} {\rm ABAE}(D\vert B)\!=\!\!\left\{\!\! {\begin{array}{l} \displaystyle\sum\limits_{j=1}^m \sum\limits_{i=1}^n [1\!-\!\beta _B' (Y_j )] \cdot \left| {X_i } \right|\cdot \!\Big[1\!-\!{\dfrac{\left| {X_i \cap Y_j } \right|}{\left| {X_i } \right|}}\!\Big/\! \Big(1\!-\!\dfrac{\left| {X_i \cap Y_j } \right|}{\left| {X_i } \right|}\Big) \Big], \;\;\;0\!\le\! \dfrac{\left| {X_i \cap Y_j } \right|}{\left| {X_i } \right|}\!<\!\dfrac{1}{2}, \\ \displaystyle\sum\limits_{j=1}^m \sum\limits_{i=1}^n [1\!-\!\beta_B' (Y_j )]\cdot \left| {X_i } \right|\cdot \!\Big[1\!-\!\Big(1\!-\!\dfrac{\left| {X_i \cap Y_j } \right|}{\left| {X_i } \right|}\Big) \!\Big/\!\dfrac{\left| {X_i \cap Y_j } \right|}{\left| {X_i } \right|} \Big], \;\;\;\dfrac{1}{2}\!\le\! \dfrac{\left| {X_i \cap Y_j } \right|}{\left| {X_i } \right|}\!\le\! 1. \end{array}} \right. \end{align} $ | (2.6) |
近似边界精度增强信息熵为
$ \begin{equation} {\rm ABAE}'(D\vert B)= \sum\limits_{j=1}^m \sum\limits_{i=1}^n [1-\beta _B' (Y_j )]\cdot \left| {X_i } \right|\cdot \Big[ 1-{\dfrac{\left| {X_i \cap Y_j } \right|}{2\left| {X_i } \right|}} \Big/\Big(1-\dfrac{\left| {X_i \cap Y_j } \right|}{2\left| {X_i } \right|}\Big) \Big], \end{equation} $ | (2.7) |
其中,
在属性约简中, 有基于代数观的算法, 也有基于信息观的算法.代数观的算法能有效度量知识的完备性, 但对知识粒度的大小度量效果不理想; 相反, 信息观的方法能有效度量知识粒度的大小, 对于知识的完备性却束手无策.显然, 只从代数观或信息观某一方面研究属性约简, 均具有片面性.由定义9可知, 近似边界精度增强信息熵有效结合了信息观与代数观的特点, 相对于传统的信息熵模型而言, 既考虑了完备性, 又考虑了知识粒度的大小, 从而能够全面、客观地度量粗糙集中的不确定性问题.
定理3 在给定的决策系统
$ \begin{align*} {\rm ABAE}'(D\vert B)\ge {\rm ABAE}'(D\vert (B\cup a)), {\rm ABAE}(D\vert B)\ge {\rm ABAE}(D\vert (B\cup a)). \end{align*} $ |
证 明 因为近似边界精度增强信息熵的定义是由近似边界精度与增强信息熵组合而成, 所以下面从这两个方面证 明.
(1) 由
(2) 设
$ \begin{align*} \sum\limits_{i=1}^n \sum\limits_{X\in U/(B\cup a)}\Big[ {{1-\dfrac{\left| {X\cap Y_i } \right|}{2\left| X \right|}} {\Big(1-\dfrac{\left| {X\cap Y_i } \right|}{2\left| X \right|}\Big)}} \Big] \\ \le \sum\limits_{i=1}^n \sum\limits_{X\in U/B}\Big[{{1-\dfrac{\left| {X\cap Y_i } \right|}{2\left| X \right|}} {\Big(1-\dfrac{\left| {X\cap Y_i } \right|}{2\left| X \right|}\Big)}} \Big], \end{align*} $ |
即
同理, 由定理1可得,
综合(1)(2)可得,
由定理3可知, 近似边界精度增强信息熵(或相对信息熵)是一个具有非严格单调性规律的函数, 因此可以借助近似边界精度增强信息熵(或相对信息熵)的特点, 来度量属性重要性, 并以此为依据, 计算约简集.
定义10 给定的决策表
定义11 给定的决策表
$ \begin{equation} {\rm Sig}(b, B, D)={\rm ABAE}(D\vert B)-{\rm ABAE}(D\vert B\cup \{b\}), \end{equation} $ | (3.1) |
增强信息熵重要性为
$ \begin{align} {\rm Sig}'(b, B, D)={\rm ABAE}'(D\vert B)-{\rm ABAE}'(D\vert B\cup \{b\}). \end{align} $ | (3.2) |
因为在计算信息熵过程中, 存在大量的计算
char[] intersect(string
{ Char[]
int
while(
{ if (
{
else if (
else
return
由intersect(string
在求相对信息熵的过程中, 存在着大量的求
算法1 近似边界精度增强信息熵及相对信息熵的计算 |
输入: 决策表 输出: 近似边界精度增强信息熵 |
int int type; for ( { int input type; for ( { count = count + temp = intersect ( if (temp = = else if (temp = = 0) else { switch(type) { case 1: //计算增强信息熵 case 2: //计算相对信息熵 if ( else break; } } |
算法2 基于近似边界精度增强信息熵约简及相对信息熵约简 |
输入: 输出: R. |
step1 step2 计算 step3 计算条件属性 step4 while ( 1 ) { 计算Sig 若有多个属性的重要性都达到最大值, 则从中任选一个 if ( 输出增强信息熵的约简 if ( 输出相对信息熵的约简 |
算法主要的时间开销在于求信息熵, 每加入一个属性时, 要重新计算近似边界精度及信息熵.由于巧妙利用
为进一步验证本文近似边界精度增强信息熵、相对信息熵约简算法与其他同类算法的性能, 利用Windows7系统, 开发工具为VS2012, CPU 2.3G, 内存4GB环境下编程.本文选用UCI机器学习数据库中的6个数据集测试: ①Tic-Tac-Toe Endgame(Tic)数据集, 958样例数, 10个属性, 2个模式类; ②Zoo数据集, 101个样例, 17个属性, 7个模式类; ③Ecoli数据集, 336个样例, 8个属性, 8个样式类; ④Lymphography数据集(Lymph), 148个样例, 19个属性, 4个模式类; ⑤Chess King-Rook vs. King-Pawn(Chess)数据集, 3196个样例, 37个属性, 2个模式类; ⑥Mushroom(Mush)数据集, 8124个样例, 23个属性, 2个模式类.
本文与以下具有代表性的几个算法进行比较: ①基于条件熵的算法(Conditional Entropy, CE)[15]; ②相对模糊熵(Fuzzy Entropy, FE)[17]; ③基于近似决策熵的算法(Approximate Decision Entropy Attribute Reduction, ADEAR)[19]; ④组合条件熵(Combine Conditional Entropy, CCE)[20].
实验从约简结果、分类精度、运行时间上比较. 表 1给出了不同算法在上述6个数据集上的约简情况, 其中RN为最小属性约简的基数.通过表 1可知, CE、FE、CCE3种算法计算属性重要性时, 只是围绕信息观下的信息熵研究, 考虑信息的粒度, 影响约简效果.但ADEAR将近似精度融入信息熵、ABAE将近似边界精度融入相对信息熵、ABAE’将近似边界精度融入增强信息熵计算, 有效结合代数观、信息观的方法, 全面、客观地度量属性重要性, 在表 1的6个数据集中, 均有较好的约简效果.
运行时间上, 本文算法ABAE、ABAE’与算法CE、FE、CCE的比较, 如表 2所示.
由表 2可知, 针对相同的数据约简, ABAE算法的运行时间远小于CE、FE, 由于ADEAR与ABAE方法在计算
为进一步验证基于信息熵算法、基于正区域算法[21](简称FBS)及本文算法的分类准确性, 将各算法得到的约简结果作为SVM分类器的输入.为提高SVM分类器对样本的分类精度, 以20%数据作测试集, 80%为训练集, 核函数采用"径向基核", 调整拉格朗日乘子上界及径向基核参数, 利用十折交叉验证的方法来评估所有的约简分类精度, 如图 1所示.
通过图 1的分类效果可知, ABAE’在数据集Tic、Zoo、Ecoli、Mush上均能获得较高分类精度的约简结果; 基于单一信息熵的约简算法CE, 约简结果的分类准确率不高, 由于只单纯考虑信息熵的方法计算属性重要性; FBS算法的约简分类准确率, 性能较稳定, 但多数情况下较ABAE’的分类精度低, 由于在度量属性重要性时, 只考虑决策表中正域样本的区分效果, 未考虑负区域样本间的区分能力.特别是在利用正区域方法计算属性重要性时, 常会出现多个条件属性的属性重要性值相同的情况, 传统的算法是随机选择一个.由于每次计算属性重要性都是计算相对重要性, 所以随机选择的属性会影响下一次属性的选择.若采用本文的两种放大信息熵的方法, 并结合代数观下的近似边界精度计算属性重要性, 可以有效度量样本间的细微差异, 从而使得在后续的数据分类工作中, 展现出本文算法在分类效果上的优势.
为了研究离群点对算法的约简影响, 利用欧式距离计算各样本对象间的空间距离, 再利用拉依达准则计算离群点个数.上述6个数据集计算得到的离群点个数: Tic为0; Zoo为2; Ecoli为4; Lymph为5; Chess为188; Mush为156.设离群点数占样本总数的比例为离群率, 则各数据集的离群率: Tic为0‰; Zoo为19.8‰; Ecoli为11.9‰; Lymph为33.8‰; Chess为58.8‰; Mush为19.2‰.上述6个数据集中, ABAE’在数据集Chess及Lymph上分类精度低于FBS算法, 因为数据集Chess、Lymph有较高的离群率, 由于离群率的存在影响了ABAE’的分类性能.相比之下, FBS算法受离群点率的影响较小, 因此其分类精度高于ABAE’.针对离群率问题, 要提高ABAE’分类性能, 必须考虑在属性约简之前, 尽量采用离群点检测方法, 找出离群点, 以减少离群点对属性约简的影响.
5 结论属性约简是粗糙集理论研究的热点之一, 广大研究者们多数只从代数观或者只从信息观设计相关属性约简算法.本文融合代数观和信息观的特点, 设计一种计算属性重要性的方法, 使分类精度更高.另外, 由于在计算
下一步工作, 考虑如何在保持高精度分类的情况下, 减少算法的计算量, 更进一步提高算法的时间性能, 以及考虑如何将计算与现代的多核处理器结合, 降低算法的时间复杂度.
[1] | PAWLAK Z, SKOWRON A. Rough sets:Some extensions[J]. Information Sciences, 2007, 117(1): 28-40. |
[2] | PAWLAK Z. Rough sets[J]. Int J of Computer and Information Sciences, 1982, 11(5): 341-356. DOI:10.1007/BF01001956 |
[3] | 王熙照, 王婷婷, 翟俊海. 基于样例选取的属性约简算法[J]. 计算机研究与发展, 2012, 49(11): 2305-2310. |
[4] | KIM K, CHU Y Y, WATADA J Z, et al. A DNA-based algorithm for minimizing decision rules:A rough sets approach[J]. IEEE Trans Nanobiosci, 2011, 10(3): 139-151. DOI:10.1109/TNB.2011.2168535 |
[5] | HUANG C C, TSENG T L, JIANG F H, et al. Rough set theory:A novel approach for extraction of robust decision rules based on incremental attributes[J]. Annals of Operations Research, 2014, 216(1): 163-189. DOI:10.1007/s10479-013-1352-1 |
[6] | 荆涛, 王家林, 石旭东, 等. 基于粗糙集约简的飞机发电机故障诊断决策研究[J]. 计算机应用研究, 2017, 34(4): 1101-1104. |
[7] | 朱庆, 苗双喜, 丁雨淋, 等. 知识引导的滑坡监测数据粗差定位与剔除方法[J]. 武汉大学学报(信息科学版), 2017, 42(4): 496-502. |
[8] | 梁宝华, 汪世义. 行式存储的快速属性约简算法[J]. 模式识别与人工智能, 2015, 8(9): 795-801. |
[9] | 赵洁, 梁俊杰, 董振宁, 等. 位运算和核属性快速识别下的粗糙集属性约简算法研究[J]. 小型微型计算机系统, 2015, 36(2): 316-321. |
[10] | 史博文, 李国和, 吴卫江, 等. 基于强化正域的属性约简方法[J]. 计算机应用研究, 2017, 34(1): 107-109. |
[11] | 周建华, 徐章艳, 章晨光. 改进的差别矩阵的快速属性约简算法[J]. 小型微型计算机系统, 2014, 35(4): 831-834. |
[12] | 蒋瑜. 基于差别信息树的rough set属性约简算法[J]. 控制与决策, 2015, 30(8): 1531-1536. |
[13] | 龙浩, 徐超. 基于改进差别矩阵的属性约简增量式更新算法[J]. 计算机科学, 2015, 42(6): 251-255. DOI:10.11896/j.issn.1002-137X.2015.06.053 |
[14] | SHANNON C E. The mathematical theory of communication[J]. Bell System Technical J, 1948, 27(3/4): 373-423. |
[15] | 王国胤, 于洪, 杨大春. 基于条件信息熵的决策表约简[J]. 计算机学报, 2002, 25(7): 759-776. |
[16] | 杨明. 决策表中基于条件信息熵的近似约简[J]. 电子学报, 2007, 35(11): 2156-2160. DOI:10.3321/j.issn:0372-2112.2007.11.023 |
[17] | 张清华, 肖雨. 新的信息熵属性约简[J]. 计算机科学与探索, 2013, 7(4): 359-367. |
[18] | 潘瑞林, 李园沁, 张洪亮, 等. 基于α信息熵的模糊粗糙集属性约简方法[J]. 控制与决策, 2017, 32(2): 340-348. |
[19] | 江峰, 王莎莎, 杜军威, 等. 基于近似决策熵的属性约简[J]. 控制与决策, 2015, 30(1): 65-70. |
[20] | QIAN Y H, LIANG J Y, PEDRYCZ W, et al. Positive approximation:An accelerator for attribute reduction in rough set theory[J]. Artificial Intelligence, 2010, 174(9): 597-618. |
[21] | 蒋瑜, 刘胤田, 李超. 基于Bucket Sort的快速属性约简算法[J]. 控制与决策, 2011, 26(2): 207-212. |