UMAPをもちいたネットワークデータの次元削減

UMAPとは？

UMAP（Uniform Manifold Approximation and Projection）は、2018年に提案された非線形次元削減手法です。UMAPは、リーマン多様体の概念に基づいており、高次元データを低次元空間に埋め込む際に、データの位相的構造を保持することを目的としています。

UMAPは、t-SNEと比べて、より高速に次元削減を行うことができ、大規模なデータセットに対して適用可能です。
また、埋め込み空間での距離関係が元の高次元空間での距離関係をより忠実に反映するという利点があります。

実装例.1

この例では、scikit-learnのdigitsデータセットを使用しています。Pythonライブラリは「umap-learn」を用いて、64次元の特徴量を2次元に削減し、結果を散布図で可視化しています。

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import load_digits
from umap import UMAP

# データセットの読み込み
digits = load_digits()
X = digits.data

# UMAPによる次元削減
reducer = UMAP(n_components=2, random_state=42)
embedding = reducer.fit_transform(X)

# 結果の可視化
plt.scatter(embedding[:, 0], embedding[:, 1], c=digits.target, cmap='Spectral', s=5)
plt.colorbar(boundaries=np.arange(11)-0.5).set_ticks(np.arange(10))
plt.title('UMAP Embedding of Digits')
plt.show()

実装例.2

この例では、近傍数とデータ点間の最小距離を調整し、マンハッタン距離を使用しています。また、ラベル情報を用いた教師あり次元削減を行っています。

ここでは、近傍数を30、データ点間の最小距離を0.1、出力次元を2、距離関数をマンハッタン距離に設定しています。

# パラメータのチューニングと教師あり次元削減
reducer = UMAP(n_neighbors=30, min_dist=0.1, n_components=2, metric='manhattan', random_state=42)
embedding = reducer.fit_transform(X, y=labels)

# 結果の可視化
plt.figure(figsize=(10, 8))
plt.scatter(embedding[:, 0], embedding[:, 1], c=labels, cmap='Spectral', s=5)
plt.colorbar(boundaries=np.arange(11)-0.5).set_ticks(np.arange(10))
plt.title('UMAP Embedding with Tuned Parameters and Supervised Dimensionality Reduction')
plt.show()

UMAPのパラメータについて、表形式で以下にまとめます。

パラメータ	説明	影響
n_neighbors	近隣の点の数を指定	値が大きいほど大域的なデータ構造が強調され、小さい値では局所的な特徴が強調されます。
min_dist	埋め込み空間における点間の最小距離を指定	値が小さいほどクラスタ内の点が緊密になり、大きい値では点間が離れます。
n_components	目標とする低次元空間の次元数	通常は2または3で、視覚化に利用されます。より高い次元も設定可能です。
metric	距離計算に使用されるメトリック（距離尺度）	メトリックによってデータポイント間の距離が変わり、得られる埋め込みの構造も変わります。選択肢: euclidean, manhattan, chebyshev, minkowski, hamming など
random_state	結果の再現性を保証するための乱数シード	同じrandom_stateを使用することで、結果が一貫して再現可能になります。

これらのパラメータは、データの特性や分析の目的に応じて適切に調整することが求められます。

UMAPを用いたネットワークデータの次元削減

ここから本題です。

ノードの特徴量から次元削減

ここでは、ランダムな有向グラフを生成し、各ノードに対して複数の中心性指標やクラスタリング係数などの特徴量を計算します。その後、UMAPを用いて特徴量を2次元に次元削減し、元のグラフと次元削減後のグラフを可視化しています。

import networkx as nx
import numpy as np
from umap import UMAP
import matplotlib.pyplot as plt

# ランダムな有向グラフの生成
G = nx.gnp_random_graph(100, 0.05, directed=True)

# ランダムに選択したノードに自己参照ループを追加
num_self_loops = 10
nodes_with_self_loops = np.random.choice(G.nodes(), num_self_loops, replace=False)
G.add_edges_from(zip(nodes_with_self_loops, nodes_with_self_loops))

# 特徴量の計算
features = []
for node in G.nodes():
    # 次数中心性
    degree_centrality = nx.degree_centrality(G)[node]
    
    # 媒介中心性
    betweenness_centrality = nx.betweenness_centrality(G)[node]
    
    # 近接中心性
    closeness_centrality = nx.closeness_centrality(G, wf_improved=True)[node]
    
    # 固有ベクトル中心性
    eigenvector_centrality = nx.eigenvector_centrality_numpy(G)[node]
    
    # クラスタリング係数
    clustering_coefficient = nx.clustering(G, nodes=[node])[node]
    
    # 自己参照ループの有無
    self_loop = 1 if G.has_edge(node, node) else 0
    
    features.append([degree_centrality, betweenness_centrality, closeness_centrality,
                     eigenvector_centrality, clustering_coefficient, self_loop])

features = np.array(features)

# UMAPによる次元削減
reducer = UMAP(n_components=2, random_state=42)
embedding = reducer.fit_transform(features)

# 結果の可視化
plt.figure(figsize=(12, 6))

# 元のグラフの可視化
plt.subplot(1, 2, 1)
pos = nx.spring_layout(G, seed=42)
nx.draw_networkx_nodes(G, pos, node_size=50, node_color='b', alpha=0.7)
nx.draw_networkx_edges(G, pos, edge_color='gray', alpha=0.5, arrows=True, width=0.5)

# ノード番号のプロット（元のグラフ）
for node in G.nodes():
    plt.annotate(node, pos[node], fontsize=8, ha='center', va='center')

plt.axis('off')
plt.title('Original Graph')

# 次元削減後のグラフの可視化
plt.subplot(1, 2, 2)
plt.scatter(embedding[:, 0], embedding[:, 1], c='b', alpha=0.7, s=50)

# ノード番号のプロット（次元削減後のグラフ）
for i, node in enumerate(G.nodes()):
    plt.annotate(node, (embedding[i, 0], embedding[i, 1]), fontsize=8, ha='center', va='center')

plt.xlabel('UMAP Dimension 1')
plt.ylabel('UMAP Dimension 2')
plt.title('Graph Embedding')

plt.tight_layout()
plt.show()

この可視化により、元の高次元のグラフ構造と、次元削減後の低次元の表現を比較することができます。

まとめ

UMAPによる次元削減は、グラフの構造を保持しつつ、低次元の空間にグラフを埋め込むことができます。これにより、グラフの全体的な構造やノード間の関係性を視覚的に理解しやすくなります。
また、次元削減後のデータを用いて、クラスタリングや分類などの他の分析手法を適用することもできます。
次元削減は、計算効率の向上やノイズの除去にも役立ちます。

Appendix. umap-learnのパラメータまとめ

パラメータ	説明	デフォルト値
n_neighbors	局所的な構造を決定する際に考慮する近傍点の数	15
min_dist	低次元空間における点間の最小距離	0.1
n_components	出力の次元数	2
metric	高次元空間における距離メトリック	euclidean
init	低次元空間における初期配置	spectral
random_state	乱数生成器の状態	None
transform_seed	新しいデータポイントを変換する際の乱数シード	None
verbose	処理の進行状況を表示するかどうか	False
a	埋め込みの学習時に使用される重み付けのパラメータ。高次元空間と低次元空間の間の距離の関係を制御するパラメータ。a が大きいほど、高次元空間で近い点は低次元空間でも近くに配置される	None
b	埋め込みの学習時に使用される重み付けのパラメータ。低次元空間における点の分布を制御するパラメータ。b が大きいほど、低次元空間で点が広く分散する	None