设
为所有项目的集合，
为事务数据库，事物
是一个项目子集（
）。每一个事务具有唯一的事务标识
。设
是一个由项目构成的集合，称为
。事务
。如果项集
个项目，则称其为
项集
。如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是
关联规则是形如
的逻辑蕴含式，其中
，且
如果事务数据库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
网友评论