Clustering using k-means in python

Since the data you have is binary and sparse (in particular, not all users have tagged all documents, right)? So I'm not at all convinced that k-means is the proper way to do this.

Anyway, if you want to give k-means a try, have a look at the variants such as k-medians (which won't allow "half-tagging") and convex/spherical k-means (which supposedly works better with distance functions such as cosine distance, which seems a lot more appropriate here).

As mentioned by @Jacob Eggers, you have to denormalize the data to form the matrix which is a sparse one indeed. Use SciPy package in python for k means. See

Scipy Kmeans

for examples and execution. Also check Kmeans in python (Stackoverflow) for more information in python kmeans clustering.

First you need to denormalize the data so that you have one file like this:

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

Then you need to loop through the k-means algorithm. Here is matlab code from the ml-class:

% 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

For sparse k-means, see the examples under scikit-learn clustering.
About how many ids are there, how many per user on average, how many clusters are you looking for ? Even rough numbers, e.g. 100k ids, av 10 per user, 100 clusters, may lead to someone who's done clustering in that range (or else to back-of-the-envelope "impossible").

MinHash may be better suited for your problem than k-means; see chapter 3, Finding Similar Items, of Ullman, Mining Massive Datasets;
also SO questions/tagged/similarity+algorithm+python.