使用Python进行k-means聚类

Question

我有一个文档d1，其中包含以"user_id tag_id"的格式构成的行。还有另一个文档d2，其中包含“tag_id tag_name”。 我需要生成具有相似标记行为的用户群集。我想在Python中使用k-means算法尝试此操作。 我完全不了解这个操作，不知道如何开始实施。有没有人可以提供任何指针？

我需要先使用用户的标记词汇从d1中创建不同的文档，然后对这些文档应用k-means算法吗？d1中有约一百万个用户。我不确定自己的想法是否正确，是否需要创建一百万个文件？

- Maxwell

Answer 1

由于您拥有的数据是二进制和稀疏的（特别是，不是所有用户都对所有文档进行了标记），所以我并不认为k-means是处理这种数据的适当方法。

无论如何，如果您想尝试一下k-means，请查看其变体，例如k-medians（它不允许“半标记”）和凸/球形k-means（据说与余弦距离等距离函数效果更好，在这种情况下似乎更加合适）。

- Has QUIT--Anony-Mousse

Answer 2

正文：

正如 @Jacob Eggers 所提到的，你必须对数据进行去规范化处理，以形成稀疏矩阵。在 Python 中使用 SciPy 包进行 k 均值聚类。请参见 Scipy Kmeans 中的示例和执行步骤。

此外，还可以查看 Kmeans in python (Stackoverflow) 了解更多有关 Python k 均值聚类的信息。

- sravan_kumar

Answer 3

首先，您需要对数据进行去规范化处理，以便您有一个类似于这样的文件：

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

然后您需要循环执行k-means算法。这里是来自ml-class的matlab代码：

% 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

- Jacob Eggers

Answer 4

关于稀疏k-means，请参见scikit-learn clustering下的示例。
有多少个ID，每个用户平均有多少个，您要寻找多少个聚类？即使是粗略的数字，例如100k个ID，每个用户平均10个，100个聚类，也可能会引导到那些在该范围内进行过聚类的人（否则就是“不可能”的背信弃义）。

MinHash可能比k-means更适合您的问题；请参见Ullman, Mining Massive Datasets的第3章“查找相似项”；
还可以参考SO questions/tagged/similarity+algorithm+python。

- denis