Обратите внимание, что вы не можете напрямую применить кластеризацию k-средних к сети, поскольку не обязательно существует метрика для измерения расстояний между узлами и центроидами. Но ...
.. при условии, что вы предполагаете:
- Длина пути взвешенного кратчайшего пути является мерой расстояния между паройузлов.
- Центроиды - это узлы .Примечание: В традиционной кластеризации k-средних центроиды не обязательно сами являются точками данных.
При этих допущениях сумма расстояний до центроидов минимальна, если вы связываете с каждым узломцентроид с кратчайшим взвешенным кратчайшим путем.
Таким образом, процедура может быть такой:
- Привязать каждый узел к центроиду так, чтобы сумма расстояний от каждого узла до его центроида была минимальной (то есть сумма расстояний в кластере)
- Обновление центроидов
- Повторяйте предыдущие два шага, пока центроиды не станут стабильными.
Эта процедура слабо соответствует процедуре k-среднего значения кластеризации, то есть для минимизации суммы квадратов внутри кластера (WCSS).
Хотя эта процедура аналогична кластеризации k-средних в точках данных в метрическом пространстве, я бы не сталназывать это K-означает кластеризацию.Тем более, что положение центроидов ограничено узлами в сети.
Вот как вы можете подойти к этому с помощью python:
1. Определить начальные центроиды :
centroids = [3, 6]
2. Для каждого узла получить все кратчайшие пути ко всем центроидам .
Например:
shortest_paths = [[(cent, nx.shortest_path(
G, source=n ,target=cent, weight='weight'
)) for cent in centroids] for n in G.nodes
]
Это дает (здесь они сообщаются вместе с идентификатором центроида):
In [26]: shortest_paths
Out[26]:
[[(3, [0, 1, 5, 6, 4, 3]), (6, [0, 1, 5, 6])],
[(3, [1, 5, 6, 4, 3]), (6, [1, 5, 6])],
[(3, [3]), (6, [3, 4, 6])],
[(3, [2, 3]), (6, [2, 3, 4, 6])],
[(3, [7, 2, 3]), (6, [7, 2, 3, 4, 6])],
[(3, [4, 3]), (6, [4, 6])],
[(3, [6, 4, 3]), (6, [6])],
[(3, [5, 6, 4, 3]), (6, [5, 6])]]
3. Рассчитать фактическое расстояние , т.е. суммировать веса по путям для всех кратчайших путей для всех узлов:
Например:
distances = [
[
(
sp[0], # this is the id of the centroid
sum([
G[sp[1][i]][sp[1][i+1]]['weight']
for i in range(len(sp[1]) - 1)
]) if len(sp[1]) > 1 else 0
) for sp in sps
] for sps in shortest_paths
]
Значения расстояний:
In [28]: distances
Out[28]:
[[(3, 15), (6, 9)],
[(3, 12), (6, 6)],
[(3, 0), (6, 6)],
[(3, 2), (6, 8)],
[(3, 7), (6, 13)],
[(3, 1), (6, 5)],
[(3, 6), (6, 0)],
[(3, 10), (6, 4)]]
4. Получите центроид с минимальным расстоянием для всех узлов:
Например:
closest_centroid = [
min(dist, key=lambda d: d[1])[0] for dist in distances
]
Вывод в группировку по центроидам:
In [30]: closest_centroid
Out[30]: [6, 6, 3, 3, 3, 3, 6, 6]
5. Обновление центроидов в качестве токаЦентроиды t могут больше не быть действительными центроидами группы:
Подход:
# for each group
# for each member of the group
# get the distance of shortest paths to all the other members of the group
# sum this distances
# find the node with the minimal summed distance > this is the new centroid of the group
Итерация :Если новые центроиды не совпадают со старыми, используйте новые центроиды и повторите шаги 2.- 5.
Последний шаг: Если новые центроидынайдены в шаг 5. совпадают со старыми или вы достигли предела итерации, свяжите ближайший центроид с каждым узлом :
Например:
nodes = [n for n in G] # the actual id of the nodes
cent_dict = {nodes[i]: closest_centroid[i] for i in range(len(nodes))}
nx.set_node_attributes(G, cent_dict, 'centroid')
или nx.set_node_attributes(G, 'centroid', cent_dict), если вы все еще на v1.x.
Это был бы подход для выполнения сортировкикластеризации k-средних для сети.
Надеюсь, что помогло и удачного кодирования!