王旭晨，陳小惠

　　（南京郵電大學 自動化學院，江蘇 南京210023）

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

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

0引言

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

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

1相關研究方法

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

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

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

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

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

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

　　2.2SARMT算法

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

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

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

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

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

　?。?）ai在類xj中應該提供一個統(tǒng)一行為。

　　為了滿足這些條件，限制興趣度的使用。標準誤差置信水平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ù)量，所以它可以生成和適應沒有數(shù)量限制的樣本模型，從而比VFDT更加靈活。

3實驗及結果分析

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

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

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

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

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

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

4結論

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

　　參考文獻

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

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

　　［3］ 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.

　?。?］ 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.

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

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

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