應(yīng) 毅，黃 慧，劉定一

(三江學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 南京 210012)

0 引 言

近年來，隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，微博、微信等新興微媒體受到大眾廣泛關(guān)注，被作為獲取時(shí)事要聞、發(fā)表個(gè)人意見的主要途徑。由于網(wǎng)絡(luò)熱點(diǎn)事件具有傳播速度快、范圍廣的特征，使得微媒體平臺(tái)在事件爆發(fā)后，能迅速積累大量的熱點(diǎn)信息。從微媒體的海量信息中挖掘熱點(diǎn)話題，有助于政府機(jī)關(guān)和相關(guān)部門及時(shí)掌握互聯(lián)網(wǎng)事件的主導(dǎo)權(quán)，積極傳播正能量，是當(dāng)前微媒體熱點(diǎn)引導(dǎo)工作面臨的重要任務(wù)。

對(duì)于熱點(diǎn)問題的發(fā)現(xiàn)，除了傳統(tǒng)的針對(duì)文本信息的聚類、分類等數(shù)據(jù)挖掘技術(shù)外，近年來也廣泛采用基于聯(lián)系的鏈接分析技術(shù)。PageRank[1-2]是進(jìn)行網(wǎng)頁權(quán)重計(jì)算的鏈接分析算法，起源于文獻(xiàn)引文分析方法[3]，主要思想是依次統(tǒng)計(jì)每個(gè)網(wǎng)頁的入度和出度，入度為當(dāng)前網(wǎng)頁被其他網(wǎng)頁引用的次數(shù)，且次數(shù)越多，說明該網(wǎng)頁的質(zhì)量越高；出度為當(dāng)前網(wǎng)頁引用其他網(wǎng)頁的次數(shù)，算法通過迭代的方式反復(fù)計(jì)算每個(gè)網(wǎng)頁的PageRank值[4]，直至達(dá)到平穩(wěn)分布為止。搜索引擎即通過PageRank算法分析互聯(lián)網(wǎng)上網(wǎng)頁間的相互引用關(guān)系，進(jìn)而衡量網(wǎng)頁的重要程度。

基于這一思想，學(xué)者們針對(duì)熱點(diǎn)話題的挖掘展開了廣泛的研究。文獻(xiàn)[5]將主題特征和時(shí)間因子引入PageRank算法進(jìn)行熱點(diǎn)分析，與傳統(tǒng)方法相比，獲得了更為可靠的分析結(jié)果。文獻(xiàn)[6]提出網(wǎng)頁時(shí)間權(quán)值的概念對(duì)熱點(diǎn)問題進(jìn)行分析，通過新方法彌補(bǔ)了傳統(tǒng)算法中新網(wǎng)頁總是處于“弱勢(shì)”地位的不足，強(qiáng)調(diào)最新發(fā)布網(wǎng)頁的重要性，對(duì)網(wǎng)頁的排序搜索起到了優(yōu)化的作用。文獻(xiàn)[7]引入時(shí)間維和空間維的主題因子，為網(wǎng)絡(luò)輿情處理提供主題樣本。

此外，學(xué)者們還從詞頻熱度、事件要素、情感趨勢(shì)等多個(gè)角度結(jié)合PageRank算法來分析熱點(diǎn)問題，都取得了一定的進(jìn)展[8-12]。

1 熱點(diǎn)發(fā)現(xiàn)研究現(xiàn)狀及文中工作

微博作為大眾獲取信息的重要來源，在熱點(diǎn)發(fā)現(xiàn)和輿情把控方面發(fā)揮了重要作用。使用傳統(tǒng)的PageRank算法對(duì)微博數(shù)據(jù)進(jìn)行熱點(diǎn)挖掘時(shí)，會(huì)產(chǎn)生以下幾個(gè)問題：

(1)微博不同于網(wǎng)頁，沒有頻繁的入度與出度，因此無法直接使用PageRank算法獲取每篇博文的重要程度。

(2)傳統(tǒng)算法未考慮文本之間的相似度，一般而言，相應(yīng)時(shí)間段內(nèi)某個(gè)主題內(nèi)容被提出的頻次越高，說明該主題內(nèi)容被關(guān)注的大眾越多，越易成為熱點(diǎn)話題。

(3)微博通常存儲(chǔ)了博文的轉(zhuǎn)發(fā)數(shù)、評(píng)論數(shù)和點(diǎn)贊數(shù)等數(shù)據(jù)，這些數(shù)據(jù)也應(yīng)被充分利用以發(fā)現(xiàn)熱點(diǎn)話題。

針對(duì)以上問題，文中通過網(wǎng)絡(luò)爬蟲工具對(duì)新浪微博的數(shù)據(jù)進(jìn)行爬取，并從多角度對(duì)數(shù)據(jù)加以分析，獲取更為可靠的熱點(diǎn)話題。文中的貢獻(xiàn)如下：

(1)引入微博用戶的社會(huì)地位，通常用戶的粉絲數(shù)越多，其社會(huì)地位越高，該用戶發(fā)表的博文影響力也越大，越易被傳播。文中將用戶的社會(huì)地位融入PageRank算法，將用戶之間擁有的粉絲信息形成鏈接結(jié)構(gòu)，通過計(jì)算每位用戶的PageRank值來衡量其社會(huì)地位，PageRank值越高，其社會(huì)地位也越高。

(2)將TF-IDF算法與余弦相似性算法結(jié)合進(jìn)行博文之間的相似度計(jì)算，若時(shí)間段內(nèi)某篇博文的相似文章數(shù)量較多，說明該時(shí)間段內(nèi)此話題被多個(gè)用戶關(guān)注，是熱點(diǎn)話題。

(3)充分利用博文的轉(zhuǎn)發(fā)數(shù)、評(píng)論數(shù)和點(diǎn)贊數(shù)等數(shù)據(jù)形成熱度指數(shù)，熱度指數(shù)越高，說明博文的影響力越大，越易形成熱點(diǎn)。

文中在PageRank算法和相似度計(jì)算技術(shù)的基礎(chǔ)上進(jìn)行改進(jìn)，提出熱點(diǎn)發(fā)現(xiàn)混合算法(hotspot detection hybrid algorithm based on PageRank and similarity computation，HDH-PRSC算法)。

2 HDH-PRSC算法

HDH-PRSC算法思想是通過計(jì)算每篇博文的評(píng)分獲取熱點(diǎn)信息，其中博文評(píng)分由三部分組成：微博用戶的社會(huì)地位、文本相似度分值和熱度指數(shù)。熱點(diǎn)分析時(shí)，將算法產(chǎn)生的三項(xiàng)值做加法運(yùn)算，得到的總評(píng)分越高，則博文成為熱點(diǎn)的可能性越大。

2.1 微博用戶的社會(huì)地位

基于PageRank算法的基本思想計(jì)算微博用戶的社會(huì)地位。

定義1(合法用戶)：U={U1,U2,…,Un}為所有微博用戶集合。如果滿足Ui∈U且1≤i≤n，則稱Ui為集合中的合法用戶，簡(jiǎn)稱用戶。

定義2(合法粉絲)：V={Vi1,Vi2,…,Vim}為用戶Ui的粉絲集合。如果滿足Vij∈V且1≤j≤m，則用戶Uj是用戶Ui的合法粉絲，簡(jiǎn)稱粉絲，記作Vij。

定義3(鏈接結(jié)構(gòu)圖)：每個(gè)用戶形成圖中的一個(gè)節(jié)點(diǎn)，如果用戶Uj是用戶Ui的粉絲，則形成Uj節(jié)點(diǎn)至Ui節(jié)點(diǎn)的一條有向邊，指向Ui的邊數(shù)稱為Ui的入度。同理，Ui也可作為其他用戶的粉絲，Ui節(jié)點(diǎn)指向其他用戶的邊數(shù)稱為Ui的出度。由節(jié)點(diǎn)和有向邊形成的圖稱為鏈接結(jié)構(gòu)圖。

基于PageRank算法的基本原理，微博用戶的社會(huì)地位計(jì)算方法如式1所示。

(1)

其中，Ui為某個(gè)待評(píng)價(jià)的用戶；j為用戶i的粉絲數(shù)；U為用戶總數(shù)；N(Vij)為用戶Ui的第j個(gè)粉絲節(jié)點(diǎn)的出度；PRstatus(Ui)為用戶Ui的社會(huì)地位值；PRstatus(Vij)為用戶Ui的粉絲的社會(huì)地位值；d為用戶之間彼此鏈接的阻尼系數(shù)，依據(jù)經(jīng)驗(yàn)，通常取值為0.85。

按照式1對(duì)用戶的社會(huì)地位值進(jìn)行迭代運(yùn)算，由于該算法是收斂的，直到用戶的社會(huì)地位值趨于平穩(wěn)，則計(jì)算結(jié)束。

通過算法獲取每位用戶的社會(huì)地位PageRank值并對(duì)PageRank值從高至低排序，同時(shí)計(jì)算所有用戶的PageRank值的平均值，記為AVG(PR)。為提高算法運(yùn)行效率，依據(jù)AVG(PR)，將用戶的社會(huì)地位劃分為三類：

e為用戶定義的閾值，通常情況下，消極用戶的發(fā)文成為熱點(diǎn)的概率較低，因此計(jì)算熱度時(shí)，不考慮消極用戶的發(fā)文，以此提高算法效率。

算法1：計(jì)算微博用戶社會(huì)地位的算法為GetUserStatus，其偽代碼如下：

輸入：鏈接結(jié)構(gòu)圖,e值；

輸出：PRstatus(Ui)(Ui∈ActiveUser &&Ui∈NormalUser)。

FOREACHUi∈U

BEGIN

Array[i,0]=GetPRstatus(Ui)//獲取每個(gè)用戶的社會(huì)地位的PageRank值

Array[i,1]=UserID(Ui)//獲取用戶的UserID賦值給數(shù)組

Array[i,2]=NULL//用戶初始的狀態(tài)為空

END

SORT(Array) //對(duì)用戶的社會(huì)地位從高到低排序

PRAvgStatus=AVG(PR) //計(jì)算所有用戶的社會(huì)地位均值賦值變量PRAvgStatus

FOREACHiin Array

BEGIN

IF(Array[i,0]>=PRAvgStatus+e)

Array[i,2]=ActiveUser

ELSE IF(Array[i,0]>=PRAvgStatus-e&& Array[i,0] <= PRAvgStatus+e )

Array[i,2]=NormalUser

ELSE

Array[i,2]=InactiveUser

END

DELETE(InactiveUser)

2.2 博文相似度指數(shù)

當(dāng)某篇博文具有較多的與其相似度較高的其他博文時(shí)，說明該博文可能是某時(shí)間段內(nèi)的熱點(diǎn)話題，被較多的用戶關(guān)注。因此，統(tǒng)計(jì)博文的相似度指數(shù)，也是熱點(diǎn)發(fā)現(xiàn)研究中的重要指標(biāo)。文中通過結(jié)合TF-IDF[13]方法和余弦相似性算法[14]獲得博文的相似度指數(shù)。

定義4(TF-IDF)：TF-IDF是用于評(píng)估一個(gè)字詞對(duì)于一個(gè)文件集或一個(gè)語料庫中的其中一份文件的重要程度。其中TF(term frequency)表示詞條在文章中出現(xiàn)的頻率；IDF(inverse document frequency)表示包含某個(gè)詞的文檔越少，則這個(gè)詞的區(qū)分度就越大，即IDF越大。

TF=某個(gè)詞在文章中出現(xiàn)的次數(shù)/文章總詞數(shù)

(2)

IDF=log[詞料庫的文檔總數(shù)/(包含該詞的文檔

數(shù)+1)]

(3)

TF-IDF=TF×IDF

(4)

通過統(tǒng)計(jì)TF-IDF的值，將每篇博文取值較高的前四個(gè)詞作為該篇博文的關(guān)鍵字。

定義5(余弦相似度)：余弦相似度利用向量空間中兩個(gè)向量夾角的余弦值作為衡量?jī)蓚€(gè)個(gè)體間差異的大小。文中將兩篇博文的關(guān)鍵字分別作為空間向量，計(jì)算相似度，公式如下：

(5)

其中，Xi為X文檔中第i個(gè)關(guān)鍵詞出現(xiàn)的次數(shù)；Yi為Y文檔中第i個(gè)關(guān)鍵詞出現(xiàn)的次數(shù)。通過式5計(jì)算向量的余弦值，余弦值越接近1，表明夾角越接近0，則兩篇文檔越相似。

統(tǒng)計(jì)博文相似度指數(shù)的過程分為三個(gè)步驟：

步驟一：利用TF-IDF方法獲取每篇博文的關(guān)鍵詞，并對(duì)關(guān)鍵詞出現(xiàn)的次數(shù)進(jìn)行排序，獲取Top-K個(gè)關(guān)鍵詞；

步驟二：依次遍歷博文，刪除不包含關(guān)鍵詞的博文；

步驟三：將剩余的博文對(duì)應(yīng)的關(guān)鍵詞按照余弦相似性的方法比較相似度，同時(shí)利用DBSCAN算法[15]對(duì)博文進(jìn)行聚類，統(tǒng)計(jì)相似博文的篇數(shù)。博文的相似度指數(shù)為每篇博文的相似篇數(shù)與總篇數(shù)的比值。

其中DBSCAN是一種基于密度的聚類算法，基本思想是在樣本區(qū)域內(nèi)任意選擇一個(gè)核心對(duì)象，以核心對(duì)象為中心計(jì)算與該核心對(duì)象的距離小于ε的其他所有對(duì)象，并將這些對(duì)象組合成一個(gè)類簇，將剩余對(duì)象作為輸入進(jìn)入下一輪算法的迭代，直到樣本空間中的所有對(duì)象都劃分為某個(gè)類簇，算法結(jié)束。文中的核心對(duì)象為算法輸入中的任意一篇博文，ε為Sim(X,Y)的取值，即博文相似度。

算法2：統(tǒng)計(jì)博文相似度指數(shù)的算法為GetSimScore，其偽代碼如下：

輸入：活躍用戶與一般用戶的博文文章，k值，相似度閾值m；

輸出：每篇博文的相似度指數(shù)。

FOREACHTi∈Title

BEGIN

Array[i,0]=GetKeyWords()//通過TF-IDF方法獲取文章關(guān)鍵字

Array[i,1]=TitleID(Ti)//獲取文章ID號(hào)

END

FOREACHjin KEYWORDS

ArrKeyWords[j]=COUNT(Array) //統(tǒng)計(jì)每個(gè)關(guān)鍵字出現(xiàn)的次數(shù)

string[] ArrImpKeyWords=SORT(ArrKeyWords,k)//獲取前k個(gè)重要關(guān)鍵字

FOREACHTi∈Title

BEGIN

IF !Ti.Contains(ArrImpKeyWords) //判斷博文Ti是否包含重要關(guān)鍵字

DELETE(Ti) //如果不包含重要關(guān)鍵字,則刪除博文

END

FOREACHTi∈Title

FOREACHTj∈Title

BEGIN

IF Sim(Ti,Tj)>=m

DBSCAN() //如果兩篇博文相似度達(dá)到閾值，則調(diào)用DBSCAN算法進(jìn)行聚類

END

FOREACHTi∈Title

SimScore(Ti) //獲取每篇博文的相似度指數(shù)

2.3 熱度指數(shù)

定義6(熱度指數(shù))：熱度指數(shù)由轉(zhuǎn)發(fā)數(shù)、評(píng)論數(shù)和點(diǎn)贊數(shù)的總和得到，熱度指數(shù)越高，說明此博文成為熱點(diǎn)的概率越大。

熱度指數(shù)的計(jì)算公式如下：

HotScore(Ti)=(轉(zhuǎn)發(fā)數(shù)+評(píng)論數(shù)+點(diǎn)贊數(shù))/(總轉(zhuǎn)發(fā)數(shù)+總評(píng)論數(shù)+總點(diǎn)贊數(shù))

(6)

2.4 HDH-PRSC算法的實(shí)現(xiàn)

博文的最終熱度綜合評(píng)分由微博用戶的社會(huì)地位、博文相似度指數(shù)和熱度指數(shù)三項(xiàng)分值獲得，如下：

Score(Ti)=αUserScore(Ui)+βSimScore(Ti)+

γHotScore(Ti)

(7)

其中，α、β和γ分別為微博用戶的社會(huì)地位、博文相似度指數(shù)和熱度指數(shù)的評(píng)分系數(shù)，且α+β+γ=1。

算法3：HDH-PRSC算法。

輸入：α值,β值,γ值；

輸出：博文綜合評(píng)分。

FOREACHTi∈Title

BEGIN

Ui=GetUserByTitle(Ti)//通過Ti獲取博文的用戶Ui

UserScore=GetPRstatus(Ui)

SimScore=SimScore(Ti)

HotScore=HotScore(Ti)

RETURNα*UserScore+β*SimScore+γ*HotScore

END

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

采用網(wǎng)絡(luò)爬蟲對(duì)新浪微博數(shù)據(jù)進(jìn)行采集，數(shù)據(jù)集包括2018年8月25日-2018年8月30日期間4 000個(gè)微博用戶共864 000條博文。刪除明星等名人的博文信息，隨機(jī)抽取部分?jǐn)?shù)據(jù)作為實(shí)驗(yàn)基礎(chǔ)，數(shù)據(jù)字段包含用戶UserID、性別、用戶粉絲信息、微博數(shù)、微博ID、微博內(nèi)容、微博發(fā)布時(shí)間、閱讀數(shù)、轉(zhuǎn)發(fā)數(shù)、評(píng)論數(shù)和點(diǎn)贊數(shù)。

實(shí)驗(yàn)操作時(shí)，用來給用戶分類的閾值e設(shè)置為AVG(PR)×0.2；計(jì)算博文相似度指數(shù)時(shí)，相似度閾值設(shè)置為0.6；式7中的α、β和γ均設(shè)置為1/3。由于實(shí)驗(yàn)數(shù)據(jù)規(guī)模較大，最終計(jì)算得到的用戶地位評(píng)分、相似度指數(shù)和熱度指數(shù)值均介于0.000 1～0.000 4之間。實(shí)驗(yàn)搜索到的熱度文章以及各項(xiàng)算法的評(píng)分結(jié)果如表1所示。

表1 熱度博文及評(píng)分

通過實(shí)驗(yàn)發(fā)現(xiàn)，單一算法(如：基于PageRank的用戶社會(huì)地位計(jì)算、結(jié)合TF-IDF和余弦相似性的博文相似度計(jì)算)得到的結(jié)果和HDH-PRSC算法得到的熱點(diǎn)博文排序不盡相同，E2事件在PageRank算法中排序第1，但在HDH-PRSC算法中排序第2；E3事件在相似度計(jì)算中排序第2，但在HDH-PRSC算法中排序第3。如圖1所示，單一算法所得結(jié)果相對(duì)比較片面，如PageRank算法將E2事件排名第1是因?yàn)樵摬┪牡陌l(fā)布者是央視財(cái)經(jīng)，算法認(rèn)為只要是央視財(cái)經(jīng)發(fā)布的博文一定都是熱點(diǎn)，而實(shí)際情況并非如此；同理，E3事件在相似度計(jì)算中排名第2是因?yàn)槠漕愃莆恼碌某霈F(xiàn)次數(shù)較多，這有可能是因?yàn)橐粋€(gè)小團(tuán)體內(nèi)多次轉(zhuǎn)發(fā)了某篇廣告，僅憑此項(xiàng)因素判斷熱點(diǎn)缺乏充足依據(jù)。HDH-PRSC算法綜合了發(fā)文用戶的社會(huì)地位、博文相似度指數(shù)、熱度指數(shù)三個(gè)因素，更加全面地從多個(gè)角度綜合評(píng)價(jià)博文的熱度，思想更為合理，其計(jì)算結(jié)果也要優(yōu)于單一算法。

圖1 熱點(diǎn)發(fā)現(xiàn)算法比較

4 結(jié)束語

基于用戶社會(huì)地位、博文相似度指數(shù)以及熱度指數(shù)對(duì)微博數(shù)據(jù)進(jìn)行分析，提出一種基于PageRank和相似度計(jì)算的熱點(diǎn)發(fā)現(xiàn)混合算法。該算法彌補(bǔ)了傳統(tǒng)算法中未考慮用戶社會(huì)地位和文本相似度的不足。實(shí)驗(yàn)結(jié)果表明，HDH-PRSC算法能夠更為合理地發(fā)現(xiàn)熱點(diǎn)話題。下一步將在更大規(guī)模的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)分析，并研究如何通過算法獲取文中α、β和γ評(píng)分系數(shù)的合理取值，以得到更為理想的實(shí)驗(yàn)效果。