Jes*_*ica 1 cluster-analysis machine-learning data-mining time-complexity space-complexity
一般来说,更具体地说是伯努利混合模型(又名潜类分析).
EM与K-means的Lloyds变体几乎相同.因此每次迭代都需要进行O(n*k)距离计算.它们是更复杂的距离计算,但最终它们是马哈拉诺比斯距离的一些变体.
但是,k-means有一个非常好的终止行为.只有k ^ n个可能的群集分配.现在,如果在每一步中,你选择一个更好的,它将不得不在尝试所有k ^ n后终止最新的.但实际上,它通常在最多几十步后终止.
对于EM来说,这并不容易.对象不会分配给单个群集,但是在fuzzy-c-means中相对于所有群集分配.那就是你失去这个终止保证的时候.
因此,如果没有任何停止阈值,EM将无限优化集群分配,达到无限精度(假设您将以无限精度实现它).
因此,EM的理论运行时间是:无限的.
任何阈值(如果它只是硬件浮点精度)将使它更早完成.但是,这将是很难得到一个理论极限比这里不同的O(n*k*i)地方i是迭代的次数(可能是无限的,但你也可以设置为0,如果你不想做一个迭代).