algorithm - Bisecting k-means clustering algorithm explanation

Question

I was required to write a bisecting k-means algorithm, but I didnt understand the algorithm. I know k-means algorithm.

Can you explain the algorithm, but not in academic language

Thanks.

Answer 1

这个想法是迭代地将你的点云分成两部分。换句话说，你构建了一个随机二叉树，其中每个分裂（一个有两个孩子的节点）对应于将你的云点分裂为 2。

你从一堆点开始。

• 计算其质心（重心）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 个“level-16-clusters”（例如随机）并将它们分别替换为两个“child”“level-32-clusters”。（这两个子“level-32-clusters”对应于两个“level-32-subcloud”，它们加起来就是父级“level-16-subcloud”）