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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 19:52, 24 декабря 2016.

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

Введение

Историческая справка

Первое применение кластерный анализ нашел в социологии. Название кластерный анализ происходит от английского слова cluster – гроздь, скопление. Впервые в 1939 был определен предмет кластерного анализа и сделано его описание исследователем Трионом (Tryon). Главное назначение кластерного анализа – разбиение множества исследуемых объектов и признаков на однородные в соответствующем понимании группы или кластеры. Это означает, что решается задача классификации данных и выявления соответствующей структуры в ней. Методы кластерного анализа можно применять в самых различных случаях, даже в тех случаях, когда речь идет о простой группировке, в которой все сводится к образованию групп по количественному сходству.

Достоинства

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

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

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

Недостатки

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

Задачи и решения

В кластерном анализе считается, что:

  1. выбранные характеристики допускают в принципе желательное разбиение на кластеры;
  2. единицы измерения (масштаб) выбраны правильно.

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

Задача кластерного анализа

Задача кластерного анализа заключается в том, чтобы на основании данных, содержащихся во множестве Х, разбить множество объектов G на m (m – целое) кластеров (подмножеств) Q1,Q2 ,…,Qm , так, чтобы каждый объект G j принадлежал одному и только одному подмножеству разбиения. А объекты, принадлежащие одному и тому же кластеру, были сходными, в то время как объекты, принадлежащие разным кластерам, были разнородными.

Решение задачи кластерного анализа

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

где - представляет собой измерения j-го объекта

Математические характеристики кластера

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

Неоднозначность задачи кластерного анализа

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

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

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

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

Формальное описание задач кластеризации

Дано множество объектов данных I, каждый из которых представлен набором атрибутов. Требуется построить множество кластеров C и отображение F множества I на множество C, т.е. F: I → C. Отображение F задает модель данных, являющуюся решением задачи. Множество I определим следующим образом:

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

Каждая переменная может принимать значения из некоторого множества:

Задача кластеризации состоит в построении множества:

- кластер, содержащий похожие друг на друга объекты из множества I:

где σ - величина, определяющая меру близости для включения объектов в один кластер; - мера близости между объектами, называемая расстоянием.

Расстояние

Неотрицательное значение называется расстоянием между элементами и , если выполняются следующие условия:

  1. , для всех и
  2. , тогда и только тогда, когда .
  3. .
  4. . Если расстояние меньше некоторого значения σ, то говорят, что элементы близки и помещаются в один кластер. В противном случае говорят, что элементы отличны друг от друга и их помещают в разные кластеры.

Алгоритмы (общее)

Большинство популярных алгоритмов, решающих задачу кластеризации, используют в качестве формата входных данных матрицу отличия D. Строки и столбцы матрицы соответствуют элементам множества I. Элементами матрицы являются значения в строке j и столбце p. Очевидно, что на главной диагонали значения будут равны нулю:

Решение задачи кластеризации принципиально неоднозначно, и тому есть несколько причин:

  1. Не существует однозначно наилучшего критерия качества кластеризации. Известен целый ряд эвристических критериев, а также ряд алгоритмов, не имеющих чётко выраженного критерия, но осуществляющих достаточно разумную кластеризацию ”по построению“. Все они могут давать разные результаты.
  2. Число кластеров, как правило, неизвестно заранее и устанавливается в соответствии с некоторым субъективным критерием.
  3. Результат кластеризации существенно зависит от метрики, выбор которой, как правило, также субъективен и определяется экспертом.

Меры близости

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

Признаки

В таблице наличие и отсутствие признака для объекта 1 и объекта 2 обозначаются 1 и 0, соответственно; a - число случаев, когда у обоих объектов присутствует признак; d - число случаев, когда признак отсутствует у объектов; b и c - когда признак есть у одного объекта и его нет у другого.

Меры расстояния

  • Бинарное евклидово расстояние имеет минимальное значение - 0, максимальное - не определено. Вычисляется по формуле:
  • Если необходимо придать большие веса более отдаленным друг от друга объектам, используется квадрат бинарного евклидова расстояния:
  • Различие размера:
  • Различие палитры:
  • Бинарная форма различия:
  • Вариация:
  • Бинарная неметрическая мера различия Ланса и Вильямса:

Меры сходства

Простой коэффициент совстречаемости имеет вид

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

Коэффициент Жаккара, определенный следующим образом

не учитывает одновременного отсутствия признака при вычислении сходства (клетка не d рассматривается). Он изменяется от 0 до 1. В противоположность коэффициенту совстречаимости коэффициент Жаккара принимает в расчет лишь те признаки, которые характерны хотя бы для одного из объектов.

Мера сходства Рассела и Рао, определенная как бинарное скалярное произведение, вычисляется по формуле:

Мера сходства Дайса:

Мера сходства Снита и Сокала (1):

Мера сходства Снита и Сокала (2):

Мера сходства Снита и Сокала (3):

Мера сходства Роджерса и Танимато:

Мера сходства Кулсински (1):

Вероятностные меры сходства

Вероятностные меры пригодны лишь для бинарных данных.

Мера сходства Кулсински (2), принимающая значения от 0 до 1, вычисляется как:

Мера сходства Снита и Сокала (4), принимающая значения от 0 до 1, определяется по формуле:

Мера сходства Хаманна, определенная на интервал [-1; +1], имеет вид:

Меры предсказуемости

Коэффициент Лямбда Гудмана и Крускала дает оценку предсказуемости состояния характеристик на один объект (наличие или отсутствие) заданного состояния на другой объект. Лямбда изменяется от 0 до 1 и вычисляется по формуле:

Коэффициент D Андерберга вычисляет уменьшение ошибки подобия, когда один объект применяется для прогнозирования другого объекта. D изменяется от 0 до 1 и определяется как:

Коэффициент Q Юла:

Этот коэффициент равен нулю, если признаки независимы и может принимать значение +1, только когда bc = 0, т.е. в случае полной связности, а значение −1, только когда ad = 0, т.е. в случае полной отрицательной связности.

Коэффициент Y Юла изменяется от -1 до 1 и вычисляется по формуле:

Другие бинарные меры

Коэффициент Охиай:

Мера сходства Снита и Сокала (5):

Корреляция четырех точек (аналог коэффициента Пирсона):

Дисперсия меры сходства:

Измерение близости объектов

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

Отметим основные трудности, возникающие при этом: неоднозначность выбора способа нормировки и определения расстояния между объектами. Рассмотрим результаты небольшого обследования. Студенты группы записывают свои данные (вес, рост), оформляют в таблицу и строят по ним корреляционное поле. Масштабы по осям выбираются произвольно (рис.1.1).

Рис. 1.1

На рис.1.1а выделяются классы A – девушки, B – юноши. На рис. 1.1b выделяются классы A1 (юноши и девушки) и B1(часть юношей). Класс юношей C (пунктирная линия) на рис. 1.1б не выделит, поскольку расстояния между ближайшими объектами классов A1 и B1 существенно больше, чем внутренние расстояния в A1, юноши из A почти никакими алгоритмами к B1 не присоединяются.

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

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

Расстоянием (метрикой) между объектами в пространстве параметров называется такая величина , которая удовлетворяет аксиомам:

A1.
A2.
A3.

Мерой близости (сходства) обычно называется величина , имеющая предел и возрастающая с возрастанием близости объектов.

B1. непрерывна
B2.
B3.

Существует возможность простого перехода от расстояний к мерам близости: .

Характеристики близости объектов

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

Способы определения близости

Евклидово расстояние является самой популярной метрикой в кластерном анализе. Оно попросту является геометрическим расстоянием в многомерном пространстве. Геометрически оно лучше всего объединяет объекты в шарообразных скоплениях.

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

Обобщенное степенное расстояние представляет только математический интерес как универсальная метрика.

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

Манхэттенское расстояние (расстояние городских кварталов), также называемое "хэмминговым" или "сити-блок" расстоянием.

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

Процент несогласия. Это расстояние вычисляется, если данные являются категориальными.

Литература

  1. Мандель И. Д. Кластерный анализ. — М.: Финансы и статистика, 1988.
  2. Tryon R.C. Cluster analysis. — London: Ann Arbor Edwards Bros, 1939.
  3. Олдендерфер М. С., Блэшфилд Р. К. Кластерный анализ / Факторный, дискриминантный и кластерный анализ: пер. с англ.; Под. ред. И. С. Енюкова. — М.: Финансы и статистика, 1989
  4. Дюран Б., Оделл П. Кластерный анализ. — М.: Статистика, 1977