Day |
Outlook |
Temperature |
Humidity |
Wind |
PlayTennis |
1 |
Sunny |
Hot |
High |
Weak |
No |
2 |
Sunny |
Hot |
High |
Strong |
No |
3 |
Overcast |
Hot |
High |
Weak |
Yes |
4 |
Rain |
Mild |
High |
Weak |
Yes |
5 |
Rain |
Cool |
Normal |
Weak |
Yes |
6 |
Rain |
Cool |
Normal |
Strong |
No |
7 |
Overcast |
Cool |
Normal |
Strong |
Yes |
8 |
Sunny |
Mild |
High |
Weak |
No |
9 |
Sunny |
Cool |
Normal |
Weak |
Yes |
10 |
Rain |
Mild |
Normal |
Weak |
Yes |
11 |
Sunny |
Mild |
Normal |
Strong |
Yes |
12 |
Overcast |
Mild |
High |
Strong |
Yes |
13 |
Overcast |
Hot |
Normal |
Weak |
Yes |
14 |
Rain |
Mild |
High |
Strong |
No |
对于上面例子,如何判断是否要去playtennis?
可以采用决策树的方式。
决策树是一种以实例为基础的归纳学习算法。从无序列/无规则的数据中,推导出树形表示的分类判决。
优点:计算量小、显示清晰
缺点:容易过拟合(需要修枝)(譬如,使用day做判决,一一对应虽然很准确,但是不能用在其他地方)、对时间顺序的数据,需要过多预处理工作
ID3算法:
1、对于实例,计算各个属性的信息增益
2、对于信息增益最大的属性P作为根节点,P的各个取值的样本作为子集进行分类
3、对于子集下,若只含有正例或反例,直接得到判决;否则递归调用算法,再次寻找子节点
熵:表示随机变量的不确定性。
条件熵:在一个条件下,随机变量的不确定性。
信息增益:熵 – 条件熵,在一个条件下,信息不确定性减少的程度。
用信息增益最大的属性作为结点,是因为最终去不去打球的不确定性,在获得该属性的结果后,不确定性大大降低。
也就是说,该属性对于打球的选择很重要。
对于解决上述问题,
首先,计算系统熵,PlayTennis
P(No) = 5/14
P(Yes) = 9/14
Entropy(S) = -(9/14)*log(9/14)-(5/14)*log(5/14) = 0.94
然后,计算各个属性的熵。
譬如:Wind
其中,Wind中取值为weak的记录有8条,其中,playtennis的正例6个,负例2个;取值为strong的记录有6条,正例为3个,负例为3个。
Entrogy(weak) = -(6/8)*log(6/8)-(2/8)*log(2/8) = 0.811
Entrogy(strong) = -(3/6)*log(3/6)-(3/6)*log(3/6) = 1.0
对应的信息增益为:
Gain(Wind) = Entropy(S) – (8/14)* Entrogy(weak)-(6/14)* Entrogy(strong) = 0.048
同理,Gain(Humidity = 0.151;Gain(Outlook = 0.247;Gain(Temperature = 0.029
此时,可以得到跟节点为:Outlook
对应点决策树:
Outlook分为三个集合:
Sunny:{1,2,8,9,11},正例:2、反例:3
Overcast:{3,7,12,13},正例:4、反例:0
Rain:{4,5,6,10,14},正例:3、反例:2
至此,可以得到:
Sunny:
Day |
Outlook |
Temperature |
Humidity |
Wind |
PlayTennis |
1 |
Sunny |
Hot |
High |
Weak |
No |
2 |
Sunny |
Hot |
High |
Strong |
No |
8 |
Sunny |
Mild |
High |
Weak |
No |
9 |
Sunny |
Cool |
Normal |
Weak |
Yes |
11 |
Sunny |
Mild |
Normal |
Strong |
Yes |
Entropy(S) = -(3/5)*log(3/5)-(2/5)*log(2/5) = 0.971
对于Wind,weak时,正例为1,反例为2;Strong时,正例为1,反例为1.
Entrogy(weak) = -(1/3)*log(1/3)-(2/3)*log(2/3) = 0.918
Entrogy(strong) = -(1/2)*log(1/2)-(1/2)*log(1/2) = 1
Gain(Wind) = Entropy(S) – 3/5* Entrogy(weak)-2/5* Entrogy(strong) = 0.0202
同理,Gain(Humidity) = 0.971;Gain(Temperature) = 0.571
此时,可以画出部分决策树:
其中,python代码:
import math #香农公式计算信息熵 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 = [['sunny', 'hot','high','weak', 'no' ], ['sunny', 'hot','high','strong', 'no' ], ['overcast', 'hot','high','weak', 'yes' ], ['rain', 'mild','high','weak', 'yes' ], ['rain', 'cool','normal','weak', 'yes' ], ['rain', 'cool','normal','strong', 'no' ], ['overcast', 'cool','normal','strong', 'yes' ], ['sunny', 'mild','high','weak', 'no' ], ['sunny', 'cool','normal','weak', 'yes' ], ['rain', 'mild','normal','weak', 'yes' ], ['sunny', 'mild','normal','strong', 'yes' ], ['overcast', 'mild','high','strong', 'yes' ], ['overcast', 'hot','normal','weak', 'yes' ], ['rain', 'mild','high','strong', 'no' ], ] labels = ['outlook', 'temperature', 'humidity', 'wind'] return dataset, labels #选取属性axis的值value的样本表 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 return max(classCount) 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() tree = createTree(myDat,labels) print tree
在计算决策树的时候,sklearn库提供了决策树的计算方法(tree),但是,这个库提供的是:
scikit-learn uses an optimised version of the CART algorithm.
对于本文中使用的ID3算法是不支持的。
然而https://pypi.python.org/pypi/decision-tree-id3/0.1.2
该库支持ID3算法。
按照官网说明,注意安装时的依赖库的版本,该升级的升级,该安装的安装即可。‘
from id3 import Id3Estimator from id3 import export_graphviz X = [['sunny', 'hot', 'high', 'weak'], ['sunny', 'hot', 'high', 'strong'], ['overcast', 'hot', 'high', 'weak'], ['rain', 'mild', 'high', 'weak'], ['rain', 'cool', 'normal', 'weak'], ['rain', 'cool', 'normal', 'strong'], ['overcast', 'cool', 'normal', 'strong'], ['sunny', 'mild', 'high', 'weak'], ['sunny', 'cool', 'normal', 'weak'], ['rain', 'mild', 'normal', 'weak'], ['sunny', 'mild', 'normal', 'strong'], ['overcast', 'mild', 'high', 'strong'], ['overcast', 'hot', 'normal', 'weak'], ['rain', 'mild', 'high', 'strong'], ] Y = ['no','no','yes','yes','yes','no','yes','no','yes','yes','yes','yes','yes','no'] f = ['outlook','temperature','humidity','wind'] estimator = Id3Estimator() estimator.fit(X, Y,check_input=True) export_graphviz(estimator.tree_, 'tree.dot', f)
然后通过GraphViz工具生成PDF
dot -Tpdf tree.dot -o tree.pdf
结果:
当然,你也可以进行预测判断:
print estimator.predict([['rain', 'mild', 'high', 'strong']])
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/119485.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...