Apriori算法在數(shù)據(jù)挖掘中的應(yīng)用

南京工業(yè)大學(xué)浦江學(xué)院 圣文順 張林慧

導(dǎo)語：在信息化時(shí)代背景下，信息成為社會發(fā)展的重要推動力，數(shù)據(jù)則演變?yōu)槿藗兩鐣袨橐?guī)律分析與挖掘的基礎(chǔ)載體。數(shù)據(jù)挖掘是指從海量數(shù)據(jù)中挖掘出更有價(jià)值的信息元素，并運(yùn)用關(guān)聯(lián)規(guī)則將事物緊密聯(lián)系，分析預(yù)測人們的后續(xù)行為。本文圍繞數(shù)據(jù)挖掘這一主題，研究Apriori算法在數(shù)據(jù)挖掘中的應(yīng)用，從數(shù)據(jù)挖掘的基本概念、Apriori算法簡介及該算法在數(shù)據(jù)挖掘中的應(yīng)用三個(gè)方面進(jìn)行論述，結(jié)合實(shí)例推演數(shù)據(jù)關(guān)聯(lián)規(guī)則的產(chǎn)生及Apriori算法的具體應(yīng)用過程。

當(dāng)今社會已進(jìn)入大數(shù)據(jù)時(shí)代，數(shù)據(jù)滲透在生活的每一個(gè)角落，數(shù)據(jù)之間存在有趣的關(guān)聯(lián)。業(yè)界人士對數(shù)據(jù)挖掘的關(guān)注度大幅度上升，數(shù)據(jù)挖掘使業(yè)務(wù)更加智能，使信息更加可靠，種種現(xiàn)象表明數(shù)據(jù)也是生產(chǎn)力。清楚數(shù)據(jù)挖掘的基本概念是關(guān)聯(lián)規(guī)則的首要任務(wù)，Apriori算法是尋找數(shù)據(jù)中頻繁項(xiàng)集的有力武器，落實(shí)Apriori算法是對數(shù)據(jù)挖掘的應(yīng)用夯實(shí)。由此，本文對數(shù)據(jù)關(guān)聯(lián)規(guī)則作出了詳細(xì)的介紹，給出了關(guān)于Apriori算法的應(yīng)用實(shí)例。

1.數(shù)據(jù)挖掘的基本概念

通過大量數(shù)據(jù)的收集和存儲，運(yùn)用關(guān)聯(lián)規(guī)則挖掘出數(shù)據(jù)各項(xiàng)之間的聯(lián)系或關(guān)聯(lián)，得到相關(guān)信息，從而得出數(shù)據(jù)也是生產(chǎn)力。因此，我們需要了解關(guān)于數(shù)據(jù)挖掘的幾個(gè)基本概念。

（1）項(xiàng)、項(xiàng)集與事務(wù)

項(xiàng)（Item）是數(shù)據(jù)中的最小單位；某幾個(gè)項(xiàng)的集合稱為事務(wù)（T），每個(gè)事務(wù)有一個(gè)關(guān)鍵字屬性，稱為事務(wù)號（或交易號），由此區(qū)分?jǐn)?shù)據(jù)庫中的各個(gè)事務(wù)；所有項(xiàng)的集合為P，T為P的子集；事務(wù)的集合為事務(wù)集（D）。將這些基本概念如圖所示：

圖1 項(xiàng)、項(xiàng)集與事物關(guān)系圖

（2）關(guān)聯(lián)規(guī)則

用Venn圖表示，如下：

圖2 Venn圖

（3）支持度（s）與置信度（c）

支持度s表示A與B的總和（A∪B）占D的百分比，即概率P（A∪B），表達(dá)式如下：

支持度定義的分子（事務(wù)數(shù)（））稱為支持度計(jì)數(shù)。由于支持度更容易由分子導(dǎo)出，一般情況下，顯示支持度計(jì)數(shù)而不是支持度。支持度反映的是實(shí)用性。

置信度c表示A與B的總和（A∪B）占包含A的事務(wù)的百分比，即條件概率P（A|B），表達(dá)式如下：

置信度反映的是有效性，確定性。當(dāng)置信度為100%時(shí)，意味著規(guī)則完全有效確定，值得信賴。

當(dāng)同時(shí)滿足最小支持度閾值min_s和最小置信度閾值min_c時(shí)，就可以挖掘出強(qiáng)關(guān)聯(lián)。支持度與置信度用百分比表示，區(qū)域范圍在0%至100%之間。

（4）k-項(xiàng)集與k-頻繁項(xiàng)集

包含k個(gè)項(xiàng)的項(xiàng)集稱為k-項(xiàng)集。例如：集合{牛奶，蛋糕}是2-項(xiàng)集；集合{牛奶，蛋糕，布丁}是3-項(xiàng)集。包含項(xiàng)集的事務(wù)數(shù)是項(xiàng)集的出現(xiàn)頻率，又稱項(xiàng)集支持計(jì)數(shù)或計(jì)數(shù)。如果：項(xiàng)集的出現(xiàn)頻率大于或者等于min_s乘以D中事物總數(shù)，則：項(xiàng)集滿足最小支持度min_s。此時(shí)，項(xiàng)集稱為頻繁項(xiàng)集。頻繁k-項(xiàng)集的集合記作：Lk。頻繁項(xiàng)集的非空子集也必須是頻繁的。

關(guān)聯(lián)規(guī)則的挖掘涉及尋找頻繁項(xiàng)集。

2.Apriori算法

關(guān)聯(lián)規(guī)則的挖掘涉及尋找頻繁項(xiàng)集。Apriori算法用于尋找頻繁項(xiàng)集。

（1）Apriori算法簡介

Apriori算法指的是一種逐層搜索的迭代方法。顧名思義，Apriori算法使用前一項(xiàng)集探索后一項(xiàng)集的方法。如：找出頻繁1-項(xiàng)集（L1），用L1找出頻繁2-項(xiàng)集L2，再用L2找出L3……Lk找出Lk+1，依次類推，直到不能找出頻繁k-項(xiàng)集。每找一個(gè)Lk需要掃描一次數(shù)據(jù)庫。

（2）Apriori性質(zhì)

為提高逐層搜索頻繁項(xiàng)集的效率，由此產(chǎn)生用于壓縮搜索空間的重要性質(zhì)。

根據(jù)定義，現(xiàn)定義一個(gè)項(xiàng)集I，如果I不滿足最小支持度s，即P(I)＜s，顯然，I不是頻繁項(xiàng)集。將項(xiàng)A添加到I，根據(jù)支持度公式推導(dǎo)，A∪I不可能比I更頻繁出現(xiàn)。即P（I∪A）＜P(I)＜s。此為反單調(diào)，即當(dāng)一個(gè)集合不能通過測試，則包含此集合的任何集合都無法通過同一測試。

由此得出：任何非頻繁的（k-1）項(xiàng)集都不可能是頻繁k-項(xiàng)集的子集。用此性質(zhì)壓縮搜索空間，可以大大提高搜索頻繁項(xiàng)集的效率。

（3）Apriori性質(zhì)應(yīng)用簡介

運(yùn)用此性質(zhì)，用Lk尋找Lk+1：

1）尋找連接集

通過Lk與其自身做連接操作產(chǎn)生候選k-項(xiàng)集，記作Ck+1。li[j]表示li的第j項(xiàng)，例如l1[3]表示l1的第3項(xiàng)。執(zhí)行連接Lk（JOIN）Lk。如果（l1[1]=l2[1]）∧（l1[2]=l2[2]）∧……∧（l1[k-1]=l2[k-1]）∧（l1[k]＜l2[k]）。其中l(wèi)1[k]＜l2[k]是為了保證不產(chǎn)生重復(fù)。所以連接項(xiàng)集是{l1[1]，l1[2]，……，l1[k]，l2[k]}。

2）刪除

Ck是Lk的超集（包含它的任何集合），Lk的成員可以是，也可以不是頻繁的，但所有的頻繁k-項(xiàng)集都包含在Ck中，確定Ck中每個(gè)候選的計(jì)數(shù)，從而確定Lk。為壓縮Ck，提高搜索效率，使用Apriori性質(zhì)：任何非頻繁的（k-1）項(xiàng)集都不可能是頻繁k-項(xiàng)集的子集。如果候選項(xiàng)集k-項(xiàng)集的子集不在Lk-1中，則候選項(xiàng)集不可能頻繁，可以從Ck中刪除。

重復(fù)尋找連接集與刪除步驟操作，直到產(chǎn)生最后的頻繁項(xiàng)集。不妨設(shè)最后產(chǎn)生的頻繁項(xiàng)集為頻繁k-項(xiàng)集。將頻繁項(xiàng)集中的k拆分為A，B兩個(gè)項(xiàng)集，計(jì)算其支持度與置信度，挖掘出其規(guī)則。

3.算法在數(shù)據(jù)挖掘中的應(yīng)用

Apriori算法指的是一種逐層搜索的迭代方法。本實(shí)例采取“超市數(shù)據(jù)庫”中的各項(xiàng)數(shù)據(jù)，具體展示介紹算法在數(shù)據(jù)挖掘?qū)嵗?dāng)中的應(yīng)用。

（1）算法迭代應(yīng)用

我們以P1，P2，P3……形式代表不同的商品，以T表示每個(gè)記錄。現(xiàn)有如下商品購買數(shù)據(jù)庫D：

表1 商品購買數(shù)據(jù)庫

從本數(shù)據(jù)庫D中可以看出共有20筆交易，即20個(gè)事務(wù)（T）；共8件商品，即8個(gè)項(xiàng)。記P={P1，P2，P3，P4，P5，P6，P7，P8}。

1）第一輪算法迭代

使候選1-項(xiàng)集C1=P，則P中每一個(gè)成員（即P1，P2，P3，P4，P5，P6，P7，P8）成為C1的成員。計(jì)數(shù)每一項(xiàng)在數(shù)據(jù)庫D中出現(xiàn)的次數(shù)，得到支持度計(jì)數(shù)。結(jié)果如下表：

表2 候選1-項(xiàng)集C1支持度計(jì)數(shù)

完成第一次與自身連接操作并得出支持度計(jì)數(shù)后進(jìn)行查找刪除。不妨設(shè)最小支持度計(jì)數(shù)為5（即最小支持度min_s=5/20=25%），從C1中查找并刪除小于最小支持度計(jì)數(shù)的項(xiàng)集，得到頻繁1-項(xiàng)集L1。結(jié)果如下表：

表3 頻繁1-項(xiàng)集L1支持度計(jì)數(shù)

2）第二輪算法迭代

產(chǎn)生候選2-項(xiàng)集C2。使L1（JOIN）L1，將L1中的每個(gè)項(xiàng)進(jìn)行組合，形成候選2-項(xiàng)集C2。計(jì)數(shù)二項(xiàng)集在數(shù)據(jù)庫D中出現(xiàn)的次數(shù)，得到支持度計(jì)數(shù)。結(jié)果如下表：

表4 候選2-項(xiàng)集C2支持度計(jì)數(shù)

完成第二次連接操作并得出支持度計(jì)數(shù)后進(jìn)行查找刪除。不妨繼續(xù)設(shè)最小支持度計(jì)數(shù)為5，從C2中查找并刪除小于最小支持度計(jì)數(shù)的項(xiàng)集，得到頻繁2-項(xiàng)集L2。結(jié)果如下表：

表5 頻繁2-項(xiàng)集L2支持度計(jì)數(shù)

3）第三輪算法迭代

產(chǎn)生候選3-項(xiàng)集C3。使L2（JOIN）L2，將L2中的每個(gè)項(xiàng)進(jìn)行組合，形成候選3-項(xiàng)集C3。根據(jù)Apriori性質(zhì)：任何非頻繁的（k-1）項(xiàng)集都不可能是頻繁k-項(xiàng)集的子集。可直接刪除某幾個(gè)項(xiàng)集。如下表：

表6 候選3-項(xiàng)集C3刪除操作表

計(jì)數(shù)三項(xiàng)集在數(shù)據(jù)庫D中出現(xiàn)的次數(shù)，得到支持度計(jì)數(shù)。結(jié)果如下表：

表7 候選3-項(xiàng)集C3支持度計(jì)數(shù)

完成第三次連接操作并得出支持度計(jì)數(shù)后進(jìn)行查找刪除。不妨繼續(xù)設(shè)最小支持度計(jì)數(shù)為5，從C3中查找并刪除小于最小支持度計(jì)數(shù)的項(xiàng)集，得到頻繁3-項(xiàng)集L3。結(jié)果如下表：

表8 頻繁3-項(xiàng)集L3支持度計(jì)數(shù)

4）第四輪算法迭代

產(chǎn)生候選4-項(xiàng)集C4。使L3（JOIN）L3，將L3中的每個(gè)項(xiàng)進(jìn)行組合，形成候選4-項(xiàng)集C4。計(jì)數(shù)四項(xiàng)集在數(shù)據(jù)庫D中出現(xiàn)的次數(shù)，得到支持度計(jì)數(shù)。最終沒有被刪除的候選4-項(xiàng)集C4只有一個(gè)。如表9所示：

表9 頻繁3-項(xiàng)集L3支持度計(jì)數(shù)

完成第四次連接操作并得出支持度計(jì)數(shù)后進(jìn)行查找刪除。繼續(xù)設(shè)最小支持度計(jì)數(shù)為5，這一項(xiàng)仍被保留。

由算法得出的最后輸出結(jié)果，頻繁項(xiàng)集全集如表10所示：

表10 頻繁項(xiàng)集全集

（2）形成關(guān)聯(lián)規(guī)則

將頻繁項(xiàng)集中的k拆分為A，B兩個(gè)項(xiàng)集，滿足條件：A∪B=k，排列出所有A，B，得出潛在規(guī)則，計(jì)算其置信度。以頻繁項(xiàng)集頻繁4-項(xiàng)集為例展示關(guān)聯(lián)規(guī)則的產(chǎn)生，，其中A∪B={P1，P2，P5，P6}，A∩B=。表11所示為潛在規(guī)則表：

表11 潛在規(guī)則表

表12 規(guī)則表

由此規(guī)則表得到：“項(xiàng)集A的購買”推出“項(xiàng)集B的購買”。所有的頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則后，可以得出一些規(guī)則，如：

本研究為關(guān)聯(lián)規(guī)則提供了強(qiáng)有效的算法，為數(shù)據(jù)挖掘提供了明確方式，也為今后對數(shù)據(jù)挖掘的研究提供了理論參考依據(jù)。

引文

①大數(shù)據(jù).http://en.wikipedia.org/wiki/Big_data.

②Viktor Mayer-Sch.nberger,Kenneth Cukier.大數(shù)據(jù)時(shí)代:生活、工作與思維的大變革[M].杭州:浙江人民出版社,2013.

③Silberschatz.A..數(shù)據(jù)庫系統(tǒng)概念(原書第6版)[M].北京:機(jī)械工業(yè)出版社,2012.

④韓嘉煒.Micheline Kamber.數(shù)據(jù)挖掘:概念與技術(shù)(原書第3版)[M].北京:機(jī)械工業(yè)出版社,2012.

⑤http://en.wikipedia.org/wiki/Meta-Object_Facility.