基于改進K-means算法的學生用戶畫像構建研究

許智宏，李彤彤，董永峰，董 瑤

（1.河北工業(yè)大學 人工智能與數(shù)據(jù)科學學院，天津 300401；2.河北工業(yè)大學 河北省大數(shù)據(jù)計算重點實驗室，天津 300401）

0 引言

校園一卡通中各種信息、資源的集成和優(yōu)化，能夠實現(xiàn)信息的有效配置和充分利用，同時一卡通作為數(shù)字校園建設重要組成部分，對學生個體發(fā)展和高校發(fā)展有著至關重要的作用。目前國內很多科研工作者對一卡通進行了相關的研究工作。姜楠和許維勝[1]以校園一卡通日常消費數(shù)據(jù)為研究對象，對學生消費習慣進行分析，運用改進初始中心點的K-means 算法通過類內密度程度高低來判定優(yōu)化初始中心點的選擇，對學生消費習慣進行聚類，采用Apriori算法對學習行為進行關聯(lián)度分析，協(xié)助高校學生工作人員分門別類對學生進行管理；黃剛等[2]采用K-means算法以校園一卡通數(shù)據(jù)為研究對象，通過做方差圖的方式對k值進行取值，分析學生的消費習慣后對學生特征進行畫像，該方法選擇多特征對學生畫像做出了基礎詳細分析，但是并未在算法層面上進行改進；韓偉等[3]用K-means算法將大學生餐飲消費行為按群體分類，側重分析時間、地點和交易金額，關聯(lián)成績預測不同層次學習成績的學生的餐飲習慣，研究側重應用，同樣未對算法過多敘述。

事實上，一個好的算法對于數(shù)據(jù)分析尤為重要，熊忠陽等[4]提出了一種基于密度的思想優(yōu)化初始聚類中心選擇的方法——最大距離法，在收斂速度和準確率上有大大提高，但是手動輸入密度系數(shù)，算法可伸縮性受限；劉靜[5]以數(shù)據(jù)中心點之間距離和數(shù)據(jù)內部以及數(shù)據(jù)間的差異度比值作為評估函數(shù)來確定初始中心點，提高了聚類算法的效率，但是數(shù)據(jù)量的大小同樣會影響效率；Shadab Irfan等[6]使用遺傳算法迭代的方式最小化目標函數(shù)和相似度函數(shù)，降低了函數(shù)的時間復雜度。

以上研究對于算法的改進均達到一定效果，但是數(shù)據(jù)特征的分散度相對較弱，數(shù)據(jù)特征的個性影響表示并不突出，未達到加強數(shù)據(jù)集特定功能的效果。因此，本研究采用DPCA-K-means算法建立數(shù)據(jù)分析模型，對多維數(shù)據(jù)特征進行降維處理，分散數(shù)據(jù)點后對新的權重特征求得數(shù)據(jù)均值作為初始質心，多次分配數(shù)據(jù)點進行聚類分析，通過增加每個特征的數(shù)據(jù)分析的個性影響，對不同行為特征的用戶對比成績進行類別劃分，研究影響學生行為與成績之間的關系。

1 用戶畫像模型構建

用戶畫像是通過收集用戶行為數(shù)據(jù)、統(tǒng)計屬性、分析特征，全面細致地挖掘用戶的特征并抽象出標簽化的用戶模型。用戶畫像側重于對用戶進行不同維度的劃分。在學生用戶畫像的構建過程中，利用高校一卡通數(shù)據(jù)對現(xiàn)有學生行為進行分析判定，其中消費數(shù)據(jù)屬性主要涵蓋交易額、交易時間、交易類型等多維，這些特征中多個數(shù)據(jù)特征或其特征組合對最終學生分類的影響較小甚至沒有影響。因此，多維度數(shù)據(jù)需要重新進行組合研究，提升數(shù)據(jù)表達的客觀全面性。

本文采用改進基礎模型K-means聚類算法和主成分分析（Principal Component Analysis，PCA）算法[7]對學生行為進行用戶畫像[8]，將學生用戶按照其行為習慣歸類，區(qū)別不同學習成績中眾多學生行為習慣的共性特征，辨識不同行為特征用戶的差異特征，幫助掌握用戶行為和成績的規(guī)律。改進的PCA算法即DPCA算法主要是用來改善數(shù)據(jù)特征對于數(shù)據(jù)分析實驗影響因素的情況，在本研究中用來對高維度特征進行重要度分析并賦予特征值權重，而K-means算法主要是實現(xiàn)對數(shù)據(jù)的基礎聚類[9]，本研究主要創(chuàng)新是在特征多樣性的基礎上分析特征的重要度并進行數(shù)據(jù)點新權重規(guī)劃，在保留盡可能大特征的基礎上增加特征之間的差異性，對K-means算法進行中心點選擇的改進[10]結合多次算法實驗，避免K-means陷入局部最優(yōu)，提高算法準確率。

1.1 K-means 算法基本思想

K-means算法是一種通過均值聚類數(shù)據(jù)點的無監(jiān)督的學習算法[11]，算法的關鍵是保證在各個中心點之間相互遠離的情況下隨機選擇不同位置的聚類中心[12]。核心思想為：選定聚類簇的個數(shù)k，隨機選擇樣本作為初始質心，依次考察每個樣本與當前質心的距離[13]，選定距離最近的簇后歸類。所有樣本考察結束一輪后，分別更新每個簇的質心，不斷重復上述過程，直到質心不再發(fā)生變化，算法結束。k個聚類簇具有以下特點：各個聚類內數(shù)據(jù)點盡可能緊湊，各聚類簇之間數(shù)據(jù)點盡可能遠離[14]。算法的最終收斂條件采用最小化誤差平方和目標函數(shù)[15]。聚類過程及其結果總體受到基礎中心點選擇的影響，均值聚類算法性能的關鍵就在于聚類中心的合理選取。其中誤差平方和的定義如式（1）：

式中：X為數(shù)據(jù)集中的數(shù)據(jù)點；Ci為質心。

TSS是嚴格的坐標下降（Coordinate Decent）過程，采用歐式距離作為變量之間的測度函數(shù)。每次趨近一個變量Ci的方向找到最優(yōu)解；目標函數(shù)TSS求偏導數(shù)，令其等于0后，得式（2）；

式中：k表示Ci所在的簇的元素的個數(shù)。

當前聚類的均值是當前方向的最優(yōu)解（最小值），與K-means的每次迭代過程一樣，保證TSS每次迭代后數(shù)值變小，最終收斂。但由于TSS是一個非凸函數(shù)（non-convex function），所以TSS并不能保證找到全局最優(yōu)解，只能確保局部最優(yōu)解。為防止K-means 算法局部最優(yōu)在處理數(shù)據(jù)的過程中采用DPCA 方式，即對數(shù)據(jù)進行降維處理后將數(shù)據(jù)重新進行再次投影，保留全部特征信息，記下每個特征的權重，且多次執(zhí)行Kmeans算法，最終選取最小的TSS為最終結果。

1.2 主成分分析算法基本思想

主成分分析算法（Principal Component Analysis）是利用降維的思想[16]，將多個變量轉化為少數(shù)幾個綜合變量（即主成分），每個主成分都是原始變量的線性組合，各主成分之間互不相關[17]，且能夠反映始變量的絕大部分信息。算法目標是計算出一組投影向量，將原始數(shù)據(jù)投影到一個維數(shù)較低的子空間，然后對這個子空間中的特征相似程度進行比較，從而實現(xiàn)對測試樣本的劃分，可以克服數(shù)據(jù)高維度造成的算法執(zhí)行效率降低的問題，將復雜因素歸結為幾個主成分，使得復雜特征得以簡化[18]。在算法執(zhí)行過程中遵循最大可分性和最近重構性原則，即數(shù)據(jù)點投影點盡可能分開，樣本點到投影平面的距離足夠近。PCA通過尋找一組線性投影向量，使得投影后得到的低維數(shù)據(jù)能夠盡可能多地保持原始數(shù)據(jù)的主要信息。理論研究表明，如果隨機變量的方差越大，則這些變量中所攜帶的信息就越多，若某一個特征的方差為零，那么該特征則為常量，對數(shù)據(jù)分析無任何影響。

PCA算法無法考慮不同樣本在識別過程中存在的重要度差異。它雖然能夠將原始數(shù)據(jù)通過線性變換矩陣從高維空間映射到低維空間，但它是平均地對待每一維特征，以各個維度特征歐氏距離上的重建誤差和最小為目標，無法實現(xiàn)特征的個性化提取。然而各樣本特征之間對于實驗結果的影響勢必一樣的，這就需要考慮用特征的權重系數(shù)來刻畫數(shù)據(jù)，因此采用特征權重系數(shù)的DPCA算法進行特征分析。算法流程如下：

步驟1 對數(shù)據(jù)集X中的每一個特征屬性進行標準化處理；

步驟2 求出數(shù)據(jù)中心化后矩陣X特征與特征之間的協(xié)方差，構成的協(xié)方差矩陣R[19]；

步驟3 對協(xié)方差矩陣做特征值分解，求特征值和特征向量；

步驟4 將特征向量按照特征值貢獻率降序排列，獲取最前的k列數(shù)據(jù)形成矩陣W。

步驟5 利用矩陣W和樣本集X進行矩陣的乘法得到降低到m維投影矩陣；

步驟6 將數(shù)據(jù)點權重置為0，重復步驟2、3、4，輸出m維新矩陣。

1.3 DPCA-K-means 算法基本思想

為了消除各個特征在量綱化和數(shù)量級上的差別，對數(shù)據(jù)進行標準化，得到標準化矩陣。假設數(shù)據(jù)集中有n個數(shù)據(jù)點X={X1,X2,…,Xn}，被劃分成k個分組{X1,X2,…,Xk}，k個質心C={c1,c2,…,ck}，要求k個分組滿足以下條件：X1?X2?Xk=X；Ck∈Xk；Xi≠Φ，其中k=1,2,…,n。為消除量綱和尺度的影響[20]，首先將數(shù)據(jù)標準化，轉化為無量綱的新數(shù)據(jù)集，便于不同單位或量級的指標能夠進行比較和加權。標準化過程如式（3）：

式中：xij為第i個體系特征第j個樣本的源數(shù)據(jù)；和σi分別是第i個特征體系的平均值和標準差。

根據(jù)標準化數(shù)據(jù)矩陣建立協(xié)方差矩陣，反映標準化后的數(shù)據(jù)之間相關關系密切程度的指標，其定義如式（4）：

式中：n代表數(shù)據(jù)點個數(shù)；Xi代表任意一個數(shù)據(jù)點；代表所有數(shù)據(jù)點的平均值。

樣本均值計算方法如式（5）：

根據(jù)協(xié)方差矩陣R求出特征值、主成分貢獻率和累計方差貢獻率。求出特征值[21]λi(i=1,2,…,n)，按大小順序排列，即λ1≥λ2≥…≥λi≥0。特征值是各主成分的方差，反映各個成分的影響力。把劃分所占整個信息的權重定義如式（6），所有劃分權重之和定義如式（7）：

式中：Wi表示每個特征在所有特征中所占的權重；W表示所有特征值的權重總和。

本研究中權重因子W的值為1，即累計特征值所占比例總和為100%，對數(shù)據(jù)重新進行加權處理后組成新的樣本數(shù)據(jù)為。將權重因子乘以每個屬性之后得到新的特征[22]，如式（8）：

歐氏距離[23]用來度量數(shù)據(jù)點與聚類中心之間的相似性。數(shù)據(jù)集X={X1,X2,…,Xn}的n個數(shù)據(jù)點，用m個元素值Xi={xi1,xi2,…,xim}組成該數(shù)據(jù)集的特征維度，特征組形成了m維空間，特征組中的每一個特征構成了每一維的數(shù)值。在m維空間下，2 個數(shù)據(jù)矩陣各形成了1 個點，計算這2 個點之間的距離，即為歐式距離。對其進行如下描述：

n個數(shù)據(jù)點X={X1,X2,…,Xn}，Xi={xi1,xi2,…,xim}中，其中2個數(shù)據(jù)Xi={xi1,xi2,…,xim} 和Xj={xj1,xj2,…,xjm}之間的距離D(XiXj)計算方法如式（9）：

式中：m表示數(shù)據(jù)點的特征維度。

第1個初始點選擇最接近均值的數(shù)據(jù)點，記為C1；選擇第2個初始點時，定義所有劃分的均值點mi到第1個初始點C1的距離WDi。選擇WDi最大的數(shù)據(jù)點為第2個初始聚類中心，記為C2。其中mi到第1個初始點C1的距離WDi，定義為加權歐幾里德距離，如式（10）：

對于最小距離選擇的描述如式（11）：

算法收斂條件為誤差平和最小值，對提出的改進算法步驟描述如下：

步驟1執(zhí)行DPCA 算法處理數(shù)據(jù)集進行重要度分析計算優(yōu)勝特征的不同的權重，得到權重因子后對每個數(shù)據(jù)點求加權平均值；

步驟2根據(jù)加權平均值對數(shù)據(jù)進行整合排序，劃分k個數(shù)據(jù)集；

步驟3計算每個數(shù)據(jù)集的平均值，取盡可能接近均值的數(shù)據(jù)點作為數(shù)據(jù)集的初始質心C1；

步驟4分別計算聚類中心Ci和數(shù)據(jù)集合中數(shù)據(jù)點Xi之間的加權歐式距離WDisti，繼續(xù)選擇其余質心；

步驟5將數(shù)據(jù)點分配給聚類最近的類中，在該聚類簇中數(shù)據(jù)點和聚類中心均有最小距離MinD，對于剩余樣本數(shù)據(jù)，同樣將其與距離最近的聚類中心歸為一類；

步驟6計算每個類中所有對象的平均值作為新的聚類中心；

步驟7重復步驟5和步驟6，直到滿足收斂條件。

改進算法流程如圖1所示。

圖1 DPCA-K-means 算法流程圖Fig.1 Flow chart of DPCA-K-means

2 驗證試驗與結果分析

2.1 實驗數(shù)據(jù)預處理

本研究原始數(shù)據(jù)包含學生的校園一卡通刷卡信息和成績信息。數(shù)據(jù)清洗階段，檢測數(shù)據(jù)中是否存在“學院/專業(yè)”缺失的情況，如有則刪除該條數(shù)據(jù)；是否存在不在食堂就餐的情況，如有則剔除該數(shù)據(jù)；清理刷卡消費價格為負數(shù)的異常點；檢測數(shù)據(jù)中是否存在消費數(shù)據(jù)缺失的情況。實驗之前將數(shù)據(jù)中行為習慣記錄較少的記為異常點并進行剔除。

2.2 實驗數(shù)據(jù)分析

實驗通過PCA算法中處理的數(shù)據(jù)進行特征重要性分析得到每個特征的相對應的權重，如表1。

表1 特征權重表Tab.1 Feature weight table

對數(shù)據(jù)進行DPCA處理后取平均值，取盡可能近的均值作為每個子集的初始質心，選取對應平方誤差和TSS最小值作為最優(yōu)聚類結果。當最小值TSS=42.658 1的時候，迭代次數(shù)為7次，此時聚類結果最佳。

用戶4個類別的聚類中心如表2、表3所示，可以明顯看出各類學生之間的差別。

表2 聚類中心結果對比（1）Tab.2 Comparison of cluster center results（1）

表3 聚類中心結果對比（2）Tab.3 Comparison of cluster center results（2）

學生用戶畫像實驗結果分析如下：

學霸類型學生：此類學生上午洗浴頻次和食堂消費占總消費比例均高于其余類別學生。他們吃早餐頻率很高，并且習慣到食堂就餐，吃飯時間最為規(guī)律，整體校園生活習慣非常好，對應成績在90分以上。

潛力類型學生：用餐總頻次、學生吃早餐、食堂消費占總消費比例、食堂消費占總消費比例等特征低于學霸類型學生，但是高于另外兩類學生。這類學生人群能夠按時吃飯，在校行為生活習慣比較規(guī)律。與部分學霸類型學生的生活習慣非常相似，學習積極性相對較高，只是成績上較低。若對此類型學生行為習慣重合的學生加以人為教導，他們的成績將會有很大的提高，躋身學霸類型學生，對與學霸類學生行為不接近的學生進行人為調控，同樣可以有進步，但是效果不如與學霸類學生人群重合的學生好。

普通類型學生：所有特征值比較均衡，可見此類學生中規(guī)中矩，去食堂的情況較正常，體現(xiàn)大多數(shù)學生的生活習慣，屬于普通類型的學生。

不努力類型學生：數(shù)據(jù)顯示各個特征聚類中心都小于其他類別學生，在食堂就餐頻次很低，很少去食堂和浴室，生活習慣不規(guī)律，整體學習不夠勤奮，學習狀態(tài)較差。

為了能夠直觀的觀察聚類的效果，選擇影響最大的前3 個特征，聚類分析進行可視化展示。其中紅色、綠色、藍色、紫色分別代表聚類1、2、3、4，分別對應成績大于90分，成績在80～90分之間，成績在60～80 分之間，成績小于60 分4 類學生。PC1、PC2、PC3 分別代表加權后的有效用餐頻次、學生早餐頻次、食堂消費占總消費比例。通過圖2可以清楚看到1、2類學生行為之間有重合，說明此類學生的行為習慣相似性很高，只是在成績上稍微有差別，算法基本可以區(qū)分不同層次的學生。

圖2 重要特征三維聚類展示圖Fig.2 3D cluster display of important features

將數(shù)據(jù)進行融合后得到訓練集聚類可視化展示，計算數(shù)據(jù)點到聚類中心的距離，如圖3所示。其中橫軸代表聚類簇，縱軸代表數(shù)據(jù)點到質心的距離，圖例分別表示各個類別。

圖3 聚類結果展示Fig.3 Comparison of cable tension under different magnitudes

為了檢驗本研究所提出的DPCA-K-means 算法的有效性，采用傳統(tǒng)PCA 結合K-means 算法的PCA-KMeans 和隨機選擇初始聚類中心的傳統(tǒng)基于歐幾里得距離的Euclidean-K-means算法作對比實驗分別對數(shù)據(jù)進行聚類，得到準確率的結果，如表4。

表4 不同聚類方法驗證性對比Tab.4 Verification comparison of different clustering methods

可以看出DPCA-K-means 算法通過特征多樣性的選取并通過權重調整聚類中心選擇，聚類的準確率較傳統(tǒng)方法有著顯著的提高[24]，對于學生用戶畫像起到了明顯作用。

3 結語

通過分析校園一卡通中學生的行為習慣，DPCAK-means 算法采用特征選擇和特征加權方式對數(shù)據(jù)進行聚類分析將學生劃分為成績好行為規(guī)律且早起的學霸類型、成績較好行為規(guī)律的潛力類型、成績一般行為不太規(guī)律的普通類型和很少早起且生活不規(guī)律的不努力類型。通過對比試驗可以看出該算法的準確率最高，可見此算法改進對分析學生行為有實用性。但由于一卡通數(shù)據(jù)的有限性，其數(shù)據(jù)不包含學生進出宿舍的數(shù)據(jù)，因此未能深入分析此因素對于成績的影響。接下來的分析將在此基礎上進行突破，并增強數(shù)據(jù)的適應性功能。