基于群體智能的半結(jié)構(gòu)化數(shù)據(jù)查詢(xún)優(yōu)化算法

高俊杰，楊 帆

(1.山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，山西太原030006；2.山西醫(yī)科大學(xué)計(jì)算機(jī)教學(xué)部，山西太原030001)

1 引言

隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展，人類(lèi)已經(jīng)逐漸走向全面數(shù)字化時(shí)代，人們?cè)诟鱾€(gè)領(lǐng)域中都開(kāi)始應(yīng)用數(shù)字化技術(shù)，為此需要研究能夠高效率處理大數(shù)據(jù)的方法，解決數(shù)據(jù)智能化等問(wèn)題[1-3]。為了能夠區(qū)分不同類(lèi)型的數(shù)據(jù)，將網(wǎng)絡(luò)數(shù)據(jù)按照信息結(jié)構(gòu)進(jìn)行劃分，為計(jì)算機(jī)系統(tǒng)提供靈活的數(shù)據(jù)轉(zhuǎn)換平臺(tái)[4]。半結(jié)構(gòu)化數(shù)據(jù)由于其組成信息結(jié)構(gòu)的不完整性，需要不斷地對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行修改，再根據(jù)半結(jié)構(gòu)化數(shù)據(jù)的特征完成數(shù)據(jù)查詢(xún)、數(shù)據(jù)采集、數(shù)據(jù)分析等內(nèi)容，半結(jié)構(gòu)化數(shù)據(jù)查詢(xún)是較為復(fù)雜的一項(xiàng)基礎(chǔ)工作，只有從多角度完成數(shù)據(jù)分析并及時(shí)發(fā)現(xiàn)潛在數(shù)據(jù)才能穩(wěn)定支持計(jì)算機(jī)系統(tǒng)運(yùn)行[5，6]。

文獻(xiàn)[7]提出一種基于路徑索引的密集鄰域圖數(shù)據(jù)查詢(xún)方法，該方法通過(guò)分析頂點(diǎn)密集領(lǐng)域數(shù)據(jù)特點(diǎn)，設(shè)計(jì)頂點(diǎn)密集鄰域的數(shù)據(jù)查詢(xún)模式，運(yùn)用B+樹(shù)方法對(duì)數(shù)據(jù)查詢(xún)路徑進(jìn)行索引與存儲(chǔ)。實(shí)驗(yàn)結(jié)果表明，該方法能夠提升數(shù)據(jù)查詢(xún)與處理性能，但是存在數(shù)據(jù)查詢(xún)量較少的問(wèn)題。文獻(xiàn)[8]提出了基于Python的協(xié)議棧軟件內(nèi)部數(shù)據(jù)查詢(xún)方法，該方法通過(guò)Linux系統(tǒng)與Windows系統(tǒng)的兼容，實(shí)現(xiàn)直接使用命令在屏幕上輸出所查數(shù)據(jù)結(jié)構(gòu)中的所有數(shù)據(jù)。實(shí)驗(yàn)結(jié)果表明，該方法數(shù)據(jù)查詢(xún)精度較高，但是耗時(shí)較長(zhǎng)。除此之外，文獻(xiàn)[9]還提出了基于符號(hào)語(yǔ)義的不完整數(shù)據(jù)聚集查詢(xún)處理算法，該算法對(duì)傳統(tǒng)關(guān)系數(shù)據(jù)庫(kù)模型進(jìn)行了擴(kuò)展，實(shí)現(xiàn)對(duì)不完整數(shù)據(jù)聚集的區(qū)間估計(jì)，并在該區(qū)間內(nèi)實(shí)現(xiàn)對(duì)數(shù)據(jù)的查詢(xún)。實(shí)驗(yàn)結(jié)果表明，該算法數(shù)據(jù)查詢(xún)速度較快，但是得到的數(shù)據(jù)量較少。

針對(duì)現(xiàn)有方法存在的問(wèn)題，提出基于群體智能的半結(jié)構(gòu)化數(shù)據(jù)查詢(xún)優(yōu)化算法。

2 基于粒子群優(yōu)化算法的半結(jié)構(gòu)化數(shù)據(jù)識(shí)別

采用粒子群優(yōu)化算法作為半結(jié)構(gòu)化數(shù)據(jù)查詢(xún)模型的優(yōu)化算法，應(yīng)用該算法的環(huán)境移動(dòng)特征能夠更加精準(zhǔn)、快速地在一定范圍內(nèi)尋找可靠數(shù)據(jù)，可以在三維空間中建立數(shù)據(jù)質(zhì)量與數(shù)據(jù)規(guī)模的位置檢索空間，在空間內(nèi)建立多種數(shù)據(jù)結(jié)構(gòu)代表粒子，粒子在半結(jié)構(gòu)化模型中的飛行過(guò)程稱(chēng)為查詢(xún)過(guò)程，具體的飛行軌跡與飛行終點(diǎn)是根據(jù)粒子數(shù)據(jù)的自身經(jīng)驗(yàn)來(lái)完成動(dòng)態(tài)調(diào)整的，具有不確定性[10]。三維空間粒子分布如圖1所示。

圖1 三維空間粒子分布

根據(jù)圖1可知，基本的粒子群算法應(yīng)用需要建設(shè)一個(gè)三維立體空間為粒子群提供飛行場(chǎng)地，每個(gè)粒子所在的粒子種群可以代表在三維空間中的精準(zhǔn)位置，粒子飛行的速度與種群迭代速度主要通過(guò)設(shè)定位置參數(shù)的方式進(jìn)行表示，基本粒子群中的粒子超出標(biāo)準(zhǔn)飛行速度，則三維立體空間內(nèi)的維度參數(shù)會(huì)根據(jù)超出的飛行速度重新定義，制定超出空間邊界的參數(shù)值[11]。標(biāo)準(zhǔn)的粒子群算法基于基本粒子群算法的三維立體空間，可以在粒子飛行過(guò)程中完成算法的慣性參數(shù)計(jì)算，相對(duì)于基本粒子群算法有著較強(qiáng)的空間查詢(xún)能力，此算法在半結(jié)構(gòu)化查詢(xún)模型中主要通過(guò)線性遞增的方式調(diào)節(jié)數(shù)據(jù)的檢索范圍，實(shí)現(xiàn)了全方面的數(shù)據(jù)結(jié)構(gòu)探索。在結(jié)構(gòu)模型中進(jìn)行深度的數(shù)據(jù)種子探索，為粒子群的收斂速度提供保障，粒子飛行的基本慣性參數(shù)可以在線性關(guān)系的基礎(chǔ)上引用常數(shù)因子，粒子飛行速度與常數(shù)因子呈現(xiàn)權(quán)重關(guān)系。離散粒子群算法是粒子群優(yōu)化算法中的高階算法，能夠?qū)Τ掷m(xù)性函數(shù)提出優(yōu)化解法，粒子在每個(gè)空間維度中的飛行狀態(tài)都需要經(jīng)過(guò)向量標(biāo)準(zhǔn)進(jìn)行評(píng)判，若粒子的飛行速度沒(méi)有受到半結(jié)構(gòu)化數(shù)據(jù)查詢(xún)模型的限制，粒子群則建立隨機(jī)數(shù)據(jù)檢索范圍，針對(duì)更深層次的算法搜索空間建立粒子飛行節(jié)點(diǎn)[12]。離散粒子分布狀態(tài)如下圖2所示。

圖2 離散粒子分布狀態(tài)

中心學(xué)習(xí)算法建立在粒子群中的共享中央位置，此算法能夠?yàn)檎麄€(gè)粒子群中的每個(gè)粒子解決粒子飛行層面問(wèn)題，當(dāng)粒子種群中的部分個(gè)體產(chǎn)生位置聚攏情況時(shí)，中心學(xué)習(xí)算法能夠協(xié)同粒子參數(shù)與種群的數(shù)據(jù)查詢(xún)機(jī)制，為該種群的局部空間設(shè)定閾值。在中心學(xué)習(xí)算法中的迭代關(guān)系主要依靠粒子的維度空間運(yùn)轉(zhuǎn)速度，中心學(xué)習(xí)算法的迭代運(yùn)行公式為

(1)

式中，v代表普通粒子在維度空間內(nèi)的飛行速度；x代表中心學(xué)習(xí)算法中的精英粒子在維度空間中的飛行速度；t代表維度空間內(nèi)的種群飛行時(shí)間；ω代表粒子慣性權(quán)重。

粒子離散過(guò)程如圖3所示。

圖3 粒子離散過(guò)程

離散學(xué)習(xí)算法是一種能夠在數(shù)據(jù)查詢(xún)模型中進(jìn)行大范圍數(shù)據(jù)查詢(xún)的搜索算法，中心學(xué)習(xí)算法主要用于計(jì)算模型數(shù)據(jù)中的精英粒子，離散學(xué)習(xí)算法主要用于計(jì)算模型數(shù)據(jù)中的普通粒子，普通粒子需要對(duì)應(yīng)每個(gè)維度空間階層，在離散學(xué)習(xí)層次上需要具備不同的粒子個(gè)體。離散學(xué)習(xí)算法的迭代運(yùn)行公式為

(2)

式中，λ代表粒子在空間中的飛行速度；t′代表粒子在空間中的總飛行時(shí)間；ω0代表粒子學(xué)習(xí)對(duì)象的權(quán)重值；?代表粒子的分布離散系數(shù)。

為了解決粒子群在半結(jié)構(gòu)化查詢(xún)模型中的粒子收斂不均勻的現(xiàn)象，在模型中進(jìn)行維度協(xié)同，應(yīng)用粒子的自身參數(shù)設(shè)定維度閾值，根據(jù)每種類(lèi)型的粒子參數(shù)進(jìn)行維度內(nèi)的數(shù)據(jù)更新。不同維度下的離散數(shù)據(jù)如圖4所示。

圖4 不同維度下的離散數(shù)據(jù)

觀察圖4可知，假設(shè)一定范圍內(nèi)的結(jié)構(gòu)模型中維度為N，則粒子種群中每個(gè)粒子可以被描述的向量需要進(jìn)行維度劃分，在粒子運(yùn)行的周期內(nèi)完成粒子與固定維度的關(guān)聯(lián)。由于維度空間內(nèi)的位置劃分具有一定的隨機(jī)特性，所以需要每層粒子在飛行前進(jìn)行隨機(jī)采樣，進(jìn)行不同維度空間的粒子協(xié)同，確保每個(gè)粒子在隨機(jī)維度中都能完成半結(jié)構(gòu)化數(shù)據(jù)識(shí)別。

3 基于群體智能的半結(jié)構(gòu)化數(shù)據(jù)查詢(xún)優(yōu)化算法

以半結(jié)構(gòu)化數(shù)據(jù)識(shí)別結(jié)果為基礎(chǔ)，進(jìn)行半結(jié)構(gòu)化數(shù)據(jù)查詢(xún)優(yōu)化。傳統(tǒng)半結(jié)構(gòu)化數(shù)據(jù)模型的設(shè)計(jì)不考慮數(shù)據(jù)的查詢(xún)路徑以及數(shù)據(jù)查詢(xún)方法等問(wèn)題，主要設(shè)計(jì)半結(jié)構(gòu)化數(shù)據(jù)模型的整體構(gòu)架以及數(shù)據(jù)儲(chǔ)存空間，而本文在半結(jié)構(gòu)化數(shù)據(jù)模型建設(shè)過(guò)程中添加數(shù)據(jù)導(dǎo)向體系，能夠?qū)⒉樵?xún)數(shù)據(jù)在有向圖中進(jìn)行表示，可以在不同數(shù)據(jù)環(huán)境中與其它種類(lèi)的查詢(xún)數(shù)據(jù)相互轉(zhuǎn)換。離散數(shù)據(jù)采集過(guò)程如圖5所示。

圖5 離散數(shù)據(jù)采集過(guò)程

數(shù)據(jù)標(biāo)記技術(shù)隨著數(shù)據(jù)運(yùn)用功能的不斷豐富，在目前的數(shù)據(jù)傳輸領(lǐng)域、數(shù)據(jù)識(shí)別領(lǐng)域、數(shù)據(jù)采集、查詢(xún)等領(lǐng)域均有所運(yùn)用，數(shù)據(jù)標(biāo)記技術(shù)應(yīng)用在空間結(jié)構(gòu)的半結(jié)構(gòu)化數(shù)據(jù)查詢(xún)模型中，主要體現(xiàn)在數(shù)據(jù)結(jié)構(gòu)樹(shù)中，在數(shù)據(jù)樹(shù)中首先建立查詢(xún)對(duì)象支路，在每條查詢(xún)支路中安裝編程接口，再通過(guò)文檔接口映射形成一套數(shù)據(jù)查詢(xún)模型集合，集合的運(yùn)行是經(jīng)過(guò)應(yīng)用程序?qū)Σ樵?xún)文檔的數(shù)據(jù)屬性提取后實(shí)現(xiàn)的。

隨著半結(jié)構(gòu)化數(shù)據(jù)模型中的數(shù)據(jù)表現(xiàn)形式越來(lái)越豐富，數(shù)據(jù)查詢(xún)模型中的數(shù)據(jù)文檔對(duì)數(shù)據(jù)挖掘需求越來(lái)越大。需要對(duì)數(shù)據(jù)進(jìn)行深入挖掘，深入挖掘示意圖如圖6所示。

圖6 數(shù)據(jù)深入挖掘示意圖

圖6中，α、θ分別表示不同區(qū)域的數(shù)據(jù)挖掘方向。被標(biāo)記的半結(jié)構(gòu)化數(shù)據(jù)模型還具有靈活性強(qiáng)的特點(diǎn)，能夠在任意時(shí)間內(nèi)完成數(shù)據(jù)查詢(xún)程序的更改，數(shù)據(jù)查詢(xún)結(jié)構(gòu)內(nèi)部也在不斷地進(jìn)行數(shù)據(jù)庫(kù)更新工作，還能夠在同一查詢(xún)階段建立多種版本的數(shù)據(jù)文檔，為動(dòng)態(tài)查詢(xún)程序增加可利用點(diǎn)。由于數(shù)據(jù)自身具備流動(dòng)特性，所以本文針對(duì)頻繁變化的數(shù)據(jù)內(nèi)容建立標(biāo)記特征的半結(jié)構(gòu)化模型，在已知的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上，開(kāi)發(fā)文檔版本與文檔版本之間的了半結(jié)構(gòu)化模型。設(shè)計(jì)子半結(jié)構(gòu)化模型的文檔版本查詢(xún)閾值，不斷累積查詢(xún)用戶與查詢(xún)參數(shù)之間的融合信息。優(yōu)化時(shí)間如圖7所示。

圖7 優(yōu)化時(shí)間

根據(jù)圖7可知，T代表優(yōu)化時(shí)間，S1代表優(yōu)化距離。半結(jié)構(gòu)化數(shù)據(jù)查詢(xún)模型中常常出現(xiàn)模糊數(shù)據(jù)的拓展問(wèn)題，通過(guò)統(tǒng)計(jì)不同數(shù)據(jù)庫(kù)中的一些不確定性信息可知，這些模糊數(shù)據(jù)在模型中容易與其它類(lèi)型查詢(xún)數(shù)據(jù)結(jié)合成為隨機(jī)數(shù)據(jù)集合或粗糙數(shù)據(jù)集合，不方便查詢(xún)運(yùn)行程序的管理。為此，基于群體智能標(biāo)簽樹(shù)研究不確定性查詢(xún)數(shù)據(jù)的節(jié)點(diǎn)關(guān)系，建立基本模型，優(yōu)化數(shù)據(jù)查詢(xún)過(guò)程中的模糊數(shù)據(jù)與其它數(shù)據(jù)建立不確定關(guān)系問(wèn)題?；谌后w智能的半結(jié)構(gòu)化數(shù)據(jù)查詢(xún)優(yōu)化過(guò)程如圖8所示。

圖8 半結(jié)構(gòu)化數(shù)據(jù)查詢(xún)優(yōu)化流程

標(biāo)簽樹(shù)在半結(jié)構(gòu)化數(shù)據(jù)查詢(xún)模型中關(guān)聯(lián)著每層數(shù)據(jù)結(jié)構(gòu)中的節(jié)點(diǎn)，區(qū)分?jǐn)?shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)層次，查詢(xún)標(biāo)簽樹(shù)的內(nèi)部數(shù)據(jù)信息時(shí)可以采用數(shù)學(xué)歸納法建立數(shù)據(jù)模型與標(biāo)簽數(shù)據(jù)的等價(jià)關(guān)系，要求每層次的數(shù)據(jù)結(jié)構(gòu)與節(jié)點(diǎn)中的數(shù)據(jù)可進(jìn)行區(qū)分。設(shè)定標(biāo)簽樹(shù)在數(shù)據(jù)模型中的應(yīng)用語(yǔ)言可以跨平臺(tái)使用，在傳統(tǒng)數(shù)據(jù)系統(tǒng)d基礎(chǔ)上增加語(yǔ)言的分析能力，簡(jiǎn)約化分析標(biāo)簽樹(shù)語(yǔ)言的精準(zhǔn)性。定義標(biāo)簽樹(shù)信息在數(shù)據(jù)結(jié)構(gòu)中的決策規(guī)則為：

DR=(l→ac)∧(l0→a0c0)

∧…∧(ln→ancn)?

(l→ad)∧(l0→a0d0)

∧…∧(ln→andn)

(3)

式中，(l→ac)代表標(biāo)簽樹(shù)數(shù)據(jù)節(jié)點(diǎn)中的決策點(diǎn)；(l→ad)代表模型決策后的數(shù)據(jù)關(guān)聯(lián)內(nèi)容，主要用于半結(jié)構(gòu)化數(shù)據(jù)決策與分化。

依據(jù)式(3)所示的決策規(guī)則，確定數(shù)據(jù)關(guān)聯(lián)關(guān)系，從而實(shí)現(xiàn)半結(jié)構(gòu)化數(shù)據(jù)的查詢(xún)優(yōu)化。

4 實(shí)驗(yàn)測(cè)試

為了評(píng)估本文研究的基于群體智能的半結(jié)構(gòu)化數(shù)據(jù)查詢(xún)優(yōu)化算法的有效性，設(shè)定實(shí)驗(yàn)測(cè)試環(huán)節(jié)。選用6個(gè)基本函數(shù)作為粒子群優(yōu)化算法的綜合性能基準(zhǔn)測(cè)試函數(shù)，前兩個(gè)函數(shù)每個(gè)函數(shù)中只有一個(gè)峰值，后四個(gè)函數(shù)具有多個(gè)峰值，多峰值函數(shù)用來(lái)檢測(cè)算法在半結(jié)構(gòu)化模型中的數(shù)據(jù)查詢(xún)量，單峰函數(shù)用來(lái)檢測(cè)算法在半結(jié)構(gòu)化數(shù)據(jù)模型中的查詢(xún)功能強(qiáng)度。

實(shí)驗(yàn)中首先測(cè)定中心-離散學(xué)習(xí)算法，將算法代入函數(shù)中重復(fù)查詢(xún)數(shù)據(jù)20次，記錄每次查詢(xún)結(jié)果，計(jì)算查詢(xún)結(jié)果的均值、方差、極差等值。應(yīng)用中心-離散學(xué)習(xí)算法對(duì)多峰函數(shù)的數(shù)據(jù)收斂效果進(jìn)行確認(rèn)，尋找算法中的函數(shù)最佳峰值，并在多峰值的環(huán)境中尋找周期性的函數(shù)最優(yōu)解。表1為各函數(shù)在算法中的參數(shù)設(shè)定值：

表1 參數(shù)設(shè)定值

實(shí)驗(yàn)中，為了保障不同函數(shù)在算法中的同步性，需要在粒子種群中設(shè)置相同維度的迭代運(yùn)算，每次完成迭代運(yùn)算的函數(shù)會(huì)統(tǒng)計(jì)自身的目標(biāo)函數(shù)值與峰值在函數(shù)環(huán)境中的最佳位置。實(shí)驗(yàn)中還應(yīng)用維爾克森雙尾秩和檢驗(yàn)方法對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行驗(yàn)證，圖9為本文算法對(duì)不同測(cè)試函數(shù)的數(shù)據(jù)查詢(xún)結(jié)果。

圖9 不同方法數(shù)據(jù)查詢(xún)量對(duì)比結(jié)果

根據(jù)圖9可知，本文選用的粒子群優(yōu)化算法不僅可以實(shí)現(xiàn)對(duì)半結(jié)構(gòu)化數(shù)據(jù)的查詢(xún)，而且隨著迭代次數(shù)的增長(zhǎng)，數(shù)據(jù)查詢(xún)量整體上呈現(xiàn)出逐漸增長(zhǎng)的趨勢(shì)，提高了維度空間內(nèi)非結(jié)構(gòu)化數(shù)據(jù)的查詢(xún)深度。

為了進(jìn)一步驗(yàn)證本文算法的有效性，對(duì)比基于路徑索引的密集鄰域圖數(shù)據(jù)查詢(xún)方法(文獻(xiàn)[7]方法)和基于Python的協(xié)議棧軟件內(nèi)部數(shù)據(jù)查詢(xún)方法(文獻(xiàn)[8]方法)與本文算法的數(shù)據(jù)查詢(xún)優(yōu)化時(shí)間，結(jié)果如下表2可知。

表2 數(shù)據(jù)查詢(xún)優(yōu)化時(shí)間對(duì)比結(jié)果

根據(jù)表2中的數(shù)據(jù)可知，本文提出的基于群體智能的半結(jié)構(gòu)化數(shù)據(jù)查詢(xún)優(yōu)化算法優(yōu)化時(shí)間小于傳統(tǒng)優(yōu)化算法。這是由于提出的算法引入了數(shù)據(jù)分析策略，具有很好的集中性，可以在短時(shí)間內(nèi)完成數(shù)據(jù)的分析。

綜上所述，提出的基于群體智能的半結(jié)構(gòu)化數(shù)據(jù)查詢(xún)優(yōu)化算法優(yōu)化能力更強(qiáng)，優(yōu)化效果更好，更適用于實(shí)際的數(shù)據(jù)優(yōu)化工作。

5 結(jié)論

半結(jié)構(gòu)化數(shù)據(jù)查詢(xún)模型自身具有結(jié)構(gòu)特性，相對(duì)于其它結(jié)構(gòu)的數(shù)據(jù)查詢(xún)模型需要不斷進(jìn)行數(shù)據(jù)修復(fù)與結(jié)構(gòu)構(gòu)建，本文基于群體智能方法，選用粒子群優(yōu)化算法對(duì)傳統(tǒng)半結(jié)構(gòu)化數(shù)據(jù)查詢(xún)模型進(jìn)行改良，從數(shù)據(jù)查詢(xún)模型的結(jié)構(gòu)、數(shù)據(jù)查詢(xún)模型維度空間以及數(shù)據(jù)查詢(xún)方式作為切入點(diǎn)，增強(qiáng)半結(jié)構(gòu)化數(shù)據(jù)查詢(xún)模型的可靠性與高效性。實(shí)驗(yàn)結(jié)果表明，該算法具有半結(jié)構(gòu)化數(shù)據(jù)查詢(xún)量大和數(shù)據(jù)查詢(xún)時(shí)間較短的優(yōu)勢(shì)。