Clustering some vectors

agglomorative clustering

agglomerative clustering(凝集型クラスタリング) と呼ばれるものです。
これを実際に行う関数を書きました。少し冗長かもしれませんね。
sample code is below…

#D:dataset, N:cluster
#DatasetをN個のclusterにclusteringする
#この時使う類似度は
#ベクトルの類似度にsimv
#clusterの類似度にsimcを用いる
def clustering(D, N, simv=simcos, simc=single_link_method):
    #クラスタがN個になるまでclustering
    C = set()
    for i in range(0, len(D)):
        C.add(frozenset([i]))
    while N < len(C):
        max = -float("inf")
        Cp = C.copy()
        for i in C:
            Cp.discard(i)
            for j in Cp:
                d1 = list()
                for k in i:
                    d1.append(D[k])
                d2 = list()
                for k in j:
                    d2.append(D[k])
                d = simc(d1, d2, simv)
                if max == d:
                    if len(i.union(j))<len(c1.union(c2)):
                        c1, c2 = i, j
                elif max < d:
                    max = d
                    c1, c2 = i, j
        C.discard(c1)
        C.discard(c2)
        C.add(c1.union(c2))
    return C

various similarity between clusters

ベクトル間類似度は前回紹介した、
cosine similarity(コサイン類似度), euclidean distance(ユークリッド距離)などがあります。
凝集型クラスタリングでは似ているクラスタをくっつけるので、
クラスタが似ているかどうかを判断する尺度が必要です。
つまりは、クラスタ間類似度なるものが必要です。
このクラスタ間類似度を最大化するクラスタ対をくっつけていくことで、
クラスタリングを実現しています。
紹介するのは以下の3つです。

1. single link method

クラスタA、Bからベクトルをひとつずつ取り出し、
ベクトル間類似度を計算し、これをsimとします。
当然ながらsimがいっぱいできるわけですが、
その中から最大のsimを、クラスタ間類似度にする方法です。
sample code is below…

def single_link_method(c1, c2, sim):
    max = -float("inf")
    for i in c1:
        for j in c2:
            s = sim(i, j)
            if max < s:
                max = s
    return max

single link methodの逆バージョンです。
ベクトル間類似度の最低のsimをクラスタ間類似度にする方法です。

2. complete link method

sample code is below…

def complete_link_method(c1, c2, sim):
    min = float("inf")
    for i in c1:
        for j in c2:
            s = sim(i, j)
            if min > s:
                min = s
    return min

3. centroid method

文字通り、ベクトルの重心を用います。
1,2,の中間的な手法とされています。
sample code is below…

def centroid(c):
    import numpy
    n = len(c)
    c = numpy.array(c, dtype=float)
    return numpy.sum(c)/n
def centroid_method(c1, c2, sim):
    return sim(centroid(c1), centroid(c2))

Test Program

ではテストしてみましょう。
sample code is below…

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

import nlp
import numpy
#d次元の標本Dを作成、大きさはN
D = []
N = 10
d = 3
for i in range(0, N):
    D.append(numpy.random.random_sample(d))
for i, j in enumerate(D):
    print i,":",j
#Dを3つにクラスタリングしてみる。
#simvはベクトル間類似度
#simcはクラスタ間類似度
print "simv:cosine similarity"
print "simc:single link method"
C = nlp.clustering(D, 3)
for i in C:
    print i
print "simv:cosine similarity"
print "simc:complete link method"
C = nlp.clustering(D, 3, simc=nlp.complete_link_method)
for i in C:
    print i
print "simv:cosine similarity"
print "simc:centroid_method"
C = nlp.clustering(D, 3, simc=nlp.centroid_method)
for i in C:
    print i
#ベクトルを眺めてもなかなか妥当性が判断しにくい。
#そこで、文→ベクトル→クラスタリング→文とすると、
#似ている文を集めることができるはず。
#文→ベクトル時にノイズがなければの話だが。

コメントを残す

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

WordPress.com ロゴ

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

Twitter 画像

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

Facebook の写真

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

Google+ フォト

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

%s と連携中