利用優(yōu)化的DBSCAN算法進(jìn)行文獻(xiàn)著者人名消歧

●任景華

（1．武漢大學(xué)新聞與傳播學(xué)院，武漢430072；2．昌吉學(xué)院中文系，新疆昌吉831100）

利用優(yōu)化的DBSCAN算法進(jìn)行文獻(xiàn)著者人名消歧

●任景華1,2

（1．武漢大學(xué)新聞與傳播學(xué)院，武漢430072；2．昌吉學(xué)院中文系，新疆昌吉831100）

人名歧義；人名消歧；DBSCAN；文獻(xiàn)著者

通過對(duì)文本聚類算法DBSCAN算法優(yōu)化對(duì)文獻(xiàn)著者人名進(jìn)行消歧，結(jié)果表明，相對(duì)標(biāo)準(zhǔn)文本聚類算法來說，優(yōu)化后的算法能取得更好的人名消歧效果。

人名歧義是一種身份不確定的現(xiàn)象，指的是文本中具有相同姓名的字符串指向現(xiàn)實(shí)世界中的不同實(shí)體人物。該現(xiàn)象普遍存在于文獻(xiàn)數(shù)據(jù)庫與網(wǎng)頁中，即不同的用戶擁有同一姓名的現(xiàn)象。其中，文獻(xiàn)著者歧義是人名歧義的一種，如在文獻(xiàn)數(shù)據(jù)庫中查詢某研究者所發(fā)表的文章時(shí)，現(xiàn)有的系統(tǒng)將會(huì)把與該研究同名的作者的所有文章返回，這樣會(huì)使得用戶對(duì)返回結(jié)果產(chǎn)生混淆。因此，對(duì)文獻(xiàn)著者進(jìn)行人名消歧，不僅可以幫助用戶搜索由特定作者撰寫的所有文章，而且也能排除其他同名作者的文章。

聚類是人名消歧中非常關(guān)鍵的一項(xiàng)任務(wù)，即將指向?qū)嶋H生活中同一個(gè)人的文檔聚為一類，于是，文本聚類技術(shù)是當(dāng)前人名消歧義的主要方法。常用的聚類方法有基于層次、基于密度與基于網(wǎng)格的聚類方法。已有的相關(guān)研究大多集中在如何探討選取特征以此實(shí)現(xiàn)人名消歧，而對(duì)通過優(yōu)化文本聚類方法以此來實(shí)現(xiàn)人名消歧探討較少。DBSCAN算法是一種典型的基于密度文本聚類算法，且在人名消歧中已取得較好的實(shí)驗(yàn)效果。所以，本文通過標(biāo)準(zhǔn)DBSCAN算法進(jìn)行優(yōu)化，以此提高文獻(xiàn)著者人名消歧的性能。

1 國內(nèi)外研究現(xiàn)狀

現(xiàn)有的消歧方法幾乎都是將問題轉(zhuǎn)化為機(jī)器學(xué)習(xí)［1］的相關(guān)分類和聚類問題。其中，基于分類思想的相關(guān)研究有Huang等［2］利用Online-SⅤM學(xué)習(xí)算法計(jì)算量文獻(xiàn)之間相似度，再用DBSCAN聚算法實(shí)現(xiàn)作者消歧。該類方法雖在進(jìn)行文獻(xiàn)著者消歧有較高的準(zhǔn)確度，但需人工構(gòu)建訓(xùn)練集，面對(duì)海量數(shù)據(jù)集進(jìn)行人工標(biāo)注幾乎是不可能完成的，從而限制了該方法在文獻(xiàn)著者消歧中的應(yīng)用。

利用聚類思想進(jìn)行人名消歧的相關(guān)研究有：楊欣欣等［3］針對(duì)現(xiàn)有很多基于特征的人名消歧方法不適用于文檔本身特征稀疏的問題，提出一種借助豐富的互聯(lián)網(wǎng)資源，使用搜索引擎查詢并擴(kuò)展出更多與文檔相關(guān)特征的方法；章順瑞等［4］利用層次聚類算法對(duì)新聞?wù)Z料中的中文人名進(jìn)行了消歧；王英師［5］探討了淺層語義分析特征在人名消歧義作用的基礎(chǔ)上，根據(jù)網(wǎng)頁的主題相關(guān)性和名字上下文噪音提出一種基于主題模型LDA和上下文摘要聚類相集合的Web人名消歧方法。宋文強(qiáng)等［6］嘗試了層次、K-means、AP三種不同的聚類消歧方法，并分析了各個(gè)聚類方法的優(yōu)缺點(diǎn)。

因聚類方法不需要訓(xùn)練數(shù)據(jù)，實(shí)用性較高，是當(dāng)前人名消歧的主流方法。以上研究主要從特征選擇方面對(duì)人名消歧問題進(jìn)行了研究，沒有對(duì)聚類方法進(jìn)行優(yōu)化。基于此，本文通過改進(jìn)DBSCAN以此提高人名消歧的實(shí)驗(yàn)效果。

2 DBSCAN算法優(yōu)化

2.1 傳統(tǒng)的DBSCAN算法

DBSCAN（Density-Based Spatial Clustering of ApplicationswithNoise）算法是一種基于密度的算法，［7］即通過采用迭代查找的方法，查找到所有直接密度可達(dá)的對(duì)象，也就是找到各個(gè)簇包含所有密度可達(dá)的對(duì)象。具體方法如下。（1）檢測(cè)數(shù)據(jù)庫中沒有被檢查到的對(duì)象P，如果P未被處理，則將其歸入某個(gè)簇標(biāo)記為噪聲點(diǎn)，再次檢查其領(lǐng)域EPs。若該鄰域中包含的對(duì)象小于MinPts，建立新簇C，將EPs中所有點(diǎn)加入該簇中。（2）檢查C中所有尚未被處理的對(duì)象q的鄰域EPs，若EPs包含的對(duì)象不少于MinPts個(gè)，將該領(lǐng)域中還未歸入到其他簇的對(duì)象加入到C中。（3）重復(fù)步驟2，繼續(xù)檢查C中未被歸類的對(duì)象，直到無新的對(duì)象加入到類簇C中為止。（4）重復(fù)步驟1－3，直到所有對(duì)象都能加入到某個(gè)類簇或者被標(biāo)記為噪聲數(shù)據(jù)。

該算法的主要優(yōu)點(diǎn)在于能發(fā)現(xiàn)任意大小形狀的類簇，并且其聚類效果受到噪聲點(diǎn)的影響比較小。但是，在數(shù)據(jù)量較大時(shí)該算法對(duì)主存的要求比較高，算法受到全局參數(shù)MinPts和EPs的影響；若參數(shù)選擇不當(dāng)，聚類質(zhì)量將降低；對(duì)于不均勻的數(shù)據(jù)集，由于參數(shù)MinPts和EPs是全局的，聚類的質(zhì)量也不理想。

2.2 優(yōu)化后的DBSCAN算法

本文通過對(duì)DBSCAN算法初始參數(shù)選擇的優(yōu)化，把對(duì)算法中EPs值的確定轉(zhuǎn)換為用戶對(duì)數(shù)據(jù)中噪音水平的估計(jì)，使參數(shù)的決定更具有客觀性，從而能夠在大容量數(shù)據(jù)集中實(shí)現(xiàn)人名消歧。其中，MinPts與EPs值的確定參見如下流程：

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集

本文的數(shù)據(jù)集是通過爬蟲程序從CNKⅠ（中國知網(wǎng)）數(shù)據(jù)庫中采集并經(jīng)過進(jìn)一步的處理獲得的數(shù)據(jù)。共采集了五所高校在CNKⅠ數(shù)據(jù)庫中22年的文獻(xiàn)，其相關(guān)文獻(xiàn)數(shù)見表1所示。其中，本文數(shù)據(jù)采集方式為：以這五所高校名為機(jī)構(gòu)名，時(shí)間限定在“1990～2012”年，然后獲得每篇文獻(xiàn)的英文標(biāo)題、英文作者、英文關(guān)鍵詞、英文摘要信息。最后，將所采集到的數(shù)據(jù)導(dǎo)入MySQL數(shù)據(jù)庫中。

鑒于本文只對(duì)五所高校教師做著者消歧，數(shù)據(jù)中重名信息量太少，為了更好地驗(yàn)證本文實(shí)驗(yàn)結(jié)果，將數(shù)據(jù)庫中的文獻(xiàn)作者名的拼音進(jìn)行人名縮寫，從而得到人名縮寫數(shù)據(jù)集。在很多情況下，若兩位作者的英文名縮寫相同，則認(rèn)為二者是同名，如“Li Ping”與“Li Peng”屬于同名作者。由于“同縮寫者”的個(gè)數(shù)要比同名者的個(gè)數(shù)多，這樣就提供了更豐富的數(shù)據(jù)集合，更能有效地驗(yàn)證人名消歧的算法。人名縮寫數(shù)據(jù)集合中的部分統(tǒng)計(jì)信息見表2。3.2實(shí)驗(yàn)過程

表1 五所高校分別在CNKⅠ數(shù)據(jù)庫中檢索到的文獻(xiàn)數(shù)

表2 人名縮寫數(shù)據(jù)集合的部分統(tǒng)計(jì)信息

文本預(yù)處理是進(jìn)行文本聚類的重要步驟。先對(duì)每篇論文的記錄（即英文標(biāo)題、英文摘要與英文關(guān)鍵詞）進(jìn)行分詞、英文詞干化、去除停用詞等操作，將每篇論文表示為向量形式。然后，在此工作基礎(chǔ)上，再進(jìn)行文本特征表示與文本之間的相似度計(jì)算。

（1）文本特征表示。采用向量空間模型對(duì)文檔特征進(jìn)行表示，利用所選取的特征將文檔形式化為n維空間向量，空間中的每一維表示選取的特征詞，其表示形式參見公式1所示。其中，wi表示第i個(gè)特征的權(quán)值，n表示特征向量維數(shù)。本文采用TF-ⅠDF值［6］來計(jì)算特征詞的權(quán)重值。使用向量空間模型表示文檔可極大地提高文檔可計(jì)算性，這也是向量空間模型在知識(shí)表示上的一個(gè)巨大優(yōu)勢(shì)。

（2）文本相似性計(jì)算。分別將每條文獻(xiàn)數(shù)據(jù)的title、keywords、abstract三字段進(jìn)行向量化。首先將文檔集分成只包含title或keywords或abstract字段值的三組文檔集，再按照文本信息特征詞建立的過程分別對(duì)三組文檔集進(jìn)行特征詞提取、生成倒排文件索引、建立特征向量，從而使得每篇文章分別由title、keywords、abstract三個(gè)字段的向量進(jìn)行表示。因此，兩文章的相似性就轉(zhuǎn)化為對(duì)加權(quán)合并后的三向量之間的相似性。文檔之間的相似度定義如公式2所示：

sim（D1,D2）=α×simtitle（D1,D2）+β×simkeywords

其中，simtitle（D1,D2）、simkeywords（D1,D2）、simabstract（D1,D2）分別表示兩文檔中title、keywords與abstract向量之間的相似性，本文分別利用歐式距離與余弦值計(jì)算兩向量之間的相似性。α、β表示權(quán)值，本文將其值分別設(shè)置為0.5、0.3。

（3）人名消歧聚類方法。將消歧聚類問題定義為：用P表示一篇文獻(xiàn)，PA表示作者名為A的所有文獻(xiàn)集合｛p1,p2，……｝。其中，屬于第i個(gè)名為A的作者的文獻(xiàn)子集為Ci=｛pk1,pk2，……｝，則人名消歧義的任務(wù)就是將文獻(xiàn)集合PA正確地劃分為C1,C2……Ck。本文主要采用改進(jìn)后的DBSCAN算法來實(shí)現(xiàn)人名消歧義，其具體實(shí)現(xiàn)過程如下。

輸入：同一人名（即人名縮寫形式相同）的N個(gè)待分類的文檔

輸出：K個(gè)不同人物個(gè)體的文檔集合D1，D2...Dk

①確定EPs及MinPts參數(shù)值

1）取MinPts=4，首先構(gòu)建描述數(shù)據(jù)對(duì)象集合的第4近鄰距離圖，然后去EPs略低于噪音水平百分比的值，最后再按照標(biāo)準(zhǔn)DBSCAN算法實(shí)現(xiàn)聚類；

2）利用各聚類結(jié)果中的和對(duì)象來構(gòu)建最小生成樹；

3）取MinPts=1，EPs為各個(gè)聚類結(jié)果所構(gòu)成的最小生成樹的最大邊值，再次按照DBSCAN算法進(jìn)行聚類。

②獲得直接可達(dá)的聚類

1）將每個(gè)文本作為數(shù)據(jù)點(diǎn)，遍歷所有數(shù)據(jù)點(diǎn)，判斷當(dāng)前數(shù)據(jù)點(diǎn)是否是核心點(diǎn)，且成為核心點(diǎn)需滿足的條件：大于或者等于MinPts個(gè)點(diǎn)到該點(diǎn)的距離小于EPs。

2）計(jì)算其他各點(diǎn)到當(dāng)前點(diǎn)的距離，如果距離小于EPs，則將當(dāng)前點(diǎn)歸并到指定點(diǎn)所在的類，并計(jì)數(shù)，如果數(shù)量大于MinPts，則當(dāng)前點(diǎn)可作為核心點(diǎn)，把當(dāng)前點(diǎn)及與該點(diǎn)歸入一類的點(diǎn)標(biāo)記為已分類。

3）對(duì)所有直接可達(dá)的聚類進(jìn)行合并，找出間接可達(dá)的聚類，即對(duì)（2）中聚類結(jié)果進(jìn)行合并，如果兩個(gè)類之間有交集，則合并為一類。

4）重復(fù)3）直至分類穩(wěn)定，即得到最后結(jié)果。

5)輸出代表K個(gè)不同人物的文檔集合。

3.3 實(shí)驗(yàn)結(jié)果評(píng)測(cè)與分析

（1）實(shí)驗(yàn)結(jié)果評(píng)測(cè)。為評(píng)價(jià)不同聚類方法在人名消歧方法中的表現(xiàn)，采用了信息檢索與文本聚類分析中的評(píng)測(cè)方法，如準(zhǔn)確率（Precision）、召回率（Recall）、F1值（F-measure）與純度（Purity）［6］來對(duì)最終實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)測(cè)。其中，表3與表4分別表示基于余弦距離公式的優(yōu)化后DBSCAN算法與標(biāo)準(zhǔn)DBSCAN算法對(duì)“Huang L”的人名消歧效果。經(jīng)過對(duì)兩表中相關(guān)評(píng)測(cè)指標(biāo)對(duì)比分析可知，針對(duì)縮寫名“Huang L”來說，優(yōu)化后DBSCAN算法的消歧效果優(yōu)于標(biāo)準(zhǔn)DBSCAN算法。另外，本文的整體實(shí)驗(yàn)效果參見表5、表6。

表3 基于余弦距離公式的優(yōu)化DBSCAN算法對(duì)“Huang L”的人名消歧效果

（2）實(shí)驗(yàn)結(jié)果分析。①從表5可以看出，針對(duì)人名消歧效果來說，優(yōu)化后的DBSCAN算法的實(shí)驗(yàn)效果優(yōu)于標(biāo)準(zhǔn)的DBSCAN算法。同時(shí)，由表6可以看出，優(yōu)化后的DBSCAN算法在運(yùn)行效率上也有顯著提高。另外，針對(duì)同一歐式距離計(jì)算公式，優(yōu)化的DBSCAN算法運(yùn)行時(shí)間比標(biāo)準(zhǔn)DBSCAN算法相比降低了20%左右。同時(shí)，內(nèi)存消耗上優(yōu)化的DBSCAN算法運(yùn)行時(shí)間與標(biāo)準(zhǔn)DBSCAN算法相比減少約17.8%。針對(duì)同一余弦距離計(jì)算公式，優(yōu)化后的DBSCAN算法運(yùn)行時(shí)間比標(biāo)準(zhǔn)DBSCAN算法降低18%，且內(nèi)存消耗降低了25%。

表4 基于余弦距離公式的標(biāo)準(zhǔn)DBSCAN算法對(duì)“Huang L”的人名消歧效果

表5 人名消歧結(jié)果的各評(píng)價(jià)指數(shù)比較

表6 各人名消歧方法的運(yùn)行時(shí)間及消耗內(nèi)存

②從表5可以看出，針對(duì)優(yōu)化后的DBSCAN算法來說，基于歐式距離的聚類純度比基于余弦距離的聚類純度高出7.6個(gè)百分點(diǎn)；從F1系數(shù)上來看，前者比后者高出10.1%。同理可獲得，針對(duì)標(biāo)準(zhǔn)DBSCAN算法來說，基于歐式距離的實(shí)驗(yàn)效果優(yōu)于基于余弦距離的方法。另從表6中可對(duì)比出，針對(duì)優(yōu)化后DBSCAN算法和標(biāo)準(zhǔn)DBSCAN算法來說，在時(shí)間消耗上和內(nèi)存消耗上，基于歐式距離優(yōu)于基于余弦距離的方法。因此，以上實(shí)驗(yàn)結(jié)果再次驗(yàn)證了在DBSCAN算法中，使用歐式距離來計(jì)算文本之間相似度的有效性。

通過以上比較分析，說明本文對(duì)算法的優(yōu)化取得了可觀的成效，同時(shí)在人名消歧方面發(fā)揮了較好的效果。另外，再次驗(yàn)證了基于DBSCAN聚類算法的文本距離公式使用歐式距離較佳。

4 實(shí)驗(yàn)總結(jié)與展望

本文主要通過改進(jìn)文本聚類算法DBSCAN算法來提高人名消歧的實(shí)驗(yàn)效果。其中，針對(duì)DBSCAN算法，本文主要對(duì)其參數(shù)進(jìn)行了優(yōu)化。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的DBSCAN算法其標(biāo)準(zhǔn)算法在人名消歧實(shí)驗(yàn)中取得更好的實(shí)驗(yàn)效果。另外，以上改進(jìn)的文本聚類方法除可用于文獻(xiàn)著者消歧外，還可用于領(lǐng)域?qū)＜野l(fā)現(xiàn)以及專家專長識(shí)別研究。但本文依然存在一些不足，在后續(xù)工作中需要深入探討的地方：（1）進(jìn)一步擴(kuò)展數(shù)據(jù)源，除探討文獻(xiàn)著者消歧外，還嘗試采集更加豐富的語料，以此探討網(wǎng)頁文本中的人名消歧義；（2）本文依然是針對(duì)英文文獻(xiàn)的著者消歧，后續(xù)工作將對(duì)中文文獻(xiàn)的著者人名消歧進(jìn)行探討；（3）針對(duì)DBSCAN算法，如何能最大化地減少其對(duì)初始值EPs及MinPts的依賴性，也是值得深入研究的問題。

［1］T M Mitchell．Machine learning［M］．New York: McGrawHill，1997.

［2］J Huang，et al．Efficient name disambiguation for large-scale databases［J］．Knowledge Discovery in Databases（PKDD2006），2006：536－544.

［3］楊欣欣，等．基于查詢擴(kuò)展的人名消歧［J］．計(jì)算機(jī)應(yīng)用，2012，32（9）：2488－2490.

［4］章順瑞，游宏梁．基于層次聚類算法的中文人名消歧研究［J］．現(xiàn)代圖書情報(bào)技術(shù)，2010（11）：64－68.

［5］王英帥．Web人名消歧方法的研究與實(shí)現(xiàn)［D］.蘇州：蘇州大學(xué)，2010.

［6］宋文強(qiáng)．科技文獻(xiàn)作者重名消歧與實(shí)體鏈接［D］.哈爾濱：哈爾濱工業(yè)大學(xué)，2011.

［7］王歸芝,王廣亮.改進(jìn)的快速DBSCAN算法［J］.計(jì)算機(jī)應(yīng)用，2009，9（29）：2505－2508.

G250.74；G254.922

A

1005－8214（2014）12－0061－04

任景華（1962－），女，博士，副研究館員，副教授，研究方向：傳播學(xué)與情報(bào)學(xué)相關(guān)理論與方法。

2014－03－24［責(zé)任編輯］閻秋娟