基于C#最近邻算法的教学系统分析与设计

周　靖

(广东石油化工学院　计算机与电子信息学院，广东　茂名　525000)



基于C#最近邻算法的教学系统分析与设计

周靖

(广东石油化工学院计算机与电子信息学院，广东茂名525000)

K-近邻分类(KNN)是著名的模式识别统计学方法之一，被广泛应用于文本分类、图像处理等领域。因其实现思想的简单性及基于实例的分类方法，可作为人工智能课程的入门案例算法。由于KNN分类识别过程中懒散的学习方式，在理论与实践教学上存在着一定的难度。通过对KNN算法的研究和软件教学系统的分析与设计，实现了基于Visual C#的KNN各种演示方法和辅助教学系统；改进了教学手段，提高了教学质量。

K-近邻分类算法；理论教学；实验教学；分析与设计

1　研究背景

K-近邻分类算法是人工智能模式识别方法之一[1-2]。其算法思想为:给定一个待分类样本，系统在训练集中查找最相似的K个近邻样本，并根据这些近邻样本的类别决策属性个数给该样本的候选决策属性评分。由于它与人的思维方式相似，较容易使用和理解，因而成了许多高校信息类学科本科高年级人工智能课程教学的入门案例算法。但在实际的教学过程中，围绕算法对K值参数依赖较大的惰性算法，一直以讲授知识表示和搜索推理技术为主导，缺乏完备的、形象的教学系统，学生在学习的过程中大都采用死记硬背其方法及步骤，加之目前研究模式识别的主要工具是Matlab，实践手段较为单一、抽象，针对这些情况，设计开发了KNN教学系统。C#是一种面向对象的编程语言，衍生于C和C++，凭借其简单、功能强大、类型安全，以及面向对象等优势可实现应用程序的快速开发[3]。因此，结合C#构建一个形象、内容新颖、实用性和对比性强的教学与实验系统，使学生可以在该系统上观察、学习、实现并验证所学习的理论算法，探索和研究新的改进方法。该系统便于因材施教，为学生提供了深入钻研和发挥创新性思想空间。

2　系统分析与设计

2.1系统需求分析

由于系统的主要目标是为教学提供演示及实践的一体化操作平台，故在系统的设计阶段着重考虑平台操作的适用性和针对性。系统用户包括有教师和学生。在其需求上，针对教师，系统需具备层次结构清晰、对比性强、重点突出并能反复操作的演示功能；针对学生，系统要提供基本的、可拓展的实验操作环境，同时配备操作细节详细的帮助信息。系统用例图如图1所示。

2.2系统设计

系统主体功能分为KNN背景介绍、KNN思想演示、实验操作3大功能模块。其中涉及理论教学演示的KNN背景介绍及思想演示模块均配备了单步、分步、断点、反复、连贯运行算法步骤的教学功能。

图1　系统用例图

2.2.1KNN背景介绍

该部分主要功能包括KNN算法起源、发展及应用领域的展示。本科高年级学生对算法应用领域、效果颇为感兴趣，这样的演示性教学能够增强模式识别技术进化历程的直观印象，树立研究目标，理清研究方向。

2.2.2KNN算法思想介绍

整个算法思想演示模块的结构如图2所示，以下详细说明图中各功能模块的设计思路。

图2　KNN算法演示系统模块结构图

1)选择UCI数据集，系统以文本形式引入UCI数据集，并将ListView列表视图控件作为UCI数据集的选择操作窗口。在触发ListView的SelectedIndexChanged事件后，UCI数据集界面对应显示已选择数据集的条件和决策属性、样本数量等详细信息。全局上可通过系统的下拉菜单切换到其他功能界面。

2)相似性距离测度的计算功能，采用面向对象类与对象的概念[4]进行设计。

①类SP为计算待测样本与训练集样本的条件属性值相同的个数[5]。

②类ED为欧式距离测度方法[6]，具体计算公式为:

(1)

式中：tik，tjk分别表示条件属性r下训练集样本xi和待分样本xj的特征参数。

③类Entropy为基于信息熵的距离计算方法，包含3个步骤。首先统计待分样本各条件属性下特征参数在数据集中出现的次数及归属各个决策属性的实例个数。其次依据熵的计算表达式:

(2)

得到特征参数ti对分类的相关性Corr(ti)的定义，其中p(ti)是ti分布概率，p(tir)是ti特征参数决策属性为r的概率值，然后归纳待分样本各条件属性下特征参数与训练集中样本的绝对差异值。最后累加平均差异值，即是样本间的距离值。

上述3种算法中涉及的数据集相关信息定义为类中的数据成员，具体计算步骤定义为类中的方法，供主程序引用，达到提高代码重用及简化程序的作用。3个类分别声明于3个独立的窗体，运行演示顺序上可以交替转换，在界面上以Button按钮的Click事件控制每一次都只运行3个类中其中的一个独立方法函数，同时将计算过程中所有样本间的距离值存储在对象的数组数据类型成员中，并将数组元素值作为函数参数传递到K值设置界面。限于篇幅，以下给出Entropy类定义。

Public partial class Entropy:Form{

public Entropy( ) {InitializeComponent( );} //构造函数

longm;//数据成员，样本集中样本个数

intn;//数据成员，n个不同的类别

int [] ds=new int [MAX];//存储样本间各条件属性下特征参数的差异值

……

private void Statistic( ) {

for(inti=1;n;i++)

for(intj=1;v;j++)

if Corr(tj) 不存在

检索TRn*v，统计特征集{|tj|}和{|trj|}，计算Corr(tj)并存储e(tj)值；//r=1，2，…，n，

存储新矩阵TR'm×q；//X=[x1，x2，…，xm]T，Y=[Corr(t1)，Corr(t2)，…，Corr(tv)]T；}

//类的方法，对样本参数进行相关性值计算预处理

Private void Difference( ){

for(i=1;m;i++)

for(j=m;n;j++)

for(f=1;v;f++)

iftif=tjf置D_Corr=0；

else iftif=tjf且e(tifr)=0，e(tjfr)=0 置D_Corr=0；//r，w=1，2，…，Q

else iftif=tjf且e(tifr)=0，e(tjfw)=0 置D_Corr=1

elseD_Corr=|Corr(tif)-Corr(tjf)|；

存储D_Corr值；}

//类的方法，计算或判断Tt与Te样本各特征间的相关性差异值D_Dorr(ti，tj)，得到特征间的距离

Private void Calculate( ){

for(i=1;m;i++)

for(j=m;n;j++)

for(f=1;v;f++)D_Corr(tif，tjf)累加求平均值得到样本间的距离测度；}

//类的方法，计算Tt与Te样本的距离。}

3)K参数的设置，教学系统不同于算法的仿真系统，不需要突出最优化参数的识别结果，而是对教学演示过程中的“比较性”有明确的要求。鉴于此，该系统中每个K值参数变化后，至少保存上一个K值参数识别结果，全局上可通过TabControl选项卡控件控制每个参数识别结果显示的切换，并显示K个近邻样本的相关信息。

由于KNN算法的分类计算发生在训练过程中，因此分类器的生成是连接模块，涉及相似性距离计算、K值设定及UCI数据集选择各功能模块的参数调用，综合以上KNN算法思想介绍系统顺序图如图3所示。

图3　KNN算法思想介绍系统顺序图

2.2.3演示过程中的教学功能

以上功能中均以MenuStrip主菜单和ComboBox上下文菜单控件实现算法单步和分步运行演示、断点处运行演示、连贯运行演示、反复演示及返回上层教学演示界面。单步运行演示首先通过ListView控件显示可供单步运行演示的若干算法步骤；然后以ListView控件的SelectedIndexChanged事件触发控制，鼠标每选择一个步骤，就运行一个类中的计算方法。连贯和分步运行演示形式类似与单步运行，只是用Timer控件控制每步之间的停顿时间，并记录跳跃或返回前任一步骤的运行信息。遵循ListView控件中的item项的索引顺序，可实现返回功能、指定反复运行的功能。断点出运行演示，即是算法运行停顿到断点处，其思路是通过namespace中定义的方法，将算法运行到断点处的相关计算信息、运行存储到相关的数据类型中，Break跳出类中的计算方法。上述功能基本思路如图4所示。

图4　教学功能基本思路设计图

2.2.4实验操作

在这部分系统中，针对学生的实践课程要求设计了基础实验操作、拓展实验操作、帮助3个功能模块。其中，对于基础实验操作实验内容的设置，主要以教学演示过程中涉及的3种距离测度机制为基础，让学生对SP、ED及Entropy 3个类的计算发放进行程序填空，运行后即可验证分类识别效果是否与教学过程中的演示结果一致；拓展实验操作则要求学生在基础实验操作的铺垫下，充分发挥自身的想象力、创造力，改进算法，进行完整的程序编写，运行后对比并分析若干类方法的分类识别结果；帮助模块用于让学生了解、熟悉实验目的、内容、步骤及实验环境。

本文着重研究基础实验与拓展实验操作。这两个模块是为了模拟KNN算法C#编程的现实实验环境，无需重新启动VS进入真实的程序编写环境。在Form窗体里，首先，设置Label标签控件提示可供改进的KNN算法点，学生通过在通过TextBox控件补充、添加新代码进行程序填空或重新编程；其次，在同一Form窗体中布置一个Button控件作为编译触发器，通过其Click事件调用CSharp namespace中的Codeprovide类直接编译由TextBox控件逐一输入、组合的字符串代码集合，并把编译是否成功以布尔类型True或False来判断MessageBox.show()的提示字符；最后若编译正确，启动另一Form窗体，以显示程序运行结果，否则返回上层编辑Form窗体修改。另外，在编写程序Form窗口还配备另一Label标签控件，始终显示实验内容、目的及步骤。

3　系统的实现

本系统采用传统各条件属性下相同特征参数统计、欧式计算、Entropy相关性3种不同的距离机制演示KNN算法，设置K值参数为5～35。在教学演示部分实现了算法在不同K值参数下运行的对比识别结果，支持对K值参数的任意选择，同时具备单步、分步、断点、反复演示功能。另一方面，系统也为实践教学提供了独立的编译环境，由浅入深，实验形式包括了验证性(基本算法程序填空)及设计性(改进算法重新编写程序)。

4　特点、效果及推广

“人工智能”课程内容抽象、难度较大，且不容易应用于工程实践[7]。为了克服这些困难并更好地实现教学目标，就必须在教学方法、内容、手段等方面进行改进。本系统作为人工智能课程的辅助教学系统，具备了以下几个特点。

4.1教学内容由浅入深

选取了模式识别中算法思想较为简单的KNN算法作为入门教学内容，而KNN算法关键的距离机制又选择了传统的、最简单的各条件属性下相同特征参数统计方法和学生最为熟悉的欧式距离公式作为基础教学案例，这些内容浅显易懂，消除了学生对“人工智能”课程“望而生畏”的第一感觉。同时，Entropy相关性距离机制关联科研课题，初步引领学生进入科学研究领域，激发学生对课程学习的兴趣及好奇心。

4.2系统具备教学可行性

围绕“教”与“学”之间的转换，本系统对教学流程的整体性和连贯性具有很强的弹性设置。从功能上，系统突出了单步、分步、断点、反复、连贯运行算法步骤的教学功能；从实现工具平台上，采用了C# Winform窗体，系统具备了高效、易用、可视化程度高的特点。

4.3系统提供了独立的实验环境

对比实际的编程环境，本系统显得实践教学思想更集中，界面更简洁，学习效率更高。同时，针对不同层次的学生，可供选择的程序填空或一段完整程序编制的实验形式也是实践教学的一个亮点。

5　结束语

实践证明，将包含理论演示、实验设计的辅助教学系统应用到“人工智能”课程的教学中，较大地提高了学生的学习积极性，培养了学生善于专研和勇于创新的精神。在后续的课程教学中，可融入其他智能算法，充实、扩大系统的内容及功能，完善系统在算法应用上的整体性，并增加多种实际应用型的验证数据集。

[1]廉师友.人工智能技术导论[M].2版。西安：西安电子科技大学出版社，2002.

[2]王煜，王正欧，白石.用于文本分类的改进KNN算法[J].中文信息学报，2007，21(3):76-81.

[3]邵顺增，李琳.C#程序设计——Windows项目开发[M].北京：清华大学出版社，2008.

[4]倪枫，王明哲，郭法滨，等.基于面向对象思想的SOS体系结构设计方法[J].系统工程与电子技术，2010，32(11):2368-2373.

[5]童先群，周忠眉.基于属性值信息熵的KNN改进算法[J].计算机工程与应用，2010，46(3):115-117.

[6]武小红，周建江，李海林.基于非欧式距离的可能性C-均值聚类[J].南京航空航天大学学报，2006，38(6):703-705.

[7]陈爱斌.“人工智能”课程教学的实践与探索[J].株洲工学院学报，2006，20(6):137-139.

Analysis and Design of KNN Teaching System Based on C#

ZHOU Jing

(College of Computer and Electronic Information，Guangdong University of Petrochemical Technology，Maoming 525000，China)

KNN (K-nearest neighbor) is the most famous pattern recognition statistical method，and it is widely used in text classification，image processing and other fields.Because of simplicity and realization based on case classification method，KNN can be used as entry case algorithm of artificial intelligence courses .For the lazy learning method in KNN classification process，it has some difficulty in the theory and practice teaching.According the study of KNN algorithm and the analysis and design of software teaching system，it has achieved the teaching system based on Visual C#，and includes practical teaching，improving the teaching methods and the quality of teaching.

KNN; practical teaching; practice teaching；analysis and design

2014-12-04；修改日期: 2015-03-19

周靖(1980-)，女，硕士，高级实验师，主要从事人工智能，模式识别方面的教学。

TP3；G642.0

A

10.3969/j.issn.1672-4550.2016.01.029