HIBOG: Improving the clustering accuracy by amelioratingdataset with gravitation论文笔记

2023-11-22 08:48:16

HIBOG: Improving the clustering accuracy by amelioratingdataset with gravitation

论文链接
总结
优点
方法
- 思路
- 做法

论文链接

总结

这篇文章提出了一个类似于物理学中力的概念，它能将拉近相邻点之间的距离，而拉大较远点的距离，使数据集更有利于聚类。

优点

鲁棒性好，对大部分不同分布的数据集都有效；
运行更快
对超参数不敏感。

方法

思路

减小相似点距离，拉大不同点距离。

做法

分为两步，计算重力和移动物体（点）。
文章的想法可以用基础的物理思想概括，即物体的近邻共同为该物体施加一个合力（重力），使它向相似点（即物体的近邻）移动。而在这个过程中，物体自然而然地会远离不相似的点。

物体移动

首先讲物体移动，因为它的形式和物理学中近似，相对更好理解。

这个公式是物理学中位移的公式，而在这篇文章中，将 v 0 v_0 v0设为0， m m m设为1，则得到了位移为：
S ⃗ = 1 2 F ⃗ t 2 \vec S = \frac{1}{2}\vec F t^2 S =21F t2
这里的 F F F就是题目中提到的重力，而 t t t则为超参。

对一个点 i i i来讲，它的新坐标就可以通过原坐标 o ⃗ i \vec o_i o i加上位移 S ⃗ i \vec S_i S i来计算。其中，第三行 T = t 2 2 T=\frac{t^2}{2} T=2t2。第四行的转换是计算“重力部分”的内容。

计算重力

对一个点 i i i，取它的 k k k个最近邻，假设这个最近邻集合为 K K K，根据最近邻与 i i i的距离从小到大排序。此时， i j ij ij代表着离i第 j j j近的节点，其中 i 1 i1 i1为最近的节点。所以，公式中的 j j j是小于等于 k k k的。
上面公式的 F i j F_{ij} Fij,可以理解为是第 j j j近邻对点 i i i施加的力（分力），首先， G G G的表达如下：

其中， o ⃗ \vec o o 代表着该点的特征向量，而 ∣ ∣ ∣ ∣ 2 ||\ ||_2 ∣∣ ∣∣2则代表二范数，这个式子就是求出数据集中各点到其第一近邻的距离的均值，对于固定数据集而言，是一个定值。
而 ∣ ∣ o i 1 ⃗ − o i ⃗ ∣ ∣ 2 ||\vec{o_{i1}} - \vec{o_i}||_2 ∣∣oi1 −oi ∣∣2对于点 i i i而言也是定值，所以无需讨论。
之后的一项 o i 1 ⃗ − o i ⃗ \vec{o_{i1}} - \vec{o_i} oi1 −oi 的结果是向量形式，这一项表示点 i i i移动的方向（向第 j j j近邻移动）
接下来是分母部分，可以看出这是求 i i i点与其第 j j j近邻的距离，当 j j j越大时（距离较远），意味着 F F F就更小，这可以看作是一个加权的方式。
那么合力 F i F_i Fi就可以得出是：

可以看出，距离越近的点 F i j ⃗ \vec{F_{ij}} Fij 越大，即物体有向距离更近点移动的趋向。