K-means聚類是一種非常流行的聚類算法
K-means聚類是一種非常流行的聚類算法，它的目標是將n個樣本劃分到k個簇中，使得每個樣本屬于與其最近的均值（即簇中心）對應的簇，從而使得簇內的方差最小化。K-means聚類算法簡單、易于實現，并且在許多應用中都非常有效。
K-means算法的基本步驟：
- 選擇初始中心：隨機選擇k個樣本點作為初始的簇中心，或者使用K-means++算法來更智能地選擇初始簇中心。
- 分配樣本：將每個樣本點分配到最近的簇中心，形成k個簇。
- 更新簇中心：重新計算每個簇的中心，通常是簇內所有點的均值。
- 迭代優化：重復步驟2和3，直到簇中心不再發生顯著變化，或者達到預設的迭代次數。
- 終止條件：當簇中心在連續迭代中的變化小于某個閾值，或者達到預設的最大迭代次數時，算法終止。
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值，而k值的選擇可能依賴于領域知識或試錯。
- 對初始簇中心的選擇敏感，可能導致局部最優解。
- 對噪聲和異常點敏感，可能影響簇中心的計算。
- 只能發現數值型特征的簇，不適合文本數據等非數值型數據。
K-means++算法：
K-means++是一種改進的K-means算法，用于更智能地選擇初始簇中心，從而提高聚類的質量。K-means++的基本思想是：
- 隨機選擇一個點作為第一個簇中心。
- 對于每個剩余的點，計算其到最近簇中心的距離，并根據距離的平方選擇下一個簇中心。
- 重復步驟2，直到選擇k個簇中心。
實際應用：
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++算法來選擇初始質心，也沒有處理空簇的情況。在實際應用中，可能需要根據具體問題進行相應的優化和改進。
浙公網安備 33010602011771號