基于模糊啟發式的KNN算法在人才需求信息分類中的應用

唐　倩，李　梁，殷志恒

(重慶理工大學 計算機科學與工程學院， 重慶　400054)

近年來，隨著計算機網絡技術的迅速發展，網絡Web招聘信息平臺已成為招聘者發布信息和應聘者獲取信息的主要渠道。網絡招聘信息一方面能直接反映用人單位對人才的基本條件、能力和素質的要求，為應聘者提供求職參考；另一方面也能反映社會和各行業對人才的需求現狀，或未來一段時間的人才需求趨向；同時能為高等院校及時了解社會對人才的需求變化情況、分析預測未來的人才市場的熱點、有針對性地調整人才培養方案和設置安排相關課程提供重要的參考信息，有助于高校培養出更多適用的優秀人才以滿足社會的需求。

網絡Web招聘信息是最大的信息資源庫,其中文本是最主要的信息載體。文本挖掘有助于揭示Web招聘信息中大量隱藏信息，特別是對重要事實、關系、趨勢和模式的認識有價值的數據。文本挖掘技術在建模和仿真任務中是有效的，其中的文本分類方法被許多學者和研究者不斷優化。文本分類首先要正確預定義文本內容的分類標記，然后根據文本的內容判別其所屬類別[1]。目前的文本分類算法大致有樸素貝葉斯(NB)算法[2]、支持向量機(SVM)算法[3]、k-最近鄰算法(KNN)[4]等。KNN分類算法是一種簡單有效的非參數化方法[5]，在模式識別中非常有效。相比其他算法，若將其作為文本分類中的分類器，則準確性和召回率都很高。訓練集規模中廣泛采用的是相對簡單、可有效計算時空線性的方法。但是，當訓練樣本集維度較高和特征分布不均勻時，該分類器會出現分類精度不高、最近鄰穩定性不好的現象。為了解決上述KNN算法中存在的問題，本文提出了一種模糊啟發式的KNN算法以提高分類器的分類精度和最近鄰的穩定性。

1　文本預處理

1.1　文本分詞

在Web信息中通過爬蟲技術獲取非結構化的文本數據。要分析這些數據，首要的任務是對其進行爬取、正則選擇和中文文本分詞。中文文本分詞和英文文本分詞有較大差異，國內常見的開源中文分詞方法有IK分詞、庖丁解牛分詞、中國科學院的ICTCLAS[6]。本文使用jieba文本分析工具來執行中文分詞，并基于Trie樹結構實現高效的字圖掃描。通過動態規劃搜索得到一個句子中所有可能的中文單詞，找出其中最大概率路徑和基于單詞頻率的最大分詞組合，并生成有向無環圖(DAG)。當沒有出現登錄詞匯時，采用基于中文詞形成能力的HMM模型，并采用Viterbi算法[7]。

結巴分詞的過程為:將DAG中詞典中未找到的單詞組合成一個新的分詞短語，并用HMM模型進行分詞。也就是說，識別出的新詞為詞典之外的新詞。使用python yield語法生成一個單詞生成器，逐字地返回。

1.2　特征選擇TF-IDF

特征選擇的主要目的是從文本中提取更具代表性和更鮮明的詞匯來表達文本，構建文本特征子集。TF-IDF是一種統計方法，反映一個詞對一個文檔的重要性[8]。TF-IDF模型的主要思想是:如果出現在文檔d中的特征w的頻率高，同時在其他文檔中出現的頻率低，則認為該特征w具有良好的辨識力，可用做特征選擇或者被賦予更高的權重，以區別于其他類別文檔[9]。

詞頻(term frequency，TF)表征某一個單詞在整個文檔中的所有重復的單詞下出現的頻數比例。ai在特定文檔中的重要性可以表示為

(1)

其中：mi, j是詞ai在文件bj中出現的次數；分母是在文件bj中所有字詞出現次數之和。

逆文檔頻率(inverse document frequency,IDF)是表征某一個單詞在整個文檔中普遍重要性的參數，表示為

(2)

其中：|D|代表文本庫中的文件總數和；|{j:ai∈bj}|代表含有詞條ai的文件個數。

在某些文件中，當有文字出現的頻率高并且在整個文件集中文字出現的頻率低的情況下，會發生TF-IDF權重較高的現象，計算公式為：tfidfi, j=tfi, j×idfi。因此，TF-IDF傾向于特征選擇，即過濾掉沒有分辨意義的單詞并保留重要的單詞。

1.3　文本聚類AP算法

Frey等[10]于2007年提出一種新的基于數據點之間“信息傳遞”的無監督算法——AP近鄰傳播算法。該算法不需要預先確定簇的個數，在迭代過程中可不間斷地搜索合適的聚類中心，可避免初始類代表點影響最后的聚類結果。并且，該算法在處理多種數據時速度更快、性能更好。

AP算法中所有初始采樣點都被認為是潛在的聚類中心，由節點之間傳輸的吸引力消息來確定聚類中心。吸引力消息有吸引度(responsibility)和歸屬度(availability)兩個參數。吸引度r(i,k)代表點k當做點i聚類中心的適合程度。同理，歸屬度a(i,k)代表點i可以選擇點k作為其聚類中心的適合程度[12]。消息傳遞過程如圖1所示。

圖1　消息傳遞過程

r(i,k)、r(i,k)和a(i,k)的初始值都是0，r(i,k)和a(i,k)的值的大小與k點成為聚類中心的概率成正比。近鄰傳播聚類算法的吸引度和歸屬度的更新迭代過程如下：

(3)

(4)

(5)

(6)

i≠k,λ∈[0.5,1)

(7)

i≠k,λ∈[0.5,1)

(8)

式(1)計算相似度矩陣S(i,j)的大小，其中P(i)是參考度,并影響AP簇的數量。假設初始時刻所有參考度的值相等。如果參考值是相似度矩陣S(i,j)，則迭代之后的簇的數量是相同的；如果參考值是最小的，那么迭代產生最少數量的簇。

在式(3)和(4)中，收斂系數通過控制其自身的大小來調節算法的收斂速度和穩定性。

2　文本分類

2.1　KNN算法

對于測試集中的每個測試對象，傳統的k近鄰算法需要計算每個測試對象與訓練對象中每個對象之間的距離，然后根據測試對象間的距離進行排序以找到最接近測試對象的k個對象。測試對象和訓練對象根據式(9)對測試對象的候選類別進行評分并排序，把測試對象歸屬到得分數最高的那一類別中。

(9)

其中：x是測試集文本；c是訓練集的類別，是與x最接近的k個文本之一；sim(x,d)是文本x與文本d的相似度，這里指的是距離；I(d,c)表示d是否屬于c類，如果屬于c類則為1，否則為0。

2.2　啟發式的KNN算法

具有模糊距離度量的啟發式KNN算法的主要組成部分是搜索單元、模糊邏輯單元和分類單元。目前，在k-近鄰算法上采用ABC(人工蟻群算法)的權重調整和遺傳算法的權重調整方法來作為權重向量的選取并提高搜索性能。

搜索單元的任務是探索最佳的權重值，在經典KNN算法中提供最佳的分類結果和基于模糊邏輯的距離測量以及KNN分類過程?；谀：壿嫷南嗨菩远攘繂挝挥糜趧摻ň嚯x矩陣，表示測試觀測值與訓練觀測值/采樣值之間的距離，屬于分類問題(本研究中來自網絡web招聘文本信息的7個數據類別)。模糊邏輯單元的主要組成部分是差異性、模糊性、規則性、決策性和模糊性單位。基于KNN的分類單元使用由模糊邏輯單元創建的距離矩陣和經典而直觀的方法確定測試觀測的類別。

傳統度量方法如KNN算法只考慮k-item最近鄰計算方式，然后對新的測試對象進行分類。根據它們到測試對象檢驗觀察的距離來確定每個k鄰居。為此，它的距離應該是測試對象(觀察點)和訓練對象之間的距離(樣本觀察點)。距離度量用于為測試對象創建一個距離數組?；镜木嚯x度量標準是歐幾里得(EU)、曼哈頓(MA)和明科夫斯基(MI)標準。經典距離測量的參數方法是測試觀察點、樣本或訓練觀察點和距離度量。這里假設的樣本觀察點是訓練樣本的多維向量空間中的樣本觀察點，距離樣本之間的兩點可以根據觀測的特征向量和度量“EU”來計算。

在模糊啟發式KNN分類器中，通過近鄰傳播算法對樣本集進行聚類，刪除噪聲對象，將訓練集劃分為多個簇，再統計文本訓練集的類別分布。最后，利用向量夾角余弦公式計算待分類文本與聚類中心的相似度。如果計算得出的相似度小于最小相似度，則不把其歸入到計算范圍內，以此減少樣本數量，從而提高效率。因此，基于AP聚類的模糊啟發式KNN文本分類算法大致流程如下:

1) 首先采用jieba分詞對中文文本進行分詞。

2) 對訓練集文本的特征項降維，去噪。

3) 把訓練集文本表示為特征向量。

4) 采用權重計算公式TF-IDF：Wik=tfik×idfk來計算文本特征項的權重，其中：tfik表示特征項Tk在文本Di的詞頻；idfk表示特征項Tk出現的文檔頻率的反比。

5) 使用近鄰傳播算法對文本訓練集S進行聚類，以獲得新的訓練集Snew。

6) 對于每個待分類文本D，根據模糊啟發式的KNN分類流程對待分類文本D進行分類。

表1　招聘信息崗位數據

3　實驗結果及分析

3.1　實驗數據

為了驗證本文提出的基于模糊啟發式的KNN算法相比經典的KNN算法在網絡文本挖掘中的優勢，通過爬取前程無憂網絡招聘網站上招聘信息中近3個月的關于產品、市場與銷售、技術、職能、設計、運營、金融方面的數據為實驗對象進行測試。數據如表1所示，其中每一類別包括大量有多個特征屬性的條目。從樣本中隨機選取80%文本數據作為訓練集，其余20%數據作為相應的測試集。

3.2　分類效果評價指標

在對文本分類的效果進行評估時，常用的標準有查準率、召回率以及F1值等。準確率(Pp)指的是分類的正確文本數(Sr)與實際分類的文本數(Sa)的比值，計算式為

(10)

召回率(Pc)指的是分類的正確文本數(Sr)與應有的文本數(So)的比值，計算式為

(11)

準確率和召回率反映的是兩個不同的方面，通常情況下需要綜合考察這兩個指標。F1值是綜合評價這兩者的一個指標，計算式為

(12)

F1值把準確率和召回率的思想結合在一起，因此只有兩者的精度都提高，才能獲得比較理想的F1值。F1值的大小和聚類的效果呈正相關。

3.3　實驗結果及分析

改進前后的KNN對比算法的混淆矩陣、準確率、召回率和F1值的對比分別如圖2～6所示。

圖2　經典KNN的混淆矩陣

圖4　KNN與改進KNN召回率

圖6　KNN與改進KNN 的F1值

圖2、3分別代表經典的KNN算法與改進后的模糊啟發式KNN算法分類后的混淆矩陣，對角線上是正確聚類到相應類別的數量，其他則為錯誤分配出去的數量。觀察圖4、5可以看出：改進后的KNN算法的召回率相比傳統KNN算法的召回率只在設計這一類別稍低，在準確率方面只在技術這一類別稍低。通常，僅從準確率和召回率兩個方面來比較兩個算法的優劣不能體現兩個算法的整體性能優劣，因而可以通過比較兩個算法的F1值來體現兩個算法的整體情況。從圖6中F1的圖表數據可以看出：改進的模糊啟發式算法的F1值優于經典算法。因此，可以得出結論：在網絡人才需求信息的訓練集下，本文提出的改進的模糊啟發式KNN算法比傳統KNN算法的分類效率有所提高。也可以看出優化后的KNN算法的鄰居穩定性要優于經典的KNN算法。

4　結束語

本文針對k-近鄰算法在網絡文本數據中特征維度高的情況下精度低、穩定性差，剪裁也容易出現錯誤等問題，提出了一種采用模糊啟發式的KNN文本分類算法。該算法首先對網絡文本數據集進行爬蟲和預處理操作，接著利用無需設定初始聚類中心的近鄰傳播算法形成簇類；然后以待聚類文本與聚類中心的相似度方法裁剪訓練集，再采用模糊啟發式的KNN分類器進行文本分類。通過實驗結果分析與比較可以看出：優化后的算法的效率在高維特征空間下有所提高。然而，該算法仍然有很大的改進空間。如何在海量數據處理中降低時間復雜度是后續工作中需要深入研究的方向。

參考文獻：

[1]羅賢鋒,祝勝林,陳澤健,等.基于K-Medoids聚類的改進KNN文本分類算法[J].計算機工程與設計,2014,35(11):3864-3867.

[2]RENNIE J D M.Tackling the poor assumptions of naive Bayes text classifiers[C]//Proc.Twentieth International Conference on Machine Learning.USA:[s.n.],2017:616-623.

[3]CHEN D,TIAN Y.V-Structural Nonparallel Support Vector Machine for Pattern Classification[C]//Ieee/wic/acm International Conference on Web Intelligence Workshops.USA:IEEE,2017:33-36.

[5]劉應東,?；菝?基于K-均值聚類的小樣本集KNN分類算法[J].計算機應用與軟件,2011,28(5):112-113.

[6]詹川.基于文本挖掘的專業人才技能需求分析——以電子商務專業為例[J].圖書館論壇,2017,37(5):116-123.

[7]ZOLOTAREV V V,GRINCHENKO N N,OVECHKIN G V,et al.Modified Viterbi algorithm for decoding of block codes[C]//Mediterranean Conference on Embedded Computing.USA:[s.n.],2017:1-4.

[8]劉為懷,才華,何東杰.一種基于中文分詞和數據聚合的餐飲行為特征挖掘方法[J].軟件產業與工程,2015(4):47-51.

[9]GAO J,ZHANG C X,WANG Z,et al.Question Classification Based on Improved TFIDF Algorithm[C]//International Conference on Control,Automation and Artificial Intelligence.USA:[s.n.],2017.

[10] 王淑靖.非重疊社區發現中近鄰傳播算法的研究與應用[D].徐州:中國礦業大學,2016.

[11] 楊凡穩,曾志高,劉強,等.基于AP聚類算法的圖像分割應用與研究[J].計算技術與自動化,2015(3):88-91.

[12] YANG Y B,WANG C D,LAI J H.A Distributed Multi-exemplar Affinity Propagation Clustering Algorithm Based on MapReduce[C]//IEEE Third International Conference on Big Data Computing Service and Applications.USA:IEEE,2017:191-197.