王旭晨,，陳小惠

　　（南京郵電大學(xué) 自動化學(xué)院,，江蘇 南京210023）

　　摘要：提出一種基于統(tǒng)計關(guān)聯(lián)規(guī)則的增量決策樹分類算法,，稱為SARMT(Statistic Association Rules Miner Tree），它基于快速決策樹(Very Fast Decision Tree,VFDT)技術(shù)來挖掘醫(yī)療數(shù)據(jù),。與VFDT不同,，改進(jìn)的SARMT算法不依賴于樣本分裂節(jié)點的數(shù)量。在醫(yī)療大數(shù)據(jù)中,，通常缺少大量可用的數(shù)據(jù)樣本,，因此SARMT算法更加適用于醫(yī)療環(huán)境中。將SARMT算法和VFDT算法應(yīng)用于不同的三個醫(yī)療數(shù)據(jù)集上,，實驗結(jié)果表明在執(zhí)行時間相當(dāng)?shù)那闆r下， SARMT算法在處理醫(yī)療數(shù)據(jù)中有更高的準(zhǔn)確率,。

　　關(guān)鍵詞：醫(yī)療數(shù)據(jù),；決策樹；關(guān)聯(lián)規(guī)則,；

0引言

　　隨著知識發(fā)現(xiàn)的發(fā)展,，決策樹在很多領(lǐng)域中得到應(yīng)用。對于醫(yī)療領(lǐng)域而言,，其應(yīng)用大多數(shù)集中在疾病診斷上,。決策樹的思路［12］是找出最有分辨能力的屬性，把數(shù)據(jù)庫劃分成許多個子集（一個子集對應(yīng)樹的一個分支），然后對每個子集遞歸調(diào)用分支過程,，直到所有子集包含同一類型的數(shù)據(jù),。它的優(yōu)點主要是描述簡單、分類速度快,，比較適合處理大規(guī)模的數(shù)據(jù),。

　　分類任務(wù)的目標(biāo)［34］是建立一個模型來描述和區(qū)分?jǐn)?shù)據(jù)類別，在大數(shù)據(jù)中,，通常使用增量技術(shù)進(jìn)行分類,，該算法可以將新加入的樣本納入原有的樣本集中，使最后生成的規(guī)則是建立在原有的樣本和新加入的樣本之上而不需要重新建立決策樹,。文獻(xiàn)［5］提出一種基于Hoeffding樹的決策樹——VFDT(Very Fast Decision Tree)算法,，它使用信息增益和基尼系數(shù)指標(biāo)為屬性進(jìn)行評估測量，并且對原始的決策樹算法進(jìn)行了優(yōu)化,。文獻(xiàn)［6］指出該算法的一些不足,，例如它需要足夠多的葉子節(jié)點保證該樹的增長，因此需要大量的數(shù)據(jù)樣本提供這些信息,。然而,，醫(yī)療行業(yè)總體數(shù)據(jù)存儲量不是很大，且各醫(yī)療機(jī)構(gòu)之間的差異比較大,，具體到某一種病情的可用數(shù)據(jù)樣本就更少了,。所以在數(shù)據(jù)存儲量不是很多的情況下，VFDT算法的準(zhǔn)確性和效率都不是很高,。

1相關(guān)研究方法

　　一般研究方法運(yùn)用Hoeffding約束規(guī)則［7］來解決應(yīng)該選取多少樣本來獲得測試屬性,，若一個真值隨機(jī)變量r的取值范圍是R，假設(shè)對r有n個獨立的觀察值,，并計算了它們的平均值,，Hoeffding約束規(guī)則即是：對于可信度1~δ，變量r的真實值至少是r~ε,，其中：

　　Hoeffding約束規(guī)則有一個特點是觀察值生成的概率是獨立分布的,，但缺點是約束規(guī)則比從屬分布保守，需要更多的樣本,。VFDT的主要特性之一是它可以保持良好的準(zhǔn)確性并且使用相關(guān)Hoeffding約束規(guī)則來處理大量數(shù)據(jù),。

2統(tǒng)計關(guān)聯(lián)規(guī)則決策樹

　　2.1統(tǒng)計關(guān)聯(lián)規(guī)則

　　統(tǒng)計關(guān)聯(lián)規(guī)則是一種基于分布定量值的可以顯示數(shù)據(jù)子集之間關(guān)系的規(guī)則，它為其他關(guān)聯(lián)規(guī)則的生成過程提供統(tǒng)計測試來確認(rèn)其有效性,。統(tǒng)計關(guān)聯(lián)規(guī)則的優(yōu)點是不需要數(shù)據(jù)離散化,，因為離散化過程可能會導(dǎo)致信息丟失，往往扭曲挖掘算法的計算結(jié)果,。

　　在本文中,，統(tǒng)計關(guān)聯(lián)規(guī)則挖掘的概念適用于屬性評估，來驗證何時分裂節(jié)點以及使用何種屬性。特征向量可以定量地描述數(shù)據(jù),，因此,，需要一個合適的方法來定量挖掘關(guān)聯(lián)規(guī)則的數(shù)據(jù)。本文提出SARMT(Statistic Association Rules Miner Tree）算法,，其目標(biāo)是找到一種統(tǒng)計關(guān)聯(lián)規(guī)則來選擇一組可以保留其他特性的最小數(shù)據(jù)集,。

　　2.2SARMT算法

　　本文基于VFDT算法，利用統(tǒng)計關(guān)聯(lián)規(guī)則作為啟發(fā)式方法［8］提出了SARMT算法,，選擇合適的屬性作為測試節(jié)點,，并通過統(tǒng)計數(shù)值數(shù)據(jù)來決定何時完成樹節(jié)點的分割。它是一種增量決策樹構(gòu)造算法,，負(fù)責(zé)處理數(shù)值數(shù)據(jù),。正如前面提到的，由于Hoeffding樹的限制,，VFDT需要構(gòu)建更多的樣本,，而SARMT提出構(gòu)建比VFDT少的樣本，且保持良好的準(zhǔn)確性,，同時根據(jù)數(shù)據(jù)描述獲得更少的執(zhí)行時間,。

　　SARMT算法的總體結(jié)構(gòu)與VFDT相似，但與VFDT不同的是SARMT算法可以決定何時執(zhí)行節(jié)點的劃分,，能夠分類描述數(shù)據(jù),，而且數(shù)據(jù)樣本比VFDT少。這里只描述與VFDT不同的算法步驟,。

　　假設(shè)T是數(shù)據(jù)集,，ai是屬性，aik是第k個數(shù)據(jù)的屬性,，xj是類,，Txj∈T。μai和σai分別表示數(shù)據(jù)集屬性的平均值和標(biāo)準(zhǔn)差,。又定義了三個閾值：Δμmin表示允許類xj中ai的平均值與剩余項集中ai的平均值的最小誤差,；σmax表示類中ai的最大標(biāo)準(zhǔn)差；γmin表示最小置信度,。計算公式分別如式(2),、(3)、(4),。

　　每個屬性ai的平均值和標(biāo)準(zhǔn)差分別由類xj產(chǎn)生，當(dāng)觀察值是最小樣本時,，SARMT選擇滿足以下條件的屬性：

　?。?）ai在類xj中應(yīng)該有不同于其他類的行為；

　　（2）ai在類xj中應(yīng)該提供一個統(tǒng)一行為,。

　　為了滿足這些條件,，限制興趣度的使用。標(biāo)準(zhǔn)誤差置信水平Z計算如式(5)：

　　SARMT算法描述如下：

　　(1)SARMT是一個根節(jié)點

　　(2)for each樣本e do

　　(3)將e使用SARMT分成葉子節(jié)點l

　　(4)在l中更新統(tǒng)計數(shù)據(jù)

　　(5)增加n1（l中樣本的數(shù)量）

　　(6)if n1 mod nmin=0 and 所有的樣本都是葉子節(jié)點且不在同一類中 then

　　(7)選擇滿足條件：(μai(Txj)－μai(T－Txj)）Δμmin的屬性

　　(8)選擇滿足條件：σai(Txj)≤σmax的屬性

　　(9)計算Zij

　　(10)if 至少選擇一個屬性and (Zij<Z1 or Zij>Z2) then

　　(11) Xa作為識別更多類的屬性,，并滿足高于μai(T－Txj)且低于σai(Txj)

　　(12)用一個分裂的內(nèi)部節(jié)點Xa代替l

　　(13)for 所有分裂的分支 do

　　(14)添加一個有初始數(shù)據(jù)的新葉子節(jié)點

　　(15)end if

　　(16) end if

　　第4行更新的數(shù)據(jù)是SARMT的Δμai(Txj)和σai(Txj),，如果只選擇一個屬性，選擇xa為分裂節(jié)點（第11行）,；如果有兩個或更多屬性滿足條件,，SARMT選擇屬性xa作為測試節(jié)點（第12~14行）。

　　與VFDT不同的是,，SARMT不依賴于樣本數(shù)量,，所以它可以生成和適應(yīng)沒有數(shù)量限制的樣本模型，從而比VFDT更加靈活,。

3實驗及結(jié)果分析

　　本文使用真實的數(shù)據(jù)集進(jìn)行了3個實驗,，數(shù)據(jù)隨機(jī)抽取100個樣本，對ECG信號,、PPG信號以及血壓的指標(biāo)進(jìn)行統(tǒng)計,，并且分別使用SARMT和VFDT算法，對結(jié)果的準(zhǔn)確性,、樹的大小和執(zhí)行時間進(jìn)行比較,。

　　心電圖（Electrocardiogram，ECG）是反映心臟興奮的電活動過程,，它可以鑒別與分析各種心律失常的情況,，也可以反映心肌受損的程度和發(fā)展過程以及心房、心室的功能結(jié)構(gòu)情況,。在日常生活中對患者進(jìn)行心電監(jiān)護(hù)可以為醫(yī)生臨床診斷提供參考,，對普通人而言，心電圖有助于用戶監(jiān)測身體健康狀態(tài),。光電容積脈搏波（Photoplethysmograph,，PPG）是心臟的搏動沿動脈血管和血流向外周傳播而形成的，脈搏波傳遞的快慢與人體心血管的多項參數(shù)都有密切關(guān)系,。血液在血管內(nèi)流動時,，無論心臟收縮或舒張，都對血管壁產(chǎn)生一定的壓力,。當(dāng)心臟收縮時大動脈里的壓力最高,，這時的血液稱為“高壓”；左心室舒張時,，大動脈里的壓力最低,，故稱為“低壓”,。平時所說的“血壓”實際上是指上臂肱動脈，即胳膊窩血管的血壓測定,，是大動脈血壓的間接測定,。正常的血壓是血液循環(huán)流動的前提，血壓在多種因素調(diào)節(jié)下保持正常,，從而為各組織器官提供足夠的血量,，以維持正常的新陳代謝。血壓過低或過高（低血壓,、高血壓）都會造成嚴(yán)重后果,，血壓消失則是死亡的前兆，這些都說明了血壓有極其重要的生物學(xué)意義,。

　　針對這三種采集的樣本數(shù)據(jù),，表1顯示了每個樣本類的參數(shù)值Δμamin和σmax（在實驗前，已計算參數(shù)值）,，在所有的實驗中,，假設(shè)γmin=0.99。

表2總結(jié)了實驗結(jié)果,，可以看出,，與VFDT相比，SARMT在所有的實驗中在執(zhí)行時間相當(dāng)?shù)那闆r下精度更高,?？梢钥隙ǖ氖牵趯嶒灁?shù)據(jù)集下,，SARMT比VFDT描述了更少的數(shù)據(jù)集,。雖然SARMT處理數(shù)據(jù)時使用了比較多的步驟，但是其使用數(shù)據(jù)集血壓,、PPG和ECG創(chuàng)建出的決策樹,，分類的精確度更高。

　　圖1~圖3顯示了VFDT和SARMT算法應(yīng)用在3種樣本數(shù)據(jù)中準(zhǔn)確度和所創(chuàng)建樹的大?。ü?jié)點個數(shù)）的對比,。

　　實驗表明，從第一個樣本開始,，使用SARMT描述的數(shù)據(jù)集可以更快速地捕獲數(shù)據(jù)的變化,。VFDT不能詳細(xì)地描述數(shù)據(jù)，而SARMT創(chuàng)建的是獨立的樣本,，可以詳細(xì)地描述數(shù)據(jù),。雖然ECG和PPG數(shù)據(jù)集需要建立一個更大的樹，但在執(zhí)行時間相當(dāng)?shù)那闆r下,，SARMT用于測試的節(jié)點分裂的速度比使用信息增益的Hoeffding樹（即VFDT)更快,。

4結(jié)論

　　本文基于VFDT算法提出了一種針對醫(yī)療數(shù)據(jù)的統(tǒng)計決策樹的分類算法——SARMT算法,。實驗表明，SARMT是一種適合數(shù)據(jù)流分類的方法,，通過比較實驗結(jié)果，SARMT可以實現(xiàn)在執(zhí)行時間相當(dāng)?shù)那闆r下,，保持實驗良好的準(zhǔn)確性,。與VFDT相比，SARMT描述了比較小的數(shù)據(jù)集,，因為它不像VFDT的分裂節(jié)點的方法依賴于樣品的數(shù)量,。在未來的工作中，希望可以使用SARMT算法處理一些概念漂移的問題,，添加一個自動估計參數(shù)并且通過有噪音的數(shù)據(jù)集來擴(kuò)展實驗,。

　　參考文獻(xiàn)

　　［1］ 譚俊璐,武建華.基于決策樹規(guī)則的分類算法研究［J］.計算機(jī)工程與設(shè)計,， 2010,，31(5)：10171019.

　　［2］ 顏延,秦興彬,樊建平,等.醫(yī)療健康大數(shù)據(jù)研究綜述［J］.科研信息化技術(shù)與應(yīng)用,，2014,5(6):316.

　?。?］ PATIL A, ATTAR V. Framework for performance comparison of classifiers［C］. Proceedings of the International Conference on Soft Computing for Problem Solving (SocProS 2011)， Springer India, 2012: 681689.

　?。?］ DONMINGOS P,， HULTEN G. Mining highspeed data streams［C］. In Proceedings of the sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, USA, 2000：7180.

　　［5］ BIFET A. Adaptive stream mining: pattern learning and mining from evolving data streams［C］.Proceedings of the 2010 Conference on Adaptive Stream Mining, Ios Press, 2010: 112129.

　?。?］ 晉愛蓮,耿麗娜,薄芳芳.多標(biāo)簽決策樹分類在數(shù)字醫(yī)學(xué)圖像分類中的應(yīng)用［J］.中國數(shù)字醫(yī)學(xué),2013,8(3):9092.

　?。?］ 鄭偉發(fā),李培亮,鄭梁珠,等.高速數(shù)據(jù)鏈的挖掘算法——VFDT 算法［J］.廣東商學(xué)院學(xué)報,2002(S2):118120.

　　［8］ 馬希驁,王國胤,于洪.決策域分布保持的啟發(fā)式屬性約簡方法［J］.軟件學(xué)報,，2014(8):17611780.