Кластеризация некоторой матрицы формы графика

Question

В нескольких вопросах по stackoverflow упоминается похожая проблема, но ...

У меня есть квадратная матрица, например, вот так:

  |  A  |  B  |  C  |  D 
A |  1  |  1  |  0  |  0 
B |  1  |  1  |  1  |  0 
C |  0  |  1  |  1  |  0 
D |  0  |  0  |  0  |  1 

Квадратная матрица может быть любого размера (может быть 1000x1000 или больше). Я хочу получить кластеры (я не знаю, сколько ...). Для приведенного выше примера я должен получить два кластера:

1. A, B, C (потому что A-B и B-C) ​​
2. D

Answer 1

1. В качестве примера вы привели классическое обнаружение клики , хорошо изученное в теории графов с несколькими алгоритмами.Это становится интереснее, когда вы пропускаете некоторые ребра.Это приведет к модульности и т. Д.
2. То, что у вас есть, представляет собой невзвешенную матрицу смежности.Есть алгоритмы кластеризации, которые работают над этим - для распространения сродства требуется сродство, и иерархическая агломерационная кластеризация может быть реализована с подобиями (будьте осторожны, большинство реализаций используют расстояния)
3. В вашем случае вы можетеТривиально использовать 1-X в качестве матрицы расстояний для многих алгоритмов кластеризации, кроме k-средних, GMM и некоторых других исключений, для которых требуется матрица координат.