Спектральная кластеризация графика в Python

Без особого опыта работы со спектральной кластеризацией и просто следуя документации (переходите к концу, чтобы узнать о результатах!):

Код:

import numpy as np
import networkx as nx
from sklearn.cluster import SpectralClustering
from sklearn import metrics
np.random.seed(1)

# Get your mentioned graph
G = nx.karate_club_graph()

# Get ground-truth: club-labels -> transform to 0/1 np-array
#     (possible overcomplicated networkx usage here)
gt_dict = nx.get_node_attributes(G, 'club')
gt = [gt_dict[i] for i in G.nodes()]
gt = np.array([0 if i == 'Mr. Hi' else 1 for i in gt])

# Get adjacency-matrix as numpy-array
adj_mat = nx.to_numpy_matrix(G)

print('ground truth')
print(gt)

# Cluster
sc = SpectralClustering(2, affinity='precomputed', n_init=100)
sc.fit(adj_mat)

# Compare ground-truth and clustering-results
print('spectral clustering')
print(sc.labels_)
print('just for better-visualization: invert clusters (permutation)')
print(np.abs(sc.labels_ - 1))

# Calculate some clustering metrics
print(metrics.adjusted_rand_score(gt, sc.labels_))
print(metrics.adjusted_mutual_info_score(gt, sc.labels_))

Вывод:

ground truth
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1]
spectral clustering
[1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
just for better-visualization: invert clusters (permutation)
[0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
0.204094758281
0.271689477828

Общая идея:

Введение в данные и задачу можно найти здесь:

Узлы на графике представляют 34 члена клуба каратэ колледжа. (Захари - социолог, и он был одним из участников.) Граница между двумя узлами указывает на то, что два участника проводили вместе значительное время вне обычных встреч клуба. Набор данных интересен тем, что пока Захари собирал свои данные, в клубе каратэ произошел спор, и он разделился на две фракции: одну во главе с «мистером Мистером». Привет », и один во главе с« Джоном А ». Оказывается, используя только информацию о связности (ребра), можно восстановить две фракции.

Использование sklearn и спектральной кластеризации для решения этой проблемы:

Если родство - это матрица смежности графа, этот метод можно использовать для поиска нормализованных разрезов графа.

Это описывает нормированные разрезы графа как:

Найдите два непересекающихся разбиения A и B вершин V графа, так что A ∪ B = V и A ∩ B = ∅

Учитывая меру сходства w (i, j) между двумя вершинами (например, идентичность, когда они соединены), значение сокращения (и его нормализованная версия) определяется как: cut (A, B) = SUM u в A, v в B: ш (и, в)

...

мы стремимся минимизировать диссоциацию между группами A и B и максимизировать ассоциацию внутри каждой группы.

Звучит нормально. Итак, мы создаем матрицу смежности (nx.to_numpy_matrix(G)) и устанавливаем для параметра affinity значение precomputed (поскольку наша матрица смежности - это наша предварительно вычисленная мера подобия).

В качестве альтернативы можно использовать предварительно вычисленную матрицу аффинности, предоставленную пользователем.

Изменить: я не знал этого, но поискал параметры для настройки и нашел assign_labels:

Стратегия, используемая для присвоения меток в пространстве для встраивания. Есть два способа присвоить метки после вложения лапласиана. К-средние могут применяться, и это популярный выбор. Но он также может быть чувствителен к инициализации. Дискретизация - это еще один подход, который менее чувствителен к случайной инициализации.

Итак, попробуем менее чувствительный подход:

sc = SpectralClustering(2, affinity='precomputed', n_init=100, assign_labels='discretize')

Вывод:

ground truth
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1]
spectral clustering
[0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1]
just for better-visualization: invert clusters (permutation)
[1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0]
0.771725032425
0.722546051351

Это почти полностью соответствует действительности!

Вот фиктивный пример, чтобы увидеть, что он делает с простой матрицей сходства, вдохновленный ответом sascha.

Код

import numpy as np
from sklearn.cluster import SpectralClustering
from sklearn import metrics
np.random.seed(0)

adj_mat = [[3,2,2,0,0,0,0,0,0],
           [2,3,2,0,0,0,0,0,0],
           [2,2,3,1,0,0,0,0,0],
           [0,0,1,3,3,3,0,0,0],
           [0,0,0,3,3,3,0,0,0],
           [0,0,0,3,3,3,1,0,0],
           [0,0,0,0,0,1,3,1,1],
           [0,0,0,0,0,0,1,3,1],
           [0,0,0,0,0,0,1,1,3]]

adj_mat = np.array(adj_mat)

sc = SpectralClustering(3, affinity='precomputed', n_init=100)
sc.fit(adj_mat)

print('spectral clustering')
print(sc.labels_)

Вывод

spectral clustering
[0 0 0 1 1 1 2 2 2]