2021年 春期 応用情報技術者試験 問3

クラスタ分析に用いるk-means法

k-means法によるクラスタ分析は、異なる性質のものが混ざり合った母集団から互いに似た性質をもつものを集め、クラスタと呼ばれる互いに素な部分集合に分類する手法である。新聞記事のビッグデータ検索、店舗の品ぞろえの分類、教師なし機械学習などで利用されている。ここでは、2次元データを扱うこととする。

分類方法と例

N個の点をK個（N未満）のクラスタに分類する方法を(1)～(5)に示す。

(1) N個の点（1からNまでの番号が付いている）からランダムにK個の点を選ぶ（以下、初期設定という）。それらの点をコアと呼ぶ。コアには1からKまでのコア番号を付ける。なお、K個のコアの座標は全て異なっていなければならない。

(2) N個の点とK個のコアとの距離をそれぞれ計算し、各点から見て、距離が最も短いコア（複数存在する場合は、番号が最も小さいコア）を選ぶ。選ばれたコアのコア番号を、各点が所属する1回目のクラスタ番号（1からK）とする。ここで、二つの点をXY座標を用いてP=(a, b)とQ=(c, d)とした場合、PとQの距離を√(a-c)²+(b-d)²で計算する。

(3) K個のクラスタのそれぞれについて、クラスタに含まれる全ての点を使って重心を求める。ここで、重心のX座標をクラスタに含まれる点のX座標の平均、Y座標をクラスタに含まれる点のY座標の平均と定義する。ここで求めた重心の番号はクラスタの番号と同じとする。

(4) N個の点と各クラスタの重心（G₁, ⋯, Gₖ）との距離をそれぞれ計算し、各点から見て距離が最も短い重心（複数存在する場合は、番号が最も小さい重心）を選ぶ。選ばれた重心の番号を、各点が所属する次のクラスタ番号とする。

(5) 重心の座標が変わらなくなるまで、(3)と(4)を繰り返す。

次の座標で与えられる7個の点を、この分類方法に従い、二つのクラスタに分類する例を図1に示す。

P₁=(1,0) P₂=(2,1) P₃=(4,1) P₄=(1.5,2) P₅=(1,3) P₆=(2,3) P₇=(4,3)

クラスタ分析のプログラム

この手法のプログラムを図2に、プログラムで使う主な変数、関数及び配列を表3に示す。ここで、配列の添字は全て1から始まり、要素の初期値は全て0とする。

function clustering (N, K)                    //Nはデータ数、Kはクラスタ数
    MaxCount ← 100                            //無限ループを防ぐため最大見直し回数を設定
    initial(K)                                //初期設定
    for( s を 1 から N まで 1 ずつ増やす )      //クラスタを決定（1回目）
        for( t を 1 から K まで 1 ずつ増やす )
            data_length[t] ← data_dist(s, core[t])
        endfor
        cluster[s] ← min_index(data_length)
    endfor
    for( p を 1 から MaxCount まで 1 ずつ増やす )   //クラスタを見直す
        if( p が 1 と等しい )
            for( イ )                 //1回目の重心の計算
                coordinate_x[t] ← gravity_x(t)
                coordinate_y[t] ← gravity_y(t)
            endfor
        else
            ウ
            for( イ )                 //2回目以降の重心の計算
                if( gravity_x(t)と coordinate_x[t]が異なる    //重心を修正する
                又は gravity_y(t)と coordinate_y[t]が異なる )
                    coordinate_x[t] ← gravity_x(t)
                    coordinate_y[t] ← gravity_y(t)
                    flag ← 1
                endif
            endfor
            if( エ )                   //終了して抜ける
                return
            endif
        endif
        for( s を 1 から N まで 1 ずつ増やす )      //近い重心を見つける
            for( t を 1 から K まで 1 ずつ増やす )
                grav_length[t] ← grav_dist(s,t)
            endfor
            オ
        endfor
    endfor
endfunction

初期設定の改良

このアルゴリズムの最終結果は初期設定に依存し、そこでのコア間の距離が短いと適切な分類結果を得にくい。そこで、関数initialにおいて一つ目のコアはランダムに選び、それ以降はコア間の距離が長くなる点が選ばれやすくなるアルゴリズムを検討した。検討したアルゴリズムでは、t番目までのコアが決まった後、t+1番目のコアを残った点から選ぶときに、それまでに決まったコアから離れた点を、より高い確率で選ぶようにする。具体的には、それまでに決まったコア（コア1～コアt）と、残った N-t 個の点からPs との距離の和をTsとする。N-t個の全ての点について TsをΣめ、Tsがカほど高い確率で点Psが選ばれるようにする。このとき、点Psがt+1番目のコアとして選ばれる確率としてキを適用する。