軟件工程畢業(yè)設(shè)計(jì)（論文）基于WORDNET的XML文檔語義相似性計(jì)算方法

1、畢業(yè)設(shè)計(jì)（論文）說明書學(xué) 院 軟件學(xué)院 專 業(yè) 軟件工程 年 級(jí) 2007 級(jí) 姓 名 指導(dǎo)教師2011年 6 月 15 日畢業(yè)設(shè)計(jì)（論文）任務(wù)書題目：基于wordnet的xml文檔語義相似性計(jì)算方法學(xué)生姓名 學(xué)院名稱 軟件學(xué)院 專 業(yè) 軟件工程 學(xué) 號(hào) 指導(dǎo)教師 職 稱 教授 講師 一、原始依據(jù)1、工作基礎(chǔ)：近年來，隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)上的信息資源呈不斷的擴(kuò)張趨勢(shì)，無論在數(shù)量還是領(lǐng)域范圍上，都爆炸式增長(zhǎng)。這在豐富網(wǎng)絡(luò)資源的同時(shí)，使得有效信息、知識(shí)的獲取變得更加困難，因此，關(guān)于結(jié)構(gòu)及語義相似性測(cè)量的研究成為數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等領(lǐng)域中的研究熱點(diǎn)之一。事實(shí)上，相似性及其度量方法一直是數(shù)據(jù)

2、挖掘、機(jī)器學(xué)習(xí)等領(lǐng)域中的研究主題之一，也是web數(shù)據(jù)挖掘系統(tǒng)所要解決的關(guān)鍵問題之一。從1996年w3c提出xml工作草案，1997年召開第一次xml會(huì)議開始，到近年來xml、語義網(wǎng)（semantic web）及owl等相關(guān)技術(shù)的研究與發(fā)展，使得面向內(nèi)容的數(shù)據(jù)挖掘等成為可能。在面向內(nèi)容的智能信息處理中，基于結(jié)構(gòu)（如樹、圖）表示模式，計(jì)算結(jié)構(gòu)化數(shù)據(jù)的結(jié)構(gòu)相似性并從中挖掘知識(shí)，在數(shù)據(jù)挖掘及相關(guān)領(lǐng)域得到了廣泛的研究。但數(shù)據(jù)的結(jié)構(gòu)相似性研究并不能解決語義沖突問題，不能從根本上消除網(wǎng)絡(luò)環(huán)境下的信息孤島和實(shí)現(xiàn)信息資源的互聯(lián)互通和資源共享。隨著語義網(wǎng)和本體（ontology）的發(fā)展，這個(gè)問題得到了較好的解決，

3、國內(nèi)外學(xué)者從不同的角度（概念相似度、文檔相似度、半結(jié)構(gòu)文檔相似度）都進(jìn)行了深入研究，而xml作為一種應(yīng)用越來越廣泛的文檔記錄方式，對(duì)xml語義相似度的研究也受到了普遍的關(guān)注和研究。但目前對(duì)基于xml半結(jié)構(gòu)語言計(jì)算語義相似性的研究沒有一套成熟、高效的計(jì)算方法，自然語言與計(jì)算機(jī)語言之間仍然存在一道鴻溝，嚴(yán)重影響了對(duì)互聯(lián)網(wǎng)信息的應(yīng)用效率。2、研究條件：在目前研究成果的基礎(chǔ)上，依托于南開大學(xué)信息學(xué)院數(shù)據(jù)庫與信息系統(tǒng)實(shí)驗(yàn)室。近7年來，該室對(duì)xml結(jié)構(gòu)相似性計(jì)算方法、基于結(jié)構(gòu)相似性計(jì)算的web挖掘方法等進(jìn)行了深入研究，在此基礎(chǔ)上，展開了xml的語義相似性研究。研究平臺(tái)和應(yīng)用環(huán)境為windows 7，軟件開

4、發(fā)工具為visual studio 2008。3、應(yīng)用環(huán)境：通過本方法，結(jié)合適當(dāng)?shù)念I(lǐng)域詞典，可對(duì)用戶需求的信息、知識(shí)進(jìn)行有效匹配，結(jié)合南開大學(xué)的已有項(xiàng)目，研究成果將應(yīng)用于web數(shù)據(jù)挖掘方法與系統(tǒng)；同時(shí)，還可以應(yīng)用于知識(shí)工程、數(shù)字圖書館、各專業(yè)領(lǐng)域的信息檢索、信息過濾、自然語言處理、數(shù)據(jù)集成及語義web等許多方面。4、工作目的：本課題基于由普林斯頓大學(xué)設(shè)計(jì)的認(rèn)知語言學(xué)詞典wordnet，設(shè)計(jì)并實(shí)現(xiàn)一套用于計(jì)算xml基本語義相似性的計(jì)算方法。并以本課題為基礎(chǔ)，為將來在更廣闊范圍的應(yīng)用做準(zhǔn)備。二、參考文獻(xiàn)1lin d. an information-theoretic definition of s

5、imilarityc.in: proceedings of the fifteenth international conference on machine learning. san francisco, ca, usa: morgan kaufmann publishers inc. 1998.296-304.2tversky, a. 1997. features of similarity. j. psychological rev. 84: 327-352.3boanerges, a. m., christian, h. w., satya, s. s., amit, s. i. a

6、nd budak a. 2005. template based semantic similarity for security applications. technical report, lsdis lab, computer science department, university of gerogia, january.4jiang, j. j., david, w. c. 1997. semantic similarity based on corpus statistics and lexical taxonomy. proc. int. conf. research on

7、 computational linguistics. taiwan, pp. 1-15.5peter, f., martin, k, erich j. n. 1991. semantic vs. structural resemblance of classes to appear in special sigmod record issue on semantic issues in multidatabase systems, 20: 4.6goldstone r l, son j y. similarity j. psychological review. 2004, 100: 254

8、-278.7li m, chen x, xin m l, et al. the similarity metricc. in: ieee transactions on information theory. 2003. 863-872.8邱明. 語義相似性度量及其在設(shè)計(jì)管理系統(tǒng)中的應(yīng)用d. 博士，浙江大學(xué)，2006.9bulskov h, knappe r, andreasen t. on measuring similarity for conceptual queryingc. in: proceedings of the 5th international conference on

9、flexible query answering systems. springer-verlag, 2002. 100-111.10宋玲. 語義相似度計(jì)算及其應(yīng)用研究. 博士， 山東大學(xué)，2009.11黃世國，耿國華. 語義相似性測(cè)度方法研究綜述計(jì)算機(jī)應(yīng)用與軟件 2008（25）.12yang, d. and powers, d. m. w. measuring semantic similarity in the taxonomy of wordnet. in proc. twenty-eighth australasian computer science conference( acs

10、c2005), newcastle, australia. crpit, 38. estivill-castro, v., ed. acs. 315-322. 2005.13budanitsky, alexander. lexical semantic relatedness and its application in natural language processing. technical report csrg-390, computer systems research group, university of toronto, august. 1999.14周子力. 基于word

11、net的本體構(gòu)建及其在安全領(lǐng)域應(yīng)用關(guān)鍵技術(shù)研究. 博士，華東師范大學(xué)，2009.15 盛立東. 模式識(shí)別導(dǎo)論m北京:北京郵電大學(xué)出版社，2010.三、設(shè)計(jì)（研究）內(nèi)容和要求研究?jī)?nèi)容：1. 了解xml語義相似性方法；2. 熟悉wordnet的使用方法；3. 基于wordnet實(shí)現(xiàn)基本語義相似性計(jì)算算法；4. 編寫程序?qū)崿F(xiàn)上述算法。主要指標(biāo)與技術(shù)參數(shù)：本課題用于計(jì)算xml文檔的語義相似性，最終實(shí)現(xiàn)的算法有兩個(gè)技術(shù)指標(biāo)，即算法的合理性和算法的效率。（1）算法的合理性指標(biāo)：相似性算法通過計(jì)算給出兩段xml文檔之間的相似度（結(jié)果介于01，其中，值越大說明兩者越相似，取值為1是，兩者完全一樣，取值為零時(shí)，

12、兩者沒有相似性），通過實(shí)驗(yàn)者的主觀判斷和wordnet詞典的詞類劃分判斷結(jié)果是否準(zhǔn)確。（2）算法的效率：算法要求時(shí)間盡可能快，由于算法越精確需要考慮的參數(shù)越多，計(jì)算量越大，因此最終的算法需要在準(zhǔn)確性和效率之間取得平衡。具體要求：基于wordnet實(shí)現(xiàn)基于語義相似性計(jì)算算法。指導(dǎo)教師（簽字）年 月 日審題小組組長(zhǎng)（簽字）年 月 日天津大學(xué)本科生畢業(yè)設(shè)計(jì)（論文）開題報(bào)告課題名稱基于wordnet的xml文檔語義相似性計(jì)算方法學(xué)院名稱軟件學(xué)院專業(yè)名稱軟件工程學(xué)生姓名指導(dǎo)教師一、課題的來源及意義近年來，關(guān)于結(jié)構(gòu)及語義相似性測(cè)量的研究成為數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等領(lǐng)域中的研究熱點(diǎn)之一。這不僅是由于xml（ex

13、tensible markup language）等互聯(lián)網(wǎng)新技術(shù)的不斷發(fā)展對(duì)已有技術(shù)帶來的挑戰(zhàn)，更是因?yàn)殡S著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)上的信息資源呈不斷的擴(kuò)張趨勢(shì)，無論在數(shù)量還是領(lǐng)域范圍上，都爆炸式增長(zhǎng)，人們已經(jīng)不僅僅滿足于以往對(duì)信息的簡(jiǎn)單獲取，對(duì)知識(shí)的需求在不斷擴(kuò)大，以往偏重結(jié)構(gòu)性相似的匹配方法已經(jīng)不能滿足需求，語義相似性測(cè)量逐漸成為關(guān)注的熱點(diǎn)。語義相似性測(cè)量方法已經(jīng)被廣泛的應(yīng)用在了數(shù)據(jù)挖掘和知識(shí)獲取方面以及國防安全、企業(yè)應(yīng)用等領(lǐng)域。從1996年w3c提出xml工作草案，1997年召開第一次xml會(huì)議開始，到近年來xml、語義網(wǎng)（semantic web）及owl等相關(guān)技術(shù)的研究與發(fā)展，使得

14、面向內(nèi)容的數(shù)據(jù)挖掘等成為可能。和文本文檔相比，xml文檔具有“自描述”、“樹形結(jié)構(gòu)”、“結(jié)構(gòu)嵌套”等特點(diǎn)。隨著xml在數(shù)據(jù)挖掘、分類聚類、數(shù)據(jù)交換、內(nèi)容管理、web服務(wù)等方面的廣泛應(yīng)用，如何高效的解決xml語義相似度的測(cè)量方法，成為人們普遍關(guān)注的一個(gè)焦點(diǎn)。wordnet是普林斯頓大學(xué)的心理學(xué)家、語言學(xué)家和計(jì)算機(jī)工程師聯(lián)合設(shè)計(jì)的一種基于認(rèn)知語言學(xué)的詞典。名詞、動(dòng)詞、形容詞和副詞各被組織成一個(gè)同義詞的網(wǎng)絡(luò)，每個(gè)同義詞集合都代表一個(gè)基本的語義概念，并且這些集合之間也由各種關(guān)系連結(jié)。因此我們使用wordnet作為參考，判斷自然語言之間語義的相似性。這也成為大家普遍接受的一種做法。綜上所述，我們使用基于

15、wordnet的語義相似性測(cè)量方法，最終能夠基本辨別不同文檔之間的語義相似性，為數(shù)據(jù)挖掘、知識(shí)獲取、web應(yīng)用等領(lǐng)域提供一種語義相似性測(cè)量的解決方案。二、國內(nèi)外發(fā)展?fàn)顩r目前xml文檔相似度的研究已經(jīng)取得了許多進(jìn)展。由于xml文檔具有“自描述”、“樹形結(jié)構(gòu)”、“結(jié)構(gòu)嵌套”等結(jié)構(gòu)特點(diǎn)，許多研究通過樹的編輯距離來計(jì)算xml文檔之間的相似度，距離和相似度之間成反比例關(guān)系，距離越大，相似度越小；另有一些研究直接比較樹中節(jié)點(diǎn)之間的相似度，先計(jì)算文檔之間相同節(jié)點(diǎn)的個(gè)數(shù)，通過共同節(jié)點(diǎn)和兩個(gè)文檔所有節(jié)點(diǎn)個(gè)數(shù)的比值來衡量文檔之間的相似度。這種方法忽略了xml文檔的結(jié)構(gòu)特點(diǎn)；還有研究基于擁有相似的路徑集合則xml文

16、檔相似的假設(shè)，通過路徑集合的比較計(jì)算xml文檔之間的相似度。這些研究取得了一些成果，但仍有不足，語義和結(jié)構(gòu)相似度不能兼顧。這些年，也有一些研究將節(jié)點(diǎn)本身的相似度納入了考量范圍，文獻(xiàn)10綜合考慮了文檔節(jié)點(diǎn)的語義相似性和結(jié)構(gòu)特點(diǎn)，但研究尚不成熟，均在計(jì)算精度和效率之間難以取舍。三、本課題的研究目標(biāo)和研究?jī)?nèi)容研究目標(biāo)：基于wordnet，實(shí)現(xiàn)xml文檔基本語義相似度計(jì)算算法，為后期語義相似度計(jì)算算法與已有結(jié)構(gòu)相似度計(jì)算算法的結(jié)合做準(zhǔn)備。研究?jī)?nèi)容：1 了解現(xiàn)有xml語義相似性方法；2 掌握wordnet的使用方法；3 基于wordnet實(shí)現(xiàn)基本語義相似性計(jì)算算法；4 編寫程序?qū)崿F(xiàn)上述算法。四、研究方法

17、和研究手段本課題以wordnet為依托，在抽取出xml文檔的節(jié)點(diǎn)之后，通過wordnet的同義詞集合建立各自的同義詞集合，通過計(jì)算兩個(gè)集合中詞對(duì)的語義相似度，即利用wordnet中節(jié)點(diǎn)的位置深度表示節(jié)點(diǎn)語義值，從而構(gòu)建節(jié)點(diǎn)語義相似度矩陣，并將這些相似度值加權(quán)求值后，計(jì)算節(jié)點(diǎn)之間的語義相似度。進(jìn)而通過進(jìn)一步的計(jì)算，考慮文檔之中所有節(jié)點(diǎn)的相似度情況，給出兩個(gè)文檔之間的語義相似度結(jié)果。本課題的開發(fā)語言為c#，應(yīng)用框架為.net，開發(fā)工具為visual studio 2008，研究平臺(tái)為windows 7，在代碼實(shí)現(xiàn)過程將遵循軟件工程的開發(fā)方法，給出合理的實(shí)驗(yàn)數(shù)據(jù)，進(jìn)行充分的實(shí)驗(yàn)驗(yàn)證，保證算法的準(zhǔn)確有

18、效。五、進(jìn)度安排2010-12-202011-1-10 查閱國內(nèi)外研究背景及現(xiàn)狀。2011-1-112011-2-17 對(duì)本課題進(jìn)行調(diào)研學(xué)習(xí)。2011-2-182011-3-10 熟悉編程環(huán)境和相關(guān)語言的開發(fā)技術(shù)。2011-3-112011-4-10 對(duì)課題相關(guān)領(lǐng)域的深入調(diào)研學(xué)習(xí)，算法初步設(shè)計(jì)。2011-4-112011-4-20 算法設(shè)計(jì)和論證。2011-4-212011-5-18 代碼實(shí)現(xiàn)。 2011-5-192011-6-5 測(cè)試、性能評(píng)估及畢業(yè)論文定稿。六、參考文獻(xiàn)1lin d. an information-theoretic definition of similarityc.in

19、: proceedings of the fifteenth international conference on machine learning. san francisco, ca, usa: morgan kaufmann publishers inc. 1998.296-304.2tversky, a. 1997. features of similarity. j. psychological rev. 84: 327-352.3boanerges, a. m., christian, h. w., satya, s. s., amit, s. i. and budak a. 2

20、005. template based semantic similarity for security applications. technical report, lsdis lab, computer science department, university of gerogia, january.4jiang, j. j., david, w. c. 1997. semantic similarity based on corpus statistics and lexical taxonomy. proc. int. conf. research on computationa

21、l linguistics. taiwan, pp. 1-15.5peter, f., martin, k, erich j. n. 1991. semantic vs. structural resemblance of classes to appear in special sigmod record issue on semantic issues in multidatabase systems, 20: 4.6goldstone r l, son j y. similarity j. psychological review. 2004, 100: 254-278.7li m, c

22、hen x, xin m l, et al. the similarity metricc. in: ieee transactions on information theory. 2003. 863-872.8邱明. 語義相似性度量及其在設(shè)計(jì)管理系統(tǒng)中的應(yīng)用d. 博士，浙江大學(xué)，2006.9bulskov h, knappe r, andreasen t. on measuring similarity for conceptual queryingc. in: proceedings of the 5th international conference on flexible quer

23、y answering systems. springer-verlag, 2002. 100-111.10宋玲. 語義相似度計(jì)算及其應(yīng)用研究. 博士， 山東大學(xué)，2009.11黃世國，耿國華. 語義相似性測(cè)度方法研究綜述計(jì)算機(jī)應(yīng)用與軟件 2008（25）.12yang, d. and powers, d. m. w. measuring semantic similarity in the taxonomy of wordnet. in proc. twenty-eighth australasian computer science conference( acsc2005), newca

24、stle, australia. crpit, 38. estivill-castro, v., ed. acs. 315-322. 2005.13周子力. 基于wordnet的本體構(gòu)建及其在安全領(lǐng)域應(yīng)用關(guān)鍵技術(shù)研究. 博士，華東師范大學(xué)，2009.選題是否合適： 是 否課題能否實(shí)現(xiàn)： 能 不能指導(dǎo)教師（簽字）年 月 日選題是否合適： 是 否課題能否實(shí)現(xiàn)： 能 不能審題小組組長(zhǎng)（簽字）年 月 日摘 要隨著xml在數(shù)據(jù)挖掘、分類聚類、數(shù)據(jù)交換、內(nèi)容管理、web服務(wù)等方面的廣泛應(yīng)用，xml文檔的相似性比較成為人們普遍關(guān)注的一個(gè)焦點(diǎn)。而如何有效的解決xml語義相似度的測(cè)量方法，仍然是一個(gè)懸而未決的問

25、題。針對(duì)于這一問題，本文在論述了當(dāng)前主流概念語義相似度比較算法的基礎(chǔ)上，以wordnet為本體給出了一個(gè)更為精確的概念語義相似性比較算法，為該領(lǐng)域，以及其他應(yīng)用領(lǐng)域，包括xml文檔、普通文檔、其它文檔以及信息檢索數(shù)據(jù)挖掘等方面都會(huì)有一定貢獻(xiàn)。在概念語義相似度比較基礎(chǔ)之上本文參照xml文檔的結(jié)構(gòu)特性設(shè)計(jì)了一種xml文檔語義相似性比較算法，該算法以xml文檔的節(jié)點(diǎn)語義相似性為基礎(chǔ)，在經(jīng)過加權(quán)求值，給出文檔整體的語義相似度，經(jīng)試驗(yàn)論證，該算法是可行的。在當(dāng)前xml文檔語義相似性比較研究還沒有大規(guī)模展開的情況下，該算法具有一定的探索意義和使用價(jià)值。關(guān)鍵詞：語義相似度；概念；wordnet；xml；xm

26、l文檔語義相似度abstractwith the use of xml in data mining, classification and clustering, data exchange, content management, web services and so on, how to decide the similarity between xml documents is becoming a common problem. and theres still no answer for where is the effective method to measure the s

27、emantic similarity between xml documents. this paper gives a more accurate way for this problem based on wordnet , the ontology , with the discussing of current mainstream ways of semantic similarity between concepts.based on the semantic similarity between concepts and the structure characteristics

28、 of xml, this paper gives a new algorithm for semantic similarity between xml documents. it count the semantic similarity of xml-elements as units, and weights them, and gives the overall semantic similarity of xml documents. the algorithm has been proved to be feasible. and its a little step forwar

29、d that the study of semantic similarity between xml documents has not been focused yet.key words：semantic similarity；concept；wordnet；xml；semantic similarity between xml documents目 錄第一章 緒論11.1 研究背景11.2 研究現(xiàn)狀21.3 研究意義21.4 主要內(nèi)容和組織結(jié)構(gòu)31.5 本章小結(jié)3第二章 語義相似度研究42.1 本體概述42.2 wordnet簡(jiǎn)介52.3 語義相似性、語義相關(guān)性和語義距離62.4 本章

30、小結(jié)6第三章 基于wordnet的概念語義相似度算法73.1 基于wordnet的語義相似性算法綜述73.1.1 網(wǎng)絡(luò)距離模型73.1.2 信息理論模型93.2 當(dāng)前算法存在的問題93.3 一種新的概念語義相似度計(jì)算方法93.4 算法分析113.5 本章小結(jié)12第四章 基于wordnet的xml語義相似性算法134.1 xml文檔簡(jiǎn)介134.2 基于語義相似性計(jì)算xml文檔的語義相似性134.3 兩種概念相似性測(cè)量方法的選擇154.4 xml文檔語義相似性測(cè)量的其他問題164.5 本章小結(jié)17第五章 基于wordnet的xml語義相似性算法設(shè)計(jì)185.1 需求分析185.2 概要設(shè)計(jì)205.2

31、.1 模塊設(shè)計(jì)205.2.2 界面設(shè)計(jì)215.3 詳細(xì)設(shè)計(jì)225.4 本章小節(jié)25第六章 xml語義相似性比較算法實(shí)現(xiàn)與測(cè)試266.1 編碼實(shí)現(xiàn)與運(yùn)行結(jié)果266.2 測(cè)試306.2.1 測(cè)試計(jì)劃326.2.2 測(cè)試結(jié)果336.3 本章小結(jié)34第七章 總結(jié)與展望357.1 總結(jié)357.2 展望35參考文獻(xiàn)36外文資料中文譯文致謝3天津大學(xué)2011屆本科生畢業(yè)設(shè)計(jì)（論文）第一章 緒論1.1 研究背景近年來，關(guān)于結(jié)構(gòu)及語義相似性測(cè)量的研究成為數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等領(lǐng)域中的研究熱點(diǎn)之一。這不僅是由于xml（extensible markup language）等互聯(lián)網(wǎng)新技術(shù)的不斷發(fā)展對(duì)已有技術(shù)帶來的挑戰(zhàn)

32、，更是因?yàn)殡S著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)上的信息資源呈不斷的擴(kuò)張趨勢(shì)，無論在數(shù)量還是領(lǐng)域范圍上，都爆炸式增長(zhǎng)，人們已經(jīng)不僅僅滿足于以往對(duì)信息的簡(jiǎn)單獲取，對(duì)知識(shí)的需求在不斷擴(kuò)大，以往偏重結(jié)構(gòu)性相似的匹配方法已經(jīng)不能滿足需求，語義相似性測(cè)量逐漸成為關(guān)注的熱點(diǎn)。語義相似性測(cè)量方法被廣泛的應(yīng)用在了數(shù)據(jù)挖掘和知識(shí)獲取方面以及國防安全、企業(yè)應(yīng)用等領(lǐng)域。而隨著使用本體表示相關(guān)應(yīng)用的領(lǐng)域知識(shí)被越來越多的人的認(rèn)同（所謂本體，是一種形式化的，對(duì)共享概念明確而又詳細(xì)的說明1，相關(guān)知識(shí)領(lǐng)域用到的所有詞匯都可以在本體中找到相應(yīng)解釋，這些詞匯也被成為概念。）,數(shù)據(jù)挖掘和知識(shí)獲取的必要步驟之一，如何實(shí)現(xiàn)不同本體之間的信息交

33、換成為一個(gè)不可忽視的問題；換言之，要實(shí)現(xiàn)不同本體間的信息交換，或者想要挖掘出所需知識(shí)，就必須找到與所需概念相似的概念。因此，問題也就被簡(jiǎn)化為如何決定不同系統(tǒng)或者不同領(lǐng)域間或者同一系統(tǒng)同一領(lǐng)域內(nèi)的兩個(gè)概念的語義相似度。研究與應(yīng)用并重，我們將重點(diǎn)放在了如何基于本體測(cè)量xml的語義相似度。從1996年w3c提出xml工作草案，1997年召開第一次xml會(huì)議開始，到近年來xml、語義網(wǎng)（semantic web）及owl等相關(guān)技術(shù)的研究與發(fā)展，使得面向內(nèi)容的數(shù)據(jù)挖掘等成為可能。和文本文檔相比，xml文檔具有“自描述”、“樹形結(jié)構(gòu)”、“結(jié)構(gòu)嵌套”等特點(diǎn)。隨著xml在數(shù)據(jù)挖掘、分類聚類、數(shù)據(jù)交換、內(nèi)容管理

34、、web服務(wù)等方面的廣泛應(yīng)用，如何有效的解決xml語義相似度的測(cè)量方法，成為人們普遍關(guān)注的一個(gè)焦點(diǎn)。有了概念語義相似度的基礎(chǔ)，解決xml語義相似度的測(cè)量問題首先需要選擇一個(gè)適合的通用本體，我們采用wordnet，一種大家普遍接受的通用本體，作為判斷自然語言之間語義的相似性的依據(jù)。wordnet是普林斯頓大學(xué)的心理學(xué)家、語言學(xué)家和計(jì)算機(jī)工程師聯(lián)合設(shè)計(jì)的一種基于認(rèn)知語言學(xué)的詞典。名詞、動(dòng)詞、形容詞和副詞各被組織成一個(gè)同義詞的網(wǎng)絡(luò)，每個(gè)同義詞集合都代表一個(gè)基本的語義概念，并且這些集合之間也由各種關(guān)系連結(jié)。綜上所述，我們以wordnet作為本體，以一種概念語義相似度測(cè)量作為基礎(chǔ)，最終能夠基本辨別不同x

35、ml文檔之間的語義相似性，為數(shù)據(jù)挖掘、知識(shí)獲取、信息交換、web應(yīng)用等領(lǐng)域提供一種xml語義相似性測(cè)量的解決方案。1.2 研究現(xiàn)狀目前xml文檔相似度的研究已經(jīng)取得了許多進(jìn)展。由于xml文檔具有“自描述”、“樹形結(jié)構(gòu)”、“結(jié)構(gòu)嵌套”等結(jié)構(gòu)特點(diǎn)，許多研究通過樹的編輯距離來計(jì)算xml文檔之間的相似度，距離和相似度之間成反比例關(guān)系，距離越大，相似度越小；另有一些研究直接比較樹種節(jié)點(diǎn)之間的相似度，先計(jì)算文檔之間相同節(jié)點(diǎn)的個(gè)數(shù)，通過共同節(jié)點(diǎn)和兩個(gè)文檔所有節(jié)點(diǎn)個(gè)數(shù)的比值來衡量文檔之間的相似度。這種方法忽略了xml文檔的結(jié)構(gòu)特點(diǎn)；還有研究基于擁有相似的路徑集合則xml文檔相似的假設(shè)，通過路徑集合的比較計(jì)算x

36、ml文檔之間的相似度。這些研究取得了一些成果，但仍有不足，均忽略了節(jié)點(diǎn)本身語義的相似性。而在語義相似性測(cè)量方面，當(dāng)前研究的主要焦點(diǎn)仍然是概念相似度測(cè)量，還很少有研究將概念相似度測(cè)量應(yīng)用到xml文檔中來實(shí)現(xiàn)xml文檔的語義相似性比較。這主要是因?yàn)槿绾螌?shí)現(xiàn)概念相似度測(cè)量還不成熟，仍然沒有一個(gè)統(tǒng)一的被大家認(rèn)同的方法來實(shí)現(xiàn)概念相似度測(cè)量，因此，概念相似度測(cè)量仍然是當(dāng)前的研究熱點(diǎn)。而少量的文獻(xiàn)中雖然提到了xml語義相似度測(cè)量，但由于將過多的精力放在了其節(jié)點(diǎn)的語義相似度上，而忽略了文檔本身的結(jié)構(gòu)性。在概念相似度測(cè)量方面，主流的研究方向分為兩種，一種根據(jù)概念之間的距離來決定概念的相似程度，另一種根據(jù)信息學(xué)理

37、論，以兩個(gè)概念共有信息量的多少來決定概念的相似程度。以距離測(cè)量的方法有太多的經(jīng)驗(yàn)判斷，缺少說服力，同時(shí)計(jì)算復(fù)雜度高；信息學(xué)理論有一個(gè)很好的評(píng)價(jià)相似性的方法，即以共有信息量的多少為標(biāo)準(zhǔn)，但卻忽視了概念之間的方向性等信息，比如“貓”和“哺乳動(dòng)物”作比較，反過來“哺乳動(dòng)物”和“貓”作比較，兩者有什么不同呢？顯然，兩者的共有信息量是一樣的。但到底是“貓”和“哺乳動(dòng)物”像，還是“哺乳動(dòng)物”和“貓”像呢？顯然是前者更像一些，這就是方向問題。在xml語義相似性測(cè)量方面，當(dāng)前的主要方法是遍歷每一個(gè)節(jié)點(diǎn)，比較每一個(gè)節(jié)點(diǎn)的語義相似度，計(jì)算出相似節(jié)點(diǎn)的個(gè)數(shù)和總結(jié)點(diǎn)個(gè)數(shù)的比作為xml文檔相似度的依據(jù)，一方面它忽略了文

38、檔本身的結(jié)構(gòu)性，另一方面為每一個(gè)節(jié)點(diǎn)執(zhí)行一遍概念相似度算法復(fù)雜度太高。1.3 研究意義通過本課題的研究，給出了一個(gè)更為精確的概念語義相似性比較算法，為該領(lǐng)域，以及其他應(yīng)用領(lǐng)域包括xml文檔、普通文檔、其它文檔以及信息檢索數(shù)據(jù)挖掘等方面都會(huì)有一定貢獻(xiàn)；同時(shí)在該算法的基礎(chǔ)之上給出了一種xml文檔語義相似性比較算法，在當(dāng)前xml文檔語義相似性比較研究還沒有大規(guī)模展開的情況下，具有一定的探索意義和使用價(jià)值。1.4 主要內(nèi)容和組織結(jié)構(gòu)本文的第一部分緒論主要闡述了課題的必要性和意義；第二部分簡(jiǎn)要敘述了語義相似性研究的基本知識(shí)，并對(duì)后文將要用到的工具wordnet進(jìn)行了介紹；第三部分在已有算法的基礎(chǔ)上給出了

39、一種更加精確的概念語義相似性比較算法；第四部分結(jié)合概念語義相似性比較算法給出了一種xml文檔語義相似性比較算法；第五部分論述了xml文檔語義相似性比較算法的實(shí)現(xiàn)過程；第六部分對(duì)本文進(jìn)行了總結(jié)并對(duì)將來的發(fā)展方向進(jìn)行了論述。1.5 本章小結(jié)本章主要對(duì)課題開展的背景、必要性和意義進(jìn)行了論述；并敘述了本文的結(jié)構(gòu)安排。第二章 語義相似度研究2.1 本體概述“本體（ontology）”一詞源于哲學(xué)領(lǐng)域，在古希臘羅馬哲學(xué)中，本體論主要研究的是對(duì)世界本源或基本構(gòu)成的探究，根據(jù)webster詞典的定義，本體是關(guān)于存在的物體的本質(zhì)或者各種存在的物體的本質(zhì)的規(guī)范定義。然而，計(jì)算機(jī)領(lǐng)域?qū)Α氨倔w”賦予了新的定義，進(jìn)而被

40、引進(jìn)信息科學(xué)領(lǐng)域。在信息科學(xué)領(lǐng)域，本體的定義是一直發(fā)展著的，目前對(duì)于本體的統(tǒng)一定義是“本體是一種形式化的，對(duì)共享概念明確而又規(guī)范的說明”。在信息科學(xué)領(lǐng)域，本體被作為所研究領(lǐng)域的一種語義基礎(chǔ)，即在本體中可以找到領(lǐng)域中每一個(gè)詞匯的語義（這里的領(lǐng)域值特定的范圍，比如化學(xué)領(lǐng)域、餐飲領(lǐng)域或者語言學(xué)領(lǐng)域、人工智能、信息提取等等）。本體的基本元素是概念，概念的表現(xiàn)形式為詞匯，即一個(gè)詞匯可以有多個(gè)語義，可以表達(dá)多個(gè)概念，而同一個(gè)概念也可以被多個(gè)詞匯表達(dá)。因此，表達(dá)同一概念的詞匯構(gòu)成類。類和概念之間加入適當(dāng)?shù)年P(guān)系，使各個(gè)獨(dú)立的概念和類相連，也就構(gòu)成了一個(gè)本體。這些關(guān)系可以被簡(jiǎn)單分為父子關(guān)系、部分整體關(guān)系、同義詞

41、關(guān)系等。有很多方法被用來表示一個(gè)本體，方法的選擇取決于研究領(lǐng)域?qū)Ρ倔w的不同需求，也就是對(duì)概念密度和概念間關(guān)系的組織強(qiáng)度的需求。同一領(lǐng)域，本體a通過100個(gè)概念來描述，而本體b通過10000個(gè)概念描述，顯然本體b的概念密度更大，描述更精確，同時(shí)，概念間的關(guān)系是多種多樣的，本體a可能只考慮了父子關(guān)系，而本體b考慮了所有關(guān)系。在具體應(yīng)用中，一個(gè)領(lǐng)域的知識(shí)庫，一個(gè)詞典，一個(gè)語義網(wǎng)都可以被用來當(dāng)作一個(gè)本體。目前最流行的一種本體組織方式是將本體組織成樹狀結(jié)構(gòu)的，每一個(gè)概念均被表示為樹形結(jié)構(gòu)中的一個(gè)節(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)都有它的父親節(jié)點(diǎn)、兄弟節(jié)點(diǎn)和子節(jié)點(diǎn)。父親節(jié)點(diǎn)是當(dāng)前節(jié)點(diǎn)所表示概念的上一級(jí)概念，比如“狗”的上一

42、級(jí)概念可能為“哺乳動(dòng)物”；兄弟節(jié)點(diǎn)是父親節(jié)點(diǎn)相同的節(jié)點(diǎn)，比如“哺乳動(dòng)物”的子節(jié)點(diǎn)可能有“狗”、“貓”、“猩猩”等等，那么“狗”的兄弟節(jié)點(diǎn)即為“貓”和“猩猩”；子節(jié)點(diǎn)為當(dāng)前概念的下一級(jí)概念，比如“狗”的下一級(jí)概念可以為“獵犬”、“牧羊犬”等等。wordnet就是這樣一種組織方式。本體有許多分類方式，一種常用的方式是根據(jù)內(nèi)容分為三類：領(lǐng)域本體：本體內(nèi)容適用于特定學(xué)科領(lǐng)域；通用本體：本體內(nèi)容包含具有普遍意義的客觀世界的常識(shí)；任務(wù)本體：本體本身為用于解決特定任務(wù)的術(shù)語集合。wordnet屬于目前常用的一種通用本體。綜上所述，我們對(duì)于本體的選擇，一方面取決于對(duì)概念密度和概念間關(guān)系的組織強(qiáng)度的需求，另一方

43、面需要參考我們使用本體的目的，所研究問題的特點(diǎn)。2.2 wordnet簡(jiǎn)介wordnet是由普林斯頓大學(xué)的george a. miller組織開發(fā)的大型英語詞典。其描述的對(duì)象包括compound（復(fù)合詞）、phrasal verb（短語動(dòng)詞）、collocation（搭配詞）、idiomatic phrase（成語）、word（單詞），其中單詞是最基本的單位。這些描述對(duì)象被分為名詞、動(dòng)詞、形容詞和副詞，它們各自被組織成一個(gè)同義詞的網(wǎng)絡(luò)，即上文中提到的樹形結(jié)構(gòu)，每個(gè)同義詞集合都代表一個(gè)基本的語義概念，并且這些集合之間也有各種關(guān)系連結(jié)。wordnet的名詞部分是目前被開發(fā)的最完整的部分，名詞的連接

44、關(guān)系就占了所有連接關(guān)系的80%。我們以名詞為例，說明wordnet的組織方式。wordnet中最基礎(chǔ)的語義關(guān)系是synonymy（同義關(guān)系）。synset（同義詞集合）構(gòu)成了樹形結(jié)構(gòu)中的每個(gè)節(jié)點(diǎn)，也即一個(gè)概念。在名詞樹形結(jié)構(gòu)的最頂層是11個(gè)基本類，比如“entity”、“event”等等。這11個(gè)基本類的下一層為25個(gè)基本類別：act,activity動(dòng)作行為，food食物，possession所有物，animal,faunal動(dòng)物；group,grouping團(tuán)體，process過程，artifact人工產(chǎn)物，location位置；quantity,amout數(shù)量，attribute屬性，m

45、otivation,motive動(dòng)機(jī)，relation關(guān)系；body身體，natural_object自然物體，shape形狀，cognition,knowledge認(rèn)知，知識(shí)；natural_phenomenon自然現(xiàn)象，state狀態(tài)，communication交流，person,human_being人類，substance物質(zhì)，event,happening事件，plant,flora植物，time時(shí)間，feeling,emotion情感。簡(jiǎn)而言之，同義詞構(gòu)成同義詞集合，同義詞集合構(gòu)成類，不同類又構(gòu)成更上層的類。除了上文中提到的同義詞關(guān)系，wordnet中還有許多其他關(guān)系來表示不同概念

46、間的關(guān)系。上下位關(guān)系：如果同義詞集合a的所有特征被包含在同義詞集合b的特征集中，而不是相反，那么b是a的下位概念（hyponym），反過來，a是b的上位概念（hypernym）。以“動(dòng)物”和“狗”為例，“狗”包含了“動(dòng)物”的所有特征，但“動(dòng)物”并不具備“狗”的獨(dú)有特征“狗拿耗子多管閑事兒”，因此“狗”是“動(dòng)物”的子類，即下位關(guān)系，而“動(dòng)物”是“狗”的父類，上位關(guān)系。整體部分關(guān)系（meronymy）：在wordnet中，包含了三種整體部分關(guān)系，a是b的組成部分；a是b的成員；a是b的構(gòu)成材料。反義關(guān)系（antonymy）：兩個(gè)詞構(gòu)成反義關(guān)系的最強(qiáng)烈的心理學(xué)暗示是，當(dāng)給出一個(gè)詞時(shí)，它的反義詞通常就

47、是最容易聯(lián)想到的詞，比如給出“美麗”這個(gè)詞時(shí)，最容易聯(lián)想到的是“丑陋”。wordnet作為一個(gè)主要的通用本體，每一個(gè)詞的定義都經(jīng)過專家論證，可以為我們常見的英文詞匯提供可靠的基本解釋；其完善的樹形組織結(jié)構(gòu)利于語義的相似度比較，在現(xiàn)階段的語義相似度研究中被廣泛使用，本文也將使用wordnet作為本體。2.3 語義相似性、語義相關(guān)性和語義距離有了確定的本體，尤其是有了樹形結(jié)構(gòu)的本體，在本體內(nèi)測(cè)量?jī)蓚€(gè)概念的相似度也就有了一種非常直觀的方法測(cè)量?jī)烧叩木嚯x，距離越近越相似，反之相似度越低。但在這之前，我們還要討論一下什么是語義相似性、語義相關(guān)性和語義距離，這三個(gè)詞總是同時(shí)出現(xiàn)，甚至被經(jīng)?；煊?，然而，它們

48、的意義并非完全一樣，這里我們舉例來說明。通過“柳條”這個(gè)詞，我們很容易聯(lián)想到“柳葉”，但“柳條”和“柳葉”相似嗎？不相似，但“柳葉”是“柳條”的一部分，它們是相關(guān)的；那么什么和“柳條”相似呢？“繩子”、“電線”甚至“蛇”都可以。因此相似和相關(guān)是不同的。進(jìn)一步的講，我們可以將相似歸類為相關(guān)，但反之卻不能，因此，相關(guān)性是相較于相似性更廣泛的定義。語義距離，簡(jiǎn)而言之就是兩個(gè)概念的語義相距的距離。這是一個(gè)抽象的概念，但許多文獻(xiàn)支持這樣一種觀點(diǎn)：語義距離可以用來表示概念相似性的反面，即距離越大，則相似性越??；同時(shí)，語義距離也可以用來表示相關(guān)性的反面，距離越大，則相關(guān)性越小。 通過語義距離測(cè)量相似性一種直

49、觀方法是網(wǎng)絡(luò)距離模型，即以本體所在樹形結(jié)構(gòu)中兩個(gè)概念的距離為基本指標(biāo)來衡量概念的相似程度；另一種測(cè)量方法是信息理論模型，即通過兩個(gè)概念的共有信息量來衡量概念的相似程度。后者顯得更有說服性，因?yàn)榍罢咦屓寺?lián)想到相關(guān)性，而不是相似性。上文我們已經(jīng)舉例說明，兩者相關(guān)并不一定說明兩者相似。2.4 本章小結(jié)作為目前語義測(cè)量的一種公認(rèn)方法，本體成為了一個(gè)不可或缺的基礎(chǔ)，因此在本章的第一部分我們簡(jiǎn)單介紹了什么是本體，本體的組成以及表示方法，本體的分類。旨在說明為什么用本體可以測(cè)量語義的相似性，如何構(gòu)建本體，如何選擇本體等。在第二部分，本文介紹了一種通用本體wordnet，簡(jiǎn)單描述了它的內(nèi)容、結(jié)構(gòu)特點(diǎn)，說明了它

50、作為通用本體的普適性，可操作性。當(dāng)然，它也有局限性，即本身是一本英文詞典，并不適用于中文或者其他語言。第三部分本文著重區(qū)分了語義相似性、語義相關(guān)性和語義距離三個(gè)概念之間的區(qū)別，旨在為后文語義相似性方法的測(cè)量做鋪墊，以免讀者對(duì)這三個(gè)概念混淆，影響對(duì)下文內(nèi)容的理解。第三章 基于wordnet的概念語義相似度算法3.1 基于wordnet的語義相似性算法綜述如上文所述，目前基于wordnet的語義相似性算法總體上分為兩類，一種直觀方法是網(wǎng)絡(luò)距離模型，即以本體所在樹形結(jié)構(gòu)中兩個(gè)概念的距離為基本指標(biāo)來衡量概念的相似程度；另一種測(cè)量方法是信息理論模型，即通過兩個(gè)概念的共有信息量來衡量概念的相似程度。我們將

51、分別闡述兩種方法的優(yōu)缺點(diǎn)。3.1.1 網(wǎng)絡(luò)距離模型由于wordnet本身的樹形結(jié)構(gòu)以及語義距離和語義相似度之間的關(guān)系，使得計(jì)算兩個(gè)概念之間的相似度有一種非常直觀的方法，即測(cè)量表示兩個(gè)概念的節(jié)點(diǎn)在樹種的距離節(jié)點(diǎn)a到b的最短路徑。路徑越短，a和b越相似。然而，這種測(cè)量方法存在一個(gè)問題，在計(jì)算最短路徑的過程中每一條邊得權(quán)重都是相同，都為1，這與實(shí)際情況是不相符的。一個(gè)簡(jiǎn)單的例子是，在wordnet中“dog”（狗）和“canine”（犬類）之間的距離是1，“canine”（犬類）和“tooth”（牙齒）之間的距離是1，很明顯，前者的相似度高一些。這是因?yàn)椤癲og”處于樹形結(jié)構(gòu)的更底層，而tooth處

52、于樹形結(jié)構(gòu)的更高層，在距離相同的情況下，樹形結(jié)構(gòu)的越高層，概念越抽象，之間的差異越大，反之，樹形結(jié)構(gòu)的越底層，概念越具體，之間的差異越小。因此，我們應(yīng)該對(duì)不同的邊賦予不同的權(quán)值。為了解決這個(gè)問題，有人嘗試給不同的邊賦予權(quán)值，然而，手工賦值的辦法顯然是不可取的，應(yīng)為大型本體中的概念實(shí)在太多，完成這一工程，無異于再建一座萬里長(zhǎng)城。那么能夠自動(dòng)賦值嗎？有許多關(guān)于這方面的工作，大家主要考慮了一下因素：深度、邊密度，節(jié)點(diǎn)之間的連接強(qiáng)度。所謂深度，就是節(jié)點(diǎn)在樹中的深度；從圖3-1我們可以看到，節(jié)點(diǎn)b所在區(qū)域邊的個(gè)數(shù)大于節(jié)點(diǎn)c所在區(qū)圖3-1 樹形節(jié)點(diǎn)圖域邊的個(gè)數(shù)，即區(qū)域密度b大于區(qū)域密度c，則對(duì)應(yīng)的bd邊的

53、權(quán)值應(yīng)當(dāng)小于cf邊的權(quán)值。父子節(jié)點(diǎn)之間的連接強(qiáng)度是基于這樣一種認(rèn)識(shí)，與一個(gè)節(jié)點(diǎn)相連的節(jié)點(diǎn)可能有許多個(gè)，它們根據(jù)不同的連接關(guān)系被連接在一起，這種連接關(guān)系越多，兩個(gè)節(jié)點(diǎn)之間的連接越不穩(wěn)定，因此對(duì)應(yīng)邊的權(quán)值變大，連接強(qiáng)度變小。簡(jiǎn)而言之，隨著深度的加深，權(quán)值隨之變小，概念間的距離變??；隨著邊的區(qū)域密度的增大，權(quán)值變小，概念間距離變小；隨著父子節(jié)點(diǎn)連接強(qiáng)度的增大，權(quán)值變小，概念間距離變小。下面介紹了幾種改進(jìn)了的邊距離測(cè)量方法。其中一種最簡(jiǎn)單的改進(jìn)是找到概念c1和c2最短路徑，并計(jì)算出c1,c2所在層級(jí)結(jié)構(gòu)的最大深度，并且只考慮上位關(guān)系即is-a關(guān)系，得到相似度計(jì)算公式： (3-1)下面的方法給出了一種計(jì)

54、算語義距離的方法，我們知道，語義距離越大，相似度越小，因此，只需要適當(dāng)變形就可以得到一種新的相似度計(jì)算方法： (3-2) (3-3)其中為到之間邊的權(quán)重，r表示語義關(guān)系（is-a關(guān)系），r是r的反關(guān)系，maxr和minr分別表示語義關(guān)系r的可能的最大和最小權(quán)重，表示的語義關(guān)系類型為r的出度。（由于wordnet中的語義關(guān)系有許多種，這在上文中有所描述，這里只計(jì)算某種特定的語義關(guān)系，比如is-a關(guān)系）。另外一種計(jì)算概念相似度的公式考慮了c1和c2最近公共祖先c3在層級(jí)結(jié)構(gòu)中的深度： (3-4)這里的n1是c1到c3的距離，n2是c2到c3的距離，n3是c3到根節(jié)點(diǎn)的距離。由公式4計(jì)算出的結(jié)果是無

55、法預(yù)知其取值范圍的，因此，有人提出了一種將取之范圍規(guī)約到0,1的方法，這種方法也同時(shí)考慮了最短路徑和公共祖先： (3-5)3.1.2 信息理論模型信息理論模型是一種本體和語料庫結(jié)合的方法。它的依據(jù)是，當(dāng)兩個(gè)概念之間的共享信息越多，兩個(gè)概念越相似。那么，如何判定兩個(gè)概念的共享信息量呢？首先，我們可以根據(jù)本體找到概念c1和c2的公共祖先c3，即它們的共有信息為c3，c3占它們所有信息量的比重是多少呢，如何量化它？這里就用到了語料庫，我們通過計(jì)算c3在語料庫中出現(xiàn)的概率p(c3)來衡量共有信息c3的數(shù)量，這樣給出一種計(jì)算相似度的方法： (3-6)這里我們只考慮了共有信息量，有人提出忽略差異信息量是不可取的，因?yàn)榧词筩1和c2的共有信息量很多，但也許它們的差異信息量更多，下面給出了一種考慮了差異信息量的計(jì)算方法，共享信息量越多，越相似，差異信息量越多，越不相似： (3-7)3.2 當(dāng)前算法存在的問題在網(wǎng)絡(luò)距離模型中，更多的考慮了is-