Анализ состояния вопроса

Введение

Кластерный анализ данных относится к одной из самых наиболее частых задач, решаемых в области многомерного интеллектуального анализа данных. Кластерный анализ (если сравнивать его с большинством математико-статических методов) не накладывает ограничений на вид распариваемых объектов [1].

Одним из наиболее распространенных методов неиерархической, разделительной кластеризации является алгоритм k-means. Помимо очевидного применения данного алгоритма в области data mining он также применяется для решения практических задач, например, в области распознавания образов.

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

· С одной стороны алгоритм k-means предназначен для интеллектуального анализа данных. При этом под интеллектуальностью понимает сведение участие человека в кластеризации к минимуму.

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

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

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

По материалам данной дипломной работы опубликовано 3 статьи [2, 3, 4].

Анализ состояния вопроса

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

Одним из наиболее распространенных методов неиерархической, разделительной кластеризации является алгоритм k-means. Помимо очевидного применения данного алгоритма в области data mining он также применяется для решения практических задач в области распознавания образов, например для выделения границ движущегося объекта, в системе распознавания автомобильных номеров. K-means в этом случае применяется так:

1. Проводится сравнение двух кадров сделанных с небольшим интервалом времени с одной и той же точки для поиска в двухмерном пространстве координат пикселей изменивших свое значение.

2. Запуск алгоритма кластеризация k-means где входными данными являются координаты пикселей найденные обнаруженные на предыдущем шаге. Количество кластеров выбирается равным из диапазона 5· N… 6· N, где N – максимальное количество предполагаемых для наблюдения объектов.

3. Центры кластеров расположенные рядом друг с другом группируются, т.к. вероятней всего они относятся к одному объекту. Границами наблюдаемого объекта являются крайние координаты точек, найденные в шаге 1 и относящиеся (по результатам работы алгоритма k-means) к кластерам из данной группы (рисунок 1.1).

Рисунок 1.1 – результат выделения движущегося объекта с помощью алгоритма k-means. Крестами показаны центры кластеров. Рамкой показано объединение ближайших кластеров

В общем виде кластеризация данных с помощью алгоритма k-means может быть представлена в виде следующих последовательных шагов:

1. Формирование набора данных для кластерного анализа. Это подразумевает под собой формирование конечного множества объектов, у каждого из которых определен фиксированный набор атрибутов. Атрибуту могут быть как числовые (числа, в том числе отрицательные и с плавающей точкой), так и категориальные (например “большой”, “оранжевый”, “кислотный”).

2. Задание алгоритму фиксированного количества k кластеров. Выбор значения k зависит от природы исходных данных.

3 Случайным образом выбирается k записей исходной выборки, которые будут служить начальными центрами кластеров.

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

5. Производится уточнение центров масс кластеров путем определения средних значений каждого атрибута для всех записей в кластере. Например, если в кластер вошло i объектов, у каждого из которых набор атрибутов (x_i, y_i), то координаты (x_ц, y_ц) центра данного кластера рассчитываться следующим образом [3-4]:

(1.1)

Шаги 4 и 5 повторяются рекурсивно до тех пор, пока границы кластеров и расположение центроидов не перестанут изменяться от итерации к итерации, т.е. на каждой итерации в каждом кластере будет оставаться один и тот же набор записей.

Сходимость алгоритма k-means к решению при любом наборе данных обычно происходит не более, чем за несколько десятков итераций.

Как видно, на 4 шаге алгоритма возможно применение различных метрик. Перед описание примем следующие обозначения:

· — множество данных, являющееся подмножеством m -мерного вещественного пространства;

· — элементы множества данных;

· – среднее значение точек данных;

· – ковариационная матрица (m x m)

Евклидово расстояние представляет собой сумму квадратов разницы значений по каждому из атрибутов исследуемых объектов и рассчитывается по формуле (1.2):

(1.2)

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

(1.3)

Расстояние Чебышева. Данная метрика применяется тогда, когда желают определить два объекта как "разные", если они различаются по какой-либо одному атрибуту, при этом другие атрибуты могут быть даже идентичными. Расстояние Чебышева вычисляется по формуле (1.4):

(1.4)

Расстояние Махаланобиса дает плохие результаты, если ковариационная матрица высчитывается на всем множестве входных данных. В то же время, будучи сосредоточенной на конкретном классе (группе данных), данная мера расстояния показывает хорошие результаты. Формула для расчета данной метрики (1.5):

(1.5)

Пиковое расстояние предполагает независимость между случайными переменными, что говорит о расстоянии в ортогональном пространстве. Но в практических приложениях эти переменные не являются независимыми. Расчетная форма данной метрики (1.6):

(1.6)

Существует также и другие метрики, например, метрика Минковского, но они применяются намного реже, чем перечисленные выше.

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

· С одной стороны алгоритм k-means предназначен для интеллектуального анализа данных. При этом под интеллектуальностью понимает сведение участие человека в кластеризации к минимуму (в еще лучше полное его исключение).

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

Продемонстрируем проблему выбора метрики на следующем примере. Пусть у нас имеется набор данных? состоящий из 450 объектов. У каждого объекта имеется два числовых параметра: координата по оси X и координата по оси Y. Предположим, что каждый из этих параметров представлен уже в нормализованном виде, т.е. их значения меняются в диапазоне от 0 до 1. Графическое отображение исходных данных представлено на рисунке 1.2.

При этом в алгоритме использовались такие метрики Евклида, Манхэттена и Минковского. На малом наборе данных (до 400 записей) результаты кластеризации оказались идентичными. На наборе данных начиная с 500 записей результаты работы алгоритма зависят от выбранной метрики. Приведем пример. На рисунке 3 представлен пример исходных данных содержащих в себе 500 записей.

Рисунок 1.2 – Исходные данные для кластеризации

Предположим что нам известно требуемое количество k групп в конечной кластерной структуре: k =6. Запустим алгоритм кластеризации с использованием в качестве метрики Евклидово расстояние. В этом случае для кластеризации данных потребовалось 14 итераций. Конечная кластерная структура представлена на рисунке 1.3.

Рисунок 1.3 – Распределение по кластерам при использовании метрики Евклида. Крестами обозначены центры кластеров. Ломаными линиями условно обозначены границы кластеров.

Повторим кластеризацию по тем же исходным данным, но с применением метрики Манхэттена. Количество кластеров k =6. В этом случае кластерная структура находится алгоритмом k-means за 11 итераций. Конечная кластерная структура для данного случая представлена на рисунке 1.4.

Рисунок 1.4 – Распределение по кластерам при использовании метрики Манхэттена. Крестами обозначены центры кластеров. Ломаными линиями условно обозначены границы кластеров.

При визуальном сравнении видны отличия в кластерных структурах на рисунке 1.3 и рисунке 1.4. Проведем повторную кластеризацию по тем же исходным данным, но с применением метрики Минковского Количество кластеров k =6. В этом случае кластерная структура находится алгоритмом k-means за 4 итерации. Конечная кластерная структура для данного случая представлена на рисунке 1.5.

Рисунок 1.5 – Распределение по кластерам при использовании метрики Минковского. Крестами обозначены центры кластеров. Ломаными линиями условно обозначены границы кластеров.

Как видно (рисунки 1.3-1.5) результаты кластеризации при использовании метрик Евклида, Манхэттена и Минковского различаются: около 20% объектов (для рассмотренного примера) могут относиться к разным кластерам. Поэтому выбор применяемой метрики требует обоснования и это является одной из проблем алгоритма k-means уменьшающей его степень автоматизации.

Известным решением данной проблемы является предварительный «ручной» анализ исходных данных для определения оптимальной метрики применяемой в алгоритме k-means [5-6]. Однако такой подход из-за низкой автоматизации вычислений требует повышенных трудозатрат. Кроме того, принятие решение об использование той или иной метрики при кластеризации данных принимается человеком. Правильность принятого решения зависит от его квалификации и выполненных им рассуждений.

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

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

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

· объединить лучшие особенности различных метрик, что, как следствие, приведет к улучшению результатов кластеризации данных;

· позволит избавиться от необходимости проведения исследований для обоснования применения конкретной метрики для наблюдаемых данных.

Таким образом, цель данной работы – повышение качества кластеризации и избавления от необходимости проведения исследований для обоснования применения конкретной метрики за счет разработки подходов по применению гибридных метрик в алгоритме k-means.

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

1. Исследовать зависимость параметров исходных данных на различия результатов кластеризация при использовании метрик Евклида, Манхэттена и Чебышева.

2. Разработать методику применения гибридной метрики в алгоритме неиерархической кластеризации данных k-means.

3. Спроектировать, изготовить и протестировать программное обеспечение, на практике реализующее предложенные решения по использованию гибридных метрик в алгоритме кластеризации k‑means.