stMind

about Tech, Computer vision and Machine learning

pythonとmatplotlibでkmeansクラスタリングを試す

f:id:satojkovic:20130209231743p:plain

kmeansクラスタリングpythonとmatplotlibで試してみました。

kmeansクラスタリングとは、教師なしデータ分類手法の一つ。
始めに、ランダムにk個の重心を配置し、

# ranges: dataの各次元の最小値[i][0]と最大値[i][1]
ranges = [ (min([ d[i] for d in data ]), \
                  max([ d[i] for d in data])) for i in range(len(data[0])) ]
# k random centroids
# 各次元毎に最小値から最大値までの値として生成
centroids = [ [ random.random()*(ranges[i][1] - ranges[i][0])+ranges[i][0] \
                      for i in range(len(data[0])) ] for j in range(k) ]

全データ点を、最も近い重心に割り当てていきます。ここでは、dataのリストのインデックスを、
クラスタ毎にbestmachesに追加することで、これを実現します。

# Find which centroid(centroids[i]) is the closest for each data
for j in range(len(data)):
    dj = data[j]
    bestmatch = 0
    for i in range(k):
        d = self.distance(centroids[i], dj)
        if d < self.distance(centroids[bestmatch], dj):
            # closest cluster number
            bestmatch = i
    # append index j to i(bestmatch) th cluster
    bestmatches[bestmatch].append(j)

クラスタに属する点の平均(mean)を新たにクラスタの重心として、

# move the centroids(centroids[i]) to the mean of their members
for i in range(k):
    mean = [0.0] * len(data[0])
    if len(bestmatches[i]) > 0:
        for data_id in bestmatches[i]:
            for dim in range(len(data[data_id])):
                mean[dim] += data[data_id][dim]
            for j in range(len(mean)):
                mean[j] /= len(bestmatches[i])
            centroids[i] = mean

割り当てに変更が生じなくなるか、一定回数以上となるまでこのプロセスを繰り返します。
一番最初の図は、データ点数が100、クラスタk=5の場合の結果の一例です。

今回試したコード全体は以下のようになってます。