Кластерный анализ
Цель кластерного анализа – выделить среди изучаемых объектов группы "схожих" (в каком-то смысле) объектов. Такая задача относится к одной из самых фундаментальных проблем науки – проблеме построения классификации. С точки зрения идеи сокращения матрицы "объект – признак", нахождение кластеров схожих объектов означает значительное уменьшение этой матрицы в направлении объектов (от исходных объектов к значительно более компактному набору их кластеров).
Поскольку задача классификации является универсальной для всех наук, в кластерном анализе синтезируется опыт решения такого рода задач в биологии, ботанике, геологии, истории, психологии и т. д. При этом, из всего многообразия приемов классификации можно выделить ряд последовательных стадий. В компьютерных программах эти стадии проявляются в виде необходимости для исследователя задать набор параметров, без указания которых программы не работают.
Обычно в качестве стадий кластерного анализа выступают следующие этапы:
Определение общей идеи или стратегии построения кластеров.
Выбор способа измерения расстояния в пространстве признаков.
Выбор способа построения кластеров.
1. Определение общей стратегии построения кластеров.
В научной практике выработано значительное число стратегий проведения кластерного анализа. Это может быть иерархический или итеративный подход, метод К-средних или одновременная кластеризация по объектам и признакам и т. д. Для решения различных содержательных задач в специфических предметных областях можно использовать наиболее подходящую стратегию.
Подход, предусматривающий одновременное проведение кластеризации по объектам и признакам может оказаться весьма полезным в медицине, когда при построении кластеров пациентов клиники (это объекты) полезно учитывать лечение, которое им назначено (это признаки).
Метод К-средних, в отличие от других стратегий кластеризации (носящих разведочный характер), предполагает, что изначально задано (или известно) нужное число кластеров (т. е. предполагается конфирматорный анализ). С статистической точки зрения процедура состоит в том, чтобы начав с случайного набора начальных точек (их число соответствует требуемому числу кластеров), дальше так формировать кластеры, чтобы минимизировать разброс показателей внутри кластеров и, одновременно, максимизировать этот разброс между кластерами.
В то же время, наибольшее распространение (как в плане универсальности, так и доступности соответствующих программ) при проведении разведочного анализа получил иерархический подход к построению кластеров. При проведении иерархической (иногда ее еще называют древовидной) кластеризации существует две альтернативы. Это агломеративная и дивизимная кластеризация.
Агломеративная (агломерация – объединение) древовидная кластеризация предполагает, что в качестве исходных групп взяты сами объекты а затем производится их поэтапное объединение так, что в одну подгруппу попадают наиболее близкие из них. Такую процедуру можно проделывать до тех пор, пока все наши исходные объекты не объединятся в одну группу.
Дивизимная (от дивайд – разделять) иерархическая кластеризация в каком-то смысле противоположна агломеративной. Она исходит из того, что сначала все объекты объединены в один кластер, а затем он разделяется на две части, затем каждый из фрагментов опять разделяется на двое и так до тех пор, пока в качестве отдельного кластера не будет выступать отдельный объект.
В качестве иллюстрации используется специальный древовидный график, называемый дендограммой. Это название связано со сходством графика с изображением дерева (его ветвей или корневой системы) (рис. 10).
В качестве примера взята горизонтальная дендограмма, отражающая ход иерархического кластерного анализа 14 объектов. Все объекты расположены по вертикали и обозначаются как Х_1 – Х_14. По горизонтали располагается шкала расстояний между объектами, обозначенная надписью Linkage Distance. Из дендограммы например видно, что дистанция между Х_5 и Х_6 соответствует примерно 2,5 единицам, аналогично определяются все остальные расстояния.
Рис. 10. Пример дендограммы в программе Statistica
Достоинство представления результата в виде дендограммы состоит в том, что с ее помощью легко определить любое число классов (кластеров). Например, если необходимо получить два кластера, то глядя на дендограмму мысленно проведем вертикальную линию так, чтобы она пересекала изображение дендограммы в двух точках. Для приведенного выше примера такую вертикаль можно провести из точки, соответствующей расстоянию 25 единиц. При этом в первый кластер попадут объекты Х_1 и Х_2, а во второй – все остальные (от Х_3 до Х_14). Однако, прежде чем можно будет начать работать с дендограммой необходимо решить еще несколько принципиальных вопросов. Важнейший из них, это вопрос о способе определения расстояния (иногда говорят о близости или дистанции) между объектами в пространстве признаков.
2. Выбор способа измерения расстояния в пространстве признаков.
Если мы рассматриваем группу продуктов питания (это наши объекты), то при определении расстояния между ними мы могли бы принять во внимание число содержащихся в них калорий, их цену, субъективные оценки вкуса, и т. д. (это наши признаки). Наиболее простой способ определения расстояний между объектами в многомерном пространстве признаков состоит в том, чтобы вычислить евклидово расстояние. Если мы имеем два или три измерения, эта мера – фактическое геометрическое расстояние между объектами в пространстве.
В математике существует специальный раздел, исследующий свойства метрических пространств. В частности показано, что для того, чтобы способ определения близости объектов в таком пространстве можно было бы назвать расстоянием (метрикой в математике), необходимо, чтобы он удовлетворял следующим условиям (аксиомы расстояния)1:
Аксиома тождества. Если расстояние обозначить d, а объекты А,В и С, то d(А=В) = 0. Здесь А=В означает совпадение объектов А и В.
Аксиома симметрии d(АВ) = d(ВА); эта аксиома означает, что расстояние не зависит от направления, в котором его измеряют.
Аксиома транзитивности (треугольника) d(AB) меньше или равно d(AC)+d(CB).
Наиболее точно соответствует этому определению расстояния и нашим интуитивным представлениям метрика Евклида. Однако используются и другие способы определения расстояния, хотя некоторые из их не удовлетворяют аксиомам расстояния (например, расстояние основанное на коэффициенте корреляции Пирсона-Браве, для которого не выполняется аксиома транзитивности). Важно помнить, что в реальной исследовательской практике пространство признаков редко бывает евклидовым и алгоритм компьютерной программы не проверяет, выбрана ли подходящая метрика. Это задача самого исследователя, у которого имеется богатый выбор, включающий более чем 20 метрик, из которых некоторые наиболее известные:
евклидово расстояние. Это – наиболее выбираемый тип расстояния. Определяется как геометрическое расстояние в многомерном пространстве. Рассчитывается – квадратный корень из суммы квадратов разностей координат соответствующих объектов d(x, y) =
.
Именно эту метрику рекомендуют применять
при первой попытке анализа;
квадрат евклидова расстояния. Сходна с предыдущей метрикой, однако обеспечивает упрощение расчетов (не надо извлекать квадратный корень из суммы квадратов) d2(x, y) = Σ(x – y)2;
расстояние городских кварталов (Манхэттанское). Это расстояние – просто суммарное различие между объектами по всем признакам. Оно получило свое название благодаря тому, что соответствует расстоянию между двумя точками в городе х и у, измеренному как число кварталов, которое надо пройти. Формально расстояние городских кварталов вычисляется как:
d(x, y) = Σ | x – y |;
чебышева расстояние. С помощью этой меры два объекта определяются как различные, если они отличаются хотя бы по одному признаку (измерению). Расстояние Чебышева может быть вычислено как d(x, y) = Max |x – y|;
расстояние мощи. Позволяет увеличить или уменьшить вес (значимость) признака, по которому объекты различаются наиболее сильно;
процент разноглася. Эта мера особенно полезна, если данные измерений, включенных в анализ номинальны по своей природе;
коэффициент Пирсона. Не является метрикой в строгом смысле этого слова, однако очень полезен, когда надо различить данные в виде профиля (например, психологические профили по тесту MMPI). Недостаток – такая метрика близости не чувствительна к сдвигу профиля (в отличие от евклидова расстояния).
В ходе иерархического кластерного анализа приходиться определять расстояние не только между исходными объектами, но и их группами (кластерами), образующимися на каждом шаге анализа. Это порождает потребность определения дистанции между кластерами в ходе анализа.
3. Выбор способа построения кластеров.
В ходе иерархического анализа производится пошаговое объединение объектов. На первом шаге, когда каждый кластер представляет собой отдельный объект, расстояние между этими объектами определяются на базе избранной на предыдущем этапе меры расстояния. Однако, как только несколько объектов были связаны вместе, возникает вопрос как мы определяем расстояния между этими новыми группами? Другими словами, возникает необходимость в правиле объединения, чтобы определить, когда две группы достаточно подобны, чтобы быть связанными вместе. Возможны следующие методы объединения:
одиночной связи – использует "самых близких соседей" из групп, чтобы определить расстояния между ними. Такое правило производит группы связанные вместе "цепочкой", через пары объектов, ближайших друг к другу;
полной связи. В этом методе, расстояния между группами определены самым большим расстоянием между любыми двумя объектами из групп (то есть, используются "дальние соседи"). Этот метод обычно хорошо работает в случаях, когда объекты фактически формируются в естественно различимые скопления шаровидного типа. Если группы имеют тенденцию быть так или иначе удлиненными, то этот метод неадекватен;
невзвешенное межгрупповое среднее. В этом методе, расстояние между двумя группами рассчитано как среднее расстояние между всеми парами объектов в двух различных группах. Этот метод весьма эффективен, и когда объекты формируют естественные шаровые скопления, и для "удлиненных" групп типа "цепи";
взвешенное межгрупповое среднее. Даный метод идентичен невзвешенному методу межгруппового среднего, за исключением того, что в вычислениях, размер соответствующих групп (то есть, число объектов, содержащихся в них) используется как вес. Этот метод, в отличие от предыдущего, должен использоваться, когда размеры групп предполагаются очень неравными;
невзвешенной средней связи (центроидный). Центроидом группы называется ее средняя точка, аналогичная центру тяжести группы. В этом методе, расстояние между двумя группами определяется как расстояние между их центроидами;
взвешенной средней связи. Этот метод идентичен предыдущему, за исключением того, что вводится коэффициент, учитывающий различия в размерах групп (то есть, число объектов, содержащихся в них). Таким образом, когда имеются (или предполагаются) значительные различия в размерах групп, этот метод предпочтительнее предыдущего;
уорда. Для формирования групп используется минимизация рассеивания (дисперсии) признаков внутри групп. Данный метод рассматривается как очень эффективный, однако, он имеет тенденцию создавать группы небольшого размера.
Наряду с соблюдением формальных параметров при проведении кластерного анализа очень важно выбрать для анализа из всех доступных признаков исследуемых объектов, только те, которые релевантны задаче (обычно их число невелико).
Если некоторые выбранные для анализа признаки имеют нечисловую природу, то проведение анализа вполне возможно, однако осмысленно подобрать метрику для определения расстояния между объектами становится практически невозможно. В подобной ситуации можно использовать следующий практический прием, предполагающий проведение анализа с несколькими (2–3) различными метриками. Если структура полученных при этом дендограмм будет близка, то можно считать, что она не является артефактом метода, а порождена объективными особенностями изучаемого явления. В таком случае именно эту структуру и надо анализировать. Если каждый раз, при изменении метрики или правила объединения в кластер получается уникальный результат, то он, скорее всего, является порождением метода, а не природы.
В силу плохой статистической обоснованности большинства стратегий кластеризации, обычно очень трудно понять, насколько полученное решение качественно. Поэтому, очень важно убедиться в надежности получаемого кластерного решения. Для этой цели обычно рекомендуется провести кластерный анализ аналогичных данных для различающихся выборок (разбить исходную выборку на две части и для каждой из них выполнить кластерный анализ по одинаковой схеме). Если структура полученных результатов будет схожей, то это обстоятельство существенно увеличивает надежность такого решения.
Отметим, что вопрос о числе кластеров, которое необходимо выделить в ходе анализа, не имеет формального решения и определяется исходя из содержательных соображений.
Для интерпретации полученных кластеров используют те различия между ними, которые удается выявить по признакам, не входившим в определение соответствующего пространства признаков для кластерного анализа. Например, если таким признаком является пол или возраст респондентов, то различия в этих показателях для различных кластеров служат основой их содержательной интерпретации не в меньшей мере, чем различия в признаках, на основании которых задавалось пространство для кластерного анализа.
Таким образом, основная идея кластерного анализа состоит в объединении наиболее близких в пространстве признаков объектов в "сгущения" или кластеры. Для этого используется набор выработанных в различных дисциплинах практических способов, позволяющий получить нужный результат, но с точки статистики являющийся плохо обоснованным.
Наряду с попыткой объединить в группы (кластеры) объекты в пространстве признаков, естественно рассмотреть и аналогичную задачу, состоящую в объединении наиболее "близких" признаков. Подобная идея лежит в основе одного из наиболее популярных в психологии (во многом, благодаря работам Спирмена и Кеттела) многомерных методов анализа – факторного анализа.