基于最近鄰子空間搜索的兩類文本分類方法＊

李玉鑑，王 影，冷強奎

（北京工業大學計算機學院，北京100124）

1 引言

文本分類是指用計算機按照一定的標準對文本集自動賦予類別標記，它在信息檢索、文本挖掘和輿情分析等領域中具有重要應用，其中涉及文本表示、特征選擇、分類模型和評價方法等關鍵技術［1，2］。

目前，比較常用的文本分類器有樸素貝葉斯（Naive Bayes）、支持向量機SVM（Support Vector Machine）、K 最 近 鄰KNN（K Nearest Neighbor）［3］等。最近鄰方法是KNN 的一個特例，基本思想是在訓練集中找到測試樣本的最近鄰樣本，然后根據此最近鄰樣本的類別作出決策。但是，最近鄰方法只根據距離最近原則進行分類，分類精度易受噪聲數據的干擾。而且，如果訓練集文檔數量較大，對新樣本分類就需要較大的計算開銷，從而導致分類過程較慢。本文利用最近鄰子空間搜索［4］的思想可以在一定程度上克服最近鄰方法的上述缺點。

目前，已存在一些利用子空間思想表示文本特征信息的算法，例如基于子空間聚類［5］以及隨機子空間［6］的文本分類方法。基于子空間聚類的文本分類方法中，每個特征維度根據其對區分不同類別文本的貢獻程度的大小被賦予不同的權重，基于這些維度權重，能夠在一個加權的高維空間中完成文本的聚類過程。隨機子空間方法將特征空間劃分為若干個維度較低的特征子空間，然后在每個維度較低的特征子空間上進行分類，最后合并結果。這些方法都能夠有效地降低特征空間的維度，充分證明了以子空間表示文本特征信息的優越性。

最近鄰子空間搜索是一種新近提出的模式分析方法，已在模式識別、機器視覺和統計學習［7，8］等領域獲得了成功應用。它的基本思想是選擇一組向量構成的子空間來表示同類或相關數據的重要信息，再把這組向量映射成高維空間中的點，最后再通過高維空間中的最近鄰方法解決所涉及的問題。子空間在計算機視覺和模式識別中是一種常用的信息表示方法。例如，在計算機視覺領域中，子空間常常用來表示不同光照、視角和空間變化下的物體特征。當一幅（或多幅）給定的查詢圖像被表示為高維空間中的點（或子空間）時，就可能需要從一個子空間數據庫中搜索與其最近的子空間。而解決相關問題的一種有效方法就是最近鄰子空間搜索。

本文的目的是將最近鄰子空間搜索的思想應用于文本分類領域，大體思路如下：首先用向量表示文本，用子空間表示文本的類別特征信息，然后把類別子空間和查詢向量映射為高維空間中的點，最后利用最近鄰算法完成分類過程。最近鄰子空間搜索的本質是在高維空間中用最近鄰點搜索計算與查詢向量距離最近的類別子空間。由于實際上只需要計算高維空間中的向量距離，因此能夠簡化分類過程，提高分類效率。

本文組織結構如下：第2節簡要介紹最近鄰子空間搜索方法；第3節為文本的子空間表示；第4節統計在標準數據集上的實驗結果，最后是結束語。

2 最近鄰子空間搜索簡介

本文把子空間定義為一個相互正交的向量集合。包含k個n維向量的子空間S可以用一個n×k維的矩陣表示。給定一個n維向量構成的子空間集合｛S1，S2，…，Sm｝和一個查詢向量q∈Rn，相應的最近鄰子空間問題是計算與q距離最近的子空間S＊，即：

其中，dist（q，Si）表示q與Si之間的歐氏距離。

設S是一個n×k維矩陣表示的子空間。顯然，直接計算dist（q，S）比較困難。為了簡化最近鄰子空間的計算，可以先定義兩個函數變換，即u＝f（S）和v＝g（q），分別將S和查詢點q映射到同一高維空間內的點u、v∈，其中n′表示高維空間的維度。然后，在空間內搜索點v的最近鄰點，并作出決策。不過這兩個函數變換必須保證u和v的距離‖u－v‖ 與原空間Rn中查詢點q與子空間Si的距離dist（q，Si）保持同步單調性，即滿足下式：

其中，μ、ω為某一特定值的常數，使得映射前后的兩個距離呈線性關系。最近鄰子空間搜索的映射模型如圖1所示。其中，圖1a表示在原空間中的查詢點和各個子空間，圖1b表示經過映射后的點。

Figure 1 Mapping model of nearest subspace search圖1 最近鄰子空間搜索的映射模型

在公式（1）成立的情況下，最近鄰子空間的搜索問題就可以轉化為高維空間中的最近鄰搜索問題。

為了方便地描述整個映射過程，首先為任意n×n的對稱矩陣M＝（mij）定義一個映射h如下：

顯然，h的作用是把矩陣M映射為一個n′＝n（n＋1）/2維的列向量。這個列向量由矩陣M的上三角部分按行連接構成，且對角線上的元素乘以常數因子

設I為單位矩陣。如果令那么前面提到的f和g可以定義如下：

其中，

公式（2）～公式（6）的證明可參見Basri R 等人［4］的論文。根據這些公式還可以確定公式（1）中的μ和ω如下：

利用式（2）和式（3），就能夠將Rn中的子空間S和查詢向量q映射為空間中點u和v。因此，只需在空間中對點v進行最近鄰搜索，就可以實現Rn中的最近鄰子空間搜索。

3 文本的子空間表示

為了構建文本的子空間，首先需要對文本進行特征向量表示，然后由得到的特征向量構建不同類別文本的子空間。其中，為將文本表示為特征向量，需要經過特征提取和特征項賦權兩個步驟。下面逐一介紹本文中采用的特征提取、特征項賦權以及子空間構建方法。

3.1 特征提取

特征提取即按照一定的約束條件，從詞項集合中選取詞項子集的過程。選擇的約束條件不同，特征提取方法也不同。常用的特征提取方法有基于文檔頻率、基于CHI統計等。本文中采用CHI統計完成文本的特征提取過程。

CHI方法假設特征t與文本類別ci之間的非獨立關系類似于具有一維自由度的χ2分布，t對于ci的CHI值由下式計算：

其中，N表示訓練語料中的文檔總數，ci為某一特定類別，t表示特定的詞項，A表示屬于ci類且包含t的文檔頻數，B表示不屬于ci類但是包含t的文檔頻數，C表示屬于ci類但是不包含t的文檔頻數，D是既不屬于ci也不包含t的文檔頻數。

CHI方法不僅考慮到了特征項與類別的正相關對特征項重要程度的影響，而且也考慮了特征項與類別的反相關對特征項重要性的影響。如果特征項t和類別ci正相關，說明含有特征項t的文檔屬于ci的概率要大一些；如果特征項t和類別ci反相關，就說明含有特征項t的文檔不屬于ci的概率要大一些。

3.2 特征項賦權

對文本進行分類之前，需要將文本表示為計算機能夠處理的形式。向量空間模型是使用較多且效果較好的表示方法之一［9］，在該模型中，文檔空間被看作是由一組正交向量張成的向量空間。如果選擇了n個特征項tk，且文本d關于特征項tk的權值為ωk，那么文本d可以表示成向量d＝（ω1，ω2，…，ωn）。

本文采用詞頻關頻積tf·rf（Product of Term Frequency and Relevance Frequency）的賦權值方法，其中tf是詞頻，rf是相關頻率［10］。對于詞項tk，令文本d關于tk的權值為ωk，產生文本d的向量表示d＝（ω1，ω2，…，ωn）。根據tf·rf計算權值ωk的公式描述如下：

ωk＝tfk＊rfk

其 中，tfk表示詞項tk在文檔d中的頻率，rfk的計算公式如下：

其中，ak表示包含詞項tk的正類文本數，ck表示包含詞項tk的負類文本數。

3.3 子空間構建

通過對文本特征提取和特征項賦權的過程，我們可以得到每個文本的向量表示。在此基礎上，為完成最近鄰子空間搜索過程，我們需要構建代表性強、區分度大的子空間，它能夠直接決定分類效果的優劣。本文中采用奇異值分解來提取兩類樣本的子空間信息。奇異值分解是一種有效的矩陣特征提取方法，矩陣的奇異值反映了矩陣向量間的內在代數本質，具備良好的數值穩定性和幾何不變性，它在語音識別、圖像處理、控制論等眾多領域有著重要應用［11，12］。

設M為n×m非零矩陣，如果矩陣的秩r（M）＝r≤min（n，m），那么關于M存在下面的奇異值分解：

其中，Un×n、Vm×m是 正 交 矩 陣，Dn×m＝（Dr，O）（n≤m）或Dn×m＝（Dr，O）T（n≥m），O為零矩陣，Dr＝diag（σ1，σ2，…，σr）。σi稱為M的奇異值，在矩陣Dr中按從大到小降序排列。事實上，i＝1，2，…，r），且λi是MTM和MMT的非零特征值，λ1≥λ2≥… ≥λr＞0。

如果選取最大的k個奇異值，可以得到M的近似奇異值分解Mk：

根據Eckart－Young定理，在所有秩不超過r的矩陣中，Mk與M之差的Frobenius范數最小。因此，當k越接近于r，則Mk越接近于M。

在文本分類時，如果M是某類文本向量構成的矩陣，那么選擇合適的k對其進行近似奇異值分解（本文的所有實驗均取k＝22 完成），相應的矩陣Un×k就是該類文本的子空間，其中n為文本特征項的個數，也就是特征維數。對于兩類文本分類問題，分別構造正類和負類文本的兩個子空間，通過計算待分類文本的查詢向量與它們之間的最近距離，實際上只需計算它在高維空間中的映射向量與兩個子空間的映射向量之間的歐氏距離，就可以完成分類過程。雖然多類問題在理論上可以類似處理，但是本文只考慮兩類問題，因為用公式（7）計算相關頻率只對兩類問題效果較好，而不能直接用于多類問題。

4 實驗

本文 采 用Reuters－21578 數 據 集［13］中 文 本 數目 最 多 的 前10 類 文 本，包 括acq、corn、crude、earn、grain、interest、money－fx、ship、trade、wheat。實驗中共使用68 274篇文本，其中65 740篇作為訓練集，其余的2 534篇作為測試集。

在每次分類過程中，均指定某一類樣本作為正類樣本，將其余的9類樣本作為負類樣本，共完成了10組實驗。數據集描述及經過特征選取后特征維數如表1所示。

Table 1 Descriptions of data sets used in the experiments表1 實驗中數據集描述

4.1 性能評價

分類器的性能主要采用正確率（Accuracy）、準確率（Precision）、召回率（Recall rate）和F1 值作為評價指標。正確率是指分類器正確分類的樣本數與總樣本數之比。準確率（查準率）是指分類器正確分類的正樣本數與分類器分為正類的總樣本數之比。召回率（查全率）是指分類器正確分類的正樣本數與實際正樣本數之比。F1值是準確率與召回率之間的綜合指標，定義如下：

為了分析基于子空間映射的文本分類方法的可行性以及有效性，我們將該方法與基于傳統的最近鄰搜索方法進行了對比實驗。

4.2 實驗結果

本文利用正確率、準確率、召回率和F1 值作為評價指標，并記錄實驗中整個文本分類過程耗費時間。在Reuters數據集上對最近鄰子空間搜索與最近鄰搜索進行文本分類獲得的比較實驗結果如表2所示。

從表2可以看出，在選定不同的類作為正類的情況下，用最近鄰子空間搜索進行文本分類的三項指標普遍優于最近鄰搜索。當ship作為正類時，因為數據的不平衡性，最近鄰搜索將所有的樣本都分為負類，因此準確率無法計算，召回率為0，導致F1值無法計算。所以，在計算最近鄰搜索的各個評價指標的平均值時，不考慮該組數據。從表2中可以看出，無論數據樣本的平衡與否，最近鄰子空間搜索的平均正確率為93.4%，平均召回率為84.1%，以及平均F1值為0.588 8，充分證明了它比最近鄰搜索在分類總體性能上具有明顯優勢。

此外，表2還記錄了用最近鄰子空間搜索進行文本分類所需的總時間，包括讀數據、映射和分類等過程，平均耗時1 603s。由于最近鄰搜索耗時較長，最短的也需要53 700s，所以在此未對相應的時間進行詳細記錄。因此，最近鄰子空間搜索不僅在總體上能夠獲得更好的分類性能，還可以有效地減少所需的計算時間。

5 結束語

本文中將最近鄰子空間搜索應用于文本分類問題，與最近鄰搜索相比，既能獲得整體分類性能上的提高，又能有效地減少整個分類過程所需的計算時間。而且，最近鄰子空間搜索還能夠在一定程度上避免分類過程中對單個文本類別的依賴，通過利用每類文本的子空間表示其類別特征信息，提高對噪聲樣本的抗干擾能力。

Table 2 Comparison of nearest neighbor search and nearest subspace search on accuracy，precision，recall rate and F1value表2 最近鄰搜索和最近鄰子空間搜索在分類正確率、召回率和F1值上的對比實驗

［1］ Debasena C L，Hemalatha M.Automatic text categorization and summarization using rule reduction［C］∥Proc of IEEE Conference Advances in Engineering，Science and Management，2012：594－598.

［2］ Cai Yue－hong，Zhu Qian，Cheng Xian－yi.Semi－supervised short text categorization based on random subspace［C］∥Proc of the 3rd International Conference on Computer Science and Information Technology，2010：470－473.

［3］ Yang Y，Liu X.A re－examination of text categorization methods［C］∥Proc of the 22nd Annual International ACMSIGIR Conference on Research and Development in Information Retrieval，1999：42－49.

［4］ Basri R，Hassner T，Zelnik－Manor L.Approximate nearest subspace search with applications to pattern recognition［C］∥Proc of IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2007：1－8.

［5］ Ahmed M S，Khan L.SISC：A text classification approach using semi supervised subspace clustering［C］∥Proc of IEEE International Conference on Data Mining Workshops，2009：1－6.

［6］ Mehrdad J G，Mhamed S K，Robert P W.Random subspace method in text categorization［C］∥Proc of the 20th IEEE International Conference on Pattern Recognition，2010：2049－2052.

［7］ Basri R，Hassner T，Zelnik－Manor L.A general framework for approximate nearest subspace search［C］∥Proc of the 12th IEEE International Conference on Computer Vision Workshops，2009：109－116.

［8］ Wright J，Yang A，Granesh A，et al.Robust face recognition via sparse representation ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2009，31（2）：210－227.

［9］ Salton G.Introduction to modern information retrieval［M］.New York：McGraw Hill Book Company，1983.

［10］ Man L，Chew L T，Jian S，et al.Supervised and traditional term weighting methods for automatic categorization［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2009，31（4）：721－735.

［11］ Berry M W，Dumais S T.Using linear algebra for intelligent information retrieval［J］.SIAM Review，1995，37（4），573－595.

［12］ Liu Gui－long，Wang Hui－ling，Song Rou.Application of matrix singular value decomposition（SVD）to the research of text categorization on style［J］.Computer Engineering，2002，28（12）：17－19.（in Chinese）

［13］ Bache K，Lichman M.UCI machine learning repository［EB/OL］.［2013－4－20］.http：//archive.ics.uci.edu/ml.

附中文參考文獻：

［12］ 劉貴龍，王慧玲，宋柔.矩陣的奇異值分解在文本分類研究中的應用［J］.計算機工程，2002，28（12）：17－19.