數(shù)據(jù)挖掘Apriori算法

1、精品文檔實(shí)驗(yàn)報告實(shí)驗(yàn)課程名稱：數(shù)據(jù)挖掘?qū)嶒?yàn)項(xiàng)目名稱：Apriori算法理 學(xué) 院實(shí)驗(yàn)時間：2014年11月11日.精品文檔學(xué)生所在學(xué)院：理學(xué)院專業(yè)：統(tǒng)計學(xué)班級：姓名學(xué)號實(shí)驗(yàn)組實(shí)驗(yàn)時間指導(dǎo)教師成績實(shí)驗(yàn)項(xiàng)目名稱Apriori算法實(shí)驗(yàn)?zāi)康募耙?：1. 加強(qiáng)對 Apriori 算法的理解2. 鍛煉分析問題、解決問題以及動手能力3. 編程實(shí)現(xiàn) Apriori 算法實(shí)驗(yàn)（或算法）原理 ：Apriori算法是一種找頻繁項(xiàng)目集的基本算法。其基本原理是逐層搜索的迭代：頻繁K項(xiàng) Lk 集用于搜索頻繁 (K+1) 項(xiàng)集 Lk+1，如此下去，直到不能找到維度更高的頻繁項(xiàng)集為止。這種方法依賴連接和剪枝這兩步來實(shí)現(xiàn)。算

2、法的第一次遍歷僅僅計算每個項(xiàng)目的具體值的數(shù)量，以確定大型 l 項(xiàng)集。隨后的遍歷，第 k 次遍歷，包括兩個階段。首先，使用在第 (k-1) 次遍歷中找到的大項(xiàng)集 Lk-1 和用 Aprioir-gen 函數(shù)產(chǎn)生候選項(xiàng)集 Ck。接著掃描數(shù)據(jù)庫，計算 Ck 中候選的支持度。用 Hash樹可以有效地確定 Ck中包含在一個給定的事務(wù) t 中的候選。算法如下：(1) L1 = 大項(xiàng)目集 1 項(xiàng)目集 ;(2)for(k = 2;Lk-1!=空;k+)dobegin(3)Ck= apriori-gen(Lk-1);/ 新的候選集(4) for所有事務(wù)t Ddobegin(5)Ct =subset(Ck，t);

3、/t中所包含的候選(6)for所有候選c Ctdo(7) c.count+;(8) end(9) Lk=cCk|c.countminsupp(10) end(11) key = Lk； Apriori-gen 函數(shù)：1Apriori 候選產(chǎn)生函數(shù) Apriori-gen 的參數(shù) Lk-1 ，即所有大型 (k-1) 項(xiàng)目集的集合。它返回所有大型 k 項(xiàng)目集的集合的一個超集 (Superset) 。首先，在 Jion( 連接 ) 步驟，我們把 Lk-1和 Lk-1 相連接以獲得候選的最終集合的一個超集Ck：(1)insertintoCk(2)selectp1，p2 ， pk-1 ，qk-1(3)f

4、romLk-1p ，Lk-1q(4)wherep1= q1 ， pk-2=qk-2， pk-1< qk-接著，在 Prune( 修剪 ) 步驟，我們將刪除所有的項(xiàng)目集cCk，如果 c 的一些 k-1 子.精品文檔集不在 Lk-1 中，為了說明這個產(chǎn)生過程為什么能保持完全性，要注意對于Lk 中的任何有最小支持度的項(xiàng)目集，任何大小為k-1 的子集也必須有最小支持度。因此，如果我們用所有可能的項(xiàng)目擴(kuò)充 Lk-1中的每個項(xiàng)目集，然后刪除所有 k-1 子集不在 Lk-1中的項(xiàng)目集，那么我們就能得到Lk 中項(xiàng)目集的一個超集。上面的合并運(yùn)算相當(dāng)于用數(shù)據(jù)庫中所有項(xiàng)目來擴(kuò)展Lk-1 ；如果刪除擴(kuò)展項(xiàng)目集的

5、第 k-1個項(xiàng)目后得到的 k-1 項(xiàng)目集不在 Lk-1中，則刪除該擴(kuò)展項(xiàng)目集。條件pk-1< qk-1 保證不會出現(xiàn)相同的擴(kuò)展項(xiàng)。因此，經(jīng)過合并運(yùn)算，Ck>Lk。類似原因在刪除運(yùn)算中，刪除Ck 中其 k-1子項(xiàng)目集不在 Lk-1 中的項(xiàng)目集，同樣沒有刪除包含在 Lk 中的項(xiàng)目集。(1)for所有項(xiàng)目集 c Ckdo(2)for所有 c 的(k-1)子集 sdo(3) if(s Lk-1)then(4) 從 Ck中刪除 c例如： L3 為123 ，1 24 ，13 4 ，1 3 5 ，2 3 4。 Jion 步驟之后， C4為 123 4 ，13 45 。Prune 步驟將刪除項(xiàng)集

6、13 45 ，因?yàn)轫?xiàng)集 1 45 不在 L3 中。Subset 函數(shù)：候選項(xiàng)目集 Ck 存儲在一棵 Hash樹中。Hash 樹的一個節(jié)點(diǎn)包含了項(xiàng)集的一個鏈表( 一個葉節(jié)點(diǎn) ) 或包含了一個 Hash表( 一個內(nèi)節(jié)點(diǎn) ) 。在內(nèi)節(jié)點(diǎn)中， Hash 表的每個 Bucket 都指向另一個節(jié)點(diǎn)。 Hash 樹的根的深度定義為 1。在深度 d 的一個內(nèi)節(jié)點(diǎn)指向深度 d+1 的節(jié)點(diǎn)。項(xiàng)目集存儲在葉子中。要加載一個項(xiàng)目集 c 時，從根開始向下直到一個葉子。在深度為 d 的一個內(nèi)節(jié)點(diǎn)上，要決定選取哪個分枝，可以對此項(xiàng)目集的第d 個項(xiàng)目使用一個 Hash函數(shù)，然后跟隨相應(yīng)Bucket 中的指針。所有的節(jié)點(diǎn)最初都

7、創(chuàng)建成葉節(jié)點(diǎn)。當(dāng)一個葉節(jié)點(diǎn)中項(xiàng)集數(shù)量超過某個指定的閾值時，此葉節(jié)點(diǎn)就轉(zhuǎn)為一個內(nèi)節(jié)點(diǎn)。從根節(jié)點(diǎn)開始， Subset 函數(shù)尋找所有包含在某個事務(wù) t 中的候選，方法如下：若處于一個葉子，就尋找此葉子中的哪些項(xiàng)目集是包括在 t 中的，并對它們附加引用指向答案集合。若處于一個內(nèi)節(jié)點(diǎn)，而且是通過 Hash項(xiàng)目 i 從而到達(dá)此節(jié)點(diǎn)的，那么就對 t中 i 之后的每個項(xiàng)目進(jìn)行 Hash，并對相應(yīng) Bucket 中的節(jié)點(diǎn)遞歸地應(yīng)用這個過程。 對于根節(jié)點(diǎn)，就對 t 中的每個項(xiàng)目進(jìn)行 Hash。盡管 Apriori 算法已經(jīng)可以壓縮候選數(shù)據(jù)項(xiàng)集 Ck，但是對于頻繁項(xiàng)集尤其是 2 維的候選數(shù)據(jù)項(xiàng)集產(chǎn)生仍然需要大量的存

8、儲空間。 也就是說對于 2 維的候選數(shù)據(jù)項(xiàng)集， Apriori 算法的剪枝操作幾乎不起任何作用。例如： 1 維高頻數(shù)據(jù)項(xiàng)集 L1 的規(guī)模是 O(n) ，則 2 維候選數(shù)據(jù)項(xiàng)集的規(guī)模將達(dá)到 O(n2) 。如果我們考慮一般情況， 即在沒有支持度的情況下 1 維高頻數(shù)據(jù)項(xiàng)集 L1 的規(guī)模是 103，則 2 維候選數(shù)據(jù)項(xiàng)集的規(guī)模 C2 將達(dá)到C10005×105這種空間復(fù)雜度以指數(shù)形式的增長，使得這個經(jīng)典的算法的執(zhí)行效率很難讓人滿意 Apriori 算法的兩大缺點(diǎn)就是產(chǎn)生大量的候選集， 以及需重復(fù)掃描數(shù)據(jù)庫。.精品文檔實(shí)驗(yàn)硬件及軟件平臺：Windows7、Visual C+ 6.0實(shí)驗(yàn)內(nèi)容（

9、包括實(shí)驗(yàn)具體內(nèi)容、算法分析、源代碼等等）：#include<iostream>#include<string>#include <vector>#include <map>#include <algorithm>using namespace std;class Aprioripublic:Apriori(size_t is =0,unsigned int mv=0)item_size = is;min_value = mv;/Apriori() ;void getItem();map< vector<string>

10、,unsigned int> find_freitem();/求事務(wù)的頻繁項(xiàng)/連接連個k-1 級頻繁項(xiàng)，得到第k 級頻繁項(xiàng)map< vector<string>,unsigned int > apri_gen(unsigned int K , map< vector<string>,unsigned int > K_item);/展示頻繁項(xiàng)集void showAprioriItem(unsigned int K,map< vector<string>,unsigned int > showmap); private:

11、map< int , vector<string> > item;/ 存儲所有最開始的事務(wù)及其項(xiàng) map< vector<string>,unsigned int > K_item;/ 存儲頻繁項(xiàng)集 size_t item_size;/ 事務(wù)數(shù)目unsignedint min_value;/ 最小閾值;void Apriori:getItem()/用戶輸入最初的事務(wù)集int ci = item_size;for (int i=0;i<ci;i+)string str;vector<string> temp;.精品文檔cout&l

12、t;<" 請輸入第"<<i+1<<" 個事務(wù)的項(xiàng)集 (wangend)： "while (cin>>str && str !="wang")temp.push_back(str);sort(temp.begin(),temp.end();pair< map<int ,vector<string> >:iterator , bool> ret = item.insert(make_pair(i+1 ,temp); if (!ret.second

13、)-i;cout<<" 你輸入的元素已存在！請重新輸入！"<<endl;cout<<"- 運(yùn)行結(jié)果如下：-"<<endl;map< vector<string>,unsigned int> Apriori:find_freitem()unsigned int i = 1;bool isEmpty = false;map< int , vector<string> >:iterator mit ;for (mit=item.begin();mit != item

14、.end();mit+)vector<string> vec = mit->second;if (vec.size() != 0)break;if (mit = item.end()/ 事務(wù)集為空isEmpty = true;cout<<" 事務(wù)集為空！程序無法進(jìn)行."<<endl;map< vector<string>,unsigned int> empty;return empty;while(1)map< vector<string>,unsigned int > K_itemT

15、emp = K_item;K_item = apri_gen(i+,K_item);if (K_itemTemp = K_item)i = UINT_MAX;.精品文檔break;/ 判斷是否需要進(jìn)行下一次的尋找map< vector<string>,unsigned int > pre_K_item = K_item;size_t Kitemsize = K_item.size();/ 存儲應(yīng)該刪除的第K 級頻繁項(xiàng)集，不能和其他K 級頻繁項(xiàng)集構(gòu)成第K+1 級項(xiàng)集的集合if (Kitemsize != 1 && i != 1)vector< map

16、< vector<string>,unsigned int >:iterator > eraseVecMit;map< vector<string>,unsigned int >:iterator pre_K_item_it1 = pre_K_item.begin() , pre_K_item_it2;while (pre_K_item_it1 != pre_K_item.end() )map< vector<string>,unsigned int >:iterator mit = pre_K_item_it1;

17、bool isExist = true;vector<string> vec1;vec1 = pre_K_item_it1->first;vector<string> vec11(vec1.begin(),vec1.end()-1);while (mit != pre_K_item.end()vector<string> vec2;vec2 = mit->first;vector<string> vec22(vec2.begin(),vec2.end()-1);if (vec11 = vec22)break;+mit;if (mit

18、= pre_K_item.end()isExist = false;if (!isExist && pre_K_item_it1 != pre_K_item.end()eraseVecMit.push_back(pre_K_item_it1);/ 該第 K 級頻繁項(xiàng)應(yīng)該刪除+pre_K_item_it1;size_t eraseSetSize = eraseVecMit.size();if (eraseSetSize = Kitemsize)break;elsevector<map<vector<string>,unsignedint>:itera

19、tor>:iteratorcurrentErs=eraseVecMit.begin();while (currentErs != eraseVecMit.end()/ 刪除所有應(yīng)該刪除的第K 級頻繁項(xiàng)map< vector<string>,unsigned int >:iterator eraseMit = *currentErs;.精品文檔K_item.erase(eraseMit);+currentErs;elseif(Kitemsize = 1 )break;cout<<endl;showAprioriItem(i,K_item);return

20、K_item;map< vector<string>,unsigned int > Apriori:apri_gen(unsigned int K , map< vector<string>,unsigned int > K_item)if (1 = K)/ 求候選集C1size_t c1 = item_size;map< int , vector<string> >:iterator mapit = item.begin();vector<string> vec;map<string,unsigned

21、int> c1_itemtemp;while (mapit != item.end() )/將原事務(wù)中所有的單項(xiàng)統(tǒng)計出來vector<string> temp = mapit->second;vector<string>:iterator vecit = temp.begin();while (vecit != temp.end() )pair<map<string,unsignedint>:iterator,bool>ret=c1_itemtemp.insert(make_pair(*vecit+ , 1);if (!ret.sec

22、ond)+ ret.first->second;+mapit;map<string,unsigned int>:iterator item_it = c1_itemtemp.begin(); map< vector<string>,unsigned int > c1_item;while (item_it != c1_itemtemp.end() )/構(gòu)造第一級頻繁項(xiàng)集.精品文檔vector<string> temp;if ( item_it->second >= min_value)temp.push_back(item_it

23、->first);c1_item.insert(make_pair(temp , item_it->second) );+item_it;return c1_item;elsecout<<endl;showAprioriItem(K-1,K_item);map< vector<string>,unsigned int >:iterator ck_item_it1 = K_item.begin(),ck_item_it2; map< vector<string>,unsigned int > ck_item;while (c

24、k_item_it1 != K_item.end() )ck_item_it2 = ck_item_it1;+ck_item_it2;map< vector<string>,unsigned int >:iterator mit = ck_item_it2;/ 取當(dāng)前第K 級頻繁項(xiàng)與其后面的第K 級頻繁項(xiàng)集聯(lián)合，但要注意聯(lián)合條件/ 聯(lián)合條件：連個頻繁項(xiàng)的前K-1 項(xiàng)完全相同，只是第K 項(xiàng)不同，然后兩個聯(lián)合生成第 K+1 級候選頻繁項(xiàng)while(mit != K_item.end() )vector<string> vec,vec1,vec2;vec1 = c

25、k_item_it1->first;vec2 = mit->first;vector<string>:iterator vit1,vit2;vit1 = vec1.begin();vit2 = vec2.begin();while (vit1 < vec1.end() && vit2 < vec2.end() )string str1 = *vit1;string str2 = *vit2;+vit1;+vit2;if ( K =2 | str1 = str2 )if (vit1 != vec1.end() && vit2 !

26、= vec2.end() ).精品文檔vec.push_back(str1);elsebreak;if (vit1 = vec1.end() && vit2 = vec2.end() )-vit1;-vit2;string str1 = *vit1;string str2 = *vit2;if (str1>str2)vec.push_back(str2);vec.push_back(str1);elsevec.push_back(str1);vec.push_back(str2);map< int , vector<string> >:iterat

27、or base_item = item.begin(); unsigned int Acount = 0 ;while (base_item != item.end() )/ 統(tǒng)計該 K+1 級候選項(xiàng)在原事務(wù)集出現(xiàn)次數(shù)unsigned int count = 0 ,mincount = UINT_MAX;vector<string> vv = base_item->second;vector<string>:iterator vecit , bvit ;for (vecit = vec.begin();vecit < vec.end();vecit+)str

28、ing t = *vecit;count = 0;for (bvit=vv.begin();bvit < vv.end();bvit+)if (t = *bvit)count+;mincount = (count < mincount ? count : mincount );if (mincount >=1 && mincount != UINT_MAX).精品文檔Acount += mincount;+base_item;if (Acount >= min_value && Acount != 0)sort(vec.begin(),v

29、ec.end();/ 該第 K+1 級候選項(xiàng)為頻繁項(xiàng)，插入頻繁項(xiàng)集pair< map< vector<string>,unsigned int >:iterator , bool> ret = ck_item.insert(make_pair(vec,Acount);if (! ret.second)ret.first->second += Acount;+mit;+ck_item_it1;if (ck_item.empty()/ 該第 K+1 級頻繁項(xiàng)集為空，說明調(diào)用結(jié)束，把上一級頻繁項(xiàng)集返回 return K_item;elsereturn ck_

30、item;void Apriori:showAprioriItem(unsigned int K,map< vector<string>,unsigned int > showmap)map< vector<string>,unsigned int >:iterator showit = showmap.begin(); if (K != UINT_MAX)cout<<endl<<" 第 "<<K<<"級頻繁項(xiàng)集為："<<endl;elsecout

31、<<" 最終的頻繁項(xiàng)集為："<<endl;cout<<" 項(xiàng)集 "<<"t"<<" 頻率 "<<endl;while (showit != showmap.end() )vector<string> vec = showit->first;vector<string>:iterator vecit = vec.begin();cout<<" "while (vecit != vec.end()cout<<*vecit<<""+vecit;.精品文檔cout<<""<<"t"cout<<showit->second<<endl;+showit;unsigned int parseNumber(const cha