胡六四

(安徽電子信息職業(yè)技術(shù)學(xué)院 軟件學(xué)院，安徽 蚌埠 233000)

在我國，伴隨著計(jì)算機(jī)技術(shù)和大數(shù)據(jù)的飛速發(fā)展，網(wǎng)絡(luò)數(shù)據(jù)目前已經(jīng)成為數(shù)據(jù)庫與文件管理系統(tǒng)的主要工具[1-2]。網(wǎng)絡(luò)數(shù)據(jù)庫具有面向多個(gè)客戶被同時(shí)共享訪問的特點(diǎn)[3]，網(wǎng)絡(luò)數(shù)據(jù)庫擴(kuò)大的同時(shí)網(wǎng)絡(luò)數(shù)據(jù)庫的結(jié)構(gòu)拓?fù)湟舶l(fā)生了改變，在這種情況下，使用一個(gè)有效的聚類算法從網(wǎng)絡(luò)數(shù)據(jù)庫內(nèi)搜索到需要的信息成為目前急需解決的問題[4-5]。但是，網(wǎng)絡(luò)數(shù)據(jù)庫內(nèi)的數(shù)據(jù)信息搜索能夠從客戶尋求服務(wù)的操作過程開始，提高網(wǎng)絡(luò)數(shù)據(jù)庫的搜索速度是行之有效的策略[6]。

本文使用模糊C均值聚類來對網(wǎng)絡(luò)數(shù)據(jù)庫特定數(shù)據(jù)的檢索，將網(wǎng)絡(luò)數(shù)據(jù)庫特定數(shù)據(jù)檢索問題轉(zhuǎn)化為一系列面向模糊C均值聚類問題進(jìn)行檢索，從而考查本文所提算法檢索復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)庫特定數(shù)據(jù)的能力。

1　網(wǎng)絡(luò)數(shù)據(jù)庫特定數(shù)據(jù)檢索算法

如圖1所示，數(shù)據(jù)與POS標(biāo)注依次出現(xiàn)于第一與第二列中，在第三列中則表明了此處數(shù)據(jù)是否和奇周邊數(shù)據(jù)存在數(shù)據(jù)關(guān)系。當(dāng)此數(shù)據(jù)與其左邊鄰近數(shù)據(jù)存在數(shù)據(jù)關(guān)系時(shí)，以“LH”(代表“父節(jié)點(diǎn)位于左處”)來表示；當(dāng)此數(shù)據(jù)與其右邊數(shù)據(jù)存在關(guān)系，以“RH”表示；當(dāng)不存在上述關(guān)系時(shí)，則將其表示為“O”。其中，“_”符號(hào)代表其后邊字串是當(dāng)存在數(shù)據(jù)關(guān)系時(shí)所對應(yīng)的數(shù)據(jù)關(guān)系種類。

圖1鄰近數(shù)據(jù)關(guān)系檢索器圖2鄰近數(shù)據(jù)關(guān)系的標(biāo)注形式Ⅰ圖3鄰近數(shù)據(jù)的關(guān)系標(biāo)注形式Ⅱ

本文從構(gòu)建樹的數(shù)據(jù)結(jié)構(gòu)層面進(jìn)行分析，先對每個(gè)數(shù)據(jù)序列是否跟其父節(jié)點(diǎn)存在相鄰關(guān)系并進(jìn)一步判斷是否為完整子樹節(jié)點(diǎn)，當(dāng)滿足上述條件時(shí)則為其標(biāo)注數(shù)據(jù)關(guān)系，具體見圖2。

通過對比圖1與圖3可知，圖3內(nèi)的標(biāo)記“O”具有明顯歧義性質(zhì)。該標(biāo)記一方面可以表示該數(shù)據(jù)和鄰近數(shù)據(jù)間無數(shù)據(jù)關(guān)系，另一方面也能夠表示該數(shù)據(jù)和鄰近數(shù)據(jù)間存在數(shù)據(jù)關(guān)系，只是在當(dāng)前條件下不能對其進(jìn)行歸約處理而只可將其通過“O”的形式進(jìn)行標(biāo)記。這是因?yàn)榇嬖跊]有找齊該數(shù)據(jù)的所有數(shù)據(jù)類型(例如，“主演”與“的”)或者是在同一方向上的連續(xù)數(shù)據(jù)關(guān)系只能被歸約為最低模型策略而受到限制(例如，“知名”這類數(shù)據(jù))。為將此類歧義充分消除，可以重新回歸至圖1的方式，對于具有數(shù)據(jù)關(guān)系的所有相鄰數(shù)據(jù)都需標(biāo)注。為構(gòu)建樹結(jié)構(gòu)，需利用專門的歸約決策標(biāo)注器對規(guī)約數(shù)據(jù)進(jìn)行標(biāo)注。圖4(a)中的最后一列“r”代表此數(shù)據(jù)符合歸約條件，可以構(gòu)建相應(yīng)的模型。

為確保能夠以最快速度對網(wǎng)絡(luò)數(shù)據(jù)庫特定數(shù)據(jù)進(jìn)行全局搜索，選擇CRF模型作為歸約決策的標(biāo)注器。但是在實(shí)際情況下，通過這一順序標(biāo)注的方式無法達(dá)到對全局進(jìn)行真正的快速搜索目標(biāo)。所以我們對數(shù)據(jù)關(guān)系以及歸約決策進(jìn)行統(tǒng)一標(biāo)記，并通過“_”符號(hào)進(jìn)行連接，圖4(b)顯示了以標(biāo)注器構(gòu)建序列的具體模型。采取這一標(biāo)注方式的另外一個(gè)原因是可以防止在歸約決策過程中對于數(shù)據(jù)關(guān)系的標(biāo)注產(chǎn)生過度依賴。

圖4鄰近數(shù)據(jù)的關(guān)系標(biāo)注形式Ⅲ

從另一層面考慮，采用以上標(biāo)注形式檢索“鄰近”數(shù)據(jù)的關(guān)系時(shí)更符合網(wǎng)絡(luò)數(shù)據(jù)庫特定數(shù)據(jù)的直接表達(dá)方式，同時(shí)將歸約決策進(jìn)行獨(dú)立處理后，也可以更加清晰地表達(dá)歸約約束。從圖5看出，可以利用流程圖的方式對復(fù)雜英語進(jìn)行整體檢索。

當(dāng)把網(wǎng)絡(luò)數(shù)據(jù)庫特定數(shù)據(jù)的鄰近關(guān)系及其歸約決策標(biāo)注都輸入之后，其中一些數(shù)據(jù)被歸約成鄰近數(shù)據(jù)的孩子，而剩余數(shù)據(jù)則在完成重新組合后進(jìn)入后續(xù)檢索過程，直至剩余單一數(shù)據(jù)或至已經(jīng)沒有被標(biāo)記成可歸約類型的數(shù)據(jù)為止。

2　實(shí)驗(yàn)結(jié)果分析

本實(shí)驗(yàn)在英語標(biāo)準(zhǔn)庫上完成。相關(guān)英語數(shù)據(jù)從賓州樹庫的《華爾街日報(bào)》語料中選取，具體劃分標(biāo)準(zhǔn)為：以02～21節(jié)作為訓(xùn)練樣本，以22節(jié)作為開發(fā)集，并對23節(jié)進(jìn)行測試(總共包含的數(shù)據(jù)數(shù)量為53624)。通過Penn2Malt工具獲得統(tǒng)一的中心數(shù)據(jù)提取規(guī)則并得到數(shù)據(jù)關(guān)系集合，該模型中總共包括了12種不同的數(shù)據(jù)關(guān)系。對于測試集與開發(fā)集上的POS標(biāo)注則通過MXPOST分析軟件自主獲取，對于測試集進(jìn)行標(biāo)注可以實(shí)現(xiàn)高達(dá)97.41%的正確率。

圖5檢索算法的流程示意圖

本文實(shí)驗(yàn)將分割策略應(yīng)用到了MaltParser中，以此提高檢索速率，根據(jù)后續(xù)輸入數(shù)據(jù)的POS標(biāo)注對SVM分類器進(jìn)行分割從而使其形成許多小分類器，同時(shí)將各分類器的訓(xùn)練案例數(shù)量設(shè)定為至少1000。Yamada03對應(yīng)的特征選取窗口寬度是6，并且將該數(shù)據(jù)加入到數(shù)據(jù)關(guān)系特征集中，SVM分類器是在對左焦點(diǎn)數(shù)據(jù)進(jìn)行POS標(biāo)注的劃分之后再進(jìn)行訓(xùn)練。

如下所示，表1與表2中分別顯示了5個(gè)基線系統(tǒng)與不同檢索模型對英語數(shù)據(jù)集進(jìn)行測試結(jié)果。其中，R代表模型中各訓(xùn)練實(shí)例對應(yīng)的數(shù)據(jù)關(guān)系標(biāo)記數(shù)量。以Viterbi算法為基礎(chǔ)的CRF序列的模型復(fù)雜度是O(R2n)?；谀Ｐ退惴ㄔ谒阉鬏斎刖W(wǎng)絡(luò)數(shù)據(jù)庫特定數(shù)據(jù)時(shí)所需的模型個(gè)數(shù)上限為n，對應(yīng)的算法復(fù)雜度是O(R2n2)。

表1　不同模型的網(wǎng)絡(luò)數(shù)據(jù)庫特定數(shù)據(jù)檢索測試結(jié)果

表2　各基于模型的模型英語檢索結(jié)果

對上述各個(gè)模型進(jìn)行對比分析可知，基于模型算法與基于轉(zhuǎn)換算法具有更高的完全匹配率與數(shù)據(jù)正確率。

檢索表2結(jié)果顯示，采用依次標(biāo)注法(LDP2)時(shí)，由于無法達(dá)到最快的全局結(jié)構(gòu)檢索速率，并且檢索的精度也不高；選擇分離模型則可以根據(jù)各個(gè)模型的特征獲得良好的性能；LDPnrAll歸約可以在當(dāng)前模型中生成完整數(shù)據(jù)，因此模型中將存在長度大于1的網(wǎng)絡(luò)數(shù)據(jù)庫特定數(shù)據(jù)，導(dǎo)致線性模糊C均值聚類的性能受到限制；對于LDPdiv而言，其能夠有效消除標(biāo)記“O”引起的歧義，因此有助于提高檢索精度。實(shí)際上，建立在模糊C均值聚類之上的網(wǎng)絡(luò)數(shù)據(jù)庫特定數(shù)據(jù)檢索算法具有很強(qiáng)的適應(yīng)性，當(dāng)語料標(biāo)注集較大或需要高搜索效率時(shí)，可利用拆分標(biāo)注與壓縮標(biāo)注集的方式來達(dá)到所需的性能；同時(shí)，自然語言數(shù)據(jù)具有聚集性，檢索遇到高模型情況時(shí)，序列長度將快速降低，此時(shí)如果網(wǎng)絡(luò)數(shù)據(jù)庫特定數(shù)據(jù)長度較大也依然不會(huì)占用較多的時(shí)間。

3　結(jié)論

本文提出了一種依賴模糊C均值聚類的網(wǎng)絡(luò)數(shù)據(jù)庫特定數(shù)據(jù)檢索算法。以網(wǎng)絡(luò)數(shù)據(jù)庫特定數(shù)據(jù)為檢索單位，自底向上構(gòu)建網(wǎng)絡(luò)數(shù)據(jù)庫特定數(shù)據(jù)的各向異性模型。實(shí)驗(yàn)結(jié)果表明：本文網(wǎng)絡(luò)數(shù)據(jù)庫特定數(shù)據(jù)檢索算法在檢索精度方面和當(dāng)前各主流算法相近，準(zhǔn)確率則介于基于圖與基于轉(zhuǎn)換算法間，同時(shí)可以達(dá)到極高的檢索速率。該算法對于網(wǎng)絡(luò)數(shù)據(jù)庫特定數(shù)據(jù)進(jìn)行搜索處理時(shí)將表現(xiàn)出極大的優(yōu)勢。

(編輯：嚴(yán)佩峰)