摘要
轮廓是评估 $k$-聚类质量的广泛使用的指标之一，其评估仅需聚类分配的信息。轮廓易于解释，为聚类整体或每个元素提供质量评分。然而，准确计算每个数据集元素的轮廓和全局轮廓需要 $\Theta(n^2)$ 次距离计算，这在现代大规模数据集中显得极为繁重。
现有的近似方法虽然使用 $O(n^2)$ 的距离计算，但通常是启发式，缺乏可证明和可控的质量保证。我们提出了首个严格且高效的算法，用于估计：
- 数据集中每个元素的（局部）轮廓；
- 任何度量 $k$-聚类的（全局）轮廓。
我们的方法基于采样，执行 $O(nk\varepsilon^{-2}\ln (nk/\delta))$ 次距离计算，提供误差为 $O(\varepsilon)$ 的估计，且概率至少为 $1-\delta$。其中，参数 $\varepsilon$ 和 $\delta$ 在 $(0,1)$ 中控制准确性与效率之间的权衡。
此外，我们为 MapReduce 和大规模并行计算 (MPC) 框架设计了可扩展的分布式方法。我们的分布式算法使用常数轮次和亚线性局部内存。通过与最先进方法的广泛实验，我们的新技术在局部和全局轮廓估计方面都展现了最佳的准确性与效率权衡，同时能够高效扩展至无法进行准确计算的大规模数据集。
博主点评： 该研究在轮廓估计领域开辟了新的视角，通过引入有效的采样算法和分布式计算框架，为处理大规模数据集提供了切实可行的解决方案。这不仅提升了聚类质量评估的效率，也为未来的相关研究奠定了基础。有效的误差控制机制使得算法在准确性与效率之间取得了良好的平衡，具有广泛的应用前景。