一派敷、問(wèn)題描述
頻繁模式挖掘搜索給定數(shù)據(jù)集中反復(fù)出現(xiàn)的聯(lián)系调限，使用Apriori算法挖掘1M電影數(shù)據(jù)集中用戶喜愛的電影之間的關(guān)聯(lián)凿宾，分析用戶的觀影喜好麻捻，幫助推薦電影纲仍，例如：如果一位用戶觀看并喜愛了電影《你的名字》呀袱，他有多大可能也會(huì)觀看《秒速5厘米》。
二郑叠、主要設(shè)備（軟件）
Ubuntu,python2.7
三夜赵、Apriori算法
算法使用的是逐層搜索的迭代方法，使用K頻繁項(xiàng)集生成k+1頻繁項(xiàng)集锻拘，掃描數(shù)據(jù)庫(kù)油吭，累計(jì)每個(gè)項(xiàng)的計(jì)數(shù)，收集滿足最小支持度的項(xiàng)生成頻繁1項(xiàng)集用它找出頻繁2項(xiàng)集署拟，每次都使用前一個(gè)找出后一個(gè)頻繁項(xiàng)集婉宰，每個(gè)Lk都需要一次數(shù)據(jù)的完整掃描。
在從Lk-1找Lk時(shí)為了提高效率推穷，壓縮搜索空間心包，使用連接步和剪枝步。連接步：通過(guò)將Lk-1于自身連接產(chǎn)生候選集k項(xiàng)集的集合馒铃。剪枝規(guī)則：將不可能的解提前過(guò)濾蟹腾，如果有一個(gè)項(xiàng)集不是頻繁項(xiàng)集，那么它的超集也一定不頻繁区宇，不作為候選集娃殖，不做最小支持度測(cè)試即任何非頻繁的（k-1)項(xiàng)集都不是頻繁k項(xiàng)集的子集。
四议谷、實(shí)驗(yàn)過(guò)程
收集數(shù)據(jù)
? 使用了MovieLens數(shù)據(jù)集ml-1m炉爆，數(shù)據(jù)大小為24.6MB的ratings.dat，數(shù)據(jù)按列依次為'user_id', 'name_id', 'rating_id', 'timestaps'卧晓。
輸入數(shù)據(jù)
使用了pandas芬首，基于numpy的工具，解決數(shù)據(jù)分析任務(wù)逼裆。
數(shù)據(jù)結(jié)構(gòu)：
Series:序列郁稍，類似一維數(shù)組
DataFrame:表格型數(shù)據(jù)結(jié)構(gòu)，二維數(shù)組
導(dǎo)入數(shù)據(jù)集：pd.read_table() 讀取表格的通用函數(shù)胜宇，使用時(shí)要指定文件中的內(nèi)容分隔符耀怜。
定義與變量說(shuō)明：
load_data_set()
加載數(shù)據(jù)集函數(shù)
rating_names
評(píng)價(jià)表的列名
rating_list
評(píng)價(jià)列表
ratings
訓(xùn)練集
D_set
name_id按user_id分組存放入子列表
pre_C1(D_set)
創(chuàng)建頻繁1項(xiàng)集的候選集函數(shù)
C1
頻繁1項(xiàng)集的候選集
pre_dict
頻繁1項(xiàng)集項(xiàng)和個(gè)數(shù)的字典
cut(Ck, Lk_1)
剪枝函數(shù)
sub_Ck
k-1項(xiàng)候選子集的集合
createCk(Lk_1, k):
list_Lk_1
連接步：生成頻繁k項(xiàng)集的候選集集合
K-1項(xiàng)頻繁項(xiàng)集集合的列表形式
l1,l2
Lk-1的項(xiàng)集
createLk(CK, D_set, min_sup)
根據(jù)候選集選出頻繁項(xiàng)集集合的函數(shù)篩去不是D_set子集的和非頻繁項(xiàng)集
Lk
K頻繁項(xiàng)集的集合
LkDict
存放k頻繁項(xiàng)集和支持度的字典
Support =[]
存放所有k頻繁項(xiàng)集集合的列表
Lk_1
k-1頻繁項(xiàng)集集合
L
總頻繁項(xiàng)集集合的列表
t_num
整個(gè)數(shù)據(jù)集的事務(wù)個(gè)數(shù)
訓(xùn)練算法
# -*- coding:utf-8 -*-
import pandas as pd
#使用pandas讀取文件并選取前200個(gè)用戶喜歡的電影，分割為訓(xùn)練集桐愉，標(biāo)準(zhǔn)：評(píng)分大于3視為該用戶喜歡此電影
def load_data_set():
? ? rating_names = ['user_id', 'name_id', 'rating_id', 'timestaps']
? ? rating_list = pd.read_table('/home/wangyuhang/python_learn/ml-1m/ratings.dat', sep='::', header=None,engine="python",names=rating_names)
? ? rating_list["like"] = rating_list["rating_id"] > 3
? ? # print rating_list.head(5)
? ? ratings = rating_list[rating_list['user_id'].isin(range(200))]
? ? like_ratings = ratings[ratings['like']]
? ? rating_data = like_ratings.groupby('user_id')
? ? data = dict((k, v.values) for k, v in like_ratings.groupby("user_id")["name_id"])
? ? D_set = []
? ? for a in data.keys():
? ? ? ? D_set.append(data[a])
? ? return D_set
# 創(chuàng)建頻繁1項(xiàng)集的候選集的集合
def pre_C1(D_set):
? ? # global L
? ? # global Support
? ? C1 = set()
? ? pre_dict = dict()
? ? for row in D_set:
? ? ? ? for item in row:
? ? ? ? ? ? item_set = frozenset([item])? # 通過(guò)循環(huán)對(duì)data_set中的每個(gè)子列表內(nèi)部的每個(gè)元素產(chǎn)生不可變集合
? ? ? ? ? ? if item_set not in C1:
? ? ? ? ? ? ? ? C1.add(item_set)
? ? ? ? ? ? ? ? pre_dict[item_set] = 1
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? pre_dict[item_set] = pre_dict[item_set] + 1
? ? return pre_dict
# 剪枝步：任何非頻繁的（k-1)項(xiàng)集都不是頻繁k項(xiàng)集的子集
def cut(Ck, Lk_1):
? ? for item in Ck:? # 候選k項(xiàng)集的集合
? ? ? ? sub_Ck = Ck - frozenset([item])? # k-1項(xiàng)子集的集合
? ? ? ? if sub_Ck not in Lk_1:? # 如果一個(gè)候選的k項(xiàng)集的(k-1)項(xiàng)子集不在頻繁項(xiàng)集L(K-1)中則該候選也不可能是頻繁的
? ? ? ? ? ? return False? # 返回false該候選集不頻繁封寞。
? ? ? ? else:
? ? ? ? ? ? return True
# 連接步：生成頻繁k項(xiàng)集的候選集的集合，為找出Lk仅财，通過(guò)將L(k-1)與自身連接產(chǎn)生候選k項(xiàng)集的集合狈究。
# 執(zhí)行L(k-1)自然連接，其中L(k-1)的元素l1,l2是可連接的，僅當(dāng)它們前(K-2)個(gè)項(xiàng)相同抖锥。即L(k-1)的元素l1,l2是可連接的亿眠。
def createCk(Lk_1, k):
? ? CK = set()
? ? list_Lk_1 = list(Lk_1)? # 將K-1頻繁項(xiàng)集的集合轉(zhuǎn)換為列表形式
? ? for i in range(0, len(Lk_1)):
? ? ? ? for j in range(1, len(Lk_1)):
? ? ? ? ? ? l1 = list(list_Lk_1[i]) #l1,l2為L(zhǎng)k-1的項(xiàng)集
? ? ? ? ? ? l2 = list(list_Lk_1[j])
? ? ? ? ? ? l1.sort()
? ? ? ? ? ? l2.sort()
? ? ? ? ? ? if l1[0:k - 2] == l2[0:k - 2]:? # 若l1,l2的前k-2個(gè)項(xiàng)相同
? ? ? ? ? ? ? ? Ck_item = list_Lk_1[i] | list_Lk_1[j]? # 將l1,l2的值并集賦給候選集子集
? ? ? ? ? ? ? ? if cut(Ck_item, Lk_1):? # 剪枝后添加到k候選集
? ? ? ? ? ? ? ? ? ? CK.add(Ck_item)
? ? return CK
# 根據(jù)候選集選出頻繁項(xiàng)集的集合，篩去不是D_set子集的和非頻繁項(xiàng)集
def createLk(CK, D_set, min_sup):
? ? Lk = set()
? ? pre_dict ={}
? ? LkDict={}
? ? for row in D_set:? # 對(duì)每個(gè)在D_set子集中的候選項(xiàng)計(jì)算支持度
? ? ? ? for item in CK:
? ? ? ? ? ? if item.issubset(row):
? ? ? ? ? ? ? ? if item not in pre_dict:
? ? ? ? ? ? ? ? ? ? pre_dict[item] = 1
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? pre_dict[item] = pre_dict[item] + 1
? ? t_num = float(len(D_set)) #整個(gè)數(shù)據(jù)集的事務(wù)個(gè)數(shù)
? ? for x in pre_dict:
? ? ? ? if pre_dict[x]/t_num >=min_sup:? # 判斷是否大于最小支持度
? ? ? ? ? ? Lk.add(x)
? ? ? ? ? ? LkDict[x]=pre_dict[x]/t_num
? ? return Lk,LkDict
def generate_L(D_set, k, min_sup): #生成頻繁項(xiàng)集集合磅废，接收createLk函數(shù)返回的每個(gè)頻繁k項(xiàng)集集合和他們的支持度纳像，并保存到列表Support中
? ? Support =[]
? ? C1 = pre_C1(D_set)? ? #生成1頻繁項(xiàng)集候選集
? ? L1= createLk(C1, D_set, min_sup)[0] #生成1頻繁項(xiàng)集
? ? Support.append(createLk(C1, D_set, min_sup)[1]) #將1頻繁項(xiàng)集和支持度的字典添加到列表Support中
? ? Lk_1 = L1 #用1頻繁項(xiàng)集初始化k-1頻繁項(xiàng)集集合
? ? L = []
? ? L.append(Lk_1)
? ? for i in range(2, k + 1):
? ? ? ? Ci = createCk(Lk_1, i)
? ? ? ? Li= createLk(Ci, D_set, min_sup)[0]
? ? ? ? Support.append(createLk(Ci, D_set, min_sup)[1])
? ? ? ? Lk_1 = Li.copy()
? ? ? ? L.append(Lk_1)
? ? ? ? # Support.append(su[i])
? ? # print su
? ? return Support
? ? # 打印頻繁項(xiàng)集和支持度
if __name__ == "__main__":
? ? """
? ? Test
? ? """
? ? print "請(qǐng)等待，該數(shù)據(jù)大小為前%d用戶的所有觀影數(shù)據(jù):"% len(load_data_set())
? ? D_set = load_data_set()
? ? Support = generate_L(D_set, 3, min_sup=0.2)
? ? # len_data=float(len(D_set))
? ? for su in Support:
? ? ? ? print "-" * 50
? ? ? ? print "frequent " + str(len(list(su.keys())[0])) + "-itemsets\t\tsupport"
? ? ? ? print "-" * 50
? ? ? ? for key in su:
? ? ? ? ? ? print "%s:\t%s" % (key, su[key])
五拯勉、問(wèn)題分析
問(wèn)題：速度過(guò)慢竟趾，存在效率問(wèn)題,一開始采用了從字典中剔除不大于最小支持度的方法，過(guò)于耗時(shí)宫峦，時(shí)間復(fù)雜度為 n^2
解決方法：?jiǎn)尾秸{(diào)試查找耗時(shí)原因岔帽，改進(jìn)數(shù)據(jù)結(jié)構(gòu)和算法。
1导绷、在createLk()中將原本的剔除方法改為增添大于最小支持度的項(xiàng)犀勒，同時(shí)在本函數(shù)中計(jì)算支持度
2、在generate_L()方法中將原先的先用su字典接收返回值妥曲，再添加到Support列表中改為直接用Support列表接收返回值,相應(yīng)的修改最終打印過(guò)程為每個(gè)Support列表中的頻繁項(xiàng)集和支持度組成的字典贾费，打印其鍵和值。
?
