基于動態演化聚類算法的E-Learning培訓搜索研究

殷文輝

（內蒙古機電職業技術學院 內蒙古 呼和浩特010070）

基于動態演化聚類算法的E-Learning培訓搜索研究

殷文輝

（內蒙古機電職業技術學院 內蒙古 呼和浩特010070）

隨著信息化社會的高速發展，網絡學習（E-Learning）培訓越來越的應用到人才培訓的各個領域，能否準確地利用用戶搜索數據的效果關系到長期人才戰略的發展。本研究簡要分析了E-Learning培訓搜索數據結構，利用重疊搜索模塊度函數和指標作為目標函數，以演化聚類算法和搜索數據的編碼解碼為基礎，構建了針對E-Learning培訓動態網絡重疊用戶的動態演化聚類算法。最后實驗表明提出的動態演化聚類算法能有效的解決用戶實時搜索數據問題。

演化聚類算法；動態分析；E-Learning培訓；實時搜索

網絡學習（E-Learning）培訓通過應用信息科技和互聯網技術進行內容傳播和快速學習，而搜索引擎被廣泛應用于有線網絡、移動通信網絡以及無線傳感器中[1]。然而，當前相關技術的發展并沒有將E-Learning培訓技術的潛力充分挖掘[2]。其中，一個重要的問題就是現有物聯網大多是封閉的、不開放的私有網絡。

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

文中首先對E-Learning培訓搜索的數據描述問題進行概述，隨后從搜索數據的特征構建動態E-Learning培訓搜索模型數學，選擇重疊搜索模塊度函數和指標作為目標函數，針對動態網絡重疊用戶實時搜索數據問題，通過編碼、解碼建立動態演化聚類算法對重疊用戶搜索進行有效挖掘。

1　E-Learning培訓搜索的數據描述研究

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

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

圖1　E-Learning培訓搜索結構

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

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

2　動態演化聚類算法

2.1演化聚類

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

其中α是一個權重參數，它決定著兩個子代價占總代價的比重。當α=l時，得到的是一個不具有平滑性的用戶結構，也就是動態網絡中相鄰兩時刻的用戶結構差別較大；而當α=0時，說明t時刻得到的用戶結構與t-l時刻的用戶結構一樣[10]。因此，通過調節權重參數α，就可以得到不同側重的用戶結構。

2.2目標函數選擇

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

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

式中i和j表示網絡中的兩個節點，m表示網絡中邊的總數，Oi和Oj表示節點i和j所屬的用戶的個數，A表示網絡的鄰接矩陣，ki和kj表示節點i和j的度數，Ck表示網絡的第k個用戶。

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

2.3動態演化聚類算法步驟

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

輸入：動態網絡N={N1，N2，…，NT}，網絡建模的圖序列G= {G1，G2，…，GT}，時間序列長度T。

Step 1：用基于連接關系聚類的靜態網絡重疊用戶發現算法GaoCD[4]，對t=l初始時刻的網絡Nl，即Gl進行劃分，僅使用一個目標函數進行優化，不做平滑處理，得到第一個時刻的用戶結構CRl={，，…，}；

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

Step 3：如果t＞T，輸出動態網絡用戶劃分序列CR={CR1，CR2，…，CRT}，算法終止；否則令genneration=0轉到Step 4；

Step 4:如果genneration=50，轉到Step 5，否則轉到Step 8；

Step 5:計算t時刻網絡種群Pt中個體的兩個目標函數的適應度值，按照個體的兩個適應度函數值并對種群所有個體進行非支配解排序；

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

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

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

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

輸出：動態網絡N，在不同時間序列上的用戶劃分CR= {CR1，CR2，…，CRT}。

3　實驗結果及分析

3.1實驗環境及算法參數設置

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

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

3.2搜索數據編碼與解碼

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

圖2　編碼過程

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

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

圖3　父代個體

圖4　交叉個體

圖5　變異個體

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

3.3實驗結果及分析

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

表1　運用XDRE工具系統進行的對比測試

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

如表2所示，動態演化算法在VAST數據集上運行的實驗結果，表中是VAST數據集構造的動態網絡在10個時間段上的網絡重疊搜索結構的模塊度值。模塊度值取值范圍為：[0，1]，模塊度值越大，表示用戶結構劃分的越準確。從表3中可以看出，動態演化聚類算法可以有效的求解動態網路重疊用戶發現問題，得到的網絡用戶劃分準確度較好。

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

表2　VAST數據集上得到的模塊度

表3　VAST數據集上得到的Rand index

4　結束語

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

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

[2]周劍，胡明欽.企業E-Learning系統培訓績效綜合評估模型的構建[J].統計與決策，2011（13）:177-179.

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

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

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

[6]胡玉琦.數據挖掘技術在企業職工培訓中的應用[J].數字技術與應用，2011（11）:120-121.

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

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

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

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

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

[12]張聰，沈惠璋.基于譜方法的復雜網絡中社團結構的模塊度[J].系統工程理論與實踐，2013，33（5）:1231-1239.

[13]胡云，王崇駿，吳駿.微博網絡上的重疊社群發現與全局表示[J].軟件學報，2014（12）:2824-2835.

[14]李仕瓊.數據挖掘中關聯規則挖掘算法的分析研[J].電子技術與軟件工程，2015（4）:200-200.

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

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

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

[18]謝娟英，魯肖肖，屈亞楠，等.粒計算優化初始聚類中心的K-medoids聚類算法[J].計算機科學與探索，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—），女，滿族，內蒙古通遼人，碩士，講師。研究方向:計算機遠程教育。