基于改進(jìn)的RAKEL算法的心電圖診斷分類

趙靜，韓京宇，錢龍，毛毅

基于改進(jìn)的RAKEL算法的心電圖診斷分類

趙靜，韓京宇*，錢龍，毛毅

（南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，南京 210023）（*通信作者電子郵箱jyhan@njupt.edu.cn）

心電圖（ECG）數(shù)據(jù)通常包含多種病癥，而ECG診斷是一個(gè)典型的多標(biāo)簽分類問題。在多標(biāo)簽分類方法中，RAKEL算法將標(biāo)簽集隨機(jī)分解為若干個(gè)大小為的子集，并建立LP分類器進(jìn)行訓(xùn)練；然而由于沒有充分考慮標(biāo)簽間的相關(guān)性，LP分類器中容易產(chǎn)生一些標(biāo)簽組合所對應(yīng)樣本稀少的情況，從而影響預(yù)測性能。為了充分考慮標(biāo)簽間的相關(guān)性，提出一種基于貝葉斯網(wǎng)絡(luò)的RAKEL算法BN-RAKEL。首先利用貝葉斯網(wǎng)絡(luò)找到標(biāo)簽間的相關(guān)性，確定候選標(biāo)簽子集；然后對每個(gè)標(biāo)簽采用基于信息增益的特征選擇算法確定其最優(yōu)特征空間，并針對每個(gè)候選標(biāo)簽子集利用最優(yōu)特征空間相似性來檢測其相關(guān)程度，以確定最終的具有強(qiáng)相關(guān)性的標(biāo)簽子集；最后在標(biāo)簽子集的最優(yōu)特征空間上訓(xùn)練LP分類器。在實(shí)際的ECG數(shù)據(jù)集上，與多標(biāo)簽K近鄰（ML-KNN）、RAKEL、CC和基于FP-Growth的RAKEL算法FI-RAKEL進(jìn)行對比，結(jié)果顯示所提算法在召回率和F-score上最少提高了3.6個(gè)百分點(diǎn)和2.3個(gè)百分點(diǎn)。實(shí)驗(yàn)結(jié)果表明，BN-RAKEL算法有較好的預(yù)測性能，能有效提升ECG診斷的準(zhǔn)確性。

心電圖；多標(biāo)簽；標(biāo)簽相關(guān)性；貝葉斯網(wǎng)絡(luò)；信息增益；特征選擇；RAKEL算法

0 引言

根據(jù)世界衛(wèi)生組織的數(shù)據(jù)，心血管疾病在影響人類健康疾病中高居榜首，為了做到早發(fā)現(xiàn)、早治療，有效的檢查方法必不可少，而心電圖（ElectroCardioGraph， ECG）是各種心律失常、房室肥大等最常用的檢查方法之一［1］。人工識別ECG非常耗時(shí)，在長時(shí)間的診斷中，可能會出現(xiàn)誤判現(xiàn)象，由此，ECG智能診斷技術(shù)開始逐漸發(fā)展。近十年來，我國的ECG智能診斷取得了長足的進(jìn)展，但仍然處于初級階段［2］，目前主要采用機(jī)器學(xué)習(xí)技術(shù)來解決［3-4］，通過提取ECG數(shù)據(jù)特征，自動進(jìn)行心律異常的識別。通常，一個(gè)ECG樣本會包含多種病癥，比如高血壓患者會同時(shí)出現(xiàn)左心房肥大、心房顫動、室性期前收縮等問題，是一個(gè)典型的多標(biāo)簽分類問題。

目前已有大量的算法用于多標(biāo)簽數(shù)據(jù)，主要概括為兩種思路［5-6］，分別為算法適應(yīng)和問題轉(zhuǎn)換。算法適應(yīng)的基本思想是改進(jìn)算法，使之與多標(biāo)簽數(shù)據(jù)相適應(yīng)；問題轉(zhuǎn)換的基本思想是不改變算法，而是將多標(biāo)簽數(shù)據(jù)轉(zhuǎn)換成單標(biāo)簽數(shù)據(jù)，使之與現(xiàn)有的算法相匹配，代表性算法有Binary Relevance（BR）［7］、RAndom-labELsets（RAKEL）［8］、Classifier Chains（CC）［9］等。

上述算法中，RAKEL算法通過隨機(jī)選擇標(biāo)簽構(gòu)建標(biāo)簽子集進(jìn)行訓(xùn)練，并沒有充分考慮標(biāo)簽的相關(guān)性，導(dǎo)致對預(yù)測性能有一定的影響。因此本文提出了基于貝葉斯網(wǎng)絡(luò)的RAKEL（Bayesian Network-based RAKEL， BN-RAKEL）算法。從貝葉斯網(wǎng)絡(luò)的角度，找到相關(guān)性高的標(biāo)簽作為RAKEL的候選標(biāo)簽子集；同時(shí)利用信息增益對每一個(gè)標(biāo)簽選擇其最優(yōu)特征空間，并利用標(biāo)簽的最優(yōu)特征空間相似性來檢測每一個(gè)候選標(biāo)簽子集的相關(guān)程度，確定最終的標(biāo)簽子集和其對應(yīng)的最優(yōu)特征空間；最后針對每個(gè)標(biāo)簽子集在其最優(yōu)特征空間上訓(xùn)練LP（Label Powerset）分類器。

1 相關(guān)工作

1.1 多標(biāo)簽算法

多標(biāo)簽數(shù)據(jù)即一個(gè)樣本可以同時(shí)屬于多個(gè)標(biāo)簽，并且每一個(gè)樣本具體的標(biāo)簽數(shù)量是不確定的。

1.1.1 算法適應(yīng)

1.1.2 問題轉(zhuǎn)換

1.2 RAKEL

由于RAKEL算法隨機(jī)選擇標(biāo)簽子集，沒有充分考慮標(biāo)簽間相關(guān)性，研究者們分別提出了不同的改進(jìn)算法。如基于聚類的RAKEL算法（LC-RAKEL）［11］的基本思想是通過k-means聚類來找到標(biāo)簽間的相關(guān)性選取標(biāo)簽子集；但當(dāng)標(biāo)簽個(gè)數(shù)較少且標(biāo)簽間相似性較高時(shí)，聚類的效果不明顯。PwRAKEL（Pairwise RAndom-labELsets）算法［12］通過考察兩兩標(biāo)簽間的相關(guān)性選取標(biāo)簽子集；但忽略了更多標(biāo)簽之間可能存在關(guān)聯(lián)的情況，具有局限性。基于FP-Growth的RAKEL算法FI-RAKEL［13］則利用FP-growth算法找到頻繁項(xiàng)集，將頻繁項(xiàng)集中每一個(gè)頻繁項(xiàng)和原始標(biāo)簽集中部分標(biāo)簽組合，作為標(biāo)簽子集；但該算法容易使大量頻繁項(xiàng)和其他原始標(biāo)簽組合構(gòu)成新的標(biāo)簽子集，其中有些標(biāo)簽組合在訓(xùn)練集中樣本稀少造成了資源浪費(fèi)。

2 基于貝葉斯網(wǎng)絡(luò)的RAKEL多標(biāo)簽分類算法

2.1 相關(guān)概念

2.2 基于貝葉斯網(wǎng)絡(luò)確定候選標(biāo)簽子集

本文通過貝葉斯網(wǎng)絡(luò)確定標(biāo)簽間相關(guān)性，產(chǎn)生候選標(biāo)簽子集。貝葉斯網(wǎng)絡(luò)［14-15］是一種概率的圖模型，允許表示節(jié)點(diǎn)之間的依賴關(guān)系。根據(jù)貝葉斯網(wǎng)絡(luò)的有向無環(huán)圖（Directed Acyclic Graph， DAG）以及條件概率表（Conditional Probability Table， CPT），可以快速得到每個(gè)節(jié)點(diǎn)與其父節(jié)點(diǎn)的所有組合的概率。

確定候選標(biāo)簽子集具體思路如下：

圖1 貝葉斯網(wǎng)絡(luò)DAG

確定候選標(biāo)簽子集具體步驟如算法1。

算法1 BN-RAKEL確定標(biāo)簽子集。

表1 條件概率表例1

表2 條件概率表例2

2.3 挖掘最優(yōu)特征空間并過濾候選標(biāo)簽子集

本文根據(jù)式（5）計(jì)算最優(yōu)特征空間相似性。最優(yōu)特征空間相似性即針對候選標(biāo)簽子集內(nèi)標(biāo)簽，共同擁有的最優(yōu)特征空間個(gè)數(shù)占該候選標(biāo)簽子集標(biāo)簽的所有最優(yōu)特征空間的比值，占比越大說明該候選標(biāo)簽子集相似性越強(qiáng)。

根據(jù)最優(yōu)特征空間過濾候選標(biāo)簽子集的具體步驟如下：

3）確定最終標(biāo)簽子集最優(yōu)特征空間。標(biāo)簽子集內(nèi)的標(biāo)簽的最優(yōu)特征空間取并集，構(gòu)成該標(biāo)簽子集的最優(yōu)特征空間，并在該標(biāo)簽子集的最優(yōu)特征空間上訓(xùn)練LP分類器。

算法2描述的是挖掘單個(gè)標(biāo)簽最優(yōu)特征空間，算法3描述的是確定最終標(biāo)簽子集及其最優(yōu)特征空間并訓(xùn)練LP分類器。

算法2 挖掘單個(gè)標(biāo)簽最優(yōu)特征空間。

算法3 確定最終標(biāo)簽子集及其最優(yōu)特征空間。

其中：5）～6）行根據(jù)最優(yōu)空間相似性確定是否剔除候選標(biāo)簽子集，確定最終標(biāo)簽子集；7）～11）行在最終標(biāo)簽子集找到其最優(yōu)特征空間；12）行在最終標(biāo)簽子集的最優(yōu)特征空間上訓(xùn)練LP分類器。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

本文使用的數(shù)據(jù)集來自中國社區(qū)衛(wèi)生服務(wù)中心，包含6 000個(gè)樣本，每個(gè)樣本包含12個(gè)導(dǎo)聯(lián)10 s記錄。經(jīng)過數(shù)據(jù)預(yù)處理，提取了718個(gè)特征，18個(gè)標(biāo)簽，標(biāo)簽由兩位專業(yè)醫(yī)生給出，下載地址為https：//github.com/hjyresearch228/PAC。

3.2 評價(jià)指標(biāo)

3.3 實(shí)驗(yàn)結(jié)果與分析

3.3.1 算法性能實(shí)驗(yàn)

3.3.2 與其他多標(biāo)簽分類算法對比分析

圖3為BN-RAKEL與ML-KNN、CC、FP-RAKEL和RAKEL算法在不同標(biāo)簽數(shù)的性能對比結(jié)果。從圖3可以看出，隨著標(biāo)簽數(shù)的增多，BN-RAKEL在Accuracy、Recall和F-score均呈逐漸增長趨勢。

圖2 BN-RAKEL算法在不同閾值下的F-score

圖3 不同標(biāo)簽數(shù)下不同算法的性能對比

表3是BN-RAKEL在ECG數(shù)據(jù)集上與其他算法的對比結(jié)果。

表3 不同分類算法的評價(jià)指標(biāo)對比

由表3可知，BN-RAKEL在Recall和F-score上都取得了最好效果，分別為0.772和0.681，在Accuracy上僅比CC算法低0.3個(gè)百分點(diǎn)；與原RAKEL算法相比，BN-RAKEL算法在Recall和F-score上有明顯提升，分別提高了19.0個(gè)百分點(diǎn)和6.7個(gè)百分點(diǎn)；與FI-RAKEL算法相比也有明顯提升，在Recall和F-score上分別提高了3.6個(gè)百分點(diǎn)和2.4個(gè)百分點(diǎn)。這說明本文提出的BN-RAKEL能夠有效挖掘標(biāo)簽間的相關(guān)性，有效提升多標(biāo)簽分類問題的預(yù)測性能。

4 結(jié)語

對于ECG診斷問題，一個(gè)樣本通常包含多種病癥，并且病癥之間存在一定的相關(guān)性。為了充分利用標(biāo)簽間存在相關(guān)性的特點(diǎn)，本文提出了基于貝葉斯網(wǎng)絡(luò)的RAKEL算法BN-RAKEL。在來自中國社區(qū)衛(wèi)生服務(wù)中心數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，與ML-KNN、CC、FP-RAKEL和RAKEL算法相比，BN-RAKEL在Recall和F-score上都取得了最好效果，分別為0.772和0.681，僅在Accuracy上比CC算法少了0.3個(gè)百分點(diǎn)。但是在檢測標(biāo)簽子集的相關(guān)性時(shí)，本文方法只考慮了各個(gè)標(biāo)簽的共同最優(yōu)特征空間個(gè)數(shù)，未來可以考慮如何使用更合適的校驗(yàn)方法來確定最終標(biāo)簽子集。

[1] 程思靜，華偉. 心電學(xué)指標(biāo)在預(yù)測心臟性猝死中的研究進(jìn)展［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ī)器學(xué)習(xí)在心血管疾病診斷中的研究進(jìn)展［J］. 北京生物醫(yī)學(xué)工程， 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ī)器學(xué)習(xí)的心電圖診斷研究［J］. 實(shí)用心電學(xué)雜志， 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] 李思男，李寧，李戰(zhàn)懷. 多標(biāo)簽數(shù)據(jù)挖掘技術(shù)：研究綜述［J］. 計(jì)算機(jī)科學(xué)， 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] 金永賢，張微微，周恩波. 一種改進(jìn)的RAKEL多標(biāo)簽分類算法［J］. 浙江師范大學(xué)學(xué)報(bào)（自然科學(xué)版）， 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] 周恩波，葉榮華，張微微，等. 一種基于成對標(biāo)簽的Rakel算法改進(jìn)［J］. 計(jì)算機(jī)與現(xiàn)代化， 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] 梁睿博，王思遠(yuǎn)，李壯，等. 基于RAKEL算法的商品評論多標(biāo)簽分類研究與實(shí)現(xiàn)［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] 張連文，郭海鵬. 貝葉斯網(wǎng)引論［M］. 北京：科學(xué)出版社， 2006： 97.（ZHANG L W， GUO H P. Introduction to Bayesian Networks［M］. Beijing： Science Press， 2006： 97.）

[16] 張振海，李士寧，李志剛，等. 一類基于信息熵的多標(biāo)簽特征選擇算法［J］. 計(jì)算機(jī)研究與發(fā)展， 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ìn)化策略的特征選擇算法研究［J］. 軟件學(xué)報(bào)， 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。

國家自然科學(xué)基金資助項(xiàng)目（62002174）。

趙靜（1996—），女，江蘇連云港人，碩士研究生，主要研究方向：機(jī)器學(xué)習(xí)；韓京宇（1976—），男，吉林白山人，教授，博士，主要研究方向：機(jī)器學(xué)習(xí)、數(shù)據(jù)庫；錢龍（1994—），男，江蘇鹽城人，碩士研究生，主要研究方向：機(jī)器學(xué)習(xí)；毛毅（1985—），女，江蘇南京人，講師，博士，主要研究方向：機(jī)器學(xué)習(xí)、深度學(xué)習(xí)。