趙 楠，劉 振，孫艷超，鄒盼盼，陳德軍

(1.中國(guó)船舶重工集團(tuán)公司第七二二研究所，湖北 武漢 430205；2.武漢理工大學(xué) 信息工程學(xué)院，湖北 武漢 430070)

基于密度聚類算法的學(xué)術(shù)資源熱點(diǎn)發(fā)現(xiàn)方法研究

趙 楠1，劉 振1，孫艷超1，鄒盼盼2，陳德軍2

(1.中國(guó)船舶重工集團(tuán)公司第七二二研究所，湖北 武漢 430205；2.武漢理工大學(xué) 信息工程學(xué)院，湖北 武漢 430070)

針對(duì)學(xué)術(shù)會(huì)議產(chǎn)生的爆炸式學(xué)術(shù)資源共享下用戶如何快速準(zhǔn)確地獲取當(dāng)前研究熱點(diǎn)的問(wèn)題，提出了一種改進(jìn)的基于密度的聚類算法DBSCAN，實(shí)現(xiàn)學(xué)術(shù)資源熱點(diǎn)的自動(dòng)發(fā)現(xiàn)，即通過(guò)合并具有明顯關(guān)系的關(guān)鍵詞以縮減特征項(xiàng)，以及解決公共資源對(duì)象鄰域的重復(fù)獲取問(wèn)題，從而在一定程度上提高聚類的準(zhǔn)確率和時(shí)間效率。結(jié)果表明，上述方法能夠快速準(zhǔn)確地發(fā)現(xiàn)當(dāng)前相關(guān)領(lǐng)域的研究熱點(diǎn)，有助于了解當(dāng)前各學(xué)科的研究熱點(diǎn)，并對(duì)傳播學(xué)術(shù)成果具有重要意義。

熱點(diǎn)發(fā)現(xiàn)；向量空間模型；密度聚類算法

20世紀(jì)70年代以來(lái)，隨著中國(guó)經(jīng)濟(jì)的持續(xù)增長(zhǎng)和社會(huì)的不斷進(jìn)步，科學(xué)研究也取得了飛速發(fā)展，各種學(xué)術(shù)會(huì)議如雨后春筍般持續(xù)增多，為推動(dòng)我國(guó)經(jīng)濟(jì)發(fā)展和社會(huì)進(jìn)步發(fā)揮了重要作用。然而，當(dāng)用戶面對(duì)各類學(xué)術(shù)會(huì)議產(chǎn)生的大量學(xué)術(shù)共享資源時(shí)，想要快速獲取當(dāng)前的研究熱點(diǎn)并掌握相關(guān)領(lǐng)域的發(fā)展趨勢(shì)卻非常困難。顯而易見(jiàn)，通過(guò)人工整理分析獲取研究熱點(diǎn)的方式，對(duì)于如今海量信息資源來(lái)說(shuō)無(wú)疑是事倍功半甚至是極其低效的。所以，亟需通過(guò)高效的文本聚類技術(shù)將海量的學(xué)術(shù)資源信息分成若干有意義的類簇，實(shí)現(xiàn)資源熱點(diǎn)的自動(dòng)發(fā)現(xiàn)，從而使用戶無(wú)需自行搜索分析就可以準(zhǔn)確了解到當(dāng)前的研究熱點(diǎn)。

近年來(lái)，國(guó)內(nèi)外學(xué)者對(duì)該問(wèn)題進(jìn)行了大量研究，取得了豐碩的成果[1-6]。傳統(tǒng)的熱點(diǎn)話題發(fā)現(xiàn)通常采用基于增量K-Means算法和凝聚層次聚類算法。基于劃分的聚類方法雖然時(shí)間效率高但是不能處理噪聲，且需要人為地事先確定分類結(jié)果個(gè)數(shù)，即輸入?yún)?shù)k，這對(duì)于未知資源的聚類是不現(xiàn)實(shí)的；基于層次的聚類方法雖然不需要人為地事先確定分類結(jié)果個(gè)數(shù)，但是一旦某對(duì)象被劃分為某一類就不能更改，這對(duì)于聚類質(zhì)量有一定的影響；基于密度的聚類方法可以發(fā)現(xiàn)各種不同形狀的類簇、不需事先確定分類結(jié)果個(gè)數(shù)并且能夠識(shí)別噪聲，是綜合性能較好的聚類方法。針對(duì)學(xué)術(shù)會(huì)議資源的特點(diǎn)，筆者提出了一種基于密度的文本聚類方法實(shí)現(xiàn)資源熱點(diǎn)的自動(dòng)發(fā)現(xiàn)，即采用向量空間模型來(lái)結(jié)構(gòu)化資源文本；然后通過(guò)改進(jìn)的DBSCAN聚類方法自動(dòng)發(fā)現(xiàn)資源熱點(diǎn)，即通過(guò)合并具有明顯包含關(guān)系的特征詞以及解決公共資源對(duì)象鄰域的重復(fù)獲取問(wèn)題，從而在一定程度上提高聚類的準(zhǔn)確率和時(shí)間效率。

1 基于時(shí)間效率的DBSCAN算法改進(jìn)

1.1 文本表示模型(VSM)

20世紀(jì)60年代末由SALTON等提出的向量空間模型(vector space model，VSM)，搭建了自然語(yǔ)言與數(shù)學(xué)模型之間相互轉(zhuǎn)換的橋梁。其基本思想為：忽略詞語(yǔ)之間的相關(guān)性，用向量代表文本。只考慮語(yǔ)料統(tǒng)計(jì)，不考慮語(yǔ)義影響，簡(jiǎn)化了文本中關(guān)鍵詞的相互關(guān)系，從而能夠以向量之間的距離來(lái)判斷文本與文本之間相似與否。向量空間模型能夠應(yīng)用在信息檢索、文本分類等領(lǐng)域[7-10]。建立向量空間模型的基本過(guò)程為：不考慮特征項(xiàng)在文本中的出現(xiàn)順序以及相互之間的關(guān)系，從而文本被表示成若干個(gè)獨(dú)立的特征項(xiàng)集合。用此集合構(gòu)造出一個(gè)高維空間，該空間的維即為各個(gè)特征項(xiàng)，那么文本就可以用此空間中的向量表示。而特征項(xiàng)對(duì)于文本的重要程度即為特征項(xiàng)權(quán)重，該權(quán)重即為文本特征向量的值，然后通過(guò)計(jì)算文本向量之間的余弦相似度來(lái)判斷文本是否相似。向量空間模型將文本數(shù)據(jù)轉(zhuǎn)變成可計(jì)算的結(jié)構(gòu)化數(shù)據(jù)，從而通過(guò)計(jì)算向量之間的相似度解決文本之間的相似性問(wèn)題。

1.2 基于密度的聚類方法(DBSCAN)

DBSCAN(density based spatial clustering of applications with noices)是一種經(jīng)典的基于密度的聚類算法。當(dāng)在給定半徑Eps的區(qū)域內(nèi)對(duì)象數(shù)目超過(guò)密度閾值MinPts，就合并到相近的類中，從而實(shí)現(xiàn)密度相似的對(duì)象聚類。在DBSCAN算法中，定義數(shù)據(jù)集合D中的對(duì)象p和q之間的距離函數(shù)為dist(p,q)。

DBSCAN算法的目的是發(fā)現(xiàn)密度相連對(duì)象的最大集合。DBSCAN算法的步驟為：首先掃描輸入對(duì)象集合，判斷每個(gè)輸入對(duì)象是否為核心對(duì)象，并找到核心對(duì)象的Eps鄰域NEps(p)中直接密度可達(dá)集合；通過(guò)對(duì)核心對(duì)象的所有直接密度可達(dá)對(duì)象進(jìn)行密度可達(dá)對(duì)象的合并，從而找到密度相連對(duì)象的最大集合，實(shí)現(xiàn)基于密度的對(duì)象聚類。

1.3 基于時(shí)間效率的DBSCAN算法改進(jìn)

從DBSCAN算法可知，其聚類過(guò)程需要遍歷對(duì)象集中每個(gè)對(duì)象的Eps鄰域，從而保證每個(gè)對(duì)象都被標(biāo)記為某類。而在實(shí)際情況中很多對(duì)象的Eps鄰域都相互交叉，即某個(gè)對(duì)象同時(shí)存在于幾個(gè)對(duì)象的Eps鄰域中，如圖1所示[11]。

圖1 鄰域交叉的核心對(duì)象

圖2 改進(jìn)的DBSCAN算法流程圖

在圖1中，對(duì)象p、o和q都是核心對(duì)象，而這3個(gè)對(duì)象的Eps鄰域相互之間都要交叉，存在一些公共對(duì)象。筆者將針對(duì)公共對(duì)象的鄰域重復(fù)獲取問(wèn)題對(duì)DBSCAN聚類算法進(jìn)行改進(jìn)。具體思路為：在獲取對(duì)象集中各個(gè)對(duì)象的Eps鄰域前，先判斷此對(duì)象是否已被標(biāo)記為某個(gè)對(duì)象Eps鄰域中的對(duì)象，如果有則獲取該對(duì)象的Eps鄰域，否則判斷下一個(gè)對(duì)象，以此來(lái)避免對(duì)公共對(duì)象重復(fù)獲取其Eps鄰域，從而減少獲取次數(shù)和時(shí)間。改進(jìn)的DBSCAN算法流程圖如圖2所示。

2 基于改進(jìn)DBSCAN學(xué)術(shù)資源熱點(diǎn)發(fā)現(xiàn)

由改進(jìn)的DBSCAN算法可知，需要先將學(xué)術(shù)會(huì)議共享資源文本表示成向量空間模型，然后進(jìn)行基于文本相似度的密度聚類，從而獲取資源熱點(diǎn)。筆者將資源按學(xué)科類別分別聚類，這樣在一定程度上降低了語(yǔ)義的干擾，同時(shí)大大縮小聚類的規(guī)模，提高了聚類的時(shí)間效率。資源聚類過(guò)程如圖3所示。

圖3 資源聚類過(guò)程

(1)資源文本按學(xué)科分類：將目標(biāo)資源文本集合按學(xué)科進(jìn)行分類后，在某學(xué)科下進(jìn)行相應(yīng)的資源聚類，這種“先分類再聚類”在一定程度上提高了聚類的準(zhǔn)確性和時(shí)間效率。

(2)文本特征提?。好總€(gè)資源都有相應(yīng)的標(biāo)題、關(guān)鍵字和摘要等信息，這些信息都是作者細(xì)心提煉而成的，能夠反映出對(duì)應(yīng)資源的主要思想。而其中每個(gè)資源的關(guān)鍵字最為精煉重要，因此選取關(guān)鍵字作為資源的特征項(xiàng)。

(3)特征集縮減：根據(jù)關(guān)鍵字選取的特征項(xiàng)數(shù)目會(huì)隨著資源數(shù)目的增加而不斷增加，因此需要對(duì)獲取的特征集進(jìn)行縮減，取特征項(xiàng)在所有資源文本中出現(xiàn)次數(shù)較多的前n個(gè)組成特征集。n值需要根據(jù)目標(biāo)資源的個(gè)數(shù)進(jìn)行適當(dāng)選取，因?yàn)楫?dāng)n過(guò)大時(shí)，會(huì)引入冗余，使聚類準(zhǔn)確性不夠；而當(dāng)n過(guò)小時(shí)，包含的特征信息不夠，不能很好地區(qū)分不同的類。與此同時(shí)，刪減掉無(wú)意義的、詞頻較低的關(guān)鍵詞外，還需對(duì)具有明顯包含關(guān)系的關(guān)鍵詞進(jìn)行合并，從而在一定程度上提高聚類結(jié)果的準(zhǔn)確率。

(4)構(gòu)建特征項(xiàng)空間：根據(jù)縮減后的特征集建立特征項(xiàng)空間(T1，T2，…，Tn)。

(5)構(gòu)建特征向量空間模型：計(jì)算特征項(xiàng)空間中各個(gè)特征項(xiàng)Tk(1≤k≤n)對(duì)于各個(gè)文本的重要程度(即權(quán)重Wk(1≤k≤n))，從而建立向量空間模型。目標(biāo)資源文本用向量空間模型表示為D(T1，T2，…，Tn)。其中，D為目標(biāo)資源文本；Tk(1≤k≤n)為劃分D的多個(gè)獨(dú)立特征項(xiàng)。然后根據(jù)TF-IDF方法確定特征項(xiàng)Tk的權(quán)重Wk。

TF-IDF是一種應(yīng)用廣泛的權(quán)重計(jì)算方法，其綜合考慮了特征項(xiàng)在筆者文本以及所有文本中的詞頻。也就是說(shuō)，某特征項(xiàng)在筆者文本中越常出現(xiàn)，其重要性就越大，即與權(quán)重結(jié)果成正比；而包含某特征項(xiàng)的文本數(shù)量越多，其區(qū)分文本的能力就越低，即對(duì)某個(gè)文本的重要性就越小，從而與權(quán)重結(jié)果成反比。TF-IDF的具體計(jì)算公式為：

TF-IDF(Tk，D)=

(1)

筆者用Wk表示Tk的權(quán)重(1≤k≤n)，則文本D的向量表示為：

D=D(W1，W2，…，Wn)

(2)

(6)文本相似度計(jì)算：文本D1和D2之間的文本相似度Sim(D1，D2)通過(guò)向量之間的夾角余弦來(lái)衡量：

(8)聚類結(jié)果描述：將聚為一類的資源文本中具有最大詞頻的兩個(gè)特征值合成聚類結(jié)果，即發(fā)現(xiàn)的熱點(diǎn)名稱。

3 基于DBSCAN的資源熱點(diǎn)發(fā)現(xiàn)驗(yàn)證

將某屆會(huì)議的所有文獻(xiàn)資源作為測(cè)試樣本，通過(guò)對(duì)比人工分類結(jié)果與實(shí)驗(yàn)聚類結(jié)果，從而驗(yàn)證聚類算法的有效性。測(cè)試樣本中共有392個(gè)文獻(xiàn)資源，通過(guò)人工的方式分為5大熱點(diǎn)：有限元分析、數(shù)值模擬、神經(jīng)網(wǎng)絡(luò)與遺傳算法、建模、模糊PID與基線波動(dòng)。

評(píng)價(jià)聚類效果的常用指標(biāo)為查準(zhǔn)率和召回率，前者表示聚類結(jié)果中確實(shí)屬于某類別的對(duì)象與此類別的聚類結(jié)果中對(duì)象總數(shù)之比，后者表示確實(shí)屬于某類別的所有對(duì)象中，聚類得出相同判斷的對(duì)象所占的比例(亦稱查全率)。

DBSCAN算法中通常取MinPts=4，Eps的值在0～1之間(歸一化后的相似度)，筆者取為0.8，即文本之間的相似度大于等于0.8時(shí)可歸為一類。特征項(xiàng)空間的維數(shù)可根據(jù)實(shí)驗(yàn)確定一個(gè)合適的值，筆者設(shè)置為15。

先對(duì)經(jīng)過(guò)一般的特征詞縮減(未合并具有包含關(guān)系的特征詞)后的資源文本進(jìn)行聚類，具體結(jié)果如表1所示。

表1 基于密度聚類的資源熱點(diǎn)發(fā)現(xiàn)結(jié)果

由表1可知，某些類別的召回率比較低，通過(guò)分析人工分類結(jié)果和聚類結(jié)果可知，某些特征詞之間存在包含關(guān)系，實(shí)際上可以歸為一類，而聚類算法卻將其作為獨(dú)立的特征詞處理，以“神經(jīng)網(wǎng)絡(luò)與遺傳算法”為例，某些文本中相關(guān)的關(guān)鍵詞有“BP神經(jīng)網(wǎng)絡(luò)”、“人工神經(jīng)網(wǎng)絡(luò)”、“混合遺傳算法”和“改進(jìn)遺傳算法”等，擁有這些關(guān)鍵詞的文本也應(yīng)該歸為“神經(jīng)網(wǎng)絡(luò)與遺傳算法”這一類。因此，筆者將對(duì)基于密度聚類的資源熱點(diǎn)發(fā)現(xiàn)方法中“特征項(xiàng)縮減”這一部分進(jìn)行改進(jìn)，即除了刪減掉無(wú)意義的、詞頻較低的關(guān)鍵詞外，還對(duì)具有明顯包含關(guān)系的關(guān)鍵詞進(jìn)行合并，從而提高聚類的準(zhǔn)確率。合并具有包含關(guān)系特征詞后的基于密度聚類的資源熱點(diǎn)發(fā)現(xiàn)結(jié)果，如表2所示。

表2 合并具有包含關(guān)系特征詞后的資源熱點(diǎn)發(fā)現(xiàn)結(jié)果

由表2可知，熱點(diǎn)類別的召回率都有了一定的提升；還發(fā)現(xiàn)“神經(jīng)網(wǎng)絡(luò)、遺傳算法”熱點(diǎn)的查準(zhǔn)率有所下降，這是因?yàn)楹喜⒕哂邪P(guān)系的關(guān)鍵詞時(shí)不可避免地引入了其他有效的關(guān)鍵詞，但是其召回率大大提高，因此該方法總體上還是有效的。除此之外，改進(jìn)方法還產(chǎn)生了新的熱點(diǎn)類別，這是因此合并具有包含關(guān)系的關(guān)鍵詞后，使得某些對(duì)象集合滿足設(shè)定的密度閾值，從而產(chǎn)生新的熱點(diǎn)類。

筆者將驗(yàn)證基于時(shí)間效率改進(jìn)的DBSCAN算法，即解決DBSCAN聚類算法中公共對(duì)象的鄰域重復(fù)獲取問(wèn)題，改進(jìn)前后的算法聚類結(jié)果相同，而改進(jìn)前后的算法時(shí)間對(duì)比結(jié)果如圖4所示。由圖4可知，在保證聚類準(zhǔn)確性的前提下，改進(jìn)后的聚類時(shí)間因避免公共對(duì)象鄰域的重復(fù)獲取而縮短，并且隨著資源文本數(shù)量的增加而越發(fā)明顯。因此，基于時(shí)間效率的算法改進(jìn)對(duì)于平臺(tái)上大量資源文本的聚類是很有意義的。

圖4 DBSCAN算法改進(jìn)前后的聚類時(shí)間對(duì)比圖

通過(guò)上述的聚類效果評(píng)價(jià)和聚類時(shí)間結(jié)果可知，改進(jìn)后的基于密度的聚類方法能夠快速有效地自動(dòng)發(fā)現(xiàn)資源熱點(diǎn)，并且通過(guò)基于學(xué)科分類后再聚類、基于合并具有包含關(guān)系的特征項(xiàng)縮減以及解決DBSCAN聚類算法中公共對(duì)象的鄰域重復(fù)獲取問(wèn)題，可以在一定程度上保證了聚類的準(zhǔn)確性和時(shí)間效率。

4 結(jié)論

筆者針對(duì)學(xué)術(shù)會(huì)議產(chǎn)生的各類爆炸式信息資源，提出了一種基于資源關(guān)鍵字的資源聚類方法，實(shí)現(xiàn)了資源熱點(diǎn)的自動(dòng)發(fā)現(xiàn)，使學(xué)術(shù)會(huì)議共享資源的用戶無(wú)需自行搜索分析就能快速了解相關(guān)領(lǐng)域的研究熱點(diǎn)，提高了會(huì)議學(xué)術(shù)資源共享平臺(tái)的使用價(jià)值和友好性。但上述DBSCAN算法中輸入的參數(shù)都是通過(guò)多次實(shí)驗(yàn)選取的，如何快速確定適宜有效的參數(shù)將是下一步研究的問(wèn)題。

[1] 韓晨靖.基于標(biāo)題特征值密度聚類以及相似度計(jì)算的熱點(diǎn)發(fā)現(xiàn)研究[D].成都:電子科技大學(xué),2013.

[2] POULIQUEN B, STEINBERGER R, IGNAT C, et al. Multilingual and cross-lingual news topic tracking[C]∥International Conference on Computational Linguistics Ralf.[S.l.]:[s.n.], 2004:20-23.

[3] 郭建永,蔡永,甄艷霞.基于文本聚類技術(shù)的主題發(fā)現(xiàn)[J]. 計(jì)算機(jī)工程與設(shè)計(jì),2008,29(6):1426-1428.

[4] 李若鵬,李翔,林祥,等.基于DK算法的互聯(lián)網(wǎng)熱點(diǎn)主動(dòng)發(fā)現(xiàn)研究與實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展,2008,18(9):1-4.

[5] 羅云.互聯(lián)網(wǎng)海量信息中熱點(diǎn)信息主題的自動(dòng)發(fā)現(xiàn)[D].廣州:華南理工大學(xué),2013.

[6] 唐遠(yuǎn)華.Web新聞熱點(diǎn)信息的自動(dòng)發(fā)現(xiàn)及展示[D].廣州:華南理工大學(xué),2012.

[7] 陳飛宏.基于向量空間模型的中文文本相似度算法研究[D].成都:電子科技大學(xué),2011.

[8] 郭慶琳,李艷梅,唐琦.基于向量空間模型的文本相似度計(jì)算的研究[J].計(jì)算機(jī)應(yīng)用研究,2008,25(11):3256-3258.

[9] ZHANG G H, ODBAL. Sentence alignment for web page text based on vector space model[C]∥International Conference on Computer Science and Information Processing.[S.l.]:[s.n.], 2012:167-170.

[10] LIANG X, WANG D, HUANG M. Improved sentence similarity algorithm based on vector space model and its application in question answering system[C]∥IEEE International Conference on Intelligent Computing & Intelligent Systems.[S.l.]: IEEE, 2010:368-371.

[11] 李雙慶,慕升弟.一種改進(jìn)的DBSCAN算法及其應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(8):72-76.

ZHAO Nan:Engineer;China Shipbuilding Industry Corporation 722 Research Institute,Wuhan 430205,China.

Research on Academic Resources Hotspot Detection Based on Density Clustering Algorithm

ZHAONan,LIUZhen,SUNYanchao,ZOUPanpan,CHENDejun

In view of the explosive sharing of scholarly resources and how to get the current research hotspots quickly and accurately, it proposed an improved density-based clustering algorithm DBSCAN, to achieve the automatic discovery of academic resources hot spots. This algorithm can detect the academic resources hotspots automatically by combining keywords with obvious relationship to reduce feature items and it also can solve the problem that public resources object neighborhood's repeated acquisition, which can improve the accuracy and time efficiency to a certain degree. The results show that this method can detect the research hotspots in current related fields accurately and quickly. It helps to understand the current research hotspots of various disciplines, and dissemination of academic achievements of great significance.

hotspot detection; vector space model; density clustering algorithm

2095-3852(2016)06-0721-05

A

2016-07-07.

TP391

10.3963/j.issn.2095-3852.2016.06.017

收稿日期：趙楠(1987-)，女，山東泰安人，中國(guó)船舶重工集團(tuán)公司第七二二研究所工程師.