Лекция №8. EM-алгоритм

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

Посмотрите нашу видео-лекцию, посвященную EM-алгоритму:

Каждый объект будем считать N-мерным вектором. В качестве исходных данных будем рассматривать M векторов

Xm=(xm1,xm2,...,xmN),    m=1,...M.

В алгоритме EM-кластеризации предполагается, что известно количество кластеров. Через K обозначим количество кластеров. Каждый кластер описывается N-мерным нормальным распределением, т.е. для каждого кластера задан вектор математических ожиданий

μk=(μk1k2,...,μkN),   k=1,...K

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

σ2k=(σ2k12k2,...,σ2kN),   k=1,...K.

Целью алгоритма является построение вероятностей, что объект Xm принадлежит кластеру k. Эти вероятности будем обозначать через gmk.

Опишем EM-алгоритм.

  1. Введем переменные wk= 1/K.
  2. Инициализируем математические ожидания для каждого кластера μkn=X1n,   k=1,...,K; n=1,...,N.
  3. Инициализируем дисперсии для каждого кластера
    σ2kn=1/(MK)[(X1nkn)2+ (X2nkn)2+...+(XMnkn)2].
  4. E-шаг

    gmk=(wkpk(Xm))/[w1p1(Xm)+w2p2(Xm)+...+ wKpK(Xm)],
    где pk(X) - плотность нормального распределения, соответствующее k-му кластеру.

    pk(Xm)=1/(Σk(2π)N/2)*exp[-((Xm1k1)2+...+(XmNkN)2)/(2Σ2k)],

    Σkk1k2*...*σkN.
  5. M-шаг

    wk=1/M[g1k+g2k+...+gMk]

    μkn=1/(Mwk)[g1kX1n+g2kX2n+...+gMkXMn]

    σ2kn=1/(Mwk)[g1k(X1nkn)2+ g2k(X2nkn)2+...+gMk(XMnkn)2].
  6. Шаги 4 и 5 повторять заданное количество раз.

После того как вероятности gmk построены, мы можем отнести объект Xm к кластеру с номером k', если gmk'=maxk{gmk}.

Рассмотрим пример применения EM-алгоритма. Программу и исходный текст на языке C# можно скачать: AI-EMSplit.

В качестве исходных данных возьмем данные о танках, которые мы уже использовали в уроке, посвященном кластеризации с помочью сети Кохонена.

НазваниеМассаДлинаШиринаМощность двигателяСкорость
PzKpfw I5.4402020605737
PzKpfw II8.94810222314040
PzKpfw III19.55380291028560
PzKpfw IV255890288030040
«Пантера»44.86870327070055
«Тигр»566316370570044
«Королевский тигр»687380375570038
Т-5013.85200247030060
Т-709.24285234814042
Т-34305920300050054
Т-4431.86070318050060
КВ-147.56675332060034
ИС-144.26770307052037
ИС-2466770307052037
ИС-3496900315052040

Попробуем классифицировать эти танки на два класса с помощью EM-алгоритма.

В результате применения нашего алгоритма мы получаем следующий результат:

НазваниеВероятность принадлежности первому кластеруВероятность принадлежности второму кластеру
PzKpfw I19.46E-23
PzKpfw II17.05E-16
PzKpfw III0.9999952964.70E-06
PzKpfw IV0.9953327840.004667216
«Пантера»2.95E-141
«Тигр»1.93E-181
«Королевский тигр»4.54E-251
Т-500.9999999973.02E-09
Т-7011.55E-17
Т-340.0007930870.999206913
Т-443.37E-050.99996627
КВ-11.99E-131
ИС-13.50E-101
ИС-29.89E-111
ИС-33.56E-121

Мы видим, что наши результаты полностью совпадают с классификацией сетью Кохонена.

Home | Лекции | Python | Видео | Скачать | Ссылки
Copyright (c) 2017, Roman Shamin
47
48608
30