RVN 一种新的聚类算法 _RVN

当我们需要对数据集进行聚类时，我们可能首先研究的算法是 K means, DBscan, hierarchical clustering。那些经典的聚类算法总是将每个数据点视为一个点。但是，这些数据点在现实生活中通常具有大小或边界（边界框）。忽略点的边缘可能会导致进一步的偏差。RVN算法是一种考虑点和每个点的边界框的方法。
RVN 的灵感来自一家家具公司的商业案例。他们的工作是按生活方式对家具进行分类，由于每件家具都有不同的形状和大小，而一些家具是否重叠比彼此之间的距离更关键，所以创建了可以考虑每个点大小的 RVN 算法，相信该算法可以进一步在其他领域实现，例如生态系统和像素聚类。
世界地图示例 - K means当需要对地球上所有国家进行聚类时，首先需要每个国家的坐标（经度和纬度）。

文章插图

文章插图

然后可以使用 K mean 或其他算法来调整最佳簇数量或找到最佳 eps 进行DB scan 。我们将使用 K mean作为样例

文章插图

根据上图，我们选择k=3 。
看起来不错！但是我们可以注意到一些国家的一些问题，比如俄罗斯。

文章插图

可以看到俄罗斯与其他亚洲国家聚集在一起。原因是代表俄罗斯位置的点更靠近其他亚洲国家。如果我们把这一点再左一点，俄罗斯就会聚集到左边。
通过这个例子定义每个点的位置对我们的结果有很大的影响。
RVN 算法下面介绍一下RVN算法的基本逻辑。
数据要求：每个点的上限和下限
初始化

初始化n个簇（数据大小为n），每个点为一个簇
计算每个簇的半径（使用上限和下限）

迭代

检查所有重叠点。（范围重叠）
将所有重叠点分组为同一个簇
更新每个簇的质心和半径

停止策略

如果没有重叠组，则停止
Stop by k ：设置一个 K 并在总聚类低于 K 时停止算法（k mean概念）
其他：所有大小的百分比，最近簇的距离

下面进一步演示这个算法。
第 1 步：初始簇

文章插图

第 2 步：检查数据点1

文章插图

第 3 步：将点 1 和 3 更新到簇 1

文章插图

第 4 步：检查数据点 2，已更新

文章插图

第 5 步：检查数据点3，更新数据点4

文章插图

第 6 步：检查数据点 5，没有重叠点

文章插图

第 7 步：更新质心和边界。第一次迭代结束

文章插图

第 8步：开始第二次迭代，检查组 1 并将点 5 更新为点 1

文章插图

第 9 步：检查数据点 5，不更新任何内容

文章插图

第10步：更新质心和边界，结束第二次迭代

文章插图

簇扩展方法有一种不可避免的情况就是没有重叠点但我们仍然希望将点分组在一起。

文章插图

如果我们根据基本规则停止算法，可能会有太多的簇。所以提供三种可能的解决方案。
Naive：逐渐将所有半径增加一个常数，以便两个最近的簇相互重叠（速度快因为所有组的半径同时增加，但可能会导致偏差）
Approximate：将两个最近的簇组合在一起。（慢但偏差较小，因为其他簇的半径保持不变）
其他：按百分比增加半径，按随机数增加
RVN 算法 - 参数在 RVN 算法中，一些参数需要调整才能找到最佳参数。