1 K-MEANS 算法

1.1 聚类问题

• 在机器学习领域，聚类属于无监督学习的范畴；

• 无监督问题：我们手里没有标签了；

  • 在有监督学习中，数据集中每个样本都有对应的标签（类别信息），算法通过学习这些带有标签的数据来建立模型，进而对新数据进行分类或预测；
  • 而聚类作为无监督问题，面对的数据是没有预先定义好的类别标签的，需要算法自行从数据的特征中寻找规律和模式，将数据划分成不同的组；

• 聚类：相似的东西分到一组；

  • 聚类算法的核心目标就是依据数据对象之间的相似性度量，把相似程度较高的数据点归为同一个簇（组），使得同一簇内的数据尽可能相似，不同簇之间的数据差异尽可能大；
  • 比如在对一群人的身高、体重数据进行聚类时，身材高大且体重大的人会被聚到一类，身材矮小且体重轻的人会被聚到另一类；

• 难点：如何评估，如何调参；

  • 由于没有事先给定的标签作为参考，很难判断聚类结果的好坏；
  • 此外，不同的聚类算法有各自的参数，如 K - MEANS 算法中的 K 值（簇的个数）、DBSCAN 算法中的半径 ϵ 和密度阈值 MinPts 等，选择合适的参数对聚类效果影响巨大，但目前并没有通用、简单的方法来确定这些参数

• 下图是一张聚类结果可视化散点图；

  

  • 图中不同颜色（绿色、红色、蓝色 ）的十字散点分别代表被划分到不同簇的数据点；
  • 聚类算法通过对数据点间相似性的计算，将原本无类别标签的数据点划分到不同类别中，相同颜色的点属于同一簇，体现了聚类“把相似东西分到一组”的特性 ，便于直观观察聚类算法对数据的分组效果。

1.2 基本概念

1.2.1 正经讲解

• 簇个数的确定：
  • K-MEANS算法需要事先指定K值 ，K代表最终要划分出的簇的个数；
  • 比如K = 3，就是要把数据聚成3个簇；
• 质心：
  • 质心是一个簇的中心位置，通过计算簇内所有向量各维度的平均值得到；
  • 例如在二维空间中，一个簇内点坐标为(1, 2)、(3, 4) ，质心坐标就是((1 + 3)/2, (2 + 4)/2) = (2, 3) ；
• 距离度量：
  • 常用欧几里得距离衡量数据点间的实际距离 ，如二维空间两点(x1, y1)、(x2, y2) ，距离为$\sqrt{(x_2-x_1{)}^2+(y_2-y_1{)}^2}$ ；
  • 余弦相似度衡量向量间方向的相似性，使用前需对数据标准化，防止不同量纲影响；
• 优化目标：
  • 公式$\min {\sum }_{i=1}^K{\sum }_{x\in C_i}dist(c_i,x{)}^2$ ，意思是最小化所有数据点到其所属簇质心距离的平方和；
  • 通过不断调整质心位置，使这个值达到最小，实现聚类效果优化。

1.2.2 通俗讲解

• 要得到簇的个数，需要指定K值：
  • 想象你有一堆五颜六色的珠子散落在桌子上，现在想把它们分成几堆；
  • K-MEANS算法就像在做这个分类工作，而K值就是你一开始决定要把珠子分成几堆；
  • 比如你说K = 4 ，那算法就会努力把这些珠子分成4堆 ，但具体怎么分，就看后面的计算啦；
• 质心：均值，即向量各维取平均即可：
  • 还是拿珠子举例，假如你已经把珠子分成了几堆。每一堆珠子都有自己的中心位置，这个中心位置怎么确定呢？
  • 就像找一群同学身高的平均值一样，把这一堆珠子在各个维度（比如在二维平面上就是横、纵两个方向）上的位置数值加起来，再除以珠子的数量，得到的那个位置就是这一堆珠子的“中心”，在K-MEANS算法里，这个“中心”就叫质心；
• 距离的度量：常用欧几里得距离和余弦相似度（先标准化）
  • 欧几里得距离：
    • 假如珠子在一张方格纸上，欧几里得距离就像是用尺子直接去量两个珠子之间的直线距离；
    • 比如一个珠子在(1, 1)位置，另一个在(3, 3)位置，就按照勾股定理算出它们之间的直线距离；
  • 余弦相似度：
    • 想象珠子有不同的朝向（可以理解为向量的方向 ），余弦相似度就是看两个珠子（向量 ）的朝向有多像，方向越接近，相似度就越高，和它们离得远不远没有关系；
    • 不过在算之前，要先把珠子的一些属性调整到统一的标准，这就是标准化；
• 优化目标：$\min {\sum }_{i=1}^K{\sum }_{x\in C_i}dist(c_i,x{)}^2$
  • 这一串符号看着复杂，其实就是说，算法要努力让每一个珠子（数据点x ）到它所在那一堆（簇Ci ）“中心”（质心ci ）的距离的平方和最小；
  • 就好像你希望每一堆珠子都紧紧围绕着自己那一堆的中心，不要太分散，这样聚类的效果就比较好了。

1.3 工作流程

• （a）初始数据分布：图中展示了一组未聚类的绿色数据点，这些点在平面上呈现出一定的分布状态，此时尚未进行聚类操作，是算法处理的原始数据集合；
• （b）初始化质心：随机选择两个点（图中用红色叉号和蓝色叉号表示 ）作为初始质心；
  • 在 K-MEANS 算法中，K 值决定了簇的数量，这里 K = 2，所以选择两个质心；
  • 这两个点的选择是随机的，不同的初始质心选择可能会导致最终聚类结果有所差异；
• （c）分配数据点：根据距离度量（通常是欧几里得距离 ），将每个数据点分配到离它最近的质心所在的簇。图中绿色数据点被重新标记为红色和蓝色，分别表示被划分到以红色叉号和蓝色叉号为质心的簇中；
• （d）更新质心：重新计算每个簇中数据点的均值，以此更新质心的位置。图中可以看到红色和蓝色的叉号（质心 ）位置发生了变化，它们移动到了各自簇内数据点的平均位置；
• （e）再次分配数据点：基于更新后的质心位置，再次根据距离度量将每个数据点重新分配到离它最近的质心所在的簇。部分数据点的归属可能会发生变化；
• （f）迭代收敛：不断重复更新质心和重新分配数据点的步骤，直到质心位置不再发生明显变化（或者达到预设的迭代次数 ），此时算法收敛，聚类结果稳定；
• 总结：
  • 图（f）展示了经过多次迭代后相对稳定的聚类状态，每个数据点都被划分到相对合适的簇中；
  • 整个过程通过不断迭代调整质心位置和数据点的归属，使得每个簇内的数据点尽可能相似（距离质心较近 ），实现数据的聚类划分；
• 可视化：Visualizing K-Means Clustering。

1.4 优势和劣势

• 优势

  • 简单：

    • K-MEANS算法的原理和实现相对直观；
    • 它主要就是围绕着确定质心、分配数据点到最近质心、更新质心这几个基本步骤循环进行，对于初学者来说容易理解和上手实现；
    • 比如在一些简单的学生成绩聚类场景中，很容易就能按照算法步骤操作起来；

  • 快速：

    • 在数据量不是特别巨大的情况下，计算速度比较快；
    • 因为每次迭代主要就是计算数据点到质心的距离以及更新质心位置，这些计算操作相对高效；
    • 像处理几千条用户购买记录的简单聚类分析时，能较快得出结果；

  • 适合常规数据集：

    • 对于分布比较均匀、簇形状大致为球形等常规形态的数据集，K-MEANS算法能很好地发挥作用，得到比较理想的聚类效果；
    • 例如在对一些具有明显分组特征的身高体重数据聚类时表现不错；

• 劣势

  • K值难确定：

    • K-MEANS算法需要事先指定簇的个数K，但在实际应用中，数据内在的合适簇数往往是未知的；
    • 如果K值设定过小，可能会把原本应该分开的类别合并；K值设定过大，又会把本属于一类的数据过度拆分；
    • 比如在对一群动物按体型、习性等特征聚类时，很难提前知道到底该聚成几类。

  • 复杂度与样本呈线性关系：

    • 随着样本数量的增加，算法的计算量会近似线性增长；
    • 因为每次迭代都要计算每个样本点到质心的距离等操作，当样本量非常大时，计算开销会变得很大，运行效率会降低，处理大规模数据集时会面临性能瓶颈；

  • 很难发现任意形状的簇：

    • K-MEANS算法基于质心和距离度量来聚类，倾向于形成球形的簇；
    • 对于一些不规则形状（如环形、细长条形等 ）的数据分布，它很难准确地识别和划分簇，容易导致聚类结果不准确；
    • 比如对于呈环形分布的数据点，K-MEANS算法就很难给出合理的聚类。

• 例：

  

  • 很难发现任意形状的簇：

    • 图中数据点分布呈现出环形等不规则形状；
    • K-MEANS算法基于质心和距离度量，倾向于形成球形簇；
    • 对于这种不规则形状的数据分布，它难以准确识别和划分簇；
    • 比如可能会把环形内外的数据点错误地划分到同一簇，无法按照其真实分布特征进行合理聚类；

  • K值难确定：

    • 从图中难以直接判断应该将这些数据点划分为几个簇合适；
    • 在K-MEANS算法中，需要事先指定K值，而面对这种复杂分布的数据，很难预先确定一个能使聚类效果最优的K值；
    • 如果K值设定不当，会导致聚类结果不佳，如过度聚类或聚类不足。

2 DBSCAN 算法

2.1 基本概念

• Density - Based Spatial Clustering of Applications with Noise（DBSCAN，具有噪声的基于密度的空间聚类应用）：

  • 它的核心是基于数据点的密度来进行聚类；
  • 不像有些算法要事先规定分成几个类，它能在有噪声（干扰数据 ）的情况下，把密度高的区域划分成簇（类 ），还能找出任意形状的簇；
  • 比如在一堆杂乱分布的数据里，把聚集在一起的数据点归为一类；

• 核心对象：

  • 想象在一个广场上，人们分散站着；
  • 如果以某个人为中心，画一个半径为 r 的圈，在这个圈里的人数如果达到了算法设定的数量（不小于minPts ），那这个站在中心的人就相当于核心对象；
  • 在数据里就是说某个点周围特定半径 r 邻域内点的数量够多，达到了要求，这个点就是核心点；

• ϵ-邻域的距离阈值（半径r）：

  • 就是例子中画圈的半径；
  • 在算法里，它用来确定一个点的邻域范围，以这个点为中心，半径 r 内的区域就是它的 ϵ - 邻域 ，通过看这个邻域里有多少点，来判断这个点是不是核心对象等情况；

• 直接密度可达：

  • 还是广场的例子，假如前面说的那个核心对象（站在圈中心且圈内人够多的人 ），另一个人在他画的圈（r 邻域 ）里面，那这个在圈里的人就和核心对象是直接密度可达的关系；
  • 对应到数据上就是，一个点p在核心点q的r邻域内，那么p - q就是直接密度可达；

• 密度可达：

  • 假如广场上有一串人，第一个人在第二个人画的圈里（直接密度可达 ），第二个人在第三个人画的圈里（直接密度可达 ），这样一直连下去，那第一个人和最后一个人就是密度可达的关系；
  • 在数据里就是有一个点的序列 q0、q1、…qk ，前面的点到后面的点都是直接密度可达，那 q0 到 qk 就是密度可达，是直接密度可达关系的传递；

• 密度相连：

  • 想象有一片茂密的森林，里面有一些大树（代表核心点）；
  • 从某一棵大树（核心点p）出发，沿着林间小道（密度可达路径），能走到两棵不同的树（点q和点k），这两棵树（点q和点k）之间就存在一种联系，它们就是密度相连的；
  • 也就是说，只要能通过从同一个核心点出发，分别到达两个点，这两个点就具有密度相连的关系 ，它们在聚类意义上属于同一“势力范围”；

• 边界点：

  • 森林里有些树，它们本身周围树木数量不够多（不是核心点），但又在某个大树（核心点）的“势力范围”（r邻域）边缘附近，属于某个大树“势力范围”（簇 ）内的点；
  • 它们没办法像核心点那样去“拉拢”更多的树（发展下线），这些树就类似于边界点 ，是属于某个簇但又不是核心成员的点；

• 噪声点：

  • 在这片森林里，有一些特别偏远、孤立的小树苗，从任何一棵大树（核心点）出发，都没办法通过林间小道（密度可达路径）走到它们那里；
  • 这些孤立的小树苗就像噪声点，在聚类中，它们不属于任何一个簇（类），是游离在正常聚类范围之外的点；

• 图解：

  

  • 核心对象（A）：

    • 图中红色点A代表核心对象；
    • 在DBSCAN算法里，核心对象是指在其ϵ-邻域（图中红色圆圈 ）内包含的数据点数量达到或超过算法设定阈值（MinPts ）的点；
    • 核心对象是聚类的关键，能“发展下线”，通过密度可达关系拓展簇；

  • 边界点（B、C）：

    • 黄色点B和C是边界点；
    • 它们属于某个簇，但自身不是核心对象，即其ϵ-邻域（黄色圆圈 ）内点数未达MinPts；
    • 边界点在核心对象的邻域内，依赖核心对象确定所属簇，不能像核心对象那样吸引其他点拓展簇；

  • 离群点（N）：

    • 蓝色点N是离群点；
    • 它不属于任何簇，从任何核心对象出发都无法通过密度可达关系到达该点，其ϵ-邻域（蓝色圆圈 ）内点数远小于MinPts ，在聚类中被视为噪声点；
    • 图中箭头表示密度可达关系，体现了核心对象如何通过密度可达拓展簇以及各点间的关系。

2.2 工作流程

• 工作流程：

  1. 初始化：

     • 将数据集中所有对象标记为未访问（unvisited ）；
     • 这是算法开始的准备工作，为后续遍历数据点做铺垫；

  2. 选择并标记点：

     • 随机挑选一个未访问的对象p ，并将其标记为已访问（visited ）；
     • 这是每次迭代开始对单个数据点的处理；

  3. 判断核心点并聚类：

     • 检查点p的ϵ - 邻域（半径为ϵ的范围 ）内是否至少有MinPts个对象；
     • 若满足，说明p是核心点，创建新簇C并把p加入；
     • 然后获取p的ϵ - 邻域内对象集合N ，遍历N中的每个点p’ ；
     • 若p’未访问，标记为已访问，若p’的ϵ - 邻域也满足至少有MinPts个对象，将这些对象添加到N ，若p’还不属于任何簇，就把p’加入到C；
     • 过这种方式不断拓展簇；

  4. 标记噪声点：若点p的ϵ - 邻域内对象数小于MinPts ，则将p标记为噪声点；

  5. 迭代终止：不断重复上述过程，直到没有未访问的对象，此时算法结束；

• 相关参数：

  • 参数D：即输入数据集，是算法处理的对象集合；

  • 参数ϵ：指定半径，用于确定一个点的邻域范围，判断点与点之间的密度关系；

  • MinPts：密度阈值，用于判断一个点是否为核心点，即其ϵ - 邻域内对象数量需达到或超过MinPts才是核心点；

• 参数选择：

  • 半径ϵ
    • 可依据K距离来设定；
    • 先对给定数据集P中的每个点P(i) ，计算它到集合D的子集S中所有点的距离，并将这些距离从小到大排序 ，排好序后的第k个距离值d(k) 就是k - 距离；
    • 通过观察k - 距离曲线的突变点来确定半径ϵ ；
    • 突变点意味着距离在此处发生明显变化，可将突变点对应的距离值作为合适的ϵ ，以合理界定数据点的邻域范围；
  • MinPts
    • 它是k - 距离中k的值；
    • 一般取值较小，需多次尝试不同数值；
    • 因为不同数据集特点不同，合适的MinPts值能准确判断核心点，进而影响聚类效果；
    • 多次尝试是为了找到能使算法在给定数据集上产生最佳聚类结果的MinPts值；

• 可视化：Visualizing DBSCAN Clustering；

  

2.3 优势和劣势

• 优势：

  • 不需要指定簇个数：

    • 与K-MEANS等算法不同，DBSCAN算法不需要事先人为确定要划分成几个簇；
    • 它通过数据点的密度相连关系自动确定簇的数量，更贴合数据实际分布情况，减少了因人为指定簇数不当导致聚类效果不佳的问题；

  • 可以发现任意形状的簇：K-MEANS倾向于形成球形簇，而DBSCAN不受此限制，能根据数据点的密度分布发现各种不规则形状的簇，比如环形、条形等，在处理复杂分布的数据时表现更灵活；

  • 擅长找到离群点（检测任务）：DBSCAN通过密度判断数据点归属，对于那些密度明显低于其他区域的数据点，即离群点，能够有效识别出来，在异常检测等任务中具有优势；

  • 两个参数就够了：该算法主要依赖半径ϵ和密度阈值MinPts这两个参数，相比一些需要更多参数调节的聚类算法，在参数设置的复杂度上更低；

• 劣势：

  • 高维数据有些困难（可以做降维）：

    • 随着数据维度增加，数据点之间的距离度量变得复杂，密度计算也不准确，导致聚类效果变差；
    • 不过可以通过降维技术（如PCA等 ）先对高维数据进行处理，再应用DBSCAN算法；

  • 参数难以选择（参数对结果的影响非常大）：

    • 半径ϵ和密度阈值MinPts的取值对聚类结果影响巨大；
    • 合适的参数能得到准确的聚类结果，参数选择不当则可能导致过度聚类或聚类不足等问题，且没有通用的方法来确定最佳参数，往往需要多次尝试和经验判断；

  • Sklearn中效率很慢（数据削减策略）：

    • 在Python的Sklearn库中实现的DBSCAN算法，当数据集规模较大时，计算效率较低；
    • 可采用数据削减策略，如先对数据进行抽样等方式，在一定程度上提高算法运行效率。