人工智能結(jié)課報(bào)告

人工智能結(jié)課報(bào)告學(xué)院：計(jì)算機(jī)學(xué)院班級(jí)：計(jì)本2012-3班姓名：黃靖學(xué)號(hào)：3110717215一種基于屬性重要度的ID3算法摘要：決策樹是數(shù)據(jù)挖掘中重要的分類算法，通常用來(lái)形成分類器。ID3算法是決策樹中的核心算法。針對(duì)ID3算法傾向于取值較多的屬性的缺點(diǎn)，引進(jìn)屬性重要度對(duì)ID3算法予以改進(jìn)，并通過實(shí)驗(yàn)對(duì)改進(jìn)前后的算法進(jìn)行了比較。實(shí)驗(yàn)表明，改進(jìn)后的算法是有效的！說明：決策樹分類方法是一種有效的數(shù)據(jù)挖掘方法。在決策樹的構(gòu)造中，ID3算法是最有影響力的決策樹生成算法，它是由Quinlan于1979年提出。ID3算法的基本思想是，以信息熵為度量，用于決策樹節(jié)點(diǎn)的屬性選擇，每次優(yōu)先選取信息量最多的屬性或者說能使熵值變成最小的屬性，以構(gòu)造一棵熵值下降最快的決策樹，到葉子節(jié)點(diǎn)處的熵值為0。但是該方法有傾向于選擇取值較多的屬性的缺點(diǎn)。粗糙集理論是由波蘭數(shù)學(xué)家ZPawlak于1982年首先提出的一種研究不精通，不確定性知識(shí)的數(shù)學(xué)工具，目前主要用于分類。通過對(duì)粗糙集理論和ID3算法的研究，利用粗糙集中屬性重要性知識(shí)，選擇屬性重要度大的屬性作為節(jié)點(diǎn)進(jìn)行分類，使生成決策樹時(shí)取值較少的屬性不會(huì)被淹沒或者降低屬性值較多且并不重要的屬性，最終使決策樹減少了對(duì)取值較多的屬性的依賴性，從而盡可能地減少大數(shù)據(jù)掩蓋小數(shù)據(jù)的現(xiàn)象發(fā)生，并通過實(shí)驗(yàn)對(duì)改進(jìn)前后的算法進(jìn)行了比較。實(shí)驗(yàn)表明，改進(jìn)后的算法是有效的！2．有關(guān)的基本概念（1）粗糙集的基本概念定義1設(shè)U是一個(gè)論域，R是U上的一個(gè)等價(jià)關(guān)系。U/R表示U上由R導(dǎo)出的所有等價(jià)類。[x]R表示包含元素x的R的等價(jià)類，x∈U。定義2一個(gè)近似空間（或知識(shí)庫(kù)）就是一個(gè)關(guān)系系統(tǒng)K={U，P}，其中U是論域，P是U上的一個(gè)等價(jià)關(guān)系簇。如果QP，Q中的等價(jià)關(guān)系的交集稱為Q上的不分明關(guān)系，記作則IND（Q），即：[x]ind(Q)=[x]p.可知，IND（Q）中的每一個(gè)等價(jià)類中的各元素對(duì)Q中的各屬性來(lái)說有相同的值，其中等價(jià)類的求解可由P中等價(jià)關(guān)系的等價(jià)類相交而求得。定義3令X∈U，對(duì)每個(gè)概念X（樣例集）和不分明關(guān)系B，包含于X中的最小可定義集和包含X的最大可定義集，都是根據(jù)B能夠確定的，前者稱為X的下近似集，后者稱為x的上近似集。下近似和上近似集的概念也可以通過集合來(lái)定義：（2）屬性重要度定義1設(shè)有兩個(gè)屬性集C和D，則D對(duì)C的依賴度定義為K，定義2設(shè)屬性,C是條件屬性集，D是決策屬性集，則的屬性重要度定義為：3．ID3算法（1）信息熵和條件熵ID3算法將實(shí)例集視為一個(gè)離散的信息系統(tǒng)，用信息熵表示其信息量。實(shí)例集中的實(shí)例的結(jié)論視為隨機(jī)事件，而將諸屬性看做是加入的信息源。設(shè)S是一個(gè)實(shí)例集，A為S中實(shí)例的一個(gè)屬性。H(S)和H(S|A)分別稱為實(shí)例集S的信息熵和條件熵，其計(jì)算公式如下：（1）其中，i(i=1,2,…,n)為S中各實(shí)例所有可能的結(jié)論；lb即log2.（2）其中，ak（k=1,2，…，m）為屬性A的取值，Sak為按屬性對(duì)實(shí)例集S進(jìn)行分類時(shí)ak對(duì)應(yīng)的那個(gè)子類所得諸子類中與屬性值。（2）基于條件熵的屬性選擇對(duì)于一個(gè)待分類的實(shí)例集S，先分別計(jì)算各可取屬性Aj（j=1,2，…，L）的條件熵H(S|Aj)。然后取其中熵值最小的屬性As作為當(dāng)前節(jié)點(diǎn)。4．算法的改進(jìn)傳統(tǒng)的ID3算法選擇屬性A作為測(cè)試屬性的原則：使式（2）的值最小。這種算法往往偏向于選擇值較多的屬性，然而取值較多的屬性卻并不總是最優(yōu)的屬性。即按照使熵值最小的原則，被ID3算法列為應(yīng)選取的屬性，對(duì)其進(jìn)行測(cè)試不會(huì)提供太多的信息。所以，我們引入屬性重要度。對(duì)于某些問題，屬性具有不同的重要度，當(dāng)我們?cè)谟肐D3算法構(gòu)造決策樹時(shí)，可以首先利用表中的數(shù)據(jù)計(jì)算所有屬性的屬性重要度，如果不是，則它們?cè)诜诸惸芰ι暇陀胁顒e。此次對(duì)ID3算法的改進(jìn)就是基于屬性重要度，對(duì)選擇標(biāo)準(zhǔn)進(jìn)行改進(jìn)。通過對(duì)式（2）加權(quán)和增加屬性重要度，加強(qiáng)了屬性的標(biāo)注，降低了非重要屬性的標(biāo)注，把“加權(quán)和”轉(zhuǎn)換為與屬性重要度相加的“新加權(quán)和”。這樣，生成決策樹時(shí)，取值少的屬性不會(huì)被淹沒，最終使決策樹減少“大數(shù)據(jù)掩蓋小數(shù)據(jù)”的現(xiàn)象的發(fā)生。利用屬性重要度，將式（2）修改為（3）用改進(jìn)后的算法構(gòu)造決策樹時(shí)，可以首先計(jì)算各個(gè)屬性的屬性重要度，若相同，則說明此實(shí)例集中的屬性在分類能力上沒有差別，則不需要用進(jìn)行改進(jìn)；若不同，則用改進(jìn)的ID3算法來(lái)構(gòu)造決策樹。5．實(shí)例驗(yàn)證注：通過計(jì)算書上P193某保險(xiǎn)公司的汽車駕駛保險(xiǎn)類別劃分的部分實(shí)例，發(fā)現(xiàn)屬性性別，年齡段，婚狀的屬性重要度均相同，我們便沒有列出，但我們?cè)诖伺e了另外一個(gè)例子來(lái)驗(yàn)證我們的算法。首先我們來(lái)計(jì)算屬性重要度（這里我們用A表示穿衣指數(shù)，B表示溫度，C表示濕度，D表示風(fēng)力，Z表示決策屬性舒適度）對(duì)于決策屬性Z，當(dāng)Z=P時(shí)，{4,5,8,14,15,16,17,,18,20}，當(dāng)Z=N時(shí)，{1,2,3,6,7,9,10,11,12,13,19}。對(duì)于條件屬性A，當(dāng)A=較多，A1={1,2,3,10,11,14,15}；當(dāng)A=正常,A2={4,5,16,17,18,20};當(dāng)A=很多，A3={6,7,8,9,12,13,19}。計(jì)算A的屬性重要度為：SGF(A)=6/20=0.3.對(duì)于條件屬性B，當(dāng)B=適中,B2={6,7,10,11,12,13,14,15,16,17,19}。計(jì)算B的屬性重要度為：SGF(B)=0/20=0.對(duì)于條件屬性C，當(dāng)C=很大，C1={1,2,3,4,5,6,7,10,11,16,17,19}；當(dāng)C=正常,C2={8,9,12,13,14,15,18,20}。計(jì)算C的屬性重要度為：SGF(C)=0/20=0.對(duì)于條件屬性D，當(dāng)D=沒有，D1={1,4,6,8,10,12,18}；當(dāng)D=很大D2={2,9,15,16,19};當(dāng)D=中等，D3={3,5,7,11,13,14,17,20}。計(jì)算D的屬性重要度為：SGF(D)=0/20=0.可知，屬性A,B,C,D的重要度是不同的，下面我們就用改進(jìn)后的算法來(lái)構(gòu)造決策樹。S(A1)={(1,N),(2,N),(3,N),(10,N),(11,N),(14,P),(15,P)}S(A2)={(4,P),(5,P),(16,P),(17,P),(18,P),(20,P)}S(A3)={(6,N),(7,N),(8,P),(9,N),(12,N),(13,N),(19,N)}從而，對(duì)子集S（A1）而言，P(P)=2/7,P(N)=5/7對(duì)子集S（A2）而言，P(P)=6/6,P(N)=0/6對(duì)子集S（A3）而言，P(P)=1/7,P(N)=6/7于是，由公式（1）有：H(S(A1))=-(P(P)lbP(P)+P(N)lbP(N))=-(（2/7）×lb(2/7)+（5/7）×lb(5/7)=0.8631H(S(A2))=-(P(P)lbP(P)+P(N)lbP(N))=-(（6/6）×lb(6/6)+（0/6）×lb(0/6)=0H(S(A3))=-(P(P)lbP(P)+P(N)lbP(N))=-(（1/7）×lb(1/7)+（6/7）×lb(6/7)=0.5917又|S(A1)|/|S|=7/20,|S(A2)|/|S|=6/20,|S(A3)|/|S|=7/20利用屬性重要度，根據(jù)式（3）則有，H(S|A)=(（7/20）+SGF(A))×H(S(A1))+(（6/20）+SGF(A))×H(S(A2))+(（7/20）+SGF(A))×H(S(A3))=0.9456用同樣的方法可求得：則有，H(S|B)=0.9661；H(S|C)=0.9328；H(S|D)=0.9880.比較可知H(S|C)<H(S|A)<H(S|B)<H(S|D).則用改進(jìn)后的ID3算法可得決策樹如下：為了便于比較，再給出用ID3算法構(gòu)造的決策樹如下：比較兩種算法構(gòu)造的決策樹我們可以看出，改進(jìn)的ID3算法所生成的決策樹降低了穿衣指數(shù)對(duì)天氣舒適影響的重要性，離根節(jié)點(diǎn)的距離變遠(yuǎn)，而濕度，溫度，風(fēng)力在分類中的的重要度相應(yīng)的提高了，這顯然是與實(shí)際情況相符合的，因?yàn)樵趯?shí)際生活中，人們穿衣服的多少實(shí)際上是一種主觀的行為，跟個(gè)人的習(xí)慣有關(guān)，比方說，老人，成人和小孩，正常人和病人在相同的環(huán)境下穿衣服肯定也是不一樣的。因此，在ID3算法中加入屬性重要度是有意義的！6．總結(jié)首先，在充分看書之后，大家都對(duì)決策樹比較感興趣，所以決定論文方向與決策樹相關(guān)。大家通關(guān)各種途徑查閱資料之后，在第一次開會(huì)交流