基于数据长尾特性的女巫防御真值发现方法及系统

1.本发明属于数据挖掘技术领域，具体涉及一种基于数据长尾特性的女巫防御真值发现方法及系统。


背景技术：

2.众包任务是雇佣工人完成计算机无法完成的智能任务。而在收集完工人提供的标签后，真值发现就在其中扮演聚合真值的角色，保证了聚合真值的准确性。真值发现是在纷扰杂乱的数据中，通过迭代、最优化和概率图模型等手段，聚合出任务真值的方法。在众包中，会通过激励手段刺激工人完成任务，但是这也引来了女巫攻击者。女巫攻击者会通过控制多个工人随机选择一个标签来影响任务的聚合结果，以获得任务奖励。大部分众包数据集中都存在严重的长尾问题，这将影响真值的聚合准确率。长尾现象是指大多数工人只提供很少的回答，而少数工人提供了大部分的回答。这将导致工人的权重估计不准确。比如一个工人只回答一个问题，答对则权重为1，答错则权重为0。
3.yuan等人首次解决了众包中存在的女巫攻击问题，他们提出了一个能够根据工人行为的相似性对其进行分组的sadu算法，该方法会通过分配黄金任务标识女巫组和正常组；但是，sadu算法遇到会逃避黄金任务检测的女巫工人会失效。后来，wang等人提出了tdssa算法，tdssa算法设置了女巫分数和可信分数以记录众包工人的行为，当女巫分数超过阈值时，工人会被判断为女巫工人并封禁，当可信分数超过阈值时，工人将不再被分配黄金任务；tdssa算法虽然可以抵御策略女巫攻击者的攻击，但是无法降低众包数据集长尾现象所带来的负面影响。


技术实现要素：

4.本发明的主要目的在于克服现有技术的缺点与不足，提出一种基于数据长尾特性的女巫防御真值发现方法及系统，方法能减少在估算真值的时候受长尾现象的影响，并且能抵御女巫攻击。
5.为了达到上述目的，本发明采用以下技术方案：
6.基于数据长尾特性的女巫防御真值发现方法，设有任务发布者、众包系统以及工人，方法包括以下步骤：
7.任务分配，响应工人的任务请求，根据pta算法为工人分配黄金任务或正常任务；
8.更新工人参数，如果工人分配黄金任务，则众包系统将通过黄金任务的回答情况更新工人的相关参数，包括权重、女巫分数以及可信分数；
9.更新任务真值，如果工人分配正常任务，则众包系统会记录工人对该任务的标签，在该任务收集到足够的标签后，会进行真值聚合；在真值聚合过程中，根据工人的权重，给予该工人标签相对应的权重，使得可信工人的标签在聚合结果上更有影响力；
10.方法迭代，重复更新工人参数和更新任务真值步骤，使得女巫工人被封禁，正常工人获得更准确的权重以及任务真值的变化小于阈值，最终得到真值。
11.进一步的，步骤s1具体为：
12.设众包有n个任务和m个工人，分别用t＝{t1,t2,
…
,tn}和w＝{w1,w2,
…
,wm}表示；每个任务都有一个真值，隐藏在p个候选答案中，用a＝{a
i,j
}表示工人wj关于任务ti的回答；
13.众包系统根据任务发布者的要求与预算，将同一个任务分配给f个工人；
14.在众包系统运作的过程中，系统响应工人wj的任务请求，根据工人wj的女巫分数sj和可信分数rj，根据pj(x)＝x
·
(1-rj)+sj·
(1-x)，概率性地为工人分配黄金任务或者正常任务，其中，x∈(0,1]代表黄金任务分配给工人wj的概率。
15.进一步的，可信分数rj根据工人回答黄金任务的正确率决定的；
16.女巫分数sj由工人在黄金任务上提供虚假标签的行为决定的；
17.权重由更新后的可信分数和工人提供标签的数量共同决定；
18.工人的女巫分数sj和可信分数rj初始设为0，权重设为1。
19.进一步的，步骤s2具体包括：
20.更新工人wj的权重，公式为：
[0021][0022]
其中，χ函数根据工人提供标签的数量决定其权重；当工人提供较多标签时，其权重就为标签准确率；当工人提供较少标签时，其权重则维持在一个较低的水平；γ表示当工人标签数较少时，工人权重所维持的水平；
[0023]
更新工人wj的女巫分数和可信分数，公式为：
[0024][0025][0026]
其中，sj代表工人wj在黄金任务上提供虚假多数标签的女巫攻击行为，rj代表工人wj在黄金任务中的可信表现；
[0027]
在计算出工人新的女巫分数和可信分数后，众包系统检测女巫分数和可信分数是否超过阈值η；如果女巫分数超过女巫阈值，则会将女巫工人封禁并回收其之前在正常任务中的答案；如果可信分数超过可信阈值，则会将工人设置为可信状态，此后将不会继续为其分配黄金任务。
[0028]
进一步的，女巫阈值和可信阈值根据数据集的不同设置为不同的值η。
[0029]
进一步的，步骤s3具体为：
[0030]
在收集全部工人任务标签a(ti,wj)后，将根据以下公式：
[0031][0032]
其中，1(x,y)是指示函数，当x＝y时，返回1；否则，返回0；τ(wj)代表工人wj的标签准确率；
[0033]
因此，当工人女巫分数很低时，其提供标签的权重则更倾向于工人权重而不是随机选择的权重
[0034]
进一步的，结合卡方函数和工人回答的数量和准确度，调整工人获得权重的大小，卡方函数χ可在工人提供少量回答时，以γ值主导函数结果，在工人提供大量回答时将和默认准确度得出的权重相近，由此抑制众包数据集中的长尾现象，以提高真值的准确率。
[0035]
进一步的，步骤s4中，由于在每次算法运行时，女巫工人都会动态地生成任务的标签，因此，需要重复多次求得平均值作为最终真值结果。
[0036]
本发明还包括基于数据长尾特性的女巫防御真值发现系统，系统采用本发明提供的方法进行真值发现，系统设有任务发布者、众包系统以及工人，包括任务分配模块、工人参数更新模块以及任务真值更新模块；
[0037]
任务分配模块，用于根据任务发布者的要求与预算，响应工人的任务请求，根据pta算法为工人分配黄金任务或正常任务；
[0038]
工人参数更新模块，用于初始化、更新以及记录工人的权重、女巫分数以及可信分数，并且根据工人工作情况更新；
[0039]
任务真值更新模块，用于进行真值聚合，根据工人的权重，给予工人标签相对应的权重，使得可信工人的标签在聚合结果上更有影响力。
[0040]
本发明与现有技术相比，具有如下优点和有益效果：
[0041]
1、本发明方法在进行防御女巫攻击的真值发现时，抑制数据长尾性所带来的影响；真值发现的准确率有显著的提高，且算法的总体开销较小。
[0042]
2、本发明方法相较现有的众包系统中防御女巫攻击的真值发现算法具有更广的适用性，如在女巫分数和可信分数失效后(即女巫分数和可信分数的阈值都设为1，不可能达到)，本发明方法的准确率仍能保持在较高水平，而tdssa算法的准确率则会急速下降。
附图说明
[0043]
图1是本发明方法的流程图；
[0044]
图2是本发明实施例中的众包流程图；
[0045]
图3是本发明的概念示意图。
具体实施方式
[0046]
下面结合实施例及附图对本发明作进一步详细的描述，但本发明的实施方式不限于此。
[0047]
实施例
[0048]
本实施例设有任务发布者、众包系统以及工人三个众包参与方。
[0049]
任务发布者：会发布任务并附上任务的奖励。在工人们完成以后，会按照约定给予答案和最后聚合结果一致的工人奖励。
[0050]
众包系统：将实事求是地记录工人提供的标签，并按照设定好的算法聚合出真值。在此之后，它会根据真值来发放工人的奖励。而不会被女巫攻击者控制，使得让他们更容易获得奖励。众包数据集还有长尾性，如图2所示。
[0051]
工人：会根据问题诚实地选择答案。工人回答问题的正确率与数据集候选答案个数成负相关性。工人们为了奖励基于自己的知识为任务提供答案。并且，由于奖励和权重机制的存在，他们会如实为任务提供标签。部分众包工人是被女巫攻击者控制的女巫工人，他们在同一个任务上，随机选择一个相同的标签，以达到左右聚合结果和获取任务奖励的目的。
[0052]
如图2所示，为实施例中的众包流程图。
[0053]
如图1和图3所示，本发明，基于数据长尾特性的女巫防御真值发现方法，其特征在于，，方法包括以下步骤：
[0054]
任务分配，响应工人的任务请求，根据pta算法为工人分配黄金任务或正常任务；具体为：
[0055]
设众包有n个任务和m个工人，分别用t＝{t1,t2,
…
,tn}和w＝{w1,w2,
…
,wm}表示；每个任务都有一个真值，隐藏在p个候选答案中，用a＝{a
i,j
}表示工人wj关于任务ti的回答；
[0056]
众包系统根据任务发布者的要求与预算，将同一个任务分配给f个工人；
[0057]
在众包系统运作的过程中，系统响应工人wj的任务请求，根据工人wj的女巫分数sj和可信分数rj，根据pj(x)＝x
·
(1-rj)+sj·
(1-x)，概率性地为工人分配黄金任务或者正常任务，其中，x∈(0,1]代表黄金任务分配给工人wj的概率。
[0058]
其中，可信分数rj根据工人回答黄金任务的正确率决定的；
[0059]
女巫分数sj由工人在黄金任务上提供虚假标签的行为决定的；
[0060]
工人的女巫分数sj和可信分数rj初始设为0，
[0061]
更新工人参数，如果工人分配黄金任务，则众包系统将通过黄金任务的回答情况更新工人的相关参数，包括权重、女巫分数以及可信分数；权重由更新后的可信分数和工人提供标签的数量共同决定，权重初始设为1。该步骤具体包括：
[0062]
更新工人wj的权重，公式为：
[0063][0064]
其中，χ函数根据工人提供标签的数量决定其权重；当工人提供较多标签时，其权重就为标签准确率；当工人提供较少标签时，其权重则维持在一个较低的水平；γ表示当工人标签数较少时，工人权重所维持的水平；
[0065]
更新工人wj的女巫分数和可信分数，公式为：
[0066][0067][0068]
其中，sj代表工人wj在黄金任务上提供虚假多数标签的女巫攻击行为，rj代表工人wj在黄金任务中的可信表现；
[0069]
在计算出工人新的女巫分数和可信分数后，众包系统检测女巫分数和可信分数是
否超过阈值η；如果女巫分数超过女巫阈值，则会将女巫工人封禁并回收其之前在正常任务中的答案；如果可信分数超过可信阈值，则会将工人设置为可信状态，此后将不会继续为其分配黄金任务。
[0070]
女巫阈值和可信阈值根据数据集的不同设置为不同的值η。
[0071]
更新任务真值，如果工人分配正常任务，则众包系统会记录工人对该任务的标签，在该任务收集到足够的标签后，会进行真值聚合；在真值聚合过程中，根据工人的权重，给予该工人标签相对应的权重，使得可信工人的标签在聚合结果上更有影响力；具体为：
[0072]
在收集全部工人任务标签a(ti,wj)后，将根据以下公式：
[0073][0074]
其中，1(x,y)是指示函数，当x＝y时，返回1；否则，返回0；τ(wj)代表工人wj的标签准确率；
[0075]
因此，当工人女巫分数很低时，其提供标签的权重则更倾向于工人权重而不是随机选择的权重
[0076]
结合卡方函数和工人回答的数量和准确度，调整工人获得权重的大小，卡方函数可在工人提供少量回答时，以γ值主导函数结果，在工人提供大量回答时将和默认准确度得出的权重相近，由此抑制众包数据集中的长尾现象，以提高真值的准确率。
[0077]
方法迭代，重复更新工人参数和更新任务真值步骤，使得女巫工人被封禁，正常工人获得更准确的权重以及任务真值的变化小于阈值，最终得到真值。
[0078]
由于在每次算法运行时，女巫工人都会动态地生成任务的标签，因此，需要重复多次求得平均值作为最终真值结果。
[0079]
在本实施例中，假设总共有f个工人收到了同一个任务，其中女巫工人有f
·
h％个被v个女巫攻击者控制；误差是指工人回答与任务真值不同，一个工人误差分布的方差一定程度上代表了这个工人的可信度；女巫工人并不是故意提供错误标签，它们只是并不在乎聚合结果。因此，在讨论工人的独立性这个问题上，认为整个任务中还有(f(1-h％)+v)个工人是独立的。
[0080]
使用数据集nlp和数据集dog；在现实数据集中，确定女巫攻击者和女巫攻击行为是很难实现的，因此使用女巫注入，使得nlp和dog数据集中存在女巫攻击的行为；女巫注入有三个主要参数包括μ，ξ和λ，分别代表着μ％的工人有ξ的概率会随机提供一个标签，以防止攻击行为过于明显。这些工人会被λ个攻击者控制。对比方法分别是td，catd和tdssa。td算法通过迭代，动态地更新工人权重和真值，直到真值变化小于阈值。catd算法也是迭代地运行这两个部分，但是其在更新权重时可以根据工人提供标签数量决定工人权重。tdssa算法注意到了众包中的策略女巫攻击。
[0081]
在另一个实施例中，还提供了基于数据长尾特性的女巫防御真值发现系统，系统采用上述实施例所述真值发现方法进行真值发现，系统设有任务发布者、众包系统以及工人，包括任务分配模块、工人参数更新模块以及任务真值更新模块；
[0082]
任务分配模块，用于根据任务发布者的要求与预算，响应工人的任务请求，根据pta算法为工人分配黄金任务或正常任务；
[0083]
工人参数更新模块，用于初始化、更新以及记录工人的权重、女巫分数以及可信分数，并且根据工人工作情况更新；
[0084]
任务真值更新模块，用于进行真值聚合，根据工人的权重，给予工人标签相对应的权重，使得可信工人的标签在聚合结果上更有影响力。
[0085]
还需要说明的是，在本说明书中，诸如术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个
……”
限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。
[0086]
对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下，在其他实施例中实现。因此，本发明将不会被限制于本文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。

技术特征：
1.基于数据长尾特性的女巫防御真值发现方法，其特征在于，设有任务发布者、众包系统以及工人，方法包括以下步骤：任务分配，响应工人的任务请求，根据pta算法为工人分配黄金任务或正常任务；更新工人参数，如果工人分配黄金任务，则众包系统将通过黄金任务的回答情况更新工人的相关参数，包括权重、女巫分数以及可信分数；更新任务真值，如果工人分配正常任务，则众包系统会记录工人对该任务的标签，在该任务收集到足够的标签后，会进行真值聚合；在真值聚合过程中，根据工人的权重，给予该工人标签相对应的权重，使得可信工人的标签在聚合结果上更有影响力；方法迭代，重复更新工人参数和更新任务真值步骤，使得女巫工人被封禁，正常工人获得更准确的权重以及任务真值的变化小于阈值，最终得到真值。2.根据权利要求1所述的基于数据长尾特性的女巫防御真值发现方法，其特征在于，步骤s1具体为：设众包有n个任务和m个工人，分别用t＝{t1，t2，...，t
n
}和w＝{w1，w2，...，w
m
}表示；每个任务都有一个真值，隐藏在p个候选答案中，用a＝{a
i，j
}表示工人w
j
关于任务t
i
的回答；众包系统根据任务发布者的要求与预算，将同一个任务分配给f个工人；在众包系统运作的过程中，系统响应工人w
j
的任务请求，根据工人w
j
的女巫分数s
j
和可信分数r
j
，根据p
j
(x)＝x
·
(1-r
j
)+s
j
·
(1-x)，概率性地为工人分配黄金任务或者正常任务，其中，x∈(0，1]代表黄金任务分配给工人w
j
的概率。3.根据权利要求2所述的基于数据长尾特性的女巫防御真值发现方法，其特征在于，可信分数r
j
根据工人回答黄金任务的正确率决定的；女巫分数s
j
由工人在黄金任务上提供虚假标签的行为决定的；权重由更新后的可信分数和工人提供标签的数量共同决定；工人的女巫分数s
j
和可信分数r
j
初始设为0，权重设为1。4.根据权利要求3所述的基于数据长尾特性的女巫防御真值发现方法，其特征在于，步骤s2具体包括：更新工人w
j
的权重，公式为：其中，χ函数根据工人提供标签的数量决定其权重；当工人提供较多标签时，其权重就为标签准确率；当工人提供较少标签时，其权重则维持在一个较低的水平；γ表示当工人标签数较少时，工人权重所维持的水平；更新工人w
j
的女巫分数和可信分数，公式为：的女巫分数和可信分数，公式为：
其中，s
j
代表工人w
j
在黄金任务上提供虚假多数标签的女巫攻击行为，r
j
代表工人w
j
在黄金任务中的可信表现；在计算出工人新的女巫分数和可信分数后，众包系统检测女巫分数和可信分数是否超过阈值η；如果女巫分数超过女巫阈值，则会将女巫工人封禁并回收其之前在正常任务中的答案；如果可信分数超过可信阈值，则会将工人设置为可信状态，此后将不会继续为其分配黄金任务。5.根据权利要求4所述的基于数据长尾特性的女巫防御真值发现方法，其特征在于，女巫阈值和可信阈值根据数据集的不同设置为不同的值η。6.根据权利要求1所述的基于数据长尾特性的女巫防御真值发现方法，其特征在于，步骤s3具体为：在收集全部工人任务标签a(t
i
，w
j
)后，将根据以下公式：其中，1(x，y)是指示函数，当x＝y时，返回1；否则，返回0；τ(w
j
)代表工人w
j
的标签准确率；因此，当工人女巫分数很低时，其提供标签的权重则更倾向于工人权重而不是随机选择的权重7.根据权利要求1所述的基于数据长尾特性的女巫防御真值发现方法，其特征在于，结合卡方函数和工人回答的数量和准确度，调整工人获得权重的大小，卡方函数χ可在工人提供少量回答时，以γ值主导函数结果，在工人提供大量回答时将和默认准确度得出的权重相近，由此抑制众包数据集中的长尾现象，以提高真值的准确率。8.根据权利要求1所述的基于数据长尾特性的女巫防御真值发现方法，其特征在于，步骤s4中，由于在每次算法运行时，女巫工人都会动态地生成任务的标签，因此，需要重复多次求得平均值作为最终真值结果。9.基于数据长尾特性的女巫防御真值发现系统，其特征在于，系统采用权利要求1-8任一项所述方法进行真值发现，系统设有任务发布者、众包系统以及工人，包括任务分配模块、工人参数更新模块以及任务真值更新模块；任务分配模块，用于根据任务发布者的要求与预算，响应工人的任务请求，根据pta算法为工人分配黄金任务或正常任务；工人参数更新模块，用于初始化、更新以及记录工人的权重、女巫分数以及可信分数，并且根据工人工作情况更新；任务真值更新模块，用于进行真值聚合，根据工人的权重，给予工人标签相对应的权重，使得可信工人的标签在聚合结果上更有影响力。

技术总结
本发明公开了一种基于数据长尾特性的女巫防御真值发现方法及系统，方法包括：任务分配，响应工人的任务请求，为工人分配黄金任务或正常任务；更新工人参数，如果工人分配黄金任务，则通过黄金任务的回答情况更新工人的相关参数；更新任务真值，如果工人分配正常任务，则记录工人对该任务的标签，在收集到足够的标签后进行真值聚合；在真值聚合过程中，根据工人的权重，给予该工人标签相对应的权重，使得可信工人的标签在聚合结果上更有影响力；重复更新工人参数和更新任务真值，使女巫工人被封禁，正常工人获得更准确的权重以及任务真值的变化小于阈值，最终得到真值。本发明方法能减少在估算真值时受长尾现象的影响，并且能抵御女巫攻击。女巫攻击。女巫攻击。


技术研发人员：林德嘉 苏国海 陈静静 范玉婷 吴永东
受保护的技术使用者：暨南大学
技术研发日：2023.03.07
技术公布日：2023/7/19