关于 K-Means++ 算法，它是一种为 k-means 聚类算法选择初始值（或“种子”）的算法。
具体算法如下：
- 从数据点中均匀随机选择一个中心。
- 对于每个数据点 x，计算 D(x)，即 x 与已选择的最近中心之间的距离。
- 使用加权概率分布随机选择一个新数据点作为新中心，其中选择点 x 的概率与 D(x)2 成正比。
- 重复步骤 2 和 3，直到选择了 k 个中心。
- 现在已经选择了初始中心，继续使用标准的 k-means 聚类。
我不明白第 3 步
“使用加权概率分布随机选择一个新数据点作为新中心，其中选择点 x 的概率与 D(x)^2 成正比。”
什么是概率比例？
如果我没有误会。. .
我选择的下一个质心 x 必须是距离
D(x) = D(x)^2 / 到所有数据点的所有距离平方的总和
是对的吗 ？
我仍然想知道实施。我在java中尝试了这个，但它不起作用，机会非常低，它使选择失真。
public static double euclidean(Data a, Data b) {
double accumValue = 0;
double res;
for (int i = 0; i < 72; i++) {
res = a.features[i] - b.features[i];
res = Math.pow(res, 2);
accumValue += res;
}
double finalRes = Math.sqrt(accumValue);
return finalRes;
}
public static double accumeratedSqrDistanceCal(ArrayList<Data> dataList, ArrayList<Data> centroids) {
double[] squareDistanceCollection = new double[dataList.size()];
for (int i = 0; i < dataList.size(); i++) {
double minDistance = minDistanceFromClosetCentroidsCal(dataList.get(i), centroids);
squareDistanceCollection[i] = Math.pow(minDistance, 2);
}
double accumerateDistance = 0;
for (int i = 0; i < dataList.size(); i++) {
accumerateDistance += squareDistanceCollection[i];
}
return accumerateDistance;
}
public static double minDistanceFromClosetCentroidsCal(Data d, ArrayList<Data> centroids) {
double minDistance = 100000;
for (int i = 0; i < centroids.size(); i++) {
double distance = euclidean(d, centroids.get(i));
if (distance < minDistance) {
minDistance = distance;
}
}
return minDistance;
}
public static void main(String[] args) {
for (int i = 0; i < CENTROIDS_SIZE; i++) {
for (int j = 0; j < dataList.size(); j++) {
double accumerateDistance = accumeratedSqrDistanceCal(dataList, centroids);
double rand = Math.random();
double distance = minDistanceFromClosetCentroidsCal(dataList.get(j), centroids);
double distanceSquare = Math.pow(distance, 2);
double chance = distanceSquare / accumerateDistance;
if (chance > rand) {
centroids.add(dataList.get(j));
break;
}
}
}
}