【机器学习】非线性分类算法（上）：KNN（基于距离相似度）与朴素（特征独立）贝叶斯（基于概率统计）

在现实世界中，数据的分布往往错综复杂，远非一条直线或一个平面可以划分清楚。例如，判断一封邮件是否为垃圾邮件，涉及到内容、时间、发件人等多种因素的复杂组合。线性分类算法就像用直尺切蛋糕，难以应对蛋糕上复杂的花纹。这时，非线性分类算法就像灵活的雕刻刀，能顺应数据的"纹理"进行精准切割。

本文将深入解析两种经典的非线性分类算法：K近邻算法（KNN）和朴素贝叶斯算法。这两种算法代表了不同的分类思路——基于距离的"邻居投票"和基于概率的"专家判断"。

 

一、K近邻算法（KNN）：基于距离的"邻居投票"

1、核心思想：物以类聚

KNN的核心思想非常简单直观：相似的样本应该属于同一类别。就像我们判断一个人的性格时，会参考他周围朋友的特点一样，KNN通过观察新样本的"邻居"来决定它的类别。

数学公式
对于新样本 $x$，找到训练集中距离它最近的 $K$ 个邻居，然后采用多数投票决定类别：

$$\hat{y}=\arg \underset{c}{\max }\sum _{i\in N_K(x)}\mathbb{I}(y_i=c)$$

其中，

• $\hat{y}$：预测的类别标签
• $\arg {\max }_c$：选择使后面表达式最大的类别 $c$
• ${\sum }_{i\in N_K(x)}$：对 $x$ 的 $K$ 个最近邻居求和
• $\mathbb{I}(y_i=c)$：指示函数，判断邻居 $i$ 是否属于类别 $c$

 

1. 指示函数是一个简单的判断函数：
$$\mathbb{I}(y_i=c)=\{\begin{array}{ll}1& \text{如果 }{y}_i=c\\ 0& \text{如果 }{y}_i\ne c\end{array}$$

假设我们有5个邻居，它们的类别分别是：[A, B, A, A, B]

• 对于类别A：$\mathbb{I}(y_1=A)=1$, $\mathbb{I}(y_2=A)=0$, $\mathbb{I}(y_3=A)=1$, $\mathbb{I}(y_4=A)=1$, $\mathbb{I}(y_5=A)=0$
• 对于类别B：$\mathbb{I}(y_1=B)=0$, $\mathbb{I}(y_2=B)=1$, $\mathbb{I}(y_3=B)=0$, $\mathbb{I}(y_4=B)=0$, $\mathbb{I}(y_5=B)=1$

 

2. 求和部分 ${\sum }_{i\in N_K(x)}\mathbb{I}(y_i=c)$

这部分计算的是在 $K$ 个最近邻居中，属于类别 $c$ 的邻居数量。

继续上面的例子：

• 类别A的票数：${\sum }_{i=1}^5\mathbb{I}(y_i=A)=1+0+1+1+0=3$
• 类别B的票数：${\sum }_{i=1}^5\mathbb{I}(y_i=B)=0+1+0+0+1=2$

 
3. $\arg {\max }_c$ 的作用

$\arg {\max }_c$ 表示选择使后面表达式达到最大值的类别 $c$。

在例子中：

• 类别A的票数：3
• 类别B的票数：2

$\arg {\max }_c$ 会选择票数最多的类别，即类别A

 

这个公式实际上就是在说：

1. 找到新样本的 $K$ 个最近邻居
2. 统计这些邻居中每个类别有多少个
3. 选择出现次数最多的类别作为预测结果

这个公式基于一个基本假设：相似的样本应该属于同一类别。如果新样本的邻居大多属于类别A，那么新样本也很可能属于类别A。这种直觉在大多数情况下都是成立的，即少数服从多数的原则。

 

2、距离度量：欧氏距离

欧氏距离就是我们在几何学中学到的"两点之间的直线距离"。在KNN中，我们将每个样本看作特征空间中的一个点，然后计算这些点之间的距离来衡量相似性。

数学公式

$$d(x_1,x_2)=\sqrt{\sum _{j=1}^n(x_{1j}-x_{2j}{)}^2}$$

各部分含义：

• $x_1,x_2$：两个样本
• $x_{1j},x_{2j}$：第 $j$ 个特征的值

 

3、工作原理：三步决策

KNN的工作流程可以概括为三个步骤：

1. 距离计算：对于每个测试样本，计算它与所有训练样本的距离
2. 邻居选择：选择距离最近的 $K$ 个训练样本作为"邻居"
3. 投票决策：根据这 $K$ 个邻居的多数类别进行预测

 

为什么这样有效？

KNN基于"相似样本有相似标签"的假设。如果两个样本在特征空间中距离很近，那么它们很可能属于同一类别。这种直觉在大多数情况下都是成立的，特别是在数据分布相对均匀的情况下。

 
K值的选择直接影响算法的性能：

• K值过小：容易受噪声影响，模型不稳定
• K值过大：可能包含太多不同类别的样本，降低分类精度
• 经验法则：通常选择 $K=\sqrt{n}$，其中 $n$ 是训练样本数

 

4、KNN算法的优势与局限

核心优势
KNN算法具有三个主要优势：无需训练、适应性强和直观易懂。它不需要复杂的模型训练过程，直接基于距离计算进行分类，能够处理各种类型的数据，只要能够定义合适的距离度量。

适用场景
KNN最适合处理小到中等规模的数据集，因为其计算复杂度为 $O(n)$，数据量过大时计算效率会显著下降。它在特征相似性明显的数据中表现优异，比如推荐系统中的用户相似性判断，以及需要快速验证想法的场合。

主要局限
KNN面临三个关键挑战：维度灾难、特征尺度敏感性和噪声敏感性。在高维空间中，距离度量失去区分能力；不同特征的值域差异会导致距离计算被大值域特征主导；异常值会显著影响分类结果。这些局限要求在使用KNN时进行适当的数据预处理，如特征标准化和降维处理。

 

二、朴素贝叶斯：基于概率的"专家判断"

1、核心思想：贝叶斯定理的应用

朴素贝叶斯算法基于贝叶斯定理，通过计算后验概率来进行分类。其核心假设是特征之间条件独立（这就是"朴素"的含义）。

贝叶斯定理：
$$P(y|x)=\frac{P(x|y)P(y)}{P(x)}$$

这个公式告诉我们：要计算样本 $x$ 属于类别 $y$ 的概率，我们需要知道：

1. 类别 $y$ 的先验概率 $P(y)$
2. 在类别 $y$ 下观察到特征 $x$ 的条件概率 $P(x|y)$

各部分含义：

1. $P(y|x)$ - 后验概率

   • 含义：在观察到特征 $x$ 的条件下，样本属于类别 $y$ 的概率
   • 例子：已知邮件包含"免费"、"中奖"等词，这封邮件是垃圾邮件的概率

2. $P(y)$ - 先验概率

   • 含义：在没有任何信息的情况下，样本属于类别 $y$ 的概率
   • 例子：所有邮件中垃圾邮件的比例

3. $P(x|y)$ - 似然概率

   • 含义：在类别 $y$ 的条件下，观察到特征 $x$ 的概率
   • 例子：在垃圾邮件中，包含"免费"、"中奖"等词的概率

4. $P(x)$ - 证据概率

   • 含义：观察到特征 $x$ 的总概率
   • 例子：所有邮件中包含"免费"、"中奖"等词的概率

 

2、朴素假设：条件独立性

为什么朴素假设有效？

虽然特征独立性假设在现实中往往不成立，但朴素贝叶斯仍然表现良好，原因包括：

• 排序而非绝对概率：我们关心的是类别排序，而不是绝对概率值
• 误差抵消：特征之间的相关性往往被先验概率和条件概率的乘积效应所抵消
• 高维稀疏数据：在文本分类等高维稀疏数据中，独立性假设相对合理

特征独立性

朴素贝叶斯的关键在于"朴素"假设：所有特征在给定类别下是条件独立的。这意味着：

$$P(x_1,x_2,...,x_n|y)=P(x_1|y)\times P(x_2|y)\times ...\times P(x_n|y)$$

简单理解：在给定类别 $y$ 的条件下，所有特征的概率等于各个特征概率相乘。

例子：

• 在垃圾邮件中，包含"免费"的概率是80%
• 在垃圾邮件中，包含"中奖"的概率是60%
• 朴素假设认为：在垃圾邮件中，同时包含"免费"和"中奖"的概率 = 80% × 60% = 48%

虽然这个假设在现实中往往不成立，但朴素贝叶斯仍然表现良好。这是因为我们关心的是类别排序，而不是绝对概率值。

 

分类决策：最大后验概率

在朴素假设下，分类公式（计算样本属于某个类别的概率）变为：

$$P(y|x_1,x_2,...,x_n)\propto P(y)\prod _{j=1}^{n}P(x_j|y)$$

正比于解释：

• 垃圾邮件概率：$\frac{0.3\times 0.8\times 0.6}{P(x)}=\frac{0.144}{P(x)}$
• 正常邮件概率：$\frac{0.7\times 0.1\times 0.05}{P(x)}=\frac{0.0035}{P(x)}$

比较大小：

• $\frac{0.144}{P(x)}>\frac{0.0035}{P(x)}$
• 等价于：$0.144>0.0035$

所以我们可以直接比较分子，省略分母。

 

例子：

判断邮件是否为垃圾邮件

• 基础概率：垃圾邮件30%，正常邮件70%
• 特征概率：包含"免费"在垃圾邮件中80%，在正常邮件中10%
• 特征概率：包含"中奖"在垃圾邮件中60%，在正常邮件中5%

计算：

• 垃圾邮件概率：30% × 80% × 60% = 14.4%
• 正常邮件概率：70% × 10% × 5% = 0.35%

 

我们选择后验概率最大的类别(选择概率最大的类别)作为预测结果：

$$\hat{y}=\arg \underset{y}{\max }P(y)\prod _{j=1}^{n}P(x_j|y)$$

例子：

• 垃圾邮件概率：14.4%
• 正常邮件概率：0.35%
• $\arg \max$ 选择：垃圾邮件（因为14.4% > 0.35%）

 

概率估计：不同类型特征的处理

连续特征（高斯朴素贝叶斯）：
对于连续特征，我们假设它们服从正态分布：如下是正态分布的概率密度函数，用来计算连续特征的概率。

$$P(x_j|y)=\frac{1}{\sqrt{2\pi {\sigma }^2}}\exp \left(-\frac{(x_j-\mu {)}^2}{2{\sigma }^2}\right)$$

其中，$\mu$ 和 ${\sigma }^2$ 分别是类别 $y$ 下特征 $j$ 的均值和方差。

各部分含义：

• $\mu$：平均值
• ${\sigma }^2$：方差
• $x_j$：特征值
• $\exp ()$：自然指数函数 $e^x$

 

为什么用这个公式？

• 对于连续特征（如年龄、收入），我们不能像离散特征那样直接算频率
• 我们假设连续特征服从正态分布
• 用正态分布公式计算概率

 

离散特征（多项式朴素贝叶斯）：
对于离散特征，我们使用频率估计：

$$P(x_j|y)=\frac{count(x_j,y)+\alpha }{count(y)+\alpha |V|}$$

其中，$\alpha$ 是平滑参数，$|V|$ 是特征 $j$ 的可能取值数量。

 

3、工作原理：四步概率推理

朴素贝叶斯的工作流程包括四个步骤：

1. 先验概率计算：根据训练数据计算每个类别的先验概率 $P(y)$
2. 条件概率估计：估计在给定类别下每个特征的条件概率 $P(x_j|y)$
3. 后验概率计算：使用贝叶斯定理计算新样本属于每个类别的后验概率
4. 分类决策：选择后验概率最大的类别作为预测结果

 

4、优势与适用场景

核心优势
朴素贝叶斯算法具有训练快速、输出概率、处理缺失值和支持增量学习四大优势。其时间复杂度仅为 $O(n\times d)$，能够高效处理大规模数据，同时提供概率输出而非简单的类别预测，这使得它在需要不确定性评估的场景中表现突出。

适用场景
该算法特别适合文本分类、医疗诊断、推荐系统和高维稀疏数据处理。在这些场景中，特征数量往往远大于样本数量，朴素贝叶斯的独立性假设相对合理，能够有效捕捉特征与类别之间的关系。

主要局限
朴素贝叶斯面临三个关键挑战：特征强相关会违反独立性假设，连续特征较多时高斯假设可能不成立，以及需要复杂特征交互的场合。这些局限要求在使用时仔细考虑数据特征，必要时进行特征工程或选择其他更适合的算法。
 

三、算法对比与选择指导

特性	KNN	朴素贝叶斯
核心思想	距离度量+投票	贝叶斯定理+条件独立
训练时间	无需训练	$O(n\times d)$
预测时间	$O(n)$	$O(d)$
内存需求	存储所有训练数据	存储概率参数
可解释性	中等	高
处理缺失值	困难	天然支持
特征尺度敏感性	高	低

选择指导：

• 选择KNN的情况：

  • 数据规模较小（<1000样本）
  • 特征相似性明显
  • 需要快速原型验证
  • 对模型可解释性要求不高

• 选择朴素贝叶斯的情况：

  • 文本分类等高维稀疏数据
  • 需要概率输出
  • 计算资源有限
  • 数据包含缺失值