詳解python實現FP-TREE進行關聯規則挖掘(帶有FP樹顯示功能)附源代碼下載(3)

上一節簡單講了下FP樹的生成,在這一節我將描述FP樹的挖掘過程.

首先我們回顧一下要挖掘的特征項及樣本空間:

items=('chips','eggs','bread','milk','beer','popcorn','butter') sample=[['milk','eggs','bread','chips'],['eggs','popcorn','chips','beer'],['eggs','bread','chips'],['milk','eggs','bread','popcorn','chips','beer'],['milk','bread','beer'],['eggs','bread','beer'],['milk','bread','chips'],['milk','eggs','bread','butter','chips'],['milk','eggs','butter','chips'] ] 由于要尋找的關聯規則的最小支持度為3,所以butter和popcorn兩個特征項就可以首先被忽略掉了，因為它們的支持度都只有2。

根據挖掘的規則，挖掘將從支持度最接近3的特征項開始，即本例中的beer，它的支持度為4.

從圖中可以看到beer的節點數為4,于是它有4個條件模式基(CPB):

{eggs,bread,chips:1}

{eggs,bread:1}

{eggs,chips:1}

{bread,milk:1}

生成的FP子樹如下圖:

(注意:在源代碼中,我為milk的FP子樹單獨生成了一個對象,其實在實際使用中FP樹會占用很大的內從空間,所以FP子樹一般會利用FP樹而不是重新生成,一個可行的辦法是將FP樹的節點支持度數表示為一個字典,例如{root:7,milk:3}表示該節點在FP樹中支持度為7,而在特征項milk的FP子樹中支持度為3)

得到FP子樹后要進行兩步操作：

第一步：將該子樹中所有支持度大于3的特征項與milk作并集，得到滿足條件的二項集：

（eggs，milk ）

（bread，milk ) ?

它們的支持度都為3。

第二步：判斷這顆子樹是否有必要進一步挖掘，這是難點，也是優化算法的一個方向。

判斷的結果有三種：

1. 該樹沒有任何一個特征項的支持度 >= 3，那么等同于空樹，就沒有必要挖掘了。

2. 該樹是一棵單路徑的樹。

3. 該樹是一棵多路徑的樹。

情況2和情況3是怎么回事，又該如何處理，請看下節

轉載請注明出處:http://blog.csdn.net/rav009/article/details/8976421

轉載于:https://www.cnblogs.com/rav009/archive/2013/05/26/5131158.html

總結

以上是生活随笔為你收集整理的详解python实现FP-TREE进行关联规则挖掘(带有FP树显示功能)附源代码下载(3)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。