Алгоритмы кластеризации на службе Data Mining

Введение

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

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

На сегодняшний момент число методов разбиения групп объектов на кластеры довольно велико – несколько десятков алгоритмов и еще больше их модификаций. Однако нас интересуют алгоритмы кластеризации с точки зрения их применения в Data Mining.

Проблематика

Большим информационным системам свойственно постоянное поступление различной информации, которая накапливается, обсчитывается и архивируется. Мы рассмотрим вариант структурированных данных, хранящихся на сервере RDBMS Oracle и в качестве примера возьмём таблицу, содержащую CDR записи (т.е. записи о вызовах) для абонентов оператора связи.

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

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

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

Кластерному хранению можно приписать следующие характеристики:

  • Данные консолидируются по общему признаку.
  • Минимизируется Disk IO при доступе по кластерному ключу.
  • Минимизируется Disk IO при join по кластерному ключу при совместном хранении таблиц.
  • Характеризуется высоким Disk IO при наполнении.
  • Не очень дружен с Parallel DML — высокий уровень сериализации.
  • Данные, как правило, хранятся в порядке поступления.
  • Характерна высокая скорость наполнения.
  • Дружественно к Parallel DML.
  • С ростом объема данных может начаться деградация скорости вставки из-за индексов.
  • При высокоселективной выборке (по индексу) наблюдается высокий DiskIO.

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

  • Высокая скорость DML и вставки в частности.
  • Высокая скорость выборки.
  • Хорошая масштабируемость.
  • Лёгкость в администрировании.

Алгоритмы кластеризации на службе Data Mining

Один из способов повышения эффективности хранения данных это использование секционирования (Oracle Partitioning Option).

  • Разбивка в длину (сокращение времени деградации производительности вставки).
  • Разбивка в ширину (повышение масштабируемости).
  • Возможность управлять каждым сегментом в отдельности.
  • Высокая эффективность Parallel операций над сегментированными объектами.

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

Предположим, что две таблицы EQ сегментированы по некоторому идентификатору по hash(N). При EQ Partition Join операциях по этому идентификатору будет произведена операция HASH JOIN не на уровне таблиц, а на уровне секций с одинаковым значением hash. Это в разы сократит время, необходимое для проведения указанной операции на заданном объёме данных.

Хотелось бы ещё наделить секционированные таблицы эффективностью кластера по доступу к данным…

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

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

  • Создать таблицу с таким же набором полей, что и наша сегментированная таблица с тем же принципом hash-сегментирования, что и на нашей таблице, как:
    create table TBL1 as select * from table  %TBL% partition(P1) order by subscriber_id, record_date...
    

    , где P1 — секция за «позавчера».

  • Создать такие же индексы, как и на секции таблицы.
  • Выполнить операцию
    alter table %TBL% exchange partition P1 with table TBL1
    

    и заменить секцию на таблицу, содержащую те же данные, но в упорядоченном (ака: кластеризованном по subscriber_id) виде.

Алгоритмы кластеризации на службе Data Mining

P.S.{amp}gt; Можно автоматизировать данный процесс, используя пакет dbms_redefinition.

Вроде, всё выглядит просто, но каков, спросите вы, эффект?..Далее рассмотрим четыре случая:

  • Данные не реорганизованы.
  • Произведен rebuild индексов.
  • Произведена реорганизация.
  • Произведена реорганизация с компрессией данных.

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

Как мы видим, прирост меньше, чем при Phisical IO, но всё-равно увеличение происходит в разы.

Даже операция обычного rebuild индекса даёт сокращение его объема. Что же произойдёт с объемом дискового пространства при реорганизации данных, а также использования компрессии?

Алгоритмы кластеризации: блеск и нищета

Итак, уже можно классифицировать кластерные алгоритмы на масштабируемые и немасштабируемые. Продолжим классификацию.

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

Неиерархические алгоритмы основаны на оптимизации некоторой целевой функции, определяющей оптимальное в определенном смысле разбиение множества объектов на кластеры. В этой группе популярны алгоритмы семейства k-средних (k-means, fuzzy c-means, Густафсон-Кесселя), которые в качестве целевой функции используют сумму квадратов взвешенных отклонений координат объектов от центров искомых кластеров.

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

Среди неиерархических алгоритмов, не основанных на расстоянии, следует выделить EM-алгоритм (Expectation-Maximization). В нем вместо центров кластеров предполагается наличие функции плотности вероятности для каждого кластера с соответствующим значением математического ожидания и дисперсией. В смеси распределений (рис.

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

(1) {23, муж, высшее}(2) {25, жен, среднее}.

(1) {до 30 лет, муж, высшее}(2) {до 30 лет, жен, среднее}.

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

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

Алгоритм оптимизации целевой функции в неиерархических алгоритмах, основанных на расстояниях, носит итеративный характер, и на каждой итерации требуется рассчитывать матрицу расстояний между объектами. При большом числе объектов это неэффективно и требует серьезных вычислительных ресурсов. Вычислительная сложность 1й итерации алгоритма k-means оценивается как O(kmn), где k,m,n – количество кластеров, атрибутов и объектов соответственно. Но итераций может быть очень много! Придется делать много проходов по набору данных.

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

Впрочем, исследования в области совершенствования алгоритмов кластеризации идут постоянно. Разработаны интересные расширения алгоритма k-means для работы с категорийными атрибутами (k-modes) и смешанными атрибутами (k-prototypes). Например, в k-prototypes расчет расстояний между объектами осуществляется по-разному в зависимости от типа атрибута.

На рынке масштабируемых алгоритмов кластеризации борьба идет за снижение каждого “дополнительного” прохода по набору данных во время работы алгоритма. Разработаны масштабируемые аналоги k-means и EM (scalable k-means и scalable EM), масштабируемые агломеративные методы (CURE, CACTUS). Эти современные алгоритмы требуют всего несколько (от двух до десяти) сканирований базы данных до получения финальной кластеризации.

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

При задании глобальной функции оптимизации добавление новой точки в кластер не требует больших вычислений: оно рассчитывается на основе старого значения, нового объекта и так называемых кластерных характеристик (clusters features). Конкретные кластерные характеристики зависят от того или иного алгоритма. Так появились алгоритмы BIRCH, LargeItem, CLOPE и многие другие.

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

Литература

  • Bradley, P., Fayyad, U., Reina, C. Scaling Clustering Algorithms to Large Databases, Proc. 4th Int’l Conf. Knowledge Discovery and Data Mining, AAAI Press, Menlo Park, Calif., 1998.
  • Zhang, T., Ramakrishnan, R., Livny, M. Birch: An Efficient Data Clustering Method for Large Databases, Proc. ACM SIGMOD Int’l Conf. Management of Data, ACM Press, New York, 1996.
  • Paul S. Bradley, Usama M. Fayyad, Cory A. Reina Scaling EM (Expectation-Maximization) Clustering to Large Databases, Microsoft Research, 1999.
  • Z. Huang. Clustering large data sets with mixed numeric and categorical values. In The First Pacific-Asia Conference on Knowledge Discovery and Data Mining, 1997.
  • Milenova, B., Campos, M. Clustering large databases with numeric and nominal values using orthogonal projections, Oracle Data Mining Technologies, 2002.
  • Z. Huang. A fast clustering algorithm to claster very large categorical data sets in Data Mining. Research Issues on on Data Mining and KDD, 1997.
  • Wang, K., Xu, C.. Liu, B. Clustering transactions using large items. In Proc. CIKM’99, Kansas, Missouri, 1999.
  • Guha S., Rastogi R.,Shim K. CURE: An Efficient Clustering Algorithm for Large Databases, Proc. ACM SIGMOD Int’l Conf. Management of Data, ACM Press, New York, 1998.
  • Ganti V., Gerhke J., Ramakrishan R. CACTUS – Clustering Categorical Data Using Summaries. In Proc KDD’99, 1999.
  • J. Bilmes. A Gentle Tutorial on the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models, Tech. Report ICSI-TR-97-021, 1997.
  • Добыча данных в сверхбольших базах данных / В. Ганти, Й. Герке, Р. Рамакришнан // Открытые системы, №9-10, 1999.
  • Барсегян и др. Методы и модели анализа данных: OLAP и Data Mining. – СПб., 2004.

Заключение

https://www.youtube.com/watch?v=iDrojfU79s4

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

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

P.S.{amp}gt; Может показаться, что реорганизация большого объема данных сильно затратная операция. Это, конечно, да, но в итоге объем операций ввода/вывода можно сократить. На примере данных заказчика могу сказать, что обращение к реорганизуемой таким образом таблице только системой самообслуживания (а это менее половины нагрузки на таблицу) менее чем за час создавало объём ввода/вывода к данной таблице больше, чем размер всех её секций за сутки. Так что игра может стоить свеч, хоть и создаёт для ДБА дополнительную работу.

Поделиться:
Нет комментариев

Добавить комментарий

Ваш e-mail не будет опубликован. Все поля обязательны для заполнения.

×
Рекомендуем посмотреть
Adblock detector