Сравните подобие между графиками?

Question

У меня есть несколько Concept Maps, которые представлены в качестве ориентированных графиков. Я использовал this method, чтобы сравнить 2 концептуальные карты, но теперь я хотел бы классифицировать/группировать подобные графики вместе.

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

В этом случае, как мне подойти к этой проблеме?

Answer 1

Многие алгоритмы кластеризации (большинство, за исключением, например, k-mean, EM и Mean-shift) используют дистанции, а не точки.

Для небольших наборов данных иерархическая кластеризация, безусловно, является первым методом, который можно попробовать. Одноканальная, полная ссылка, средняя ссылка имеют небольшие формальные требования, то есть они могут использоваться либо с расстоянием, либо с подобием, что не должно удовлетворять неравенству треугольника. Другие показатели, такие как Ward и centroid linkage, требуют квадратичных евклидовых расстояний и, вероятно, не будут работать здесь.

1. Compute попарного график согласование расстояния
2. проверки для любой нормализации (например, размером графика) требуется
3. запустить иерархическую кластеризацию
4. исследования дендрограммы, вам, возможно, придется вернуться и улучшить нормализацию, расстояние, и т. д.
5. вырезанные поддеревны кластеры из дендрограммы