共计 2371 个字符,预计需要花费 6 分钟才能阅读完成。
当咱们须要对数据集进行聚类时,咱们可能首先钻研的算法是 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 算法中,一些参数须要调整能力找到最佳参数。
- 半径:如果数据集是二维的,会有四个候选半径,别离是 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 算法的实现
https://github.com/red574890/…
算法的挑战
数据收集:数据收集是该算法中最麻烦的局部,因为须要收集一个点的地位和边界框。
高维:现实状况下,该算法能够在高维空间上实现。然而目前还没有尝试将其利用于超过三个维度的数据。
圆形假如:RVN 假如组扩大为一个圆形,这意味着如果一个簇增长,它将在所有方向上扩大雷同的大小。然而,这种假如在某些状况下可能是谬误的,如下图所示。
直观地说,这些数据应该分为 11 组。
然而,因为 x 轴和 y 轴的尺度差别很大(y 范畴从 0 到 1000,x 范畴从 0 到 50),因而 RVN 算法的后果可能十分违反察看后果。
有一种可能的解决方案是标准化 x 范畴或 y 范畴。这个动作能够保障一个维度比另一个维度扩大得更快。
速度体现:不同的分组合并形式会导致算法的速度不同。目前没有最佳办法。
整体性能:该算法在平面图状况下比 DBscan 和 K means 成果更好。然而目前不晓得 RVN 是否会在其余状况下体现更好。
将来
这是一种受家具行业平面图启发的全新算法。我真诚地心愿咱们能持续倒退这种非凡的办法;因而,如果有人对改良或施行有任何疑难,请随时与我分割。
https://www.overfit.cn/post/cbf8eaf7ec2c44368bd25db40a6af68d
该算法由 Ray、Vamshi 和 Noah 创立
本文作者:Ray Hsu