読者です 読者をやめる 読者になる 読者になる

Information Retrieval-1章

Introduction of Infomation Retrieval(IIR)について
適当&もしかしたら間違ってる,なんで参考にして失敗しても責任とりませんので悪しからず.

第一章 Information Retrieval(IR):情報検索

IRは膨大なデータのcollectionから欲しい情報を持つunstructed natureを持つmaterialを探し出す事.

  • unstructed nature ≒ text , material ≒ document
  • unstructed data
    • コンピュータで扱いやすい形ではない → 検索しやすいようにする。

documentの中に検索したいtermがあるかどうかを

  • あれば0
  • なければ1

で表す.

  • boolean検索

precision & recall

検索結果の良し悪しは適合率(precision)と再現率(recall)の2つを用いて計算される.

  • 適合率:全検索結果に対する検索要求を満たす結果の割合
  • 再現率:検索要求を満たす全documentに対しての検索要求を満たす結果の割合

この2つはトレード・オフの関係
→ 検索して検索対象の全てを結果として返してしまえば,再現率は100%になるが、適合率は極小になる.

text走査とindex化

query_termを持つdocumentをそのdocIDでindex化する.
これによって大規模なデータから検索することが容易になる.
しかしindexが大きくなりすぎる → 転置index

  • term => docID(posting list)
  • term(Brutus) => [1,2,4,11,31,45,173,174]
  • term(Caesar) => [1,2,3,4,5,16,57,132]
  • term(Calpurnia) => [2,31,54,101]
  • リストの集合:postings
    • 各リスト:posting list
      • 各リストの要素:posting
  • 検索語:term => termの集合:dictionary

これらの対応をまとめた物:inverted index(転置index)

  • dictionary => メモリ上に
  • postings => ディスク上に

それぞれ記憶することで容量の問題を解決する.

転置indexの作り方

  • index化したい文を取得 → 単語ごとに分割 → 言語の処理(大文字とか)
    • lemmatize → index化

こうやって出来たindexをmergeしてsortする.

  • merge

[2,4,8,16,32]
[1,2,3,5,8,13]

    ⇣

[2,8]

boolean検索

上でも述べたように,0か1かの検索.
基本はand, or, notの3つを使ってqueryを生成して検索する.
「あるか、ないか」を知りたい時はboolean検索で十分である

  • macのspotlightとか

よりよいindexの構造などを考慮したい.

ranking検索

boolean検索で十分で無いときは, ranking searchが欲しい.

  • (Document | term) frequency

を使うなどして.
それについてはこれから….