我基于这篇论文实现了自己的期望最大化（EM）算法，并希望将其与另一个实现的性能进行比较。在测试中，我使用了k个中心点和1 Gb的文本数据，仅测量计算新中心点在一次迭代中所需的时间。我尝试使用R语言中的EM实现，但未能成功，因为结果在图表中显示，当文本数据量很大时会卡住。我是按照这里的示例进行操作的。
有谁知道如何测量EM算法的性能，或者如何在R中实现这一点？
回答：
公平地对EM算法进行基准测试是困难的。非常困难。
-
初始化通常会涉及到随机因素，并且可能大不相同。据我所知，R的实现默认使用层次聚类来寻找初始聚类。这需要O(n^2)的内存和最可能的O(n^3)的运行时间成本。在我的基准测试中，R会因为这个原因而耗尽内存。我假设有办法指定初始聚类中心/模型。当然，随机对象初始化会快得多。实践中，k-means++可能是选择初始中心的一个好方法。
-
理论上，EM算法永远不会终止。它只是在某个点上不再有太大变化，因此你可以设置一个阈值来停止。然而，停止阈值的具体定义各不相同。
-
存在各种模型变体。仅使用模糊分配的方法（如模糊c均值）当然会比使用多元高斯混合模型和协方差矩阵的实现快得多。特别是在高维度的情况下。协方差矩阵还需要O(k * d^2)的内存，而求逆将花费O(k * d^3)的时间，因此显然不适合文本数据。
-
数据可能适合也可能不适合。如果你在实际上具有高斯聚类的数据集上运行EM算法，通常会比在不适合的数据集上运行效果好得多。当没有好的拟合时，即使使用相同的实现，你也会看到运行时间的高方差。
作为起点，尝试多次运行你自己的算法，使用不同的初始化，并检查运行时间的方差。方差与总运行时间相比有多大？
你可以尝试与ELKI中的EM实现进行基准测试。但我怀疑该实现无法处理像文本这样的稀疏数据——这些数据不是高斯分布的，不适合进行基准测试。很可能它根本无法处理这些数据，这是预期的，并且可以从理论上解释。尝试寻找密集的数据集，并且预期这些数据集具有多个高斯聚类（对不起，我在这里无法给出很多推荐。经典的Iris和Old Faithful数据集对于基准测试来说太小了）。
