ВВЕДЕНИЕ 3
ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ ЗАДАЧИ КЛАСТЕРИЗАЦИИ 5
1.1 Формальная постановка задачи кластеризации 5
1.2 Актуальные проблемы кластерного анализа 6
1.3 Этапы кластерного анализа 8
1.4 Цели кластеризации 9
1.5 Функции расстояний 10
1.6 Алгоритмы кластеризации 12
1.6.1 Неиерархические методы 13
1.6.2 Иерархические алгоритмы 14
ГЛАВА 2. РЕАЛИЗАЦИЯ АЛГОРИТМОВ ЗАДАЧИ КЛАСТЕРИЗАЦИИ 15
2.1 Алгоритм k-means 15
2.2 Иерархический метод 17
2.3 DBSCAN 20
2.4 MaxFlow 21
ГЛАВА 3. РЕЗУЛЬТАТЫ РАБОТЫ РЕАЛИЗОВАННЫХ АЛГОРИТМОВ 23
ЗАКЛЮЧЕНИЕ 28
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 30
ПРИЛОЖЕНИЕ
На протяжении всей истории человек извлекал и накапливал информацию об окружающем мире. Люди упорядочивали все объекты по мере их схожести и различия, опираясь на опыт и полученные знания. Данная группировка имела важное значение для выживания и развития (ярким примером служит разделение растений на съедобные и несъедобные, животных - опасны, неопасны и т.д.). Процесс распределения объектов по группам получил название классификация данных. По мере роста знаний о жизни и окружающем мире, так же росла и роль классификации. Р. Сокэл в одной из своих статей отмечает, что классификация - интеллектуальная деятельность высокого уровня, необходимая нам для понимания природы. Способность собирать внешние раздражители в некие группы присуща всем живущим в мире и является результатом инстинктов, обучения и генетической памяти.
Классификация развивалась с развитием науки как одна из ее фундаментальных граней, но до последнего времени данный процесс опирался на возможности человека распознавать образы и группировать объекты. Но с ростом научных знаний, растет объем и сложность информации, ввиду чего эффективный анализ становится практически недосягаемым для человека и требуются новые походы.
В таких условиях, автоматизация направлений человеческой деятельности затронула и процесс кластеризации. В настоящее время совокупность алгоритмов и методов, которые используются для автоматической группировки объектов, называют кластерным анализом.
Задача кластеризации (англ. clustering), в отличие от задач регрессионного анализа и задач классификации, а также от других известных классов задач машинного обучения, основывается на так называемом «обучении без учителя» (англ. «unsupervised learning»). Основная задача состоит в том, чтобы предоставить пользователю, который исследует данные инструмент для автоматического разделения имеющихся объектов на классы, с учетом сходств или различий характеристик (так называемых, факторов) этих объектов.
Основная проблема заключается в том, что ни количество классов, ни сами классы заведомо не известны. Возникает вопрос: как компьютер выполнит разбиение на классы, если сами эти классы неизвестны?
Все кластеры организованы таким образом, что факторы экземпляров одного класса достаточно близки между собой, но при этом достаточно отличаются от факторов экземпляров других кластеров. В данном определении, понятия какого-то “сходства” и “различия” весомо зависят от конкретной области и от задачи. В большинстве случаев, кластеризацию используют с той целью, чтобы произвести сжатие данных, а именно сократить объем исходных данных за счет того, что один класс исследуется как один цельный объект.
Кластеризация обеспечивает понимание исходных данных и упрощает дальнейшее исследование данных. Так же стоит учитывать, что при проведении кластеризации могут быть найдены “нетипичные” объекты, т.е. объекты, которые невозможно отнести ни к одному классу. Именно такие объекты дают новый полезный материал для дальнейшего изучения и исследования.
Цель данной работы заключается в ознакомлении с задачей кластеризации, а также в изучении и сравнении алгоритмов задачи кластерного анализа.
В настоящее время окружающий мир переполнен различной информацией и объемными данными. Достаточно часто возникает проблема разделения нелинейных данных, которые проблематично представить в математическом виде. Одним из главных инструментов обработки данных является кластеризация, которая состоит в разбиении объектов на однородные группы, с целью поиска существующих структур.
Существует огромное количество алгоритмов кластеризации. Интуитивно понятным является алгоритм k-means, однако у данного алгоритма существует ряд своих минусов. Существует две большие группы алгоритмов: иерархические и неиерархические.
Кластеризация относится к разделу “задач без учителя”. Это означает, что не требуется наличие обучающей выборки.
Цель данной работы заключалась в изучении и исследовании алгоритмов кластерного анализа.
В ходе работы были рассмотрены, изучены, реализованы и проанализированы следующие алгоритмы:
•K-mean;
•Ward;
•BDSCAN;
•MaxFlow (собственный метод).
Все графические результаты представлены в главе 3.
Проанализировав результаты работы алгоритмов, можно сказать, что не существует универсального метода кластеризации. Исходя из приоритетных свойств (простота и прозрачность, легкость реализации, быстрота выполнения, надобность “выделения” шумов, необходимость иметь полное решение - дендрограмму и т.д.), необходимо выбирать алгоритм, подходящий под конкретную ситуацию.
В главе 3 сделанные основные выводы и предположения, какие алгоритмы использовать в конкретной ситуации.
Наилучшие временные результаты показывает алгоритм k-means и DBSCAN, наилучшие качественные характеристики - DBSCAN и MaxFlow. Алгоритмами, которые способны распознать шум - DBSCAN и MaxFlow. Если имеется необходимость отслеживать каждый шаг разбиения/соединения кластеров, то имеет смысл использовать иерархический алгоритм Ward.
Стоит заметить, что алгоритмы MaxFlow и DBSCAN позволяют выделять кластеры произвольной формы, когда алгоритмы k-means и Ward выделяют кластеры сферической формы.
Данные выводы и алгоритмы являются только началом изучения задачи кластерного анализа. Проблема кластеризации всегда будет оставаться актуальной, так как с каждым днем область применения разбиения данных расширяется, растут объемы данных, что вызывает рост необходимости прибегать к дополнительным технологиям.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
