计算机应用   2016, Vol. 36 Issue (10): 2777-2783  DOI: 10.11772/j.issn.1001-9081.2016.10.2777
0

引用本文 

王青, 谭良. 基于用户主题精确感知大数据群体计算任务分配算法[J]. 计算机应用, 2016, 36(10): 2777-2783.DOI: 10.11772/j.issn.1001-9081.2016.10.2777.
WANG Qing, TAN Liang. Optimization algorithm for accurately theme-aware task assignment in crowd computing on big data[J]. JOURNAL OF COMPUTER APPLICATIONS, 2016, 36(10): 2777-2783. DOI: 10.11772/j.issn.1001-9081.2016.10.2777.

基金项目

国家自然科学基金资助项目(61373162);四川省科技支撑计划项目(2014GZ007)

通信作者

王青(1992—),女,湖南衡阳人,硕士研究生,主要研究方向:大数据处理、数据挖掘、机器学习.E-mail:wq920121@126.com

作者简介

谭良(1972—),男,四川成都人,教授,博士,CCF高级会员,主要研究方向:可信计算、网络安全、云计算、大数据处理

文章历史

收稿日期:2016-03-15
修回日期:2016-06-21
基于用户主题精确感知大数据群体计算任务分配算法
王青1, 谭良1,2    
1. 四川师范大学 计算机科学学院, 成都 610101 ;
2. 中国科学院 计算技术研究所, 北京 100190
摘要: 针对大数据任务中海量数据分析需求、复杂认知推理挑战和传统计算中随机分配任务算法的低效性以及互联网用户的虚拟性、不确定性等问题,提出了一种基于用户主题精准感知的迭代式任务分配算法。首先,通过基于自适应模糊聚类与主题提取模型相结合的方法提取已发布群体任务的主题,然后构建特定任务模型和用户模型计算各关联度,再利用已提交高质量答案的历史任务迭代地检测新用户的真实主题并计算初始准确率;其次,通过逻辑回归(LR)方法预测用户能参与到某类任务的可能性并得到参与用户候选序列,在充分了解用户真实主题和对应主题上的准确率以及用户诚信度的情况下进行精准分配。通过与随机算法在模拟实验中对准确率进行比较,实验结果表明所提算法准确率比随机算法高20个百分点以上,并随着训练数据量的增加而提高,在相似任务上的准确率更是接近100%。实验验证所提算法更精准、尤其适用于大数据环境,并一定程度上节约了随机算法需多次重复分配确保准确率的花销
关键词: 群体计算    主题匹配    大数据    逻辑回归    人机协作    
Optimization algorithm for accurately theme-aware task assignment in crowd computing on big data
WANG Qing1, TAN Liang1,2     
1. College of Computer Science, Sichuan Normal University, Chengdu Sichuan 610101, China ;
2. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
Abstract: Aiming at the problems of massive data analysis requirement, complex cognitive inference in big data tasks, low efficiency of random assignment algorithm and virtual property and uncertainty of Internet users, an optimization algorithm for accurately theme-aware task assignment in crowd computing on big data was proposed. Firstly, the themes in crowd computing were extracted by method which combined with theme extraction model with fuzzy-kmeans adaptation, then the correlations were computed through task model and user model. Secondly, new users' real theme and initial accuracy were tested by historical tasks with high quality answers. Lastly, the probability that a user can participate in a certain kind of task was calculated and a sequence of candidate sequences was predicted by Logistic Regression (LR), and then the appropriate workers were assigned accurately to the tasks. Compared with random algorithm, the accuracy of the proposed algorithm was more than 20 percentage points higher, which increases with the increase of the training data, and the accuracy was nearly close to 100% especially in correlation tasks through full training. The simulation results show that the proposed algorithm has a higher accuracy with more cost-effective and performance in big data environment
Key words: crowd computing    theme match    big data    Logistic Regression (LR)    human-computer cooperation    
0 引言

随着大数据时代的到来,数据的快速增长成为许多行业共同面对的宝贵机遇和严峻挑战,同时它蕴含着巨大的价值,为人们更加全面与深入地感知、认识和控制现实世界提供了极其丰富的信息和知识。由于大数据的4V特点(即Volume、Variety、Value、Velocity),大数据的分析和处理给传统计算方法带来了严峻的挑战[1]。针对大数据计算中海量计算分析和复杂认知推理需求并存的技术挑战,传统的基于计算机的算法已经无法满足日益苛刻的数据处理要求,群体计算是有效的解决途径[2-4]

关于“群体计算”的准确定义,学术界目前缺乏统一的表述。维基百科给出的定义是:“群体计算是人群和机群协作的一种计算模型,它通过整合互联网上大量未知用户(人群)和计算资源(机群)来处理现有计算技术难以完成的复杂任务。” 在群体计算过程中,当前绝大部分方法均对任务随机分配给用户[5-8]。而“大数据群体计算”主要研究如何通过人机协作的方法来解决大数环境下的复杂计算任务。它提供了一种组织群体智力的全新方式,重点在于人机协作的计算模型以及优化制机制等。值得注意的是,大数据处理是群体计算产生的重要动机,

而大数据群体计算的核心是将群体计算技术应用于大数据问题求解,对于知识挖掘和分析决策具有重要而现实的意义。

在真实的大数据应用环境中,联网用户具有虚拟性、繁杂性,并拥有不同的知识背景、诚信程度,因此不能简单随机分配大数据分析和处理任务。为了解决这个问题,文献[4]提出基于“众包”改进的基于主题感知的迭代群体计算模型。该模型利用大量测试问题迭代检测不同人群的专业背景和完成任务的准确率,在充分了解用户真实主题和准确率的情况下为他们分配合适的问题,克服了“众包”模式三个方面的困难:1)用户主题的感知;2)估计用户在不同主题上准确率;3)设计了一种针对用户主题的任务分配算法。但该模型仍然存在准确率不高以及测试问题成本过高、针对不同主题的提取具有不稳定性等缺陷。为此,本文提出了一种新的主题精确感知新型分配策略。它通过分析任务的关联度、测试人群的专业领域来找到用户真实主题,提出任务分配方案,计算参与者完成任务的准确率,并构建用户的信用体系,在充分了解人群的专业领域、准确率和诚信度的情况下为他们分配合适的问题,实现完成任务的质量和效率最大化。

1 相关工作

大数据群体计算与众包、群智感知计算等概念有着密切的关联,但也存在本质的区别。大数据群体计算主要解决如何协同机器和人来解决发布在众包平台上的大数据问题。目前已有一些关于突破传统围绕机器式的数据计算模型的研究。

1.1 群智感知计算

随着无线移动终端设备的爆炸式普及,移动感知和众包模型[9]的结合产生了新型物联网感知模式,即群智感知计算。在群智感知计算中,大量普通用户使用移动设备作为基本感知单元,通过移动互联网进行协作,实现感知任务分发与感知数据收集利用,最终完成大规模、复杂的社会感知任务。如基于Facebook、Twitter等在线社会媒体数据的认知与分析的社会计算方法[10]。物联网应用中,刘云浩[11]提出“群智感知计算”,通过发挥“人多力量大”的特点,将大量草根用户拧成一股绳,形成随时随地、与人们生活密切相关的感知系统;赵妍妍等[12]通过“众包游戏软件”构建了中文的语义相关性词典;岳德君等[13]提出了“阶段式动态众包质量控制策略”。

1.2 众包

传统的“众包模式”[9]是一个公司或机构把过去由员工执行的工作任务,以自由自愿的形式外包给非特定的(而且通常是大型的)大众网络的做法。由于起步晚,国内还处于发展阶段[14-15]。但作为一种新型的商业模式,众包在中国制造向中国创造转型的过程中发展潜力巨大。这种新型的商业模式是值得借鉴的。人们对于一些产品不再像以前那样只会被动接受,他们更愿意参与到产品设计的范畴。小米“众筹”平台就是一个成功的例子,它成功实现了“双赢”,既满足了消费者需要的“参与感”,也让自己赚到了钱。可以说,对于当今消费市场,参与感是个关键词。

这种任务分配方法并不考虑参与者的专业背景知识,只是将任务简单地发布出去而后再收集网络大众提供的答案和反馈。

这种任务分配方式有其本身的优点,但是该分配方式对任务本身有着苛刻的要求,难以适应大数据计算中繁杂多源数据分析和处理的任务,这种不加区分直接将任务交给网络普通大众的分配方式是需要优化的。而且,在数据处理质量层面,该随机任务分发方法为了达到期望的准确率不得不将同一任务交给多个用户来完成,在数据量大时这种重复问题分配方式将带来巨大额外的开销。

综上所述,目前,针对大数据群体计算的研究工作不多,还缺少对大数据群体计算中任务管理、数据管理、质量管理[16-17]等方面的研究工作,特别是为了更快速、更准确地处理大数据相关的计算任务,亟须一种用户主题精确感知新型任务分配计算模型。

2 基于用户主题精确感知的任务分配

为进行大数据群体计算任务的合理分配,在“众包”模式下,本文提出了一种新型的用户主题精确感知任务分配方法。该方法在进行任务分配时,不仅对发布方提交的任务进行预处理,同时也对接收方的真实主题以及对应主题的准确率、诚信度等进行建模。在任务分配过程中,接收方精确感知主题并被迭代分配任务,从而使任务分配更准确,更有针对性。基于用户主题精确感知的用户任务分配和处理的计算模型如图 1所示。

图 1 大数据群体计算用户主题感知任务分配算法流程示意

具体的任务分配和处理流程描述如下:

①各发包方通过“众包”平台发布大数据分析和处理群体任务;

②“众包”平台对大数据分析和处理群体任务进行收集,通过任务模型建模后进行预处理然后发布;

③新用户预先通过用户模型进行初始化,任务发布后各接包方提出接包申请;

④通过主题精确感知模型对任务主题的感知,进行初步用户推荐;

⑤对推荐结果进行准确率评估;

⑥对高准确率匹配结果通过“众包”平台进行任务分发;

⑦接包方提交答案,平台把答案转发给发包方;

⑧发包方对结果进行反馈;

⑨“众包”平台更新对应用户模型的用户信息。

2.1 大数据群体计算任务模型

根据图 1,各发包方在“众包”平台上提交大数据分析和处理群体任务时,任务数量多、类型繁多,所以平台需要构建能批量处理大数据群体任务的任务模型。

2.1.1 任务模型

定义1 任务模型是一个任务属性行向量task=(T,Pro,L,S,Uc,C_rate,A_rate)。其中:T代表任务自身属性以及对任务的描述;Pro代表任务对用户擅长的领域需求;L代表任务难易程度;S代表任务之间关联度;Uc代表完成任务的用户数需求;C_rate代表任务对用户最低诚信度需求;A_rate代表当次任务对用户准确率需求。

任务模型用矩阵Tm×n存放,其中:m行代表m个用户,第n列表示任务的第n个属性。

2.1.2 任务预处理

“众包”平台如何能够正确判别企业或组织提交的任务所属的主题领域,从而找到处理该任务的最优解决对象呢?本文方法是通过“众包”平台首先应对企业或组织提交的任务进行预处理,采用算法1提取任务的主题。

算法1 主题提取算法。

输入 群体任务集Task={task1,task2,…,taskn}。

输出 各类任务的主题领域集合Pro

1) 首先通过聚类算法2对群体任务聚合得到聚类结果集C={C1,C2,…,Ck}。

2) 然后通过算法3挖掘聚类结果集C,发现每类任务的主题句的结果集Topic={C_topic1,C_topic2,…,C_topici}。

3) 对结果集Topic再次采用算法2进行聚类分析,直到主题Topic不再变化。

4) Pro=Topic

5) 返回Pro

在算法1中,聚类算法用了算法2、主题提取用到了算法3。通过对常用聚类方法K-means方法、K-medoids方法、基于随机选择的聚类算法(Clustering Algorithm based on RANdomized Search,CLARANS)、利用层次方法的平衡迭代规约和聚类(Balanced Iterative Reducing and Clustering using Hierarchies,BIRCH)方法等分析其是否能用于大数据量、是否能应付不同的数据类型、是否能发现不同类型等算法特性,本文选择了能在云平台上对大数据群体任务进行聚类的算法:自适应模糊聚类算法(Fuzzy-kmeans adaptation),它是用隶属度确定每个数据点属于某个聚类的程度的算法,可以自适应地确定聚类中心个数并作为其他分析算法的预处理步骤。

算法2 Fuzzy-kmeans adaptation聚类算法。

输入 群体任务集Task={task1,task2,…,taskn}。

输出 k个聚类的结果Cj(j=1,2,…,k),2≤kn

1) 随机得到自适应k个模糊聚类中心Cj并初始化,设迭代次数为count=0。

2) 计算每个taski(1≤in)到聚类中心Cj隶属函数Fij (Fij代表第i个任务对第j个聚类中心的隶属度):${{F}_{ij}}={{\left( \mathop{\sum\limits_{c=1}^{k}{\left( \frac{\left\| Tas{{k}_{i}}-{{C}_{j}} \right\|}{\left\| Tas{{k}_{i}}-{{C}_{c}} \right\|} \right)}}^{\frac{2}{m-1}} \right)}^{-1}}$,其中:m是模糊指数,m∈(1,∞),最佳取值为[1.5,2.5],根据经验此处取值m=2;‖taski-Cj‖表示第i个任务数据与第j个聚类中心之间的欧几里得距离。对于所有任务到每个聚类中心隶属度总和满足$\sum\limits_{j=1}^{k}{F(i,j)}=1;i=1,2,\cdots ,n$,其中:i=1,2,…,n;k为聚类中心数。

3) 根据2)中各点隶属度程度,计算聚类中心:

${{C}_{j}}=\frac{\sum\limits_{i=1}^{n}{\mathop{F}_{ij}^{m}\cdot Tas{{k}_{i}}}}{\sum\limits_{i=1}^{N}{\mathop{F}_{ij}^{m}}}$

4)根据Cj的变化,重新计算隶属度;计算目标函数:

${{J}_{m}}=\sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{k}{\mathop{F}_{ij}^{m}}}{{(\left\| Tas{{k}_{i}}-{{C}_{j}} \right\|)}^{2}}$

如果Jm不收敛,count=count+1并返回步骤3)。

5) 返回聚类的结果Cj(j=1,2,…,k)。

主题模型是指对文字中隐含主题的一种建模方法、语义挖掘的利器。它克服了传统信息检索中文档相似度计算的缺点,并且能够在海量互联网数据中自动寻找出文字间的语义主题,其中统计主题模型(Latent Dirichlet Allocation,LDA)是一种非监督学习技术,可以用来识别大规模文档集(document collection)或语料库(corpus)中潜藏的主题信息,这种方法将每一篇文档视为一个词频向量,从而将文本信息转化为了易于建模的数字信息。经实验验证LDA适应于本文研究对大数据环境下群体任务的主题提取。

算法3 主题提取模型LDA。

输入 k个聚类的结果Cj(j=1,2,…,k),Dirichlet参数α(文档主题的超参数)、β(词的超参数)。

输出 每个聚合类的对应的主题Topic

1) 随机得到分布参数αβ(参数随着训练和学习过程自动变化)。

2) 对于任一聚类结果Cj,把构成Cj的每一个任务看作一个有n个不同单词的词序列W{w1,w2,…,wn},对于K个结果集Cj中涉及的所有不同单词组成v个词的大集合W,wi表示序列Wi个词,对于每一个wi到主题服从泊松分布。

3) 结果集Cj到主题发生的概率P(θ|α)得到主题分布θ

4) 对结果集Cj,按照以下方式从大集合W得到主题词WordiW:

①从Dirichlet分布中以概率P(Zi|θ)选择某一个多项分布Z,选择Zi代表当前选择的主题;

②按照当前主题Zi下的多项分布概率P(Wordi|Zi),选择一个单词Wordi;

注意βZ也是多项分布,是一个K×V的矩阵,表示从ZiWordj的产生概率,即: βij= p (Wordj=1|Zi=1),β记录了某个主题条件下生成某个单词的概率。

2.1.3 任务关联度

不同的任务所需要的用户是不一样的。由于大量的任务之间具有紧密的联系,一旦算法获知用户曾经很好地完成某个特定的任务,那么有理由相信和该任务紧密相关的任务也有较高的可能性由该用户来完成,因此计算任务之间的关联度有实际意义。关联度估算主要取决于两个因素:一个是任务所属主题领域,另一个是两个不同任务之间的相似度。根据经验,权重为gl分别占80%与20%。最终将权衡这两个因素来决定任务之间的关联度。

当任务属于同一个主题领域Proi时,只需计算得到任务之间描述的相似度,然后得到各个任务之间关联度的权重系数μtask,值越大表示任务相关性越大,即用户能完成相关任务的准确率越高。

相似度计算的方法有很多,为应对预处理之后的大数据群体任务,本文选择了基于空间权值向量Ochiai coefficient余弦定律的余弦度量法,它不受限于数据规模、应用相对广泛、效果精确,并易于在云平台上改进和扩展。本文中,任务可以抽象为词语的向量,余弦度量法通过计算两个任务向量的夹角余弦值来衡量两个任务的相似度。

假设W={w1,w2,…,wn}表示描述任务task1task2时出现的所有词集合。对应集合W,描述task1时每个词的出现次数为:c1i(1≤in);描述task2时每个词的出现次数为:c2i(1≤in);不出现则相应计数为0。分别可以表示为向量task1=(c11,c12,…,c1n)和task2=(c21,c22,…,c2n)。相似度计算如下:

$DescribeSimilary(Task1,Task2) = {{\sum\limits_{i = 1}^n {(c{1_i} \times c{2_i})} } \over {\sqrt {\sum\limits_{i = 1}^n {(c{1_i}^2)} \times \sum\limits_{i = 1}^n {(c{2_i}^2)} } }}$

DS=DescribeSimilary(task1,task2)

任务关联度为:

μtask=g·TopicSimilary(task1,task2)+l·DS

2.2 群体计算用户模型

根据图 1可知,平台将发包方提交的群体任务分发给接包方时,由于接包方用户多,其知识、智慧、经验、技能均存在差别。为了找到适合执行提交任务的接包方,本文采用用户信息地图式建模,使得符合条件的用户收到任务,形成候选序列,然后通过提出的基于主题感知任务分配方案合理分配任务,最终完成任务,因此平台需要构建能处理大数据群体任务的用户模型。

由于用户之间存在相似性,当新用户申请接包时,只需通过计算用户相似度μuser,通过相似度找到参与过群体任务的相关用户初始化新用户。

2.2.1 用户模型

定义2 用户模型是一个用户属性行向量User=(u,Pro,E,C_rate,A)。其中:u代表在“众包”平台上注册用户;Pro代表用户擅长的领域;E代表用户完成过的群体计算任务的经验说明;C_rate代表用户在任务执行中的真实诚信度;A代表用户能力胜任度;Pro是一个二元组Pro{Proi:Skill,Experience},其中:Skill代表用户技能;Experience代表用户在Skill上的技能经验;A用百分比表示,主要根据用户当前准确度和历次任务完成中的每次准确率的变化情况评判并实时更新。

用户模型采用矩阵Um×n存储,其中:第m行代表第m个用户,第n列表示该用户的第n个属性。

2.2.2 用户属性初始化

对于申请接包的用户,需要对他们的一些属性进行初始化。

1) 能力胜任度以及擅长领域初始化。

能力胜任度A记录用户不同主题任务经验的平均准确率,用户i完成j主题任务的准确率为A_rateij,那么用户i能力胜任度

${A_i}{\rm{ = }}{1 \over n}\sum\limits_{j{\rm{ = }}1}^n {A\_rat{e_{ij}}} $

其中:n表示主题个数。

①当用户i从未参与过群体任务,根据该用户不完整属性计算相似度系数μuser,得到用户能力胜任度:

Ai=Max(μuser×ASimilarityUser),Proi=ProSimilarityUser

用户越相似,主题和准确率越接近。

②当用户i参与过群体任务,计算该次主题j任务与用户历史任务的关联系数μtask,预测用户完成任务准确率为:

A_rateij=Max(μtask×A_rateSimilarityTaski)

所以用户完成该次主题j任务的准确率A_rateij=Max(Ai,A_rateij)。

2) 诚信度初始化。

①当用户i从未参与过群体任务时,给予用户参与的权限,i用户诚信度C_ratei等于初次参与j任务所需的诚信度C_ratej

②当用户i参与过群体任务时,

$C\_rat{e_i} = {1 \over n}\sum\limits_{i = 1}^n {{{C{R_i}} \over {C{Y_i}}}} $

其中:n表示任务数;CRiCYi分别代表实际完成任务准确率和预测完成任务准确率。

2.3 用户主题感知

当企业发布某类任务或项目时,平台对申请任务的用户的真实主题分布和准确率可能并不了解,需要对申请参与接包的用户进行主题预测与捕获,然后进行推荐,从而提高任务整体的完成质量。

2.3.1 使用逻辑回归算法感知用户主题

为了解决参与大数据群体任务用户的不确定性和多样性,本文利用逻辑回归(Logistic Regression,LR)的适用性[18-19]:各个特征之间不需要满足条件独立假设,但各个特征值的贡献是独立计算的。它既可用于分类,也可用于预测。本文中逻辑回归主要用于预测用户能准确完成某类任务概率,事先预知的预测类别数为当前已得到的群体任务的主题数。通过阈值设置,预测到参与某类任务的用户候选序列。

算法4 预测完成群体任务的候选用户序列算法。

输入 群体任务集Task={task1,task2,…,taskn}、用户集合U={User1,User2,…,Userm}。

输出 主题领域Proi,Proi对应用户序列Ui=(i=1,2,…,m),Ui⊆U。

1) 由算法1得到群体任务聚类结果集Ci(1≤i$ \ll $n)对应的主题Proi(1≤i$ \ll $n)。

2) 计算用户参与Proi主题的可能性:P(Proi)=λTU

3) 引人归一化Sigmoid函数:

${\mathop{\rm g}\nolimits} (P(Pr{o_i})) = {1 \over {1 + {e^{ - P(Pr{o_i})}}}}$

4) 设置得分阈值r,如果目标函数g(P(Proi))≥r,得到主题Proi用户候选用户序列Ui

5) 返回UiProi

λ是算法在训练过程中学到的属性的权重列向量λ(λ1,λ2,…λn),r需要根据需求设置。

2.3.2 捕获候选用户真实主题

当预测到参与用户的主题后,算法需要验证和捕获他们的真实主题和相应准确率,得到真正参与到某个主题的任务的用户序列,从而使得任务分配更加精准。

算法5 捕获候选用户真实主题与准确率算法

输入 主题领域Proi,Proi对应用户序列Ui(i=1,2,…,m),UiU

输出 候选序列Ui各用户真实主题Proi与在该主题上准确率A_ratei(i=1,2,…,m)。

1) 如果用户j从未参与过群体任务:

a) 初始化可知:用户j的初始化Aj 和Proj

b) 用已提交答案、主题为Proi的历史问题去测试,得出用户该主题实时准确率A_rateji。如果A_ratejiAj,那么该用户真实主题为测试问题主题Proi;否则为Proj

c) 更新用户主题和准确率。

2) 如果用户j参与过群体任务:

a) 预测用户能完成主题Proi的准确率为:A_rateji=Max(μtask×A_rateSimilarityTaskj),并重新计算该用户能力胜任度Ai(平均准确率)。

b) 如果方差${1 \over n}\sum\limits_{i = 1}^n {{{(A\_rat{e_{ji}} - {A_j})}^2}} $变小,用户真实主题是当前主题Proi

c) 否则,真实主题为原来的主题Proj

3) 返回候选用户序列Ui真实主题P与准确率A_rate

对于此处涉及的测试问题的数量,理论值是越多越好,这样能够得到参与方对该主题的一个更准确的实时准确率。但由于群体任务数量巨大、种类繁多,如果每次都使用较多测试问题对每个主题进行测试,那么会使得主题感知分配过程的时间消耗变大,代价变大,在实际应用中应该根据真实需求进行取舍,一般只用于测试新用户,一般测试问题占各类主题任务总数的5%。

2.4 群体任务分配算法

算法6 推荐完成群体任务的精准用户序列算法。

输入 群体任务集Task={task1,task2,…,taskn},用户集U={User1,User2,…,Usern}。

输出 每个任务taski(i=1,2,…,n)最终用户序列Ui

1) 首先通过算法1得到任务taskiProi(1≤i$ \ll $n),由算法4预测得到参与任务taski的人数为num候选用户序列Ui={User1,User2,…,Usernum},1<num$ \ll $n

2) 再由算法5得到1)任务taski候选用户序列Ui中每个用户对应的真实主题和真实准确率,根据任务taski对用户擅长的领域需求Proi,筛选出该主题领域的用户,更新候选序列设为Ui,并设置对应的用户准确率AiAi1。

3) 根据任务taski对准确率需求A_ratei,筛选出1)中Ui能力胜任度A大于等于A_ratei的用户,更新用户序列U"i和对应的准确率Ai记为Ai2

4) 利用K-L方法[20]计算随着Ai1、Ai2变化的信息增益,形成以Max(Ai)+Min(K-L(Ai1,Ai2))降序排列的新用户序列Ui

5) 根据任务taski对用户诚信度C_ratei需求,选取4)中Ui中用户诚信度C_rateC_ratei的用户。

6) 再根据任务taski对完成任务所需用户数Uc需求,选取5)中候选用户的前floor(120%Uc)个用户组成最终序列Ui

7) 返回各个任务taski(i=1,2,…,n)对应的最终用户序列Ui

3 实验和结果分析 3.1 实验环境

本文采取的实验均在单机开发环境下简化实现,并通过实验评价指标的对比验证本文算法的有效性、准确性和经济性。

仿真实验环境:Windows7+MyEclipse+Maven+Mahout API。

Mahout最大的优点就是基于Hadoop实现,把很多以前基于单机上运行的算法转化为了MapReduce模式,这样大大提升了算法可处理的数据量和处理性能,在大数据群体计算中尤为重要。虽然Mahout最初应用平台是Hadoop集群平台,现经扩展,它的算法已经能单机运行,结合Java可进行二次开发,相对纯Java编写的算法更优化,效率更高。

3.2 实验设计

群体计算的任务分配是利用现有“众包平台”进行发布,由于在大数据环境下,任务复杂度高、形式多样、数量大,所以本文的分配过程是事先对群体任务和用户预处理再进行仿真迭代分配的,包括:1)任务方模型初始化;2)接收任务方模型初始化;3)用户主题感知过程动态匹配;4)分配结果准确率显示。

实验数据:

1) 任务数据。

数据集[21]:Car Evaluation(通过汽车6个属性给出评价)、Wine-quality(通过红酒的12个化学成分数据分析质量,难度系数较大)和Music(快速傅里叶变换先预处理), 作为任务Titaski自身属性。

例1 Car测评 task{T{{买入价、维护费、车门数、可容纳人数、后备箱大小、安全性}→性能测评},Pro{汽车:{汽车市场营销,2年},{汽车制造,1年}…},L{low},S{初始值},Uc{2},C_rate{0.8},A{0.85}}。任务模型释义:通过任务T的六个自身属性的不同值,给出关于汽车的性能测评(不可接受、可接受、好等),任务需求汽车领域P两个技能以及经验,难度等级低,任务需求人数2人,诚信度需求80%以上,准确率需求85%以上。

例2 Music歌名竞猜类task。

预处理:

1) 对发布的music任务Music主题,再对旋律处理后聚类,得到音乐曲风分类{Pop,dub,trip-hop,rock…}。

task{T{{Music旋律}→曲风竞猜},Pro{Music:{Pop,2年}…},L{Middle},S{初始值},Uc{3},C_rate{0.9},A{0.95}}。释义同上。

例3 是例2任务结束后再发布的任务{歌名竞猜}task,任务形式同例2。

例4 是例2任务结束后再发布的任务{Music歌手竞猜类}task,任务形式同例2。

例3和例4是用来测试在基于用户主题感知分配方式下群体计算对相关任务的用户匹配。

2) 用户数据。

根据用户信息地图构造用户矩阵,填充并进行预处理。在本文实验下,构造500个用户,分别使用随机分配算法和基于主题感知算法在三个真实数据集上进行实验。

User{u:{Pro{{Music:Pop,2年}…},E{{完成音乐任务2次}…},C_rate{0.87},A{0.95}}}

在本文模拟实验中,使用上述实验数据。通过2.1.2 节中的算法来得到群体任务主题;由于每个问题的描述由大小为20~100的字符串构成,通过2.1.3节中的算法来比较两个字符串的相似度,即任务相似度;在模拟实验初始时本文首先将关联度高的任务分为若干个集合。在实验过程中,应用算法3时,考虑到算法3的收敛性和适应性,对于超参数α、 β值的选取,本文首先利用测试集,使用网格搜索的方式找出最优的超参数取值,得到对称的标量值(即每个值都一样),再根据文献[22]中建议的固定点迭代方法更新,得到α、 β的取值分别为0.1、0.01。应用算法4时,考虑到资源的合理利用,对于预测分类临界值r的选择取值太高时,查全率变高,使得查询条件过于严格,得到潜在用户会过少;反之,预测结果失真,资源浪费变多,针对本实验,经过0-1损失函数计算代价,r综合取值为0.85。

3.3 实验结果与分析 3.3.1 实验结果

1) 三种数据集各200例,三种不同算法下的准确率情况。

根据图 2分析可知随机算法分配结果的准确率基本处于45%~65%,而且在难度系数较大的Wine任务上得到的准确率明显降低;通过对文献[4]模拟实验中难度处于beta(5,1)下的结果进行分析,该文献提出的主题感知算法的准确率基本处于78%左右,在Wine数据集和Music数据集上准确率高于car数据集;而基于本文算法的准确率基本保持在75%~85%,通过逻辑回归计算可能性可知,由于任务准确分配给擅长该领域的用户,在数据集Wine上得到的结果可以保持在较高的准确率。本次实验检验了本文所提出的任务分配算法的有效性,并优于随机分配算法。

图 2 真实数据上模拟实验准确率

2) 任务数量不同对三种算法准确率的影响。

图 3显示了任务数变化的实验准确率结果。分析得到随机分配算法结果的准确率基本处于45%~65%;基于文献[4]模拟实验中每一轮中用户完成任务的准确率的变化情况得出,该算法随着任务数据量和迭代次数的增加,准确率是逐步上升再趋于稳定;而基于本文算法的准确率随着任务数量的增加,准确率变化趋势也是逐步上升并趋至稳定,这主要是因为本文方法利用测试问题以及逻辑回归算法感知主题,随着迭代轮数的增多,算法得到了充分的训练,对主题的感知则愈发准确。

3) 针对相似任务在三种不同算法下用户完成任务的准确率变化情况。

图 4显示了完成基于Music旋律的曲风竞猜任务数之后,公司或者企业再发布基于该Music旋律的歌名竞猜、歌手名字等相似群体任务,用户完成任务的准确率变化情况。根据图 4分析得到随机算法分配得到的准确率处于45%~65%,随机性较大;基于文献[4]真实实验中用户完成Music任务的准确率结果分析可知,最终准确率提升可至100%;而基于本文算法的准确率则充分利用了用户对任务主题的感知,以及对相似任务进行合理推荐用户的处理,合适地为任务挑选相关领域的用户,把相似任务发布给上一轮完成任务准确率高的用户,他们提交答案的准确率提高,甚至可能接近100%。

图 4 任务相似性对准确率的影响
3.3.2 实验分析

本次实验是在仿真环境下进行的模拟实验,准确率结果存在一定误差。从上述3组对比实验中可知:对于群体任务的分配问题,随机分配算法整体准确率水平不高。如果要达到群体任务需求的准确率,需要对任务进行多次的重复随机分配,但随着任务数量的增加导致成本提高;而基于文献[4]提出的实验中,虽然准确率得到了保证并且算法在真实实验中也得到了验证,但是在检测用户主题领域时,为了确保准确率,需要增加整体测试问题的数量,随着更多的测试问题也带来更多的花费(需要更多人工的标注),所以需要综合考虑预算;而基于本文算法在随着任务数量的增加、任务种类的不同、相关任务的完成方面,通过模拟实验得出的结果分析可知,能达到文献[4]算法得到的准确率,且一直维持在一个较高的水平。由于本文算法在用户感知过程中使用了已知答案的测试问题测试以及领域属性分类、独立属性匹配等,从而大大节约了成本,并使用算法既提高了准确性又极具经济性。

4 结语

本文算法首先利用用户之间、任务之间的相似度分别对用户和任务进行聚类、主题提取,再使用逻辑回归对用户的各个属性进行训练得到权重,进行预测分类,分类出能完成某类群体任务的用户,通过设置阈值,选出候选序列,从而再根据群体任务的要求进行淘汰进而实现精准的任务分配策略。最后通过实验验证了本文算法的有效性,与文献[4]算法相比,不仅提高了预测精确度还节约了成本。在接下来的研究中,将增加参与方情感分析和团体合作能力测试、简化任务发布方发布任务需求操作、跟进任务完成进度、考虑任务的时效性等;继续探索一种更加完善的分配机制,并尝试在云平台上进行大数据群体任务上实现精准分配。

参考文献
[1] 孟小峰, 李勇, 祝建华. 社会计算:大数据时代的机遇与挑战[J]. 计算机研究与发展, 2013, 50 (12) : 2483-2491. ( MENG X F, LI Y, ZHU J H. Social computing in the era of big data: opportunities and challenges[J]. Journal of Computer Research and Development, 2013, 50 (12) : 2483-2491. ) (0)
[2] HOSIO S, GONCALVES J, KOSTAKOS V, et al. Crowdsourcing public opinion using urban pervasive technologies: lessons from real-life experiments in Oulu[J]. Policy & Internet, 2015, 7 (2) : 203-222. (0)
[3] DOUGLAS V A, AULTMAN BECKER A. Encouraging better graphic design in libraries: a creative commons crowdsourcing approach[J]. Journal of Library Administration, 2015, 55 (6) : 459-472. doi: 10.1080/01930826.2015.1054765 (0)
[4] 张晓航, 李国良, 冯建华. 大数据群体计算中用户主题感知的任务分配[J]. 计算机研究与发展, 2015, 52 (2) : 309-317. ( ZHANG X H, LI G L, FENG J H. Theme-aware task assignment in crowd computing on big data[J]. Journal of Computer Research and Development, 2015, 52 (2) : 309-317. ) (0)
[5] 张引, 陈敏, 廖小飞. 大数据应用的现状与展望[J]. 计算机研究与发展, 2013, 50 (S2) : 216-233. ( ZHANG Y, CHEN M, LIAO X F. Big data applications: a survey[J]. Journal of Computer Research and Development, 2013, 50 (S2) : 216-233. ) (0)
[6] 孟韬, 张媛, 董大海. 基于威客模式的众包参与行为影响因素研究[J]. 中国软科学, 2014 (12) : 112-123. ( MENG T, ZHANG Y, DONG D H. The research on influencing factors of crowdsourcing participating behavior based on wickey model[J]. China Soft Science, 2014 (12) : 112-123. ) (0)
[7] 叶晨, 王宏志, 周小田, 等. 基于众包的电子商务数据实体分类系统[J]. 计算机研究与发展, 2013, 50 (S1) : 405-409. ( YE C, WANG H Z, ZHOU X T, et al. Codesourcing-based e-commerce entity classification system[J]. Journal of Computer Research and Development, 2013, 50 (S1) : 405-409. ) (0)
[8] 叶伟巍, 朱凌. 面向创新的网络众包模式特征及实现路径研究[J]. 科学学研究, 2012 (1) : 145-151. ( YE W W, ZHU L. Study on the characteristics and achieving pathes for crowdsourcing innovation[J]. Studies in Science of Science, 2012 (1) : 145-151. ) (0)
[9] 冯剑红, 李国良, 冯建华. 众包技术研究综述[J]. 计算机学报, 2015, 38 (9) : 1713-1726. ( FEND J H, LI G L, FEND J H. A survey on crowdsourcing[J]. Chinese Journal of Computers, 2015, 38 (9) : 1713-1726. ) (0)
[10] 王飞跃, 王晓, 袁勇, 等. 社会计算与计算社会:智慧社会的基础与必然[J]. 科学通报, 2015, 60 (S1) : 460-469. ( WANG F Y, WANG X, YUAN Y, et al. Social computing and computational societies: the foundation and consequence of smart societies[J]. Science China Press, 2015, 60 (S1) : 460-469. ) (0)
[11] 刘云浩. 群智感知计算[J]. 中国计算机学会通讯, 2012, 8 (10) : 38-41. ( LIU Y H. Crowd sensing computing[J]. Communications of the China Computer Federation, 2012, 8 (10) : 38-41. ) (0)
[12] 赵妍妍, 秦兵, 刘挺. 文本情感分析[J]. 软件学报, 2010, 21 (8) : 1834-1848. ( ZHAO Y Y, QIN B, LIU T. Sentiment analysis[J]. Journal of Software, 2010, 21 (8) : 1834-1848. doi: 10.3724/SP.J.1001.2010.03832 ) (0)
[13] 岳德君, 于戈, 申德荣, 等. 基于投票一致性的众包质量评估策略[J]. 东北大学学报(自然科学版), 2014, 35 (8) : 1097-1101. ( YUE D J, YU G, SHEN D R, et al. Crowdsourcing quality evaluation strategies based consistency on voting[J]. Journal of Northeastern University (Natural Science), 2014, 35 (8) : 1097-1101. ) (0)
[14] 韩清池, 赵国杰. 基于众包的开放式创新研究:现状与发展方向[J]. 科技进步与对策, 2014, 31 (21) : 11-16. ( HAN Q C, ZHAO G J. Research on the open innovation based on crowdsourcing: state of the art and future directions[J]. Science & Technology Progress and Policy, 2014, 31 (21) : 11-16. ) (0)
[15] 朱小宁.支持任务推送的众包系统的研究与实现[D]. 北京:北京邮电大学, 2015:24-95. ( ZHU X N. Research and implementation of a crowdsourcing system supporting task routing [D]. Beijing: Beijing University of Posts and Telecommunications, 2015:24-95. ) http://cdmd.cnki.com.cn/article/cdmd-10013-1015586372.htm (0)
[16] 张志强, 逄居升, 谢晓芹, 等. 众包质量控制策略及评估算法研究[J]. 计算机学报, 2013, 36 (8) : 1636-1649. ( ZHANG Z Q, PANG J S, XIE X Q, et al. Research on crowdsourcing quality control strategies and evaluation algorithm[J]. Chinese Journal of Computers, 2013, 36 (8) : 1636-1649. ) (0)
[17] 李勇军, 郭基凤, 缑西梅. 软件"众包"任务分配方法[J]. 计算机系统应用, 2015, 24 (2) : 1-6. ( LI Y J, GUO J F, GOU X M. Software task allocation method in crowdsourcing[J]. Computer Systems & Applications, 2015, 24 (2) : 1-6. ) (0)
[18] 潘尔顺, 金垚, 叶亮. 基于逻辑回归的计数型质量特性健壮参数谨慎控制策略[J]. 上海交通大学学报(自然科学版), 2010, 44 (12) : 1711-1715. ( PAN E S, JIN Y, YE L. Robust parameter control approach with cautious control strategy for attributes quality characteristics based on logistic regression model[J]. Journal of Shanghai Jiaotong University, 2010, 44 (12) : 1711-1715. ) (0)
[19] 毛林, 陆全华, 程涛. 基于高维数据的集成逻辑回归分类算法的研究与应用[J]. 科技通报, 2013, 29 (12) : 64-66. ( MAO L, LU Q H, CHENG T. The research and application of ensemble logistic regression classification algorithm based on high dimensional data[J]. Bulletin of Science and Technology, 2013, 29 (12) : 64-66. ) (0)
[20] 孙爱程. 基于熵距离的离群点检测及其应用[J]. 无线电工程, 2012, 42 (6) : 45-47. (0)
[21] LICHMAN, M. UCI machine learning repository [D]. Irvine, CA: University of California, School of Information and Computer Science, 2013. http://cn.bing.com/academic/profile?id=140219781&encoded=0&v=paper_preview&mkt=zh-cn (0)
[22] ASUNCION A, WELLING M, SMYTH P, et al. On smoothing and inference for topic models[C]//Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence. Quebec: AUAI Press, 2009: 27-34. http://cn.bing.com/academic/profile?id=2161353674&encoded=0&v=paper_preview&mkt=zh-cn (0)