鄒艷春

摘 要：提出使用文本相似度算法與DBSCAN聚類算法相結(jié)合的方法對文本進(jìn)行聚類，實(shí)現(xiàn)對文本的管理。首先對文本進(jìn)行特征提取和分詞操作，在分詞過程中會(huì)產(chǎn)生大量的特征詞匯，而有些特征詞匯對文本特征的表達(dá)并無實(shí)際意義。因此，在文本特征提取過程中根據(jù)特征詞匯對文本特征表達(dá)的貢獻(xiàn)度進(jìn)行取舍，以提高文本聚類的效率和準(zhǔn)確性。利用TF-IDF方法對特征詞匯進(jìn)行加權(quán)，并且對文本進(jìn)行相似度計(jì)算，將相似度低于閾值的文本作為孤立點(diǎn)進(jìn)行處理。利用DBSCAN算法對文本進(jìn)行聚類，將相似的文本聚為一類。

關(guān)鍵詞關(guān)鍵詞：文本聚類；DBSCAN聚類；文本相似度；文本處理

DOIDOI：10.11907/rjdk.161915

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2016）008-0036-03

0 引言

互聯(lián)網(wǎng)作為開放共享的信息平臺(tái)，蘊(yùn)含著海量的文本信息資源，而這些海量文本信息資源通常在互聯(lián)網(wǎng)上是無序存放的，存在著各種各種冗余的信息，因此需要采用相關(guān)技術(shù)來組織和管理這些文本信息。文本分類和聚類是文本信息管理的重要方法，文本聚類是文本挖掘的重要組成部分，越來越受到關(guān)注。文本聚類廣泛應(yīng)用于文檔自動(dòng)整理、組織管理等，可以對搜索引擎搜索結(jié)果分類進(jìn)行優(yōu)化。此外，也可以應(yīng)用于推薦系統(tǒng)中，根據(jù)用戶所感興趣的文檔進(jìn)行聚類，發(fā)現(xiàn)用戶的興趣模式，從而挖掘出用戶新的感興趣的資源。本文利用DBSCAN算法來對文本進(jìn)行聚類，DBSCAN算法是一種基于密度的聚類算法，該算法通過過濾低密度的區(qū)域，發(fā)現(xiàn)稠密的區(qū)域[1]。本文文本處理的模型如圖1所示，在文本預(yù)處理階段，需要對文本表示方式轉(zhuǎn)換為數(shù)值數(shù)據(jù)的表達(dá)形式，通過對文本進(jìn)行分詞和特征項(xiàng)提取，使用TF-IDF對特征詞匯進(jìn)行加權(quán)，利用DBSCAN聚類算法將相似的文本聚為一類。

1 文本預(yù)處理

1.1 中文文檔分詞處理

文本預(yù)處理首先需要對文本進(jìn)行分詞操作，中文文檔使用詞典和砌詞的方式進(jìn)行分詞，分詞過程由計(jì)算機(jī)自動(dòng)實(shí)現(xiàn)。由于文檔中存在一些無用的詞匯或符號等，需要在分詞過程中去除這些無用的詞語及符號，比如文檔中的標(biāo)點(diǎn)符號、結(jié)構(gòu)助詞等，這些詞匯對文本特征表示并無太大的關(guān)聯(lián)，因此需要過濾掉。同時(shí)，中文詞匯中存在同義詞問題，需要對同義詞進(jìn)行合并操作，比如“歌唱”和“歌頌”屬于同義詞，可以合并為“歌唱”。

1.2 文本特征提取

文本經(jīng)過分詞處理后會(huì)出現(xiàn)大量的特征詞匯，特征詞匯可以是詞組，也可以是詞條。這些特征詞匯中相當(dāng)部分對文本特征表示并無太大貢獻(xiàn)，因此需要對這些特征詞匯進(jìn)行取舍，以提高聚類的效率和準(zhǔn)確性。特征詞匯的提取依據(jù)主要是由文本特征表達(dá)的貢獻(xiàn)度來決定，特征詞匯的貢獻(xiàn)度越高，說明這個(gè)特征詞匯就越能表達(dá)文本特征。特征詞匯的貢獻(xiàn)度受多個(gè)因素影響，主要影響因素是特征詞匯出現(xiàn)的頻率、文本的主題和特征增量。

2 DBSCAN聚類算法分析與實(shí)現(xiàn)

2.1 DBSCAN聚類算法分析

文本聚類是按照聚類假設(shè)：同類文檔相似度大，對于不是同類的文檔，它們的相似度小[3]。作為一種無監(jiān)督的機(jī)器學(xué)習(xí)方法，聚類由于不需要訓(xùn)練樣本的過程，不需要預(yù)先對文檔手工標(biāo)注類別，因此具有一定的靈活性和較高的自動(dòng)化處理能力，已經(jīng)成為對文本信息進(jìn)行有效組織、摘要和導(dǎo)航的重要手段[4]。DBSCAN算法是一種基于密度的聚類算法，其主要目的是過濾低密度的樣本區(qū)域，從而發(fā)現(xiàn)稠密的樣本區(qū)域。與傳統(tǒng)的基于層次聚類和劃分聚類的凸形聚類簇不同，該算法可以發(fā)現(xiàn)任意形狀的聚類簇[5]。與K-means相比較，不必輸入劃分的聚類個(gè)數(shù)，聚類簇的形狀可以是任意形狀的空間聚類，可以在需要時(shí)輸入過濾噪聲的參數(shù)，DBSCAN中的定義如下：

輸出：所有生成的簇，達(dá)到密度要求。

算法1：Repeat。

算法2：從數(shù)據(jù)集S中取出一個(gè)沒有處理過的對象。

算法3：IF取出的對象是核心對象 THEN 尋找全部從該對象密度可達(dá)的對象，形成一個(gè)簇。

算法4：ELSE 取出的對象不是核心對象，跳出本次循環(huán)，繼續(xù)尋找下一個(gè)對象。

算法5：UNTIL 所有的對象都被處理。

2.2 DBSCAN聚類算法對文本聚類的實(shí)現(xiàn)

從文檔集中抽取一篇未被處理的文檔p（p代表從文檔集抽出的一篇文檔），并標(biāo)示文檔p為已處理，先對文檔p進(jìn)行分詞和特征提取。在特征提取過程中需要對特征詞匯進(jìn)行去噪處理，從而得到特征詞匯集合。利用TF-IDF方法對文檔集中的文檔（包括文檔p）分別對這些特征詞匯集合進(jìn)行加權(quán)操作，得到一個(gè)數(shù)據(jù)矩陣。利用文本相似度算法計(jì)算文檔p與文檔集中其它文檔的相似度，如果與文檔p相似度大于或等于設(shè)定閾值，就存放到文檔p的領(lǐng)域中，直到數(shù)據(jù)矩陣全部數(shù)據(jù)處理完畢。判斷p的領(lǐng)域中文檔數(shù)量是否大于設(shè)定的MinPts值，如果大于設(shè)定的MinPts值，則稱p為核心對象并繼續(xù)向下執(zhí)行，否則返回上層重新從文檔集中抽取一篇未被處理的文檔開始處理。判斷文檔p是否已經(jīng)屬于某一個(gè)簇中，如果文檔p沒有所屬的簇，就新建一個(gè)簇并且將文檔p放到這個(gè)簇中。從文檔p的領(lǐng)域中抽取一篇未處理的文檔（r代表從p的領(lǐng)領(lǐng)域中抽出的一篇文檔）r，并標(biāo)記文檔r已處理，對文檔r得到領(lǐng)域的方法和文檔p處理一樣，判斷r的領(lǐng)域中文檔數(shù)量，如果文檔數(shù)據(jù)大于設(shè)定的MinPts值，就把文檔r領(lǐng)域中的文檔存放到文檔p所屬的簇中，直到p的領(lǐng)域中的文檔處理完畢。最后直到文檔集中的文檔都處理完畢之后算法結(jié)束，算法流程圖如圖2所示。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)過程

從網(wǎng)絡(luò)中摘取1 028篇關(guān)于Java教程內(nèi)容的文檔進(jìn)行實(shí)驗(yàn)，其中關(guān)于Struts的文檔有22篇，Hibernate文檔有37篇，Spring文檔有38篇，Java多線程文檔有135篇。對每個(gè)類別的文檔分別進(jìn)行聚類，一共進(jìn)行4次聚類操作，聚類結(jié)果如表1所示。

3.2 實(shí)驗(yàn)結(jié)果分析

從聚類結(jié)果分析，有些文檔并沒有與其它文檔聚為一類，成為孤立的噪點(diǎn)，還有些文檔并沒有準(zhǔn)確聚到相應(yīng)的簇中。出現(xiàn)這種情況的原因有很多，比如文檔的特征詞匯不能很好地反映文檔的特征，特征詞匯對文檔之間的區(qū)分度反應(yīng)不明顯。但從總體來看，DBSCAN算法能夠有效將相似的文本聚為一類，從而對文本進(jìn)行組織管理。

4 結(jié)語

本文綜合利用DBSCAN聚類算法與文本相似度算法對文本進(jìn)行聚類，把相似的文本聚為一類，實(shí)現(xiàn)對文本的管理。實(shí)驗(yàn)過程中也發(fā)現(xiàn)一些不足，比如一些文檔由于特征不明顯會(huì)被當(dāng)作孤立點(diǎn)處理或不能聚到正確的類別中，這就需要對文本特征的提取和算法的優(yōu)化作進(jìn)行一步研究。但從實(shí)驗(yàn)數(shù)據(jù)分析來看，DBSCAN聚類算法能有效對大部分的文本進(jìn)行有效的聚類，實(shí)驗(yàn)結(jié)果表明這種方法是有效的。

參考文獻(xiàn)：

[1]許芳芳.基于DBSCAN優(yōu)化算法的Web文本聚類研究[D].上海：華東師范大學(xué)，2011.

[2]PANG-NING TAN，MICHAEL STEINBACH，VIPIN KUMAR.Introduction to data min[M].北京：人民郵電出版社，2006（1）：32-45.

[3]劉遠(yuǎn)超，王曉龍，劉秉權(quán)，等.信息檢索中的聚類分析技術(shù)[J].電子與信息學(xué)報(bào)， 2006（4）：29-32.

[4]王偉.文本自動(dòng)聚類技術(shù)研究[J].情報(bào)雜志，2009（2）：94-97.

[5]傅華忠，茅劍.基于DBSCAN聚類算法的Web文本挖掘[J].科技信息，2007（1）： 55-56.

（責(zé)任編輯：陳福時(shí)）