Laboratory of Mathematical Logic at PDMI

Пятница, 20 апреля, комната 106. Начало в 15:30.

Докладчик: Ю. Лифшиц.

Тема: Алгоритмы поиска ближайших соседей.

Abstract

Абстрактно, задачу о ближайших соседях можно сформулировать следующим образом. Есть некоторое пространство с метрикой близости. Нам дана большая коллекция элементов этого пространства. Требуется провести такие предварительные вычисления, чтобы при получении нового элемента как можно быстрее определить его ближайшего соседа в нашей коллекции. Алгоритмы поиска ближайших соседей играют важнейшую роль в классификации текстов, распознавании образов, рекомендующих системах и системах размещения интернет-рекламы.

В рамках доклада будут кратко представлены основные подходы к решению задачи о ближайших соседях. Далее, мы рассмотрим новый метод, основанный на предположении, что каждая пара ближайших соседей имеет общий редкий признак. Затем будет представлен новый метод вероятностного анализа задачи о ближайших соседях. В конце доклада будет объявлен список открытых проблем и направлений для дальнейших исследований.