ryamadaの遺伝学・遺伝統計学メモ このページをアンテナに追加 RSSフィード

数学・コンピュータ関連の姉妹ブログ『ryamadaのコンピュータ・数学メモ』
京都大学大学院医学研究科ゲノム医学センター統計遺伝学分野のWiki
講義・スライド
医学生物学と数学とプログラミングの三重学習を狙う学習ツール
駆け足で読む○○シリーズ
ぱらぱらめくるシリーズ
カシオの計算機
オンライン整数列大辞典

2012-11-25 組合せ集合の圧縮表現ZDD

[][][][]圧縮したまま演算する

  • こちらでZDD/BDDについて書いた
  • その元ネタとしてこちらがある
  • その中に頻出アイテム集合マイニングという話題がある
  • スーパーで、スーパーの全商品リストを全体集合とし、顧客の1回毎の買い物リストを、部分集合としたときのデータハンドリングの話
  • まず、「部分集合のどれがあって、どれがないか」は部分集合なのでZDD構造にすることができるし、そのデータ圧縮が効果的である
    • 個々のアイテムが購入される頻度が低いとき、圧縮効率がよい
  • ハプロタイプに転用する
    • 全商品を全ゲノムの塩基位置とする。個々の買い物リストを、個々のハプロタイプのマイナーアレル箇所集合とする
    • ZDD構造が作れる
    • レアバリアントが多いと圧縮効率がよい
  • 頻出アイテム集合マイニングとは、部分集合の出現回数を問題にしてデータマイニングすることである
    • 出現回数に閾値を定めて、該当する部分集合を列挙することも必要だし、その膨大(になるかもしれない)な部分集合のそれぞれに出現回数情報を付与して保持することも大変だ
    • 膨大な個数の出現回数の把持方法にもZDDを応用できる
    • 部分集合に順番をつけて並べる。その順番に応じて、回数という整数値がある。これを2進数表現すると、部分集合数を行数とし、2進数の桁数を列数とする行列ができる。この各列に着目すると、ある部分集合が0か1かの情報がとれて、それはZDDにできる。これで、列数分のZDDができたことになる。さらにZDD同士で共通する節点を共有させることでさらに圧縮できる
  • ハプロタイプに転用する
    • ハプロタイプにも出現回数がある。それに使える
  • ZDDではZDD同士の演算が可能で、それが演算を速くする
  • ハプロタイプに転用する
    • 複数のハプロタイプ集合をZDD表現して、それを「併せたり」「引いたり」「割ったり」「掛けたり」することに意義を見出せば…