广义多粒度粗糙集特征选择算法研究

Researches on Feature Selection Algorithm for Generalized Multi-Granularity Rough Sets

摘要: 随着信息技术的迅猛发展，产生了大量的数据，这些数据体量巨大、形式多样、产生迅速、价值密度低、商业价值高。如何使这些数据对人类社会的进步产生积极影响是一个难题。粗糙集理论可以直接对数据进行降维处理，发现数据中的隐含知识，促进社会进步。经典粗糙集理论基于单个二元关系，缺乏灵活性和普遍性，基于多个二元关系的粗糙集理论可以解决上述难题，因此，本文主要针对广义多粒度粗糙集进行了研究，引入元启发式算法，提出通过元启发式算法(蚁群算法)实现广义多粒度粗糙集特征选择算法。通过实验结果看出本文所提算法可以对数据集起到降维效果且得到的特征子集的分类精度和原数据集基本保持一致。

Abstract: With the rapid development of information technology, a large amount of data has been generated, which is huge in volume, diverse in form, rapid in generation, low in value density, and high in commercial value. How to make these data have a positive impact on the progress of human society is a challenge. Rough set theory can directly reduce the dimensionality of the data, discover the implicit knowledge in the data, and promote the social progress. The classical rough set theory is based on a single binary relationship, which lacks flexibility and universality. The rough set theory based on multiple binary relationships can solve the above problems. Therefore, this paper mainly focuses on the generalized multi-granularity rough set and introduces the meta-heuristic algorithm, and proposes to implement the generalized multi-granularity rough set feature selection algorithm by the meta-heuristic algorithm (ant colony algorithm). The experimental results show that the proposed algorithm can reduce the dimensionality of the data set and the classification accuracy of the obtained feature subsets is basically consistent with the original data set.

1. 引言

粗糙集理论 [1] 是一个用于处理不确定的数学工具，经典粗糙集理论建立在单个二元关系上，不能用于处理具有多个二元关系的决策系统。Qian等 [2] 提出了基于多个二元关系的决策系统，称为多粒度粗糙集理论。多粒度粗糙集模型分为乐观多粒度粗糙集模型和悲观多粒度粗糙集模型，由于乐观多粒度粗糙集模型的构造过于放松，悲观多粒度粗糙集模型的构造过于严苛，因此，Xu等 [3] 提出了广义多粒度粗糙集模型。一些学者针对广义多粒度粗糙集理论进行了深入研究。Qian等 [4] 构造了一个广义层次决策表，并将多粒度和序贯三支决策相结合，提出了广义层次多粒度序贯三支决策模型。Xu等 [5] 通过考虑类与概念之间的相对和绝对定量信息，提出了两种广义多粒双定量决策理论粗糙集模型。Xu等 [6] 针对局部广义多粒度邻域粗糙集模型，提出了动态更新近似的方法。张先韬等 [7] 给出了广义多粒度粗糙集约简的一些基本性质，给出matlab计算的过程及计算实例。

在已有研究中，广义多粒度粗糙集特征选择的研究并不完善，未有人通过元启发式算法进行广义多粒度粗糙集特征选择算法的研究。元启发式算法是启发式算法的改进，由于其有较好的泛化性、较强的通用性，现已被广泛应用于各个领域。因此，本文首先介绍了广义多粒度粗糙集的相关概念，然后详细介绍了蚁群算法的基础知识，在此基础上提出通过元启发算法(蚁群算法)实现对广义多粒度粗糙集特征选择算法的研究。实验结果表明，本文所提的算法可以对高维数据进行降维，并且得到的特征子集并没有降低原数据集的分类精度。

2. 基本概念

四元组 $DS=\left(U,AT=C\cup D,V,f\right)$ 为决策系统，其中U为论域，C为条件属性集，D为决策属性集，V为 $a_k\in AT$ 的值域集，f为映射函数。

定义1 [8] 给定决策系统 $DS=\left(U,AT=C\cup D,V,f\right)$ ，对 $X\subseteq U$ ，粒度集 $P=\left\{P_1,P_2,\cdots ,P_m\right\}$ ， $P_i\subseteq C\left(1\le i\le m\right)$ ，通过特征函数 $S_X^{P_i}\left(x\right)$ 描述X和等价类 ${\left[x\right]}_{P_i}$ 之间的包含关系，特征函数 $S_X^{P_i}\left(x\right)$ 定义为：

$S_X^{P_i}\left(x\right)=\{\begin{array}{cc}1,& {\left[x\right]}_{P_i}\subseteq X\\ 0,& 其他\end{array}$ ( $1\le i\le m$ ),

其中 $S_X^{P_i}\left(x\right)$ 为x的特征函数。

定义2 [8] 给定决策系统 $DS=\left(U,AT=C\cup D,V,f\right)$ ，对 $X\subseteq U$ ，粒度集 $P=\left\{P_1,P_2,\cdots ,P_m\right\}$ ， $P_i\subseteq C\left(1\le i\le m\right)$ ， $S_X^{P_i}\left(x\right)$ 是x的支持特征函数， $\beta \in (0.5,1]$ ，X在粒度集P上的广义多粒度粗糙集上近似集和下近似集定义为：

$\stackrel{¯}{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(X\right)}_{\beta }=\left\{x\in U|\frac{{\displaystyle \underset{i=1}{\overset{m}{\sum }}\left(1-S_{\sim X}^{P_i}\left(x\right)\right)}}{m}>1-\beta \right\}$ ,

$\underset{\_}{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(X\right)}_{\beta }=\left\{x\in U|\frac{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{S}_X^{P_i}\left(x\right)}}{m}\ge \beta \right\}$ .

定义3 [8] 给定决策系统 $DS=\left(U,AT=C\cup D,V,f\right)$ ，对 $X\subseteq U$ ，粒度集 $P=\left\{P_1,P_2,\cdots ,P_m\right\}$ ， $P_i\subseteq C\left(1\le i\le m\right)$ ，X在粒度集P上的广义多粒度粗糙集正域、边界域以及负域定义为：

$PO{S}_{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(X\right)}_{\beta }=\underset{\_}{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(X\right)}_{\beta }$ ,

$BN{D}_{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(X\right)}_{\beta }=\stackrel{¯}{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(X\right)}_{\beta }-\underset{\_}{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(X\right)}_{\beta }$ ,

$NE{G}_{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(X\right)}_{\beta }=U-\left(PO{S}_{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(X\right)}_{\beta }\cup BN{D}_{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(X\right)}_{\beta }\right)$ .

定义4 [8] 给定决策系统 $DS=\left(U,AT=C\cup D,V,f\right)$ ，不可分辨关系 $IND\left(D\right)$ 在U上导出的划分为 $U/D=\left\{D_1,D_2,\cdots ,D_r\right\}\left(1\le r\le \left|U\right|\right)$ ，粒度集 $P=\left\{P_1,P_2,\cdots ,P_m\right\}$ ， $P_i\subseteq C\left(1\le i\le m\right)$ ， $\beta \in (0.5,1]$ ，决策类集合U/D在粒度集P上的广义多粒度粗糙集上近似集和下近似集定义为：

$\stackrel{¯}{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(U/D\right)}_{\beta }=\left\{\stackrel{¯}{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(D_1\right)}_{\beta },\stackrel{¯}{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(D_2\right)}_{\beta },\cdots ,\stackrel{¯}{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(D_r\right)}_{\beta }\right\}$ ,

$\underset{\_}{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(U/D\right)}_{\beta }=\left\{\underset{\_}{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(D_1\right)}_{\beta },\underset{\_}{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(D_2\right)}_{\beta },\cdots ,\underset{\_}{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(D_r\right)}_{\beta }\right\}$ .

决策类集合U/D在粒度集P上的正域和边界域定义为：

$PO{S}_{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(U/D\right)}_{\beta }={\displaystyle \underset{D_l\in U/D}{\cup }\underset{\_}{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(D_l\right)}_{\beta }}$ ,

$BN{D}_{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(U/D\right)}_{\beta }={\displaystyle \underset{D_l\in U/D}{\cup }\stackrel{¯}{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(D_l\right)}_{\beta }}-{\displaystyle \underset{D_l\in U/D}{\cup }\underset{\_}{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{\left(D_l\right)}_{\beta }}$ .

性质1给定决策系统 $DS=\left(U,AT=C\cup D,V,F,f\right)$ ，对 $\forall A\subseteq B\subseteq C$ ，粒度集 $P\_B=\left\{B_1,B_2,\cdots ,B_m\right\}$ ， $B_i\subseteq B\left(1\le i\le m\right)$ ， ${\displaystyle \underset{i=1}{\overset{m}{\cup }}{B}_i}=B$ ，粒度集 $P\_A=\left\{A_1,A_2,\cdots ,A_k\right\}$ ， $A_l\subseteq A\left(1\le l\le k\right)$ ， ${\displaystyle \underset{l=1}{\overset{k}{\cup }}{A}_l}=A$ ， $\beta \in (0.5,1]$ ，可得 $PO{S}_{{\displaystyle \underset{l=1}{\overset{k}{\sum }}{A}_l}}{\left(U/D\right)}_{\beta }\subseteq PO{S}_{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{B}_i}}{\left(U/D\right)}_{\beta }$ 或 $PO{S}_{{\displaystyle \underset{l=1}{\overset{k}{\sum }}{A}_l}}{\left(U/D\right)}_{\beta }\supseteq PO{S}_{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{B}_i}}{\left(U/D\right)}_{\beta }$ 均不恒成立。

3. 广义多粒度粗糙集特征选择算法

元启发式算法包括遗传算法 [9] 、蜂群算法 [10] 、蚁群算法 [11] 等。接下来将详细介绍蚁群算法。

现实生活中，蚂蚁在觅食的过程中会在其经过的路径上留下信息素，后面的蚂蚁能感知到路径上的信息素，依据信息素指导自己的行为，选择具有信息素含量较多的路径可能性最大，也会留下信息素并对走过路径上的信息素加强。这样，大量蚂蚁组成的集体觅食行为就表现为对信息素正反馈的现象，进而逼近了最优路径。受现实生活中蚂蚁觅食的影响，Dorigo等 [11] 提出了蚁群优化算法。Jensen等 [12] 将蚁群优化算法用于粗糙集中的特征选择。Chen等 [13] 将粗糙集中求取核属性集的方法融合到利用蚁群优化算法进行特征选择的算法中。特征选择的过程中，将单个条件属性看做一个节点，节点和节点之间的路径就是特征选择的过程，首先计算决策系统的核属性集，然后定义最大迭代次数，在每次迭代过程中给定一个由蚁群组成的搜索空间，蚁群中的每只人工蚂蚁从核属性集开始构造解，随机选择一个节点，再依据概率公式进行下一个节点的选择直到满足构造解的停止条件。每轮迭代结束后，进行信息素的更新，迭代过程结束后得到最优特征子集。下面将详细说明通过蚁群算法对决策系统进行特征选择的过程。

启发式信息

定义5 [8] 给定决策系统 $DS=\left(U,AT=C\cup D,V,f\right)$ ，粒度集 $P=\left\{P_1,P_2,\cdots ,P_m\right\}$ ， $P_i\subseteq C\left(1\le i\le m\right)$ ，对 $\beta \in (0.5,1]$ ，D关于粒度集P在广义多粒度粗糙集下的依赖度定义为：

$r{({\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i},D)}_{\beta }=\frac{\left|PO{S}_{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i}}{(U/D)}_{\beta }\right|}{\left|U\right|}$ .

定义6 给定决策系统 $DS=\left(U,AT=C\cup D,V,f\right)$ ，粒度集 $P\_C=\left\{C_1,C_2,\cdots ,C_n\right\}$ ， $C_i\subseteq C\left(1\le i\le n\right)$ ， ${\displaystyle \underset{i=1}{\overset{n}{\cup }}{C}_i}=C$ ，粒度集 $P\_B=\left\{B_1,B_2,\cdots ,B_m\right\}$ ， $B_j\subseteq B\left(1\le j\le m\right)$ ， ${\displaystyle \underset{j=1}{\overset{m}{\cup }}{B}_j}=B$ ，粒度集 $P\_A=\left\{A_1,A_2,\cdots ,A_k\right\}$ ， $A_l\subseteq A\left(1\le l\le k\right)$ ， ${\displaystyle \underset{l=1}{\overset{k}{\cup }}{A}_l}=A$ ， $A\subset B\subseteq C$ ， $\beta \in (0.5,1]$ ，若属性集B为DS的广义多粒度属性约简，那么B应该满足如下条件：

1) $r{\left({\displaystyle \underset{j=1}{\overset{m}{\sum }}{B}_j},D\right)}_{\beta }=r{\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{C}_i},D\right)}_{\beta }$ ；

2) $\forall A\subset B$ ， $r{\left({\displaystyle \underset{l=1}{\overset{k}{\sum }}{A}_l},D\right)}_{\beta }\ne r{\left({\displaystyle \underset{j=1}{\overset{m}{\sum }}{B}_j},D\right)}_{\beta }$ 。

定义7给定决策系统 $DS=\left(U,AT=C\cup D,V,f\right)$ ，粒度集 $P\_B=\left\{B_1,B_2,\cdots ,B_m\right\}$ ， $B_i\subseteq B\left(1\le i\le m\right)$ ， ${\displaystyle \underset{i=1}{\overset{m}{\cup }}{B}_i}=B$ ，粒度集 $P\_DB=\left\{B_{d1},B_{d2},\cdots ,B_{dm}\right\}$ ， $B_l\subseteq B-\left\{b\right\}$ $\left(d1\le l\le dm\right)$， ${\displaystyle \underset{l=d1}{\overset{dm}{\cup }}{B}_l}=B-\left\{b\right\}$ ， $B-\left\{b\right\}\subseteq B\subseteq C$ ， $\beta \in (0.5,1]$ ，对 $\forall b\in B$ 的内部属性重要度定义为：

$Si{g}_{inner}{\left(b,B,D\right)}_{\beta }=r{\left({\displaystyle \underset{i=1}{\overset{m}{\sum }}{B}_i},D\right)}_{\beta }-r{\left({\displaystyle \underset{l=d1}{\overset{dm}{\sum }}{B}_l},D\right)}_{\beta }$ .

当 $Si{g}_{inner}{\left(b,B,D\right)}_{\beta }=0$ ，说明属性b是不重要的，当 $Si{g}_{inner}{\left(b,B,D\right)}_{\beta }\ne 0$ ，说明属性b是不可缺少的。

因此可以将核属性集定义为：

$core\left(C\right)=\left\{b\in C|Si{g}_{inner}{\left(b,C,D\right)}_{\beta }\ne 0\right\}$ .

性质2广义多粒度粗糙集理论中，满足核属性集是约简集的交集，即：

$core\left(C\right)=\cap RED\left(C\right)$ .

证明：

给定决策系统 $DS=\left(U,AT=C\cup D,V,f\right)$ ，粒度集 $P\_C=\left\{C_1,C_2,\cdots ,C_n\right\}$ ， $C_i\subseteq C\left(1\le i\le n\right)$ ， ${\displaystyle \underset{i=1}{\overset{n}{\cup }}{C}_i}=C$ ， $\beta \in (0.5,1]$ 。

1) 设 $a\notin \cap RED\left(C\right)$ ， $\exists R\in RED\left(C\right)$ 使得 $a\notin R$ ，满足 $r{\left({\displaystyle \underset{j=1}{\overset{m}{\sum }}{R}_j},D\right)}_{\beta }=r{\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{C}_i},D\right)}_{\beta }$ (粒度集 $P\_R=\left\{R_1,R_2,\cdots ,R_m\right\}$ ， $R_j\subseteq R\left(1\le j\le m\right)$ ， ${\displaystyle \underset{j=1}{\overset{m}{\cup }}{R}_j}=R$ )，因为 $R\subseteq C-\left\{a\right\}\subseteq C$ ，故 $r{\left({\displaystyle \underset{j=1}{\overset{m}{\sum }}{R}_j},D\right)}_{\beta }=r{\left({\displaystyle \underset{l=1}{\overset{o}{\sum }}A{C}_l},D\right)}_{\beta }$ (粒度集 $P\_AC=\left\{A{C}_1,A{C}_2,\cdots ,A{C}_o\right\}$ ， $A{C}_l\subseteq C-\left\{a\right\}\left(1\le l\le o\right)$ ， ${\displaystyle \underset{l=1}{\overset{o}{\cup }}A{C}_l}=C-\left\{a\right\}$ )，由定义7可得 $r{\left({\displaystyle \underset{l=1}{\overset{o}{\sum }}A{C}_l},D\right)}_{\beta }=r{\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{C}_i},D\right)}_{\beta }$ ，即 $a\notin core\left(C\right)$ ，因此可得 $core\left(C\right)\subseteq \cap RED\left(C\right)$ 。

2) 设 $a\notin core\left(C\right)$ ，由定义7可得 $r{\left({\displaystyle \underset{l=1}{\overset{o}{\sum }}A{C}_l},D\right)}_{\beta }=r{\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{C}_i},D\right)}_{\beta }$ (粒度集 $P\_AC=\left\{A{C}_1,A{C}_2,\cdots ,A{C}_o\right\}$ ， $A{C}_l\subseteq C-\left\{a\right\}\left(1\le l\le o\right)$ ， ${\displaystyle \underset{l=1}{\overset{o}{\cup }}A{C}_l}=C-\left\{a\right\}$ )。 $\exists R\subseteq C-\left\{a\right\}$ ，使得 $r{\left({\displaystyle \underset{j=1}{\overset{m}{\sum }}{R}_j},D\right)}_{\beta }=r{\left({\displaystyle \underset{l=1}{\overset{o}{\sum }}A{C}_l},D\right)}_{\beta }$ (粒度集 $P\_R=\left\{R_1,R_2,\cdots ,R_m\right\}$ ， $R_j\subseteq R\left(1\le j\le m\right)$ ， ${\displaystyle \underset{j=1}{\overset{m}{\cup }}{R}_j}=R$ )且 $\forall A\subset R$ ， $r{\left({\displaystyle \underset{r=1}{\overset{k}{\sum }}{A}_r},D_{mc}\right)}_{\beta }\ne r{\left({\displaystyle \underset{j=1}{\overset{m}{\sum }}{R}_j},D\right)}_{\beta }$ (粒度集 $P\_A=\left\{A_1,A_2,\cdots ,A_k\right\}$ ， $A_r\subseteq A\left(1\le r\le k\right)$ ， ${\displaystyle \underset{r=1}{\overset{k}{\cup }}{A}_r}=A$ )，即 $R\in RED\left(C-\left\{a\right\}\right)$ ，又因为 $R\subseteq C-\left\{a\right\}\subseteq C$ ，那么 $R\in RED\left(C\right)$ ，因为 $a\notin R$ ，可得 $a\notin \cap RED\left(C\right)$ ，因此 $\cap RED\left(C\right)\subseteq core\left(C\right)$ 。

定义8给定决策系统 $DS=\left(U,AT=C\cup D,V,f\right)$ ，粒度集 $P\_B=\left\{B_1,B_2,\cdots ,B_m\right\}$ ， $B_i\subseteq B\left(1\le i\le m\right)$ ， ${\displaystyle \underset{i=1}{\overset{m}{\cup }}{B}_i}=B$ ，粒度集 $P\_AB=\left\{B_{a1},B_{a2},\cdots ,B_{am}\right\}$ ， $B_l\subseteq B$ $\left(a1\le l\le am\right)$， ${\displaystyle \underset{l=a1}{\overset{am}{\cup }}{B}_l}=B\cup \left\{b\right\}$ ， $B\subseteq B\cup \left\{b\right\}\subseteq C$ ， $\beta \in (0.5,1]$ ，对 $\forall b\in C-B$ 的外部属性重要度定义为：

$Si{g}_{outer}{\left(b,B,D\right)}_{\beta }=r{\left({\displaystyle \underset{l=a1}{\overset{am}{\sum }}{B}_l},D\right)}_{\beta }-r{\left({\displaystyle \underset{i=1}{\overset{m}{\sum }}{B}_i},D\right)}_{\beta }$ .

给定决策系统 $DS=\left(U,AT=C\cup D,V,f\right)$ ，首先通过定义7计算DS中的核属性集core，每只人工蚂蚁构造解时从core开始，从候选属性集中随机选择一个节点 $i\in C-core$ ，当前人工蚂蚁在节点i，对 $\forall j\in C-\left\{core\cup i\right\}$ ，j关于i的启发信息定义为：

${\eta }_{ij}=Si{g}_{outer}{\left(j,\left\{core\cup i\right\},D\right)}_{\beta }$ ,

如果 ${\eta }_{ij}<\epsilon$ ，那么 ${\eta }_{ij}\leftarrow \epsilon$ ，其中 $\epsilon >0$ 。

可行解的构造

当前人工蚂蚁在节点i，依据概率选择下一个节点，概率计算如下：

$p_{ij}^k\left(t\right)=\frac{{\tau }_{ij}^a{\eta }_{ij}^b\left(t\right)}{{\displaystyle \underset{l\in allowe{d}_k}{\sum }{\tau }_{il}^a{\eta }_{il}^b\left(t\right)}}$ , $j\in allowe{d}_k$ .

其中k表示蚂蚁数；t表示迭代次数； $allowe{d}_k$ 表示候选属性集； ${\tau }_{ij}$ 表示节点i到节点j路径上的信息素； ${\eta }_{ij}$ 表示节点j关于节点i的启发信息； $a>0$ 表示信息素相对于启发信息的相对重要性； $b>0$ 表示启发信息相对于信息素的相对重要性。若 $a\gg b$ ，人工蚂蚁选择下一个节点主要是依据信息素的大小；若 $b\gg a$ ，人工蚂蚁选择下一个节点主要是依据启发信息的大小。

只要满足以下两个条件之一，人工蚂蚁将停止解的构造：

1) $r{\left({\displaystyle \underset{j=1}{\overset{n}{\sum }}{R}_j},D\right)}_{\beta }=r{\left({\displaystyle \underset{i=1}{\overset{m}{\sum }}{P}_i},D\right)}_{\beta }$ 。其中R是蚂蚁构造的当前解( $R_1,R_2,\cdots ,R_n\subseteq R$ ， ${\displaystyle \underset{j=1}{\overset{n}{\cup }}{R}_j}=R$ ； $P_1,P_2,\cdots ,P_m\subseteq C$ ， ${\displaystyle \underset{i=1}{\overset{m}{\cup }}{P}_i}=C$ )；

2) 当前解的长度 $\left|R\right|$ 大于临时最短属性集合的长度。

Table 1. A generalized multi-granularity rough set feature selection algorithm based on ant colony algorithm (GL-AFS)

表1. 基于蚁群算法的广义多粒度粗糙集特征选择算法

信息素的更新

每轮迭代结束时，可得到一个当前最优解，此时需要对每条路径上的信息素进行更新，信息素依据以下规则更新：

${\tau }_{ij}\left(t+1\right)=\rho {\tau }_{ij}\left(t\right)+\Delta {\tau }_{ij}\left(t\right)$ .

其中 ${\tau }_{ij}\left(t\right)$ 表示迭代t次时路径 $\left(i,j\right)$ 上的信息素值； ${\tau }_{ij}\left(t+1\right)$ 表示下一次迭代时路径 $\left(i,j\right)$ 上的信息素值； $\rho \left(0<\rho <1\right)$ 表示信息素蒸发的衰减常数； $\Delta {\tau }_{ij}\left(t\right)$ 表示路径 $\left(i,j\right)$ 上存储的信息素值，计算方式如下：

$\Delta {\tau }_{ij}\left(t\right)=\{\begin{array}{ll}q/\left|R\left(t\right)\right|\hfill & \left(i,j\right)已遍历\hfill \\ 0\hfill & 其他\hfill \end{array}$ .

其中q是给定的常数； $R\left(t\right)$ 表示在迭代次数t时，当前得到属性集合的长度。

下面将给出通过蚁群算法实现广义多粒度粗糙集特征选择的算法，算法的具体描述见表1。

表1中，步骤2用于计算广义多粒度粗糙集的依赖度，步骤3用于求取决策系统的核属性集，步骤4用于模拟蚂蚁觅食的过程，其中，步骤4.1.3为蚂蚁觅食结束的条件，步骤4.2为路径上信息素的更新。

4. 实验分析

本节将在运行时间和分类精度两个方面对所提出的算法进行验证。实验选用6组标准UCI数据集，所用数据集见表2。数据集通过WEKA3.6进行等频离散化，将数据集中名词性数据使用整数进行替换表示。实验所运行的硬件环境为：Windows10 64位操作系统；8192MB RAM内存；Intel Core i3-9100 CPU；软件环境为：Pycharm 2020；编程语言：Python。

Table 2. Dataset description

表2. 数据集描述

Table 3. Feature subset length comparison

表3. 特征子集长度比较

Table 4. KNN classification accuracy

表4. KNN分类精度

本节验证GL-AFS算法的有效性，进行了两方面的比较：特征子集长度的比较，见表3；特征子集分类精度的比较，见表4、表5。为了满足多粒度的思想，实验任选3个属性看作一个粒度( $num=3$ )、4个属性看作一个粒度( $num=4$ )、5个属性看作一个粒度( $num=5$ )，且满足粒度和粒度之间的交集为空，粒度的并集为条件属性集。实验参数：阈值 $\beta =0.6$ 、 $a=1$ 、 $b=0.01$ 、 $\rho =0.9$ 、 $q=0.1$ 、 $\epsilon =0.001$ 、初始化信息素为0.5。算法运行停止的条件是：达到最大循环次数或三次迭代过程得到的特征集合相同。由于主要依据信息素进行特征选择、粒度选择的随机性使得蚁群算法每次得到的结果不同，为了保证实验的准确性，将GL-AFS算法运行20次，取特征选择结果长度的平均值放入表3中。通过表3可以看出通过本文提出的GL-AFS算法可以起到对高维数据集进行降维处理的效果。表4、表5分别为GL-AFS算法运行20次，对每次得到的结果通过十折交叉验证的方法计算在KNN、SVM分类器上的分类精度，分别取20次的平均值。通过表4、表5可以看出任选3个属性一个粒度、任选4个属性一个粒度、任选5个属性一个粒度通过GL-AFS算法得到特征集合的分类精度和条件属性集C下的得到的分类精度的数值相差不大。可以得出，通过GL-AFS算法可以得到和原数据分类性能相差不大的特征集合。

Table 5. SVM classification accuracy

表5. SVM分类精度

5. 总结

目前针对广义多粒度粗糙集特征选择的研究不完善，通过元启发式算法进行广义多粒度粗糙集特征选择未有人研究，因此，本文将元启发式算法(蚁群算法)用于广义多粒度粗糙集特征选择中具有很重要的研究意义。实验表明：本文所提算法不仅可以对高维数据实现降维的效果且得到的特征集合具有和原数据集相差不大的分类精度。

基金项目

本文受烟台市科技计划项目(编号：2022XDRH016)的资助。