王新澳 段 磊 崔丁山 盧 莉 頓毅杰 秦蕊琦

1(四川大學(xué)計算機學(xué)院 成都 610065)

2(西北民族大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院 蘭州 730030)(wangxinao@stu.scu.edu.cn)

隨著2018年國家標(biāo)準(zhǔn)《智慧校園總體框架》發(fā)布，致力于構(gòu)建校園工作、學(xué)習(xí)和生活一體化的智慧校園正在全國多個高校逐步成型，從課堂到生活的教育理念已經(jīng)被廣為接受.傳統(tǒng)基于預(yù)制定教學(xué)計劃的培養(yǎng)模式已不能滿足當(dāng)前創(chuàng)新性人才的個性化培養(yǎng)需求.以大數(shù)據(jù)分析、人工智能等信息技術(shù)為支撐的智慧教育模式已成為教育信息化的趨勢[1]，通過掌握學(xué)生的興趣、愛好、生活習(xí)慣等，提高人才培養(yǎng)質(zhì)量成為當(dāng)前教育領(lǐng)域的重要研究問題.

生活習(xí)慣是學(xué)生心理狀況、財務(wù)狀況和興趣愛好的綜合體現(xiàn)，對學(xué)生的個人發(fā)展和學(xué)業(yè)表現(xiàn)有著重要的影響.分析學(xué)生的行為，掌握學(xué)生的生活習(xí)慣，對關(guān)愛學(xué)生心理健康、明晰學(xué)生財務(wù)狀況、促進學(xué)生學(xué)業(yè)進步有非常重要的作用.例如:中國礦業(yè)大學(xué)根據(jù)學(xué)生校園生活狀況，建立家庭經(jīng)濟困難學(xué)生數(shù)據(jù)庫，提供精準(zhǔn)資助依據(jù)(1)http://www.moe.gov.cn/jyb_xwfb/s6192/s133/s183/201612/t20161212_291588.html.西安電子科技大學(xué)利用大數(shù)據(jù)分析學(xué)生食堂用餐期間的消費記錄，“隱性地”資助貧困學(xué)生(2)http://www.cpwnews.com/content-22-32315-1.html.

計算學(xué)生生活習(xí)慣的相似性，搜索相似的學(xué)生，可以支持包括下面2種場景的眾多應(yīng)用:

1) 場景1.現(xiàn)有的大學(xué)寢室分配方法較單一，沒有充分考慮學(xué)生的興趣、性格、生活習(xí)慣等方面，容易造成矛盾.通過搜索生活習(xí)慣相似學(xué)生，調(diào)整寢室分配，對促進和諧校園、改善寢室氛圍有著積極的作用.

2) 場景2.學(xué)生進行社團選擇、項目組隊時信息來源較少.搜索與學(xué)生生活習(xí)慣一致的社員或隊友，可以為學(xué)生的選擇提供參考，同時有利于突破學(xué)生自身交際圈促成跨專業(yè)或跨學(xué)院的交流.

本文基于校園行為信息搜索具有相似生活習(xí)慣的學(xué)生.從技術(shù)上講，使用校園行為數(shù)據(jù)分析學(xué)生生活習(xí)慣具有2方面挑戰(zhàn):

1) 學(xué)生在校行為數(shù)據(jù)是多源、異構(gòu)且持續(xù)增長的，包含例如選課、成績、消費、門禁等不同來源和不同結(jié)構(gòu)，并會隨時間逐漸增多數(shù)據(jù).算法設(shè)計過程中需要充分考慮原始數(shù)據(jù)的這些特點.

2) 不同數(shù)據(jù)源之間的語義復(fù)雜，包括自習(xí)(圖書館門禁數(shù)據(jù))、飲食(食堂消費數(shù)據(jù))等.在計算相似性時需要保證語義清晰準(zhǔn)確，即能夠解釋相似的原因.

目前教育數(shù)據(jù)挖掘領(lǐng)域絕大多數(shù)研究的關(guān)注點在于學(xué)生的學(xué)習(xí)過程和學(xué)習(xí)表現(xiàn)以及一些特殊任務(wù)，例如評估抑郁[2]、拖延癥[3]、學(xué)業(yè)預(yù)警[4]或輔助獎助學(xué)金發(fā)放[5-6]等.文獻[7]通過基于LINE的網(wǎng)絡(luò)嵌入方法獲得學(xué)生的低維向量表示，從而計算學(xué)生之間的相似性，但這種方法會損失原始數(shù)據(jù)中包含的語義信息，并且無法拓展性地融合更多的數(shù)據(jù)源.

使用異構(gòu)信息網(wǎng)絡(luò)可以很好地將學(xué)生和行為信息保存在一起.借鑒異構(gòu)信息網(wǎng)絡(luò)的思想和技術(shù)[8]，我們構(gòu)建校園行為信息網(wǎng)絡(luò)(campus behavior infor-mation network)來表達學(xué)生在校行為信息.并且在校園行為信息網(wǎng)絡(luò)中，我們用具有明確語義信息的元路徑度量學(xué)生之間的相似性，從而得到所有學(xué)生之間的相似關(guān)系.目前基于異構(gòu)信息網(wǎng)絡(luò)的相似性度量方法已較為成熟，但因為校園活動數(shù)據(jù)與常用于構(gòu)建異構(gòu)信息網(wǎng)絡(luò)的數(shù)據(jù)不同，具有重復(fù)率高的特點(第2節(jié)做詳細分析)，目前的相似性度量方法并不完全適用于校園行為信息網(wǎng)絡(luò).

同時因為校園行為數(shù)據(jù)多源的特點，在單一數(shù)據(jù)源的行為信息網(wǎng)絡(luò)中提取的相似語義信息往往是片面的.例如，僅使用圖書館的進出記錄無法確定一個學(xué)生是否喜歡上自習(xí)，因為教學(xué)樓同樣具有自習(xí)的功能.因此有必要集成多個網(wǎng)絡(luò)中的相似信息來更全面地體現(xiàn)學(xué)生的在校行為.相應(yīng)地，還需要設(shè)計將多個學(xué)生相似信息融合起來的方法，用于從整體上評判學(xué)生之間的相似性.

對此，本文提出SCALE(similar campus lifestyle miner)算法用于解決在校園行為信息網(wǎng)絡(luò)中搜索生活習(xí)慣相似學(xué)生的問題.主要工作有4個方面:

1) 單層學(xué)生相似子網(wǎng)絡(luò)的構(gòu)建.由單一數(shù)據(jù)源得到校園行為信息網(wǎng)絡(luò)，提出一種帶約束的元路徑相似度計算方法，使用給定的元路徑計算學(xué)生之間的相似度，構(gòu)建單層學(xué)生相似子網(wǎng)絡(luò).

2) 學(xué)生相似網(wǎng)絡(luò)的構(gòu)建.增量式地將單層學(xué)生相似子網(wǎng)絡(luò)構(gòu)建為一個多層結(jié)構(gòu)的學(xué)生相似網(wǎng)絡(luò)，并通過帶偏隨機游走的方式生成每個學(xué)生的上下文語義.

3) 基于網(wǎng)絡(luò)嵌入的相似學(xué)生搜索.使用Skip-Gram模型將所有學(xué)生的上下文語義嵌入到一個低維向量空間中，將每位同學(xué)的相似信息向量化.通過計算向量之間的相似度搜索相似學(xué)生.

4) 通過真實校園環(huán)境數(shù)據(jù)集上的實驗，驗證了SCALE算法的有效性和執(zhí)行效率.

1 問題定義

我們首先引入一些用于表示學(xué)生行為的概念.

考慮到校園行為一般以教學(xué)周為周期迭代進行，我們用時間約束(τ)描述一對時間條件{W(t)=Tdow，T(t)∈Tz}，其中Tdow表示1周中的某一天，Tz表示1天中的某個時間區(qū)間.滿足此約束的時間t記作tτ.例如{W(t)=Monday，T(t)∈[11:00，13:00)}為一個具體的時間約束.

滿足同一個時間約束且在相同地點發(fā)生的同類型事件實例的集合體現(xiàn)了相似的行為，由一個行為實例表示，記作時間約束(τ)，地點(l)，事件類型(c).對于tτ，l=l，c=c，都有t，l，c∈τ，l，c.

例1.有屬于學(xué)生1和學(xué)生2的3個事件實例.

對于時間約束τ:{W(t)=Monday,T(t)∈[11:00，13:00)},t1,t2滿足時間約束τ,而t3不滿足τ.因此,學(xué)生1的2個事件實例均屬于同一個行為實例{W(t)=Monday,T(t)∈[11:00,13:00)},一食堂,就餐.且學(xué)生1參與了此行為實例2次,學(xué)生2沒有參與此行為實例.

校園行為信息網(wǎng)絡(luò)包含了5種典型的對象類型:學(xué)生(s)、時間約束(τ)、地點(l)、事件類型(c)、行為實例(b).時間約束、地點及事件類型為行為實例的屬性.網(wǎng)絡(luò)還包括4種類型的鏈接:學(xué)生與行為實例之間具有參與幾次或者被參與幾次的關(guān)系,行為實例和時間約束之間存在“發(fā)生”或者“發(fā)生在”的關(guān)系,行為實例和地點之間存在處于或發(fā)生的關(guān)系,行為實例與事件類型之間存在屬于或包含的關(guān)系.容易看出,校園行為信息網(wǎng)絡(luò)是一個帶權(quán)重的異構(gòu)信息網(wǎng)絡(luò)[9],包含了4種權(quán)重類型.學(xué)生與行為實例之間鏈接的權(quán)重為學(xué)生參與此行為實例的次數(shù),時間約束、地點和事件類型為行為實例的屬性,它們與行為實例之間鏈接的權(quán)重均為1，且任一行為實例必須與其對應(yīng)的時間約束、處于的地點及屬于的事件類型對象相連.圖1為校園行為信息網(wǎng)絡(luò)的一個示例,時間約束、地點、事件類型與行為實例之間鏈接的權(quán)重被省略.

Fig.1 An example of campus behavior information network

在校園行為信息網(wǎng)絡(luò)中,2個對象可以通過多條不同的路徑相連,連接2個對象的某一條路徑蘊含了這2個對象之間的某種語義關(guān)系,且不同路徑表達著不同的語義關(guān)系,稱這些路徑為元路徑,記作P.若元路徑P上的鏈接帶有權(quán)重,則P為帶權(quán)重元路徑[9].

若校園信息網(wǎng)絡(luò)中存在1條與元路徑P的對象類型和鏈接類型全部對應(yīng)的路徑p,則稱p為元路徑P的實例,記作p∈P.

考慮元路徑P:“學(xué)生—行為實例—地點—行為實例—學(xué)生”,在要求路徑中對象不重復(fù)的情況下,圖1中存在著2條元路徑P的實例.p1:“s1—b3—l2—b2—s3”;p2:“s2—b3—l2—b2—s3”.

在校園行為信息網(wǎng)絡(luò)中使用元路徑查找相似語義時,存在不同類型行為的路徑并不能表達相似,因此要求元路徑中出現(xiàn)的行為實例為相同事件類型.具有較強相似語義信息的元路徑有3條:

1) “學(xué)生—行為實例—時間約束—行為實例—學(xué)生”.2個學(xué)生在相同的時間約束下具有相同類型的行為,例如圖1中包含的實例“s1—b3—τ3—b4—s4”,語義為s1和s4在相同的時間約束(τ3)下有相同類型的行為(b3,b4的事件類型同為c2).

2) “學(xué)生—行為實例—地點—行為實例—學(xué)生”.2個學(xué)生在相同的地點具有同樣類型的行為,例如圖1中包含的實例“s1—b3—l2—b2—s3”,語義為s1和s3在相同的地點(l2)有同樣類型的行為(b2,b3的事件類型同為c2).

3) “學(xué)生—行為實例—學(xué)生”.2個學(xué)生在相同的時間約束下和相同的地點有相同的行為,例如圖1中包含的實例“s1—b3—s2”,等價于同時存在前2種元路徑的情況,即同時存在實例“s1—b3—τ3—b3—s2”和“s1—b3—l2—b3—s2”,語義為s1和s2在相同的時間約束(τ3)下和地點(l2)中有相同的行為(b3的事件類型為c2).

可以發(fā)現(xiàn),上面3種元路徑與其反向的元路徑是相同的,我們稱這種元路徑為對稱元路徑[8].對于一個給定的對稱元路徑P,文獻[8]給出了2個相同類型對象os和ot之間基于實例數(shù)的元路徑相似性度量方式PathSim.

Sim(os,ot,P)=

(1)

其中,pos?ot表示os和ot之間的路徑實例,pos?os表示os和os之間的路徑實例,pot?ot表示ot和ot之間的路徑實例.

例2.對于圖1中的校園行為信息網(wǎng)絡(luò)G和元路徑P:“學(xué)生—行為實例—學(xué)生”.學(xué)生1(s1)與學(xué)生2(s2)之間的Pathsim相似度計算如下:

1) 學(xué)生1與學(xué)生2之間元路徑P的實例有2條,分別為“s1—b1—s2”和“s1—b3—s2”,因此|{ps1?s2|ps1?s2∈P}|=2.

2) 學(xué)生1與學(xué)生1之間元路徑P的實例有2條,分別為“s1—b1—s1”和“s1—b3—s1”,因此|{ps1?s1|ps1?s1∈P}|=2.

3) 學(xué)生2與學(xué)生2之間元路徑P的實例有2條,分別為“s2—b1—s2”和“s2—b3—s2”,因此|{ps2?s2|ps2?s2∈P}|=2.

4) 因此,Sim(s1,s2,P

通過基于元路徑的相似度計算方式,我們可以基于給定元路徑從校園行為信息網(wǎng)絡(luò)中計算得到所有學(xué)生之間的相似度.以學(xué)生作為節(jié)點、相似度作為權(quán)重，構(gòu)建單層學(xué)生相似子網(wǎng)絡(luò).單層學(xué)生相似子網(wǎng)絡(luò)是一個無向帶權(quán)重圖B=(S,),其中每個節(jié)點s∈S代表1個學(xué)生,每條邊e∈連接2個相似的學(xué)生,e上帶有的屬性w代表2個學(xué)生的相似度.

但是獲得多個子網(wǎng)絡(luò)之后,單層學(xué)生相似子網(wǎng)絡(luò)的權(quán)重并不能表達學(xué)生之間的相似度.因此為了度量學(xué)生在多個子網(wǎng)絡(luò)中表現(xiàn)出的相似性,我們構(gòu)建多層結(jié)構(gòu)的學(xué)生相似網(wǎng)絡(luò)并使用網(wǎng)絡(luò)嵌入的方法得到學(xué)生的向量表示,從而通過計算向量之間的距離得到學(xué)生之間的相似性.

2 相關(guān)工作

本文基于異構(gòu)信息網(wǎng)絡(luò),以信息網(wǎng)絡(luò)的形式重構(gòu)校園行為數(shù)據(jù),構(gòu)建了校園行為信息網(wǎng)絡(luò),使用結(jié)合元路徑方法的網(wǎng)絡(luò)嵌入方法來研究校園行為信息網(wǎng)絡(luò)中的相似搜索.因此,本節(jié)將從基于異構(gòu)信息網(wǎng)絡(luò)的相似性度量和教育數(shù)據(jù)挖掘2個方面介紹本文的相關(guān)工作.

2.1 基于異構(gòu)信息網(wǎng)絡(luò)的相似性度量

異構(gòu)信息網(wǎng)絡(luò)被定義為由多種類型的實體和關(guān)系構(gòu)成的網(wǎng)絡(luò).區(qū)別于傳統(tǒng)的網(wǎng)絡(luò),異構(gòu)信息網(wǎng)絡(luò)包含了不同的類別信息,它們能用來表達路徑中豐富的語義信息.因此在大部分現(xiàn)實場景下,異構(gòu)信息網(wǎng)絡(luò)更適合用于對現(xiàn)實世界進行抽象表示.近些年,為了研究復(fù)雜網(wǎng)絡(luò)中節(jié)點之間豐富的聯(lián)系,基于異構(gòu)信息網(wǎng)絡(luò)的數(shù)據(jù)挖掘任務(wù)成為了研究熱點,其中包括聚類[10]、分類[11]、鏈接預(yù)測[12]和相似搜索[13]等.比如,Sun等人[10]將元路徑與融入了用戶偏好的聚類相結(jié)合,從而對網(wǎng)絡(luò)中對象聚類;Ji等人[11]基于在1個類中排位更高對象應(yīng)該有更重要作用的思想,提出了基于排序的分類方法RankClass;Kuo等人[12]通過綜合的統(tǒng)計方法,將異構(gòu)信息網(wǎng)絡(luò)中不同類別的信息建模到一個多層的圖中,并推理出隱藏的鏈接.侯泳旭等人[13]構(gòu)建了包含疾病、基因和病癥節(jié)點的疾病信息網(wǎng)絡(luò),并設(shè)計了基于元路徑的相似基因搜索算法gSim_Miner.在這些任務(wù)中,異構(gòu)信息網(wǎng)絡(luò)的相似性度量是一個基本并且重要的功能.在下文中,我們將總結(jié)異構(gòu)信息網(wǎng)絡(luò)的相似性度量的相關(guān)工作.

不少研究者已經(jīng)意識到基于異構(gòu)信息網(wǎng)絡(luò)的相似性度量的重要性.Ni等人[14]在利用科學(xué)文獻中豐富的元數(shù)據(jù)構(gòu)建有向圖的基礎(chǔ)上,設(shè)計了一個有路徑約束的隨機游走算法(path-constrained random walks, PCRW)來測量任意類型節(jié)點對之間的相似性.Sun等人[8]考慮到不同類型對象組成的元路徑能表達語義,提出了PathSim算法,該算法通過對稱的元路徑計算2個相同類型對象之間的相似性.Shi等人[15]結(jié)合PCRW和PathSim算法,設(shè)計了HeteSim算法,通過用戶給定的任意的元路徑計算相同或不同類型的對象相關(guān)性.注意：校園行為信息網(wǎng)絡(luò)與其他常見的異構(gòu)信息網(wǎng)絡(luò)存在不同,學(xué)生常在幾個固定的場所活動,很少前往沒有去過的地點,且對于熟悉的地點,學(xué)生通常會頻繁前往,即重復(fù)率高,所以在校園信息網(wǎng)絡(luò)中需要以邊上權(quán)重的方式存儲學(xué)生與某地之間產(chǎn)生聯(lián)系的頻度,且一般情況下權(quán)重會比較高.若使用以上的方法計算元路徑相似度,邊上的權(quán)重信息就會被丟失,例如偶爾去1次圖書館和經(jīng)常出入圖書館會被相似度評價方法視作相同的行為.因此以上方法不適用于本問題.近年來,Shi等人[9]介紹了SemRec算法,并提出用帶有權(quán)重的元路徑來精細地描述路徑語義,在計算實例數(shù)時要求對稱的2個關(guān)系所具有的權(quán)重相等,從而保證被計算的實例能夠表達2個對象之間相似的語義.但是SemRec適用于評分的場景,對于重復(fù)率高的校園數(shù)據(jù)來說,只計算權(quán)重相等的實例太過嚴格,會丟失過多的語義.

網(wǎng)絡(luò)嵌入是將對象嵌入到低維稠密的向量空間中的技術(shù),能有效捕捉對象的重要信息.因此,許多研究工作將基于元路徑的方法融入網(wǎng)絡(luò)嵌入來得到節(jié)點唯一的向量表達.Metapath2vec[16]和HIN2Vec[17]通過元路徑的隨機游走得到節(jié)點的序列,并結(jié)合Skip-gram模型從而得到網(wǎng)絡(luò)節(jié)點的嵌入.HEBE[18]提出了異構(gòu)信息網(wǎng)絡(luò)中事件的概念,它將參與同一個事件的對象看為1個整體,即1個事件,并用超邊表示對象之間的多種關(guān)系,從而得到對象的近似.TransPath[19]借用了知識圖譜中的平移機制的思想,將元路徑當(dāng)作源結(jié)點到目標(biāo)節(jié)點的平移操作,用于得到元路徑和節(jié)點的嵌入.但是此類方法的拓展性普遍較差,在融合更多數(shù)據(jù)源的數(shù)據(jù)時已有的計算結(jié)果將被全部重新計算.

2.2 教育數(shù)據(jù)挖掘

近年來,由于學(xué)生相關(guān)數(shù)據(jù)越來越多,教育數(shù)據(jù)挖掘(educational data mining, EDM)已成為一個新興的跨學(xué)科研究領(lǐng)域.EDM指在教育環(huán)境中利用數(shù)據(jù)挖掘的技術(shù)解決實際的教育教學(xué)問題,從而改善和提高學(xué)生學(xué)習(xí)質(zhì)量,完善學(xué)習(xí)過程與教育管理[20].

在教育數(shù)據(jù)挖掘中,大部分研究關(guān)注于學(xué)生的學(xué)習(xí)過程[21-26]和學(xué)習(xí)表現(xiàn)[27-33].這些方法通過分析線下或線上的學(xué)習(xí)活動所產(chǎn)生的數(shù)據(jù)來進行建模,從而研究和預(yù)測學(xué)生的學(xué)習(xí)行為和學(xué)習(xí)成績.除了學(xué)生的學(xué)習(xí)過程和學(xué)習(xí)表現(xiàn),校園生活等也引起了研究者的注意.Resnik等人[2]分析對大學(xué)生的問卷調(diào)查,使用文本分析主題建模以預(yù)測學(xué)生中的抑郁者.Zhu等人[3]提出了一個從行為畫像到預(yù)測抑郁的無監(jiān)督學(xué)習(xí)模型(動態(tài)RP),該模型通過分析大學(xué)生在圖書館的借閱記錄來評估學(xué)生的拖延癥.Sattar等人[4]介紹了一個框架,該框架利用了多組不同類型的變量,包括了家庭背景、中學(xué)信息、注冊登記和學(xué)分,以預(yù)測學(xué)生退學(xué)的概率.Ye等人[5]給出了多模型多標(biāo)簽的方法,來輔助大學(xué)提供學(xué)生獎學(xué)金和補助金的分配.Guan等人[6]設(shè)計了Dis-HARD框架,用于預(yù)測學(xué)生應(yīng)給的補助等級.Hang等人[7]將學(xué)生的Check-In數(shù)據(jù)(WIFI訪問日志)整合到二部圖,并編碼學(xué)生、興趣點(point of interest, POI)和活動之間的相關(guān)性,用以預(yù)測POI、查詢相似學(xué)生.

據(jù)我們所知,在教育環(huán)境下的研究工作只有文獻[7]針對有著相似生活行為學(xué)生的搜索,與本文最為相似.但文獻[7]提出的算法基于LINE進行向量嵌入,計算時會丟失語義信息,并且無法拓展性地融合更多數(shù)據(jù)源.本文將在實驗部分與文獻[7]提出的算法進行對比.

3 SCALE—生活習(xí)慣相似學(xué)生搜索

SCALE是基于校園行為信息網(wǎng)絡(luò)的生活習(xí)慣相似學(xué)生搜索算法.學(xué)生的校園行為是多種多樣的,因此描述學(xué)生在校行為的數(shù)據(jù)也是多源的,對于單個數(shù)據(jù)源可以構(gòu)建出一個校園行為信息網(wǎng)絡(luò),通過給定的元路徑能得到單層學(xué)生相似子網(wǎng)絡(luò).顯然,單層學(xué)生相似子網(wǎng)絡(luò)所包含的信息是片面的,無法從整體上對學(xué)生之間的相似性進行表達.因此需要構(gòu)建多層結(jié)構(gòu)的學(xué)生相似網(wǎng)絡(luò),并使用網(wǎng)絡(luò)嵌入的方法將所有學(xué)生映射到低維的向量空間中,從而使相似學(xué)生搜索問題得到簡化.

圖2展示了SCALE算法的主要流程.

Fig.2 Algorithm flow introduction of SCALE

3.1 單層學(xué)生相似子網(wǎng)絡(luò)的構(gòu)建

根據(jù)不同的數(shù)據(jù)源,構(gòu)建校園行為信息網(wǎng)絡(luò)的方式有很多種.對于行為信息來說,我們首先可以把學(xué)生的所有事件劃分為多個獨立的行為實例,用行為實例作為事件實例的載體保存在網(wǎng)絡(luò)中.同時,為保證能夠在網(wǎng)絡(luò)的元路徑中提取到明確的語義,我們按如下方式構(gòu)建校園行為信息網(wǎng)絡(luò):

1) 根據(jù)校園生活存在的周期性和具體情況設(shè)置時間約束.不失一般性,我們采用與文獻[7]相同的方式將所有的時間劃分到以1周7天為周期,每天4個時間段(從0點開始,每6 h為1個時間段)所組成的28個時間約束中.

2) 將同一個時間約束下,同一個地點發(fā)生的相同類型的事件實例保存在同一個行為實例對象中存入校園行為信息網(wǎng)絡(luò).并與對應(yīng)的時間約束、地點和事件類型對象相連,鏈接的權(quán)重為1.

3) 將每個學(xué)生作為1個對象存入網(wǎng)絡(luò),并與參與的行為實例對象相連,鏈接的權(quán)重為參與的次數(shù).

自然地,所有的行為實例都具有時間約束、地點及事件類型屬性.因此上述的校園行為信息網(wǎng)絡(luò)構(gòu)建方式對于所有的校園行為都適用.但校園行為信息網(wǎng)絡(luò)的表達能力是可拓展的.針對一些具有特殊屬性的行為實例,也可以將這些屬性作為節(jié)點加入到校園行為信息網(wǎng)絡(luò)中,使網(wǎng)絡(luò)包含更豐富的語義.例如,對于學(xué)生的消費行為,可以將“消費金額范圍”作為行為實例的屬性存儲在校園行為信息網(wǎng)絡(luò)中,從而使元路徑“學(xué)生—行為實例—消費金額范圍—行為實例—學(xué)生”表達2個學(xué)生消費金額相近的語義.

根據(jù)上述的方式在單數(shù)據(jù)源下構(gòu)建校園行為信息網(wǎng)絡(luò)后,我們可以通過基于元路徑的相似性度量方式計算學(xué)生之間在此網(wǎng)絡(luò)中的相似度.本文提出一種基于權(quán)重相似度的方式對元路徑的實例數(shù)進行計算.

(2)

(3)

(4)

使用帶約束的元路徑相似度計算公式可以得到所有學(xué)生相互之間的相似度值,從而構(gòu)建學(xué)生相似子網(wǎng)絡(luò).

例3.對于圖1中展示的校園行為信息網(wǎng)絡(luò)G,給定元路徑P:“學(xué)生—行為實例—地點—行為實例—學(xué)生”及權(quán)重相似度閾值α=2.構(gòu)建基于(G,P)的單層學(xué)生相似子網(wǎng)絡(luò)的步驟為:

3) 同理,s1與s2之間有2條元路徑實例,s4與其他學(xué)生對象之間無元路徑實例.s1,s2,s3與自身之間分別有2條、2條、1條元路徑實例.

4) 使用wij代表si與sj的相似度,有

5)s4與其他學(xué)生對象之間的相似度均為0.

以每一個學(xué)生作為對象,學(xué)生之間相似度作為鏈接的權(quán)重,構(gòu)建基于(G,P)的單層學(xué)生相似子網(wǎng)絡(luò).

3.2 學(xué)生相似網(wǎng)絡(luò)的構(gòu)建

單層學(xué)生相似子網(wǎng)絡(luò)只反映了從1個數(shù)據(jù)源中通過1條元路徑語義表達的學(xué)生相似性,將得到的多個單層學(xué)生相似子網(wǎng)絡(luò)整合起來,形成1個多層結(jié)構(gòu)的學(xué)生相似網(wǎng)絡(luò).因為每個學(xué)生一定是和自身完全相似的,所以通過權(quán)重為1的邊將多層網(wǎng)絡(luò)中相同的學(xué)生對象連接起來.從而獲得1個多層的網(wǎng)絡(luò)結(jié)構(gòu)表達學(xué)生之間的相似關(guān)系.

SCALE在學(xué)生相似網(wǎng)絡(luò)中采取帶偏的隨機游走算法生成每個學(xué)生的上下文語義.因為網(wǎng)絡(luò)是多層的,因此隨機游走的過程中會出現(xiàn)2種情況:1)算法根據(jù)隨機生成的概率選擇留在本層,以更大概率游走到和當(dāng)前節(jié)點更相似的節(jié)點,即與當(dāng)前節(jié)點由更大權(quán)重的邊相連的節(jié)點;2)算法選擇游走到網(wǎng)絡(luò)中的其他層,則此步不再做其他操作.通過上述的隨機游走算法,可以為每一個學(xué)生生成1個由相似節(jié)點組成的序列,表達其他節(jié)點與當(dāng)前節(jié)點之間的相似關(guān)系.

3.3 基于網(wǎng)絡(luò)嵌入的相似學(xué)生搜索

通過帶偏的隨機游走算法在學(xué)生相似網(wǎng)絡(luò)中獲得每個學(xué)生與其他學(xué)生的相似關(guān)系之后,SCALE采用Skip-Gram模型對所有的隨機游走序列進行嵌入學(xué)習(xí).從而將所有學(xué)生映射到1個低維的向量空間中,使得每個學(xué)生嵌入的向量保留了學(xué)生相似網(wǎng)絡(luò)中體現(xiàn)的相似性.

得到所有學(xué)生的向量表示之后,對于每一個查詢學(xué)生,利用余弦相似度計算此學(xué)生向量與其他所有向量之間的距離,得到距離最小的k個向量,所對應(yīng)的k個學(xué)生即為SCALE的搜索結(jié)果.

需要注意的是,SCALE在單層學(xué)生相似子網(wǎng)絡(luò)構(gòu)建時采用基于帶約束的元路徑相似度計算方法度量節(jié)點間相似性,在學(xué)生相似網(wǎng)絡(luò)生成上下文語義和網(wǎng)絡(luò)嵌入時使用帶偏隨機游走和Skip-Gram模型將學(xué)生映射到低維向量.在其他的應(yīng)用中,可以根據(jù)使用場景,更換上述度量方式或表達學(xué)習(xí)方法.

SCALE算法的整體流程如算法1所示.

算法1.SCALE算法.

③ 計算G中每一對學(xué)生的PathSimC(si,sj,P);

④N←由G構(gòu)建的單層學(xué)生相似子網(wǎng)絡(luò);

⑥ END FOR

3.4 并行化

SCALE算法有3處是可解耦的,因此可以針對本算法設(shè)計并行化處理方法,從而提高算法效率.

1) 學(xué)生相似度計算.在構(gòu)建學(xué)生相似網(wǎng)絡(luò)的過程中,需要對任意2個學(xué)生之間計算相似度.而不同對學(xué)生之間計算相似度的過程是互不影響的,因此在學(xué)生相似度計算時,即單層學(xué)生相似子網(wǎng)絡(luò)的構(gòu)建過程中可以使用多進程(線程)提升程序運行效率.

2) 學(xué)生相似網(wǎng)絡(luò)構(gòu)建.構(gòu)建不同的學(xué)生相似子網(wǎng)絡(luò)的過程是相互獨立的,在相似網(wǎng)絡(luò)構(gòu)建的過程中網(wǎng)絡(luò)之間不會互相影響,因此可以使用多進程(線程)完成學(xué)生相似網(wǎng)絡(luò)的構(gòu)建過程.

3) 構(gòu)建學(xué)生相似網(wǎng)絡(luò)之后,需要針對每個學(xué)生使用帶偏隨機游走算法生成大量的隨機游走序列,此處可用2個思路實現(xiàn)并行化:①每個進程(線程)都對所有的學(xué)生生成部分隨機游走序列,全部運行完成后將結(jié)果進行拼接得到1個學(xué)生所有的隨機游走序列.②每個進程(線程)只對部分學(xué)生生成所有的隨機游走序列,全部運行完成后得到所有學(xué)生的隨機游走序列.

同時,因為SCALE算法構(gòu)建學(xué)生相似網(wǎng)絡(luò)的過程是解耦的,因此SCALE算法是一個可拓展的方法.當(dāng)添加新的數(shù)據(jù)源或元路徑時,只需將新獲得的單層學(xué)生相似子網(wǎng)絡(luò)加入到之前已經(jīng)構(gòu)建好的學(xué)生相似網(wǎng)絡(luò)中即可進行后續(xù)計算.之前計算得到的學(xué)生相似網(wǎng)絡(luò)無需重新進行計算,由此節(jié)約了運算資源.

4 實 驗

本文利用真實的數(shù)據(jù)集驗證校園行為信息網(wǎng)絡(luò)的適用性和相似學(xué)生搜索算法SCALE的有效性以及執(zhí)行效率.實驗源碼存放于https:github.comhdwxaSCALE.git.

4.1 數(shù)據(jù)集介紹及實驗設(shè)置

本文使用2018年3月1日—11月30日期間,四川大學(xué)3個校區(qū)內(nèi)采集到的6個不同學(xué)院共2 449名學(xué)生在校行為數(shù)據(jù)進行本次實驗.該數(shù)據(jù)包含2個數(shù)據(jù)源:1)后勤集團數(shù)據(jù)(source1).學(xué)生在校園內(nèi)食堂、便利店及澡堂等地點的消費記錄,共包含1 276 806個事件實例.2)保衛(wèi)處數(shù)據(jù)(source2).學(xué)生進出教學(xué)樓、球場、寢室樓的門禁記錄,共包含752 361個事件實例.表1分別展示了相關(guān)的事件實例數(shù)為Top-5的地點和事件類型,及它們對應(yīng)的事件實例數(shù).

Table 1 Top-5 Locations and Event Types with Highest Number of Event Instances

表2列出了通過每個數(shù)據(jù)源構(gòu)建的校園信息網(wǎng)絡(luò)的具體規(guī)模.

Table 2 Size of Campus Behavior Information Networks

為驗證SCALE算法的有效性和執(zhí)行效率,本文在真實數(shù)據(jù)集上運行SCALE算法,挖掘Top-k生活習(xí)慣相似學(xué)生.從有效性測試、模型簡化測試以及應(yīng)用實例3方面說明SCALE算法的有效性.并驗證SCALE算法采取的并行化策略對執(zhí)行效率的提升效果.

4.2 SCALE有效性測試

與本文工作相似的最新工作是由文獻[7]提出的EDHG算法,對于給定的查詢學(xué)生s、向量嵌入維度d和負采樣個數(shù)m,EDHG可以找到Top-k個相似學(xué)生,但無法提供對結(jié)果相似的語義解釋.

同時,本文還將校園行為信息網(wǎng)絡(luò)轉(zhuǎn)化為矩陣的形式記錄學(xué)生在2個數(shù)據(jù)源中參與某個事件類型、時間約束和地點的行為實例的次數(shù),針對每位學(xué)生構(gòu)建9×28×101的3維張量.其中后勤集團數(shù)據(jù)包含6種事件類型及44個地點,保衛(wèi)處數(shù)據(jù)包含3種事件類型及57個地點,時間約束個數(shù)均為28.通過主成分分析得到每位學(xué)生在事件類型、時間約束和地點維度上的第1主成分作為每位學(xué)生的向量表示,以此搜索Top-k的相似學(xué)生,與SCALE算法進行效果對比,從而說明SCALE算法獲取校園行為信息網(wǎng)絡(luò)中信息的準(zhǔn)確性.3種算法分別記為PCA-c,PCA-τ,PCA-l.

文獻[7]提出使用共現(xiàn)行為,即2位學(xué)生在很短的時間內(nèi)(本次實驗設(shè)置為2 min)同時出現(xiàn)在同一個地點,作為學(xué)生之間是否在行為上相似的一種評判方式.2位學(xué)生之間共現(xiàn)行為越多,則這2位學(xué)生生活習(xí)慣就更為相似.本文采取與文獻[7]相同的方式作為評估模型效果的指標(biāo).以共現(xiàn)行為最高的k個學(xué)生為標(biāo)準(zhǔn),對SCALE算法找到的Top-k個相似學(xué)生使用平均相關(guān)排名(mean reciprocal rank,MRR)進行評估.平均相關(guān)排名的計算方式為

(5)

其中,U為全部查詢學(xué)生的集合,Fi為使用共現(xiàn)行為找出學(xué)生i的|Fi|=k個相似生活習(xí)慣的學(xué)生,Rank(j)為學(xué)生j由SCALE算法計算出的排名.MRR得分越高,說明SCALE算法的效果越好.

實驗過程中,SCALE算法需要設(shè)置的參數(shù)有：每次查詢搜索的相似生活習(xí)慣學(xué)生個數(shù)k、計算學(xué)生相似度時的權(quán)重相似度閾值α、多層學(xué)生相似網(wǎng)絡(luò)中對每個節(jié)點產(chǎn)生隨機游走序列的個數(shù)n,以及使用Skip-Gram模型進行向量嵌入的維度d.為保證提取的相似語義充分且不重復(fù),實驗在元路徑“學(xué)生—行為實例—學(xué)生”上計算相似度.表3記錄了將四川大學(xué)學(xué)生在校行為數(shù)據(jù)分別應(yīng)用于PCA-c,PCA-τ,PCA-l,EDHG算法和SCALE算法得到的結(jié)果.

Table 3 MRR Scores

在表3中可以看出,在k=2時,SCALE算法和EDHG算法的效果相近,且都比PCA-c,PCA-τ,PCA-l效果好.隨著k的增大,5種算法的MRR得分都呈現(xiàn)增長趨勢,并且SCALE算法的得分始終高于其他4種算法,說明本文提出的SCALE算法在尋找相似生活習(xí)慣學(xué)生的任務(wù)上比其他4種算法效果更好.在k=10時,SCALE算法相對于PCA-c,PCA-τ,PCA-l,EDHG算法的效果提升分別達到了391%,115%,70.3%,65.4%.同時可以發(fā)現(xiàn),在k增大時,SCALE算法相對于其他4種算法效果提升得更為明顯,說明SCALE算法的效果在k取較大的值時更有優(yōu)勢.

Fig. 3 Influence on SCALE with respect to parameters

圖3(a)～(c)分別展示了在完整數(shù)據(jù)集下參數(shù)α,n,d對于SCALE算法效果的影響.圖3(a)中可以看出,隨著權(quán)重相似度閾α變大,算法的效果呈現(xiàn)先升后降的趨勢,在α=1.4時,SCALE算法取得最好的效果,因此默認情況下設(shè)置α=1.4.由圖3(b)可以看出隨著每個節(jié)點產(chǎn)生隨機游走序列個數(shù)n的增大,SCALE的效果也逐漸變好,但當(dāng)n由128增大至256時,模型效果的提升很微弱,因此本次實驗?zāi)J將n設(shè)置為128.由圖3(c)觀察可知,當(dāng)d=32時SCALE效果最好,因此默認設(shè)置d=32.

4.3 模型簡化測試

在圖3(a)中,當(dāng)權(quán)重相似度閾值α=1時,PathSimC等價于文獻[9]提出的算法,當(dāng)α為正無窮時,PathSimC等價于PathSim算法,SCALE算法的效果在α=1.4時獲得最好效果,說明PathSimC相對于之前的方法可以更好地保留學(xué)生之間相似生活習(xí)慣的信息.

我們還將沒有構(gòu)建多層學(xué)生相似網(wǎng)絡(luò)的單數(shù)據(jù)源Na?ve算法與SCALE算法進行對比,說明在多數(shù)據(jù)源情況下使用SCALE算法的有效性.在本實驗中,使用消費數(shù)據(jù)和門禁數(shù)據(jù)的Na?ve算法分別記為Na?ve-C和Na?ve-E,對比結(jié)果記錄在圖3(d)中.可以看出,SCALE算法的效果始終好于2種Na?ve算法,說明使用多層結(jié)構(gòu)的學(xué)生相似網(wǎng)絡(luò)可以更好地保留多數(shù)據(jù)源中的學(xué)生生活習(xí)慣信息.

4.4 應(yīng)用實例

SCALE算法使用的相似度計算方法是基于元路徑的,因此SCALE算法相對于EDHG算法的另一個優(yōu)點就是還保留了原始數(shù)據(jù)中的語義信息.本實驗展示2種應(yīng)用場景下SCALE算法的Top-k搜索結(jié)果.

1) 在消費和門禁2個數(shù)據(jù)源中都使用元路徑“學(xué)生—行為實例—學(xué)生”計算相似度.相似度高的學(xué)生說明他們更傾向于在同一時間、同一地點產(chǎn)生相同的行為.

2) 僅使用消費數(shù)據(jù)源,將“消費金額范圍”作為行為實例的屬性存儲在校園行為信息網(wǎng)絡(luò)中,使用元路徑“學(xué)生—行為實例—消費金額范圍—行為實例—學(xué)生”和元路徑“學(xué)生—行為實例—地點—行為實例—學(xué)生”計算相似度,相似度高的學(xué)生說明他們消費金額相近且喜歡去相同的地方消費,即消費能力相似.

本文隨機抽取了3位學(xué)生,并展示針對他們搜索得到的Top-10相似的學(xué)生來說明結(jié)果的合理性.為方便對比,展示時使用“專業(yè)—班號—學(xué)號后2位”代替學(xué)號.由表4的結(jié)果可以看出,在第1種應(yīng)用場景下,尋找到的相似學(xué)生絕大多數(shù)都是相同專業(yè)甚至是相同班級的學(xué)生,這是因為相同專業(yè)和班級學(xué)生的上課時間安排及主要活動區(qū)域是一致的,因此他們更傾向于在相同時間前往相同的教學(xué)樓、食堂、宿舍等區(qū)域,說明SCALE算法在計算相似性時成功捕獲了此類信息.同時我們可以發(fā)現(xiàn)一些有趣的現(xiàn)象:第2位和第3位查詢學(xué)生在其搜索到的相似學(xué)生中都各自出現(xiàn)了1個非本專業(yè)的學(xué)生.我們通過查看以上學(xué)生的基本信息,發(fā)現(xiàn)第2位同學(xué)與其相似的非本專業(yè)相似學(xué)生性別都為女性,我們推測她們可能是好友.第3位同學(xué)與其相似的非本專業(yè)同學(xué)為不同性別(與其他相似同學(xué)均為同性別),推測他們可能是情侶.

Table 4 Top-10 Similar Students Found by SCALE

而在第2種應(yīng)用場景下,不再出現(xiàn)大多數(shù)相似學(xué)生專業(yè)、班級甚至性別屬性相同的情況.這和常識相符,因為第2種場景下元路徑所表達的語義為消費能力相似,與專業(yè)、班級或性別屬性的相關(guān)性較小.

可見SCALE算法具有很好的靈活性,根據(jù)語義設(shè)置不同的元路徑可以獲取學(xué)生之間不同的相似性.

4.5 SCALE執(zhí)行效率

為了驗證SCALE算法并行化策略對效率的提升效果,本文使用不采取并行化策略的SCALE-Ser算法和使用了并行化策略的SCALE算法在不同數(shù)據(jù)規(guī)模下對比執(zhí)行時間.同時驗證SCALE算法在數(shù)據(jù)規(guī)模上的拓展性，本實驗在合成數(shù)據(jù)集上完成.

若無特殊說明,實驗過程中參數(shù)設(shè)置與有效性實驗中保持一致.并行化使用最大進程數(shù)為10的進程池實現(xiàn).在圖4(a)中可以看出,SCALE算法相對于SCALE-Ser算法有顯著的效率提升.但只降低到了原時間規(guī)模的40%左右，并沒有在最大進程數(shù)為10的情況下將效率提升到預(yù)期的10倍.這是因為并行化方法只對SCALE算法的學(xué)生相似網(wǎng)絡(luò)構(gòu)建和隨機游走部分進行了并行化,并沒有對網(wǎng)絡(luò)嵌入和Top-k搜索步驟采取并行測量,因此并行化并不能完全達到預(yù)期的效果.

同時我們可以發(fā)現(xiàn),隨著數(shù)據(jù)集規(guī)模的增大,SCALE算法的耗時呈非線性關(guān)系增大趨勢,這是因為在構(gòu)建學(xué)生相似網(wǎng)絡(luò)部分需要計算任意2個學(xué)生之間的相似度,通過Skip-Gram模型進行向量嵌入時也需要與其他所有學(xué)生作對比,因此當(dāng)數(shù)據(jù)規(guī)模增大時需要進行的計算次數(shù)以平方規(guī)模增長,因此時間的增加呈現(xiàn)非線性趨勢.

圖4(a)中還可以看出,SCALE算法具有較好的拓展性,在學(xué)生規(guī)模達到20 000時仍然可以支持相似學(xué)生的搜索.真實環(huán)境下,在上萬人中搜索相似學(xué)生已經(jīng)可以滿足絕大多數(shù)需求,因此本算法是具有現(xiàn)實意義的.

Fig.4 Scalability test and runtime with respect to parameters

圖4的(b)～(d)分別展示了參數(shù)α,n,d對SCALE算法效率的影響.圖4(b)中可以看出α對于SCALE算法效率的影響不大,只有在α較小時耗時略低,這是因為在α很接近1時,構(gòu)建學(xué)生相似網(wǎng)絡(luò)過程中只有很少的學(xué)生之間有邊連接,因此導(dǎo)致耗時較短.在α增長到1.4后SCALE算法的效率保持穩(wěn)定.參數(shù)n對SCALE算法效率的影響在隨機游走和網(wǎng)絡(luò)嵌入2部分,圖4(c)中可以看出,參數(shù)n以乘方規(guī)模增大時,SCALE算法耗時也呈非線性增長,但是增長速度沒有達到乘方規(guī)模.圖4(d)中展示了SCALE算法隨參數(shù)d的變化,整體上呈現(xiàn)非線性增長的趨勢,但是在d由16增長至32時,耗時反而下降了,這可能是因為在d=16時,Skip-Gram無法快速收斂,因而導(dǎo)致效率降低.

5 結(jié) 論

搜索相似生活習(xí)慣的學(xué)生在教育數(shù)據(jù)挖掘領(lǐng)域是一個值得被關(guān)注的問題,但目前已有的研究存在著語義缺失或不適用于校園場景數(shù)據(jù)等問題,因此本文提出SCALE算法用于搜索校園場景下生活習(xí)慣相似的學(xué)生,在保留學(xué)生間相似語義的情況下設(shè)計帶約束的元路徑相似度計算方法解決校園場景數(shù)據(jù)中存在的密集性高的問題,最終得到所有學(xué)生的低維向量表示,從而搜索Top-k的相似生活習(xí)慣學(xué)生.同時,我們將SCALE算法的各部分解耦,通過并行化的方法提升效率.最后,我們在校園環(huán)境采集到的真實數(shù)據(jù)集中驗證了SCALE算法的有效性和執(zhí)行效率.

因為SCALE算法的設(shè)計是模塊化、易拓展的,因此下一步可以考慮將更多的數(shù)據(jù)源納入SCALE,同時可以嘗試在網(wǎng)絡(luò)嵌入部分使用更為前沿的方法以提升模型的效果.在目前SCALE的算法流程中,并未考慮噪聲對搜索結(jié)果的影響,如何在搜索過程中降低噪聲的影響從而獲得更準(zhǔn)確的結(jié)果是未來需要進一步研究的工作.