WIMS'18(Hub在KNN图中的影响)-The Influence of Hubness on NN-Descent

  • hubness（exact入度）比较大的点，最终在nn-descent产生的Kgraph中的召回普遍比较高，hubness比较小的点则说不准，有的召回高，有的召回低。

  • 原因：hubness小的点很快就会从最初的几轮迭代中被驱逐出去，所以后续得到refine的机会也不大，恶性循环。hubness大的点会在大部分点的NN-list里面，所以refine的机会也很大，良性循环。


    image.png
  • 如果采用不同的随机初始化图，hubness比较大的点方差很低，几乎总是高召回，hubness比较小的则方差很高，受随机化的影响比较大。

  • 原因：hubness大的点如何初始化都会在大部分NN-list中，所以召回不大有变化；但是hubness小的点很受初始化出现频率的影响，出现频率高refine的机会也大一些，召回就能相对好一些，反之亦然。


    image.png

    （本文的实验都是基于标准高斯分布实验的，保证一个较高的本征维数）

  • 基于以上两个预实验，作者提出了两个优化nn-descent的方法，一个是在Refine的时候随机把一些hub替换掉随机点，hub是过程中近似估计的；另一个是用更大的K'NN-list，效率换精度。
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容