ID3 決策樹

西瓜數據集D如下:

編號	色澤	根蒂	敲聲	紋理	臍部	觸感	好瓜
1	青綠	蜷縮	濁響	清晰	凹陷	硬滑	是
2	烏黑	蜷縮	沉悶	清晰	凹陷	硬滑	是
3	烏黑	蜷縮	濁響	清晰	凹陷	硬滑	是
4	青綠	蜷縮	沉悶	清晰	凹陷	硬滑	是
5	淺白	蜷縮	濁響	清晰	凹陷	硬滑	是
6	青綠	稍蜷	濁響	清晰	稍凹	軟粘	是
7	烏黑	稍蜷	濁響	稍糊	稍凹	軟粘	是
8	烏黑	稍蜷	濁響	清晰	稍凹	硬滑	是
9	烏黑	稍蜷	沉悶	稍糊	稍凹	硬滑	否
10	青綠	硬挺	清脆	清晰	平坦	軟粘	否
11	淺白	硬挺	清脆	模糊	平坦	硬滑	否
12	淺白	蜷縮	濁響	模糊	平坦	軟粘	否
13	青綠	稍蜷	濁響	稍糊	凹陷	硬滑	否
14	淺白	稍蜷	沉悶	稍糊	凹陷	硬滑	否
15	烏黑	稍蜷	濁響	清晰	稍凹	軟粘	否
16	淺白	蜷縮	濁響	模糊	平坦	硬滑	否
17	青綠	蜷縮	沉悶	稍糊	稍凹	硬滑	否

即集合D為分類問題,分類瓜的好壞是一個二分類問題,故|y| =2 ,故只存在p1,p2

信息熵為衡量信息混亂程度的量
記好瓜比例為p1,壞瓜比例為p2

$1.若全是好瓜,則p_1=1,p_2=0 \\ Ent(D) = -\sum\limits _{k=1}^{|y|}p_klog_2p_k \\= -(p_1log_2p_1 + p_2log_2p_2 ) \\=1\cdot log_2\cdot 1 + 0\cdot log_2\cdot 0 \\=0\\ 2.若全是好瓜,則p_1=0,p_2=1 \\ Ent(D) = -\sum\limits _{k=1}^{|y|}p_klog_2p_k \\= -(p_1log_2p_1 + p_2log_2p_2 ) \\=0\cdot log_2\cdot 0 + 1\cdot log_2\cdot 1 \\=0\\ 則完全不混亂為全是好瓜或全是壞瓜,Ent(D) = 0\\ 2.若全是好壞瓜個一半,則p_1=\frac12,p_2=\frac12 \\ Ent(D) = -\sum\limits _{k=1}^{|y|}p_klog_2p_k \\= -(p_1log_2p_1 + p_2log_2p_2 ) \\=-(\frac12\cdot log_2\cdot \frac12 + \frac12\cdot log_2\cdot \frac12 )\\=1\\ 則最混亂為Ent(D) = 1$

當前樣本集合D中第k類樣本所占比例為pk(k=1,2,3,…,|y|),則D的信息熵為:

$-\sum\limits _{k=1}^{|y|}p_klog_2p_k$

信息增益為:

$\sum\limits _{v=1}^V \frac{|Dv|}{|D|}Ent(D^v)$

import math
D = [
['青綠','蜷縮','濁響','清晰','凹陷','硬滑','是'],
['烏黑','蜷縮','沉悶','清晰','凹陷','硬滑','是'],
['烏黑','蜷縮','濁響','清晰','凹陷','硬滑','是'],
['青綠','蜷縮','沉悶','清晰','凹陷','硬滑','是'],
['淺白','蜷縮','濁響','清晰','凹陷','硬滑','是'],
['青綠','稍蜷','濁響','清晰','稍凹','軟粘','是'],
['烏黑','稍蜷','濁響','稍糊','稍凹','軟粘','是'],
['烏黑','稍蜷','濁響','清晰','稍凹','硬滑','是'],
['烏黑','稍蜷','沉悶','稍糊','稍凹','硬滑','否'],
['青綠','硬挺','清脆','清晰','平坦','軟粘','否'],
['淺白','硬挺','清脆','模糊','平坦','硬滑','否'],
['淺白','蜷縮','濁響','模糊','平坦','軟粘','否'],
['青綠','稍蜷','濁響','稍糊','凹陷','硬滑','否'],
['淺白','稍蜷','沉悶','稍糊','凹陷','硬滑','否'],
['烏黑','稍蜷','濁響','清晰','稍凹','軟粘','否'],
['淺白','蜷縮','濁響','模糊','平坦','硬滑','否'],
['青綠','蜷縮','沉悶','稍糊','稍凹','硬滑','否']
]
A = ['色澤','根蒂','敲聲','紋理','臍部','觸感','好瓜']# 當前樣本集合D中第k類樣本所占比例為pk(k=1,2,3,…,|y|)
# 計算A的信息熵,以數據最后一列為分類
def getEnt(D):# 獲取一個類型k->出現次數的mapkMap = dict()for dLine in D:# 獲取分類值kk = dLine[len(dLine) - 1]# 獲取當前k出現的次數kNum = kMap.get(k)if  kNum is None:kMap[k] = 1else:kMap[k] = kNum + 1# 遍歷mapdLen = len(D)rs = 0for kk in kMap:pk = kMap[kk]/dLenrs = rs + pk * math.log2(pk)return -rs# 求信息增益,aIndex為屬性列號
def getGain(D,aIndex):dMap = dict()for dLine in D:# 獲取屬性k = dLine[aIndex]# 屬性所屬的數組dChildren = dMap.get(k)if  dChildren is None:dChildren = []dMap[k] = dChildrendChildren.append(dLine)rs = 0    for key in dMap:dChildren = dMap[key]entx = getEnt(dChildren)print(entx)r = len(dChildren)/len(D) * entxrs = rs + rreturn getEnt(D) - rs

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/39390.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/39390.shtml
英文地址，請注明出處：http://en.pswp.cn/news/39390.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！