, , , , , ,3,

(1.華東理工大學機械與動力工程學院,上海 200237; 2.上海中醫(yī)藥大學四診信息綜合實驗室,上海 201203;3.上海中醫(yī)藥大學交叉科學研究院,上海 201203)

基于極值隨機森林的慢性胃炎中醫(yī)證候分類

顏建軍1,胡宗杰1,劉國萍2,王憶勤2,付晶晶2,郭睿2,3,錢鵬2

(1.華東理工大學機械與動力工程學院,上海200237;2.上海中醫(yī)藥大學四診信息綜合實驗室,上海201203;3.上海中醫(yī)藥大學交叉科學研究院,上海201203)

大多數(shù)機器學習算法能得到較好的分類效果,但模型卻無法解釋;而隨機森林等模型有良好的可解釋性,卻無法處理中醫(yī)數(shù)據(jù)中兼證的情況。本文利用極值隨機森林算法對慢性胃炎中醫(yī)數(shù)據(jù)進行證候分類研究,其中決策樹的葉節(jié)點能輸出多個標簽,通過加權(quán)機制綜合分量來處理兼證問題。與已有多標記學習算法和C4.5、CART等基于決策樹的算法進行比較,實驗結(jié)果表明,極值隨機森林算法無論在6個證型的分類準確率上,還是在多標記評價指標上都具有更好的效果,而且模型中得到的規(guī)則基本符合中醫(yī)理論。

證候分類; 極值隨機森林; 可解釋性; 慢性胃炎; 決策樹

辨證論治是中醫(yī)診斷學的精髓,其中辨證是綜合了臨床各類信息并加以分析、歸納,以辨清疾病的病因、病機、病性和病位的過程。然而,在中醫(yī)辨證中存在大量的不確定性和模糊性,缺乏客觀的評價標準,制約了中醫(yī)的推廣和發(fā)展。利用數(shù)據(jù)挖掘、機器學習等計算機技術(shù)分析中醫(yī)四診信息,探索癥狀與證型之間的關(guān)系,構(gòu)建中醫(yī)辨證模型,實現(xiàn)中醫(yī)診斷數(shù)字化和客觀化,已成為中醫(yī)診斷現(xiàn)代化發(fā)展的趨勢。

大多數(shù)機器學習算法能得到較好的分類效果,但模型卻無法解釋。決策樹用直觀易懂的圖結(jié)構(gòu)模型來表示觀測變量與觀測變量、觀測變量與標簽之間的關(guān)系,從根節(jié)點到葉節(jié)點的每一條路徑都有一個完整的決策規(guī)則[1],由此生成的模型具有良好的可解釋性和分類效果,所以決策樹在中醫(yī)辨證模型的研究中得到了廣泛應用。早在20世紀90年代,就有學者利用決策樹提取專家經(jīng)驗,建立專家系統(tǒng)并取得了較好的結(jié)果[2]。本世紀研究者對中醫(yī)辨證推理開始了比較深入的研究,應用決策樹方法進行中醫(yī)證型的分類,如文獻[3-5]利用決策樹算法建立了不同疾病的辨證模型。隨著算法的不斷改進,決策樹在分類效果和可解釋性的優(yōu)勢越發(fā)明顯。2001年,Breiman等[6]提出隨機森林算法,利用bootstrap重復采樣技術(shù)來構(gòu)建多個決策樹模型,算法在樣本數(shù)量大或者屬性多的情況下處理效果非常好。文獻[7-9]對隨機森林算法開展了進一步研究,也取得了不錯的成果。

然而,在這些傳統(tǒng)的監(jiān)督學習中,一個對象只對應一個標簽,當學習對象明確且唯一時,這些算法在一定程度上能取得較好的分類效果,但它卻無法處理一個對象對應多個標簽的情況[10]。若一個樣本和多個標簽相對應,則稱這樣的數(shù)據(jù)為多標記數(shù)據(jù),中醫(yī)辨證就屬于這類任務,中醫(yī)臨床兼證多見,即一個病人可能會對應多個證型。本文中慢性胃炎數(shù)據(jù)的證型包括脾胃濕熱、濕濁中阻、脾胃氣虛、脾胃虛寒、肝氣郁滯和肝胃郁熱6類,一個病例樣本可能同時對應多個證型,屬于典型的多標記數(shù)據(jù)。多標記學習是處理這類數(shù)據(jù)的有效方法,可以解決一個樣本同時對應多個標簽的情況,通過對大量的多標記數(shù)據(jù)樣本進行訓練得到多標記模型,通過該模型對未知的多標記樣本進行預測。近些年來,也有學者將基于樹的算法應用于多標記學習中[11-14],并對算法模型的解釋性做了進一步研究[15-19]。本文利用極值隨機森林(Extremely Randomized Forest,ERF)算法來處理慢性胃炎患者多兼證的問題,即多個證型同時輸出的問題,通過加權(quán)機制綜合分量來處理兼證問題,并與其他多標記算法和C4.5、CART等基于決策樹的算法進行了比較。

1 實驗方法

1.1ERF算法

ERF算法[20]根據(jù)自上而下的過程,生成一組無剪枝的決策樹,與其他基于樹的集成算法相比有2點不同:(1)屬性的切割點是完全隨機選擇的;(2)使用整體學習樣本(而不是重復采樣)來生成決策樹。ERF算法在每個分裂節(jié)點處隨機選取k個不同的屬性,生成k個分裂點,選取Score分值最高的分裂點將節(jié)點分裂為左右子樹,建立決策樹模型。極值隨機森林算法偽代碼如下:

extra_random_forest(S)輸入:訓練集S

輸出:由M棵決策樹T={t1,…,tM}組成的隨機森林

Fori=1 toM

生成決策樹ti=extra_tree(S)

Return 極值隨機森林T

extra_tree(S)

輸入:訓練集S

輸出:一棵決策樹t

IF

節(jié)點中當樣本數(shù)|S|<分裂所需要的最小樣本數(shù)nmin,或節(jié)點中只存在一個標簽,或候選屬性唯一

Return 葉節(jié)點

else

隨機選取k個不同的屬性ai,…,ak,產(chǎn)生k個分裂點s1,…,sk

si=random_split(S,ai),?i=1,…,k,選取結(jié)果最好的分裂點為最佳分裂點s*

Score=maxi=1,…,kScore(si,S),分裂為左右子樹

左子樹tl=extra_tree(Sl),右子樹tr=extra_tree(Sr),直至節(jié)點變成葉節(jié)點

random_split(S,a)

輸入:訓練集S和屬性a

輸出:最佳分裂點s*

在分類問題上,Score的表達式為

(1)

假設(shè)學習樣本lSN={(xi,yi):i=1,…,N},N為總的學習樣本數(shù)量,lt為決策樹t的葉子,lt,i(x)為決策樹t第i個葉子的特征函數(shù),nt,i為第i棵決策樹學習樣本的數(shù)目。則t的特征函數(shù)lt(x)為

(2)

則模型可以表示為

(3)

由式(2)、(3)可以看出:極值決策樹模型可以看作基于核的模型,核可表示為

(4)

對于M個集成樹T={ti:i=1,…,M},核的集成模型可表示為

(5)

由此得到預測模型

(6)

(7)

該集成核為

(8)

通過式(7)、(8)可以得到最終的集成預測模型(式6)。

以上算法包含了3個設(shè)定的參數(shù):在任意節(jié)點上被隨機選取的屬性的數(shù)量k、分裂節(jié)點所需要的最小樣本數(shù)量nmin和集成樹的數(shù)量M。

1.2參數(shù)的選擇

參數(shù)k表示ERF算法中每個節(jié)點的隨機選擇屬性的數(shù)目。對于給定的問題,k越小,算法的隨機化越強,學習樣本的輸出與模型結(jié)構(gòu)的依賴性就越弱。在極端情況下,當k=1時,屬性和切點會選擇一個完全獨立的輸出變量。而在另一個極端情況下,當k=n時,屬性的選擇就不是確定的隨機了,算法僅僅通過隨機點的行為來影響隨機效應。k的選擇是算法可解釋性的另一個重要體現(xiàn)。當k較大時,由于考慮了更多的屬性之間的相互關(guān)聯(lián),得到的模型會具有較好的可解釋性,但會使得算法模型分支太多而導致分類準確率下降,所以k的正確選擇對算法有著重要影響。

nmin為ERF算法中節(jié)點分裂時所需的最小樣本數(shù)量,是決策樹停止準則中重要的參數(shù)。當節(jié)點中樣本數(shù)小于最小分裂樣本數(shù)時,該節(jié)點停止分裂,成為葉節(jié)點。較大的nmin不僅會降低樹的深度和廣度,還會導致較高的方差;但如果nmin較小,又容易出現(xiàn)過擬合現(xiàn)象,因此,原則上nmin最優(yōu)值取決于數(shù)據(jù)集輸出噪音的水平。

參數(shù)M表示集成樹的數(shù)量,隨機化方法的誤差預測是M的單調(diào)遞減函數(shù)。因此,M越高,表明其精確度越好。不同隨機化方法對不同問題的解決,其收斂情況可能有差異,因為算法的收斂情況不僅取決于集成樹的數(shù)量,還取決于樣本量的大小和其他參數(shù)的設(shè)置。

1.3實驗數(shù)據(jù)

919例慢性胃炎數(shù)據(jù)樣本由上海中醫(yī)藥大學中醫(yī)四診信息綜合研究實驗室提供,采集自2008年9月～2010年10月上海中醫(yī)藥大學附屬龍華醫(yī)院、曙光醫(yī)院、岳陽醫(yī)院及上海市第八人民醫(yī)院的胃鏡檢查室、病房和門診等臨床病例。所有病例都是經(jīng)胃鏡與病理組織學結(jié)果結(jié)合臨床表現(xiàn)診斷確診為慢性胃炎的患者。由具有中級職稱以上(或具有博士學位)的醫(yī)師根據(jù)問診量表進行病史和癥狀、體征等方面數(shù)據(jù)的收集,記錄包括面色、舌象及脈象等共113個特征,并標出每個樣本具有的證型,制作成問診量表。慢性胃炎中醫(yī)診斷證型包括脾胃濕熱、濕濁中阻、脾胃氣虛、脾胃虛寒、肝氣郁滯、肝胃郁熱、胃陰虛、瘀血阻胃8個證型,但由于采集到的數(shù)據(jù)中,胃陰虛和瘀血阻胃出現(xiàn)的頻次太少,本文中只對其他6個證型進行分析。

1.4比較方法

為了驗證算法的性能,本文將ERF算法與BPMLL[21]、MLKNN[22]、RankSVM[23]、BSVM[24]、ECC[25]、LIFT[26]等多標記學習算法和C4.5和CART[27]等決策樹算法進行了比較。

1.5實驗性能評價準則

利用每個標簽的分類準確率和多標記學習中常用的6個評價標準作為實驗的性能評價指標[28],分別為覆蓋距離(coverage)、漢明損失(hamming loss)、首標記錯誤(one-error)、排序損失(ranking loss)、平均精度(average precision)、平均AUC曲線下面積(average AUC)。

(1) average precision:高于某個特定標簽y∈Y的相關(guān)標簽的平均分數(shù),其值越高越好,如式(9)所示。

(9)

(2) coverage:覆蓋預測樣本的所有相關(guān)標簽,其值越小越好,如式(10)所示。

(10)

(3) hamming loss:漢明損失評估的是類別標簽被錯分的次數(shù),其值越小越好,如式(11)所示。

(11)

(4) one-error:預測最高排序不屬于相關(guān)標簽集合的次數(shù),其值越小越好,如式(12)所示。

(12)

(5) ranking loss:評估反向有序標簽對的數(shù)目,即不相關(guān)標簽排序比相關(guān)標簽高的次數(shù)。其值越小越好,如式(13)所示。

|{(y1,y2)|f(xi,y1)≤f(xi,y2),

(13)

(6) average AUC[29]:即處于ROC(Receiver Operating Characteristic)曲線下方與一條斜率大小為1的直線所包含的那部分面積的大小,其值越大越好。

2 實驗結(jié)果

將ERF算法與BPMLL、MLKNN、RankSVM、BSVM、ECC、LIFT等多標記算法和CART和C4.5算法進行比較。為了更清晰地比較各種算法的結(jié)果,使用雙尾t檢驗將對應的10倍交叉數(shù)據(jù)進行統(tǒng)計分析,比較結(jié)果見表1,其中○表示ERF算法在統(tǒng)計學上劣于某算法,●表示ERF在統(tǒng)計學上優(yōu)于某算法。

表1 各算法的多標記評價指標的實驗結(jié)果

從表1可以看出,ERF算法在6個多標記評價指標上均優(yōu)于其他幾種算法,特別是在平均精度、覆蓋距離、排序損失、平均AOC曲線下面積4個指標上具有明顯優(yōu)勢。統(tǒng)計結(jié)果顯示,在漢明損失上,BSVM和LIFT與ERF沒有明顯差異;在首標記錯誤上,C4.5與ERF也沒有明顯差異。

圖1示出了各算法的證型分類準確率,從圖1可以看出,ERF算法在脾胃濕熱、脾胃氣虛、脾胃虛寒、肝氣郁滯上得到最高的分類準確率。對于濕濁中阻證,C4.5算法的分類準確率略優(yōu)于ERF。對于脾胃虛寒證,ERF算法與MLKNN、BPMLL、BSVM、LIFT的分類準確率相同,分類效果最好。對于肝胃郁熱證,MLKNN、BPMLL、LIFT的分類準確率略優(yōu)于ERF算法。ERF算法在脾胃濕熱、脾胃氣虛、脾胃虛寒、肝氣郁滯4個證型上取得了最好的分類準確率,在濕濁中阻和肝胃郁熱2個證型上表現(xiàn)出了較好的分類準確率。

圖1 各算法的證型分類準確率Fig.1 Classification accuracy of syndromes of each algorithm

3 討 論

圖2 平均精度隨k/變化的結(jié)果Fig.2 Variation of average precision with different k/

圖3 標簽平均分類準確率隨k/變化的結(jié)果Fig.3 Variation of average classification

利用ERF算法推薦的參數(shù)設(shè)置可以提高精確度和降低計算復雜度,也減少了算法的運行時間,由于分割點是隨機的,使得決策樹在深度和廣度上都有了一定的提高。ERF算法考慮了每個標簽之間的聯(lián)系,通過葉節(jié)點加權(quán)機制綜合分量來處理兼證問題。決策樹中每一條從根節(jié)點到葉節(jié)點的路徑都有一個完整的決策規(guī)則,這就決定了算法模型有良好的可解釋性。經(jīng)過規(guī)則整理,本文對其中脾胃濕熱證、脾胃氣虛證分別給出一條辨證分類規(guī)則:

(1) 如果“苔膩:是”并且“舌色紅:是”并且“舌中:是”并且“苔黃:是”并且“口粘膩:是”,那么該病人診斷為脾胃濕熱。

(2) 如果“膩:否”并且“口氣重:否”并且“乏力:是”并且“舌色淡白:是”并且“全舌:是”并且“苔白:是”并且“肢體沉重:是”,那么該病人診斷為脾胃氣虛。

根據(jù)實證和虛癥的診斷標準,這些決策規(guī)則基本符合中醫(yī)理論,說明ERF算法具有良好的分類效果的同時,也具有較好的可解釋性,這表明ERF算法能夠有效地處理多標簽的中醫(yī)數(shù)據(jù)。因此,極值隨機森林算法能夠較好地處理癥狀和證型以及證型與證型之間的相互聯(lián)系,所建立的模型具有良好的可解釋性,有利于中醫(yī)慢性胃炎證候診斷的標準化和客觀化,也為中醫(yī)診斷客觀化提供了有益的參考和新的思路。

[1] 趙悅.概率圖模型學習理論及其應用[M].北京:清華大學出版社,2012.

[2] 王勇.一種診斷外周神經(jīng)系統(tǒng)疾病的專家系統(tǒng)[J].重慶大學學報,1994,17(4):104-109.

[3] 徐蕾,賀佳,孟虹,等.基于信息熵的決策樹在慢性胃炎中醫(yī)辨證中的應用[J].第二軍醫(yī)大學學報,2004,25(9):1009-1012.

[4] 查青林,何羿婷,喻建平,等.基于決策樹分析方法探索類風濕性關(guān)節(jié)炎證病信息與療效的相關(guān)關(guān)系[J].中國中西醫(yī)結(jié)合雜志,2006,26(10):871-878.

[5] 廖曉威,馬利莊,王彥.ES-ID3算法及其在中醫(yī)辨證中的應用[J].計算機工程與應用,2008,44(32):191-195.

[6] BREIMAN L.Random forests[J].Machine Learning,2001,45(1):5-32.

[7] 劉永春,宋宏.基于隨機森林的乳腺腫瘤診斷研究[J].電視技術(shù),2014,38(15):253-255.

[8] 聶斌,王卓,杜建強,等.基于粗糙集和隨機森林算法輔助糖尿病并發(fā)癥分類研究[J].江西師范大學學報,2014,38(3):278-282.

[9] 范昕,趙桂新,孫萌,等.使用隨機森林判別分析法預測黑加侖油膠囊治療高血脂的效果[J].中醫(yī)藥信息,2012,29(4):43-47.

[10] 何志芬,楊明,劉會東.多標記分類和標記相關(guān)性的聯(lián)合學習[J].軟件學報,2014,25(9):1967-1981.

[11] DIMITROVSKI I,KOCEV D,LOSKOVSKA S,etal. Hierarchical classification of diatom images using ensembles of predictive clustering trees[J].Ecological Informatics,2012,7(1):19-29.

[12] VENS C,STRUYF J,SCHIETGAT L,etal.Decision trees for hierarchical multi-label classification[J].Machine Learning,2008,73(2):185-214.

[13] ZHOU T,TAO D.Multi-label subspace ensemble[C]//15thInternational Conference on Artificial Intelligence and Statistics.Berlin:Springer-Verlag,2012:1444-1452.

[14] JOLY A,GEURTS P,WEHENKEL L.Random forests with random projections of the output space for high dimensional multi-label classification[J].Lecture Notes in Computer Science,2014,8724:607-622.

[15] TAN S,SIM K C,GALES M.Improving the interpretability of deep neural networks with stimulated learning[J].IEEE Transactions on Neural Networks,2015,10:617-623.

[16] SHUKLA P K ,TRIPATHI S P.A Survey on interpretability-accuracy (I-A) trade-off in evolutionary fuzzy systems[C]//Fifth International Conference on Genetic and Evolutionary Computing.New Jersey:IEEE press,2011:97-101.

[17] OTERO F E B,FREITAS A A.Improving the interpretability of classification rules discovered by an ant colony algorithm:Extended results[J].Evolutionary Computation,2016,24(3):385-409.

[18] TURNER R.A model explanation system[EB/OL].[2015-12-22].http://www.inference.vc/accuracy-vs- explainability-in-machine-learning-models-nips-workshop-poster-review/.

[19] MAISTO D,ESPOSITO M.Improving accuracy and interpretability of clinical decision support systems through possibilistic constrained evolutionary optimization[C]//Eighth International Conference on Signal Image Technology and Internet Based Systems.Sorrento:Institute of Electrical and Electronics Engineers,2012:474-481.

[20] GEURTS P,ERNST D,WEHENKEL L.Extremely randomized trees[J].Machine Learning,2006,63(1):3-42.

[21] ZHANG M L,ZHOU Z H.Multi-label neural networks with applications to functional genomics and text categorization[J].IEEE Transactions on Knowledge and Data Engineering,2006,18(10):1338-1351.

[22] ZHANG M L,ZHOU Z H.ML-kNN:A lazy learning approach to multi-label learning[J].Pattern Recognition,2007,40(7):2038-2048.

[23] TSOUMAKAS G,KATAKIS I,VLAHAVAS I.Data Mining and Knowledge Discovery Handbook[M].Berlin:Springer-Verlag,2010.

[24] BOUTELL M R,LUO J,SHEN X,etal.Learning multi-label scene classification[J].Pattern Recognition,2004,37(9):1757-1771.

[35] READ J,PFAHRINGER B,HOLMES G,etal.Classifier chains for multi-label classification[J].Machine Learning and Knowledge Discovery in Databases,2009,11:254-269.

[26] ZHANG M L.LIFT:Multi-label learning with label-specific features[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,37(1):107-120.

[27] TRENDOWICZ A,JEFFERY R.Classification and Regression Trees[M].Berlin:Springer-Verlag,2014.

[28] 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.

[29] DAVID J.Measuring classifier performance:A coherent alternative to the area under the ROC curve[J].Machine Learning,2009,77(1):103-123.

SyndromeClassificationofChronicGastritisBasedonExtremelyRandomizedForestAlgorithm

YANJian-jun1,HUZong-jie1,LIUGuo-ping2,WANGYi-qin2,FUJing-jing2,GUORui2,3,QIANPeng2

(1.SchoolofMechanicalandPowerEngineering,EastChinaUniversityofScienceandTechnology,Shanghai200237,China;2.LaboratoryofInformationAccessandSynthesisofTraditionalChineseMedicineFourDiagnosis,ShanghaiUniversityofTraditionalChineseMedicine,Shanghai201203,China;3.InstituteofInterdisciplinaryResearchComplex,ShanghaiUniversityofTraditionalChineseMedicine,Shanghai201203,China)

Syndrome differentiation and treatment,which is the essence of traditional Chinese medicine (TCM),contain abundant rules.The majority of machine learning algorithms can obtain good classification accuracy,but these models are difficult to be explained.The models established by random forests have great interpretability,while these models cannot deal with multi-syndrome that patients may simultaneously have more than one syndrome in TCM.In this paper,syndrome classification for Chronic Gastritis (CG) is researched by using extremely randomized forest (ERF) algorithm,and compared with state-of-the-art multi-label algorithms and the tree-based algorithms (such as C4.5,CART).The experimental results show that ERF algorithm has better performance than other algorithms in the classification accuracy of every label and the six evaluation metrics of multi-label learning.The rules obtained in the model are basically in accord with TCM theory.

syndrome classification; extremely randomized forest; interpretability; chronic gastritis; decision tree

R241

A

1006-3080(2017)05-0698-06

10.14135/j.cnki.1006-3080.2017.05.015

2016-12-30

國家自然科學基金(81270050,81302913,30901897,81173199)

顏建軍(1975-),男,副教授,主要研究方向為復雜機電系統(tǒng)控制、中醫(yī)四診數(shù)字化和客觀化、醫(yī)學信號處理和圖像處理。 E-mail:jjyan@ecust.edu.cn

劉國萍,E-mail:13564133728@163.com