挖掘建模之分类与预测

根据挖掘目标和数据形式可以建立分类与预测、聚类分析、关联规则、时序模式、偏差检测、智能推荐等模型，帮助企业提取数据中蕴含的商业价值，提高企业的竞争力。

1.分类与预测

就餐饮企业而言，经常会碰到这样的问题：      
1）如何基于菜品历史销售情况，以及节假日、气候和竞争对手等影     响因素，对菜品销量进行趋势预测？      
2）如何预测在未来一段时间哪些顾客会流失，哪些顾客最有可能会       成为VIP客户？      
3）如何预测一种新产品的销售量，以及在哪种类型的客户中会较受欢迎？

除此之外，餐厅经理需要通过数据分析来帮助他了解具有某些特征的顾客的消费习惯；餐饮企业老板希望知道下个月的销售收入，原材料采购需要投入多少，这些都是分类与预测的例子。

1.1 实现过程

• 分类和预测是预测问题的两种主要类型。
• 分类主要是预测分类标号（离散、无序的），而预测主要是建立连续值函数模型，预测给定自变量的条件下因变量的值

分类：指将数据映射到预先定义好的群组或类。
因为在分析测试数据之前，类别就已经确定了，所以分类通常被称为有监督的学习。分类算法要求基于数据属性值来定义类别。分类就是构造一个分类模型，把具有某些特征的数据项映射到某个给定的类别上。下图是一个三分类问题：

预测：确定两种或两种以上变量间相互依赖的函数模型，然后进行预测或控制。

分类和预测的实现过程类似，以分类模型为例，实现过程如图：

分类算法有两步过程：
第一步是学习步，通过归纳分析训练样本集来建立分类模型得到分类规则；
第二步是分类步，先用已知的检验样本集评估分类规则的准确率，如果准确率是可以接受的，则使用该模型对未知类标号的待测样本集进行预测。

预测模型的实现也有两步，类似于分类模型，
第一步是通过训练集建立预测属性（数值型的）的函数模型，
第二步是预测，模型通过检验后再进行预测或控制。

1.2 常用的分类与预测算法

主要分类与预测算法简介：

1.3 回归分析

• 回归分析是通过建立模型来研究变量之间相互关系的密切程度、结构状态及进行模型预测的一种有效工具，在工商管理、经济、社会、医学和生物学等领域应用十分广泛。
• 从19世纪初高斯提出最小二乘估计算起，回归分析的历史已有200多年。从经典的回归分析方法到近代的回归分析方法，按照研究方法划分，回归分析研究的范围大致如下：

在数据挖掘环境下，自变量与因变量具有相关关系，自变量的值是已知的，因变量是要预测的。

常用的回归模型如下： 

 用于建模的数据集表示为{(x1,y1),(x2,y2)，......,(xm,ym)}，用数学公式                     可表示该模型。 将特征X中每一个值xi都带入其中，得到对应的h(xi)，定义可以将损失定义为yi和h(xi)之间的差值平方的和，可修改为。 求损失值的最小值：最小二乘法或梯度下降法等。 该模型其实就是从一堆训练集中去算出一条直线，使数据集到直线之间的距离差最小。

练习1

1.利用一元线性回归模型，预测工资收入与工作年限之间的关系。

一元线性回归模型反应的是单个自变量对因变量的影响。
多元线性回归模型则反应多个自变量对因变量的影响，模型中含有多个自变量和1个因变量。

求损失值的最小值：最小二乘法或梯度下降法等。

1.4 决策树

决策树算法在分类、预测、规则提取等领域有着广泛应用。在20世纪70年代后期和80年代初期，机器学习研究者J.Ross Quinilan提出了ID3算法以后，决策树在机器学习、数据挖掘邻域得到极大的发展。Quinilan后来又提出了C4.5，成为新的监督学习算法的性能比较基准。1984年几位统计学家提出了CART分类算法。ID3和CART算法大约同时被提出，但都是采用类似的方法从训练元组中学习决策树。
决策树是一树状结构，它的每一个树结点可以是叶节点，对应着某一类，也可以对应着一个划分，将该节点对应的样本集划分成若干个子集，每个子集对应一个节点。对一个分类问题，从已知类标记的训练元组学习并构造出决策树是一个从上至下，分而治之的过程。

选择一个合适的特征（属性）作为判断节点，可以快速的分类，减少决策树的深度。
特征（属性）选择的目标使得分类后的数据集比较纯，降低数据的复杂度。
如何衡量一个数据集纯度，这里要引入数据纯度函数：信息增益，信息增益率和基尼系数。

常用的决策树算法如下表所示，本节将详细介绍ID3算法，也是最经典的决策树分类算法。

信息熵和信息增益：

信息熵表示的是不确定度，也可以说是信息量的大小。数据集种各类别数据均匀分布时，不确定度最大，信息量最大，此时熵就最大。当选择某个特征（属性）对数据集进行分类时，分类后的数据集信息熵会比分类前的小，其差值表示为信息增益。

假设在样本数据集 D 中，混有 c 种类别的数据。构建决策树时，根据给定的样本数据集选择某个特征值作为树的节点。在数据集中，可以计算出该数据中的信息熵：

其中 D 表示训练数据集，c 表示数据类别数，pi 表示类别 i 样本数量占所有样本的比例。

对应数据集 D，选择特征 A 作为决策树判断节点时，在特征 A 作用后的信息熵的为 Info(D)，计算如下：

其中 k 表示样本 D 被分为 k 个部分。 信息增益表示数据集 D 在特征 A 的作用后，其信息熵减少的值。公式如下：

ID3算法的具体实现步骤：
（1）计算当前样本集合中所有属性的信息增益。
（2）选择信息增益大的属性作为测试属性，把测试属性取值相同的样本划分为同一个样本子集。（3）若样本子集的类别只含有单个属性或者没有再可选择的属性进行样本划分，则分支为叶子节点，判断其属性值并标注上相应的符号，然后返回调用处；否则，对样本子集递归调用本算法。

• ID3算法是一种基于信息增益的决策树分类算法，它选择当前样本集中具有最大信息增益值的属性作为测试属性；样本集的划分则依据测试属性的取值进行，测试属性有多少不同取值就将样本集划分为多少子样本集，同时，决策树上相应于该样本集的节点长出新的叶子节点。
• ID3算法根据信息理论，采用划分后样本集的不确定性作为衡量划分好坏的标准，用信息增益值度量：信息增益值越大，不确定性越小。因此，ID3算法在每个非叶节点选择信息增益最大的属性作为测试属性。该属性使得对结果划分中的样本分类所需的信息最小，并反映划分的最小随机性。

1.5 ID3算法——示例（buy_computer) 

首先，计算数据集分类前的熵：
在数据集中，给定的样本数量为14，类标号为Yes (表示购买电脑)的样本数量为n1=9，类标号为No (表示不购买电脑)的样本数量为n2=5，因此数据集中两个类别的先验概率分别为：     p(Yes)=n1/total=9/14            
p(No)=n2/total=5/14

对数据集分类前的熵为：        
 Info(n1,n2)
=-p(Yes)*log(p(Yes))-p(No)*log(p(No))                            
=-9/14*log(9/14)-5/14*log(5/14)                            
≈0.94

其次，计算各属性划分数据集时的信息增益：
先计算属性age的熵。由于属性age有三个不同取值（youth，middle_aged，senior），因此可将数据集划分成三个子集：X1, X2和X3。
对于子集X1(age=youth)，它的样本数量为n1=5，其中类标号为Yes的数量n11=2，类标号为No的数量n12=3，则这两类样本在子集X1中所占的比例分别为：          
p11=n11/n1=2/5=0.4          
p12=n12/n1=3/5=0.6

这样，子集X1的熵为：        
Info(n11,n12)
=-p11*log(p11)-p12*log(p12)                            
=-0.4*log(0.4)-0.6*log(0.6) 

 其次，计算各属性划分数据集时的信息增益：
先计算属性age的熵。由于属性age有三个不同取值（youth，middle_aged，senior），因此可将数据集划分成三个子集：X1, X2和X3。
对于子集X2(age=middle_aged)，它的样本数量为n2=4，其中类标号为Yes的数量n12=4，类标号为No的数量n22=0，则这两类样本在子集X2中所占的比例分别为：          
p21=n12/n2=4/4=1          
p22=n22/n2=0/4=0

这样，子集X2的熵为：        
Info(n12,n22)=-p12*log(p12)-p22*log(p22)=0

其次，计算各属性划分数据集时的信息增益：
先计算属性age的熵。由于属性age有三个不同取值（youth，middle_aged，senior），因此可将数据集划分成三个子集：X1, X2和X3。
对于子集X3(age=senior)，它的样本数量为n3=5，其中类标号为Yes的数量n13=3，类标号为No的数量n23=2，则这两类样本在子集X3中所占的比例分别为：          
p13=n13/n3=3/5=0.6          
p23=n23/n3=2/5=0.4

这样，子集X3的熵为：        
Info(n13,n23)
=-p13*log(p13)-p23*log(p23)                            
=-0.6*log(0.6)-0.4*log(0.4) 

 其次，计算各属性划分数据集时的信息增益：
先计算属性age的熵。由于属性age有三个不同取值（youth，middle_aged，senior），因此可将数据集划分成三个子集：X1, X2和X3。
由于子集X1, X2和X3各自的期望信息分别为Info(n11,n12)，Info(n12,n22)和Info(n13,n23)，因此，属性age划分数据集的熵为：    
E(age) =
5/14*Info(n11,n12) + 4/14*Info(n12,n22) + 5/14*Info(n13,n23)              
≈ 0.694
计算属性age的信息增益为：      
Gain(age) = Info(Yes,No) – E(age) = 0.94 – 0.694 = 0.246

其次，计算各属性划分数据集时的信息增益：
按上述方式，可依次计算其他属性的信息增益分别为：
Gain(income) = 0.029
Gain(student) = 0.151
Gain(credit_rating) = 0.048

在4个属性中，age的信息增益最大(0.246)，因此先以该属性来划分数据集。

ID3算法的优点：

ID3算法通常只需要测试一部分属性就可完成对训练数据集的分类。
从ID3算法构建的决策树中，很容易获得相应的决策规则。

ID3算法的缺点：

ID3算法在选择根节点和内部结点的属性时，使用信息增益作为评价标准。 信息增益更倾向于选择取值种类较多的属性进行划分，而不一定是最优属性进行划分。
ID3算法只能对属性值为离散型的数据集进行划分（构建决策树），不能处理属性值为连续型的数据集。

C4.5算法使用信息增益比来确定分枝属性，能够克服ID3算法使用信息增益时偏向于取值类型较多属性的不足。 属性Af的信息增益比的定义为： 其中：

C4.5算法既可以处理离散型描述属性，也可以处理连续型描述属性。

• 当处理离散型属性时，C4.5算法与ID3算法相同；
• 当处理连续型属性时，C4.5算法需要先将连续型属性转换成离散型属性。 

当处理连续型属性时，C4.5算法需要先将连续型属性转换成离散型属性。 对于连续值属性Ac，假设在某个结点上的样本数量为total，则C4.5算法将进行如下操作：
(1) 将该结点上的所有样本按照属性的取值由小到大排序，得到排序结果{A1c, A2c, ..., Atotalc}；
(2) 在{A1c, A2c, ..., Atotalc}中生成total-1个分割点     其中：第i个(1≤i≤total-1)分割点的取值设置为vi=(Aic+A(i+1)c)/2。
(3) 从total-1个分割点中选择最佳分割点。     其中：最佳分割点具有最大信息增益比。

将“buy_computer”中的属性age的取值由{youth, middle_aged, senior}改为具体年龄{32, 25, 46, 56, 60, 52, 42, 36, 23, 51, 38, 43, 41, 65}，C4.5算法离散化的具体过程。

(1) 对年龄序列由小到大排序，新的序列为{23, 25, 32, 36, 38, 41, 42, 43, 46, 51, 52, 56, 60, 65}；

(2) 对新的年龄序列生成分割点：由于样本数量为14，因此可生成13个分割点。
例如：第一个分割点为(23+25)/2=24，它可将数据集划分为年龄在区间[23, 24]的样本和在区间(24, 65]的样本。 

(3) 选择最佳分割点。
例如：对于第一个分割点，可以计算得到年龄在区间[23, 24]和(24, 65]的样本数量以及每个区间的样本属于各个类别的数量，从而计算第一个分割点的信息增益比。
依此方式，计算其他分割点的信息增益比，并从中选出具有最大信息增益比的分割点。

(4) 根据最佳分割点，离散化属性的连续值。
例如：当最佳分割点为37时，数据集中的样本可以根据age取值分成两类，一类是≤37，另一类是＞37。
说明：在有些情况下，可能需要确定多个最佳分割点。可以按上述过程获得依次信息增益比最大的分割点、次大的分割点等等。