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

Суть иерархической кластеризации состоит в последовательном объединении меньших кластеров в большие или разделении больших кластеров на меньшие.

Иерархические агломеративные методы (Agglomerative Nesting, AGNES)

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

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

Иерархические дивизимные (делимые) методы (DIvisive ANAlysis, DIANA)

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

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

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

Преимуществом иерархических методов кластеризации является их наглядность.

Иерархические алгоритмы связаны с построением дендрограмм (от греческого dendron - "дерево"), которые являются результатом иерархического кластерного анализа. Дендрограмма описывает близость отдельных точек и кластеров друг к другу, представляет в графическом виде последовательность объединения (разделения) кластеров.

Дендрограмма (dendrogram) - древовидная диаграмма, содержащая n уровней, каждый из которых соответствует одному из шагов процесса последовательного укрупнения кластеров.

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

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

Существует много способов построения дендограмм. В дендограмме объекты могут располагаться вертикально или горизонтально.

25))Технология выполнения метода к- средних. Описания графика средних

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

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

Чтобы использовать кластеризацию методом К-средних, выберите Classify > K-Means Cluster из списка Analyze в главном меню редактора данных. Появится окно.

Перенесите переменные, которые вы хотите использовать в своем анализе, из левой части списка в список Variables (Переменные). Аналогично, выберите столбец для использования в качестве уникального идентификатора записи и поместите его в поле Label Cases by (Помечать случаи меткой…). В случае классификации клиентов это неизменный номер клиента.

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

Далее, отрегулируйте количество кластеров, которое вы хотели бы увидеть в итоге.

Если вы удовлетворены выбором, нажмите кнопку ОК. Позднее можно будет поэкспериментировать с кнопками Iterate (Повторение) иOptions (Параметры настройки). С их помощью можно влиять на результат, но нужно хорошо знать алгоритм и возможные последствия изменения этих настроек. Убедитесь, что в поле Method (Метод) выбран параметр Iterate and classify (Повторение и классификация).

В диалоговом окне Cluster Centers (Центры кластеров) установите флажок Write final (Запись конечного результата). Выберите вариант Data file (Файл данных); затем нажмите кнопку File и в появившемся обозревателе файлов присвойте файлу имя. Запомните, где находится этот файл.

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

Взглянем, например, на линию для кластера экономичный седан (Кластер 1) и сравним её с кластером роскошный седан (Кластер 2) на графике ниже. Можно заметить, что и в самом деле, автомобили в последнем классе:

(1) Являются более дорогими,

(2) Имеют меньше время разгона (вероятно из-за большего веса),

(3) Имеют приблизительно тот самый тормозной путь,

(4) Являются одинаковыми с точки зрения управляемости, и

(5) Имеют меньший расход топлива.

Расстояния между кластерами. Другой полезный результат проверки - евклидовы расстояния между кластерами (нажмите на кнопку Средние кластеров и евклидовы расстояния). Эти расстояния (евклидовы и их квадраты) вычисляются по средним каждой переменной в кластере.

26))Проверка статистической значимости построенных кластеров

Кластерный анализ не только предоставля­ет существенно меньшие возможности для кластеризации переменных (например, отсутствие возможности сохранять групповые рейтинги) по сравнению с фактор­ным анализом, но и выдает гораздо менее наглядные результаты. В нашем случае, если кластеры 2, 3 и 4 еще поддаются логической интерпретации1, то кластер 1 содержит совершенно разные по смыслу утверждения. В данной ситуации можно либо попытаться описать кластер 1 как есть, либо перестроить статистическую модель с другим числом кластеров. В последнем случае для поиска оптимального числа кластеров, поддающихся логическому описанию, можно воспользоваться параметром Range of solutions в диалоговом окне Statistics (см. рис. 5.57), указав в соответствующих полях минимальное и максимальное число кластеров (в нашем случае 4 и 6 соответственно). В такой ситуации SPSS перестроит таблицу Cluster Membership для каждого числа кластеров. Задача аналитика в данном случае — по­пытаться подобрать такую классификационную модель, при которой все кластеры будут интерпретироваться однозначно. С целью демонстрации возможностей про­цедуры кластерного анализа для кластеризации переменных мы не будем пере­страивать кластерную модель, а ограничимся лишь сказанным выше.

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

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

Из анализа внутрикластерного стандартного отклонения видно, что разброс характеристик внутри первой группы больше для ОЭ-1, для второй по ОЭ-1 и ОЭ-2, для третьей по ОЭ-2 (кластеры имеют вытянутую форму по этим осям). Из чего можно сделать вывод о нестабильности результатов обу­чающихся перечисленных групп по указанным обучающим элементам.

Проверка статистической значимости различия между средними значе­ниями каждого кластера с использованием t-критерия Стьюдента, подтвер­дила гипотезу о различии между средними для уровня значимости р=0,05. Это, а также то, что расстояние объектов до центра каждого кластера невели­ко относительно расстояний между центрами кластеров и примерно равное, позволяет сделать вывод, что кластеры являются компактными скоплениями объектов, а данное разбиение устойчиво и отражает внутреннюю структуру данных.

Оценка значимости

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

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

При разработке алгоритма оценки значимости необходимо принять два решения:

– как генерировать случайную выборку с однокластерной структурой (по построению), которая была бы по остальным параметрам сравнима с исходной выборкой?;

– как измерять значимость гипотезы однокластерности, располагая значениями критерия качества разделения (при k кластерах) на исходных данных и для всего множества случайных выборок?

Рассмотрим эти проблемы по порядку.

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

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

Теперь перейдем к вопросу измерения значимости гипотезы однокластерности. Поскольку критерием качества кластеризации была выбрана доля остаточной дисперсии, которая принимает значения от нуля до единицы, то естественно будет аппроксимировать распределение значений этого критерия в серии случайных экспериментов Бэта-распределе­нием, которое работает для случайных величин, имеющих ограниченную с обоих сторон область допустимых значений:

(1)

Параметры a и b Бэта-распределения легко определить по выборочному среднему M и дисперсии D:

	(2)
	(3)

Получив оценки параметров Бэта-распределения, мы можем вычислить значимость гипотезы однокластерности при любом значении x(k) – доли остаточной диперсии на k кластерах. Значимость вычисляется как интеграл Бэта-распределения в пределах от нуля до остаточной дисперсии d(k):

27)) Дисперсионный анализ результатов метода к – средних

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

Дисперсионный анализ, в котором проверяется влияние одного фактора, называется однофакторным (одномерный анализ). При изучении влияния более чем одного фактора используют многофакторный дисперсионный анализ (многомерный анализ).

Факторные признаки — это те признаки, которые влияют на изучаемое явление.

Результативные признаки — это те признаки, которые изменяются под влиянием факторных признаков.

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

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

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

Идея дисперсионного анализа заключается в разложении общей дисперсии случайной величины на независимые случайные слагаемые, каждое из которых характеризует влияние того или иного фактора или их взаимодействия. Последующее сравнение этих дисперсий позволяет оценить существенность влияния фактора на исследуемую величину. Таким образом, задача дисперсионного анализа состоит в том, чтобы выявить ту часть общей изменчивости признака, которая обусловлена воздействием учитываемых факторов, и оценить достоверность делаемого вывода. Пусть, например, А – исследуемая величина, – среднее значение величины А, учитываемые факторы мы обозначим буквой х, неучитываемые – z, а все факторы вместе – буквой у (или припиской этих букв к соответствующим символам). Неучитываемые факторы составляют «шум» – помехи, мешающие выделить степень влияния учитываемых факторов. Отклонение А от при действии факторов х и z можно представить в виде суммы

(А– )=У=Х+Z,

где Х – отклонение, вызываемое фактором х, Z – отклонение, вызываемое фактором z, У – отклонение, вызываемое всеми факторами. Кроме того, предположим, что Х,У,Z – являются независимыми случайными величинами, обозначим дисперсии через s²_Х, s²_У, s²_Z, s²_А. Тогда имеет место равенство

s²_А=s²_Х+s²_Z. (4.54)

Сравнивая дисперсии, можно установить степень влияния факторов х и z на величину А, т.е. степень влияния учтенных и неучтенных факторов.

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

28)))= Введение в дискриминантный анализ. Проблема классификации

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

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

Задачи дискриминантного анализа можно разделить на три типа.

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

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

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

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

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

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

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

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

Xi= (xi1,xi2, ...xip)T , i= 1, 2, ... ,n, к одному из классов, необходимо четко определить понятие класса. Мы будем понимать под «классом» генеральную совокупность, описываемую унимодальной плотностью f(x) (или унимодальным полигоном вероятностей в случае дискретных признаков X ). Дискриминантный анализ используется для принятия решения о том, какие переменные различают

(дискриминируют, классифицируют) две или более возникающие совокупности (классы