圧縮したまま演算する

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