Question

ID3算法的具体详细实现步骤如下。

1）对当前样本集合，计算所有属性的信息增益；

2）选择信息增益最大的属性作为测试属性，把测试属性取值相同的样本划为同一个子样本集；

3）若子样本集的类别属性只含有单个属性，则分支为叶子节点，判断其属性值并标上相应的符号，然后返回调用处；否则对子样本集递归调用本算法。

下面将结合餐饮案例实现ID3的具体实施步骤。T餐饮企业作为大型连锁企业，生产的产品种类比较多，另外涉及的分店所处的位置也不同，数目比较多。对于企业的高层来讲，了解周末和非周末销量是否有大的区别，以及天气、促销活动这些因素是否能够影响门店的销量等信息至关重要。因此，为了让决策者准确了解和销量有关的一系列影响因素，需要构建模型来分析天气、是否周末和是否有促销活动对销量的影响，下面以单个门店为例来进行分析。

对于天气属性，数据源中存在多种不同的值，这里将那些属性值相近的值进行类别整合。如天气为“多云”“多云转晴”“晴”这些属性值相近，均是适宜外出的天气，不会对产品销量有太大的影响，因此将它们归为一类，天气属性值设置为“好”。同理，对于“雨”“小到中雨”等天气，均是不适宜外出的天气，因此将它们归为一类，天气属性值设置为“坏”。

对于是否周末属性，周末则设置为“是”，非周末则设置为“否”。

对于是否有促销活动属性，有促销则设置为“是”，无促销则设置为“否”。

产品的销售数量为数值型，需要对属性进行离散化，将销售数据划分为“高”和“低”两类。将其平均值作为分界点，大于平均值的划分到类别“高”，小于平均值的划分为“低”类别。

经过以上的处理，我们得到的数据集合见表5-5。

表5-5　处理后的数据集

数据详见：示例程序/data/sales_data.xls

采用ID3算法构建决策树模型的具体步骤如下。

1）根据公式（5-5），计算总的信息熵。其中，数据中总记录数为34，而销售数量为“高”的数据有18，“低”的有16。

2）根据公式（5-5）和（5-6），计算每个测试属性的信息熵。

对于天气属性，其属性值有“好”和“坏”两种。其中，天气为“好”的条件下，销售数量为“高”的记录为11，销售数量为“低”的记录为6，可表示为（11，6）；天气为“坏”的条件下，销售数量为“高”的记录为7，销售数量为“低”的记录为10，可表示为（7，10）。则天气属性的信息熵计算过程如下。

对于是否周末属性，其属性值有“是”和“否”两种。其中，是否周末属性为“是”的条件下，销售数量为“高”的记录为11，销售数量为“低”的记录为3，可表示为（11，3）；是否周末属性为“否”的条件下，销售数量为“高”的记录为7，销售数量为“低”的记录为13，可表示为（7，13）。则节假日属性的信息熵计算过程如下。

对于是否有促销属性，其属性值有“是”和“否”两种。其中，是否有促销属性为“是”的条件下，销售数量为“高”的记录为15，销售数量为“低”的记录为7，可表示为（15，7）；其中，是否有促销属性为“否”的条件下，销售数量为“高”的记录为3，销售数量为“低”的记录为9，可表示为（3，9）。则是否有促销属性的信息熵计算过程如下。

3）根据公式（5-7），计算天气、是否周末和是否有促销属性的信息增益值。

Gain（天气）=I（18，16）-E（天气）=0.997503-0.957043=0.04046

Gain（是否周末）=I（18，16）-E（是否周末）=0.997503-0.858109=0.139394

Gain（是否有促销）=I（18，16）-E（是否有促销）=0.997503-0.870235=0.127268

4）由第3）步的计算结果可以知道，是否周末属性的信息增益值最大，它的两个属性值“是”和“否”作为该根结点的两个分支。然后按照第1）步到第3）步所示步骤继续对该根结点的3个分支进行结点的划分，针对每一个分支结点继续进行信息增益的计算，如此循环反复，直到没有新的结点分支，最终构成一棵决策树。生成的决策树模型如图5-5所示。

图5-5　ID3生成的决策树模型

从上面的决策树模型可以看出门店的销售高低和各个属性之间的关系，并可以提取出以下决策规则。

若周末属性为“是”，天气为“好”，则销售数量为“高”。

若周末属性为“是”，天气为“坏”，促销属性为“是”，则销售数量为“高”。

若周末属性为“是”，天气为“坏”，促销属性为“否”，则销售数量为“低”。

若周末属性为“否”，促销属性为“否”，则销售数量为“低”。

若周末属性为“否”，促销属性为“是”，天气为“好”，则销售数量为“高”。

若周末属性为“否”，促销属性为“是”，天气为“坏”，则销售数量为“低”。

由于ID3决策树算法采用了信息增益作为选择测试属性的标准，会偏向于选择取值较多的，即所谓高度分支属性，而这类属性并不一定是最优的属性。同时ID3决策树算法只能处理离散属性，对于连续型的属性，在分类前需要对其进行离散化。为了解决倾向于选择高度分支属性的问题，人们采用信息增益率作为选择测试属性的标准，这样便得到C4.5决策树算法。此外，常用的决策树算法还有CART算法、SLIQ算法、SPRINT算法和PUBLIC算法等。

使用Scikit-Learn建立基于信息熵的决策树模型，如代码清单5-2所示。

代码清单5-2　决策树算法预测销量高低代码

#-*- coding: utf-8 -*-
#使用ID3决策树算法预测销量高低
import pandas as pd
#参数初始化
filename = '../data/sales_data.xls'
data = pd.read_excel(filename, index_col = u'序号') #导入数据
#数据是类别标签，要将它转换为数据
#用1来表示“好”“是”“高”这三个属性，用-1来表示“坏”“否”“低”
data[data == u'好'] = 1
data[data == u'是'] = 1
data[data == u'高'] = 1
data[data != 1] = -1
x = data.iloc[:,:3].as_matrix().astype(int)
y = data.iloc[:,3].as_matrix().astype(int)
from sklearn.tree import DecisionTreeClassifier as DTC
dtc = DTC(criterion='entropy') #建立决策树模型，基于信息熵
dtc.fit(x, y) #训练模型
#导入相关函数，可视化决策树。
#导出的结果是一个dot文件，需要安装Graphviz才能将它转换为pdf或png等格式。
from sklearn.tree import export_graphviz
from sklearn.externals.six import StringIO
with open("tree.dot", 'w') as f:
  f = export_graphviz(dtc, feature_names = x.columns, out_file = f)

代码详见：示例程序/code/decision_tree.py

运行代码后，将会输出一个tree.dot的文本文件。由于我们输出中包含中文，需要用文本编辑器在文件中指定中文字体，如，

digraph Tree {
edge [fontname="SimHei"];  /*添加这两行，指定中文字体（这里是黑体）*/
node [fontname="SimHei"];  /*添加这两行，指定中文字体（这里是黑体）*/
0 [label="是否周末 <= 0.0000\nentropy = 0.997502546369\nsamples = 34", shape="box"] ;
1 [label="是否有促销 <= 0.0000\nentropy = 0.934068055375\nsamples = 20", shape="box"] ;…
}

然后将它保存为UTF-8格式。为了进一步将它转换为可视化格式，需要安装Graphviz（跨平台的、基于命令行的绘图工具），然后在命令行中以如下方式编译。

dot -Tpdf tree.dot –o tree.pdf
dot -Tpng tree.dot –o tree.pdf

生成的结果图如下，显然，它等价于图5-5。

5.1.5　人工神经网络

人工神经网络^[9][10]（Artificial Neural Networks，ANN），是模拟生物神经网络进行信息处理的一种数学模型。它以对大脑的生理研究成果为基础，其目的在于模拟大脑的某些机理与机制，实现一些特定的功能。

1943年，美国心理学家McCulloch和数学家Pitts联合提出了形式神经元的数学模型MP模型，证明了单个神经元能执行逻辑功能，开创了人工神经网络研究的时代。1957年，计算机科学家Rosenblatt用硬件完成了最早的神经网络模型，即感知器，并用来模拟生物的感知和学习能力。1969年M.Minsky等仔细分析了以感知器为代表的神经网络系统的功能及局限后，出版了《Perceptron》（感知器）一书，指出感知器不能解决高阶谓词问题，人工神经网络的研究进入一个低谷期。20世纪80年代以后，超大规模集成电路、脑科学、生物学、光学的迅速发展为人工神经网络的发展打下了基础，人工神经网络的发展进入兴盛期。

人工神经元是人工神经网络操作的基本信息处理单位。人工神经元的模型如图5-6所示，它是人工神经网络的设计基础。一个人工神经元对输入信号X＝[x₁，x₂，…x_m]^T的输出y为y＝f（u＋b），其中，公式中各字符的含义如图5-6所示。

图5-6　人工神经元模型

激活函数主要有以下3种形式，见表5-6。

人工神经网络的学习也称为训练，指的是神经网络在受到外部环境的刺激下调整神经网络的参数，使神经网络以一种新的方式对外部环境作出反应的一个过程。在分类与预测中，人工神将网络主要使用有指导的学习方式，即根据给定的训练样本，调整人工神经网络的参数以使网络输出接近于已知的样本类标记或其他形式的因变量。

表5-6　激活函数分类表

在人工神经网络的发展过程中，提出了多种不同的学习规则，没有一种特定的学习算法适用于所有的网络结构和具体问题。在分类与预测中，δ学习规则（误差校正学习算法）是使用最广泛的一种。误差校正学习算法根据神经网络的输出误差对神经元的连接强度进行修正，属于有指导学习。设神经网络中神经元i作为输入，神经元j为输出神经元，它们的连接权值为wij，则对权值的修正为Δw_ij＝ηδ_jY_i，其中η为学习率，δ_j＝T_j－Y_j为j的偏差，即输出神经元j的实际输出和教师信号之差，示意图如图5-7所示。

图5-7　δ学习规则示意图

神经网络训练是否完成常用误差函数（也称目标函数）E来衡量。当误差函数小于某一个设定的值时即停止神经网络的训练。误差函数为衡量实际输出向量Y_k与期望值向量T_k误差大小的函数，常采用二乘误差函数来定义为（或）k＝1，2，…，N为训练样本个数。

使用人工神经网络模型需要确定网络连接的拓扑结构、神经元的特征和学习规则等。目前，已有近40种人工神经网络模型，常用的用来实现分类和预测的人工神经网络算法见表5-7。

表5-7　人工神经网络算法

BP神经网络的学习算法是δ学习规则，目标函数采用，下面详细介绍BP神经网络算法。

反向传播（Back Propagation，BP）算法的特征是利用输出后的误差来估计输出层的直接前导层的误差，再用这个误差估计更前一层的误差，如此一层一层的反向传播下去，就获得了所有其他各层的误差估计。这样就形成了将输出层表现出的误差沿着与输入传送相反的方向逐级向网络的输入层传递的过程。这里我们以典型的三层BP网络为例，描述标准的BP算法。图5-8所示的是一个有3个输入节点，4个隐层节点，1个输出节点的一个三层BP神经网络。

图5-8　三层BP神经网络结构

BP算法的学习过程由信号的正向传播与误差的逆向传播两个过程组成。正向传播时，输入信号经过隐层的处理后，传向输出层。若输出层节点未能得到期望的输出，则转入误差的逆向传播阶段，将输出误差按某种子形式，通过隐层向输入层返回，并“分摊”给隐层4个节点与输入层x₁、x₂、x₃三个输入节点，从而获得各层单元的参考误差或称误差信号，作为修改各单元权值的依据。这种信号正向传播与误差逆向传播的各层权矩阵的修改过程，是周而复始进行的。权值不断修改的过程，也就是网络的学习（或称训练）过程。此过程一直进行到网络输出的误差逐渐减少到可接受的程度或达到设定的学习次数为止，学习过程的流程图如图5-9所示。

算法开始后，给定学习次数上限，初始化学习次数为0，对权值和阈值赋予小的随机数，一般在[-1，1]之间。输入样本数据，网络正向传播，得到中间层与输出层的值。比较输出层的值与教师信号值的误差，用误差函数E来判断误差是否小于误差上限，如不小于误差上限，则对中间层和输出层权值和阈值进行更新，更新的算法为δ学习规则。更新权值和阈值后，再次将样本数据作为输入，得到中间层与输出层的值，计算误差E是否小于上限，学习次数是否到达指定值，如果达到，则学习结束。

图5-9　BP算法学习过程流程图

BP算法只用到均方误差函数对权值和阈值的一阶导数（梯度）的信息，使得算法存在收敛速度缓慢、易陷入局部极小等缺陷。为了解决这一问题，Hinton等人于2006年提出了非监督贪心逐层训练算法，为解决深层结构相关的优化难题带来希望，并以此为基础发展成了如今脍炙人口的“深度学习”算法。本书中所建立的神经网络，结构跟传统的BP神经网络是类似的，但是求解算法已经用了新的逐层训练算法。限于篇幅，本文不对深度学习做进一步的讲解。有兴趣的读者，请自行搜索并阅读相关资料。

在第2章我们已经提过，Scikit-Learn中并没有神经网络模型，我们认为Python中比较好的神经网络算法库是Keras，这是一个强大而易用的深度学习算法库。在本书中，我们仅仅牛刀小试，把它当成一个基本的神经网络算法库来看待。

针对表5-5的数据应用神经网络算法进行建模，建立的神经网络有3个输入节点、10个隐藏节点和1个输出节点，其Python代码如代码清单5-3所示。

代码清单5-3　神经网络算法预测销量高低

#-*- coding: utf-8 -*-
#使用神经网络算法预测销量高低
import pandas as pd
#参数初始化
inputfile = '../data/sales_data.xls'
data = pd.read_excel(inputfile, index_col = u'序号') #导入数据
#数据是类别标签，要将它转换为数据
#用1来表示“好”“是”“高”这3个属性，用0来表示“坏”“否”“低”
data[data == u'好'] = 1
data[data == u'是'] = 1
data[data == u'高'] = 1
data[data != 1] = 0
x = data.iloc[:,:3].as_matrix().astype(int)
y = data.iloc[:,3].as_matrix().astype(int)
from keras.models import Sequential
from keras.layers.core import Dense, Activation
model = Sequential() #建立模型
model.add(Dense(3, 10))
model.add(Activation('relu')) #用relu函数作为激活函数，能够大幅提供准确度
model.add(Dense(10, 1))
model.add(Activation('sigmoid')) #由于是0-1输出，用sigmoid函数作为激活函数
model.compile(loss = 'binary_crossentropy', optimizer = 'adam', class_mode = 'binary')
#编译模型。由于我们做的是二元分类，所以我们指定损失函数为binary_crossentropy，以及模式为binary
#另外常见的损失函数还有mean_squared_error、categorical_crossentropy等，请阅读帮助文件。
#求解方法我们指定用adam，还有sgd、rmsprop等可选
model.fit(x, y, nb_epoch = 1000, batch_size = 10) #训练模型，学习一千次
yp = model.predict_classes(x).reshape(len(y)) #分类预测
from cm_plot import * #导入自行编写的混淆矩阵可视化函数
cm_plot(y,yp).show() #显示混淆矩阵可视化结果

代码详见：示例程序/code/neural_network.py

运行上面的代码，可以得到下面的混淆矩阵图，如图5-10所示。

图5-10　BP神经网络预测销量高低混淆矩阵图

从图5-10可以看出，检测样本为34个，预测正确的个数为26个，预测准确率为76.4%，预测准确率较低，是由于神经网络训练时需要较多样本，而这里是由于训练数据较少造成的。

需要指出的是，这里的案例比较简单，我们并没有考虑过拟合的问题。事实上，神经网络的拟合能力是很强的，容易出现过拟合现象。跟传统的添加“惩罚项”的做法不同，目前神经网络（尤其是深度神经网络）中流行的防止过拟合的方法是随机地让部分神经网络节点休眠。

5.1.6　分类与预测算法评价

分类与预测模型对训练集进行预测而得出的准确率并不能很好地反映预测模型未来的性能，为了有效判断一个预测模型的性能表现，需要一组没有参与预测模型建立的数据集，并在该数据集上评价预测模型的准确率，这组独立的数据集叫作测试集。模型预测效果评价，通常用相对/绝对误差、平均绝对误差、均方误差、均方根误差等指标来衡量。

（1）绝对误差与相对误差

设Y表示实际值，表示预测值，则称E为绝对误差（Absolute Error），计算公式如下。

e为相对误差（RelativeError），计算公式如下。

有时相对误差也用百分数表示。

这是一种直观的误差表示方法。

（2）平均绝对误差

平均绝对误差（MeanAbsoluteError，MAE）定义如下。

式中各项的含义如下。

MAE：平均绝对误差。

E_i：第i个实际值与预测值的绝对误差。

Y_i：第i个实际值。

：第i个预测值。

由于预测误差有正有负，为了避免正负相抵消，故取误差的绝对值进行综合并取其平均数，这是误差分析的综合指标法之一。

（3）均方误差

均方误差（Mean Squared Error，MSE）定义如下。

在上式中，MSE表示均方差，其他符号同前。

本方法用于还原平方失真程度。

均方误差是预测误差平方之和的平均数，它避免了正负误差不能相加的问题。由于对误差E进行了平方，加强了数值大的误差在指标中的作用，从而提高了这个指标的灵敏性，是一大优点。均方误差是误差分析的综合指标法之一。

（4）均方根误差

均方根误差（Root Mean Squared Error，RMSE）定义如下。

上式中，RMSE表示均方根误差，其他符号同前。

这是均方误差的平方根，代表了预测值的离散程度，也称为标准误差，最佳拟合情况为RMSE＝0。均方根误差也是误差分析的综合指标之一。

（5）平均绝对百分误差

平均绝对百分误差（Mean Absolute Percentage Error，MAPE）定义如下。

上式中，MAPE表示平均绝对百分误差。一般认为MAPE小于10时，预测精度较高。

（6）Kappa统计

Kappa统计是比较两个或多个观测者对同一事物，或观测者对同一事物的两次或多次观测结果是否一致，以由于机遇造成的一致性和实际观测的一致性之间的差别大小作为评价基础的统计指标。Kappa统计量和加权Kappa统计量不仅可以用于无序和有序分类变量资料的一致性、重现性检验，而且能给出一个反映一致性大小的“量”值。

Kappa取值在［-1，+1］之间，其值的大小均有不同意义。

Kappa＝+1说明两次判断的结果完全一致。

Kappa＝-1说明两次判断的结果完全不一致。

Kappa＝0说明两次判断的结果是机遇造成。

Kappa＜0说明一致程度比机遇造成的还差，两次检查结果很不一致，在实际应用中无意义。

Kappa＞0此时说明有意义，Kappa越大，说明一致性越好。

Kappa≥0.75说明已经取得相当满意的一致程度。

Kappa＜0.4说明一致程度不够。

（7）识别准确度

识别准确度（Accuracy）定义如下。

式中各项说明如下。

TP（True Positives）：正确的肯定表示正确肯定的分类数。

TN（True Negatives）：正确的否定表示正确否定的分类数。

FP（False Positives）：错误的肯定表示错误肯定的分类数。

FN（False Negatives）：错误的否定表示错误否定的分类数。

（8）识别精确率

识别精确率（Precision）定义如下。

（9）反馈率

反馈率（Recall）定义如下。

（10）ROC曲线

受试者工作特性（Receiver Operating Characteristic，ROC）曲线是一种非常有效的模型评价方法，可为选定临界值给出定量提示。将灵敏度（Sensitivity）设在纵轴，1-特异性（1-Specificity）设在横轴，就可得出ROC曲线图。该曲线下的积分面积（Area）大小与每种方法优劣密切相关，反映分类器正确分类的统计概率，其值越接近1说明该算法效果越好。

（11）混淆矩阵

混淆矩阵（Confusion Matrix）是模式识别领域中一种常用的表达形式。它描绘样本数据的真实属性与识别结果类型之间的关系，是评价分类器性能的一种常用方法。假设对于N类模式的分类任务，识别数据集D包括T0个样本，每类模式分别含有Ti个数据（i＝1，…，N）。采用某种识别算法构造分类器C，cmij表示第i类模式被分类器C判断成第j类模式的数据占第i类模式样本总数的百分率，则可得到N×N维混淆矩阵CM（C，D）。

混淆矩阵中元素的行下标对应目标的真实属性，列下标对应分类器产生的识别属性。对角线元素表示各模式能够被分类器C正确识别的百分率，而非对角线元素则表示发生错误判断的百分率。

通过混淆矩阵，可以获得分类器的正确识别率和错误识别率。

各模式正确识别率：

平均正确识别率：

各模式错误识别率：

平均错误识别率：

对于一个二分类预测模型，分类结束后的混淆矩阵如表5-8所示。

表5-8　混淆矩阵

如有150个样本数据，这些数据分成3类，每类50个。分类结束后得到的混淆矩阵如下。

第1行的数据说明有43个样本正确分类，有5个样本应该属于第1类，却错误分到了第二类，有2个样本应属于第一类，却错误地分到第三类。

5.1.7　Python分类预测模型特点

首先总结一下常见的分类/预测模型，见表5-9。这些模型的使用方法大同小异，因此不再赘述，请读者参考本书相应的例子，以及对应的官方帮助文档。

表5-9　常见的模型评价和在Python中的实现

经过对前面章节中的分类与预测的学习，我们应该基本认识到了Python建模的特点。首先，我们需要认识到：Python本身是一门面向对象的编程语言，这就意味着很多Python的程序是面向对象的。放到建模之中，我们就会发现，不管是在Scikit-Learn还是Keras中，建模的第一个步骤是建立一个对象，这个对象是空白的，需要进一步训练的，然后我们要设置模型的参数，接着就是通过fit（）方法对模型进行训练，最后通过predict（）方法预测结果。当然，还有一些方法有助于我们完成对模型的评估，如score（）等。

Scikit-Learn和Keras的功能都非常强大，我们能够做的仅仅是通过一些简单的例子介绍它们的基本功能，这仅仅是它们本身功能的冰山一角。因此，我们再次强调，如果遇到书本上没有讲解过的问题，应当尽可能地查阅官方的帮助文档。只有官方的帮助文章，才有可能全面地提供解决问题的答案。