基于改進的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—），女，江蘇南京人，講師，博士，主要研究方向：機器學習、深度學習。