Нечеткая кластеризация потоков данных с помощью ЕМ-алгоритма на основе самообучения по Т. Кохонену

Размещено на http://www.allbest.ru/

Нечеткая кластеризация потоков данных с помощью ЕМ-алгоритма на основе самообучения по Т. Кохонену

Е.В. Бодянский, А.А. Дейнеко,

А.А. Заика, Я.В. Куценко

Аннотация

В работе предложен мягкий вероятностный нечеткий алгоритм кластеризации многомерных данных, последовательно поступающих на обработку в режиме реального времени. Развиваемый подход предназначен для решения задач Dynamic Stream Mining в условиях перекрывающихся классов, по сравнению со своими прототипами значительно проще в вычислительной реализации, не использует никаких вероятностных предположений о природе обрабатываемых данных.

Ключевые слова: кластеризация, нечеткая логика, вычислительный интеллект, самообучение, нечеткая кластеризация, самоорганизующаяся карта Т. Кохонена.

Задача кластеризации больших массивов многомерных наблюдений (векторов-образов) часто встречается во многих реальных практических задачах, а для ее решения разработано множество алгоритмов [1-3], при этом в последние годы в рамках концепции Big Data особое внимание уделяется обработке информации, хранящейся либо в сверхбольших базах данных (VLDB), либо поступающей на обработку в on-line режиме в форме потока данных (data stream). Для решения этих задач с успехом может быть использован математический аппарат вычислительного интеллекта (computational intelligence) [4-7] и, прежде всего, искусственные нейронные сети и мягкие вычисления (soft computing), основанные на нечеткой логике. Понятно, что известные системы вычислительного интеллекта должны быть существенно модифицированы для обработки больших объемов информации. последовательно поступающей на обработку.

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

,

который необходимо разбить на кластеров, при этом это число может быть заранее не известно, т.е. . Очевидно, что столь большое число известных методов решения задачи кластеризации связано с тем, что сегодня не существует универсального алгоритма пригодного для эффективного использования во всех возникающих ситуациях. Одна из таких возможных и достаточно сложных ситуаций связана с предположением, что каждый вектор наблюдений может одновременно относиться с различными уровнями возможностей, вероятностей или принадлежностей не к одному, а сразу к нескольким или ко всем формируемым кластерам. В этой ситуации на первый план выходят, так называемые, мягкие алгоритмы (soft algorithms) [8], среди которых наибольшее внимание привлечено к нечетким методам кластеризации [9-11] и вероятностным алгоритмам (probabilistic model-based algorithms) [8], среди которых для обработки больших массивов широкое распространение получил, так называемый, ЕМ-алгоритм (Expectation-Maximization algorithm) [12-17], в основе которого лежат сугубо вероятностные предпосылки. Каждый из отмеченных подходов имеет свои достоинства и недостатки, в связи с чем представляется целесообразным разработка численно простой мягкой процедуры кластеризации, объединяющей в себе достоинства вероятностного и фаззи-подходов и предназначенной для обработки потоков данных, поступающих в on-line режиме.

ЕМ-алгоритм вероятностной кластеризации. Задача вероятностной кластеризации в общей постановке сводится к проблеме самообучения при неизвестном числе областей [18], при этом предполагается, что плотность распределения данных в каждом кластере подчиняется многомерному нормальному (гауссовскому) закону

(1)

а совместная плотность распределения всех данных описывается смесью

(2)

где мерный вектор-центроид го кластера, корреляционная матрица го кластера такая, что

(3)

априорные вероятности (веса), подчиняющиеся естественному условию

(4)

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

Здесь можно отметить, что показатель степени экспоненты в (1), (2) есть расстояние Махаланобиса между и наблюдением , т.е.

(5)

а условие (4) совпадает с условием, накладываемым на сумму принадлежностей в популярном алгоритме нечетких C-средних (FCM) Дж. Бездека [9]

(6)

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

Работа ЕМ-алгоритма состоит из повторяющейся последовательности двух шагов, при этом на шаге Е (expectation step) производится оценивание параметров совместного распределения (2), а на шаге М (maximization step) максимизируется критерий самообучения в виде логарифмической функции правдоподобия

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

И, наконец, для оценки вероятности принадлежности наблюдения му кластеру используется выражение

(7)

удовлетворяющее условию (4).

Частным случаем ЕМ-алгоритма является популярный метод кластеризации K-средних и совпадающий с ним при и единичных корреляционных матрицах . При этом метод K-средних является четкой процедурой, что означает, что каждое наблюдение может быть отнесено к единственному кластеру. При этом метод K-средних существенно проще с вычислительной точки зрения чем ЕМ-алгоритм и связан с минимизацией критерия самообучения, основанного на евклидовых расстояниях

(8)

алгоритм кластеризация многомерный данные

где

(9)

ЕМ-алгоритм также относится к процедурам, основанным на расстояниях, и в этом смысле близок к, так называемому, методу K-средних Махаланобиса, являющемуся четкой процедурой, минимизирующей целевую функцию

(10)

где и определяется выражениями (3), (9).

Принципиальная разница между ЕМ-алгоритмом и методом K-средних Махаланобиса состоит в том, что последний дает однозначное решение о принадлежности каждого наблюдения единственному кластеру, в то время как вероятностная процедура учитывает возможность перекрытия классов с расчетом вероятностей согласно выражению (7).

Наряду с несомненными достоинствами ЕМ-алгоритм обладает и рядом существенных ограничений. Во-первых, исходные данные должны иметь случайную природу и подчиняться нормальному закону распределения, во-вторых, на М-этапе возможно «застревание» процесса оптимизации в локальных экстремумах (эта проблема может быть преодолена с помощью использования процедур многоэкстремальной оптимизации), в-третьих, с вычислительной точки зрения это все-таки довольно громоздкая процедура [8] и, наконец, подразумевается, что весь массив данных, подлежащих кластеризации, задан заранее и не изменяется в процессе обработки.

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

Нечеткая вероятностная кластеризация на основе WTA-правила самообучения. Результат минимизации критерия самообучения (8) метода K-средних имеет вид среднего арифметического данных каждого кластера

(11)

где количество наблюдений , отнесенных к кластеру .

Если же данные поступают на обработку последовательно в on-line режиме, решение (11) может быть получено с помощью кластеризирующей нейронной сети Т. Кохонена [19], настройка синаптических весов которой, являющихся по сути компонентами векторов-центроидов, производится с помощью тех или иных алгоритмов конкурентного самообучения, наиболее популярным из которых является WTA-правило (“Winner Takes All”). При этом сама процедура настройки подобно ЕМ-алгоритму состоит из последовательности двух этапов: конкуренции (соответствует Е-шагу) и синаптической адаптации [20] (соответствует М-шагу).

Суть конкурентного обучения по Кохонену состоит в том, что если к моменту поступления наблюдения рассчитаны координаты центроидов , среди них выбирается «победитель» ближайший в смысле евклидова расстояния

(12)

к (Е-шаг), который и уточняется на М-шаге с помощью рекуррентной процедуры

(13)

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

Несложно заметить, что первое соотношение (13) есть не что иное, как градиентная минимизация (8), т.е. может быть переписано в виде

(14)

Аналогично (14) может быть введена градиентная процедура минимизации критерия (10) на основе метрики Махаланобиса (5) в виде

или

(15)

Несложно заметить, что алгоритм самообучения (15) является по сути последовательной реализацией метода K-средних Махаланобиса, т.е. позволяет получить только четкое решение.

Для оценки уровня принадлежности отдельных наблюдений в случае перекрывающихся классов вместо громоздкого выражения (7) целесообразно воспользоваться оценкой, принятой в стандартном FCM-алгоритме Дж. Бездека, используя вместо расстояния метрику Махаланобиса в виде

(16)

Таким образом, процедура нечеткой вероятностной кластеризации (15), (16), являясь своеобразным гибридом ЕМ-алгоритма, метода K-средних Махаланобиса, алгоритмов нечеткой кластеризации Бездека [9] и Гата-Гевы [10] и нечеткой кластеризующей нейронной сети Кохонена в ее адаптивном варианте [21, 22], характеризуется вычислительной простотой и позволяет анализировать данные, последовательно поступающие на обработку в on-line режиме.

Выводы

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

Литература

[1]Gan, G., Ma, Ch. and Wu, J., Data Clustering: Theory, Algorithms and Applications, Philadelphia: SIAM, 2007, 466 p.

[2]Xu, R. and Wunsch, D.C., Clustering, IEEE Press Series on Computational Intelligence. Hoboken, NJ: John Wiley & Sons, Inc., 2009, 370 p.

[3]Aggarwal, C.C. and Reddy, C.K., Data Clustering. Algorithms and Application, Boca Raton: CRC Press, 2014, 648 p.

[4]Rutkowski, L., Computational Intelligence. Methods and Techniques, Berlin-Heidelberg: Springer-Verlag, 2008, 514 p.

[5]Mumford, C. and Jain, L., Computational Intelligence. Collaboration, Fuzzy and Emergence, Berlin: Springer-Vergal, 2009, 726 p.

[6]Kruse, R., Borgelt, C., Klawonn, F., Moewes, C., Steinbrecher, M. and Held, P., Computational Intelligence. A Methodological Introduction, Berlin: Springer, 2013, 488 p.

[7]Du, K.-L. and Swamy, M.N.S., Neural Networks and Statistical Learning, London: Springer-Verlag, 2014, 824 p.

[8]Aggarwal, C.C., Data Mining, Cham: Springer, Int. Publ., Switzerland, 2015, 734 p.

[9]Bezdek, J.-C. Pattern Recognition with Fuzzy Objective Function Algorithms, N.Y.: Plenum Press, 1981, 272 p.

[10]Gath, I. and Geva, A.B., Unsupervised optimal fuzzy clustering, Pattern Analysis and Machine Intelligence, 1989. vol. 2, no.7, pp. 773-787.

[11]Bezdek, J.C. Keller, J., Krishnapuram, R. and Pal, N., Fuzzy Models and Algorithms for Pattern Recognition andImage Processing. The Handbooks of Fuzzy Sets, Kluwer, Dordrecht, Netherlands: Springer, 1999. vol. 4, 776 p.

[12]Dempster, A.P., Laird, N.M. and Rubin, D.B., Maximum likelihood from incomplete data via the EM algorithm, J. of the Royal Statistical Society, 1977, Ser.B, vol. 39, no.1, рр. 1-38.

[13]Hathaway, R., Another interpretation of the EM algorithm for mixture distributions. J. of Statistics & Probability Letters, 1986, vol. 4, pp. 53-56.

[14]Meng, X.L. and Rubin, D.B., Maximum likelihood estimation via the ECM algorithm:a general framework, Biometrica, 1993, vol. 80, рр. 267-278.

[15]Liu, C. and Rubin, D.B., The ECME algorithm: A simple extension of EM and ECM with faster monotone convergence, Biometrica, 1994, vol. 81, рр. 633-648.

[16]Fessler, J.A. and Hero, A.O., Space - alternating generalized EM algorithm, IEEE Trans. on Signal Processing, 1994. vol .42, pp. 2664-2677.

[17]Friedman, J., Hastie, T. and Tibshirani, R., The Elements of Statistical Learning. Data Mining, Inference and Prediction, Berlin: Springer, 2003, 552 p.

[18]Tsypkin, Ya.Z., Foundations of learning systems theory, M.: Nauka, 1970. (in Russion)

[19]Kohonen, T. Self-Organizing Maps, Berlin: Springer-Verlag, 1995, 362 p.

[20]Haykin, S., Neural Networks. A Comprehensive Foundation, Upper Saddle River, N.J.: Prentice Hall, Inc., 1999, 842 р.

[21]Gorshkov, Ye., Kolodyaznhiy, V. and Bodyanskiy, Ye., New recursive learning algorithms for fuzzy Kohonen clustering network, Proc. 17th Int. Workshop on Nonlinear Dynamics of Electronic Systems, Rapperswil, Switzerland, 2009, pp. 58-61.

[22]Bodyanskiy, Ye., Kolchygin, B.V. and Pliss, I.P., Adaptive neuro-fuzzy Kohonen network with variable fuzzifier, International Journal «Information Theories and Applications», Sofia: ITHEA, 2011. vol.18, no3, pp. 215-223

Размещено на Allbest.ru