关联规则分析(频繁项集查找方法为apriori方法的Fk-1*Fk-1)

关联分析思想因其在生活中的某些方面（比如购物推荐）能够取得良好的效果，所以在机器学习里面占有一席之地，如今随着大数据时代的到来，找出数据之间的关系显得更加重要，这次，通过一个小例子来探究一下关联分析背后的秘密。

一：实验要求：

实验目的

1. 理解频繁项集、关联规则等基本概念

2. 运用Apriori算法分析数据中频繁项集和关联规则

实验问题描述

编写Apriori算法，分析出下表中数据集的频繁项集和关联规则，最小支持度为30%，最小置信度为50%。
讨论不同参数（最小支持度、最小置信度）对实验结果的影响。

实验要求

关联分析基本算法需要编程实现，不能直接调用第三方函数库
程序可以运行，输出结果

实验报告内容

1. 实验内容：

2. 设计思想：主要算法的基本思想。

3. 主要算法的程序实现：

4. 调试报告：调试过程中遇到的主要问题是如何解决的；对设计和编码的回顾讨论和分析以及对主要算法的改进设想。

5. 实验总结：对实验用到的理论知识的理解，在算法设计上有何创新。

实验报告提交要求

1. 实验报告应使用学校统一给定的实验报告的封面，实验名称为实验指导书中的实验名称。

2. 实验报告提交内容包括：1）实验报告的word版；2）程序源代码（单独放在一个文件夹内）。将上述2部分内容放在一个文件夹内。命名格式：班级-学号-姓名

3．实验完成后一周内，在课堂派上提交（直接上传原始文件，不要压缩）。

二：解决思路

代码：

"""
coding:utf-8
@author: Li Sentan
@time:2021.11.02
@file:guanliansys.py
"""
import itertools

def delsame(B,L):#B,L均为字符串，返回值是在B中删除两个字符串中的相同字符后的字符串
    b = sorted(B)
    c = b
    l = sorted(L)
    for i in l:
        for j in b:
            if i == j:
                c.remove(i)
    d = "".join(sorted(c))
    return d

def listtoset(m):#将二维列表转化为集合的列表
    a = []
    for i in range(len(m)):
        c = set()
        for j in range(len(m[i])):
            c.add(m[i][j])
        a.append(c)
    return a

#定义一个关联分析的类
class assys():
    def __init__(self,dataset,m = 1,minsupport = 0.5):
        self.a = listtoset(dataset)
        self.dataset = dataset
        self.m = m
        self.minsupport  =  minsupport
        self.Ck = dict()
        self.mincon = 0

    def createC1(self):#创造1-项集
        Cp1 = {}
        for transaction in self.dataset:
            for item in transaction:
                if item not in Cp1:
                    Cp1[item] = 0
                Cp1[item] += 1
        return Cp1

    def supportset(self, Cp1):#选出1-频繁项集
        lk = []
        C1 = dict()
        for key in Cp1:
            support = Cp1[key] / len(self.dataset)
            if support >= self.minsupport:
                lk.append(key)
                C1[key] = support
        return lk, C1

    def aprioriGen(self,Lk, k):#用Fk-1*Fk-1选出K-频繁项集并以字典的形式存储频繁项集的支持度。
        lk = []
        Cpk = dict()
        for i in range(len(Lk)):
            for j in range(i+1,len(Lk)):
                L1 = Lk[i][:k - 2]
                L2 = Lk[j][:k - 2]
                if L1 == L2:
                    c = Lk[i][:k - 1]+Lk[j][k-2]
                    b = set(sorted(c))
                    if c not in Cpk:
                        Cpk[c] = 0
                    for m in self.a:
                        if b.issubset(m):
                            Cpk[c] += 1
                    support = Cpk[c]/len(self.dataset)
                    if support >= self.minsupport:
                        self.Ck[c] = support
                        lk.append(c)
        return lk

    def apriori(self): #构造1-K频繁项集的结构函数，返回值是频繁项集的二维列表和带有支持度信息的字典
        Cp1 = self.createC1()
        L1,C1 = self.supportset(Cp1)
        self.Ck = C1
        L = [sorted(L1)]
        k = 2
        while (k<=self.m and len(L[k - 2]) > 0):
            lk = self.aprioriGen(L[k - 2], k)
            L.append(lk)
            k += 1
        if L[-1] == []:
            L = L[:-1]
        return L,self.Ck

    def culcon(self,L,mincon):#选择关联项的函数
        o = dict()
        if len(L) >= 2:
            for i in range(len(L)-1,0,-1):
                for j in range(len(L[i])-1,-1,-1):
                    m = sorted(L[i][j])
                    for q in range(1, len(m)):
                        for x in itertools.combinations(m, q):#以元组的形式返回m(为数组）中所有长度为q的子序列，所以下面用.join()方法时要加list()
                            result = "".join(list(x))
                            w = L[i][j]
                            a = result
                            b = delsame(w,a)
                            con = self.Ck[w]/self.Ck[a]
                            if con >=mincon:
                                o[a + "--->" + b] = round(con,2)
                                g = sorted(b)
                                for f in range(1, len(g)):
                                    for h in itertools.combinations(g, f):
                                        result2 = "".join(list(h))
                                        con2 = self.Ck["".join(sorted(result2+a))] / self.Ck[a]
                                        o[a + "--->" + "".join(sorted(result2))] = round(con2,2)
        return o

if __name__ == '__main__':

    b = [["a", "b", "d", "e"], ["b", "c", "d"], ["a", "b", "d", "e"], ["a", "c", "d", "e"], ["b", "c", "d", "e"],
         ["b", "d", "e"], ["c", "d"], ["a", "b", "c"], ["a", "d", "e"], ["b", "d"]]

    minsupport = eval(input("请输入最小支持度："))
    M = eval(input("请输入M的值：(0代表输出K-频繁项集，否则代表默认输出1到K-频繁项集)"))
    k = eval(input("请输入k的值，得到相应的频繁项集："))
    c = assys(b,k,minsupport)
    L,Ck = c.apriori()
    if M==0:
        try:
            print("{",end="")
            for key in L[k-1]:
                print("{}:{}".format(key,Ck[key]),end=" ")
            print("}")
        except:
            print("没有该频繁项集。")
    else:
        print(Ck)
    mincon = eval(input("请输最小关联度："))
    n = c.culcon(L,mincon)
    for key,value in n.items():
        print("{}:{}".format(key,value))

如果直接看代码的话还是有些难度的，不过咱们先来分析分析解决思路：

1.我们想要能够找到其中的1-K频繁项集，所以我们从1-频繁项集开始找，一直到K-频繁项集。好的，那我们给定一个最小支持度，根据支持度先把1-频繁项集找出来，再在1-频繁项集的基础上根据Fk-1*Fk-1原则逐次把2，3…..K-频繁项集找出来。

2.我们想要得到所有的关联项，只需要知道图中圈起来的公式来计算置信度：由公式延伸得知：若X–>AB,则必有：X–>A,X–>B,由于置信度是建立在频繁项集的基础上，所以我们只在所有的频繁项集上寻找满足置信度的关联项。我们先从k-频繁项集出发，将k-频繁项集分成两部分，且两部分都不为空，共有（2的K次方-2）种分配方式。计算第一部分与第二部分的关联置信度，再根据公式延伸得到的规则，若X–>ABC,则X–>ABC的所有真子集，重复上述过程直至2-频繁项集，最终即可得到2-K频繁项集内的所有关联项。

理清了思路，代码实现就简单便捷了。

culcon()方法之前的apriori()是为了得到1-K的频繁项集，在apriori()中调用了aprioriGen(self,Lk, k)，aprioriGen(self,Lk, k)是为了寻找K-频繁项集，最后将频繁项集和支持度存在一个字典Ck中,同时L是一个二维列表，每个频繁项集是其中的一个列表。并且频繁项集以字符串的形式表示。笔者在实现过程中用到很多次字符串，列表，集合的相互转换，看官在进行实现时需要慢慢整理数据的类型，其思路上文已经给出。

笔者之前在culcon()方法实现时犯了一个错误，就是把上述的公式延伸给记反了，导致后面结果出错，还有一点就是，这个方法有点绕，毕竟有好多个for循环，还有要说明的地方就是itertools.combinations(m, q)，即可以创建一个迭代器，返回m(为数组）中所有长度为q的子序列,结果以元组的形式返回，返回的子序列中的项按输入m中的顺序排序,所以加了for循环之后，可以看作是生成了不包含m本身的m的真子集。最后运行得到最终结果。

笔者方法的特点是多种数据形式的转换，看官们一定要搞清楚sorted（），””.join(list())等数据转换的方法。不然很容易就迷糊了，哈哈。

运行结果如下：