Алгоритм Хошены-Копельман является простым и эффективным алгоритмом для маркировки кластеров на сетку, в которой сетка является регулярной сетью ячеек, причем клетка либо оказывался занята или незанятость. Этот алгоритм основан на хорошо известном алгоритме поиска объединений . [1] Алгоритм был первоначально описан Джозефом Хошеном и Раулем Копельманом в их статье 1976 года «Перколяция и кластерное распределение. I. Метод множественной маркировки кластеров и алгоритм критической концентрации». [2]
Теория перколяции
Теория перколяции является изучение поведения и статистики из кластеров на решетках . Предположим, у нас есть большая квадратная решетка, в которой каждая ячейка может быть занята с вероятностью p
и может быть пустой с вероятностью . Каждая группа соседних занятых ячеек образует кластер. Соседи определяются как ячейки, имеющие общую сторону, но не те, которые имеют общий угол, т.е. мы рассматриваем 4-связное соседство : верхнее, нижнее, левое и правое. Каждая занятая ячейка не зависит от статуса своего соседства. Количество кластеров, размер каждого кластера и их распределение - важные темы теории перколяции.1 – p
|
| Рассмотрим 5x5 сетки на рисунках (а) и (б). На рисунке (а) вероятность занятости составляет p = 6/25 = 0.24 . На рисунке (b) вероятность занятости составляет p = 16/25 = 0.64 . |
Алгоритм Хошена – Копельмана для поиска кластеров
В этом алгоритме мы просматриваем сетку в поисках занятых ячеек и помечаем их метками кластера. Процесс сканирования называется растровым сканированием . Алгоритм начинается со сканирования ячейки сетки за ячейкой и проверки, занята ячейка или нет. Если ячейка занята, то она должна быть помечена меткой кластера. Эта метка кластера определяется на основе соседей этой ячейки. (Для этого мы собираемся использовать алгоритм поиска объединения, который объясняется в следующем разделе.) Если ячейка не имеет занятых соседей, то ячейке назначается новая метка. [3]
Алгоритм поиска объединения
Этот алгоритм представляет собой простой метод вычисления классов эквивалентности . Вызов функции union(x,y)
указывает, что элементы x
и y
являются членами одного класса эквивалентности. Потому что отношения эквивалентности транзитивны ; все элементы, эквивалентные x
, эквивалентны всем элементам, эквивалентным y
. Таким образом, для любого предмета x
существует набор предметов, которые все эквивалентны x
. Этот набор является классом эквивалентности, членом которого x
является. Вторая функция find(x)
возвращает представительного члена класса эквивалентности, к которому x
принадлежит.
Псевдокод
Во время растрового сканирования сетки всякий раз, когда встречается занятая ячейка, соседние ячейки сканируются, чтобы проверить, не была ли какая-либо из них уже просканирована. Если мы находим уже просканированных соседей, выполняется union
операция, чтобы указать, что эти соседние ячейки на самом деле являются членами одного и того же класса эквивалентности. Затем выполняется find
операция по поиску представительного члена того класса эквивалентности, которым будет помечена текущая ячейка.
С другой стороны, если текущая ячейка не имеет соседей, ей назначается новая, ранее не использовавшаяся метка. Таким образом обрабатывается вся сетка.
После псевдокод называется от Tobin Фрике реализации одного и того же алгоритма. [3]
Растровое сканирование и нанесение надписей на сеткуКрупнейшая_ метка = 0;для x от 0 до n_columns { для y от 0 до n_rows { если занято [x, y], то слева = занято [x-1, y]; # Разве это не должно быть ярлыком [x-1, y] вверху = занято [x, y-1]; # То же самое? if (left == 0) и (вверху == 0) then / * Ни метка сверху, ни слева. * / самая большая_метка = наибольшая_метка + 1; / * Создаем новую, еще не используемую метку кластера. * / метка [x, y] = большая_метка; else if (left! = 0) и (выше == 0) then / * Один сосед слева. * / метка [x, y] = найти (слева); else if (left == 0) и (выше! = 0) then / * Один сосед, выше. * / метка [x, y] = найти (вверху); else / * Соседи ОБЕИ слева и сверху. * / союз (слева, вверху); / * Связываем левый и верхний кластеры. * / метка [x, y] = найти (слева); }}Союзvoid union (int x, int y) { метки [find (x)] = find (y);}Находитьint find (int x) { int y = x; в то время как (метки [y]! = y) y = метки [y]; while (label [x]! = x) { int z = метки [x]; метки [x] = y; х = z; } вернуть y;}
Пример
Рассмотрим следующий пример. Темные ячейки в сетке figure (a)
означают, что они заняты, а белые пустые. Таким образом, запустив алгоритм H – K для этого входа, мы получим результат, как показано на рисунке, figure (b)
со всеми помеченными кластерами.
Алгоритм обрабатывает входную сетку, ячейка за ячейкой, следующим образом: Предположим, что сетка - это двумерный массив.
- Начиная с ячейки,
grid[0][0]
т.е. с первой ячейки. Ячейка занята, и у нее нет ячеек слева или выше, поэтому мы пометим эту ячейку новой меткой, скажем1
. grid[0][1]
иgrid[0][2]
оба они не заняты, поэтому они не помечены.grid[0][3]
занято, поэтому проверьте ячейку слева, которая не занята, поэтому мы увеличиваем текущее значение метки и назначаем метку ячейке как2
.grid[0][4]
,grid[0][5]
и неgrid[1][0]
заняты, поэтому они не помечены.grid[1][1]
занято, поэтому проверьте ячейку слева и выше, обе ячейки не заняты, поэтому назначьте новую метку3
.grid[1][2]
занято, поэтому проверьте ячейку слева и выше, занята только ячейка слева, поэтому присвойте этой ячейке метку ячейки слева3
.grid[1][3]
занимает так контрольной ячейки слева и выше, как клетки заняты, поэтому объединить два кластера и присвоить метку кластера ячейки выше клетки слева и в этой камере есть2
. (Объединение с использованием алгоритма накидной будет маркировать все клетки с этикеткой3
к2
)grid[1][4]
занято, поэтому проверьте ячейку слева и выше, занята только ячейка слева, поэтому присвойте этой ячейке метку ячейки слева2
.grid[1][5]
,grid[2][0]
и неgrid[2][1]
заняты, поэтому они не помечены.grid[2][2]
занято, поэтому проверьте ячейку слева и выше, занята только ячейка выше, поэтому присвойте этой ячейке метку ячейки выше2
.grid[2][3]
,grid[2][4]
и неgrid[2][5]
заняты, поэтому они не помечены.grid[3][0]
занято, поэтому проверьте ячейку выше, которая не занята, поэтому мы увеличиваем текущее значение метки и назначаем метку ячейке как4
.grid[3][1]
занято, поэтому проверьте ячейку слева и выше, занята только ячейка слева, поэтому присвойте этой ячейке метку ячейки слева4
.grid[3][2]
не занято, поэтому на нем нет надписи.grid[3][3]
занято, поэтому проверьте ячейку слева и выше, обе ячейки не заняты, поэтому назначьте новую метку5
.grid[3][4]
занято, поэтому проверьте ячейку слева и выше, занята только ячейка слева, поэтому присвойте этой ячейке метку ячейки слева5
.grid[3][5]
,grid[4][0]
и неgrid[4][1]
заняты, поэтому они не помечены.grid[4][2]
занято, поэтому проверьте ячейку слева и выше, обе ячейки не заняты, поэтому назначьте новую метку6
.grid[4][3]
занято, поэтому проверьте ячейку слева и выше, обе ячейки слева и выше заняты, поэтому объедините два кластера и назначьте метку кластера ячейки выше ячейке слева и этой ячейке, т5
. е . (Объединение с использованием алгоритма накидной будет маркировать все клетки с этикеткой6
к5
).grid[4][4]
не занято, поэтому на нем нет надписи.grid[4][5]
занято, поэтому проверьте ячейку слева и выше, обе ячейки не заняты, поэтому назначьте новую метку7
.grid[5][0]
,grid[5][1]
,grid[5][2]
Иgrid[5][3]
незаняты поэтому они не помечены.grid[5][4]
занято, поэтому проверьте ячейку слева и выше, обе ячейки не заняты, поэтому назначьте новую метку8
.grid[5][5]
занято, поэтому проверьте ячейку слева и выше, обе ячейки слева и выше заняты, поэтому объедините два кластера и назначьте метку кластера ячейки выше ячейке слева и этой ячейке, т7
. е . (Объединение с использованием алгоритма накидной будет маркировать все клетки с этикеткой8
к7
).
|
| Рассмотрим 6x6 сетки на рисунках (а) и (б). Рисунок (а). Это входные данные для алгоритма Хошена – Копельмана. Рисунок (b), это результат работы алгоритма со всеми помеченными кластерами. |
Приложения
- Определение площади узловых доменов и длин узловых линий [4]
- Информация о узловых соединениях
- Моделирование электропроводности
Смотрите также
- Алгоритм кластеризации K-средних
- Алгоритм нечеткой кластеризации
- Алгоритм кластеризации по Гауссу ( максимизация ожидания )
- Методы кластеризации [5]
- Алгоритм кластеризации C-средних [6]
- Маркировка подключенных компонентов
Рекомендации
- ^ https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf
- ^ Хошен, Дж .; Копельман, Р. (15 октября 1976 г.). «Перколяция и распределение кластеров. I. Методика множественной маркировки кластеров и алгоритм критической концентрации» . Phys. Rev. B . 14 (8): 3438–3445. doi : 10.1103 / PhysRevB.14.3438 - через APS.
- ^ а б Фрике, Тобин (21 апреля 2004 г.). «Алгоритм Хошена-Копельмана для идентификации кластеров» . ocf.berkeley.edu . Проверено 17 сентября 2016 .
- ^ Кристиан Иоас. «Введение в алгоритм Хошена-Копельмана и его применение в статистике узловых областей» (PDF) . Webhome.weizmann.ac.il . Проверено 17 сентября 2016 .
- ^ «Кластеризация» (PDF) .
- ^ «Нечеткая кластеризация c-средних» .