基于類鄰域字典的線性回歸文本分類

武 嬌，洪彩鳳，顧永春，顧興全，金世舉

（1.中國計量大學 理學院，杭州 310018；2.中國計量大學 標準化學院，杭州 310018）

0 概述

隨著壓縮感知理論［1］的興起，圖像處理領域出現了很多稀疏表示分類（Sparse Representation Classification，SRC）方法［2-6］。由于此類方法基于同類數據應當位于相同低維子空間這一直觀認識，因此待分類的測試樣本可以由同類別樣本的線性組合充分表示。目前多數SRC 方法都采用了協作表示（Collaborative Representation，CR）的設計思想，即使用所有的訓練樣本來表示測試樣本，因此，大多都被命名為基于協作表示的分類（Collaborative Representation based Classification，CRC）方法。這種基于表示的分類方法將待分類的測試樣本表示為訓練樣本的線性組合，然后把測試樣本分配到具有最小編碼誤差的類別。研究者通過對測試樣本的編碼過程使用不同的正則項，提出了不同的分類算法，如基于l1-范數正則約束的SRC［2］、基于l2-范數正則約束的CRC［3-5］和基于lp-范數稀疏表示的分類［6］。

SRC 在人臉識別等圖像分類任務中取得的成功，促使一些研究者將其應用于文本分類［7-12］。然而在文本分類中，SRC 面臨數據的高維性導致的高計算復雜度問題。研究者對此又提出了一些新的特征投影、子空間學習和字典學習方法［13-15］，通過提取更具判別性的特征字典來提高SRC 的性能，但這些方法的優化求解過程通常較為復雜。此外，SRC 由于訓練樣本數量過大導致在對測試樣本表示過程中的優化問題進行求解時計算復雜度較高。針對此問題，研究者通過對訓練樣本進行選擇［7-9］或變換［10-12］來減少字典的原子個數，從而降低對測試樣本稀疏表示的計算復雜度。近年來提出的基于K 近鄰（K-Nearest Neighbor，KNN）的SRC［3，16-18］和CRC［19-20］正屬于“樣本選擇”方法。這些方法通過計算測試樣本與訓練樣本間的相似度或設計優化算法，從訓練樣本中選擇近鄰樣本作為縮減的字典，并采用CR 的形式來表示測試樣本。雖然字典規模的縮小在一定程度上降低了對測試樣本編碼的復雜度，但基于lp-范數（p≤1）正則約束的SRC 對測試樣本稀疏表示的求解過程仍較為復雜。文獻［2］指出，基于CR 的SRC 在分類性能提升方面起關鍵作用的并不是對測試樣本表示的l1-范數稀疏性約束，而是CR 發揮了重要作用。雖然l1-范數稀疏性能夠提供一定的判別性能力，但基于l2-范數正則約束的CRC 的分類性能與基于l1-范數正則約束的SRC 的分類性能相近，并且基于l2-范數正則約束的CR 優化問題具有閉式解，其計算復雜度顯著低于SRC。此外，l1-范數最小化通常用于求解欠定方程的稀疏解，對應于在訓練樣本數量較多時構成冗余字典的情況。當訓練樣本數量較少且低于數量維數時，將形成超定方程，此時l2-范數優化更為適用。

針對文本分類問題，本文提出一種基于類鄰域字典的線性回歸分類（CND-LRC）方法，該方法可以看作是基于線性回歸分類方法［21］的推廣和改進。CND-LRC 使用KNN 進行樣本選擇得到縮減的表示字典，但與上述基于KNN 的SRC 和CRC 不同，其并非在所有的訓練樣本中選擇測試樣本的K個近鄰樣本構成表示字典，而是對每個類別的訓練樣本分別選擇測試樣本的K個近鄰構成各類別的子鄰域字典。在對測試樣本進行表示和分類時，本文分別提出基于級聯類鄰域字典的LRC 模型CCND-LRC 和基于類鄰域字典的LRC 模型CND-LRC。CCND-LRC使用由各個類子鄰域字典連接得到的級聯字典學習測試樣本的線性表示，是一種CR 模型，CND-LRC 則分別學習測試樣本在每個類子鄰域字典下的線性表示。兩種表示模型都采用l2-范數優化以提高計算效率。此外，為緩解噪聲數據對分類性能的影響，本文設計一種類相關度測量用以度量測試樣本與各個類別之間的相關度，對于極不相似的類別，將其包含的訓練樣本看作是與測試樣本不相關的“噪聲”而直接從字典中刪除，通過這種類別裁剪方法提高分類性能。

1 基于稀疏和協作表示的文本分類

將來自于C個不同類別的N個訓練樣本記為X=[X1，X2，…，XC]∈RM×N，其中是由屬于第i類的Ni個訓練樣本組成的矩陣，在向量空間模型（Vector Space Model，VSM）下，M是特征詞的個數，樣本xin是以這M個特征詞的統計量作為特征項構成的第i類第n個文檔的表示向量。

在SRC 和CRC 方法中，測試樣本y∈RM首先被表示為所有訓練樣本的線性組合：

然后，由每個類別的訓練樣本Xi和相應的表示系數αi重構測試樣本y，并計算重構誤差：

最后，將測試樣本y分配到重構誤差最小的那個類別：

1.1 基于l1-范數正則約束的SRC

SRC［2］假設式（1）是測試樣本y在訓練樣本X下的稀疏表示，X=[X1，X2，…，XC]，即系數向量α是稀疏向量。當y屬于第i類時，通常y能夠被Xiαi很好地近似，即在系數向量α中除了αi中的系數顯著不為零，αk(k≠i)中的系數幾乎都很接近零。

為得到式（1）的稀疏解，需要求解如下l0-范數優化問題：

其中，‖ ‖·0為向量l0-范數，表示向量中非零元素的個數。l0-范數優化是NP-hard 問題，關于壓縮感知理論［1］的研究表明，在某些條件下，l0-范數優化可等價地轉化為式（5）或式（6）所示的l1-范數最小化問題。

其中，λ＞0 是正則化參數，用于平衡表示的精確度和解的稀疏度，一般較大的λ會產生更為稀疏的解。目前，已存在許多求解l0-范數優化的貪婪追蹤算法［22-23］和l1-最小化算法［24-26］。

1.2 基于l2-范數正則約束的CRC

文獻［2］指出，SRC 方法對于分類性能的提升主要是協作表示起到了重要作用，而不是稀疏表示。考慮到l1-最小化問題（如式（5）和式（6））求解的復雜性，文獻［2］在CRC 的工作中研究了基于l2-范數正則約束的表示模型，取得了與SRC 相近的分類性能。

基于l2-范數正則約束CR 優化問題為：

該模型又被稱為嶺回歸。模型中的正則化參數λ一方面起到了獲得穩定的最小二乘解的作用，另一方面使得式（7）的解是比l1-范數表示的稀疏度低得多的一種“弱稀疏”解［4］。盡管l2-范數表示不具有強稀疏性，但仍能夠保持良好的分類性能。與式（5）和式（6）相比，不需要通過復雜的優化和迭代計算，對l2-范數優化可以容易地得到其閉式解。

基于SRC 和CRC 的分類算法描述如下：

2 基于類鄰域字典的線性回歸分類

本節將KNN 的思想應用于類子鄰域字典的提取，同時提出一種類相關度測量來度量測試樣本與各個類別之間的相關度。在使用類子鄰域字典對測試樣本進行線性表示時，基于計算的類相關度大小對噪聲類進行裁剪，以提高的算法的效率，減弱噪聲數據的影響，提高表示的精確度，從而優化最終的分類性能。

2.1 類鄰域字典提取

在第i個類別的訓練樣本Xi中，通過選擇測試樣本y的K個最近鄰樣本，構成第i個縮減的類鄰域字典。一般K近鄰的選擇是通過計算樣本之間的距離來實現的。在文本處理任務中，常使用余弦相似度來刻畫文本向量之間的距離。向量y和x之間的余弦相似度定義為：

其中，y·x表示y與x的內積，‖ · ‖2是向量的l2-范數。可以看出，當對樣本做歸一化處理后，即其l2-范數等于1，此時兩向量的余弦相似度即為兩者的內積。余弦相似值越大表示兩個向量越相似，當余弦相似值小于等于零時，表示兩個向量不相似。由此，將兩個文本向量y和x的相似度定義為：

計算測試樣本y與第i個類的Ni個訓練樣本的相似度，并從大到小進行排序：

縮減的類鄰域字典由最大的K個相似度對應的訓練樣本組成。定義Ni(y)為測試樣本y在第i類的K個近鄰樣本的索引集，|Ni(y)|=K，則記第i個類鄰域字典為即以Xi中對應于Ni(y)的那些列向量構成的矩陣。

2.2 類相關度測量

在樣本之間相似度的基礎上，本文將測試樣本y與第i類之間的類相關度定義為：

2.3 CCND-LRC 模型

本文提出的CCND-LRC 模型采用SRC 和CRC方法中協作表示（CR）的思想，將2.1 節中提取的類鄰域字典進行拼接，形成由多個子字典構成的級聯字典，記為：

利用該級聯字典對測試樣本y構造如下基于l2-范數正則約束的線性回歸模型：

其中，AN(y)是大小為CK×CK的矩陣，ICK是CK×CK單位矩陣。

當樣本的維度大于等于級聯字典中樣本的個數時，即M≥CK，利用式（15）計算回歸系數向量其計算復雜度主要由求AN(y)的逆矩陣決定。因為AN(y)是CK×CK的正定矩陣，所以使用Cholesky 分解［27］對AN(y)求逆的復雜度為O((CK)3/3+(CK)2)。

當樣本的維度小于級聯字典中樣本的個數時，即M＜CK，利用Woodbury 矩陣恒等式，式（15）中回歸系數解又可表示為：

此時，對M×M矩陣BN(y)求逆的計算復雜度為O(M3/3+M2)。

利用2.2 節中提出的類相關度對噪聲類進行裁剪后，由類鄰域字典個數的減少將導致級聯字典維度的降低。用C(y)表示裁剪后被保留下來的類鄰域字典的標識集，字典個數Cd=|C(y)|＜C，則級聯字典被縮減為大小為M×CdK的矩陣，記為，那么由式（15）計算回歸系數向量時，對矩陣求逆的計算復雜度將降低為O((CdK)3/3+(CdK)2)，被裁剪的類鄰域字典對應的回歸系數直接設置為零。CCND-LRC 算法描述如下：

2.4 CND-LRC 模型

與CCND-LRC 采用的協作表示不同，CND-LRC 分別學習測試樣本在每個類子鄰域字典下的線性表示。使用第i個類鄰域字典對測試樣本y線性表示的l2-范數正則約束回歸模型為：

其中，αi∈RK是回歸系數向量。與式（14）的最優解類似，式（19）的解可表示為：

當樣本的維度大于等于類鄰域字典的樣本個數時，即M≥K，計算回歸系數向量的計算復雜度由計算的逆矩陣決定，復雜度為O(K3/3+K2)。那么，計算測試樣本y在C個類鄰域字典表示下的回歸系數向量的計算復雜度即為O(C(K3/3+K2))。當M＜K時，由對求逆的復雜度O(M3/3+M2)可得，計算C個回歸系數向量的計算復雜度為O(C(M3/3+M2))。與CCND-LRC 算法相比，可以看出當樣本維度M較高時，CND-LRC 算法在計算效率上有較大的優勢。同樣，利用類相關度對噪聲類進行裁剪后，可進一步提高CND-LRC 的計算效率。CND-LRC 算法描述如下：

3 實驗結果與分析

本文通過對2 個長文本語料和2 個短文本英文語料的實驗來驗證基于類鄰域字典的線性回歸模型在文本分類任務上的有效性和優越性。實驗包括兩大部分：第一部分為模型參數實驗，第二部分為文本分類實驗。在參數實驗中，討論了CND-LRC 和CCND-LRC 算法的正則參數λ、類裁剪參數和K-近鄰參數對分類性能的影響。在文本分類實驗中，將CND-LRC 和CCND-LRC 與MSRC［8］、PCA-SVM［9］、SRC［3］、E-SRC［12］、KNN-SRC［16］算法的分類精度和算法效率進行比較。

實驗使用的長文本語料為復旦中文語料庫［28］和20newgroup 英文語料，短文本語料［29］為Search-snippets、Stack-overflow 和Bio-medical，語料類別及數量見表1。語料中的文本用VSM 進行向量表示，在復旦語料庫和20newgroup 中，通過提取前5 000 個詞項的TF-IDF（Term Frequency-Inverse Document Frequency）特征，形成訓練和測試樣本的5 000 維VSM 向量，對短文本語料提取前3 000 個TF-IDF 特征，形成訓練和測試樣本的3 000 維VSM 向量。實驗以微平均F1值（Micro-F1）和宏平均F1 值（Macro-F1）作為算法分類性能的評價指標。實驗的運行環境為Spyder 3（Python 3.6.5），Intel?CoreTMi5-7500U，內存8 GB。

表1 語料類別及數量Table 1 Type and quantity of corpus

3.1 模型參數實驗

3.1.1 正則參數的敏感性分析

正則參數λ在實驗中起到了獲得穩定的最小二乘解的作用，圖1 為不同λ下CCND-LRC 和CND-LRC算法對復旦語料的分類效果。實驗結果表明，當λ較小時，CCND-LRC 和CND-LRC 算法的分類性能更優。后續實驗選取λ=0.2。

圖1 CCND-LRC 和CND-LRC 算法的分類F1-值隨正則參數λ 的變化趨勢Fig.1 F1-scores of CCND-LRC and CND-LRC with varying regularization parameter λ

3.1.2 類裁剪參數的敏感性分析

圖2 和圖3 分別是由類相關度閾值參數篩選后得到的不同類別數目下基于噪聲類裁剪的CCND-LRC與CND-LRC 算法的分類結果。可以看出：對類別數較多的長文本語料（復旦語料庫和20newgroup 語料（20 類）），在裁剪為10 類時算法的分類性能最好，分類Macro-F1 與Micro-F1 值達到最高，說明結合噪聲類裁剪策略的CCND-LRC 與CND-LRC 算法對于長文本多類別語料的分類效果較好；對包含20 個類的Bio-medical 短文本語料進行噪聲類裁剪后，在保留2 個類時能夠達最優的分類性能，說明對短文本語料本文提出的類相關度測量能夠很好地度量測試樣本與各類別之間的相關度；對僅包含8 類的Searchsnippets 語料，噪聲類裁剪對算法的分類性能的提升并不顯著，一方面Search-snippets 語料的類別數較少，另一方面與Bio-medical 相比，Search-snippets 中句子長度較長（平均長度17.88），使得噪聲類裁剪的作用類似于在長文本分類中應用的效果。

圖2 噪聲類裁剪對CCND-LRC 分類性能的影響Fig.2 Influence of noise class clipping on classification performance of CCND-LRC

圖3 噪聲類裁剪對CND-LRC 分類性能的影響Fig.3 Influence of noise class clipping on classification performance of CND-LRC

3.1.3 KNN 參數的敏感性分析

在復旦語料下，測試使用KNN 對各類別選擇不同規模類鄰域字典時，CCND-LRC 和CND-LRC的分類性能及算法運算效率，實驗結果如圖4 所示。參數K為每個類鄰域字典中包含的訓練樣本個數。從圖4（a）可以看出，CCND-LRC 和CND-LRC的分類Micro-F1 值都隨K的增大而增大，當K達到10 時變化趨于平穩，并且兩個算法的Micro-F1 值很接近。圖4（b）給出兩個算法的分類Macro-F1 隨K的變化趨勢，從中可以看出，當K=10 時兩個算法都獲得最優Macro-F1，相比之下，CND-LRC 具有更高的Macro-F1 值。圖4（c）表明兩個算法的運行時間都隨K的增大而上升，并且在整體上CND-LRC比CCND-LRC 具有更高的效率，這與上文中對CND-LRC 和CCND-LRC 算法計算復雜度的分析相一致。

圖4 CCND-LRC 和CND-LRC 算法的分類F1-值和運行時間隨KNN 參數K 的變化趨勢Fig.4 F1-scores and CPU times of CCND-LRC and CND-LRC with varying KNN parameter K

3.2 文本分類實驗

本節在4 個語料庫上進行實驗，將CND-LRC、CCND-LRC 與 MSRC、PCA-SVM、SRC、E-SRC、KNN-SRC 算法的分類精度和算法效率進行對比，各算法的分類F1-值和運算時間如表2 所示。SRC 算法使用所有訓練樣本作為對測試樣本稀疏表示的字典，其他算法都從訓練樣本中選擇部分樣本或采用降維方法形成新的縮減的字典，其中E-SRC 算法按類別選擇不同數目的訓練樣本作為字典原子。表2中各個算法的F1-值后括號內的數字表示進行字典選擇/學習后新字典中原子的個數，在該字典規模下各個算法均取得了最優的分類性能。

表2 不同算法對4 個語料的分類性能比較Table 2 Performance comparison of different algorithms for four corporas

分析Marco-F1 和Micor-F1 指標可知：對長文本語料語料，基于噪聲類裁剪的CCND-LRC和CND-LRC算法在長文本語料的分類精度上都顯著優于其他算法，Micro-F1 值優于其他算法3%～11%，Macro-F1 值超過其他算法3%～12%；對短文Search-snippets 語料，CCNDLRC 和CND-LRC 算法的分類精度也明顯高于其他算法；然而對Bio-medical 語料，CCND-LRC 取得最優的Micro-F1 值，但其Macro-F1 值低于KNN-SRC。兩個短文本語料進行對比，其中Search-snippets 的平均文本長度為17.88，包含8 個類別，Bio-medical的平均文本長度為12.88，包含20 個類，說明本文的CCND-LRC 和CND-LRC 算法對文本長度較長、類別數較少的短文本語料具有較好的分類性能。此外，復旦語料是一個不平衡文本數據集，其20 個類別中有11 個類別的樣本數在100 以下，其他類別的樣本數則達到1 000 及以上。從對復旦語料的分類Macro-F1 值可以看出，CND-LRC明顯優于其他算法，說明對不平衡語料的分類，CND-LRC更具魯棒性。

分析算法運行效率可知：在長文本分類中，由于CCND-LRC 和CND-LRC 僅需使用由少量訓練樣本組成的字典構建線性回歸分類模型，因此其計算效率明顯高于使用全訓練樣本的SRC 和采用降維的MSRC 和PCA-SVM 算法，與基于“樣本選擇”的KNN-SRC 和E-SRC 算法相比，當字典原子個數相近時，CCND-LRC 和CND-LRC 的計算效率更高；在短文本分類中，CCND-LRC 和CND-LRC 的計算效率都高于SRC、KNN-SRC 和E-SRC，與MSRC 和PCA-SVM相比，由于CCND-LRC 和CND-LRC 的字典規模略高，使得本文的兩個算法與MSRC 和PCA-SVM 具有相近的計算效率。CCND-LRC 和CND-LRC 相比，由于CCND-LRC 采用了協作表示的機制，具有更高的計算復雜度，但由于類別數不多，因此其計算效率略低于CND-LRC。綜上所述，CND-LRC 適用于語料和類別數量較多且類別不平衡的情況，在較好的運行效率下也保證了較優的精度，而CCND-LRC在短語料中有更好的分類性能。

4 結束語

針對文本分類問題，本文采用KNN 的思想，通過相似度計算在每個類別中選擇與測試樣本相近的部分訓練樣本形成縮減的類鄰域字典，并基于類鄰域字典提出兩種線性回歸分類算法，同時提出一種類相關度測量方法，通過計算測試樣本與類別的相關度對噪聲類進行裁剪。對長文本的分類實驗結果表明，本文算法具有較高的分類精度和計算效率，在類別數較多的情況下，噪聲類裁剪的策略能有效提高算法性能，與同類算法相比，分類精度可提高約3%～10%。后續將針對短文本分類任務，進一步提高本文算法的分類性能。