范文无忧网数据挖掘入门与实战 公众号： datadw
1 决策树/判定树（decision tree)
1 决策树（Dicision Tree）是机器学习有监督算法中分类算法的一种，有关机器学习中分类和预测算法的评估主要体现在：
准确率：预测的准确与否是本算法的核心问题，其在征信系统，商品购买预测等都有应用。
速度：一个好的算法不仅要求具备准确性，其运行速度也是衡量重要标准之一。
强壮行：具备容错等功能和扩展性等。
可规模性：能够应对现实生活中的实际案例
可解释性：运行结果能够说明其含义。
2 判定树是一个类似于流程图的树结构：其中，每个内部结点表示在一个属性上的测试，每个分支代表一个属性输出，而每个树叶结点代表类或类分布。树的最顶层是根结点。
如上案例判断是否去打球？根节点显示14天中9天适合打球，其中5天不适合打球。这里面没有全部一致的情况，说明还需要细分：
1 晴天：晴天中有2天适合打球，3天不适合打球，还需细分①湿度小于等于70时候有2天都适合打球，停止划分；②湿度大于70有3天都不适合打球，停止划分。
2 阴天：共4天都适合打球，停止划分。
3 雨天：3天适合打球，2天不适合打球，继续划分。①没有风的有3天且都适合打球，停止划分；②有风的2天且都不适合打球，停止划分。
注意：有的时候不易太细的划分，特征过多过细的话反而会影响预测的准确率。把大多数归为一类，极少数的可以归到大多数之中。
案例：如上决策树，如果某天是：晴天，湿度90 判定是否适合打球，可以由图知是不适合打球的。
3 官方文档： http://scikit-learn.org/stable/modules/tree.html
2 构造决策树的基本算法：判定顾客对商品购买能力
2.1 算法结果图：
根据决策树分析如下客户数据，判定新客户购买力。其中
客户年龄age：青年、中年、老年
客户收入income：低、中、高
客户身份student：是学生，不是学生
客户信用credit_rating：信用一般，信用好
是否购买电脑buy_computer：购买、不购买
2.2 在介绍决策树算法之前，我们引入熵的概念。熵的（entropy）概念：信息和抽象，如何度量？
1948年，香农提出了 ”信息熵(entropy)“的概念，一条信息的信息量大小和它的不确定性有直接的关系，要搞清楚一件非常非常不确定的事情，或者是我们一无所知的事情，需要了解大量信息==>信息量的度量就等于不确定性的多少。
例子：猜世界杯冠军，假如一无所知，猜多少次？每个队夺冠的几率不是相等的，比特(bit)来衡量信息的多少。
采用如下方式求信息熵：
1 当每个球队夺冠概率相等时候，32支参加世界杯夺冠球队的信息熵是5，计算是2^5=32，也就是你5次可以猜对那支球队夺冠。
2 当球队夺冠概率不相等，比如巴西、德国、荷兰是强队概率较大，信息熵就小于5，也就是你用不到5次就可以猜出哪个球队夺冠。
注：变量的不确定性越大，熵也就越大
2.3 决策树归纳算法 （ID3）
1970-1980， J.Ross. Quinlan首先提出ID3算法，第一步是选择属性判断结点，我们采用信息熵的比较。第二步是信息获取量(Information Gain)：Gain(A) = Info(D) - Infor_A(D)通过A来作为节点分类获取了多少信息
详解：信息获取量/信息增益(Information Gain)：Gain(A) = Info(D) - Infor_A(D)，例如age的信息增益，Gain(age) = Info(buys_computer) - Infor_age(buys_computer)。Info(buys_computer)是这14个记录中，购买的概率9/14，不购买的5/14，带入到信息熵公式。
Infor_age(buys_computer)是age属性中，青年5/14购买概率是2/5,不购买3/5;中年4/14购买概率是1,不购买概率是0,老年5/14购买概率3/5，不购买概率是2/5.分别代入信息熵公式Info(buys_computer)与Infor_age(buys_computer)做差，即是age的信息增益，具体如下：
类似，Gain(income) = 0.029, Gain(student) = 0.151, Gain(credit_rating)=0.048
所以，选择信息增益最大的作为根节点即age作为第一个根节点
重复计算即可
2.4 决策树算法：
决策树算法的形式化描述如下：
树以代表训练样本的单个结点开始（步骤1）。
如果样本都在同一个类，则该结点成为树叶，并用该类标号（步骤2 和3）。
否则，算法使用称为信息增益的基于熵的度量作为启发信息，选择能够最好地将样本分类的属性（步骤6）。该属性成为该结点的“测试”或“判定”属性（步骤7）。在算法的该版本中，
所有的属性都是分类的，即离散值。连续属性必须离散化。
对测试属性的每个已知的值，创建一个分枝，并据此划分样本（步骤8-10）。
算法使用同样的过程，递归地形成每个划分上的样本判定树。一旦一个属性出现在一个结点上，就不必该结点的任何后代上考虑它（步骤13）。
递归划分步骤仅当下列条件之一成立停止：
(a) 给定结点的所有样本属于同一类（步骤2 和3）。
(b) 没有剩余属性可以用来进一步划分样本（步骤4）。在此情况下，使用多数表决（步骤5）。
这涉及将给定的结点转换成树叶，并用样本中的多数所在的类标记它。替换地，可以存放结
点样本的类分布。
(c) 分枝
test_attribute = a i 没有样本（步骤11）。在这种情况下，以 samples 中的多数类
创建一个树叶（步骤12）
在决策树ID3基础上，又进行了算法改进，衍生出 其他算法如：C4.5: （Quinlan） 和Classification and Regression Trees (CART): (L. Breiman, J. Friedman, R. Olshen, C. Stone)。这些算法
共同点：都是贪心算法，自上而下(Top-down approach)
区别：属性选择度量方法不同： C4.5 （gain ratio，增益比), CART(gini index，基尼指数), ID3 (Information Gain，信息增益)
2.5 如何处理连续性变量的属性？
有些数据是连续性的，其不像如上实验数据可以离散化表示。诸如根据天气情况预测打球案例中，其湿度是一个连续值，我们的做法是将湿度70作为一个分界点，这里就是连续变量离散化的体现。
2.6 补充知识
树剪枝叶 （避免overfitting)：为了避免拟合问题，我们可以对归于繁琐的树进行剪枝（就是降低树的高度），可以分为先剪枝和后剪枝。
决策树的优点：直观，便于理解，小规模数据集有效
决策树的缺点：处理连续变量不好、类别较多时，错误增加的比较快、可规模性一般
3 基于python代码的决策树算法实现：预测顾客购买商品的能力
3.1 机器学习的库：scikit-learnPython
scikit-learnPython，其特性简单高效的数据挖掘和机器学习分析，简单高效的数据挖掘和机器学习分析，对所有用户开放，根据不同需求高度可重用性，基于Numpy, SciPy和matplotlib，开源，商用级别：获得 BSD许可。scikit-learn覆盖分类（classification), 回归（regression), 聚类（clustering), 降维(dimensionality reduction)，模型选择(model selection), 预处理(preprocessing)等领域。
3.2 scikit-learn的使用：Anaconda集成了如下包，不需要安装即可使用
安装scikit-learn: pip, easy_install, windows installer，安装必要package：numpy， SciPy和matplotlib， 可使用Anaconda (包含numpy, scipy等科学计算常用package）
安装注意问题：Python解释器版本（2.7 or 3.4？）, 32-bit or 64-bit系统
商品购买例子：
转化为csv文件如下：
3.3 运行效果如下：
其中，datafile存放模型训练数据集和测试数据集，TarFile是算法生成文本形式的dot文件和转化后的pdf图像文件，两个py文件，一个是训练算法一个是测试训练结果。右侧预测值【0 1 1】代表三条测试数据，其中后两条具备购买能力。具体算法和细节下节详解。
3.4 具体算法和细节
python中导入决策树相关包文件，然后通过对csv格式转化为sklearn工具包中可以识别的数据格式，再调用决策树算法，最后将模型训练的结果以图形形式展示。
包的导入：
from sklearn.feature_extraction import DictVectorizerimport csvfrom sklearn import treefrom sklearn import preprocessingfrom sklearn.externals.six import StringIO
1
读取csv文件，将其特征值存储在列表featureList中，将预测的目标值存储在labelList中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
'''
Description:python调用机器学习库scikit-learn的决策树算法，实现商品购买力的预测，并转化为pdf图像显示
Author:Bai Ningchao
DateTime:2016年12月24日14:08:11
Blog URL:http://www.cnblogs.com/baiboy/
'''
def trainDicisionTree(csvfileurl):
'读取csv文件，将其特征值存储在列表featureList中，将预测的目标值存储在labelList中'
featureList = []
labelList = []
#读取商品信息
allElectronicsData=open(csvfileurl)
reader = csv.reader(allElectronicsData) #逐行读取信息
headers=str(allElectronicsData.readline()).split(',') #读取信息头文件
print(headers)
运行结果：
存储特征数列和目标数列
1
2
3
4
5
6
7
8
9
10
'存储特征数列和目标数列'
for row in reader:
labelList.append(row[len(row)-1]) #读取最后一列的目标数据
rowDict = {} #存放特征值的字典
for i in range(1, len(row)-1):
rowDict[headers[i]] = row[i]
# print('rowDict:',rowDict)
featureList.append(rowDict)
print(featureList)
print(labelList)
运行结果：
1
将特征值数值化
1
2
3
4
5
6
7
8
9
10
11
12
13
'Vetorize features:将特征值数值化'
vec = DictVectorizer() #整形数字转化
dummyX = vec.fit_transform(featureList) .toarray() #特征值转化是整形数据
print('dummyX: ' + str(dummyX))
print(vec.get_feature_names())
print('labelList: ' + str(labelList))
# vectorize class labels
lb = preprocessing.LabelBinarizer()
dummyY = lb.fit_transform(labelList)
print('dummyY: \n' + str(dummyY))
运行结果：
1
如上算法就是将商品信息转化为机器学习决策树库文件可以识别的形式，即如下形式：
1
使用决策树进行分类预测处理
1
2
3
4
5
6
7
8
9
10
'使用决策树进行分类预测处理'
# clf = tree.DecisionTreeClassifier()
#自定义采用信息熵的方式确定根节点
clf = tree.DecisionTreeClassifier(criterion='entropy')
clf = clf.fit(dummyX, dummyY)
print('clf: ' + str(clf))
# Visualize model
with open('../Tarfile/allElectronicInformationGainOri.dot', 'w') as f:
f = tree.export_graphviz(clf, feature_names=vec.get_feature_names(), out_file=f)
运行结果：
将其转化为图像形式展示，需要下载插件：安装 下载Graphviz：
一路安装下来，然后打开cmd进入dos环境下，并进入../Tarfile/Tname.dot路径下;#2 输入dot -Tname.dot -o name.pdf命令，将dos转化为pdf格式
打开文件可见：
源码和数据：
回复“决策树”获取。
新浪微博名称：大数据_机器学习
数据挖掘入门与实战