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

Многие важнейшие понятия кластер–анализа связаны с биологически наследуемыми свойствами людей и других животных. Оказалось, что концепция <сходства> встроена в нервную систему человека. Человек, выросший в примитивных условиях, но с достаточным жизненным опытом, без колебаний сформирует многие кластеры спонтанно: кластер людей, кластер птиц, кластер деревьев и т.д. Он или она без сомнения сочтут кошку более похожей на белку, чем на муравья. Отличие кластер–анализа, который обсуждается в этой книге, от стихийной человеческой деятельности, которую я только что описал, состоит в том, что мы строим кластеры по некоторой системе, исходя из данных.

Это приводит нас к первому из упомянутых выше способу классификации методов, который показан на рис. 1. Существует три основных типа данных, используемых в кластер–анализе. Первый тип я буду называть многомерными данными, второй тип — данными о близости, а третий тип — данными о кластерах. Многомерные данные задают значения нескольких переменных для нескольких индивидуумов. Будем обозначать такие данные через x_ij, где i соответствует индивидууму, а j — переменной. Данные о близости состоят из значений близости объектов одинакового типа. Это могут быть значения близости индивидуумов, переменных, раздражителей, или же значения близости любых однородных объектов. Термин <близость> (следуя терминологии, предложенной Шепардом) относится к сходству, к различию, к корреляции, к мере пересечения или же любой другой переменной, используемой в качестве меры сходства или расстояния между двумя объектами одного вида.

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

Для одного из основных типов общепринятых алгоритмов кластеризации данные о близости берутся в качестве входа, а разбиение на кластеры является выходом. Другой распространенный подход к кластер–анализу — начинать с многомерных данных, преобразуя их в процессе предварительной обработки в данные о близости. Затем данные о близости преобразуются с помощью процедуры только что упомянутого типа в данные о кластерах. Однако мне кажется, что лучше всего такой метод считать состоящим из двух независимых этапов, а выражение <алгоритм кластеризации> использовать для обозначения только второго этапа. В этом .случае мы считаем первый этап предварительным шагом, предшествующим кластеризации. Многие из тех, кто пишет о кластер–анализе, рассматривают этот этап как вычисление индексов сходства или различия. Менее распространенный тип кластеризации, который исследовался время от времени, в основном Хартиганом, начинает с многомерных данных и производит кластеризацию без использования в качестве промежуточных данных значений близости.

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

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

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

Существует очень простая процедура, которую часто используют для преобразования данных о кластерах в значения близости. Для получения значения близости между объектами необходимо вычислить только число субъектов, поместивших объект i и объект j в один кластер. Эти данные о близости можно затем проанализировать любым из методов, пригодных для обработки данных о близости, включая кластеризацию (которая приведет нас назад к данным о кластерах) и многомерное шкалирование (которое приведет нас к многомерным данным). В действительности при использовании большего числа процедур достигается тот же успех. Например, Розенберг и др. [1969] получили, интересные результаты, начиная работать с данными о кластерах и проделав следующую последовательность шагов: вначале используется описанная выше простая процедура для получения матрицы значений близости, затем эта матрица близости рассматривается в качестве матрицы многомерных данных (что приводит нас к вершине диаграммы), а между строками матрицы вычисляются евклидовы расстояния (что приводит нас назад на уровень значений близости); после этого применяется многомерное шкалирование (что опять приводит нас на вершину диаграммы). Также вполне имело бы смысл Начинать сданных о кластерах и по ним непосредственно строить группировку в кластеры без промежуточных шагов (построения значений близости или многомерных данных).

Вторая характеристика, по которой отличаются разные подходы в кластер–анализе, — это цель, для которой он проводится. Существует два типа целей; определенные и неопределенные.

Цели обоих типов законны и обоснованы. Сначала позвольте мне привести в качестве примера несколько определенных целей. В .экономическом моделировании часто бывает необходимо агрегировать компании по отраслям, а районы — по географическим областям. Агрегирование, конечно же, является формой кластер–анализа. Фактически в Соединенных Штатах применяется хорошо разработанный способ иерархического группирования компаний по отраслям промышленности, который называется стандартным промышленным кодом (SIC). Эта пятизначная классификационная система широко используется экономистами. Второй пример определенной цели кластер–анализа встречается в области медицины, а именно стремление улучшить лечение и диагностику. Исследователи–медики часто группируют случаи одного заболевания по подгруппам. Если существуют естественные подгруппы, то можно надеяться, что в них реакция на лечение будет различна, а дальнейшее течение болезни будет отличаться. Если в действительности так и оказывается, то отнесение по кластерам становится чрезвычайно ценным. Третья определенная цель встречается в связи с информационным поиском. Предметный указатель в библиотеке или любая другая информационно–поисковая система — это весьма важные приложения кластер–анализа, хотя для получения таких кластеров обычно не применяют количественный подход, основанный на данных. Эти другие определенные цели характеризуются тем, что они пригодны, по крайней мере в принципе, для измерения того, насколько хорошо отнесение по кластерам служило рассматриваемой цели.

Напротив, неопределенные цели непригодны для измерений. Разбиение на кластеры при неопределенной цели может быть очень ценным, и, возможно, впоследствии мы будем вполне удовлетворены результатами, но обычно получить объективное подтверждение их ценности очень трудно. Первым примером неопределенной цели служит исследовательская цель — просто <посмотреть, что тут такое>. Еще одна цель — облегчить сравнение и оценку данных. Третья цель — подготовить проведение последующего анализа. Например, после процедуры кластер–анализа мы можем захотеть образовать расслоенную подвыборку данных, отбирая определенное число индивидуумов из каждого кластера. Расслоенная подвыборка такого рода часто бывает полезна просто для того, чтобы перед проведением более тонкого анализа сократить объем данных до приемлемых размеров. Другой способ использовать разбиение на кластеры в последующем анализе связан с тем, что у нас может возникнуть желание провести отдельный анализ (например, регрессий) внутри каждого кластера. Если свойства объектов из разных кластеров действительно различны, то вполне возможно, что при переходе от одного кластера к другому коэффициенты регрессии могут изменяться в широких пределах, и поэтому такой способ описания данных был бы гораздо более приемлемым. Последняя неопределенная цель, которую мне хотелось бы упомянуть, — это кластер–анализ ради него самого, что наиболее заметно при построении генеалогических деревьев для языков, растений или животных. Хотя такие родословные в биологии иногда составляются для определенных целей, тем не менее они часто интересны сами по себе.

Другой способ классификации основан на различии между естественными и произвольными кластерами, которое поясняется

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

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

Следующая схема классификации касается возможности пересечения кластеров. Один из вариантов — это простое отнесение по кластерам, при котором их пересечение совсем не допускается. Вторая возможность — простое отнесение по кластерам, разрешающее небольшое пересечение, когда допускается принадлежность объектов, находящихся на границе двух кластеров, им обоим. Третья возможность — известный иерархический кластер–анализ, когда допускается полное включение одного кластера в другой, обусловленное определенными правилами, но не допускается частичное пересечение. Другая возможность пересечения при кластер–анализе подробно исследуется в книге Джардайна и Сибсона [1971]. Хотя их идеи интересны теоретически, мне кажется, что этот подход не является ценным для практики. Другой неиерархический подход, допускающий сильное пересечение кластеров, был развит за последние несколько лет Шепардом и Арабье. Мне кажется, что их метод представляет существенный интерес для практики, и чуть позднее я упомяну об этом.

Другая схема классификации методов кластер–анализа, изображенная на рис. 4, связана со статистической моделью (если таковая есть), на которой данный метод основан. В подходе к кластер–анализу порой отсутствует как явная, так и неявная модель, хотя такие подходы, к счастью, теперь встречаются все реже и реже. На рисунке изображены три наиболее широко используемые модели, а также новая важная модель. Первую из них мне бы хотелось назвать <времяподобное дерево>. Она состоит из дерева, все терминальные узлы которого обычно находятся на первом уровне, и шкалы, расположенной вдоль вертикальной оси. Каждому узлу приписано значение шкалы, и эти значения монотонно изменяются вдоль дерева. Здесь расстояние на дереве задается с помощью d_ij — значения шкалы для самого нижнего узла, из которого доступны объекты i и j. Эта статистическая модель используется в случае данных типа значений близости, где значения близости есть значения различий d_ij. Модель определяется уравнением d_ij = d_ij + ошибка. Эта модель часто соответствует описанию родословных видов или же языков. Вторую модель, которая изображена, мне бы хотелось назвать деревом расстояний. Здесь нет связанной с деревом шкалы. Вместо этого с каждой дугой связана некоторая длина. Величина d_ij — длина пути от i до j, а уравнение, определяющее модель, как и ранее, d_ij = d_ij + ошибка. Оказалось, что деревья расстояний хорошо подходят в качестве моделей развития сложных биологических молекул типа цепочек, таких, как цитохром–с и ДНК. Представляется также, что эти модели подходят для описания эволюции документов, которые претерпели длительное развитие задолго до появления большинства древнейших из известных рукописных копий (например, Тора (Пятикнижие), <Одиссея>, <Илиада> и <Романс о розе>). Другая модель, изображенная на рисунке (ее можно назвать <классической моделью>) используется в случае многомерных данных. Здесь мы предполагаем, что каждый кластер содержит выборку из одного распределения с единственным средним, поэтому уравнение, определяющее модель, таково: x_i = m_k + ошибка, если объект i входит в кластер k. Конечно, используются также и другие модели, но эти три модели наиболее распространены.