分类定义
分类任务就是通过学习得到一个目标函数(target function)\(f\),把每个属性集\(x\)映射到一个预先定义的类标号\(y\)。 分类和回归的区别之处就是类标号是否是离散的。回归的目标属性\(y\)是连续的。 分类的一般方法有决策树，基于规则的分类，神经网络，支持向量机和朴素贝叶斯算法。
决策树
决策树是一种简单的分类方法，由结点和有向边组成，树中包含非终结结点和终结点（叶结点）。非终结点包含属性测试条件，用以分开不同属性的记录，而每个终结点都被赋予了一个类标号。在构造了决策树之后，从树的根结点开始，将测试条件用于校验记录，根据测试结果选择适当的分支，最后到达叶结点，叶结点的类称号就被赋给该检验记录。(见图1）。 
决策树的优点：
- 可解释性强，比较适合处理有缺失属性值的样本，能够处理不相关的特征
- 非参数的分类模型。不要求任何先验假设，不假定类和其他属性服从一定的概率分布
- 计算量简单，构建和构建之后的位置样本分类都很快
决策树的缺点：
- 容易过拟合,匹配的选项可能太多，需要剪枝
如何确定划分好坏
在构造决策树时，我们需要解决的一个问题就是，当前数据集上哪个特征在分类的时候能够起到决定作用。为了划分出最好的结果，我们必须评估每个特征，从而对属性分支。在确立分支之后，我们再对各自的分支递归地重新划分，直到每个分支下的数据都属于同一个类型为止。（当然这个要求比较苛刻，有可能所有的特征还不能将数据分开）
那么如何度量划分的好坏呢？划分的度量通常是用划分后子女结点的不纯性的程度。不纯的程度越低，类分布就越倾斜。设\(p(i)\)表示父节点\(t\)划分之后属于类\(i\)的记录占总数的比例。在二类问题中,类分布为(0,1) 的结点不纯性最低，而(0.5,0.5)的不纯性最高。不纯性的度量包括 \[\begin{split}Entropy(t) = & -\sum^{c}_{i=1} p(i)\log_2 p(i) \\ Gini(t) = & 1-\sum^{c}_{i=1} [p(i)]^2 \\Classification(t) = & 1-max_i [p(i)] \\\end{split}\]
为了确定测试条件的效果，我们需要比较父节点的不纯程度和子女结点的不纯程度之差，他们的差越大，测试条件的效果就越好。 \[\Delta=I(parent)-\sum_j^k \frac{N(v_j)}{N}I(v_j)\] 其中\(N(v_j)\)是划分到该子节点的记录数目,\(N\)是父亲节点的记录数目，\(I(.)\)是节点的不纯性度量,\(k\)是划分类的数目。因为\(I(parent)\)是个固定值，所以最大化增益等价于最小化子女节点的不纯度的加权平均（说白了就是希望每个子女节点下面的数据尽可能的属于同一个类）。
特别地，当使用熵来表示不纯性的度量时，我们知道熵等于信息量的期望值。熵是用于刻画系统或者变量不确定性的一个量，熵越高，则能把问题搞清楚就需要越多的信息，不确定性越大，熵越低，则意味着所需的信息越少。对一个特征而言，系统有它和没它时信息量将发生变化，而前后信息量的差值就是这个特征给系统带来的信息量，被称为信息增益\(\Delta_{info}\)。当特征使得所有的记录都属于一个类时，这个特征使得新系统所需要的信息量为0，也就是给出了一个确定的结果，所以这个时候信息增益是最大的。
ID3算法
使用信息增益来确定特征划分的好坏，这就是ID3算法了。但是它存在一个问题，见下图： 
可以看到，c中顾客的ID提供了最大的信息增益，产生了非常纯的划分，但是它确是个无效的属性，因为每个样本在该属性上的值都是唯一的，这样训练出来的分类器没有任何预测性。由于每个划分相关联的记录太少，我们无法做出可靠的预测。
C4.5算法
为了限制这种大量不同值的属性，算法C4.5提出了增益率的概念来改进这个缺点： \[\text{Gain ratio}=\frac{\Delta_{info}}{\text{Split Info}}\] 其中，划分信息\(\text{Split Info}=-\sum^k_{i=1}P(v_i)\log_2 P(v_i)\)，而\(k\)是划分总数。这样如果每个属性都有相同的记录数目，划分信息会等于\(\log_2 k\)达到最大值，从而降低了增益率。
如何建立决策树
既然我们有了特征划分好坏的标准，那么接下来自然是根据这个标准选择最好的特征对决策树进行分支了，这个过程是递归的，伪代码如下：
|
|
最近邻分类器
决策树是属于积极学习方法的例子，如果训练数据可用，它就开始学习从输入属性到类标号的映射模型。而最近邻分类是属于另一种消极学习方法，推迟对训练数据的建模，直到需要分类测试样例时才进行。最近邻分类器把每个样例看做\(d\)维空间上的一个数据点。给定一个测试样例，我们计算该样例与其他数据点的邻近度，然后根据最近的\(k\)个邻近点的类标号，将该数据分派到最近邻的多数类中（见图2）。 
具体公式如下： \[ y'=\arg_v \sum_{(x_i,y_i)\in D_z} I(v=y_i)\] 其中,\(v\)是类标号，\(y_i\)是一个最近邻的类标号，\(I(.)\)是指示函数，参数为真时返回1，反之返回0。 最近邻的特点
属于基于实例的学习，使用具体的实例学习，而不是源自数据的抽象（或模型）。
基于局部信息预测，对噪声较敏感。
可以生成任意形状的决策边界，比较灵活。
贝叶斯分类器
在很多应用中，属性集和类变量的关系是不确定的。即尽管测试记录的属性和训练样例一摸一样，它的类标号也可能不同。这种情况的原因可能是噪声，或者没有考虑到某些影响分类的因素。贝叶斯分类器是一种对属性集和类变量的概率关系建模的方法，它把类的先验知识和从数据中收集的新证据相结合的统计原理。 设X表示属性性，Y表示类变量。如果类变量和属性之间的关系不确定，那么我们把X和Y看做随机变量，用概率\(P(Y|X)\)来捕捉两者之间的关系。这个条件概率又称为\(Y\)的后验概率(posterior probability)。准确估计类标号和属性值的后验概率非常困难，所以利用贝叶斯定理 \[ P(Y|X)=\frac{P(X|Y)P(Y)}{P(X)}\] 其中，\(P(Y)\)被称作先验概率(prior probability),即预先了解的Y的知识，\(P(X|Y)\)被称为类似然。 朴素的贝叶斯分类器 假设属性之间相互条件独立，那么每个类Y的后验概率可以写为: \[ P(Y|X)=\frac{P(Y)\prod^d_{i=1} P(X_i|Y)}{P(X)}\] 特点： 1.对孤立的噪声点健壮。从数据中估计条件概率时，这些点被平均。 2.对无关属性健壮。如果\(X_i\)是无关属性，那么\(P(X_i|Y)\)的分布几乎是均匀的。 3.相关属性可能会降低朴素贝叶斯的性能。
支持向量机
支持向量机（SVM）是一种基于统计学理论的分类计数，它可以很好地用于高维数据，避免了维度灾难问题。 首先介绍最大边缘超平面。图X中包含了属于两个不同类的样本，分别用方块和圆圈表示。这个数据集是线性可分的，即可以找到这样一个超平面，是的所有的方块都处于这个超平面的一侧，而所有的圆圈都在另一侧。如图所示，可能存在无穷多个可以满足条件的超平面，而我们要找到这些超平面中边缘最大（最大间距）的一个。（见图3）
在线性可分条件下，SVM的学习任务可以被形式化地描述为以下被约束的优化问题： \[ \begin{split}& \min_w \frac{||w||^2}{2} \\& y_i(\mathbf{w\cdot x_i+b})\geq 1,i=1,2,\cdots,N\end{split}\] 因为边缘\(d=\frac{2}{||w||}\)，所以求\(||w||\)的最小值就是求\(d\)的最大值。再利用拉格朗日乘子求解该凸优化问题。 在非线性条件下，SVM希望寻找一个非线性变换\(\Phi\),将数据从原先的特征空间映射到一个高维的新空间，使得决策边界在这个空间下成为线性的。但是存在一些实现问题，一是不清楚什么类型的映射函数，才能在变换后的空间构建线性决策边界。二是，即使知道合适的映射函数，在高位特征空间中解约束优化问题仍然计算代价很高。 因为在求解中我们只需要计算变换后空间中向量对之间的点积\(\Phi(x_i)\cdot\Phi(x_j)\),所以SVM寻找到一些特殊的函数——核函数，它在变换后空间中的点积可以用原空间中的相似度函数表示，比如： \[ K(u,v)=\Phi(u) \cdot \Phi(v)=(\mathbf{u\cdot v}+1)^2 \] 这样就使得计算可以在原空间中进行，减少计算开销。
SVM的特点
- 学习问题可以表示为凸优化问题，可以利用已知的有效算法发现目标函数的全局最小值。
- SVM在解决小样本、非线性及高维模式识别中表现出许多特有的优势。
基于规则的分类，人工神经网络分类等更多未涉及内容请见《数据挖掘导论》。
参考文献
- 《数据挖掘导论》,人民邮电出版社。
- 《机器学习实战》,人民邮电出版社。