最近上數(shù)據(jù)挖掘的課程，其中學(xué)習(xí)到了頻繁模式挖掘這一章，這章介紹了三種算法，Apriori、FP-Growth和Eclat算法；由于對于不同的數(shù)據(jù)來說，這三種算法的表現(xiàn)不同，所以我們本次就對這三種算法在不同情況下的效率進(jìn)行對比。從而得出適合相應(yīng)算法的情況。

（一）算法原理

其中相應(yīng)的算法原理在之前的博客中都有非常詳細(xì)的介紹，這里就不再贅述，這里給出三種算法大概的介紹

但是這里給出每個算法的關(guān)鍵點(diǎn)：

1.1 Apriori算法：

  • 限制候選產(chǎn)生發(fā)現(xiàn)頻繁項(xiàng)集

  • 重要性質(zhì)：頻繁項(xiàng)集所有非空子集也一定是頻繁的。

  • 主要步驟：

  1. 連接

  2. 剪枝

  • 特點(diǎn)：需要多次掃描數(shù)據(jù)庫，對于大規(guī)模數(shù)據(jù)效率很低！

Apriori算法原理詳細(xì)介紹：http://www.cnblogs.com/90zeng/p/apriori.html

1.2 FP-Growth算法

  • 通過模式增長挖掘頻繁模式

  • 主要步驟：

  1. 構(gòu)建頻繁模式樹

  2. 構(gòu)造條件模式基

  3. 挖掘頻繁模式

  • 特點(diǎn)：兩次掃描數(shù)據(jù)庫，采用分治的策略有效降低搜索開銷

FP-Growth算法原理詳細(xì)介紹：http://www.cnblogs.com/datahunter/p/3903413.html

1.3 Eclat算法

  • 使用垂直格式挖掘頻繁項(xiàng)集

  • 主要步驟：

  1. 將數(shù)據(jù)倒排{ item：TID_set }

  2. 通過求頻繁k項(xiàng)集的交集來獲取k+1項(xiàng)集

  • 特點(diǎn)：僅需要一次掃描數(shù)據(jù)庫，TID集合很長的話需要消耗大量的內(nèi)存和計(jì)算時間

Eclat算法原理詳細(xì)介紹：

網(wǎng)友評論