KNN 算法和朴素贝叶斯

# 逻辑回归

手推逻辑回归：

• Logit 函数写模型
• 极大似然求梯度
• 学习率更新参数

# KNN 算法

KNN 算法属于懒学习方法，基本上不学习，导致预测的速度比逻辑回归等算法慢。

KNN 算法三要素：

• k 值选取：交叉验证选取，过小会引起过拟合，过大则模型太简单。
• 距离的度量方式：一般为欧式距离，当然曼哈顿距离、闵式距离也可。
• 分类决策规则：一般为多数表决法。

k 值减小，模型复杂，容易过拟合，k值增大，模型简单。

蛮力算法实现 KNN 通常适用于少量样本的简单模型，否则就要借助 KD 树来求解了。

KD 树的建立：选择方差最大的特征，求其中位数对应的样本，以此为基准将剩下的样本划分为两类，以此类推，直到没有可以划分的样本。

KD 树的预测：用最邻近算法跑 k 次，就得到了 k 个最邻近样本，然后根据多数表决法得到预测值。

KNN 算法的主要优缺点这里说的比较详细。

# 朴素贝叶斯

朴素贝叶斯的核心算法就是贝叶斯公式：

$P(B|A) = \frac{P(A|B)P(B)}{P(A)}$

那么怎么应用呢？换个形式就会很明朗：

P(类别|特征) = \frac{P(特征|类别)P(类别)}{P(特征)}

其基本假设是条件独立性，即

$\begin{aligned} P(X=x|Y=c_k) = & P(X^{(1)}=x^{(1)}, \cdots, X^{(n)}=x^{(n)}|Y=c_k) \\ = & \prod_{j=1}^{n}P(X^{j}=x^{j}|Y=c_k) \end{aligned}$

这是一个较强的假设，由于这一假设，模型包含的条件概率数量从 $mxn$ 降到了 $m+n$，因此，学习与预测大为化简。

概率估计方法可以有极大似然估计或贝叶斯估计（当 lambda 为 0 时退化为极大似然估计）。