データ粒子化による高速高精度な次世代マイニング技術の創出
宇野 毅明 （国立情報学研究所＆総合研究大学院大学）
http://research.nii.ac.jp/~uno/index-j.html
e-mail: uno@nii.ac.jp
2016年12月23日 河原林ERATO Winter Festa

データマイニングとはデータの中から、おもしろいもの、特徴的なもの、を見つける問題＋ 全体的な特徴なら、統計や主成分分析や機械学習＋ ある種の極値、コストが良い物なら、最適化＋ データマイニングは、多様、局所的なものに注目
クラスタリング、パターンマイニング、セグメンテーション、、、
HC

OOビッグデータにおけるマイニング• マイニングは、上流の手法で使う「構造」を見つけ出す
クラウド

知識・価値

センサ
プライバシ

統計検定

可視化

アルゴリズム
ゲーミフィ
ケーション
クラウド
ソーシング

シミュレーション

機械学習
特徴抽出

マイニング

タグ付け
画像映像
位置情報
ビッグデータ 自然言語解析
センサデータ分かりにくいデータ• 位置情報などのセンサデータ、非常に正確で密度も濃いが、だからと言って意味が取りやすいわけではない• 抽象度の高い、意味の濃い部分（粒子）は、理解しやすい
デパートで買い物した？

○時○分にここにいた

知識shopデータ

point A

多くの人が寄り道している

parkpoint B機械学習• ○と×を分けるルールを、データから見つける手法• 分け方／切り方により多くの方法がある• 解（切り方）は、基本的に「理解しがたい」

粒子による学習• 粒子を使って解を作ると、すっきりする

このへん
このへん
• 分類の「意味」を捉えやすそう抽象化、現状は？
• 抽象化をすべきマイニングは、「利用しやすさ」の発想に欠ける• 手法・問題ごとに場当たり／散発的で、「理解しやすさ」が欠落
 開発の容易さ、精度向上、理解しやすさ、技術の統一的な俯瞰

知識・価値検定
機械学習

自然言語

粒子化データマイニング

ビッグデータ可視化

なぜ抽象化か予測に関わる属性を見つける  大量の属性、組合せ「この属性が効いています」と言われても、何なのかわからない儲け方が知りたい 仕組みや理由が知りたい「今こうすれば儲かる」でも、明日儲かるかどうかわからない
きっちり理解できることでないと、安心して使えない
つまり、「データと理由が何なのか、知りたい」• 現場では、このような感覚を持つ方が急増している
しかし、現場でもビジネスでも学術でも、この問題意識に重心を置いた研究は少ない

クラスタリング• クラスタリングは、大きく３つに別れる＋ データがラベルがあり、データ空間をラベルで分ける＋ ラベルがなく、少数のものに(ときに階層的に)分ける＋ ラベルがなく、似た物が集まった物をたくさん見つける• ３つ目は抽象化。多様性の高いデータに良い
機械学習の特徴まとめ、可視化の材料、コーパス作り、名寄せクラスタリングの現状• １つ目、２つ目は多くの研究があり、現実的にもうまくいっている• ３つ目はうまくいっていない
大量の微細解、ばらばらのサイズ、乱雑な粒度、ゆらぎ、 、 、グラフカットによるクラスタの例

 サイズ

クラスタの大きさをソート

小型機が着陸失敗、日本人女性重傷か…ネパール
東京株、午前終値は１５２円高 ８カ月ぶり９７００円台回復
オセロ松嶋が体調不良、笑福亭鶴瓶のみ出演へ
トヨタの前３月期、豊田社長ら首脳３氏が報酬１億円超
タケノコ採り４人無事 秋田・仙北で一時不明…

1万テキスト100万トピック
 クラスタデータを見えるようにする• 密な部分の境目があいまいなので、解が大量／計算が大変／精度が出ない
 境目がクッキリしていればいいのに、、、• 画像処理だったら、＋ コントラストを強めてエッジを強調する＋ ぶつぶつのノイズを消してフラットにする• 中身がわかりやすくなり、認識精度も上がる

books
bottles

データでも同じことをしよう！

PC
pens

papers新しいアプローチ： データ研磨
データ研磨
確実な根拠に基づき、データの「揺らぎ」を消す
密グラフ

系列データ

パターン

• 「明らかにこうだろう」を変更。損失なく、網羅性も担保• 揺らぎが消え、大量の類似解はまとまるグラフ研磨：周辺情報を利用
２つの頂点が同じクラスタに属するかどうか、周辺情報で判断
実行可能仮説A と B が同じクラスタにいる  A と B は共通隣人を多く持つ
AAの隣人 ∩ Bの隣人 ≧ k  AB 間に枝をはる
Aの隣人 ∩ Bの隣人 ＜ k  AB 間の枝を切る+ これを一度に全部行い新しいグラフを作る+ 変化しなくなるまで繰り返す• 友達集合の類似性を使うと、クラスタの粒度がそろう

BABなぜ今までは無かったか• アイディア自体は簡単。でも、無かった。
★ 「データを変えてしまっていいのか」という疑念
 中規模の構造は保存するようにしている（誤字やピンぼけの修正のようなもの）★ 計算の難しさ （密部分を網羅的に見つける）
 新しいモデル化で対応
 最新の高速アルゴリズムを利用友達の友達• 「v」さんと友達を共有している  「v」の友達の友達• 「v」さんは、友達の友達とだけ比べればいい 比較対象がものすごく少なくなる（が100万点でも、友達の友達は100-1000人くらい）• さらに、離散アルゴリズム技術で、「共通友達」のカウントを高速化

uvデータ研磨の威力• 帝国データバンク様、企業間取引データ
点：企業、線：取引ある、似てる：共通友達 PMI ≧0.6
研磨前 研磨後
頂点数

3,282

枝数

35,168 73,132

3,282

クリーク数 32,953

343

買い物データを用いた、顧客が健康志向かどうかの予測精度
クリーク Newman グラフカット
研磨前

60.60% 59.70%

研磨後

71.36% 62.76% 67.78%

60.03%

人工生成したベンチマークデータにおける、意味的構造の検出率
研磨

Newman グラフカット

ノイズ10% 100.00% 68.74%

76.10%

ノイズ40% 99.69%

77.03%

7.91%

結果：データ研磨• 数が妥当。大きさの分布も良い。中身も妥当
境目は明確になったようだ
データ研磨によるクラスタの一例
トヨタ14年3月期営業利益は1兆8000億円へ、市場予測下回るホンダの今期連結営業利益は前年比＋43.2％の見通し、市場予測下回る
ＮＴＴドコモの今期営業利益は0.3％増益を予想、市場予測をやや上回る
ファーストリテ、12年9―13年2月期営業利益は前年比＋5.3％
オリンパス、今期営業利益予想を前年比‐1.5％の350億円に下方修正
日産自、12年4―12月期営業益は18.4％減の3491億円
ソニー、今期当期損益予想を200億円の黒字で変更せず
ニコン、13年3月期営業利益予想を前年比‐40.1％に下方修正
三菱重が13年3月期営業益予想を上方修正、予測上回る…

成果と未達成項目

粒子化
局所

実利用

集中

実例
分割

ノウハウ

対応
広がり・・・

系列
問題意識のフィードバック

アルゴリズム
高速化
関係性

部分構造
対話性
外部知識

着目点

Experimental Result• Set k1 = 2, and k2 = 5 , and #vertices = 10000
cluster size = 20x20
noisepatterns• Polish the matrix by using only rows
Enumerate concepts of size no less than 3(on column direction)#patterns
classified bysizes
originalclusters

14052
9320
388
110000000000000761640
791110000
10455721641
50001
113308211278332017448256527791547917505612416927308078203891120288
62309
27576
9674
2543
322
20000
10001

データ研磨の高速化
4• 研磨されたグラフ、だいたい研磨されたグラフは、少数のクリークが重なりあった、単純な構造をしているため、同型な頂点が数多く存在する
 同型な頂点を一つにまとめることで、計算が高速化される• データが含む粒子の数が多いと高速化されないのだが、我々が解析したいデータは粒子がそれほど多くない（はずである）ので、現実的には計算が高速である• 実データでの実験では、粒子数が小さく、重なるクリークも少ない
ため、10倍程度の高速化が実現できている （反復数の半分程度）

データ研磨の数理
4• 「Aと B両方に隣接する頂点が k個以上なら、AB 間に枝をはる」＋ 頂点数 γkで内部の最小次数が (γ+1)k/2 以上の部分グラフは、このデータ研磨により必ずクリークになる＋ 頂点数 γkで内部の最小次数が (γ-1)k/3 以上の部分グラフは、

γ− 1 
密度 δ が 3(1 −δ) < 
 γ 2を満たすと、必ずその密度が増加＋ 研磨されたグラフの極大クリーク数は nk 以下になる

婚活におけるお勧め (愛媛結婚支援センター)• プロフィール検索では、出会い人の範囲がせまくなりすぎる 「好みが似ている人は人格も似ている」仮説から閲覧した異性の類似によるユーザ粒子を使って推薦お見合いを受ける率が ２．２ 倍に上昇！

総務省 地域情報化大賞 特別賞
5年間活動してきました。「ビッグデータのお勧め」で、初めて、結婚してもいいと思える人と出会えました！

Finding dense subgraphs and Bid rigging
50
密部分抽出と地方公共団体競争入札• Extracting particles from real big data
Chiba-city fiscal 2005 (172 items, 276 companies)
to finding sets of items bid by groups of companies
and groups of companies bidding a set of items simultaneously• Combination of NMF for matrix computation and merging clusters
according to “density first search”

Designing Visual Interactivity for Data Engagement
誘導的ビジュアルインタラクティビティの実現

52• We have identified components in data engagement toward knowledge creation:
知識創造を促すデータ利用の因子- peruse individual data items- glance a series of individual data items- peruse a data particle- glance a series of data particles
個々のデータの精査と走査
データ粒子の精査と走査• focusing （注視対象）• context-switching （異なる近接性の転換）• course-grounding （理解のprovenance）• multiple proximities 多様な近接性• an interactive visual environment
to engage in historical data
時間基軸を有する
歴史年表データの粒子化と可視化環境- temporal axis
- symbolic axis
- data particles (semantic axis)• nodes-linked network (expanded phenomena)• lines-intertwined meshwork (Tim Gold)
連結と交叉による知識構成[HistoInformatics2016]

データ解析ハッカソン (ソレイユデータ道場)• ハッカソンとは、限られた時間で課題を解き、その質を競うコンペティション• データ研磨で得られた解を元に、ビジネスアイディアを創出するハッカソンを開催した
・東京・大阪・愛媛同時開催、参加者100名以上
・大量の、ユーザの解析行動ログを入手！
・研磨の解を元に、多種のアイディアが創出された• 参加者の解析から、データ研磨の解がどのように利用されるか、何に着目されているかをうかがい知ることができた＋ 研磨解はデータの抽象的な理解を助けている＋ ２つ以上のものを比較する際に、周辺情報を提供している＋ 研磨解の隣の（類似する）解に興味着目が多い

データ解析2.0• データから物事と現象を深く理解できるようになる• 箱物とブラックボックス技術に皮をかぶせる仕事から、データの意味を知り、価値を創造する仕事へ• 小さな活動をする個人事業主やNPOもデータ解析• 個人が自身の主観に基づく理解と解析結果を発信し、その集合知として社会が持つ「データに対する認識」が決まる時代

ビッグデータ

理由の解明

データ全体の俯瞰

理解しやすい解

隠された
意味の獲得

ポスドク・研究協力募集！！
• モデルが新しく、応用がたくさんある。適用しがいがあるデータをいじって、実際に面白みを体感できる• 計算の筋や方向性が新しく、今までにない観点からアルゴリズムが研究できる• 収束性・精度保証、クラスタ内の比較、クラスタ間の関係、それらの作る局所的・大域的な構造など、数理的に面白いトピックがたくさんある• 神田にラボがあって、広々していい雰囲気中の人もゲストも、楽しく過ごし、議論できる

研究体制
データ研磨
アルゴリズム宇野 毅明 情報学研究所

意味構造解析
機械学習
山本 章博 京都大学

実応用、可視化
ビジネスデータ
羽室 行信 関西学院大学
インタラクション
ユーザ解析
中小路 久美代 京都大学

実データとユーザ行動の解析から課題抽出を行い、データ研磨アルゴリズムと粒子の持つ意味構造の解析手法を構築

相互類似関係を考慮したグラフ研磨の応用- 商品間の絆を求めて 中原 孝信 (専修大学)、岩崎 幸子、羽室 行信（関西学院大学）、宇野 毅明（NII）
流通・小売業の現場担当者が意味解釈可能な相関ルールを発見し、棚割りやクロスマーチャンダイジングに活用できるグラフ研磨手法を開発すること。
問題点1: 列挙されるルールが膨大になってしまい、重要なルールをフィルタリングできない。
問題点2: 膨大なルールが列挙されるため、全体を把握することが困難である。適切な視覚化方法が必要
問題点3: 出現頻度の高い商品を持った常識的なルールばかりが列挙されてしまう。

Friendsによるデータ研磨

各ノードの順位が1,2位の枝お互いの類似度の順位が高い枝を残し、それ以外を削除

「大規模離散構造データからの超高速パターン発見：深い意味の獲得に向けて」（宇野チーム・有村他）
配列情報とRMSDを用いた3次元点集合マッチング

アイテム集合列挙に基づく最適な順序付き決定木の高速発見(○佐々木耀一(北大M2)，渋谷，伊藤，有村，宇野)(○長部和仁(北大M2)，宇野，有村)
aacbdb「もし大規模3次元点集合
順序付き決定木 順序ナシ決定木
データの近似検索が高速に 「もしすべてのサイズと信頼できたら？」度の決定木ルールを残らず高速に調べられたら？」dedfce

CCATA

回転y = RxTG2C

GA

G

A

平行移動
y=x
図:パターンの回転と平行移動+v
A 可能な応用： ウイルスデータ・ポイントクラ
ウド・時空間配置データの大規模解析
 研究成果：マッチングの全列挙とスコアの下限枝刈りを用いた高速称号アルゴリズム
 実験：ウイルスデータベース上で全対全マッチで生物学的仮説の検証に応用

 可能な応用： 信頼度付き学習・統計検定・
プライバシー
 研究成果：制約下で全ての「変数順序付き決定木」から，最適決定木を厳密計算可能
 頻出マイニングと同じ計算量
 目標： 最適化（済）・計数・ランダム生成

本研究は，下記のJSTビッグデータCREST研究チームとのチーム間共同研究です：
伊藤公人（北海道大学・CREST西浦博チーム分担者），渋谷哲朗（東京大学・CREST加藤直樹チーム分担者），津田宏治（東京大学・CREST津田チーム代表），瀬々潤（産総研・同CREST共同研究者），
湊真一・石畠さん（北大・基盤(S)）

df