RIFS一种随机重启的增量特征选择算法
1. 摘要
大数据时代的到来给机器学习研究者带来了运行时间和学习效率的挑战。生物医学基因组研究就是其中一个大数据领域，它极大地改变了生物医学研究。但是数据生产的高成本和招募参与者的困难将“大p小n”的范式引入到生物医学研究中。特征选择通常用于减少生物医学特征的数量，从而实现一个稳定的数据独立的分类或回归模型。本研究随机改变广泛使用的增量特征选择(IFS)策略的第一个元素，选择可能被统计关联评价算法排序较低的最佳特征子集，如t检验。假设可以通过编排两个低等级的特征来获得较好的分类性能。提出的随机重启动增量特征选择(RIFS)算法比现有算法具有更高的分类精度和更小的特征数。RIFS也优于现有的前列腺恶性肿瘤的甲基体诊断模型，具有更大的准确性和更少的转录组特征。 # 2. 材料和方法 ## 2.1 二元分类问题
本研究利用二值分类性能评估特征子集。一个二值分类问题有两组样本，即正(P)和负(N)样本。P和N也用来表示正样本数和负样本数。二分类问题是最简单的分类模型，通常采用启发式规则求解。这也是生物医学研究者最广泛采用的问题设置，如全基因组关联研究中的疾病对照样本，以及临床生存分析中两种表型的样本等。
2.2 两类特征选择算法
本研究将提出的算法与两大类特征选择算法进行比较。3个过滤器算法，即基于t检验排序(Trank)、假阳性分类率(FPR)和基于wilcox -test排序(Wrank)，在选择与本研究提出的算法相同数量的特征时进行评估。包装器可以直接推荐一组特征，而不需要用户决定特征的数量。本研究将Lasso、Random Forest (RF)和Ridge Regression (Ridge)三种wrappers与RIFS进行比较。因此，本文对这些特征选择算法的分类性能和特征数量进行了研究。其中两个算法，Trank和Wrank，来自Python scipy包，其他所有算法都来自Python scikit-learn包。包装算法可以通过使用不同的参数实现不同的效果。假设包装器算法的默认参数在大多数情况下都能正常工作。为了进行公平比较，在ALL1/ALL2/ALL3/ALL4四个数据集上对RIFS的参数进行了优化，本研究在所有17个转录组数据集上对RIFS与现有算法进行了综合比较。Lasso参数Alpha设置为0.1。特征选择算法的其他参数都使用默认值。
2.3 性能度量
采用三种广泛使用的指标来评价二值分类器的预测性能，即灵敏性(Sn)、特异性(Sp)、准确性(Acc)和F-score。让正确预测的阳性样本的数量为TP(真阳性)，其余的数量为FN(假阴性)。同样，正确预测的负样本的数量定义为TN(真阴性)，而假阳性样本的数量定义为FP。在本例中，敏感性计算为Sn = TP/ (TP + FN)，特异性定义为Sp = TN/ (TN + FP)。整体精度Acc公式为Acc = (TP + TN)/(TP + FN + TN + FP)。F-score也被称为F-measure或F1-score，广泛用于评价二值分类模型的性能。F-score被定义为2×(Precision×Sn) /(Precision+Sn),Precision=TP / (TP+FP)。
在数据集上对五种具有代表性的分类算法进行评价，并将这五种算法在数据集特征子集上所达到的最大精度定义为最大精度mAcc。支持向量机(SVM)是一种流行的二分类算法。K近邻(K Nearest Neighbors, KNN)算法是一种直观的基于距离的分类算法。决策树(DTree)将生成一个易于解释的分类器。朴素贝叶斯分类器(NBayes)假设所有的特征都是相互独立的。Logistic回归(LR)训练一个线性分类函数，它可以提示所选特征的权重。
所有的算法都在两个主要的Python版本(即2.7.13和3.6.0)下测试。
2.4 生物医学数据集
本研究选择了17个转录组数据集进行测试。这17个转录组数据集都是广泛使用和公开的。包括DLBCL、Pros、Colon、Leuk、Mye、ALL1、ALL2、ALL3、ALL4、CNS、Lym、Adeno、Gas,、Gas1、Gas2 、T1D和Stroke。
2.5 RIFS一种随机重新启动的增量特征选择算法
对增量特征选择算法进行改进，使其具有起始位置k和连续性能下降截止点D，记为算法sIFS(k, D)。对于具有n个特征和m个样本的二分类问题，根据特征与类标签的关联显著性对特征进行排序。特征与类标签的关联显著性由t-test的统计显著性P值计算,并根据p值排序，特征被记为fi , i∈{1 2n}。该算法将连续向特征子集中添加下一个元素，直到二分类精度连续下降D次。算法sIFS(k, D)的伪代码如下所示。
随机重启增量特征选择(RIFS)算法基于单元算法sIFS (k, D)。假设多个sIFS(k, D)算法可以生成一个比经典算法有更好的分类精度的特征子集。RIFS的伪代码如下所示。
## 2.6 随机种子k-fold交叉验证
利用k折交叉验证策略计算总体分类性能。数据集被随机分割成k折，并使用每一折来验证从剩下的k−1折训练出来的模型。KFCV将P和N分别随机分成k个大小相等的子集，给定一个具有正样本和负样本的二值分类数据集。P={P1, P2,Pk}和N={N1、N2,Nk}。迭代地选择Pi∪Ni作为测试数据集，其他样本作为给定分类算法的训练数据。基于这一轮迭代计算分类性能度量值Sn、Sp和Acc。
RIFS使用增量规则从给定的起始特征中选择特征，只保留分类性能最好的特征子集供进一步分析。由于不同的数据拆分会产生不同的分类性能，因此会使用多个随机种子来产生KFCV计算。为了消除过拟合和随机分割的影响，本研究进行了10折交叉验证，在SVM、KNN、DTree、NBayes和LR五个分类器中选择分类精度最大的分类器。
2.7 实验过程
将RIFS与六种主要的特征选择算法(即三种过滤器和三种包装器)进行比较。性能度量采用10倍交叉验证的方法计算，在SVM、KNN、DTree、NBayes和LR五种分类算法中，分类精度mAcc为5种分类器的最大值。具体过程如图1所示。
3.结果和讨论
3.1 IFS策略的两个优化规则
本研究基于实验数据对增量特征选择(IFS)策略提出了两种假设修改，如图2所示。优化目标是利用所选特征子集最大化二分类精度。通过一轮10倍交叉验证来计算此演示步骤中的分类性能。
随机重新启动IFS策略。将经典版的IFS归纳为IFS(i)， IFS(i)从第i个等级开始选择一个连续排列的特征子集，假设可能存在一个分类精度优于IFS(0)的特征子集IFS(i)。图2(a)中的两个例子支持了这一假设。排名31和32的两个特征在ALL2数据集上的整体准确率达到了79.5%，优于IFS(0)排名前两的特征的准确率77.0%，如图2所示。在数据集ALL3中，排名为443、444、445和446的四个特征的准确率比排名前四的特征高1.3%。以p值衡量，这四个低阶特征的统计学显著性分别为0.036990、0.036994、0.037100和0.037105。因此，可以通过随机重新启动规则来改进IFS策略。
停在一次下降不太好。观察到添加两个连续排列的特征可以大幅度提高分类性能，即使添加第一个特征会降低分类性能。例如，特征筛选过程IFS(37)在添加第四个特征(排名40)时，对数据集冒号的准确率第一次下降(1.5%)。而IFS(37)与加入第四个特征前相比，准确率也提高了1.4%，如图2(b)所示。另一种情况是数据集T1D的特征筛选过程IFS(757)，如图2(c)所示。第3个特征的融合降低了1.3%的准确率，但第2个特征(第760位)的融合提高了5.4%的准确率，也比第2个连续排序的特征757和758的准确率高出4.1%。因此，IFS(i)的停止策略需要至少容忍一次精度下降。
对大多数数据集来说，多少个起始点是足够的?我们使用ALL1/ALL2/ALL3/ALL4这四个数据集来研究RIFS的最佳起始点数。选择起始点的数量进行评估,即pStartingPercentage分别为总特征数的15%,25%,35%,45%,55%。通过一轮10倍交叉验证计算了该参数优化步骤的分类性能。最终决定参数pStartingPercentage的默认值为45%。
对连续精度下降的容忍度有多大就足够了?贪婪特征选择算法在特征筛选过程中，当优化目标降低时往往会停止，例如经典的IFS策略。本文的假设是，在分类性能略有下降后，添加下一个特征可能会获得更好的整体性能提升。
评估了rif停止标准pStoppingDepth分别等于1,2,3,4和5,即rif当检测到连续pStoppingDepth性能降低时停止。选取ALL1/ALL2/ALL3/ALL4四个数据集进行评价。参数pStartingPercentage设置为10%、20%、30%、40%和50%，通过10倍交叉验证策略进行性能度量为mAcc。通过一轮10倍交叉验证计算了该参数优化步骤的分类性能。图3显示，对于使用pStartingPercentage的5个值的所有4个数据集，当pStoppingDepth达到4时，RIFS获得了最佳mAcc。因此，实验数据支持了本文的假设，即在检测到性能下降后立即停止可能不是最佳选择。pStoppingDepth的默认值为4。
RIFS的综合评价与默认参数值pStartingPercentage =45%，pStoppingDepth=4进行了17个转录组数据集,如图4所示。通过20轮随机10倍交叉验证计算下列比较分析步骤的分类性能。对于这些数据集，RIFS在mAcc中达到了至少0.804，甚至在17个数据集中的6个在mAcc中达到了1.000。
