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

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

КЕМЕРОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Математический факультет

Кафедра АИТК

Реферат на тему:

«Кластерный анализ и метод горной кластеризации»

студента 5 курса, М-063 группы

Баранова Семёна Фёдоровича

Специальность – 010501 –

«Прикладная математика и информатика»

Руководитель:

Р.Ю.Замараев

Кемерово 2010

Содержание

Цель работы

1. Происхождение метода анализа

2. Решаемая данным методом задача

3. Возможная область применения

4. Математическое описание метода

5. Пример использования метода на реальных данных

Заключение

Используемая литература

Цель работы

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

Требования к работе:

1. Самостоятельная работа оформляется в виде реферата;

2. Работа должна содержать следующие обязательные пункты:

· происхождение метода анализа (автор, базовый метод);

· решаемая данным методом задача (тип снимаемой неопределенности);

· возможная область применения в различных предметных областях;

· пример использования метода на реальных данных (выдаются преподавателем);

3. Пример реализуется в удобном математическом пакете (Matlab, Mathcad, Mathematica) в виде макроса или рабочего листа с иллюстрациями;

4. Работа сдается в печатном и электронном виде.

1 Происхождение метода анализа

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

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

Метод горной кластеризации предложен Р. Ягером и Д. Филевым в 1993 г. Кластеризация по горному методу не является нечеткой, однако, ее часто используют при синтезе нечетких правил из данных. Особенностью метода является отсутствие необходимости задания количества кластеров до начала работы алгоритма.

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

2 Решаемая данным методом задача

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

3 Возможная область применения в различных предметных областях

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

4 Математическое описание метода

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

На втором шаге алгоритма рассчитывается потенциал центров кластеров по следующей формуле:

, ,

где - потенциальный центр h-го кластера;

- положительная константа

- расстояние между потенциальным центром кластера () и объектом кластеризации (). В евклидовом пространстве это расстояние рассчитывается по формуле:

.

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

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

,

где - потенциал на 1-й итерации;

- потенциал на 2-й итерации;

- центр первого найденного кластера:

;

- положительная константа.

Центр второго кластера определяется по максимальному значению обновленного потенциала:

.

Затем снова пересчитывается значение потенциалов:

.

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

5 Пример использования метода на реальных данных

Для реализации метода горной кластеризации на реальных данных по показателям 3(Atomic-radius-emp), 7(Electron-affinity) и 14(Electronegativity-AllredRochow) автором был использован математический пакет Matlab версии 7.10.0(R2010a), в который были импортированы данные из таблицы MSExcel с помощью надстройки SpreadsheetLinkEX 3.1.1. Вызов встроенной в Matlab функции кластеризации subclust() и создания фигуры для отображения получившихся результатов записаны в скрипте Cluster.m:

Результаты:

В командном окне Matlab выводятся координаты трех кластеров и их радиусы:

centers =

155.0000 41.1000 1.2200

135.0000 118.4000 1.7500

220.0000 48.4000 0.9100

sigmas =

27.5772 37.0170 0.5834

Заключение

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

Используемая литература

1. Гайдышев И. Анализ и обработка данных: специальный справочник – СПб: Питер, 2001.

2. www.exponenta.ru