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

1、 數(shù)據(jù)挖掘Apriori算法報告一關聯(lián)算法簡介關聯(lián)規(guī)則的目的在于在一個數(shù)據(jù)集中找出項之間的關系，也稱之為購物藍分析 (market basketanalysis)。例如，購買鞋的顧客，有10%的可能也會買襪子，60%的買面包的顧客，也會買牛奶。這其中最有名的例子就是"尿布和啤酒"的故事了。關聯(lián)規(guī)則的應用場合。在商業(yè)銷售上，關聯(lián)規(guī)則可用于交叉銷售，以得到更大的收入；在保險業(yè)務方面，如果出現(xiàn)了不常見的索賠要求組合，則可能為欺詐，需要作進一步的調查。在醫(yī)療方面，可找出可能的治療組合；在銀行方面，對顧客進行分析，可以推薦感興趣的服務等等。Apriori algorithm是關聯(lián)規(guī)則

2、里一項基本算法。由Rakesh Agrawal 在 1994年提出的，詳細的介紹請猛擊這里Fast Algorithms for Mining Association Rules。二.關聯(lián)算法的基本原理 該算法的基本思想是：首先找出所有的頻集，這些項集出現(xiàn)的頻繁性至少和預定義的最小支持度一樣。然后由頻集產(chǎn)生強關聯(lián)規(guī)則，這些規(guī)則必須滿足最小支持度和最小可信度。然后使用第1步找到的頻集產(chǎn)生期望的規(guī)則，產(chǎn)生只包含集合的項的所有規(guī)則，其中每一條規(guī)則的右部只有一項，這里采用的是中規(guī)則的定義。一旦這些規(guī)則被生成，那么只有那些大于用戶給定的最小可信度的規(guī)則才被留下來。為了生成所有頻集，使用了遞推的方法（1）

3、L1 = find_frequent_1-itemsets(D); / 挖掘頻繁1-項集，比較容易（2）for (k=2;Lk-1 ;k+) （3）Ck = apriori_gen(Lk-1 ,min_sup); / 調用apriori_gen方法生成候選頻繁k-項集（4）for each transaction t D      / 掃描事務數(shù)據(jù)庫D（5）Ct = subset(Ck,t);（6）for each candidate c Ct（7）c.count+; /   統(tǒng)計候選頻繁k-項集的計數(shù)（8）（9）Lk =c

4、 Ck|c.countmin_sup / 滿足最小支持度的k-項集即為頻繁k-項集（10） （11） return L= k Lk; / 合并頻繁k-項集（k>0）三.關聯(lián)算法的C+簡單實現(xiàn)（1）算法數(shù)據(jù)：對給定數(shù)據(jù)集用Apriori算法進行挖掘，找出其中的頻繁集并生成關聯(lián)規(guī)則。對下面數(shù)據(jù)集進行挖掘：I1 I2 I5I1 I2I2 I4I1 I2 I4I1 I3I1 I2 I3 I5I1 I2 I3I2 I5I2 I3 I4I3 I4對于數(shù)據(jù)集，取最小支持度minsup=2，最小置信度minconf=0.8。（2）算法步驟： 首先單趟掃描數(shù)據(jù)集，計算各個一項集的支持度，根據(jù)給定的最小支持

5、度閔值，得到一項頻繁集L1。 然后通過連接運算，得到二項候選集，對每個候選集再次掃描數(shù)據(jù)集，得出每個候選集的支持度，再與最小支持度比較。得到二項頻繁集L2。 如此進行下去，直到不能連接產(chǎn)生新的候選集為止。 對于找到的所有頻繁集，用規(guī)則提取算法進行關聯(lián)規(guī)則的提取。（3）C+算法的簡單實現(xiàn) 首先要在工程名文件夾里自己定義date.txt文檔存放數(shù)據(jù)，然后在main函數(shù)中用FILE* fp=fopen("date.txt","r");將數(shù)據(jù)導入算法。 定義int countL110;找到各一維頻繁子集出現(xiàn)的次數(shù)。定義char curL1202;實現(xiàn)出現(xiàn)的一維子

6、集。由于給出的數(shù)據(jù)最多有4個數(shù)，所以同樣的我們要定義到4維來放數(shù)據(jù)。int countL210; /各二維頻繁子集出現(xiàn)的次數(shù)char curL2203; /出現(xiàn)的二維子集int countL310; /各三維頻繁子集出現(xiàn)的次數(shù)char curL3204; /出現(xiàn)的三維子集char cur504; 定義int SizeStr(char* m) 得到字符串的長度。實現(xiàn)代碼如下： int SizeStr(char* m)int i=0;while(*(m+i)!=0)i+;return i;比較兩個字符串，如果相等返回true,否則返回false bool OpD(char* x,char* y)i

7、nt i=0;if(SizeStr(x)=SizeStr(y)while(*(x+i)=*(y+i)i+;if(*(x+i)=0 && *(y+i)=0)return true;return 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+)

8、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+;curL100=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=cu

9、rL1i;if(*m=0)break;if(OpD(m,curj)countL1i+;printf("L1: n ");printf("項集 支持度計數(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(c

10、ur);for(i=0;i<20;i+)curL2i0=0;curL2i1=0;curL2i2=0;for(i=0;i<10;i+)countL2i=0;for(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)

11、 得到各個2元頻繁子串出現(xiàn)的次數(shù) void LoadItemL2(char *p)int k,i,j;char* s;int f;SubItem2(p);curL200=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

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

13、nt n=0;memset(cur,0,sizeof(cur);for(j=0;j<20;j+)curL3j0=0;curL3j1=0;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);*(c

14、urn+1)=*(s+j);*(curn+2)=*(s+h);*(curn+3)=0;n+;同樣我們要得到得到各個3元頻繁子串出現(xiàn)的次數(shù) 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=cu

15、ri0;curL3k1=curi1;curL3k2=curi2;curL3k3=curi3;for(i=0;i<20;i+)for(j=0;j<50;j+)s=curL3i;if(*s=0)break;if(OpD(s,curj)countL3i+;printf("L3: n");printf("項集 支持度計數(shù)n");for(i=0;i<10;i+)if(curL3i=0)break;if(countL3i>=2)printf("I%c,I%c,I%c: %dn",curL3i0,curL3i1,curL3i

16、2,countL3i);定義void LoadItemL4(char* p) 得到各個3元子串出現(xiàn)的次數(shù) void LoadItemL4(char* p)int i;char* s;int j=0;for(i=0;i<10;i+)s=*(p+i);if(SizeStr(s)=4)j+;printf("四維子集出現(xiàn)的次數(shù): %dn",j);printf("沒有四維的頻繁子集，算法結束! n");通過void Support(char* w,int g) 得到關聯(lián)規(guī)則，并輸出結果 void Support(char* w,int g)int i,j,k

17、,n=0;char* s;float c=0.8,d=0;memset(cur,0,sizeof(cur);s=w;for(i=0;i<SizeStr(s);i+)*(curn+0)=*(s+i);*(curn+1)=0;*(curn+2)=0;*(curn+3)=0;n+;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+;for(i=0;i<10;i+)if(Si

18、zeStr(curi)=1)for(j=0;j<10;j+)if(OpD(curi,curL1j)d=countL3g/(float)countL1j;if(d>=c)printf("I%s: %f",curL1i,d);break;if(SizeStr(curi)=2)for(j=0;j<10;j+)if(OpD(curi,curL2j)d=countL3g/(float)countL2j;if(d>=c)printf("I%c,I%c: %f n",curL2j0,curL2j1,d);break;最后通過main函數(shù)完成整過程序 int main(int argc, char* argv)int i=0,j=0,k;char buf106;char* p10;char ch;memset(buf,0,sizeof(buf);FILE* fp=fopen("date.txt","r");if(fp=NULL)return 0;ch=fgetc(fp);while(ch!=EOF)if(ch=0xa | ch=0xd)i+;ch=fgetc(fp);j=0;continue;bufij=ch;j+;ch=fgetc(fp);for(k