王旭晨，陳小惠

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

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

　　關鍵詞：醫療數據；決策樹；關聯規則；

0引言

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

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

1相關研究方法

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

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

2統計關聯規則決策樹

　　2.1統計關聯規則

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

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

　　2.2SARMT算法

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

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

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

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

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

　　（2）ai在類xj中應該提供一個統一行為。

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

　　SARMT算法描述如下：

　　(1)SARMT是一個根節點

　　(2)for each樣本e do

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

　　(4)在l中更新統計數據

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

　　(6)if n1 mod nmin=0 and 所有的樣本都是葉子節點且不在同一類中 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)用一個分裂的內部節點Xa代替l

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

　　(14)添加一個有初始數據的新葉子節點

　　(15)end if

　　(16) end if

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

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

3實驗及結果分析

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

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

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

表2總結了實驗結果，可以看出，與VFDT相比，SARMT在所有的實驗中在執行時間相當的情況下精度更高。可以肯定的是，在實驗數據集下，SARMT比VFDT描述了更少的數據集。雖然SARMT處理數據時使用了比較多的步驟，但是其使用數據集血壓、PPG和ECG創建出的決策樹，分類的精確度更高。

　　圖1~圖3顯示了VFDT和SARMT算法應用在3種樣本數據中準確度和所創建樹的大小（節點個數）的對比。

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

4結論

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

　　參考文獻

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

　　［2］ 顏延,秦興彬,樊建平,等.醫療健康大數據研究綜述［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.

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

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

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

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