LBG+Splittingアルゴリズムを作ってみた
背景
とある事情でクラスタリングを行いたかった。しかも非階層型クラスタリング。しかし、k-平均法は「最終的な結果が安定しない」と言うことで、どうしようと悩んでいた。
それに対し、色々な改善方法が提案されているけれど、それでも不安定性は残る。
目的
最終的な結果が一意になるようなクラスタリング手法の実装。
クラスタリングとは
クラスタリングとは、与えられたデータをいくつかの種類に分類する方法。カテゴリー分けなどと言った方が分かりやすいのかな。
主な使用例は
- twitterの年齢層と性別、投稿数でいくつかのグループに分類、利用層を分析する
- TVアニメのキャラクターの顔を、目の大きさなどで分類して、名前を付ける
- ソシャゲのキャラクターを、成長率などに基づいて、大器晩成型などに分類する
k-平均法
k-means法, k平均クラスタリングとも。何故か一般的な非階層型クラスタリング手法です。主な理由としては、ライブラリの標準関数としてあったり、実装が簡単だから・・・じゃないっすかね(適当)。
データN個をk個に分類する際の主な流れとしては、
これの問題点は、最初のN個を適当にクラスタリング分けすることらしいです。ランダムに決めることによって、初期位置に偏りが生じやすく、それが最後まで解消されないとか*1。そのため、クラスタリング結果が毎回異なり、「分類することが出来るが、それが本当に綺麗に分類した結果か」が不明なようです。
これに対し、初期位置を確率的に決める手法が色々提案されており、k-means++法が一番有名なのかと。
作ってみた
n0749086/LBG_Algorithm · GitHub
最初はscipyを使わずに、一次元データを扱う用のスクリプトです。これに関しては、とある研究のデータで一致することを検証済み。
scipyを使った方は、多次元データを扱えるようにしています。こちらは、クラス化しており、色々扱いやすくしているはず・・・です。但しまだ検証していないし、出力が正しいかを視覚的に確認していない。
考察
scipy未使用版は、最終出力結果は、ほとんど動いていなかった。と言うことは、量子化成功=クラスタリング結果が安定・・・?
個人的には、こういう結果が欲しかった。というのは、こういう風にしないと、きちんと理由付けが出来ない。
まとめ
多分出来たっぽい。まだ微修正+検証する必要があるけれど、とりあえず満足してます。
え、主成分分析しろ?あれはちょっと違うよね?けど、主成分分析→クラスタリングは一つの方法としてありなのかなと思う。