周　靖

(廣東石油化工學(xué)院　計(jì)算機(jī)與電子信息學(xué)院，廣東　茂名　525000)

?

基于C#最近鄰算法的教學(xué)系統(tǒng)分析與設(shè)計(jì)

周靖

(廣東石油化工學(xué)院計(jì)算機(jī)與電子信息學(xué)院，廣東茂名525000)

K-近鄰分類(KNN)是著名的模式識(shí)別統(tǒng)計(jì)學(xué)方法之一，被廣泛應(yīng)用于文本分類、圖像處理等領(lǐng)域。因其實(shí)現(xiàn)思想的簡(jiǎn)單性及基于實(shí)例的分類方法，可作為人工智能課程的入門案例算法。由于KNN分類識(shí)別過(guò)程中懶散的學(xué)習(xí)方式，在理論與實(shí)踐教學(xué)上存在著一定的難度。通過(guò)對(duì)KNN算法的研究和軟件教學(xué)系統(tǒng)的分析與設(shè)計(jì)，實(shí)現(xiàn)了基于Visual C#的KNN各種演示方法和輔助教學(xué)系統(tǒng)；改進(jìn)了教學(xué)手段，提高了教學(xué)質(zhì)量。

K-近鄰分類算法；理論教學(xué)；實(shí)驗(yàn)教學(xué)；分析與設(shè)計(jì)

1　研究背景

K-近鄰分類算法是人工智能模式識(shí)別方法之一[1-2]。其算法思想為:給定一個(gè)待分類樣本，系統(tǒng)在訓(xùn)練集中查找最相似的K個(gè)近鄰樣本，并根據(jù)這些近鄰樣本的類別決策屬性個(gè)數(shù)給該樣本的候選決策屬性評(píng)分。由于它與人的思維方式相似，較容易使用和理解，因而成了許多高校信息類學(xué)科本科高年級(jí)人工智能課程教學(xué)的入門案例算法。但在實(shí)際的教學(xué)過(guò)程中，圍繞算法對(duì)K值參數(shù)依賴較大的惰性算法，一直以講授知識(shí)表示和搜索推理技術(shù)為主導(dǎo)，缺乏完備的、形象的教學(xué)系統(tǒng)，學(xué)生在學(xué)習(xí)的過(guò)程中大都采用死記硬背其方法及步驟，加之目前研究模式識(shí)別的主要工具是Matlab，實(shí)踐手段較為單一、抽象，針對(duì)這些情況，設(shè)計(jì)開發(fā)了KNN教學(xué)系統(tǒng)。C#是一種面向?qū)ο蟮木幊陶Z(yǔ)言，衍生于C和C++，憑借其簡(jiǎn)單、功能強(qiáng)大、類型安全，以及面向?qū)ο蟮葍?yōu)勢(shì)可實(shí)現(xiàn)應(yīng)用程序的快速開發(fā)[3]。因此，結(jié)合C#構(gòu)建一個(gè)形象、內(nèi)容新穎、實(shí)用性和對(duì)比性強(qiáng)的教學(xué)與實(shí)驗(yàn)系統(tǒng)，使學(xué)生可以在該系統(tǒng)上觀察、學(xué)習(xí)、實(shí)現(xiàn)并驗(yàn)證所學(xué)習(xí)的理論算法，探索和研究新的改進(jìn)方法。該系統(tǒng)便于因材施教，為學(xué)生提供了深入鉆研和發(fā)揮創(chuàng)新性思想空間。

2　系統(tǒng)分析與設(shè)計(jì)

2.1系統(tǒng)需求分析

由于系統(tǒng)的主要目標(biāo)是為教學(xué)提供演示及實(shí)踐的一體化操作平臺(tái)，故在系統(tǒng)的設(shè)計(jì)階段著重考慮平臺(tái)操作的適用性和針對(duì)性。系統(tǒng)用戶包括有教師和學(xué)生。在其需求上，針對(duì)教師，系統(tǒng)需具備層次結(jié)構(gòu)清晰、對(duì)比性強(qiáng)、重點(diǎn)突出并能反復(fù)操作的演示功能；針對(duì)學(xué)生，系統(tǒng)要提供基本的、可拓展的實(shí)驗(yàn)操作環(huán)境，同時(shí)配備操作細(xì)節(jié)詳細(xì)的幫助信息。系統(tǒng)用例圖如圖1所示。

2.2系統(tǒng)設(shè)計(jì)

系統(tǒng)主體功能分為KNN背景介紹、KNN思想演示、實(shí)驗(yàn)操作3大功能模塊。其中涉及理論教學(xué)演示的KNN背景介紹及思想演示模塊均配備了單步、分步、斷點(diǎn)、反復(fù)、連貫運(yùn)行算法步驟的教學(xué)功能。

圖1　系統(tǒng)用例圖

2.2.1KNN背景介紹

該部分主要功能包括KNN算法起源、發(fā)展及應(yīng)用領(lǐng)域的展示。本科高年級(jí)學(xué)生對(duì)算法應(yīng)用領(lǐng)域、效果頗為感興趣，這樣的演示性教學(xué)能夠增強(qiáng)模式識(shí)別技術(shù)進(jìn)化歷程的直觀印象，樹立研究目標(biāo)，理清研究方向。

2.2.2KNN算法思想介紹

整個(gè)算法思想演示模塊的結(jié)構(gòu)如圖2所示，以下詳細(xì)說(shuō)明圖中各功能模塊的設(shè)計(jì)思路。

圖2　KNN算法演示系統(tǒng)模塊結(jié)構(gòu)圖

1)選擇UCI數(shù)據(jù)集，系統(tǒng)以文本形式引入U(xiǎn)CI數(shù)據(jù)集，并將ListView列表視圖控件作為UCI數(shù)據(jù)集的選擇操作窗口。在觸發(fā)ListView的SelectedIndexChanged事件后，UCI數(shù)據(jù)集界面對(duì)應(yīng)顯示已選擇數(shù)據(jù)集的條件和決策屬性、樣本數(shù)量等詳細(xì)信息。全局上可通過(guò)系統(tǒng)的下拉菜單切換到其他功能界面。

2)相似性距離測(cè)度的計(jì)算功能，采用面向?qū)ο箢惻c對(duì)象的概念[4]進(jìn)行設(shè)計(jì)。

①類SP為計(jì)算待測(cè)樣本與訓(xùn)練集樣本的條件屬性值相同的個(gè)數(shù)[5]。

②類ED為歐式距離測(cè)度方法[6]，具體計(jì)算公式為:

(1)

式中：tik，tjk分別表示條件屬性r下訓(xùn)練集樣本xi和待分樣本xj的特征參數(shù)。

③類Entropy為基于信息熵的距離計(jì)算方法，包含3個(gè)步驟。首先統(tǒng)計(jì)待分樣本各條件屬性下特征參數(shù)在數(shù)據(jù)集中出現(xiàn)的次數(shù)及歸屬各個(gè)決策屬性的實(shí)例個(gè)數(shù)。其次依據(jù)熵的計(jì)算表達(dá)式:

(2)

得到特征參數(shù)ti對(duì)分類的相關(guān)性Corr(ti)的定義，其中p(ti)是ti分布概率，p(tir)是ti特征參數(shù)決策屬性為r的概率值，然后歸納待分樣本各條件屬性下特征參數(shù)與訓(xùn)練集中樣本的絕對(duì)差異值。最后累加平均差異值，即是樣本間的距離值。

上述3種算法中涉及的數(shù)據(jù)集相關(guān)信息定義為類中的數(shù)據(jù)成員，具體計(jì)算步驟定義為類中的方法，供主程序引用，達(dá)到提高代碼重用及簡(jiǎn)化程序的作用。3個(gè)類分別聲明于3個(gè)獨(dú)立的窗體，運(yùn)行演示順序上可以交替轉(zhuǎn)換，在界面上以Button按鈕的Click事件控制每一次都只運(yùn)行3個(gè)類中其中的一個(gè)獨(dú)立方法函數(shù)，同時(shí)將計(jì)算過(guò)程中所有樣本間的距離值存儲(chǔ)在對(duì)象的數(shù)組數(shù)據(jù)類型成員中，并將數(shù)組元素值作為函數(shù)參數(shù)傳遞到K值設(shè)置界面。限于篇幅，以下給出Entropy類定義。

Public partial class Entropy:Form{

public Entropy( ) {InitializeComponent( );} //構(gòu)造函數(shù)

longm;//數(shù)據(jù)成員，樣本集中樣本個(gè)數(shù)

intn;//數(shù)據(jù)成員，n個(gè)不同的類別

int [] ds=new int [MAX];//存儲(chǔ)樣本間各條件屬性下特征參數(shù)的差異值

……

private void Statistic( ) {

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

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

if Corr(tj) 不存在

檢索TRn*v，統(tǒng)計(jì)特征集{|tj|}和{|trj|}，計(jì)算Corr(tj)并存儲(chǔ)e(tj)值；//r=1，2，…，n，

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

//類的方法，對(duì)樣本參數(shù)進(jìn)行相關(guān)性值計(jì)算預(yù)處理

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)|；

存儲(chǔ)D_Corr值；}

//類的方法，計(jì)算或判斷Tt與Te樣本各特征間的相關(guān)性差異值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)累加求平均值得到樣本間的距離測(cè)度；}

//類的方法，計(jì)算Tt與Te樣本的距離。}

3)K參數(shù)的設(shè)置，教學(xué)系統(tǒng)不同于算法的仿真系統(tǒng)，不需要突出最優(yōu)化參數(shù)的識(shí)別結(jié)果，而是對(duì)教學(xué)演示過(guò)程中的“比較性”有明確的要求。鑒于此，該系統(tǒng)中每個(gè)K值參數(shù)變化后，至少保存上一個(gè)K值參數(shù)識(shí)別結(jié)果，全局上可通過(guò)TabControl選項(xiàng)卡控件控制每個(gè)參數(shù)識(shí)別結(jié)果顯示的切換，并顯示K個(gè)近鄰樣本的相關(guān)信息。

由于KNN算法的分類計(jì)算發(fā)生在訓(xùn)練過(guò)程中，因此分類器的生成是連接模塊，涉及相似性距離計(jì)算、K值設(shè)定及UCI數(shù)據(jù)集選擇各功能模塊的參數(shù)調(diào)用，綜合以上KNN算法思想介紹系統(tǒng)順序圖如圖3所示。

圖3　KNN算法思想介紹系統(tǒng)順序圖

2.2.3演示過(guò)程中的教學(xué)功能

以上功能中均以MenuStrip主菜單和ComboBox上下文菜單控件實(shí)現(xiàn)算法單步和分步運(yùn)行演示、斷點(diǎn)處運(yùn)行演示、連貫運(yùn)行演示、反復(fù)演示及返回上層教學(xué)演示界面。單步運(yùn)行演示首先通過(guò)ListView控件顯示可供單步運(yùn)行演示的若干算法步驟；然后以ListView控件的SelectedIndexChanged事件觸發(fā)控制，鼠標(biāo)每選擇一個(gè)步驟，就運(yùn)行一個(gè)類中的計(jì)算方法。連貫和分步運(yùn)行演示形式類似與單步運(yùn)行，只是用Timer控件控制每步之間的停頓時(shí)間，并記錄跳躍或返回前任一步驟的運(yùn)行信息。遵循ListView控件中的item項(xiàng)的索引順序，可實(shí)現(xiàn)返回功能、指定反復(fù)運(yùn)行的功能。斷點(diǎn)出運(yùn)行演示，即是算法運(yùn)行停頓到斷點(diǎn)處，其思路是通過(guò)namespace中定義的方法，將算法運(yùn)行到斷點(diǎn)處的相關(guān)計(jì)算信息、運(yùn)行存儲(chǔ)到相關(guān)的數(shù)據(jù)類型中，Break跳出類中的計(jì)算方法。上述功能基本思路如圖4所示。

圖4　教學(xué)功能基本思路設(shè)計(jì)圖

2.2.4實(shí)驗(yàn)操作

在這部分系統(tǒng)中，針對(duì)學(xué)生的實(shí)踐課程要求設(shè)計(jì)了基礎(chǔ)實(shí)驗(yàn)操作、拓展實(shí)驗(yàn)操作、幫助3個(gè)功能模塊。其中，對(duì)于基礎(chǔ)實(shí)驗(yàn)操作實(shí)驗(yàn)內(nèi)容的設(shè)置，主要以教學(xué)演示過(guò)程中涉及的3種距離測(cè)度機(jī)制為基礎(chǔ)，讓學(xué)生對(duì)SP、ED及Entropy 3個(gè)類的計(jì)算發(fā)放進(jìn)行程序填空，運(yùn)行后即可驗(yàn)證分類識(shí)別效果是否與教學(xué)過(guò)程中的演示結(jié)果一致；拓展實(shí)驗(yàn)操作則要求學(xué)生在基礎(chǔ)實(shí)驗(yàn)操作的鋪墊下，充分發(fā)揮自身的想象力、創(chuàng)造力，改進(jìn)算法，進(jìn)行完整的程序編寫，運(yùn)行后對(duì)比并分析若干類方法的分類識(shí)別結(jié)果；幫助模塊用于讓學(xué)生了解、熟悉實(shí)驗(yàn)?zāi)康摹?nèi)容、步驟及實(shí)驗(yàn)環(huán)境。

本文著重研究基礎(chǔ)實(shí)驗(yàn)與拓展實(shí)驗(yàn)操作。這兩個(gè)模塊是為了模擬KNN算法C#編程的現(xiàn)實(shí)實(shí)驗(yàn)環(huán)境，無(wú)需重新啟動(dòng)VS進(jìn)入真實(shí)的程序編寫環(huán)境。在Form窗體里，首先，設(shè)置Label標(biāo)簽控件提示可供改進(jìn)的KNN算法點(diǎn)，學(xué)生通過(guò)在通過(guò)TextBox控件補(bǔ)充、添加新代碼進(jìn)行程序填空或重新編程；其次，在同一Form窗體中布置一個(gè)Button控件作為編譯觸發(fā)器，通過(guò)其Click事件調(diào)用CSharp namespace中的Codeprovide類直接編譯由TextBox控件逐一輸入、組合的字符串代碼集合，并把編譯是否成功以布爾類型True或False來(lái)判斷MessageBox.show()的提示字符；最后若編譯正確，啟動(dòng)另一Form窗體，以顯示程序運(yùn)行結(jié)果，否則返回上層編輯Form窗體修改。另外，在編寫程序Form窗口還配備另一Label標(biāo)簽控件，始終顯示實(shí)驗(yàn)內(nèi)容、目的及步驟。

3　系統(tǒng)的實(shí)現(xiàn)

本系統(tǒng)采用傳統(tǒng)各條件屬性下相同特征參數(shù)統(tǒng)計(jì)、歐式計(jì)算、Entropy相關(guān)性3種不同的距離機(jī)制演示KNN算法，設(shè)置K值參數(shù)為5～35。在教學(xué)演示部分實(shí)現(xiàn)了算法在不同K值參數(shù)下運(yùn)行的對(duì)比識(shí)別結(jié)果，支持對(duì)K值參數(shù)的任意選擇，同時(shí)具備單步、分步、斷點(diǎn)、反復(fù)演示功能。另一方面，系統(tǒng)也為實(shí)踐教學(xué)提供了獨(dú)立的編譯環(huán)境，由淺入深，實(shí)驗(yàn)形式包括了驗(yàn)證性(基本算法程序填空)及設(shè)計(jì)性(改進(jìn)算法重新編寫程序)。

4　特點(diǎn)、效果及推廣

“人工智能”課程內(nèi)容抽象、難度較大，且不容易應(yīng)用于工程實(shí)踐[7]。為了克服這些困難并更好地實(shí)現(xiàn)教學(xué)目標(biāo)，就必須在教學(xué)方法、內(nèi)容、手段等方面進(jìn)行改進(jìn)。本系統(tǒng)作為人工智能課程的輔助教學(xué)系統(tǒng)，具備了以下幾個(gè)特點(diǎn)。

4.1教學(xué)內(nèi)容由淺入深

選取了模式識(shí)別中算法思想較為簡(jiǎn)單的KNN算法作為入門教學(xué)內(nèi)容，而KNN算法關(guān)鍵的距離機(jī)制又選擇了傳統(tǒng)的、最簡(jiǎn)單的各條件屬性下相同特征參數(shù)統(tǒng)計(jì)方法和學(xué)生最為熟悉的歐式距離公式作為基礎(chǔ)教學(xué)案例，這些內(nèi)容淺顯易懂，消除了學(xué)生對(duì)“人工智能”課程“望而生畏”的第一感覺(jué)。同時(shí)，Entropy相關(guān)性距離機(jī)制關(guān)聯(lián)科研課題，初步引領(lǐng)學(xué)生進(jìn)入科學(xué)研究領(lǐng)域，激發(fā)學(xué)生對(duì)課程學(xué)習(xí)的興趣及好奇心。

4.2系統(tǒng)具備教學(xué)可行性

圍繞“教”與“學(xué)”之間的轉(zhuǎn)換，本系統(tǒng)對(duì)教學(xué)流程的整體性和連貫性具有很強(qiáng)的彈性設(shè)置。從功能上，系統(tǒng)突出了單步、分步、斷點(diǎn)、反復(fù)、連貫運(yùn)行算法步驟的教學(xué)功能；從實(shí)現(xiàn)工具平臺(tái)上，采用了C# Winform窗體，系統(tǒng)具備了高效、易用、可視化程度高的特點(diǎn)。

4.3系統(tǒng)提供了獨(dú)立的實(shí)驗(yàn)環(huán)境

對(duì)比實(shí)際的編程環(huán)境，本系統(tǒng)顯得實(shí)踐教學(xué)思想更集中，界面更簡(jiǎn)潔，學(xué)習(xí)效率更高。同時(shí)，針對(duì)不同層次的學(xué)生，可供選擇的程序填空或一段完整程序編制的實(shí)驗(yàn)形式也是實(shí)踐教學(xué)的一個(gè)亮點(diǎn)。

5　結(jié)束語(yǔ)

實(shí)踐證明，將包含理論演示、實(shí)驗(yàn)設(shè)計(jì)的輔助教學(xué)系統(tǒng)應(yīng)用到“人工智能”課程的教學(xué)中，較大地提高了學(xué)生的學(xué)習(xí)積極性，培養(yǎng)了學(xué)生善于專研和勇于創(chuàng)新的精神。在后續(xù)的課程教學(xué)中，可融入其他智能算法，充實(shí)、擴(kuò)大系統(tǒng)的內(nèi)容及功能，完善系統(tǒng)在算法應(yīng)用上的整體性，并增加多種實(shí)際應(yīng)用型的驗(yàn)證數(shù)據(jù)集。

[1]廉師友.人工智能技術(shù)導(dǎo)論[M].2版。西安：西安電子科技大學(xué)出版社，2002.

[2]王煜，王正歐，白石.用于文本分類的改進(jìn)KNN算法[J].中文信息學(xué)報(bào)，2007，21(3):76-81.

[3]邵順增，李琳.C#程序設(shè)計(jì)——Windows項(xiàng)目開發(fā)[M].北京：清華大學(xué)出版社，2008.

[4]倪楓，王明哲，郭法濱，等.基于面向?qū)ο笏枷氲腟OS體系結(jié)構(gòu)設(shè)計(jì)方法[J].系統(tǒng)工程與電子技術(shù)，2010，32(11):2368-2373.

[5]童先群，周忠眉.基于屬性值信息熵的KNN改進(jìn)算法[J].計(jì)算機(jī)工程與應(yīng)用，2010，46(3):115-117.

[6]武小紅，周建江，李海林.基于非歐式距離的可能性C-均值聚類[J].南京航空航天大學(xué)學(xué)報(bào)，2006，38(6):703-705.

[7]陳愛(ài)斌.“人工智能”課程教學(xué)的實(shí)踐與探索[J].株洲工學(xué)院學(xué)報(bào)，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-)，女，碩士，高級(jí)實(shí)驗(yàn)師，主要從事人工智能，模式識(shí)別方面的教學(xué)。

TP3；G642.0

A

10.3969/j.issn.1672-4550.2016.01.029