一、问题描述
频繁模式挖掘搜索给定数据集中反复出现的联系，使用Apriori算法挖掘1M电影数据集中用户喜爱的电影之间的关联，分析用户的观影喜好，帮助推荐电影，例如：如果一位用户观看并喜爱了电影《你的名字》，他有多大可能也会观看《秒速5厘米》。
二、主要设备（软件）
Ubuntu,python2.7
三、Apriori算法
算法使用的是逐层搜索的迭代方法，使用K频繁项集生成k+1频繁项集，扫描数据库，累计每个项的计数，收集满足最小支持度的项生成频繁1项集用它找出频繁2项集，每次都使用前一个找出后一个频繁项集，每个Lk都需要一次数据的完整扫描。
在从Lk-1找Lk时为了提高效率，压缩搜索空间，使用连接步和剪枝步。连接步：通过将Lk-1于自身连接产生候选集k项集的集合。剪枝规则：将不可能的解提前过滤，如果有一个项集不是频繁项集，那么它的超集也一定不频繁，不作为候选集，不做最小支持度测试即任何非频繁的（k-1)项集都不是频繁k项集的子集。
四、实验过程
收集数据
使用了MovieLens数据集ml-1m，数据大小为24.6MB的ratings.dat，数据按列依次为'user_id', 'name_id', 'rating_id', 'timestaps'。
输入数据
使用了pandas，基于numpy的工具，解决数据分析任务。
数据结构：
Series:序列，类似一维数组
DataFrame:表格型数据结构，二维数组
导入数据集：pd.read_table() 读取表格的通用函数，使用时要指定文件中的内容分隔符。
定义与变量说明：
load_data_set()
加载数据集函数
rating_names
评价表的列名
rating_list
评价列表
ratings
训练集
D_set
name_id按user_id分组存放入子列表
pre_C1(D_set)
创建频繁1项集的候选集函数
C1
频繁1项集的候选集
pre_dict
频繁1项集项和个数的字典
cut(Ck, Lk_1)
剪枝函数
sub_Ck
k-1项候选子集的集合
createCk(Lk_1, k):
list_Lk_1
连接步：生成频繁k项集的候选集集合
K-1项频繁项集集合的列表形式
l1,l2
Lk-1的项集
createLk(CK, D_set, min_sup)
根据候选集选出频繁项集集合的函数筛去不是D_set子集的和非频繁项集
Lk
K频繁项集的集合
LkDict
存放k频繁项集和支持度的字典
Support =[]
存放所有k频繁项集集合的列表
Lk_1
k-1频繁项集集合
L
总频繁项集集合的列表
t_num
整个数据集的事务个数
训练算法
# -*- coding:utf-8 -*-
import pandas as pd
#使用pandas读取文件并选取前200个用户喜欢的电影，分割为训练集，标准：评分大于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
# 创建频繁1项集的候选集的集合
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]) # 通过循环对data_set中的每个子列表内部的每个元素产生不可变集合
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)项集都不是频繁k项集的子集
def cut(Ck, Lk_1):
for item in Ck: # 候选k项集的集合
sub_Ck = Ck - frozenset([item]) # k-1项子集的集合
if sub_Ck not in Lk_1: # 如果一个候选的k项集的(k-1)项子集不在频繁项集L(K-1)中则该候选也不可能是频繁的
return False # 返回false该候选集不频繁。
else:
return True
# 连接步：生成频繁k项集的候选集的集合，为找出Lk，通过将L(k-1)与自身连接产生候选k项集的集合。
# 执行L(k-1)自然连接，其中L(k-1)的元素l1,l2是可连接的，仅当它们前(K-2)个项相同。即L(k-1)的元素l1,l2是可连接的。
def createCk(Lk_1, k):
CK = set()
list_Lk_1 = list(Lk_1) # 将K-1频繁项集的集合转换为列表形式
for i in range(0, len(Lk_1)):
for j in range(1, len(Lk_1)):
l1 = list(list_Lk_1[i]) #l1,l2为Lk-1的项集
l2 = list(list_Lk_1[j])
l1.sort()
l2.sort()
if l1[0:k - 2] == l2[0:k - 2]: # 若l1,l2的前k-2个项相同
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
# 根据候选集选出频繁项集的集合，筛去不是D_set子集的和非频繁项集
def createLk(CK, D_set, min_sup):
Lk = set()
pre_dict ={}
LkDict={}
for row in D_set: # 对每个在D_set子集中的候选项计算支持度
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)) #整个数据集的事务个数
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): #生成频繁项集集合，接收createLk函数返回的每个频繁k项集集合和他们的支持度，并保存到列表Support中
Support =[]
C1 = pre_C1(D_set) #生成1频繁项集候选集
L1= createLk(C1, D_set, min_sup)[0] #生成1频繁项集
Support.append(createLk(C1, D_set, min_sup)[1]) #将1频繁项集和支持度的字典添加到列表Support中
Lk_1 = L1 #用1频繁项集初始化k-1频繁项集集合
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
# 打印频繁项集和支持度
if __name__ == "__main__":
"""
Test
"""
print "请等待，该数据大小为前%d用户的所有观影数据:"% 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])
五、问题分析
问题：速度过慢，存在效率问题,一开始采用了从字典中剔除不大于最小支持度的方法，过于耗时，时间复杂度为 n^2
解决方法：单步调试查找耗时原因，改进数据结构和算法。
1、在createLk()中将原本的剔除方法改为增添大于最小支持度的项，同时在本函数中计算支持度
2、在generate_L()方法中将原先的先用su字典接收返回值，再添加到Support列表中改为直接用Support列表接收返回值,相应的修改最终打印过程为每个Support列表中的频繁项集和支持度组成的字典，打印其键和值。
