唐　倩，李　梁，殷志恒

(重慶理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 重慶　400054)

近年來(lái)，隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的迅速發(fā)展，網(wǎng)絡(luò)Web招聘信息平臺(tái)已成為招聘者發(fā)布信息和應(yīng)聘者獲取信息的主要渠道。網(wǎng)絡(luò)招聘信息一方面能直接反映用人單位對(duì)人才的基本條件、能力和素質(zhì)的要求，為應(yīng)聘者提供求職參考；另一方面也能反映社會(huì)和各行業(yè)對(duì)人才的需求現(xiàn)狀，或未來(lái)一段時(shí)間的人才需求趨向；同時(shí)能為高等院校及時(shí)了解社會(huì)對(duì)人才的需求變化情況、分析預(yù)測(cè)未來(lái)的人才市場(chǎng)的熱點(diǎn)、有針對(duì)性地調(diào)整人才培養(yǎng)方案和設(shè)置安排相關(guān)課程提供重要的參考信息，有助于高校培養(yǎng)出更多適用的優(yōu)秀人才以滿足社會(huì)的需求。

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

1　文本預(yù)處理

1.1　文本分詞

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

結(jié)巴分詞的過(guò)程為:將DAG中詞典中未找到的單詞組合成一個(gè)新的分詞短語(yǔ)，并用HMM模型進(jìn)行分詞。也就是說(shuō)，識(shí)別出的新詞為詞典之外的新詞。使用python yield語(yǔ)法生成一個(gè)單詞生成器，逐字地返回。

1.2　特征選擇TF-IDF

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

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

(1)

其中：mi, j是詞ai在文件bj中出現(xiàn)的次數(shù)；分母是在文件bj中所有字詞出現(xiàn)次數(shù)之和。

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

(2)

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

在某些文件中，當(dāng)有文字出現(xiàn)的頻率高并且在整個(gè)文件集中文字出現(xiàn)的頻率低的情況下，會(huì)發(fā)生TF-IDF權(quán)重較高的現(xiàn)象，計(jì)算公式為：tfidfi, j=tfi, j×idfi。因此，TF-IDF傾向于特征選擇，即過(guò)濾掉沒(méi)有分辨意義的單詞并保留重要的單詞。

1.3　文本聚類(lèi)AP算法

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

AP算法中所有初始采樣點(diǎn)都被認(rèn)為是潛在的聚類(lèi)中心，由節(jié)點(diǎn)之間傳輸?shù)奈ο?lái)確定聚類(lèi)中心。吸引力消息有吸引度(responsibility)和歸屬度(availability)兩個(gè)參數(shù)。吸引度r(i,k)代表點(diǎn)k當(dāng)做點(diǎn)i聚類(lèi)中心的適合程度。同理，歸屬度a(i,k)代表點(diǎn)i可以選擇點(diǎn)k作為其聚類(lèi)中心的適合程度[12]。消息傳遞過(guò)程如圖1所示。

圖1　消息傳遞過(guò)程

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

(3)

(4)

(5)

(6)

i≠k,λ∈[0.5,1)

(7)

i≠k,λ∈[0.5,1)

(8)

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

在式(3)和(4)中，收斂系數(shù)通過(guò)控制其自身的大小來(lái)調(diào)節(jié)算法的收斂速度和穩(wěn)定性。

2　文本分類(lèi)

2.1　KNN算法

對(duì)于測(cè)試集中的每個(gè)測(cè)試對(duì)象，傳統(tǒng)的k近鄰算法需要計(jì)算每個(gè)測(cè)試對(duì)象與訓(xùn)練對(duì)象中每個(gè)對(duì)象之間的距離，然后根據(jù)測(cè)試對(duì)象間的距離進(jìn)行排序以找到最接近測(cè)試對(duì)象的k個(gè)對(duì)象。測(cè)試對(duì)象和訓(xùn)練對(duì)象根據(jù)式(9)對(duì)測(cè)試對(duì)象的候選類(lèi)別進(jìn)行評(píng)分并排序，把測(cè)試對(duì)象歸屬到得分?jǐn)?shù)最高的那一類(lèi)別中。

(9)

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

2.2　啟發(fā)式的KNN算法

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

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

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

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

1) 首先采用jieba分詞對(duì)中文文本進(jìn)行分詞。

2) 對(duì)訓(xùn)練集文本的特征項(xiàng)降維，去噪。

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

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

5) 使用近鄰傳播算法對(duì)文本訓(xùn)練集S進(jìn)行聚類(lèi)，以獲得新的訓(xùn)練集Snew。

6) 對(duì)于每個(gè)待分類(lèi)文本D，根據(jù)模糊啟發(fā)式的KNN分類(lèi)流程對(duì)待分類(lèi)文本D進(jìn)行分類(lèi)。

表1　招聘信息崗位數(shù)據(jù)

3　實(shí)驗(yàn)結(jié)果及分析

3.1　實(shí)驗(yàn)數(shù)據(jù)

為了驗(yàn)證本文提出的基于模糊啟發(fā)式的KNN算法相比經(jīng)典的KNN算法在網(wǎng)絡(luò)文本挖掘中的優(yōu)勢(shì)，通過(guò)爬取前程無(wú)憂網(wǎng)絡(luò)招聘網(wǎng)站上招聘信息中近3個(gè)月的關(guān)于產(chǎn)品、市場(chǎng)與銷(xiāo)售、技術(shù)、職能、設(shè)計(jì)、運(yùn)營(yíng)、金融方面的數(shù)據(jù)為實(shí)驗(yàn)對(duì)象進(jìn)行測(cè)試。數(shù)據(jù)如表1所示，其中每一類(lèi)別包括大量有多個(gè)特征屬性的條目。從樣本中隨機(jī)選取80%文本數(shù)據(jù)作為訓(xùn)練集，其余20%數(shù)據(jù)作為相應(yīng)的測(cè)試集。

3.2　分類(lèi)效果評(píng)價(jià)指標(biāo)

在對(duì)文本分類(lèi)的效果進(jìn)行評(píng)估時(shí)，常用的標(biāo)準(zhǔn)有查準(zhǔn)率、召回率以及F1值等。準(zhǔn)確率(Pp)指的是分類(lèi)的正確文本數(shù)(Sr)與實(shí)際分類(lèi)的文本數(shù)(Sa)的比值，計(jì)算式為

(10)

召回率(Pc)指的是分類(lèi)的正確文本數(shù)(Sr)與應(yīng)有的文本數(shù)(So)的比值，計(jì)算式為

(11)

準(zhǔn)確率和召回率反映的是兩個(gè)不同的方面，通常情況下需要綜合考察這兩個(gè)指標(biāo)。F1值是綜合評(píng)價(jià)這兩者的一個(gè)指標(biāo)，計(jì)算式為

(12)

F1值把準(zhǔn)確率和召回率的思想結(jié)合在一起，因此只有兩者的精度都提高，才能獲得比較理想的F1值。F1值的大小和聚類(lèi)的效果呈正相關(guān)。

3.3　實(shí)驗(yàn)結(jié)果及分析

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

圖2　經(jīng)典KNN的混淆矩陣

圖4　KNN與改進(jìn)KNN召回率

圖6　KNN與改進(jìn)KNN 的F1值

圖2、3分別代表經(jīng)典的KNN算法與改進(jìn)后的模糊啟發(fā)式KNN算法分類(lèi)后的混淆矩陣，對(duì)角線上是正確聚類(lèi)到相應(yīng)類(lèi)別的數(shù)量，其他則為錯(cuò)誤分配出去的數(shù)量。觀察圖4、5可以看出：改進(jìn)后的KNN算法的召回率相比傳統(tǒng)KNN算法的召回率只在設(shè)計(jì)這一類(lèi)別稍低，在準(zhǔn)確率方面只在技術(shù)這一類(lèi)別稍低。通常，僅從準(zhǔn)確率和召回率兩個(gè)方面來(lái)比較兩個(gè)算法的優(yōu)劣不能體現(xiàn)兩個(gè)算法的整體性能優(yōu)劣，因而可以通過(guò)比較兩個(gè)算法的F1值來(lái)體現(xiàn)兩個(gè)算法的整體情況。從圖6中F1的圖表數(shù)據(jù)可以看出：改進(jìn)的模糊啟發(fā)式算法的F1值優(yōu)于經(jīng)典算法。因此，可以得出結(jié)論：在網(wǎng)絡(luò)人才需求信息的訓(xùn)練集下，本文提出的改進(jìn)的模糊啟發(fā)式KNN算法比傳統(tǒng)KNN算法的分類(lèi)效率有所提高。也可以看出優(yōu)化后的KNN算法的鄰居穩(wěn)定性要優(yōu)于經(jīng)典的KNN算法。

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

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

參考文獻(xiàn)：

[1]羅賢鋒,祝勝林,陳澤健,等.基于K-Medoids聚類(lèi)的改進(jìn)KNN文本分類(lèi)算法[J].計(jì)算機(jī)工程與設(shè)計(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]劉應(yīng)東,?；菝?基于K-均值聚類(lèi)的小樣本集KNN分類(lèi)算法[J].計(jì)算機(jī)應(yīng)用與軟件,2011,28(5):112-113.

[6]詹川.基于文本挖掘的專(zhuān)業(yè)人才技能需求分析——以電子商務(wù)專(zhuān)業(yè)為例[J].圖書(shū)館論壇,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]劉為懷,才華,何東杰.一種基于中文分詞和數(shù)據(jù)聚合的餐飲行為特征挖掘方法[J].軟件產(chǎn)業(yè)與工程,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] 王淑靖.非重疊社區(qū)發(fā)現(xiàn)中近鄰傳播算法的研究與應(yīng)用[D].徐州:中國(guó)礦業(yè)大學(xué),2016.

[11] 楊凡穩(wěn),曾志高,劉強(qiáng),等.基于AP聚類(lèi)算法的圖像分割應(yīng)用與研究[J].計(jì)算技術(shù)與自動(dòng)化,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.