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

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РФ

ФГБОУ ВО «ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ СЕВЕРНОГО ЗАУРАЛЬЯ»

АГРОТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ

КАФЕДРА ЭКОЛОГИИ И РАЦИОНАЛЬНОГО ПРИРОДОПОЛЬЗОВАНИЯ

Реферат

По дисциплине: Математическое моделирование процессов в компонентах природы

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

Руководитель: Малышкин Николай Георгиевич

к.с.н., доцент

Исполнитель: Коваленко Евгения Валерьевна

Группа М-ПР 11 очн.

Тюмень, 2018 г.

Содержание

кластеризация кластерный метод анализ

Введение

1. Задачи и условия

2. Анализ и интерпретация его результатов

3. Типология задач кластеризации

3.1 Типы входных данных

3.2 Цели кластеризации

3.3 Методы кластеризации

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

5. Применение

5.1 В биологии

5.2 В информатике

Заключение

Литература

Введение

Кластерный анализ (англ. Data clustering) -- задача разбиения заданной выборки объектов (ситуаций) на подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались. Задача кластеризации относится к статистической обработке, а также к широкому классу задач обучения без учителя. Кластерный анализ -- это многомерная статистическая процедура, выполняющая сбор данных, содержащих информацию о выборке объектов, и затем упорядочивающая объекты в сравнительно однородные группы (кластеры) (Q-кластеризация, или Q-техника, собственно кластерный анализ). Кластер -- группа элементов, характеризуемых общим свойством, главная цель кластерного анализа -- нахождение групп схожих объектов в выборке (примечание 1). Спектр применений кластерного анализа очень широк: его используют в археологии, медицине, психологии, химии, биологии, государственном управлении, филологии, антропологии, маркетинге, социологии и других дисциплинах. «Тематика исследований варьирует от анализа морфологии мумифицированных грызунов в Новой Гвинее до изучения результатов голосования сенаторов США, от анализа поведенческих функций замороженных тараканов при их размораживании до исследования географического распределения некоторых видов лишая в Саскачеване» (примечание 1). Однако универсальность применения привела к появлению большого количества несовместимых терминов, методов и подходов, затрудняющих однозначное использование и непротиворечивую интерпретацию кластерного анализа.

1. Задачи и условия

Кластерный анализ выполняет следующие основные задачи:

· Разработка типологии или классификации.

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

· Порождение гипотез на основе исследования данных.

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

Независимо от предмета изучения применение кластерного анализа предполагает следующие этапы:

§ Отбор выборки для кластеризации.

§ Определение множества переменных, по которым будут оцениваться объекты в выборке.

§ Вычисление значений той или иной меры сходства между объектами.

§ Применение метода кластерного анализа для создания групп сходных объектов.

§ Проверка достоверности результатов кластерного решения.

Кластерный анализ предъявляет следующие требования к данным:

· показатели не должны коррелировать между собой

· показатели должны быть безразмерными

· распределение показателей должно быть близко к нормальному

· показатели должны отвечать требованию «устойчивости», под которой понимается отсутствие влияния на их значения случайных факторов

· выборка должна быть однородна, не содержать «выбросов».

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

2. Анализ и интерпретация его результатов

При анализе результатов социологических исследований рекомендуется осуществлять анализ методами иерархического агломеративного семейства, а именно методом Уорда, при котором внутри кластеров оптимизируется минимальная дисперсия, в итоге создаются кластеры приблизительно равных размеров. Метод Уорда наиболее удачен для анализа социологических данных. В качестве меры различия лучше квадратичное евклидово расстояние, которое способствует увеличению контрастности кластеров. Главным итогом иерархического кластерного анализа является дендрограмма или «сосульчатая диаграмма». При её интерпретации исследователи сталкиваются с проблемой того же рода, что и толкование результатов факторного анализа -- отсутствием однозначных критериев выделения кластеров. В качестве главных рекомендуется использовать два способа -- визуальный анализ дендрограммы и сравнение результатов кластеризации, выполненной различными методами. Визуальный анализ дендрограммы предполагает «обрезание» дерева на оптимальном уровне сходства элементов выборки. «Виноградную ветвь» (терминология Олдендерфера М. С. и Блэшфилда Р. К.) целесообразно «обрезать» на отметке 5 шкалы Rescaled Distance Cluster Combine, таким образом будет достигнут 80 % уровень сходства. Если выделение кластеров по этой метке затруднено (на ней происходит слияние нескольких мелких кластеров в один крупный), то можно выбрать другую метку. Такая методика предлагается Олдендерфером и Блэшфилдом.

Теперь возникает вопрос устойчивости принятого кластерного решения. По сути, проверка устойчивости кластеризации сводится к проверке её достоверности. Здесь существует эмпирическое правило -- устойчивая типология сохраняется при изменении методов кластеризации. Результаты иерархического кластерного анализа можно проверять итеративным кластерным анализом по методу k-средних. Если сравниваемые классификации групп респондентов имеют долю совпадений более 70 % (более 2/3 совпадений), то кластерное решение принимается.

Проверить адекватность решения, не прибегая к помощи другого вида анализа, нельзя. По крайней мере, в теоретическом плане эта проблема не решена. В классической работе Олдендерфера и Блэшфилда «Кластерный анализ» подробно рассматриваются и в итоге отвергаются дополнительные пять методов проверки устойчивости: 1) кофенетическая корреляция -- не рекомендуется и ограниченна в использовании; 2) тесты значимости (дисперсионный анализ) -- всегда дают значимый результат; 3) методика повторных (случайных) выборок, что, тем не менее, не доказывает обоснованность решения; 4) тесты значимости для внешних признаков пригодны только для повторных измерений; 5) методы Монте-Карло очень сложны и доступны только опытным математикам.

3. Типология задач кластеризации

3.1 Типы входных данных

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

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

3.2 Цели кластеризации

· Понимание данных путём выявления кластерной структуры. Разбиение выборки на группы схожих объектов позволяет упростить дальнейшую обработку данных и принятия решений, применяя к каждому кластеру свой метод анализа (стратегия «разделяй и властвуй»).

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

· Обнаружение новизны (англ. novelty detection). Выделяются нетипичные объекты, которые не удаётся присоединить ни к одному из кластеров.

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

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

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

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

3.3 Методы кластеризации

· K-средних (K-means)

· Графовые алгоритмы кластеризации

· Статистические алгоритмы кластеризации

· Алгоритмы семейства FOREL

· Иерархическая кластеризация или таксономия

· Нейронная сеть Кохонена

· Ансамбль кластеризаторов

· Алгоритмы семейства КRAB

· EM-алгоритм

· Алгоритм, основанный на методе просеивания

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

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

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

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

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

· не существует однозначно наилучшего критерия качества кластеризации. Известен целый ряд эвристических критериев, а также ряд алгоритмов, не имеющих чётко выраженного критерия, но осуществляющих достаточно разумную кластеризацию «по построению». Все они могут давать разные результаты.

· число кластеров, как правило, неизвестно заранее и устанавливается в соответствии с некоторым субъективным критерием.

· результат кластеризации существенно зависит от метрики, выбор которой, как правило, также субъективен и определяется экспертом.

5. Применение

5.1 В биологии

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

5.2 В информатике

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

Clusty[1] -- кластеризующая поисковая машина компании Vivнsimo

Nigma -- российская поисковая система с автоматической кластеризацией результатов

Quintura -- визуальная кластеризация в виде облака ключевых слов

Сегментация изображений (image segmentation): Кластеризация может быть использована для разбиения цифрового изображения на отдельные области с целью обнаружения границ (edge detection) или распознавания объектов.

Интеллектуальный анализ данных (data mining): Кластеризация в Data Mining приобретает ценность тогда, когда она выступает одним из этапов анализа данных, построения законченного аналитического решения. Аналитику часто легче выделить группы схожих объектов, изучить их особенности и построить для каждой группы отдельную модель, чем создавать одну общую модель для всех данных. Таким приемом постоянно пользуются в маркетинге, выделяя группы клиентов, покупателей, товаров и разрабатывая для каждой из них отдельную стратегию.

Заключение

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

Литература

1. Бухштабер В.М. Прикладная статистика: классификация и снижение размерности /1. Айвазян С. А., В.М. Бухштабер, И.С. Енюков, Л.Д. Мешалкин. Финансы и статистика, 1989.

2. Журавлев, Ю.И. Распознавание. Математические методы. Программная система. Практические применения /Ю.И. Журавлев, В.В. Рязанов, О.В. Сенько. Фазис, 2006.

3. Хайдуков Д. С. Применение кластерного анализа в государственном управлении// Философия математики: актуальные проблемы. М.: МАКС Пресс, 2009.

4. Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознаванию. Киев: Наукова думка, 2004.

5. Шуметов В. Г. Шуметова Л. В. «Кластерный анализ: подход с применением ЭВМ». ОрелГТУ, Орел, 2000. 118 с.

6. Электронный учебник по статистике. Москва, StatSoft. WEB: www.statsoft.ru/home/textbook/default.htm.

Размещено на Allbest.ru