HIBOG: Improving the clustering accuracy by amelioratingdataset with gravitation

• 论文链接
• 总结
• 优点
• 方法
• • 思路
  • 做法
  • • 物体移动
    • 计算重力
    • 优化
    • 注意点

论文链接

总结

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

优点

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

方法

思路

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

做法

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

物体移动

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

这个公式是物理学中位移的公式，而在这篇文章中，将 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 =21​F 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​ ​越大，即物体有向距离更近点移动的趋向。

优化

有时可能只移动一次不足以将数据集变得适合聚类，所以可以进行多次移动：

其中 d d d为移动次数。

注意点

每次移动后，常数 G G G还有每个点的近邻会改变，所以移动过后需要重新计算。
对于超参 d d d和 T T T，虽然设置得越大，数据会越适合于聚类，但是如果太大的话会导致失去原本数据的信息。文中建议是 d ≤ 10 、 T ≤ 0.5 d\leq10、T\leq0.5 d≤10、T≤0.5。

BS3_1 12th