面向K-近邻学习模型的高效数据清洗框架.pdf

计算机科学与探索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-摘要：现实世界中收集的数据集通常是含有缺失的，为了在不完备数据集上构建有效的机器学习模型，需要对数据集进行清洗。为了确保较好的清洗效果，通常需要人工参与，从而导致大量成本。确定不完备数据的清洗优先级将有助于减小清洗规模，节约人工成本。而计算不完备数据的清洗优先级应确定其对模型性能的贡献。夏普利值是目前流行的用来评估数据在机器学习模型中贡献的方法，因此可以借助夏普利值的概念计算不完备数据的清洗优先级。由于现有工作缺少对不完备数据夏普利值的研究，首先基于不完备数据集的指数级的所有可能世界定义了一种不完备数据夏普利值的表示方法；然后基于K-近邻分类模型的效用函数，提出了一种多项式时间内计算不完备数据在K-近邻分类模型中夏普利值的近似算法；最后提出了一种基于夏普利值的面向K-近邻分类模型的启发式数据清洗算法ShapClean。实验表明，该算法在清洗后模型分类准确率方面往往可以明显超过现有的针对机器学习模型的自动清洗算法，而且相比同样需要人工参与的数据清洗算法，该方法具有更高的清洗效率，可以有效节约人工成本，同时保证理想的模型准确度。关键词：不完备数据集；夏普利值；K-近邻（KNN）；清洗优先级；数据清洗文献标志码：A中图分类号：TP399Efficient Data Cleaning Framework for K-Nearest Neighbor Learning ModelsWANG Jingyi1,CHEN Yinjia2,YUAN Ye1+,CHEN Chen1,WANG Guoren11.School 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 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 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 incomplete 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 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 Foundation of China(61932004,61732003,U2001211).收稿日期：2022-07-29修回日期：2022-10-12开放科学(OSID)Journal of Frontiers of Computer Science and Technology计算机科学与探索2023,17(9)随着计算机科学和商业的发展，机器学习模型已经被广泛应用于各个领域，如金融、空间科学、智慧交通、农业和医学等，并起到了重要的作用。而高质量的数据集通常对机器学习模型的质量起到重要的作用1。然而，现实世界在收集数据的过程中不可避免地会产生一些错误或属性值缺失，使得现实世界的数据集通常具有不一致性和不完整性2，从而对在这些数据集上训练的机器学习模型产生影响。因此，获得高质量的数据集通常是获得高质量机器学习模型的决定性因素。许多机器学习模型都需要从没有属性值缺失的完备数据集上训练得到，为了获得训练数据集，一种方法是丢弃所有不完整的数据样本，只使用完整的数据样本来构建学习模型，但是有限的完整样本可能无法保证机器学习模型的有效性3。为了在不完备数据集上构建有效的机器学习模型，需要处理不完整的数据集，其中重要的步骤包括对缺失的属性值进行填补4，以及去除错误或不相关的数据5等。为了保证清洗后数据的质量，通常需要人工参与，这就直接导致了数据清洗成本的大幅度提高。对于商业公司和组织而言，如何控制处理数据集的成本非常重要，因此研究如何提高数据集清洗的效率具有十分重要的现实意义。为了提高清洗不完备数据集的效率，需要确定数据集中哪些不完备数据更值得被清洗，即不完备数据被清洗的优先级，从而尽可能减小清洗规模，并使清洗后的数据集具有较高的质量。为了达到上述目标，则需要获得不完备数据集中不同数据对模型性能贡献的大小，若某个数据对模型性能具有较大的贡献，则说明该数据对于训练机器学习模型具有较大的价值，应该优先被清洗。因此对于不完备数据集中的每个数据都应该评估在机器学习模型中的价值。评估数据在机器学习模型中的价值可以采用博弈论观点，每个数据都被建模为联盟博弈中的参与者6，而数据在模型中的价值即参与者对联盟的影响可以用模型的效用函数表示。夏普利值（Shapleyvalue）7是合作博弈论中用于分配所有参与者联盟产生的总收益的经典方法，可以有效地解决数据价值评估问题。夏普利值定义了一种合理的价值分配方案，满足公平性、合理性和去中心化性等具有现实意义的良好属性，因此被广泛应用于各个领域。通过计算每个不完备数据在机器学习模型中的夏普利值，就可以有效评估不完备数据在机器学习模型中的价值，从而进一步评估该数据被清洗的优先级。K-近邻（K-nearest neighbor,KNN）分类模型8是在实际应用中最流行的机器学习分类模型之一。KNN分类模型具有结构简单、可解释的优点，这将有助于有效地评估不完备数据对于训练模型的价值。因此，本文提出了一种针对 KNN分类模型的基于不完备数据在模型中夏普利值的数据清洗方法，所面临的主要挑战是：（1）如何定义不完备数据的夏普利值。（2）数据夏普利值的计算是非常困难的。对于完备数据而言通常采用蒙特卡洛采样方法进行近似计算；但对于不完备数据集，每个不完备数据的域是di，其中i=1,2,N。则该数据集可以表示的可能世界数量为|di|，而对于每次采样都需要遍历所有的可能世界，因此即使采用蒙特卡洛采样方法，计算不完备数据夏普利值的时间复杂度仍然是指数级的。（3）如何在不完备数据夏普利值和清洗该数据的优先级之间建立联系。为了解决以上挑战，本文首先基于不完备数据集的所有可能世界定义了一种不完备数据夏普利值的表示方法。然后针对 KNN模型，提出了一种高效的计算不完备数据夏普利值的近似算法。最后提出了一种基于夏普利值的计算不完备数据清洗优先级的启发式算法 ShapClean，可以有效提高清洗不完备数据集的效率，降低人工成本。1基础知识1.1数据夏普利值数据在模型中的价值可以用夏普利值来表示。夏普利值的含义是假设在博弈中对于任意参与者子集组成的联盟加入当前参与者后，联盟财富的边际效用期望即为该参与者的夏普利值9。为了计算数据的夏普利值，可以将每个数据都建模为联盟博弈中的参与者，而数据集中每个数据对当前模型的边compared with data cleaning 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*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的所有数据的集合。该计算方法假设所有数据都将按随机顺序收集，而任意数据z*i在该顺序中的边际贡献即为在已经被收集的数据子集的基础上加入数据z*i带来的模型效用提升。数据z*i的夏普利值则是在所有可能顺序中数据z*i的边际贡献的平均值。1.2KNN分类模型及其效用函数KNN分类模型是一种简单但应用广泛的监督学习模型。对于一个给定的测试集，Jia等人提出了一个针对于KNN分类模型的效用函数，称为KNN效用10。KNN分类模型查找前K个与测试数据最相似的训练数据，并根据其K个最近邻数据的标签判断测试数据的标签。因此，通过计算测试数据的前K最近邻数据中与测试数据标签相同的数量，该效用函数可以直观地衡量KNN分类模型为每个测试数据分配正确标签的可能性。定义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模型中不完备数据夏普利值的计算方法。首先将给出不完备数据夏普利值的定义，并证明其计算复杂度，然后提出一种能够高效计算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中该属性的值进行填补，生成候选值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相似数据实例的集合边界集边界集的大小相似度低于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，因此计算期望时只要取平均值即可，第 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的数据。然后根据以下递推公式计算准确的夏普利值：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=1Mij=1Nw W,w(zi)=zi,m,ztj=zishaptj（7）该方法需要确定每个可能世界中各数据按与测试数据的相似度排序的顺序，而所有可能世界的数量为|di|，因此采用该方法计算不完备数据在KNN模型中的准确夏普利值仍然是困难的。而根据定义 2中不完备数据夏普利值的定义直接计算需要遍历该不完备数据集数量为|di|的所有可能世界和2N个可能的数据子集，因此难以计算不完备数据在KNN模型中的准确夏普利值。因此，需要考虑计算不完备数据在 KNN模型中夏普利值的高效近似算法。2.2不完备数据夏普利值近似计算根据计算完备数据夏普利值的式（2），计算不完备数据夏普利值的式（4）还可以写成如式（8）的形式：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 Iztjk.y=tj.y（9）其中，ztjk代表训练集中第k接近测试数据tj的数据，y代表数据的标签，I为判断条件是否成立的指示函图1不完备数据候选值实例Fig.1Example of incomplete data candidates2244王婧怡 等：面向K-近邻学习模型的高效数据清洗框架数，其值域为0,1。将效用函数代入夏普利值的计算公式，可以得到不完备数据的夏普利值如式（10）所示：shap(i,D)=1N!Ntest|W|j=1Ntestm=1Mi(D)w W,w(zi)=zi,m1Kk=1minK,|Pi|+1Iztjk.y=tj.y-n=1minK,|Pi|Iztjn.y=tj.y（10）其中，ztjn是Pi在可能世界w中第n接近测试数据tj的数据实例，ztjk是Pi和数据zi的并集在可能世界w中第k接近测试数据tj的数据实例。当K|Pi|时，只需要找到Pi中与测试数据t第K相似的数据ztK，并判断在该可能世界中数据zi的实例zi,m与测试数据的相似度是否大于该点。若zi,m与测试数据的相似度大于ztK，则计算zi,m对测试数据标签分类正确可能性的影响，若不大于则说明zi,m不产生影响。训练数据实例与测试数据的相似度sim可通过欧式距离进行计算。因此在这种情况下zi的夏普利值shap1(i,D)的计算可以写成式（11）的形式：shap1(i,D)=1N!Ntest|W(D),K|Pi|j=1Ntestm=1Miw W,w(zi)=zi,m1KIsim(zi,m)sim(ztjK)(Izi,m.y=tj.y-IztjK.y=tj.y)（11）其中，y为数据的标签。当K|Pi|时，所有可能世界中数据zi的实例都一定在与测试数据前K相似的数据集中，因此必须对该数据是否对测试数据分类正确可能性产生影响进行判断，此时其夏普利值可以通过以下形式进行计算：shap2(i,D)=1N!Ntest(D),K|Pi|j=1Ntest1KIzi.y=tj.y（12）数据夏普利值的计算需要结合以上两种情况，如下式：shap(i,D)=shap1(i,D)+shap2(i,D)（13）对于每个数据候选值zi,m在抽样顺序满足K|Pi|条件的情况下，zi,m对测试数据分类正确可能性是否产生影响即其标签是否与测试数据标签相同可以在O(1)的时间复杂度内计算，因此计算shap(i,D)的成本主要取决于计算shap1(i,D)的时间复杂度。对于不完备数据集D上的KNN分类问题，Karlas等人提出了边界集的概念11。定义 3（边界集）边界集B(i,m,K,t)代表在不完备数据集D构成的可能世界集合W中，所有与测试数据t第K相似的数据实例为zi,m的可能世界构成的子集。即：B(i,m,K,t)=w:w(zi)=zi,mzi,m Top(K,w,t)zi,m Top(K-1,w,t)（14）其中，Top(K,w,t)是可能世界w W中与测试数据t前K相似的数据实例组成的集合。可以将边界集的概念应用到计算不完备数据夏普利值中。计算shap1(i,D)只需要遍历Pi中所有数据的候选值，并计算它们的边界集，此时该候选值zf,h是与测试数据t第k相似的数据ztk，判断候选值zi,m与测试数据的相似度是否大于该值，若大于则计算zi,m对测试数据标签分类正确可能性的影响。因此shap1(i,D)的计算可以写成如下形式：shap1(i,D)=1N!NtestMi(D),K|Pi|j=1Ntestm=1Mi1|Wi|1KzfPih=1Mf|B(f,h,K,tj)Isim(zi,m)sim(zf,h)(Izi,m.y=tj.y-Izf,h.y=tj.y)（15）其中，Wi是Pi的所有可能世界的集合。为了计算边界集大小，需要先计算所有候选值与测试数据的相似度。对于任意候选值zf,h，计算训练数据集中的每个数据zn有多少候选值与测试数据的相似度低于zf,h，其数量可以用scnf,h来表示：scnf,h=m=1MnIsim(zn,m)sim(zf,h)（16）其中，指示函数I的值域为0,1。按照与测试数据的相似度，从小到大将所有候选值进行排序并遍历，scnf,h可以由以下公式计算：scnf,h=scni,j+1,n=fscni,j,n f（17）其中，zi,j是排序后zf,h的前一个数据。对于图1展示的不完备数据候选值实例，该不完备数据集D中有两个不完备数据z1和z3，根据它们的实例与测试数据t的相似度，可以得到：sc11,1=2，sc21,1=1，sc31,1=2；sc11,2=1，sc21,2=0，sc31,2=2；sc12,1=1，sc22,1=1，sc32,1=2；sc13,1=0，sc23,1=0，sc33,1=1；sc13,2=0，sc23,2=0，sc33,2=2。2245Journal of Frontiers of Computer Science and Technology计算机科学与探索2023,17(9)然后对Pi中的任意数据zf的所有候选值zf,h递归计算|B(f,h,K,t)|即BCf,h(K,|Pi|)。BCf,h(k,n)=BCf,h(k-1,n-1),f=nscnf,hBCf,h(k,n-1)+(Mn-scnf,h)BCf,h(k-1,n-1),fn（18）当f=n时，当前的zn是与测试数据t第k相似的数据，因此一定在与测试数据t前k相似的数据中；否则，该点有scnf,h种情况其相似度不大于zf,h，即不在与测试数据t前k相似的数据中，有Mn-scnf,h种情况其相似度大于zf,h，即在与测试数据t前k相似的数据中。递归公式的终止条件是：当nk时，BCf,h(k,n)=0；当n=0且k=0时，BCf,h(k,n)=1；当ksim(zf,h)(Izi,m.y=tj.y-Izf,h.y=tj.y)（19）shap2(i,D)=1TNtestt=1,K|Pi|Tj=1Ntest1KIzi.y=tj.y（20）当夏普利值结果满足(,)-approximation时，T=r2/22lb(2N/)，r为 效 用 函 数 之 差U(Pizi,m)-U(Pi)的最大值。由于不完备数据集D中有N个数据，需要依次计算它们的夏普利值，算法的时间复杂度是O(M2N3KNtestlbN)。不完备数据夏普利值的计算过程如算法 1 所示。对于图 1展示的不完备数据候选值实例，共有 6种排列顺序（排列数量较少不需要使用 Monte Carlo采样），对于数据z1根据算法 1 进行计算，可以得到shap1(1,D)=0.416 7，shap2(1,D)=0.333 3，shap(1,D)=0.75。算法1 不完备数据夏普利值近似算法输入：不完备数据zi，不完备数据集D，测试数据t，数据集大小N，KNN参数K，Monte Carlo采样误差参数、。输出：zi的夏普利值shap(i,D)。1.d=candidate(D)/获得所有候选值2.s=cal_s(d,t)/计算候选值与t的相似度3.sorted=sort(s,d)/根据相似度排序4.cal_sc(sorted)/为每个候选值计算sc5.cal_T(N,K,)/计算采样次数6.For t in T7.p=perm(D,zi)/对排序采样，获得zi之前的排序数据8.b=cal_BC(p)/为各数据计算其BC9.W=pw(p,zi)/计算总可能世界数量10.For every candidatezi,mofzi11.sh(zi,m)=012.Ifp K13.Forzf,hin p/当前排序中的每个候选值14.Ifs(zf,h)s(zi,m)/计算zi,m的贡献15.Ifzf.y t.y andzi.y=t.y16.sh(zi,m)+=b(zf,h)/K17.End if18.Ifzf.y=t.y andzi.y t.y19.sh(zi,m)-=b(zf,h)/K20.End if21.End if22.End for23.End if24.Ifpsim(ztjK)(Izi,m.y=tj.y-IztjK.y=tj.y)（21）shap2(i,D,m)=1TNtestt=1,K|Pi|Tj=1Ntest1KIzi,m.y=tj.y（22）shap(i,D,m)=shap1(i,D,m)+shap2(i,D,m)（23）其中，Pi为可能排序中先于数据zi的所有数据的集合。根据数据zi在排序中的位置，数据夏普利值shap(i,D,m)的计算可以分为K|Pi|和K|Pi|两种情况，即式（21）和式（22）中的shap1(i,D,m)和shap2(i,D,m)。对于每个不完备数据zi，计算zi的夏普利值shap(i,D)以及zi所有候选值的夏普利值，并计算所有候选值夏普利值与shap(i,D)之差的平方的均值。该值较大说明不完备数据zi不同候选值的夏普利值大小差距较大，即该数据不同候选值对模型准确度贡献的差异较大，清洗这样的数据有较高的概率对模型准确度有较大的提升。此外Ghorbani等人的实验证明在完备数据集中去除夏普利值较低的数据可以提高模型的效用13，因此在清洗不完备数据集时还需要考虑不完备数据本身的夏普利值。若zi所有候选值夏普利值的最大值为非正数，意味着该数据清洗后可能对模型效用仍产生负面影响，直接删除该数据更能节省人工开销并且保证模型效用。结合以上两方面，不完备数据的清洗优先级计算如下：i=1Mim=1Mishap(i,D,m)-shap(i,D)2Imax(shap(i,D,m)0（24）其中，指示函数I的值域为1,-1。根据值对不完备数据依次进行清洗，对于值较大的数据首先进行清洗，对于值较小的数据可以选择直接删除，其余不完备数据直接使用默认值进行填补。清洗不完备数据集的流程如算法2所示。对 于 图 1 中 的 不 完 备 数 据 候 选 值 实 例，shap(1,D,1)=1，shap(1,D,2)=0.5；shap(3,D,1)=0，shap(3,D,2)=0。1=0.062 5，3=0。因此当=0.5时，选择z1进行清洗。算法2 基于夏普利值的ShapClean算法输入：不完备数据集D，D中各数据候选值的夏普利值shap(i,D,m)，清洗比例。输出：需要清洗的数据子集S，更新后的数据集D。1.Forziin D/计算清洗优先级2.i=cal_metrics(allshap(i,D,m)3.End for4.arr=sort_metrics(all|i|,D)/排列5.Forzfin D6.Ifzf s|fis in topof arr7.Iff 08.removezffrom D9.End if10.Iff 011.addzfto S12.End if13.End if14.End for15.S is the subset of D to clean算法第13行计算清洗优先级，第4行对数据清洗优先级绝对值进行排列，第 515行根据清洗比例选择相应数据子集，并更新数据集D。2247Journal of Frontiers of Computer Science and Technology计算机科学与探索2023,17(9)4实验分析4.1实验数据与参数设置获得现实世界的不完备数据集缺失值的真实值往往非常困难，因此大多数数据清洗实验都需要借助于注入了合成错误的合成数据集。本实验对完备数据集随机注入缺失值（例如 5%、10%等）来模拟不完备数据集，对应的原本属性值作为不完备数据的真实值。为了尽可能模拟真实的不完备数据集，本文采用留一法14计算不同特征对于分类任务的相对重要性，更重要的属性有更高的概率缺失。本实验根据不同特征的相对重要性，随机地向完备数据集中注入缺失值。对于每个缺失的数值类型属性，将数据集中该属性的最小值、平均值、最大值、25%位数、75%位数作为其候选值。对于每个缺失的类别类型属性，将数据集中该属性前四频繁出现的类别和其他类别作为其候选值。本文实验部分使用的数据集包括 Blood Trans-fusion15、Airfoil Self-Noise16和 Real Estate17，对于每个数据集抽取10%的数据作为验证数据集，10%的数据作为测试数据集，剩余数据作为训练数据集。对于 Blood Transfusion 和 Real Estate 数据集，向其中10%的数据注入缺失值；对于 Airfoil Self-Noise数据集，向其中5%的数据注入缺失值。为了便于与 CPClean（certain prediction-based datacleaning）等算法进行对比实验，本文采用了Karlas等人的论文中的实验设置11，即使用了K=3的KNN分类器，并利用欧氏距离计算相似度。4.2评价指标与基准模型本文将利用真实值清洗不完备数据集和利用默认值清洗不完备数据集作为基准模型。对于数值类型的属性，用该属性的平均值作为默认值；对于类别类型的属性，用该属性的最频繁出现的值作为默认值。本文用真实值填补不完备数据集后训练的模型准确度作为清洗算法性能的上界，用默认值填补后训练的模型准确度作为清洗算法性能的下界。基于这两种基准模型使用如下评价指标：M(A)=acc(A)-acclaccu-accl（25）其中，A为任意清洗算法；accl为清洗算法性能下界，即用默认值填补不完备数据集后训练模型的准确度；accu为清洗算法性能上界，即用真实值填补不完备数据集后训练模型的准确度；acc(A)为使用清洗算法A填补不完备数据集后训练模型的准确度。本文除了在数据集上完成了本文所提出的算法，还使用以下几种算法在数据集上进行了对比实验：（1）随机清洗算法：随机选取部分不完备数据进行人工清洗，对于这部分数据用真实值填补其缺失属性值，其余不完备数据的缺失属性值用默认值进行填补。（2）CPClean 算法11：使用序列信息最大化的思想使验证集中的数据都达到CP ed状态，以此来选择要清理的不完备数据。为了确保对比实验的公平性，被CPClean算法选择的不完备数据同样使用真实值进行清理，并与本文算法使用相同的不完备数据的候选值。（3）BoostClean18：从预定义的清洗方法集中选择在验证集上具有最大验证精度的方法。为了确保对比实验的公平性，预定义的清洗方法集即为本文算法生成候选值的方法，包括属性的最小值、最大值、平均值、最频繁出现的值等。4.3实验结果与分析表 2展示了用数据真实值清洗和用默认值清洗后，在各数据集上训练的模型的准确度。从表2中可以看到，数据的缺失值对这些数据集上训练的模型产生了不同程度的影响，即用真实值和默认值清洗数据集后训练的模型准确度的差距。表 3 展示了本文方法和 BoostClean 方法的性能比较。BoostClean算法由于缺少人工参与，通常难以弥补数据的缺失值造成的性能损失，对于Airfoil Self-Noise数据集，BoostClean方法甚至会加大性能损失。而本文提出的ShapClean算法只需要清洗较少的不完备数据即可完全弥补性能损失，其中为清洗比例。表2准确度结果Table 2Accuracy results清洗方法真实值默认值Blood Transfusion0.7470.707Airfoil Self-Noise0.8870.874Real Estate0.8100.762表3数据清洗结果Table 3Data clean results数据集Blood TransfusionAirfoil Self-NoiseReal EstateBoostCleanM/%0-49.6250.00ShapCleanM/%100.00100.00100.00/%12.073.8532.352248王婧怡 等：面向K-近邻学习模型的高效数据清洗框架图2展示了本文提出的ShapClean算法与CPClean算法在不同数据集上的清洗效率对比。对于 AirfoilSelf-Noise 数据集上训练的模型，CPClean 算法可以完全弥补性能损失，但对于Blood Transfusion数据集只能弥补33.25%的性能损失，对于Real Estate数据集只能弥补50%的性能损失。而本文提出的ShapClean算法对于各数据集都能完全弥补性能损失，而且对于所有数据集，ShapClean算法都只需要清洗更少的不完备数据就能达到不低于 CPClean算法的清洗效果，需要清洗的不完备数据数量通常不超过CPClean算法的一半。此外，图 2 展示了在 Blood Transfusion 和 RealEstate数据集上，CPClean算法达到对训练的模型所能弥补的最大性能差距时，CPClean 和 ShapClean 算法的清洗比例，而 ShapClean 算法弥补 100%性能差距时的清洗比例如表3中所示。修改选取的候选值再次进行实验，即对于每个缺失的数值类型属性，将数据集中该属性的最小值、平均值、最大值作为其候选值；对于每个缺失的类别类型属性，将数据集中该属性前二频繁出现的类别和其他类别作为其候选值。对于 Blood Transfusion和Airfoil Self-Noise数据集，CPClean和ShapClean算法能够弥补的性能损失和需要的清洗比例均不发生变化。对于Real Estate数据集，CPClean算法则失效，能够弥补性能损失的比例为 0%，而 ShapClean 算法能够弥补的性能损失和需要的清洗比例仍不发生变化。实验表明 ShapClean 算法不仅只需要清洗更少的不完备数据就能达到不低于 CPClean算法的清洗效果，而且对于候选值选取方案的依赖性更低，具有更高的稳定性。图3展示了ShapClean算法与随机清洗方法的清洗效果区别。相比随机清洗方法，ShapClean算法能够大幅提高清洗效率。为了达到与表3中ShapClean算法相同的清洗效果，对于 Blood Transfusion 数据集，随机清洗方法需要清洗 89.66%的数据；对于 AirfoilSelf-N