ぐるんぐるん

おもむくままに書いてます。

LBG+Splittingアルゴリズムを作ってみた

背景

とある事情でクラスタリングを行いたかった。しかも非階層型クラスタリング。しかし、k-平均法は「最終的な結果が安定しない」と言うことで、どうしようと悩んでいた。

それに対し、色々な改善方法が提案されているけれど、それでも不安定性は残る。

目的

最終的な結果が一意になるようなクラスタリング手法の実装。

クラスタリングとは

クラスタリングとは、与えられたデータをいくつかの種類に分類する方法。カテゴリー分けなどと言った方が分かりやすいのかな。

主な使用例は

  • twitterの年齢層と性別、投稿数でいくつかのグループに分類、利用層を分析する
  • TVアニメのキャラクターの顔を、目の大きさなどで分類して、名前を付ける
  • ソシャゲのキャラクターを、成長率などに基づいて、大器晩成型などに分類する

k-平均法

k-means法, k平均クラスタリングとも。何故か一般的な非階層型クラスタリング手法です。主な理由としては、ライブラリの標準関数としてあったり、実装が簡単だから・・・じゃないっすかね(適当)。

データN個をk個に分類する際の主な流れとしては、

  • データN個をk個のクラスタにランダムに分ける
  • k個のクラスタの中心点を計算する
  • データN個を再度k個のクラスタに分類する
    • この際、それぞれのクラスタとの中心との距離を算出し、最小距離のクラスタに分類する
  • 適当なタイミングで終了する

これの問題点は、最初のN個を適当にクラスタリング分けすることらしいです。ランダムに決めることによって、初期位置に偏りが生じやすく、それが最後まで解消されないとか*1。そのため、クラスタリング結果が毎回異なり、「分類することが出来るが、それが本当に綺麗に分類した結果か」が不明なようです。

これに対し、初期位置を確率的に決める手法が色々提案されており、k-means++法が一番有名なのかと。

LBGアルゴリズム

これは、実はベクトル量子化アルゴリズムです。簡単に言うと、「この世界では、1と言うデータは0として扱う。」的な感じで、近似値に置き換えるためのアルゴリズムです。

今回は、「近似値にするって、考え的にクラスタリングと同じじゃね?」と思って使ってみるわけです。はい、ご指摘待ってます。

基本的には、k-平均法と同じです。何が違うかというと、最初のベクトルの決定の仕方が違う。簡単に言うと、「ランダムにk/2個のクラスタに分けた後、その中心を計算し、その中心±ε*2を中心として扱う」と言うものです。これにより、収束が早くなる・・・らしい。

作ってみた

n0749086/LBG_Algorithm · GitHub

最初はscipyを使わずに、一次元データを扱う用のスクリプトです。これに関しては、とある研究のデータで一致することを検証済み。

scipyを使った方は、多次元データを扱えるようにしています。こちらは、クラス化しており、色々扱いやすくしているはず・・・です。但しまだ検証していないし、出力が正しいかを視覚的に確認していない。

考察

scipy未使用版は、最終出力結果は、ほとんど動いていなかった。と言うことは、量子化成功=クラスタリング結果が安定・・・?

個人的には、こういう結果が欲しかった。というのは、こういう風にしないと、きちんと理由付けが出来ない。

まとめ

多分出来たっぽい。まだ微修正+検証する必要があるけれど、とりあえず満足してます。

え、主成分分析しろ?あれはちょっと違うよね?けど、主成分分析→クラスタリングは一つの方法としてありなのかなと思う。

今後の課題

*1:他にも理由は色々あります

*2:εは中心と最も遠いベクトルの距離の1%ぐらいが良いとされています

*3:距離最大化という観点から