参考资料:
李航《统计学习方法》
《机器学习实战》

1. 决策树模型

决策树(decision tree)是一种基本的分类与回归方法,其示意图如下图所示:

决策树由结点和有向边组成,结点分为内部结点(图中的圆形的结点)和叶结点(图中的方形的结点)。内部结点表示一个特征或者属性,叶结点表示一个类。决策树可以看做是一个if-then规则的集合,从根节点到叶结点的一条路径即构成一条规则。决策树的学习本质上是从训练数据集中归纳出一组分类规则,常用的学习算法有ID3、C4.5和CART。

2. 决策树的构造

2.1 特征选择与信息增益

前面说到,决策树的学习本质上是从训练数据集中归纳出一组分类规则,那么选择一组对训练数据具有分类能力的特征极其重要。特征选择是决定用哪个特征来划分特征空间。那么,我们怎么判断我们选择的特征是合适的呢?我们通过一个准则——信息增益(informaiton gain)来判断。

2.2 信息增益

定义:熵(entropy)——表示随机变量不确定性的度量。

假设X是一个取有限个值得离散随机变量,其概率分布为:

P(X=x_i)=p_i, i=1,2,\cdots, n

则随机变量X的熵定义为

H(X)=-\sum_{i=1}^n p_i \log p_i

如果p_i=0,则定义0 \log 0 =0

由定义可知,熵只依赖于X的分布,与X的取值无关。所以,也可以将X的熵记作H(p),即

H(p)=-\sum_{i=1}^n p_i \log p_i

熵越大,随机变量的不确定性就越大。

熵的计算代码如下(代码中取底为2的对数函数):

from math import log

def calEntropy(dataSet):
    # 这里dataSet的数据格式为[特征值1,特征值2,...,特征值n,分类标签]
    num = len(dataSet)
    labelCounts = {}
    for featVec in dataSet:
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts:
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    entropy = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/num
        entropy -= prob * log(prob, 2)
    return entropy

定义:信息增益(Information gain)表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。即,特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差。即:

g(D,A)=H(D)-H(D|A)

通俗地说,划分数据集的目的就是使无序的数据变得有序。信息增益表示的就是划分数据集前后信息发生的变化。在选择的过程中,我们对每一个选择标准都进行一次计算,选择信息增益最大的作为本次分类的标准。

选择的过程有两个关键的步骤:

(1)划分数据集

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

(2) 选择最好的数据集划分方式

def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0])-1
    baseEntropy = calEntropy(dataSet)
    bestInfoGain = 0.0
    bestFeature = -1
    for i in range(numFeatures):
        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 * calEntropy(subDataSet)
        infoGain = baseEntropy - newEntropy
        if (infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature() = i
    return bestFeature

2.3 决策树的生成——递归生成决策树

递归结束的条件是:程序遍历完所有划分数据集的属性,或者每个分支下的所有实例都具有相同的分类。

def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vot 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

3. 案例应用——使用决策树预测隐形眼镜类型

数据集下载:http://archive.ics.uci.edu/ml/machine-learning-databases/lenses/

我们先看一下这个数据集:

这个数据集特别简单,一共只有24个数据,第一列是序号。每个数据有4个特征,共有三个类别。这4个特征和分类如下所示:

分类结果的意义如下图所示:

因此,我们首先创建我们的数据输入:

import pandas as pd 

def createDataSet(filename):
    dataSet = []
    # header=None 表示读取无表头的数据文件
    data = pd.read_csv(filename, header=None)
    for i in range(len(data)):
        line = data.iloc[i]
        linedata = [int(line[0][3]),
                    int(line[0][6]),
                    int(line[0][9]),
                    int(line[0][12]),
                    int(line[0][15])]
        dataSet.append(linedata)
    return dataSet

myDat = createDataSet('lenses.data')
labels = ['age of the patient', 'spectacle prescription', 'astigmatic', 'tear production rate']

然后运行代码,创建决策树:

myTree = createTree(myDat, labels)
print(myTree)

可以得到结果:

{'tear production rate': {1: 3, 2: {'astigmatic': {1: {'age of the patient': {1: 2, 2: 2, 3: {'spectacle prescription': {1: 3, 2: 2}}}}, 2: {'spectacle prescription': {1: 1, 2: {'age of the patient': {1: 1, 2: 3, 3: 3}}}}}}}}

如果画成图来表示,则如下表示:

4. Decision Tree Regression(DTR)——回归树

参考资料
sklearn-Decision Tree Regression

决策树用于拟合带有附加噪声观测的正弦曲线。因此,它学习了逼近正弦曲线的局部线性回归。(The decision trees is used to fit a sine curve with addition noisy observation. As a result, it learns local linear regressions approximating the sine curve.)

先导入需要用到的包

import numpy as np
from sklearn.tree import DecisionTreeRegressor
import matplotlib.pyplot as plt

生成所需要的数据

rng = np.random.RandomState(1)
X = np.sort(5 * rng.rand(80, 1), axis=0)
y = np.sin(X).ravel()
y[::5] += 3 * (0.5 - rng.rand(16))

数据分布如下图所示:

训练模型:

regr_1 = DecisionTreeRegressor(max_depth=2)
regr_2 = DecisionTreeRegressor(max_depth=5)
regr_1.fit(X, y)
regr_2.fit(X, y)

训练结果:

5. 随机森林

在机器学习中,随机森林是一个包含多个决策树的分类器,属于bagging集成算法的一种。理论上来说,随机森林的表现要好于决策树。

推荐阅读:
随机森林(Random Forest)算法原理