一、基本概念

SVM 寻找一个最大边缘超平面（maximal margin hyperplane），使得将数据分开，并且有最大的margin，泛化能力。

（1）结构风险最小化（structual risk minimization，SRM）

线性分类器的边缘与泛化误差之间的关系，分类器的泛化误差在最坏的情况下：
$$R\leqslant R_{e}+\varphi \left(\frac{h}{N},\frac{log(\eta )}{N}\right)$$
$\varphi$是h的单调增函数，$1-\eta$表示概率。

一、感知器

下图为一个感知器，单个神经元。

该感知器的算法：

一、k-最近邻

1、算法

积极学习方法（eager learner）：通过训练样本建立模型。
消极学习方法（lazy learner）：实例的学习，k-最近邻就属于这种。

k-最近邻算法：

1
2
3
4
5

令k是最近邻数目，D是训练样例集合
for z in 样例集合:
  计算 z 和每个样例 (x,y) 的距离 d
  选择离 z 前 k 个近距离的点，为集合 Dt
  z的标记 y 为 Dt 中类较多的

一、如何建立决策树

1、Hunt算法

Hunt算法是许多决策树算法的基础，包括ID3、C4.5、CART。
Hunt算法步骤：

（1）如果Dt中所有数据都属于同一个类yt，则t是叶结点，用yt标记。
（2）如果Dt中包含属于多个类的数据，则选择一个属性，将数据划分为较小子集。创建子女结点，将数据按属性放入子女结点中，然后递归调用该算法。

但是该算法对于大多数情况太苛刻了，需要附加：

（1）没有可以选择的属性，则该结点为叶结点，类标号为父结点上较多数的类。
（2）如果与Dt相关的数据均为同一个属性，则不可以继续划分，类标号为多数类。

一、数据知识

如果若干属性是强相关的，则说明这些属性可能提供了高度冗余的信息，我们可以决定只保留一个。

二、数据预处理

1、维规约：

通过创建新属性，将一些旧属性合并在一起来降低数据的维度。通过选择旧属性的子集得到的新属性，这种维规约称为特征子集选择。