Актуальные проблемы кластерного анализа

Размещено на http://www.allbest.ru/

Оглавление

• Введение
• Специальная часть проекта
• 1. Актуальные проблемы кластерного анализа
• 1.1 Задачи кластерного анализа
• 1.2 Этапы кластерного анализа
• 1.3 Цели кластеризации для выработки рекомендаций
• 1.4 Построение ценовых (весовых) моделей
• 2. Техническое задание
• 2.1 Цель и назначение разработки

2.2 Этапы разработки

2.3 Основные требования к программному обеспечению

• 3. Обзор существующих решений

3.1 Иерархические методы кластеризации

• 3.2 Неиерархические (итеративные) методы кластеризации

3.3 Сравнительный анализ иерархических и неиерархических методов кластеризации

3.4 Сеточные алгоритмы

• 4. Обзор существующих систем кластеризации
• 4.1 Коммерческие инструменты
• 5. Предлагаемые методы и математическое обеспечение
• 5.1 Методы кластеризации

5.2 Метод вычисления ценовых моделей

• 6. Структура системы
• 6.1 Принципиальная схема

6.2 Программная реализация библиотеки

6.3 Форматы входных и выходных данных

• Конструктивно-технологическая часть проекта
• 7. Технология программирования
• 7.1 Модели на основе инженерного подхода
• 7.2 Модели, учитывающие специфику разработки ПО
• 7.3 Современные модели
• 7.4 Модели быстрой разработки
• 7.5 Адаптированные и комбинированные модели
• 8. Выбор языка программирования
• 8.1 Анализ инструментальных средств
• 9. Охрана труда
• 9.1 Расчет защитного заземления
• 9.2 Электробезопасность рабочего места с ПЭВМ
• 10. Экологическая часть
• 10.1 Микроклимат
• 10.2 Защита от шума
• 11. Решение задачи на ЭВМ
• 11.1 Структура классов и пример функционирования
• Заключение
• Список использованной литературы


Введение

кластерный программирование алгоритм

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

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

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

Список областей, в которых применяется кластеризация очень большой: это работа с изображениями, маркетинговые исследования, прогнозирование, текстовый анализ, обнаружение мошеннических действий и многие другие[28]. Сегодня кластеризация является первым шагом анализа данных. Задачи кластеризации формируются в различных научных направлениях: в статистике, оптимизации, машинном обучении, что породило множество различных синонимов понятия кластера - класс, таксон, сгущение. Сегодня уже применяются несколько десятков алгоритмов разбиения и множество их модификаций. Зачастую данные с которыми приходится работать этим алгоритмам обусловлены такими особенностями как высокая размерность и сверхбольшой объём данных (миллионы записей в тысячах полей), так же содержание большого количества числовых (numerical), которые способны упорядочиваться в пространстве, и категорийных (categorical), неупорядочивающихся, атрибутов. Атрибуты получают значения согласно типу шкалы, выбор которой является отдельной задачей.

В своей основе алгоритмы кластеризации сравнивают между собой объекты на основе различных мер сходства или близости, величины, имеющей предел и возрастающей по мере схожести объектов. Эти меры сходства выбираются в зависимости от задачи и шкалы измерений[36]. Для числовых атрибутов очень часто применяют евклидово расстояние:

,

а категорийные атрибуты сравнивают при помощи меры Чекановского-Серенсена и Жаккара

.

Необходимость обрабатывать огромные объёмы данных позволила сформулировать ряд требований для алгоритма кластеризации. Рассмотрим эти требования. Минимизация итераций обращения к данным

1. Ограниченность ресурсов, в частности памяти системы

2. Восстанавливаемость алгоритма

3. Работа алгоритма с базой данных в режиме однонаправленного курсора.

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

Трудно соблюсти баланс между высоким качеством кластеризации и масштабируемостью. Поэтому в идеале в арсенале Data Mining должны присутствовать как эффективные алгоритмы кластеризации микромассивов (Microarrays), так и масштабируемые для обработки сверхбольших баз данных (Large Databases).



Специальная часть проекта

1. Актуальные проблемы кластерного анализа

Несмотря на большое число исследований в области кластерного анализа, в этой области существует ряд актуальных проблем. Можно сформулировать основные[28]:

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

1. Анализ большого числа разнотипных данных порождает методологическую проблему выбора метрик. Так же увеличение числа объектов даже однотипных данных может повлечь за собой неразличимость расстояний.

2. Нелинейность взаимосвязей. Классические методы снижения размерности в кластерном анализе направлены на линейной взаимосвязи между переменными. Для поиска более сложных зависимостей необходимо переходить к ядерным методам.

3. Проблема поиска глобального экстремума функции критерия качества. Критерий качества, как правило, является функцией, зависящей от большого числа факторов, нелинейным, обладающим множеством локальных экстремумов. Для нахождения кластеров необходимо решить сложную комбинаторную задачу поиска оптимального варианта классификации. Поэтому алгоритм полного перебора вариантов имеет трудоемкость, экспоненциально зависящую от размерности. Если число групп заранее неизвестно, то переборная задача становится еще сложнее. Таким образом, при увеличении размерности таблиц данных происходит «комбинаторный взрыв». Классические алгоритмы кластерного анализа осуществляют направленный поиск в сравнительно небольшом подмножестве пространства решений, используя различного рода априорные ограничения (на число кластеров или их форму, на порядок включения объектов в группы и т.д.). При этом нахождение строго-оптимального решения не гарантируется. Для поиска оптимального решения применяются более сложные методы, такие как генетические (эволюционные) алгоритмы, нейронные сети и т.д. Существуют экспериментальные исследования, подтверждающие преимущества таких алгоритмов перед классическими алгоритмами. Однако и при использовании эволюционных методов возникают проблемы, связанные со спецификой решаемой задачи кластер-анализа: с трудностью интерпретации используемых операторов рекомбинации и кроссовера.

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

5. Недостаточность знаний об объекте. Существует проблема трудноформализуемых областей, в которых становится затруднительным создание модели объекта. В таком случае становится затруднительным применение алгоритмов, основывающихся на представлении класса, как набора распределённых в пространстве переменных.

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

1.1 Задачи кластерного анализа

Кластерный анализ выполняет следующие основные задачи:

· Исследование схем группировки объектов;

· Выработка гипотез на базе исследований данных;

· Подтверждение гипотез и исследований данных;

· Определение присутствия групп внутри данных.

1.2 Этапы кластерного анализа

Независимо от предмета изучения применение кластерного анализа предполагает следующие этапы:

1. Формирование выборки для кластеризации;

2. Выделение признакового пространства;

3. Выбор меры сходства (расстояния) между объектами;

4. Применение метода кластерного анализа;

5. Проверка результатов кластеризации.

Существуют два ключевых требования к данным:

· Однородность - необходимость гарантировать единую природу всех кластеризуемых сущностей. То есть все объекты должны описываться схожим набором характеристик;

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



1.3 Цели кластеризации для выработки рекомендаций

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

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

· Выделение нетипичных объектов, аномалий или выбросов, для определения новизны кластеров или их количества. Наибольший интерес представляют отдельные объекты, не вписывающиеся ни в один из кластеров.

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

1.4 Построение ценовых (весовых) моделей

Методы кластеризации и классификации хорошо приспособлены к прогнозированию того, к какой категории относится какой-либо образец. Однако методы в их математическом виде не оптимальны для выборки прогнозов о числовых данных на основании различных атрибутов. Важной задачей так же становится учитывать распределение вероятностей прогноза и интерпретировать данные[29].

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

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

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

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

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



2. Техническое задание

2.1. Цель и назначение разработки

Цель разработки

Целью разработки является создание программной библиотеки для выработки рекомендаций на большом объеме данных. На основании кластерного анализа библиотека должна отыскивать взаимосвязи и выдавать рекомендации на основании пользовательских запросов построения. Разработанная библиотека должна внедряться в программные продукты, подключаться к базе данных и, получая информацию, распределять её.

Назначение разработки

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

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

2.2 Этапы разработки

1. Анализ требований к разработке

2. Анализ решений конкурентов

3. Проектирование библиотеки

4. Разработка и тестирование библиотеки

5. Написание документации

6. Тестовое внедрение в проект



2.3 Основные требования к программному обеспечению

Общие положения

Требования к программным решениям

Программное библиотека должна разрабатываться по модульному принципу. Каждый модуль должен работать с данными независимо, но использовать единый драйвер баз данных. Драйвер баз данных должен иметь методы записи и чтения через методы, формируя внутри себя SQL-запросы. При разработке библиотеки должен использоваться язык С++ со стандартной библиотекой классов. Допускается применение фреймворка «Qt» без использования элементов пользовательского интерфейса.

Требование к программному обеспечению

Библиотека должна встраиваться в проекты, разрабатываемые на языке С++ с применением фреймворка «Qt». Библиотека должна быть платформонезависимой и компилируемой MinGW или аналогом.

Состав программного комплекса

В библиотеку должны входить модули:

Кластеризации

Построение ценовых моделей

Выработка рекомендаций

Драйвер баз данных

Функциональные требования к СУБД

Общее назначение библиотеки:

1. Формировать набор данных для кластеризации

2. Выделять предполагаемое количество кластеров в конкретном наборе данных

3. Находить центройды и предполагаемую форму кластера

4. Ассоциировать новый экземпляр данных с кластером

5. Определять веса в наборах данных

6. Масштабировать векторы экземпляров

7. Принимать пользовательские запросы

8. Строить ценовую модель на основании пользовательского запроса

9. Ранжировать кластеры и экземпляры внутри кластеров по релевантности на основании пользовательского запроса



3. Обзор существующих решений

3.1 Иерархические методы кластеризации

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

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

В графической аналогии иерархические методы базируются на построении дендрограмм (от греческого dendron - "дерево"), которые описывают расстояния между отдельными точками и кластерами друг по отношению к другу.

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

Агломеративные AGNES (Agglomerative Nesting).

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

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

CURE

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

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

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

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

ROCK

Алгоритм кластеризации ROCK. Robust Clustering Algorithm - агломеративный иерархический алгоритм, для кластеризации большого количества данных с номинальными (булевыми) атрибутами[34].

Алгоритм по работе схож с K-means, но он учитывает наличие связи у общих соседей. Работа алгоритма построена на составлении матриц схожести. Это матрицы соседства кластеров, количества общих соседей, меры близости объектов. Соседство кластеров определяется отношением конъюнкции и суммы по модулю 2 двух кластеров. Формула определения близости объектов зависит количества объектов в каждом кластере и общих ссылок между двумя кластерами. После формирования матриц начинается итеративная кластеризация, находящая двух наиболее близких кластера, и объединяя их. При этом формируются новые значения в матрице общих ссылок и матрице близости, а данные о двух оригинальных кластерах удаляются. Критериями для завершения итераций являются либо достижения заданного их числа, либо сформировано указанное количество кластеров, все расстояния между кластерами нулевые или сформирован кластер больше заданного размера.

Дивизимные DIANA (Divisive Analysis):

Методы этой группы логически противоположны агломеративным, в начале их работы объекты находятся в одном кластере. В результате работы алгоритмов на каждом их шаге такой кластер будет делиться на меньшие, создавая последовательность расщепляющих групп[33].

BIRCH

Алгоритм предложен Тьян Зангом и его коллегами[37].

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

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

Тьян Занг приводит следующую аналогию в отношении алгоритма BIRCH: «Если каждый элемент данных представить себе как бусину, лежащую на поверхности стола, то кластеры бусин можно "заменить" теннисными шариками и перейти к более детальному изучению кластеров теннисных шариков. Число бусин может оказаться достаточно велико, однако диаметр теннисных шариков можно подобрать таким образом, чтобы на втором этапе можно было, применив традиционные алгоритмы кластеризации, определить действительную сложную форму кластеров.»

MST

Этот алгоритм основан на построении минимального остовного дерева (MST, minimum spanning tree). Граф строится на основании представления объектов как вершин, а расстояний между этими объектами как дуг. На полученный граф применяется метод построения минимального остовного дерева, причём может применяться любой известный метод, но с учётом большого числа дуг в графе (при N документах в коллекции - дуг). После этого удаляются ребра с наибольшими длинами, образуя лес небольших деревьев, узлы которых порождают кластеры.

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

3.2 Неиерархические (итеративные) методы кластеризации

С возрастанием объёмов данных иерархические методы теряют все свои привлекательные свойства, тогда эффективными могут оказаться неиерархические методы, представляющие из себя итеративные алгоритмы разделения исходной совокупности. То есть весь набор данных делится на определённое количество кластеров или пока не сработает правило остановки. В этой группе методов, используются два подхода, оба отличных от работы дивизимных иерархических принципов. Методы первого подхода определяют границы кластеров по наиболее плотным участкам многомерного пространства исходных данных. То есть происходит процесс поиска «сгущения точек». Методы второго подхода минимизируют меры различия объектов.

К-средних (k-means)

Это наиболее распространённый неиерархический метод, и возможно самый распространённый метод кластеризации в целом в связи с простотой его реализации[36].

Перед началом работы метода необходимо иметь предположение о вероятном количестве кластеров. K-means хорошо подходит для подтверждения гипотез о количестве кластеров и может использоваться данные от предыдущих вычислений, либо просто от интуитивно выбранного числа. Алгоритм сначала построит заданное количество кластеров, а после этого будет распределять объекты так, чтобы среднее среди всех переменных в кластере будут максимально отличными.

PAM (k-means + k-medoids)

Метод по своей сути является модификацией К-средних с применением К-медианы[30]. Работа алгоритма аналогична K-means, только объекты в нём распределяются не относительно центра кластера, а релятивно его медианы. Алгоритм лучше своего основоположника противостоит выбросам и шумам, поскольку медиана мене подвержена этим явлениям. К сожалению, алгоритм не преобразовался настолько, чтобы применяться к для больших объёмов данных.

Алгоритм CLARA (Clustering LARge Applications)

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

LargeItem

Алгортим LargeItem был предложен Вангом в 1990 году. Это оптимизационный алгоритм для кластеризации транзакционных данных, основанных на критериальной функции, оптимизации глобального критерия[35]. Этот глобальный критерий использует параметр поддержки (в терминологии здесь много общего с алгоритмами для выявления ассоциативных правил). В вычисление глобального критерия делает алгоритм кластеризации во много раз быстрее, чем при использовании локального критерия при парном сравнении объектов, поэтому "глобализация" оценочной функции - один из путей получения масштабируемых алгоритмов. Алгоритм включает в себя две фазы: фазу распределения и фазу улучшения. Лучшим решением является то, которое лучше минимизирует целевую функцию. Так как найти абсолютно точное решение не представляется возможным с достаточной долей вероятности, то цель этого алгоритма состоит в нахождении приближенного решения, что является достаточным для практического применения. В отличии от К-means, LargeItem позволяет значению k варьироваться, т.е. алгоритм не обязан знать её заранее. Чтобы избежать сканирования всех транзакций при кластеризации, некоторые кассетные функции, такие как |Large_i|, |U^k_i=1=Small_i| и | U^k_i=1=Large_i|, сохраняются после каждого распределения или перемещения транзакции.

Алгоритм использует некоторые стандартные методы индексации, такие как хэш-таблицы и B-дерева в обслуживании и обновлении, доступные для каждого кластера.

CLOPE

В 2002 году группа китайских учёных представила[35] алгоритм CLOPE (Clustering with sLOPE). Особенностью этого алгоритма является высокая производительность работы по сравнению с другими иерархическими методами. Работа этого алгоритма основана на максимизации глобальной функции стоимости, повышающей близость транзакций в кластерах с помощью увеличения параметра кластерной гистограммы.

С помощью параметра, названного авторами CLOPE коэффициентом отталкивания (repulsion), регулируется уровень сходства транзакций внутри кластера, и, как следствие, финальное количество кластеров. Этот коэффициент подбирается пользователем. Чем больше r, тем ниже уровень сходства и тем больше кластеров будет сгенерировано.

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

3.3 Сравнительный анализ иерархических и неиерархических методов кластеризации

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

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

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

За счет такого "варьирования" результатов достигается достаточно большая гибкость кластеризации.

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

Преимущество же этой группы методов в сравнении с неиерархическими методами - их наглядность и возможность получить детальное представление о структуре данных.

3.4 Сеточные алгоритмы

Алгоритм WaveCluster

Данные алгоритм относится к группе сеточных алгоритмов (Grid-based)

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

Среди сеточных алгоритмов так же выделяют STING, OptiGrid, GRIDCLUS, GDILC.

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

Метод	Достоинства	Недостатки
CURE	- Кластеризация высокого уровня даже при наличии выбросов - Выделение кластеров сложной формы и различных размеров - Обладает линейно зависимыми требованиями к месту хранения данных и временную сложность для данных высокой размерности	- Необходимость в задании пороговых значений и количества кластеров
BIRCH	- Двухступенчатая кластеризация, кластеризация больших объемов данных - Работает на ограниченном объеме памяти - Является локальным алгоритмом - Может работать при одном сканировании входного набора данных - Данные могут быть неодинаково распределены по пространству - Обрабатывает области с большой плотностью как единый кластер	- Работает только с числовыми данными - Хорошо выделяет только кластеры выпуклой или сферической формы - Необходимость в задании пороговых значений
MST	- выделяет кластеры произвольной формы (выпуклой и вогнутой форм) - выбирает из нескольких оптимальных решений самое оптимальное	- чувствителен к выбросам
k-средних	- Простота использования - Скорость работы - Понятность и прозрачность алгоритма	- Чувствителен к выбросам - Медленная работа на больших объёмах - Необходимо задавать количество кластеров - Невозможность применения алгоритма на данных, где имеются пересекающиеся кластеры - Не гарантируется достижение глобального минимума - Работа алгоритма сильно зависит от выбранных начальных центров кластеров, оптимальное значение которых не может быть известно заоанее
PAM	- Простота использования - Скорость работы - Понятность и прозрачность алгоритма - Менее чувствителен к выбросам в сравнении с k-means	- необходимо задавать количество кластеров; - медленная работа на больших базах данных
CLOPE	- масштабируемость - скорость работы - качество кластеризации, что достигается использованием глобального критерия оптимизации на основе максимизации градиента высоты гистограммы кластера. - легко рассчитывается и интерпретируется - малый объём ресурсов - автоматически подбирает количество кластеров - регулируется одним единственным параметром - коэффициентом отталкивания.
Алгоритм HCM	- Легкость реализации - Вычислительная простота	- задание количества кластеров - отсутствие гарантии в нахождении оптимального решения
Fuzzy C-means	- Нечеткость при определении объекта в кластер позволяет классифицировать пограничные объекты	- Вычислительная сложность - Задание количества кластеров - Неопределённость с выбросами
WaveCluster	- Может обнаруживать кластеры произвольных форм - Не чувствителен к шумам	- Сложность реализации - Применим только к данным низкой размерности

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



4. Обзор существующих систем кластеризации

4.1 Коммерческие инструменты

ClustanGraphics

На момент написания работы актуальная версия 8 (2005 год релиза). Инструмент основан на K-means, так же применяется иерархическая кластеризация. Программный пакет способен разделить миллион объектов на 20 тысяч кластеров. Мастер в программе позволяет импортировать данные из таблиц Excel, а представление результатов происходит в графическом виде.

BayesiaLab, includes Bayesian classification algorithms for data segmentation and uses Bayesian networks to automatically cluster the variables.

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

CViz Cluster Visualization это инструмент, разработанный на Java. Назначение - это кластеризация для визуального анализа.

CViz - это средство визуализации для анализа данных высокой размерности. Основной упор сделан на графическом представлении результатов анализа и предназначена для обзорного анализа. Работа программы проводится на методах линейного дискриминантного анализа.

IBM Intelligent Miner for Data

Специализированный прикладной интерфейс SQL API, который состоит из двух уровней с разной степенью детализации и абстракции.

Прикладной интерфейс задач Easy Mining является проблемно-ориентированным и используется для выполнения базовых задач интеллектуального анализа;

Прикладной интерфейс IM Scoring / Modeling SQL/MM API соответствует стандарту ISO/IEC 13249-6:Data Mining и позволяет создавать приложения интеллектуального анализа под конкретные индивидуальные требования пользователя. Этот интерфейс может быть использован через скрипты SQL, или из любого JDBC, CLI, ODBC, или SQLJ приложения. Приложение разработано компанией IBM как Java приложение. Есть возможность не использовать базы данных, а получать данные из таблиц Excel. Программный комплекс включает в себя модули оценки и моделирования, предоставляя набор инструментальных средств разработки программ. Результаты моделирования просматриваются при помощи готового Java продукта IM Visualization. А инструмент Design Studio интегрируется в среду Eclipse. Результаты моделирования данных (ассоциации, последовательности, классификации, кластеризации и регрессии) могут быть просмотрены с помощью готовых Java средств визуализации IM Visualization.

ELKI: Environment for Developing KDD-Applications Supported by Index-Structures

ELKI - это программный модульный фреймворк, разработанный на JAVA для исследований и обучения Профессором Хоано-Питеров Крейгелем в Мюнхенском университете Людвига Максимилиана. ELKI использует соединение алгоритмов разделения, типизации и индексации данных, различных методов расстояний. Система использует SQL для хранения даннх, формат SVG для вывода графических результатов, а для математических вводов применяется система LaTeX.

Алгоритмы 4C, COPAC, HiCO, ERiC, CASH были опубликованы в рамках диссертации, а их реализация удостоилась многих наград. Кластерный анализ включает в себя K-means, Максимизационные алгоритмы, односвязную кластеризацию. Включены такие алгоритмы как DBSCAN (Density-Based Spatial Clustering of Applications with Noise); OPTICS (Ordering Points To Identify the Clustering Structure), включая расширения OPTICS-OF, DeLi-Clu, HiSC, HiCO и DiSH; SUBCLU (Density-Connected Subspace Clustering for High-Dimensional Data). Используются априорные данные, динамическое оболочки. Сейчас программа имеет мажорную версии 0.

CLUTO

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

Название программной библиотеки	Достоинства	Недостатки
ClustanGraphics	Быстрая кластеризация миллиона объектов в 20 тысяч кластеров	Основан на K-means; Устаревшая версия от 2005 года Java-ориентирование приложение
BayesiaLab	Присутствие большой базы для решения прикладных задач; Применение Байсовских сетей	Продукт направлен на решение конкретных задач
CViz	Реализует методы линейного дискриминантного анализа	Основан на визуальную оценку данных экспертом
IBM Intelligent Miner for Data	Простота использования Быстрое представление данных	Java-ориентированое приложение. Коммерческий продукт IBM, очень тесно связан с другими продуктами IBM
ELKI	Очень мощный продукт, использующий множество актуальных и современных методов Много возможны форматов данных для работы Оценён наградами	На момент написания диплома находится в нулевой мажорной версии. Выход версии 1.0 не определён во времени.
CLUTO	Включает в себя графический и Веб модули



Выводы

Из вышеизложенного материала очевидно положительно выделяется алгоритм кластеризации CLOPE. Во время изучения материала были выделены группы методов, описанные ранее, следуя которым, алгоритм CLOPE является категорийным итеративным и транзакционным, что не может покрыть весь спектр задач, таких как например сферическая кластеризация с центроидом размерности на целочисленных значениях, совпадающей с объектом размерности. Для решения подобной задачи будет рассмотрен и добавлен в библиотеку алгоритм BIRCH, совмещённый с методом k-meanes.

Среди рассмотренных продуктов практически все ориентированы на Java-интеграцию. Практически все методы используют для своей работы SQL. Многие продукты заранее ориентированы на решение конкретных бизнес-задач. Целью моей работы стоит создание универсального инструмента на пользовательских данных, способного интегрироваться в разрабатываемые продукты, преимущественно на C++. Среди представленных систем ярко выделяется своими возможностями продукт ELKI, но это новый пакет, находящийся на стадии публичного тестирования, а время выхода первой стабильной версии неизвестно.



5. Предлагаемые методы и математическое обеспечение

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

CLOPE

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

Например, для набора транзакций {(a, b), (a, b, c), (a, c, d), (d, e), (d, e, f)} сравним два разбиения на кластеры:

1. {{ab, abc, acd}, {de, def}};

2. {{ab, abc}, {acd, de, def}}.

Рис. 5.1 Разбиение кластеризацией CLOPE

В первом случае кластер представляет четыре независимых уникальных объекта (a, b, c, d), которые входят в кластер количеством (3, 2, 2, 1) соответственно. Таким образом, кластер имеет ширину W=4, то есть включает в себя 4 типа объектов. Площадью S будем считать вхождение в кластер всех объектов, то есть S=3+2+2+1=8. Зная два этих параметра можно рассчитать высоту кластера H=S/W=8/4=2. Если тоже самое проделать с остальными с кластерами, то мы увидим, что при одинаковом количестве элементов в кластере параметры H, W, S могут произвольно меняться. Если посмотреть оба разбиения, то можно понять, что разбиение 1 выгоднее, так как обеспечивает большее число меньшее количество уникальных объектов и большее число наложений. Именно в этом заключается принцип максимизации стоимости.

Пусть D - множество транзакций {t1,…,tn}, где t - набор объектов {i1,…,in}. Найти такое множество кластеров {C1,…,Ck} для множества {t1,…,tn}, такое что

Гистограмма кластера - это графическое изображение его расчетных характеристик^.

Алгоритм должен учитывать высоту H при разбиении, потому что транзакция, максимально увеличивающая площадь по отношению к другим существующим кластерам, не увеличивая ширины, наиболее подходит к уже содержащимся в кластере транзакциям. Но оценка высоты не является эффективным критерием в случае разбиений с одинаковой высотой, например H=1. В таком случае вместо оценки высоты необходимо вычислять градиент G(C)=H(C)/W(C)=S(C)/W(C).

Обобщая, выведем формулу глобального критерия

(5.1.1.2)

Где |Ci| - количество объектов в i-м кластере

k - количество кластеров.

r - коэффициент отталкивания (repulsion), положительно вещественное число превосходящее 1.

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

Таким образом, постановка задачи кластеризации для алгоритма CLOPE выглядит так:

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

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

Вполне очевидно, что CLOPE - масштабируемый алгоритм, способный работать на ограниченных ресурсах. Во время его работы в памяти находится только текущая транзакция и кластерные характеристики (CF - cluster features). При вхождении 10 000 объектов в 1 000 кластер требуется всего около 40 Мб памяти для хранения данной информации.

Вычислительная сложность алгоритма возрастает линейно с увеличением таблицы и ростом числа кластеров, она равна O(N*K*A), где

N - общее число транзакций;

K - максимальное число кластеров;

A - средняя длина транзакции.

Таким образом алгоритм относится к эффективным на большим объёмах данных.

Данный алгоритм можно успешно применять не только для транзакционных данных, но и для любых категорийных. Основным требованием является нормализация данных. Это может быть бинарная матрица или отображение уникальных объектов {u1, u2, …, uq} и множеством целых чисел {1, 2, …, q}. Таким образом к виду транзакции можно свести любой набор данных, поэтому CLOPE находит своё место в обработке категорийных данных.

K-meanes

Теперь рассмотрим подробно самый популярный и простой в реализации алгоритм k-means. Этот алгоритм был открыть в различных дисциплинах Ллойдом (1957), Форджи (1965), Фридманом и Рубином (1967), а так же МакКуином (1967).

K-means применим к объектам в d-мерном векторном пространстве, представимых как набор D = {xi | i=1, …, N}, где xi ? Rd - i-й объект. Суть алгоритма состоит в объединении D так, чтобы каждая xi попала только в один k раздел. В результате образуется кластерный составной вектор m длиною N, где mi - номер кластера xi. Параметр k - входное значение для работы алгоритма и является конечным числом кластеров. Этот параметр является экспертным вводом, основанным на наблюдениях, анализе предварительных результатов или просто интуитивном предпочтении аналитика. Неважно каким будет значение k для понимание разделения набора данных, но оптимальное значение достигается путём ряда итеративных экспериментов.

В работе алгоритма каждый кластер представлен точкой в Rd и представляется как множество C={cj | j=1, …, k}. Эти состояния называют центроидами кластера. Для кластеризации применяются меры близости, в частности евклидово расстояние, уже рассмотренное ранее. Работа алгоритма заключается в минимизации функции стоимости, которая представлена как квадрат расстояния между каждой точкой xi и ближайшим представителем кластера cj.



(5.1.2.1)

Приведённое уравнение часто называют целевой функцией k-means.

Алгоритм строится в 2 шага, которые итеративно чередуются между собой:

1. Переписывание номера кластера для всех объектов в D

2. Обновление данных кластера по содержащимся в нём объектам

Сначала инициализируются представители кластера, но основании выборки k из Rd случайным образом, устанавливая их как решения подмножества, либо нарушая среднее значение данных k-раз. Затем выполняется итерации до сходимости за 2 шага:

1. Каждому объекту присваивается самый близкий представитель, произвольно нарушая связи данных, что приводит к их разделению;

2. Центроид кластера перемещается на место среднего арифметического всех объектов в кластере.

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

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

Реализация алгоритма:

1. Выберем случайным образом k точек из D как представителей класса C в соответствии с формулой (1)

2. Вычислим центр для каждого кластера

3. Перераспределим объекты по кластерам

Каждая итерация в таком случае будет иметь сложность O(N*k), а число итераций, необходимых неизвестно, но растёт с числом объектов N. Решение проблемы скорости в данном случае может быть предложено путём распределения вычислений на потомки, в этом случае необходимо разбить множество данных на P частей равному по значению количеству потоков, а каждый поток будет работать со своим набором данных.

Актуальной проблемой разбиения является проблема «пустых кластеров». Этот недостаток усиливается с увеличением числа k, когда в момент работы образуется центройд кластера cj, такой, что все точки xi в D оказываются ближе к центроиду другого кластера. В таком случае точки перераспределятся, а исходному кластеру будут назначены нулевые значения, образуя из него пустое множество. В таком случае необходимо предусмотреть переинициализацию центроида пустого кластера.

Несмотря на недостатки, алгоритм k-means является наиболее распространённым инструментом кластеризации на практике. Это простой и масштабируемый метод, который обладает достаточной эффективностью и способен работать как дополнение к более сложным методам, что я рассмотрю далее.

BIRCH

Алгоритм BIRCH представляет из себя двухэтапный процесс кластеризации, который хорошо кластеризует большие наборы числовых данных. Ранее был рассмотрен алгоритм k-means, который предполагается использовать как второй этап в данном методе. Хорошая связь этих методов состоит в том, что они оба работают с числовыми данными и строят кластеры сферических форм. Для работы алгоритма BIRCH необходимо только указание пороговых значений, а количество кластеров, необходимое для k-means будет определено во время первого этапа.

Рассмотрим работу алгоритма:

Построение начального CF-дерева (CF Tree, кластерное дерево). Кластерное дерево - это взвешенно сбалансированное двухпараметрическое дерево, где B- коэффициент разветвления, а T - пороговая величина. Каждый узел, не являющийся листом дерева, имеет не более B вхождений узлов, представленных в форме [CF_i, Child_i], где i=1, …, B; а Child_i - указатель на дочерний i-й узел. Лист дерева имеет указатель на два соседних узла, а радиус кластера, состоящего из элементов этого узла не должен превосходить пороговое значение.

Кластер представляется как тройка (N, LSS, SS), где N - число элементов входных данных кластера, LS - сумма элементов входных данных, SS - сумма квадратов элементов входных данных.

Сжатие данных (необязательный этап) осуществляется перестроением кластерного дерева с увеличением пороговой величины T.

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

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

5.2 Метод вычисления ценовых моделей

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

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



6. Структура системы

6.1 Принципиальная схема

6.2 Программная реализация библиотеки

Модуль ввода данных

Связь данных пользователя и данных работы библиотеки задаётся не произвольно. Надсистема библиотеки не может просто так подключить свою базу данных для обработки информации. В первую очередь это связано с необходимостью строго типизировать библиотеку и уменьшать абстракцию, следовательно, сжимать область применения программного продукта. Во-вторых, работая с абстрактными данными библиотека не получает прямого доступа к пользовательским данным, а так же не несёт в себе опасности кражи данных. Надсистема, использующая библиотеку перед началом работы должна передать конфигурации для подключения к заранее созданной базе данных. В этой базе будут размечены необходимые таблицы. Если таблицы уже существуют, то драйвер базы данных библиотеки продолжит заполнение таблиц информацией. После подключения к базе данных надсистема получает возможность передавать библиотеке данные в итеративном режиме по одному событию. Событием будем называть целочисленное значение, характеризованное двумя уникальными метками. Первая метка - идентификатор процесса, которому принадлежит событие, вторая - кэш имени события. Библиотека не обязана работать с истинными значениями процесса и события, поэтому надсистеме рекомендуется оперировать двумя хэш-таблицами вида «процесс | идентификатор» и «событие | кэш имени события». Ввод информации в систему образован в виде передачи функции добавления процесса с двумя строковыми и одним целочисленным параметрами. Первые два строковых параметра - это идентификатор процесса и кэш имени события соответственно, а третье, целочисленное, инкремент счётчика событий. При получении параметров, библиотека отыскивает в базе данных ячейку, соответствующую паре «идентификатор процесса - кэш имени события» и увеличивает её значение на значение инкремента. Если указанных процесса или события не существует, то происходит их создание. В базе данных также находятся две несвязанных таблицы - хэш таблица идентификатор «процесса | строка» и кэш имени «события | столбец». Удаление записей из базы данных библиотекой не предусмотрено, эта функция ложится на администратора базы данных и сторонние редакторы. В случае обновления исходных данных, рекомендуется сделать резервную копию существующей базы данных библиотеки, очистить текущее содержимое таблиц и агрегировать процессы заново. Это поможет не образовывать коллизий, а скорость выполнения данной операции O(N), где N - число процессов.

...