在迅猛增加的海量異構(gòu)的Web信息資源中，蘊含著巨大潛在價值的數(shù)據(jù)。如何從浩如煙海的Web資源中發(fā)現(xiàn)潛在有價值的知識成為迫在眉睫的問題。人們迫切需要能從Web上快速、有效地發(fā)現(xiàn)資源和數(shù)據(jù)的工具，以提高在Web上檢索信息、利用信息的效率。

目前Web文本挖掘大部分研究都是建立在詞匯袋(bag of words)或稱向量表示法(Vector Representation)的基礎(chǔ)上，這種方法將單個的詞匯看成文檔集合中的屬性，只從統(tǒng)計的角度將詞匯孤立地看待而忽略該詞匯出現(xiàn)的位置和上下文環(huán)境。詞匯袋方法的一個弊端是自由文本中的數(shù)據(jù)豐富，詞匯量非常大，處理起來很困難，為解決這個問題人們做了相應(yīng)的研究，采取了不同技術(shù)，如信息增益，交叉熵、差異比等，其目的都是為了減少屬性。一個比較有意義的方法是潛在語義索引(Latent Semantic Indexing)，它通過分析不同文檔中相同主題的共享詞匯，找到它們共同的根，用這個公共的根代替所有詞匯，以此來減少維空間。其它的屬性表示法還有詞匯在文檔中的出現(xiàn)位置、層次關(guān)系、使用短語、使用術(shù)語、命名實體等，目前還沒有研究表明一種表示法明顯優(yōu)于另一種。

圖1 文本聚類模型

本文所提出的挖掘技術(shù)，不是基于詞匯屬性，而是文本塊。在利用網(wǎng)頁的標簽樹結(jié)構(gòu)的基礎(chǔ)上，提取標題和文本塊生成SHA-1指紋序列，如果兩個頁面具有的相同的指紋塊在我們所設(shè)定的范圍內(nèi)，那么就把這兩個頁面歸為一類，類值就是所要聚類的準確數(shù)目k，接下來用k-means進行文本聚類，達到文本挖掘的目的[2][3]。圖1是文本聚類模型。

文本預(yù)處理

◆網(wǎng)頁凈化

由于Web文本上存在大量的廣告、html標簽、相關(guān)鏈接等無用信息，所以首先要對所收集到的網(wǎng)頁進行凈化處理，也稱為網(wǎng)頁去噪，以提高聚類效果。我們把網(wǎng)頁設(shè)計者為了輔助網(wǎng)站組織而增加的文字定義為“噪聲”，把原本要表達的文字素材稱為“主題內(nèi)容”。 這些噪音是與頁面主題無關(guān)(即瀏覽者不關(guān)心)的區(qū)域及項，包括廣告欄、導(dǎo)航條、修飾成分等。

這樣，我們對HTML源碼進行分析，根據(jù)起分隔作用的標記去掉噪音部分，提取出網(wǎng)頁正文[4]。

◆生成SHA-1指紋

SHA的全稱是Secure Hash Algorithm，即安全哈希算法。它是由美國國家標準和技術(shù)協(xié)會(NIST)開發(fā)，于1993年作為聯(lián)邦信息處理標準(FIPS PUB 180)公布。1995年又發(fā)布了一個修訂版FIPS PUB 180-1，通常稱之為SHA-1?，F(xiàn)在已成為公認的最安全的散列算法之一，并被廣泛使用。該算法的思想是接收一段明文，然后以一種不可逆的方式將它轉(zhuǎn)換成一段(通常更小)密文，也可以簡單的理解為取一串輸入碼(稱為預(yù)映射或信息)，并把它們轉(zhuǎn)化為長度較短、位數(shù)固定的輸出序列即散列值(也稱為信息摘要或信息認證代碼)的過程[5]。

由于sha-1算法的雪崩效應(yīng)，對文本塊作信息摘要時，要消除文本塊中的不可見字符，而文本塊排序是為了降低算法的復(fù)雜度。對于凈化后的文本塊，通過格式分析生成M個文本塊B1，B2，…BM(文本塊按重要性排序)，取前m(≤ M)個文本塊生成sha-1指紋sha-11，sha-12，…sha-1m。對于網(wǎng)頁對(pi，pj)，定義STm (pi，pj)= m0/m，其中m0為pi，pj的相同sha-1指紋的個數(shù)。易得，給定范圍t，如果STm (pi，pj)∈t，則把兩個頁面歸為某一類。

文本聚類

目前，有多種文本聚類算法，常見的聚類方法有層次凝聚類方法和以k-means為代表的平面劃分法。

層次聚類方法能夠生成層次化的嵌套簇，且準確度較高。但是在每次合并時需要全局地比較所有簇之間的相似度，并選擇出最佳的兩個簇，因此運行速度較慢，不適合于大量文檔的集合。

近年來各種研究顯示，平面劃分法比層次凝聚法更適合對大規(guī)模文檔進行聚類，這是因為平面劃分法的計算量相對較小。如：層次凝聚法中的Single-link和group-average方法的時間復(fù)雜度為O(n2)，complete-link法的時間復(fù)雜度為(n3)，n為文檔數(shù)。而平面劃分法中的k-means法的時間復(fù)雜度為O(nKT)，single-pass法的時間復(fù)雜度為O(nK)，其中n為文檔數(shù)，k是最終聚類數(shù)目，T是迭代次數(shù)。

所以本文選取k-means算法進行文本聚類，k-means 算法接受輸入量 k;然后將n個數(shù)據(jù)對象劃分為 k個聚類以便使所獲得的聚類滿足，同一聚類中的對象相似度較高;而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個“中心對象”(引力中心)來進行計算的。

k-means 算法的工作過程說明如下：首先從n個數(shù)據(jù)對象任意選擇 k 個對象作為初始聚類中心;而對于所剩下其它對象，則根據(jù)它們與這些聚類中心的相似度(距離)，分別將它們分配給與其最相似的(聚類中心所代表的)聚類;然后再計算每個所獲新聚類的聚類中心(該聚類中所有對象的均值);不斷重復(fù)這一過程直到標準測度函數(shù)開始收斂為止。一般都采用均方差作為標準測度函數(shù)。

雖然k-means算法對初始聚類中心選取較敏感，但在本文中，文本分成了多少個類，就有多少個k對象。以兩個文本塊相同的指紋數(shù)作為它們的相似度做聚類得到最終聚類結(jié)果。

總結(jié)

本文舍棄了常用的提取特征值，計算文本相似度的方法，而是對凈化的文本塊作分塊的信息摘要(即文件指紋)，在比較相同指紋的基礎(chǔ)上對文本進行分類，以類值為k-means算法的初始聚類值，以兩文本的相同指紋數(shù)作為文本的相似度做文本聚類。

【編輯推薦】

1. 基于指紋特征的電子商務(wù)身份安全認證技術(shù)研究？
2. 挖掘指尖上的密碼