本文整理了最近学习（来自NJUSE的数据仓库课程）的一些常见聚类方法，包括K-Means、凝聚层次、DBSCAN方法，以及概率统计中的朴素贝叶斯方法（贝叶斯公式的拓展）和拉普拉斯修正。

K-Means

K - Means算法是一种划分式聚类算法，目标是将数据集划分为 K 个不同的聚类。它的基本思想是通过不断地迭代，使得同一聚类中的数据点尽可能相似（距离较近），不同聚类中的数据点尽可能不同（距离较远）。

举例说明：

  • 假设我们有一群学生，他们的考试成绩包括语文、数学和英语三门科目，我们想根据成绩把学生分成 3 个小组（这里的 K = 3）。

  • 第一步：选择初始聚类中心

    • 随机挑选 3 名学生的成绩作为初始的聚类中心。比如学生 A（语文 80，数学 70，英语 75）、学生 B（语文 60，数学 80，英语 65）、学生 C（语文 90，数学 90，英语 80）。这三个点就代表了三个初始的聚类中心。

  • 第二步：分配数据点到聚类

    • 计算其他每个学生的成绩与这三个聚类中心的距离。距离的计算可以使用欧几里得距离公式，比如对于学生 D（语文 70，数学 75，英语 70），与学生 A 的距离是：
      $$
      d_{AD}=\sqrt{(70 - 80)^2+(75 - 70)^2+(70 - 75)^2}=\sqrt{100 + 25+ 25}=\sqrt{150}
      $$

    • 同样地，计算与学生 B 和学生 C 的距离。假设经过计算，学生 D 离学生 A 的距离最近，那么就把学生 D 分配到以学生 A 为中心的聚类中。

    • 对所有学生都进行这样的操作，这样所有学生就被分配到了三个聚类中的一个。

  • 第三步：更新聚类中心

    • 对于每个聚类，重新计算聚类中心。比如在以学生 A 为中心的聚类中，把所有分配到这个聚类中的学生成绩相加，然后除以这个聚类中的学生数量，得到新的聚类中心。
    • 假设在这个聚类中有 5 个学生，他们的语文成绩总和是 380，数学成绩总和是 360，英语成绩总和是 370。那么新的聚类中心（语文成绩）就是 $380\div5=76$，数学成绩是$ 360\div5 = 72$，英语成绩是$370\div5 = 74$。

  • 第四步：重复第二步和第三步，直到收敛

    • 不断重复分配数据点和更新聚类中心的步骤，直到聚类中心不再发生明显变化（收敛）。例如，经过多次迭代后，发现聚类中心的位置变化很小，比如每次更新后，语文、数学和英语成绩的变化都在一个很小的范围内（比如小于 0.1），此时就认为算法收敛，聚类完成。

在实际应用中，K - 均值算法可以用于客户细分。例如，一家电商公司可以根据客户的购买频率、购买金额和购买商品的类别等属性，将客户分成不同的群体，以便更好地制定营销策略。

#凝聚层次

凝聚式层次聚类是一种自底向上的聚类方法。它最初将每个数据点看作是一个单独的聚类，然后在每一步中，合并最相似（距离最近）的两个聚类，直到满足某个停止条件，比如达到预定的聚类数量或者所有聚类之间的距离超过某个阈值。

举例说明：

  • 假设我们要对一些动物进行聚类，这些动物包括猫、狗、马、牛、鸡、鸭。
  • 初始状态
    • 开始时，我们把每一种动物都看作是一个单独的聚类。所以有 6 个聚类：{猫}、{狗}、{马}、{牛}、{鸡}、{鸭}。
  • 计算相似度（距离）并合并聚类
    • 我们可以通过一些特征来衡量动物之间的相似度，比如生活习性、体型等。假设我们以生活习性为主要衡量标准。
    • 我们发现猫和狗都是宠物，它们的生活习性比较相似，比如都生活在人类的住所周围，所以我们把 {猫} 和 {狗} 合并成一个新的聚类 {猫，狗}。现在还剩下 5 个聚类：{猫，狗}、{马}、{牛}、{鸡}、{鸭}。
  • 继续合并
    • 接着我们发现马和牛都是大型家畜，它们的生活习性也比较相似，比如都在牧场生活，所以我们把 {马} 和 {牛} 合并成一个聚类 {马，牛}。现在有 4 个聚类：{猫，狗}、{马，牛}、{鸡}、{鸭}。
  • 进一步合并
    • 再看鸡和鸭，它们都是家禽，生活习性类似，都在农场的禽类养殖区域生活，于是我们把 {鸡} 和 {鸭} 合并成 {鸡，鸭}。现在剩下 3 个聚类：{猫，狗}、{马，牛}、{鸡，鸭}。
  • 停止条件
    • 如果我们设定聚类数量为 3 个就停止，那么此时聚类过程就结束了。如果没有设定这样的停止条件，聚类过程会继续，比如再考虑 {猫，狗} 和 {马，牛} 的相似度，看是否要合并它们等，直到所有聚类之间的距离超过一个我们设定的阈值。

在实际应用中，凝聚式层次算法可以用于文档聚类。例如，将许多新闻文章进行聚类，最初每篇文章是一个聚类，然后根据文章内容的相似性（如主题、关键词等）逐步合并聚类，最后得到不同主题的新闻文章聚类，帮助用户快速了解新闻的主题分布情况。

DBSCAN

DBSCAN（Density - Based Spatial Clustering of Applications with Noise）是一种基于密度的空间聚类算法。它将数据点分为三类：核心点、边界点和噪声点。核心点是在其邻域内包含足够多的数据点的点；边界点是在核心点的邻域内但自身邻域内数据点数量不足的点；噪声点是既不是核心点也不是边界点的点。

核心概念：

  • $\epsilon$-邻域：对于样本集中的样本$x_j$，其$\epsilon$-邻域包含样本集中与$x_j$的距离小于等于$\epsilon$的样本，即$N_{\epsilon}(x_j)={x_i\in D|d(x_i,x_j)\leq\epsilon}$，其中$D$是数据集，$d$是距离度量（如欧几里得距离）。
  • 核心点：若样本$x_j$的$\epsilon$-邻域内至少包含$MinPts$个样本（包括$x_j$本身），则$x_j$是核心点，即$|N_{\epsilon}(x_j)|\geq MinPts$。
  • 边界点：若样本$x_i$不是核心点，但它在某个核心点的$\epsilon$-邻域内，则$x_i$是边界点。
  • 噪声点：既不是核心点也不是边界点的样本是噪声点。

举例说明：

  • 假设我们有一群人分布在一个操场上，这些人就是我们的数据点。
  • 确定$\epsilon$-邻域和密度阈值$MinPts$
    • 我们先定义一个距离（比如 2 米）作为邻域范围，密度阈值（比如 3 个人）。也就是说，如果一个人周围 2 米范围内有至少 3 个人，那么这个人就是一个核心点。
  • 寻找核心点
    • 比如有一群人在操场的一个角落聊天，他们彼此之间的距离都小于 2 米，人数超过 3 个。那么这个小群体中的每个人都是核心点。
  • 确定边界点和噪声点
    • 现在有一个人，他距离这个聊天群体比较近，大概在 2 米左右的位置，但是他周围（2 米范围内）没有达到 3 个人，那这个人就是边界点。因为他靠近一个密集的群体，但自己所在的小区域密度不够。
    • 而在操场的另一个很远的地方，有一个人孤零零地站着，他周围 2 米范围内根本没有其他人，那这个人就是噪声点。
  • 形成聚类
    • 所有的核心点以及和它们邻域内的边界点就构成了一个聚类。在这个例子中，聊天的那群人以及旁边的边界点就形成了一个聚类，表示操场上的一个人群聚集区域。

在实际应用中，DBSCAN 算法常用于分析空间数据、客户细分等场景，例如分析城市中店铺的分布，找出店铺聚集的商圈（聚类）以及孤立的店铺（噪声）。

计算方法：

这里我们定义$MinPts$为2，相似度阈值为0.8（$\epsilon$-邻域距离计算时取距离小于阈值的点，相似度计算时取相似度大于阈值的点，本质方法一样）。表格表示点P1到P5之间的相似度。

P1 P2 P3 P4 P5
P1 1 0.1 0.41 0.55 0.35
P2 0.10 1 0.64 0.47 0.98
P3 0.41 0.64 1 0.44 0.85
P4 0.55 0.47 0.44 1 0.76
P5 0.35 0.98 0.85 0.76 1

根据表格，P2与P5的相似度为0.98＞0.8，P3与P5的相似度为0.85＞0.8，因此可以判定P2，P3，P5为一类，其中P5是核心点，P2和P3是边界点，P1和P4是噪点。

朴素贝叶斯方法

朴素贝叶斯是一种基于贝叶斯定理的分类算法。贝叶斯定理公式为：
$$
P(A|B)=\frac{P(B|A)P(A)}{P(B)}
$$
在分类问题中，假设我们要分类的类别是$C$（比如是垃圾邮件或者不是垃圾邮件），特征向量是$X = (x_1,x_2,\cdots,x_n)$（比如邮件中的单词、短语等特征）。我们的目标是计算$P(C|X)$，即给定特征向量$X$，属于类别$C$的概率。

根据贝叶斯定理，$P(C|X)=\frac{P(X|C)P(C)}{P(X)}$，由于$P(X)$对于所有类别来说是相同的，所以我们主要关注$P(X|C)P(C)$。

朴素贝叶斯假设特征之间相互独立，所以有
$$
P(X|C)=P(x_1|C)P(x_2|C)\cdots P(x_n|C)
$$
即X包含的子事件X1，X2 … Xn都是独立发生的。

举例说明：

假设我们要判断一封邮件是否是垃圾邮件。类别$C$有两种情况：$C_1$表示是垃圾邮件，$C_2$表示不是垃圾邮件。特征向量$X$是邮件中出现的单词，假设只考虑两个单词“赚钱”和“优惠”。

  • 我们先统计一些数据来计算概率。假设我们有100封邮件，其中60封是垃圾邮件（$P(C_1) = 0.6$），40封不是垃圾邮件（$P(C_2)=0.4$）

  • 在60封垃圾邮件中，“赚钱”这个单词出现了30次，所以$P(x_1 =“赚钱”|C_1)=\frac{30}{60}=0.5$；“优惠”这个单词在垃圾邮件中出现了20次，所以$P(x_2 =“优惠”|C_1)=\frac{20}{60}=\frac{1}{3}$

  • 在40封非垃圾邮件中，“赚钱”这个单词出现了10次，所以$P(x_1 =“赚钱”|C_2)=\frac{10}{40}=0.25$；“优惠”这个单词在非垃圾邮件中出现了20次，所以$P(x_2 =“优惠”|C_2)=\frac{20}{40}=0.5$。

现在有一封新邮件，里面出现了“赚钱”和“优惠”这两个单词。我们来计算它是垃圾邮件的概率$P(C_1|X)$

$$
P(X|C_1)=P(x_1 =“赚钱”|C_1)P(x_2 =“优惠”|C_1)=0.5\times\frac{1}{3}=\frac{1}{6}
$$

$$
P(X|C_2)=P(x_1 =“赚钱”|C_2)P(x_2 =“优惠”|C_2)=0.25\times0.5=\frac{1}{8}
$$

$$
P(C_1|X)=\frac{P(X|C_1)P(C_1)}{P(X|C_1)P(C_1)+P(X|C_2)P(C_2)}=\frac{\frac{1}{6}\times0.6}{\frac{1}{6}\times0.6+\frac{1}{8}\times0.4}=\frac{\frac{1}{10}}{\frac{1}{10}+\frac{1}{20}}=\frac{\frac{1}{10}}{\frac{3}{20}}=\frac{2}{3}
$$

所以这封邮件有$\frac{2}{3}$的概率是垃圾邮件。

拉普拉斯修正

在朴素贝叶斯算法中，可能会出现某个特征在某个类别下概率为0的情况。比如在判断邮件是否为垃圾邮件时，如果在非垃圾邮件中从未出现过“抽奖”这个单词，那么$P(x =“抽奖”|C_2)=0$，这会导致整个$P(X|C_2)$为0，进而影响分类结果。拉普拉斯修正就是为了解决这个问题。

拉普拉斯修正公式为：
$$
P(x_i|C_j)=\frac{N_{x_i,C_j}+1}{N_{C_j}+|V|}
$$
其中$N_{x_i,C_j}$是特征$x_i$在类别$C_j$中出现的次数，$N_{C_j}$是类别$C_j$的总数，$|V|$是特征空间的大小（也就是所有可能特征的数量）。

举例说明：

  • 假设我们还是判断邮件是否是垃圾邮件，特征向量还是考虑“赚钱”和“优惠”两个单词，现在新增一个单词“抽奖”。我们还是有100封邮件，60封垃圾邮件，40封非垃圾邮件。

  • 在垃圾邮件中，“赚钱”出现30次，“优惠”出现20次，“抽奖”出现0次。在非垃圾邮件中，“赚钱”出现10次，“优惠”出现20次，“抽奖”出现0次。 - 假设特征空间大小$|V| = 3$（就是“赚钱”“优惠”“抽奖”这3个单词）。

  • 对于垃圾邮件类别，根据拉普拉斯修正：

    $P(x_1 =“赚钱”|C_1)=\frac{30 + 1}{60+3}=\frac{31}{63}$，$P(x_2 =“优惠”|C_1)=\frac{20 + 1}{60+3}=\frac{21}{63}$，$P(x_3 =“抽奖”|C_1)=\frac{0 + 1}{60+3}=\frac{1}{63}$

  • 对于非垃圾邮件类别，根据拉普拉斯修正：

    $P(x_1 =“赚钱”|C_2)=\frac{10 + 1}{40+3}=\frac{11}{43}$ ，$P(x_2 =“优惠”|C_2)=\frac{20 + 1}{40+3}=\frac{21}{43}$ ，$P(x_3 =“抽奖”|C_2)=\frac{0 + 1}{40+3}=\frac{1}{43}$

现在有一封新邮件，里面出现了“抽奖”这个单词，我们来计算它是垃圾邮件的概率$P(C_1|X)$
$$
P(X|C_1)=P(x_1 =“抽奖”|C_1)=\frac{1}{63}
$$

$$
P(X|C_2)=P(x_1 =“抽奖”|C_2)=\frac{1}{43}
$$

$$
P(C_1|X)=\frac{P(X|C_1)P(C_1)}{P(X|C_1)P(C_1)+P(X|C_2)P(C_2)}=\frac{\frac{1}{63}\times0.6}{\frac{1}{63}\times0.6+\frac{1}{43}\times0.4}=\frac{\frac{1}{105}}{\frac{1}{105}+\frac{2}{215}}=\frac{43}{86}
$$

可以看到拉普拉斯修正避免了因为某个特征概率为0而导致的不合理结果。

参考链接

感谢泰姆埃洛斯，伟大，无需多言

[1] 南京大学软件学院-2023-数据仓库（研究生）期末复习参考