K值确定方法

2024-08-05

K值确定方法（精选3篇）

K值确定方法篇1

0 引言

KNN分类算法[1]是机器学习领域的一个经典算法,该算法简单、易于实现,被列为数据挖掘十大算法之一[2]。KNN是一种基于实例的学习算法,它的分类原理是寻找与被预测对象最相似的K个对象—邻居,由邻居确定被预测对象的类别。K值决定了邻居的个数,进一步决定了密度估计的平滑度,它的取值是一个重要的问题[3]。如果值取得过小,则算法易受噪声的影响,使分类结果不稳定;值取得过大,则模型偏向于将预测对象为类别数量多的一类。同时,过大的K值也增加了算法的时间复杂度。

前人有很多工作研究了最优K值选择的问题。文献[4,5]从理论上说明当邻居距离使用的是欧式距离的时候,K的选择应该遵循原则:k→∞,k/n→0,这个理论对小样本数据并不适用。文献[6,7]使用交叉验证的方式评估取得最小错误率的K值作为最优K值。这种方式是目前普遍使用的方法,它的计算复杂性较大,存在多值性,难以取舍。

文献[8]指出,为了确保分类正确,近邻集中至少有n+1个实例来自正确的类别,因此建议K=2n+1。文献[9]提出一个基于样本个数、问题空间维度、内在概率分布的函数用于预测最优K值。文献[10]先在数据集上进行聚类,进而对不同的簇使用不同的K值,但需要提前指定簇的数目值。文献[11]指出了最优值的取值范围为,利用重复计算的方法进一步确定K值。文献[12]指出不平衡二分类问题中两个类别下邻居个数K和错误率存在非单调关系,并研究了K值选择问题,但是没有给出具体取K值的方法。文献[13]利用统计置信度来选择K值,并且根据局部统计特征调整每个样本的K值。文献[14]根据数据分布使用不同的值,这种动态求值的方法极大地增加了算法的时间开销。文献[15]考虑泊松分布和二项分布下的KNN算法K值选择。文献[16]首先从训练集中选择一个子集,然后在该子集上应用KNN,该方法缩减了训练集,没有充分利用训练集的信息。文献[17]分析最优K值分布规律的基础上,采取压缩候选K值的范围的方法来快速寻找最优K值。该方法在压缩候选K值范围的时候,用到交叉验证的方式确定KNN算法在数据集上的精度,对大规模数据集不太适用。

模型的精度、参数本质上是由数据集本身的特征决定的。文献[18]利用各种数据集构建元数据建立回归模型对算法精度进行预测并取得较好效果。借鉴文献[18]的思想,利用已有数据集的先验知识,提取数据集的特征直接预测KNN算法中的参数K值。对UCI公共数据集[19]的特征进行度量,利用线性回归模型建立数据集特征和最优K值之间的模型。对新的数据集提取相应的特征,利用训练好的回归模型对最优K值进行预测。该方法在UCI120个数据集测试上取得理想结果,能在短时间内预测出KNN算法的最优K值。

1 算法精度与数据集的关系

文献[17]通过分析UCI上的五个数据集(sick、labor、pima、iono和vechicle)的K值与精度变化曲线指出KNN算法的精度会随着K值呈现一定规律变化。K值从1开始逐渐增大的过程中,精度会出现一定的抖动,之后会出现平稳的下降趋势。并分析了上述规律的主要原因:K较小时候,精度会受到噪声的很大影响;当K较大的时候,精度会受到多数类别样本的影响。不同的数据集由于数据分布、噪声点、离群点、属性类别等不一样,参数K的取值也不一样。文献[20]指出影响模型精度的原因是数据集本身的特征,他们用数据集上提取的特征向量预测各个模型的精度,并取得较好效果。

图1是UCI数据集中任意挑选的20个数据集在十种分类算法下的精度表现,参数为weka(http://www.cs.waikato.ac.nz/ml/weka/)的默认参数。同时计算了每个数据集对应各个算法的精度平均值、方差以及KNN算法最优K值,这里的最优K值是通过十折交叉验证的方式取得精度最高对应的K值。

表1列举了部分数据集的算法精度值,从表1可以看出,每个数据集在各种算法上的精度表现都有一定规律性。比如:数据集horse-colic的精度在0.8附近,最小值为0.75(KStar),最大值0.856(PART、C4.5)。此数据集在基于实例的算法,3NN和KStar的精度都不如基于树规则的C4.5、PART算法。这本质上是由于数据集的数据分布规律和特征决定的。同样,KNN算法中,最优K值是和数据集的特征紧密联系的,数据集的特征决定了各个分类器的精度以及最优K值。寻找到合适的数据集特征来刻画数据集,就能有效地预测算法的精度以及最优K值。

2 数据集与最优K值预测

2.1 数据集的刻画

刻画数据集的方法,可以分为六个方面:简单特征[21]、统计特征[22]、基于信息熵的特征[23]、基于模型的特征[24]、基于地标算法精度的特征[25]、基于数据集复杂性的特征[26]。这些数据集特征的详细内容如下:

1)简单特征:样本数量、类别数量、特征数量、类别型特征的数量、数值型特征的数量、类别型特征的比例、数值型特征个数比例、维度比。

2)统计特征:峰度、偏度、典型相关分析、特征值、最大关联系数。

3)信息熵:标准化类别信息熵、标注化类别平均信息熵、联合信息熵、互信息、信噪比、信息熵度量下的等同特征数目。计算公式如下:

其中,X是属性变量,Y是类别量,p(x)是属性变量X的概率分布。Joint Entropy是联合熵,Mutual Inf(X,Y)是属性和类别的互信息,Class Entropy是类别熵,Atts Entropy是属性熵。

4)基于决策树的特征:构建一棵没有剪枝的决策树,关于这棵决策树的很多统计量作为特征。用到的统计量是叶节点的个数、节点的个数、每个特征的平均节点数、每个样本的平均节点数。利用决策树来判别数据集相似性的原理是认为相似的数据集会产生的决策树有相似的结构。图2是决策树的统计特征示意图。

决策树指标的提取,包括树的宽度、高度、层数、分支数目、属性使用次数等,都是以图2所示的决策树作为基础。

5)简单算法精度特征:简单分类器的精度,比如:朴素贝叶斯算法、线性判别、1NN。简单分类器的精度表现能在一定程度上反映数据集的特征。

6)数据复杂性指标:特征最大Fisher判别率、类别间重合比例、最大单特征分类效率、联合特征分类效率、类别重合率、边界比例、边界点不同类别比例、属性纯净度等。这些指标的具体定义的详细介绍见文献[26]。其中属性纯净度的概念是针对离散型数据集,它用来定义数据集中的属性对类别的区别能力大小,计算公式如下:

定义数据集的总的纯净度为:

首先定义属性的每个属性值的纯净度为对应属性值vi的样本在各个类别下的分布的混乱程度,也就是对应该分布的信息熵,见式(5)。属性f是类别型属性,设f有m个属性值{v1,v2,…,vm},样本取值为属性值vk的个数为|vk|,式(5)中的pkj为样本在特征f下取值为vk且属于第j类的样本概率。Purej指的是第j个特征的纯净度,见式(6),它是每个属性值纯净度的加权和。数据集E的纯净度定义为所有特征纯净度的最小值,见式(7)。

前人利用数据集的特征在算法选择问题上做了很多工作。比如:用于模型选择[27]、用于模型参数确定[28]、样本选择[29]。

2.2 影响KNN算法精度的指标

文献[18]指出类别个数、峰度、联合熵、相当于类别属性信息熵的属性数量、互信息、决策树的宽度、宽度均值、宽度方差、1NN、C4.5、NB(朴素贝叶斯算法)等特征对KNN算法的精度有较大影响。同时,为了保证计算效率,文中只选择部分数据集特征作为预测K值的特征。选择的特征的复杂度要小于O(N×|D|×log|D|)。

数据集属性可能是数值型或者类别型的,计算数据集的特征向量会涉及到属性类型的转化。数值型数据离散化有基于信息熵的MDLP算法、频率等;类别型数据数值化一般采取的是二进制的方法。实际运用算法过程中,一般将连续数据离散化,而较少将类别数据数值化。因此本文使用的数据集特征向量的提取指标中不考虑只针对数值型数据的指标。例如:去掉了峰度、偏度等指标。这样避免了由于数据类型之间的转化对结果造成影响。而对于混合型数据集,在计算类别型指标的时候就要先将连续数据离散化,离散化方法采取的最后选择的用于预测KNN算法最优K值的数据集特征如表2所示。

2.3 最优K值预测流程

算法流程为首先提取每个数据集的特征向量,以及在十折交叉验证下的最优K值。最优K值的求取采取穷举的方法。如果用交叉验证方式评价的最优K值有多个,则选择较小的K值。利用特征向量和K值构成训练样本,采取线性回归模型建立模型。最后,对新的数据集预测最优K值。具体流程如图3所示。

利用特征向量和K值构成的训练样本构建线性回归模型,利用weka(http://www.cs.waikato.ac.nz/ml/weka/)自带的线性回归算法进行建模。特征向量的计算指标都是复杂性在O(N×|D|×log|D|)内的,而且避免了多次交叉验证求取最优K值,因此该方法预测K值是有意义的。对于新样本,首先提取该数据集的特征,然后利用训练好的模型预测出K值。

预测模型的建立有很多种选择,可以使用神经网络、决策树、KNN算法、支持向量机等。本文仅以线性回归模型为例进行说明。处理具体应用的数据集的时候,可以选择本领域的大量数据集作为历史数据集。根据机器学习理论,更具有代表性的、更多的历史数据集的积累会改善机器学习的准确性。本文实验以来自网络的公开的加州大学欧文分校的机器学习数据库[19]为例进行说明,实验结果证明了该方法的有效性。

3 实验

3.1 数据集

数据集来自加州大学欧文分校公开的机器学习数据库。选取其中120个分类型数据集作为本实验的数据来源,涉及计算机工程、生命科学、物理科学、社会生活、电子商务以及游戏等领域。数据集的实例个数分布在14到20 000个;属性个数分布在3到101个;类别个数分布在2到28个。这些都是数据集的表面特征,取更大的范围能保证本文方法的适用性。

3.2 评价指标

本文提出的方法在计算复杂度上远远低于重复多次的十次交叉验证方法。为了支持这一结论,本文在评价指标中加入了算法性能指标。

其次预测的K值与最优K值的差距是算法效果的直接体现。为了计算预测的K值与最优K值的距离,要计算数据在这两个K值下的精度差距。借鉴文献[17]采用的三个评价指标:

1)MAE(magnitude of absolute error)表示推荐的值对应的分类精度(预测精度)与最优对应的分类精度(最优精度)的绝对误差,即MAE=(最优精度-预测精度)×100%。

2)MRE(magnitude of relative error)表示预测精度与最优精度之间的相对误差,即MRE=(最优精度-预测精度)÷最优精度×100%。对于MAE和MRE,它们的值越小表示预测精度越接近最优精度,意味着算法效果越好。

3)PRED(·)是另一个常用的评价指标。PRED(m)表示MAE小于m%的数据集个数占总预测数据集个数的百分比;最优的K和预测出来的K值对应精度的差别在5%之内就认为是不错的结果。

3.3 实验结果与分析

3.3.1 算法性能测试

算法的性能测试,测试环境是:CPU是Intel core i5 duo3.2 GHz,内存4 GB。

实验目的是测试算法的运行效率,选择了120个数据集进行对比测试。表3显示了部分数据集的在最优K值预测算法运行时间、文献[17]提出的压缩K值范围的算法时间、使用多次交叉验证算法运行的时间。K值的初始范围为1~log N,文献[17]的算法的是进一步压缩了K值范围为1~log(log N)。由表3可以看出,本文使用的算法的运行效率明显高于多次交叉验证算法的运行效率。当数据集的样本个数较大的情况下,差异越是明显。

3.3.2 算法效果

根据选择的120个数据集特征以及最优K值构成的训练样本,利用分层抽样的办法选择其中60个数据集作为训练集,总的120个数据集作为测试集。此模型只是在有限的历史数据集中学习得到的案例,不能直接使用到任意应用领域中。为了说明实验的有效性,本文给出了实验得到的回归模型如图4所示。

可以看到的是,指标属性个数比例(Rate Ofnumeric Att以及Rate Of Nominal Att)、简单算法精度(C4.5、NB、1NN)以及基于未剪枝决策树的统计量(树高-treeheight、最长分支-Long Branch)等对回归模型影响较大。用预测的K值与最优K值对应的KNN算法精度衡量本方法的效果。部分数据集的在两个K值下的精度偏差,如表4所示。

表5统计了120个数据集上MAE和MRE的最小值(min)、最大值(max)、中位数(median)、众数(mode)、平均值(mean)和标准差(std),并给出了PRED(m)的值。

从表5可以看出有86.13%的数据集的预测K值精度与最优K值对应精度的绝对偏差在5%范围内。此结果与文献[17]对比,预测准确率要低于94%,但是本方法避免了多次交叉验证即可求取最优K值,因此在速度上更优。

4 结语

本文针对KNN算法中近邻数的确定问题进行了研究。不同于从交叉验证方式、概率分布角度、快速搜索方式求取K值,本文从数据集特征的角度直接预测最优K值。在120个公开数据集上的实验结果表明了该算法的运行效率高,实验效果较好。实验过程中算法采取的回归模型能很好地预测未知数据集最优K值,为快速确定模型参数提供了新的方法。虽然本方法预测模型参数取得较快速度,但是在精度上有所损失,只有86%的数据集能确保精度误差在5%范围内。

计算众多数据集特征影响模型参数会影响预测性能,进一步筛选有效、可用的数据集特征是下一步的工作。另外,数据集特征对模型多参数的预测、模型的选择是下一步要研究的工作。

摘要：KNN算法中的参数K的选择一般采取多次交叉验证方法求取,数据规模较大时并不适用。同时,影响参数选择最根本的因素是数据集本身。因此,提出利用数据集本身的特征预测最优K值的方法。首先提取历史数据集的简单特征、统计特征、信息熵特征、简单算法精度特征、复杂度特征等构建特征向量,然后利用线性回归、神经网络等方法建立特征向量与最优K值之间的预测模型,并用该模型预测新数据集的最优K值。在UCI数据集上的实验表明,该方法能迅速预测最优K值,并确保一定的精度。

关键词：KNN分类算法,数据集特征,信息熵,最优K

浅述未投产气井危险值的确定方法篇2

未投产气井是指那些因为各种原因暂未投入生产的探资井和开发井,这些气井虽然没有投入生产,却也需要时常巡查、维护保养,否则容易出现人为破坏、腐蚀等问题,进而发展成为天然气从井口渗漏等较危险的情况。问题一旦出现,就需要企业拿出大量的人力、物力来控制和消除。因此,做好未投产气井的巡查、维护工作,把天然气泄漏等安全隐患发生的可能性彻底消除,这对于未投产气井的管理工作和企业的安全生产工作来说意义非常的巨大。为此,提出对这些气井进行分类管理,提出科学合理的分类方法,计算出每口气井的危险值,为分类管理提供直观可参考的依据。

1 影响未投产气井安全的重要因素

影响未投产井安全的因素很多,总结起来主要有以下几点因素。

1.1 井口装置维护现状

未投产井由于没有生产,井位一般较为偏远,因此维护保养的力度远远跟不上生产井。这就导致许多井有腐蚀、密封脂失效等情况出现,一旦出现这样的问题,下一步很有可能就会发展成井底天然气从井口泄漏的情况。因此每两年对未投产气井井口装置进行防腐处理,对连接法兰螺栓作预紧维护,对油管头BT密封进行补塑(注特氟隆)保养是非常必要的。

1.2 固井质量

固井质量的好坏是保证一口气井能否长期安全的重要指标,如果固井质量不好,则可能会有表层套管、技术套管带压等安全隐患出现。根据我们对目前未投产气井固井报告的分析,我们发现目前气井的固井质量大致可以分为合格、暂定合格、部分井段不合格和不合格几大类。

1.3 最大试气量

最大试气量是指天然气井在试油试气阶段测出的日最大产气量,该项指标是天然气井日后是否投产的重要参考依据,同时做好高产气井的维护工作也是探资队管理工作的重中之重。根据我们对目前未投产气井最大试气量的分析,按试气量的大小,可以大致分为以下几类:最大试气量大于10×104m3;最大试气量在5×104m3～10×104m3之间;最大试气量在1×104m3～5×104m3之间;最大试气量在1×103m3～1×104m3之间;最大试气量在1×103m3以下。

1.4 地层压力

对未投产气井压力的监测是探资队巡井的重要任务之一,及时准确的掌握气井压力变化有助于对整个气田开发进行动态研究和防范气井意外事故发生。因为地层压力和气井井筒压力有一定的关系,在不知道大部分未投产气井井筒压力的情况下,我们根据对目前未投产气井地层压力的分析,按地层压力大小,可以大致分为以下几类:地层压力在50 MPa以上;地层压力在30 MPa～50 MPa之间;地层压力在30 MPa以下。

1.5 气井周边情况

未投产气井由于没有投入生产,气井井场周边情况不能及时了解和掌握,经常会有人为的有意或无意的严重影响气井安全的行为出现。在这里本文把气井周边情况大致分为草原和农用地,草原中的气井受到人为的影响少,农用地中的气井则会较多一些。

2 未投产气井危险值概念的公式化表述

由上面的叙述可知,影响气井安全的主要因素有5个方面,这些因素对气井安全的影响大小也各有不同。在这里,为了更直观的评价一口井目前存在的危险性的大小,将5个方面的因素整合成一个概念,即“未投产气井危险值”。未投产气井危险值的定义是影响气井安全的主要因素的量化叠加。公式表述如下:

其中:S—未投产气井危险值;W—井口装置维护现状;G—固井质量;Z—最大试气量;D—地层压力;J—气井周边情况。

根据现场实际巡井经验和以往事故气井事故原因分析总结,影响未投产气井安全的5大因素在未投产气井危险值中占的比重如下:W—30%,G—20%,Z—20%,D—15%,J—15%。如果按百分制来计算未投产气井危险值S的大小,那么井口装置维护现状W的波动范围是0≤W≤30,井口装置维护现状越差,则W值越大。以此类推0≤G≤20,0≤Z≤20,0≤D≤15,0≤J≤15。每种因素的细化分类评分办法如下表1。

3 危险值概念在实际工作中的应用效果分析

对于探资队来说,巡井和气井维护就是他们的主要工作,也只有这些工作做到位了,才能保证未投产井的安全。然而,如果探资队对这所有未投产气井不分轻重地去管理,不但工作量太大,也没有抓住工作的重点,有些工作就失去了意义。因此,有必要对这些气井分门别类的进行管理。

在这里,将利用上文中提出的气井危险值的概念来实现对这些气井的分类管理。首先根据未投产气井危险值的计算公式,计算出每口井的危险值,再按照这些值的大小把所有的未投产井分成几大类,分类情况如下表2所示:

在巡井计划的制定过程中,可以参考上表所列的每口井的危险值,制定适合该井的巡井计划,建议A类井需要每天巡查,B类15 d巡一次,C类井一个月巡一次,D类井3个月巡一次,E类井6个月巡一次,F类井一年巡一次。

通过这样分类,探资队就能将巡井工作安排的科学合理、主次分明,同时为探资队节省人力物力和排除可能存在的安全隐患提供积极帮助。

另外,为了在实际工作中更为有效地利用未投产气井危险值这个概念来帮助探资队将未投产气井维护工作做的更好,本文提出设计一个气井危险值评估单,通过该评估单对每口井进行定期评估并存档。下面以某井为例来说明气井危险值评估单的内容和用途,见表3。

4 结语

目前的未投产气井由于位置偏远,井数多,巡井人员少,因此要做好每一口井的维护保养工作难度较大。影响未投产气井安全的因素较多,主要有五个方面的因素,即井口装置维护现状、固井质量、最大试气量、地层压力、井口周边环境。未投产气井危险值是对未投产气井存在安全隐患的定量表述,能较好的帮助技术人员制定科学合理的巡井计划,指导巡井人员在巡井过程中及时排除安全隐患。