分类问题是监督学习的一个核心问题，它从数据中学习一个分类决策函数或分类模型（分类器（classifier））,对新的输入进行输出预测，输出变量取有限个离散值。

分类在我们日常生活中很常见

核心算法

决策树、贝叶斯、SVM、逻辑回归

决策树

决策树（decision tree）是一个树结构，每个非叶节点表示一个特征属性，每个分支边代表这个特征属性在某个值域上的输出，每个叶节点存放一个类别。

决策过程：从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类边作为决策结果。

决策树特征选择

特征选择就是要选出对训练数据集具有分类能力的特征，提高决策树的学习效率。
有几个需要掌握的概念
信息熵：表示随机变量的不确定性，熵越大不确定性越大。（每一次特征选择，都希望熵变小）

信息增益：信息增益=信息熵（前）-信息熵（后）

信息增益比：信息增益比=惩罚参数*信息增益。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。

基尼系数：表示集合的不确定性，基尼系数越大，表示不平等程度越高。
算法|支持模型|树结构|特征选择
--|--|--|--
ID3|分类|多叉树|信息增益
C4.5|分类|多叉树|信息增益比
CART|分类、回归|二叉树|基尼系数、均方差

决策树剪枝

尽可能让叶子节点数最少、叶子节点深度最小、叶子节点数最少且叶子节点深度最小。

预剪枝

开始先设置一个条件，一旦停止，节点就是叶子，该条件可以是定义一个高度、实例个数、系统性能增益等。

后剪枝

先构造完整的决策树，然后对那些置信度不够的结点子树用叶子节点来代替。相比于预剪枝，这种方法更常用，因为估计何时停止生长很困难。

贝叶斯分类

贝叶斯分类是基于贝叶斯定理和属性特征条件独立性的分类方法。（常识的数学化）

概率论只不过是把常识用数学公式表达了出来。 ——————拉普拉斯

案例：假设春季感冒流行，你同桌打了一个喷嚏，那你同桌感冒的概率是多少？

1.计算先验概率：你同桌没有任何症状的情况下可能得感冒的概率是多少？
2.为每个属性计算条件概率：如果你同学感冒了，那么他打喷嚏的概率是多少，如果他没感冒，出现打喷嚏的概率有多少
3.计算后验概率：根据1,2求解最终问题

为了式子中的每个概率尽可能不为0，有拉普拉斯修正：

优点：
（1）算法逻辑简单，易于实现
（2）分类过程中时空开销小
缺点：
理论上，朴素贝叶斯模型与其他分类方法相比具有最小的误差率，但是实际上并非总是如此，这是因为朴素贝叶斯模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，在属性个数比较多或属性之间相关性较大时，分类效果不好。

SVM分类

支持向量机（Support Vector Machine,SVM）是一种有监督学习方法，主要思想是建立一个最优决策超平面，使得该平面两侧距离该平面最近的两类样本之间的距离最大化，从而对分类问题提供良好的泛化能力。

简单来说，硬间隔就是所有样本点都是分类正确的、软间隔线性可分是存在一些样本点站错地方，但是通过引入惩罚系数，允许存在错误、而核函数非线性SVM将二维中不可二分的数据映射到三维中，用超平面分开。

逻辑回归

logistic回归是一个分类算法，它可以处理二元分类及多元分类。首先逻辑回归构造广义的线性回归函数，然后使用sigmoid函数g(z)将回归值映射到离散类别。

以下为sigmoid函数

蓝色的点归类到1，红色的归类到0

逻辑回归与最大熵模型

熵是随机变量不确定性的度量，不确定性越大，熵值就越大。

万事万物朝着熵愈来愈大的方向发展。
比如耳机整理好放入口袋中，下次拿出来已经乱了，让耳机线乱掉的看不见的“力”就是熵力，耳机线喜欢变成更混乱。墨水滴入水中，熵增大，墨水扩散。
熵首次提出是指任何一种能量在空间中分布的均匀程度，能量分布得越均匀，熵就越大。

数学上的最大熵模型，保留全部的不确定性，将风险降到最小。
最大熵原理指出，对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设。（概率分布最均匀，预测的风险最小，不要把鸡蛋放在一个篮子里）

逻辑回归是最大熵的特殊情况。（对数线性模型）

集成学习

集成学习通过将多个弱分类器集成在一起，使它们共同完成学习任务，构建一个强分类器。
抽象地说，就是一堆考60分的学生，按指定的方法，可以达到90分的程度。

集成学习方法

每次从数据集中采一些数据，对此用个分类器，然后把数据放回，再采数据，再用个分类器……

一次次改变分类错误样本的权重，以此集中对分错的样本进行判断。

集成学习严格意义上说，不算一种机器学习的算法，而更像一种优化手段或者策略，通常是结合多个简单的弱机器学习算法，去做更可靠的决策，类似于开会做决策。