k 近邻分类法：
非线性地分类方法
1，怎么选择距离 2，在样本量大地时候计算量很大，3， k的选择（应该用交叉验证）
对每个测试样本，时间是O(n),如果有m个测试样本的话，就是O（mn）太大了。采用kd树来作为存储的数据结构加快搜索。
如图，每一次做二分的标准是，两边差不多一样多。然后终止的标准是，叶节点里个数小于等于阈值。这样的话来一个新的测试样本可以很快确定在哪个叶节点。
缺点：训练集非常大的时候，泛化误差是bayes error rate的两倍。
训练集小的时候过拟合。
优点：对于异常值不敏感，鲁棒
=====
决策树分类法：
决策树的终止条件：某个节点中只属于某个类别（分类）或者方差很小（回归）
决策树每步决策两个要考虑的：1.到底选择哪个特征去分裂 2.这个特征下到底用什么标准去分裂
一般也不想要特别深的决策树，矮一点更好。
不纯度：每个阶段可以计算不纯度：越高的话代表越不纯，也就是这个节点里面类别很多。如果只有一个类别，不纯度就会最低。所以分裂要朝着不纯度下降很快的放下走着。
决策树还需要剪枝，如果分太细会过拟合。
预剪枝：设定一个阈值下限。
后剪枝：弄完决策树之后再减。
需要平衡纯度（拟合度）和树的大小（复杂度）。
优点：可解释性好！
缺点：模型不稳定，方差大。改变训练集会导致性能变化。（集成方法解决）
容易陷入局部最优解（贪心算法）
决策边界是垂直坐标轴的，准确性会比较差。
三种度量不纯度的方法：
Gini p是频率。当每个类别频率一样的时候是(1-1/C) 当只有一个类别的时候是0.
信息熵 如果均匀分布 最大，是log 2 C ，如果只有一个类，是0 最小。
信息增益是：
但是实际上，我们仅仅用这个信息增益会容易把叶节点分出很多来，就导致过拟合。
所以 （信息增益率）是一个更好的选择，避免分的太细了。
错误分类率：
名字含义：如果按照当前组内最多数来确定类别，错误分类的概率。
只有两类的时候三种指标的示意图。可以看到用信息熵的话，对不良分类的惩罚是最大的。所以会倾向于分到很细很细的情况。
=====
机器学习framework/神经网络
我们的假设集不能太大也不能太小，overfit/不能拟合
如果 其中
hn是算法返回的函数，这样就是PAC可以学习的。
能否把泛化误差表示成训练误差和假设集复杂度的函数？
固定一个假设函数h，那么以1-delta的概率有
如果想要对某个有限的假设集里的h都成立，也就是以1-delta的概率有
可见，n越大，那么经验误差和泛化误差就会很接近
神经网络缺陷：
不能训练未标注的数据,但现实中大多数数据都是未标注的。
修正信号在通过多个隐藏层传输时被减弱
当包含的隐藏层过多时,学习速度太慢
会陷于局部最优解
=====
SVM方法：
间隔最大化的方法是最好的方法：
SVM ：使得训练点到分割超平面的最小距离最大
=====
朴素贝叶斯方法：
假设了特征条件独立
