知識發(fā)現(xiàn)與數(shù)據(jù)挖掘?qū)嶒?yàn)報(bào)告

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

2、定的最小可信度的規(guī)則才被留下來。為了生成所有頻繁項(xiàng)目集，使用了遞推的方法。(一)、Apriori（發(fā)現(xiàn)頻繁項(xiàng)目集）輸入：數(shù)據(jù)集D；最小支持?jǐn)?shù)minsup_count。輸出：頻繁項(xiàng)目集L。（1）L1=large 1-itemsets;/所有支持讀不小于minsupport的1-項(xiàng)目集（2）、FOR （k=2;Lk-1;k+） DO BEGIN（3）Ck = apriori-gen(Lk-1 ,min_sup);/Ck是k個(gè)元素的候選集（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)-頻繁項(xiàng)目集Lk-1。輸出：k-候選項(xiàng)目集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)生）輸入：一個(gè)k-候選項(xiàng)目集c,(k-1)-頻繁項(xiàng)目集Lk-1。輸出：c是否從候選集中刪除的布爾判斷。（1）FOR all (k-1)-subsets of c DO（2）IF S Lk-1 THEN Return TRUE；（3）Return FALSE;四、代碼實(shí)現(xiàn)（一）算法數(shù)據(jù)：對給定數(shù)據(jù)集用Apriori算法進(jìn)行挖掘，找出其中的頻繁集并生成關(guān)聯(lián)規(guī)則

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

6、。（三）C+算法的簡單實(shí)現(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;實(shí)現(xiàn)出現(xiàn)的一維子集。由于給出的數(shù)據(jù)最多有4個(gè)數(shù)，所以同樣的我們要定義到4維來放數(shù)據(jù)。int countL210; /各二維頻繁子集出現(xiàn)的次數(shù)char curL2203; /出現(xiàn)的二維子集int countL310; /各三維頻繁子集出現(xiàn)的次數(shù)char curL32

7、04; /出現(xiàn)的三維子集char cur504;（3）、定義int SizeStr(char* m) 得到字符串的長度。實(shí)現(xiàn)代碼如下：int SizeStr(char* m)int i=0;while(*(m+i)!=0)i+;return i;（4）、比較兩個(gè)字符串，如果相等返回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）、通過voi

8、d 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+;curL100=cur00;curL101=cur01

9、;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("項(xiàng)集 支持度計(jì)數(shù)n");for(i=0;i<10;

10、i+)if(curL1i=0)break;if(countL1i>=2)printf("I%s: %dn",curL1i,countL1i);（6）、通過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;for(k=0;k<10;k+)s=*(p+k);if

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

12、02=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");printf("項(xiàng)集 支持度計(jì)數(shù)n");for

13、(i=0;i<10;i+)if(curL2i=0)break;if(countL2i>=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;j<20;j+)curL3j0=0;curL3j1=0;curL3j2=0;curL3j3=0;for(i=0;i<10;i

14、+)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+;（9）同樣我們要得到得到各個(gè)3元頻繁子串出現(xiàn)的次數(shù)void LoadItemL3(char* p)int k,i,j;cha

15、r* 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(j=0;j<50;j+)s=curL3i;if(*s=0)break

16、;if(OpD(s,curj)countL3i+;printf("L3: n");printf("項(xiàng)集 支持度計(jì)數(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,curL3i2,countL3i);（10）、定義void LoadItemL4(char* p) 得到各個(gè)3元子串出現(xiàn)的次數(shù)void LoadItemL4(char* p)int i;char* s;int j=0;for

17、(i=0;i<10;i+)s=*(p+i);if(SizeStr(s)=4)j+;printf("四維子集出現(xiàn)的次數(shù): %dn",j);printf("沒有四維的頻繁子集，算法結(jié)束! 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;i<SizeStr(s);i+)*(curn+0)=*(s

18、+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(SizeStr(curi)=1)for(j=0;j<10;j+)if(OpD(curi,curL1j)d=countL3g/(float)countL1j;if(d>=c)printf(&

19、quot;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;（12）、最后通過main函數(shù)完成整過程序int main(int argc, char* argv)int i=0,j=0,k;char buf106;char* p10;char ch;memset(buf,0,size

20、of(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;k<10;k+)*(p+k)=bufk;LoadItemL1(p);LoadItemL2(p);LoadItemL3(p);LoadItemL4(p);printf("產(chǎn)生關(guān)聯(lián)規(guī)則: n");prin

21、tf("非空子集: 置信度:n");for(i=0;i<10;i+)if(curL3i!=0 && countL3i>=2)Support(curL3i,i);return 0;（四）程序輸出結(jié)果：實(shí)驗(yàn)二 分類模型 1 Id3算法一、實(shí)驗(yàn)?zāi)康耐ㄟ^實(shí)驗(yàn)，加深數(shù)據(jù)挖掘中分類（決策樹）的認(rèn)識，其經(jīng)典算法為Id3算法，了解影響Id3算法性能的因素，掌握基于Id3算法理論的分類分析的原理和方法。二、實(shí)驗(yàn)內(nèi)容對一數(shù)據(jù)集用Id3算法做數(shù)據(jù)分類分析（預(yù)測），用java語言實(shí)現(xiàn)。三、方法手段眾所周知，數(shù)據(jù)庫技術(shù)從20世紀(jì)80年代開始，已經(jīng)得到廣泛的普及和應(yīng)用。隨著

22、數(shù)據(jù)庫容量的膨脹，特別是數(shù)據(jù)倉庫以及web等新型數(shù)據(jù)源的日益普及，人們面臨的主要問題不再是缺乏足夠的信息可以使用，而是面對浩瀚的數(shù)據(jù)海洋如何有效地利用這些數(shù)據(jù)。從數(shù)據(jù)中生成分類器的一個(gè)特別有效的方法是生成一個(gè)決策樹（Decision Tree）。決策樹表示方法是應(yīng)用最廣泛的邏輯方法之一，它從一組無次序、無規(guī)則的事例中推理出決策樹表示形式的分類規(guī)則。決策樹分類方法采用自頂向下的遞歸方式，在決策樹的內(nèi)部結(jié)點(diǎn)進(jìn)行屬性值的比較并根據(jù)不同的屬性值判斷從該結(jié)點(diǎn)向下的分支，在決策樹的葉結(jié)點(diǎn)得到結(jié)論。所以從決策樹的根到葉結(jié)點(diǎn)的一條路徑就對應(yīng)著一條合取規(guī)則，整棵決策樹就對應(yīng)著一組析取表達(dá)式規(guī)則。決策樹是應(yīng)用非常

23、廣泛的分類方法，目前有多種決策樹方法，如ID3、CN2、SLIQ、SPRINT等。四、Id3算法1.1相關(guān)信息決策樹是一個(gè)類似于流程圖的樹結(jié)構(gòu)，其中每個(gè)內(nèi)部結(jié)點(diǎn)表示在一個(gè)屬性上的測試，每個(gè)分支代表一個(gè)測試輸入，而每個(gè)樹葉結(jié)點(diǎn)代表類或類分布。數(shù)的最頂層結(jié)點(diǎn)是根結(jié)點(diǎn)。一棵典型的決策樹如圖1所示。它表示概念buys_computer，它預(yù)測顧客是否可能購買計(jì)算機(jī)。內(nèi)部結(jié)點(diǎn)用矩形表示，而樹葉結(jié)點(diǎn)用橢圓表示。為了對未知的樣本分類，樣本的屬性值在決策樹上測試。決策樹從根到葉結(jié)點(diǎn)的一條路徑就對應(yīng)著一條合取規(guī)則，因此決策樹容易轉(zhuǎn)化成分類規(guī)則。圖1ID3算法特點(diǎn)：1）決策樹中每一個(gè)非葉結(jié)點(diǎn)對應(yīng)著一個(gè)非類別屬性，

24、樹枝代表這個(gè)屬性的值。一個(gè)葉結(jié)點(diǎn)代表從樹根到葉結(jié)點(diǎn)之間的路徑對應(yīng)的記錄所屬的類別屬性值。2）每一個(gè)非葉結(jié)點(diǎn)都將與屬性中具有最大信息量的非類別屬性相關(guān)聯(lián)。3）采用信息增益來選擇能夠最好地將樣本分類的屬性。信息增益基于信息論中熵的概念。ID3總是選擇具有最高信息增益（或最大熵壓縮）的屬性作為當(dāng)前結(jié)點(diǎn)的測試屬性。該屬性使得對結(jié)果劃分中的樣本分類所需的信息量最小，并反映劃分的最小隨機(jī)性或“不純性”。1.2問題重述1、目標(biāo)概念為“壽險(xiǎn)促銷”2、計(jì)算每個(gè)屬性的信息增益3、確定根節(jié)點(diǎn)的測試屬性1.3 模型求解構(gòu)造決策樹的方法是采用自上而下的遞歸構(gòu)造，其思路是：1）以代表訓(xùn)練樣本的單個(gè)結(jié)點(diǎn)開始建樹（步驟1）。

25、2）如果樣本都在同一類，則該結(jié)點(diǎn)成為樹葉，并用該類標(biāo)記（步驟2和3）。3）否則，算法使用稱為信息增益的機(jī)遇熵的度量為啟發(fā)信息，選擇能最好地將樣本分類的屬性（步驟6）。該屬性成為該結(jié)點(diǎn)的“測試”或“判定”屬性（步驟7）。值得注意的是，在這類算法中，所有的屬性都是分類的，即取離散值的。連續(xù)值的屬性必須離散化。4）對測試屬性的每個(gè)已知的值，創(chuàng)建一個(gè)分支，并據(jù)此劃分樣本（步驟810）。5）算法使用同樣的過程，遞歸地形成每個(gè)劃分上的樣本決策樹。一旦一個(gè)屬性出現(xiàn)在一個(gè)結(jié)點(diǎn)上，就不必考慮該結(jié)點(diǎn)的任何后代（步驟13）。6）遞歸劃分步驟，當(dāng)下列條件之一成立時(shí)停止：（a）給定結(jié)點(diǎn)的所有樣本屬于同一類（步驟2和3）

26、。（b）沒有剩余屬性可以用來進(jìn)一步劃分樣本（步驟4）。在此情況下，采用多數(shù)表決（步驟5）。這涉及將給定的結(jié)點(diǎn)轉(zhuǎn)換成樹葉，并用samples中的多數(shù)所在類別標(biāo)記它。換一種方式，可以存放結(jié)點(diǎn)樣本的類分布。（c）分支test_attribute=ai 沒有樣本。在這種情況下，以samples中的多數(shù)類創(chuàng)建一個(gè)樹葉（步驟12）。1.4 算法步驟Decision_Tree(samples,attribute_list)輸入由離散值屬性描述的訓(xùn)練樣本集samples;候選屬性集合attribute_list。輸出一棵決策樹。（1） 創(chuàng)建節(jié)點(diǎn)N；（2） if samples 都在同一類C中then （3）

27、返回N作為葉節(jié)點(diǎn)，以類C標(biāo)記；（4） if attribute_list為空then （5） 返回N作為葉節(jié)點(diǎn)，以samples 中最普遍的類標(biāo)記；/多數(shù)表決（6） 選擇attribute_list 中具有最高信息增益的屬性test_attribute;（7） 以test_attribute 標(biāo)記節(jié)點(diǎn)N；（8） for each test_attribute 的已知值v /劃分 samples（9） 由節(jié)點(diǎn)N分出一個(gè)對應(yīng)test_attribute=v的分支；（10）令Sv為 samples中 test_attribute=v 的樣本集合；/一個(gè)劃分塊（11）if Sv為空 then （12）

28、加上一個(gè)葉節(jié)點(diǎn)，以samples中最普遍的類標(biāo)記；（13）else 加入一個(gè)由Decision_Tree(Sv,attribute_list-test_attribute)返回節(jié)點(diǎn)值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)- (3

29、4)log2(34)=0.8113E(S(50-60K)= (-22)log2 (22)- (02)log2(02)=0所以，E(S,收入范圍)=(4/15) 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同理：計(jì)算“保險(xiǎn)”，“性別”，“年齡”的信息增益為：E(S)=(-915)log2(915)-(615)log2(615)=0.971Insurance(保險(xiǎn))=yes, noE(S(yes)= (-33)log2 (3

30、3)- (03)log2(03)=0E(S(no)= (-612)log2 (612)- (612)log2(612)=1E(S, 保險(xiǎn))=(3/15) E(S(yes) +(12/15) E(S(no) =0.8Gain(S, 保險(xiǎn))=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

31、/15) E(S(male) +(8/15) E(S(female) =0.8925Gain(S, 性別)=0.971-0.8925=0.0785E(S)=(-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.785

32、1=0.1859五、實(shí)驗(yàn)結(jié)果根據(jù)輸出結(jié)果畫出決策樹，如下圖所示：六、實(shí)驗(yàn)總結(jié)基于決策樹的分類算法的一個(gè)最大的優(yōu)點(diǎn)就是它在學(xué)習(xí)過程中不需要使用者了解很多背景知識（這同時(shí)也是它的最大的缺點(diǎn)），只要訓(xùn)練例子能夠用屬性-結(jié)論式表示出來，就能使用該算法來學(xué)習(xí)。在ID3算法的假設(shè)空間包含所有的決策樹，它是關(guān)于現(xiàn)有屬性的有限離散值函數(shù)的一個(gè)完整空間。因?yàn)槊總€(gè)有限離散值函數(shù)可被表示為某個(gè)決策樹，所以ID3算法避免了搜索不完整。假設(shè)空間的一個(gè)主要風(fēng)險(xiǎn)：假設(shè)空間可能不包含目標(biāo)函數(shù)。ID3算法只能處理離散值的屬性。首先，學(xué)習(xí)到的決策樹要預(yù)測的目標(biāo)屬性必須是離散的，其次樹的決策結(jié)點(diǎn)的屬性也必須是離散的。實(shí)驗(yàn)三、分類模

33、型2 C4.5算法一、實(shí)驗(yàn)?zāi)康募訌?qiáng)對C4.5算法的理解。二、實(shí)驗(yàn)內(nèi)容編程實(shí)現(xiàn)C4.5算法，加深對其理解。三、實(shí)驗(yàn)原理C4.5算法是機(jī)器學(xué)習(xí)算法中的一種分類決策樹算法,其核心算法是ID3算法。C4.5算法繼承了ID3算法的優(yōu)點(diǎn)，并引入了新方法和增加了新的功能。例如：n 用信息增益比例的概念；n 合并具有連續(xù)屬性的值；n 可以處理缺少屬性值的訓(xùn)練樣本；n 通過使用不同的修剪技術(shù)以避免樹的過度擬合；n k交叉驗(yàn)證；n 規(guī)則的產(chǎn)生方式等。(一)、ID3算法存在的缺點(diǎn)（1）ID3算法在選擇根節(jié)點(diǎn)和各內(nèi)部節(jié)點(diǎn)中的分支屬性時(shí)，采用信息增益作為評價(jià)標(biāo)準(zhǔn)。信息增益的缺點(diǎn)是傾向于選擇取值較多的屬性，在有些情況下這

34、類屬性可能不會提供太多有價(jià)值的信息。（2）ID3算法只能對描述屬性為離散型屬性的數(shù)據(jù)集構(gòu)造決策樹。(二)、C4.5算法做出的改進(jìn)（1）、用信息增益率來選擇屬性?？朔擞眯畔⒃鲆鎭磉x擇屬性時(shí)偏向選擇值多的屬性的不足。信息增益率定義為： 其中Gain(S,A)與ID3算法中的信息增益相同，而分裂信息SplitInfo(S,A)代表了按照屬性A分裂樣本集S的廣度和均勻性。其中，S1到Sc是c個(gè)不同值的屬性A分割S而形成的c個(gè)樣本子集。如按照屬性A把S集（含30個(gè)用例）分成了10個(gè)用例和20個(gè)用例兩個(gè)集合則SplitInfo(S,A)=-1/3*log(1/3)-2/3*log(2/3)（2）、可以處

35、理連續(xù)數(shù)值型屬性。C4.5既可以處理離散型描述屬性，也可以處理連續(xù)性描述屬性。在選擇某節(jié)點(diǎn)上的分枝屬性時(shí)，對于離散型描述屬性，C4.5的處理方法與ID3相同，按照該屬性本身的取值個(gè)數(shù)進(jìn)行計(jì)算；對于某個(gè)連續(xù)性描述屬性Ac，假設(shè)在某個(gè)結(jié)點(diǎn)上的數(shù)據(jù)集的樣本數(shù)量為total，C4.5將作以下處理。n 將該結(jié)點(diǎn)上的所有數(shù)據(jù)樣本按照連續(xù)型描述屬性的具體數(shù)值，由小到大進(jìn)行排序，得到屬性值的取值序列A1c，A2c，Atotalc。n 在取值序列中生成total-1個(gè)分割點(diǎn)。第i（0<i<total）個(gè)分割點(diǎn)的取值設(shè)置為Vi=（Aic+A（i+1）c）/2,它可以將該節(jié)點(diǎn)上的數(shù)據(jù)集劃分為兩個(gè)子集。n

36、 從total-1個(gè)分割點(diǎn)中選擇最佳分割點(diǎn)。對于每一個(gè)分割點(diǎn)劃分?jǐn)?shù)據(jù)集的方式，C4.5計(jì)算它的信息增益比，并且從中選擇信息增益比最大的分割點(diǎn)來劃分?jǐn)?shù)據(jù)集。（3）、對于缺失值的處理。在某些情況下，可供使用的數(shù)據(jù)可能缺少某些屬性的值。假如x，c(x)是樣本集S中的一個(gè)訓(xùn)練實(shí)例，但是其屬性A的值A(chǔ)(x)未知。處理缺少屬性值的一種策略是賦給它結(jié)點(diǎn)n所對應(yīng)的訓(xùn)練實(shí)例中該屬性的最常見值；另外一種更復(fù)雜的策略是為A的每個(gè)可能值賦予一個(gè)概率。例如，給定一個(gè)布爾屬性A，如果結(jié)點(diǎn)n包含6個(gè)已知A=1和4個(gè)A=0的實(shí)例，那么A(x)=1的概率是0.6，而A(x)=0的概率是0.4。于是，實(shí)例x的60%被分配到A=1

37、的分支，40%被分配到另一個(gè)分支。這些片斷樣例（fractional examples）的目的是計(jì)算信息增益，另外，如果有第二個(gè)缺少值的屬性必須被測試，這些樣例可以在后繼的樹分支中被進(jìn)一步細(xì)分。C4.5就是使用這種方法處理缺少的屬性值。(三)、C4.5算法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。缺點(diǎn)：在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。此外，C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時(shí)程序無法運(yùn)行。(四)、C4.5算法的簡單實(shí)現(xiàn)#include "stdafx.h"#include <stdio

38、.h>#include <math.h>#include "malloc.h"#include <stdlib.h>const int MAX = 10;int* iInput;int i = 0;/列數(shù)int j = 0;/行數(shù)void build_tree(FILE *fp, int* iSamples, int* iAttribute,int ilevel);/輸出規(guī)則int choose_attribute(int* iSamples, int* iAttribute);/通過計(jì)算信息增益率選出test_attributedouble

39、info(double dTrue,double dFalse);/計(jì)算期望信息double entropy(double dTrue, double dFalse, double dAll);/求熵double splitinfo(int* list,double dAll);int check_samples(int *iSamples);/檢查samples是否都在同一個(gè)類里int check_ordinary(int *iSamples);/檢查最普通的類int check_attribute_null(int *iAttribute);/檢查attribute是否為空void get

40、_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)變量 int* iSamples; int* iAttribute; fp = fopen("c:input.txt","r"); if (NULL =

41、fp)   printf("errorn");  return 0;  iGet = getc(fp);  while ('n' != iGet)&&(EOF != iGet)   if (',' = iGet)     i+;    iGet = getc(fp);  i+;  

42、iAttribute = (int *)malloc(sizeof(int)*i); for (int k = 0; k<i; k+)   iAttributek = (int)malloc(sizeof(int);  iAttributek = 1;  while (EOF != iGet)   if ('n' = iGet)     j+;    iGet = getc(

43、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; 

44、fclose(fp); fp=fopen("c:input.txt","r"); iGet = getc(fp); while(EOF != iGet)   if (',' != iGet)&&('n' != iGet)     iInputab = iGet - 48;   b+;    if (b = i) 

45、0;   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

46、)/ int iTest_Attribute = 0; int iAttributeValueMAX; int k = 0; int l = 0; int m = 0; int *iSamples1; for (k = 0; k<MAX; k+)   iAttributeValuek = -1;  if (0 = check_samples(iSamples)   fprintf(fp,"result: %dn",iIn

47、putiSamples0i-1);  return;  if (1 = check_attribute_null(iAttribute)   fprintf(fp,"result: %dn",check_ordinary(iSamples);  return;  iTest_Attribute = choose_attribute(iSamples,iAttribute); iAttributeiTest_Attribute = -1; get_

48、attributes(iSamples,iAttributeValue,iTest_Attribute); k = 0; while (-1 != iAttributeValuek)&&(k < MAX)   l = 0;  m = 0;  while (-1 != iSamplesl)&&(l < j)     if (iInputiSamplesliTest_Attribute = iAttributeVal

49、uek)       m+;      l+;    iSamples1 = (int *)malloc(sizeof(int)*(m+1);  l = 0;  m = 0;  while (-1 != iSamplesl)&&(l < j)     if (iInputiSamplesliTes

50、t_Attribute = iAttributeValuek)       iSamples1m = iSamplesl;    m+;      l+;    iSamples1m = -1;  if (-1 = iSamples10)     fprintf(fp,"result: %dn",c

51、heck_ordinary(iSamples);   return;    fprintf(fp,"level%d: %d = %dn",level,iTest_Attribute,iAttributeValuek);  build_tree(fp,iSamples1,iAttribute,level+1);  k+; int choose_attribute(int* iSamples, int* iAttribute) int iTestAt

52、tribute = -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

53、 (k = 0;k<MAX;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+)

54、     if (iAttributek = -1)       return iAttributek;       for (k = 0;k < (i-1);k+)   l = 0;  iTrue = 0;  iFalse = 0;  if (iAttributek != -1)  

55、0;  while (-1 != iSamplesl)&&(l < j)       if (0 = iInputiSamplesli-1)         iFalse+;        if (1 = iInputiSamplesli-1)      &

56、#160;  iTrue+;        l+;          for (n = 0;n<l;n+)/計(jì)算該屬性有多少不同的值并記錄       m = 0;    while(iDepartm!=-1)&&(m!=MAX)   &

57、#160;     if (iInputiSamplesniAttributek = iDepartm)           break;          m+;        if (-1 = iDepartm)   

58、0;     iDepartm = iInputiSamplesniAttributek;          while (iDepartm != -1)&&(m!=MAX)       for (n = 0;n<l;n+)         if (iInputiSa

59、mplesniAttributek = iDepartm)           if (1 = iInputiSamplesni-1)             iTrue1+;            if (0 = iInputiSamplesni-1)             iFalse1+;            iRecord