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

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

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

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

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

Одной из наиболее распространенных задач интеллектуального анализа данных является кластеризация данных. Кластеризация применяется для выделения наиболее весомых параметров данных и для дальнейшего распределения данных по выделенным группам, позволяет выделять схожие области на сложных изображениях, применяется для построения иерархической модели данных [7,9,11].

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

1. Определение структуры данных;

2. Разделение основных и второстепенных данных;

3. Выявление нестандартных характеристик данных.

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

• вначале необходимо выделить наиболее явные общие характеристики;

• далее требуется определить методологию, в соответствии с которой будет проводиться отбор;

• на следующем этапе необходимо провести распределение данных, соотнося их по выбранным вначале характеристикам;

• на последнем этапе проводится сбор результатов, необходимо выделить по результатам исследования основные группы данных.

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

Пусть - множество объектов, - множество номеров (имён, меток) кластеров. Задана функция расстояния между объектами с (x, x'). Имеется конечная обучающая выборка объектов X^m = {x₁, …, x_m} ? X. Требуется разбить выборку на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из объектов, близких по метрике с (x, x'), а объекты разных кластеров существенно отличались. При этом каждому объекту x_i ? X^m приписывается номер кластера y_i. Алгоритм кластеризации - функция ??: ?? > ??, которая любому объекту x_i ? X^m ставит в соответствие номер кластера y_i ? Y^m.

При создании алгоритмов кластеризации для сравнения данных используют меры расстояний [2,3,5,6,8] - то есть меру схожести двух каких-либо объектов. Расстояние можно считать критерием связанности объектов. В зависимости целей кластерного анализа расстояние может быть определено разными способами (см. табл. 1).

Таблица 1. Меры расстояний в кластерном анализе

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

Обзор алгоритмов кластерного анализа и классификация алгоритмов

Кластерный анализ применяется при решении различных задач изучения данных, поэтому дифференцировать алгоритмы кластеризации можно несколькими способами [1,9]:

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

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

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

Иерархический кластерный анализ Иерархические алгоритмы можно разделить на два вида:

? восходящие (агломеративные); ? нисходящие (дивизимные).

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

При использовании нисходящих алгоритмов данные распределяются по обратному принципу - «сверху-вниз». Изначально считается, что объекты образуют один общий кластер, который в дальнейшем делится на более мелкие.

К наиболее распространенным методам иерархической кластеризации можно отнести: метод одиночной связи, полной связи, средней связи, а также метод Уорда.

Метод одиночной связи.

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

Метод полных связей (наиболее удаленных соседей)

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

Метод средней связи.

Способ был предложен в 1958 году учеными Р.Р. Сокэлом и Ч.Д. Миченером в качестве позволяющего снизить негативные качества методов одиночной и полной связи.

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

Метод Уорда.

Принцип данного метода заключается в вычислении минимальной дисперсии внутри кластеров и ее последующей минимизации. В качестве целевой функции используется сумма квадратов отклонений (см. формулу 6):

,

где: хj - значение признака j-го объекта.

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

Сравнительный анализ описанных методов представлен в таблице 2.

Таблица 2. Сравнительный анализ агломеративных алгоритмов кластеризации

Использование графов в кластерном анализе

Построение графовой модели при проведении кластерного анализа позволяет получить разбиение данных с учетом их связанности [1]. То есть, полученное дерево кластеров будет состоять из наиболее крупных и важных характеристик группы данных, а листья дерева будут образовывать локальные признаки - меньшие кластеры, по которым можно распределить данные. Алгоритмы кластеризации данных, основанные на графах, могут разделяться по способу распределения данных.

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

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

К основным алгоритмам кластеризации, при которых используется методология построения графовой модели, относят: алгоритм выделения связных компонент, алгоритмы, в которых производится послойная кластеризация, алгоритмы построения минимального покрывающего дерева, алгоритм Эдсгера Дейкстры.

Решение задач кластерного анализа коллективами алгоритмов

Для получения более устойчивых разбиений данных применяются методы решения задачи коллективами алгоритмов, которые позволяют строить наиболее «согласованные» решения ^[7].

Комитетный синтез коллективных решений

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

Ниже приведено описание методики построения комитетных решений.

Построение оптимальных комитетных решений

Рассматривается множество алгоритмов кластеризации, в которых вычисляется числовая матрица оценок степени близости объектов к каждому из кластеров по решающему правилу. Задача построения оптимального комитетного коллективного решения на основе кластеризации выборки S алгоритмами А1, А2, …, Аn решается в два этапа:

1. Матрица признаков разбивается на множество классов эквивалентности - Кс.

2. Находят оптимальное коллективное решение задачи кластерного анализа как результат поиска наилучшего в определенном смысле элемента из Кс. Проводят подбор такой нумерации столбцов полученных матриц, чтобы в результате суммирования итоговая матрица оценок имела наименьшее расхождение. Для минимизации можно использовать алгоритм «наискорейшего спуска».

Построение начального приближения при поиске комитетных коллективных кластеризации

Предположим, что в результате анализа исследуемой выборки методами А1,…, Ап были получены некоторые матрицы оценок. Пусть также известно распределение объектов по кластерам коллективной кластеризации, полученное на основе некоторого алгоритма. Задача состоит в поиске кластеризаций, наиболее близких к конкретной кластеризации.

Методы построения коллективных решений на основе графов

Для построения коллективных решений можно также использовать графические модели представления данных [1,10]. Задача построения коллективного решения сводится к объединению результатов работы алгоритмов, т.е. построению коллективной функции кластеризации. Для решения этой задачи строят матрицу сопряженности и граф сопряженности, которые позволяют проверить гипотезы о наличии связи между полученными результатами.

Результаты применения коллективных алгоритмов.

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

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

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

3. Результаты кластеризации на известное априори число кластеров сравнивались с истинной классификацией.

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

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

1. автоматическое исключение заведомо вырожденных решений;

2. автоматическое создание новых оптимальных кластеризации;

3. выделение кластеризаций, наиболее согласованных с остальными из заданного набора решений;

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

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

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

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

Список литературы

алгоритм кластеризация управление

1. Бирюков А.С., Рязанов В.В., Шмаков А.С., Решение задач кластерного анализа коллективами алгоритмов, Ж. вычисл. матем. и матем. физ., 2008, том 48, номер 1, 176-192

2. Бочкарёв П.В., Киреев В.С. Разработка ансамбля алгоритмов кластеризации на основе изменяющихся метрик расстояний // Аналитика и управление данными в областях с интенсивным использованием данных XVIII международная конференция. DAMDID/RSDL' 2016 (11-14 октября 2016 г., Ершово, Московская область, Россия): труды конференции. - М.: ФИЦ ИУ РАН, 2016 - с. 69-73. Одновременная электронная публикация в CEUR Workshop Proceedings, 2016. Vol.1752. Pp. 32-46. Индексируется в Scopus. URL: http://ceur-ws.org/Vol-1752/paper06.pdf

3. Грешилов А.А., Лебедев А.Л. Компьютерные обучающие пособия для решения задач математической статистики и математического программирования. Москва, Изд-во МГТУ им. Н.Э. Баумана, 2011

4. Григорьев А.А. Алгоритмы кластеризации. А.А. Григорьев. Клаcтеpный анализ как инcтpумент обpаботки данных пpи анализе инфоpмационных cиcтем. Электронный научный журнал «Известия РЭУ им. Г.В. Плеханова». Вып. 11., 2013 г.

5. Григорьев А.А. Меры сходства в кластеризации. Электронный научный журнал «Известия РЭУ им. Г.В. Плеханова». Вып. 11., 2013 г.

6. Дж.-О. Ким, Ч.У. Мьюллер, У.Р. Клекка и др.; Под ред. И.С. Енюкова, факторный, дискриминантный и кластерный анализ: - М.: Финансы и статистика, 1989. - 215 с.

7. Котов А., Красильников Н. Кластеризация данных. 2006

8. Поляков И.В., Чеповский А.А., Чеповский А.М. Алгоритмы поиска путей на графах большого размера, Фундаментальная и прикладная математика, 2014, том 19, выпуск 1, 165-172

9. David Varadi. Fast Threshold Clustering Algorithm

10. Mirkin, B.G. Methods of cluster analysis to support decision making. - M.: izd. dom «Vysshaia shkola ekonomiki», 2011.

11. Yanjun Li, Soon M. Chung. Text Document Clustering Based on Frequent Word Sequences // Proceedings of the 14th ACM international conference on Information and knowledge management. New York, USA, ACM Press, 2005. Р. 293-294.

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