Кластеризация с использованием k-средних в Python

Question

У меня есть документ d1, состоящий из строк вида user_id tag_id.Есть еще один документ d2, состоящий из tag_id tag_name, который мне нужен для генерации кластеров пользователей с похожим поведением тегов.Я хочу попробовать это с алгоритмом k-средних в Python.Я совершенно новичок в этом и не могу понять, с чего начать.Кто-нибудь может дать какие-нибудь указатели?

Нужно ли сначала создавать разные документы для каждого пользователя, используя d1 со своим словарем тегов?И затем применить алгоритм k-средних на эти документы?В d1 около 1 миллиона пользователей.Я не уверен, что я думаю в правильном направлении, создавая 1 миллион файлов?

Answer 1

Поскольку ваши данные являются двоичными и разреженными (в частности, не все пользователи пометили все документы, верно)?Так что я совсем не уверен, что k-means - правильный способ сделать это.

В любом случае, если вы хотите попробовать k-means, взгляните на варианты, такие как k-медианы (которые не допускают "полу-пометки") и выпуклые / сферические k-средства (которые предположительно работают лучше с функциями расстояния, такими как косинусное расстояние, которое кажется здесь более подходящим).

Answer 2

Как упомянул @Jacob Eggers, вы должны денормализовать данные, чтобы сформировать матрицу, которая действительно является разреженной. Используйте пакет SciPy в Python для k означает. Смотри

Scipy Kmeans

за примеры и исполнение. Также проверьте Kmeans в Python (Stackoverflow) для получения дополнительной информации о кластеризации Python Kmeans.

Answer 3

Для разреженных k-средних см. Примеры под scikit-Learn кластеризация .
О том, сколько существует идентификаторов, сколько на пользователя в среднем, сколько кластеров вы ищете? Даже грубые цифры, например 100 тыс. Идентификаторов, av 10 на пользователя, 100 кластеров, может привести к тому, кто сделал кластеризацию в этом диапазоне (или иначе "невозможного").

MinHash может быть лучше подходит для вашей проблемы, чем K-средства; см. главу 3 «Поиск похожих предметов», Ullman, Наборы горных массивов ;
также SO вопросов / с тегами / сходство + алгоритм + python .

Answer 4

Сначала вам нужно денормализовать данные, чтобы у вас был один файл, подобный этому:

userid tag1 tag2 tag3 tag4 ....
0001   1    0    1    0    ....
0002   0    1    1    0    ....
0003   0    0    1    1    ....

Тогда вам нужно перебрать алгоритм k-средних. Вот код matlab из класса ml:

% Initialize centroids
centroids = kMeansInitCentroids(X, K);
for iter = 1:iterations
    % Cluster assignment step: Assign each data point to the
    % closest centroid. idx(i) corresponds to cˆ(i), the index 
    % of the centroid assigned to example i
    idx = findClosestCentroids(X, centroids);

    % Move centroid step: Compute means based on centroid
    % assignments
    centroids = computeMeans(X, idx, K);
end