□張 軼 高雪冬 郭亞偉 趙丙賀

一、引言

黨中央、國(guó)務(wù)院高度重視家庭經(jīng)濟(jì)困難學(xué)生資助工作。尤其是黨的十八大以來(lái)，國(guó)家對(duì)高校貧困生的資助越來(lái)越多。不斷建立健全家庭經(jīng)濟(jì)困難學(xué)生資助政策體系，是實(shí)施科教興國(guó)和人才強(qiáng)國(guó)戰(zhàn)略，優(yōu)化教育結(jié)構(gòu)，促進(jìn)教育公平和社會(huì)公正的有效手段。目前，高校貧困生的判別方式為人工判別，并不存在統(tǒng)一標(biāo)準(zhǔn)，基本過(guò)程是首先由學(xué)生主動(dòng)填寫《高等學(xué)校學(xué)生及家庭情況調(diào)查表》，再出示相關(guān)困難證明，如《最低生活保障證》《特困證》等。其次，根據(jù)輔導(dǎo)員和班級(jí)內(nèi)部同宿舍室友組成判別小組進(jìn)行判別。這樣的判別方式難免存在信息錯(cuò)誤、虛假的問(wèn)題，造成貧困生判別與實(shí)際情況誤差較大。另外，由于一些同學(xué)自尊心等緣由，即便是家庭情況比較艱難但也不愿意去申報(bào)改善自己的生活條件。

大數(shù)據(jù)[1]時(shí)代的到來(lái)，學(xué)生消費(fèi)的財(cái)務(wù)狀況反映在生活中的方方面面，如日常使用校園卡就餐消費(fèi)，網(wǎng)購(gòu)次數(shù)以及金額，奢侈品使用情況等。如果對(duì)這些數(shù)據(jù)進(jìn)行分析和挖掘，將有助于分析和識(shí)別貧困生。但是當(dāng)前存在諸多方法，如分類方法[2～3]和概念漂移檢測(cè)的方法[4]，這些方法需要預(yù)先標(biāo)定大量訓(xùn)練數(shù)據(jù)，然后訓(xùn)練出分類器，最后才能實(shí)現(xiàn)對(duì)其他數(shù)據(jù)進(jìn)行分類。對(duì)于貧困生判別問(wèn)題而言，預(yù)先獲得大量標(biāo)注數(shù)據(jù)難度較大，因此分類方法不適宜求解本文問(wèn)題。序列模式挖掘方法[5]是數(shù)據(jù)挖掘中一類重要的分析方法[6～7]，可以通過(guò)挖掘負(fù)序列的行為特征[8]，進(jìn)而實(shí)現(xiàn)負(fù)樣本識(shí)別。然而這同樣需要預(yù)先標(biāo)定大量數(shù)據(jù)，因而難以取得良好的效果。

聚類分析作為一種無(wú)監(jiān)督學(xué)習(xí)方法[9]，無(wú)需預(yù)先標(biāo)定數(shù)據(jù)，是數(shù)據(jù)挖掘[10]中常用的方法之一。k-means作為最常用的基于劃分的聚類算法，具有原理簡(jiǎn)單、收斂速度快、能有效處理大量數(shù)據(jù)等優(yōu)點(diǎn)。但其也存在一些問(wèn)題，如：算法對(duì)初始中心點(diǎn)的選取較為敏感，當(dāng)初始中心點(diǎn)選取不合理時(shí)，算法容易陷入局部最優(yōu)解；k值需要人為給定；算法沒(méi)有考慮樣本各維特征的權(quán)重。針對(duì)以上問(wèn)題，已有學(xué)者提出了一系列的改進(jìn)。汪中等人[11]提出基于密度的初始中心點(diǎn)選取方法，但在密度分布較為均勻的數(shù)據(jù)集中效果不佳。郭靖[12]提出基于變異系數(shù)的加權(quán)歐式距離方法，從而提高了聚類精度，但穩(wěn)定度不佳。Xiong等人[13]提出基于平均密度與最遠(yuǎn)距離的初始中心點(diǎn)選取方法，有效提高了聚類穩(wěn)定度，但聚類精度不高。這些研究或存在迭代收斂速度慢，聚類結(jié)果不穩(wěn)定，或存在聚類精度不高等問(wèn)題。

為了增加聚類的穩(wěn)定度，提高聚類結(jié)果的精度，本文采用將基于變異系數(shù)的加權(quán)權(quán)重與基于平均密度與最遠(yuǎn)距離的初始中心點(diǎn)選取算法結(jié)合，形成基于平均密度與最遠(yuǎn)距離的變異加權(quán)k-means算法(以下簡(jiǎn)稱DDCVK-means算法)。將改進(jìn)后的算法應(yīng)用在UCI標(biāo)準(zhǔn)數(shù)據(jù)集中多種數(shù)據(jù)集上進(jìn)行聚類，實(shí)驗(yàn)結(jié)果表明，本文算法無(wú)論是精確度還是聚類穩(wěn)定度，都有了一定程度的提高，從而驗(yàn)證了本文方法的有效性，進(jìn)而實(shí)現(xiàn)了貧困生判別。

二、傳統(tǒng)k-means算法

傳統(tǒng)的k-means聚類算法是基于劃分的聚類算法，給定樣本集D={X1,X2,…,Xm}，k-means的任務(wù)是將樣本集D中的樣本劃分為k個(gè)不相交的類簇，使類內(nèi)間距盡可能小，類間間距盡可能大，從而使所得的劃分的誤差平方和SSE(sum of squared errors)最小化。假設(shè)聚類分析后產(chǎn)生的類別集合為C={C1,C2,…,Ck}，則SSE定義如下：

(1)

其中ck為簇Ck心點(diǎn)，計(jì)算方法為：

(2)

k-means算法的任務(wù)是找到能最小化SSE的聚類結(jié)果，這是一個(gè)NP難問(wèn)題[14]。k-means算法[15]的基本流程為：

算法1 傳統(tǒng)k-means算法

輸入:樣本集D，聚類個(gè)數(shù)k。

輸出:k個(gè)聚類中心點(diǎn)，k個(gè)劃分。

a)隨機(jī)選取k個(gè)樣本點(diǎn)作為初始的中心點(diǎn)。

b)計(jì)算每個(gè)樣本點(diǎn)與各個(gè)中心點(diǎn)之間的距離，將該點(diǎn)并入到與其距離最近的中心點(diǎn)所屬的類簇中。

c)根據(jù)公式(2)更新各類簇的中心點(diǎn)。

d)重復(fù)(2)，(3)兩步，直至中心點(diǎn)不再發(fā)生變化或者達(dá)到指定的迭代次數(shù)。

e)輸出k個(gè)聚類中心點(diǎn)以及k個(gè)劃分。

三、改進(jìn)k-means算法

本文算法在前人的基礎(chǔ)上進(jìn)行研究改進(jìn)，提出DDCVK-means算法。該算法分三個(gè)階段，第一個(gè)階段是計(jì)算各個(gè)特征的權(quán)重；第二個(gè)階段是確定初始聚類中心；第三個(gè)階段是聚類過(guò)程，并對(duì)孤立點(diǎn)做出處理。設(shè)樣本數(shù)據(jù)集為X={xi|xi∈Rp,i=1,2,…,n}，p是維數(shù)，wj為各維特征權(quán)重。

(一)特征的權(quán)重。在特征權(quán)重計(jì)算階段，本文采用基于變異系數(shù)的歐式距離實(shí)現(xiàn)特征加權(quán)。

在統(tǒng)計(jì)學(xué)中，用來(lái)描述數(shù)據(jù)離散程度的指標(biāo)有：標(biāo)準(zhǔn)差(Standard Deviation)，方差(Variance)，變異系數(shù)(Coefficient of Variation)，平均絕對(duì)偏差(Mean Absolute Deviation)。文獻(xiàn)[12]所做的研究指出，變異系數(shù)不但能反映數(shù)據(jù)的離散程度，還能消除測(cè)量尺度和量綱的影響，故采用變異系數(shù)作為加權(quán)系數(shù)。

變異系數(shù)(Coefficient of Variation)的定義為標(biāo)準(zhǔn)差與平均數(shù)的比。定義樣本中各維特征加權(quán)系數(shù)為w1,w2,…,wj為樣本數(shù)據(jù)維度)。

則加權(quán)系數(shù)為:

(3)

(二)初始聚類中心。在確定初始聚類中心階段，本文采用基于平均密度與最遠(yuǎn)距離的選取方法實(shí)現(xiàn)初始聚類中心點(diǎn)的選取。

初始中心點(diǎn)選取首先需要計(jì)算所有樣本點(diǎn)兩兩之間的加權(quán)歐式距離，本文采用加權(quán)歐式距離進(jìn)行計(jì)算，其計(jì)算公式如下：

(4)

然后根據(jù)公式(5)計(jì)算出平均距離。

(5)

再根據(jù)公式(6)計(jì)算出所有樣本點(diǎn)的密度參數(shù)。

(6)

(7)

求得平均密度后，便可根據(jù)孤立點(diǎn)的判定方法，將樣本集中滿足不等式(8)的樣本點(diǎn)放入孤立點(diǎn)集N中。

Dens(xi)<α×AverDens(D)

(8)

在除去孤立點(diǎn)的樣本集S中，選取密度最大的點(diǎn)作為第一個(gè)初始聚類中心，然后在大于平均密度β倍的點(diǎn)集中選取距離初始聚類中心點(diǎn)集最遠(yuǎn)的點(diǎn)作為下一個(gè)聚類中心，劃入初始聚類中心點(diǎn)集合。點(diǎn)xi合的距離如公式(9)所示：

d(xi,C)=min(d(xi,xj),xj∈C)

(9)

即將點(diǎn)與集合的距離定義為點(diǎn)與集合中的點(diǎn)的最近距離。

(三)本文算法描述。與傳統(tǒng)k-means算法相比，本算法先計(jì)算了各維特征的權(quán)重，在后續(xù)的過(guò)程中所有的距離計(jì)算上均使用加權(quán)的歐式距離，改進(jìn)了傳統(tǒng)k-means算法權(quán)重相同這一不足；之后通過(guò)計(jì)算得出初始中心點(diǎn)，改進(jìn)了傳統(tǒng)k-means算法的不穩(wěn)定性這一不足；算法還對(duì)孤立點(diǎn)進(jìn)行處理，有效減小了孤立點(diǎn)對(duì)聚類結(jié)果的影響，最后將孤立點(diǎn)劃入最近的類簇中，得出最終劃分。綜合以上過(guò)程，下面給出本文算法描述：

算法2 本文算法

輸入:樣本集D，聚類個(gè)數(shù)k，參數(shù)α，參數(shù)β。

輸出:k個(gè)聚類中心點(diǎn)，k個(gè)劃分。

a)根據(jù)3.1節(jié)的內(nèi)容計(jì)算各維特征的權(quán)重。

b)根據(jù)3.2節(jié)的內(nèi)容計(jì)算出k個(gè)初始聚類中心、孤立點(diǎn)集N和除去孤立點(diǎn)的樣本集S。

c)根據(jù)加權(quán)歐式距離公式(4)計(jì)算樣本S中每個(gè)樣本點(diǎn)與各個(gè)中心點(diǎn)之間的距離，將該點(diǎn)并入到與其距離最近的中心點(diǎn)所屬的類簇中。

d)根據(jù)公式(2)更新各類簇的中心點(diǎn)。

e)重復(fù)c)，d)兩步，直至中心點(diǎn)不再發(fā)生變化或者達(dá)到指定的迭代次數(shù)。

f)計(jì)算出當(dāng)前聚類中心點(diǎn)，將孤立點(diǎn)集N中的點(diǎn)劃入與之距離最近的中心點(diǎn)所在的類簇中。

g)輸出k個(gè)聚類中心點(diǎn)以及k個(gè)劃分。

四、實(shí)驗(yàn)結(jié)果分析

(一)標(biāo)準(zhǔn)數(shù)據(jù)集驗(yàn)證與分析。本文將文獻(xiàn)[13]中的算法稱為DDK-means，將文獻(xiàn)[12]中的算法稱為CVK-means算法。為了驗(yàn)證本文DDCVK-means算法的性能，我們選取了傳統(tǒng)k-means算法、k-means++算法、DDK-means算法和CVK-means算法進(jìn)行對(duì)比，實(shí)驗(yàn)數(shù)據(jù)選取了UCI中的Iris、Seeds、Wine、Vertebral Column和Wholesale Customers數(shù)據(jù)集。表1給出了本文算法及對(duì)比算法在五個(gè)數(shù)據(jù)集下執(zhí)行若干次的最高精確度、最低精確度和平均精確度。

表1 聚類算法對(duì)比

從表1可以看出，除了本文提出的算法，其他的聚類算法在精度或穩(wěn)定度上都稍有欠缺；例如k-means算法在Iris數(shù)據(jù)集平均準(zhǔn)確率僅為81.44%，而這是所有算法中聚類效果最差的，其他四種數(shù)據(jù)集也有類似現(xiàn)象，造成這樣現(xiàn)象的原因是傳統(tǒng)k-means算法聚類中心點(diǎn)的選取方式為隨機(jī)選取，受孤立點(diǎn)的影響較大，容易陷入局部最優(yōu)解，且樣本各維特征權(quán)重相同；改進(jìn)的k-means++算法在五種數(shù)據(jù)集上的平均精度與最高精度非常接進(jìn)，說(shuō)明其穩(wěn)定度大有提高，但由于其存在隨機(jī)因素，所以仍然存在不穩(wěn)定現(xiàn)象，且精度不高；CVK-means算法在五種數(shù)據(jù)集上的最高精度都有了一定程度的提高，在Iris數(shù)據(jù)集上的最高精度達(dá)到了96%，但因?yàn)槠涑跏季垲愔行狞c(diǎn)的選取為隨機(jī)選取，故造成最低精度只有50.67%的現(xiàn)象，穩(wěn)定度差；DDK-means算法通過(guò)計(jì)算獲得初始中心點(diǎn)，故聚類結(jié)果相同，穩(wěn)定度好，但是相同的權(quán)重使得其精度不高。本文DDCVK-means算法取得了最好的效果。由于本文算法是計(jì)算產(chǎn)生初始聚類中心，而非隨機(jī)生成初始聚類中心，因此本文算法聚類結(jié)果是穩(wěn)定不變的。更為重要的是，從表1可以看出，本文算法聚類效果最好，例如在Iris數(shù)據(jù)集上，本文算法的平均準(zhǔn)確率取得了96.00%的效果，這是優(yōu)于其他所有方法的，并且其他四種數(shù)據(jù)集均呈現(xiàn)同樣的結(jié)果。造成這樣現(xiàn)象的原因是本文算法結(jié)合了DDK-means算法和CVK-means算法的優(yōu)點(diǎn)，具有較高的聚類精度和穩(wěn)定度。

(二)貧困學(xué)生識(shí)別結(jié)果與分析。使用DDCVK-means算法，選取某大學(xué)的學(xué)生為樣本進(jìn)行實(shí)驗(yàn)。

圖1 當(dāng)前學(xué)生經(jīng)濟(jì)情況

1.當(dāng)前貧困生現(xiàn)狀。首先對(duì)數(shù)據(jù)進(jìn)行抓取以及預(yù)處理，即從現(xiàn)有數(shù)據(jù)庫(kù)找到樣本學(xué)生在校期間的消費(fèi)情況，主要包括在食堂消費(fèi)的次數(shù)以及單次金額。圖1展現(xiàn)的是樣本學(xué)生當(dāng)前平均消費(fèi)金額，消費(fèi)次數(shù)與登記在貧困生庫(kù)中學(xué)生的貧困程度散點(diǎn)圖。圖中“+”代表家庭經(jīng)濟(jì)條件正常的學(xué)生，“×”代表家庭經(jīng)濟(jì)條件困難的學(xué)生，其中綠色為一般貧困、藍(lán)色為貧困、黃色為特殊貧困。從圖上這些散點(diǎn)來(lái)看，學(xué)生的分布較為雜亂，不同貧困程度的學(xué)生的分布與其在食堂消費(fèi)的次數(shù)和平均金額關(guān)系不明顯，表明當(dāng)前的貧困生很有可能存在假貧困。樣本數(shù)據(jù)也沒(méi)有明顯的分簇，用傳統(tǒng)的k-means算法很有可能會(huì)陷入局部最優(yōu)解，聚類精度不高等問(wèn)題中。

2.聚類結(jié)果。綜合考慮學(xué)生的消費(fèi)能力和學(xué)習(xí)成績(jī)，最終使用如下屬性字段進(jìn)行聚類。

表2 聚類屬性字段

通過(guò)多次試驗(yàn)，當(dāng)k為3時(shí)，聚類結(jié)果與貧困生資助比例更為貼切，且與學(xué)生真實(shí)消費(fèi)情況擬合度更高。故采用k的值為3進(jìn)行實(shí)驗(yàn)。

聚類后得到如圖2的結(jié)果。

圖2 基于消費(fèi)數(shù)據(jù)的聚類結(jié)果

據(jù)經(jīng)驗(yàn)數(shù)據(jù)將類1劃分為貧困學(xué)生；類2平均消費(fèi)金額較高，且在食堂消費(fèi)次數(shù)少，故將類2劃分為富裕學(xué)生，類3為一般學(xué)生。

為了驗(yàn)證平均消費(fèi)金額-消費(fèi)次數(shù)可以有效地用于識(shí)別貧困情況，而其他數(shù)據(jù)難以正確識(shí)別家庭情況是否貧困問(wèn)題，為此我們又選擇了專業(yè)排名比率-GPA信息。如圖3所示。

圖3 基于GPA數(shù)據(jù)的聚類結(jié)果

圖3中類1貧困學(xué)生，類2富裕學(xué)生和類3一般學(xué)生混合分布，發(fā)現(xiàn)學(xué)生成績(jī)和家庭貧困情況并無(wú)明顯相關(guān)性，故學(xué)習(xí)成績(jī)并不能反映學(xué)生家庭貧困狀況，更多的還是由學(xué)生的消費(fèi)水平直接反映。

3.結(jié)果分析。實(shí)驗(yàn)隨機(jī)選取10名學(xué)生，通過(guò)當(dāng)面交談，咨詢監(jiān)護(hù)人，咨詢室友等方式調(diào)查其家庭經(jīng)濟(jì)的真實(shí)狀況，并與聚類結(jié)果以及當(dāng)前記錄在貧困生庫(kù)的情況進(jìn)行對(duì)比，對(duì)比結(jié)果見表3。

表3 實(shí)驗(yàn)結(jié)果驗(yàn)證

聚類結(jié)果將學(xué)生分為3類：貧困、一般、富裕。而貧困生又分為3類：一般貧困、貧困和特殊貧困。故三類貧困生都應(yīng)在聚類所得到的貧困類簇中，也就是類1中。忽略不同貧困等級(jí)的區(qū)別，10個(gè)學(xué)生中真實(shí)貧困狀況和記錄在貧困生庫(kù)中的情況不符的有學(xué)生1、2、9。而真實(shí)貧困情況和聚類結(jié)果不符的僅有學(xué)生7。

實(shí)驗(yàn)表明聚類結(jié)果能將家庭貧困的學(xué)生較好地區(qū)分出來(lái)，通過(guò)隨機(jī)調(diào)查的結(jié)果顯示聚類算法的準(zhǔn)確度大約為90%。實(shí)驗(yàn)誤差可能是由于部分貧困生是在外實(shí)習(xí)無(wú)法進(jìn)入食堂點(diǎn)餐、學(xué)校周邊小吃店或外賣價(jià)格較低、自身生活習(xí)慣、體重等因素造成。而現(xiàn)有的貧困生庫(kù)中不符合實(shí)際情況的信息大約為30%，不符合情況較為嚴(yán)重，一方面可能是因?yàn)榇嬖谔摷偕陥?bào)，另一方面可能是部分富裕家庭孩子由于平時(shí)生活比較節(jié)儉，錯(cuò)被認(rèn)為是貧困家庭。若評(píng)選貧困生時(shí)使用本實(shí)驗(yàn)所提供的方法作為參考，則可提高貧困生判別精準(zhǔn)度。

因此，根據(jù)研究統(tǒng)計(jì)和分析結(jié)果，推測(cè)出識(shí)別貧困生的兩個(gè)步驟：第一，經(jīng)過(guò)算法識(shí)別滿足兩種消費(fèi)特征，即不僅每月在食堂的就餐次數(shù)高，而且平均消費(fèi)低。第二，在通過(guò)算法識(shí)別貧困生后，為進(jìn)一步提高準(zhǔn)確性，需要通過(guò)得到周圍人的證明確認(rèn)。

五、結(jié)語(yǔ)

研究通過(guò)改進(jìn)后的算法，基本能達(dá)到提高識(shí)別貧困生的準(zhǔn)確率目的。具體而言，文中針對(duì)傳統(tǒng)k-means對(duì)聚類中心點(diǎn)敏感，樣本各維特征權(quán)重相同這兩點(diǎn)進(jìn)行改進(jìn)，結(jié)合基于平均密度與最遠(yuǎn)距離的初始聚類中心點(diǎn)選取方法和基于變異系數(shù)的加權(quán)方法提出了DDCVK-means算法。并將本文算法與多種算法進(jìn)行對(duì)比，結(jié)果顯示本文DDCVK-means算法提高了聚類精度和穩(wěn)定度。

以高校學(xué)生校園食堂消費(fèi)數(shù)據(jù)為基礎(chǔ)，本文研究了如何根據(jù)適當(dāng)?shù)呐袛鄻?biāo)準(zhǔn)通過(guò)算法識(shí)別進(jìn)而識(shí)別、確認(rèn)貧困生名單以及在貧困生中找出假貧困生的辦法，并且提出了采用加權(quán)k-means算法應(yīng)用于貧困生識(shí)別的新思路。在研究過(guò)程中，通過(guò)判別貧困生以及識(shí)別貧困生等級(jí)，發(fā)現(xiàn)了貧困生在消費(fèi)行為上較為鮮明的特點(diǎn)。比如一些學(xué)生為了省午飯費(fèi)用，會(huì)在早上多買一些食物；在校外的消費(fèi)費(fèi)用比在校內(nèi)更低；幾乎很少消費(fèi)含蛋白質(zhì)較高的魚肉類以及補(bǔ)充維生素的水果類。這類同學(xué)往往對(duì)伙食費(fèi)控制得非常嚴(yán)格，長(zhǎng)期以來(lái)，很可能對(duì)同學(xué)的身體發(fā)育、心理健康、學(xué)業(yè)成就等都產(chǎn)生不良影響。因此，學(xué)?？梢远ㄆ谕ㄟ^(guò)算法估算來(lái)對(duì)這些同學(xué)實(shí)施經(jīng)濟(jì)補(bǔ)助，進(jìn)而引導(dǎo)他們逐步改變消費(fèi)習(xí)慣。

對(duì)比傳統(tǒng)的人工判別以及傳統(tǒng)k-means算法，改進(jìn)后的算法能夠更有效應(yīng)用于貧困生判別上，通過(guò)對(duì)校園卡日常消費(fèi)數(shù)據(jù)進(jìn)行聚類，分析學(xué)生的貧困程度，極大縮小了學(xué)校調(diào)查認(rèn)證的工作量，維護(hù)了貧困同學(xué)的自尊心，并且能夠幫助到一批由于自尊心或面子問(wèn)題不愿申請(qǐng)的貧困同學(xué)，最終達(dá)到輔助學(xué)?？茖W(xué)公平地進(jìn)行貧困生資助工作的目的。

在本文的算法中，盡管對(duì)數(shù)據(jù)各維特征進(jìn)行變異系數(shù)加權(quán)會(huì)使聚類結(jié)果精確度提高，但由于高校貧困生認(rèn)定是一個(gè)龐大的系統(tǒng)工作，因而可能并不適用于所有樣本數(shù)據(jù)，在今后的工作中，將對(duì)加權(quán)算法做進(jìn)一步研究，大量采集多維度、多方面的高質(zhì)量數(shù)據(jù)，以期望獲得更適用的樣本數(shù)據(jù)，從而適用更恰當(dāng)?shù)目茖W(xué)評(píng)判方法，讓更多真正需要資助的大學(xué)生享受到資助政策的利益。