第4期 李顺勇，等：一种新的最大相关最小冗余特征选择算法 ·651· 原始数据集 为相关度的度量准则。 1.3目标函数 数据预处理 基于特征选择和聚类的众多分类算法中，目 标函数常采用加权的信息差方式，并且通过对权 训练集 测试集 重信息不断赋值来求解最优特征子集，不能根据 不同用户实际需求的维度求解最优特征子集。因 冗余度评价函数 相关度评价函数 此，本文提出了一种新的目标函数，引入了一个 指示向量1以及参数k来表示所选的特征维度。 Fisher Score pearson相关系数 NHWN-MON 具体目标函数如下： Information Gain 互信息 Chi-square Test (AD ACA Laplacian Score mk依-)st∑=k4e0,山 式中：k为用户需求的实际数据维度；D为冗余度 带有指示向量的 用户需求维度的 矩阵；C为特征与类别之间的相关性矩阵。 目标函数 特征子集 A=12…J',n为原始特征集的特征数。当 取值为0时，说明对应的特征不会被选择进最终 最优特征子集 的特征子集，取值越大时，表明其对应的特征越 图1New-MRMR特征选择流程 容易被选进最终的特征子集。 Fig.1 New-MRMR feature selection flow 对于该目标函数的求解，与最优化标准二次 1.1冗余度评价准则 规划问题21相似，本文采用成对更新方法网来求 特征选择是为了去除原始特征集中的冗余特 解以上目标函数的最优解。 征，达到降维目的。因此，利用冗余度评价可以 2实验结果与分析 作为New-MRMR特征选择算法的一部分，其基 本思想是：两个特征的相关度越大，则这两个特 2.1数据集信息及评价指标 征冗余度也越高。但是，由于评价特征之间冗余 为验证New-MRMR算法的有效性，本文使用 度以及特征与类别之间相关度的准则众多，且目 了4个真实的UCI数据集。先利用新提出的算法 前缺乏相关研究给出具体哪种方法更适用于哪种 处理原始特征，进而使用支持向量机对所得到的 数据类型。所以，本文新提出的算法仅采用了 特征子集进行分类实验，最后比较各种算法在测 Pearson相关系数4以及互信息两种准则来度 试集上的分类准确率(classification precision, 量特征之间的冗余度。 CP)。相关定义如下： 1.2相关度评价准则 CC CP= ×100% 在特征选择过程中，通常优先选择与类别相 Num 关度较大的特征，而特征的重要度在一定程度上 式中：CC(correct classification,CC)为正确分类的 反映了与类别的相关度大小，因此，相关度的度 样本数量；Num为样本数量总数。 量准则就转化成了特征重要度的衡量。衡量特征 表1为4个UC2数据集的具体信息： 重要度的评价准则有很多，例如：Fisher scorem、信 表1实验数据集 息增益((information gain,IG)、Laplacian Scor Table 1 Experimental data set Chi--squar Test-2等。Fisher score主要是按照类 数据集 特征数样本数 测试集 训练集 内距离小，类间距离大的原则，选出包含鉴别信 isolet 617 7797 2599 5198 息比较多的特征，其值越大，说明该特征越重要， waveform 40 5000 1666 3334 与类别的相关度越大；信息增益是通过计算某特 clean 168 476 158 318 征被使用前后的信息嫡来为该特征进行打分，信 Parkinson's Disease 754 756 252 504 息增益越大，说明该特征越重要，与类别的相关 度越大；Laplacian Score是根据拉普拉斯特征映射 实验中，与新提算法进行对比的特征选择算 等对单个特征评分，然后选出方差和局部几何结 法分别是：Fisher Score、基于Information Gain的 构保持能力较强的特征，其分值越高，特征越重 方法、基于Laplacian Score的方法、基于Chi-squar 要。New-MRMR算法也采用这4种评价准则作 Test的方法、基于MRMR的方法。表2列出了以原始数据集 数据预处理 训练集 测试集 冗余度评价函数 相关度评价函数 Fisher Score Information Gain Chi-square Test Laplacian Score pearson 相关系数 互信息 带有指示向量的 目标函数 用户需求维度的 特征子集 最优特征子集 New-MRMR 图 1 New-MRMR 特征选择流程 Fig. 1 New-MRMR feature selection flow 1.1 冗余度评价准则 特征选择是为了去除原始特征集中的冗余特 征，达到降维目的。因此，利用冗余度评价可以 作为 New-MRMR 特征选择算法的一部分，其基 本思想是：两个特征的相关度越大，则这两个特 征冗余度也越高。但是，由于评价特征之间冗余 度以及特征与类别之间相关度的准则众多，且目 前缺乏相关研究给出具体哪种方法更适用于哪种 数据类型。所以，本文新提出的算法仅采用了 Pearson 相关系数[14] 以及互信息[14] 两种准则来度 量特征之间的冗余度。 1.2 相关度评价准则 在特征选择过程中，通常优先选择与类别相 关度较大的特征，而特征的重要度在一定程度上 反映了与类别的相关度大小，因此，相关度的度 量准则就转化成了特征重要度的衡量。衡量特征 重要度的评价准则有很多，例如：Fisher score[7] 、信 息增益 (information gain，IG)[8] 、Laplacian Score[20] 、 Chi-squar Test[21-22] 等。Fisher score 主要是按照类 内距离小，类间距离大的原则，选出包含鉴别信 息比较多的特征，其值越大，说明该特征越重要， 与类别的相关度越大；信息增益是通过计算某特 征被使用前后的信息熵来为该特征进行打分，信 息增益越大，说明该特征越重要，与类别的相关 度越大；Laplacian Score 是根据拉普拉斯特征映射 等对单个特征评分，然后选出方差和局部几何结 构保持能力较强的特征，其分值越高，特征越重 要。New-MRMR 算法也采用这 4 种评价准则作 为相关度的度量准则。 1.3 目标函数 λ 基于特征选择和聚类的众多分类算法中，目 标函数常采用加权的信息差方式，并且通过对权 重信息不断赋值来求解最优特征子集，不能根据 不同用户实际需求的维度求解最优特征子集。因 此，本文提出了一种新的目标函数，引入了一个 指示向量 以及参数 k 来表示所选的特征维度。 具体目标函数如下： max λ ( λ T D k − λ TCλ k(k−1)) ,s.t. ∑ λi = k, λi ∈ [0,1] λ =[λ1 λ2 ··· λn] T λi λi 式中：k 为用户需求的实际数据维度；D 为冗余度 矩阵； C 为特征与类别之间的相关性矩阵。 ，n 为原始特征集的特征数。当 取值为 0 时，说明对应的特征不会被选择进最终 的特征子集， 取值越大时，表明其对应的特征越 容易被选进最终的特征子集。 对于该目标函数的求解，与最优化标准二次 规划问题[23] 相似，本文采用成对更新方法[24] 来求 解以上目标函数的最优解。 2 实验结果与分析 2.1 数据集信息及评价指标 为验证 New-MRMR 算法的有效性，本文使用 了 4 个真实的 UCI 数据集。先利用新提出的算法 处理原始特征，进而使用支持向量机对所得到的 特征子集进行分类实验，最后比较各种算法在测 试集上的分类准确率 (classification precision， CP)。相关定义如下： CP = CC Num ×100% 式中：CC(correct classification，CC) 为正确分类的 样本数量；Num 为样本数量总数。 表 1 为 4 个 UCI[25] 数据集的具体信息: 表 1 实验数据集 Table 1 Experimental data set 数据集 特征数 样本数 测试集 训练集 isolet 617 7797 2 599 5 198 waveform 40 5000 1 666 3 334 clean 168 476 158 318 Parkinson's Disease 754 756 252 504 实验中，与新提算法进行对比的特征选择算 法分别是：Fisher Score、基于 Information Gain 的 方法、基于 Laplacian Score 的方法、基于 Chi-squar Test 的方法、基于 MRMR 的方法。表 2 列出了以 第 4 期 李顺勇，等：一种新的最大相关最小冗余特征选择算法 ·651·