线性模型
线性模型试图学得一个通过属性的线性组合来进行预测的函数
$$
f(x)=w_1x_1+w_2x_2+…+w_dx_d+b
$$
向量形式：
$$
f(x)=w^Tx+b
$$
单线性回归
$$
f(x_i)=wx_i+b 使得 f(x_i)\backsim y_i
$$
离散属性的处理：若有“序”（order），则连续化；否则，转化为k维向量
均方误差最小化：
$$
(w^*,b^*)=argmin\sum_{i=1}^{m}(f(x_i)-y_i)^2=argmin\sum_{i=1}^{m}(y_i-wx_i-b)^2
$$
- 应用：最小二乘法：找到一条直线，使得所有样本到直线上的欧式距离之和最小
分别对w、b求导可得
$$
\frac{\partial E(w,b)}{\partial w}=2(w\sum_{i=1}^{m}x_i^2-\sum_{i=1}^{m}(y_i-b)x_i)
$$
$$
\frac{\partial E(w,b)}{\partial b}=2(mb-\sum_{i=1}^{m}(y_i-w_ix_i))
$$
令导数值为0得到w、b表达式
多元线性回归
$$
f(x_i)=w^Tx_i+b,使得f(x_i)\backsim y_i
$$
将w和b吸收入向量中：
$$
\hat{w}=(w;b)
$$
$$
X = \left[
\begin{matrix}
x_{11} & x_{12} & \cdots & x_{1d} & 1 \
x_{21} & x_{22} & \cdots & x_{2d} & 1 \
\vdots & \vdots & \ddots & \vdots & \vdots \
x_{m1} & x_{m2} & \cdots & x_{md} & 1 \
\end{matrix}
\right] = \left[
\begin{matrix}
x_1^T & 1 \
x_2^T & 1 \
\vdots & \vdots \
x_m^T & 1 \
\end{matrix}
\right]
$$
$$
(w^*,b^*)=\hat{w}^*=argmin(y-X\hat{w})^T(y-X\hat{w})
$$
$$
\frac{\partial E_{\hat{w}}}{\partial \hat{w}} = 2X^T(X\hat{w}-y)
$$
$$
\hat{w}^* = (X^TX)^{-1}X^Ty
$$
$$
f(\hat{x}_i) = X\hat{w} = \hat{x}_i(X^TX)^{-1}X^Ty
$$
广义线性模型
$$
y = g^{-1}(w^Tx+b) 其中g(·)是联系函数
$$
对数几率回归
二分类问题
- TP 将正类预测为正类
- FN 将正类预测为负类
- FP 将负类预测为正类
- TN 将负类预测为负类
- 精确率
$$
P = \frac{TP}{TP+FP}
$$
- 召回率
$$
R = \frac{TP}{TP+FN}
$$
- 调和均值
$$
\frac{2}{F_1}=\frac{1}{P}+\frac{1}{R}
$$
- 输出标记 y∈{0,1}
- 预测值 z
$$
y =\frac{1}{1+e^{-z}}=\frac{1}{1+e^{-(w^Tx+b)}}
$$
$$
ln\frac{y}{1-y} = w^Tx+b ,其中\frac{y}{1-y}称为几率(odds)
$$
- 类别不平衡问题
- 正类和负类个数并不相同，差距较大
$$
原先 \frac{y}{1-y}>1,则预测为正例。判断条件改进为\frac{y}{1-y}>\frac{m^+}{m^-}
$$
决策树
信息增益
“信息熵”是度量样本集合纯度的指标，针对数据集D的信息熵为：
$$
Ent(D) = -\sum_{k=1}^{|y|}p_klog_2p_k
$$
Ent(D)越小，D纯度越高
针对属性a对样本集D进行划分所获得的“信息增益”
$$
Gain(D,a)=Ent(D)-\sum_{v=1}^{V} \frac{|D^v|}{|D|}Ent(D^v)
$$
信息增益大的用来划分属性，但是有些属性划分不具有泛化能力（如：序号）
增益率
$$
Gain-ration(D,a)=\frac{Gain(D,a)}{IV(a)}
$$
$$
IV(a) = -\sum_{v=1}^{V}\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}
$$
先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的
基尼指数
数据集D的纯度用来度量：
$$
Gini(D)=\sum_{k=1}^{|y|}\sum_{k’≠k}p_kp_{k’}=1-\sum_{k=1}^{|y|}p_k^2
$$
剪枝处理(pruning)
解决“过拟合”现象
预剪枝
- 提前不让树枝长出来
- 最大深度限制：设定决策树的最大深度，当达到设定的最大深度时停止分支。
- 叶子节点样本数限制：设置一个阈值，当某个节点上的样本数量小于该阈值时，停止分支，将该节点作为叶子节点。
- 不纯度减小阈值：计算每个节点的不纯度（如基尼指数、熵），设定一个阈值，当分支后不纯度的减小量低于该阈值时，停止分支。
- 类别纯度阈值：判断节点上的样本是否属于同一类别，当节点的类别纯度达到设定阈值时，停止分支。
- 特征重要性评估：在决策树构建过程中，实时评估每个特征的重要性，当某个特征的重要性低于一定阈值时，停止分支。
后剪枝
- 构建完整的决策树：使用训练数据构建完整的决策树，直到每个叶子节点都包含纯净的类别或达到预定的停止条件。
- 评估子树的准确性：对于每个非叶子节点，考虑其子树的整体准确性，可以使用交叉验证、验证集或其他评估方法来评估子树的性能。
- 执行剪枝操作：从决策树的底部开始逐步剪枝，将子树替换为叶子节点，并将叶子节点的类别设置为该子树中最常见的类别。然后，通过比较剪枝前后的整体准确性来确定是否剪枝。
- 重复剪枝操作：循环执行步骤3，逐步剪枝决策树的其他子树，直到不能再获得更好的性能为止。
连续与缺失值
神经网络
感知机
- 二分类的线性模型
- 梯度下降
一个超平面S能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧
- 损失函数
- 输入空间R中任一点x到超平面S的距离
$$
d = \frac{1}{||w||}|w·x_0+b|
$$
$$
范式||w|| = \sqrt{w_1^2+w_2^2+…+w_n^2}
$$
- 误分类
$$
-y_i(w·x_i+b)> 0
$$
- 感知机学习损失函数
$$
L(w,b)=-\sum_{x_i∈M}y_i(w·x_i+b)
$$
感知机学习的策略是在假设空间中选取损失函数式最小的模型参数w，b
- 迭代求最好的w、b值
- η（0 < η ≤ 1）是学习步长，又称学习率
$$
\frac{\partial L}{\partial w}=-\sum_{i=1;x∈M}^{n}y_ix_i
$$
$$
\frac{\partial L}{\partial b}=-\sum_{i=1;x∈M}^{n}y_i
$$
$$
w = w + \eta \frac{\partial L}{\partial w}
$$
$$
b = b + \eta \frac{\partial L}{\partial b}
$$
- 感知机算法过程
- 选取初值w、b
- 在训练集中选取数据（x，y）
- 如果y(wx+b) ≤ 0,
- 改变w、b的值
- 重复至第二步，直至训练集中没有误分类点
证明上述结论：
$$
\hat{w}k·\hat{w}{opt} ≥ k \eta \gamma
$$
$$
||w_k||^2 ≤ k \eta^2 \gamma^2
$$
- 对偶形式
$$
w = \sum_{i=1}^{N} \alpha_iy_ix_i
$$
$$
b = \sum_{i=1}^{N}\alpha_iy_i
$$
这里的α就是误分类点出现的次数
- Gram矩阵
$$
G = [x_i,x_j]_{N×N}
$$
K近邻
给定一个数据集，对于新输入的实例，在训练数据集中找到与该实例最接近的k个实例，这k个实例的多数属于哪个类，就把它划分到哪个类
三个参数
- 距离度量
- 欧式距离
- 由于不同的距离度量所确定的最近邻点是不同的
- 欧式距离
- k值的选择
- 太小过拟合
- 太大无异议
- 分类决策规则
- 多数表决规则 = 经验风险最小化
kd树
- kd树的查找
kd树构建完毕后，利用kd树进行k近邻搜索。在kd树上进行近邻搜索时，很多时候可以不进入某个父节点的另一个子节点（省去了另一个子节点数据点的查找）。kd树查找的具体算法如下：
算法输入：构造完毕的kd树，需要分类的目标点x
算法输出：目标点x的k近邻点
算法过程：
（1）通过深度优先方法，在kd树中搜索到目标点的所在的叶节点。（注：该搜索并不能直接找到最近邻点）搜索方法如下，在搜索每一层的过程中，根据该层的分割特征的序数，来对目标点的该序数的特征进行分类（决定是进入左子节点还是右子节点）。
（2）以该叶节点作为当前的NN（最近邻）点，计算该叶节点与目标点的距离，并设为当前的最小距离。
（3）计算该叶节点父节点与目标点的距离，若小于当前的最小距离，则更新当前的最小距离以及当前的NN点（被覆盖的点先记录下来）
（4） 判断是否要进入父节点的另一个子节点： 判断方法为：计算父节点在其分割特征上的值距离目标点在该特征上的值的距离，若该距离小于当前的最小距离，则进入另一个子节点，否则不进入。既：检查另一子节点对应的区域是否与以目标点为球心，以目标点与当前的NN点的距离为半径的球体相交。若相交则进入，反正不进入。
a）若不进入另一个子节点，则以此父节点视为叶节点，重复步骤3。
b）若进入另一个子节点，则对右边节点以下的子树执行步骤1，找到新的叶节点。判断是否要更新NN点与当前最小距离。随后以该叶节点开始，重复步骤3。
以此类推，搜索过程中将不断向跟节点回退。在向根节点回退的过程中，不必再次进入从中退出的子节点，保证过程不会进入死循环。
5 当回退到根节点时（且以根节点与目标点的距离来更新最小距离与NN点后），最后的NN点即为x的最近邻点。且记录下来的所有NN点，对应的距离，最小的K个即为K近邻点。
如果实例点是随机分布的，则kd树搜索的平均及计算复杂度是O（logN）
贝叶斯分类器
对给定的输入x，通过学习到的模型计算后验概率分布P，将后验概率最大的类作为x的类输出。——生成学习的方法
$$
P(Y=c_k|X=x)=\frac{P(X=x|Y=c_k)P(Y=c_k)}{\sum_{k}P(X=x|Y=c_k)P(Y=c_k)}
$$
朴素贝叶斯分类器
$$
y = f(x)= argmax\frac{P(Y=c_k)\quad\prod_jP(X^{(j)}=x^{(j)}|Y=c_k)}{\sum_{k}P(X=x|Y=c_k)\quad\prod_jP(X^{(j)}=x^{(j)}|Y=c_k)}
$$
因为分母对所以C_k都是相同的，所以：
$$
y = P(Y=c_k)\quad\prod_jP(X^{(j)}=x^{(j)}|Y=c_k)
$$
根据算数得出期望风险最小化准则就得到了后验概率最大化准则：
$$
f(x) = argmaxP(C_k|X=x)
$$
逻辑斯蒂回归与最大熵模型
逻辑斯蒂回归
逻辑斯蒂分布中的分布函数和密度函数：
$$
F(x) = P(X≤x)=\frac{1}{1+e^{-(x-u)/r}}
$$
$$
f(x)=F^{‘}(x)=\frac{e^{-(x-u)/r}}{r(1+e^{-(x-u)/r})^2}
$$
F(x)关于点（u，½）中心对称
$$
F(-x+u)-1/2=-F(x-u)+1/2
$$
最大熵模型
在已有条件约束下，在模型集合中选择熵最大的模型（即最优化的模型）
熵：
$$
H(P) = -\sum_{x}P(x)logP(x)
$$
$$
0 ≤ H(P) ≤log|X| (|X|是X的取值个数)
$$
最大熵模型：
$$
H(P) = - um
$$
