肖永磊，劉盛華，劉 悅，程學(xué)旗,趙文靜,任 彥，王宇平

(1. 中國(guó)科學(xué)院 計(jì)算技術(shù)研究所，北京 100190；2. 中國(guó)科學(xué)院大學(xué)，北京 100190；3. 西安電子科技大學(xué)計(jì)算機(jī)學(xué)院，陜西 西安 710126；4. 國(guó)家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心，北京 100029)

1 引言

隨著Web2.0的發(fā)展，微博、論壇、照片分享網(wǎng)站Flicker等社會(huì)化媒體已深入人們的日常生活，其中衍生出來的標(biāo)簽推薦、新聞推薦、問答、評(píng)論等應(yīng)用產(chǎn)生了大量的網(wǎng)絡(luò)短文本。社會(huì)化媒體上的短文本按其時(shí)間屬性組織形成的消息流，包含著網(wǎng)民們的許多思想觀念與傾向，對(duì)其進(jìn)行深入的挖掘有重大的應(yīng)用價(jià)值和學(xué)術(shù)意義。然而，文本消息的不完整性、海量性和動(dòng)態(tài)性導(dǎo)致文本消息流的話題發(fā)現(xiàn)、傾向性分析和熱點(diǎn)信息挖掘等數(shù)據(jù)挖掘任務(wù)變得十分困難。本文提出了一種新的短文本語義概念擴(kuò)展方法，可以去除短文本的噪聲和增加短文本的內(nèi)容特征，可以作為其他數(shù)據(jù)挖掘方法的補(bǔ)充。由于社會(huì)化媒體短文本的多樣性，本文選擇了應(yīng)用較多的微博作為實(shí)驗(yàn)數(shù)據(jù)來源，來說明論文提出的方法。

微博作為新的信息交流平臺(tái)，得到快速的發(fā)展，并逐漸成為用戶群最龐大、最活躍的網(wǎng)絡(luò)媒體之一。Twitter最近幾年用戶數(shù)量突飛猛進(jìn)，已經(jīng)成為最大的在線微博平臺(tái)，擁有超過6 500萬的用戶，每天超過2億條的微博。據(jù)報(bào)告[1]顯示，2011年在中國(guó)已經(jīng)有14%的互聯(lián)網(wǎng)用戶開始使用微博，并呈逐年上升的趨勢(shì)。微博傳播迅速，極大地方便了人們交流，同時(shí)也帶來信息過載問題。由于人們時(shí)間和能力有限，往往不能及時(shí)有效地獲取自己感興趣的信息。微博產(chǎn)生的海量信息已經(jīng)成為多種應(yīng)用的重要信息源，比如新聞話題發(fā)現(xiàn)和追蹤[2]，廣告投放，個(gè)性化內(nèi)容推薦等。Takeshi[3]等首先利用用戶tweets的關(guān)鍵詞信息，tweets長(zhǎng)度，上下文等特征構(gòu)建一個(gè)分類器，將Twitter用戶看成一個(gè)傳感器，采用了卡曼濾波算法和粒子濾波算法預(yù)測(cè)地震事件發(fā)生的地點(diǎn)。

不同于傳統(tǒng)的長(zhǎng)文本，以微博為代表的社會(huì)媒體短文本具有以下特征：

1) 用語大多隨意，具有不規(guī)范性[4];

2) 長(zhǎng)度有限，使其具有天然的極稀疏性，很難提取出有效的內(nèi)容特征[5]。

以上特征對(duì)微博信息的挖掘帶來了很大的挑戰(zhàn)。針對(duì)微博內(nèi)容的極稀疏性，將其鏈接到其他的知識(shí)庫(kù)來擴(kuò)展內(nèi)容特征的研究，最近受到了越來越多的關(guān)注。Abel[6]等利用新聞信息來增加tweets的上下文，然后利用這些上下文信息來定義用戶的屬性。另外將Wikipedia作為輔助知識(shí)庫(kù)也成為一個(gè)主要的研究方向。Wikipedia作為一個(gè)互聯(lián)網(wǎng)開放式的在線百科全書，具有較廣的覆蓋面和較高的準(zhǔn)確度。由于其包含大量的語料，具有內(nèi)容組織結(jié)構(gòu)化，不需要人工搭建等特點(diǎn)，比較適用于網(wǎng)絡(luò)數(shù)據(jù)挖掘，可以用于自然語言處理中詞義消歧、文本分類和索引、構(gòu)建和維護(hù)語義資源等領(lǐng)域。目前基于Wikipedia的研究工作包含了關(guān)鍵詞語義擴(kuò)展[5]，命名實(shí)體識(shí)別，詞義消歧[7]等方面。研究工作[5,8-9]通過利用Wikipedia的結(jié)構(gòu)化信息來擴(kuò)展微博或者短文本的內(nèi)容，并結(jié)合機(jī)器學(xué)習(xí)的方法訓(xùn)練模型，取得了比較好的效果。文獻(xiàn)[8]設(shè)計(jì)了一種在線的可以將短文本鏈接到語義相關(guān)的Wikipedia頁(yè)面的系統(tǒng)，它采用了一種快速、有效的基于上下文的投票機(jī)制來進(jìn)行語義消歧，在短文本和長(zhǎng)文本上都獲得了比較高的準(zhǔn)確率，但是文獻(xiàn)[8]不能獲得語義相近的更多概念集合，因?yàn)樗逆溄舆^程是基于字符匹配的，不能找到那些不匹配但語義相近的概念。文獻(xiàn)[9]用圖模型描述了Wikipedia中的概念之間關(guān)系，采用了隨機(jī)游走算法來找到語義相關(guān)的概念集合，雖然可以找到那些沒有共現(xiàn)的語義相似度很高的概念，但圖節(jié)點(diǎn)數(shù)量巨大，計(jì)算效率成為一個(gè)瓶頸。與文獻(xiàn)[8-9]相比，本文提出的方法不僅可以找出語義相關(guān)的概念，而且計(jì)算效率也得到比較大的提升。與文獻(xiàn)[10]中基于目錄信息和文獻(xiàn)[11]中基于概念共現(xiàn)的方法來計(jì)算概念之間的相似度相比，本文提出的語義概念擴(kuò)展方法在性能和準(zhǔn)確率上都有較大的提升。

Wikipedia包含了大量的概念并以概念為標(biāo)題的網(wǎng)絡(luò)文章，它的文章正文所包含的相關(guān)概念也以錨文本的方式顯式給出，本文中提到的概念和錨文本含有相同的意義。本文提出了一種新的方法利用Wikipedia作為輔助知識(shí)庫(kù)為微博做語義概念擴(kuò)展，從而達(dá)到擴(kuò)展社會(huì)媒體短文本的內(nèi)容語義特征的效果。本文選擇了有代表性的社會(huì)媒體——微博來描述提出的語義概念擴(kuò)展方法。首先，生成微博所有可能的n-gram,提取n-gram的可鏈接性、詞頻、逆文檔頻率等特征，利用LR(logistic regression)進(jìn)行剪枝，去掉不需要增加概念語義的n-gram。其次，采用了基于上下文相關(guān)的互信息方法將n-gram與Wikipedia中的概念對(duì)應(yīng)起來。最后，利用Wikipedia的概念與文檔之間的結(jié)構(gòu)化信息，構(gòu)建了基于概念—文檔矩陣的非負(fù)矩陣分解(NMF)模型,有效獲取概念之間的語義相似度關(guān)系，為已關(guān)聯(lián)的概念增加更多語義相似的概念。論文的結(jié)構(gòu)如下，第2節(jié)為相關(guān)工作，第3節(jié)是介紹了微博語義概念擴(kuò)展的詳細(xì)方法，第4節(jié)為實(shí)驗(yàn)和分析，最后第5節(jié)對(duì)本文工作做了總結(jié)和展望。

2 相關(guān)工作

相關(guān)工作主要分為針對(duì)Twitter內(nèi)容的研究和基于NMF的文本建模的研究。

2.1 基于Twitter的研究

許多針對(duì)微博的應(yīng)用主要是找到用戶感興趣的話題，例如，電影、產(chǎn)品、人物等，并基于這些信息進(jìn)行話題追蹤、市場(chǎng)營(yíng)銷、個(gè)性化推薦等，工作[5，8，12-13]針對(duì)不同應(yīng)用采用有監(jiān)督或者無監(jiān)督的機(jī)器學(xué)習(xí)方法對(duì)大量微博進(jìn)行數(shù)據(jù)挖掘。Liu[10]等集中在tweet中的命名實(shí)體識(shí)別領(lǐng)域，他們采用了一種基于KNN的監(jiān)督學(xué)習(xí)的框架來鑒別4種不同的實(shí)體類型。Abel[6]等先對(duì)tweet增加上下文信息，然后利用增加的上下文信息為用戶定義屬性，首先利用新聞內(nèi)容為tweet增加語義信息，其次利用增加的語義信息來對(duì)用戶屬性建模。Mendes[14]等利用微博中的鏈接數(shù)據(jù)來對(duì)tweet進(jìn)行標(biāo)注，他們直接利用tweet里面的hashtag標(biāo)簽或者在DBpedia中利用字符串匹配查找在tweet中出現(xiàn)的實(shí)體。Edgar[15]等提出了一種自動(dòng)將tweet與Wikipedia中文章對(duì)應(yīng)起來的方法。他們首先提出了一種基于召回率的方法獲取與微博相關(guān)的概念集合，然后使用了多種方法對(duì)概念進(jìn)行重新排序，并使用機(jī)器學(xué)習(xí)的方法來提升結(jié)果。雖然Edgar的方法能達(dá)到較高的正確率和召回率，但是計(jì)算效率不高，并且得到的概念是基于共現(xiàn)的，并不能獲取潛在語義空間上相似的概念集合。為了獲得潛在語義空間上相似的概念集合，本文提出基于NMF的方法用于計(jì)算Wikipedia中概念之間的語義相關(guān)性。

2.2 基于NMF的研究

NMF(非負(fù)矩陣分解)[16-17]提出了一種新的矩陣描述的方法，對(duì)非負(fù)矩陣X，尋找一個(gè)逼近的分解X≈WH，其中W和H都是非負(fù)矩陣，非負(fù)性約束使得矩陣的表述與其它線性描述方法如ICA[18]相比更具直觀性，更符合常理。Shahmaz[19]等提出了一種基于NMF的方法，可以自動(dòng)識(shí)別非結(jié)構(gòu)化文檔的語義特征并進(jìn)行聚類和話題發(fā)現(xiàn)，與傳統(tǒng)的潛在語義發(fā)現(xiàn)方法相比，取得了比較好的效果。Ankan[20]等提出了一種動(dòng)態(tài)的NMF方法，通過比較分解得到的矩陣的變化能快速地識(shí)別新出現(xiàn)的話題，并能跟蹤到話題隨著時(shí)間的變化情況。Patrik[21]等提出了基于稀疏性約束的NMF分解方法，通過對(duì)迭代產(chǎn)生的矩陣加以稀疏性約束來提升矩陣分解的效果，實(shí)驗(yàn)表明，該方法具有比較快的收斂性和比較高的準(zhǔn)確率。本次實(shí)驗(yàn)主要是采用NMF計(jì)算Wikipedia中概念的語義相似性，類似普通的詞—文檔矩陣分解可以得到詞—詞的語義相似度矩陣，通過對(duì)Wikipedia中概念—文檔矩陣分解可以得到概念—概念的語義相似度矩陣，這是本文與其它鏈接到Wikipedia的研究工作中最主要的不同。

3 微博語義概念擴(kuò)展

本文將Wikipedia作為知識(shí)庫(kù)，為微博信息擴(kuò)展相關(guān)的語義概念。語義概念的擴(kuò)展主要分為以下階段。首先，提取出微博信息的所有n-gram，并對(duì)微博的n-gram進(jìn)行可鏈接性剪枝。在剪枝階段，提取所有n-gram的可鏈接性、詞頻、逆文檔頻率等特征，并利用LR(logistic regression)模型進(jìn)行剪枝，去掉不需要關(guān)聯(lián)語義概念的n-gram。其次，在n-gram和Wikipedia概念關(guān)聯(lián)和消歧階段，采用了基于上下文相關(guān)的互信息方法將剪枝后的n-gram與Wikipedia中的概念對(duì)應(yīng)起來。最后，在語義概念擴(kuò)展階段，利用Wikipedia的概念與文檔之間的結(jié)構(gòu)化信息，構(gòu)建了基于概念—文檔矩陣的非負(fù)矩陣分解模型,有效獲取概念之間的語義相似度，為已關(guān)聯(lián)的概念增加更多語義相似的概念。本文用到的符號(hào)在表1中給出了具體含義的描述。

表1 本文用到的符號(hào)描述

續(xù)表

符號(hào)屬性描述LINK(t)表示t在Wikipedia中的錨文本中出現(xiàn)的次數(shù)OCR(t)表示t在Wikipedia中總的出現(xiàn)次數(shù)LOC(t)與t相匹配的Wikipedia中錨文本集合SEM(c)與c語義相關(guān)的所有錨文本集合H(x)為x的在Wikipedia的邊際熵,x為任意的n-gram或者錨文本H(x,y)為x,y的聯(lián)合熵

3.1 可鏈接性剪枝

對(duì)于微博信息M，為了找出其中可以進(jìn)行語義概念擴(kuò)展的n-gram，首先提取出微博所有的n-gram集合(1≤n≤|M|)。根據(jù)文獻(xiàn)[9]的研究表明，當(dāng)n取4時(shí)，精度不會(huì)明顯下降并且計(jì)算效率也能提升很多，因此本文的n取的最大值是4。對(duì)于微博M，設(shè)M產(chǎn)生的所有可能的n-gram組成集合GS(M) ，我們首先進(jìn)行剪枝處理，因?yàn)椴⒉皇撬械膎-gram都需要增加語義，對(duì)這些n-gram增加語義不僅不能幫助我們理解微博語義，反而可能會(huì)增加歧義。例如，

ObamaandKoehlerwillvisitchinatomorrow!

其中，Obama是美國(guó)總統(tǒng)，Koehler是德國(guó)總統(tǒng)，它們可以鏈接到Wikipedia進(jìn)行語義概念擴(kuò)展，and在Wikipedia中可以作為加法器出現(xiàn)，如果也鏈接到Wikipedia就增加了歧義，所以要進(jìn)行n-gram的剪枝。與文獻(xiàn)[8]中工作不同的是我們將剪枝過程提前，這樣可以減少鏈接的n-gram數(shù)目，提高語義概念擴(kuò)展階段的計(jì)算效率。在這里我們提出了一種基于LR的機(jī)器學(xué)習(xí)方法來判斷這些n-gram的可鏈接性，并找出比較重要的特征。

首先對(duì)于每一個(gè)n-gram，我們通過以下方式計(jì)算它在Wikipedia中出現(xiàn)在錨文本中的概率，如式(1)所示。

其中當(dāng)t含有多個(gè)詞時(shí)，對(duì)任意的ti∈t，OCR(t) = ∑OCR(ti-LINK(t)。

其次，對(duì)于每一個(gè)n-gram，計(jì)算它在Wikipedia中的逆文檔頻率IDF(t)，如式(2)所示。

(2)

最后結(jié)合LR方法，確定了預(yù)測(cè)函數(shù)(3)，其中OCR(t)與|C|的比值表示t出現(xiàn)的概率，如式(3)所示。

(3)

即對(duì)于給定的t,函數(shù)F(t) >ρ的時(shí)候我們就認(rèn)為t可以進(jìn)行鏈接處理，反之就對(duì)t進(jìn)行剪枝，ρ為指定的閾值。

3.2 概念關(guān)聯(lián)和消歧

對(duì)于經(jīng)過剪枝后需要進(jìn)行語義概念擴(kuò)展的t，需要將t鏈接到Wikipedia中對(duì)應(yīng)的錨文本，這時(shí)候會(huì)產(chǎn)生很多帶有歧義的錨文本。因?yàn)閷?duì)于給定的t,可能在不同的上下文中存在不同的錨文本與之對(duì)應(yīng)。比如Michal Jordan 可以與Wikipedia中超過20種錨文本相對(duì)應(yīng)。如何從這些錨文本集合中選出與t最相關(guān)的錨文本即為語義消歧過程。這里我們采用了一種簡(jiǎn)單有效的基于上下文互信息的方法來決定t來鏈接到哪個(gè)錨文本。利用式(4)計(jì)算t和錨文本c之間的互信息MI(t,c)。

MI(t,c=H(t+H(c-H(t,c

(4)

對(duì)任意的ci∈LOC(t，選出與t上下文CT(t)相關(guān)性最大的錨文本ci滿足式(5)：

(5)

3.3 語義概念擴(kuò)展

語義概念的擴(kuò)展主要是為了增加更多語義相關(guān)的概念集合，主要涉及概念之間的語義相似度計(jì)算和語義概念擴(kuò)展。當(dāng)獲得了每一個(gè)t在Wikipedia中對(duì)應(yīng)的錨文本c之后，很多的研究工作[7-8]把該錨文本的鏈接或者頁(yè)面內(nèi)容作為擴(kuò)展的概念語義或者背景知識(shí)，這些方法通常是基于字符匹配或者共現(xiàn)的，不能找到與錨文本語義相關(guān)的更多錨文本信息，從而擴(kuò)展的語義概念就很有限，為了擴(kuò)展更多的語義相關(guān)的概念，需要采取一種有效的方法來找到與c語義相近的更多概念。比如Barack Obama,與其語義相近的錨文本有President of the United States 和U.S.Senator 等。Wikipedia中的頁(yè)面包含很多個(gè)錨文本，目前專門針對(duì)錨文本進(jìn)行語義挖掘的研究并不多，文獻(xiàn)[9]采取了一種基于圖模型的隨機(jī)游走算法來查找語義相關(guān)的錨文本，但由于節(jié)點(diǎn)數(shù)據(jù)巨大計(jì)算效率比較低。我們提出了利用NMF的方法來計(jì)算錨文本之間的語義相似度的方法，在此基礎(chǔ)上為錨文本增加更多的語義信息。

3.3.1 語義概念相似度

如何計(jì)算概念之間的語義相似度，已經(jīng)成為采用Wikipedia進(jìn)行數(shù)據(jù)挖掘工作中比較重要的一部分，不同于文獻(xiàn)[7，11]的計(jì)算方法和文獻(xiàn)[9]中的基于圖的隨機(jī)游走算法，我們采用NMF方法來計(jì)算概念之間的語義相關(guān)性。本文將文獻(xiàn)[7，11]中實(shí)現(xiàn)的方法作為基準(zhǔn)與我們提出的方法進(jìn)行對(duì)比。

基于NMF的語義概念建模。假設(shè)初始待分解矩陣X為m×n的概念—文檔矩陣，m為概念集合的數(shù)目，n為文檔集合的數(shù)目，則可以利用NMF算法分解得到兩個(gè)非負(fù)矩陣W和H，其中W是m×r的概念—主題矩陣，H是r×n的主題—文檔矩陣，這里r為分解矩陣W的列數(shù)和H的行數(shù)，表示文檔集合中主題的數(shù)目。由相關(guān)工作中的研究可以知道，矩陣分解的方法不同，適用的領(lǐng)域也不同。本文實(shí)現(xiàn)的NMF方法是文獻(xiàn)[21]提出的基于L1,L2稀疏性約束的NMF方法,該方法實(shí)驗(yàn)證明了對(duì)分解過程中矩陣W和H的稀疏性進(jìn)行顯示的L1,L2約束可以加快收斂速度，提高算法的效率和結(jié)果的準(zhǔn)確度。在矩陣分解的迭代過程中，尋找非負(fù)的矩陣W和H，使得以下目標(biāo)函數(shù)最小，如式(6)所示。

E(W,H=||X-WH||2

(6)

矩陣分解主要分為兩個(gè)階段。一是投影過程，即對(duì)分解迭代過程中產(chǎn)生的矩陣加以稀疏性約束，在L1約束和L2約束不變的條件下，找到矩陣每一行或者每一列的最優(yōu)投影向量；二是分解過程，在每次迭代過程中，按照非負(fù)約束和稀疏性約束，利用第一階段得到的最優(yōu)解進(jìn)行分解迭代直到滿足停止條件。算法描述如下。

投影部分算法

說明：對(duì)任意的向量x,在給定的L1約束和L2約束下尋找離x最近(歐氏距離)的非負(fù)向量s，對(duì)每一個(gè)元素分別計(jì)算，直到所有元素都非負(fù)則停止。m和s都是與x維度相同的向量

For (i=0;i

1. si:=xi+(L1-∑xi)/dim(x

2. Z:={} //Z為向量s中元素為負(fù)值的下標(biāo)集合

3. while true:

else mi= 0

(b) s:=m+α(s-m) //α為設(shè)定的正值

(c) if all of s are non-negative, return s //如果s的元素都為正，則返回s

(d) Z:=Z∪{i;si<0} //如果si為負(fù)，則將下標(biāo)i添加到集合Z

(e) si=0,?i∈Z //將s中所有為負(fù)數(shù)的值設(shè)為0

(f) c:=(∑si-L1)/(dim(x)-size(Z))

(g) si:=si-c,?i?Z

(h) go (a)

矩陣分解的算法

說明：基于L1和L2稀疏性約束的NMF分解

1. init W and H to random positive matrics //將W和H初始化為非負(fù)的隨機(jī)矩陣

2. If sparseness constraints on W apply, then project each column of W to be non-negative, have

unchanged L2 norm, but L1 norm set to achieve desired sparseness //如果對(duì)W加稀疏性約束，將W的每一列在L1，L2約束下進(jìn)行非負(fù)的投影

3. If sparseness constraints on H apply, then project each row of H to be non-negative, have unitL2 norm, andL1 norm set to achieve desired sparseness

//如果對(duì)H加稀疏性約束，將H的每一行在L1，L2約束下進(jìn)行非負(fù)的投影

4. while(tot

(a) If sparseness constraints onW apply : //如果W加了約束

(1) set W:=W-μW(WH-X)HT

(2) Project each column of W to be non-negative, have unchanged L2 norm, but L1

norm set to achieve desired sparseness //計(jì)算W的投影

Else W:=W?(XHT)(WHHT) //如果W沒有加約束

(b) If sparseness constraints on H apply: //如果H加了約束

(1) set H:=H-μH(WH-X)WT

(2) Project each column of H to be non-negative, have unchanged L2 norm, but L1

norm set to achieve desired sparseness //計(jì)算H的投影

Else H:=H?(WTX)(WHWT) //如果H沒有加約束

(c) it++; tot = ||X-WH||2

3.3.2 基于語義相似度的概念擴(kuò)展

在求得錨文本跟錨文本之間的相似度之后，并不能簡(jiǎn)單的基于語義相似度選取最大的K個(gè)，因?yàn)闆]有考慮上下文信息，即使有些相似度很高的錨文本也不能用來增加語義，否則只會(huì)對(duì)微博的理解產(chǎn)生更多的歧義。作為比較，在實(shí)驗(yàn)過程中我們分別實(shí)現(xiàn)了基于上下文和不基于上下文的語義概念擴(kuò)展方法。在基于上下文的方法中，我們提出了一種結(jié)合逆文檔頻率和互信息的方法來計(jì)算錨文本跟上下文的語義相關(guān)性。假設(shè)t對(duì)應(yīng)的錨文本為m，對(duì)任意的mi∈SEM(m,上下文語義一致性SM(mi,t) 通過式(7)計(jì)算。

對(duì)于給定的K值，使得以下目標(biāo)函數(shù)最大即為跟上下文最相關(guān)的K個(gè)錨文本集合。

4 實(shí)驗(yàn)和評(píng)價(jià)

4.1 實(shí)驗(yàn)數(shù)據(jù)

本次試驗(yàn)采用的1 000條tweet數(shù)據(jù)是基于TREC 2011數(shù)據(jù)集,從其中選取了300條tweet，對(duì)其產(chǎn)生的2 691個(gè)n-gram進(jìn)行了人工標(biāo)注，用來訓(xùn)練和測(cè)試可鏈接剪枝中的LR模型，其余的700條用來做語義擴(kuò)展。Wikipedia采用的是2011年的數(shù)據(jù)集，大概有1 200萬的網(wǎng)頁(yè)，380萬錨文本數(shù)據(jù)，為了驗(yàn)證本文提出方法的有效性，我們?cè)趯?duì)Wikipedia語料構(gòu)建索引之后，按照與American和Obama相關(guān)的話題選擇了其中的2 078篇頁(yè)面作為此次實(shí)驗(yàn)的語料，共含有117 227個(gè)錨文本。

4.2 候選語義概念擴(kuò)展比較算法

在過濾掉語料中的非錨文本詞之后，初始化得到概念—文檔矩陣X，經(jīng)過NMF矩陣分解后得到的矩陣W為概念—主題矩陣，H為文檔—主題矩陣，得到的概念—概念相似度矩陣為W×WT，然后基于這個(gè)相似度矩陣進(jìn)行上下文無關(guān)和上下文相關(guān)的語義概念擴(kuò)展。作為比較，實(shí)驗(yàn)實(shí)現(xiàn)了文獻(xiàn)[7，11]的計(jì)算概念之間相關(guān)度的方法。

(1) Silvim[7]的基于目錄信息的計(jì)算方法

c為Wikipedia中的錨文本，g(c)是Wikipedia中這個(gè)錨文本所屬于的目錄集合的向量表示。作者采用了以式(9)來計(jì)算錨文本之間的相似度。

(9)

(2) Milne和Witten[11]的基于共現(xiàn)信息的計(jì)算方法

c為Wikipedia中的錨文本，g(c)為包含c的Wikipedia的頁(yè)面集合，A為所有的Wikipedia頁(yè)面集合。

(10)

4.3 實(shí)驗(yàn)結(jié)果和評(píng)價(jià)

剪枝階段利用LR模型的實(shí)驗(yàn)的結(jié)果如表2所示。

表2 LR的結(jié)果

假設(shè)tp表示模型將樣本中標(biāo)注為1的預(yù)測(cè)為1；fp表示將-1預(yù)測(cè)成1；fn表示將-1預(yù)測(cè)成0；tn表示將1預(yù)測(cè)成0，基于測(cè)試集合得到的結(jié)果數(shù)據(jù)計(jì)算方式如下。

最終發(fā)現(xiàn)在所有訓(xùn)練集合中，可以進(jìn)行鏈接的t總數(shù)為872個(gè)，平均每一條微博有2.91個(gè)n-gram可以進(jìn)行鏈接。在選擇進(jìn)行預(yù)測(cè)的三個(gè)特征中，比較重要的特征是n-gram的P(t)和IDF(t)。

利用NMF方法得到的初步結(jié)果如表3所示，例子中給出了2個(gè)概念的語義相關(guān)度最大的前5個(gè)概念。

表3 NMF分解得到的前5個(gè)最相關(guān)的概念向量

本次實(shí)驗(yàn)中設(shè)置文檔主題數(shù)r = 50,迭代停止誤差為tot=0.000 001,迭代次數(shù)為8 000，針對(duì)不同計(jì)算方法得到的結(jié)果集合上，作為比較我們選取了不同的結(jié)果集合范圍。不基于上下文的語義概念擴(kuò)展方法與其它兩種方法得到的準(zhǔn)確率如圖1所示。

圖1 給定主題數(shù)r在不同范圍k的結(jié)果正確率(不基于上下文)

從圖上看出在不同的范圍K基于NMF的方法在準(zhǔn)確率上均比其他兩種方法有比較大的提升，從曲線的趨勢(shì)可以看出，基于NMF的方法梯度下降較慢，具有比較好的擴(kuò)展性。Silvim的方法由于直接采用了概念的目錄信息，而Wikipedia的目錄信息噪聲大，很多目錄的區(qū)分度較低，使結(jié)果的準(zhǔn)確度較低。Milne 和Witten的基于共現(xiàn)的方法在候選集合比較小的時(shí)候，準(zhǔn)確率較高，但是當(dāng)集合范圍逐漸擴(kuò)大，引入了更多語義不相關(guān)的概念使準(zhǔn)確率下降很快。由于選擇的語料只是Wikipedia的一個(gè)子集，在以后的工作中可以選擇更全面的語料來更深入的評(píng)價(jià)基于NMF的相似度計(jì)算方法。

在不基于上下文的基礎(chǔ)上，增加了利用上下文信息擴(kuò)展語義概念的結(jié)果如圖2所示。

圖2 給定主題數(shù)r在不同 k的正確率(基于上下文)

可以看出在原有方法基礎(chǔ)上再結(jié)合上下文語義，三種方法的實(shí)驗(yàn)結(jié)果都獲得了比較大的提升，證明了基于上下文語義概念擴(kuò)展方法的有效性。

圖2和圖3的實(shí)驗(yàn)中文檔集合主題數(shù)目r是相同的，本次實(shí)驗(yàn)中也探討了不同的主題數(shù)目r對(duì)結(jié)果正確率的影響。

圖3 不同的主題數(shù)目r的正確率

從實(shí)驗(yàn)的效果看，結(jié)果的正確率跟初始設(shè)置的文檔集合主題數(shù)目r的設(shè)定有比較大的關(guān)系。由于r通常是由人為設(shè)定，跟人的經(jīng)驗(yàn)相關(guān)，造成的誤差會(huì)比較大。因此，我們下一步的改進(jìn)方向是針對(duì)文本的特點(diǎn)，自動(dòng)選擇一個(gè)較優(yōu)的主題數(shù)目r，從而能提高實(shí)驗(yàn)效率和準(zhǔn)確率。

5 總結(jié)及展望

本文提出了一種基于NMF的方法來計(jì)算Wikipedia中概念語義相似度，并在此基礎(chǔ)上為社會(huì)媒體短文本擴(kuò)展語義概念，擴(kuò)展它們的內(nèi)容特征?；诓糠治⒉┱Z料的實(shí)驗(yàn)表明該方法可以實(shí)現(xiàn)較好的性能。接下來我們將從以下三個(gè)方面進(jìn)行改進(jìn)。首先是增大Wikipedia的實(shí)驗(yàn)數(shù)據(jù)集合，對(duì)該方法在大數(shù)據(jù)集合上的性能進(jìn)行深入的探討。由于實(shí)驗(yàn)的條件所限，本次試驗(yàn)只選擇了部分Wikipedia語料，擴(kuò)大語料規(guī)模，驗(yàn)證該方法在大規(guī)模數(shù)據(jù)集合的性能在擁有海量數(shù)據(jù)的今天具有很強(qiáng)的現(xiàn)實(shí)意義和應(yīng)用價(jià)值；其次，通過一種自動(dòng)化尋找最優(yōu)的主題數(shù)目的方法來對(duì)NMF進(jìn)行改進(jìn)，減少人工設(shè)定和調(diào)試參數(shù)的工作量，提高程序的運(yùn)行效率和精度。最后，社會(huì)媒體短文本有多種類型，本次實(shí)驗(yàn)雖然選用的是微博數(shù)據(jù)，但可以擴(kuò)展到其他短文本領(lǐng)域如評(píng)論分析、標(biāo)簽推薦等，除此之外，該方法不僅可以尋找出短文本中有意義的概念實(shí)體，而且可以進(jìn)行語義概念擴(kuò)展，方便在擴(kuò)展的語義特征空間上進(jìn)行深入的數(shù)據(jù)挖掘處理。

[1] 中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心. 第28次中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告[R]. 2011.

[2] A Sitaram, A Huberman. Predicting the Future With Social Media[C]//Proceedings of the ACM, 2010.

[3] S Takeshi, O Makoto, M Yutaka. Earthquake Shakes Twitter Users:Real-time Event Detection by Social Sensors[C]//Proceedings of the WWW, 2010.

[4] A Mathes. Folksonomies-cooperative classification and communication through shared metadata[J]. Computer Mediated Communication, 2004, 47(10): 1-13.

[5] S Banerjee, K Ramanathan, A Gupta. Clustering Short Texts using Wikipedia[C]//Proceedings of the SIGIR,ACM, 2007: 787-788.

[6] A Fabian, G Qi, H Geert-Jan, et al. Semantic Enrichment of Twitter Posts for User Profile Construction on the Social Web[C]//Proceedings of the ESWC, 2011.

[7] C Silvim. Large-scale named entity disambiguation based on Wikipedia data[C]//Proceedings of the EMNLP, 2006.

[8] F Paolo, S Ugo.TAGME:On-the-fly Annotation of Short Text Fragments(by Wikipedia Entities)[C]//Proceedings of the CIKM,2010.

[9] H Xianpei,S Le, Z Jun. Collective Entity Linking in Web Text:A Graph-Based Method[C]//Proceedings of the SIGIR, 2011.

[10] L Xiaohua， Z Shaodian,W Furu,et al. Recognizing Named Entities in Tweets[C]//Proceedings of the ACL, 2011.

[11] D Milne， I H Witten. Learning to link with Wikipedia[C]//Proceedings of the CIKM, 2008.

[12] P Cao,S Liu， J Gao,et al. Finding Topic-related Tweets Using Conversational Thread[C]//Proceedings of the IFIP 7th International Conference on Intelligent Information Processing, 2012.

[13] 莫溢，劉盛華，劉悅，程學(xué)旗. 一種相關(guān)話題微博信息的篩選規(guī)則學(xué)習(xí)算法[J]. 中文信息學(xué)報(bào)，2012，26(5)：1-7.

[14] P N Mendes, P Alexandre,K Pavan, et al. Linked open social signals[C]//Proceedings of the WI-IAT, 2010.

[15] M Edgar,W Wouter, R Maarten. Adding Semantics to Microblog Posts[C]//Proceedings of the WSDM, 2012.

[16] D D Lee, H S Seung. Learning the parts of objects by non-negative matrix factorization Nature,1999, 401(6755):788-791.

[17] D D Lee, H S Seung. Algorithms for non-negative matrix factorization[C]//Proceedings of Neural Information Processing Systems, 2001.

[18] A Hyvarinen,J Karhunen, E Oja. Independent Component Analysis[C]//Proceedings of the Wiley Interscience, 2001.

[19] S Farial,W Berry Michael, V Paul. Document clustering using nonnegative martix factorization[J].Information Processing and Management, 2006,42(2):373-386.

[20] A Saha， S Vikas. Learning Evolving and Emerging Topics in Social Media:A Dynamic NMF approach with Temporal Regularization[C]//Proceedings of the WSDM, 2012.

[21] Patrik O.Hoyer.Non-negative Matrix Factorization with Sparseness Constraints[J]. Journal of Machine Learning Research， 2004，5：1457-1469.