趙星宇，趙志宏，王業(yè)沛，陳松宇

(南京大學(xué)軟件學(xué)院，南京210093)

(*通信作者電子郵箱zhaozhih@nju．edu．cn)

0 引言

微博這一概念最初于2006年由美國Twitter網(wǎng)站的創(chuàng)始人Evan Williams提出［1］。2009年，新浪將這一自媒體表現(xiàn)形式引入國內(nèi)。經(jīng)過幾年的成長，微博早已走進(jìn)了人們的日常生活;而伴隨著微博的迅猛發(fā)展，越來越多的垃圾信息也隨之出現(xiàn)，這些信息不僅影響著用戶體驗(yàn)，也對(duì)微博的相關(guān)研究工作造成了極大的負(fù)面影響［2］。

針對(duì)微博空間中的垃圾信息，傳統(tǒng)的發(fā)現(xiàn)方法主要依靠微博信息中的顯示統(tǒng)計(jì)特征:Zhang等［3］利用重復(fù)信息檢測(cè)提出一種局部性敏感散列算法來過濾大量相似的微博;丁兆云等［4］針對(duì)微博中關(guān)注網(wǎng)絡(luò)的有向特性，給出了郵箱網(wǎng)絡(luò)中局部三角形數(shù)量統(tǒng)計(jì)算法DirTriangleC，結(jié)合用戶博文數(shù)量和局部三角形比例發(fā)現(xiàn)隱式垃圾用戶;Thomas等［5］針對(duì)Twitter中出現(xiàn)的URL(Uniform Resource Locator)進(jìn)行處理來識(shí)別其中的推銷內(nèi)容。利用統(tǒng)計(jì)特征進(jìn)行計(jì)算具有一定的局限性:1)數(shù)據(jù)處理能力低，無法實(shí)現(xiàn)大數(shù)據(jù)量計(jì)算;2)計(jì)算主要依據(jù)經(jīng)驗(yàn)，檢測(cè)具有一定的滯后性。

Benevento等［6］將垃圾信息的檢測(cè)轉(zhuǎn)化為機(jī)器學(xué)習(xí)的分類問題，他們使用用戶行為(關(guān)注數(shù)、粉絲數(shù)、tweet條數(shù))和微博內(nèi)容(廣告關(guān)鍵詞、URL)等特征，采用支持向量機(jī)(Support Vector Machine，SVM)方法發(fā)現(xiàn)twitter平臺(tái)上的廣告內(nèi)容及廣告發(fā)布者;Wang［7］通過提取用戶特征、傳播特征等，采用樸素貝葉斯分類算法進(jìn)行訓(xùn)練，從而篩選出樣本中的垃圾信息。國內(nèi)學(xué)者也針對(duì)微博空間進(jìn)行了相應(yīng)的研究:李赫元等［8］針對(duì)垃圾用戶提出了基于用戶圖、用戶資料、微博內(nèi)容的3大類7種檢測(cè)特征，并最終使用支持向量機(jī)得到了較好的實(shí)驗(yàn)結(jié)果;趙斌等［9］針對(duì)微博中的反垃圾處理問題提出了基于重用檢測(cè)模型的垃圾用戶檢測(cè)算法，利用文本相關(guān)性和時(shí)間相關(guān)性對(duì)發(fā)帖行為進(jìn)行建模，而使用分類算法需要對(duì)大量的樣本數(shù)據(jù)進(jìn)行人工標(biāo)注，訓(xùn)練集大小有限，對(duì)此，馬彬等［10］提出了通過聚類實(shí)現(xiàn)微博話題檢測(cè)的思想，他們使用基于線索樹的雙層聚類方法進(jìn)行實(shí)驗(yàn)并取得了較好的效果。因此，本文使用聚類算法進(jìn)行計(jì)算，但由于實(shí)驗(yàn)?zāi)繕?biāo)對(duì)象為微博廣告發(fā)布者，作為微博用戶群體中的非正常用戶，采用具有離異點(diǎn)處理能力的基于密度的空間聚類(Density-Based Spatial Clustering of Applications with Noise，DBSCAN)算法更為合適。

對(duì)比現(xiàn)有研究，本文提出了以下幾點(diǎn)改進(jìn)方法:

1)提出核心微博序列概念。本文針對(duì)更為常見的在廣告微博中夾雜大量的普通微博這一現(xiàn)象進(jìn)行處理，提出核心微博概念，從大量混雜的微博中篩選出用戶核心主題和對(duì)應(yīng)的核心微博序列，用于之后的特征提取。

2)基于聚類算法處理多維微博特征。本文使用DBSCAN算法，通過每個(gè)樣本是否為噪聲點(diǎn)來判斷其是否為廣告用戶。由于使用聚類算法，從而避免了大量的人工標(biāo)注行為，使利用大數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)成為可能。

3)基于用戶粒度進(jìn)行檢測(cè)篩選?，F(xiàn)有研究多針對(duì)單條微博進(jìn)行判斷，而以單條微博為粒度的數(shù)據(jù)集數(shù)據(jù)量巨大，處理困難。本文以用戶為粒度，以檢測(cè)用戶是否為微博廣告發(fā)布者為目的，單條微博只會(huì)與同一用戶的其他微博進(jìn)行交叉計(jì)算，極大減少運(yùn)算量。

1 微博數(shù)據(jù)集及特征提取

1．1 新浪微博數(shù)據(jù)集

本文數(shù)據(jù)集來源于新浪微博，內(nèi)容更新至2015年11月12日。此數(shù)據(jù)集內(nèi)包含用戶數(shù)據(jù)和微博數(shù)據(jù)，都為結(jié)構(gòu)化數(shù)據(jù)，以CSV格式存儲(chǔ)。其中，weibo_users．csv文件描述用戶信息;lvX_weibo．csv文件描述微博發(fā)帖信息。

表1 weibo_users．csv用戶信息數(shù)據(jù)結(jié)構(gòu)Tab．1 Data structure of user information weibo_users．csv

表2 lvX_weibo．csv微博信息數(shù)據(jù)結(jié)構(gòu)Tab．2 Data structure of weibo information lvX_weibo．csv

1．2 核心微博序列提取

微博廣告發(fā)布者經(jīng)常使用各種手段掩蓋其廣告內(nèi)容，其表現(xiàn)特征有以下幾種:1)在廣告微博中夾雜大量的普通微博來稀釋其中的廣告特征，如表3所示;2)在某一時(shí)間段進(jìn)行廣告發(fā)布，其余時(shí)間段均表現(xiàn)為正常微博用戶。普通微博的存在會(huì)嚴(yán)重影響各個(gè)文本特征計(jì)算的準(zhǔn)確性。另一方面，微博廣告發(fā)布者大都圍繞一個(gè)或幾個(gè)類別的實(shí)體進(jìn)行宣傳。因此，本文引入基于關(guān)鍵詞的核心微博序列提取方法。

表3 廣告內(nèi)容夾雜普通內(nèi)容示例Tab．3 Examples of advertising content mixed with ordinary content

此處核心微博的定義為:與當(dāng)前用戶發(fā)帖內(nèi)容中高頻主題相關(guān)的微博。由于微博內(nèi)容長度限制，通常無法從中提取出確定唯一的主題，所以此處采用關(guān)鍵詞作為每條微博的主題，每條微博提取一個(gè)關(guān)鍵詞序列。使用各微博的關(guān)鍵詞序列，統(tǒng)計(jì)其中關(guān)鍵詞出現(xiàn)的詞頻，并對(duì)其中的近義詞進(jìn)行合并處理，得到關(guān)鍵詞的詞頻序列。由于同一微博用戶的微博主題可能會(huì)出現(xiàn)遷移，本文取關(guān)鍵詞詞頻序列中的前10位作為高頻關(guān)鍵詞，以保證能夠篩選出其中的廣告主題。最終，保留包含這10個(gè)關(guān)鍵詞或其近義詞的微博組成核心微博序列。

本文使用自然語言處理與信息檢索共享平臺(tái)(Natural Language Processing＆ Information Retrieval Sharing Platform，NLPIR)中文分詞系統(tǒng)提取關(guān)鍵詞，每個(gè)用戶的每條微博都會(huì)獲得一個(gè)關(guān)鍵詞列表。

其中:Useri是表示用戶i的微博序列，Wi表示其中第i條微博的關(guān)鍵詞列表，keyword為具體某個(gè)關(guān)鍵詞。統(tǒng)計(jì)每個(gè)用戶關(guān)鍵詞的詞頻，將近義詞的詞頻進(jìn)行合并后取最大詞頻的10個(gè)關(guān)鍵詞，組成用戶關(guān)鍵詞列表，并使用該列表查詢包含這10個(gè)關(guān)鍵詞的所有微博，最終得到該用戶的核心微博序列C:

使用核心微博序列進(jìn)行微博文本特征計(jì)算，可有效降低普通微博對(duì)計(jì)算結(jié)果的影響。由于排除了其中大量的普通內(nèi)容，使得文本相似特征和時(shí)間規(guī)律性更為顯著。

1．3 用戶特征選擇

特征選擇是聚類問題的關(guān)鍵部分，恰當(dāng)?shù)厥褂枚嗑S特征才能取得較為明顯的聚類效果。在本文中，由于實(shí)驗(yàn)對(duì)象為用戶而不是獨(dú)立的微博文本，所以在選取特征時(shí)，不僅選取了用戶所發(fā)微博對(duì)應(yīng)的文本特征，也加入了發(fā)布者的屬性特征。結(jié)合用戶屬性特征，不僅可以更接近用戶聚類的目的，更能解決僅針對(duì)微博文本詞匯計(jì)算相似度帶來的數(shù)據(jù)稀疏性問題。

1．3．1 文本特征

1)文本相似度。

由于微博廣告發(fā)布者具有較為單一的主題(購物、旅游、活動(dòng)等)，發(fā)帖人也具有比較固定的語言習(xí)慣，導(dǎo)致廣告微博相比普通微博具有較強(qiáng)的模板化特征，所以其文本相似度顯著高于普通微博。

在本文中，計(jì)算每個(gè)用戶的核心微博之間的余弦相似度并求平均值以作為該用戶的文本相似度。

其具體步驟如下:

(1)關(guān)鍵詞提取后的核心微博序列C。

(2)使用NLPIR對(duì)每條微博進(jìn)行分詞處理，得到分詞結(jié)果。

(3)計(jì)算每兩條微博W'i、W'j的余弦相似度。

(a)取分詞結(jié)果的并集。

(b)計(jì)算詞頻。

(c)寫出詞頻向量 Si、Sj。

(d)計(jì)算余弦相似度。

(4)計(jì)算相似度平均值

2)時(shí)序相似度。

通過對(duì)比各個(gè)用戶發(fā)帖時(shí)間序列，發(fā)現(xiàn)廣告發(fā)布者的核心微博與普通用戶相比具有明顯的時(shí)序規(guī)律性。分析原因有如下幾點(diǎn):a)微博廣告發(fā)布者為了廣告能夠獲得更好的收益，即獲得更高的關(guān)注度，通常會(huì)研究廣告發(fā)布的時(shí)間曲線，尋找最佳時(shí)間點(diǎn)將廣告投放出去;b)為了避免給用戶造成刷屏的感覺，廣告發(fā)布者通常會(huì)以一定的間隔進(jìn)行廣告投放;c)部分廣告實(shí)際為機(jī)器自動(dòng)發(fā)布，由人工設(shè)定內(nèi)容和時(shí)間間隔，因此機(jī)器投放的廣告微博會(huì)呈現(xiàn)極強(qiáng)的時(shí)序規(guī)律性。

針對(duì)上述問題，本文對(duì)發(fā)帖時(shí)間序列進(jìn)行分析，引入信號(hào)學(xué)中的白噪聲(white noise)檢驗(yàn)方法。白噪聲序列是沒有消息可提取的平穩(wěn)序列［11］。本文中，白噪聲檢驗(yàn)結(jié)果——統(tǒng)計(jì)量whiteNoise值越大表明時(shí)間序列隨機(jī)性越強(qiáng)，即為廣告發(fā)布者的可能性越低。其計(jì)算公式如下:

其中:whiteNoisei為第i個(gè)用戶的白噪聲顯著性水平，timei表示其發(fā)帖時(shí)間序列，K為差分階數(shù)。

1．3．2 用戶特征

1)廣告微博關(guān)鍵詞傾向性。

對(duì)比廣告微博和正常微博，廣告微博在詞語使用和語言組織上與正常微博相比具有一定的規(guī)律性。這是因?yàn)橐韵聨c(diǎn):(1)微博廣告發(fā)布者為了廣告能夠獲得更好的收益，即獲得更高的關(guān)注度，通常需要使用具有煽動(dòng)效果的詞語，如爆款、打折等。(2)由于廣告自身內(nèi)容決定某些詞語的出現(xiàn)頻率會(huì)明顯高于普通微博，如店鋪、購買等。

本文使用已標(biāo)注的廣告發(fā)布者數(shù)據(jù)，統(tǒng)計(jì)其關(guān)鍵詞詞頻，并將關(guān)鍵詞序列按照詞頻倒排，從而得到廣告微博關(guān)鍵詞序列A，但廣告微博中也存在許多微博常用語，這些常用語在普通微博中同樣高頻率存在。為此，本文使用同樣的方法針對(duì)普通微博統(tǒng)計(jì)出普通微博關(guān)鍵詞序列P。針對(duì)某一詞語的廣告微博關(guān)鍵詞傾向性，本文定義如下:

其中:IndexAi、IndexPi分別為詞語在序列A、P中的位置;Ii為該詞語的廣告微博關(guān)鍵詞傾向性。計(jì)算所有實(shí)驗(yàn)語料中所涉及的關(guān)鍵詞，按照關(guān)鍵詞傾向性排序，得到的前10位關(guān)鍵詞如表4所示。由表中數(shù)據(jù)可看出前10位關(guān)鍵詞都與購物類廣告有關(guān)，表明Ii作為廣告傾向性的衡量標(biāo)準(zhǔn)具有有效性。

表4 關(guān)鍵詞廣告傾向性排序Tab．4 Advertising tendency ranking of keywords

而針對(duì)某一用戶的廣告關(guān)鍵詞傾向性，本文使用上文提到的用戶關(guān)鍵詞序列W，并將W中每一個(gè)關(guān)鍵詞的廣告微博關(guān)鍵詞傾向性相加，得到用戶的廣告傾向值。

2)廣告元素?cái)?shù)量。

由于自身宣傳需要，微博廣告發(fā)布者通常需要多平臺(tái)多渠道宣傳，為了能夠促進(jìn)多平臺(tái)互通，許多廣告發(fā)布者會(huì)在個(gè)人介紹中加入多種聯(lián)系方式，包括網(wǎng)址URL、郵箱、手機(jī)號(hào)、QQ、微信等。而隨著個(gè)人隱私意識(shí)的不斷加強(qiáng)和垃圾信息對(duì)人們生活影響的不斷加深，普通用戶對(duì)于私密性較強(qiáng)的微信號(hào)、QQ等信息的保護(hù)意識(shí)也在加強(qiáng)，所以，普通用戶一般不會(huì)在個(gè)人信息中透露其他聯(lián)系方式。因此，會(huì)呈現(xiàn)出廣告發(fā)布者的個(gè)人介紹廣告元素遠(yuǎn)多于普通用戶的現(xiàn)象，如圖1所示。

圖1 廣告元素出現(xiàn)頻率對(duì)比Fig．1 Frequency contrast of advertising elements

圖1中可以看出，廣告發(fā)布者賬號(hào)對(duì)應(yīng)的個(gè)人介紹中，含有鏈接(URL)、QQ號(hào)、微信號(hào)、手機(jī)號(hào)的比例遠(yuǎn)高于普通用戶?；诖颂攸c(diǎn)，本文統(tǒng)計(jì)每個(gè)用戶個(gè)人介紹中推廣元素的數(shù)量，并以此作為聚類中的一項(xiàng)特征值。

2 聚類算法選擇及實(shí)驗(yàn)設(shè)計(jì)

2．1 聚類算法DBSCAN

如上文所述，微博廣告發(fā)布者在多個(gè)特征維度上與普通用戶相比具有較為明顯的差異;而考慮廣告發(fā)布者的內(nèi)部差異，不同的廣告發(fā)布者，其發(fā)帖習(xí)慣也有較大區(qū)別，這會(huì)導(dǎo)致其行為模型的多樣化。在這種情況下，為篩選出樣本中的微博廣告發(fā)布者，將其獨(dú)立為一個(gè)或多個(gè)簇顯然是不合適的，于是本文著眼于聚類問題中的離異點(diǎn)查找，即將聚類方法中的離異點(diǎn)標(biāo)注為廣告發(fā)布者?；谶@樣的要求，本文選取DBSCAN作為本實(shí)驗(yàn)所使用的聚類方法。DBSCAN算法為基于密度的聚類算法，與傳統(tǒng)的基于層次的聚類算法不同，該算法可以發(fā)現(xiàn)任意形狀的聚類簇，且可以在需要時(shí)輸入過濾噪聲的參數(shù)［12］。

2．2 實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)設(shè)計(jì)如圖2所示。

1)數(shù)據(jù)清洗:針對(duì)用戶，將發(fā)帖數(shù)小于10的用戶不納入計(jì)算范圍;針對(duì)單條微博，將微博中帶有轉(zhuǎn)發(fā)含義的字段及“@”符號(hào)后的內(nèi)容進(jìn)行刪除。

2)數(shù)據(jù)標(biāo)注:對(duì)用戶進(jìn)行手動(dòng)標(biāo)注以便于評(píng)判實(shí)驗(yàn)的準(zhǔn)確度，標(biāo)注分為微博廣告發(fā)布者和普通微博發(fā)布者兩類。微博廣告發(fā)布者的行為特征為:發(fā)布內(nèi)容帶有強(qiáng)烈的商業(yè)色彩或轉(zhuǎn)發(fā)大量低質(zhì)信息等。

3)參數(shù)選擇:由于DBSCAN中當(dāng)Eps過大或MinPts過小時(shí)，聚類結(jié)果將趨近于一個(gè)簇，所以本文定義Eps的范圍是0．1 ～1．5，MinPts的范圍是3 ～ 50。

圖2 實(shí)驗(yàn)流程Fig．2 Process of experiment

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

3．1 實(shí)驗(yàn)數(shù)據(jù)及評(píng)價(jià)標(biāo)準(zhǔn)

目前在微博過濾領(lǐng)域，尚無國際公認(rèn)的標(biāo)準(zhǔn)測(cè)試語料庫。本實(shí)驗(yàn)使用2755名微博用戶的310萬條微博數(shù)據(jù)，提取其中微博文本、用戶信息和傳播關(guān)系信息，并手動(dòng)標(biāo)注了2755名微博用戶屬性，共計(jì)2099名普通用戶及656名微博廣告發(fā)布者，所有的用戶標(biāo)注僅用來評(píng)判實(shí)驗(yàn)的準(zhǔn)確度，并未在實(shí)驗(yàn)中使用。所有實(shí)驗(yàn)都以此作為實(shí)驗(yàn)語料，在相同的實(shí)驗(yàn)環(huán)境下進(jìn)行。

本文采用準(zhǔn)確率(precision)、召回率(recall)、F值(F-measure)來評(píng)價(jià)算法性能［13］。計(jì)算公式如下:

其中:A為正確識(shí)別廣告發(fā)布者的數(shù)量，CA為實(shí)驗(yàn)結(jié)果中被標(biāo)記為廣告發(fā)布者的總量，TA為數(shù)據(jù)集中實(shí)際廣告發(fā)布者的總量。

3．2 特征值權(quán)重與聚類參數(shù)選取

實(shí)驗(yàn)中主要涉及聚類參數(shù)有:DBSCAN算法中的半徑(Eps)和以點(diǎn)P為中心的鄰域內(nèi)最少點(diǎn)的數(shù)量(MinPts)。此外，由于不同特征值對(duì)結(jié)果的影響程度不同，需要對(duì)各個(gè)特征值賦予權(quán)重。本實(shí)驗(yàn)對(duì)特征值權(quán)重與聚類參數(shù)的不同組合進(jìn)行分析，使用同一組數(shù)據(jù)，測(cè)試在不同特征值權(quán)重與聚類參數(shù)的組合下的準(zhǔn)確率、召回率和F值。測(cè)試結(jié)果如表4所示，其中P1、P2、P3、P4分別代表文本相似度、時(shí)序相似度、廣告微博關(guān)鍵詞傾向性、廣告元素?cái)?shù)量的權(quán)重，且P1+P2+P3+P4=1;P表示準(zhǔn)確率，R表示召回率，F(xiàn)表示F值。

通過大量實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)DBSCAN中的半徑(Eps)為0．1，以點(diǎn)P為中心的鄰域內(nèi)最少點(diǎn)的數(shù)量(MinPts)分別為4或20時(shí)，準(zhǔn)確率有較為良好的表現(xiàn)。這是因?yàn)楫?dāng)Eps過大或MinPts過小時(shí)，表示將一個(gè)樣本識(shí)別為離異點(diǎn)的條件趨于寬松，造成漏識(shí)別離異點(diǎn)，導(dǎo)致召回率降低;而MinPts過大會(huì)導(dǎo)致大量具有獨(dú)立特性的普通樣本被標(biāo)記為離異點(diǎn)，導(dǎo)致準(zhǔn)確率降低。當(dāng)Eps和MinPts分別為0．1和20時(shí)，結(jié)果顯示，當(dāng)P1、P2、P3、P4 分別取 0．3、0．2、0．4、0．1 時(shí)，F(xiàn) 值達(dá)到峰值0．95，表明文本相似度和廣告微博關(guān)鍵詞傾向性比對(duì)于結(jié)果的影響要優(yōu)于時(shí)序相似度和廣告元素?cái)?shù)量。但當(dāng)分別刪去時(shí)序相似度和廣告元素?cái)?shù)量進(jìn)行實(shí)驗(yàn)(即P2=0或P4=0)，結(jié)果顯示召回率急劇下降，說明這兩個(gè)特征對(duì)于識(shí)別廣告發(fā)布者具有重要作用。

表5 特征值權(quán)重與聚類參數(shù)對(duì)實(shí)驗(yàn)結(jié)果的影響Tab．5 Influence of eigenvalue weight and clustering parameters on experimental results

3．3 對(duì)比實(shí)驗(yàn)

本文提出了核心微博序列的概念，提取出微博序列中占較大比重的微博主題，從而去除由普通微博與廣告微博混雜帶來的影響。在此，本文分別使用原微博序列與核心微博序列進(jìn)行實(shí)驗(yàn)對(duì)比，使用相同區(qū)間的特征值權(quán)重與聚類參數(shù)進(jìn)行組合分析。實(shí)驗(yàn)結(jié)果顯示，當(dāng)特征值權(quán)重與聚類參數(shù)分別為表6所示的數(shù)值時(shí)，F(xiàn)值達(dá)到峰值。

表6 使用核心序列和原序列準(zhǔn)確率對(duì)比Tab．6 Comparison of accuracy between core sequences and original sequences

從表6可以看出，使用了核心微博序列的實(shí)驗(yàn)結(jié)果，其準(zhǔn)確率、召回率和F值均明顯高于使用原微博序列的實(shí)驗(yàn)結(jié)果。即可證明，使用核心微博序列可以有效地排除用戶微博序列中的噪聲干擾，提高聚類的準(zhǔn)確率。

4 結(jié)語

本文分析了中文廣告型微博的文本特征以及用戶特征，提出了一種廣告型微博發(fā)布者識(shí)別方法，算法效率較高，效果理想。與現(xiàn)有的微博文本過濾算法相比，創(chuàng)新地提出了核心微博序列的概念和聚類算法進(jìn)行實(shí)驗(yàn)，有效解決了分類算法帶來的數(shù)據(jù)標(biāo)注困難問題。而對(duì)比垃圾微博的過濾方法，本文著重關(guān)注其中的廣告微博，通過核心微博序列及多維特征提取，較為精確地過濾出微博用戶中的微博廣告發(fā)布者。這對(duì)于今后的研究，包括微博廣告發(fā)布者行為建模，情感分析等具有重要意義。

同時(shí)，由于微博空間信息量巨大，傳播速度快［14］，越來越多的數(shù)據(jù)必然會(huì)使算法效率降低，如何提升算法效率和針對(duì)微博數(shù)據(jù)流進(jìn)行聚類將成為接下來的工作重點(diǎn)。