Рассмотрение основных современных подходов к кластеризации данных. Описание предшествующих решений и предоставление версии алгоритма мультимодальной кластеризации для запуска в системе распределённых вычислений под Apache Hadoop. Адаптация алгоритма.
Аннотация к работе
Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский университет "Высшая школа экономики" Факультет Компьютерных наук Департамент программной инженерии ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА по направлению 09.03.04 «Программная инженерия» подготовки бакалавра Студента группы № БПИ122 ______________ ПодписьРабота посвящена распределенному проведению мультимодальной кластеризации. В работе рассмотрены основные современные подходы к кластеризации данных, приведено описание предшествующих решений и предоставлена версия алгоритма мультимодальной кластеризации для запуска в системе распределенных вычисления под Apache Hadoop. Программа позволяет проводить кластеризацию данных, имеющих модальность большей либо равной двум. Алгоритм адаптирован под модель распределенных вычислений MAPREDUCE, программа реализована с помощью фреймворка Apache Hadoop, что позволяет распараллелить вычисления по тысячам вычислительных узлов. Besides, we introduce a new version of multimodal clustering algorithm for distributed processing in Apache Hadoop on computer clusters.Online version of prime OAC-triclustering ................................................................10 Distributed version of online prime OAC-triclustering..............................................11 Анализ предшествующей реализации ........................................................................153.1. Используемые технологии...............................................................................................23 Apache Hadoop ...........................................................................................................27 Apache Maven.............................................................................................................28 Классы MAPREDUCE.............................................................................................30 Закладка не определена.Программа мультимодальной кластеризацииКластеризация данных - это методология, используемая для группирования объектов определенного набора данных в соответствии с некоторой мерой похожести [14]. Являясь одной из фундаментальных задач интеллектуального анализа данных, кластерный анализ находит применение в различных областях: от построения рекомендательных систем до решения задач генетики [3]. Такими же темпами увеличивается и количество задач и методов их решения, связанных с кластеризацией. Первые методы кластеризации объектов, содержащих один параметр, были предложены в работе Хартигана [10], позднее Миркин [19] расширил понятие для случая двумерных данных. В таких алгоритмах за бикластер принимается формальный концепт - пара, состоящая из экстента и интента, где экстент состоит из всех объектов, имеющих все атрибуты из интента, а интент - подмножество всех атрибутов, которые есть у всех объектов из экстента.В данной главе приводится описание различных алгоритмов и техник, используемых в кластерном анализе.Фактически анализ формальных понятий имеет дело с данными в объектно-признаковой форме, а формальные понятия, определенные с помощью соответствия Галуа, представляют собой пары множеств вида (объем, содержание), им в точности до перестановки строк и столбцов соответствуют максимальные прямоугольники в таблице объект-признак. К примеру, она может представлять набор покупателей и продуктов какого-либо магазина (таблица 1). Формальные кон е сты включают в себя операторы, формирующие формальный операторов сгенерирует два множества: A? = {m ? M | GIM for all g Применив эти операторы к данным, описанным в Таблице 1 для экстента {Покупатель 1, Покупатель 2}, мы получим соответствующий интент {Продукт 1, Продукт 3} - продукты, которые приобрели оба покупателя. Из интента {Продукт 1, Продукт 2, Продукт 3} мы подобным образом получим экстент {ПокупательХоть целью работы и является построение программы, проводящей мультимодальную кластеризацию, ее сравнение будет проводиться с алгоритмами трикластеризации, т.к. именно для триадического контекста были предложены все относящиеся к работе алгоритмы-предшественники. Под формальным контекстом будет иметь в виду набор K = (G, M, B, I), где G - множество объектов, M - множество их атрибутов, B - множество условий и I - отношение между этими множествами.(I G ? M ? B) Идея данного алгоритма построена на использовании box-операторов [20]: для каждой компоненты из тройки множества отношений I применяется box-оператор, затем строится трикластер, состоящий из трех полученных множеств. На последнем шаге алгоритм проходит по остальным тройкам и проводит проверку на принадлежность ее объектов к множеству, получаемому box-оператором, и если проверка положительна, добавляет тройку в трикластер. Идея алгоритма достаточно проста: сперва алгоритм проходит по всем парам объект-атрибут, атрибут-условие, объект-условие и строит составляющие будущих прототипов трикластеров - экстенты, интенты и модусы.