數(shù)據(jù)挖掘Apriori算法復習進程

1、數(shù)據(jù)挖掘 Apr i or i算法精品文檔實驗報告實驗課程名稱：數(shù)據(jù)挖掘實驗項目名稱：Apriori算法理 學 院實驗時間：2014 年 11 月11日收集于網(wǎng)絡，如有侵權請聯(lián)系管理員刪除精品文檔學生所在學院：理學院專業(yè)： 統(tǒng)計學班級：姓學號實驗名組實驗時間指導教成師績實驗項目名Apriori算法稱實驗目的及要求 ：1. 加強對 Apriori 算法的理解2. 鍛煉分析問題、解決問題以及動手能力3. 編程實現(xiàn) Apriori 算法實驗（或算法）原理 ：Apriori算法是一種找頻繁項目集的基本算法。其基本原理是逐層搜索的迭代：頻繁K 項 Lk 集用于搜索頻繁 (K+1) 項集 Lk+1，如此下

2、去，直到不能找到維度更高的頻繁項集為止。這種方法依賴連接和剪枝這兩步來實現(xiàn)。算法的第一次遍歷僅僅計算每個項目的具體值的數(shù)量，以確定大型l 項集。隨后的遍歷，第 k 次遍歷，包括兩個階段。首先，使用在第 (k-1) 次遍歷中找到的大項集 Lk-1 和用 Aprioir-gen 函數(shù)產生候選項集 Ck。接著掃描數(shù)據(jù)庫，計算 Ck 中候選的支持度。用 Hash樹可以有效地確定 Ck 中包含在一個給定的事務 t 中的候選。算法如下：(1) L1 = 大項目集 1 項目集 ;(2)for(k = 2;Lk-1!=空;k+)dobegin(3)Ck= apriori-gen(Lk-1);/ 新的候選集(4

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

4、ntoCk收集于網(wǎng)絡，如有侵權請聯(lián)系管理員刪除精品文檔(2)selectp1，p2 ， ， pk-1，qk-1(3)fromLk-1p ，Lk-1q(4)wherep1= q1 ， ， pk-2= qk-2， pk-1< qk-接著，在 Prune( 修剪 ) 步驟，我們將刪除所有的項目集cCk，如果 c 的一些 k-1 子集不在 Lk-1 中，為了說明這個產生過程為什么能保持完全性，要注意對于Lk 中的任何有最小支持度的項目集，任何大小為k-1 的子集也必須有最小支持度。因此，如果我們用所有可能的項目擴充 Lk-1中的每個項目集，然后刪除所有k-1 子集不在 Lk-1中的項目集，那么我

5、們就能得到Lk 中項目集的一個超集。上面的合并運算相當于用數(shù)據(jù)庫中所有項目來擴展Lk-1 ；如果刪除擴展項目集的第k-1 個項目后得到的 k-1 項目集不在 Lk-1 中，則刪除該擴展項目集。條件pk-1< qk-1 保證不會出現(xiàn)相同的擴展項。因此，經過合并運算，Ck>Lk。類似原因在刪除運算中，刪除Ck中其 k-1子項目集不在 Lk-1中的項目集，同樣沒有刪除包含在 Lk 中的項目集。(1)for所有項目集 c Ckdo(2)for所有 c 的 (k-1)子集 sdo(3) if(s Lk-1)then(4) 從 Ck中刪除 c例如： L3 為123 ，124 ，13 4 ，13

6、 5，2 34 。 Jion 步驟之后， C4為 123 4 ，13 45 。Prune 步驟將刪除項集1 3 4 5 ，因為項集 14 5不在 L3中。Subset 函數(shù)：候選項目集 Ck 存儲在一棵 Hash樹中。 Hash 樹的一個節(jié)點包含了項集的一個鏈表 ( 一個葉節(jié)點 ) 或包含了一個 Hash表 ( 一個內節(jié)點 ) 。在內節(jié)點中， Hash 表的每個 Bucket 都指向另一個節(jié)點。 Hash 樹的根的深度定義為 1。在深度 d 的一個內節(jié)點指向深度 d+1 的節(jié)點。項目集存儲在葉子中。要加載一個項目集 c 時，從根開始向下直到一個葉子。在深度為 d 的一個內節(jié)點上，要決定選取哪個

7、分枝，可以對此項目集的第 d 個項目使用一個 Hash函數(shù)，然后跟隨相應 Bucket 中的指針。所有的節(jié)點最初都創(chuàng)建成葉節(jié)點。當一個葉節(jié)點中項集數(shù)量超過某個指定的閾值時，此葉節(jié)點就轉為一個內節(jié)點。從根節(jié)點開始， Subset 函數(shù)尋找所有包含在某個事務 t 中的候選，方法如下：若處于一個葉子，就尋找此葉子中的哪些項目集是包括在 t 中的，并對它們附加引用指向答案集合。若處于一個內節(jié)點，而且是通過 Hash項目 i 從而到達此節(jié)點的，那么就對 t中 i 之后的每個項目進行 Hash，并對相應 Bucket 中的節(jié)點遞歸地應用這個過程。對于根節(jié)點，就對 t 中的每個項目進行 Hash。盡管 Ap

8、riori算法已經可以壓縮候選數(shù)據(jù)項集Ck，但是對于頻繁項集尤其是2 維的候選數(shù)據(jù)項集產生仍然需要大量的存儲空間。也就是說對于 2 維的候選數(shù)據(jù)項集， Apriori 算法的剪枝操作幾乎不起任何作用。例如： 1 維高頻數(shù)據(jù)項集 L1 的規(guī)模是O(n) ，則 2 維候選數(shù)據(jù)項集的規(guī)模將達到 O(n2) 。如果我們考慮一般情況，即在沒有支持度的情況下 1 維高頻數(shù)據(jù)項集 L1 的規(guī)模是 103，則 2 維候選數(shù)據(jù)項集的規(guī)模 C2 將達到 C10005×105這種空間復雜度以指數(shù)形式的增長，使得這個經典的算法的執(zhí)行效率很難讓人滿意 Apriori 算法的兩大缺點就是產生大量的候選集，以及需

9、重復掃描數(shù)據(jù)庫。收集于網(wǎng)絡，如有侵權請聯(lián)系管理員刪除精品文檔實驗硬件及軟件平臺：Windows7、Visual C+ 6.0收集于網(wǎng)絡，如有侵權請聯(lián)系管理員刪除精品文檔實驗內容（包括實驗具體內容、算法分析、源代碼等等）：#include<iostream>#include<string>#include <vector>#include <map>#include <algorithm>using namespace std;class Aprioripublic:Apriori(size_t is =0,unsigned int m

10、v=0)item_size = is;min_value = mv;/Apriori() ;void getItem();map< vector<string>,unsigned int> find_freitem();/求事務的頻繁項/連接連個 k-1 級頻繁項，得到第k 級頻繁項map< vector<string>,unsigned int > apri_gen(unsigned int K , map< vector<string>,unsigned int > K_item);/展示頻繁項集void showAp

11、rioriItem(unsigned int K,map< vector<string>,unsigned int > showmap); private:map< int , vector<string> > item;/存儲所有最開始的事務及其項 map< vector<string>,unsigned int > K_item;/存儲頻繁項集 size_t item_size;/事務數(shù)目unsigned int min_value;/最小閾值;void Apriori:getItem()/ 用戶輸入最初的事務集int

12、 ci = item_size;for (int i=0;i<ci;i+)string str;vector<string> temp;cout<<"請輸入第 "<<i+1<<" 個事務的項集 (wang end)：" while (cin>>str && str !="wang")temp.push_back(str);sort(temp.begin(),temp.end();pair< map<int ,vector<string&

13、gt; >:iterator , bool> ret = item.insert(make_pair(i+1 ,temp);if (!ret.second)收集于網(wǎng)絡，如有侵權請聯(lián)系管理員刪除精品文檔-i;cout<<"你輸入的元素已存在！請重新輸入！"<<endl;cout<<"- 運行結果如下： -"<<endl;map< vector<string>,unsigned int> Apriori:find_freitem()unsigned int i = 1;boo

14、l isEmpty = false;map< int , vector<string> >:iterator mit ;for (mit=item.begin();mit != item.end();mit+)vector<string> vec = mit->second;if (vec.size() != 0)break;if (mit = item.end()/ 事務集為空isEmpty = true;cout<<"事務集為空！程序無法進行."<<endl;map< vector<strin

15、g>,unsigned 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;/判斷是否需要進行下一次的尋找map< vector<string>,unsigned int > pre_K_item = K_item; size_t Kitemsize = K_item.si

16、ze();/存儲應該刪除的第 K 級頻繁項集，不能和其他 K 級頻繁項集構成第 K+1 級項集的集合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.begin() , pre_K_item_it2;while (pre_K_item_it

17、1 != pre_K_item.end() )收集于網(wǎng)絡，如有侵權請聯(lián)系管理員刪除精品文檔map< vector<string>,unsigned int >:iterator mit = pre_K_item_it1; 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<strin

18、g> vec2;vec2 = mit->first;vector<string> vec22(vec2.begin(),vec2.end()-1);if (vec11 = vec22)break;+mit;if (mit = pre_K_item.end()isExist = false;if (!isExist && pre_K_item_it1 != pre_K_item.end()eraseVecMit.push_back(pre_K_item_it1);/該第 K 級頻繁項應該刪除+pre_K_item_it1;size_t eraseSetSi

19、ze = eraseVecMit.size();if (eraseSetSize = Kitemsize)break;elsevector< map< vector<string>,unsigned int >:iterator >:iterator currentErs = eraseVecMit.begin();while (currentErs != eraseVecMit.end()/刪除所有應該刪除的第K 級頻繁項map< vector<string>,unsigned int >:iterator eraseMit = *

20、currentErs; K_item.erase(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 > K_item)收集于網(wǎng)絡，如有侵權請聯(lián)系管理員刪除精品文檔if (1 = K)/

21、 求候選集 C1size_t c1 = item_size;map< int , vector<string> >:iterator mapit = item.begin(); vector<string> vec;map<string,unsigned int> c1_itemtemp;while (mapit != item.end() )/ 將原事務中所有的單項統(tǒng)計出來vector<string> temp = mapit->second;vector<string>:iterator vecit = temp

22、.begin();while (vecit != temp.end() )pair< map<string,unsigned int>:iterator , bool > ret = c1_itemtemp.insert(make_pair(*vecit+ , 1);if (!ret.second)+ ret.first->second;+mapit;map<string,unsigned int>:iterator item_it = c1_itemtemp.begin(); map< vector<string>,unsigned

23、 int > c1_item;while (item_it != c1_itemtemp.end() )/ 構造第一級頻繁項集vector<string> temp;if ( item_it->second >= min_value)temp.push_back(item_it->first);c1_item.insert(make_pair(temp , item_it->second) );+item_it;return c1_item;elsecout<<endl;showAprioriItem(K-1,K_item);map<

24、 vector<string>,unsigned int >:iterator ck_item_it1 = K_item.begin(),ck_item_it2; map< vector<string>,unsigned int > ck_item; while (ck_item_it1 != K_item.end() )ck_item_it2 = ck_item_it1;+ck_item_it2;map< vector<string>,unsigned int >:iterator mit = ck_item_it2;收集于網(wǎng)

25、絡，如有侵權請聯(lián)系管理員刪除精品文檔/取當前第 K 級頻繁項與其后面的第K 級頻繁項集聯(lián)合，但要注意聯(lián)合條件/聯(lián)合條件：連個頻繁項的前 K-1 項完全相同，只是第 K 項不同，然后兩個聯(lián)合生成第 K+1 級候選頻繁項while(mit != K_item.end() )vector<string> vec,vec1,vec2;vec1 = ck_item_it1->first;vec2 = mit->first;vector<string>:iterator vit1,vit2;vit1 = vec1.begin();vit2 = vec2.begin();

26、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 != vec2.end() )vec.push_back(str1);elsebreak;if (vit1 = vec1.end() && vit2 = vec2.end() )-vit1;-vit2;string str1 =

27、*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> >:iterator base_item = item.begin(); unsigned int Acount = 0 ;while (base_item != item.end() )/統(tǒng)計該 K+1 級候選項在原事務集出現(xiàn)次數(shù)收集于網(wǎng)絡，如有侵權請聯(lián)系管理員刪除精

28、品文檔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+)string t = *vecit;count = 0;for (bvit=vv.begin();bvit < vv.end();bvit+)if (t = *bvit)count+;mincount = (co

29、unt < mincount ? count : mincount );if (mincount >=1 && mincount != UINT_MAX)Acount += mincount;+base_item;if (Acount >= min_value && Acount != 0)sort(vec.begin(),vec.end();/該第 K+1 級候選項為頻繁項，插入頻繁項集pair< map< vector<string>,unsigned int >:iterator , bool> ret

30、 = ck_item.insert(make_pair(vec,Acount);if (! ret.second)ret.first->second += Acount;+mit;+ck_item_it1;if (ck_item.empty()/ 該第 K+1 級頻繁項集為空，說明調用結束，把上一級頻繁項集返回return K_item;elsereturn ck_item;void Apriori:showAprioriItem(unsigned int K,map< vector<string>,unsigned int > showmap)map< v

31、ector<string>,unsigned int >:iterator showit = showmap.begin(); if (K != UINT_MAX)cout<<endl<<"第 "<<K<<" 級頻繁項集為： "<<endl;收集于網(wǎng)絡，如有侵權請聯(lián)系管理員刪除精品文檔elsecout<<"最終的頻繁項集為： "<<endl;cout<<"項 集"<<" t &qu

32、ot;<<" 頻率 "<<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 char * str)/對用戶輸入的數(shù)字進行判斷和轉換if (str = NULL)