参考资料:
李航《统计学习方法》
《机器学习实战》
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)——回归树
决策树用于拟合带有附加噪声观测的正弦曲线。因此,它学习了逼近正弦曲线的局部线性回归。(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集成算法的一种。理论上来说,随机森林的表现要好于决策树。
评论(0)
您还未登录,请登录后发表或查看评论