用改進Apriori算法確定藥房處方藥物的關聯(lián)規(guī)則

黃黎明，劉振宇

（南華大學計算機學院，湖南衡陽 421001）

不同領域數(shù)據(jù)日益增長以及通過數(shù)據(jù)分析獲得有用信息和結果的需求使研究人員面臨各種困難。數(shù)據(jù)收集本身不會簡單地獲得有用的結果。因此，有必要將數(shù)據(jù)作為原材料進行處理，以便通過執(zhí)行分析方法來提取有用的信息。另外，如果沒有計算機或強大的分析工具的幫助，很難從數(shù)據(jù)庫手工或可視化地獲得有用的結果[1]。數(shù)據(jù)庫中的知識發(fā)現(xiàn)（KDD）是利用全自動方法從數(shù)據(jù)庫中分析和提取有用信息的一般方法，KDD是從數(shù)據(jù)集合中發(fā)現(xiàn)有用知識的過程[2]。這種廣泛使用的數(shù)據(jù)挖掘技術是一個過程，包括數(shù)據(jù)準備和選擇，數(shù)據(jù)清理，結合數(shù)據(jù)集的先驗知識和解釋觀測結果的精確解。KDD的主要應用領域包括但不限于營銷，電信和制造領域。

最終，KDD的概念已經(jīng)擴展到包括知識發(fā)現(xiàn)的所有階段。數(shù)據(jù)挖掘是指KDD的一個階段，其中學習算法被應用于數(shù)據(jù)[2]。事實上，這個概念已經(jīng)擴展到隨著時間的推移并在利用數(shù)據(jù)挖掘之后的知識發(fā)現(xiàn)的整個階段[18]；因此，數(shù)據(jù)挖掘也可能涉及知識發(fā)現(xiàn)的整個過程[3-4]。

在衛(wèi)生保健方面，數(shù)據(jù)挖掘得到了重視。特別是對藥物數(shù)據(jù)進行了一些研究[5-6]。一般來說，與其他領域產(chǎn)生的數(shù)據(jù)相比，醫(yī)療數(shù)據(jù)是獨一無二的。因此，他們需要更高的精度，因為處方包含個人的私人信息，其中簡單的錯誤會導致相當多的倫理問題。據(jù)觀察，由于越來越多地使用技術，特別是基于互聯(lián)網(wǎng)的處方，遇到了一些問題；因此，必須考慮其后果，以減少這些問題的范圍。世界衛(wèi)生組織指出，發(fā)展中國家的許多問題處方?jīng)]有適當修復[16]。此外，不正確或過度的使用藥品與個人的心態(tài)有關，他們只是覺得更多的藥品消費會導致更快的康復療程。

文中，已經(jīng)嘗試澄清醫(yī)療處方給藥房帶來的藥物是相互依賴的。為了實現(xiàn)這一目標，必須提供一個完全真實的數(shù)據(jù)庫，從中可以提取有效的信息。在這方面，暫時沒有發(fā)現(xiàn)可供研究人員輕松獲取的數(shù)據(jù)庫。因此，藥店的信息是人工收集的，這是非常耗時的任務。

1 背景

近年來，已經(jīng)發(fā)表了許多關于購買組合分析的論文，并提出了藥店最佳銷售藥品的新方法。還有一些方法可以通過差異化銷售表示選定的最大利潤。例如，ChEMBL是一個具有醫(yī)學性質并已被人工收集的大型信息數(shù)據(jù)庫[13]。為了提取有用的信息，應該在數(shù)據(jù)庫中測試假設條件，然后跟蹤錯誤事件。這些被解決的案例可以被視為數(shù)據(jù)挖掘問題，其中模式檢測是這方面的一個非常重要的工具。在大多數(shù)提及的論文中，購買組合分析更受歡迎。然而有人開發(fā)了一個特殊的軟件系統(tǒng)[14]，其中由用戶/患者提供的癥狀是輸入，系統(tǒng)然后根據(jù)癥狀開藥。在志愿者協(xié)助下，用戶也可以對其他人推薦的新藥進行初步評估。

美國食品和藥物管理局（FDA）還利用數(shù)據(jù)挖掘方法在其數(shù)據(jù)庫中使用了有關藥物副作用的信息[15]。為此，可以比傳統(tǒng)方法提前5年確定藥物的副作用，成功率為67%[9]。

2 本系統(tǒng)的目的和優(yōu)勢

文中研究的目的是設計和實施一個系統(tǒng)，它可以找到藥房中藥物之間的關聯(lián)。在這些藥物中發(fā)現(xiàn)這種關聯(lián)具有以下優(yōu)點：

1）幫助藥店內(nèi)部設計和合理安排藥物；

2）考慮保險公司對藥物集合的折扣；

3）準備相關藥物，以盡量減少或避免缺少相關處方藥；因為如果處方中的所有藥物都有，大多數(shù)人通常會從藥店購買藥物。

文中，首先解釋了本研究中應用的數(shù)據(jù)挖掘算法和方法。然后，解釋這個算法在數(shù)據(jù)集上的實現(xiàn)，最后得到規(guī)則和結果。

3 論文的創(chuàng)新點

1）提出的改進算法相比較傳統(tǒng)Apriori算法內(nèi)存消耗和時間消耗低。

2）無論是稀疏數(shù)據(jù)集還是密集數(shù)據(jù)集中新方法在時間消耗和內(nèi)存消耗上都要優(yōu)于傳統(tǒng)數(shù)據(jù)挖掘算法。

3）該方案不產(chǎn)生候選項目集，且僅為剪枝數(shù)據(jù)庫構建FP-Tree，這樣數(shù)據(jù)庫可以很容易地裝入主存。因此節(jié)省了很多時間和空間。

4 研究方法

為了找到藥物之間的關聯(lián)，應該有一個完整的數(shù)據(jù)庫來提取必要的信息。該數(shù)據(jù)庫應包含每種藥物的名稱，類型，代碼，劑量和條件?？傊?，這項研究的數(shù)據(jù)庫包括3 444種藥物（藥物）。為了構建這樣的數(shù)據(jù)庫，處方在藥店人工收集的。然后，編寫軟件代碼用于將這些處方輸入到數(shù)據(jù)庫中。在下一步中，為了使本研究中應用的數(shù)據(jù)挖掘軟件能夠輕松地處理該數(shù)據(jù)庫，該數(shù)據(jù)庫中的數(shù)據(jù)被轉換為單一格式。然后，從這些數(shù)據(jù)集中提取關聯(lián)規(guī)則。為此，應用了包含不同數(shù)據(jù)挖掘算法的SPSS Clementine軟件[8]。Apriori算法是求解關聯(lián)規(guī)則的算法之一，然后應用于本研究中。這種算法的優(yōu)點是它將搜索問題減少到可控和可管理的大小[7]。這對于減少搜索空間也非常有用。

4.1 算法描述

該算法是在數(shù)據(jù)庫或數(shù)據(jù)集內(nèi)的數(shù)據(jù)之間查找關聯(lián)規(guī)則的傳統(tǒng)算法之一。這些規(guī)則主要基于數(shù)據(jù)庫內(nèi)的交易和項目[7]。在這個討論中，項目是指一組相互關聯(lián)的數(shù)據(jù)，它傳達了一個概念（對象或實體）[10]，其中應該找到一些關聯(lián)。實際上，一個項目可以是單個成員，只包含一個數(shù)據(jù)。一組放在一起并構建一個帶有記錄的工作單元的項目稱為事務處理[11]。例如，在商店中，來自商店的顧客的購買組合是交易，并且購買組合內(nèi)的購買物品是其物品。這些項目中的每一個都包含一個或多個數(shù)據(jù)片段，這些數(shù)據(jù)片段可以是項目編號，項目名稱/標識，以及店內(nèi)商品的商品價格。

該算法在以下兩個步驟中工作：

1）尋找傳統(tǒng)的項目集；

2）根據(jù)找到的集合構造關聯(lián)規(guī)則；

這個算法考慮了以下兩個假設：

1）迭代項集的每個子集都是迭代的。如果假設集合{a，b，c}是迭代的，那么集合{a，b}也是迭代的[7]；

2）非迭代項集的每個超集都是非迭代的[7]。

如果集合{a，b}被假定為非迭代的，那么集合{a，b，c}也是非迭代的[12]。

Apriori[7]從每個時間長度為K的所選項目集構造一系列長度為K+1的大型項目集，并持續(xù)到達到具有最長長度的項集，前提是支持度超過了所需的閾。

4.2 本文算法

提出的該算法基于Apriori屬性[2]，即所有頻繁項目集的非空子集也頻繁。

算法有兩個過程。在第一個過程中，在數(shù)據(jù)庫中找到所有這些重復出現(xiàn)的最大交易稱為最大頻繁項集[15]。然后根據(jù)Apriori屬性獲得這些最大頻繁項目集的所有非空子集。掃描數(shù)據(jù)庫到找到頻繁的元素。可能有許多項目是1項集頻繁，但不在最大的頻繁交易中。因此，通過僅考慮數(shù)據(jù)庫中的包含1項集但不包括在最大頻繁項目集中的頻繁元素的那些事務來修剪數(shù)據(jù)庫?，F(xiàn)在修剪了數(shù)據(jù)庫在平均情況下比實際數(shù)據(jù)庫小，最好情況下是沒有項目剩下。

對于第二個過程，將剪枝數(shù)據(jù)庫作為輸入并掃描剪枝數(shù)據(jù)庫，一旦發(fā)現(xiàn)1項集頻繁并從交易中刪除那些不是1-項集頻繁的元素。然后僅基于修剪事務構造FP-tree[6]。通過這種方式，它減少了FP-tree的內(nèi)存問題，因為數(shù)據(jù)庫大部分都減少了。在最好的情況下，不需要構建FP-tree，因為所有元素都在第一部先找到了。在最壞的情況下，如果沒有最大的頻繁交易存在，那么只有進行第二部，計算性能與FP-tree相同。這個想法關鍵之一在找到最大頻繁項集和形成FP-tree之后修剪數(shù)據(jù)庫，修剪數(shù)據(jù)從而減少了FP-tree中的內(nèi)存問題并使快速挖掘過程成為可能。更詳細的步驟如下：

過程1：

輸入：數(shù)據(jù)庫D，最小支持度。

第1步：取2維數(shù)組；將帶重復次數(shù)計數(shù)的事務置于2維數(shù)組中。

步驟2：根據(jù)每個模式的長度以遞增順序排列交易。

第3步：從數(shù)量大于或等于最小支持度的數(shù)組中查找稱為最大頻繁項集或事務的最大事務（k-項集）。如果k-項集計數(shù)小于最小支持度，然后找到k-項集和（k-1）項集連接為下一個（k-1）最大項目集合等，直到?jīng)]有發(fā)現(xiàn)項目集計數(shù)比最低的支持更大的項目集。如果沒有找到這樣的事務，則轉到過程2。

步驟4：一旦發(fā)現(xiàn)最大的頻繁項目集，根據(jù)Apriori屬性其所有非空子集是頻繁的。

步驟5：剩余的項目集不包含在最大頻繁項目集中，但他們很頻繁。因此，找到所有頻繁的1項目集并修剪僅考慮那些包含頻繁的1-項集元素但不包含在最大頻繁項中的事務數(shù)據(jù)庫。

輸出：部分或全部頻繁項目集，修剪數(shù)據(jù)庫D1。

過程2：

輸入：修剪數(shù)據(jù)庫D1，最小支持度

第1步：從修剪過的數(shù)據(jù)庫中查找頻繁的1項目集；刪除所有這些

不是頻繁的1-項集的項目。

步驟2：通過前面討論的FP-樹算法[6]的程序按以下步驟構造剩余頻繁項目集的FP-tree。

輸出：剩余頻繁項目集。

4.3 支持度

支持度表示前項與后項在一個數(shù)據(jù)集中同時出現(xiàn)的頻率。在這個討論中，交易意味著處方。術語“元組”有時用來代替事務。換句話說，規(guī)則“支持度”表示包括集合A和B的交易與集合D（1）中可用的總交易的比率，

4.4 置信度

5 應用Apriori算法

本研究的輸入數(shù)據(jù)被轉換為文本文件，然后作為輸入源應用于Clementine。存儲的數(shù)據(jù)從文件中讀取并發(fā)送到流。在我們提出的Apriori算法實現(xiàn)后，獲得了9條規(guī)則，這些規(guī)則顯示為先行和后續(xù)。圖1顯示了藥物之間的關聯(lián)。在這個圖中，較強的關聯(lián)用粗線表示，較弱的關聯(lián)用虛線表示。

6 結果

規(guī)則1顯示了獲得的關聯(lián)規(guī)則。然后，研究獲得的規(guī)則。

規(guī)則1和2：

規(guī)則1:如果維生素D3，則鈣D片；

規(guī)則2:如果鈣-D則維生素D3。

得到的結果顯示維生素D和鈣都具有最大置信系數(shù)，并在表格的最上面一行給出。這兩種藥物都被稱為先導及后繼的。維生素D和鈣是人體內(nèi)兩種重要的物質。鈣在骨骼力量，牙齒，凝血，神經(jīng)收縮和肌肉中起著有效的作用。

圖1 藥物關系圖

表1 Apriori算法的結果

規(guī)則3：如奧美拉唑則甲硝唑

規(guī)則10：如甲硝唑則奧美拉唑

甲硝唑和奧美拉唑是用于治療消化問題的藥物。甲硝唑是一種抗菌藥物，奧美拉

唑具有抗?jié)冏饔谩榱酥斡罎儯@兩種藥物大多是一起開處方。更具體地說，如果開處方甲硝唑，奧美拉唑的處方概率為28.6%。

規(guī)則4：如果維生素D3則吡羅昔康G

吡羅昔康凝膠是一種消炎藥，對緩解疼痛，肌肉僵硬和炎癥非常有效。維生素D對增強骨骼，增強神經(jīng)，治療收縮和肌肉痙攣以及治療肌肉無力非常有用。該規(guī)則意味著，如果患者服用維生素D，那么匹羅昔康凝膠也將以25%的置信系數(shù)進行處方。

規(guī)則5：如果倍他米松則茶堿G

茶堿G用于治療支氣管痙攣，并與倍他米松一起處方，作為治療季節(jié)性過敏，哮喘和支氣管炎的抗組胺藥。

規(guī)則6：如阿莫西林則甲硝唑

阿莫西林是青霉素類抗生素藥物，用于治療許多感染，特別是耳部或呼吸道感染。甲硝唑也是一種抗菌藥物，用于治療感染。

7 結論

本文的目的是基于藥店的處方來獲取藥物間的關聯(lián)規(guī)則。由于處方藥不是隨機排列在一起，而是根據(jù)患者的疾病和癥狀，使用處方內(nèi)藥物可以發(fā)現(xiàn)處方藥之間的關聯(lián)。為此，從藥店的銷售訂單收集處方及其藥物數(shù)據(jù)庫。為此，編寫一個程序。然后將這些數(shù)據(jù)的格式轉換為適用于Clementine[8]軟件的格式。通過在此軟件中應用Apriori算法來識別一些關聯(lián)規(guī)則。已經(jīng)確定維生素D和鈣是最相關的藥物，并且在大多數(shù)處方中彼此應用。奧美拉唑和甲硝唑在關聯(lián)方面排名第二。本文還發(fā)現(xiàn)并討論了其他關聯(lián)規(guī)則。

應用其他算法找到這些數(shù)據(jù)的關聯(lián)規(guī)則是繼續(xù)本文工作的一個建議思路。處理這些藥物在處方中關聯(lián)的其他方面也是另一個建議。在這項研究中解決的最重要的問題是難以完成的數(shù)據(jù)收集，因為測試中參與的藥店是手工保存處方。他們必須轉換成電腦處方。因此，建議通過電腦收集那些接受處方的藥店的數(shù)據(jù)，如果有幾家藥店，可以進行比較。如果收集來自不同地理區(qū)域的藥店的數(shù)據(jù)樣本，則可以獲得更好的比較結果。