Реферат по кластерному анализу

Обновлено: 05.07.2024

История "кластерного анализа" и его терминология. Расстояние между объектами (метрика). Плотность и локальность кластеров. Особенности иерархических агломеративных методов и итерационных методов кластеризации. Устойчивость и качество кластеризации.

Рубрика	Экономико-математическое моделирование
Вид	реферат
Язык	русский
Дата добавления	07.11.2010
Размер файла	619,8 K

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

СОДЕРЖАНИЕ

2.1Объект и признак

2.2Расстояние между объектами (метрика)

2.3Плотность и локальность кластеров

2.4Расстояние между кластерами

3. Методы группировки

3.1Особенности иерархических агломеративных методов

3.2Особенности итерационных методов кластеризации

4. Кластеризация признаков

5. Устойчивость и качество кластеризации

Список используемой литературы

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

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

В 1925 г. советский гидробиолог П.В. Терентьев разработал так называемый "метод корреляционных плеяд", предназначенный для группировки коррелирующих признаков. Этот метод дал толчок развитию методов группировки с помощью графов. Термин "кластерный анализ" впервые был предложен Трионом. Слово "cluster" переводится с английского языка как "гроздь, кисть, пучок, группа". По этой причине первоначальное время этот вид анализа называли "гроздевым анализом". В начале 50-х годов появились публикации Р.Люиса, Е.Фикса и Дж. Ходжеса по иерархическим алгоритмам кластерного анализа. Заметный толчок развитие работ по кластерному анализу дали работы Р.Розенблатта по распознающему устройству (персептрону), положившие начало развитию теории "распознавания образов без учителя".

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

В эти же годы было предложено множество алгоритмов таких авторов, как Дж. Мак-Кин, Г. Болл и Д. Холл по методам k-средних; Г. Ланса и У. Уильямса, Н. Джардайна и др. - по иерархическим методам. Заметный вклад в развитие методов кластерного анализа внесли и отечественные ученые - Э.М.Браверман, А.А.Дорофеюк, И.Б.Мучник, Л.А,Растригин, Ю.И.Журавлев, И.И.Елисеева и др. В частности, в 60-70 гг. большой популярностью пользовались многочисленные алгоритмы разработанные новосибирскими математиками Н.Г.Загоруйко, В.Н.Елкиной и Г.С.Лбовым. Это такие широко известные алгоритмы, как FOREL, BIGFOR, KRAB, NTTP, DRET, TRF и др. На основе этих пакетов был создан специализированный пакет программ ОТЭКС. Не менее интересные программные продукты ППСА и Класс-Мастер были созданы московскими математиками С.А.Айвазяном, И.С.Енюковым и Б.Г.Миркиным.

В том или ином объеме методы кластерного анализа имеются в большинстве наиболее известных отечественных и зарубежных статистических пакетах: SIGAMD, DataScope, STADIA, СОМИ, ПНП-БИМ, СОРРА-2, СИТО, SAS, SPSS, STATISTICA, BMDP, STATGRAPHICS, GENSTAT, S-PLUS и т.д. Конечно, спустя 10 лет после выхода этого обзора, изменилось достаточно много, появились новые версии многих статистических программ, появились и абсолютно новые программы, использующие как новые алгоритмы, так и сильно возросшие мощности вычислительной техники. Однако большинство статистических пакетов используют алгоритмы предложенные и разработанные в 60-70 гг.

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

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

2 ТЕРМИНОЛОГИЯ

2.1 ОБЪЕКТ И ПРИЗНАК

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

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

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

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

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

2.2 РАССТОЯНИЕ МЕЖДУ ОБЪЕКТАМИ (МЕТРИКА)

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

1. d_ij > 0 (неотрицательность расстояния)

3. d_ij + d_jk > d_ik (неравенство треугольника)

4. Если d_ij не равно 0, то i не равно j (различимость нетождественных объектов)

5. Если d_ij = 0, то i = j (неразличимость тождественных объектов)

Меру близости (сходства) объектов удобно представить как обратную величину от расстояния между объектами. В многочисленных изданиях посвященных кластерному анализу описано более 50 различных способов вычисления расстояния между объектами. Кроме термина "расстояние" в литературе часто встречается и другой термин - "метрика", который подразумевает метод вычисления того или иного конкретного расстояния. Наиболее доступно для восприятия и понимания в случае количественных признаков является так называемое "евклидово расстояние" или "евклидова метрика". Формула для вычисления такого расстояния:

В данной формуле использованы следующие обозначения:

· d_ij - расстояние между i-тым и j-тым объектами;

· x_ik - численное значение k-той переменной для i-того объекта;

· x_jk - численное значение k-той переменной для j-того объекта;

· v - количество переменных, которыми описываются объекты.

Таким образом, для случая v=2, когда мы имеем всего два количественных признака, расстояние d_ij будет равно длине гипотенузы прямоугольного треугольника, которая соединяет собой две точки в прямоугольной системе координат. Эти две точки будут отвечать i-тому и j-тому наблюдениям выборки. Нередко вместо обычного евклидового расстояния используют его квадрат d 2 _ij. Кроме того, в ряде случаев используется "взвешенное" евклидово расстояние, при вычислении которого для отдельных слагаемых используются весовые коэффициенты. Для иллюстрации понятия евклидовой метрики используем простой обучающий пример. Матрица данных, приведенная ниже в таблице, состоит из 5 наблюдений и двух переменных.

Содержание:
1. Введение. Понятие метода кластерного анализа.
2. Описание методики применения кластерного анализа. Контрольный пример решения задач.
3. Решение задач для контрольной работы.
4. Список используемой литературы

1. Введение. Понятие метода кластерного анализа.

2. Описание методики применения кластерного анализа. Контрольный пример решения задач.

3. Решение задач для контрольной работы.

4. Список используемой литературы

Кластерный анализ – это совокупность методов, позволяющих классифицировать многомерные наблюдения, каждое из которых описывается набором признаков (параметров) Х1, Х2,…,Хк.

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

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

Методы кластерного анализа позволяют решать следующие задачи:

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

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

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

2. Описание методики применения кластерного анализа. Контрольный пример решения задач.

Кластерный анализ позволяет из n объектов, характеризуемых k признаками, сформировать разбивку на однородные группы (кластеры). Однородность объектов определяется по расстоянию p(xi xj), где xi = (xi1, …., xik) и xj= (xj1,…,xjk) - векторы, составленные из значений k признаков i-го и j-го объектов соответственно.

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

p(xi , xj) = √ ∑(x1m-xjm) 2 (1)*

Читайте также: