После более подробного изучения я обнаружил, что это так называемая задача о максимальном независимом множестве в теории графов, которая, к сожалению, NP-трудная.
An независимое множество S графа G - это подмножество вершин G, такое, что никакие вершины в S не смежны друг с другом. В нашем случае мы ищем максимально независимый набор (MIS), то есть независимый набор с максимально возможным числом вершин.
Существует несколько библиотек для работы с графами и сетями, например: igraph или NetworkX , которые имеют функции для поиска максимально независимых наборов. В итоге я использовал igraph.
Для моей задачи мы можем рассматривать изображения как вершины графа G, а «матрицу сходства» - как матрицу смежности:
images = ['image_0', 'image_1', 'image_2', 'image_3', 'image_4']
sm = np.array([[1, 1, 1, 0, 1],
[1, 1, 0, 0, 1],
[1, 0, 1, 0, 0],
[0, 0, 0, 1, 0],
[1, 1, 0, 0, 1]])
# Adjacency matrix
adj = sm.copy()
np.fill_diagonal(adj, 0)
# Create the graph
import igraph
g = igraph.Graph.Adjacency(adj.tolist(), mode='UNDIRECTED')
# Find the maximum independent sets
g.largest_independent_vertex_sets()
[(1, 2, 3), (2, 3, 4)]
К сожалению, это слишком медленно для тысяч изображений (вершин). Так что я все еще открыт для предложений по более быстрому способу сделать это (возможно, вместо того, чтобы найти все MIS, просто найдите).
Примечание : предлагаемые решения от @Sergey (ОБНОВЛЕНИЕ # 1) и @marke не всегда возвращают MIS - они являются жадными приблизительными алгоритмами, которые удаляют вершину максимальной степени, пока не останется ребро. Чтобы продемонстрировать это, рассмотрим следующий пример:
sm = np.array([[1, 1, 0, 0, 0, 1],
[1, 1, 0, 1, 0, 0],
[0, 0, 1, 1, 1, 0],
[0, 1, 1, 1, 0, 0],
[0, 0, 1, 0, 1, 1],
[1, 0, 0, 0, 1, 1]])
Оба решения возвращают [3, 5], но для этого примера максимальные независимые наборы равны двум, [(0, 3, 4), (1, 2, 5)], как правильно найдено с помощью igraph. Чтобы понять, почему этим решениям не удается найти MIS, ниже приведен рисунок, показывающий, как удаляются вершины и ребра на каждой итерации (что является «побочным эффектом» np.argmax, возвращая первое вхождение для нескольких вхождений максимального значения). ):
Решение Сергея (ОБНОВЛЕНИЕ № 2), похоже, работает, однако оно намного медленнее, чем у igraph largest_independent_vertex_sets(). Для сравнения скорости вы можете использовать следующую случайно сгенерированную матрицу подобия длины 100:
a = np.random.randint(2, size=(100, 100))
# create a symmetric similarity matrix
sm = np.tril(a) + np.tril(a, -1).T
np.fill_diagonal(sm, 1)
# create adjacency matrix for igraph
adj = sm.copy()
np.fill_diagonal(adj, 0)
Обновление : получается, что хотя у меня есть тысячи изображений - вершин, количество ребер является относительно небольшим (т.е. у меня есть разреженный график), поэтому использование igraph для поиска MIS является приемлемым с точки зрения скорости. Альтернативно, в качестве компромисса можно использовать жадный приближенный алгоритм для нахождения большого независимого набора (или MIS, если повезет). Ниже приведен алгоритм, который выглядит довольно быстро:
def independent_set(adj):
'''
Given adjacency matrix, returns an independent set
of size >= np.sum(1/(1 + adj.sum(0)))
'''
adj = np.array(adj, dtype=bool).astype(np.uint8)
np.fill_diagonal(adj, 1) # for the purposes of algorithm
indep_set = set(range(len(adj)))
# Loop until no edges remain
while adj.sum(0).max() > 1:
degrees = adj.sum(0)
# Randomly pick a vertex v of max degree
v = random.choice(np.where(degrees == degrees.max())[0])
# "Remove" the vertex v and the edges to its neigbours
adj[v, :], adj[:, v] = 0, 0
# Update the maximal independent set
indep_set.difference_update({v})
return indep_set
Или даже лучше, мы можем получить максимальный независимый набор:
def maximal_independent_set(adj):
adj = np.array(adj, dtype=bool).astype(np.uint8)
degrees = adj.sum(0)
V = set(range(len(adj))) # vertices of the graph
mis = set() # maximal independent set
while V:
# Randomly pick a vertex of min degree
v = random.choice(np.where(degrees == degrees.min())[0])
# Add it to the mis and remove it and its neighbours from V
mis.add(v)
Nv_c = set(np.nonzero(adj[v])[0]).union({v}) # closed neighbourhood of v
V.difference_update(Nv_c)
degrees[list(Nv_c)] = len(adj) + 1
return mis