基于改进徒步优化算法的变精度邻域粗糙集特征选择研究

Research on Variable Precision Neighborhood Rough Set Feature Selection Based on Improved Hiking Optimization Algorithm

摘要: 特征选择是数据降维的有效方法，粗糙集理论是处理不确定性信息的有效工具，在粗糙集理论中，变精度邻域粗糙集是处理连续型数值信息系统的有效工具，在分类任务中，变精度邻域粗糙集可以为属性集提供重要性度量。徒步优化算法是群智能优化算法中的一种，可以寻找组合最优解，本文针对徒步优化算法无法动态平衡局部与全局寻优能力，容易陷入局部最优的问题，提出改进徒步优化算法，并提出基于改进徒步优化算法的特征选择算法。为了验证所提算法的有效性，在8个UCI数据集上进行了基于改进徒步优化算法的特征选择算法的对比实验，通过实验验证了所提出算法的有效性和可行性。

Abstract: Feature selection is an effective method for data dimensionality reduction, and rough set theory is an effective tool for dealing with uncertainty information. In rough set theory, variable precision neighborhood rough set is an effective tool for dealing with continuous numerical information systems. Hiking optimization algorithm is one of the swarm intelligence optimization algorithms, which can find the combined optimal solution. In this paper, aiming at the problem that the hiking optimization algorithm cannot dynamically balance the local and global optimization ability, and is easy to fall into the local optimum, an improved hiking optimization algorithm is proposed. A feature selection algorithm based on improved hiking optimization algorithm was proposed. In order to verify the effectiveness of the proposed algorithm, comparative experiments of feature selection algorithm based on improved hiking optimization algorithm are carried out on 8 UCI data sets, and the effectiveness and feasibility of the proposed algorithm are verified by experiments.

1. 引言

数据降维作为人工智能数据预处理的关键步骤，在机器学习领域具有重要的理论和实践意义。通过减少特征数量，数据降维不仅能够提高算法效率、降低存储需求，还能有效去除冗余信息，揭示数据潜在结构，从而增强模型的泛化能力。

粗糙集理论[1]是处理不确定性信息的有效工具，变精度邻域粗糙集[2]是基于邻域粗糙集的扩展模型，在邻域粗糙集的基础上引入了变精度参数β，允许在分类过程中存在一定的误差，增加了模型对于噪声样本的处理能力，在连续型数值信息系统的分类任务中，变精度邻域粗糙集可以有效地提供属性集的重要度度量。徒步优化算法[3]是群智能优化算法的一种，徒步优化算法的思想源于徒步旅行者登山的过程，徒步者根据目前领队的位置进行移动，并且受到地形的影响发生速度改变。

针对徒步优化算法无法动态平衡局部和全局寻优能力、易陷入局部最优解的问题，本文结合多策略改进了徒步优化算法，结合变精度邻域粗糙集，提出特征选择算法。在8个UCI数据集上进行对比实验，实验结果验证了本文所提算法在分类精度上具有一定优势，验证了所提算法的可行性和有效性。

2. 基本概念

2.1. 变精度邻域粗糙集模型

定义1 [2]：邻域决策系统定义为$RDIS=\left(U,C\cup D,V,f\right)$ ，其中$U=\left\{x_1,x_2,\cdots ,x_n\right\}$ 表示论域，是非空有限对象的集合，$C=\left\{a_1,a_2,\cdots ,a_m\right\}$ 表示非空有限的条件属性集，$D=\left\{d\right\}$ 表示决策属性，$V=V_C\cup V_D$ 表示值域，其中$V_C$ 表示元素在条件属性下的属性值的集合，中$V_D$ 表示元素在决策属性下的属性值的集合。f表示元素到值域的映射，$f_C=U\times C\to V_C$ 表示条件属性到值的映射，$f\left(x,a\right)$ 表示元素x在条件属性a下的值，$f_D=U\times D\to V_D$ 表示元素对于决策属性的映射，$f\left(x,d\right)$ 表示元素x的决策值。

定义2 [2]：在邻域粗糙集模型中，邻域决策系统$RDIS=\left(U,C\cup D,V,f\right)$ ，$\left(U,\Delta \right)$ 定义为度量空间，其中$\Delta$ 定义为度量，对于元素$x,y,z\in U$ ，满足以下性质：

1) $\Delta \left(x,y\right)\ge 0$ ，当且仅当$x=y$ 时，$\Delta \left(x,y\right)=0$ ；

2) $\Delta \left(x,y\right)=\Delta \left(y,x\right)$ ；

3) $\Delta \left(x,y\right)+\Delta \left(y,z\right)\ge \Delta \left(x,z\right)$ 。

在邻域粗糙集模型中，采用欧几里得距离作为距离度量，对于任意属性集$B\subseteq C$ ，在B上的距离度量$\Delta$ 表示为：

${\Delta }_B\left(x,y\right)=\sqrt{{\displaystyle \sum _{a\in B}{\left(f\left(x,a\right)-f\left(y,a\right)\right)}^2}}$ (1)

定义3 [2]：在邻域决策系统$RDIS=\left(U,C\cup D,V,f\right)$ 中，属性集$B\subseteq C$ ，对于元素$\forall x\in U$ ，关于B的$\delta$ 邻域定义为：

${\delta }_B\left(x\right)=\left\{y\in U|{\Delta }_B\left(x,y\right)\le \delta \right\}$ (2)

定义4 [2]：在变精度邻域粗糙集模型中，邻域决策系统$RDIS=\left(U,C\cup D,V,f\right)$ ，属性集$B\subseteq C$ ，给定阈值$\beta \in \left(0.5,1\right]$ ，对于$\forall X\subseteq U$ ，X关于B的下近似和上近似定义为：

$\underset{\_}{N_B^{\beta }}\left(X\right)=\left\{x\in U|\frac{\left|{\delta }_B\left(x\right)\cap X\right|}{{\delta }_B\left(x\right)}\ge \beta \right\}$ (3)

$\overline{N_B^{\beta }}\left(X\right)=\left\{x\in U|\frac{\left|{\delta }_B\left(x\right)\cap X\right|}{{\delta }_B\left(x\right)}\ge 1-\beta \right\}$ (4)

定义5 [2]：在变精度邻域粗糙集模型中，邻域决策系统$RDIS=\left(U,C\cup D,V,f\right)$ ，论域U以决策属性$D=\left\{d\right\}$ 划分为$U/D=\left\{X_1,X_2,\cdots ,X_{\left|U/IND\left(D\right)\right|}\right\}$ ，属性集$B\subseteq C$ ，论域U关于决策属性D的下近似和上近似定义为：

$\underset{\_}{N_B^{\beta }}\left(D\right)={\displaystyle \underset{i=1}{\overset{\left|U/IND\left(D\right)\right|}{\cup }}\underset{\_}{N_B^{\beta }}\left(X\right)}$ (5)

$\overline{N_B^{\beta }}\left(D\right)={\displaystyle \underset{i=1}{\overset{\left|U/IND\left(D\right)\right|}{\cup }}\overline{N_B^{\beta }}}\left(X\right)$ (6)

定义6 [2]：在变精度邻域粗糙集模型中，邻域决策系统$RDIS=\left(U,C\cup D,V,f\right)$ ，属性集$B\subseteq C$ ，关于决策属性D的正域、边界域定义为：

$PO{S}_B^{\delta }\left(D\right)=\underset{\_}{N_B^{\beta }}\left(D\right)$ (7)

$BN{D}_B^{\delta }\left(D\right)=\overline{N_B^{\beta }}\left(D\right)$ (8)

定义7 [2]：在变精度邻域粗糙集模型中，邻域决策系统$RDIS=\left(U,C\cup D,V,f\right)$ ，属性集$B\subseteq C$ ，决策属性D关于属性集B的依赖度定义为：

${\gamma }_B^{\delta }\left(D\right)=\frac{\left|PO{S}_B^{\delta }\left(D\right)\right|}{\left|U\right|}$ (9)

2.2. 徒步优化算法

定义8 [3]：徒步优化算法中，徒步者的速度由当前地形坡度决定，其速度定义为：

$w_{i,t}=6e^{-3.5\left|s_{i,t}+0.05\right|}$ (10)

其中，$w_{i,t}$ 表示第i个徒步者$h_i$ 在第t次迭代中的速度，$s_{i,t}$ 表示徒步者$h_i$ 在第t次迭代中所处位置的坡度，定义为：

$s_{i,t}=\frac{dh}{dx}=\tan {\theta }_{i,t}$ (11)

其中，$dh$ 表示地形的高度差异，$dx$ 表示徒步者的行走距离，${\theta }_{i,t}$ 表示地形的倾斜角度，${\theta }_{i,t}\in \left[0^{\circ },{50}^{\circ }\right]$ 。

定义9 [3]：徒步优化算法中，徒步者的实际当前速度计算方式定义为：

$w_{i,t}=w_{i,t-1}+{\gamma }_{i,t}\left(X_{best}-{\alpha }_{i,t}{X}_{i,t}\right)$ (12)

其中，${\gamma }_{i,t}$ 是$\left[0,1\right]$ 内均匀分布的随机数，$w_{i,t}$ 和$w_{i,t-1}$ 表示徒步者的当前速度和上一时刻速度，$X_{best}$ 表示领队$h_{best}$ 的当前位置，$X_{i,t}$ 表示徒步者$h_i$ 在第$t$ 时刻的位置，${\alpha }_{i,t}$ 表示一个扫描因子$SF$ ，$SF\in \left[1,3\right]$ 。徒步者的位置更新函数表示为：

$X_{i,t}=X_{i,t-1}+w_{i,t}$ (13)

定义10 [3]：徒步优化算法中，徒步者的位置初始化定义为：

$X_{i,t}=lb+\delta \left(ub-lb\right)$ (14)

其中，lb和ub分别表示解空间维度的下界和上界，$\delta$ 是$\left[0,1\right]$ 范围内均匀分布的随机数向量，经过初始化可以得到一个徒步者位置矩阵：

$R=\left[\begin{array}{c}{X}_{1,t}\\ X_{2,t}\\ ⋮\\ X_{pop,t}\end{array}\right]=\left[\begin{array}{cccc}{x}_{1,t}^1& x_{1,t}^2& \cdots & x_{1,t}^d\\ x_{2,t}^1& x_{2,t}^2& \cdots & x_{2,t}^d\\ ⋮& ⋮& ⋮& ⋮\\ x_{pop,t}^1& x_{pop,t}^2& \cdots & x_{pop,t}^d\end{array}\right]$ (15)

其中，pop表示徒步者数量，m表示解空间维度，$x_{i,t}^j$ 表示徒步者$h_i$ 在第t时刻上，在第j个维度上的值，徒步者群体以集合$H=\left\{h_1,h_2,\cdots h_{pop}\right\}$ 表示。

定义11 [3]：给定优化目标函数f，在t时刻，徒步者$h_i$ 的适应度定义为：

$fi{t}_{i,t}=f\left(X_{i,t}\right)$ (16)

徒步优化算法的算法流程如文献[3]所示。

3. 基于改进徒步优化算法的特征选择算法

改进徒步优化算法使用Tent-Logistic-Cosine混沌映射[4]来进行初始化。

定义12：改进徒步优化算法中，使用Tent-Logistic-Cosine混沌映射进行初始化的表达式定义为：

$x_i^{j+1}=\{\begin{array}{c}\text{cos}\left(\pi \left(2r{x}_i^j+4\left(1-r\right)x_i^j\left(1-x_i^j\right)-0.5\right)\right),\text{ if}{x}_i^j<0.5\\ \text{cos}\left(\pi \left(2r\left(1-x_i^j\right)+4\left(1-r\right)x_i^j\left(1-x_i^j\right)-0.5\right)\right),\text{ else, }r\in \left[0,1\right]\end{array}$ (17)

改进徒步优化算法在地形倾斜角度${\theta }_{i,t}$ 的生成上使用了正态分布[5]。

定义13：改进徒步优化算法中，通过正态分布生成地形倾斜角度${\theta }_{i,t}$ 表达式定义为：

${\theta }_{i,t}=\frac{e^{-\frac{{\left(x-\mu \right)}^2}{2{\sigma }^2}}}{\sqrt{2\pi }\sigma }$ (18)

对扫描因子的生成使用了Beta分布[6]，Beta分布是一种参数化的概率分布。通过调整参数，可以控制分布的偏向程度，本文设置$\alpha =1$ ，$\beta =\frac{5t}{T}$ 。

定义14：改进徒步优化算法中，通过Beta分布生成扫描因子SF的表达式定义为：

$SF=1+\left(3-1\right)\times \frac{x^{\alpha -1}{\left(1-x\right)}^{\beta -1}}{{\displaystyle \underset{0}{\overset{1}{\int }}{u}^{\alpha -1}{\left(1-u\right)}^{\beta -1}du}}=\frac{2x^{\alpha -1}{\left(1-x\right)}^{\beta -1}}{B\left(\alpha ,\beta \right)}+1$ (19)

改进徒步优化算法在地形坡度上应用逃逸能量理论[7]，可以动态平衡全局搜索和局部开发的能力。

定义15：改进徒步优化算法中，徒步者的速度$w_{i,t}$ 的更新策略定义为：

$w_{i,t}=\{\begin{array}{c}{w}_{i,t-1}+{\gamma }_{i,t}\left({\beta }_{best}-{\alpha }_{i,t}{\beta }_{i,t}\right),\text{ if }rand<r_E\\ {\gamma }_{i,t}\left({\beta }_{best}-{\alpha }_{i,t}{\beta }_{i,t}\right),\text{ else}\end{array}$ (20)

其中，$r_E$ 表示平缓概率，计算方式为：

$r_E=0.1E+0.6$ (21)

$E=2E_0\left(1-\frac{t}{T}\right)$ (22)

$E_0=2rand-1$ (23)

为了使算法在算法后期不易陷入局部最优解，本文应用动态反向学习策略[8]。

定义16：改进徒步优化算法中，生成反向解的公式定义如下：

$X_i^{do}=X_i+w\cdot rand\cdot \left(rand\cdot \left(up+lb-X_i\right)-X_i\right)$ (24)

此处权重$w$ 取值为1。在获取动态反向解后，根据反向解和当前解的优劣进行选择：

$X_{i,t}=best\left(f\left(X_{i,t}\right),f\left(X_{i,t}^{do}\right)\right)$ (25)

定义17：在改进徒步优化算法的特征选择算法中，徒步者位置的二元化转换公式定义为：

$x_{i,t}^j=\{\begin{array}{c}1,\text{if Z}\left(x_{i,t}^j\right)>0.5\\ 0,\text{else}\end{array}$ (26)

其中Z表示双曲正切函数映射，其计算方式为：

$\mathbb{Z}\text{(}{x}_{i,t}^j)=\tanh \left(x_{i,t}^j\right)=\frac{e^{x_{i,t}^j}-e^{-x_{i,t}^j}}{e^{x_{i,t}^j}+e^{-x_{i,t}^j}}$ (27)

在特征选择算法中，同时兼顾分类能力和特征子集长度两个指标，所以优化算法同时优化两个目标函数，采用分层优化法，依赖度为主函数，特征子集长度为次函数，两个函数的表达式为：

$fi{t}^1=f^1\left(X_{i,t}\right)={\gamma }_B^{\delta }\left(D\right)$ (28)

$fi{t}^2=f^2\left(X_{i,t}\right)=\frac{\left|C-B\right|}{\left|C\right|}$ (29)

在算法迭代时，徒步者当前位置的更新机制为：

$X_{i,t}=\{\begin{array}{c}{X}_{i,t}^{new},\text{if }fi{t}_{new}^1>fi{t}^1\vee \left(fi{t}_{new}^1=fi{t}^1\wedge fi{t}_{new}^2>fi{t}^2\right)\\ X_{i,t},\text{else}\end{array}$ (30)

根据上述定义，本文提出基于改进徒步优化算法的特征选择算法(Improved Hiking Optimization Algorithm for Feature Selection Algorithm, IHOAFSA)，算法流程如表1所示。

Table 1. Improved Hiking Optimization Algorithm for Feature Selection Algorithm (IHOAFSA)

表1. 基于改进徒步优化算法的特征选择算法

输入：邻域决策系统$RDIS=\left(U,C\cup D,V,f\right)$ ，种群数$pop$ ，迭代数T； 输出：特征子集B；

1. 初始化：解空间维度$d=\left|C\right|$ ； 2. 根据定义12生成徒步者群体$H=\left\{h_1,h_2,\cdots h_{pop}\right\}$ ； 3. 如果$t>T$ ，转步骤8； 4. 对于$\forall h_i\in H$ ，计算其适应度$fi{t}_{i,t}^1$ 和$fi{t}_{i,t}^2$ ； 5. 设在$fi{t}_{i,t}^1$ 最大的徒步者中，$fi{t}_{i,t}^2$ 最大的徒步者为领队$h_{best}$ ，其位置为$X_{best}$ ； 6. 对于$\forall h_i\in H$ ： 6.1. 获取徒步者$h_i$ 上一时刻位置$X_{i,t-1}$ ； 6.2. 根据定义13生成地形倾斜角度${\theta }_{i,t}$ ； 6.3. 根据定义14生成扫描因子$SF$ ； 6.4. 根据定义8计算受地形影响速度$w_{i,t-1}$ ； 6.5. 根据定义15计算当前速度$w_{i,t}$ ； 6.6. 计算新的当前位置$X_{i,t}$ ，限制在上下界$lb$ 和$ub$ 之间； 6.7. 计算适应度$fi{t}^1$ 和$fi{t}^2$ ； 6.8. 根据定义16计算动态反向解$X_{i,t}^{do}$ ，限制在上下界$lb$ 和$ub$ 之间； 6.9. 计算动态反向解的适应度$fi{t}^1$ 和$fi{t}^2$ ； 6.10. 对徒步者当前位置进行更新； 7. $t=t+1$ ，转步骤3； 8. 对最优个体位置$X_{best}$ 进行二元化得到特征子集B； 9. 返回特征子集B。

4. 实验分析

为了验证所提出算法IHOAFSA的有效性，本节与算法PSORSFS [9]、FSARSR [10]、FSRSWOA [11]进行对比实验，实验统一设置邻域半径$\delta =0.1$ 、迭代次数$T=50$ ，种群数$pop=20$ ，设置算法IHOAFSA的阈值$\beta =0.8$ ，本节实验的数据集来源为UCI数据集(https://archive.ics.uci.edu/datasets/)，包括8个数据集，数据集信息如表2所示，表中分别标注了数据集的名称、缩写，后续以缩写表示数据集，样本数即元素数，属性数即特征数，类别数为论域以决策类的划分种类数，实验前预先将数据集进行最小最大归一化到$\left[0,1\right]$ 之间。由于优化算法的结果具有随机性，本实验将每个数据集在各个算法上分别独立运行5次，在SVM分类器和KNN分类器上以十倍交叉验证的方式记录每一次特征子集的分类精度，求5次分类精度的平均分类精度以及分类精度的标准差，实验结果如表3、表4以及图1、图2所示。

实验采用Inter Core i5-12490F 4.6GHz处理器、16GB内存和window11操作系统，算法的实现代码的编程语言为Python 3.11，在开发工具PyCharm 2024.3上编译运行。

Table 2. UCI datasets information

表2. UCI数据集信息

序号	数据集	缩写	样本数	属性数	类别数
1	Breast Cancer	Breast	286	9	2
2	Cervical	Cervical	88	17	2
3	Fertility	Fertility	72	19	2
4	Forty Soybean Cultivars	Forty	100	9	2
5	Image Segmentation	Image	210	19	7
6	Iris	Iris	150	4	3
7	Wine	Wine	178	13	3
8	Zoo	Zoo	101	16	7

Table 3. Classification accuracy under SVM classifier (%)

表3. SVM分类器下的分类精度(%)

数据集	PSORSFS	FSARSR	FSRSWOA	IHOAFSA
Breast	72.37 ± 0.52	73.23 ± 1.54	72.16 ± 0.17	72.30 ± 0.00
Cervical	74.82 ± 1.98	81.43 ± 1.34	83.79 ± 3.86	83.61 ± 6.55
Fertility	88.00 ± 0.00	88.00 ± 0.00	88.00 ± 0.00	88.00 ± 0.00
Forty	79.75 ± 0.64	79.88 ± 0.70	78.62 ± 1.68	80.25 ± 0.85
Image	84.38 ± 2.78	85.71 ± 3.61	84.86 ± 3.05	88.86 ± 0.23
Iris	96.67 ± 0.00	96.67 ± 0.00	96.67 ± 0.00	96.67 ± 0.00
Wine	90.14 ± 3.40	90.57 ± 4.77	91.35 ± 3.52	91.31 ± 2.59
Zoo	84.93 ± 2.88	90.89 ± 1.47	86.91 ± 5.26	91.85 ± 1.68
Average	83.88	85.80	85.30	86.61

Table 4. Classification accuracy under KNN classifier (%)

表4. KNN分类器下的分类精度(%)

数据集	PSORSFS	FSARSR	FSRSWOA	IHOAFSA
Breast	71.71 ± 1.84	70.95 ± 1.28	72.25 ± 1.76	72.94 ± 0.00
Cervical	76.39 ± 2.44	83.32 ± 4.90	81.57 ± 5.41	84.96 ± 6.41
Fertility	85.20 ± 0.75	85.20 ± 1.72	84.80 ± 1.17	85.60 ± 0.80
Forty	71.81 ± 4.53	69.94 ± 3.58	66.69 ± 0.15	71.88 ± 1.49
Image	81.90 ± 1.51	83.43 ± 2.44	82.38 ± 2.02	84.76 ± 0.67
Iris	95.33 ± 0.00	95.33 ± 0.00	95.33 ± 0.00	95.33 ± 0.00
Wine	91.29 ± 2.56	90.67 ± 3.77	91.12 ± 3.48	92.07 ± 2.50
Zoo	88.73 ± 2.01	90.07 ± 1.65	87.56 ± 1.72	91.24 ± 1.44
Average	82.80	83.61	82.71	84.85

Figure 1. Comparison of classification accuracy under SVM classifier

图1. SVM分类器下的分类精度对比图

Figure 2. Comparison of classification accuracy under KNN classifier

图2. KNN分类器下的分类精度对比图

根据实验结果所示，本文所提算法在SVM分类器和KNN分类器的大部分数据集上具有最高的平均分类精度，并且算法IHOAFSA具有最高的平均分类精度的平均值，实验结果表明了本文所提算法在分类精度上对比其他算法具有一定优势，表明了算法的可行性和有效性。

5. 结论

本文介绍了变精度邻域粗糙集和徒步优化算法，针对徒步优化算法无法动态调整局部和全局寻优能力的问题，采用多策略改进徒步优化，结合变精度邻域粗糙集提供的属性集重要度度量，提出基于改进徒步优化算法的特征选择算法。通过在UCI数据集上的对比实验验证了本文所提算法的可行性和有效性。

基金项目

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