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

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

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

0 引言

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

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

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

1 用戶畫像模型構建

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

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

1.1 K-means 算法基本思想

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

式中：X為數據集中的數據點；Ci為質心。

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

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

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

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

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

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

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

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

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

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

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

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

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

為了消除各個特征在量綱化和數量級上的差別，對數據進行標準化，得到標準化矩陣。假設數據集中有n個數據點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]，首先將數據標準化，轉化為無量綱的新數據集，便于不同單位或量級的指標能夠進行比較和加權。標準化過程如式（3）：

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

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

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

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

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

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

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

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

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

式中：m表示數據點的特征維度。

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

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

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

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

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

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

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

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

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

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

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

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

2 驗證試驗與結果分析

2.1 實驗數據預處理

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

2.2 實驗數據分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結語

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