簡介：本Demo是參照這個網(wǎng)站上的Demo自己用Java實現(xiàn)的。將Java打包為Jar，再將Jar轉(zhuǎn)為exe，源代碼及程序Demo下載請點我。

K-Means算法簡介

　　我盡量用通俗易懂但不規(guī)范的語言來描述K-Means算法。

　　K-Means算法是數(shù)據(jù)挖掘十大算法之一，是一種聚類算法，也是最簡單的無監(jiān)督學(xué)習(xí)（unsupervised?learning）算法之一。

　　假設(shè)有一個元素集合，我們的目標(biāo)是將該集合中的元素劃分成K個簇（就是K個部分），每個簇內(nèi)的元素相似度較高，不同簇的元素相似度較低（正所謂物以類聚，人以群分）。

　　而K-Means算法就是實現(xiàn)這樣一個目標(biāo)的算法。

　　先看Demo，會有直觀的了解。

K-Means算法步驟

　　因為要做可視化界面，所以我們現(xiàn)在只討論二維的情況，即每個元素用2個數(shù)表示。

　　假如我們的元素集合是平面上的N個點，計算相似度用的是兩點之間的歐氏距離（當(dāng)然也可以使用其他距離公式，相關(guān)距離公式見下部分），兩點距離越短則表示相似度越高。那么算法步驟大概是這個樣子：

　　Step?1.?隨機產(chǎn)生K個點，作為K個簇的中心（注意K<=N）

　　Step?2.?對N個點中的每一個點，計算該點離哪個中心最近，離哪個中心最近就屬于哪個簇。　　

　　Step?3.?更新每個簇的中心（取簇中的元素的坐標(biāo)的均值）

　　Step?4.?重復(fù)Step2和Step3直到所有簇的中心不再改變。

Java實現(xiàn)代碼（帶圖形界面）

import java.awt.*; import java.awt.event.*; import javax.swing.*; import javax.swing.JFrame; import javax.swing.JPanel; import java.util.Random; import java.applet.*;class PaintovalPane extends JPanel {/*K-Means*/int K = 5; //K個中心int N = 50; //N個點int D = 2; //二維元素 Random rand = new Random();class Point{ Point(){initial();}void initial(){/*初始化為[0,600)的隨機點，簇編號為-1，無意義*/for (int i = 0; i < D; ++i)x[i] = rand.nextDouble()*600;clusterNum = -1;}double x[] = new double[D]; //坐標(biāo)int clusterNum; //簇編號 };Point p[]; //數(shù)據(jù)點Point centroid[]; //中心點Point oldCentroid[]; //上一次的中心點，用于確定中心點是否不再改變Color colors[]; //表示不同簇的顏色值/*歐式距離*/double Euclidean(Point p1, Point p2){double dis = 0;for (int i = 0; i < D; ++i)dis += (p1.x[i]-p2.x[i])*(p1.x[i]-p2.x[i]);return Math.sqrt(dis);}/*更新中心點*/void updateCentroid(int clusterNum){ for (int i = 0; i < D; ++i)centroid[clusterNum].x[i] = 0;int clusterSize = 0;for (int i = 0; i < N; ++i)if (p[i].clusterNum == clusterNum){clusterSize++;for (int j = 0; j < D; ++j)centroid[clusterNum].x[j] += p[i].x[j];}if (clusterSize == 0)return;for (int i = 0; i < D; ++i)centroid[clusterNum].x[i] /= (double)clusterSize;}/*更新中心點的接口函數(shù)*/void updateCentroids(){for (int i = 0; i < K; ++i)updateCentroid(i);}/*分配數(shù)據(jù)點到哪個簇*/void assignPoint(int x){double minDis = 99999999;int minIndex = 1;for (int i = 0; i < K; ++i){double curDis = Euclidean(p[x], centroid[i]);if (curDis < minDis){minDis = curDis;minIndex = i;}}p[x].clusterNum = minIndex;}/*分配數(shù)據(jù)點到哪個簇的接口函數(shù)*/void assign(){for (int i = 0; i < N; ++i)assignPoint(i);}/*判斷2點是否同一個點*/Boolean samePoint(Point p1, Point p2){if (p1.clusterNum != p2.clusterNum)return false;for (int i = 0; i < D; ++i)if (p1.x[i] != p2.x[i])return false;return true;}/*判斷算法是否終止*/Boolean stop(){/*如果每一個中心點都與上一次的中心點相同，則算法終止，否則更新oldCentroid*/for (int i = 0; i < K; ++i)if (!samePoint(oldCentroid[i], centroid[i])) {for (int j = 0; j < K; ++j)copy(oldCentroid[j],centroid[j]);return false;}return true;}/*令p1 = p2*/void copy(Point p1, Point p2){p1.clusterNum = p2.clusterNum;for (int i = 0; i < D; ++i)p1.x[i] = p2.x[i];}/*初始化*/void init(){/*分配內(nèi)存*/p = new Point[N]; centroid = new Point[K];oldCentroid = new Point[K];colors = new Color[K];for (int i = 0; i < N; ++i){p[i] = new Point();p[i].initial();}for (int i = 0; i < K; ++i){centroid[i] = new Point();oldCentroid[i] = new Point();centroid[i].initial();oldCentroid[i].initial();copy(oldCentroid[i],centroid[i]);colors[i] = new Color(rand.nextInt(255), rand.nextInt(255), rand.nextInt(255));}}/*默認(rèn)構(gòu)造函數(shù)，調(diào)用初始化函數(shù)*/PaintovalPane(){init();}/*重載繪圖函數(shù)*/public void paintComponent(Graphics g){super.paintComponent(g);setBackground(Color.white);/*畫數(shù)據(jù)點（圓形），根據(jù)簇編號來確定顏色*/for (int i = 0; i < N; ++i){int x = (int)p[i].x[0], y = (int)p[i].x[1];if (p[i].clusterNum == -1)g.setColor(Color.black);elseg.setColor(colors[p[i].clusterNum]);g.fillOval(x, y, 15, 15);}/*畫中心點（矩形），根據(jù)簇編號來確定顏色*/for (int i = 0; i < K; ++i) {int x = (int)centroid[i].x[0], y = (int)centroid[i].x[1];g.setColor(colors[i]);g.fillRect(x, y, 15, 15);}} }class Drawing extends JFrame {/*聲明一系列組件*/JButton jButton1 = new JButton("Start");JButton jButton2 = new JButton("Step");JButton jButton3 = new JButton("Run");JLabel label1 = new JLabel("Points");JLabel label2 = new JLabel("Clusters");JTextField textField1 = new JTextField("This is buffer for text", 15);JTextField textField2 = new JTextField("This is buffer for text", 15);JPanel jPanel = new JPanel();PaintovalPane paint = new PaintovalPane();Drawing(){setTitle("K-Means");setVisible(true);setDefaultCloseOperation(EXIT_ON_CLOSE);setSize (660,710);textField1.setText(String.valueOf(paint.N));textField2.setText(String.valueOf(paint.K));/*Start按鈕的監(jiān)聽器*/jButton1.addActionListener(new ActionListener(){public void actionPerformed(ActionEvent ae) {int input1 = Integer.parseInt(textField1.getText());int input2 = Integer.parseInt(textField2.getText());/*判斷輸入是否合法*/if (input1 > 500 || input1 <= 0){JOptionPane.showMessageDialog(null, "Please input the number between 1-500");}else if (input2 > input1 || input2 <= 0){JOptionPane.showMessageDialog(null, "Please input the number between 1-Points");}else{paint.N = input1;paint.K = input2;paint.init();paint.repaint();jButton2.setText("Step");jButton2.setEnabled(true);jButton3.setText("Run");jButton3.setEnabled(true);}}});/*Step按鈕的監(jiān)聽器*/jButton2.addActionListener(new ActionListener(){public void actionPerformed(ActionEvent ae) {paint.assign();paint.updateCentroids();/*算法終止的話讓按鈕變灰并提示算法結(jié)束*/if (paint.stop()){jButton2.setText("End");jButton2.setEnabled(false);jButton3.setText("End");jButton3.setEnabled(false);}paint.repaint();}});/*Run按鈕的監(jiān)聽器*/jButton3.addActionListener(new ActionListener(){public void actionPerformed(ActionEvent ae) {do{paint.assign();paint.updateCentroids();paint.repaint();}while(!paint.stop());/*算法終止的話讓按鈕變灰并提示算法結(jié)束*/jButton2.setText("End");jButton2.setEnabled(false);jButton3.setText("End");jButton3.setEnabled(false);}});jPanel.add(label1);jPanel.add(textField1);jPanel.add(label2);jPanel.add(textField2);jPanel.add(jButton1);jPanel.add(jButton2);jPanel.add(jButton3);jPanel.setBackground(new Color(1,255,1));add(BorderLayout.NORTH,jPanel);add(BorderLayout.CENTER, paint);} }public class Hello extends Applet {public static void main(String args[]){Drawing d = new Drawing();} } View Code

C++實現(xiàn)代碼

#include <iostream> #include <cmath> #include <ctime> #include <cstdlib> using namespace std;#define K 10 //簇數(shù) #define N 200 //點數(shù) #define D 2 //維數(shù)/*產(chǎn)生0-100的隨機數(shù)*/ double random() { return 100*(double)rand()/(double)RAND_MAX; } class Point {public:Point(){for (int i = 0; i < D; ++i)x[i] = random();clusterNum = -1;}double x[D]; //坐標(biāo)int clusterNum; //所屬簇的編號 };Point p[N]; Point centroid[K]; Point oldCentroid[K];/*歐式距離*/ double Euclidean(Point p1, Point p2) {double dis = 0;for (int i = 0; i < D; ++i)dis += (p1.x[i]-p2.x[i])*(p1.x[i]-p2.x[i]);return sqrt(dis); }/*重新計算編號為clusterNum的簇的重心*/ void updateCentroid(int clusterNum) { for (int i = 0; i < D; ++i)centroid[clusterNum].x[i] = 0;int clusterSize = 0;for (int i = 0; i < N; ++i)if (p[i].clusterNum == clusterNum){clusterSize++;for (int j = 0; j < D; ++j)centroid[clusterNum].x[j] += p[i].x[j];}if (clusterSize == 0)return;for (int i = 0; i < D; ++i)centroid[clusterNum].x[i] /= (double)clusterSize; }void updateCentroids() {for (int i = 0; i < K; ++i)updateCentroid(i); } /*計算某點屬于哪一簇*/ void assignPoint(Point &point) {double minDis = INT_MAX;int minIndex = 1;for (int i = 0; i < K; ++i){double curDis = Euclidean(point, centroid[i]);if (curDis < minDis)minDis = curDis, minIndex = i;}point.clusterNum = minIndex; }void assign() {for (int i = 0; i < N; ++i)assignPoint(p[i]); } /*比較是否相同的兩個點，注意double的比較有時候可能出現(xiàn)問題*/ bool samePoint(Point p1, Point p2) {if (p1.clusterNum != p2.clusterNum)return false;for (int i = 0; i < D; ++i)if (p1.x[i] != p2.x[i])return false;return true; }/*判斷重心是否不變，若重心不再變化，算法終止*/ bool stop() {for (int i = 0; i < K; ++i)if (!samePoint(oldCentroid[i], centroid[i])) //若算法未停止，則更新oldCentroid {for (int j = 0; j < K; ++j)oldCentroid[j] = centroid[j];return false;}return true; }void init() {srand(time(0));/*如果類內(nèi)成員是基本類型，則默認(rèn)的operator=可以完成簡單的賦值功能*/for (int i = 0; i < K; ++i)oldCentroid[i] = centroid[i]; }int main() {init();do{assign();updateCentroids();}while(!stop()); } View Code

ps.一點收獲，C++中，自定義類提供的默認(rèn)operator=是可以完成基本數(shù)據(jù)類型的賦值的，但是Java的operator=并不是簡單賦值，而是=左邊的類變成=右邊的類引用。

程序效果

　　按下Start

　　按下Step

　　按下Run

將Java程序轉(zhuǎn)為exe

　　為了能夠讓Java程序到處跑（不是每個電腦都裝有Java虛擬機的），決定將Java程序轉(zhuǎn)為exe。

　　步驟如下：

　　1、將.java編譯為.class

進入cmd，cd切換到.java文件目錄下，執(zhí)行javac Hello.java，產(chǎn)生Hello.class

　　2、將相關(guān)的.class打包為一個.jar文件

　　繼續(xù)在當(dāng)前目錄下，執(zhí)行jar cvf Hello.jar *.class，產(chǎn)生Hello.jar

　　注意，此時Hello.jar是不能直接執(zhí)行的，因為缺少入口函數(shù)。我們用360壓縮打開Hello.jar，可以看到有一個META-INF文件夾，里面有一個MANIFEST.MF文件，用筆記本打開，在最后面添加Main-Class: Hello。（注意1，Hello是我自己的入口函數(shù)所在的類；注意2，Main-Class:后面有空格）。這個時候.jar文件應(yīng)該可以用java虛擬機執(zhí)行了。

　　3、利用軟件j2ewiz.exe?or click me?將.jar文件轉(zhuǎn)為.exe

距離公式

　　1）Minkowski?Distance（閔可夫斯基距離）——λ可取任意值，可以是負(fù)數(shù)，也可以是正數(shù)，或是無窮大。

　　2）Euclidean?Distance（歐氏距離）——也就是第一個公式λ=2的情況，高中學(xué)過的最基本的平面上兩點的距離公式。

?

　　3）CityBlock?Distance（曼哈頓距離）——也就是第一個公式λ=1的情況。

?

　　如下圖，綠色代表歐氏距離，也就是直線距離；而紅色、藍色和黃色代表等價的曼哈頓距離。

參考資料

算法雜貨鋪——k均值聚類(K-means)

K-Means算法Demo

曼哈頓距離

斯坦福公開課

java如何打JAR包

轉(zhuǎn)載于:https://www.cnblogs.com/chenyg32/p/3793207.html

總結(jié)

以上是生活随笔為你收集整理的K-Means算法Demo的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。