●任景華

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

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

●任景華1,2

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

人名歧義；人名消歧；DBSCAN；文獻著者

通過對文本聚類算法DBSCAN算法優(yōu)化對文獻著者人名進行消歧，結果表明，相對標準文本聚類算法來說，優(yōu)化后的算法能取得更好的人名消歧效果。

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

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

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

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

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

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

2 DBSCAN算法優(yōu)化

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

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

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

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

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

3 實驗及結果分析

3.1 實驗數(shù)據(jù)集

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2）利用各聚類結果中的和對象來構建最小生成樹；

3）取MinPts=1，EPs為各個聚類結果所構成的最小生成樹的最大邊值，再次按照DBSCAN算法進行聚類。

②獲得直接可達的聚類

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

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

3）對所有直接可達的聚類進行合并，找出間接可達的聚類，即對（2）中聚類結果進行合并，如果兩個類之間有交集，則合并為一類。

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

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

3.3 實驗結果評測與分析

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

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

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

表4 基于余弦距離公式的標準DBSCAN算法對“Huang L”的人名消歧效果

表5 人名消歧結果的各評價指數(shù)比較

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

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

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

4 實驗總結與展望

本文主要通過改進文本聚類算法DBSCAN算法來提高人名消歧的實驗效果。其中，針對DBSCAN算法，本文主要對其參數(shù)進行了優(yōu)化。實驗結果表明，改進的DBSCAN算法其標準算法在人名消歧實驗中取得更好的實驗效果。另外，以上改進的文本聚類方法除可用于文獻著者消歧外，還可用于領域?qū)＜野l(fā)現(xiàn)以及專家專長識別研究。但本文依然存在一些不足，在后續(xù)工作中需要深入探討的地方：（1）進一步擴展數(shù)據(jù)源，除探討文獻著者消歧外，還嘗試采集更加豐富的語料，以此探討網(wǎng)頁文本中的人名消歧義；（2）本文依然是針對英文文獻的著者消歧，后續(xù)工作將對中文文獻的著者人名消歧進行探討；（3）針對DBSCAN算法，如何能最大化地減少其對初始值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］楊欣欣，等．基于查詢擴展的人名消歧［J］．計算機應用，2012，32（9）：2488－2490.

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

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

［6］宋文強．科技文獻作者重名消歧與實體鏈接［D］.哈爾濱：哈爾濱工業(yè)大學，2011.

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

G250.74；G254.922

A

1005－8214（2014）12－0061－04

任景華（1962－），女，博士，副研究館員，副教授，研究方向：傳播學與情報學相關理論與方法。

2014－03－24［責任編輯］閻秋娟