褚衍杰，徐正國(guó)

(盲信號(hào)處理重點(diǎn)實(shí)驗(yàn)室，成都610041)

1 引言

在第二次世界大戰(zhàn)期間，由于戰(zhàn)爭(zhēng)中快速搜索對(duì)方運(yùn)動(dòng)目標(biāo)的需要，George Kimball、Bernard Koopman等人創(chuàng)立了最優(yōu)搜索理論，并逐漸在犯罪學(xué)、礦藏勘探、市場(chǎng)調(diào)查、網(wǎng)絡(luò)信息處理等領(lǐng)域得到了深入研究[1]。

最優(yōu)搜索理論是關(guān)于如何以一種“最佳”的方式尋找某個(gè)事先已確定的對(duì)象(搜索目標(biāo))的理論。最優(yōu)搜索問(wèn)題的3個(gè)基本要素即目標(biāo)位置概率分布函數(shù)、探測(cè)函數(shù)、代價(jià)函數(shù)從模型的角度來(lái)講分別對(duì)應(yīng)了目標(biāo)初始概率密度、目標(biāo)探測(cè)模型以及搜索資源模型。利用這些模型可以針對(duì)靜止或運(yùn)動(dòng)目標(biāo)的搜索問(wèn)題展開研究，例如文獻(xiàn)[2]研究了一維隨機(jī)恒速運(yùn)動(dòng)目標(biāo)的搜索問(wèn)題，文獻(xiàn)[3－4]將靜止目標(biāo)的搜索方法應(yīng)用到網(wǎng)絡(luò)信息處理領(lǐng)域，分別研究特定信息搜索和入侵檢測(cè)問(wèn)題。

網(wǎng)絡(luò)用戶的瀏覽行為、通信行為、入侵行為等都受到作息時(shí)間、個(gè)人行為習(xí)慣、入侵方法等的限制，從而在網(wǎng)絡(luò)數(shù)據(jù)上反應(yīng)出一定的規(guī)律，例如文獻(xiàn)[5]對(duì)用戶信息查找行為的規(guī)律進(jìn)行了分析，文獻(xiàn)[6－7]將行為規(guī)律應(yīng)用到異常檢測(cè)和入侵檢測(cè)領(lǐng)域，而以最優(yōu)搜索為代表的眾多優(yōu)化搜索策略的方法，利用了目標(biāo)的概率分布，但未對(duì)目標(biāo)的行為規(guī)律進(jìn)行進(jìn)一步的探討。

本文從網(wǎng)絡(luò)數(shù)據(jù)中分析目標(biāo)出現(xiàn)的規(guī)律，建立其行為規(guī)律模型，結(jié)合最優(yōu)搜索理論提出基于行為規(guī)律的搜索資源分配算法，解決搜索多長(zhǎng)時(shí)間和從何時(shí)開始搜索的問(wèn)題，并通過(guò)網(wǎng)站關(guān)鍵詞的實(shí)驗(yàn)證明了算法能夠有效提高目標(biāo)搜索的效率。

2 算法模型

搜索資源主要是指搜索的時(shí)間資源，搜索資源分配策略是指根據(jù)目標(biāo)在各搜索區(qū)域出現(xiàn)的經(jīng)驗(yàn)記錄，制定出時(shí)間資源分配策略，具體包括在各搜索區(qū)域的搜索時(shí)長(zhǎng)和開始搜索的時(shí)刻。

新算法的創(chuàng)新在于建立目標(biāo)行為規(guī)律描述模型，并將其引入搜索資源分配策略中，其中目標(biāo)行為規(guī)律是指目標(biāo)在同一個(gè)區(qū)域不同時(shí)間出現(xiàn)規(guī)律的統(tǒng)計(jì)。算法結(jié)構(gòu)如圖1所示，首先統(tǒng)計(jì)目標(biāo)概率分布，結(jié)合最優(yōu)搜索理論制定各區(qū)域搜索時(shí)長(zhǎng)的分配策略，其中目標(biāo)概率分布是指目標(biāo)在各搜索區(qū)域出現(xiàn)次數(shù)的概率統(tǒng)計(jì);同時(shí)統(tǒng)計(jì)各區(qū)域內(nèi)目標(biāo)的行為規(guī)律，以獲取更多信息為目標(biāo)檢測(cè)區(qū)域的最佳搜索時(shí)刻;最后結(jié)合區(qū)域搜索時(shí)長(zhǎng)和最佳搜索時(shí)刻，制定目標(biāo)搜索的時(shí)間資源分配策略。

圖1 資源分配算法結(jié)構(gòu)Fig.1 Structure of the algorithm

算法用到的符號(hào)如下:待搜索區(qū)域?yàn)?S={S1，S2，…，SN};目標(biāo)在各區(qū)域的出現(xiàn)記錄為G={g1，g2，…，gM}，其中 gi= {Si，Ti}，1≤i≤M，Si∈S為第i條記錄的出現(xiàn)區(qū)域，Ti為第i條記錄的出現(xiàn)時(shí)刻;算法的結(jié)果為 R= {r1，r2，…，rN}，其中 ri={ Si，TLi，TSi}，1≤i≤N，表示了從時(shí)間 TSi開始搜索區(qū)域Si，共搜索TLi長(zhǎng)的時(shí)間。

2.1 區(qū)域搜索時(shí)長(zhǎng)分配

按照經(jīng)典的最優(yōu)搜索理論，區(qū)域搜索時(shí)長(zhǎng)分配主要包含以下幾個(gè)步驟。

(1)目標(biāo)位置概率分布估計(jì)

由于目標(biāo)的行為規(guī)律一般以天為單位，因此如果目標(biāo)出現(xiàn)記錄中包含多天的結(jié)果，可以進(jìn)行加權(quán)融合。利用 G=g1，g2，…gM}可以統(tǒng)計(jì)第i個(gè)區(qū)域第j天目標(biāo)出現(xiàn)的總次數(shù)Cij，定義規(guī)律有效性衰減因子 β=[β1，β2，…，βD]，其中 βk(1≤k≤D)表示第 k天的規(guī)律的加權(quán)系數(shù)，D為規(guī)律統(tǒng)計(jì)的總天數(shù)，則第i個(gè)區(qū)域的加權(quán)次數(shù)為C'i=∑Dj=1Cijβj，1≤i≤N，于是可以得到目標(biāo)在各區(qū)域的概率分布估計(jì)P=p1，p2，…，pN{}，其中目標(biāo)在第i個(gè)區(qū)域的概率為

(2)目標(biāo)探測(cè)函數(shù)

用探測(cè)函數(shù)b(i，t)表示在區(qū)域Si上，花費(fèi)時(shí)間t能成功搜索到目標(biāo)的概率。根據(jù)一般經(jīng)驗(yàn)，若不考慮目標(biāo)的概率分布，投入到區(qū)域Si上的時(shí)間t越長(zhǎng)，最后能成功找到目標(biāo)的概率越大，因此可以將探測(cè)函數(shù)設(shè)為如下形式:

其中，1≤i≤N，t＞0，τ 為經(jīng)驗(yàn)常數(shù)。

(3)時(shí)長(zhǎng)分配策略

設(shè)總的時(shí)間資源為T，根據(jù)目標(biāo)的概率分布及探測(cè)函數(shù)，可以得到時(shí)間T內(nèi)發(fā)現(xiàn)目標(biāo)的概率為

其中，f(i)為分配給區(qū)域 Si的搜索時(shí)長(zhǎng)，且

代價(jià)函數(shù)c(i，t)表示把時(shí)間t分配給區(qū)域Si的代價(jià)，可以簡(jiǎn)單地令c(i，t)=t，則策略f的總代價(jià)為

于是問(wèn)題轉(zhuǎn)化為有約束的最優(yōu)化問(wèn)題:

max P[f]

求解該問(wèn)題有兩個(gè)方法:第一種方法是首先忽略約束條件f(i)≥0，1≤i≤N，利用拉格朗日乘數(shù)法求得解析解:

然后在解析解的基礎(chǔ)上進(jìn)行結(jié)果調(diào)整，使得f(i)≥0，1≤i≤N;第二種方法是將該問(wèn)題轉(zhuǎn)化為有約束最小化問(wèn)題:

則可以直接利用Matlab的fmincon函數(shù)求取數(shù)值解。

2.2 最佳搜索時(shí)刻檢測(cè)

目標(biāo)的活動(dòng)一般具有規(guī)律性，例如以網(wǎng)絡(luò)活動(dòng)為例，朝九晚五的上班族一般在上午10點(diǎn)前后會(huì)集中處理郵件等日常工作，利用此類規(guī)律決定目標(biāo)搜索的最佳時(shí)刻，可以提高搜索到目標(biāo)的概率。

為了檢測(cè)最佳搜索時(shí)刻，首先建立對(duì)目標(biāo)行為規(guī)律的描述:對(duì)于區(qū)域 Si，以時(shí)間分布向量[n't1，n't2，…，n'tH]表示目標(biāo)的行為規(guī)律，其中 n'ti=是多天統(tǒng)計(jì)結(jié)果按衰減系數(shù)的加權(quán)，表示第 j天目標(biāo)在(ti－1，ti]時(shí)間段內(nèi)在該區(qū)域出現(xiàn)的次數(shù)。

按照上述方法建立每個(gè)區(qū)域目標(biāo)行為的時(shí)間分布，該分布可能呈現(xiàn)一定的規(guī)律性，比如多峰，如圖2所示的為雙峰現(xiàn)象。

圖2 雙峰現(xiàn)象及最佳搜索時(shí)刻檢測(cè)示意圖Fig.2 The sketch map for double－peak and detection of the optimal search moment

本文主要利用時(shí)間分布的多峰現(xiàn)象，將每個(gè)區(qū)域的搜索時(shí)間f(i)分配到各個(gè)峰值位置。最佳搜索時(shí)刻的最優(yōu)目標(biāo)是圖2中搜索時(shí)間段內(nèi)曲線覆蓋的面積最大，但是通過(guò)分析實(shí)際數(shù)據(jù)發(fā)現(xiàn)，對(duì)應(yīng)每個(gè)區(qū)域的行為規(guī)律，圖2中曲線的形狀差異非常大，優(yōu)化復(fù)雜，因此選取了一種相對(duì)較優(yōu)的簡(jiǎn)化方法，便于在實(shí)際工程中使用。以雙峰規(guī)律為例說(shuō)明分配方法如下:

(1)利用包絡(luò)檢測(cè)的方法，檢測(cè)最高峰[t1，n1]和次高峰[t2，n2]，其中 t1、t2表示位置，n1、n2表示峰值;

(2)檢測(cè)t1兩側(cè)值為n2的位置，記錄時(shí)間差t;

(3)若 f(i)≤t，則最佳接入位置為 t1，時(shí)長(zhǎng)為f(i)，無(wú)次佳搜索時(shí)刻;否則最佳搜索時(shí)刻為t1，時(shí)長(zhǎng)為，次佳搜索時(shí)刻為t2，時(shí)長(zhǎng)為。

2.3 時(shí)間資源分配策略制定

對(duì)于雙峰規(guī)律，得到每個(gè)區(qū)域的搜索時(shí)長(zhǎng)和最佳/次佳搜索時(shí)刻后，問(wèn)題轉(zhuǎn)化為根據(jù)上述信息在時(shí)間軸上完成對(duì)搜索時(shí)長(zhǎng)的分配。本算法采用根據(jù)各區(qū)域目標(biāo)出現(xiàn)次數(shù)的排序，依次按照最佳/次佳搜索時(shí)刻分配區(qū)域搜索時(shí)刻，流程如圖3所示。

沙蔥根系發(fā)達(dá)，耐干旱，能防風(fēng)固沙，改良土壤，保持水土。早年間，科爾沁沙地里隨處可見，但是由于長(zhǎng)期過(guò)度開墾和放牧，近些年，野生沙蔥日漸稀少。

圖3 時(shí)間資源分配策略制定流程圖Fig.3 The flow for time distributing strategy

對(duì)于流程的具體說(shuō)明如下:

(1)統(tǒng)計(jì)目標(biāo)的概率分布，并計(jì)算各區(qū)域的搜索時(shí)長(zhǎng);

(2)對(duì)于所有區(qū)域，統(tǒng)計(jì)每個(gè)區(qū)域D天的時(shí)間分布向量，并加權(quán)融合，得到每個(gè)區(qū)域的時(shí)間分布向量;

(3)利用包絡(luò)檢測(cè)方法檢測(cè)時(shí)間規(guī)律是否具有雙峰現(xiàn)象;

(4)對(duì)于有雙峰現(xiàn)象的區(qū)域，完成兩段搜索時(shí)長(zhǎng)的分配，并記錄兩個(gè)峰值為最佳/次佳搜索時(shí)刻;

(5)對(duì)于沒有雙峰現(xiàn)象的區(qū)域，檢測(cè)單峰位置，記錄為其最佳搜索時(shí)刻;

(6)對(duì)所有區(qū)域，按照目標(biāo)出現(xiàn)次數(shù)進(jìn)行重要性排序;

(7)按照排序結(jié)果，對(duì)所有區(qū)域，以其最佳/次佳搜索時(shí)刻為中心，按照預(yù)先分配的時(shí)間長(zhǎng)度，檢測(cè)該時(shí)間區(qū)間是否被占用，若未被占用，確認(rèn)搜索時(shí)刻及時(shí)長(zhǎng)并更新時(shí)間占用情況，否則在最佳/次佳搜索時(shí)刻一定范圍內(nèi)移動(dòng)中心，檢測(cè)時(shí)間是否被占用;若未被占用，確認(rèn)搜索時(shí)刻及時(shí)長(zhǎng)并更新時(shí)間占用情況，否則縮短搜索時(shí)長(zhǎng)，以最佳/次佳搜索時(shí)刻為中心搜索，直至找到合適的搜索時(shí)刻;

(8)完成所有區(qū)域的初次分配后，檢測(cè)時(shí)間占用情況，對(duì)于未被占用的時(shí)間段，若時(shí)長(zhǎng)大于一定門限，根據(jù)在步驟7中縮短時(shí)長(zhǎng)的區(qū)域的最佳搜索時(shí)刻，選取距離最近的區(qū)域填補(bǔ)空白，直至無(wú)法填補(bǔ)。

3 試驗(yàn)驗(yàn)證及結(jié)果分析

為了驗(yàn)證算法的性能，分兩次采集了254個(gè)網(wǎng)站(數(shù)據(jù)集1)以及1 219個(gè)網(wǎng)站(數(shù)據(jù)集2)9天的數(shù)據(jù)，并按照 gi= Si，Ti{ }(1≤i≤M)的方式記錄關(guān)鍵詞的每次出現(xiàn)，以此作為試驗(yàn)驗(yàn)證的原始數(shù)據(jù)。驗(yàn)證過(guò)程模擬目標(biāo)搜索過(guò)程，即假設(shè)目標(biāo)為關(guān)鍵詞，且關(guān)鍵詞按照gi= Si，Ti{ }(1≤i≤M)的方式在網(wǎng)站上出現(xiàn)，搜索目標(biāo)時(shí)僅能搜索到網(wǎng)站實(shí)時(shí)出現(xiàn)的關(guān)鍵詞，不能搜索到已經(jīng)存在的關(guān)鍵詞。驗(yàn)證方法是利用前5天的數(shù)據(jù)訓(xùn)練目標(biāo)的概率分布和行為規(guī)律，然后利用后4天的數(shù)據(jù)分別按照制定的策略進(jìn)行統(tǒng)計(jì)，得到每天可以搜索到的關(guān)鍵詞次數(shù)，并對(duì)比不同算法搜索到關(guān)鍵詞數(shù)量的性能;本算法主要分析一天內(nèi)的行為規(guī)律，因此策略中總的搜索時(shí)間資源為1天。

3.1 行為規(guī)律分析

圖4分別給出數(shù)據(jù)集1和數(shù)據(jù)集2中行為規(guī)律時(shí)間相關(guān)性最強(qiáng)的3個(gè)網(wǎng)站的相關(guān)性變化曲線，其中橫坐標(biāo)代表間隔時(shí)間(天)，縱坐標(biāo)代表相關(guān)系數(shù)，每個(gè)點(diǎn)表示當(dāng)天數(shù)據(jù)的時(shí)間分布向量與第一天數(shù)據(jù)的時(shí)間分布向量之間的相關(guān)系數(shù)。

圖4 行為規(guī)律相關(guān)性變化曲線Fig.4 Relativity of behavior rule

由圖4可以看出，數(shù)據(jù)集1中各網(wǎng)站的相關(guān)系數(shù)隨著時(shí)間間隔的變大呈現(xiàn)變小的趨勢(shì)，而數(shù)據(jù)集2中網(wǎng)站的相關(guān)系數(shù)保持穩(wěn)定，沒有明顯的變小趨勢(shì)，而且相關(guān)性比數(shù)據(jù)集1中更大。這種現(xiàn)象說(shuō)明，不同的網(wǎng)站上關(guān)鍵詞的行為規(guī)律隨著時(shí)間延續(xù)在不斷變化，行為規(guī)律有一定的時(shí)效性;也說(shuō)明每個(gè)網(wǎng)站上不同日期的行為規(guī)律具有相關(guān)性，雖然相關(guān)程度不同，但可以利用前期的數(shù)據(jù)預(yù)測(cè)后期數(shù)據(jù)的行為規(guī)律，證明了本算法在原理上是可行的。

3.2 算法有效性對(duì)比

表1給出了利用數(shù)據(jù)集1和數(shù)據(jù)集2進(jìn)行驗(yàn)證的結(jié)果，其中衰減指數(shù)均選擇指數(shù)衰減。為了體現(xiàn)算法效果，將結(jié)果以平均分配方法(各區(qū)域分配相同的時(shí)長(zhǎng)，順序搜索)為基準(zhǔn)進(jìn)行了歸一化，并給出了本算法以及最優(yōu)搜索方法(只使用最優(yōu)搜索不利用行為規(guī)律)的性能提升對(duì)比，性能提升表示相應(yīng)算法獲取的關(guān)鍵詞數(shù)量與平均方法獲取的關(guān)鍵詞數(shù)量的比值;圖5給出了不同算法和數(shù)據(jù)集的性能提升對(duì)比，其中橫坐標(biāo)代表不同日期，縱坐標(biāo)代表性能提升倍數(shù)。

表1 算法性能提升對(duì)比表Table1 Comparison of performance advance

圖5 性能提升對(duì)比圖Fig.5 Comparison of performance advance

從表1和圖5可以看出，對(duì)于數(shù)據(jù)集1，最優(yōu)搜索方法的性能是平均算法的3～5倍，本文算法性能是平均算法的4～6倍，本文算法比最優(yōu)搜索方法性能提升20% ～50%;對(duì)于數(shù)據(jù)集2，最優(yōu)搜索方法的性能是平均算法的20～30倍，本文算法性能是平均算法的28～35倍，本文算法比最優(yōu)搜索方法性能提升15%～25%;對(duì)照?qǐng)D4可以看出，由于數(shù)據(jù)集2的行為規(guī)律在時(shí)間上的相關(guān)性更強(qiáng)，因此相對(duì)平均算法的性能提升效果更明顯。

3.3 訓(xùn)練數(shù)據(jù)對(duì)結(jié)果的影響

圖6給出了對(duì)于數(shù)據(jù)集1和數(shù)據(jù)集2，利用5天的數(shù)據(jù)進(jìn)行概率分布統(tǒng)計(jì)和行為規(guī)律統(tǒng)計(jì)，且采用不同的衰減因子β時(shí)，算法相對(duì)于平均分配算法性能提升倍數(shù)的結(jié)果對(duì)比，其中橫坐標(biāo)代表不同日期，縱坐標(biāo)代表性能提升倍數(shù)。無(wú)衰減的衰減因子為β=[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可以看出，對(duì)于數(shù)據(jù)集1，采用指數(shù)衰減因子時(shí)算法性能提升最大，說(shuō)明了不同日期行為規(guī)律相關(guān)性隨時(shí)間降低時(shí)，應(yīng)該采取快速衰減的β，保證行為規(guī)律的及時(shí)性，而使用1天訓(xùn)練數(shù)據(jù)的性能提升最差，則是因?yàn)橛?天數(shù)據(jù)得到的行為規(guī)律具有一定的不穩(wěn)定性;對(duì)于數(shù)據(jù)集2，使用1天訓(xùn)練數(shù)據(jù)時(shí)性能提升反而要好些，這是由于數(shù)據(jù)集2的5天訓(xùn)練數(shù)據(jù)中，行為規(guī)律非常穩(wěn)定，只有第3天的數(shù)據(jù)偏差較大，因此使用5天訓(xùn)練數(shù)據(jù)相當(dāng)于引入了一個(gè)噪聲，效果反而變差。通過(guò)分析可以看出，在算法使用過(guò)程中，需要兼顧行為規(guī)律的穩(wěn)定性和及時(shí)性，根據(jù)行為規(guī)律相關(guān)性的變化規(guī)律采用合理的衰減因子β:時(shí)間規(guī)律衰減快則選擇衰減快的β，時(shí)間規(guī)律穩(wěn)定則β的選擇對(duì)性能影響較小，因此一般情況下，建議選擇衰減較快的指數(shù)衰減因子。

4 結(jié)束語(yǔ)

本文通過(guò)分析目標(biāo)的行為規(guī)律，結(jié)合最優(yōu)搜索理論，提出了一種基于行為規(guī)律的搜索資源分配算法。利用網(wǎng)站上關(guān)鍵詞出現(xiàn)記錄進(jìn)行的模擬搜索試驗(yàn)證明了目標(biāo)行為規(guī)律的存在以及其在穩(wěn)定性、時(shí)效性等方面的特點(diǎn)，實(shí)驗(yàn)結(jié)果顯示，本文的方法相對(duì)于平均分配資源能夠大幅度提高搜索效率，相對(duì)于單獨(dú)使用最優(yōu)搜索方法，搜索效率也有顯著提高，在對(duì)大量信息源進(jìn)行信息搜索時(shí)具有應(yīng)用價(jià)值。另外，在實(shí)時(shí)處理?xiàng)l件下如何獲取各搜索區(qū)域完整的歷史信息問(wèn)題未在文中涉及，將是下一步研究的重點(diǎn)。

圖6 采用不同衰減因子β時(shí)性能提升對(duì)比圖Fig.6 Comparison of performance advance with different β

[1]朱清新.離散和連續(xù)空間的最優(yōu)搜索理論[M].北京:科學(xué)出版社，2005.ZHU Qing－xin.The optimal search theory in discrete and continuous space[M].Beijing:Science Press，2005.(in Chinese)

[2]陳建勇，王健.對(duì)隨機(jī)運(yùn)動(dòng)目標(biāo)的一種最優(yōu)搜索算法[J].海軍航空工程學(xué)院學(xué)報(bào)，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)搜索理論在入侵檢測(cè)系統(tǒng)中的應(yīng)用研究[J].計(jì)算機(jī)應(yīng)用與軟件，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)絡(luò)環(huán)境下用戶信息查找行為規(guī)律的實(shí)證分析[J].情報(bào)探索，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]苗強(qiáng)，周興社.基于行為規(guī)律的異常檢測(cè)技術(shù)研究[J].計(jì)算機(jī)工程與應(yīng)用，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.