1、實訓報告書實訓名稱：系 < 部） ：專業班級 ：學生姓名 ：學號：指導教師：完成日期：山東科技大學泰山科技學院實訓課題實訓人姓名同組人員實訓日期至實訓成績指導 教師 評語指導教師簽名：年月日目錄一關聯算法簡介 31.1 相關概念 31.2 Apriori 算法思想 41.3 Apriori 算法的典型改進 4二. 關聯算法的基本原理 5三. 關聯算法的C+簡單實現53.1算法數據：53.2算法步驟： 63.3 C+算法的簡單實現63.4程序輸出結果： 15四. 學習心得體會 16數據挖掘 Apriori 算法報告一關聯算法簡介關規則數據挖掘是重要的一種數據挖掘方法 ,它的關鍵環節是尋找頻

2、繁項集 .近幾年許 多數據挖掘領域的研究人員投入了大量的時間和精力,深入研究了關聯規則的算法 ,其中Agrawal 等人于 1993 年提出的 Apriori 算法就是其中最具代表的成果 ,隨后眾多學者又在此 基礎上提出了一些改進 ,目的在于提高算法的效率 , 從而改進數據挖掘的效率 .這方面的研究 是目前數據挖掘領域研究的熱點之一 .1.1 相關概念所謂關聯規則挖掘就是從事務數據庫、關系數據庫或數據倉庫等海量數據的項集之間發現有價值的頻繁出現的模式關聯和相關性 .通過預先設定的支持度和可信度 ,通過特定的數應用到實際工作中 ,真正實現從數據到信息、再到知識的遷移過程.關聯規則數據挖掘的過程大

3、體為兩步 :第一步是從全部項集中尋找出所有頻繁項集。第二步是由頻繁項集獲取關聯規 則 .因為第二步較為容易和直觀 ,所以第一步是關聯規則挖掘的核心步驟.目前大多數尋找頻繁項集算法因需要大量候選集而效率不高 .在關聯規則挖掘的方法中, 最經典的算法是APriroi 算法 ,除此之外還有基于充分挖掘增量事務的關聯規則更新算法、Patition 算法、完全頻繁項集挖掘、頻繁閉項集挖掘、最大頻繁項集挖掘算法以及一些新的頻繁項集挖掘算 法.1.2 Apriori 算法思想Apriori 算法是一種最有影響的挖掘布爾關聯規則頻繁項集的算法，是 Agrawal 等人于 1993 年提出的一種寬度優先算法 .

4、算法的核心是使用候選項集找頻繁項集。算法思想如下： 首先掃描數據集中所有事務 ,統計每個項出現的次數，刪除小于預先設定的支持度的項集， 得到頻 繁 12 項集；利用頻繁 12 項集合的連接，產生候選 22 項集合 (Candi2date22itemset> 。然后對其中每個候選項集的支持計數，得到頻繁項集22 項集的集合，并利用這些頻繁 22 項集合的連接，得到候選 32 項集合。重復掃描數據庫產生更高層 次的頻繁項集合，再連接產生下一級候選項集,直到窮盡數據集中的所有頻繁項集。1.3 Apriori 算法的典型改進Apriori 算法能夠有效地產生關聯規則 ,但存在算法效率不高的缺陷，

5、因為Apriori 算法存在兩個比較明顯的缺點：一個是可能產生大量的候選集，另一個是需要重復掃描數據庫 . 因此如果挖掘數據倉庫數據量很大，應用此算法每次迭代產生候選項集用來統計其支持度 需要花費很多時間。為了提高算法的效率,國內外專家學者提出的一系列改進算法主要從減少掃描數據庫的次數和減少生成候選項目集的數目方面進行優化。從近幾年頻繁項集挖掘 算法的研究趨勢來看 ,為了提高算法的效率，提出了一系列的混合搜索策略和高效剪枝策 略。當數據集中所包含的項目個數比較多時，馬占欣,陸玉昌提出只有恰當地設置 2 個額外參數，才能夠保證挖掘過程的正常進行，但這樣做的代價是可能會遺漏部分包含更多負項 目的關

6、聯規則。二. 關聯算法的基本原理該算法的基本思想是：首先找出所有的頻集，這些項集出現的頻繁性至少和預定義的最小支持度一樣。然后由頻集產生強關聯規則，這些規則必須滿足最小支持度和最小可信 度。然后使用第 1步找到的頻集產生期望的規則，產生只包含集合的項的所有規則，其中 每一條規則的右部只有一項，這里采用的是中規則的定義。一旦這些規則被生成，那么只 有那些大于用戶給定的最小可信度的規則才被留下來。為了生成所有頻集，使用了遞推的方法<1 )L1=find_frequent_1-itemsets(D> 。挖掘頻繁1-項集，比較容易<2)for(k=2。Lk-1工。k+><

7、3)Ck=apriori_ge n( Lk-1,min_sup>。/調用 apriori_ge n方法生成候選頻繁k-項集<4)for eachtran sact iont D / 掃描事務數據庫D<5)Ct=subset(Ck,t>。<6)foreachcan didatecCt<7)c.co un t+。/統計候選頻繁k- 項集的計數<8)<9 )Lk=c Ck|c.co unt> min_sup滿足最小支持度的k-項集即為頻繁k-項集<10)<11) return L= U k Lk。/ 合并頻繁 k-項集 <k&g

8、t;0 )三. 關聯算法的C+簡單實現3.1算法數據：對給定數據集用Apriori算法進行挖掘，找出其中的頻繁集并生成關聯規則。對下面數據集進行挖掘：13 14對于數據集，取最小支持度minsup=2，最小置信度 minconf=0.83.2算法步驟: 首先單趟掃描數據集，計算各個一項集的支持度，根據給定的最小支持度閔值，得到一 項頻繁集L1。 然后通過連接運算，得到二項候選集，對每個候選集再次掃描數據集，得出每個候選集的支持度，再與最小支持度比較。得到二項頻繁集L2。 如此進行下去，直到不能連接產生新的候選集為止。 對于找到的所有頻繁集，用規則提取算法進行關聯規則的提取。3.3 C+算法的簡

9、單實現 首先要在項目名文件夾里自己定義date.txt文檔存放數據，然后在main函數中用FILE* fp=fope n("date.txt","r">。將數據導入算法。 定義int countL110。找到各一維頻繁子集出現的次數。 定義char curL1202。實現出現的一維子集。4維來放數據。因為給出的數據最多有 4個數，所以同樣的我們要定義到 int coun tL210。/各二維頻繁子集出現的次數char curL2203。/ 出現的二維子集int coun tL310。/各三維頻繁子集出現的次數char curL3204。/出現的三維

10、子集char cur504。得到字符串的長度。實現代碼如下: 定義 int SizeStr(char* m> int SizeStr(char* m> int i=0。while(*(m+i>!=0> i+。return i 比較兩個字符串，如果相等返回true,否則返回false bool 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> r

11、eturn true 。 return false 。 通過 void LoadItemL1(char *p>得到所有 1 元的字串和各自出現的次數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 。

12、j<4 。 j+>ch=*(*(p+i>+j> 。 if(ch=0> break 。curn0=ch 。 n+。curL100=cur00curL101=cur01k=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

13、。j+>char* m 。m=curL1i 。if(*m=0>break 。if(OpD(m,curj>>countL1i+ 。printf("L1: n ">。printf(" 項集 支持度計數 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 元子串v

14、oid 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 。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。

15、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 元頻繁子串出現的次數 void LoadItemL2(char *p>int k,i,j 。char* s 。int f 。SubItem2(p> 。 curL200=cur00。curL201=cur01。curL202=cur0

16、2。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+ 。 p

17、rintf("L2: n">。printf(" 項集支持度計數 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 。 int n=0 。 mem

18、set(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+> h+>for(h=j+

19、1 。 h<SizeStr(s> if(*(s+h>=0> break 。*(curn+0>=*(s+i>*(curn+1>=*(s+j>*(curn+2>=*(s+h>*(curn+3>=0 。 n+。3 元頻繁子串出現的次數同樣我們要得到得到各個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 。

20、i<50 。 i+>if(curi=0>break 。 s=curi 。 f=1 。for(j=0 。j<=k。j+>if(0pD(s,curL3j>>f=0。break。if(f=1>+k。curL3k0=curi0。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>>coun tL3i+。prin tf("L3:

21、n">。printf("項集支持度計數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,coun tL3i>。定義void LoadltemL4(char* p>得到各個 3元子串出現的次數void LoadltemL4(char* p>int i 。char* s 。int j=0。for(i=0 。 i<10 。 i+

22、>s=*(p+i> 。if(SizeStr(s>=4>j+。printf("四維子集出現的次數：dn",j>。prin tf("沒有四維的頻繁子集，算法結束！ n"> 。錯誤！通過void Support(char* w,int g>得到關聯規則，并輸出結果void Support(char* w,i nt g>int i,j,k, n=0。char* s 。float c=0.8,d=0。memset(cur,0,sizeof(cur>> s=w。for(i=0 。 i<SizeStr(

23、s> 。 i+>*(cur n+0>=*(s+i>。*(cur n+1>=0。*(cur n+2>=0。*(cur n+3>=0。n+ofor(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+ofor(i=0 。 i<10。 i+>if(Siz

24、eStr(curi>=1>for(j=0 。j<10。j+>nif(OpD(curi,curL1j>>d=cou ntL3g/(float>cou ntL1j if(d>=c>prin tf("l%s:%f",curL1i,d>。break。 |if(SizeStr(curi>=2>for(j=0 。j<10。j+>if(0pD(curi,curL2j>>d=cou ntL3g/(float>cou ntL2j。if(d>=c>prin tf("l%c

25、,l%c:%fn",curL2j0,curL2j1,d>。break。錯誤！最后通過main函數完成整過程序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>continu