課題5

• データのMushroomのデータを使う。
  • agaricus-lepiota.data.txt: キノコが持つ属性の表(キノコの種類は8124): これを使いやすくしたデータが以下にある。
  • agaricus-lepiota.names.txt: データの説明
• mushroom1.dat: 記号に列番号をつけて、異なる列の記号がまざらないようにしたもの
• mushroom2.dat: 記号にユニークな番号を割当てた対応表
• mushroom3.dat: ユニークな記号を番号に置き換えた表
• mushroom4.dat: ユニークな記号を番号に置き換えた表。区切りは空白。(読み込むのが楽かもしれない。)

例えば、食べられて(e0)、傷がある(t4)キノコは2752種類あるので、e0とt4は条件を満たす。 しかし、えらが開いている(b8)という属性を加えても2656種類あり、その方が属性が多いのでよい答えである。

ヒント: n個の属性値の組合せのそれぞれに対して、いくつのキノコがその属性の組合せを持っているかを数えると、 nが大きい場合、計算が大変である。例えば、nが5とすると、23の列から5個の列を選ぶ組合せは₂₃C₅=33694であり、 各属性の属性値の可能性が平均3通りあるとすると、それぞれにつき3⁵=243の組み合わせを調べることになってしまう。

このような計算を減らす方法として Apriori Algorithmというものが知られている。 ここではエッセンスだけ利用しよう。

このアルゴリズムの原理は「指定したn個の属性値を持つキノコが2000種類以上なら、そのn個の一部の属性値を持つキノコは必ず2000種類以上ある。」ということである。(Apriori性)
これを利用して、少ない属性の組合せのうちに候補を絞ってしまうと、調べるものが少なくてすむ。

具体的な手順は以下のようになる。

1. 2000種類以上のキノコが持っている属性aを全てあげ、これを{a}として1-itemsetに加える。
2. 1-itemsetから{a}と{b}を取り出し、属性aとbを持つキノコが2000種類以上あれば、{a,b}を2-itemsetに加える。
3. 2-itemsetから{a,b}と{a,c}を取り出し、(対称なので、b>cの場合だけ考えればよい。) 属性a,b,cを持つキノコが2000種類以上あれば、{a,b,c}を3-itemsetに加える。
4. 以上を十分大きなk-itemsetまで繰り返す。

発展課題: 上記の課題が簡単すぎる場合は追加で他のアルゴリズムを実装して比較しても良い。 他のアルゴリズムは自分で考案しても良いし、調べたものでもよい。 (「FP-Tree」などのキーワードで探してみよ。)

1. 追加で実装したアルゴリズムの概要とポイントを書くこと
2. 上記のアルゴリズムと計算時間の比較を書くこと。プログラムのどの部分の違いによるものかを考察するとよい。

提出

• 説明とソースプログラムと実行結果(実行時間を含む)を提出すること。説明とプログラムは別ファイルで構わない。
• 無断複製は禁止
• 提出期限：7月28日
• CFIVE の「課題」の「キノコ」に提出すること

yamaguch@mail.ecc.u-tokyo.ac.jp

Copyright 2008 Kazunori Yamaguchi 山口和紀@東京大学総合文化研究科