Парадигма развития науки. Идеологическое обеспечение (стр. 43 )

Задачу кластеризации можно разными способами видоизменять. Например, можно, как в задаче многоклассовой классификации, строить кластеризатор для каждой точки х пространства признаков вычисляющий не только решение arg maxj fj(x) (помер кластера), но и уверенность в нем, равную maxj fj(x). Такой кластеризатор заодно может решать задачу обнаружения выбросов.

Обучать такой кластеризатор можно следующим образом: потребовать, что­бы его решения удовлетворяли обычным вероятностным нормировкам ии решать для обучающего набора X максимизационную задачу

(1)

Для решения этой задачи возьмем какой-нибудь метод обучения классифика­торов, максимизирующий суммарную оценку уверенностей распознавателя в ответе на обучающем наборе, и какую-нибудь, хоть бы и случайную, класте­ризацию. Обучим классификатор классифицировать в соответствии с этим на­значением кластеров. Затем каждый вектор признаков из обучающего набора классифицируем с помощью обученного классификатора. Хотя классификатор и обучался на этом же самом обучающем наборе, для некоторых обучающих векторов его ответ может отличаться от того, чему его учили. Для полученно­го разбиения на классы снова обучим классификатор, затем в соответствии с результатами обучения снова подправим классификацию и т. д. При обучении сумма уверенностей (1) монотонно не убывает. Обучение останавливается, ко­гда эта сумма перестает возрастать. При таком обучении классификатор учится классифицировать не так, как задано в каком-то обучающем наборе, а так, как ему удобно максимизировать уверенность в своей работе. Результат обучения кластеризатора сильно зависит от начального разбиения на кластеры.

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

В качестве примера рассмотрим байесовский q-классовый классификатор на d-мерном евклидовом пространстве признаков для следу­ющей порождающей модели: вероятности р(у) всех классов равны 1/q, а плотно­сти условных вероятностей р(х|у) являются гауссовыми с единичной матрицей ковариации

Обучение модели состоит в подборе q векторов μ1,...,μq в пространстве При обучении методом наибольшего правдоподобия на обучаю­щем наборе с каким-то распределением у1,…,,уN обучающих векторов по кластерам, максимизируется произведение вероятностей

т. е. минимизируется сумма

что эквивалентно минимизации суммы квадратов

Квадратичная минимизация сводится к очень простой системе линейных урав­нений, которая элементарно решается. Ответ получается та­кой:

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

Этот пример обучения кластеризатора по совместительству является самым распространенным примером описываемого в п. 3.9.2 векторного кванто­вания. Он обычно называется "k-means" (k средних), где k — обозначение числа кластеров (то, что выше обозначалось буквой q), a "means" — память о вычис­лении средних арифметических. Как правило, метод k-means сходится быстро. Напоминаем, что получающаяся кластеризация зависит от начальной кластеризации и не обязательно оптимальна.

Метод k-means легко обобщить, допустив в качестве плотностей условных вероятности гауссианы с любыми матрицами ковариации, в том числе и с разными матрицами для разных кластеров.

Количество кластеров k может быть фиксировано заранее, а может, аналогично обучению распознавателей с pегуляризадней, подбираться минимиза­цией суммы какою-либо зависящею от k штрафа "за сложность" и убывающей функции от уверенности (1). Стандарных рецептов, как именно штрафовать и как минимизировать по дискретному параметру k, нет.

3.9.2. Векторное квантование и понижение размерности

Широко распространена следующая модификация задачи кластеризации. Одно­временно с поиском хорошей кластеризующей функции f: → бyдем искать "функцию центров" с: сопоставляющую каждому кластер y его типичного представителя с(у) называемого центром кластера. Желательно, чтобы центр кластера был достаточно близок ко всем объекам познания и созидания этого кластера.

В такой постановке задача кластеризации обычно называется векторным квантованием (vecloi quantization). Векторное квантование чаще всего при­меняется при необратимом сжатии информации для хранения или передачи по линиям связи. Информация любой природы представляется, возможно ис­кусственно, в виде последовательности векторов признаков лежащих в про­странстве признаков . При кодировании (сжатии) каждый вектор кодируется номером кластера, которому он принадлежит. При декодировании (раздутии) каждый номер кластера заменяется на его центр

Задачу векторного квантования можно формализовав в том же стиле, что и задачу распознавания. Имеется:

пространство (векторов) признаков , точками которого кодируются кван­туемые объекты и созидания, например d-мерное евклидово пространство Rd или лю­бое метрическое пространство;

пространство кластеров обычно конечное, хотя возможны и обобще­ния;

пространствокластеризующих функций f: , например, любых функций из в ;

пространство С функций центров с: , как правило, пространство всех функций из в ;

пространство распределений (вероятностных мер) на , например, в случае евклидова пространства , — абсолютно непрерывных по мере Лебега, гауссовых смесей и т. п. ;

функция штрафа Е как правило неотрицательная и равная 0 при совпадении параметров, например, в случае евклидова пространства удобно взять

набор обучающих данных Х= (х1,…., хN), где считаются значениями независимых случайных величин с одним и тем же, но совершенно неизвестным распределением .

Необходимо по построить кластеризатор и функцию центровминимизирующие ожидание штрафа