ВВЕДЕНИЕ 3
II. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ 4
Основные понятия 4
Формальная постановка задачи 5
Оценка качества работы алгоритма 7
Иерархическая кластеризация 8
Алгоритм CURE 9
Применение кластеризации 10
III. ЦЕЛЬ РАБОТЫ И ПОСТАНОВКА ЗАДАЧИ 11
IV. ТЕОРЕТИЧЕСКИЕ ОСНОВАНИЯ РАБОТЫ 12
Задача о чебышевском центре конечного числа точек 12
Метод условного градиента 13
V. ПРОЦЕСС РЕАЛИЗАЦИИ 16
Проверка на условие оптимальности 18
Определение числа кластеров 19
VI. ТЕСТИРОВАНИЕ АЛГОРИТМА НА РАЗЛИЧНЫХ НАБОРАХ ДАННЫХ 21
Сравнение результатов при поиске репрезентативных точек 21
Оценка результатов кластеризации 22
VII. ЗАКЛЮЧЕНИЕ 25
VIII. СПИСОК ЛИТЕРАТУРЫ 26
IX. ПРИЛОЖЕНИЯ 27
Приложение 1 27
Приложение 2
Ни для кого не секрет, что в современном обществе информационные ресурсы наравне с материальными, финансовыми и другими ресурсами играют немаловажную роль. Производство и потребление информации лежит в основе становления и эффективного функционирования всех сфер общественной жизни.
С развитием технологий стало возможным хранение огромного количества информации, быстрое вычисление сложных функций, что облегчает работу исследователю, однако этого мало, простой набор данных недостаточен. Часто необходимо выделить суть, т.е. определить структуру, взаимосвязь, особенности на основе той или иной информации, без участия эксперта предметной области. В этом заключается основная идея машинного обучения - выявление закономерностей для дальнейшего анализа данных.
В широком смысле все алгоритмы машинного обучения делятся на два больших раздела: обучение с учителем и обучение без учителя. Первый раздел содержит алгоритмы, которые на основе имеющихся данных об объектах и соответствующих им правильных ответов, получив на вход описание неизвестного заранее объекта, выдают результат. Но распространены случаи, когда имеется только набор данных и необходимо найти зависимость между объектами, чтобы выявить дополнительные особенности объекта по группе, которой он принадлежит, или выявить нетипичные примеры. Алгоритмы, которые решают эти проблемы, содержатся во втором разделе - обучение без учителя.
Предметом исследования данной дипломной работы является один из типов задач обучения без учителя - кластеризация, в частности, иерархический подход. Задача, поставленная перед автором работы, состоит в разработке алгоритма на основе методов оптимизации.
В настоящей дипломной работе был рассмотрен иерархический алгоритм кластеризации CURE. Результатом выполнения поставленных задач является модификация алгоритма, которая использует решение задачи о чебышевском центре и метод локтя.
На основе тестовых примеров было выявлено, что решение задачи о чебышевском центре значительно ускоряет процесс поиска репрезентативных точек кластера. Благодаря этому данный метод позволяет быстрее обрабатывать данные, особенно те, у которых большое число признаков.
Метод локтя как способ определения числа кластеров хорошо работает на данных невысокой размерности. С увеличением числа параметров на качество разбиения начинает влиять коэффициент сжатия, что демонстрируют примеры.
В дальнейшем, в модификацию алгоритма планируется внедрить методы, позволяющие быстрее решать задачу минимизации линейной функции и умножать матрицы. Также планируется выявить закономерности при работе с коэффициентом сжатия а.
