Python入門トップページ

« 戻る 次へ »

目次

  1. NumPy とは
  2. Python リストの場合
  3. NumPy の使用例
  4. NumPy で線形代数
    1. 行列式
    2. 単位行列
    3. 逆行列
    4. 行列の階数
    5. 固有値
    6. 固有値の応用例：PageRank
    7. ノルム（L1ノルムとL2ノルム）
  5. NumPy の乱数生成

NumPy

NumPy で線形代数

固有値の応用例：PageRank

Webページが下図のような \(n = 6 \) ページからなるリンク構造を持つものとする．例えばページ A からはページ B, D, E へリンクが貼られており，ページ A にはページ B, D, F からリンクが貼られている．

install_01

PageRank は \( n \times n\) の行列 \(H\) の固有値を用いて導出できる．ページ \(i\) から出るリンクの個数を \(P_i\) とする．ページ \(i\) からページ \(j\) にリンクがある場合には，行列 \(H\) の \(i\) 行 \(j\) 列を \(1 / P_i\) とし，それ以外を \(0\) とする．行列 \(H\) を転置した行列に対して，絶対値が最大となる固有値に対応する固有ベクトルを選ぶ．選択された固有ベクトルの各要素を要素の和で割ることにより PageRank が導出される．

実際に Python で PageRank を求めてみよう．まず，リンク構造から行列 \(H\) を作成する．たとえば，ページAからは3つのページ (B, D, E)にリンクが貼られているので，行列の1行目（インデックス0）は2, 4, 5列目（インデックス1,3,4）の要素が1/3となる． 

行列の作成import numpy as np # プログラムの先頭でモジュールを読み込む
H = np.array([
    [0, 1/3, 0, 1/3, 1/3, 0],
    [1/3, 0, 1/3, 0, 0, 1/3],
    [0, 1, 0, 0, 0, 0],
    [1/2, 0, 0, 0, 1/2, 0],
    [0, 0, 0, 0, 0, 1],
    [1/3, 1/3, 0, 0, 1/3, 0]
])
print(H)

[[0.         0.33333333 0.         0.33333333 0.33333333 0.        ]
 [0.33333333 0.         0.33333333 0.         0.         0.33333333]
 [0.         1.         0.         0.         0.         0.        ]
 [0.5        0.         0.         0.         0.5        0.        ]
 [0.         0.         0.         0.         0.         1.        ]
 [0.33333333 0.33333333 0.         0.         0.33333333 0.        ]]

次に行列 \(H\) を転置する． 

行列の転置HT = np.transpose(H)
print(HT)

[[0.         0.33333333 0.         0.5        0.         0.33333333]
 [0.33333333 0.         1.         0.         0.         0.33333333]
 [0.         0.33333333 0.         0.         0.         0.        ]
 [0.33333333 0.         0.         0.         0.         0.        ]
 [0.33333333 0.         0.         0.5        0.         0.33333333]
 [0.         0.33333333 0.         0.         1.         0.        ]]

転置した行列の固有値と固有ベクトルを求める． 

固有値と固有ベクトルの計算w, v = np.linalg.eig(HT)

固有値を表示すると，絶対値が最大になる固有値は1番目（インデックス0）の 1.0 であることがわかる． 

固有値の表示print(w)

[ 1.00000000e+00  4.34258546e-01 -2.33852425e-16 -9.76310729e-02
 -7.67591879e-01 -5.69035594e-01]

全ての固有ベクトルを表示してみる． 

固有ベクトルを表示print(v)

[[ 4.34650760e-01  4.32098738e-18  2.79665526e-16  1.68895809e-01
   7.22434883e-16 -6.17490156e-01]
 [ 5.07092553e-01 -5.60913760e-01  1.75476408e-16  8.99013349e-02
   6.48590681e-01 -1.00875321e-01]
 [ 1.69030851e-01 -4.30552847e-01 -2.67261242e-01 -3.06942357e-01
  -2.81656046e-01  5.90913950e-02]
 [ 1.44883587e-01  4.53703675e-17 -5.34522484e-01 -5.76646362e-01
   2.49568414e-16  3.61717358e-01]
 [ 4.10503495e-01  4.30552847e-01 -2.19345510e-16 -1.00808196e-01
   2.81656046e-01 -3.14864192e-01]
 [ 5.79534346e-01  5.60913760e-01  8.01783726e-01  7.25599770e-01
  -6.48590681e-01  6.12420915e-01]]

このうち，絶対値が最大となる固有値 (1.0) に対応する固有ベクトルだけを表示する． 

固有ベクトルを選ぶvec = v[:, 0]
print(vec)

[0.43465076 0.50709255 0.16903085 0.14488359 0.4105035  0.57953435]

固有ベクトルの要素の和が1になるように，各要素を要素の和で割ることにより，PageRank が計算される． 

PageRankの表示print(vec / vec.sum())

[0.19354839 0.22580645 0.07526882 0.06451613 0.1827957  0.25806452]

目次に戻る

« 戻る 次へ »