當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

决策树---ID3算法

發(fā)布時間：2024/4/24 编程问答 31 豆豆

生活随笔收集整理的這篇文章主要介紹了决策树---ID3算法小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

決策樹---ID3算法

決策樹：

以天氣數(shù)據(jù)庫的訓(xùn)練數(shù)據(jù)為例。

Outlook	Temperature	Humidity	Windy	PlayGolf?
sunny	85	85	FALSE	no
sunny	80	90	TRUE	no
overcast	83	86	FALSE	yes
rainy	70	96	FALSE	yes
rainy	68	80	FALSE	yes
rainy	65	70	TRUE	no
overcast	64	65	TRUE	yes
sunny	72	95	FALSE	no
sunny	69	70	FALSE	yes
rainy	75	80	FALSE	yes
sunny	75	70	TRUE	yes
overcast	72	90	TRUE	yes
overcast	81	75	FALSE	yes
rainy	71	91	TRUE	no

這個例子是根據(jù)報告天氣條件的記錄來決定是否外出打高爾夫球。

作為分類器，決策樹是一棵有向無環(huán)樹。

由根節(jié)點(diǎn)、葉節(jié)點(diǎn)、內(nèi)部節(jié)點(diǎn)、分割屬性、分割判斷規(guī)則構(gòu)成

生成階段：決策樹的構(gòu)建和決策樹的修剪。

根據(jù)分割方法的不同：有基于信息論（Information Theory）的方法和基于最小GINI指數(shù)（lowest GINI index）的方法。對應(yīng)前者的常見方法有ID3、C4.5，后者的有CART。

?ID3 算法

?????? ID3的基本概念是：

1）? 決策樹中的每一個非葉子節(jié)點(diǎn)對應(yīng)著一個特征屬性，樹枝代表這個屬性的值。一個葉節(jié)點(diǎn)代表從樹根到葉節(jié)點(diǎn)之間的路徑所對應(yīng)的記錄所屬的類別屬性值。這就是決策樹的定義。

2）? 在決策樹中，每一個非葉子節(jié)點(diǎn)都將與屬性中具有最大信息量的特征屬性相關(guān)聯(lián)。

3）? 熵通常是用于測量一個非葉子節(jié)點(diǎn)的信息量大小的名詞。

熵

熱力學(xué)中表征物質(zhì)狀態(tài)的參量之一，用符號S表示，其物理意義是體系混亂程度的度量。熱力學(xué)第二定律（second law of thermodynamics），熱力學(xué)基本定律之一，又稱“熵增定律”，表明在自然過程中，一個孤立系統(tǒng)的總混亂度（即“熵”）不會減小。

在信息論中，變量的不確定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大。信息熵是信息論中用于度量信息量的一個概念。一個系統(tǒng)越是有序，信息熵就越低；反之，一個系統(tǒng)越是混亂，信息熵就越高。所以，信息熵也可以說是系統(tǒng)有序化程度的一個度量。

?信息增益的計(jì)算

定義1：若存在個相同概率的消息，則每個消息的概率是,一個消息傳遞的信息量為。若有16個事件，則，需要4個比特來代表一個消息。

定義2：若給定概率分布，則由該分布傳遞的信息量稱為的熵，即

例：若是，則是1；若是，則是0.92；若

是，則是0（注意概率分布越均勻，其信息量越大）

定義3：若一個記錄的集合根據(jù)類別屬性的值被分為相互獨(dú)立的類，則識別的一個元素所屬哪個類別所需要的信息量是,其中是的概率分布，即

仍以天氣數(shù)據(jù)庫的數(shù)據(jù)為例。我們統(tǒng)計(jì)了14天的氣象數(shù)據(jù)(指標(biāo)包括outlook，temperature，humidity，windy)，并已知這些天氣是否打球(play)。如果給出新一天的氣象指標(biāo)數(shù)據(jù)，判斷一下會不會去打球。在沒有給定任何天氣信息時，根據(jù)歷史數(shù)據(jù)，我們知道一天中打球的概率是9/14，不打的概率是5/14。此時的熵為：

定義4：若我們根據(jù)某一特征屬性將分成集合，則確定中的一個元素類的信息量可通過確定的加權(quán)平均值來得到，即的加權(quán)平均值為：

Outlook			temperature	humidity	windy			play
?	yes	no	?	?	?	yes	no	yes	no
sunny	2	3			False	6	2	9	5
overcast	4	0			True	3	3	?	?
rainy	3	2			?	?	?	?	?

針對屬性O(shè)utlook，我們來計(jì)算

定義5：將信息增益定義為：

即增益的定義是兩個信息量之間的差值，其中一個信息量是需確定的一個元素的信息量，另一個信息量是在已得到的屬性的值后確定的一個元素的信息量，即信息增益與屬性相關(guān)。

針對屬性O(shè)utlook的增益值：

若用屬性windy替換outlook,可以得到，。即outlook比windy取得的信息量大。

ID3算法的Python實(shí)現(xiàn)

import math

import operator

def calcShannonEnt(dataset):

????numEntries = len(dataset)

????labelCounts = {}

????for featVec in dataset:

????????currentLabel = featVec[-1]

????????if currentLabel not in labelCounts.keys():

????????????labelCounts[currentLabel] = 0

????????labelCounts[currentLabel] +=1

?????????

????shannonEnt = 0.0

????for key in labelCounts:

????????prob = float(labelCounts[key])/numEntries

????????shannonEnt -= prob*math.log(prob, 2)

????return shannonEnt

?????

def CreateDataSet():

????dataset = [[1, 1, 'yes' ],

???????????????[1, 1, 'yes' ],

???????????????[1, 0, 'no'],

???????????????[0, 1, 'no'],

???????????????[0, 1, 'no']]

????labels = ['no surfacing', 'flippers']

????return dataset, labels

def splitDataSet(dataSet, axis, value):

????retDataSet = []

????for featVec in dataSet:

????????if featVec[axis] == value:

????????????reducedFeatVec = featVec[:axis]

????????????reducedFeatVec.extend(featVec[axis+1:])

????????????retDataSet.append(reducedFeatVec)

?????

????return retDataSet

def chooseBestFeatureToSplit(dataSet):

????numberFeatures = len(dataSet[0])-1

????baseEntropy = calcShannonEnt(dataSet)

????bestInfoGain = 0.0;

????bestFeature = -1;

????for i in range(numberFeatures):

????????featList = [example[i] for example in dataSet]

????????uniqueVals = set(featList)

????????newEntropy =0.0

????????for value in uniqueVals:

????????????subDataSet = splitDataSet(dataSet, i, value)

????????????prob = len(subDataSet)/float(len(dataSet))

????????????newEntropy += prob * calcShannonEnt(subDataSet)

????????infoGain = baseEntropy - newEntropy

????????if(infoGain > bestInfoGain):

????????????bestInfoGain = infoGain

????????????bestFeature = i

????return bestFeature

def majorityCnt(classList):

????classCount ={}

????for vote in classList:

????????if vote not in classCount.keys():

????????????classCount[vote]=0

????????classCount[vote]=1

????sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)

????return sortedClassCount[0][0]

def createTree(dataSet, labels):

????classList = [example[-1] for example in dataSet]

????if classList.count(classList[0])==len(classList):

????????return classList[0]

????if len(dataSet[0])==1:

????????return majorityCnt(classList)

????bestFeat = chooseBestFeatureToSplit(dataSet)

????bestFeatLabel = labels[bestFeat]

????myTree = {bestFeatLabel:{}}

????del(labels[bestFeat])

????featValues = [example[bestFeat] for example in dataSet]

????uniqueVals = set(featValues)

????for value in uniqueVals:

????????subLabels = labels[:]

????????myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)

????return myTree

?????????

myDat,labels = CreateDataSet()

createTree(myDat,labels)

運(yùn)行結(jié)果如下：

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的决策树---ID3算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。

上一篇： Python递归实现汉诺塔
下一篇： ubuntu下超级用户和普通用户