基于哈希表的動態(tài)向量降維方法的研究及應(yīng)用

王 偉，許云峰，高 凱

（河北科技大學(xué)信息科學(xué)與工程學(xué)院，河北石家莊 050018）

文檔信息的特征表示方式有多種，常用的有布爾邏輯模型、向量空間模型、概率模型以及混合模型等［1］。其中向量空間模型VSM是應(yīng)用較多且效果較好的方法［2］。向量空間模型表示方法的主要不足是文檔特征向量具有驚人的高維次，因此在進行向量計算之前還必須對文檔特征向量進行降維處理。文獻［3］和文獻［4］認為高維數(shù)據(jù)中通常含有許多冗余信息，其中起到實質(zhì)作用的維數(shù)要遠遠小于原始的數(shù)據(jù)維數(shù)，所以高維向量的處理可以歸結(jié)為通過相關(guān)的降維方法減少一些不太相關(guān)的維次數(shù)據(jù)，然后用低維向量的處理辦法進行處理。文獻［5］—文獻［8］介紹了MDS，Isomap，LLE等3種高維數(shù)據(jù)的降維方法。文獻［1］介紹了一種稀疏的空間向量表示方法。文獻［9］提出了規(guī)則族之間相似度的構(gòu)建準(zhǔn)則。文獻［10］介紹的特征臉方法大大降低了原始空間的維數(shù)。

在研究中發(fā)現(xiàn)，雖然文檔特征向量空間的維次巨大，但具體到單個文檔，絕大多數(shù)向量元素都為零，這就決定了單個文檔的特征向量是一個稀疏向量。筆者在此提出并實現(xiàn)了一種基于哈希表的動態(tài)向量降維方法，用哈希表作為文檔特征向量的存儲數(shù)據(jù)結(jié)構(gòu)，只將權(quán)重不為零的特征向量詞條加入哈希表。實驗證明這種向量表示方式大大減少了內(nèi)存占用量，有效降低文檔特征向量的維次，顯著提高了文檔特征向量相關(guān)算法的性能。

1 基于哈希表的動態(tài)向量降維算法

該算法利用了哈希表的鍵值和表項唯一對應(yīng)的特性，將哈希表作為默認的向量模板，向量空間中每一維次在哈希表中都唯一對應(yīng)一個表項，并且各個維次排列的先后順序由哈希表的鍵值大小決定。

1.1 基于向量模板的向量空間模型算法

在傳統(tǒng)的基于向量模板的向量空間模型算法中，首先利用分詞技術(shù)對每篇文檔進行分詞，然后再用特征選擇算法，去除掉信息含量少的詞項，這一步驟相當(dāng)于對文檔向量空間做降維處理。其次，按照特征選擇算法賦予每個詞項的分值或者稱為詞項的權(quán)重大小，對保留下來的文檔特征詞項降序排序，根據(jù)用戶設(shè)定的最大向量空間維數(shù)n，截取已排序的文檔特征詞數(shù)組的前n項作為文檔向量模板。在這一步，截取的向量空間維數(shù)n的大小很關(guān)鍵，n的取值太大則文檔向量的維數(shù)就會很大；n的取值太小則會導(dǎo)致許多含有豐富信息量的特征詞丟失，從而降低文檔向量對文檔的標(biāo)識性能。確定了文檔向量模板就同時確定了文檔向量空間的維數(shù)、各維次對應(yīng)的特征詞項，以及各維次排列的先后順序。接下來就是參照文檔向量模板實現(xiàn)各文檔的向量化表示。但用這種方法生成的文檔向量維數(shù)都是相等而且是稀疏的向量，當(dāng)文檔中含有向量模板里不存在的特征詞時，盡管這個特征詞含有豐富的信息也會被忽略掉。人為規(guī)定向量空間的最大維數(shù)，相當(dāng)于對文檔向量空間又進行了一次強制的降維。

1.2 算法描述

筆者提出的基于哈希表的動態(tài)向量降維算法中，通過在哈希表中只存儲權(quán)重不為零的特征詞，來實現(xiàn)稀疏向量的動態(tài)壓縮存儲。算法主要思想和步驟是：1）在確定了訓(xùn)練文檔集后，利用分詞技術(shù)對每篇文檔進行分詞，然后再用特征選擇算法去除掉信息含量少的詞項，在這一步實現(xiàn)了對文檔向量空間的第1次降維處理；2）哈希表鍵值和表項是唯一對應(yīng)的，但是這個特性必須在特定前提條件下才能實現(xiàn)，可以利用哈希表這一特性，將其視為一個無限維次的向量空間模型，就文檔的特征詞而言，在這個空間中，每一個特征詞都有一個唯一對應(yīng)的維次，并且各維次的先后順序都由特征詞的哈希值的排列順序決定；3）將每一個文檔的特征詞存儲在一個哈希表里，每一個文檔都唯一對應(yīng)一個哈希表。在這一步還采用了一個策略，即在哈希表里只存儲權(quán)重不為零的特征詞項。對于稀疏的文檔向量，當(dāng)其存儲為哈希表形式時，就自動過濾掉權(quán)值為零的特征詞，實現(xiàn)了對稀疏文檔向量的壓縮存儲，從而實現(xiàn)了對文檔特征詞向量的第2次降維。至此就完成了基于哈希表的文檔向量空間模型的構(gòu)建過程。在哈希算法性能良好和計算機硬件性能允許的前提下，可以認為基于哈希表的向量空間維數(shù)是無限的，無論有多少特征詞都能在這個空間里找到所對應(yīng)的維次，而不用再人為限定向量空間的最大維數(shù)，從而避免了將信息含量大的特征詞丟失，并且這種方法也省略了構(gòu)建向量模板的過程，直接由特征詞生成文檔向量，節(jié)省了計算機資源，提高了算法性能。值得強調(diào)的一點是，要想有效發(fā)揮基于哈希表的動態(tài)向量降維算法的作用，就必須保證特征詞選擇算法能夠有效地選擇出富含信息的特征詞，并且保證特征詞的數(shù)量遠小于文檔分詞后的詞項總數(shù)。圖1顯示了將文檔向量化的過程。

圖1 文檔的向量化表示過程Fig.1 Process of the document says as vector

2 算法性能實驗

2.1 實驗設(shè)計

在此使用相同的語料庫和分類器，分別應(yīng)用不同的文檔向量表示方法，比較分類器對相同語料庫的總處理時間和分類速率的差別，來觀察2種向量表示方法的性能差異。這里采用靈玖中科軟件有限公司提供的文本分類語料庫作為測試語料，該語料庫共包括10個類別2 816篇文檔。筆者提到的文檔分詞和文檔特征詞選擇任務(wù)由本課題組提供的主題詞抽取模塊完成，該模塊集分詞和主題詞提取功能于一身，并且該模塊的主題詞提取算法是一種高性能的特征選擇和降維算法，能夠滿足本文實驗的要求。另一方面，主題詞是一種性能良好的文檔特征量，對文檔有非常好的標(biāo)引性和區(qū)分性，一般10個主題詞就能很好地標(biāo)引和區(qū)分不同文檔了?？紤]到主題詞提取模塊的性能，提取主題詞個數(shù)越多，模塊的處理速度就越慢，所以將提取的主題詞的最多個數(shù)設(shè)定為30個。

筆者的基于文檔向量模板的向量表示方法和基于哈希表的動態(tài)向量降維算法都在課題組提供的中心向量分類器中實現(xiàn)，采用了2種模塊組合對比實驗：1）主題詞提取模塊＋基于文檔向量模板的向量表示方法＋中心向量分類器；2）主題詞提取模塊＋基于哈希表的動態(tài)向量降維算法＋中心向量分類器。

為了提高實驗效率，預(yù)先提取了語料庫每篇文檔的主題詞，并且保存在一個主題文件里。實驗時只需從主題文件里讀取每篇文檔的主題詞串然后進行分類處理就行了。通過多次實驗，分別在不同的訓(xùn)練集規(guī)模、測試集規(guī)模和向量維數(shù)下對2種算法進行了性能測試，分別記錄“總耗時”（即分類器對測試文檔集內(nèi)所有文檔進行分類所耗費的總時間，單位為s）、“分類速率”（即分類器在1s內(nèi)能夠分類的文檔篇數(shù)，單位為“篇／s”）、“F1評價值”（是對分類器總體分類正確率和總體查全率的綜合評價，體現(xiàn)了分類器的綜合性能）3項性能指標(biāo)。需要說明的是，實驗中分類器沒有考慮兼類的情況，每篇測試文檔只能歸屬唯一的類別。訓(xùn)練集和測試集都是按照不同的規(guī)模比例從同一個語料庫中隨機選擇的，2個文檔集中的文檔沒有重復(fù)，分類測試采用開放性測試。

2.2 數(shù)據(jù)分析

主要實驗數(shù)據(jù)如表1所示。

表1 采用基于文檔向量模板的向量表示方法的測試結(jié)果Tab.1 Testing results of the vector representation method based on the document vector template

表1一共進行了3組實驗，分別對應(yīng)于3種測試集規(guī)模：702篇、936篇和1 406篇；每組實驗又包括3次實驗，分別對應(yīng)于3種向量維數(shù)：1 000維、3 000維和6 000維。由表1中的數(shù)據(jù)可以發(fā)現(xiàn)，隨著向量維數(shù)的增大，分類的總耗時增加，分類的速率降低，這說明隨著維數(shù)的增大，文檔向量所包含的數(shù)據(jù)項數(shù)增加，與向量相關(guān)的計算量也增加了。同時還發(fā)現(xiàn)隨著維數(shù)的增大，分類器的F1值增大，這說明隨著維數(shù)的增大，人為舍棄的關(guān)鍵詞的數(shù)量減少，同時每個文檔向量包含的信息量增加，進而提高了分類的準(zhǔn)確率和查全率，提高了分類器的性能。通過3組實驗數(shù)據(jù)的對照比較可以看出，隨著測試集規(guī)模的增大，分類總耗時相應(yīng)增加，分類速率降低，這說明測試文檔集規(guī)模的增大也會增加分類器的計算量。同時也發(fā)現(xiàn)隨著測試文檔集規(guī)模的增大，分類器F1值沒有顯著的變化，這說明分類器的性能受文檔向量維數(shù)變化的影響最大。

表2是采用基于哈希表的動態(tài)向量降維算法的測試結(jié)果。一共進行了3次實驗，分別對應(yīng)于3種測試集規(guī)模，由于是采用動態(tài)降維算法，向量維數(shù)隨著不同的文檔而隨時變化，不便于采集比較，所以在這組實驗里不考慮向量維數(shù)。通過分析表2的實驗數(shù)據(jù)，可知隨著測試集規(guī)模的增大，分類總耗時有小幅度的增加，分類速率有小幅度的降低，這說明隨著測試集規(guī)模的增大，與文檔向量相關(guān)的計算量有小幅度的增加。同時也看到，隨著測試集規(guī)模的增大，分類器的總體F1值沒有顯著的變化，這說明分類器的總體F1值與測試集規(guī)模的變化沒有明顯的關(guān)聯(lián)，同時還說明該算法顯著減小了向量維數(shù)變化對分類器性能的影響。

表2 采用基于哈希表的動態(tài)向量降維算法的測試結(jié)果Tab.2 Testing results of the vector dimension reduction algorithm based on hash table dynamic

圖2是2種向量表示算法的性能比較，其中A算法代表基于哈希表的動態(tài)向量降維算法，B算法代表基于文檔向量模板的向量表示方法，橫坐標(biāo)代表測試文檔集的規(guī)模，縱坐標(biāo)代表使用2種向量表示方法的文本分類器對同樣的測試文檔集進行分類所耗費的時間，也代表了使用2種向量表示方法的文本分類器對同樣的測試文檔集進行分類時的分類速率，其衡量指標(biāo)是每秒分類的文檔數(shù)。在此記錄了3組數(shù)據(jù)，分別對應(yīng)于3種測試文檔集規(guī)模：702篇、936篇和1 406篇，通過2種算法實驗數(shù)據(jù)的比較可以看出，基于哈希表的動態(tài)向量降維算法的性能顯著優(yōu)于基于文檔向量模板的向量表示方法的性能。

表3分別記錄了2種算法多次實驗數(shù)據(jù)的平均值，分別代表了2種算法的平均性能。其中“↑”表示第2種算法與第1種算法相比較，性能指標(biāo)提高的百分比；“↓”表示第2種算法與第1種算法相比較，性能指標(biāo)降低的百分比。通過對2種算法平均實驗數(shù)據(jù)的對比計算，得到了2種算法性能量化的比較結(jié)果。從表3最后一行的性能比較數(shù)據(jù)可以看出，基于哈希表的動態(tài)向量降維算法的性能顯著優(yōu)于基于文檔向量模板的向量表示方法的性能，支持了圖2顯示的性能比較結(jié)論。

圖2 2種向量表示算法的性能比較圖Fig.2 Comparison of two vector says algorithm

表3 2種算法的量化性能比較Tab.3 Two algorithm′s quantitative performance comparison

3 結(jié) 語

在對向量空間模型的特性和哈希表的特性進行深入研究后，在綜合考慮了基于文檔向量模板的向量表示方法優(yōu)缺點的基礎(chǔ)上，提出并實現(xiàn)了一種基于哈希表的動態(tài)向量降維算法，并成功地將該算法應(yīng)用到了中心向量分類器里。實驗證明該算法有效降低了向量空間模型的維數(shù)，并且顯著提高了基于向量空間模型分類算法的性能。

［1］ 姚清耘，劉功申，李 翔.基于向量空間模型的文本聚類算法［J］.計算機工程（Computer Engineering），2008，34（18）：40-41，44.

［2］ HAMADI R，BENATALLAH B.A petri Net-based model for web service composition［A］Proc of the 14th Australasian Database Conference on Research and Practice in Information Technology［C］.Adelaide：［s.n.］，2003.191-200.

［3］ SAMARASENA B，NEIL D，RAY J，et al.Dimensionality reduction of face Images for cender classification［EB／OL］.http：／／homepages.Feis，herts.ac.Uk／～nngroup／pubs／papers／Buchala2IS04.pdf，2006-03-20.

［4］ LESPINATS S，GIRON A，F(xiàn)ERTIL B.Visualization and exploration of high-dimensional data using a“force directed placement”method：Application to the analysis of genomic signatures［EB／OL］.http：／／asmda2005.enst-bretagne.Fr／IMG／pdf／proceedings／230.pdf，2006-03-24.

［5］ TENENBAUM J B，VIN de Silva，JOHN C L.A global geometric framework for nonlinear dimensionality reduction［J］.Science，2000，290：2 319-2 323.

［6］ VIN de Silva，JOSHUA B T.Global versus local methods in non-linear dimensionality reduction［EB／OL］.http：／／web.mit.edu／cocosci／Papers／nips02-localglobal-in-press.pdf，2006-03-24.

［7］ ROWEIS S，SAUL L.Nonlinear dimensionality reduction by locally linear embedding［J］.Science，2000，290：2 323-2 326.

［8］ LAWRENCE K Saul，SAM T Roweis.An introduction to locally linear embedding［EB／OL］.http：／／www.pami.sjtu.edu.Cn／people／xzj／introducelle.htm，2006-03-24.

［9］ 李 萍，李法朝.基于決策樹的知識表示模型及其應(yīng)用［J］.河北科技大學(xué)學(xué)報（Journal of Hebei University of Science and Technology），2009，30（2）：87-91.

［10］ 李春明，李玉山，莊慶德，等.人臉識別技術(shù)的研究［J］.河北科技大學(xué)學(xué)報（Journal of Hebei University of Science and Technology），2003，24（3）：1-6.