董光芹, 夏文秀

(東北大學(xué) 圖書館, 沈陽 110819)

Top-k查詢(k項最大值)算法[1]與其他信息識別技術(shù)的差異是其不需要通過鍵盤輸入信息數(shù)據(jù), 而是采用Top-k查詢算法設(shè)備輸入, 該算法具有信息采集速度快、可靠性高等優(yōu)點[2-3].圖書自整合信息檢索是圖書館的一項基本工作, 如何能更方便快速地對圖書館中海量圖書進(jìn)行自整合信息識別是該領(lǐng)域的主要任務(wù).目前, 圖書自整合信息快速檢索方法已有許多研究成果.文獻(xiàn)[4]提出了一種基于模糊聚類與模糊模式識別(STAR)的方法, 該方法對圖書信息進(jìn)行檢索時, 對圖書借閱用戶的信息素質(zhì)和借閱圖書的資源信息檢索情況進(jìn)行聚類分析, 確定圖書信息的最佳分類閾值, 實現(xiàn)對圖書信息的快速檢索, 但該方法存在用戶信息不準(zhǔn)確、圖書資源檢索種類繁多的問題, 導(dǎo)致獲取信息不精確, 檢索結(jié)果有誤差.文獻(xiàn)[5]提出了一種基于特征聚類的信息檢索方法, 該方法首先對圖書信息進(jìn)行降維處理, 保留圖書信息的關(guān)鍵詞特征, 同時去除冗余文本帶來的影響, 然后按照圖書信息關(guān)鍵詞特征相似程度將圖書信息特征進(jìn)行聚類, 確定圖書信息檢索的目標(biāo)函數(shù), 采取約束條件對其進(jìn)行約束, 最后調(diào)整圖書信息關(guān)鍵詞特征的聚類中心和權(quán)值, 實現(xiàn)對圖書信息的檢索, 但該方法工作量較大, 耗時較長, 且未考慮對自整合信息的管理.

基于上述問題, 本文提出一種基于Top-k查詢算法的圖書自整合信息快速檢索方法.仿真實驗結(jié)果表明, 該方法具有檢索速率快、檢索自整合信息準(zhǔn)確等優(yōu)點.

1 改進(jìn)圖書自整合信息快速檢索方法設(shè)計

為更精確完成圖書自整合信息的快速檢索, 本文采用小波分解方法對自整合信息進(jìn)行去噪[6].對去噪后的自整合信息進(jìn)行檢索前的預(yù)處理, 最終實現(xiàn)基于Top-k查詢算法的圖書自整合信息檢索.

1.1 自整合信息的去噪 本文采用小波去噪的方法對自整合信息進(jìn)行去噪處理, 小波去噪方法通?？蓪⒁痪S信號的模型表示為S(i)=f(i)+e(i), 其中:S(i)為含噪聲的自整合信息；f(i)為真實信息；e(i)為噪聲.通常真實的信息為低頻信號, 而噪聲為高頻信號.對于圖書變形數(shù)據(jù), 變形表現(xiàn)為低頻平穩(wěn)的變化, 數(shù)據(jù)中的觀測誤差即為噪聲, 具有高頻特征, 所以可利用小波去噪的原理去除噪聲.小波去噪有很多方法： 小波分解與重構(gòu)法、非線性小波變換閾值法、平移不變量法、小波變換模極大值法等.本文采用小波分解與重構(gòu)法, 步驟如下：

1) 一維信號的小波分解, 先根據(jù)數(shù)據(jù)的平滑需要和噪聲模型的適應(yīng)性確定分解所用的小波函數(shù), 本文采用db6函數(shù), 然后確定分解的層數(shù)N, 按要求對變形信號進(jìn)行分解, 如圖1所示;

圖1 自整合信息的小波N層分解Fig.1 Wavelet N layer decomposition of self-integrated information

2) 小波分解后, 將高頻部分進(jìn)行閾值量化處理；

3) 一維小波重構(gòu), 小波分解到第N層后的低頻部分和已經(jīng)閾值處理后的高頻部分進(jìn)行重構(gòu), 得到去噪后的變形信息.

采用小波去噪方法時, 通常選用MATLAB工具箱對信息進(jìn)行處理, 通過wave工具, 將需處理的數(shù)據(jù)轉(zhuǎn)變?yōu)樾畔⑦x擇對應(yīng)的參數(shù), 并對轉(zhuǎn)變后的參數(shù)進(jìn)行適當(dāng)調(diào)整, 最終完成信息的去噪處理, 從而得到去噪后的信息.通過上述步驟完成圖書自整合信息的去噪, 消除無效數(shù)據(jù)在檢索過程中的干擾.

1.2 基于Top-k查詢算法的圖書自整合信息檢索 Top-k查詢算法是一種最常用的查詢方法, 通過Top-k查詢算法對數(shù)據(jù)集合中的記錄進(jìn)行檢索時, 用戶可設(shè)定不同屬性的權(quán)值反映其自身偏好, 而系統(tǒng)則根據(jù)用戶提交的權(quán)值估計, 并根據(jù)估算后的權(quán)值進(jìn)行匹配, 返回符合該用戶需求的前k個結(jié)果.Top-k查詢能幫助用戶從大量數(shù)據(jù)中得到所需信息, 不需查詢所有記錄即可獲取檢索結(jié)果, 檢索效率較高.本文利用Top-k查詢算法對獲取的圖書自整合信息區(qū)域進(jìn)行可信度分配, 并對詞意進(jìn)行度量, 最終完成圖書自整合信息快速檢索.

自整合信息檢索是指從大量信息中搜尋到所需自整合信息的過程.常用的自整合信息檢索模型有Boole模型、空間向量模型、幾率模型和文字模型等.本文方法模型以Top-k查詢算法為基礎(chǔ)對圖書進(jìn)行自整合信息檢索.假設(shè)圖書自整合信息Top-k查詢算法框架為Θ={相似,不相似,無法確定}, 圖書自整合信息快速檢索模型可描述為如下基本可信度分配：

(1)

其中RSV(q,d)表示對應(yīng)的檢索方法中相似度計算結(jié)果[7].在該模型中, Bel(相似)=m(相似)=RSV(q,d),pl(相似)=1-Bel(不相似)=1-m(不相似).

圖書自整合信息的詞意特性和無法確定詞意按下述可信度分配：

(2)

其中：qP和dP分別為圖書自整合信息q和d中的肯定因素；qN和dN為否定因素.基于當(dāng)前的檢索模型, 令詞意相似的計算為匹配, 詞意不相似的計算為不匹配, 得

Bel(相似)=RSV(qP,dP)+RSV(qN,dN).

(3)

結(jié)合相關(guān)先驗知識對當(dāng)前檢索模型和無法確定的詞意進(jìn)行結(jié)合：

(4)

在實際計算中簡化為

其中: RSV函數(shù)為檢索模型的相似度計算方法；l為否定詞意的對立系數(shù);m為詞意特性系數(shù).

用關(guān)于計算事件發(fā)生幾率的Markov鏈方法對詞意進(jìn)行度量其在圖書自整合信息內(nèi)的重要性[8-9].采用當(dāng)前的原始狀態(tài)幾率值和狀態(tài)變更幾率矩陣, 驗證事件的未來情況, 步驟如下.

1) 確定原始狀態(tài)幾率向量H0： 即在檢索過程中確定圖書自整合信息內(nèi)各詞意的原始幾率, 公式為

(7)

其中M為圖書自整合信息內(nèi)所有不相同的詞數(shù).

2) 計算狀態(tài)變更幾率的矩陣： 按照創(chuàng)建的詞圖可得出圖書自整合信息內(nèi)詞同時出現(xiàn)的矩陣, 再根據(jù)矩陣得到各詞間的幾率變更矩陣Pi×j(i,j=0,1,…,H-1), 計算公式為

(8)

其中ni,j表示兩個詞意在圖書自整合信息中同時出現(xiàn)的次數(shù).考慮到詞意在同部位共同出現(xiàn)次數(shù)的關(guān)系[10-13], 運用形式類似PageRank算法中混入阻尼因子的方法, 將式(8)改為

(9)

其中y表示阻尼因子, 初始值取0.18.

3) 計算變更結(jié)果： 根據(jù)Markov鏈的特征, 當(dāng)幾率變更矩陣P經(jīng)過q步幾率變更為正規(guī)幾率矩陣U, 代入模型Bk=B0U中, 得到Bk約束.由式(9)可見, 本文方法采用的幾率變更矩陣P已是正規(guī)幾率矩陣.

4) 確定詞的TI： 約束得到狀態(tài)幾率向量B中的幾率被用于計算詞意在圖書自整合信息中的重要性TI, 公式為

TI(ti,d)=BiH,

(10)

其中:i為圖書自整合信息t中詞意的下標(biāo)；Bi為約束后向量B中第i個詞意對應(yīng)的幾率.

基于上述步驟完成基于Top-k查詢算法的圖書自整合自整合信息快速檢索方法.

2 實驗結(jié)果與分析

實驗平臺為Windows10系統(tǒng), CPU 2.6 GHz主頻, 8 GB內(nèi)存, 利用ImageMatch軟件進(jìn)行仿真實驗.實驗選取某高校圖書館中的856本圖書作為實驗對象, 對圖書自整合信息進(jìn)行預(yù)處理后, 完成詞意匹配, 最終實現(xiàn)對圖書自整合信息的快速檢索.仿真實驗采用文獻(xiàn)[4]和文獻(xiàn)[5]方法作為對比方法, 以檢索所需的時間和準(zhǔn)確率作為評價指標(biāo).

2.1 檢索效果分析 在真實環(huán)境下通過所需時間和準(zhǔn)確率可體現(xiàn)不同方法的檢索性能, 圖書信息檢索數(shù)量和圖書信息數(shù)量的擬合結(jié)果表示檢索準(zhǔn)確率, 計算方法如下:

圖2 不同方法的準(zhǔn)確率對比Fig.2 Comparison of accuracy of different methods

其中G0(j)為圖書信息總數(shù)量.基于評價指標(biāo)值的檢索結(jié)果對比如圖2所示.由圖2可見, 文獻(xiàn)[5]方法的檢索效果最差, 本文方法的平均準(zhǔn)確率為88%, 文獻(xiàn)[4]和文獻(xiàn)[5]方法的平均準(zhǔn)確率分別為58%和55%.與這兩種方法相比, 本文方法的檢索效果較好.由于文獻(xiàn)[4]方法主要偏于圖的檢索, 運用隨機(jī)計算的方式, 從而導(dǎo)致檢索效果不準(zhǔn)確的情況.而本文方法考慮了詞意關(guān)系的強弱和時態(tài)詞意, 因此檢索效果比對比方法更好.

2.2 檢索效率分析 分別對3種方法的圖書自整合信息檢索效率進(jìn)行對比, 對比結(jié)果如圖3所示.由圖3可見, 隨著圖書自整合信息數(shù)量的增加, 3種方法所用時間都呈增加趨勢, 文獻(xiàn)[5]方法所用時間最多, 其次是文獻(xiàn)[4]方法, 本文方法所用時間相對較短, 表明本文方法提高了檢索效率.

根據(jù)本文方法進(jìn)行拓展實驗, 從實驗對象中選取不同的圖書自整合信息數(shù)量, 計算各組檢索自整合信息時間的平均值.圖4是3種方法的響應(yīng)時間.在不同的圖書自整合信息數(shù)量下, 3組效率排序為: 文獻(xiàn)[5]方法<文獻(xiàn)[4]方法<本文方法, 由計算可得本文方法的檢索效率提高了120.49 ms.由圖4可見, 隨著關(guān)鍵詞數(shù)量的增加, 3種方法的時間都有增加, 文獻(xiàn)[5]方法時間增加最多, 本文方法增加的時間最少, 這是由于本文方法添加了對時間的限制, 所以增加的時間少于文獻(xiàn)[4]和文獻(xiàn)[5]方法, 提高了檢索效率.

圖3 不同圖書自整合信息數(shù)量對檢索效率的影響Fig.3 Influence of self-integrated information quantity of different books on retrieval efficiency

圖4 Top-k檢索時間Fig.4 Retrieval time of Top-k

綜上所述, 針對采用當(dāng)前檢索方法進(jìn)行圖書自整合信息檢索時, 難以保證自整合信息檢索結(jié)果的質(zhì)量和效率, 存在圖書自整合信息檢索準(zhǔn)確率和效率較低的問題, 本文提出了一種基于Top-k查詢算法的圖書自整合信息檢索方法.仿真實驗結(jié)果表明, 本文方法不僅能準(zhǔn)確檢索出圖書自整合信息, 且檢索效率更高.