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

Question

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

Я назначил двумерную точку каждому пользователю (где каждая координата находится между 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.