搜索
K值均值聚类算法在教学分组中的应用引言：K-均值聚类是流行、经典、简单的聚类方法之一。聚类是非监督学习的一种方法，也是常用的统计数据分析技术，应用领域很广，涉及机器学习、数据挖掘、模式识别、图像分析和生物信息学等。在统计和机器学习中，K-均值算法是一种聚类分析方法，它将n个观察对象分类到k个聚类，每个观察对象将被分到与均值最接近的聚类中。其基本思想是：通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。一、K值均值聚类原理所谓聚类问题，就是给定一个元素集合D，其中每个元素具有n个可观察属性，使用某种算法将D划分成k个子集，要求每个子集内部的元素之间相异度尽可能低，而不同子集的元素相异度尽可能高。其中每个子集叫做一个簇。与分类不同，分类是示例式学习，要求分类前明确各个类别，并断言每个元素映射到一个类别，而聚类是观察式学习，在聚类前可以不知道类别甚至不给定类别数量，是无监督学习的一种。目前聚类广泛应用于统计学、生物学、数据库技术和市场营销等领域，相应的算法也非常的多。本文仅介绍一种最简单的聚类算法——k均值（k-means）算法。1.1算法简介k-means算法，也被称为k-平均或k-均值，是一种得到最广泛使用的聚类算法。它是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点，算法的主要思想是通过迭代过程把数据集划分为不同的类别，使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类内紧凑，类间独立。这一算法不适合处理离散型属性，但是对于连续型具有较好的聚类效果。1.2算法描述1、为中心向量c1,c2,…,ck初始化k个种子2、分组:（1）将样本分配给距离其最近的中心向量（2）由这些样本构造不相交（non-overlapping）的聚类3、确定中心:用各个聚类的中心向量作为新的中心4、重复分组和确定中心的步骤，直至算法收敛。1.3算法k-means算法输入输出初始K个聚类中心样本数据分配到最近聚类中使用每个聚类中的样本均值作为新的聚类中心聚类中心变化不变簇的数目k和包含n个对象的数据库。图1.1算法流程图输入：簇的数目k和包含n个对象的数据库。输出：k个簇，使平方误差准则最小。算法步骤：1.为每个聚类确定一个初始聚类中心，这样就有K个初始聚类中心。2.将样本集中的样本按照最小距离原则分配到最邻近聚类3.使用每个聚类中的样本均值作为新的聚类中心。4.重复步骤2.3直到聚类中心不再变化。5.结束，得到K个聚类PS1.将样本分配给距离它们最近的中心向量，并使目标函数值减小∑({})2、更新簇平均值̅∑3、计算准则函数E∑∑̅计算准则函数（2）选择评价聚类性能的准则函数k-means聚类算法使用误差平方和准则函数来评价聚类性能。给定数据集X，其中只包含描述属性，不包含类别属性。假设X包含k个聚类子集X1,X2,…XK；各个聚类子集中的样本数量分别为n1，n2,…,nk;各个聚类子集的均值代表点（也称聚类中心）分别为m1，m2,…,mk。则误差平方和准则函数公式为：∑∑（3）相似度的计算根据一个簇中对象的平均值来进行。1）将所有对象随机分配到k个非空的簇中。2）计算每个簇的平均值，并用该平均值代表相应的簇。3）根据每个对象与各个簇中心的距离，分配给最近的簇。4）然后转2），重新计算每个簇的平均值。这个过程不断重复直到满足某个准则函数才停止1.4聚类例子图1.2数据集数据对象集合S见上表，作为一个聚类分析的二维样本，要求的簇的数量k=2。(1)选择()，()为初始的簇中心，即()()(2)对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇对：()√()()()√()()显然()()，故将C2分配给对于:()√()()√()√()()因为：()()所以将分配给C2对于:()√()()()√()()√因为：()()所以讲:分配给C1更新，得到新簇{}和{}计算平方误差准则，单个方差为[()()][()()]()()总体平均方差是：（3）计算新的簇的中心。(()()⁄⁄)()(()()⁄⁄)()重复（2）和（3），得到O1分配给C1；O2分配给C2，O3分配给C2，O4分配给C2，O5分配给C1。更新，得到新簇{}和{}中心为(),()单个方差分别为[()()][()()]总体平均误差是：由上可以看出，第一次迭代后，总体平均误差值52.25~25.65，显著减小。由于在两次迭代中，簇中心不变，所以停止迭代过程，算法停止。二、K值均值聚类的Java实现以下是五个核心方法，他们分别是clusterSet（将当前元素放到最小距离中心相关的簇中），errorSquare（误差平方和准则函数），setNewCenter（生成新的簇中心），kmeans（主方法），KmeansTest（测试）。2.1元素的分簇将当前元素放到最小距离中心相关的簇中privatevoidclusterSet(){float[]distance=newfloat[k];for(inti=0;idataSetLength;i++){for(intj=0;jk;j++){distance[j]=distance(dataSet.get(i),center.get(j));//System.out.println(test2:+dataSet[+i+],center[+j+],distance=+distance[j]);}intminLocation=minDistance(distance);//System.out.println(test3:+dataSet[+i+],minLocation=+minLocation);//System.out.println();cluster.get(minLocation).add(dataSet.get(i));//核心，将当前元素放到最小距离中心相关的簇中}}2.2两点误差平方和误差平方和准则函数/***求两点误差平方的方法**@paramelement*点1*@paramcenter*点2*@return误差平方*/privatefloaterrorSquare(float[]element,float[]center){floatx=element[0]-center[0];floaty=element[1]-center[1];floaterrSquare=x*x+y*y;returnerrSquare;}/***计算误差平方和准则函数方法*/privatevoidcountRule(){floatjcF=0;for(inti=0;icluster.size();i++){for(intj=0;jcluster.get(i).size();j++){jcF+=errorSquare(cluster.get(i).get(j),center.get(i));}}jc.add(jcF);}2.3生成新的簇中心/***设置新的簇中心方法*/privatevoidsetNewCenter(){for(inti=0;ik;i++){intn=cluster.get(i).size();if(n!=0){float[]newCenter={0,0};for(intj=0;jn;j++){newCenter[0]+=cluster.get(i).get(j)[0];newCenter[1]+=cluster.get(i).get(j)[1];}//设置一个平均值newCenter[0]=newCenter[0]/n;newCenter[1]=newCenter[1]/n;center.set(i,newCenter);}}}2.4核心算法过程/***Kmeans算法核心过程方法*/privatevoidkmeans(){init();//printDataArray(dataSet,initDataSet);//printDataArray(center,initCenter);//循环分组，直到误差不变为止while(true){clusterSet();//for(inti=0;icluster.size();i++)//{//printDataArray(cluster.get(i),cluster[+i+]);//}countRule();//System.out.println(count:+jc[+m+]=+jc.get(m));//System.out.println();//误差不变了，分组完成if(m!=0){if(jc.get(m)-jc.get(m-1)==0){break;}}setNewCenter();//printDataArray(center,newCenter);m++;cluster.clear();cluster=initCluster();}//System.out.println(note:thetimesofrepeat:m=+m);//输出迭代次数}/***执行算法*/publicvoidexecute(){longstartTime=System.currentTimeMillis();System.out.println(kmeansbegins);kmeans();longendTime=System.currentTimeMillis();System.out.println(kmeansrunningtime=+(endTime-startTime)+ms);System.out.println(kmeansends);System.out.println();}}2.5、测试[java]viewplaincopypackageorg.test;importjava.util.ArrayList;importorg.algorithm.Kmeans;publicclassKmeansTest{publicstaticvoidmain(String[]args){//初始化一个Kmean对象，将k置为10Kmeansk=newKmeans(10);ArrayListfloat[]dataSet=newArrayListfloat[]();dataSet.add(newfloat[]{1,2});dataSet.add(newfloat[]{3,3});dataSet.add(newfloat[]{3,4});dataSet.add(newfloat[]{5,6});dataSet.add(newfloat[]{8,9});dataSet.add(newfloat[]{4,5});dataSet.add(newfloat[]{6,4});dataSet.add(newfloat[]{3,9});dataSet.add(newfloat[]{5,9});dataSet.add(newfloat[]{4,2});dataSet.add(newfloat[]{1,9});dataSet.add(newfloat[]{7,8});//设置原始数据集k.setDataSet(dataSet);//执行算法k.execute();//得到聚类结果ArrayListArrayListfloat[]cluster=k.getCluster();//查看结果for(inti=0;icluster.size();i++){k.printDataArray(cluster.get(i),cluster[+i+]);}}}三．学生分组应用“只要在提供恰当的材料和进行教学的同时，给每个学生提供适度的帮助和充分的时间，几乎所有的学生都能完成学习任务或达到规定的学习目标。”与此相关的是掌握学习的目标，“要求教师对应各级教学目标制定出相应的教学措施”；“应根据每个学生的实际发展水平、学习方式和个性特点来进行。”动态分层教学把集体教学、小组教学、个别辅导、同伴帮助、个人自学等多种教学形式结合起来，充分使用教学评价，保证教学始终以评定作为衡量的标准，能