重要論文検索システムIaskの実装と評価
8
0
0
全文
(2) Vol.2011-CE-109 No.10 2011/3/19. 情報処理学会研究報告 IPSJ SIG Technical Report. て Web マイニング技術を適応することが,非常に有効であり,様々なアルゴリズムを適用. Google のキャッシュを利用しているため,非常に大規模なデータベースである. • 著者名,年代,出版社による検索. することができると考えられる. 以下,本論文では,2 章で既存のシステムや関連研究について述べ,3 章でこれまで行っ. 単純なタイトルや本文以外の条件による検索が行える.. • 引用元の情報. てきた論文検索手法について述べる.4 章では提案システムの設計及び実装について述べ,. 5 章で評価と考察を行い,6 章で本論文をまとめる.. その論文から派生した研究を簡単に見つけられる.また引用数によりその論文の注目度 がわかる.. 2. 既存の論文検索システム. • Recent articles. 2.1 ACM Portal. 検索する際に,近年の研究への重み付けを行い,現在行われてる研究を見つけることが. ACM Portal3) は ACM(Association for Computing Machinery) の Web ベースのポー. できる.. タルサービスである.オンラインジャーナルのデータベースである Digital Library と書籍. 2.3 関 連 研 究. データベースである The Guide の2つから構成されている.Digital Library では,ACM. Web を使った論文サーベイの研究では,検索クエリの拡張による検索支援を行う研究5). が刊行している学会誌などに記載されたジャーナルを検索することができる.The Guide. などが存在する.また,論文のランク付けを行う研究も数多く行われている.その中でも,. では,コンピュータ分野における書籍情報を検索することができる.ACM Portal では,以. Web ページのランク付けアルゴリズムが論文のランク付けに利用されており,よい結果が. 下のような特徴がある.. 出ている6) .さらに,論文検索にランク付けアルゴリズムを応用した研究として,HITS ア. • ダウンロード数の表示. ルゴリズムを利用し,サーベイ論文を発見する方法7) がある.これは論文データベースに. 過去 6 週間,1 年間でのダウンロード数を見ることができるため,記事の引用以外にも. 対して HITS アルゴリズムを適用し,サーベイ論文を発見する手法である.. 2.4 問 題 点. 研究の注目度がわかる.. • 各論文の記事へ URL リンクが可能. 利便性の高い検索システムや,論文の評価,分類のためのアルゴリズムなどの研究が行わ. URL によって論文の記事を参照できるために,ユーザ間で情報を簡単に共有できる.. れており,論文検索の負担は減少している.しかし,これらのシステムは論文の検索を行っ. • 参照情報. た後,検索結果から,必要な論文を探す必要がある.また,研究の理解のために,その分野. 各論文ごとに参照,被参照の情報が掲載されており,記事へのリンクがされているた. で必要な知識についての論文を別に探す必要がある.特に,知識の少ないユーザにとって,. め,参考文献などを簡単に辿ることができる.. これらの作業は重要であり,手助けする必要がある.. • 様々な検索機能. 3. 参照構造を利用した論文検索. キーワード,著者名,ISBN/ISSN,雑誌名,出版社名,刊年など様々な条件により検 索ができる.. 本章では,我々がこれまでに行ってきた手法について述べる.以下,この手法を従来手法. 2.2 Google Scholar. と呼ぶ.従来手法では,論文の参照構造を作成し,解析することによって,適切な検索を行. Google Scholar4) は Google が収集しているデータから,特に学術文献を抽出し,それら. い,ユーザの研究への理解を手助けすることができる.. を検索しやすいように機能を追加した検索システムである.タイトルや本文検索だけでな. 3.1 参考文献とリンク解析. く,著者名や出版社,年代による検索ができる.Google Scholar には,以下のような特徴. 従来手法は,ユーザの興味をもった論文の分野における,重要論文の発見を目的とし,そ. がある.. のために論文の参照構造を作成する.学術論文は,研究の際に参考とした論文や文献など. • 大規模なデータベース. を,参考文献として記載している.参考文献内では,研究において基礎となる技術,概念な. 2. c 2011 Information Processing Society of Japan ⃝.
(3) Vol.2011-CE-109 No.10 2011/3/19. 情報処理学会研究報告 IPSJ SIG Technical Report. どや,実装の対象となるアルゴリズムなどが記載されている.そのため,参考文献を辿るこ. ジ本文の情報を利用するようなアルゴリズムは除外する必要がある.. とは,研究について理解する上で重要である.. 続いて,サーベイ論文の存在である.論文の中には,ある分野の近況や,関連技術などの. 論文の集合から知識を得るための手法として,この参考文献をリンクとしたネットワーク. 調査を行ったサーベイ論文が存在する.この論文は,その分野の研究の理解に大きく貢献す. として捉え,リンク解析を行う手法がある.これらの解析の多くはデータベース全体や,検. ると考えられる.よって,サーベイ論文を適切に扱うことが重要である.サーベイ論文は,. 索結果による集合に対して行われ,ユーザの要求にあった論文を発見する。. 数多くの優良な研究論文へのリンクを持っていると定義できる.これは,Web 上における. しかし,Web 上の論文公開により情報量が膨大になり,比例して結果の集合も大きくなっ. 優秀なリンク集と類似している.. ている.このため,研究に対する知識の少ないユーザでは,検索技術などにより絞り込まれ. この二つの条件により,参照構造の解析に HITS8) を利用する.HITS とは,Web マイ. た集合においても,自分の要求にあった,重要論文を発見することが難しい.そのため,興. ニングの手法の一つであり,Web ページのランク付けを行う.HITS では,Web ページを. 味を持った論文からサーベイを行い,その研究についての理解を深めることが困難である.. hub と authority という2つに分類を行っている.authority は,検索ワードに関する集合. よって,知識の少ないユーザにおいても,研究への理解を得られるように,論文のサーベ. の中で,重要なページであり,hub はそれら優秀な authority を数多くリンクしているよう. イを支援するようなシステムが必要である.. なページである.これら2つの指標によってランク付けを行っている.ここで本手法におい. 3.2 適切な参照構造の作成. て,hub は優秀なサーベイ論文や複合分野の研究,authority は優秀な研究や基礎概念の論. 研究への理解を手助けする方法として,参考文献中から,その研究分野における重要論文. 文に相当する.. を発見し,参照の道筋を提示することが考えられる.これにより,ユーザは,研究の基礎と. 3.4 参照関係の抽出. なる技術や,研究の遷移を理解することができ,自分の研究に役立てることができる.ここ. 参照構造の習得のために,ACM Portal を利用する.ACM Portal では各論文ごとにペー. で,初めてサーベイを行うユーザは,ある論文に興味を持ち,調査を行う場合が多い.. ジが生成され,参考文献が ACM Portal 上に存在する場合,各論文の ID によってリンクさ. そこで,解析対象となる論文の集合を以下のようなアルゴリズムで作成する.. れている.これを利用し,参照構造を作成する.ACM Portal の論文ページから論文のタイ トル,URL,参考文献などを取得する.. (1). ユーザが興味を持った論文を root とし,集合に追加する. (2). 集合に追加された論文の参考文献を調べ全て追加する. 3.5 研究の遷移図. (3). 2の手順を参考文献が辿れなくなるか,集合が一定の要素数を超えるまで繰り返す. ユーザの研究に対する理解をより深めるために,研究の遷移の出力を行う.解析によって 得られた重要論文から,root となった論文までの参照の過程を出力する.これによりユー. 3. については,Web 上で情報を取得できる論文を対象とするため,過去の論文が電子化. ザは,これまでの研究の変化や新規研究の起こり方を理解することができる.. されていない,もしくは有料となっており閲覧できないなどの問題から,辿れない論文が存. 3.6 問 題 点. 在する.. これらの手法について,実際にいくつかの論文に対して実験を行った.検索結果から,root. 3.3 リンク解析. となった論文に関係した分野,重要論文を発見することができた.. 参照構造の解析のために,重要な点として以下の二点が考えられる.初めに,参照の関係. しかし,検索結果は,参照構造の中の一つの分野における論文のみのスコアが高くなって. のみによる解析を行う必要がある.Web 上の論文は,様々なフォーマットで電子化されて. いる.例として,3D モデルを検索するインターフェイスに関する研究では,本来ならば画. おり,内容の取得が難しい.また,本文が有料となっており,参考文献などの情報のみが公. 像処理だけでなく,インターフェイスや検索手法など,様々な分野の研究が存在するはずで. 開されている場合なども多い.しかし,これらの論文の中に重要論文があることも考えら. あるが,一番盛んな画像に関する研究が多く発見される.しかし,研究を理解するために. れるため,Web 上で取得しやすい参考文献の情報からなる,参照構造の解析が必要となる.. は,背景となった様々な論文の理解が必要である.. そのため,Web マイニングのアルゴリズムの中でも形態素解析などを利用した,Web ペー. 3. c 2011 Information Processing Society of Japan ⃝.
(4) Vol.2011-CE-109 No.10 2011/3/19. 情報処理学会研究報告 IPSJ SIG Technical Report. ザが必要とする操作を選ぶことで結果の表示を行う.HITS などの検索アルゴリズムを選ぶ. 4. Web マイニング技術を利用した重要論文検索システム Iask の実装. と,図 2 のように,選択したアルゴリズムによってランク付けされた論文のうち,上位 10. 本章では,我々の提案する,重要論文検索システムについて述べる.. 4.1 設. 件が出力される.. 計. 本システムは従来手法を元に,以下の方針を加えて,実際にユーザの論文サーベイを補助 するアプリケーションの作成を行う.. • 簡単に利用できるシステム • より適切な検索結果の提示 • 元になった研究分野の抽出 まず,利用者が簡単にできるシステムであることが必要である.ここでは,対象が Web 上の論文であることを考え,Web アプリケーションとしての実装を行う.これにより,将 来的に論文の参考文献情報をもったデータベースとともに運用することが可能である.. 4.2 検索アルゴリズム HITS による検索が,一つの分野に偏った結果になった背景には,ネットワーク解析での 問題点である,TKC 効果9) があると考えられる.これは,解析対象の中から,リンクが密で. 図1. Iask の入力画面. あるような,一部のコミュニティのみを重要であるとランク付けしてしまうものである.こ れに対し SALSA は,HITS 同様の hub と authority の概念を持ったまま,ランダムウォー クによる確率的手法をとることで,TKC 効果の改善に対して効果的な、Web マイニングの アルゴリズムである10) .そこで本研究では,確率的手法である PageRank,SALSA と,こ れまで使っていた HITS をそれぞれ実装し,検索結果を比較することで,よりユーザの要 求にあった論文の提示を行えるシステムとする.これらの検索結果は,ユーザが任意で選べ るよう設計する.. 4.3 研究分野の抽出 本システムでは,研究分野の抽出のために,GN 法によるクラスタリング11) を行う.GN 法とは,Web ページのリンクなどのグラフ構造の中から,媒介性が高い辺を取り除いていく ことによって,各コミュニティに分割していく手法である.この手法では,論文の内容よる 関連度などを計算する必要がなく,参照構造のみでのクラスタリングを行うことができる.. 4.4 インタフェース. 図2. Iask による検索結果. 本システムは Web アプリケーションとして実装されているため,ブラウザ上で操作を行 う.まず,Iask にアクセスすると図 1 の画面が出力される.ここでユーザは,root としたい 論文の ACM Portal における URL を入力する.参照構造の取得が正常に行われると,ユー. 4. c 2011 Information Processing Society of Japan ⃝.
(5) Vol.2011-CE-109 No.10 2011/3/19. 情報処理学会研究報告 IPSJ SIG Technical Report. 5. 評. 価. 本章では,本システムに対して行った評価実験の結果と考察に関して述べる.評価は,論 文検索による検索アルゴリズムの評価,クラスタリングによるコミュニティ抽出の評価の 2 つを行う.システムは,Tomcat によりローカルホスト上で動作させ,Web ブラウザとし て FireFox3.0.17 を用いた.. 5.1 検索アルゴリズムの評価実験 ここでは,本システムを用いて論文検索を行い,その結果について評価を行う.対象とな る論文は ACM Portal 上で,簡単なワードによる検索を行い,トップページに表示された 論文の中から,無作為に選んだ.. “3D content-based search using sketches” “3D content-based search using sketches” を root として実験を行った.この論文は 2009 年に “Personal and Ubiquitous Computing” で発表され,“3d content-based search”,“de-. sign experimentation”,“multimodal interfaces”,“retrieval models”,“sketch”,“user interfaces” といったタグがつけられている.結果はそれぞれ,図 3,4,5 のようになって いる. 図3. HITS では,3D モデルなど,画像に関する論文が上位を占めていたのに対し,SALSA や. “3D content-based search using sketches” の HITS による解析結果. PageRank では,それ以外の分野の論文も多く現れていることがわかる.これらから HITS における,ある分野のみのスコアの上昇に対し,SALSA や PageRank といった確率的手法. より,計算機の基礎である,コンパイラなどのアルゴリズムが上位になっている.これらは,. は効果的であると言える.SALSA による結果では,非常に多くの論文から参照されている. 年代の古い論文であり,基礎部分の研究であるため,多くの論文からリンクされていたと考. ような書籍が数多く発見できており,分野も様々に分かれていることから,幅広い分野にお. えられる.. 5.2 クラスタリングによるコミュニティ抽出の評価実験. ける,重要な研究を見つけることができた.また,PageRank による結果では,他のアルゴ リズムに比べ,古い論文が多く,上位の論文の被引用数も,比較的少なくなっていた.. ここでは,参照構造のクラスタリングを行い,その結果について評価を行う.検索アルゴ リズムの評価実験から得られた結果を対象とする.. “Hits hits TREC: exploring IR evaluation results with network analysis” “Hits hits TREC: exploring IR evaluation results with network analysis” を root と. ここでは,“3D content-based search using sketches” を root として得られた参照構造. して実験を行った.この論文は,2007 年に “SIGIR ’07” で発表され,“experimentation”,. に対し,クラスタリングを行い,コミュニティの抽出を行った.まず,分割されたクラスタ. “information search and retrieval”,“ir evaluation” といったタグがつけられている.結. は図 9 のようになっている.ここで,クラスタの番号は,大きさの順序を表し,数字が小さ. 果はそれぞれ,図 6,7,8 のようになっている.. いものほど大きなクラスタである.ここで,クラスタごとにおける各検索アルゴリズムによ. HITS と SALSA では,リンク解析に関係のある論文が上位となっている.その中でも,. るスコアの平均値を見ると,HITS ではクラスタ間のスコアの差が大きくなっていることが. HITS は Web に関係した分野の論文が発見され,SALSA ではハイパーテキストやデータ. 分かる.ここから TKC 効果により,リンクが密であり,大きなコミュニティにスコアが集. ベース管理など,より広い領域の論文が多くなっている.PageRank は Web やリンク解析. 中していることが分かる.それに対し,PageRank や SALSA は,ある程度クラスタの大き. 5. c 2011 Information Processing Society of Japan ⃝.
(6) Vol.2011-CE-109 No.10 2011/3/19. 情報処理学会研究報告 IPSJ SIG Technical Report. 図6 図4. “3D content-based search using sketches” の SALSA による解析結果. “Hits hits TREC: exploring IR evaluation results with network analysis” の HITS による解析 結果. さを無視し,参照構造全体から論文を発見していると考えられる. また,ここで発見されたクラスタのうち,No.0 の詳細の一部を表 1 に示す.No.0 はこの 参照構造の中で,最大のクラスタと判定されたものである.クラスタに含まれる論文のう ち,多くは視覚化や 3D モデルのような画像に関係するものとなっている.続いて,クラス タ No.8 の詳細の一部を表 2 に示す.これは検索結果のうち SALSA によって上位となった 論文が含まれたクラスタである.ここでは,2 分木探索など,データ構造及びデータ探索に 関する論文が多く見られる.これらの結果から,論文の参照構造に対し,リンク解析による クラスタリングは効果的であることが分かる.. 5.3 Web マイニング技術の適用に関する考察 HITS による検索結果や各クラスタのランク付けアルゴリズムによって付けられたスコア の平均値から,論文の参照構造に対しても Web 上と同じく TKC 効果が現れていることが 図5. 分かる.それに対し SALSA を用いることで,TKC 効果を取り除くことができた.これら. “3D content-based search using sketches” の PageRank による解析結果. の結果は,論文の参照構造に対し,Web マイニングのアルゴリズムが有効に作用すること を示している.. 6. c 2011 Information Processing Society of Japan ⃝.
(7) Vol.2011-CE-109 No.10 2011/3/19. 情報処理学会研究報告 IPSJ SIG Technical Report. 図7. “Hits hits TREC: exploring IR evaluation results with network analysis” の SALSA による解析 結果 表1. 図 8 “Hits hits TREC: exploring IR evaluation results with network analysis” の PageRank による解 析結果. “3D content-based search using sketches” におけるクラスタ No.0 の一部 タイトル. しかし,リンクが密であり,大きなクラスタが形成されるということは,root となった. Computer Vision, 1st edition 3DPO: A three-dimensional part orientation system Surface reconstruction from unorganized points Perceptual organization and the representation of natural form 3-Draw: A Tool for Designing 3D Shapes. 論文を理解するうえで必要であり,盛んに研究されている分野の論文であることを指してい る.そのため,HITS による値の集中にも,論文サーベイを行う上では重要な意味があると 考えられる. 本手法における PageRank を用いたランク付けでは,よい結果が得られなかった。これ. 表2. は,参考文献の取得法により,構造の末端に位置する古い論文からの参照が無いため,ラン. “3D content-based search using sketches” におけるクラスタ No.8 の一部. タイトル. ダムウォークがうまく行われないことが原因であると考えられる。. Multidimensional binary search trees used for associative searching Data Structures for Range Searching A new representation for linear lists Two applications of a probabilistic search technique The R*-tree: an efficient and robust access method for points and rectangles. 類似分野の中で,もっとも盛んな研究を調査するためには HITS アルゴリズムを利用する. これらのことから,基礎となっている多くの分野を理解するためには SALSA を利用し, ことで,適切な論文サーベイを行うことができる.. 7. c 2011 Information Processing Society of Japan ⃝.
(8) Vol.2011-CE-109 No.10 2011/3/19. 情報処理学会研究報告 IPSJ SIG Technical Report. タを表わす要素として,ACM Portal で利用されているタグを用いて,クラスタ内で頻出 する語句などによるラベル付けを行う. 二つ目は,アプリケーションの公開及び,ユーザによる評価実験である.今回,作成した アプリケーションを用いて,検索を行い,良い成果を得られた.今後は,本システムを一 般に公開し,論文サーベイの経験が少ないユーザを対象とした実証実験を行いたい.また, ユーザの意見により,必要な機能の追加を行っていきたい.. 参. 図9. 考. 文. 献. 1) 井坂 徳恭,藤本 敬介,中山 泰一: 参照構造を用いた重要論文検索システム, 情報処理 学会 コンピュータと教育研究会 99 回研究発表会(2009). 2) 井坂 徳恭,中山 泰一: Web アプリケーションを用いた重要論文サーベイシステムの 設計, 情報処理学会 コンピュータと教育研究会 105 回研究発表会(2010). 3) The ACM Portal, ACM(online), available from <http://portal.acm.org/> (accessed 2009-11-20). 4) Google Scholar, Google(online), available from <http://scholar.google.co.jp/> (accessed 2009-11-20). 5) 榊 剛史, 石塚 満: Web を活用した論文サーベイシステムに関する研究, 東京大学大学 院 情報理工学系研究科 修士論文(2005). 6) Y, Sun. and C. L, Giles.: “Popularity Weighted Ranking for Academic Digital Libraries”, Lecture Notes ic Computer Science, 4425, pp.605-612(2007) 7) 難波 英嗣, 奥村 学: 多言語論文データベースを用いたサーベイ論文検出 : サーベイ論 文自動作成の実現に向けて, 電子情報通信学会技術研究報告. NLC, 言語理解とコミュ ニケーション, vol.102, No.199,pp.35-41(2002). 8) Kleinberg, J.: “Authoritative sources in a hyperlinked environment”, ACM Computing Surveys, vol.31, Issue 4es, Article no.5(1999). 9) Lempel, R. and Moran, S.: “The stochastic approach for link-structure analysis (SALSA) and the TKC effect”, Computer Networks, vol.33, Issue 1-6(2000). 10) Lempel, R. and Moran, S.: “The stochastic approach for link-structure analysis”, ACM Transactions on Information Systems, vol.19, Issue 2, Pages131-160(2001). 11) Newman, M. E. J. and Girvan, M.: “Finding and evaluating community structure in networks”, Physical Review, E 69, 026113(2004).. “3D content-based search using sketches” のクラスタリング. 6. 今後の予定 本研究では,論文の参照構造を利用した検索手法をもとに,Web マイニング技術を適用 した,論文サーベイ支援システムの設計と実装を行った.論文の参考文献の集合である参照 構造を定義し,それに対し HITS,SALSA,PageRank,GN 法といったアルゴリズムによ る解析を行うアプリケーションの作成を行った.実験の結果から,Web マイニング技術を 用いた論文の参照構造の解析によって,ユーザに対し適切な論文を発見し,研究の理解を手 助けすることができた.このシステムを利用することで,学生など,論文サーベイを初めて 行うようなユーザの負担を減らし,研究への理解を深めることによって,研究の効率を上げ ることができる. また今後の課題として,次の二つが挙げられる.一つ目は,クラスタリングの内容に関 する課題である.今回のシステムはリンク解析のみにより,参照構造の解析を行っているた め,クラスタリングによる分類はできたが,内容についての表示を行っていない.各クラス. 8. c 2011 Information Processing Society of Japan ⃝.
(9)
図
+2
関連したドキュメント
名の下に、アプリオリとアポステリオリの対を分析性と綜合性の対に解消しようとする論理実証主義の
Robertson-Seymour の結果により,左図のように disjoint
2813 論文の潜在意味解析とトピック分析により、 8 つの異なったトピックスが得られ
Based on the models of urban density, two kinds of fractal dimensions of urban form can be evaluated with the scaling relations between the wave number and the spectral density.. One
荷役機器の増車やゲートオープン時間の延長(昼休みの対応を含む)、ヤードの拡張、ターミ
As in 4 , four performance metrics are considered: i the stationary workload of the queue, ii the queueing delay, that is, the delay of a “packet” a fluid particle that arrives at
連携DB 営業店AP お客さま番号.
図表 5-1-6 評価シート.. 検査方法基本設計 (奈留港に適合した寸法)工場試験結果追加試験結果対応内容