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

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

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

２．アフィニティクラスタリングとは？

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

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

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

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

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

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