【文章內(nèi)容簡(jiǎn)介】 的短語(yǔ)(key phrase)，準(zhǔn)確的找尋到，這樣既能夠準(zhǔn)確的解讀文檔中的關(guān)鍵信息，同時(shí)能夠大大提高聚類的可讀性。提取出來的短語(yǔ)首先要確保的是其完整性。提出了短語(yǔ)完整性的概念。設(shè)文檔T，其長(zhǎng)度為N，T的完整子字符串S定義為：S稱為T的完整子字符串，當(dāng)S在T中出現(xiàn)互不相同的k次的位置P， P2.. .， Pk時(shí)，其中至少存在一對(duì)吏得T中第(/01個(gè)字符與第個(gè)字符不相同（左完整性），并且，其中至少存在一對(duì)(/，/)(1^〗^_/^/0使得了中第(p， +|s1)個(gè)字符與第(/^ +岡)個(gè)字符不相同(右完整性)。我們以文檔T= “to—be—or—not—to—be”和T的子字符串“to_be”為例，說明一下以上的概念。左完整：子字符串“to_be”是左完整的，比較第(01)個(gè)字符，和第（131)個(gè)字符（“―”），兩者不同，根據(jù)以上概念定義，“to—be”是左完整的。右完整：子字符串“to_be”也是右完整的，比較T中第(0+5)個(gè)字符（“一”）和第（13+5)個(gè)字符(T的結(jié)尾處），兩者不相同，根據(jù)以上概念定義，“to—be”也‘ 是右完整的。 根據(jù)完整字符串的定義，“to_be”就是T的完整字符串。在LINGO算法中，后綴數(shù)組(Suffix Array)是一個(gè)重要的數(shù)據(jù)的結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)就是效率特別的高，高效率來自于它能夠準(zhǔn)確的對(duì)文檔或者文本中的信息進(jìn)行充分的解讀，并從中找出關(guān)鍵性的短語(yǔ)。設(shè)一個(gè)文檔T，長(zhǎng)度為N，T的后綴數(shù)組S指將T所有的后綴按照字符順序排序，而令后綴起始的位置（按排序后的順序）構(gòu)成的數(shù)組。例如，設(shè)文檔T ： to_be_or_not_to_be?它的后綴集合為rs，則有下表所示：表1 表3. 2后綴數(shù)組表表3. 2從上述表格可以看出，實(shí)際需要存儲(chǔ)的僅僅是表格的中間一列，很明顯后綴數(shù)組的存儲(chǔ)只需要0(aO的空間，其中N為文檔的長(zhǎng)度。而創(chuàng)建后綴數(shù)組的算法的期望時(shí)間復(fù)雜度也是0(aO，查找一個(gè)長(zhǎng)度為P的字符串只需要0(尸+ logJV)的時(shí)間。 LINGO算法基礎(chǔ)之隱含語(yǔ)義分析隱含語(yǔ)義其實(shí)是漢語(yǔ)語(yǔ)法中的一個(gè)重要的特色，在其他語(yǔ)言中也有所體現(xiàn)，簡(jiǎn)言之，隱含語(yǔ)義分析就是針對(duì)日常用語(yǔ)中的同義詞或者近義詞進(jìn)行有效的歸類和合理的分析，同時(shí)對(duì)具有相同意思表達(dá)的詞組短語(yǔ)進(jìn)行有效的應(yīng)用，例如，在漢語(yǔ)中，“教師”和“先生”是完全不一樣的兩個(gè)詞，但是在詞語(yǔ)的詞義和實(shí)際的應(yīng)用中可以做到語(yǔ)義互換，能夠表達(dá)出同樣的含義。如果利用向量空間模型對(duì)所有的詞語(yǔ)或者關(guān)鍵詞進(jìn)行完全匹配，必然無法將同義詞這種意思相同表達(dá)不同的詞語(yǔ)做到完全區(qū)分，即如果將“教師”作為關(guān)鍵詞進(jìn)行搜索，那么對(duì)文檔進(jìn)行聚類分析之后，以“先生”為關(guān)鍵詞內(nèi)容的相關(guān)意思一致的文檔也就無法顯示出來，這給我們的搜索引擎發(fā)展帶來了技術(shù)性的瓶頸。事實(shí)上，在搜索引擎的實(shí)際應(yīng)用中，對(duì)詞組或者是關(guān)聯(lián)詞的使用，是搜索引擎技術(shù)發(fā)展的一個(gè)必由之路，因?yàn)樵跐h語(yǔ)中，有很多類似的隱含語(yǔ)義分析的詞組短語(yǔ)，而它們?cè)谕獗砩峡词歉窀癫蝗氲?。例如，“高等院校招生”，“高等院?！焙汀罢猩笔莾蓚€(gè)相互獨(dú)立、又有一定聯(lián)系的關(guān)鍵詞，如果用戶搜索“招生”，就會(huì)顯示出含有“招生”作為關(guān)鍵詞的文檔匹配項(xiàng)，但是很可能有一部分包含有“高等院?！钡膬?nèi)容，但是不包含“招生”。所以我們認(rèn)為這兩個(gè)詞存在著一定的語(yǔ)義關(guān)系，這類文檔也可能包含了用戶所需信息。作為一種常用的信息檢索技術(shù)，隱含語(yǔ)義分析（Latent Semantic Indexing， LSI)的出現(xiàn)最重要的作用是彌補(bǔ)向量空間模型所存在的缺陷。根據(jù)隱含語(yǔ)義分析（Latent Semantic Indexing， LSI)的觀點(diǎn)，詞語(yǔ)的選擇背后是隱含著一種來自語(yǔ)言含義方面的信息流，這種信息流是搜索的精髓，如何利用隱含語(yǔ)義分析的方法，從詞中提取的抽象概念替換或者取代與搜索關(guān)鍵詞意思相同的內(nèi)容。即將向量空間模型中簡(jiǎn)單的詞匯的匹配替代為語(yǔ)義的匹配。 如果把用來檢索的文檔之間的內(nèi)容看做是詞空間下面的一個(gè)子空間，那么任意兩個(gè)不同的文檔之間的子空間距離越小，則這兩個(gè)文檔之間的語(yǔ)義上就越相關(guān)，因此，詞往往被視作是一個(gè)文檔空間內(nèi)下屬的一個(gè)子空間，通過對(duì)兩個(gè)詞語(yǔ)之間的子空間距離進(jìn)行的判斷，可以對(duì)兩個(gè)詞語(yǔ)之間的相關(guān)程度進(jìn)行大致的判斷和分類。在實(shí)際操作中，由于詞與詞，文檔與文檔，以及詞語(yǔ)文檔之間的子空間的分布不是隨機(jī)分布的狀態(tài)，而是出于全文整體語(yǔ)義、詞義的內(nèi)容之中的，因此會(huì)受到上下文和整個(gè)文章所要表達(dá)的思想的束縛和限制。在這種情況下，語(yǔ)義空間表現(xiàn)出了詞詞、詞文檔、文檔文檔之間在語(yǔ)義上相關(guān)性。而在實(shí)際操作中，由于詞文檔矩陣的數(shù)據(jù)往往非常龐大，而且鑒于漢語(yǔ)文化的博大精深，常常會(huì)出現(xiàn)一詞多義，多詞一義的情況，這種情況的出現(xiàn)在現(xiàn)代漢語(yǔ)語(yǔ)文的行文和應(yīng)用充非常常見，因此會(huì)給我們的判斷帶來干擾和迷惑，在這種情況下，與向量空間模型中的文檔高維表示不同，潛在語(yǔ)義標(biāo)引還需要利用數(shù)學(xué)工具將原來的文檔高維表示投影到低維的空間、即潛在語(yǔ)義空間中，簡(jiǎn)化語(yǔ)義的空間結(jié)構(gòu)，從而達(dá)到縮小問題規(guī)模，消除并減少常見的迷惑和干擾。進(jìn)而在得到潛在語(yǔ)義空間之后，就可以根據(jù)各個(gè)詞和文檔的向量坐標(biāo)進(jìn)一步進(jìn)行分析。 LINGO算法過程分析所謂的文本預(yù)處理，是指為了進(jìn)一步提高取類標(biāo)簽的準(zhǔn)確性，將文本以聚類算法可用處理的形式進(jìn)行預(yù)處理，具體包括兩個(gè)階段：第一個(gè)階段叫做特征表示，第二個(gè)階段稱為特征提取。一般常見的理論認(rèn)為，文本的特征表示的模型有很多，常見的諸如概率檢索模型、布爾模型、概率檢索模型、向量空間模型等都是比較常見的模型，其中最流行的模型當(dāng)屬向量空間模型。下面具體介紹向量空間模型，根據(jù)向量空間模型的原理，文檔集C中的每個(gè)文檔Dj都是一個(gè)特征向量，且向量空間模型中所有文檔的特征向量都具有相同的維數(shù)：設(shè)為n，這個(gè)相同的尾數(shù)是全部文檔中所有不同特征項(xiàng)的總數(shù)目。文檔Dj的特征向量就可以用文檔中的特征項(xiàng)Ti及其權(quán)重Wij來表示：V(Dj={T，W。T，W，i；。T?W， }特征項(xiàng)Ti的權(quán)重Wij的計(jì)算才用TFIDF方法的標(biāo)準(zhǔn)定義：= TF，j X IDIf = X logAVDI^在以上的公式中，文檔集C的所有文檔的總和為N，TFi」為特征項(xiàng)T，在文檔Dj中出現(xiàn)的次數(shù)，DFi為文檔集C中包含Ti的文檔數(shù)目。類標(biāo)簽的提取是第二個(gè)步驟，是指在提取之前，需要對(duì)所有的包括關(guān)鍵詞和詞組在內(nèi)的關(guān)鍵詞進(jìn)行提取。我們所采用的LINGO算法在此步驟中采用的方法被稱為奇異值分解法(SVD： Singular Value Deposition)。通過奇異值分解法(SVD： Singular Value Deposition)來發(fā)現(xiàn)抽象的概念，主要是單一主題或者相關(guān)主題的集合，這種方法的有點(diǎn)在于能夠高效率的客服重復(fù)的詞組、短語(yǔ)，以及同義詞、近義詞和相關(guān)的人稱物主代詞，切實(shí)提高系統(tǒng)的便捷性和高效性。LINGO算法在關(guān)鍵詞組的提取方面采用的技術(shù)被稱為后綴數(shù)組技術(shù)。類標(biāo)簽的提取大致可以分為三個(gè)步驟：即抽象概念的發(fā)現(xiàn)、詞匹配和標(biāo)簽提取。其中，抽象概念發(fā)現(xiàn)階段主要是通過奇異值分解獲得文檔集合的潛在語(yǔ)義關(guān)系，LINGO認(rèn)為詞文檔矩陣A經(jīng)奇異值分解后產(chǎn)生三個(gè)矩陣U、S和V即：j = USV.39。.， U的列向量就代表抽象概念。最常用的獲得A的最佳近似矩陣Ak的方法如下式所示：Ml，名 II，乏？其中||y4||，..，是矩陣A的Frobenius范數(shù)，q是一個(gè)控制參數(shù)，明顯地g值越大獲得的k值也就越大，最終聚類獲得的類別數(shù)也就越多，默認(rèn)情況下LINGO取q=0. 775。詞匹配和標(biāo)簽提取主要解決的問題是類標(biāo)簽的確定。由于抽象概念和關(guān)鍵詞組都可以在同一個(gè)向量空間中描述，因此LINGO使用cosine距離公式來度量抽象概念和關(guān)鍵詞或關(guān)鍵詞組之間的相似度。P表示關(guān)鍵詞關(guān)鍵詞組矩陣，它可以通過將關(guān)鍵詞組看作偽文檔的方式來構(gòu)造，Uk表示抽象概念，因此抽象概念和關(guān)鍵詞、關(guān)鍵詞組的關(guān)系就可以通過下式來表示：M = U/P最后，類標(biāo)簽提取還要考慮重疊標(biāo)簽的修剪。構(gòu)造一個(gè)詞一文檔矩陣Z，其中類的候選標(biāo)簽表示一個(gè)文檔，執(zhí)行ZZ得到類標(biāo)簽之間的相似關(guān)系，選擇結(jié)果矩陣每行中超過標(biāo)簽相似度閾值(Label Similarity Threshold)并且最大者為. 該類的類標(biāo)簽。本文中所稱的文檔分配，具體是指在一個(gè)定義的矩陣Q中，用每一個(gè)行向量表示一個(gè)類標(biāo)簽，用C表示文檔的分配矩陣，那么整個(gè)文檔分配的具體構(gòu)造過程可以用下面的公式所表示：C=Q39。A在上面的公式中，A是輸入文檔的詞文檔矩陣，結(jié)果矩陣中的元素Cij表示第j個(gè)文檔屬于第i個(gè)類別的程度，定義一個(gè)文檔分配域值A(chǔ)SSIGNMENT—THRESHOLD，當(dāng)CijASSIGNMENT—THRESHOLD時(shí)將第j個(gè)文檔分配到第i個(gè)類，最后將沒有被分配的文檔分配到Other類，默認(rèn)情況ASSIGNMENT—THRESH0LD=0. 225。 LINGO聚類算法最終要形成最終聚類，聚類的結(jié)果的作用是將經(jīng)過處理后類權(quán)重排序后返回給用戶，下面的公式是根據(jù)LINGO算法采用的類權(quán)重計(jì)算方法：C/ote/ = labelscore x ||C||其中Ctote/ =7^^amp。/^^076乂||6|是分配到類別C的文檔數(shù)。 LINGO聚類算法的優(yōu)缺點(diǎn)作為搜索引擎技術(shù)中眾多優(yōu)秀算法的一種，LIGNO聚類算法經(jīng)過長(zhǎng)期的發(fā)展和演變，不斷的將技術(shù)應(yīng)用中存在的問題和缺陷進(jìn)行修補(bǔ)和完善，發(fā)展至今，LINGO聚類算法已經(jīng)成為比較成熟、易用性強(qiáng)、對(duì)不同的系統(tǒng)適應(yīng)程度高的一個(gè)比較好的優(yōu)選算法，本文對(duì)LINGO聚類算法的介紹，還停留在技術(shù)應(yīng)用的表面，LINGO聚類算法的優(yōu)點(diǎn)還有很多，特別是在系統(tǒng)的應(yīng)用中，和對(duì)搜索引擎技術(shù)的發(fā)展方面，還有很多值得肯定的方面，下面簡(jiǎn)單對(duì)LINGO聚類算法的優(yōu)點(diǎn)總結(jié)如下：首先，LINGO聚類算法能夠?yàn)榫垲惤Y(jié)果創(chuàng)建有意義的類標(biāo)題。通過類標(biāo)題的使用，能夠大大提高算法的準(zhǔn)確度和處理速度，對(duì)快速得到結(jié)果，并準(zhǔn)確的優(yōu)選出最佳結(jié)果具有重要的意義。其次，LINGO聚類算法可以通過利用奇異值分解的方法獲取取文檔集合的抽象概念，該標(biāo)簽?zāi)軌蜃畲笙薅鹊姆从吵霾煌悇e中的文檔的語(yǔ)義信息，通過準(zhǔn)確的聚類，實(shí)現(xiàn)在LINGO聚類算法的運(yùn)用下的模糊聚類（即一個(gè)文檔能夠同時(shí)出現(xiàn)在多個(gè)相關(guān)的類別中）。同時(shí)，我們也應(yīng)該看到，在發(fā)展的過程中，由于系統(tǒng)環(huán)境和實(shí)際應(yīng)用環(huán)境的變遷，LINGO聚類算法的發(fā)展也在繼續(xù)，在計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)快速發(fā)展的今天，作為一種優(yōu)秀的算法，LINGO聚類算法也需要不斷的與時(shí)俱進(jìn)，通過不斷的自我完善和修補(bǔ)獲得更好的用戶體驗(yàn)，具體而言，目前LINGO聚類算法的發(fā)展中主要存在的最主要的的缺點(diǎn)和不足就是，在LINGO聚類算法中，詞權(quán)重公式采用了傳統(tǒng)的TFIDF，這種情況不能充分的考慮并照顧到不同的詞性因素與位置因素，也正因?yàn)槿绱耍琇INGO聚類算法中LINGO形成的聚類缺乏層次關(guān)系。這也是我們?cè)诒舅阉饕嫦到y(tǒng)的設(shè)計(jì)中需要重點(diǎn)關(guān)注和克服的問題之一。總體而言，LINGO聚類算法還是優(yōu)點(diǎn)多于缺點(diǎn)的，具體在系統(tǒng)的應(yīng)用中，還需要我們根據(jù)不同的情況，結(jié)合實(shí)際中遇到的問題，對(duì)出現(xiàn)的新情況、新問題進(jìn)行重點(diǎn)解決和集中克服，力爭(zhēng)揚(yáng)長(zhǎng)避短，用好LINGO聚類算法服務(wù)我們的“妙搜”系統(tǒng)。 本章小結(jié)在本章中，我們對(duì)文本聚類的概念進(jìn)行了集中的介紹，重點(diǎn)從文本聚類中的重要方法，LINGO聚類算法進(jìn)行了闡述，并對(duì)LINGO聚類算法的全過程，包括運(yùn)行的計(jì)算過程中的每一個(gè)步驟進(jìn)行了詳細(xì)的介紹，并對(duì)LINGO聚類算法的優(yōu)點(diǎn)和存在的不足進(jìn)行了分別的描述，通過以上對(duì)LINGO聚類算法的全面詳盡的介紹，從理論上論證搜索引擎系統(tǒng)所需要應(yīng)用的基礎(chǔ)理論，從而將移動(dòng)環(huán)境下搜索引擎技術(shù)所涉及的相關(guān)原理和技術(shù)理論進(jìn)行了一個(gè)全面的介紹，從下一章開始，我們將對(duì)本文中的重點(diǎn)內(nèi)容：“妙搜”移動(dòng)搜索引擎項(xiàng)目進(jìn)行闡述和介紹，行文的體例將從“妙搜”移動(dòng)搜索引擎項(xiàng)目的需求分析入手。第4章 妙搜移動(dòng)搜索引擎系統(tǒng)的需求分析 前文我們用了一定的篇幅對(duì)當(dāng)前實(shí)際應(yīng)用中，移動(dòng)環(huán)境下搜索引擎技術(shù)的發(fā)展及其相關(guān)基礎(chǔ)技術(shù)和理論進(jìn)行了介紹，特別是結(jié)合移動(dòng)互聯(lián)網(wǎng)中搜索引擎技術(shù)的關(guān)鍵性、核心技術(shù)進(jìn)行了闡述，將包括索引、中文分詞、查詢倒排技術(shù)以及文本聚類等技術(shù)理論進(jìn)行了分別的敘述，本章重點(diǎn)在前面的基礎(chǔ)上，介紹本文中的重點(diǎn)內(nèi)容：“妙搜”移動(dòng)搜索引擎項(xiàng)目的系統(tǒng)設(shè)計(jì)背景、系統(tǒng)所要實(shí)現(xiàn)的目標(biāo)以及系統(tǒng)的具體結(jié)構(gòu)和性能等方面，展開進(jìn)行深入的分析。 “妙搜”移動(dòng)搜索引擎項(xiàng)目的研究，主要的背景是目前互聯(lián)網(wǎng)技術(shù)發(fā)展的大背景下，以手機(jī)、平板電腦為代表的移動(dòng)客戶端發(fā)展速度迅猛，成為移動(dòng)互聯(lián)網(wǎng)發(fā)展的重要硬件依托，而從軟件方面來看，目前移動(dòng)互聯(lián)網(wǎng)在軟件發(fā)展方面還相對(duì)滯后，發(fā)展移動(dòng)環(huán)境下的互聯(lián)網(wǎng)搜索引擎技術(shù)大有可為，筆者結(jié)合自身的工作實(shí)際認(rèn)識(shí)到，在移動(dòng)環(huán)境下的互聯(lián)網(wǎng)發(fā)展中，進(jìn)行照搬照抄原有的互聯(lián)網(wǎng)搜索引擎技術(shù)服務(wù)是行不通的，因?yàn)槭謾C(jī)設(shè)備用戶對(duì)移動(dòng)環(huán)境下的互聯(lián)網(wǎng)搜索引擎技術(shù)有著差異化的需求，正是這種需求，成為本文開發(fā)“妙搜”移動(dòng)搜索引擎項(xiàng)目的動(dòng)力和靈感源泉，本文試圖以“妙搜”移動(dòng)搜索引擎項(xiàng)目的基礎(chǔ)，在充分借鑒前人理論成果的基礎(chǔ)上，深入發(fā)掘移動(dòng)環(huán)境下的互聯(lián)網(wǎng)搜索引擎技術(shù)的發(fā)展方向，力求開發(fā)出一整套能夠針對(duì)移動(dòng)互聯(lián)網(wǎng)終端的、適合移動(dòng)用戶使用的移動(dòng)環(huán)境下互聯(lián)網(wǎng)搜索引擎服務(wù)系統(tǒng)。區(qū)別于傳統(tǒng)的PC端互聯(lián)網(wǎng)技術(shù)，移動(dòng)環(huán)境下的互聯(lián)網(wǎng)技術(shù)發(fā)展，在當(dāng)今互聯(lián)網(wǎng)時(shí)代信息技術(shù)和計(jì)算機(jī)技術(shù)飛速發(fā)展的今天，呈現(xiàn)出與以往互聯(lián)網(wǎng)發(fā)展完全不同的新特點(diǎn)，在這樣的基礎(chǔ)上，我們認(rèn)識(shí)到，作為傳統(tǒng)互聯(lián)網(wǎng)服務(wù)領(lǐng)域使用最多的搜索引擎服務(wù)，目前在國(guó)內(nèi)市場(chǎng)上，針對(duì)漢語(yǔ)特點(diǎn)和移動(dòng)環(huán)境下互聯(lián)網(wǎng)發(fā)展規(guī)律的搜索引擎還鳳毛麟角，現(xiàn)有的搜索引擎技術(shù)大多是對(duì)PC端的互聯(lián)網(wǎng)搜索引擎技術(shù)進(jìn)行照搬照抄，完全沒有根據(jù)移動(dòng)環(huán)境下的互聯(lián)網(wǎng)用戶的特點(diǎn)和需求進(jìn)行差異化發(fā)展，據(jù)此，筆者在結(jié)合自身工作、學(xué)習(xí)的基礎(chǔ)上，機(jī)會(huì)設(shè)計(jì)在移動(dòng)環(huán)境下的互聯(lián)網(wǎng)搜索引擎服務(wù)系統(tǒng)：“妙搜”移動(dòng)搜索引擎。這套移動(dòng)搜索引擎系統(tǒng)的設(shè)計(jì)中，最大限度的考慮到移動(dòng)環(huán)境下互聯(lián)網(wǎng)用戶的需求和體驗(yàn)，是為移動(dòng)環(huán)境下互聯(lián)網(wǎng)用戶量身訂做的一套互聯(lián)網(wǎng)搜索引擎服務(wù)系統(tǒng)。首先