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

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

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

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

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

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

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

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

短文本分類；特征擴展；關聯規則；Spark平臺

1 緒論

1.1 研究背景

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

1.2 問題提出

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

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

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

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

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

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

1.3 研究現狀

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

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

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

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

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

1.4 本文貢獻

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

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

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

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

1.5 論文組織結構

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

2 短文本特征擴展

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

2.1 方法描述

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

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

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

2.2 偽代碼

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

首先，初始化短文本特征集exd_d為空集。遍歷一次數據集，取每個短文本特征tm，對于每個關聯規則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表示基于關聯規則挖掘的特征擴展方法，其中s表示背景語料庫S對應的關聯規則數據集。

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

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

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

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

2.3.1 MR-Apriori算法

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

Fig.3 Process of MR-Apriori圖3 MR-Apriori算法執行過程

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

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

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

2.3.2 MR-FP-Growth算法

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

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

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

步驟1把數據庫分成連續的不同的分區，每一個分區分布在不同的機器上。

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

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

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

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

3 短文本分類

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

3.1 方法描述

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

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

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

（1）短文本數據集TD被劃分為4份，由4個計算節點根據本地訓練數據集并行訓練，每個計算節點產生一個超平面，即SVMi。

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

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

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

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

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

3.2 偽代碼

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

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

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

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

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

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

實驗1不同關聯規則挖掘算法效率對比。

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

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

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

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

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

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

實驗2參數α對實驗結果的影響。

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

Table 2 Influence ofαto category results表2 參數α對實驗結果影響統計表

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

Fig.8 Influence ofαto accuracy and running time圖8 參數α對準確率及執行時間影響統計圖

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

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

Table 3 Relation ofαand data sets表3 數據集與參數α對應關系表

如表3所示，數據集大小為3 MB時，對應相對較優α值為0.4；數據集大小為33 MB時，對應相對較優α值為0.3；數據集為1.4GB時，對應相對較優α值為0.2。

實驗3數據劃分塊數對特征擴展及分類的影響。

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

Table 4 Influence of cluster partitions to efficiency表4 集群數據分區數對分類效率的影響

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

Fig.9 Influence of cluster partitions to efficiency圖9 集群分區數對分類效率的影響

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

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

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

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

實驗5特征擴展及分類優化對效率的影響。

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

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

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

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

5 總結

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

[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]新浪微博數據中心.2015微博消費者白皮書[EB/OL].[2016-06-12].http://data.weibo.com/report/reportDetail?id=318.

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

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

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

[11]胡勇軍,江嘉欣,常會友.基于LDA高頻詞擴展的中文短文本分類[J].現代圖書情報技術,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—），女，山東鄒市人，中國人民大學信息學院碩士研究生，主要研究領域為文本挖掘，并行數據處理。

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—），男，陜西渭南人，中國人民大學信息學院博士研究生，主要研究領域為推薦系統，數據融合，大數據分析。

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—），女，博士，中國人民大學信息學院教授，主要研究領域為數據庫技術，數據挖掘，社交網絡分析，社會推薦。

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—），女，博士，中國人民大學信息學院教授，主要研究領域為數據庫技術，新硬件平臺下的高性能計算。

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—），女，博士，中國人民大學信息學院講師，主要研究領域為數據挖掘，高性能數據庫。

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網絡優先出版:2016-10-31,http://www.cnki.net/kcms/detail/11.5602.TP.20161031.1650.010.html

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