算法思想
- 從數(shù)據(jù)集中找到一個(gè)特征,這個(gè)特征在劃分?jǐn)?shù)據(jù)分類中起決定性作用.為了找到這個(gè)特征,就要評(píng)估每個(gè)特征,找到區(qū)分度對(duì)好的呢個(gè)特征,將數(shù)據(jù)集分開(kāi).
- 劃分?jǐn)?shù)據(jù)集之前,之后信息發(fā)生的變化成為信息增益.每個(gè)特征劃分?jǐn)?shù)據(jù)獲取的信息增益,越大的,表示區(qū)分效果越好
信息增益(Information Gain)- 熵定義為信息的期望值. 越不確定的事件的信息熵越大,因?yàn)橐欢ǖ氖虑闆](méi)有信息量
(地球繞著太陽(yáng)轉(zhuǎn))
得了解的信息論基本概念
自信息量：一個(gè)事件（消息）本身所包含的信息量窄绒，由事件的不確定性決定的辅辩。
隨機(jī)事件Xi發(fā)生概率為P(xi)箩言，則隨機(jī)事件的自信息量定義為：
自信息量計(jì)算公式
信息熵(Entropy)：隨機(jī)變量自信息量I(xi)的數(shù)學(xué)期望（平均自信息量）逻杖，用H（X）表示蓝纲，即為熵的定義：
信息熵計(jì)算公式
動(dòng)手實(shí)踐
2票同意,3票不同意
同意的占40%,不同意的占60%,此時(shí)信息熵是0.970
將一個(gè)同意改為不確定的時(shí)候
{yes:2,no:3} -> {yes:1,not sure:1,no:3}
同意的占20%,不確定的占20%,不同意的占60%,此時(shí)信息熵是1.370
劃分?jǐn)?shù)據(jù)集
通過(guò)計(jì)算信息熵,可以衡量數(shù)據(jù)的無(wú)序程度
現(xiàn)在要計(jì)算,通過(guò)每個(gè)特征值劃分后的數(shù)據(jù)集的信息熵,然后判斷那個(gè)特征劃分后的數(shù)據(jù)集
選取信息熵最大的特征值,這相當(dāng)于讓剩下是數(shù)據(jù)更具確定性
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 0.0
bestFeature = -1
for i in range(numFeatures):
featList = [example[i] for example in dataSet] # 每一列的值,即一個(gè)feature所有的數(shù)據(jù)
print featList
uniqueVals = set(featList)
print uniqueVals
newEntropy = 0.0
for value in uniqueVals:
subDataSet = splitDataSet(dataSet,i,value)
print "subDataSet : %s" % subDataSet
prob = len(subDataSet)/float(len(dataSet))
print "prob : %f" % prob
print "calcShannonEnt: %f" % calcShannonEnt(subDataSet)
newEntropy += prob * calcShannonEnt(subDataSet)
print "new entropy : %f" % newEntropy
infoGain = baseEntropy - newEntropy
print "infoGain : %f" % infoGain
if (infoGain > bestInfoGain):
bestInfoGain = infoGain
bestFeature = i
return bestFeature
動(dòng)手實(shí)現(xiàn)一遍
原始數(shù)據(jù)
Paste_Image.png
處理為屬性和標(biāo)簽的形式
Paste_Image.png
計(jì)算該矩陣對(duì)應(yīng)的基準(zhǔn)信息熵(Base Entropy) = 0.97
算法開(kāi)始
1.選取特征A
Paste_Image.png
2.選取特征B
Paste_Image.png
3.因?yàn)镮G(A) = 0.42 > IG(B) = 0.17,所以對(duì)數(shù)據(jù)集最具有區(qū)分度的特征為第0個(gè)特征A.以此為依據(jù)構(gòu)建決策樹(shù)
Paste_Image.png
決策樹(shù)最終狀態(tài)
Paste_Image.png
