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

1、GUIZHOU UNIVERSITY實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)課程名稱：數(shù)據(jù)挖掘 實(shí)驗(yàn)項(xiàng)目名稱： Apriori算法理學(xué)院實(shí)驗(yàn)時(shí)間： 2014年 11月11 日姓名學(xué) 號(hào)實(shí)驗(yàn)組實(shí)驗(yàn)時(shí)間指導(dǎo)教師成績(jī)實(shí)驗(yàn)項(xiàng)目名稱Apriori 算法實(shí)驗(yàn)?zāi)康募耙螅? .加強(qiáng)對(duì)Apriori算法的理解2 .鍛煉分析問(wèn)題、解決問(wèn)題以及動(dòng)手能力3 .編程實(shí)現(xiàn)Apriori算法實(shí)驗(yàn)(或算法)原理：Apriori算法是一種找頻繁項(xiàng)目集的基本算法。其基本原理是逐層搜索的迭代：頻繁K項(xiàng)Lk集用于搜索頻繁(K+1)®集Lk+1,如此下去，直到不能找到維度更高的頻繁項(xiàng)集為 止。這種方法依賴連接和剪枝這兩步來(lái)實(shí)現(xiàn)。算法的第一次遍歷僅僅計(jì)

2、算每個(gè)項(xiàng)目的具體值的數(shù)量，以確定大型l項(xiàng)集。隨后的遍歷，第k次遍歷,包括兩個(gè)階段。首先，使用在第(k-1)次遍歷中找到的大項(xiàng)集Lk-1和用Aprioir-gen函數(shù)廣生候選項(xiàng)集Ck。接右掃描數(shù)據(jù)庫(kù)，計(jì)算Ck中候選的支持度。用Hash 樹(shù)可以肩效地確定Ck中包含在一個(gè)給定的事務(wù)t中的候選。算法如下：L1 =大項(xiàng)目集1項(xiàng)目集;(2) for (k = 2; Lk-1 !=空；k+) do begin(3) Ck = apriori-gen(Lk-1);學(xué)生所在學(xué)院：理學(xué)院專業(yè)：統(tǒng)計(jì)學(xué)班級(jí):."<<endl;map< vector<string>,unsign

3、ed int> empty;return empty;while(1)map< vector<string>,unsigned int > K_itemTemp = 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 =();存儲(chǔ)應(yīng)該刪除的第 K級(jí)頻繁項(xiàng)集，不能和其

4、他K級(jí)頻繁項(xiàng)集構(gòu)成第 K+1級(jí)項(xiàng)集的集合if (Kitemsize != 1 && i != 1)vector< map< vector<string>,unsigned int >:iterator > eraseVecMit;map< vector<string>,unsigned int >:iterator pre_K_item_it1 = () , pre_K_item_it2;while (pre_K_item_it1 !=()map< vector<string>,unsigned in

5、t >:iterator mit = pre_K_item_it1;bool isExist = true;vector<string> vecl;vecl = pre_K_item_it1->first;vector<string> vec11(),()-1);while (mit !=()vector<string> vec2;vec2 = mit->first;vector<string> vec22(),()-1);if (vec11 = vec22)break;+mit;if (mit =()isExist = fal

6、se;if (!isExist && pre_K_item_it1 !=()(pre_K_item_it1);該第K級(jí)頻繁項(xiàng)應(yīng)該刪除+pre_K_item_it1;size_t eraseSetSize =();if (eraseSetSize = Kitemsize)break;elsevector< map< vector<string>,unsigned int >:iterator >:iterator currentErs =();while (currentErs != ()/刪除所有應(yīng)該刪除的第K級(jí)頻繁項(xiàng) map< vec

7、tor<string>,unsigned int >:iterator eraseMit = *currentErs;(eraseMit);+currentErs;elseif(Kitemsize = 1 )break;cout<<endl;showAprioriItem(i,K_item);return K_item;map< vector<string>,unsigned int > Apriori:apri_gen(unsigned int K , map< vector<string>,unsigned int &

8、gt; K_item)if (1 = K)/求候選集 C1size_t c1 = item_size;map< int , vector<string> >:iterator mapit =();vector<string> vec;map<string,unsigned int> c1_itemtemp;while (mapit != () )/將原事務(wù)中所有的單項(xiàng)統(tǒng)計(jì)出來(lái)vector<string> temp = mapit->second;vector<string>:iterator vecit =();wh

9、ile (vecit !=()(pair< map<string,unsigned int>:iterator , bool > ret = (make_pair(*vecit+ , 1);if (!(+ >second;+mapit;map<string,unsigned int>:iterator item_it =();map< vector<string>,unsigned int > c1_item;while (item_it != () )/構(gòu)造第一級(jí)頻繁項(xiàng)集(vector<string> temp;i

10、f ( item_it->second >= min_value)(item_it->first);(make_pair(temp , item_it->second);+item_it; return c1_item;else(cout<<endl;showAprioriItem(K-1,K_item);map< vector<string>,unsigned int >:iterator ck_item_it1 = (),ck_item_it2;map< vector<string>,unsigned int &

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

12、;first;vec2 = mit->first;vector<string>:iterator vit1,vit2;vit1 =();vit2 =();while (vit1 < () && vit2 < ()(string str1 = *vit1;string str2 = *vit2;+vit1;+vit2;if ( K =2 | strl = str2 )(if (vitl != () && vit2 !=()(strl);)elsebreak;)if (vit1 = () && vit2 =()(-vit

13、1;-vit2;string str1 = *vit1;string str2 = *vit2;if (str1>str2)(str2);(str1);) else(strl);(str2);)map< int , vector<string> >:iterator base_item =();unsigned int Acount = 0 ;while (base_item != () )/統(tǒng)計(jì)該K+1級(jí)候選項(xiàng)在原事務(wù)集出現(xiàn)次數(shù) (unsigned int count = 0 ,mincount = UINT_MAX;vector<string> v

14、v = base_item->second;vector<string>二iterator vecit , bvit ;for (vecit = ();vecit < ();vecit+)(string t = *vecit;count = 0;for (bvit=();bvit < ();bvit+)(if (t = *bvit)count+;)mincount = (count < mincount count : mincount );)if (mincount >=1 && mincount != UINT_MAX)Acount

15、 += mincount;+base_item;if (Acount >= min_value && Acount != 0) (sort(),();/該第K+1級(jí)候選項(xiàng)為頻繁項(xiàng)，插入頻繁項(xiàng)集ret =pair< map< vector<string>,unsigned int >:iterator , bool> (make_pair(vec,Acount);if (!(>second += Acount; +mit;+ck_item_it1;if ()/該第K+1級(jí)頻繁項(xiàng)集為空，說(shuō)明調(diào)用結(jié)束，把上一級(jí)頻繁項(xiàng)集返回return

16、K_item;elsereturn ck_item;void Apriori:showAprioriItem(unsigned int K,map< vector<string>,unsigned int > showmap)(map< vector<string>,unsigned int >:iterator showit =();if (K != UINT_MAX) cout<<endl<<"第"<<K<<"級(jí)頻繁項(xiàng)集為："<<endl;el

17、secout<<"最終的頻繁項(xiàng)集為："<<endl;cout<<"項(xiàng)集"<<"t"<<"頻率"<<endl;while (showit !=()(vector<string> vec = showit->first;vector<string>:iterator vecit =();cout<<""while (vecit !=()cout<<*vecit<<

18、""+vecit;cout<<""<<"t"cout<<showit->second<<endl;+showit;unsigned int parseNumber(const char * str)/ 對(duì)用戶輸入的數(shù)字進(jìn)行判斷和轉(zhuǎn)換 if (str = NULL)return 0;elseunsigned int num = 0;size_t len = strlen(str);for (size_t i=0;i<len;i+)(num *= 10;if (stri>=

19、 '0' && stri <= '9')num += stri - '0'elsereturn 0;return num;void main()(/Apriori a;unsigned int itemsize = 0;unsigned int min;do(cout<<"請(qǐng)輸入事務(wù)數(shù)："char * str = new char;cin>>str;itemsize = parseNumber(str);cout<<"請(qǐng)輸入大于0正整數(shù)！ "<

20、<endl;) while (itemsize = 0);do(cout<<"請(qǐng)輸入最小支持度："char * str = new char;cin>>str;min = parseNumber(str);if (min = 0)(cout<<"請(qǐng)輸入大于0正整數(shù)！ "<<endl; while (min = 0);Apriori a(itemsize,min);();map< vector<string>,unsigned int> AprioriMap =();/(UINT_MAX,AprioriMap);system("pause");運(yùn)行的結(jié)果：end) i end> ： end)： end>： ond> ； end> ： end>： end>!ond> ； end>1U