Разбиение на группы со схожими характеристиками категорийных и транзакционных массивов данных в больших БД является важнейшей задачей Data Mining. Традиционные алгоритмы кластеризации в большинстве случаев не эффективны при обработке сверхбольших баз данных. В материале рассказывается о масштабируемом эвристическом алгоритме CLOPE, который позволяет проводить кластеризацию с высоким качеством и производительностью.
Задачи кластеризации больших массивов категорийных данных весьма актуальна для систем анализа данных. Категорийные данные встречаются в любых областях: производство, коммерция, маркетинг, медицина… Категорийные данные включают в себя и так называемые транзакционные данные: чеки в супермаркетах, логи посещений веб-ресурсов. Сюда же относится анализ и классификация текстовых документов (Text Mining).
Здесь и далее под категорийными данными понимаются качественные характеристики объектов, измеренные в шкале наименований. Напомним: при использовании шкалы наименований указывается только, одинаковы или нет объекты относительно измеряемого признака.
Применять для кластеризации объектов с категорийными признаками традиционные алгоритмы неэффективно, а часто — невозможно (подробнее см. материал «Алгоритмы кластеризации на службе Data Mining»). Основные трудности связаны с высокой размерностью и гигантским объемом, которыми часто характеризуются такие базы данных.
Алгоритмы, основанные на парном вычислении расстояний (k-means и аналоги) эффективны в основном на числовых данных. Их производительность на массивах записей с большим количеством нечисловых факторов неудовлетворительная. И дело даже не столько в сложности задания метрики для вычисления расстояния между категорийными атрибутами, сколько в том, что на каждой итерации алгоритма требуется попарно сравнивать объекты между собой, а итераций может быть очень много. Для таблиц с миллионами записей и тысячами полей это неприменимо.
Поэтому в настоящее время ведутся активные исследования в области разработки масштабируемых (scalable) алгоритмов кластеризации категорийных и транзакционных данных. К ним предъявляются особые требования, а именно:
На сегодняшний день предложено свыше десятка методов для работы с категорийными данными, например, семейство иерархических кластерных алгоритмов. Но не всегда они удовлетворяют перечисленным выше требованиям. Одним из эффективных считается алгоритм LargeItem, который основан на оптимизации некоторого глобального критерия. Этот глобальный критерий использует параметр поддержки (в терминологии здесь много общего с алгоритмами для выявления ассоциативных правил).
Вообще, вычисление глобального критерия делает алгоритм кластеризации во много раз быстрее, чем при использовании локального критерия при парном сравнении объектов, поэтому «глобализация» оценочной функции – один из путей получения масштабируемых алгоритмов.
Алгоритм CLOPE, который мы рассматриваем в данной статье, очень похож на LargeItem, но быстрее и проще в программной реализации. CLOPE предложен в 2002 году группой китайских ученых. При этом он обеспечивает более высокую производительность и лучшее качество кластеризации в сравнении с алгоритмом LargeItem и многими иерархическими алгоритмами.
Для начала формализуем рассматриваемую задачу кластеризации для категорийных данных. Все изложение будет идти как будто бы у нас в наличии имеется база транзакционных данных, а в конце материала будет показано, как с помощью CLOPE разбивать на кластеры любые категорийные массивы, работая с ними как с транзакционными.
Под термином транзакция здесь понимается некоторый произвольный набор объектов, будь это список ключевых слов статьи, товары, купленные в супермаркете, множество симптомов пациента, характерные фрагменты изображения и так далее. Задача кластеризации транзакционных данных состоит в получении такого разбиения всего множества транзакций, чтобы похожие транзакции оказались в одном кластере, а отличающиеся друг от друга — в разных кластерах.
В основе алгоритма кластеризации CLOPE лежит идея максимизации глобальной функции стоимости, которая повышает близость транзакций в кластерах при помощи увеличения параметра кластерной гистограммы. Рассмотрим простой пример из 5 транзакций: \{ (a,b), (a,b,c), (a,c,d), (d,e), (d,e,f) \}. Представим себе, что мы хотим сравнить между собой следующие два разбиения на кластеры:
\{ \{ ab,abc,acd \}, \{ de,def \} \} , (1)
\{ \{ ab,abc \}, \{ acd,de,def \} \}, (2)
Для первого и второго вариантов разбиения в каждом кластере рассчитаем количество вхождений в него каждого элемента транзакции, а затем вычислим высоту (H) и ширину (W) кластера. Например, кластер \{ ab,abc,acd \} имеет вхождения a : 3, b : 2, c : 2, d:1 с H=2 и W=4. Для облегчения понимания на рис. 1 эти результаты показаны геометрически в виде гистограмм.
Рисунок 1. Гистограммы двух разбиений
Качество двух разбиений оценим, проанализировав их высоту H и ширину W. Кластеры \{ de,def \} и \{ ab,abc \} имеют одинаковые гистограммы, следовательно, равноценны. Гистограмма для кластера \{ ab,abc,acd \} содержит 4 различных элемента и имеет площадь 8 блоков (H=2.0,H/W=0.5), а кластер \{ acd,de,def \} — 5 различных элементов с такой же площадью (H=1.6,H/W=0.32). Очевидно, что разбиение (1) лучше, поскольку обеспечивает большее наложение транзакций друг на друга (соответственно, параметр H там выше).
На основе такой очевидной и простой идеи геометрических гистограмм и работает алгоритм CLOPE (англ.: Clustering with sLOPE). Рассмотрим его подробнее в более формальном описании.
Пусть имеется база транзакций D, состоящая из множества транзакций \{ t_1,t_2,…,t_n \}. Каждая транзакция есть набор объектов \{ i_1,…,i_m \}. Множество кластеров \{ C_1,…,C_k \} есть разбиение множества \{ t_1,…,t_n \}, такое, что C_1…C_k = \{ t_1,…,t_n \} и C_i\neq \varnothing \wedge C_i \bigcap C_j = \varnothing, для 1<=i, j<=k. Каждый элемент C_i называется кластером, n, m, k — количество транзакций, количество объектов в базе транзакций и число кластеров соответственно.
Каждый кластер C имеет следующие характеристики:
Гистограммой кластера C называется графическое изображение его расчетных характеристик: по оси OX откладываются объекты кластера в порядке убывания величины Occ(i,C), а сама величина Occ(i,C) — по оси OY (рис. 2).
На рисунке 2: S(C), W(C), H(C) упрощены до S, W , H соответственно.
На рис. 2 S(C)=8, соответствует площади прямоугольника, ограниченного осями координат и пунктирной линией. Очевидно, что чем больше значение H, тем более «похожи» две транзакции. Поэтому алгоритм должен выбирать такие разбиения, которые максимизируют H.
Однако учитывать одно только значение высоты H недостаточно. Возьмем базу, состоящую из 2-х транзакций: \{ abc,def \}. Они не содержат общих объектов, но разбиение \{ \{abc,def \} \} и разбиение \{ \{ abc \}, \{ def \} \} характеризуются одинаковой высотой H=1. Получается, оба варианта разбиения равноценны. Но если для оценки вместо H(C) использовать градиент G(C)=H(C)/W(C)=S(C)/W(C)^2, то разбиение \{ \{ abc \}, \{ def \} \} будет лучше (градиент каждого кластера равен 1/3 против 1/6 у разбиения \{ \{ abc,def \} \}).
Обобщив вышесказанное, запишем формулу для вычисления глобального критерия – функции стоимости Profit(C):
Profit (C) = \frac {\sum \limits_{i=1}^{k} G(C_i)\times\mid C_i\mid}{\sum \limits_{i=1}^{k} \mid C_i\mid}=\frac {\sum \limits_{i=1}^{k} \frac{S(C_i)}{W(C_i)^r}\times\mid C_i\mid}{\sum \limits_{i=1}^{k} \mid C_i\mid}
где:
С помощью параметра r, названного авторами CLOPE коэффициентом отталкивания (repulsion), регулируется уровень сходства транзакций внутри кластера, и, как следствие, финальное количество кластеров. Этот коэффициент подбирается пользователем. Чем больше r, тем ниже уровень сходства и тем больше кластеров будет сгенерировано.
Формальная постановка задачи кластеризации алгоритмом CLOPE выглядит следующим образом: для заданных D и r найти разбиение C: Profit(C,r) -> max.
Предположим, что транзакции хранятся в таблице базы данных. Лучшее решение ищется в течение последовательного итеративного перебора записей базы данных. Поскольку критерий оптимизации имеет глобальный характер, основанный только на расчете H и W, производительность и скорость алгоритма будет значительно выше, чем при попарном сравнении транзакций.
Реализация алгоритма требует первого прохода по таблице транзакций для построения начального разбиения, определяемого функцией Profit(C,r). После этого требуется незначительное (1-3) количество дополнительных сканирований таблицы для повышения качества кластеризации и оптимизации функции стоимости. Если в текущем проходе по таблице изменений не произошло, то алгоритм прекращает свою работу. Псевдокод алгоритма имеет следующий вид.
Как видно, алгоритм CLOPE является масштабируемым, поскольку способен работать в ограниченном объеме оперативной памяти компьютера. Во время работы в RAM хранится только текущая транзакция и небольшое количество информации по каждому кластеру, которая состоит из: количества транзакций N, числа уникальных объектов (или ширины кластера) W, простой хэш-таблицы для расчета Occ(i,C) и значения S площади кластера. Они называются кластерными характеристиками (CF – cluster features). Для простоты обозначим их как свойства кластера C, например, C.Occ[i] означает число вхождений объекта i в кластер C и т.д. Можно посчитать, что для хранения частоты вхождений 10 тыс. объектов в 1 тыс. кластерах необходимо около 40 Мб оперативной памяти.
Для завершения реализации алгоритма нам нужны еще две функции, рассчитывающие прирост Profit(C,r) при добавлении и удалении транзакции из кластера. Это легко сделать, зная величины S, W и N каждого кластера:
Здесь t.Items[i] — значение i-го объекта транзакции t. Заметим, что DeltaAdd(C,t,r) при добавлении t в новый кластер равна S/W^r, где S и W — площадь и ширина кластера, состоящего из добавляемой транзакции t.
Реализация функции прироста Profit(C,r) при удалении транзакции похожа на DeltaAdd(C,t,r), поэтому опустим ее подробный код.
Следующая теорема гарантирует корректность использования функции DeltaAdd.
Теорема. Если DeltaAdd(C_i,t) есть максимум, то перемещение t в кластерC_i максимизирует Profit(C,r).
Теперь можно оценить вычислительную сложность алгоритма CLOPE. Пусть средняя длина транзакции равна A, общее число транзакцийN, максимально возможное число кластеров K. Временная сложность одной итерации равна O( N*K*A ), показывающая, что скорость работы алгоритма растет линейно с ростом кластеров и размера таблицы. Это делает алгоритм быстрым и эффективным на больших объемах.
Рассказав о реализации алгоритма, мы ничего не сказали о виде таблицы транзакций, чтобы можно было применять алгоритм CLOPE. CLOPE позволяет решать задачи кластеризации не только транзакционных данных, но и любых категорийных. Главное, чтобы все признаки объектов были измерены в шкале наименований.
Однако перед тем как запускать CLOPE, данные необходимо привести к нормализованному виду. Он может иметь вид бинарной матрицы образов, как в ассоциативных правилах, так и представлять собой взаимно однозначное отображение между множеством уникальных объектов \{ u_1,…u_q \} таблицы и множеством целых чисел \{ 0,1,2,…,q-1 \}.
Задача о грибах (The mushroom dataset) – популярный тест, который применяют для оценки алгоритмов кластеризации категорийных наборов данных (доступен на UCI machine learning repository). Тестовая выборка содержит 8124 записи с описанием 22 характеристик грибов двух классов: 4208 съедобных (e) и 3916 несъедобных (p) грибов. Файл выборки имеет следующий вид:
{p, x, s, n, t, p, f, c, n, k, e, e, s, s, w, w, p, w, o, p, k, s, u}
{e, x, s, y, t, a, f, c, b, k, e, c, s, s, w, w, p, w, o, p, n, n, g}
{e, b, s, w, t, l, f, c, b, n, e, c, s, s, w, w, p, w, o, p, n, n, m}
{p, x, y, w, t, p, f, c, n, n, e, e, s, s, w, w, p, w, o, p, k, s, u}
{e, x, s, g, f, n, f, w, b, k, t, e, s, s, w, w, p, w, o, e, n, a, g}
.........
Общее количество уникальных характеристик объектов равно 116. 2480 записей имеют пропущенные значения в одном атрибуте. Описание набора данных — https://archive.ics.uci.edu/ml/datasets/mushroom.
Если такой набор данных представить в описанном выше нормализованном виде, то получится 8124 транзакции, из которых 2408 будут длиной 21, а остальные – 22 элемента (пропущенные значения игнорируются). И теперь можно применить алгоритм CLOPE. Результат работы CLOPE при r=2.6 для задачи о грибах после 1-ой итерации (фаза инициализации) представлен в таблице 1. При этом критерием качества работы алгоритма служит количество «грязных» кластеров, т.е. таких, в которых присутствуют как съедобные (e), так и несъедобные (p) грибы.
Чем меньше таких кластеров, тем лучше. Из таблицы 1 видно, что уже после 1-ой итерации остался только 1 «грязный» кластер №18. Потребуется еще пару-тройку сканирований базы данных для получения финальной кластеризации. Очевидно, что кластер 12 исчезнет.
Детальное исследование работы алгоритма CLOPE, проведенное его авторами, показало высокое качество кластеризации в сравнении с другими алгоритмами, в т.ч. иерархическими. При этом по скорости работы и производительности он обгоняет их в несколько раз.
| CLUSTER | e | p |
|---|---|---|
| 1 | 256 | |
| 2 | 512 | |
| 3 | 768 | |
| 4 | 96 | |
| 5 | 96 | |
| 6 | 192 | |
| 7 | 1296 | |
| 8 | 432 | |
| 9 | 149 | |
| 10 | 192 | |
| 11 | 1146 | |
| 12 | 1 | |
| 13 | 288 | |
| 14 | 192 | |
| 15 | 223 | |
| 16 | 48 | |
| 17 | 72 | |
| 18 | 48 | 32 |
| 19 | 8 | |
| 20 | 8 | |
| 21 | 1497 | |
| 22 | 192 | |
| 23 | 288 | |
| 24 | 32 | |
| 25 | 36 | |
| 26 | 8 | |
| 27 | 16 | |
| Итого | 4208 | 3916 |
Таблица 1: результат работы CLOPE после 1 итерации
Алгоритм CLOPE предназначен для работы с транзакционными данными, но, как мы увидели, очень много наборов данных с категорийными атрибутами представляют собой транзакционные данные либо сводятся к ним. Ответы респондента в анкете, список ключевых слов документа, множество посещенных веб-ресурсов пользователя, симптомы больного, характеристики гриба – все это не что иное, как транзакция. Поэтому области применения CLOPE распространяются на все массивы категорийных баз данных.
Вообще, кластеризация транзакционных данных имеет много общего с анализом ассоциаций. Обе эти технологии Data Mining выявляют скрытые зависимости в наборах данных. Но есть и отличия. С одной стороны, кластеризация дает общий взгляд на совокупность данных, тогда как ассоциативный анализ находит конкретные зависимости между атрибутами. С другой стороны, ассоциативные правила сразу пригодны для использования, тогда как кластеризация чаще всего используется как первая стадия анализа.
В завершение подчеркнем преимущества алгоритма CLOPE:
Другие материалы по теме:
