2001年度　演習３　データマイニング

演習３　データマイニング

1) リンク情報を使ったランキング法やサイバーコミュニティ発見法　　

知能システム論の「Webグラフと検索エンジン」に関する講義（講義ノート）で紹介した以下のアルゴリズムのどれかを試作してみる課題です。

Page Ranking - google.com
Sergey Brin and Lawrence Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. 7th International World Wide Web Conference. April 1998. Html file
Page Ranking - Hubs & Authorities
Jon M. Kleinberg: Authoritative Sources in a Hyperlinked Environment. JACM 46(5): 604-632 1999. PDF file
Cyber Communities
Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins. Trawling the web for emerging cyber-communities. The Eighth International World Wide Web Conference. May 1999. Html file

これらの課題に取り組む際に問題になるのがデータをどのように収集するかです。例えばgoogle.com が成功したのは、link を利用した有効な Page Ranking アルゴリズムを先駆けて開発したことにもありますが、それ以上に１０億を超える Web Page を高速に収集する技術と計算機環境を持ったことだと言われています。

この課題を選択するには、自分で Web Crawler（Web Page の収集ソフト）を作成することになります。wget を利用してテキストを収集し link を辿ってゆくソフトを書くのが基本的なアプローチですが、既にあるソフトを使うこともできると思います。例えば

http://verno.ueda.info.waseda.ac.jp/

にはWeb Crawlerが公開されてます。 Web Crawler は簡単なものを作成し、ある程度ページを収集したら、Page Ranking してみるのが1ヶ月でこなせる現実的な目標だと思います。

昨年もこの課題を出したのですが、Web Crawler を作成するのに皆苦労していました。研究の最前線でも、高速で無駄のない Web Crawler の開発それ自身が活発に研究されてます。例えば以下の論文で最新の結果を議論しています。これらの論文を読んで、Web Crawler を作成する際の問題点を考えるだけでもよいです。

Junghoo Cho, Narayanan Shivakumar, Hector Garcia-Molina: Finding Replicated Web Collections. ACM SIGMOD 2000. PDF file
Junghoo Cho, Hector Garcia-Molina "The Evolution of the Web and Implications for an incremental Crawler." International Conference on Very Large Databases (VLDB), September 2000. PDF file

2) クラス分類法決定木／Boosting／最適区間領域計算

知能システム論の「クラス分類」に関する講義（講義ノート）で紹介した決定木を生成するプログラムを作成し、以下の例題を解くことを試みます。

例題B　（本年度 KDD Cup　出題中の Dataset 1です。増田君用に新しく出題します。）

この例題のデータは　http://www.biostat.wisc.edu/~page/Thrombin.zip　から入手できます。このアーカイブには README がついているのですが、簡単に解説します。

このデータは、Thrombin という血液の凝固を起こす酵素に結合する可能性のある1909個の化合物に対して実験を行った結果を示しています。1行が一つの化合物に対応しており、第一列目が結合した(Active)もしくは結合しなかった(Inactive) を示しています。結合した化合物は 41 個です。 1行目から139,352行目までが各化合物の3次元的構造の特徴の有無を 1 もしくは 0 で表現しています。求めたいのは、 139,351 個の３次元的特徴の有無を使って、結合が Active もしくは Inactive どちらになるかを判別できる決定木です。

決定木の各ノードは f1234 = 1 とか f2345 = 0 のような条件でもよいですし、(f1234 = 1) かつ (f2345 = 0) のような論理積でも構いません。

データは訓練データで、テストデータは7月10日に　 http://www.cs.wisc.edu/~dpage/kddcup2001/　から公開になります。創薬デザインに役立つ知識を発見する問題で、バイオインフォマティクスの主要な問題の一つです。

例題A　（大谷君と由利君が、アッという間に解いてしまったので、この例題は店じまいします）

Whitehead/MIT Center for Genome Research が公開している癌関連遺伝子を推測するためのデータを解析しましょう。　7129個の遺伝子の発現情報に関するデータが登録されてます。訓練データから癌か否かを判別するクラス分類ルールを生成して、テストデータに適用して判定するのが目的です。

データの解説
データフォーマットの意味
細胞が ALL もしくは AML のどちらかのタイプであるかを推測する問題。
訓練データ　７１２９個の遺伝子（縦軸）が３８個の細胞（横軸）での発現パターン。
データフォーマットの意味でも書いてあるのですが、少し分かりにくいので補足します。３８個のうち、１～２７までが ALL型で、２８～３８までが AML 型です。各細胞には call というフィールドがあり、A もしくは P の値が付与されてますが、このフィールドの値は無視してください。
テストデータ３４個の細胞での発現パターン。
これもデータフォーマットの意味で書いてあるのですが、分かりにくいですね。　39-49, 55, 56, 59, 67-72 が ALL 型で、その他が AML型です。

このデータは数値を含んでいるので、"Attribute > value" のような条件の中で Entropy Gain を最小化する条件を計算する必要があります。さらに進んで "low < Attribute < high" の形をした最適区間とか、２次元中における最適領域を高速に計算することが考えられますが、これらの解法はちょっとと難しいので以下の参考文献を挙げます。
Takeshi Fukuda, Yasuhiko Morimoto, Shinichi Morishita, and Takeshi Tokuyama: "Constructing Efficient Decision Trees by Using Optimized Numeric Association Rules" Proceedings of VLDB '96, pages 146-155, Bombay, India, September 1996 （コピーのほしい人は私まで）

このテーマに深い興味を持った人には AdaBoost 法の実装も薦めます。AdaBoost では予測精度のあまり高くない仮説（例えば深さ１の決定木）をうまく組合せ、重み付き多数決を取ることにより、高い予測精度が得られることが経験的に知られています。 AdaBoost については以下の論文と講義ノートを参照してください。
Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119-139, 1997. Postscript or compressed postscript.
講義ノート HTML MSPowerPoint
しかし、この手法の成否は、５０％を超える予測精度の仮説を数多く生成できるかという点にかかっており、現実には仮説を少ししか生成できないため、予測精度を上げられないケースもしばしばあります。この問題を解決するため、我々が提案しているのは、最適な仮説を効率的に計算するアプローチです。
Jun Sese and Shinichi Morishita. "Computing Optimal Hypotheses Efficiently for Boosting'' (unpublished) PDF file