数据挖掘算法之 K-means
一、什么是K-means
k-means algorithm is a direct clustering method that is widely used, capable of partitioning a set of objects into clusters with similar objects within each cluster and distinct differences between clusters.
二、K-Means 算法思想
该算法接受d维空间中的若干数据点作为输入，并将这些数据集划分为k个互不重叠的簇。该算法确保每个数据点精确地分配到且仅分配到一个特定的簇中。该算法默认使用欧几里得距离作为衡量数据点与聚类中心之间相似性的指标，并寻求最小值以优化数据分布：即使每个数据点与其所属聚类中心之间的欧氏距离平方之和达到最小值。
算法过程：
: 1：用集合D中的K个数据作为初始的聚簇代表，（可以随机选取）
2：对数据进行处理时，会将每个样本划分到与其最邻近的聚类中心，并且会消除上一次迭代所设定的归属关系。
3：重新计算均值，并对每个聚类重新选择其中心点；然后针对被分配到这些新中心点的数据集进行均值再计算以确定新的聚类核心位置。
4：重复步骤2、3，当C={cj|j=1,2,3...,k} 不再变化 或者目标函数收敛 的时候算法停止。
三、代码：
package dataMining;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
/** * @author 作者 : xcy
* @version 创建时间：2016年11月16日 下午7:11:53
* 类说明
*/
public class Kmeans {
private int k;
private double[][] data;
private double threshold;
private double[][] center;
private int[] cate;
public Kmeans(String path, int k, double threshold) throws IOException {
// data;
BufferedReader bfr = new BufferedReader(new FileReader(path));
List<String> tmp = new ArrayList<String>();
String s = "";
while ((s = bfr.readLine()) != null) {
tmp.add(s);
}
bfr.close();
this.data = new double[tmp.size()][2];
this.cate = new int[tmp.size()];
this.center = new double[k][2];
for (int i = 0; i < tmp.size(); i++) {
this.data[i][0] = Double.parseDouble(tmp.get(i).split("\ s+")[0]);
this.data[i][1] = Double.parseDouble(tmp.get(i).split("\ s+")[1]);
}
this.threshold = threshold;
this.k = k;
// k;
// threshold;
// center;
// cate
}
public void init() {
for (int i = 0; i < k; i++) {
int id = (data.length - 1) / k;
center[i][0] = data[i * id][0];
center[i][1] = data[i * id][1];
}
}
public double computeError(int[] a, int[] b) {
double re = 0.0;
for (int i = 0; i < a.length; i++) {
re += Math.abs(a[i] - b[i]);
}
return 1.0 * re / a.length;
}
public double computeDis(double[] a, double[] b) {
double re = (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]);
return Math.pow(re, 0.5);
}
public void run() {
init();
int[] cateTmp = new int[cate.length];
do {
for (int i = 0; i < cate.length; i++) {
cateTmp[i] = cate[i];
}
List<List<Integer>> id = new ArrayList<List<Integer>>();
for (int i = 0; i < k; i++) {
List<Integer> tmp = new ArrayList<Integer>();
id.add(tmp);
}
// classification
for (int i = 0; i < data.length; i++) {
double min = 10000;
int kTmp = 0;
for (int j = 0; j < k; j++) {
double dis = computeDis(center[j], data[i]);
kTmp = min > dis ? j : kTmp;
min = min > dis ? dis : min;
}
cate[i] = kTmp;
id.get(kTmp).add(i);
}
// compute center
for (int i = 0; i < k; i++) {
double x = 0.0;
double y = 0.0;
for (Integer it : id.get(i)) {
x += data[it][0];
y += data[it][1];
}
x /= id.get(i).size();
y /= id.get(i).size();
center[i][0] = x;
center[i][1] = y;
}
} while (computeError(cateTmp, cate) > threshold);
for (int i = 0; i < cate.length; i++) {
System.out.println("point : x= " + data[i][0] + " y= " + data[i][1] + " belongs to class : " + cate[i]);
// System.out.println(cate[i]);
}
}
}
代码解释测试：
package dataMining;
import java.io.IOException;
/** * @author 作者 : xcy
* @version 创建时间：2016年11月16日 下午9:26:44
* 类说明
*/
public class TestKm {
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
Kmeans km = new Kmeans("G:/eclipse/kmeansdata.txt", 5, 0.001);
km.run();
}
}
代码解释注： 文档是符合高斯分布的5个聚类：如下：
4.6602 0.9253
-3.9947 -7.5923
-4.4925 -3.3613
1.2045 -3.7078
2.2606 -2.9145
3.7825 -0.2030
3.1589 -3.2922
4.7679 -4.8348
5.6935 -3.2575
5.1470 -2.1590
0.6414 -5.1072
2.6100 -2.9368
4.4424 2.1681
2.6412 -1.3317
4.3479 -2.7407
5.2461 0.9865
2.1980 -2.6252
3.8800 0.6746
2.3690 -1.5874
4.5014 -2.0193
3.0303 -3.9696
2.4603 -3.1614
3.6636 1.3918
4.7581 0.0304
0.1153 -4.2849
1.0497 -3.4746
5.6175 -2.0646
2.5696 1.4066
3.9583 0.1060
2.5413 -0.4867
2.4251 -3.0049
3.4495 0.2427
4.0754 1.1745
3.1116 2.5405
4.9772 -2.3127
2.2828 -0.9141
4.4390 -0.2898
-2.4880 -6.4171
-2.4185 -6.2171
3.8600 -0.1667
2.9116 -1.0016
-0.7830 -7.1270
6.4273 2.3923
3.4034 -2.0693
4.1536 -2.0101
3.3553 0.4044
4.9335 1.3022
-1.6310 -5.4618
4.4513 -3.3567
-1.7313 -6.6377
6.0389 -2.0521
5.1400 -2.8396
3.6005 1.7586
3.9374 -0.6904
5.1500 -1.1583
-0.4157 -1.3474
-1.9768 -5.6723
2.4570 -2.8330
1.4664 -2.1910
-3.5808 -5.3188
2.9172 0.0009
6.3628 -2.6788
-0.0506 -2.8126
2.9034 1.5399
3.3807 0.4659
2.5631 -1.1925
-3.3058 -7.0301
3.7878 -2.1915
-2.1661 -6.3184
4.3194 -1.6982
5.3181 -0.9893
4.2741 -0.8572
-2.7674 -5.7855
-2.2835 -5.8701
2.4044 -2.1204
4.6775 -3.3235
4.8867 3.4046
1.9115 -1.6398
1.7925 -0.4656
5.4598 -0.7963
5.9935 -0.2185
5.0791 -1.7439
4.9994 -0.5472
0.2248 -5.8282
1.3278 -2.1331
2.3867 -2.5329
-3.6554 -5.8883
6.9589 -3.5587
2.9543 -0.6016
5.2627 1.3518
5.0759 1.7370
4.4705 -2.4140
3.7507 -0.0336
4.6846 0.9337
3.8627 1.1580
5.0376 1.2592
4.2444 1.1460
4.1011 0.0918
4.8366 2.2751
-0.3019 -2.0370
最终的分类结果用图片展示如下：
