人工智能結課報告

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