决策树

image.png
image.png

正方形代表判断模块，椭圆形代表终止模块，从判断模块引出的左右键头称作分支。
决策树很多任务都是为了数据中所蕴含的知识信息，因此决策树可以使用不熟悉的数据集合，并从中提取出一系列规则，机器学习算法最终将使用这个机器从数据集中创造的规则。

在构造决策树时，需要解决的第一个问题是，当前数据集上哪个
特征在划分数据分类时起决定性作用。为了找到决定性的特征，划分出最好的结果，必须评估每个特征。完成测试之后，原始数据集就被划分为几个数据子集。这些数据子集会分布在第一个决策点的所有分支上。如果某个分支下的数据属于同一类型，则当前无需阅读的垃圾邮件已经正确地划分数据分类，无需进一步对数据集进行分割。如果数据子集内的数据不属于同一类型，则需要重复划分数据子集的过程。如何划分数据子集的算法和划分原始数据集的方法相同，直到所有具有相同类型的数据均在一个数据子集内。

image.png

信息增益

划分数据集的大原则是：将无序的数据变得更加有序。使用信息论度量信息，信息论是量化处理信息的分支科学。
在划分数据集之前之后信息发生的变化称为信息增益，获得信息增益最高的特征是最好的选择。

集合信息的度量方式称为香农熵或者简称为熵。熵定义为信息的期望值。如果待分类的事物可能划分在多个分类中，则符号xi的信息定义为 image.png
其中p(xi)是选择该分类的概率。
计算熵需所有类别所有可能值包含的信息期望值， image.png

其中n是分类的数目。

#计算给定数据集的香农熵
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*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

Debug1:
IndentationError: unexpected indent
解决方法：
文件里格式不对，可能是tab和空格没对齐的问题
检查代码调整格式

Debug2:
TypeError: list indices must be integers or slices, not tuple
解决方法:
矩阵元素之间要用逗号隔开

#输出
import trees
myDat,labels=trees.createDataSet()
print(myDat)
print(trees.calcShannonEnt(myDat))

输出：

[[1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
0.9709505944546686

得到熵之后，就可以按照获取最大信息增益的方法划分数据集。
另一个度量集合无序程度的方法是基尼不纯度，简单说就是从一个数据集中随机选取子项，度量其被错误分类到其他分组里的概率。