KM算法（精选3篇）
KM算法 篇1
0 引言
传统的毕业设计选题方式, 通常是系院汇总课题后, 再分发到各班供学生选择, 最终课题由教师或学生决定。这种选题方式由于人的主观作用太强, 很难得到师生双方满意的结果。此外, 随着毕业生人数的增多, 这种传统的选题方式容易出现效率低、过程混乱、工作量大等问题。
综上分析提出了基于KM算法的毕业设计选题系统。系统将根据学生的志愿和教师的期望值, 智能完成学生与课题的匹配, 且使师生整体满意度最高。通过系统的智能匹配, 节省了大量的人力和时间, 大大提高了选题的效率。由于充分考虑了教师与学生的意愿, 因此也使师生双方满意度达到了最高。
1 系统分析
1.1 系统概述
系统分为3类角色:学生、教师、管理员。采用B/S模式, 主要包括以下功能模块:基本信息管理 (学生信息、教师信息、题目类别等) 、课题管理、选题管理、公告管理、数据导入导出管理、登录管理、邮件通知管理、附件管理、系统设置管理等。系统用例如图1所示。
1.2 系统功能
1.2.1 学生角色功能模块
学生登录选题系统后, 可对个人信息进行维护;可以根据课题名称、研究方向、难度等浏览课题信息, 同时如果教师有上传该课题的附件, 则学生可以下载相应的附件;选择自己感兴趣的课题时, 如个人志愿没选满或该课题没被选满, 则选择成功, 否则失败;对选择的课题进行排序, 此排序号将作为KM算法审核课题的影响因子;此外, 学生还可查看选题情况, 并可在规定的时间范围内退题, 另行选择其它课题。
1.2.2 教师角色功能模块
教师登录选题系统后, 并可对个人信息进行维护, 在规定的时间范围内发布课题, 对课题进行修改、删除和上传课题相关附件, 以及查看课题的审核情况, 查看学生的选择情况和学生信息。此外, 还可对选择课题的学生赋予期望值等。
1.2.3 管理员角色功能模块
管理员的功能包括:对学生、教师基本信息进行添加、修改、删除;可通过导入Excel文件对学生、教师信息进行批量添加, 也可把信息导出用于别处, 当系统完成匹配后, 还可把最终匹配结果导出;发布相关公告, 并对公告进行相应的维护;审核老师提交的课题, 由管理员人工审核;审核学生选择的课题, 由KM算法自动完成审核, 管理员只需启动匹配算法即可;系统初始化设置, 如设置系统对教师与学生的开放与关闭时间, 以及教师提交课题开始和截止时间, 学生选择课题开始和截止时间等;邮件通知管理, 通过系统发送邮件通知老师与学生何时提交课题与选择课题, 以及生成选题结果的同时发送邮件通知学生他们的选题结果等;查看最终课题分配结果, 如有需要, 可以把分配结果导出。
2 系统设计
2.1 系统流程
此系统主要用于学生在线完成课题的选择以及依据KM算法自动完成审核工作。从以上分析可知, 系统分为3类角色:学生、教师、管理员。首先由教师发布课题, 经审核后学生并可在线查询相关课题, 对感兴趣的课题进行选择。如果课题没被选满或个人志愿没选满, 则选择成功, 否则失败。之后, 学生对自己选择的课题进行排序, 教师对选择自己课题的学生赋予期望值。学生的志愿和教师的期望值将作为课题审核的依据。最后, 由管理员启动匹配算法, 完成课题的匹配。系统的主要活动如图2所示。
2.2 学生与课题智能匹配算法
2.2.1 基本概念
(1) 二分图。二分图是这样一个图, 它的顶点可以分为两个互不相交的集合X和Y, 所有的边关联的顶点中, 恰好一个属于X集合, 一个属于Y集合。本系统中就是将学生与课题抽象为一个带权的二分图 (如图3) , 其中学生的兴趣度值和教师的期望值即为二分图中的权值。然后通过最优匹配算法求得一个匹配使得权值和最大, 即满意度最高。
(2) 完美匹配。如果所有的点都在匹配边上, 则称这个最大匹配为完美匹配。
(3) 二分图最优匹配。又称带权最大匹配, 即每条边上都带有权值, 使得权值和最大的一个匹配。
(4) 可行顶标。L是一个关于结点的函数, L (x) 是顶点x对应的顶标值。可行顶标对于图中的每条边 (x, y) 都有L (x) +L (y) >=w (x, y)
(5) 相等子图。只包含L (x) +L (y) =w (x, y) 的边的子图。
2.2.2 KM算法
KM算法是通过给每个顶点一个标号 (顶标) 将求最大权匹配的问题转化为求完备匹配的问题。设顶点Xi的顶标为a[i], 顶点Yi的顶标为b[j]。初始时为了使a[i]+b[j]>=w (i, j) 恒成立, 令a[i]为与Xi相关联的边的最大权值, b[j]=0。如果当前的相等子图没有完备匹配, 就适当修改顶标以扩大相等子图, 直到找到完备匹配为止;当从Xi寻找交错路失败后, 得到一棵交错树, 它的所有叶子节点都是X节点, 对交错树中X顶点的顶标减少d值, Y顶点的顶标增加d值, 对于图中所有的边 (i, j) , 可以看到:
(1) i和j都不在交错树中, a[i]+b[j]的值没有变化, 原来属于 (或不属于) 相等子图, 现在仍属于 (或不属于) 相等子图。
(2) i和j都在交错树中, a[i]+b[j]的值没有变化, 边 (i, j) 仍然属于相等子图。
(3) i不在交错树中, j在交错树中, a[i]+b[j]的值扩大, 原来不属于相等子图, 现在更加不属于相等子图。
(4) i在交错树, j不在交错树中, 它的a[i]+b[j]的值有所减小。也就是说, 它原来不属于相等子图, 现在有可能进入相等子图。因而使相等子图得到了扩大。
为了使a[i]+b[j]>=w (i, j) 始终成立, 且至少有一条边加入到相等子图中, 其中d=min{a[i]+b[j]-w (i, j) }, i在交错树中, j不在交错树中。
2.2.3 KM算法在选题系统中的应用
KM算法能很好地解决在选题系统中学生与课题的匹配问题。首先令学生集合为X={X1, X2…Xm}, 题目集合为Y={Y1, Y2…Yn}, 根据学生的兴趣度值和教师的期望值求得综合兴趣度即为二分图中的权值, 其中权值为二维矩阵W[m][n]的值, 没有关联的令其权值为0。其实在实践应用中, W[m][n]中应保存学号、课题号以及排序号, 学号与课题号用于匹配结果的保存, 所以W[m][n]是一个对象数组。当将二分图转换为二维数组后并可根据KM算法流程找到一个匹配, 且使得师生整体满意度最高。对于匹配结果的处理, 由于权值为0代表的是没有关联的两个顶点的匹配, 所以把权值为0的匹配去掉, 只保存选择成功的学生的匹配。
3 系统实现
按照以上描述的设计思路及算法, 系统采用S2SH这3大主流框架以及MySQL数据库完成了系统的开发, 开发工具为Eclipse3.6。系统部分运行界面如图4-图6所示。
4 结语
目前基于B/S模式的毕业设计选题系统已很普遍, 从文献中查询到的情况来看, 这些系统的功能都大同小异。本文的一个特色就是采用最优匹配算法, 根据学生的志愿和教师的期望值, 智能完成匹配, 且使教师学生整体满意度最高, 极大提高选题效率, 真正实现课题的双向选择。该系统在桂林理工大学计算机科学与技术专业2012届学生中进行了应用, 取得了较好的效果。
摘要：针对传统的毕业设计选题方式所带来的效率低、容易出错以及管理不及时等问题, 提出了基于KM算法的毕业设计选题系统。采用KM算法, 根据学生志愿和教师期望值, 智能地完成学生与课题的最优匹配, 提高了选题效率, 解决了教师手工分配课题工作量大、难度大以及师生满意度偏低等问题。
关键词：毕业设计选题,学生志愿,教师期望值,最优匹配,KM算法
参考文献
[1]陈作滩, 何骅.基于B/S模式的毕业设计选题系统的设计与开发[J].浙江教育学院学报, 2010 (24) .
[2]刘晶峰.基于Web的毕业设计选题系统的设计与实现[J].电脑编程技巧与维护, 2009 (20) .
[3]刘跃, 邓维斌, 黄蜀江.毕业设计选题系统的构建与实现[J].实验室研究与探索, 2011 (30) .
[4]孙惠泉.图论及其应用[M].北京:科学出版社, 2004.
KM算法 篇2
关键词：聚类算法,粒子群优化算法,k均值算法,云平台
0 引言
如今的时代被称为大数据时代[1,2],如何高效地从海量数据中提取所需信息已成为主流问题。数据挖掘是常用的在大量数据中提取隐藏的有用数据的方式,但如今的数据量急剧猛增,效率与存储量成为数据挖掘系统的瓶颈。例如,k - means算法[3]是数据挖掘算法中一种常用的划分方法,它具有简单方便易实现的特点。它主要通过不断迭代更新各聚类中心值,直到最优解为止。但k - means算法存在以下缺点: 第一,容易受初始聚类中心影响,结果会随着初始聚类中心浮动[4,5]; 第二,串行处理,迭代计算多,时间开销大。为此,很多研究人员提出了解决方案,例如其中通过粒子群算法优化初始聚类中心的算法[6]、通过数据密度参数选择初始聚类中心的方法[7],通过Hadoop平台并行处理k - means的方法[8]等,这些算法都在一定程度上克服了一些k - means算法的缺点。其中通过粒子群算法查找k - means算法初始中心的算法表现出良好的效果, 但此算法在面对海量数据时,其计算量较大,需要耗费较多的时间,效率较低。
现如今云平台[9]日益壮大,它作为一种新型计算模型具有强大的计算能力,其中作为新兴商业计算模型的云平台的Hadoop逐步成长,作为Apache基金会开发的一个开源分布式计算平台,它不仅架构和使用非常方便,而且还可以开发运行处理海量数据的应用程序。因此,本文提出运用Hadoop的并行方式,全程并行处理PSO - KM算法,不仅可以解决k - means对初始聚类中心敏感的问题,还可以稳定处理海量数据在准确率和效率都有很大的提升。
1 基于 PSO 的 k - means 算法
PSO - KM算法是先运用PSO算法[10]的搜索能力,通过粒子之间的相互合作和比较寻找数据集中的最优解即搜索出k个最优初始聚类中心,而后通过这些最优聚类中心再进行k - means算法操作的模型。这种算法模型在一定 程度上克 服了k means本身的对初始聚类中心敏感的缺点。
如图1所示,随机给定粒子的初始位置xi和初始速度vi并根据公式( 1) 计算适应度f( xi) ; 初始化粒子群,继续构建出m个粒子的粒子群。比较各个粒子的当前适应度和粒子最优适应度f( pb) ,并根据比较结果判断是否更新粒子最优适应度和粒子最优位置; 比较粒子最优适应度值f( pb) 和粒子群最优适应度值f( gb) ,根据比较结果判断是否更新粒子群最优适应度和粒子群最优位置; 继而根据公式 ( 2) 更新粒子的速度vi,根据公式( 3) 更新粒子位置xi; 判断是否达到收敛条件,若没达到继续迭代操作,若达到则输出结果; 将输出结果作为初始聚类中心,进行k - means运算。根据公式( 4) 计算每个数据对象到聚类中心的距离d并对其归类; 结束归类后更新聚类中心,判断是否达到收敛条件,若未达到继续迭代操作,达到则终止算法输出最终结果。
基于PSO的k - means聚类算法运用PSO算法的全局搜索的 特点优势,利用PSO算法搜索 出k - means算法所需的初始聚类中心,从而杜绝k means算法本身对初始聚类中心随机性的选择,减少最终划分结果的不稳定性因素。
2 Hadoop
Hadoop是一种可以允许用户构架编程模型和使用的分布式计算大量数据集的平台[11]。Hadoop的两大核心是HDFS和MapReduce。HDFS[12]是分布式文件系统,采用主从结构,使用低廉的硬件设备,具有容错性高、传输率高的特点、可用来创建目录,打开、删除、重命名文件等。MapReduce是一种处理大规模 数据的并 行分布式 计算框架,是由Google率先提出的[13],可以将任务分配到由上千台商用机,Map阶段和Reduce阶段,分别由map和reduce函数控制。map和reduce函数都可由用户编写,接收形如 < key,value > 的键/值对。MapReduce的工作流程如图1所示。首先,进行输入初始化,将输入数据partition( 切分) 为若干split分片,解析出 < k,v > 键值对。其器组成的集群上。MapReduce大致可以分为两个阶段次,进入Map阶段,map函数接收 < k,v > 键值对作为输入进入进行相关操作,输出一系列 < kk,vv > 键值对,然后输出结果经过shuffle ( 洗牌) 的过程,将结果进行划分 ( partiton) 、排序 ( sort) 、分割( spill) 并储存在本地磁盘上。再次,进入Reduce阶段,将 < kk,vv > 按照设定的排序方法,聚集相同kk值数据,然后将处理后的 < kk,list( vv) > 作为reduce函数的输入数据处理。最后,reduce函数结果 < kkk,vvv > 并存入HDFS的指定目录中。
由此可见,Hadoop[14]是一个能够让用户轻松架构和使用的分布式计算平台。用户可以轻松地在Hadoop上开发和运行处理海量数据的应用程序。
3 基于 Hadoop 的 PSO - KM 算法
MapReduce并行处理问题,适合处理可被分成独立子问题处理并且具有有限通信的问题。在PSO算法中[15],每个粒子的每一次迭代过程是相互独立的; 任务粒度较大,每个粒子不断迭代相同任务; 有限的通信需求,仅需在对种群最优信息的更新时通信。同样在k - means算法中,每个数据对象分类都是独立的; 迭代进行数据对象的分类计算; 通信有限,在更新聚类中心时通信。有的相关人员提出了并行基于MapReduce的K - PSO算法[16],它采用串行的PSO算法处理数据得到初始聚类中心,然后再进行并行的k - means算法的方式。本文针对PSO算法也可在Hadoop平台上并行运行的事实[17],将PSO - KM全部并行运行。因此PSO和k - means都可以使用MapReduce模型进行处理。
在PSO - MapReduce的map阶段,粒子被更新、移动和评估,最后判断更新单个粒子最优解,若粒子有更新则更新粒子群最优解。在reduce阶段,在接收了所有相关更新后的粒子,合并粒子信息,更新粒子群的最优解,如图2所示。
3. 1 并行 PSO 算法
处理PSO算法操作时,先进行初始化操作,构建初始粒子群。然后一个粒子作为一个map,它接收新位置、速度、价值和单个粒子最优适应度。最终粒子的id作为key,更新后的粒子属性字符串作为value输出。map函数如下:
PSO - reduce函数,接收key和list( value) 。这个key是特定粒子的id,这个value列表包含最新更新的粒子的属性信息。reduce函数的作用是合并信息,全局更新粒子群最优位置和粒子群最优适应度, 最终输出粒 子群最优 粒子。PSO - reduce函数如下:
3. 2 并行处理 k - means
当PSO - MapReduce中迭代完成后,会输出经过PSO算法优化后的初始聚类中心点。把这些初始聚类中心输入到下一个k - means算法的MapReduce中。然后在map阶段计算数据集中数据对象分别到中心点的距离,并根据距离将数据对象归类, 输出的key是类别号,value是数据对象相关信息。combine函数[18]将这些输出先做个整合,将类别号相同的合并到一起,combine增加map函数输出数据的紧凑性,减少写入磁盘文件的数据量,从而提高处理数据的效率,非常适合用于需要大量加法的操作。combine函数将整合信息输出传递给reduce函数,reduce主要进行更新聚类中心点的操作。当迭代结束输出最终分类结果,系统操作结束。
4 实验和结果分析
4. 1 实验环境
实验中Hadoop云平台的搭建是由六台PC机组成的,其中1台PC机是master作为Name Node和Job Tracker,其余的PC机是slave作为Data Node和Task Tracker。具体配置: mater的PC机是四核2. 9GHz,8G内存; 其余节点有三台PC机是双核2. 7GHz,4G内存; 另外两台是双核2. 4GHz,2G内存。每台PC系统配置均为centos 6. 3版本; hadoop 1. 1. 2; jdk1. 7. 025。具体分布如图3所示。
4. 2 准确性效率实验
首先测试改进后算法的稳定性和准确性能。采用人工数据作为实验数据,设定数据集维度为5。将数据集分成4组,分别是D1,D2,D3。其中D1包含500个数据; D2包含了3000个数据; 而D3包含10000个数据,D4为200000数据,数据类别设为7。在PSO - KM算法中设定粒子数为40,最大迭代次数设为50次。结果如表1所示。
实验结果显示,串行的k - means准确率最低, 由于它的初始聚类中心是随机选取,因此受到初始聚类中心的影响比较明显。而串行的PSO - KM算法有以其本身的全局搜索能力,有效的改善了k means算法缺陷。而并行PSO - KM算法的准确率更高,可见并行计算可以提高PSO算法的全局搜索能力,而且随着数据量的增长,并行PSO - KM所表现出的优越性就越明显。
4. 3 集群性能实验
本实验目的是测试PSO - KM并行算法的并行计算效率,测试随着节点数的增加,系统处理同一组数据的能力变化并且测试节点数和数据量同时增加的情况下系统的处理能力[19]。本实验采用了四组3维人工数据,如表2所示,设定生成5个类别。为了表现系统性能,实验数据进行加速比和运行效率的测试。加速比是单节点运行时间和增加节点运行时间的比值,而运行效率则是加速比和节点数的比值。每个节点处理5个map /reduce任务,每次逐个增加节点。
如图4所示,处理较小数据集A、B时,随着节点的增加加速比增长较快,而处理数据量较大的C和D时,加速比和节点处成比例增长,增长速度趋于稳定。这样,系统表现出良好的稳定性和扩展性。图5反映了算法的并行效率,随着数据量的增多和节点数量的增多,并行效率会减小。由于集群中,节点数目增长, 节点之间的通信时间会增多,所以数据量和节点数同时增长时,系统运行操作的时间加大。但系统效率在一定数据量后,表现出来稳定性说明系统算法具有较高的并行效率。综合来说,并行PSO - KM算法在扩展性和稳定性上都有了不错的提升。
5 结束语
KM算法 篇3
浙江如今拥有7条干线铁路:上海到昆明、沪杭客专、安徽宣城到杭州、萧山到宁波、金华到温州、江苏新沂到长兴等, 还有金华到千岛湖、衢州到常山2条地方铁路及支线铁路。1 774km铁路中, 有65.6%是拥有2条铁轨的复线铁路, 60.6%是电力机车牵引的电气化铁路。每1万km2的浙江土地上有174km铁路, 铁路网密度高于全国平均水平。因浙江人口密度大, 平均算下来, 每个浙江人仅拥有3.3cm铁路, 不到一根香烟的长度, 也只有全国人均长度的50%。
一份规划昭示着未来8年浙江的铁路建设速度将前所未有, 依照省发展和改革委员会、省住房和城乡建设厅不久前联合印发的《浙江省铁路网规划 (2011-2030) 》, 到2020年, 浙江将拥有近6000km铁路, 意味着短短8年间, 浙江将新建4 200km铁路线, 这个数字是过往106年铁路建设总长的2倍多。
(摘自中国建材信息总网)