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

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

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

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

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

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

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

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

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

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

1 基于時間效率的DBSCAN算法改進

1.1 文本表示模型(VSM)

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

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

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

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

1.3 基于時間效率的DBSCAN算法改進

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

圖1 鄰域交叉的核心對象

圖2 改進的DBSCAN算法流程圖

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

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

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

圖3 資源聚類過程

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

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

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

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

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

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

TF-IDF(Tk，D)=

(1)

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

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

(2)

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

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

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

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

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

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

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

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

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

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

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

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

圖4 DBSCAN算法改進前后的聚類時間對比圖

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

4 結(jié)論

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

[1] 韓晨靖.基于標(biāo)題特征值密度聚類以及相似度計算的熱點發(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]. 計算機工程與設(shè)計,2008,29(6):1426-1428.

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

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

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

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

[8] 郭慶琳,李艷梅,唐琦.基于向量空間模型的文本相似度計算的研究[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] 李雙慶,慕升弟.一種改進的DBSCAN算法及其應(yīng)用[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-)，女，山東泰安人，中國船舶重工集團公司第七二二研究所工程師.