机器学习开放课程（三）：分类、决策树和K近邻
编者按：机器学习开放课程第三课，Mail.Ru数据科学家Yury Kashnitsky深入浅出地介绍了决策树、K近邻、交叉验证。
嘿！这是我们的系列文章的第三篇。我们今天终于要开始聊机器学习了。真激动！
相关阅读：机器学习开放课程（一）：使用Pandas探索数据分析
概览
导言
决策树
如何构建决策树
树构建算法
分类问题中的分割的其他质量标准
决策树如何应用于数值特征
决定性的树参数
scikit-learn的
DecisionTreeClassifier回归问题中的决策树
最近邻方法
实际应用中的最近邻方法
scikit-learn的
KNeighborsClassifier类选择模型参数和交叉验证
应用样例和复杂情形
客户离网率预测任务中的决策树和最近邻方法
决策树的复杂情形
MNIST手写数字识别任务中的决策树和k-NN
最近邻方法的复杂情形
决策树和最近邻方法的优势和劣势
作业三
相关资源
下面的材料以Jupyter notebook的形式查看效果最佳。如果你克隆了本教程的代码仓库，你也可以在本地运行。
1. 导言
在我们深入本文之前，让我们来谈谈我们即将解决的问题的类型和它在机器学习这一激动人心的领域中的位置。T. Mitchell的书Machine Learning（机器学习，1997年出版）给出了机器学习经典、通用的定义：
给定某类任务T和其相应的表现测度P与经验E，如果一个程序在T中的任务上的表现，根据P测度，基于经验E提升了，那么我们称该程序基于经验E学习。
在不同的问题设定下，T、P、E可能指完全不同的东西。机器学习中一些最流行的任务T包括：
基于特征分类实例为某类；
回归——预测实例的一个数值目标特征（基于实例的其他特征）；
聚类——基于实例的特征识别实例的分区，从而让组内成员更为相似（相比其他组的成员而言）；
异常侦测——寻找与其他样本或组内实例“很不一样”的实例；
其他更多。
Deep Learning（《深度学习》，Ian Goodfellow、Yoshua Bengio、Aaron Courville著，2016年出版）的“Machine Learning basics”（机器学习基础）一章提供了一份很好的综述。
经验E指数据（没有数据我们什么也干不了）。根据训练方式，机器学习算法可以分为监督（supervised）和无监督（unsupervised）两类。在无监督学习任务中，我们有一个包含由特征（feature）集合描述的实例（instance）的集合。而监督学习问题还有一个目标变量（target variable），这是我们想要能够预测的变量，在训练集（training set）中，目标变量是已知的。
例子
分类和回归属于监督学习问题。例如，信用机构可能想要基于积累的客户数据预测贷款违约。这里，经验E是已有的训练数据：实例（客户）的集合，一组特征（例如年龄、薪水、贷款类型、以往违约记录，等等），一个目标变量（他们是否会违约）。目标变量是关于贷款违约的事实（1或0），因此预测该变量是一个（二元）分类问题。如果你转而预测贷款会超期多久，那这就是一个回归问题了。
最后，机器学习定义的第三个术语是算法表现的评估度量P。不同问题和算法的度量不同，当我们学习新算法时，我们将讨论这一点。就目前而言，我们将使用分类算法的一个简单度量，测试集上预测出的正确答案的比例——精确度。
让我们来讨论两种监督学习问题：分类和回归。
2. 决策树
我们对分类与回归方法的概览从其中最流行的方法之一——决策树开始。不仅仅在机器学习中，在每天的日常决策中，我们都在使用决策树。流程图实际上是决策树的可视化表示。例如，下面是俄罗斯国立高等经济研究大学（Higher School of Economics）提供给雇员的在学院网站上发表论文的流程图：
用机器学习的术语来说，我们可以把它看成一个简单的分类器，判定合适的发表类型（书、文章、书的章节、预印本、Higher School of Economics and the Media稿件），分类的依据是内容（书、小册子、论文）、新闻类型、原发表物类型（科学期刊、通讯）等等。
决策树常常是专家经验的概括，一种分享特定过程的方式。例如，在引入可伸缩的机器学习算法之前，银行部门的信用评分任务是由专家解决的。放贷的决策是基于一些源自直觉（或经验）的演绎规则，这样的规则可以表示为决策树的形式。
我们的下一个例子将解决一个二元分类问题（许可/拒绝贷款），基于“年龄”、“房产”、“收入”、“教育”。
作为机器学习算法的决策树基本上和上面的示意图差不多；我们合并一连串逻辑规则为一个树形的数据结构，这些规则的形式为“特征a的值小于x，特征b的值小于y ... => 类别1”。这一算法的优势是它们很容易解释。例如，银行可以向客户解释拒绝发放贷款的原因：客户不拥有房产，收入低于五千。
我们之后会看到，很多其他模型，尽管更为精确，并不具备这一属性，而更像“黑盒”，难以解释输入数据是如何转换为输出的。由于这一“可理解性”和与人类决策过程的相似性（向你的老板解释这一模型很容易），决策树极为流行。C4.5，这一分类方法的代表，在十大最佳数据挖掘算法的榜单上名列第一（Top 10 Algorithms in Data Mining）。
如何构建决策树
之前我们见到了基于年龄、资产、收入和其他变量做出的放贷决策。但是我们首先应该关注哪些变量呢？让我们讨论一个简单的例子，其中所有变量是二元的。
回忆一下游戏“20个问题”，介绍决策树时常常提到这个游戏。你大概玩过这个游戏吧——一个人心里想着一个名人，另一个人仅仅通过询问答案为“是”或“否”的问题猜测这个名人是谁。猜的人首先会问什么？当然，他会问一个可以最大限度上压缩剩余选项数目的问题。询问“是不是安吉丽娜·朱莉？”，如果得到的是否定的回答，仅仅剔除了一个可能选项。相反，询问“这个名人是女人吗？”将消除大约一半的可能选项。这就是说，“性别”特征相比“安吉丽娜·朱莉”、“西班牙人”、“喜欢足球”等其他特征更能区分名人数据集。这背后的道理和衡量获得的信息量的概念——香农熵有关。
熵
对于具有N种可能状态的系统而言，香农熵的定义如下：
其中，Pi是发现系统位于第i个状态的概率。这是一个在物理、信息论和其他领域中广泛应用的重要概念。熵可以描述为系统的混沌程度。熵越高，系统的有序性越差，反之亦然。这将帮助我们形式化“高效数据分割”，我们在上面谈论“20个问题”时顺便提到的概念。
玩具示例
为了演示熵如何帮助我们识别构建决策树的良好特征，让我们来看一个玩具示例。我们将基于球的位置预测它的颜色。
这里有9个蓝球和11个黄球。如果我们随机选择一个球，这个球是蓝球的概率p1 = 9/20，是黄球的概率p2 = 11/20，这意味着熵S0 = -9/20 log2(9/20) - 11/20 log2(11/20) ≈ 1. 这个值本身可能无法告诉我们很多信息，但让我们看看如果我们将球分为两组，值会如何改变：位置小于等于12、位置大于12.
左边一组有13个球，8蓝5黄。这一组的熵S1 = -5/13 log2(5/13) - 8/13 log2(8/13) ≈ 0.96. 右边一组有7个球，1蓝6黄。右边这组的熵S2 = -1/7 log2(1/7) - 6/7 log2(6/7) ≈ 0.6. 如你所见，两组的熵都下降了，右边这组降得更多。由于熵实际上是系统混沌（或不确定）的程度，熵的下降称为信息增益。形式化地说，基于变量Q（在这个例子中是变量“x ≤ 12”）所作的分割，得到的信息增益（IG）定义为：
其中，q是分割的组数，Ni是变量Q等于第i项值时的样本数目。在我们的例子中，分割带来了两组（q = 2），一组有13个元素（N1 = 13），另一组有7个（N2 = 7）。因此，信息增益为：
结果表明，根据“坐标小于或等于12”将球分为两组带来了一个更有序的系统。让我们继续分组，直到每组中的球颜色都一样。
我们很容易看到，右边那组只需根据“坐标小于或等于18”再分割一次。而左边那组还需要三次分割。注意，组内所有球的颜色都一样，意味着熵为0（log2(1) = 0）。
我们成功构建了一个基于球的位置预测球的颜色的决策树。如果我们增加任意一个球，这个决策树可能无法很好地工作，因为它完全拟合了训练集（初始的20球）。如果我们希望在这个例子中做得更好，那么一棵“问题”或分割更少的树将会更精确，尽管它没有完全拟合训练集。我们以后将讨论过拟合这个问题。
树构建算法
我们可以确定，在之前的例子中构建的决策树是最优的：它仅仅提了5个“问题”（基于变量x），完全拟合了训练集。其他分割条件得到的树会更深，即，需要更多“问题”获得答案。
诸如ID3和C4.5之类的构建决策树的流行算法的核心，是贪婪最大化信息增益：在每一步，算法选择能在分割后给出最大信息增益的变量。接着递归重复这一流程，直到熵为零（或者，为了避免过拟合，直到熵为某个较小的值）。不同的算法使用不同的推断，通过“及早停止”或“截断”以避免构建过拟合的树。
分类问题中的分割的其他质量标准
我们讨论了熵是如何让我们形式化树的分区的。但这只是一种推断；还有其他指标。
最大化这一标准可以被解释为最大化在同一子树下同一类别的成对对象的数目（不要和基尼指数混淆了）。
实践中几乎从不使用错分率，而基尼不确定性和信息增益的效果差不多。
二元分类问题的熵和基尼不确定性为：
其中p+是对象具有标签+的概率。
如果我们以p+为坐标，绘制这两个函数的图像，我们将看到熵的图像和基尼不确定性的两倍的图像非常接近。因此，在实践中，这两个标注基本上是一样的。
例子
让我们考虑用一棵决策树拟合一些合成数据。我们将生成两个分类的样本，两者均为正态分布，但均值不同。
# 第一类
np.random.seed(17)
train_data = np.random.normal(size=(100, 2))
train_labels = np.zeros(100)
# 加入第二类
train_data = np.r_[train_data, np.random.normal(size=(100, 2), loc=2)]
train_labels = np.r_[train_labels, np.ones(100)]
让我们绘制数据。用非形式化的方式来说，这一例子中的分类问题是构造分开两类（红点和黄点）的某种“良好的”边界。在这个例子中，机器学习归结为选择一个良好的分界。一条直线可能太过简单，而沿着每个红点画出的蛇形曲线可能太过复杂，导致我们在新样本上犯错。从直觉上说，某种平滑的边界，或者，一条直线、一个超平面，在新数据上的效果会比较好。
plt.rcParams['figure.figsize'] = (10,8)
plt.scatter(train_data[:, 0], train_data[:, 1], c=train_labels, s=100,
cmap='autumn', edgecolors='black', linewidth=1.5);
plt.plot(range(-2,5), range(4,-3,-1));
让我们尝试训练一棵Sklearn决策树，区分这两类数据点。最后我们可视化所得的边界。
from sklearn.tree import DecisionTreeClassifier
# 让我们编写一个辅助函数，返回之后的可视化网格
def get_grid(data):
x_min, x_max = data[:, 0].min() - 1, data[:, 0].max() + 1
y_min, y_max = data[:, 1].min() - 1, data[:, 1].max() + 1
return np.meshgrid(np.arange(x_min, x_max, 0.01),
np.arange(y_min, y_max, 0.01))
# max_depth参数限制树的深度。
clf_tree = DecisionTreeClassifier(criterion='entropy', max_depth=3,
random_state=17)
# 训练树
clf_tree.fit(train_data, train_labels)
# 可视化
xx, yy = get_grid(train_data)
predicted = clf_tree.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)
plt.pcolormesh(xx, yy, predicted, cmap='autumn')
plt.scatter(train_data[:, 0], train_data[:, 1], c=train_labels, s=100,
cmap='autumn', edgecolors='black', linewidth=1.5);
树本身是什么样的呢？我们看到树将空间“切割”为8个矩形，也就是说，树有8个叶节点。在每个矩形之中，树将根据其中大多数对象的标签做出预测。
# 使用.dot格式可视化树
from ipywidgets import Image
from io import StringIO
import pydotplus #pip install pydotplus
from sklearn.tree import export_graphviz
dot_data = StringIO()
export_graphviz(clf_tree, feature_names=['x1', 'x2'],
out_file=dot_data, filled=True)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
Image(value=graph.create_png())
我们如何“阅读”这棵树？
最初，我们有200个样本（实例），每个分类各有100个样本。初始状态的熵是最大的，S = 1. 接着，第一次分区，将样本分成两组，是通过比较x2的值与1.211达成的（你可以在上面可视化边界的图中找到这一部分边界）。基于这一分割，左右两组的熵都下降了。这一过程持续进行，直到深度3. 在上图的可视化中，属于第一类的样本数量越多，节点的橙色就越深，属于第二类的样本越多，节点的蓝色就越深。在一开始，两类样本的数量相等，因此树的根节点是白色。
决策树如何应用于数值特征
假设我们有一个数值特征“年龄”，该特征有大量的唯一值。决策树将通过查看“年龄 < 17”、“年龄 < 22.87”这样的二元属性寻找最好的（根据某种信息增益标准）分割。不过，如果年龄范围很大怎么办？或者，另一个定量变量，“薪水”，同样能以许多方式“切割”呢？在构建树的每一步中，会有过多的二元属性可供选择。为了解决这一问题，我们经常使用推断来限制和定量变量比较的阈值的数量。
让我们考虑一个例子。假设我们有如下数据集：
data = pd.DataFrame({'Age': [17,64,18,20,38,49,55,25,29,31,33],
'Loan Default': [1,0,1,0,1,0,0,1,1,0,1]})
# 让我们根据年龄进行升序排列
data.sort_values('Age')
age_tree = DecisionTreeClassifier(random_state=17)
age_tree.fit(data['Age'].values.reshape(-1, 1), data['Loan Default'].values)
dot_data = StringIO()
export_graphviz(age_tree, feature_names=['Age'],
out_file=dot_data, filled=True)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
Image(value=graph.create_png())
我们看到，树使用以下5个值来评估年龄：43.5、19、22.5、30、32. 如果你仔细查看，你会发现它们就是目标分类从1“切换”到0或从0“切换”到1的那两个年龄的均值。比如，43.5是38和49的均值，一个39岁的客户没能偿还贷款，而一个49岁的客户还贷了。树寻找目标变量切换它的值的那些变量的值，以此作为“切割”定量变量的阈值。
看到这里，我想你应该明白为什么像“年龄 < 17.5”这样的特征是不用考虑的。
让我们考虑一个更复杂的例子，加入“薪水”变量（以千美元每年为单位）。
data2 = pd.DataFrame({'Age': [17,64,18,20,38,49,55,25,29,31,33],
'Salary': [25,80,22,36,37,59,74,70,33,102,88],
'Loan Default': [1,0,1,0,1,0,0,1,1,0,1]})
data2.sort_values('Age')
如果我们据年龄排序，目标分类（“loan default”）将切换（从1到0或从0到1）5次。如果我们根据薪水排序，它将切换7次。现在树将如何选择特征？让我们看看。
age_sal_tree = DecisionTreeClassifier(random_state=17)
age_sal_tree.fit(data2[['Age', 'Salary']].values, data2['Loan Default'].values)
dot_data = StringIO()
export_graphviz(age_sal_tree, feature_names=['Age', 'Salary'],
out_file=dot_data, filled=True)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
Image(value=graph.create_png())
我们看到，树同时根据薪水和年龄进行分区。另外，特征比较的阈值为43.5岁、22.5岁和95k、30.5k每年。同样，我们看到95是88和102的均值；年薪88k的个体被证明“不好”，而年薪102k的个体是“好的”。30.5k同理。也就是说，只搜寻了一些年龄和薪水的值用于比较。树为何选择这些特征？因为它们提供了更好的分区（根据基尼不确定性）。
结论 最简单的推断决策树处理数值特征的方法是升序排列它的值，然后只关注目标变量的值改变的那些阈值。
此外，当数据集具有大量数值特征，每个特征具有大量唯一值时，只选择最高的N个阈值，即，仅仅使用最高的N个提供最大增益的值。这一过程可以看成是构造了一棵深度为1的树，计算熵（或基尼不确定性），然后选择最佳阈值用于比较。
比方说，如果我们根据“薪水 ≤ 34.5”分割，左子组的熵为0（所有客户都是“不好的”），而右边的熵为0.954（3个“不好的”，5个“好的”，你可以自行确认这一点，这将作为作业的一部分）。信息增益大概是0.3. 如果我们根据“薪水 ≤ 95”分割，左边的子组的熵会是0.97（6个“不好的”，4个“好的”），而右边的熵会是0（该组只包含一个对象）。信息增益大约是0.11. 如果我们以这样的方式计算每种分区的信息增益，我们可以在（使用所有特征）构造一棵大决策树之前，选择比较每个数值特征的阈值。
更多数值特征离散化的例子可以参考网上的其他文章。关于这一主题最知名的论文之一是“On the handling of continuous-valued attributes in decision tree generation”（UM Fayyad. KB Irani, “Machine Learning”, 1992）。
决定性的树参数
技术上说，我们可以构建每个叶节点只有一个实例的决策树，但在实践中构建单棵决策树时，这一做法并不常见，因为它会导致过拟合。在树的底部很深的地方，会有基于不怎么重要的特征进行的分区（例如，客户来自利兹还是纽约）。我们甚至可以进一步夸大这个故事，发现所有穿着绿裤子进银行申请贷款的四个客户都没能还上贷款。即使在训练中这是真的，我们也不想让分类模型生成这样的规则。
在两个例外情形中，树构建到最大深度：
随机森林（一组树）将平均化构建到最大深度的单棵树的回应（我们以后会讨论为何要这么做）。
剪枝树。在这一方法中，树首先构建到最大深度。接着，从底部开始，通过比较有分区/无分区情形下树的质量，移除树的一些节点（比较基于交叉验证，下文会具体讨论）。
下面是过拟合树给出的分界。
最常见的应对过拟合决策树的方式为：
人工限制深度或叶节点的最少样本数：达到限制时停止树的构造。
对树进行剪枝。
scikit-learn的DecisionTreeClassifier
sklearn.tree.DecisionTreeClassifier类的主要参数为：
max_depth树的最大深度；max_features搜索最佳分区时的最大特征数（特征很多时，设置这个参数很有必要，因为基于所有特征搜索分区会很“昂贵”）；min_samples_leaf叶节点的最少样本数。该参数防止创建任何叶节点只有很少成员的树。
树的参数需要根据输入数据设定，通常通过交叉验证确定，下文会具体讨论交叉验证。
回归问题中的决策树
预测数值变量时，构造决策树的思路是一样的，但质量标准改变了。
其中，n是叶节点中的样本数，yi是目标变量的值。简单来说，通过最小化方差，我们寻找以如下方式切分训练集的特征，每个叶节点中的目标特征的值大致相等。
例子
让我们基于以下函数生成某个数据分布（添加了一些噪声）：
接着我们将在生成的数据分布上训练一颗决策树，显示它做出的预测。
n_train = 150
n_test = 1000
noise = 0.1
def f(x):
x = x.ravel()
return np.exp(-x ** 2) + 1.5 * np.exp(-(x - 2) ** 2)
def generate(n_samples, noise):
X = np.random.rand(n_samples) * 10 - 5
X = np.sort(X).ravel()
y = np.exp(-X ** 2) + 1.5 * np.exp(-(X - 2) ** 2) + \
np.random.normal(0.0, noise, n_samples)
X = X.reshape((n_samples, 1))
return X, y
X_train, y_train = generate(n_samples=n_train, noise=noise)
X_test, y_test = generate(n_samples=n_test, noise=noise)
from sklearn.tree import DecisionTreeRegressor
reg_tree = DecisionTreeRegressor(max_depth=5, random_state=17)
reg_tree.fit(X_train, y_train)
reg_tree_pred = reg_tree.predict(X_test)
plt.figure(figsize=(10, 6))
plt.plot(X_test, f(X_test), "b")
plt.scatter(X_train, y_train, c="b", s=20)
plt.plot(X_test, reg_tree_pred, "g", lw=2)
plt.xlim([-5, 5])
plt.title("Decision tree regressor, MSE = %.2f" % np.sum((y_test - reg_tree_pred) ** 2))
plt.show()
我们看到，决策树使用分段常数函数逼近数据。
3. 最近邻方法
最近邻方法（K近邻或k-NN）是另一个非常流行的分类方法。同样，k-NN有时也用于回归问题。和决策树类似，这是最容易理解的分类方法之一。背后的直觉是你和你的邻居相似。更形式化地说，这一方法遵循紧密性假说：如果样本间的距离以足够好的方法衡量，那么相似的样本更可能属于同一分类。
根据最近邻方法，下图中的绿球将被分类为“蓝色”而不是“红色”。
再举一个例子，如果你不知道在网站的列表中如何标记蓝牙耳机，你可以查找5个相似的耳机，如果其中4个标记为“配件”，只有1个标记为“科技”，那么你可以同样将它标记为“配件”。
为了分类测试集中的每个样本，需要依次进行以下操作：
计算和训练集中每个样本的距离。
从训练集中选取k个距离最近的样本。
测试样本的分类将是它的k个最近邻中最常见的分类。
在回归问题中应用这一方法很容易，只需做一个小小的改动：第3步不返回分类，而是返回一个数字——目标变量在邻居中的均值（或中位数）。
这一方式的一个引人注意的特征是惰性——仅在需要分类测试样本的预测阶段做出计算。事先并不基于训练样本创建模型。相反，回想一下本文前半部分的决策树，决策树是基于训练集构建的，而在测试情形下，通过遍历决策树可以快速地分类。
最近邻是一个经过充分研究的方法。存在很多重要的理论声称，在“无尽的”数据集上，它是最佳的分类方法。经典著作“The Elements of Statistical Learning”的作者认为k-NN是理论上的理想算法，其使用仅受算力和维度诅咒的限制。
实际应用中的最近邻方法
在某些案例中，k-NN可以作为一个开始（基线）；
在Kaggle竞赛中，k-NN常常用于构建元特征（即k-NN预测作为其他模型的输入），或用于堆叠/混合；
最近邻方法还可以用于其他任务，比如推荐系统。比如，推荐一项在接受推荐者的最近邻中很受欢迎的产品（或服务）；
实践中，在大型数据集上，常常使用逼近方法搜索最近邻。有不少实现这一算法的开源库；Spotify的Annoy了解下。
k-NN分类/回归的质量取决于一些参数：
邻居数k.
样本间距离的测量（常用的有Hamming、欧几里得、余弦、Minkowski距离）。注意大部分距离要求数据在同一尺度下。简单来说，我们不想让数量级以千计的“薪水”特征，影响通常小于100的“年龄”特征的距离。
邻居的权重（每个邻居可能贡献不同的权重；例如，样本越远，权重越低）。
scikit-learn的KNeighborsClassifier类
sklearn.neighbors.KNeighborsClassifier类的主要参数为：
weights：uniform（所有权重相等），distance（权重和到测试样本的距离成反比），或任何其他用户定义的函数；algorithm（可选）：brute、ball_tree、KD_tree、auto。brute，最近邻基于在训练集上的网格搜索得出。ball_tree和KD_tree，样本间的距离储存在树中，以加速寻找最近邻的过程。如果你设置该参数为auto，将基于训练集自动选择合适的寻找最近邻的方法。leaf_size（可选）：若寻找最近邻的算法是BallTree或KDTree，切换为网格搜索的阈值。metric：minkowski、manhattan、euclidean、chebyshev或其他。
4. 选择模型参数和交叉验证
机器学习算法的主要任务是能够概括未见数据。由于我们无法立刻查看模型在新到数据上的表现（因为我们还不知道目标变量的真值），有必要牺牲一小部分数据，来看看模型的质量。
将数据集的一部分留置到一边（留置数据集）。我们保留一小部分训练集（一般是20%到40%），在剩余数据上训练模型（原数据集的60%-80%），然后在留置集上计算模型的表现度量（例如，精确度）。
交叉验证。最常见的情形是k折交叉验证。
在k折交叉验证中，模型在原数据集的不同（K-1）子集上进行训练（上图白色部分），然后在剩余子集上验证表现（每次使用不同的子集，上图橙色部分）。我们得到了K个模型质量评估，这些评估通常加以平均，以得到分类/回归的总体平均质量。
相比留置法，交叉验证能更好地评估模型在新数据上的表现。然而，当你有大量数据时，交叉验证在算力上比较昂贵。
交叉验证是机器学习中非常重要的技术，同时也应用于统计学和经济学。它有助于超参数调优、模型比较、特征评估，等等。更多细节可以参考Sebastian Raschka的博客，或者任何机器（统计）学习的经典教材。
5. 应用样例和复杂情形
客户离网率预测任务中的决策树和最近邻方法
让我们读取数据至DataFrame并进行预处理。将State从dateframe转移到单独的Series对象。我们训练的第一个模型将不包括State特征，以后我们将考察State特征是否有用。
df = pd.read_csv('../../data/telecom_churn.csv')
df['International plan'] = pd.factorize(df['International plan'])[0]
df['Voice mail plan'] = pd.factorize(df['Voice mail plan'])[0]
df['Churn'] = df['Churn'].astype('int')
states = df['State']
y = df['Churn']
df.drop(['State', 'Churn'], axis=1, inplace=True)
我们将数据集的70%划分为训练集（X_train、y_train），30%划分为留置集（X_holdout、y_holdout）。调优模型参数时不涉及留置集。我们将在最后使用它，在调优之后，用留置集评定所得模型的质量。我们将训练2个模型：决策树和k-NN。我们并不知道哪些参数是好的，所以我们将假定一些随机值：树深为5，近邻数量为10.
from sklearn.model_selection import train_test_split, StratifiedKFold
from sklearn.neighbors import KNeighborsClassifier
X_train, X_holdout, y_train, y_holdout = train_test_split(df.values, y,
test_size=0.3, random_state=17)
tree = DecisionTreeClassifier(max_depth=5, random_state=17)
knn = KNeighborsClassifier(n_neighbors=10)
tree.fit(X_train, y_train)
knn.fit(X_train, y_train)
让我们用一个简单的度量在留置集上评定预测的质量——正确回答的比例（精确度）。决策树做得更好——正确回答的百分比大约是94%（决策树）和88%（k-NN）。注意，这一表现是通过使用随机参数达到的。
from sklearn.metrics import accuracy_score
tree_pred = tree.predict(X_holdout)
print(accuracy_score(y_holdout, tree_pred)) # 0.94
knn_pred = knn.predict(X_holdout)
print(accuracy_score(y_holdout, knn_pred)) # 0.88
现在，让我们使用交叉验证确定树的参数。我们将调优每次分割的最大深度和最大特征数。大体上，GridSearchCV做了这些：为每对唯一的max_depth和max_features的值，使用5折验证计算模型的表现，接着选择参数的最佳组合。
from sklearn.model_selection import GridSearchCV, cross_val_score
tree_params = {'max_depth': range(1, 11),
'max_features': range(4, 19)}
tree_grid = GridSearchCV(tree, tree_params,
cv=5, n_jobs=-1,
verbose=True)
tree_grid.fit(X_train, y_train)
让我们列出交叉验证得出的最佳参数和相应的精确度均值。
print(tree_grid.best_params_) # {'max_depth': 6, 'max_features': 17}
print(tree_grid.best_score_) # 0.942
print(accuracy_score(y_holdout, tree_grid.predict(X_holdout))) # 0.946
让我们绘制所得决策树。
dot_data = StringIO()
export_graphviz(tree_grid.best_estimator_, feature_names=df.columns,
out_file=dot_data, filled=True)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
Image(value=graph.create_png())
现在，让我们调优k-NN的k值（邻居数）：
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
knn_pipe = Pipeline([('scaler', StandardScaler()),
('knn', KNeighborsClassifier(n_jobs=-1))])
knn_params = {'knn__n_neighbors': range(1, 10)}
knn_grid = GridSearchCV(knn_pipe, knn_params,
cv=5, n_jobs=-1, verbose=True)
knn_grid.fit(X_train, y_train)
print(knn_grid.best_params_, knn_grid.best_score_)
# ({'knn__n_neighbors': 7}, 0.886)
这证明了决策树比最近邻算法表现更好：94.2%/96.6%的精确度（交叉验证/留置）。决策树的表现非常好，即使是训练时间长得多的随机森林（让我们把它想象成一群互相协作的决策树）在这个例子上也无法取得更好的表现（95.1%/95.3%）。
from sklearn.ensemble import RandomForestClassifier
forest = RandomForestClassifier(n_estimators=100, n_jobs=-1,
random_state=17)
print(np.mean(cross_val_score(forest, X_train, y_train, cv=5))) # 0.949
forest_params = {'max_depth': range(1, 11), 'max_features': range(4, 19)}
forest_grid = GridSearchCV(forest, forest_params,
cv=5, n_jobs=-1, verbose=True)
forest_grid.fit(X_train, y_train)
print(forest_grid.best_params_, forest_grid.best_score_)
# ({'max_depth': 9, 'max_features': 6}, 0.951)
决策树的复杂情形
为了讨论决策树和k-NN的优劣，让我们考虑一个简单的分类任务，其中决策树表现良好但得到的结果过于复杂。让我们在一个平面上创建一个数据点的集合（2个特征），每个数据点是两个分类中的一个（+1表示红色，-1表示黄色）。如果你把它看成分类问题，那么它看起来非常简单：分类由直线分割。
def form_linearly_separable_data(n=500, x1_min=0, x1_max=30, x2_min=0, x2_max=30):
data, target = [], []
for i in range(n):
x1, x2 = np.random.randint(x1_min, x1_max), np.random.randint(x2_min, x2_max)
if np.abs(x1 - x2) > 0.5:
data.append([x1, x2])
target.append(np.sign(x1 - x2))
return np.array(data), np.array(target)
X, y = form_linearly_separable_data()
plt.scatter(X[:, 0], X[:, 1], c=y, cmap='autumn', edgecolors='black');
然而，决策树构建的边界过于复杂；而且树本身也非常深。另外，想想决策树对30x30方块之外的空间的概括性会有多差。
tree = DecisionTreeClassifier(random_state=17).fit(X, y)
xx, yy = get_grid(X)
predicted = tree.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)
plt.pcolormesh(xx, yy, predicted, cmap='autumn')
plt.scatter(X[:, 0], X[:, 1], c=y, s=100,
cmap='autumn', edgecolors='black', linewidth=1.5)
plt.title('Easy task. Decision tree complexifies everything');
我们得到这一过度复杂的构造，尽管正解不过是一条直线x1 = x2.
dot_data = StringIO()
export_graphviz(tree, feature_names=['x1', 'x2'],
out_file=dot_data, filled=True)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
Image(value=graph.create_png())
最近邻方法的表现比决策树好一点，但仍然比不上线性分类器（这将是下一课的内容）。
knn = KNeighborsClassifier(n_neighbors=1).fit(X, y)
xx, yy = get_grid(X)
predicted = knn.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)
plt.pcolormesh(xx, yy, predicted, cmap='autumn')
plt.scatter(X[:, 0], X[:, 1], c=y, s=100,
cmap='autumn', edgecolors='black', linewidth=1.5);
plt.title('Easy task, kNN. Not bad');
MNIST手写数字识别任务中的决策树和k-NN
现在让我们看看这两个算法在实际任务上的表现。我们将使用sklearn内置的手写数字数据集。这一任务是一个k-NN效果惊人的例子。
图片为8x8矩阵（每个像素的白色亮度）。接着每个这样的矩阵“展开”为长度为64的向量，同时我们取得对象的特征描述。
让我们绘制一些手写数字。我们看到它们可以辨认。
from sklearn.datasets import load_digits
data = load_digits()
X, y = data.data, data.target
f, axes = plt.subplots(1, 4, sharey=True, figsize=(16, 6))
for i in range(4):
axes[i].imshow(X[i,:].reshape([8,8]), cmap='Greys');
现在让我们进行和之前的任务类似的试验，不过这次我们将改变可调参数的范围。
数据集的70%用于训练（X_train、y_train），30%用作留置（X_holdout、y_holdout）。
X_train, X_holdout, y_train, y_holdout = train_test_split(X, y, test_size=0.3,
random_state=17)
让我们训练使用随机参数的决策树和k-NN，然后在留置集上进行预测。
tree = DecisionTreeClassifier(max_depth=5, random_state=17)
knn = KNeighborsClassifier(n_neighbors=10)
tree.fit(X_train, y_train)
knn.fit(X_train, y_train)
现在，让我们在留置集上做出预测。我们看到，k-NN做得更好，不过别忘了我们用的是随机参数。
tree_pred = tree.predict(X_holdout)
knn_pred = knn.predict(X_holdout)
print(accuracy_score(y_holdout, knn_pred),
accuracy_score(y_holdout, tree_pred))
# (0.97, 0.666)
现在，让我们像之前一样使用交叉验证调优我们的模型，不过这次我们需要考虑到我们的特征比之前任务中的更多：64.
tree_params = {'max_depth': [1, 2, 3, 5, 10, 20, 25, 30, 40, 50, 64],
'max_features': [1, 2, 3, 5, 10, 20 ,30, 50, 64]}
tree_grid = GridSearchCV(tree, tree_params, cv=5, n_jobs=-1,
verbose=True)
tree_grid.fit(X_train, y_train)
让我们看下交叉验证得到的最佳参数组合和相应的精确度：
print(tree_grid.best_params_, tree_grid.best_score_)
# ({'max_depth': 20, 'max_features': 64}, 0.844)
调优后的表现已经超过了66%（使用随机参数的决策树），但还不到97%（使用随机参数的k-NN）。k-NN在这一数据集上表现更好。基于交叉验证，我们能达到99%的精确度。
print(np.mean(cross_val_score(KNeighborsClassifier(n_neighbors=1),
X_train, y_train, cv=5))) # 0.987
让我们在这一数据集上训练随机森林模型，在大多数数据集上，它的效果比k-NN要好。但这个数据集是个例外。
print(np.mean(cross_val_score(RandomForestClassifier(random_state=17),
X_train, y_train, cv=5))) # 0.935
你可能会说，我们没有对RandomForestClassifier的参数进行任何调优，你说得没错。不过，即使经过调优，训练精确度也无法达到k-NN的98%。
这一试验得到的结论（同时也是一个通用的建议）：首先查看简单模型在你的数据上的表现：决策树和最近邻（下一课之后，我们将在这个列表中加上逻辑回归）。你可能会碰到这些方法表现已经足够好的情况。
最近邻方法的复杂情形
让我们考虑另一个简单例子。在一个分类问题中，某个特征直接和响应向量成比例。
def form_noisy_data(n_obj=1000, n_feat=100, random_seed=17):
np.random.seed(random_seed)
y = np.random.choice([-1, 1], size=n_obj)
# 第一个特征与目标成比例
x1 = 0.3 * y
# 其他特征为噪声
x_other = np.random.random(size=[n_obj, n_feat - 1])
return np.hstack([x1.reshape([n_obj, 1]), x_other]), y
X, y = form_noisy_data()
一如既往，我们将查看交叉验证和留置集的精确度。让我们构造一条反映最近邻方法的n_neighbors参数与上述两种精确度的关系的曲线。这样的曲线称为验证曲线。
我们看到，基于欧几里得距离的k-NN在这个问题上的表现不好，即使我们尝试在较广范围内改变最近邻数目。
X_train, X_holdout, y_train, y_holdout = train_test_split(X, y, test_size=0.3,
random_state=17)
from sklearn.model_selection import cross_val_score
cv_scores, holdout_scores = [], []
n_neighb = [1, 2, 3, 5] + list(range(50, 550, 50))
for k in n_neighb:
knn = KNeighborsClassifier(n_neighbors=k)
cv_scores.append(np.mean(cross_val_score(knn, X_train, y_train, cv=5)))
knn.fit(X_train, y_train)
holdout_scores.append(accuracy_score(y_holdout, knn.predict(X_holdout)))
plt.plot(n_neighb, cv_scores, label='CV')
plt.plot(n_neighb, holdout_scores, label='holdout')
plt.title('Easy task. kNN fails')
plt.legend();
相反，尽管限制了最大深度，决策树轻易地“检测”到了数据中的隐藏依赖。
tree = DecisionTreeClassifier(random_state=17, max_depth=1)
tree_cv_score = np.mean(cross_val_score(tree, X_train, y_train, cv=5))
tree.fit(X_train, y_train)
tree_holdout_score = accuracy_score(y_holdout, tree.predict(X_holdout))
print(‘Decision tree. CV: {}, holdout: {}’.format(tree_cv_score,
tree_holdout_score))
# Decision tree. CV: 1.0, holdout: 1.0
在这一例子中，决策树完美地解决了问题，而k-NN遇到了困难。不过，这更多的是使用欧几里得距离造成的，而不是方法本身造成的。欧几里得距离没能让揭示出有一个特征比其他所有特征更重要。
6. 决策树和最近邻方法的优势和劣势
决策树的优势和劣势
优势：
生成清晰、易于为人类理解的分类规则，例如“如果年龄不满25岁，并对摩托车感兴趣，拒绝发放贷款”。这一属性称为模型的可解释性。
决策树很容易可视化，即，模型本身（树）和特定测试对象的预测（穿过树的路径）可以“被解释”。
快速训练和预测。
较少参数数目。
支持数值和类别特征。
劣势：
决策树对输入数据中的噪声非常敏感。这削弱了模型的可解释性。
决策树构建的边界有其局限性——它包含与坐标轴垂直的超平面，在实践中比其他方法的效果要差。
我们需要通过剪枝、设定叶节点的最小样本数、设定树的最大深度避免过拟合。注意所有机器学习方法都存在过拟合问题。
不稳定性。数据的小变动会显著改变决策树。这一问题可通过决策树集成处理（以后介绍）。
搜索最佳决策树是一个NP完全问题。实践中使用一些推断方法，比如基于最大信息增益进行贪婪搜索，但这并不能保证找到全局最优决策树。
难以支持数据中的缺失值。Friedman估计CART算法中大约50%的代码是为了支持数据中的缺口（sklearn实现了这一算法的改进版本）。
这一模型只能内插，不能外推（这一点同样适用于随机森林和树提升）。也就是说，对特征空间中，在由训练集圈定的包围盒之外的对象，决策树只能做出常数预测。在我们的黄球和蓝球的例子中，这意味着模型将对所有位于>19或<0的球做出同样的预测。
最近邻方法的优劣
优势：
简单实现。
充分研究。
通常而言，这一方法不仅是分类或回归问题第一个值得尝试的选项，也是推荐问题中值得首先尝试的选项。
通过选择恰当的量度或核（一言以蔽之，核在k-NN方法的框架下为图之类的复杂对象设定了相似性运算），它可以适应特定问题。顺便提一下，以前在kaggle排名第一的Alexander Dyakonov偏爱最简单的k-NN算法（不过基于调整过的对象相似性量度）。
良好的可解释性。不过有例外：如果邻居的数目很大，可解释性会恶化（“我们没有给他发放贷款，因为他和350位客户类似，其中70位客户是不良客户，比数据集的平均值高12%”）。
劣势：
和其他复合算法相比，这一方法算快的。但是，现实生活中，用于分类的邻居数目通常较大（100-150），在这一情形下，k-NN不如决策树快。
如果数据集有很多变量，很难找到合适的权重，也很难判定哪些特征对分类/回归不重要。
依赖于选择的对象间距离量度。默认选项欧几里得距离常常是不合理的。你可以通过网格搜索参数得到良好的解，但在大型数据集上这耗时很长。
没有理论方法选择邻居数——只能进行网格搜索（尽管对于所有模型的所有超参数而言，网格搜索常常是唯一方法）。在邻居数较小的情形下，该方法对离散值很敏感，也就是说，有过拟合的倾向。
由于“维度的诅咒”，有很多特征时它的表现并不好。ML社区知名成员Pedro Domingos教授，在他的流行论文“A Few Useful Things to Know about Machine Learning”中提及了这点。Ian Goodfellow等的《深度学习》第5章讨论了“纬度的诅咒”。
7. 作业三
第三次作业，你将为一个有趣的分类问题构建一颗玩具决策树，以理解决策树是如何工作的。接着你将在UCI成人数据集上训练决策树。
我们建议你在Jupyter notebook上完成任务，接着回答Google表单中的7个问题。提交表单后你仍可以修改你的回答。
截止日期： February 25, 23:59 CET
8. 相关资源
每本ML书基本上都会介绍决策树和K近邻。我们推荐《Pattern Recognition and Machine Learning》（C. Bishop）和《Machine Learning: A Probabilistic Perspective》（K. Murphy）。
《Machine Learning in Action》（P. Harrington）将引导你完全使用Python实现经典ML算法。
scikit-learn库。scikit-learn的开发者致力于编写极为清晰的文档。
Scipy 2017 scikit-learn教程（Alex Gramfort、Andreas Mueller）。
MTH594课程 Advanced data mining: theory and applications包含很多非常好的材料。
GitHub仓库rushter/MLAlgorithms里有许多ML算法的实现，其中包括决策树和k-NN。
欢迎留言分享其他资源。
原文地址：https://medium.com/open-machine-learning-course/open-machine-learning-course-topic-3-classification-decision-trees-and-k-nearest-neighbors-8613c6b6d2cd
相关内容
微信扫码咨询专知VIP会员