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

  • hubness（exact入度）比較大的點，最終在nn-descent產(chǎn)生的Kgraph中的召回普遍比較高，hubness比較小的點則說不準，有的召回高，有的召回低。

  • 原因：hubness小的點很快就會從最初的幾輪迭代中被驅(qū)逐出去，所以后續(xù)得到refine的機會也不大，惡性循環(huán)。hubness大的點會在大部分點的NN-list里面，所以refine的機會也很大，良性循環(huán)。


    image.png
  • 如果采用不同的隨機初始化圖，hubness比較大的點方差很低，幾乎總是高召回，hubness比較小的則方差很高，受隨機化的影響比較大。

  • 原因：hubness大的點如何初始化都會在大部分NN-list中，所以召回不大有變化；但是hubness小的點很受初始化出現(xiàn)頻率的影響，出現(xiàn)頻率高refine的機會也大一些，召回就能相對好一些，反之亦然。


    image.png

    （本文的實驗都是基于標準高斯分布實驗的，保證一個較高的本征維數(shù)）

  • 基于以上兩個預實驗，作者提出了兩個優(yōu)化nn-descent的方法，一個是在Refine的時候隨機把一些hub替換掉隨機點，hub是過程中近似估計的；另一個是用更大的K'NN-list，效率換精度。
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容