第121天：机器学习之决策树
决策树（Decision Tree）
决策树是一种分类回归算法，决策树采用的是树形结构。每一个内部节点表示对于特征属性的判断，每一个分支就代表对这个特征属性判断的输出，每一个叶节点就是对决策结果的分类。
举个例子：在贷款买房、买车时，为了防止不良贷款，银行一般会看借款人的银行流水是否合格，如：月收入是否达标、时间是否合规、流水是否是造假。
决策树是一种常用的分类方法，是监督学习的一种，需要给出一些数据集样本，这些样本中包括了特征属性、决策分类的结果。通过这些数据集样本能够得到一个决策树，通过决策树得出新样本的分类结果。决策树的优点是计算的复杂度不高、输出结果容易理解、对中间值的缺省不敏感。缺点是可能产生过度匹配的问题。
特征属性
在构造决策树时，需要解决的第一个问题就是，在数据集样本中，每个样本都有许多特征属性，每个特征属性对决策结果的影响都有大有小。为了找到那些决定性的特征，必须对每个特征进行评估、选择。对每个特征属性进行评估、选择就是对数据集的划分，一个数据集将被分为多个数据子集。
在选择特征属性时通常使用的方法为：信息增益。
信息增益
在选择特征属性之前和之后数据集发生的变化称之为信息增益。只要知道如何计算信息增益，就可以知道哪个特征属性就是最好的选择。
集合信息的度量方式被称为：香浓熵或者简称为熵。熵：信息的期望值，集合的无序程度，熵越大表示集合越无序，熵越小表示集合越有序。
如果待分类的数据集中可能会划分出多个分类，则符号 x~i~ 的信息定义为
其中 p(x~i~) 是这个分类的概率。
通过下面的公式可以得到所有类别的信息期望值，n 是分类的数目:
ID3.5 算法
ID3.5 算法的核心思想是在决策树各个结点上选择最优的信息增益得出特征属性，递归地构建决策树，直到没有特征选择为止。最后得到一个决策树。
举个例子使用 ID3.5 算法计算熵与信息增益，下表是简单的银行流水是否达标
| 申请人序号 | 月收入是否达标 | 时间是否合规 | 流水是否造假 | 银行流水是否达标 |
|---|---|---|---|---|
| 1 | 是 | 是 | 否 | 是 |
| 2 | 是 | 是 | 否 | 是 |
| 3 | 是 | 否 | 否 | 否 |
| 4 | 否 | 是 | 否 | 否 |
| 5 | 否 | 否 | 是 | 否 |
| 6 | 是 | 否 | 是 | 否 |
| 7 | 是 | 是 | 是 | 否 |
使用 ID3.5 算法计算上表中熵的值，把【是】用 1 表示，【否】用 0 表示，最后是否达标用 y/n 表示
from math import logdef createDataSet():'''创建数据集'''dataSet = [[1, 1, 0, 'y'],[1, 1, 0, 'y'],[1, 0, 0, 'n'],[0, 1, 0, 'n'],[0, 0, 1, 'n'],[1, 0, 1, 'n'],[1, 1, 1, 'n']]labels = ['Salary', 'Time', 'Bank flow']return dataSet,labelsdef calcEntropy(dataSet):'''计算熵:param dataSet: 数据集:return: 熵值'''numEntries = len(dataSet)labelCounts = {}for line in dataSet:currentLabel = line[-1]if currentLabel not in labelCounts.keys():labelCounts[currentLabel] = 0labelCounts[currentLabel] += 1entropy = 0.0for key in labelCounts:prob = float(labelCounts[key]) / numEntriesentropy -= prob * log(prob, 2)return entropymydata = createDataSet()entropy = calcEntropy(mydata)print('熵值为：', entropy)
示例结果
熵值为：0.863120568566631
熵值越大表示集合越无序，熵越小表示集合越有序。
下面使用 Python 代码计算出示例中的最优特征
def splitDataSet(dataSet,axis,value):'''划分数据集:param dataSet: 按照给定特征划分数据集:param axis: 划分数据集的特征:param value: 需要返回的特征的值:return: 经验熵'''retDataSet=[]for featVec in dataSet:if featVec[axis]==value:reducedFeatVec=featVec[:axis]reducedFeatVec.extend(featVec[axis+1:])retDataSet.append(reducedFeatVec)return retDataSetdef chooseBestFeatureToSplit(dataSet):'''计算数据集的熵:param dataSet: 数据集:return: 最优的特征值的索引'''# 特征个数numFeatures = len(dataSet[0]) - 1# 数据集的熵baseEntropy = calcEntropy(dataSet)# 最优信息增益bestInfoGain = 0.0# 最优特征的索引值bestFeature = -1for i in range(numFeatures):# 获取数据集的第 i 个所有特征featList = [example[i] for example in dataSet]#创建 set集合{}，元素不可重复uniqueVals = set(featList)# 经验条件熵newEntropy = 0.0#计算信息增益for value in uniqueVals:# 数据集划分后的子集subDataSet = splitDataSet(dataSet, i, value)# 计算子集的概率prob = len(subDataSet) / float(len(dataSet))# 根据公式计算经验条件熵newEntropy += prob * calcEntropy((subDataSet))# 信息增益infoGain = baseEntropy - newEntropy# 打印每个特征的信息增益print("第%d个特征属性的信息增益为%.3f" % (i, infoGain))if (infoGain > bestInfoGain):bestInfoGain = infoGainbestFeature = ireturn bestFeaturemydata = createDataSet()print("最优的索引值为：", str(chooseBestFeatureToSplit(mydata)))
示例结果
第0个特征属性的信息增益为0.170第1个特征属性的信息增益为0.292第2个特征属性的信息增益为0.292最优的索引值为：1
在计算出第二个最优特征属性后，可以继续使用递归方式计算第二个最优特征属性，直至得出所有可能的决策类别。
下面构建决策树
import operatordef majorityCnt(classList):'''类别数多的类别:param classList: 类别:return: 返回类别数多的类别'''classCount={}for vote in classList:if vote not in classCount.keys(): classCount[vote] = 0classCount[vote] += 1sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)return sortedClassCount[0][0]def createTree(dataSet,labels):'''构建决策树:param dataSet: 数据集样本:param labels: 特征属性:return: 决策树'''# 决策类别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)# 返回最优的特征属性bestFeature = chooseBestFeatureToSplit(dataSet)bestFeatLabel = labels[bestFeature]myTree = {bestFeatLabel:{}}del(labels[bestFeature])# 最优特征值featureValues = [example[bestFeature] for example in dataSet]uniqueVals = set(featureValues)for value in uniqueVals:subLabels = labels[:]myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeature, value), subLabels)return myTree
示例结果
第0个特征属性的信息增益为0.170第1个特征属性的信息增益为0.292第2个特征属性的信息增益为0.292第0个特征属性的信息增益为0.311第1个特征属性的信息增益为0.311第0个特征属性的信息增益为0.918{'Time': {0: 'n', 1: {'Salary': {0: 'n', 1: {'Bank flow': {0: 'y', 1: 'n'}}}}}}总结
简单的介绍了决策树和 ID3.5 算法，用了一个示例构造了一个简单的决策树，希望对大家有所帮助。
示例代码：https://github.com/JustDoPython/python-100-day/tree/master/day-121
©著作权归作者所有：来自51CTO博客作者mob604756e8ada8的原创作品，如需转载，请注明出处，否则将追究法律责任
更多相关文章
- Top4 数据科学竞赛解决方案 | 附带报告+方案+代码讲解+数据集
- 基于 Flink 的实时特征平台在携程的应用
- 推荐系统中模型训练及使用流程的标准化
- 视频 | 阿里文娱智能营销增益模型（uplift model）技术实践
- 深度时空网络、记忆网络与特征表达学习在 CTR 预估中的应用
- 多媒体内容理解在美图社区的应用实践
- 全基因组分析揭示长非编码RNA的差异表观特征模式
- 浅谈SVM三特征模型的可视化与拟合度的分析
- Spark SQL用UDF实现按列特征重分区