PythonでK-meansクラスタリング

この記事に書かれていること

K-meansの説明
PythonによるK-meansアルゴリズムの実装

クラスタリングとは何か

クラスタリングとは、ざっくり言うと分類対象の沢山のデータから、それらを適当に分別するルールを勝手に獲得することだそうです。

変な言い回しですね。
これは正しく無い表現かもしれませんが、クラスタリングとはデータを分類分けする事に重きを置いています。

この分類分けという言葉が厄介で、SupportVectorMachineやベイズ規則、NeuralNetwork等による識別も分類分けをする事が出来ます。

これらの手法とクラスタリングの違いは、プログラムに対し分類対象の正解を教えるかどうかだと思います。

SVM等は分類対象のデータの中から学習用のデータを選出し、そのデータとそのデータが所属するラベルを一緒に与えて学習します。これを教師あり学習と呼びます。

そして、学習用データに対し、教師として与えられた正解を出力するように分類器のパラメータを学習していきます。

対してクラスタリングは、教師信号を与えません。与えられたデータ同士の関係を用いて分類器のパラメータをチューニングしていきます。

その為、クラスタリングでは良くも悪くも、設計者が想像したものとは全く異なった分類結果になる事も有ります。

K-meansアルゴリズム

K-meansアルゴリズムは分類対象のデータと、データの距離の計算方法と、分類するカテゴリの数さえ設定できればクラスタリングが可能な非常に高速で手頃なクラスタリング手法です。

ざっくりK-meansを説明すると、分類対象のデータにランダムにラベル付を行い、ラベル毎にデータの中心（重心）を算出し、分類対象の全てのデータに対し尤も近い重心のラベルに再割当てするアルゴリズムです。

アルゴリズムはWikipediaに簡潔にまとめられています。
k平均法 - Wikipedia

Pythonによる実装

def near(vector, center_vectors):
    """
    vectorに対し、尤も近いラベルを返す
    :param vector:
    :param center_vectors:
    :return:
    """
    euclid_dist = lambda vector1, vector2: (sum([(vec[0]-vec[1])**2 for vec in list(zip(vector1, vector2))]))**0.5
    d = [euclid_dist(vector, center_vector) for center_vector in center_vectors]
    return d.index(min(d))


def clustering(vectors, label_count, learning_count_max=1000):
    """
    K-meansを行い、各ラベルの重心を返す
    :param vectors:
    :param label_count:
    :param learning_count_max:
    :return:
    """
    import random
    #各vectorに割り当てられたクラスタラベルを保持するvector
    label_vector = [random.randint(0, label_count-1) for i in vectors]
    #一つ前のStepで割り当てられたラベル。終了条件の判定に使用
    old_label_vector = list()
    #各クラスタの重心vector
    center_vectors = [[0 for i in range(len(vectors[0]))] for label in range(label_count)]

    for step in range(learning_count_max):
        #各クラスタの重心vectorの作成
        for vec, label in zip(vectors, label_vector):
            center_vectors[label] = [c+v for c, v in zip(center_vectors[label], vec)]
        for i, center_vector in enumerate(center_vectors):
            center_vectors[i] = [v/label_vector.count(i) for v in center_vector]
        #各ベクトルのラベルの再割当て
        for i, vec in enumerate(vectors):
            label_vector[i] = near(vec, center_vectors)
        #前Stepと比較し、ラベルの割り当てに変化が無かったら終了
        if old_label_vector == label_vector:
            break
        #ラベルのベクトルを保持
        old_label_vector = [l for l in label_vector]
    return center_vectors

次のように呼び出すと重心vectorを作成することが出来ます。

#分類対象のデータのリスト。各要素はfloatのリスト
vectors = [[random.random(), random.random()] for i in range(100)]
#分類対象のデータをクラスタ数3でクラスタリング
centers = clustering(vectors, 3)

あるデータが所属するクラスタを求めたい時は次のように呼び出します。

#新しいデータ
vector = [0.5, 0.5]
label = near(vector, centers)

ランダムにデータを生成し、クラスタ数4でクラスタリングした時、次のようになります。

ちゃんとクラスタリングされていますね。