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

（一）算法原理

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

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

1.1 Apriori算法：

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

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

  • 主要步驟：

  1. 連接

  2. 剪枝

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

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

1.2 FP-Growth算法

  • 通過(guò)模式增長(zhǎng)挖掘頻繁模式

  • 主要步驟：

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

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

  3. 挖掘頻繁模式

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

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

1.3 Eclat算法

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

  • 主要步驟：

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

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

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

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

網(wǎng)友評(píng)論