基于细粒度用户可靠性的众包任务分配研究分析工商管理专业.docx

前言3第1章绪论411¾J)IJ.正页；11»1.2 国内外研究现状及挑战41.3 本文的主要工作及创新点4第2章相关技术和研究工作72.1 众包基本特征72.1.2与外包区别72.2 众包工作流程82»3)'iJIj»82.2.1 AmazonMechanicalTurk82.2.2 科研领域应用9旦.fjlS*12.4.1 低质量结果产生的原因102.4.2 相关工作115J-1一*11第3章问题抽象与模型建立13第4章算法研究154.1 共聚类可靠性矩阵154.1.1 基于用户回答准确率的任务聚类154.1.2 计算共聚类164.2 预1贝!目K任务正确答案.,164.2.1 朴素贝叶斯相关的统计学知识164.2.2 朴素贝叶斯模型174.2.3 3预贝!目K任务答案.,.17第5章实验与对比225.1 模拟仿真5.1.1 贝塔分布5.1.2 狄利克雷分布5.1.3 模拟用户作答5.1.4 分析预测结果5.2 相关预测方法5.2.1 majorityvoting5.2.2 weightedvoting5.3 方法对比5.3.1 k折交叉验证.5.3.2 对比结果5.4 本章小结第6章总结与展望6.1 本文总结6.2 后续工作展望.22.22.22.23.23.25.25.25.26.26.26.29.30.30.30.32.346.3 致谢摘要众包(CrOWdSoUrCing)计算模式因其自身优势，近年来被学术界视为一种高效大规模数据集收集方式。但是，由于众包用户自身能力所限，不同用户提供的答案可能存在不合理的情况。因此,如何将收集到的用户答案进行整合,来推断任务的正确答案，是一项关键问题。己有的真实答案预测方法通过挖掘用户可靠性和任务话题之间的相关性来解决这一问题。但是，己有研究仅在有限的任务上起作用，对标准数据集的利用不充分,对于有些任务不兼容。为了考虑兼容性，我们认为任务和用户都存在聚类，进而提出了一个通用的细粒度方法。该方法包括两个方面：建立共聚类和基于共聚类可靠性模型的真实答案预测机制。首先，基于用户对标准任务的回答，利用特定的聚类方法得到用户聚类、任务聚类，建立共聚类可靠性模型。然后对于一系列答案未知的目标任务，根据学习得到的模型，将收集到的用户答案以特定的方式组合，预测出目标任务的真实答案。通过理论分析，我们证明了本论文提出的方法适用性强，可以更好的表达用户和任务之间的关系。同时，实验表明，我们的方法可以对目标任务得到更为精确的估计。关键词：众包；共聚类模型；答案预测；标准任务AbstractCrowdsourcinghasbeenregardedasaveryefficientandpromisingmethodtocollectlargedatasetsinrecentyearsduetoitsnativeadvantages.Unfortunately,theanswersprovidedbyworkersofcrowdsourcingarenotalwaysreasonablesincethevariationabilitiesofworkers.Sohowtointegratethecollectedanswerstoinferthetrueanswerofthetargettasksisacriticalissue.Existingstate-of-the-arttruthdiscoverymethodssolvetheproblembyexploringthecorrelationbetweensourcereliabilityandtasktopics.However,theabovemethodscanonlyworkwellinlimitedtasks,sincetheyoftendonotmakefulluseofglobaldatasets.Weconsiderthatbothtasksandsourcesexistclustersandproposeageneralfine-grainedmethod,whichcanmaintaincompatibility.Themethodincludestwoaspects:buildingco-clusterreliabilityanddiscoveringtrueanswer.First,basedonanswersforstandardtasks,wecancalculatethesourceclustersandtaskclustersthroughspecificalgorithmsothatco-clusterreliabilitymatrixcanbebuilt.Thenforaseriousoftargettasks,wecollectworkers,answersandaggregatethem,makingfulluseofthepattern,toproducetheestimation.Throughthetheoreticalanalysis,ourapproachiscompatiblewithvarioustasks.Itcanbetterdescribetherelationshipbetweenworkersandtasks.Atthesametime,weshowthatourmethodcanproduceamoreaccurateestimationthroughextensiveexperimentalresults.Keywords:crowdsourcing;co-cluster;answerestimation;standardtasks随着互联网的不断发展，众包这种新的生产组织形式应运而生。企业为了有效地解决技术问题或者是发现创意想法，利用互联网发布各种任务。而网络大众里，有些人是兴趣驱动，有些人是利益驱动，利用自己的时间，通过网络这一媒介，来完成企业发布的任务。众包提供了i种全新的组织大量劳动力的方式，对于软件业和服务业尤其有用。本文介绍了众包模式以及众包的广泛应用，包括一些众包平台和众包在科研领域的应用，同时也提出了该模式存在的问题，指出众包的质量控制是一项值得科研工作者去研究探讨的问题，进而提出了本文的众包模式学习方法，通过有效的将用户和任务进行聚类，学习用户类和任务类之间的可靠性，更加有效准确地解决任务，此方法具有良好的通用性。本文完成的主要工作及创新点有：(1)介绍众包模式以及众包的工作流程，列举了一些众包平台和众包在科研领域的应用，阐明了众包的研究价值，同时提出了众包模式中存在的问题。(2)提出用户和任务分别存在聚类，将用户集和任务集分别聚类。同时学习用户聚类和任务聚类,得到共聚类可靠性模型，从而得到比现有方法更为通用的模型。(3)利用学习到的共聚类可靠性模型，结合朴素贝叶斯的思想，采取特定的算法,得到对目标任务序列的真实答案更为精确的估计。(4)我们通过在真实的数据集上进行实验，将该方法和现有基本方法的效果进行对比与分析，验证了该方法的有效性。第1章绪论本章首先介绍了众包的研究背景和意义，然后简单介绍了众包国内外研究现状,其次，概述了本文所做的主要工作以及创新点，在本章的最后介绍了这篇论文的组织结构。1.1 研究课题的提出近年来，产生大规模数据集对于研究和工业应用都有着巨大的价值。传统的策略大多是雇佣对相关领域感兴趣的专家，但想要收集大规模的数据，几乎是要付出很大代价且几乎不可能实现的。因此，众包服务，像AMT(AmazonMechanicalTurk)或者CrOWdFk)Wer,通过将将任务分发给全世界的用户，来收集数据集。1.2 国内外研究现状及挑战由于众包在提供大规模数据集时有着很好的有效性，因此它越来越受欢迎。用户不一定要是领域专家，任务也通常不止分发给一个用户，这导致了用户们的答案质量往往是参差不齐的。因此，如何聚集用户答案来推断任务的真实答案是众包领域的一个关键性挑战。一个直观的解决方法是最大值投票法，该方法将被最多数目的用户选择的答案作为最终的真实答案。但是，它没有考虑到一个问题，用户之间的可靠性是参差不齐的当低质量的用户数目比高质量用户数目还多时，这种方法得到的结果并不理想。为了解决这个问题，一系列加权投票的方法被提出，这类方法的宗旨是给有着更高可靠性的用户赋予一个更大的权重，从而该用户所给出的答案对于最终答案的影响因子也更大。然而，这些方法的一个共同特点是，均假设一个用户对于所有任务的可靠性是一致的。其实这是不合理的，因为任务类型是各种各样的，每个用户也都有自己所擅长的任务类型。1.3 本文的主要工作及创新点本文首先介绍了众包是什么，众包模式是如何工作的，我们研究众包的意义和价值体现在哪，同时提出了众包模式中的存在问题，为此，提出了本文的解决方案，也是本文的核心问题。我们充分利用了每个事物都有其代表特征这一想法，认为用户之间存在用户聚类,任务之间存在任务聚类。同一类任务或者同一类用户享有同样的模式而不考虑他们之间的差异性。比如说，一个用户聚类共享的模式是该用户聚类对于各种任务聚类的可靠性。更具体的说，一个用户对于不同的任务类型有着不同的可靠性，但是，我们认为对于一个特定的任务聚类，属于同一个用户聚类的用户们的可靠性是相同的。虽然我们清楚，每个用户都是独一无二的，对于同一任务的认知或者说是可靠性不可能完全相同，但我们将最为相似的用户聚集在一起而不考虑他们之间的细微差别。对于任务来说，也是同理，我们将最为相似的任务聚集在一起而不考虑他们之间细微差别。利用聚类的想法，可以使我们的方法有着更好的通用性和有效性。因此，我们首先学习用户聚类和任务聚类，得到共聚类可靠性矩阵，然后基于该模式，分别通过随机选择一定个数的用户，和基于用户标签及共聚类可靠性矩阵选择用户，来回答目标任务，通过特定的算法获得任务的正确答案推断。在本文中，我们首先引入标准任务，即拥有标准答案的一类数据。用户首先对给定的标准任务进行作答，根据作答情况，得到用户特征，采用k-means算法的思想对用户进行聚类，然后计算出任务特征，采用类似的思想对任务进行聚类，学习到用户聚类和任务聚类以后，计算得到共聚类可靠性矩阵，代表同类用户与同类任务的相关性。然后根据学习到的模型，利用朴素贝叶斯算法的思想，预测目标任务的真实答案，获得对目标任务更加精确的推断。最后，通过在模拟仿真实验以及在真实数据集上进行实验，和基准方法进行对比与分析，验证了该众包方法的有效性。1.4 本文的组织结构本文共分为六个章节，各章的内容安排如下：第一章：绪论。本章简要地介绍了众包的研究背景以及众包的研究价值，同时也介绍了国内外现有的众包研究现状，指出解决众包的质量控制问题的必要性，进而提出了本文的主要工作和创新点。第二章：相关技术和研究工作。本章首先详细介绍了众包的工作流程和一些众包平台，同时介绍了众包在科研领域的应用，并指出了众包研究中的一项关键问题一一众包质量控制问题。第三章：问题抽象与模型建立。本章对众包工作流程进行抽象，介绍了该众包模式的理论模型，给出该问题的形式化定义。第四章：算法设计。本章首先利用聚类算法的思想，给出获得用户簇、任务簇以及共聚类可靠性模型的算法。接着，利用朴素贝叶斯算法的思想，对于答案未知的目标任务,结合已有的用户簇、任务簇和共聚类可靠性模型,推断目标任务的正确答案。第五章：实验与对比。本章首先通过仿真实验，展示了在用户规模不同、用户质量不同时该算法得到的结果对比。然后，基于真实的数据集，将设计的算法与两个基准方法所获得的预测答案准确率进行对比，分析该方法的有效性。第六章：总结全文，提出未来工作的设想与展望。第2章相关技术和研究工作所谓众包（CrOWdSOUrCing）,是指一个公司或者组织（requester）把需要执行的工作任务（tasks）分解成合适的规模（microTaSkS）,借助于众包平台（例如AmazonMTurk或CroWdFloWer等）进行发布，互联网用户（CroWdS或WOrkerS）可以自愿选择来完成这些任务，当然，这些用户对于公司或组织来说是匿名的，完成任务以后这些用户可以获得相应的奖金。这些任务通常由一些简单操作就可完成，比如判断一句话的表述是否合理，将图片进行分类等。本章详细介绍了众包的特征，众包是如何工作的，众包的应用，列举了一些众包平台，然后介绍了众包模式中存在的问题。2.1 众包基本特征2.1.1 基本特征众包的基本特征包含：（1）计算机自身通常难以解决众包中的任务；（2）通过公开的方式发布一些任务，传递并召集互联网上的大众群体；（3）大众用户独自完成任务，或者协作完成一些任务；（4）是一种分布式的问题解决机制。2.1.2 与外包区别外包（outsourcing）是指企业将非核心业务委派给专业的外部公司（往往是因为人力资源有限，并且想要保持住企业组织的核心力量），从而减少成本，凝聚了人力资源，提升了企业效率和形象。众包和常规意义上的外包不同，众包的任务分配给的大众网络用户具有不确定性,而外包则是将任务给确定的个体来完成。此外，外包非常注重外包对象是否专业，而众包更注重自由发挥和创意，有一定的随机性。最关键的区别在于，外包的合同双方通常不是匿名的，是基于一定的契约精神的。发布者和完成者对于对方的背景、资历等都具有充分的了解才可以确定合作合同，任务实现的媒介也未必是网络平台。而众包的用户对于任务发布人来说，是不知道具体个人信息的，众包平台提供的有限数据就是彼此之间的所掌握的信息。这可能会导致一些众包质量控制问题，比如恶意欺骗。尽管如此，众包还是有其独特的优势。众包的特色就是“众”，集大众的力量，解决大规模的、枯燥的、重复性的任务。2.2 众包工作流程众包领域的研究的主要包含了三个方面的问题，分别是众包的任务该怎么设计，众包的成本如何做到尽可能地低，还有就是众包用户的质量问题。具体来说，众包领域的研究问题可以细化：微型任务设置、用户奖励策略、任务完成时间的控制、发布者成本控制策略,检测欺骗类型用户，众包结果聚集及答案预测、工作流程设计等。众包的主体包括了任务发布者(requester)和任务完成者，也叫做用户(worker)。任务(tasks)将他们关联到一起。当有任务需求的人想要利用众包来完成自己的任务时，需要按照一定的流程来使用众包。首先他要设计自己的任务，然后可以利用众包平台来发布设计好的任务，等待用户来完成任务。用户可以在众包平台上查找感兴趣的任务，选择性的回答并且提交给众包平台。在任务期限截至以后，任务需求者将用户的答案进行筛选并整合。具体的工作过程如图2.1所示。任务发布者任务完成者图2.1众包工作流程2.3 众包应用美国加州伯克利大学(UniversityofCalifornia,Berkeley)的SETIhome分布式计算项目，遍及世界各地的成千上万的个人电脑的闲置计算能力，为他所用。那么，与此类似，成千上万的互联网大众的闲置脑力也可以通过分布式的人力资源网络得到充分的利用。2.3.1 AmazonMechanicalTtirk机器的智能化训练需依靠庞大的数据，谷歌开源的GooogleOpenImageDatasets,Yooutube-8M中的标记视频等，这些需要按规则分类的数据集必须依靠人类的智慧，才可以区分每一个细微的差别，机器是无法直接完成的。那么这些海量数据由谁来标定是我们需要考虑的，亚马逊的劳务众包平台（AMT）很好的解决了这个问题。亚马逊劳务众包平台，是一个有着十几年历史经验的平台。随着时间推进，平台不断的发展，到今天为止，AMT拥有累计超过50万的用户参与注册。用户们在平台上领取一些微型的任务，完成这些任务从而可以得到相应的报酬。AMT会给用户进行评级。往往用户等级越高，相应的酬劳也越高。当任务需求者发布任务需求时，AMT系统会自动将任务优先分配给等级比较高的用户。等级较低的用户被分配到任务的机会也会相对小一点。通过实例训练机器的方式被称为监督式学习，而实例的产生，出自于AMT的用户们，也就是在线劳工。ImageNet拥有超过1400万被分类的图片，这其中大部分都是由AMT上5万名用户花费了两年的时间完成的。AMT将这类服务形容为“人工的人工智能”。232科研领域应用近几年来，众包作为一种很有效的解决问题的方法，被大众所认可。在数据挖掘领域中，众包逐渐应用于科学研究的训练和测试阶段，将其作为科学实验的一个良好的辅助手段。在机器学习、信息检索等研究领域里，一个语料库是否优质有着比较重要的影响。通过同一语料库，可以比较不同系统或者算法之间的有效性。然而，如果是通过相关领域的研究者来一项一项地标注知识数据，从零开始建立该研究领域相关的大型数据库，显然是非常浪费时间和精力的，并且成本很高。因此，众包可以很有效地运用于研究领域，解决该问题。众包在监督学习中有着一定的应用，监督学习也称为分类或者归纳学习，这一种学习方法与人类的学习模式有着类似之处。人类往往从积累的经验中，来对问题进行思考、归纳和总结，从而再遇到此类问题时具备一定的能力。但是，计算机本身没有人类的智慧，而是要通过搜集大量的数据来进行机器学习，这些大量的数据就类似于人类的经验积累。显然，监督学习中需要有明确类标、且有着一定的可靠性的训练数据集。这种数据集可以通过众包模式来有效获得。可以首先通过众包来标注各个数据的类别，然后利用各种监督学习的方法来学习分类特征，获得分类算法，这也就是计算机对大量数据进行学习的过程，最后还可以利用众包的数据集来衡量算法的优劣程度，以便优化算法。通俗来说，就是把一些对于计算机来说难以解决，但是对于人类来说比较简单的问题，交给众包来解决，这种解决方式高效、成本较低且有着较高的可靠性。信息可信度计算，也就是对于信息的可信程度进行估计，这是近几年的一个研究热点网。过去是新闻媒体主导言论的时代，信息往往具有较高的真实性，而随着互联网的蓬勃发展，无数的网民都有了话语权，可以发帖、评论。网民们不需要为自己的言论承担责任，导致网络中充斥着大量无效的、虚假的信息。这种无效的网页内容浪费了我们的时间，严重影响了我们对于信息知识的获取，甚至会误导我们。CarlosCastillo等人在论文中提出了一种判断一篇微博信息是否可信的分类算法,其中巧妙地运用了众包模式，来进行微博语料的标注。我们可以发现，众包在科学研究中遇到限制和瓶颈时，是一种很好的辅助手段。2.4 众包质量控制众包可以为任务发布者提供大量的匿名的用户，通过聚集这些用户的智慧和劳动,很多实际问题，而且往往是计算机难以直接完成的，可以得到有效解决。但是，总会存在一些用户，没有很好的为任务发布者完成任务，提交的答案质量低下，造成负面影响。如何将有噪声存在的答案（即错误的干扰答案）聚集起来推测任务的真实解，是众包中一项有挑战性的任务。2.4.1 低质量结果产生的原因企业和科研的需求日益增加，众包平台日益发展普及，有着越来越多的大众网络用户参与到众包的工作中，这些众包用户显然是多样化的。起初，很多众包用户到众包平台上选择一些任务，往往是因为感兴趣或者是作为一种打发时间的方式。一方面消磨了时间，一方面帮助别人解决了一些问题。金钱上的回报对于这些用户来说不是最主要的目的。有一些众包用户，可能受自身特长技能所限制，完成任务的质量一般。然而，形势严峻的是，随着众包用户的增多，受利益驱动的众包用户也越来越多。其中不乏一些恶意工作者,尽可能付出最少的劳动，对待任务丝毫没有认真严肃的态度，而是随意作答、快速提交，从而导致众包的结果是低质量的。这一问题引起了很多研究者的关注。2.4.2 相关工作对于含有低质量结果的用户答案，如何将这些答窠聚集起来推断任务的真实答案,科研工作者们已经做出了相关的研究。一部分工作考虑将用户的可靠性水平融合进来,作为答案预测的一个因素。DaVid等人提出一种模型,每个用户的可靠性可以被预测，然后使用EM算法来推测真实答案。ZenCrowd1101也采用了用户可靠性和EM算法来预测真实答案。尽管他们的模型各不相同，但他们都遵循的原则是，在估计任务真实答案时，赋予更高可靠性的用户更大的权值。但是,他们都不考虑任务之间的异构性，而是假定一个用户对于所有任务都有着相同的可靠性。与之不同的是，我们的方法将用户对于不同的任务有着不同的可靠性作为一个考虑因素，也就是说将用户对于任务的可靠性细粒度化。也有一些研究，将用户对于不同任务的细粒度可靠性作为考虑。FaitCrOWdWI针对任务的描述，采用了话题模型，从而将任务进行聚类，然后估计用户对于属于不同话题聚类的任务的可靠性，从而推断任务的真实答案。SimPSon1提出了一种贝叶斯分类组合方法来得到一种更为精确的分类。我们粗略的将这些方法分为两类；一种利用任务描述和任务聚类的关系，另一种对用户对于不同答案的细粒度可靠性进行建模。但是，他们都对任务有着额外的条件，要求任务有特定的描述，或者要求任务的候选答案是非特定的，也就是说仅仅适用于有限的任务。和这些方法不同的是，我们的方法直接从正确性矩阵中学习任务聚类和用户聚类，而对任务的类型没有额外的限制，因此，该方法更为通用。基于对标准数据的运用，真实答案预测方法可以被划分为两类。一类是无监督方法，一类是半监督方法。FaitCrOWd可以归为第一类，该方法同时推断目标任务的真实答案和用户的可靠性。而采用半监督方法的模型，利用了真实数据来建立可靠性估计。ShahU引等人采用了“黄金标准”任务来帮助估计用户的表现水平。2.5 本章小结作为从各种各样的用户中廉价地收集数据的一种方式，众包模式变得越来越流行。众包往往可以解决计算机难以完成的任务，有着广泛的应用。但是由于人为错误和垃圾邮件的流行，收集到的用户答案往往是有噪声的，对于一项任务，我们希望通过较低的成本获得较高质量的答案，因此，收集并整合用户答案是一项关键问题。第3章问题抽象与模型建立我们考虑这样一个众包工作流程：该众包平台包含了若干任务和用户。任务分为标准任务（由众包平台提供）和目标任务（由任务请求者发布）。每个用户需回答平台中所有的标准任务，众包平台收集这些用户答案，然后采用基于用户答案准确率的聚类算法构建用户特征数据库、任务特征数据库以及可靠性数据库。任务请求者发布新的任务，即目标任务。众包平台选择部分用户来完成目标任务，收集用户答案，结合平台中的数据库信息，采用朴素贝叶斯算法的思想，给出目标任务的答案预测。我们的目标是，该众包平台为目标任务提供的答案具有相对更高的准确率，从而更好地为任务请求者服务。图3.1简要显示了该众包的框架。用户回答标准任务<目标任务信息用户回答目标任务=>目标任务答案用户用户众包平台目标任务用户用户特征数据库r标准任务任务特征数据库可靠性数据库目标任务目标任务图3.1众包框架该众包的工作流程为：1 .用户回答平台中的标准任务；2 .平台构建用户特征、任务特征和可靠性数据库；3 .任务请求者发布任务需求；4 .平台选择用户完成任务；5 .平台聚集用户答案，提交给任务请求者。基于这样一个众包问题，我们给出该问题的形式化定义：有m个标准任务T=9PW个目标任务T=q精叫以及n个用户U=uy用户对标准任务的回答构成答案矩阵为A=心力犯：因为标准任务的答案对我们IljjL=ItJ=I来说是已知的，因此可以得到正确性矩阵R=对于每个目标任务，均选取"个用户进行作答。定义1.所有的任务都是单选问题。对于特定任务如它包含了B个候选答案Ci=%,Ci2,Gb,它的真实答案表示为C：Cq。定义2.答案元素表示用户%给任务。的答案。aij=bflbB,表示用户均选择任务。的候选答案中的作为该用户的回答。定义3.正确性元素”j表示用户均对于标准任务。的答案是否正确。Gj=I表示用户%正确回答标准任务3rij=O表示用户%对于标准任务G回答错误。定义4.共聚类可靠性矩阵"x'表示第1个用户聚类对第k个任务聚类的可靠程度。定义5.同一用户聚类中的所有用户对于某一任务有着相同的特征，并且某一用户对于属于同一任务聚类中所有任务的可靠性是相同的。定义6.用户给目标任务。的所有回答中，我们通过计算得到答案修，作为对目标任务最精确的预测答案。我们的目标是要是要得到1个用户聚类彷；,标准任务的k个任务聚类p共聚类可靠性矩阵为=以：11，再通过川个用户对目标任务的回答，得到对于目标任务真实答案的估计E=ej÷7l,o第4章算法研究4.1 共聚类可靠性矩阵聚类是指将一组对象集合分划成多个类别的过程，每一个类别中的对象称为一个簇。一个簇内部的对象彼此相近，簇与簇之间的对象彼此相异。在本文的研究任务中，不同的用户有着不同的能力和特长，不同的任务也代表着不同的话题或领域。我们需要根据用户对标准任务的回答,得到用户之间的相似程度,将用户划分到不同的类别中。根据用户聚类和正确性矩阵，再将标准任务进行聚类划分。分别将用户和标准任务进行聚类，由聚类所生成的簇是一组用户或者标准任务的集合，属于同一个簇的用户彼此相近，不同簇之间的用户彼此相异。任务也是同理。4.1.1 基于用户回答准确率的任务聚类在本文中，我们需要根据n个用户对于m个标准任务的回答，也就是mxn规格的正确性矩阵R=HjRj=,来将用户聚类、标准任务聚类，计算出共聚类可靠性矩阵。在这里，我将用户对于每一个标准任务的回答情况作为一个用户的特征，即每个用户包含了m个特征。想要将用户聚成1类，则首先随机生成1个聚类中心。对于每个用户，计算出离该用户最近的一个聚类中心，将用户划分为该类别。计算完每个用户所属的类别以后，再重新计算每个类的质心，并更新用户的类别，直到质心不再变化为止口41：1 .随机选取1个初始质心（作为初始CIUSter）；2 .重复以下步骤：3 .对每个用户特征弓=j曙1，计算得到距其最近的质心，将用户归为该cluster；4 .重新计算1个cluster对应的质心；5 .直到质心不再发生变化。算法4.1用户聚类算法由此，我们得到了1个用户聚类。接着，计算每一个用户聚类对于每一个标准任务的平均准确率，得到了mXl规格的平均准确率矩阵，R=%：；,=其中，力表示第j类用户中正确回答任务i的人数除以第j类用户回答任务i的总人数。根据每类用户对于每个任务的平均准确率矩阵，采用k-means算法进行聚类。将每类用户对于一个任务的平均准确率作为该任务的特征，即每个任务包含了1个特征。想要将任务聚成k类，则首先随机生成k个聚类中心，对于每个任务，计算出距离该任务最近的聚类中心，将任务划分进该类别。计算完每个任务所属的类别以后，再重新计算每个类的质心，并且根据新的质心更新任务的类别，直到质心不再变化为止，由此，我们得到了k个任务聚类：1 .对每个标准任务i：2 .对每一个用户聚类j:3 .计算%j，即第j类用户中正确回答任务i的人数与第j类用户中回答任务i的总人数的比值；4 .得到1类用户对m个任务的平均准确率矩阵R'=rmj-；5 .随机选取K个初始质心（作为初始cluster）；6 .重复以下步骤：7 .对每个任务特征不二也'；=/计算得到距其最近的质心，将任务归为该cluster；8 .重新计算K个ClUSter对应的质心；9 .直到质心不再发生变化。算法4.2基于用户准确率的任务聚类算法4.1.2计算共聚类最后，需要通过计算求出共聚类可靠性矩阵。共聚类可靠性的含义是某一类用户对于某一类任务的可靠性，也可以理解为该类用户对于该类任务的能力值。在这里，任务聚类和用户聚类均已通过k-means方法求得，那么共聚类可靠性矩阵=Wk1：=中的值3可以通过第1类用户中正确回答第k类任务的人数，与第1类用户中回答第k类任务的总人数的比值得到。4.2预测目标任务正确答案4.2.1 朴素贝叶斯相关的统计学知识在很多的实际应用中，贝叶斯理论被验证是效果很好的。首先看条件独立公式，如果事件X和Y相互独立，则有：P(XJ)=P(X)P(Y)条件概率公式：P(XIy)=P(X,y)p(x)全概率公式：P(X)=Wp(XW=W)P(K)由此得到贝叶斯公式：PmX)=P(x/)P(yQI"J-kp(y=%)p(%)4.2.2 朴素贝叶斯模型假如我们有m个样本，每个样本有n个特征，则分类模型样本可以表示为：W),婷),姆),%)W),4),.,峭,丫2),(%”斓nyn)特征输出有K个类别，定义为JC2Qo根据贝叶斯公式，得到X和Y的联合分布：P(X,Y=Ck)=p(r=CQP(X=万丫=CQ=P(V=G)P(XI=X,X71=占卜=。)其中，p(y=Ck)可以通过最大似然法求出，即类别Ck在训练集里面出现的频数，但是P(X=%,xr=%ry=嬴)很难求出，这是一个有n个维度的条件分布。朴素贝叶斯模型假设，X的n个维度之间是相互独立的，由此可以得出：P(Xl=S,，Xn=X7JY=CQ=P(Xl=X1Y=Ck)P(X2=X2Y=CQP(Xn=ny=CQ最后，我们通过后验概率最大化来判断分类。计算出所有的条件概率p(y=CklX=XteSt),找出最大的条件概率所对应的类别，即为朴素贝叶斯的预测I，表示为CreSlllt=argmaxP(Y=CkX=XteSt)O4.2.3 预测目标任务答案目标任务的正确答案在预测阶段是不可知的，用于预测结束后的对于正确答案预测准确率进行评估。（一）分配任务当任务需求量很大时，我们为每个任务随机选择一部分用户作答，从而充分调动众包平台中的用户。当任务需求量不大时，我们可以根据用户的可靠性进行排序，利用贪心的思想，优先选择综合来说更加可靠的用户来完成任务。在该问题中，目标任务的标签是未知的，用户的标签是我们根据用户对标准任务的回答学习得到的。我们在预测真实答案时假设目标任务对每一个任务类别有一个隶属度，目标任务的标签表示为瓦仇表示该任务对第k类任务聚类的隶属度，通过标准任务中属于第k类任务的个数与标准任务总数的比值得到。又知共聚类可靠性矩阵为3=*口：1=1，并将某个用户对应的用户聚类标签记为1，那么该用户的可靠性可以通过=氏外来计算。我们可以计算出所有用户对目标任务的可靠度，将可靠程度从高到低排序，优先选择高可靠性用户作答。（二）答案预测基于学习得到的共聚类可靠性矩阵和用户的聚类分布，我们想要估计出目标任务的正确答案。核心思想是遍历每一个候选答案，计算该答案为真实答案的概率，选取概率值最大的答案作为对于真实答案的估计。已知共聚类可靠性矩阵为=乎膜；：=，每一个用户对应的聚类标签，每一个标准任务的标签。现有目标任务3该任务有B个候选答案，该任务的真实答案为c；。随机选取一些用户对目标任务t进行作答，可以得到答案数组瓦,4,如。对于每个答案Q,iZ,它所对应的用户为加产，这些用户对应的聚类标签构成标签数组无其中，用户兀产所对应的用户聚类标签为优。目标任务t所属的任务聚类标签对我们来说是未知的，在本算法中，我们假设该任务的聚类标签为瓦丽表示该任务对第k类任务聚类的隶属度,曲通过标准任务中属于第k类任务的任务个数与标准任务总数的比值得到。候选答案b是真实答案的概率可以表示为：p（c；=battBt,）丸表示所有可能的正确性数组，我么可以通过以下公式计算候选答案b是真实答案的概率：PG=bdt,Bt,fy）=«p（c；=b,xtdtfBfft）（公式4.1）当正确答案为b时，我们用指示变量为i,=,1他,2|”，勺,|闺|,匕来表示相应的正确性数组，显然，对于由IZl个用户构成的所有可能的正确性数组中，除了正确性数组兀1b，其余数组丸均使得概率PG=4元同,B,0）为0。因此：P（C；=bat,Bf,=p（c；=btxbattB,）（公式4.2）根据贝叶斯公式：p（c；=b,如Z,8,0）=Q"鬻（公式4.3）P（Z）表示一种答案矩阵的概率，在这里是一个常量，因此我们得到：PG=bdtfBt,f）ocp（c；=blxtb,atB,tl）（公式4.4）目标任务属于每一种任务类型的概率是由标准任务的概率获得的：P（Ct=btxtlb,dtBfff）=fc=P（Ct=b,xtb,at,t=kBt,§）（公式4.5）根据贝叶斯公式：p（c?=b,xtb,at,t=kBf,0）=p（c（=b）p（t=k）p（&|%b，c；=bfB）p（xtlbfft=k）（公式4.6）既然真实答案在候选答案上的先验分布是未知的，我们假设真实答案服从一个均匀分布，换句话说，真实答案是b的先验概率，形式为p（c；=b）,对于所有的候选答案来说是一个常量：p（c；=b）=,be1,2,8（公式4.7）根据朴素贝叶斯模型的假设，用户与用户之间的作答是互相独立的：P%b，c；=bfBy）=nT'p（小他i，c；=b,B）（公式4.8）P（4,iktM，c；=b,B）的含义是给定当前正确答案和正确性数组的情况下，用户回答某个答案的概率。如果用户答案为当前正确答案，p（4,i|%b,iC=b,B）显然是1,如果用户答案非当前正确答案，那么他回答所有其他候选答案的可能性相同，均为上：,、(l,b,i=lPdi殉EiC=b,B)=1(公式4.9)0，狗以一U和用户与用户之间的作答相互独立同理，正确性矩阵中的元素之间也是彼此独立