Большинство алгоритмов потоковой кластеризации ограничены однопроходным условием, то есть, поскольку мы используем набор потоковых данных, мы можем получить доступ к информации об одной точке данных только один раз. Хранение точек данных приведет к высоким требованиям к памяти, что невозможно для больших наборов данных. Доступные алгоритмы потоковой кластеризации обычно не учитывают эволюцию данных. Это приводит к плохой кластеризации, когда потоки данных развиваются с течением времени. Если мы рассмотрим потоковую передачу K-средств, она зависит от порядка поступления данных.
Авторы статьи о CluStream предлагают принципиально иной подход к проблеме, разделив процесс кластеризации на две составляющие.
- Онлайн-микрокластеризация
- Автономная макрокластеризация
Этот двухэтапный подход предлагает пользователям гибкость в изучении характера эволюции кластеров в разные периоды времени.
Во время онлайн-фазы сводная статистика полученных на данный момент точек данных эффективно сохраняется, так что ею можно управлять для обслуживания различных типов запросов. Онлайн-фаза удовлетворяет однопроходному ограничению, поэтому можно обрабатывать большие данные. В автономной фазе используется только сводная статистика, сохраненная во время онлайн-фазы, а не сам фактический набор данных. Таким образом, наша автономная фаза больше не ограничивается однопроходным условием. Это позволяет нам использовать эффективные автономные алгоритмы, чтобы предоставлять кластерам различную информацию. Чтобы продолжить, читатель должен быть знаком с двумя основными концепциями в статье:
- Микрокластеры: используются для хранения сводной статистики точек данных с точки зрения пространственной локальности и временных компонентов.
- Пирамидальные временные рамки: чтобы облегчить анализ эволюции кластера, информация о микрокластерах периодически сохраняется на постоянном носителе. Этот период изменяется пирамидально. В статье такое хранение называется «моментальным снимком», поэтому мы продолжим использовать этот термин.
Платформа потоковой кластеризации
После введения понятий и терминов мы углубимся в формальные определения.
Поток данных. Предполагается, что поток данных состоит из многомерных точек данных X1, X2,…, Xk, .., прибывающих во временные метки T1, T2,…, Tk. ,…. Каждая точка данных Xi представляет собой вектор d измерений Xi = {xi1, xi2,…, xid}.
Микрокластер: набор из n d-мерных точек данных X1, X2,…, Xn с отметками времени T1, T2,…, Tn, определенными как (2d + 3) кортеж. Представляется как (CF2X, CF1 X, CF2T, CF1T, n), где,
- CF2X - это d-мерный вектор, имеющий сумму квадратов всех n точек данных по каждому измерению. Например, если микрокластер имеет точки (a, b) и (c, d), полученные в моменты времени t1 и t2 CF2X = {a² + c², b² + d²}
- CF1X - это еще один d-мерный вектор, имеющий сумму компонентов каждой точки данных в микрокластере по каждому измерению. то есть CF1X = {a + c, b + d}
- CF2T = t1²+t2²
- CF1T = t1+t2
- n = количество точек данных, принадлежащих микрокластеру
Пирамидальные временные рамки: снимки хранятся на разных уровнях детализации в зависимости от давности. Моментальные снимки классифицируются по разным порядкам, которые могут варьироваться от 1 до журнала (T), где T = время, прошедшее с начала потока. Моментальный снимок i-го порядка происходит каждые α ^ i единиц времени, где α - целое число, а α ›1.
Например, когда T = 8 и α = 2, порядок и время сохраненных снимков выглядят следующим образом:
Снимок порядка 0 (2⁰ x единицы времени) - 0, 1, 2, 3, 4, 5, 6, 7, 8
Заказать 1 снимок (2¹ x единицы времени) - 0, 2, 4, 6, 8
Снимок порядка 2 (2² x единицы времени) - 0, 4, 8
Снимок порядка 3 (2³ x единицы времени) - 0, 8
Если мы выберем хранить только последние α + 1 (= 3) снимка каждого заказа, то снимки будут по адресу,
Снимок порядка 0 (2⁰ x единицы времени) - 6, 7, 8
Заказать 1 снимок (2¹ x единицы времени) - 4, 6, 8
Снимок порядка 2 (2² x единицы времени) - 0, 4, 8
Снимок порядка 3 (2³ x единицы времени) - 0, 8
Можно проверить следующие результаты,
- максимальный порядок любого снимка, хранящегося в T, равен logα (T)
- максимальное количество снимков в точке T равно (α + 1) logα (T)
- для любого указанного пользователем временного окна в ч можно найти хотя бы один моментальный снимок в пределах 2 ч единиц текущего времени (приближение временного горизонта). (Доказательство этого результата можно найти на странице 3 ссылки [1].
Например, если мы хотим найти моментальный снимок с коэффициентом 2 по сравнению с любым указанным пользователем временным окном для потока данных, работающего в течение 100 лет с детализацией по времени в 1 секунду, общее количество снимков, которые необходимо сохранить, составляет (2+ 1) * log2 (100 * 365 * 24 * 60 * 60) = 95, что является скромным требованием к хранилищу.
Мы можем улучшить приближение этого временного горизонта, сохраняя более (α + 1) снимков каждого порядка. Можно доказать, что если мы храним (α ^ l) + 1 моментальных снимков, временной горизонт можно приблизить к коэффициенту 1 + 1 / [α ^ (l-1)].
Из предыдущего примера, где мы хранили снимки разных порядков, можно увидеть, что многие снимки постоянно хранятся под разными порядками. Это можно понять из следующего. Снимок при T = 8 (2³) одновременно соответствует снимкам порядков 0, 1, 2, 3. Мы можем устранить эту избыточность хранилища, удалив все снимки порядка i, которые делятся на 2 ^ (я + 1 ). Также при сохранении нового снимка удаляется самый старый из этого порядка.
Онлайн-обслуживание микрокластеров
В любой момент поддерживается в общей сложности q микрокластеров. Значение q значительно больше натурального числа кластеров в наборе данных, а также значительно меньше количества точек данных в потоке. Это позволяет нам поддерживать высокий уровень временной и пространственной детализации при одновременном снижении требований к хранилищу. Обозначим q микрокластеров через M1, M2,…, Mq. Каждый микрокластер будет иметь связанный уникальный идентификатор, присвоенный при его создании.
Эти микрокластеры сохраняются, когда время на часах делится на α ^ i и снимки порядка i старше α ^ (l + i ) единицы времени удаляются.
Начальные q микрокластеров создаются с использованием автономного процесса. Используя начало потока данных и применяя алгоритм кластеризации k-средних, создайте q начальных кластеров. Когда после инициализации появляется новая точка данных, у нас есть два варианта:
- Поглотите новую точку в существующий кластер
- создать собственный кластер и добавить его в качестве первой точки
Решение основывается на расстоянии от новой точки до существующих кластеров. Сначала мы определяем максимальный граничный фактор для каждого кластера. Это среднеквадратичное отклонение точек данных в кластере, умноженное на коэффициент t. Если новая точка не лежит в границах ближайшего к ней кластера, нам нужно создать новый кластер. Это может быть результатом того, что новая точка является выбросом, или появлением нового естественного кластера в потоке данных. После создания нового кластера нам нужно уменьшить количество кластеров на один, чтобы поддерживать его на уровне q. Это можно сделать двумя способами:
- Удалить старый кластер
- объединить два кластера, которые расположены близко друг к другу
Сначала мы проверяем, можем ли мы удалить старый кластер. Для этого нам нужен определенный пользователем порог δ, и кластер, который не обновлялся много после T-δ, где T - текущее время, можно удалить. Для этого мы находим отметку актуальности каждого кластера. Этот штамп релевантности представляет собой среднее время прибытия последних m точек кластера. Это вычисляется путем нахождения m / (2n) -го процентиля точек в кластере M, предполагая, что отметки времени распределены нормально. Если штамп релевантности кластера старше T-δ, мы можем приступить к его удалению. Если ни один из микрокластеров не имеет значения, мы объединяем два кластера, которые находятся ближе всего друг к другу. Мы создаем список идентификаторов и добавляем уникальные идентификаторы объединенных кластеров. Эта операция выполняется при поступлении каждой точки данных.
Таким образом, в онлайн-компоненте мы обрабатываем каждую новую точку данных одним из двух способов, упомянутых выше, и сохраняем моментальные снимки каждые α ^ i раз.
Создание макро-кластера
Это автономная фаза и не ограничивается требованием однопроходности, как обсуждалось ранее. На этом этапе
- Входные данные - h (временной горизонт), k (номер макрокластера)
- Данные - сводная статистика в сохраненных снимках.
Читатель должен понять концепцию временного горизонта, прежде чем продолжить. Например, если текущее время - T, а временной горизонт - h, при создании макрокластера следует учитывать только данные, поступившие в течение периода (T-h, T). Можно отметить, что снимки, хранящиеся на каждом этапе, содержат всю историю потока данных до этого этапа. Чтобы понять создание микрокластеров, которые содержат информацию о данных, поступающих в период (T-h, T), читатель должен быть знаком со следующими двумя свойствами. Мы будем называть микрокластер для набора точек C как CFT (C).
- Пусть C1 и C2 - два набора точек. Тогда вектор кластерных признаков CFT (C1UC2) = CFT (C1) + CFT (C2).
- Пусть C1 и C2 - два набора точек, такие что C2 является подмножеством C1. Тогда вектор кластерных признаков CFT (C1-C2) = CFT (C1) - CFT (C2).
Рассмотрим ситуацию на часах tc и временном горизонте h. Мы можем найти снимок в tc-h1, где h1 - это приблизительное значение временного горизонта для h. Если мы обозначим микрокластеры в tc-h через S (tc-h1), а текущие микрокластеры через S (tc), то микрокластеры, соответствующие данным между (tc-h, tc), задаются как N (tc, h1) = S (tc) - S (tc-h1). Мы можем подвергнуть это N (tc, h1) процессу макрокластеризации.
Мы модифицируем алгоритм k-средних следующими способами, чтобы использовать его для процесса макрокластеризации.
- Начальные семена не случайны, они выбираются с вероятностью, пропорциональной количеству точек в каждом микрокластере.
- Расстояние от семени до любого микрокластера равно расстоянию между семенем и центроидом микрокластера.
- Новое начальное число для данного раздела определяется как взвешенный центроид микрокластеров в этом разделе.
Можно отметить, что для процесса макрокластеризации нам нужно всего два тщательно отобранных снапшота.
Анализ эволюции кластеров
Если мы хотим сравнить кластеры в два разных момента времени t1 и t2 (t2 ›t1), шаги следующие:
- Найдите N (t1, h) и N (t2, h), используя процесс, описанный в предыдущем разделе.
- Разделите микрокластеры в N (t1, h) U N (t2, h) на три категории:
- M-added (t1, t2) = кластеры в N (t2, h), для которых нет соответствующих идентификаторов в N (t1, h)
- M-удалено (t1, t2) = кластеры в N (t1, h), для которых нет соответствующих идентификаторов в N (t2, h)
- M-сохраненный (t1, t2) = кластеры, для которых некоторые или все идентификаторы являются общими для N (t1, h) и N (t2, h).
- Затем к этим трем категориям отдельно применяется алгоритм макрокластеров.
- Если поток данных не сильно изменился за (t1, t2), M-сохраненный будет содержать большую часть данных
- Если поток данных развился в (t1, t2), M-удалено и M-добавлено, будет большая часть данных.
Можно убедиться, что CluStream создает кластеры более высокого качества, чем традиционные алгоритмы потоковой кластеризации, особенно при эволюции данных. А моментальные снимки пирамидальных временных рамок позволяют пользователям получать ответы на многие типы запросов. CluStream также обладает хорошей масштабируемостью.
Справка:
[1] Чару К. Аггарвал, Цзявэй Хан, Цзяньюн Ван и Филип С. Ю. Платформа для кластеризации развивающихся потоков данных. Материалы 29-й конференции VLDB, Берлин, Германия, 2003 г..
