Weka[]EM源代码分析.doc

Weka[28] EM 源代码分析 作者：Koala++/屈伟 EM 算法在 clusterers 下面，提一下是因为我没有想到它竟然在这里，而且它的名字也 太大了点，因为这里它只是与 SimpleKMeans 结合的算法。 引自 Andrew Ng 的 Lecture notes mixtures of Gaussians and the EM algorithm：The EM-algorithm is also reminiscent of the K-means clustering algorithm, except that instead of “hard” cluster assignment c(i), we instead have the “soft” assignment w_j^(i). Similar to K-means, it is also susceptible to local optima, so reinitializing at several different initial parameters may be a good idea。 Soft 指的是我们猜测是概率，取值在[0,1]区间，相反，“hard”猜测是指单个最好的猜测， 可以取值在 {0,1}或是 {1,…,k}。英文原文： The term “soft” refers to our guesses being probabilities and taking values in [0,1]; in contrast, a “hard” guess is one that represents a single best guess( such as taking values in {0,1} or {1,…,k}) 下面的图来自 Ng Andrew 和 Bishop Chistopher，第一组图 K-Means 的猜测是两个点， 而第二组图 EM 是对概率的猜测。 另一点是刚才文中提到的，多个初始化点，在代码中也体现了。 Ng 在对 EM 算法收敛证明之后，解释如下：Hence, EM causes the likelihood to converge monotonically. In our description of the EM algorithm, we said wed run it until convergence. Given the result that we just showed, one reasonable convergence test would be to check if the increase in l(theta) between successive iterations is smaller than some tolerance parameter, and to declare convergence if EM is improving l(theta) too slowly. 从 buildCluster 开始： if (data.checkForStringAttributes()) { throw new Exception(Cant handle string attributes!); } m_replaceMissing = new ReplaceMissingValues(); Instances instances = new Instances(data); instances.setClassIndex(-1); m_replaceMissing.setInputFormat(instances); data = weka.filters.Filter.useFilter(instances, m_replaceMissing); instances = null; m_theInstances = data; // calculate min and max values for attributes m_minValues = new double[m_theInstances.numAttributes()]; m_maxValues = new double[m_theInstances.numAttributes()]; for (int i = 0; i m_theInstances.numAttributes(); i++) { m_minValues[i] = m_maxValues[i] = Double.NaN; } for (int i = 0; i m_theInstances.numInstances(