王旭晨，陳小惠

　?。暇┼]電大學(xué) 自動(dòng)化學(xué)院，江蘇 南京210023）

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

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

0引言

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

　　分類任務(wù)的目標(biāo)［34］是建立一個(gè)模型來描述和區(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)行評(píng)估測(cè)量，并且對(duì)原始的決策樹算法進(jìn)行了優(yōu)化。文獻(xiàn)［6］指出該算法的一些不足，例如它需要足夠多的葉子節(jié)點(diǎn)保證該樹的增長(zhǎng)，因此需要大量的數(shù)據(jù)樣本提供這些信息。然而，醫(yī)療行業(yè)總體數(shù)據(jù)存儲(chǔ)量不是很大，且各醫(yī)療機(jī)構(gòu)之間的差異比較大，具體到某一種病情的可用數(shù)據(jù)樣本就更少了。所以在數(shù)據(jù)存儲(chǔ)量不是很多的情況下，VFDT算法的準(zhǔn)確性和效率都不是很高。

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

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

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

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

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

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

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

　　2.2SARMT算法

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

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

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

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

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

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

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

　　SARMT算法描述如下：

　　(1)SARMT是一個(gè)根節(jié)點(diǎn)

　　(2)for each樣本e do

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

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

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

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

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

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

　　(9)計(jì)算Zij

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

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

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

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

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

　　(15)end if

　　(16) end if

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

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

3實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

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

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

4結(jié)論

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

　　參考文獻(xiàn)

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

　?。?］ 顏延,秦興彬,樊建平,等.醫(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.

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

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

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