11.2節曾經提到,可以利用關聯分析發現許多有趣的內容。人們最常尋找的兩個目標是頻繁項集與關聯規則。上一節介紹如何使用Apriori算法來發現頻繁項集,現在需要解決的問題是如何找出關聯規則。
要找到關聯規則,我們首先從一個頻繁項集開始。我們知道集合中的元素是不重複的,但我們想知道基於這些元素能否獲得其他內容。某個元素或者某個元素集合可能會推導出另一個元素。從雜貨店的例子可以得到,如果有一個頻繁項集{豆奶, 萵苣},那麼就可能有一條關聯規則「豆奶 ➞ 萵苣」。這意味著如果有人購買了豆奶,那麼在統計上他會購買萵苣的概率較大。但是,這一條反過來並不總是成立。也就是說,即使「豆奶 ➞ 萵苣」統計上顯著,那麼「萵苣 ➞ 豆奶」也不一定成立。(從邏輯研究上來講,箭頭左邊的集合稱作前件,箭頭右邊的集合稱為後件。)
11.3節給出了頻繁項集的量化定義,即它滿足最小支持度要求。對於關聯規則,我們也有類似的量化方法,這種量化指標稱為可信度。一條規則P ➞ H的可信度定義為support(P | H)/support(P)
。記住,在Python中,操作符|
表示集合的並操作,而數學上集合併的符號是U
。P | H
是指所有出現在集合P
或者集合H
中的元素。前面一節已經計算了所有頻繁項集支持度。現在想獲得可信度,所需要做的只是取出那些支持度值做一次除法運算。
從一個頻繁項集中可以產生多少條關聯規則?圖11-4的網格圖給出的是從項集{0,1,2,3}產生的所有關聯規則。為找到感興趣的規則,我們先生成一個可能的規則列表,然後測試每條規則的可信度。如果可信度不滿足最小要求,則去掉該規則。
圖11-4 對於頻繁項集{0,1,2,3}的關聯規則網格示意圖。陰影區域給出的是低可信度的規則。如果發現0,1,2→3是一條低可信度規則,那麼所有其他以3作為後件的規則可信度也會較低
類似於上一節的頻繁項集生成,我們可以為每個頻繁項集產生許多關聯規則。如果能夠減少規則數目來確保問題的可解性,那麼計算起來就會好很多。可以觀察到,如果某條規則並不滿足最小可信度要求,那麼該規則的所有子集也不會滿足最小可信度要求。以圖11-4為例,假設規則0,1,2 ➞ 3並不滿足最小可信度要求,那麼就知道任何左部為{0,1,2}子集的規則也不會滿足最小可信度要求。在圖11-4中這些規則上都加了陰影來表示。
可以利用關聯規則的上述性質屬性來減少需要測試的規則數目。類似於程序清單11-2中的Apriori算法,可以首先從一個頻繁項集開始,接著創建一個規則列表,其中規則右部只包含一個元素,然後對這些規則進行測試。接下來合併所有剩餘規則來創建一個新的規則列表,其中規則右部包含兩個元素。這種方法也被稱作分級法。下面看一下這種方法的實際效果,打開apriori.py
文件,加入下面的代碼。
程序清單11-3 關聯規則生成函數
def generateRules(L, supportData, minConf=0.7):
bigRuleList =
#❶ 只獲取有兩個或更多元素的集合
for i in range(1, len(L)):
for freqSet in L[i]:
H1 = [frozenset([item]) for item in freqSet]
if (i > 1):
rulesFromConseq(freqSet, H1, supportData, bigRuleList,minConf)
else:
calcConf(freqSet, H1, supportData, bigRuleList, minConf)
return bigRuleList
def calcConf(freqSet, H, supportData, brl, minConf=0.7):
prunedH =
for conseq in H:
conf = supportData[freqSet]/supportData[freqSet-conseq]
if conf >= minConf:
print freqSet-conseq,\'-->\',conseq,\'conf:\',conf
brl.append((freqSet-conseq, conseq, conf))
prunedH.append(conseq)
return prunedH
def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
m = len(H[0])
#❷ 嘗試進一步合併
if (len(freqSet) > (m + 1)):
#❸ 創建Hm+1條新候選規則
Hmp1 = aprioriGen(H, m + 1)
Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
if (len(Hmp1) > 1):
rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
上述程序中包含三個函數。第一個函數generateRules
是主函數,它調用其他兩個函數。其他兩個函數是rulesFromConseq
和calcConf
,分別用於生成候選規則集合以及對規則進行評估。
函數generateRules
有3個參數:頻繁項集列表、包含那些頻繁項集支持數據的字典、最小可信度閾值。函數最後要生成一個包含可信度的規則列表,後面可以基於可信度對它們進行排序。這些規則存放在bigRuleList
中。如果事先沒有給定最小可信度的閾值,那麼默認值設為0.7。generateRules
的另兩個輸入參數正好是程序清單11-2中函數apriori
的輸出結果。該函數遍歷L
中的每一個頻繁項集並對每個頻繁項集創建只包含單個元素集合的列表H1
。因為無法從單元素項集中構建關聯規則,所以要從包含兩個或者更多元素的項集開始規則構建過程❶。如果從集合{0,1,2}開始,那麼H1
應該是[{0},{1},{2}]。如果頻繁項集的元素數目超過2,那麼會考慮對它做進一步的合併。具體合併可以通過函數rulesFromConseq
來完成,後面會詳細討論合併過程。如果項集中只有兩個元素,那麼使用函數calcConf
來計算可信度值。
我們的目標是計算規則的可信度以及找到滿足最小可信度要求的規則。所有這些可以使用函數calcConf
來完成,而程序清單11-3中的其餘代碼都用來準備規則。函數會返回一個滿足最小可信度要求的規則列表,為了保存這些規則,需要創建一個空列表prunedH
。接下來,遍歷H
中的所有項集並計算它們的可信度值。可信度計算時使用supportData
中的支持度數據。通過導入這些支持度數據,可以節省大量計算時間。如果某條規則滿足最小可信度值,那麼將這些規則輸出到屏幕顯示。通過檢查的規則也會被返回,並被用在下一個函數rulesFromConseq
中。同時也需要對列表brl
進行填充,而brl
是前面通過檢查的bigRuleList
。
為從最初的項集中生成更多的關聯規則,可以使用rulesFromConseq
函數。該函數有2個參數:一個是頻繁項集,另一個是可以出現在規則右部的元素列表H
。函數先計算H
中的頻繁集大小m
❷。接下來查看該頻繁項集是否大到可以移除大小為m的子集。如果可以的話,則將其移除。可以使用程序清單11-2中的函數aprioriGen
來生成H
中元素的無重複組合❸。該結果會存儲在Hmp1
中,這也是下一次迭代的H
列表。Hmp1
包含所有可能的規則。可以利用calcConf
來測試它們的可信度以確定規則是否滿足要求。如果不止一條規則滿足要求,那麼使用Hmp1
迭代調用函數rulesFromConseq
來判斷是否可以進一步組合這些規則。
下面看一下實際的運行效果,保存apriori.py
文件,在Python提示符下輸入:
>>> reload(apriori)
<module \'apriori\' from \'apriori.py\'>
現在,讓我們生成一個最小支持度是0.5的頻繁項集的集合:
>>> L,suppData=apriori.apriori(dataSet,minSupport=0.5)
>>> rules=apriori.generateRules(L,suppData, minConf=0.7)
>>> rules
[(frozenset([1]), frozenset([3]), 1.0), (frozenset([5]), frozenset([2]),1.0), (frozenset([2]), frozenset([5]), 1.0)]
frozenset([1]) --> frozenset([3]) conf: 1.0
frozenset([5]) --> frozenset([2]) conf: 1.0
frozenset([2]) --> frozenset([5]) conf: 1.0
結果中給出三條規則:{1} ➞ {3}、{5} ➞ {2}及{2} ➞ {5}。可以看到,後兩條包含2和5的規則可以互換前件和後件,但是前一條包含1和3 的規則不行。下面降低可信度閾值之後看一下結果:
>>> rules=apriori.generateRules(L,suppData, minConf=0.5) >>> rules [(frozenset([3]), frozenset([1]), 0.6666666666666666), (frozenset([1]),frozenset([3]), 1.0), (frozenset([5]), frozenset([2]), 1.0),(frozenset([2]), frozenset([5]), 1.0), (frozenset([3]), frozenset([2]),0.6666666666666666), (frozenset([2]), frozenset([3]), 0.6666666666666666),(frozenset([5]), frozenset([3]), 0.6666666666666666), (frozenset([3]),frozenset([5]), 0.6666666666666666), (frozenset([5]), frozenset([2, 3]), 0.6666666666666666), (frozenset([3]), frozenset([2, 5]),0.6666666666666666), (frozenset([2]), frozenset([3, 5]),0.6666666666666666)] frozenset([3]) --> frozenset([1]) conf: 0.666666666667 frozenset([1]) --> frozenset([3]) conf: 1.0 frozenset([5]) --> frozenset([2]) conf: 1.0 frozenset([2]) --> frozenset([5]) conf: 1.0 frozenset([3]) --> frozenset([2]) conf: 0.666666666667 frozenset([2]) --> frozenset([3]) conf: 0.666666666667 frozenset([5]) --> frozenset([3]) conf: 0.666666666667 frozenset([3]) --> frozenset([5]) conf: 0.666666666667 frozenset([5]) --> frozenset([2, 3]) conf: 0.666666666667 frozenset([3]) --> frozenset([2, 5]) conf: 0.666666666667 frozenset([2]) --> frozenset([3, 5]) conf: 0.666666666667
一旦降低可信度閾值,就可以獲得更多的規則。到現在為止,我們看到上述程序能夠在一個小數據集上正常運行,接下來將在一個更大的真實數據集上測試一下效果。具體地,下一節將檢查其在美國國會投票記錄上的處理效果。