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

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

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

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