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

王全民 張書軍

（北京工業大學計算機學院 北京 100124）

1 引言

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

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

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

2 相關工作

2.1 聚類算法

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

2.2 K-means算法

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

圖1 K-means算法流程圖

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

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

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

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

其中：

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

2.3 Canopy算法

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

圖2 Canopy算法流程圖

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

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

3）重復上述過程，直至數據集為空。

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

2.4 改進的Canopy-K-means算法

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

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

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

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

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

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

3 實驗

3.1 數據集

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

表1 學生一卡通食堂消費數據和上網日志

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

圖4 食堂消費和上網日志數據離散圖

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

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

表2 Canopy-K-means聚類結果表

從表2聚類結果可對這5類學生食堂消費習慣和上網行為進行分析如表3。

表3 學生類別食堂消費習慣和上網行為分析

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

4 結語

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