algorithm - Bisecting k-means聚类算法解释

Question

我被要求写一个二等分 k-means 算法，但我不明白这个算法。我知道 k-means 算法。

你能解释一下这个算法吗，但在academic language中没有

谢谢。

Answer 1

这个想法是迭代地将点云分成两部分。换句话说，您构建了一个随机二叉树，其中每次拆分(一个有两个子节点的节点)对应于将云中的点一分为二。

你从一堆点开始。

• 计算其质心(重心)w

• 在云的点中随机选择一个点cL

• 构造点cR作为cL相对于w的对称点(线段cL->w与w->cR相同)

• 将云的点一分为二，最接近 cR 的点属于子云 R，最接近 cL 的点属于子云 L

• 重申子云R和L

注释:

您可以在使用后丢弃随机点。但是，保留所有子函数的质心。

当您的子云恰好包含一个点时停止。

如果你想要 k 个簇，只需取 k 个质心，使它们包含初始云的所有点。如果你愿意，你可以做更精细的事情(最小化云的方差等......)假设你想要 4 个集群(为方便起见，是 2 的幂)然后你只需要将云切成两半，然后将每个亚云一分为二。如果您想要 8 个簇，则再次将这些子云一分为二切割。又是 16 个集群。

如果您想要 K 个 K 不是 2 的幂(比如 24)的簇，则查看最接近的次幂 2。 16个，你还缺8个簇。每个“16 级集群”都是“16 级子云”的质心。你要做的是取 8 个“16 级集群”(例如随机)并用两个“子级”“32 级集群”替换它们。 (这两个子“level-32-clusters”对应于两个“level-32-subclouds”加起来就是父“level-16-subcloud”)