`

K-均值算法

 
阅读更多

总是有废话要先说~~

二妹原创,转载请注明出处,大家讨论~

上次面试,写自我评价的缺点,我写的比较胖~~然后拿offer了,人啊 就是要看得见的实诚!

 

----------------------------------------我是废话分割线 -------------------------------------------------------------

 

web上大量的数据,希望对这些数据进行聚类,而事先并不知道该怎么聚类,k-均值算法则是将大数据聚为k类。

关键要素:

1:用户事先要确定K的值,这个可能需要大量的测试优化k值。k值代表将数据聚为k类,那么将会产生k个簇的质心(均值所在的位置)。

2:聚类的的数据节点之间必须是可以计算平均值。K均值的思想就是某一堆数据都在一个均值的附近,那么将这一堆数据划为一簇。

3:适用于球状分布的数据。例如如果数据是环形分布的,直观上应该将同一环形的数据归为一类,而用k均值则可能分为扇形簇。

4:初始的质心选择得不同,则得到的聚类也会不同。

例如如下图,当k为3的时候,下面红黄蓝是正确的分类,使用k均值算法可以正确的分类第一类,而第二类则会出现错误。

 

以Person为例,现在有一堆人的集合,将他们分为三类,按年龄相近来分类。

 

Person对象,相当于集合中的节点。

package com.zyp.learn.datamining.algorithm;

public class Person {
	private int age;
	private String name;
	
	public Person(String name,int age){
		this.name = name;
		this.age = age;
	}
	public int getAge() {
		return age;
	}
	public void setAge(int age) {
		this.age = age;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
}

 

算法实现类:

    package com.zyp.learn.datamining.algorithm;  
      
    import java.util.ArrayList;  
    import java.util.HashMap;  
    import java.util.HashSet;  
    import java.util.List;  
    import java.util.Map;  
    import java.util.Set;  
      
      
    /** 
     * K均值算法 
     * @author 卓二妹 2012/10/31 
     * 
     */  
    public class KAverageAlgorithm {  
          
        public static void main(String[] args){  
            //生成集合,年龄随机生成0-99的数字  
//            Set<Person> personSet= initSet(5);  
    
            //生成固定值集合,便于调试        	 
               Set<Person> personSet= initSet();  
              
            System.out.print("集合元素:");  
            for(Person p : personSet){  
                System.out.print(p.getAge()+" ");  
            }  
            System.out.println();  
            // 调用无监督学习的k均值算法,将这50人按年龄分为3类,如老、中、青  
            Person[] centerArray = cluster(3,personSet);   
              
            System.out.print("质心:");  
            for(Person center : centerArray){  
                System.out.print(center.getAge()+" ");  
            }  
              
            //标记元素所属质心  
            Map<String,List> map = new HashMap();  
              
            //集合中的某个元素所属的质心,加到该质心对应的数组上  
            for(Person p: personSet){  
                int index = nearestIndex(centerArray,p);//p属于centerArray[index]质心  
                List<Person> lst = map.get(centerArray[index].getAge()+"");  
                if(lst==null){  
                    lst = new ArrayList();  
                    map.put(centerArray[index].getAge()+"",lst);  
                }  
                lst.add(p);  
            }  
              
            System.out.println("\n质心包含的元素:");  
            for(Person center : centerArray){  
                System.out.print(center.getAge()+" :");  
                List<Person> lst = map.get(center.getAge()+"");  
                if(lst!=null){  
                    for(Person p : lst){  
                        System.out.print(p.getAge()+" ");  
                    }  
                }  
                System.out.println("\n");  
            }  
        }  
          
        /** 
         * 将person集合分类,按照person的年龄维度来分类。 
         * 分为k个年龄段,而每个年龄段是事前并不知道。 
         * 用k-均值算法的硬盘版本,只需要遍历一次全集。 
         * @param k:簇的数量 
         * @param personSet:要划分簇的全集 
         * @return 质心的数组 
         */  
        public static Person[] cluster(int k,final Set<Person> personSet){  
            Person[] centerArray = new Person[k];   
            //由于集合是无序的,因此在集合中选前k个点做初始的质心(任意k个点)  
            int i = 0;  
            for(Person p:personSet){  
                centerArray[i++] = p;  
                if(i==k){  
                    break;  
                }  
            }  
              
            //进行一遍执行的调整,本次调整中,改变了所属簇的节点的数量为chanedPointNum  
            int chanedPointNum = -1;  
            //直到没有任何person所属簇都不再变化后,结束分类  
            boolean isExit = false;
            while(isExit){  
            	Person[] newCenterArray = adjustCenteroid(centerArray,personSet);  
            	isExit = exit(newCenterArray,centerArray,personSet);
            }  
              
            return centerArray;  
        }  
          
        /** 
         * 进行一遍质心的调整 
         * @param centerArray 质心数组 
         * @param personSet 全集 
         * return 返回本轮调整质心,改变了所属簇的Person的个数 
         */  
        public static Person[] adjustCenteroid(final Person[] centerArray,final Set<Person> personSet){  
            int changedPointNum = 0;//本次调整质心,改变了所属的簇的节点的个数  
            int oldIndex = -1;  
            int newIndex = -1;  
            int k = centerArray.length;  
            //distArray[i]代表该划划分到第i类的年龄的总和  
            int[] distArray = new int[k];  
              
            //numberArray[i]代表划分到第i类的年龄有多少个  
            int[] numberArray = new int[k];  
              
            //待返回的新质心
            Person[] newCenterArray  = new Person[k];
            
            //将数组元素初始化为0  
            initArray(distArray);  
            initArray(numberArray);  
              
            for(Person tempPerson:personSet){  
                //计算该tempPerson到centerArray的第index质心最近  
                int index = nearestIndex(centerArray,tempPerson);  
                //则该tempPerson被划为第index质心代表的簇中  
                distArray[index] = distArray[index] + tempPerson.getAge();  
                numberArray[index] ++;  
            }  
              
            //已将每个元素分到k个质心中,重新计算每个簇的均值,得到新的质心  
            for(int index = 0; index<k;index++){  
            	newCenterArray[index] = new Person("",distArray[index]/numberArray[index]);
            }  
            return newCenterArray;  
        }  
        
        /**
         * 质心调整的退出标准 
         * @param centerArray当前的质心
         * @param oldCenterArray 调整前的质心
         * @param personSet 数据集合
         * @return 数据集合的簇在质心调整前后无变化,则返回true
         */
        public static boolean exit(final Person[] centerArray,final Person[] oldCenterArray,final Set<Person> personSet){
        	boolean isExit = false;
        	int changedPointNum = 0;
            
            //遍历person集合,看质心调整后,person的所属簇是否改变  
            for(Person tempPerson:personSet){  
                int newIndex = nearestIndex(centerArray,tempPerson);  
                int oldIndex = nearestIndex(oldCenterArray,tempPerson);  
                if(oldIndex!=newIndex){  
                    changedPointNum++;  
                }
            } 
            if(changedPointNum==0){
            	isExit = true;
            }
        	return isExit;
        }  
        public static void initArray(int array[]){  
            for(int i = 0;i<array.length;i++){  
                array[i] = 0;  
            }  
        }  
          
        public static int nearestIndex(final Person[] centerArray,final Person tempPerson){  
            int minIndex = 0;//与该点距离最近的质心的index  
            int minValue = 100;//与最近的质心的距离  
              
            for(int i = 0;i<centerArray.length;i++){  
                int centerAge = centerArray[i].getAge();  
                int temp = Math.abs(tempPerson.getAge()-centerAge);//数据点的年龄与质心距离  
                if(temp<=minValue){  
                    minValue = temp;//  
                    minIndex = i;  
                }  
            }  
            return minIndex;  
        }  
          
      
          
        /** 
         * 初始化集合中的数据 
         * @param count:需要生成的集合的元素个数 
         * @return 
         */  
        public static Set<Person> initSet(int count){  
            Set<Person> set = new HashSet();  
    //      System.out.print("初始集合:");  
            for(int i=0;i<count;i++){  
                String name = "person"+i;  
                //随即生成0--99的人的年龄  
                int age = (int)(Math.random()*100);  
    //          System.out.print(age+" ");  
                set.add(new Person(name,age));  
            }  
            System.out.println();  
            return set;  
        }  
          
        /** 
         * 初始化集合中的数据,指定一些出错的数据,便于调试 
         * @return 
         */  
        public static Set<Person> initSet(){  
            Set<Person> set = new HashSet();  
            set.add(new Person("", 69));
            set.add(new Person("", 30));
            set.add(new Person("", 75));
            set.add(new Person("", 12));
            set.add(new Person("", 14));
            return set;  
        } 
    }  
 

运行一下main方法,随机生成5个人,按年龄分为3类,打印结果如下:


集合元素:75 69 14 12 30
质心:75 69 14
质心包含的元素:
75 :75

69 :69

14 :14 12 30

 

二天空了再来解释算法,敬请期待~

 

分享到:
评论

相关推荐

    K-均值算法的高斯计分布

    《K-均值算法与高斯混合模型》 K-均值算法,是数据挖掘领域广泛应用的一种无监督学习方法,主要用于对数据进行聚类分析。它通过迭代过程将数据分配到预先设定好的K个类别中,使得每个类别内的数据点间差异最小,...

    新的K-均值算法最佳聚类数确定方法

    ### 新的K-均值算法最佳聚类数确定方法 #### 概述 在数据挖掘与机器学习领域中,K-均值算法是一种非常流行的无监督学习方法,主要用于聚类分析。该算法通过将数据集划分为多个聚类(或组),使得每个数据点都属于...

    k-均值算法的java实现

    《k-均值算法的Java实现详解》 k-均值算法(K-Means)是一种广泛应用的无监督学习方法,常用于数据聚类。它通过迭代过程将数据分配到预先设定的k个聚类中,以最小化各聚类内部的平方误差和。在Java编程环境中,我们...

    kmeans_k-均值算法聚类_K-均值_k均值聚类_K._

    K-均值算法的核心思想是将数据点分配到最近的聚类中心,然后更新这些中心为该聚类所有点的均值,这个过程会反复进行直到聚类结果不再改变或达到预设的迭代次数。 下面我们将深入探讨K-均值算法的细节: 1. **算法...

    JAVA实现K-均值算法

    K-均值算法是聚类中最常用且直观的方法之一,它通过迭代将数据点分配到最近的聚类中心,直到聚类中心不再显著变化或者达到预设的迭代次数为止。在这个名为"JAVA实现K-均值算法"的项目中,作者提供了一个用JAVA编写的...

    模糊K-均值算法及其matlab实现.docx

    模糊K-均值算法是一种基于模糊集合理论的聚类方法,它是在经典的K-均值算法基础上发展起来的。K-均值算法是通过迭代更新样本所属类别和聚类中心来实现数据分组,而模糊K-均值算法允许样本同时属于多个类别,其分类...

    用于文档聚类的高效稀疏球面k-均值算法_Efficient Sparse Spherical k-Means for Docum

    "用于文档聚类的高效稀疏球面k-均值算法"针对的就是这个问题,它提供了一种改进的方法来应对高维度且稀疏的文档表示。球面k-均值(Spherical k-Means)算法在许多情况下表现良好,且计算效率高,但由于其时间复杂度...

    模糊K-均值算法及其matlab实现.pdf

    模糊K-均值算法是一种基于模糊集合理论的聚类方法,它是在经典的K-均值算法基础上发展起来的。K-均值算法是通过迭代更新样本的类别归属和聚类中心来达到优化聚类效果的目的,而模糊K-均值算法则允许样本同时隶属于多...

    基于K-均值算法的数据挖掘技术研究及应用.pdf

    8. 文章结构和内容:文档分为摘要、引言、K-均值算法概述、K-均值算法计算模型、应用案例以及作者简介等部分,系统性地介绍了K-均值算法的原理、计算方法以及在特定案例中的应用。 这些知识点覆盖了K-均值算法的...

    数据挖掘K-均值算法实现毕业设计.docx

    ### 数据挖掘K-均值算法实现毕业设计 #### 1. 研究背景与意义 随着信息技术的飞速发展,特别是互联网的普及,我们每天都在产生大量的数据。这些数据覆盖了生活的方方面面,如科学研究、政府办公、军事分析、企业...

Global site tag (gtag.js) - Google Analytics