1

データを MongoDB に保存する Node.js アプリケーションがあります。1 つの文書が与えられた場合、データベース内で最も類似した文書を見つけたいと考えています。

私の考えは、すべてのレコードをトレーニング シーケンスとして取得し、最も類似したドキュメント (これら 2 つのドキュメントがどの程度類似しているかについてのパーセンテージを含む) を返す、ある種の最近傍アルゴリズムを実装することです。

たとえば、データベースにこれらのレコードがある...

{ 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

任意の種類のオブジェクト/パラメーターを取り、最も近い隣人を返す Node モジュール/実装はありますか?

4

2 に答える 2

2

ここにいくつかのコード例があります。すべてのリクエストで検索を実行できることを前提としています。変更する場合は、すべての類似度関数が 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);
于 2013-01-15T00:09:27.747 に答える
0

これを行う簡単な方法は、2 つのドキュメント間の差分を計算することです。差分が大きいほど、距離が大きくなります。可能な最大差分を使用して差分を正規化できます。これにより、相互に比較できる相対距離が得られます。

この質問を見て、json ドキュメントの差分を計算してください。

JSON オブジェクトのデルタ エンコーディング

于 2013-01-14T22:11:18.953 に答える