Введение к работе
Актуальность темы. Интеллектуальный анализ данных (англ. Data Mining) — собирательное название, используемое для обозначения совокупности методов обнаружения в исследуемых данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности. Кластеризация(или же кластерный анализ) является одной из центральных областей интеллектуального анализа данных. Её задачей является выделение в исходном множестве некоторой, заранее неизвестной, структуры кластеров. Термин кластер понимается в интеллектуальном анализе данных как объединение нескольких однородных элементов, которое может рассматриваться как самостоятельная единица, обладающая определёнными свойствами.
Кластеризация широко используется как в качестве отдельного инструмент анализа, так и как один из этапов предварительной обработки данных перед использованием других аналитических методов (например, перед классификацией или поиском ассоциативных правил). Кажущаяся простота постановки задачи, возможность выявления скрытых группировок элементов данных как на множестве в целом, так и внутри каждого кластера по отдельности, а так же несомненное улучшение восприятия аналитиками данных, разбитых на кластеры, — всё это делает методы кластерного анализа широко используемыми в самых различных областях. Кластеризации подвергаются данные по экономике и социологии, тексты, новостные потоки, блоги, генетические последовательности, изображения, данные социальных сетей, медицинские и биологические показатели.
При получении какого-либо результата у исследователя, аналитика или разработчика естественным образом возникает вопрос о его качестве. Точно так же вопрос о качестве возникает и после проведения кластерного анализа данных. Оценка качества несомненно важна для всего процесса кластеризации, потому что без неё полученная структура кластеров не может быть сочтена достаточно достоверной для того, чтобы делать из неё определённые выводы или проводить дальнейший анализ на её основе. Широко распространённым способом оценки качества кластеризации является проверка, производимая аналитиком вручную, например, с помощью визуализации полученной кластерной структуры. Однако, это является удобным далеко не всегда, а в случае больших объёмов данных или же данных с высокой размерностью, такая проверка достаточно затруднительна. Альтернативой методам визуальной оценки качества являются автоматические методы оценки качества кластеризации. Они могут быть рассмотрены как функции от полученной кластерной структуры и исходного множества. В литературе методы данной группы носят названия индексы или метрики. Именно такой спектр методов является объектом исследования в данной работе.
Разнообразные задачи кластерного анализа данных традиционно привлекают к себе внимание исследователей на протяжении нескольких десятилетий и до текущего момента не потеряли своей актуальности. Поскольку оценка качества результатов неотделима от общего процесса кластеризации, разработка, сравнение или повышение эффективности автоматических методов оценки качества кластеризации являются актуальными областями исследований.
Цель работы. Целью работы является исследование методов оценки качества кластеризации, выявление их сильных и слабых сторон и создание специальной библиотеки индексов оценки качества кластеризации, которой смогут пользоваться аналитики разных направлений.
Для достижения поставленной цели были выделены следующие задачи:
Сравнение уже имеющихся индексов оценки качества кластеризации и определение их эффективности в зависимости от используемого алгоритма кластеризации.
Выявление зависимости качества кластеризации от качества исходных данных.
Разработка модели качества кластеризации, учитывающей формализованное представление пользователя о желаемой кластерной структуре.
Основные результаты. В диссертации получены следующие результаты:
-
Предложен метод выбора индексов оценки качества в зависимости от используемых алгоритмов кластеризации.
-
Предложен метод выбора алгоритмов кластеризации в зависимости от ожидаемого уровня качества данных.
-
Построена семантическая модель оценки качества кластеризации, основанная на сравнении формализованного представления пользователя о результатах кластеризации с полученной структурой кластеров.
-
Представлен индекс оценки качества кластеризации, построенный на основе разработанной модели.
-
Разработана библиотека индексов оценки качества кластеризации, содержащая реализации методов, рассмотренных в ходе проведённых исследований.
Научная новизна. В работе предложена модель оценки качества кластеризации, отражающая семантику полученного результата кластеризации. Под семантикой в данном случае понимается выраженные в терминах предложенной модели представления пользователя о результатах кластеризации.
В соответствии с этой моделью введены понятия размерностей качества кластеризации, и представлен метод их измерения в терминах модели Resource Description Framework(RDF).
Выяснено влияние измерений качества исходных данных на качество результатов кластеризации, и сделаны выводы об использовании алгоритмов кластеризации в случае соответствующих ошибок данных.
Сформулированы требования к методам оценки качества кластеризации в зависимости от используемого алгоритма.
Теоретическая ценность и практическая значимость. Теоретическую ценность работы составляет предложенная семантическая модель оценки качества кластеризации, позволяющая исследователям и аналитикам оценивать валидность кластерной структуры с семантической точки зрения.
В рамках данной работы разработан прототип библиотеки методов оценки качества кластеризации, включающий в себя реализацию одиннадцати относительных индексов и четырёх внешних индексов оценки качества. Библиотека написана на языке Java и является совместимой с платформой Weka.
Апробация работы. Основные результаты диссертации докладывались на семинаре Московской Секции ACM SIGMOD; на семинарах группы исследования методов организации информации при лаборатории исследования операций НИММ СПбГУ, а также на следующих конференциях:
-
Симпозиуме Молодых Учёных SYRCoDIS, 2009;
-
Докторском консорциуме объединенных конфференций EDBT/ICDT "EDBT/ICDT PhD Workshop" 2012;
-
Международной конференции "Advanced Databases and Information Systems" 2012;
-
Международной Балтийской Конференции по Базам Данных и Информационным Системам "Baltic Conference on Databases and Information Systems" 2012;
Публикации. Основное содержание диссертации опубликовано в восьми научных статьях, список которых приведён в конце автореферата. Две из этих статей находятся в изданиях, рекомендуемых ВАК для публикации основных результатов диссертаций на соискание учёной степени кандидата наук.
Основными работами по теме диссертации являются
1. Сивоголовко Е. Методы оценки качества четкой кластеризации. // Компьютерные инструменты в образовании — Тверь, 2011 — Вып. 4 (96) - С. 14-31.
-
Sivogolovko E. The Influence of Data Quality on Clustering Outcomes. // Frontiers in Artificial Intelligence and Applications — IOS Press, 2012 — Vol. 249 - P. 95-105.
-
Sivogolovko, E., Thalheim, B. Semantic approach to cluster validity notion. // Advances in Databases and Information Systems / Ed. by Tadeusz Morzy, Theo Harder, Robert Wrembel. — Springer Berlin Heidelberg, 2012 - Vol. 186 - P. 229-239.
Структура и объем диссертации. Диссертация состоит из пяти глав, включая введение; заключения и списка литературы, содержащего восемьдесят семь названий. Общий объём диссертации составляет девяносто две страницы.
