基于KNN 算法的財(cái)政預(yù)算監(jiān)督方法

沈 斌，趙重遠(yuǎn)

武漢工程大學(xué)電氣信息學(xué)院，湖北 武漢 430205

預(yù)算績效是一種以結(jié)果為導(dǎo)向的財(cái)政預(yù)算管理模式，其作用是對(duì)財(cái)政資金進(jìn)行編制預(yù)算并對(duì)結(jié)果進(jìn)行分析評(píng)價(jià)，最終應(yīng)用到下一年的預(yù)算安排中。而在實(shí)際應(yīng)用過程中，出現(xiàn)很多單位不按照規(guī)定的績效目標(biāo)使用資金，最終導(dǎo)致結(jié)果評(píng)估不準(zhǔn)確的情況。所以為了解決預(yù)算績效使用不規(guī)范的問題，本文提出一種基于KNN 算法的財(cái)政預(yù)算監(jiān)督方法。

本方法按照語義分析的原理，提取交易報(bào)文中的特征項(xiàng)，快速判斷各類交易報(bào)文所屬的預(yù)算類別，其監(jiān)管工作由人工審核交由系統(tǒng)自行處理，減少了人力成本，提高預(yù)算績效考核的準(zhǔn)確性和實(shí)時(shí)性，為財(cái)政預(yù)算績效考核提供新的思路和方法。

作為常用文本分類器之一的傳統(tǒng)的K 最近鄰分類算法［1］（tranditional k-nearest neighbor，T-KNN），T-KNN 算法是以樣本特征空間中的最鄰近K 個(gè)樣本來投票以決定它的分類，這種投票分類的決策容易受到K 值、特征向量、待檢測(cè)數(shù)據(jù)規(guī)模的影響，從而出現(xiàn)檢測(cè)準(zhǔn)確率下降及檢測(cè)速度變慢的問題。鮑舒婷等［2］通過歐式距離與近鄰相似度的結(jié)合算法來定義樣本的局部密度，減少了傳統(tǒng)算法中對(duì)截?cái)嗑嚯x的依賴。Gabrilovich 等［3］提出了一種云環(huán)境下基于貝葉斯與決策樹的主動(dòng)云計(jì)算錯(cuò)誤文本類別管理方法，首先利用貝葉斯模型預(yù)測(cè)出錯(cuò)誤行為，系統(tǒng)管理員對(duì)其進(jìn)行標(biāo)記，然后利用標(biāo)記的錯(cuò)誤樣本點(diǎn)作為訓(xùn)練樣本構(gòu)建決策樹，最后對(duì)未標(biāo)記的樣本點(diǎn)進(jìn)行錯(cuò)誤預(yù)測(cè)。再如Jannach 等［4］對(duì)KNN 算法中的特征值加權(quán)方法進(jìn)行的改進(jìn)，用模式搜索代替原有的歐式距離搜索方法，并引用了統(tǒng)計(jì)回歸模型，此方法降低了誤檢率，且降低了計(jì)算成本。

T-KNN 作為一種經(jīng)典的統(tǒng)計(jì)模式識(shí)別方法，識(shí)別主要靠待檢測(cè)數(shù)據(jù)周圍的臨近樣本，因此在類別區(qū)域邊界的交叉部分或數(shù)據(jù)量較大時(shí)存在過多的噪聲數(shù)據(jù)［5］會(huì)對(duì)樣本檢測(cè)準(zhǔn)確性產(chǎn)生影響，為了提高分類性能，可以使用給噪聲數(shù)據(jù)較小的隸屬度與加權(quán)投票等方法，對(duì)訓(xùn)練樣本及分類器做一定的優(yōu)化，本文提出了一種基于KNN 算法的改進(jìn)KNN算法（improved k-nearest neighbor，I-KNN）。

1 數(shù)據(jù)檢測(cè)模型

該數(shù)據(jù)檢測(cè)模型主要由2 個(gè)部分組成。第一部分：由于目前財(cái)政預(yù)算請(qǐng)求都是通過XML 格式的報(bào)文進(jìn)行信息傳遞，首先需要在財(cái)政端傳遞的報(bào)文中，遍歷其節(jié)點(diǎn)獲取其中的文本信息［6］，將XML 處理成待檢測(cè)數(shù)據(jù)文本集。第二部分：確定訓(xùn)練文本集之前，由于噪聲數(shù)據(jù)一般分布于類邊界，故使用Chen 等［7］提出的基于密度的快速密度峰值搜索算法進(jìn)行類簇分類，然后根據(jù)Du等［8］提出的不對(duì)稱邊界變精度粗糙集模型，篩選出噪聲數(shù)據(jù)，最后給予噪聲數(shù)據(jù)一個(gè)較小的隸屬度以減小噪聲數(shù)據(jù)對(duì)后續(xù)檢測(cè)的影響，確定了訓(xùn)練文本集后，就可對(duì)財(cái)政預(yù)算請(qǐng)求待檢測(cè)文本進(jìn)行檢測(cè)，本文主要介紹第二部分。

2 改進(jìn)的KNN 預(yù)警檢測(cè)方法

2.1 訓(xùn)練集預(yù)處理

檢測(cè)系統(tǒng)的性能通常由其穩(wěn)定性、準(zhǔn)確性、快速性來判斷，而財(cái)政系統(tǒng)的預(yù)算請(qǐng)求數(shù)據(jù)的預(yù)警功能，其準(zhǔn)確性更是成了重中之重。該檢測(cè)方法的財(cái)政請(qǐng)求預(yù)警類別訓(xùn)練集中的類別越平均，內(nèi)容越全面，其檢測(cè)的準(zhǔn)確性就越高。首先將訓(xùn)練樣本數(shù)據(jù)進(jìn)行類簇處理找出它的類簇中心點(diǎn)［9］，然后對(duì)距離類簇中心點(diǎn)過遠(yuǎn)的噪聲數(shù)據(jù)進(jìn)行預(yù)處理。

首先將該文本集進(jìn)行聚類分類，找出它的類簇中心點(diǎn)，而類簇中心點(diǎn)一般具有以下2 個(gè)特點(diǎn)：類簇中心被一群密度較低的臨近點(diǎn)包圍；類簇中心離其他具有更高的局部密度的點(diǎn)距離都較大。

根據(jù)這2 個(gè)特點(diǎn)，以類別分類的各類簇中心應(yīng)該同時(shí)具有較大的局部密度和相對(duì)距離，要確定數(shù)據(jù)集各類簇中心，對(duì)于每個(gè)數(shù)據(jù)點(diǎn)都要計(jì)算它的局部密度ρi和距離δi。局部密度的定義如下：

其中，S 代表整個(gè)數(shù)據(jù)集，dc是截?cái)嗑嚯x，式(1)需要先設(shè)置好截?cái)嘀礵c，而dc的值通常選取所有點(diǎn)之間的相互距離升序前2%，dij是點(diǎn)i 到點(diǎn)j的歐式距離，其定義如式（3）所示。

距離參數(shù)如式（4）所示：

在待檢測(cè)的訓(xùn)練集內(nèi)選取ρi與δi都較大的點(diǎn)作為類簇中心點(diǎn)，即

在確定了所有類的類簇中心點(diǎn)，其余待檢測(cè)訓(xùn)練集中的點(diǎn)會(huì)根據(jù)局部密度［10］進(jìn)行點(diǎn)的排序，從而得到密度點(diǎn)集合G。

其中，pi=為密度參數(shù)，pij為類簇中心與待測(cè)試樣本之間的所有路徑，l 為連接樣本點(diǎn)與類簇中心點(diǎn)間的訓(xùn)練樣本的個(gè)數(shù)為xk與xk+1之間的歐式距離。在選擇出所有的類簇中心后，剩下的樣本點(diǎn)會(huì)分配給局部密度大于該樣本點(diǎn)本身且與之距離最近的點(diǎn)所在的類簇。

將訓(xùn)練集以類分簇后，就可以根據(jù)式（7）確定噪聲數(shù)據(jù)，當(dāng)樣本T 中的訓(xùn)練樣本點(diǎn)到類簇中心的距離大于R，則該樣本點(diǎn)為噪聲數(shù)據(jù)。

其中j ≤N-1，density(x_j)∈G，ε 為調(diào)節(jié)閾值，a 為樣本中心點(diǎn)。

最后根據(jù)式（8）計(jì)算T 樣本中的訓(xùn)練樣本的隸屬度，并給予噪聲數(shù)據(jù)一個(gè)較小的隸屬度。

2.2 預(yù)警類別特征加權(quán)

當(dāng)訓(xùn)練集的類別點(diǎn)分布不均勻時(shí)，每個(gè)待檢測(cè)樣本在尋找其K 個(gè)近鄰點(diǎn)時(shí)會(huì)更趨向于測(cè)試集樣本中數(shù)量最多的那個(gè)類別。如果使用傳統(tǒng)的T-KNN 算法除了數(shù)量最多的那個(gè)類別，其他類別的準(zhǔn)確率都會(huì)不同程度降低。所以采取對(duì)文本內(nèi)的樣本點(diǎn)進(jìn)行加權(quán)的方式，來降低樣本分布不均勻時(shí)產(chǎn)生的分類準(zhǔn)確率的影響。加權(quán)的步驟如下：

1）在進(jìn)行了預(yù)處理的集合D 中，將訓(xùn)練樣本歸一化，根據(jù)特征值找出能代表集合D 的特征向量。本方法中使用K 近鄰中類別的平均文本值作為理想向量［11］。其權(quán)重的修正公式為

式（9）中Num( Ci)為K 近鄰中屬于Ci的文本數(shù)量，Avgnum( Cl)為平均文本數(shù)。

2）根據(jù)加權(quán)方法［12-13］，可以通過確定每個(gè)特征的權(quán)值來確定最終的分類

式（10）中Ji為待檢測(cè)文本的特征向量，sim( Ji，Jj)為計(jì)算相似度公式，Hi為待檢測(cè)樣本的類別權(quán)重。如果待測(cè)試文本屬于Ci，則函數(shù)y 為1，否則為0。

2.3 確定訓(xùn)練樣本

針對(duì)計(jì)算的數(shù)據(jù)量大，數(shù)據(jù)源多等特點(diǎn)，本文根據(jù)財(cái)政預(yù)算績效制定的預(yù)算使用規(guī)則進(jìn)行樹結(jié)構(gòu)分層［14］，減少計(jì)算量，具體步驟為：

1）根據(jù)財(cái)政專業(yè)知識(shí)將預(yù)警類別分類為n 層樹狀結(jié)構(gòu)。對(duì)于前n-1 層中，判斷每個(gè)類型中與待檢測(cè)樣本最鄰近的個(gè)節(jié)點(diǎn)的預(yù)警類型是否存在子節(jié)點(diǎn)，若存在則加入子節(jié)點(diǎn)一起作為訓(xùn)練樣本，若不存在則直接進(jìn)入預(yù)警類型的下一層。

2）引入上下近似區(qū)域［15］計(jì)算方法，設(shè)置上述分層遍歷后的訓(xùn)練樣本集中存在的m 個(gè)類簇，其類簇中心點(diǎn)在預(yù)處理時(shí)已經(jīng)得出，然后計(jì)算類簇中心點(diǎn)與該類別的所有樣本的相似度，取最小值作為上近似半徑。再將相似度大于隸屬度R 的樣本中的點(diǎn)與類簇中心最近的距離作為下近似區(qū)域。

3）確定各預(yù)處理后的類別的上下近似區(qū)域。

2.4 確定待檢測(cè)數(shù)據(jù)的類別

在確定較為準(zhǔn)確的訓(xùn)練集后，就可以進(jìn)行檢測(cè)了。具體步驟如下：

1）對(duì)于一個(gè)待檢測(cè)文本集，根據(jù)它的特征詞形成待檢測(cè)文本向量。

2）依次計(jì)算待檢測(cè)文本集與n 層訓(xùn)練集中的每個(gè)文本的相似度。

3）文本相似度的計(jì)算公式為：

式（11）中，Ji為測(cè)試文本的特征向量；Jj1為1 層j類的中心向量；M 為特征向量的維數(shù)；Wik為第i個(gè)向量的第K 維。K 的值根據(jù)實(shí)驗(yàn)結(jié)果的準(zhǔn)確度進(jìn)行調(diào)整。

4）在對(duì)待檢測(cè)文本的數(shù)據(jù)經(jīng)過加權(quán)以后，通過式（10）來確定待檢測(cè)文本中的各個(gè)點(diǎn)的類別是否屬于下近似區(qū)域內(nèi)，如果是則直接歸入該類，如果不是則判斷為未知可疑類別的財(cái)政預(yù)算請(qǐng)求。

3 結(jié)果與討論

3.1 數(shù)據(jù)準(zhǔn)備

本實(shí)驗(yàn)使用湖北省某國庫支付代理銀行2019年上半年的財(cái)政報(bào)文請(qǐng)求數(shù)據(jù)中存在不同類別的預(yù)警數(shù)據(jù)共計(jì)18 000 份。為清晰實(shí)驗(yàn)過程，本實(shí)驗(yàn)將請(qǐng)求報(bào)文節(jié)點(diǎn)分類為3 層樹結(jié)構(gòu)。

實(shí)驗(yàn)檢測(cè)準(zhǔn)確性的評(píng)估指標(biāo)［16］一般以真正類率（true positive rate，TPR），真負(fù)類率（true negative rate，TNR）來作為評(píng)估參考。

其中，Apr即被檢測(cè)為正常無預(yù)警類別的樣本占所有正常樣本的比例。Cnr是指被檢測(cè)為存在相應(yīng)預(yù)警類型的樣本占所有含預(yù)警類型樣本的比例。T 為正常無預(yù)警類別的樣本數(shù)，N 為存在預(yù)警類型的樣本數(shù)，F(xiàn) 為存在預(yù)警類型的正常樣本數(shù)，P 為所有正常樣本中含預(yù)警類型的樣本數(shù)。

3.2 準(zhǔn)確率分析

本實(shí)驗(yàn)從報(bào)文中選取產(chǎn)品預(yù)警類型1 500 份（包括產(chǎn)品型號(hào)可疑樣本700 份，產(chǎn)品個(gè)數(shù)可疑樣本800 份），收款方可疑類型1 500 份（包括收款人可疑樣本700 份，收款公司可疑樣本800 份），金額可疑類型1 500 份以及1 500 個(gè)正常報(bào)文樣本作為訓(xùn)練樣本，訓(xùn)練樣本總量為6 000 份，然后使用包含各個(gè)可疑類型樣本12 000 份作為待檢測(cè)數(shù)據(jù)，近鄰樣本個(gè)數(shù)k=16，圖1 為T-KNN 算法與I-KNN 的真正類率（TPR）與真負(fù)類率（TNR）檢測(cè)準(zhǔn)確度的比較結(jié)果。

圖1 T-KNN 與I-KNN 的比較：（a）真正類率，（b）真負(fù)類率Fig.1 Comparison of T-KNN and I-KNN：（a）true positive rate，（b）true negative rate

從上述實(shí)驗(yàn)中可以看出，從Apr與Cnr的準(zhǔn)確率來看，改進(jìn)后的I-KNN 算法均比傳統(tǒng)的T-KNN算法有一定程度的提高，在樣本數(shù)量較小的時(shí)候增幅不是很明顯，但在樣本數(shù)量增加以后，I-KNN較之于傳統(tǒng)T-KNN 算法的真正類率（TPR）由86.1%提升到88.9%，真負(fù)類率（TNR）由85.3%提升到88.4%。綜上所述，I-KNN 在分類準(zhǔn)確率上的改進(jìn)有效。

3.3 檢測(cè)時(shí)間分析

將12 000 份報(bào)文作為速度檢測(cè)樣本均分為3份，每份4 000 個(gè)樣本，分別為Dataset1，Dataset2，Dataset3，并使用T-KNN 算法與I-KNN 算法分別記錄其分類時(shí)間，如表1 所示。

表1 分類時(shí)間比較Tab.1 Comparison of classification times ms

從表1 可以看出：3 份數(shù)據(jù)集在檢測(cè)時(shí)間上I-KNN 算法比傳統(tǒng)的T-KNN 算法均縮短了大約40%，本文提出的I-KNN 算法在檢測(cè)時(shí)間上明顯優(yōu)于T-KNN 算法。

4 結(jié) 論

本文提出的將傳統(tǒng)KNN 的改進(jìn)算法應(yīng)用于數(shù)據(jù)量較大的財(cái)政預(yù)算請(qǐng)求檢測(cè)中，通過給予噪聲數(shù)據(jù)更小的隸屬度和權(quán)重，使檢測(cè)結(jié)果更加精確，同時(shí)對(duì)訓(xùn)練集在一定的規(guī)則下分層為樹結(jié)構(gòu)，簡化了檢測(cè)的時(shí)間。由實(shí)驗(yàn)可以看出，I-KNN 是一種檢測(cè)準(zhǔn)確率較高、分類速度較快的報(bào)文分類算法，對(duì)識(shí)別財(cái)政資金的性質(zhì)和分類有一定的應(yīng)用價(jià)值。但是由于該方法的分類類別需要人為去維護(hù)，后續(xù)將進(jìn)一步改進(jìn)本方法的不足之處。