使用Apriori算法挖掘频繁项集

一、问题描述

频繁模式挖掘搜索给定数据集中反复出现的联系，使用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列表中的频繁项集和支持度组成的字典，打印其键和值。