一维数组的K-Means 聚类算法JAVA实现

【转】http://www.oschina.net/code/snippet_42411_2527

 

Java代码  

1. public class BasicKMeans {  
2.     /** 
3.      * @param args 
4.      */  
5.     public static void main(String[] args) {  
6.         // TODO Auto-generated method stub  
7.         double[] p = { 1, 2, 3, 5, 6, 7, 9, 10, 11, 100, 150, 200, 1000 };  
8.         int k = 5;  
9.         double[][] g;  
10.         g = cluster(p, k);  
11.         for (int i = 0; i < g.length; i++) {  
12.             for (int j = 0; j < g[i].length; j++) {  
13.                 System.out.print(g[i][j]);  
14.                 System.out.print("\t");  
15.             }  
16.             System.out.println();  
17.         }  
18.     }  
19.     /* 
20.      * 聚类函数主体。 
21.      * 针对一维 double 数组。指定聚类数目 k。 
22.      * 将数据聚成 k 类。 
23.      */  
24.     public static double[][] cluster(double[] p, int k) {  
25.         // 存放聚类旧的聚类中心  
26.         double[] c = new double[k];  
27.         // 存放新计算的聚类中心  
28.         double[] nc = new double[k];  
29.         // 存放放回结果  
30.         double[][] g;  
31.         // 初始化聚类中心  
32.         // 经典方法是随机选取 k 个  
33.         // 本例中采用前 k 个作为聚类中心  
34.         // 聚类中心的选取不影响最终结果  
35.         for (int i = 0; i < k; i++)  
36.             c[i] = p[i];  
37.         // 循环聚类，更新聚类中心  
38.         // 到聚类中心不变为止  
39.         while (true) {  
40.             // 根据聚类中心将元素分类  
41.             g = group(p, c);  
42.             // 计算分类后的聚类中心  
43.             for (int i = 0; i < g.length; i++) {  
44.                 nc[i] = center(g[i]);  
45.             }  
46.             // 如果聚类中心不同  
47.             if (!equal(nc, c)) {  
48.                 // 为下一次聚类准备  
49.                 c = nc;  
50.                 nc = new double[k];  
51.             } else // 聚类结束  
52.                 break;  
53.         }  
54.         // 返回聚类结果  
55.         return g;  
56.     }  
57.     /* 
58.      * 聚类中心函数 
59.      * 简单的一维聚类返回其算数平均值 
60.      * 可扩展 
61.      */  
62.     public static double center(double[] p) {  
63.         return sum(p) / p.length;  
64.     }  
65.     /* 
66.      * 给定 double 型数组 p 和聚类中心 c。 
67.      * 根据 c 将 p 中元素聚类。返回二维数组。 
68.      * 存放各组元素。 
69.      */  
70.     public static double[][] group(double[] p, double[] c) {  
71.         // 中间变量，用来分组标记  
72.         int[] gi = new int[p.length];  
73.         // 考察每一个元素 pi 同聚类中心 cj 的距离  
74.         // pi 与 cj 的距离最小则归为 j 类  
75.         for (int i = 0; i < p.length; i++) {  
76.             // 存放距离  
77.             double[] d = new double[c.length];  
78.             // 计算到每个聚类中心的距离  
79.             for (int j = 0; j < c.length; j++) {  
80.                 d[j] = distance(p[i], c[j]);  
81.             }  
82.             // 找出最小距离，返回最小值的下标  
83.             int ci = min(d);  
84.             // 标记属于哪一组  
85.             gi[i] = ci;  
86.         }  
87.         // 存放分组结果  
88.         double[][] g = new double[c.length][];  
89.         // 遍历每个聚类中心，分组  
90.         for (int i = 0; i < c.length; i++) {  
91.             // 中间变量，记录聚类后每一组的大小  
92.             int s = 0;  
93.             // 计算每一组的长度  
94.             for (int j = 0; j < gi.length; j++)  
95.                 if (gi[j] == i)  
96.                     s++;  
97.             // 存储每一组的成员  
98.             g[i] = new double[s];  
99.             s = 0;  
100.             // 根据分组标记将各元素归位  
101.             for (int j = 0; j < gi.length; j++)  
102.                 if (gi[j] == i) {  
103.                     g[i][s] = p[j];  
104.                     s++;  
105.                 }  
106.         }  
107.         // 返回分组结果  
108.         return g;  
109.     }  
110.   
111.     /* 
112.      * 计算两个点之间的距离， 这里采用最简单得一维欧氏距离， 可扩展。 
113.      */  
114.     public static double distance(double x, double y) {  
115.         return Math.abs(x - y);  
116.     }  
117.   
118.     /* 
119.      * 返回给定 double 数组各元素之和。 
120.      */  
121.     public static double sum(double[] p) {  
122.         double sum = 0.0;  
123.         for (int i = 0; i < p.length; i++)  
124.             sum += p[i];  
125.         return sum;  
126.     }  
127.   
128.     /* 
129.      * 给定 double 类型数组，返回最小值得下标。 
130.      */  
131.     public static int min(double[] p) {  
132.         int i = 0;  
133.         double m = p[0];  
134.         for (int j = 1; j < p.length; j++) {  
135.             if (p[j] < m) {  
136.                 i = j;  
137.                 m = p[j];  
138.             }  
139.         }  
140.         return i;  
141.     }  
142.   
143.     /* 
144.      * 判断两个 double 数组是否相等。 长度一样且对应位置值相同返回真。 
145.      */  
146.     public static boolean equal(double[] a, double[] b) {  
147.         if (a.length != b.length)  
148.             return false;  
149.         else {  
150.             for (int i = 0; i < a.length; i++) {  
151.                 if (a[i] != b[i])  
152.                     return false;  
153.             }  
154.         }  
155.         return true;  
156.     }  
157. }