基于聚類分析的微博廣告發(fā)布者識別

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

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

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

0 引言

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

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

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

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

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

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

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

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格式存儲。其中，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)在某一時間段進行廣告發(fā)布，其余時間段均表現(xiàn)為正常微博用戶。普通微博的存在會嚴重影響各個文本特征計算的準確性。另一方面，微博廣告發(fā)布者大都圍繞一個或幾個類別的實體進行宣傳。因此，本文引入基于關(guān)鍵詞的核心微博序列提取方法。

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

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

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

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

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

1．3 用戶特征選擇

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

1．3．1 文本特征

1)文本相似度。

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

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

其具體步驟如下:

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

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

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

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

(b)計算詞頻。

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

(d)計算余弦相似度。

(4)計算相似度平均值

2)時序相似度。

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

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

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

1．3．2 用戶特征

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

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

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

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

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

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

2)廣告元素數(shù)量。

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

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

圖1中可以看出，廣告發(fā)布者賬號對應的個人介紹中，含有鏈接(URL)、QQ號、微信號、手機號的比例遠高于普通用戶。基于此特點，本文統(tǒng)計每個用戶個人介紹中推廣元素的數(shù)量，并以此作為聚類中的一項特征值。

2 聚類算法選擇及實驗設(shè)計

2．1 聚類算法DBSCAN

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

2．2 實驗設(shè)計

實驗設(shè)計如圖2所示。

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

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

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

圖2 實驗流程Fig．2 Process of experiment

3 實驗與結(jié)果分析

3．1 實驗數(shù)據(jù)及評價標準

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

本文采用準確率(precision)、召回率(recall)、F值(F-measure)來評價算法性能［13］。計算公式如下:

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

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

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

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

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

3．3 對比實驗

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

表6 使用核心序列和原序列準確率對比Tab．6 Comparison of accuracy between core sequences and original sequences

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

4 結(jié)語

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

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