38
правок
Изменения
→Метод нормализованных срезов
<br><center><tex>Ncut(A,B)=\frac{cut(A,B)}{assoc(A, V)}+\frac{cut(A,B)}{assoc(B,V)},</tex></center>
где <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> Данный рисунок схематично показывает этот процесс. [[Файл:grephEdges.png]], где ''на первом изображении'' - исходная пиксельная сетка черно-белого изображения; ''на втором'' - межпиксельные связи, где более толстые линии указывают на более сильные связи; ''на третьем'' - сетка после одного уровня огрубления, когда каждый исходный пиксель сильно связан с одним из узлов грубого уровня; ''на четвертом'' - после двух уровней огрубления. Как только набор грубых переменных был выбран, межуровневая интерполяционная матрица с элементами, подобными <tex>\frac{\sum_{j \in C}w_{ij}}{\sum_{j \in V}w_{ij}}</tex>, используется для определения сокращенной версии задачи ''нормализованных разрезов''. В дополнение к вычислению матрицы весов с использованием интерполяции используются дополнительные статистические данные области для модуляции весов. После того, как ''нормализованный разрез'' был вычислен на самом грубом уровне, значения узлов более нижнего уровня вычисляются путем интерполяции родительских значений и сопоставления значений <tex> \epsilon = 0,1</tex> в пределах от 0 и 1 до Boolean значений. Результат работы данного алгоритма:[[Файл:bear1.png]] [[Файл:bear2.png]]
