基于動態(tài)演化聚類算法的E-Learning培訓(xùn)搜索研究

殷文輝

（內(nèi)蒙古機電職業(yè)技術(shù)學(xué)院 內(nèi)蒙古 呼和浩特010070）

基于動態(tài)演化聚類算法的E-Learning培訓(xùn)搜索研究

殷文輝

（內(nèi)蒙古機電職業(yè)技術(shù)學(xué)院 內(nèi)蒙古 呼和浩特010070）

隨著信息化社會的高速發(fā)展，網(wǎng)絡(luò)學(xué)習(xí)（E-Learning）培訓(xùn)越來越的應(yīng)用到人才培訓(xùn)的各個領(lǐng)域，能否準確地利用用戶搜索數(shù)據(jù)的效果關(guān)系到長期人才戰(zhàn)略的發(fā)展。本研究簡要分析了E-Learning培訓(xùn)搜索數(shù)據(jù)結(jié)構(gòu)，利用重疊搜索模塊度函數(shù)和指標作為目標函數(shù)，以演化聚類算法和搜索數(shù)據(jù)的編碼解碼為基礎(chǔ)，構(gòu)建了針對E-Learning培訓(xùn)動態(tài)網(wǎng)絡(luò)重疊用戶的動態(tài)演化聚類算法。最后實驗表明提出的動態(tài)演化聚類算法能有效的解決用戶實時搜索數(shù)據(jù)問題。

演化聚類算法；動態(tài)分析；E-Learning培訓(xùn)；實時搜索

網(wǎng)絡(luò)學(xué)習(xí)（E-Learning）培訓(xùn)通過應(yīng)用信息科技和互聯(lián)網(wǎng)技術(shù)進行內(nèi)容傳播和快速學(xué)習(xí)，而搜索引擎被廣泛應(yīng)用于有線網(wǎng)絡(luò)、移動通信網(wǎng)絡(luò)以及無線傳感器中[1]。然而，當前相關(guān)技術(shù)的發(fā)展并沒有將E-Learning培訓(xùn)技術(shù)的潛力充分挖掘[2]。其中，一個重要的問題就是現(xiàn)有物聯(lián)網(wǎng)大多是封閉的、不開放的私有網(wǎng)絡(luò)。

搜索的數(shù)據(jù)是非常有意義的，它可以為很多其他智能應(yīng)用提供數(shù)據(jù)支撐，但是這些數(shù)據(jù)資源是不開放的，進而無法被外界訪問，造成數(shù)據(jù)資源的浪費[3]。為了實現(xiàn)E-Learning培訓(xùn)搜索的潛在價值，即將這些傳感數(shù)據(jù)開放共享[4]。該方向立志于打破傳統(tǒng)搜索數(shù)據(jù)的封閉性，讓搜索數(shù)據(jù)接入互聯(lián)網(wǎng)，并將這些數(shù)據(jù)以一種易理解的、程序可讀的統(tǒng)一格式呈現(xiàn)在上，使之可以被自由地訪問和多方面的利用。

文中首先對E-Learning培訓(xùn)搜索的數(shù)據(jù)描述問題進行概述，隨后從搜索數(shù)據(jù)的特征構(gòu)建動態(tài)E-Learning培訓(xùn)搜索模型數(shù)學(xué)，選擇重疊搜索模塊度函數(shù)和指標作為目標函數(shù)，針對動態(tài)網(wǎng)絡(luò)重疊用戶實時搜索數(shù)據(jù)問題，通過編碼、解碼建立動態(tài)演化聚類算法對重疊用戶搜索進行有效挖掘。

1　E-Learning培訓(xùn)搜索的數(shù)據(jù)描述研究

從搜索的靜態(tài)屬性描述完備性、web描述語言的支持度（使用web語言描述資源描述模型）和動態(tài)特征的描述能力對已有的資源描述模型及其實現(xiàn)進行綜述，對其在E-Learning培訓(xùn)搜索中針對實體進行資源描述的適用能力進行探討。

E-Learning培訓(xùn)主要由以下幾個功能實體組成[5]：1）資源信息數(shù)據(jù)采集；2）動態(tài)特征預(yù)測；3）實體資源描述；4）實體資源信息實時索引；5）實體資源信息實時呈現(xiàn)。

圖1　E-Learning培訓(xùn)搜索結(jié)構(gòu)

如圖1所示，實體資源信息實時采集方式主要包括相關(guān)web頁面的周期性爬取以及E-Learning培訓(xùn)數(shù)據(jù)通過事件觸發(fā)或周期模式進行主動上報和被動獲取。E-Learning培訓(xùn)數(shù)據(jù)特征預(yù)測模型以E-Learning實體采集的數(shù)據(jù)作為輸入，并根據(jù)E-Learning培訓(xùn)的類型及特點進行未來一定時間段內(nèi)的數(shù)據(jù)預(yù)測。E-Learning培訓(xùn)特征預(yù)測模型旨在根據(jù)ELearning及其數(shù)據(jù)的特點對傳感器的動態(tài)特征進行預(yù)測。培訓(xùn)的數(shù)據(jù)會在時間、空間維度上呈現(xiàn)動態(tài)特性。此外，ELearning培訓(xùn)的工作狀態(tài)也會呈現(xiàn)動態(tài)的特性[6]。例如，預(yù)測數(shù)據(jù)、基本信息及用戶自定義信息將上報至搜索平臺中的實體資源描述庫處理后進行存儲。E-Learning培訓(xùn)數(shù)據(jù)資源描述庫對傳感器資源描述模型進行存儲，數(shù)據(jù)資源描述模型旨在針對E-Learning資源實體及其數(shù)據(jù)的靜態(tài)特征 （如類型、內(nèi)置標識、所屬單位等）、動態(tài)特征（如當前數(shù)值、傳感器當前工作狀態(tài)等）進行有效的描述。根據(jù)E-Learning資源描述信息所屬的預(yù)測模型的信息周期時長對E-Learning資源描述庫的信息索引進行實時更新。根據(jù)搜索資源描述庫的信息，建立表示層的搜索web呈現(xiàn)頁面，用于呈現(xiàn)頁面信息和其他相關(guān)機構(gòu)收集的信息。

動態(tài)E-Learning培訓(xùn)搜索模型數(shù)學(xué)描述：動態(tài)網(wǎng)絡(luò)G被定義成一個網(wǎng)絡(luò)序列Gt（Vt，Et），也就是Gt=（G1，G2，…，GT），Vt是一個集合，表示時間t為時網(wǎng)路的節(jié)點集合，每一個vt∈Vt表示一個節(jié)點，每一條邊eij∈Et表示節(jié)點vi和vj存在聯(lián)系。我們用Gt表示網(wǎng)絡(luò)Nt在時刻t的網(wǎng)絡(luò)快照。讓CR={CR1，CR2，…，CRT}表示動態(tài)網(wǎng)絡(luò)N在個時間序列上的用戶劃分，CRt={，，…，}表示網(wǎng)絡(luò)Nt在時刻t的用戶結(jié)構(gòu)劃分，其中表示網(wǎng)絡(luò)在時刻t的第i個用戶，當兩個用戶有公共節(jié)點時，即∩≠?，表示這兩個用戶間構(gòu)成了重疊用戶結(jié)構(gòu)。

2　動態(tài)演化聚類算法

2.1演化聚類

演化聚類通過處理時間序列上的不斷改變的數(shù)據(jù)，產(chǎn)生一系列的類簇[7]。這個過程主要是通過同時優(yōu)化兩個互補的代價函數(shù)實現(xiàn)的，一個被定義為聚類代價函數(shù)（Snapshot Cost），它主要反映的是當前時刻的聚類質(zhì)量[8]，另一個被定義為時空代價函數(shù)（Temporal Cost），它主要反映的是當前時刻的聚類結(jié)果與上一時刻聚類結(jié)果的相似度[9]，通過一個權(quán)值參數(shù)，將兩部分結(jié)合起來，可以得到總的代價函數(shù)。

其中α是一個權(quán)重參數(shù)，它決定著兩個子代價占總代價的比重。當α=l時，得到的是一個不具有平滑性的用戶結(jié)構(gòu)，也就是動態(tài)網(wǎng)絡(luò)中相鄰兩時刻的用戶結(jié)構(gòu)差別較大；而當α=0時，說明t時刻得到的用戶結(jié)構(gòu)與t-l時刻的用戶結(jié)構(gòu)一樣[10]。因此，通過調(diào)節(jié)權(quán)重參數(shù)α，就可以得到不同側(cè)重的用戶結(jié)構(gòu)。

2.2目標函數(shù)選擇

選擇重疊搜索模塊度函數(shù)和指標作為目標函數(shù)，其中前者作為聚類代價函數(shù)，后者作為時空代價函數(shù)。利用基于遺傳算法的多目標進化算法，直接對定義的兩個代價函數(shù)動態(tài)分析和演化聚類同時進行優(yōu)化，不再需要設(shè)定α的值。從每個時刻通過找到一個代表該時刻網(wǎng)絡(luò)最優(yōu)劃分的解，以達到對動態(tài)網(wǎng)絡(luò)進行處理的目的[11]。

模塊度是目前最常用的搜索評價指標[12]。其通過比較現(xiàn)有網(wǎng)絡(luò)和基準網(wǎng)絡(luò)在相同用戶劃分下的連接密度差來衡量網(wǎng)絡(luò)用戶劃分的優(yōu)劣，其中基準網(wǎng)絡(luò) 是與原網(wǎng)絡(luò)具有相同度序列的隨機網(wǎng)絡(luò)。在模塊度基礎(chǔ)上，構(gòu)建重疊用戶模塊度函數(shù)QOL。重疊用戶模塊度定義計算公式如下[13]：

式中i和j表示網(wǎng)絡(luò)中的兩個節(jié)點，m表示網(wǎng)絡(luò)中邊的總數(shù)，Oi和Oj表示節(jié)點i和j所屬的用戶的個數(shù)，A表示網(wǎng)絡(luò)的鄰接矩陣，ki和kj表示節(jié)點i和j的度數(shù)，Ck表示網(wǎng)絡(luò)的第k個用戶。

由于E-Learning培訓(xùn)網(wǎng)絡(luò)中的虛擬用戶發(fā)現(xiàn)問題可以被看成數(shù)據(jù)挖掘領(lǐng)域中的聚類問題，數(shù)據(jù)挖掘領(lǐng)域的學(xué)者提出了若干個數(shù)字指標來衡量數(shù)據(jù)聚類的好壞[14-17]。其中最有代表性的Rand index表示在兩個劃分中都屬于同一個用戶的節(jié)點對的數(shù)量與所有可能的節(jié)點對數(shù)量比值[18]。設(shè)有n個節(jié)點，分別用N1，N2，…，Nn來表示，對于n個節(jié)點存在兩種劃分X和Y，則Rand index指標計算公式如下：

2.3動態(tài)演化聚類算法步驟

基于已有的動態(tài)分析算法和演化聚類算法，文中提出了一種動態(tài)演化聚類算法，根據(jù)算法中設(shè)定目標函數(shù)定義結(jié)合基因的編碼和解碼方式，還有群體交叉、變異策略，給出了算法步驟。

輸入：動態(tài)網(wǎng)絡(luò)N={N1，N2，…，NT}，網(wǎng)絡(luò)建模的圖序列G= {G1，G2，…，GT}，時間序列長度T。

Step 1：用基于連接關(guān)系聚類的靜態(tài)網(wǎng)絡(luò)重疊用戶發(fā)現(xiàn)算法GaoCD[4]，對t=l初始時刻的網(wǎng)絡(luò)Nl，即Gl進行劃分，僅使用一個目標函數(shù)進行優(yōu)化，不做平滑處理，得到第一個時刻的用戶結(jié)構(gòu)CRl={，，…，}；

Step 2：隨機初始化網(wǎng)絡(luò)劃分{CR2，CR3，…，CRT}，每個時刻種群大小popolation=100，隨機初始化得到，個體長度length=|eij∈Nt|，得到（T-2）個種群：{P2，P3，…，PT}，Pt={，，…，Ipopotlation}。令 t=2；

Step 3：如果t＞T，輸出動態(tài)網(wǎng)絡(luò)用戶劃分序列CR={CR1，CR2，…，CRT}，算法終止；否則令genneration=0轉(zhuǎn)到Step 4；

Step 4:如果genneration=50，轉(zhuǎn)到Step 5，否則轉(zhuǎn)到Step 8；

Step 5:計算t時刻網(wǎng)絡(luò)種群Pt中個體的兩個目標函數(shù)的適應(yīng)度值，按照個體的兩個適應(yīng)度函數(shù)值并對種群所有個體進行非支配解排序；

Step 6:對種群Pt中個體進行交叉和變異操作，生成一個新的的子代種群，計算種中每個個體的兩個目標函數(shù)的適應(yīng)度值，按照個體的兩個適應(yīng)度函數(shù)值并對種群中所有個體進行非支配解排序；

Step 7:按照一定比例的精英解保留策略，合并種群Pt和，得到更新后的種群Pt，合并后的種群大小仍為popolation=100；

Step 8:對于t時刻得到一個帕累托解集Dt，按照模塊度最大原則，從Dt中選擇一個個體作為最優(yōu)解；

Step 10:令t=t+l，返回Step 3。

輸出：動態(tài)網(wǎng)絡(luò)N，在不同時間序列上的用戶劃分CR= {CR1，CR2，…，CRT}。

3　實驗結(jié)果及分析

3.1實驗環(huán)境及算法參數(shù)設(shè)置

試驗中的動態(tài)演化聚類算法有關(guān)的參數(shù)設(shè)置如下：交叉概率pc=0.8，變異概率pm=0.2，10%的搜索數(shù)據(jù)保留策略，種群大小popolation=100，種群進化代數(shù)genneration=50。算法隨機運行5次。

算法試驗環(huán)境為：CPU Intel（R）Core（TM）2 Duo，主頻2.93 GHz，內(nèi)存2.00 GB，硬盤 300 GB，操作系統(tǒng) Windows 7，算法運行環(huán)境為Matable R2012。

3.2搜索數(shù)據(jù)編碼與解碼

基因編碼方式：給網(wǎng)絡(luò)圖G中的每一條邊編號0，1，2，…，m，每個個體的有m個基因組成，第i個基因的值表示的是編號為i的邊的一條鄰接邊的編號，為了保證網(wǎng)絡(luò)連接的有效 性，規(guī)定每條邊的等位基因值只能在與它相鄰接的邊中產(chǎn)生[4]。

圖2　編碼過程

解碼處理方式：根據(jù)個體的基因，相鄰的邊屬于一個用戶，組成這些邊的節(jié)點就屬于一 個用戶劃分，由于多條邊可以有共同的節(jié)點，所以包含同一個節(jié)點的邊可能被劃分在不同的 用戶，所以一個節(jié)點就可以同時屬于多個用戶。解碼后節(jié)點1屬于兩個用戶，形成一個重疊用戶結(jié)構(gòu)。

交叉操作：隨機選擇兩個個體如圖 3所示，根據(jù)隨機生成多個交換基因位，交換兩個個體相同基因位的值。交叉操作后的個體如圖4所示。

圖3　父代個體

圖4　交叉?zhèn)€體

圖5　變異個體

變異操作：隨機選擇一些個體，隨機生成多個突變基因位，給這個突變基因位重新隨機分配一個鄰接邊的編號值。變異操作后的個體如圖5所示。

3.3實驗結(jié)果及分析

序列圖的生成算法已經(jīng)在XDRE工具系統(tǒng)中實現(xiàn)，采用了E-Learning培訓(xùn)搜索仿真系統(tǒng)，對序列圖逆向生成的動態(tài)演化算法和非動態(tài)演化算法進行了對比測試。E-Learning培訓(xùn)搜索仿真系統(tǒng)的動態(tài)信息文件具有層次較深的特點。實驗結(jié)果如表1所示。

表1　運用XDRE工具系統(tǒng)進行的對比測試

表1主要反映兩種算法針對不同大小、不同層次深度的動態(tài)信息文件，逆向生成序列圖所產(chǎn)生的效率差別。通過表1可以看出，逆向生成序列圖的時間主要取決于實際畫出的消息交互個數(shù)，而兩種算法所產(chǎn)生的時間差別則主要來源于動態(tài)信息文件的深度。分析實驗結(jié)果可以發(fā)現(xiàn)，動態(tài)搜索信息文件越大，樹狀結(jié)構(gòu)層次越深，非動態(tài)演化算法的優(yōu)勢越明顯。

如表2所示，動態(tài)演化算法在VAST數(shù)據(jù)集上運行的實驗結(jié)果，表中是VAST數(shù)據(jù)集構(gòu)造的動態(tài)網(wǎng)絡(luò)在10個時間段上的網(wǎng)絡(luò)重疊搜索結(jié)構(gòu)的模塊度值。模塊度值取值范圍為：[0，1]，模塊度值越大，表示用戶結(jié)構(gòu)劃分的越準確。從表3中可以看出，動態(tài)演化聚類算法可以有效的求解動態(tài)網(wǎng)路重疊用戶發(fā)現(xiàn)問題，得到的網(wǎng)絡(luò)用戶劃分準確度較好。

動態(tài)聚類算法分別在VAST數(shù)據(jù)集上十個時刻的網(wǎng)絡(luò)快照上獨立做重疊用戶搜索發(fā)現(xiàn)，與文中提出的動態(tài)演化聚類算法作對比分析。動態(tài)聚類算法算法是一種經(jīng)典的靜態(tài)網(wǎng)絡(luò)連接關(guān)系邊聚類重疊用戶搜索數(shù)據(jù)發(fā)現(xiàn)算法。從表2中可以看出，除時刻6、7和10外，動態(tài)演化聚類算法的結(jié)果都要優(yōu)于動態(tài)聚類算法，所以總得來說動態(tài)演化聚類算法在數(shù)據(jù)集VAST的重疊用戶劃分準確度上要高于動態(tài)聚類算法。由于動態(tài)演化聚類算法是同時優(yōu)化兩個目標函數(shù)，在優(yōu)化模塊度的同時也考慮了Rand index指標，而動態(tài)聚類算法只考慮模塊度優(yōu)化，所以動態(tài)演化聚類算法的解在Rand index指標要好于動態(tài)聚類算法。此外動態(tài)演化聚類算法是一種多目標算法，每次迭代要計算種群在個體的多個適應(yīng)度值，還要按照個體的適應(yīng)度值進行非支配解排序，所以動態(tài)演化聚類算法時間復(fù)雜度要高于動態(tài)聚類算法。

表2　VAST數(shù)據(jù)集上得到的模塊度

表3　VAST數(shù)據(jù)集上得到的Rand index

4　結(jié)束語

E-Learning培訓(xùn)的特性決定了搜索的需求。搜索數(shù)據(jù)的多樣性、異構(gòu)性和動態(tài)性等特征決定了E-Learning培訓(xùn)用戶搜索中對資源的描述方式與傳統(tǒng)互聯(lián)網(wǎng)搜索相比具有較大的差異性。對于搜索資源描述的研究尚處于剛剛起步的階段，現(xiàn)有的研究并不是以E-Learning培訓(xùn)為目標，僅僅是針對已有的資源描述模型進行探討，并不能直接應(yīng)用于特征明顯的搜索需求。本研究通過對E-Learning培訓(xùn)搜索中的數(shù)據(jù)資源描述進行了概述與建模，分析了搜索數(shù)據(jù)特點及描述目標。選擇重疊搜索模塊度函數(shù)和指標作為目標函數(shù)，利用編碼、解碼建立動態(tài)演化聚類算法對重疊用戶搜索進行有效挖掘。因此，基于搜索算法的E-Learning培訓(xùn)具有廣闊的研究空間和重大的研究意義。

[1]朱必祥.影響E-Learning員工培訓(xùn)開發(fā)因素分析 [J].中國人力資源開發(fā)，2008（10）:66-69.

[2]周劍，胡明欽.企業(yè)E-Learning系統(tǒng)培訓(xùn)績效綜合評估模型的構(gòu)建[J].統(tǒng)計與決策，2011（13）:177-179.

[3]黃加文，黃景碧，聶文芳.人力資源E-Learning:信息時代企業(yè)培訓(xùn)新發(fā)展[J].現(xiàn)代遠程教育研究，2012（4）:79-84.

[4]宋正國，刁秀麗，魯法明.E-Learning研究現(xiàn)狀和趨勢探析[J].計算機時代，2014（12）:1-4.

[5]魏潔怡，黃國青.企業(yè)員工E-Learning接受意向影響因素研究[J].世界科技研究與發(fā)展，2013（3）:33-37.

[6]胡玉琦.數(shù)據(jù)挖掘技術(shù)在企業(yè)職工培訓(xùn)中的應(yīng)用[J].數(shù)字技術(shù)與應(yīng)用，2011（11）:120-121.

[7]侯薇，董紅斌，印桂生.一種基于隸屬度優(yōu)化的演化聚類算法[J].計算機研究與發(fā)展，2013，50（3）:548-558.

[8]周治平，王杰鋒，朱書偉，等.一種改進的自適應(yīng)快速AFDBSCAN聚類算法[J].智能系統(tǒng)學(xué)報，2015（5）:8-15.

[9]胡偉.改進的層次K均值聚類算法[J].計算機工程與應(yīng)用，2013，49（2）:152-154.

[10]楊寧，唐常杰，王悅，等.基于譜聚類的多數(shù)據(jù)流演化事件挖掘[J].軟件學(xué)報，2010，21（10）:2395-2409.

[11]周晨曦，梁循，齊金山.基于約束動態(tài)更新的半監(jiān)督層次聚類算法[J].自動化學(xué)報，2015，41（7）:1253-1263.

[12]張聰，沈惠璋.基于譜方法的復(fù)雜網(wǎng)絡(luò)中社團結(jié)構(gòu)的模塊度[J].系統(tǒng)工程理論與實踐，2013，33（5）:1231-1239.

[13]胡云，王崇駿，吳駿.微博網(wǎng)絡(luò)上的重疊社群發(fā)現(xiàn)與全局表示[J].軟件學(xué)報，2014（12）:2824-2835.

[14]李仕瓊.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則挖掘算法的分析研[J].電子技術(shù)與軟件工程，2015（4）:200-200.

[15]劉大有，陳慧靈，齊紅，等.時空數(shù)據(jù)挖掘研究進展[J].計算機研究與發(fā)展，2013，50（2）:225-239.

[16]蔡敏，沈培鋒，朱紅，等.基于模糊聚類的配電網(wǎng)負荷特性分析[J].陜西電力,2015(4):24-27，39.

[17]高勇，吳江.基于三比值法與模糊聚類的變壓器故障診斷[J].陜西電力,2012(7):80-82.

[18]謝娟英，魯肖肖，屈亞楠，等.粒計算優(yōu)化初始聚類中心的K-medoids聚類算法[J].計算機科學(xué)與探索，2015（5）: 611-620.

E-Learning train search based on dynamic evolutionary clustering algorithm

YIN Wen-hui
（Inner Mongolia Technical College of Mechanics and Electrics，Hohhot 010070，China）

With the development of information society to tell，E-Learning training is more and more applied to various fields of talent training，it can the effect of the users to search the data is related to the long-term development of talents strategy.In this study the brief analysis of the E-Learning training search data structure，using overlapping search module function and index as the objective function with evolutionary clustering algorithm and search data encoding decoding as the foundation，and we build a dynamic network of overlapping for E-Learning training users the dynamic evolution of the clustering algorithm. Finally，experiments show that the proposed dynamic evolutionary clustering algorithm can effectively solve the problem of real-time search user data.

evolutionary clustering；dynamic analysis；E-Learning train；live search

TN919.8

A

1674－6236（2016）22-0090-04

2016-01-11稿件編號：201601064

殷文輝（1981—），女，滿族，內(nèi)蒙古通遼人，碩士，講師。研究方向:計算機遠程教育。