Проектирование систем искусственного интеллекта

Методы и алгоритмы анализа структуры многомерных данных

Разбить на страницы
Показывать лекцию целиком

Если процедура факторного анализа сжимает в малое число количественных переменных данные, описанные количественными переменными, то кластерный анализ сжимает данные в классификацию объектов. Синонимами термина "кластерный анализ" являются "автоматическая классификация объектов без учителя" и "таксономия".

Если данные понимать как точки в признаковом пространстве, то задача кластерного анализа формулируется как выделение "сгущений точек", разбиение совокупности на однородные подмножества объектов.

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

Кластерный анализ является описательной процедурой, он не позволяет сделать никаких статистических выводов, но дает возможность провести своеобразную разведку — изучить "структуру совокупности".

Иерархический кластерный анализ

Процедура иерархического кластерного анализа в SPSS предусматривает группировку как объектов (строк матрицы данных), так и переменных (столбцов). Можно считать, что в последнем случае роль объектов играют переменные, а роль переменных — столбцы.

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

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

  • Среднее расстояние между кластерами (Between-groups linkage).
  • Среднее расстояние между всеми объектами пары кластеров с учетом расстояний внутри кластеров(Within-groups linkage).
  • Расстояние между ближайшими соседями — ближайшими объектами кластеров (Nearest neighbor).
  • Расстояние между самыми далекими соседями (Furthest neighbor).
  • Расстояние между центрами кластеров (Centroid clustering).
  • Расстояние между центрами кластеров (Centroid clustering), или центроидный метод. Недостатком этого метода является то, что центр объединенного кластера вычисляется как среднее центров объединяемых кластеров, без учета их объема.
  • Метод медиан — тот же центроидный метод, но центр объединенного кластера вычисляется как среднее всех объектов (Median clustering).
  • Метод Варда (Ward's method). В качестве расстояния между кластерами берется прирост суммы квадратов расстояний объектов до центров кластеров, получаемый в результате их объединения.
    •

    Расстояния и меры близости между объектами. У нас нет возможности сделать полный обзор всех коэффициентов, поэтому остановимся лишь на характерных расстояниях и мерах близости для определенных видов данных.

    Меры близости отличаются от расстояний тем, что они тем больше, чем более похожи объекты.

    Пусть имеются два объекта X=(X1,…,Xm) и Y=(Y1,…,Ym). Применяя эту запись для объектов, определить основные виды расстояний, используемых процедуре CLUSTER:

  • Евклидово расстояние $$d(X,Y)=\sqrt{\sum\limits_{i=1}^{m} (X_i-Y_i)^2}$$ (Euclidian distance).
  • Квадрат евклидова расстояния $$d(X,Y)=\sum\limits_{i=1}^{m} (X_i-Y_i)^2$$ (Squared Euclidian distance)
    •

    Эвклидово расстояние и его квадрат целесообразно использовать для анализа количественных данных.

  • Мера близости — коэффициент корреляции $$S(X,Y)=(\sum\limits_{i=1}^{m} Z_{X_i}Z_{Y_i})/(m-1)$$, где $$Z_{X_i}$$ и $$Z_{Y_i}$$ — компоненты стандартизованных векторов X и Y. Эту меру целесообразно использовать для выявления кластеров переменных, а не объектов.
  • Расстояние хи-квадрат получается на основе таблицы сопряженности, составленной из объектов X и Y, которые, предположительно, являются
    Таблица для пары объектов — строк частот
    X X1 ... Xm X.
    Y Y1 ... Ym Y.
    X+Y X1+Y1 ... Xm+Ym X.+Y.
    векторами частот. Здесь рассматриваются ожидаемые значения элементов, равные E(Xi)=X.*(Xi+Yi)/(X.+Y.) и E(Yi)=Y.*(Xi+Yi)/(X.+Y.), а расстояние хи-квадрат имеет вид корня из соответствующего показателя $$d(X,Y)=\sqrt{\sum\limits_{i=1}^{m}\frac{(X_i-E(X_i))^2}{E(X_i)}+\sum\limits_{i=1}^{m}\frac{(Y_i-E(Y_i))^2}{E(Y_i)}}$$.
  • Расстояние Фи-квадрат является расстоянием хи-квадрат, нормированным "число объектов" в таблице сопряженности, представляемой строками X и Y, т.е. на корень квадратный из N=X.+Y..
  • В иерархичесом кластерном анализе в SPSS также имеется несколько видов расстояний для бинарных данных (векторы X и Y состоят из нулей и единиц, обозначающих наличие или отсутствие определенных свойств объектов). Наиболее естественными из них, по видимому, являются евклидово расстояние и его квадрат.
    •

    Стандартизация

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

  • Z -шкалы (Z-Scores). Из значений переменных вычитается их среднее, и эти значения делятся на стандартное отклонение.
  • Разброс от -1 до 1. Линейным преобразованием переменных добиваются разброса значений от -1 до 1.
  • Разброс от 0 до 1. Линейным преобразованием переменных добиваются разброса значений от 0 до 1.
  • Максимум 1. Значения переменных делятся на их максимум.
  • Среднее 1. Значения переменных делятся на их среднее.
  • Стандартное отклонение 1. Значения переменных делятся на стандартное отклонение.
  • Кроме того, возможны преобразования самих расстояний, в частности, можно расстояния заменить их абсолютными значениями, это актуально для коэффициентов корреляции. Можно также все расстояния преобразовать так, чтобы они изменялись от 0 до 1.
    •

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

    Процесс агрегирования данных может быть представлен графически деревом объединения кластеров (Dendrogramm) либо "сосульковой" диаграммой (Icicle).(рис 5.2) Дендрограмма классификацииНо подробнее о процессе кластеризации можно узнать по протоколу объединения кластеров (Schedule).

    Пример иерархического кластерного анализа. Проведем кластерный анализ по полученным нами ранее факторам на агрегированном файле Курильского опроса:(рис 5.3) Классификация городов

    CLUSTER fac1_1 fac2_1 /METHOD BAVERAGE /MEASURE= SEUCLID /ID=name /PRINT SCHEDULE CLUSTER(3,5) /PLOT DENDROGRAM .

    В команде указаны переменные fac1_1 fac2_1 для кластеризации. По умолчанию расстояние между кластерами определяется по среднему расстоянию между объектами ( METHOD BAVERAGE ), а расстояние между объектами — как квадрат евклидова ( MEASURE= SEUCLID ). Кроме того, распечатывается протокол ( PRINT SCHEDULE ), в качестве переменных выводятся классификации из 3, 4, 5 кластеров ( CLUSTER(3,5) ) и строится дендрограмма ( PLOT DENDROGRAM ).

    Разрез дерева агрегирования (рис. 5.2) вертикальной чертой на четыре части дал два кластера, состоящих из уникальных по своим характеристикам городов Александровск-Сахалинский и Черемхово; кластер из 5 городов (Оха, Елизово, Южно-Сахалинск, Хабаровск, Курильск); еще один кластер из 14 городов составили последний кластер.

    Естественность такой классификации демонстрирует полученное поле рассеяния данных (рис.5.3).

    Протокол объединения кластеров
    Cluster CombinedCoefficientsStage Cluster First AppearsNext Stage
    StageCluster 1Cluster 2Cluster 1Cluster 2
    1 5 20 0.0115 0 0 2
    2 5 11 0.0175 1 0 3
    3 5 19 0.0464 2 0 11
    4 6 12 0.0510 0 0 8
    5 3 16 0.0549 0 0 9
    6 13 21 0.0808 0 0 10
    7 10 14 0.1082 0 0 14
    8 6 15 0.1349 4 0 11
    9 3 8 0.1538 5 0 13
    10 1 13 0.2818 0 6 12
    11 5 6 0.4560 3 8 13
    12 1 2 0.5768 10 0 16
    13 3 5 0.5861 9 11 16
    14 10 17 0.6130 7 0 17
    15 7 18 0.8098 0 0 17
    16 1 3 1.5406 12 13 18
    17 7 10 2.5726 15 14 19
    18 1 4 3.5613 16 0 19
    19 1 7 5.2217 18 17 20
    20 1 9 14.9146 19 0 0

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

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

    Быстрый кластерный анализ

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

    Здесь наиболее приемлем быстрый алгоритм, носящий название метода " k -средних". Он реализуется в пакете командой QUICK CLUSTER или командой меню k -means.

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

    Затем заново вычисляются центры этих кластеров, которыми после этого момента считаются покоординатные средние кластеров. После этого опять перераспределяются объекты. Вычисление центров и перераспределение объектов происходит до тех пор, пока не стабилизируются центры.

    Синтаксис команды:

    QUICK CLUSTER W3d1 TO W3D6/CRITERIA CLUSTERS(3) /MISSING=PAIRWISE /SAVE CLUSTER(SAVCLU) /PRINT ANOVA.

    За именем команды располагаются переменные, по которым происходит кластеризация. Параметр /CRITERIA CLUSTERS задает в скобках число кластеров. Подкомандой /SAVE CLUSTER можно сохранить полученную классификацию в виде переменной, имя которой дается в скобках. Подкоманда /PRINT ANOVA позволяет провести по каждой переменной одномерный дисперсионный анализ — сравнение средних в кластерах. Этот анализ имеет лишь описательное значение и позволяет определить переменные, которые не оказывают никакого влияния на классификацию.

    Команда использует только евклидово расстояние. При этом часть переменных может иметь неопределенные значения, расстояния до центров определяются по определенным значениям. Для использования такой возможности следует употребить подкоманду /MISSING=PAIRWISE.

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

    Для этого можно использовать команду DESCRIPTIVE. Напомним, что подкоманда /save в ней позволяет автоматически сохранить стандартизованные переменные. Кроме того, хорошие средства стандартизующих преобразований шкал дает команда RANK.

    В выдаче распечатываются центры кластеров (средние значения переменных кластеризации для каждого кластера), получаемые на каждой итерации алгоритма. Однако для нас полезна лишь часть выдачи, помеченная текстом "Final centres".

    Интерпретация кластеров осуществляется на основе сравнения средних значений, выдаваемых процедурой, а также исследования сохраненной переменной средствами статистического пакета.

    Пример использования QUICK CLUSTER. Для иллюстрации построим классификацию по предварительно отобранным данным городских семей по жилплощади и душевому доходу. Такая классификация может грубо, но наглядно показать различие семей по благосостоянию.

    В данных, полученных из обследования RLMS 1998 г. имеются переменные: c5 — жилплощадь, приходящаяся на семью, memb — число членов семьи, df14 — суммарные денежные доходы семьи.

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

    *вычисление логарифма жилплощади на члена семьи.

    compute lns=Ln(dc5/memb).

    *вычисление логарифма душевого дохода.

    compute lincome=ln(df14/memb).

    *стандартизация переменных.

    DESCRIPTIVES VARIABLES=lincome lns/SAVE .

    QUICK CLUSTER zlincome zlns /MISSING=PAIRWISE /CRITERIA= CLUSTER(3) /SAVE CLUSTER /PRINT ANOVA.

    На основании таблицы 7.5 центров классов интерпретация полученных кластеров следующая:

    Кластер 1 — зажиточные семьи, имеющие относительно большой доход и жилплощадь.

    Кластер 2 — семьи, проживающие в квартирах с небольшой площадью, но имеющие относительно высокий доход.

    Кластер 3 — семьи, имеющие низкий доход и ограниченные в жилплощади.

    Кластер 4 — семьи, имеющие несколько больший доход, чем в среднем, но ограниченные в жилплощади.

    Центры кластеров (Final Cluster Centers)
    Cluster
    1 2 3 4
    Zscore(LINCOME) 1.26 0.52 -1.08 -0.40
    Zscore(LNS) 1.35 -0.56 -0.86 0.58
    Дисперсионный анализ в методе k-средних (ANOVA, имееет только описательное значение)
    ClusterErrorFSig
    Mean Square Df Mean Square Df
    ZLINCOME Zscore(LINCOME) 513.006 3 .370 2440 1384.7 0
    ZLNS Zscore(LNS) 530.153 3 .363 2491 1461.6 0
    (рис 5.5) Классификация семей по душевому доходу Lincome и жилплощади на человека LNS (в логарифмических шкалах).

    Дисперсионный анализ (табл. 5.4) показал, что по обоим переменным различие кластеров существенно. Но о статистической значимости переменных говорить бессмысленно, поскольку гипотеза дисперсионного анализа — по сути, независимость групп и "зависимой" переменной, а в данном случае группы сформированы на основе значений "независимых" переменных.

    Полезно рассмотреть график рассеяния данных по кластерам (рис. 5.5). В нашем случае, пожалуй, не стоит говорить о выделении "сгущений" точек в признаковом пространстве, скорее, программа нашла разумные границы для описания типов, выделив их в непрерывном двумерном распределении.

    Кластерный анализ

    Кластерный анализ предназначен для разбиения множества объектов на заданное или неизвестное число классов на основании некоторого математического критерия качества классификации (cluster (англ.) — гроздь, пучок, скопление, группа элементов, характеризуемых каким-либо общим свойством). Критерий качества кластеризации в той или иной мере отражает следующие неформальные требования:

  • внутри групп объекты должны быть тесно связаны между собой;
  • объекты разных групп должны быть далеки друг от друга;
  • при прочих равных условиях распределения объектов по группам должны быть равномерными.
    •

    Требования 1) и 2) выражают стандартную концепцию компактности классов разбиения; требование 3) состоит в том, чтобы критерий не навязывал объединения отдельных групп объектов.

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

    Другой важной величиной в кластерном анализе является расстояние между целыми группами объектов. Приведем примеры наиболее распространенных расстояний и мер близости, характеризующих взаимное расположение отдельных групп объектов. Пусть wi — i -я группа (класс, кластер) объектов, Ni — число объектов, образующих группу wi, вектор $$\mu_i$$ — среднее арифметическое объектов, входящих в wi (другими словами, $$\mu_i$$ — "центр тяжести" i-й группы), a q ( wl, wm ) — расстояние между группами wl и wm.

    (рис 5.6) Различные способы определения расстояния между кластерами wl и wm: 1 — по центрам тяжести, 2 — по ближайшим объектам, 3 — по самым далеким объектам

    Расстояние ближайшего соседа есть расстояние между ближайшими объектами кластеров:$$q_{\min}(w_1,w_m)=\mathop{\min d(x_i,x_j)}\limits_{x_i*w_1, x_j*w_m}$$

    Расстояние дальнего соседа — расстояние между самыми дальними объектами кластеров:$$q_{\max}(w_1,w_m)=\mathop{\max d(x_i,x_j)}\limits_{x_i*w_1, x_j*w_m}$$

    Расстояние центров тяжести равно расстоянию между центральными точками кластеров:

    $$q(w_1,w_m)=d(\mu_1,\mu_m)$$

    Обобщенное (по Колмогорову) расстояние между классами, или обобщенное K -расстояние, вычисляется по формуле $$q_{\tau}^{(K)}(w_1,w_m)\left[\frac{1}{N_1 N_m} \sum\limits_{x_i*w_1} \sum\limits_{x_j*w_m} d^{\tau}(x_i,x_j)\right]^{\frac{1}{\tau}}$$

    В частности, при $$\tau \to \propto$$ и при $$\tau \to -\propto$$ имеем

    $$q_{\infty}^{(K)}(w_1,w_m)=q_{max}(w_1,w_m)\\q_{-\infty}^{(K)}(w_1,w_m)=q_{max}(w_1,w_m)$$

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

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

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

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

    Функционалы качества и конкретные алгоритмы автоматической классификации достаточно полно и подробно рассмотрены в специальной литературе. Эти функционалы и алгоритмы характеризуются различной трудоемкостью и подчас требуют ресурсов высокопроизводительных компьютеров. Разнообразные процедуры кластерного анализа входят в состав практически всех современных пакетов прикладных программ для статистической обработки многомерных данных.

    Иерархическое группирование

    (рис 5.7) Результаты работы иерархической агломеративной процедуры группирования объектов, представленные в виде дендрограммы

    Классификационные процедуры иерархического типа предназначены для получения наглядного представления о стратификационной структуре всей исследуемой совокупности объектов. Эти процедуры основаны на последовательном объединении кластеров (агломеративные процедуры) и на последовательном разбиении (дивизимные процедуры). Наибольшее распространение получили агломеративные процедуры. Рассмотрим последовательность операций в таких процедурах.

    На первом шаге все объекты считаются отдельными кластерами. Затем на каждом последующем шаге два ближайших кластера объединяются в один. Каждое объединение уменьшает число кластеров на один так, что в конце концов все объекты объединяются в один кластер. Наиболее подходящее разбиение выбирает чаще всего сам исследователь, которому предоставляется дендрограмма, отображающая результаты группирования объектов на всех шагах алгоритма (рис. 5.7). Могут одновременно также использоваться и математические критерии качества группирования.

    Различные варианты определения расстояния между кластерами дают различные варианты иерархических агломеративных процедур. Учитывая специфику подобных процедур, для задания расстояния между классами оказывается достаточным указать порядок пересчета расстояний между классом wl и классом w(m, n) являющимся объединением двух других классов wm и wn по расстояниям qmт = q(wm, wn) и qlт = q(wl, wn) между этими классами. В литературе предлагается следующая общая формула для вычисления расстояния между некоторым классом wl и классом w(m, n):

    $$q_{l(m,n)}q(w_1,w(m,n))=\alpha q_{lm}+\beta q_{ln} +\gamma q_{mn}+\delta |q_{lm}-q_{ln}|$$

    где $$\alpha ,\beta ,\gamma$$ и $$\delta$$ — числовые коэффициенты, определяющие нацеленность агломеративной процедуры на решение той или иной экстремальной задачи. В частности, полагая $$\alpha =\beta =-\delta =1/2$$ и $$\gamma =0$$, приходим к расстоянию, измеряемому по принципу ближайшего соседа. Если положить $$\alpha =\beta =\delta =1/2$$ и $$\gamma =0$$, то расстояние между двумя классами определится как расстояние между двумя самыми далекими объектами этих классов, то есть это будет расстояние дальнего соседа. И, наконец, выбор коэффициентов соотношения по формулам

    $$\alpha =\frac{N_m}{N_m+N_n},\beta =\frac{N_n}{N_m+N_n},\gamma = \delta =0$$

    приводит к расстоянию qcр между классами, вычисленному как среднее расстояние между всеми парами объектов, один из которых берется из одного класса, а другой из другого.

    Использование следующей модификации формулы

    $$q^2_{l(m,n)}=\frac{N_1+N_m}{N_l+N_m+N_n}q^2_{lm} + \frac{N_l+N_n}{N_l+N_m+N_n}q^2_{ln} - \frac{N_l}{N_l+N_m+N_n}q^2_{mn}$$

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

    Страницы:

    Если процедура факторного анализа сжимает в малое число количественных переменных данные, описанные количественными переменными, то кластерный анализ сжимает данные в классификацию объектов. Синонимами термина "кластерный анализ" являются "автоматическая классификация объектов без учителя" и "таксономия".

    Если данные понимать как точки в признаковом пространстве, то задача кластерного анализа формулируется как выделение "сгущений точек", разбиение совокупности на однородные подмножества объектов.

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

    Кластерный анализ является описательной процедурой, он не позволяет сделать никаких статистических выводов, но дает возможность провести своеобразную разведку — изучить "структуру совокупности".

    Иерархический кластерный анализ

    Процедура иерархического кластерного анализа в SPSS предусматривает группировку как объектов (строк матрицы данных), так и переменных (столбцов). Можно считать, что в последнем случае роль объектов играют переменные, а роль переменных — столбцы.

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

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

  • Среднее расстояние между кластерами (Between-groups linkage).
  • Среднее расстояние между всеми объектами пары кластеров с учетом расстояний внутри кластеров(Within-groups linkage).
  • Расстояние между ближайшими соседями — ближайшими объектами кластеров (Nearest neighbor).
  • Расстояние между самыми далекими соседями (Furthest neighbor).
  • Расстояние между центрами кластеров (Centroid clustering).
  • Расстояние между центрами кластеров (Centroid clustering), или центроидный метод. Недостатком этого метода является то, что центр объединенного кластера вычисляется как среднее центров объединяемых кластеров, без учета их объема.
  • Метод медиан — тот же центроидный метод, но центр объединенного кластера вычисляется как среднее всех объектов (Median clustering).
  • Метод Варда (Ward's method). В качестве расстояния между кластерами берется прирост суммы квадратов расстояний объектов до центров кластеров, получаемый в результате их объединения.
    •

    Расстояния и меры близости между объектами. У нас нет возможности сделать полный обзор всех коэффициентов, поэтому остановимся лишь на характерных расстояниях и мерах близости для определенных видов данных.

    Меры близости отличаются от расстояний тем, что они тем больше, чем более похожи объекты.

    Пусть имеются два объекта X=(X1,…,Xm) и Y=(Y1,…,Ym). Применяя эту запись для объектов, определить основные виды расстояний, используемых процедуре CLUSTER:

  • Евклидово расстояние $$d(X,Y)=\sqrt{\sum\limits_{i=1}^{m} (X_i-Y_i)^2}$$ (Euclidian distance).
  • Квадрат евклидова расстояния $$d(X,Y)=\sum\limits_{i=1}^{m} (X_i-Y_i)^2$$ (Squared Euclidian distance)
    •

    Эвклидово расстояние и его квадрат целесообразно использовать для анализа количественных данных.

  • Мера близости — коэффициент корреляции $$S(X,Y)=(\sum\limits_{i=1}^{m} Z_{X_i}Z_{Y_i})/(m-1)$$, где $$Z_{X_i}$$ и $$Z_{Y_i}$$ — компоненты стандартизованных векторов X и Y. Эту меру целесообразно использовать для выявления кластеров переменных, а не объектов.
  • Расстояние хи-квадрат получается на основе таблицы сопряженности, составленной из объектов X и Y, которые, предположительно, являются
    Таблица для пары объектов — строк частот
    X X1 ... Xm X.
    Y Y1 ... Ym Y.
    X+Y X1+Y1 ... Xm+Ym X.+Y.
    векторами частот. Здесь рассматриваются ожидаемые значения элементов, равные E(Xi)=X.*(Xi+Yi)/(X.+Y.) и E(Yi)=Y.*(Xi+Yi)/(X.+Y.), а расстояние хи-квадрат имеет вид корня из соответствующего показателя $$d(X,Y)=\sqrt{\sum\limits_{i=1}^{m}\frac{(X_i-E(X_i))^2}{E(X_i)}+\sum\limits_{i=1}^{m}\frac{(Y_i-E(Y_i))^2}{E(Y_i)}}$$.
  • Расстояние Фи-квадрат является расстоянием хи-квадрат, нормированным "число объектов" в таблице сопряженности, представляемой строками X и Y, т.е. на корень квадратный из N=X.+Y..
  • В иерархичесом кластерном анализе в SPSS также имеется несколько видов расстояний для бинарных данных (векторы X и Y состоят из нулей и единиц, обозначающих наличие или отсутствие определенных свойств объектов). Наиболее естественными из них, по видимому, являются евклидово расстояние и его квадрат.
    •

    Стандартизация

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

  • Z -шкалы (Z-Scores). Из значений переменных вычитается их среднее, и эти значения делятся на стандартное отклонение.
  • Разброс от -1 до 1. Линейным преобразованием переменных добиваются разброса значений от -1 до 1.
  • Разброс от 0 до 1. Линейным преобразованием переменных добиваются разброса значений от 0 до 1.
  • Максимум 1. Значения переменных делятся на их максимум.
  • Среднее 1. Значения переменных делятся на их среднее.
  • Стандартное отклонение 1. Значения переменных делятся на стандартное отклонение.
  • Кроме того, возможны преобразования самих расстояний, в частности, можно расстояния заменить их абсолютными значениями, это актуально для коэффициентов корреляции. Можно также все расстояния преобразовать так, чтобы они изменялись от 0 до 1.
    •

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

    Процесс агрегирования данных может быть представлен графически деревом объединения кластеров (Dendrogramm) либо "сосульковой" диаграммой (Icicle).(рис 5.2) Дендрограмма классификацииНо подробнее о процессе кластеризации можно узнать по протоколу объединения кластеров (Schedule).

    Пример иерархического кластерного анализа. Проведем кластерный анализ по полученным нами ранее факторам на агрегированном файле Курильского опроса:(рис 5.3) Классификация городов

    CLUSTER fac1_1 fac2_1 /METHOD BAVERAGE /MEASURE= SEUCLID /ID=name /PRINT SCHEDULE CLUSTER(3,5) /PLOT DENDROGRAM .

    В команде указаны переменные fac1_1 fac2_1 для кластеризации. По умолчанию расстояние между кластерами определяется по среднему расстоянию между объектами ( METHOD BAVERAGE ), а расстояние между объектами — как квадрат евклидова ( MEASURE= SEUCLID ). Кроме того, распечатывается протокол ( PRINT SCHEDULE ), в качестве переменных выводятся классификации из 3, 4, 5 кластеров ( CLUSTER(3,5) ) и строится дендрограмма ( PLOT DENDROGRAM ).

    Разрез дерева агрегирования (рис. 5.2) вертикальной чертой на четыре части дал два кластера, состоящих из уникальных по своим характеристикам городов Александровск-Сахалинский и Черемхово; кластер из 5 городов (Оха, Елизово, Южно-Сахалинск, Хабаровск, Курильск); еще один кластер из 14 городов составили последний кластер.

    Естественность такой классификации демонстрирует полученное поле рассеяния данных (рис.5.3).

    Протокол объединения кластеров
    Cluster CombinedCoefficientsStage Cluster First AppearsNext Stage
    StageCluster 1Cluster 2Cluster 1Cluster 2
    1 5 20 0.0115 0 0 2
    2 5 11 0.0175 1 0 3
    3 5 19 0.0464 2 0 11
    4 6 12 0.0510 0 0 8
    5 3 16 0.0549 0 0 9
    6 13 21 0.0808 0 0 10
    7 10 14 0.1082 0 0 14
    8 6 15 0.1349 4 0 11
    9 3 8 0.1538 5 0 13
    10 1 13 0.2818 0 6 12
    11 5 6 0.4560 3 8 13
    12 1 2 0.5768 10 0 16
    13 3 5 0.5861 9 11 16
    14 10 17 0.6130 7 0 17
    15 7 18 0.8098 0 0 17
    16 1 3 1.5406 12 13 18
    17 7 10 2.5726 15 14 19
    18 1 4 3.5613 16 0 19
    19 1 7 5.2217 18 17 20
    20 1 9 14.9146 19 0 0

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

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

    Быстрый кластерный анализ

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

    Здесь наиболее приемлем быстрый алгоритм, носящий название метода " k -средних". Он реализуется в пакете командой QUICK CLUSTER или командой меню k -means.

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

    Затем заново вычисляются центры этих кластеров, которыми после этого момента считаются покоординатные средние кластеров. После этого опять перераспределяются объекты. Вычисление центров и перераспределение объектов происходит до тех пор, пока не стабилизируются центры.

    Синтаксис команды:

    QUICK CLUSTER W3d1 TO W3D6/CRITERIA CLUSTERS(3) /MISSING=PAIRWISE /SAVE CLUSTER(SAVCLU) /PRINT ANOVA.

    За именем команды располагаются переменные, по которым происходит кластеризация. Параметр /CRITERIA CLUSTERS задает в скобках число кластеров. Подкомандой /SAVE CLUSTER можно сохранить полученную классификацию в виде переменной, имя которой дается в скобках. Подкоманда /PRINT ANOVA позволяет провести по каждой переменной одномерный дисперсионный анализ — сравнение средних в кластерах. Этот анализ имеет лишь описательное значение и позволяет определить переменные, которые не оказывают никакого влияния на классификацию.

    Команда использует только евклидово расстояние. При этом часть переменных может иметь неопределенные значения, расстояния до центров определяются по определенным значениям. Для использования такой возможности следует употребить подкоманду /MISSING=PAIRWISE.

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

    Для этого можно использовать команду DESCRIPTIVE. Напомним, что подкоманда /save в ней позволяет автоматически сохранить стандартизованные переменные. Кроме того, хорошие средства стандартизующих преобразований шкал дает команда RANK.

    В выдаче распечатываются центры кластеров (средние значения переменных кластеризации для каждого кластера), получаемые на каждой итерации алгоритма. Однако для нас полезна лишь часть выдачи, помеченная текстом "Final centres".

    Интерпретация кластеров осуществляется на основе сравнения средних значений, выдаваемых процедурой, а также исследования сохраненной переменной средствами статистического пакета.

    Пример использования QUICK CLUSTER. Для иллюстрации построим классификацию по предварительно отобранным данным городских семей по жилплощади и душевому доходу. Такая классификация может грубо, но наглядно показать различие семей по благосостоянию.

    В данных, полученных из обследования RLMS 1998 г. имеются переменные: c5 — жилплощадь, приходящаяся на семью, memb — число членов семьи, df14 — суммарные денежные доходы семьи.

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

    *вычисление логарифма жилплощади на члена семьи.

    compute lns=Ln(dc5/memb).

    *вычисление логарифма душевого дохода.

    compute lincome=ln(df14/memb).

    *стандартизация переменных.

    DESCRIPTIVES VARIABLES=lincome lns/SAVE .

    QUICK CLUSTER zlincome zlns /MISSING=PAIRWISE /CRITERIA= CLUSTER(3) /SAVE CLUSTER /PRINT ANOVA.

    На основании таблицы 7.5 центров классов интерпретация полученных кластеров следующая:

    Кластер 1 — зажиточные семьи, имеющие относительно большой доход и жилплощадь.

    Кластер 2 — семьи, проживающие в квартирах с небольшой площадью, но имеющие относительно высокий доход.

    Кластер 3 — семьи, имеющие низкий доход и ограниченные в жилплощади.

    Кластер 4 — семьи, имеющие несколько больший доход, чем в среднем, но ограниченные в жилплощади.

    Центры кластеров (Final Cluster Centers)
    Cluster
    1 2 3 4
    Zscore(LINCOME) 1.26 0.52 -1.08 -0.40
    Zscore(LNS) 1.35 -0.56 -0.86 0.58
    Дисперсионный анализ в методе k-средних (ANOVA, имееет только описательное значение)
    ClusterErrorFSig
    Mean Square Df Mean Square Df
    ZLINCOME Zscore(LINCOME) 513.006 3 .370 2440 1384.7 0
    ZLNS Zscore(LNS) 530.153 3 .363 2491 1461.6 0
    (рис 5.5) Классификация семей по душевому доходу Lincome и жилплощади на человека LNS (в логарифмических шкалах).

    Дисперсионный анализ (табл. 5.4) показал, что по обоим переменным различие кластеров существенно. Но о статистической значимости переменных говорить бессмысленно, поскольку гипотеза дисперсионного анализа — по сути, независимость групп и "зависимой" переменной, а в данном случае группы сформированы на основе значений "независимых" переменных.

    Полезно рассмотреть график рассеяния данных по кластерам (рис. 5.5). В нашем случае, пожалуй, не стоит говорить о выделении "сгущений" точек в признаковом пространстве, скорее, программа нашла разумные границы для описания типов, выделив их в непрерывном двумерном распределении.

    Кластерный анализ

    Кластерный анализ предназначен для разбиения множества объектов на заданное или неизвестное число классов на основании некоторого математического критерия качества классификации (cluster (англ.) — гроздь, пучок, скопление, группа элементов, характеризуемых каким-либо общим свойством). Критерий качества кластеризации в той или иной мере отражает следующие неформальные требования:

  • внутри групп объекты должны быть тесно связаны между собой;
  • объекты разных групп должны быть далеки друг от друга;
  • при прочих равных условиях распределения объектов по группам должны быть равномерными.
    •

    Требования 1) и 2) выражают стандартную концепцию компактности классов разбиения; требование 3) состоит в том, чтобы критерий не навязывал объединения отдельных групп объектов.

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

    Другой важной величиной в кластерном анализе является расстояние между целыми группами объектов. Приведем примеры наиболее распространенных расстояний и мер близости, характеризующих взаимное расположение отдельных групп объектов. Пусть wi — i -я группа (класс, кластер) объектов, Ni — число объектов, образующих группу wi, вектор $$\mu_i$$ — среднее арифметическое объектов, входящих в wi (другими словами, $$\mu_i$$ — "центр тяжести" i-й группы), a q ( wl, wm ) — расстояние между группами wl и wm.

    (рис 5.6) Различные способы определения расстояния между кластерами wl и wm: 1 — по центрам тяжести, 2 — по ближайшим объектам, 3 — по самым далеким объектам

    Расстояние ближайшего соседа есть расстояние между ближайшими объектами кластеров:$$q_{\min}(w_1,w_m)=\mathop{\min d(x_i,x_j)}\limits_{x_i*w_1, x_j*w_m}$$

    Расстояние дальнего соседа — расстояние между самыми дальними объектами кластеров:$$q_{\max}(w_1,w_m)=\mathop{\max d(x_i,x_j)}\limits_{x_i*w_1, x_j*w_m}$$

    Расстояние центров тяжести равно расстоянию между центральными точками кластеров:

    $$q(w_1,w_m)=d(\mu_1,\mu_m)$$

    Обобщенное (по Колмогорову) расстояние между классами, или обобщенное K -расстояние, вычисляется по формуле $$q_{\tau}^{(K)}(w_1,w_m)\left[\frac{1}{N_1 N_m} \sum\limits_{x_i*w_1} \sum\limits_{x_j*w_m} d^{\tau}(x_i,x_j)\right]^{\frac{1}{\tau}}$$

    В частности, при $$\tau \to \propto$$ и при $$\tau \to -\propto$$ имеем

    $$q_{\infty}^{(K)}(w_1,w_m)=q_{max}(w_1,w_m)\\q_{-\infty}^{(K)}(w_1,w_m)=q_{max}(w_1,w_m)$$

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

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

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

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

    Функционалы качества и конкретные алгоритмы автоматической классификации достаточно полно и подробно рассмотрены в специальной литературе. Эти функционалы и алгоритмы характеризуются различной трудоемкостью и подчас требуют ресурсов высокопроизводительных компьютеров. Разнообразные процедуры кластерного анализа входят в состав практически всех современных пакетов прикладных программ для статистической обработки многомерных данных.

    Иерархическое группирование

    (рис 5.7) Результаты работы иерархической агломеративной процедуры группирования объектов, представленные в виде дендрограммы

    Классификационные процедуры иерархического типа предназначены для получения наглядного представления о стратификационной структуре всей исследуемой совокупности объектов. Эти процедуры основаны на последовательном объединении кластеров (агломеративные процедуры) и на последовательном разбиении (дивизимные процедуры). Наибольшее распространение получили агломеративные процедуры. Рассмотрим последовательность операций в таких процедурах.

    На первом шаге все объекты считаются отдельными кластерами. Затем на каждом последующем шаге два ближайших кластера объединяются в один. Каждое объединение уменьшает число кластеров на один так, что в конце концов все объекты объединяются в один кластер. Наиболее подходящее разбиение выбирает чаще всего сам исследователь, которому предоставляется дендрограмма, отображающая результаты группирования объектов на всех шагах алгоритма (рис. 5.7). Могут одновременно также использоваться и математические критерии качества группирования.

    Различные варианты определения расстояния между кластерами дают различные варианты иерархических агломеративных процедур. Учитывая специфику подобных процедур, для задания расстояния между классами оказывается достаточным указать порядок пересчета расстояний между классом wl и классом w(m, n) являющимся объединением двух других классов wm и wn по расстояниям qmт = q(wm, wn) и qlт = q(wl, wn) между этими классами. В литературе предлагается следующая общая формула для вычисления расстояния между некоторым классом wl и классом w(m, n):

    $$q_{l(m,n)}q(w_1,w(m,n))=\alpha q_{lm}+\beta q_{ln} +\gamma q_{mn}+\delta |q_{lm}-q_{ln}|$$

    где $$\alpha ,\beta ,\gamma$$ и $$\delta$$ — числовые коэффициенты, определяющие нацеленность агломеративной процедуры на решение той или иной экстремальной задачи. В частности, полагая $$\alpha =\beta =-\delta =1/2$$ и $$\gamma =0$$, приходим к расстоянию, измеряемому по принципу ближайшего соседа. Если положить $$\alpha =\beta =\delta =1/2$$ и $$\gamma =0$$, то расстояние между двумя классами определится как расстояние между двумя самыми далекими объектами этих классов, то есть это будет расстояние дальнего соседа. И, наконец, выбор коэффициентов соотношения по формулам

    $$\alpha =\frac{N_m}{N_m+N_n},\beta =\frac{N_n}{N_m+N_n},\gamma = \delta =0$$

    приводит к расстоянию qcр между классами, вычисленному как среднее расстояние между всеми парами объектов, один из которых берется из одного класса, а другой из другого.

    Использование следующей модификации формулы

    $$q^2_{l(m,n)}=\frac{N_1+N_m}{N_l+N_m+N_n}q^2_{lm} + \frac{N_l+N_n}{N_l+N_m+N_n}q^2_{ln} - \frac{N_l}{N_l+N_m+N_n}q^2_{mn}$$

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

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^