McTwo 一个基于最大信息系数的两步特征选择算法

Posted on Edited on

McTwo:一个基于最大信息系数的两步特征选择算法

  1. 摘要：

高通量生物组学技术正以越来越快的速度从生物样本中产生高维数据，而传统实验的训练样本数量由于各种困难而一直处于较小的水平。这种生物医学“大数据”领域的“大p，小n”范式，可以通过特征选择算法部分解决。然而特征选择是一个np困难的问题，寻找全局最优解的时间要求呈指数增长。本文描述了一种基于最近发表的相关度量最大信息系数(MIC)的特征选择算法。所提出的算法McTwo的目的是选择与表型相关且彼此独立的特征。基于对17个数据集的比较研究，McTwo的性能与现有算法相当，甚至更好，所选特征的数量明显减少，更是与文献中的表型有特定的生物医学相关性。

2. 介绍

由于收集特定类型样本非常困难，传统生物学研究只能收集少量样本。然而，随着现代生物技术的发展，可能会产生大量的生物医学“大数据”用于单个样本。这就导致了生物大数据中“大p小n”范式的挑战，这是深度学习策略所无法解决的。一个“大p小n”数据集通常有几十个或最多几百个样本，每个样本有数百万个或更多的特征。如果将所有特征都用于这些样本的分类或回归建模，将会导致过度拟合。

本文提出了一种新的基于最大信息系数的包装器特征选择算法McTwo。McTwo的第一步是筛选出具有显著区分能力且互相不冗余的特征，以便进一步筛选。然后利用最优优先搜索策略寻找分类性能最优的特征子集。实验数据表明，该算法在大多数情况下都优于其他算法，显著减少了特征数量。

3.方法

  • 二分类问题及其性能度量

本文研究了二元分类问题。一个二元分类问题有两组样本，正(P)集和负(N)集。P ={P1, P2，…，Pn}， N ={N1, N2，…，Nm}。正、负样本的个数也分别简写为P = n和N = m。样本总数为s，每个样本X∈P∪N是一个具有k个特征的向量。

敏感性(Sn)、特异性(Sp)和精确度(Acc)被广泛用于衡量二分类模型的执行情况。Sn定义为正确预测阳性样本数占正确预测样本数的比例，Sp定义为正确预测阴性样本数占正确预测样本数的比例。模型的总体精度定义为正确预测样本数占总样本数比例。

所有的分类算法都使用5次内部交叉验证来评估它们的总体性能。Acc值越大的二分类算法性能越好。如果两个模型的性能相似，则首选更简单的模型。

  • 本研究使用的生物医学数据集

本研究使用17个二元分类数据集进行分类性能评价，两个被广泛研究的数据集:结肠癌和白血病分别来自于R/Bioconductor packages colonCA和golubEsets。六个公开的数据集，即DLBCL，前列腺，ALL，CNS，淋巴瘤和腺瘤，从布罗德研究所基因组数据分析中心下载，可在http://www.broadinstitute.org/cgi-bin/cancer/datasets.cgi获得。根据表1所示的不同表现型注释，将数据集进一步处理成ALL1、ALL2、ALL3、ALL4四种二元分类数据集。另外5个新数据集，即骨髓瘤(登录:GDS531)、胃癌(登录:GSE37023)、Gastric1/Gastric2(登录:GSE29272)、T1D(登录:GSE35725)和中风(登录:GSE22255)，从NCBI基因表达综合(GEO)数据库中下载。

将NCBI GEO数据库的原始数据规格化为RMA算法的默认参数的基因表达矩阵，其他所有数据集作为规格化数据矩阵下载

  • 基于最大信息系数的特征筛选(McOne)
img

最大信息系数(MIC)检验两个变量之间的依赖关系以及它们是否具有线性关系或其他函数关系。测量MIC是对称的，并归一化到一个范围[0,1]。MIC值高表示被检查变量之间的相关性高，MIC = 0表示两个变量之间没有相关性。

一种基于MIC的过滤步骤McOne，用于去除与表型关系不大或与特征子集中剩余的其他特征存在冗余的特征。首先，定义一些术语。对于一个给定的二分类问题，类标签C ={C1, C2，…，Cs}，Ci∈{P, N}，每个样本都有k个特征<F1(X)， F2(X)，…，Fk(X)>，其中Fj是第j个特征。

定义: 信息相关特征:S ={Fi |MIC(Fi, C) > r}，其中r为预先设置的不相关阈值。

定义: 信息冗余特征Fi冗余的，如果存在另一个特征Fj, s.t.MIC(Fj,C) >MIC(Fi,C)和MIC(Fj,Fi) >MIC(Fi,C)。

信息优势准则: 如果特征Fj在候选特征子集MIC(Fj,Fi) >MIC(Fi,C)中与目标变量C的信息相关度最大，且与已经选择的特征不存在冗余，则保留特征Fj。

  • McTwo算法

采用最佳优先搜索策略来进一步减少特征数量。实验数据表明，McOne选择的特征子集具有令人满意的分类性能。然而，McOne可能会选择几十个甚至上百个特征，这依旧可能会导致一些大数据领域出现过拟合问题。因此使用最佳优先搜索策略进一步减少特征的数量。

首次搜索过程中，采用KNN算法作为嵌入分类器。虽然KNN是一个非常简单的分类器，但是它具有计算速度快和参数独立性的优点。

再以leave-one-out (LOO)验证策略计算得到的平衡精度BAcc = (Sn + Sp)/2为优化目标。

  • McTwo2的时间复杂度分析

McOne需要计算所有特征之间的MIC值，以及针对类标签的特征。设p和n分别为特征个数和样本个数，McOne运行的时间复杂度为O(p2+p)~O(p2)。McTwo的第二步理论上需要过滤掉McOne过滤掉的所有剩余的特征，即是O(p)。因此，最坏情况下mc2的时间复杂度为O(p2 + p) + O(p) ~ O(p2+2p) ~ O(p2)，与特征选择算法FCBF相同。但是为了评估特征和类标签之间的MIC值，通常会采用过滤步骤McOne，这通常会排除大部分的特征。这样可以显著加快特征间MIC值的评估。因此，实际计算时间在大多数情况下不会达到上限O(p2)。

  • 特征选择性能比较分析

本实验中与其他常用的特征选择算法进行了一系列综合比较实验，从分类精度和选择特征个数两个方面进行了比较。将PAM和RRF这两种包装算法与TRank、WRank和RocRank这三种广泛使用的过滤算法进行比较。

根据上述特征选择算法所选择的特征，选择了一些有代表性的分类算法来构建二分类模型：支持向量机(SVM)，朴素贝叶斯(Naive Bayes, NBayes)，决策树(DTree)，K近邻(KNN，K = 1)。过程如图一所示：

img
  1. 实验结论

1.McTwo与McOne的比较结果如图所示

img

2.McTwo与CFS,PAM,RRF的比较如图所示

img