一種基于頻率的多最小支持度挖掘算法

古良云 樂紅兵

（江南大學 無錫 214122）

1 引言

數據挖掘又稱知識發(fā)現(xiàn)，它的目的是為了從龐大的數據中發(fā)現(xiàn)有意義的隱藏的知識［1］，關聯(lián)規(guī)則［2］是由R.Agrawal等于1993年提出的，在數據挖掘領域它是一個重要且熱門的研究課題。關聯(lián)規(guī)則，顧名思義它的目的是為了挖掘兩個及以上項目之間隱藏的聯(lián)系。關聯(lián)規(guī)則的示例如下：

床單→枕套［sup=40%，conf=90%］

這條規(guī)則表示40%的顧客會同時購買床單和枕套，而購買床單的人中有90%購買了枕套。

關聯(lián)規(guī)則有關定義為I={i1，i2，…，i m}D={T1，T2，…，T n}是m個不同項目的集合，那么任意一個項目i k則被稱為一個項目。T是I的子集{t1，t2，…，t n}，稱為事務，每一個事務有一個唯一標識號，記作TID。事務全體構成了事務數據庫D，|D|表示D中事務的個數。關聯(lián)規(guī)則是形如X?Y的蘊含式，其中X?I，Y?I，同時集合X和Y也為不相交的兩個集合，即X∩Y=φ。關于關聯(lián)規(guī)則的蘊含式可解釋為項目集合X出現(xiàn)在某一個事務數據中，則可能導致項目集合Y也會以某一個概率存在于相同的事務數據中。在研究領域，通常使用兩個指標來度量項目集合之間關聯(lián)規(guī)則的緊密程度，即支持度和置信度。其中支持度可解釋為事務數據庫中即包含集合X又包含集合Y的事務數量與|D|之間的比值。即：

支持度反映了X、Y同時出現(xiàn)的概率。定義置信度為包含X和Y的事務數與包含X的事務數之比。即：

置信度反映了如果事務中包含X，則事務中包含Y的概率。

在關聯(lián)規(guī)則挖掘領域，若某一個集合在事務數據庫中出現(xiàn)的頻率大于一個用戶設定的值，則將這個集合稱為頻繁項集［3］，假設這個集合中有k個元素則稱這個集合為k-頻繁項集即L k，同時這個用戶設定的值被稱為最小支持度即min sup。

在關聯(lián)規(guī)則的學習中，評價項集的一個重要指標即為支持度，支持度的大小代表項集在數據庫中的普遍性，這個項集出現(xiàn)的越普遍則說明這個項集越重要［4］。置信度用來衡量關聯(lián)規(guī)則的準確性。綜上所述，在發(fā)現(xiàn)關聯(lián)規(guī)則的過程中有兩個不可或缺的評價標準，這兩個標準能夠衡量規(guī)則的好壞，即支持度和置信度［5］。針對關聯(lián)規(guī)則的Apriori算法的局限性，人們提出了一些改進的算法。如基于交集的InterApriori算法［6］，基于壓縮矩陣的Apriori算法［7］等。文獻［8］為了突破Apriori算法的瓶頸，利用矩陣有效地處理數據庫中的事務，使用“與”運算以達到最大的計算效率，并且不需要頻繁地掃描數據庫來查找事務。文獻［9］掃描數據庫后對事務進行二進制編碼，并根據事務出現(xiàn)的實際頻率進行排序，以此來對候選項集進行剪枝，文獻［10］提出了一種不產生候選項集的算法FP-growth，該算法采用遞歸策略并且掃描兩次原始數據集即可。這些改進的Apriori算法使用的最小支持度均是用戶指定的唯一的值，這就默認數據中的所有項均有相同的頻率［11］，但在現(xiàn)實生活中情況往往更加復雜，比如實際收集的數據具有多樣性，有些項目出現(xiàn)的極其頻繁，而有些項目則很少出現(xiàn)。如果項目的頻率變化很大，將會出現(xiàn)兩個問題：1）如果最小支持度設置的很高，則不能發(fā)現(xiàn)出現(xiàn)頻率較低的項目；2）如果最小支持度太低，則會出現(xiàn)規(guī)則爆炸的現(xiàn)象，這樣的挖掘結果是沒有意義的［12］。

以購買商品為例，人們經常購買酸奶，但購買酸奶機的頻率卻很低，假設酸奶和酸奶機采用相同的支持度，如果支持度設置過高，在最后生成的關聯(lián)規(guī)則中將很難得到有關酸奶機的規(guī)則。而在實際生活中，酸奶機的利潤比酸奶要高許多，且在人們購買酸奶機時還會購買自制酸奶的其它材料，因此一般情況下用戶會認為由酸奶機產生的關聯(lián)規(guī)則是比較重要的，但是相同的支持度會導致在項目集中由于酸奶機的支持計數較低，包含酸奶機的頻繁項集被丟棄，有關酸奶機的規(guī)則被遺漏。如果支持度設置過低，又會出現(xiàn)大量無意義的規(guī)則。

解決這一問題的方法是可以讓用戶指定多個最小支持度，比如可以為數據集的每個項目都指定一個最小項目支持度［13］，這樣可以反映出不同項目具有不同頻率的特性。文獻［14］提出了使用相關項目集中各項目最小支持度中的最大值來實現(xiàn)剪枝，避免產生過多無意義的規(guī)則。文獻［15］提出了一個基于多最小支持度的加權關聯(lián)規(guī)則算法，允許用戶為每個數據項設置不同的權重和最小支持度，但仍然存在著產生大量候選項集，充分掃描事務數據庫I/O開銷很大等不足。

利用多最小支持度模型，本文提出了一種基于頻率的多最小支持度算法，將事務數據庫中項目的實際出現(xiàn)頻率作為其最小項目支持度，并通過設置項目頻率最小閾值避免產生過多無意義的關聯(lián)規(guī)則。這對增強關聯(lián)規(guī)則挖掘的實用性，提高生成關聯(lián)規(guī)則的準確率具有積極意義［16］。

2 相關工作

本文描述的改進算法是一種根據事務數據庫中各事務本身的出現(xiàn)頻率再單獨設定其最小支持度的算法，此改進算法仍使用之前的支持度定義。

在該挖掘策略中，一條規(guī)則的最小支持度［17］采用在規(guī)則中出現(xiàn)的所有項目的最小項目支持度。也就是說，在數據集中，每個項目都擁有一個用戶指定的最小項目支持度，通過對不同的項目指定不同的最小項目支持度，用戶就可以方便地對不同規(guī)則設置不同的支持度要求。

定義1：最小項目支持度

對于項目集I={i1，i2，…，i m}，其中任一項目皆設置了其最小支持度，即是最小項目支持度，寫作MIS（i）。

其中count（i）是項目i在數據集中出現(xiàn)的次數，|D|是事務集的大小。

定義2：項目頻率最小閾值

對于項目集I={i1，i2，…，i m}，用戶設置項目出現(xiàn)的最小頻率值，稱之為項目頻率最小閾值，記作MF，其中M F≥0。

在大型數據集中，將項目出現(xiàn)頻率作為最小項目支持度，考慮到現(xiàn)實情況中事務記錄表會出現(xiàn)大量頻率極低的項目，生成大量1-頻繁項集，提高算法的運行時間開銷。因此，用戶可設置項目出現(xiàn)頻率最小閾值MF，減少1-頻繁項集的數量。在生成1-頻繁項集過程中，?i∈I，若count(i)

定義3：

假設有R:i1，i2，…，i k?i k+1，…，i r，其中i r∈I，在這個規(guī)則中最小項目支持度的最小值min（MIS（i1），MIS（i2），…，MIS（ik），MIS（ik+1），…，MIS（ir））則為規(guī)則R所需要滿足的最小支持度。

由以上定義可知，采用最小項目支持度可以對不同的規(guī)則進行不同的最小支持度限制。對于包含出現(xiàn)頻率較高的項目的規(guī)則，其最小支持度可以很大，而對于出現(xiàn)頻率低的項目的規(guī)則，其最小支持度可以很小。

例1：項目集I=｛A，B，C｝，各項目最小項目支持度分別為MIS（A）=20%，MIS（B）=1%，MIS（C）=2%

1）規(guī)則C?A［sup=1.5%，conf=70%］不滿足其最小支持度。

因為min（MIS（A），MIS（C））=2%>1.5%

2）規(guī)則C?B［sup=1.5%，conf=70%］滿足其最小支持度。

因為min（MIS（B），MIS（C））=1%<1.5%

3 基于頻率的多最小支持度算法描述

3.1 基于頻率的多最小支持度算法中的剪枝策略

Apriori算法挖掘關聯(lián)規(guī)則通常需要兩個環(huán)節(jié)［18］：

1）以迭代的方式發(fā)現(xiàn)原始數據集中全部的頻繁項集；

2）根據設定的最小置信度，在頻繁項集中挖掘關聯(lián)規(guī)則。

Apriori算法的性質為［19］假設一個項集為頻繁項集，則它的所有子集除非空子集外都是頻繁項集。

但是，如果我們使用本文的改進算法來生成頻繁項集，這一性質已經不再滿足了。

例2：項目集I=｛A，B，C，D｝，各項目最小項目支持度分別為MIS（A）=12%，MIS（B）=18%，MIS（C）=3%，MIS（D）=5%

假設使用改進算法在第2輪搜索時得到2-項集｛A，B｝，它的實際支持度為10%，由于實際支持度小于MIS（A），也小于MIS（B），所以，根據改進算法策略，項集｛A，B｝被丟棄。由于｛A，B｝被丟棄，將導致在第3輪搜索中不會產生3-項集｛A，B，C｝和｛A，B，D｝。但是經過分析，項目C和D的最小支持度很低，那么3-項集｛A，B，C｝和｛A，B，D｝就極有可能是頻繁項集，所以丟棄項目集｛A，B｝就可能是錯誤的。因此，采用改進算法時，Apriori算法的性質將不再滿足。

候選項集的大小直接影響算法的挖掘效率，因此可通過修剪候選項集來提高算法的挖掘效率。為了解決這一問題，本算法采用了將候選項集按照項目屬性的最小項目支持度排序的方法，盡可能多地完成剪枝，減少算法運行的開銷。

具體描述：在多最小支持度的情況下，對每個數據集所包含的項按照各自的最小項目支持度進行升序排列，經過排序后，整個數據集的最小支持度就由其首項的最小項目支持度確定，所以，當其（k-1）-子集包含首項或者（k-1）-子集的最小項支持度等于最小支持度時，就可以根據子集是否在（k-1）-頻繁項集中來判斷是否將其剪枝。

例3：假設有3項頻繁集：L3=｛<1，2，3>，<1，2，4>，<1，3，4>，<1，3，5>，<1，4，5>，<1，4，6>，<2，3，4>｝，對各項目按照其最小項目支持度進行排序，結果為｛1，2，3，4，5，6｝，由L3得到候選項集C4=｛<1，2，3，4>，<1，3，4，5>，<1，4，5，6>｝，對候選集進行剪枝時，由于<1，5，6>?L3，由此可知，sup（<1，4，5，6>））），故候選項<1，4，5，6>不是頻繁項集，被剪枝。對于候選項<1，3，4，5>，其一個子集<3，4，5>?L3，所以sup（<3，4，5>））可能大于或者等于MIS（1），因此無法判斷候選項<1，3，4，5>的最小項支持度與MIS（1）的關系，故將候選項<1，3，4，5>加入頻繁項集，若MIS（1）=MIS（3），則可確定sup（<3，4，5>）

3.2 基于頻率的多最小支持度算法描述

按照上文的算法思想，得到基于頻率的多最小支持度算法如下：

輸入：挖掘數據庫DB，項目頻率最小閾值MF

輸出：頻繁數據集L

算法步驟：

1）對數據庫DB進行初次掃描，得到候選項集C1。

2）計算各項目的實際出現(xiàn)頻率count(i)

3）if count（i）>MF

4）insertiintoL1

5）else

6）deleteifromC1

7）得到頻繁項集L1，根據定義1中的公式（3）得到最小項目支持度

8）根據最小項目支持度對頻繁項集L1中的各項目按照升序排序

9）for(k=2;Lk-1≠?;k++)

10）Ifk=2

11） then C2=level2-candidate-gen（L1）

12）else

13） Ck=candidate-gen（Lk-1）

14）end

15）掃描數據庫，計算每個候選項集中的數據集的支持度

16）若該候選項集的支持度大于或等于最小項支持度，則為頻繁項集

17）合并各長度的頻繁項集，得到所有的頻繁項集

長度為2的候選項集C2的產生過程：

level2-candidate-gen（L1）

1）for each item c inL1

2）if count（c）/|DB|≥MIS（c）then

3） for each item h inL1that is after c do

4） if count（h）/|DB|≥MIS（c）then

5） insertintoC2

在剪枝過程中添加了限制條件，具體描述如下：

Candidate-gen-prune（Ck）

1）for each itemcinCk

2）for each（k-1）-subset s of c do

3） if s中包含首項c［1］ands?Lk-1

then delete c fromCk

4） if s中不包含首項c［1］and（s中包含某項c［n］and MIS（c［n］）=MIS（c［1］））ands?Lk-1then delete c fromCk

上述算法與Apriori算法的剪枝過程相比，添加了步驟4）的限制條件。具體示例見例3。

4 實驗分析

4.1 實驗一

4.1.1 實驗平臺與實驗數據

為了驗證算法的有效性，采用三個實驗與基于頻率的多最小支持度挖掘算法進行對比。實驗環(huán)境為1.70GHz AMD A6 CPU，6G內存和Windows 7操作系統(tǒng)，算法在MyEclipse平臺上采用Java語言編程實現(xiàn)。在Java中隨機函數random（）產生的數據上進行了測試，其好處是可以靈活產生所需數據，且無需進行預處理。隨機函數生成的數據如表1所示，共8條事務記錄，6個項目。

表1 隨機數據

4.1.2 實驗結果與分析

將該數據分別應用Apriori算法與基于頻率的多最小支持度挖掘算法進行關聯(lián)挖掘。生成的頻繁項集如表2所示，兩種算法的挖掘結果如表3所示，其中項目覆蓋率指算法挖掘高、低頻率項目的能力，覆蓋率越高，說明算法挖掘的頻繁項集中涉及的項目越全面。

表2 Apriori算法與多最小支持度算法生成的頻繁項集

表3 兩種算法挖掘結果對比

通過表2、表3的實驗結果可以看出：

1）使用較小支持度的Apriori算法得到了大量的頻繁項集，使用較大支持度的Apriori算法則遺漏了小概率頻繁項集，而基于頻率的多最小支持度挖掘算法生成的頻繁項集數目則介于這兩種支持度的Apriori算法之間。

2）使用基于頻率的多最小支持度挖掘算法運行時間介于兩種支持度的Apriori算法之間，但是在項目覆蓋率方面，基于頻率的多最小支持度挖掘算法明顯高于其它兩種Apriori算法。

4.2 實驗二

選取標準UCI數據集中的Zoo數據集，將該數據集應用于本文提出的基于頻率的多最小支持度挖掘算法和文獻［17］提出的算法，并對實驗結果進行比較。實驗結果如表4所示。

表4 Zoo數據集挖掘結果對比

由表4可知，與文獻［17］提出的算法對比，使用基于頻率的多最小支持度挖掘算法具有較高的項目覆蓋率，且運行時間短。因此，本文算法在效率提升方面的效果也是顯著的。

4.3 實驗三

將本文提出的基于頻率的多最小支持度挖掘算法、文獻［17］提出的算法與Apriori算法應用于真實數據［20］，對實驗結果進行對比。實驗數據來源：https：//www.kaggle.com。該數據庫存儲超市中顧客的線上交易記錄，在該數據庫中，User_Product表中共有12430條記錄，記錄中包括用戶ID，用戶名，用戶購買的商品ID，商品名稱，購買時間，商品類別，商品擺放位置等15個屬性。對該表中的數據進行預處理，其中保留用戶ID及商品ID屬性值，處理后的數據形式如表1所示。挖掘后的規(guī)則中，可根據數據庫中的Product表查詢出對應的商品名稱。實驗結果如表5所示。

表5 交易數據庫挖掘結果對比

由表5可知，使用基于頻率的多最小支持度挖掘算法具有較高的項目覆蓋率，且綜合挖掘的頻繁項集數和運行時間，基于頻率的多最小支持度挖掘算法都具有較理想的挖掘效果。

5 結語

本文主要討論了在關聯(lián)規(guī)則挖掘中，針對Apriori算法中的始終保持單一的最小支持度的不足，提出并實現(xiàn)了一種基于頻率的多最小支持度挖掘算法。該算法針對每個項目設定了最小項目支持度，彌補了Apriori算法中的不足，并通過設置項目頻率最小閾值避免產生過多無意義的關聯(lián)規(guī)則，新算法能有效地挖掘出出現(xiàn)頻率較低的項目的關聯(lián)規(guī)則。通過在合成數據與實際應用中驗證了新算法的有效性。