解決復(fù)雜數(shù)據(jù)最近鄰問題的通用方法

如果你打算開一家咖啡館，你一定想知道：“附近最近的一家咖啡館在哪？”了解這些信息有助于應(yīng)對(duì)商業(yè)競(jìng)爭(zhēng)。

這種現(xiàn)象是計(jì)算機(jī)科學(xué)中廣泛研究的問題，稱為“最近鄰搜索”。它的問題是，給定數(shù)據(jù)集和新的數(shù)據(jù)點(diǎn)，數(shù)據(jù)集中哪個(gè)數(shù)據(jù)離新數(shù)據(jù)點(diǎn)最近？這個(gè)問題出現(xiàn)的場(chǎng)景非常豐富，可以是基因搜索、圖像查詢，或者音樂推薦。

但是最近鄰問題并不像咖啡館那么容易解決。過去幾十年，很多計(jì)算機(jī)科學(xué)家都在致力于尋找更好的解決辦法。與此同時(shí)，他們還要解決隨之而來的復(fù)雜情況，例如不同數(shù)據(jù)集對(duì)“相近”有著不同的定義。

現(xiàn)在，一個(gè)五人小組提出了開創(chuàng)性的解決辦法，他們?cè)趦善撐闹校ㄒ黄延?月發(fā)表，另一篇還未出爐）提出了解決復(fù)雜數(shù)據(jù)最近鄰問題的通用方法。

麻省理工學(xué)院的計(jì)算機(jī)科學(xué)家、最近鄰搜索領(lǐng)域的重要任務(wù)Piotr Indyk表示：“這是首個(gè)用單一算法捕捉大量空間的結(jié)果?！?/p>

不同的距離

我們已經(jīng)習(xí)慣了用一種方法定義距離，常常會(huì)忽視其他方式。通常，我們用“歐幾里得距離”測(cè)量距離，即在兩點(diǎn)之間測(cè)量直線的距離。但在有些情況下，這樣的測(cè)量方式就說不通了。例如在街道網(wǎng)格中，就需要用到“曼哈頓距離”了，直線距離5英里的目的地，可能需要走3英里之后轉(zhuǎn)90°，再繼續(xù)走4英里才能到達(dá)。

另外，還可以用非地理的術(shù)語表示距離。比如Facebook上的兩名用戶、兩部電影、兩組基因之間的距離怎么計(jì)算？在這些問題上，“距離”表示的是兩個(gè)物體之間的相似程度。

有關(guān)距離的測(cè)量尺度有很多，例如兩組基因，生物學(xué)家會(huì)用“編輯距離（edit distance）”來比較二者。這樣一來，兩組基因序列之間的距離就是從一組基因轉(zhuǎn)換到另一組所需要添加、刪除、插入、替換的數(shù)字。

編輯距離和歐幾里得距離是兩種完全不同的距離測(cè)量方法，二者是不能相互替代的。但是這樣的情況對(duì)研究最近鄰算法的科學(xué)家們來說很棘手，能有效計(jì)算一種距離的算法在另一種情況下就無法工作了。

在夾縫中求生存

為了找到最近鄰，通常所用的方法是將數(shù)據(jù)分成好幾份。假設(shè)你的數(shù)據(jù)就像在牧場(chǎng)中吃草的奶牛，給分散在草場(chǎng)中的牛群畫不同的圓圈，現(xiàn)在進(jìn)來了一頭新奶牛，問它會(huì)落在哪個(gè)圓圈里？可以肯定的是，這頭新奶牛的最近鄰一定也在這個(gè)圈里。

然后重復(fù)這一過程，不斷進(jìn)行細(xì)分。最終會(huì)得到一個(gè)只包含兩頭牛的區(qū)域，這樣就找到了最近鄰。

現(xiàn)在，算法能夠完成這一過程，好的算法還會(huì)將這一任務(wù)完成得又快又好。這里“好”的標(biāo)準(zhǔn)可以理解成，算法不會(huì)得出最近鄰與新數(shù)據(jù)不在一個(gè)圈子里的結(jié)果。

近些年來，科學(xué)家們提出了多種分割數(shù)據(jù)的算法。對(duì)于低維數(shù)據(jù)（即每個(gè)數(shù)據(jù)點(diǎn)僅由少量的值定義，例如牧場(chǎng)中牛的位置），算法在解決最近鄰問題時(shí)會(huì)生成Voronoi圖。

對(duì)于高維數(shù)據(jù)（每個(gè)數(shù)據(jù)點(diǎn)可能有成百上千個(gè)值），Voronoi圖要計(jì)算起來就十分費(fèi)力了。所以科學(xué)家們用“局部敏感哈希（LSH）算法”對(duì)數(shù)據(jù)進(jìn)行分割，這種算法于1998年由Indyk和Rajeev Motwani共同提出。LSH算法是隨機(jī)對(duì)數(shù)據(jù)進(jìn)行分類的，這使得它速度很快，但精確度較低。算法最終并不是找到確切的最近鄰點(diǎn)，而是告訴你最近鄰與已有數(shù)據(jù)的確切距離。（可以想象成在電影推薦時(shí)，推薦結(jié)果并不是最佳的，而是那些還不錯(cuò)的。）

上世紀(jì)90年代末，計(jì)算機(jī)科學(xué)家們提出的LSH算法以特殊的距離尺度對(duì)最近鄰問題給出大致的解決方案。這些LSH算法都非常具體，無法通用。

“你可以為歐幾里得距離或曼哈頓距離設(shè)計(jì)非常高效的算法。但是我們沒有一種技術(shù)能在多種距離上通用，”Indyk說道。

受制于這種困境，科學(xué)家們想了一種應(yīng)變方法：通過嵌入，在沒有好的算法的距離標(biāo)準(zhǔn)之上“覆蓋”一種距離尺度。但是這樣的結(jié)果往往不準(zhǔn)確，有的時(shí)候嵌入根本無法完成。所以他們?nèi)孕枰氤鲆环N合適的通用方法。

驚人的結(jié)果

在這項(xiàng)新研究開始之際，科學(xué)家們回過頭思考當(dāng)初具體的最近鄰算法追求的目標(biāo)是什么。他們提出了一個(gè)更寬泛的問題：對(duì)距離尺度來說，阻礙一款好的最近鄰算法出現(xiàn)的原因是什么？

他們想原因可能與在尋找最近鄰時(shí)復(fù)雜的“擴(kuò)展圖（expander graph）”有關(guān)。擴(kuò)展圖是一群由線條連接起來的點(diǎn)。這些圖都有它們自己的距離尺度，圖中兩點(diǎn)之間的距離是你從一點(diǎn)到另一點(diǎn)所經(jīng)過的最少線段?？梢詫⑵湎胂蟪缮缃?a href="http://wenjunhu.com/v/tag/1722/" target="_blank">網(wǎng)絡(luò)中的各種人脈關(guān)系。

擴(kuò)展圖有兩個(gè)明顯矛盾的特點(diǎn)：它聯(lián)系廣泛，所以如果想切斷與某一點(diǎn)的聯(lián)系，就要切斷之間的線段。但同時(shí)，大多數(shù)點(diǎn)都和其他的點(diǎn)相連。所以，最終有些點(diǎn)會(huì)越來越遠(yuǎn)。

這樣的特征造成的結(jié)果是，在擴(kuò)展圖上可以很快地進(jìn)行最近鄰搜索，而將數(shù)據(jù)點(diǎn)分割的過程可以看成將最近的兩點(diǎn)分開。

“任何分割擴(kuò)展圖的方法都會(huì)切斷很多線，分開很多相近的點(diǎn)，”論文作者之一Waingarten說道。

從左至右：Alexandr Andoni、Ilya Razenshteyn、Erik Waingarten

2016年夏天，Andoni、Nikolov、Razenshteyn和Waingarten認(rèn)為，是不可能存在對(duì)最近鄰算法有效的擴(kuò)展圖的。但他們真正想證明的是，好的最近鄰算法同樣也不存在于其他距離尺度中。

他們證明的方法是在這些距離尺度中嵌入擴(kuò)展尺度。這樣一來，他們可以確定這些尺度有類似擴(kuò)展圖的無法工作的特征。

這四位科學(xué)家找到普林斯頓大學(xué)的Assaf Naor，他是一名數(shù)學(xué)家，同時(shí)也是計(jì)算機(jī)科學(xué)家，此前的研究非常適合回答有關(guān)擴(kuò)展圖的問題。他們?cè)儐柫擞嘘P(guān)擴(kuò)展圖嵌入到其他距離類型中的問題，但答案并非所期望的那樣，Assaf給出了完全相反的回答。

Naor證明，擴(kuò)展圖并不能嵌入到多種距離尺度中，研究者將這一論斷作為基礎(chǔ)，接著這個(gè)邏輯鏈條開始思考：如果擴(kuò)展圖不能嵌入到其他尺度，那么一個(gè)好的數(shù)據(jù)分割方法一定存在（因?yàn)樗麄冏C明擴(kuò)展圖的特征是阻礙良好數(shù)據(jù)分割的障礙）。因此，良好最近鄰算法可能存在。

他們將發(fā)現(xiàn)結(jié)果寫在第一篇論文中，而第二篇論文本月也即將發(fā)表。Waingarten表示：“第一篇論文證明了確實(shí)存在一種方法能良好地進(jìn)行數(shù)據(jù)分割，但沒有給出如何快速完成的方案。在第二篇論文中會(huì)詳細(xì)解釋。”

同時(shí)，這項(xiàng)新研究第一次用通用的方法對(duì)高維數(shù)據(jù)進(jìn)行最近鄰搜索?！叭魏纬叨瓤臻g都可以用該算法實(shí)現(xiàn)最近鄰搜索，”Waingarten說。