基于改进的RAKEL算法的心电图诊断分类

赵静，韩京宇，钱龙，毛毅

基于改进的RAKEL算法的心电图诊断分类

赵静，韩京宇*，钱龙，毛毅

（南京邮电大学 计算机学院，南京 210023）（*通信作者电子邮箱jyhan@njupt.edu.cn）

心电图（ECG）数据通常包含多种病症，而ECG诊断是一个典型的多标签分类问题。在多标签分类方法中，RAKEL算法将标签集随机分解为若干个大小为的子集，并建立LP分类器进行训练；然而由于没有充分考虑标签间的相关性，LP分类器中容易产生一些标签组合所对应样本稀少的情况，从而影响预测性能。为了充分考虑标签间的相关性，提出一种基于贝叶斯网络的RAKEL算法BN-RAKEL。首先利用贝叶斯网络找到标签间的相关性，确定候选标签子集；然后对每个标签采用基于信息增益的特征选择算法确定其最优特征空间，并针对每个候选标签子集利用最优特征空间相似性来检测其相关程度，以确定最终的具有强相关性的标签子集；最后在标签子集的最优特征空间上训练LP分类器。在实际的ECG数据集上，与多标签K近邻（ML-KNN）、RAKEL、CC和基于FP-Growth的RAKEL算法FI-RAKEL进行对比，结果显示所提算法在召回率和F-score上最少提高了3.6个百分点和2.3个百分点。实验结果表明，BN-RAKEL算法有较好的预测性能，能有效提升ECG诊断的准确性。

心电图；多标签；标签相关性；贝叶斯网络；信息增益；特征选择；RAKEL算法

0 引言

根据世界卫生组织的数据，心血管疾病在影响人类健康疾病中高居榜首，为了做到早发现、早治疗，有效的检查方法必不可少，而心电图（ElectroCardioGraph， ECG）是各种心律失常、房室肥大等最常用的检查方法之一［1］。人工识别ECG非常耗时，在长时间的诊断中，可能会出现误判现象，由此，ECG智能诊断技术开始逐渐发展。近十年来，我国的ECG智能诊断取得了长足的进展，但仍然处于初级阶段［2］，目前主要采用机器学习技术来解决［3-4］，通过提取ECG数据特征，自动进行心律异常的识别。通常，一个ECG样本会包含多种病症，比如高血压患者会同时出现左心房肥大、心房颤动、室性期前收缩等问题，是一个典型的多标签分类问题。

目前已有大量的算法用于多标签数据，主要概括为两种思路［5-6］，分别为算法适应和问题转换。算法适应的基本思想是改进算法，使之与多标签数据相适应；问题转换的基本思想是不改变算法，而是将多标签数据转换成单标签数据，使之与现有的算法相匹配，代表性算法有Binary Relevance（BR）［7］、RAndom-labELsets（RAKEL）［8］、Classifier Chains（CC）［9］等。

上述算法中，RAKEL算法通过随机选择标签构建标签子集进行训练，并没有充分考虑标签的相关性，导致对预测性能有一定的影响。因此本文提出了基于贝叶斯网络的RAKEL（Bayesian Network-based RAKEL， BN-RAKEL）算法。从贝叶斯网络的角度，找到相关性高的标签作为RAKEL的候选标签子集；同时利用信息增益对每一个标签选择其最优特征空间，并利用标签的最优特征空间相似性来检测每一个候选标签子集的相关程度，确定最终的标签子集和其对应的最优特征空间；最后针对每个标签子集在其最优特征空间上训练LP（Label Powerset）分类器。

1 相关工作

1.1 多标签算法

多标签数据即一个样本可以同时属于多个标签，并且每一个样本具体的标签数量是不确定的。

1.1.1 算法适应

1.1.2 问题转换

1.2 RAKEL

由于RAKEL算法随机选择标签子集，没有充分考虑标签间相关性，研究者们分别提出了不同的改进算法。如基于聚类的RAKEL算法（LC-RAKEL）［11］的基本思想是通过k-means聚类来找到标签间的相关性选取标签子集；但当标签个数较少且标签间相似性较高时，聚类的效果不明显。PwRAKEL（Pairwise RAndom-labELsets）算法［12］通过考察两两标签间的相关性选取标签子集；但忽略了更多标签之间可能存在关联的情况，具有局限性。基于FP-Growth的RAKEL算法FI-RAKEL［13］则利用FP-growth算法找到频繁项集，将频繁项集中每一个频繁项和原始标签集中部分标签组合，作为标签子集；但该算法容易使大量频繁项和其他原始标签组合构成新的标签子集，其中有些标签组合在训练集中样本稀少造成了资源浪费。

2 基于贝叶斯网络的RAKEL多标签分类算法

2.1 相关概念

2.2 基于贝叶斯网络确定候选标签子集

本文通过贝叶斯网络确定标签间相关性，产生候选标签子集。贝叶斯网络［14-15］是一种概率的图模型，允许表示节点之间的依赖关系。根据贝叶斯网络的有向无环图（Directed Acyclic Graph， DAG）以及条件概率表（Conditional Probability Table， CPT），可以快速得到每个节点与其父节点的所有组合的概率。

确定候选标签子集具体思路如下：

图1 贝叶斯网络DAG

确定候选标签子集具体步骤如算法1。

算法1 BN-RAKEL确定标签子集。

表1 条件概率表例1

表2 条件概率表例2

2.3 挖掘最优特征空间并过滤候选标签子集

本文根据式（5）计算最优特征空间相似性。最优特征空间相似性即针对候选标签子集内标签，共同拥有的最优特征空间个数占该候选标签子集标签的所有最优特征空间的比值，占比越大说明该候选标签子集相似性越强。

根据最优特征空间过滤候选标签子集的具体步骤如下：

3）确定最终标签子集最优特征空间。标签子集内的标签的最优特征空间取并集，构成该标签子集的最优特征空间，并在该标签子集的最优特征空间上训练LP分类器。

算法2描述的是挖掘单个标签最优特征空间，算法3描述的是确定最终标签子集及其最优特征空间并训练LP分类器。

算法2 挖掘单个标签最优特征空间。

算法3 确定最终标签子集及其最优特征空间。

其中：5）～6）行根据最优空间相似性确定是否剔除候选标签子集，确定最终标签子集；7）～11）行在最终标签子集找到其最优特征空间；12）行在最终标签子集的最优特征空间上训练LP分类器。

3 实验与结果分析

3.1 实验数据集

本文使用的数据集来自中国社区卫生服务中心，包含6 000个样本，每个样本包含12个导联10 s记录。经过数据预处理，提取了718个特征，18个标签，标签由两位专业医生给出，下载地址为https：//github.com/hjyresearch228/PAC。

3.2 评价指标

3.3 实验结果与分析

3.3.1 算法性能实验

3.3.2 与其他多标签分类算法对比分析

图3为BN-RAKEL与ML-KNN、CC、FP-RAKEL和RAKEL算法在不同标签数的性能对比结果。从图3可以看出，随着标签数的增多，BN-RAKEL在Accuracy、Recall和F-score均呈逐渐增长趋势。

图2 BN-RAKEL算法在不同阈值下的F-score

图3 不同标签数下不同算法的性能对比

表3是BN-RAKEL在ECG数据集上与其他算法的对比结果。

表3 不同分类算法的评价指标对比

由表3可知，BN-RAKEL在Recall和F-score上都取得了最好效果，分别为0.772和0.681，在Accuracy上仅比CC算法低0.3个百分点；与原RAKEL算法相比，BN-RAKEL算法在Recall和F-score上有明显提升，分别提高了19.0个百分点和6.7个百分点；与FI-RAKEL算法相比也有明显提升，在Recall和F-score上分别提高了3.6个百分点和2.4个百分点。这说明本文提出的BN-RAKEL能够有效挖掘标签间的相关性，有效提升多标签分类问题的预测性能。

4 结语

对于ECG诊断问题，一个样本通常包含多种病症，并且病症之间存在一定的相关性。为了充分利用标签间存在相关性的特点，本文提出了基于贝叶斯网络的RAKEL算法BN-RAKEL。在来自中国社区卫生服务中心数据集上的实验结果表明，与ML-KNN、CC、FP-RAKEL和RAKEL算法相比，BN-RAKEL在Recall和F-score上都取得了最好效果，分别为0.772和0.681，仅在Accuracy上比CC算法少了0.3个百分点。但是在检测标签子集的相关性时，本文方法只考虑了各个标签的共同最优特征空间个数，未来可以考虑如何使用更合适的校验方法来确定最终标签子集。

[1] 程思静，华伟. 心电学指标在预测心脏性猝死中的研究进展［J］. 中国心血管杂志， 2021， 26（6）：505-508.（CHENG S J， HUA W. Electrocardiographic indicators for the prediction of sudden cardiac death： a literature review［J］. Chinese Journal of Cardiovascular Medicine， 2021， 26（6）：505-508.）

[2] 赵梦蝶，孙九爱. 机器学习在心血管疾病诊断中的研究进展［J］. 北京生物医学工程， 2020， 39（2）：208-214.（ZHAO M D， SUN J A. Review on machine learning approaches for cardiovascular disease diagnosis［J］. Beijing Biomedical Engineering， 2020， 39（2）：208-214.）

[3] HU W L， CHEN X H， WANG Y， et al. Arrhythmia recognition and classification using ECG morphology and segment feature analysis［J］. IEEE/ACM Transactions on Computational Biology and Bioinformatics， 2019， 16（1）：131-138.

[4] 王官军，吴婷，汪龙. 基于机器学习的心电图诊断研究［J］. 实用心电学杂志， 2020， 29（4）：262-268， 297.（WANG G J， WU T， WANG L. Research of ECG diagnosis based on machine learning［J］. Journal of Practical Electrocardiology， 2020， 29（4）：262-268， 297.）

[5] ZHANG M L， ZHOU Z H. A review on multi-label learning algorithms［J］. IEEE Transactions on Knowledge and Data Engineering， 2014， 26（8）： 1819-1837.

[6] 李思男，李宁，李战怀. 多标签数据挖掘技术：研究综述［J］. 计算机科学， 2013， 40（4）：14-21.（LI S N， LI N， LI Z H. Multi-label data mining： a survey［J］. Computer Science， 2013， 40（4）：14-21.）

[7] CLARE A， KING R D. Knowledge discovery in multi-label phenotype data［C］// Proceedings of the 2001 European Conference on Principles of Data Mining and Knowledge Discovery， LNAI 2168. Berlin： Springer， 2001：42-53.

[8] TSOUMAKAS G， VLAHAVAS I. Random-labelsets： an ensemble method for multilabel classification［C］// Proceedings of the 2007 European Conference on Machine Learning， LNAI 4701. Berlin： Springer， 2007： 406-417.

[9] DEMBCZYNSKI K， CHENG W W， HÜLLERMEIER E. Bayes optimal multilabel classification via probabilistic classifier chains［C］// Proceedings of the 27th International Conference on Machine Learning. Madison， WI： Omnipress， 2010： 279-286.

[10] ZHANG M L， ZHOU Z H. ML-KNN： a lazy learning approach to multi-label learning［J］. Pattern Recognition， 2007， 40（7）：2038-2048.

[11] 金永贤，张微微，周恩波. 一种改进的RAKEL多标签分类算法［J］. 浙江师范大学学报（自然科学版）， 2016， 39（4）： 386-391.（JIN Y X， ZHANG W W， ZHOU E B. An improved RAKEL method for multilabel classification［J］. Journal of Zhejiang Normal University （Natural Sciences）， 2016， 39（4）： 386-391.）

[12] 周恩波，叶荣华，张微微，等. 一种基于成对标签的Rakel算法改进［J］. 计算机与现代化， 2016（3）：16-18， 23.（ZHOU E B， YE R H， ZHANG W W， et al. An improved Rakel approach based on label pairwise［J］. Computer and Modernization， 2016（3）： 16-18， 23.）

[13] 梁睿博，王思远，李壮，等. 基于RAKEL算法的商品评论多标签分类研究与实现［J］. 软件工程， 2019， 22（1）：8-11.（LIANG R B， WANG S Y， LI Z， et al. Research and implementation of RAKEL algorithm based multi-label classification for online commodity reviews［J］. Software Engineering， 2019， 22（1）：8-11.）

[14] SUCAR L E， BIELZA C， MORALES E F. Multi-label classification with Bayesian network-based chain classifiers［J］. Pattern Recognition Letters， 2014， 41： 14-22.

[15] 张连文，郭海鹏. 贝叶斯网引论［M］. 北京：科学出版社， 2006： 97.（ZHANG L W， GUO H P. Introduction to Bayesian Networks［M］. Beijing： Science Press， 2006： 97.）

[16] 张振海，李士宁，李志刚，等. 一类基于信息熵的多标签特征选择算法［J］. 计算机研究与发展， 2013， 50（6）： 1177-1184.（ZHANG Z H， LI S N， LI Z G， et al. Multi-label feature selection algorithm based on information entropy［J］. Journal of Computer Research and Development， 2013， 50（6）： 1177-1184.）

[17] 张鑫，李占山. 自然进化策略的特征选择算法研究［J］. 软件学报， 2020， 31（12）：3733-3752.（ZHANG X， LI Z S. Research on feature selection algorithm based on natural evolution strategy［J］. Journal of Software， 2020， 31（12）：3733-3752.）

[18] HANCER E. Differential evolution for feature selection： a fuzzy wrapper-filter approach［J］. Soft Computing， 2019， 23（13）：5233-5248.

ECG diagnostic classification based on improved RAKEL algorithm

ZHAO Jing， HAN Jingyu*， QIAN Long， MAO Yi

（，，210023，）

ElectroCardioGram （ECG） data usually contain many diseases， and ECG diagnosis is a typical multi-label classification problem. In RAndom-labELsets （RAKEL） algorithm， one of multi-label classification methods， all labels are randomly decomposed into several labelsets of size， and a Label Powerset （LP） classifier is established for training； however， the lack of sufficient consideration of correlation between labels makes the LP classifier obtain quite few samples corresponding to certain label combinations， which affects the prediction performance. To fully consider the correlation between labels， a Bayesian Network-based RAKEL （BN-RAKEL） algorithm was proposed. Firstly， the correlation between labels was found by Bayesian network to determine the candidate labelsets. Then， a feature selection method based on information gain was applied to construct the optimal feature space for each label， and the optimal feature space similarity was used for each candidate label subset to detect its correlation degree， determing the final labelsets with strong correlation. Finally， the LP classifiers were trained in the optimal feature space of the corresponding labelsets. A comparison with K-Nearest Neighbors for Multi-label Learning （ML-KNN）， RAKEL， Classifier Chains （CC） and FP-Growth based RAKEL algorithm named FI-RAKEL on the real ECG dataset showed that the proposed algorithm achieved a minimum improvement of 3.6 percentage points and 2.3percentage points in recall and F-score， respectively. Experimental results show that BN-RAKEL algorithm has good prediction performance， and can effectively improve the ECG diagnosis accuracy.

ElectroCardioGram (ECG);multi-label; label correlation; Bayesian network; information gain; feature selection; RAndom-labELsets (RAKEL) algorithm

This work is partially supported by National Natural Science Foundation of China （62002174）.

ZHAO Jing， born in 1996， M. S. candidate. Her research interests include machine learning.

HAN Jingyu， born in 1976， Ph. D.， professor. His research interests include machine learning， database.

QIAN Long， born in 1994， M. S. candidate. His research interests include machine learning.

MAO Yi， born in 1985， Ph. D.， lecturer. Her research interests include machine learning， deep learning.

TP391

A

1001-9081（2022）06-1892-06

10.11772/j.issn.1001-9081.2021061068

2021⁃06⁃22；

2022⁃01⁃16；

2022⁃01⁃20。

国家自然科学基金资助项目（62002174）。

赵静（1996—），女，江苏连云港人，硕士研究生，主要研究方向：机器学习；韩京宇（1976—），男，吉林白山人，教授，博士，主要研究方向：机器学习、数据库；钱龙（1994—），男，江苏盐城人，硕士研究生，主要研究方向：机器学习；毛毅（1985—），女，江苏南京人，讲师，博士，主要研究方向：机器学习、深度学习。