データベース<ビックデータの分析・活用>

世界最速! 138億年かかるビッグデータ解析をノートパソコンで「瞬時」に計算する賢いアルゴリズム

塩川浩昭先生 筑波大学 計算科学研究センター

データベースシステム研究では、データベースや情報管理の在り方、データの検索・分析・活用方法などを学ぶことができ、この情報化社会の中で私たちの身の回りに溢れている様々な情報の最大限の活用に役立てることができます。塩川先生はその中でも、ソーシャルネットワークサービスで、毎分毎秒更新され続けるユーザーの膨大な情報、いわゆる「ビッグデータ」を瞬時に解析することができる賢いアルゴリズムを研究開発しました。

現在、多くの人が利用しているTwitterやFacebook、E-mailなどでは時々刻々と膨大な量のデータが作られています。1分間にTwitterであれば40万ツイート、Facebookなら250万投稿・1800万「いいね!」、E-mailなら、なんと1億通のやり取りがなされています。このような大規模なデータ、いわゆるビッグデータを解析して、そのデータの中に隠れた知識や法則、ルールを見つけ出すことはビジネスやサイエンスの領域で非常に重要な技術となっています。

 

直感的な例として、芸能人の共演関係から作った仮想的なSNSを考えてみましょう。このSNSを解析することで、SNSのなかに隠れたコミュニティ構造を明らかにすることができます。例えば、男性俳優と男性モデルは同じコミュニティを形成しているのかと思いきや、男性俳優と男性モデルは全く別のコミュニティに分かれており、男性モデルコミュニティの周りには女性モデルや女性俳優といったコミュニティが非常にたくさん集まっているという性質が見えてきます。

 

 

このような、SNS上のコミュニティ分析は広告配信やインフルエンザのような病気の流行分析などで活用されています。例えば、SNSの中からコミュニティ構造を発見してあげることで、特定の商品に興味のあるコミュニティにだけ的確なタイミングで広告を配信したり、どのようなコミュニティで病気が蔓延しているのかなどを明らかにしたりすることが可能となります。

 

しかし、こうしたビッグデータの解析は簡単ではありません。特に難しいポイントとなるのがデータの解析時間です。ビッグデータはその名の通り非常に膨大なデータですので、そのまま計算しようとするととても長い計算時間がかかります。例えば先程のSNSの例をもう一度考えてみましょう。7人のユーザーからなる非常に小さなSNSから2つのコミュニティを見つけようとした場合、コンピュータはこの7人を2つに分けたときに取り得る全てのパターンを一つ一つ見ていき、その中から一番もっともらしいパターンを解析結果として出力する、ということをする必要があります。

 

問題になるのはこのパターンの数です。このパターン数は人数が増えるほど爆発的に増します。仮に50人のユーザーを分析しようとなると2つのコミュニティを見つけるだけでも1,225通りのパターンを見る必要があります。一般的にSNSの中に含まれているコミュニティの数は事前にはわかりませんので、実際には50人を2つに分ける場合、3つに分ける場合、4つに分ける場合…と取り得る全てのパターンをコンピュータは検証する必要があります。

 

このパターン数は50人規模のSNSであったとしても1084通り以上になってしまいます。このパターン数は、例えスーパーコンピュータ規模の計算性能をもってしても宇宙の歴史より長い時間が計算に必要となってしまう量です。

私の研究ではこのような膨大なパターンを皆さんの家庭や学校にあるようなノートパソコン1台であっという間に解析できるような賢いデータ解析アルゴリズムを開発しています。

 

世の中に存在するデータには、次数分布のべき乗則、クラスタ性、スモールワールド性といった様々な構造特性があります。

 

例えば先程のSNSの例でも、SNS上には3人組が多く含まれるという「トライアングル構造」がよく知られています。私はこの「トライアングル構造」に着目することで、賢い解析アルゴリズムを開発しました。

 

SNS上に存在するトライアングル構造は直感的には3人のユーザがお互いに仲良しであるということを意味しています。つまり、トライアングル構造を構成するこの3人は別のコミュニティに分断されてしまっては不自然なわけです。そこで、トライアングル構造が分断されてしまうような不自然なパターンを除外し、コンピュータが解析しなければならないパターン数を大幅に絞り込むというアプローチを採用しました。コンピュータの解析対象となるパターン数が格段に減るわけですから、解析効率をアップさせ計算時間を大幅に短縮することができるようになりました。

 

このアルゴリズムを用いて、日本の総人口1億人分のデータをもとにしたコミュニティ構造の解析をノートパソコンで行なうと、なんと60秒未満で解析が終わります。これは2018年現在で我々が知る限り世界最速の計算性能です。Twitterを分析する場合であれば0.004秒、まさに「瞬時」にデータ解析を行うことができます。コンピュータが必要のない計算をしなくてもいいように「余分な作業」を省くことで、飛躍的な計算効率のアップを実現させています。

 

興味がわいたら

映画『イミテーション・ゲーム』

コンピュータの父としても知られる数学者アラン・チューリングの伝記を基にした映画です。時代は第二次世界大戦の真っ只中。当時ドイツ軍が使用していた難攻不落のエニグマ暗号をチューリングが解読するまでの過程が映画では描かれています。エニグマ暗号を解読するためには、暗号文がどのようなパターンに従って、人間が理解可能な文章(平文)に変換されているのかを明らかにする必要があります。しかし、暗号文が取り得る平文の組合せは非常に膨大であり、当時の技術では現実的な時間での解析が不可能でした。このビッグデータに対してチューリングが挑んで行く姿は、今のビッグデータ解析にも通じるものがあります。彼が何にヒントを得てエニグマ暗号を破ったのか、興味のある方は是非観てみることをお勧めします。

[amazonへ]


『コンピュータはなぜ動くのか~知っておきたいハードウエア&ソフトウエアの基礎知識~』

矢沢久雄(日経BP社)

現代のコンピュータの基本となる仕組みが解説されている本です。高校物理レベルの電気回路から始まり、コンピュータを構成するハードウェア、プログラム、アルゴリズム、データ構造、データベースなどについて幅広く解説しています。コンピュータや情報を扱う大学・研究に興味があるけど、予備知識がまったくないという初学者にお勧めします。

[amazonへ]


『プログラムはなぜ動くのか 第2版 知っておきたいプログラムの基礎知識』

矢沢久雄(日経BP社)

上記で紹介した本の発展版です。この本ではプログラムがどういう仕組みで動くのかに焦点を当てて解説されています。上記の本を読破してしまった方、簡単だった方にはこちらがお勧めです。

[amazonへ]


『ビッグデータの正体 情報の産業革命が世界のすべてを変える』

ビクター・マイヤー=ショーンベルガー(講談社)

ビッグデータ解析が我々の身の回りのどのようなところで活躍しているのか、また、それらを活用した企業たちがどのように成功を収めたかについて論じた本です。コンピュータやデータ分析に詳しくない方でも簡単に読めるのではないかと思います。

我々は日々、どのようなデータを生み出していて、それらがどのような場所でどのような価値を生んでいるのだろうか?そしてそこにはどんなリスクがあるのか?我々の知らないところで日夜行われているビッグデータ解析。その一端をこの本を通じて知ってもらえれば幸いです。 

[amazonへ]