1 引言

随着互联网、物联网、传感器等技术的快速发展, 人们在生产和生活中产生了大量的数据, 从这些数据中可以挖掘到有价值的信息. 然而其中很多数据呈现出样本数量庞大并且数据特征维度高的特点, 这种特点加大了数据挖掘的难度. 针对以上问题, 可以通过特征选择(Feature Selection)删除数据中无关、冗余的特征信息, 从而降低数据维度、噪音的干扰和算法的复杂度, 使模型变得简单且易于理解, 改进数据挖掘性能, 为后期的预测分析准备干净且可理解的数据. 在数据挖掘领域, 特征选择已经成为一个研究的热点.

目前特征选择问题的处理方法, 根据其是否依赖后续的学习算法, 大体上可以分为过滤式(Filter)和封装式(Wrapper)两种方法^[1]. Filter方法一般使用距离、信息、依赖性、一致性评价准则来增强特征与类的相关性, 削弱特征之间的相关性, 从而选出更能代表原数据特点的特征子集. 该类方法特征选择效率较高, 但对噪声敏感, 在实际应用中一般都是采用此类方法进行特征的初步筛选. Wrapper方法和所使用的分类器关系紧密, 该方法在特征筛选过程中直接用所选特征子集来训练分类器, 之后用这个分类器在验证集上的表现来评价所选的特征. 因其直接用学习算法评估特征子集, 有利于关键特征的提取, 所以得到的特征子集有较高的分类性能, 预测准确性较高; 但是Wrapper方法存在时间复杂度高的问题, 不适用于超大规模的数据挖掘任务. 然而随着计算能力提高和分布式技术的成熟, 在一定程度上解决了时间复杂度高的问题, Wrapper方法越发受到广大研究者的青睐^[2,3].

强化学习(Reinforcement Learning)是机器学习中的一个领域, 其基本思想是从环境中得到反馈而学习, 即所谓的试错学习方法. 在学习过程中, 智能体Agent不断地尝试进行选择, 并根据环境的反馈调整动作的评价值, 最终智能体Agent选择获得最大回报的策略作为最优策略^[4]. DeepMind团队提出的围棋机器人AlphaGo的算法中就包含了强化学习算法思想^[5].

研究中发现传统特征选择算法存在着不足, 或是选择的特征子集在进行分类任务时准确率较低, 或是选择的特征子集规模较大^[6]. 针对以上问题, 本文结合强化学习的决策能力和Wrapper特征选择方法, 提出了一种基于强化学习的特征选择方法(Reinforcement Learning for Feature Selection, RLFS), 将强化学习的学习和决策能力应用于特征选择过程中, 通过训练学习得到特征子集. 最后通过仿真实验证明了RLFS方法有良好的降维能力, 并有较高的分类准确率.

2 相关理论 2.1 信息熵

信息熵将随机变量取值的不确定性程度以数值的大小形式来衡量, 目的是描述信息含量的多少. 假设X是一个随机变量, X取值为x的概率用p(x)表示, 则变量X的不确定程度可以表示为信息熵H(X)的形式,

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

(1)

由此定义分析可得, 信息熵H(X)只与变量X的概率分布有关, 而与其取值无关. 这表明信息熵可以一定程度上避免噪声数据的干扰. 并且当变量X的不确定程度较高时, 则概率分布越大, 其信息熵也随之越大, 所需的信息量越多^[7]. 在数据分类中每个特征f可看作变量X, 此种情况下, 特征f的信息熵就是样本数据集相对于特征f的不纯度(Impurity)的量化形式, 表示特征f包含信息量的多少, H( f)越大, 则表明取值范围分布比较均匀, 信息纯度较低; 反之, 当H( f)越小则说明特征值分布较不均匀, 可能某个或几个值的样本较多. 如某一个特征f在样本数据集中取值唯一时, H( f)=0, 此时数据集对于特征f来讲是最纯的, 但这也意味该特征不能为分类提供任何有用信息^[8,9].

基于以上分析, 在特征选择过程中可以通过计算每个特征的信息熵来衡量该特征所包含信息量的多少, 优先选择信息熵较大的特征.

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)

其中, $\overline X $ , $\overline Y $ 分别为X,Y的均值, ${\rho _{x,y}}$ 的取值在[–1, 1]之间, 该值反映了两个变量的线性相关性的强弱程度, 其绝对值越大说明相关性越强. 当其取值为–1或1时, 表示两个变量完全相关, 其取值为0时, 表明两个变量不是线性相关, 但可能存在其他方式的相关性. 当两个特征的Pearson相关系数绝对值较大时, 两特征中有冗余特征的可能性也较大^[10,11].

基于以上分析, 在特征选择过程中可以计算特征间的Pearson相关系数, 剔除特征空间中相关系数较大的一对特征中的一个特征, 尽量减少冗余特征.

2.3 Q学习

强化学习中Q学习方法符合马尔科夫决策过程(Markov Decision Processes, MDP). 在决策过程中, Agent可以感知周围环境, 并可以执行动作列表中的任何一个动作. 在t时刻, 当前环境状态为S_t, Agent选择并执行动作a_t, 环境状态则由S_t转变为S_t+1, 同时反馈收益R(S_t, a_t)给Agent, 智能体Agent一直重复以上过程, 直到训练学习过程结束. Q学习算法中用动作评价函数Q(S_t, a_t)来表示在状态S_t时Agent选择动作a_t后所得到的最大累计回报, 此值是由Agent选择并执行动作后的即时收益与之后周期执行最优策略所得到的值, 其中Q(S_t, a_t)的值可用公式表示为:

${{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)

其中, a为动作列表中任一动作, 常量参数γ(0≤γ≤1)称作折扣系数. 在Agent训练学习过程中, 总是选择所对应的状态拥有最大Q值的动作, 然后据此策略进行迭代训练. 经过多次训练学习, 存储Q值的Q表不断更新, 以上即是Q学习算法的训练学习过程^[12,13].

为了让Q学习在适当的时刻收敛, 在公式中加入了适当的学习率. 当引入学习率 $\alpha $ 后, Q(S_t, a_t)表示为:

$\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)

其中, $\alpha \left( {0 < \alpha < 1} \right)$ 是控制Q学习算法收敛的学习率, γ(0≤γ≤1)为折扣系数.

3 RLFS算法实现

本文所提出的RLFS算法, 将Q学习方法应用于特征选择过程中. 定义初始特征子集为空集, 动作列表中定义了添加和删除两个动作, 分别表示添加一个特征和删除一个特征操作. 结合Wrapper特征选择方法, 使用高斯贝叶斯分类器的在当前状态(特征子集)下的分类准确率作为即时收益. 具体方法如图1所示.

其中步骤A到F所代表的处理过程如下:

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

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

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

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

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

根据以上算法流程, 给出RLFS的算法步骤. 假设原始数据集为X=(X_ij)_N×D, 代表N个样本D个特征, 则样本的类别向量为C=(c_i)_N×1, 样本向量为 (x₁, x₂, …, x_N)^T, 特征向量为(f₁, f₂, …, f_D). 将RLFS算法思想总结为下表所示, 并有以下定义.

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

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

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

4) 将选中要添加的特征称为f_add, 将选中要删除的特征称为f_del;

5) 其中, T←T∪{f_add}表示将T与特征f_add取并集的结果赋值给T, H←H\{f_add}表示将从H中删除特征f_add的结果赋值给H.

RLFS算法主要步骤

输入: 数据集X

输出: 最优特征子集S

1) 初始化当前特征子集T= $\emptyset $ , 候选特征集合为H={f₁, f₂, …, f_D}.

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

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

4) 当T= $\emptyset $ 时, 随机添加一个特征f_add(f_add∈H), T←T∪{f_add}, H←H\{f_add}.

5) 从H∩HS中随机选择一个特征f_add, 计算特征子集T∪{f_add}分类准确率记为R_add. 通过查询PS找到T中特征间相关系数中较大的几对特征, 随机选择几对特征中的一个特征f_del, 计算特征子集T\{f_del}分类准确率记为R_del, 执行R_add和R_del中值较大的那个动作当作此轮决策, 即

　If R_add.>R_del: T←T∪{f_add}, H←H\{f_add}

　If R_add.<R_del: T←T\{f_del}, H←H∪{f_del}

根据公式(4)计算Q值, 并更新Q表.

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

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

本文选用的数据集是UCI Machine Learning Repository^[14]. 在数据挖掘等相关领域中, 常用该数据集验证算法的性能, 现已经成为该领域公认的标准数据集. 实验部分主要使用了其中四个数据集. 各数据集具体的描述信息见表1.

4.2 实验环境

为了验证RLFS算法的有效性, 从Filter、Wrapper方法中选择了3个经典特征选择算法^[6]进行对比, 基于相互关系度量的特征选择算法FCBF、基于支持向量机的递归消除方法SVM-RFE、基于L2正则化的SVM特征选择算法SVM-L2. 以特征选择数量和特征子集的分类准确率作为评价指标进行了两个对比实验.

4.3 实验结果

实验1. 以选择的特征数量作为评价标准进行对比.

通过RLFS、FCBF、SVM-RFE、SVM-L2算法所选取的特征数量信息见表2. 表中Raw列表示数据集原始特征的数量. 此外, Average行统计了各算法在每个数据集所选特征数量的均值.

由表2中的数据对比分析可得, 这五种算法都可以有效地减少特征数量. 观察各算法在数据集所选特征数量的均值, 可以发现FCBF和SVM-L2算法的特征降维效果最为明显, 而基于Wrapper的两种特征选择算法SVM-RFE、RLFS特征降维水平相对较弱, 但RLFS算法的降维能力高于经典的SVM-RFE算法.

实验2.　以特征选择后特征子集的分类准确率作为评价指标进行对比.

为了减少在单一分类器上表现过好或过差而对实验分析产生影响, 在实验中采用KNN(K近邻)、LSVM(线性支持向量机)、朴素贝叶斯、决策树四个经典分类器进行验证. 为了减少过拟合对实验结果的影响, 实验中采用10折交叉验证的平均分类精度的值来评价特征子集优劣. 实验结果记录于表3至表6中, 其中KNN算法中参数K取值为10. 表中数值为10折交叉验证分类准确率均值, 括号内为标准差.

通过表3到表6, 分析可得以下几点:

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

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

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

综合实验1和实验2数据可知, 本文提出的特征选择算法可以明显减少特征数目, 并在此基础上有较高的分类准确率, 在进行实验的四个数据集上本文算法的平均分类准确率均高于FCBF、SVM-RFE、SVM-L2算法.

5 总结

结合Wrapper特征选择方法, 本文提出了基于强化学习的特征选择算法(RLFS), 通过智能体训练学习, 以最大化收益的方式自主决策进行特征选择得到特征子集, 此算法在公开的四个UCI数据集上进行实验, 通过与其它特征选择算法进行对比实验, 发现本算法能够选择较少的特征并获得较高的分类准确率.