agglomorative clustering and k-means

本日2回目のPostです。
先程k-meansを実装した記事を書きましたが、
言うまでもなく、k-meansでは初期値が大事です。
というわけでagglomorative clusteringでクラスタリングをし、
それを初期値にしてk-meansに投げるというコードを書きました。
k-meansのコードは相変わらずです、清書してません。笑
少しk-meansのコードをいじりました。

sample code

 1:  #D(data)をk個のクラスタにクラスタリングする。
 2:  #初期クラスタCを与えることもできる。
 3:  #与えなければ適当に初期クラスタを生成する。
 4:  #なお、ベクトル間類似度にはコサイン類似度を用いる。
 5:  def kmeans(D, k, simv=nlp.simcos, C=None):
 6:      class Cluster(list):
 7:          def __init__(self, mean=None, l=None):
 8:              if mean is not None:
 9:                  self.mean = mean
10:              if l is not None:
11:                  self = l
12:          def setmean(self, m):
13:              self.mean = m
14:          def removeall(self):
15:              del self[:]
16:  
17:      def sim(v1, v2):
18:          import numpy
19:          return numpy.dot(v1, v2) / (numpy.sqrt(numpy.dot(v1, v1)) * numpy.sqrt(numpy.dot(v2, v2)))
20:      def mean(D):#Dの平均値を返す
21:          import numpy
22:          if len(D) == 0:#Dが空なら
23:              return
24:          else:
25:              d = len(D[0])
26:          sum = numpy.zeros(d)
27:          for i in D:
28:              sum += i
29:          return sum / len(D)
30:      def mofc(C):
31:          for i in C:
32:              l = []
33:              for j in i:
34:                  l.append(D[j])
35:              if len(i) == 0:
36:                  pass
37:              else:
38:                  i.setmean(mean(l))
39:      def argmax(i, C):
40:          max = -float("inf")
41:          maxindex = 0
42:          for j in range(len(C)):
43:              s = sim(i, C[j].mean)
44:              if max < s:
45:                  max, maxindex = s, j
46:          return maxindex
47:      def initc(self):
48:          for i in self:
49:              i.removeall()
50:      from copy import deepcopy
51:      import numpy
52:      if C is None:#初期値が指定されていなければ適当な初期値を
53:          m = mean(D)
54:          d = len(D[0])
55:          l = m / k
56:          M = []
57:  #        for i in range(k):
58:  #            M.append(numpy.random.random_sample(d))
59:          for i in range(k):
60:              M.append(l*(i+1))
61:          C = []#初期クラスタを生成
62:          for i in M:
63:              C.append(Cluster(i))
64:      else:#初期値が指定されている場合
65:          c = deepcopy(C)
66:          C = []
67:          for i in c:
68:              cl = Cluster()
69:              for j in i:
70:                  cl.append(j)
71:              C.append(cl)
72:          mofc(C)
73:      oldC = None
74:      step = 0
75:      #以下k-meansのアルゴリズム
76:      while oldC != C:
77:          #前のCをoldCへ
78:          oldC = deepcopy(C)
79:          #Cを初期化
80:          initc(C)
81:          for i in range(len(D)):
82:              j = argmax(D[i], C)#D[i]に最も近いクラスタを探す
83:              #D[i]はC[j]にクラスタリングされるべき,ここではC[j]にiをクラスタリングする
84:              C[j].append(i)
85:          #calculate mean of each cluter
86:          mofc(C)
87:          #以下出力、収束までが見える
88:          print "Step",step
89:          step += 1
90:          for i, j in enumerate(C):
91:              print i, j, j.mean
92:          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 と連携中