改進kmeans算法在學生消費畫像中的應用

凌玉龍，張 曉，李 霞，張 勇

(1.西北工業(yè)大學 大數(shù)據(jù)存儲與管理工信部重點實驗室，陜西 西安 710129； 2.西北工業(yè)大學 學生資助服務中心，陜西 西安 710129)

0 引 言

學生群體肩負著祖國的未來，在社會中扮演著重要的角色，因此對學生的行為進行分析具有重大意義。數(shù)據(jù)挖掘作為一種從海量數(shù)據(jù)中獲取潛在知識的技術，已經(jīng)在各個領域取得廣泛應用。采用數(shù)據(jù)挖掘技術挖掘?qū)W生消費數(shù)據(jù)中潛在的知識可以充分發(fā)揮現(xiàn)有消費數(shù)據(jù)的作用，為學校管理人員的決策提供數(shù)據(jù)支持。

作為最經(jīng)典的數(shù)據(jù)挖掘算法之一，kmeans算法思想簡單，易于實現(xiàn)，有著廣泛的應用。隨著社會的發(fā)展，出現(xiàn)了一系列使用傳統(tǒng)kmeans算法難以解決的新問題和新場景，學術界針對傳統(tǒng)kmeans算法不斷進行改進以適應這些場景。例如，謝修娟[1]為了從微博數(shù)據(jù)中發(fā)現(xiàn)熱點輿情，提出一種基于密度的初始聚類中心選擇算法，改進算法在微博數(shù)據(jù)集上擁有更高的準確性和穩(wěn)定性。馬漢達[2]針對傳統(tǒng)kmeans在Web日志挖掘中性能不高的缺點，提出了基于粒子群算法的改進kmeans算法,并在Hadoop上實現(xiàn)了并行化，實驗證明改進算法不僅提高了聚類準確率，而且提升了運行效率。Lutz[3]為了解決kmeans算法在GPU上效能較低的問題，針對kmeans算法每次迭代計算質(zhì)心的過程提出了一種新的算法來更新質(zhì)心，改進后的kmeans算法提高了20%的吞吐量。

如何利用校園消費數(shù)據(jù)分析學生群體行為，實現(xiàn)貧困生精確資助，提高學生學習生活質(zhì)量，保障學生安全，已經(jīng)成為高校急需解決的問題。隨著數(shù)據(jù)挖掘技術的發(fā)展，很多研究人員嘗試將數(shù)據(jù)挖掘技術與學生行為分析相結合[4-13]，其中黃剛[14]和姜楠[15]的研究具有一定的代表性。這兩位學者在學生校園消費數(shù)據(jù)集上采用kmeans算法對學生進行聚類，分析學生的消費習慣和群體特征，并進行了畫像說明，為高校學生管理工作提供依據(jù)。但是他們的研究僅是將kmeans算法引入到學生行為分析領域，沒有考慮學生消費數(shù)據(jù)集本身的特點和kmeans算法隨機選擇初始聚類中心的缺點。

文中根據(jù)學生消費數(shù)據(jù)集的特點和kmeans算法隨機選擇初始聚類中心的不足，提出一種基于馬氏距離和密度的改進kmeans算法，并將其應用于西安某高校的校園一卡通消費數(shù)據(jù)集上，對學生群體行為進行分析并構建消費畫像，從大數(shù)據(jù)的角度探究了學生行為，同時推動了貧困生精準資助領域的發(fā)展。

1 理論介紹

本節(jié)分析了學生消費數(shù)據(jù)集的特點和kmeans算法選擇隨機初始聚類中心的不足，針對kmeans算法提出兩點改進以更好地適用于學生群體聚類場景。

1.1 歐氏距離和馬氏距離

經(jīng)典的kmeans算法采用歐氏距離計算樣本之間的距離，歐氏距離單純考慮數(shù)值上的距離，忽略了數(shù)據(jù)屬性之間的依賴性，將數(shù)據(jù)各個屬性之間的差別同等看待。但是大部分實際場景中的數(shù)據(jù)屬性之間并不是獨立的，各個屬性起到的作用也各不相同。

馬氏距離是歐氏距離的一種修正，其修正了歐氏距離中各個屬性尺度不一致且相關的問題。馬氏距離認為屬性之間是存在聯(lián)系的，所以在計算公式中引入了協(xié)方差。對于一個多變量向量x=(x1,x2,…,xp)T，設其均值為μ=(μ1,μ2,…,μp)T，協(xié)方差矩陣為Σ，則其馬氏距離定義為：

(1)

其中，T表示矩陣的轉(zhuǎn)置。如果數(shù)據(jù)之間獨立同分布，那么對應的協(xié)方差矩陣就變成了單位陣，在這種情況下馬氏距離就變成了歐氏距離。

馬氏距離由于其設計思想會將某一微小變量的作用放大，這在某些應用場景中可能會導致結果的過擬合。但是不同于其他應用場景下的數(shù)據(jù)，學生群體是一個具有高度相似性的群體，由于課業(yè)的安排和學校的規(guī)章制度，大部分學生的生活作息規(guī)律極其相似，學生的就餐時間、就餐地點、消費情況相對固定且有規(guī)律，不同學生的行為相差較小。由于學生消費數(shù)據(jù)的特點和馬氏距離的特點，該文認為采用馬氏距離代替歐氏距離的kmeans算法更適合對學生消費數(shù)據(jù)進行聚類分析。

1.2 初始聚類中心的選擇

kmeans算法是從樣本集合中隨機選擇k個樣本作為初始聚類中心，這種初始化聚類中心的思想沒有考慮到數(shù)據(jù)的分布情況和離群樣本點的影響，很可能會產(chǎn)生較差的聚類結果。雖然隨機選擇初始聚類中心的kmeans算法的聚類效果可能不好，但是無論初始聚類中心怎么選擇，經(jīng)過一系列迭代后得到的最終聚類中心的周邊的點都是高密度點，即這些聚類中心周邊的點都比較密集，不會存在離群樣本點。

文中選擇初始聚類中心的改進思想為：在高密度樣本集上應用最小最大原則得到k個樣本作為初始聚類中心。具體步驟如下：

(1)運行一次kmeans算法，得到k個聚類中心；

(2)選擇與k個聚類中心距離最近的一定比例(記為percent)的樣本作為高密度樣本集；

(3)從高密度樣本集中隨機選擇一個樣本作為第一個初始聚類中心；

(4)從剩下的高密度樣本集中選擇距離已有的初始聚類中心最遠的樣本作為第2個初始聚類中心；

(5)重復執(zhí)行步驟(4)直到初始聚類中心中包含k個樣本。

上述步驟中percent的值過大會引入噪聲樣本點，過小又會使得高密度樣本集中樣本數(shù)據(jù)過少。經(jīng)過綜合考慮，文中設置percent為20%。這個參數(shù)并不是固定不變的，可以根據(jù)數(shù)據(jù)集的具體情況進行調(diào)整。

在高密度數(shù)據(jù)集上應用最小最大原則得到的k個初始聚類中心，既考慮到了數(shù)據(jù)的分布情況，又可以避免離群樣本點的干擾。文中基于上述兩點改進思想實現(xiàn)了改進的kmeans算法(記做Improve-Kmeans算法)，并將其應用于學生消費數(shù)據(jù)集，以更好地描述學生群體的共性與特性。

2 實驗分析

2.1 實驗環(huán)境與數(shù)據(jù)

文中以西安某高校2019年03月—2019年06月的17、18級碩士研究生的一卡通消費數(shù)據(jù)作為樣本集，原始數(shù)據(jù)由學校信息中心提供，其格式如表1所示。

表1 一卡通消費數(shù)據(jù)集(部分)

原始的一卡通消費數(shù)據(jù)集中不僅包含所有學生的一卡通消費記錄，還包含部分教職工及學校管理人員的數(shù)據(jù)，這些數(shù)據(jù)屬于噪聲數(shù)據(jù)，分析這些噪聲數(shù)據(jù)會對挖掘結果產(chǎn)生一定程度的影響。因此，文中的首要工作就是從原始數(shù)據(jù)集中去除噪聲數(shù)據(jù)(在校學生之外的所有其他人的消費數(shù)據(jù))。

一卡通消費數(shù)據(jù)集中只記錄著每一次消費的記錄，對單一記錄進行分析無法得出有用的結論，只有根據(jù)具體需求構建合適的特征后才能應用于聚類算法中，使數(shù)據(jù)挖掘更有針對性，從而提高算法性能。

為了全面刻畫學生的特點，文中從多個角度分層提取了學生消費特征。表2展示了這些特征的基本信息。

表2 學生消費特征

2.2 實驗方法

為了確定Improve-Kmeans算法中k的取值，通過對處理后的學生消費數(shù)據(jù)集進行k=1到8的聚類實驗，得到k在不同取值下聚類結果的誤差平方和(sum of the squared errors，SSE)，具體步驟如下：

(1)設k=1，運行Improve-Kmeans算法；

(2)記錄k=1下得到的各個聚類中心及樣本所屬的類別；

(3)按照公式(2)計算組內(nèi)方差SSE，并記錄；

(4)設k=2到8，重復執(zhí)行步驟(1)～步驟(3)。

(2)

式中，ci是聚類結果中的第i個類，p是ci中的樣本點，mi是ci的聚類中心(即ci中所有樣本的均值)。

實驗結果如圖1所示。

圖1 不同k值下聚類結果的SSE

從圖1中可以看到，隨著k值的增大，SSE逐漸減小，且在k=3時SSE的減小幅度開始減緩，這表明最佳聚類數(shù)為3。

為了減少實驗誤差，文中運行Improve-Kmeans算法16次，每次聚類得到的SSE和輪廓系數(shù)見表3。從表中可以看出，在第11次實驗時，SSE值最小且輪廓系數(shù)最大，因此文中選擇該次實驗結果得到的學生群體畫像進行分析。

表3 16次實驗的SSE和輪廓系數(shù)

文中設計了兩個實驗：

(1)使用Improve-Kmeans算法對學生刻畫群體消費畫像，并對畫像進行解釋分析，應用畫像的結果為學校管理人員提供決策支持；

(2)將Improve-Kmeans算法得到的貧困生數(shù)據(jù)與學校線下認定的貧困生數(shù)據(jù)進行對比分析，以輔助高校精準資助活動。

2.3 學生群體消費畫像

文中從三個角度：(1)3個類的聚類中心點；(2)3類學生對應的原始數(shù)據(jù)的平均值；(3)3類學生對應的原始數(shù)據(jù)的分布情況，分析學生群體的消費特征。

表4列出了第I、II、III類學生群體的聚類中心點，圖2描述了3類學生群體對應的原始數(shù)據(jù)的平均值，圖3描述了3類學生群體對應的原始數(shù)據(jù)的分布情況。

表4 學生群體聚類中心

圖2 3類學生的原始消費數(shù)據(jù)的平均值

圖3 3類學生的原始消費數(shù)據(jù)的分布

從圖2中可以看出，對于第I類群體，其午餐平均消費、晚餐平均消費明顯比第III類群體低，同時比第II類群體高，說明其消費水平在三類群體中居中。其食堂消費天數(shù)接近第III類群體且明顯高于第II類群體，說明這類學生頻繁在食堂就餐。其午晚餐差額比例明顯低于第II類群體，說明這類學生的飲食比較規(guī)律。周內(nèi)在校天數(shù)和周末在校天數(shù)接近第III類群體且明顯高于第II類群體，說明這類學生經(jīng)常在校。早起次數(shù)比例接近第II類群體且明顯低于第II類群體，說明這類學生同樣很少早起，屬于懶癌患者。綜上分析，第I類學生符合大部分正常學生的消費情況。

對于第II類群體，其午餐平均消費、晚餐平均消費明顯比第I和III類群體高，說明其消費水平是三類群體中最高的。其食堂消費天數(shù)最低且明顯低于其他兩類群體，說明這類學生很少在食堂吃飯。其午晚餐差額比例最高且明顯高于其他兩類群體，說明這類學生經(jīng)常性的只吃單餐，飲食不規(guī)律，很可能是經(jīng)常點外賣。周內(nèi)在校天數(shù)和周末在校天數(shù)最低且明顯低于其他兩類學生，說明這類學生喜歡經(jīng)常離校。早起次數(shù)比例最低，且明顯低于第III類群體，說明這類學生很少早起。綜上分析，第II類學生符合小富群體的行為特點。

對于第III類群體，其午餐平均消費、晚餐平均消費最低且明顯比第I和II類群體低，說明其消費水平是三類群體中最低的。其食堂消費天數(shù)最高且明顯高于其他兩類群體，說明這類學生是最頻繁在食堂就餐的學生。其午晚餐差額比例接近第I類群體且明顯低于第II類群體，說明這類學生的飲食比較規(guī)律，午晚餐消費次數(shù)基本上相同。周內(nèi)在校天數(shù)和周末在校天數(shù)最高且明顯高于第II類群體，說明這類學生是最常在校的學生。早起次數(shù)比例最高且明顯高于其他兩類群體，說明這類學生擁有早起的好習慣。綜上分析，第III類學生符合貧困生群體的行為特點。

表4中的“所屬類包含的樣本數(shù)量”列的結果也能驗證學生群體分類結果。第III類貧困生群體共415人，占總人數(shù)的7.64%，符合該校研究生中的貧困生數(shù)量和比例，第I類普通學生群體共4 133人，占總人數(shù)的76.16%，基本上也符合現(xiàn)實情況。

圖3是3類學生群體在消費特征上對應數(shù)據(jù)的箱型圖，橫坐標代表學生群體，縱坐標代表各類群體在各特征上原始數(shù)據(jù)的分布情況，文中以第III類群體為例分析此類群體的消費特點。從圖中可以看出第III類群體在特征：午餐消費金額、晚餐消費金額、食堂消費天數(shù)、午晚餐差額比例、周內(nèi)在校天數(shù)、周末在校天數(shù)上的四分位距明顯比第II類群體小，說明第III類群體在這些特征上數(shù)據(jù)的分布比較集中，波動范圍小，消費習慣比較規(guī)律。

在特征：午餐消費金額，晚餐消費金額，午晚餐差額比例上的最大值、最小值、中位數(shù)、上下限比第I和第II類群體小，說明這類群體的消費水平較低。在特征：食堂消費天數(shù)，周內(nèi)在校天數(shù)，周末在校天數(shù)的最大值、最小值、中位數(shù)、上下限明顯比第I和第II類群體大，說明這類群體是最經(jīng)常在校內(nèi)就餐、很少離校。在早起次數(shù)比例上的各特征明顯高于其他兩類群體，說明這些學生喜歡早起，有著良好的習慣。綜上，第III類群體可以認定是有著良好生活和消費習慣、基本上不離校且消費水平較低的貧困生。各個群體消費數(shù)據(jù)波動程度的分析結果和上面各個群體聚類中心的分析結果相同。

2.4 聚類標記的貧困生分析

為了驗證Improve-Kmeans算法標記貧困生的效果，文中獲取了學校線下認定的2017級和2018級的貧困生名單，共349人。聚類標記與線下認定的貧困生名單重合率為47%，分析原因可能有兩方面：(1)Improve-Kmeans算法還需要進一步完善以更好地適應高校貧困生認定的應用環(huán)境；(2)線下貧困認定名單具有很大的不確定性，老師、學生很多情況下是通過申請表、平時的認知(甚至并不認識)來進行貧困認定，可能存在誤判的情況。因此文中以午餐平均消費水平和食堂就餐天數(shù)兩個特征為例，研究兩種方法中不重合的學生的消費情況：分別統(tǒng)計僅在聚類標記名單中出現(xiàn)的貧困生和僅在線下認定名單中出現(xiàn)的貧困生的午餐平均消費水平和食堂就餐天數(shù)，并繪制對應的概率密度曲線，如圖4所示。

(a)午餐平均消費金額概率密度曲線 (b)食堂消費天數(shù)概率密度曲線圖4 消費水平的概率密度曲線

從圖4(a)中可以看出，聚類標記貧困生的密度曲線比線下認定貧困生的密度曲線更加集中，這意味著聚類標記的貧困生比學生認定的貧困生的午餐平均消費金額波動更小，更加穩(wěn)定。

從圖4(b)中可以看出，聚類標記貧困生的密度曲線所處的位置明顯比線下認定貧困生的密度曲線所處的位置整體偏右，這意味著聚類標記的貧困生更偏向于在食堂就餐。

從午餐平均消費和食堂消費天數(shù)兩個指標上可以看出，相比沒有加入數(shù)據(jù)挖掘算法的線下貧困認定而言，基于客觀消費數(shù)據(jù)聚類挖掘貧困生的方法更加適用。

聚類標記貧困生方法和線下認定貧困生方法的總結如下：

(1)聚類標記貧困生的目標是找出消費水平低的貧困生，不考慮任何人為因素，單純從客觀的學生消費數(shù)據(jù)出發(fā)，挖掘各個群體的學生的消費水平，找出消費水平較低的貧困生。但是沒有考慮到學生家庭條件、健康情況、家庭人口情況和是否低保戶等信息；

(2)線下貧困生認定的目標是找出家庭經(jīng)濟情況困難的貧困生，以學生家庭收入情況、健康情況、家庭人口情況和是否低保戶等信息為標準，按照流程進行貧困生認定。但是沒有考慮學生的消費數(shù)據(jù)，難以發(fā)現(xiàn)沒有申請貧困認定的隱藏貧困生和申請了貧困認定的偽貧困生。

具體的貧困生認定工作可以結合這兩種方式的優(yōu)點：對于聚類標記認定的貧困生(或只考慮客觀消費數(shù)據(jù)的挖掘算法挖掘出的貧困生)可以發(fā)放專項的貧困生助學基金；對于線下流程化認定的貧困生可以按照國家的要求發(fā)放貧困生補貼。

文中算法不僅可以用來輔助貧困生的認定，還為以后更深入地利用數(shù)據(jù)挖掘相關技術研究高校精準資助活動提供了支持，值得進一步研究。

3 結束語

為了全面了解學生的行為特點，文中從學生群體的角度出發(fā)，利用學生校園消費數(shù)據(jù)研究不同學生群體行為特征的相似性與差異性。采用適合校園消費數(shù)據(jù)場景的Improve-Kmeans聚類算法對研究生的消費數(shù)據(jù)集進行聚類，分析不同學生群體的消費特征，進行畫像說明。同時對比分析了聚類得到的貧困生的消費數(shù)據(jù)和線下認定的貧困生的消費數(shù)據(jù)，為貧困生認定工作提出了改進意見，為高校的精準資助工作提供數(shù)據(jù)支持，為學生的校園學習生活保駕護航。