Заметим, что число N наблюдаемых объектов здесь принципиально не ограничено N®Ґ. Поэтому решением задачи должен быть способ отнесения к некоторому классу каждого вновь появившегося объекта независимо от остальных. Такой способ реализуется в виде так называемого решающего правила.

Нам здесь будет удобно, никак не противореча общепринятому пониманию терминов “классификация” и “кластеризация”, различать их в том смысле, что классификация строится, когда число объектов принципиально не ограничено, а кластеризация строится, когда число объектов заранее известно, и все они анализируются совместно.

Решающее правило представляет собой некоторую функцию g(w), принимающую значения на множестве классов {W₁,…W_m}, где g(w_i) = W_k при w_iОW_k. Пусть результат наблюдения объекта w_i представлен n-мерным вектором x_i= (x_i1,…x_in). Тогда решающая функция g(w) может быть доступна нам в виде функции g(x), причем мы хотим, чтобы выполнялось условие g(x_i) = W_k при x_iОW_k.

Наиболее общим подходом к решению задачи классификации является построение вероятностного решающего правила. Предполагается, что в n-мерном пространстве задана m-модальная плотность распределения вероятностей, где локальные максимумы плотности распределения характеризуют локальные сгущения объектов в пространстве. В данном случае, вообще говоря, области W₁,…W_m локальных сгущений объектов пересекаются, накрывая в итоге все пространство, и не являются в этом смысле классами. Собственно классификация порождается решающим правилом g(x) в виде непересекающихся областей O_kНW_k, k=1,…m, также накрывающими в общем случае все признаковое пространство, где g(x_i) = O_k при x_iОO_k.

Построение вероятностного решающего правила часто затруднено, т.к. требует, в итоге, полного знания всех соответствующих распределений вероятностей. Если предположить, что вероятностные меры сосредоточены в ограниченных областях признакового пространства, то допустимо построение детерминистского решающего правила. В этом случае предполагается, что области W₁,…W_m не пересекаются O_k= W_k, k=1,…m, образуя разбиение n-мерного пространства на m классов. Для построения детерминистского решающего правила требуется лишь знание характеристик, описывающих взаимное расположение областей W₁,…W_m в признаковом пространстве.

Прикладные методы построения решающих правил развиваются, например, в теории распознавания образов.

Результаты совокупности наблюдений обычно представлены матрицей данных X(N, n), состоящей из N строк и n столбцов. Фиксированное число наблюдений N позволяет построить классификацию данной совокупности из N объектов не на основе решающего правила, а сразу, непосредственно перечисляя номера классов объектов.

Методы построения классификации сразу перечислением решают задачу кластер-анализа. Особенность задачи кластер-анализа состоит в том, что ее решение получается при анализе одновременно всей совокупности N наблюдаемых объектов. Следовательно, методы кластер-анализа основаны на изучении характеристик взаимного расположения классов как локальных сгущений точек в признаковом пространстве.

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

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

Алгоритмы кластер-анализа обычно довольно просты, что весьма привлекательно на практике, но результат их работы может и не иметь достаточного статистического обоснования.

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

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

В целом, весьма полезным может оказаться подход, когда варианты алгоритмов кластеризации конструируются на основе некоторого набора исходных алгоритмов. Ниже мы покажем примеры построения таких алгоритмов.

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

Хорошо известны два существенно разных способа перебора: иерархические дивизимные и агломеративные алгоритмы и неиерархические алгоритмы типа ISODATA на основе семейства алгоритмов K-средних (Болл Ж., Холл Д., Мак-Куин Дж.) или алгоритмов семейства FOREL (Загоруйко Н.Г., Лбов Г.С., Елкина В.Н.).

В иерархических алгоритмах фактически отказываются от определения числа кластеров, строя полное дерево вложенных кластеров (дендрограмму). Число кластеров определяется из предположений, вообще говоря, не относящихся к работе алгоритмов, например, по динамике изменения порога расщепления (слияния) кластеров. Трудности таких алгоритмов хорошо изучены: выбор мер близости кластеров, проблема инверсий индексации в дендрограммах, негибкость иерархических классификаций, которая иногда весьма нежелательна. Тем не менее, представление кластеризации в виде дендрограммы позволяет получить наиболее полное представление о структуре кластеров.

В неиерархических алгоритмах характер их работы и условие остановки необходимо заранее регламентировать часто довольно большим числом параметров, что иногда затруднительно, особенно на начальном этапе изучения материала. Но в таких алгоритмах достигается большая гибкость в варьировании кластеризации, и обычно определяется число кластеров.

С другой стороны, когда объекты характеризуется большим числом признаков (параметров), то приобретает важное значение задача группировки признаков. Исходная информация содержится в квадратной матрице связей признаков, в частности, в корреляционной матрице. Основой успешного решения задачи группировки является неформальная гипотеза о небольшом числе скрытых факторов, которые определяют структуру взаимных связей между признаками.

Задача группировки имеет как самостоятельное значение (задача агрегирования, задача диагонализации матрицы связей) с целью выделения групп признаков, характеризующих изучаемые объекты с какой-то одной стороны, и может пониматься как специфическая задача кластер-анализа, так и вспомогательное – например, с целью выдвижения предварительной гипотезы о числе общих факторов в факторном анализе.

Проблема выбора числа групп также весьма нетривиальна. Поэтому часто алгоритмы группировки признаков строятся из предположения, что число групп K заранее задано (экстремальная группировка – Браверман Э.М., Лумельский В.Я.), или также строятся как агломеративные или дивизимные процедуры перебора последовательных группировок при различных K.

Опыт применения иерархических алгоритмов (метод корреляционных плеяд – Выханду Л.К., Терентьев В.П., алгоритм “Объединение” – Дорофеюк А.А., Лумельский В.Я.) показывает, что для достаточно сложных корреляционных матриц не всегда удается получить разбиение, удовлетворяющее содержательным требованиям исследования. И это закономерно, так как свойство иерархичности группировок, как правило, существенно ограничивает их разнообразие. В свою очередь, алгоритмы экстремальной группировки признаков свободны от этого ограничения, но являются локально-оптимальными. Поэтому в сложных случаях их результат существенно зависит от числа групп и начальной группировки.

Здесь предлагается неиерархический дивизимный алгоритм кластеризации, не требующий параметров настройки, на основе классического алгоритма K-средних. Результатом работы такого алгоритма является последовательность кластеризаций, которые в общем случае не образуют иерархии. Предлагается заранее не определять число кластеров, т.к. свойства построенной последовательности позволяют указать те кластеризации, которые заведомо не будут оптимальными. Тогда оставшиеся кластеризации определят те допустимые значения числа кластеров, из которых при необходимости можно сделать окончательный выбор.

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

	часть 1 (RUS/ENG)  часть 2 (RUS/ENG)  часть 3 (RUS/ENG)  Пример