Участник:Александр Куваев/Алгоритм кластеризации, основанный на максимизации ожидания: различия между версиями
| Строка 4: | Строка 4: | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| + | Задача кластеризации заключается в разбиении входного множества объектов на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались друг от друга. | ||
| + | |||
| + | Решение этой задачи принципиально неоднозначно по следующим причинам: | ||
| + | # результат кластеризации зависит от способа задания меры сходства объектов выборки | ||
| + | # не существует однозначно наилучшего критерия качества кластеризации | ||
| + | # число кластеров, как правило, неизвестно заранее и задается из некоторых априорных соображений (хотя существуют алгоритмы, способные определять число кластеров автоматически) | ||
| + | |||
| + | На этой странице представлено описание одного из методов кластеризации — EM-алгоритма. EM-алгоритм опирается на предположение о вероятностной природе данных: элементы выборки получены случайно и независимо из смеси распределений с фиксированным числом компонент <math>k</math>. Таким образом, плотность распределения на множестве объектов имеет следующий вид: | ||
| + | |||
| + | <math>p(x)=\sum_{j=1}^{k}w_{j}p_{j}(x), \sum_{j=1}^{k}w_{j}=1, w_{j} \ge 0 </math>, где <math>p_{j}</math> - плотность распределения <math>j</math>-й компоненты смеси. | ||
| + | |||
| + | В дальнейшем будем предполагать, что <math>p_{j}</math> имеют вид многомерных нормальных плотностей с произвольной матрицей ковариации: смеси нормальных распределений позволяют приближать произвольные непрерывные функции плотности с наперед заданной точностью. Результатом работы EM-алгоритма являются оценки априорных вероятностей компонент смеси <math>w_{j}</math>, а также оценки векторов математических ожиданий и матриц ковариации для каждой компоненты. | ||
| + | |||
| + | EM-алгоритм позволяет значительно упростить задачу максимизации правдоподобия выборки путем искусственного введения вспомогательной матрицы скрытых переменных <math>G</math>. Алгоритм заключается в итерационном повторении шагов E(expectation) и M(maximization): | ||
| + | * На шаге E на основе текущего приближения параметров смеси по формуле Байеса вычисляются ожидаемые значения скрытых переменных <math>g_{i,j}</math> — апостериорные вероятности того, что <math>i</math>-й объект принадлежит кластеру <math>j</math> | ||
| + | * На шаге M решается задача максимизации правдоподобия для нахождения следующего приближения параметров смеси на основе текущего приближения и вектора скрытых переменных | ||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
Версия 17:08, 12 октября 2016
Авторы описания: Куваев А.С. и Щенявская Е.В.
Содержание
- 1 Свойства и структура алгоритмов
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритмов
1.1 Общее описание алгоритма
Задача кластеризации заключается в разбиении входного множества объектов на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались друг от друга.
Решение этой задачи принципиально неоднозначно по следующим причинам:
- результат кластеризации зависит от способа задания меры сходства объектов выборки
- не существует однозначно наилучшего критерия качества кластеризации
- число кластеров, как правило, неизвестно заранее и задается из некоторых априорных соображений (хотя существуют алгоритмы, способные определять число кластеров автоматически)
На этой странице представлено описание одного из методов кластеризации — EM-алгоритма. EM-алгоритм опирается на предположение о вероятностной природе данных: элементы выборки получены случайно и независимо из смеси распределений с фиксированным числом компонент [math]k[/math]. Таким образом, плотность распределения на множестве объектов имеет следующий вид:
[math]p(x)=\sum_{j=1}^{k}w_{j}p_{j}(x), \sum_{j=1}^{k}w_{j}=1, w_{j} \ge 0 [/math], где [math]p_{j}[/math] - плотность распределения [math]j[/math]-й компоненты смеси.
В дальнейшем будем предполагать, что [math]p_{j}[/math] имеют вид многомерных нормальных плотностей с произвольной матрицей ковариации: смеси нормальных распределений позволяют приближать произвольные непрерывные функции плотности с наперед заданной точностью. Результатом работы EM-алгоритма являются оценки априорных вероятностей компонент смеси [math]w_{j}[/math], а также оценки векторов математических ожиданий и матриц ковариации для каждой компоненты.
EM-алгоритм позволяет значительно упростить задачу максимизации правдоподобия выборки путем искусственного введения вспомогательной матрицы скрытых переменных [math]G[/math]. Алгоритм заключается в итерационном повторении шагов E(expectation) и M(maximization):
- На шаге E на основе текущего приближения параметров смеси по формуле Байеса вычисляются ожидаемые значения скрытых переменных [math]g_{i,j}[/math] — апостериорные вероятности того, что [math]i[/math]-й объект принадлежит кластеру [math]j[/math]
- На шаге M решается задача максимизации правдоподобия для нахождения следующего приближения параметров смеси на основе текущего приближения и вектора скрытых переменных
