Рассылка закрыта
Вы можете найти рассылки сходной тематики в Каталоге рассылок.
Статистика в SPSS: за пределами кнопочного интерфейса. Выпуск 24
В рассылке используются материалы веб-сайта
www.spsstools.ru
Содержание выпускаНеединственность и инверсии кластерных решений: примеры в SPSS Здравствуйте, уважаемые подписчики! Неединственность и инверсии кластерных решений: примеры в SPSSКак можно почувствовать из названия выпуска, сегодня он посвящён в большей степени некоторым методологическим вопросам анализа, нежели техническим аспектам программирования в пакете. Но, разумеется, и здесь мы прибегнем к помощи синтаксиса SPSS в разборе примеров. Есть такая статья: Morgan, Byron J., Ray, Andrew P.G. Non-uniqueness and Inversions in Cluster Analysis // Applied Statistics, 1995, Vol. 44, No 1 (pp. 117-134). Авторы рассматривают особенности широко распространённых методов иерархического кластерного анализа, связанные с возможностью появления неединственных или инверсных решений. Указанные вопросы изучались и ранее. Заслуга авторов статьи - в подробном обсуждении связанных с ними проблем, а также в демонстрации на 20 "классических" массивах данных для кластерного анализа того, что данные особенности возникают достаточно часто, тогда как в большинстве публикаций и руководств по кластерному анализу они вовсе не обсуждаются. Данный выпуск подготовлен по материалам этой статьи. Я не пересказываю здесь её содержание, а концентрируюсь на демонстрации проблем неединственности и инверсии кластерных решений в пакете SPSS. Но в начале полезно коротко охарактеризовать, что именно мы понимаем под неединственностью и инверсией.
Неединственность кластерного решения (non-uniqueness) Иерархические алгоритмы объединяющего (агломеративного) кластерного анализа строят цепочки кластерных решений с количеством кластеров от n до 1, где n - число наблюдений. На первом шаге алгоритма каждое наблюдение представляет из себя отдельный кластер, а на последнем шаге - все наблюдения объединены. Формирование промежуточных решений происходит за счёт объединения "похожих" друг на друга наблюдений, наблюдений и кластеров и пар кластеров. В этом смысле, не ограничивая общности, каждое наблюдение можно считать кластером. Объединение каждый раз происходит на основе поиска наиболее похожих пар кластеров в матрице сходства (или матрице различий, чаще - матрице расстояний). В первом случае наиболее похожая пара - это пара кластеров, имеющих наибольшую меру сходства, во втором случае - эта пара кластеров, имеющих наименьшую меру различия (например, наименьшее евклидово расстояние, если используется эта метрика). Ситуация неединственности возникает тогда, когда на некотором этапе объединения в матрице сходства/различий существует более одной пары "наиболее похожих" кластеров (например, когда кластеры 1 и 2 удалены друг от друга на то же расстояние, что и 3 и 4, и это расстояние является минимальным среди всех остальных расстояний). В этом случае некоторые статистические пакеты (авторы пишут про SAS, мои эксперименты говорят, что и SPSS тоже) для определённости идут по так называемому стандартному пути кластеризации (default clustering path). Его идея такова... Ещё перед началом кластеризации каждое наблюдение получает порядковый номер. При объединении наблюдений в кластер результирующий кластер получает номер, равный наименьшему номеру объединяемых наблюдений. Та же логика сохраняется и при дальнейшем объединении кластеров, а также кластеров и отдельных наблюдений. В случае появления двух равнозначных пар-кандидатов на объединение, объединяется пара с наибольшим номером кластера/наблюдения. Т.е. в примере выше в первую очередь будут объединены кластеры 3 и 4. Если же кластер с наибольшим номером сам участвует в двух таких "связках" (например, расстояние (1, 4) = расстоянию (2, 4)), объединяется пара с наименьшим идентификационным номером (в нашем примере - 1 и 4). Таким образом, для того, чтобы получить альтернативное кластерное решение на тех же данных и теми же методами, достаточно соответствующим образом изменить порядок наблюдений, участвующих в "связках", в файле данных или матрице сходства/различия. Так или иначе, в случае наличия "связок", благодаря принципу стандартного пути кластеризации пользователь получает лишь одну из нескольких возможных цепочек кластерных решений, а значит волен выбирать не из всего множества разбиений, а из некоторого их поднабора. Проблема может и не быть слишком острой, если только альтернативные цепочки кластерных решений не будут различаться слишком сильно. Неприятный момент состоит в том, что пользователь, как правило не знает о степени различий альтернатив (а иногда и не подозревает об их существовании). Проблема неединственности характерна не только для иерархических методов. Так, в методе k-средних окончательное кластерное разбиение будет зависеть и от порядка наблюдений, и от выбора начальных центроидов, и от наличия равноудалённых центроидов от некоторого наблюдения... Тем не менее, даже разные варианты решений в методе k-средних редко получаются принципиально различными из-за заложенной в методе возможности перераспределения наблюдений между кластерами. В ситуации с иерархическими алгоритмами неоднозначность цепочки решений может приводить к драматическим различиям в выводах. Ведь выбор одной альтернативы может кардинально изменить всю дальнейшую цепочку подобно тому, как выбор, например, учебного заведения в молодости может определить всю дальнейшую жизнь индивида. При этом альтернативные пути построения цепочки решений могут встречаться несколько раз на одних и тех же данных. Разумеется, такие альтернативы будут, если изначально несколько пар наблюдений являются равнозначными кандидатами на объединение. Но ситуации неоднозначности могут возникать и далее по ходу решения, когда в матрице сходства/различий появятся "связанные" кластеры. Ситуации альтернативных решений возникают реже, если кластеризуются данные, измеренные с высокой степенью точности по числовой шкале, и чаще, если мы имеем дело с более "дискретными" данными (например, с ситуацией сильного округления числовых значений). Наиболее часто альтернативные варианты появляются при кластеризации с участием двоичных переменных с использованием специальных метрик. В этом случае количество альтернативных решений может быть настолько велико, что все их рассмотреть практически невозможно. Кроме этого, наличие и число альтернатив, безусловно зависит и от выбранных метрик сходства, и непосредственно от метода кластерного анализа. Авторы упомянутой выше статьи ратуют за то, чтобы в профессиональных статистических пакетах была включена проверка на неединственность иерархического кластерного решения. Пользователю в этом случае необходимо выдавать соответствующее предупреждение. В данном выпуске мы не решаем подобной задачи, а лишь демонстрируем на одном примере существование двух альтернативных решений.
Инверсии кластерных решений (reversals, inversions) Инверсия возникает когда нарушается принцип монотонности построения иерархии. Монотонность имеет место, когда добавление каждого нового кластера к уже существующим кластерам (объединение) происходит на основе "меньшего сходства" чем наблюдалось в кластере до этого. Соблюдение монотонности гарантирует получение монотонного графика функции объединения (возрастающего, если используются меры различий или убывающего, если используются меры сходства). Соответственно, по заметным скачкам на данном графике мы можем видеть снижение однородности при переходе к решению с меньшим числом кластеров и задумываться о вариантах окончательного решения. В упрощенном понимании принцип монотонности заключается в том, что при каждом объединении к кластеру присоединяется нечто менее (а точнее - не более) похожее на него, чем то, что присоединялось к нему до этого. Монотонно снижающаяся однородность кластеров с их укрупнением кажется вполне естественным процессом. Авторы указывают, что среди 7 наиболее популярных методов иерархического кластерного анализа -"ближнего соседа", "дальнего соседа", средней связи, средней взвешенной связи, метода Варда, центроидного метода и медианного метода - лишь последним двум присуща возможность образования инверсий. В центроидном или схожем с ним медианном методе кластеризации на очередном шаге алгоритма некоторый кластер может оказаться на меньшем расстоянии от центроида второго кластера, чем то расстояние, на котором к этому второму кластеру ранее присоединялись другие кластеры. Связана эта особенность с самим принципом центроида-представителя кластера и возможностью перемещения центроида. Ниже мы покажем на простом примере механизм возникновения инверсии, а на более сложном - продемонстрируем, как инверсия может возникать на одной цепочке решений несколько раз. По мнению авторов, инверсии не расставляют каких-либо серьёзных ловушек для исследователей. Иногда их присутствие может быть малозаметным. С другой стороны, в случае множественных инверсий дендрограмма становится "нечитабельной". Множественность инверсий может свидетельствовать в пользу отсутствия чёткой кластерной структуры в данных. С этих позиций мне лично кажется непоследовательной рекомендация авторов... не использовать вовсе центроидный и медианный методы. Непоследовательной - потому, что в кластерном анализе индикаторы отсутствия чёткой структуры столь же важны, как и индикаторы её наличия. Абсолютно бесспорная рекомендация авторов производителям статистического ПО - по крайней мере, предупреждать пользователя о ситуации инверсии, а авторам учебников - освещать подобные вопросы в обязательном порядке.
Неединственность - пример в SPSS Возьмём для примера один из массивов данных, исследованных авторами статьи на неединственность решений. Данный файл приводится в наиболее часто цитируемом учебнике по кластерному анализу - John Hartigan, Clustering Algorithms, Wiley, 1975. Этот массив (как и все массивы из учебника) можно найти на веб сайте http://www.csit.fsu.edu/~burkardt/datasets/hartigan (file29.txt). В примере исследуется схожесть между собой некоторых биологических видов: человека, обезьяны, свиньи, собаки, грибка и проч. В данном случае мы разбираем не исходные данные, а готовую матрицу расстояний, в которой расстояния вычислены по некоторой метрике (возможно, это округлённые евклидовы расстояния, полученные по каким-то исходным переменным, возможно - экспертные оценки силы различий между видами, возможно - какие-то частоты). Перед нами стоит задача провести кластерный анализ этих видов, чтобы установить возможность их классификации на чётко отделимые группы по тем параметрам, которые принимались в расчёт при составлении матрицы расстояний. Команда CLUSTER в SPSS может принимать в качестве входных данных матрицы сходства/различий, однако при этом данные нуждаются в соответствующем описании. Так, кроме непосредственно названий видов и расстояний между ними, необходимо в каждой строке в переменной с характерным именем ROWTYPE_ указать значение PROX (от PROXIMITIES - близости), что сообщает программе о том, что в данной строке находятся показатели схожести объектов между собой. Кроме этого, следует провести соответствие между строками и столбцами матрицы, последовательным именованием переменных с расстояниями как VAR1, VAR2 и т.д., VAR20 (всего имеется 20 видов) и дублированием этих имён в соответствующих строках матрицы (в переменной VARNAME_). Обратите внимание, в нашей матрице на главной диагонали стоят нули, что является необходимым свойством матрицы расстояний в принципе (а по факту наблюдения в файле данных можно легко менять местами; перед началом кластеризации SPSS легко восстановит исходный порядок по значениям переменной VARNAME_). Данные вводятся в программу посредством известных команд DATA LIST и BEGIN DATA - END DATA. Наименование видов указывается в переменной species. Поскольку некоторые виды включают в своём имени пробелы, при использовании подкоманды LIST имена должны быть заключены в кавычки. DATA LIST LIST /ROWTYPE_(A8) species(A20) VARNAME_(A8) VAR1 to VAR20. BEGIN DATA END DATA. Ещё один технический момент - для порядка нужно указать программе, что мы используем меры различия (dissimilarities), т.е. большее значение в матрице соответствует меньшему сходству (см. команду VALUE LABELS). Впрочем, это, скорее аккуратность. По умолчанию это задано и так. Но обратное действие совершенно необходимо, если в матрице стоят меры сходства (similarities). VALUE LABELS ROWTYPE_ 'PROX' 'DISSIMILARITIES'. Теперь проведём кластерный анализ всех 20 видов (переменные с VAR1 по VAR20) методом полной связи ("дальнего соседа") - COMLETE, выведем функцию объединения (SCHEDULE), данные представлены в виде матрицы в текущем файле (MATRIX = IN(*)), пометим везде наблюдения именами видов (ID=species) и, наконец, покажем дендрограмму (PLOT DENDROGRAM). Обратите внимания, поскольку расстояния заданы из матрицы, определения метрики отсутствуют в команде (а если бы были заданы, то игнорировались бы программой). CLUSTER VAR1 to VAR20 Непосредственный разбор структуры полученных кластеров и интерпретация решения в данный момент нас мало интересует. Тем не менее, где-то в глубине души приятно отметить, что "ближайшим родственником" для нас в этой классификации явилась обезьяна, а не гремучая змея или хлебные дрожжи. :-) Теперь - о неединственности. Вернёмся к матрице расстояний. Видно, что многие виды оказались расположены друг от друга на одинаковых расстояниях (например, человек с обезьяной и лошадь с ослом, свинья с собакой и свинья с ослом). Хотя наличие одинаковых расстояний в исходной матрице и не является обязательным условием возникновения неединственности, это обстоятельство увеличивает вероятность получения принципиально разных альтернативных решений. Впрочем, альтернатива альтернативе рознь. В проведённой классификации в первую очередь были объединены в один кластер лошадь и осёл (хотя в равной степени можно было начать с человека и обезьяны). Но, поскольку у осла был больший порядковый номер, согласно принципу стандартного пути кластеризации была объединена именно эта пара животных. Если изменить порядок строк и столбцов в матрице корреляций, чтобы порядковый номер человека или обезьяны превосходил максимальный порядковый номер лошади и осла, то первый сформированный кластер окажется "человекоподобным". При этом, однако, все остальные решения с числом кластеров 18, 17, ..., 1, окажутся в точности такими же, как и без изменения порядка видов в матрице расстояний. Это пример достаточно "безобидной" неединственности. Более интересный пример можно получить так изменив порядок следования видов, что изменится кластерная структура. Рассмотрим содержательно эквивалентную матрицу расстояний с иным порядком видов. DATA LIST LIST /ROWTYPE_(A8) species(A20) VARNAME_(A8) VAR1 to VAR20. BEGIN DATA END DATA. Запустим кластерный анализ с теми же параметрами. CLUSTER VAR1 to VAR20 Серьёзных изменений не видно, но пытливый исследователь увидит на ранних стадиях кластеризации незначительные отличия. То, что началась кластеризация с человека и обезьяны - это ерунда. Обратите внимание на четвёрку "курица, пингвин, голубь, утка" (Chicken, King Penguin, Pigeon, Peking Duck). В первом варианте курица, пингвин и утка сформировали один достаточно однородный кластер, к которому позже (на несколько большем расстоянии) присоединился голубь. Во втором варианте вначале мы получили два однородных кластера (курица - пингвин) и (голубь - утка), которые затем объединили в один. Кто-то скажет, что пример вышел натянутым: всё равно кластерная структура анализируется на более значительных расстояниях (например, чётко выделяется кластер млекопитающих и множество малопохожих "всех остальных" видов). Но, тем не менее, факт - на ранних этапах кластеризации кластерная структура получилась иной. Произошло это всё из-за тех же происков стандартного пути кластеризации. В первом случае после того, как разобрались с человеком, обезьяной, лошадью и ослом, дошла очередь до курицы и пингвина (они находятся на расстоянии 2, объединили). Далее встал вопрос о присоединении утки к голубю (расстояние 3) или утки к кластеру (курица - пингвин, расстояние 3: что до пингвина, что до курицы). Сделан выбор в пользу укрупнения кластера (курица - пингвин), поскольку среди исследовавшихся альтернатив наибольший идентификационный номер был именно у кластера (курица - пингвин - 11) - он достался кластеру по наследству от курицы, чей идентификационный номер был наименьшим из пары (курица (11) - пингвин (12)). И лишь после этого наибольшее расстояние между кластером (курица - пингвин - утка) и голубем (расстояние 4) оказалось наименьшим среди остальных альтернатив. А точнее, альтернативные решения были и в этот раз, но за счёт большого идентификационного номера голубя (10) он выиграл в честной борьбе за право объединиться у собаки со свиньёй. Во втором случае мы повлияли на начальные идентификационные номера и на перепутье утка оказалась присоединённой к голубю, так как её номер (11) оказался выше, чем номер кластера (курица - пингвин - 10). ...перечитал последние 2 абзаца и понял, что вне контекста они будут представлять из себя полный бред... :-) Авторы статьи написали специальную программу, через которую пропустили 20 подобных "классических" примеров данных для кластерного анализа. Ровно в половине массивов возникала неединственность решений, причём иногда различия в решениях оказывались весьма существенными. В статье даже предлагается специальная метрика для исследования отличий решений. Авторы отмечают, что, по результатам их опытов, метод "ближнего соседа" всегда давал уникальные результаты. Наихудшая ситуация с уникальностью наблюдается именно с методом "дальнего соседа" - из всех 7 рассмотренных методов кластеризации он даёт неединственные решения наиболее часто. В заключение исследователи напоминают, что матрица расстояний, как правило, является результатом реализации случайных переменных, а значит единственность наблюдаемого решения в кластерном анализе, вообще говоря, может быть весьма иллюзорной.
Инверсии: пример в SPSS Продемонстрируем механизм возникновения инверсий когда исходными данными являются 4 наблюдения (a - d), измеренные в 2 переменных (x, y). DATA LIST LIST /point (A1) x y. BEGIN DATA END DATA. В качестве метода кластеризации выберем центроидный, в качестве метрики расстояния - евклидово расстояние. Кластеризация, таким образом, допускает прозрачную геометрическую интерпретацию. Рассмотрим относительное положение точек на диаграмме разброса: GRAPH /SCATTERPLOT(BIVAR)=x WITH y BY point (NAME). И запустим процедуру кластеризации: CLUSTER x y На первом шаге будут объединены точки a и b, как наиболее близкие. Центроид кластера займёт положение между ними и наиболее близкой до него окажется точка c. После присоединения c центроид укрупнённого кластера заметно "переезжает" влево. Осталось подсоединить точку d, что и было сделано. Но вот незадача: расстояние от d до нового центроида оказалось меньше, чем от c до старого центроида кластера (a - b). Получается, согласно функции расстояния, более крупный кластер оказался менее разнородным, чем был до этого. Разумеется, такого не могло бы произойти, если бы мы в качестве функции объединения использовали, например, среднее взвешенное расстояние, или статистику Варда - что-то, что более адекватно характеризует дисперсию внутри кластера. Из рисунка, полученного выше, впрочем, очевидно, что доводить дело до 1 кластера не стоило. После объединения a и b стоило остановиться и принять решение с 3 кластерами. Кстати, можно заметить, что в случае использования центроидного, медианного методов и метода Варда, SPSS настаивает на необходимости использования квадрата евклидова расстояния в качестве метрики. (Я затрудняюсь назвать причину подобной рекомендации и буду глубоко признателен, если кто-то из уважаемых подписчиков просветит меня на этот счёт письмом) В данном случае выбор квадрата евклидова расстояния нам поможет - инверсия исчезнет. Но вообще квадрат расстояния, безусловно, не снимает проблему инверсий, как это будет видно из следующего примера. Рассмотрим более практическую задачу из той же книги Хартигана. Данные доступны по ссылке, приведённой выше (file03.txt). Массив представляет собой данные о числе зарегистрированных преступлений
различного вида (на 100 000 населения) в 16 американских городах в 1970 году
(первоисточник: United States DATA LIST LIST /city (A16) murder rape robbery assault burglary larceny autothf (7F4.1). BEGIN DATA END DATA. VARIABLE LABEL murder 'убийства' Проведём кластерный анализ по всем имеющимся переменным с квадратом евклидова расстояния центроидным методом. CLUSTER murder to autothf Из таблицы со значениями функции объединения видно, что на 12 и 13 шагах алгоритма функция убывает, хотя, по логике, должна возрастать. Центроид "слитых" на 11 шаге Бостона и Чигаго оказывается ближе к центроиду кластера Атланта - Тусон - Хартфорд, чем расстояние, на котором были объединены Бостон и Чикаго. А затем относительно неподалёку от центра этого крупного и разнородного кластера оказывается Новый Орлеан. Если произвести несложные манипуляции с таблицей Agglomeration Schedule, можно быстро вывести значения функции объединения на график и увидеть на нём участок отрицательной динамики. Внимательно: двойной клик на таблице, курсор - в заголовок графы Coefficients, правый клик мыши - Select - Data Cells and Label, правый клик мыши - Create Graph - Line. Можно расслабиться. График указывает, что имело смысл остановиться на 9 шаге, когда функция резко пошла вверх (однородность кластеров стала стремительно убывать), либо на 11. Впрочем, окончательное решение лучше принимать, попробовав проведение анализа с другими параметрами: другим методом, например. Необходимо отметить, что существенные различия в дисперсиях переменных (например, между убийствами и кражами со взломом), приводят к тому, что убийства и изнасилования оказываются непоказательными параметрами при группировке городов по криминальной обстановке. Имеет смысл рассмотреть вопрос о стандартизации всех переменных. Забавно, но инверсии не исчезают и в этом случае. Проверьте: PROXIMITIES murder to autothf CLUSTER ERASE FILE = 'C:\temp\spssclus.tmp'. Да, стандартизация "на лету" проходит незаметно при проведении анализа через диалоговые окна, но в синтаксисе оборачивается предварительным построением матрицы расстояний через команду PROXIMITIES. Инверсия в цепочке решений наблюдается дважды, причём "виновниками" наиболее заметной из них по-прежнему являются Бостон и Чикаго. На дендрограмме в пакете SPSS инверсия выглядит так, будто происходит несколько объединений в один кластер на примерно одинаковом расстоянии.
В заключение - прошу понять меня правильно: разобранные сегодня вопросы и выводы по ним - не столько критика кластерного анализа в целом, сколько анализ особенностей работы его методов!
Всего доброго! Ведущий рассылки, Балабанов Антон
© См. www.spsstools.ru, 2005-2006 |
| В избранное | ||
