王 雯，趙衎衎，李翠平+，陳 紅，孫 輝

1.中國人民大學 數(shù)據(jù)工程與知識工程教育部重點實驗室，北京 100872

2.中國人民大學 信息學院，北京 100872

Spark平臺下的短文本特征擴展與分類研究*

王 雯1,2，趙衎衎1,2，李翠平1,2+，陳 紅1,2，孫 輝1,2

1.中國人民大學 數(shù)據(jù)工程與知識工程教育部重點實驗室，北京 100872

2.中國人民大學 信息學院，北京 100872

短文本分類；特征擴展；關聯(lián)規(guī)則；Spark平臺

1 緒論

1.1 研究背景

短文本通常是指字數(shù)在160字以下的文本，被廣泛應用于微博、論壇、短信、即時消息、郵件等網(wǎng)絡應用中。相對長文本，短文本具有字數(shù)少、數(shù)據(jù)量大、實時性高、應用廣泛等突出特性。短文本在日常網(wǎng)絡溝通及信息獲取中扮演了重要的角色，隨著互聯(lián)網(wǎng)的發(fā)展，互聯(lián)網(wǎng)應用不斷豐富，網(wǎng)民參與度日益上升，互聯(lián)網(wǎng)產(chǎn)生的短文本數(shù)量呈指數(shù)增長。以微博為例，微博是一個基于用戶關系圈的信息獲取、傳播及分享平臺，其中微博內(nèi)容為140字以下的典型的短文本，用戶可以隨時隨地更新關于日常生活、新聞熱點等的見聞。據(jù)微博2016年3月發(fā)布的《2015年微博消費者白皮書》[1]顯示，截至2015年12月，微博日活躍用戶（day active users，DAU）數(shù)量達到1.06億，同比增長32%。以2015年熱門互聯(lián)網(wǎng)金融事件“e租寶”話題為例，圍繞該話題，參與人數(shù)達到6萬人，總共被提及22.7萬次，達到1.9億的閱讀人數(shù)；從垂直領域角度講，涉及“美食”話題的微博數(shù)量達到10.8億條，互動博文數(shù)量超過900億次。數(shù)據(jù)是21世紀最寶貴的財富，隨著短文本數(shù)據(jù)的增加，如何有效利用豐富的數(shù)據(jù)資產(chǎn)，產(chǎn)生巨大的再生價值，成為當下學術及工業(yè)領域研究熱點。短文本分類技術在話題追蹤、輿情分析、信息檢索等多方面具有重要的研究及應用價值。

1.2 問題提出

短文本作為文本的一種特殊類型，分類流程大致相同，即：給定帶標簽C的文檔集D，定義函數(shù)F，求解每個文檔d與類別c的關系映射，并根據(jù)映射F，預測未知類別文檔集合D′對應的類別C′。該過程描述如圖1所示。

Fig.1 Process of text classification圖1 文本分類過程圖

關于長文本分類的研究開始較早，且研究成果顯著，如K近鄰、樸素貝葉斯、支持向量機等算法在不同文本分類問題中得到廣泛應用，并針對不同數(shù)據(jù)集及測試標準得到較好的分類效果。然而，因短文本實時性強、數(shù)據(jù)量大、字數(shù)少、特征維度高、特征稀疏等特性，導致上述傳統(tǒng)分類方法在處理短文本時，分類效果不佳。相對于長文本，短文本分類的瓶頸及挑戰(zhàn)主要體現(xiàn)在以下三方面：

（1）因特征維數(shù)高采用傳統(tǒng)的針對長文本進行處理的方法，如分詞、TF-IDF、去停用詞（stop word）等操作時，很容易丟失短文本的語義信息。

（2）因特征稀疏，使用傳統(tǒng)的長文本分類方法，如K-近鄰（K-nearestneighbor，KNN）、樸素貝葉斯（naive Bayes，NB）、神經(jīng)網(wǎng)絡（neural network，NN）、支持向量機（support vector machine，SVM）進行分類時，無法有效選擇特征，構造向量空間。

（3）因數(shù)據(jù)量大，實時性要求高，傳統(tǒng)短文本分類方法，如支持向量機算法，在處理大數(shù)據(jù)集短文本時面臨吞吐量及執(zhí)行效率的問題。

1.3 研究現(xiàn)狀

特征擴展是解決短文本特征維度高且特征稀疏問題的有效方式，近年來得到廣泛的研究及應用。具體特征擴展的研究方向總結如下：

（1）使用知識庫如WordNet或Wikipedia[2-3]等，可以發(fā)現(xiàn)絕大部分詞與詞之間的語義關系，但是對于在知識庫中沒有收錄的詞語就無效了。

（2）借助外部文本[4]，如搜索引擎搜索的結果，進而擴展短文本的特征[2,5-6]。將短文本特征作為關鍵詞，以搜索引擎返回結果對短文本進行擴展，原特征與擴展后的特征之間關聯(lián)性較高，但實現(xiàn)難度較大，比較耗時，同時在一定程度上依賴于搜索引擎結果的好壞。

（3）基于背景語料庫，采用不同算法挖掘背景語料中的潛在“特征”。Phan[7]、Chen[8]等人使用主題模型LDA（latent Dirichlet allocation）[9]來計算文本之間的相似性。通過與傳統(tǒng)直接采用SVM分類算法進行短文本分類相比，取得了較好的加速效果。采用LDA進行特征擴展首先需要一個較大的背景文檔集，其次LDA主題模型以純概率為基礎，不考慮組成詞之間的聯(lián)系[10-11]。并且由于采用不同的特征權重計量標準，導致后期擴展結果很大程度上依賴于特征權重歸一化處理的結果。文獻[12]提出一種基于頻繁項集考慮語義關聯(lián)性的特征擴展方式，通過背景語料庫挖掘各類別頻繁項集，使用頻繁項集對原短文本各類別特征進行擴展。使用頻繁項集進行特征擴展的方法在解決短文本特征稀疏問題的同時考慮到特征之間的語義關聯(lián)，文中實驗結果顯示，特征擴展后使用SVM分類的效果相對于普通SVM算法在準確率和召回率方面都能得到較大的提升。上述研究中采用卡方檢驗的方式選取影響因子較大的前K個特征值，對選出的特征值在后續(xù)計算中，不再計算初始特征值權重。如對類別C1按照卡方檢驗結果選取特征值(t1,t2,t3)，針對擴展語料庫的挖掘，存在頻繁項集{t3,t4}，則擴展后特征值為(t1,t2,t3,t4)。該計算方法是對模型的一種簡化，但忽略特征值的權重可能導致模型無法真實反映現(xiàn)實應用。

文獻調(diào)研結果顯示，當數(shù)據(jù)集較小時，對特征擴展后的短文本進行分類，準確率明顯上升，但當數(shù)據(jù)集較大時，短文本本身面臨較大的吞吐量瓶頸，擴展后的短文本因特征補充，數(shù)據(jù)量增大，分類壓力更加突出。隨著MapReduce思想的成熟及應用，關于分布式計算框架上并行數(shù)據(jù)處理成為大數(shù)據(jù)環(huán)境下解決吞吐量問題的有效方式[13]。

1.4 本文貢獻

針對短文本分類過程中面臨的瓶頸問題，本文在上述文獻調(diào)研的基礎上，提出基于關聯(lián)規(guī)則挖掘的特征擴展方法，進行Spark平臺上短文本特征擴展與分類研究。本文貢獻總結為以下幾方面：

（1）提出基于關聯(lián)規(guī)則挖掘算法進行特征擴展的方法，并在特征擴展的過程中保留特征權重。通過特征擴展的方式對短文本特征稀疏問題進行優(yōu)化。

（2）對擴展后的短文本采用支持向量機算法進行分類，并針對短文本特性，對cascade SVM算法支持向量選擇過程提出基于距離選擇的改進方法。

（3）針對目前短文本信息量大，對計算能力、實時性要求較高等特性，提出Spark平臺上先特征擴展再分類的兩步短文本分類方法，構建Spark平臺上高效的短文本分類器。

1.5 論文組織結構

本文組織結構如下：第1章介紹短文本定義、應用及短文本分類的巨大研究價值，通過對分類過程的簡要分析，介紹目前分類瓶頸及相應研究現(xiàn)狀，在上述基礎上提出Spark平臺上基于關聯(lián)規(guī)則挖掘的短文本特征擴展方法，并指出本文主要貢獻；第2章介紹基于關聯(lián)規(guī)則挖掘的短文本特征擴展方法的思想、偽代碼及算法選擇；第3章介紹基于距離選擇的層疊支持向量機算法；第4章實現(xiàn)Spark平臺上短文本特征擴展及分類實驗，通過多組實驗，從分類準確率及效率提升的角度，驗證本文提出的Spark平臺上的短文本分類方法在分類效率及分類準確率上的有效性；第5章對全文進行總結，并指出未來工作方向。

2 短文本特征擴展

如上文介紹，相比于長文本，短文本因特征維度高，特征稀疏，在分類過程中特征抽取及特征展示階段面臨較大的瓶頸，進而在分類過程中，分類準確率表現(xiàn)不佳。下面介紹如何借助背景語料庫，采用關聯(lián)規(guī)則挖掘的方式，對短文本特征進行擴展。

2.1 方法描述

基于關聯(lián)規(guī)則的特征擴展方法要求對比短文本特征及背景語料庫關聯(lián)規(guī)則，使用背景語料庫中的關聯(lián)規(guī)則對短文本特征進行補充。該方法實現(xiàn)過程如圖2所示。

記數(shù)據(jù)集D為目標短文本數(shù)據(jù)集，S={d1,d2,…, dn}為與目標短文本相關的語料庫，如目標短文本D為新聞標題數(shù)據(jù)集，則語料庫S可以是對應的新聞正文內(nèi)容。以集合T={t1,t2,…,tk}表示語料庫S的特征集合，集合C={c1,c2,…,cm}表示數(shù)據(jù)集D和S的所有類別。以 sup(t)表示特征 t的支持度，sup(T)= Count(Dt)/Count(D)，Count(Dt)表示文本集中包含特征t的文檔的數(shù)量，Count(D)表示文檔總數(shù)。以conf(t,c)表示關聯(lián)規(guī)則t≥c成立的置信度，conf(t,c)=Count(t,c)/ Count(Dt)，Count(t,c)表示t、c共同出現(xiàn)的文檔數(shù)，Count(Dt)表示出現(xiàn)特征t的文檔數(shù)。當sup(T)超過最小支持度限制α時，稱集合T中子項之間具有一致性。如T包含t1、t2兩個子項，已知t1屬于類別C，則稱Tendency(t2)=c。以Conf(t1→t2)表示關聯(lián)規(guī)則t1→t2的置信度，以V(t)表示原短文本特征t的權重。

首先對于原短文本特征，保留原特征值的權重，對背景語料庫，挖掘關聯(lián)規(guī)則，計算特征置信度，以置信度和原特征的權重乘積作為擴展特征的權重值。如t3為原特征集與頻繁項集的共同特征，假設關聯(lián)規(guī)則t3→t4，且Conf(t3→t4)=0.8，原t3權重V(t3)= 0.2，則擴展后特征t4權重V(t4)=0.8×0.2=0.16。

2.2 偽代碼

特征擴展過程以短文本數(shù)據(jù)集和背景語料庫關聯(lián)規(guī)則作為輸入，分別記為d和s，其中d={＜t1,v1＞,＜t2,v2＞,…,＜tk,vk＞}，數(shù)據(jù)集中包含k個短文本特征。

首先，初始化短文本特征集exd_d為空集。遍歷一次數(shù)據(jù)集，取每個短文本特征tm，對于每個關聯(lián)規(guī)則s的左右兩端特征ti和tj，若tm=tj且tj既不在d中，也不在exd_d中，則計算tj的權重w=Conf(tm→tj)× V(tm)，并將 ＜tj,w＞加入到exd_d中。最后，exd_d= exd_d∪d即為擴充后的短文本特征集合。

為簡化記錄，以AR-FeatureExtension表示基于關聯(lián)規(guī)則挖掘的特征擴展方法，其中s表示背景語料庫S對應的關聯(lián)規(guī)則數(shù)據(jù)集。

遍歷關聯(lián)規(guī)則挖掘的結果，對于每個關聯(lián)規(guī)則對，如一方出現(xiàn)在原短文本數(shù)據(jù)集，另一方不存在，則將后者擴充到原短文本中，新加入的特征權重值為原短文本對應特征權重與關聯(lián)規(guī)則置信度的乘積。

2.3 Spark平臺上特征擴展算法選擇

本文在使用關聯(lián)規(guī)則進行擴展特征挖掘的過程中，針對常用的關聯(lián)規(guī)則挖掘算法Apriori算法和FPGrowth算法，采用MapReduce思想設計并行Apriori算法（MR-Apriori）和并行FP-Growth算法（MR-FP-Growth），后期通過對比實驗選擇Spark平臺上關聯(lián)規(guī)則挖掘效果較好的算法作為特征擴展階段的基礎算法。

Fig.2 Feature extension and classification of short text圖2 短文本特征擴展及分類過程

2.3.1 MR-Apriori算法

Spark平臺上MR-Apriori算法實現(xiàn)過程中，對每次迭代采用MapReduce思想。Map階段先由各計算節(jié)點根據(jù)本地數(shù)據(jù)集，產(chǎn)生局部頻繁模式；Reduce階段由主節(jié)點進行聚集操作，產(chǎn)生全局頻繁模式，最后進行關聯(lián)規(guī)則的挖掘。Spark平臺上MR-Apriori算法執(zhí)行過程如圖3所示。

Fig.3 Process of MR-Apriori圖3 MR-Apriori算法執(zhí)行過程

Apriori算法的最重要特點是在挖掘關聯(lián)規(guī)則的過程中引入候選集的概念，以原始數(shù)據(jù)集D為輸入，最終得到了1至K階的頻繁模式集。

首先，并行掃描數(shù)據(jù)集，將D分為N個分區(qū)，各節(jié)點根據(jù)本地數(shù)據(jù)分區(qū)生成本地1階候選集，將結果返回給主節(jié)點，再進行數(shù)據(jù)聚合，產(chǎn)生1階候選集C-1。對C-1進行剪枝，從而生成1階頻繁項集L-1。

在此基礎上，可生成2到K階頻繁項集。并行掃描數(shù)據(jù)庫，判斷是否存在K-1階頻繁項集（K＞1）。若存在，則對K-1階頻繁項集進行連接操作，產(chǎn)生候選集C-K，各節(jié)點計算本地K階候選集內(nèi)各元素的支持度并將結果返回給主節(jié)點，主節(jié)點聚合數(shù)據(jù)后產(chǎn)生K階候選集和支持度，對其進行剪枝后生成K階頻繁項集L-K。若不存在，則令K=K+1，重新判斷，多次迭代，直至沒有新的候選集產(chǎn)生。

2.3.2 MR-FP-Growth算法

Spark平臺上的MR-FP-Growth算法在實現(xiàn)過程中，各執(zhí)行步驟之間存在遞歸關系，因此采用數(shù)據(jù)集劃分的方法，算法執(zhí)行過程中執(zhí)行3次MapReduce過程。Spark平臺上使用MR-FP-Growth進行頻繁模式及關聯(lián)規(guī)則挖掘過程如圖4所示。

Fig.4 Process of MR-FP-Growth圖4MR-FP-Growth算法執(zhí)行過程

上述算法執(zhí)行過程中包括MapReduce及生成條件頻繁樹兩個階段，對應的執(zhí)行流程如下：

步驟1把數(shù)據(jù)庫分成連續(xù)的不同的分區(qū)，每一個分區(qū)分布在不同的機器上。

步驟2執(zhí)行第一次MapReduce過程，計算F_list,即item的support count。

步驟3將F_list中item分成Q組，形成group_list,每個group都被分配唯一的group_id，并包含一組item。

步驟4并行FP-Growth，執(zhí)行第二次MapReduce操作。具體的，在Map階段，利用步驟1的數(shù)據(jù)庫分區(qū)，處理數(shù)據(jù)庫分區(qū)中的每一條transaction，將transaction細分成item，每個item根據(jù)group_list映射到合適的group中。Map過程后，屬于同一個group的item集合聚合到同一臺機器上。在Reduce階段，根據(jù)Map過程中產(chǎn)生的集合，進行本地FP-Growth計算。

步驟5聚合各機器結果形成全局FP-Growth計算值。

3 短文本分類

對擴展后的短文本進行分類過程中采用cascade SVM算法[13-15]，通過并行的方式加速短文本分類效率。本文在應用cascade SVM算法時，根據(jù)短文本特性，引入?yún)?shù)α，提出根據(jù)文本集大小調(diào)整參數(shù)α，從而按照距離選擇支持向量的方式[16]。

3.1 方法描述

本文提出對層疊支持向量機在支持向量選擇時的方法優(yōu)化，在每次迭代過程中，SVM訓練結束后，計算訓練集中各個樣本到超平面的距離，得到距離d1,d2,…,dn，計算樣本到分類超平面的距離，并將樣本按照到超平面的距離升序排列。設定選擇參數(shù)α，α∈(0,1)，對升序排列后的樣本，選擇前α的樣本作為支持向量，一方面作為下一級SVM訓練過程的輸入，另一方面在反饋調(diào)整環(huán)節(jié)，充分利用該樣本集，對每次迭代過程中產(chǎn)生的SVM進行調(diào)整[17-18]。如α＝0.1，則對排序后的樣本選擇10%作為支持向量。具體過程如圖5所示。

Fig.5 Process of cascade SVM algorithm圖5 層疊支持向量機執(zhí)行過程圖

圖5所述的短文本分類實例描述如下：

（1）短文本數(shù)據(jù)集TD被劃分為4份，由4個計算節(jié)點根據(jù)本地訓練數(shù)據(jù)集并行訓練，每個計算節(jié)點產(chǎn)生一個超平面，即SVMi。

（2）每個計算節(jié)點，計算本地子訓練集中的樣本到超平面的距離，并將樣本按距離升序排列，選擇前α的樣本作為本次計算過程產(chǎn)生的支持向量svi。如圖6中上下兩個實例，分別表示α＝0.3及α＝0.7時對應的支持向量。

（3）將步驟（2）產(chǎn)生的svi作為第二次迭代過程的訓練集輸入，并將數(shù)據(jù)重新組合分配，同理得到下一級子超平面及支持向量。

（4）重復上述步驟，直至訓練出一個超平面SVM及對應的支持向量sv，并將生成的sv作為下一次優(yōu)化調(diào)整的輸入，判斷一次分類過程的準確性。

（5）重復上述過程，直至產(chǎn)生的sv′與上一次產(chǎn)生的sv之間差集為空，或小于設定值。

Fig.6 Example ofα-cascade-SVM圖6 α-cascade-SVM示例圖

3.2 偽代碼

基于距離選擇的層疊支持向量機以訓練集、選擇參數(shù)α和終止條件閾值β作為輸入。

首先進行一次MapReduce產(chǎn)生一個超平面及支持向量：對數(shù)據(jù)集進行劃分，訓練出子SVMi，掃描訓練集計算樣本點與超平面的距離并排序，再以α為比例選擇樣本作為支持向量，合并后生成SVM及sv。

接下來進行判斷，若sv′-sv＞β，則重復第一步，通過多次迭代，最終生成SVM模型及支持向量。

4 Spark平臺上特征擴展與分類實驗

本文采用搜狗實驗室提供的18個頻道搜狐新聞數(shù)據(jù)集，包含國內(nèi)、國際、體育、娛樂、社會等。數(shù)據(jù)集包括新聞標題及新聞內(nèi)容，文本采用原新聞標題數(shù)據(jù)集作為短文本數(shù)據(jù)集，內(nèi)容數(shù)據(jù)集為背景語料庫數(shù)據(jù)集。分別采用37 KB，330 KB，3 MB，33 MB，330 MB，1.4 GB等6個大小不同的數(shù)據(jù)集進行實驗。每個數(shù)據(jù)集中新聞標題短文本數(shù)據(jù)約占5%，背景語料數(shù)據(jù)約占95%。

實驗在有6個集群節(jié)點的分布式計算平臺Spark上進行，該Spark集群部署為Standalone模式，其中包括1個主節(jié)點和5個計算節(jié)點，每個節(jié)點配有4個物理核，內(nèi)存為6.6GB。集群為Linux系統(tǒng)，配置Spark1.6.0，同時部署Hadoop2.6.0提供如HDFS等底層支持。

實驗1不同關聯(lián)規(guī)則挖掘算法效率對比。

使用上述6個背景語料數(shù)據(jù)集分別采用MR-Apriori和MR-FP-Growth算法進行基于關聯(lián)規(guī)則挖掘的特征擴展，設置支持度為0.1，置信度為0.5，各算法執(zhí)行時間如表1和圖7所示。

Table 1 Execution costs of MR-Apriori and MR-FP-Growth表1 MR-Apriori和MR-FP-Growth算法執(zhí)行時間對比

Fig.7 Execution costs of MR-Apriori and MR-FP-Growth圖7MR-Apriori和MR-FP-Growth算法執(zhí)行時間對比

圖7中虛線表示不同數(shù)據(jù)集采用MR-Apriori算法進行特征擴展在Spark集群上的執(zhí)行時間，實線表示不同數(shù)據(jù)集采用MR-FP-Growth算法在Spark集群上的執(zhí)行時間。首先對比關聯(lián)規(guī)則挖掘結果，每種數(shù)據(jù)集下，采用兩種算法得到的擴展后的數(shù)據(jù)集相同。

由圖7可知，當數(shù)據(jù)集較小時，采用兩種算法進行特征擴展效果相當。當數(shù)據(jù)集較大（本實驗中，超過3 MB）時，MR-Apriori算法執(zhí)行耗時顯著上升，MR-FP-Growth算法執(zhí)行耗時增長較平緩。當數(shù)據(jù)集達到330 MB時，MR-Apriori算法執(zhí)行時間為MRFP-Growth算法的42倍，且當數(shù)據(jù)集繼續(xù)增大，達到1.4 GB時，Apriori執(zhí)行過程中頻繁發(fā)出內(nèi)存不足的警告，算法執(zhí)行時間超過1 h。

根據(jù)上述實驗結果，選擇MR-FP-Growth算法為本文特征擴展的基礎算法，后續(xù)實驗利用該算法，研究影響特征擴展效果的因素。

實驗2參數(shù)α對實驗結果的影響。

本實驗中選擇短文本數(shù)據(jù)集A，該數(shù)據(jù)集包含63 260條短文本新聞標題，以及18個分類標簽。按照6∶4的比例，取37 956條數(shù)據(jù)作為訓練集，25 304條作為測試集數(shù)據(jù)。首先進行改進前的層疊支持向量機算法實驗，記錄實驗結果中支持向量數(shù)量、準確率及執(zhí)行時間，實驗結果記作E1。測試設置不同距離選擇參數(shù)α＝{0.1,0.2,0.3,0.4,0.5,0.6}，通過實驗統(tǒng)計支持向量、準確率及執(zhí)行時間，結果如表2所示。

Table 2 Influence ofαto category results表2 參數(shù)α對實驗結果影響統(tǒng)計表

實驗結果采用組合圖的形式描述，如圖8所示。

Fig.8 Influence ofαto accuracy and running time圖8 參數(shù)α對準確率及執(zhí)行時間影響統(tǒng)計圖

圖8中橫坐標表示實驗分組類別，柱形圖表示不同參數(shù)α對應的分類準確率結果（對應左側縱坐標），折線圖表示不同參數(shù)α對應的分類執(zhí)行時間（對應右側縱坐標）。由表2可知，隨著α值增加，支持向量數(shù)增加，準確率上升，執(zhí)行時間上升。由圖8可知，當α較小時，準確率及執(zhí)行時間上升較明顯，隨著α增大，本實驗中α＞0.3時，準確率上升速度放緩，執(zhí)行時間上升速度增加。

根據(jù)上述實驗，綜合考慮分類準確率及分類時間，針對該數(shù)據(jù)集選擇α＝0.3，使用最小的執(zhí)行時間代價換相對較高的準確率提升。根據(jù)上述實驗過程，分別對3.3節(jié)中的搜狗新聞數(shù)據(jù)集進行上述實驗，通過調(diào)整參數(shù)α的值，統(tǒng)計不同參數(shù)下對應的支持向量數(shù)據(jù)、準確率及執(zhí)行時間，并采用上述的對比方式，針對每一數(shù)據(jù)集，綜合考慮參數(shù)α對分類準確率及執(zhí)行時間的影響，選取性價比相對較高的參數(shù)α設置，各數(shù)據(jù)集及相對最優(yōu)α值對應關系如表3所示。

Table 3 Relation ofαand data sets表3 數(shù)據(jù)集與參數(shù)α對應關系表

如表3所示，數(shù)據(jù)集大小為3 MB時，對應相對較優(yōu)α值為0.4；數(shù)據(jù)集大小為33 MB時，對應相對較優(yōu)α值為0.3；數(shù)據(jù)集為1.4GB時，對應相對較優(yōu)α值為0.2。

實驗3數(shù)據(jù)劃分塊數(shù)對特征擴展及分類的影響。

特征擴展及分類過程中，分別將數(shù)據(jù)分塊，每個計算節(jié)點每個計算階段處理其中幾塊子數(shù)據(jù)集。為驗證參數(shù)n1、n2對整個短文本分類效率的影響，以上述330 MB數(shù)據(jù)為例，進行不同n1、n2設置的組合實驗，實驗結果如表4和圖9所示。

Table 4 Influence of cluster partitions to efficiency表4 集群數(shù)據(jù)分區(qū)數(shù)對分類效率的影響

圖9中橫坐標表示分類階段參數(shù)n2，即分類過程中數(shù)據(jù)劃分塊數(shù)，每個n2值對應5個不同n1取值，由左至右分別表示n1為1、5、10、15、20。由圖9可知，對330 MB數(shù)據(jù)集，特征擴展階段分區(qū)數(shù)n1固定時，對不同參數(shù)n2，當n2＝15時，整體分類效率最高；當固定分類階段分區(qū)數(shù)量n2，調(diào)整特征擴展階段分區(qū)數(shù)量n1時，對不同參數(shù)n1，當n1＝10時，整體分類效率最高。即對330 MB數(shù)據(jù)集，當特征擴展階段分區(qū)數(shù)為10，分類階段分區(qū)數(shù)為15時，整體分類效率最高，相應分類時間為172.5 s，執(zhí)行時間相比于分類效率最低時（280.4 s），約提升60%。

Fig.9 Influence of cluster partitions to efficiency圖9 集群分區(qū)數(shù)對分類效率的影響

實驗4特征擴展及分類優(yōu)化對準確率的影響。

分別設計不進行特征擴展和分類優(yōu)化（E1）、特征擴展后分類不優(yōu)化（E2）及既特征擴展又分類優(yōu)化（E3）的3組實驗，每組實驗針對不同數(shù)據(jù)集分別測試。實驗結果如圖10所示。

Fig.10 Accuracy comparison圖10 分類準確率對比圖

由圖10可知，特征擴展及分類優(yōu)化階段均對分類準確率的提升發(fā)揮重要的作用，其中特征擴展約得到10.3%的準確率提升，分類優(yōu)化約得到5.2%的準確率提升；當數(shù)據(jù)集較小時（本實驗中小于33 MB），特征擴展對準確率提升作用較明顯，隨著短文本數(shù)據(jù)集的增加，特征擴展的準確率提升幅度相對下降。

實驗5特征擴展及分類優(yōu)化對效率的影響。

為驗證本文提出的Spark平臺上基于特征擴展的短文本分類方法的效率，將本文提出的特征擴展與分類優(yōu)化方法與傳統(tǒng)單機上短文本分類算法進行對比，統(tǒng)計各數(shù)據(jù)集下不同算法的執(zhí)行效率，通過對比實驗，分析本文提出的短文本分類方法的分類效率。實驗結果統(tǒng)計如圖11所示，E4表示單機數(shù)據(jù)，E5表示集群數(shù)據(jù)。

Fig.11 Efficiency comparison of cluster and local圖11 單機與集群執(zhí)行效率對比圖

圖11中虛線表示單機上采用傳統(tǒng)cascade SVM算法進行短文本分類的執(zhí)行時間，實線表示采用本文提出的Spark平臺上的特征擴展并分類優(yōu)化的短文本分類技術的執(zhí)行時間。

由上述實驗結果可知，當數(shù)據(jù)集較小時，本文提出的短文本分類方式執(zhí)行效率低于傳統(tǒng)短文本分類方法執(zhí)行效率，隨著數(shù)據(jù)集增大，E5增長相對較緩慢，當數(shù)據(jù)集達到1.4 GB時，傳統(tǒng)分類方法分類時間超過半小時，本文提出的短文本分類方法約需要376.2 s，分類效率約為傳統(tǒng)單機上短文本分類算法的4倍。該實驗驗證了本文提出的分類方法在面向大數(shù)據(jù)集分類時，在吞吐能力和分類效率上的有效性。

5 總結

本文在特征擴展階段，將關聯(lián)規(guī)則挖掘階段產(chǎn)生的項擴充到原短文本時，采用置信度與原短文本特征值直接相乘的方法，該方法相比于傳統(tǒng)使用支持向量機算法進行短文本分類的方法，在分類準確率及分類效率上均得到較好的提升。但實驗過程中，對特征擴展過程中新特征權重計算方式缺乏對比，后期針對該問題，繼續(xù)設計可行的平滑公式，對擴展后的特征計算方式進行優(yōu)化。其次，本文分類實驗過程中，集群環(huán)境中算法運行效率相對單機環(huán)境雖然相對較高，但從加速比看，加速效果還有提升的空間，目前尚未達到線性加速比，后期針對該問題繼續(xù)尋找優(yōu)化與改進的空間。

[1]Weibo white paper on consumer in 2015[EB/OL].[2016-06-12].http://data.weibo.com/report/reportDetail?id=318.

[2]Ning Yahui,Fan Xinghua,Wu Yu.Short text classification based on domain word ontology[J].Computer Science,2009, 36(3):142-145.

[3]Fan Yunjie,Liu Huailiang.Research on Chinese short text classification based on Wikipedia[J].New Technology of Library&Information Service,2012,28(3):47-52.

[4]Liu Jinling,Yan Yunyang.SMS text classification method based on context[J].Computer Engineering,2011,37(10): 41-43.

[5]He Hui,Chen Bo,Xu Weiran,et al.Short text feature extraction and clustering for Web topic mining[C]//Proceedings of the 3rd International Conference on Semantics,Knowledge and Grid,Xi'an,China,Oct 29-31,2007.Washington: IEEE Computer Society,2007:382-385.

[6]Wang Zuli.An improved method of short text feature extraction based on words co-occurrence[C]//Proceedings of the 2nd International Conference on Electric Technology and Civil Engineering,Wuhan,China,May 18-20,2012.Washington:IEEE Computer Society,2012:266-269.

[7]Phan X H,Nguyen L M,Horiguchi S.Learning to classify short and sparse text&Web with hidden topics from largescale data collections[C]//Proceedings of the 17th International Conference on World Wide Web,Beijing,Apr 21-25, 2008.New York:ACM,2008:91-100.

[8]Chen Mengen,Jin Xiaoming,Shen Dou.Short text classification improved by learning multi-granularity topics[C]// Proceedings of the 22nd International Joint Conference on Artificial Intelligence,Barcelona,Spain,Jul 16-22,2011. Menlo Park,USA:AAAI,2011:1776-1781.

[9]Blei D M,Ng A Y,Jordan M I.Latent Dirichlet allocation[J]. The Journal of Machine Learning Research,2003,3:993-1022.

[10]Vo D T,Ock C Y.Learning to classify short text from scientific documents using topic models with various types of knowledge[J].Expert Systems with Applications,2015,42 (3):1684-1698.

[11]Hu Yongjun,Jiang Jiaxin,Chang Huiyou.A new method of keywords extraction for Chinese short-text classification[J]. New Technology of Library and Information Service,2013, 29(6):42-48.

[12]Zhang Zhifei,Miao Duoqian,Gao Can.Short text classification using latent Dirichlet allocation[J].Journal of Computer Applications,2013,33(6):1587-1590.

[13]Dean J,Ghemawat S.MapReduce:simplified data processing on large clusters[C]//Proceedings of the 6th Conference onSymposium on Operating Systems Design and Implementation,San Francisco,USA,Dec 6-8,2004.Berkeley,USA: USENIXAssociation,2004:107-113.

[14]Keerthi S S,Shevade S K,Bhattacharyya C,et al.Improvements to Platt's SMO algorithm for SVM classifier design [J].Neural Computation,2006,13(3):637-649.

[15]Platt J C.Fast training of support vector machines using sequential minimal optimization[M]//Advances in Kernel Methods.Cambridge,USA:MIT Press,1999:185-208.

[16]Song Ge,Ye Yunming,Du Xiaolin,et al.Short text classification:a survey[J].Journal of Multimedia,2014,9(5):635-643.

[17]Li Haoyuan,Wang Yi,Zhang Dong,et al.PFP:parallel FP-growth for query recommendation[C]//Proceedings of the 2008 ACM Conference on Recommender Systems,Lousanne,Switzerland,Oct 23-25,2008.New York:ACM,2008: 107-114.

[18]Joachims T.Making large-scale support vector machine learning practical[M]//Advances in Kernel Methods.Cambridge, USA:MIT Press,1999:169-184.

附中文參考文獻：

[1]新浪微博數(shù)據(jù)中心.2015微博消費者白皮書[EB/OL].[2016-06-12].http://data.weibo.com/report/reportDetail?id=318.

[2]寧亞輝,樊興華,吳渝.基于領域詞語本體的短文本分類[J].計算機科學,2009,36(3):142-145.

[3]范云杰,劉懷亮.基于維基百科的中文短文本分類研究[J].現(xiàn)代圖書情報技術,2012,28(3):47-52.

[4]劉金嶺,嚴云洋.基于上下文的短信文本分類方法[J].計算機工程,2011,37(10):41-43.

[11]胡勇軍,江嘉欣,常會友.基于LDA高頻詞擴展的中文短文本分類[J].現(xiàn)代圖書情報技術,2013,29(6):42-48.

[12]張志飛,苗奪謙,高燦.基于LDA主題模型的短文本分類方法[J].計算機應用,2013,33(6):1587-1590.

WANG Wen was born in 1992.She is an M.S.candidate at School of Information,Renmin University of China. Her research interests include text mining and parallel data processing.

王雯（1992—），女，山東鄒市人，中國人民大學信息學院碩士研究生，主要研究領域為文本挖掘，并行數(shù)據(jù)處理。

ZHAO Kankan was born in 1991.He is a Ph.D.candidate at School of Information,Renmin University of China. His research interests include recommender system,data fusion and big data analysis.

趙衎衎（1991—），男，陜西渭南人，中國人民大學信息學院博士研究生，主要研究領域為推薦系統(tǒng)，數(shù)據(jù)融合，大數(shù)據(jù)分析。

LI Cuiping was born in 1971.She is a professor at School of Information,Renmin University of China.Her research interests include database technology,data mining,social network analysis and social recommendation.

李翠平（1971—），女，博士，中國人民大學信息學院教授，主要研究領域為數(shù)據(jù)庫技術，數(shù)據(jù)挖掘，社交網(wǎng)絡分析，社會推薦。

CHEN Hong was born in 1965.She is a professor at School of Information,Renmin University of China.Her research interests include database technology and hardware based high performance computing.

陳紅（1965—），女，博士，中國人民大學信息學院教授，主要研究領域為數(shù)據(jù)庫技術，新硬件平臺下的高性能計算。

SUN Hui was born in 1977.She is a lecturer at School of Information,Renmin University of China with a Ph.D.degree in Tsinghua University.Her research interests include data mining and high-performance database.

孫輝（1977—），女，博士，中國人民大學信息學院講師，主要研究領域為數(shù)據(jù)挖掘，高性能數(shù)據(jù)庫。

Feature Extension and Category Research for Short Text Based on Spark Platform*

WANG Wen1,2,ZHAO Kankan1,2,LI Cuiping1,2+,CHEN Hong1,2,SUN Hui1,2
1.Key Laboratory of Data Engineering and Knowledge Engineering,Renmin University of China,Beijing 100872, China
2.School of Information,Renmin University of China,Beijing 100872,China

+Corresponding author:E-mail:licuiping@ruc.edu.cn

WANG Wen,ZHAO Kankan,LI Cuiping,et al.Feature extension and category research for short text based on spark platform.Journal of Frontiers of Computer Science and Technology,2017,11(5)：732-741.

Short text classification is often confronted with some limitations including high feature dimensions, sparse feature existences and poor classification accuracy,which can be solved by feature extension effectively. However,it decreases the execution efficiency greatly.To improve classification accuracy and efficiency of short text,this paper proposes a new solution,association rule based feature extension method which is designed on Spark platform.Given a background data set of short text corpus,firstly extend origin corpus and complement the features by mining the association rules and the corresponding confidences.Then apply a new cascade SVM(support vector machine)algorithm based on distance to choose during classification.Finally design the feature extension and classification algorithm of short text on Spark platform and improve the efficiency of short text processing through distributed algorithm.The experiments show that the new method gains 4 times of efficiency improvement compared with the traditional method and 15%increase in classification accuracy,in which the accuracy of feature extension and classification optimization is 10%and 5%respectively.

short text classification;feature extension;association rule;Spark platform

10.3778/j.issn.1673-9418.1608041

A

：TP391

*The National Social Science Foundation of China under Grant No.12&ZD220(國家社會科學基金).

Received 2016-08,Accepted 2016-10.

CNKI網(wǎng)絡優(yōu)先出版:2016-10-31,http://www.cnki.net/kcms/detail/11.5602.TP.20161031.1650.010.html

摘 要：短文本分類經(jīng)常面臨特征維度高、特征稀疏、分類準確率差的問題。特征擴展是解決上述問題的有效方法，但卻面臨更大的短文本分類效率瓶頸。結合以上問題和現(xiàn)狀，針對如何提升短文本分類準確率及效率進行了詳細研究，提出了一種Spark平臺上的基于關聯(lián)規(guī)則挖掘的短文本特征擴展及分類方法。該方法首先采用背景語料庫，通過關聯(lián)規(guī)則挖掘的方式對原短文本進行特征補充；其次針對分類過程，提出基于距離選擇的層疊支持向量機（support vector machine，SVM）算法；最后設計Spark平臺上的短文本特征擴展與分類算法，通過分布式算法設計，提高短文本處理的效率。實驗結果顯示，采用提出的Spark平臺上基于關聯(lián)規(guī)則挖掘的短文本特征擴展方法后，針對大數(shù)據(jù)集，Spark集群上短文本特征擴展及分類效率約為傳統(tǒng)單機上效率的4倍，且相比于傳統(tǒng)分類實驗，平均得到約15%的效率提升，其中特征擴展及分類優(yōu)化準確率提升分別為10%與5%。