agglomorative clustering and k-means

本日2回目のPostです。
先程k-meansを実装した記事を書きましたが、
言うまでもなく、k-meansでは初期値が大事です。
というわけでagglomorative clusteringでクラスタリングをし、
それを初期値にしてk-meansに投げるというコードを書きました。
k-meansのコードは相変わらずです、清書してません。笑
少し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, l=None):
            if mean is not None:
                self.mean = mean
            if l is not None:
                self = l
        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))
    else:#初期値が指定されている場合
        c = deepcopy(C)
        C = []
        for i in c:
            cl = Cluster()
            for j in i:
                cl.append(j)
            C.append(cl)
        mofc(C)
    oldC = None
    step = 0
    #以下k-meansのアルゴリズム
    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 -*-

#try k-means after agglomoratice clustering
import ml
print "create test data"
D = ml.test(3, 10)
for i, j in enumerate(D):
    print i, ":", j
print ""
import nlp
#agglomorative clustering
C = nlp.clustering(D, 3, simc=nlp.centroid_method)
#fix style of C
c = []
for i in C:
    l = list()
    for j in sorted(i):
        l.append(j)
    c.append(l)
print "the result of agglomoratice clustering"
for i, j in enumerate(c):
    print i, j
print ""
#k-means
C = ml.kmeans(D, 3, C=c)


result

create test data
0 : [ 0.65884922  0.17473523  0.64237452]
1 : [ 0.36397418  0.85349117  0.09308705]
2 : [ 0.26349176  0.2303135   0.28957912]
3 : [ 0.66841756  0.97203244  0.93656511]
4 : [ 0.6845394   0.12005654  0.40629962]
5 : [ 0.00648247  0.48151821  0.95795305]
6 : [ 0.90481084  0.38438392  0.03251916]
7 : [ 0.14460615  0.14097697  0.56173015]
8 : [ 0.98490412  0.65376514  0.62516488]
9 : [ 0.92865121  0.07216407  0.6124043 ]

the result of agglomoratice clustering
0 [1, 4, 6, 8]
1 [2, 5, 7, 9]
2 [0, 3]

Step 0
0 [1, 4, 6, 8] [ 0.73455714  0.50292419  0.28926768]
1 [0, 5, 7] [ 0.26997928  0.26574347  0.7206859 ]
2 [2, 3, 9] [ 0.62018684  0.42483667  0.61284951]

Step 1
0 [1, 6, 8] [ 0.75122971  0.63054674  0.25025703]
1 [5, 7] [ 0.07554431  0.31124759  0.7598416 ]
2 [0, 2, 3, 4, 9] [ 0.64078983  0.31386036  0.57744453]

Step 2
0 [1, 6] [ 0.63439251  0.61893755  0.0628031 ]
1 [5, 7] [ 0.07554431  0.31124759  0.7598416 ]
2 [0, 2, 3, 4, 8, 9] [ 0.69814221  0.37051115  0.58539793]

Step 3
0 [1, 6] [ 0.63439251  0.61893755  0.0628031 ]
1 [5, 7] [ 0.07554431  0.31124759  0.7598416 ]
2 [0, 2, 3, 4, 8, 9] [ 0.69814221  0.37051115  0.58539793]

コメントを残す

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

WordPress.com ロゴ

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

Twitter 画像

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

Facebook の写真

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

Google+ フォト

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

%s と連携中