華工人工智能ID3算法問題詳解-基于信息熵的ID3算法

1、.華工人工智能ID3算法問題詳解基于信息熵的ID3算法ID3算法是一個(gè)典型的決策樹學(xué)習(xí)算法，其核心是在決策樹的各級節(jié)點(diǎn)上，使用信息增益方法作為屬性的選擇標(biāo)準(zhǔn)，來幫助確定生成每個(gè)節(jié)點(diǎn)時(shí)所應(yīng)采用的合適屬性。這樣就可以選擇具有最高信息增益屬性作為當(dāng)前節(jié)點(diǎn)的測試屬性，以便使用該屬性所劃分獲得的訓(xùn)練樣本子集進(jìn)行分類所需信息最小。定義1設(shè)U是論域，是U的一個(gè)劃分，其上有概率分布，則稱：為信源X的信息熵，其中對數(shù)取以2為底，而當(dāng)某個(gè)為零時(shí)，則可以理解為。定義2 設(shè)是一個(gè)信息源，即是U的另一個(gè)劃分，則已知信息源X是信息源Y的條件熵H(Y|X)定義為：其中為事件發(fā)生時(shí)信息源Y的條件熵。在ID3算法分類問題中，每

2、個(gè)實(shí)體用多個(gè)特征來描述，每個(gè)特征限于在一個(gè)離散集中取互斥的值。ID3算法的基本原理如下：設(shè)是n維有窮向量空間，其中是有窮離散符號集。E中的元素稱為樣本空間的例子，其中，。為簡單起見，假定樣本例子在真實(shí)世界中僅有兩個(gè)類別，在這種兩個(gè)類別的歸納任務(wù)中，PE和NE的實(shí)體分別稱為概念的正例和反例。假設(shè)向量空間E中的正、反例集的大小分別為P、N，由決策樹的基本思想，ID3算法是基于如下2種假設(shè)：（1）在向量空間E上的一棵正確的決策樹對任意樣本集的分類概率同E中的正、反例的概率一致。（2）根據(jù)定義1，一棵決策樹對一樣本集做出正確分類，所需要的信息熵為：如果選擇屬性A作為決策樹的根，A取V個(gè)不同的值，利用屬

3、性A可以將E劃分為V個(gè)子集，其中包含了E中屬性A取值的樣本數(shù)據(jù)，假設(shè)中含有個(gè)正例和個(gè)反例，那么子集所需要的期望信息是，以屬性A為根所需要的期望熵為：其中，以A為根的信息增益是：ID3算法選擇最大的屬性作為根節(jié)點(diǎn)，對的不同取值對應(yīng)的E的V個(gè)子集遞歸調(diào)用上述過程生成的的子節(jié)點(diǎn)。ID3算法的基本原理是基于兩類問題的，但是它很容易被擴(kuò)展到多類問題。設(shè)樣本集S共有C類樣本，每類的樣本數(shù)為。如果以屬性A作為決策樹的根，A具有V個(gè)值，它將E劃分為V個(gè)子集。假設(shè)中含有的第j類樣本個(gè)數(shù)為，那么子集的信息量，即熵為：以A為根分類后的信息熵為：選擇屬性，使最小，信息增益將最大。實(shí)際上，能正確分類訓(xùn)練集的決策樹不止一

4、棵。ID3算法能得出節(jié)點(diǎn)最小的決策樹。在ID3算法的每一個(gè)循環(huán)過程中，都對訓(xùn)練集進(jìn)行查詢以確定屬性的信息增益，然而此時(shí)的工作只是查詢樣本的子集而沒有對其分類。為了避免訪問全部數(shù)據(jù)集，ID3算法采用了稱為窗口（Windows）的方法，窗口隨機(jī)性是從數(shù)據(jù)集中選擇一個(gè)子集。采用該方法會大大加快構(gòu)建決策樹的速度。ID3算法的主算法非常簡單，首先從訓(xùn)練集中隨機(jī)選擇一個(gè)窗口（既含正例又含反例的樣本子集），對當(dāng)前的窗口形成一棵決策樹；其次，對訓(xùn)練集（窗口除外）中例子用所得到的決策樹進(jìn)行類別判定，找出錯(cuò)判的例子。若存在錯(cuò)判的例子，把他們插入窗口，轉(zhuǎn)到建樹過程，否則停止。算法每迭代循環(huán)一次，生成的決策樹將會不同

5、。ID3算法以一種從簡單到復(fù)雜的爬山策略遍歷這個(gè)假設(shè)空間，從空的樹開始，然后逐步考慮更加復(fù)雜的假設(shè)。通過觀察搜索空間和搜索策略，我們可以發(fā)現(xiàn)，它同樣存在著一些優(yōu)勢和不足。ID3算法的優(yōu)點(diǎn)：（1）ID3算法的假設(shè)空間包含所有的決策樹，搜索空間也是完整的假設(shè)空間。因?yàn)槊總€(gè)有限離散值函數(shù)可以被表示為某個(gè)決策樹，所以它避免了假設(shè)空間可能不包含目標(biāo)函數(shù)的風(fēng)險(xiǎn)。（2）ID3算法在搜索的每一步都使用當(dāng)前的所有訓(xùn)練樣本，以信息增益的標(biāo)準(zhǔn)為基礎(chǔ)決定怎樣簡化當(dāng)前的假設(shè)。使用信息增益這一統(tǒng)計(jì)屬性的一個(gè)優(yōu)點(diǎn)是大大降低了對個(gè)別訓(xùn)練樣例錯(cuò)誤的敏感性，因此，通過修改算法可以很容易地?cái)U(kuò)展到處理含有噪聲的訓(xùn)練樣本。（3）ID3

6、算法采用自頂向下的搜索策略，搜索全部空間的一部分，確保所作的測試次數(shù)較少，分類速度較快。算法的計(jì)算時(shí)間與樣本例子個(gè)數(shù)、特征個(gè)數(shù)、節(jié)點(diǎn)個(gè)數(shù)三者的乘積呈線性關(guān)系。（4）ID3算法與最基礎(chǔ)的決策樹算法一樣，非常適合處理離散值樣本數(shù)據(jù)，并且利用樹型結(jié)構(gòu)的分層的效果，可以輕而易舉地提取到容易理解的If-Then分類規(guī)則。（5）由于引進(jìn)了信息熵的概念，ID3算法能得出節(jié)點(diǎn)數(shù)最少的決策樹。ID3算法存在的不足之處（1）當(dāng)遍歷決策樹空間時(shí)，ID3算法僅維護(hù)單一的當(dāng)前假設(shè)，它失去了表示所有一致假設(shè)帶來的優(yōu)勢。比如，它不能判斷有多少其他的決策樹也是與現(xiàn)有的訓(xùn)練數(shù)據(jù)一致的，或者使用新的實(shí)例查詢來最優(yōu)地區(qū)分這些競爭的

7、假設(shè)。（2）ID3算法在搜索中不進(jìn)行回溯，每當(dāng)在樹的某一層選擇了一個(gè)屬性進(jìn)行測試，它不會再回溯重新考慮這個(gè)選擇。這樣，算法容易收斂到局部最優(yōu)的答案，而不是全局最優(yōu)的。（3）ID3算法使用的基于互信息的計(jì)算方法依賴于屬性值數(shù)目較多的屬性，但是屬性值較多的屬性不一定是分類最優(yōu)的屬性。（4）ID3算法是一種貪心算法，對于增量式學(xué)習(xí)任務(wù)來說，由于它不能增量地接受訓(xùn)練樣例，使得每增加一次實(shí)例都必須拋棄原有的決策樹，重新構(gòu)造新的決策樹，造成極大的開銷。所以，ID3算法不適合于漸進(jìn)學(xué)習(xí)。（5）ID3算法啊對噪聲較為敏感。Quinlan定義噪聲未訓(xùn)練樣本數(shù)據(jù)中的屬性值錯(cuò)誤和分類類別錯(cuò)誤。（6）ID3算法將注意力集中在屬性的選擇上，而這種方式已受到一些