《微博熱點(diǎn)話題發(fā)現(xiàn)的算法設(shè)計(jì)案例6300字》

微博熱點(diǎn)話題發(fā)現(xiàn)的算法設(shè)計(jì)案例綜述目錄TOC\o"1-2"\h\u12826微博熱點(diǎn)話題發(fā)現(xiàn)的算法設(shè)計(jì)案例綜述 132611.1話題的演化流程 1269081.2微博熱點(diǎn)話題發(fā)現(xiàn) 2214031.3微博數(shù)據(jù)采集及處理 220411.1.1微博數(shù)據(jù)采集 2305301.1.2文本預(yù)處理 431771.4微博文本表示 5192911.5微博文本聚類 6238111.5.1聚類算法的選擇 680691.5.2Canopy算法的基本思想 622351.5.3K-means算法的基本思想 7136531.5.4Canopy-Kmeans算法的并行實(shí)現(xiàn) 8微博內(nèi)容的口語化嚴(yán)重并且文本格式不規(guī)范，為了減小數(shù)據(jù)稀疏帶來的影響需要過濾掉噪聲數(shù)據(jù)，從而使得到的微博文本數(shù)據(jù)盡可能的包含更多的信息量；其次對去除噪聲之后的數(shù)據(jù)文本進(jìn)行分詞和去除停用詞的操作，并對處理完成的文本進(jìn)行向量化；最后對文本進(jìn)行聚類生成熱點(diǎn)話題。1.1話題的演化流程微博熱點(diǎn)話題是指在某段時(shí)間內(nèi)引起大量微博用戶對相關(guān)微博進(jìn)行轉(zhuǎn)發(fā)、評論或點(diǎn)贊的話題。互聯(lián)網(wǎng)的普及使得現(xiàn)實(shí)社會中發(fā)生的幾乎所有重大事件都會在微博上被討論到，在表象上看話題的產(chǎn)生是偶然的，是突然爆發(fā)的，但背后的根源是微博用戶情緒的反應(yīng)和宣泄。和事件一樣，話題也有其產(chǎn)生、發(fā)展、衰落然后凋亡的周期，而話題熱度的持續(xù)時(shí)間就是話題的生命周期。事件發(fā)表在微博平臺上就標(biāo)志著話題的產(chǎn)生，但是由于每個事件的影響力和發(fā)生時(shí)環(huán)境的不同，話題產(chǎn)生之后一般都會有一個發(fā)展的階段，在這個階段中會經(jīng)過若干次轉(zhuǎn)發(fā)和評論，特別是粉絲量多、影響力大的關(guān)鍵用戶的參與會加速話題的發(fā)展。當(dāng)出現(xiàn)大量與事件相關(guān)的轉(zhuǎn)發(fā)、評論等數(shù)據(jù)信息后，就形成了熱點(diǎn)話題，標(biāo)志著事件發(fā)展到了高潮。微博話題的壽命普遍偏短，95%以上的微博話題壽命不能達(dá)到24小時(shí)，平臺的時(shí)效性、用戶對事件的新鮮度和其他事件的產(chǎn)生都影響著話題熱度的持續(xù)時(shí)間[58]。隨著時(shí)間的推移，用戶對該話題的關(guān)注度和參與度降低，話題熱度也隨之下降，話題開始衰落直至凋亡。話題熱度主要轉(zhuǎn)發(fā)數(shù)目和評論數(shù)目有關(guān)，本文采取如下的話題熱度計(jì)算方法[59]，如公式（3-1）所示。 （3-1）式中，表示話題的熱度，表示微博的轉(zhuǎn)發(fā)數(shù)目，表示第條微博的評論數(shù)量，表示博主發(fā)布該微博時(shí)的粉絲數(shù)目。由話題熱度計(jì)算公式，綜合考慮轉(zhuǎn)發(fā)數(shù)目、評論數(shù)目以及博主粉絲數(shù)目對微博熱度的影響，通過對話題的熱度進(jìn)行排序就可以得到話題熱度排行列表。1.2微博熱點(diǎn)話題發(fā)現(xiàn)微博熱點(diǎn)話題發(fā)現(xiàn)的方法大致如下：首先通過新浪微博API接口[60]對新浪微博的網(wǎng)頁數(shù)據(jù)進(jìn)行采集。由于微博內(nèi)容的口語化嚴(yán)重并且文本格式不規(guī)范，為了減小數(shù)據(jù)稀疏帶來的影響需要過濾掉噪聲數(shù)據(jù)，從而使得到的微博文本數(shù)據(jù)盡可能的包含更多的信息量；其次對微博文本數(shù)據(jù)做預(yù)處理操作，主要有分詞和去停用詞等；進(jìn)而對微博進(jìn)行文本表示，包括關(guān)鍵詞提取、文本向量化等步驟；最后對向量計(jì)算文本相似度進(jìn)行聚類，相同話題的文本劃分為一簇，完成熱點(diǎn)話題發(fā)現(xiàn)。發(fā)現(xiàn)熱點(diǎn)話題的具體過程如圖3-1所示：圖3-1微博熱點(diǎn)話題框圖Fig.3-1BlockDiagramofHotTopicDiscoveryinMicroblog1.3微博數(shù)據(jù)采集及處理1.1.1微博數(shù)據(jù)采集由于微博的活躍用戶更多是80、90后的年輕群體，且發(fā)表的微博博文內(nèi)容涉及的主題和表達(dá)形式并不固定，這為微博情感分析增加了難度。雖然微博文本的表達(dá)形式多種多樣，但歸根結(jié)底依舊是使用文本表達(dá)情感。新浪微博憑借著“短平快”的消息機(jī)制已成為國內(nèi)最受歡迎的平臺之一，使得越來越多的學(xué)者對其文本數(shù)據(jù)進(jìn)行研究。而對微博進(jìn)行分析的第一步，就是根據(jù)網(wǎng)絡(luò)爬蟲獲取所需要的數(shù)據(jù)。目前，對于新浪微博數(shù)據(jù)的采集，主要有兩種方式：一種是通過定制網(wǎng)絡(luò)爬蟲來獲取，另一種是使用新浪微博應(yīng)用程序接口（ApplicationProgrammingInterface，API）獲取數(shù)據(jù)。新浪微博對外提供了相對簡單的數(shù)據(jù)獲取方式，研究人員可以通過微博API的開放平臺實(shí)時(shí)獲取最新的微博數(shù)據(jù)。所以，本文采用調(diào)用新浪微博API接口的方式對微博數(shù)據(jù)采集。研究人員需要下載并配置軟件開發(fā)工具包（SoftwareDevelopmentKit，SDK）并填寫授權(quán)文件，在獲取到新浪微博的官方授權(quán)以后才可以進(jìn)行開發(fā)操作。本文選自Java版本的SDK進(jìn)行數(shù)據(jù)采集，步驟如下：（1）向微博官方平臺申請成為開發(fā)者并在微博中創(chuàng)建微博賬號，目的是為了獲取AppKey和AppSecret，經(jīng)微博官方授權(quán)后可以登陸進(jìn)入開發(fā)平臺；（2）進(jìn)入應(yīng)用信息設(shè)置OAuth2權(quán)限，在調(diào)用所有的API之前都需要進(jìn)行OAuth2驗(yàn)證，填寫授權(quán)回調(diào)頁；（3）下載微博JavaSDK并導(dǎo)入開發(fā)工具中進(jìn)行設(shè)置修改，之后在跳轉(zhuǎn)頁面獲取授權(quán)以后就可以隨意調(diào)用微博開放平臺開放的所有API接口。新浪微博的開放API接口對單位時(shí)間內(nèi)請求的頻數(shù)有一定的限制。當(dāng)請求頻數(shù)在規(guī)定的范圍之內(nèi)，則可以繼續(xù)調(diào)用API來采集數(shù)據(jù)；但是若超過頻數(shù)限制的過度調(diào)用或是非用戶主動行為頻繁調(diào)用微博開放接口，AppKey、用戶IP地址都會被判為惡意爬取用戶數(shù)據(jù)，從而觸發(fā)微博開放平臺的反爬蟲機(jī)制，之后系統(tǒng)會封禁應(yīng)用和IP的接口訪問權(quán)限，所有開放接口的請求都會被限制。為了解決這一問題，本文使用模擬登陸的方式對微博數(shù)據(jù)進(jìn)行抓取，微博API接口模擬登陸采集數(shù)據(jù)的流程如圖3-2所示。圖3-2新浪微博API獲取數(shù)據(jù)流程Fig.3-2DataAcquisitionProcessofSinaMicroblogAPI由于用戶發(fā)布的微博內(nèi)容比較隨意，表述比較口語化，而且數(shù)據(jù)不規(guī)范，存在很多的噪聲數(shù)據(jù)，因此在獲取到微博數(shù)據(jù)之后不可以直接對其進(jìn)行分析，需要對微博文本進(jìn)行過濾和清洗，過濾掉噪聲數(shù)據(jù)，使得文本能夠含有更多的信息。本文根據(jù)以下三個方面來處理微博數(shù)據(jù)：（1）刪除@等表示用戶進(jìn)行互動的標(biāo)識符。微博用戶在與人互動時(shí)，為了提醒被互動人經(jīng)常會使用“@”等符號，該符號并沒有任何語義信息，起到的是提醒作用和記錄作用。對于生成熱點(diǎn)話題和情感分析并沒有幫助，因此需要去除。（2）刪除文本中的URL鏈接。用戶在用發(fā)布博文表述觀點(diǎn)時(shí)，為了對發(fā)布的內(nèi)容進(jìn)行補(bǔ)充說明，經(jīng)常會在博文內(nèi)容中加入視頻和圖片內(nèi)容等的超鏈接。雖然微博后臺系統(tǒng)使用網(wǎng)址轉(zhuǎn)換機(jī)制將冗長的網(wǎng)址轉(zhuǎn)變?yōu)檎加米址麛?shù)較少的URL地址，但是博文的文本內(nèi)容已經(jīng)含有足夠的信息進(jìn)行特征信息提取，URL鏈接地址在文本表達(dá)時(shí)并沒有實(shí)際語義信息，因此需要將微博文本數(shù)據(jù)的URL鏈接去除。（3）刪除過短的微博文本數(shù)據(jù)。字?jǐn)?shù)較少的微博文本基本不能完整的表達(dá)一個主題或思想，大多是為了抒發(fā)即時(shí)的感情，過短的微博文本在進(jìn)行文本向量化時(shí)會造成數(shù)據(jù)稀疏，因此為了減少噪聲保證研究的準(zhǔn)確性需要刪除過短的微博文本。1.1.2文本預(yù)處理經(jīng)過去噪處理后的微博文本數(shù)據(jù)存入數(shù)據(jù)庫中，然后對其進(jìn)行文本預(yù)處理。微博文本預(yù)處理主要包括中文分詞和去停用詞兩部分。預(yù)處理之后的文本數(shù)據(jù)經(jīng)過情感特征提取和文本向量化，為后續(xù)的聚類生成話題和情感分析提供數(shù)據(jù)支持。中文分詞是中文自然語言處理中的基礎(chǔ)與關(guān)鍵。英文文本中詞與詞之間存在空格，分詞較為簡單，而中文句式結(jié)構(gòu)復(fù)雜，一個字也可以構(gòu)成詞，這使得中文文本處理起來較困難。目前比較成熟的分詞系統(tǒng)有清華大學(xué)的中文詞法分析工具包THULAC、ANSJ中文分詞系統(tǒng)、中國科學(xué)院的NLPIR詞法分析系統(tǒng)、Jieba分詞系統(tǒng)和哈工大的中文語言技術(shù)平臺LTP。本文使用的為ANSJ中文分詞系統(tǒng)，它是基于中科院的NLPIR中文分詞算法的JAVA開源實(shí)現(xiàn)，詞典由開源版的NLPIR所提供，分詞精度高達(dá)96%，基本上重寫了NLPIR的所有數(shù)據(jù)結(jié)構(gòu)和算法，并在已有的功能上進(jìn)行了部分的人工優(yōu)化。該系統(tǒng)的主要包括中英文分詞、詞性標(biāo)注、命名實(shí)體識別、網(wǎng)絡(luò)新詞識別，同時(shí)支持用戶詞典等功能。ANSJ支持UTF-8、GBK、BIG-5等不同編碼，支持Windows、Linux等操作系統(tǒng)。去停用詞是自然語言處理中必不可少的一步。中文文本在經(jīng)過分詞系統(tǒng)進(jìn)行分詞之后，原本連續(xù)的所有語句都按照分詞規(guī)則被切分成了詞語。在分詞結(jié)果中有許多沒有實(shí)際意義的詞，這些在文本中起輔助作用、沒有含義的詞就被稱為停用詞或功能詞。例如“的”、“了”等詞語，它們沒有具體的意義，不能體現(xiàn)文本所表示的內(nèi)容，將其刪除不僅可以降低維度還可以提高聚類準(zhǔn)確度。本文將網(wǎng)絡(luò)上現(xiàn)有的停用詞表進(jìn)行整合，經(jīng)過去重，根據(jù)微博文本特點(diǎn)進(jìn)行停用詞篩選，整理出一個相對全面的停用詞表，共包含詞語2694個。1.4微博文本表示使用機(jī)器學(xué)習(xí)算法進(jìn)行操作時(shí)，非結(jié)構(gòu)化的文本數(shù)據(jù)不能直接被計(jì)算機(jī)進(jìn)行處理，為了方便計(jì)算機(jī)處理文本特征，需要對文本特征進(jìn)行加權(quán)處理，將文本表示成計(jì)算機(jī)可以處理的結(jié)構(gòu)化數(shù)據(jù)，本文選用向量空間模型來表示文本。一條微博由若干個詞語組成的，每個詞語轉(zhuǎn)化成權(quán)值以后,每個權(quán)值可以看成向量中的一個分量，那么一條微博可以看成是維空間中的一個向量，這就是向量空間模型的由來。為確定向量空間模型的詞語對應(yīng)的權(quán)值，本文文本中的特征關(guān)鍵詞和特征權(quán)值采用TF-IDF算法。TF-IDF[61]是采用統(tǒng)計(jì)的計(jì)算方式來衡量每個詞語對于文本文件重要性。計(jì)算文檔中所有詞語的TF-IDF值，值越大則對文本的重要性和識別性越高，詞語越關(guān)鍵。本文采用Hadoop平臺實(shí)現(xiàn)，因此采用分布式計(jì)算模型MapReduce來完成TF-IDF的并行計(jì)算，結(jié)果格式為<key,value>鍵值對。首先在Job1中計(jì)算TF。map函數(shù)每次讀取一條文本（每條文本存成一行），分別計(jì)算詞語在文本中出現(xiàn)的次數(shù)，按照公式（2-1）計(jì)算輸出結(jié)果為Output_TF；然后在Job2中計(jì)算IDF。啟動Job2，分別計(jì)算包含指定詞的微博文本數(shù)目，輸出結(jié)果為Output_IDF；最后Job3中計(jì)算TF-IDF。先統(tǒng)計(jì)微博文本集的數(shù)目，按照公式（2-3）計(jì)算IDF，并與Job1的計(jì)算結(jié)果Output_TF相乘，最后計(jì)算出微博文本集中各個詞語的權(quán)值，輸出為Output_TF*IDF。TF-IDF值的具體實(shí)現(xiàn)思路如圖3-3所示：圖3-3TF-IDF的并行化實(shí)現(xiàn)Fig.3-3ParallelizationImplementationofTF-IDF1.5微博文本聚類1.5.1聚類算法的選擇在對微博進(jìn)行文本預(yù)處理并向量化表示之后，話題的生成還需要通過聚類算法來對數(shù)據(jù)進(jìn)行聚類。本文采用K-means算法進(jìn)行文本聚類，作為一種無監(jiān)督的方法，K-means算法聚類不僅實(shí)現(xiàn)簡單，聚類速度快，而且不需要預(yù)先對文本進(jìn)行類別標(biāo)注，對海量數(shù)據(jù)進(jìn)行聚類處理時(shí)依舊擁有良好的可伸縮性和高效性，因此具有較高的靈活性和自動化處理能力，是目前最常用的聚類算法。聚類的基本原理是計(jì)算出文本之間的距離，然后根據(jù)算法將距離接近的文本劃分到同一個簇。由于簇內(nèi)的文本距離接近，因此簇內(nèi)的文本相似度較高，簇與簇之間相似度較低。對微博熱點(diǎn)話題而言，對文本聚類之后，聚類結(jié)果的K個簇就是K個話題，話題簇內(nèi)的微博表達(dá)的是相同主題。K-means算法在進(jìn)行初始化操作時(shí)需要指定K個初始聚類中心，但是調(diào)用接口對微博數(shù)據(jù)進(jìn)行抓取時(shí)是無針對性的，文本內(nèi)容包含各個領(lǐng)域，生成簇的數(shù)目和中心點(diǎn)也并不固定。為了解決K-means算法依賴K值和初始聚類中心的問題，通過查閱大量文獻(xiàn)，本文在借鑒前人研究成果的基礎(chǔ)上結(jié)合微博特點(diǎn)和實(shí)際需要，采用Canopy-Kmeans[62]算法對文本進(jìn)行聚類。本文基于Hadoop分布式平臺，因此實(shí)現(xiàn)聚類算法的并行化可以極大的提高算法的運(yùn)行效率。1.5.2Canopy算法的基本思想Canopy算法[63]是McCallum在2000年提出的一種聚類算法，適用于海量高維數(shù)據(jù)預(yù)聚類分析。算法利用文本相似性將相似的數(shù)據(jù)對象放在一個canopy中，通過計(jì)算得到若干個canopy，canopy之間有些數(shù)據(jù)對象可以是重疊的，但所有的數(shù)據(jù)對象都會屬于一個canopy。和K-means算法不同，Canopy算法不預(yù)先指定聚類的個數(shù)，速度快但精度較低，因此經(jīng)常用在文本數(shù)據(jù)的預(yù)處理階段。Canopy算法首先需要設(shè)置兩個距離閾值（區(qū)域半徑）T1和T2，且T1>T2，算法執(zhí)行效率受Canopy閾值T1、T2影響較大，當(dāng)T1過大時(shí)，會使同一點(diǎn)屬于多個canopy，增加了計(jì)算開銷；當(dāng)T2過大時(shí)，會減少聚類的個數(shù)。具體實(shí)現(xiàn)步驟如下：（1）將數(shù)據(jù)以list的形式進(jìn)行存儲，原始狀態(tài)下還沒有分類。從list中隨機(jī)選取一個數(shù)據(jù)對象P（通常取list中的第一個）并從list中移除，根據(jù)距離公式計(jì)算數(shù)據(jù)對象P和所有canopy之間的距離。如果當(dāng)前不存在canopy，則把P作為一個canopy；（2）如果計(jì)算的距離小于T1，則把數(shù)據(jù)對象P加入這個canopy，作為弱關(guān)聯(lián)。如果距離小于T2，則把數(shù)據(jù)對象P從list移除，作為強(qiáng)關(guān)聯(lián)，因?yàn)閿?shù)據(jù)對象P與此canopy的中心距離足夠接近，避免重復(fù)加入到其他canopy。如果距離大于T1，則生成一個新的canopy；（3）重復(fù)上述步驟，直到所存數(shù)據(jù)的list為空，生成多個canopy，算法結(jié)束。Canopy算法的具體實(shí)現(xiàn)流程圖如圖3-4所示：圖3-4Canopy算法的流程圖Fig.3-4FlowChartofCanopyAlgorithm本文將向量化數(shù)據(jù)先進(jìn)行Canopy預(yù)聚類，利用Canopy算法對文本數(shù)據(jù)集進(jìn)行初步聚類得到若干個canopy。canopy的個數(shù)作為K-means算法的初始K值，每個canopy的中心點(diǎn)作為K-means的初始中心點(diǎn)。1.5.3K-means算法的基本思想K-means算法是一種基于距離的聚類算法，串行K-means算法的復(fù)雜度為，其中是微博文本數(shù)目，是算法的迭代次數(shù)，是聚類結(jié)果的簇個數(shù)。具體的實(shí)現(xiàn)步驟如下：（1）原始狀態(tài)下還沒有分類。在數(shù)據(jù)集中任意選擇K個點(diǎn)作為初始聚類中心點(diǎn)；（2）數(shù)據(jù)集中剩下的點(diǎn)根據(jù)距離公式分別計(jì)算到各個聚類中心點(diǎn)的距離，按照臨近原則將之劃分到最近的聚類中心點(diǎn)所在的類；（3）重新計(jì)算每個類中的點(diǎn)到該類中心點(diǎn)距離的均值，并將均值作為新的中心點(diǎn)；（4）重復(fù)2、3步驟，直到聚類中心不再變化或達(dá)到設(shè)置的迭代次數(shù)為止，算法結(jié)束。K-means算法的具體實(shí)現(xiàn)流程如圖3-5所示。圖3-5K-means算法的流程圖Fig.3-5FlowChartofK-meansAlgorithm本文使用余弦相似度來計(jì)算文本之間的相似度。根據(jù)余弦定理，如果夾角余弦的值越接近1，說明兩條文本內(nèi)容相似度越高，余弦相似度(CosineSimilarity)計(jì)算公式如公式（3-2）所示。 （3-2）式中，表示第篇文本第個詞的權(quán)值，同理。1.5.4Canopy-Kmeans算法的并行實(shí)現(xiàn)單機(jī)串行聚類處理速度會緩慢，花費(fèi)的時(shí)長較長，本文數(shù)據(jù)處理是基于Hadoop分布式系統(tǒng)實(shí)現(xiàn)的，利用分布式系統(tǒng)并行運(yùn)算可以有效的提高海量數(shù)據(jù)的執(zhí)行效率，因此需要實(shí)現(xiàn)聚類算法的并行化。算法的并行化實(shí)現(xiàn)主要包括Map操作和Reduce操作。Canopy聚類階段從HBase中讀取文本表示后的向量化數(shù)據(jù)，調(diào)用第一個MapReduce任務(wù)進(jìn)行Canopy預(yù)聚類，該算法的結(jié)果是生成若干個canopy和中心點(diǎn)。Canopy在初始化時(shí)需要設(shè)置的兩個距離閾值T1和T2，通常T1和T2的值可以根據(jù)操作經(jīng)驗(yàn)或交叉驗(yàn)證來選取，根據(jù)實(shí)踐經(jīng)驗(yàn)，本文分別設(shè)為0.018和0.017。在Map操作中，將待處理數(shù)據(jù)分配到各個節(jié)點(diǎn)上，在各個節(jié)點(diǎn)上map函數(shù)每次讀取一條數(shù)據(jù)，按照距離公式分別計(jì)算和其他canopy的距離并和T1、T2比較，輸出在該Map端上的所有canopy中心。在Reduce操作中，reduce函數(shù)將Map過程得到所有點(diǎn)再進(jìn)行canopy聚類，得到全部的canopy數(shù)目并輸出中心點(diǎn)，最后將結(jié)果存入HBase中。K-means并行化計(jì)算時(shí)，將預(yù)聚類得到的canopy的數(shù)量作為聚類算法初始化階段預(yù)指定的值K，canopy輸出的數(shù)據(jù)點(diǎn)作為初始聚類中心，每一次迭代都執(zhí)行一次MapReduce任務(wù)，最后得到的K即為話題數(shù)目。在Map操作中，map函數(shù)每次讀取一條樣本數(shù)據(jù)和K個聚類中心計(jì)算距離，并找出離的最近的中心點(diǎn)，然后以中心點(diǎn)為key，樣本數(shù)據(jù)為value，輸出格式為<key,value>鍵值對。在進(jìn)行大批量數(shù)據(jù)Map操作中會有大量中間數(shù)據(jù)產(chǎn)生，如果直接傳至Reduce操作會增大IO開銷和Reduce的壓力，通常在Map操作之后執(zhí)行一個Combine操作。一般認(rèn)為該操作是在Map端的預(yù)先進(jìn)行的Reduce合并，主要的作用是對單個Map任務(wù)輸出的鍵值對將key相同的歸并在一起，因此Combine的輸入是Map操作的輸出，Combine的輸出是Reduce操作的輸入。在Reduce操作中，reduce函數(shù)獲取到Combine的輸