加權(quán)k-means算法及其在高校貧困生判別中的應(yīng)用

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

一、引言

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

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

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

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

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

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

(1)

其中ck為簇Ck心點，計算方法為：

(2)

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

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

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

輸出:k個聚類中心點，k個劃分。

a)隨機選取k個樣本點作為初始的中心點。

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

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

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

e)輸出k個聚類中心點以及k個劃分。

三、改進k-means算法

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

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

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

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

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

(3)

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

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

(4)

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

(5)

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

(6)

(7)

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

Dens(xi)<α×AverDens(D)

(8)

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

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

(9)

即將點與集合的距離定義為點與集合中的點的最近距離。

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

算法2 本文算法

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

輸出:k個聚類中心點，k個劃分。

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

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

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

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

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

f)計算出當前聚類中心點，將孤立點集N中的點劃入與之距離最近的中心點所在的類簇中。

g)輸出k個聚類中心點以及k個劃分。

四、實驗結(jié)果分析

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

表1 聚類算法對比

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

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

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

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

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

表2 聚類屬性字段

通過多次試驗，當k為3時，聚類結(jié)果與貧困生資助比例更為貼切，且與學(xué)生真實消費情況擬合度更高。故采用k的值為3進行實驗。

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

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

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

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

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

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

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

表3 實驗結(jié)果驗證

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

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

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

五、結(jié)語

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

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

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

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