KNN поиск, растущее множество, произвольная норма - PullRequest
Новая
       9

KNN поиск, растущее множество, произвольная норма

1 голос
/ 17 января 2020

Предположим следующую задачу в E3 с произвольной нормой. Например, используется норма L1 (также применимы Hamming, Karlsruhe, geodesi c, ...). 

namespace {
   typedef boost::tuple<double, double, double> Point;

   double nL1(const Point& p1, const Point& p2) {  //L1 norm, example
        double dx = p1.get<0>() - p2.get<0>();
        double dy = p1.get<1>() - p2.get<1>();
        double dz = p1.get<2>() - p2.get<2>();
        return abs(dx) + abs(dy) + abs(dz);
  }
}

Существует два комплекта A , B . A инициализируется n случайными точками, где n относительно велико (n = 1 * 10 ^ 7 - 1 * 10 ^ 9), B пусто ; см. пример кода: 

int main() {
   using namespace std;
   using namespace boost::lambda;

   vector<Point> A, B;
   int n = 10000000;
   for (int i = 0; i < n; i++)  //Create random points
      A.push_back(boost::make_tuple(rand(), rand(), rand()));

Изначально мы ставим случайную точку от A до B . В упрощенном примере используется первая точка A [0]: 

   B.push_back(A[0]);

Затем для i = 1: n мы повторяем эти шаги:

  • Найти ближайшая точка в B к A [i] в ​​соответствии с заданной нормой 

     B * = argmin(|A[i]-B|)

  • If | B * - A [i] | B (Здесь используется eps = 1,0 * 10 ^ 4).

Для ближайшего поиска, Я использую std :: частичный_сорт. 

   const int k = 1;
   for (int i = 1; i < A.size(); i++) {
       partial_sort(B.begin(), B.begin() + k, B.end(), bind(less<double>(), bind(nL1, _1, A[i]), bind(nL1, _2, A[i])));
       if (nL1(*B.begin(), A[i]) < 1e4) B.push_back(A[i]); //Some threshold, eps=1.0*10^4 
   }
}

B постоянно растет и поиск становится более дорогим ... Повторяется в l oop, это слишком медленно даже для небольших множеств (n = 1 * 10 ^ 6) ... Здесь частичная сортировка неэффективна.

  • Есть ли значительные улучшения в скорости? Конечно, можно использовать наивный подход (но он не быстрее).
  • Как ускорить nn-поиск?

Другая проблема возникает, когда вторая ближайшая точка требуется ...

Нынешние библиотеки поиска k-nn не могут быть использованы из-за произвольной нормы (проблема может быть решена на сфере). Я пытался использовать нано-фланн, но он не поддерживает некоторые спецификации c норм ...

...