简介：本Demo是参照这个网站上的Demo自己用Java实现的。将Java打包为Jar，再将Jar转为exe，源代码及程序Demo下载请点我。

K-Means算法简介

　　我尽量用通俗易懂但不规范的语言来描述K-Means算法。

　　K-Means算法是数据挖掘十大算法之一，是一种聚类算法，也是最简单的无监督学习（unsupervised learning）算法之一。

　　假设有一个元素集合，我们的目标是将该集合中的元素划分成K个簇（就是K个部分），每个簇内的元素相似度较高，不同簇的元素相似度较低（正所谓物以类聚，人以群分）。

　　而K-Means算法就是实现这样一个目标的算法。

　　先看Demo，会有直观的了解。

K-Means算法步骤

　　因为要做可视化界面，所以我们现在只讨论二维的情况，即每个元素用2个数表示。

　　假如我们的元素集合是平面上的N个点，计算相似度用的是两点之间的欧氏距离（当然也可以使用其他距离公式，相关距离公式见下部分），两点距离越短则表示相似度越高。那么算法步骤大概是这个样子：

　　Step 1. 随机产生K个点，作为K个簇的中心（注意K<=N）

　　Step 2. 对N个点中的每一个点，计算该点离哪个中心最近，离哪个中心最近就属于哪个簇。　　

　　Step 3. 更新每个簇的中心（取簇中的元素的坐标的均值）

　　Step 4. 重复Step2和Step3直到所有簇的中心不再改变。

Java实现代码（带图形界面）

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];    //坐标

        int clusterNum;                //簇编号

    };

    Point p[];                //数据点

    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;

    }

    /*更新中心点的接口函数*/

    void updateCentroids()

    {

        for (int i = 0; i < K; ++i)

            updateCentroid(i);

    }

    /*分配数据点到哪个簇*/

    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;

    }

    /*分配数据点到哪个簇的接口函数*/

    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()

    {

        /*分配内存*/

        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));

        }

    }

    /*默认构造函数，调用初始化函数*/

    PaintovalPane()

    {

        init();

    }

    /*重载绘图函数*/

    public void paintComponent(Graphics g)

    {

        super.paintComponent(g);

        setBackground(Color.white);

        /*画数据点（圆形），根据簇编号来确定颜色*/

        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);

            else

                g.setColor(colors[p[i].clusterNum]);

            g.fillOval(x, y, 15, 15);

        }

        /*画中心点（矩形），根据簇编号来确定颜色*/

        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按钮的监听器*/

        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按钮的监听器*/

        jButton2.addActionListener(new ActionListener(){

            public void actionPerformed(ActionEvent ae)

            {

                paint.assign();

                paint.updateCentroids();

                /*算法终止的话让按钮变灰并提示算法结束*/

                if (paint.stop())

                {

                    jButton2.setText("End");

                    jButton2.setEnabled(false);

                    jButton3.setText("End");

                    jButton3.setEnabled(false);

                }

                paint.repaint();

            }

        });

        /*Run按钮的监听器*/

        jButton3.addActionListener(new ActionListener(){

            public void actionPerformed(ActionEvent ae)

            {

                do

                {

                    paint.assign();

                    paint.updateCentroids();

                    paint.repaint();

                }

                while(!paint.stop());

                /*算法终止的话让按钮变灰并提示算法结束*/

                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();

    }

}

C++实现代码

#include <iostream>

#include <cmath>

#include <ctime>

#include <cstdlib>

using namespace std;

#define K 10    //簇数

#define N 200    //点数

#define D 2        //维数

/*产生0-100的随机数*/

double random()

{

    return *(double)rand()/(double)RAND_MAX;

} 

class Point

{

    public:

    Point()

    {

        for (int i = ; i < D; ++i)

            x[i] = random();

        clusterNum = -;

    }

    double x[D];    //坐标

    int clusterNum;    //所属簇的编号

};

Point p[N];

Point centroid[K];

Point oldCentroid[K];

/*欧式距离*/

double Euclidean(Point p1, Point p2)

{

    double dis = ;

    for (int i = ; 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 = ; i < D; ++i)

        centroid[clusterNum].x[i] = ;

    int clusterSize = ;

    for (int i = ; i < N; ++i)

        if (p[i].clusterNum == clusterNum)

        {

            clusterSize++;

            for (int j = ; j < D; ++j)

                centroid[clusterNum].x[j] += p[i].x[j];

        }

    if (clusterSize == )

        return;

    for (int i = ; i < D; ++i)

        centroid[clusterNum].x[i] /= (double)clusterSize;

}

void updateCentroids()

{

    for (int i = ; i < K; ++i)

        updateCentroid(i);

}

/*计算某点属于哪一簇*/

void assignPoint(Point &point)

{

    double minDis = INT_MAX;

    int minIndex = ;

    for (int i = ; i < K; ++i)

    {

        double curDis = Euclidean(point, centroid[i]);

        if (curDis < minDis)

            minDis = curDis, minIndex = i;

    }

    point.clusterNum = minIndex;

}

void assign()

{

    for (int i = ; i < N; ++i)

        assignPoint(p[i]);

}

/*比较是否相同的两个点，注意double的比较有时候可能出现问题*/

bool samePoint(Point p1, Point p2)

{

    if (p1.clusterNum != p2.clusterNum)

        return false;

    for (int i = ; i < D; ++i)

        if (p1.x[i] != p2.x[i])

            return false;

    return true;

}

/*判断重心是否不变，若重心不再变化，算法终止*/

bool stop()

{

    for (int i = ; i < K; ++i)

        if (!samePoint(oldCentroid[i], centroid[i]))    //若算法未停止，则更新oldCentroid

        {

            for (int j = ; j < K; ++j)

                oldCentroid[j] = centroid[j];

            return false;

        }

    return true;

}

void init()

{

    srand(time());

    /*如果类内成员是基本类型，则默认的operator=可以完成简单的赋值功能*/

    for (int i = ; i < K; ++i)

        oldCentroid[i] = centroid[i];

}

int main()

{

    init();

    do

    {

        assign();

        updateCentroids();

    }

    while(!stop());

}

ps.一点收获，C++中，自定义类提供的默认operator=是可以完成基本数据类型的赋值的，但是Java的operator=并不是简单赋值，而是=左边的类变成=右边的类引用。

程序效果

　　按下Start

　　按下Step

　　按下Run

将Java程序转为exe

　　为了能够让Java程序到处跑（不是每个电脑都装有Java虚拟机的），决定将Java程序转为exe。

　　步骤如下：

　　1、将.java编译为.class

进入cmd，cd切换到.java文件目录下，执行javac Hello.java，产生Hello.class

　　2、将相关的.class打包为一个.jar文件

　　继续在当前目录下，执行jar cvf Hello.jar *.class，产生Hello.jar

　　注意，此时Hello.jar是不能直接执行的，因为缺少入口函数。我们用360压缩打开Hello.jar，可以看到有一个META-INF文件夹，里面有一个MANIFEST.MF文件，用笔记本打开，在最后面添加Main-Class: Hello。（注意1，Hello是我自己的入口函数所在的类；注意2，Main-Class:后面有空格）。这个时候.jar文件应该可以用java虚拟机执行了。

　　3、利用软件j2ewiz.exe or click me 将.jar文件转为.exe

距离公式

　　1）Minkowski Distance（闵可夫斯基距离）——λ可取任意值，可以是负数，也可以是正数，或是无穷大。

　　2）Euclidean Distance（欧氏距离）——也就是第一个公式λ=2的情况，高中学过的最基本的平面上两点的距离公式。

　　3）CityBlock Distance（曼哈顿距离）——也就是第一个公式λ=1的情况。

　　如下图，绿色代表欧氏距离，也就是直线距离；而红色、蓝色和黄色代表等价的曼哈顿距离。

参考资料

算法杂货铺——k均值聚类(K-means)

K-Means算法Demo

曼哈顿距离

斯坦福公开课

java如何打JAR包


最新文章

  1. Android异步消息处理机制完全解析，带你从源码的角度彻底理解（转）
  2. [UWP]涨姿势UWP源码——RSS feed的获取和解析
  3. 获取week of year的小程序
  4. Cocos2d-x——CocosBuilder官方帮助文档翻译2 多分辨率支持
  5. [转]前端利器：SASS基础与Compass入门
  6. linux内核——进程，轻量级进程，线程，线程组
  7. PAT1016
  8. python爬虫requests 下载图片
  9. 基于Spring Security OAuth2搭建的Spring Cloud 认证中心
  10. 提供HTML5播放RTSP流 提供微信播放RTSP流 HTML5支持rtsp web播放rtsp，微信支持rtsp
  11. java.util.concurrent包学习笔记（一）Executor框架
  12. NOIp 2018 游记
  13. 【Jmeter自学】Jmeter作用域（五）
  14. centos常用命令--备份
  15. ASP.NET MVC 表格操作
  16. Tomcat学习总结（2）——Tomcat使用详解
  17. CentOS7.5搭建Flask环境python3.6+mysql+redis+virtualenv
  18. sort+函数指针、sort+比较器对象、qsort速度比较
  19. Shadow Mapping 的原理与实践 【转】
  20. [Yii2]yiisoft/yii2 2.0.2 requires bower-asset/jquery 2.1.*@stable | 1.11.*@stable -&gt; no matching package found

热门文章

  1. iOS项目开发实战——使用CoreLocation获取当前位置信息
  2. Unity 背包道具搜索(2)
  3. 【微信小程序】转载：微信小程序之购物车功能
  4. Android实现换肤功能（二）
  5. $(&quot;#SpecialAptitude&quot;).on(&quot;change&quot;,function(){CheckType($(this))})$(&quot;#SpecialAptitude&quot;).on(&quot;change&quot;,CheckType($(this)))
  6. Json数组操作小记 及 JSON对象和字符串之间的相互转换
  7. django学习笔记【003】创建第一个带有model的app
  8. unity, access sprite of UGUI Image
  9. Atitit.用户权限服务 登录退出功能
  10. Atitit.antlr实现词法分析