用改進Apriori算法確定藥房處方藥物的關聯規則

黃黎明，劉振宇

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

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

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

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

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

1 背景

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

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

2 本系統的目的和優勢

文中研究的目的是設計和實施一個系統，它可以找到藥房中藥物之間的關聯。在這些藥物中發現這種關聯具有以下優點：

1）幫助藥店內部設計和合理安排藥物；

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

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

文中，首先解釋了本研究中應用的數據挖掘算法和方法。然后，解釋這個算法在數據集上的實現，最后得到規則和結果。

3 論文的創新點

1）提出的改進算法相比較傳統Apriori算法內存消耗和時間消耗低。

2）無論是稀疏數據集還是密集數據集中新方法在時間消耗和內存消耗上都要優于傳統數據挖掘算法。

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

4 研究方法

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

4.1 算法描述

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

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

1）尋找傳統的項目集；

2）根據找到的集合構造關聯規則；

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

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

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

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

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

4.2 本文算法

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

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

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

過程1：

輸入：數據庫D，最小支持度。

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

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

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

步驟4：一旦發現最大的頻繁項目集，根據Apriori屬性其所有非空子集是頻繁的。

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

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

過程2：

輸入：修剪數據庫D1，最小支持度

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

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

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

輸出：剩余頻繁項目集。

4.3 支持度

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

4.4 置信度

5 應用Apriori算法

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

6 結果

規則1顯示了獲得的關聯規則。然后，研究獲得的規則。

規則1和2：

規則1:如果維生素D3，則鈣D片；

規則2:如果鈣-D則維生素D3。

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

圖1 藥物關系圖

表1 Apriori算法的結果

規則3：如奧美拉唑則甲硝唑

規則10：如甲硝唑則奧美拉唑

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

唑具有抗潰瘍作用。為了治愈消化道潰瘍，這兩種藥物大多是一起開處方。更具體地說，如果開處方甲硝唑，奧美拉唑的處方概率為28.6%。

規則4：如果維生素D3則吡羅昔康G

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

規則5：如果倍他米松則茶堿G

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

規則6：如阿莫西林則甲硝唑

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

7 結論

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

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