改进K-means算法在职高试卷成绩分析中的应用

摘要:考试成绩是一所学校评估教学质量的重要依据之一。这些成绩中隐含着该校学生的学习能力和教师的教学水平,合理分析这些成绩对提高学校教学质量有很大的推动作用。文中改进了K-means聚类算法,并将此算法应用于职高学生试卷成绩分析中,首先对数据进行了预处理,然后使用改进K-means算法对学生试卷成绩进行了分析,并用所获得的结果指导学生的学习和今后的教学工作。

关键词:数据挖掘;聚类分析;K-means算法;成绩分析;教学质量

中图分类号:TP311文献标识码:A文章编号:1009-3044(2010)18-5048-02

The Application of Improved K-means Algorithm in Vocational School Result Analysis

WANG Zhi

(Datong Second Vocational School, Datong 037008, China)

Abstract: Examination result was one of the important bases for evaluating the teaching quality. These results implied the ability of school students and teachers teaching, so, reasonable analyzing of these results could be the key to improve the quality of school education. The k-means clustering algorithm was improved in this paper, which was applied to examination result analyzing of vocational school, firstly, data were preprocessed, and then results were analyzed using the improved k-means algorithm, finally, and the future studying and teaching would be guided by these analyzing results.

Key words: data mining; cluster analysis; k-means algorithm; result analysis; teaching quality

随着信息技术的飞速发展,围绕着人类各种日常活动和经济活动的数据,以多种形式被存储在数据库中。传统的数据分析方法是统计分析法,该方法只是对事实的验证,描述已经发生的事实,难以发现数据中存在的关系和规律,也难以根据现有的数据预测未来的发展趋势。面对这一挑战,产生了数据挖掘(Data Mining, DM)[1]和知识发现(Knowledge Discovery in Database, KDD)技术[2],并在不断地探索中逐渐显示出其强大的功能。数据挖掘可以从大量有关数据中挖掘出隐含的、先前未知的、对企业决策有潜在价值的知识和规则。作为数据挖掘技术中的一种重要方法,K-means聚类分析算法应用非常广泛。

考试成绩是一所学校评估教学质量的重要依据之一,也是评估学生是否掌握好所学知识的重要方式[3]。聚类技术可以深层次的进行试卷成绩分析,它可以全面的分析考试结果与各种因素之间隐藏的内在联系,从而得出一些有益的决策。

本文对大同市第二高级职业中学计算机专业班级的5门课程进行了基于改进后K-means聚类算法的成绩分析,并得出了有用的信息。

1 聚类分析

1.1 聚类分析

聚类分析可以应用到多个领域,包括数据挖掘、统计学、生物学,以及机器学习等。聚类(clustering)是根据数据对象的属性值计算相异度并将其分组成为多个类或簇(cluster),同一个簇中的对象相似度较高,不同簇间的对象差别较大。聚类算法包括如下几类:划分方法(partitioning method)、层次方法(hierarchical method)、基于密度的方法(density-based method)、基于网格的方法(grid-based method)及基于模型的方法(model based method)等。

1.2 K-means算法

1.2.1 传统的K-means聚类算法

传统K-means算法[4]把n个样本点分为k个簇,各簇内的样本点具有较高的相似度,而各簇间的样本点相似度较低,相似度的计算是依据一个簇中样本点的平均值来进行的。算法的处理过程如下:

step 1. 在样本数据集D中选择k个样本点,将k个样本点值分别赋给初始聚类中心ai(i=1,2,…,k);

step 2. 对数据集D中的所有样本点bj(j=1,2,…,n),依次计算到各簇中心ai的距离:;

step 3. 找出bj关于ai的最小距离min(d(i,j)),将bj归并到和ai距离最小的簇中;

step 4. 重新计算各簇的聚类中心;

step 5. 按式计算数据集D中的所有点的标准差E(t),并与前一次误差E(t-1)比较;

step 6. 若E(t)

1.2.2 改进的K-means聚类算法

为提高聚类结果的稳定性[5],改进选取初始聚类中心的方法,具体步骤为:对原始数据进行l次取样,l的大小依据实际数据集的大小人为决定。取样要求每次取D/ l 个数据,满足l 次取样后,集中的所有数据都被取到,并且没有被重复使用。然后对每一次取样数据用原始的K-means法进行聚类产生k个类。如果聚类结果中有的类为空,即没有数据点被这个类的聚类中心吸引过来,就重新选取k个初始聚类中心再进行聚类,直到没有类为空。每次取样出来的数据会输出k(c1,c2,…,ck)个聚类中心,共输出l×k个聚类中心。最后再对这l×k个聚类中心采取距离比较方法选取初始聚类中心,输出最优的一组聚类中心值。

改进后的K-means算法描述如下:

输入:n个对象的数据集D,数据分类数目k,取样次数l;

输出:k个簇,满足标准差函数值最小。

具体步骤:

step 1. 根据上述描述获取k个初始数据中心{C1,C2,…,Ck};

step 2. 将k个样本点值分别赋给初始聚类中心ai= Ci(i=1,2,…,k);

step 3. 对数据集D中的所有样本点bj(j=1,2,…,n),依次计算到各簇中心ai的距离 ;

step 4. 找出bj关于ai的最小距离min(d(i,j)),将bj归并到和ai距离最小的簇中;

step 5. 重新计算各簇的聚类中心;

step 6. 按式计算数据集D中的所有点的标准差E(t),并与前一次误差E(t-1)比较;

step 7. 若E(t)< E(tC1)转step 3 ,否则算法结束。

2 实验分析

2.1 数据预处理

1)数据集成:成绩数据库中包括了学生的平时作业成绩及课程的考试成绩。实验中抽取了大同市第二职业中学计算机专业一个年级学生的一学期的课程(网络操作系统、计算机网络、网页制作、计算机基础、计算机组装与维修)的成绩(186),如表1所示。

stuid为学生学号,c1为网络操作系统的成绩,c2为计算机网络的成绩,c3为网页制作的成绩,c4为计算机基础实验的成绩,c5为计算机组装与维修的成绩。

2)数据清理:数据清理的主要工作就是填补遗漏的数据值。本实验中,采用忽略元祖的方法删除退学、休学、转学、没有参加考试的学生的记录。对于其它个别重要空缺,如果空缺值较少,采用人工填充的方法处理,填充原则是使用该记录其他同类属性的平均值填充此空缺值。经过上述清理后,总记录条数剩下156条。

3)数据转换:数据转换就是量化的过程。对于成绩分析,我们需要将成绩全部转换成数值。本实验数据中,只有c5(计算机组装与维修的成绩)是等级分,需要转换一下,“优”为90,“良”为80,“中”为70,“及”为60,“差”为0。

最小-最大规范化对原始数据进行线性变换。假定minA和maxA分别为属性A的最小值和最大值。最小-最大规范化通过计算:

将A的值v映射到区间[new_minA, new_maxA]中的v'。表1中经最小-最大规范化将数据映射到[0,1]上,如表2所示。

2.2 实验结果

将表2中的成绩进行聚类分析,规定聚类为3类,最后各类均值如表3。

实验结果中,簇1中包含82条记录,占总数的52%;簇2中包含64条记录,占总数的41%;簇3中包含10条记录,占总数的6.4%。也就是说,约有52%的学生考试成绩较好,约有41%的学生考试成绩中等,约有6.4%的学生考试成绩较差。

簇1均值中的c1、c2、c3、c5的值在3个簇的均值中都是最高的,但c4的值却是3个簇的均值中最低的。这说明簇1中的学生除计算机基础实验外的其他课程成绩都较好,但计算机基础实验成绩较差。在今后教学中,应注意学生在计算机基础的实际动手能力。

3 结束语

本文针对职高教学过程中的成绩做了聚类分析,从分析结果中我们得到了一些对教学有用的信息,基本达到了挖掘的效果。但在实验过程中发现,有关采集数据的清理有很大的弊端,可能由于人工补充缺值而误导教学工作,所以,在以后的研究过程中要着手解决这个问题,另外,聚类算法也有待优化。

参考文献:

[1] Kantardzic M.数据挖掘――概念、模型、方法和算法[M].北京: 清华大学出版社,2003.

[2] Han J, Kamber M,范明,孟小峰.译.数据挖掘概念与技术[M].北京: 机械工业出版社,2007.

[3] 马希荣,孙华志.数据挖掘技术在教学评价中的应用[J].计算机工程与应用,2003,(19):51-54.

[4] 翟音,罗萍.基于K-means算法的产品市场定位聚类分析[J].电脑开发与技术,2008,3(8):1635-1636.

[5] 刘少辉.一种基于Rough集的层次聚类算法[J].计算机研究与发展,2004,41(4):552-557.