基于相关族方法的特征选择算法

谢棚宇， 杨 田， 代建华

(1. 中南林业科技大学 物流与交通学院 湖南 长沙 410004； 2. 湖南师范大学 智能计算与语言信息处理湖南省重点实验室 湖南 长沙 410081； 3.国防科技大学 系统工程学院 湖南 长沙 410073)

0 引言

突发事件是指在短时间内突然发生、对社会和人民群众的生命财产安全产生严重影响的事件。一般而言，突发事件数据的属性集中存在大量冗余信息，可能会掩盖突发事件信息系统中各要素的关系，影响应急决策的质量和效率。因此，需要对突发事件信息系统进行有效的属性约简，以达到删除冗余或不必要属性、减少突发事件响应时间和提高决策准确性的目的。文献[1-3]利用粗糙集理论[4]对各类突发事件进行了属性约简，提高了分类的质量。粗糙集的主要思想是在保持分类能力不变的情况下，通过知识约简导出问题的决策或分类规则。利用粗糙集理论的属性约简一般采用区分矩阵[5]、邻域粗糙集[6]、信息熵[7]等工具，但利用这些方法提出的约简理论不能适用于所有的覆盖粗糙集模型的属性约简。针对这一难题，文献[8]基于逼近空间提出相关族方法，解决了M逼近空间覆盖粗糙集模型的属性约简问题。此外，突发事件积累了大量的数据，而基于相关族方法设计的属性约简算法能快速地得到约简结果，运行时间短。因此，本文以粗糙集理论和相关族方法为基础，针对突发事件的属性约简问题提出相应的约简理论和算法，将决策表中一致和非一致两种情况整合为统一框架，进而利用相关族理论对决策表进行属性约简，在此基础上设计了启发式约简算法，并对恐怖袭击事件数据集进行了实例分析。

1 相关概念

1.1 粗糙集

为避免在处理数值型数据过程中发生数据内部结构改变、数据挖掘性能下降和离散化产生误差等问题，文献[9]提出了覆盖粗糙集模型。设U为一个非空有限论域，C为U的一个非空子集族，若∪C=U，则称C为U上的一个覆盖，序对(U,C)称为覆盖逼近空间。

定义1(极小描述、邻域、逼近空间)[10]令C为U上的一个覆盖，MdC(x)={K∈C|x∈K∧(∀S∈C∧x∈S∧S⊆K)⟹K=S}称为x的极小描述，MC=∪{MdC(x)|x∈C }称为覆盖C的M逼近空间。NC(x)=∩{C∈C|x∈C}称为x的邻域，NC={NC(x)|x∈C}称为覆盖C的N逼近空间。当不引起混淆时，可以省略下标C。

定义2(第一型逼近算子)[10]令C为U上的一个覆盖，对任意的X⊆U,集合CLC(X)=∪{K∈C|K⊆X}和FHC(X)=CLC(X)∪(∪{Md(x)|x∈X-CLC(X)})分别称为X的下近似和上近似。当不引起混淆时，可以省略下标C。

具有条件属性和决策属性的知识表达系统称为决策表。若条件属性中对象的关系表现为覆盖C，则决策表为覆盖决策表，记为S=(U,Δ,D)，其中Δ={C1, C2,…,Cn}为论域U上的一个覆盖族。

1.2 覆盖粗糙集的属性约简

属性约简的目标就是寻找保持信息系统分类能力不变的属性极小子集，但此时的逼近方式或空间却没有发生改变。本文的属性约简基于覆盖决策表，即研究条件属性所产生的分类相对于决策属性所产生的分类之间的关系，产生的属性约简记为相对属性约简。相对属性约简有两个重要概念：相对约简和相对核(简称为约简和核)。

定义4(约简、核) 设S=(U,Δ,D)是一个覆盖决策表，其中Δ={C1,C2,…,Cn}是论域U上的一个覆盖族。对任意的Ci∈Δ，若POSΔ(D)⊆POSΔ-{Ci}(D)，则Ci在Δ中关于D不必要；否则，Ci在Δ中关于D必要。对于每一个P⊆Δ，若POSΔ(D)⊆POSP(D)，并且P的任意一个覆盖都是必要的，称P是Δ相对于D的一个属性约简。Δ中所有必要关系组成的集合称为Δ的相对核，记为CORE(Δ)。Δ中所有约简的集合记为RED(Δ)。

1.3 相关族

在粗糙集属性约简理论中，区分矩阵是最经典的工具之一，其被广泛地应用到N逼近空间类型的覆盖粗糙集属性约简中。在对M逼近空间类型的覆盖粗糙集进行属性约简时，区分矩阵这一工具不再适用，而相关族方法能对逼近空间为MC的覆盖粗糙集模型进行属性约简。因此，本文基于第一型覆盖粗糙集模型和相关族方法对突发事件数据进行属性约简。下面基于覆盖决策表给出相关族的定义，覆盖决策表分为一致和非一致两种情况，为节省时间，在属性约简之前不再区分数据是否一致，并将一致和不一致覆盖决策表整合为统一框架，在此框架上讨论相关族理论。

定义5令(U,Δ,D)为一个覆盖决策表，其中U={x1,x2,…,xn}，S (U,Δ,D)={Ck∈∪Δ|∃Xi∈U/Ds.t. Ck⊆Xi}称为(U,Δ,D)的有效逼近集合，有效逼近集合中的对象称为有效信息粒。

定义6令(U,Δ,D)为一个覆盖决策表，S (U,Δ,D)为有效逼近集合，则对任意的xi∈∪S(U,Δ,D)，有

1)r(xi)={C∈Δ|∃Ck∈S (U,Δ,D) s.t.xi∈Ck∈C}称为xi的相关集合；

2)R(U,Δ,D)={r(xi)|xi∈Δ}称为决策表(U,Δ,D)的相关族。

定理1令(U,Δ,D)为覆盖决策表，P∈Δ，则

1) 对任意的xi∈S (U,Δ,D)，当且仅当P∩r(xi)≠∅，有POS∪Δ(D)=POS∪P(D)；

2) 对于某些xi∈U，有CORE(Δ)={C∈Δ|r(xi)={C }}。

证明1) 假设POS∪Δ(D)=POS∪P(D)，对任意的xi∈∪S (U,Δ,D)，有∃K∈S (U,P,D)={K|K∈∪P且∃X∈U/D}，其中xi∈K。即有C∈P使得xi∈K∈C。因为P∈Δ，很明显C∈r(xi)，所以(C∈r(xi))∩P≠∅。假设对任意的xi∈∪S (U,Δ,D)，有P∩r(xi)≠∅，则存在C∈P使得C∈r(xi)，故∪S (U,Δ,D)=∪S (U,P,D)，所以POS∪Δ(D)=POS∪P(D)。

2) 假设C∈CORE(Δ)，则说明C在Δ是必要的，即POS∪Δ(D)≠POS∪(Δ-C )(D)，存在xi∈U使得xi∉∪{K|K∈∪(Δ-{C })且∃X∈U/Ds.t.K⊆X}。因此，r(xi)={C }。如果对那些xi∈U有r(xi)={C }，很明显有C∈CORE(Δ)。

以上定义阐述了相关族方法的基本思想，在求覆盖决策表的属性约简时，相关族引入了布尔函数。

定理2令(U,Δ,D)为覆盖决策表，f(U,Δ,D)为其相关方程。若g(U,Δ,D)为f(U,Δ,D)通过乘法律和吸收率得到的极小析取范式，即g(U,Δ,D)=(∧P1)∨…∨(∧Pm)，Pk⊆P,k=1,2,…,m且Pk中的任意元素至多出现一次，则RED(Δ)={P1,P2,…,Pm}。

2 基于相关族的快速属性约简算法

2.1 数据预处理

本文进行属性约简的基础是覆盖决策表，若数据集的数据类型表现为混合数据或连续型数据，需对其进行预处理使之形成覆盖。对于连续型属性下的对象xi(i=1,2,…,m)，首先对其进行归一化处理，使属性值取值区间为[0,1],K(xi)={xj|d(xi,xj)≤δ}称为关于对象xi形成的信息粒，其中：d(xi,xj)=|a(xi)-a(xj)|；δ是区间为[0,1]的可调节参数。若属性为符号型，则K(xi)={xj|a(xi)=a(xj)}。单个属性下所有K(xi)的集合形成了关于该属性的覆盖。

2.2 基于相关族的快速属性约简算法

本文提出的基于相关族的快速属性约简算法分为两步。首先求得覆盖决策表的相关族(Step 1)，再在相关族的基础上求得决策表的属性约简结果(Step 2)。at∈A(t=1,2,…,n)表示属性，xi∈U(i=1,2,…,m)表示对象，[xi]at表示对象xi在属性at中根据δ形成的信息粒，[xi]D表示对象xi所在的决策类，|r(xi)|表示该集合的势，‖at‖表示属性at在R(U,Δ,D)中出现的频次，算法的具体步骤如下。

Step1在覆盖决策表上生成相关族。

输入：决策表S(U,A,D)，参数δ；

输出：相关族R(U,Δ,D)；

① 令R(U,Δ,D)=∅,r(xi)=∅

② forat∈A,Pt=∅

③ forxi∈U,r(xj)=∅

④if 存在xj∈U-[xi]D使得|at(xi)-at(xj)|≤δ

则[xi]at和[xj]at为无效粒子

⑤ else [xi]at为有效粒子

计算[xi]at，Pt=Pt∪[xi]at

⑥ end if

⑦ end for

⑧ ifxj∈Pt

⑨r(xj)=r(xj)∪{at}

Step2基于相关族得到属性约简。

输入：相关族R(U,Δ,D)；

输出：约简RED；

① 令CORE=∅,RED=∅

② forr(xi)∈R(U,Δ,D)

③ if |r(xi)|=1

④CORE=CORE∪r(xi);从R(U,Δ,D)中删去r(xi)

⑤ end if

⑥ end for

⑦RED=CORE

⑧ whileR(U,Δ,D)≠∅

⑨ if ‖at‖=max{‖a‖|a∈A}

⑩RED=RED∪{at}

⑩ end if

记对象个数为m，属性个数为n。在本文提出的属性约简算法中，Step 1计算相关族的时间复杂度为O(m2n/2)，Step 2计算属性约简的时间复杂度为O(min{m,n})，因此本算法的时间复杂度为O(m2n/2+min{m,n})。其中在计算相关族时，考虑到2个对象之间的距离关系是对称的，当xi与xj不在同一决策类，而|d(xi,xj)|≤δ，此时由xi生成的信息粒视为无效信息粒，根据对称性，xj所在的信息粒也视为无效信息粒，因此Step 1的时间复杂度为O(m2n/2)。当判断信息粒为无效粒子时，运算中断，此过程不会生成完整的信息粒。因此，实际计算量会远小于复杂度中的计算量。

3 实验分析

所有实验均在同一设备、同一环境下进行。其中设备运行系统为macOS10.14.4，处理器为2.7 GHz Intel Core I7，内存为8 GB，实验所用软件为Matlab R2018a。利用5个公开数据集来检验本文算法的有效性，突发事件实例分析数据为环球恐怖主义数据集GTD。

3.1 算法有效性检验

为验证本文算法的有效性，利用5个公开数据集与文献[6]中基于邻域粗糙集的NRS算法、文献[7]中基于信息熵的HANDI算法、文献[11]中基于区分矩阵的CDG算法进行属性约简对比实验，对比项包括数据集的分类精度及约简时间。判断数据集分类精度的工具为支持向量机(SVM)和决策树ID3，对比结果如表1、表2所示。在实验过程中，除CDG算法在对数据集texture进行属性约简时，由于超出设备内存而不能得到约简结果外，其他算法对5个数据集均能计算出约简结果。经本文算法约简后的数据集分类精度与初始精度相比，约简结果均能保持或提升分类精度；与其他几种算法约简得到的分类精度进行对比，也仅存在细微差别，约简结果基本保持一致，证明了本文算法的有效性。在约简时间对比上，本文算法具有明显的时间优势，特别是对对象个数较多的大型数据集，时间差距更为明显。因此，若将本文算法应用于突发事件数据的属性约简，能极大地缩短得到关键因素的时间，协助救援机构快速判断突发事件的危害等级，以开展对应等级的救援活动。

表1 不同算法的分类精度对比Table 1 Comparisons of classification accuracy of different algorithms 单位：%

表2 不同算法的约简时间对比Table 2 Comparisons of reduction time of different algorithms 单位：s

图1 分类精度及属性个数在参数δ下的变化趋势Figure 1 Variation of classification accuracies and number of attributes with δ

3.2 恐怖袭击事件实例分析

恐怖袭击事件数据记录了大量的情景与袭击后果信息，若能删除恐怖袭击事件中的冗余知识，则可以明确属性因素与袭击后果的关系，有利于决策者根据少量关键情景因素做出判断，实施相应救援调度。环球恐怖主义数据集GTD获取了1998—2017年近20年的恐怖袭击的详尽内容，包含了大量的文本属性和相似描述属性，且很多对象属性值为缺失值，不利于后续进行约简实验。因此，对数据集GTD进行了处理，并得到了关于环球恐怖主义事件危害程度的决策表，该决策表有对象35 415个，属性26个，其中条件属性25个。用本文算法对决策表进行属性约简，总约简时间约为2 160.704 s，分类精度及属性个数在参数δ下的变化趋势如图1所示。可以看出，当邻域变量δ在区间[0,1.0]变化时，约简后的分类精度在区间[86.2%,87.9%]变动。当δ=0.9时，SVM分类器下分类精度的最优值为87.84%；当δ=0.85时，ID3分类器下分类精度的最优值为87.83%。两种分类器最优精度对应的约简结果相同，约简后均剩余3个属性，分别为受伤总人数、人质总数、赎金支付总数。数据集GTD基于SVM和ID3分类器的原始分类精度分别为85.76%和85.57%。对比发现，约简后的分类精度提升了2%左右，而原决策表的条件属性个数由25个降至3个。

同样地，本文也利用3.1小节的对比算法对恐怖袭击事件数据进行属性约简，数据集GTD的约简结果对比如表3所示。CDG和HANDI算法由于所要求的计算空间超出设备内存而无法计算，NRS算法只有在参数δ=0时得到约简结果，其单次约简时间约为1 853.54 s，为本文算法单次约简时间(102.89 s)的18.01倍。NRS算法的分类精度均低于本文算法约简后的分类精度。因此，根据算法的有效性检验和恐怖袭击事件实例分析可知，本文算法对数据集进行属性约简后，不仅能继续保持甚至提高分类精度，且相较于其他高效的属性约简算法具有明显的时间优势。当突发事件发生时，本文算法能帮助决策者或救援机构快速地找到关键影响因素，减少数据收集的难度，使得决策者能根据有限的属性判断突发事件的危害等级，做出合理的救援决策。

表3 数据集GTD的约简结果对比Table 3 Comparisons of reduction results of GTD dataset

4 小结

本文在相关族理论的基础上提出了基于第一型覆盖粗糙集的属性约简理论，设计了启发式属性约简算法，并与现有的几种有效算法进行了比较。结果表明，本文算法能快速地进行属性约简，缩短知识发现的时间，节省存储空间。对数据规模较大的恐怖袭击事件数据集进行了实例分析，结果表明，该算法能快速地删除数据库中大量的冗余属性，提高了约简后数据分类的精度，提取出恐怖袭击事件数据的关键属性，降低了突发事件发生时数据收集的难度。此外，在该数据集存在属性值缺失、信息不完备的情况下，本文算法依旧可以得到满意的结果，说明此方法能解决此类不完备信息系统的属性约简问题，其实际应用性更加广泛。