Как мне визуализировать кластеры пользователей?

Question

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

Я назначил 2D-точку каждому пользователю (где каждая координата находится между 0 и 1).Моя идея заключается в том, что точки двух пользователей сближаются, когда они взаимодействуют, это "сила притяжения", и я просто снова и снова просматриваю свои журналы взаимодействия.

Конечно, мне нужна "сила отталкивания", которая тоже будет раздвигать пользователей, иначе все они просто сведутся в одну точку.

Сначала я попытался отслеживать самую низкую и самую высокую координаты XY и нормализовать их положение, но это не сработало, несколько пользователей с небольшим количеством взаимодействий остались по краям, а все остальные рухнули в середину.

Кто-нибудь знает, какие уравнения я должен использовать для перемещения точек, как для силы "притяжения" между пользователями при их взаимодействии, так и для силы "отталкивания", чтобы остановить их слияние в одну точку?

Редактировать:Отвечая на вопрос, я должен отметить, что я имею дело примерно с 1 миллионом пользователей и примерно с 10 миллионами взаимодействий между пользователями.Если кто-нибудь может порекомендовать инструмент, который мог бы сделать это за меня, я весь внимание :-)

Answer 1

В прошлом, когда я пробовал подобные вещи, я использовал пружинную модель для объединения связанных узлов вместе, что-то вроде: dx = -k*(x-l). dx является ли изменение положения, x является текущей позицией, l является желаемым разделением, и k это коэффициент пружины, который вы настраиваете до тех пор, пока не получите хороший баланс между прочностью пружины и стабильностью, он будет меньше 0,1.Имея l > 0 гарантирует, что все не окажется посередине.

В дополнение к этому, общая "отталкивающая" сила между всеми узлами распределит их, что-то вроде: dx = k / x^2.Это будет больше, чем ближе расположены два узла, настройте k чтобы получить разумный эффект.

Answer 2

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

Независимо от этой проблемы масштабирования:посмотрите на некоторые стратегии рендеринга в graphviz, в частности на программы "neato" и "fdp".Со справочной страницы:

  neato  draws  undirected graphs using ``spring'' models (see Kamada and
  Kawai, Information Processing Letters 31:1, April 1989).   Input files
  must  be  formatted  in the dot attributed graph language.  By default,
  the output  of  neato  is  the  input  graph  with  layout coordinates
  appended.

  fdp  draws  undirected  graphs using a ``spring'' model. It relies on a
  force-directed approach in the spirit of Fruchterman and Reingold  (cf.
  Software-Practice & Experience 21(11), 1991, pp. 1129-1164).

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

Рассмотрим модель, в которой все будет рано или поздно рухнет, но медленно.Затем просто запускайте до тех пор, пока не будет выполнено какое-либо условие (узел пересекает центр области макета или что-то подобное).

Сопротивление или импульс могут быть просто закодированы как базовое сопротивление движению и сводятся к ограничению движений;это может применяться дифференцированно (объекты могут двигаться медленнее в зависимости от того, как далеко они продвинулись, где они находятся в пространстве, сколько других узлов находятся близко и т.д.).

Надеюсь, это поможет.

Answer 3

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

Кроме того, если у вас нет всего нескольких узлов, я бы сделал это в 3D.Дополнительное измерение свободы позволяет создавать лучшие решения, и вы должны уметь визуализировать кластеры также в 3D, если не лучше, чем в 2D.