数据挖掘即研究如何从大量数据或者数据库中提取有用信息。

而机器学习则是数据挖掘的一种方法，是研究计算机如何模仿人类的思维方式进行学习。

一个非常有名的例子详细大家都听说过，就是沃尔玛在分析研究人们购物留下的账单时发现很多购买了尿布的账单上会同时出现啤酒这个商品，通过调查得知原来很多奶爸在下班后收到家里妻子的请求希望给孩子买一些尿布，在给孩子买尿布的同时往往会顺带买一些啤酒，于是沃尔玛利用“啤酒和尿布”的效应，将二者的货架摆放在一起并且捆绑打折出售，结果二者的销量大增。

这就是一个非常典型的从海量数据中提取有用信息并且将该信息服务于我们日常的生产生活中，那么作为数据挖掘的一种有利工具，机器学习主要包括分类分析、回归分析、聚类分析、异常分析、关联分析、推荐分析、时序分析。上述的啤酒尿布的例子就是一个非常典型的推荐分析。

下面我们先从分类分析开始。

一、分类定义

分类故名思意就是对数据进行分别归类，通过构建一个分类模型，然后利用分类模型将数据对象映射到给定的类别中。

分类主要包含三步：

（1）第一步是根据训练数据进行分类模型；

（2）第二步是将分类模型在测试集上验证性能，这个测试集可以是提前准备好的，也可以是将训练集按照比例进行划分，一部分用来训练模型，一部分用来测试模型.；

（3）第三步是在得到一个性能较优的分类器前提下，对未知类别的数据进行分类。

例如这是一张已知天气状况的数据属性表，最后一栏是在该天气状况下是否适合打网球，我们希望对这些已知的数据进行分析，得到一个分类模型，让给定的任意天气状况属性值就能判断是否适合打网球。

Day	Outlook	Temperature	Humidity	Wind	PlayTennis
1	Sunny	Hot	High	Weak	No
2	Sunny	Hot	High	Strong	No
3	Overcast	Hot	High	Weak	Yes
4	Rain	Mild	High	Weak	Yes
5	Rain	Cool	Normal	Weak	Yes
6	Rain	Cool	Normal	Strong	No
7	Overcast	Cool	Normal	Strong	Yes
8	Sunny	Mild	High	Weak	No
9	Sunny	Cool	Normal	Weak	Yes
10	Rain	Mild	Normal	Weak	Yes
11	Sunny	Mild	Normal	Strong	Yes
12	Overcast	Mild	High	Strong	Yes
13	Overcast	Hot	Normal	Weak	Yes
14	Rain	Mild	High	Strong	No

15

Sunny

Cool

High

Strong

？

二、分类模型的评估指标

在分类的第二步我们可以通过训练集得到很多分类器，我们主要通过以下几个指标对分类器进行性能评估：

1. 精度：即分类的准确度，通过在测试集上进行验证可以得到分类器分类的准确度；
2. 速度：即构建分类器的时间消耗，该指标可能与计算机的算力性能有关；
3. 鲁棒性：即模型面对不同的多样未知数据的稳定性能，特别是面对一些含缺省值和噪声的数据样本。

三、分类的常用方法

分类分析有很多方法，比较常用的包括以下几点：

• 决策树学习
• 贝叶斯学习
• 最近邻学习
• 线性学习
• 支持向量机学习
• 神经网络学习
• 演化学习
• 集成学习

四、决策树学习

决策树学习（Decision Tree Learning）是一种非常常见的分类方法，通过构造树模型来对未知类别样本进行分类，以一种离散化的方法得到数据的类别。决策树一般有以下特点：

• 叶子结点对应着不同的决策类别信息
• 内部结点对应着属性的判断，通过判断的结果将待测样本划分到该结点的子结点中
• 从根结点出发到叶子结点的路径对应着一条决策的规则

决策树采取的是递归的方法，生成的步骤如下：

1. 选取最好的属性作为树的根结点；
2. 对根结点的取值进行属性判断，将样本划分到不同的子结点中；
3. 对每一个子结点重复1,2步骤，直到所有的子节点都是叶子节点。

通过其生成步骤可以发现决策树的生成需要解决以下问题：

（1）选择最好属性的度量标准

根据决策树的生成步骤，我们可以知道选择作为根结点的属性，需要满足经过该属性划分后的子结点之间差异性越大越好，即子结点包括的样本集合纯度越来越高，这就要求选择的属性在样本划分前后不纯度降低程度越大越好。

这里我们引入了不纯度这个概念，我们将不纯度的降低程度记为，则有下列公式：

                                                                      

其中是父结点的不纯度，为第j个子结点的不纯度，k为属性的取值个数，N为父结点的样本数，N(j)为第j个子结点的样本数。

我们引入熵的概念来代表任意结点的不纯度，熵的计算公式如下：

                                                                      

其中为结点t中第i类样本占该结点样本总数的比例。

所以可以得到熵减最大的公式：

                                                    

直接使用熵减作为度量标准可能会碰到一个问题，就是这种策略会尽可能选取那种属性值取值比较多的属性，因为选取这种属性经过划分后熵减会非常大，比如上面的打网球例子，根结点大概率会选取属性date，而显然选择属性date并没有什么意义。

为了避免出现这种情况，我们将这种有较多属性值的属性添加一个惩罚，除上属性的分裂信息，得到新的度量信息熵减率：

                                                                 

同时我们也可以直接将分母换为样本数k，得到度量标准平均熵减：

                                                                    

按熵减的大小对天气属性进行决策树的构建，得到以下决策树：

（2）样本属性值缺失

实际任务中常常会碰到样本缺失某些属性值，面对这些缺失属性值的样本，往往有两种解决办法：

①如果样本总数比较大的话，并且缺失属性值的样本数不多时，可以直接舍弃缺失属性值的样本；

②根据其他属性值已知的样本来估计缺失属性值的样本。

（3）样本属性为连续值

在实际任务中，难免会遇到有些属性值是连续的，而决策树在进行结点的属性判断时要将样本分为不同的子结点，将连续属性值离散化就成了一个必须的步骤，主要的离散方法包括：无监督离散化和有监督离散化

无监督离散化常用的有等深分箱法和等宽分箱法，等深分箱法即每个箱子中样本的个数相同，等宽分箱法即每个箱子的取值范围大小相同。

有监督离散化常用的方法是二分法，即将按照属性值连续的属性值将样本进行排列，找出类别不同的相邻样本，那么离散的边界阈值一定在这些相邻样本间，然后计算每个相邻样本之间阈值的熵减，选择熵减最大的阈值对该属性进行离散化

（4）叶结点的判定

决策树的生成是一个递归的过程，既然是递归，那么就涉及到递归什么时候返回，通俗一点就是划分到什么时候会认为当前的结点就是叶结点，当出现以下三种情况的时候我们就认为当前结点为叶子结点：

• 当前结点中的样本集合为空
• 当前结点中的样本集合都属于同一类
• 当前结点中的所有样本在所有属性上取值都相同，即属性已经被划分完

（5）过拟合

过拟合是机器学习算法的通病，如何避免将训练集的一些特点当作所有数据的共同特点是研究的热点。

在决策树问题中，往往通过剪枝的策略来避免过拟合问题，剪枝分为”预剪枝“和”后剪枝“：

”预剪枝“：在生成完整的决策树之前就强制让决策树停止生长，避免分类器学习到一些训练集的”特性“；

”后剪枝“：在决策树生长完成之后，通过策略对树进行剪枝，剪去学习到的”特性“。

（6）待测样本的分类问题

当构建好决策树后，将如何对待测样本进行分类呢？

我们通常的做法是从决策树的根结点开始，按照结点的属性将样本分到对应的子结点中，然后一直分到叶结点，最后根据叶结点集合中的样本类别计算待测样本最大概率属于哪个类别，最后将该类别输出。

五、贝叶斯学习

贝叶斯学习是基于概率统计的一种分类方法，其基本思想是通过先验概率来计算后验概率，贝叶斯定理公式如下：

                                                                         

为已知A发生时B发生的概率