數據挖掘-Eclat算法
本次實驗，我主要負責實現Apriori算法的改進算法——Eclat算法。
Eclat算法的基本思想
首先，有引理：每個k+1項的頻繁項集可以由兩個k項的頻繁項集經過或運算生成，并且將這兩個頻繁項集中的項按排序碼從小到大排列后，這兩個k項頻繁項集只有最后一項不一樣，之前的k-1項完全一樣。引理容易證明：假設這個k+1項的頻繁項集的支持度為a，閾值限制為b，則顯然有a≥b。該k+1項中的前k項的集合C1的支持度顯然大于等于 a，同樣前k-1項和最后一項組成的集合C2支持度顯然也大于等于a。易得，C1,C2均為頻繁項集，且這兩個集合經過或運算可以得到上述的k+1項的頻 繁項集。
下證如果已經找到所有的k項頻繁，可以找到所有的k+1項集。假設不能找到所有的k+1項集，那么與引理矛盾。所以可以通過已知所有的k項頻繁項集找到所有的k+1項頻繁項集。
可以通過掃描一遍數據庫，得到所有的一維的頻繁項集。則由以上結論，我們可以遞歸地得到所有的頻繁項集。
Eclat算法根據以上結論，可以掃描一遍數據庫，先獲得一維的頻繁項集，然后無需再掃描數據庫，直接處理所有的一維的頻繁項集，就可以遞歸得到所有的頻繁項集。
Eclat算法的具體實現
主要的數據結構有兩個，記錄頻繁項集以及相關信息的mymap類，和處理單一項的onemap類。mymap類由一個bitset記錄頻繁項集（當某個項出現在該頻繁項集中則相應的bitset位為1），一個bitset記錄出現在哪些交易中，以及一個int記錄頻繁項集的支持度。
onemap類由一個bitset記錄該項出現在哪些交易中，以及該項的支持度。該項的具體編號不需要記錄，因為建了一個onemap數組對應每一個單項，單項可以通過數組中的下標值區分。
實現的Eclat算法主要分兩個階段，input階段掃描數據庫一遍，connect階段連接擴展頻繁項集維數。
input階段的主要任務是掃描一遍數據庫，數據存入onemap，再導入到mymap中。掃描每條交易時，處理每一項對應的onemap，即支 持度加一，交易對應的bitset位置1。掃描完所有的交易后，onemap記錄了所有單項的支持度和所在的交易。對所有單項依次進行判斷，如果某單項的 支持度大于閾值，就mymap動態數組mmp1中加入一個元素，該元素與該單項對應。input完成時，動態數組mmp1中已經存了所有的一維的頻繁項 集，并且由于之前是依次處理的，所以mmp1中元素是有序的。
connect階段的主要任務是，通過k維頻繁項集生出k+1維頻繁項集。這里定義了一個函數，void connect(vector
conmp函數的實現。認為只有最后一項不同的頻繁項集才能生成下一維的頻繁項集。則對于vm1兩個元素記錄頻繁項集的bitset找到最后一個 非零位置0，如此處理后，如果符合條件，那么這兩個bitset應該相同，不同則無法生成下一維。如果可以生成，那么記錄頻繁項集的兩個bitset簡單 的進行或運算就可以得到下一維頻繁項集，記錄交易的頻繁項集進行與操作就可以得到生成的頻繁項集的記錄交易的bitset，對該bitset中的非0位進 行記數，如果小于閾值，則舍棄，否則加入vm2。
connect函數的實現。由上，一維的頻繁項集是按大小有序排列的，本函數確保生成的下一維頻繁項集的仍然有序（vm2中元素按記錄頻繁項集的 bitset有序排列）。由于有序，只有最后一項不同的頻繁項集顯然相鄰。對于vm1中的第i項，與i之后的每一項進行conmp，一旦發現一次生成失 敗，則第i項處理結束，對i+1項進行處理。處理完vm1中所有的元素后，清空vm1中的元素，如果這時vm2中的元素個數大于等于2,則 connect(vm2,vm1)，即將vm2中的元素當做k維元素，向vm1中生成k+1維的頻繁項集。
另：如果需要輸出數據的話，在發現一個頻繁項集后，立刻輸出。
一些優化
選用bitset進行存儲，相對于布爾節省了空間。同時，bitset的位運算，在一定程度上，節省了時間，程序更精簡。在connect函數的實現中，只是用了兩個vector，利用類似與滾動數組的思想，將vm1與vm2不斷交換功能，極大地節省了空間。
遇到的問題及解決
一開始出現了爆內存的情況，原因是本來打算將所有頻繁項都存在內存中，方便輸出時間忽略輸入到文件。后來，直接一邊找一邊輸出，如果要計時就直接不輸出。還發現程序在小閾值時跑得非常慢。多次檢查后發現，connect函數中，i元素與j元素連接失敗后，沒有停止對i的繼續連接。實際上，i與i之后的某元素連接失敗后可以開始對i+1元素測試，因為可生成下一維的元素一定相鄰。
感想
總體來說，Eclat算法不難理解也不難理解。經過本次實驗，加深了對數據挖掘的理解。不一樣的算法，花費的時間相差很大，也讓我體會到算法意義不僅僅是做幾道題那么簡單。本次實驗，還讓我熟悉了bitset的相關函數。
算法比較
下面列出的三個塊分別是對三組數據不同閾值下,三種算法所需的時間,單位秒.
全部算法g++編譯,-O2優化,不計算輸出時間.
運行環境ubuntu13.04 64位;cpu i5;內存 4G.
相對fp_growth算法與改進版的fp_growth算法來看,還是差了一點的.
[本算法占內存較大!極容易爆內存!]
/*============================================================================= FileName: Eclat.cpp
Desc:
Author: zhuting
Email: cnjs.zhuting@gmail.com
HomePage: my.oschina.net/locusxt
Version: 0.0.1
CreatTime: 2013-12-07 18:54:34
LastChange: 2013-12-07 18:54:34
History:
=============================================================================*/
include <cstdio>
include <cstdlib>
include <bitset>
include <string>
include <cstring>
include <time.h>
include <vector>
define item 1001
define line 100000
define datafile "T10I4D100K.dat"
define outputfile "r_ans.txt"
define out_put false
using namespace std;
int min_num = 0;/最小要求項集出現次數/ char outputfilename[500] = outputfile; FILE* fw = fopen(outputfilename, "w");
class mymap { public: bitset <item> it_bs;/頻繁項集/ int it_set;/支持度/ bitset <line> l_bs;/交易/ mymap() { it_set = 0; } }; vector <mymap> mmp1; vector <mymap> mmp2;
int cur_beg = 0, cur_end = -1, cur_mmp = -1;
/onemap用來記錄一維的頻繁項集/ class onemap { public: int it_set;/支持度/ bitset <line> l_bs;/出現在哪些交易中/ onemap() { it_set = 0; } }; onemap om[item];
/掃描數據庫, 獲取一維頻繁項集/ void input() { char filename[500] = datafile; FILE* fp = fopen(filename, "r"); char ch_temp[500]; int cur_line = 0; char ch_num[500]; int num_cur = -1; int i_temp = 0;
while(cur_line < line) { ++cur_line; fscanf(fp, "%[^\n]", ch_temp); fscanf(fp, "\n"); int len = strlen(ch_temp); for (int i = 0; i < len; ++i) { if (ch_temp[i] == ' ') { ch_num[++num_cur] = '\0'; sscanf(ch_num, "%d", &i_temp); om[i_temp].l_bs[cur_line] = true; om[i_temp].it_set += 1; num_cur = -1; } else ch_num[++num_cur] = ch_temp[i]; } } for (int i = 1; i < item; ++i) { if (om[i].it_set >= min_num)/*將一維頻繁項集放入mymap*/ { mymap mp; mp.it_bs[i] = true; mp.it_set = om[i].it_set; mp.l_bs = om[i].l_bs; ++cur_mmp; mmp1.push_back(mp); if (out_put) { for (int j = 0; j < item; ++j) { if (mp.it_bs[j]) fprintf(fw, "%d ", j); } fprintf(fw, ":%d\n", mp.it_set);/*輸出支持度*/ } } } fclose(fp); return;}
bool conmp(int a, int b, vector <mymap> & vm1, vector <mymap> & vm2) { bool afind = 0, bfind = 0; bitset <item> a_bs = vm1[a].it_bs; bitset <item> b_bs = vm1[b].it_bs; for (int i = item - 1; i >= 0; --i)/判斷兩個項集是否只相差最后一個項,即是否可以生成k+1項/ { /* 從后向前找到第一個bitset值為1的位置,并將其置0.
* 如果兩個項集只相差最后一個項不同,則分別置0后,兩個項集應該一樣*/ if (!afind && a_bs[i]) { afind = true; a_bs[i] = 0; } if (!bfind && b_bs[i]) { bfind = true; b_bs[i] = 0; } if (afind && bfind) { break; } } if (a_bs != b_bs) return false;/*分別置0操作后,若不一樣,則無法生成k+1項*/ bitset <line> bs_temp = vm1[a].l_bs & vm1[b].l_bs;/*由k項生成k+1項*/ int i_temp = bs_temp.count();/*支持度*/ if (i_temp >= min_num) { mymap mp; mp.it_bs = vm1[a].it_bs | vm1[b].it_bs; mp.l_bs = bs_temp; mp.it_set = i_temp; vm2.push_back(mp); ++cur_mmp; if (out_put) { for (int j = 0; j < item; ++j) { if (mp.it_bs[j]) fprintf(fw, "%d ", j); } fprintf(fw, " : %d\n", mp.it_set); } } return true;}
void connect(vector <mymap> & vm1, vector <mymap> & vm2) {
for (int i = 0; i < vm1.size(); ++i) for (int j = i + 1; j < vm1.size(); ++j) { bool b_temp = conmp(i, j, vm1, vm2); if(!b_temp) break; } vm1.clear(); if(vm2.size() >= 2) connect(vm2, vm1);/*充分利用空間,兩個vector交替使用*/ return;}
int main() { float minsup;/閾值,小數形式.eg.%5, 閾值為0.05/ printf("input limit...\n"); scanf("%f", &minsup); min_num = (int)((float)(line) minsup) + 1;/min_num為最小要求的個數/ if (out_put) printf("%d\n", min_num); if (out_put) printf("now load date...\n"); int start = clock();/開始計時/ input(); if (out_put) printf("now connect...\n"); connect(mmp1, mmp2); int finish = clock();/結束計時/ printf("total time: %f\n", (float)((float)(finish - start) / (float)CLOCKS_PER_SEC)); printf("%d\n", cur_mmp + 1);/輸出總的頻繁項集數*/ //if(out_put) fprintf(fw, "%d\n", cur_mmp + 1); fclose(fw); return 0; }</pre>
來自：http://my.oschina.net/locusxt/blog/183168 </mymap></mymap></mymap></mymap>