西華大學碩士學位論文基于WEB的問答系統(tǒng)答案抽取的研究計算機應用技術研究生唐娟指導教師杜亞軍摘要隨著INTERACT的高速發(fā)展，網上的信息越來越多，如何在海量的信息中快速準確的找到所需要的信息成為目前的一個研究熱點。新一代搜索引擎一問答系統(tǒng)予互聯(lián)網豐富，開放的信息資源中應運而生，實現(xiàn)更快速，更智能，更準確的獲取用戶所需的信息。問答系統(tǒng)QUESTIONANSWERING,簡稱QA即是能利用信息抽取，信息檢索，自然語言處理等相關技術，用準確、簡潔的答案回答用戶用自然語言提出的問題。它主要由三個部分組成問題理解，信息檢索，答案抽取。如何在問題理解階段充分理解用戶的提問意圖，如何在信息檢索模塊中把相關的文檔找出來，如何在答案抽取模塊中準確地把答案從相關文檔中抽取出來，這三個問題是問答技術的核心問題。本文的研究內容是問答系統(tǒng)的答案抽取部分。利用形式概念分析對以下兩個部分做相應的研究從常問問答集中抽取答案；從WEB中抽取答案。本文采用基于WEB和語料相結合的多策略方法。針對問答系統(tǒng)的結構復雜性，提出使用FCA形式概念分析來抽取答案。對于不同類型的問題，使用不同的抽取模式。利用概念匹配完成答案抽取，特別地，對于定義型問題，提出了協(xié)作推薦的方法。本文首先使用了FCA來處理問答系統(tǒng)的答案抽取。在抽取處理中，首先在FAQS中尋找問題，如果該問題相應的答案不能滿足用戶的需要，再通過搜索引擎從網上獲取相關的文檔，從而使用返回的最相關的前N個文檔建立概念格。最后，利用概念匹配的在格中抽取答案。對于不同的問題，本文使用了不同的抽取策略。為了提高問答系統(tǒng)的精確度，本文提出了一個新的結合形式概念分析的概第1頁HTTP/INFO3DOUCOM/口碑營銷西華大學碩士學位論文念化聚類用戶日志的方法。由于日志信息是每天變化的，本文改進聚類算法獲得更好的性能。首先使用改進的基于DBSCAN聚類算法聚類用戶的日志。其次，這些聚類被用來構建形式背景，從而試圖根據(jù)問題查詢詞的內容和文檔的點擊信息來處理相似性問題。這里，主要利用聚類來建立更符合用戶需求的概念格。最后，本文提出使用導航技術從FAQS中抽取答案。在信息獲取方面，本文介紹了一種新的基于FCA的個性化的元搜索引擎，MYSCARCH。它獲取用戶的信息，通過重排結果，提供一個實時的響應。重排是通過使用用戶的使用日志和源搜索引擎返回的結果共同組建的概念格實現(xiàn)的。最后，改進的重排通過MYSEARCH返回給用戶。對于定義型的問題，本文利用基于形式概念分析的協(xié)作推薦來回答定義型的問題。在協(xié)作推薦中，本文應用文檔和問題之間的關系作推薦。FCA組建文檔和查詢?yōu)楦拍睿ㄟ^概念格來排序。最后，本文介紹了基于概念匹配的答案抽取，概念聚類日志與FAQS評估，基于元搜索引擎信息獲取，利用協(xié)作推薦回答定義型問題等四個核心模塊的實驗方法，步驟，結果及其評價。關鍵字問答系統(tǒng)；形式概念分析；答案抽?。痪垲惙治?；數(shù)據(jù)挖掘第頁西華大學碩士學位論文ANSWEREXACTIONOFQUESTIONANSWERINGBASEDON爭紹BCOMPUTERAPPLICATIONTECHNOLOGYMASTERDEGREECANDIDATEJUANTANGSUPERVISORYAJANDUABSTRACTALONGWITHTHEHIGHSPEEDDEVELOPMENTOFINTEMET,THEINFORMATIONONTHEWEBISMOREANDMORCITISAHOTRESEARCHTHATHOWTOFINDOUTTHENEEDEDINFORMATIONQUICKLYANDEXACTLYFROMVERYLARGEAMOUNTOFINFORMATIONSOURCCINGENERALDOMAINATPRESENT，THEINTEMETNOTONLYHASTHEABUNDANTINFORMATIONSOURCC，BUTALSOTHEINFORMATIONISOPENEDHOWTORETRIEVETHENEEDEDINFORMATIONTHEMOSTOFQUICKLY,THEMOSTOFINTELLIGENCEANDTHEMOSTOFEXACTLYBASEDONTHEEACHUSEHAVEVERYLARGEAMOUNTOFINFORMATIONSOURCEISTHENEWGENERATIONOFSEARCHENGINETODEVELOPTHEREBY,QUESTIONANSWERINGISPRODUCEDQUESTIONANSWERINGDEPENDSONAPPLYINGINFORMATIONRETRIEVAL，INFORMATIONEXTRACTION,ANDNATURALLANGUAGEPROCESSINGNLPTOANSWERFORGIVENDOMAININDEPENDENTQUESTIONSWRITTENINNATURALLANGUAGEEXACTLYANDSIMPLYQUESTIONANSWERINGQASYSTEMSTYPICALLYCONSISTROUGHLYOFQUESTIONANALYSIS,DOCAMENTPASSAGERETRIEVAL,ANDANSWERSELECTIONTHEREARETHREECOREQUESTIONSOFQUESTIONANSWERINGHOWTOCOMPREHENDENOUGHATTHESTAGEOFQUESTIONANALYSIS，HOWTOFINDOUTTHERELATEDDOCUMENTSFROMMODULEOFINFORMATIONRETRIEVES，ANDHOWTOEXACTTHEANSWERSFROMTHERELATEDDOCUMENTSINTHEMODULEOFANSWEREXACTIONWEARERESEARCH011THEANSWEREXACTIONINTHISPAPERWEUTILIZEFORMALCONCEPTANALYSISTORESEARCHTHEFOLLOWINGTWOPARTSTOEXACTANSWERSFROMTHEFREQUENTLYASKCDQUESTIONSANDTOEXACTANSWERSFROMTHEWEB第頁HTTP/INFO3DOUCOM/口碑營銷西華大學碩士學位論文WEPROPOSEANFFWAPPROACHOFCONCEPTUALCLUSTERINGTHEU嘶QUERIESLOGSWITHFORMALCONCEPTANALYSISFCADUETOTHELOGDATACHANGEDAILY,OURMETHODSCOULDBERECEIVEDBETTERPERFORMANCEBYUSEOURCLUSTERINGMETHODWEUSEOURCLUSTERALGORITHMTHATISBASEDONTHEDSBCANTOCLUSTERTHEUSERLO筍FIRSTLYTHENTHESECLUSTERSAREESTABLISHEDTHEFORMALCONTEXTWEATTEMPTTODEALWITHSIMILARQUESTIONSQUERIESACCORDINGTOTHEJRCONTENTSASWELLASTHEDOCUMENTCLICKINFORMATIONCROSSREFERENCESINTHEFORMALCONTEXTWEMAINLYUSETHEMTOBUILDTHEBEUERCONCEPTLATTICESINADDITION,WEPROPOSEDTHATNAVIGATIONCANBEUSEDTOEXTRACTANSWERSFROMTLIEFAOSWERSEMULTISTRATEGYBASEDONTHEWEBANDCORPUSDUETOTHECOMPLEXITYOFTHESTRUCTUREINTHEQUESTIONANSWERING,WEPROPOSEDTHATNSGFCATOEXACTANSWERSFORTHEDIFFERENTQUESTIONS，WEUSETHEDIFFERENTSTRATEGIESTOEXACTWEACHIEVEDTHEANSWEREXACTIONBASED011THECONCEPTMATCHING，SPECIALLY,FORTHEDEFINITIONQUESTIONS，WEUTILIZETHECOLLABORATIVERECOMMENDERSTOSELECTANSWERSTHISPAPERINTRODUCEDANEWPERSONALMETASEARCHENGINEMYSEARCH,WHICHISBASEDONFORMALCONCEPTANALYSISITEXTRACTSUSERSINFORMATIONIMPLICITLYANDPROVIDESREALTIMERESPONSEBYRERANKINGTHERESULTSRERANKINGISDONEBYUSINGCONCEPTLATTICETHATISBUILTBYUSERSUSAGELOGSANDTHERESULMOFSOURCEENGINELASTLY,THEIMPROVERERANKISRETURNEDBYTHEMYSCARBHEXPERIMENTALRESULTSSHOWOURMETHODHAVEASIGNIFICANTIMPROVEMENTONSATISFACTIONDEGREEBETWEENTHESEARCHRESULTANDUSERSREQUIREMENTFINALLY,WEINTRODUCETHEEXPERIMENTRESULTSANDTHEEVALUATIONKEYWORDSQUESTIONANSWERING；FORMALCONCEPTANALYSIS；ANSWEREXACTION；OUSTERANALYSIS；DATAMINING第頁西華大學碩士學位論文聲明本人聲明所呈交的學位論文是本人在導師指導下進行的研究工作及取得的研究成果。除了文中特別加以標注和致謝的地方外，論文中不包含其他人已經發(fā)表或撰寫過的研究成果，也不包含為獲得西華大學或其他教育機構的學位或證書而使用過的材料。與我一同工作的同志對本研究所做的任何貢獻均已在論文中作了明確的說明并表示謝意。本學位論文成果是本人在西華大學讀書期間在導師指導下取得的，論文成果歸西華大學所有，特此聲明。作者簽名碴礪弘7年月日導師簽名弛。吵警砷年6月F日第68頁HTTP/INFO3DOUCOM/口碑營銷西華大學碩士學位論文第1章引言隨著HTEMCT的高速發(fā)展，網上的信息越來越多，如何在海量的信息中快速，準確的找到所需要的信息成為目前的一個研究熱點。目前的搜索引擎GOOGLE1，YAHOO3，百度【2】，中搜【4】等已經取得了很大的成就，但是這些搜索引擎存在了一些不足1目前，搜索引擎主要是被設計用來獲取與用戶查詢請求相關的文檔，其查詢的序列一般是一系列的關鍵字的組合，而不是自然語言形式提供的，用戶不能僅僅通過幾個關鍵字清楚的表達自己的檢索意圖，搜索引擎也就沒有辦法找到最符合用戶心意的答案；2搜索引擎返回的也是與關鍵字內容相關的網頁即關鍵字字符與網頁字符相關列表，并沒有涉及到語義，檢索的質量較差；3另外，在返回的結果中只有一小部分是用戶需要的，用戶還必須從這些結果中自己尋找相關的具體信息。目前，互聯(lián)網不僅擁有豐富的信息資源，而且信息是開放的，每個用戶都可以通過互聯(lián)網訪問這個海量的信息，因此如何最快速，最智能，最準確的獲取自己所需的信息就成為了新一代搜索引擎的發(fā)展方向，問答系統(tǒng)便由此產生。11問答系統(tǒng)研究動態(tài)隨著網絡和信息技術的快速發(fā)展，同時人們想更快的獲取信息的愿望促進了自動問答系統(tǒng)技術的發(fā)展。最近越來越多的公司和科研院所參與了自動問答技術的研究。比如微軟和IBM等著名的跨國公司。文本信息檢索會議觚也C，TEXTRETRIEVALCONFERENCE，HTTPTRECNISTGOV是文本檢索領域最為權威的組織，TRECL，TREC5，TREC6等是世界公認的文本檢索系統(tǒng)的標準化測試集。從1999年開始TREC推出了TRECQUSCTIONANSWERINGTRACKHUPTREENLSTGOVDATAQAHTML1，用于推動問答領域的工作A在2000年10月召開的ACL2000國際計算語言學學術會議上，有一個專題討論會，題目是“OPENDOMAINQUESTIONANSWERING“。自此，自動問答QUESTION第1頁西華大學碩士學位論文AMWCRINGTRACK是最受關注的主題之一。越來越多的大學和科研機構參與了TREC會議的OUCSTIONANSWERINGTRACK。目前已有的問答系統(tǒng)1STARHTTPWWWAIMITEDUPROJECTSINFOLAB麻省理工MIT就開發(fā)出一個問答系統(tǒng)STAR，從1993年開始發(fā)布在INTEMET上，可以回答一些有關地理，歷史，文化，科技，娛樂等方面的簡單問題。在2000年，MRR開發(fā)的S1ART是世界上最早基于WEB的QA系統(tǒng)，返回段落或者句子。2ANSWCRBUSHTTPMISSHOOVCRSIUMICHEDUZZHENGQANEW是一個多語種的自動問答系統(tǒng)，它不僅可以回答英語的問題，還可以回答法語，德語，意大利語和葡萄牙語的問題，返回的是段落或者句子。3ASKJEEVCSHTTPWWWASKJEEVESEOM返回結果與普通的搜索引擎很相似，都是網頁。特點是允許用戶用自然語言句子提問，檢索系統(tǒng)會自動分析用戶的提問，然后通過人機交互方式，準確地辨識用戶的意圖，這樣用戶就能夠充分表達他的檢索需求。4ASKMSR5微軟研究院研制開發(fā)，為了快速查找相關文檔的能力，建立在GOOGLE搜索引擎之上，返回簡短詞語或短語。ASMSR是基于答案頻率統(tǒng)計的問答系統(tǒng)。把答案用ANSWERTTLING的方式組合，沒有使用詞性信息但是，對中文來說，詞性對答案很有用，簡單使用出現(xiàn)頻次和NGRAM模型來匹配答案，NGKAM即是考慮前面N1個詞構成歷史的模型，它有助于英文短語的提取。5WENIWENHTTPLLWWWWENIWENTOM由100多個學生組織起來對INTERACT上的各個網頁進行提問，這些提問被記錄下來作為網頁的索引，在實際使用時，如果用戶的某個提問與作為索引的某些提問在語義上非常接近，那么就把與這些提問相連的網頁返還給用戶。但是它返回的結果仍然是網頁，而不是真正的問題的直接答案。另外，其他典型的問答系統(tǒng)還有IONAUT，WEBCLOPEDIA，MULAER等等6。，自從文本檢索會議N匝C在1999年的11REC一8會議上引入了對問答系統(tǒng)的評測后，越來越多的基于自然語言的問答系統(tǒng)產生問答系統(tǒng)進入一種積極的研究領域，由1RI邏CQA上反應出，問答系統(tǒng)逐漸向問題多樣化，問題復雜化，和評估的精確化方向發(fā)展。近年來，問答系統(tǒng)滲入學習機制，向多種語言，多領域發(fā)展。近期的研究也是集中在為問題獲取答案，而不是獲取與查詢第2頁HTTP/INFO3DOUCOM/口碑營銷西華大學碩士學位論文詞相關的文檔或者最佳的匹配章節(jié)。問答系統(tǒng)的難點是應用信息檢索，信息抽取，機器學習和自然語言處理等相關技術。綜上所述，國內外針對問答系統(tǒng)已經做了大量的研究，從理論和實踐上都取得了一定的成果，但目前仍然處于研究的初期階段，因此，有必要進行深入、系統(tǒng)的研究。L2問答系統(tǒng)的研究簡況現(xiàn)有的問答系統(tǒng)所采用的方法主要包括自然語言處理方法；冗余技術；基于頻率統(tǒng)計；多策略方法。它的體系結構包括問題理解，信息檢索，答案抽取。121問答系統(tǒng)的研究方法自從文本檢索會議通C在1999年的TREC8會議上引入了對問答系統(tǒng)的評測后，越來越多的基于自然語言的問答系統(tǒng)產生問答系統(tǒng)進入一種積極的研究領域，由TREEQA上反應出，問答系統(tǒng)逐漸向問題多樣化，問題復雜化，和評估的精確化方向發(fā)展【刀。由于管道結構成功的應用【8】，問答系統(tǒng)通過結合知識源，應用復雜的推理機制，逐漸開始處理各種類型的問題【9】，引入的外部數(shù)據(jù)源，比如WEB、百科全書、數(shù)據(jù)庫等10，111。在元系統(tǒng)MET,ASYSTEMS中也應用了多種代理和策略12，131。綜上，問答系統(tǒng)的研究方法主要分為以下幾類11自然語言處理方法N也CQA在近來的問答系統(tǒng)研究領域中，起了積極的推動作用。在最初的問答系統(tǒng)研究中，主要是基于事實的，短的問答，比如1H0KILLEDABRAHAMLINCOLN”，”WHATWASTHELENGTHOFTHEWRIGHTBROTHERSFIRSTFLIGHT”，WHENDIDCNNBEGMBROADCASTING”。問答系統(tǒng)使用NLP技術來標準化信息獲取技術。系統(tǒng)使用瓜技術來標識侯選段落，然后利用語吉學詳細的分析問題和匹配段落，以便找到明確的答案。在問答系統(tǒng)中使用了多種語言學方法，比如詞性標注PARTOFSPEECHTAGGING；句子解析PARSING；命名實體抽取ENTITYEXTRACTION第3頁西華大學碩士學位論文利用語義關系詞典，如WORDNETL；使用相關語言學處理軟件，如LINGJIPE2，MINIPARA等。由HARABAGIU等人提出的FALCON系統(tǒng)便使用了語言學方法，在基準測試中證明具有極好的性能。在系統(tǒng)中，查詢問題被解析為可識別重要實體，并提出一種可能的答案類型。一種應用詞匯語義資源的答案類型在WORDNET中發(fā)展起來141。WORDNET在同義詞集中描繪了大于10萬的英語名詞，動詞，形容詞和副詞，并通過詞典編纂者進行編碼。侯選的匹配段落如果能與答案的類型匹配，那么它將會做相似的處理。常見的，相關的段落中含有的單詞與查詢中的單詞不一樣。在這類情況下，F(xiàn)ALCON系統(tǒng)使用WORDNET來檢查詞性的可選性，詞匯的可選性例如名詞“KILLER”，“ASSASSIN”，“SLAYER”將會與動詞“KILLED”匹配和語義的可選性例如“CAUSETHEDEATHOF”。另外，綁架的過程也會用來作為答案的選取依據(jù)，從而刪除一些不正確的答案。2冗余技術相對于這些豐富的自然語言方法，有的問答系統(tǒng)試圖通過信息源中大量的冗余信息來解決匹配和抽取答案的問題。例如ASKMSR151。冗余信息，可以用來獲得多樣的。不同的提問方式的答案。目前，促進問答系統(tǒng)發(fā)展有兩種趨勢第一，大量的信息源，信息越多，與問題越接近的答案越可能出現(xiàn)。例如問題“WHOKILLEDABRAHAMLINCOLN”，本文可以在大量的冗余信息中，直接的獲得“JOHNWILKESBOOTHL【ILLEDABRAHAMLINCOLNINFORDSTHEATER”。第二，就算沒有直接的答案，冗余信息也可以通過頻率統(tǒng)計比較容易的獲得答案。有些研究者利用WEB作為問答系統(tǒng)的信息源。例如MULDER系統(tǒng)【161在很多方面與ASKMSR相似。就每個問題，MULDER向WEB搜索引擎提交多個查詢，然后從搜索引擎返回的結果中分析答案。MULDER對問題進行解析，然后從獲取的全文網頁中識別侯選答案。MULDER用了一個本地數(shù)據(jù)庫來為每個侯選答案標識權重以抽取和選擇答案。但是MULDER還沒有被TREC查詢評估，所以它的性能很難與其它的系統(tǒng)比較。CLARKE等人17，181在他們的問答系統(tǒng)中，對冗余的重要性進行了研究。他們發(fā)現(xiàn)，問答系統(tǒng)最好的評估權重的方法是同時使用統(tǒng)計頻率即1WORDNETMILLER,1990一個眾所周知的英語語義關系詞典，它覆蓋了一大半的英語名詞，動詞，形容詞，副詞等，被廣泛的應用在NIP和其它的OA系統(tǒng)中1LINGPIPE由ALIAS1開發(fā)是一種開放式的NLP資源軟件它提供語言學上的分析處理功能如句子的發(fā)現(xiàn)，命名實體發(fā)現(xiàn)等3MINIPAT由DEKANGLING博士于1994年開發(fā)，提供NIP功能，比如詞性標注，句子解析，命名實體分類等。第4頁HTTP/INFO3DOUCOM/口碑營銷西華大學碩士學位論文冗余和一個標準權重。而且，他們發(fā)現(xiàn)分析更多的高權重的段落是很有幫助的。他們的系統(tǒng)為所有搜集的文檔建立一個全文索引作為TREC測試搜集。它們的實現(xiàn)要求一個可靠的輔助性的WEB文集。KWOK16和CLARKE17，18】為問題和最佳匹配網頁實現(xiàn)復雜的句子解析和命名實體的提取，這樣可以控制它們，從而詳細分析網頁數(shù)量。他們同樣在選取或者排序最佳匹配段落中要求輔助的數(shù)據(jù)結構。ASKMSR不同之處在于它的簡單性和有效性。該系統(tǒng)只伎用了簡單的重寫和句子匹配，且在查詢到WEB資源時直接的使用了摘要和簡單的隊列返回。這種數(shù)據(jù)驅動技術在TREC基準測試中表現(xiàn)出很好的性能191。3基于頻率統(tǒng)計基于統(tǒng)計學習的答案提取技術已經取得一定的成功。一個統(tǒng)計的QA系統(tǒng)【20】使用了極大熵來實現(xiàn)答案的正確性分類。18】使用了簡單的模式，采用直接的匹配來回答相關類別的問題?！?1】提出一種噪聲一引導方法NOISYCHANNEL來抽取答案，根據(jù)統(tǒng)計學的特點，來適應知識源的使用。使用同樣的方法【221提出一種完全的基于實例的，易于訓練的統(tǒng)計方法。4多策略方法近年來，問答系統(tǒng)出現(xiàn)多策略方法?！?3結合兩種端到端的問答系統(tǒng)基于知識的系統(tǒng)和基于統(tǒng)計的系統(tǒng)，在解析，獲取和產生答案階段共享中間結果。MITRE公司【24】在TREC2002結合使用基于距離和單詞及其性質的NGRAMS方法實現(xiàn)問答系統(tǒng)的標準輸出。雖然目前沒有更好的組合比這個組合更有效，但是，他們仍然建議使用幾種系統(tǒng)結合的方法來使輸出表現(xiàn)出更高的有效性，更多的訓練數(shù)據(jù)集和更好的特征?；诮M件水平的多策略方法已經通過反饋循環(huán)和極限集的應用，使他們在問答過程中重復的實現(xiàn)?！?5利用預先設定極限值來決定查詢的重寫和另外獲取數(shù)據(jù)集的必要性。近幾年來，LCC【9】構建了一個系統(tǒng)，嘗試著證明一個問題理論上來自一個答案，使用一種基于來自WORDNET的公理萃取的推理機制來證明。當證明失敗后，系統(tǒng)增加了松弛條件。ASKMSRDT11是一個基于WEB的問答系統(tǒng)，探測使用了決策樹來為動態(tài)產生的查詢重寫策略提供答案質量預測。這個方法，即是使用質量預測作為一個啟發(fā)式的規(guī)則來選擇重寫的順序和提供重寫的極限值。122問答系統(tǒng)體系結構隨著與多種自然語言處理工具與知識源的結合，問答系統(tǒng)的結構逐漸復雜第5頁西華大學碩士學位論文起來。傳統(tǒng)的問答系統(tǒng)如圖11由三個部分組成問題理解，信息檢索，答案抽取。如何在問題理解階段充分理解用戶的提阿意圖，如何在信息檢索模塊中把相關的文檔找出來，如何在答案抽取模塊中準確地把答案從相關文檔中抽取出來，這三個問題是問答技術的核心問題。FIGUREL1THESTRUCTUREOFQASYSTEM圖11問答系統(tǒng)結構1問題理解問題的分析是問答系統(tǒng)首先進行地工作，它的功能是將用自然語言描述的問題轉化成一系列代表了問題語義的關鍵詞。主要包括以下幾部分工作；對問題進行分詞以及詞性標注，確定問題的類型，提取出問題的關鍵詞，依據(jù)問題的類型等因素對關鍵詞進行適當?shù)臄U展。1問題分類對不同類型的問題，將會用不同的處理方法。一般的問答系統(tǒng)都按照疑問短語來對問題進行分類。它的目的就是為了幫助用戶縮小可能答案的范圍。通過對大量問題的統(tǒng)計分析發(fā)現(xiàn)，用戶提出的問題大概可以分為以下類型如圖二2關鍵字提取本文需要在用戶的提問中，提取對后面檢索系統(tǒng)有用的關鍵字，它不僅能第6頁HTTP/INFO3DOUCOM/口碑營銷西華大學碩士學位論文說明問題的主要內容，使問題意義清楚，而且突出強調了答案的類型。比如，表11常見的問題類型TABLEL1NORMALTYPCSOFQUESTIONTYPEOFQUESTIONQUESTIONASKPEOPLEWHOASKTIMEWHATTIMEWHICHYEAR，ASKNUMBERHOWMANYHOWLARGEHOWLONGASKDEFINITIONWHTASKLOCATION、VHE咒ASKLEASONWHY0THE侶疑問詞和一些常用的“吧，了，的”等詞就應該被過濾掉，為此，需要建立一個停用詞表來過濾這些詞。關鍵詞主要由名詞，動詞，形容詞，限定性副詞等組成，它們將被賦予不同的權重，在檢索段落時使用它們來計算段落的權重。關鍵詞被分為兩種一般性關鍵詞和“必須含有”性關鍵詞。所謂“必須含有”性關鍵詞指的就是該關鍵詞在答案段落中必須含有，主要由專用名詞，限定性副詞如最大，最高，最遠，最快，第一等、時間、數(shù)詞等組成。而一般性關鍵詞可以不被答案段落所包含。通常情況下，名詞，“必須含有”性關鍵詞，具有限定性作用的副詞會有比較高的權重。3關鍵詞擴展信息檢索評價的標準是信息檢索的精度和召回率。信息檢索的精度為檢索結果中相關信息文檔與查詢結果總數(shù)之比。信息檢索的召回率為實際檢索出的相關信息文檔數(shù)與信息庫中總的文檔數(shù)之比。為了提高檢索系統(tǒng)的召回率，需要對關鍵詞進行擴展。在答案句子中某些詞常常不是原來問題的關鍵詞，而是這些關鍵詞的同義詞。對關鍵詞進行擴展，可以提高關鍵詞的查詢成功率。對關鍵詞的擴展主要采用以下方式1名詞同義詞擴展和語義蘊涵擴展；2動詞同義詞擴展減少出現(xiàn)歧義的情況；3根據(jù)問題類型擴展如詢問數(shù)量類型可以把一些表示數(shù)量的單位加入。2信息檢索第7頁囂華大學碩士學位論文信息檢索就是用前面提取出來的關鍵詞，使用搜索引擎如GOOGLE來查找相關的文檔并返回一些最相關的文檔。系統(tǒng)實際分為兩個階段進行檢索文獻檢索和段落檢索。1文獻檢索文獻檢索主要使用信息檢索技術，根據(jù)問題處理部分產生的關鍵詞分類進行查詢遞交出符合關鍵詞的文獻一般的，取前100篇，并可以根據(jù)文獻相關性對它們進行排序。2段落檢索從文獻檢索中的文獻中選取最相關的段落一般的，取前100個段落，采用段落過濾方法，用盡可能少的摘錄覆蓋盡可能多的閥題內容。3答案抽取問答系統(tǒng)需要返回的是簡短的，準確性高的答案。這樣，通過信息檢索模塊搜索出來的相關文檔就要提交給答案抽取模塊來提煉答案。在答案抽取部分為了找到答案，系統(tǒng)主要依據(jù)關鍵詞，命名實體，模式匹配。對不同的問題，系統(tǒng)確定不同的答案模式。答案可以是一句話，或者是幾句話，也可以是幾個詞或短語。對于那些問時間地點的問題，就可以用很短的語句回答，而對于詢問原因，事件的問題就需要較長的句子才能回答比如為什么，怎么樣，等類型的問題。1以句子作為答案此類答案的抽取步驟如下1把檢索出來的文檔分成句子；，2按照一定的算法，計算每個句子的權重；需要考慮句子中含有的關鍵詞，和關鍵詞有相同語義的詞，句子中不包含的關鍵詞以及侯選句子與問題之間的語義相似度。3對句子按照權重進行排序；4根據(jù)問題的類型對侯選答案重新排序。2以詞或短語作為答案對于問題類型為時間或者地點類的問題，答案就比較簡短。所以希望直接把包含答案的詞或短語提取出來。但是，目前很難準確的把答案抽取出來。3以文摘作為答案對于有些問題，簡短的一個短語或者一句話很難說清楚。比如“地球是怎樣形成的”。這類河題，本文需要采用多文檔自動文攢技術，它把信息檢索模第8頁HTTP/INFO3DOUCOM/口碑營銷西華大學碩士學位論文塊檢索出來的相關文檔做成文摘，再把這個文摘作為答案返回給用戶。123問答系統(tǒng)評價方法評價方法1首先，需要建立一個測試集，可以是人工做出來的問題和答案對的集合。把這個測試集中的問題提交給問答系統(tǒng)，讓問答系統(tǒng)自動的給出答案。然后把問答系統(tǒng)自動找出的答案和測試集中的答案，進行人工的對比。如果問答系統(tǒng)給出的答案通過人工的對比基本正確，則可以判斷這個答案是正確的，否則可以判斷這個答案是錯誤的。根據(jù)公式1可以計算出問答系統(tǒng)的準確率。準確率答對的問蹶數(shù)問題總數(shù)12TREE會議每年都會提供一個測試集，讓參加TREE的研究人員評價自己的問答系統(tǒng)。TREC允許對每個問題給出5個答案。如果問答系統(tǒng)返回的第一個答案是對的，那么這個問題就得5分，。如果問答系統(tǒng)返回的第二個答案是對的，那么這個問題就得4分，如果問答系統(tǒng)返回的第三個答案是對的，那么這個問題就得3分，如果問答系統(tǒng)返回的第四個答案是對的，那么這個問題就得2分，如桌問答系統(tǒng)返回的第五個答案是對的，那么這個問題就得1分。把每個問題所得得分加起來就可以得到問答系統(tǒng)所得總分。總分越高，該系統(tǒng)得到準確率越高。13形式概念分析概念被理解為由外延和內涵兩個部分所組成的思想單元?；诟拍畹倪@一哲學理解，德國的WILLE教授提出了形式概念分析EZ63，273，用于概念的發(fā)現(xiàn)，排序和顯示。在形式概念分析中，概念的外延被理解為屬于這個概念的所有對象的集合，而內涵則被認為是所有這些對象所共的的特征或屬性集，這實現(xiàn)了對概念的哲學理解的形式化。而概念格作為形式概念分析中核心的數(shù)據(jù)結構，本質上描述了對象和特征之間的聯(lián)系，表明了概念之間的泛化和例化關系，其相應的HASSE圖則實現(xiàn)了對數(shù)據(jù)的可視化。作為序論和格論與實際應用結合的產物，概念格模型的研究具有重要的理論意義。第9頁西華大學碩士學位論文131形式概念分析的理論基礎現(xiàn)實世界是由各種各樣的對象組成，每個對象有自己的一組屬性或者特征，概念格結構是反映對象與屬性之間聯(lián)系以及概念泛化與例化關系的一種完備的概念層次結構。WHILE于1982年提出26由二元關系來建造相應的概念格的基本思想，這種特殊形式的格結構及其相應的HASSC圖就反映了一種概念層次結構。其建立在一個形式背景上，為研究信息系統(tǒng)的概念或知識提供了有力的工具。下面給出概念格的形式化描述。定義126一個形式背景FORMALCONTEXT是一個三元組T一0，D，R，其中0是對象集合，D是特征集合，R是0和D之間的二元關系，即尺OXD。其中ORD表示DD與DED之間存在關系R。形式背景可以用一個數(shù)據(jù)表來表示，它描述了對象及其特征之間的自然分組和關系的有序集。定義2263在形式背景中，對于對象集APD和特征集BPD可以定義下面的兩個函數(shù)F和GBA，D陬CA，珊AGA一XEOLVY召，XRY簡記為A。B，BA通常稱函數(shù)F和G為D的冪集PD和0的冪集E0之間的GALOIS連接。定義從形式背景中得到的每一個滿足BFA和AGB元組A，B為一個形式概念FORMALCONCEPT。其中A稱為概念的外延EXTENTB稱為概念的內涵INTENT。顯然，概念的內涵是概念外延中所有對象的共同屬性的集合，面概念的”延是概念內涵可以確定的最大的對象集合，一個概念是一個完備的二元組。定義3在概念節(jié)點之間能夠建立起一種偏序關系。對于給定CL4，且和C一即，島，則CJ，C2一曩C晚靜43心，領先次序意味著CT是C。的父節(jié)點或稱泛化。若概念CI0T，B，和C2。042，暑滿足嗚C4，且不存在概念A，B使得A，CACAL，則稱C。是島的直接超概念，C2是C。的直接子概念，記為研，且PU，B根據(jù)偏序關系可生成概念格的H豳辯圖。如果有CLC2，在HASSE圖中將存在一條邊從C1到CLC1是Q的直接超概念，C2是C1的直接子概念，形式背景T毛O，D，R中，滿足直接子概念超概念關系的所有概念節(jié)點的集合是一個完全格稱之為GALOIS概念格，簡記為概念格。第10頁HTTP/INFO3DOUCOM/口碑營銷西華大學碩士學位論文132概念格的構造算法概述在概念格的應用過程中，建格算法具有很重要的地位。概念格所具有的完備性是不受數(shù)據(jù)或屬性排列次序的影響，不同的構造方法所生成的格形式是唯一的，完備性一方面是概念格的優(yōu)點之一，另一方面即使對于適當大小的數(shù)據(jù)，也將產生龐大的格結構。理論上說，概念的節(jié)點個數(shù)會以形式背景對象個數(shù)和屬性個數(shù)的指數(shù)倍增長。所以概念格的構造過程十分耗時和非常關鍵。從構造方法的角度，概念格的建造算法分為三類批生成算法，漸進式算法和并行算法。目前有關概念格生成的并行算法PARALLELALGORITHM研究不多，并行算法通常是以其他算法原理為基礎提出可以預測對于海量數(shù)據(jù)的概念格的生成和應用研究，并行算法必然是一個大的趨勢。建立GALOIS格的過程實際上就是一個概念聚類的過程，因為它產生一種概念層次結構。迄今為止，國內外學者已經提出了許多不同的算法來構建概念格，但只有少數(shù)在構造的同時生成相應的HASSE圖。1漸進式算法INCREMENTALALGORITHM其基本的思想是假設形式背景中的前I個對象已經生成了概念節(jié)點的子集和概念格的子格，當?shù)贗L號對象加入時，去更新原有的概念節(jié)點子集和概念格的子格。重復這一步驟，直到生成最終的格結構。典型的算法有GODIN算法282和CARPINET29算法。這些策略很容易應用于屬性上，可以依據(jù)屬性而不是對象來漸進式生成概念格。在漸進式生成概念格的求解過程中，將當前要插入的對象插入概念格圖表中時，通常需要考慮三個問題所有新節(jié)點的生成；避免已有的概念節(jié)點的重復生成；HASSC圖表的更新。GODIN算法283采用漸進式算法來創(chuàng)建概念格，構造的關鍵在于找出所產生的子節(jié)點。其基本思想是在插入一個新對象之后，將格中的節(jié)點分為三類不變節(jié)點。它們是新格L，中所保留的格L中的節(jié)點，這些節(jié)點的內涵和新對象的內涵沒有交集更新節(jié)點。它們是對原來格L中的節(jié)點更新后的節(jié)點，這些節(jié)點的內涵包含在新對象的內涵中，因此只需將其外延更新包括新對象即可；新增節(jié)點。即所要插入的節(jié)點的內涵與原來格L中某個節(jié)點的內涵的交所產生的而在格L中沒有出現(xiàn)過的集合?？梢宰C明，新節(jié)點的父節(jié)點必然是某個新增節(jié)點或者更新節(jié)點。CARPINETO算法和GODIN算法的主要不同點出現(xiàn)在連接過程中，CARPINCTO的做法是找到新節(jié)點的最小上界和最大下界，刪除它們之間的邊，第11頁西華大學碩士學位論文并將其連接到新概念。2批生成算法BATCHALGORITHM主要完成兩項任務第一，生成所有概念節(jié)點集合，即形式概念的集合；第二，建立概念節(jié)點之間的直接前驅和直接后繼關系。常見的有兩種情況，其一是首先生成所有的概念節(jié)點的集合，再生成概念的圖表結構；其二是每次生成概念節(jié)點的一小部分，同時將這些節(jié)點鏈接到概念格圖表結構中。目前已提出許多生成概念格的批生成算法。但是其中多數(shù)是僅僅生成概念節(jié)點的集合只有少數(shù)同時生成HASSE圖。批生成算法根據(jù)其構造格的不同方式，可分為兩類，即自頂向下算法和自底向上算法。自頂向下算法首先構造格的最上層節(jié)點即外延最大的概念節(jié)點，再逐漸往下生成較小外延概念。自底向上算法則相反，首先構造底部的外延最小的概念節(jié)點，逐步向上擴展生成較大夕延的概念，如CHEIN算法。另外，本文也可以從屬性的角度，依據(jù)屬性和概念的內涵而不是外延來自頂向下或者自底向上的生成概念。BORDAT701在1986年提出的批處理算法采用的是自頂向下的策略，其基本思想是從格的最大下界概念E，F(xiàn)E開始，并生成它的所有子概念，然后把這些概念添加到GCL中，并與其超概念連接，這一子概念生成過程對每個概念重復進行。GANTER算法使用表示X集的特征向量來枚舉格的X集，每個向量的長度是屬性集的基數(shù)。若某個屬性值在該向量中出現(xiàn)，則相應位置1，否則為0。給定完全對的向量XX1，X2，XM，它找到作為完全對一部分的下一個X向量關于向量的字典序。查找方式是按順序將屬性位置L，并測試它是否是完全對來進行的。以此方式產生的向量的有序列表是按照X集的包含順序拓撲排序的?；贐ORDAT的批處理算法70，NJIWOUA等提出了構造概念格的并行算法，文中給出了算法的正確性證明并研究了該算法的理論復雜性。133概念格的壓用作為近來引起廣泛關注的一種數(shù)據(jù)分析和知識處理的形式化工具，概念格目前已經在機器學習，信息檢索，數(shù)字圖書館，軟件工程，知識分類和數(shù)據(jù)挖掘等領域顯示出來一定的應用價值。作為數(shù)據(jù)分析和知識處理的形式化工具，形式概念分析已經獲得了廣泛而成功的應用。在軟件工程領域，形式概念分析為再工程，軟件重用，面向對象程序設計等領域中某些問題的解決提供了理論第12頁HTTP/INFO3DOUCOM/口碑營銷西華大學碩士學位論文支持，并已經取得了一系列的應用成果。隨著計算機和數(shù)據(jù)庫技術的發(fā)展以及各種電子設備的大量使用，人類收集數(shù)據(jù)的能力得到了極大的增強，數(shù)據(jù)信息日益膨脹，但是堆積如山的積累數(shù)據(jù)對于人類是難以處理的，真正有價值的是埋藏于數(shù)據(jù)中的知識，因此數(shù)據(jù)挖掘技術已經褥到了廣泛的研究。而形式概念分析以概念格的形式使數(shù)據(jù)有機的組織起來，概念格節(jié)點體現(xiàn)了概念內涵和外延的統(tǒng)一，因此非常適合于用來發(fā)現(xiàn)規(guī)則型知識。已有不少學者討論了從概念格上提取規(guī)則或函數(shù)依賴的問題。和其它分類器相比，概念格上提取的規(guī)則具有相當或更好的分類效果陰F8】【9】。而在信息檢索方面，NEUSS和KENT30使用概念格進行INTEMET上文檔信息的自動分類和分析。COLE和EKLUND將概念格方法應用于分析和可視化具有1962個屬性和4000個處方摘要的醫(yī)藥數(shù)據(jù)庫。EKLUND和MARTIN31展示了概念層次進行WEB文檔索引和導航的能力。LENGNINK32將VSM模型中的相似度和距離概念轉換到格模型中，這樣傳統(tǒng)信息檢索模型中的自動化的方法自動分類，聚類能應用到格模型中。CARPINETO和ROMANO33將查詢插入文檔集的概念格中，用最短路徑的方法來計算文檔相似度，以解決詞匯不匹配問題。聯(lián)機分析處理OLAP依賴于一個包含有數(shù)據(jù)的多維立方體，當維不是層次化結構的時候，用立方體作比喻為多位數(shù)據(jù)提供了一種良好的直觀理解。但是OIAP維的一個重要的特征在于它們是層次排序的。通常它們是樹，但也可能是任意的偏序集。由于立方體的比喻反映的是線形向量空間的直積的數(shù)學意義，在這種情況下，層次必須被強制轉化為簡單的線形形式，因此立方體并不適合用于表示具有層次維的數(shù)據(jù)。概念信息系統(tǒng)由一個關系數(shù)據(jù)庫和多個概念層次概念標尺組成，這些層次被用于支持對數(shù)據(jù)的導航。以概念信息系統(tǒng)為基礎，文【11通過使用嵌套線圖來對概念層次的任意組合進行可視化。由于層次維大致地對應于概念標尺；因此OLAP分析工具可以被大致看作是一種特殊的概念信息系統(tǒng)。嵌套的線圖被用于繪制維的直積，從而替代了在OLAP中被廣泛使用的嵌套圖。與傳統(tǒng)的嵌套圖相比，嵌套的線圖占用了較多的空間，它的優(yōu)點在于沿著最重要的維被選為最外層的層次的清晰的結構化，因此非常便于閱讀數(shù)據(jù)，并且允許使用比OLAP中通常使用的樹狀維更加復雜的標尺任意的偏序集。為了實現(xiàn)對數(shù)據(jù)立方中數(shù)據(jù)進行存取的四種交互方法切片，旋轉，DRILLDOWN和DRIFTUP，另外還研究了與這些操作相對應的嵌套線圖的相應動作。第13頁西華大學碩士學位論文概念格還獲得了其它的一些應用，比如，WILLE在【34】中將概念圖和形式概念分析結合起來，從而得到了對初等邏輯的一種形式化，這對于知識表示和處理是非常有用的。RICHARDSDEBBIE35利用概念格對RIPPLEDOWNRULE進行有機的組織COLE的CEM電子郵件管理系統(tǒng)【36】通過將FMAIL存儲在概念格中，而不是常用的櫥狀結構中，從而在檢索電子郵件時獲得了更大的靈活性；文F5】則將概念格應用于智能幫助系統(tǒng)的領域建模等等。14本文的主要研究內容問答系統(tǒng)主要由三個部分組成問題理解。信息檢索，答案抽取。如何在闖題理解階段充分理解用戶的提問意圖，如何在信息檢索模塊中把相關的文檔找出來，如何在答案抽取模塊中準確地把答案從相關文檔中抽取出來，這三個問題是問答技術的核心問題。本文主要內容是對問答系統(tǒng)的答案抽取部分的研究。利用形式概念分析重點對以下部分做相應的研究從常問問答集中抽取答案；和從WEB中抽取答案等問題進行研究。1、從常問問答集FREQUENTLYASKEDQUESTIONS。FAQSQH抽取答案FAQS，即常問問題集。作為本文問答系統(tǒng)的一個組成部分，把用戶經常提問的問題和答案保存起來。對于用戶輸入的問題，首先在常問問題集中查找，如果能夠找到相應的問題，就可以直接將相應的答案返回給用戶，而不需要經過問題理解，信息檢索，答案抽取等相關的復雜的處理過程，這樣不僅可以提高效率，而且也能提高精度。但是其中需要解決兩個問題人類編輯如何確定哪些問題查詢是常問問題，即那些是FAQS另外，一個系統(tǒng)如何判斷兩個問題查詢詞是相似的本文采用的方法是使用一種概念化的查詢聚類的方法，使用用戶的日志信息來識別用戶使用過的文檔信息。對于計算推導兩個查詢詞的相似度將使用查詢詞和交叉參照兩個標準。PRINCIPLE1USINGQUERYCONTENTS如果兩個查詢包含相同的或相似的項，它們表示相同或相似的信息需要。顯然，查詢越長，原理1就越可靠。但是，在查詢短的情況下，光使用這個原理是不夠的。因此，第二個標準作為原理的補充。HTTP/INFO3DOUCOM/口碑營銷西華大學碩士學位論文PRINCIPLE2USINGDOCUMENTDICKS如果兩個查詢導致選擇了相同或相似的文檔，那么它們是相似的。而聚類處理的算法，考慮日志信息本身的特點一查詢日志經常都是很大的，該算法應該有能力處理大的數(shù)據(jù)集，而且存在合理的時間和空間的約束。一算法應該不需要人工的設置聚類的形式，例如，聚類的數(shù)量或者最大聚類的大小。根據(jù)本文的研究對象一龐大的日志，事先就要確定好聚類數(shù)量等參數(shù)是不切實際的。一對于實際的日志信息，本文只要求找到出現(xiàn)頻率高的FAQS，對于低頻信息，本文暫不關注。所以算法應該可以過濾低頻率的查詢。一由于實際的日志數(shù)據(jù)是時刻變化的，算法必須是增量的。所以，本文采用基于密度的聚類方法DBSCAN和它的增量的版本增量的DBSCAN作為基礎算法，另外改進它，從而可以直接產生出常闖問題類，方便抽取精確度更高的答案。2、基于WEB的答案抽取采用基于WEB和語料相結合的多策略方法。針對問答系統(tǒng)的結構復雜性，提出使用FCA形式概念分析來抽取答案。對于不同類型的問題，使用不同的抽取模式。首先，從語料數(shù)據(jù)庫中即EAQS搜索與用戶問題相關的問題，如果沒有或者答案不滿足用戶的需求，再通過搜索引擎從WEB中搜索相關的文檔然后使用搜索引擎返回的前R1個文檔，構建概念格最后，利用概念匹配來抽取答案。這里，本文針對不同類型的問題，使用不同的抽取模式。抽取處理步驟1文檔概念格的建立使用搜索引擎返回的文檔作為形式背景，文檔作為對象，描述文檔的短語作為屬性，文檔與短語之間的關系作為值布爾值。主要涉及的問題短語的選取。37】本文的步驟1在文檔中選取所有出現(xiàn)的侯選短語；2在侯選短語中根據(jù)特殊查詢平衡策略OUERYSPECIFICBALANCEDSTRATEGY37選取能更好描述文檔的短語得分高。特殊查詢平衡策略的特點是利用短語本身的特點和它在文檔中出現(xiàn)的頻率進行打分。第15頁西華大學碩士學位論文2問題概念格的建立；對于一個用戶提出的問題，本文主要是發(fā)現(xiàn)問題的主題和問題的焦點。這里，將問題的主題作為對象，焦點作為屬性，進行概念格的構建。另外，考慮問題類型對答案的影響很大，所以，考慮將問題的類型也作為屬性。3概念匹配為每對問題一答案對賦權值，再利用相似度的計算方法作概念匹配。余弦相似度的計算方法如下【38】SIMILARITY自RDP，口。FACTOIDQUESTIONS在答案選取過程中，使用單元匹配OBJECTATTRIBUTE對；利用相似度的計算方法，選擇最相關匹配的概念最多的短語作為答案。LISTQUESTIONS使用單元匹配，但是選擇所有匹配的概念作為答案。這里需要選擇一個相似度的閾值來判斷，該答案是否為