K-mean算法详解

An efficient K-means clustering algorithm for massive data论文详解

关于这一部分，你将收获到K-means算法关于初始聚类点的计算以及优化方式，除此之外还有关于聚类边界的点集划分的计算。

核心概念：快速判断一个数据块内的点是否都属于同一个聚类

BWKM算法的核心目标之一是避免对每个数据点都进行K次距离计算（传统Lloyd算法需要）。它通过将数据空间划分为块(Block)，并利用块的整体几何属性质心信息，快速判断整个块内的点是否可能都属于同一个聚类。如果判断属于同一个聚类，那么该块内所有点都可以被整体分配给该聚类，无需再逐个点计算距离。这大大节省了计算量。

定义解析：

1. 定义3：误分配函数 (ϵᴄ,ᴅ(B))

   • 输入:
     • C: K个质心的集合。
     • D: 数据集 (d维空间中的点)。
     • B: 一个空间块 (比如一个矩形区域)。
     • P = B(D): 落在块B内的数据点的子集。如果P是空的(∅)，则误分配函数为0。
   • 输出: ϵᴄ,ᴅ(B) - 一个非负实数，衡量块B内的点可能被错误分配到不同聚类的风险程度。
   • 计算公式:
     • ϵᴄ,ᴅ(B) = max{0, 2 * lʙ - δᴘ(C)}
   • 公式组成:
     • lʙ: 块B对角线的长度。这代表了块B在空间中的最大可能跨度。块越大，lʙ越大。
     • δᴘ(C):
       • 设P̄是点集P的代表点（通常用P的质心，由加权Lloyd算法计算得出）。
       • 设cᴘ̄是离P̄最近的那个质心 (cᴘ̄ ∈ C)。
       • δᴘ(C) = min_{c ∈ C \ {cᴘ̄}} ||P̄ - c|| - ||P̄ - cᴘ̄||
       • 解释:
         • ||P̄ - cᴘ̄|| 是代表点P̄到其最近质心cᴘ̄的距离。
         • min_{c ∈ C \ {cᴘ̄}} ||P̄ - c|| 是代表点P̄到除最近质心cᴘ̄外所有其他质心c中最小的距离（即到第二近质心的距离）。
         • 所以，δᴘ(C) = (代表点P̄到第二近质心的距离) - (代表点P̄到最近质心的距离)。
         • 物理意义: δᴘ(C) 衡量了最近质心cᴘ̄相对于其他质心对代表点P̄的“优势”有多大。δᴘ(C)越大，说明cᴘ̄比第二近的质心离P̄近很多，P̄属于cᴘ̄的确定性越高。
   • 2 * lʙ - δᴘ(C) 的含义:
     • 2 * lʙ: 这是块B内任意两点之间最大可能距离的上限（根据三角不等式，块内任意两点距离不会超过对角线长度lʙ，但乘以2提供了一个更宽松的、更容易计算的上界）。
     • δᴘ(C): 如上所述，是最近质心cᴘ̄对P̄的优势程度。
     • 整个项 2 * lʙ - δᴘ(C) 的含义: 想象块B内有一个点x，它可能离代表点P̄很远（最远可达lʙ量级）。如果块B非常大(lʙ很大)，或者cᴘ̄的优势很小(δᴘ(C)很小)，那么x离P̄的距离可能会抵消cᴘ̄相对于其他质心对P̄的优势，使得x有可能被分配到cᴘ̄以外的其他质心（比如第二近的质心）。2 * lʙ - δᴘ(C) 这个值量化了这种风险。
   • max{0, ...} 的含义: 如果2 * lʙ - δᴘ(C)小于或等于0，说明即使考虑块内离P̄最远的点，cᴘ̄的优势仍然足够大，理论上可以保证块内所有点都应该分配给cᴘ̄。此时ϵ=0。如果2 * lʙ - δᴘ(C) > 0，则存在风险，块内可能有点不属于cᴘ̄。风险越大，ϵ值越大。
   • 总结 ϵᴄ,ᴅ(B) 的作用: 它是一个风险指示器。ϵ=0 表示块B内所有点一定都属于同一个聚类（即cᴘ̄）。ϵ>0 表示块B内可能有点属于不同的聚类，ϵ值越大，这种可能性越高（启发式规则）。

2. 定理1：误分配函数为0的意义

   • 陈述: 如果对于一个非空的块B（包含点集P），计算出的误分配函数 ϵᴄ,ᴅ(B) = 0，那么块B内每一个点x的最近质心cₓ，都等于代表点P̄的最近质心cᴘ̄。即：所有点x ∈ P都属于同一个聚类cᴘ̄。
   • 重要性: 这是BWKM算法高效性的理论基础。它证明了仅利用块B的几何信息(lʙ)、代表点P̄（由加权Lloyd提供）和质心C，通过计算ϵ，无需检查块内任何一个具体数据点x的距离，就能绝对确定整个块B内的点都属于同一个聚类cᴘ̄。这是算法能跳过大量距离计算的关键。

3. 定义4：边界 (ℱᴄ,ᴅ(ℬ))

   • 输入:
     • D: 数据集。
     • C: 质心集合。
     • ℬ: 一个空间划分（由许多块B组成）。
   • 输出: ℱᴄ,ᴅ(ℬ) - 当前划分ℬ的边界。
   • 定义: 边界 ℱᴄ,ᴅ(ℬ) 是划分ℬ中所有满足 ϵᴄ,ᴅ(B) > 0 的块B组成的子集。
   • 意义: 边界包含了所有可能没有被正确分配（即内部点可能属于不同聚类）的块。这些块是算法需要进一步关注和处理的对象。
   • 算法中的应用 (BWKM的核心策略): BWKM算法在运行过程中会维护一个空间划分ℬ。它只对边界块(ℱᴄ,ᴅ(ℬ)中的块)进行分割细化。如果一个块B的ϵ=0（不在边界上），那么它就被认为是“安全”的，其内部所有点都被整体分配给cᴘ̄，算法在后续迭代中不会再处理这个块内部（除非质心移动导致ϵ重新大于0）。这个策略极大地减少了需要细化和计算距离的块的数量，从而提高了效率。

图1解释:

图中展示了一个具体的块B（黑色边框矩形），内部有红蓝两色的点（属于两个不同的聚类，质心用蓝色星星表示）。代表点P̄是紫色菱形。

• 计算 ϵᴄ,ᴅ(B) 需要的信息 (图中所示):
  • ||P̄ - cᴘ̄||: 紫色菱形(P̄)到离它最近的蓝色星星(cᴘ̄)的距离（一条蓝色虚线）。
  • min_{c ∈ C \ {cᴘ̄}} ||P̄ - c||: 紫色菱形(P̄)到另一个（第二近的）蓝色星星的距离（另一条蓝色虚线）。在这个例子中，cᴘ̄和这个第二近质心正好是那两个蓝色星星。
  • δᴘ(C) = min_{c ∈ C \ {cᴘ̄}} ||P̄ - c|| - ||P̄ - cᴘ̄||: 两条蓝色虚线长度的差值。
  • lʙ: 块B的紫色对角线长度（紫色虚线）。
• 为什么 ϵ > 0? 块内实际包含了属于两个不同聚类的点（红点和蓝点）。代表点P̄可能靠近块中心或某个质心，但块的范围(lʙ)足够大，包含了靠近另一个质心的区域（图中右上角的红点离右边的蓝色星星更近）。计算出来的 2 * lʙ 大于 δᴘ(C)，导致 ϵ = 2 * lʙ - δᴘ(C) > 0。这正确地反映了该块没有被“完好分配”（well assigned）的风险/事实，因此它会被包含在边界ℱ中，需要被进一步分割。

总结:

1. 误分配函数 ϵ：是一个利用块几何大小(lʙ)、代表点(P̄)和质心(C)计算出来的值，用于评估块内点是否可能属于不同聚类。
2. 定理1：ϵ=0 是块内所有点必然属于同一聚类的充分条件。这允许算法安全地跳过这些块内部的距离计算。
3. 边界 ℱ：是所有 ϵ>0 的块的集合。这些块需要进一步处理（分割细化）。
4. BWKM算法策略：在每次迭代中，只对当前划分的**边界块(ℱ)**进行分割细化，并对这些细化后的块计算ϵ。对于ϵ=0的块，将其内所有点整体分配给cᴘ̄；对于ϵ>0的块，保留在边界中等待下次迭代可能继续分割。同时，质心会根据当前分配更新。这个过程不断重复，边界越来越细，直到满足停止条件（如边界为空、迭代次数、质心变化小等）。
5. 优势：通过避免对ϵ=0的“安全”块进行内部点级的距离计算和检查，以及只关注边界块进行细化，BWKM显著减少了k-means迭代中所需的距离计算次数，从而加速了计算，尤其适合处理大规模数据集。

Reference

[1] An efficient K-means clustering algorithm for massive data