Numpy реализация простого алгоритма кластеризации

Question

Я хотел бы реализовать простой алгоритм кластеризации, используя python. Сначала я опишу проблему:

У меня есть несколько точек, каждая точка представлена ​​id, и между каждой парой существует вероятность пары, то есть prob(id1, id2)=some_value. Это расположено в numpy массиве формы [N,3], где N - количество всех возможных пар точек. Для большей ясности приведем пример массива:

a = np.array([[1,2, 0.9],
     [2,3, 0.63],
     [3,4, 0.98],
     [4,5, 0.1],
     [5,6, 0.98],
     [6,7, 1]])

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

Кластеризация проблема заключается в соединении точек, которые проходят вероятность сокращения cut=0.5, то есть точки 1,2,3,4 принадлежат одному кластеру, а 5,6,7 принадлежат другому кластеру. Текущее решение, которое у меня есть, - составить список списков (идентификаторов точек), то есть l=[[1,2,3,4],[5,6,7]], дважды зацикливая уникальные идентификаторы точек и массив a. Есть ли более умный и быстрый способ сделать это?

Answer 1

Проблема, которую вы описываете, является проблемой графа. Многие распространенные алгоритмы графов реализованы в пакете networkx.

import numpy as np
import networkx as nx
threshold = 0.5

Если ваш порог написан камнем, вы можете предварительно применить его и построить свой График из оставшихся данных:

G = nx.Graph()
G.add_weighted_edges_from(a[a[:, -1] >= threshold])

Если вы хотите поиграть со своим порогом на графике, вы можете построить весь массив и удалить ребра на графике. Это будет медленнее, чем предварительно обработанная версия:

G = nx.Graph()
G.add_weighted_edges_from(a)
G.remove_edges_from(e for e in g.edges if g.get_edge_data(*e) < threshold)

или альтернативно

G.remove_edges_from(a[a[:, -1] < threshold]])

или

G.remove_edges_from(r for r in a if r[-1] < threshold)

Независимо от того, строите ли вы уменьшенный граф или уменьшаете его удалив ребра, вы можете получить количество и содержимое кластеров, взглянув на компоненты :

>>> nx.number_connected_components(G)
2
>>> for c in nx.connected_components(G):
...     print(c)
{1.0, 2.0, 3.0, 4.0}
{5.0, 6.0, 7.0}