許智宏,李彤彤,董永峰,董 瑤
(1.河北工業(yè)大學(xué) 人工智能與數(shù)據(jù)科學(xué)學(xué)院,天津 300401;2.河北工業(yè)大學(xué) 河北省大數(shù)據(jù)計(jì)算重點(diǎn)實(shí)驗(yàn)室,天津 300401)
校園一卡通中各種信息、資源的集成和優(yōu)化,能夠?qū)崿F(xiàn)信息的有效配置和充分利用,同時(shí)一卡通作為數(shù)字校園建設(shè)重要組成部分,對(duì)學(xué)生個(gè)體發(fā)展和高校發(fā)展有著至關(guān)重要的作用。目前國內(nèi)很多科研工作者對(duì)一卡通進(jìn)行了相關(guān)的研究工作。姜楠和許維勝[1]以校園一卡通日常消費(fèi)數(shù)據(jù)為研究對(duì)象,對(duì)學(xué)生消費(fèi)習(xí)慣進(jìn)行分析,運(yùn)用改進(jìn)初始中心點(diǎn)的K-means 算法通過類內(nèi)密度程度高低來判定優(yōu)化初始中心點(diǎn)的選擇,對(duì)學(xué)生消費(fèi)習(xí)慣進(jìn)行聚類,采用Apriori算法對(duì)學(xué)習(xí)行為進(jìn)行關(guān)聯(lián)度分析,協(xié)助高校學(xué)生工作人員分門別類對(duì)學(xué)生進(jìn)行管理;黃剛等[2]采用K-means算法以校園一卡通數(shù)據(jù)為研究對(duì)象,通過做方差圖的方式對(duì)k值進(jìn)行取值,分析學(xué)生的消費(fèi)習(xí)慣后對(duì)學(xué)生特征進(jìn)行畫像,該方法選擇多特征對(duì)學(xué)生畫像做出了基礎(chǔ)詳細(xì)分析,但是并未在算法層面上進(jìn)行改進(jìn);韓偉等[3]用K-means算法將大學(xué)生餐飲消費(fèi)行為按群體分類,側(cè)重分析時(shí)間、地點(diǎn)和交易金額,關(guān)聯(lián)成績預(yù)測不同層次學(xué)習(xí)成績的學(xué)生的餐飲習(xí)慣,研究側(cè)重應(yīng)用,同樣未對(duì)算法過多敘述。
事實(shí)上,一個(gè)好的算法對(duì)于數(shù)據(jù)分析尤為重要,熊忠陽等[4]提出了一種基于密度的思想優(yōu)化初始聚類中心選擇的方法——最大距離法,在收斂速度和準(zhǔn)確率上有大大提高,但是手動(dòng)輸入密度系數(shù),算法可伸縮性受限;劉靜[5]以數(shù)據(jù)中心點(diǎn)之間距離和數(shù)據(jù)內(nèi)部以及數(shù)據(jù)間的差異度比值作為評(píng)估函數(shù)來確定初始中心點(diǎn),提高了聚類算法的效率,但是數(shù)據(jù)量的大小同樣會(huì)影響效率;Shadab Irfan等[6]使用遺傳算法迭代的方式最小化目標(biāo)函數(shù)和相似度函數(shù),降低了函數(shù)的時(shí)間復(fù)雜度。
以上研究對(duì)于算法的改進(jìn)均達(dá)到一定效果,但是數(shù)據(jù)特征的分散度相對(duì)較弱,數(shù)據(jù)特征的個(gè)性影響表示并不突出,未達(dá)到加強(qiáng)數(shù)據(jù)集特定功能的效果。因此,本研究采用DPCA-K-means算法建立數(shù)據(jù)分析模型,對(duì)多維數(shù)據(jù)特征進(jìn)行降維處理,分散數(shù)據(jù)點(diǎn)后對(duì)新的權(quán)重特征求得數(shù)據(jù)均值作為初始質(zhì)心,多次分配數(shù)據(jù)點(diǎn)進(jìn)行聚類分析,通過增加每個(gè)特征的數(shù)據(jù)分析的個(gè)性影響,對(duì)不同行為特征的用戶對(duì)比成績進(jìn)行類別劃分,研究影響學(xué)生行為與成績之間的關(guān)系。
用戶畫像是通過收集用戶行為數(shù)據(jù)、統(tǒng)計(jì)屬性、分析特征,全面細(xì)致地挖掘用戶的特征并抽象出標(biāo)簽化的用戶模型。用戶畫像側(cè)重于對(duì)用戶進(jìn)行不同維度的劃分。在學(xué)生用戶畫像的構(gòu)建過程中,利用高校一卡通數(shù)據(jù)對(duì)現(xiàn)有學(xué)生行為進(jìn)行分析判定,其中消費(fèi)數(shù)據(jù)屬性主要涵蓋交易額、交易時(shí)間、交易類型等多維,這些特征中多個(gè)數(shù)據(jù)特征或其特征組合對(duì)最終學(xué)生分類的影響較小甚至沒有影響。因此,多維度數(shù)據(jù)需要重新進(jìn)行組合研究,提升數(shù)據(jù)表達(dá)的客觀全面性。
本文采用改進(jìn)基礎(chǔ)模型K-means聚類算法和主成分分析(Principal Component Analysis,PCA)算法[7]對(duì)學(xué)生行為進(jìn)行用戶畫像[8],將學(xué)生用戶按照其行為習(xí)慣歸類,區(qū)別不同學(xué)習(xí)成績中眾多學(xué)生行為習(xí)慣的共性特征,辨識(shí)不同行為特征用戶的差異特征,幫助掌握用戶行為和成績的規(guī)律。改進(jìn)的PCA算法即DPCA算法主要是用來改善數(shù)據(jù)特征對(duì)于數(shù)據(jù)分析實(shí)驗(yàn)影響因素的情況,在本研究中用來對(duì)高維度特征進(jìn)行重要度分析并賦予特征值權(quán)重,而K-means算法主要是實(shí)現(xiàn)對(duì)數(shù)據(jù)的基礎(chǔ)聚類[9],本研究主要?jiǎng)?chuàng)新是在特征多樣性的基礎(chǔ)上分析特征的重要度并進(jìn)行數(shù)據(jù)點(diǎn)新權(quán)重規(guī)劃,在保留盡可能大特征的基礎(chǔ)上增加特征之間的差異性,對(duì)K-means算法進(jìn)行中心點(diǎn)選擇的改進(jìn)[10]結(jié)合多次算法實(shí)驗(yàn),避免K-means陷入局部最優(yōu),提高算法準(zhǔn)確率。
K-means算法是一種通過均值聚類數(shù)據(jù)點(diǎn)的無監(jiān)督的學(xué)習(xí)算法[11],算法的關(guān)鍵是保證在各個(gè)中心點(diǎn)之間相互遠(yuǎn)離的情況下隨機(jī)選擇不同位置的聚類中心[12]。核心思想為:選定聚類簇的個(gè)數(shù)k,隨機(jī)選擇樣本作為初始質(zhì)心,依次考察每個(gè)樣本與當(dāng)前質(zhì)心的距離[13],選定距離最近的簇后歸類。所有樣本考察結(jié)束一輪后,分別更新每個(gè)簇的質(zhì)心,不斷重復(fù)上述過程,直到質(zhì)心不再發(fā)生變化,算法結(jié)束。k個(gè)聚類簇具有以下特點(diǎn):各個(gè)聚類內(nèi)數(shù)據(jù)點(diǎn)盡可能緊湊,各聚類簇之間數(shù)據(jù)點(diǎn)盡可能遠(yuǎn)離[14]。算法的最終收斂條件采用最小化誤差平方和目標(biāo)函數(shù)[15]。聚類過程及其結(jié)果總體受到基礎(chǔ)中心點(diǎn)選擇的影響,均值聚類算法性能的關(guān)鍵就在于聚類中心的合理選取。其中誤差平方和的定義如式(1):
式中:X為數(shù)據(jù)集中的數(shù)據(jù)點(diǎn);Ci為質(zhì)心。
TSS是嚴(yán)格的坐標(biāo)下降(Coordinate Decent)過程,采用歐式距離作為變量之間的測度函數(shù)。每次趨近一個(gè)變量Ci的方向找到最優(yōu)解;目標(biāo)函數(shù)TSS求偏導(dǎo)數(shù),令其等于0后,得式(2);
式中:k表示Ci所在的簇的元素的個(gè)數(shù)。
當(dāng)前聚類的均值是當(dāng)前方向的最優(yōu)解(最小值),與K-means的每次迭代過程一樣,保證TSS每次迭代后數(shù)值變小,最終收斂。但由于TSS是一個(gè)非凸函數(shù)(non-convex function),所以TSS并不能保證找到全局最優(yōu)解,只能確保局部最優(yōu)解。為防止K-means 算法局部最優(yōu)在處理數(shù)據(jù)的過程中采用DPCA 方式,即對(duì)數(shù)據(jù)進(jìn)行降維處理后將數(shù)據(jù)重新進(jìn)行再次投影,保留全部特征信息,記下每個(gè)特征的權(quán)重,且多次執(zhí)行Kmeans算法,最終選取最小的TSS為最終結(jié)果。
主成分分析算法(Principal Component Analysis)是利用降維的思想[16],將多個(gè)變量轉(zhuǎn)化為少數(shù)幾個(gè)綜合變量(即主成分),每個(gè)主成分都是原始變量的線性組合,各主成分之間互不相關(guān)[17],且能夠反映始變量的絕大部分信息。算法目標(biāo)是計(jì)算出一組投影向量,將原始數(shù)據(jù)投影到一個(gè)維數(shù)較低的子空間,然后對(duì)這個(gè)子空間中的特征相似程度進(jìn)行比較,從而實(shí)現(xiàn)對(duì)測試樣本的劃分,可以克服數(shù)據(jù)高維度造成的算法執(zhí)行效率降低的問題,將復(fù)雜因素歸結(jié)為幾個(gè)主成分,使得復(fù)雜特征得以簡化[18]。在算法執(zhí)行過程中遵循最大可分性和最近重構(gòu)性原則,即數(shù)據(jù)點(diǎn)投影點(diǎn)盡可能分開,樣本點(diǎn)到投影平面的距離足夠近。PCA通過尋找一組線性投影向量,使得投影后得到的低維數(shù)據(jù)能夠盡可能多地保持原始數(shù)據(jù)的主要信息。理論研究表明,如果隨機(jī)變量的方差越大,則這些變量中所攜帶的信息就越多,若某一個(gè)特征的方差為零,那么該特征則為常量,對(duì)數(shù)據(jù)分析無任何影響。
PCA算法無法考慮不同樣本在識(shí)別過程中存在的重要度差異。它雖然能夠?qū)⒃紨?shù)據(jù)通過線性變換矩陣從高維空間映射到低維空間,但它是平均地對(duì)待每一維特征,以各個(gè)維度特征歐氏距離上的重建誤差和最小為目標(biāo),無法實(shí)現(xiàn)特征的個(gè)性化提取。然而各樣本特征之間對(duì)于實(shí)驗(yàn)結(jié)果的影響勢必一樣的,這就需要考慮用特征的權(quán)重系數(shù)來刻畫數(shù)據(jù),因此采用特征權(quán)重系數(shù)的DPCA算法進(jìn)行特征分析。算法流程如下:
步驟1 對(duì)數(shù)據(jù)集X中的每一個(gè)特征屬性進(jìn)行標(biāo)準(zhǔn)化處理;
步驟2 求出數(shù)據(jù)中心化后矩陣X特征與特征之間的協(xié)方差,構(gòu)成的協(xié)方差矩陣R[19];
步驟3 對(duì)協(xié)方差矩陣做特征值分解,求特征值和特征向量;
步驟4 將特征向量按照特征值貢獻(xiàn)率降序排列,獲取最前的k列數(shù)據(jù)形成矩陣W。
步驟5 利用矩陣W和樣本集X進(jìn)行矩陣的乘法得到降低到m維投影矩陣;
步驟6 將數(shù)據(jù)點(diǎn)權(quán)重置為0,重復(fù)步驟2、3、4,輸出m維新矩陣。
為了消除各個(gè)特征在量綱化和數(shù)量級(jí)上的差別,對(duì)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化,得到標(biāo)準(zhǔn)化矩陣。假設(shè)數(shù)據(jù)集中有n個(gè)數(shù)據(jù)點(diǎn)X={X1,X2,…,Xn},被劃分成k個(gè)分組{X1,X2,…,Xk},k個(gè)質(zhì)心C={c1,c2,…,ck},要求k個(gè)分組滿足以下條件:X1?X2?Xk=X;Ck∈Xk;Xi≠Φ,其中k=1,2,…,n。為消除量綱和尺度的影響[20],首先將數(shù)據(jù)標(biāo)準(zhǔn)化,轉(zhuǎn)化為無量綱的新數(shù)據(jù)集,便于不同單位或量級(jí)的指標(biāo)能夠進(jìn)行比較和加權(quán)。標(biāo)準(zhǔn)化過程如式(3):
式中:xij為第i個(gè)體系特征第j個(gè)樣本的源數(shù)據(jù);和σi分別是第i個(gè)特征體系的平均值和標(biāo)準(zhǔn)差。
根據(jù)標(biāo)準(zhǔn)化數(shù)據(jù)矩陣建立協(xié)方差矩陣,反映標(biāo)準(zhǔn)化后的數(shù)據(jù)之間相關(guān)關(guān)系密切程度的指標(biāo),其定義如式(4):
式中:n代表數(shù)據(jù)點(diǎn)個(gè)數(shù);Xi代表任意一個(gè)數(shù)據(jù)點(diǎn);代表所有數(shù)據(jù)點(diǎn)的平均值。
樣本均值計(jì)算方法如式(5):
根據(jù)協(xié)方差矩陣R求出特征值、主成分貢獻(xiàn)率和累計(jì)方差貢獻(xiàn)率。求出特征值[21]λi(i=1,2,…,n),按大小順序排列,即λ1≥λ2≥…≥λi≥0。特征值是各主成分的方差,反映各個(gè)成分的影響力。把劃分所占整個(gè)信息的權(quán)重定義如式(6),所有劃分權(quán)重之和定義如式(7):
式中:Wi表示每個(gè)特征在所有特征中所占的權(quán)重;W表示所有特征值的權(quán)重總和。
本研究中權(quán)重因子W的值為1,即累計(jì)特征值所占比例總和為100%,對(duì)數(shù)據(jù)重新進(jìn)行加權(quán)處理后組成新的樣本數(shù)據(jù)為。將權(quán)重因子乘以每個(gè)屬性之后得到新的特征[22],如式(8):
歐氏距離[23]用來度量數(shù)據(jù)點(diǎn)與聚類中心之間的相似性。數(shù)據(jù)集X={X1,X2,…,Xn}的n個(gè)數(shù)據(jù)點(diǎn),用m個(gè)元素值Xi={xi1,xi2,…,xim}組成該數(shù)據(jù)集的特征維度,特征組形成了m維空間,特征組中的每一個(gè)特征構(gòu)成了每一維的數(shù)值。在m維空間下,2 個(gè)數(shù)據(jù)矩陣各形成了1 個(gè)點(diǎn),計(jì)算這2 個(gè)點(diǎn)之間的距離,即為歐式距離。對(duì)其進(jìn)行如下描述:
n個(gè)數(shù)據(jù)點(diǎn)X={X1,X2,…,Xn},Xi={xi1,xi2,…,xim}中,其中2個(gè)數(shù)據(jù)Xi={xi1,xi2,…,xim} 和Xj={xj1,xj2,…,xjm}之間的距離D(XiXj)計(jì)算方法如式(9):
式中:m表示數(shù)據(jù)點(diǎn)的特征維度。
第1個(gè)初始點(diǎn)選擇最接近均值的數(shù)據(jù)點(diǎn),記為C1;選擇第2個(gè)初始點(diǎn)時(shí),定義所有劃分的均值點(diǎn)mi到第1個(gè)初始點(diǎn)C1的距離WDi。選擇WDi最大的數(shù)據(jù)點(diǎn)為第2個(gè)初始聚類中心,記為C2。其中mi到第1個(gè)初始點(diǎn)C1的距離WDi,定義為加權(quán)歐幾里德距離,如式(10):
對(duì)于最小距離選擇的描述如式(11):
算法收斂條件為誤差平和最小值,對(duì)提出的改進(jìn)算法步驟描述如下:
步驟1執(zhí)行DPCA 算法處理數(shù)據(jù)集進(jìn)行重要度分析計(jì)算優(yōu)勝特征的不同的權(quán)重,得到權(quán)重因子后對(duì)每個(gè)數(shù)據(jù)點(diǎn)求加權(quán)平均值;
步驟2根據(jù)加權(quán)平均值對(duì)數(shù)據(jù)進(jìn)行整合排序,劃分k個(gè)數(shù)據(jù)集;
步驟3計(jì)算每個(gè)數(shù)據(jù)集的平均值,取盡可能接近均值的數(shù)據(jù)點(diǎn)作為數(shù)據(jù)集的初始質(zhì)心C1;
步驟4分別計(jì)算聚類中心Ci和數(shù)據(jù)集合中數(shù)據(jù)點(diǎn)Xi之間的加權(quán)歐式距離WDisti,繼續(xù)選擇其余質(zhì)心;
步驟5將數(shù)據(jù)點(diǎn)分配給聚類最近的類中,在該聚類簇中數(shù)據(jù)點(diǎn)和聚類中心均有最小距離MinD,對(duì)于剩余樣本數(shù)據(jù),同樣將其與距離最近的聚類中心歸為一類;
步驟6計(jì)算每個(gè)類中所有對(duì)象的平均值作為新的聚類中心;
步驟7重復(fù)步驟5和步驟6,直到滿足收斂條件。
改進(jìn)算法流程如圖1所示。
圖1 DPCA-K-means 算法流程圖Fig.1 Flow chart of DPCA-K-means
本研究原始數(shù)據(jù)包含學(xué)生的校園一卡通刷卡信息和成績信息。數(shù)據(jù)清洗階段,檢測數(shù)據(jù)中是否存在“學(xué)院/專業(yè)”缺失的情況,如有則刪除該條數(shù)據(jù);是否存在不在食堂就餐的情況,如有則剔除該數(shù)據(jù);清理刷卡消費(fèi)價(jià)格為負(fù)數(shù)的異常點(diǎn);檢測數(shù)據(jù)中是否存在消費(fèi)數(shù)據(jù)缺失的情況。實(shí)驗(yàn)之前將數(shù)據(jù)中行為習(xí)慣記錄較少的記為異常點(diǎn)并進(jìn)行剔除。
實(shí)驗(yàn)通過PCA算法中處理的數(shù)據(jù)進(jìn)行特征重要性分析得到每個(gè)特征的相對(duì)應(yīng)的權(quán)重,如表1。
表1 特征權(quán)重表Tab.1 Feature weight table
對(duì)數(shù)據(jù)進(jìn)行DPCA處理后取平均值,取盡可能近的均值作為每個(gè)子集的初始質(zhì)心,選取對(duì)應(yīng)平方誤差和TSS最小值作為最優(yōu)聚類結(jié)果。當(dāng)最小值TSS=42.658 1的時(shí)候,迭代次數(shù)為7次,此時(shí)聚類結(jié)果最佳。
用戶4個(gè)類別的聚類中心如表2、表3所示,可以明顯看出各類學(xué)生之間的差別。
表2 聚類中心結(jié)果對(duì)比(1)Tab.2 Comparison of cluster center results(1)
表3 聚類中心結(jié)果對(duì)比(2)Tab.3 Comparison of cluster center results(2)
學(xué)生用戶畫像實(shí)驗(yàn)結(jié)果分析如下:
學(xué)霸類型學(xué)生:此類學(xué)生上午洗浴頻次和食堂消費(fèi)占總消費(fèi)比例均高于其余類別學(xué)生。他們吃早餐頻率很高,并且習(xí)慣到食堂就餐,吃飯時(shí)間最為規(guī)律,整體校園生活習(xí)慣非常好,對(duì)應(yīng)成績?cè)?0分以上。
潛力類型學(xué)生:用餐總頻次、學(xué)生吃早餐、食堂消費(fèi)占總消費(fèi)比例、食堂消費(fèi)占總消費(fèi)比例等特征低于學(xué)霸類型學(xué)生,但是高于另外兩類學(xué)生。這類學(xué)生人群能夠按時(shí)吃飯,在校行為生活習(xí)慣比較規(guī)律。與部分學(xué)霸類型學(xué)生的生活習(xí)慣非常相似,學(xué)習(xí)積極性相對(duì)較高,只是成績上較低。若對(duì)此類型學(xué)生行為習(xí)慣重合的學(xué)生加以人為教導(dǎo),他們的成績將會(huì)有很大的提高,躋身學(xué)霸類型學(xué)生,對(duì)與學(xué)霸類學(xué)生行為不接近的學(xué)生進(jìn)行人為調(diào)控,同樣可以有進(jìn)步,但是效果不如與學(xué)霸類學(xué)生人群重合的學(xué)生好。
普通類型學(xué)生:所有特征值比較均衡,可見此類學(xué)生中規(guī)中矩,去食堂的情況較正常,體現(xiàn)大多數(shù)學(xué)生的生活習(xí)慣,屬于普通類型的學(xué)生。
不努力類型學(xué)生:數(shù)據(jù)顯示各個(gè)特征聚類中心都小于其他類別學(xué)生,在食堂就餐頻次很低,很少去食堂和浴室,生活習(xí)慣不規(guī)律,整體學(xué)習(xí)不夠勤奮,學(xué)習(xí)狀態(tài)較差。
為了能夠直觀的觀察聚類的效果,選擇影響最大的前3 個(gè)特征,聚類分析進(jìn)行可視化展示。其中紅色、綠色、藍(lán)色、紫色分別代表聚類1、2、3、4,分別對(duì)應(yīng)成績大于90分,成績?cè)?0~90分之間,成績?cè)?0~80 分之間,成績小于60 分4 類學(xué)生。PC1、PC2、PC3 分別代表加權(quán)后的有效用餐頻次、學(xué)生早餐頻次、食堂消費(fèi)占總消費(fèi)比例。通過圖2可以清楚看到1、2類學(xué)生行為之間有重合,說明此類學(xué)生的行為習(xí)慣相似性很高,只是在成績上稍微有差別,算法基本可以區(qū)分不同層次的學(xué)生。
圖2 重要特征三維聚類展示圖Fig.2 3D cluster display of important features
將數(shù)據(jù)進(jìn)行融合后得到訓(xùn)練集聚類可視化展示,計(jì)算數(shù)據(jù)點(diǎn)到聚類中心的距離,如圖3所示。其中橫軸代表聚類簇,縱軸代表數(shù)據(jù)點(diǎn)到質(zhì)心的距離,圖例分別表示各個(gè)類別。
圖3 聚類結(jié)果展示Fig.3 Comparison of cable tension under different magnitudes
為了檢驗(yàn)本研究所提出的DPCA-K-means 算法的有效性,采用傳統(tǒng)PCA 結(jié)合K-means 算法的PCA-KMeans 和隨機(jī)選擇初始聚類中心的傳統(tǒng)基于歐幾里得距離的Euclidean-K-means算法作對(duì)比實(shí)驗(yàn)分別對(duì)數(shù)據(jù)進(jìn)行聚類,得到準(zhǔn)確率的結(jié)果,如表4。
表4 不同聚類方法驗(yàn)證性對(duì)比Tab.4 Verification comparison of different clustering methods
可以看出DPCA-K-means 算法通過特征多樣性的選取并通過權(quán)重調(diào)整聚類中心選擇,聚類的準(zhǔn)確率較傳統(tǒng)方法有著顯著的提高[24],對(duì)于學(xué)生用戶畫像起到了明顯作用。
通過分析校園一卡通中學(xué)生的行為習(xí)慣,DPCAK-means 算法采用特征選擇和特征加權(quán)方式對(duì)數(shù)據(jù)進(jìn)行聚類分析將學(xué)生劃分為成績好行為規(guī)律且早起的學(xué)霸類型、成績較好行為規(guī)律的潛力類型、成績一般行為不太規(guī)律的普通類型和很少早起且生活不規(guī)律的不努力類型。通過對(duì)比試驗(yàn)可以看出該算法的準(zhǔn)確率最高,可見此算法改進(jìn)對(duì)分析學(xué)生行為有實(shí)用性。但由于一卡通數(shù)據(jù)的有限性,其數(shù)據(jù)不包含學(xué)生進(jìn)出宿舍的數(shù)據(jù),因此未能深入分析此因素對(duì)于成績的影響。接下來的分析將在此基礎(chǔ)上進(jìn)行突破,并增強(qiáng)數(shù)據(jù)的適應(yīng)性功能。