共同発表：ビッグデータのクラスタリングがパソコンで可能に少ないメモリー容量でも高速に処理できる手法を開発

ポイント

データを圧縮して処理することで省メモリーを実現
似たデータを集めたグループの「平均」を効率よく計算する新技術を考案して処理を高速化
これにより、一般的な能力のパソコンでもビッグデータのクラスタリング処理が可能に

大学共同利用機関法人情報・システム研究機構国立情報学研究所（ＮＩＩ）コンテンツ科学研究系特任研究員　松井勇佑（マツイユウスケ）、株式会社ドワンゴメディアヴィレッジ研究開発グループ　グループリーダー　大垣慶介（オオガキケイスケ）、国立大学法人東京大学大学院情報理工学系研究科電子情報学専攻　教授　相澤清晴（アイザワキヨハル）、同　准教授　山崎俊彦（ヤマザキトシヒコ）の研究グループは、データ処理の基本操作であるクラスタリングを、１０億個程度のビッグデータに対して、高速で、かつ、少ないメモリー容量で実行できる実用性の高い手法を開発しました。これにより、例えばソーシャルメディアの膨大な画像データを一般的なパソコンでも手軽に処理することが可能となります。一般の技術者や研究者にもビッグデータの扱いが容易になるため、深層学習を応用した人工知能（ＡＩ）の開発をはじめとする広い分野での活用が期待されます。

本手法では、データを圧縮した状態でクラスタリングを行うため、従来手法よりも少ないメモリー容量で処理が可能になりました。さらに、似たデータを集めたグループの「平均」を効率良く計算する新技術を考案したことで、処理の高速化を実現しました。クラスタリングの基本的手法の１つであるｋ平均法に対して、精度は劣るものの、１０～１０００倍程度高速化し、１００～４０００倍程度の省メモリーとなります。

本研究成果は、マルチメディア分野のトップ国際会議「ＡＣＭ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍｕｌｔｉｍｅｄｉａ　２０１７」（１０月２３日～２７日、米カリフォルニア州マウンテンビュー）で発表されます。また、論文（PQk-means: Billion-scale Clustering for Product-quantized Codes）は９月１４日に計算機科学などの論文を保存・公開するウェブサイト「ａｒＸｉｖ（アーカイブ）」（https://arxiv.org/）に先行掲載されます。

本研究成果の一部は、以下の事業・研究領域・研究課題によって得られました。

科学技術振興機構（ＪＳＴ）戦略的創造研究推進事業　ＡＣＴ－Ｉ

研究領域	「情報と未来」^※ （研究総括：後藤真孝産業技術総合研究所　首席研究員）
研究課題	「圧縮線形代数：データ圧縮による省メモリ高速大規模行列演算」（グラント番号：JPMJPR16UO）
研究者	松井勇佑

※文部科学省の人工知能/ビッグデータ/IoT/サイバーセキュリティ統合プロジェクト（AIPプロジェクト）の一環として運営

＜研究の背景＞

ＡＩなどの研究においては、巨大で複雑なデータ（ビッグデータ）を処理する必要があります。こうした大量のデータのうち似たものをまとめてグループに分ける「クラスタリング」は、データ処理の最も基本的な作業の１つです。例えば、ソーシャルメディアにアップロードされている膨大な数の画像データを対象に、動物のようなものが写っている写真、街の風景が写っている写真といったグループに分ける処理がクラスタリングです。しかし、枚数が１億以上の巨大なデータに対しては、従来の手法では、処理速度が遅すぎたり、必要なメモリー容量が大きすぎたりして、個人パソコンユーザーが入手・利用できる仕様のパソコン^注１）１台ではクラスタリングを実行することは難しいという問題がありました。このため、大規模なクラスタリングを行うためには、多数のサーバーを用いた分散並列処理が必要でした。

＜今回開発した技術と成果＞

研究チームが開発した手法では、まず、直積量子化^注２）という技術を用いてデータを圧縮します。これにより、データを従来手法よりも少ないメモリーで表現することができます。次に、圧縮されたデータに対して、「似ているデータを集めてグループを作る」「グループの『平均』を計算する」という処理を繰り返します。今回は、グループの平均を効率的に計算する技術を新たに考案し、これにより、高速なクラスタリングが可能になりました。似ているデータを集める手法については、松井が過去に提案した技術^注３）を利用しています。

この手法を用いることで、例えば、画像データセット「Ｙａｈｏｏ　Ｆｌｉｃｋｒ　Ｃｒｅａｔｉｖｅ　Ｃｏｍｍｏｎｓ　１００Ｍ（ＹＦＣＣ１００Ｍ）」の１億枚の画像を対象に、「氷上のスポーツ試合」や「欧風の教会」、「ヤシの木」など１０万種類のグループに分類する処理を、個人が一般に入手できる高性能機種の仕様であるメモリー容量３２ＧＢ、ＣＰＵのコア数４のパソコン１台でも約１時間で実行できました。これを一般的なクラスタリング手法を用いて同じ所要時間で実行しようとすると、同じ仕様のパソコンが約３００台必要になります。また、１０億の画像データを１０万種類のグループに分ける処理も約１２時間で実行できました。

さらに、本手法を最新の既存手法である「Ｂｉｎａｒｙ　ｋ平均法」^注４）などと比較した場合、以下のような利点があります。

（１）本手法は、クラスタリング終了後にデータを近似的に復元できます。多くの既存手法は高速化を実現するために元データを不可逆的に大きく変形してしまうため、クラスタリングが終わった後に元データを復元できず、クラスタリング結果を解釈したり、別の処理に利用したりすることができないという弱点がありました。本手法はこの問題を解決しています。

（２）本手法はシンプルであり、煩雑な設定が必要ありません。多くの既存手法は使うデータに応じてチューニングする必要がありましたが、本手法は何も設定することなく簡単に使うことができます。

研究チームでは、従来の最近傍探索分野の研究で使われているデータセットの中で最大規模と言われている１０億個のデータ^注５）を目標として研究に取り組み、今回、その規模のクラスタリングを実現したことを１つのマイルストーンと考えています。

＜今後の展望＞

クラスタリングは大規模なデータを扱う際に最も基本的で最初に行う処理です。１０億個規模の大規模データを一般的な能力のパソコンでも手軽に扱えるクラスタリング手法を新たに提案できたことは、大規模なデータ処理に日常的に取り組むエンジニアや研究者にとって有益であると考えられます。また、マイコンなどメモリー容量があまりないＩｏＴ（モノのインターネット）のエッジデバイスにおいてもクラスタリング前処理を行えるようになるなど、ＩｏＴ時代のデータ処理にも有効だと考えられます。

研究チームでは、ビッグデータ処理に関わるすべてのエンジニアや研究者の利用に供するため、本手法のコードを９月１４日より、以下のＵＲＬで一般公開する予定です。

https://github.com/DwangoMediaVillage/pqkmeans

＜参考図＞

図

１億枚の画像をクラスタリング処理した結果の例。似た画像がまとめられている（上から、「氷上のスポーツ試合」グループ、「欧風の教会」グループ、「ヤシの木」グループそれぞれの画像の一部）

＜用語解説＞

注１）個人パソコンユーザーが入手・利用できる仕様のパソコン: チェコのサイバーセキュリティー会社「Ａｖａｓｔ　Ｓｏｆｔｗａｒｅ」が今年４月に発表した、同社の製品から得られたデータに基づく「Ａｖａｓｔ　ＰＣ　Ｔｒｅｎｄｓ　Ｒｅｐｏｒｔ」（http://files.avast.com/files/marketing/materials/pctrendsreportjan2017.pdf）によると、メモリー容量６４ＧＢ以上のパソコンを使っているのは調査対象９６０万人中１万人以下（０．１％）で、ＣＰＵのコア数はデュアルコア（２個）とクアッドコア（４個）を合わせて全体の９２％を占めている。
注２）直積量子化: 事前に、「候補データ」を複数用意しておく。圧縮したいデータに対し、最も近い候補データの「番号」だけを記録する。これにより、データを「番号」だけで表すことができる。この考え方を発展させ、データを次元方向に複数個に分割し、上記の番号表現を行ったものが直積量子化である。 H. Jégou, M.Douze, and C.Schmid, “Product Quantization for Nearest Neighbor Search” , IEEE TPAMI 2011
注３）松井が過去に提案した技術: 直積量子化により圧縮されたデータに対し、ハッシュテーブルというデータ構造を用いて高速に似ているデータを探す手法。Y.Matsui, T.Yamasaki, and K.Aizawa, “PQTable: Fast Exact Asymmetric Distance Neighbor Search for Product Quantization using Hash Tables”, ICCV 2015
注４）Ｂｉｎａｒｙ　ｋ平均法: 一般的なクラスタリング手法であるｋ平均法を高速化した手法。Y.Gong, M.Pawlowski, F.Yang,L.Brandy, L.Bourdev, and Rob Fergus, “Web Scale Photo Hash Clustering on A Single Machine”, CVPR 2015
注５）最大規模と言われている１０億個のデータ: 「ＡＮＮ＿ＳＩＦＴ１Ｂ」データセット（http://corpus-texmex.irisa.fr/、「Deep1B」データセット（http://sites.skoltech.ru/compvision/noimi/）。