Locality-Sensitive Hashingを用いた階層的クラスタ解析手法の近似解法

摘要

階層的クラスタ解析手法は類似度でデータを階層的に分類し、その結果は樹形図で表現することができる。 この手法を用いると細かい分類から大まかな分類までクラスタ間の包含関係が理解しやすいが、計算量は大きなものとなるので、高次元·大規模データに対して適用することは難しい。 本研究では階層的クラスタ解析の代表的なSingle-Link法に対して、高速な近似手法を提案する。 本手法は最近接点の候補を高速に見つけるアルゴリズムであるLocality-Sensitive Hashingにおいて作られるハッシュテーブルを用いることで計算量を減らす。 実験の結果、提案手法が（1）Single Link法と同じく楕円形以外のクラスタでも抽出できること、及び（2）高次元大規模データに対してSingle Link法より高速に動作することを確認した。