劉曉娜，王愷，王成德，楊進(jìn)軍

1.蘭州文理學(xué)院，甘肅蘭州，730010；2.甘肅華科信息技術(shù)有限公司，甘肅蘭州，730010

0 引言

高校困難生識(shí)別是指通過(guò)一系列的調(diào)查和評(píng)估，準(zhǔn)確地確定哪些學(xué)生符合貧困生的認(rèn)定標(biāo)準(zhǔn)，以便學(xué)校能夠提供更有針對(duì)性的資助和幫助，幫助他們完成學(xué)業(yè)，促進(jìn)學(xué)生的發(fā)展。而高校學(xué)生的經(jīng)濟(jì)狀況主要由原生家庭所決定，傳統(tǒng)的評(píng)定方式采用學(xué)生自己填表，再結(jié)合人工評(píng)定的方式來(lái)完成。該方式在新環(huán)境下開(kāi)始暴露出一定的弊端，如人為干預(yù)、班內(nèi)拉票等。因此，在助學(xué)系統(tǒng)中，我們期望能提出一種人工與計(jì)算機(jī)結(jié)合的方法，先由評(píng)定人員制定規(guī)則，再由計(jì)算機(jī)對(duì)數(shù)據(jù)進(jìn)行識(shí)別，認(rèn)定貧困生并劃分困難等級(jí)，按等級(jí)進(jìn)行資助。

貧困生的計(jì)算機(jī)認(rèn)定過(guò)程主要依托于對(duì)困難學(xué)生數(shù)據(jù)的分類，認(rèn)定等級(jí)分為一般困難、困難、特別困難三類。在獲取到基本數(shù)據(jù)后，貧困生的認(rèn)定就轉(zhuǎn)變成按照學(xué)生信息字段進(jìn)行分類的問(wèn)題。大多學(xué)者在分類時(shí)，選擇了基于K-means的聚類算法，將學(xué)生劃分為不同的消費(fèi)群體，或者采用K鄰近算法建立預(yù)測(cè)分類模型，再結(jié)合概率分布進(jìn)行反饋。目前已有的研究技術(shù)如下：基于集成學(xué)習(xí)算法的校園貧困生精準(zhǔn)識(shí)別，借助數(shù)據(jù)挖掘技術(shù)采用XCB模型作為評(píng)估模型；在分布式環(huán)境下利用GBDT決策樹(shù)分類算法對(duì)貧困生進(jìn)行分類；基于稀疏貝葉斯學(xué)習(xí)的貧困學(xué)生識(shí)別算法，利用已有貧困學(xué)生信息數(shù)據(jù)訓(xùn)練模型；使用優(yōu)化SVM算法，在特殊類型數(shù)據(jù)識(shí)別方面取得了較大的改進(jìn)[1]。各種算法在模型上各有優(yōu)缺點(diǎn)，但均依托于機(jī)器學(xué)習(xí)，能夠高效地實(shí)現(xiàn)大數(shù)據(jù)處理。所以，貧困生的模式識(shí)別在大數(shù)據(jù)技術(shù)上，借助遺傳算法等工具，是完全具有可行性的。其中，已被證明效率較高的一種方法是使用K近鄰（KNN）算法。

1 KNN技術(shù)簡(jiǎn)介

KNN是一種有監(jiān)督的機(jī)器學(xué)習(xí)算法，可用于根據(jù)數(shù)據(jù)點(diǎn)與其他數(shù)據(jù)點(diǎn)的相似性對(duì)數(shù)據(jù)點(diǎn)進(jìn)行分類。該算法的工作原理是找到給定數(shù)據(jù)點(diǎn)的k個(gè)最近鄰居，然后使用這些鄰居的標(biāo)簽來(lái)對(duì)未標(biāo)記的觀察數(shù)據(jù)點(diǎn)進(jìn)行分類[2]。在計(jì)算時(shí)，每一次計(jì)算當(dāng)前數(shù)據(jù)點(diǎn)與樣本所有點(diǎn)的距離，然后由近到遠(yuǎn)排序，選取最近的k個(gè)點(diǎn)，這k個(gè)點(diǎn)中屬于哪一類的最多，就認(rèn)為該組數(shù)據(jù)屬于哪一類。該算法易于實(shí)現(xiàn)，可用于分類和回歸任務(wù)。執(zhí)行過(guò)程如圖1所示。

圖1 KNN 執(zhí)行過(guò)程圖

2 KNN算法的優(yōu)缺點(diǎn)

2.1 KNN算法的優(yōu)點(diǎn)

該算法在識(shí)別貧困大學(xué)生方面有幾個(gè)優(yōu)點(diǎn)。首先，該算法易于實(shí)現(xiàn)，可用于分類和回歸任務(wù)，這使得它易于用于各種應(yīng)用。其次，該算法是非參數(shù)的，這意味著它不需要任何數(shù)據(jù)的先驗(yàn)知識(shí)，這使得它適用于數(shù)據(jù)不被很好理解的應(yīng)用。再次，該算法對(duì)噪聲和異常值具有魯棒性，這意味著即使當(dāng)數(shù)據(jù)有噪聲或包含異常值時(shí)，它仍能產(chǎn)生準(zhǔn)確的結(jié)果。最后，該算法計(jì)算效率高，這意味著它可以在相對(duì)短的時(shí)間內(nèi)用于對(duì)大型數(shù)據(jù)集進(jìn)行分類[3]。

2.2 KNN算法的缺點(diǎn)

盡管KNN算法有優(yōu)點(diǎn)，但在識(shí)別貧困大學(xué)生時(shí)，它也有一些缺點(diǎn)。首先，該算法對(duì)k的選擇很敏感，這意味著結(jié)果的準(zhǔn)確性可能會(huì)根據(jù)k的值而變化，這意味著為數(shù)據(jù)集選擇合適的k值很重要。其次，該算法不適用于高維數(shù)據(jù)，意味著它可能無(wú)法準(zhǔn)確地對(duì)分布式環(huán)境中的數(shù)據(jù)點(diǎn)進(jìn)行分類。再次，該算法不適合具有缺失值的數(shù)據(jù)，這意味著它可能無(wú)法準(zhǔn)確地對(duì)具有缺失值的數(shù)據(jù)點(diǎn)進(jìn)行分類。最后，該算法不適用于具有非線性關(guān)系的數(shù)據(jù)，這意味著它可能無(wú)法準(zhǔn)確地對(duì)具有非線性關(guān)系的數(shù)據(jù)點(diǎn)進(jìn)行分類。

2.3 幾種常用的改進(jìn)KNN算法

總的來(lái)說(shuō)，KNN算法是一種簡(jiǎn)單有效的分類方法，它可以應(yīng)用于多個(gè)領(lǐng)域的問(wèn)題，但也存在一些缺點(diǎn)，如計(jì)算復(fù)雜度高、受數(shù)據(jù)維度影響等。針對(duì)這些問(wèn)題，研究人員提出了許多改進(jìn)算法，如距離加權(quán)KNN算法、局部加權(quán)KNN算法、混合KNN算法等，這些算法在一定程度上提高了KNN算法的分類精度和計(jì)算效率，對(duì)實(shí)際問(wèn)題的解決也起到了積極的作用[4]。

（1）距離加權(quán)KNN算法。該方法基于不同鄰居與數(shù)據(jù)點(diǎn)的距離為不同鄰居分配不同的權(quán)重。這可以通過(guò)給更近的鄰居賦予更多的權(quán)重來(lái)幫助提高算法的準(zhǔn)確性。該算法的工作原理是找到給定數(shù)據(jù)點(diǎn)的k個(gè)最近鄰居，然后使用數(shù)據(jù)點(diǎn)的屬性對(duì)數(shù)據(jù)點(diǎn)進(jìn)行分類。具體工作中，加權(quán)KNN算法通過(guò)為每個(gè)數(shù)據(jù)點(diǎn)的屬性分配權(quán)重，這些權(quán)重用于確定分類過(guò)程中每個(gè)屬性的重要性。例如，如果學(xué)生的學(xué)習(xí)成績(jī)比他們的財(cái)務(wù)狀況更重要，那么學(xué)習(xí)成績(jī)屬性將被賦予比財(cái)務(wù)狀況屬性更高的權(quán)重，這允許算法在對(duì)數(shù)據(jù)點(diǎn)進(jìn)行分類時(shí)關(guān)注最重要的屬性。

加權(quán)KNN首先獲得經(jīng)過(guò)排序的距離值，再取距離最近的k個(gè)元素。在處理離散數(shù)據(jù)時(shí)，將這k個(gè)數(shù)據(jù)用權(quán)重區(qū)別對(duì)待。在處理數(shù)值型數(shù)據(jù)時(shí)，并不是對(duì)這k個(gè)數(shù)據(jù)簡(jiǎn)單地求平均，而是加權(quán)平均：通過(guò)將每一項(xiàng)的距離值乘以對(duì)應(yīng)權(quán)重，然后將結(jié)果累加。求出總和后，再對(duì)其除以所有權(quán)重之和。

在某問(wèn)題分析中，設(shè)各因素的權(quán)重值為qi，權(quán)重反映了各個(gè)因素在分類時(shí)所占的地位和所起的作用，可憑經(jīng)驗(yàn)直接給出，但這種方式過(guò)于主觀性，評(píng)判結(jié)果可能失真。為保證公平公正，可采用專家預(yù)測(cè)法來(lái)確定權(quán)重。設(shè)有k個(gè)專家獨(dú)立地給出因素值，如表1所示。

表1 專家-因素權(quán)重獨(dú)立評(píng)估表

在得出權(quán)重值qi后，設(shè)當(dāng)前節(jié)點(diǎn)x與鄰居節(jié)點(diǎn)xi的距離為歐幾里得距離Di，則Di值計(jì)算如下式所示，m為原始數(shù)據(jù)樣本數(shù)：

f(x)是當(dāng)前加權(quán)分類的數(shù)值型結(jié)果，計(jì)算公式如下式所示：

實(shí)現(xiàn)關(guān)鍵代碼如下：

/*注釋：創(chuàng)建加權(quán)KNN函數(shù)q-knn，根據(jù)前k項(xiàng)估值，采用加權(quán)KNN算法計(jì)算f(x)的值，qf(x)為計(jì)算出的各評(píng)價(jià)因素的權(quán)值*/

var q-knn(k,qf(x)=weight):

var q-knn(data,vec1):

/*注釋：按照距離值經(jīng)過(guò)排序的列表f(x)*/

f(x) = getdistances(data,vec1);

avg = 0;

total_weight = 0.0

for i to range(k)

{(dist,id) = x[i];

weight = qf(dist);

avg= avg +data[id]['result']*weight;

total_weight = total_weight +weight;

avg = avg/total_weight; }

return avg;

return q-knn;

通過(guò)加權(quán)KNN算法，可通過(guò)分析學(xué)生的學(xué)習(xí)成績(jī)、家庭經(jīng)濟(jì)狀況和其他主要相關(guān)因素來(lái)更好地識(shí)別需要幫助的學(xué)生。

（2）局部加權(quán)KNN。該方法也是一種基于距離加權(quán)的改進(jìn)k近鄰方法。不同的是，普通KNN算法是對(duì)全部的樣本計(jì)算，而局部加權(quán)k近鄰算法，通過(guò)引入權(quán)值，即核函數(shù)的方式，在預(yù)測(cè)的時(shí)候，只使用與測(cè)試點(diǎn)距離相近的部分樣本來(lái)計(jì)算回歸系數(shù)。該算法的工作原理是分析給定學(xué)生的數(shù)據(jù)點(diǎn)，然后使用數(shù)據(jù)點(diǎn)的屬性和權(quán)重將學(xué)生分類，使用核來(lái)對(duì)附近的點(diǎn)賦予更高的權(quán)重，核的類型可以自由選擇，權(quán)重計(jì)算一般使用簡(jiǎn)單的高斯核函數(shù)等方法。設(shè)x為樣本數(shù)，xi為其中第i項(xiàng)數(shù)據(jù)，則本次的高斯核計(jì)算如下式所示：

其中w是一個(gè)對(duì)角方陣，方陣大小與x的樣本數(shù)量相等，計(jì)算每一個(gè)樣本點(diǎn)的時(shí)候都要計(jì)算一次w矩陣。一個(gè)均值為x、標(biāo)準(zhǔn)差為k的高斯函數(shù)，與測(cè)試樣本x越近的樣本點(diǎn)，能夠得到更高的權(quán)重，而遠(yuǎn)的點(diǎn)則權(quán)重很小，以此來(lái)提高模型對(duì)局部特征的刻畫能力。該算法對(duì)數(shù)據(jù)的差異進(jìn)行放大，適用于數(shù)據(jù)量大、原始數(shù)據(jù)差異較小的環(huán)境[5]。

（3）混合KNN算法是一種將多個(gè)KNN分類器集成起來(lái)的方法，它通過(guò)對(duì)不同的KNN分類器進(jìn)行加權(quán)，以獲得更好的分類精度?；旌螷NN算法可以使用多種不同的KNN分類器，如不同的距離度量方法、不同的k值等，通過(guò)對(duì)這些分類器進(jìn)行加權(quán)，可以有效地提高模型的分類精度，缺點(diǎn)是需要確定的參數(shù)較多，算法實(shí)現(xiàn)比較復(fù)雜[6]。

3 實(shí)驗(yàn)結(jié)果對(duì)比

利用隨機(jī)生成的原始數(shù)據(jù)集，按KNN算法實(shí)驗(yàn)，如表2所示。實(shí)驗(yàn)軟件采用MATLAB，操作系統(tǒng)為Win10，內(nèi)存4G，CPU i7。對(duì)于測(cè)試數(shù)據(jù)中的每一個(gè)實(shí)例，MATLAB中可以借助Class包中的KNN()函數(shù)來(lái)實(shí)現(xiàn)分類，該函數(shù)使用歐氏距離來(lái)標(biāo)識(shí)k個(gè)近鄰，以一個(gè)單獨(dú)的因子向量來(lái)存放數(shù)據(jù)標(biāo)簽，通過(guò)k個(gè)近鄰的投票來(lái)對(duì)測(cè)試的數(shù)據(jù)進(jìn)行分類認(rèn)定。按照二分類的結(jié)果，一般k取奇數(shù)，可消除各類票數(shù)相等的可能性，如訓(xùn)練數(shù)據(jù)有500條，那么可嘗試k為23，該值為素?cái)?shù)，且為接近500的開(kāi)方的奇數(shù)。實(shí)驗(yàn)中，對(duì)隨機(jī)生成的原始500個(gè)數(shù)據(jù)，分別采用加權(quán)k近鄰和局部加權(quán)k近鄰算法進(jìn)行聚類分析。原始數(shù)據(jù)如圖2所示，實(shí)驗(yàn)1按照加權(quán)KNN的分類結(jié)果如圖3所示，實(shí)驗(yàn)2按照局部加權(quán)KNN所得結(jié)果如圖4所示。

表2 KNN 算法下的數(shù)據(jù)實(shí)驗(yàn)表

圖2 原始隨機(jī)數(shù)據(jù)集

圖3 采用加權(quán)KNN 算法得到的分類結(jié)果

圖4 采用局部加權(quán)KNN 算法得到的分類結(jié)果

由圖3、圖4可見(jiàn)，采用KNN算法，不論是加權(quán)k近鄰還是局部加權(quán)k近鄰，都可以較好地對(duì)數(shù)據(jù)進(jìn)行分類。數(shù)據(jù)之間的聚合度好、聚類清晰，可有效地將貧困生按數(shù)據(jù)分為特別困難、困難和一般困難三類，算法運(yùn)行時(shí)間也在6秒以內(nèi)，性能良好[7]。

4 結(jié)語(yǔ)

綜上所述，KNN算法可用于識(shí)別貧困大學(xué)生。該算法具有簡(jiǎn)單、對(duì)噪聲和異常值兼容以及計(jì)算效率高等優(yōu)點(diǎn)。然而，該算法也有一些缺點(diǎn)，包括對(duì)k值的選擇比較敏感，無(wú)法處理高維數(shù)據(jù)，以及無(wú)法處理缺失值和非線性關(guān)系的數(shù)據(jù)等。實(shí)踐證明，KNN算法可用于準(zhǔn)確識(shí)別貧困大學(xué)生，對(duì)實(shí)現(xiàn)教育的精準(zhǔn)扶貧具有一定的應(yīng)用價(jià)值。