алгоритм n-мерного соответствия

Question

Нужен совет здесь. Кто-нибудь знает хорошее место, чтобы начать искать алгоритм сопоставления в n-мерном пространстве. Например, любой сайт знакомств должен использовать какой-то алгоритм для соответствия 2 человек. Я прочитал, что мы можем отобразить характеристики человека в n-мерном массиве с системой точек для каждой характеристики. Когда у нас есть все (доступные) характеристики человека, мы можем представить его в точке в n-мерном массиве. Тогда сопоставить 2 человека будет так же просто, как найти кратчайшее расстояние между 2 точками в этом массиве n-dim. У кого-нибудь есть ссылки на реализацию такого рода алгоритма? На каком языке лучше всего писать такие вещи?

Answer 1

Если вы хотите найти наиболее близкое совпадение для одного человека, Bentley & Shamos опубликовал многомерный метод «разделяй и властвуй»: разделяй и властвуй за время O (N log N): Делите и - победить в многомерном пространстве в материалах восьмого ежегодного симпозиума ACM по теории вычислений 1976. Если вы не можете получить копию , это также может быть полезно.

Однако для вашего примера приложения поиск ближайшего соседа, похоже, не самая большая проблема - гораздо сложнее отобразить входные данные в измерения. Например, если одно измерение «любит животных», какую ценность вы придаете тому, кто любит собак и кошек, но не выносит лошадей? А как насчет того, кто любит лошадей, думает, что с собаками все в порядке, раздражен кошками и имеет двойственное отношение к золотой рыбке?

Answer 2

Как насчет следующего решения.

Предположим, что пользователями являются U1, U2, U3, U4, U5 .... Un. Атрибуты А1, А2, А3, А4, А5 ..... Am

Храните их как

A1 - U1, U2, U3 ... A2 - U4, U6, U7 .... A3 -

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

Answer 3

Процесс, который вы упоминаете, известен как k-ближайший сосед, с k = 1. Это наиболее интуитивный подход для поиска похожих векторов.

http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm

Answer 4

Прежде всего, выберите язык, с которым вы наиболее знакомы. Алгоритмы для обработки этого довольно просты, и должны работать на любом современном языке. (Пока есть некоторая концепция массива и, возможно, матричной библиотеки, у вас все должно быть в порядке.) Я уже реализовал многие из них в C, C ++ и C #, но видел реализации в python, vb.net и т. Д. .

В зависимости от того, что вы пытаетесь сделать, есть несколько вариантов.

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

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

Answer 5

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

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