張忠林，劉述昌，江粉桃

(蘭州交通大學(xué) 電子與信息工程學(xué)院，蘭州 730070) (*通信作者電子郵箱l15117014316@163.com)

深層次分類中候選類別搜索算法

張忠林，劉述昌*，江粉桃

(蘭州交通大學(xué) 電子與信息工程學(xué)院，蘭州 730070) (*通信作者電子郵箱l15117014316@163.com)

針對(duì)深層次分類中分類準(zhǔn)確率低、處理速度慢等問題，提出一種待分類文本的候選類別搜索算法。首先,引入搜索、分類兩階段的處理思想，結(jié)合類別層次樹的結(jié)構(gòu)特點(diǎn)和類別間的相關(guān)聯(lián)系等隱含的領(lǐng)域知識(shí)，進(jìn)行了類別層次權(quán)重分析和特征項(xiàng)的動(dòng)態(tài)更新，為類樹層次結(jié)構(gòu)的各個(gè)節(jié)點(diǎn)構(gòu)建更具分類判斷力的特征項(xiàng)集合；進(jìn)而，采用深度優(yōu)先搜索算法并結(jié)合設(shè)定閾值的剪枝策略縮小搜索范圍，搜索得到待分類文本的最優(yōu)候選類別;最后,在候選類別的基礎(chǔ)上應(yīng)用經(jīng)典的K最近鄰(KNN)分類算法和支持向量機(jī)(SVM)分類算法進(jìn)行分類測(cè)試和對(duì)比分析。實(shí)驗(yàn)結(jié)果顯示，所提算法的總體分類性能優(yōu)于傳統(tǒng)的分類算法，而且使平均F1值較基于貪心策略的啟發(fā)式搜索算法提高了6%左右。該算法顯著提高了深層次文本分類的分類準(zhǔn)確度。

深層文本分類；類別層次；類別層次樹；深度優(yōu)先搜索；候選類別

0 引言

隨著信息技術(shù)和社交媒體的快速發(fā)展，世界已進(jìn)入網(wǎng)絡(luò)化的大數(shù)據(jù)(Big Data, BD)時(shí)代[1]。據(jù)著名國際數(shù)據(jù)公司(International Data Corporation, IDC)的統(tǒng)計(jì)，2011年全球存儲(chǔ)的數(shù)據(jù)總量達(dá)到1.8 ZB(10的21次方), 傳感網(wǎng)和物聯(lián)網(wǎng)的蓬勃發(fā)展以及實(shí)時(shí)采集的巨量流媒體數(shù)據(jù)又推動(dòng)了大數(shù)據(jù)的進(jìn)一步發(fā)展。面對(duì)指數(shù)級(jí)增長的大規(guī)模數(shù)據(jù)，人們渴望更加有效的工具對(duì)所擁有的數(shù)據(jù)信息進(jìn)行快速準(zhǔn)確分類，提取出實(shí)時(shí)、精煉、對(duì)商業(yè)分析有價(jià)值的知識(shí)，并且做到對(duì)網(wǎng)絡(luò)和信息的安全管理與控制。

為了更加有效地組織和管理大規(guī)模的文本信息，一般是按照主題類別或一個(gè)概念將這些文本信息構(gòu)建成類樹層次目錄，以便更好地存儲(chǔ)、管理和檢索、查詢這些文本資源信息得到最新的重要資訊。目前國內(nèi)關(guān)于大規(guī)模多層次文本分類的研究還處于初級(jí)階段，文獻(xiàn)[2]對(duì)大規(guī)模多層次文本分類問題的定義、求解方法進(jìn)行了系統(tǒng)詳細(xì)的論述及評(píng)價(jià)比較，并且結(jié)合實(shí)際應(yīng)用需求和問題研究現(xiàn)狀概括了大規(guī)模多層次文本分類未來的研究方向；文獻(xiàn)[3]利用類別層次體系中隱含的語義信息，提出了幾種基于類別層次結(jié)構(gòu)的大規(guī)模多層次文本分類樣本擴(kuò)展策略，從而擴(kuò)展較少類別的訓(xùn)練樣本，取得了第二名的參賽成績(2014年大規(guī)模中文新聞分類評(píng)測(cè))；文獻(xiàn)[4]將監(jiān)督學(xué)習(xí)與無監(jiān)督學(xué)習(xí)相結(jié)合，提出了一種基于分層聚類和重采樣技術(shù)的支持向量機(jī)(Support Vector Machine，SVM)算法，來解決大規(guī)模數(shù)據(jù)的分類問題，其分類性能比隨機(jī)采樣更優(yōu)。國外學(xué)者對(duì)大規(guī)模多層次的分類研究相對(duì)較早，例如，Sun等[5]提出了基于類別相似性和類別間相關(guān)距離來判別待分類文本類別屬性的方法，此方法還支持部分深層類別分類和全深層類別分類；Liu等[6]用數(shù)學(xué)分析的方法驗(yàn)證了層次式SVM分類方法在大規(guī)模多層次分類中的學(xué)習(xí)時(shí)間是可以接受的，優(yōu)于平面式的分類方法。本文在已有研究進(jìn)展的基礎(chǔ)上，對(duì)大規(guī)模多層次文本分類中的深層類別屬性判定問題進(jìn)行了更深入具體的研究，結(jié)合主流的兩階段分類思想，根據(jù)類別層次樹的特點(diǎn)和類別間的相關(guān)聯(lián)系，引入類別層次權(quán)重分析和特征項(xiàng)的動(dòng)態(tài)更新策略，為類樹層次結(jié)構(gòu)的各個(gè)節(jié)點(diǎn)構(gòu)建更具分類判斷力的特征項(xiàng)集合，搜索得到待分類文本的最優(yōu)候選類別，在此基礎(chǔ)上采用K最近鄰(KNearest Neighbor,KNN)分類算法進(jìn)行分類準(zhǔn)確率的測(cè)試，并與已有算法比較評(píng)價(jià)。

本文的主要工作有以下幾點(diǎn)：

1) 結(jié)合大規(guī)模多層次分類的類別層次結(jié)構(gòu)特點(diǎn)，使用類別層次信息和隱含的語義信息，分析各層次類別的相關(guān)聯(lián)系，給出類別層次權(quán)重的計(jì)算方法;引入概率論知識(shí)求得特征項(xiàng)的類別區(qū)分度，實(shí)現(xiàn)深層類別分類中特征項(xiàng)權(quán)重的動(dòng)態(tài)更新。

2) 在更新后的特征集基礎(chǔ)上，采用深度優(yōu)先搜索算法搜索待分類文本的候選類別集合，結(jié)合本文的閾值定義，在設(shè)置合適閾值的情況下找到待分類文本的最優(yōu)候選類別集合。

3) 對(duì)本文提出的算法進(jìn)行測(cè)試并與已有候選搜索算法比較，結(jié)果數(shù)據(jù)表明，本文提出的算法使分類結(jié)果的F1值提高了約6%，證明該算法的搜索過程是有效的，且顯著提高了深層次文本分類的分類準(zhǔn)確度。

1 相關(guān)工作

深層分類是對(duì)給定的待分類文本，首先應(yīng)用搜索算法尋找其最優(yōu)候選類別集合；然后在候選類別集合上構(gòu)建更加精準(zhǔn)的分類器來判定待分類文本的類別屬性。

在大規(guī)模多層次分類中，類別層次有較深的深度，而深層類別的分類就是類別層次相關(guān)中的精確分類，而且隨著層次深度的增加，具有兄弟關(guān)系的類別間的相似度增強(qiáng)，判別待分類文本的類別屬性就更加地困難。對(duì)此文獻(xiàn)[7]提出化繁為簡的分類策略，該策略包括搜索和分類兩個(gè)階段，首先搜索待分類文本的候選類別集合，然后建立平面分類器對(duì)文本進(jìn)行最終類別屬性的判定，而且在分類階段可以使用平面分類算法訓(xùn)練分類模型，獲得了很好的分類效果；然而文獻(xiàn)[8]并未結(jié)合類別層次結(jié)構(gòu)及深層分類的類別特點(diǎn)對(duì)候選搜索方法進(jìn)行深入研究；而文獻(xiàn)[9]雖然對(duì)候選搜索問題的計(jì)算復(fù)雜性進(jìn)行了分析，證明了該問題是非確定多項(xiàng)式(Non-Deterministic Polynomial, NP)難解的，但是其對(duì)候選類別集合的搜索是在平面分類的基礎(chǔ)上更新特征權(quán)重矩陣G獲得局部最優(yōu)選擇,也未結(jié)合類別層次相關(guān)性及類別層次權(quán)重來動(dòng)態(tài)更新類別特征項(xiàng)的權(quán)值。

候選搜索方法分為基于實(shí)例的候選搜索和基于類別的候選搜索方法兩種。由于基于實(shí)例的候選搜索方法需要與所有樣本進(jìn)行比較，時(shí)間復(fù)雜度比較高， 因此在現(xiàn)有的相關(guān)研究中很少采用這種搜索策略；而基于類別的候選搜索方法思考如何根據(jù)類別的層次位置為每個(gè)內(nèi)部類別和葉子類別分別構(gòu)造準(zhǔn)確的特征權(quán)重集合，也就是形成具有類別層次結(jié)構(gòu)的層級(jí)分類器，這也是本文重點(diǎn)討論的內(nèi)容，在下一章將會(huì)詳細(xì)的描述。閱讀相關(guān)文獻(xiàn)，本領(lǐng)域?qū)W者對(duì)特征權(quán)重集合的計(jì)算作出如下貢獻(xiàn)：文獻(xiàn)[10]使用詞頻(TermFrequency,TF)、文檔頻率(DocumentFrequency,DF)及逆類別頻率(InverseClassFrequency,ICF)給不同層次的類別選擇不同的特征集合訓(xùn)練分類模型；文獻(xiàn)[11]以類別包含所有的文本詞頻之和作為特征詞權(quán)重，為類別分別構(gòu)造類特征向量，進(jìn)而計(jì)算待分類文本與類特征向量間的余弦相似度。本文是基于類別候選搜索方法進(jìn)行以下的問題分析和驗(yàn)證的。

2 類別層次權(quán)重分析和特征項(xiàng)的動(dòng)態(tài)更新

2.1 類別層次權(quán)重的計(jì)算

大規(guī)模多層次分類中，類別被組織成類別層次樹結(jié)構(gòu)[12]，即所有類別根據(jù)相關(guān)性被組織成樹型結(jié)構(gòu)，每個(gè)類別有一個(gè)父類別(根節(jié)點(diǎn)除外)，樹的中間節(jié)點(diǎn)存儲(chǔ)自身的樣本數(shù)據(jù)，待分類文本可以被分到葉子類別，也可以被分到內(nèi)部類別中。根據(jù)樹的結(jié)構(gòu)特點(diǎn)，類別節(jié)點(diǎn)間的關(guān)系可歸納為四種：父子關(guān)系、非父上下層級(jí)關(guān)系、非同父同層關(guān)系和同父兄弟關(guān)系(簡稱并列關(guān)系)，在多層次分類中，并列關(guān)系上的準(zhǔn)確分類才是分類的關(guān)鍵點(diǎn)，決定下一步分類的走向和是否有“錯(cuò)誤傳播”問題的發(fā)生。對(duì)于深層類別的分類問題，隨著層次深度的不斷增加，具有并列關(guān)系類別間的相似性會(huì)增強(qiáng)，因此討論類別層次的相關(guān)性、類別層次權(quán)重就顯得非常有必要了。

設(shè)類別集合C={c1,c2,…,cn}，關(guān)于類別層次相關(guān)性的系列概念參照文獻(xiàn)[13]中的描述，這里不再贅述。在此對(duì)類別層次權(quán)重的計(jì)算進(jìn)行詳細(xì)的說明，在大規(guī)模多層次分類中對(duì)內(nèi)部節(jié)點(diǎn)ci建立分類器時(shí)，其訓(xùn)練樣本包括類別ci自身的訓(xùn)練樣本和類別ci直接子類含有的所有訓(xùn)練樣本，如圖1所示，類別ci的直接子類是Dsub(ci)={ci1,ci2,…,cik}，其自身包含的樣本集合為Di，把類別ci自身存儲(chǔ)的訓(xùn)練樣本加入到其直接子類中并更新，即DSub(ci)={ci0,ci1,…,cik}，其中ci0為類別ci的概念節(jié)點(diǎn)，則類別層次權(quán)重的計(jì)算方法如下：

圖1 類樹層次結(jié)構(gòu)

對(duì)類樹T的任意一個(gè)類別cj：weight(cj)=

(1)

其中:weight(cj)指類別cj的類別層次權(quán)重，correlation(ci,cj)[13]53-56指類別ci與cj間的相關(guān)性。

通過式(1)進(jìn)行遞歸計(jì)算可以得到類樹中每個(gè)類別的權(quán)重weight(cj)(1≤j≤n)。

2.2 特征項(xiàng)的動(dòng)態(tài)更新

在大規(guī)模多層次分類的類別層次結(jié)構(gòu)中，不同層次的類別具有不同的重要性，而且類別層次結(jié)構(gòu)中內(nèi)部節(jié)點(diǎn)所代表的類別本身也存儲(chǔ)一定數(shù)量的訓(xùn)練樣本，并且在訓(xùn)練過程中，類別ci直接子類所包含的訓(xùn)練樣本比其非直接子類所擁有的訓(xùn)練樣本更適合于該類的類別判斷，因此結(jié)合類別的層次權(quán)重，要對(duì)類別所包含訓(xùn)練樣本對(duì)特征項(xiàng)區(qū)分能力貢獻(xiàn)的大小進(jìn)行區(qū)別對(duì)待。

設(shè)特征項(xiàng)fs，類別ci的訓(xùn)練樣本包括ci自身存儲(chǔ)的訓(xùn)練樣本和其直接子類所包含的訓(xùn)練樣本，即有:

(2)

而且對(duì)于任何屬于DSub(ci)={ci0,ci1,…,cik}中的類別，其所包含的訓(xùn)練樣本是不重疊的，但都有可能包含特征項(xiàng)fs。?cs,ct∈DSub(ci)時(shí)，即有:

trains(cs)∩trains(ct)=?；cs≠ct

(3)

由全概率公式[14]得：

(4)

其中:P(fs|ci)表示特征項(xiàng)fs在DSub(ci)={ci0,ci1,…,cik}類別集合包含所有訓(xùn)練樣本中出現(xiàn)的概率，P(fs|cj)表示特征項(xiàng)fs在類別cj自身存儲(chǔ)的訓(xùn)練樣本中出現(xiàn)的概率。

(5)

其中:nsi表示特征項(xiàng)fs在類別ci自身存儲(chǔ)的訓(xùn)練樣本中出現(xiàn)的概率，n(ci)表示類別ci自身包含的所有特征項(xiàng)個(gè)數(shù)。

由式(4)、(5)進(jìn)行遞歸計(jì)算，就可以獲得任意特征項(xiàng)fs在類別ci以及其直接子類cj(cj∈Dsub(ci))中出現(xiàn)的條件概率值P(fs|cj)。

特征項(xiàng)的類別區(qū)分能力如下。

引入概率論的知識(shí)，用后驗(yàn)概率P(ci|fs)表示特征項(xiàng)fs對(duì)任意類別ci的區(qū)分度大小，結(jié)合全概率式(4)，根據(jù)貝葉斯定理得：

(6)

其中：P(fs)與P(fs|ci)相等，ni表示類別ci中所有訓(xùn)練樣本含有特征項(xiàng)的個(gè)數(shù)，n表示類別集合C中所有訓(xùn)練樣本含有特征項(xiàng)的個(gè)數(shù)。

在分類過程中，當(dāng)待分類文本經(jīng)過類別ci到其直接子類時(shí)，結(jié)合式(6)則特征項(xiàng)fs對(duì)其各個(gè)直接子類的區(qū)分能力可表示為：

1≤i≤n, 1≤j≤k

(7)

由上述理論可求得特征項(xiàng)fs對(duì)類別ci的各個(gè)直接子類的區(qū)分度deci(cij|fs)，并對(duì)其按降序進(jìn)行排序，選擇前t個(gè)特征項(xiàng)組成樣本的特征詞集合F={fi1,fi2,…,fit}。而且在大規(guī)模多層次文本分類的深層類別分類中，隨著類別層次深度的不斷增加，具有并列關(guān)系類別間的相似性會(huì)逐級(jí)增強(qiáng)，層次深度越深對(duì)文本的準(zhǔn)確分類就越困難，而且并列關(guān)系上的準(zhǔn)確分類才是深層分類的關(guān)鍵點(diǎn)，因此可以根據(jù)式(7)的結(jié)果在水平方向上動(dòng)態(tài)的更新特征項(xiàng)，例如，適當(dāng)?shù)亟档蜕蠈铀爬ㄐ蕴卣黜?xiàng)的deci(cij|fs)值，甚至可以刪除；也可以適當(dāng)?shù)靥岣呦聦铀杈唧w特征項(xiàng)的deci(cij|fs)值，這樣就能突顯出具有并列關(guān)系類別本身的類別特點(diǎn)，更有利于深層次類別的判定。

3 深層次分類中候選類別搜索算法

3.1 候選類別搜索中閾值的確定

本節(jié)內(nèi)容結(jié)合更新后的特征詞集合，引入深度優(yōu)先搜索(DepthFirstSearch,DFS)算法[15]并結(jié)合設(shè)定閾值的剪枝策略縮小搜索范圍，以求解待分類文本的最優(yōu)候選類別集合。在深度優(yōu)先搜索過程中，采用經(jīng)典的K最近鄰(KNN)分類算法[16]進(jìn)行層次文本分類，并結(jié)合類別層次結(jié)構(gòu)進(jìn)行以下討論。

在內(nèi)部類別節(jié)點(diǎn)ci上用類別集合DSub(ci)={ci0,ci1,…,cik}中包含的所有訓(xùn)練樣本訓(xùn)練KNN分類器hi，本文試將此訓(xùn)練樣本集合分成三個(gè)子集來確定待分類文本從類別ci到其直接子類cij的閾值Tci(cij)(1≤i≤n,1≤j≤k)，子集定義如下：

1)S1={dk|dk∈trains(ci)}；

2)S2={dk|dk∈trains(DSub(cij))}；

3)S3={dk|dk∈trains(DSub(sbe(cij)))}；

其中:DSub(cij)表示類別cij本身及其直接子類別集合，sbe(cij)表示除類別cij外的類別ci的其余直接子類。

下面對(duì)閾值Tci(cij)的確定過程進(jìn)行詳細(xì)的說明，采用經(jīng)典KNN分類算法的思想，在類別ci上建立分類器hi，在對(duì)待分類文本分類時(shí)，由分類器hi返回的K個(gè)最近鄰中屬于類別cij的樣本數(shù)目記為num(d,ci,cij)，并有如下定義：

(8)

1) 使用子集S1中的樣本訓(xùn)練分類器hi，當(dāng)待分類文本到達(dá)類別ci時(shí)，統(tǒng)計(jì)其K個(gè)最近鄰中屬于子類別cik的樣本數(shù)目num(d,ci,cik)，只要使閾值Tci(cij)大于屬于各個(gè)子類別cik的樣本數(shù)目的最大值TS1，這樣對(duì)屬于類別ci的文本就不會(huì)繼續(xù)向下層分類而只屬于ci。

2) 使用子集S2中的樣本訓(xùn)練分類器hi，當(dāng)待分類文本到達(dá)類別ci時(shí)就會(huì)被分到以類別cij為根的子樹中去，此時(shí)設(shè)定閾值Tci(cij)小于num(d,ci,cij)的最小值TS2，這樣對(duì)屬于類別ci及其子樹類別的文本就會(huì)在以ci為根的分支上繼續(xù)向下分類。

3) 使用子集S3中的樣本訓(xùn)練分類器hi，當(dāng)待分類文本經(jīng)過分類器hi后，將會(huì)分到類別cij的并列關(guān)系類別cik(cik∈sbe(cij))中去，此時(shí)設(shè)定閾值Tci(cij)大于TS3，這樣能使屬于類別cij的文本在經(jīng)過分類器hi后不能被分到其他兄弟類別中去。經(jīng)過以上過程，取Tci(cij)≥max(TS1,TS3)∩Tci(cij)≤TS2(Tci(cij)∈Z+)的值作為確定的待分類文本從類別ci到其直接子類cij的閾值，就可以為類樹T中的每個(gè)類別節(jié)點(diǎn)求得合適的閾值。

3.2 候選類別搜索算法描述

經(jīng)過3.1節(jié)的討論就可以為類別層次結(jié)構(gòu)中的每個(gè)內(nèi)部類別節(jié)點(diǎn)求得其對(duì)各直接子類的閾值。但是當(dāng)待分類文本經(jīng)過類別ci到達(dá)其直接子類時(shí)，可能有多個(gè)子類cik滿足閾值條件，因此必須對(duì)這些子類cik進(jìn)行分別處理，采用深度優(yōu)先搜索算法將滿足條件的子類分支逐個(gè)遍歷，就得到了所需的待分類文本的候選類別集合。算法步驟如下：

算法：候選類別搜索算法(CandidateCategorySearchAlgorithm,CCSA)。

輸入：類樹T，待分類文本d，參數(shù)k。

輸出：候選類別集合(Candidate Category Set(d)，CCS(d))。

Algorithm CCSA(T,d,k){ 初始化T，為T中每個(gè)類別計(jì)算特征詞集合F如果ci是葉子節(jié)點(diǎn)且num(d,ci)>Tci(cij)ci加入CCS(d)； 否則調(diào)用方法DFS(ci,d,k) }

AlgorithmDFS(ci,d,k){ 計(jì)算閾值Tci(cij) 如果ci是葉子節(jié)點(diǎn)且num(d,ci)>Tci(cij)ci加入CCS(d)； 否則{ 計(jì)算num(d,ci,cik) 如果num(d,ci,cik)>Tci(cij)cik加入候選序列L(d)； 對(duì)L(d)中的每個(gè)類別ct，調(diào)用方法DFS(ct,d,k) }

}

4 實(shí)驗(yàn)

選用CWT70th數(shù)據(jù)集中具有足夠訓(xùn)練樣本的類別組成類別集合，并構(gòu)建成二層的類樹層次結(jié)構(gòu)，利用Java的開源軟件包HTMLParser對(duì)解壓的網(wǎng)頁文件預(yù)處理，采用中國科學(xué)院最新發(fā)布的分詞系統(tǒng)包及二次開發(fā)Java調(diào)用接口對(duì)文本數(shù)據(jù)分詞處理，還用到Weka數(shù)據(jù)挖掘工具的部分功能。實(shí)驗(yàn)過程如下。

4.1 特征項(xiàng)的有效性驗(yàn)證

隨機(jī)抽取9個(gè)類別訓(xùn)練樣本的2 800篇文檔組成類樹層次結(jié)構(gòu)且中間節(jié)點(diǎn)也存儲(chǔ)樣本，這符合上文所描述的類樹層次結(jié)構(gòu)的特點(diǎn)，用詞頻逆文檔頻率(Term-InverseDocumentFrequency,TF-IDF)[17]方法計(jì)算特征詞的權(quán)重，并根據(jù)第2章的內(nèi)容對(duì)特征詞集合進(jìn)行刪選、動(dòng)態(tài)更新后得到類別ci的特征項(xiàng)集合為Wci={w1,w2,…,wt}，為了評(píng)價(jià)特征項(xiàng)集合對(duì)類別的覆蓋范圍及避免分類時(shí)出現(xiàn)偏向的問題，實(shí)驗(yàn)中用了如下公式對(duì)所選特征項(xiàng)間的相似度進(jìn)行了衡量。

(9)

在類樹結(jié)構(gòu)的第一層分別用第2章描述的特征選取方法、信息增益(InformationGain,IG)和χ2(Chi-square,CHI)統(tǒng)計(jì)選取不同數(shù)量的特征詞并比較特征詞間的相似度；在第二層中選擇社會(huì)科學(xué)類構(gòu)建特征詞集合，也分別計(jì)算三種方法所得特征詞之間的相似度。結(jié)果數(shù)據(jù)如表1所示。

分析表中數(shù)據(jù)可得，第一層選取的特征詞集合中，本文方法與IG方法的相似度比較各有優(yōu)劣，特征詞數(shù)目為200、400時(shí)，IG方法優(yōu)于本文方法；當(dāng)特征詞數(shù)目逐漸增多時(shí)，本文方法優(yōu)于IG方法，而CHI方法的效果明顯不理想。第二層選取的特征詞集合中，本文方法優(yōu)于IG和CHI方法，分析原因，這主要是本文建立的類樹層次結(jié)構(gòu)中，中間節(jié)點(diǎn)存儲(chǔ)有自身的訓(xùn)練樣本，在特征詞的選擇過程中既考慮了類別的層次位置和權(quán)重也進(jìn)行了特征詞的動(dòng)態(tài)更新，選取了更有利于深層分類的特征詞集合，這也進(jìn)一步說明了在大規(guī)模多層次文本分類中，面對(duì)大規(guī)模文本數(shù)據(jù)和高維特征詞集合時(shí)，本文方法選擇的特征詞能夠較好地覆蓋在所在層次的各個(gè)類別上，具有解決深層分類問題的優(yōu)勢(shì)，為下一步搜索準(zhǔn)確的候選類別做好了充分的準(zhǔn)備和基礎(chǔ)。

表1 類樹結(jié)構(gòu)中第一、二層所選不同數(shù)目特征詞間的相似度比較

4.2 候選類別搜索算法及分類準(zhǔn)確率驗(yàn)證

為了驗(yàn)證第3章提出的候選類別搜索算法的有效性，采用開放式分類目錄(OpenDirectoryProject,ODP)[18]的中文數(shù)據(jù)和20Newsgroups語料庫[19]進(jìn)行實(shí)驗(yàn)?；贠DP本身的分類目錄結(jié)構(gòu)，本文選擇單標(biāo)簽且只有一個(gè)父類的文本數(shù)據(jù)組成深度為5的類樹層次結(jié)構(gòu)，其中包括7個(gè)大類別組成了類樹層次結(jié)構(gòu)的第一層，有商業(yè)(5 623)、參考(2 220)、計(jì)算機(jī)(1 643)、社會(huì)(1 554)、藝術(shù)(1 031)、科學(xué)(923)、健康(747)，共選取9 576篇中文樣本構(gòu)成類樹層次結(jié)構(gòu)；并且選取20Newsgroups語料庫的8 000篇樣本數(shù)據(jù)組成深度為3的類樹層次結(jié)構(gòu)，0～2層分別有：288篇、6 756篇和956篇樣本，詳細(xì)情況如表2和表3所示。

表2 ODP類樹層次結(jié)構(gòu)樣本分布

將實(shí)驗(yàn)數(shù)據(jù)集分成5份進(jìn)行交叉驗(yàn)證，并與經(jīng)典的KNN分類算法和SVM算法進(jìn)行比較，為了評(píng)估整體的分類效果，采用宏平均準(zhǔn)確率和召回率評(píng)價(jià)分類結(jié)果。通過多次實(shí)驗(yàn)，取K=45、特征詞數(shù)量為500時(shí)分類效果最好。實(shí)驗(yàn)數(shù)據(jù)如表4所示。

由表4的實(shí)驗(yàn)數(shù)據(jù)可得，本文所提出的分類算法要比傳統(tǒng)KNN算法和SVM算法的分類效果好很多，根據(jù)公式：F1=2*準(zhǔn)確率*召回率/(準(zhǔn)確率+召回率)，數(shù)據(jù)集ODP取得5次數(shù)據(jù)的平均F1值分別為0.90、0.84和0.84；數(shù)據(jù)集20 Newsgroups取得5次數(shù)據(jù)的平均F1值分別為0.87、0.83和0.81，得到本文算法的總體性能比經(jīng)典算法的好。

為了討論在最好實(shí)驗(yàn)條件下，加入類別層次信息和特征項(xiàng)動(dòng)態(tài)更新后的候選類別搜索算法的改進(jìn)效果，在以下實(shí)驗(yàn)中，改進(jìn)的搜索算法和文獻(xiàn)[10]45-48中提出的基于貪心策略的啟發(fā)式搜索算法(Heuristic Learning, HL)進(jìn)行了比較，為了保證比較的準(zhǔn)確性，選擇在ODP數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)，并取HL算法評(píng)價(jià)標(biāo)準(zhǔn)Vk的最大值，多次實(shí)驗(yàn)結(jié)果表明在Vk=0.89～0.91時(shí)，HL算法的平均F1值達(dá)到0.85，本文算法較之提高了大約6%((0.90-0.85)/0.85)，結(jié)果進(jìn)一步說明了加入了類別層次信息和特征項(xiàng)動(dòng)態(tài)更新后的候選類別搜索改進(jìn)算法具有一定的實(shí)際應(yīng)用意義。但是在分類模型的建立和候選類別的搜索階段，本文算法花費(fèi)的時(shí)間比文獻(xiàn)[10]中的HL算法的實(shí)驗(yàn)時(shí)間多花費(fèi)約986ms，而且每次都有一定的波動(dòng)，分析深層原因，在類樹層次結(jié)構(gòu)的建立過程中要為每個(gè)類別分別構(gòu)建特征項(xiàng)集合并且當(dāng)待分類文本到達(dá)時(shí)，根據(jù)其搜索路徑要計(jì)算路徑分支類別各自的閾值，這需要花費(fèi)大量的時(shí)間，影響了算法的總體分類性能。

表3 20 Newsgroups類樹層次結(jié)構(gòu)樣本分布

表4 三種分類算法的分類效果比較

5 結(jié)語

針對(duì)大規(guī)模多層次文本分類中的深層類別分類問題，本文結(jié)合類樹層次結(jié)構(gòu)分析了類別層次相關(guān)性及權(quán)重計(jì)算，在此基礎(chǔ)上引入深度優(yōu)先搜索算法找到待分類文本的最優(yōu)候選類別集合，最終確定待分類文本的類別屬性，相比已有搜索算法使其F1值提高了6%左右；但是本文在實(shí)驗(yàn)數(shù)據(jù)集上有意識(shí)地選取訓(xùn)練樣本比較充分的大類別，忽略了較少樣本的類別和稀有類別，使算法的適用范圍有了局限性。對(duì)此，在下一步的學(xué)習(xí)中考慮結(jié)合類別層次結(jié)構(gòu)中蘊(yùn)含的類別名稱、描述信息以及類別間的層次結(jié)構(gòu)關(guān)系來擴(kuò)展稀有類別的訓(xùn)練樣本，幫助稀有類別的特征學(xué)習(xí)，提高稀有文本的分類準(zhǔn)確率；還有對(duì)于大規(guī)模的多層次文本分類研究，系統(tǒng)運(yùn)行時(shí)間較長，對(duì)計(jì)算環(huán)境的要求比較高，因此，在后續(xù)嘗試搭建分布式計(jì)算環(huán)境，應(yīng)用當(dāng)前流行的分布式計(jì)算技術(shù)進(jìn)一步提高深層類別分類的準(zhǔn)確率和運(yùn)行效率。

References)

[1] 嚴(yán)霄鳳,張德馨.大數(shù)據(jù)研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2013,23(4):168-172.(YAN X F, ZHANG D X. Big data research [J]. Computer Technology and Development, 2013, 23(4): 168-172.)

[2] 何力,賈焰,韓偉紅,等.大規(guī)模層次分類問題研究及其進(jìn)展[J].計(jì)算機(jī)學(xué)報(bào), 2012,35(10):2101-2115.(HE L, JIA Y, HAN W H, et al. Research and development of large scale hierarchical classification problem [J]. Chinese Journal of Computers, 2012, 35(10): 2101-2115.)

[3] 李保利.基于類別層次結(jié)構(gòu)的多層文本分類樣本擴(kuò)展策略[J].北京大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,51(2):357-366.(LI B L. Expanding training dataset with class hierarchy in hierarchical text categorization [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2015, 51(2): 357-366.)

[4] 張永,浮盼盼,張玉婷.基于分層聚類及重采樣的大規(guī)模數(shù)據(jù)分類[J].計(jì)算機(jī)應(yīng)用,2013,33(10):2801-2803.(ZHANG Y, FU P P, ZHANG Y T. Large-scale data classification based on hierarchical clustering and resembling [J]. Journal of Computer Applications, 2013, 33(10): 2801-2803.)

[5] SUN A, LIM E P. Hierarchical text classification and evaluation [C]// Proceedings of the 2001 IEEE International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2001: 521-528.

[6] LIU T-Y, YANG Y M, WAN H, et al. Support vector machines classification with a very large-scale taxonomy [J]. ACM SIGKDD Explorations Newsletter, 2005, 7(1): 36-43.

[7] XUE G-R, XING D, YANG Q, et al. Deep classification in large-scale text hierarchies [C]// Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 2008: 619-626.

[8] MALIK H. Improving hierarchical SVM by hierarchy flattening and lazy classification [C]// Proceedings of the Large-Scale Hierarchical Classification Workshop in 32nd European Conference on Information Retrial. Milton Keynes, UK: 〖s.n.〗, 2010: 1-12.

[9] 何力,丁兆云,賈焰,等.大規(guī)模層次分類中的候選類別搜索[J].計(jì)算機(jī)學(xué)報(bào),2014,37(1):41-49.(HE L, DING Z Y, JIA Y, et al. Category candidate search in large scale hierarchical classification [J]. Chinese Journal of Computers, 2014, 37(1): 41-49.).

[10] CECI M, MALERBA D. Classifying Web documents in a hierarchy of categories: a comprehensive study[J]. Journal of Intelligent Information System, 2007, 28(1): 37-78.

[11] OH H S, CHOI Y J, MYAENG S H. Combining global and local information for enhanced deep classification [C]// Proceeding of the 2010 ACM Symposium on Applied Computing. New York: ACM, 2010: 1760-1768.

[12] WANG K, ZHOU S, HE Y. Hierarchical classification of real life documents [C]// Proceeding of the 1st SIAM International Conference on Data Mining. Philadelphia, PA: SIAM, 2001: 33-46.

[13] 祝翠玲.基于類別結(jié)構(gòu)的文本層次分類方法研究[D].濟(jì)南:山東大學(xué),2011:52-56.(ZHU C L. Research of hierarchical text classification methods based on category structure [D]. Jinan: Shandong University, 2011: 52-56.)

[14] 盛驟,謝式千,潘承毅.概率論與數(shù)理統(tǒng)計(jì)[M].北京：高等教育出版社,2015:11-65.(SHENG Z, XIE S Q, PAN C Y. Probability and Mathematical Statistics [M]. Beijing: Higher Education Press, 2015: 11-65.)

[15] 許少華.算法設(shè)計(jì)與分析[M].哈爾濱：哈爾濱工業(yè)大學(xué)出版社,2011:21-78. (XU S H. Algorithm Design and Analysis [M]. Harbin: Harbin Institute of Technology Press, 2011: 21-78.)

[16] CHAKRABARTI S, JOSHI M, TAWDE V. Enhanced topic distillation using text, markup tags, and hyperlinks [C]// Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 2001: 208-216.

[17] ZHU S, LIU Y, LIU M, et al. Research on feature extraction from Chinese text for opinion mining [C]// Proceedings of the 2009 International Conference on Asian Languages Processing. Washington, DC: IEEE Computer Society, 2009: 7-10.

[18] The directory of the Web. The simplified chinese data set of open directory project [EB/OL]. [2016- 05- 01]. http://www.dmoz.org/World/Chinese_Simplified/.

[19] Ken Lang. The data set of 20Newsgroups [EB/OL]. [2016- 09- 07]. http://people.csail.mit.edu/jrennie/20Newsgroups/.

This work is partially supported by the National Natural Science Foundation of China (61662043).

ZHANG Zhonglin, born in 1965, Ph. D., professor. His research interests include intelligent information processing, software engineering.

LIU Shuchang, born in 1989, M. S. candidate. His research interests include data mining.

JIANG Fentao, born in 1991, M. S. candidate. Her research interests include Web data mining.

Candidate category search algorithm in deep level classification

ZHANG Zhonglin, LIU Shuchang*, JIANG Fentao

(SchoolofElectronicandInformationEngineering,LanzhouJiaotongUniversity,LanzhouGansu730070,China)

Aiming at the problem of low classification accuracy and slow processing speed in deep classification, a candidate category searching algorithm for text classification was proposed. Firstly, the search, classification of two-stage processing ideas were introduced, and the weighting of the category hierarchy was analyzed and feature was updated dynamically by combining with the structure characteristics of the category hierarchy tree and the related link between categories as well as other implicit domain knowledge. Meanwhile feature set with more classification judgment was built for each node of the category hierarchy tree. In addition, depth first search algorithm was used to reduce the search range and the pruning strategy with setting threshold was applied to search the best candidate category for classified text. Finally, the classicalKNearest Neighbor (KNN) classification algorithm and Support Vector Machine (SVM) classification algorithm were applied to classification test and contrast analysis on the basis of candidate classes. The experimental results show that the overall classification performance of the proposed algorithm is superior to the traditional classification algorithm, and the averageF1value is about 6% higher than the heuristic search algorithm based on greedy strategy. The algorithm improves the classification accuracy of deep text classification significantly.

deep text classification; class hierarchy; tree-structured class hierarchy; depth first search; candidate category

2016- 09- 18;

2016- 10- 18。

國家自然科學(xué)基金資助項(xiàng)目(61662043)。

張忠林(1965—)，男，河北衡水人，教授，博士，CCF會(huì)員，主要研究方向：智能信息處理、軟件工程； 劉述昌(1989—)，男，甘肅金昌人，碩士研究生，主要研究方向：數(shù)據(jù)挖掘； 江粉桃(1991—)，女，甘肅定西人，碩士研究生，主要研究方向：Web數(shù)據(jù)挖掘。

1001- 9081(2017)03- 0635- 05

10.11772/j.issn.1001- 9081.2017.03.635

TP

A