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

关联规则分析(频繁项集查找方法为apriori方法的Fk-1*Fk-1)关联分析思想因其在生活中的某些方面(比如购物推荐)能够取得良好的效果,所以在机器学习里面占有一席之地,如今随着大数据时代的到来,找出数据之间的关系显得更加重要,这次,通过一个小例子来探究一下关联分析背

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

一:实验要求: 

实验目的

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

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

实验问题描述

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

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

实验要求

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

实验报告内容

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.我们想要得到所有的关联项,只需要知道图中圈起来的公式来计算置信度:关联规则分析(频繁项集查找方法为apriori方法的Fk-1*Fk-1) 由公式延伸得知:若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())等数据转换的方法。不然很容易就迷糊了,哈哈。

运行结果如下:关联规则分析(频繁项集查找方法为apriori方法的Fk-1*Fk-1)

今天的文章关联规则分析(频繁项集查找方法为apriori方法的Fk-1*Fk-1)分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:http://bianchenghao.cn/63571.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注