MD-KNN算法在高校精準(zhǔn)資助中的應(yīng)用

李 博，李 霞，張 曉，王艷秋，李 恒，張 勇，凌玉龍

(1.西北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安 710129；2.西北工業(yè)大學(xué) 工信部大數(shù)據(jù)存儲(chǔ)與管理重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710129；3.西北工業(yè)大學(xué) 學(xué)生資助服務(wù)中心，陜西 西安 710129)

0 引 言

學(xué)生群體是社會(huì)中非常重要的群體，并且對(duì)社會(huì)的發(fā)展有重大影響，因此對(duì)學(xué)生行為的分析有很大的意義。但是由于學(xué)生群體是一個(gè)相似度比較高的群體，目前針對(duì)學(xué)生群體的數(shù)據(jù)挖掘算法還比較少。貧困學(xué)生的篩選與資助是很多高校的一項(xiàng)重要事務(wù)，通過(guò)分析學(xué)生的家庭情況、消費(fèi)和學(xué)習(xí)行為，可以找到需要資助的貧困學(xué)生群體，還可以預(yù)防甄別生活規(guī)律有異常的學(xué)生，從而進(jìn)行相應(yīng)的幫助[1-5]。

基于馬氏距離的KNN算法(Mahalanobis distance k-nearest neighbor algorithm，MD-KNN，馬氏KNN)是一種改進(jìn)的KNN算法。相比于傳統(tǒng)的KNN算法，MD-KNN算法采用了馬氏距離，可以更好地處理一些非數(shù)值型數(shù)據(jù)，比如：生源地、性別等因素。文中采用該算法，以西安某高校在校學(xué)生數(shù)據(jù)為樣本，進(jìn)行實(shí)驗(yàn)分析，探究MD-KNN算法在貧困學(xué)生資助工作中的效果。在通過(guò)MD-KNN算法篩選得到擬貧困學(xué)生名單后，與實(shí)際篩選名單進(jìn)行對(duì)比，分析兩者的匹配率，以及學(xué)生的消費(fèi)水平。在分析學(xué)生數(shù)據(jù)時(shí)發(fā)現(xiàn)：貧困學(xué)生的在校就餐次數(shù)與就餐天數(shù)會(huì)有一定的規(guī)律，并通過(guò)實(shí)驗(yàn)分析驗(yàn)證了這一觀點(diǎn)。此外還發(fā)現(xiàn)，學(xué)生吃早餐情況也與該生的學(xué)習(xí)成績(jī)之間有正相關(guān)的聯(lián)系[6-9]。

1 研究現(xiàn)狀

KNN分類(lèi)算法是一種經(jīng)典且應(yīng)用廣泛的數(shù)據(jù)挖掘算法。隨著科學(xué)技術(shù)的發(fā)展，為了適應(yīng)一些新問(wèn)題、新背景，在傳統(tǒng)KNN算法的基礎(chǔ)上也不斷提出新的改進(jìn)方法，比如：AHP-KNN(analytic hierarchy process KNN)、FCD-KNN(feature correlation difference KNN)等。MD-KNN算法是在原先KNN算法的基礎(chǔ)上，采用馬氏距離(Mahalanobis distance)來(lái)計(jì)算樣本之間的距離，因此MD-KNN算法可以更多地考慮非數(shù)值型因素，從而提升算法的精度。根據(jù)在西安某高校收集的學(xué)生數(shù)據(jù)，其中以數(shù)值型數(shù)據(jù)為主，如經(jīng)濟(jì)消費(fèi)數(shù)據(jù)、學(xué)習(xí)成績(jī)、圖書(shū)館入館記錄、借書(shū)記錄等，也有部分非數(shù)值數(shù)據(jù)，如生源地、性別、是否殘疾單親等。文中選用MD-KNN算法進(jìn)行學(xué)生行為的分析，探索學(xué)生行為的規(guī)律，并篩選需要資助的學(xué)生，以及行為有異常的學(xué)生[10-12]。

國(guó)內(nèi)外對(duì)于學(xué)生群體的行為分析由來(lái)已久，20世紀(jì)就有人開(kāi)始進(jìn)行研究。隨著時(shí)代的發(fā)展，學(xué)生的行為也變得復(fù)雜化，但是學(xué)生群體內(nèi)部依然具有較高的相似性。如何對(duì)貧困學(xué)生進(jìn)行精確資助，以及分析學(xué)生行為，提高學(xué)生學(xué)習(xí)生活質(zhì)量，保障學(xué)生生活安全，成為了各個(gè)高校關(guān)心的熱點(diǎn)問(wèn)題之一。隨著大數(shù)據(jù)技術(shù)的發(fā)展，從2014年起，很多團(tuán)隊(duì)嘗試將大數(shù)據(jù)分析與精準(zhǔn)資助相結(jié)合，如西北工業(yè)大學(xué)學(xué)生資助服務(wù)中心的李霞老師團(tuán)隊(duì)。但是現(xiàn)有大部分高校的精準(zhǔn)資助系統(tǒng)的算法具有局限性，過(guò)于主觀，某些高校的貧困學(xué)生通過(guò)老師或?qū)W生人工篩選推薦，缺乏科學(xué)的理論分析。文中采用MD-KNN算法來(lái)進(jìn)行學(xué)生行為的分析，從大數(shù)據(jù)角度探究學(xué)生行為，推動(dòng)困難學(xué)生精準(zhǔn)資助領(lǐng)域的發(fā)展[13-15]。

2 理論介紹

2.1 MD-KNN算法介紹

馬氏距離是由印度統(tǒng)計(jì)學(xué)家馬哈拉諾比斯(P. C. Mahalanobis)提出的，表示數(shù)據(jù)的協(xié)方差距離[14-15]。經(jīng)典的KNN算法采用的是歐氏距離，歐氏距離單純地考慮數(shù)值上的距離，但是當(dāng)前在很多的實(shí)際場(chǎng)景中需要考慮非數(shù)值型的因素，并且很多因素之間并不是相互獨(dú)立的。馬氏距離認(rèn)為屬性之間是存在聯(lián)系的，比如身高與鞋碼之間就是存在聯(lián)系的，所以在距離計(jì)算公式中引入了協(xié)方差。而如果是兩個(gè)完全獨(dú)立的變量，其協(xié)方差是0，在這種情況下就變成了歐氏距離。對(duì)于一個(gè)均值為μ=(μ1,μ2,…,μp)T，協(xié)方差矩陣為Σ的多變量向量x=(x1,x2,…,xp)T，其馬氏距離為：

(1)

其中，T是指矩陣的轉(zhuǎn)置。

在馬氏距離的設(shè)計(jì)中，某一微小變量的作用可以被放大，這在某些應(yīng)用環(huán)境中會(huì)導(dǎo)致過(guò)度擬合的狀況。但不同于其他數(shù)據(jù)，學(xué)生群體是一個(gè)具有高相似性的群體，大部分成員內(nèi)部之間生活作息規(guī)律比較相似，就餐時(shí)間、地點(diǎn)相對(duì)固定且有規(guī)律，不同學(xué)生樣本的行為也是大致相似。而如果通過(guò)分析發(fā)現(xiàn)一些奇異點(diǎn)，或者某些方面存在異常，則需要學(xué)校的額外注意。因此文中根據(jù)馬氏距離的這一特點(diǎn)，認(rèn)為采用馬氏距離的MD-KNN算法更為適合學(xué)生數(shù)據(jù)分析。

2.2 學(xué)生在食堂就餐天數(shù)與就餐次數(shù)的分析

馬氏距離考慮了變量之間的相互聯(lián)系，文中分析這一設(shè)計(jì)思想，著重分析了貧困學(xué)生在學(xué)校食堂的就餐次數(shù)與就餐天數(shù)之間的聯(lián)系。通常而言，經(jīng)濟(jì)困難的在校大學(xué)生相比于經(jīng)濟(jì)富裕的在校大學(xué)生，其娛樂(lè)時(shí)間和消費(fèi)水平會(huì)較低。而很多大學(xué)食堂會(huì)有補(bǔ)助，食堂飯菜的價(jià)格會(huì)略低于學(xué)校外飯店的價(jià)格。因此，潛在的困難大學(xué)生的在校天數(shù)和在食堂就餐次數(shù)可能更多。文中根據(jù)在校學(xué)生在學(xué)校食堂刷卡產(chǎn)生的消費(fèi)記錄進(jìn)行分析，列出以下公式：

N=(X+Y)/Z

(2)

其中，X和Y分別表示午餐數(shù)和晚餐數(shù)，Z是根據(jù)該學(xué)生的就餐情況(午餐和晚餐)，推斷出的該學(xué)生在校天數(shù)，再乘以2得到的數(shù)字(該生在食堂應(yīng)該就餐次數(shù))。最終N越大說(shuō)明該學(xué)生在校天數(shù)以及食堂就餐數(shù)之間的比例高，該生在校食堂就餐的頻率高，也更有可能是經(jīng)濟(jì)較為困難的同學(xué)。理論上，X和Y可以為不超過(guò)在校天數(shù)任意大的整數(shù)，也可以為0。文中默認(rèn)設(shè)置每位學(xué)生每天只吃一頓午餐(晚餐)，即：某位學(xué)生在中午時(shí)段有多次刷卡記錄(比如分開(kāi)打菜和米飯)，文中也會(huì)將金額累計(jì)，認(rèn)為是一次消費(fèi)記錄。

圖1 學(xué)生在食堂就餐天數(shù)與就餐次數(shù)對(duì)比

根據(jù)式(2)，由每個(gè)學(xué)生在一段時(shí)間內(nèi)的就餐情況得到N值(有對(duì)應(yīng)的X+Y，Z)。所有學(xué)生消費(fèi)行為所對(duì)應(yīng)的點(diǎn)，都會(huì)落在陰影區(qū)域里，即：每個(gè)樣本點(diǎn)得到N值的最大值不會(huì)超過(guò)1，最小值不會(huì)小于0.5,(0.5≤N≤1)。如圖1所示，文中取一個(gè)分析區(qū)間為30天，則應(yīng)該就餐數(shù)目為60頓(午餐和晚餐)。可以分析這條線(xiàn)上的A、B兩點(diǎn)，A點(diǎn)是最理想狀態(tài)，該生在校30天，就餐60頓，N=1。而B(niǎo)點(diǎn)，該生就餐30次，在校30天，N=0.5，這名同學(xué)的情況很極端，他是每天只吃午餐或晚餐，連續(xù)30天(比如連續(xù)30天只吃午餐)，則也可以推導(dǎo)出其在校30天，但是N=0.5。如果一位同學(xué)連續(xù)多天均不在食堂消費(fèi)，則X與Y都會(huì)相應(yīng)減少，他的數(shù)據(jù)點(diǎn)會(huì)位于該陰影區(qū)域的左下角部分，趨向于0點(diǎn)。

再沿平行x軸方向分析線(xiàn)B，線(xiàn)B上有兩個(gè)點(diǎn)，B和C，這兩點(diǎn)都是就餐次數(shù)為30次，但是由于點(diǎn)B的行為，他的在校天數(shù)是點(diǎn)C的兩倍(點(diǎn)C的在校天數(shù)是15天)。但是分析推斷樣本B點(diǎn)學(xué)生的行為更有規(guī)律。通過(guò)進(jìn)一步的分析，推測(cè)在學(xué)校內(nèi)消費(fèi)次數(shù)越多和越平均的學(xué)生樣本更有可能是需要資助的貧困學(xué)生。當(dāng)加入早餐的因素時(shí)，圖1的變化如圖2所示。

圖2 學(xué)生在食堂就餐天數(shù)與就餐次數(shù)對(duì)比(含早餐)

此時(shí)Z的含義為：根據(jù)早中晚餐實(shí)際就餐次數(shù)推算出來(lái)的該生實(shí)際在校天數(shù)，再乘以3，得到的該生應(yīng)當(dāng)就餐次數(shù)。根據(jù)分析，經(jīng)濟(jì)困難的學(xué)生的數(shù)據(jù)點(diǎn)更有可能落在陰影區(qū)域的右上角區(qū)域范圍(所有學(xué)生的數(shù)據(jù)點(diǎn)都會(huì)集中在這個(gè)陰影三角形區(qū)域)，即貧困學(xué)生的在校食堂消費(fèi)次數(shù)更多，消費(fèi)天數(shù)更多，消費(fèi)次數(shù)也更均勻、更規(guī)律。

3 實(shí)驗(yàn)分析

文中搭建Eclipse+Tomcat實(shí)驗(yàn)環(huán)境，使用Java語(yǔ)言編程，以西安某高校2016和2017級(jí)碩士研究生，2012至2017級(jí)博士研究生在2017年11月至2018年4月(約180天)的學(xué)生行為數(shù)據(jù)(主要是食堂消費(fèi)數(shù)據(jù)、圖書(shū)館進(jìn)出信息、學(xué)習(xí)成績(jī)等數(shù)據(jù))進(jìn)行實(shí)驗(yàn)分析。其中男生7 636人(約占68.36%)，女生3 534人(約占31.64%)，共計(jì)11 170人。該高校有2個(gè)校區(qū)，A校區(qū)位于西安大唐西市附近，整體消費(fèi)水平較高；B校區(qū)位于郊區(qū)，物價(jià)相對(duì)較低；且該高校不同學(xué)院位于不同校區(qū)。在進(jìn)行數(shù)據(jù)分析時(shí)，將校區(qū)、學(xué)院等差異考慮在內(nèi)。針對(duì)所研究的問(wèn)題，設(shè)計(jì)了如下三個(gè)實(shí)驗(yàn)：(1)使用該校實(shí)際貧困生名單的實(shí)際生活消費(fèi)數(shù)據(jù)，對(duì)前述學(xué)生食堂就餐次數(shù)與在校天數(shù)的分析進(jìn)行相應(yīng)的驗(yàn)證；(2)使用MD-KNN算法，對(duì)該高校學(xué)生進(jìn)行貧困學(xué)生的篩選，然后比較與已有的，由人工認(rèn)定貧困學(xué)生的名單的差異；(3)為了更好地對(duì)比實(shí)驗(yàn)(2)和人工認(rèn)定貧困學(xué)生的名單，將這兩份名單中的學(xué)生進(jìn)行經(jīng)濟(jì)消費(fèi)水平的對(duì)比。

3.1 關(guān)于經(jīng)濟(jì)困難學(xué)生在食堂就餐次數(shù)、就餐天數(shù)的分析

通過(guò)分析，經(jīng)濟(jì)困難學(xué)生會(huì)更多地在校內(nèi)食堂就餐，因此其校內(nèi)食堂就餐次數(shù)與就餐天數(shù)會(huì)相對(duì)較高，獲得資助的同學(xué)其數(shù)據(jù)實(shí)驗(yàn)結(jié)果會(huì)落在圖1所示三角區(qū)域的右上角部分。文中通過(guò)采集西安某高校人工認(rèn)定的200多名貧困學(xué)生在2017年11月至2018年4月間，學(xué)校食堂的早餐、午餐、晚餐的就餐情況的數(shù)據(jù)進(jìn)行驗(yàn)證，結(jié)果如圖3所示。

圖3 貧困學(xué)生在食堂就餐天數(shù)與就餐次數(shù)對(duì)比圖

如圖3所示，該校人工篩選的貧困學(xué)生就餐情況是符合文中分析的，學(xué)生在食堂的就餐次數(shù)與就餐天數(shù)兩種因素與學(xué)生的貧困與否是一種正相關(guān)的條件，貧困學(xué)生相比于非貧困學(xué)生會(huì)在學(xué)校食堂就餐次數(shù)更多，這也為今后貧困學(xué)生資助工作提供了一種新的參考因素。

3.2 MD-KNN算法的實(shí)驗(yàn)分析

根據(jù)收集到的實(shí)驗(yàn)樣本數(shù)據(jù)，使用MD-KNN算法進(jìn)行分析，設(shè)置經(jīng)濟(jì)、消費(fèi)、學(xué)習(xí)、生源地、是否有生源地貧困證明、是否殘疾等二十余項(xiàng)標(biāo)簽，然后進(jìn)行迭代的實(shí)驗(yàn)分析。在得到初步的貧困學(xué)生名單后，再在結(jié)果中設(shè)置篩選學(xué)生名單條件，即：擬評(píng)選人數(shù)、助學(xué)金等級(jí)等，這樣就得到了由MD-KNN算法篩選推薦的貧困學(xué)生名單，篩選出的部分學(xué)生名單見(jiàn)表1。將由MD-KNN算法篩選得到的名單與實(shí)際人工審核推薦的學(xué)生名單進(jìn)行對(duì)比。兩份名單的匹配率大致在50%左右，這一概率并不算高，但分析原因可能有兩方面：(1)使用的MD-KNN算法或許還需要進(jìn)行改進(jìn)，以更好適應(yīng)高校貧困學(xué)生篩選的應(yīng)用環(huán)境；(2)人工篩選名單具有很大的不確定性，老師、學(xué)生很多情況下是通過(guò)申請(qǐng)表、平時(shí)的認(rèn)知(甚至并不認(rèn)識(shí))來(lái)進(jìn)行篩選推薦，人工篩選貧困學(xué)生也存在一些漏洞。因此通過(guò)實(shí)驗(yàn)3.3，對(duì)兩份名單中的學(xué)生進(jìn)行消費(fèi)情況的分析。

表1 MD-KNN算法篩選得到的經(jīng)濟(jì)困難學(xué)生名單(部分)

3.3 MD-KNN算法與線(xiàn)下人工篩選名單的對(duì)比

針對(duì)3.2節(jié)實(shí)驗(yàn)分析的結(jié)果，對(duì)兩份名單中的學(xué)生進(jìn)行進(jìn)一步的分析。還是以2017年11月至2018年4月之間的學(xué)生消費(fèi)數(shù)據(jù)來(lái)進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 日均消費(fèi)金額對(duì)比

通過(guò)對(duì)比發(fā)現(xiàn)，由文中篩選的學(xué)生名單的消費(fèi)水平(圖4)明顯低于由學(xué)校提供的，由實(shí)際人員參與評(píng)審所得到的貧困學(xué)生名單，這就說(shuō)明所設(shè)計(jì)的貧困學(xué)生篩選算法是有效的。雖然一些經(jīng)濟(jì)困難學(xué)生由于身體或疾病原因可能會(huì)有較高的消費(fèi)數(shù)據(jù)，但總體而言，大部分經(jīng)濟(jì)困難的學(xué)生在學(xué)生群體中的消費(fèi)數(shù)據(jù)應(yīng)該是較低的。因此，MD-KNN算法在篩選困難學(xué)生的過(guò)程中是一種有效的算法，并值得進(jìn)一步的分析研究。

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

學(xué)生群體是一個(gè)相似度較高的群體，具有很多共性，對(duì)學(xué)生群體進(jìn)行行為分析，篩選出應(yīng)該資助的貧困學(xué)生，是當(dāng)前很多高校的一項(xiàng)重要事務(wù)。通過(guò)分析MD-KNN的特性，將其應(yīng)用到貧困學(xué)生篩選資助的過(guò)程中，設(shè)置學(xué)生的屬性標(biāo)簽、消費(fèi)行為標(biāo)簽、學(xué)習(xí)行為標(biāo)簽(相同條件下最后考慮學(xué)習(xí)成績(jī))進(jìn)行篩選，發(fā)現(xiàn)與實(shí)際得到的貧困學(xué)生名單相比，通過(guò)MD-KNN算法篩選出來(lái)的學(xué)生名單消費(fèi)水平更低，有更高的精確度。同時(shí)發(fā)現(xiàn)，經(jīng)濟(jì)水平較低的學(xué)生的在校食堂消費(fèi)天數(shù)與消費(fèi)次數(shù)更高，以及學(xué)習(xí)成績(jī)與吃早餐次數(shù)具有正相關(guān)的關(guān)系。因此該研究是有效的，有助于貧困學(xué)生資助工作的發(fā)展。