基于KNN算法的高校困難生認定研究

劉曉娜，王愷，王成德，楊進軍

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

0 引言

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

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

1 KNN技術簡介

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

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

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

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

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

2.2 KNN算法的缺點

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

2.3 幾種常用的改進KNN算法

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

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

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

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

表1 專家-因素權重獨立評估表

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

f(x)是當前加權分類的數(shù)值型結果，計算公式如下式所示：

實現(xiàn)關鍵代碼如下：

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

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

var q-knn(data,vec1):

/*注釋：按照距離值經(jīng)過排序的列表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;

通過加權KNN算法，可通過分析學生的學習成績、家庭經(jīng)濟狀況和其他主要相關因素來更好地識別需要幫助的學生。

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

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

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

3 實驗結果對比

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

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

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

圖3 采用加權KNN 算法得到的分類結果

圖4 采用局部加權KNN 算法得到的分類結果

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

4 結語

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