Основа для сравнения временных характеристик максимизации ожиданий

Question

У меня есть собственная реализация алгоритма максимизации ожиданий (EM), основанная на следующей статье http://pdf.aminer.org/000/221/588/fuzzy_k_means_clustering_with_crisp_regions.pdf Я хотел бы сравнить производительность с другой реализацией. Для тестирования я использую число K центроидов с 1 Гб текстовых данных и просто измеряю время, необходимое для вычисления новых центроидов за 1 итерацию. Я попытался с реализацией EM в R, но не смог, так как результат изображен на графике и застрял с большим количеством текстовых данных. Я следовал за примерами: http://en.wikibooks.org/wiki/Data_Mining_Algorithms_In_R/Clustering/Expectation_Maximization_%28EM%29

Кто-нибудь знает о реализации EM для измерения производительности или как это сделать с R?

Answer 1

Справедливый сравнительный анализ EM сложно. Очень сложно.

1. инициализация обычно включает в себя случайный характер и может сильно отличаться. Насколько я знаю, реализация R по умолчанию использует иерархическую кластеризацию для поиска начальных кластеров. Который приходит в O(n^2) памяти и, скорее всего, в O(n^3) времени выполнения. В моих тестах R из-за этого не хватило бы памяти. Я предполагаю, что есть способ указать начальные кластерные центры / модели. Инициализация случайных объектов, конечно, будет намного быстрее. Вероятно, k-means++ - хороший способ выбрать начальные центры на практике.

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

3. Существуют все виды модельных вариаций. Метод, использующий только нечеткие назначения, такие как Fuzzy-c-means, будет, конечно, намного быстрее, чем реализация, использующая многомерные модели гауссовой смеси с ковариационной матрицей. В частности, с более высокой размерностью. Ковариационные матрицы также нуждаются в памяти O(k * d^2), а инверсия займет время O(k * d^3) и, следовательно, явно не подходит для текстовых данных.

4. Данные могут быть или не быть подходящими. Если вы запускаете EM для набора данных, который на самом деле имеет гауссовы кластеры, он обычно будет работать намного лучше, чем для набора данных, который вообще не обеспечивает хорошего соответствия. Когда нет подходящей подгонки, вы увидите высокую дисперсию во время выполнения даже при одной и той же реализации.

Для начала попробуйте запустить свой собственный алгоритм несколько раз с различной инициализацией и проверьте время выполнения на наличие отклонений. Насколько велика разница по сравнению с общим временем выполнения?

Вы можете попробовать сравнительный анализ реализации EM в ELKI. Но я сомневаюсь, что реализация будет работать с разреженными данными, такими как текст - эти данные просто не гауссовы, они не подходят для сравнения. Скорее всего, из-за этого он вообще не сможет обрабатывать данные. Это ожидается и может быть объяснено из теории. Попытайтесь найти наборы данных, которые плотны и могут иметь несколько гауссовых кластеров (извините, я не могу дать вам много рекомендаций здесь. Классические наборы данных Iris и Old Faithful слишком малы, чтобы их можно было использовать для сравнительного анализа.