基于PageRank算法的校園好友關(guān)系分析

王全民，趙亞康

(北京工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，北京 100124)

0 引 言

在社會信息化的大背景下，建設(shè)“智慧型”校園，不斷推進(jìn)以學(xué)校為主體的教育信息化進(jìn)程，成為教育信息化的重要組成部分[1]。隨著建設(shè)“智慧校園”理念的興起，國內(nèi)高校信息化建設(shè)開始推廣，各高校普遍經(jīng)歷了校園網(wǎng)絡(luò)建設(shè)階段和以各類信息系統(tǒng)及相關(guān)資源建設(shè)為主的數(shù)字校園建設(shè)階段。這意味著學(xué)生的在校生活“軌跡”可以很好地被記錄下來，也為研究、分析并合理利用學(xué)校學(xué)生大數(shù)據(jù)提供了可能[2-3]。利用數(shù)字化校園產(chǎn)生的海量數(shù)據(jù)去分析學(xué)生的行為特點(diǎn)，挖掘出大數(shù)據(jù)中隱藏的價值，將在很大程度上有助于學(xué)校的日常管理并為學(xué)校領(lǐng)導(dǎo)提供決策依據(jù)。而校園“一卡通”是在大多數(shù)高校功能建設(shè)比較齊全的校園數(shù)字化系統(tǒng)，已經(jīng)滲透到了學(xué)生生活中的方方面面，比如學(xué)生的餐飲、洗浴消費(fèi)，圖書借閱情況，門禁出入管理等，是學(xué)生校園生活軌跡的一個記錄儀。

作為一個特殊的社會群體，當(dāng)代大學(xué)生也面臨許多問題，有對專業(yè)選擇上的迷茫，有對新學(xué)習(xí)環(huán)境新學(xué)習(xí)方式的不適，也存在人際交往能力上的問題以及對未來職業(yè)的選擇問題等等。方方面面的壓力很容易造成學(xué)生的心理問題。良好的交往行為，能建立良好的人際關(guān)系，提供良好的學(xué)習(xí)、生活氛圍，通過好友間的交流及時疏通心理障礙，保證身心健康發(fā)展，促進(jìn)專業(yè)知識的學(xué)習(xí)[4]。因此，挖掘?qū)W生校園中的生活數(shù)據(jù)，了解學(xué)生交友動態(tài)，引導(dǎo)和幫助學(xué)生積極健康學(xué)習(xí)、交友和生活對學(xué)生的成長意義重大[5]。同時找出疑似“孤立”學(xué)生，及時發(fā)現(xiàn)潛在的孤獨(dú)癥學(xué)生，并由輔導(dǎo)員及時的溝通和輔導(dǎo)，有利于構(gòu)造和諧的校園生活。

文中通過對校園一卡通消費(fèi)數(shù)據(jù)的研究分析，發(fā)現(xiàn)學(xué)生交友情況并找出疑似孤獨(dú)癥學(xué)生，為學(xué)校相關(guān)部門的管理提供決策依據(jù)。

1 一卡通消費(fèi)數(shù)據(jù)分析模型

目前，大部分高校的“一卡通”功能建設(shè)趨于成熟，可以較為詳細(xì)地記錄到每個在校學(xué)生的生活軌跡信息。文中所用的數(shù)據(jù)為某高校脫敏后的一卡通消費(fèi)信息，包括食堂、浴室、校園超市等消費(fèi)地點(diǎn)的詳細(xì)信息和消費(fèi)時間以及金額。經(jīng)過數(shù)據(jù)預(yù)處理從中刪除跟研究無關(guān)的用戶群及特征值，之后對數(shù)據(jù)進(jìn)行格式轉(zhuǎn)換，利用高斯相似度分析對學(xué)生的消費(fèi)數(shù)據(jù)進(jìn)行處理生成學(xué)生相互間的關(guān)系矩陣，可以通過這個關(guān)系矩陣找到某學(xué)生關(guān)聯(lián)值較高的同學(xué)，推測其為該生的好友或者有相同作息習(xí)慣的同學(xué)，并為學(xué)生提供好友推薦；基于生成的關(guān)系矩陣，利用PageRank算法對學(xué)生進(jìn)一步進(jìn)行關(guān)聯(lián)度分析，進(jìn)而推測疑似孤獨(dú)癥學(xué)生。分析框架如圖1所示。

圖1 分析模型框架

1.1 數(shù)據(jù)介紹和預(yù)處理

文中需要分析的是學(xué)生的一卡通消費(fèi)數(shù)據(jù)，會預(yù)先刪除教職工的消費(fèi)信息。其次將消費(fèi)地點(diǎn)進(jìn)行聚類后按順序編號，將學(xué)生ID聚類后按順序編號。并將原始數(shù)據(jù)里的消費(fèi)時間轉(zhuǎn)換為數(shù)字編碼。處理后的數(shù)據(jù)格式如下：

第一列為學(xué)生分配的新ID編號，第二列為轉(zhuǎn)化格式便于計(jì)算的消費(fèi)時間，第三列為消費(fèi)金額，第四列為相應(yīng)的消費(fèi)地點(diǎn)。處理后的數(shù)據(jù)集格式如圖2所示。

圖2 數(shù)據(jù)清洗結(jié)果

1.2 高斯相似度分析

高斯分布(Gaussian distribution)又稱正態(tài)分布(normal distribution)，也稱“常態(tài)分布”，而自然界中實(shí)例以及實(shí)例屬性的分布很多情況下都是正態(tài)分布。顯然文中所研究的學(xué)生每一次的消費(fèi)時間概率也滿足正態(tài)分布。那么采用高斯相似度函數(shù)對學(xué)生之間進(jìn)行相似度計(jì)算，也將得到比較有效的實(shí)驗(yàn)結(jié)果。

高斯相似度(Gaussian similarity)表示的是兩個零均值高斯分布間的相似程度，基于這種度量的算法稱為高斯相似度分析(Gaussian similarity analysis，GSA)[6-7]。將每個學(xué)生看成一個點(diǎn)，將所有的點(diǎn)都相互連接起來，就構(gòu)成一個校園學(xué)生關(guān)系圖，同時所有的邊的權(quán)重設(shè)置為相似度。即將任意兩個樣本點(diǎn)之間的高斯相似度形成權(quán)值矩陣。這種高斯相似度函數(shù)能夠較好地反映實(shí)際中的相鄰關(guān)系。

在所研究的數(shù)據(jù)集中，決定學(xué)生關(guān)聯(lián)性的除了同一地點(diǎn)消費(fèi)，還需要考慮消費(fèi)時間，若是經(jīng)常同時就餐，那么兩位學(xué)生之間的消費(fèi)時間差就會很小。學(xué)生i、j的某次消費(fèi)時間分別為vi、vj，兩人之間的消費(fèi)時間差可表示為‖vi-vj‖，則基于時間差的相似度函數(shù)為：

(1)

兩位學(xué)生間的消費(fèi)時間間隔越長，‖vi-vj‖越大，f(x)值越小，表示兩人之間的關(guān)聯(lián)度就越小。將每一次消費(fèi)相似度進(jìn)行累加，得到兩個同學(xué)間的關(guān)聯(lián)值。

1.3 PageRank算法

通過高斯相似度分析，可以得到一個全校由學(xué)生間相似度作為權(quán)值的關(guān)系矩陣。可以通過ID信息檢索得到所屬學(xué)生“好友”推測。但仍需要從這個龐大的校園學(xué)生關(guān)系網(wǎng)中篩選出疑似孤立的學(xué)生，以為相關(guān)管理部分提供有用信息。

PageRank算法是在1998年4月舉行的第七屆國際萬維網(wǎng)大會上由Sergey Brin和Larry Page提出的[8]。隨著對這種算法的深入學(xué)習(xí)，研究者漸漸地從對網(wǎng)頁數(shù)據(jù)的分析擴(kuò)展到了對人群數(shù)據(jù)的研究。Riquelme F等[9]基于用戶間的交互關(guān)系，通過改進(jìn)PageRank算法建立影響力的評估方法；孫紅等[10-11]根據(jù)微博用戶之間的交流關(guān)系利用PageRank模型計(jì)算出微博用戶的影響力；周飛等[12]用PageRank算法計(jì)算網(wǎng)絡(luò)社區(qū)“知乎”用戶的影響值；張欣等[13]結(jié)合專利的被引用次數(shù)和年限對原始的PageRank算法進(jìn)行改進(jìn)來識別核心專利。這些研究都是通過研究對象之間所存在的關(guān)聯(lián)關(guān)系來分析個體在整個研究群體中的價值、影響力或者活躍值。最終找到活躍值最高的、影響力最大的。那么疑似“孤立”學(xué)生的選取也可理解為在校園關(guān)系網(wǎng)中活躍值最低的那位同學(xué)。就可采用該模型去挖掘疑似“孤立”學(xué)生。

PageRank算法的最初目的是通過計(jì)算頁面鏈接的數(shù)量和質(zhì)量來確定網(wǎng)站重要性的粗略估計(jì)，創(chuàng)立之初是應(yīng)用在Google的搜索引擎中，用來標(biāo)識網(wǎng)頁重要性的一種方法，即網(wǎng)頁排名。它是根據(jù)網(wǎng)頁之間的相互鏈接結(jié)構(gòu)實(shí)現(xiàn)的。簡而言之，如果一個網(wǎng)頁可被其他很多個網(wǎng)頁鏈接到，就說明這個網(wǎng)頁比較重要，排名就靠前。算法的表達(dá)式為:

(2)

其中，p1，p2，…，pn表示網(wǎng)頁；M(pi)表示待研究頁面pi的頁面鏈入數(shù)；L(pj)表示頁面pj的頁面鏈出數(shù)；N表示網(wǎng)絡(luò)中的所有頁面數(shù)量；PageRank(Pi)表示頁面pi的PageRank值，所有頁面的PageRank值構(gòu)成網(wǎng)絡(luò)的PageRank向量；q表示用戶繼續(xù)瀏覽該頁面之后的頁面的概率，通常概率值取0.85。

文中將PageRank算法的思想用于校園學(xué)生疑似孤立的預(yù)測。同學(xué)間生成的具有相互關(guān)聯(lián)關(guān)系的矩陣就類似于網(wǎng)絡(luò)有向圖，然后每個學(xué)生就如同要研究的頁面，通過PageRank算法得到每個學(xué)生的PageRank值。與網(wǎng)頁排序同理，如果一個學(xué)生可以被很多學(xué)生聯(lián)系到，證明該生比較活躍，反則，該生社交范圍極小，甚至有可能存在長期孤獨(dú)的狀況。

2 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)分析了該高校一學(xué)期的學(xué)生一卡通消費(fèi)數(shù)據(jù)。首先對每天刷卡時段進(jìn)行聚類分析，根據(jù)刷卡時間分布將一天的消費(fèi)時間分成早、中、晚三個時間段。圖3為時間聚類結(jié)果，由此分布情況將消費(fèi)事件大致劃分為早餐6-10點(diǎn)；中餐10-14點(diǎn)；晚餐14點(diǎn)后，根據(jù)聚類可以將一天分為3個時間片。

圖3 學(xué)生消費(fèi)時間分布

圖4 疑似孤立群年級分配比例

在活躍度排序結(jié)果中取活躍度最低的300名學(xué)生進(jìn)行研究，除去13級延遲畢業(yè)的學(xué)生，活躍度較低群體的年級分布如圖4所示。初步分析，高年級，特別是即將畢業(yè)的學(xué)生，由于找工作和實(shí)習(xí)不在校外的情況會較多，在所分析出來疑似孤立或存在交友問題的學(xué)生群里占得比例較大，低年級大部分時間都在校內(nèi)上課，出現(xiàn)長時間單獨(dú)出現(xiàn)的概率就會較少，在疑似孤立的學(xué)生群體中所占比例就會較小。實(shí)驗(yàn)結(jié)果與預(yù)期的理論分析結(jié)果完全吻合。

圖5 疑似孤立和正常學(xué)生好友情況分析對比

圖5為一個普通學(xué)生與一個疑似孤立學(xué)生與“好友”之間關(guān)聯(lián)值的比較。實(shí)驗(yàn)思路為分別取與這兩位學(xué)生關(guān)聯(lián)值最大的五位同學(xué)，用X坐標(biāo)表示“好友”，Y坐標(biāo)表示該學(xué)生與好友之間的關(guān)聯(lián)度值，那么每個點(diǎn)由所研究學(xué)生與其好友的相似度值大小生成?？梢悦黠@看出，普通學(xué)生與其實(shí)驗(yàn)計(jì)算出的前五名“好友”之間的關(guān)聯(lián)值較大，而“疑似孤立”學(xué)生與其對應(yīng)的前五名“好友”的關(guān)聯(lián)值極其小。這說明該學(xué)生與好友間共同消費(fèi)行為較少，并且經(jīng)常獨(dú)自一人錯峰消費(fèi)。針對出現(xiàn)這種情況的學(xué)生，學(xué)校相關(guān)部門就需要深入了解一下這類學(xué)生的生活學(xué)習(xí)狀態(tài)，針對有交友障礙的學(xué)生提供相應(yīng)的疏導(dǎo)。

3 結(jié)束語

高斯相似度模型被廣泛應(yīng)用于基于相似度矩陣的聚類算法中。比如譜聚類算法，其主要思想就是對樣本數(shù)據(jù)集生成的關(guān)聯(lián)矩陣進(jìn)行聚類，比起傳統(tǒng)的K-means算法對數(shù)據(jù)分布的適應(yīng)性更強(qiáng)[14-15]。文中的高斯相似度函數(shù)，將消費(fèi)時間、地點(diǎn)看成空間上的一個點(diǎn)，每兩個學(xué)生間的消費(fèi)時間間隔較短的邊的權(quán)值較高，這樣可以有效地得出學(xué)生之間的關(guān)聯(lián)程度。而在重要度、影響力排序中有頗多應(yīng)用的PageRank算法可以綜合計(jì)算出學(xué)生在校“影響力”，有助于分析出活躍度極低，疑似交友困難甚至“孤獨(dú)癥”的學(xué)生。

校園中的學(xué)生群體之間會形成一個巨大的關(guān)系圖，為驗(yàn)證實(shí)驗(yàn)結(jié)果，在數(shù)據(jù)源所涉高校相關(guān)部門的幫助下對所分析的結(jié)果進(jìn)行實(shí)體驗(yàn)證，隨機(jī)選取該校學(xué)生進(jìn)行訪問。據(jù)調(diào)研學(xué)生驗(yàn)證，與其關(guān)聯(lián)值較大的同學(xué)大多是其好友或是室友關(guān)系，但也存在生活習(xí)慣相近導(dǎo)致的“熟悉的陌生人”情況的發(fā)生，所以對數(shù)據(jù)一卡通消費(fèi)數(shù)據(jù)的分析可以對有需求的同學(xué)提供一個好友推薦的平臺，通過向其推薦與其生活習(xí)慣相近的同學(xué)來拓展該生的交際圈。

一卡通系統(tǒng)會源源不斷地產(chǎn)生新的、大量的甚至是孤立無序的數(shù)據(jù)，需進(jìn)一步采用科學(xué)合理的算法構(gòu)建數(shù)學(xué)模型，找到數(shù)據(jù)之間的關(guān)聯(lián)，為學(xué)校相關(guān)管理和學(xué)生的健康成長提供更多科學(xué)決策依據(jù)，這些還有待深入研究。