一種基于密度的Web文本聚類算法

許芳芳

摘要：針對(duì)DBSCAN算法采用全局參數(shù)Eps、對(duì)高維數(shù)據(jù)處理能力不足等問題，提出一種改進(jìn)算法，該算法結(jié)合蟻群聚類算法實(shí)現(xiàn)數(shù)據(jù)集的劃分以獲取參數(shù)Eps的值組，然后根據(jù)不同的Eps值分別調(diào)用DBSCAN算法，從而實(shí)現(xiàn)對(duì)Web文本的聚類。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法的有效性有所提高。

關(guān)鍵詞：Web文本；DBSCAN；蟻群聚類；Eps值組

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）08-0234-02

Abstract： Focusing on the problem that the DBSCAN algorithm uses the same global Eps and has difficulty with high-dimension of data，proposed an improved web text clustering algorithm.The algorithm use ant clustering algorithm in data preprocessing phase to classify the datasets and to get several values of parameter eps， then call DBSCAN algorithm with different values of Eps to cluster web text . Experimental results demonstrate the effectiveness of the improved algorithm.

Key words： web text； DBSCAN； Ant clustering algorithm； A set of values of Eps

1 引言

互聯(lián)網(wǎng)的發(fā)展使網(wǎng)絡(luò)上的信息呈爆炸式增長(zhǎng)，且超過80%的Web資源以文本的形式存在[1]。這些文本信息的增長(zhǎng)對(duì)準(zhǔn)確檢索到相關(guān)信息帶來了極大的挑戰(zhàn)，人們急需某種方法從海量Web文本信息中尋找需要的資源。作為文本分析的一種重要技術(shù)，文本聚類可以發(fā)現(xiàn)相似文檔，以供進(jìn)一步分析挖掘。由于Web文本挖掘的數(shù)據(jù)不是事先存儲(chǔ)在數(shù)據(jù)庫中，而是利用網(wǎng)絡(luò)爬蟲抓取的大量網(wǎng)頁資源，因此，要對(duì)Web文本聚類，必須將抓取的Web網(wǎng)頁進(jìn)行文本預(yù)處理， 形成文本特征向量，才能進(jìn)行聚類。

文本聚類算法有多種，但由于Web文本不同于普通文本，這些常用的文本聚類方法必須經(jīng)過一定的改進(jìn)后，才可適用于Web文本。基于密度的DBSCAN算法可以發(fā)現(xiàn)任意形狀的簇，且不需要預(yù)先確定數(shù)據(jù)集將被聚類的簇?cái)?shù)，也不受噪聲影響。但是該算法需要用戶輸入統(tǒng)一的全局參數(shù)Eps，當(dāng)數(shù)據(jù)集的密度不均勻時(shí)，導(dǎo)致聚類效果差；并且對(duì)于高維數(shù)據(jù)的處理能力也較差，而Web文本往往是高維的且分布不均的。為了實(shí)現(xiàn)對(duì)Web文本的有效聚類，本文提出一種改進(jìn)的DBSCAN算法。

2 Web文本聚類關(guān)鍵技術(shù)

要實(shí)現(xiàn)Web文本聚類，首先使用網(wǎng)絡(luò)蜘蛛抓取網(wǎng)頁，將網(wǎng)頁中與主題內(nèi)容不相關(guān)的HTML標(biāo)記和廣告等移除，并將其轉(zhuǎn)換成文本文件保存；然后對(duì)得到的文本進(jìn)行分詞處理，將文本切分成特征詞條，去除停用詞，統(tǒng)計(jì)詞頻等；將分詞后的文本轉(zhuǎn)換為易被計(jì)算機(jī)理解的形式（即文本特征表示），以及特征降維，之后才能對(duì)Web文本進(jìn)行聚類。

2.1 文本表示

特征詞條（即分詞后的文本）是用自然語言描述的，計(jì)算機(jī)無法直接處理，因此需要將文本表示為計(jì)算機(jī)可以直接處理的形式。向量空間模型（VSM，Vector Space Model）是目前應(yīng)用最廣的文本表示模型。它由哈佛大學(xué)的G Salton提出，它將任意一個(gè)文本表示成空間向量的形式：V（di）=（w1（di），w2（di），…，wn（di））。其中，n表示總的特征詞條數(shù)，wj（di）表示第j個(gè)特征詞條在文檔di中的權(quán)值。在權(quán)值的量化方法上，比較常用的是TF*IDF算法，其中，TF（詞項(xiàng)頻率）表示特征詞條ti在文本dj中出現(xiàn)的次數(shù)，記為tfij；IDF（倒排文檔頻率）表示文本集中總的文檔數(shù)N與包含該特征詞條的文檔數(shù)n的商值，常用公式log（N/n）來計(jì)算，它是特征詞條在文本集分布情況的量化。文本特征詞條權(quán)值的計(jì)算如公式1所示：

（1）其中，tfij為在文檔dj中含有第i個(gè)特征詞條的頻數(shù)，N為文本集中的總文檔數(shù)，Ni為含有第i個(gè)特征詞條的文檔數(shù)。

2.2 文本特征降維

分詞后的文本集由眾多特征詞條構(gòu)成，且詞條數(shù)量相當(dāng)?shù)拇?。因此表示文本的向量空間維數(shù)會(huì)很高，將影響文本聚類的效率和精度。一方面大多數(shù)聚類算法都難以承受維數(shù)太高的向量空間；另一方面在文本中會(huì)存在一些通用的、對(duì)文本聚類貢獻(xiàn)度小的特征詞，因此，有必要對(duì)文本數(shù)據(jù)進(jìn)行降維處理。實(shí)驗(yàn)表明，對(duì)特征集適當(dāng)?shù)慕稻S可以減少聚類的計(jì)算量且改善聚類效果[2]。目前，用得最多的降維方法有兩類：綜合評(píng)估法和獨(dú)立評(píng)估法[3]。本文選擇信息增益法進(jìn)行降維處理。

2.3 文本相似度計(jì)算

對(duì)文本集進(jìn)行聚類處理，需要先度量文本對(duì)象之間的相似度sim（di，dj），并且文本聚類的質(zhì)量一定程度上也取決于度量方法的選擇。聚類分析中通常使用歐式距離函數(shù)或余弦距離來度量對(duì)象之間的相似度。本文采用余弦計(jì)算法來度量?jī)蓚€(gè)文本間的相似度，其定義為：

（2）其中：wki和wkj分別表示文檔di和dj的第k個(gè)特征詞的權(quán)值，n為文檔特征詞條數(shù)。Sim（di，dj）值越大，則表明文本di和dj越相似，反之則區(qū)別越大。

3 文本的聚類

3.1 DBSCAN算法

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法[4]是一個(gè)被廣泛用于文本聚類分析的算法，它將簇定義為密度相連的點(diǎn)的最大集合，能把具有足夠高密度的區(qū)域劃分為簇。該算法需要用戶輸入對(duì)象鄰域半徑Eps和鄰域內(nèi)最少對(duì)象數(shù)MinPts這兩個(gè)參數(shù)來識(shí)別一個(gè)簇。DBSCAN算法的基本思想是：從數(shù)據(jù)集中任選一對(duì)象p，若p在半徑為Eps的區(qū)域內(nèi)包含的對(duì)象數(shù)目大于等于MinPts個(gè)，則p為核心對(duì)象并建立新簇，找出所有從p密度可達(dá)的對(duì)象，將這些對(duì)象標(biāo)注為同一簇；否則，沒有其他對(duì)象從p密度可達(dá)，p被暫時(shí)標(biāo)注為噪聲。然后，DBSCAN對(duì)數(shù)據(jù)集中其他未被處理的對(duì)象均做上述處理。

3.2 LF算法

蟻群聚類算法是由Deneubourg J L[5]等人根據(jù)螞蟻堆積蟻尸等蟻群聚類現(xiàn)象提出的一種基本模型（Basic Model， BM），Lumer E和Faieta B將該模型擴(kuò)展，提出了用于數(shù)據(jù)聚類的LF算法[6]。其主要思想是將待聚類的高維數(shù)據(jù)對(duì)象隨機(jī)投影到一個(gè)二維網(wǎng)格上，同時(shí)將若干只人工螞蟻隨機(jī)放置到該二維網(wǎng)格內(nèi)，每只螞蟻選擇一個(gè)數(shù)據(jù)對(duì)象，根據(jù)該數(shù)據(jù)對(duì)象與局部區(qū)域的相似度，決定螞蟻拾起或放下該對(duì)象的概率，從而指導(dǎo)螞蟻的下一步動(dòng)作。經(jīng)過一定代數(shù)的迭代后，平面上的屬于同一類別的數(shù)據(jù)對(duì)象聚集在一起，從而實(shí)現(xiàn)自組織的聚類過程。

鄰域相似度f（i）表示螞蟻在地點(diǎn)r發(fā)現(xiàn)的一個(gè)數(shù)據(jù)對(duì)象i與其鄰域?qū)ο箝g的平均相似度， f（i）可由公式（3）來計(jì)算

（3）式中，[0，1]為相似度調(diào)節(jié)因子；Neighsxs（r）表示地點(diǎn)r周圍的以s為邊長(zhǎng)的正方形局部區(qū)域；d（i，j）表示對(duì)象i和j在屬性空間中的距離，通常采用歐式距離或余弦距離函數(shù)。

在LF算法中，若螞蟻有負(fù)載，則按公式（4）計(jì)算螞蟻的放下概率Pd；若螞蟻無負(fù)載，則按公式（5）計(jì)算螞蟻拾起數(shù)據(jù)的概率Pp。其中，kp和kd均為閾值常數(shù)。鄰域相似度越高，則螞蟻放下對(duì)象的概率越高，拾起對(duì)象的概率越低；反之亦然。

3.3 改進(jìn)算法描述

LF算法易與其他算法結(jié)合，且能有效處理高維數(shù)據(jù)，但存在計(jì)算時(shí)間較長(zhǎng)等問題；本文采用文獻(xiàn)[7]提出的LF改進(jìn)算法，以減少算法時(shí)間成本。改進(jìn)算法是LF算法與DBSCAN算法的結(jié)合，以實(shí)現(xiàn)對(duì)密度不均的高維數(shù)據(jù)集的有效聚類。該算法可分為如下三個(gè)階段：

（1）基于LF算法的聚類過程。利用LF算法將高維數(shù)據(jù)集映射到二維網(wǎng)格中，并將人工螞蟻和數(shù)據(jù)綁定，實(shí)現(xiàn)對(duì)數(shù)據(jù)集的初始劃分。

（2）獲取參數(shù)Eps的值組。對(duì)第一階段得到的每個(gè)數(shù)據(jù)子集，計(jì)算某個(gè)到當(dāng)前聚類中的其他所有點(diǎn)的距離之和最小的點(diǎn)，此點(diǎn)為該類的中心點(diǎn)；計(jì)算各類的鄰域閾值Epsi（為每個(gè)中心點(diǎn)的k個(gè)近鄰距離的平均距離）。

（3）基于DBSCAN算法的聚類過程。對(duì)所有的Epsi按升序排序，依次根據(jù)Epsi調(diào)用DBSCAN進(jìn)行聚類，以實(shí)現(xiàn)對(duì)高密度數(shù)據(jù)和稀疏密度數(shù)據(jù)的分別聚類；每次調(diào)用后，所有已聚類的數(shù)據(jù)點(diǎn)將不再參與以后的調(diào)用；直到所有的Epsi都使用完畢，剩下的沒有被處理過的數(shù)據(jù)點(diǎn)即是噪聲點(diǎn)。

4 實(shí)驗(yàn)分析

為了驗(yàn)證本文提出的改進(jìn)算法的有效性，使用網(wǎng)絡(luò)爬蟲從網(wǎng)易網(wǎng)站爬取了5類約370篇文檔作為實(shí)驗(yàn)數(shù)據(jù)，含財(cái)經(jīng)85篇、科技96篇、旅游66、娛樂60和教育63，其中20篇涉及到財(cái)經(jīng)類和科技類，12篇涉及到教育類和娛樂類。將采集到的網(wǎng)頁資源進(jìn)行去噪處理后，以文本文檔的格式保存，并采用中科院ICTCLAS分詞系統(tǒng)模塊對(duì)得到的文本信息進(jìn)行分詞；使用公式1進(jìn)行權(quán)值計(jì)算，形成向量空間模型并降維。本文采用綜合考慮了查準(zhǔn)率和查全率的 F-Measure度量[8]作為評(píng)價(jià)指標(biāo)，對(duì)聚類實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)價(jià)。分別調(diào)用DBSCAN算法和改進(jìn)后的算法對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行聚類，實(shí)驗(yàn)結(jié)果的F-Measure值如圖1所示。通過圖1可以得到：改進(jìn)DBSCAN算法的F-Measure值高于經(jīng)典DBSCAN算法，表明改進(jìn)DBSCAN算法的有效性更好，增強(qiáng)了Web文本聚類的能力。

5 結(jié)束語

本文簡(jiǎn)述了Web文本聚類過程中涉及到的關(guān)鍵技術(shù)。提出了一種改進(jìn)的DBSCAN算法，針對(duì)DBSCAN算法用于Web文本聚類時(shí)采用全局參數(shù)Eps導(dǎo)致聚類效果差、對(duì)高維數(shù)據(jù)處理能力不足等問題給與了有效解決。實(shí)驗(yàn)表明，改進(jìn)后的DBSCAN算法的有效性有所提高。

參考文獻(xiàn)：

[1] 陳宇，王強(qiáng).聚類算法在Web文本挖掘中的應(yīng)用研究[A].2009全國(guó)計(jì)算機(jī)網(wǎng)絡(luò)與通信學(xué)術(shù)會(huì)議論文集[C].2009.

[2] 晏璐.基于劃分的聚類算法及其在Web挖掘中的應(yīng)用[D].大連：大連理工大學(xué)，2007.

[3] 楊亞坤.基于Web文本挖掘的聚類算法研究[D].包頭：內(nèi)蒙古科技大學(xué)，2012.

[4] Ester M，Kriegel H P，Sander J，et al.A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining（KDD96），1996：226-231.

[5] Deneubourg J L，Goss S，F(xiàn)ranks N，et al.The dynamics of collective sorting：robot-like ants and ant-like robots[C].Proceedings of the 1st International Conference on Simulation of Adaptive Behavior：From Animal to Animals，1991：356-365.

[6] Lumer E，F(xiàn)aieta B.Diversity and adaptation in populations of clustering ants[C]. Proceedings of the 3rd International Conference on Simulation of Adaptive Behavior：From Animals to Animals.Cambridge，MIT Press，1994：501-508.

[7] 趙燁，黃澤君.蟻群K-medoids融合的聚類算法[J].電子測(cè)量與儀器學(xué)報(bào)，2012，26（9）：800-

804.

[8] 黃承慧，印鑒，侯昉.一種結(jié)合詞項(xiàng)語義信息和TF-IDF的文本相似度量方法[J].計(jì)算機(jī)學(xué)報(bào)，2011，34（5） ：856-864.