KMeans文档聚类python实现

KMeans是聚类中常用的一种方法，原理简单，速度快,缺点是必须确定聚类的数目k。
在文本聚类中，一般将每个词算作一个单独的特征，所以特征数目是很大的。如果将文档名作为行，词作为列，通常这个文档-词矩阵是很稀疏的。在K-Means计算中，需要把一个文档的所有词表示成向量，其元素是词的权重(tf-idf等)，元素的index是词的索引。在python里，这个向量最好用dict来表示，这样可以避免因矩阵稀疏而存储太多的0。
在<<集体智慧编程>>第三章里有KMeans的python实现，但这个实现有几个缺点：
a. 词向量是用list存的，文档数目一大很容易内存不足(存储太多无用的0)
b. 每个文档词向量的模(cosine的分母)没有提前计算，而是在循环中重复计算

下边是改后的程序，我的输入是一个文件夹，里边每个文件为一个文档，文件名是文档编号.txt(如1.txt), 内容是(词:tfidf值),如:
演讲 0.375399
励志 0.337192
马云 0.242213

from PIL import Image,ImageDraw
import os, codecs, random
from math import sqrt
#Kmeans聚类，sparse matrix 实现
#保存row的模
row_norms={}
def readfile(dirname):
    rows={}
    for f in os.listdir(dirname):
        fr=codecs.open(dirname+f, 'r', encoding='utf-8')
        #mod=0
        tw_dict={}
        norm=0
        for line in fr:
            items=line.split('\t')
            token=items[0].strip()
            #一个中文字符，舍弃
            if len(token)<2:
                continue
            w=float(items[1].strip())
            norm+=w**2
            tw_dict[token]=w
#取出文档编号
        rows[int(f[:-4])]=tw_dict
        row_norms[int(f[:-4])]=sqrt(float(norm))
    print len(rows)
    return rows
        #vector_norm[f]=math.sqrt(norm)
#向量模
def norm(vec):
    return sqrt(sum([pow(v,2) for k, v in vec.items()]))
#v1: row, norm_v1: row的norm; v2:聚类中心点， norm_v2:中心点的norm
def cosine(v1, norm_v1, v2, norm_v2):
    # 交集w乘积
    if norm_v1==0 or norm_v2==0:
        return 1.0
    dividend=0
    #sum1Sq=0
    for k, v in v1.items():
        if k in v2:
            dividend+=v*v2[k]
        #sum1Sq+=pow(v, 2)

    # Sums of the squares
    #sum2Sq=sum([pow(v,2) for k, v in v2.items()])
    #if sum1Sq==0 or sum2Sq==0:
        #return 1.0
    #else:
    return 1.0-dividend/(norm_v1*norm_v2)

#计算数据各个维度的限制
def rows_range(rows):
    tokens={}
    for k, tw in rows.items():
        for t, w in tw.items():
            if t not in tokens:
                tokens[t]=[]
            tokens[t].append(w)
    res={}
    for t, wl in tokens.items():
        res[t]=(min(wl), max(wl))
    return res

#生成随机初始点
def random_vec(ranges):
    res={}
    for k, v in ranges.items():
        res[k]=random.random()*(v[1]-v[0])+v[0]
    return res

#计算类中心
def center(clust, rows):
    res={}
    s=len(clust)
    for c in clust:
        for k, v in rows[c].items():
            if not k in res:
                res[k]=0.0
            res[k]+=v
    for k, v in res.items():
        res[k]=v/s
    return res

def kcluster(rows,distance=cosine,k=4):
    # Determine the minimum and maximum values for each point
    ranges=rows_range(rows)
    # Create k randomly placed centroids
    clusters=[]
    for i in range(k):
        clusters.append(random_vec(ranges))

    clusteres_norm=[]
    for i in range(k):
        clusteres_norm.append(norm(clusters[i]))
    lastmatches=None
    for t in range(20):
        print 'Iteration %d' % t
        bestmatches=[[] for i in range(k)]

        # Find which centroid is the closest for each row
        for j in rows.keys():
            #print 'iter row:', j
            row=rows[j]
            row_norm=row_norms[j]
            bestmatch=0
            min_dis=9999999
            for i in range(k):
                d=distance(row, row_norm, clusters[i],clusteres_norm[i])
                if d<min_dis:
                    bestmatch=i
                    min_dis=d
            bestmatches[bestmatch].append(j)

        # If the results are the same as last time, this is complete
        if bestmatches==lastmatches:
            break
        lastmatches=bestmatches

        # Move the centroids to the average of their members

        for i in range(k):
            clusters[i]=center(bestmatches[i], rows)

    return bestmatches

if __name__ == '__main__':
    corpus_dir='D:/python_workspace/corpus_res2/sigram/'
    rows=readfile(corpus_dir)
    print 'create vectorspace'
    n=29
    clust=kcluster(rows,k=n)
    fw=open('D:/python_workspace/corpus_res2/kmeans_'+str(n)+'.txt', 'w')
    for c in clust:
        fw.write('%s\n' % ','.join([str(v) for v in c]))