k-means(k-平均法)を実装してみた。

クラスタリング手法の1つ、k-meansを実装してみた。
とても見せられるようなコードではないのだが、一応載せておく。
関数の中に関数を書くのはいいんだろうか。
僕はよく書くのだが…

sample code

#D(data)をk個のクラスタにクラスタリングする。
#初期クラスタCを与えることもできる。
#与えなければ適当に初期クラスタを生成する。
#なお、ベクトル間類似度にはコサイン類似度を用いる。
def kmeans(D, k, simv=nlp.simcos, C=None):
    class Cluster(list):
        def __init__(self, mean=None):
            if mean is not None:
                self.mean = mean
        def setmean(self, m):
            self.mean = m
        def removeall(self):
            del self[:]

    def sim(v1, v2):
        import numpy
        return numpy.dot(v1, v2) / (numpy.sqrt(numpy.dot(v1, v1)) * numpy.sqrt(numpy.dot(v2, v2)))
    def mean(D):#Dの平均値を返す
        import numpy
        if len(D) == 0:#Dが空なら
            return
        else:
            d = len(D[0])
        sum = numpy.zeros(d)
        for i in D:
            sum += i
        return sum / len(D)
    def mofc(C):
        for i in C:
            l = []
            for j in i:
                l.append(D[j])
            if len(i) == 0:
                pass
            else:
                i.setmean(mean(l))
    def argmax(i, C):
        max = -float("inf")
        maxindex = 0
        for j in range(len(C)):
            s = sim(i, C[j].mean)
            if max < s:
                max, maxindex = s, j
        return maxindex
    def initc(self):
        for i in self:
            i.removeall()
    from copy import deepcopy
    import numpy
    if C is None:#初期値が指定されていなければ適当な初期値を
        m = mean(D)
        d = len(D[0])
        l = m / k
        M = []
#        for i in range(k):
#            M.append(numpy.random.random_sample(d))
        for i in range(k):
            M.append(l*(i+1))
        C = []#初期クラスタを生成
        for i in M:
            C.append(Cluster(i))
    oldC = None
    step = 0
    #以下k-meanのアルゴリズム
    while oldC != C:
        #前のCをoldCへ
        oldC = deepcopy(C)
        #Cを初期化
        initc(C)
        for i in range(len(D)):
            j = argmax(D[i], C)#D[i]に最も近いクラスタを探す
            #D[i]はC[j]にクラスタリングされるべき,ここではC[j]にiをクラスタリングする
            C[j].append(i)
        #calculate mean of each cluter
        mofc(C)
        #以下出力、収束までが見える
        print "Step",step
        step += 1
        for i, j in enumerate(C):
            print i, j, j.mean
        print ""

test code

#! usr/bin/env python
# -*- coding: utf-8 -*-

#k-means
import ml
print "create test data"
D = ml.test(3, 10)
for i, j in enumerate(D):
    print i, ":", j
#print ml.kmeans()mean(D, len(D[0]))
C = ml.kmeans(D, 3)

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中