聚类算法讲解
《聚类算法讲解》由会员分享，可在线阅读，更多相关《聚类算法讲解（32页珍藏版）》请在文档大全上搜索。
1、Kmeans实战实战聚类算法简介聚类算法简介Kmeans算法详解算法详解Kmeans算法的缺陷及若干改进算法的缺陷及若干改进 Kmeans的单机实现与分布式实现策略的单机实现与分布式实现策略 123聚类的目标：聚类的目标：将一组向量分成若干组，组内数据是相似的，将一组向量分成若干组，组内数据是相似的，而组间数据是有较明显差异而组间数据是有较明显差异。与分类区别：与分类区别：分类与聚类最大的区别在于分类的目标事先已分类与聚类最大的区别在于分类的目标事先已知，聚类也被称为无监督机器学习知，聚类也被称为无监督机器学习聚类手段：传统聚类算法聚类手段：传统聚类算法 划分法划分法 层次方法层次方法 基于密
2、度基于密度方法方法 基于网络方法基于网络方法 基于模型方法基于模型方法Q1：K是什么？是什么？A1：k是聚类算法当中类的个数。是聚类算法当中类的个数。Summary：Kmeans是用均值算法把数是用均值算法把数据分成据分成K个类的算法！个类的算法！ Q2：means是什么？是什么？A2：means是均值算法。是均值算法。步骤一：取得步骤一：取得k个初始初始中心点个初始初始中心点Min of threedue to the EuclidDistance步骤二：把每个点划分进相应的簇步骤二：把每个点划分进相应的簇Min of threedue to the EuclidDistance步骤三：重新
3、计算中心点步骤三：重新计算中心点步骤四：迭代计算中心点步骤四：迭代计算中心点步骤五：收敛步骤五：收敛1.从数据中随机抽取从数据中随机抽取k个点作为初始聚类个点作为初始聚类的中心，由这个中心代表各个聚类的中心，由这个中心代表各个聚类2.计算数据中所有的点到这计算数据中所有的点到这k个点的距离，个点的距离，将点归到离其最近的聚类里将点归到离其最近的聚类里3.调整聚类中心，即将聚类的中心移动到调整聚类中心，即将聚类的中心移动到聚类的几何中心（即平均值）处，也就是聚类的几何中心（即平均值）处，也就是k-means中的中的mean的含义的含义4.重复第重复第2步直到聚类的中心不再移动，步直到聚类的中心不
4、再移动，此时算法收敛此时算法收敛最后最后kmeans算法时间、空间复杂度是：算法时间、空间复杂度是：时间复杂度：上限为时间复杂度：上限为O(tKmn)，下限为，下限为（Kmn）其中，）其中，t为迭代次数，为迭代次数，K为簇的数为簇的数目，目，m为记录数，为记录数，n为维数为维数 空间复杂度：空间复杂度：O(m+K)n)，其中，其中，K为簇为簇的数目，的数目，m为记录数，为记录数，n为维数为维数Input & centroidsSelected kMaxIterations & ConvergenceMeassures数据的采集和抽象初始的中心选择最大迭代次数收敛值 k值的选定
5、度量距离的手段factors？初始中初始中心点心点输入的数输入的数据及据及K值值的选择的选择距离度距离度量量我们主要研究的三个方面因素。我们主要研究的三个方面因素。讨论初始中心点意义何在？下面的例子一目了然吧？讨论初始中心点意义何在？下面的例子一目了然吧？初始中心点初始中心点收敛后收敛后你你懂懂的的 在进一步阐述初始中心点选择在进一步阐述初始中心点选择之前，我们应该先确定度量之前，我们应该先确定度量kmeans的算法精确度的方法。的算法精确度的方法。一种度量聚类效果的标准是：一种度量聚类效果的标准是：SSE(Sum of Square Error，误差平方和误差平方和)SSE越小表示数据点越接
6、近于越小表示数据点越接近于它们的质心，聚类效果也就越它们的质心，聚类效果也就越好。因为对误差取了平方所以好。因为对误差取了平方所以更重视那些远离中心的点。更重视那些远离中心的点。一种可以肯定降低一种可以肯定降低SSE的方法的方法是增加簇的个数。但这违背了是增加簇的个数。但这违背了聚类的目标。因为聚类是在保聚类的目标。因为聚类是在保持目标簇不变的情况下提高聚持目标簇不变的情况下提高聚类的质量。类的质量。现在思路明了了我们首先以缩现在思路明了了我们首先以缩小小SSE为目标改进算法。为目标改进算法。为了克服为了克服k均值算法收敛于局部的问题，提出了二分均值算法收敛于局部的问题，提出了二分k均值算法。
7、该算法首先将所有的点作为一个簇，然后均值算法。该算法首先将所有的点作为一个簇，然后将该簇一分为二。之后选择其中一个簇继续划分，选将该簇一分为二。之后选择其中一个簇继续划分，选择哪个簇进行划分取决于对其划分是否可以最大程度择哪个簇进行划分取决于对其划分是否可以最大程度降低降低SSE值。值。伪代码如下：伪代码如下：将所有的点看成一个簇将所有的点看成一个簇当簇数目小于当簇数目小于k时时对于每一个簇对于每一个簇计算总误差计算总误差在给定的簇上面进行在给定的簇上面进行K均值聚类均值聚类(K=2)计算将该簇一分为二后的总误差计算将该簇一分为二后的总误差选择使得误差最小的那个簇进行划分操作选择使得误差最小的
8、那个簇进行划分操作既然是改进算法就要体现改既然是改进算法就要体现改进算法的优越性。为此控制进算法的优越性。为此控制变量，在相同的实验环境下，变量，在相同的实验环境下，取相同的取相同的k值取。值取。选取相同的的距离度量标选取相同的的距离度量标准（欧氏距离）准（欧氏距离）在相同的数据集下进行测在相同的数据集下进行测试。试。一组不好的初始点产生的一组不好的初始点产生的Kmeans算法结果算法结果二分二分kmeans产生的结果产生的结果要强调的是尽管只是这一组实验不得以得出二分要强调的是尽管只是这一组实验不得以得出二分kmeans的的优越性，优越性，但是但是经过大量实验得出的结论却是在大多数情况下经过
