Эта работа успешно выполнена
Преподавателю: в основное пространство, в подстраницу
Данное задание было проверено и зачтено.
Проверено Dexter и Преподаватель 1.

Авторы описания: Готман М.Л., Лукашкина Ю.Н.

Эта работа ждет рассмотрения преподавателем
Дата последней правки страницы: 16.11.2016
Авторы этой статьи считают, что задание выполнено.

ЧАСТЬ. Свойства и структура алгоритмов

Общее описание алгоритма

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

Для решения этой задачи можно использовать, например, метод максимизации ожидания, также известный как EM-алгоритм (англ. expectation-maximization) ^[1]. В таком случае делается предположение, что входные данные — смесь многомерных нормальных распределений, соотвественно отдельный кластер — это одна компонента смеси. Предполагается, что количество кластеров является входным параметром алгоритма (существуют модификации EM-алгоритма, которые автоматически находят число кластеров, но они не рассматриваются в данной статье). Результат работы EM-алгоритма — веса кластеров и найденные параметры нормальных распределений для каждого кластера: вектора математических ожиданий и матрицы ковариации.

Алгоритм EM кластеризации основан на итеративном выполнении двух последовательных шагов: E-шага и M-шага. На E-шаге вычисляются вспомогательные (скрытые) переменные, которые характеризуют апостериорную вероятность того, что определенный обучающий объект получен из фиксированной компоненты смеси. На M-шаге с помощью вычисленных скрытых переменных производится обновление параметров смеси: по определённым формулам пересчитываются веса кластеров, их математические ожидания и матрицы ковариаций.

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

В данной статье рассматривается частный случай EM-алгоритма, который работает с двумерными входными данными.

Математическое описание алгоритма

Рассматривается смесь многомерных нормальных распределений [math]\displaystyle{ p_j(x) = N(x;\mu_j, \Sigma_j) = \frac1{(2\pi)^{d/2}\sqrt{|\Sigma_j|}} \exp \biggl(-\frac{1}{2}(x - \mu_j) \Sigma_j^{-1} (x - \mu_j)^T\biggr) }[/math] с весами [math]\displaystyle{ w_j }[/math]: [math]\displaystyle{ p(x)=\sum_{j=1}^kw_jp_j(x), \sum_{j=1}^kw_j =1, w_j \ge 0 }[/math].

На вход алгоритму подаются [math]\displaystyle{ m }[/math] объектов, каждый из которых имеет [math]\displaystyle{ d }[/math] признаков, в виде матрицы объектов-признаков [math]\displaystyle{ X \in \R^{m \times d} }[/math] и [math]\displaystyle{ k }[/math] — количество кластеров.

Алгоритм кластеризации, основанный на максимизации правдоподобия, итеративно выполняет два шага: E-шаг и M-шаг. Идея алгоритма заключается в введении матрицы скрытых переменных [math]\displaystyle{ G }[/math], где [math]\displaystyle{ g_{ij} \equiv P(\theta_j |x_i) }[/math] обозначает вероятность принадлежности [math]\displaystyle{ i }[/math]-го объекта [math]\displaystyle{ j }[/math]-му кластеру.

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

На выходе получаем набор параметров модели для каждого кластера [math]\displaystyle{ \Theta = (w_1,...,w_k;\;\mu_1,...,\mu_k;\;\Sigma_1,...,\Sigma_k) }[/math], где [math]\displaystyle{ w_j }[/math] — вес [math]\displaystyle{ j }[/math]-го кластера в смеси нормальных распределений, [math]\displaystyle{ \mu_j }[/math] — математическое ожидание [math]\displaystyle{ j }[/math]-ой компоненты смеси, [math]\displaystyle{ \Sigma_j }[/math] — матрица ковариации [math]\displaystyle{ j }[/math]-ой компоненты смеси.

E-шаг:

На E-шаге вычисляется значение скрытых переменных [math]\displaystyle{ g_{ij} }[/math] по текущему приближению параметров [math]\displaystyle{ \Theta }[/math].

[math]\displaystyle{ g_{ij} = \frac{w_jp_j(x_i)}{\sum_{s=1}^k w_sp_s(x_i)} }[/math], что интерпретируется как вероятность принадлежности объекту [math]\displaystyle{ x_i }[/math] к [math]\displaystyle{ j }[/math]-ому кластеру.

M-шаг:

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

[math]\displaystyle{ Q(\Theta) = \ln\prod_{i=1}^mp(x_i) = \sum_{i=1}^m\ln\sum_{j=1}^kw_jp_j(x_i) \rightarrow \max_{\Theta} }[/math], при условии [math]\displaystyle{ \sum_{j=1}^kw_j=1 }[/math]

Решением оптимизационной задачи являются формулы для пересчета параметров:

[math]\displaystyle{ w_j = \frac1m\sum_{i=1}^m g_{ij} }[/math],

[math]\displaystyle{ \mu_j = \frac1{mw_j}\sum_{i=1}^m g_{ij}x_i }[/math],

[math]\displaystyle{ \Sigma_j = \frac1{mw_j}\sum_{i=1}^m g_{ij}(x_i - \mu_j)(x_i - \mu_j)^T,\; j = 1, \dots, k }[/math]

Вычислительное ядро алгоритма

Вычислительное ядро алгоритма представляет собой итерационное вычисление всех параметров модели, независимое по [math]\displaystyle{ m }[/math] объектам выборки [math]\displaystyle{ X }[/math]. На каждой итерации алгоритма на Е-шаге пересчитывается значение скрытых переменных, на M-шаге пересчет параметров модели с учетом скрытых переменных.

Макроструктура алгоритма

Как записано в описании ядра алгоритма, основную часть метода составляют вычисления элементов матрицы G на E шаге, и пересчет параметров [math]\displaystyle{ \Theta }[/math] на M-шаге.

Схема реализации последовательного алгоритма

Инициализация параметров
for iter = 1 : max_iterations
[E-шаг]
1. вычисление [math]\displaystyle{ \Sigma_j^{-1} }[/math] и [math]\displaystyle{ \frac1{(2\pi)^{d/2}\sqrt{|\Sigma_j|}}, j = 1 : k }[/math]
2. вычисление [math]\displaystyle{ g_{ij},\;i = 1 : m, \; j = 1 : k }[/math]
3. вычисление [math]\displaystyle{ LL_i }[/math] (логарифм правдоподобия), [math]\displaystyle{ \;i = 1 : m }[/math]
[M-шаг]
1. вычисление [math]\displaystyle{ \tilde w_j = \sum_{i=1}^m g_{ij}, \; j = 1 : m }[/math]
2. вычисление [math]\displaystyle{ \tilde \mu_j = \sum_{i=1}^m g_{ij}x_i,\; j = 1 : k }[/math]
3. вычисление [math]\displaystyle{ \tilde \Sigma_j = \sum_{i=1}^m g_{ij}(x_i - \mu_j)^T(x_i - \mu_j),\; j = 1 : k }[/math]
4. нормировка [math]\displaystyle{ w_j = \frac{\tilde w_j}{m} }[/math], [math]\displaystyle{ \mu_j = \frac{\tilde \mu_j}{w_j}, \tilde \Sigma_j = \frac{\tilde \Sigma_j}{w_j}, \;j = 1 : k }[/math]
вычисление изменения логарифма правдоподобия[math]\displaystyle{ \Delta LL = fabs(\sum_{i=1}^m LL^{iter}_i - \sum_{i=1}^m LL^{iter - 1}_i) }[/math]
if ([math]\displaystyle{ \Delta LL \lt \varepsilon }[/math]) then break;
end for

Последовательная сложность алгоритма

E-шаг:

вычисление обратной матрицы [math]\displaystyle{ \Sigma_j^{-1}, j = 1 : k }[/math] при фиксированном [math]\displaystyle{ j }[/math] для двумерного случая по явным формулам имеет сложность [math]\displaystyle{ O(d^2) }[/math], для всех кластеров — [math]\displaystyle{ O(d^2k) }[/math]
вычисление [math]\displaystyle{ g_{ij}, i = 1 : m, j = 1 : k }[/math] при фиксированных [math]\displaystyle{ i, j }[/math] имеет сложность [math]\displaystyle{ O(d) }[/math], сложность вычисления матрицы G — [math]\displaystyle{ O(dmk) }[/math]
вычисление [math]\displaystyle{ LL_i, i = 1 : m }[/math] при фиксированном [math]\displaystyle{ i }[/math] имеет сложность [math]\displaystyle{ O(k) }[/math], для всех объектов имеет сложность [math]\displaystyle{ O(mk) }[/math],

M-шаг:

вычисление [math]\displaystyle{ w_j, j = 1 : k }[/math] при фиксированном [math]\displaystyle{ j }[/math] имеет сложность [math]\displaystyle{ O(m) }[/math], для весов всех кластеров — [math]\displaystyle{ O(mk) }[/math]
вычисление [math]\displaystyle{ \mu_j, j = 1 : k }[/math] при фиксированном [math]\displaystyle{ j }[/math] имеет сложность [math]\displaystyle{ O(dm) }[/math], для всех кластеров — [math]\displaystyle{ O(dmk) }[/math]
вычисление [math]\displaystyle{ \Sigma_j, j = 1 : k }[/math] при фиксированном [math]\displaystyle{ j }[/math] имеет сложность [math]\displaystyle{ O(d^2m) }[/math], для всех кластеров — [math]\displaystyle{ O(d^2mk) }[/math]
нормировка [math]\displaystyle{ w }[/math], [math]\displaystyle{ \mu_j = \frac{\mu_j}{w_j}, \Sigma_j = \frac{\Sigma_j}{w_j}, j = 1 : k }[/math] имеет сложность [math]\displaystyle{ O(k) }[/math], [math]\displaystyle{ O(dk) }[/math], [math]\displaystyle{ O(d^2k) }[/math]
вычисление изменения логарифма правдоподобия[math]\displaystyle{ \Delta LL }[/math] имеет сложность [math]\displaystyle{ O(1) }[/math]

Сложность алгоритма на одной итерации:

[math]\displaystyle{ O(k(d^2+dm+m+m+dm+d^2m+1+d+d^2)) = O(d^2mk) }[/math], так как мы рассматриваем задачу для двумерного случая, то есть [math]\displaystyle{ d=2 }[/math], множитель [math]\displaystyle{ d^2 }[/math] можно отнести в константу, итоговая сложность вычисления на одной итерации [math]\displaystyle{ O(mk) }[/math].

Для [math]\displaystyle{ n }[/math] итераций итоговая сложность алгоритма будет равна:

[math]\displaystyle{ O(mkn) }[/math], где [math]\displaystyle{ m }[/math] — число объектов, [math]\displaystyle{ k }[/math] — число кластеров, [math]\displaystyle{ n }[/math] — число итераций.

Информационный граф

Опишем граф алгоритма для следующих входных данных: [math]\displaystyle{ m = 3 }[/math], то есть 3 входных объекта.

На рис.1 показана макроструктура EM-алгоритма. Входными данными в таком случае являются матрица [math]\displaystyle{ X \in \R^{3 \times d} }[/math], число кластеров [math]\displaystyle{ = K }[/math], число признаков [math]\displaystyle{ =d }[/math].

На шаге [math]\displaystyle{ \mathbf{init} }[/math] происходит инициализация начальных приближений параметров модели и затем итеративное повторение [math]\displaystyle{ \mathbf{E} }[/math] и [math]\displaystyle{ \mathbf{M} }[/math] шагов алгоритма.

Рис.1. Граф EM-алгоритма с отображением входных и выходных данных

E-шаг. На рис.2 детально изображена схема E-шага. Входные параметры [math]\displaystyle{ x_1,\; x_2,\; x_3 \in \R^{1 \times d} }[/math] являются строчками входной матрицы [math]\displaystyle{ X }[/math], также на вход подаются текущие приближения векторов средних значений ([math]\displaystyle{ \mu_1, \dots, \;\mu_K }[/math]), матриц ковариаций ([math]\displaystyle{ \Sigma_1, \dots, \Sigma_K }[/math]) и весов [math]\displaystyle{ w }[/math].

Вершинами [math]\displaystyle{ \mathbf{eI} }[/math] обозначена операция нахождения обратной матрицы [math]\displaystyle{ \Sigma_j^{-1},\; j = 1,\dots,K }[/math]. Вершины группы [math]\displaystyle{ \mathbf{eS} }[/math] обозначают вычитание векторов [math]\displaystyle{ x_i - \mu_j,\; i = 1,2,3; \; j = 1,\dots,K }[/math]. Салатовые узлы графа [math]\displaystyle{ \mathbf{eE} }[/math] обозначают вычисление ненормированного значения [math]\displaystyle{ g_{ij}, \;i = 1,2,3;\;j=1,\dots,K }[/math] по формулам из раздела описания алгоритма. Далее выход вершин этой группы подаётся на вход вершинам [math]\displaystyle{ \mathbf{eN} }[/math], которые обозначают нормировку, затем в [math]\displaystyle{ \mathbf{eL} }[/math] происходит подсчет логарифма правдоподобия. На выходе этого графа получаются скрытые переменные [math]\displaystyle{ g_{ij} }[/math] и логарифм правдоподобия LL.

M-шаг. На рисунке 3 изображена схема M-шага. Входными параметрами являются: исходные объекты [math]\displaystyle{ x_1,\; x_2,\; x_3 \in \R^{1 \times d} }[/math], скрытые переменные [math]\displaystyle{ g_{11},\;g_{21},\;g_{31},\;\mu_1 }[/math] для пересчета параметров первого кластера и [math]\displaystyle{ g_{1K},\;g_{2K},\;g_{3K},\;\mu_K }[/math] — для K-ого кластера.

Вершина [math]\displaystyle{ \mathbf{m}\boldsymbol{\mu} }[/math] обозначает подсчет слагаемого математического ожидания для одного объекта, затем на шаге [math]\displaystyle{ \mathbf{mS_1} }[/math] происходит суммирование слагаемых, и, наконец, на шаге [math]\displaystyle{ \mathbf{mN_1} }[/math] нормировка математического ожидания, выходом являются [math]\displaystyle{ \mu_1,\dots,\;\mu_K }[/math]. Вершина [math]\displaystyle{ \mathbf{m}\boldsymbol{\Sigma} }[/math] обозначает подсчет слагаемого матрицы ковариации для одного объекта, затем на шаге [math]\displaystyle{ \mathbf{mS_2} }[/math] происходит суммирование слагаемых, и, наконец, на шаге [math]\displaystyle{ \mathbf{mN_2} }[/math] нормировка матрицы ковариации, выходом являются [math]\displaystyle{ \Sigma_1,\;\dots,\;\Sigma_K }[/math]. Операция [math]\displaystyle{ \mathbf{mS_3} }[/math] обозначает вычисление ненормированного веса для одного шага, затем при выполнении [math]\displaystyle{ \mathbf{mN_3} }[/math] происходит нормировка весов, выходом являются [math]\displaystyle{ w_1,\dots,\;w_K }[/math].

На рис.1 показана структура ЕM-алгоритма для кластеризации, на рис.2 — структура E-шага и на рис.3 — структура M-шага.

Ресурс параллелизма алгоритма

Как видно из информационного графа, возможно распараллеливание как по кластерам, так и по объектам. Однако, в реальных задачах число кластеров много меньше числа объектов, поэтому распараллеливание по кластерам нецелесообразно.

В данной статье рассматривается вариант распараллеливания по объектам. Стоит отметить, что важно корректно организовать работу с параметрами модели (матрицами ковариаций, средними значениями и весами), чтобы не произошло ситуации гонки за ресурсами ^[2].

Входные и выходные данные алгоритма

Входные данные: плотная вещественная матрица объектов-признаков [math]\displaystyle{ X \in \R^{m \times d} }[/math] и количество кластеров [math]\displaystyle{ k }[/math], где [math]\displaystyle{ m }[/math] — количество объектов, [math]\displaystyle{ d }[/math] — количество кластеров.

Объём входных данных: [math]\displaystyle{ m \times d + 1 }[/math].

Выходные данные: вектор весов [math]\displaystyle{ w \in \R^{k \times 1} }[/math], [math]\displaystyle{ \;\;k }[/math] векторов математических ожиданий [math]\displaystyle{ \mu_j \in \R^{d \times 1} }[/math], [math]\displaystyle{ \;\;k }[/math] матриц ковариации [math]\displaystyle{ \Sigma \in \R^{d \times d} }[/math]

Объём выходных данных: [math]\displaystyle{ k \times (d \times d + d + 1) }[/math]

Свойства алгоритма

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

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

Алгоритм сбалансирован по E и M шагам, затраты на выполнение этих этапов примерно одинаковы.

ЧАСТЬ. Программная реализация алгоритма

Особенности реализации последовательного алгоритма

В данном разделе приведем код реализации последовательного алгоритма.

double_vector em_algo::expectation_step(double_matrix& features)
{
    long n_objects = features.size1();
    int n_clusters = parameters.sigmas.size();
    double pi = boost::math::constants::pi<double>();

    // precalculate inverse matrices and dets
    std::vector<double_matrix> sigmas_inverted(n_clusters);
    std::vector<double> norm_distribution_denominator(n_clusters);
    for (int i = 0; i < n_clusters; ++i)
    {        
        double_matrix sigma_inverted(parameters.sigmas[i].size1(), parameters.sigmas[i].size2());
        double det = InvertMatrix(parameters.sigmas[i], sigma_inverted);
        if (det == 0)
        {
            std::cerr << "Matrix can not be inverted\n";
            exit(1);
        }
        norm_distribution_denominator[i] = sqrt(pow(2 * pi, parameters.n_features) * det);
        sigmas_inverted[i] = sigma_inverted;
    }

    hidden_vars = double_matrix(n_objects, n_clusters);
    double_vector log_likelihood(n_objects, 0);

    for (auto i = 0; i < n_objects; ++i)
    {
        double_matrix_row x(features, i);
        double norm_value = 0;
        for (auto j = 0; j < n_clusters; ++j)
        {
            double_matrix_column current_means(parameters.means, j);
            double_vector x_centered = x - current_means;

            double exp_power = -0.5 * inner_prod(prod(x_centered, sigmas_inverted[j]), x_centered);
            hidden_vars(i, j) = parameters.weights(j) * exp(exp_power) / norm_distribution_denominator[j];

            norm_value += hidden_vars(i, j);
        }
        double_matrix_row hidden_vars_row(hidden_vars, i);
        if (norm_value != 0)
        {
            hidden_vars_row = hidden_vars_row / norm_value;
            log_likelihood(i) = log(inner_prod(hidden_vars_row, parameters.weights));
        }

    }
    return log_likelihood;
}

void em_algo::maximization_step(double_matrix& features)
{
    int n_objects = features.size1();

    double_vector w = double_vector(n_clusters, 0.0);
    double_matrix means = double_matrix(parameters.n_features, n_clusters, 0.0);
    std::vector<double_matrix> sigmas;
    for (int j = 0; j < n_clusters; ++j)
        sigmas.push_back(double_matrix(parameters.n_features, parameters.n_features, 0.0));

    for (int i = 0; i < n_objects; ++i)
    {
        double_matrix_row x_i = row(features, i);

        for (int j = 0; j < n_clusters; ++j)
        {
            double g = hidden_vars(i, j);
            w(j) += g;

            double_matrix_column single_mean = column(means, j);

            single_mean += g * x_i;

            double_vector x_centered = x_i - column(parameters.means, j);
            for (int k = 0; k < parameters.n_features; ++k)
                for (int l = 0; l < parameters.n_features; ++l)
                    sigmas[j](k, l) = sigmas[j](k, l) + g * x_centered(k) * x_centered(l);
        }
    }
    // update weights
    parameters.weights = w / n_objects;

    for (int j = 0; j < n_clusters; ++j) {
        double weight = w(j);
        // update means
        double_matrix_column means_old = column(parameters.means, j);
        double_matrix_column means_new = column(means, j);
        means_old = means_new / weight;

        // update sigmas
        parameters.sigmas[j] = sigmas[j] / weight;
        for (int k = 0; k < parameters.n_features; ++k)
            parameters.sigmas[j](k, k) = parameters.sigmas[j](k, k) + tol;
    }
}

bool em_algo::is_likelihood_stabilized(double_vector likelihood, double_vector previous_likelihood)
{
    double likelihood_diff = sum(likelihood) - sum(previous_likelihood);
    return fabs(likelihood_diff) < tol;
}

model em_algo::process(double_matrix& features, int max_iterations)
{
    int iteration = 0;
    double_vector likelihood, previous_likelihood;
    while (iteration++ < max_iterations && (iteration <= 2 || !is_likelihood_stabilized(likelihood, previous_likelihood)))
    {
        previous_likelihood = likelihood;
        likelihood = expectation_step(features);
        maximization_step(features);
    }
    return parameters;
}

Возможной реализацией является перестановка местами циклов по объектам и по кластерам на E и М шаге. В данном случае внешний цикл проходит по объектам, так как подразумевается дальнейшая реализации распараллеливания по объектам. При реализации только последовательного алгоритма более понятной версией будет реализация внешнего цикла по кластерам, и внутреннего по объектам, но такая реализация увеличит число обращений в память и общее время работы алгоритма.

Локальность данных и вычислений

Возможные способы и особенности параллельной реализации алгоритма

Масштабируемость алгоритма и его реализации

Для проведения экспериментов по масштабируемости были выбраны следующие параметры алгоритма: были зафиксированы число кластеров [math]\displaystyle{ k = 4 }[/math], и, также, было зафиксировано ядро рандомизации, чтобы избавиться от случайности различного выбора начального приближения параметров. Для показательности результатов условие досрочного завершения работы алгоритма в случае стабилизации логарифма правдоподобия игнорировалось, и для каждого запуска проводилось 50 итераций EM-алгоритма.

Для экспериментов было сгенерировано 20 выборок разного размера: от 40000 объектов до 200000 с шагом в 10000. Для каждой выборки время работы алгоритма усреднялось по нескольким запускам, чтобы избежать выбросов.

Для работы с многопоточностью использовалась библиотека OpenMP. С помощью нее были распараллелены основные циклы по объектам на E и M шаге.

Эксперименты проводились на компьютере с процессором Intel(R) Core(TM) i7-5820K @ 3.30GHz, который поддерживает до 12ти потоков.

При увеличении числа процессоров производительность растёт. Заметим также, что с увеличением числа точек, скорость работы программы линейно увеличивается.

Рис. 4 Время работы EM алгоритма в зависимости от числа процессов и размера задачи

В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:

минимальная эффективность реализации 0,00072%;
максимальная эффективность реализации 25.5037%.

Динамические характеристики и эффективность реализации алгоритма

Выводы для классов архитектур

Существующие реализации алгоритма

Существуют следующие последовательные реализации EM-алгоритма для кластеризации: opencv, scikit-learn.

Также существует несколько параллельных реализаций, описанных в следующих статьях:

В статье ^[3] авторы предлагают распределить вычисление скрытых переменных для каждого объекта между процессорами и на каждой итерации производить нормализацию. M-шаг предлагается параллелить по компонентам, что требует реализации корректного взаимодействия между процессорами. Предложенный вариант распараллеливания был реализован и протестирован авторами статьи с помощью MPI библиотеки MPICH.

Авторы статьи ^[4] используют MapReduce для распараллеливания EM-алгоритма для PLSI моделей.

Литература

↑ Воронцов К.В.; Математические методы обучения по прецедентам (теория обучения машин)
↑ Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.
↑ López-de-Teruel P. E., García J. M., Acacio; The Parallel EM Algorithm and its Applications in Computer Vision
↑ Abhinandan Das, Mayur Datar, Ashutosh Garg; Google News Personalization: Scalable Online Collaborative Filtering

[1] Воронцов К.В.; Математические методы обучения по прецедентам (теория обучения машин)

[2] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

[3] López-de-Teruel P. E., García J. M., Acacio; The Parallel EM Algorithm and its Applications in Computer Vision

[4] Abhinandan Das, Mayur Datar, Ashutosh Garg; Google News Personalization: Scalable Online Collaborative Filtering

[1]

[2]

[3]

[4]

Участник:Мария Готман/Алгоритм кластеризации, основанный на максимизации ожидания

Содержание

ЧАСТЬ. Свойства и структура алгоритмов

Общее описание алгоритма

Математическое описание алгоритма

Вычислительное ядро алгоритма

Макроструктура алгоритма

Схема реализации последовательного алгоритма

Последовательная сложность алгоритма

Информационный граф

Ресурс параллелизма алгоритма

Входные и выходные данные алгоритма

Свойства алгоритма

ЧАСТЬ. Программная реализация алгоритма

Особенности реализации последовательного алгоритма

Локальность данных и вычислений

Возможные способы и особенности параллельной реализации алгоритма

Масштабируемость алгоритма и его реализации

Динамические характеристики и эффективность реализации алгоритма

Выводы для классов архитектур

Существующие реализации алгоритма

Литература

Навигация

Участник:Мария Готман/Алгоритм кластеризации, основанный на максимизации ожидания

ЧАСТЬ. Свойства и структура алгоритмов

Общее описание алгоритма

Математическое описание алгоритма

Вычислительное ядро алгоритма

Макроструктура алгоритма

Схема реализации последовательного алгоритма

Последовательная сложность алгоритма

Информационный граф

Ресурс параллелизма алгоритма

Входные и выходные данные алгоритма

Свойства алгоритма

ЧАСТЬ. Программная реализация алгоритма

Особенности реализации последовательного алгоритма

Локальность данных и вычислений

Возможные способы и особенности параллельной реализации алгоритма

Масштабируемость алгоритма и его реализации

Динамические характеристики и эффективность реализации алгоритма

Выводы для классов архитектур

Существующие реализации алгоритма

Литература

Навигация

Поиск