Пусть даномножество N изображений объектов и определена произвольная неотрицательная пороговая величина ; Необходимо получить представление о количестве кластеров.
Алгоритм:
1) Пусть . (центр первого кластера совпадает с любым из заданных образов)
2) Вычисляем расстояние между образом и центром кластера по формуле
.
3) Если это расстояние больше значения пороговой величины , то учреждается новый центр кластера , в противном случае изображение объекта включается в кластер, центром которого является .
Пусть условие выполнено, т.е. – центр нового кластера.
4) Вычисляем расстояния и от до центров кластеров и
5) Если оба расстояния оказываются больше порога , то учреждается новый центр кластера , в противном случае изображение объекта зачисляется в тот кластер, чей центр к нему ближе.
Подобным же образом расстояния от каждого нового изображения объекта до каждого до каждого известного центра кластера вычисляются и сравниваются с пороговой величиной – если все эти расстояния превосходят значение порога , учреждается новый центр кластера. В противном случае образ зачисляется в кластер с самым близким к нему центром.
|
|
Результаты описанной процедуры определяются выбором первого центра кластера, порядком осмотра образов, значением пороговой величины и, конечно, геометрическими характеристиками данных.
Хотя это алгоритм обладает рядом очевидных недостатков, он позволяет просто и быстро получить приблизительные оценки основных характеристик заданного набора данных. Кроме того, этот алгоритм привлекателен с вычислительной точки зрения, так как для выявления центров кластеров, соответствующих определенному значению порога ,ему требуется только однократный просмотр выборки. Практически же, для того чтобы хорошо понять геометрию распределения образов с помощью такой процедуры, приходится проводить многочисленные эксперименты с различными значениями порога и различными исходными точками кластеризации. Поскольку изучаемые образы обычно имеют высокую размерность, визуальная интерпретация результатов исключается; поэтому необходимая информация добывается в основном при помощи сопоставления после каждого цикла просмотра данных расстояний, разделяющих центры кластеров, и количества образов, вошедших в различные кластеры. Полезными характеристиками являются также ближайшая и наиболее удаленная от центра точки кластера и различие размеров отдельных кластеров. Информацию, полученную таким образом после каждого цикла обработки данных, можно использовать для коррекции выбора нового значения порога и новой исходной точки классификации в следующем цикле. Можно рассчитывать на получение с помощью подобной процедуры полезных результатов в тех случаях, когда в данных имеются характерные «гнезда», которые достаточно хорошо разделяются при соответствующем выборе значения порога.
|
|