情報システム - SELECT * FROM life;

索引法

主キーによる検索:B木、ハッシュ
副次キーによる検索（副次索引）
- 副次キー:ここでは主キーでないものを副次キーと呼んでいる

副次索引の例
レコードの任意の属性値（の組み合わせ）による検索

完全一致質問:全ての属性値の指定

部分一致質問:一部の属性値の指定

範囲質問:ある属性に関して値の範囲を指定

ブール質問:AND/OR/NOTの組み合わせ

近傍質問:属性値がだいたい合っているもの

転置ファイル
- 論理的構造:属性値と、この属性値を持つレコードへのポインタ。B木やハッシュ表を用いて実装する。
- フルテキスト検索の場合:n-gram index　連続するn文字ごとにインデックスを作成
- ブール質問の処理:ポインタの集合操作
グリッドファイル
- k個の属性を持つレコードをk次元空間の点として表現
- k次元空間をグリッドに分割、各グリッドに点を均等配分
- 索引レコードに対して高速にアクセスするにはB木やハッシュが使われる
k-D木
- k-D木全体を主記憶にtって来てから扱う主記憶ベースのアクセス法
- アドレス空間を重なりのない領域に分ける
- 構造は２分木
- 完全一致、範囲、近傍質問の処理に適する
シグニチャファイル
- quick and dirty
  - 答えにならない文章群のほとんどを早く排除する
  - 答えになる文章はすべて含む
- 各文章中の各単語の先頭２文字を記憶
- 実際にはあまり用いられない

テキスト検索

再現率と適合率

再現率: 正解の何％が結果に現れたか
適合率: 検索結果の何％が正解か

- 再現率と適合率は互いにtrade-offの関係にある
質問緩和法による再現率向上
- キーワードを減らし、質問を緩和することで再現率を向上
- 検索結果のページで、テキスト部部分に緩和されたキーワードを含むページを適合と判断

テストコレクション

テストコレクション: (a)文章集合(b)多数の質問(c)各質問に対する適合文書の集合、を組にしたデータベース。情報検索システムの性能評価に重要。

なぜ重要か？
- 適合文章集合の作成の困難さ→再現率計算の困難さ
- 適合解の集合を作るのは困難

Pooling method: 多数の検索エンジンで同一の文章集合に同じ質問をし、それぞれの上位100件程度を集め人出で適合性を判断し、それを適合文書集合とする。

ベクトル空間モデル

索引付け
- 各文章をV次元ベクトルで表現（特徴ベクトル）
- Vは文章群から抽出された索引語の総数
クラスタ作成
- 類似ベクトル群をグループ（クラスタ）にまとめる
クラスタ検索
- 質問（ベクトル）に最も類似したクラスを検索

文章iの特徴ベクトル: Di=(wi1,wi2,...,wim) (m:索引語の総数, wij:文章iにおける索引語jの重要度）

wijをどのように定めるか？

出現したら１、なければ０

索引語の出現頻度で正規化*1

tf/idf法

wij=tfij*idfj

tfij

文章iにおける索引語j(term)の出現頻度(frequency)

idfj

索引語jが文章(document)集合に出現する頻度の逆(inverse)*2

ユーザの検索要求の特徴ベクトル: Q=(Q1,Q2,...,Qm)　Qj:検索語jの重要度*3

類似度計算*4

内積: $sim(Q,D_i)=Q{\cdot}D_i=w_1{\cdot}w_{i1}+{\cdots}+w_m{\cdot}w_{im}$
コサイン相関値: $sim(Q,Di)=\frac{QD_i}{|Q|{\times}|D_i|}=\frac{w_1{\cdot}w_{i1}+{\cdots}+w_m{\cdot}w_{im}}{\sqrt{w_{1}^2+{\cdots}w_{m}^2}\times\sqrt{w_{i1}^2+{\cdots}w_{im}^2}}=\cos\theta$

パッセージ検索とは？
Webページは通常1ページに複数の話題がある→ページ全体ではなく、パッセージ（段落など）毎に特徴ベクトルを作る*5

パッセージの候補

固定長に分割したテキストの部分

形式段落

形式な節、章

適合フィードバック

ユーザの質問Qとそれに対する検索結果集合をユーザが適合、不適合を手動で判断し、これらをフィードバックして新たな質問Q'を作る。

$Q'=Q+\frac{1}{n_1}\sum_{i=1}^{n_1}R_i-\frac{1}{n_2}\sum_{i=1}^{n_2}S_i$
$R_i{\cdots}R_{n_1}$ ：適当と判断されたもの
$S_i{\cdots}S_{n_1}$ ：不適合と判断されたもの
各項目に適当な重みα、β、γを付加する。このプロセスを繰り返す。

クラスタリング

クラスタの生成方法

グラフ理論的アプローチ
- 文章の類似度がある閾値を超えたものを枝で結ぶ→無向グラフ
- 無郷グラフ中の連結成分または極大クリークを１つのクラスタとする。文章数Nに対してO(N×N)以上の計算量が必要
反復法
- サンプルから適当なクラスタ作成。ある文章をそれに最も近いクラスタに追加。
- クラスタの重心点を修正、これを繰り返す

質問-クラスタ間の類似度

質問とクラスタの中央値の類似度を使う
クラスタ内文書との最少の類似度を使う
クラスタ内文章との最大の類似度を使う

情報フィルタリング、協調フィルタリング、推薦（レコメンデーション）

情報配信の流れ

プル型
- エンドユーザが能動的に情報にアクセス*6
プッシュ型
- 情報提供者主導。エンドユーザが能動的なアクションを行わなくても、情報が自動的に配信される

情報フィルタリング*7

内容フィルタリング
- ユーザが入力したキーワードやユーザのプロファイルの情報の内容を照合することによって情報を取捨選択する
- 処理
  - 配信されたコンテンツとユーザの情報の類似度を計算する
- 弱点
  - ユーザの好みをユーザプロファイルに十分に反映できない場合がある
  - ユーザは自信が選択したものに類似したものしか見ることができない
協調フィルタリング
- ユーザとプロファイルや興味・関心が類似している人の情報に対する評価を基に情報を取捨選択する
- 処理
  - ユーザのプロファイルとマッチする人を選択し、その人が高く評価した情報を選択する
- 弱点
  - コミュニティの作成と、評価情報の集積が必要

比較

内容フィルタリング: 少ない入力で情報を得ることができるが、表面的なテキスト情報のみから判断する為、質の高い情報を選択することが難しく、ユーザのスキルや選択ルールの作り方に大きく依存する
協調フィルタリング: 同じような人が評価済みの情報だから質の高い情報を容易に得ることができるが、評価情報を十分に集積するまでは得られる情報が少ない

レコメンダシステムのアーキテクチャ *8

推薦情報の蓄積
- ユーザが推奨する情報を蓄積する
- このユーザの嗜好を調べ、プロファイルの獲得に利用するとともに、ほかのユーザに情報を推奨する際の元情報とする
ユーザプロファイルの獲得
- ユーザプロファイルはユーザの特性を表し、ユーザのグルーピングに用いられる
グルーピング
- ユーザプロファイル間の相関関係を調べて、思考の似ているユーザのグループを見つけ出す
嗜好の予想
- 対象ユーザと類似しているユーザを探し出し、類似ユーザの推奨している情報の中から大賞ユーザに最も適していると思われる情報を推奨する

相関係数 $t_{KL}$ :ユーザKとユーザLの相関
$t_{KL}=\frac{Cov(K,L)}{\sigma_K{\cdot}\sigma_L}=\frac{\sum_i(K_i-\bar{K})(L_i-\bar{L})}{\sqrt{\sum_i(K_i-\bar{K})^2}{\cdot}\sqrt{\sum_i(L_i-\bar{L})^2}}$
$\sigma_K,\sigma_L$ :標準偏差
$\bar{K},\bar{L}$ :評価の平均
$Cov(K,L)$ :共分散