褚衍杰,徐正國
(盲信號處理重點實驗室,成都610041)
在第二次世界大戰(zhàn)期間,由于戰(zhàn)爭中快速搜索對方運動目標的需要,George Kimball、Bernard Koopman等人創(chuàng)立了最優(yōu)搜索理論,并逐漸在犯罪學、礦藏勘探、市場調(diào)查、網(wǎng)絡信息處理等領域得到了深入研究[1]。
最優(yōu)搜索理論是關于如何以一種“最佳”的方式尋找某個事先已確定的對象(搜索目標)的理論。最優(yōu)搜索問題的3個基本要素即目標位置概率分布函數(shù)、探測函數(shù)、代價函數(shù)從模型的角度來講分別對應了目標初始概率密度、目標探測模型以及搜索資源模型。利用這些模型可以針對靜止或運動目標的搜索問題展開研究,例如文獻[2]研究了一維隨機恒速運動目標的搜索問題,文獻[3-4]將靜止目標的搜索方法應用到網(wǎng)絡信息處理領域,分別研究特定信息搜索和入侵檢測問題。
網(wǎng)絡用戶的瀏覽行為、通信行為、入侵行為等都受到作息時間、個人行為習慣、入侵方法等的限制,從而在網(wǎng)絡數(shù)據(jù)上反應出一定的規(guī)律,例如文獻[5]對用戶信息查找行為的規(guī)律進行了分析,文獻[6-7]將行為規(guī)律應用到異常檢測和入侵檢測領域,而以最優(yōu)搜索為代表的眾多優(yōu)化搜索策略的方法,利用了目標的概率分布,但未對目標的行為規(guī)律進行進一步的探討。
本文從網(wǎng)絡數(shù)據(jù)中分析目標出現(xiàn)的規(guī)律,建立其行為規(guī)律模型,結合最優(yōu)搜索理論提出基于行為規(guī)律的搜索資源分配算法,解決搜索多長時間和從何時開始搜索的問題,并通過網(wǎng)站關鍵詞的實驗證明了算法能夠有效提高目標搜索的效率。
搜索資源主要是指搜索的時間資源,搜索資源分配策略是指根據(jù)目標在各搜索區(qū)域出現(xiàn)的經(jīng)驗記錄,制定出時間資源分配策略,具體包括在各搜索區(qū)域的搜索時長和開始搜索的時刻。
新算法的創(chuàng)新在于建立目標行為規(guī)律描述模型,并將其引入搜索資源分配策略中,其中目標行為規(guī)律是指目標在同一個區(qū)域不同時間出現(xiàn)規(guī)律的統(tǒng)計。算法結構如圖1所示,首先統(tǒng)計目標概率分布,結合最優(yōu)搜索理論制定各區(qū)域搜索時長的分配策略,其中目標概率分布是指目標在各搜索區(qū)域出現(xiàn)次數(shù)的概率統(tǒng)計;同時統(tǒng)計各區(qū)域內(nèi)目標的行為規(guī)律,以獲取更多信息為目標檢測區(qū)域的最佳搜索時刻;最后結合區(qū)域搜索時長和最佳搜索時刻,制定目標搜索的時間資源分配策略。
圖1 資源分配算法結構Fig.1 Structure of the algorithm
算法用到的符號如下:待搜索區(qū)域為 S={S1,S2,…,SN};目標在各區(qū)域的出現(xiàn)記錄為G={g1,g2,…,gM},其中 gi= {Si,Ti},1≤i≤M,Si∈S為第i條記錄的出現(xiàn)區(qū)域,Ti為第i條記錄的出現(xiàn)時刻;算法的結果為 R= {r1,r2,…,rN},其中 ri={ Si,TLi,TSi},1≤i≤N,表示了從時間 TSi開始搜索區(qū)域Si,共搜索TLi長的時間。
按照經(jīng)典的最優(yōu)搜索理論,區(qū)域搜索時長分配主要包含以下幾個步驟。
(1)目標位置概率分布估計
由于目標的行為規(guī)律一般以天為單位,因此如果目標出現(xiàn)記錄中包含多天的結果,可以進行加權融合。利用 G=g1,g2,…gM}可以統(tǒng)計第i個區(qū)域第j天目標出現(xiàn)的總次數(shù)Cij,定義規(guī)律有效性衰減因子 β=[β1,β2,…,βD],其中 βk(1≤k≤D)表示第 k天的規(guī)律的加權系數(shù),D為規(guī)律統(tǒng)計的總天數(shù),則第i個區(qū)域的加權次數(shù)為C'i=∑Dj=1Cijβj,1≤i≤N,于是可以得到目標在各區(qū)域的概率分布估計P=p1,p2,…,pN{},其中目標在第i個區(qū)域的概率為
(2)目標探測函數(shù)
用探測函數(shù)b(i,t)表示在區(qū)域Si上,花費時間t能成功搜索到目標的概率。根據(jù)一般經(jīng)驗,若不考慮目標的概率分布,投入到區(qū)域Si上的時間t越長,最后能成功找到目標的概率越大,因此可以將探測函數(shù)設為如下形式:
其中,1≤i≤N,t>0,τ 為經(jīng)驗常數(shù)。
(3)時長分配策略
設總的時間資源為T,根據(jù)目標的概率分布及探測函數(shù),可以得到時間T內(nèi)發(fā)現(xiàn)目標的概率為
其中,f(i)為分配給區(qū)域 Si的搜索時長,且
代價函數(shù)c(i,t)表示把時間t分配給區(qū)域Si的代價,可以簡單地令c(i,t)=t,則策略f的總代價為
于是問題轉化為有約束的最優(yōu)化問題:
max P[f]
求解該問題有兩個方法:第一種方法是首先忽略約束條件f(i)≥0,1≤i≤N,利用拉格朗日乘數(shù)法求得解析解:
然后在解析解的基礎上進行結果調(diào)整,使得f(i)≥0,1≤i≤N;第二種方法是將該問題轉化為有約束最小化問題:
則可以直接利用Matlab的fmincon函數(shù)求取數(shù)值解。
目標的活動一般具有規(guī)律性,例如以網(wǎng)絡活動為例,朝九晚五的上班族一般在上午10點前后會集中處理郵件等日常工作,利用此類規(guī)律決定目標搜索的最佳時刻,可以提高搜索到目標的概率。
為了檢測最佳搜索時刻,首先建立對目標行為規(guī)律的描述:對于區(qū)域 Si,以時間分布向量[n't1,n't2,…,n'tH]表示目標的行為規(guī)律,其中 n'ti=是多天統(tǒng)計結果按衰減系數(shù)的加權,表示第 j天目標在(ti-1,ti]時間段內(nèi)在該區(qū)域出現(xiàn)的次數(shù)。
按照上述方法建立每個區(qū)域目標行為的時間分布,該分布可能呈現(xiàn)一定的規(guī)律性,比如多峰,如圖2所示的為雙峰現(xiàn)象。
圖2 雙峰現(xiàn)象及最佳搜索時刻檢測示意圖Fig.2 The sketch map for double-peak and detection of the optimal search moment
本文主要利用時間分布的多峰現(xiàn)象,將每個區(qū)域的搜索時間f(i)分配到各個峰值位置。最佳搜索時刻的最優(yōu)目標是圖2中搜索時間段內(nèi)曲線覆蓋的面積最大,但是通過分析實際數(shù)據(jù)發(fā)現(xiàn),對應每個區(qū)域的行為規(guī)律,圖2中曲線的形狀差異非常大,優(yōu)化復雜,因此選取了一種相對較優(yōu)的簡化方法,便于在實際工程中使用。以雙峰規(guī)律為例說明分配方法如下:
(1)利用包絡檢測的方法,檢測最高峰[t1,n1]和次高峰[t2,n2],其中 t1、t2表示位置,n1、n2表示峰值;
(2)檢測t1兩側值為n2的位置,記錄時間差t;
(3)若 f(i)≤t,則最佳接入位置為 t1,時長為f(i),無次佳搜索時刻;否則最佳搜索時刻為t1,時長為,次佳搜索時刻為t2,時長為。
對于雙峰規(guī)律,得到每個區(qū)域的搜索時長和最佳/次佳搜索時刻后,問題轉化為根據(jù)上述信息在時間軸上完成對搜索時長的分配。本算法采用根據(jù)各區(qū)域目標出現(xiàn)次數(shù)的排序,依次按照最佳/次佳搜索時刻分配區(qū)域搜索時刻,流程如圖3所示。
沙蔥根系發(fā)達,耐干旱,能防風固沙,改良土壤,保持水土。早年間,科爾沁沙地里隨處可見,但是由于長期過度開墾和放牧,近些年,野生沙蔥日漸稀少。
圖3 時間資源分配策略制定流程圖Fig.3 The flow for time distributing strategy
對于流程的具體說明如下:
(1)統(tǒng)計目標的概率分布,并計算各區(qū)域的搜索時長;
(2)對于所有區(qū)域,統(tǒng)計每個區(qū)域D天的時間分布向量,并加權融合,得到每個區(qū)域的時間分布向量;
(3)利用包絡檢測方法檢測時間規(guī)律是否具有雙峰現(xiàn)象;
(4)對于有雙峰現(xiàn)象的區(qū)域,完成兩段搜索時長的分配,并記錄兩個峰值為最佳/次佳搜索時刻;
(5)對于沒有雙峰現(xiàn)象的區(qū)域,檢測單峰位置,記錄為其最佳搜索時刻;
(6)對所有區(qū)域,按照目標出現(xiàn)次數(shù)進行重要性排序;
(7)按照排序結果,對所有區(qū)域,以其最佳/次佳搜索時刻為中心,按照預先分配的時間長度,檢測該時間區(qū)間是否被占用,若未被占用,確認搜索時刻及時長并更新時間占用情況,否則在最佳/次佳搜索時刻一定范圍內(nèi)移動中心,檢測時間是否被占用;若未被占用,確認搜索時刻及時長并更新時間占用情況,否則縮短搜索時長,以最佳/次佳搜索時刻為中心搜索,直至找到合適的搜索時刻;
(8)完成所有區(qū)域的初次分配后,檢測時間占用情況,對于未被占用的時間段,若時長大于一定門限,根據(jù)在步驟7中縮短時長的區(qū)域的最佳搜索時刻,選取距離最近的區(qū)域填補空白,直至無法填補。
為了驗證算法的性能,分兩次采集了254個網(wǎng)站(數(shù)據(jù)集1)以及1 219個網(wǎng)站(數(shù)據(jù)集2)9天的數(shù)據(jù),并按照 gi= Si,Ti{ }(1≤i≤M)的方式記錄關鍵詞的每次出現(xiàn),以此作為試驗驗證的原始數(shù)據(jù)。驗證過程模擬目標搜索過程,即假設目標為關鍵詞,且關鍵詞按照gi= Si,Ti{ }(1≤i≤M)的方式在網(wǎng)站上出現(xiàn),搜索目標時僅能搜索到網(wǎng)站實時出現(xiàn)的關鍵詞,不能搜索到已經(jīng)存在的關鍵詞。驗證方法是利用前5天的數(shù)據(jù)訓練目標的概率分布和行為規(guī)律,然后利用后4天的數(shù)據(jù)分別按照制定的策略進行統(tǒng)計,得到每天可以搜索到的關鍵詞次數(shù),并對比不同算法搜索到關鍵詞數(shù)量的性能;本算法主要分析一天內(nèi)的行為規(guī)律,因此策略中總的搜索時間資源為1天。
圖4分別給出數(shù)據(jù)集1和數(shù)據(jù)集2中行為規(guī)律時間相關性最強的3個網(wǎng)站的相關性變化曲線,其中橫坐標代表間隔時間(天),縱坐標代表相關系數(shù),每個點表示當天數(shù)據(jù)的時間分布向量與第一天數(shù)據(jù)的時間分布向量之間的相關系數(shù)。
圖4 行為規(guī)律相關性變化曲線Fig.4 Relativity of behavior rule
由圖4可以看出,數(shù)據(jù)集1中各網(wǎng)站的相關系數(shù)隨著時間間隔的變大呈現(xiàn)變小的趨勢,而數(shù)據(jù)集2中網(wǎng)站的相關系數(shù)保持穩(wěn)定,沒有明顯的變小趨勢,而且相關性比數(shù)據(jù)集1中更大。這種現(xiàn)象說明,不同的網(wǎng)站上關鍵詞的行為規(guī)律隨著時間延續(xù)在不斷變化,行為規(guī)律有一定的時效性;也說明每個網(wǎng)站上不同日期的行為規(guī)律具有相關性,雖然相關程度不同,但可以利用前期的數(shù)據(jù)預測后期數(shù)據(jù)的行為規(guī)律,證明了本算法在原理上是可行的。
表1給出了利用數(shù)據(jù)集1和數(shù)據(jù)集2進行驗證的結果,其中衰減指數(shù)均選擇指數(shù)衰減。為了體現(xiàn)算法效果,將結果以平均分配方法(各區(qū)域分配相同的時長,順序搜索)為基準進行了歸一化,并給出了本算法以及最優(yōu)搜索方法(只使用最優(yōu)搜索不利用行為規(guī)律)的性能提升對比,性能提升表示相應算法獲取的關鍵詞數(shù)量與平均方法獲取的關鍵詞數(shù)量的比值;圖5給出了不同算法和數(shù)據(jù)集的性能提升對比,其中橫坐標代表不同日期,縱坐標代表性能提升倍數(shù)。
表1 算法性能提升對比表Table1 Comparison of performance advance
圖5 性能提升對比圖Fig.5 Comparison of performance advance
從表1和圖5可以看出,對于數(shù)據(jù)集1,最優(yōu)搜索方法的性能是平均算法的3~5倍,本文算法性能是平均算法的4~6倍,本文算法比最優(yōu)搜索方法性能提升20% ~50%;對于數(shù)據(jù)集2,最優(yōu)搜索方法的性能是平均算法的20~30倍,本文算法性能是平均算法的28~35倍,本文算法比最優(yōu)搜索方法性能提升15%~25%;對照圖4可以看出,由于數(shù)據(jù)集2的行為規(guī)律在時間上的相關性更強,因此相對平均算法的性能提升效果更明顯。
圖6給出了對于數(shù)據(jù)集1和數(shù)據(jù)集2,利用5天的數(shù)據(jù)進行概率分布統(tǒng)計和行為規(guī)律統(tǒng)計,且采用不同的衰減因子β時,算法相對于平均分配算法性能提升倍數(shù)的結果對比,其中橫坐標代表不同日期,縱坐標代表性能提升倍數(shù)。無衰減的衰減因子為β=[1,1,1,1,1],指 數(shù) 衰 減 因 子 為 β =[0.018 2,0.049 8,0.135 3,0.367 9,1],線性衰減因子為 β=[0.2,0.4,0.6,0.8,1],一天的衰減因子為 β=[0,0,0,0,1]。
由圖6可以看出,對于數(shù)據(jù)集1,采用指數(shù)衰減因子時算法性能提升最大,說明了不同日期行為規(guī)律相關性隨時間降低時,應該采取快速衰減的β,保證行為規(guī)律的及時性,而使用1天訓練數(shù)據(jù)的性能提升最差,則是因為由1天數(shù)據(jù)得到的行為規(guī)律具有一定的不穩(wěn)定性;對于數(shù)據(jù)集2,使用1天訓練數(shù)據(jù)時性能提升反而要好些,這是由于數(shù)據(jù)集2的5天訓練數(shù)據(jù)中,行為規(guī)律非常穩(wěn)定,只有第3天的數(shù)據(jù)偏差較大,因此使用5天訓練數(shù)據(jù)相當于引入了一個噪聲,效果反而變差。通過分析可以看出,在算法使用過程中,需要兼顧行為規(guī)律的穩(wěn)定性和及時性,根據(jù)行為規(guī)律相關性的變化規(guī)律采用合理的衰減因子β:時間規(guī)律衰減快則選擇衰減快的β,時間規(guī)律穩(wěn)定則β的選擇對性能影響較小,因此一般情況下,建議選擇衰減較快的指數(shù)衰減因子。
本文通過分析目標的行為規(guī)律,結合最優(yōu)搜索理論,提出了一種基于行為規(guī)律的搜索資源分配算法。利用網(wǎng)站上關鍵詞出現(xiàn)記錄進行的模擬搜索試驗證明了目標行為規(guī)律的存在以及其在穩(wěn)定性、時效性等方面的特點,實驗結果顯示,本文的方法相對于平均分配資源能夠大幅度提高搜索效率,相對于單獨使用最優(yōu)搜索方法,搜索效率也有顯著提高,在對大量信息源進行信息搜索時具有應用價值。另外,在實時處理條件下如何獲取各搜索區(qū)域完整的歷史信息問題未在文中涉及,將是下一步研究的重點。
圖6 采用不同衰減因子β時性能提升對比圖Fig.6 Comparison of performance advance with different β
[1]朱清新.離散和連續(xù)空間的最優(yōu)搜索理論[M].北京:科學出版社,2005.ZHU Qing-xin.The optimal search theory in discrete and continuous space[M].Beijing:Science Press,2005.(in Chinese)
[2]陳建勇,王健.對隨機運動目標的一種最優(yōu)搜索算法[J].海軍航空工程學院學報,2012,27(4):456-458.CHEN Jian-yong,WANG Jian.An optimal search algorithm for randomly moving target[J].Journal of Naval Aeronautical Engineering Institute,2012,27(4):456 -458.(in Chinese)
[3]Chu Yanjie,Wei Qiang.A network specific information search system based on mobile agent[C]//Proceedings of 2012 Third Global Congress on Intelligent Systems.Wuhan:IEEE,2012:302-304.
[4]盛志偉,朱清新.最優(yōu)搜索理論在入侵檢測系統(tǒng)中的應用研究[J].計算機應用與軟件,2008,25(5):248-250.SHENG Zhi-wei,ZHU Qing-xin.On appling optimal search theory in IDS[J].Computer Applications and Software,2008,25(5):248-250.(in Chinese)
[5]何惠芳.網(wǎng)絡環(huán)境下用戶信息查找行為規(guī)律的實證分析[J].情報探索,2008(4):6-8.HE Hui-fang.The analysis of behavior rule of information searching in network[J].Information Research,2008(4):6-8.(in Chinese)
[6]苗強,周興社.基于行為規(guī)律的異常檢測技術研究[J].計算機工程與應用,2010,46(15):211-214.MIAO Qiang,ZHOU Xing-she.Research of outlier detection technique based on behavior rule[J].Computer Engineering and Applications,2010,46(15):211-214.(in Chinese)
[7]Mitchell R,ChenI R.Behavior rule based intrusion detection for supporting secure medical cyber physical systems[C]//Proceedings of 2012 International Conference on Computer Communications and Networks.Munich,Germany:IEEE,2012:1-7.