最近剛上了資料挖掘這門課，老師講了兩個算法，即Apriori算法和FP-growth算法，然後布置了上機作業，挖掘一個有8萬行的記錄的retail.dat，需要從中找出強規則，即同時滿足最小支援度和最小置信度的規則。
Apriori算法
在這裡給出一個實作找出所有頻繁模式集的c++代碼，其中主要使用的存儲結構是二維數組，有點簡陋，湊合着看看。
另外，這個版本是剛寫出來初始版本，自連接配接之後沒有修剪步驟，而是直接掃描資料庫，是以效率偏低。
這個版本測試時用的最小支援度是2000，這個支援度比較大，是以輸出結果還是較快的。不過如果最小支援度設為1000以下的話，那麼運作速度就差了很多。
改進之後增加了修剪步驟的算法運作速度在最小支援度較低時運作速度明顯加快，但是還是耗時較長。
可以看到，在最小支援度在500時，改進後的算法提升了一分多鐘，是以修剪對于Apriori算法來說是很重要的一步。
12.02更新
這兩天本來打算補完修剪部分，就去研究一下FP-growth算法的。結果發現樹的知識還不會，準備先把資料結構的樹部分的OJ題刷完再寫。于是這兩天一直在優化Apriori算法，終于在參考了韓家偉教授的《資料挖掘：概念與技術》一書後，明白了可以用散列函數來處理2項集，效率一下子就提上來了。在這裡給出書中的描述。
由于散列函數，也就是哈希函數其實我也不會，百度看了大半天，大概懂了一點，在這裡用二項集的例子嘗試着解釋一下。
在優化前的代碼中，二項集的處理是每掃描一行資料庫，便需要将二項集中的每一項拿出來比較，假設二項集中有n組項，即一行資料庫就需要掃描n次，效率十分低下。
而對于一項集，則用了計數排序的思想，即在第一次掃描讀取全體資料集時，每讀取一個數temp，便在相應的H[temp]++，如此實作了一項集的快速計數。
如果二項集也能采取類似的方法，那麼運作效率無疑會比現在高出很多。是以哈希函數就是這麼個東西，我們能夠用一個關鍵字key來表示一組數，這裡用的應該是叫桶哈希的方法。
首先我們需要建立出一個Hash數組，其大小由你使用的雜湊演算法決定，然後在掃描生成一項集的同時，對資料集的每一行中的項組成所有的二項集，然後使用散列函數hash(x,y）建立散清單，同時進行相應的桶計數。全部掃描完成後，我們便得到了一個存有全體資料集的一個Hash數組（原諒我隻會數組）。
在我們自連接配接得到了候選二項集C2後，掃描每一個項{i,j}，判斷Hash[hash(i,j)]是否大于你的最小支援度門檻值Min_sup，由此可以通過掃描一次候選二項集C2快速的得到一個頻繁二項集L2。
接下來我們看一個簡單的例子
圖6.2中代表一個資料集，我們可以使用函數hash（x,y）=(x10+y)%7建立Hash數組，顯然其大小size為7。
先看第一行，I1,I2,I5，可以組成三個二項集{I1,I2}，{I1,I5}，{I2,I5}，我們使用函數将其存入Hash數組中，key=hash（1,2）=（110+2）mod 7=5，H[key]++；hash（1,5）=1，Hash[1]++；hash（2,5）=4，Hash[4]++;即每一個二項集都對應着Hash中的一個key，接下來每一行都可以用該方法存入。
其中{I1,I4}，{I3,I5}因為hash（1,4）=hash（3,5）=0，則他們被稱為同義詞，如果我們不進行任何處理的話，在計數中Hash[0]對應的數包含這兩個項。在這裡我們可以使用開放位址法（線性探測法），再哈希法，鍊位址法解決這種“位址沖突”，由于我也是剛剛快速看完哈希函數，是以具體的知識都不太了解，有興趣的可以自行去查找相關資料，這裡就不說如何将他們分别存放了。
經過上面這一步，我們在第一次掃描資料集的時候，就同時得到了一個存着資料集中全部二項集的Hash數組。假設圖6.2中項的最小支援度門檻值為2，首先可得到候選二項集為{I1,I2}，{I1,I3}，{I1,I4}，…，{I3,I5}，{I4,I5}，接着就是掃描全體資料集得出每一個二項集的支援度計數，但是我們已經有了一個存着全部二項集的哈希數組，是以我們隻需要在Hash找到相應的支援度就可以了。如{I1,I2}的支援度為Hash[hash(1,2)]，如果該數值大于2，即存入頻繁二項集L2中。
改進後的算法1%支援度掃描時間由20多秒減少到了7秒，進步了不少。
支援度為千分之五掃描時間也隻需要10秒，不過存在的問題還是比較多，各個地方查缺補漏的，越寫越亂，可讀性極差。
源碼釋出在我的Github上。