作者：幼儿之家燕郊_880 | 来源：互联网 | 2022-12-16 16:26
K-Means算法是聚类算法，k在在这里指的是分类的类型数（根据经验指出会出现几个类别），所以在开始设定的时候非常关键，算法的原理是首先假定k个分类点，然后根据欧式距离计算分类，然后去同分类的均
K-Means算法是聚类算法，k在在这里指的是分类的类型数（根据经验指出会出现几个类别），所以在开始设定的时候非常关键，算法的原理是首先假定k个分类点，然后根据欧式距离计算分类，然后去同分类的均值作为新的聚簇中心，循环操作直到收敛。算法的关键在K个值的选取上，如果均值选得恰当将有利于算法的快速收敛。
Kmeans算法的执行过程的伪代码可概括为如下：
Kmeans算法时间复杂度：O(tkmn)，其中t为迭代次数，K为簇数目；
Kmeans算法空间复杂度：O((m+k)n)，m为记录数，n为维数；
K-means算法是最为经典的基于划分的聚类方法，是十大经典数据挖掘算法之一。K-means算法的基本思想是：以空间中k个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。
距离的度量
常用的距离度量方法包括：欧几里得距离和余弦相似度。两者都是评定个体间差异的大小的。欧几里得距离度量会受指标不同单位刻度的影响，所以一般需要先进行标准化，同时距离越大，个体间差异越大；空间向量余弦夹角的相似度度量不会受指标刻度的影响，余弦值落于区间[-1,1]，值越大，差异越小。但是针对具体应用，什么情况下使用欧氏距离，什么情况下使用余弦相似度？
从几何意义上来说，n维向量空间的一条线段作为底边和原点组成的三角形，其顶角大小是不确定的。也就是说对于两条空间向量，即使两点距离一定，他们的夹角余弦值也可以随意变化。感性的认识，当两用户评分趋势一致时，但是评分值差距很大，余弦相似度倾向给出更优解。举个极端的例子，两用户只对两件商品评分，向量分别为(3,3)和(5,5)，这两位用户的认知其实是一样的，但是欧式距离给出的解显然没有余弦值合理。
算法的停止条件
一般是目标函数达到最优或者达到最大的迭代次数即可终止。对于不同的距离度量，目标函数往往不同。当采用欧式距离时，目标函数一般为最小化对象到其簇质心的距离的平方和，如下：
当采用余弦相似度时，目标函数一般为最大化对象到其簇质心的余弦相似度和，如下：
Kmeans算法特点
该算法的最大优势在于简洁和快速。算法的关键在于初始中心的选择和距离公式。
Kmenas算法试图找到使平均误差准则函数最小的簇。当潜在的簇形状是凸面的，簇与簇之间区别较明显，且簇大小相近时，其聚类结果较理想。前面提到，该算法时间复杂度为O(tKmn)，与样本数量线性相关，所以，对于处理大数据集合，该算法非常高效，且伸缩性较好。但该算法除了要事先确定簇数K和对初始聚类中心敏感外，经常以局部最优结束，同时对“噪声”和孤立点敏感，并且该方法不适于发现非凸面形状的簇或大小差别很大的簇。
算法理解
或许对上述描述，有人还是对kmeans算法不太理解，下面通过形象化的图形来加深理解。假设研究的数据点不是很多，小到还是可以用二维坐标来表示（如下图，大概有两个类）。
取K=2，现随机取两个点（点1，点2），计算所有的点到点1、2的距离，形成c图（红色属于点1的类，蓝色属于点2的类），计算各类的平均值（中心点）（如d图）；以d图中的两个x点为k均值点，进行第二次迭代，再进行上述同样的距离计算过程，直至图f结束。算法结束的条件是簇质心的距离的平方和最小（一般迭代次数大于k值）。
算法改进意见
由kmeans算法特点知道，算法对噪声和孤立点很敏感，需要作平滑去噪处理，把不必要的点去除；在作数据挖掘时难以确定k值，因此canopy算法比该算法更有用武之地。可以先使用canopy找出最佳k值，然后kmeans聚类。Kmeans算法可用于聚类划分，如净化网络论坛，用户的行为划分寻找水军的共同特征；电子商务客商的消费行为，进而结合推荐系统投递广告。
算法实现(核心代码)
详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43373159
| public void kMeansClustering() { double tempX = 0; double tempY = 0; int count = 0; double error = Integer.MAX_VALUE; Point temp; while (error > 0.01 * classNum) { for (Point p_total : totalPoints) { // 将所有的测试坐标点就近分类,打标签分类的过程,p2遍历两个类点 for (Point p_class : classPoints) { p_class.computerDistance(p_total); } Collections.sort(classPoints); // 小到大排序 // 取出p_total离类坐标点最近的那个点 p_total.setClassName(classPoints.get(0).getClassName()); } error = 0; // 按照均值重新计算聚类中心点 for (Point p1 : classPoints) { count = 0; tempX = 0; tempY = 0; for (Point p : totalPoints) { if (p.getClassName().equals(p1.getClassName())) { count++; tempX += p.getX(); tempY += p.getY(); } } tempX /= count; tempY /= count; // 类质心 error += Math.abs((tempX - p1.getX())); error += Math.abs((tempY - p1.getY())); // 计算均值 p1.setX(tempX); p1.setY(tempY); } for (int i = 0; i temp = classPoints.get(i); System.out.println(MessageFormat.format("聚类中心点{0}，x={1},y={2}", (i + 1), temp.getX(), temp.getY())); } System.out.println("----------"); } System.out.println("结果值收敛"); // classPoints.size()=类数目 for (int i = 0; i temp = classPoints.get(i); System.out.println(MessageFormat.format("聚类中心点{0}，x={1},y={2}", (i + 1), temp.getX(), temp.getY())); } } |
![[大整数乘法] java代码实现](https://img1.php1.cn/3cd4a/24c6f/9f3/0133bb25da242824.jpeg)
京公网安备 11010802041100号