научная статья по теме АВТОМАТИЧЕСКОЕ ОПРЕДЕЛЕНИЕ КОЛИЧЕСТВА КОМПОНЕНТ В EM-АЛГОРИТМЕ ВОССТАНОВЛЕНИЯ СМЕСИ НОРМАЛЬНЫХ РАСПРЕДЕЛЕНИЙ Математика

Текст научной статьи на тему «АВТОМАТИЧЕСКОЕ ОПРЕДЕЛЕНИЕ КОЛИЧЕСТВА КОМПОНЕНТ В EM-АЛГОРИТМЕ ВОССТАНОВЛЕНИЯ СМЕСИ НОРМАЛЬНЫХ РАСПРЕДЕЛЕНИЙ»

ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2010, том 50, № 4, с. 770-783

автоматическое определение количества компонент в em-алгоритме восстановления смеси нормальных распределений^

(* 119992 Москва, Ленинские горы, 1, МГУ, ф-т ВМиК; ** 119333 Москва, ул. Вавилова, 40, ВЦ РАН) e-mail: vetrovd@yandex.ru; dmitry.kropotov@gmail.com; osokin.anton@gmail.com Поступила в редакцию 24.07.2009 г. Переработанный вариант 11.11.2009 г.

Классический EM-алгоритм восстановления смеси нормальных распределений не позволяет определять количество компонент смеси. В данной работе предлагается алгоритм автоматического определения числа компонент ARD EM, основанный на методе релевантных векторов. Идея алгоритма состоит в использовании на начальном этапе заведомо избыточного количества компонент смеси с дальнейшим определением релевантных компонент с помощью максимизации обоснованности. Эксперименты на модельных задачах показывают, что количество найденных кластеров либо совпадает с истинным, либо немного превосходит его. Кроме того, кластеризация с помощью ARD EM оказывается ближе к истинной, чем у аналогов, основанных на скользящем контроле и принципе минимальной длины описания. Библ. 14. Фиг. 1. Табл. 4.

Ключевые слова: распознавание образов, восстановление плотностей, кластерный анализ, определение числа кластеров, ЕМ-алгоритм, байесовское обучение, автоматическое определение релевантности.

В работе рассматривается ЕМ-алгоритм разделения смесей нормальных распределений (см. [1]) как инструмент для решения задачи кластеризации. Классический ЕМ-алгоритм решает данную задачу при фиксированном числе кластеров. Число кластеров — структурный параметр, настройка которого является сложной задачей. Целью данного исследования является разработка метода автоматического определения числа кластеров.

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

Для определения числа компонент смеси здесь используются методы так называемого байесовского обучения (см. [2]), которые в настоящее время широко применяются для решения задач выбора модели. В частности, авторами предложено применить прием, аналогичный использованному в методе релевантных векторов (ЯУМ, см. [3]). Его идея заключается в использовании индивидуальных коэффициентов регуляризации для каждого фактора, необходимость учета которого в модели не очевидна. В методе релевантных векторов в качестве таковых факторов выступают обобщенные признаки (базисные функции). В данной работе к факторам предложено отнести кластеры (компоненты смеси). Настройка индивидуальных коэффициентов регуляризации осуществляется путем максимизации так называемой обоснованности (правдоподобия) модели (см. [4]). На основе этой процедуры разработана модификация ЕМ-алгоритма, позволяющая, в отличие от аналогов, за один проход определять не только параметры компонент смеси, но и их количество. В работе проведено сравнение предложенного подхода с более простым ва-

1) Работа выполнена при финансовой поддержке РФФИ (коды проектов 08-01-00405, 08-01-90427, 08-01-90016, 0901-12060, 07-01-00211) и программы Президиума РАН № 2.

риантом определения числа кластеров путем последовательного запуска EM-алгоритма с возрастающим количеством компонент и последующим подсчетом обоснованности. Среди других альтернатив рассмотрен способ оценки числа кластеров с помощью минимизации длины описания (см. [5]), а также с помощью скользящего контроля. Кроме того, проведено сравнение с "идеальным" методом, который использует информацию об истинном числе компонент смеси.

Работа состоит из трех разделов. В разд. 2 приводится описание классического EM-алгоритма как исходного объекта для дальнейших исследований. В разд. 3 описывается теоретическое построение предлагаемого алгоритма ARD ЕМ. Также в нем приведена краткая характеристика существующих аналогов. Разд. 4 посвящен результатам экспериментов, проведенных для оценки качества работы полученного алгоритма.

2. КЛАССИЧЕСКИЙ ЕМ-АЛГОРИТМ 2.1. Разделение смеси распределений

Определение 1. Смесью распределений для действительной многомерной случайной величины x е [ будем называть распределение с плотностью

p(x) = £юуру(х), £юу = 1, ffly ^ 0, j = 1, 2. K. (2.1)

Здесь K е N — количество компонент в смеси, юу- е [ — веса компонент, аp(x) : [ —»- [ — плотности распределения компонент смеси.

Пусть дана выборка X = 1 , xn е [ , N — число объектов в выборке. Пусть далее функции распределения компонент смеси заданы параметрически: p/x) = p(x|öj), j = 1, 2, . K. Тогда задача восстановления смеси распределений заключается в определении по выборке X параметров компонент K= 1 и весов Д 1 . В дальнейшем будем обозначать совокупность всех параметров

смеси через Е = = j = 1 .

Для решения задачи восстановления смеси воспользуемся методом максимального правдоподобия:

Eml = argmaxp( X\ Е) = arg max П P (Xn| Е). (2.2)

Переходя к логарифму правдоподобия, получаем следующую задачу условной оптимизации:

L(X, E) = logp(X E) = £ log £ ®jP(Xn| Öj) —- max, (2.3)

£fflj = 1, fflj ^ 0, j = 1, 2, . K. (2.4)

Функционал (2.3) имеет вид "логарифм суммы" и сложен для прямой оптимизации. Наиболее распространенным путем решения этой задачи является введение скрытых переменных с дальнейшим применением EM-алгоритма максимизации неполного правдоподобия (т.е. правдоподобия при наличии скрытых переменных). Известно (см. [6]), что EM-алгоритм для задачи разделения смесей распределения имеет ряд преимуществ перед другими методами оптимизации, такими как проекция градиента и ньютоновские алгоритмы. Поэтому ниже для решения задачи разделения смеси будет использоваться EM-алгоритм.

Рассмотрим вероятностную модель, эквивалентную (2.1). Для этого представим процесс генерации объекта из смеси распределений в два этапа: сначала с вероятностями, пропорциональными весам ю, выбирается одна компонента смеси, а затем из этой компоненты генерируется объ-

ект x. Формально для каждого объекта x вводится случайная переменная t, определяющая соответствующий x номер компоненты смеси:

, к I 1, если объект x взят из j-й компоненты смеси

p (x|t) = П [Pj (x )]J. (2.6)

Легко показать, что маргинальное распределение p(x) в вероятностной модели (2.5), (2.6) совпадает с распределением (2.1). В этом смысле модели (2.5), (2.6) и (2.1) эквивалентны.

2.2. Идея EM-алгоритма

EM-алгоритм позволяет максимизировать правдоподобие в вероятностных моделях со скрытыми переменными (см. [1]). Пусть имеется некоторая вероятностная модель, в которой часть переменных X известна, часть переменных T не наблюдается, а также имеется набор параметров Е. Задача состоит в отыскании параметров Е путем максимизации правдоподобия:

P(XЕ) = jp(X, T\Е)dT = j"p(X T, Е)p(T Е)dT — max.

EM-алгоритм представляет собой итерационную схему, состоящую из двух шагов. В начале выбирается некоторое значение параметров ЕоИ. Далее на первом шаге (E-шаг, ожидание) вычисляется апостериорное распределение на скрытые компоненты T при фиксированном значении параметров ЕоИ:

p (Т|Х,ЕоМ) = p (X T ЕоИ ) . (2.7)

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

Е^ = argmaxET|x,Holdlogp(X, T|Е). (2.8)

Шаги E и M повторяются в цикле до сходимости. Можно показать (см. [1]), что на каждой итерации значение логарифма правдоподобия не уменьшается. Таким образом, EM-алгоритм позволяет находить локальный максимум правдоподобия.

2.3. Применение EM-алгоритма для разделения смеси распределений Рассмотрим применение EM-алгоритма для вероятностной модели (2.5), (2.6), в которой в качестве скрытых переменных выступают номера компонент смеси T =

📎📎📎📎📎📎📎📎📎📎