基于抽取規(guī)則和本體映射的語義搜索算法

周詩源, 王英林

(1. 上海財(cái)經(jīng)大學(xué) 信息管理與工程學(xué)院, 上海 200433； 2. 嘉興學(xué)院 計(jì)劃財(cái)務(wù)處, 浙江 嘉興 314001)

目前, 搜索引擎已成為人們獲取信息的主要工具[1-5]. 搜索引擎對網(wǎng)絡(luò)上的信息搜索實(shí)際是一種信息的組織形式, 其通過網(wǎng)絡(luò)爬蟲不斷在網(wǎng)絡(luò)上“爬行”, 對網(wǎng)絡(luò)上的信息進(jìn)行周期性搜索, 然后對搜索信息進(jìn)行標(biāo)記, 建立一個(gè)供用戶按關(guān)鍵詞進(jìn)行搜索的網(wǎng)頁索引數(shù)據(jù)庫[6-9]. 在實(shí)際應(yīng)用中, 由于網(wǎng)頁中的信息組織形式與傳統(tǒng)文本信息組織形式差別較大, 如果采用傳統(tǒng)文本信息的標(biāo)記方式, 則無法準(zhǔn)確描述關(guān)鍵詞間的語義關(guān)系, 搜索效率極低, 且搜索結(jié)果與用戶真正需求相差較遠(yuǎn), 導(dǎo)致面對大量信息用戶卻找不到自己真正需要的信息[10-11]. 這主要是因?yàn)閭鹘y(tǒng)文本搜索算法無法真正理解用戶的需求, 無法實(shí)現(xiàn)用戶內(nèi)容的查詢擴(kuò)展、 語義理解和關(guān)聯(lián)缺失. 而語義網(wǎng)[12-14]可排除一切平臺、 語言的分歧, 其中本體是語義網(wǎng)的核心, 是對知識的共同理解和描述. 目前已有許多基于本體的語義搜索算法, 如采用本體中定義的語匯作為關(guān)鍵標(biāo)記文檔； 利用本體的路徑進(jìn)行用戶查詢的擴(kuò)展, 獲得了較傳統(tǒng)算法更好的搜索結(jié)果. 這些語義搜索算法缺乏統(tǒng)一的語義描述, 計(jì)算機(jī)程序理解的語義與用戶需求之間偏差較大, 導(dǎo)致搜索時(shí)間長, 無法實(shí)現(xiàn)智能搜索[15-17].

針對當(dāng)前語義搜索算法存在的不足, 本文提出一種基于抽取規(guī)則和本體映射的語義搜索算法. 首先根據(jù)用戶搜索要求抽取語義中的元素和屬性, 然后建立計(jì)算機(jī)和用戶之間的語義本體映射, 并將語義搜索算法應(yīng)用于用戶個(gè)性化推薦系統(tǒng). 實(shí)驗(yàn)結(jié)果表明, 本文算法提高了語義的搜索效率, 增強(qiáng)了用戶個(gè)性化推薦系統(tǒng)的性能.

1 算法設(shè)計(jì)

1.1 語義網(wǎng)

語義網(wǎng)是以鏈接為主要形式的信息網(wǎng), 是對萬維網(wǎng)的一種擴(kuò)展, 即增加了語言標(biāo)記, 其中語義是關(guān)鍵部分, 主要用于描述符號及其對應(yīng)對象之間的關(guān)系. 在語義網(wǎng)中, 信息只有具備了語義, 不同應(yīng)用和用戶之間才能實(shí)現(xiàn)互相操作[18].

1.2 本體的定義

在計(jì)算機(jī)科學(xué)領(lǐng)域， 本體定義為一定領(lǐng)域詞匯的基本定義和關(guān)系及其之間的規(guī)則, 其目標(biāo)是捕獲相關(guān)領(lǐng)域的共同知識, 并定義共同認(rèn)可的術(shù)語, 從而實(shí)現(xiàn)對領(lǐng)域知識的推理.

1.3 語義抽取規(guī)則

網(wǎng)頁主要包括類結(jié)構(gòu)、 層次結(jié)構(gòu)、 對象、 數(shù)據(jù)和基數(shù)5個(gè)元素. 網(wǎng)頁關(guān)鍵詞的語義由多個(gè)義原組成, 因此語義抽取時(shí), 要綜合考慮每個(gè)詞的義原集, 對于兩個(gè)關(guān)鍵詞w1和w2, 它們分別包括n個(gè)和m個(gè)義原, 即s11,s12,…,s1n和s21,s22,…,s2n, 則兩個(gè)關(guān)鍵詞w1和w2之間的相似度可描述為

(1)

根據(jù)上下文之間關(guān)系建立樹狀層次體系描述義原, 設(shè)兩個(gè)義原p1與p2在樹中的距離為d, 則其語義距離計(jì)算公式為

(2)

其中a表示可調(diào)節(jié)參數(shù).

對于兩個(gè)關(guān)鍵詞, 若只從語義方面分析, 則它們語義相似度可能很低, 而它們出現(xiàn)在同一網(wǎng)頁的概率非常大, 因此本文還需從關(guān)鍵詞的義原進(jìn)行考慮, 即考慮關(guān)鍵詞之間的相關(guān)性. 對于一組關(guān)鍵詞, 首先得到每個(gè)關(guān)鍵詞的義原集, 并從第一個(gè)關(guān)鍵詞不斷遍歷全部關(guān)鍵詞與義原集, 若找到一個(gè)關(guān)鍵詞與其他關(guān)鍵詞不相同, 如果它們義原集有相同的部分, 則提取它們的共同義原, 并將兩個(gè)關(guān)鍵詞分別放在共同義原后; 但若發(fā)現(xiàn)一個(gè)關(guān)鍵詞在不同行中重復(fù)出現(xiàn), 即將其從重復(fù)的行中刪除, 根據(jù)領(lǐng)域詞典判斷每個(gè)義原是否與主題相關(guān), 不相關(guān)則將其對應(yīng)行刪除, 即完成語義抽取.

1.4 本體映射

圖1 基于內(nèi)容的本體映射流程Fig.1 Ontology mapping process based on content

對于結(jié)構(gòu)和內(nèi)容相似度非常高的兩個(gè)本體, 它們均可用于兩種類型的網(wǎng)頁分類, 但兩個(gè)本體之間存在一定的語義沖突, 若根據(jù)兩對概念可建立本體的語義映射關(guān)系, 則會得到錯(cuò)誤的映射結(jié)果, 因此即使兩個(gè)本體片段的結(jié)構(gòu)和內(nèi)容很相似, 由于語境不同也可能導(dǎo)致本體語義映射的差異性. 在本體映射過程中需考慮概念語義信息, 降低映射誤差. 本文建立本體間語義映射關(guān)系時(shí), 綜合考慮了與語義信息相關(guān)的知識, 這些信息主要包括詞語知識、 領(lǐng)域知識和結(jié)構(gòu)知識.

綜合分析詞語知識、 領(lǐng)域知識和結(jié)構(gòu)知識對本體映射的貢獻(xiàn), 設(shè)計(jì)一種基于內(nèi)容的本體映射方法, 其工作流程如圖1所示. 步驟如下：

1) 輸入兩個(gè)本體模型;

2) 提取兩個(gè)本體的語義信息;

3) 通過邏輯推理的方法建立本體的語義映射關(guān)系.

2 基于語義搜索算法的用戶協(xié)同推薦系統(tǒng)

2.1 相似用戶的發(fā)現(xiàn)

基于語義搜索算法的用戶協(xié)同推薦系統(tǒng)的用戶相似性計(jì)算方法很多. 設(shè)用戶a和b對信息i的評分分別為da,i和db,i, 用戶共同評價(jià)過的信息數(shù)量為|Ia,b|, 用戶a和b評價(jià)過的信息數(shù)目分別為|Ia|和|Ib|, 則基于用戶共同評價(jià)信息的相似性與基于用戶共同評價(jià)過信息數(shù)量的相似性計(jì)算公式分別為

(3)

(4)

Sima,b=CPCa,b×Jaccarda,b.

(5)

2.2 信任用戶的確定

用戶間的信任關(guān)系直接關(guān)系到推薦系統(tǒng)的性能優(yōu)劣, 根據(jù)用戶鄰居推薦是否成功確定用戶之間的信任值. 鄰居b向用戶a推薦成功可描述為：a與b對所推薦資源i評分之間的偏差小于信任閾值ε, 即

|da,i-db,i|×Jaccarda,b<ε.

(6)

根據(jù)式(4)可初步得到用戶間的信任關(guān)系, 則用戶a和b間的信任值計(jì)算公式為

(7)

式(7)未考慮用戶單獨(dú)評價(jià)的信息, 會使極少的信息評價(jià)產(chǎn)生極高的信任值, 這與實(shí)際情況不符, 因此要考慮用戶的單獨(dú)評價(jià)信息, 用戶a和b間的信任值計(jì)算公式變?yōu)椋?/p>

(8)

式(8)表示用戶之間的直接信任關(guān)系, 但實(shí)際還存在一些間接信任關(guān)系的用戶. 用戶a信任用戶b, 用戶b信任用戶c, 即可認(rèn)為用戶a在一定程度上信任用戶c, 而間接信任可能存在多條信任路徑, 在考慮用戶a和c之間的信任路徑數(shù)(adj(a,c))基礎(chǔ)上可得

(9)

其中:d表示兩個(gè)用戶間的距離；βd表示信任的衰減指數(shù)計(jì)算公式：

(10)

綜上可知, 用戶a和b間信任值的最終計(jì)算公式為

(11)

2.3 計(jì)算用戶信任權(quán)重

信任權(quán)值作為用戶信任度的一個(gè)評價(jià)指標(biāo), 有利于發(fā)現(xiàn)更多相似用戶, 改善用戶推薦系統(tǒng)的性能, 信任權(quán)重值計(jì)算主要考慮： 用戶間的信任值Trusta→b、 用戶評價(jià)聲譽(yù)和語義相似性3個(gè)方面. 用戶對某信息評價(jià)比例可間接描述用戶在該信息推薦上的可信程度, 因此用戶對于某信息評價(jià)越多, 表示該用戶越熟悉該信息, 對該信息進(jìn)行推薦, 該用戶的信任權(quán)重值相對越大, 則有

(12)

其中: #Nb(ICL)表示用戶評價(jià)過ICL類信息的數(shù)量; #N(ICL)表示屬于ICL類信息的數(shù)量.

兩個(gè)信息的語義相似性越大, 對于成功向用戶推薦過信息的鄰居, 其推薦該信息的可信度越大. 信息ix和iy的語義相似度與本體圖中的深度(depth(ix),depth(iy))和最近共同祖先(least common ancestor, LCA)的深度相關(guān), 計(jì)算公式為

(13)

為充分考慮語義屬性信息, 引入語義相似性, 此時(shí)用戶信任權(quán)重值的計(jì)算公式為

(14)

根據(jù)信任權(quán)重值TWa→b、 相似用戶的數(shù)量及推薦系統(tǒng)信任閾值ε之間的關(guān)系發(fā)現(xiàn)更多的相似用戶, 從而提高用戶個(gè)性化推薦系統(tǒng)的推薦結(jié)果質(zhì)量.

3 仿真實(shí)驗(yàn)

3.1 數(shù)據(jù)集

為了分析基于抽取規(guī)則和本體映射的語義搜索算法性能, 在4核Intel 3.0 GHz CPU, 8 GB內(nèi)存的計(jì)算機(jī)上, 采用Windows7作為操作系統(tǒng), 選擇JAVA語言進(jìn)行編程, 采用MovieLens數(shù)據(jù)集作為研究對象. 為使實(shí)驗(yàn)結(jié)果更具說服力, 采用文獻(xiàn)[19]和文獻(xiàn)[20]的語義搜索算法進(jìn)行對比分析, 用平均絕對誤差(mean absolute error, MAE)對實(shí)驗(yàn)結(jié)果進(jìn)行評價(jià), 其計(jì)算公式為

(15)

其中:N表示測試樣本集的規(guī)模;pi表示算法的評分值;qi表示實(shí)際評分值.

3.2 結(jié)果與分析

1) 隨機(jī)選取不同規(guī)模的訓(xùn)練樣本和測試樣本, 采用本文語義搜索算法與對比語義搜索算法對數(shù)據(jù)集進(jìn)行求解和分析, 對比結(jié)果如圖2所示. 由圖2可見, 訓(xùn)練樣本的數(shù)量越多, 則MAE的值越小, 表明訓(xùn)練樣本越多, 學(xué)習(xí)結(jié)果越好, 但在相同訓(xùn)練樣本的數(shù)量條件下, 本文語義搜索算法的MAE值最低, 表明本文語義搜索算法有效提高了用戶需要推薦精度, 較好地解決了當(dāng)前語義搜索算法存在的缺陷.

2) 為了分析本文語義搜索算法的通用性, 采用Book-Crossing數(shù)據(jù)集實(shí)現(xiàn)預(yù)測實(shí)驗(yàn), 本文語義搜索算法與對比語義搜索算法的實(shí)驗(yàn)結(jié)果如圖3所示. 由圖3可見, 相對文獻(xiàn)[19]和文獻(xiàn)[20]的語義搜索算法, 本文語義搜索算法的MAE大幅度提升, 有效提高了用戶個(gè)性化推薦精度, 獲得了更理想的用戶個(gè)性化推薦結(jié)果.

圖2 MovieLens數(shù)據(jù)集的推薦結(jié)果對比Fig.2 Comparisons of recommended results of MovieLens dataset

圖3 Book-Crossing數(shù)據(jù)集的推薦結(jié)果對比Fig.3 Comparisons of recommended results of Book-Crossing dataset

綜上所述, 針對傳統(tǒng)信息檢索系統(tǒng)沒有準(zhǔn)確描述語義, 導(dǎo)致檢索結(jié)果與用戶實(shí)際需要結(jié)果相差較大的問題, 為了提高用戶需要檢索的準(zhǔn)確性, 本文設(shè)計(jì)了一種基于抽取規(guī)則和本體映射的語義搜索算法. 首先根據(jù)抽取規(guī)則提取網(wǎng)頁信息中的元素和屬性, 根據(jù)元素和屬性對網(wǎng)頁信息進(jìn)行重新組織; 然后建立計(jì)算機(jī)和用戶語義之間的本體映射, 使計(jì)算機(jī)能真正理解用戶的意圖, 實(shí)現(xiàn)用戶需要的智能化搜索; 最后將語義搜索算法嵌入到用戶個(gè)性化推薦系統(tǒng). 實(shí)驗(yàn)結(jié)果表明, 相比于傳統(tǒng)算法, 本文算法的語義搜索速度更快, 減少了信息映射冗余度, 取得較好的本體映射結(jié)果, 能找到用戶真正需要的信息, 提高了用戶個(gè)性化推薦系統(tǒng)的查詢精度.

[1] Shvaiko P, Euzenat J. Ontology Matching: State of the Art and Future Challenges [J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(1): 158-176.

[2] Kumar S K, Harding J A. Ontology Mapping Using Description Logic and Bridging Axioms [J]. Computers in Industry, 2013, 64(1): 19-28.

[3] HUANG Shengjun, JIN Rong, ZHOU Zhihua. Active Learning by Querying Informative and Representative Examples [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(10): 1936-1949.

[4] 吳建. TRIZ 理論在搜索引擎創(chuàng)新設(shè)計(jì)中的應(yīng)用研究 [J]. 重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版), 2012, 24(6): 735-739. (WU Jian. Application of TRIZ in Search Engine’s Innovative Design [J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2012, 24(6): 735-739.)

[5] 陳治昂, 張毅, 李大學(xué). 基于Web智能的網(wǎng)絡(luò)廣告監(jiān)測器研究與設(shè)計(jì) [J]. 重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版), 2009, 21(1): 115-118. (CHEN Zhi’ang, ZHANG Yi, LI Daxue. Research and Design of Web Adsmonitor Based on Web Intelligence [J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2009, 21(1): 115-118.)

[6] 劉顯敏, 李建中. 基于鍵規(guī)則的XML實(shí)體抽取方法 [J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(1): 64-75. (LIU Xianmin, LI Jianzhong. Key-Based Method for Extracting Entities from XML Data [J]. Journal of Computer Research and Development, 2014, 51(1): 64-75.)

[7] 丁國棟, 白碩, 王斌. 一種基于局部共現(xiàn)的查詢擴(kuò)展研究 [J]. 中文信息學(xué)報(bào), 2013, 20(3): 84-91. (DING Guodong, BAI Shuo, WANG Bin. Local Co-occurrence Based Query Expansion for Information Retrieval [J]. Journal of Chinese Information Processing, 2013, 20(3): 84-91.)

[8] 王璐, 王國春, 桂金花, 等. 本體語義檢索系統(tǒng) [J]. 長春工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版), 2013, 34(6): 726-730. (WANG Lu, WANG Guochun, GUI Jinhua, et al. A Semantic Retrieval System Based on Ontology [J]. Journal of Changchun University of Technology (Natural Science Edition), 2013, 34(6): 726-730.)

[9] 李穎, 李志蜀, 鄧歡. 基于Lucene 的中文分詞方法設(shè)計(jì)與實(shí)現(xiàn) [J]. 四川大學(xué)學(xué)報(bào)(自然科學(xué)版), 2008, 45(5): 1095-1099. (LI Ying, LI Zhishu, DENG Huan. Design and Implementation of Chinese Words Segementation Based on Lucene [J]. Journal of Sichuan University (Natural Science Edition), 2008, 45(5): 1095-1099.)

[10] 張祥, 李星, 溫韻清, 等. 語義網(wǎng)虛擬本體構(gòu)建 [J]. 東南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015, 45(4): 652-656. (ZHANG Xiang, LI Xing, WEN Yunqing, et al. Virtual Semantic Web Ontology [J]. Journal of Southeast University (Natural Science), 2015, 45(4): 652-656.)

[11] 楊政國, 馬建紅. 基于領(lǐng)域本體科學(xué)效應(yīng)知識語義檢索的研究 [J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用, 2014, 23(2): 209-213. (YANG Zhengguo, MA Jianhong. Based on Scientific Effect Knowledge Domain Ontology Semantic Retrieval [J]. Computer Systems & Applications, 2014, 23(2): 209-213.)

[12] 張凌宇, 姜廷慈, 陳淑鑫. 一種基于參考本體的多本體映射方法 [J]. 四川大學(xué)學(xué)報(bào)(工程科學(xué)版), 2016, 48(5): 114-123. (ZHANG Lingyu, JIANG Tingci, CHEN Shuxin. A Method of Multiple Ontology Mapping Based on Reference Ontology [J]. Journal of Sichuan University (Engineering Science Edition), 2016, 48(5): 114-123.)

[13] 李凱, 李萬龍, 鄭山紅, 等. 改進(jìn)的多策略本體映射方法 [J]. 吉林大學(xué)學(xué)報(bào)(信息科學(xué)版), 2016, 34(4): 536-542. (LI Kai, LI Wanlong, ZHENG Shanhong, et al. Improved Multi-strategy Ontology Mapping Method [J]. Journal of Jilin University (Information Science Edition), 2016, 34(4): 536-542.)

[14] 史致遠(yuǎn), Volker Gruhn, 朱明放. 微學(xué)習(xí)環(huán)境下基于語義的MASHUP架構(gòu)優(yōu)化 [J]. 江蘇大學(xué)學(xué)報(bào)(自然科學(xué)版)， 2010, 31(3)： 339-342. (SHI Zhiyuan, Volker Gruhn, ZHU Mingfang. Optimization of Semantic MASHUP Architecture Applied in Microlearning Enivironment [J]. Journal of Jiangsu University (Natural Science Edition), 2010, 31(3)： 339-342.)

[15] 孫煜飛, 馬良荔, 呂閩暉, 等. 基于改進(jìn)協(xié)同訓(xùn)練的本體映射方法 [J]. 系統(tǒng)工程與電子技術(shù), 2017, 39(2): 459-464. (SUN Yufei, MA Liangli, Lü Minhui, et al. Improved Co-training Based Ontology Matching Method [J]. Systems Engineering and Electronics, 2017, 39(2): 459-464.)

[16] 李華昱, 張培穎, 肖晗. 基于抽取規(guī)則和本體映射的領(lǐng)域XML語義集成 [J]. 河北科技大學(xué)學(xué)報(bào), 2016, 37(4): 416-422. (LI Huayu, ZHANG Peiying, XIAO Han. Domain XML Semantic Integration Based on Extraction Rules and Ontology Mapping [J]. Journal of Hebei University of Science and Technology, 2016, 37(4): 416-422.)

[17] 徐德智, 易曉媛, 湯哲. 基AHP-熵權(quán)決策的本體映射優(yōu)化算法 [J]. 微電子學(xué)與計(jì)算機(jī), 2017, 34(11): 48-52. (XU Dezhi, YI Xiaoyuan, TANG Zhe. An Ontology Mapping Optimization Algorithm Based on AHP and Entropy Weight Decision [J]. Microelectronics & Computer, 2017, 34(11): 48-52.)

[18] 韓彤, 宋文愛. 可信的第三方模糊本體映射框架及其實(shí)現(xiàn) [J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2017, 38(3): 633-639. (HAN Tong, SONG Wen’ai. Trusted Third Party Fuzzy Ontology Mapping Framework and Its Implementation [J]. Computer Engineering and Design, 2017, 38(3): 633-639.)

[19] 王旭陽, 尉醒醒. 基于本體的語義檢索方法 [J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2016, 37(9): 2538-2542. (WANG Xuyang, WEI Xingxing. Semantic Retrieval Method Based on Ontology [J]. Computer Engineering and Design, 2016, 37(9): 2538-2542.)

[20] 張建梁, 肖開東, 顧劍峰, 等. 基于P2P的結(jié)構(gòu)化半分布式語義搜索算法 [J]. 計(jì)算機(jī)應(yīng)用與軟件, 2009, 26(4): 188-193. (ZHANG Jianliang, XIAO Kaidong, GU Jianfeng, et al. Semantic Search Algorithm Based on Structured Half-distributed P2P Network [J]. Computer Applications and Software, 2009, 26(4): 188-193.)