基本

• 奥卡姆剃刀原则
  若有多个假设与观察一致，则选最简单的那个
• “没有免费的午餐”定理（NoFreeLunch Theorem）
  在所有问题出现机会相同时，所有算法期望性能相同

评估方法

• 留出法
  将数据集划分为两个互斥的子集
• 交叉验证法
  现将数据集划分为k个互斥子集，从中分层采样出测试集，返回k个测试结果的均值
• 自助法
  从数据集中随机抽样部分数据（可重复）为训练集，未被抽样的部分为测试集

性能评估

• 错误率
  错误样本数量占总样本数
• 精度
  正确样本数量占总样本数
  > 查准与查全

• 查准率
  P=\\frac{TP} {TP+FP}

• 查全率
  R=\\frac{TP} {TP+FN}

  • 一般来说查全率高时查准率低 反之也成立R
• F1度量
  F1=\\frac{2PR}{P+R}或者 F1=\\frac{(1+\\beta^2)PR}{(\\beta^2*P)+R}

• ROC
  受试者工作特征（纵轴 真正例率、横轴 假正例率）

线性回归

f(x)=w^Tx+b
– w为参数列表
– x为输入数据矩阵

loss

均方误差 (w^*,b^*)=argmin_{(w,b)}\sum^m_{i=1}(f(x_i)-y_i)^2

可对上式分别对w和b求偏导并使其为0可得到线性回归的最优闭式解

对数几率回归

将线性回归的输出值转换为0\1值

logisitic function

y=\\frac{1} {a+e^{-z}}

得到逻辑回归的函数为： y=\\frac{1} {1+e^{(-w^Tx+b)}}

对数几率： ln \\frac{y}{1-y}

似然度函数 L(\\theta)= \\prod_{i=1}^m (h_\\theta(x^{(i)}))^{y^{(i)}}(1-h_\\theta(x^{(i)}))^{1-y^{(i)}}

对似然度函数做log得到其loss函数 \\mathscr{l}(\\theta)=\\sum_{i=1}^m y^{(i)}log\,h(x^{(i)})+(1-y^{(i)})log(1-h(x^{(i)}))

线性判别分析

使同类样例投影点尽可能接近，异类尽可能远离

最大化目标 J=\\frac{||w^tu_0 – w^tu_1||^2_2} {w^T\\sum_0w+w^T\\sum_1w}

决策树

• 叶节点对应决策结果，其他节点对应一个属性测试
• 学习的目的是产生一颗泛化能力强，能处理未见事例的决策树

划分选择

• 信息增益

对可取值数目较多的属性有偏好

信息熵

假定样本D中第k类样本所占比例为p_k

信息熵定义为： End(D)=-\\sum_{k=1}^{|y|} p_klog_2p_k

信息增益

Gain(D,a)=Ent(D)-\\sum_{v=1}^V {\\frac{|D_v|} {|D|} End(D^v)}

ID3 决策树以信息增益做为划分依据

• 增益率

对可取值数目较少的属性有偏好

增益率

GainRatio(D,a)=\\frac{Gain(D,a)} {IV(a)}

属性固有值

IV(a)=-\\sum^V_{v=1} \\frac{|D^v|} {|D|} log_2 \\frac{|D^v|} {|D|}

C4.5决策树 先从候选属性中找出信息增益高于平均的 再从中取增益率最高的

• 基尼指数

Gini(D)=\\sum^{|y|}_{k=1} \\sum_{k’\not= k} p_kp_{k’}=1-\\sum^{|y|}_{k=1}p^2_k

反映了从D随机抽取两个样本其类别标记不一致的概率，基尼指数越小数据纯度越高

CART决策树使用最小基尼指数的属性作为划分属性

剪枝处理

• 预剪枝

在选择分割的属性后，以该属性进行验证集验证，如果能提升验证集精度则进行划分，如果不能则作为叶节点

训练快速，分支少

• 后剪枝

先生成完整的决策树，从最后划分节点开始尝试去除该分割节点，如能提高总体准确度则将改节点改为叶节点

训练时间大，分支多泛化性能好

连续与缺失值

连续值

• 二分划分

使用 有序排列的连续属性 相邻两个值的平均值作为划分值

然后计算信息增益以确定二分点的位置

连续属性可作为后代节点的划分属性

C4.5决策树使用二分划分处理

缺失值

• 推广信息增益

Gain(D,a)=\\rho*Gain(\\underline{D}^~,a)

其中 \\underline{D} 值不缺失该属性的子集

若一个样本不存在该属性，则划分时同时归入所有类别中

C4.5决策树使用了上述方法

多变量决策树

将每一个非叶节点作为一个类似 \sum^d_{i=1} w_ia_i = t的线性分类器