Метрическое пространство для k-nearest neighbors?

Question

[floppa322]

Пример: пусть есть видеохостинг и требуется выдать пользователю релеватные видеозаписи.
Например, у видеозаписи есть 4 параметра (ниже в квадтратных скобках диапазон значений):
1. Количество просмотров на ед. времени [0, V]
2. Жанр видео (в непрерывной форме, что бы это не означало) [0, U]
3. Длительность видео [0, K]
4. Абс. количество лайков [0, Z]
Значение этих 4-х параметров нормировали от 0 до 1. Видеозаписи разместили в 4-D пространстве с евклидовой метрикой, где координата видео зависит от его 4-х вышеуказанных параметров.
Зайдя на главную страницу видеохостинга, пусть у пользователя есть история о его просмотрах и к пользователю прикреплены 2 из 4-х параметров, которые есть у видео, а именно:
1. Усредненный жанр ранее просмотренных видео - X1
2. Усреднённая длительной просмотра видео - X2
Теперь требуется выдать пользователю k релевантных видео: делаем запрос к нашему ранее построенному пространству getKNearestBeighbors(1, X1, X2, 1). Иными словами координаты "интересов" пользователя это (1, X1, X2, 1): первая единица - передаём всегда макс. 1-й параметр видео, передаём значение 2-го параметра равное этому же параметру, но у пользователя, передаём значение 3-го параметра равное этому же параметру но у пользователя и передаём макс. значение для 4-го параметра. То есть 2 параметра всегда выбираем максимальными, а другие 2 - в зависимости от пользователя

Тут можно было бы ещё приписать каждому из 4-х параметров видео коэффициент-вес (такой что сумма всех коэффициентов для каждого параметра равна 1) определяющий степень "значимости" параметра

Вопрос: а если для разных n-мерных кубов (вырезок из целого n-мерного куба, множеств значений из n параметров) будут разные коэффициенты-веса ? Например, в 2-D если бы были параметры рост и вес, то для значений роста [x1, x2] - были бы k1 и k2 (ki + k(i+1) = 1) а для [x3, x4] - k3, k4 и так далее. То какой мат. аппарат понадобится для решения такой задачи ? Самое похожее, что удалось нагуглить это диф. геом. и геом. многообразий

Answer 1

[dmshar]

Теоретически может использоваться любая функция, которая удовлетворяет аксиомам метричности (тождества, положительности, симметричности, треугольника). Которые, в свою очередь, выражают интуитивные представления о понятии "расстояния". Т.е. можно взять любую функцию, проверить, удовлетворяет-ли она указанным аксиомам, и если да - то применять. В данном случае понятия "лучше"-"хуже" нет - этот вопрос выноситься за скобки, и как правило является предметом исследования на этапе предварительного анализа задачи.

Наиболее распространенным меры, применяемые в кластерном, классификационном анализе, в задачах распознавания образов и пр. - уже упомянутая вами эвклидова мера (или метрика L2). Ее модификация - квадрат евклидова расстояния. Манхэттенская мера (или метрика L1), мера Махаланобиса, мера Чебышева, мера Хэмминга, косинусная мера (полезная в многомерном пространстве, но в случае, если много параметров могут иметь нулевые значения), ее модификация - "мягкая" косинусная мера, мера Кульбака — Лейблера (если все значения всех признаков положительны и векторы объектов нормированы на единицу ) и пр.

А бывают еще неметрические меры близости. (т.е. случаи кода используется функция, которая нарушает одну из упомянутых выше аксиом). В общем, не советую задавать вопрос в теоретической плоскости типа "какой мат. аппарат понадобится для решения такой задачи", потому как там, в этом аппарате, можно и закопаться :-). Достаточно ознакомиться с такой вот интересной книгой: Деза Е.И., Деза М.-М. Энциклопедический словарь расстояний. Ну и при большом желании все перечисленные выше метрики, их описание и области применения легко гуглятся.

Что до практического использования этого аппарата - такая функция должна подбираться для каждой прикладной задачи отдельно. Это подтверждается успешным использованием в разных прикладных областях различных специфических мер близости - например, мера Левенштейна и мера Джаро — Винклера (используемые при обработке текстов), мера Хаусдорфа (при работе с подмножествами), мера Вассерштейна (применяется в различного рода транспортных задачах и - неожиданно - в обработке изображений, от распознавания рукописных текстов до диагностики по рентгеновским снимкам), и пр. А иногда выбор и обоснование тех или иных мер в конкретной задаче есть предмет научных статей и даже диссертаций.

Comments

[floppa322]

Спасибо за ответ :)

Answer 2

[Griboks]

Предлагаю пойти ещё дальше и определить для вашей некой пока неизвестной функции выбора апостериорные метрики. Тогда на достаточно репрезентативной (большой) выборке можно сделать аппроксимацию функции выбора какой-нибудь известной, например линейной комбинацией ваших n-мерных кубов.

Но есть нюанс...

Строго говоря, придётся всё равно выбрать меру более высокого порядка уже для аппроксимации. Однако, полагая, что чем выше порядок меры тем глаже метрики (и что функция дифференцируема), можно смело сказать, что более высокий порядок меры даст лучшие результаты.

Но мы можем пойти ещё дальше и выполнить оптимизацию (например, градиентным спуском) аппроксимации целевой функции выбора. Для этого придётся определить функции более высокого порядка: меру ошибки и функцию обратного распространения ошибки. Короче, сделать нейросеть.

Останется только одна проблема - удостовериться в оптимальном выборе мер и функций обучения нейросети. Поскольку у вас есть компьютер, то вы можете составить матрицу всевозможных параметров обучения (не модели) и банально проверить все возможные комбинации.

Comments

[floppa322]

Благодарю за ответ :)