機械学習

KMeansでのクラスタリングと特徴量の生成に関して勉強したことをまとめておく

今日はクラスタリング手法の一つであるKMeansと、KMeansを用いた特徴量の生成(クラスタ重心からの各点の距離の特徴量の生成)に関して調べたので簡単にまとめておきます。

K-Meansの理解

まず、K-Means(k-平均法)はラベル無しのデータを任意の数に分類をするときに用いられる教師無し学習の手法の一つとなります。

k-Meansでは大きく分けて5つのステップで計算が行われます。

STEP 1 :データを何個に分類するか指定する(k個)

STEP 2 :ランダムにk個の点をプロットする ※初期値依存問題有り

STEP 3 :全てのデータをSTEP2のランダムな点に近い方(k個)に分類する

STEP 4:分類毎の重心点を求める

STEP5:重心点を起点として再度全てのデータの分類を行う(STEP3と同様)

STEP3~STEP5を重心点の移動が起きなくなるまで繰り返す

yaaku

なるほど…

STEP 1.データを何個に分類するか指定する(k個)

簡単な例として下記のような散布図を持ったデータを考えます。x, y はそれぞれ特徴量となります。

ここでは2個に分類する場合を考え以下進めていきます。

STEP 2.ランダムにk個の点をプロットする

分類を2個としたので、下記のようにランダムな点を2点プロットします。

ランダムな点は既存の点に重なっても問題なく、それぞれをA,Bとします。

後に出てきますが、最初にランダムに置く点(初期値)の位置によって、最終分類結果に影響を及ぼしてしまう初期値依存の問題があるため、初期値の置き方には注意が必要になります。

STEP 3. 全てのデータをSTEP 2のランダムな点に近い方に分類する

先ほどランダムにプロットした点A,Bをそれぞれグループとし、各データの点との距離を計算し、より近いほうのグループに属させます。

この時の距離の計算方法の種類としてはユーグリッド距離とマンハッタン距離が使われているようです。

STEP 4:分類毎の重心点を求める

グループA、Bができたので、各グループの重心点を求め、最初にランダムにプロットした起点を重心点に移動させます。

yaaku

絵のセンス…

 

STEP 5:重心点で再度分類を行う(STEP 3と同様)

STEP 4で重心点が移動したので最初にグループ分けしたデータの中で基準点(A,B)との距離の関係が逆転したものが出てきます(下記黄色い〇)。

このようなデータを再度重心点が近いほうのグループに分類します。

そうすると各グループの重心点の位置も変わるので重心点の移動を行います(STEP 4)

STEP 4と5を繰り返すことで重心点の移動が行われなくなると分類終了となり、最終的な分類結果が計算できます。

初期値依存による問題

K-Meansでは最初にランダムでプロットした初期値により、分類結果が変わるという問題が起きてしまいます。例えば、最初にランダムにプロットする点が下記のような場合、同じデータでも最終の分類結果が変わってしまいます。

これを防ぐ方法として初期値の選択でK-Means++という方法があります。

k-means++法は、初期のk個のクラスタ中心はなるべく離れている方が良いという考えにもとづいている。まず始めにデータ点をランダムに選び1つ目のクラスタ中心とし、全てのデータ点とその最近傍のクラスタ中心の距離を求め、その距離の二乗に比例した確率でクラスタ中心として選ばれていないデータ点をクラスタ中心としてランダムに選ぶ。

(Wikipedia引用)

K-means++での初期値選択は下記のようになります。

STEP 1:実際のデータからランダムな点を1個選ぶ

STEP 2 :次の点は最初の点との距離で重み付けした確率分布を用いて選択する

ただsklearnではデフォルトでk-means++が設定されているので特に気にする必要はないようです。

(sklearn公式より)

重心からの距離で特徴量を作る

最後にkaggleで使えるんじゃないかという「各クラスタの重心点からの距離(cluster distance feature)」という特徴を作るコードを書いておきます。

この特徴量は先日開催されたMicrosoft Malware Predictionのkernelであったものを他のkagglerの方がブログにされてたいたので参考にさせていただきました。

全ての特徴量を使用しても計算可能ですが、lgbなどのツリー系でimportanceが高い特徴量の中から何個か選んでk-meansにかけても有効な特徴量を生成することができることがあるみたいなので実践で使っていきたいですね。