[ ML In Action ] Unsupervised learning : Efficiently finding frequent itemsets with FP-growth

Preface: 
在上一章 Association analysis with the Apriori algorithm 我們使用 Apriori 演算法從 transaction list 找到 data 間的關係, 常見的應用是便利商店可以用來判斷當你買了商品 A 後接著會買其他商品的可能組合. 而在這個過程中我們第一步要找的是所謂的 frequent item set, 並透過設定 minimum support 來 filter 不常見的 item(s). 而在 Apriori 是使用窮舉法找出所有可能的 data set 組合, 雖然有利用 pruning 的技巧, 但是效率仍然不是很理想, 在處理大量資料時可能會遇到處理速度的瓶頸. 這邊要介紹另一種演算法, 讓你能更快速的從 transaction set 中找出 frequent item set. 該演算法需要建立一種特殊的資料結構稱為 FP-Tree (FP means Frequent Pattern) 而該演算法為 FP-growth algorithm. 

FP-trees: an efficient way to encode a dataset: 
在使用 FP-growth algorithm 前必須先建立 FP-Tree, 接著使用 FP-Tree 來 mining 出 frequent item set. 該演算法有以下特性: 

Pros: Usually faster than Apriori.
Cons: Difficult to implement; certain datasets degrade the performance.
Works with: Nominal values.

首先我們來看一個簡單的範例, 來了解 FP-Tree 是如何建立. 假設你有如下的 transaction list: 
 

在使用 transaction list 前, 我們要做一些前置處理. 就如在 Apriori 中處理 frequent item set 一樣, 我們會根據 minimum support 移除不常出現的 item (這邊 minimum support=3); 接著將 transaction 紀錄依據出現頻率從高到低進行 sorting. 處理完結果如下: 
 

接著我們就要用處理過後的 transaction list 來建立 FP-Tree 時. 在 FP-Tree 在最上層的 root 是空集合的符號. 底下是前兩筆 transaction 建立 FP-Tree 的過程: 
 

在 item 旁邊的數字說明該 item 出現的頻率 (z:1 說明 'z' 目前頻率為 1), 可能會隨著加入越來越多的 transaction 而增加. 另外為了迅速找到某個 item 在 FP-Tree 中的位置, 我們會建立一個 Header Table (鍵為 item, 值為該 item 在 FP-Tree 中的位置), 而每個 Node 都會有一個 link 連到同樣 item 的下一個 Node 而形成類似 linked list 的結構, 完整的 FP-Tree 建立結果長相如下: 
 
Figure 12.2 FP-tree with header table. The header table serves as a starting point to find similar items. 

下一個部份我們要來看如何透過代碼來建立 FP-Tree 並利用 FP-Tree 來 mining frequent items. 在開始 coding 前, 我們定義下面的類別作為 FP-Tree 的 node 以記載相關資料: 

view plaincopy to clipboardprint?

1. class treeNode:  
2.     def __init__(self, nameValue, numOccur, parentNode):  
3.         self.name = nameValue       # item name  
4.         self.count = numOccur       # frequency   
5.         self.nodeLink = None        # pointer to next node with same item name  
6.         self.parent = parentNode    # needs to be updated  
7.         self.children = {}          # next node according to sorting transaction set  
8.       
9.     def inc(self, numOccur):  
10.         self.count += numOccur  
11.           
12.     def disp(self, ind=1):  
13.         print '  '*ind, self.name, ' ', self.count  
14.         for child in self.children.values():  
15.             child.disp(ind+1)  

底下我們要先來看看從 transaction set 建立 FP-Tree 的部分代碼: 
- Listing 12.2 FP-tree creation code 

view plaincopy to clipboardprint?

1. """Create tree based on given .  
2.     Args:  
3.         dataSet: Input transaction set.  
4.         minSup: Used to filter out infrequent item(s).  
5.           
6.     Returns:  
7.         retTree: FP-Tree(treeNode) or None if no frequent item  
8.         headerTable: Header table of FP-Tree or None if no frequent item  
9.                      headerTable[item] = (frequency,)  
10.           
11.     Raises:  
12.         None  
13. """  
14. def createTree(dataSet, minSup=1): #create FP-tree from dataset but don't mine  
15.     headerTable = {}  
16.     #go over dataSet twice  
17.     for trans in dataSet:#first pass counts frequency of occurance  
18.         for item in trans:  
19.             headerTable[item] = headerTable.get(item, 0) + dataSet[trans]  
20.     for k in headerTable.keys():  #remove items not meeting minSup  
21.         if headerTable[k] < minSup:   
22.             del(headerTable[k])  
23.     freqItemSet = set(headerTable.keys())  
24.     #print 'freqItemSet: ',freqItemSet  
25.     if len(freqItemSet) == 0: return None, None  #if no items meet min support -->get out  
26.     for k in headerTable:  
27.         headerTable[k] = [headerTable[k], None] #reformat headerTable to use Node link   
28.     #print 'headerTable: ',headerTable  
29.     retTree = treeNode('Null Set', 1, None) #create tree  
30.     for tranSet, count in dataSet.items():  #go through dataset 2nd time  
31.         localD = {}  
32.         for item in tranSet:  #put transaction items in order  
33.             if item in freqItemSet:  
34.                 localD[item] = headerTable[item][0]  
35.         if len(localD) > 0:  
36.             orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)]  
37.             updateTree(orderedItems, retTree, headerTable, count)#populate tree with ordered freq itemset  
38.     return retTree, headerTable #return tree and header table  
39.   
40. """ Recursively update the FP-Tree  
41.     Args:  
42.         items: Ordered frequent items  
43.         inTree: FP-Tree node  
44.         headerTable: Header table of FP-Tree  
45.         count: Count of exist same transaction of input items.  
46.           
47.     Returns:  
48.         None  
49.       
50.     Raises:  
51.         None  
52. """  
53. def updateTree(items, inTree, headerTable, count):  
54.     if items[0] in inTree.children:#check if orderedItems[0] in retTree.children  
55.         inTree.children[items[0]].inc(count) #incrament count  
56.     else:   #add items[0] to inTree.children  
57.         inTree.children[items[0]] = treeNode(items[0], count, inTree)  
58.         if headerTable[items[0]][1] == None: #update header table   
59.             headerTable[items[0]][1] = inTree.children[items[0]]  
60.         else:  
61.             updateHeader(headerTable[items[0]][1], inTree.children[items[0]])  
62.     if len(items) > 1:#call updateTree() with remaining ordered items  
63.         updateTree(items[1::], inTree.children[items[0]], headerTable, count)  
64.           
65. def updateHeader(nodeToTest, targetNode):   #this version does not use recursion  
66.     while (nodeToTest.nodeLink != None):    #Do not use recursion to traverse a linked list!  
67.         nodeToTest = nodeToTest.nodeLink  
68.     nodeToTest.nodeLink = targetNode  

底下是產生測試 transaction set 的代碼: 
- Listing 12.3 Simple dataset and data wrapper 

view plaincopy to clipboardprint?

1. """Create testing transaction set  
2.     Args:  
3.         None  
4.           
5.     Returns:  
6.         simpDat: Transaction set  
7.           
8.     Raises:  
9.         None  
10. """  
11. def loadSimpDat():  
12.     simpDat = [['r', 'z', 'h', 'j', 'p'],  
13.                ['z', 'y', 'x', 'w', 'v', 'u', 't', 's'],  
14.                ['z'],  
15.                ['r', 'x', 'n', 'o', 's'],  
16.                ['y', 'r', 'x', 'z', 'q', 't', 'p'],  
17.                ['y', 'z', 'x', 'e', 'q', 's', 't', 'm']]  
18.     return simpDat  
19.   
20. """Build up directory to contains (transaction->frequency)  
21.     Args:  
22.         dataSet: Transaction set created by API:loadSimpDat()  
23.           
24.     Return:  
25.         retDict:  
26.           
27.     Raise:  
28.         None  
29. """  
30. def createInitSet(dataSet):  
31.     retDict = {}  
32.     for trans in dataSet:  
33.         retDict[frozenset(trans)] = 1  
34.     return retDict  

接著假設代碼撰寫在 "fpGrowth.py", 我們可以如下測試 FP-Tree 的建立過程: 
 

Mining frequent items from an FP-tree: 
當你建立 FP-Tree, 接下來要 mining 出 frequent items 就相當 straight forward, 以下是後續的三個動作: 

1. Get conditional pattern bases from the FP-tree.
2. From the conditional pattern base, construct a conditional FP-tree.
3. Recursively repeat steps 1 and 2 on until the tree contains a single item.

那什麼是 "conditional pattern bases"? 你可以想像成剛剛產生的 frequent item set 中每個 item 從剛剛建立的 FP-Tree 可以走出所有可能的 path, 而該 path 的最後一個 item 為 target item. 舉例來說, 當 target item="z" 時, 從 FP-Tree 能走到 "z" 的所有走法只有 {Φ->z}5 (5 指的是頻率): 
 

如果 target item="r", 則走法有 {Φ->z->r}1 , {Φ->z->x->y->r}1, {Φ->x->s->r}1: 
 

如果拿掉 path 的頭尾, 底下整理出所有 frequent item set 的 "conditional pattern bases": 
 

而地下是找出 "conditional pattern bases" 的代碼, 而在找的過程中代碼利用 Header table 指向每一個 frequent item, 並利用其 nodeLink 屬性指向下一個相同 item 的 Node; 並利用 Node 上面的的 parentNode 屬性往上走直到 root (parentNode=None): 
- Listing 12.4 A function to find all paths ending with a given item 

view plaincopy to clipboardprint?

1. """Ascends from the left node to root and store the path to .  
2.     Args:  
3.         leafNode: Node of PF-Tree  
4.         prefixPath: list to store the traversal path  
5.           
6.     Returns:  
7.         None  
8.           
9.     Raises:  
10.         None  
11. """          
12. def ascendTree(leafNode, prefixPath): #ascends from leaf node to root  
13.     if leafNode.parent != None:  
14.         prefixPath.append(leafNode.name)  
15.         ascendTree(leafNode.parent, prefixPath)  
16.           
17. """Find prefix path according to given FP-Tree node as   
18.     Args:  
19.         basePat: ?  
20.         treeNode: Target FP-Tree node.  
21.           
22.     Return:  
23.         condPats: The directory to hold {conditional path->count}  
24.           
25.     Raises:  
26.         None  
27. """  
28. def findPrefixPath(basePat, treeNode): #treeNode comes from header table  
29.     condPats = {}  
30.     while treeNode != None:  
31.         prefixPath = []  
32.         ascendTree(treeNode, prefixPath)  
33.         if len(prefixPath) > 1:   
34.             condPats[frozenset(prefixPath[1:])] = treeNode.count  
35.         treeNode = treeNode.nodeLink  
36.     return condPats  

接著底下是上面代碼的使用範例: 
 

接下來利用這些找到的 "conditional pattern bases" 當作 transaction 在建立 "conditional FP-trees". 以 target item='t' 為範例, 底下是建立的過程: 
 
(item 's' 與 'r' 沒有出現在 "conditional FP-trees" 是因為它們不滿足 minimum support=3 的限制) 

如此第三步只是重複 一, 二步. 因此我們只要利用 recursive 的方法便可以完成, 而 stop condition 為當 "conditional FP-trees" 為 None 時並終止 recursive. 底下為 mining 過程代碼: 
- Listing 12.5 The mineTree function recursively finds frequent itemsets. 

view plaincopy to clipboardprint?

1. """Recursively finds frequent itemsets.  
2.     Args:  
3.         inTree: FP-Tree  
4.         headerTable: Header table of FP-Tree  
5.         preFix: Prefix paths  
6.         freqItemList: Frequent item list (Final result)  
7.           
8.     Returns:  
9.         None  
10.           
11.     Raises:  
12.         None  
13. """  
14. def mineTree(inTree, headerTable, minSup, preFix, freqItemList):  
15.     bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1])]#(sort header table)  
16.     for basePat in bigL:  #start from bottom of header table  
17.         newFreqSet = preFix.copy()  
18.         newFreqSet.add(basePat)  
19.         #print 'finalFrequent Item: ',newFreqSet    #append to set  
20.         freqItemList.append(newFreqSet)  
21.         condPattBases = findPrefixPath(basePat, headerTable[basePat][1])  
22.         #print 'condPattBases :',basePat, condPattBases  
23.         #2. construct cond FP-tree from cond. pattern base  
24.         myCondTree, myHead = createTree(condPattBases, minSup)  
25.         #print 'head from conditional tree: ', myHead  
26.         if myHead != None: #3. mine cond. FP-tree  
27.             #print 'conditional tree for: ',newFreqSet  
28.             #myCondTree.disp(1)              
29.             mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)  

最後的使用範例也相當簡單, 而上面完整代碼可到 這裡下載: 
 

Supplement: 
* [ Python 範例代碼 ] Sorting directory into item key list according to the item value