關聯規則--用來發現資料中屬性具有高度關聯的樣式(fpgrowth algorithm)

這篇不是要講很艱深的東西，簡單解釋一下啥事關聯規則。

基本上上面這張購物欄交易資料，透過底下的 apriori 演算法程式，可以找到啤酒和尿布具有很大的相關性，他的支持度高達 50 。故事請看這裡。這是個範例，只是說明關聯規則程式可發覺這樣形式的規則關聯樣式。

在網路上有個人 Christian Borgelt 寫了很多程式，其中有 apriori 和 fpgrowth ，基本上這兩個程式做的工作差不多，但是 fpgrowth 有效率多了。

所以今天用這個 fpgrowth 程式來跑跑看數據。

我從：http://fimi.ua.ac.be/data/ Frequent Itemset Mining Dataset Repository 抓了很多資料
http://fimi.ua.ac.be/data/T10I4D100K.dat
http://fimi.ua.ac.be/data/T40I10D100K.dat
http://fimi.ua.ac.be/data/webdocs.dat.gz

放到我的電腦內，然後去找 Christian Borgelt http://www.borgelt.net/fpgrowth.html 抓了一些程式。
大概長的這樣：
[hadoop@hnamenode FrequentItemset]$ ls -la
-rwxrwxr-x. 1 hadoop hadoop      486760 Sep  5 05:17 fpgrowth
-rw-rw-r--. 1 hadoop hadoop     4022055 Oct 14  2010 T10I4D100K.dat
-rw-rw-r--. 1 hadoop hadoop    15478113 Oct 14  2010 T40I10D100K.dat
-rw-rw-r--. 1 hadoop hadoop         151 Oct 17 23:15 webdocs.out

有個很簡單的檔案  sample_fpgrowth.txt

[hadoop@hnamenode FrequentItemset]$ cat sample_fpgrowth.txt 
r z h k p
z y x w v u t s
s x o n r
x z y m t s q e
z
x z y r q t p

# -m3 為找出三個元素在一起 , -s50 支持度 50  , 預設信任度為 80%
[hadoop@hnamenode FrequentItemset]$ ./fpgrowth -m3 -s50 sample_fpgrowth.txt sample_fpgrowth.out
./fpgrowth - find frequent item sets with the fpgrowth algorithm
version 6.7 (2015.08.18)         (c) 2004-2015   Christian Borgelt
reading sample_fpgrowth.txt ... [17 item(s), 6 transaction(s)] done [0.00s].
filtering, sorting and recoding items ... [6 item(s)] done [0.00s].
sorting and reducing transactions ... [4/6 transaction(s)] done [0.00s].
writing sample_fpgrowth.out ... [5 set(s)] done [0.00s].

[hadoop@hnamenode FrequentItemset]$ cat sample_fpgrowth.out 
y x z (50)
t z x y (50)
t z x (50)
t z y (50)
t x y (50)

可以知道上面這五個組合，是 sample_fpgrowth.txt 這裡最常出現的組合。

後來繼續用 fpgrowth 依序分析底下這些檔案，做了一些範例。
[hadoop@hnamenode FrequentItemset]$ ./fpgrowth -m2 -s1 T10I4D100K.dat T10I4D100K.out.txt
./fpgrowth - find frequent item sets with the fpgrowth algorithm
version 6.7 (2015.08.18)         (c) 2004-2015   Christian Borgelt
reading T10I4D100K.dat ... [870 item(s), 100000 transaction(s)] done [0.09s].
filtering, sorting and recoding items ... [375 item(s)] done [0.01s].
sorting and reducing transactions ... [87314/100000 transaction(s)] done [0.02s].
writing T10I4D100K.out.txt ... [10 set(s)] done [0.09s].
[hadoop@hnamenode FrequentItemset]$ cat T10I4D100K.out.txt
829 368 (1.194)
789 829 (1.194)
682 368 (1.193)
346 217 (1.336)
825 39 (1.187)
390 722 (1.042)
227 390 (1.049)
704 39 (1.107)
704 825 39 (1.035)
704 825 (1.102)

[hadoop@hnamenode FrequentItemset]$ ./fpgrowth -m3 -s2 T40I10D100K.dat T40I10D100K.out.txt
./fpgrowth - find frequent item sets with the fpgrowth algorithm
version 6.7 (2015.08.18)         (c) 2004-2015   Christian Borgelt
reading T40I10D100K.dat ... [942 item(s), 100000 transaction(s)] done [0.29s].
filtering, sorting and recoding items ... [610 item(s)] done [0.01s].
sorting and reducing transactions ... [99929/100000 transaction(s)] done [0.13s].
writing T40I10D100K.out.txt ... [6 set(s)] done [1.81s].

[hadoop@hnamenode FrequentItemset]$ cat T40I10D100K.out.txt
829 529 368 (2.288)
217 529 368 (2.181)
682 489 368 (2.42)
692 529 368 (2.373)
895 937 368 (2.081)
198 937 368 (2.099)


[hadoop@hnamenode FrequentItemset]$ ./fpgrowth -m6 -s23 webdocs.dat webdocs.out.txt
./fpgrowth - find frequent item sets with the fpgrowth algorithm
version 6.7 (2015.08.18)         (c) 2004-2015   Christian Borgelt
reading webdocs.dat ... [5267656 item(s), 1692082 transaction(s)] done [40.53s].
filtering, sorting and recoding items ... [39 item(s)] done [2.25s].
sorting and reducing transactions ... [959755/1692082 transaction(s)] done [3.50s].
writing webdocs.out.txt ... [13 set(s)] done [1.47s].

[hadoop@hnamenode FrequentItemset]$ cat webdocs.out.txt
171 124 516 49 8 122 (24.2785)
51 124 516 49 8 122 (26.1091)
51 171 516 49 8 122 (23.7428)
121 124 516 49 8 122 (26.9704)
121 51 516 49 8 122 (26.0395)
121 51 124 49 8 122 (24.6961)
121 51 124 516 8 122 (23.2243)
121 171 516 49 8 122 (24.2021)
121 171 124 49 8 122 (23.0385)
60 124 516 49 8 122 (24.0302)
60 121 516 49 8 122 (24.4904)
60 121 124 49 8 122 (23.5529)
60 51 516 49 8 122 (23.2219)

如果仔細看可以得知，這幾個檔案容量大小差很多。可以仔細觀察它門的執行時間。
-rw-r--r--. 1 hadoop hadoop   68 Oct 17 22:12 sample_fpgrowth.txt
-rw-rw-r--. 1 hadoop hadoop 3.9M Oct 14  2010 T10I4D100K.dat
-rw-rw-r--. 1 hadoop hadoop  15M Oct 14  2010 T40I10D100K.dat
-rw-rw-r--. 1 hadoop hadoop 1.4G Oct 14  2010 webdocs.dat

除了 webdocs.dat 這個檔案，跑比較久外，其他都很快。
講這多，就是剛有機會用 apache spark 來跑   fpgrowth algorithm 想要知道揪竟 big data 要多大才有他的效益。

延伸閱讀：
Apache Spark 測試 FPGrowth(傳統C語言與Spark 的簡易測試)http://blog.jangmt.com/2015/10/apache-spark-fpgrowthcspark.html