Vietoris-Rips filtrationのチュートリアル

このチュートリアルでは Vietoris-Rips filtrationを使ってパーシステント図を計算する例です。

Vietoris-Rips filtrationは以下のような利点があります。

• 2点間の距離の情報(distance matrix)だけあれば計算できる
  • 遺伝子間の距離情報のようにユークリッド空間以外の空間でも計算できる
  • alpha filtrationは2次元、3次元でしか現在は計算できないが、より高次元の点でも計算できる

一方で以下のような欠点もあります。

• 組み合わせ爆発により、計算コストが高い
  • 特に高次のホモロジーの計算が困難
  • そのため、計算する次数を制限することは必須
  • また、実用的な計算時間のためある距離より大きな辺は無視する必要がある場合がある
• データの幾何的な情報を近似的にしか反映していない
  • 各点に球を置くやりかたとはけっこう大きなずれが生じる

まず必要なライブラリを読み込みます

import numpy as np
import homcloud.interface as hc
from scipy.spatial import distance_matrix
import matplotlib.pyplot as plt
%matplotlib inline

200次元のデータを100個、ランダムに準備します

data = np.random.uniform(size=(100, 200))

distance matrix (距離行列) を scipy.spatial.distance_matrix を使って計算します。

dmatrix = distance_matrix(data, data)

distance matrix は 100x100 の行列です

dmatrix.shape

(100, 100)

パーシステント図の計算

homcloud.interface.PDList.from_rips_filtration でパーシステント図を計算します。引数の意味は以下の通りです。

• 最初の引数は距離行列
• maxdim で最大次数を指定
• save_to で保存先を指定
• ここでは指定していませんが、maxvalue で取り扱う birth/death time の最大値を指定します。

%%time
hc.PDList.from_rips_filtration(dmatrix, maxdim=3, save_to="rips.pdgm")

CPU times: user 1.19 s, sys: 31.8 ms, total: 1.22 s
Wall time: 1.21 s

PDList(path=rips.pdgm)

計算時間は maxdim をどうするかでかなり変わります。

• 2 - 一瞬
• 3 - 5-10 sec
• 4 - 2min
• それ以上は試してない。maxdimに対して指数的に計算量が増大すると思われる

これらの計算は ripser というプログラムで計算されています。この ripser は Vietoris-Rips filtration による パーシステント図を計算するには(おそらく)最速のプログラムです。

パーシステント図の可視化

以下のようにしてパーシステント図を読み込みます。

pdlist = hc.PDList("rips.pdgm")

1次のパーシステント図を可視化します

pd1 = pdlist.dth_diagram(1)
pd1.histogram().plot(colorbar={"type": "log"})

2次のパーシステント図も可視化します。

pd2 = pdlist.dth_diagram(2)
pd2.histogram().plot(colorbar={"type": "log"})

pd3 = pdlist.dth_diagram(3)
pd3.histogram().plot(colorbar={"type": "log"})

maxvalue の効果

さて、ここで PD を計算するときに maxvalue を指定すると何がおきるかを見ていきましょう。 まず、distance matrixの値がどのように分布しているか、histogramを見てみましょう。

numpy.triu_indicesを使うと距離行列の上半分だけ取り出すことができます。

plt.hist(dmatrix[np.triu_indices(100, 1)], 100); None

5〜6.5の間に分布しているようです。

ここでは 5.6 を上限として計算しましょう。

%%time
hc.PDList.from_rips_filtration(dmatrix, maxdim=3, maxvalue=5.6, save_to="rips-5.6.pdgm")

CPU times: user 14.9 ms, sys: 8.01 ms, total: 22.9 ms
Wall time: 187 ms

PDList(path=rips-5.6.pdgm)

さきほどよりかなり計算時間が早くなったことがわかると思います。 ここで注意しておくと、maxvalueを使う場合には ripser は使われず、diphaが代わりに使われます。 diphaはripserよりかなり遅いので、上限をうまく指定しないと却って遅くなる可能性もあります。

それでは PD をプロットしましょう。

pdlist56 = hc.PDList("rips-5.6.pdgm")

pd56_1 = pdlist56.dth_diagram(1)
pd56_1.histogram().plot(colorbar={"type": "log"})
pd56_2 = pdlist56.dth_diagram(2)
pd56_2.histogram().plot(colorbar={"type": "log"})
pd56_3 = pdlist56.dth_diagram(3)
pd56_3.histogram().plot(colorbar={"type": "log"})

PDの範囲の最大値が5.6になっています。maxvalueを指定しない場合と比較してみましょう。

pd1.histogram((5.1, 5.7)).plot(colorbar={"type": "log", "max": 10})
pd56_1.histogram((5.1, 5.7)).plot(colorbar={"type": "log", "max": 10})
pd2.histogram((5.3, 5.9)).plot(colorbar={"type": "log", "max": 10})
pd56_2.histogram((5.3, 5.9)).plot(colorbar={"type": "log", "max": 10})
pd3.histogram((5.3, 5.9)).plot(colorbar={"type": "log", "max": 10})
pd56_3.histogram((5.3, 5.9)).plot(colorbar={"type": "log", "max": 10})

maxvalueを指定したほうはbirth, deathともに5.6の所で切れていることがわかると思います。5.6よりも下の部分はどちらも同じ ヒストグラムになっています。

ではこれらの切りとられた birth-death pairはどこに行ったのでしょうか？ 実はその一部は death time が∞なbirth-death pairとなっています。 そのような birth-death pair の birth time は essential_births というattributeに保持されています。では見てみましょう。

pd2.essential_births

array([], dtype=float64)

pd56_2.essential_births

array([5.49050903, 5.49558115, 5.49599171, 5.4972477 , 5.54403162,
       5.54411221, 5.54651642, 5.54965925, 5.55589342, 5.55590916,
       5.55789328, 5.55789328, 5.56123495, 5.56383944, 5.56398296,
       5.56482077, 5.56669712, 5.56908083, 5.57187653, 5.57208538,
       5.57232475, 5.57366419, 5.57515287, 5.57604694, 5.57734394,
       5.58260918, 5.58372021, 5.58549118, 5.58569527, 5.58782101,
       5.5894084 , 5.59046316, 5.59143591, 5.59158564, 5.59349155,
       5.5941062 , 5.59486675, 5.59713125, 5.597785  , 5.597785  ,
       5.59828329, 5.5983448 , 5.59896135, 5.59946871])

このように、maxvalueを指定しなかった場合にはessential_birthsは空ですが、指定した場合にはいくつかの値が得られます。 birth が 5.6 以下で death が 5.6 以上の birth-death pair がここに移動します。birth, death がともに 5.6以上の場合には それらの birth-death pair は痕跡もなく消されます。

これらの death time が ∞ な birth-death pair を並べてプロットすることもできます。

pd56_1.histogram((5.1, 5.7)).plot(colorbar={"type": "log", "max": 10}, plot_ess=True)
pd56_2.histogram((5.3, 5.9)).plot(colorbar={"type": "log", "max": 10}, plot_ess=True)
pd56_3.histogram((5.3, 5.9)).plot(colorbar={"type": "log", "max": 10}, plot_ess=True)

逆解析について

パーシステント図の上の各点は元データのホモロジー的構造(1次元はリング，2次元は空隙，等々)に対応しています．その構造を取りだすことができればデータ解析に便利でしょう．アルファ複体を使う場合には optimal volume の利用でこれが可能になります．しかし Vietoris-Rips 複体は単体の個数が多いためそのような構造を抽出するのは難しい問題になります．しかし1次元のPDに関してのみはある種の近似により比較的簡単にそういった構造の抽出が可能です．ここではその構造(optimal 1-cycleと呼びます)を抽出する方法について説明しましょう．

optimal 1-cycleを計算するためには，from_rips_filtrationを呼ぶ際にsave_graph=Trueという引数を付ける必要があります．1次元PDしか使わないのでmaxdimも1で計算しましょう．

%%time
hc.PDList.from_rips_filtration(dmatrix, maxdim=1, save_graph=True, save_to="rips_with_graph.pdgm")

CPU times: user 6.61 ms, sys: 63 µs, total: 6.68 ms
Wall time: 6.23 ms

PDList(path=rips_with_graph.pdgm)

1次元のPDを読み込んでプロットします．

pd1 = hc.PDList("rips_with_graph.pdgm").dth_diagram(1)

pd1.histogram().plot(colorbar={"type": "log"})

(5.3, 5.6) に一番近い点を取り出します．

pair = pd1.nearest_pair_to(5.3, 5.6)
pair

Pair(5.251756191253662, 5.5174455642700195)

Optimal 1-cycleを計算します．計算時間はそれほどかかりません．

optimal_1_cycle = pair.optimal_1_cycle()

boundary_points というメソッドを呼び出すとリング上の点が得られます．各点は番号で表現され，その番号は最初の点から0, 1, 2, ... と昇順で付けられます．

optimal_1_cycle.boundary_points()

[90, 97, 19, 22, 25, 43, 80, 17]

注意

optimal 1-cycle を計算するときに， Pairs with the same birth time というエラーが発生する場合があります．実は距離行列の対称でない要素が同じ値を持っているとこの機能はうまく動きません．このようなエラーが出場合には距離行列に小さなノイズを加えておくとうまくいくでしょう．対称性を保ったままノイズを加えてください．

以上でこのチュートリアルは終わりです。