《武汉工程大学学报》 2020年01期
108-112
出版日期：2021-01-25
ISSN:1674-2869
CN:42-1779/TQ
基于KNN算法的财政预算监督方法
预算绩效是一种以结果为导向的财政预算管理模式，其作用是对财政资金进行编制预算并对结果进行分析评价，最终应用到下一年的预算安排中。而在实际应用过程中，出现很多单位不按照规定的绩效目标使用资金，最终导致结果评估不准确的情况。所以为了解决预算绩效使用不规范的问题，本文提出一种基于KNN算法的财政预算监督方法。本方法按照语义分析的原理，提取交易报文中的特征项，快速判断各类交易报文所属的预算类别，其监管工作由人工审核交由系统自行处理，减少了人力成本，提高预算绩效考核的准确性和实时性，为财政预算绩效考核提供新的思路和方法。作为常用文本分类器之一的传统的K最近邻分类算法［1］（tranditional k-nearest neighbor，T-KNN），T-KNN算法是以样本特征空间中的最邻近K个样本来投票以决定它的分类，这种投票分类的决策容易受到K值、特征向量、待检测数据规模的影响，从而出现检测准确率下降及检测速度变慢的问题。鲍舒婷等［2］通过欧式距离与近邻相似度的结合算法来定义样本的局部密度，减少了传统算法中对截断距离的依赖。Gabrilovich等［3］提出了一种云环境下基于贝叶斯与决策树的主动云计算错误文本类别管理方法，首先利用贝叶斯模型预测出错误行为，系统管理员对其进行标记，然后利用标记的错误样本点作为训练样本构建决策树，最后对未标记的样本点进行错误预测。再如Jannach等 ［4］对KNN算法中的特征值加权方法进行的改进，用模式搜索代替原有的欧式距离搜索方法，并引用了统计回归模型，此方法降低了误检率，且降低了计算成本。T-KNN作为一种经典的统计模式识别方法，识别主要靠待检测数据周围的临近样本，因此在类别区域边界的交叉部分或数据量较大时存在过多的噪声数据［5］会对样本检测准确性产生影响，为了提高分类性能，可以使用给噪声数据较小的隶属度与加权投票等方法，对训练样本及分类器做一定的优化，本文提出了一种基于KNN算法的改进KNN算法（improved k-nearest neighbor，I-KNN）。1 数据检测模型该数据检测模型主要由2个部分组成。第一部分：由于目前财政预算请求都是通过XML格式的报文进行信息传递，首先需要在财政端传递的报文中，遍历其节点获取其中的文本信息［6］，将XML处理成待检测数据文本集。第二部分：确定训练文本集之前，由于噪声数据一般分布于类边界，故使用Chen等［7］提出的基于密度的快速密度峰值搜索算法进行类簇分类，然后根据Du等［8］提出的不对称边界变精度粗糙集模型，筛选出噪声数据，最后给予噪声数据一个较小的隶属度以减小噪声数据对后续检测的影响，确定了训练文本集后，就可对财政预算请求待检测文本进行检测，本文主要介绍第二部分。2 改进的KNN预警检测方法2.1 训练集预处理检测系统的性能通常由其稳定性、准确性、快速性来判断，而财政系统的预算请求数据的预警功能，其准确性更是成了重中之重。该检测方法的财政请求预警类别训练集中的类别越平均，内容越全面，其检测的准确性就越高。首先将训练样本数据进行类簇处理找出它的类簇中心点［9］，然后对距离类簇中心点过远的噪声数据进行预处理。假设[T={(xi,ci)| i=1,?,N}]为某请求预算报文处理后所得到的训练文本集，其中N是该样本的个数，[ci]为[xi]的检测类别。首先将该文本集进行聚类分类，找出它的类簇中心点，而类簇中心点一般具有以下2个特点：类簇中心被一群密度较低的临近点包围；类簇中心离其他具有更高的局部密度的点距离都较大。根据这2个特点，以类别分类的各类簇中心应该同时具有较大的局部密度和相对距离，要确定数据集各类簇中心，对于每个数据点都要计算它的局部密度[ρi]和距离[δi]。局部密度的定义如下：[ρi=j∈S,j≠iχ(dij-dc)] （1）[χ(x)=1,x＜00,x≥0] （2）其中，S代表整个数据集，[dc]是截断距离，式(1)需要先设置好截断值[dc]，而[dc]的值通常选取所有点之间的相互距离升序前2%，[dij]是点i到点j的欧式距离，其定义如式（3）所示。[dij=k=1n(xik-xjk)2] （3）距离参数如式（4）所示：[δi=max{d(i,j) j∈S}min{d(i,j) ρi＜j∈S}] （4）在待检测的训练集内选取[ρi]与[δi]都较大的点作为类簇中心点，即[λi=ρi·δi] （5）在确定了所有类的类簇中心点，其余待检测训练集中的点会根据局部密度［10］进行点的排序，从而得到密度点集合G。[density(xi)=j=1k1minpijk=1l-1αd(xk,xk+1)-1] （6）其中，[pi]=为密度参数，[pij]为类簇中心与待测试样本之间的所有路径，[l]为连接样本点与类簇中心点间的训练样本的个数，[dxk,xk+1]为[xk]与[xk+1]之间的欧式距离。在选择出所有的类簇中心后，剩下的样本点会分配给局部密度大于该样本点本身且与之距离最近的点所在的类簇。将训练集以类分簇后，就可以根据式（7）确定噪声数据，当样本[T]中的训练样本点到类簇中心的距离[dλi,xi]大于R，则该样本点为噪声数据。[R=xj-a,xj满足max[|density(xj)-density(xj+1)|]≤ε] （7）其中[j≤N-1，density(x_j)∈G, ε]为调节阈值，a为样本中心点。最后根据式（8）计算T样本中的训练样本的隶属度，并给予噪声数据一个较小的隶属度。[μ(x)=0.7×1-d(xj,λj)R1+d(xi,λi)R+0.3,d(xi,λi)∈R0.3×11+(d(a,xi)-R), d(xi,λi)≥R] （8）通过对T的预处理后得到的预警类别训练集[D=[xi,ci,μ(xi)]| i=1,?,N。]2.2 预警类别特征加权当训练集的类别点分布不均匀时，每个待检测样本在寻找其K个近邻点时会更趋向于测试集样本中数量最多的那个类别。如果使用传统的T-KNN算法除了数量最多的那个类别，其他类别的准确率都会不同程度降低。所以采取对文本内的样本点进行加权的方式，来降低样本分布不均匀时产生的分类准确率的影响。加权的步骤如下：1）在进行了预处理的集合D中，将训练样本归一化，根据特征值找出能代表集合D的特征向量。本方法中使用K近邻中类别的平均文本值作为理想向量［11］。其权重的修正公式为[Hi=1[1+Num(Ci)/Avgnum(Cl)]1tt＞0] （9）式（9）中[NumCi]为K近邻中属于[Ci]的文本数量，[AvgnumCl]为平均文本数。2）根据加权方法［12-13］，可以通过确定每个特征的权值来确定最终的分类[p(Jj,ci)=j=1kHi*sim(Ji,Jj)*y(Jj,ci)] （10）式（10）中[Ji]为待检测文本的特征向量，[simJi,Jj]为计算相似度公式，[Hi]为待检测样本的类别权重。如果待测试文本属于[Ci]，则函数y为1，否则为0。2.3 确定训练样本针对计算的数据量大，数据源多等特点，本文根据财政预算绩效制定的预算使用规则进行树结构分层［14］，减少计算量，具体步骤为：1）根据财政专业知识将预警类别分类为n层树状结构。对于前n-1层中，判断每个类型中与待检测样本最邻近的个节点的预警类型是否存在子节点，若存在则加入子节点一起作为训练样本，若不存在则直接进入预警类型的下一层。2）引入上下近似区域［15］计算方法，设置上述分层遍历后的训练样本集中存在的m个类簇，其类簇中心点在预处理时已经得出，然后计算类簇中心点与该类别的所有样本的相似度，取最小值作为上近似半径。再将相似度大于隶属度R的样本中的点与类簇中心最近的距离作为下近似区域。3）确定各预处理后的类别的上下近似区域。2.4 确定待检测数据的类别在确定较为准确的训练集后，就可以进行检测了。具体步骤如下：1）对于一个待检测文本集，根据它的特征词形成待检测文本向量。2）依次计算待检测文本集与n层训练集中的每个文本的相似度。3）文本相似度的计算公式为：[sim(Ji,J1j)=k=1MWik×W1jkk=1MW2ikk=1MW21jk] （11）式（11）中，[Ji]为测试文本的特征向量；[Jj1]为1层[j]类的中心向量；[M]为特征向量的维数；[Wik]为第i个向量的第K维。K的值根据实验结果的准确度进行调整。4）在对待检测文本的数据经过加权以后，通过式（10）来确定待检测文本中的各个点的类别是否属于下近似区域内，如果是则直接归入该类，如果不是则判断为未知可疑类别的财政预算请求。3 结果与讨论3.1 数据准备本实验使用湖北省某国库支付代理银行2019年上半年的财政报文请求数据中存在不同类别的预警数据共计18 000份。为清晰实验过程，本实验将请求报文节点分类为3层树结构。实验检测准确性的评估指标［16］一般以真正类率（true positive rate，TPR），真负类率（true negative rate，TNR）来作为评估参考。[Apr=TP+F] （12）[Cnr=NN+P] （13）其中，[Apr]即被检测为正常无预警类别的样本占所有正常样本的比例。[Cnr]是指被检测为存在相应预警类型的样本占所有含预警类型样本的比例。T为正常无预警类别的样本数，N为存在预警类型的样本数，F为存在预警类型的正常样本数，P为所有正常样本中含预警类型的样本数。3.2 准确率分析本实验从报文中选取产品预警类型1 500份（包括产品型号可疑样本700份，产品个数可疑样本800份），收款方可疑类型1 500份（包括收款人可疑样本700份，收款公司可疑样本800份），金额可疑类型1 500份以及1 500个正常报文样本作为训练样本，训练样本总量为6 000份，然后使用包含各个可疑类型样本12 000份作为待检测数据，近邻样本个数k=16，图1为T-KNN算法与I-KNN的真正类率（TPR）与真负类率（TNR）检测准确度的比较结果。从上述实验中可以看出，从[Apr]与[Cnr]的准确率来看，改进后的I-KNN算法均比传统的T-KNN算法有一定程度的提高，在样本数量较小的时候增幅不是很明显，但在样本数量增加以后，I-KNN较之于传统T-KNN算法的真正类率（TPR）由86.1%提升到88.9%，真负类率（TNR）由85.3%提升到88.4%。综上所述，I-KNN在分类准确率上的改进有效。3.3 检测时间分析将12 000份报文作为速度检测样本均分为3份，每份4 000个样本，分别为Dataset1，Dataset2，Dataset3，并使用T-KNN算法与I-KNN算法分别记录其分类时间，如表1所示。表1 分类时间比较 Tab.1 Comparison of classification times ms[速度检测样本\&T-KNN\&I-KNN\&Dataset 1\&3 233.7\&1 847.6\&Dataset 2\&3 144.9\&1 977.3\&Dataset 3\&3 197.4\&1 924.1\&]从表1可以看出：3份数据集在检测时间上I-KNN算法比传统的T-KNN算法均缩短了大约40%，本文提出的I-KNN算法在检测时间上明显优于T-KNN算法。4 结 论本文提出的将传统KNN的改进算法应用于数据量较大的财政预算请求检测中，通过给予噪声数据更小的隶属度和权重，使检测结果更加精确，同时对训练集在一定的规则下分层为树结构，简化了检测的时间。由实验可以看出，I-KNN是一种检测准确率较高、分类速度较快的报文分类算法，对识别财政资金的性质和分类有一定的应用价值。但是由于该方法的分类类别需要人为去维护，后续将进一步改进本方法的不足之处。