机器学习算法：关联规则分析-六虎

大众号：尤而小屋
作者：Peter
修改：Peter

大家好，我是Peter~

今日给大家共享一个经典的机器学习算法：相关规矩剖析，从理论到代码到实战，悉数拉满。

本文首要内容：

文章过长，建议收藏

经典事例

相关剖析是一种从大规模的数据会集寻觅风趣联系的办法。一个常常被用到相关剖析的比方：购物篮剖析。

通过检查哪些产品常常在一同被顾客购买，能够协助商店去了解用户的购买行为。

经典的啤酒和尿布的事例：

某家超市的销售管理人员在剖析销售订单时发现，啤酒与尿布这两件看起来毫不相关的产品居然常常会出现在同一个订单中。

后来跟踪调查发现，本来年轻夫妇一般在周五晚上妻子会组织老公去超市购买尿布，而老公在购买尿布时总会忍不住顺便给自己买上几罐啤酒。

这便是为什么啤酒和尿布这两件看起来毫不相关的产品常常会出现在同一个购物篮中。

为了解决啤酒和尿布一同出现的问题，这样便引出了相关规矩剖析的算法。

相关规矩现在还被用在许多应用领域中，包括网络用法挖掘、侵略检测、连续生产及生物信息学中。

用公式能够标明为：

$\frac {num(XY)}{num(samples)}$

支撑度是针对项集的。在实践的需求中，能够指定一个最小支撑度，从而来保留满意最小支撑度的项集，起到数据过滤的作用。

可信度/置信度

可信度/置信度 Confidence：是针对一条诸如{尿布}—>{葡萄酒}的相关规矩来进行界说的。咱们能够将可信度界说为：

支撑度{尿布, 葡萄酒} / 支撑度{尿布}

在上面的比方中：支撑度{尿布, 葡萄酒} = 3/5；支撑度{尿布}=4/5。那么：可信度便是(3/5) / (4/5) = 3/4=75%

这样的含义便是：在一切包括尿布的订单中，有75%的包括葡萄酒

假如用条件概率的公式能够标明为：

$\frac {P(XY)}{P(X)}$

也便是：在X产生的条件下Y产生的概率 = XY一同产生的概率 / X产生的概率

在上面的比方中，假定有一条相关规矩**{尿布,啤酒} —>{莴苣}**能够标明为：

$\frac {P(莴苣,啤酒,尿布)}{P(尿布,啤酒)}$

提高度

提高度Lift标明含有X的条件下，一同含有Y的概率，与Y总体产生的概率之比。也便是X对Y的置信度与Y总体产生的概率之比：

$Lift(X—>Y)=P(Y∣X)P(Y)=Confidence(X—>Y)P(Y)Lift(X—>Y)=\frac {P(Y|X)}{P(Y)} = \frac {Confidence(X—>Y)}{P(Y)}$

提高度反映了相关规矩中的X与Y的相关性强弱

提高度>1且越高标明正相关性越高
提高度<1且越低标明负相关性越高
提高度=1标明没有相关性

强相关规矩

一个重要的概念：强相关规矩。在实践的应用中，通常是：

先寻觅满意最小支撑度的频频项集
然后在频频项会集寻觅满意最小置信度的相关规矩

这样找出来的相关规矩称之为强相关规矩。

事例

通过一个简单的比方来了解3个目标。假定一个班级40个同学，男女各20个，核算他们对篮球和乒乓球的爱好：

性别	篮球	乒乓球
男（共20人）	18	20
女（共20人）	0	12

假定：X = {喜爱篮球}，Y={喜爱乒乓球}，求出**相关规矩{X—>Y}（既喜爱篮球，又喜爱乒乓球）**3个目标

1、针对男生

Support{X,Y}=18/20   # 18个人一同喜爱；20是男生总数
Confidence{X,Y}=P(Y|X)=P(XY)/P(X)=18/18=1 # 第一个18：标明一同喜爱的人数，第二个标明喜爱篮球人数
Lift{X,Y}=Confidence{X,Y} / P(Y)=1/1=1

此时提高度为1，阐明XY是相互独立，彼此互不影响。也便是说，在男生中喜爱篮球和乒乓球没有任何相关。

虽然支撑度和可信度都挺高的，但它们也不是一条强相关的规矩。

2、针对女生

Support{X,Y}=0/20=0  # 没有女生喜爱篮球
Confidence{X,Y}=P(Y|X)=P(XY)/P(X) = 0
Lift{X,Y}=0

在女生中完全没有任何相关

3、针对全体

Support{X,Y}=18/40=9/20
Confidence{X,Y}=P(Y|X)=P(XY)/P(X)=(18/40) / (18/40)=1
Lift{X,Y}=Confidence{X,Y}/P(Y) = 1 / (32/40)=5/4

在全体中支撑度和可信度都挺高，而且提高度也大于1，阐明XY是强相关的规矩。

Apriori算法

相关剖析的最终目标是找出强相关规矩。Apriori算法是闻名的相关规矩挖掘算法之一。算法的首要过程：

设定最小支撑度和最小置信度
根据最小支撑度找出一切的频频项集
根据最小的置信度发现强相关规矩

产品组合

假定有4种产品：产品0、产品1、产品2、产品3。能够快速理清被一同购买的产品组合。比方0号产品：

独自被购买
和某产品一同：01、02、03
和2种产品一同：012、013、023
和3种产品一同：0123

注释：第一个调集是 $\phi$ 。标明的是空集或许不包括物品的调集

支撑度核算

某个调集的支撑度：是指有多少比例的买卖记载包括了该调集。比方{0,3}调集的支撑度的核算：

遍历每个记载检查是否包括{0,3}。假如包括记载数加1
在遍历完悉数数据之后，运用得到的支撑度为：包括调集的总记载数 / 总的买卖记载数

上面的比方中，仅有4种产品，从【项集组合图】中咱们看到：需要遍历15次。当有N个产品，遍历的次数便是 $2^N-1$ 次。

数据量会剧增，核算时刻随之大量添加。为了解决这个问题，Apriori算法来了。

算法假定：假如某个项集是频频的，那么包括它的一切子集也是频频的。

浅了解下：假如项集{1,3}是频频的，那么{1}或许{3}也是频频的。也便是说：假如某个项集对错频频项集，那么它的一切超集都对错频频项集。

鄙人图中灰色标明的非频频项集。假如**{2,3}对错频频项集**，那么它的超集{023}、{123}、{0123}都对错频频项集。

关于超集和子集

假如调集A包括调集B中的悉数元素，且调集A或许存在调集B中不存在的元素，那么调集A便是调集B的超集，反之调集B便是便是调集A的超集。

假如调集A中一定存在调集B中不存在的元素，那么A便是B的真超集，反之B是A的真子集。

算法流程

给定一份数据或许模仿一份数据集dataSet
从原始数据会集创立C1（只含有一个元素的项集）
通过scan函数来扫描数据，找到满意大于最小支撑度的频频项集L1
将L1中的每个1-项集进行两两组合，重复过程3，找到频频项集L2
重复过程3,4直到k-项集循环完停止

C1到Ck代表1-项集，k-项集
L1到Lk代表的是含有k个数据集的频频项集
scan办法：扫描整个数据集。对数据进行过滤，去除那些不满意最小支撑度的数据

生成候选项集

1、模仿数据

def loadData():
    """
    模仿需要的数据
    """
    dataSet = [[1,3,4],[2,3,5],[1,2,3,5],[2,5]]
    return dataSet

2、生成基于单个元素的项集

必须运用frozenset，后续作为字典的键

def createC1(data):
    """
    功用：生成第一个候选数据集C1
    参数：原始数据集dataset
    返回：frozenset方式的候选调集C1
    """
    C1 = []
    for transaction in data:  # 遍历data的每条元素，比方：[1,3,4] 作为一个元素
        print(transaction)
        for item in transaction:  # 遍历data元素中的每个元素，比方：1,3,4,2,3,5...
            print(item)
            if not [item] in C1:  # 单个元素作为列表追加到C1中 [item]是为每个物品构建一个调集
                C1.append([item])
                print(C1)
    C1.sort()   # [[1], [2], [3], [4], [5]]
    return list(map(frozenset, C1))  # 对C1中的每个元素履行frozenset函数的功用

在生成C1的过程中，假如某个元素已经在其间，则大列表中不会在进行添加。

3、生成候选项集

def scanD(D, Ck, minSupport):
    """
    参数：
        D：传入数据dataset
        Ck：候选集列表
        最小支撑度
    """
    ssCnt = {}
    for tid in D:  # 遍历原始数据
        for can in Ck:  # 遍历k项会集的每个数据
            if can.issubset(tid):  # 判别can是否是tid的子集，返回的是布尔类型数据
                if can not in ssCnt.keys():  # 假如不在ssCnt的key里边，就赋值为1
                    ssCnt[can] = 1
                else:  # 不然再加1
                    ssCnt[can] += 1  
    numItems = float(len(D))  # 数据集的长度
    retList = []  # 频频项集
    supportData = {}  # 寄存候选项集Ck的支撑度字典：key-候选项  value-支撑度
    for key in ssCnt:  # 对key进行遍历
        support = ssCnt[key] / numItems  # 取出key对应的支撑度
        supportData[key] = support  # 寄存候选项集的支撑度
        if support >= minSupport:  # 判别假如大于最小支撑度就追加到列表中
            retList.append(key)
    return retList, supportData  # 频频项集 候选项集

其间{4}项集的置信度小于阈值0.5，直接被放弃了。

生成频频项集

算法的伪代码：

当调会集项的个数大于0时:
  构建一个k个项组成的候选项集的列表
  检查数据以确认每个项集都是频频的
  保留频频项集并构建k+1项组成的候选项集的列表

def aprioriGen(Lk,k):
    """
    功用：生成频频项集
    参数：
        Lk：包括k个元素的频频项集
        k：项集的元素个数
    返回：
        Ck：候选项集列表
    """
    Ck = []  # 频频项集，比方 {0、1}{0、2}和{1、2}
    length = len(Lk)  # 项集的数量，上面比方的话便是3
    for i in range(length):  
        for j in range(i+1, length):  
            # 前k-2个项集相同的话，就将两个调调集并，得到k的元素的调集
            L1 = list(Lk[i])[:k-2]
            L2 = list(Lk[j])[:k-2]
            L1.sort()  # 排序操作
            L2.sort()
            if L1==L2:
                Ck.append(Lk[i] | Lk[j])  # 兼并
    return Ck  # 候选项集列表

关于上述代码中k-2的解释：

假如咱们运用{0}、{1}、{2}，能够快速构建{0、1}{0、2}和{1、2}
当运用{0、1}、{0、2}和{1、2}来构建{0、1、2}的时分，假如咱们将调集两两兼并，就会得到{0、1、2}、{0、1、2}、{0、1、2}，也便是说数据是重读了三次。
当接下来扫描3个元素的项集列表来得到非重复成果，需要确保遍历列表的次数最少。假如比较调集{0、1}{0、2}和{1、2}的第一个元素，而且只对第一个元素相同的进行兼并操作，就能够得到调集{0、1、2}

再看二项集生成三项集的比方，假如有多个二项集的元素：{0,1}、{0,2}、{0,3}、{1,2}、{1,3}、{2,3}。

最终合成后是：{0,1,2}、{0,1,3}、{0,2,3}、{1,2,3}。其间{1,2,3}是最先由{1,2}、{1,3}生成的，且重复元素还在第一位，而不是{1,3}、{2,3}

类推下，假如是3项集生成4项集的话，便是首2位相同；生成n项集的便是前面的0到k-2位元素相同

aprioriGen(L1, 2)   # 调用函数
[frozenset({1, 3}),
 frozenset({1, 2}),
 frozenset({1, 5}),
 frozenset({2, 3}),
 frozenset({3, 5}),
 frozenset({2, 5})]

主函数

def apriori(D, minSupport=0.5):
    """
    功用：主函数
    函数：
        D：原数据
        minSupport：支撑度
    返回值：
        L：频频项集
        supportData：支撑度数据
    """
    C1 = createC1(D)  # 先生成C1候选项集
    L1, support = scanD(D, C1, minSupport)  # 扫描原始数据，找出满意minSupport的数据
    L = [L1]
    k = 2
    while (len(L[k-2]) > 0):
        Ck = aprioriGen(L[k-2], k)
        Lk, supK = scanD(D, Ck, minSupport)
        supportData.update(supK)
        L.append(Lk)
        k += 1
    return L, supportData

运行下主函数

L, supportData = apriori(dataSet, minSupport=0.5)

结论：当minsupport=0.5的时分，咱们能够看到1-项会集满意条件的数据

改变支撑度的作用：

apriori(dataSet, minSupport=0.7)
([[frozenset({3}), frozenset({2}), frozenset({5})], [frozenset({2, 5})], []],
 {frozenset({1}): 0.5,
  frozenset({3}): 0.75,
  frozenset({4}): 0.25,
  frozenset({2}): 0.75,
  frozenset({5}): 0.75,
  frozenset({1, 3}): 0.5,
  frozenset({2, 3}): 0.5,
  frozenset({3, 5}): 0.5,
  frozenset({2, 5}): 0.75,
  frozenset({1, 2}): 0.25,
  frozenset({1, 5}): 0.25,
  frozenset({2, 3, 5}): 0.5})

流程

首先从原始数据中通过扫描函数得到1-项集和相应的置信度；挑选满意置信度大于等于0.5，也便是support>=2的频频项集（右侧拐弯的大箭头）
然后将1-项集进行两两组合，得到2-项集。再次通过扫描函数，对原始数据再次进行扫描，检查2-项会集每个元素的置信度，找出挑选满意置信度大于等于0.5的频频项集（左侧拐弯的大箭头）
将2-项会集的数据两两组合，得到3-项会集的每个元素，对原始数据再次进行扫描，检查3-项会集每个元素的置信度，最后找到只有{235}满意

参考书籍

《机器学习实战》
《相关剖析算法（Association Analysis）Apriori算法和FP-growth算法初探》

机器学习算法：关联规则分析

经典事例

相关术语

业务库

业务

k-项集

相关规矩

频频项集

评估标准

支撑度

可信度/置信度

提高度

强相关规矩

事例

Apriori算法

产品组合

支撑度核算

关于超集和子集

算法流程

生成候选项集

生成频频项集

主函数

流程

参考书籍

作者信息

推广

机器学习算法：关联规则分析

经典事例

相关术语

业务库

业务

k-项集

相关规矩

频频项集

评估标准

支撑度

可信度/置信度

提高度

强相关规矩

事例

Apriori算法

产品组合

支撑度核算

关于超集和子集

算法流程

生成候选项集

生成频频项集

主函数

流程

参考书籍

相关文章

如何不依着惯性做事

使用 LangChain 开发 LLM 应用（3）：记忆（Memory）

大聪明教你学Java | SpringBoot 整合 Activiti7 实现工作流

大数据与 AI 的双向奔赴｜创原会畅聊云原生第12期·作者光临

作者信息

推广