利用信息傳播特性的中文網絡新詞發現方法

孫立遠,周亞東,管曉宏1,

(1.清華大學智能與網絡化系統研究中心, 100084, 北京;2.國家計算機網絡應急技術處理協調中心, 100029, 北京;3.西安交通大學智能網絡與網絡安全教育部重點實驗室, 710049, 西安)

?

利用信息傳播特性的中文網絡新詞發現方法

孫立遠1,2,周亞東3,管曉宏1,3

(1.清華大學智能與網絡化系統研究中心, 100084, 北京;2.國家計算機網絡應急技術處理協調中心, 100029, 北京;3.西安交通大學智能網絡與網絡安全教育部重點實驗室, 710049, 西安)

針對已有方法識別出的網絡中文新詞生命周期短且很快不再為人們所用的問題,提出了一種基于信息傳播特性的中文新詞發現方法。該方法結合“新詞傳播范圍廣、持續時間長”的特點,從用戶覆蓋率、話題覆蓋率和新詞生命周期3個方面設計統計量;采用N-gram算法得到候選詞串列表;用基于詞頻和詞語靈活度的方法過濾垃圾詞串。實驗中以微博文本作為語料來源,與已有方法相比,用戶特性使得新詞識別的準確率提高了11%,話題特性使準確率提高了10%,時間特性使準確率提高了13%,綜合用戶、話題和時間的方法使準確率提高了16%。實驗結果表明:該方法中的每個特性都提高了中文網絡新詞識別的準確率,而且同時考慮3種特性的準確率比只考慮單一特性的高。

新詞發現;信息傳播;用戶行為;時間特性

隨著計算機網絡技術的迅猛發展,網絡日益成為社會信息發布和語言文化傳播的平臺,由此不斷產生新的網絡用語和熱門詞匯。一些認同度較高的網絡新詞逐漸被人們接受,并被擴充到漢語詞匯中。由于散落在海量網絡文本中的網絡新詞很難僅依靠人工進行查找、檢索和統計,因此如何快速有效地自動檢測網絡數據并發現新詞是一項亟需解決的問題。

目前,學術界對新詞的定義尚不統一。有研究認為,只要是以前沒有出現過的詞就是新詞[1-5]。但是,在這樣的定義下識別出的新詞絕大部分從出現到消失總的存在時間不超過5 d,生命周期很短;只有0.80%的新詞生命周期達到26 d以上,能夠被廣泛使用[3]。因此,考慮到信息傳播的特性,本文將存在時間久、使用范圍廣泛也作為判斷新詞的標準。

中文新詞發現方法一般包括2個步驟:一是劃分文本生成候選詞串,這是因為中文文本中詞與詞之間沒有明確的邊界;二是從候選詞串中發現新詞。

對于第一步劃分文本生成侯選詞串,大多數方法采用概率詞法分析系統(例如ICTCLAS等中文分詞軟件[2])或是基于詞典查找的方法,但是這種方法創建和維護詞典困難,而且因為新詞并不在詞典中,所以由基于詞典的分詞方法產生的候選詞串不一定包括所有可能的新詞,造成查全率的損失。

對于第二步從候選詞串中發現新詞,目前主要有兩類方法:基于規則的方法和基于統計的方法[1]。基于規則的方法是指結合構詞法、語義、詞性等語言學特征創建匹配模板發現新詞[6-7]。這類方法的優點是準確率高,但是規則維護困難,且適應性和移植性較差。基于統計的方法一般通過定義統計量將新詞發現看做模式識別的二分類問題,其中兩個類別分別代表“是新詞”和“不是新詞”。根據有無訓練語料,基于統計的方法可以分為有監督方法和無監督方法。有監督方法首先提取語料中的詞項特征,然后訓練分類器判斷是否是新詞,這類方法依賴于訓練語料和分類器設計;無監督的方法由于沒有訓練語料,因而采用設定統計量閾值的方法,如果一個候選詞串滿足統計量的閾值要求則被看作是新詞。常用的統計量有詞頻[8]、互信息[9]、上下文信息熵[10]等。這類基于統計的方法,其優點是具有很強的適應性和可移植性,但是需要大量語料進行統計而且準確率相對較低。另外,已有的統計量并不能體現新詞在傳播范圍和存在時間上的特點。

本文利用“新詞傳播范圍廣、持續時間長”的特點,提出基于信息傳播特性的中文新詞發現方法。該方法采用N-gram算法得到候選詞串列表,用基于詞頻和詞語靈活度的方法過濾垃圾詞串,并結合信息傳播特性從用戶覆蓋率、話題覆蓋率和新詞生命周期3個方面設計統計量。本文以近年來非常流行的網絡微博應用為示例,采用微博文本作為語料來源。

1 基于信息傳播特性的中文網絡新詞發現方法

1.1N-gram劃分詞串

因為微博文本的書寫風格靈活,形成了一些特有的微博表達方式和使用方法,例如URL、@符和表情符號等。這些微博表達方式中一般不包含新詞,所以本文首先對微博語料內容進行自動預處理,過濾掉不包含新詞的部分,以提高后續步驟的處理效率。其中,URL短鏈接字符串和@用戶名稱采用正則表達式過濾,表情字符串采用表情符號列表過濾。

為了避免中文分詞軟件查全率不高的缺點,本文采用N-gram算法[11]劃分預處理后的文本,順次將臨近的N個漢字聚集在一起形成一個候選詞串。考慮到新詞至少由2個漢字組成,而大于5個漢字的詞語比例非常小,本文設定閾值Nmax為5。為了提高處理效率,N-gram算法劃分詞串的同時統計每個詞串出現的次數,具體的實現過程如下。

輸入 預處理后的語料為T,詞串中的漢字個數為N,初始值Nmin,最大值為Nmax

輸出 候選詞串集合

步驟1 逐條讀取語料T中的微博,按空格切割成I個孤島詞串。

步驟2 掃描第i個孤島詞串,以連續N個字符的字符串S為候選,查找候選詞串集合,如果S在候選集合中,則S的頻次加1;如果S不在候選集合中,則將S加入候選集合。

步驟3i=i+1,如果i大于I,轉至步驟4,否則轉至步驟2。

步驟4N=N+1,如果N>Nmax則退出,否則轉至步驟1。

N-gram算法的優點是方法簡單,容易實現,查全率高,能保證所有新詞都在候選詞串中,但缺點是產生大量無意義的垃圾詞串。

1.2 基于詞頻和詞語靈活度的過濾方法

本文采用基于詞頻和詞語靈活度的方法過濾垃圾詞串,以便提高后續基于統計的方法的效率。

一個可以被視為詞的字符串,應該會被廣泛使用,因此在語料中也會頻繁出現。出現頻率低的詞串不大可能是有意義的詞串。91.4%的候選詞串出現次數小于等于2,因此本文設定詞頻過濾方法的閾值為2。

另外,根據中文的構詞規則,有些字符不經常出現在詞首或詞尾,這些字符被稱為停用字,包括詞首停用字和詞尾停用字。本文利用詞語的靈活度(即每個字符構成詞的概率)和設定的閾值比較,來發現停用字。用c表示待判斷的字符,·表示任意字符,c可能出現在詞首、詞尾或是詞中間,由此定義詞首停用字為

(1)

定義詞尾停用字為

(2)

式中:D(S)表示字符串S在語料中出現的次數;α是字符出現在詞首或詞尾的概率閾值。實驗中設定閾值為0.1,共抽取出約150個停用字,包括“是”“的”“了”“們”等。

對候選詞串過濾之后,本文采用統計的方法獲得最終的新詞結果。

1.3 基于信息傳播特性的統計方法

本文新詞發現的目標是使用范圍廣、存在時間長的未出現過的詞。結合信息傳播特性,有如下假設:如果使用某個詞的用戶數目越多,則說明該詞的使用范圍越廣;如果某個詞出現在越多的話題中,則說明該詞的使用范圍越廣;如果某個詞在一段時間內的頻度變化是遞增的,則說明該詞更有可能長時間存在。所以我們從用戶覆蓋率、話題覆蓋率和新詞生命周期3個方面分別設計了用戶特性統計量、話題特性統計量和時間特性統計量,最后綜合這3個方面提出了綜合統計量。

1.3.1 用戶特性統計量 每條微博都有一個唯一的發布者,即微博用戶,而一個用戶可以發布不止一條微博。同一個用戶的語言習慣固定,發表的微博內容在用詞上也有相似性,但是絕大多數用戶重復發帖的數目不多[12],所以由于同一個用戶語言使用習慣帶來的偏差并不大。可以認為使用某個詞的用戶數目越多,該詞的使用范圍越廣。

用三元組(w,m,u)表示候選詞w出現在微博m中且微博m的發布者是用戶u,用二元組(m,u)表示微博m的發布者是用戶u,設計用戶特性統計量為

(3)

式中:分母表示所有微博語料中不同用戶的數目;分子表示包含詞w的微博中不同用戶的數目。

1.3.2 話題特性統計量 如果某個詞在很多類別的話題中出現,說明該詞的使用范圍很廣。由于每個類別的話題數目不同,所以先對各類別的話題數歸一化然后再統計某個候選詞的話題特性統計量數值。

用三元組(w,m,k)表示候選詞w出現在微博m中且屬于話題k。話題的類別用K表示,設計話題特性統計量為

(4)

式中:|{k|k∈K,(w,m,k)}|表示出現詞串w的微博涉及的話題中屬于類別K的個數;D(K)表示類別K中話題的總數。

1.3.3 時間特性統計量 候選詞串如果存在時間越久越有可能是新詞,如果候選詞串的詞頻在增長則更有可能是新詞。考察候選詞串在一段時間內的頻度變化趨勢,通過評價函數給每個候選詞串打分,并據此設計時間特性統計量。

候選詞w的觀測區間為語料中該詞第一次出現的時間tw,f到該詞最后一次出現的時間tw,e,則候選詞w的觀測天數為nw=tw,e-tw,f+1。第i天的詞頻為ai(i=1,2,…,nw)。定義評價函數為

(5)

時間特性統計量定義為觀測區間內評價函數數值的和

(6)

1.3.4 綜合統計量 以上3種統計量從信息傳播特性出發,各有側重。為了提高新詞發現的整體準確率,同時考慮這3種統計量,提出了綜合統計量。由于每個特性統計量的取值范圍不同,不能直接相加,所以先對它們做歸一化,使每個統計量的取值都在[0,1]之間。采用如下的歸一化方法

(7)

式中:X∈{U,T,L}分別代表用戶特性統計量、話題特性統計量和時間特性統計量;Xmin表示變量X的最小取值;Xmax表示變量X的最大取值。

歸一化之后,綜合統計量為各個統計量的和

(8)

2 實驗與結果分析

2.1 數據介紹

利用新浪微博API,隨機選取新浪微博中粉絲數較多的賬號作為采集起點,采用“滾雪球”策略,采集了2013年3月1日到2013年5月31日期間這些賬號發布的每條微博的ID號、發布時間、發布人、內容等信息,經過去除垃圾微博等預處理后,構建了包括68 754名用戶、107萬條微博的原始數據集。

通過識別每條微博中的話題標簽生成研究中需要的話題數據集。在新浪微博中,用2個#標識一個話題,例如“#雅安地震#”和“#李宇春戛納行#”等。本文首先識別微博中出現的所有話題標簽,共218 619個,其中大部分話題包含的微博數很少,對新詞識別的作用也有限,因此本文進一步識別傳播范圍較廣的熱門話題數據。考慮到新浪微博會公布每天的前10個話題,實驗中選取2013年3月出現的微博數最多的300個話題標簽,合并屬于同一個話題的多個標簽,生成話題列表。然后,在全部微博(其中包括未使用#標識但提及某個話題的微博)中逐個搜索話題列表中的話題,如果一條微博中出現多個話題標簽,則標記第一個出現的話題標簽作為這條微博所屬的話題類別。另外,為了觀測到話題的完整生命周期,實驗中只保留了2013年3月2日以后出現的話題。最后,構建了包括36 038名用戶、19.5萬條微博、涵蓋106個最熱門話題的話題數據集。參照新浪微博的話題類別劃分方法,將106個熱門話題分為5類,包括社會新聞類、廣告公關類、網絡熱點類、電影電視類和其他類,見表1。

2.2 實驗設置

下面介紹實驗所用的評價指標和基準方法。

2.2.1 評價指標 因為微博數據量極大,很難標注出所有真實的新詞,所以本文采用無監督的方法,提出基于信息傳播特性的統計量,對每個候選詞打分,分值越高則越有可能是新詞,然后將每個候選詞的分值從大到小排序,獲得最終的新詞列表。

表1 話題類別概況

本文方法和對比方法的識別正確率采用了信息檢索領域常用的前N個結果的準確率(P@N)[3]來計算,具體來說就是對各個方法返回的前N個新詞結果進行人工判別,判斷‘是新詞’或者’不是新詞’,把‘是新詞’的比例作為前N個結果的準確率。N一般取值100,200,300等(相應的表示為P@100,P@200,P@300),以便減少人工標注的工作量。

2.2.2 基準方法 本文的基準方法包括:常見的經典統計量互信息量、鄰接熵,以及最新的基于詞內部結合度和邊界自由度的方法。通過和基準方法的對比,說明各方法性能的優劣。另外,為了說明本文方法的有效性,基準方法使用的數據源和本文方法的數據源一致,并采用了相同的預處理過程。

基準1 互信息量MI是衡量兩個事件之間相關性的信息度量。對于候選新詞w=c1c2…cn,如果它的兩個最長子串wleft=c1c2…cn-1和wright=c2c3…cn的相關性越高,說明w越可能是一個詞。本文使用文獻[9]的計算方法,計算公式如下

(9)

式中:p(w)是詞w在所有候選詞串中出現的概率。

基準2 鄰接熵BE利用信息熵來衡量候選新詞w的左鄰字符和右鄰字符的不確定性[10]。不確定性越高,說明其上下文環境越豐富。用字符x和字符y分別表示w的左鄰字符和右鄰字符,則w的左鄰熵Hleft(w)和右鄰熵Hright(w)的計算方法如下

(10)

(11)

鄰接熵BBE(w)定義為左鄰熵和右鄰熵中較小的

(12)

基準3 詞內部結合度和邊界自由度ICBF由文獻[13]提出,該方法對預處理后的語料進行中文分詞,統計“散串”,并計算詞內部的結合度(即互信息量),保留詞內部結合度大于閾值的詞語,最后計算詞語的左右邊界自由度(即左鄰熵和右鄰熵),把左右邊界自由度都大于閾值的候選詞作為新詞。在本文的語料上,使用該方法共得到1 982個新詞。為了更好地與本文方法比較并計算P@N值,對于給定的N,從這些新詞中隨機選擇N個,然后判斷新詞的準確率,重復做10次取平均值作為該方法的P@N值。

2.3 結果分析

實驗中各種方法采用同樣的新浪微博語料來發現中文新詞。表2列出了本文方法和基準方法識別中文新詞的準確率。對比結果顯示,本文提出的每個特性都比基準方法的準確率高,而且同時考慮3種特性的準確率比只考慮單一特性的高。具體來說,和基準方法1-MI相比,用戶特性使得前100個詞的識別準確率提高了11%,話題特性使準確率提高了10%,時間特性使準確率提高了13%,綜合用戶、話題和時間的方法使準確率提高了16%;前200個詞和前300個詞的識別準確率也有類似的提高。由于微博中的詞語使用較不規范,有大量曇花一現的詞語,基準方法中只根據上下文的文本信息不能有效地甄別詞語使用周期的差別,而且基準方法中BE比MI的準確率高,說明考慮上下文信息能提高新詞識別的準確率。

表2 新詞識別準確率的對比

另外,表2中準確率最高為36%,并不是很高。這是因為微博詞匯的隨機性比較大,本文在處理過程中為了保證不漏掉可能的新詞,不得不容忍了大量無意義詞語的出現,因而影響了整體正確率。本文方法的用途是為發現新詞提供數據輸出,以減輕人工從大量文本中篩選的工作量,后期還可以通過人工的方式提高準確率。

表3列舉了按統計量數值排名前20的結果中有意義的新詞,這些詞大多是近些年出現的,說明本文的中文網頁新詞自動獲取方法能有效地識別出網絡新詞。另外,前20個結果中兩字詞的準確率最高,四字詞的準確率最低。說明詞串過濾步驟中,四字詞的過濾效果最差,需要研究更有效的詞串過濾方法。

表3 新詞發現結果舉例

3 結 論

本文利用“新詞傳播范圍廣、持續時間長”的特點,提出基于信息傳播特性的中文新詞發現方法。該方法采用N-gram算法得到候選詞串列表,用基于詞頻和詞語靈活度的方法過濾垃圾詞串,并結合信息傳播特性從用戶覆蓋率、話題覆蓋率和新詞生命周期3個方面設計統計量,實現針對微博文本的新詞發現方法,實驗結果表明該方法提高了中文網絡新詞發現的準確率。

[1] 張海軍, 史樹敏, 朱朝勇, 等. 中文新詞識別技術綜述 [J]. 計算機科學, 2010, 37(3): 6-10. ZHANG Haijun, SHI Shumin, ZHU Zhaoyong, et al. Survey of Chinese new words identification [J]. Computer Science, 2010, 37(3): 6-10.

[2] 霍帥, 張敏, 劉奕群, 等. 基于微博內容的新詞發現方法 [J]. 模式識別與人工智能, 2014, 27(2): 141-145. HUO Shuai, ZHANG Min, LIU Yiqun, et al. New word discovery in microblog content [J]. Pattern Recognition and Artificial Intelligence, 2014, 27(2): 141-145.

[3] 蘇其龍. 微博新詞發現研究 [D]. 哈爾濱: 哈爾濱工業大學, 2013.

[4] 楊輝. 漢語新詞語發現及其詞性標注方法研究 [D]. 上海: 復旦大學, 2008.

[5] 鄒綱, 劉洋, 劉群, 等. 面向Internet的中文新詞語檢測 [J]. 中文信息學報, 2004, 18(6): 1-9. ZOU Gang, LIU Yang, LIU Qun, et al. Internet-oriented Chinese new words detection [J]. Journal of Chinese Information Processing, 2004, 18(6): 1-9.

[6] SUI Zhifang, CHEN Yirong. The research on the automatic term extraction in the domain of information science and technology [C]∥Proceedings of the 5th East Asia Forum of Terminology. Beijing, China: China National Institute of Standardization, 2002: 17-21.

[7] HIDEKI I. Japanese named entity recognition based on a simple rule generator and decision tree learning [C]∥Proceedings of the 39th Annual Meeting on Association for Computational Linguistics. Stroudsburg, PA, USA: Association for Computational Linguistics, 2001: 314-321.

[8] 羅盛芬, 孫茂松. 基于字串內部結合緊密度的漢語自動抽詞實驗研究 [J]. 中文信息學報, 2003, 17(3): 9-14. LUO Shengfen, SUN Maosong. Chinese word extraction based on the internal associative strength of character strings [J]. Journal of Chinese Information Processing, 2003, 17(3): 9-14.

[9] YE Yunming, WU Qingyao, LI Yan, et al. Unknown Chinese word extraction based on variety of overlapping strings [J]. Information Processing and Management, 2013, 49(2): 497-512.

[10]HUANG J H, POWERS D. Chinese word segmentation based on contextual entropy [C]∥Proceedings of the 17th Asian Pacific Conference on Language, Information and Computation. Piscataway, NJ, USA: IEEE, 2003: 152-158.

[11]孫立遠, 袁睿翕, 卞小丁. 一種中文網頁新詞自動獲取方法: 中國, ZL 200910237979.3 [P]. 2011-06-01.

[12]周亞東. 在線社會網絡熱點話題識別與動態傳播建模與分析研究 [D]. 西安: 西安交通大學, 2011.

[13]李文坤, 張仰森, 陳若愚. 基于詞內部結合度和邊界自由度的新詞發現 [J]. 計算機應用研究, 2015, 32(8): 51-55. LI Wenkun, ZHANG Yangsen, CHEN Ruoyu. New word detection based on inner combination degree and boundary freedom degree of word [J]. Application Research of Computers, 2015, 32(8): 51-55.

[本刊相關文獻鏈接]

楊攀,桂小林,安健,等.利用貝葉斯原理在隱私保護數據上進行分類的方法.2015,49(4):46-52.[doi:10.7652/xjtuxb 201504008]

李劉強,桂小林,安健,等.采用模糊層次聚類的社會網絡重疊社區檢測算法.2015,49(2):6-13.[doi:10.7652/xjtuxb 201502002]

李長路,王勁林,郭志川,等.兩階段密度意識子空間聚類模型.2014,48(10):108-114.[doi:10.7652/xjtuxb201410017]

李濤,肖南峰.應用相似度測量的圖離群點檢測方法.2014,48(8):67-72.[doi:10.7652/xjtuxb201408012]

陳家旭,唐亞哲,胡成臣,等.延遲容忍網絡中基于地點偏好的社會感知多播路由協議設計.2014,48(6):13-18.[doi:10.7652/xjtuxb201406003]

張賽,徐恪,李海濤.微博類社交網絡中信息傳播的測量與分析.2013,47(2):124-130.[doi:10.7652/xjtuxb201302021]

莫同,褚偉杰,李偉平,等.采用超圖的微博群落感知方法.2012,46(11):120-126.[doi:10.7652/xjtuxb201211022]

豆增發,高琳.利用膜粒子群優化和信息熵的醫學文本特征選擇.2012,46(4):45-51.[doi:10.7652/xjtuxb201204008]

陳剛,蔡遠利,穆靜,等.海量信息異常檢測問題的異常概率排序算法.2011,45(4):36-40.[doi:10.7652/xjtuxb201104 007]

劉京鑫,孫劍,孟德宇.基于視覺原理的分類算法.2010,44(10):116-119.[doi:10.7652/xjtuxb201010022]

馮少榮,張東站.高效的用戶訪問預測新算法.2010,44(4):28-33.[doi:10.7652/xjtuxb201004007]

李小虎,杜海峰,莊健,等.基于小世界原理的模型降階優化研究.2009,43(1):108-113.[doi:10.7652/xjtuxb200901024]

朱虎明,焦李成.基于免疫記憶克隆的特征選擇.2008,42(6):679-682.[doi:10.7652/xjtuxb200806007]

周亞東,孫欽東,管曉宏,等.流量內容詞語相關度的網絡熱點話題提取.2007,41(10):1142-1145.[doi:10.7652/xjtuxb 200710004]

杜海峰,李樹茁,Marcus W.Feldman,等.基于先驗知識與模塊性的網絡社區結構探測算法.2007,41(6):750-754.[doi:10.7652/xjtuxb200706026]

(編輯 武紅江)

A Method of Discovering New Chinese Words from Internet Based on Information Propagation

SUN Liyuan1,2,ZHOU Yadong3,GUAN Xiaohong1,3

(1. Center for Intelligent and Networked Systems, Tsinghua University, Beijing 100084, China;2. National Computer Network Emergency Response Technical Team/Coordination Center, Beijing 100029, China;3. MOE Key Laboratory for Intelligent Networks and Network Security, Xi’an Jiaotong University, Xi’an 710049, China)

A method of discovering new Chinese words from Internet based on information propagation is proposed to solve the problems that the recognizing results of existing methods always have short life cycles and will not be used again in soon. The method combines the characteristics of new words such as widely spreading and long lasting, and three statistics, i.e. coverage rate of users, coverage rate of topics and life cycle of a new word, are defined. TheN-gram algorithm is applied to generate candidates of new words, then the word candidates are filtered bade on word frequency and word flexibility. Experiments with the text of microblogs as corpus and comparisons with the existing methods show that the user statistic enhances the accuracy rate of recognizing new words by 11%, the topic statistic enhances the accuracy rate by 10%, and the time statistic enhances the accuracy rate by 13%. When the three statistics are combined, the accuracy rate is raised by 16%. It can be concluded that each single statistic considered by the proposed method can enhance the accuracy rate, and more accurate rate can be obtained by considering the combination of the three statistics rather than just considering one statistic.

new word discovery; information propagation; user behavior; temporal characteristics

2015-07-10。

孫立遠(1986—),女,博士生;周亞東(通信作者),男,博士,講師。

國家自然科學基金資助項目(61221063,61572397,61502383);陜西省自然科學基礎研究計劃資助項目(2015JM6298)。

時間:2015-09-21

10.7652/xjtuxb201512010

TP393

A

0253-987X(2015)12-0059-06

網絡出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20150921.1442.006.html