Java实现的基于欧式距离的聚类算法的Kmeans作业

冷不防 2024-04-07 14:33 60阅读 0赞

## Kmeans作业 ##

#### 环境配置 ####

java环境，使用原生的Java UI组件JPanel和JFrame

#### 算法原理 ####

基于欧式距离的聚类算法，其认为两个目标的距离越近，相似度越大。

该实验产生的点为二维空间中的点。

##### 欧式距离 #####

n维空间中的两个点X，Y

d i s t ( X , Y ) = ∑ i = 1 n ( x i − y i ) 2 dist(X, Y) = \\sqrt\{\\sum\_\{i = 1\}^\{n\} (x\_\{i\} - y\_\{i\})^\{2\}\} dist(X,Y)=∑i=1n(xi−yi)2

##### 算法过程 #####

1.  选择k，聚类的数量。
2.  选择k个点作为聚类中心。
3.  对每个样本点计算到k个聚类中心的距离，采用的是欧氏距离，将其分类到距离最近的类别中。
4.  根据每个类别，计算被分类在该类别中的所有点的中心。
5.  如果计算出来的中心和聚类中心相同，则退出循环，否则以新的计算出来的中心为每个聚类的聚类中心，不断重复3 - 4步。

#### 核心代码 ####

##### 设定K #####

/*Step按钮的监听器*/
    jButton2.addActionListener(new ActionListener() {
        
        public void actionPerformed(ActionEvent ae) {
        
    
    
            painting.assign();
    
            painting.updateCentroids();
    
    
            /*算法终止的话让按钮变灰并提示算法结束*/
            if (painting.stop(num++)) {
        
                jButton2.setText("End");
                jButton2.setEnabled(false);
            }
    
    
            painting.repaint();
        }
    });

##### 计算欧式距离 #####

/*欧式距离*/
    double Euc(Point p1, Point p2) {
        
        double distance = 0.0;
    
        for (int i = 0; i < Dimension; ++i)
            distance += (p1.x[i] - p2.x[i]) * (p1.x[i] - p2.x[i]);
        return Math.sqrt(distance);
    }

##### 更新中心点 #####

/*更新中心点*/
    void updateCentroid(int clusterNum) {
        
        //将newCluster数组的那个中心点置空
        for (int i = 0; i < Dimension; ++i)
            newCluster[clusterNum].x[i] = 0;
    
        int clusterSize = 0;
    
        for (int i = 0; i < Nodes; ++i)
            if (p[i].cluster == clusterNum) {
        
                //这个簇中有多少点
                clusterSize++;
                for (int j = 0; j < Dimension; ++j)
                    newCluster[clusterNum].x[j] += p[i].x[j];
            }
    
    
        if (clusterSize == 0)
            return;
    
        for (int i = 0; i < Dimension; ++i)
            newCluster[clusterNum].x[i] /= (double) clusterSize;
    }

##### 计算每个点的分类 #####

/*分配数据点到哪个簇*/
    void assignPoint(int x) {
        
        double minDistance = 99999999;
        int nodeClassify = 1;
        for (int i = 0; i < K; ++i) {
        
            //计算欧式距离
            double newDistance = Euc(p[x], newCluster[i]);
            if (newDistance < minDistance) {
        
                minDistance = newDistance;
                nodeClassify = i;
            }
        }
        p[x].cluster = nodeClassify;
    }

##### 判断终止条件 #####

/*判断算法是否终止*/
    Boolean stop(int currentTime) {
        
        //超过迭代次数
        if (currentTime > range) {
        
            int num = 1;
            System.out.println("超过迭代次数");
            for (Point i : oldCluster) {
        
                System.out.println("中心点" + num + "坐标：(" + i.x[0] + "," + i.x[1] + ")");
                num++;
            }
            return true;
        }
        /*如果每一个中心点都与上一次的中心点相同，则算法终止，否则更新oldCentroid*/
        for (int i = 0; i < K; ++i)
            if (!samePoint(oldCluster[i], newCluster[i])) {
        
                for (int j = 0; j < K; ++j)
                    copy(oldCluster[j], newCluster[j]);
                return false;
            }
        int num = 1;
        System.out.println("迭代完成");
        for (Point i : oldCluster) {
        
            System.out.println("中心点" + num + "坐标：(" + i.x[0] + "," + i.x[1] + ")");
            num++;
        }
        return true;
    }

#### 实验结果 ####

![在这里插入图片描述][7370be8ea709480486c9d591fbe5eed3.png]

点击start之后，产生新的随机点与初始聚类中心

![在这里插入图片描述][b46ae249dc9944a89ee0ca896754023d.png]  
![在这里插入图片描述][901c60fcae674e3395b1f24299cec00c.png]  
![在这里插入图片描述][a7170dfdb9ce43f39025e04386fc02dd.png]  
![在这里插入图片描述][72a75674081e45f5b449014e0547c6e7.png]

点击step，将每一步的迭代展示出来，这里展示了4步，从左上角的图开始。

![在这里插入图片描述][c7225ef259194cf2be2a0ccc1d708f01.png]

[7370be8ea709480486c9d591fbe5eed3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/a15469d192e341ec998ba0c1643d1112.png
[b46ae249dc9944a89ee0ca896754023d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/a76f9ed5ccb24275a6a294127d42f8cc.png
[901c60fcae674e3395b1f24299cec00c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/b90bf224de5a4404ad1a942199c49e8f.png
[a7170dfdb9ce43f39025e04386fc02dd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/2425ae8cf9a1465ba84f70117790058b.png
[72a75674081e45f5b449014e0547c6e7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/667206bfbd004438b607e73ed7f4ad14.png
[c7225ef259194cf2be2a0ccc1d708f01.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/97894347c28a482e920d7860b73e05c1.png