I have a Node.js application that saves data to MongoDB. Given one document, I want to find the most similar document in the database.
My idea is to implement some sort of nearest neighbour algorithm that takes all the records as a training sequence and returns the most similar document (including some sort of percentage on how similar these two documents are.)
E.g. having these records in my database...
{ 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" }
...I want to find the closest document to this one
{ name: "Tom", age: 10, pc: "Mac", ip: "68.23.13.10" }
// algorithm returns "Bill", .76
Are there any Node modules/implementations that take any kind of objects/parameters and return their nearest neighbour?
Here is some example code. It assumes that you can run the search on every request. If you want to modify it, make sure that all similarity functions return a number between 0 and 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);
A straightforward way of doing this would be to calculate a diff between the two documents and the larger the diff, the larger the distance. You could normalize the diff using the maximum possible diff which should give you relative distances that you can compare against each other.
Take a look at this question for calculating a diff on json documents.