public class BasicKMeans {
/**
* @param args
*/
public static void main(String[] args) {
long time = System.currentTimeMillis();
double[] p = new double[] { 1, 2, 3, 5, 6, 7, 9, 10, 11, 100, 150, 200, 1000 };
int k = 5;
double[][] g;
g = cluster(p, k);
for (int i = 0; i < g.length; i++) {
for (int j = 0; j < g[i].length; j++) {
System.out.print(g[i][j]);
System.out.print("\t");
}
System.out.println();
}
System.out.println(System.currentTimeMillis() - time);
}
/*
* 聚類函數主體。 針對一維 double 數組。指定聚類數目 k。 將數據聚成 k 類。
*/
public static double[][] cluster(double[] p, int k) {
// 存放聚類舊的聚類中心
double[] c = new double[k];
// 存放新計算的聚類中心
double[] nc = new double[k];
// 存放放回結果
double[][] g;
// 初始化聚類中心
// 經典方法是隨機選取 k 個
// 本例中采用前 k 個作為聚類中心
// 聚類中心的選取不影響最終結果
for (int i = 0; i < k; i++) {
c[i] = p[i];
}
// 循環聚類，更新聚類中心
// 到聚類中心不變為止
while (true) {
// 根據聚類中心將元素分類
g = group(p, c);
// 計算分類后的聚類中心
for (int i = 0; i < g.length; i++) {
nc[i] = center(g[i]);
}
// 如果聚類中心不同
if (!equal(nc, c)) {
// 為下一次聚類準備
c = nc;
nc = new double[k];
} else {
break;
}
}
// 返回聚類結果
return g;
}
/*
* 聚類中心函數 簡單的一維聚類返回其算數平均值 可擴展
*/
public static double center(double[] p) {
return sum(p) / p.length;
}
/*
* 給定 double 型數組 p 和聚類中心 c。 根據 c 將 p 中元素聚類。返回二維數組。 存放各組元素。
*/
public static double[][] group(double[] p, double[] c) {
// 中間變量，用來分組標記
int[] gi = new int[p.length];
// 考察每一個元素 pi 同聚類中心 cj 的距離
// pi 與 cj 的距離最小則歸為 j 類
for (int i = 0; i < p.length; i++) {
// 存放距離
double[] d = new double[c.length];
// 計算到每個聚類中心的距離
for (int j = 0; j < c.length; j++) {
d[j] = distance(p[i], c[j]);
}
// 找出最小距離
int ci = min(d);
// 標記屬于哪一組
gi[i] = ci;
}
// 存放分組結果
double[][] g = new double[c.length][];
// 遍歷每個聚類中心，分組
for (int i = 0; i < c.length; i++) {
// 中間變量，記錄聚類后每一組的大小
int s = 0;
// 計算每一組的長度
for (int j = 0; j < gi.length; j++) {
if (gi[j] == i) {
s++;
}
}
// 存儲每一組的成員
g[i] = new double[s];
s = 0;
// 根據分組標記將各元素歸位
for (int j = 0; j < gi.length; j++) {
if (gi[j] == i) {
g[i][s] = p[j];
s++;
}
}
}
// 返回分組結果
return g;
}
/*
* 計算兩個點之間的距離， 這里采用最簡單得一維歐氏距離， 可擴展。
*/
public static double distance(double x, double y) {
return Math.abs(x - y);
}
/*
* 返回給定 double 數組各元素之和。
*/
public static double sum(double[] p) {
double sum = 0.0;
for (int i = 0; i < p.length; i++) {
sum += p[i];
}
return sum;
}
/*
* 給定 double 類型數組，返回最小值得下標。
*/
public static int min(double[] p) {
int i = 0;
double m = p[0];
for (int j = 1; j < p.length; j++) {
if (p[j] < m) {
i = j;
m = p[j];
}
}
return i;
}
/*
* 判斷兩個 double 數組是否相等。 長度一樣且對應位置值相同返回真。
*/
public static boolean equal(double[] a, double[] b) {
if (a.length != b.length) {
return false;
} else {
for (int i = 0; i < a.length; i++) {
if (a[i] != b[i]) {
return false;
}
}
}
return true;
}
}
posted on 2012-01-12 15:37
SIMONE 閱讀(380)
評論(0) 編輯 收藏 所屬分類:
JAVA