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

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

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

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

Использование кластерного анализа «…от анализа морфологии мумифицированных грызунов в Новой Гвинее до изучения результатов голосования сенаторов США, от анализа поведенческих функций замороженных тараканов при их размораживании до исследования географического распределения некоторых видов лишая в Саскачеване»

Примеры кластерного анализа

Практическая ценность кластерного анализа группировка объектов не только по одному параметру, но и по целому набору признаков; сокращение, сжатие больших объёмов информации в хранилищах и базах данных; Data Mining.

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

Дендрограмма последовательность разбиений, в которой каждое разбиение вложено в последующее разбиение в последовательности.

Формализация задачи кластеризации Неотрицательная, вещественнозначная функция называется функцией расстояния (метрикой), если:метрикой для всех X i и X j ; тогда и только тогда, когда X i =X j ; выполняется неравенство треугольника,где X i, X j, X k – любые 3 объекта. x2x2 x1x1 XjXj XiXi x3x3 1-й кластер (класс, таксон) 2-й кластер (X i, X j )

Функции расстояния евклидова метрика хеммингово расстояние

Алгоритм кластеризации 0 0 0

Алгоритм построения минимального остовного дерева (МОД) Шаг 0. [Инициализация] Построение матрицы расстояний (близости) R по результатам измерений n объектов, представленным матрицей данных размером p×n

Алгоритм построения минимального остовного дерева (МОД) Шаг 1. [Построение минимального остовного дерева] C использованием матрицы R осуществляется построение минимального остовного дерева T. Для построения минимального остовного дерева предлагается воспользоваться алгоритмами Крускала и Прима

Алгоритм построения минимального остовного дерева (МОД) Шаг 2. [Группировка объектов в кластеры] Вершины – объекты минимального остовного дерева группируются в кластеры. Выбираются два объекта, которым соответствует минимальное ребро, где. Далее эти объекты стягиваются в один кластер (класс, таксон, страту) и процедура шага 2 повторяется до тех пор, пока на n-1 этапе группирования не будет сформирован один кластер, объединяющий все объекты. STOP.

Алгоритм построения минимального остовного дерева (МОД)

Способы описания результатов иерархической кластеризации Скобочная запись

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

Алгоритмы построения минимального остовного дерева Минимальным остовным деревом T сети G является самая дешёвая подсеть, т.е. подсеть минимального веса, которая покрывает все вершины сети G и не содержит циклов.

Алгоритм Крускала Шаг 0. [Инициализация] Создаём сеть T с n вершинами, но без рёбер. Создаём сеть H идентичную сети G.

Алгоритм Крускала Шаг 1. [Цикл] До тех пор, пока сеть T не является связной сетью выполнять шаг 2, в противном случае STOP.

Алгоритм Крускала Шаг 2. [Отыскание ребра с наименьшим весом] Пусть (u,v) – ребро с наименьшим весом в сети H. Если при добавлении ребра (u,v) к сети T в последней не образуется циклов, то это ребро добавляется к T.

Алгоритм Крускала Шаг 2. [Отыскание ребра с наименьшим весом] Пусть (u,v) – ребро с наименьшим весом в сети H. Если при добавлении ребра (u,v) к сети T в последней не образуется циклов, то это ребро добавляется к T.

Алгоритм Крускала Шаг 2. [Отыскание ребра с наименьшим весом] Пусть (u,v) – ребро с наименьшим весом в сети H. Если при добавлении ребра (u,v) к сети T в последней не образуется циклов, то это ребро добавляется к T.

Алгоритм Крускала Шаг 2. [Отыскание ребра с наименьшим весом] Пусть (u,v) – ребро с наименьшим весом в сети H. Если при добавлении ребра (u,v) к сети T в последней не образуется циклов, то это ребро добавляется к T.

Алгоритм Крускала Шаг 2. [Отыскание ребра с наименьшим весом] Пусть (u,v) – ребро с наименьшим весом в сети H. Если при добавлении ребра (u,v) к сети T в последней не образуется циклов, то это ребро добавляется к T.

Алгоритм Крускала Шаг 2. [Отыскание ребра с наименьшим весом] Пусть (u,v) – ребро с наименьшим весом в сети H. Если при добавлении ребра (u,v) к сети T в последней не образуется циклов, то это ребро добавляется к T.

Алгоритм Прима Шаг 0. [Инициализация] Помечаем все вершины «невыбранными». Создаём сеть T с n вершинами, но без рёбер. Выбираем произвольную вершину и помечаем её «выбранной» T[0] 0

Алгоритм Прима Шаг 1. [Цикл] До тех пор, пока существуют «невыбранные» вершины, выполнять шаг 2, в противном случае – STOP T[0] 0

Алгоритм Прима Шаг 2. [Отыскание ребра с наименьшим весом] Пусть (u,v) – ребро с наименьшим весом между произвольно выбранной вершиной u и произвольной невыбранной вершиной v. Помечаем v как «выбранную» и добавляем ребро (u,v) в сеть T T[1] 1 3 4

Алгоритм Прима Шаг 2. [Отыскание ребра с наименьшим весом] Пусть (u,v) – ребро с наименьшим весом между произвольно выбранной вершиной u и произвольной невыбранной вершиной v. Помечаем v как «выбранную» и добавляем ребро (u,v) в сеть T T[1]

Алгоритм Прима Шаг 2. [Отыскание ребра с наименьшим весом] Пусть (u,v) – ребро с наименьшим весом между произвольно выбранной вершиной u и произвольной невыбранной вершиной v. Помечаем v как «выбранную» и добавляем ребро (u,v) в сеть T T[1]

Алгоритм Прима Шаг 2. [Отыскание ребра с наименьшим весом] Пусть (u,v) – ребро с наименьшим весом между произвольно выбранной вершиной u и произвольной невыбранной вершиной v. Помечаем v как «выбранную» и добавляем ребро (u,v) в сеть T T[1]

Разработка программы кластерного анализа