王曉麗 奚克敏 劉占波

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

關(guān)鍵詞： Apriori;關(guān)聯(lián)分析;數(shù)據(jù)挖掘;醫(yī)學信息學

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

1? 關(guān)聯(lián)規(guī)則及其抽象描述

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

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

2? 關(guān)聯(lián)規(guī)則暴力算法

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

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

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

3? Apriori算法

3.1? 算法基本思想

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

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