简述算法 上一章的kNN更像是应用统计知识来进行科学的预测,它可以完成许多分类任务。但是最大的缺点就是无法给出数据的内在含义,而决策树算法数据形式非常便于理解。决策树的结果经常会应用到专家系统当中。
【机器学习|【读书笔记】机器学习实战-决策树(1)】构建一棵决策树的流程:
检测数据集中每一个子祥的属性是否属于同一类
if so return 类标签;
else
寻找划分数据集的最好特征
划分数据集
创建分支结点
for 每个划分的子集
调用createBranch并增加返回结果到分支结点中
return 分支结点
决策树的一般流程
- 收集数据
- 准备数据:决策树算法只适用于标称型数据,数值数据必须离散化
- 分析数据:树构造完成之后检查是否符合预期
- 训练算法:构造树的数据结构
- 测试算法:计算错误率
书里用到的熵的计算方法如下:
文章图片
其中p(xi)是选择分类的概率
还有所有类别的信息期望值:
文章图片
完成上述计算熵的代码如下:‘
def calcShannonEnt(dataSet):
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet: #the the number of unique elements and their occurance
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 * log(prob,2) #log base 2
return shannonEnt
划分数据集 划分数据集的关键在于寻找恰当的特征值来进行划分。我们需要尝试数据集中的每一个特征值的划分并且计算该划分的熵。通过比较得出最终的结果。
根据给定特征值划分数据集:
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):
numFeatures = len(dataSet[0]) - 1#the last column is used for the labels
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 0.0;
bestFeature = -1
for i in range(numFeatures):#iterate over all the features
featList = [example[i] for example in dataSet]#create a list of all the examples of this feature
uniqueVals = set(featList)#get a set of unique values
newEntropy = 0.0
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet)/float(len(dataSet))
newEntropy += prob * calcShannonEnt(subDataSet)
#calculate the info gain;
ie reduction in entropy
infoGain = baseEntropy - newEntropy
#compare this to the best gain so far
if (infoGain > bestInfoGain):
#if better than current best, set to best
bestInfoGain = infoGain
bestFeature = i
#returns an integer
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]
这和之前kNN算法的投票部分非常相似。
接下来就是根据上述方法的创建决策树代码:
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:
#python中传入的参数为列表是使传入引用,所以这里复制一下
subLabels = labels[:]
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
return myTree
文章图片
推荐阅读
- 机器学习|【读书笔记】机器学习实战-决策树(2)
- 为什么Python是最适合机器学习的编程语言()
- GRE数据分析|数据分布,随机变量和概率分布
- 创建一个简单的机器学习模型
- ML算法(基于动量的梯度优化器介绍)
- ML算法(使用Python进行多元线性回归)
- ML算法(Python中数据集的一种热编码)
- ML算法(OPTICS聚类说明详细指南)
- ML算法(使用Sklearn实现OPTICS聚类)