前言

關(guān)聯(lián)規(guī)則挖掘發(fā)現(xiàn)大量數(shù)據(jù)中項(xiàng)集之間有趣的關(guān)聯(lián)或者相互聯(lián)系。關(guān)聯(lián)規(guī)則挖掘的一個(gè)典型例子就是購物籃分析，該過程通過發(fā)現(xiàn)顧客放入其購物籃中不同商品之間的聯(lián)系，分析出顧客的購買習(xí)慣，通過了解哪些商品頻繁地被顧客同時(shí)買入，能夠幫助零售商制定合理的營銷策略。購物籃事務(wù)的例子如下圖所示：??

?

例如：在同一次去超級市場時(shí)，如果顧客購買牛奶，同時(shí)他也購買面包的可能性有多大？

通過幫助零售商有選擇地經(jīng)銷和安排貨架，這種信息會(huì)引導(dǎo)銷售。零售商有兩種方法可以進(jìn)行安排貨架，第一種方法是將牛奶和面包盡可能的放的近一些，方便顧客自取，第二種方法是將牛奶和面包放的遠(yuǎn)一些，顧客在購買這兩件物品的時(shí)候，這中間貨架上的物品也會(huì)被顧客選擇購買。這兩種方法都可以進(jìn)一步刺激消費(fèi)。但是，如何發(fā)現(xiàn)牛奶和面包之間的關(guān)聯(lián)關(guān)系呢？Apriori算法可以進(jìn)行關(guān)聯(lián)規(guī)則挖掘。

算法中的基本概念

1、項(xiàng)集和K-項(xiàng)集

令I(lǐng)={i1，i2，i3……id}是購物籃數(shù)據(jù)中所有項(xiàng)的集合，而T={t1，t2，t3….tN}是所有事務(wù)的集合，每個(gè)事務(wù)ti包含的項(xiàng)集都是I的子集。在關(guān)聯(lián)分析中，包含0個(gè)或多個(gè)項(xiàng)的集合稱為項(xiàng)集。如果一個(gè)項(xiàng)集包含K個(gè)項(xiàng)，則稱它為K-項(xiàng)集?？占侵覆话魏雾?xiàng)的項(xiàng)集。例如，在購物籃事務(wù)的例子中，｛啤酒，尿布，牛奶｝是一個(gè)3-項(xiàng)集。

2、支持度計(jì)數(shù)

項(xiàng)集的一個(gè)重要性質(zhì)是它的支持度計(jì)數(shù)，即包含特定項(xiàng)集的事務(wù)個(gè)數(shù)，數(shù)學(xué)上，項(xiàng)集X的支持度計(jì)數(shù)σ（X）可以表示為

σ（X）=|{ti|X?ti，ti∈T}|

其中，符號|*|表示集合中元素的個(gè)數(shù)。

在購物籃事務(wù)的例子中，項(xiàng)集｛啤酒，尿布，牛奶｝的支持度計(jì)數(shù)為2，因?yàn)橹挥?和4兩個(gè)事務(wù)中同時(shí)包含這3個(gè)項(xiàng)。

3、關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則是形如X→Y的蘊(yùn)含表達(dá)式，其中X和Y是不相交的項(xiàng)集，即X∩Y=?。

關(guān)聯(lián)規(guī)則的強(qiáng)度可以用它的支持度（support）和置信度（confidence）來度量。支持度確定規(guī)則可以用于給定數(shù)據(jù)集的頻繁程度，而置信度確定Y在包含X的事務(wù)中出現(xiàn)的頻繁程度。

支持度（s）和置信度（c）這兩種度量的形式定義如下：

s（X→Y）=σ（X∪Y）/N

c（X→Y）=σ（X∪Y）/σ（X）

其中， σ（X∪Y）是（X∪Y）的支持度計(jì)數(shù)，N為事務(wù)總數(shù)，σ（X）是X的支持度計(jì)數(shù)。

Example

在購物籃事務(wù)的例子中，考慮規(guī)則{牛奶，尿布}→{啤酒}。由于項(xiàng)集{牛奶，尿布，啤酒}的支持度計(jì)數(shù)為2，而事務(wù)的總數(shù)為5，所以規(guī)則的支持度為2/5=0.4。

規(guī)則的置信度是項(xiàng)集{牛奶，尿布，啤酒}的支持度計(jì)數(shù)與項(xiàng)集{牛奶，尿布}支持度技術(shù)的商，由于存在3個(gè)事務(wù)同時(shí)包含牛奶和尿布，所以規(guī)則的置信度為2/3=0.67。

關(guān)聯(lián)規(guī)則發(fā)現(xiàn)

給定事務(wù)的集合T，關(guān)聯(lián)規(guī)則發(fā)現(xiàn)是指找出支持度大于等于minsup （最小支持度）并且置信度大于等于minconf（最小置信度）的所有規(guī)則，minsup和minconf是對應(yīng)的支持度和置信度閾值。

關(guān)聯(lián)規(guī)則的挖掘是一個(gè)兩步的過程：

（1）頻繁項(xiàng)集產(chǎn)生：其目標(biāo)是發(fā)現(xiàn)滿足最小支持度閾值的所有項(xiàng)集（至少和預(yù)定義的最小支持計(jì)數(shù)一樣），這些項(xiàng)集稱作頻繁項(xiàng)集。

（2）規(guī)則的產(chǎn)生：其目標(biāo)是從上一步發(fā)現(xiàn)的頻繁項(xiàng)集中提取所有高置信度的規(guī)則，這些規(guī)則稱作強(qiáng)規(guī)則。（必須滿足最小支持度和最小置信度）

Apriori算法介紹

Apriori算法的實(shí)質(zhì)使用候選項(xiàng)集找頻繁項(xiàng)集。

Apriori 算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。算法的名字基于這樣的事實(shí)：算法使用頻繁項(xiàng)集性質(zhì)的先驗(yàn)知識， 正如我們將看到的。Apriori 使用一種稱作逐層搜索的迭代方法，k-項(xiàng)集用于探索（k+1）-項(xiàng)集。首先，找出頻繁1-項(xiàng)集的集合。該集合記作L1。L1 用于找頻繁2-項(xiàng)集的集合L2，而L2 用于找L3，如此下去，直到不能找到頻繁k-項(xiàng)集。找每個(gè)Lk 需要一次數(shù)據(jù)庫掃描。

Apriori性質(zhì)

Apriori性質(zhì)：頻繁項(xiàng)集的所有非空子集都必須也是頻繁的。 Apriori 性質(zhì)基于如下觀察：根據(jù)定義，如果項(xiàng)集I不滿足最小支持度閾值s，則I不是頻繁的，即P（I）《 s。如果項(xiàng)A添加到I，則結(jié)果項(xiàng)集（即I∪A）不可能比I更頻繁出現(xiàn)。因此， I∪A也不是頻繁的，即 P（I∪A）《 s 。

該性質(zhì)屬于一種特殊的分類，稱作反單調(diào)，意指如果一個(gè)集合不能通過測試，則它的所有超集也都不能通過相同的測試。稱它為反單調(diào)的，因?yàn)樵谕ú贿^測試的意義下，該性質(zhì)是單調(diào)的。

先驗(yàn)定理

先驗(yàn)定理：如果一個(gè)項(xiàng)集是頻繁的，則它的所有子集一定也是頻繁的。

（關(guān)于先驗(yàn)定理、單調(diào)與反單調(diào)可以參考下面的例子理解）

?

如圖所示，假定｛c，d，e｝是頻繁項(xiàng)集。顯而易見，任何包含項(xiàng)集{c，d，e}的事務(wù)一定包含它的子集{c，d}，{c，e}，{d，e}，{c}，tbdfd7ljx和{e}。這樣，如果{c，d，e}是頻繁的，則它的所有子集一定也是頻繁的。

?

如果項(xiàng)集{a，b}是非頻繁的，則它的所有超集也一定是非頻繁的。即一旦發(fā)現(xiàn){a，b}是非頻繁的，則整個(gè)包含{a，b}超集的子圖可以被立即剪枝。這種基于支持度度量修剪指數(shù)搜索空間的策略稱為基于支持度的剪枝。

這種剪枝策略依賴于支持度度量的一個(gè)關(guān)鍵性質(zhì)，即一個(gè)項(xiàng)集的支持度絕不會(huì)超過它的子集的支持度。這個(gè)性質(zhì)也稱支持度度量的反單調(diào)性。

挖掘頻繁項(xiàng)集

Apriori算法的關(guān)鍵是如何用Lk-1找Lk？由下面的兩步過程連接和剪枝組成。

連接步：為找Lk，通過Lk-1與自己連接產(chǎn)生候選k-項(xiàng)集的集合。該候選項(xiàng)集的集合記作Ck。設(shè)l1和l2是Lk-1中的項(xiàng)集。記號li［j］表示li的第j項(xiàng)（例如，l1［k-2］表示l1的倒數(shù)第3項(xiàng)）。為方便計(jì)，假定事務(wù)或項(xiàng)集中的項(xiàng)按字典次序排序。執(zhí)行連接Lk-1　Lk-1；其中，Lk-1的元素是可連接的，如果它們前（k-2）個(gè)項(xiàng)相同；即，Lk-1的元素l1和l2是可連接的，如果（l1［1］=l2［1］）∧（l1［2］=l2［2］）∧…∧（l1［k-2］=l2［k-2］）∧（l1［k-1］《 l2［k-1］）。條件（l1［k-1］《 l2［k-1］）是簡單地保證不產(chǎn)生重復(fù)。連接l1和l2產(chǎn)生的結(jié)果項(xiàng)集是l1［1］l1［2］…l1［k-1］l2［k-1］。

剪枝步：Ck是Lk的超集；即，它的成員可以是頻繁的，也可以不是頻繁的，但所有的頻繁k-項(xiàng)集都包含在Ck中。掃描數(shù)據(jù)庫，確定Ck中每個(gè)候選的計(jì)數(shù)，從而確定Lk（即，根據(jù)定義，計(jì)數(shù)值不小于最小支持度計(jì)數(shù)的所有候選是頻繁的，從而屬于Lk）。然而，Ck可能很大，這樣所涉及的計(jì)算量就很大。為壓縮Ck，可以用以下辦法使用Apriori性質(zhì)：任何非頻繁的（k-1）-項(xiàng)集都不是可能是頻繁k-項(xiàng)集的子集。因此，如果一個(gè)候選k-項(xiàng)集的（k-1）-子集不在Lk-1中，則該候選也不可能是頻繁的，從而可以由Ck中刪除。這種子集測試可以使用所有頻繁項(xiàng)集的散列樹快速完成。

Apriori算法

算法6.2.1（Apriori） 使用逐層迭代找出頻繁項(xiàng)集

輸入：事務(wù)數(shù)據(jù)庫D；12345678910111213141516最小支持度閾值。

輸出：D中的頻繁項(xiàng)集L。

方法：

1） L1 = find_frequent_1_itemsets（D）; //找出頻繁1-項(xiàng)集的集合L1

2） for（k = 2; Lk-1 ≠ ?; k++） { //產(chǎn)生候選，并剪枝

3） Ck = aproiri_gen（Lk-1，min_sup）;

4） for each transaction t∈D{ //掃描D進(jìn)行候選計(jì)數(shù)

5） Ct = subset（Ck，t）; //得到t的子集

6） for each candidate c∈Ct

7） c.count++; //支持度計(jì)數(shù)

8） }

9） Lk={c∈Ck| c.count ≥min_sup} //返回候選項(xiàng)集中不小于最小支持度的項(xiàng)集

10） }

11） return L = ∪kLk；//所有的頻繁集

第一步（連接 join）

Procedure apriori_gen（Lk-1： frequent （k-1）-itemset; min_sup： support）

1） for each itemset l1∈Lk-1

2） for each itemset l2∈Lk-1

3） if（l1［1］=l2［1］）∧。..∧（l1［k-2］=l2［k-2］）∧（l1［k-1］《l2［k-1］） then{

4） c = l1　l2; //連接步：l1連接l2

//連接步產(chǎn)生候選，若K-1項(xiàng)集中已經(jīng)存在子集c，則進(jìn)行剪枝

5） if has_infrequent_subset（c，Lk-1） then

6） delete c; //剪枝步：刪除非頻繁候選

7） else add c to Ck;

8） }

9） return Ck;

12345678910111213

第二步：剪枝（prune）

Procedure has_infrequent_subset（c:candidate k-itemset; Lk-1:frequent （k-1）-itemset） //使用先驗(yàn)定理

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

2） if c?Lk-1 then

3） return TRUE;

4） return FALSE;

1234567

由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則

一旦由數(shù)據(jù)庫D中的事務(wù)找出頻繁項(xiàng)集，由它們產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則是直接了當(dāng)?shù)模◤?qiáng)關(guān)聯(lián)規(guī)則滿足最小支持度和最小置信度）。對于置信度，可以用下式，其中條件概率用項(xiàng)集支持度計(jì)數(shù)表示。

confidence（A→B）=P（A│B）=support（A∪B）/support（A）

其中，support（A∪B）是（A∪B）的支持度計(jì)數(shù)，support（A）是A的支持度計(jì)數(shù)。

根據(jù)該式，關(guān)聯(lián)規(guī)則可以產(chǎn)生如下：

? 1、對于每個(gè)頻繁項(xiàng)集l，產(chǎn)生l的所有非空子集。

? 2、對于l的每個(gè)非空子集s，如果support（l）/support（s） ≥min_conf，則輸出規(guī)則“s?（l-s）”。其中，min_conf是最小置信度閾值。

由于規(guī)則由頻繁項(xiàng)集產(chǎn)生，每個(gè)規(guī)則都自動(dòng)滿足最小支持度。頻繁項(xiàng)集連同它們的支持度預(yù)先存放在hash表中，使得它們可以快速被訪問。

Apriori算法的實(shí)例

問題：數(shù)據(jù)庫中有9個(gè)事務(wù)，即|D| = 9。Apriori假定事務(wù)中的項(xiàng)按字典次序存放。我們使用下圖解釋Apriori算法發(fā)現(xiàn)D中的頻繁項(xiàng)集。 圖四

分析與解：

（一）、挖掘頻繁項(xiàng)集

1、在算法的第一次迭代，每個(gè)項(xiàng)都是候選1-項(xiàng)集的集合C1的成員，算法簡單地掃描所有的事務(wù)，對每個(gè)項(xiàng)的出現(xiàn)次數(shù)計(jì)數(shù)。

2、假定最小事務(wù)支持計(jì)數(shù)為2（即，minsup=2/9=22%）。可以確定頻繁1-項(xiàng)集的集合L1。它由具有最小支持度的候選1-項(xiàng)集組成。

?

3、為發(fā)現(xiàn)頻繁2-項(xiàng)集的集合L2，算法使用L1　L1產(chǎn)生候選2-項(xiàng)集的集合C2。

4、下一步，掃描D中事務(wù)，計(jì)算C2中每個(gè)候選項(xiàng)集的支持計(jì)數(shù)。

5、確定頻繁2-項(xiàng)集的集合L2，它由具有最小支持度的C2中的候選2-項(xiàng)集組成。

【注】 L1　L1等價(jià)于L1×L1，因?yàn)長k　Lk的定義要求兩個(gè)連接的項(xiàng)集共享k-1個(gè)項(xiàng)。

?

6、候選3-項(xiàng)集的集合C3的產(chǎn)生詳細(xì)地列在圖中。首先，令C3 = L2　L2 = {{I1，I2，I3}， {I1，I2，I5}， {I1，I3，I5}， {I2，I3，I4}， {I2，I3，I5}， {I2，I4，I5}}。根據(jù)Apriori性質(zhì)，頻繁項(xiàng)集的所有子集必須是頻繁的，我們可以確定后4個(gè)候選不可能是頻繁的。因此，我們把它們由C3刪除，這樣，在此后掃描D確定L3時(shí)就不必再求它們的計(jì)數(shù)值。注意，Apriori算法使用逐層搜索技術(shù)，給定k-項(xiàng)集，我們只需要檢查它們的（k-1）-子集是否頻繁。

【L2 L2連接生成C3的過程】

1．連接：C3= L2 L2={{I1，I2}，{I1，I3}，{I1，I5}，{I2，I3}，{I2，I4}，{I2，I5}} 　{{I1，I2}，{I1，I3}，{I1，I5}，{I2，I3}，{I2，I4}，{I2，I5}} = {{I1，I2，I3}，{I1，I2，I5}，{I1，I3，I5}，{I2，I3，I4}，{I2，I3，I5}，{I2，I4，I5}}

2．使用Apriori性質(zhì)剪枝：頻繁項(xiàng)集的所有子集必須是頻繁的。存在候選項(xiàng)集，其子集不是頻繁的嗎？

?{I1，I2，I3}的2-項(xiàng)子集是{I1，I2}，{I1，I3}和{I2，I3}。{I1，I2，I3}的所有2-項(xiàng)子集都是L2的元素。因此，保留{I1，I2，I3}在C3中。

?{I1，I2，I5}的2-項(xiàng)子集是{I1，I2}，{I1，I5}和{I2，I5}。{I1，I2，I5}的所有2-項(xiàng)子集都是L2的元素。因此，保留{I1，I2，I5}在C3中。

?{I1，I3，I5}的2-項(xiàng)子集是{I1，I3}，{I1，I5}和{I3，I5}。{I3，I5}不是L2的元素，因而不是頻繁的。這樣，由C3中刪除{I1，I3，I5}。

?{I2，I3，I4}的2-項(xiàng)子集是{I2，I3}，{I2，I4}和{I3，I4}。{I3，I4}不是L2的元素，因而不是頻繁的。這樣，由C3中刪除{I2，I3，I4}。

?{I2，I3，I5}的2-項(xiàng)子集是{I2，I3}，{I2，I5}和{I3，I5}。{I3，I5}不是L2的元素，因而不是頻繁的。這樣，由C3中刪除{I2，I3，I5}。

?{I2，I4，I5}的2-項(xiàng)子集是{I2，I4}，{I2，I5}和{I4，I5}。{I4，I5}不是L2的元素，因而不是頻繁的。這樣，由C3中刪除{I2，I3，I5}。

3．這樣，剪枝后C3 = {{I1，I2，I3}，{I1，I2，I5}}

7、掃描D中事務(wù)，以確定L3，它由具有最小支持度的C3中的候選3-項(xiàng)集組成。

?

8、算法使用L3　L3產(chǎn)生候選4-項(xiàng)集的集合C4。盡管連接產(chǎn)生結(jié)果{{I1，I2，I3，I5}}，這個(gè)項(xiàng)集被剪去，因?yàn)樗淖蛹瘂I1，I3，I5}不是頻繁的。這樣，C4=?，因此算法終止，找出了所有的頻繁項(xiàng)集。

（二）、由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則

假定數(shù)據(jù)包含頻繁項(xiàng)集l={I1，I2，I5}，可以由l產(chǎn)生哪些關(guān)聯(lián)規(guī)則？l的非空子集有{I1，I2}，{I1，I5}，{I2，I5}，{I1}，{I2}和{I5}。結(jié)果關(guān)聯(lián)規(guī)則如下，每個(gè)都列出置信度。

I1∩I2→I5， confidence=2/4=0.5=50%

I1∩I5→I2， confidence=2/2=1=100%

I2∩I5→I1， confidence=2/2=1=100%

I1→I2∩I5， confidence=2/6=0.33=33%

I2→I1∩I5， confidence=2/7=0.29=29%

I5→I1∩I2， confidence=2/2=1=100%

如果最小置信度閾值為70%，則只有2、3和最后一個(gè)規(guī)則可以輸出，因?yàn)橹挥羞@些才是強(qiáng)規(guī)則。

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)

使用先驗(yàn)性質(zhì)，大大提高了頻繁項(xiàng)集逐層產(chǎn)生的效率；簡單易理解；數(shù)據(jù)集要求低。

缺點(diǎn)

1、候選頻繁K項(xiàng)集數(shù)量巨大。

2、在驗(yàn)證候選頻繁K項(xiàng)集的時(shí)候，需要對整個(gè)數(shù)據(jù)庫進(jìn)行掃描，非常耗時(shí)。

改進(jìn)算法

算法思想：

上面的原始算法中由Ck（Lk-1直接生成的）到Lk經(jīng)過了兩步處理，第一步根據(jù)Lk-1進(jìn)行裁剪，第二步根據(jù)minsupport裁剪。上面提到的兩個(gè)提高效率的方法都是基于第一步的。當(dāng)經(jīng)過聯(lián)接生成K維數(shù)據(jù)項(xiàng)集時(shí)，判斷它的K-1維子集是否存在于Lk-1中，如果不在直接刪除。這樣每生成一個(gè)K維數(shù)據(jù)項(xiàng)集時(shí)，就要搜索一遍Lk-1。改進(jìn)算法的思想就是只需要搜索一遍Lk-1就可以了。當(dāng)所有聯(lián)接完成的時(shí)候，掃描一遍Lk-1，對于Lk-1任意元素A，判斷A是否為Ck中元素 c的子集，如果是，對子集c進(jìn)行計(jì)數(shù)。也就是統(tǒng)計(jì)Lk-1中包含Ck中任意元素c的K-1維子集的個(gè)數(shù)。最后根據(jù)c進(jìn)行裁剪。c的計(jì)數(shù)，即 Lk-1中包含的c的子集的個(gè)數(shù)，小于K，則刪除。

改進(jìn)算法偽代碼

算法的主體不變，aprriori_gen函數(shù)改變?nèi)缦拢瘮?shù) has_infrequent_subset不再需要。

procedure apriori_gen（Lk-1:frequent（k-1）-itemsets;minsupport:minimum support threshold）

（1）for each itemset l1 ∈ Lk-1

（2）for each itemset l2∈ L k-1

（3）if（l1［1］=l2［1］）∧（l1［2］=l2［2］）∧…∧（l1［k-2］=l2［k-2］）∧（l1［k-1］=l2［k-1］） then

（4）c=l1∪ l2;

（5）for each itemset l1∈ L k-1 //掃描Lk-1中的元素

（6）for each candidate c∈ Ck //掃描 Ck中的元素

（7）if l1 is the subset of Ck then //判斷前者是不是后者的子集，如果是計(jì)數(shù)加1

（8）c.number++;

（9）C‘k={ c∈Ck |c.number=k};

（10）return C’k;

12345678910111213

例子對比：

問題：假設(shè)Lk-1={{1，2，3}，{1，2，4}，{2，3，4}，{2，3，5}，{1，3，4}}，求Lk。

由Lk-1得到Ck={{1，2，3，4}，{2，3，4，5}，{1，2，3，5}}。

原算法：首先得到{1，2，3，4}的子集{1，2，3}，{1，2，4}，{2，3，4}，{1，3，4}。然后判斷這些子集是不是 Lk-1的元素。如果都是則保留，否則刪除。這里保留，{2，3，4，5}和{1，2，3，5}則應(yīng)該刪除。得到C’k={{1，2，3，4}}。

改進(jìn)算法：首先從Lk-1中取元素{1，2，3}，掃描Ck中的元素，看{1，2，3}是不是Ck元中元素的子集，{1，2，3}是{1，2，3，4}的子集，{1，2，3，4}的計(jì)數(shù)加1，{1，2，3}不是{2，3，4，5}的子集，計(jì)數(shù)不變，是{1，2，3，5}的子集，計(jì)數(shù)加1，經(jīng)過對{1，2，3}處理后得到計(jì)數(shù){1，0，1}；然后看{1，2，4}，{1，2，4}是{1，2，3，4}的子集，而不是 {2，3，4，5}的子集，也不是{1，2，3，5}的子集，計(jì)數(shù)不變，計(jì)數(shù)變?yōu)閧2，0，1}；考察{2，3，4}，{2，3，4}是{1，2，3，4}的子集，也是{2，3，4，5}的子集，不是｛1，2，3，5｝的子集，計(jì)數(shù)變?yōu)閧3，1，1}；{2，3，5}不是{1，2，3，4}的子集，是{2，3，4，5}的子集，也是{1，2，3，5}的子集，計(jì)數(shù)變?yōu)閧3，2，2}；{1，3，4}是{1，2，3，4}的子集，不是{2，3，4，5}的子集，也不是{1，2，3，5}的子集，計(jì)數(shù)變?yōu)閧4，2，2}。對數(shù)據(jù)掃描完畢。此時(shí)K=4，只有第一個(gè)元素的計(jì)數(shù)為4，為高頻數(shù)據(jù)項(xiàng)集。得到C’k={{1，2，3，4}}。

復(fù)雜度對比

下面對原算法和改進(jìn)算法的性能進(jìn)行比較。Lk-1中的數(shù)據(jù)項(xiàng)集的個(gè)數(shù)記為|Lk-1|，Ck中的數(shù)據(jù)項(xiàng)集的個(gè)數(shù)記為|Ck|，Ck中元素的子集個(gè)數(shù)設(shè)為ni，其中i=1～|Ck| 。這里只分析從Ck～C’k的處理。原 算法從 AprioriCk中取元素，然后求該元素的子集，判斷該子集是否在 |Ck|中。需要進(jìn)行的計(jì)算為? 次， 1<=|L’k-1|<=|L’k-1|，1<= n’i <=n i。而改進(jìn)算法是從Lk-1中選取元素，看是不是Ck中元素的子集，對 Ck中數(shù)據(jù)項(xiàng)集的子集個(gè)數(shù)進(jìn)行統(tǒng)計(jì)。需要進(jìn)行的計(jì)算是（|Lk-1|+1）*|Ck| 次。如果 n’i =1，就是每次只取Ck中數(shù)據(jù)項(xiàng)集的一個(gè)子集就可以判斷該數(shù)據(jù)項(xiàng)集，則兩個(gè)算法的效率基本相同，但是這種情況很少出現(xiàn)，從而大部分情況下，改進(jìn)算法的效率要高于原算法。