用于模式匹配的众包发包方法及优化策略

摘要

信息技术和网络的迅速发展，各个应用领域之间的合作越来越频繁，数据的互操作性越来越重要。由于各领域生产方式的高度自治，导致了数据模式的异构性，为实现数据共享和使用，解决“信息孤岛”的现状就需要数据集成的工作。模式匹配作为数据集成过程中的一个基础性问题，受到了学术界的关注，并提出了许多匹配方法以及研发出了各种模式匹配工具。使用模式匹配工具能大大提高模式匹配效率，但其给出的结果是带有不确定性的，且这种不确定性很难通过优化模式匹配的方法来进行消除。人类的智慧和生活经验能帮助减少这种不确定性。 随着众包概念的提出，众包这种将任务分发给一组分布式网络用户的新型问题解决模式在许多领域得到了广泛的应用。在数据库领域，运用众包的方式来帮助解决模式匹配工具在匹配过程中产生的不确定性问题成为一个研究的热点。 本文在运用众包的方式解决模式匹配问题的基础之上，针对众包发包流程进行了研究，提出了一种用于模式匹配的众包发包方法及优化策略。通过本文给出的方法和策略可以为众包问题发布者节省费用和时间成本。本文的研究工作包括两部分，具体如下： 本文基于熵和贝塔分布提出了一种用于模式匹配众包方法中的问题发布方法：Entropy-Beta。该方法引入了熵的概念，对模式匹配不确定性的大小给出度量，在此基础之上根据每个问题相对于模式匹配结果集熵的大小来选择最佳的问题进行发布，使每次发布的问题都能最大程度的减少模式匹配工具结果中的不确定性，以提高解决问题的效率。同时基于Beta分布的方法对众包工作者提供的答案精确度进行计算，并根据计算的结果动态的对发布问题的顺序进行调整，以保证解决问题的精确度。 在Entropy-Beta方法的基础之上，本文引入了经济学中的边际原理思想，提出了用于模式匹配众包方法中的发包优化策略：MarP（Marginal Principle）。该策略综合考虑了解决模式匹配不确定性的精确度以及发布问题的成本。根据边际原理的思想对发布问题的顺序进行了优化调整，使其满足边际报酬递减的原则。其次，在发包的过程中给出了发包成本和减少的模式匹配不确定性大小（即发包收益）之间的对比方法。并根据两者之间的大小给出了停止问题发布的判断条件，以保证问题发布者所花费的成本能获得相对最大程度的模式匹配不确定性大小的减少。 最后,本文采用四组实验数据,通仿真实验和招募志愿者实验两种实验方法，从解决模式匹配不确定性问题的效率、精确度以及成本三方面进行实验。通过实验结果的对比，验证了本文提出的发包方法及优化策略能更好的满足问题的发布者对于解决模式匹配问题的需求。 本文的创新点主要体现以下两个方面： 1、针对用于模式匹配的众包发包流程，提出了一种基于熵的问题发布排序方法。该方法能选择出对解决模式匹配不确定性问题贡献最大的问题进行优先发布，提高了解决问题的效率。 2、基于边际原理提出了对用于模式匹配的众包发包流程优化策略。该策略根据发包成本和收益的对比来判断何时停止问题的发布，保证了问题发布者所花费的费用能获得相对最大的收益。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1研究背景

1.2研究意义

1.3研究现状

1.4论文工作

1.5论文组织结构

第二章 基于熵和贝塔分布的模式匹配众包发包方法

2.1 基于Entropy的问题发布过程

2.2 基于Beta分布的众包答案精度评估

2.3 Entropy-Beta算法

2.4本章小结

第三章 基于边际原理的模式匹配众包发包优化策略

3.1边际原理简单介绍

3.2 众包发包优化问题

3.3问题发布过程中边际点的判断方法

3.4 本章小结

第四章 实验结果与分析

4.1 实验数据及工具

4.2实验验证方式

4.3 实验结果

4.4 本章小结

5 结论与展望

5.1 总结

5.2 展望

参考文献

附录

致谢