巨大データを効率よく分割するアフィニティ クラスタリング

巨大データを効率よく分割するアフィニティ クラスタリング

1.巨大データを効率よく分割するアフィニティ クラスタリングまとめ

・Googleが新しいクラスタリング手法の実績を公開
・アフィニティクラスタリングをベースとした手法で巨大データを効率よく分割
・GoogleMapのデータベースアクセス効率を大きく向上させた

2.アフィニティ クラスタリングとは?

巨大で複雑なデータを効率良く扱うためには、データを分割すると良い。しかし、巨大データを同じくらいのサイズのデータに綺麗に分割する事は簡単ではない。昔からグラフ分割問題として知られており、ビッグデータの世界でも様々な分割手法(クラスタリング)が考案されてきた。

Googleは以前からこの問題に取り組んでおり、アフィニティ クラスタリング(affinity clustering)をベースとするアルゴリズムの改良を続けている。

Googleによれば、10兆以上の頂点を持つ規模のグラフデータでは、アフィニティ クラスタリングは、良く使われるクラスタリング手法であるk-means等より質の高いクラスタを作成できるという。

アフィニティ クラスタリングはボトムアップでクラスタを作成していき、希望の分割数が実現できた時にクラスタ作成をストップする。

 

アフィニティ クラスタリングを更に改良し、従来手法より品質の高い分割を実現する事が出来た。品質の高い分割とは各クラスタのサイズ差をより小さく抑える事と定義できるが、改良したアフィニティ クラスタリングは、サイズ差を15~25%程度低くする事が出来ている。

この研究結果は、Google製品に実際に適用されている。GoogleMapのデータベースは複数のshardsに分割されているが、このshardsの分割にアフィニティ クラスタリングの手法を適用したところ、複数のshardsにアクセスする必要のあるデータベースクエリを21%削減でき、GoogleMapの道順案内のデータベースアクセス効率を大きく向上させた。

3.巨大データを効率よく分割するアフィニティ クラスタリング関連リンク

1)research.googleblog.com
Balanced Partitioning and Hierarchical Clustering at Scale

2)papers.nips.cc
Affinity Clustering: Hierarchical Clustering at Scale