ГЛАВА 5. КЛАСТЕРИЗАЦИЯ НА ОСНОВЕ ОЦЕНИВАНИЯ ФУНКЦИИ ПЛОТНОСТИ

5.1. Модальный анализ

Один, из методов кластеризации, рассмотренных - в главе 1, — метод по минимальному локальному расстоянию — приводит к удлинению кластеров. Этот метод не принадлежит к классу методов с минимальной дисперсией, которые рассматривались в параграфе 1.6.

Применение для кластеризации метода минимального локального расстояния благодаря цепной тенденции может привести к ряду «плотных» кластеров, которые перемежаются, соединяются «редкими, неплотными» кластерами. В случае одной характеристики гистограмма будет иметь вид мультимодального распределения. Желательно пользоваться методами, которые бы определяли моды этого распределения и соответствующие им отдельные кластеры.

Для массивов среднего объема Уишарт [396] предложил метод кластеризации, который он назвал модальным анализом. Этот метод им же был обобщен на случай большого числа наблюдений. Его процедура начинается с выяснения вопроса о мультимодальности данных. В случае одной характеристики необходимо построить гистограмму и вычеркнуть данные с малой частотой (седловые области). Тогда соответствующий кластер можно установить для каждой модальной области. Данные, принадлежащие седловой области, относятся к ближайшей моде. В случае -характеристик этот метод становится неудобным. Если каждая остз измерения разбита на k классов, то мы получим -мерных прямоугольников. Для определения, в какой из классов необходимо отнести то или иное наблюдение.

требуется ответить на ряд вопросов, одним из которых является выбор оси измерения. Эту проблему можно обойти, если пользоваться сферическими областями. Одноуровневый алгоритм Уишарта может быть записан следующим образом:

а) выбираем значения порогового расстояния и пороговой частоты

б) вычисляем матрицу сходства ;

в) для каждой точки находим частоту попадания точек лежащих на расстоянии меньшем ;

г) точку с частотой меньшей чем удаляем;

д) кластеризуем оставшиеся точки концентрации по методу минимального локального расстояния;

е) распределяем точки, исключенные на шаге по кластерам, полученным в (д), соответственно некоторому критерию. (Например, каждую точку, не являющуюся точкой концентрации, приписываем к кластеру, для которого расстояние между данной точкой и соответствующей точкой концентрации минимально.)

Далее, Уишарт предложил ступенчатый алгоритм, который выполнял только задачу модального анализа. Для этого необходимо было задать лишь пороговое значение для частоты На первом и последнем цикле алгоритма определяется один кластер. На некотором промежуточном цикле получается максимальное число кластеров. Для унимодальных данных анализ приводит к одному кластеру. За полным описанием этого ступенчатого алгоритма отсылаем читателя к работе [396].

Заде [407] ввел понятие «размытого» множества, его процедура имеет много общего с модальным анализом Уишарта. По Заде, если Е — пространство точек, размытое множество А в Е характеризуется функцией семейства (характеристической функцией) которая каждой точке в Е ставит в соответствие число в интервале [0, 1], причем величина представляет собой степень «принадлежности» к множеству А. Смысл аналогичен пороговому значению f Уишарта.

Гитман и Левин [129] предлагают алгоритм, который разбивает выборку из мультимодального размытого множества на унимодальные размытые множества; а затем применяется алгоритм кластеризации многомерных наблюдений, в результате которого получаются однородные группы. Эта процедура также аналогична модальному анализу Уишарта.

Результат кластеризации, основанный на модальном анализе, сильно зависит от оценивания положения моды, поэтому различные методы оценивания мультимодальных многомерных функций плотностей приведут и к новым методам кластеризации. Этой проблеме мы и посвятим оставшуюся часть этой главы.