周麗杰，于偉海，郭成

(1.煙臺職業(yè)學(xué)院電教中心，山東煙臺264670; 2.煙臺市普通話培訓(xùn)測試中心，山東煙臺264003;3.大連理工大學(xué)軟件學(xué)院，遼寧大連116620)

基于關(guān)鍵詞協(xié)同投票過濾的短文本特征提取算法研究

周麗杰1，于偉海2，郭成3

(1.煙臺職業(yè)學(xué)院電教中心，山東煙臺264670; 2.煙臺市普通話培訓(xùn)測試中心，山東煙臺264003;3.大連理工大學(xué)軟件學(xué)院，遼寧大連116620)

特征提取算法的目的是為了放大特征項(xiàng)和非特征項(xiàng)之間的權(quán)值差異性。目前文本特征提取算法通常都是面向通用文本，文本因篇幅差異在采用通用特征提取算法進(jìn)行特征提取時性能也各有差異.以關(guān)鍵詞詞頻特性為基礎(chǔ)，構(gòu)建關(guān)鍵詞間協(xié)同過濾投票矩陣，投票矩陣中特征值作為特征項(xiàng)之間的投票數(shù)值，以投票權(quán)值和反文檔頻率共同來表征特征項(xiàng)權(quán)值，以此來滿足短文本內(nèi)容簡短而特征提取準(zhǔn)確率較高的要求.以新浪微博數(shù)據(jù)為測試數(shù)據(jù)集，實(shí)驗(yàn)結(jié)果表明，本文算法能夠較為明顯地差異化特征項(xiàng)和非特征項(xiàng)之間的權(quán)值.

共現(xiàn)頻率;投票矩陣;協(xié)同過濾;特征提取;短文本

短文本因內(nèi)容簡短，在對短文本進(jìn)行特征提取時要更加注重特征提取算法的準(zhǔn)確率，否則稀疏的關(guān)鍵詞將嚴(yán)重影響文本主題的表征［1］.目前，短文本的特征提取已經(jīng)在自然語言處理、問題系統(tǒng)、搜索引擎等多個領(lǐng)域嶄露頭角，對于時下流行的微博話題發(fā)現(xiàn)具有非常重要的現(xiàn)實(shí)意義［2－3］.

經(jīng)典的特征提取算法有基于關(guān)鍵詞詞頻方法(TF)、基于文檔倒排頻率方法(TF－IDF)、基于卡方統(tǒng)計(jì)方法(CHI)和基于信息增益的方法(IG)等.上述算法在文本特征提取領(lǐng)域都是非常成熟的算法，然而在處理時下流行的微博短文本時效果不佳［4］.針對文本的結(jié)構(gòu)特征，有研究者采用最長公共子序列(LCS)的方法試圖從結(jié)構(gòu)角度來對文本塊做整體劃分以此來進(jìn)行特征提取，這種方式比較適用于長文本［5］;針對中英文在表達(dá)上的差異性，結(jié)合中文微博和英文Twitter的差異性，研究者們試圖從語義的角度來出發(fā)，通過HowNet和WordNet詞典計(jì)算特征項(xiàng)語義權(quán)值來進(jìn)行特征提取，因詞典本身容量有限難以適用適應(yīng)微博中不斷出現(xiàn)新詞的場景［6］;在對文本結(jié)構(gòu)化分析的基礎(chǔ)上，有學(xué)者提出發(fā)現(xiàn)文本中相同或相近語法結(jié)構(gòu)來進(jìn)行特征項(xiàng)篩選，諸如提取文本中名詞－動詞組合、動詞－副詞組合［7］，這種方式同樣比較適用于長文本，短文本本身篇幅非常有限，其自身包含的模式串也非常有限.

本文在關(guān)鍵詞詞頻信息的基礎(chǔ)上，以關(guān)鍵詞在文本中出現(xiàn)頻率為依據(jù)，構(gòu)造短文本中關(guān)鍵詞間共現(xiàn)頻率矩陣，共現(xiàn)頻率矩陣中元素的權(quán)值表示為該特征項(xiàng)在短文本中出現(xiàn)次數(shù).某元素的權(quán)值通過其它特征項(xiàng)對該元素進(jìn)行投票所得，采用迭代進(jìn)化的方式，當(dāng)元素的權(quán)值進(jìn)行一定次數(shù)的迭代趨于穩(wěn)定時，則該趨于穩(wěn)定的權(quán)值與反文檔頻率組合作為該特征項(xiàng)的最終權(quán)值.

1 投票模型

投票模型依賴圖結(jié)構(gòu)，圖以結(jié)點(diǎn)和邊構(gòu)成，各個節(jié)點(diǎn)都有出度和入度之分，投票模型假設(shè)各個節(jié)點(diǎn)的權(quán)值受到出度和入度的影響.每一條指向該節(jié)點(diǎn)的邊都認(rèn)為是其它節(jié)點(diǎn)對該節(jié)點(diǎn)的投票(即節(jié)點(diǎn)入度)，從該節(jié)點(diǎn)出發(fā)的邊則認(rèn)為是該節(jié)點(diǎn)對其它節(jié)點(diǎn)的投票(即節(jié)點(diǎn)出度)，根據(jù)出度和入度的關(guān)聯(lián)性對節(jié)點(diǎn)的權(quán)值進(jìn)行迭代計(jì)算［8－9］.投票模型的具體流程可表示如表1所示.

表1 投票模型算法流程

根據(jù)表1所示投票模型算法流程圖，對于圖中某個節(jié)點(diǎn)v，則該節(jié)點(diǎn)的權(quán)值可以量化表示為公式1所示.

在公式1中，wv＇和wv分別表示本次迭代和上次迭代時節(jié)點(diǎn)v的權(quán)值，in_degree(v)和out_degree (vi)分別表示節(jié)點(diǎn)v和節(jié)點(diǎn)vi的入度和出度.

2 改進(jìn)的特征提取算法

將文本轉(zhuǎn)化為圖的表示方式，圖中各個節(jié)點(diǎn)對應(yīng)于文本中各個關(guān)鍵詞，圖中節(jié)點(diǎn)之間的邊關(guān)系對于文本中關(guān)鍵詞之間共現(xiàn)頻率，如此，可以通過關(guān)鍵詞間投票關(guān)系實(shí)現(xiàn)特征項(xiàng)的提取.

2.1 共現(xiàn)投票矩陣構(gòu)建

通過文本分詞和停用詞去除，將文本切分為以關(guān)鍵詞組合來表征的集合，以關(guān)鍵詞作為基礎(chǔ)進(jìn)行投票矩陣構(gòu)建，構(gòu)建的二維矩陣表示如表2所示.

表2 投票矩陣

在表2中，wij表示關(guān)鍵詞ti和關(guān)鍵詞tj之間的共現(xiàn)頻率，共現(xiàn)頻率表示關(guān)鍵詞ti和關(guān)鍵詞tj共同出現(xiàn)的次數(shù).

在表2中，可以看出文本被形式化的表征為圖的模式，wij可以對應(yīng)于關(guān)鍵詞ti和關(guān)鍵詞tj邊上的權(quán)值，關(guān)鍵詞則對應(yīng)于圖中各個節(jié)點(diǎn).

2.2 特征項(xiàng)權(quán)值計(jì)算

通過將文本中關(guān)鍵詞轉(zhuǎn)為二維矩陣的表現(xiàn)方式，借助于投票模型，從而實(shí)現(xiàn)關(guān)鍵詞間投票權(quán)值計(jì)算.

關(guān)鍵詞存在于文本當(dāng)中，關(guān)鍵詞間具有一定的關(guān)聯(lián)性，關(guān)鍵詞之間的關(guān)聯(lián)性通過相互之間的共現(xiàn)關(guān)系加以體現(xiàn)［10］，共現(xiàn)關(guān)系構(gòu)成投票關(guān)系，以投票關(guān)系來反映關(guān)鍵詞在文本中重要程度.根據(jù)投票模型和表征文本的二維矩陣，關(guān)鍵詞ti的投票權(quán)值可表示為公式2所示.

vwti'和vwti分別表示本次迭代和上次迭代時關(guān)鍵詞ti的權(quán)值，wtitj和wtjti分別表示關(guān)鍵詞ti和tj的共現(xiàn)頻率以及關(guān)鍵詞tj和關(guān)鍵詞ti的共現(xiàn)頻率.關(guān)鍵詞的投票權(quán)值受到當(dāng)前投票權(quán)值以及其它節(jié)點(diǎn)的投票共同影響.

關(guān)鍵詞當(dāng)前的投票權(quán)值通過其自身的權(quán)值和其它節(jié)點(diǎn)的投票加權(quán)獲得.其它節(jié)點(diǎn)的投票加權(quán)表示為當(dāng)前的共現(xiàn)頻率與該節(jié)點(diǎn)的共現(xiàn)頻率之和的比例決定.

2.3 特征項(xiàng)選擇

通過特征項(xiàng)投票權(quán)值，可以反映出該關(guān)鍵詞在文本中重要程度［11］，同時文本特征選擇的結(jié)果是該特征項(xiàng)能夠較為明顯地區(qū)分該文本和其它文本，在TF－IDF方法［12］的基礎(chǔ)上，將關(guān)鍵詞詞頻信息更改為特征項(xiàng)投票權(quán)值與反文檔頻率的乘積，通過此種方式，一方面提取出來的特征項(xiàng)反映了該特征項(xiàng)在文本中重要程度，另一方面，也能夠達(dá)到區(qū)分文本的目的.則最終關(guān)鍵詞t的權(quán)值可表示為公式3所示.

3 實(shí)驗(yàn)與分析

本文實(shí)驗(yàn)采用新浪微博測試數(shù)據(jù)集，數(shù)據(jù)集來源于數(shù)據(jù)堂科研共享平臺，微博內(nèi)容語料庫由北京理工大學(xué)網(wǎng)絡(luò)搜索挖掘與安全實(shí)驗(yàn)室張華平博士，通過公開采集與抽取從新浪微博、騰訊微博中獲得.為了推進(jìn)微博計(jì)算的研究，已通過自然語言處理與信息檢索共享平臺(www.nlpir.org)予以公開共享其中的23萬條數(shù)據(jù)［13－14］.

3.1 實(shí)驗(yàn)結(jié)果

將23萬條數(shù)據(jù)隨機(jī)分成9組，分別采用本文算法VA(vote algorithm)、文檔頻率算法(TF－IDF)、卡方統(tǒng)計(jì)算法(CHI)和信息增益算法(IG)［15］計(jì)算這9組數(shù)據(jù)中關(guān)鍵詞的權(quán)值.

分別對9組數(shù)據(jù)中特征項(xiàng)權(quán)值較大者和權(quán)值較小者兩兩做差值，對所有的差值做平均化，如表3所示.

表39 組數(shù)據(jù)權(quán)值差值平均值

在表3中可以看出，本文算法VA在特征提取時，能夠較為明顯地差異化特征項(xiàng)中權(quán)值較大者和特征項(xiàng)中權(quán)值較小者，從而達(dá)到特征提取的目的，即通過權(quán)值差異分離出特征項(xiàng)，特征項(xiàng)之間的形式化表示如圖1所示.

圖1VA、TF－IDF、CHI和IG四種算法權(quán)值比較圖

在圖1中可以看出，本文算法VA和IG算法使得特征項(xiàng)的權(quán)值差異性較為明顯，這也比較符合實(shí)際的情況，IG算法本身是比較好的特征提取算法.相比而言，TF－IDF算法和CHI算法的差異化并不明顯，也表明TF－IDF算法和CHI算法在處理微博這種短文本時效果并不明顯.從圖中走勢圖上可以表明本文算法在微博短文本特征提取時效果較為明顯.分別從9組數(shù)據(jù)中統(tǒng)計(jì)TopN(N=3)條特征項(xiàng)權(quán)值差異化最大的前N條數(shù)據(jù)，比較前N條記錄的權(quán)值差異化平均值，如表4所示.

表4 TopN權(quán)值差異平均值

在表4中可以看出，本文算法VA使得9組中數(shù)組的權(quán)值較為明顯，相對于其它三種，本文算法VA使得權(quán)值差異化也保持最大化，從數(shù)據(jù)中可以看出本文算法能夠使得特征項(xiàng)權(quán)值差異化較明顯，同時也說明本文算法不僅在穩(wěn)定上較好，同時，在局部數(shù)據(jù)上效果同樣很明顯，當(dāng)需要根據(jù)TopN來取特征記錄時，本文算法是一個比較好的選擇.本文算法的走勢圖如圖2所示.

圖2 四種算法在9組數(shù)據(jù)上TopN值

3.2 結(jié)果分析

從實(shí)驗(yàn)結(jié)果可以看出，本文算法在特征提取時能夠較為明顯的差異化特征項(xiàng)之間的權(quán)值特征，從而達(dá)到區(qū)分特征項(xiàng)的目的.

本文算法主要從微博短文本自身的特性出發(fā)，利用微博文本內(nèi)容的結(jié)構(gòu)特征，利用特征項(xiàng)之間的投票關(guān)系來判定特征項(xiàng)在文本中的重要程度，相比于IG算法在特征提取方面，本文算法不需要IG算法來進(jìn)行特征類別掃描，能夠較為明顯地降低時間開銷，同時又能使得特征選擇的效果較好.

4 結(jié)論

本文以時下流行的微博短文本為研究出發(fā)點(diǎn)，分析并闡述文本特征提取的目的是為了差異化特征項(xiàng)和非特征項(xiàng)的權(quán)值，文本中關(guān)鍵詞間共現(xiàn)頻率為基礎(chǔ)，構(gòu)建關(guān)鍵詞間共現(xiàn)頻率矩陣，以圖模型中投票為理論出發(fā)點(diǎn)，將關(guān)鍵詞間關(guān)聯(lián)性通過關(guān)鍵詞間相互投票加以反映，關(guān)鍵詞的投票權(quán)值用來表征該關(guān)鍵詞在文本重要性，同時結(jié)合反文檔頻率來區(qū)分各個文檔.改進(jìn)的算法在新浪微博測試語料庫上的結(jié)果可以表明本文算法能夠較為明顯地差異化特征項(xiàng)和非特征項(xiàng)，從而達(dá)到文本特征提取的目的.

［1］熊忠陽，藺顯強(qiáng)，張玉芳，牙漫.結(jié)合網(wǎng)頁結(jié)構(gòu)與文本特征的正文提取方法［J］.計(jì)算機(jī)工程，2013(12):200－203.

［2］Jung Yi Jiang，Shian Chi Tsai，Shie Jue Lee.Multi－label text categorization based on fuzzy similarity and k nearest neighbors［J］.Expert Systems with Applications，2012，39(3):2813－2821.

［3］何曉亮，宋威，梁久禎.基于資源分配網(wǎng)絡(luò)和語義特征選取的文本分類［J］.計(jì)算機(jī)工程與科學(xué)，2014(2):340－346.

［4］邵曉根，鞠訓(xùn)光，胡局新，馬忠偉.基于改進(jìn)權(quán)重的貝葉斯推理和TFIDF算法文本主題詞提取研究［J］.南京師大學(xué)報(bào)(自然科學(xué)版)，2014(1):57－60.

［5］程傳鵬，蘇安婕.一種短文本特征詞提取的方法［J］.計(jì)算機(jī)應(yīng)用與軟件，2014(6):162－164.

［6］路永和，梁明輝.遺傳算法在改進(jìn)文本特征提取方法中的應(yīng)用［J］.現(xiàn)代圖書情報(bào)技術(shù)，2014(4):48－57.

［7］李明江.結(jié)合類詞頻的文本特征選擇方法的研究［J］.計(jì)算機(jī)應(yīng)用研究，2014(7):2024－2026.

［8］張鳳琴，王磊，張水平，王鵬，程超.一種基于聚類加權(quán)的文本特征生成算法［J］.計(jì)算機(jī)應(yīng)用研究，2013(1):146－148.

［9］侯勇，鄭雪峰.基于最大間隔超平面的增強(qiáng)特征提取算法［J］.計(jì)算機(jī)應(yīng)用，2013(4):998－1000.

［10］李建林.一種基于PCA的組合特征提取文本分類方法［J］.計(jì)算機(jī)應(yīng)用研究，2013(8):2398－2401.

［11］林少波，楊丹，徐玲.基于類別相關(guān)的新文本特征提取方法［J］.計(jì)算機(jī)應(yīng)用研究，2012(5):1680－1683.

［12］Yan hui Gu，Zheng lu Yang，Guan dong Xu.Exploration on efficient similar sentences extraction［J］.World Wide Web，2013，23(1):1－32.

［13］陳炯，張永奎.一種基于詞聚類的文本特征描述方法［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2011(2):211－215.

［14］劉海峰，劉守生，張學(xué)仁.聚類模式下一種優(yōu)化的K－means文本特征選擇［J］.計(jì)算機(jī)科學(xué)，2011(1):195－197.

［15］Aminul Islam，Diana Inkpen.Semantic text similarity using corpus－based word similarity and string similarity［J］.ACM Transactions on Knowledge Discovery from Data，2008，2(2):1－25.

Research on Short Text Feature Extracting Algorithm Based on Keywords Collaboratively Voting Filter

ZHOU Li－jie1，YU Wei－h(huán)ai2，GUO Cheng3
(1.Electronic Teaching Center，Yantai Vocational College，Yantai，264670; 2.Yantai Mandarin Training and Testing Center，Yantai，264003; 3.School of Software Technology，Dalian University of Technology，Dalian，116620，China)

Feature extraction algorithm is designed to amplify the weight difference between feature and non－feature characteristics.Currently，the text feature extraction algorithm is usually designed for general text，however，there exists performance difference while adopting common feature extracting algorithm because of length differences among texts.In this paper，we begin with the term frequency，constructing voting matrix of collaborative filter among terms，the characteristic value in voting matrix is set as the voting value between characteristics，merging the inverted document frequency with voting value to represent weight of characteristic in order to meet the requirement of the content of short text is less while precision rate of characteristic extracting is high.The experimental results on sina weibo datasets show our proposed algorithm can significantly amplify the weight between feature and non－feature characteristics.

common frequency;voting matrix;collaborative filter;feature extracting;short text

TP391

A

1672－2590(2015)06－0043－05

2015－09－28

國家自然科學(xué)基金資助項(xiàng)目(61401060;61272173);山東省高等學(xué)?？萍加?jì)劃基金資助項(xiàng)目(J12LN73)

周麗杰(1976－)，女，山東龍口人，煙臺職業(yè)學(xué)院電教中心實(shí)驗(yàn)師.