Adaptive Estimation of Weight Coefficient in a Time-weighted Incremental EM-algorithm for Data Streams.pdf Интеллектуальный анализ потоков данных на протяжении последних десятилетий вызывает живой интерес исследователей по всему миру. Кластерный анализ - эффективный инструмент анализа данных, закономерными являются многочисленные попытки его применения к потокам данных. В последние годы был предложен ряд алгоритмов динамической кластеризации, учитывающих специфику обработки потоков: высокую размерность, большой объем, постоянно поступающие измерения, которые требуют эффективных, работающих в режиме реального времени алгоритмов [1]. Впервые проблема кластеризации потоков данных, по-видимому, была затронута в 1980-е гг. в [2], а соответствующая модель формализована в 1998 г. [3]. В настоящее время публикуется множество работ, посвященных созданию и применению алгоритмов кластеризации к потокам данных, например [4-16]. Область применения динамической кластеризации данных достаточно широка. Такие алгоритмы востребованы при наблюдении за сложными системами, такими как информационные системы, компьютерные сети, в долговременных популяционных, когнитивных, социологических исследованиях в режиме реального времени [17-21]. Обработка больших объемов информации в режиме реального времени требует эффективных, быстродействующих алгоритмов, а также сжатия данных - необходимо отказаться от хранения всего массива данных (измерений). При этом информация, полученная недавно, зачастую имеет большую значимость, нежели старые данные. Еще одной важной задачей при разработке алгоритмов машинного обучения является сокращение количества параметров алгоритма (user-defined parameter) путем разработки адаптивных механизмов [1]. Такой механизм для определения параметра затухающего временного окна предложен в данной работе и может быть применен не только для описанного здесь алгоритма кластеризации [22], но и других, таких как DenStream [23]. 1. Динамический ЕМ-алгоритм для потока данных, взвешенных по времени В [22] на основе [24] путем применения затухающей оконной модели построен алгоритм, кластеризующий потоки данных, причем каждой точке соответствует весовой коэффициент w = w(At), являющийся функцией от времени, прошедшего с момента поступления измерения (точки), а вес кластера W(t) является суммой весов всех входящих в него точек. В качестве весовой функции выбрана w(At) = e-aAt (a>0), обладающая следующими свойствами: 1) в момент возникновения точка имеет вес, равный 1: w(0) = 1; 2) c течением времени вес точки монотонно убывает к 0: lim w(At) = 0; At 3) если известен вес точки через Ati ед. вр. после ее возникновения, то вес этой же точки еще через At2 ед. вр. рассчитывается по формуле w(At1+At2) = w(A^)w(At2); 4) если известен вес кластера в момент времени t и за последующий период времени длительности At в кластер не попадало новых точек, то его вес пересчитывается по формуле W(t+At) = W(t)w(At). Такой выбор весовой функции, во-первых, позволяет обрабатывать динамические данные в режиме реального времени; во-вторых, не требует хранения обработанных данных; в-третьих, учитывает «новые» данные с большими весами, чем «старые». Следует отметить, что подобный выбор весовой функции, обеспечивающей затухающее временное окно, является достаточно распространенной практикой и применен независимо, например в [23] (с точностью до основания). Пусть в некоторый момент времени набор измерений (назовем их исходными данными) разбит классическим ЕМ-алгоритмом на множество кластеров. Каждый кластер Ck представлен функцией плотности нормального распределения в пространстве характеристик: Ф(Х|Ц, I) = {(2п)11|ехр[(х-ц)т1-1(х-ц)]}-1/2, (1) где ц и £ - координаты центра и ковариационная матрица кластера, рассчитанные согласно соответствующим формулам для нормального распределения, xeRd - координаты новой точки, индекс к - номер кластера, для простоты опущен. Весовые коэффициенты кластеров в начальный момент времени устанавливаются равными количеству точек в них. Пусть теперь {x1, x2, ...}eRd - поток данных, т.е. точки, поступающие в последовательные моменты времени t1, t2, ... . В момент поступления очередной точки x она относится к одному из кластеров методом максимального правдоподобия. Вероятность пк принадлежности точки x к кластеру Ck с весом Wk определяется формулой = WkФк (^ fa, 2к ) (2) 1K1W Ф (( ц,, Z,). () При появлении в потоке очередной точки x выполняется следующий алгоритм. Вход: x - новая точка, цк, £к, Wk- характеристики и веса кластеров (к = 1,2,...,K), At - время, прошедшее с момента получения предыдущей точки. 1. Пересчитать веса кластеров Wk = e-aAtWk. 2. Рассчитать вероятности попадания точки x в кластеры согласно (2). Отнести x к одному из кластеров методом максимального правдоподобия. 3. Для этого кластера произвести пересчет центра ц, ковариационной матрицы £ и веса W: W^ + x _ W L (ц_- x)2 ^ ; W=W+1, w+1 ц+ = ,„ ., ; 2+ = w+1 W+1 где индексы «-» и «+» соответствуют значениям до и после пересчета, индекс к опущен. Заметим, что весовая функция содержит параметр a > 0, причем при a = 0 разработанный алгоритм совпадает с [24]. Данный параметр влияет на скорость устаревания точки: при его возрастании точка устаревает скорее. Очевидно, он может быть определен отдельно для каждого кластера и зависит от множества факторов: скорости изменения параметров кластера, частоты поступления точек и т.п. 2. Адаптивный алгоритм расчета параметра весовой функции Назовем точку, полученную в момент времени t0, незначимой в момент времени t = t0+At, если ее вес ниже наперед заданного малого значения в (0 < в i+V (t;-t0), где ^ - реализация нормально распределенной случайной величины со средним ц0 и ковариационной матрицей Е0, i = 1,2,.,N. Тогда, обозначив среднее для N последних точек как ц, имеем ц _ £i=1 xi _ £i=1 + V ^N=1(ti ~ t0) NN N ' Среднее всех есть оценка для ц0, поэтому для V можно построить оценку V _ N(Ц-Ц0) V _х ;_i(t,(4) приняв в качестве ц0 оценку центра кластера в момент времени t0. Для пересчета a предложим следующий подход. В начальный момент времени можно принять a = 0, т.е. предположить, что центр кластера не смещается. При попадании в кластер каждой точки накапливать значения ц и знаменателя в (4), а при попадании каждой N-й точки - пересчитывать a согласно (4) и (3). Такой подход позволяет не хранить обработанные точки для алгоритма пересчета a так же, как и для алгоритма кластеризации. Относительно выбора параметра N можно сделать следующие предположения: N должно быть достаточным для репрезентативности выборки; с другой стороны, при увеличении N снижается частота пересчета коэффициента a. Таким образом, выбор N определяется желаемой частотой пересчета параметра затухания a и ограничен снизу минимально необходимым объемом выборки. Результаты экспериментов, иллюстрирующие вопрос качества оценивания скорости в зависимости от выбора N, приведены в третьем пункте. В случае возможности выделить для каждого кластера хранилище точек объема N; предложим другой подход к пересчету параметра a: при поступлении в кластер новой точки она добавляется в хранилище вместо самой старой, значение a пересчитывается согласно (4) и (3). В этом случае пересчет параметра затухания происходит при поступлении в кластер каждой точки, и N ограничено лишь выделенным объемом хранилища точек, с одной стороны, и минимальным значением для репрезентативности выборки - с другой. 3. Вычислительный эксперимент Разработанный алгоритм был реализован на С#. Было проведено несколько серий экспериментов, в каждом из которых моделировалось 9 000 точек в одном кластере, центр которого смещался с постоянной скоростью, а ковариационная матрица оставалась неизменной. Рассчитывались оценки скорости согласно (4) при различных N. В момент поступления каждой точки производилась оценка скорости V, для скаляра которой рассчитывалась относительная погрешность 5 = |v-v|/v, были получены выборочные средние V , 5 среднеквадратические отклонения oV, о5. Перечисленные выборочные характеристики при ^ (400 0 ^ | V | = 0,04 ед.расст./ед.вр. и постоянной ковариационной матрице Е = 0 400 приведены в табл. 1. С увеличением N погрешность, в среднем, уменьшается, как и ее среднеквадратическое отклонение. Т а б л и ц а 1 Результаты эксперимента при v = 0,04 N 100 250 500 V 0,0724 0,0394 0,0346 av 0,0196 0,0079 0,0044 s 0,8281 0,1682 0,1544 as 0,4574 0,1041 0,0820 Траектория скаляра оценки скорости в сравнении с траекторией истинного его значения, для упомянутого эксперимента при N = 500 приведен на рис. 1. Рис. 1. Траектории скаляров оценки скорости (черная линия) и его истинного значения (серая линия) при N = 500 Был проведен вычислительный эксперимент, в котором для одних и тех же исходных параметров было смоделировано 30 комплектов данных, полученных в трех кластерах с нормальным распределением в R2, причем местоположение центров кластеров изменялось со временем. Начальное положение центра первого кластера = (650,700), ковариационная матрица диагональная, а111 = а221 = 700 (здесь верхний индекс - номер кластера), скорость движения центра v1 = 7 ед.расст./ед.вр. Для второго кластера ц2 = (100, 300), ковариационная матрица также диагональная, а112 = а222 = 400, v2 = 5 ед.расст./ед.вр, для третьего аналогично ц3 = (550, 500), ац3 = а223 =200, v3 = 4 ед.расст./ед.вр, Направления скоростей задавались случайным образом. Точки моделировались с интервалом в 1/3 ед.вр. с равными вероятностями попадания в каждый из кластеров. Обработка данных производилась предложенным алгоритмом, пересчет параметра a производился согласно (3) и (4). В момент окончания расчетов для каждого эксперимента было вычислено отношение отклонения оцененного центра кластера от истинного к истинному среднеквадратическому отклонению Ац^/ац^. Гистограммы их частот по всем 30 экспериментам приведены на рис. 2. 0,7 0,6 0,5 0,4 0,3 0,2 0,1 0,35 а 0,7 0,6 0,5 0,4 0,3 0,2 0,1

Скачать электронную версию публикации