当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

K-MEANS聚类算法

发表于: 2011-10-06   作者:chuanwang66   来源:转载   浏览次数:
摘要: K-MEANS 算法     输入聚类个数 k ,以及包含 n 个数据对象的数据库,输出满足方差最小标准的 k 个聚类。     k-means 算法接受输入量 k ;然后将 n 个数据对象划分为 k 个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。聚类相似度是利用各聚

K-MEANS 算法

    输入聚类个数 k ,以及包含 n 个数据对象的数据库,输出满足方差最小标准的 k 个聚类。

    k-means 算法接受输入量 k ;然后将 n 个数据对象划分为 k 个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个 中心对象 (引力中心)来进行计算的。

    k-means 算法的工作过程说明如下:首先从 n 个数据对象任意选择 k 个对象作为初始聚类中心;而对于所剩下其它对象,则根据它们与这些聚类中心的相似度(距离),分别将它们分配给与其最相似的(聚类中心所代表的)聚类;然后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值);不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数 k 个聚类具有以下特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。

处理流程

  ( 1 n 个数据对象任意选择 k 个对象作为初始聚类中心;

  ( 2 循环( 3 )到( 4 )直到每个聚类不再发生变化为止

  ( 3 根据每个聚类对象的均值(中心对象),计算每个对象与这些中心对象的距离;并根据最小距离重新对相应对象进行划分;

  ( 4 重新计算每个(有变化)聚类的均值(中心对象)

 

计算复杂度:

O(nkt), 其中 t 是迭代次数。



下面是程序代码:

效果是分成了1,2,3,5,6,7,9,10,11 和 100,150,200 和 1000三组,和感觉上的聚类一样:)

 

public class BasicKMeans {

    public static void main(String[] args) {

        double [] p={1,2,3,5,6,7,9,10,11,100,150,200,1000};

        int k=3;

        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]+ "\t" );

            }

            System. out .println();

        }

    }

   

    /**

      * 聚类函数

      * @param p 数据对象

      * @param k 聚类数目

      * @return

      */

    public static double [][] cluster( double [] p, int k){

        double [] c= new double [k];   // 旧的聚类中心

        double [] nc= new double [k];  // 新的聚类中心

        double [][] g;               // 结果

       

        /*

          * 1. 初始化聚类中心(经典方式是随机选取 k 个,本例中取前 k 个)

          */

        for ( int i=0;i<k;i++){

            c[i]=p[i];

        }

       

        /*

          * 2. 循环聚类,更新聚类中心直到不变为止

          */

        while ( true ){

            /*

              * 2.1 根据数组中每个元素分配给当前聚类中心

              */

            g=group (p,c);

            /*

              * 2.2 计算分配后的聚类中心

              */

            for ( int i=0;i<g. length ;i++){

                nc[i]=center (g[i]);

            }

           

            /*

              * 2.3 更新聚类中心

              */

            if (!equal (nc,c)){

                c=nc;

                nc= new double [k];

            } else {

                break ;

            }

        } //while(true)

       

        return g;

    }

   

    /**

      * 根据聚类中心 c 将数组 p 中元素分配到不同类别 !!!

      * @param p 待分配的数组

      * @param c 聚类中心数组

      * @return

      */

    private static double [][] group( double [] p, double [] c) {

        int [] gi= new int [p. length ]; // 记录每个元素被归到哪一类

       

        /*

          * 考察每个元素 pi 同每个聚类中心 cj 的距离,

          * 距离最小就将 pi 归为 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 minDistOffset=min (d);

            gi[i]=minDistOffset;

        }

       

        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;

    }

 

    /**

      * 重新计算一个类的中心(简单的以为聚类返回其算术平均值)

      * @param gi

      * @return

      */

    private static double center( double [] gi) {

        return sum (gi)/gi. length ;

    }

   

    /**

      * 返回两点的一维欧氏距离

      */

    private static double distance( double x, double y){

        return Math.abs (x-y);

    }

   

    /**

      * 返回数组和

      */

    private static double sum( double [] arr) {

        double sum=0.0;

        for ( int i=0;i<arr. length ;i++){

            sum+=arr[i];

        }

        return sum;

    }

   

    /**

      * 返回数组(第一个)最小元素下标

      */

    private static int min( double [] arr){

        int min=0;

        double minEle=arr[0];

        for ( int i=1;i<arr. length ;i++){

            if (arr[i]<minEle){

                min=i;

                minEle=arr[i];

            }

        }

        return min;

    }

   

    /**

      * 判断两个数组是否相同

      */

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

    }

} 

K-MEANS聚类算法

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
在数据挖掘中,K-Means算法是一种cluster analysis的算法,其主要是来计算数据聚集的算法,主要通过
在数据挖掘中,K-Means算法是一种cluster analysis的算法,其主要是来计算数据聚集的算法,主要通过
在数据挖掘中,K-Means算法是一种cluster analysis的算法,其主要是来计算数据聚集的算法,主要通过
最近由于工作需要,对聚类算法做了一些相关的调研。现将搜集到的资料和自己对算法的一些理解整理如
第一章 引言 第二章 预备知识 第三章 直接聚类法 第四章 K-means 第五章 DBSCAN 第六章 OPTICS <
聚类术语无监督的学习,K-means算法是基于距离的聚类算法,采用 距离作为相似性的评价指标,如果两
4.1、摘要 在前面的文章中,介绍了三种常见的分类算法。分类作为一种监督学习方法,要求必须事先明
4.1、摘要 在前面的文章中,介绍了三种常见的分类算法。分类作为一种监督学习方法,要求必须事先明
4.1、摘要 在前面的文章中,介绍了三种常见的分类算法。分类作为一种监督学习方法,要求必须事先明
4.1、摘要 在前面的文章中,介绍了三种常见的分类算法。分类作为一种监督学习方法,要求必须事先明
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号