4.5.2. Метод k средних

Мак-Куин (1967) разработал очень простой прямой метод группирования, названный им методом k средних. Этот метод не только служит примером прямого группирования для независимых классов, но также представляет адаптивное группирование, поскольку,

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

Алгоритм Мак-Куина выглядит следующим образом:

(1) Вычислить множество начальных оценок относя к каждому классу одну из первых точек в На этом этапе

(2) Отнести предъявляемую точку к группе точек для которой расстояние минимально. Неоднозначности разрешаются в пользу группы с меньшим индексом.

(3) Найти новые оценки средних точек вычисляя новые средние для каждой группы.

(За) Если точка не была отнесена к группе то не меняется.

(3б) Если точка отнесена к группе то на основе текущего состава группы устанавливается новая оценка средней точки. Пусть — число экспериментальных точек в группе в момент, когда предъявляется экспериментальная точка. Тогда

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

Качество конструктивного алгоритма, подобного процедуре средних, можно определить лишь экспериментально, поскольку он не связан ни с каким критерием. Несколько примеров Мак-Куина особенно наглядны. В одном слова были оценены по набору их эмоционального значения (например, „хороший, плохой», „пассивный, активный»). Эти оценки определили X. Найденными классами были {покой, сумрачный, озеро, мир, спать, белый}, {нищий, уродливый, равнодушный, недоразвитый, подлый} и {статуя, солнечный свет, время, деревья, мудрый}. Метод был также применен к многомерным оценкам жизни студентов в различных университетах. Здесь были получены две совершенно разные группы: {Рид, Суортмор, Антиох, Одерлин, Брин Мор} и {Корнелл,

Мичиган, Миннесота, Иллинойс, Арканзас, Джорджия, Пердью}. В обоих приложениях результаты выглядят разумными.

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

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

Мейзел (1972) описал центрирующий алгоритм, очень похожий на процедуру средних, за исключением того, что он применяется к данным независимо от порядка наблюдений. Вместо последовательности экспериментальных точек рассматривается множество X, которое надо разбить на подмножества.

Центрирующий алгоритм

(1) Выбрать произвольное множество начальных средних.

(2) Отнести каждую точку из X к той группе, к средней точке которой она ближе, чем к другим средним.

(3) Вычислить путем определения средней точки каждой группы.

(4) Повторять шаги 2 и 3 до тех пор, пот не образуются устойчивые скопления точек.

Как и алгоритм средних, центрирующий алгоритм чувствителен к начальному выбору средних точек и подходящему выбору Несмотря на эти недостатки, метод часто бывает очень полезен. Дир (1969) отметил, что его можно распространить на случай, когда разрешается использовать в качестве средних только определенные их прототипы. В этом случае учитываются потери, связанные с рассмотрением каждой экспериментальной точки, как если бы она на самом деле была прототипом средней точки. Это довольно похоже на допущение изготовителя лифтов, что все человечество можно считать состоящим из людей весом 150 фунтов. Метод Дира можно приспособить для решения задач исследования операций, таких, как расположение складов или прикрепление клиентов к различным центрам обслуживания.