Алгоритм - группировка пользователей на основе наиболее схожих предпочтений - PullRequest
Новая
       19

Алгоритм - группировка пользователей на основе наиболее схожих предпочтений

0 голосов
/ 01 октября 2018

Я занимаюсь разработкой приложения, в котором пользователи группируются по командам 'n' на основе набора вопросов, на которые они ответили.Набор вопросов является основным множественным выбором, и каждый пользователь должен ответить на каждый вопрос.

Это жесткие критерии:

  • В каждой группе может быть до 'n' пользователей
  • Каждый пользователь может быть назначен только на 1 команду
  • Каждая команда состоит из пользователей, которые имеют высокое сходство

наборы данных, которые я использую, выглядят следующим образом (я могу изменить это) 

{
 1: { 1: 'a', 2: 'b', 3: 'a', 4: 'c' },
 2: { 1: 'b', 2: 'c', 3: 'b', 4: 'd' },
 3: { 1: 'b', 2: 'a', 3: 'c', 4: 'd' },
 ...
}

ВМоя первая попытка : я создал функцию, которая при задании начального пользователя будет возвращать набор пользователей в порядке сходства.Это работало нормально, но не дает сплошных групп.

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

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

Любые советы или решения по моей проблеме приветствуются.

1 Ответ

0 голосов
/ 03 октября 2018

Это очень сложная проблема, но вот формализация, которая может вам помочь.

Скажем, у вас N пользователей.Вы можете просмотреть их как полный граф из N узлов, где вес ребра (i, j) - это «сходство» пользователей i и j (например, количество общих ответов).Затем вы ищете разбиение вершин на группы размера n, которое максимизирует вес ребра внутри разбиения, то есть разбиение P, максимизирующее

objective function

Это может быть доказано каканалогично минимизации весов между разбиениями.

Это преобразование сводит вашу проблему к нахождению (k, nu) -балансированного разбиения графа.Это сложная проблема, но Сбалансированное разбиение графа , Андреев и Ракке, ACM 2004 предоставляет алгоритм аппроксимации и его детальный анализ сложности.

Вы можете использовать этот алгоритмсо свободным значением nu, получите приблизительный ответ, а затем перебалансируйте пользователей, чтобы получить ровно n в каждой группе.Мы надеемся, что это даст результаты, близкие к оптимальным, но достичь оптимальности будет очень сложно.

...