數據集中的最近鄰居Node.js

Question

我有一個將數據保存到MongoDB的Node.js應用程序。給定一個文檔，我想在數據庫中找到最相似的文檔。

我的想法是實現某種近鄰算法，這需要所有記錄作爲訓練序列，並返回最相似的文檔（包括某種形式的百分比在這兩個文件的相似程度。）

例如有我的數據庫中這些記錄...

{ name: "Bill", age: 10, pc: "Mac",  ip: "68.23.13.8" } 
{ name: "Alice", age: 22, pc: "Windows", ip: "193.186.11.3" } 
{ name: "Bob", age: 12, pc: "Windows", ip: "56.89.22.1" } 

...我想找到最接近的文檔這一

{ name: "Tom", age: 10, pc: "Mac", ip: "68.23.13.10" } 
// algorithm returns "Bill", .76 

是否有任何節點模塊/實現，採取任何類型的對象/參數並返回他們最近的鄰居？

Answer 1

下面是一些示例代碼。它假定您可以對每個請求運行搜索。如果要修改它，請確保所有相似性函數都返回0到1之間的數字。

function tokenize(string) { 
    var tokens = []; 
    for (var i = 0; i < string.length-1; i++) { 
    tokens.push(string.substr(i,2)); 
    } 

    return tokens.sort(); 
} 

function intersect(a, b) 
{ 
    var ai=0, bi=0; 
    var result = new Array(); 

    while(ai < a.length && bi < b.length) 
    { 
    if  (a[ai] < b[bi]){ ai++; } 
    else if (a[ai] > b[bi]){ bi++; } 
    else /* they're equal */ 
    { 
     result.push(a[ai]); 
     ai++; 
     bi++; 
    } 
    } 

    return result; 
} 

function sum(items) { 
    var sum = 0; 
    for (var i = 0; i < items.length; i++) { 
    sum += items[i]; 
    } 

    return sum; 
} 

function wordSimilarity(a, b) { 
    var left = tokenize(a); 
    var right = tokenize(b); 
    var middle = intersect(left, right); 

    return (2*middle.length)/(left.length + right.length); 
} 

function ipSimilarity(a, b) { 
    var left = a.split('.'); 
    var right = b.split('.'); 

    var diffs = []; 
    for (var i = 0; i < 4; i++) { 
    var diff1 = 255-left[i]; 
    var diff2 = 255-right[i]; 
    var diff = Math.abs(diff2-diff1); 

    diffs[i] = diff; 
    } 

    var distance = sum(diffs)/(255*4); 

    return 1 - distance; 
} 

function ageSimilarity(a, b) { 
    var maxAge = 100; 
    var diff1 = maxAge-a; 
    var diff2 = maxAge-b; 
    var diff  = Math.abs(diff2-diff1); 
    var distance = diff/maxAge; 

    return 1-distance; 
} 

function recordSimilarity(a, b) { 
    var fields = [ 
    {name:'name', measure:wordSimilarity}, 
    {name:'age', measure:ageSimilarity}, 
    {name:'pc', measure:wordSimilarity}, 
    {name:'ip', measure:ipSimilarity} 
    ]; 

    var sum = 0; 
    for (var i = 0; i < fields.length; i++) { 
    var field = fields[i]; 
    var name = field.name; 
    var measure = field.measure; 
    var sim  = measure(a[name], b[name]); 

    sum += sim; 
    } 

    return sum/fields.length; 
} 

function findMostSimilar(items, query) { 
    var maxSim = 0; 
    var result = null; 

    for (var i = 0; i < items.length; i++) { 
    var item = items[i]; 
    var sim = recordSimilarity(item, query); 

    if (sim > maxSim) { 
     maxSim = sim; 
     result = item; 
    } 
    } 

    return result 
} 

var items = [ 
    { name: "Bill", age: 10, pc: "Mac",  ip: "68.23.13.8" }, 
    { name: "Alice", age: 22, pc: "Windows", ip: "193.186.11.3" }, 
    { name: "Bob", age: 12, pc: "Windows", ip: "56.89.22.1" } 
]; 

var query = { name: "Tom", age: 10, pc: "Mac", ip: "68.23.13.10" }; 
var result = findMostSimilar(items, query); 

console.log(result); 

Answer 2

這樣做的直接方法是計算兩個文檔之間的差異，差異越大，距離越大。你可以使用最大可能的差異來標準化diff，它應該給你相對的距離，你可以相互比較。

看看這個問題來計算json文檔上的差異。

Delta encoding for JSON objects