K-means聚类算法.ppt

K-meansK-means聚类算法聚类算法报告人：张鸣磊报告人：张鸣磊 K-means算法是很典型的基于距离的聚算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就即认为两个对象的距离越近，其相似度就越大。越大。该算法认为类是由距离靠近的对象组成该算法认为类是由距离靠近的对象组成的，因此把得到紧凑且独立的类作为最终的，因此把得到紧凑且独立的类作为最终目标。目标。假设数据集合为假设数据集合为(x1,(x1,x2,x2,xn)xn)，并且每个并且每个xixi为为d d维的向量，维的向量，K-meansK-means聚类的聚类的目的是，在给定分类组数目的是，在给定分类组数k k（k kn n）值）值的条件下，将原始数据分成的条件下，将原始数据分成k k类：类：S S=S1,S1,S2,S2,SkSk 在数值模型上，即对以下表达式求最小值：在数值模型上，即对以下表达式求最小值：算法过程：算法过程：（1）随机选取）随机选取K个对象作为初始聚类中心；个对象作为初始聚类中心；（2）将数据样本集合中的样本按照最小距离）将数据样本集合中的样本按照最小距离原则分配到最邻近聚类；原则分配到最邻近聚类；（3）根据聚类的结果，重新计算）根据聚类的结果，重新计算K个聚类的个聚类的中心，并作为新的聚类中心；中心，并作为新的聚类中心；（4）重复步骤）重复步骤2.3直到聚类中心不再变化。直到聚类中心不再变化。数学表达式：数学表达式：n：样本数。：样本数。k：样本分为：样本分为k类。类。rnk：第：第n个样本点是否属于第个样本点是否属于第k类，属于则类，属于则rnk=1，不属于则不属于则rnk=0。K：第：第k个中心点。个中心点。k-means k-means 要做的就是最小化要做的就是最小化这个函数。这个函数。迭代的方法：迭代的方法：1 1、固定、固定K K，得到，得到r rnknk。2 2、固定、固定r rnknk，求出最，求出最优优的的K K。求求r rnknk 求求KK-meansK-means算法性能分析算法性能分析优点：优点：1 1、k-k-均值算法框架清晰，简单，均值算法框架清晰，简单，容易理解。容易理解。2 2、对于处理大数据集，这个算法、对于处理大数据集，这个算法是相对可伸缩和高效的，计算的复杂是相对可伸缩和高效的，计算的复杂度为度为O(NKt)O(NKt)，其中，其中N N是数据对象的数目，是数据对象的数目，t t是迭代的次数。一般来说，是迭代的次数。一般来说，KNKN，tN tN。3 3、当结果类是密集的，而类与类、当结果类是密集的，而类与类之间区别明显时，它的效果最好。之间区别明显时，它的效果最好。缺点：缺点：1 1、要求必须事先给出要生成的类的数、要求必须事先给出要生成的类的数目目k k，这个这个k k值的选定是非常难以估值的选定是非常难以估计。计。2 2、对初值敏感，对于不同的初始值，、对初值敏感，对于不同的初始值，可能会导致不同的聚类结果。可能会导致不同的聚类结果。3 3、对于、对于 噪声噪声 和孤立点数据敏感，少和孤立点数据敏感，少量的该类数据能够对平均值产生极大影响。量的该类数据能够对平均值产生极大影响。K-meansK-means算法变体算法变体（一）（一）k-medoidsk-medoids算法（算法（K-K-中心点算法）中心点算法）不采用聚类中对象的平均值作为参照点，不采用聚类中对象的平均值作为参照点，而是选用聚类中位置最中心的对象，即中而是选用聚类中位置最中心的对象，即中心点（心点（medoidmedoid）作为参照点。）作为参照点。K-K-中心点算法思想：中心点算法思想：首先随机选择首先随机选择k k个对象作为中心，把每个对象作为中心，把每 个对象分配给离它最近的中心。个对象分配给离它最近的中心。然后随机地选择一个非中心对象替换然后随机地选择一个非中心对象替换中心对象，计算分配后的距离改进量。聚中心对象，计算分配后的距离改进量。聚类的过程就是不断迭代，进行中心对象和类的过程就是不断迭代，进行中心对象和非中心对象的反复替换过程，直到目标函非中心对象的反复替换过程，直到目标函数不再有改进为止。数不再有改进为止。K-medoidsK-medoids算法流程如下：算法流程如下：1 1、任意选取、任意选取K K个对象作为初始中心点个对象作为初始中心点（O1,O2,O1,O2,OiOiOkOk）。）。2 2、将余下的对象分到各个类中去（根据与、将余下的对象分到各个类中去（根据与中心点最相近的原则）；中心点最相近的原则）；3 3、对于每个类（、对于每个类（OiOi）中，顺序选取一个）中，顺序选取一个OrOr，计算用，计算用OrOr代替代替OiOi后的消耗后的消耗E E（OrOr）。选）。选择择E E最小的那个最小的那个OrOr来代替来代替OiOi。这样。这样K K个中心个中心点就改变了。点就改变了。其中：其中：p p是空间中的样本点，是空间中的样本点，oj是类簇是类簇 cj 的的中心点中心点。4 4、重复、重复2 2、3 3步直到步直到K K个个medoidsmedoids固定下来固定下来。K-means算法与K-medoidsK-medoids算法结果对比：算法结果对比：K-meansK-means算法变体算法变体（二）（二）K-means+K-means+算法算法 使用使用K-meansK-means算法时，我们可以在输入算法时，我们可以在输入的数据集中随机的选择的数据集中随机的选择k k个点作为初始的聚个点作为初始的聚类中心，但是随机选择初始点可能会造成类中心，但是随机选择初始点可能会造成聚类的结果和数据的实际分布相差很大。聚类的结果和数据的实际分布相差很大。不同初始点，结果不同。不同初始点，结果不同。k-means+k-means+算法选择初始聚类中心的基算法选择初始聚类中心的基本思想是：初始的聚类中心之间的相互距本思想是：初始的聚类中心之间的相互距离要尽可能的远。离要尽可能的远。1 1、从输入的数据点集合中随机选择一个点作、从输入的数据点集合中随机选择一个点作为第一个聚类中心。为第一个聚类中心。2 2、对于数据集中的每一个点、对于数据集中的每一个点x x，计算它与最，计算它与最近聚类中心的距离近聚类中心的距离D(x)D(x)。3 3、选择一个新的数据点作为新的聚类中心，、选择一个新的数据点作为新的聚类中心，选择的原则是：选择的原则是：D(x)D(x)较大的点，被选取作较大的点，被选取作为聚类中心的概率较大。为聚类中心的概率较大。对于每个点，我们都计算其和最近的一对于每个点，我们都计算其和最近的一个聚类中心的距离个聚类中心的距离D(x)并保存在一个数组里，并保存在一个数组里，然后把这些距离加起来得到然后把这些距离加起来得到Sum(D(x)。再。再取一个随机值取一个随机值Random(0RandomSum)然然后用后用Random-=D(x)，直到其，直到其=0，此时的点，此时的点就是下一个聚类中心。就是下一个聚类中心。4、重复、重复2和和3直到直到k个聚类中心被选出来个聚类中心被选出来K-meansK-means算法与算法与k-means+k-means+算法选取初始点对比：算法选取初始点对比：K-means k-means+K-means k-means+K-meansK-means算法变体算法变体（三）（三）Fuzzy C-MeansFuzzy C-Means（模糊（模糊C C均值算法均值算法FCMFCM）是用隶属度确定每个数据点属于某个聚是用隶属度确定每个数据点属于某个聚类的程度的一种聚类算法。类的程度的一种聚类算法。隶属矩阵隶属矩阵U允许有取值在允许有取值在0-1间的元素。间的元素。不过，加上归一化规定，一个数据不过，加上归一化规定，一个数据点点的隶的隶属度的和总等于属度的和总等于1：把把n个元素个元素xi（i=1,2,n）分为）分为c个模糊组，个模糊组，目标函数：目标函数：其中，其中，m m是大于是大于1 1的实数，加权实数。的实数，加权实数。uij是是xixi属于类别属于类别j j隶属度，隶属度，cjcj是类是类j j的聚类中心。的聚类中心。算法步骤：算法步骤：1 1、用值在、用值在0 0，1 1间的随机数初始化隶属矩阵间的随机数初始化隶属矩阵U U，使其满足下面的约束条件：，使其满足下面的约束条件：2 2、计算、计算c c个聚类中心个聚类中心cici，i=1,i=1,c,c。3、更新隶属度、更新隶属度U矩阵。矩阵。4、算法停止条件：算法停止条件：其中其中0011。K-means算法和Fuzzy C-MeansFuzzy C-Means算法结果对比：算法结果对比：谢谢！