K均值算法K值选择、EM算法原理

K均值算法K值选择、EM算法原理 数据挖掘作业三: 吕培聪 学号,23220101153245 一、 K均值算法K值的选择问题 遗传算法(GA)可以优化K值的选择。遗传算法是一种利用达尔文适者生存的自然进化原理实现的全局性随机优化过程，该算法将搜索空间中的每个点用一个染色体(CHROMOSOME)示，每个染色体包含了一组与题解有关的特征参数(或基因，GENES)，不同染色体对于环境的适应性用适应度函数(FITNESS FUNCTION)表示，开始时由随机找到的若干个染色体组成群落(POPULATION)，在每一代，通过搜索，即对每个染色体用适应度函数进行评价，找到群落中适应度较高的染色体基因串。经过一代又一代染色体的交叉(CROSSOVER)、变异(MUTATION)，可以搜索到多个局部极值，从而增加了找到全局优解的可能性。本方法中，每条染色体对应一个K值，以K-MEAN聚类效果作为评价染色体适应度的主要标准，以寻找到全局优值。使得各类之间距离和达到最大，而类内间的距离达到最小。具体方法:先形成初始染色体组POPULATION，计算染色体的适应函数FITNESS FUNCTION，再进化部分适应性好的染色体到MATING POOL，交叉、变异，最后选择适应性强的染色体形成新一代染色体组POPULATION。循环一定代数，找到最优的K值(见下图)。 二、 EM期望最大化算法的原理 EM算法就是这样，假设我们估计知道A和B两个参数，在开始状态下二者都是未知的，并且知道了A的信息就可以得到B的信息，反过来知道了B也就得到了A。可以考虑首先赋予A某种初值，以此得到B的估计值，然后从B的当前值出发，重新估计A的取值，这个过程一直持续到收敛为止。 EM 算法是 Dempster，Laind，Rubin 于 1977 年提出的求参数极大似然估计的一种方法，它可以从非完整数据集中对参数进行 MLE 估计，是一种非常简单实用的学习算法。这种方法可以广泛地应用于处理缺损数据，截尾数据，带有讨厌数据等所谓的不完全数据(incomplete data)。 假定集合Z = (X,Y)由观测数据 X 和未观测数据Y 组成，Z = (X,Y)和 X 分别称为完整数据和不完整数据。假设Z的联合概率密度被参数化地定义为P(X，Y|Θ)，其中Θ 表示要被估计的参数。Θ 的最大似然估计是求不完整数据的对数似然函数L(X;Θ)的最大值而得到的: L(Θ; X )= log p(X |Θ) = ?log p(X ,Y |Θ)dY ; EM算法包括两个步骤:由E步和M步组成，它是通过迭代地最大化完整数据的对数似然函数Lc( X;Θ )的期望来最大化不完整数据的对数似然函数，其中: Lc(X;Θ) =log p(X，Y |Θ) ; 假设在算法第t次迭代后Θ 获得的估计记为Θ(t ) ，则在(t+1)次迭代时， E-步:计算完整数据的对数似然函数的期望，记为: Q(Θ |Θ (t) ) = E{Lc(Θ;Z)|X;Θ(t) }; M-步:通过最大化Q(Θ |Θ(t) ) 来获得新的Θ 。 通过交替使用这两个步骤，EM算法逐步改进模型的参数，使参数和训练样本的似然概率逐渐增大，最后终止于一个极大点。直观地理解EM算法，它也可被看作为一个逐次逼近算法:事先并不知道模型的参数，可以随机的选择一套参数或者事先粗略地给定某个初始参数λ0 ，确定出对应于这组参数的最可能的状态，计算每个训练样本的可能结果的概率，在当前的状态下再由样本对参数修正，重新估计参数λ ，并在新的参数下重新确定模型的状态，这样，通过多次的迭代，循环直至某个收敛条件满足为止，就可以使得模型的参数逐渐逼近真实参数。