Python реализация алгоритма градации сходства

Ответ 1

То, что мы закончили, - это реализовать алгоритм, описанный в: Эвристика для соответствия химическим соединениям.

Мы используем NetworkX для представления графа и для поиска максимальной клики.

Edit:

В принципе, вы создаете новый график, каждый node (v), представляющий возможное спаривание node из графика A (a) в node из графика B (b).

Если в вашем приложении два узла (a, b) либо схожи, либо не, вы удаляете узлы (v) из нового графика, которые соответствуют несходным спариваниям (a, b). Вы соединяете два узла с ребром, если они не противоречат друг другу. Например, пары (a, b) и (a, c) противоречат друг другу (см. Статью для формального определения). Затем вы найдете клику в новом графике с максимальным количеством узлов.

Если в приложении сходство двух узлов не является двоичным, вы даете новые веса узлов в пределах диапазона (скажем (0,1)). Вы можете удалить, эвристически, удалить новые узлы со степенями подобия ниже предопределенного порога. Затем вы найдете клику в новом графике с максимальным весом (сумма назначенных весов узлов).

В любом случае, вы закончите, создав класс сходства: размер/общий вес клики, деленный на функцию атрибутов исходных графиков (максимальный/минимальный/средний размер/вес A и B).

Хорошей особенностью является то, что вы можете вывести "источник" сходства из найденной вами клики - "более сильные" пары.

Дальнейшие разъяснения: Ограничения зависят от приложения. Мы использовали подход для сравнения пар графиков потока управления функциями. Как правило, подход находит совпадение некоторых узлов в первом графе с некоторыми узлами во втором графе (подграф подграфом). Каждый node в графике ассоциации символизирует возможное совпадение одного node от первого графика до одного node во втором графике. Поскольку в итоге клика (подмножество узлов) выбрана, край означает, что два совпадения не противоречат друг другу. Чтобы подать заявку на другое приложение, вы должны спросить, каковы критерии возможных пар (или какие узлы я создаю), и как выбор одного спаривания влияет на выбор другого спаривания (или как я соединяю узлы с ребрами).

Ответ 2

Другой метод - использовать то, что называется сходством с собственным вектором. В принципе, вы вычисляете собственные значения Лапласа для матриц смежности каждого из графов. Для каждого графика найдем наименьшее k такое, что сумма k наибольших собственных значений составляет не менее 90% от суммы всех собственных значений. Если значения k отличаются между двумя графиками, используйте меньший. Метрика подобия представляет собой сумму квадратов различий между наибольшими k собственных значений между графиками. Это даст метрику подобия в диапазоне [0, ∞), где значения, близкие к нулю, более схожи.

Например, если используется networkx:

def select_k(spectrum, minimum_energy = 0.9):
    running_total = 0.0
    total = sum(spectrum)
    if total == 0.0:
        return len(spectrum)
    for i in range(len(spectrum)):
        running_total += spectrum[i]
        if running_total / total >= minimum_energy:
            return i + 1
    return len(spectrum)

laplacian1 = nx.spectrum.laplacian_spectrum(graph1)
laplacian2 = nx.spectrum.laplacian_spectrum(graph2)

k1 = select_k(laplacian1)
k2 = select_k(laplacian2)
k = min(k1, k2)

similarity = sum((laplacian1[:k] - laplacian2[:k])**2)

Ответ 3

Я думаю, что способ определения подобия не очень стандартный, поэтому, вероятно, легче найти реализации для проверки изоморфизма, расстояния редактирования графа и максимального общего подграфа, а затем объединить их сами.

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

igraph может проверить, например, изоморфизм.

РЕДАКТИРОВАТЬ: на самом деле вам, вероятно, нужно только расстояние редактирования, так как наличие MCS обычно не имеет значения, как я уже указывал выше, и два графика будут изоморфными в любом случае, если расстояние редактирования равно 0.

Ответ 4

Это старый вопрос, но я хотел бы поделиться своим подходом. У меня была задача CVRP (проблема маршрутизации емкостного транспортного средства). Мой эвристический алгоритм создал несколько разных графиков, чтобы найти решение. Чтобы не застрять на местном оптимуме, я использовал процедуру расслабления и ремонта.

На этом этапе мне пришлось отфильтровать решения, которые были слишком похожи. Поскольку большинство эвристических подходов используют систематическое изменение окрестностей в рамках процедуры локального поиска, чтобы найти решения, расстояние Edit (Levenshtein distance) было для меня идеальным. Алгоритм Levenshtein имеет сложность O(n*m) где n и m - длина двух строк. Таким образом, с помощью строкового представления узлов и маршрутов графа я смог выяснить сходство. edit operations могут рассматриваться как neighborhood operations поэтому они могут рассматриваться как расстояние в пространстве поиска (а не расстояние в пространстве решений).

Лучшим/обобщенным подходом, который жертвует некоторой скоростью, был бы Needleman-Wunsch. Needleman-Wunsch - это гибридная мера подобия, которая обобщает расстояние Левенштейна и учитывает глобальное выравнивание между двумя строками. В частности, он вычисляется путем присвоения оценки каждому выравниванию между двумя входными строками и выбора показателя наилучшего выравнивания, то есть максимального значения. Выравнивание между двумя строками - это набор соответствий между их символами, допускающий пробелы.

Например:

import py_stringmatching as sm
nw = sm.NeedlemanWunsch(gap_cost=0.5, sim_func=lambda s1, s2: (0.0 if s1 == s2 else 1.0))
print('\nNeedleman-Wunsch: ', nw.get_raw_score('045601230', '062401530'))

В этом примере вы можете использовать собственный алгоритм Левенштейна.

Быстрые реализации Левенштейна существуют в Git (с использованием Cython, Numpy и т.д.).
Хорошей библиотекой является py_stringmatching, которая содержит следующий список алгоритмов подобия:

• Affine Gap
• Сумка Расстояние
• Косинус
• Игральная кость
• Editex
• Обобщенная жаккарда
• Расстояние Хэмминга
• Jaccard
• Яро
• Яро Винклер
• Левенштейн
• Монж Элкан
• Рукодельница Вунш
• Коэффициент перекрытия
• Частичное соотношение
• Частичная сортировка токенов
• соотношение
• Smith-Waterman
• Мягкий TF/IDF
• Саундэкс
• TF/IDF
• Сортировка токенов
• Тверский указатель