基于规则提取的决策粗糙集阈值自适应算法*

范兵兵，李 进，陈玉金

（空军工程大学防空反导学院，西安 710051）

0 引言

决策粗糙集［1］是Yao等人提出的，在经典Pawlak粗糙集［2-3］的基础上引入了贝叶斯风险分析，通过单个代价矩阵来求得构建概率粗糙近似所需的一对阈值［4］。然而，单个代价矩阵的确定需要合理的先验知识，不合理的先验知识将直接导致模型无法获得具有普遍决策意义的近似集和决策规则。为了消除或者抑制这种由不合理先验知识带来的模型噪声，许多学者给出了自己的解决方法。文献［5-7］通过构建多重代价决策粗糙集模型来解决单一矩阵决策的不足；文献［8-11］通过构建包含模糊概念的代价函数，建立基于模糊概念的决策粗糙集模型，进而抑制不合理的先验知识带来的分类不精确性；文献［12］通过引入博弈论寻求最优策略确定阈值；文献［13］从最小代价角度考虑自适应确定阈值。以上的研究从不同侧面推动了决策粗糙集模型的发展。

回顾决策粗糙集模型和相关的约简算法，决策规则的简洁程度和可信度是模型分类效果好坏的直接体现。因此，在考虑如何抑制由不合理先验知识带来的模型噪声时，需要兼顾考虑模型分类效果好坏：1）在属性约简及后续决策中，可信度高的规则更具有指导性作用。2）获取的决策规则越简洁，即属性的个数越少，信息系统决策速率越快。

1 基本知识

1.1 经典决策粗糙集模型

在此基础上，定义决策粗糙集的下、上近似分别为：

1.2 决策规则的获取

2 基于决策规则的求阈值方法

在决策粗糙集及属性约简中，如何通过合理的先验知识给出合理的风险代价矩阵是一个需要解决的关键问题。基于此，本节介绍一种自适应求代价矩阵的算法，以减少新引入参数对模型的影响。

回顾决策粗糙集模型和相关的约简算法，决策规则的简洁程度和可信度是模型分类效果好坏的直接体现。因此，在考虑自适应求代价矩阵的算法中必须考虑以下两点：

1）在属性约简及后续决策中，可信度高的规则更具有指导性作用。

2）获取的决策规则越简洁，即属性的个数越少，信息系统决策速率越快。

下面我们将基于决策规则的自适应求代价矩阵方法转化为单目标优化问题进行解决。令为一信息系统，其中，那么，求代价矩阵的问题可以转化为

同时，为了保留一个明确的边界域，假设α≥β。综合以上条件，对约束条件进行简化

3 基于引力搜索算法的自适应求阈值算法

3.1 引力搜索算法的基本描述

假设存在一个包含N个个体的系统。其中，第i个个体的位置定义为n维空间。那么，t时刻第 d维上，个体 Xj，Xi之间的作用力分量定义为

其中，Maj（t）和Mpi（t）分别为个体Xj和粒子Xi的主动引力质量和被动引力质量。ε是一个很小的常量，防止分母为零；Rij（t）是粒子Xj和粒子Xi的欧式距离；G（t）是在 t时刻的引力常数

其中，G0、α为常数，T是最大迭代次数。文献［15］建议取值为 G0=100，α=20。

这里假设引力质量和惯性质量相等，即Mai=Mpi=Mii=Mi，i=1，2，…，n。那么，式（3）中的相关质量值可以计算如下

其中，fiti（t）表示t时刻个体Xi的适应度；best（t），worst（t）表示t时刻所有个体最好和最差的适应度值。

Rij（t）通过矩阵范数表示

那么，个体Xi在t时刻第d维上受到的合力为：

其中，randj是［0，1］的随机数，kbest表示当前质量排名前k位的个体。

根据牛顿第二定律，个体Xi在t时刻第d维的加速度aid（t）为

最后，个体的速度和位置更新如下

其中，randi是［0，1］的随机数。分别表示个体Xi在t时刻第d维上的速度分量和位移分量。

3.2 自适应求阈值的算法描述

3.2.1 个体位置的表示

第i个个体Xi的位置由一组四维的正实数向量，其中，表示当一个对象x属于集合X时，采取aB，aN决策时所需的代价表示当一个对象x不属于集合X时，采取aP，aB决策时所需的代价。同时根据最优化问题描述可得，满足如下关系

3.2.2 适应度函数

代价矩阵的适应度函数需要满足两个条件：一是要保证通过代价矩阵得出的阈值可以给出简洁且有效的决策规则；二是要保证所有个体都能够受到力的作用（惯性质量大于等于0），进而发生位移，以产生新的个体供全局搜索。因此，适应度函数定义为

由于约简问题中需要求解目标函数的最大值，因此定义

3.2.3 位置修正

由适应度函数可得，引力搜索算法中对于加速度和位移分量的计算结果可能导致个体位置不满足式（14）的约束，故需要对数据结果进行修正。

阈值α，β的取值事实上可以为一系列离散值代替以往区间内的连续值，而使等价类进行正域、负域、边界域划分效果不变。例：已知，等价类为，当阈值或者时，均可达到使等价类划分到正域的效果，同理，对于等价类，当阈值或者时，均可达到使等价类划分到负域的效果。因此，可以推断，对于任一等价类，假设其含有n个元素，则当时，可以达到相同的划分效果。将α，β的取值离散化后，相对于区间内的连续值更加适合智能算法的搜索，使搜索时间减少也避免发生组合爆炸。

本算法引入上述位置修正以及阈值α，β的离散化限定，保证个体位置满足问题约束，具体如算法1所示。

算法1：代价矩阵位置修正

综合以上分析，下面给出基于引力搜索算法的自适应求代价矩阵算法，如下页算法2所示。

4 仿真实验

为了检验上述基于引力搜索的自适应求阈值算法的应用过程和效果，将引力搜索求三支决策最优阈值算法分别和自适应算法Alcofa、模拟退火算法求解三支决策阈值从运行时间随着属性个数以及样本数增加，对其运行时间影响两方面进行比较。此外，为了检验利用基于引力搜索的自适应算法学习到的阈值的有效性，利用3种算法学习到的阈值构建了分类器，并计算其准确率Precision（P）、召回率Recall（R）和F1值，计算方法［14］如下：Preciosn=系统检索到的相关文件数/相关文件总数Recall=系统检索到的相关文件数/系统返回的文件总数

算法2：基于引力搜索算法的自适应求代价矩阵算法

Step1：系统初始化

1）给定系统中个体规模N，最大迭代次数T，初始化每个个体的位置

2）根据式（14）、相应的属性约简算法和决策规则提取方法计算每个个体的适应度值fiti（t），记录最优适应度值及对应的个体位置信息作为历史最优信息

Step2：系统位置更新

1）根据式（8）计算每个个体的惯性质量Mi（t）

2）根据式（10）计算每个个体当前时刻受其他个体影响的合力Fid（t）

3）根据式（11）计算每个个体当前时刻的加速度aid（t）

4）根据式（12）更新每个个体的速度和位置

5）根据算法1对新系统中的个体位置进行修正

6）根据式（14）更新每个个体的适应度值fiti（t）

7）记录当前时刻最优适应度值及对应的个体位置信息。若当前时刻最优适应度值优于历史最优适应度值，则更新历史最优信息

Step3：如果连续M代最优适应度值没有发生变化或者迭代次数达到最大迭代次数T，转到Step4，否则转到Step2

F1=2Precision x Recall/（ Precision+Recall）

实验环境如下：CPU是Intel的I7-4790，主频3.60 GHz，8G 的内存，64位的 Windows7系统，Matlab R2012a上实现。

表1 数据集描述

实验的数据集为UCI数据库中的10个数据集，首先，需要对数据集进行预处理，将数据集中的missing值直接删除。又因为模拟退火算法是一种随机算法，每次运行状态和结果可能不一样，因此，对每个数据集都运行50次取平均值作为算法的运行结果。

从表2中的运行时间结果来看，由于对引力搜索空间进行了离散化的搜索限定，使得引力搜索自适应算法明显快于自适应算法和模拟退火算法，并且随着数据集样本以及属性的增加，运行时间无明显增加。而自适应算法Alcofa的运行时间随着样本个数以及属性个数的增加明显提高。

表2 3种算法的运行时间结果

为了研究随着属性个数以及样本数增加对其运行时间影响，分别限定数据集样本个数固定为432、属性个数9到34不等，以及数据集样本个数为192～45 212不等、属性个数固定为11，对这两种情况进行实验，并统计运行时间，如下页表3所示。

从表3所求的标准差来看，无论是随着属性个数增加还是随着样本个数增加，引力搜索自适应算法较Alcofa算法以及模拟退火算法均具有更好的稳定性。

表3 两种情况的运行时间结果

表4 3种算法所求阈值构建的分类器的性能比较

从表4的结果来看，对比10组数据库的分类效果，在07、08号数据库中引力搜索自适应算法略高于Alcofa自适应算法构建的分类器的分类能力，在04号数据库，显示两者分类能力相同，其余7个数据库显示，Alcofa自适应算法构建的分类器的分类能力略高于引力搜索自适应算法所构建的分类器。对比上述十组数据显示，模拟退火算法所构建的分类器的分类能力强于Alcofa自适应算法和引力搜索自适应算法。

出现引力搜索自适应算法的分类能力下降主要原因是，为了加快运行时间，对引力搜索空间进行了离散化的搜索限定，因此，在精度上有所下降，下面分别就引力搜索自适应算法对Alcofa自适应算法以及模拟退火算法的准确率（P）的平均误差率μ1、μ2进行计算，来说明这种误差是可接受的，以此说明该算法所得出的阈值有效。

由于平均误差率μ1、μ2的值均小于千分之五，属于可接受范围之内，说明该算法所得出的阈值有效。

5 结论

为了消除或者抑制由不合理先验知识带来的模型噪声，本文提出了一种基于规则提取的阈值自适应方法。本文以约简结果中属性的数量最小和相应决策规则的可信度最大为目标，结合引力搜索算法，并利用决策粗糙集中的阈值α，β为一特定离散取值时，不会改变等价类的划分这一性质，对搜索空间离散化处理，然后给出基于智能算法的自适应求阈值算法。通过实例证明，本文提出的决策粗糙集阈值自适应方法是可行的。下一步需要努力在本文工作的基础上考虑特定语义下的根据权重，构建新的目标函数将这一方法运用到更多方面。

参考文献：

［1］YAO Y Y，WONG S K M，LINGRAS P.A decision-theoretic rough set model［C］//Raszw，Zemankovam，Proceedings of the 5th International Symposium on Methodologies for Intelligent Systems.North-Holland，1990：17-25.

［2］PAWLAK Z.Rough sets ［J］.International Journal of Computer and Information Sciences，1982，11（5）：341-356.

［3］PAWLAK Z.Rudiments of rough sets ［J］.Information Science，2007，177（1）：3-27.

［4］于洪，王国胤，姚一豫.决策粗糙集理论研究现状与展望［J］.计算机学报，2015，38（8）：1628-1639.

［5］陈玉金，李续武，贾英杰，等.可变多重代价决策粗糙集模型［J］.计算机科学，2017，44（6）：245-249.

［6］MA X B，YANG X B，QI Y，et al.Multicost decision-theoretic rough sets based on maximal consistent blocks［C］//Miao Duoqian，Witold pedrycz.Rough sets and knowledge technology：9th International Conference.Shanghai：Springer，2014：824-833.

［7］DOU H L，YANG X B，SONG X N，et al.Decision-theoretic rough set：a multicost strategy ［J］.Knowledge-Based Systems，2016，91：71-83.

［8］LIANG D C，LIU D，WITOLD PEDRYCZ，et al.Triangular fuzzy decision-theoretic rough sets［J］.International Journal of Approximate Reasoning，2013，54：1087-1106.

［9］LIANG D C，LIU D.Systematic studies on three-way decisions with interval-valued decision-theoretic rough sets［J］.Information Sciences，2014，276：186-203.

［10］LIANG D C，LIU D.Deriving three-way decisions from intuitionistic fuzzy decision-theoretic rough sets［J］.Information Science，2015，300：28-48.

［11］LIANG D C，XU Z S，LIU D.Three-way decisions with intuitionistic fuzzy decision-theoretic rough sets based on pointoperators ［J］.Information Science，2017，375：183-201.

［12］HERBERT J P，YAO J T.Game-theoretical rough sets［J］.Fudanmenta Informaticae，2011，108（3）：267-286.

［13］JIA X Y，TANG Z M，LIAO W H，et al.On an optimization representation of decision-theoretic rough set model［J］.International Journal of Approximate Reasoning，2014，55：155-166.

［14］胡盼，秦亮曦，姚洪曼.用人工鱼群算法自动确定三支决策阂值［J］.计算机与现代化，2016，32（6）：97-101.

［15］JIA X Y，ZHENG K，LI W W，et al.Three-way decisions solution to filter spam email：An empirical study［C］//Proceedings of the 8th International Conference on Rough Sets and Current Trends in Computing.Chengdu，China，2012：287-296.

［16］RASHEDI E，NEZAMABADI-POUR H，SARYAZDI S.GSA：A gravitational search algorithm［J］.Information Sciences，2009，179（13）：2232-2248.

［17］YAO Y Y，ZHAO Y.Attribute reduction in decision-theoretic rough set models［J］.Information Sciences，2008，178（17）：3356-3373.