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

張忠林，劉述昌，江粉桃

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

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

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

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

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

深層文本分類；類別層次；類別層次樹；深度優先搜索；候選類別

0 引言

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

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

本文的主要工作有以下幾點：

1) 結合大規模多層次分類的類別層次結構特點，使用類別層次信息和隱含的語義信息，分析各層次類別的相關聯系，給出類別層次權重的計算方法;引入概率論知識求得特征項的類別區分度，實現深層類別分類中特征項權重的動態更新。

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

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

1 相關工作

深層分類是對給定的待分類文本，首先應用搜索算法尋找其最優候選類別集合；然后在候選類別集合上構建更加精準的分類器來判定待分類文本的類別屬性。

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

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

2 類別層次權重分析和特征項的動態更新

2.1 類別層次權重的計算

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

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

圖1 類樹層次結構

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

(1)

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

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

2.2 特征項的動態更新

在大規模多層次分類的類別層次結構中，不同層次的類別具有不同的重要性，而且類別層次結構中內部節點所代表的類別本身也存儲一定數量的訓練樣本，并且在訓練過程中，類別ci直接子類所包含的訓練樣本比其非直接子類所擁有的訓練樣本更適合于該類的類別判斷，因此結合類別的層次權重，要對類別所包含訓練樣本對特征項區分能力貢獻的大小進行區別對待。

設特征項fs，類別ci的訓練樣本包括ci自身存儲的訓練樣本和其直接子類所包含的訓練樣本，即有:

(2)

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

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

(3)

由全概率公式[14]得：

(4)

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

(5)

其中:nsi表示特征項fs在類別ci自身存儲的訓練樣本中出現的概率，n(ci)表示類別ci自身包含的所有特征項個數。

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

特征項的類別區分能力如下。

引入概率論的知識，用后驗概率P(ci|fs)表示特征項fs對任意類別ci的區分度大小，結合全概率式(4)，根據貝葉斯定理得：

(6)

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

在分類過程中，當待分類文本經過類別ci到其直接子類時，結合式(6)則特征項fs對其各個直接子類的區分能力可表示為：

1≤i≤n, 1≤j≤k

(7)

由上述理論可求得特征項fs對類別ci的各個直接子類的區分度deci(cij|fs)，并對其按降序進行排序，選擇前t個特征項組成樣本的特征詞集合F={fi1,fi2,…,fit}。而且在大規模多層次文本分類的深層類別分類中，隨著類別層次深度的不斷增加，具有并列關系類別間的相似性會逐級增強，層次深度越深對文本的準確分類就越困難，而且并列關系上的準確分類才是深層分類的關鍵點，因此可以根據式(7)的結果在水平方向上動態的更新特征項，例如，適當地降低上層所包含概括性特征項的deci(cij|fs)值，甚至可以刪除；也可以適當地提高下層所需具體特征項的deci(cij|fs)值，這樣就能突顯出具有并列關系類別本身的類別特點，更有利于深層次類別的判定。

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

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

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

在內部類別節點ci上用類別集合DSub(ci)={ci0,ci1,…,cik}中包含的所有訓練樣本訓練KNN分類器hi，本文試將此訓練樣本集合分成三個子集來確定待分類文本從類別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的其余直接子類。

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

(8)

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

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

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

3.2 候選類別搜索算法描述

經過3.1節的討論就可以為類別層次結構中的每個內部類別節點求得其對各直接子類的閾值。但是當待分類文本經過類別ci到達其直接子類時，可能有多個子類cik滿足閾值條件，因此必須對這些子類cik進行分別處理，采用深度優先搜索算法將滿足條件的子類分支逐個遍歷，就得到了所需的待分類文本的候選類別集合。算法步驟如下：

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

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

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

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

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

}

4 實驗

選用CWT70th數據集中具有足夠訓練樣本的類別組成類別集合，并構建成二層的類樹層次結構，利用Java的開源軟件包HTMLParser對解壓的網頁文件預處理，采用中國科學院最新發布的分詞系統包及二次開發Java調用接口對文本數據分詞處理，還用到Weka數據挖掘工具的部分功能。實驗過程如下。

4.1 特征項的有效性驗證

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

(9)

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

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

表1 類樹結構中第一、二層所選不同數目特征詞間的相似度比較

4.2 候選類別搜索算法及分類準確率驗證

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

表2 ODP類樹層次結構樣本分布

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

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

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

表3 20 Newsgroups類樹層次結構樣本分布

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

5 結語

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

References)

[1] 嚴霄鳳,張德馨.大數據研究[J].計算機技術與發展,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] 何力,賈焰,韓偉紅,等.大規模層次分類問題研究及其進展[J].計算機學報, 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] 李保利.基于類別層次結構的多層文本分類樣本擴展策略[J].北京大學學報(自然科學版),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] 張永,浮盼盼,張玉婷.基于分層聚類及重采樣的大規模數據分類[J].計算機應用,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] 何力,丁兆云,賈焰,等.大規模層次分類中的候選類別搜索[J].計算機學報,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] 祝翠玲.基于類別結構的文本層次分類方法研究[D].濟南:山東大學,2011:52-56.(ZHU C L. Research of hierarchical text classification methods based on category structure [D]. Jinan: Shandong University, 2011: 52-56.)

[14] 盛驟,謝式千,潘承毅.概率論與數理統計[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] 許少華.算法設計與分析[M].哈爾濱：哈爾濱工業大學出版社,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。

國家自然科學基金資助項目(61662043)。

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

1001- 9081(2017)03- 0635- 05

10.11772/j.issn.1001- 9081.2017.03.635

TP

A