理解關聯規則演算法：演算法應用

上篇我們講到，關聯規則演算法的本質是利用很容易實現的原理：

如果一個組合是非頻繁項集，則其超集也一定非頻繁

換句話說，如果{啤酒}出現的次數不多，那麼{啤酒，尿布}的組合出現的次數一定不會多的啦。

那麼在各種演算法（Apriori、FP-Growth、Eclat）中是怎麼具體應用這個理論的呢？

在講解演算法之前，我們需要了解支持度（support）這個概念。

支持度——數據集出現的概率，即

仔細一看，支持度就是這個組合出現的概率嘛，5個購物車裡，啤酒+尿布出現了4次，支持度就是0.8。

也就是說，我們想找的頻繁項集實際上就是支持度高的項集。理論上，只要我們計算出所有商品的排列組合集合的支持度，比如計算出{麵包}、{牛奶}...{麵包、牛奶}、{麵包、尿布}...{麵包、牛奶、尿布}...所有組合的支持度，找到支持度高的那幾個集合就可以找到關聯規則啦~

然鵝，商品好多好多好多，這麼算下去效率實在是太低啦~怎麼樣才能提高計算效率呢？

我們先來看一下Apriori演算法是如何實現的。概括來說，這個演算法是先計算出每個單項的支持度，剔除掉支持度低的之後，把剩餘項兩兩組合起來接著計算。

舉個栗子~上文中的購物清單中，各個單項的支持度如下：

根據先驗原理的逆否命題，子集非頻繁（即其支持度較低），其超集也一定非頻繁，那麼我們就可以把上表裡一些支持度低的項去掉了，因為它們的超集支持度肯定也不會高的。這裡我們去掉支持度小於等於0.6（0.6是可以設置的）的項，就得到了下表：

好了，現在把這個表裡的項目兩兩組合一下再算個支持度，構成這個表：

好啦，這下我們就可一得到一條關聯規則了~也就是支持度最高的{尿布、啤酒}。當然，如果還想繼續算下去，比如{麵包、尿布、啤酒}，那麼重複上面的步驟就可以了~~

Apriori演算法是關聯規則里一條經典的演算法，而FP-Growth和Eclat演算法在原理上與Apriori演算法大同小異，只不過是在計算效率上應用了更多的trick。

FP-Growth演算法也是先剔除掉支持度低的項，然後構建一棵二叉樹來得到頻繁項集；Eclat演算法則是利用了倒排序的思想，這可以使數據的輸入輸出只進行一次，提高了計算速度。

關於關聯規則演算法的介紹就到這裡，更多量化投資相關知識將在以後慢慢推送送，歡迎持續關注公眾號寬客塔: )

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！