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

1、實訓(xùn)報告書實訓(xùn)名稱： 系 （部）：專業(yè)班級：學(xué)生姓名：學(xué) 號：指導(dǎo)教師：完成日期：山東科技大學(xué)泰山科技學(xué)院實訓(xùn)課題實訓(xùn)人姓名同組人員實訓(xùn)日期至實訓(xùn)成績指導(dǎo)教師評語指導(dǎo)教師簽名：年月日目錄一關(guān)聯(lián)算法簡介 4.1.1 相關(guān)概念 4.1.2 Apriori 算法思想 4.1.3 Apriori 算法的典型改進(jìn) 5.二. 關(guān)聯(lián)算法的基本原理 5.三. 關(guān)聯(lián)算法的C+簡單實現(xiàn) .6.3.1算法數(shù)據(jù)： 6.3.2算法步驟： 6.3.3 C+算法的簡單實現(xiàn)7.3.4 程序輸出結(jié)果： 1.6四. 學(xué)習(xí)心得體會 1.6.17 / 17數(shù)據(jù)挖掘 Apriori 算法報告一關(guān)聯(lián)算法簡介關(guān)規(guī)則數(shù)據(jù)挖掘是重要的一種數(shù)據(jù)

2、挖掘方法,它的關(guān)鍵環(huán)節(jié)是尋找頻繁項集 .近幾年許多數(shù)據(jù)挖掘領(lǐng)域的研究人員投入了大量的時間和精力,深入研究了關(guān)聯(lián)規(guī)則的算法,其中Agrawal 等人于 1993 年提出的 Apriori 算法就是其中最具代表的成果 ,隨后眾多學(xué)者又在此基 礎(chǔ)上提出了一些改進(jìn) ,目的在于提高算法的效率 ,從而改進(jìn)數(shù)據(jù)挖掘的效率 . 這方面的研究是 目前數(shù)據(jù)挖掘領(lǐng)域研究的熱點之一 .1.1 相關(guān)概念所謂關(guān)聯(lián)規(guī)則挖掘就是從事務(wù)數(shù)據(jù)庫、關(guān)系數(shù)據(jù)庫或數(shù)據(jù)倉庫等海量數(shù)據(jù)的項集之間 發(fā)現(xiàn)有價值的頻繁出現(xiàn)的模式關(guān)聯(lián)和相關(guān)性.通過預(yù)先設(shè)定的支持度和可信度 ,通過特定的數(shù)據(jù)挖掘算法獲得支持度和可信度均較高的關(guān)聯(lián)規(guī)則,得到用戶感興趣

3、、有價值的關(guān)聯(lián)規(guī)則并應(yīng)用到實際工作中 ,真正實現(xiàn)從數(shù)據(jù)到信息、再到知識的遷移過程.關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘的過程大體為兩步 :第一步是從全部項集中尋找出所有頻繁項集;第二步是由頻繁項集獲取關(guān)聯(lián)規(guī)則 .由于第二步較為容易和直觀 ,所以第一步是關(guān)聯(lián)規(guī)則挖掘的核心步驟.目前大多數(shù)尋找頻繁項集算法因需要大量候選集而效率不高 .在關(guān)聯(lián)規(guī)則挖掘的方法中, 最經(jīng)典的算法是APriroi 算法 ,除此之外還有基于充分挖掘增量事務(wù)的關(guān)聯(lián)規(guī)則更新算法、 Patition 算法、 完全 頻繁項集挖掘、頻繁閉項集挖掘、最大頻繁項集挖掘算法以及一些新的頻繁項集挖掘算法 .1.2 Apriori 算法思想Apriori 算法是一

4、種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法，是 Agrawal 等人于 1993 年提出的一種寬度優(yōu)先算法 .算法的核心是使用候選項集找頻繁項集。算法思想如下： 首先掃描數(shù)據(jù)集中所有事務(wù) ,統(tǒng)計每個項出現(xiàn)的次數(shù)，刪除小于預(yù)先設(shè)定的支持度的項集， 得到頻繁 12 項集；利用頻繁 12 項集合的連接，產(chǎn)生候選 22 項集合 (Candi2date22itemset) 。 然后對其中每個候選項集的支持計數(shù)，得到頻繁項集 22 項集的集合，并利用這些頻繁 22 項集合的連接，得到候選 32 項集合。重復(fù)掃描數(shù)據(jù)庫產(chǎn)生更高層次的頻繁項集合，再連接產(chǎn)生下一級候選項集 ,直到窮盡數(shù)據(jù)集中的所有頻繁項集1.3

5、 Apriori 算法的典型改進(jìn)Apriori 算法能夠有效地產(chǎn)生關(guān)聯(lián)規(guī)則 ,但存在算法效率不高的缺陷，因為Apriori 算法存在兩個比較明顯的缺點：一個是可能產(chǎn)生大量的候選集，另一個是需要重復(fù)掃描數(shù)據(jù)庫 因此如果挖掘數(shù)據(jù)倉庫數(shù)據(jù)量很大， 應(yīng)用此算法每次迭代產(chǎn)生候選項集用來統(tǒng)計其支持度需 要花費很多時間。為了提高算法的效率,國內(nèi)外專家學(xué)者提出的一系列改進(jìn)算法主要從減少掃描數(shù)據(jù)庫的次數(shù)和減少生成候選項目集的數(shù)目方面進(jìn)行優(yōu)化。 從近幾年頻繁項集挖掘算法 的研究趨勢來看 ,為了提高算法的效率，提出了一系列的混合搜索策略和高效剪枝策略。當(dāng) 數(shù)據(jù)集中所包含的項目個數(shù)比較多時，馬占欣,陸玉昌提出只有恰當(dāng)

6、地設(shè)置 2 個額外參數(shù)，才能夠保證挖掘過程的正常進(jìn)行， 但這樣做的代價是可能會遺漏部分包含更多負(fù)項目的關(guān)聯(lián) 規(guī)則。二. 關(guān)聯(lián)算法的基本原理該算法的基本思想是：首先找出所有的頻集，這些項集出現(xiàn)的頻繁性至少和預(yù)定義的 最小支持度一樣。 然后由頻集產(chǎn)生強關(guān)聯(lián)規(guī)則， 這些規(guī)則必須滿足最小支持度和最小可信度。 然后使用第 1 步找到的頻集產(chǎn)生期望的規(guī)則， 產(chǎn)生只包含集合的項的所有規(guī)則， 其中每一條 規(guī)則的右部只有一項， 這里采用的是中規(guī)則的定義。 一旦這些規(guī)則被生成， 那么只有那些大 于用戶給定的最小可信度的規(guī)則才被留下來。為了生成所有頻集，使用了遞推的方法1) L1 = find_frequent_1

7、-itemsets(D);/ 挖掘頻繁 1-項集，比較容易(2) for (k=2;Lk- 1 工；k+) (3) Ck =即riori_gen(Lk-1 ,min_sup); / 調(diào)用 apriori_gen 方法生成候選頻繁k-項集(4) for each transaction t D / 掃描事務(wù)數(shù)據(jù)庫D5) Ct = subset(Ck,t);6) for each candidate c Ct(7) c.count+;/統(tǒng)計候選頻繁k-項集的計數(shù)8)(9) Lk =c Ck|c.count > min_sup /滿足最小支持度的k-項集即為頻繁 k-項集10) (11) re

8、turn L= U k Lk;/ 合并頻繁 k-項集(k>0)三. 關(guān)聯(lián)算法的C+簡單實現(xiàn)3.1算法數(shù)據(jù)：對下面數(shù)對給定數(shù)據(jù)集用Apriori算法進(jìn)行挖掘，找出其中的頻繁集并生成關(guān)聯(lián)規(guī)則。據(jù)集進(jìn)行挖掘：對于數(shù)據(jù)集，取最小支持度minsup=2，最小置信度 minconf=0.8。3.2算法步驟: 首先單趟掃描數(shù)據(jù)集，計算各個一項集的支持度，根據(jù)給定的最小支持度閔值，得到 一項頻繁集L1。 然后通過連接運算，得到二項候選集，對每個候選集再次掃描數(shù)據(jù)集，得出每個候選集的支持度，再與最小支持度比較。得到二項頻繁集L2。 如此進(jìn)行下去，直到不能連接產(chǎn)生新的候選集為止。 對于找到的所有頻繁集，用規(guī)

9、則提取算法進(jìn)行關(guān)聯(lián)規(guī)則的提取。3.3 C+ 算法的簡單實現(xiàn)首先要在工程名文件夾里自己定義 date.txt 文檔存放數(shù)據(jù)，然后在 main 函數(shù)中用FILE* fp=fopen("date.txt","r");將數(shù)據(jù)導(dǎo)入算法。定義 int countL110; 定義 char curL1202; 由于給出的數(shù)據(jù)最多有 int countL210; / char curL2203; /找到各一維頻繁子集出現(xiàn)的次數(shù)。 實現(xiàn)出現(xiàn)的一維子集。4 個數(shù)，所以同樣的我們要定義到4 維來放數(shù)據(jù)。各二維頻繁子集出現(xiàn)的次數(shù) 出現(xiàn)的二維子集int countL310; /

10、char curL3204; /各三維頻繁子集出現(xiàn)的次數(shù)出現(xiàn)的三維子集char cur504;得到字符串的長度。實現(xiàn)代碼如下：定義 int SizeStr(char* m) int SizeStr(char* m)int i=0; while(*(m+i)!=0)i+; return i;比較兩個字符串，如果相等返回true,否則返回falsebool OpD(char* x,char* y)int i=0; if(SizeStr(x)=SizeStr(y)while(*(x+i)=*(y+i)i+; if(*(x+i)=0 && *(y+i)=0)return true;re

11、turn false;通過 void LoadItemL1(char *p) 得到所有 1 元的字串和各自出現(xiàn)的次數(shù) void LoadItemL1(char *p)int i,j,n=0,k=0;char ch;char* s;int f;memset(cur,0,sizeof(cur);for(i=0;i<20;i+)curL1i0=0;curL1i1=0;for(j=0;j<10;j+) countL1j=0;for(i=0;i<10;i+) for(j=0;j<4;j+) ch=*(*(p+i)+j);if(ch=0)break;curn0=ch;n+;curL

12、100=cur00;curL101=cur01;k=0;for(i=0;i<50;i+)if(curi=0)break;s=curi;f=1;for(j=0;j<=k;j+)if(OpD(s,curL1j)f=0; break;if(f=1)+k;curL1k0=curi0;curL1k1=curi1; for(i=0;i<20;i+)for(j=0;j<50;j+)char* m;m=curL1i;if(*m=0)break;if(OpD(m,curj) countL1i+;printf("L1: n ");printf(" 項集 支持度

13、計數(shù) n");for(i=0;i<10;i+)if(curL1i=0)break;if(countL1i>=2)printf("I%s: %dn",curL1i,countL1i);通過 void SubItem2(char *p) 得到所有的 2 元子串 void SubItem2(char *p)int i,j,k,n=0;char* s;memset(cur,0,sizeof(cur);for(i=0;i<20;i+)curL2i0=0;curL2i1=0;curL2i2=0;for(i=0;i<10;i+)countL2i=0;fo

14、r(k=0;k<10;k+)s=*(p+k);if(SizeStr(s)<2)continue;for(i=0;i<SizeStr(s);i+) for(j=i+1;j<SizeStr(s);j+) if(*(s+j)=0) break;*(curn+0)=*(s+i);*(curn+1)=*(s+j);*(curn+2)=0;*(curn+3)=0;n+;通過 void LoadItemL2(char *p)得到各個 2 元頻繁子串出現(xiàn)的次數(shù)void LoadItemL2(char *p)int k,i,j;char* s;int f;SubItem2(p);curL

15、200=cur00;curL201=cur01;curL202=cur02;k=0;for(i=0;i<50;i+)if(curi=0)break;s=curi;f=1;for(j=0;j<=k;j+)if(OpD(s,curL2j)f=0;break;if(f=1)+k;curL2k0=curi0;curL2k1=curi1;curL2k2=curi2;for(i=0;i<20;i+)for(j=0;j<50;j+)s=curL2i;if(*s=0)break;if(OpD(s,curj)countL2i+; printf("L2: n"); pr

16、intf(" 項集 支持度計數(shù) n"); for(i=0;i<10;i+)if(curL2i=0) break;if(countL2i>=2) printf("I%c,I%c: %dn",curL2i0,curL2i1,countL2i); 得到所有 3 元的子串通過定義 void SubItem3(char *p) void SubItem3(char *p)char *s;int i,j,h,m;int n=0;memset(cur,0,sizeof(cur);for(j=0;j<20;j+)curL3j0=0;curL3j1=0;

17、curL3j2=0;curL3j3=0;for(i=0;i<10;i+)countL3i=0;for(m=0;m<10;m+)s=*(p+m);if(SizeStr(s)<3)continue;for(i=0;i<SizeStr(s);i+)for(j=i+1;j<SizeStr(s);j+)for(h=j+1;h<SizeStr(s);h+)if(*(s+h)=0) break;*(curn+0)=*(s+i);*(curn+1)=*(s+j);*(curn+2)=*(s+h);*(curn+3)=0;n+;同樣我們要得到得到各個 3 元頻繁子串出現(xiàn)的次數(shù)

18、 void LoadItemL3(char* p)int k,i,j;char* s;int f;SubItem3(p);curL300=cur00;curL301=cur01;curL302=cur02;curL303=cur03;k=0;for(i=0;i<50;i+)if(curi=0)break;s=curi;f=1;for(j=0;j<=k;j+)if(OpD(s,curL3j)f=0;break;if(f=1)+k;curL3k0=curi0;curL3k1=curi1;curL3k2=curi2;curL3k3=curi3;for(i=0;i<20;i+)for

19、(j=0;j<50;j+)s=curL3i;if(*s=O) break;if(OpD(s,curj)coun tL3i+;prin tf("L3: n ”);printf("項集支持度計數(shù)n");for(i=0;i<10;i+)if(curL3i=0)break;if(cou ntL3i>=2)prin tf("l%c,l%c,l%c:%dn",curL3i0,curL3i1,curL3i2,countL3i);定義void LoadltemL4(char* p)得到各個3元子串出現(xiàn)的次數(shù)void LoadItemL4(ch

20、ar* p)int i;char* s;int j=0;for(i=0;i<10;i+)s=*(p+i);if(SizeStr(s)=4)j+;prin tf("四維子集出現(xiàn)的次數(shù)：%dn",j);prin tf("沒有四維的頻繁子集，算法結(jié)束！ n");得到關(guān)聯(lián)規(guī)則，并輸出結(jié)果 通過 void Support(char* w,int g)void Support(char* w,i nt g) float c=0.8,d=0; memset(cur,0,sizeof(cur); s=w;int i,j,k, n=0;char* s;for(i=0

21、;i<SizeStr(s);i+)*(cur n+0)=*(s+i);*(cur n+1)=0;*(cur n+2)=0;*(cur n+3)=0;n+;for(i=0;i<SizeStr(s);i+) for(j=i+1;j<SizeStr(s);j+) if(*(s+j)=0) break;*(cur n+0)=*(s+i);*(cur n+1)=*(s+j);*(cur n+2)=0;*(cur n+3)=0;n+;for(i=0;i<10;i+)if(SizeStr(curi)=1)for(j=0;j<10;j+)if(OpD(curi,curL1j)_d

22、=cou ntL3g/(float)cou ntL1j; if(d>=c)prin tf("l%s:%f",curL1i,d);break;for(j=0;j<10;j+)if(OpD(curi,curL2j)d=cou ntL3 g/(float)cou ntL2j;if(d>=c)prin tf("l%c,l%c:%fn",curL2j0,curL2j1,d);break;第最后通過main函數(shù)完成整過程序int main (i nt argc, char* argv)int i=O,j=O,k;char buf10 6;char* p10;char ch;memset(buf,0,sizeof(buf);FILE* fp=fope n("date.txt","r"); if(fp=NULL)return 0;ch=fgetc(fp);while(ch!=EOF)if(ch=0xa | ch=0xd)con ti nue;bufij=ch; j+; ch=fgetc(fp); for(k=0;k<10;k+)*(p+k)=bufk;LoadItemL1(p);LoadItemL2(p);LoadItemL3(p);LoadltemL4(p