基于Apriori算法的關聯規則分析

王曉麗 奚克敏 劉占波

摘? 要： 用糖尿病患者患病記錄作為實例詳細闡述了基于Apriori算法的關聯規則問題。探討了Apriori算法在關聯規則中求解頻繁項集的基本思想，并用實例描述了算法的執行過程。

關鍵詞： Apriori;關聯分析;數據挖掘;醫學信息學

中圖分類號： TP393.4? ? 文獻標識碼： A? ? DOI：10.3969/j.issn.1003-6970.2019.02.005

【Abstract】： This paper elaborates the association rule based on Apriori algorithm taking the diabetic patient's disease record as a case. The core idea of association rule based on Apriori algorithm for mining large itemsets is discusses， furthemore the example show the execution process of the algorithm.

【Key words】： Apriori; Association analysis; Data mining; Medical informatics

0? 引言

1993年，Agrawal等人借鑒了Petr Hjek[1]的邏輯推理思想，提出了關聯規則的概念[2]。Agrawal舉出了一個最典型的使用案例，超市購物籃的購物分析（basket analysis）。在顧客的大量購物中超市發現了一個有趣的現象，40%左右的年輕男士購買完尿布也會購買啤酒。于是超市將尿布和啤酒放在一起進行促銷，使得尿布和啤酒的銷量大增。利用類似的關聯發現超市可以獲得各種關于顧客的相似商品購買習慣，這樣能夠幫助其開發更好的營銷策略從而利于商品銷售[3]。關聯規則的實際應用遠不僅如此，在金融分析、工程建筑、鐵路航空、大數據、網絡安全、醫療衛生、生物醫藥等各個領域都與關聯分析緊密相關。目前關聯規則已成為數據挖掘的一個重要研究方向， 大量的科研人員改進相關算法并將其應用于具體案例中。在關聯規則各種算法中，Agrawal等人在1994年發表的Apriori算法是目前影響最為深遠的算法之一[4]，本文基于Apriori算法對經典的關聯規則進行分析并對其執行過程進行探討。

1? 關聯規則及其抽象描述

在實際中患者往往會同時患有多種疾病，很多疾病都是由并發癥所引起，比如糖尿病往往會同時與高血壓、高血脂、冠心病、胰腺炎、肥胖癥、痛風、酒精性肝炎、周圍神經炎等相互關聯，還會引起視網膜病變，腎臟及神經性病變等并發癥[5]。醫療從業人員往往會在這些大量的患者電子病例數據庫中尋找這些疾病的相互關聯性，疾病的種類可能是成千上萬，電子病例數據庫中的病例數量可以達到幾十萬條以上[6]。

為了描述方便，將幾萬種疾病種類簡化為5種：糖尿病，高血壓，脂肪肝，白內障，腎病。即假設患者病例中只患這5種或5類疾病，并假設這5種疾病在病例數據庫中按照字典序號排列，既糖尿病排在高血壓的前面。將病例數據庫中的幾十萬條病例簡化為10條并去除雜項。具體描述如圖1所示。

2? 關聯規則暴力算法

根據關聯規則的基本定義可以得到最基本的求解關聯規則簡單的暴力算法：對于m個項組成的集合，首先用窮舉法生成所有的關聯規則，然后對每一個關聯規則掃描數據庫計算出支持度和置信度，和規定的閾值進行比較來生成強關聯規則。根據排列組合可以知道利用窮舉方式生成的所有關聯規則數量為：，并且每一個關聯規則計算支持度和置信度都需要掃描事務數據庫一次，掃描事物數據庫的時間復雜度將達到指數級。

利用暴力算法亦可先窮舉出所有的頻繁項集，共有個，然后用頻繁項集再生成強關聯規則?？梢钥闯鲞@2種方法的時間復雜度都是指數級。

如果設定的最小支持度和最小置信度很小接近于零，那么暴力算法窮舉出的所有關聯規則都是強關聯規則，任何改進算法同暴力算法一樣都需要生成所有的關聯規則。在實際應用中給定的閾值不是很低時，求得的強關聯規則往往沒有那么多，尤其是頻繁項集數可能很少。對于一個幾十萬條記錄，成千上萬種圖書的圖書管理系統尋找關聯規則，利用時間復雜度是指數級的暴力算法顯然不是很好的選擇。這就需要我們另外尋找更為高效的算法應用于關聯分析。

3? Apriori算法

3.1? 算法基本思想

強關聯規則的生成需要滿足2點：最小支持度，最小置信度。于是可以通過某種方法先生成滿足最小支持度的項集，即頻繁項集，不頻繁項集及所對應的關聯規則可以迅速排除。然后通過頻繁項集來得到強關聯規則，生成方法可以簡單對每個頻繁項集用暴力法生成其每個非空子集，然后用該集合作為關聯規則的前項，用頻繁項集和子集的差集作為關聯規則后項，如果其置信度大于最小置信度則生成強關聯規則。Apriori算法是快速生成頻繁項集的一種算法。

Apriori算法首先將項集I中的每一項生成1-項集（生成的項集可能是頻繁項集，也可能不是頻繁項集，稱之為候選項集），然后掃描數據庫D，將所有1-項集和最小支持度進行比較生成頻繁1-項集。將頻繁1-項集中的項兩兩拼接生成候選2-項集，再次掃描數據庫D，將所有由頻繁1-項集產生的候選2-項集和最小支持度進行比較生成頻繁2-項集。通過頻繁2-項集生成候選3-項集，然后生成頻繁3-項集…直到沒有新的頻繁項集產生為止。在頻繁（k-1）- 項集拼接成候選k-項集的過程中，需要找出前k-2項相同，最后一項不同的項集進行依次兩兩拼接，由于項集中的項已經按照字典序號排列，因此生成的項集不會產生重復項。