RVN 一种新的聚类算法( 二 ) _RVN

半径：如果数据集是二维的，会有四个候选半径，分别是x-upperbound_x、x-lowerbound_x、y-upperbound_y、y-lowerbound_y 。我们对选项进行排序，以挑选出最好的选项或根据经验进行选择。
扩展速度：在没有重叠点的情况下，圆圈希望增长多快。
K 的阈值：当总簇数小于 K 时，算法停止。（仅用于“按 K 逻辑停止”）

找到最好的 K与 K means算法相同，我们需要找到最佳 K 。对于任何聚类方法，通常有两种方法可以找到最佳 K 。轮廓系数和平方误差之和（每个点和组质心）。由于我们使用边界框而不是点，直接应用轮廓系数和平方误差之和会导致偏差。
因此在计算轮廓系数和平方误差和时，我们可以为每个点（母点）创建四个额外的点（子点），并将它们分配到与母点相同的组中。子点的坐标是（x，上界y），（x，下界y），（上界x，y）和（下界x，y）。

文章插图

因为子点和母点加在一起可以更好地表示每个母点的大小，所以我们可以通过轮廓系数和平方误差和得到更无偏的 K 。
在深入研究案例之前，让我们再次回到世界地图。
世界地图示例 - RVN除了每个国家的经度和纬度，我们还需要上限和下限。

文章插图

我们在这个例子中跳过了调优K 的部分，因为我们只想展示不同的结果。

文章插图

让我们仔细看看俄罗斯。

文章插图

我们可以看到，俄罗斯现在与周边所有国家都聚集在一起。
家具公司示例现在我们回到最初的家具公司示例，我们有了一个平面图将使用 RVN 对所有家具进行聚类。

文章插图

让我们找到最佳 K

文章插图

结果

文章插图

我们可以看到，虽然有些点非常接近较大的组，因为它们的范围不与较大的组重叠，但它们被认为是不同的簇。
Python 实现以下github地址是 NVR 算法的实现
github/red574890/NVR-algorithm
算法的挑战数据收集：数据收集是该算法中最麻烦的部分，因为需要收集一个点的位置和边界框。
高维：理想情况下，该算法可以在高维空间上实现。但是目前还没有尝试将其应用于超过三个维度的数据。
圆形假设：RVN 假设组扩展为一个圆形，这意味着如果一个簇增长，它将在所有方向上扩展相同的大小。但是，这种假设在某些情况下可能是错误的，如下图所示。

文章插图

直观地说，这些数据应该分为 11 组。

文章插图

但是，由于 x 轴和 y 轴的尺度差异很大（y 范围从 0 到 1000，x 范围从 0 到 50），因此 RVN 算法的结果可能非常违反观察结果。

文章插图

有一种可能的解决方案是标准化 x 范围或 y 范围。这个动作可以保证一个维度比另一个维度扩展得更快。

文章插图

速度表现：不同的分组合并方式会导致算法的速度不同。目前没有最佳方法。
整体性能：该算法在平面图情况下比 DBscan和 K means效果更好。但是目前不知道 RVN 是否会在其他情况下表现更好。
未来这是一种受家具行业平面图启发的全新算法。我真诚地希望我们能继续发展这种特殊的方法；因此，如果有人对改进或实施有任何疑问，请随时与我联系。
该算法由 Ray、Vamshi 和 Noah 创建
本文作者：Ray Hsu

【RVN 一种新的聚类算法】