スペクトラルクラスタリングを用いてグラフ構造のデータをクラスタリングする
はじめに
グラフ構造のデータをクラスタリングする方法について調べていて、 スペクトラルクラスタリングという手法が使えそうだったので、その実験結果を記述します。
参考資料
- https://arxiv.org/pdf/0711.0189.pdf[1]
- https://towardsdatascience.com/spectral-clustering-aba2640c0d5b[2]
- ラプラシアンの中に１人以上、ゼロ固有値がいる！ - FANCOMI Ad-Tech Blog[3]
使用データ
20年4月にtwitter apiで取得したホロライブ(vtuber)のtwitterの共通フォロワーを元に作成した相関行列を利用します。 (少し古いデータですがこれ結構データ取得に時間がかかるので…)
データはこのような感じで、ライバー間で共通のフォロワーが多い組み合わせのときに値が大きくなるようなデータとなっています。(フォロワーが全くかぶっていない場合に0、完全に一致している場合に1になります。)
共通フォロワーが0の組み合わせはなく全結合のグラフなので、グラフネットワークとして図示するとこんな感じです。なんの情報量もない…。
実験
このグラフをいくつかの類似した特性をもつグループに分割するためにスペクトラルクラスタリングを行います。
参考資料[1][2]の記述を参考に計算を行います。 手順はこのようになります。
ラプラシアン行列は正規化する場合としない場合があるようですが、正規化しなかった場合にはクラスタリングをうまく行えなかったため、今回は正規化したものを使用しています。
import pandas as pd import numpy as np from scipy import linalg from sklearn.cluster import KMeans #相関行列の読み込み cor=pd.read_csv("./cor_matrix_hololive.csv") #隣接行列 A=cor-np.diag([1 for _ in range(len(cor))]) #対角行列 D= np.diag(A.sum(axis=1)) #ラプラシアン行列 L = D-A #正規化ラプラシアン行列 L_norm=((np.linalg.inv(D)**(1/2))) @ L @ ((np.linalg.inv(D)**(1/2))) #固有値分解(昇順で結果が出る) vals, vecs = linalg.eig(L_norm) #kmeans kmeans = KMeans(n_clusters=6,random_state=0) kmeans.fit(vecs[:,1:6])
PCAだと大きい固有値をもつ固有ベクトルだけを抽出することで次元削減をしているので、 この手法で小さい方の固有値から使用するのはなぜかと思っていたのですが、 固有値が小さいということは、その成分の分散が小さい、つまり全体に対する影響量が小さいということになります。今回は全結合しているグラフのうち、切断しても全体への影響が少ない部分で分割したいという意図があるので、小さい方から選択していると理解しました。また、固有値が0である個数がグラフが完全に分離している数に相当するために、使用する固有ベクトルの次元数はクラスタリングの分割数(=グラフカットを行いたい数)と同じにしているようです。
sklearnでもスペクトラルクラスタリングのモジュールがあります。 隣接行列を入力とする場合はaffinity='precomputed'とすればクラスタリングが行えます。
from sklearn.cluster import SpectralClustering sc = SpectralClustering(6, affinity='precomputed', n_init=100,assign_labels='kmeans',random_state=0) sc.fit(A)
分割数6でクラスタリングを行った場合、クラスタリング結果は以下のようになりました。 今回の条件だと、手計算したものと、sklearnで計算した結果は一致しました。
| クラスタ1 | クラスタ2 | クラスタ3 | クラスタ4 | クラスタ5 | クラスタ6 |
|---|---|---|---|---|---|
| 不知火フレア | 常闇トワ | 大空スバル | 友人A | AZKi | 紫咲シオン |
| さくらみこ | 姫森ルーナ | 大神ミオ | ロボ子さん | アキ・ローゼンタール | 赤井はあと |
| 星街すいせい | 角巻わため | 猫又おかゆ | ホロライブ公式 | 夜空メル | 夏色まつり |
| 潤羽るしあ | 天音かなた | 百鬼あやめ | ときのそら | 癒月ちょこ | 湊あくあ |
| 兎田ぺこら | 桐生ココ | 戌神ころね | 白上フブキ | ||
| 白銀ノエル | |||||
| 宝鐘マリン |
この結果をざっくり解釈するとこのような形になります。
- クラスタ1: 3期生+3期生とのコラボ多
- クラスタ2: 4期生
- クラスタ3: ゲーマーズ+ゲーマーズとのコラボ多
- クラスタ4: 初期＋運営
- クラスタ5: 1,2期生（登録者数少）
- クラスタ6: 1,2期生（登録者数多）
ホロライブのメンバーはそれぞれの加入時期によって1~4期生等の名称がつけられているのですが、 今回の結果だと、この加入時期が大きな影響を与えているようです。 加入時期が同じということは、同時に認知される可能性が高いですし、コラボ配信などで絡む機会も多い傾向がありますので、 今回の結果がtwitterの共通フォロワー数を用いたことから考えると、比較的妥当性の高いものではないかと思われます。
ちなみに細かいパラメータなどで違いはあるようで、クラスタ数によっては手計算とsklearnの結果にある程度差異は出ます。
まとめ
今回は全結合かつ、各パスにそれほど顕著な差があるわけではないデータだったのですが、 スペクトラルクラスタリングを用いることで、思ったよりも解釈可能なクラスタリング結果を出すことができました。 グラフネットワークの分析は今までやってこなかったですが、結構面白そうです。 あと計算を追っていて線形代数を再履修したくなってきました…。
使用したコードはこちらになります。 github.com
