数据挖掘的经典算法：分类算法

监督学习和非监督学习

首先关于监督学习和非监督学习的区别，监督学习是有一组训练集，并且训练集都标注好了类别属性，我们可以通过训练集来构建分类模型和分类标准。非监督学习的训练集则不带有类别属性，我们需要通过比较训练集的特点构建不同的集群。

分类算法（Classification)

分类算法就属于前文提到的监督学习中的一种，我们需要通过已知类别属性的训练集来构建分类模型，通过构建好的模型对未知类别属性的数据进行预测。所以分类算法大致包含三部分：模型构建，模型的检测和模型使用。

上面的两幅图描述了模型构建和模型使用的大致过程，在图片里使用的数据中，“TENURED”属性是类别属性，我们通过训练集得出了关于“TENURED”的分类标准，也就是：IF rank=‘Professor’ OR years > 6 THEN tenured=‘yes’

关于模型的检测，就是除了训练集之外，还会有一组标注了类别属性的测试集用来测试模型的正确性，后文讲到具体算法时再分析。
介绍完了分类算法的大致过程，接下来介绍几种具体的算法

决策树归纳

决策树归纳，顾名思义是构建一颗类似树结构的分类模型，下面来看一个例子。

上图就是一颗构建好的决策树。不难发现树的叶子节点对应着类别属性，非叶子节点对应着一个特征属性。上图描述了一个关于顾客是否购买电脑的预测模型，我们可以通过年龄，收入等特征属性来判断该顾客是否会购买电脑。

接下来的关键就是通过训练集构建合适的决策树，训练集就是右上角的一组给定类别属性的数据。

介绍构建流程之前首先需要先介绍几个概念：
熵：熵是信息论中的一个概念，它描述了信息的不确定性，也可以描述成想知道答案需要的信息量。显然，熵的值越大代表不确定性越高，所需要的信息量越多。 计算公式：H(x) = E[I(xi)] = E[ log(2,1/P(xi)) ] = -∑P(xi)log(2,P(xi)) (i=1,2,…n)

Expected information描述了类别属性的不确定性，第二行的公式表示了经过特征属性A的分类后，类别属性D的不确定性，Information gained是前两个值相减，描述了用属性A分类之后，获得的信息量。

显然，构建决策树的过程就是利用特征属性不断地进行分类，通过不断地分类使类别属性的不确定性越来越小。
所以我们要做的就是不断的选择信息增益最大的特征属性。

上图描述了选择特征属性的过程：
计算当前类别属性D的信息熵，Info(D)=0.940
计算age属性分类之后D的信息熵 info age(D)。这里多提一嘴，假设通过age进行分类之后，我们得到三个分支，<=30,31…40,>40。这三个分支对应的概率分别是5/14，4/14，5/14。在每一个分支中，计算类别属性D的信息熵，然后加权平均，就得到了经过age分类后D的信息熵。
信息增益就是两者的差，对每一个属性计算他的信息增益，选取最大的一个构建分支。
之后对每个分支采用相同的方法进行分类，知道D的信息熵为0，也就是分类后所有数据的D值相同，结束分类。或者当所有属性都用完之后，还有一些分支信息熵不为0，这个时候就只能进行统计，然后选取数量较多的值作为最终值。