建站
咨詢
售后
建站咨詢
新聞中心
在迅猛增加的海量異構(gòu)的Web信息資源中，蘊(yùn)含著巨大潛在價(jià)值的數(shù)據(jù)。如何從浩如煙海的Web資源中發(fā)現(xiàn)潛在有價(jià)值的知識(shí)成為迫在眉睫的問(wèn)題。人們迫切需要能從Web上快速、有效地發(fā)現(xiàn)資源和數(shù)據(jù)的工具，以提高在Web上檢索信息、利用信息的效率。
創(chuàng)新互聯(lián)于2013年成立，先為永善等服務(wù)建站，永善等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為永善企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問(wèn)題。
目前Web文本挖掘大部分研究都是建立在詞匯袋(bag of words)或稱向量表示法(Vector Representation)的基礎(chǔ)上，這種方法將單個(gè)的詞匯看成文檔集合中的屬性，只從統(tǒng)計(jì)的角度將詞匯孤立地看待而忽略該詞匯出現(xiàn)的位置和上下文環(huán)境。詞匯袋方法的一個(gè)弊端是自由文本中的數(shù)據(jù)豐富，詞匯量非常大，處理起來(lái)很困難，為解決這個(gè)問(wèn)題人們做了相應(yīng)的研究，采取了不同技術(shù)，如信息增益，交叉熵、差異比等，其目的都是為了減少屬性。一個(gè)比較有意義的方法是潛在語(yǔ)義索引(Latent Semantic Indexing)，它通過(guò)分析不同文檔中相同主題的共享詞匯，找到它們共同的根，用這個(gè)公共的根代替所有詞匯，以此來(lái)減少維空間。其它的屬性表示法還有詞匯在文檔中的出現(xiàn)位置、層次關(guān)系、使用短語(yǔ)、使用術(shù)語(yǔ)、命名實(shí)體等，目前還沒(méi)有研究表明一種表示法明顯優(yōu)于另一種。
圖1 文本聚類模型
本文所提出的挖掘技術(shù)，不是基于詞匯屬性，而是文本塊。在利用網(wǎng)頁(yè)的標(biāo)簽樹結(jié)構(gòu)的基礎(chǔ)上，提取標(biāo)題和文本塊生成SHA-1指紋序列，如果兩個(gè)頁(yè)面具有的相同的指紋塊在我們所設(shè)定的范圍內(nèi)，那么就把這兩個(gè)頁(yè)面歸為一類，類值就是所要聚類的準(zhǔn)確數(shù)目k，接下來(lái)用k-means進(jìn)行文本聚類，達(dá)到文本挖掘的目的[2][3]。圖1是文本聚類模型。
文本預(yù)處理
◆網(wǎng)頁(yè)凈化
由于Web文本上存在大量的廣告、html標(biāo)簽、相關(guān)鏈接等無(wú)用信息，所以首先要對(duì)所收集到的網(wǎng)頁(yè)進(jìn)行凈化處理，也稱為網(wǎng)頁(yè)去噪，以提高聚類效果。我們把網(wǎng)頁(yè)設(shè)計(jì)者為了輔助網(wǎng)站組織而增加的文字定義為“噪聲”，把原本要表達(dá)的文字素材稱為“主題內(nèi)容”。 這些噪音是與頁(yè)面主題無(wú)關(guān)(即瀏覽者不關(guān)心)的區(qū)域及項(xiàng)，包括廣告欄、導(dǎo)航條、修飾成分等。
這樣，我們對(duì)HTML源碼進(jìn)行分析，根據(jù)起分隔作用的標(biāo)記去掉噪音部分，提取出網(wǎng)頁(yè)正文[4]。
◆生成SHA-1指紋
SHA的全稱是Secure Hash Algorithm，即安全哈希算法。它是由美國(guó)國(guó)家標(biāo)準(zhǔn)和技術(shù)協(xié)會(huì)(NIST)開發(fā)，于1993年作為聯(lián)邦信息處理標(biāo)準(zhǔn)(FIPS PUB 180)公布。1995年又發(fā)布了一個(gè)修訂版FIPS PUB 180-1，通常稱之為SHA-1。現(xiàn)在已成為公認(rèn)的最安全的散列算法之一，并被廣泛使用。該算法的思想是接收一段明文，然后以一種不可逆的方式將它轉(zhuǎn)換成一段(通常更小)密文，也可以簡(jiǎn)單的理解為取一串輸入碼(稱為預(yù)映射或信息)，并把它們轉(zhuǎn)化為長(zhǎng)度較短、位數(shù)固定的輸出序列即散列值(也稱為信息摘要或信息認(rèn)證代碼)的過(guò)程[5]。
由于sha-1算法的雪崩效應(yīng)，對(duì)文本塊作信息摘要時(shí)，要消除文本塊中的不可見(jiàn)字符，而文本塊排序是為了降低算法的復(fù)雜度。對(duì)于凈化后的文本塊，通過(guò)格式分析生成M個(gè)文本塊B1，B2，…BM(文本塊按重要性排序)，取前m(≤ M)個(gè)文本塊生成sha-1指紋sha-11，sha-12，…sha-1m。對(duì)于網(wǎng)頁(yè)對(duì)(pi，pj)，定義STm (pi，pj)= m0/m，其中m0為pi，pj的相同sha-1指紋的個(gè)數(shù)。易得，給定范圍t，如果STm (pi，pj)∈t，則把兩個(gè)頁(yè)面歸為某一類。
文本聚類
目前，有多種文本聚類算法，常見(jiàn)的聚類方法有層次凝聚類方法和以k-means為代表的平面劃分法。
層次聚類方法能夠生成層次化的嵌套簇，且準(zhǔn)確度較高。但是在每次合并時(shí)需要全局地比較所有簇之間的相似度，并選擇出最佳的兩個(gè)簇，因此運(yùn)行速度較慢，不適合于大量文檔的集合。
近年來(lái)各種研究顯示，平面劃分法比層次凝聚法更適合對(duì)大規(guī)模文檔進(jìn)行聚類，這是因?yàn)槠矫鎰澐址ǖ挠?jì)算量相對(duì)較小。如：層次凝聚法中的Single-link和group-average方法的時(shí)間復(fù)雜度為O(n2)，complete-link法的時(shí)間復(fù)雜度為(n3)，n為文檔數(shù)。而平面劃分法中的k-means法的時(shí)間復(fù)雜度為O(nKT)，single-pass法的時(shí)間復(fù)雜度為O(nK)，其中n為文檔數(shù)，k是最終聚類數(shù)目，T是迭代次數(shù)。
所以本文選取k-means算法進(jìn)行文本聚類，k-means 算法接受輸入量 k;然后將n個(gè)數(shù)據(jù)對(duì)象劃分為 k個(gè)聚類以便使所獲得的聚類滿足，同一聚類中的對(duì)象相似度較高;而不同聚類中的對(duì)象相似度較小。聚類相似度是利用各聚類中對(duì)象的均值所獲得一個(gè)“中心對(duì)象”(引力中心)來(lái)進(jìn)行計(jì)算的。
k-means 算法的工作過(guò)程說(shuō)明如下：首先從n個(gè)數(shù)據(jù)對(duì)象任意選擇 k 個(gè)對(duì)象作為初始聚類中心;而對(duì)于所剩下其它對(duì)象，則根據(jù)它們與這些聚類中心的相似度(距離)，分別將它們分配給與其最相似的(聚類中心所代表的)聚類;然后再計(jì)算每個(gè)所獲新聚類的聚類中心(該聚類中所有對(duì)象的均值);不斷重復(fù)這一過(guò)程直到標(biāo)準(zhǔn)測(cè)度函數(shù)開始收斂為止。一般都采用均方差作為標(biāo)準(zhǔn)測(cè)度函數(shù)。
雖然k-means算法對(duì)初始聚類中心選取較敏感，但在本文中，文本分成了多少個(gè)類，就有多少個(gè)k對(duì)象。以兩個(gè)文本塊相同的指紋數(shù)作為它們的相似度做聚類得到最終聚類結(jié)果。
總結(jié)
本文舍棄了常用的提取特征值，計(jì)算文本相似度的方法，而是對(duì)凈化的文本塊作分塊的信息摘要(即文件指紋)，在比較相同指紋的基礎(chǔ)上對(duì)文本進(jìn)行分類，以類值為k-means算法的初始聚類值，以兩文本的相同指紋數(shù)作為文本的相似度做文本聚類。
【編輯推薦】
- 基于指紋特征的電子商務(wù)身份安全認(rèn)證技術(shù)研究？
- 挖掘指尖上的密碼
網(wǎng)站名稱：基于文件指紋的Web文本挖掘
文章位置：http://www.dlmjj.cn/article/dpioeed.html
