eclat算法

eclat算法簡介

Eclat算法是一種深度優先算法,採用垂直數據表示形式,在概念格理論的基礎上利用基於前綴的等價關係將搜尋空間(概念格[4])劃分為較小的子空間(子概念格)。

eclat算法原理

垂直數據表示

支持度的計算需要訪問資料庫。在大多數算法中,考慮資料庫中事務(即記錄)的表示形式。從概念上講,這樣的資料庫可以用一個二進制的二維矩陣來表示,矩陣的每一行代表資料庫的一條事務,每一列代表項目。
傳統的數據挖掘算法多採用水平數據表示,在水平數據表示中,資料庫的一條事務由事務標識符(TID)和項目組成。事務由TID唯一標識,一條事務可以包含一個項目或多個項目。Apriori、FP?Growth等算法都是採用此種表示方法。
定義1(Tidset)?設有項目X,包含項目X的所有事務的標識符的集合稱為項目X的Tidset。在這種數據表示方法中,資料庫的事務由項目和該項目的Tidset組成,該事務由項目唯一標識。Tidset垂直數據表示:資料庫中的每一條記錄由一個項目及其所出現過的所有事務記錄的列表(即Tidset表)構成。這樣使得任何一個頻繁項集的支持度計數都可以通過對Tidset交集運算求得。

支持度計數方法

Eclat算法採用方法二計算支持度。對候選k項集進行支持度計算時,不需再次掃描資料庫,僅在一次掃描資料庫後得到每個1項集的支持度,而候選k項集的支持度就是在對k-1項集進行交集操作後得到的該k項集Tidset中元素的個數。

概念格理論

Eclat算法在概念格理論的基礎上,利用基於前綴的等價關係將搜尋空間(概念格)劃分為較小的子空間(子概念格),各子概念格採用自底向上的搜尋方法獨立產生頻繁項集。

eclat算法不足

在Eclat算法中,它由2個集合的並集產生新的候選集,通過計算這2個項集的Tidset的交集快速得到候選集的支持度,因此,當Tidset的規模龐大時將出現以下問題:(1)求Tidset的交集的操作將消耗大量時間,影響了算法的效率;(2)Tidset的規模相當龐大,消耗系統大量的記憶體。