Flattening the Density Gradient for Eliminating Spatial Centrality to Reduce Hubness
Flattening the Density Gradient for Eliminating Spatial Centrality to Reduce Hubness
复制标题
DOI：
10.1609/aaai.v30i1.10240
复制
发表时间：
2016-02
期刊：
影响因子：
--
通讯作者：
Kazuo Hara;Ikumi Suzuki;Kei Kobayashi;K. Fukumizu;Miloš Radovanović
中科院分区：
文献类型：
--
作者：
Kazuo Hara;Ikumi Suzuki;Kei Kobayashi;K. Fukumizu;Miloš Radovanović
空间中心性，即离数据集中心越近的样本往往离所有其他样本越近，被认为是中心性的一个来源。众所周知，Hubness会降低k-近邻(k-NN)分类。在使用内积相似性的情况下，可以通过居中来消除空间中心性，即，将原点移动到数据集的全局中心。然而，当使用欧几里得距离时，居中对空间中心性没有影响，因为居中前后样本之间的距离是相同的。如本文所述，当考虑欧氏距离时，我们提出了一种解决轮毂问题的方法。我们提供了一个理论解释来演示该解决方案如何消除空间中心性和降低中心性。然后，我们从密度梯度的角度讨论了所提出的解决方案可行的原因，密度梯度被认为是空间中心性和集中性的起源。我们证明了该解对应于使密度梯度变平。使用真实世界的数据集，我们证明了所提出的方法提高了k-NN的分类性能，并且优于现有的集线器约简方法。
Spatial centrality, whereby samples closer to the center of a dataset tend to be closer to all other samples, is regarded as one source of hubness. Hubness is well known to degrade k-nearest-neighbor (k-NN) classification. Spatial centrality can be removed by centering, i.e., shifting the origin to the global center of the dataset, in cases where inner product similarity is used. However, when Euclidean distance is used, centering has no effect on spatial centrality because the distance between the samples is the same before and after centering. As described in this paper, we propose a solution for the hubness problem when Euclidean distance is considered. We provide a theoretical explanation to demonstrate how the solution eliminates spatial centrality and reduces hubness. We then present some discussion of the reason the proposed solution works, from a viewpoint of density gradient, which is regarded as the origin of spatial centrality and hubness. We demonstrate that the solution corresponds to flattening the density gradient. Using real-world datasets, we demonstrate that the proposed method improves k-NN classification performance and outperforms an existing hub-reduction method.