融合信息增益比和遗传算法的混合式特征选择算法-许召召，申德荣，聂铁铮，寇月.pdf

上善若水

418

13页

0次

2022-05-19

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software, 2022,33(3):1128−1140 [doi: 10.13328/j.cnki.jos.006099] http://www.jos.org.cn

融合信息增益比和遗传算法的混合式特征选择算法

∗

许召召

申德荣

聂铁铮

寇

月

(东北大学计算机科学与工程学院, 辽宁沈阳 110819)

通信作者: 许召召, E-mail: zhaozhaotoms@foxmail.com

摘要: 随着信息技术以及电子病历和病案在医疗机构的应用, 医院数据库产生了大量的医学数据. 决策树因其

分类精度高、计算速度快, 且分类规则简单、易于理解, 而被广泛应用于医学数据分析中. 然而, 医学数据固有的

高维特征空间和高度特征冗余等特点, 使得传统的决策树在医学数据上的分类精度并不理想. 基于此, 提出了一

种融合信息增益比排序分组和分组进化遗传算法的混合式特征选择算法(GRRGA). 该算法首先使用基于信息增

益比的过滤式算法对原始特征集合进行排序, 然后按照密度等分的原理对排序后的特征进行分组, 最后再使用分

组进化遗传算法对排序后的特征组进行遗传搜索. 其中, 分组进化遗传算法共分为种群内和种群外两种进化方法,

并使用两种不同的适应度函数来控制进化过程. 此外, 针对决策树的不稳定性, 提出使用 Bagging 方法对 C4.5 算

法进行集成学习. 实验结果显示, GRRGA 算法在 6 组 UCI 数据集上的 Precision 指标均值为 87.13%, 显著优于传

统的特征选择算法. 此外, 与另外两种分类算法对比可知, GRRGA 算法的特征筛选性能依然是最优的. 更重要的

是, Bagging 方法在 Arrhythmia 和 Cancer 医学数据集上的 Precision 指标分别为 84.7%和 78.7%, 充分证明了该算法

的实际应用意义.

关键词: 医学数据; 决策树; 特征选择; 遗传算法; 信息增益比

中图法分类号: TP18

中文引用格式: 许召召, 申德荣, 聂铁铮, 寇月. 融合信息增益比和遗传算法的混合式特征选择算法. 软件学报, 2022,

33(3): 1128−1140. http://www.jos.org.cn/1000-9825/6099.htm

英文引用格式: Xu ZZ, Shen DR, Nie TZ, Kou Y. Hybrid feature selection algorithm combining information gain ratio and

genetic algorithm. Ruan Jian Xue Bao/Journal of Software, 2022, 33(3): 1128−1140 (in Chinese). http://www.jos.org.cn/1000-

9825/6099.htm

Hybrid Feature Selection Algorithm Combining Information Gain Ratio and Genetic

Algorithm

XU Zhao-Zhao, SHEN De-Rong, NIE Tie-Zheng, KOU Yue

(School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China)

Abstra ct : In recent years, the application of information technology and electronic medical records and medical records in medical

institutions has become more and more widespread, which has resulted in a large amount of medical data in hospital databases. Decision

tree is widely used in medical data analysis because of its high classification precision, fast calculation speed, and simple and easily

understood classification rules. However, due to the inherent high dimensional feature space and high feature redundancy of medical data,

the classification precision of traditional decision trees is low. Based on this, this paper proposes a hybrid feature selection algorithm

(GRRGA) that combines information gain ratio ranking grouping and group evolution genetic algorithm. Firstly, the information gain

ratio based filtering algorithm is used to sort the original feature set; then, the ranked features are grouped according to the density

principle of equal division; finally, a group evolution genetic algorithm is used to perform a search on the ranked feature groups. There are

two kinds of evolution methods: in-population and out-population, which use two different fitness functions to control the evolution

∗ 基金项目: 国家自然科学基金(62172082，62072084, 62072086); 国家重点研发计划(2018YFB1003404)

收稿时间: 2020-01-23; 修改时间: 2020-03-09; 采用时间: 2020-04-09

许召召等: 融合信息增益比和遗传算法的混合式特征选择算法

1129

process in group evolution genetic algorithm. The experimental results show that the average precision index of the GRRGA algorithm on

the six UCI datasets is 87.13%, which is significantly better than the traditional feature selection algorithm. In addition, compared with

the other two classification algorithms, the feature selection performance of the GRRGA algorithm proposed in this study is optimal. More

importantly, the precision index of the bagging method on the arrhythmia and cancer medical datasets is 84.7% and 78.7% respectively,

which fully proves the practical application significance of the proposed algorithm.

Key words: medical data; decision tree; feature selection; genetic algorithm; information gain ratio

随着信息技术以及电子病历和病案在医疗机构的广泛应用, 使得医院数据库产生了大量的医学数据

[1,2]

这些医学数据对于疾病的诊断、治疗和医学研究都是十分有价值的

[3]

. 决策树作为一种经典的分类算法, 因其

分类精度高、运算速度快, 尤其是分类规则简单、易于理解, 而被广泛应用于医学数据分析中

[4]

. 然而, 由于

医学数据所固有的高维特征空间和高度特征冗余等特点

[5,6]

, 使得决策树在医学数据上的分类效果并不

理想

[7]

特征选择

[8,9]

是指从一组原始特征集合中筛选出最优的特征子集, 以达到降低特征维度和提升分类精度

的目的. 根据是否与分类算法

[10]

有关, 可将特征选择算法分为过滤式(filter)、封装式(wrapper)和混合式

(hybrid)这 3 种. 信息增益比

[11]

是一种经典的过滤式算法, 特征的信息增益比越大, 其包含的信息量也越大.

因此, 通过设置阈值来筛选信息增益比高于阈值的特征子集. 然而, 基于信息增益比的过滤式算法得到的特

征子集辨识度较差

[12,13]

. 此外, 过滤式算法的阈值设定也具有一定的盲目性

[14]

封装式算法

[15]

需要嵌入分类算法, 通过对原始特征集合进行搜索, 并使用分类算法作为评估算法. 遗传

算法

[16]

是一种常见的搜索算法, 适合对较大特征空间数据进行搜索, 不需要评估算法具有单调性, 因此常被

用于高维特征空间数据的特征选择中

[17]

. 但有研究表明

[18]

: 遗传算法容易陷入局部最优解, 出现“早熟”现象.

引起这种现象的主要原因是: 在进化初期, 群体中个体的多样性迅速降低, 使得算法过早收敛, 从而可能丢

失一些有意义的搜索点和最优点, 而陷入局部最优.

由于过滤式算法和封装式算法各有优缺点, 因此有学者

[19]

提出将两种算法融合使用, 不仅可以节约时间,

而且提升了候选特征子集的辨识度. 混合式算法一般由两个阶段组成: 首先, 使用基于信息增益比的过滤式

算法

[11]

剔除大部分冗余特征, 只保留少量特征, 从而有效地缩减了后续启发式算法的搜索规模; 然后, 将过

滤式筛选的特征子集连同样本作为输入参数传递给基于遗传搜索的封装式算法

[17]

, 以进一步筛选更重要的特

征. 虽然混合式算法可以有效地克服过滤式和封装式的缺点. 然而, 过滤式阶段的阈值设定以及遗传算法的

局部最优解等问题仍然需要解决

[12−14,18]

基于上述描述, 本文提出一种融合信息增益比排序分组和分组进化遗传算法的混合式特征选择算法

(GRRGA). 该算法主要分为 3 部分: 首先, 使用基于信息增益比的过滤式算法计算原始特征的信息增益比, 按

照信息增益比的大小对原始特征进行排序; 然后对排序后的特征进行分组, 按照密度等分的方法对排序后的

特征进行分组; 最后, 再使用基于分组进化遗传的封装式算法对排序后的特征组进行搜索, 按照种群内和种

群外两种评估方法来筛选特征, 使用 C4.5 算法作为封装式算法中的评估算法. 此外, 本文使用集成方法对

C4.5 算法进行集成学习, 以降低 C4.5 算法的不稳定性. 在实验方面: 首先是本文所提 GRRGA 算法的验证实

验, 通过在 6 组 UCI 数据集上将 GRRGA 算法与传统的特征选择算法进行对比实验, 以验证 GRRGA 算法的

优越性; 然后, 使用集成方法对 C4.5 算法进行集成学习, 选择最优的集成方法作为应用实验的应用算法; 最

后, 将本文所提 GRRGA 算法应用于 2 组 UCI 医学数据集上, 取得了实际的应用意义.

1 相关工作

特征选择是一种数据降维算法, 通过对高维特征空间数据进行搜索, 并使用评估算法对搜索的子集进行

评估, 从而筛选出最优的特征子集. 过滤式和封装式的区别在于评估方法的不同

[20]

, 而混合式则融合了两者

的优点. 分别总结如下.

过滤式算法通过某种评估算法来增强特征与类别的相关性, 削减特征与特征之间的相关性. 常见的过

of 13

免费下载

软件学报计算机技术

关注

评论