始まりました、「～したい」シリーズ。
今回はHKM≪階層的K平均法≫です。
話は変わるんですけど、ワタクシ大変なことに気づいてしまいました・・・。
「～したい」シリーズのタイトルの後ろについてる「＠その～」っていうバックナンバー、
そのいち、そのにぐらいまでしか続かない(^p^)
バックナンバーつける意味あるのかってね。
BBCPマコトの紹介記事とかだと結構続いたんですけどね。
飽きっぽい性格の私は一つの物事に集中して取り組めないのですよ(^p^)
いっそバックナンバー制廃止にしようかな。
まあ、それはさておいて、今回のタイトル「HKM」についてです。
HKMとは本来ならクラスタ分析をする為に使われる手法です。
今回はこれを最近傍探索に使います。
最近傍探索にはいろいろな手法があるのですが、これはKDtreeに似ているかもしれません。
KDtreeという手法は簡単に言えば
- 空間を分割する。
- クエリが分割された空間のどこに属するか調べる。
- クエリが属する空間の中に最近傍がある。
という手法です。
それに対してHKMは
- データを2つのクラスタ（データの集合）に分ける。
- 分けられたクラスタの中のデータをさらに2つのクラスタに分ける。
- クラスタの中のデータが1つになるまで1.2.を繰り返す。
- クエリがどのクラスタに属するか調べる。
- クエリが属するクラスタがの中に最近傍がある。
詳しいことは 知 り ま せ ん 。
詳しい人は私にご教授ください。
とりあえず今回HKMを使うために使ったアルゴリズムとその紹介。
KNN（ｋ近傍法）
クエリの近傍をｋ個求める手法。アルゴリズム
- クエリとデータベース全点の距離を計算。
- 距離を昇順にソート。
- 上からｋ個をとる。
Kmeans（ｋ平均法）
ｋ個のクラスタを作る手法。
アルゴリズム
- 空のクラスタをｋ個作る。
- それぞれのクラスタにランダムにデータを割り当てる。
- クラスタに含まれるデータの座標の平均をクラスタの中心とする。
- 各データと各クラスタ中心の距離を計算し、各データを最近傍となる各クラスタに割り当てなおす。
- 割り当ての変化量が一定の閾値以内になるまで3.4.を繰り返す。
HKM（階層的ｋ平均法）
階層的にｋ個のクラスタを作る手法。アルゴリズム
- ｋ個のクラスタを作る。
- クラスタの中でさらにｋ個のクラスタを作る。
- クラスタの中のデータが1個になるまで2.を繰り返す。
こんな感じです。
最初にKNNを作って、次にKNNを使ってKmeansを作って、次にKmeansを使ってHKMを作ります。
こういうの楽しいよね。
弱い武器を強化していって最強の武器を作るみたいな感じ。
テンションが上がりますね(^p^)
それでは以下ソース
量がやばい。
説明はきっといらないよね・・・？
アルゴリズムの紹介してるしね？
未来の俺はこう言う。
「コメント文ぐらい書けよ(#^p^)」
ってか、あれ、これ・・・
そのに、そのさんに分ければよかったんじゃね？？
