基于行為規(guī)律的搜索資源分配新算法*

褚衍杰，徐正國

(盲信號處理重點實驗室，成都610041)

1 引言

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

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

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

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

2 算法模型

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

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

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

算法用到的符號如下:待搜索區(qū)域為 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)時刻;算法的結(jié)果為 R= {r1，r2，…，rN}，其中 ri={ Si，TLi，TSi}，1≤i≤N，表示了從時間 TSi開始搜索區(qū)域Si，共搜索TLi長的時間。

2.1 區(qū)域搜索時長分配

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

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

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

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

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

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

(3)時長分配策略

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

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

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

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

max P[f]

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

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

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

2.2 最佳搜索時刻檢測

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

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

按照上述方法建立每個區(qū)域目標(biāo)行為的時間分布，該分布可能呈現(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)目標(biāo)是圖2中搜索時間段內(nèi)曲線覆蓋的面積最大，但是通過分析實際數(shù)據(jù)發(fā)現(xiàn)，對應(yīng)每個區(qū)域的行為規(guī)律，圖2中曲線的形狀差異非常大，優(yōu)化復(fù)雜，因此選取了一種相對較優(yōu)的簡化方法，便于在實際工程中使用。以雙峰規(guī)律為例說明分配方法如下:

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

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

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

2.3 時間資源分配策略制定

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

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

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

對于流程的具體說明如下:

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

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

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

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

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

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

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

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

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

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

3.1 行為規(guī)律分析

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

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

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

3.2 算法有效性對比

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

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

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

4 結(jié)束語

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

圖6 采用不同衰減因子β時性能提升對比圖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]陳建勇，王健.對隨機(jī)運動目標(biāo)的一種最優(yōu)搜索算法[J].海軍航空工程學(xué)院學(xué)報，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)中的應(yīng)用研究[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ī)律的實證分析[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]苗強(qiáng)，周興社.基于行為規(guī)律的異常檢測技術(shù)研究[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.