関係性を中心としたデータ分析の実践として、グラフ描画アルゴリズムと、それを応用した視覚的分析システムについて学ぶ。ヒトとヒト、ヒトとモノ、モノとモノなどの関係性を表すグラフ構造は、人間関係、購買行動、類似性などの表現に頻繁に用いられる。関係性の図示に用いられるグラフを描画技術は、グラフ論的距離をユークリッド空間に埋め込む技術に始まり長い歴史がある。応用上の制約を折り込んだ柔軟化、高速化を施した新しいアルゴリズムが今日も活発に研究されている。このラウンドでは、最新のアルゴリズムを学び、それを実装する (上手に書けば Python で 50 行未満) とともに視覚的分析の応用について学ぶ。

利用するツール: Python, Pandas, NumPy, NetworkX, Bokeh

担当教員: 脇田建
Email: wakita @ is . titech . ac.jp
2021年度研究プロジェクト: ラウンド共通の内容

DAY1 (2021-10-12)

Zheng+19 SGD法の実装

Zheng and others, “Graph Drawing by Stochastic Gradient Descent,” IEEE TVCG 25(9), pp. 2738-2748, 2019.

実習キット

ソフトウェア開発環境の設定

研究プロジェクトのページを参照して下さい。不明な点は Slack ですぐに質問して下さい。とくに脇田は Windows 環境に疎いので、説明のとおりに動かない可能性があります。そういう場合には、すぐに知らせて下さい。

ソフトウェアの実行方法

仮想環境を起動してから python3 main.py で動くはずです。ウェブブラウザが起動して、そこにグラフが描画されるはずです。

実習の方法

グラフの描画は g/sgd.py のコメント (# ここに Stochastic Gradient Descent 法のアルゴリズムを実装する（脇田の実装は約20行でした）) の後ろに記述して下さい。sgd 関数の引数 G と D がそれぞれグラフ構造と距離行列にあたります。

N = G.order() は頂点数です。

P = np.random.rand(N, 2) は二次元配列で、各頂点の初期配置を与えています。この配置では平面上の単位正方形のなかの点を無作為に設定しています。

グラフ描画の本質は各頂点を移動してストレス関数の値を減少することです。このために二次元配列Pのなかの各頂点の位置を変更していきます。

PはNumpy配列と呼ばれるデータ構造で、二次元配列を表現しています。使い方は以下のとおりです。

P[i]: i番目の頂点の座標
P[i][0]: i番目の頂点のx座標
P[i][1]: i番目の頂点のy座標
P[j] - P[i]: i -> j なベクトル

DAY2 (2021-10-19)

SGD (`sgd`)

GapMinder (`gapminder`)

Python3 で
- import bokeh
- bokeh.sampledata.download()
（Python を抜けて）コマンド行から
- bokeh serve --show .