Кластеризация данных

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

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

Архитектуры системы можно разделить на две основные части: веб приложение и программное обеспечение кластеризации и классификации данных

Алгоритм программного обеспечение для машинного обучение состоит из 3 основных частей:

1. обработка естественного языка;

   1. токенизация;

   2. лемматизация;

   3. стоп-листинг;

   4. частота слов;

2. методы кластеризации ;

   1. TF-IDF ;

   2. SVD;

   3. нахождение кластерных групп;

3. методы классификации Aylien API.

Обработка естественного языка

Алгоритм начинается с чтение любых текстовых данных. Так как система у нас электронная библиотеку, то и книги в основном в формате pdf. Реализация и детали обработки NLP можно почитать тут.

Ниже приводим сравнение при запуске алгоритмов Лемматизации и Стеммитизации:

Общее количество слов: 4173415Количество слов после приминение Лемматизации: 88547Количество слов после приминение Стеммитизации: 82294

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

characterize, design, space, render, robot, face, alisa, kalegina, university, washington, seattle, washington, grace, schroeder, university, washington, seattle, washington, aidan, allchin, lakeside, also, il, school, seattle, washington, keara, berlin, macalester, college, saint, paul, minnesota, kearaberlingmailcom, maya, cakmak, university, washington, seattle, washington, abstract, face, critical, establish, agency, social, robot, building, expressive, mechanical, face, costly, difficult, robot, build, year, face, ren, der, screen, great, flexibility, robot, face, open, design, space, tablish, robot, character, perceive, property, despite, prevalence, robot, render, face, systematic, exploration, design, space, work, aim, fill, gap, conduct, survey, identify, robot, render, face, code, term, property, statistics

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

character, design, space, render, robot, face, alisa, kalegina, univers, washington, seattl, washington, grace, schroeder, univers, washington, seattl, washington, grsuwedu, aidan, allchin, lakesid, also, il, school, seattl, washington, keara, berlin, macalest, colleg, saint, paul, minnesota, kearaberlingmailcom, maya, cakmak, univers, washington, seattl, washington, abstract, face, critic, establish, agenc, social, robot, build, express, mechan, face, cost, difficult, mani, robot, built, year, face, ren, dere, screen, great, flexibl, robot, face, open, design, space, tablish, robot, charact, perceiv, properti, despit, preval, robot, render, face, systemat, explor, design, space, work, aim, fill, gap, conduct, survey, identifi, robot, render, face, code, term, properti, statist, common, pattern, observ, data, set, face, conduct, survey, understand, peopl, percep, tion, render, robot, face, identifi, impact, differ, face, featur, survey, result, indic, prefer, vari, level, realism, detail, robot, facecharacter, design, space, render, robot, face, alisa, kalegina, univers, washington, seattl, washington, grace, schroeder, univers, washington, seattl, washington, grsuwedu, aidan, allchin, lakesid, also, il, school, seattl, washington, keara, berlin, macalest, colleg, saint, paul, minnesota, kearaberlingmailcom, maya, cakmak, univers, washington, seattl, washington, abstract, face, critic, establish, agenc, social, robot, build, express, mechan, face, cost, difficult, mani, robot, built, year, face, ren, dere, screen, great, flexibl, robot, face, open, design, space, tablish, robot, charact, perceiv, properti, despit, preval, robot, render, face, systemat, explor, design, space, work, aim, fill, gap, conduct, survey, identifi, robot, render, face, code, term, properti, statist, common, pattern, observ, data, set, face, conduct, survey, understand, peopl, percep, tion, render, robot, face, identifi, impact, differ, face, featur, survey, result, indic, prefer, vari, level, realism, detail, robot, face

Методы кластеризации

Для применения алгоритма tf-idf нужно подсчитать сколько раз слово встречается в каждом документе. Можно использовать HashMap, где ключ - слово, значение - кол-во.

После этого нужно построит матрицу документы-слова:

Далее по формуле вычисляем tf-idf:

Следующий этап, использование метода сингулярного разложение, где на вход приходит результат tf-idf. Пример выходных данных алгоритма сингулярного разложение:

-0.0031139399383999997 0.023330604746 -1.3650204652799997E-4-0.038380206566 0.00104373247064 0.056140327901-0.006980774822399999 0.073057418689 -0.0035209342337999996-0.0047152503238 0.0017397257449 0.024816828582999998-0.005195951771999999 0.03189764447 -5.9991080912E-4-0.008568593700999999 0.114337675179 -0.0088221197958-0.00337365927 0.022604474721999997 -1.1457816390099999E-4-0.03938283525 -0.0012682796482399999 0.0023486548592-0.034341362795999995 -0.00111758118864 0.0036010404917-0.0039026609385999994 0.0016699372352999998 0.021206653766000002-0.0079418490394 0.003116062838 0.072380311755-0.007021828444599999 0.0036496566028 0.07869801528199999-0.0030219410092 0.018637386319 0.00102082843809-0.0042041069026 0.023621439238999998 0.0022947637053-0.0061050946438 0.00114796066823 0.018477825284-0.0065708646563999995 0.0022944737838999996 0.035902813761-0.037790461814 -0.0015372596281999999 0.008878823611899999-0.13264545848599998 -0.0144908102251 -0.033606397957999995-0.016229093174 1.41831464625E-4 0.005181988760999999-0.024075296507999996 -8.708131965899999E-4 0.0034344653516999997

Матрицу SVD можно использовать как координаты в трехмерном пространстве.

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

Теперь нужно применить данную операцию и для терминов, то есть слов.

Последний этап метода кластеризации найти кластерные группы. Так как у нас уже есть трехмерная пространство, где хранятся точки документов и терминов в виде вершин, то нужно соединить эти документы и слова использовав схожий метод кластеризации DBSCAN. Для определения расстояние между документом и словом используется Евклидовое расстояние. А радиус можно определить по формуле ниже. В данном примере и при тестировании используется r=0.007. Так как в пространстве находится 562 документов и более 80.000 тысяч слов, то они расположены близко. При большом радиусе алгоритм будет связывать термин и документ в один кластер, которые не должны быть в одной группе.

где max(D) это дистанция между документом и самой дальней точкой термина, то есть максимальная дистанция документа в пространстве. n - это количество документов в пространстве

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

После этого нужно всего лишь соединить вершины документов, которые имеют общие вершины терминов. Для соединения документов нужно чтобы общее число терминов было больше 4-х. Формула определение общего сила слов (в данном случае > nt)

N это количество кластерных групп термин - документов, S это количество связей в семантическом пространстве.

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

Методы классификации Aylien API

Для классификации в инструменте Aylien API всего лишь нужно передать любой текст. API вернет ответ в виде json объекта, где внутри есть категории классификации. Можно было бы отправлять весь текст каждого документа в одной группе кластеров через API и получить категории классификации. Для примера рассмотрим 9 групп кластеров, которые состоят из статьи про ИТ технологии. Все тексты документов каждой группы записываются в массив и отправляют запрос POST через API:

String queryText = "select  DocText from documents where clusters = '" + cluster + "'";   OResultSet resultSet = database.query(queryText);   while (resultSet.hasNext()) {   OResult result = resultSet.next();   String textDoc = result.toString().replaceAll("[\\<||\\>||\\{||\\}]", "").replaceAll("doctext:", "")   .toLowerCase();   keywords.add(textDoc.replaceAll("\\n", ""));   }   ClassifyByTaxonomyParams.Builder classifyByTaxonomybuilder    = ClassifyByTaxonomyParams.newBuilder();   classifyByTaxonomybuilder.setText(keywords.toString());   classifyByTaxonomybuilder.setTaxonomy(ClassifyByTaxonomyParams.StandardTaxonomy.IAB_QAG);   TaxonomyClassifications response = client.classifyByTaxonomy(classifyByTaxonomybuilder.build());   for (TaxonomyCategory c : response.getCategories()) {   clusterUpdate.add(c.getLabel());   }

После успешного получение ответа от сервиса методам GET, данные группы обновляются:

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

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

Разработка веб-интерфейса

Цель разработки веб-интерфейса наглядный вид результата использование алгоритма кластеризации и классификации. Это дает пользователю удобный интерфейс не только увидеть сам результат, но и в дальнейшем использовать эти данные для нужд. Так же разработка веб-интерфейса показывает, что данный метод можно успешно использовать для онлайн библиотек. Веб приложение было написано с использованием Фреймворка Vaadin Flow:

В данном приложении есть следующие функции:

• Документы, разделенные по предметам методом кластеризации и классификации.

• Поиск по ключевым словам.

• Поиск по хэш-тегам.

• Весь список документов в базе данных, где есть возможность поиска по ИД документа, наименованию документа, предметам кластеров, ключевым словам и по хэш-тэгам.

• Возможность скачивание файла.

Список документов классификации по предмету Technology & Computing:

Список документов найденные по ключевым словам:

Табличный список всех документов:

Заключение

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

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

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

Для классификации кластерных используется Aylien API, который использует подход классификации по таксономии и на базе кодов. В результате исследовании кластерные группы были разделены по предметным областям, который включает в себя более 100 контентной категории. Данный метод можно заменить и другими, более специфическими алгоритмами машинного обучение, таких как метод опорных векторов, метод k-ближайших, нейронную сеть. Но так как данные методы требуют большое количество данных который используется для построения модели, в данной работе было использована готовая модель классификации.

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

Почему это круто

Кластерный анализ неформально можно определить как разбиение множества объектов так, чтобы похожие объекты попали в одно и то же подмножество, а объекты из разных подмножеств существенно различались. От обычной классификации по заданным признакам кластерный анализ отличается тем, что не алгоритм, а человек выявляет критерий кластеризации данных. Эта задача относится к классу обучения без учителя (англ. unsupervised learning), так как размеченного набора данных или какой-то заведомо известной информации о нём не предоставляется.

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

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

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

Как определить меру качества

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

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

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

Сравниваем разбиения

Берём алгоритмы кластеризации и применяем их к набору данных. Полученные разбиения можно оценивать как адекватные или неадекватные, а ещё можно проводить сравнения разбиений друг с другом, чтобы определить лучшие. На рисунке ниже приведён пример сравнения различных разбиений примитивного набора данных с точки зрения адекватности, а также с точки зрения сравнения разбиений друг с другом. Чем выше на рисунке расположено разбиение, тем оно лучше с точки зрения попарного сравнения с другими разбиениями.

Сравниваем меры качества

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

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

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

Для наглядности давайте рассмотрим пример с собранным мною набором данных из двухсот двумерных наборов данных 2D-200. Для каждого набора данных из 2D-200 были сформированы 14 разбиений. Эти разбиения были оценены пятью асессорами и девятнадцатью мерами качества. В итоге на наборе данных 2D-200 выявлены лучшие меры качества с точки зрения критериев иЗатем для каждой меры по всем элементам из 2D-200 были вычислены следующие величины:

соотношение числа раз, когда мера отвечала критерию адекватности к общему числу экспериментов;

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

Значения и для всех мер качества на наборе данных наборов данных 2D-200 представлены в таблице ниже.

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

Однако эффективная рекомендация из девятнадцати мер качества требует значительно большего числа наборов данных, чем представлено в 2D-200. Поэтому я построил множество из четырех самых лучших мер с точки зрения среднего значения, вычисляемого на основе критерия ранжирования мер: мера Silhouette, мера Calinski-Harabasz, мера gD41 и мера OS. В таблице приведены значения для всех исследованных мной внутренних мер качества.

Классификатор, который рекомендует меру качества

Всякий раз производить данные вычисления довольно ресурсозатратно. Можно упростить задачу рекомендации меры качества, если свести её к задаче классификации. И я решил построить классификатор, который для нового набора данных предсказывает, какая из рассматриваемых мер качества будет лучше с точки зрения агрегированных оценок асессоров, если бы они действительно проходили описанный выше тест для этого набора данных. В качестве классификатора я использовал алгоритм случайного леса, который выбрал экспериментально, и который показывает качество классификации Интересно, что разработанный мета-классификатор сам по себе выступает новой мерой качества, назовём её Meta-CVI.

Как подобрать алгоритм

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

Эвристические алгоритмы

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

Чтобы решить эту проблему, я разработал метод выбора и настройки алгоритмов на базе обучения с подкреплением MASSCAH. Этот метод сводится к задаче о многоруком бандите. Предлагается осуществлять поиск компромисса между исследованием и эксплуатацией процессов настройки параметров для различных алгоритмов кластеризации.

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

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

гдеи

В этом случае каждой ручке бандита соответствует определённая модель алгоритма кластеризации из конечного множества вызову ручки на итерации процесс оптимизации гиперпараметров этой модели в течение времени В результате будет достигнуто качество кластеризации

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

Иллюстрация работы метода выбора и настройки эвристического алгоритма MASSCAH представлена на рисунке ниже:

Эволюционные алгоритмы

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

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

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

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

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

Ниже представлена таблица числа запусков алгоритма с автоматизацией и без неё, сгруппированная по оптимизируемым мерам качества. Хуже и не хуже означает, что автоматизированный алгоритм, соответственно, отстаёт либо не отстаёт от алгоритма без автоматической настройки параметров по качеству разбиений; среднее время работы алгоритма с автоматизацией и без неё соответственно.

Сравнение алгоритмов

Интересно сравнить алгоритм на основе выбора и настройки эвристических алгоритмов кластеризации MASSCAH с алгоритмом настройки эволюционного алгоритма кластеризации.

Я предположил, что два алгоритма получают одинаковые значения меры качества, если интервалы этих значений пересекаются. То есть была использована квантиль уровня для нормального распределения. Временной бюджет алгоритма, запускаемого на определённых мере и наборе данных, задавался равным среднему времени работы автоматизированного эволюционного алгоритма на этих мере и наборе данных. Я запустил алгоритмы со всеми отобранными ранее четырьмя мерами качества: Silhouette, Calinski-Harabasz, gD41 и OS. Для каждой пары мера набор данных производилось 10 запусков алгоритма. Полученные количества удачных и неудачных запусков приведены в таблице ниже.

Число положительных и отрицательных результатов сравнений алгоритмов на базе метода выбора и настройки эвристического алгоритма кластеризации на основе обучения с подкреплением, сгруппированные по мере качества разбиений. Столбец MASSCAH > Evo соответствует случаям, когда качество эволюционного алгоритма оказалось хуже, чем алгоритма на базе обучения с подкрепление, MASSCAH Evo что качества сравнимы, MASSCAH < Evo разработанный алгоритм опережает существующий результат.

Можно заметить, что успешность эволюционного алгоритма зависит от используемой меры, но по общему числу запусков он сравним с предложенным методом выбора и настройки гиперпараметров эвристического алгоритма кластеризации. Отдельно стоит заметить, что эволюционный алгоритм кластеризации с автоматически настраиваемыми параметрами опережает таковой без автоматической настройки параметров по измеренным характеристикам независимо от меры, однако при этом его производительность по сравнению с разработанным методом на основе обучения с подкреплением зависит от выбора меры оценки качества разбиения. Кроме того, расчёт числа удачных и неудачных запусков производился для предложенной мной меры Meta-CVI.

Как применить всё это на практике

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

Этот программный комплекс состоит из нескольких пакетов. Пакет CVI_Predictor реализует алгоритм предсказания меры для конкретной задачи кластеризации на основе мета-обучения. Пакет RL_Clustering реализует различные алгоритмы на базе представленного в работе метода выбора и настройки эвристического алгоритма кластеризации. Пакет Evo_Clustering реализует эволюционный алгоритм кластеризации с параметрами, настраиваемыми при помощи мета-обучения. Пакет Incremental_CVI реализует инкрементальное вычисление мер качества разбиений. Весь комплекс можно скачать на GitHub.

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

На сегодняшний день система автоматического выбора и оценки алгоритмов кластеризации и их параметров была успешно использована в рамках государственного задания 2.8866.2017/8.9 Технология разработки программного обеспечения систем управления ответственными объектами на основе глубокого обучения и конечных автоматов. В рамках этого задания решалась задача нахождения формальной грамматики по некоторому конечному списку слов, которые принадлежат некоторому неизвестному формальному языку. В частности, была решена важная подзадача разметки слов-примеров, по которым строится грамматика при помощи рекуррентных нейронных сетей.

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

Помимо этого, программный комплекс был применён для разработки рекомендательной системы выбора научного руководителя и темы исследования для абитуриентов Университета ИТМО.

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