kmeans与高斯混合模型课件.ppt

1、 K-means算法，也被称为K-均值，是一种得到最广泛使 用的聚类算法。它是将各个聚类内的所有数据样本的均值作为该聚类的代表点，算法的主要思想是通过迭代过程把数据划分为不同的类别，使得评价聚类性能的准则函数能达到最优，从而使生成的每个聚类内紧凑，类间独立。K-MEANS算法流程算法流程1.1.从样本选从样本选K K个对象作为初始聚类的中心个对象作为初始聚类的中心2.2.根据样本与聚类中心的相异度判断每个样根据样本与聚类中心的相异度判断每个样本属于哪个簇本属于哪个簇3.3.每个簇中重新计算聚类中心每个簇中重新计算聚类中心4.4.重复重复2 2、3 3步骤直到聚类不再变化步骤直到聚类不再变化 标

2、量：标量：闵可夫斯基距离：闵可夫斯基距离：曼哈顿距离曼哈顿距离:欧几里得距离欧几里得距离:对于每个样本，计算出它与每个样本中心的距离，距离最小的样本中心则视为相异度最低，则该样本属于该样本中心对应的簇，从而可以计算出每个样本都属于哪个簇。根据样本与聚类中心的根据样本与聚类中心的相异度相异度判断每个判断每个 样本属于样本属于哪个簇哪个簇 二元变量二元变量：取值不同的同位属性数取值不同的同位属性数/单个元素的属性位数单个元素的属性位数二元变量是只能取0和1两种值变量，例如X=1,0,0,0,1,0,1,1，Y=0,0,0,1,1,1,1,1，可以看到，两个元素第2、3、5、7和8个属性取值相同，而

3、第1、4和6个取值不同，那么相异度可以标识为3/8=0.375向量向量：（相似度）在每个簇中重新计算聚类中心：在每个簇中重新计算聚类中心：将同一个簇的样本的每个属性求平均值，从而计算出每个簇的聚类中心。此处可以生成新的K个聚类中心，用于下次计算样本属于的类别。例如：簇中有点(1,2,3)(4,5,6)。聚类中心就为（2.5,3.5,4.5）每个簇中重新计算聚类中心每个簇中重新计算聚类中心要点：要点：1、初始聚类中心的选取、初始聚类中心的选取这个过程大多数情况下采用随机选取的办法。因为k-means 并不能保证全局最优，是否能收敛到全局最优解其实和初值的选取有很大的关系，所以有时候我们会多次选取

4、初值跑 k-means，并取其中最好的一次结果K-means-test演示采用基于距离和的孤立点定义来进行孤立点的预先筛选不可预知孤立点就进行最远距离法首先整理移除孤立点后的数据集U,记录数据个数y,令m=1。比较数据集中所有数据对象两两之间的距离。找出距离最近的2个数据对象形成集合Am;比较Am中每一个数据对象与数据对象集合U中每一个对象的距离,在U中找出与Am 中最近的数据对象,优先吸收到Am 中,直到Am 中的数据对象个数到达一定数值,然后令m=m+1。再从U中找到对象两两间距离最近的2个数据对象构成Am,重复上面的过程,直到形成k个对象集合。这些集合内部的数据是相似的,而集合间是相异的

5、。可以看出,这种聚类方法同时满足以下2个条件:每个组至少包含一个数据对象;每个数据对象必须属于且仅属于一个组。即数据对象Xi Ai,且U=A1 A2 Ak A0,且Ai Aj=。最后对k个对象集合分别进行算术平均,形成k个初始聚类中心。KNN算法等等摘自wiki百科 迭代终止条件迭代终止条件 1、重复迭代直到聚类中心不再变化或者变化很小 准则函数：每一个样本点到其聚类中心点的平方和，K-MEANS要将J函数调整到最小。当J函数前后相差小于一个阈值的时候即可以终止迭代。若单一定义让聚类中心不再变化则停止迭代，可能会存在问题。因为某一点不一定百分之百属于某个聚类。演示K-MEANS-TEST22、

6、达到迭代最大步数Opencv的函数cvKMeans2中变量CvTermCriteria可设置两个迭代终止条件 高斯混合模型高斯混合模型GMM（Gaussian Mixture Model）可以看出K-MEANS是简单的，因为它基于假设即一个点仅以1或者0的概率属于某一聚类，这两者中间的取值没有考虑，将一个可以无穷取值的模型进化到了两个值，显然变得不那么复杂了，那么如果想要考虑到中间的值呢？即一个点仅以某一个概率属于某一类呢？既然考虑到概率，那么与K-MEANS的数学基础便是完全不同的，即并没有直接考虑欧氏距离的问题。此处就可以用高斯混合模型和E-M算法进行解决。高斯混合模型高斯混合模型GMM（

7、Gaussian Mixture Model）高斯分布（正态分布）：高斯分布（正态分布）：x是d维列向量，u是期望，是方差 高斯混合模型：高斯混合模型：高斯混合模型由K个单高斯生成，每个高斯模型为一个Component。首先随机地在这个 Component 之中选一个，每个 Component 被选中的概率为 选中了Component后，再考虑从这个Component中选取某一个点。GMM与聚类的关系与聚类的关系K是事先确定好的值，每个component就是一个聚类中心，即在只有样本点，不知道样本分类（含有隐含变量）的情况下，计算出模型参数（，u和）我们就需要确定、u 和 这些参数。找到这样一

8、组参数，它所确定的概率分布生成这些给定的数据点的概率最大它所确定的概率分布生成这些给定的数据点的概率最大假设我们有一个训练集x(1),x(m)，数据服从 Mixture Gaussian Distribution，即把数据看作是从许多个 Gaussian Distribution 中生成出来的。具体就是建立联合分布：z(i)满足多项分布 ,z(i)即为上式中的 ，即每个 Component 被选中的概率?j即p(z(i)=j)。，k为开始就确定好的k个Component1、首先选取一个Component，概率 2、在这个Component中的x(i)属于高斯分布 注意：此处的z(i)都是未知的

9、 现在，我们要确定，使生成x(i)这些数据点的概率最大，这里用到了最大似然估计法。似然函数：(可看做未知数，的集合，N即 文中的m)取对数此处则转化为模型：求，使的 l(，)的值最大。无法直接求导取0，然后求最大值。所以此处用到E-M算法。E步：步：估计数据由每个 Component 生成的概率（并不是每个 Component 被选中的概率）：对于每个x(i)数据来说，它由第j个 Component 生成的概率为(贝叶斯公式)：由于式子里的 和 也是需要我们估计的值，我们采用迭代法，在计算 的时候我们假定 和 均已知，我们将取上一次迭代所得的值（或者初始值）。问题：初始值怎么定的？M步：步：估计每个 Component 的参数：现在我们假设上一步中得到的就是正确的“数据x(i)由 Componentk生成的概率”。由于每个 Component 都是一个标准的 Gaussian 分布，可以很容易分布求出最大似然所对应的参数值：循环进行EM步，直到似然函数收敛。一种收敛方法是不再变化，还有一种就是变化幅度很小