关联规则挖掘算法

设为所有项目的集合，为事务数据库，事物是一个项目子集（）。每一个事务具有唯一的事务标识。设是一个由项目构成的集合，称为。事务包含项集，当且仅当。如果项集中包含个项目，则称其为

项集在事务数据库中出现的次数占总事务的百分比叫做项集的。如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是

关联规则是形如的逻辑蕴含式，其中，且

如果事务数据库D中有的事务包含， 则称关
联规则的⽀持度为

关联规则的信任度为
也就是：

强关联规则就是⽀持度和信任度分别满⾜⽤户
给定阈值的规则

例子

交易ID	购买的商品
2000	A,B,C
1000	A,C
4000	A,D
5000	B,E,F

设最⼩⽀持度为50%, 最⼩可信度为 50%, 则可得到

• A ⇒ C (50%, 66.6%)
• C ⇒ A (50%, 100%)

Apriori算法

命名源于算法使⽤了频繁项集性质的先验（ Prior） 知识。

Apriori算法将发现关联规则的过程分为两个步骤：

• 通过迭代， 检索出事务数据库中的所有频繁
  项集， 即⽀持度不低于⽤户设定的阈值的项集；
• 利⽤频繁项集构造出满⾜⽤户最⼩信任度的
  规则。
• 挖掘或识别出所有频繁项集是该算法的核⼼， 占整个
  计算量的⼤部分

Apriori的性质

性质1： 频繁项集的所有⾮空⼦集必为频繁项集。

性质2： ⾮频繁项集的超集⼀定是⾮频繁的。

Apriori的步骤

连接步： 为找Lk，通过将Lk-1与⾃⾝连接产⽣候选k项集
的集合

剪枝步： Ck是Lk 的超集， 也就是说， Ck的成员可以是
也可以不是频繁的， 但所有的频繁k项集都包含在Ck中。
任何⾮频繁的（ k-1） 项集都不是频繁k项集的⼦集

Apriori算法实例

现有A、 B、 C、 D、 E五种商品的交易记录表， 试找出
三种商品关联销售情况(k=3)， 最小支持度=50%

交易号	商品代码
100	A,C,D
200	B,C,E
300	A,B,C,E
400	B,E

读入数据

data = {'交易号':range(100,500,100),'商品代码':['A,C,D', 'B,C,E', 'A,B,C,E', 'B,E']}
df_data = pd.DataFrame(data=data)

算一个事务集在事务数据库的支持度

def get_score(values):
    score = 0.0
    b = True
    for value_code in df_data['商品代码'].values:
        if values.difference(value_code.split(',')) == set():
            score += 1
    return score/len(df_data)

首先构造等候集C

c = []
for code in df_data['商品代码'].values:
    for _ in code.split(','):
        if {_} not in c:
            c.append({_})

输出c

 [{'A'}, {'C'}, {'D'}, {'B'}, {'E'}]

计算L

from collections import defaultdict

score = 0.5
# 这里用字典来保存频繁项集
L = defaultdict(list)
i = 0
length = len(c)
while c:
    i += 1
    for ci in c:
        if get_score(ci) >= score:
            L[i].append(ci)
    print L[i]
    c = get_c(L[i])

[set(['A']), set(['C']), set(['B']), set(['E'])]
[set(['A', 'C']), set(['C', 'B']), set(['C', 'E']), set(['B', 'E'])]
[set(['C', 'B', 'E'])]

可以得出三种商品关联销售情况(k=3)， 最小支持度=50%只有一组（CBE）

Apriori算法的不⾜

• 中的项集是⽤来产⽣频集的候选集.

• 最后的频集必须是的⼀个⼦集。

• 中的每个元素需在交易数据库中进⾏验证来决定其是否加
  ⼊

• 验证过程是性能瓶颈
  交易数据库可能⾮常⼤
  ⽐如频集最多包含10个项， 那么就需要扫描交易数据库10遍
  需要很⼤的I/O负载。

FP-tree算法（不⽤⽣成候选集）

2000年， Han等提出了⼀个称为FP-tree的算法。
FP-tree算法只进⾏2次数据库扫描。

• no候选集
• 直接压缩数据库成⼀个频繁模式树
• 通过这棵树⽣成关联规则。

FP-tree两个主要步骤

• ①利⽤事务数据库中的数据构造FP-tree；
• ②从FP-tree中挖掘频繁模式

步骤1： 构造 FP-tree树

具体过程：
1.  扫描数据库⼀次， 得到频繁1-项集
2.  把项按⽀持度递减排序
3.  再⼀次扫描数据库， 建⽴FP-tree

FP-tree 结构的好处

• 完备
  不会打破交易中的任何模式
  包含了频繁模式挖掘所需的全部信息
• 紧密
  去除不相关信息—不包含⾮频繁项
  ⽀持度降序排列: ⽀持度⾼的项在FP-tree中共享的机会也⾼
  决不会⽐原数据库⼤（如果不计算树节点的额外开销)

步骤2： 频繁模式的挖掘

• 具体过程:
  根据事务数据库D 和最⼩⽀持度min_sup， 调⽤建树过程建⽴FP-tree;
  if (FP-tree 为简单路径)
  将路径上⽀持度计数⼤于等于min_sup 的节点任意组合， 得到所需
  的频繁模式
  else
  初始化最⼤频繁模式集合为空
  按照⽀持频率升序， 以每个1 － 频繁项为后缀， 调⽤挖掘算法挖掘
  最⼤频繁模式集
  根据最⼤频繁模式集合中最⼤频繁模式， 输出全部的频繁模式

FP-tree算法的一个例子

事物数据库:

Tid	Items
1	I1,I2,I5
2	I2,I4
3	I2,I3
4	I1,I2,I4
5	I1,I3
6	I2,I3
7	I1,I3
8	I1,I2,I3,I5
9	I1,I2,I3

df_fp_data = pd.DataFrame({'Tid':xrange(1,10,1), 'Items':['I1,I2,I5', 'I2,I4','I2,I3','I1,I2,I4',
                                                         'I1,I3', 'I2,I3','I1,I3','I1,I2,I3,I5',
                                                         'I1,I2,I3']})

def get_item_number(item):
    for el in item.split(','):
        dic_items[el]+=1   
dic_items = defaultdict(int)

df_fp_data['Items'].map(get_item_number)

dic_items

统计了每一项频数，输出

defaultdict(int, {'I1': 6, 'I2': 7, 'I3': 6, 'I4': 2, 'I5': 2})

按照频数对Items由大到小排序

df_fp_data['Items'] = df_fp_data['Items'].map(lambda items: 
        ','.join(sorted(items.split(','), key=lambda item:-dic_items[item])))

创建节点类与树类

# 节点
class Node():
    def __init__(self, item):
        self.item = item
        self.numbers = 1
        self.children = []
        
class Tree():
    def __init__(self, root=None):
        self.root = root
    # 加入items
    def add_nodes(self, items):
        # 建立根节点
        if self.root is None:
            self.root = Node('null')
        temp = self.root.children
        if temp == [] and len(items)>0:
            temp.append(Node(items[0]))
            items.pop(0)
            temp_tree = Tree(temp[0])
            temp_tree.add_nodes(items)
        elif temp != []:
            for item in items:
                b = False
                for node in temp:
                    if node.item == item:
                        node.numbers += 1
                        temp = node.children
                        b = True
                        break
                if b is False:
                    temp_tree = Tree(Node(item))
                    temp_tree.add_nodes(items[items.index(item)+1:])
                    temp.append(temp_tree.root)
                    break
    def print_tree(self):
        node = self.root
        stack = [node]
        while stack != []:
            temp_node = stack.pop(0)
            print temp_node.item,temp_node.numbers
            stack += temp_node.children   
    def preorder_traversal(self):
        # 采用先序遍历
        stack = []
        path = []
        temp = self.root
        while temp or stack:
            if temp is not None:
                print temp.item, temp.numbers
                stack.append(temp)
                if temp.children == []:
                    temp = None
                else:
                    temp = temp.children.pop(0)
            else:
                children = stack[-1].children
                if children == []:
                    stack.pop()
                else:
                    if len(children) == 1:
                        stack.pop()
                    temp = children.pop(0)
         

将节点加入树中

tree = Tree(Node('null'))
for item in df_fp_data['Items'].values:
    tree.add_nodes(item.split(','))

打印树(层次打印)

tree.print_tree()

null 1
I2 7
I1 2
I1 4
I4 1
I3 2
I3 2
I5 1
I4 1
I3 2
I5 1

FP-tree树

tree.preorder_traversal()

输出

null 1
I2 7
I1 4
I5 1
I4 1
I3 2
I5 1
I4 1
I3 2
I1 2
I3 2