1. 机器学习中分类和预测算法的评估
准确性
速度
强壮性：当数据总有噪音或缺失时……
可规模性：数据呈指数增长时，同样的算法是否存在问题。
可解释性
2. 决策数/判定树（decision tree）
决策树算法是机器学习分类算法中一个重要的算法
决策树是一个类似于流程图的树结构，其中每个内部结点标识在一个属性上的测试，每个分支代表一个属性输出，而每个树叶结点代表分类或类分布，树的最顶层是根节点。
决策树是附加概率结果的一个树状的决策图，是直观的运用统计概率分析的图法。机器学习中决策树是一个预测模型，它表示对象属性和对象值之间的一种映射，树中的每一个节点表示对象属性的判断条件，其分支表示符合节点条件的对象。树的叶子节点表示对象所属的预测结果。
这是一颗简单的决策树，用于预测小明是否进行水上运动。主要依赖一些天气条件：
总体天气（晴天、阴天、雨天）
湿度（小于等于70，大于70），连续变量离散化处理
是否刮风（刮风、不刮风）
每一个内部节点都表示一个属性条件判断，叶子节点表示是否进行水上运动
样本数据集有14天的数据，其中9天做了运动，5天没有。
14天中，5天晴天，4天阴天，5天雨天
晴天时有2天进行了运动，3天没有
当天气为晴天时，继续观测湿度情况，有2天湿度小于等于70，进行了水上运动。另外三天湿度大于70，未进行运动。
当天气为阴天时，全部进行了水上运动
当天气为雨天时，观测刮风情况，有2天刮风了，未做水上运动，另外3天未刮风，进行了水上运动
3. 决策树建立
本文上一节已经讨论如何用一棵决策树进行分类。本节将通过特征选择、剪枝，介绍如何根据已有的样本数据建立一棵决策树。
首先介绍下特征选择。选择一个合适的特征作为判断节点，可以快速的分类，减少决策树的深度。决策树的目标就是把数据集按对应的类标签进行分类。最理想的情况是，通过特征的选择能把不同类别的数据集贴上对应类标签。特征选择的目标使得分类后的数据集比较纯。如何衡量一个数据集纯度，这里就需要引入数据纯度函数。下面将介绍两种表示数据纯度的函数。
- 信息增益
信息熵表示的是不确定度。均匀分布时，不确定度最大，此时熵就最大。当选择某个特征对数据集进行分类时，分类后的数据集信息熵会比分类前的小，其差值表示为信息增益。信息增益可以衡量某个特征对分类结果的影响大小。
假设在样本数据集 D 中，混有 c 种类别的数据。构建决策树时，根据给定的样本数据集选择某个特征值作为树的节点。在数据集中，可以计算出该数据中的信息熵：
作用前的信息熵计算公式
其中 D 表示训练数据集，c 表示数据类别数，Pi 表示类别 i 样本数量占所有样本的比例。
对应数据集 D，选择特征 A 作为决策树判断节点时，在特征 A 作用后的信息熵的为 Info(D)，计算如下：
作用后的信息熵计算公式
其中 k 表示样本 D 被分为 k 个部分。
信息增益表示数据集 D 在特征 A 的作用后，其信息熵减少的值。公式如下：
信息熵差值计算公式
对于决策树节点最合适的特征选择，就是 Gain(A) 值最大的特征。
- 基尼指数
基尼指数是另一种数据的不纯度的度量方法，其公式为：
基尼指数计算公式
其中 c 表示数据集中类别的数量，Pi 表示类别 i 样本数量占所有样本的比例。
从该公式可以看出，当数据集中数据混合的程度越高，基尼指数也就越高。当数据集 D 只有一种数据类型，那么基尼指数的值为最低 0。
如果选取的属性为 A，那么分裂后的数据集 D 的基尼指数的计算公式为：
分裂后的基尼指数计算公式
其中 k 表示样本 D 被分为 k 个部分，数据集 D 分裂成为 k 个 Dj 数据集。
对于特征选取，需要选择最小的分裂后的基尼指数。也可以用基尼指数增益值作为决策树选择特征的依据。公式如下：
基尼指数差值计算公式
在决策树选择特征时，应选择基尼指数增益值最大的特征，作为该节点分裂条件。
接下来介绍剪枝。在分类模型建立的过程中，很容易出现过拟合的现象。过拟合是指在模型学习训练中，训练样本达到非常高的逼近精度，但对检验样本的逼近误差随着训练次数而呈现出先下降后上升的现象。过拟合时训练误差很小，但是检验误差很大，不利于实际应用。
决策树的过拟合现象可以通过剪枝进行一定的修复。剪枝分为预先剪枝和后剪枝两种。
预先剪枝指在决策树生长过程中，使用一定条件加以限制，使得产生完全拟合的决策树之前就停止生长。预先剪枝的判断方法也有很多，比如信息增益小于一定阀值的时候通过剪枝使决策树停止生长。但如何确定一个合适的阀值也需要一定的依据，阀值太高导致模型拟合不足，阀值太低又导致模型过拟合。
后剪枝是在决策树生长完成之后，按照自底向上的方式修剪决策树。后剪枝有两种方式，一种用新的叶子节点替换子树，该节点的预测类由子树数据集中的多数类决定。另一种用子树中最常使用的分支代替子树。
预先剪枝可能过早的终止决策树的生长，后剪枝一般能够产生更好的效果。但后剪枝在子树被剪掉后，决策树生长的一部分计算就被浪费了。
4. 决策树模型评估
建立了决策树模型后需要给出该模型的评估值，这样才可以来判断模型的优劣。学习算法模型使用训练集 (training set) 建立模型，使用校验集 (test set) 来评估模型。本文通过评估指标和评估方法来评估决策树模型。
评估指标有分类准确度、召回率、虚警率和精确度等。而这些指标都是基于混淆矩阵 (confusion matrix) 进行计算的。
混淆矩阵是用来评价监督式学习模型的精确性，矩阵的每一列代表一个类的实例预测，而每一行表示一个实际的类的实例。以二类分类问题为例，如下表所示：
混淆矩阵
|
|
预测的类 |
|
|
|
|
实际的类 |
|
类 = 1 |
类 = 0 |
|
|
|
类 = 1 |
TP |
FN |
P |
|
|
类 = 0 |
FP |
TN |
N |
其中
P (Positive Sample)：正例的样本数量。
N(Negative Sample)：负例的样本数量。
TP(True Positive)：正确预测到的正例的数量。
FP(False Positive)：把负例预测成正例的数量。
FN(False Negative)：把正例预测成负例的数量。
TN(True Negative)：正确预测到的负例的数量。
根据混淆矩阵可以得到评价分类模型的指标有以下几种。
分类准确度，就是正负样本分别被正确分类的概率，计算公式为：
分类准确度计算公式
召回率，就是正样本被识别出的概率，计算公式为：
召回率计算公式
虚警率，就是负样本被错误分为正样本的概率，计算公式为：
虚警率计算公式
精确度，就是分类结果为正样本的情况真实性程度，计算公式为：
精确度计算公式
评估方法有保留法、随机二次抽样、交叉验证和自助法等。
保留法 (holdout) 是评估分类模型性能的最基本的一种方法。将被标记的原始数据集分成训练集和检验集两份，训练集用于训练分类模型，检验集用于评估分类模型性能。但此方法不适用样本较小的情况，模型可能高度依赖训练集和检验集的构成。
随机二次抽样 (random subsampling) 是指多次重复使用保留方法来改进分类器评估方法。同样此方法也不适用训练集数量不足的情况，而且也可能造成有些数据未被用于训练集。
交叉验证 (cross-validation) 是指把数据分成数量相同的 k 份，每次使用数据进行分类时，选择其中一份作为检验集，剩下的 k-1 份为训练集，重复 k 次，正好使得每一份数据都被用于一次检验集 k-1 次训练集。该方法的优点是尽可能多的数据作为训练集数据，每一次训练集数据和检验集数据都是相互独立的，并且完全覆盖了整个数据集。也存在一个缺点，就是分类模型运行了 K 次，计算开销较大。
自助法 (bootstrap) 是指在其方法中，训练集数据采用的是有放回的抽样，即已经选取为训练集的数据又被放回原来的数据集中，使得该数据有机会能被再一次抽取。用于样本数不多的情况下，效果很好。
5. 决策树建模
本节通过使用Python的机器学习库scikit-learn对实际案例进行建模
数据集如下图：
#-*- coding: UTF-8 -*-
from sklearn.feature_extraction import DictVectorizer
import csv
from sklearn import preprocessing
from sklearn import tree
from sklearn.externals.six import StringIO
#Read in the csv File and put feature in a list of class label
allElectronicsData = open(r"example.csv","rb")
reader = csv.reader(allElectronicsData)
headers = reader.next()
#print headers
featureList = []
labelList = []
#存放在两个元祖中
for row in reader:
labelList.append(row[len(row)-1])
rowDic = {}
for i in range(1,len(row)-1):
rowDic[headers[i]] = row[i]
featureList.append(rowDic)
# print featureList
# print labelList
# Vector Feature
vec = DictVectorizer()
dummyX = vec.fit_transform(featureList) .toarray()
# print "dummyX:",dummyX
# print vec.get_feature_names()
# print "labelList:"+str(labelList)
lb = preprocessing.LabelBinarizer()
dummyY = lb.fit_transform(labelList)
#print "dummyY:" + str(dummyY)
#using desicionTree for classfication
clf = tree.DecisionTreeClassifier(criterion="entropy") #创建一个分类器，entropy决定了用ID3算法
clf = clf.fit(dummyX, dummyY)
print "clf:"+str(clf)
#Visulize model
with open("allEallElectronicInfomationGainori.txt","w") as f:
f = tree.export_graphviz(clf, feature_names=vec.get_feature_names(), out_file = f)
#预测
oneRowX = dummyX[0,:]
#print "oneRowX:" +str(oneRowX)
newRowX = oneRowX
newRowX[0] = 1
newRowX[2] = 0
print "newRowX:" +str(newRowX)
predictedY = clf.predict(newRowX)
print "predictedY:" + str(predictedY)
使用命令导出图形为pdf：dot -T pdf ex.txt -o output.pdf.txt
6. 决策树算法的优缺点：
优点
1：理解和解释起来简单，且决策树模型可以想象
2：需要准备的数据量不大，而其他的技术往往需要很大的数据集，需要创建虚拟变量，去除不完整的数据，但是该算法对于丢失的数据不能进行准确的预测
3：决策树算法的时间复杂度(即预测数据)是用于训练决策树的数据点的对数
4：能够处理数字和数据的类别（需要做相应的转变），而其他算法分析的数据集往往是只有一种类型的变量
5：能够处理多输出的问题
6：使用白盒模型，如果给定的情况是在一个模型中观察到的，该条件的解释很容易解释的布尔逻辑，相比之下，在一个黑盒子模型（例如人工神经网络），结果可能更难以解释
7：可能使用统计检验来验证模型，这是为了验证模型的可靠性
8：从数据结果来看，它执行的效果很好，虽然它的假设有点违反真实模型
缺点
1：决策树算法学习者可以创建复杂的树，但是没有推广依据，这就是所谓的过拟合，为了避免这种问题，出现了剪枝的概念，即设置一个叶子结点所需要的最小数目或者设置树的最大深度
2：决策树的结果可能是不稳定的，因为在数据中一个很小的变化可能导致生成一个完全不同的树，这个问题可以通过使用集成决策树来解决
3：众所周知，学习一恶搞最优决策树的问题是NP——得到几方面完全的优越性，甚至是一些简单的概念。因此，实际决策树学习算法是基于启发式算法，如贪婪算法，寻求在每个节点上的局部最优决策。这样的算法不能保证返回全局最优决策树。这可以减轻训练多棵树的合奏学习者，在那里的功能和样本随机抽样更换。
4：这里有一些概念是很难的理解的，因为决策树本身并不难很轻易的表达它们，比如说异或校验或复用的问题。
5：决策树学习者很可能在某些类占主导地位时创建有有偏异的树，因此建议用平衡的数据训练决策树
参考资源