Математическая модель алгоритма k-means: исследование кластеризации и практическая реализация

Введение 3
1 Анализ состояния вопроса 8
1.1 Проблемы развития алгоритмов машинного обучения 8
1.2 Проблемы кластерного анализа 31
2 Разработка метода выбора начального расположения центров кластеров 42
2.1 Формальное описание задачи кластеризации 42
2.2 Математический аппарат алгоритма EM - кластеризации 44
2.3 Методика определения первоначального расположения кластеров 49
2.4 Проведение вычислительных экспериментов 52
2.5 Результаты вычислительных экспериментов 54
3 Программная реализация 70
3.1 Описание разработанного программного обеспечения 70
3.2 Алгоритм работы с приложением 70
3.3 Реализация модуля вычислительных экспериментов 77
Заключение 84
Список используемых источников 86
Купить

Существующие методы машинного обучения в зависимости от степени автоматизации поиска решений поставленной задачи, по мнению доктор наук Yoshua Bengio можно разделить на 4 типа: rule-based systems (экспертные системы, основанные на базе знаний); classic machine learning (классические алгоритмы машинного обучения); representation learning (обучение представлениям); deep learning (глубокое обучение) (рисунок 1.1).
Экспертные системы, основанные на базе знаний, обладают наименьшей степень автоматизации получения решения поставленной задачи. В этом случае качество работы такой системы зависит только от мастерства программиста, инженера по знаниям и эксперта (источника экспертных знаний). Алгоритмы глубоко машинного обучения наоборот обладают высокой степенью автоматизации при работе с данными. Такие алгоритмы самостоятельно анализируют исходные данные, выделяют существенные признаки данных, вырабатывают стратегию решения поставленной задачи. Классические алгоритмы машинного обучения и обучение представлениям обладают средней степенью автоматизации при работе с данными.
В настоящее время проводятся исследования по повышению степени автоматизации алгоритмов машинного обучения. Например, на начальном этапе своего развития нейронные сети нейронные сети с малым количеством слоев относились к классическим алгоритмам машинного обучения. Однако с увеличением количества вычислительных слоев и совершенствованием способов их обучения стали появляться конфигурации нейронных сетей, относящихся к глубокому обучению.
Рисунок 1.1 - Анализ алгоритмов машинного обучения
В машинном обучении существует алгоритм, предназначенный для кластеризации данных - k-means. Он автоматически анализирует исходные данные и подбирает оптимальную кластерную структуру. Одной из главных его проблем является возможность попадания алгоритма в локальное решение (вместо глобального). Это связано с тем, что начальное расположение кластеров (которое, впоследствии выполнения алгоритма, уточняется) выбирается случайным образом.
Гипотезой исследования является предположение, что степень автоматизации, точность и скорость работы алгоритма k-means можно повысить путем разработки метода по расчету начального расположению центров кластеров.
Исследованиями в области совершенствования алгоритмов машинного обучения занимаются такие ученые как: Langley P., Carbonell J., Ding S., Zong W., Zhu С., Chen Z., Blum A., Bing L., Gunnemann S., Langley P., Abdolrazzaghi M., Carbonell J., Shen Q., Blocki M.M., Celebe H.M., Wuy H., Liotte D., Mucherin B., Mirkins M., Tryone C.B., Li X., Alom M.Z., Mirza B., Ertugrul O.F., Stein G., Li B., Perlich C., Chang K.C., Dietterich T.G., Carbonell J., Tamura H., Langlei M., Wiens J. E., Zhou ZH., Hemmi H. L., Webb G.I., Zhang D., Nayak P.K. и др.
Объектом исследования являются кластеризация данных, предметом исследования - разработки метода по расчету начального расположению центров кластеров.
Цель исследования - повышение степени автоматизации алгоритма k- means путем разработки метода по расчету начального расположению центров кластеров.
Цель достигается путем решения следующих задач:
1. Проведение анализа состояния вопроса по теме исследования
2. Разработка метода по определению начальных положений центров кластеров (при анализе данных с помощью алгоритма k-means).
3. Разработка программной реализация данного метода для проверки его эффективности на практике.
4. Тестирование предложенного метода на практике. Формулирование выводов по результатам вычислительных экспериментов.
Научная новизна исследования - доказано что скорость и точность результатов кластеризации данных с помощью алгоритма k-means может быть увеличена путем обоснованного задания начального положения центров кластеров. Это также приведет к снижению вероятности схождения алгоритма к локальному решению.
Практическая значимость работы заключается в разработке методики выбора начального положения центров кластеров, что позволяет увеличить точность и скорость кластеризации данных с использованием алгоритма k- means.
В первой главе настоящего исследования рассматриваются проблемы развития алгоритмов машинного обучения. Также рассмотрены проблемы кластерного анализа с помощью алгоритма k-means.
Во второй главе рассматривается формальное описание задачи кластеризации данных. Описан математический аппарат EM-алгоритмов кластеризации Затем дается описание метода по определению оптимального начального положения центров кластеров при кластеризации данных с использованием алгоритма k-means. Далее даются результаты вычислительных экспериментов по применению предложенного метода в сравнении с классической реализацией алгоритма.
В третьей главе дается описание разработанного программного обеспечения. Затем приведен алгоритм работы с, созданным в рамках данного исследования, приложением. И описывается реализация модуля вычислительных экспериментов.
На защиту выносятся:
1. Методика по расчету начального положения центров кластеров.
2. Результаты апробации предложенной методики при кластеризации данных.
По результатам проведенных исследований опубликовано 5 статей в сборниках, входящих в РИНЦ.
Результаты исследований доложены на таких конференциях как:
• XXXI студенческой международной научно-практической конференции, г. Москва.
• Научно-практической конференции ''Студенческие дни науки в ТГУ'', г. Тольятти
• III научно-практической всероссийской конференции (школе - семинаре) молодых ученых «Прикладная математика и информатика: современные исследования в области естественных и технических наук».
Купить