38
правок
Изменения
→Метод нормализованных срезов (англ. Normalized cuts)
где <tex>assoc(A,A)=\sum_{i \in A, j \in A}w_{ij}</tex> это ''ассоциациея'' (сумма всех весов) в кластере и <tex>assoc(A,V)=assoc(A,A)+cut(A,B)</tex> это сумма всех весов ассоциированных с <tex>А</tex>.
<br>Нормализованные разрезы могут быть довольно медленными, поскольку это требует решения больших разреженных задач. Однако существует способ ускорить вычисление нормализованных разрезов, используя подход, основанный на алгебраической сетке. Можно выбирать меньшее количество переменных, чтобы оставшиеся переменные более нижнего уровня были ''сильно связаны'' по крайней мере с одной переменной грубого уровня. Подмножество <tex>C \subset V</tex> считается ''сильно связаным'', если выполняется
<br><center><tex>\frac{\sum_{j \in C}w_{ij}}{\sum_{j \in V}w_{ij}} > \phi,</tex>[*] </center> [*]
обычно <tex>\phi = 0.2.</tex> Данный рисунок схематично показывает этот процесс.
