Содержание выпуска

Расчёт процента "объяснённой дисперсии" в кластерном решении

Новое на сайте www.spsstools.ru

Здравствуйте, уважаемые подписчики!

Напомню, что продолжается приём заявок на "Справочник по синтаксису SPSS". С анонсом этого проекта можно ознакомиться в прошлом выпуске рассылки.

Расчёт процента "объяснённой дисперсии" в кластерном решении

В нашем выпуске сегодня - не пример из коллекции, а разработанный мной синтаксис, помогающий, IMHO, при проведении кластерного анализа. Будем считать, что читатели знакомы с принципом кластеризации методом k-средних. Этот алгоритм реализован в команде QUICK CLUSTER SPSS. Мы также не будем вдаваться в способы интерпретации кластерного решения, выбора одного решения из множества и так далее. Затронем лишь вопрос об объективной метрике "компактности" полученных кластеров. Построим статистику, которая была бы близка к 0, если облако данных является практически равномерно распределённым, без каких-либо сгущений точек в пространстве и близка к 100%, если в пространстве существуют k заметно отстоящих друг от друга, компактных групп точек. Значения этой метрики помогут нам судить, являются ли полученные кластеры действительно различимыми группами, или же кластеры - это лишь произвольные наборы расположенных по соседству наблюдений. Иными словами, эта метрика поможет решить, можно ли говорить о полученной на основе кластерного анализа типологии, или же кластеры - это лишь один из многих равнозначных вариантов группировки точек. Указанный показатель будет полезен всякий раз, когда кластерное решение затруднительно представить графически на диаграмме разброса (практически - это случаи кластеризации в более, чем 2 или 3-мерном пространстве, а также - кластеризация очень большого числа объектов (точек), что делает невозможным визуальный анализ групп на диаграмме разброса).

Метрика (назовём её D) характеризует "объясняющую" способность кластерного решения и описывается, например, в учебном пособии Балабанов А.С., Стронгина Н.Р. Анализ данных в экономических приложениях. Компьютерный практикум в SPSS. Н.Новгород, Изд-во ННГУ, 2003. Однако, её простота и очевидность заставляют думать, что она описывалась ранее и другими авторам. Аналогичную идею вместе со множеством других показателей качества разбиения в кластерном анализе можно увидеть, например, в статье Maria Halkidi, Yannis Batistakis, Michalis Vazirgiannis On Clustering Validation Techniques, которая доступна в коллекции текстов Forum.Gfk.ru.

Мы исходим из тождества

R_ср² = SUM_j[R_j²*n_j/n]+r_ср², j=1..k

Здесь R_ср² - сумма средних квадратов отклонений от среднего значения по всем переменным, участвующим в кластеризации. Она же - средний квадрат расстояния от каждого наблюдения до общего центра (общей средней). Она же - суммарная дисперсия переменных, участвующих в кластеризации (вычисляется по формуле генеральной дисперсии, со знаменателем, равным n).

R_j² - сумма квадратов расстояний от центра j-го кластера до общего центра.

n_j - количество наблюдений, определённых по результатам кластеризации в j-й кластер.

n - общее количество наблюдений

r_ср² - средний квадрат расстояния от каждого наблюдения до центра своего кластера по всем кластерам.

Ясно, что если кластеры будут компактными внутри себя и разнородными между собой, вклад величины r_ср² (характеризующей ошибку, рассеяние, отклонение от кластерной модели) в формирование суммарной дисперсии будет невелик. В случае же наличия однородного облака данных, основная часть суммарной дисперсии будет формироваться за счёт величины r_ср².

Из этих соображений предлагается статистика D:

D = (R_ср²-r_ср²)*100% / R_ср².

Ясно, что в случае одного кластера величина D будет иметь значение 0, а в случае наличия n кластеров (т.е. число кластеров k равно числу наблюдений n), D будет равно 100%. Последнее будет означать получение абсолютно гомогенных кластеров.

Стремление к получению типологии (отделимых друг от друга модельных типов объектов) должно сопровождаться стремлением к максимизации показателя D при одновременной минимизации числа кластеров. Данная метрика, безусловно, не претендует на однозначное определение таких понятий, как "похожесть" объектов, "однородность" групп, но вполне соответствует логике кластерного анализа методом k-средних.

Одним из вариантов использования этой метрики может быть построение достаточно большого числа кластерных решений с одинаковыми параметрами, но разным числом кластеров. Последний параметр должен пробежать значения от 2 до некоторого числа, меньшего n, которое будет определять сам пользователь. Потом можно построить график величины D для каждого из решений и смотреть на динамику этого показателя. Если при переходе от решения с k-1 кластерами к решению с k кластерами показатель продемонстрирует заметный рост, решение с k кластерами будет иметь заметные преимущества в однородности кластеров перед решением с k-1 кластерами. Если же при увеличении числа кластеров величина D возросла незначительно, возможно, подробно рассматривать новое решение не стоит.

SPSS не предлагает такую метрику однородности кластеров, однако мы могли бы её вычислить сами, применив наши знания синтаксиса.

Общий алгоритм довольно прост:

1. Вычисляем суммарную дисперсию переменных;

2. Проводим кластеризацию на k кластеров, сохраняя при этом расстояние от наблюдения до кластерного центра, возводим это расстояние в квадрат и вычисляем средний квадрат;

3. На основе полученных данных вычисляем статистику D_k, которая будет говорить о том, какая доля суммарной дисперсии признаков объясняется разбиением объектов на группы с k центрами.

4. Пункты 2 и 3 могут повторяться несколько раз для оценки решений с разным числом кластеров.

Ниже приводится пример синтаксиса, рассчитывающего показатель D. Перед тем, как рассматривать его, следует сделать несколько замечаний:

1. В данных могут быть пропуски. Суммарная дисперсия должна быть рассчитана на основе тех наблюдений без пропусков, которые потом будут кластеризованы;

2. Приводимый алгоритм может быть несколько упрощен, если кластеризация проводится по стандартизированным признакам (там не надо считать общую дисперсию. По определению, она равна z: числу стандартизированных переменных, использующихся для кластеризации при отсутствии пропущенных значений);

3. Приводимый алгоритм и работа с ним могут быть значительно упрощены, если использовать макроязык. Я намеренно не стал использовать макросы в данном примере.

4. При использовании алгоритма все переменные, участвующие в кластеризации, должны быть помещены в соседние столбцы в редакторе данных (так, чтобы к ним стало возможно обращение посредством ключевого слова "to"). Кроме этого, они должны быть переименованы в x1, x2,..., xz, где z - номер последней переменной.

5. При работе с синтаксисом следует везде заменить номер переменной с x2 на xz, где z - номер последней переменной.

Загрузим файл примера Employee data.sav, входящий в комплект поставки SPSS. Скорее всего, на вашей машине он находится по тому пути, который указан в команде. В противном случае, измените путь, или загрузите свои данные. Далее мы тут же сохраняем этот файл во временную директорию, так как он будет подвергаться преобразованиям.

GET FILE='C:\Program Files\SPSS\Employee data.sav'.

SAVE OUTFILE='c:\temp\mydata1.sav'.

Допустим, мы хотим провести кластеризацию в пространстве 2-х переменных: salary и salbegin (то есть, текущего и начального жалованья). Осуществим несколько подготовительных действий: переименуем эти переменные в x1 и x2 (команда RENAME VARIABLES), вычислим фильтрующую переменную, которая будет иметь значение 1, если в наблюдении ни одна из переменных x1 и x2 не будет иметь пропусков (функция NMISS), команда COMPUTE, отберём только те наблюдения, для которых отсутствуют пропуски (SELECT IF, неотобранные наблюдения при этом удаляются). А также вычислим группирующую переменную nobreak (она будет иметь значение 1 для всех наблюдений и потребуется нам при выполнении следующей команды AGGREGATE).

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

RENAME VARIABLES (salary to salbegin = x1 to x2).

COMPUTE filt=NMISS(x1 to x2)=0.

SELECT IF filt=1.

COMPUTE nobreak=1.

Следующий блок команд вычисляет суммарную дисперсию переменных, которые используются для кластеризации. Первая команда, AGGREGATE, создаёт в файле данных новые переменные, содержащие стандартные отклонения переменных x1 и x2 (x_s1 и x_s2), а также число наблюдений в файле данных (ncases). Статистика вычисляется по группам, заданным nobreak (т.е. группировка, фактически, не производится, ибо nobreak=1), подкоманда PRESORTED указывает на то, что наблюдения уже были отсортированы по группирующей переменной (разумеется, это так, ведь эта переменная на самом деле - константа). Подкоманды OUTFILE=* и MODE=ADDVARIABLES указывают на то, что статистика будет помещена в рабочий файл путём добавления новых переменных. Ясно, что каждая из новых переменных будет иметь одинаковые значения для всех наблюдений, то есть, информация будет, в определённом смысле, избыточной. После того, как стандартные отклонения получены, нам нужно "превратить" их в дисперсии. Для этого стандарт каждой из переменных возведём в квадрат. Это делается с использованием цикла, заданного командой DO REPEAT для того, чтобы не писать отдельную инструкцию COMPUTE для каждой из переменных кластеризации, которых может быть очень много. Дисперсии помещаются в переменные #x_sq1 и #x_sq2, то есть, временные переменные, которые в редакторе данных не отображаются. Они нужны нам лишь для того, чтобы следующей после закрытия цикла DO REPEAT командой COMPUTE вычислить суммарную дисперсию.
При подсчёте суммарной дисперсии мы складываем дисперсии отдельных переменных с помощью функции SUM. При этом суммарная дисперсия ещё не является нужной нам средней суммой квадратов, поскольку SPSS рассчитывает выборочную дисперсию (со знаменателем n-1 вместо n). Поэтому после суммирования мы исправим полученную сумму, домножив её на (n-1)/n. В нашем случае число наблюдений содержит переменная ncases. Затем мы запускаем отложенные вычисления (EXECUTE).

AGGREGATE
/OUTFILE=* MODE=ADDVARIABLES
/PRESORTED
/BREAK=nobreak
/x_s1 to x_s2 = SD(x1 to x2)/ncases=N.

DO REPEAT x=x_s1 to x_s2 /x_sq=#x_sq1 to #x_sq2.

COMPUTE x_sq=x**2.

END REPEAT.

COMPUTE vartot=SUM(#x_sq1 to #x_sq2)*(ncases-1)/ncases.

EXECUTE.

Следующей командой мы удаляем ненужные нам более переменные, содержащие стандартные отклонения.

DELETE VARIABLES x_s1 to x_s2.

Переменная vartot содержит сумму средних квадратов отклонения от среднего значения по переменным, которые будут участвовать в кластеризации.

Следующий блок команд (заключен между двумя строками из символов "=") проводит кластеризацию на заданное число кластеров, считает средний квадрат "ошибки" и вычисляет величину D, характеризующую, какую долю общей суммы средних квадратов объясняет разбиение объектов на k кластеров. Мы предполагаем, что этот блок будет запускаться несколько раз как единое целое, с различным параметром k - число кластеров. После каждого вычисления программа убирает за собой ненужные переменные.

Так, вы можете попробовать разбиения на 2, 3, 4 и более кластеров, каждый раз запуская указанные команды единым блоком и исправляя при этом количество кластеров в двух местах, обозначенных символами ***.

Команда QUICK CLUSTER выполняет разбиение объектов на k групп по алгоритму кластерного анализа методом k-средних. x1 to x2 указывает на перечень переменных, в пространстве которых проводится группировка, подкоманда /CRITERIA задаёт число кластеров и максимальное число итераций. Подкоманда /SAVE указывает на необходимость сохранения расстояния от наблюдения до центра своего кластера в новую переменную (если подобных переменных не существует в файле данных, она получит имя qcl_1). Остальные параметры не приводятся и идут с установками по умолчанию.

Команда COMPUTE, выполняющаяся сразу после окончания кластеризации, возводит полученные расстояния до центров кластеров в квадрат. Следующая команда (AGGREGATE) по тем же принципам, что и приведённая выше, вычисляет сумму квадратов и помещает её в файл. Поскольку в данном случае нас интересует отклонение не от среднего значения переменной, а просто сумма квадратов, используется функция суммы (SUM), а не стандартное отклонение.

Следующая команда COMPUTE вычисляет меру D как разницу между суммой средних квадратов и средним квадратом расстояния до центра кластера, умноженную на 100 и делённую на сумму средних квадратов.

Далее мы запускаем отложенные вычисления (EXECUTE) и удаляем лишние переменные (DELETE VARIABLES). Файл готов к следующему запуску блока команд кластеризации.

*=================================.

*** В команде QUICK CLUSTER вместо переменной x2 установите переменную,

*** которая является последней в вашем случае.

*** В подкоманде /CRITERIA установите в CLUSTER нужное количество

*** кластеров и при необходимости увеличьте максимальное число итераций (MXITER).

QUICK CLUSTER x1 to x2
/CRITERIA= CLUSTER(2) MXITER(100)
/SAVE DISTANCE.

COMPUTE csq=qcl_1**2.

AGGREGATE
/OUTFILE=* MODE=ADDVARIABLES
/PRESORTED
/BREAK=nobreak
/csqs = SUM(csq).

*** в следующей строке дайте переменной d имя, соответствующее количеству

*** кластеров, на которые разбивались наблюдения (d2, d3, ...).

COMPUTE d2=(vartot-csqs/ncases)*100/vartot.

EXECUTE.

DELETE VARIABLES csq qcl_1 csqs.

*=================================.

Теперь необходимые параметры D вычислены для решений с разным числом кластеров. Следующая команда предполагает, что мы попробовали все решения с числом k от 2 до 10. Графически отобразим величину "объяснённости" суммарной дисперсии для каждого случая. Команда GRAPH строит линейный график, где по горизонтали откладываются маркеры переменных d2-d10, а по вертикали - средние значения каждой из этих переменных. Вместо функции MEAN (средние) можно было бы поставить функцию MAX, или MIN - разницы нет, так как для всех наблюдений каждая из переменных d2-d10 является константой.

GRAPH
/LINE(SIMPLE)= MEAN(d2 d3 d4 d5 d6 d7 d8 d9 d10)
/MISSING=LISTWISE.

Если вы использовали предложенный файл данных для этого примера, вы увидите, что "объяснённость" уже в первом из вариантов превосходит 70%, что означает, что в пространстве кластеризации точки действительно формируют сгущения. 10-кластерное решение даёт 94% объяснения, причём отдельные наблюдения оказываются отщеплёнными в кластеры, состоящие лишь из одного наблюдения. Если прокомментировать эти случаи отдельно, можно исключить данные наблюдения из кластеризации и получить группировку с высокой объясняющей способностью с меньшим числом кластеров.

График показывает, что показатель D стремительно растёт до решения с разбиением на 6 кластеров. Дальше прирост показателя становится незначительным. Таким образом, можно отдельно построить решение с 6 кластерами и тщательно его изучить:

QUICK CLUSTER x1 x2
/CRITERIA= CLUSTER(6) MXITER(100)
/SAVE CLUSTER DISTANCE
/PRINT INITIAL ANOVA CLUSTER DISTAN.

Как видите, в данном случае мы запросили сохранение не только расстояний наблюдений от центра своего кластера (DISTANCE в подкоманде SAVE), но и номер кластера - CLUSTER (в той же подкоманде), а также таблицу ANOVA, таблицу результатов кластеризации (которая, правда, сама по себе нам не очень интересна - эта информация куда более полезна в сохранённых переменных, а лишь ради того, что вместе с этим выводится таблица расстояний между кластерными центрами). Воспользовавшись тем, что пространство кластеризации данном случае 2-мерное, выведем результаты кластеризации на наглядную диаграмму разброса. Если вы выполняли этот пример шаг за шагом, переменная qcl_1 в данном случае будет содержать номер кластера. В результате каждая точка на диаграмме окажется помеченной цветом того кластера, к которому она принадлежит.

GRAPH
/SCATTERPLOT(BIVAR)=x1 WITH x2 BY QCL_1
/MISSING=LISTWISE .

Попробуйте предложенный метод определения эффективности кластеризации на своих данных.

Всего доброго,

Ведущий рассылки,

Балабанов Антон

Новое на сайте www.spsstools.ru

Переведены и добавлены примеры синтаксиса:

Добавить переменные с границами доверительного интервала для среднего.SPS

Байесовские оценки долей и доверительные интервалы.SPS

Значимость по хи-квадрат при заданных q и df.SPS

Вычисление 95% доверительного интервала для медианы.SPS

Проверка Мак-Немара хи-квадрат.SPS

© См. www.spsstools.ru, 2005-2006