魏大順，張德林，董瑞國

(1.徐州醫(yī)科大學(xué) 醫(yī)學(xué)信息學(xué)院,江蘇 徐州 221000；2.徐州醫(yī)科大學(xué)附屬醫(yī)院,江蘇 徐州 221000)

0 引言

由于醫(yī)療報銷等問題，在圍術(shù)期過程中醫(yī)生要控制、縮短平均住院日，術(shù)后如果沒有較嚴(yán)重并發(fā)癥，一般要求病人盡快出院；但是患者又擔(dān)心康復(fù)不徹底；而國家又沒有相關(guān)的出院技術(shù)標(biāo)準(zhǔn)，因此在患者各項生理指標(biāo)正常的情況下，我們提出一種以病人術(shù)后活動指標(biāo)作為一種檢測是否可以出院的方法。通過患者腕帶標(biāo)簽，局域網(wǎng)內(nèi)的接收器檢測這些標(biāo)簽，并向位置軟體傳遞即時位置狀態(tài)等資料，具體如圖1所示。FP-growth作為一種有效的關(guān)聯(lián)規(guī)則挖掘算法已經(jīng)被用于許多領(lǐng)域，許多學(xué)者也針對不同的應(yīng)用場景或者算法本身進行了許多改進。如基于節(jié)點表的FP-growth算法改進[1]、基于FP-tree的快速構(gòu)建算法[2]和無項頭的FP-growth[3]算法。但在醫(yī)療應(yīng)用場景下這些算法都很難發(fā)揮他們的優(yōu)勢，特別是在處理RFID所產(chǎn)生的事務(wù)數(shù)據(jù)，這主要是由于其高維度性、高無用性、高冗余性等特性導(dǎo)致[4]。例如基于節(jié)點表的FP-growth算法通過新增的節(jié)點表和頻繁模式樹兩者中共通的項，從而進行頻繁項集挖掘，然而當(dāng)數(shù)據(jù)維度越高，兩者中共通的項則越多，挖掘效率因此也就越低下；基于FP-growth的快速構(gòu)建算法通過動態(tài)調(diào)整各項的順序從而減少數(shù)據(jù)庫訪問頻度，但是醫(yī)療數(shù)據(jù)具有高無用性以及高冗余性，因此若利用此方法處理醫(yī)療數(shù)據(jù)將會消耗大量的內(nèi)存；無項頭的FP-growth算法雖然可以精簡生成的關(guān)聯(lián)規(guī)則，但是生成的關(guān)聯(lián)規(guī)則中依然還會存在大量的冗余規(guī)則。在實際應(yīng)用場景中，醫(yī)療人員更多的是希望在他們已有的專業(yè)判斷下，進一步從某些關(guān)鍵因素進行確認(rèn)患者是否達到出院標(biāo)準(zhǔn)，比如患者在術(shù)后的行動時間與行動距離是否存在關(guān)聯(lián)性、活動范圍與術(shù)后時間是否存在關(guān)聯(lián)性。若使用原始FP-growth或者目前已有的改進算法去解決這一需求，不僅無法針對性的進行關(guān)聯(lián)挖掘，而且會找出許多無用的關(guān)聯(lián)規(guī)則[5]，而這必然會嚴(yán)重影響挖掘效率，降低挖掘質(zhì)量。本文針對此種應(yīng)用場景，以胸外科數(shù)據(jù)為作為實驗數(shù)據(jù)，提出了一種改進的FP-growth算法。該算法首先通過計算數(shù)據(jù)集中各屬性的條件信息熵[6]進行約減；創(chuàng)建FP-Tree，根據(jù)判斷分支中是否含有決策項以及項重要度大小進行相應(yīng)的剪枝。該算法從整體上縮減了事務(wù)數(shù)據(jù)庫的規(guī)模，對FP-tree進行了橫向和縱向剪枝壓縮，從而簡化了最終頻繁項集的挖掘，提高了挖掘效率，降低了算法運行所需內(nèi)存與CPU。實驗結(jié)果表明，本文改進方法在可接受的精度范圍內(nèi)，挖掘效率高于已有主要挖掘算法。

圖1 患者活動RFID射頻識別

1 基礎(chǔ)知識

本節(jié)介紹本文所需的基本知識，主要是RFID以及FP-growth算法。

1.1 基本定義

定義1：RFID，無線射頻識別即射頻識別技術(shù)(radio frequency identification，RFID)，是自動識別技術(shù)的一種，通過無線射頻方式進行非接觸雙向數(shù)據(jù)通信，利用無線射頻方式對記錄媒體(電子標(biāo)簽或射頻卡)進行讀寫，從而達到識別目標(biāo)和數(shù)據(jù)交換的目的。

定義2：FP-growth，F(xiàn)P-Growth算法采取如下分治策略：將提供頻繁項集的數(shù)據(jù)庫壓縮到一棵頻繁模式樹(FP-tree)，但仍保留項集關(guān)聯(lián)信息。

定義3：支持度，確定規(guī)則可以用于給定數(shù)據(jù)集的頻繁程度，公式如下：

(1)

其中:N是事務(wù)的總數(shù)，X,Y為對應(yīng)的屬性。

1.2 FP-gowth算法流程

輸入：事務(wù)數(shù)據(jù)庫(transaction database,TD);最小支持度(minimum support,MinSup)[2]。

輸出：頻繁模式的完全集。

1)對TD中的事務(wù)進行逐條遍歷,統(tǒng)計每項支持度，并且以集合F表示，并且按照支持度大小重新排列，最終得到頻繁項表L。

2)再一次對數(shù)據(jù)庫TD進行掃描,按照L中的順序?qū)D進行重新排序，得到TD′；

3)創(chuàng)建頻繁挖掘樹FP-tree,其中根節(jié)點為root,默認(rèn)值為空，將步驟2)得到的TD'中的數(shù)據(jù)按照順序插入FP-tree中，若數(shù)據(jù)節(jié)點第一次在FP-tree中出現(xiàn)，則新建節(jié)點，并計數(shù)1，若待插入的節(jié)點已經(jīng)存在于FP-tree中，則原計數(shù)加1，同時令項頭表為步驟1)中得到的L,且鏈頭為項頭，連接內(nèi)容相同的項；

4)對項集L中的項逆序挖掘頻繁項集。

2 對FP-growth算法的改進

FP-growth算法在處理事務(wù)庫時無法對無用屬性的篩選以及對特定關(guān)聯(lián)的挖掘，從而導(dǎo)致挖掘速度緩慢以及影響挖掘質(zhì)量。因此，本文提出了一種改進的驗證式挖掘算法—IEFP-growth(Information Entropy FP-growth)算法。通過對FP-growth挖掘前的屬性約減和FP-tree創(chuàng)建過程中的剪枝來進行優(yōu)化。該算法首先通過計算數(shù)據(jù)集中各屬性的條件信息熵[7]進行約減；在原算法掃描數(shù)據(jù)庫生成頻繁一項集的基礎(chǔ)上，創(chuàng)建FP-Tree，根據(jù)判斷分支中是否含有決策項以及項重要度IT(Item importance)大小進行相應(yīng)的剪枝，若不含決策項則進行剪枝，若含決策項且所在分支中含有項重要度大于重要度閾值的項則保留，否則進行剪枝。該算法首先從整體上縮減了事務(wù)數(shù)據(jù)庫的規(guī)模，其次對FP-tree進行了橫向壓縮，進而提高了整體挖掘速度與質(zhì)量。

剪枝依據(jù)性質(zhì)：

1)支持度大的項并不一定和決策項具有關(guān)聯(lián)；

2)支持度大于MinSup且重要度大于或等于IT的項一定和決策項具有一定程度的關(guān)聯(lián)。

2.1 IEFP-growth的算法流程

輸入：TD;MinSup;IT。

輸出：含決策屬性的頻繁模式集

1)對TD-事務(wù)數(shù)據(jù)庫進行屬性約減得到TD′;

(1)計算TD中除決策屬性[8]外每個屬性相對于決策屬性的條件信息熵，例如D相對于C的：

(2)

其中:D是決策屬性，C是條件屬性，U為論域，Xi,Yj分別是某一屬性的屬性集合。

(2)計算條件屬性集C中相對于決策屬性集D的主屬性Cr,并令P=Cr,B=C-Cr;

(3)計算條件信息熵H(D|P)，轉(zhuǎn)步驟(6)；

(4)對i=1…n,bi∈B中的每個屬性計算條件熵H(D|P∪bi),求:

SGF(bi,P,D)=H(D│P)-H(D|P∪bi)

(3)

得到屬性bi相對于決策屬性的重要度SGF;

(5)找出屬性bi,該bi可以讓SGF取得最大值，然后在P的后面追加bi，并且去掉使SGF為0的bi;

(6)如果H(D|P)=H(D|C),則轉(zhuǎn)步驟(7，否則轉(zhuǎn)步驟(4)；

(7)依次判斷p中每個屬性是否可以去掉，判斷順序是從p尾開始，p頭結(jié)束。假如a在coreC(D)中,則從a往前都不可約，算法結(jié)束；否則a是可約減的，于是把a從A中刪除。

(8)得到處理之后的TD′

2)第一次掃描TD′，除去小于MinSup的項，得到頻繁一項集L；

3)再次遍歷TD′，重新排列TD′，排序規(guī)則以L中各項的支持度為度量進行降序排序，得到TD″;

4)建立FP-tree根節(jié)點，值為null，將TD″中的事務(wù)依次插入，若分支中不含決策項則進行剪枝，若含決策項且所在分支中含有項重要度-SGF大于重要度閾值IT的項則保留，否則進行剪枝；若節(jié)點不存在，則新建并計數(shù)并置1，若節(jié)點存在，則計數(shù)加1；

5)對創(chuàng)建好的FP-tree進行頻繁項集的挖掘。

(1)獲取頭指針表中每一個元素的條件模式基；

(2)按照步驟1)至步驟4)的建樹步驟，對上一步驟獲得條件模式基建立條件FP樹；

(3)重復(fù)以上步驟，獲取條件模式基并構(gòu)建條件FP樹，直至無法構(gòu)建條件FP樹為止；

2.2 算法詳解

(1)以表1簡易患者活動事務(wù)數(shù)據(jù)庫-TD為例。

表1 患者活動事務(wù)數(shù)據(jù)庫TD

為使得RFID數(shù)據(jù)信息滿足挖掘要求，將活動時間、活動距離等數(shù)據(jù)以范圍表示。

計算各屬性重要度SGF:

H(D|C)=0.5

H(D|P)=1

SGF(活動時間,P,D)=H(D|)-H(D|半小時，)=0.049

SGF(心跳,P,D)=H(D|)-H(D|快，)=0

SGF(活動距離P,D)=H(D|)-H(D|5米以內(nèi)，)=0.311 278

根據(jù)屬性重要度SGF進行屬性約減得到表2。

(2)再次遍歷TD′,重新排列TD′，排序規(guī)則以L中各項的支持度為度量進行降序排序，得到TD″；

(3)在TD″的基礎(chǔ)上生成FP-tree，并且對根節(jié)點初始化，其中根節(jié)點名稱為root,默認(rèn)值為空。按照頻繁樹生

表2 約減后數(shù)據(jù)庫TD′

成規(guī)則，將TD″中事務(wù)逐條壓縮到頻繁樹中。若需驗證活動時間與活動距離是否存在關(guān)聯(lián)規(guī)則，則待插入的分支中不含有“活動時間”屬性，則舍棄該分支，若待插入分支中含有“活動時間”屬性且所在分支中含有項重要度大于重要度閾值IT的項則保留，否則進行剪枝；若節(jié)點不存在，則新建并計數(shù)并置1，若節(jié)點已經(jīng)在FP-tree中出現(xiàn)，則相應(yīng)的計數(shù)加1。

(4)利用項頭表和頻繁模式樹遞歸挖掘頻繁項集。

3 實驗與結(jié)果

本節(jié)通過將IEFP-growth算法與當(dāng)前效果較好的基于節(jié)點表的FP-growth算法以及原始FP-growth算法進行實驗對比，對比分析本文所提出的IEFP算法的挖掘效果；最后將挖掘結(jié)果與其對應(yīng)的生理指標(biāo)進行對比，證明所提方法具有一定的臨床可行性。

綜上所述，現(xiàn)階段，我國各大高中學(xué)校管理人員已經(jīng)有效地認(rèn)知到分層教學(xué)模式對于提升學(xué)生學(xué)習(xí)水平的重要性，并且在這種意識的引導(dǎo)下，正在積極開展化學(xué)分層教學(xué)活動，但是由于起步時間較晚，該種教學(xué)模式的教學(xué)成效并不顯著，因此相關(guān)的教職人員必須要將工作重心放到高中化學(xué)分層教學(xué)模式實施措施的研究上，結(jié)合實際情況，制訂出具有針對性的措施，以此來實現(xiàn)既定教學(xué)目標(biāo)。

3.1 實驗環(huán)境

軟件環(huán)境：pycharm編輯器；硬件環(huán)境：Intel(R)Core(TM)i5-7300HQCPU@ 2.50GHz，內(nèi)存為8G,64位Window10操作系統(tǒng)；

3.2 實驗一

隨機選取10 000條實驗數(shù)據(jù)，事務(wù)數(shù)據(jù)事務(wù)中項的頻繁項集支持度大多在0.04%到0.18%之間，分別測試FP-growth、基于節(jié)點表優(yōu)化的FP-growth和IEFP-growth算法在不同支持度下的消耗時間以及經(jīng)過差分隱私后的IEFP-tree的挖掘時間對比。詳細數(shù)據(jù)內(nèi)容見表3。

表3 不同算法運行時間對比圖

由表3可知，第一列是最小支持度，第二列、第三列和第四列分別是FP-growth算法、基于節(jié)點表優(yōu)化的FP-growth算法和IEFP-growth算法執(zhí)行時間，并且IEFP-growth在各支持度下的消耗時間都低于FP-growth原始算法和基于節(jié)點表的FP-growth算法所需要的時間。

圖2繪制了FP-growth、基于節(jié)點表的FP-growth算法和IEFP-growth在最小支持度變化下各自挖掘時間的變化及對比情況。

圖2 不同算法在不同支持度下的執(zhí)行時間對比圖

由圖2可以看出，隨著支持度的縮小，IEEP-growth算法相比于FP-growth算法以及基于節(jié)點表的FP-growth算法在相同支持度下所需時間更少，且隨著支持度的減小，所需時間增長速率緩慢，且支持度范圍在0.04～0.08之間，IEEP-growth消耗時間的增長速率明顯低于其他兩種算法，這表明支持度越小，IEFP-growth比原始FP-Growth、基于節(jié)點表的FP-growth挖掘能力越顯著。

3.3 實驗二

在不同事務(wù)量的情況下分別測試FP-growth、基于節(jié)點表優(yōu)化的nodetable-FP-growth和IEFP-growth算法，統(tǒng)計在不同事務(wù)量下的內(nèi)存消耗情況[9]。詳細數(shù)據(jù)見表4。

表4 不同算法所需內(nèi)存對比

由表4可知，第一列是事務(wù)量，第二列、第三列和第四列分別是FP-growth算法、基于節(jié)點表的FP-growth算法以及IEFP-growth算法在不同事務(wù)量情況下內(nèi)存利用率占比，并且IEFP-growth算法在各事務(wù)量情況下，特別是事務(wù)量越大的情況下，所需要的內(nèi)存相對于其他兩種算法都相對較少。

圖3繪制了FP-growth算法、基于節(jié)點表的FP-growth算法、以及經(jīng)過差分隱私保護的IEFP-tree算法在不同事務(wù)量變化下下各自內(nèi)存利用率的柱狀對比圖。

圖3 不同算法在不同事務(wù)量下所需內(nèi)存圖

3.4 實驗三

在不同事務(wù)量的情況下進行FP-growth、基于節(jié)點表優(yōu)化的FP-growth、IEFP-growth挖掘，統(tǒng)計在不同事務(wù)量情況下的CPU使用情況[10]。詳細數(shù)據(jù)見表5。

表5 不同算法所需CPU對比

如表5所示，第一列是事務(wù)量，第二列、第三列和第四列分別是FP-growth、基于節(jié)點表的FP-growth和IEFP-growth算法CPU利用率占比，并且IEFP-growth算法在各事務(wù)量情況下，特別是事務(wù)量越大的情況下，所需要的CPU相對于其他兩種算法都相對較少。

圖4繪制了FP-growth、IEFP-growth、基于節(jié)點表優(yōu)化的FP-growth以及經(jīng)過差分隱私保護的IEFP-tree算法在不同事務(wù)量變化下各自CPU利用率的變化。

圖4 不同算法CPU變化圖

從圖4可以看出，IEFP-growth算法所需CPU比FP-growth算法和基于節(jié)點表的FP-growth算法所需CPU少，且事務(wù)量越大，所需CPU差距越明顯。

3.5 實驗四

實驗選取10 000條事務(wù)數(shù)據(jù)，分別利用FP-growth算法、基于節(jié)點表的FP-growth算法以及IEFP-growth算法進行關(guān)聯(lián)規(guī)則挖掘，對挖掘得到的頻繁模式集分析其中含有決策屬性-活動時間的構(gòu)成比[11]，如圖5所示。

圖5 不同算法挖掘結(jié)果中頻繁項集構(gòu)成比圖

從圖5可以發(fā)現(xiàn)，IEFP-growth挖掘得到的頻繁項集中決策項占據(jù)了絕大部分，其中少部分不是決策屬性主要是在剪枝過程中由于重要度以及支持度等因素被減去，也就是說假設(shè)的關(guān)聯(lián)關(guān)系中存在少部分非關(guān)聯(lián)規(guī)則，而由FP-growth和基于節(jié)點表的FP-growth算法挖掘得到的頻繁項集中與決策屬性有關(guān)的頻繁項只占了很小的一部分。因此IEFP-growth算法可以很好地進行針對性的挖掘，對臨床具有一定的價值。

3.6 實驗五

為了證明本文所提方法具有一定的臨床指導(dǎo)意義，從電子病歷系統(tǒng)中提取100位患者闌尾炎患者術(shù)后不同時間內(nèi)白細胞數(shù)量平均值，如圖6所示，以及術(shù)后的活動距離平均值，如圖7所示。

圖6 術(shù)后白細胞變化

圖7 術(shù)后患者活動距離平均值

從圖6我們可以看出在天數(shù)為0時即未進行手術(shù)情況下，白細胞的數(shù)量達到了25 000/L以上，此時病人闌尾已經(jīng)發(fā)生壞死、穿孔等癥狀，但術(shù)后隨著時間的推移，白細胞數(shù)量逐漸下降，在第6天之后白細胞數(shù)量已經(jīng)趨近于正常水平，且在第八天之后患者辦理了出院，因此沒有了數(shù)據(jù)；從圖7我們可以看出，患者的活動距離隨著術(shù)后時間的推移逐步增加，結(jié)合圖6與圖7我們可以發(fā)現(xiàn)患者的活動距離與白細胞數(shù)量在術(shù)后一定時間內(nèi)具有一定的關(guān)聯(lián)性，而這也符合挖掘結(jié)果，因此利用RFID獲取的患者活動距離來挖掘數(shù)據(jù)間的關(guān)系并判斷是否達康復(fù)行為具有一定的臨床指導(dǎo)意義。

4 結(jié)語

本文通過挖掘RFID采集的患者活動信息數(shù)據(jù)，為醫(yī)療人員提供患者術(shù)后出院參考。

針對FP-growth算法在進行頻繁模式挖掘過程中，RFID采集的患者數(shù)據(jù)無關(guān)屬性過多以及無法進行目的性的挖掘從而引起挖掘效率和質(zhì)量低下的問題，提出一種驗證式挖掘算法——IEFP-growth算法。在對數(shù)據(jù)庫屬性約減的基礎(chǔ)上，根據(jù)判斷FP-tree分支中是否含有決策項以及項重要度大小進行相應(yīng)的橫向和縱向剪枝壓縮，簡化最終頻繁項集的挖掘，提高了挖掘效率和質(zhì)量，降低了算法運行所需內(nèi)存和CPU。實驗結(jié)果表明了IEFP-growth算法在時間效率、內(nèi)存與CPU利用率以及挖掘質(zhì)量上較傳統(tǒng)FP-growth算法都有所改進；并且通過對比分析患者術(shù)后白細胞與活動距離的變化趨勢，發(fā)現(xiàn)白細胞變化與活動距離在一定時間內(nèi)具有一定的關(guān)聯(lián)，證明該算法在臨床檢測上具有可行性與實用性[12-18]。