关联分析

Apriori算法
优点：易编码实现
缺点：在大数据集上可能较慢
适用数据类型：数值型或者标称型数据

关联分析是一种在大规模数据集中寻找有趣关系的任务。这些关系可以有两种形式：频繁项集或者关联规则。
频繁项集(frequent item sets) 是经常出现在一起的物品的集合，关联规则(association rules) 暗示两种物品之间可能存在很强的关系。

一个项集的支持度(support) 被定义为数据集中包含该项集的记录所占的比例。
可信度或置信度(confidence) 是针对一条诸如{尿布}->{葡萄酒}的关联规则来定义的。这条规则的可信度被定义为“支持度({尿布，葡萄酒})/支持度({尿布})”。

支持度和可信度是用来量化关联分析是否成功的方法。

Apriori原理

Apriori算法一般过程：

(1) 收集数据：使用任意方法。
(2) 准备数据：任何数据类型都可以，因为我们只保存集合。
(3) 分析数据：使用任意方法。
(4) 训练算法：使用Apriori算法来找到频繁项集。
(5) 测试算法：不需要测试过程。
(6) 使用算法：用于发现频繁项集以及物品之间的关联规则。

对于包含N种物品的数据集共有$2^{N}-1$种项集组合。与组合数$C_{N}^{0},C_{N}^{1},C_{N}^{2}...,C_{N}^{N}$有关。
Apriori原理：如果某个项集是频繁的，它的子集也是频繁的。如果一个项集是非频繁集，那么它的所有超集也是非频繁的。

使用Apriori算法来发现频繁项集

Apriori算法的两个输入参数分别是：最小支持度和数据集。该算法首先会生成所有单个物品的项集列表，接着扫描交易记录来查看哪些项集满足最小支持度要求，那些不满足最小值尺度的集合会被去掉。然后，对剩下来的集合进行组合以生成包含两个元素的项集。接下来，再重新扫描交易记录，去掉不满足最小支持度的项集。该过程重复直到所有项集都被去掉。

生成候选项集

下面会创建一个用于构建初始集合的函数，也会创建一个通过扫描数据集以寻找交易记录子集的函数。数据集扫描的伪代码如下：

对数据集中的每条交易记录tran
对每个候选项集can
    检查一下can是否是tran的子集：
    如果是，则增加can的计数值
    对每个候选项集：
    如果其支持度不低于最小值，则保留该项集
    返回所有频繁项集列表

Apriori算法首先构建集合C1,然后扫描数据集来判断这些只有一个元素的项集是否满足最小支持度的要求。满足最小支持度要求的项集构成集合L1。L1中的元素相互组合构成C2，C2再进一步过滤变成L2。

import apriori

dataSet = apriori.loadDataSet()

dataSet

[[1, 3, 4],
 [2, 3, 5],
 [1, 2, 3, 5],
 [1, 2, 3, 4, 5],
 [1, 3, 4, 5],
 [1, 2, 3, 5, 6],
 [1, 2, 3, 5, 7],
 [1, 2, 3, 5, 8],
 [1, 2, 3, 5, 9],
 [2, 3, 5, 6],
 [2, 4, 5],
 [2, 5]]

reload(apriori)

<module 'apriori' from 'apriori.pyc'>

C1 = apriori.createC1(dataSet)

C1

[frozenset({1}),
 frozenset({2}),
 frozenset({3}),
 frozenset({4}),
 frozenset({5}),
 frozenset({6}),
 frozenset({7}),
 frozenset({8}),
 frozenset({9})]

D = map(set, dataSet)

D

[{1, 3, 4},
 {2, 3, 5},
 {1, 2, 3, 5},
 {1, 2, 3, 4, 5},
 {1, 3, 4, 5},
 {1, 2, 3, 5, 6},
 {1, 2, 3, 5, 7},
 {1, 2, 3, 5, 8},
 {1, 2, 3, 5, 9},
 {2, 3, 5, 6},
 {2, 4, 5},
 {2, 5}]

type(D[0])

set

L1, suppData0 = apriori.scanD(D, C1, 0.5)

L1

[frozenset({2}), frozenset({1}), frozenset({3}), frozenset({5})]

组织完整的Apriori算法

整个Apriori算法的伪代码如下：

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

reload(apriori)

<module 'apriori' from 'apriori.pyc'>

L, suppData = apriori.apriori(dataSet)

L

[[frozenset({2}), frozenset({1}), frozenset({3}), frozenset({5})],
 [frozenset({1, 3}),
  frozenset({2, 5}),
  frozenset({2, 3}),
  frozenset({3, 5}),
  frozenset({1, 5}),
  frozenset({1, 2})],
 [frozenset({1, 2, 5}),
  frozenset({1, 2, 3}),
  frozenset({1, 3, 5}),
  frozenset({2, 3, 5})],
 [frozenset({1, 2, 3, 5})],
 []]

L[0]

[frozenset({2}), frozenset({1}), frozenset({3}), frozenset({5})]

L[1]

[frozenset({1, 3}),
 frozenset({2, 5}),
 frozenset({2, 3}),
 frozenset({3, 5}),
 frozenset({1, 5}),
 frozenset({1, 2})]

L[2]

[frozenset({1, 2, 5}),
 frozenset({1, 2, 3}),
 frozenset({1, 3, 5}),
 frozenset({2, 3, 5})]

L[3]

[frozenset({1, 2, 3, 5})]

apriori.aprioriGen(L[0], 2)

[frozenset({1, 2}),
 frozenset({2, 3}),
 frozenset({2, 5}),
 frozenset({1, 3}),
 frozenset({1, 5}),
 frozenset({3, 5})]

apriori.aprioriGen(L[1], 3)

[frozenset({1, 3, 5}),
 frozenset({1, 2, 3}),
 frozenset({2, 3, 5}),
 frozenset({1, 2, 5})]

L, suppData = apriori.apriori(dataSet, minSupport=0.7)

L

[[frozenset({2}), frozenset({3}), frozenset({5})],
 [frozenset({2, 5}), frozenset({3, 5})],
 []]

suppData

{frozenset({7}): 0.08333333333333333,
 frozenset({5}): 0.9166666666666666,
 frozenset({3}): 0.8333333333333334,
 frozenset({6}): 0.16666666666666666,
 frozenset({3, 5}): 0.75,
 frozenset({8}): 0.08333333333333333,
 frozenset({4}): 0.3333333333333333,
 frozenset({2, 3}): 0.6666666666666666,
 frozenset({2, 5}): 0.8333333333333334,
 frozenset({1}): 0.6666666666666666,
 frozenset({2}): 0.8333333333333334,
 frozenset({9}): 0.08333333333333333}

从频繁项集中挖掘关联规则

要找到关联规则，我们首先从一个频繁项集开始。我们知道集合中的元素是不重复的，但我们想知道基于这些元素能否获得其他内容。如果有一个频繁项集{豆奶，莴苣}，那么就有可能有一条关联规则“豆奶->莴苣”。这意味着如果有人购买了豆奶，那么在统计上他会购买莴苣的概率较大。但是这一条反之并不总成立。即使“豆奶->莴苣”在统计上显著，那么“莴苣->豆奶”也不一定成立。

关联规则中箭头左侧集合称为前件 ，箭头右侧集合称为后件。第3节中给出了频繁项集的量化定义，即满足最小支持度要求。对于关联规则，这种量化的指标称为可信度。

一条规则P->H的可信度定义为support(P|H)}/support(P) 。Python中操作符|表示集合的并操作。P|H表示所有出现在集合P或者集合H中的元素。

类似上一节频繁项集生成，我们可以为每个频繁项集产生许多关联规则。如果某条规则并不满足最小可信度要求，则该规则的所有子集也不会满足最小可信度要求。

可以利用关联规则的这个性质属性来减少需要测试的规则数目。类似Apriori算法，可以首先从一个频繁项集开始，接着创建一个规则列表，其中规则右部只包含一个元素，然后对这些规则进行测试。接下来合并所有剩余规则来创建一个新的规则列表，其中规则右部包含两个元素。这种方法也被称为分级法。

reload(apriori)

<module 'apriori' from 'apriori.pyc'>

L, suppData = apriori.apriori(dataSet, minSupport=0.5)

L

[[frozenset({2}), frozenset({1}), frozenset({3}), frozenset({5})],
 [frozenset({1, 3}),
  frozenset({2, 5}),
  frozenset({2, 3}),
  frozenset({3, 5}),
  frozenset({1, 5}),
  frozenset({1, 2})],
 [frozenset({1, 2, 5}),
  frozenset({1, 2, 3}),
  frozenset({1, 3, 5}),
  frozenset({2, 3, 5})],
 [frozenset({1, 2, 3, 5})],
 []]

suppData

{frozenset({7}): 0.08333333333333333,
 frozenset({5}): 0.9166666666666666,
 frozenset({3}): 0.8333333333333334,
 frozenset({6}): 0.16666666666666666,
 frozenset({2}): 0.8333333333333334,
 frozenset({1, 2}): 0.5,
 frozenset({1, 5}): 0.5833333333333334,
 frozenset({3, 5}): 0.75,
 frozenset({1, 2, 3, 5}): 0.5,
 frozenset({8}): 0.08333333333333333,
 frozenset({2, 3, 5}): 0.6666666666666666,
 frozenset({4}): 0.3333333333333333,
 frozenset({2, 3}): 0.6666666666666666,
 frozenset({2, 5}): 0.8333333333333334,
 frozenset({1}): 0.6666666666666666,
 frozenset({1, 3}): 0.6666666666666666,
 frozenset({1, 3, 5}): 0.5833333333333334,
 frozenset({1, 2, 5}): 0.5,
 frozenset({1, 2, 3}): 0.5,
 frozenset({9}): 0.08333333333333333}

rules = apriori.generateRules(L, suppData, minConf=0.7)

frozenset([3]) --> frozenset([1]) conf: 0.8
frozenset([1]) --> frozenset([3]) conf: 1.0
frozenset([5]) --> frozenset([2]) conf: 0.909090909091
frozenset([2]) --> frozenset([5]) conf: 1.0
frozenset([3]) --> frozenset([2]) conf: 0.8
frozenset([2]) --> frozenset([3]) conf: 0.8
frozenset([5]) --> frozenset([3]) conf: 0.818181818182
frozenset([3]) --> frozenset([5]) conf: 0.9
frozenset([1]) --> frozenset([5]) conf: 0.875
frozenset([1]) --> frozenset([2]) conf: 0.75
frozenset([1]) --> frozenset([2, 5]) conf: 0.75
frozenset([1]) --> frozenset([2, 3]) conf: 0.75
frozenset([3]) --> frozenset([1, 5]) conf: 0.7
frozenset([1]) --> frozenset([3, 5]) conf: 0.875
frozenset([5]) --> frozenset([2, 3]) conf: 0.727272727273
frozenset([3]) --> frozenset([2, 5]) conf: 0.8
frozenset([2]) --> frozenset([3, 5]) conf: 0.8
frozenset([2, 3]) --> frozenset([1, 5]) conf: 0.75
frozenset([1, 5]) --> frozenset([2, 3]) conf: 0.857142857143
frozenset([1, 3]) --> frozenset([2, 5]) conf: 0.75
frozenset([1, 2]) --> frozenset([3, 5]) conf: 1.0
frozenset([1]) --> frozenset([2, 3, 5]) conf: 0.75

rules = apriori.generateRules(L, suppData, minConf=0)

frozenset([3]) --> frozenset([1]) conf: 0.8
frozenset([1]) --> frozenset([3]) conf: 1.0
frozenset([5]) --> frozenset([2]) conf: 0.909090909091
frozenset([2]) --> frozenset([5]) conf: 1.0
frozenset([3]) --> frozenset([2]) conf: 0.8
frozenset([2]) --> frozenset([3]) conf: 0.8
frozenset([5]) --> frozenset([3]) conf: 0.818181818182
frozenset([3]) --> frozenset([5]) conf: 0.9
frozenset([5]) --> frozenset([1]) conf: 0.636363636364
frozenset([1]) --> frozenset([5]) conf: 0.875
frozenset([2]) --> frozenset([1]) conf: 0.6
frozenset([1]) --> frozenset([2]) conf: 0.75
frozenset([5]) --> frozenset([1, 2]) conf: 0.545454545455
frozenset([2]) --> frozenset([1, 5]) conf: 0.6
frozenset([1]) --> frozenset([2, 5]) conf: 0.75
frozenset([3]) --> frozenset([1, 2]) conf: 0.6
frozenset([2]) --> frozenset([1, 3]) conf: 0.6
frozenset([1]) --> frozenset([2, 3]) conf: 0.75
frozenset([5]) --> frozenset([1, 3]) conf: 0.636363636364
frozenset([3]) --> frozenset([1, 5]) conf: 0.7
frozenset([1]) --> frozenset([3, 5]) conf: 0.875
frozenset([5]) --> frozenset([2, 3]) conf: 0.727272727273
frozenset([3]) --> frozenset([2, 5]) conf: 0.8
frozenset([2]) --> frozenset([3, 5]) conf: 0.8
frozenset([3, 5]) --> frozenset([1, 2]) conf: 0.666666666667
frozenset([2, 5]) --> frozenset([1, 3]) conf: 0.6
frozenset([2, 3]) --> frozenset([1, 5]) conf: 0.75
frozenset([1, 5]) --> frozenset([2, 3]) conf: 0.857142857143
frozenset([1, 3]) --> frozenset([2, 5]) conf: 0.75
frozenset([1, 2]) --> frozenset([3, 5]) conf: 1.0
frozenset([5]) --> frozenset([1, 2, 3]) conf: 0.545454545455
frozenset([3]) --> frozenset([1, 2, 5]) conf: 0.6
frozenset([2]) --> frozenset([1, 3, 5]) conf: 0.6
frozenset([1]) --> frozenset([2, 3, 5]) conf: 0.75

rules

[(frozenset({3}), frozenset({1}), 0.7999999999999999),
 (frozenset({1}), frozenset({3}), 1.0),
 (frozenset({5}), frozenset({2}), 0.9090909090909092),
 (frozenset({2}), frozenset({5}), 1.0),
 (frozenset({3}), frozenset({2}), 0.7999999999999999),
 (frozenset({2}), frozenset({3}), 0.7999999999999999),
 (frozenset({5}), frozenset({3}), 0.8181818181818182),
 (frozenset({3}), frozenset({5}), 0.8999999999999999),
 (frozenset({5}), frozenset({1}), 0.6363636363636365),
 (frozenset({1}), frozenset({5}), 0.8750000000000001),
 (frozenset({2}), frozenset({1}), 0.6),
 (frozenset({1}), frozenset({2}), 0.75),
 (frozenset({5}), frozenset({1, 2}), 0.5454545454545455),
 (frozenset({2}), frozenset({1, 5}), 0.6),
 (frozenset({1}), frozenset({2, 5}), 0.75),
 (frozenset({3}), frozenset({1, 2}), 0.6),
 (frozenset({2}), frozenset({1, 3}), 0.6),
 (frozenset({1}), frozenset({2, 3}), 0.75),
 (frozenset({5}), frozenset({1, 3}), 0.6363636363636365),
 (frozenset({3}), frozenset({1, 5}), 0.7000000000000001),
 (frozenset({1}), frozenset({3, 5}), 0.8750000000000001),
 (frozenset({5}), frozenset({2, 3}), 0.7272727272727273),
 (frozenset({3}), frozenset({2, 5}), 0.7999999999999999),
 (frozenset({2}), frozenset({3, 5}), 0.7999999999999999),
 (frozenset({3, 5}), frozenset({1, 2}), 0.6666666666666666),
 (frozenset({2, 5}), frozenset({1, 3}), 0.6),
 (frozenset({2, 3}), frozenset({1, 5}), 0.75),
 (frozenset({1, 5}), frozenset({2, 3}), 0.8571428571428571),
 (frozenset({1, 3}), frozenset({2, 5}), 0.75),
 (frozenset({1, 2}), frozenset({3, 5}), 1.0),
 (frozenset({5}), frozenset({1, 2, 3}), 0.5454545454545455),
 (frozenset({3}), frozenset({1, 2, 5}), 0.6),
 (frozenset({2}), frozenset({1, 3, 5}), 0.6),
 (frozenset({1}), frozenset({2, 3, 5}), 0.75)]

程序中generateRules就是按照规则的后件的元素数目来筛选的，当i=1时，直接调用calcConf函数来计算后件元素个数为1的全部情况。当i>1时，调用rulesFromConseq函数来计算后件元素个数大于等于2的全部情况。

关联分析可以用来发现大数据集中元素间的有趣关系，可以使用两种方式来量化这些关系。第一种方式是使用频繁项集，它会给出在一起经常出现的元素项。第二种方式是关联规则，每条关联规则意味着元素项之间的“如果...那么...”关系。