白曉燕

(榆林學(xué)院, 陜西 榆林 719000)

0 引言

目前，高校圖書(shū)館大部分只有借書(shū)的功能，并沒(méi)有充分地利用圖書(shū)借書(shū)數(shù)據(jù)來(lái)挖掘潛在的信息.高校圖書(shū)館擁有大量的書(shū)籍，基本是按照學(xué)科來(lái)分類，學(xué)生尋找圖書(shū)基本是單一的檢索模式.因此，學(xué)生有時(shí)候很難知道自己需要什么樣的書(shū)籍，這樣一來(lái)，就會(huì)導(dǎo)致只有很少一部分圖書(shū)被借閱，而造成大量圖書(shū)處于空閑狀態(tài).

在大數(shù)據(jù)技術(shù)和數(shù)據(jù)挖掘技術(shù)飛速發(fā)展的今天，已經(jīng)可以挖掘出圖書(shū)與圖書(shū)、圖書(shū)和借閱者之間的關(guān)系，挖掘出學(xué)生的學(xué)習(xí)興趣，挖掘出哪些同學(xué)之間有相同的借閱圖書(shū)內(nèi)容.這樣一來(lái)，圖書(shū)館就不僅是被動(dòng)地讓學(xué)生來(lái)查找書(shū)籍，而是主動(dòng)地給學(xué)生推送一些書(shū)籍；還可以建立基于圖書(shū)借閱信息的學(xué)習(xí)群體，構(gòu)建大學(xué)生學(xué)習(xí)生態(tài)網(wǎng)絡(luò)，學(xué)生可以知道相同學(xué)習(xí)圈里其他同學(xué)在看什么樣的書(shū)籍.這種類型的高校圖書(shū)館，不僅具有提供借閱書(shū)籍的功能，更是可以主動(dòng)地給大學(xué)生推薦其有可能感興趣的書(shū)籍，從而解決了高校圖書(shū)館個(gè)性化推薦水平不高、圖書(shū)利用率不均衡等一系列不利的問(wèn)題.

學(xué)習(xí)群體[1-2]是協(xié)作學(xué)習(xí)的核心組成部分.本文針對(duì)大學(xué)生借閱圖書(shū)事件，構(gòu)建多目標(biāo)優(yōu)化視角下大學(xué)生學(xué)習(xí)群體形成模型；然后，將大學(xué)生圖書(shū)借閱事件問(wèn)題抽象為粒子群多目標(biāo)優(yōu)化問(wèn)題，分析了大學(xué)生借書(shū)事件的關(guān)聯(lián)度與親密度，并采用改進(jìn)的多目標(biāo)離散的粒子群優(yōu)化算法[3-4]，對(duì)大學(xué)生借書(shū)事件網(wǎng)絡(luò)進(jìn)行優(yōu)化，從而得到多目標(biāo)優(yōu)化[5]視角下的大學(xué)生學(xué)習(xí)群體社區(qū)，即可以有效地、有目的地把相關(guān)書(shū)籍推薦給相應(yīng)學(xué)生的社區(qū).

1 粒子群優(yōu)化算法

粒子群優(yōu)化算法[6]是群智能算法的一種，其來(lái)源于對(duì)群居動(dòng)物覓食和躲避捕食者的群體智能行為的人工建模與仿真[7].粒子群優(yōu)化算法具有快速有效性、參數(shù)少、精度高、容易實(shí)現(xiàn)等優(yōu)點(diǎn)，在單任務(wù)領(lǐng)域得到廣泛應(yīng)用.PSO算法[8]作為一種基于群智能體的優(yōu)化算法，個(gè)體之間的協(xié)作[9]能涌現(xiàn)出智能行為.

粒子群算法是微粒群優(yōu)化算法，通過(guò)微粒子在粒子空間中搜索解來(lái)優(yōu)化一個(gè)問(wèn)題，每個(gè)微粒子有兩個(gè)屬性：位置和速度，每個(gè)粒子通過(guò)記得自己最優(yōu)解和知道整個(gè)種群的最優(yōu)解來(lái)調(diào)整自己的速度和位置來(lái)到達(dá)全局最優(yōu).

假設(shè)一個(gè)種群有n個(gè)粒子，粒子的搜索空間的維數(shù)為d，令Vi={vi1,vi2,…,vid}表示第i個(gè)粒子的速度向量，令Xi={xi1,xi2,…,xid}表示第i個(gè)粒子的位置向量，則粒子更新自身狀態(tài)的規(guī)則可以表示為：

(1)

(2)

式(1)中：Pi={pi1,pi2,…,pid}和G={g1,g2,…,gd}，分別表示第i個(gè)粒子在飛行過(guò)程中的歷史最優(yōu)解和整個(gè)種群的最優(yōu)解；c1和c2分別為粒子加速系數(shù)[10]和社會(huì)系數(shù)[11]；r1和r2是0到1之間的隨機(jī)數(shù).

粒子群優(yōu)化算法是一個(gè)不斷重復(fù)的迭代計(jì)算算法，每個(gè)粒子根據(jù)公式(1)和公式(2)來(lái)不斷地調(diào)整本身粒子飛行軌跡，從而得到整個(gè)粒子空間中最優(yōu)的粒子，然后進(jìn)行不斷地逼近.

2 基于粒子群優(yōu)化的借書(shū)網(wǎng)絡(luò)社區(qū)建立

2.1 算法框架

本文提出的離散粒子群優(yōu)化算法[11]通過(guò)重新定義粒子群算法操作算子，計(jì)算能量函數(shù)的最小值等來(lái)更新粒子的位置和速度[12-13].本文所提出算法的工作流程圖如圖1所示.

圖1 本文算法工作流程圖

2.2 粒子適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用來(lái)評(píng)價(jià)粒子的優(yōu)秀程度，對(duì)于社交網(wǎng)絡(luò)的問(wèn)題而言，適應(yīng)度函數(shù)用來(lái)評(píng)價(jià)粒子的收斂程度是否合理，收斂速度怎么樣，文獻(xiàn)[14]提出了一種度量網(wǎng)絡(luò)平衡程度的能量函數(shù)H(s)，其定義如下：

H(s)=∑i,j(1-aijsisj)/2

(3)

式(3)中：aij∈{±1}是網(wǎng)絡(luò)鄰接矩陣的元素，si和sj分別表示節(jié)點(diǎn)i和節(jié)點(diǎn)j的符號(hào).若節(jié)點(diǎn)i和節(jié)點(diǎn)j屬于同一個(gè)社區(qū)，則si·sj=1，若節(jié)點(diǎn)i和節(jié)點(diǎn)j屬于不在同一個(gè)社區(qū)，si·sj=-1.

該適應(yīng)度函數(shù)[15]是根據(jù)網(wǎng)絡(luò)平衡結(jié)果來(lái)衡量其對(duì)應(yīng)的能量函數(shù)，函數(shù)值越小代表網(wǎng)絡(luò)越接近于平衡.本文利用粒子群優(yōu)化算法來(lái)最小化該函數(shù)，從而很快地找到對(duì)應(yīng)的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)，繼而找到對(duì)應(yīng)的圖.

2.3 粒子的表示

本文基于字符串的編碼和解碼[16]對(duì)網(wǎng)絡(luò)進(jìn)行編解碼，編解碼是優(yōu)化問(wèn)題和優(yōu)化算法之間的橋梁.本文采用基于字符串的編碼，這種編碼操作簡(jiǎn)單可靠，對(duì)后期的解碼有利，具體采用的粒子編碼如圖2所示.

圖2 粒子的表示示意圖

由圖2可知，粒子的位置采用整數(shù)序列來(lái)表示，序列中的每個(gè)數(shù)字代表粒子的對(duì)應(yīng)位置，其對(duì)應(yīng)的數(shù)字代表粒子分類的社區(qū)標(biāo)號(hào)，進(jìn)行解碼的時(shí)候，具有相同社區(qū)類標(biāo)號(hào)的整數(shù)節(jié)點(diǎn)會(huì)被劃分到同一個(gè)社區(qū)里面.從而，采用整數(shù)進(jìn)行編碼可以自動(dòng)地預(yù)測(cè)網(wǎng)絡(luò)需要?jiǎng)澐譃閹讉€(gè)社區(qū).

采用整數(shù)編碼的方法，在解碼的時(shí)候，如果節(jié)點(diǎn)i和節(jié)點(diǎn)j在同一個(gè)社區(qū)，則si·sj=1，如果節(jié)點(diǎn)i和節(jié)點(diǎn)j不在同一個(gè)社區(qū)，則si·sj=-1.

2.4 粒子的狀態(tài)更新規(guī)則

本文算法中粒子的位置采用整數(shù)來(lái)進(jìn)行編碼，因此傳統(tǒng)的粒子狀態(tài)更新方程已經(jīng)不再適用本文問(wèn)題的求解.為了更好地得到社區(qū)結(jié)構(gòu)，本文重新定義了粒子的狀態(tài)更新方程：

(4)

(5)

式(4)中：ω是慣性權(quán)值常數(shù)，符號(hào)⊕表示異或操作.

函數(shù)ζ(x)是一個(gè)二維向量函數(shù)，其目的是將變量x變?yōu)殡x散的二進(jìn)制形式，便于其與位置向量進(jìn)行公式(4)的操作.函數(shù)ζ(x)具體定義如下:

(6)

公式(5)中的?操作是粒子狀態(tài)更新的核心操作，該操作設(shè)置的好壞會(huì)直接影響算法挖掘社區(qū)的性能，還會(huì)影響算法的收斂程度.

對(duì)于一個(gè)圖書(shū)網(wǎng)絡(luò)而言，兩個(gè)節(jié)點(diǎn)之間的連接概率采用如下方法，本文定義的?操作如下:

(7)

式(7)中：rand(xit)表示的是從xit對(duì)應(yīng)的節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中隨機(jī)選取一個(gè)節(jié)點(diǎn)的社區(qū)標(biāo)號(hào).

2.5 算法過(guò)程

算法過(guò)程如下所示：

步驟1首先初始化種群W，設(shè)種群W中粒子數(shù)為N；

步驟2計(jì)算粒子I在不同任務(wù)上的適應(yīng)值；

步驟3計(jì)算粒子的i的最優(yōu)因子ti,i屬于W；

步驟4對(duì)當(dāng)前種群W引入擾動(dòng)因子φ,產(chǎn)生新的個(gè)體形成新的種群W1;

步驟5將W1中的新個(gè)體用于求解特定的任務(wù)；

步驟6將原始種群W和新的種群合并形成一個(gè)新的臨時(shí)種群W2W2(W2=W∪W1)

步驟7更新W2中的最優(yōu)因子ti；

步驟8從當(dāng)前臨時(shí)種群W2中挑選出適應(yīng)值最優(yōu)的N個(gè)粒子形成新的種群W3；

步驟9對(duì)每個(gè)任務(wù)的當(dāng)前值解實(shí)行局部搜索，以逼近全局最優(yōu).

步驟10循環(huán)步驟3～步驟9，直到滿足循環(huán)條件；

步驟11輸出所有的任務(wù)的全局最優(yōu)解.

3 實(shí)驗(yàn)測(cè)試與分析

3.1 實(shí)驗(yàn)設(shè)置

為了測(cè)試本算法的性能，將采用真實(shí)的圖書(shū)借閱書(shū)籍進(jìn)行實(shí)驗(yàn)測(cè)試.首先將本文算法命名為PSOSB，本文算法用到的參數(shù)做如下設(shè)置：慣性系數(shù)ω設(shè)置為0.718，本算法的加速系數(shù)c1和c2設(shè)置為1.510，粒子群的種群大小N設(shè)置為200，算法的循環(huán)迭代次數(shù)M設(shè)置為200.本文采用的算法對(duì)比文獻(xiàn)[17]提出算法MemeSB，該算法的交叉概率和變異概率分別設(shè)置為0.8和0.2，其種群規(guī)模N設(shè)為200,算法的迭代次數(shù)設(shè)置為300.

實(shí)驗(yàn)中用到的數(shù)據(jù)為榆林學(xué)院圖書(shū)館四組不同的圖書(shū)借閱事件，該網(wǎng)絡(luò)由不同的節(jié)點(diǎn)組成，分別采用改進(jìn)的粒子群優(yōu)化算法進(jìn)行測(cè)試.高校圖書(shū)館借閱事件分別用(YLTSG1)、(YLTSG2)、(YLTSG3)、(YLTSG4)來(lái)表示.本文通過(guò)四組(YLTSG1)、(YLTSG2)、(YLTSG3)、(YLTSG4)圖書(shū)借閱真實(shí)數(shù)據(jù)進(jìn)行測(cè)試，該四組圖書(shū)借閱事件網(wǎng)絡(luò)的屬性見(jiàn)表1所示.

表1 圖書(shū)借閱事件數(shù)據(jù)統(tǒng)計(jì)表

3.2 模擬數(shù)據(jù)測(cè)試

對(duì)本文算法運(yùn)行30次，實(shí)驗(yàn)中發(fā)現(xiàn)，在對(duì)YLTSG事件1和YLTSG事件2網(wǎng)絡(luò)進(jìn)行測(cè)試時(shí)，可以得到不同的四個(gè)圖書(shū)事件社區(qū).

PSOSB算法和MemeSB算法30次獨(dú)立運(yùn)行得到的能量函數(shù)H(s)的值均為0，說(shuō)明兩種算法均找到了網(wǎng)絡(luò)的平衡結(jié)構(gòu).圖3和圖4分別展示了YLTSG事件1和YLTSG事件2的網(wǎng)絡(luò)結(jié)構(gòu)圖.從圖3和圖4可以看出，YLTSG事件1和YLTSG事件2網(wǎng)絡(luò)都被分成了三個(gè)社區(qū)，且每個(gè)社區(qū)內(nèi)部的節(jié)點(diǎn)都是正邊連接的，社區(qū)之間的節(jié)點(diǎn)均為負(fù)邊連接，可以得到哪些同學(xué)在讀相似的圖書(shū)，得到大學(xué)生學(xué)習(xí)群體社區(qū)[18].

圖3 YLTSG事件1結(jié)構(gòu)圖

圖4 YLTSG事件2結(jié)構(gòu)圖

3.3 模擬數(shù)據(jù)測(cè)試(Real data test)

在對(duì)真實(shí)網(wǎng)絡(luò)YLTSG3，YLTSG4進(jìn)行測(cè)試時(shí)，PSOSB和MemeSB同樣獨(dú)立運(yùn)行30次.表2記錄了實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果.

在網(wǎng)絡(luò)YLTSG事件3和YLTSG事件4上，兩個(gè)算法都得到了相同的結(jié)果，PSOSB和MemeSB均得到了最小的能量函數(shù)值，但PSOSB算法的計(jì)算速度要比MemeSB算法快0.8 s.

圖5和圖6分別展示了圖書(shū)借閱事件的真實(shí)社區(qū)結(jié)構(gòu)圖以及PSOSB算法得到的具有最小能量函數(shù)[19]的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)經(jīng)過(guò)改變非平衡邊得到的網(wǎng)絡(luò)的平衡結(jié)構(gòu)圖.通過(guò)圖5和圖6對(duì)比可以看出，為了實(shí)現(xiàn)網(wǎng)絡(luò)的結(jié)構(gòu)平衡[20]，節(jié)點(diǎn)SNS與DS和ZS-ESS之間的負(fù)邊變成了正邊，從而讓曾經(jīng)讀過(guò)和該書(shū)有相似的借閱事件大學(xué)生加入該社區(qū).

圖5 YLTSG圖書(shū)借閱事件3的真實(shí)社區(qū)結(jié)構(gòu)圖

圖6 YLTSG圖書(shū)借閱事件3的真實(shí)社區(qū)結(jié)構(gòu)變換非平衡邊得到的平衡結(jié)構(gòu)圖

在YLTSG圖書(shū)借閱事件1上，從表2可以看出，PSOSB比MemeSB得到了更小的H(s)的值，且PSOSB算法的計(jì)算速度仍然要比MemeSB算法快.圖7和圖8展示了YLTSG3網(wǎng)絡(luò)的真實(shí)社區(qū)劃分以及網(wǎng)絡(luò)通過(guò)改變非平衡的邊所得到的平衡結(jié)構(gòu).從圖7和圖8的對(duì)比可以看出，YLTSG圖書(shū)借閱事件3的四條正邊被變成了負(fù)邊，可以把不相關(guān)的借閱事件剔除出該社區(qū).

表2 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)30次獨(dú)立測(cè)試結(jié)果統(tǒng)計(jì)表

圖7 事件4網(wǎng)絡(luò)真實(shí)社區(qū)結(jié)構(gòu)

圖8 事件4網(wǎng)絡(luò)變換非平衡邊得到的平衡結(jié)構(gòu)圖

在YLTSG事件3和YLTSG事件4上，本文提出的算法和對(duì)比算法的實(shí)驗(yàn)結(jié)果一樣，這是因?yàn)檫@兩個(gè)網(wǎng)絡(luò)的規(guī)模太小，兩種算法均很容易找到問(wèn)題的最優(yōu)解.雖然在YLTSG事件3和YLTSG事件4上，兩種算法得到了相同的實(shí)驗(yàn)結(jié)果，但是本文算法比對(duì)比算法具有更快的收斂速度，本文算法的運(yùn)行時(shí)間比對(duì)比算法要快兩個(gè)數(shù)量級(jí).從表2所示的統(tǒng)計(jì)結(jié)果來(lái)看，本文提出的PSOSB算法在YLTSG事件3和YLTSG事件4網(wǎng)絡(luò)上的實(shí)驗(yàn)性能要明顯優(yōu)于MemeSB算法，PSOSB不僅能夠得到比MemeSB算法更小的能量函數(shù)值，而且PSOSB算法的運(yùn)行收斂時(shí)間明顯要快于對(duì)比算法MemeSB.

實(shí)驗(yàn)中還發(fā)現(xiàn)，PSOSB算法比MemeSB算法具有更快的收斂速度.圖9和圖10分別展示了在YLTSG事件3網(wǎng)絡(luò)和YLTSG事件4網(wǎng)絡(luò)上兩種算法在迭代100次時(shí)，算法單次運(yùn)行得到的收斂曲線.從收斂實(shí)驗(yàn)的對(duì)比結(jié)果可以看出，PSOSB算法基本上在迭代40次的時(shí)候就已經(jīng)收斂，而MemeSB算法需要迭代大約80次才能達(dá)到收斂.

圖9 算法在YLTSG事件3網(wǎng)絡(luò)上的收斂情況對(duì)比

圖10 算法在YLTSG事件4網(wǎng)絡(luò)上的收斂情況對(duì)比

從圖9和圖10可以看出，本文提出的基于離散的粒子群優(yōu)化算法可以很快地向最優(yōu)方向逼近，另外，本文算法在結(jié)構(gòu)設(shè)計(jì)上充分考慮到圖書(shū)網(wǎng)絡(luò)本身的特點(diǎn)，在經(jīng)典的粒子群算法的基礎(chǔ)上，重新設(shè)計(jì)了粒子的狀態(tài)更新方程，該方程可以增加粒子的全局尋優(yōu)速度.對(duì)比MemeticSB算法，本文算法增加了擾動(dòng)粒子，防止算法進(jìn)入局部最優(yōu)，而MemeticSB算法采用貪婪算法容易使算法陷入局部最優(yōu)，而且貪婪算法的計(jì)算代價(jià)特別高.

由于本文算法和MemeSB算法都是隨機(jī)搜索算法，算法的運(yùn)行受到很多實(shí)際參數(shù)的影響，而且算法在每次運(yùn)行時(shí)結(jié)果都不一樣，因此探討算法的穩(wěn)定性是很有必要的.圖11是PSOSB算法和MemeSB算法在YLTSG事件3網(wǎng)絡(luò)數(shù)據(jù)、YLTSG事件4網(wǎng)絡(luò)數(shù)據(jù)上獨(dú)立運(yùn)行200次得到的統(tǒng)計(jì)結(jié)果的箱圖展示.

圖11 在YLTSG事件3和YLTSG事件4上的算法穩(wěn)定性對(duì)比實(shí)驗(yàn)

箱圖能夠反應(yīng)算法的穩(wěn)定性情況，其長(zhǎng)短反應(yīng)的是算法的穩(wěn)定性.箱圖長(zhǎng)度越長(zhǎng)代表算法不穩(wěn)定，箱圖長(zhǎng)度越短代表算法越穩(wěn)定.從圖11可看出，本文算法經(jīng)過(guò)200次的迭代運(yùn)行，得到的箱圖長(zhǎng)度比MemeSB的要短，同時(shí)說(shuō)明本文算法相對(duì)于MemeSB算法在穩(wěn)定性方面更優(yōu)秀.從箱圖的數(shù)據(jù)分布情況可以看出，在不同大學(xué)生借閱圖書(shū)事件上本文算法優(yōu)化得到的最小的能量函數(shù)的函數(shù)值要比MemeSB算法的更小，從而證明了本文所提算法的有效性.

4 結(jié)論

本文以大學(xué)生圖書(shū)借閱事件為研究對(duì)象，建立了大學(xué)生圖書(shū)借閱事件網(wǎng)絡(luò)結(jié)構(gòu)圖.然后，以圖論知識(shí)為基礎(chǔ)，對(duì)大學(xué)生借閱圖書(shū)事件網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行了深入研究，提出了一種基于粒子群優(yōu)化的求解大學(xué)生學(xué)習(xí)群體問(wèn)題的方法.該方法不僅可以實(shí)現(xiàn)大學(xué)生學(xué)習(xí)群體網(wǎng)絡(luò)結(jié)構(gòu)圖，還可以挖掘網(wǎng)絡(luò)中隱藏的社團(tuán)結(jié)構(gòu).

本文把大學(xué)生借閱事件看做粒子，粒子通過(guò)調(diào)整種群中解的表示方法、位置和速度的更新規(guī)則以及局部搜索策略，設(shè)計(jì)出離散粒子群算法，從而得到具有相同大學(xué)生借書(shū)事件網(wǎng)絡(luò)社區(qū).最后，將本文算法在真實(shí)的大學(xué)生借閱圖書(shū)事件上進(jìn)行測(cè)試，較好地得到了大學(xué)生具有相同借閱事件的網(wǎng)絡(luò)結(jié)構(gòu)圖，從而發(fā)現(xiàn)大學(xué)生學(xué)習(xí)群體，驗(yàn)證了該算法的有效性，并可以有針對(duì)性地把相關(guān)書(shū)籍推薦給大學(xué)生.根據(jù)真實(shí)實(shí)驗(yàn)測(cè)試，本文推薦算法的準(zhǔn)確率提高了11%，覆蓋率提升了13%，這對(duì)高校建立大學(xué)生學(xué)習(xí)社團(tuán)具有很好的指導(dǎo)意義.