面向K-近邻学习模型的高效数据清洗框架.pdf
《面向K-近邻学习模型的高效数据清洗框架.pdf》由会员分享,可在线阅读,更多相关《面向K-近邻学习模型的高效数据清洗框架.pdf(11页珍藏版)》请在咨信网上搜索。
1、计算机科学与探索Journal of Frontiers of Computer Science and Technology1673-9418/2023/17(09)-2241-11doi:10.3778/j.issn.1673-9418.2207105面向K-近邻学习模型的高效数据清洗框架王婧怡1,陈胤佳2,袁野1+,陈辰1,王国仁11.北京理工大学 计算机学院,北京 1000812.北京航空航天大学 计算机学院,北京 100191+通信作者 E-mail:yuan-摘要:现实世界中收集的数据集通常是含有缺失的,为了在不完备数据集上构建有效的机器学习模型,需要对数据集进行清洗。为了确保较好
2、的清洗效果,通常需要人工参与,从而导致大量成本。确定不完备数据的清洗优先级将有助于减小清洗规模,节约人工成本。而计算不完备数据的清洗优先级应确定其对模型性能的贡献。夏普利值是目前流行的用来评估数据在机器学习模型中贡献的方法,因此可以借助夏普利值的概念计算不完备数据的清洗优先级。由于现有工作缺少对不完备数据夏普利值的研究,首先基于不完备数据集的指数级的所有可能世界定义了一种不完备数据夏普利值的表示方法;然后基于K-近邻分类模型的效用函数,提出了一种多项式时间内计算不完备数据在K-近邻分类模型中夏普利值的近似算法;最后提出了一种基于夏普利值的面向K-近邻分类模型的启发式数据清洗算法ShapClea
3、n。实验表明,该算法在清洗后模型分类准确率方面往往可以明显超过现有的针对机器学习模型的自动清洗算法,而且相比同样需要人工参与的数据清洗算法,该方法具有更高的清洗效率,可以有效节约人工成本,同时保证理想的模型准确度。关键词:不完备数据集;夏普利值;K-近邻(KNN);清洗优先级;数据清洗文献标志码:A中图分类号:TP399Efficient Data Cleaning Framework for K-Nearest Neighbor Learning ModelsWANG Jingyi1,CHEN Yinjia2,YUAN Ye1+,CHEN Chen1,WANG Guoren11.School
4、 of Computer Science&Technology,Beijing Institute of Technology,Beijing 100081,China2.School of Computer Science&Engineering,Beihang University,Beijing 100191,ChinaAbstract:Real-world datasets are often collected with missing data,and in order to build effective machine learningmodels on incomplete
5、datasets,the datasets need to be cleaned.To ensure the quality of the cleaned datasets,humaninvolvement is often required,which incurs considerable costs.Prioritizing the cleaning of incomplete data will helpminimize cleaning scale and save labor costs.Calculating the priority needs determining the
6、contribution of theincomplete data to the performance of the model.Shapley value is a popular method for evaluating the contribution,so it can be used to calculate the cleaning priority.Due to the lack of existing work on Shapley value of incompletedata,a representation of Shapley value of incomplet
7、e data is firstly defined based on the possible worlds of thedatasets.And an approximation algorithm for calculating Shapley value of incomplete data in the K-nearestneighbor classification model in polynomial time is proposed based on the K-nearest neighbor utility.Finally,theShapClean,a heuristic
8、data cleaning algorithm based on Shapley value,is proposed.Experiments show that thealgorithm can often significantly exceed the existing automatic cleaning algorithms in terms of the accuracy.And基金项目:国家自然科学基金(61932004,61732003,U2001211)。This work was supported by the National Natural Science Founda
9、tion of China(61932004,61732003,U2001211).收稿日期:2022-07-29修回日期:2022-10-12开放科学(OSID)Journal of Frontiers of Computer Science and Technology计算机科学与探索2023,17(9)随着计算机科学和商业的发展,机器学习模型已经被广泛应用于各个领域,如金融、空间科学、智慧交通、农业和医学等,并起到了重要的作用。而高质量的数据集通常对机器学习模型的质量起到重要的作用1。然而,现实世界在收集数据的过程中不可避免地会产生一些错误或属性值缺失,使得现实世界的数据集通常具有不一致
10、性和不完整性2,从而对在这些数据集上训练的机器学习模型产生影响。因此,获得高质量的数据集通常是获得高质量机器学习模型的决定性因素。许多机器学习模型都需要从没有属性值缺失的完备数据集上训练得到,为了获得训练数据集,一种方法是丢弃所有不完整的数据样本,只使用完整的数据样本来构建学习模型,但是有限的完整样本可能无法保证机器学习模型的有效性3。为了在不完备数据集上构建有效的机器学习模型,需要处理不完整的数据集,其中重要的步骤包括对缺失的属性值进行填补4,以及去除错误或不相关的数据5等。为了保证清洗后数据的质量,通常需要人工参与,这就直接导致了数据清洗成本的大幅度提高。对于商业公司和组织而言,如何控制处
11、理数据集的成本非常重要,因此研究如何提高数据集清洗的效率具有十分重要的现实意义。为了提高清洗不完备数据集的效率,需要确定数据集中哪些不完备数据更值得被清洗,即不完备数据被清洗的优先级,从而尽可能减小清洗规模,并使清洗后的数据集具有较高的质量。为了达到上述目标,则需要获得不完备数据集中不同数据对模型性能贡献的大小,若某个数据对模型性能具有较大的贡献,则说明该数据对于训练机器学习模型具有较大的价值,应该优先被清洗。因此对于不完备数据集中的每个数据都应该评估在机器学习模型中的价值。评估数据在机器学习模型中的价值可以采用博弈论观点,每个数据都被建模为联盟博弈中的参与者6,而数据在模型中的价值即参与者对
12、联盟的影响可以用模型的效用函数表示。夏普利值(Shapleyvalue)7是合作博弈论中用于分配所有参与者联盟产生的总收益的经典方法,可以有效地解决数据价值评估问题。夏普利值定义了一种合理的价值分配方案,满足公平性、合理性和去中心化性等具有现实意义的良好属性,因此被广泛应用于各个领域。通过计算每个不完备数据在机器学习模型中的夏普利值,就可以有效评估不完备数据在机器学习模型中的价值,从而进一步评估该数据被清洗的优先级。K-近邻(K-nearest neighbor,KNN)分类模型8是在实际应用中最流行的机器学习分类模型之一。KNN分类模型具有结构简单、可解释的优点,这将有助于有效地评估不完备数
13、据对于训练模型的价值。因此,本文提出了一种针对 KNN分类模型的基于不完备数据在模型中夏普利值的数据清洗方法,所面临的主要挑战是:(1)如何定义不完备数据的夏普利值。(2)数据夏普利值的计算是非常困难的。对于完备数据而言通常采用蒙特卡洛采样方法进行近似计算;但对于不完备数据集,每个不完备数据的域是di,其中i=1,2,N。则该数据集可以表示的可能世界数量为|di|,而对于每次采样都需要遍历所有的可能世界,因此即使采用蒙特卡洛采样方法,计算不完备数据夏普利值的时间复杂度仍然是指数级的。(3)如何在不完备数据夏普利值和清洗该数据的优先级之间建立联系。为了解决以上挑战,本文首先基于不完备数据集的所有
14、可能世界定义了一种不完备数据夏普利值的表示方法。然后针对 KNN模型,提出了一种高效的计算不完备数据夏普利值的近似算法。最后提出了一种基于夏普利值的计算不完备数据清洗优先级的启发式算法 ShapClean,可以有效提高清洗不完备数据集的效率,降低人工成本。1基础知识1.1数据夏普利值数据在模型中的价值可以用夏普利值来表示。夏普利值的含义是假设在博弈中对于任意参与者子集组成的联盟加入当前参与者后,联盟财富的边际效用期望即为该参与者的夏普利值9。为了计算数据的夏普利值,可以将每个数据都建模为联盟博弈中的参与者,而数据集中每个数据对当前模型的边compared with data cleaning
15、algorithms that also require human involvement,the ShapClean can save more labourcosts while ensuring the desired model accuracy.Key words:incomplete dataset;Shapley value;K-nearest neighbor(KNN);cleaning priority;data cleaning2242王婧怡 等:面向K-近邻学习模型的高效数据清洗框架际效用可以用该数据加入训练集前后的效用函数之差表示。对于数据集D*=z*1,z*2,z*
16、n,其中任意数据在模型中的夏普利值定义如下:shap(i,D*)=1NS D*z*i1N-1|S|U(Sz*i)-U(S)(1)其中,S D*z*i表示数据集D*除去数据z*i的任意数据子集,效用函数U(S)表示在数据子集S上训练的预测模型的性能得分。根据公式可以直观得到夏普利值将数据z*i的价值归因于z*i对模型效用的边际改进,并对数据集D*的所有可能子集进行平均。数据的夏普利值计算公式还可以被写成如下形式:shap(i,D*)=1N!(D)U(Piz*i)-U(Pi)(2)其中,(D)为数据集D中数据所有可能排序的集合,|(D)|=O(N!),Pi为当前可能排序中先于数据zi的所有数据的集
17、合。该计算方法假设所有数据都将按随机顺序收集,而任意数据z*i在该顺序中的边际贡献即为在已经被收集的数据子集的基础上加入数据z*i带来的模型效用提升。数据z*i的夏普利值则是在所有可能顺序中数据z*i的边际贡献的平均值。1.2KNN分类模型及其效用函数KNN分类模型是一种简单但应用广泛的监督学习模型。对于一个给定的测试集,Jia等人提出了一个针对于KNN分类模型的效用函数,称为KNN效用10。KNN分类模型查找前K个与测试数据最相似的训练数据,并根据其K个最近邻数据的标签判断测试数据的标签。因此,通过计算测试数据的前K最近邻数据中与测试数据标签相同的数量,该效用函数可以直观地衡量KNN分类模型
18、为每个测试数据分配正确标签的可能性。定义1(KNN效用)数据子集S与测试数据t前K相似的数据中,与测试数据t标签相同的数据数量即为S对于t的KNN效用。如下:U(S)=1Kk=1minK,|S|Iztk.y=t.y(3)其中,ztk代表数据子集S中第k邻近测试数据t的数据,y代表该数据的标签,I为指示函数,若括号内等式成立则返回1,否则返回0。通过使用 KNN效用函数,可以实现一种有效计算不完备数据在KNN分类模型中夏普利值的方法。2KNN模型中不完备数据夏普利值计算本章将阐述KNN模型中不完备数据夏普利值的计算方法。首先将给出不完备数据夏普利值的定义,并证明其计算复杂度,然后提出一种能够高效
19、计算KNN模型中不完备数据夏普利值的近似算法。表1对所常用到的一些符号的意义进行了简要说明。2.1不完备数据夏普利值的定义不完备数据集D=z1,z2,zN可以用关系型数据库中的一个表来表示,该表中每个元组代表一个不完备数据,不完备数据zi的候选值域为di,|di|=Mi,其中i=1,2,N,Mi的大小满足O(M),则该表可以表示的可能世界数量为|di|。本文只考虑不完备数据缺失的属性值较少即M较小的情况。图1展示了一个不完备数据集的候选值实例。假设其中z1和z3的缺失属性为类别类型。对于z1可以选取z2、z3中该属性的值进行填补,生成候选值z1,1和z1,2;对于z3可以选取z1、z2中该属性
20、的值进行填补,生成候选值z3,1和z3,2。各候选值与测试数据t的相似度如图1中所示。表1常用符号表示及其含义Table 1Commonly used labels and meanings名称Dzizi,mdiMSU(S)tyztkwWNNtest(D)PiTop(K,w,t)BBCscnf,hT描述不完备数据集训练数据训练数据zi的候选值不完备数据候选值域不完备数据候选值域的大小数据子集数据子集S的效用测试数据数据标签第k邻近测试数据t的数据可能世界可能世界集合训练数据集大小测试数据集大小数据集中数据的可能排序数据集D中数据所有排序的集合中先于zi的所有数据的集合w中与t前K相似数据实例的
21、集合边界集边界集的大小相似度低于zf,h的zn候选值数量Monte Carlo采样数量2243Journal of Frontiers of Computer Science and Technology计算机科学与探索2023,17(9)完备数据集中数据z*i的夏普利值代表该数据在所有子集S D*z*i上的平均边际贡献,如式(1)所示,其中数据z*i边际贡献即在Szi和S上训练的预测模型的性能得分之差。而对于不完备的数据集,数据zi的边际贡献为所有可能世界W中在Szi和S上训练的预测模型性能得分之差的期望。通常可以为属性域中每个候选值是真实值的可能性设置相同的先验概率11,因此计算期望时只要
22、取平均值即可,第 4章中的实验也表明该方式可以在数据清洗中达到较好的效果。定义2(不完备数据夏普利值)在不完备数据集D的所有可能世界中,zi对于在去除不完备数据zi的任意子集S训练的机器学习模型的边际效用平均值即为该不完备数据的夏普利值,如式(4)所示:shap(i,D)=1N|W|w WS Dzi1N-1|S|U(Sw(zi)-U(S)(4)对于完备数据,目前已有的研究成果可以在多项式时间内准确计算完备数据在KNN模型中的夏普利值10。该方法首先对训练集中的数据按与测试数据t的相似度进行排序,得到zt1,zt2,ztN,其中zti代表训练集中第i邻近测试数据t的数据。然后根据以下递推公式计算
23、准确的夏普利值:shaptN=IztN.y=t.yN(5)shapti=shapti+1+Izti.y=t.y-Izti+1.y=t.yKminK,ii(6)其中,shapti代表训练集中第i邻近测试数据t的数据的夏普利值。对于不完备数据集D=zi,z2,zN,其中不完备数据zi的域为di,|di|=Mi,不完备数据zi的所有候选值的集合为zi,m,其中m=1,2,Mi。用上述方法计算不完备数据zi的夏普利值,其中w(zi)=zi,m代表在可能世界w中不完备数据zi的值为候选值zi,m,ztj=zi代表训练集中第j邻近测试数据t的数据为zi,计算过程如下:shap(i,D)=1|W|m=1Mi
24、j=1Nw W,w(zi)=zi,m,ztj=zishaptj(7)该方法需要确定每个可能世界中各数据按与测试数据的相似度排序的顺序,而所有可能世界的数量为|di|,因此采用该方法计算不完备数据在KNN模型中的准确夏普利值仍然是困难的。而根据定义 2中不完备数据夏普利值的定义直接计算需要遍历该不完备数据集数量为|di|的所有可能世界和2N个可能的数据子集,因此难以计算不完备数据在KNN模型中的准确夏普利值。因此,需要考虑计算不完备数据在 KNN模型中夏普利值的高效近似算法。2.2不完备数据夏普利值近似计算根据计算完备数据夏普利值的式(2),计算不完备数据夏普利值的式(4)还可以写成如式(8)的
25、形式:shap(i,D)=1N!|W(D)w WU(Piw(zi)-U(Pi)(8)其中,(D)为D中数据所有可能排序的集合,Pi为当前可能排序中先于数据zi的所有数据的集合,w(zi)代表不完备数据zi在可能世界w中的取值。对于不完备数据集D=z1,z2,zN,训练数据集S D的效用函数U(S)则表示在所有的可能世界中训练的预测模型的性能得分的平均值。根据 1.2 节的论述,预测模型的性能得分取决于测试数据的前K最近邻数据中与测试数据标签相同的数量,因此对于测试数据集Dtest=t1,t2,tNtest,效用函数可以被写成如下形式:U(S)=1NtestKj=1Ntestk=1minK,|S
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 面向 近邻 学习 模型 高效 数据 清洗 框架
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。