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