在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
资源下载#本文PDF版下载 #本文代码下载
前言最近由于上C # 课的时候,老师提到了-我们的课程成绩由几个部分组成.分别是「最终作品展示」「小组合作聊天记录评分」「组内成员匿名互评」「报告书评分」这四项综合评价.老师希望我能够通过这四个项目对所有同学进行聚类,然后根据离每簇的中心距离来评价最终的分数.由于我没有接触过这方面的算法,所以就选了实现较为方便并且直观的聚类方法K-MEANS.所以下文中就会对我这次学习到的一些心得进行分享.由于是C # 课程,所以本次的算法将以C# 为例子进行介绍.
聚类百科上对于聚类的解释是这样的: 聚类和分类的区别分类:从特定的数据中根据人为打上的数据表浅进行数据挖掘,做出判断.是将类别已知.并且样本数据已经做了标记的数据进行归类.是一个有监督的过程. K-Means算法K-Means算法是基于距离(我在这次中使用了欧几里德距离)的聚类算法 , 采用距离或者特征向量作为相似程度的考量,数据之间的距离/向量余弦越接近, 其相似度就越大.在K-Means聚类算法中-簇是由距离较为相近的数据对象构成的,故用K-Means算法的目的是想要得到数据对象相对紧凑且独立的不同簇.
「评分系统」和K-Means的结合这次老师让我做的就是希望我能通过给出的「最终作品展示」「小组合作聊天记录评分」「组内成员匿名互评」「报告书评分」这四个维度的数据对所有同学的成绩使用K-Means聚成四个类,分别对应90-100/80-90/70-80/60-70/不及格这五个等第.分出登第后,五个类的中心分别是95/85/75/65/55,根据离数据中心的欧几里得距离按比例来决定最终的成绩.这就是老师让我实现的功能. K-Means的非适用性K-Means算法适应于连续形式的数据,由于数据的分布不同,有时候就无法分得准确的类,比如下面的两种形式
1.非标准正态分布 K-Means用于表示聚类趋势只是说在数据符合正态分布或偏态不太严重时才是合理的.如果偏态严重,或者有异常的极大极小值,对均数影响很大,这时K-MEANS不能代表聚类的趋势.
2.非均匀分布
由于分布的不均匀,疏密程度就会对中心的选取造成影响.就会偏向左侧较密的地方.如下所示:
K-Means的优点和缺点优点:1. 算法简单并且效率很高,迭代次数. 缺点:1. 需要指定K的值 我们在每次聚类之前需要指定数据会被分成几类即要有几个中心点. K-Means的一些细节欧几里德距离欧几里德距离简称欧式距离,是我们平时经常用到的一个距离度量公式,具体就是基础求距离公式,并且拓展至了n维空间.我们以三维空间举一个例子,如下图所示.A,B点根据欧几里得距离公式算出来的就是中间灰色线上方的距离公式
“质心”公式计算“质心”的选取是因为每一次聚类后都需要通过簇中的数据对象生成新的中心,而生成新中心的方式就是产生所有数据对象的”质心”.公式也可以拓展至n维,这里我们以3维的空间为例子 A/B/C三个点的”质心”就是图中的灰点,坐标为((X1+X2+X3)/3),(Y1+Y2+Y3)/3,(Z1+Z2+Z3)/3)拓展到n维就是((X1+…+Xn)/n,…,((Z1+…Zn)/n)). K-Means算法实现步骤这里我们介绍的是K-Means算法的本身步骤,没有加上任何的优化方式,总共分为 5 步,分别如下: 接下来我们通过举例子的方法来更好的理解一下K-Means算法,我们随机生成了七个点,它们的位置即坐标如下图所示
很明显,我们如果有监督的将他们分类,那么结果一定是如下图所示的情况
那么我们按照K-Means算法的步骤,看一下聚类的过程是怎么样的. 2.计算么个数据对象距离各个簇中心的距离
3.重新计算每个簇的中心 K-Means在C#下算法的实现(在这里我展示的是没有优化过的K-Means实现) 1.首先是初始化中心.根据我们设定的簇的数量,我们可以随机从所有的数据对象中选择k个点作为初始的中心点.这里只需要使用Random类的Next方法即可,所以此步骤不进行介绍. 2.聚类步骤的实现代码特点解释: 我们先来看一下聚类这个方法中的运行步骤,如下所示:
解释: 下面就是聚类方法中的代码: private void Cluster() { int tmpclass = 0; double tmpClusDis = 0, tmpClusMinDis = 0; //清除每一个簇里原来的项 for (int i = 0; i < ClassNum; i++) { ClusterAssem[i].Clear(); } //进行欧几里德距离计算并聚类 for (int i = 0; i < RowCount - 1; i++) { tmpClusMinDis = vurMax; for (int j = 0; j < ClassNum; j++) { tmpClusDis = 0; //这里是取出每个维度的数据进行加和 for (int k = 3; k < 7; k++) { tmpClusDis += Math.Pow((System.Convert.ToDouble(XlsDataSh.Items[i].SubItems[k].Text) - CenterArrayParams[j, k - 3]), 2); } if (tmpClusDis < tmpClusMinDis) { tmpclass = j; tmpClusMinDis = tmpClusDis; } } ClusterAssem[tmpclass].Add(i); } //重新初始化 if (ClusterAssem[0].Count == 0 || ClusterAssem[1].Count == 0 || ClusterAssem[2].Count == 0 || ClusterAssem[3].Count == 0 || ClusterAssem[4].Count == 0) { InitCenter();//重新初始化中心的方法. Cluster(); } } 3.重新生成每个簇的中心解释: private void RenewCenter() { double tmpSameDis = 0; for (int i = 0; i < ClassNum; i++) { for (int k = 3; k < 7; k++) { tmpSameDis = 0; //遍历每个簇的点,求出中心点 foreach (object n in ClusterAssem[i]) { tmpSameDis += System.Convert.ToDouble(XlsDataSh.Items[System.Convert.ToInt16(n)].SubItems[k].Text); } RenewCenterArrayParams[i, k - 3] = (tmpSameDis * 1.0 / (ClusterAssem[i].Count+1)); } } } 4.计算结束的标记结束标志的意图就是当中心不再发生变化或小于一个阈值的时候就停止算法的进行了. private Boolean CalEndFlag() { double tmpDifferDis = 0, tmpSameDis = 0; for (int i = 0; i < ClassNum; i++) { tmpSameDis = 0; for (int j = 0; j < 4; j++) { tmpSameDis += Math.Pow((RenewCenterArrayParams[i, j] - CenterArrayParams[i, j]),2); } tmpDifferDis += Math.Pow(tmpSameDis,1.0/2); } //判断中心点和前一次的偏移 if ((BalEndFlag - tmpDifferDis) <= EndFlag) return false; else { //算法没有结束,所以将新的中心赋给用于计算的ArrayList for (int i = 0; i < ClassNum; i++) { for (int j = 0; j < 4; j++) { CenterArrayParams[i, j] = RenewCenterArrayParams[i, j]; } } BalEndFlag = tmpDifferDis; tmpDifferDis = 0; return true; } } 结果展示下面就是我做的基于K—Means的自动聚类评分系统的界面.首先我们先看看有监督下的聚类是否符合预期,如下图所示:
我们通过上图的红色框中可以看出这个聚类的结果和我们的预期是十分的符合的.下面就是我通过随机的生成方法生成的数据,来观察K-Means算法在无监督下的运行结果.如下图所示:
以上就是本次探究的最终成果展示. K—Means的收敛性K-Means算法一定是收敛的,否则就会陷入一直寻找新的”质心”而没有最终的结果了.具体的证明步骤较为复杂.通过参考一些文章(会在下文中参考中标出)涉及到了E-M算法.将一个聚类问题转化为一个最大似然估计问题可证明K-Means是E-M算法的一个特例.在E-M算法下,求得的参数一定是收敛的.在K-Means算法中目标是使损失函数最小,所以在E-step时,找到一个最逼近目标的函数,在M-step时,固定这个函数(数据对象的分配),更新均值(簇的中心),所以最后一定会收敛了. 基础K-Means算法的优化由于K-Means是非常成熟的算法,所以有很多先辈们改良了这个算法,在这里仅仅只是介绍在各个方面有哪些能够参考改进的方法. 参考1.「K-Means算法的收敛性和如何快速收敛超大的KMeans? - 大数据躺过的坑 - 博客园」(传送门)(http://www.cnblogs.com/zlslch/p/6965209.html?utm_source=itdadao&utm_medium=referral) |
请发表评论