2005/10/06 情報知識ネットーワーク研究室紹介（有村・喜田研）北海道大学工学部情報エレクトロニクス学科コンピュータサイエンス・コース 3年ゼミナール紹介情報知識ネットワーク有村・喜田研究室 {arim,kida}@ist.hokudai.ac.jp ex. 7678, 7679 研究室ホームページ http://www-ikn.ist.hokudai.ac.jp/ 1 情報知識ネットーワーク研究室紹介（有村・喜田研） 2005/10/06 紹介: 情報知識ネットワーク研究室（有村・喜田研）  研究テーマ：情報検索とデータマイニング  教官：有村博紀教授，喜田拓也助教授  研究協力者：宇野毅明，佐藤健（国立情報学研究所），湊真一，トーマス・ツォイグマン（北大大学院情報科学研究科）坂本比呂志，下薗真一（九工大），北大情報科学ＣＳ専攻知識ソフトウェア科学講座メンバーとも研究交流 2 情報知識ネットーワーク研究室紹介（有村・喜田研） 2005/10/06 有村博紀  専門：  データマイニング  情報検索（とくに全文テキスト索引）  計算学習理論（機械学習）  興味があること  膨大なデータから，人間に役立つ情報と知識をとりだすこと  高速なアルゴリズム（プログラム）を設計すること  最近面白かったこと  企業の人たちと一緒に，ソフトウェア開発をしたこと． 3 情報知識ネットーワーク研究室紹介（有村・喜田研） 2005/10/06 データマイニング・エンジンの開発ウェブやHTML，テキストデータなどのグラフデータから特徴的なパターンを高速に取り出す．情報検索や日本語テキスト処理，画像データ処理に役立つ．  AWAP: Fast Text Mining Engine (1997－2002)  FREQT: Fast XML and Tree-like Data Miner (SDM'02)  A collection of trees OPTT: Optimized Pattern Disocvery Frequent Patterns with s = 50 % Mining (PKDD'02)  StreamT: Online XML Stream Miner (IEEE ICDM'02)  UnoT: Unordered Tree Miner (Discovery Science'03) (with 浅井達哉君@現・富士通研，安部賢治君@現・シャープ，宇野毅明先生@NII，中野眞一先生@群馬大，) 4 情報知識ネットーワーク研究室紹介（有村・喜田研） 2005/10/06 AWAP: Fast Text Mining Engine (1997－2002) HONDA vs. SOFTBANK HONDA vs. TOYOTA HONDA vs. SOFTBANK Rank Other 0 0 1 1 2って 33 3 >350 4 どんな会社だろう？ >350 5 >350 6 5 7 >350 8 2 9 24 10 108 11 じゃなくて， 4 12 6 に出ているもの 13 >350 14 19 はなにかな？ 15 3 16 28 17 >350 18 >350 19 >350 ホンダソフトバンクホンダ Pattern HONDA vs. TOYOTA Rank Other Pattern 0 0 <honda > 1 1 <prelude > 2 8 <vtec > 3 15 <si > 4 11 <bike > 5 6 <99 > 6 12 <motorcycle > 7 25 <the honda > 8 41 <prelude si > 9 20 <civic > 10 35 <honda prelude > 11 48 <98 > 12 53 <valkyrie > 13 60 <99 time > じゃなくて， 14 37 <honda s > 15 36 <rims > に出ているもの 16 40 <looking > 17 30 <looking for > はなにかな？ 18 67 <scooters > 19 14 <black > <honda > <prelude > <i > <car > <parts > <engine > <99 > <rear > <vtec > <exhaust > <miles > <bike > <motorcycle > <racing > トヨタ <black > <si > ホンダ <me > <tires > <fuel > <my > 5 情報知識ネットーワーク研究室紹介（有村・喜田研） 2005/10/06 喜田拓也  専門：  情報検索（特に文字列照合）  テキスト・アルゴリズム  データ圧縮  興味があること  巧妙なアルゴリズムを知るor設計すること  効率よく情報を検索するためにコンピュータができること  最近面白かったこと  国際会議でイタリアへ行ったこと． 6 情報知識ネットーワーク研究室紹介（有村・喜田研） 2005/10/06 圧縮データに対する文字列照合テキストデータ文字列照合アルゴリズム転送二次記憶装置上主記憶装置上圧縮テキスト復号転送二次記憶装置上文字列照合アルゴリズム主記憶装置上主記憶装置上圧縮テキスト転送二次記憶装置上主記憶装置上圧縮文字列照合アルゴリズム 7 情報知識ネットーワーク研究室紹介（有村・喜田研） 2005/10/06 実験結果（非圧縮テキスト上のアルゴリズムとの対比） CPU時間（秒） 0.8 0.7 AlphaStation XP1000 (Alpha21264: 667MHz) Tru64 UNIX V4.0F 0.6 Medline（英文テキスト） 60.3Mbyte 0.5 非圧縮テキストをKMPで照合 0.4 BPE圧縮テキストに対する照合 0.3 非圧縮テキストをAgrepで照合 0.2 BPE圧縮テキストに対する Boyer-Moore型のアルゴリズムを用いた照合（Shibataら[2000]） 0.1 0.0 5 10 15 20 25 パタンの長さ 30 * BPEはByte Pair Encoding圧縮法 * KMPはKnuth-Morris-Pratt法 * AgrepはWu&Manberが開発した検索ツール (with 柴田裕介君@現・NTTコムウェア, 松本徹也君@現・NTTドコモ, 竹田正幸先生@九大，篠原歩先生@九大) 8 情報知識ネットーワーク研究室紹介（有村・喜田研） 2005/10/06 3年生ゼミナール  ゼミナール       英語または日本語の資料を読むわかったことを他のひとに説明する新しい考え／方法を作るプログラムを作る／実験するこれは今回は見送り日本語または英語で書く大学の残りの2年間でしてほしいこと＊  興味があること／やりたいことをみつける  何でもいいから，集中して基礎的な勉強をしてみる（20代前半に) 9 ＊）大学院の2年間で身につけてほしいことでもあります．情報知識ネットーワーク研究室紹介（有村・喜田研） 2005/10/06 H16年の例 3年生ゼミナール：テキスト   英語の教科書 "Managing Gigabytes" (ギガバイトを征服！）  著者： Ian H. Witten, Alistair Moffat, Timothy C. Bell, Morgan Kaufmann Publishers, 1999.  ウェブサーチ・エンジンを作るための現在唯一の教科書  テキストと画像の圧縮  テキスト索引の実装  問合せの実現 ManagingGygabyte site: http://www.cs.mu.oz.au/mg/ 写真略 Ian Witten先生ワイカト大学, NZ 写真略 Alistair Moffat先生メルボルン大学, AU 10 情報知識ネットーワーク研究室紹介（有村・喜田研） 2005/10/06 3年生ゼミナール：  ゼミで直接まなぶこと  情報検索の基礎技術  データ圧縮の技術  ウェブ検索エンジンのしくみ  情報工学として  アルゴリズムとデータ構造の議論に慣れる  情報理論と統計の実際をしる  工学(engineering)の感覚  読む・話す・聞く・作る 11 情報知識ネットーワーク研究室紹介（有村・喜田研） 2005/10/06 3年生ゼミナール  オプション（希望者があれば）  プログラム作成  複数パターン照合機械（情報検索）  ハフマンor LZ圧縮プログラム (テキスト圧縮）  アイテム集合発見プログラム（データマイニング）  コンテスト？？？ 12 2005/10/06 情報知識ネットーワーク研究室紹介（有村・喜田研）おまちしています情報知識ネットワーク有村・喜田研究室 {arim,kida}@ist.hokudai.ac.jp ex. 7678, 7679 研究室ホームページ http://www-ikn.ist.hokudai.ac.jp/ 13