﻿ 基于强化学习的特征选择算法
 计算机系统应用  2018, Vol. 27 Issue (10): 214-218 PDF

Feature Selection Algorithm Based on Reinforcement Learning
ZHU Zhen-Guo, ZHAO Kai-Xuan, LIU Min-Kang
School of Information Science and Engineering, Chongqing Jiaotong University, Chongqing 400074, China
Abstract: For the dimensional disaster and feature redundancy problems in the process of data mining, a reinforcement learning based feature selection algorithm, which is combined Q learning methods with traditional feature selection methods, is proposed in this study. In the proposed method, the agent acquires a subset of characteristics autonomously through training and learning. Experimental results show that the proposed algorithm can effectively reduce the number of features and has higher classification performance.
Key words: reinforcement learning     feature selection     Q-learning     feature subset     data mining

1 引言

2 相关理论 2.1 信息熵

 ${{H}}\left( {{X}} \right){\rm{ = - }}\int_x {{{p}}\left( x \right)} \log p\left( x \right)dx$ (1)

2.2 Pearson相关系数

Pearson相关系数反映了两个变量间的线性相关程度, 是一种线性相关系数. 假设, X, Y为随机变量, 两个随机变量的Pearson相关系数定义如下,

 ${\rho _{x,y}} = \frac{{\sum\limits_{i = 1}^n {\left( {{X_i} - \overline X } \right)\left( {{Y_i} - \overline Y } \right)} }}{{\sqrt {\sum\limits_{i = 1}^n {{{\left( {{X_i} - \overline X } \right)}^2}} } \sqrt {\sum\limits_{i = 1}^n {{{\left( {{Y_i} - \overline Y } \right)}^2}} } }}$ (2)

2.3 Q学习

 ${{Q}}\left( {{S_t},{a_t}} \right) = R\left( {{S_t},{a_t}} \right) + \gamma \max {{Q}}\left( {{S_{t + 1}},{a_{t + 1}}} \right)$ (3)

 \begin{aligned} {{Q}}\left( {{S_t},{a_t}} \right) =& \left( {1 - \alpha } \right){{Q}}\left( {{S_t},{a_t}} \right)+\alpha \left(R\left( {{S_t},{a_t}} \right) \right. \\& \left.+ \gamma \max {{Q}}\left( {{S_{t + 1}},{a_{t + 1}}} \right)\right)\end{aligned} (4)

3 RLFS算法实现

 图 1 RLFS算法示意图

A) 数据预处理, 包括对原始数据集进行归一化和离散化处理, 得到训练数据.

B) 计算每个特征的信息熵和信息熵均值, 并将特征信息熵高于信息熵均值的特征记录在信息熵表.

C) 计算每两个特征Pearson相关系数以及Pearson相关系数的均值, 将高于Pearson相关系数均值的特征对记录在Pearson表.

D) 此步骤为Q学习算法中Agent进行迭代训练学习并逐步进行决策的核心过程. 将训练数据和Pearson表以及信息熵表代入Agent, Agent根据添加和删除特征的动作所带来的不同收益作出决策.

E) 当Agent训练学习完成后输出Q表, 通过对Q表的分析得到经过RLFS算法选择后的特征子集.

1) S是经RLFS算法选择到的最优特征子集;

2) T为当前特征子集, 其表示Agent在某时刻已经选择特征的集合;

3) H为候选特征子集, 其表示未被选入T中的特征集合;

RLFS算法主要步骤

1) 初始化当前特征子集T= $\emptyset$ , 候选特征集合为H={f1, f2, …, fD}.

2) 计算每个特征的信息熵以及信息熵均值, 将高于信息熵均值的特征记入HS.

3) 计算每两个特征间的Pearson相关系数以及Pearson相关系数的均值, 将高于均值的特征记入PS.

4) 当T= $\emptyset$ 时, 随机添加一个特征fadd(faddH), TT∪{fadd}, HH\{fadd}.

6) 判断是否满足终止条件, 若满足则停止并通过Q表输出最大Q值所对应的特征子集S, 不满足则重复步骤4)–6).

4 实验设计与结果比较 4.1 实验数据

4.2 实验环境

4.3 实验结果

1) 通过对比4种特征选择算法在不同分类器下平均分类准确度, 可以看出本文提出的RLFS算法在不同的数据集上均有较好的表现, 算法平均分类准确度较高.

2) RLFS算法在少数情况中表现不如其它算法, 如在LSVM分类器下的Iono数据集上准确率低于SVM-L2, 在朴素贝叶斯分类器下的Wine数据集上准确率低于SVM-RFE, 但相差较小, 而在其余情况均高于其它算法.

3) 在某些分类器下的数据集上, 经特征选择算法找到的特征子集分类准确率低于原始特征, 例如在线性支持向量机分类器上, 所有算法不如原始特征分类准确率高, 但偏差不大. 这在现实中是可能出现的, 因为特征选择的目标有两点, 其一是删除不相关特征和冗余特征; 其二是找出关键特征缩减特征数目, 提高预测准确率. 因此牺牲较小的分类准确率得到特征数目较少的优质数据也是可行的.

5 总结

 [1] Gheyas IA, Smith LS. Feature subset selection in large dimensionality domains. Pattern Recognition, 2010, 43(1): 5-13. DOI:10.1016/j.patcog.2009.06.009 [2] 刘景华, 林梦雷, 张佳, 等. 一种启发式的局部随机特征选择算法. 计算机工程与应用, 2016, 52(2): 170-174, 185. DOI:10.3778/j.issn.1002-8331.1401-0302 [3] 戴平, 李宁. 一种基于SVM的快速特征选择方法. 山东大学学报(工学版), 2010, 40(5): 60-65. [4] Mnih V, Kavukcuoglu K, Silver D, et al. Human-level control through deep reinforcement learning. Nature, 2015, 518(7540): 529-533. DOI:10.1038/nature14236 [5] 赵冬斌, 邵坤, 朱圆恒, 等. 深度强化学习综述: 兼论计算机围棋的发展. 控制理论与应用, 2016, 33(6): 701-717. [6] 姚旭, 王晓丹, 张玉玺, 等. 特征选择方法综述. 控制与决策, 2012, 27(2): 161-166, 192. [7] 刘华文. 基于信息熵的特征选择算法研究[博士学位论文]. 长春: 吉林大学, 2010. [8] 董红斌, 滕旭阳, 杨雪. 一种基于关联信息熵度量的特征选择方法. 计算机研究与发展, 2016, 53(8): 1684-1695. [9] 王晨曦, 林耀进, 刘景华, 等. 基于最近邻互信息的特征选择算法. 计算机工程与应用, 2016, 52(18): 74-78. DOI:10.3778/j.issn.1002-8331.1412-0214 [10] 李叶紫, 周怡璐, 王振友. 基于互信息的组合特征选择算法. 计算机系统应用, 2017, 26(8): 173-179. DOI:10.15888/j.cnki.csa.005891 [11] 仇利克, 郭忠文, 刘青, 等. 基于冗余分析的特征选择算法. 北京邮电大学学报, 2017, 40(1): 36-41. [12] 章惠龙, 李龙澍. Q学习在RoboCup前场进攻动作决策中的应用. 计算机工程与应用, 2013, 49(7): 240-242. DOI:10.3778/j.issn.1002-8331.1108-0114 [13] Goldberg Y, Kosorok MR. Q-learning with censored data. Annals of Statistics, 2012, 40(1): 529-560. DOI:10.1214/12-AOS968 [14] UCI机器学习数据集数据库. http://archive.ics.uci.edu/ml/datasets.html.