李玉鑑，王 影，冷強(qiáng)奎

（北京工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，北京100124）

1 引言

文本分類是指用計(jì)算機(jī)按照一定的標(biāo)準(zhǔn)對(duì)文本集自動(dòng)賦予類別標(biāo)記，它在信息檢索、文本挖掘和輿情分析等領(lǐng)域中具有重要應(yīng)用，其中涉及文本表示、特征選擇、分類模型和評(píng)價(jià)方法等關(guān)鍵技術(shù)［1，2］。

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

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

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

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

本文組織結(jié)構(gòu)如下：第2節(jié)簡(jiǎn)要介紹最近鄰子空間搜索方法；第3節(jié)為文本的子空間表示；第4節(jié)統(tǒng)計(jì)在標(biāo)準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，最后是結(jié)束語(yǔ)。

2 最近鄰子空間搜索簡(jiǎn)介

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

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

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

其中，μ、ω為某一特定值的常數(shù)，使得映射前后的兩個(gè)距離呈線性關(guān)系。最近鄰子空間搜索的映射模型如圖1所示。其中，圖1a表示在原空間中的查詢點(diǎn)和各個(gè)子空間，圖1b表示經(jīng)過(guò)映射后的點(diǎn)。

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

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

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

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

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

其中，

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

利用式（2）和式（3），就能夠?qū)n中的子空間S和查詢向量q映射為空間中點(diǎn)u和v。因此，只需在空間中對(duì)點(diǎn)v進(jìn)行最近鄰搜索，就可以實(shí)現(xiàn)Rn中的最近鄰子空間搜索。

3 文本的子空間表示

為了構(gòu)建文本的子空間，首先需要對(duì)文本進(jìn)行特征向量表示，然后由得到的特征向量構(gòu)建不同類別文本的子空間。其中，為將文本表示為特征向量，需要經(jīng)過(guò)特征提取和特征項(xiàng)賦權(quán)兩個(gè)步驟。下面逐一介紹本文中采用的特征提取、特征項(xiàng)賦權(quán)以及子空間構(gòu)建方法。

3.1 特征提取

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

CHI方法假設(shè)特征t與文本類別ci之間的非獨(dú)立關(guān)系類似于具有一維自由度的χ2分布，t對(duì)于ci的CHI值由下式計(jì)算：

其中，N表示訓(xùn)練語(yǔ)料中的文檔總數(shù)，ci為某一特定類別，t表示特定的詞項(xiàng)，A表示屬于ci類且包含t的文檔頻數(shù)，B表示不屬于ci類但是包含t的文檔頻數(shù)，C表示屬于ci類但是不包含t的文檔頻數(shù)，D是既不屬于ci也不包含t的文檔頻數(shù)。

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

3.2 特征項(xiàng)賦權(quán)

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

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

ωk＝tfk＊rfk

其 中，tfk表示詞項(xiàng)tk在文檔d中的頻率，rfk的計(jì)算公式如下：

其中，ak表示包含詞項(xiàng)tk的正類文本數(shù)，ck表示包含詞項(xiàng)tk的負(fù)類文本數(shù)。

3.3 子空間構(gòu)建

通過(guò)對(duì)文本特征提取和特征項(xiàng)賦權(quán)的過(guò)程，我們可以得到每個(gè)文本的向量表示。在此基礎(chǔ)上，為完成最近鄰子空間搜索過(guò)程，我們需要構(gòu)建代表性強(qiáng)、區(qū)分度大的子空間，它能夠直接決定分類效果的優(yōu)劣。本文中采用奇異值分解來(lái)提取兩類樣本的子空間信息。奇異值分解是一種有效的矩陣特征提取方法，矩陣的奇異值反映了矩陣向量間的內(nèi)在代數(shù)本質(zhì)，具備良好的數(shù)值穩(wěn)定性和幾何不變性，它在語(yǔ)音識(shí)別、圖像處理、控制論等眾多領(lǐng)域有著重要應(yīng)用［11，12］。

設(shè)M為n×m非零矩陣，如果矩陣的秩r（M）＝r≤min（n，m），那么關(guān)于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中按從大到小降序排列。事實(shí)上，i＝1，2，…，r），且λi是MTM和MMT的非零特征值，λ1≥λ2≥… ≥λr＞0。

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

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

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

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

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

在每次分類過(guò)程中，均指定某一類樣本作為正類樣本，將其余的9類樣本作為負(fù)類樣本，共完成了10組實(shí)驗(yàn)。數(shù)據(jù)集描述及經(jīng)過(guò)特征選取后特征維數(shù)如表1所示。

Table 1 Descriptions of data sets used in the experiments表1 實(shí)驗(yàn)中數(shù)據(jù)集描述

4.1 性能評(píng)價(jià)

分類器的性能主要采用正確率（Accuracy）、準(zhǔn)確率（Precision）、召回率（Recall rate）和F1 值作為評(píng)價(jià)指標(biāo)。正確率是指分類器正確分類的樣本數(shù)與總樣本數(shù)之比。準(zhǔn)確率（查準(zhǔn)率）是指分類器正確分類的正樣本數(shù)與分類器分為正類的總樣本數(shù)之比。召回率（查全率）是指分類器正確分類的正樣本數(shù)與實(shí)際正樣本數(shù)之比。F1值是準(zhǔn)確率與召回率之間的綜合指標(biāo)，定義如下：

為了分析基于子空間映射的文本分類方法的可行性以及有效性，我們將該方法與基于傳統(tǒng)的最近鄰搜索方法進(jìn)行了對(duì)比實(shí)驗(yàn)。

4.2 實(shí)驗(yàn)結(jié)果

本文利用正確率、準(zhǔn)確率、召回率和F1 值作為評(píng)價(jià)指標(biāo)，并記錄實(shí)驗(yàn)中整個(gè)文本分類過(guò)程耗費(fèi)時(shí)間。在Reuters數(shù)據(jù)集上對(duì)最近鄰子空間搜索與最近鄰搜索進(jìn)行文本分類獲得的比較實(shí)驗(yàn)結(jié)果如表2所示。

從表2可以看出，在選定不同的類作為正類的情況下，用最近鄰子空間搜索進(jìn)行文本分類的三項(xiàng)指標(biāo)普遍優(yōu)于最近鄰搜索。當(dāng)ship作為正類時(shí)，因?yàn)閿?shù)據(jù)的不平衡性，最近鄰搜索將所有的樣本都分為負(fù)類，因此準(zhǔn)確率無(wú)法計(jì)算，召回率為0，導(dǎo)致F1值無(wú)法計(jì)算。所以，在計(jì)算最近鄰搜索的各個(gè)評(píng)價(jià)指標(biāo)的平均值時(shí)，不考慮該組數(shù)據(jù)。從表2中可以看出，無(wú)論數(shù)據(jù)樣本的平衡與否，最近鄰子空間搜索的平均正確率為93.4%，平均召回率為84.1%，以及平均F1值為0.588 8，充分證明了它比最近鄰搜索在分類總體性能上具有明顯優(yōu)勢(shì)。

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

5 結(jié)束語(yǔ)

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

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

［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－h(huán)ong，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.

附中文參考文獻(xiàn)：

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