いいプログラムは コーディング技術だけではない

Presentation on theme: "いいプログラムは コーディング技術だけではない"— Presentation transcript:

1 いいプログラムは コーディング技術だけではない
宇野 毅明 　（国立情報学研究所 　　　　　　　　＆総合研究大学院大学） 2007年3月22日 JOI合宿

2 簡単に自己紹介 名前： 宇野 毅明 年齢・職種： ３６歳、助教授 研究分野： アルゴリズム理論 － コンピュータプログラムの設計手法の理論
　 － コンピュータプログラムの設計手法の理論 　 － 速いコンピュータを作ったり、プログラミングの腕を競うの 　　　ではなく、「設計方法の違いによる性能の向上」を目指す 最近の研究： ゲノム情報学やデータマイングで出てくる巨大なデータベースの基礎的（とはいっても非常に時間のかかる）な解析を超高速で行うアルゴリズムの開発 趣味（日課？）： 子供と遊ぶこと

3 アルゴリズム技術の粋

4 世の中での「プログラミング」 ・ 情報化社会において、コンピュータプログラムはありとあらゆる場所で使われている、もはや「言葉」と同じくらい基本的で重要なツール ・ それゆえに、プログラミングは、単純労働に近い位置にある 　－ SEのシステムを組む、という作業は、 　　　　　　　プログラムではなく全体の設計 　－ ゲノムなど、○○情報学の分野でも、あくまでプログラミングは道具であり、真の目的とは一線を画する ・ 昔はプログラムが組めるだけですごかったんだけど．．．

5 プログラムの美学 ・ プログラムの普及がプログラムを単純労働にしたが、それはプログラムの価値を低くしたわけではない
 誰でも文章を書けるが、質の高い文学作品は誰にでも書けるものではない ・ プログラムにはプログラムの粋がある ビジネス モデル 豊かな 生活 情報 システム 自然 科学 技術 の粋 プログラム

6 技術の粋とは ・ 「日本にはOSを作れる人材がいない」と言われることがある
・ これは言いすぎだと思うが、「高い技術を持ったプログラマーが少ない」というのはあっていると思う ・ OSのような高度なシステム作りに要求される技術は「大規模なシステムを、論理的に正しくデザインすること」 　 いわば、車やジャンボジェット作りに似ている 　　（1万、10万を超える部品を組立てて、安定した製品を作る） ・ 他の粋として、「速いプログラムを作る」というものがある 　 こちらは、F1カーや、ジェット戦闘機作りに相当 　　（目的に特化して、どこまで高性能にできるか、限界に挑戦）

7 プログラムを速くするには ・ プログラムを速くする方法の１つは、並列化をすること  クラスタコンピュータ、デュアルコア、メニーコア
　 クラスタコンピュータ、デュアルコア、メニーコア ・ もうひとつはプログラムコードの改良 　－ 使用言語を変える 　　  インタープリタ系(perl,lisp)からコンパイル系へ(C,PASCAL) 　－ キャッシュのヒット率を上げる（ループを開く） 　－ ディスクIO、メモリIOを高速化する（バッファを自分で管理） ・ その他にも、「アルゴリズムの改良」 　 アルゴリズムは、いわばプログラムの設計書。設計を変えることで、高速化を図る

8 アルゴリズム理論のアプローチ ・ アルゴリズム理論では、解く問題の大きさに対する計算時間に注目し、増加の仕方が小さくなる設計法を考える
　アルゴリズム理論のアプローチ ・ アルゴリズム理論では、解く問題の大きさに対する計算時間に注目し、増加の仕方が小さくなる設計法を考える ・ 「増加の仕方」にしか注目しないので、コーディングの技術など、問題の大きさに依存しない高速化部分は無視できる ・ 大体の場合、「最悪の場合の計算時間」 を算定するので、リスクが小さい ・ 「実際の計算時間」「小規模だと単純なものに負ける」 が弱点

9 情報爆発時代のアルゴリズム

10 ・ 近年、IT技術の発達で、大規模なデータが半自動的に収集できるようになった （POS、web、文書、顧客データ、財務、利用者、人事…）
データ中心の科学 ・ 近年、IT技術の発達で、大規模なデータが半自動的に収集できるようになった 　　（POS、web、文書、顧客データ、財務、利用者、人事…） 既存のデータを使って何かを得たい データの選別 モデル化 データ処理 いわば、データを出発点とした問題解決の科学 （人工知能、データマイニング、自然言語処理、セマンティックweb… 近年の情報学でもメジャーな研究スタイル）

11 データ中心科学の特徴 半自動で集められたデータであるので、データは通常、巨大である。しかし各項目が持つ属性は少なく、疎である。
・ データが整形されていない 　目的がはっきりしない、あるいは異なる目的のために集められたデータを用いるため、必要なものがすぐ取り出せるとは限らない。また、ノイズや不正確な情報も含まれうる。 ・ 目的関数があいまい 　データが情報の塊のようなものなので、そこから得られるものはやはり情報であることが多い（知識、特徴分析といったもの）。それら情報の価値は数理的な尺度では計りにくい。また、従来の最適化とは異なる尺度を用いることが多い。（グラフクラス、シークエンス、情報量、隣接性、類似度、頻出度・・・） ・ データが巨大で、構造を持つ 半自動で集められたデータであるので、データは通常、巨大である。しかし各項目が持つ属性は少なく、疎である。 ・ データ処理は比較的簡単なものが多い データ処理の計算は、最適化のような複雑ではなく、 組合せの検索や整形などいくつかの簡単な処理の組合せ

12 より高度な解析のため、より複雑な基礎処理アルゴリズムが必要
　今、巨大データにできること ・ データベースの構築（データ構造） ・ キーワード検索 ・ ソート、整列 ・ フィルタリング ・ 統計量の計算 ・ 圧縮 ・ 最短路検索 ．．． １次的な処理が多い。組合せ的な構造を処理するものは少ない より高度な解析のため、より複雑な基礎処理アルゴリズムが必要

13 複雑かつ大量の計算を効率良く行う手法の開発が重要
データ処理の変化 ▪ 不ぞろいなデータから有用な情報を得るには複雑で豊かなモデルを解く必要がある ▪ そのためには、解く問題を複雑にする必要がある 　　▪ 比較・統計量  全対比較・組合せ的な統計量 　　▪ キーワード検索  パターンマイニング 　　▪ 完全一致  類似検索 　　▪ 最適化  列挙 ・ このように処理が変化すると、既存のアルゴリズムを用いて行った場合に、非常に時間がかかることがある 例） 全対比較を通常の検索を用いて行うと、レコード数だけのクエリを必要とする データベース 複雑かつ大量の計算を効率良く行う手法の開発が重要

14 データ処理に求められるもの ［多様性］ 個別の案件に対してモデルが変化 － ［基礎問題］ 解く問題が基礎的であること
 問題設定の変化に対して柔軟であること 　－ ［基礎問題］ 解く問題が基礎的であること 　－ ［単純な構造］ アルゴリズムのアイディアが単純であり、 　　　　　　　　　　　　汎用性の高いレベルで構築されていること ［速度］ 大規模データに対しても高速に動作すること  コードの改良より、良いアルゴリズムの開発 　－ ［疎成］ データの疎性、スケールフリー性を利用して 　－ ［計算構造］ 計算構造の改良により、無駄な探索を省く 　－ ［スケールメリット］ 多数の操作を一度に行うことで高速化 ［正確性］ なんらかの意味で正確な計算を行うこと 　－ ［列挙］ 全ての解をもらさず重複無く発見 　－ ［精度保障］ 誤差の範囲を保障する

15 アルゴリズム理論の利点 ・ 大規模な計算には、アルゴリズム理論に基づいた技術が有効
　アルゴリズム理論の利点 ・ 大規模な計算には、アルゴリズム理論に基づいた技術が有効 　 アルゴリズム理論による高速化は、問題の大きさに対する計算時間の増加を抑える 　 計算の結果は変化しない 100項目 2-3倍 100万項目 10000倍 データが巨大になるほど、アルゴリズム改良の加速率は上がる

16 頻出パターン発見

17 データベースを分析したい ・ データベース構築と検索は、もうできるようになった （絞込みや、あいまい検索はまだ改良の余地があるけど）
　（絞込みや、あいまい検索はまだ改良の余地があるけど） ・ より詳しくデータを解析するために、データの特徴を捉えたい 各種統計量（データベースの大きさ、密度、分布）よりも、深い解析がしたい  組合せ（パターン）的な構造に注目 （どういう組合せ（パターン）が どれくらい入っているか） ・ 組合せ・パターンの個数は指数的に 増えていくので、全てを尽くすのは無理  多く現れるものだけに注目 データベース 実験1 実験2 実験3 実験4 　● 　▲ ATGCGCCGTA TAGCGGGTGG TTCGCGTTAG GGATATAAAT GCGCCAAATA ATAATGTATTA TTGAAGGGCG ACAGTCTCTCA ATAAGCGGCT 実験結果 ゲノム情報

18 頻出パターンの列挙 ・ データベースの中に多く現れるパターンを全て見つける問題を 頻出パターン列挙（あるいは発見、マイニング）問題という
　データベース： トランザクション、ツリー、グラフ、多次元ベクトル 　パターン： 部分集合、木、パス・サイクル、グラフ、図形 データベース 頻出する パターンを抽出 ・ 実験1● ,実験3 ▲ ・ 実験2● ,実験4● ・ 実験2●, 実験3 ▲, 実験4● ・ 実験2▲ ,実験3 ▲ 　　　　． 実験1 実験2 実験3 実験4 　● 　▲ ATGCGCCGTA TAGCGGGTGG TTCGCGTTAG GGATATAAAT GCGCCAAATA ATAATGTATTA TTGAAGGGCG ACAGTCTCTCA ATAAGCGGCT ・ ATGCAT ・ CCCGGGTAA ・ GGCGTTA ・ ATAAGGG 　　　　． 実験結果 ゲノム情報

19 多く現れる  頻出する 多く現れるものを見つけるために、多く現れるとは何か、を決める ・ データベースが項目の集まりだとする
多く現れる  頻出する 多く現れるものを見つけるために、多く現れるとは何か、を決める ・ データベースが項目の集まりだとする ・ パターンに対して、そのパターンを含む項目を出現という ・ 出現の数（頻出度）が閾値より大きければ、良く現れるとする （含む、の定義は、集合で行ったり、文字列の 包含、グラフの埋め込みなどで定義する） パターン XYZ {A,C,D} 項目 AXccYddZf {A,B,C,D,E}

20 トランザクションデータベース ・ パターンとして、集合を考える　（集合：ものの集まり。ここでは {1,2,…,n}。部分集合は、この中からいくつかを選んだもの。{1,4,7} など。） トランザクションデータベース： 各トランザクション T がアイテム集合 E={1,…,n} の 部分集合であるデータベース － POSデータ（各項目が、客1人の購入品目） － アンケートのデータ（1人がチェックした項目） － web log （1人が1回のwebサーフィンで見たページ） － オプション装備 （車購入時に1人が選んだオプション） 1,2,5,6,7 2,3,4,5 1,2,7,8,9 1,7,9 2,7,9 2 D ＝ 実際のデータは、大きくて疎なものが多い パワー則、スモールワールドが成り立つ

21 集合の出現と頻出度 集合K に対して： K の出現： K を含む D のトランザクション
K の出現集合 Occ(K)： K を含む D のトランザクション全ての集合 K の頻出度 frq(K)：　 K の出現集合の大きさ 　{1,2}の出現集合 ＝　{ {1,2,5,6,7,9}, {1,2,7,8,9} } 1,2,5,6,7,9 2,3,4,5 1,2,7,8,9 1,7,9 2,7,9 2 T ＝ 　{2,7,9}の出現集合 ＝　{ {1,2,5,6,7,9}, 　　　　{1,2,7,8,9}, {2,7,9} }

22 与えられたトランザクションデータベースと最小サポートθに対して、頻出集合を全て見つける問題を考える
・ 頻出集合：T の定数θ個以上のトランザクションに含まれる集合 　（頻出度がθ以上の集合）（ θを最小サポートとよぶ） 例） データベースT の3つ以上のトランザクションに含まれる集合 ３つ以上に含まれるもの {1} {2} {7} {9} {1,7} {1,9} {2,7} {2,9} {7,9} {1,7,9} {2,7,9} 1,2,5,6,7,9 2,3,4,5 1,2,7,8,9 1,7,9 2,7,9 2 T ＝ 与えられたトランザクションデータベースと最小サポートθに対して、頻出集合を全て見つける問題を考える

23 応用：バスケット分析 ・ スーパーなどの小売店舗で、同時に購入される事の多い品物の組を知りたい ・ 客が購入した品目  トランザクション
・ 客が購入した品目  トランザクション ・ 品目の組で、多くの客が購入したもの  多くのトランザクションに含まれるアイテム集合  （あるθに対する）頻出集合 ● 牛乳、弁当 ● お茶、弁当 ● おにぎり、雑誌 ● はさみ、のり ● ラーメン、はし ● こっぷ、皿 ● 弁当、おにぎり 　　　．．． 「おむつとビールの組合せが良く売れる」 という発見が有名

24 応用：データベースの比較 ・ ２つのデータベースが、意味的にどの程度似ているか知りたい  大きさの違い、ノイズは無視したい
・ 各アイテム、属性などの総数だけでは、組合せがわからない ・ 組合せを細かく見ると、ノイズに振り回される データ ベース 頻出集合を列挙することで、 組合せ的な特徴を比較できる ・ いろいろな言語の辞書データ ・ 異なる種のゲノムデータ ・ 文書集合の単語データ（新聞のデータ、雑誌のデータなど） ・ 顧客のデータ

25 応用：分類ルール、特性の発見 ・ データの特徴を現す規則、あるいは正例・負例を分類するような規則が知りたい （A,B,C が含まれている、A,B が含まれれば、C が含まれる、など） ・ 多く現れる組合せを用いないと、仮定部分を満たすものが少なく、ルールとして意味がない ・ 組合せを細かく見ると、ノイズに振り回される 頻出集合を仮定に用いることで、 信頼度の高いルールを 効率良く見つけられる データ ベース データ ベース 正例 ・ 実験データ ・ 利用者履歴データ、マーケッティング 負例

26 研究の歴史 ・ 頻出パターン発見問題はデータマイニングの基礎的な問題
 星の数ほどの論文がある （Google Scholarで5000件） ・ 1990年代から、「大きなデータから知識を得たい」という 　　スローガンの元、研究されている  「巨大データを扱うこと」を前提としている ・ 1990年ごろ集合をパターンとしたものから始まり、 極大なもの、飽和集合、誤差つき．．．とバリエーションができ、 パターンの種類も、集合から文字列、文字シークエンス、集合シークエンス、パス、ツリー、グラフ．．． と増えてきている

27 アルゴリズム研究の歴史 ・ アルゴリズム的には － 1994年 Agrawal らの apriori （解の大きさごとに解候補を
生成してからデータベースをスキャンして頻出度を計算） － 1998年 Bayardo のバックトラック － 1998年 Pasquir らによる飽和パターンの提唱 － 2001年 Burdick らによる MAFIA （データをビット列で格納して、 　　　演算を高速化） － 2002年 Zakiによる CHARM （枝刈りを利用した飽和集合列挙） － 2002年 牧野らによる、極大パターンの列挙の困難性の証明 － 2003年 有村宇野による LCM 　　　　（初の多項式時間飽和集合列挙アルゴリズム）

28 頻出集合の列挙

29 どういうアルゴリズムがあるのか、見てみよう
頻出集合発見用のプログラム ・ 頻出集合発見は、データマイニングと呼ばれる最近興ったデータ解析の中でも基礎的な問題なので、プログラムが多く作られている ・ 入力データ、出力する解、どちらも大きいことが多いので、計算速度は非常に重要 ・ しかも、アルゴリズムの設計しだい で、パフォーマンスが大きく変わる ・ 国際プログラミングコンテスト でも、こんな感じ。ばらつき大きい （時間軸は対数） どういうアルゴリズムがあるのか、見てみよう

30 プログラムを作ろう ・ 問題は 入力： トランザクションデータベースDと閾値 θ 出力： 全ての頻出集合出現
・ さて、どんな方針でプログラムを作りましょうか （これがアルゴリズムを考える、という作業） 作戦１：部分集合１つ１つについて頻出度を計算する  計算時間は O(2n|D|) 　　　（n=アイテムの数、|D|＝データベースの大きさ）  n=30、|D| =1000 くらいでも大変なことになる もう少し工夫しないと

31 計算時間は、どうなるべきだろう？ ・頻出集合の数は最高で 2n個になるから、計算時間 O(2n|D|) は、|D| の部分を除けばある意味で仕方ない？  そんなことはない。そんなにたくさん答えが出てくるような計算は、そもそもしたくない  つまり、解（頻出集合）の数はそんなに多くない、と思ってよい  逆に考えると、解を出力する部分の計算は避けられない つまり、「これだけは最低かかる」 ・そこで、「解１つあたりの計算時間がどうなるか」に注目しよう

32 頻出集合の単調性 ・ 工夫をするためには、何か問題の特徴をつかまなくてはいけない 111…1
・ 使えそうなのが、「頻出集合の部分集合は必ず頻出」、というもの（単調性という）  つまり、ハッセ図（包含関係を 図示したもの）の上では、 頻出集合が存在する エリアはつながっている 頻出 111…1 000…0 φ 1,3 1,2 1,2,3 1,2,4 1,3,4 2,3,4 1 2 3 4 3,4 2,4 1,4 2,3 1,2,3,4 これなら、うまいことたどれば、 頻出集合をすばやく全部見つけられそう

33 重複に気をつける ・ また、よくよく見ると、「どの頻出集合も、空集合（アイテムが 何も入っていない集合）にアイテムを１つずつ追加して作れる
・ また、頻出集合にアイテムを追加して、頻出でなくなったら、その後いくら追加しても2度と頻出にはならない 全ての追加の仕方を尽くせば、 　全ての頻出集合が見つかる ・しかし、単純に全てを 尽くすと、大量に重複が出る 1,2,3,4 φ 1,2 1,2,3 1 φ 1,2 1,2,3 2 1,2,3 1,2,4 1,3,4 2,3,4 1,2 1,3 φ 1,3 1 1,4 2,3 2,4 3,4 1 2 3 4 どうやって重複を回避しようか φ

34 メモリを使わず、本質的に重複を回避する方法がほしい
重複の回避法 ・ グラフ探索問題（幅優先探索、深さ優先探索）をするのだ、と考えれば、「一度訪れた頂点には、マークをつければいい」となる  マークをどうやってつける？　そもそも、探索するグラフを得ること自体が、解を求める作業と同じ ・ 他の手として、出力した解を全部メモリにとっておいて、新たな頻出集合が見つかるたびに、「今までにこれを出力したか」チェックをする  メモリが大量に必要。おまけに、探索の手法、というレベルでは、重複は避けられていないため、１つあたりの計算時間は長くなるはず メモリを使わず、本質的に重複を回避する方法がほしい

35 こういう探索方法をバックトラック法という
バックトラック法による探索 ・ そもそも重複が起こるのは、各頻出集合がいくつもの部分集合から「アイテムを１つ追加」として得られるのが原因 　（{1,2,3} には、{2,3}+1, {1,3}+2, {1,2}+3 の3通りある） ・ そこで、各頻出集合に対して、「作られ方」と1通りに制限する ・ 具体的には、「一番大きなアイテムを加えた場合のみ」とする 　（{1,2,3} は、{1,2}+3 という 　　作り方でしか作らない、 　　ということ） 探索ルートが木構造に 　　なるので、重複がなくなる φ 1,3 1,2 1,2,3 1,2,4 1,3,4 2,3,4 1 2 3 4 3,4 2,4 1,4 2,3 1,2,3,4 こういう探索方法をバックトラック法という

36 バックトラック法の計算時間 ・計算時間を算定してみよう。擬似コードは Backtrack (K) 1 Output K
2 For each e > K の末尾（ K の最大のアイテム） If K ＋e が頻出集合 call Backtrack　(K＋e) －再帰呼び出しの回数は、 　　頻出集合の数と同じ －1呼び出し（反復と言う）の 　　計算時間は （n-K の末尾）×（頻出度計算時間） φ 1,3 1,2 1,2,3 1,2,4 1,3,4 2,3,4 1 2 3 4 3,4 2,4 1,4 2,3 1,2,3,4 O(|D|) 解１つあたりの計算時間が算定できた

37 解1つ当たり、を速くする ・解１つあたりの計算時間はそれなりに（多項式時間で）抑えられたが、まだまだ大きい
・ 各 K＋e について、その頻出度を計算 　－単純にするなら、全ての項目（トランザクション）について、 K＋e を含むかどうか調べる 　 最悪、データベースの大きさに比例、 　　　平均ではだいたい、項目数、 　　頻出度×Kの大きさ、の大きいほう 　－ 2分木のようなデータ構造を作って、含むものだけ 抜き出す、あるいは勘定する、というのは、難しい 1,2,5,6,7,9 2,3,4,5 1,2,7,8,9 1,7,9 2,7,9 2 ここにもアルゴリズムが必要

38 メモリを使う点、検索に時間がかかる点がネック
幅優先探索の利用 D0={φ}, k := 1 while Dk-1 が空でない for each Dk-1 のメンバー X for each e if X+e が頻出集合 then Dk に X+e を挿入 ・ X+e の頻出度を計算する前に X+e に含まれる部分集合が 全てDkにあるか調べる ・ ないものがあるなら、頻出でない 1,2,3,4 1,2,3 1,2,4 1,3,4 2,3,4 1,2 1,3 1,4 2,3 2,4 3,4 1 2 3 4 φ メモリを使う点、検索に時間がかかる点がネック

39 含むものしか含まない ・ アイテム集合 X の出現集合を T とする ・ X＋e の出現は X を含む（＝ X の出現）
・ T のトランザクションで e を含むものを集めると X＋e の出現集合が得られる ・ 出現集合を更新すれば、 　　　データ全体を見なくて良い  計算時間はだいぶ短くなる

40 計算時間は、スキャンしたアイテムの数  両者の大きさの和
共通部分をとる ・ T のトランザクションで e を含むものを集めると X＋e の出現集合が得られる 　 X＋e の出現集合は、 Xの出現集合と e の出現集合の共通部分 （両方に含まれるものを集めたもの） ・ 共通部分をとるには、両者をソートしておき、同時に先頭からスキャンする {1,3,7,8,9} {1,2,4,7,9} ＝ {1,7,9} 計算時間は、スキャンしたアイテムの数　 両者の大きさの和

41 しかし、後述するデータベース縮約と相性が悪い
ビット演算を使った共通部分の高速計算 ・ 各アイテムの出現をビットの形で保持する （現在の部分集合も同じように） {1,3,7,8,9}  [ ] {1,2,4,7,9}  [ ] 　 [ ]  共通部分の計算が、AND 演算でできる 　　　　（いっぺんに32個(最近は64個) 計算できる） 　　メモリの節約にもなる しかし、後述するデータベース縮約と相性が悪い

42 振り分けによる高速化 ・ 各アイテムに空のバケツを用意する ・ X の各出現 T に対して、以下を行う
　 － T に含まれるアイテム e に対して、 e のバケツにT を入れる  この操作が終わった後は、各アイテムe のバケツの中身は X＋e の出現集合になる for each X の各出現 T for each T に含まれる e, e>Xの末尾 　　　eのバケツに T を挿入 1: A,C,D 2: A,B,C,E,F 3: B 4: B 5: A,B 6: A 7: A,C,D,E 8: C 9: A,C,D,E A: 1,2,5,6,7,9 B: 2,3,4,5 C: 1,2,7,8,9 D: 1,7,9 E: 2,7,9 F: 2

43 振り分けの計算時間 for each X の各出現 T for each T に含まれる e, e>Xの末尾 eのバケツに T を挿入
・ 計算時間は, X の各出現の (Xの末尾) より大きなアイテムの数の総和 A: 1,2,5,6,7 B: 2,3,4,5 C: 1,2,7,8,9 D: 1,7,9 E: 2,7,9 F: 2

44 ・ Compute the denotations of P ∪{i} for all i’s at once,
Occurrence Deliver ・ Compute the denotations of P ∪{i} for all i’s at once, A 1 2 5 6 7 9 B 3 4 C 8 D E F A A A A 1,2,5,6,7,9 2,3,4,5 1,2,7,8,9 1,7,9 2,7,9 2 D＝ C C C D P = {1,7} Check the frequency for all items to be added in linear time of the database size Generating the recursive calls in reverse direction, we can re-use the memory

45 1再帰呼び出しの計算時間のイメージ 効果はこれだけではない ・ 普通に頻出度の計算をすると 各 X＋e に対してデータを 一回スキャンする
・ 共通部分による計算は D(X) と D(e) のをスキャンする 　 D(X) を n-t 回スキャンし、 データベースの t より大きな アイテムをスキャンする ・ 振り分けは D(X) に含まれるトランザ クションの t のをスキャンする t より 大きなアイテムをスキャンする (n-t)個 効果はこれだけではない ＋ (n-t)個 t t

46 ほぼ全ての反復が短時間で終了  全体も速くなる
末広がり性 ・ 再帰呼び出しを繰り返すと、 Xの頻出度は小さくなる  振り分けの計算時間も短くなる ・ バックトラックは、各反復で複数の再帰呼び出しをする 　 計算木は、下に行くほど大きくなる  計算時間を支配するのは一番下の数レベル ・・・ 計算時間長 計算時間短 ほぼ全ての反復が短時間で終了  全体も速くなる

47 最小サポートが大きい場合も ・ θが大きいと、下のレベルでも多くの出現を見ることになる  末広がり性による高速化はいまひとつ
 末広がり性による高速化はいまひとつ ・ データベースの縮約により、下のレベルの高速化をはかる （１） 前回追加したアイテムより小さいアイテムは消す （２） 現在の出現集合からできるデータベースの中で、頻出になっていないアイテムは消去する 　（再帰呼び出しの中で加えられることが無いから） （３） まったく同一のトランザクションは、１つにまとめる ・ 実データだと、下のほうのレベルでは だいたい大きさが定数になる １ ３ ４ ５ ２ ６ ７ θが小さいときと速度の大きな差はない

48 キャッシュとの相性 ・ 速いプログラムを作るとき、キャッシュのヒット率が良く問題になる － ループを開く － メモリの配置を変える
　－ ループを開く 　－ メモリの配置を変える for i=1 to n { x[i]=0; }  for i=1 to n step 3 { x[i]=0; x[i+1]=0; x[i+2]=0; } ● ● ● ●▲ ● ▲ ▲ 再帰的に問題が小さくなり、ある反復より先ではキャッシュに入る  末広がり性より、ほぼ全ての部分でキャッシュに入っている

49 木構造を用いた圧縮 （trie, prefix tree）
・ 各トランザクションを文字列とみなすと、2分木の形で格納でき、メモリを節約できる 　 振り分けと併用できる。スキャンの時間も、それだけ短くなる * 1 2 5 6 7 9 8 21 3 4 A C D B E F A: 1,2,5,6,7,9 B: 2,3,4,5 C: 1,2,7,8,9 D: 1,7,9 E: 2,3,7,9 F: 2,7,9

50 コンテストの結果

51 計算機実験： FIMI04 ・ FIMI: Frequent Itemset Mining Implementations
－ ICDM (International Conference on Data Mining) サテライトワークショップで、頻出／頻出飽和／極大頻出集合列挙のプログラムコンテストを行った。2回目。3回目はなし ・去年は15、今年は8個の投稿があった ルール： － ファイルを読み、列挙してファイルに書くこと － time コマンドで時間を計測（メモリも他のコマンドで計測） － CPUを制御する命令（パイプラインなど）は使用禁止

52 計算機実験： FIMI04 ・計算機環境：CPU、メモリ: Pentium4 3.2GHz、1GB RAM
OS、言語、コンパイラ: Linux 、C言語、gcc ・ データセット： 　－ 実データ： 疎、アイテム数大 　－ 機械学習用データ： 密、アイテム数小、規則的 　－ 人工データ： 疎、アイテム数大、ランダム 　－ 密な実データ： 超密、アイテム数小 LCM（宇野有村清見）、見事優勝

53 “Most Frequent Itemset” だそうです
賞状と賞品 賞品は {ビール, 紙おむつ} “Most Frequent Itemset” だそうです

54 実データ （すかすか） 平均の大きさ5-10 BMS-WebView2 BMS-POS retail

55 実データ （すかすか） メモリ使用量 BMS-WebView2 retail BMS-POS

56 密（50%程度）で 構造があるデータ pumsb connect chess

57 密で構造があるデータ、メモリ量 pumsb connect chess

58 密な実データ＆ 巨大データ accidents accidents メモリ web-doc

59 飽和集合の列挙

60 頻出集合の問題点 ・ 面白い頻出集合を見つけようとすると、θを小さくする必要がある  大量の頻出集合が出てくる
 大量の頻出集合が出てくる ・ 情報を失わずに、頻出集合的な、数の少ないものを 　　　見つけるようにモデルを変えたい １． 極大頻出集合： 他の頻出集合に含まれない頻出集合 ２． 飽和集合： 出現集合が等しいものの中で極大なもの 111…1 000…0

61 極大頻出集合と飽和集合の例 ・ 頻出集合を出現集合で分類 ３つ以上に含まれるもの {1} {2} {7} {9} {1,7} {1,9}
{1} {2} {7} {9} {1,7} {1,9} {2,7} {2,9} {7,9} {1,7,9} {2,7,9} 1,2,5,6,7,9 2,3,4,5 1,2,7,8,9 1,7,9 2,7,9 2 T ＝ 頻出飽和集合 出現集合の共通部分が 飽和集合になる 極大頻出集合

62 両者とも、１つあたりほぼ定数時間、1秒間に1～10万個
極大頻出集合と飽和集合 極大頻出集合 ・ 多項式時間で列挙できるかどうか、未解決 ・ クリークと同じように枝刈りをすると、高速に列挙できる ・ 数が少ないがθによる解のぶれが大きい 飽和集合 ・ 逆探索という探索手法で多項式時間列挙可能 ・ 離散アルゴリズムと末広がり性を用いて、高速列挙可能 ・ 出現の意味で情報の損失がない ・ ノイズが多いと出現集合が等しいものが少なくなり、 　　　解の減少効率が悪くなる 両者とも、１つあたりほぼ定数時間、1秒間に1～10万個

63 飽和集合の列挙手法 ・ 頻出集合列挙ベース － 頻出集合列挙アルゴリズムをベースに、多少無駄な計算を省く
　－ 頻出集合列挙アルゴリズムをベースに、多少無駄な計算を省く 　－ 飽和集合のよさが出ない。計算時間の改善も少ない ・ 保存 ＋ 枝狩り　　 　－ 見つけた解を保存し、それを用いて無駄な分枝を刈る 　－ 計算速度はまあまあ 　－ 解保存のためにメモリを使用し、それがひとつのネック ・ 逆探索　＋　データベース縮約　　（LCM） 　　 － 計算効率が良い 　　 － 解保存用のメモリが不要

64 飽和集合の隣接関係 ・ 飽和集合から、添え字の大きい順に要素を抜いていく ・ どこかで出現集合が大きくなる
・ その出現集合の飽和集合を求める ・ こうして求めた飽和集合を、親とする　（一意的に定まる） ・ 親の頻出度は必ず真に大きいので、親子関係は非巡回的 　 親子関係は有向根付き木を導出する

65 逆探索 親子関係は有向根付き木を導出する この木を深さ優先探索すれば全ての解を見つけられる
・ 探索には、子供を見つけるアルゴリズムがあれば十分 ・ 子供が１つあたり多項式時間で見つかれば、全体も多項式時間 （親に要素を１つ加えて極大をとった飽和集合が子供になる） 非巡回的な親子関係と、子供を見つける多項式時間アルゴリズムがあれば、なんでも多項式時間列挙ができる

66 ・ データベースの全ての 飽和集合とその親子関係
親子関係の例 ・ データベースの全ての 飽和集合とその親子関係 φ 1,7,9 2,7,9 1,2,7,9 7,9 2,5 2 2,3,4,5 1,2,7,8,9 1,2,5,6,7,9 1,2,5,6,7,9 2,3,4,5 1,2,7,8,9 1,7,9 2,7,9 2 T ＝ 出現集合が隣接 親子関係

67 子どもを求める ・ 子どもから親を作る際に抜いた、最後のアイテムを親に追加すると、出現集合は子どもと等しくなる
　 子どもは、アイテムを１つ追加して、出現集合の共通部分をとると得られる 　 とはいえ、そのようにして作ったもの全てが子どもになるとは限らない 　 子どもである条件は、抜いたアイテムより前の部分に、新しくアイテムが追加されないこと

68 比較の手間 ・K+e の出現の共通部分、素直に計算してもよいが、「共通部分がKと等しいか」を調べるだけなので、必ずしも全て計算する必要はない
 異なることがわかった時点で、計算をやめてよい ・ K+e の出現それぞれを小さい順にたどり、 全てに共通するものがあるか調べる ・ 全てに共通するものがあったら K に入っているか調べる ・ 前回たどったところで止まって おき、次回はそこからたどる K 4 11 3 3 4 4 6 6 9 9 11 1 1 3 3 4 4 5 5 9 9 11 K+e の 出現集合 3 2 4 4 5 5 9 9 11 1 1 2 2 4 4 6 6 9 9 11 1 1 4 4 9 9 11

69 ビットマトリクス ・ スウィープポインタは、行列の形でデータを持ってないがゆえの工夫。隣接行列を持って入れば、もっと単純に速くできる
・が、大きすぎて構築することすら不可能 ・ 出現集合がある程度以下に小さくなったところで、 　　　　行列を構築しよう 　  ビットで持てば、各列が1つの変数に入る！

70 ビットマトリクスの定数時間計算 ・ 各アイテムに対応する列を１変数で持っていると、K+e の出現全
てにそのアイテムが含まれるかどうか、1ステップでチェックできる ・ K+e の出現のビットパターンと、アイテム i の列のビットパターンの AND をとる ・アイテム i が K+e の出現全てに含まれるなら、共通部分はK+e の出現ビットパターンと等しくなる ・・・ K<i ∩N(vi) K の頂点

71 実データ （すかすか） 平均の大きさ5-10 BMS-WebView2 BMS-POS retail

72 実データ （すかすか） メモリ使用量 BMS-WebView2 retail BMS-POS

73 密（50%程度）で 構造があるデータ pumsb connect chess

74 密で構造があるデータ、メモリ量 pumsb connect chess

75 密な実データ＆ 巨大データ accidents accidents メモリ web-doc

76 参考文献など ・ 頻出集合およびその応用 (’90～) 星の数ほど
・ 頻出集合およびその応用 (’90～)　　星の数ほど 　　 “frequent pattern”、”frequent itemset” で検索すると出てくる ・ 極大頻出集合およびその応用 (’90～)　　やはり多い 　　 “maximal frequent itemset” などで検索すると出てくる ・ pasquerらのアルゴリズム (‘99) 飽和集合の導入 ・ 宇野らのアルゴリズムLCM (‘04) 現在最速のアルゴリズム ・ 実装 LCM: (Linear time Closed itemset Miner) 宇野のHP ・ レポジトリ　（実装、論文、比較実験の数々） ・ 中野・宇野・有村 （’03～ ） 順序木・無順序木の多項式時間頻出列挙

77 閑話休題：　初期化のいらない配列

78 閑話休題：初期化のいらない配列 ・ 配列は、普通、確保したら初期化（0などを代入）してから使う  初期化しないで使えるかな？？？
　　初期化しないで使えるかな？？？ ・ 実はうまい方法がある ・ 配列を準備。初期化せず。各セルには値を入れるところと、添え字を入れるところ、２つを割当てる ・ あと、もうひとつ、添え字の配列と、書き込まれた配列の数を覚えるカウンタを準備。カウンタは0に設定 配列 添え字配列

79 閑話休題：初期化のいらない配列 配列 添え字配列 カウンタ
・ 配列の i 番目に値を代入するときは、添え字配列のカウンタの場所に、i を書き込み、配列の添え字側に、カウンタを書き込む。カウンタを 1 進める。 ・ 配列 i 番目の値を参照するときは、添え字側の数字 p を見て、p がカウンターより大きい、あるいは添え字配列の p 番目が i でないなら、代入されてない、と答える 値 ０ ２ ０ ３ １ ０

80 類似項目の発見

81 データベースから類似する項目を見つける ・ データベースの項目の中で、似た項目のペアを全て見つけたい （項目のペア全てについて、
2項関係が成り立つかを調べる） ・ 類似している項目の検出は、 　データベース解析の基礎的な手法 　　基礎的なツールがあれば、使い方しだいで いろいろなことができる （大域的な類似性、データの局所的な関連の構造・・・）

82 問題が大きいので、平均的な意味でよいので、 計算オーダーの小さいアルゴリズムがほしい
類似項目発見の計算時間 ・ 似たもののペアを全て見つけるさい、項目のペア全てについて、単純に全対比較を行うと項目数の２乗の時間がかかる 　　項目数が100万を越えるころか現実的には解けなくなる 　　　100万×100万 ÷100万（演算per秒） = 100万秒 ・ 類似検索を使う手もあるが、100万回のクエリを実行しなければならない。類似検索は完全一致より大幅に時間がかかる 　 1秒間にクエリが1000回できるとして、1000秒 問題が大きいので、平均的な意味でよいので、 計算オーダーの小さいアルゴリズムがほしい

83 応用１：似ているwebページの発見 ・ web 検索を行うと、よく似た内容、あるいは引用しているものを多量に見つけることがある
　　ニュース記事、レビューの記事の一部など ・ あらかじめ、類似しているページをグループのように検出できれば、こういった似たものをひとくくりにでき、検索エンジンの効率化にもつながる （検索結果を出してから似たものを見つける、という方法もあり） ・ さらに、例えば、最近のホットな話題は何ですか、 　　　というような検索もできるかもしれない

84 応用２：リンクが似ているwebページ ・ リンク先、あるいはリンク元が、集合として似ているページは、よく似ていると考えられる
　　サッカーのページ、料理のページ、地域のページ ・ グループ化すれば、コミュニティー発見、著名なトピック、web の構造の解析など、いろいろなことがやりやすくなる ・ さらに、例えば、「スパムサイト」の検出にも使えるかも 　（レポート課題のコピーの検出、とか）

85 応用３：長い文章の比較 ・ （文庫本のような）長い文章がいくつかあるときに、類似する部分がどことどこにあるかを検出したい
　 長い文章の比較はそれ自体が大変（時間がかかる）ので、複数あると手が出ない ・ 長い文章を、短い文字列にスライスし、全体を比較する 　 大域的に似た部分は、局所的に似ている 　　　　ところを多く含むと思われる 　　　つまり、似ている短い文字列のペアを多く含む ・ 短い文字列の全対比較からアプローチできる

86 応用４： ゲノムの比較 ・ 異なる種のゲノムを比較して、類似するところを見つけ出したい － ２つの染色体の比較（1億文字以上）
応用４：　ゲノムの比較 ・ 異なる種のゲノムを比較して、類似するところを見つけ出したい 　－　 ２つの染色体の比較（1億文字以上） 　－　複数の、短い染色体の比較（バクテリアなど：400万程度） 　－　 両方とも、ゲノムをスライスして全対比較する ATGCCGCG GCGTGTAC GCCTCTAT TGCGTTTC TGTAATGA 　　．．． ・ ATGCCGCG と AAGCCGCC ・ GCCTCTAT と GCTTCTAA ・ TGTAATGA と GGTAATGG 　　　　 ．．．

87 応用５： 特異的な部分を見つける ・ 似ているものがない項目は、データの中で特異的な部分と考えられる
　 － 携帯電話・クレジットカードの不正使用 　 － 制御システムの故障・異常の発見 　 － 実験データから新しいものを発見 　 － マーカーの設計 （「宇野毅明のホームページは、”助教授，宇野毅明の研究”で検索するとユニークに定まる） ・ 比較的大きなデータが複数あるような場合でも、特異な項目を多く含むもの、他のどのデータとも、似ている部分が少ないものは、特異なデータだと考えられる ・ 「似ている項目の数」は、データがエラーを含む際の統計量として使えるかも知れない

88 応用５： マイクロアレイのデザイン ・ マイクロアレイは調べたいDNAに、ある特定の短い文字列（20文字程度）が含まれているかどうかを検出する実験装置（いっぺんにたくさん実験できる） ・ 特定の遺伝子（あるいは変化）が含まれているか、たくさんの微生物が含まれているコロニーの中に、特定の生物種がいるか、といったことを調べる際に使われる ・ 短い文字列が、他の場所にも含まれていると、検出が効率良くできない  固有の短い文字列があらかじめわかっているとうれしい

89 問題設定：短い文字列の比較 ・ 具体的に見るため、扱うデータベースと問題を具体化する
問題： 各項目が同じ長さ l の短い文字列（50文字程度）であるデータベースを入力したときに、文字列のペアで異なり数が d 文字以下である組を全て見つけよ （ハミング距離がd 以下） ・ 長くて、ある程度似ている文字列は、このような似ている部分列をある一定数以上含む ATGCCGCG GCGTGTAC GCCTCTAT TGCGTTTC TGTAATGA 　　．．． ・ ATGCCGCG と AAGCCGCC ・ GCCTCTAT と GCTTCTAA ・ TGTAATGA と GGTAATGG 　　　　 ．．．

90 問題の難しさ ・ 全ての項目が同じだと、およそ項目数2) 個の出力がある  l を定数だと思えば、単純な全対比較のアルゴリズムが
　　　　　計算量の意味では最適になる 　  計算量理論的には面白くない問題 ・ 現実には、やたらと似てるものがあるものを比較しても意味が無い 　  出力は少ないと仮定する ATGCCGCG GCGTGTAC GCCTCTAT TGCGTTTC TGTAATGA 　　．．． ・ ATGCCGCG と AAGCCGCC ・ GCCTCTAT と GCTTCTAA ・ TGTAATGA と GGTAATGG 　　　　 ．．．

91 基本のアイディア：文字列の分割 ・ 各文字列を、k（>d） 個のブロックに分割する
・ k-d 個のブロックの場所を指定したときに、そこがまったく等しくて、かつハミング距離がd 以下となるようなペアを全て見つけよ、という部分問題を考える  各文字列の k-d 個のブロックをつなげてキーにし、ソートをする。同じものはグループになる。それを総当りで比較すればよい ・ k-d 個のグループ数が大きければ、平均的にグループのメンバー数は小さくなるので、総当りで比較してもたいしたことない

92 全ての場合を尽くす ・ 先の部分問題を、全ての場所の組合せについて解く  ２つの文字列が似てれば、必ずどこか k-d 個のブロックが同じ
 必ずどれかの組合せで見つかる ・ 部分問題は、バケツソートやRadixソートで速く解ける ・ 組合せの数は kCd 。のk=5 で d=2 なら10通り 　　 ソート10回 ＋α で解ける。全対比較よりもかなり高速 ・各文字の数から、１文字比較した場合に等しくなる確率を求め、適切な分割数 k を使用する

93 ・ ABC、ABD、ACC、EFG、FFG、AFG、GAB のペアでハミング距離が1以下のものを求めよ
例題 ・ ABC、ABD、ACC、EFG、FFG、AFG、GAB のペアでハミング距離が1以下のものを求めよ A B C A B D A C C E F G F F G A F G G A B G A B A B C A B D A C C E F G F F G A F G A B C A C C A B D A F G E F G F F G G A B A B C A B D A C C A F G E F G F F G G A B

94 メモリに解を保持せずとも、重複が回避できる
重複の回避 ・ まったく同じ文字列があると、全てのブロックの組合せで見つかるので、 kCd 。回出力される 　 重複を回避する必要がある ・ 各見つかったペアについて、選択されていないブロックが選択したブロックの間にあったら出力しないようにする 　 等しいブロックが一番左端によっている場合にのみ出力 メモリに解を保持せずとも、重複が回避できる

95 イメージ的には ・ 似ているもののペアを探す問題は、マトリクスのセルの中で必要なものを全て見つける問題
・ 全対比較は、マトリクスのセルをすべて見ていることに対応 ・ 分類によるアルゴリズムは、 分類を順々にしていると思えば、 木構造の探索を行っていることに対応

96 実験：長さ20文字で異なり数 d を変化

97 ゲノムの比較 染色体と染色体を比較する － 1億以上の文字列の比較になるので、非常に時間がかかる
　－ 1億以上の文字列の比較になるので、非常に時間がかかる 　－ アラインメントでは部分が入れ替わった構造が見つけられない ・ 比較するゲノムを、オーバーラップするようにスライスし、全対比較 ・ 縦横に比較するゲノムをおき マトリクスを作って類似するペアが あるセルの色を白くする （実際は細長い四角でいい） 類似する構造が見える

98 ゲノムの比較 (1) ヒト21番染色体とチンパンジー22番染色体の比較 ・長さ3000万の配列×2 から、30文字の切片を3000万個取る
・ 似ている部分配列のペアの数に応じて、各ドットの明るさを変える ・ 白い部分が 「似ている可能性のある部分」 ・ 黒い部分が 「(絶対に)似ていない部分」 ・ 格子模様は、繰り返し 　　配列を拾っている ヒト 21番染色体 チンパンジー22番染色体 PCで 1時間で可能

99 ゲノムの比較 (2) ヒトX染色体とマウスX染色体の比較 ・ 30文字で間違い2文 字以下のペアを列挙 ・ 長さ3000、幅300
の領域に3つペア があれば点を打つ ・ ノイズをかなり 除去できている ヒトX番染色体 マウスX染色体 PCで 1時間で可能

100 バクテリアを30種 ABC順の取得し つなげて比較
ゲノムの比較 (3) バクテリアを30種 ABC順の取得し つなげて比較 PCで 1時間で可能

101 （マイクロアレイ用の）固有な配列のデザイン
・ マイクロアレイの設計には、ゲノム配列中でなるべく他の部分と似ていない配列が使えるとありがたい ・ 配列の長さは２０文字、のように決まっているので、 対象となるゲノムの全て２０文字の部分配列を比較し、 似ているものがないもの、を見つければよい ・ 似ている文字列の数、はある種の統計量として利用できるかもしれない 100Mベース、25文字、間違い2文字まで、くらいなら PCで 1時間で可能

102 ゲノムの読み取り ・ ゲノム配列は、そのままひも状のものを一度に読むことはできない。通常、一度に500文字程度しか読めない。
・ そこで、染色体を10万文字程度の長さにぶつ切りにし、大腸菌に移植して増殖させる ・ 増殖したものをさらにぶつ切りにし、500文字程度ずつ読み、つなげる（できたものをBAC配列と言う） ・ BAC配列をさらにつなげて、もとの染色体を作る

103 重なり部分の検出 ・ 短い配列を読んだとき、あるいはBAC配列を作ったとき、それがもとの染色体、BAC配列のどの位置にあったかはわからない
 配列を構成する際に使える情報は「どことどこが重なるか」 ・ 機械の読み取りエラーや大腸菌が増殖する際のコピーミスも起こりうるので、「完全に重なる」ではなく「だいたい重なる」でなければいけない ・ BAC１つ作るのに、 万文字の比較が必要

104 BAC配列の比較 ・ ゲノム全体の配列を決める際には、BAC同士がどのようにつながるかを調べる必要がある
・ しかし、どの配列とどの配列がオーバーラップしているか調べるのは、大変。（前述のアセンブリをミスしていると、微妙に異なるところが出て、重ならなくなる） ・ 既存の手法は、直接的でない 手段を使って比較をしていて、 ときどきオーバーラップしそうな ところを落としてしまう ・ この手法なら全対比較可能 PCで 1ペア1秒

105 課題点 ・ マウス13番染色体の未解読領域に対して、この相同検索アルゴリズムの適用を行っている  既にいくつかの空白部分が埋まった
・ 比較は高速にできるようになった。しかし、比較した結果をどう使うか、どのような点に留意する必要があるか、といった点は、まだまだ明らかでない － 実験の指針を出すためには、 　　何を出力する必要があるか － どの程度の精度が必要か － どこまで処理を自動化すべきか － エラーをどのように扱うべきか  既存のアセンブリングソフトでは 見つからない、特殊な重なり方を している相同領域が見つかる。 どう解釈すべきか？

106 類似部分（アイテム）集合の列挙

107 D が巨大かつ疎で（各Ti が平均的に小さい）、出力の数がそれほど多くない（ ||D|| の数倍）状況での高速化を考える
問題の定義 入力： 部分集合族（トランザクションデータベース） D = {T1,…,Tn} （ ただし、各 Ti はアイテム集合 E = {1,…,n} の部分集合） 　　＋ 閾値 θ 出力： |Ti∩Tj| がθより大きいような、 　　　　　全てのTi 、Tjのペア 例： 閾値 θ=2 のとき、 (A,B), (A,C), (A,D), (A,E) (C,D), (C,E), (D,E) A: 1,2,5,6,7 B: 2,3,4,5 C: 1,2,7,8,9 D: 1,7,9 E: 2,7,9 F: 2 D ＝ D が巨大かつ疎で（各Ti が平均的に小さい）、出力の数がそれほど多くない（ ||D|| の数倍）状況での高速化を考える

108 単純に全対比較すると A: 1,2,5,6,7 B: 2,3,4,5 C: 1,2,7,8,9 D: 1,7,9 E: 2,7,9 F: 2
・ 単純に全対比較するアルゴリズムを考える for i=1 to |D|-1 　for j=i to |D| 　if |Ti∩Tj|≧ θ then output (Ti, Tj ) ・ 共通部分の計算は、各 Ti をアイテム順でソートしておき、Ti 、Tjをマージソートのように並行してスキャンすればよい。 　　時間はO(|Ti |＋| Tj|) ・ 全体の計算時間は ∑i,j(|Ti |＋| Tj|) = 2n ||D|| D ＝ かなり時間がかかると見てよい

109 振り分けによる高速化 ・各Ti に対し、|Ti∩Tj|がθ以上になるものを見つける問題を考える
・ 各アイテム e に対して、e を含む部分集合の集合を D(e) とする ・ Ti が含む各 e に対して、D(e) の各 T に対して、カウントを１つ増やす、という作業をする  全ての e∈Ti についてこの作業をすると、各 Tj のカウントは |Ti∩Tj| になる for each e∈Ti for each Tj∈ D(e), j>i, do c(T)++ ・ D(e) を添え字順にソートしておくと、j>i である 　　Tj∈ D(e) を見つけるのも簡単 A: 1,2,5,6,7 B: 2,3,4,5 C: 1,2,7,8,9 D: 1,7,9 E: 2,7,9 F: 2 D ＝

110 振り分けの計算時間 for each e∈Ti for each Tj∈ D(e), j>i, do c(T)++ ・ 計算時間は
∑j ∑e∈Ti |{ Tj∈D(e), i<j}| ＝ ∑e |D(e)|2  |D(e)| が平均的に小さければ、かなり速い A: 1,2,5,6,7 B: 2,3,4,5 C: 1,2,7,8,9 D: 1,7,9 E: 2,7,9 F: 2 D ＝

111 1再帰呼び出しの計算時間のイメージ ・ 普通に頻出度の計算をすると 各 X＋e に対してデータを 一回スキャンする ・ 共通部分による計算は
D(e) と D(e) のをスキャンする 　 D(X) を n-t 回スキャンし、 データベースの t より大きな アイテムをスキャンする ・ 振り分けは D(X) に含まれるトランザ クションの t のをスキャンする t より 大きなアイテムをスキャンする (n-t)個 ＋ (n-t)個 t t

112 計算実験 ・ webリンクのデータの一部を使用 － ノード数 550万、枝数1300万 － Pentium4 3.2GHz、メモリ2GB
　　　－ ノード数 550万、枝数1300万 　　　－ Pentium4 3.2GHz、メモリ2GB ・ リンク先 20個以上 個、20個以上共有する ペア数が 個、計算時間、約8分 ・ リンク元 20個以上が 個、20個以上共有する ペア数が 個、計算時間、約3分 ・ 方向を無視して、リンクが 100個以上あるものが 個、 100個以上共有するペア数が 個、計算時間、約7分 ・方向を無視して、リンクが20個以上あるものが 個、 20個以上共有するペア数が 個、計算時間、約14分

113 簡単に追加できる条件 ・ |A∩B| が、|A| のα倍以上 、(and/or) |B| のα倍以上 ・ |A∩B| / |A∪B| ≧ α
など。 この手の、共通部分や和集合の大きさから計算できる評価値であれば、簡単に評価できる ・ 計算時間は、ほぼ線形で増えていくと思われるので、多少大きなデータでも大丈夫

114 これからも、より質の高いプログラム作りを目指して
まとめ ・ 速いプログラムを作るための理論、アルゴリズム理論 ・ 計算の構造・デザインを工夫することで、コーディング技術では届かないくらいの高速化を行う － 頻出集合を列挙するアルゴリズム 　　計算構造に着目して、解１つあたりの計算時間を短縮 － 類似する項目のペアを列挙する出力数依存型のアルゴリズム 　　異なりの場所に注目し、分類による絞込みを行う これからも、より質の高いプログラム作りを目指して がんばってください