基于DBSCAN算法的文本聚類研究

鄒艷春

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

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

DOIDOI：10.11907/rjdk.161915

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2016）008-0036-03

0 引言

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

1 文本預處理

1.1 中文文檔分詞處理

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

1.2 文本特征提取

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

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

2.1 DBSCAN聚類算法分析

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

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

算法1：Repeat。

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

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

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

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

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

從文檔集中抽取一篇未被處理的文檔p（p代表從文檔集抽出的一篇文檔），并標示文檔p為已處理，先對文檔p進行分詞和特征提取。在特征提取過程中需要對特征詞匯進行去噪處理，從而得到特征詞匯集合。利用TF-IDF方法對文檔集中的文檔（包括文檔p）分別對這些特征詞匯集合進行加權(quán)操作，得到一個數(shù)據(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)屬于某一個簇中，如果文檔p沒有所屬的簇，就新建一個簇并且將文檔p放到這個簇中。從文檔p的領(lǐng)域中抽取一篇未處理的文檔（r代表從p的領(lǐng)領(lǐng)域中抽出的一篇文檔）r，并標記文檔r已處理，對文檔r得到領(lǐng)域的方法和文檔p處理一樣，判斷r的領(lǐng)域中文檔數(shù)量，如果文檔數(shù)據(jù)大于設(shè)定的MinPts值，就把文檔r領(lǐng)域中的文檔存放到文檔p所屬的簇中，直到p的領(lǐng)域中的文檔處理完畢。最后直到文檔集中的文檔都處理完畢之后算法結(jié)束，算法流程圖如圖2所示。

3 實驗與結(jié)果分析

3.1 實驗過程

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

3.2 實驗結(jié)果分析

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

4 結(jié)語

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

參考文獻：

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

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

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

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

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

（責任編輯：陳福時）