《數(shù)據(jù)倉庫與數(shù)據(jù)挖掘》課程論文

題目： 關(guān)聯(lián)分析Apriori算法的研究和案例實現(xiàn)

專業(yè)： 計算機科學(xué)與技術(shù)
學(xué)號： XXXXXXXXX
姓名： XXX

2018-2019學(xué)年第二學(xué)期
目錄

研究現(xiàn)狀 1
1.1 算法簡介 1
1.2 研究現(xiàn)狀 1

算法思想 2
2.1 相關(guān)概念 2
2.2 基本思想 3

算法步驟 4

算法應(yīng)用 6
4.1 所應(yīng)用的數(shù)據(jù)集介紹 6
4.2 核心代碼 7
4.3 實現(xiàn)頁面截圖 10
5.總結(jié) 12

1.研究現(xiàn)狀
1.1算法簡介
Apriori算法是經(jīng)典的挖掘頻繁項集和關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法。A priori在拉丁語中指"來自以前"。當(dāng)定義問題時，通常會使用先驗知識或者假設(shè)，這被稱作"一個先驗"（a priori）。Apriori算法的名字正是基于這樣的事實：算法使用頻繁項集性質(zhì)的先驗性質(zhì)，即頻繁項集的所有非空子集也一定是頻繁的。Apriori算法使用一種稱為逐層搜索的迭代方法，其中k項集用于探索(k+1)項集。首先，通過掃描數(shù)據(jù)庫，累計每個項的計數(shù)，并收集滿足最小支持度的項，找出頻繁1項集的集合。該集合記為L1。然后，使用L1找出頻繁2項集的集合L2，使用L2找出L3，如此下去，直到不能再找到頻繁k項集。每找出一個Lk需要一次數(shù)據(jù)庫的完整掃描。Apriori算法使用頻繁項集的先驗性質(zhì)來壓縮搜索空間。
1.2研究現(xiàn)狀
Apriori是Agrawal等于1993年設(shè)計的一個基本算法，首先提出了挖掘顧客交易數(shù)據(jù)庫中項集間的關(guān)聯(lián)規(guī)則問題，其核心方法是基于頻繁項集理論的遞推方法。算法提出后以后，很多研究人員對關(guān)聯(lián)規(guī)則挖掘算法進(jìn)行了大量研究，特別是對關(guān)聯(lián)規(guī)則挖掘算法進(jìn)行了大量的研究和優(yōu)化。如Savasere等人設(shè)計了一個基于劃分的算法，Mannila提出的基于采樣的方法等。
近幾年，隨著研究者對于關(guān)聯(lián)規(guī)則挖掘的深入研究，關(guān)聯(lián)規(guī)則挖掘研究有了許多擴展，包括：事務(wù)間關(guān)聯(lián)規(guī)則挖掘、空間關(guān)聯(lián)規(guī)則挖掘、負(fù)關(guān)聯(lián)規(guī)則挖掘、序列模式挖掘及正關(guān)聯(lián)規(guī)則挖掘；另外，對度量的研究也有所突破。自從Chen，Hart，Brin和Motwani等人提出了強關(guān)聯(lián)規(guī)則的興趣度問題以后，強關(guān)聯(lián)規(guī)則興趣度問題的研究得到了很高的重視。后來評估關(guān)聯(lián)規(guī)則興趣度相應(yīng)的一些優(yōu)化方法的出現(xiàn)，促進(jìn)了目前度量方法的進(jìn)一步改進(jìn)和完善。同時，Motwani和Silverstein把這方面的研究和討論推廣到相關(guān)的算法中。除這個方面外，其他方面的研究也得到了發(fā)展，如多層關(guān)聯(lián)規(guī)則挖掘、區(qū)間數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘、刪除冗余規(guī)則、度量的改進(jìn)研究、關(guān)聯(lián)規(guī)則的有效增量更新和并行分布規(guī)則挖掘等等，這些關(guān)聯(lián)規(guī)則挖掘算法在實際數(shù)據(jù)挖掘系統(tǒng)中的到了很好的應(yīng)用。
2.算法思想
2.1相關(guān)概念
（1）項(item): 項指的是具體的一件東西，比如在購物籃的例子中，你的購物籃里面的大米，被子，紅酒等等商品都是項；
（2）項集(itemset): 顧名思義，項的集合，由一個或多個項組成的一個整體，我們把由kk個項組成的項集叫kk項集；
（3）事務(wù)(transaction)：一個事務(wù)，可以看做是發(fā)生的一次事件，比如一個人一次的購物清單，用符號TT表示，一般來說，TT包含一個它本身的身份——TIDTID以及事務(wù)中的一個項集。當(dāng)然，如果我們收集很多這樣的清單，構(gòu)成一個數(shù)據(jù)庫，這個數(shù)據(jù)庫就能作為我們挖掘計算的依據(jù)了。這個庫，用符號DD表示。
（4）關(guān)聯(lián)規(guī)則：表示實體之間相關(guān)關(guān)系，用蘊含式A?BA?B表示A和B之間相關(guān)關(guān)系（A和B可以是兩個項，也可以是兩個項集），關(guān)聯(lián)規(guī)則包含支持度(support)和置信度(confidence)兩個層面指標(biāo)；
（5）支持度(support)：說的是所有事務(wù)中，A和B同時出現(xiàn)的次數(shù)與總的事務(wù)數(shù)的比例。換個說法，現(xiàn)實數(shù)據(jù)中，支持A和B這種關(guān)聯(lián)的比例。用以下公式計算：
support(A?B)=P(A∪B)
其中，P(A∪B)的意思是事務(wù)中同時包含A和B的比例；
（6）置信度(confidence)：A?BA?B的置信度說的是包含A的事務(wù)中，同時也包含B的事務(wù)所占的比例。用以下公式計算：
confidence(A?B)=P(B|A)
比如說，總共100個事務(wù)，有50個包含A，而這50個事務(wù)當(dāng)中，又有20個同時也包含B，那么，confidence(A?B)=40%
了解了支持度(support)和置信度(confidence)兩個概念，那么不妨可以再深入一步，拓展一個概念：絕對支持度；
支持度計數(shù)（絕對支持度）：絕對支持度又叫支持度計數(shù)，頻度或計數(shù)。上面我們定義的支持度其實也可以叫“相對支持度”，而絕對支持度則說的是一個實體出現(xiàn)的次數(shù)，比如：support(A) = A在全體事務(wù)數(shù)據(jù)庫DD中出現(xiàn)的次數(shù)。這個概念很重要，因為依靠支持度計數(shù)我們就能通過support(A)support(A)和support(A∪B)support(A∪B)來計算置信度：
confidence(A?B)=P(B|A)=support(A∪B)support(A)
（7）強規(guī)則：我們將實體之間的關(guān)聯(lián)規(guī)則定義為強規(guī)則，如果實體之間的相對支持度(support)和置信度(confidence)滿足我們預(yù)定義的最小支持度閾值(min_sup)和最小置信度閾值(min_conf)。換句話說，只要我們在上面的概念5中定義的兩個指標(biāo)都滿足，那么，實體之間就是極有強（關(guān)聯(lián)）規(guī)則的；
（8）頻繁項集：指的是頻繁在事務(wù)中出現(xiàn)的項集，所謂“頻繁”的標(biāo)準(zhǔn)就是這個項集出現(xiàn)的次數(shù)滿足最小支持度計數(shù)（閾值）。
2.2 基本思想
該算法的基本思想是：首先找出所有的頻集，這些項集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度一樣。然后由頻集產(chǎn)生強關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿足最小支持度和最小可信度。然后使用第1步找到的頻集產(chǎn)生期望的規(guī)則，產(chǎn)生只包含集合的項的所有規(guī)則，其中每一條規(guī)則的右部只有一項，這里采用的是中規(guī)則的定義。一旦這些規(guī)則被生成，那么只有那些大于用戶給定的最小可信度的規(guī)則才被留下來。為了生成所有頻集，使用了遞歸的方法。
（1） L1 = find_frequent_1-itemsets(D);
（2） for (k=2;Lk-1 ≠Φ ;k++) {
（3） Ck = apriori_gen(Lk-1 ,min_sup);
（4） for each transaction t ∈ D {//scan D for counts
（5） Ct = subset(Ck,t);//get the subsets of t that are candidates
（6） for each candidate c ∈ Ct
（7） c.count++;
（8） }
（9） Lk ={c ∈ Ck|c.count≥min_sup}
（10） }
（11） return L= ∪ k Lk;
可能產(chǎn)生大量的候選集,以及可能需要重復(fù)掃描數(shù)據(jù)庫，是Apriori算法的兩大缺點。　　　　
3.算法步驟
下面我們對Aprior算法流程做一個總結(jié)。
　　輸入：數(shù)據(jù)集合D，支持度閾值α
　　輸出：最大的頻繁k項集
　 （1）掃描整個數(shù)據(jù)集，得到所有出現(xiàn)過的數(shù)據(jù)，作為候選頻繁1項集。k=1，頻繁0項集為空集。
　　（2）挖掘頻繁k項集
　　　　(a) 掃描數(shù)據(jù)計算候選頻繁k項集的支持度
　　　　(b) 去除候選頻繁k項集中支持度低于閾值的數(shù)據(jù)集,得到頻繁k項集。如果得到的頻繁k項集為空，則直接返回頻繁k-1項集的集合作為算法結(jié)果，算法結(jié)束。如果得到的頻繁k項集只有一項，則直接返回頻繁k項集的集合作為算法結(jié)果，算法結(jié)束。
　　　　? 基于頻繁k項集，連接生成候選頻繁k+1項集。
　　（3） 令k=k+1，轉(zhuǎn)入步驟2。
從算法的步驟可以看出，Aprior算法每輪迭代都要掃描數(shù)據(jù)集，因此在數(shù)據(jù)集很大，數(shù)據(jù)種類很多的時候，算法效率很低。
我們下面這個簡單的例子看看：

圖3.1.1
　　我們的數(shù)據(jù)集D有4條記錄，分別是134,235,1235和25。現(xiàn)在我們用Apriori算法來尋找頻繁k項集，最小支持度設(shè)置為50%。首先我們生成候選頻繁1項集，包括我們所有的5個數(shù)據(jù)并計算5個數(shù)據(jù)的支持度，計算完畢后我們進(jìn)行剪枝，數(shù)據(jù)4由于支持度只有25%被剪掉。我們最終的頻繁1項集為1235，現(xiàn)在我們鏈接生成候選頻繁2項集，包括12,13,15,23,25,35共6組。此時我們的第一輪迭代結(jié)束。
　　進(jìn)入第二輪迭代，我們掃描數(shù)據(jù)集計算候選頻繁2項集的支持度，接著進(jìn)行剪枝，由于12和15的支持度只有25%而被篩除，得到真正的頻繁2項集，包括13,23,25,35。現(xiàn)在我們鏈接生成候選頻繁3項集,123, 125，135和235共4組，這部分圖中沒有畫出。通過計算候選頻繁3項集的支持度，我們發(fā)現(xiàn)123,125和135的支持度均為25%，因此接著被剪枝，最終得到的真正頻繁3項集為235一組。由于此時我們無法再進(jìn)行數(shù)據(jù)連接，進(jìn)而得到候選頻繁4項集，最終的結(jié)果即為頻繁3三項集235。

4.算法應(yīng)用
4.1所應(yīng)用的數(shù)據(jù)集介紹
以超市交易為數(shù)據(jù)集，所有商品的項集為I = {bread, beer, cake, cream, milk, tea}
某條交易如Ti = {bread, beer, milk}，可以簡化為Ti = {a, b, d}
data.txt數(shù)據(jù)集樣本如下
a, d, e,f
a, d, e
c, e
e, f
…
數(shù)據(jù)集位于本地的D:\data目錄下，數(shù)據(jù)集一共有270行，前24行的數(shù)據(jù)內(nèi)容如圖4.1所示

圖4.1.1

4.2核心代碼

# -*- coding: utf-8 -*- """ Created on Tue Jun 25 21:39:58 2019@author: lyz """def load_data_set():data_set = []fd = open("d:\data\data.txt", "r")for line in fd.readlines():line = line.strip('\n')data_set.append(line)return data_set''' 直接從數(shù)據(jù)集構(gòu)造1-候選集 ''' def create_C1(data_set):C1 = set()for t in data_set:for item in t:item_set = frozenset([item])C1.add(item_set)return C1''' 判斷是否滿足 ''' def is_apriori(Ck_item, Lksub1):for item in Ck_item:sub_Ck = Ck_item - frozenset([item])if sub_Ck not in Lksub1:return Falsereturn True''' 生成各個候選集Ck ''' def create_Ck(Lksub1, k):Ck = set()len_Lksub1 = len(Lksub1)list_Lksub1 = list(Lksub1)for i in range(len_Lksub1):for j in range(1, len_Lksub1):l1 = list(list_Lksub1[i])l2 = list(list_Lksub1[j])l1.sort()l2.sort()if l1[0:k-2] == l2[0:k-2]:Ck_item = list_Lksub1[i] | list_Lksub1[j]if is_apriori(Ck_item, Lksub1):Ck.add(Ck_item)return Ck''' 通過候選集Ck生成頻繁集Lk ''' def generate_Lk_by_Ck(data_set, Ck, min_support, support_data):Lk = set()item_count = {}for t in data_set:for item in Ck:if item.issubset(t):if item not in item_count:item_count[item] = 1else:item_count[item] += 1t_num = float(len(data_set))for item in item_count:if (item_count[item] / t_num) >= min_support:Lk.add(item)support_data[item] = item_count[item] / t_numreturn Lk''' 生成各階頻繁集，最小支持度為0.2 ''' def generate_L(data_set, k, min_support):support_data = {}C1 = create_C1(data_set)L1 = generate_Lk_by_Ck(data_set, C1, min_support, support_data)Lksub1 = L1.copy()L = []L.append(Lksub1)for i in range(2, k+1):Ci = create_Ck(Lksub1, i)Li = generate_Lk_by_Ck(data_set, Ci, min_support, support_data)Lksub1 = Li.copy()L.append(Lksub1)return L, support_data''' 生成從頻繁集關(guān)聯(lián)規(guī)則分析 ''' def generate_big_rules(L, support_data, min_conf):big_rule_list = []sub_set_list = []for i in range(0, len(L)):for freq_set in L[i]:for sub_set in sub_set_list:if sub_set.issubset(freq_set):conf = support_data[freq_set] / support_data[freq_set - sub_set]big_rule = (freq_set - sub_set, sub_set, conf)if conf >= min_conf and big_rule not in big_rule_list:big_rule_list.append(big_rule)sub_set_list.append(freq_set)return big_rule_listif __name__ == "__main__":data_set = load_data_set()L, support_data = generate_L(data_set, k=3, min_support=0.2)big_rules_list = generate_big_rules(L, support_data, min_conf=0.7)for Lk in L:print ("=" * 50)print ("frequent " + str(len(list(Lk)[0])) + "-itemsets\t\tsupport")print ("=" * 50)for freq_set in Lk:print (freq_set, support_data[freq_set])print()print ("Big Rules")for item in big_rules_list:print (item[0], "=>", item[1], "conf: ", item[2])

4.3實現(xiàn)頁面截圖

圖 4.3.1

圖4.3.2

圖4.3.3

圖4.3.4
5.總結(jié)
Aprior算法是一個非常經(jīng)典的頻繁項集的挖掘算法，很多算法都是基于Aprior算法而產(chǎn)生的，包括FP-Tree,GSP, CBA等。這些算法利用了Aprior算法的思想，但是對算法做了改進(jìn)，數(shù)據(jù)挖掘效率更好一些，因此現(xiàn)在一般很少直接用Aprior算法來挖掘數(shù)據(jù)了，但是理解Aprior算法是理解其它Aprior類算法的前提，同時算法本身也不復(fù)雜，因此值得好好研究一番。
這次的收獲主要有以下幾點：同一行數(shù)據(jù)，最小支持度越小，那么產(chǎn)生的頻繁項集維數(shù)越高，程序運行的時間越長；頻繁項集的子集一定是頻繁的，子集頻繁父親一定頻繁；Apriori也存在缺點：第一，在每一步產(chǎn)生候選項目集時循環(huán)產(chǎn)生的組合過多，沒有排除不應(yīng)該參與組合的元素；第二，每次計算項集的支持度時，開銷會隨著數(shù)據(jù)的增多而成幾何級增長。

總結(jié)

以上是生活随笔為你收集整理的数据仓库与数据挖掘论文的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。