設(shè)
為所有項(xiàng)目的集合遭笋，
為事務(wù)數(shù)據(jù)庫(kù)，事物
是一個(gè)項(xiàng)目子集（
）徒探。每一個(gè)事務(wù)具有唯一的事務(wù)標(biāo)識(shí)
瓦呼。設(shè)
是一個(gè)由項(xiàng)目構(gòu)成的集合，稱為
测暗。事務(wù)
。如果項(xiàng)集
個(gè)項(xiàng)目碗啄，則稱其為
項(xiàng)集
质和。如果項(xiàng)集的支持度超過用戶給定的最小支持度閾值，就稱該項(xiàng)集是
關(guān)聯(lián)規(guī)則是形如
的邏輯蘊(yùn)含式稚字，其中
，且
如果事務(wù)數(shù)據(jù)庫(kù)D中有
的事務(wù)包含
胆描， 則稱關(guān)
聯(lián)規(guī)則的?持度為
關(guān)聯(lián)規(guī)則的信任度為
也就是：
強(qiáng)關(guān)聯(lián)規(guī)則就是?持度和信任度分別滿??戶
給定閾值的規(guī)則
例子
| 交易ID | 購(gòu)買的商品 |
|---|---|
| 2000 | A,B,C |
| 1000 | A,C |
| 4000 | A,D |
| 5000 | B,E,F |
設(shè)最??持度為50%, 最?可信度為 50%, 則可得到
- A ? C (50%, 66.6%)
- C ? A (50%, 100%)
Apriori算法
命名源于算法使?了頻繁項(xiàng)集性質(zhì)的先驗(yàn)（ Prior） 知識(shí)瘫想。
Apriori算法將發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的過程分為兩個(gè)步驟：
- 通過迭代， 檢索出事務(wù)數(shù)據(jù)庫(kù)中的所有頻繁
項(xiàng)集昌讲， 即?持度不低于?戶設(shè)定的閾值的項(xiàng)集国夜； - 利?頻繁項(xiàng)集構(gòu)造出滿??戶最?信任度的
規(guī)則。 - 挖掘或識(shí)別出所有頻繁項(xiàng)集是該算法的核?短绸， 占整個(gè)
計(jì)算量的?部分
Apriori的性質(zhì)
性質(zhì)1： 頻繁項(xiàng)集的所有?空?集必為頻繁項(xiàng)集车吹。
性質(zhì)2： ?頻繁項(xiàng)集的超集?定是?頻繁的。
Apriori的步驟
連接步： 為找Lk醋闭，通過將Lk-1與??連接產(chǎn)?候選k項(xiàng)集
的集合
剪枝步： Ck是Lk 的超集窄驹， 也就是說， Ck的成員可以是
也可以不是頻繁的证逻， 但所有的頻繁k項(xiàng)集都包含在Ck中乐埠。
任何?頻繁的（ k-1） 項(xiàng)集都不是頻繁k項(xiàng)集的?集
Apriori算法實(shí)例
現(xiàn)有A、 B、 C饮戳、 D、 E五種商品的交易記錄表洞拨， 試找出
三種商品關(guān)聯(lián)銷售情況(k=3)扯罐， 最小支持度=50%
| 交易號(hào) | 商品代碼 |
|---|---|
| 100 | A,C,D |
| 200 | B,C,E |
| 300 | A,B,C,E |
| 400 | B,E |
讀入數(shù)據(jù)
data = {'交易號(hào)':range(100,500,100),'商品代碼':['A,C,D', 'B,C,E', 'A,B,C,E', 'B,E']}
df_data = pd.DataFrame(data=data)
算一個(gè)事務(wù)集在事務(wù)數(shù)據(jù)庫(kù)的支持度
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)
首先構(gòu)造等候集C
c = []
for code in df_data['商品代碼'].values:
for _ in code.split(','):
if {_} not in c:
c.append({_})
輸出c
[{'A'}, {'C'}, {'D'}, {'B'}, {'E'}]
計(jì)算L
from collections import defaultdict
score = 0.5
# 這里用字典來保存頻繁項(xiàng)集
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'])]
可以得出三種商品關(guān)聯(lián)銷售情況(k=3)， 最小支持度=50%只有一組（CBE）
Apriori算法的不?
中的項(xiàng)集是?來產(chǎn)?頻集的候選集.
最后的頻集
必須是
?驗(yàn)證過程是性能瓶頸
交易數(shù)據(jù)庫(kù)可能?常?
?如頻集最多包含10個(gè)項(xiàng)歹河， 那么就需要掃描交易數(shù)據(jù)庫(kù)10遍
需要很?的I/O負(fù)載。
FP-tree算法（不??成候選集）
2000年花吟， Han等提出了?個(gè)稱為FP-tree的算法秸歧。
FP-tree算法只進(jìn)?2次數(shù)據(jù)庫(kù)掃描。
- no候選集
- 直接壓縮數(shù)據(jù)庫(kù)成?個(gè)頻繁模式樹
- 通過這棵樹?成關(guān)聯(lián)規(guī)則衅澈。
FP-tree兩個(gè)主要步驟
- ①利?事務(wù)數(shù)據(jù)庫(kù)中的數(shù)據(jù)構(gòu)造FP-tree键菱；
- ②從FP-tree中挖掘頻繁模式
步驟1： 構(gòu)造 FP-tree樹
具體過程：
1.? 掃描數(shù)據(jù)庫(kù)?次， 得到頻繁1-項(xiàng)集
2.? 把項(xiàng)按?持度遞減排序
3.? 再?次掃描數(shù)據(jù)庫(kù)今布， 建?FP-tree
FP-tree 結(jié)構(gòu)的好處
- 完備
不會(huì)打破交易中的任何模式
包含了頻繁模式挖掘所需的全部信息 - 緊密
去除不相關(guān)信息—不包含?頻繁項(xiàng)
?持度降序排列: ?持度?的項(xiàng)在FP-tree中共享的機(jī)會(huì)也?
決不會(huì)?原數(shù)據(jù)庫(kù)?（如果不計(jì)算樹節(jié)點(diǎn)的額外開銷)
步驟2： 頻繁模式的挖掘
- 具體過程:
根據(jù)事務(wù)數(shù)據(jù)庫(kù)D 和最??持度min_sup经备， 調(diào)?建樹過程建?FP-tree;
if (FP-tree 為簡(jiǎn)單路徑)
將路徑上?持度計(jì)數(shù)?于等于min_sup 的節(jié)點(diǎn)任意組合， 得到所需
的頻繁模式
else
初始化最?頻繁模式集合為空
按照?持頻率升序部默， 以每個(gè)1 － 頻繁項(xiàng)為后綴侵蒙， 調(diào)?挖掘算法挖掘
最?頻繁模式集
根據(jù)最?頻繁模式集合中最?頻繁模式， 輸出全部的頻繁模式
FP-tree算法的一個(gè)例子
事物數(shù)據(jù)庫(kù):
| 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
統(tǒng)計(jì)了每一項(xiàng)頻數(shù)傅蹂，輸出
defaultdict(int, {'I1': 6, 'I2': 7, 'I3': 6, 'I4': 2, 'I5': 2})
按照頻數(shù)對(duì)Items由大到小排序
df_fp_data['Items'] = df_fp_data['Items'].map(lambda items:
','.join(sorted(items.split(','), key=lambda item:-dic_items[item])))
創(chuàng)建節(jié)點(diǎn)類與樹類
# 節(jié)點(diǎn)
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):
# 建立根節(jié)點(diǎn)
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)
將節(jié)點(diǎn)加入樹中
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
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
