AllenYGY's Blog

Appearance

BFR Algorithm ​

The BFR Algorithm is an extension of K-Means designed for large-scale and high-dimensional data. It improves K-Means by dividing data into three sets:

  1. Discard Set (DS): Summarizes points close to cluster centroids using statistics (e.g., count, sum, sum of squares).
  2. Compression Set (CS): Groups points that form small clusters but aren’t close to the main centroids.
  3. Retained Set (RS): Holds points far from any cluster or mini-cluster, which are potential outliers.

Outlier Detection Process ​

Outliers are identified using the RS:

  1. Points in the RS are compared against cluster centroids.
  2. Those consistently far from all clusters and mini-clusters across iterations are marked as outliers.

Example ​

A 2D dataset shows customer transactions. Most points group into three clusters:

  • Frequent, low-value purchases.
  • Occasional, high-value purchases.
  • Moderate frequency and value.

Some points are far from these groups.

  1. Assign points to clusters based on proximity to centroids.
  2. Points far from all centroids go into the RS.
  3. After several iterations, points still in the RS are flagged as outliers.

Unusual transactions, such as very high-value but rare purchases, are identified as outliers.

BFR 算法（Bradley-Fayyad-Reina Algorithm） ​

BFR 算法是一种用于 大规模数据聚类 的经典方法，尤其适用于需要在主内存受限的情况下处理高维数据流。该算法以 k-means 为核心，利用主内存和磁盘协作来进行聚类。

1. 背景与目标 ​

  • 背景：

    • 数据规模过大，无法一次性加载到主内存中。
    • 数据分布在高维空间，传统聚类算法在处理速度和内存使用上表现不佳。

  • 目标：

    • 聚类数据为 kk 个簇，同时高效利用内存和磁盘。

2. 核心思想 ​

  1. 利用统计摘要：

    • 使用 统计量 来描述每个聚类簇（例如：质心、协方差矩阵）。
    • 通过统计摘要避免频繁存储和读取完整数据点，减少内存压力。

  2. 分块处理数据：

    • 数据流按块（chunks）加载到内存，每次只处理一部分数据。

  3. 聚类更新：

    • 对内存中的数据点进行聚类，更新现有的簇统计量。
    • 对离群点（outliers）单独处理，避免影响聚类质量。

3. 主要步骤 ​

BFR 算法分为以下几个阶段：

(1) 初始化 ​

  • 从初始数据中随机采样 kk 个点，使用传统 k-means 算法初始化 kk 个聚类中心。
  • 记录每个簇的统计摘要：
    • NiN_i：簇 ii 中数据点的数量。
    • SUMi\textbf{SUM}_i：簇 ii 中所有数据点的向量和。
    • SUMSQi\textbf{SUMSQ}_i：簇 ii 中所有数据点的向量平方和。

(2) 数据分块处理 ​

对于每个加载到内存中的数据块，执行以下操作：

  1. 分配数据点到簇：

    • 计算每个数据点到所有聚类中心的距离，分配到距离最近的簇。
    • 更新统计摘要：
      • Ni=Ni+1N_i = N_i + 1
      • SUMi=SUMi+x\textbf{SUM}_i = \textbf{SUM}_i + \textbf
      • SUMSQi=SUMSQi+x2\textbf{SUMSQ}_i = \textbf{SUMSQ}_i + \textbf{x}^2
    • 不保存具体的数据点，仅更新统计量。

  2. 处理离群点：

    • 如果某些数据点距离任何簇中心都较远，标记为离群点（Outliers）。
    • 将离群点单独存储，稍后处理。

(3) 聚类统计更新 ​

  • 使用更新后的统计摘要重新计算每个簇的质心和协方差：
    • 质心：μi=SUMiNi\mu_i = \frac{\textbf{SUM}_i}
    • 协方差矩阵：根据 SUMSQi\textbf{SUMSQ}_i、SUMi\textbf{SUM}_i 和 NiN_i 计算。

(4) 合并离群点 ​

  • 检查离群点集合，如果某些离群点在新一轮聚类中接近某个簇的质心，则将其合并到该簇中。
  • 如果离群点长期不属于任何簇，可将其删除或作为单独簇处理。

(5) 重复迭代 ​

  • 加载下一个数据块，重复步骤 (2)-(4)，直到所有数据处理完毕。

4. 算法特点 ​

  • 优点：

    • 节省内存：通过统计摘要处理数据，无需存储所有点。
    • 适合高维数据：避免直接对高维数据计算，减少计算复杂度。
    • 增量更新：能够动态处理数据流，适应不断到来的新数据。

  • 缺点：

    • 对于复杂分布的簇，可能不能很好地捕捉非球形簇的特征。
    • 离群点处理的质量依赖于算法参数（如阈值）。

5. 应用场景 ​

  • 大规模数据聚类：
    • 大型社交网络数据分析。
    • 电商中的推荐系统。
  • 高维数据分析：
    • 文本数据的主题分类。
    • 生物信息学中的基因表达聚类。
  • 实时数据处理：
    • 网络流量聚类。
    • 日志数据中的模式发现。

总结 ​

BFR 算法是一种结合了 k-means 和统计摘要的高效聚类算法，适用于大规模、高维、数据流式的场景。通过分块处理和离群点管理，它能够在内存限制下实现接近于传统聚类算法的效果。如果需要实现或更深入的细节，欢迎随时交流！