Web文本挖掘技術(shù)研究

鈴兒響叮當(dāng) 2006-06-02

展開全文

王繼成　潘金貴　張福炎

關(guān)鍵詞　Web挖掘，文本挖掘，文本分類，文本聚類，多維文本分析
中圖法分類號(hào)　TP391； TP393

RESEARCH ON WEB TEXT MINING

WANG Ji-Cheng, PAN Jin-Gui, and ZHANG Fu-Yan
(Department of Computer Science and Technology, Nanjing University, Nanjing 210093)
(State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093)

Abstract　With the flood of information on the Web, Web mining is a new research issue which draws great interest from many communities. Currently, there is no agreement about Web mining yet. It needs more discussion among scientists in order to define what it is exactly. Meanwhile, the development of Web mining system will promote its research in turn. In this paper, a systemic discussion about the principle of Web mining is presented, including the definition, the relationship between information mining and retrieval on the Web, the taxonomy and function. Then the methods of text mining on the Web are discussed in detail and a prototype of Web text mining system WebMiner is introduced. WebMiner is a multi-agent system which combines text mining and multi-dimension text analysis in order to help user in mining HTML documents on the Web efficiently and effectively.
Key words　Web mining, text mining, text categorization, text clustering, multi-dimension text analysis

1　引言

　　在Web迅猛發(fā)展的同時(shí)，我們不能忽視“信息爆炸”的問題，即信息極大豐富而知識(shí)相對(duì)匱乏.據(jù)估計(jì)，Web已經(jīng)發(fā)展成為擁有3億頁面的分布式信息空間，而且這個(gè)數(shù)字仍以每4至6個(gè)月翻一倍的速度增加^［1］.在這些大量、異質(zhì)的Web信息資源中，蘊(yùn)含著具有巨大潛在價(jià)值的知識(shí).人們迫切需要能夠從Web上快速、有效地發(fā)現(xiàn)資源和知識(shí)的工具.Web上的搜索引擎部分地解決了資源發(fā)現(xiàn)問題，但由于精確度不高等原因，其效果遠(yuǎn)不能使人滿意.此外，搜索引擎的目的在于發(fā)現(xiàn)Web上的資源，就Web上的知識(shí)發(fā)現(xiàn)而言，即使檢索精度再高，搜索引擎也不能夠勝任.為此，我們需要開發(fā)比信息檢索層次更高的新技術(shù).為了從大量數(shù)據(jù)的集合中發(fā)現(xiàn)有效、新穎、有用、可理解的模式，數(shù)據(jù)庫領(lǐng)域采用了數(shù)據(jù)挖掘技術(shù)^［2］.但是，數(shù)據(jù)挖掘的絕大部分工作所涉及的是結(jié)構(gòu)化數(shù)據(jù)庫，很少有處理Web上的異質(zhì)、非結(jié)構(gòu)化信息的工作.Web挖掘作為數(shù)據(jù)挖掘的一個(gè)新主題，引起了人們的極大興趣.同時(shí)，它也是一個(gè)富于爭(zhēng)議的研究方向.目前，對(duì)于Web挖掘的含義、功能等尚無統(tǒng)一的結(jié)論，需要國(guó)內(nèi)外學(xué)者在理論上開展更多的討論以進(jìn)行精確地定義.此外，Web挖掘系統(tǒng)的開發(fā)對(duì)其研究也將起到很大推進(jìn)作用.
　　在本文中，我們對(duì)Web挖掘技術(shù)作了系統(tǒng)性的研究.給出了Web挖掘的定義，討論了Web挖掘與傳統(tǒng)的數(shù)據(jù)挖掘以及Web信息檢索之間的關(guān)系；對(duì)Web挖掘的任務(wù)進(jìn)行了分類，重點(diǎn)討論了Web文本挖掘和結(jié)構(gòu)挖掘的功能；分析了Web文本挖掘的方法，包括文本的特征表示、文本分類和文本聚類.最后，簡(jiǎn)單介紹了我們?cè)O(shè)計(jì)的一個(gè)Web文檔挖掘系統(tǒng)原型WebMiner.

2　Web挖掘與Web信息檢索

2.1　Web挖掘的定義

　　Web挖掘是一項(xiàng)綜合技術(shù)，涉及Web、數(shù)據(jù)挖掘、計(jì)算機(jī)語言學(xué)、信息學(xué)等多個(gè)領(lǐng)域.不同研究者從自身的領(lǐng)域出發(fā)，對(duì)Web挖掘的含義有著不同的理解，項(xiàng)目開發(fā)也各有其側(cè)重點(diǎn).例如，有些計(jì)算機(jī)語言學(xué)家認(rèn)為，Web文檔為自然語言理解提供了豐富的語料，可以從中自動(dòng)地學(xué)習(xí)詞語的意義，以進(jìn)行詞義辨析或確定詞語所屬的概念^［3］.我們從更為一般的角度出發(fā)，對(duì)Web挖掘作如下定義.
　　定義1. Web挖掘是指從大量Web文檔的集合C中發(fā)現(xiàn)隱含的模式p.如果將C看作輸入，將p看作輸出，那么Web挖掘的過程就是從輸入到輸出的一個(gè)映射ξ: C→p.
　　Web挖掘從數(shù)據(jù)挖掘發(fā)展而來，因此其定義與我們熟知的數(shù)據(jù)挖掘定義^［2］相類似.但是，Web挖掘與傳統(tǒng)的數(shù)據(jù)挖掘相比有許多獨(dú)特之處.首先，Web挖掘的對(duì)象是大量、異質(zhì)、分布的Web文檔.我們認(rèn)為，以Web作為中間件對(duì)數(shù)據(jù)庫進(jìn)行挖掘，以及對(duì)Web服務(wù)器上的日志、用戶信息等數(shù)據(jù)所開展的挖掘工作，仍屬于傳統(tǒng)的數(shù)據(jù)挖掘的范疇.其次，Web在邏輯上是一個(gè)由文檔節(jié)點(diǎn)和超鏈構(gòu)成的圖，因此Web挖掘所得到的模式可能是關(guān)于Web內(nèi)容的，也可能是關(guān)于Web結(jié)構(gòu)的.此外，由于Web文檔本身是半結(jié)構(gòu)化或無結(jié)構(gòu)的，且缺乏機(jī)器可理解的語義，而數(shù)據(jù)挖掘的對(duì)象局限于數(shù)據(jù)庫中的結(jié)構(gòu)化數(shù)據(jù)，并利用關(guān)系表格等存儲(chǔ)結(jié)構(gòu)來發(fā)現(xiàn)知識(shí)，因此有些數(shù)據(jù)挖掘技術(shù)并不適用于Web挖掘，即使可用也需要建立在對(duì)Web文檔進(jìn)行預(yù)處理的基礎(chǔ)之上.這樣，開發(fā)新的Web挖掘技術(shù)，以及對(duì)Web文檔進(jìn)行預(yù)處理以得到關(guān)于文檔的特征表示，便成為Web挖掘研究的重點(diǎn).

2.2　Web信息檢索的定義

　　定義2. Web信息檢索，是指從大量Web文檔的集合C中找到與給定的查詢請(qǐng)求q相關(guān)的、恰當(dāng)數(shù)目的文檔子集S.Web信息檢索的過程也對(duì)應(yīng)于一個(gè)映射ζ：(C, q)→S.
　　從60年代以來，信息檢索領(lǐng)域在索引模型、文檔內(nèi)容表示、匹配策略等方面取得了許多研究成果.這些成果被成功地應(yīng)用在Web上，產(chǎn)生了搜索引擎，例如Yahoo!，Alta-vista等.搜索引擎工作的一般流程包括：使用Robot搜集Web文檔、對(duì)文檔集合建立倒排索引、分析用戶的查詢請(qǐng)求、匹配文檔與查詢請(qǐng)求以計(jì)算二者之間的相似度、對(duì)查詢結(jié)果進(jìn)行排序以及用戶相關(guān)度回饋^［4］.

2.3　Web上的挖掘與信息檢索

　　Web上的挖掘和信息檢索是兩種不同的技術(shù)，其區(qū)別主要表現(xiàn)在以下幾個(gè)方面.
　　(1) 方法論不同. 信息檢索是目標(biāo)驅(qū)動(dòng)的，用戶需要明確提出查詢要求；而挖掘是機(jī)會(huì)主義的，其結(jié)果獨(dú)立于用戶的信息需求，也是用戶所無法預(yù)知的；
　　(2) 著眼點(diǎn)不同. 信息檢索著重于文檔中顯式存儲(chǔ)的字詞和鏈接；而挖掘試圖更多地理解其內(nèi)容和結(jié)構(gòu)；
　　(3) 目的不同. 信息檢索的目的在于幫助用戶發(fā)現(xiàn)資源，即從大量文檔中找到滿足其查詢請(qǐng)求的文檔子集；而挖掘是為了揭示文檔中隱含的知識(shí)；
　　(4) 評(píng)價(jià)方法不同. 信息檢索使用精度（precision）和召回率（recall）來評(píng)價(jià)其性能，要求返回盡可能多的相關(guān)文檔，同時(shí)不相關(guān)的文檔盡可能少.而挖掘采用收益（gain）、置信度（certainty）、簡(jiǎn)潔性（simplicity）等來衡量所發(fā)現(xiàn)知識(shí)的有效性、可用性和可理解性；
　　(5) 使用場(chǎng)合不同. 有時(shí)信息檢索系統(tǒng)返回太多的結(jié)果以致用戶無法一一瀏覽，有時(shí)用戶沒有明確的信息需求，有時(shí)用戶希望發(fā)現(xiàn)文檔集合中所具有的結(jié)構(gòu)、趨勢(shì)、含義，在這些場(chǎng)合下，就需要使用挖掘技術(shù).
　　盡管Web挖掘是比信息檢索層次更高的技術(shù)，但它并不是用來取代信息檢索技術(shù)，二者是相輔相成的.一方面，這兩種技術(shù)各有所長(zhǎng)，有各自適用的場(chǎng)合；另一方面，我們可以利用Web挖掘的研究成果來提高信息檢索的精度和效率，改善檢索結(jié)果的組織，使信息檢索系統(tǒng)發(fā)展到一個(gè)新的水平.

3　Web挖掘的任務(wù)

3.1　Web挖掘任務(wù)的分類

　　在邏輯上，我們可以把Web看作是位于物理網(wǎng)絡(luò)之上的一個(gè)有向圖G=(N, E)，其中節(jié)點(diǎn)集N對(duì)應(yīng)于Web上的所有文檔，而有向邊集E則對(duì)應(yīng)于節(jié)點(diǎn)之間的超鏈.對(duì)節(jié)點(diǎn)集作進(jìn)一步的劃分，N={N_l, N_nl}.所有的非葉節(jié)點(diǎn)N_nl是HTML文檔，其中除了包含文本以外，還包含了標(biāo)記以指定文檔的屬性和內(nèi)部結(jié)構(gòu)，或者嵌入了超鏈以表示文檔間的結(jié)構(gòu)關(guān)系.葉節(jié)點(diǎn)N_l可以是HTML文檔，也可以是其它格式的文檔，例如PostScript等文本文件，以及圖形、音頻等媒體文件.如圖1所示.N中每個(gè)節(jié)點(diǎn)都有一個(gè)URL，其中包含了關(guān)于該節(jié)點(diǎn)所位于的Web站點(diǎn)和目錄路徑的結(jié)構(gòu)信息.
　　Web上信息的多樣性決定了Web挖掘任務(wù)的多樣性.按照處理對(duì)象的不同，我們將Web挖掘分為兩大類：內(nèi)容挖掘和結(jié)構(gòu)挖掘.前者指的是從Web文檔的內(nèi)容信息中抽取知識(shí)，而后者指的是從Web文檔的結(jié)構(gòu)信息中推導(dǎo)知識(shí).Web內(nèi)容挖掘又分為對(duì)文本文檔（包括text，HTML等格式）和多媒體文檔（包括image，audio，video等媒體類型）的挖掘.Web結(jié)構(gòu)挖掘不僅僅局限于文檔之間的超鏈結(jié)構(gòu)，還包括文檔內(nèi)部的結(jié)構(gòu)、文檔URL中的目錄路徑結(jié)構(gòu)等.如圖2所示.在本文中，我們僅對(duì)Web上的文本挖掘和結(jié)構(gòu)挖掘加以討論，下文中提及的“文檔”指的是文本文檔，不包括多媒體文檔.有關(guān)Web上的多媒體挖掘，感興趣的讀者可以參見文獻(xiàn)［5］，其中介紹了一個(gè)簡(jiǎn)單的Web多媒體挖掘系統(tǒng)原型.

圖1　Web的邏輯結(jié)構(gòu)

圖2　Web挖掘的分類

3.2　Web文本挖掘

　　Web文本挖掘可以對(duì)Web上大量文檔集合的內(nèi)容進(jìn)行總結(jié)、分類、聚類、關(guān)聯(lián)分析，以及利用Web文檔進(jìn)行趨勢(shì)預(yù)測(cè)等.
　　文本總結(jié)是指從文檔中抽取關(guān)鍵信息，用簡(jiǎn)潔的形式對(duì)文檔內(nèi)容進(jìn)行摘要或解釋.這樣，用戶不需要瀏覽全文就可以了解文檔或文檔集合的總體內(nèi)容.文本總結(jié)在有些場(chǎng)合十分有用，例如，搜索引擎在向用戶返回查詢結(jié)果時(shí)，通常需要給出文檔的摘要.目前，絕大部分搜索引擎采用的方法是簡(jiǎn)單地截取文檔的前幾行.文獻(xiàn)［6］提出了使用中心文檔來代表文檔集合，使用中心詞匯來表示文檔的方法，并給出了求取中心文檔和中心詞匯的算法.
　　文本分類是指按照預(yù)先定義的主題類別，為文檔集合中的每個(gè)文檔確定一個(gè)類別.這樣，用戶不但能夠方便地瀏覽文檔，而且可以通過限制搜索范圍來使文檔的查找更為容易.目前，Yahoo!通過人工來對(duì)Web上的文檔進(jìn)行分類，這大大影響了索引的頁面數(shù)目（Yahoo! 索引的覆蓋范圍遠(yuǎn)遠(yuǎn)小于Alta-vista等搜索引擎）.利用文本分類技術(shù)可以對(duì)大量文檔進(jìn)行快速、有效地自動(dòng)分類.目前，文本分類的算法有很多種，比較常用的有TFIDF^［7］和Naive Bayes^［8］等方法.
　　文本聚類與分類的不同之處在于，聚類沒有預(yù)先定義好的主題類別，它的目標(biāo)是將文檔集合分成若干個(gè)簇，要求同一簇內(nèi)文檔內(nèi)容的相似度盡可能地大，而不同簇間的相似度盡可能地小.Hearst等人的研究已經(jīng)證明了“聚類假設(shè)”，即與用戶查詢相關(guān)的文檔通常會(huì)聚類得比較靠近，而遠(yuǎn)離與用戶查詢不相關(guān)的文檔^［9］.因此，我們可以利用文本聚類技術(shù)將搜索引擎的檢索結(jié)果劃分為若干個(gè)簇，用戶只需要考慮那些相關(guān)的簇，大大縮小了所需要瀏覽的結(jié)果數(shù)量.目前，有多種文本聚類算法，大致可以分為兩種類型：以G-HAC等算法為代表的層次凝聚法^［10］，以k-means等算法為代表的平面劃分法^［11］.文獻(xiàn)［12］介紹了將G-HAC和k-means集合起來的Buckshot方法和Fractionation方法.
　　關(guān)聯(lián)分析是指從文檔集合中找出不同詞語之間的關(guān)系.Brin提出了一種從大量文檔中發(fā)現(xiàn)一對(duì)詞語出現(xiàn)模式的算法，并用來在Web上尋找作者和書名的出現(xiàn)模式，從而發(fā)現(xiàn)了數(shù)千本在Amazon網(wǎng)站上找不到的新書籍^［13］.Wang等人以Web上的電影介紹作為測(cè)試文檔，通過使用OEM模型從這些半結(jié)構(gòu)化的頁面中抽取詞語項(xiàng)，進(jìn)而得到一些關(guān)于電影名稱、導(dǎo)演、演員、編劇的出現(xiàn)模式^［14］.
　　分布分析與趨勢(shì)預(yù)測(cè)是指通過對(duì)Web文檔的分析，得到特定數(shù)據(jù)在某個(gè)歷史時(shí)刻的情況或?qū)淼娜≈第厔?shì).Feldman等人使用多種分布模型對(duì)路透社的兩萬多篇新聞進(jìn)行了挖掘，得到主題、國(guó)家、組織、人、股票交易之間的相對(duì)分布，揭示了一些有趣的趨勢(shì)^［15］.Wüthrich等人通過分析Web上出版的權(quán)威性經(jīng)濟(jì)文章，對(duì)每天的股票市場(chǎng)指數(shù)進(jìn)行預(yù)測(cè)，取得了良好的效果^［16］.
　　需要說明的是，Web上的文本挖掘和通常的平面文本挖掘的功能和方法比較類似，但是，Web文檔中的標(biāo)記，例如〈Title〉，〈Heading〉等蘊(yùn)含了額外的信息，我們可以利用這些信息來提高Web文本挖掘的性能.

3.3　Web結(jié)構(gòu)挖掘

　　由于Web中包含的結(jié)構(gòu)信息處理起來比較困難，因此通常的Web搜索引擎等工具僅將Web看作是一個(gè)平面文檔的集合，而忽略了其中的結(jié)構(gòu)信息.Web結(jié)構(gòu)挖掘的目的在于揭示蘊(yùn)含在這些文檔結(jié)構(gòu)信息中的有用模式.
　　文檔之間的超鏈反映了文檔間的某種聯(lián)系，例如包含、從屬等.超鏈中的標(biāo)記文本（anchor）對(duì)鏈宿頁面也起到了概括作用，這種概括在一定程度上比鏈宿頁面作者所作的概括（頁面的標(biāo)題）要更為客觀、準(zhǔn)確.Craven等人使用一階學(xué)習(xí)方法對(duì)Web頁面間的超鏈類型進(jìn)行分類，以判斷頁面間的members-of-project，department-of-persons等關(guān)系；同時(shí)，他們還利用超鏈中的標(biāo)記文本對(duì)鏈宿頁面進(jìn)行分類，取得了較好的效果^［17］.超鏈還反映了文檔間的引用關(guān)系，一個(gè)頁面被引用的次數(shù)體現(xiàn)了該頁面的重要性.Brin等人通過綜合考慮頁面的引用次數(shù)和鏈源頁面的重要性來判斷鏈宿頁面的重要性，從而設(shè)計(jì)出能夠查詢與用戶請(qǐng)求相關(guān)的“權(quán)威”頁面的搜索引擎^［18］.
　　每個(gè)Web頁面并不是原子對(duì)象，其內(nèi)部有或多或少的結(jié)構(gòu).Spertus對(duì)Web頁面的內(nèi)部結(jié)構(gòu)作了研究，提出了一些啟發(fā)式規(guī)則，并用于尋找與給定的頁面集合｛P₁，…，P_n｝相關(guān)的其它頁面^［19］.DiPasquo使用HTML結(jié)構(gòu)樹對(duì)Web頁面進(jìn)行分析，得到其內(nèi)部結(jié)構(gòu)特征，從而學(xué)習(xí)公司的名稱和地址等信息在頁面中的出現(xiàn)模式^［20］.
　　Web頁面的URL可能會(huì)反映頁面的類型，也可能會(huì)反映頁面之間的目錄結(jié)構(gòu)關(guān)系.Spertus提出了與Web頁面URL有關(guān)的啟發(fā)式規(guī)則，并用于尋找個(gè)人主頁，或者尋找改變了位置的Web頁面的新位置^［19］.
　　目前，與Web挖掘有關(guān)的各種項(xiàng)目涉及了上述任務(wù)的某個(gè)方面^{［6～8,10～13,15,16］}，也有一些項(xiàng)目綜合考慮了Web的內(nèi)容和結(jié)構(gòu)因素，將文本挖掘與結(jié)構(gòu)挖掘結(jié)合起來，以取得更好的效果^{［14,17～20］}.盡管與多媒體信息相比，文本信息顯得比較普通，但文本仍然是記載和傳播信息的最主要媒體.此外，文本挖掘又相對(duì)容易取得技術(shù)突破，其中的許多研究成果也可以為多媒體挖掘和結(jié)構(gòu)挖掘所借鑒.因此對(duì)文本挖掘技術(shù)的研究具有十分重要的意義和廣泛的應(yīng)用前景.下面，我們重點(diǎn)對(duì)Web文本挖掘的方法和系統(tǒng)設(shè)計(jì)進(jìn)行討論.

4　Web文本挖掘方法

　　在Web文本挖掘中，文本的特征表示是挖掘工作的基礎(chǔ)，而文本分類和聚類是兩種最重要、最基本的挖掘功能.

4.1　文本的特征表示

　　與數(shù)據(jù)庫中的結(jié)構(gòu)化數(shù)據(jù)相比，Web文檔具有有限的結(jié)構(gòu)，或者根本就沒有結(jié)構(gòu).即使具有一些結(jié)構(gòu)，也是著重于格式，而非文檔內(nèi)容.不同類型文檔的結(jié)構(gòu)也不一致.此外，文檔的內(nèi)容是人類所使用的自然語言，計(jì)算機(jī)很難處理其語義.文本信息源的這些特殊性使得現(xiàn)有的數(shù)據(jù)挖掘技術(shù)無法直接應(yīng)用于其上.我們需要對(duì)文本進(jìn)行預(yù)處理，抽取代表其特征的元數(shù)據(jù).這些特征可以用結(jié)構(gòu)化的形式保存，作為文檔的中間表示形式.
　　文本特征指的是關(guān)于文本的元數(shù)據(jù)，分為描述性特征，例如文本的名稱、日期、大小、類型等；以及語義性特征，例如文本的作者、機(jī)構(gòu)、標(biāo)題、內(nèi)容等.描述性特征易于獲得，而語義性特征則較難得到.W3C近來制定的XML^［21］，RDF^［22］等規(guī)范提供了對(duì)Web文檔資源進(jìn)行描述的語言和框架.在此基礎(chǔ)上，我們可以從半結(jié)構(gòu)化的Web文檔中抽取作者、機(jī)構(gòu)等特征.
　　對(duì)于內(nèi)容這個(gè)難以表示的特征，我們首先要找到一種能夠被計(jì)算機(jī)所處理的表示方法.矢量空間模型（VSM）是近年來應(yīng)用較多且效果較好的方法之一^［23］.在該模型中，文檔空間被看作是由一組正交詞條矢量所張成的矢量空間，每個(gè)文檔d表示為其中的一個(gè)范化特征矢量V(d)=(t₁, w₁(d);…;t_i, w_i(d);…; t_n, w_n(d))，其中t_i為詞條項(xiàng)，w_i(d)為t_i在d中的權(quán)值.可以將d中出現(xiàn)的所有單詞作為t_i，也可以要求t_i是d中出現(xiàn)的所有短語，從而提高內(nèi)容特征表示的準(zhǔn)確性.w_i(d)一般被定義為t_i在d中出現(xiàn)頻率tf_i(d)的函數(shù)，即w_i(d)=Ψ(tf_i(d)). 常用的Ψ有：布爾函數(shù)平方根函數(shù)對(duì)數(shù)函數(shù)Ψ=log(tf_i(d)+1)；TFIDF函數(shù)其中，N為所有文檔的數(shù)目，n_i為含有詞條t_i的文檔數(shù)目.

4.2　文本分類

　　文本分類是一種典型的有教師的機(jī)器學(xué)習(xí)問題，一般分為訓(xùn)練和分類兩個(gè)階段，具體過程如下.
　　訓(xùn)練階段：
　　(1) 定義類別集合C={c₁,…, c_i,…,c_m}，這些類別可以是層次式的，也可以是并列式的；
　　(2) 給出訓(xùn)練文檔集合S={s₁,…,s_j,…,s_n}，每個(gè)訓(xùn)練文檔s_j被標(biāo)上所屬的類別標(biāo)識(shí)c_i；
　　(3) 統(tǒng)計(jì)S中所有文檔的特征矢量V(s_j)，確定代表C中每個(gè)類別的特征矢量V(c_i)；
　　分類階段：
　　(4) 對(duì)于測(cè)試文檔集合T={d₁,…,d_k,…,d_r}中的每個(gè)待分類文檔d_k，計(jì)算其特征矢量V(d_k)與每個(gè)V(c_i)之間的相似度sim(d_k,c_i)；
　　(5) 選取相似度最大的一個(gè)類別作為d_k的類別.
　　有時(shí)也可以為d_k指定多個(gè)類別，只要d_k與這些類別之間的相似度超過某個(gè)預(yù)定的閾值.如果d_k與所有類別的相似度均低于閾值，那么通常將該文檔放在一邊，由用戶來做最終決定.對(duì)于類別與預(yù)定義類別不匹配的文檔而言，這是合理的，也是必須的.如果這種情況經(jīng)常發(fā)生，則說明需要修改預(yù)定義類別，然后重新進(jìn)行上述訓(xùn)練與分類過程.
　　在計(jì)算sim(d_k, c_i)時(shí)，有多種方法可供選擇.最簡(jiǎn)單的方法是僅考慮兩個(gè)特征矢量中所包含的詞條的重疊程度，即其中，n_∩(d_k,c_i)是V(d_k)和V(c_i)具有的相同詞條數(shù)目，n_∪(d_k,c_i)是V(d_k)和V(c_i)具有的所有詞條數(shù)目；最常用的方法是考慮兩個(gè)特征矢量之間的夾角余弦，即sim(d_k, c_i)=

4.3　文本聚類

　　文本聚類是一種典型的無教師的機(jī)器學(xué)習(xí)問題.目前的文本聚類方法大致可以分為層次凝聚法和平面劃分法兩種類型.
　　對(duì)于給定的文檔集合D={d₁,…, d_i,…,d_n}，層次凝聚法的具體過程如下：
　　(1) 將D中的每個(gè)文檔d_i看作是一個(gè)具有單個(gè)成員的簇c_i={d_i}，這些簇構(gòu)成了D的一個(gè)聚類C={c₁,…,c_i,…,c_n}；
　　(2) 計(jì)算C中每對(duì)簇(c_i,c_j)之間的相似度sim(c_i,c_j)；
　　(3) 選取具有最大相似度的簇對(duì)并將c_i和c_j合并為一個(gè)新的簇c_k=c_i∪c_j，從而構(gòu)成了D的一個(gè)新的聚類C={c₁,…,c_n-1}；
　　(4) 重復(fù)上述步驟，直至C中剩下一個(gè)簇為止.
　　該過程構(gòu)造出一棵生成樹，其中包含了簇的層次信息，以及所有簇內(nèi)和簇間的相似度.層次聚類方法是最為常用的聚類方法，它能夠生成層次化的嵌套簇，且準(zhǔn)確度較高.但是，在每次合并時(shí)，需要全局地比較所有簇之間的相似度，并選擇出最佳的兩個(gè)簇，因此運(yùn)行速度較慢，不適合于大量文檔的集合.
　　平面劃分法與層次凝聚法的區(qū)別在于，它將文檔集合水平地分割為若干個(gè)簇，而不是生成層次化的嵌套簇.對(duì)于給定的文檔集合D={d₁,…,d_i,…,d_n}，平面劃分法的具體過程如下.
　?、?確定要生成的簇的數(shù)目k；
　　② 按照某種原則生成k個(gè)聚類中心作為聚類的種子S={s₁,…,s_j,…,s_k}；
　?、?對(duì)D中的每個(gè)文檔d_i，依次計(jì)算它與各個(gè)種子s_j的相似度sim(d_i,s_j)；
　?、?選取具有最大相似度的種子將d_i歸入以s_j為聚類中心的簇c_j，從而得到D的一個(gè)聚類C={c₁,…,c_k}.
　?、?重復(fù)步驟②、③、④若干次，以得到較為穩(wěn)定的聚類結(jié)果.
　　該方法的運(yùn)行速度較快，但是必須事先確定k的取值，且種子選取的好壞對(duì)聚類結(jié)果有較大影響.

5　Web文本挖掘系統(tǒng)原型WebMiner

　　我們?cè)趯?duì)Web挖掘技術(shù)進(jìn)行系統(tǒng)研究的理論基礎(chǔ)之上，設(shè)計(jì)了一個(gè)Web文本挖掘系統(tǒng)原型WebMiner(如圖3所示). WebMiner采用了多agent的體系結(jié)構(gòu)，將多維文本分析與文本挖掘這兩種技術(shù)有機(jī)地結(jié)合起來，以幫助用戶快速、有效地挖掘Web上的HTML文檔.以下給出系統(tǒng)組件和系統(tǒng)行為的簡(jiǎn)要描述.

圖3　Web文本挖掘系統(tǒng)原型WebMiner

5.1　系統(tǒng)組件

5.2　系統(tǒng)行為

　　用戶通過與系統(tǒng)中各個(gè)組件進(jìn)行交互來實(shí)現(xiàn)Web文本挖掘的全過程.首先，用戶給出搜集策略（例如，起始URL列表、指定主題或者網(wǎng)絡(luò)域等）以指導(dǎo)文本搜集agent進(jìn)行Web文檔的搜集.然后，文本預(yù)處理agent從搜集到的Web文檔中抽取描述性特征和語義性特征.此后，用戶有多種方案供選擇，包括：使用多維分析引擎對(duì)文檔特征進(jìn)行多維分析，得到多維文檔視圖（每個(gè)視圖對(duì)應(yīng)于文檔集合的一個(gè)子集）；按照預(yù)定義的類別層次，對(duì)文檔集合（或者其中的部分子集）的內(nèi)容進(jìn)行分類；當(dāng)預(yù)定義的類別層次與文檔集合的內(nèi)在層次不符合時(shí)，用戶可以修改或重新創(chuàng)建文本分類agent的預(yù)定義類別層次和訓(xùn)練文檔，或者利用文本聚類agent對(duì)文檔集合進(jìn)行聚類得到文檔簇；由于簇也是文檔的集合，因此，當(dāng)用戶對(duì)某個(gè)簇感興趣，而這個(gè)簇中又包含很多文檔時(shí)，可以再次使用文本聚類agent將簇進(jìn)一步劃分為子簇，直到每個(gè)簇中包含的文檔數(shù)目適中為止.用戶與系統(tǒng)的交互存在多次反復(fù)，直到獲得滿意的結(jié)果為止.

6　結(jié)束語

　　在Web信息充斥的情況下，Web挖掘是一個(gè)具有極大潛力的研究方向.一些國(guó)際會(huì)議，例如KDD‘97、IJCAI‘99等，已經(jīng)或即將舉行有關(guān)Web挖掘的專題討論，對(duì)其理論、體系結(jié)構(gòu)、算法等展開研究.本文對(duì)Web挖掘的定義、任務(wù)、功能作了系統(tǒng)性的研究，著重分析了Web文本挖掘的方法，并設(shè)計(jì)了一個(gè)Web文本挖掘系統(tǒng)原型WebMiner.在該領(lǐng)域仍有許多問題值得探討，包括：適用于大規(guī)模文檔集合的有效算法，利用XML規(guī)范對(duì)Web文檔元數(shù)據(jù)進(jìn)行描述和抽取，設(shè)計(jì)更多的Web挖掘部件以豐富WebMiner的功能等，這些將是我們下一步研究要解決的問題.

王繼成，男，1973年生，博士研究生，研究方向?yàn)樾畔z索與挖掘.
潘金貴，男，1952年生，教授，研究方向?yàn)橹虚g件、agent技術(shù).
張福炎，男，1939年生，教授，博士生導(dǎo)師，研究方向?yàn)閿?shù)字化圖書館、多媒體技術(shù).
王繼成（南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系　南京　210093）
（南京大學(xué)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室　南京　210093）
潘金貴（南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系　南京　210093）
（南京大學(xué)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室　南京　210093）
張福炎（南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系　南京　210093）
（南京大學(xué)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室　南京　210093）

參考文獻(xiàn)

1，Lawrence S et al. Searching the World Wide Web. Science, 1998, 280(5360): 98～100
2，F(xiàn)ayyad U et al. The KDD process for extracting useful knowledge from volumes of data. Communications of the ACM, 1996, 39(11): 27～34
3，Hahn U, Schnattinger K. Deep knowledge discovery from natural language texts. In: Proc of the 3rd Int‘l Conf on Knowledge Discovery and Data Mining. Newport Beach, 1997. 175～178
4，Gudivada V N et al. Information retrieval on the World Wide Web. IEEE Internet Computing, 1997, 1(5): 58～68
5，Zaïane O R, Han J et al. MultiMedia-miner: A system prototype for multimedia data mining. In: Proc of 1998 ACM-SIGMOD Conf on Management of Data. Seattle, 1998. 581～583
6，Pirolli P, Schank P et al. Scatter/gather browsing communicates the topic structure of a very large text collection. In: Proc of the ACM SIGCHI Conf on Human Factors in Computing Systems. 1996. http://www./sigs/sigchi/chi96/proceedings/papers/pirolli/pp-txt.htm
7，鄒濤, 王繼成等. 基于WWW的資料搜集系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn). 情報(bào)學(xué)報(bào), 1999, 18(3): 195～201
，　(Zou Tao, Wang Jicheng et al. The design and implementation of an information gathering system on the Web. Journal of the China Society for Scientific and Technical Information(in Chinese), 1999, 18(3): 195～201)
8，Choon Yang Quek. Classification of world wide web documents ［Senior Honors dissertation］. School of Computer Science, Camegie Mellon University, 1997
9，Hearst M A, Pedersen J. Reexamining the cluster hypothesis: Scatter/gather on retrieval results. In: Proc of the 19th Annual Int‘l ACM/SIGIR Conf. Zurich, 1996. 76～84
10，Willet P. Recent trends in hierarchical document clustering: A critical review. Information Processing and Management, 1988, 24: 577～597
11，Rocchio J J. Document retrieval systems——Optimization and evaluation ［Ph D dissertation］. Harvard University, Cambridge, MA, 1966
12，Cutting D et al. Scatter/gather: A cluster-based approach to browsing large document collections. In: Proc of the 15th Annual Int‘l ACM/SIGIR Conf. Copenhagen, 1992. 318～329
13，Brin S. Extracting patterns and relations from the World Wide Web. In: Proc of WebDB Workshop at EDBT‘98. Valencia, 1998
14，Wang Ke, Liu Huiqing. Schema discovery from semi-structured data. In: Proc of the 3rd Int‘l Conf on Knowledge Discovery and Data Mining. Newport Beach, 1997
15，F(xiàn)eldman R, Dagan I. Knowledge discovery in textual databases(KDT). In: Proc of the 1st Int‘l Conf on Knowledge Discovery. Montreal, 1995. 112～117
16，Wüthrich B, Permunetilleke D, Leung S et al. Daily prediction of major stock indices from textual WWW data. In: Proc of the 4th Int‘l Conf on Knowledge Discovery. New York, 1998
17，Craven M, Slattery S, Nigam K. First-order learning for Web mining. In: Proc of the 10th European Conf on Machine Learning. Chemnitz, 1998
18，Brin S et al. The anatomy of large-scale hypertextual web search engine. In: Proc of the Seventh Int‘l World Wide Web Conf. 1998. http://decweb./www7/1921/com1921.htm
19，Spertus E. ParaSite: Mining structural information on the web. In: Proc of the Sixth Int‘l World Wide Web Conf. 1997. http://decweb./www6/Technical/paper206/paper206.html
20，DiPasquo D. Using HTML formatting to aid in natural language processing on the World Wide Web ［Senior Honors dissertation］. School of Computer Science, Canegie Mellon University, 1998
21，Bray T, Paoli J, Sperberg-McQueen C M. Extensible Markup Language (XML) 1.0 specification. World Wide Web Consortium Recommendation. 1998. http://www./TR/REC-xml/
22，Lassila O, Swick R R. Resource Description Framework(RDF) Model and Syntax Specification. World Wide Web Consortium Recommendation. 1999. http://www./TR/REC-rdf-syntax/
23，Salton G, Wong A, Yang C S. A vector space model for automatic indexing. Communications of the ACM, 1975, 18(5): 613～620

　　原稿收到日期：1999-05-11；修改稿收到日期：2000-01-26.

本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。

小男孩‘自慰网亚洲一区二区,亚洲一级在线播放毛片,亚洲中文字幕av每天更新,黄aⅴ永久免费无码,91成人午夜在线精品,色网站免费在线观看,亚洲欧洲wwwww在线观看

Web文本挖掘技術(shù)研究