1. 何時(shí)使用規(guī)則模型
?機(jī)器學(xué)習(xí)時(shí)常遇到一個(gè)問(wèn)題：當(dāng)數(shù)據(jù)并不完全可分時(shí)霜运，分類器得分不高宛琅。真實(shí)世界中的數(shù)據(jù)經(jīng)常是這樣：各種無(wú)意義數(shù)據(jù)和少量有意義數(shù)據(jù)混在一起刻蟹，無(wú)意義數(shù)據(jù)又沒什么規(guī)律，無(wú)法統(tǒng)一去除嘿辟。比如說(shuō)舆瘪，對(duì)股票外匯市場(chǎng)受各種因素影響，預(yù)測(cè)次日漲跌一般各算法效果都不好红伦。雖然找不到通用的規(guī)則英古，卻能在數(shù)據(jù)中探索到一些模式，比如十字星昙读，孕線召调，三只烏鴉等組合還是具有一定的預(yù)測(cè)性。
?之前使用決策樹時(shí)蛮浑，就遇到過(guò)這種情況唠叛，雖然整體得分不高，但某些葉節(jié)點(diǎn)上純度高（全是正例或全是反例）并且實(shí)例多沮稚，可以把該分枝拿出來(lái)當(dāng)規(guī)則使用矢赁。雖然不能用它預(yù)測(cè)任意數(shù)據(jù)峰弹，但可以作為一個(gè)過(guò)濾器使用。
2. 規(guī)則模型是什么
?規(guī)則模型和決策樹同屬邏輯模型，不同的是決策樹對(duì)正例反例同樣重視耘眨，而規(guī)則只重視正例/反例其中一項(xiàng)。因此決策樹呈現(xiàn)的是互斥關(guān)系翼闽，而規(guī)則模型允許重疊倦零，結(jié)果也相對(duì)零散的規(guī)則列表。規(guī)則更像是在大量數(shù)據(jù)中挑選有意義的數(shù)據(jù)饶唤。
?如果說(shuō)樹是精確模型徐伐，規(guī)則模型則是啟發(fā)式策略（雖然經(jīng)過(guò)修改也能覆蓋所有實(shí)例，但一般不這么用）募狂。它可以找到數(shù)據(jù)集中的一個(gè)子集办素，相對(duì)于全部數(shù)據(jù)，該子集有明顯的意義祸穷。
規(guī)則模型多用于處理離散數(shù)據(jù)性穿，如文本中查找頻繁單詞，提取摘要雷滚，分析購(gòu)物信息等等需曾。
3. 具體實(shí)現(xiàn)
?在實(shí)現(xiàn)上，我們可以把規(guī)則當(dāng)成樹的變種，稍加修改呆万，便是規(guī)則模型商源。具體有兩種做法：一種是找規(guī)則，使其覆蓋同質(zhì)（全真或全假）的樣本集（和樹類似）谋减；另一種是選定類別牡彻，找覆蓋該類別實(shí)例樣本的規(guī)則集。
4. 關(guān)聯(lián)規(guī)則
?規(guī)則是一個(gè)用途很多的算法出爹，關(guān)于規(guī)則模型的文章不多庄吼，有的書把它歸入邏輯推理中，而非機(jī)器學(xué)習(xí)严就。我們最常見的是關(guān)聯(lián)規(guī)則总寻，比如用Apriori實(shí)現(xiàn)的頻繁項(xiàng)集挖掘算法。
?最經(jīng)典的是購(gòu)物籃分析中啤酒梢为、尿布的故事渐行，即通過(guò)對(duì)購(gòu)物清單的分析，發(fā)現(xiàn)看似毫無(wú)關(guān)系的啤酒和尿布經(jīng)常在用戶的購(gòu)物籃中一起出現(xiàn)铸董，通過(guò)挖掘出啤酒殊轴、尿布這個(gè)頻繁項(xiàng)集，則當(dāng)一個(gè)用戶買了啤酒的時(shí)候可以為他推薦尿布袒炉，從而達(dá)到組合營(yíng)銷的目的旁理。
?下面將介紹兩種基于關(guān)聯(lián)規(guī)則的無(wú)監(jiān)督學(xué)習(xí)算算法Apriori和FP-growth
5. Apriori
(1) 介紹
?Apriori這個(gè)單詞在拉丁語(yǔ)中的意思是“來(lái)自以前”，也可拆開為a priori我磁，即一次先驗(yàn)孽文。算法的目標(biāo)是找到出現(xiàn)頻率高的簡(jiǎn)單規(guī)則。
(2) 原理
?如果某個(gè)項(xiàng)是頻繁的夺艰，那么它的所有子集也是頻繁的芋哭。反之，如果一個(gè)項(xiàng)集是非頻繁的郁副，那么它的超集也是非頻的减牺。比如啤酒和尿布常常同時(shí)出現(xiàn)，則啤酒單獨(dú)出現(xiàn)的機(jī)率也很高存谎；如果這個(gè)地區(qū)的人極少喝啤酒拔疚，啤酒和尿布的組合也不會(huì)常常出現(xiàn)。
(3) 算法
?生成單個(gè)物品列表既荚，去掉頻率低于支持度的稚失，再組合兩個(gè)物品，去掉低于支持度的恰聘，以此類推句各，求出頻繁項(xiàng)集吸占，在頻繁項(xiàng)集中抽取關(guān)聯(lián)規(guī)則。
?算法的輸入是大量可能相關(guān)的數(shù)據(jù)組合凿宾，支持度矾屯，置信度。輸出是頻率項(xiàng)集或關(guān)聯(lián)規(guī)則初厚。
(4) 優(yōu)缺點(diǎn)
?Apriori的優(yōu)點(diǎn)是易于理解问拘，缺點(diǎn)是算得慢，如果共有N件物品惧所，計(jì)算量是2^N-1。在屬性過(guò)多绪杏，或?qū)傩缘臓顟B(tài)過(guò)多時(shí)都會(huì)導(dǎo)致大量計(jì)算下愈。
(5) 相關(guān)概念
?支持度：數(shù)據(jù)集中包含該項(xiàng)集的記錄所占的比例
?置信度：同時(shí)支持度/部分支持度（純度）
?頻繁項(xiàng)集：經(jīng)常同時(shí)出現(xiàn)的物品的集合
?關(guān)聯(lián)規(guī)則：兩種物品間可能存在很強(qiáng)的關(guān)系，比如A,B同時(shí)出現(xiàn)蕾久，如果A->B势似，則A稱為前件，B稱為后件僧著。如果A發(fā)生概率50%履因，而AB概率25%，則A不一定引發(fā)B盹愚，但如果AB發(fā)生概率為49%栅迄，則說(shuō)明A->B。
(6) 例程
i. 功能
從多次購(gòu)物數(shù)據(jù)中取頻率項(xiàng)集皆怕，并顯示各組合的支持度
ii. 代碼
# -*- coding: utf-8 -*-
from numpy import *
def loadDataSet():
return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
# 建立所有單項(xiàng)的集合毅舆，如購(gòu)物中的物品集合
def createC1(dataSet):
C1 = []
for transaction in dataSet:
for item in transaction:
if not [item] in C1:
C1.append([item])
C1.sort()
return list(map(frozenset, C1))
# D是數(shù)據(jù)，Ck是各個(gè)組的集合愈腾，返回滿足支持率的組
def scanD(D, Ck, minSupport):
ssCnt = {} # 字典
for tid in D: # 每條記錄
for can in Ck: # 每個(gè)組
if can.issubset(tid):
if not can in ssCnt: # 把組放入字典
ssCnt[can]=1
else:
ssCnt[can] += 1
numItems = float(len(D))
retList = []
supportData = {}
for key in ssCnt:
support = ssCnt[key]/numItems
if support >= minSupport:
retList.insert(0,key) # 把字典中的該項(xiàng)加入list
supportData[key] = support
return retList, supportData
# 建立各個(gè)層次的組, 只建立不判斷, k是組里元素的個(gè)數(shù)
def aprioriGen(Lk, k):
retList = []
lenLk = len(Lk)
for i in range(lenLk):
for j in range(i+1, lenLk):
L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2]
L1.sort(); L2.sort()
if L1==L2: #if first k-2 elements are equal
retList.append(Lk[i] | Lk[j]) #set union
return retList
def apriori(dataSet, minSupport = 0.5):
C1 = createC1(dataSet)
D = list(map(set, dataSet))
L1, supportData = scanD(D, C1, 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) # 將本次結(jié)果加入整體
k += 1
return L, supportData
if __name__ == '__main__':
dataSet = loadDataSet() # 數(shù)據(jù)是二維數(shù)組憋活，每項(xiàng)可看作如一次購(gòu)物
L,suppData = apriori(dataSet, minSupport = 0.7)
print(L)
print(suppData)
iii. 結(jié)果
[[frozenset([3]), frozenset([2]), frozenset([5])], [frozenset([2, 5])], []]
{frozenset([5]): 0.75, frozenset([3]): 0.75, frozenset([3, 5]): 0.5, frozenset([4]): 0.25, frozenset([2, 3]): 0.5, frozenset([2, 5]): 0.75, frozenset([1]): 0.5, frozenset([2]): 0.75}
6. FP-growth
(1) 介紹
?FP是Frequent Pattern的縮寫，代表頻繁模式虱黄。FP-growth比Apriori快悦即，性能提高在兩個(gè)數(shù)量級(jí)以上，在大數(shù)據(jù)集上表現(xiàn)更佳橱乱。
?和Apriori多次掃描原始數(shù)據(jù)相比辜梳，F(xiàn)P-Growth算法則只需掃描原始數(shù)據(jù)兩遍，把數(shù)據(jù)存儲(chǔ)在FP-Tree結(jié)構(gòu)中泳叠。
(2) FP-Tree
?與搜索樹不同的是冗美，一個(gè)元素項(xiàng)可以在FP樹中出現(xiàn)多次，F(xiàn)P樹會(huì)存儲(chǔ)項(xiàng)集的出現(xiàn)頻率析二。每個(gè)項(xiàng)集會(huì)以路徑的方式存儲(chǔ)在樹中粉洼，存在相似元素的集合會(huì)共享樹的一部分节预，只當(dāng)集合之間完全不同時(shí)，樹才會(huì)分叉属韧。
?除了樹安拟，還有個(gè)索引表（Header table），把所有含相同元素的組織起來(lái)(link list)宵喂，以便查找糠赦。
(3) 算法
先構(gòu)建FP樹，然后從FP樹中挖掘頻繁項(xiàng)集
i. 收集數(shù)據(jù)
數(shù)據(jù)是五次購(gòu)物的清單（記錄）锅棕，a,b,c,d…分別代表物品（item）
ii. 去除非頻繁項(xiàng)l, i, o等拙泽，并排序
iii. 將記錄依次加入樹，并建立索引表（左側(cè)框）裸燎，粉色為添加第一次購(gòu)物數(shù)據(jù)顾瞻。
iv. 從下往上構(gòu)造每個(gè)item的條件模式基CPB（conditional pattern base）
?順著header table中item的鏈表，找出所有包含該item的前綴路徑德绿，這些前綴路徑就是該item的條件模式基（CPB）
?所有這些CPB的頻繁度（計(jì)數(shù)）為該路徑上item的頻繁度（計(jì)數(shù)）
?如包含p的其中一條路徑是fcamp荷荤，該路徑中p的頻繁度為2，則該CPB fcam的頻繁度為2
v. 構(gòu)造條件FP-tree（conditional FP-tree）
?累加每個(gè)CPB上的item的頻繁度（計(jì)數(shù)）移稳，過(guò)濾低于閾值的item蕴纳，構(gòu)建FP-tree
?如m的CPB{<fca:2>, <fcab:1>}，f:3, c:3, a:3, b:1, 閾值假設(shè)為3个粱，則過(guò)濾掉b古毛。
?遞歸的挖掘每個(gè)條件FP-tree，累加后綴頻繁項(xiàng)集都许，直到找到FP-tree為空或者FP-tree只有一條路徑喇潘。
