IT業務効率化

Pythonで理解するグラフ信号処理1【PyGSP】

pythonでグラフ信号処理

[mathjax]

はじめに

本記事はLINE AI Talk #02の感想記事です。テーマはグラフ信号処理でした。このテーマに関してもともと何の知見もなかったのですが、面白い内容だったので、もう少し勉強してみようと思います。

PyGSPという専用のライブラリがあったので、これを利用して勉強しようと思います。

よろしくお願いします。

※一部難解な箇所があり、誤りがあるかもしれません。ぜひコメント欄でご指摘ください。

グラフ信号処理とは

大変恐れ入りますが、筆者が完全に理解できていないため、本記事は未完の状態としてお読みください。(2019/07/16)

PyGSPを使ってみる

PyGSPとは

The PyGSP is a Python package to ease Signal Processing on Graphs

PyGSPとは、Pythonでグラフ信号処理を簡単に実装するためのライブラリです。

The PyGSP facilitates a wide variety of operations on graphs, like computing their Fourier basis, filtering or interpolating signals, plotting graphs, signals, and filters.

PyGSPはグラフに対する豊富な種類の操作が可能です、フーリエ規定を計算したり、信号の間をフィルタリングしたり補完したり、グラフ、信号、フィルター描画したり。

とグラフ信号処理に関するあらゆる操作を可能としているようです。

それでは早速チュートリアルをやってみて、理解を進めていきます。

ライブラリを先にインストールしておきます。

pip install pygsp

チュートリアルをやってみる

必要なライブラリをインストールし、描画のためにmatplotlibを使用するように明示します。

import numpy as np
import matplotlib.pyplot as plt
from pygsp import graphs, filters, plotting

plotting.BACKEND = 'matplotlib'  # The pyqtgraph backend is best suited for interactive visualization.
plt.rcParams['figure.figsize'] = (10, 5)

次にグラフを作成します。

rs = np.random.RandomState(42)

RandomStateはランダムな数値を生成するためのインスタンスを生成してくれます。一言でいえば乱数生成器です。

完全なランダムではなく、引数に与えた整数にしたがって、再現性のある結果をもたらします。

W = rs.uniform(size=(30, 30)) 

numpy.random.uniformは一様分布を返します。30×30の行列式を生成しています。第一引数と第二引数にランダムな数の上限と下限を設定できますが、デフォルトで0~1になっています。

W[W < 0.93] = 0  # Sparse graph.
W = W + W.T  # Symmetric graph.

グラフで0.93以下の値を0に置き換えます。そのあと転置行列を足し合わせて、対称行列にします。

np.fill_diagonal(W, 0)  # No self-loops.

numpy.fill_diagonal(array, val)は対角線条の数値にvalを代入します。

G = graphs.Graph(W)
print('{} nodes, {} edges'.format(G.N, G.Ne))

そしてその行列をグラフのインスタンスとして生成します。nodesの数は30×30行列のため30個です。対象行列であるため、各行と列それぞれに結びつきがあるかないかが、書かれていて、0以外の数が全てエッジとなります。

[[0, 0.9], [0.9, 0]]という2次行列であれば、1つ目の行と2つ目の行は0.9の重みを持つエッジで繋がっていることになります。

PyGSPやってみた

set_coordinatesによってグラフの形が決まりますので、円であることに意味はありません。引数をspringにするとよくみるグラフの形になります。

PyGSP

フーリエ基底を計算する

グラフフーリエ変換によってもたらされる周波数領域においては、固有値=周波数、フーリエ基底=固有ベクトルとなる。式は以下で表される。

$$F(\omega) := <f, e^{j\omega t}> = \int_D f(t)e^{-j\omega t}dt$$

この公式によってグラフの情報(空間情報)を周波数領域に変換できる。周波数領域の話にすることで、周波数(固有値)とフーリエ基底(固有ベクトル)で、グラフを表現することが可能となる。

下の画像は周波数0,1,2に対応したフーリエ基底をグラフとしてプロットした様子である。

pythonでグラフ信号処理

周波数にが小さいほど、グラフ信号も滑らかになる。周波数を大きくすると、下の図のようになる。

pythonでグラフ信号処理

フーリエ基底でグラフの構造を表現することが可能であることがわかった。

一旦ここまで

固有値問題とフーリエ変換が絡んできており、筆者は大学以来のため苦戦しております。

数記事に渡って記載していきますので、よろしくお願いします。

申し訳ありません。。。
ABOUT ME
hirayuki
今年で社会人3年目になります。 日々体当たりで仕事を覚えています。 テーマはIT・教育です。 少しでも技術に親しんでもらえるよう、noteで4コマ漫画も書いています。 https://note.mu/hirayuki