基于Canopy-K-means算法的高校貧困生預(yù)測的研究*

王全民 張書軍

（北京工業(yè)大學(xué)計算機學(xué)院 北京 100124）

1 引言

黨的十九大提出，堅決打贏扶貧攻堅戰(zhàn)，堅持精準扶貧、精準脫貧［1］，確保2020年實現(xiàn)全部脫貧；同時提出要優(yōu)先發(fā)展教育事業(yè)，要健全學(xué)生資助制度，使更多人接受高等教育。到2018年初，我國貧困人口預(yù)計還有3000萬左右［2］，這些貧困人口主要集中在農(nóng)村，農(nóng)村是打贏脫貧攻堅戰(zhàn)的主要短板。據(jù)統(tǒng)計，農(nóng)村貧困人口出現(xiàn)的主要原因包括教育致貧、因病致貧，其中相當一部分是由于教育致貧［3］。對于這些農(nóng)村貧困人口的脫貧問題，關(guān)鍵在于減輕家庭因教育相關(guān)費用而產(chǎn)生的負擔。因此，高等教育領(lǐng)域的精準扶貧工作非常重要，要實現(xiàn)精準扶貧，核心在于精準資助［4］，而貧困生認定是高校貧困生精準資助的前提與基礎(chǔ)，只有找準扶貧對象，才能進行有效資助。因此，解決高校貧困生資助工作中的認定問題迫在眉睫。

高校貧困生是指學(xué)生本人及其家庭難以支付其在校期間的學(xué)習(xí)生活費用的學(xué)生人群［5］。隨著國家經(jīng)濟的發(fā)展，國家對于教育事業(yè)發(fā)展的支持度不斷提升，讓更多的人能夠得到高等院校的教育。不過高校中存在的經(jīng)濟困難的學(xué)生也逐漸增加，在高校占比15%～30%［6］。目前由于學(xué)生的貧困生申請信息偏于主觀、貧困指標難以量化等因素，使得貧困生認定工作仍然是高校資助決策中的難點問題。高校數(shù)字化校園的建設(shè)中一卡通的應(yīng)用極大方便管理校園學(xué)生的日常生活，其應(yīng)用的范圍比較廣泛，食堂、超市、洗浴、門禁、圖書借閱等都可以直接刷卡?；谛@一卡通的消費數(shù)據(jù)，對其采用數(shù)據(jù)挖掘技術(shù)，分析學(xué)生消費特性及其能力，可作為一項評價標準，為貧困生認定提供數(shù)據(jù)依據(jù)。近年來，國內(nèi)已有一些初步研究，如馬玲玲［7］利用一卡通消費數(shù)據(jù)采用數(shù)據(jù)挖掘技術(shù)設(shè)計了一套高校貧困輔助分析系統(tǒng)；張璽［8］利用支持向量機（Support Vector Machine，SVM）算法進行數(shù)據(jù)分類認定貧困生；費小丹［9］選用K-means模型作為分析貧困生一卡通數(shù)據(jù)的聚類算法計算學(xué)生貧困指數(shù)。

綜上所述，雖然各種研究方法都對貧困生認定有了相關(guān)預(yù)測，但大多數(shù)研究都使用單源一卡通消費數(shù)據(jù)進行分析，而較少關(guān)注學(xué)生在校的其他行為對于貧困生評價的作用。高校校園網(wǎng)的建設(shè)也比較普及，學(xué)生可以通過登錄賬號上網(wǎng)，通過學(xué)生上網(wǎng)日志可以查到學(xué)生的登陸下線時間、上網(wǎng)使用流量、上網(wǎng)時長、上網(wǎng)消費金額等。對于學(xué)生來說，在校學(xué)習(xí)是當前最重要的任務(wù)，過度沉迷網(wǎng)絡(luò)的學(xué)生不應(yīng)該受到學(xué)校的資助。本文在已有的研究基礎(chǔ)上提出了一種基于Canopy-K-means算法的高校貧困生認定方法。以某211高校一卡通消費數(shù)據(jù)、上網(wǎng)日志等多模態(tài)數(shù)據(jù)使用數(shù)據(jù)作為研究內(nèi)容，通過高效聚類獲取貧困生類別，并采用數(shù)據(jù)統(tǒng)計和對比分析的方法預(yù)測貧困生劃分的合理性，為高校貧困生的資助提供輔助決策作用。

2 相關(guān)工作

2.1 聚類算法

聚類算法是數(shù)據(jù)挖掘中的重要算法之一［11］，在無先驗知識的條件下，按照數(shù)據(jù)集中數(shù)據(jù)本身的特點和差異，把一個數(shù)據(jù)集分割成若干個不同的類和簇，使得在同一個類中的數(shù)據(jù)對象的差異性盡可能地小，而處于不同類中的數(shù)據(jù)對象的差異性盡可能地大［11］。

2.2 K-means算法

K-means算法是聚類算法中使用最為廣泛的算法之一［14～15］，其用到的數(shù)學(xué)思想是基于距離的相似度計算，相對簡單，而且效率高，且對于“圓形-球形”性質(zhì)集合進行分類是，可以達到良好的聚類結(jié)果［10］。傳統(tǒng)K-means算法的工作流程如圖1所示，步驟如下。

圖1 K-means算法流程圖

1）對于數(shù)據(jù)集X=（x1，x2，…，x n），首先通過人工指定數(shù)字K作為聚類的數(shù)目，并隨機從樣本點中選取相應(yīng)數(shù)目的初始聚類中心｛c1，c2，…，c k｝；

2）計算各個樣本點xi到K個聚類中心的距離，并把樣本xi歸到與他距離最近的那個聚類中心ci所在的類中；

3）根據(jù)劃分的類別，計算同一個類中所有樣本點的各維平均值，作為新一輪聚類的k個中心；

4）重復(fù)上述過程繼續(xù)聚類，直至收斂。即使得式（1）最小化：

其中：

K-means算法雖然簡單易懂、高效，但其缺陷也比較明顯，主要有以下幾個方面：由于聚類的簇數(shù)K值需要預(yù)先給定，然而在實際中這個K值的選定是非常難以估計的，很多時候如果不是很了解樣本的大致分布情況，就不太好確定；K個初始中心點的選取存在隨機性，每次算法開始時不同的初始點懸著將可能導(dǎo)致完全不同的分組，在數(shù)次迭代之后，得到完全不同的聚類結(jié)果，使得聚類的結(jié)果具有不穩(wěn)定性［12］；K-means算法中許多計算是冗余的，若計算量很大時，算法的時間開銷也非常大。

2.3 Canopy算法

Canopy［13］也是一種聚類算法，主要用于海量高維數(shù)據(jù)的聚類。Canopy可以粗略地將數(shù)據(jù)劃分成若干個重疊子集。每個子集作為一個類簇，其一般使用一種代價低的相似度度量方法，以加快聚類的速度。Canopy算法一般用于其他聚類算法的初始化操作。Canopy算法工作流程如圖2所示，步驟如下。

圖2 Canopy算法流程圖

1）首先需要指定兩個距離閾值，T1、T2（T1>T2），在數(shù)據(jù)集中選擇一個點作為初始中心點加入到Canopy中心列表C中。

2）對于數(shù)據(jù)集中任意一個點xi（xi∈C），若xi與cj（cj∈C）的距離均大于T1，則將xi作為一個新的Canopy中心加入到C中；若距離小于T1，則將xi加入以cj為中心的Canopy中；若xi與cj的距離小于T2，將x i與cj強關(guān)聯(lián)，xi不能再作為其他Canopy的中心，將其從數(shù)據(jù)集中刪除；

3）重復(fù)上述過程，直至數(shù)據(jù)集為空。

Canopy聚類允許有重疊子集，增加了算法的容錯性和消除孤立點作用；同時，由于只需在每個Canopy中心內(nèi)進行精確聚類，從而避免了對多有點精確聚類帶來的計算量大的問題。

2.4 改進的Canopy-K-means算法

傳統(tǒng)的K-means算法由于初始聚類中心選擇的隨機性，算法結(jié)果隨著中心點選擇的不同而改變，導(dǎo)致結(jié)果的不穩(wěn)定性，可能會造成局部最優(yōu)值的問題。針對中心點選擇的問題，通過引入Canopy算法，為K-means算法確定初始聚類中心。在進行K-means聚類過程中，將不在考慮每個點到所有中心的距離，只需計算點到其所屬的Canopy中心的距離，即K-means算法將在每個Canopy中進行，而隨著K-means算法的迭代，每個Canopy中心不斷變化，直至收斂。具體執(zhí)行流程如圖2所示。

圖3 改進的Canopy-K-means算法

從圖3可知，改進的Canopy-K-means算法首先通過Canopy算法形成相互重疊的Canopy，再進行K-means迭代，最后產(chǎn)出聚類結(jié)果。其算法步驟如下。

1）給定數(shù)據(jù)集，利用Canopy算法生成相互重疊Canopy聚類中心。

2）計算合并K-means算法中心點。將點歸到最近的Canopy中心點，計算每個簇點的平均值即K-menas算法的初始聚類中心。由于前期采用了Canopy算法生成初始中心，在確定T1、T2時，由于半徑過小會導(dǎo)致聚類后的中心點過多的問題，因此選擇一定的范圍，將中心點間距離過小的點合并求均值，即K-means的中心點。

3）對每個Canopy內(nèi)的點使用K-means算法進行精確聚類，進行K-means迭代。在迭代結(jié)束之后，形成不重疊的最終簇，完成聚類。

3 實驗

3.1 數(shù)據(jù)集

本文研究數(shù)據(jù)主要是基于2017年9月～2018年1月的某211高校學(xué)生一卡通食堂消費數(shù)據(jù)和上網(wǎng)日志分別見間表1中的表（a）和表（b）。其中表（a）原始數(shù)據(jù)包含學(xué)號、消費時間、消費金額、消費地點，表（b）原始數(shù)據(jù)學(xué)號、上網(wǎng)消費金額、上網(wǎng)使用流量、上網(wǎng)時長、上網(wǎng)IP地址、上網(wǎng)上線和下線時間等，其中表（b）提供了部分的原始數(shù)據(jù)集。為了保護數(shù)據(jù)隱私，將學(xué)生學(xué)號和IP地址的部分用“***”表示。

表1 學(xué)生一卡通食堂消費數(shù)據(jù)和上網(wǎng)日志

原始數(shù)據(jù)需要進行數(shù)據(jù)預(yù)處理才可應(yīng)用算法進行模型訓(xùn)練和預(yù)測分析，具體數(shù)據(jù)處理信息如下：本文研究的對象為本科生，需要對數(shù)據(jù)中博士研究生數(shù)據(jù)需要剔除；一卡通食堂消費數(shù)據(jù)提取學(xué)生早中晚三餐消費金額和消費次數(shù)，其中早餐時間段為6：00-9：59，中餐時間段為10：00-14：59，晚餐時間段為15：00-20：00，由于在同一時間段內(nèi)會有多次消費，所以在這一時間段內(nèi)的消費按一次計算，消費金額累加；上網(wǎng)日志需要提取每次上網(wǎng)上線下線所消費金額、使用流量、上網(wǎng)時長。為了便于聚類分析，需要將以上處理的數(shù)據(jù)離散化，按照數(shù)據(jù)進行等寬劃分五個區(qū)間，即很高（2）、高（1）、中（0）、低（-1）、很低（-2），所得結(jié)果如圖4所示。

圖4 食堂消費和上網(wǎng)日志數(shù)據(jù)離散圖

3.2 運用Canopy-K-means聚類算法確定聚類中心

首先，獲取學(xué)生一卡通消費數(shù)據(jù)和上網(wǎng)日志，對數(shù)據(jù)進行預(yù)處理。其次，Canopy-K-means聚類算法需要分兩步使用，Canopy算法聚類過程包含兩個參數(shù)T1、T2（T1>T2），其中T1、T2都表示數(shù)據(jù)集中的點距Canopy算法中心點C i的距離；若距離小于T1且小于T2，則將該點與C i強關(guān)聯(lián)，在使用K-means算法是則不需要計算數(shù)據(jù)點到給定隨機點的距離，只需要計算數(shù)據(jù)點到Canopy中心點的距離即可。T1、T2的選取將影響聚類結(jié)果的效果。最后，經(jīng)過多次迭代試驗，確定T1的值為15、T2的值為6時，得到的效果最佳，此時可劃分5類，其聚類結(jié)果如表2所示。

表2 Canopy-K-means聚類結(jié)果表

從表2聚類結(jié)果可對這5類學(xué)生食堂消費習(xí)慣和上網(wǎng)行為進行分析如表3。

表3 學(xué)生類別食堂消費習(xí)慣和上網(wǎng)行為分析

將實驗結(jié)果與在校實際評定的貧困生進行對比，可以發(fā)現(xiàn)第II類學(xué)生中有378名貧困生，占貧困生總數(shù)的75.6%，第II類學(xué)生表現(xiàn)出的食堂消費比較規(guī)律，消費金額少消費次數(shù)高，上網(wǎng)使用金額、流量、時長較少。從表3分析結(jié)果可知第二類特征習(xí)慣符合一個貧困生在校的生活規(guī)律，這類學(xué)生可推薦貧困申請，為高校工作人員提供輔助決策作用。其他類別分布較少，這其中可能有一些特殊的原因被評定為貧困生。比如單親家庭，家里突發(fā)事故等。

4 結(jié)語

本文研究以某211高校2017年9月～2018年1月本科生一卡通食堂消費數(shù)據(jù)和上網(wǎng)日志數(shù)據(jù)作為研究對象，結(jié)合Canopy-K-means算法對數(shù)據(jù)進行聚類，分析聚類的類別，對比通過實驗獲得的結(jié)果與實際評定的貧困生，預(yù)測準確度達到75.6%，找出相應(yīng)的貧困生類別并做深入分析，分析貧困生食堂消費習(xí)慣和上網(wǎng)行為，為高校貧困生認定提供輔助決策作用。貧困生認定工作在高校中是比較重要的環(huán)節(jié)，有效的評定貧困生能夠讓真正貧困的學(xué)生得到學(xué)校的資助，讓他們能夠在校園健康成長。我們應(yīng)該從學(xué)生在校生活中挖掘更多的信息來為貧困生評定工作提供數(shù)據(jù)依據(jù)，提高貧困生認定的準確度。