收稿日期:20180926;修回日期:20181116 基金项目:国家重点研发计划资助项目(2016YFB1000905);国家自然科学基金资助项
目(61170131,61263035,61573270,90718020);国家“973”计划资助项目(2013CB329404);中国博士后科学基金资助项目(2015M570837);广西自
然科学基金资助项目(2015GXNSFCB139011,2015GXNSFAA139306)
作者简介:李佳烨(1993),男,山西晋城人,硕士研究生,主要研究方向为数据挖掘、机器学习;余浩(1994),男(通信作者),江西上饶人,博士
研究生,主要研究方向为数据挖掘、机器学习(yhgxnu@gmail.com).
基于 K近邻的众包数据分类算法
李佳烨
1
,余 浩
2
(1.广西师范大学 广西多源信息挖掘与安全重点实验室,广西 桂林 541004;2.中南大学 计算机学院,长沙
410083)
摘 要:针对众包数据处理中的质量控制问题,提出了一种加权 K近邻投票分类方法。该方法不单单只是考虑
了某个样例的标记来返回一个答案,而是通过综合考虑样例的近邻来得到更加准确的答案。同时对样例的近邻
加以适当的权重来进一步提高算法的性能,并保持了传统多数投票分类的简单性。K近邻投票分类算法可以有
效地解决缺乏标记的情况,通过对近邻加以权重可以解决不平衡标记造成的影响,从而使算法的泛化性更强。
通过各种场景下的实验,结果表明加权 K近邻投票分类方法取得了很好的效果。
关键词:众包数据;质量控制;K近邻投票;多数投票
中图分类号:TP181 文献标志码:A 文章编号:10013695(2020)04003097304
doi:10.19734/j.issn.10013695.2018.09.0736
CrowdsourcingdataclassificationalgorithmviaKnearestneighbor
LiJiaye
1
,YuHao
2
(1.GuangxiKeyLaboratoryofMultisourceInformationMining& Security,GuangxiNormalUniversity,GuilinGuangxi541004, China;
2.SchoolofComputerScience&Engineering,CentralSouthUniversity,Changsha410083,China)
Abstract:Aimingatthequalitycontrolproblemincrowdsourcingdataprocessing,thispaperproposedaweightedKnearestneigh
borvotingmethod.Thismethodnotonlyconsideredthemarkofacertainsampletoreturnananswer
,butratherobtainedamore
accurateanswerbyconsideringtheneighborsofthesamplecomprehensively.Atthesametime,itappliedappropriateweightstothe
neighborsofthesampletofurtherimprovetheperformanceofthealgorithmandmaintainedthesimplicityofthetraditionalmajor
ityvote.TheKnearestneighborvotecaneffectivelysolvetheproblemoflackofmarkup.Byweightingtheneighbors
,itcansolve
theinfluenceoftheunbalancedmarkandmadethegeneralizationofthealgorithmbestronger.Throughexperimentsinvarious
situations,theresultsshowthattheproposedweightedKnearestneighborvotingmethodhasachievedgoodresults.
Keywords:crowdsourcingdata;qualitycontrol;Knearestneighborvoting;majorityvoting
0 引言
随着人工 智 能时代 的 到 来,数 据 的 重 要 性 已 经 不 言 而
喻
[1]
,并且影响世界的方方面面。阿里巴巴的城市大脑项目
将 AI技术应用在系统收集到的城市大数据上,可以 20min锁
定嫌犯;滴滴出行通过对城市大数据分析来为每辆车规划最优
行车路线,缓解交通拥堵问题;沃尔玛通过超市顾客的选购记
录数据分析,为商家精准投放广告。这些数据收集的任务大部
分都可以使用机器自动完成,但是在图像类别标注
[2]
、商品优
劣等一些任务中,机器常常无法准确地对这些数据进行处理。
近年来,有学者在研究中发现数据的有效性与数量级对实验效
果的影响甚至高于对算法本身进行优化
[3]
。因此,如何在研
究的相关领域找到高质量与高数量级兼具的数据集成为了众
多科研工作者迫切需要解决的问题。2009年普林斯顿大学李
飞飞团队推出的
ImageNet图像数据集
[4]
是目前世界上最大的
图像识别数据库,经过近十年的发展,ImageNet数据集已经对
计算机视觉以及整个机器学习领域带来了深远的影响。在
2010—2017年期间,研究人员已经将物体分类的准确率提高
到 97.3%,超过了人类分辨水平
[5]
。随着时间推移,这个数字
仍然在一步步向 100%靠近。可以说 ImageNet数据集打开了
计算机视觉、模式识别甚至整个人工智能领域的研究新篇章,
同时也充分证明了巨量级的真实数据集对科学研究的重要性。
在
ImageNet数据集研发之初,如何对 1600万张图像数据进行
标注成为了关键难点。在当时看来这个几乎是个不可能完成
的任务,团队创始人李飞飞偶然接触到 Amazon的 众 包 平 台
AmazonMechanicalTurk,通过众包平台将大量的图片标注任务
分配给世界上任何一个对之感兴趣的人,最终历时两年多才完
成了这个标注任务。ImageNet数据集的成功也同时证明了利
用众包方法处理一些问题是非常必要与高效的。然而众包方
法带来大量数据的同时也带来了一些问题。通常很多标记人
员并不是相关的专业人士,水平参差不齐,每个人给出的数据
标注并不是完全正确的,有些给对象标注了错误的标签,有些
因为不确定而没有给出标签。这些缺陷导致最终得到的众包
数据通常含有一定的噪声值与缺失值。这些问题在数据挖掘
中非常常见
[6]
,因此,如何针对性地处理这些问题,成为能否
高效利用众包数据的关键。
在之前 Zhang等人
[7]
对传统的 KNN算法做了改进,通过
l
1
范数来动态地为不同的样本生成不同的 K值,以此来使算
法达到很好的性能。但是这种算法只能适用于一般的数据集,
并不能用于众包数据,而且它对数据标记的缺失很敏感。此
外,郝建柏等人
[8]
也提出了一种模糊近邻标签传递的半监督
分类算法。该方法虽然能对没有标签的数据进行分类,但是它
第 37卷第 4期
2020年 4月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol37No4
Apr.2020