上傳人：5***

認證信息

認證類型：個人認證

認證主體：李**（實名認證）

IP屬地：湖北

IP屬地：湖北 上傳時間：2021-08-14 格式：DOC 頁數(shù)：33 大小：306.50KB 積分：30 舉報 版權(quán)申訴

1、知識發(fā)現(xiàn)與數(shù)據(jù)挖掘?qū)嶒瀳蟾嫘彰簒xx專業(yè)：xxxxxx學(xué)號：xxxxx2013 年 8 月 15日實驗一、頻繁模式挖掘算法 Apriori算法一、實驗?zāi)康募訌妼priori算法的理解。二、實驗內(nèi)容編程實現(xiàn)Apriori算法，加深對其理解。三、實驗原理該算法的基本思想是：首先找出所有的頻繁項目集，這些項集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度一樣。然后由頻繁項目集產(chǎn)生的強關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿足最小支持度和最小可信度。然后使用第1步找到的頻繁項目集產(chǎn)生的期望的規(guī)則，產(chǎn)生只包含集合的項的所有規(guī)則，其中每一條規(guī)則的右部只有一項，這里采用的是中規(guī)則的定義。一旦這些規(guī)則被生成，那么只有那些大于用戶給

2、定的最小可信度的規(guī)則才被留下來。為了生成所有頻繁項目集，使用了遞推的方法。(一)、Apriori（發(fā)現(xiàn)頻繁項目集）輸入：數(shù)據(jù)集D；最小支持數(shù)minsup_count。輸出：頻繁項目集L。（1）L1=large 1-itemsets;/所有支持讀不小于minsupport的1-項目集（2）、FOR （k=2;Lk-1;k+） DO BEGIN（3）Ck = apriori-gen(Lk-1 ,min_sup);/Ck是k個元素的候選集（4）FOR all transaction t D DO BEGIN（5）Ct = subset(Ck,t);/Ct是所有t包含的候選集元素（6）FOR all

3、candidate c Ct DO c.count+;（7）END（8）Lk =c Ck|c.countminsup_count（9）END（10）L= k Lk;(二)、apriori-gen(Lk-1)（候選集產(chǎn)生）輸入：(k-1)-頻繁項目集Lk-1。輸出：k-候選項目集Ck。（1）FOR all itemset pLk-1 DO（2）FOR all itemset qLk-1 DO（3）IF p.item1=q.item1，p.item2=q.item2，p.itemk-2=q.itemk-2，p.itemk-1=q.itemk-1 THEN BEGIN（4）c=pq;（5）IF ha

4、s_infrequent_subset(c,Lk-1) THEN（6）delete c;（7）ELSE add c to Ck;（8）END（9）Return Ck;(三)、has_infrequent_subset(c,Lk-1)（候選集產(chǎn)生）輸入：一個k-候選項目集c,(k-1)-頻繁項目集Lk-1。輸出：c是否從候選集中刪除的布爾判斷。（1）FOR all (k-1)-subsets of c DO（2）IF S Lk-1 THEN Return TRUE；（3）Return FALSE;四、代碼實現(xiàn)（一）算法數(shù)據(jù)：對給定數(shù)據(jù)集用Apriori算法進行挖掘，找出其中的頻繁集并生成關(guān)聯(lián)規(guī)則

5、。對下面數(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。（二）算法步驟：（1）、首先單趟掃描數(shù)據(jù)集，計算各個一項集的支持度，根據(jù)給定的最小支持度閔值，得到一項頻繁集L1。（2）、然后通過連接運算，得到二項候選集，對每個候選集再次掃描數(shù)據(jù)集，得出每個候選集的支持度，再與最小支持度比較。得到二項頻繁集L2。（3）、如此進行下去，直到不能連接產(chǎn)生新的候選集為止。（4）、對于找到的所有頻繁集，用規(guī)則提取算法進行關(guān)聯(lián)規(guī)則的提取

6、。（三）C+算法的簡單實現(xiàn)（1）、首先要在工程名文件夾里自己定義date.txt文檔存放數(shù)據(jù)，然后在main函數(shù)中用FILE* fp=fopen(date.txt,r);將數(shù)據(jù)導(dǎo)入算法。（2）、定義int countL110;找到各一維頻繁子集出現(xiàn)的次數(shù)。定義char curL1202;實現(xiàn)出現(xiàn)的一維子集。由于給出的數(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;

7、（3）、定義int SizeStr(char* m) 得到字符串的長度。實現(xiàn)代碼如下：int SizeStr(char* m)int i=0;while(*(m+i)!=0)i+;return i;（4）、比較兩個字符串，如果相等返回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;return false;（5）、通過void LoadItemL1(char *p) 得到所有1元的字串和各

8、自出現(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;i20;i+)curL1i0=0;curL1i1=0;for(j=0;j10;j+)countL1j=0;for(i=0;i10;i+)for(j=0;j4;j+)ch=*(*(p+i)+j);if(ch=0)break;curn0=ch;n+;curL100=cur00;curL101=cur01;k=0;for(i=0;i50;i+)if(curi=0)break;s=curi;f=1;fo

9、r(j=0;j=k;j+)if(OpD(s,curL1j)f=0;break;if(f=1)+k;curL1k0=curi0;curL1k1=curi1;for(i=0;i20;i+)for(j=0;j50;j+)char* m;m=curL1i;if(*m=0)break;if(OpD(m,curj)countL1i+;printf(L1: n );printf(項集 支持度計數(shù)n);for(i=0;i=2)printf(I%s: %dn,curL1i,countL1i);（6）、通過void SubItem2(char *p) 得到所有的2元子串void SubItem2(char *p)

10、int i,j,k,n=0;char* s;memset(cur,0,sizeof(cur);for(i=0;i20;i+)curL2i0=0;curL2i1=0;curL2i2=0;for(i=0;i10;i+)countL2i=0;for(k=0;k10;k+)s=*(p+k);if(SizeStr(s)2)continue;for(i=0;iSizeStr(s);i+)for(j=i+1;jSizeStr(s);j+)if(*(s+j)=0)break;*(curn+0)=*(s+i);*(curn+1)=*(s+j);*(curn+2)=0;*(curn+3)=0;n+;（7）、通過v

11、oid LoadItemL2(char *p) 得到各個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;i50;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;i20;i+)for(j

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

13、3j2=0;curL3j3=0;for(i=0;i10;i+)countL3i=0;for(m=0;m10;m+)s=*(p+m);if(SizeStr(s)3)continue;for(i=0;iSizeStr(s);i+)for(j=i+1;jSizeStr(s);j+)for(h=j+1;hSizeStr(s);h+)if(*(s+h)=0)break;*(curn+0)=*(s+i);*(curn+1)=*(s+j);*(curn+2)=*(s+h);*(curn+3)=0;n+;（9）同樣我們要得到得到各個3元頻繁子串出現(xiàn)的次數(shù)void LoadItemL3(char* p)int

14、k,i,j;char* s;int f;SubItem3(p);curL300=cur00;curL301=cur01;curL302=cur02;curL303=cur03;k=0;for(i=0;i50;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;i20;i+)for(j=0;j50;j+)s=curL3i;if(*s=0)break;if(OpD

15、(s,curj)countL3i+;printf(L3: n);printf(項集 支持度計數(shù)n);for(i=0;i=2)printf(I%c,I%c,I%c: %dn,curL3i0,curL3i1,curL3i2,countL3i);（10）、定義void LoadItemL4(char* p) 得到各個3元子串出現(xiàn)的次數(shù)void LoadItemL4(char* p)int i;char* s;int j=0;for(i=0;i10;i+)s=*(p+i);if(SizeStr(s)=4)j+;printf(四維子集出現(xiàn)的次數(shù): %dn,j);printf(沒有四維的頻繁子集，算法結(jié)束

16、! n);（11）、通過void Support(char* w,int g) 得到關(guān)聯(lián)規(guī)則，并輸出結(jié)果void Support(char* w,int 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;iSizeStr(s);i+)*(curn+0)=*(s+i);*(curn+1)=0;*(curn+2)=0;*(curn+3)=0;n+;for(i=0;iSizeStr(s);i+)for(j=i+1;jSizeStr(s);j+)if(*(s+j)=0)break;*(curn+0)

17、=*(s+i);*(curn+1)=*(s+j);*(curn+2)=0;*(curn+3)=0;n+;for(i=0;i10;i+)if(SizeStr(curi)=1)for(j=0;j=c)printf(I%s: %f,curL1i,d);break;if(SizeStr(curi)=2)for(j=0;j=c)printf(I%c,I%c: %f n,curL2j0,curL2j1,d);break;（12）、最后通過main函數(shù)完成整過程序int main(int argc, char* argv)int i=0,j=0,k;char buf106;char* p10;char ch

18、;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=0;k10;k+)*(p+k)=bufk;LoadItemL1(p);LoadItemL2(p);LoadItemL3(p);LoadItemL4(p);printf(產(chǎn)生關(guān)聯(lián)規(guī)則: n);printf(非空子集: 置信度:n);for(i=

19、0;i=2)Support(curL3i,i);return 0;（四）程序輸出結(jié)果：實驗二 分類模型 1 Id3算法一、實驗?zāi)康耐ㄟ^實驗，加深數(shù)據(jù)挖掘中分類（決策樹）的認識，其經(jīng)典算法為Id3算法，了解影響Id3算法性能的因素，掌握基于Id3算法理論的分類分析的原理和方法。二、實驗內(nèi)容對一數(shù)據(jù)集用Id3算法做數(shù)據(jù)分類分析（預(yù)測），用java語言實現(xiàn)。三、方法手段眾所周知，數(shù)據(jù)庫技術(shù)從20世紀80年代開始，已經(jīng)得到廣泛的普及和應(yīng)用。隨著數(shù)據(jù)庫容量的膨脹，特別是數(shù)據(jù)倉庫以及web等新型數(shù)據(jù)源的日益普及，人們面臨的主要問題不再是缺乏足夠的信息可以使用，而是面對浩瀚的數(shù)據(jù)海洋如何有效地利用這些數(shù)據(jù)。

20、從數(shù)據(jù)中生成分類器的一個特別有效的方法是生成一個決策樹（Decision Tree）。決策樹表示方法是應(yīng)用最廣泛的邏輯方法之一，它從一組無次序、無規(guī)則的事例中推理出決策樹表示形式的分類規(guī)則。決策樹分類方法采用自頂向下的遞歸方式，在決策樹的內(nèi)部結(jié)點進行屬性值的比較并根據(jù)不同的屬性值判斷從該結(jié)點向下的分支，在決策樹的葉結(jié)點得到結(jié)論。所以從決策樹的根到葉結(jié)點的一條路徑就對應(yīng)著一條合取規(guī)則，整棵決策樹就對應(yīng)著一組析取表達式規(guī)則。決策樹是應(yīng)用非常廣泛的分類方法，目前有多種決策樹方法，如ID3、CN2、SLIQ、SPRINT等。四、Id3算法1.1相關(guān)信息決策樹是一個類似于流程圖的樹結(jié)構(gòu)，其中每個內(nèi)部結(jié)點

21、表示在一個屬性上的測試，每個分支代表一個測試輸入，而每個樹葉結(jié)點代表類或類分布。數(shù)的最頂層結(jié)點是根結(jié)點。一棵典型的決策樹如圖1所示。它表示概念buys_computer，它預(yù)測顧客是否可能購買計算機。內(nèi)部結(jié)點用矩形表示，而樹葉結(jié)點用橢圓表示。為了對未知的樣本分類，樣本的屬性值在決策樹上測試。決策樹從根到葉結(jié)點的一條路徑就對應(yīng)著一條合取規(guī)則，因此決策樹容易轉(zhuǎn)化成分類規(guī)則。圖1ID3算法特點：1）決策樹中每一個非葉結(jié)點對應(yīng)著一個非類別屬性，樹枝代表這個屬性的值。一個葉結(jié)點代表從樹根到葉結(jié)點之間的路徑對應(yīng)的記錄所屬的類別屬性值。2）每一個非葉結(jié)點都將與屬性中具有最大信息量的非類別屬性相關(guān)聯(lián)。3）采用

22、信息增益來選擇能夠最好地將樣本分類的屬性。信息增益基于信息論中熵的概念。ID3總是選擇具有最高信息增益（或最大熵壓縮）的屬性作為當(dāng)前結(jié)點的測試屬性。該屬性使得對結(jié)果劃分中的樣本分類所需的信息量最小，并反映劃分的最小隨機性或“不純性”。1.2問題重述1、目標概念為“壽險促銷”2、計算每個屬性的信息增益3、確定根節(jié)點的測試屬性1.3 模型求解構(gòu)造決策樹的方法是采用自上而下的遞歸構(gòu)造，其思路是：1）以代表訓(xùn)練樣本的單個結(jié)點開始建樹（步驟1）。2）如果樣本都在同一類，則該結(jié)點成為樹葉，并用該類標記（步驟2和3）。3）否則，算法使用稱為信息增益的機遇熵的度量為啟發(fā)信息，選擇能最好地將樣本分類的屬性（步驟

23、6）。該屬性成為該結(jié)點的“測試”或“判定”屬性（步驟7）。值得注意的是，在這類算法中，所有的屬性都是分類的，即取離散值的。連續(xù)值的屬性必須離散化。4）對測試屬性的每個已知的值，創(chuàng)建一個分支，并據(jù)此劃分樣本（步驟810）。5）算法使用同樣的過程，遞歸地形成每個劃分上的樣本決策樹。一旦一個屬性出現(xiàn)在一個結(jié)點上，就不必考慮該結(jié)點的任何后代（步驟13）。6）遞歸劃分步驟，當(dāng)下列條件之一成立時停止：（a）給定結(jié)點的所有樣本屬于同一類（步驟2和3）。（b）沒有剩余屬性可以用來進一步劃分樣本（步驟4）。在此情況下，采用多數(shù)表決（步驟5）。這涉及將給定的結(jié)點轉(zhuǎn)換成樹葉，并用samples中的多數(shù)所在類別標記它

24、。換一種方式，可以存放結(jié)點樣本的類分布。（c）分支test_attribute=ai 沒有樣本。在這種情況下，以samples中的多數(shù)類創(chuàng)建一個樹葉（步驟12）。1.4 算法步驟Decision_Tree(samples,attribute_list)輸入由離散值屬性描述的訓(xùn)練樣本集samples;候選屬性集合attribute_list。輸出一棵決策樹。（1） 創(chuàng)建節(jié)點N；（2） if samples 都在同一類C中then （3） 返回N作為葉節(jié)點，以類C標記；（4） if attribute_list為空then （5） 返回N作為葉節(jié)點，以samples 中最普遍的類標記；/多數(shù)表決（

25、6） 選擇attribute_list 中具有最高信息增益的屬性test_attribute;（7） 以test_attribute 標記節(jié)點N；（8） for each test_attribute 的已知值v /劃分 samples（9） 由節(jié)點N分出一個對應(yīng)test_attribute=v的分支；（10）令Sv為 samples中 test_attribute=v 的樣本集合；/一個劃分塊（11）if Sv為空 then （12）加上一個葉節(jié)點，以samples中最普遍的類標記；（13）else 加入一個由Decision_Tree(Sv,attribute_list-test_attr

26、ibute)返回節(jié)點值1.5 例子說明E(S)=(-915)log2(915)-(615)log2(615)=0.971Values(收入范圍)=20-30K,30-40k,40-50K,50-60K E(S(20-30K)= (-24)log2(24)- (24)log2(24)=1E(S(30-40K)= (-45)log2(45)- (15)log2(15)=0.7219E(S(40-50K)= (-14)log2(14)- (34)log2(34)=0.8113E(S(50-60K)= (-22)log2 (22)- (02)log2(02)=0所以，E(S,收入范圍)=(4/15)

27、E(S(20-30K) +(5/15) E(S(30-40K) +(4/15) E(S(40-50K) +(2/15) E(S(50-60K)=0.7236Gain(S,收入范圍)=0.971-0.7236=0.2474同理：計算“保險”，“性別”，“年齡”的信息增益為：E(S)=(-915)log2(915)-(615)log2(615)=0.971Insurance(保險)=yes, noE(S(yes)= (-33)log2 (33)- (03)log2(03)=0E(S(no)= (-612)log2 (612)- (612)log2(612)=1E(S, 保險)=(3/15) E(S

28、(yes) +(12/15) E(S(no) =0.8Gain(S, 保險)=0.971-0.8=0.171E(S)=(-915)log2(915)-(615)log2(615)=0.971sex(性別)=male, femaleE(S(male)= (-37)log2 (37)- (47)log2(47)=0.9852E(S(female)= (-68)log2 (68)- (28)log2(28)=0.8113E(S, 性別)=(7/15) E(S(male) +(8/15) E(S(female) =0.8925Gain(S, 性別)=0.971-0.8925=0.0785E(S)=(-

29、915)log2(915)-(615)log2(615)=0.971age(年齡)=1540,41 60E(S(1540)= (-67)log2 (67)- (17)log2(17)=0.5917E(S(41 60)= (-38)log2 (38)- (58)log2(58)=0.9544E(S, 年齡)=(7/15) E(S(1540) +(8/15) E(S(41 60) =0.7851Gain(S, 年齡)=0.971-0.7851=0.1859五、實驗結(jié)果根據(jù)輸出結(jié)果畫出決策樹，如下圖所示：六、實驗總結(jié)基于決策樹的分類算法的一個最大的優(yōu)點就是它在學(xué)習(xí)過程中不需要使用者了解很多背景知識（

30、這同時也是它的最大的缺點），只要訓(xùn)練例子能夠用屬性-結(jié)論式表示出來，就能使用該算法來學(xué)習(xí)。在ID3算法的假設(shè)空間包含所有的決策樹，它是關(guān)于現(xiàn)有屬性的有限離散值函數(shù)的一個完整空間。因為每個有限離散值函數(shù)可被表示為某個決策樹，所以ID3算法避免了搜索不完整。假設(shè)空間的一個主要風(fēng)險：假設(shè)空間可能不包含目標函數(shù)。ID3算法只能處理離散值的屬性。首先，學(xué)習(xí)到的決策樹要預(yù)測的目標屬性必須是離散的，其次樹的決策結(jié)點的屬性也必須是離散的。實驗三、分類模型2 C4.5算法一、實驗?zāi)康募訌妼4.5算法的理解。二、實驗內(nèi)容編程實現(xiàn)C4.5算法，加深對其理解。三、實驗原理C4.5算法是機器學(xué)習(xí)算法中的一種分類決策樹

31、算法,其核心算法是ID3算法。C4.5算法繼承了ID3算法的優(yōu)點，并引入了新方法和增加了新的功能。例如：n 用信息增益比例的概念；n 合并具有連續(xù)屬性的值；n 可以處理缺少屬性值的訓(xùn)練樣本；n 通過使用不同的修剪技術(shù)以避免樹的過度擬合；n k交叉驗證；n 規(guī)則的產(chǎn)生方式等。(一)、ID3算法存在的缺點（1）ID3算法在選擇根節(jié)點和各內(nèi)部節(jié)點中的分支屬性時，采用信息增益作為評價標準。信息增益的缺點是傾向于選擇取值較多的屬性，在有些情況下這類屬性可能不會提供太多有價值的信息。（2）ID3算法只能對描述屬性為離散型屬性的數(shù)據(jù)集構(gòu)造決策樹。(二)、C4.5算法做出的改進（1）、用信息增益率來選擇屬性。

32、克服了用信息增益來選擇屬性時偏向選擇值多的屬性的不足。信息增益率定義為： 其中Gain(S,A)與ID3算法中的信息增益相同，而分裂信息SplitInfo(S,A)代表了按照屬性A分裂樣本集S的廣度和均勻性。其中，S1到Sc是c個不同值的屬性A分割S而形成的c個樣本子集。如按照屬性A把S集（含30個用例）分成了10個用例和20個用例兩個集合則SplitInfo(S,A)=-1/3*log(1/3)-2/3*log(2/3)（2）、可以處理連續(xù)數(shù)值型屬性。C4.5既可以處理離散型描述屬性，也可以處理連續(xù)性描述屬性。在選擇某節(jié)點上的分枝屬性時，對于離散型描述屬性，C4.5的處理方法與ID3相同，按

33、照該屬性本身的取值個數(shù)進行計算；對于某個連續(xù)性描述屬性Ac，假設(shè)在某個結(jié)點上的數(shù)據(jù)集的樣本數(shù)量為total，C4.5將作以下處理。n 將該結(jié)點上的所有數(shù)據(jù)樣本按照連續(xù)型描述屬性的具體數(shù)值，由小到大進行排序，得到屬性值的取值序列A1c，A2c，Atotalc。n 在取值序列中生成total-1個分割點。第i（0itotal）個分割點的取值設(shè)置為Vi=（Aic+A（i+1）c）/2,它可以將該節(jié)點上的數(shù)據(jù)集劃分為兩個子集。n 從total-1個分割點中選擇最佳分割點。對于每一個分割點劃分數(shù)據(jù)集的方式，C4.5計算它的信息增益比，并且從中選擇信息增益比最大的分割點來劃分數(shù)據(jù)集。（3）、對于缺失值的處

34、理。在某些情況下，可供使用的數(shù)據(jù)可能缺少某些屬性的值。假如x，c(x)是樣本集S中的一個訓(xùn)練實例，但是其屬性A的值A(chǔ)(x)未知。處理缺少屬性值的一種策略是賦給它結(jié)點n所對應(yīng)的訓(xùn)練實例中該屬性的最常見值；另外一種更復(fù)雜的策略是為A的每個可能值賦予一個概率。例如，給定一個布爾屬性A，如果結(jié)點n包含6個已知A=1和4個A=0的實例，那么A(x)=1的概率是0.6，而A(x)=0的概率是0.4。于是，實例x的60%被分配到A=1的分支，40%被分配到另一個分支。這些片斷樣例（fractional examples）的目的是計算信息增益，另外，如果有第二個缺少值的屬性必須被測試，這些樣例可以在后繼的樹分

35、支中被進一步細分。C4.5就是使用這種方法處理缺少的屬性值。(三)、C4.5算法的優(yōu)缺點優(yōu)點：產(chǎn)生的分類規(guī)則易于理解，準確率較高。缺點：在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進行多次的順序掃描和排序，因而導(dǎo)致算法的低效。此外，C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時程序無法運行。(四)、C4.5算法的簡單實現(xiàn)#include stdafx.h#include #include #include malloc.h#include const int MAX = 10;int* iInput;int i = 0;/列數(shù)int j = 0;/行數(shù)void build_tree(F

36、ILE *fp, int* iSamples, int* iAttribute,int ilevel);/輸出規(guī)則int choose_attribute(int* iSamples, int* iAttribute);/通過計算信息增益率選出test_attributedouble info(double dTrue,double dFalse);/計算期望信息double entropy(double dTrue, double dFalse, double dAll);/求熵double splitinfo(int* list,double dAll);int check_samples

37、(int *iSamples);/檢查samples是否都在同一個類里int check_ordinary(int *iSamples);/檢查最普通的類int check_attribute_null(int *iAttribute);/檢查attribute是否為空void get_attributes(int *iSamples,int *iAttributeValue,int iAttribute);int _tmain(int argc, _TCHAR* argv)FILE *fp;FILE *fp1;char iGet;int a = 0;int b = 0;/a,b是循環(huán)變量in

38、t* iSamples;int* iAttribute;fp = fopen(c:input.txt,r);if (NULL = fp)printf(errorn);return 0;iGet = getc(fp);while (n != iGet)&(EOF != iGet)if (, = iGet)i+;iGet = getc(fp);i+;iAttribute = (int *)malloc(sizeof(int)*i);for (int k = 0; ki; k+)iAttributek = (int)malloc(sizeof(int);iAttributek = 1;while (

39、EOF != iGet)if (n = iGet)j+;iGet = getc(fp);j+;iInput = (int *)malloc(sizeof(int*)*j);iSamples = (int *)malloc(sizeof(int)*j);for (a = 0;a j;a+)iInputa = (int *)malloc(sizeof(int)*i);iSamplesa = (int)malloc(sizeof(int);iSamplesa = a;a = 0;fclose(fp);fp=fopen(c:input.txt,r);iGet = getc(fp);while(EOF

40、!= iGet)if (, != iGet)&(n != iGet)iInputab = iGet - 48;b+;if (b = i)a+;b = 0;iGet = getc(fp);fp1 = fopen(d:output.txt,w);build_tree(fp1,iSamples,iAttribute,0);fclose(fp);return 0;void build_tree(FILE * fp, int* iSamples, int* iAttribute,int level)/int iTest_Attribute = 0;int iAttributeValueMAX;int k

41、 = 0;int l = 0;int m = 0;int *iSamples1;for (k = 0; kMAX; k+)iAttributeValuek = -1;if (0 = check_samples(iSamples)fprintf(fp,result: %dn,iInputiSamples0i-1);return;if (1 = check_attribute_null(iAttribute)fprintf(fp,result: %dn,check_ordinary(iSamples);return;iTest_Attribute = choose_attribute(iSampl

42、es,iAttribute);iAttributeiTest_Attribute = -1;get_attributes(iSamples,iAttributeValue,iTest_Attribute);k = 0;while (-1 != iAttributeValuek)&(k MAX)l = 0;m = 0;while (-1 != iSamplesl)&(l j)if (iInputiSamplesliTest_Attribute = iAttributeValuek)m+;l+;iSamples1 = (int *)malloc(sizeof(int)*(m+1);l = 0;m

43、= 0;while (-1 != iSamplesl)&(l j)if (iInputiSamplesliTest_Attribute = iAttributeValuek)iSamples1m = iSamplesl;m+;l+;iSamples1m = -1;if (-1 = iSamples10)fprintf(fp,result: %dn,check_ordinary(iSamples);return;fprintf(fp,level%d: %d = %dn,level,iTest_Attribute,iAttributeValuek);build_tree(fp,iSamples1,

44、iAttribute,level+1);k+;int choose_attribute(int* iSamples, int* iAttribute)int iTestAttribute = -1;int k = 0;int l = 0;int m = 0;int n = 0;int iTrue = 0;int iFalse = 0;int iTrue1 = 0;int iFalse1 = 0;int iDepartMAX;int iRecordMAX;double dEntropy = 0.0;double dGainratio = 0.0;double test = 0.0;for (k

45、= 0;kMAX;k+)iDepartk = -1;iRecordk = 0;k = 0;while (l!=2)&(k(i - 1)if (iAttributek = -1)l+;k+;if (l = 1)for (k = 0;k(k-1);k+)if (iAttributek = -1)return iAttributek;for (k = 0;k (i-1);k+)l = 0;iTrue = 0;iFalse = 0;if (iAttributek != -1)while (-1 != iSamplesl)&(l j)if (0 = iInputiSamplesli-1)iFalse+;if (1 = iInputiSamplesli-1)iTrue+;l+;for