K-means聚类是一种非常流行的聚类算法，它的目标是将n个样本划分到k个簇中，使得每个样本属于与其最近的均值（即簇中心）对应的簇，从而使得簇内的方差最小化。K-means聚类算法简单、易于实现，并且在许多应用中都非常有效。
设 C={c1,c2,...,ck}C={c1,c2,...,ck} 为簇中心的集合，X={x1,x2,...,xn}X={x1,x2,...,xn} 为样本点集合。
K-means的目标是最小化簇内误差平方和（Within-Cluster Sum of Squares, WCSS）：
J(C)=∑i=1k∑x∈Si∣∣x−ci∣∣2J(C)=∑i=1k∑x∈Si∣∣x−ci∣∣2
其中，SiSi 是簇 cici 中的样本点集合。
优点：
缺点：
K-means++是一种改进的K-means算法，用于更智能地选择初始簇中心，从而提高聚类的质量。K-means++的基本思想是：
K-means聚类可以应用于多种场景，包括但不限于：
K-means聚类是一种非常实用的工具，但需要根据具体问题和数据集的特性来调整和优化。
下面是一个简单的Java实现K-means聚类算法的示例代码。这个示例将演示如何使用K-means算法对一组二维点进行聚类。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
public class KMeansClustering {
static class Point {
double x, y;
Point(double x, double y) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return String.format("(%f, %f)", x, y);
}
}
public static void kMeans(List<Point> points, int k, int maxIterations) {
Random rand = new Random();
List<Point> centroids = new ArrayList<>();
// 初始化质心
for (int i = 0; i < k; i++) {
centroids.add(points.get(rand.nextInt(points.size())));
}
for (int iter = 0; iter < maxIterations; iter++) {
// 1. 将每个点分配到最近的质心
List<List<Point>> clusters = new ArrayList<>();
for (int i = 0; i < k; i++) {
clusters.add(new ArrayList<>());
}
for (Point point : points) {
double minDistance = Double.MAX_VALUE;
int closestCentroid = 0;
for (int j = 0; j < k; j++) {
double dist = point.distance(centroids.get(j));
if (dist < minDistance) {
minDistance = dist;
closestCentroid = j;
}
}
clusters.get(closestCentroid).add(point);
}
// 2. 更新质心
boolean changed = false;
List<Point> newCentroids = new ArrayList<>();
for (List<Point> cluster : clusters) {
if (cluster.isEmpty()) {
newCentroids.add(centroids.get(0)); // 如果某个簇为空，随机选择一个质心
changed = true;
} else {
Point newCentroid = cluster.get(0);
for (Point point : cluster) {
newCentroid = new Point(
newCentroid.x / cluster.size() + point.x / cluster.size(),
newCentroid.y / cluster.size() + point.y / cluster.size()
);
}
newCentroids.add(newCentroid);
}
}
// 检查质心是否变化，如果没有则停止迭代
if (!changed && centroids.equals(newCentroids)) {
break;
}
centroids.clear();
centroids.addAll(newCentroids);
}
// 输出最终的质心和簇
for (int i = 0; i < centroids.size(); i++) {
System.out.println("Centroid " + i + ": " + centroids.get(i));
System.out.print("Cluster " + i + ": ");
for (Point point : clusters.get(i)) {
System.out.print(point + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
List<Point> points = new ArrayList<>();
points.add(new Point(1.0, 2.0));
points.add(new Point(1.5, 1.8));
points.add(new Point(5.0, 8.0));
points.add(new Point(8.0, 8.0));
points.add(new Point(1.0, 0.6));
points.add(new Point(9.0, 11.0));
points.add(new Point(8.0, 2.0));
points.add(new Point(10.0, 2.0));
points.add(new Point(9.0, 3.0));
int k = 3; // 簇的数量
int maxIterations = 100; // 最大迭代次数
kMeans(points, k, maxIterations);
}
}
Point类：一个简单的Point类，包含x和y坐标，并重写了toString方法以便于打印。
kMeans方法：
分配点到最近的质心：对于每个点，计算其到每个质心的距离，并将点分配到最近的质心所代表的簇。
更新质心：计算每个簇所有点的均值，作为新的质心。
接受一组点、簇的数量k和最大迭代次数maxIterations作为参数。
随机选择初始质心。
进行迭代，每次迭代包括两个主要步骤：
分配点到最近的质心：对于每个点，计算其到每个质心的距离，并将点分配到最近的质心所代表的簇。
更新质心：计算每个簇所有点的均值，作为新的质心。
如果质心没有变化，或者达到最大迭代次数，则停止迭代。
main方法：创建了一个点的列表，并指定了簇的数量和最大迭代次数，然后调用kMeans方法进行聚类。
这个示例代码演示了K-means聚类的基本实现，但它没有使用K-means++算法来选择初始质心，也没有处理空簇的情况。在实际应用中，可能需要根据具体问题进行相应的优化和改进。
Lru-k与lru的区别在于多维护一个队列，及每个元素多维护一个次数选项，对于性能的影响不大，仅仅多耗一点cpu，但是可以相应的提高命中率，下一章将介绍LFU按频次的淘汰机制。