張齊勛 劉宏志 劉詩祥 賈 堂 曹 健

1(北京大學軟件與微電子學院 北京 102600)2(北京大學信息科學技術學院 北京 100871)

?

基于行業(yè)專有詞典的TF-IDF特征選擇算法改進

張齊勛1,2劉宏志1劉詩祥1賈 堂1曹 健1,2

1(北京大學軟件與微電子學院 北京 102600)2(北京大學信息科學技術學院 北京 100871)

行業(yè)專有詞典是收錄特定行業(yè)專有用語的詞典，將行業(yè)專有詞典運用到基于TF-IDF的特征選取算法中可提高文本特征空間的完備性?；赥F-IDF的改進算法的核心目標是提取出低頻的關鍵詞，現(xiàn)有的基于統(tǒng)計特征的改進方法增加了原始算法的計算復雜度，降低了算法的效率。針對這一問題，在原始的TF-IDF特征選取算法上采用詞典映射的方法提取低頻關鍵詞來構建完備的特征空間。實驗結果表明，基于行業(yè)專有詞典的TF-IDF算法提取出的特征較未使用行業(yè)專有詞典特征選取算法提取出的特征在后續(xù)的二次聚類驗證實驗中能有效地提高聚類的查全率和查準率。

行業(yè)專有詞典 TF-IDF 特征空間 特征選擇算法

0 引 言

行業(yè)專有詞典是收錄某種特定行業(yè)專用術語的詞典。它可以使用結合統(tǒng)計方法的機械匹配算法對特定行業(yè)的文本庫進行分詞來登記生詞，從而構建出該行業(yè)專有的詞典。行業(yè)專用詞典通常運用于文本挖掘的預處理階段,從而獲取高質量的分詞結果。但實際上行業(yè)專用詞典還包含了大量對應行業(yè)中的重要且在文本中出現(xiàn)頻率較低的詞，這些詞都可以作為文章的關鍵詞以及特征向量出現(xiàn)，然而傳統(tǒng)的TF-IDF算法往往會忽略掉低頻詞匯。由此衍生了針對原始算法缺點的改進算法，例如Mingmin Xu等提出了一種基于IDF的改進算法，命名為信道分配信息，該方法通過原始數(shù)據(jù)的統(tǒng)計特征來識別核心詞[1]。羅欣等則基于TF改進原始算法，該算法以詞頻差異為基礎，用信息量來重新計算TF值[2]。這些改進的算法能夠找到低頻核心詞，提高文本特征空間的準確度，但同時也提高了算法的時間開銷。

本文根據(jù)數(shù)據(jù)自身的特點將行業(yè)專有詞典運用到原始的TF-IDF特性選擇的過程中，從而在提取出低頻關鍵詞的同時避免較大的時間復雜度，通過該算法獲取的特征空間結構穩(wěn)定，可滿足較高的準確性要求。

1 行業(yè)專有詞典的構建

1.1 基本詞典

網絡資源中廣泛使用的大都為基本詞典，基本詞典是指不包含行業(yè)專業(yè)用語的詞典,包含了實體詞詞典、停用詞詞典等，基本詞典里面的詞可以無差別地出現(xiàn)在任何行業(yè)的文本中，如圖1所示。

正是由于針對特定行業(yè)的詞典在網上難以直接獲取，而該詞典在后續(xù)的分詞以及特征選取中又尤為重要，所以需要提前構建出行業(yè)專有詞典。

圖1 基本詞典和行業(yè)詞典的關系

1.2 行業(yè)專有詞典的構建

行業(yè)專有詞典的構建分為數(shù)據(jù)采集、正文提取以及利用基本詞典和統(tǒng)計的方法構建，具體過程如下:

1) 數(shù)據(jù)采集

構建詞典的第一步是獲取特定的行業(yè)文本，通常的方法有：

(1) 利用網絡爬蟲設定關鍵詞定向獲取網頁文件；

(2) 使用網絡爬蟲獲取與行業(yè)相關的垂直新聞網站的網頁文件。

2) 正文提取

獲取網頁文件之后需對文件進行正文提取，即過濾網頁中的標簽、廣告、導航條等無關信息從而得到有用信息。圖2為原始的網頁DOM機構片段，圖3從DOM結構中提取的正文。

圖2 html DOM結構

圖3 DOM中的正文信息

3) 利用基本詞典和統(tǒng)計的方法構建行業(yè)詞典

(1) 統(tǒng)計的方法

中文詞是字和字之間穩(wěn)定的組合，可采用基于統(tǒng)計的方法計算相鄰字的字符串在文檔集合中出現(xiàn)的頻率，頻率越大表明該字符串構成一個詞的可信度越大，詞的可信度主要依賴于字與字相鄰出現(xiàn)的頻率，該頻率被稱之為互信息。

單純的依靠統(tǒng)計的方法來登記詞，時間空間開銷較大且效果不理想，會得到很多沒有意義的詞，工程中通常把這種方法和機械匹配法結合起來使用：使用機械匹配分詞，使用統(tǒng)計方法識別新詞。這樣利用了機械匹配快速準確以及統(tǒng)計方法可識別新詞的優(yōu)點。

(2) 生成行業(yè)詞典的步驟

首先，利用已有的基本詞典對提取的正文進行分詞，并記錄詞典中未登記的單字及其在文本中出現(xiàn)的上下文。

其次，將單字和其位置信息作為統(tǒng)計方法的輸入，進行新詞的查找計算。

最后，人工審核和標定新詞。

1.3 TD-IDF算法

TF-IDF算法是一種統(tǒng)計方法，用以評估一個詞對一個文檔集中的某一篇文本的重要程度。詞的重要性隨著它在文件中出現(xiàn)的頻率成正比增加，但同時會隨著它在文檔集中出現(xiàn)的頻率呈反比下降。

TF代表Term Frequency，它是特征詞出現(xiàn)在文章中的頻率[4]，其定義為：

(1)

其中f(w)是w在文本中出現(xiàn)的頻數(shù)，n是文本中實體詞總數(shù)。IDF代表Inverse Document Frequency，它是特征的逆文檔頻率，其定義為：

(2)

其中D是文本總數(shù)，d是包含詞w的文本的數(shù)量。通過上述兩個公式可知，TF反映的是w在文本中的重要程度，而IDF反映的是w在整個文檔集上的常見程度[5]。若一個詞的TF和IDF值都比較大則表明這個詞在整個文檔集合中不常見，但是在該文本中卻大量出現(xiàn)，即該詞為該文章的一個關鍵詞，需分配較大的權重。權重為：

TF-IDF(w)=TF(w)×IDF(w)

(3)

TF-IDF算法計算簡單，可以直接計算出特征的權重，面對數(shù)據(jù)量的增長，TF-IDF的算法復雜度是線性增長的。所以TF-IDF在精度要求不是非常嚴格的系統(tǒng)中是信息量算法的最好的替代者。

2 算法的改進

首先對一些現(xiàn)有的算法進行簡介，其后提出改進算法。

2.1 K-means算法

K-means是非常典型的基于劃分的聚類算法，它接收輸入數(shù)值k和數(shù)據(jù)集中k個初始中心數(shù)據(jù)對象，計算剩余數(shù)據(jù)與各中心點的距離，并將其劃分距離最近的中心點形成的簇中。重新計算有變化的簇的均值，并以該均值為新的中心點繼續(xù)迭代上述步驟，直到中心點不再變化[6]。

2.2 DBSCAN算法

DBSACN算法從任意一個未訪問的數(shù)據(jù)對象d開始，根據(jù)指定的掃描半徑E來掃描所有從d出發(fā)密度可達的數(shù)據(jù)對象。當掃描半徑內的對象數(shù)量達到指定的最小包含數(shù)據(jù)點數(shù)MinPts的時候，則標記這些點為一個簇，標記d為該簇的核心點，并標記其為已訪問。在簇內重復上述工作，如果一個簇內出現(xiàn)多個核心點，那么這些核心點的簇要合并為一個簇。如果掃描半徑內的對象數(shù)量達不到MinPts的時候，d則被標記為噪聲和已訪問。繼續(xù)迭代步驟，直到沒有點可以訪問[7]。

2.3 基于K-means和DBSCAN算法的二次聚類

DBSCAN相比K-Means算法無需指定簇的數(shù)目作為參數(shù)，且能識別噪聲[8]。本文的聚類采用DBSCAN算法作為一次聚類算法獲取粗糙集[9]來確定k和k個初始的中心點，其后在粗糙集上使用K-Means算法來提高聚類效果。參數(shù)E和MinPts的確定沒有規(guī)律可循[10]，本文采用一種啟發(fā)式方法來確定相關參數(shù)。二次聚類算法流程如下：

(1) 設有N個數(shù)據(jù)對象，計算出這N個數(shù)據(jù)對象之間的間距，取這些間距的平均值作為DESCAN算法的掃描半徑。

(2) 用(1)得到的掃描半徑來計算這N個數(shù)據(jù)對象周圍的數(shù)據(jù)點，并從大到小排列。

(3) 根據(jù)(2)的結果來選取K-Means算法的簇中心，若某個點在先前選定的簇中心所覆蓋的區(qū)域內，則忽略該點并繼續(xù)選擇，直到所有點都被標記為訪問。

(4) 根據(jù)(3)的結果作為K-Means算法的參數(shù)，對原數(shù)據(jù)集進行劃分。

二次聚類中無需人工指定E和Minpts，而是利用了數(shù)據(jù)自身的分布情況，所以聚類結果較為穩(wěn)定。

2.4 改進目標

TF-IDF是一種基于詞頻的算法，經常會遺漏出現(xiàn)頻率不高但是能顯著代表文本信息的詞。通過TF-IDF算法選擇出來的特征并不能完全代表原始文本，所以現(xiàn)有的基于TF-IDF的改進算法的目標都是將原始算法遺漏的低頻詞添加到算法選擇的結果之中，提高了原始算法的計算復雜度。本文設計了基于行業(yè)專有詞典的TF-IDF特征選擇算法，在避免提高算法復雜度的情況下獲取到文本準確的關鍵低頻詞。

2.5 算法改進流程

(1) 將行業(yè)專有詞典中的詞以哈希表的形式存入內存，例如：“聚亞安酯輪輻”是輪胎行業(yè)專有詞典中的詞，則在內存中以“聚亞安酯輪輻”為鍵，“1”為對應的值，鍵值就是這個詞的權重。

(2) 對文本的分詞數(shù)據(jù)進行TF-IDF值的計算，結果從小到大進行排列，TF-IDF大于閾值的詞被視為特征元素。

(3) 遍歷文本的分詞數(shù)據(jù)，如果分詞數(shù)據(jù)中的項存在于(1)生成的哈希表中，則標記該中間數(shù)據(jù)為特征元素。

(4) 將(2)和(3)中的特征合并，得到該文本的特征向量。

3 驗證實驗設計

實驗的目的在于對比由本文提出的基于行業(yè)專有詞典的TF-IDF特征選擇算法選擇出的文本特征和用普通TF-IDF算法選擇出的文本特征的差異，主要通過聚類的方法來進行驗證。通過對聚類的查全率以及查準率的比較得出實驗結論。

3.1 實驗環(huán)境

數(shù)據(jù)采集以及后續(xù)的預處理和聚類都屬于計算密集形的工作，本文的實驗環(huán)境如下：

(1) 實驗環(huán)境由臺式電腦集群構成，其系統(tǒng)為Window2003，CPU：i7-4800、內存：16 GB、硬盤：4 TB。分別負責新聞數(shù)據(jù)采集、預處理、聚類。這些模塊都使用Java語言進行編寫。

(2) 數(shù)據(jù)庫采用MySQL。

3.2 實驗流程

選取不同行業(yè)的文本進行二次聚類來橫向對比子向量空間的優(yōu)劣，其流程具體如下：

(1) 選取具有行業(yè)專有詞典的輪胎行業(yè)新聞文本20 000篇，選取金融行業(yè)新聞文本20 000篇，根據(jù)百度熱點新聞獲取的其他社會熱點新聞文本40 000篇(4類新聞，每個類10 000篇)作為原始數(shù)據(jù)；

(2) 預處理(1)中的文本；

(3) 先使用二次聚類，并從中獲得DBSCAN需要的掃描半徑；

(4) 采用(3)獲取的掃描半徑開始用DESCAN算法聚類，Minpts指定為10 000；

(5) 用K-Means算法聚類，根據(jù)粗糙集的中間結果來設定k值；

(6) 分別用K-means和DBSCAN進行聚類生成結果對照組。

3.3 實驗結果分析

實驗結果從三方面進行考察：

? 時間開銷：時間從特征選擇開始計時直到聚類結束；

? 查全率：查全率是指某個簇中數(shù)據(jù)量和數(shù)據(jù)集中與該簇同類的數(shù)據(jù)量的比值；

? 查準率：查準率是指簇中某個類別的數(shù)據(jù)總數(shù)和全簇數(shù)據(jù)總數(shù)的比值。

1) 時間開銷

各算法時間開銷如圖4所示。

圖4 時間開銷對比

圖4展示了三種算法隨文本數(shù)量變化的變化情況，可見以上三種算法的時間開銷都隨著文本增加而增加，但是二次聚類算法的增長速度較慢，而DBSCAN算法和K-Means算法增長率隨文本增加大幅上升。時間開銷上升有兩方面的原因:隨著文本數(shù)量加劇預處理的時間上升，算法自身的時間開銷。K-Means和DBSCAN算法對于不同的參數(shù)設定會有不同的時間開銷，當參數(shù)選取不當時，時間開銷較大。

2) 查全率

查全率如圖5、圖6所示。

圖5 輪胎行業(yè)的查全率

圖6 金融行業(yè)的查全率

從圖5、圖6中可以看出，查全率隨著特征向量的維數(shù)升高而升高。二次聚類的查全率高于其他兩種算法，說明二次聚類更加穩(wěn)定。輪胎行業(yè)的查全率普遍高于金融行業(yè)的查全率，這是因為在輪胎行業(yè)文本的特征選擇階段加入了輪胎行業(yè)專有詞典，從而使得輪胎行業(yè)的特征更為明顯。

3) 查準率

查準率如圖7、圖8所示。

圖7 輪胎行業(yè)的查準率

圖8 金融行業(yè)的查準率

從圖7、圖8中可以看出，查準率隨著特征向量維數(shù)的增加而降低，這是因為特征的維數(shù)越大，特征間的區(qū)別度就越低，就容易把不相關的文本聚類到簇中。總體來說，輪胎行業(yè)的查準率也高于金融行業(yè)的查準率。

從上述輪胎行業(yè)和金融行業(yè)的查全率、查準率測試結果對比中可以看出使用了行業(yè)專有詞典選擇的特征在聚類分析中對聚類效果的提升影響非常明顯，二次聚類比起人工確定參數(shù)的單次聚類表現(xiàn)得更加穩(wěn)定。

4 結 語

本文研究了垂直行業(yè)中專有詞典的生成，主要包括用統(tǒng)計的方法進行新詞的識別。本文創(chuàng)新性地將行業(yè)專有詞典用于特征的選擇中，提高了特征向量的區(qū)分度。通過對比實驗，證明了本文設計的基于行業(yè)專有詞典的TF-IDF特征選擇算法在查全率和查準率上較原始算法均有所提高。

[1] Lu Z, Zhao Q, Yang L. A segmentation method for crossing ambiguity string based on mutual information and t-test difference[C]// Information, Computing and Telecommunication, 2009. YC-ICT '09. IEEE Youth Conference on. IEEE, 2009:371-374.

[2] 羅欣, 夏德麟, 晏蒲柳. 基于詞頻差異的特征選取及改進的TF-IDF公式[J]. 計算機應用, 2005, 25(9):2031-2033.

[3] Huang X, Wu Q. Micro-blog commercial word extraction based on improved TF-IDF algorithm[C]// TENCON 2013-2013 IEEE Region 10 Conference (31194). IEEE, 2013:1-5.

[4] Xu M, He L, Xin L. A Refined TF-IDF Algorithm Based on Channel Distribution Information for Web News Feature Extraction[C]// Proceedings of the 2010 Second International Workshop on Education Technology and Computer Science-Volume 02. IEEE Computer Society, 2010:15-19.

[5] 趙衛(wèi)中, 馬慧芳, 傅燕翔,等. 基于云計算平臺Hadoop的并行k-means聚類算法設計研究[J]. 計算機科學, 2011, 38(10):166-168.

[6] Ay M, Kisi O. Modelling of chemical oxygen demand by using ANNs, ANFIS and k-means clustering techniques[J]. Journal of Hydrology, 2014, 511(7):279-289.

[7] Abbasi A A, Younis M. A Survey on Clustering Algorithms for Wireless Sensor Networks[J]. Network Based Information Systems International Conference on, 2010, 30(2-3):358-364.

[8] Wang Q, Dai H, Sun Y. A rough set based clustering algorithm and the information theoretical approach to refine clusters[C]// Intelligent Control and Automation, 2004. WCICA 2004. Fifth World Congress on. IEEE, 2004:4287-4291.

[9] Kerdprasop K, Kerdprasop N, Sattayatham P. Weighted K-Means for Density-Biased Clustering[J]. Lecture Notes in Computer Science, 2005, 3589:488-497.

[10] 付立東. 核k-means聚類檢測復雜網絡社團算法[J]. 計算機科學, 2010, 37(9):212-213.

IMPROVEMENT OF TF-IDF FEATURE SELECTION ALGORITHM BASED ON INDUSTRY PROPRIETARY DICTIONARY

Zhang Qixun1,2Liu Hongzhi1Liu Shixiang1Jia Tang1Cao Jian1,2

1(SchoolofSoftwareandMicroelectronics,PekingUniversity,Beijing102600,China)2(SchoolofElectronicsEngineeringandComputerScience,PekingUniversity,Beijing100871,China)

An industry proprietary dictionary is a dictionary of industry-specific terms, it can improve the completeness of the text feature space by applying the industry proprietary dictionary to the feature selection algorithm based on TF-IDF. The key goal of TF-IDF-based improved algorithm is to extract low-frequency keywords. The existing improved method based on statistical features increases the computational complexity of the original algorithm and reduces the efficiency of the algorithm. To solve this problem, the original TF-IDF feature selection algorithm adopts lexical mapping to extract low-frequency keywords to construct a complete feature space. Experimental results show that the feature extracted by TF-IDF algorithm based on industry proprietary dictionary can improve the recall and precision of clustering effectively in the following secondary clustering verification experiments compared with the feature extracted without using the industry proprietary dictionary feature selection algorithm.

Industry proprietary dictionary TF-IDF Feature space Feature selection algorithm

2016-05-06。張齊勛，講師，主研領域：計算機軟件與理論。劉宏志，副教授。劉詩祥，碩士生。賈堂，碩士生。曹健，講師。

TP391.1

A

10.3969/j.issn.1000-386x.2017.07.051