理論談話会#3 吉野さん 議事録

■内容
BDDを経路列挙に利用できないか

頻出パターンマイニング
↓これを解くアプローチ
パターン成長アプローチ

BDDからZDDは生まれた(どちらも二分木表現)
ZDDは組み合わせ表現に特化
BDDとZDDは冗長接点削除規則が異なる

SeqBDD(系列二分木決定グラフ)を使う

WeightedSeqBDD

頻出部分列問題のためのSeqBDDの構築アルゴリズム

閾値が下がるということはウェイティングの意味がない

系列が短い場合は他の手法が有効である場合が多い

系列データを扱うときはSeqBDDが有用
毎日の系列データを分析する際は有効

おいで地区に適用する場合はZDDでよい


■質疑
羽藤：最後の出して見て．時間系列のデータなんで，同じようなルート通ってるんだけど，少し違うからSeqBDD？


吉野：ZDDでは時系列を区別できない

羽藤：縦軸にtをとればよいのでは

吉野：

羽藤：禁則を入れればいいんじゃないのか

大山：有効グラフのZDDはないのか

吉野：あります，それもひとつのやりかたですけど，入ってくる次数と出て行く次数を分けて，ZDDを普通に作ると，ノードに入ってくるのと出て行くのを分けるので表現できる．

時空間だとそれでも大丈夫かもしれないけど，重なりがあったら分からない

羽藤：所感の4つ目と5つ目とかは吉野さんの思っているいいこと？
データベースの設定として

羽藤：あるいはPT調査としての圧縮方法としてのSeqBDDとかなら面白い
そのでーたを用いて配分を行うとかだったら面白いのではないか

吉野：データのストックということ？

羽藤：BDDのデータをついるプロセスがモデリングのプロセスに一致する．

計画学のときに発表する際に，陸前高田のデータでこれをつかってというのはないが，違うことに適用したら面白いのではないか．

データベースから似たものを見つけることができる．
そういう使い方が公共交通の中にもないのかという質問

検索の際に組み合わせ的に似ているものを探すのではなく，組み合わせるものを検索できると面白い

あるアクティビティパターンとあるアクティビティパターンを組み合わせるとコストが安くなりますよということが検索できたら，そういう組み合わせ問題の解き方のほうが新しいというか

吉野：住民のアクティビティがどれだけにているかに使おうとしていた

羽藤：ACCとBDDが組み合わさるとコストが安くなるみたいなことが分かる操作関数を探るとかはあるかもしれない．そういうコスト関数を探す．
サービスを前提としたアルゴリズムの開発がおもしろい．
簡単な組み合わせ問題でやってみるべき．

羽藤：時間がずれてたら，AからB，BからAっていうものも組み合わせることができる
例題的なものを探して(5角形都市とか)．
探せるところにアルゴリズムの意味がある．
一筆書きのパスを作る

吉野：一人の人を固定して，組み合わせるものを探すっていうことです

羽藤：最適化問題の解き方の視点からの提案はすごく新しい．

大山：重みはノードとノードの間に当てるものなのか，系列に与えるものなのか．

吉野：閾値はリンクとリンクの間にあるやつを，結局はそれぞれの発生確率にかけるんですけど，このときは1なので

本来はエッジにかかっているものを考慮する

大山：S1ごとに確率がある？

吉野：もともとあるデータをもとに，確率というよりはデータから得られるもの

大山：パターンの頻度とか確率を計算できるのが全列挙方の強み

AAAAA，BBBBBは文字は違うが，すごく似ているみたいなことが出てくると面白い．

吉野：文字列の連なり方みたいなものを入れてやると，そういうものが出てくるかもしれない

羽藤：経路では？

大山：時間上に射影すると，違うパターンだが本質は似ている

羽藤：ルービックキューブみたいな問題ならば簡単．遺伝子解析とかのやり方を適用するのもあり(修士1年生)．後藤とかはあり．
後藤の場合はWifiで，信号パターンがでてくるので，似ているパターンが観測されたら経路を決めることができるようになる．全部のパスを通っているのかって言うパターンがとれていれば，経路を決めることができる．データベースの形成方法はこのSeqBDDがありなのではないか．


大山：正答率っていうのは

吉野：マイニングがちゃんとできたかという意味

羽藤：経路パターンがあったときに，あるものが出たときに次にこれが出やすいというものがデータベースから探すということができる，システム方程式見たいな物を使ってやっている．

吉野：0にすれば，必ず一致する．

大山：今のサポート値みたいなものがあると，

羽藤：システム方程式がデータマイニング敵に出てくるところがミソ
観測したデータが構造化しながら構築できるのは大きい．

羽藤：これは好き嫌いが出る．思いが一方通行．
似たパターンを推論できるのは大きい．
同じアドレスが観測されたところでOD表が作れる見たいのも野がオーストラリアではやっている．

福山：どのパターンが一番使われているのかという解釈はグラフからどうするのか

吉野：どっちかというと，索引的に使うことはできる．閾値で頻出というものは表現する．

三木：頻出か頻出じゃないかで閾値が決めれて

吉野：どれだけ頻出のやつだけ生き残らせるかということはできる．

三木：閾値を下げていって当てることができるようになる．

羽藤：サービスを前提とすると面白い．使えそうな感じがする．

森田：シェアリングでZDDってどういう使い方?

吉野：ポートの組み合わせ？

羽藤：吉野が使おうとしているシェアリングを説明してやって

吉野：運転者がどういう風に通るかっていう経路を圧縮してデータとしておくことで索引ですぐ引ける．パスの組み合わせを急遽考え直すことに利用できる．

羽藤：新たにマッチする人を探すときにZDDを利用できる

大山：新しいリンクを追加したときは高速列挙できるのか

吉野：それは厳しいかもしれない，なくなるのはぜんぜんいける．