データマイニング
データマイニング：多量のデータ集合から、意味のある情報を抜き出す手法多量のデータが電子的に蓄積され
多量のデータを処理・分析することが可能に
予備知識なしに理解可能な計算法のいくつかを直感的に紹介
- グーグルのページランクアルゴリズム
- 推薦システム
- マーケットバスケット分析（アソシエーションルール）
グーグルのページランク
グーグルの創設者 Sergey Brin と Lawrence Page による現在のグーグルの隆盛の基礎をなす技術
ページの重要度をそのページがどれだけ閲覧されるのかで決める
Webページの間のリンク関係に基づいて測る
パズル：1から8の番号のついたWebページの間のリンク関係が右のようなグラフ(ネットワーク)になっている。このとき、どのページが重要、すなわち、よく閲覧されるか。隣接行列⇒遷移確率行列
グラフの隣接行列$A$：$A(i,j)=\begin{cases} 1&頂点iから頂点jへ矢印(リンク)\\ 0&なければ \end{cases}$
隣接行列$A$から遷移確率行列$P$を求めるとき
- 頂点のどれか(例えば１)から出発
- 矢印のどれかを等確率で選んで、遷移(移動)
- 出る矢印がなければ、その頂点にとどまる
$P(i,j)=\begin{cases} A(i,j)/k&k>0（条件\text{B}）\\ 1&k=0でi=j（条件\text{C}）\\ 0&k=0でi\ne j \end{cases}$
一般に各頂点に対し、次の頂点への遷移確率(必ずしもすべて等しいとは限らないが和は１)が与えれらたグラフをマルコフ連鎖といい、その行列表現を遷移確率行列という。
パズル．確率遷移行列の計算
パズル．確率遷移行列の計算
- 例示グラフの確率遷移行列を計算せよ
パラメータ(意味は後述)を１にして、準備ボタンをクリックする - ページ(頂点)数を4にして、準備ボタンをクリックし、確率遷移行列が条件のCを満たしていることを確認せよ
また、どのようなグラフの確率遷移行列を計算しているのか、図示せよ。
定常状態
ある頂点から出発して(確率的な)遷移を繰り返すと、$n$回目の遷移の後でそれぞれの頂点にいる確率の分布（状態ベクトル）が定義される$n+1$回目の状態ベクトル$=n$回目の状態ベクトル×確率遷移行列
ページランクアルゴリズムの基本的な考え方
状態ベクトル(確率分布)が定常状態に収束したら、確率はそのページを平均的に訪れる(閲覧する)頻度を表すので、重要度の指標とする
グラフが次の条件を満たすと出発頂点がどこであるかに関わらず状態ベクトルは定常状態に収束する
- グラフが強連結である(各頂点が互いにつながっている)
- グラフのサイクル(循環する道)の長さの最大公約数が１である
パズル．定常状態アプリで準備ボタンをクリックした後、更新ボタンのクリックを繰り返すと、各頂点にいる確率の分布が変化(収束)が見られる。
- ページ数を3、パラメータを1にして(隣接行列はそのまま！)、条件 b が成り立たないと確率分布が循環することを確認せよ。
- ページ数を6にすると条件 a が成り立たない。グラフを書いて確認せよ。
- ページ数を6、パラメータを1とし、異なる定常状態に収束するような初期状態(出発頂点)を求めよ。
パラメータαの導入
パラメータ$1$の議論・マルコフ連鎖としてよく知られ、さまざまな場面に応用されてきた
・グラフがWeb上のページリンクを表すという文脈ではおかしな仮定
- リンクを持たないページ(PDFファイル等)にとどまり続ける
- 必ずリンクをたどる(各リンクの遷移確率の和が1)
パラメータαの意味
ページでリンク(のどれか)をたどる確率α(＝0.85)
確率1－αで、新たなページを(等確率で)選んでネットサーフィンを始める
遷移確率行列$P_\alpha$は、総ページ数を$N$として
$P_\alpha(i,j)=\begin{cases} \alpha A(i,j)/k+(1-\alpha)/N & 頂点iから出る矢印の本数k>0\\ 1/N & k=0\\ \end{cases}$
・すべてのページの間に矢印(遷移)が付く⇒定常状態に必ず収束
・定常状態への収束の速さは$\alpha^n$に比例
・計算速度と、定常状態(ページランク)の正確さとのバランス
⇒$\alpha=0.85$（と言われている）
パズル．パラメータα
アプリで収束までの回数および各ページのランク(確率)値を、パラメータα=１のときとパラメータα=0.85のときで、比較せよ
・グーグルがページのランク付けに利用しているのはリンク構造だけではないし、詳細は公表されていない
・解説したような単純なものでない
・検索サイトがつけるランクをアップさせるための様々な工夫や業者が存在し、検索サイトとの間でいたちごっこ
アプリで収束までの回数および各ページのランク(確率)値を、パラメータα=１のときとパラメータα=0.85のときで、比較せよ
・グーグルがページのランク付けに利用しているのはリンク構造だけではないし、詳細は公表されていない
・解説したような単純なものでない
・検索サイトがつけるランクをアップさせるための様々な工夫や業者が存在し、検索サイトとの間でいたちごっこ
推薦システム
ショッピングサイトで品物を買う(見る)と、他の品物も勧められる。あなたが薦められるのは
- 人ベースの推薦：嗜好(購買行動)が似た客が買った品物
- 物ベースの推薦：買った(見た)品物と(売れ方が)似ている品物
基本的なアイディア：似た人(物)は、似た動きをする
表 $A$：本人(0)と人1～人6の物A～Eに対する評価(購買数)、空欄は評価(購買)無し
[人ベース]： 本人と人$i$の間の(ユークリッド)距離(の2乗)
$\displaystyle d(i)=\sum_{i,0が共に評価しているX}(A(i,X)-A(0,X))^2$
本人の物$X$に対する予想評価(推薦スコア) $\displaystyle ={\large(}\sum_{A(i,X)\ne 空}A(i,X)(1+d(i))^{-1}{\large)}/{\large(}\sum_{A(i,X)\ne 空}(1+d(i))^{-1}{\large)}$
即ち、近い人ほど大きな重み$1/(1+d(i))$を評価$A(i,X)$につけて平均をとる
[物ベース]：
物$X$と$Y$の間の(ユークリッド)距離(の2乗)
$\displaystyle d(X,Y)=\sum_{X,Yを共に評価している人n}(A(n,X)-A(n,Y))^2$
本人の物$X$に対する予想評価(推薦スコア) $\displaystyle ={\large(}\sum_{A(0,Y)\ne 空}A(0,Y)(1+d(X,Y))^{-1}{\large)}/{\large(}\sum_{A(0,Y)\ne 空}(1+d(X,Y))^{-1}{\large)}$
即ち、本人が物$Y$に与えた評価$A(0,Y)$に、物$X$と$Y$の距離$d(X,Y)$から定まる重み$1/(1+d(X,Y))$をつけた重みつき平均をとる。
実際の推薦システムでは、求めた評価値をそのまま表示するのではなく、評価の高い品物から順に(いくつか)推薦する
$\displaystyle d(X,Y)=\sum_{X,Yを共に評価している人n}(A(n,X)-A(n,Y))^2$
本人の物$X$に対する予想評価(推薦スコア) $\displaystyle ={\large(}\sum_{A(0,Y)\ne 空}A(0,Y)(1+d(X,Y))^{-1}{\large)}/{\large(}\sum_{A(0,Y)\ne 空}(1+d(X,Y))^{-1}{\large)}$
即ち、本人が物$Y$に与えた評価$A(0,Y)$に、物$X$と$Y$の距離$d(X,Y)$から定まる重み$1/(1+d(X,Y))$をつけた重みつき平均をとる。
実際の推薦システムでは、求めた評価値をそのまま表示するのではなく、評価の高い品物から順に(いくつか)推薦する
推薦法の比較
距離を求める計算：人ベース推薦の方が容易人ベース推薦：各人の、本人との距離だけを計算
物ベース推薦：すべての物の組み合わせについて計算
物ベース推薦の長所
推薦を行う前に、本人の嗜好がわからなくても、あらかじめ品物の間距離を計算しておける
（人ベース推薦で利用する本人との距離は、本人の嗜好がわかって初めて計算できる）
各品物に対してそれに近い品物との距離だけ記録しておけばよい
パズル．あらかじめ距離を計算しておけることは、Web上のリアルタイムの応答では決定的な利点である。その理由を考えよ。
マーケットバスケット分析
・スーパーマーケットのレジで集められるPOS(Point Of Sale)データからバスケット(籠)の中身を分析・どの商品とどの商品が同時に買われやすいかを求める
・伝説的な事例：週末に紙おむつを買う人はビールも買う
アソシエーションルール
次の形の有効なルールを探す
$A\to B$：$A$(を買う人)ならば$B$(も買う)
$A$や$B$は、一般的には複数の商品や条件からなり、冒頭の例は
(週末∧紙おむつ) → ビール
簡単のため、$A$や$B$はそれぞれ単一の商品とする
$\mathcal U$をすべての籠の集合
商品$A$が入っている籠の集合を$\mathcal A$($\mathcal B$も同様)
集合$\mathcal X$ の要素数を$|\mathcal X|$で表す
アソシエーションルール $A\to B$ の有効性を、以下の数値で評価
$\mathcal U$をすべての籠の集合
商品$A$が入っている籠の集合を$\mathcal A$($\mathcal B$も同様)
集合$\mathcal X$ の要素数を$|\mathcal X|$で表す
アソシエーションルール $A\to B$ の有効性を、以下の数値で評価
- サポート$(A\to B)$$=|{\mathcal A}\cap{\mathcal B}|/|{\mathcal U}|$：ルールを支持する籠が全体に占める比率
サポート値が低いルールは少数の事例にしか当てはまらず一般性を持たない。 - 信頼度$(A\to B)$$=|{\mathcal A}∩{\mathcal B}|/|{\mathcal A}|$：$A$を含む籠の中で$B$を含む籠が占める比率
信頼度が低いルールは、そもそもルールが成り立っていない - 改善率$(A\to B)$$=信頼度(A\to B)/信頼度(\ \to B)=(|{\mathcal A}∩{\mathcal B}|\cdot|{\mathcal U}|)/(|{\mathcal A}|\cdot|{\mathcal B}|)$：仮定$A$による信頼度の改善率
信頼度が高くても改善率が1以下なら、$B$が買われる理由が$A$を買うことにはなく、そもそも無条件に(あるいは他の理由で)$B$が買われていることを意味するので、この場合もルールが有効であるとはいえない。
アプリを使って、サポート、信頼度、改善率の意味を理解しよう。
パズル．アソシエーションルールの評価
左のアプリで例示されているデータを使って、以下の問いに答えよ。
1. 単一前後件ルールで最高信頼度のルールはどれか
2. 単一前後件ルールで最高改善度のルールはどれか
3. ルール AB→Cについて、そのサポート、信頼度、改善率の値を求め、値がそうなる理由を説明せよ
4. XY→Zの形で改善率2.5以上のルールを求めよ
パズル．アソシエーションルールの評価
左のアプリで例示されているデータを使って、以下の問いに答えよ。
1. 単一前後件ルールで最高信頼度のルールはどれか
2. 単一前後件ルールで最高改善度のルールはどれか
3. ルール AB→Cについて、そのサポート、信頼度、改善率の値を求め、値がそうなる理由を説明せよ
4. XY→Zの形で改善率2.5以上のルールを求めよ
長所と短所
〇対象となるデータの中に潜む有効なルールを探し出す探索的手法〇結果をアソシエーションルールという分かりやすい形で提供
×品数が多くなると、$X\to Y$という形の規則の個数は指数関数的に増大
⇒すべて調べるのは現実的ではない
×｢苗→肥料」のように、当然のルールが多数出る
⇒真に有効なルールを見出すには、機械だけでは無理
〇推薦システムと異なり、個人と紐付けられていない匿名データに対しても有効