Вам нужен алгоритм кластеризации, который автоматически группирует похожих пользователей. Первая трудность, с которой вы сталкиваетесь, заключается в том, что большинство алгоритмов кластеризации ожидают, что элементы, которые они кластеризуют, будут представлены в виде точек в евклидовом пространстве. В вашем случае у вас нет координат точек. Вместо этого вы можете вычислить значение функции «сходство» между их парами.
Одной из хороших возможностей здесь является использование спектральной кластеризации , которая нуждается именно в том, что у вас есть: матрице подобия. Недостатком является то, что вам все еще нужно вычислить функцию совместимости для каждой пары точек, т.е. е. алгоритм O (n ^ 2).
Если вам абсолютно необходим алгоритм быстрее, чем O (n ^ 2), то вы можете попробовать подход, называемый пространствами различий . Идея очень проста. Вы инвертируете свою функцию совместимости (например, взяв ее в обратную сторону), чтобы превратить ее в меру отличия или расстояния. Затем вы сравниваете каждый элемент (в вашем случае пользователь) с набором элементов-прототипов и рассматриваете полученные расстояния как координаты в пространстве. Например, если у вас есть 100 прототипов, то каждый пользователь будет представлен вектором из 100 элементов, т.е. е. точкой в 100-мерном пространстве. Тогда вы можете использовать любой стандартный алгоритм кластеризации, такой как K-means .
Вопрос теперь в том, как вы выбираете прототипы и сколько вам нужно. Были испробованы различные эвристики, однако здесь есть диссертация , в которой утверждается, что случайного выбора прототипов может быть достаточно. Это показывает эксперименты, в которых использование 100 или 200 случайно выбранных прототипов дало хорошие результаты. В вашем случае, если у вас есть 1000 пользователей, и вы выбираете 200 из них в качестве прототипов, то вам нужно будет оценить вашу функцию совместимости 200 000 раз, что является улучшением в 2,5 раза по сравнению со сравнением каждой пары. Однако реальным преимуществом является то, что для 1 000 000 пользователей 200 прототипов все еще будет достаточно, и вам нужно будет выполнить 200 000 000 сравнений, а не 500 000 000 000 улучшений с коэффициентом 2500. В результате получается алгоритм O (n), лучше, чем O (n ^ 2), несмотря на потенциально большой постоянный коэффициент.