V Международная студенческая научная конференция Студенческий научный форум - 2013

Введение

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

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

Решением этих задач занимается кластерный анализ.

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

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

Основные понятия

Кластеризация – общее название множества вычислительных процедур, используемых при создании классификации объектов. В результате кластеризации образуются “кластеры” (регионы, области) – группы похожих по различным характеристикам процессов.[1]

Можно выделить два основных признака кластера:

1. внутренняяоднородность – объекты внутри одного кластера должны быть максимально схожи между собой:

2. внешняяизолированность – объекты из одного кластера должны быть как можно меньше схожи с объектами из другого кластера.

Исходные данные для процедуры кластеризации– набор объектов, каждый из которых задается вектором своих характеристик. Алгоритмы кластеризации позволяют обрабатывать следующие наборы данных:

 содержащие только категориальные (нечисловые) атрибуты

 содержащие только числовые атрибуты

 содержащие смешанные атрибуты (категориальные и числовые) [1,7]

В качестве примера набора объектов можно рассмотреть:

1.Изображения

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

2. Текстовые данные

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

Техника кластеризации применяется в самых разнообразных областях:

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

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

В маркетинговых исследованиях. Например, для позиционирования: определения в какой нише лучше позиционировать выводимый на рынок продукт. Кластерный анализ позволяет построить карту, на основе которой можно будет определить уровень конкуренции в различных сегментах и характеристики, которыми должен обладать товар для того, чтобы попасть в целевой сегмент. Такая карта позволяет, к примеру, выявить новые рынки, для которых можно разрабатывать и продвигать свои решения. [2]

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

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

Процедура кластеризации происходит в 6 этапов:

Подробнее о некоторых этапах кластеризации:

II этап – Выбор меры расстояния: Выбор метрики, по которой определяется близость объектов. Она выбирается в зависимости от пространства, в котором расположены объекты и неявных характеристик кластеров.

III этап – Выбор метода кластеризации: Выбор алгоритма кластеризации.

V этап - Интерпретация профилирование кластеров: Данный включает проверку кластерных центроидов. Центроиды представляют средние значения объектов, содержащиеся в кластере по каждой из переменных. Они позволяют описывать каждый кластер, если присвоить ему номер или метку. [8]

В ходе процедуры кластеризации происходит объединение “подобных” объектов в отдельные классы. Результатом кластеризации является набор классов, содержащих однородные объекты [1,4].

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

• представление кластеров центроидами;

• представление кластеров набором характерных точек;

• представление кластеров их ограничениями.

Классификация алгоритмов

Существует несколько классификаций алгоритмов кластеризации:

1. по способу обработки данных:

1.  

   1. иерархические

При иерархической кластеризации выполняется последовательное объединение меньших кластеров в большие или разделение больших кластеров на меньшие [5].

Достоинства:

• строит оптимальное разбиение

• представление результата в виде дендрограммы(дерева)

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

Недостатки:

• вычислительная сходимость

• кластеры не пересекаются

• вычислительная сложность

1.  

   1. плоские

Задачу кластеризации можно рассматривать как построение оптимального

разбиения объектов на группы. При этом оптимальность может быть определена на

основе выбранного функционала качества(функционал среднего риска, функционал

ошибки и т.д.).

Достоинства:

● простота реализации;

● интуитивная понятность и прозрачность алгоритма;

Недостатки:

● число кластеров надо знать заранее;

● зависимость результата от инициализации центров

кластеров;

● вычислительная сложность;

1. по способу анализа данных:

1.  

   1. нечеткие

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

Рассмотрев ряд алгоритмов, можно сделать следующие выводы.

Достоинства:

• нечеткость при определении объекта в кластер

Недостатки:

• вычислительная сложность;

• задание количества кластеров;

1.  

   1. четкие

Четкие (или непересекающиеся) алгоритмы каждому объекту выборки ставят в соответствие номер кластера, т.е. каждый объект принадлежит только одному кластеру.

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

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

Алгоритм CURE

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

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

Недостатки: есть необходимость в задании пороговых значений и количества кластеров.

Описание алгоритма [6]:

Шаг 1: Построение дерева кластеров, состоящего из каждой строки входного набора данных.

Шаг 2: Формирование «кучи» в оперативной памяти, расчет расстояния до ближайшего кластера (строки данных) для каждого кластера. При формировании кучи кластеры сортируются по возрастанию дистанции от кластера до ближайшего кластера. Расстояние между кластерами определяется по двум ближайшим элементам из соседних кластеров. Для определения расстояния между кластерами используются «манхеттенская», «евклидова» метрики или похожие на них функции.

Шаг 3: Слияние ближних кластеров в один кластер. Новый кластер получает все точки входящих в него входных данных. Расчет расстояния до остальных кластеров для новообразованного кластера. Для расчета расстояния кластеры делятся на две группы: первая группа – кластеры, у которых ближайшими кластерами считаются кластеры, входящие в новообразованный кластер, остальные кластеры – вторая группа. И при этом для кластеров из первой группы, если расстояние до новообразованного кластера меньше чем до предыдущего ближайшего кластера, то ближайший кластер меняется на новообразованный кластер. В противном случае ищется новый ближайший кластер, но при этом не берутся кластеры, расстояния до которых больше, чем до новообразованного кластера. Для кластеров второй группы выполняется следующее: если расстояние до новообразованного u1082 кластера ближе, чем предыдущий ближайший кластер, то ближайший кластер меняется. В противном случае ничего не происходит.

Шаг 4: Переход на шаг 3, если не получено требуемое количество кластеров.

Алгоритм BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies).

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

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

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

Блок-схема работы алгоритма:[12]

 

Корень

Корень

Внутренние узлы

Конечные узлы

 

СF – представление точек данных в кластере

B – количество записей, которые имеет каждый неконечный узел

L – количество записей, которые имеет каждый конечный узел

Описание алгоритма:

Фаза 1: Загрузка данных в память.

Построение начального кластерного дерева (CF Tree) по данным (первое сканирование набора данных) в памяти;

Алгоритм построения кластерного дерева (CF Tree):

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

Кластерное дерево – это взвешенно сбалансированное дерево с двумя параметрами: B – коэффициент разветвления, T – пороговая величина. Каждый нелистьевой узел дерева имеет не более чем B вхождений узлов следующей формы: [CFi, Childi], где i = 1, 2, …, B; Childi – указатель на i-й дочерний узел. Каждый листьевой узел имеет ссылку на два соседних узла. Кластер состоящий из элементов листьевого узла должен удовлетворять следующему условию: диаметр или радиус полученного кластера должен быть не более пороговой величины T.

Фаза 2 (необязательная): Сжатие (уплотнение) данных.

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

Фаза 3: Глобальная кластеризация.

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

Фаза 4 (необязательная): Улучшение кластеров.

Использует центры тяжести кластеров, полученные в фазе 3, как основы. 3

Перераспределяет данные между «близкими» кластерами. Данная фаза гарантирует попадание одинаковых данных в один кластер.

ART1

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

Алгоритм ART1 работает с объектами, которые называются векторами признаков. Вектор признаков является группой значений в двоичном коде, которые представляют определенный тип информации. Примером вектора признаков может служить, например, выбор покупок. Каждый объект вектора признаков показывает, приобрел ли покупатель товар (если да, то значение равно 1, если нет – 0).[10]

Основные параметры алгоритма:

1. побитовый вектор: результат побитового «И» для двух векторов

2. количество значимых элементов вектора

3. количество векторов-прототипов

4. параметр внимательное: для определения размера класса

5. вектор-прототип: является центром кластера

6. вектор признаков

7. размер векторов

8. бета-параметр: используется в уравнении проверки на схожесть

Блок-схема работы для данного алгоритма:[10]

 

Выражение 3.1

Выражение 3.1

Выражение 3.1

 

Алгоритм:

Шаг 1. Инициируются параметры сети.

Шаг 2. До тех пор, пока не соблюдаются условия остановки, выполняются шаги 3 - 10. Шаг 3. Для каждого входного вектора или изображения выпол­няются шаги 4 - 9.

Шаг 4. Предъявляется входной вектор и вычисляются выходные сигналы нейронов входного слоя .

Шаг 5. Пока не соблюдаются условия сброса или возврата к поиску нового Y-нейрона, выполняются шаги 6 - 8.

Шаг 6. Находится незаторможенный Y-элемент, имеющий наибольший выходной сигнал. Шаг 7. Вычисляются выходные сигналы нейронов интерфейсного слоя.

Шаг 8. С помощью параметра сходства проверяются усло­вия сброса или возврата (они различны для сетей АРТ-1 и АРТ2). Если они выполняются, тогда выделенный Y-элемент затормаживается и произво­дится возврат к шагу 5. Если условия сброса не выполняются, тогда выделенный кандидат из Y-слоя допускается к обучению на шаге

Шаг 9. Производится обучение выделенного Y-элемента.

Шаг 10. Проверяются условия остановки. Если они не выполняются, то переход к шагу 2, в противном случае - переход к шагу 11.

Шаг 11. Остановка.

В данной работе были рассмотрены лишь 3 алгоритма: CURE, BIRCH, ART1, которые дают наиболее полное представление о классе иерархических алгоритмов.

Вывод

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

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

Список литературы

1. Ким Д.О., Мьюллер Ч.У., Клекка У.Р. Факторный, дискриминантный и кластерный анализ. – М.: Финансы и статистика, 1989. – 215 с.

2. Girish Punj and David W. Stewart Journal of Marketing Research, Vol. XX, (May 1983), pp.134-148

3. http://wseweb.ru/stat/klasteru.htm

4. Классификация и кластер, Под ред. Райзина Д. В. – М.: Мир, 1980. – 393 с.

5. И. А. Чубукова Data Mining. Учебное пособие. – М.: Интернет-Университет Информационных технологий; БИНОМ. Лабораториязнаний, 2006. – 382 с.: ил., табл. – (Серия «Основы информационных технологий»).

6. Дорофеюк А. А. Алгоритмы автоматической классификации: Обзор // Автоматика

и телемеханика. – 1971. – № 12. – С. 78—113.

7. Jain, A.K., Murty M. N., and Flynn P. J. Data Clustering: A Review, ACM Computing Surveys, vol. 31, 3, 264-323,1999

8. 184. Малхотра, Н.К. Маркетинговые исследования: практ. руководство / Н.К. Малхотра — 3-е изд.: пер. с англ. -М.: Изд. дом «Вильяме», 2003. — 960 с.

9. 1. John F. Gantz "A Forecast of Worldwide Information Growth Through 2010" The Expanding Digital Universe, 2007

10. Программирование искусственного интеллекта в приложениях / М. Тим Джонс ; Пер. с англ. Осипов А. И. - М.: ДМК Пресс, 2004. - 312 с: ил.

11. http://life-prog.ru/view_neyrocomputer.php?id=1

12. http://avid.cs.umass.edu/courses/745/f2010/notes/DataMining.htm

Код для цитирования: Скопировать