k-means清書しました。

まだまだ汚いですが、清書しました。
もう書きたくないです。笑
というわけで最終版になりそうですねー。
ベクトルはIndexで管理したいんですけど、
平均を求めるときとか少しめんどくさいんですよね。
まぁネストしてる関数だから、その関数上で使えればいいんですけどね。

 1:  def kmeans(D, k, C=None, sim=simcos):
 2:      import numpy
 3:      import copy
 4:      class Cluster(list):
 5:          def __init__(self, initlist=None, initmean=None):
 6:              if initlist is not None:
 7:                  self = initlist
 8:              if initmean is not None:
 9:                  self.mean = initmean
10:              else:
11:                  self.mean = 0
12:          def setmean(self, mean=None):
13:              if not self:
14:                  print "test"
15:                  return
16:              elif mean is None:
17:                  l = list()
18:                  for i in self:
19:                      l.append(D[i])
20:                  self.mean = numpy.array(l).sum(axis=0)
21:              else:
22:                  self.mean = mean
23:          def init(self):
24:              del self[:]
25:          def __repr__(self):
26:              str = ""
27:              str += "-----------------------------------------------------------------\n"
28:              str += "{"
29:              for i in self:
30:                  str += repr(i)+" "
31:              str += "}\n"
32:              str += "mean:"+repr(self.mean)
33:              return str
34:      def sim(v1, v2):
35:          return numpy.dot(v1, v2) / (numpy.sqrt(numpy.dot(v1, v1)) * numpy.sqrt(numpy.dot(v2, v2)))
36:      def initclusters(c=None):
37:          if c is None:
38:              #ベクトルはクラスタリングせずに、初期値だけ与えておく
39:              m = D.sum(axis=0)
40:              l = m / k
41:              c = []
42:              for i in range(k):
43:                  c.append(Cluster(initmean=l*(i+1)))
44:              return c
45:          else:
46:              new = copy.deepcopy(c)
47:              for i in new:
48:                  i.init()
49:              return new
50:      def argmax(v):
51:          max = -float("inf")
52:          maxindex = 0
53:          for i in range(len(c)):
54:              s = sim(v, c[i].mean)
55:              if max < s:
56:                  max, maxindex = s, i
57:          return maxindex
58:      def estimatemean():
59:          for i in c:
60:              i.setmean()
61:              i.mean
62:      if C is None:
63:          c = initclusters()
64:      else:
65:          pass
66:      old = None
67:      while old != c:
68:          old = copy.deepcopy(c)
69:          c = initclusters(c)
70:          for i in range(len(D)):
71:              j = argmax(D[i])
72:              c[j].append(i)
73:          #更新
74:          estimatemean()
75:          for i, j in enumerate(c):
76:              print i, repr(j)
77:          print ""

Sample Mean in numpy

こんばんは。
前記のk-meansやらでSample Mean(標本平均)を求める必要があったので、その場しのぎで自作してたんですけど、もっとスマートにできないかなと、探して見ました。
これはベクトルを実際どう管理するかっていう最近の悩みにも直結するんですけどね。笑
結論から言うとありました。
ここのsumのところを見てみてください。
axisで深さを指定できるみたいです。
やはり、思ったことはすでに誰かがやってくれてますね。笑

sample codeは下に載せておきます。

 1:  #! usr/bin/env python
 2:  # -*- coding: utf-8 -*-
 3:  
 4:  #元がベクトルであるような標本を扱う際に、
 5:  #効率良く標本平均を求めることができないか、検証する
 6:  import numpy
 7:  N = 10
 8:  d = 3
 9:  D = []#まず標本をリストとしておく
10:  for i in range(N):
11:      D.append(numpy.random.random_sample(d))
12:  #とりあえずプリント
13:  for i, j in enumerate(D):
14:      print i, j
15:  #とりあえず現在の方法でプリントしておく
16:  s = numpy.zeros(len(D[0]))
17:  for i in D:
18:      s += i
19:  print s#これがほしい
20:  #とりあえずDをnumpy.arrayにしてみる。
21:  D = numpy.array(D)
22:  print "convert list to numpy.array"
23:  print D
24:  
25:  #できた。
26:  #じゃあこれのsumを出してみる。
27:  
28:  print D.sum()
29:  #スカラーが出てきた…
30:  #もしかしてこのスカラーは全部のエレメントをを足したものだろうか。
31:  #だとすると以下と一致するはず
32:  
33:  s = 0
34:  for i in D:
35:      s += i.sum()
36:  print s
37:  #予想通り一致した。
38:  #次の方法を模索する。
39:  
40:  #耳寄りな情報!
41:  #参考文献に載せておく。
42:  #sumのaxisを0にすればよいみたいだ。
43:  print D.sum(axis=0)#完了だ。
44:  
45:  #ちなみに…
46:  print D.sum(axis=1)
47:  #各ベクトルのsumが出てるみたいだ。
48:  
49:  print D.sum(axis=2)
50:  #これはエラー
51:  #axisは深さだと理解しておこう。
52:  
53:  

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]

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]

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)