王曉麗 奚克敏 劉占波

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

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

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

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

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

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

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

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

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

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

3? Apriori算法

3.1? 算法基本思想

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

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