依賴模糊C均值聚類的網(wǎng)絡(luò)數(shù)據(jù)庫特定數(shù)據(jù)檢索算法

胡六四

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

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

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

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

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

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

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

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

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

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

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

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

2　實驗結(jié)果分析

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

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

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

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

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

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

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

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

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ù)的各向異性模型。實驗結(jié)果表明：本文網(wǎng)絡(luò)數(shù)據(jù)庫特定數(shù)據(jù)檢索算法在檢索精度方面和當前各主流算法相近，準確率則介于基于圖與基于轉(zhuǎn)換算法間，同時可以達到極高的檢索速率。該算法對于網(wǎng)絡(luò)數(shù)據(jù)庫特定數(shù)據(jù)進行搜索處理時將表現(xiàn)出極大的優(yōu)勢。

(編輯：嚴佩峰)