每周学点大数据 | No.52众包算法例析
NO.52
众包算法例析
小可：讨论了这么多，我还是想通过一个具体的众包例子来了解一下众包算法。
Mr. 王：好，我们就从计算机的角度用具体的例子来分析一下众包算法。通过我们前面讨论的内容，你能不能想到设计众包算法需要考虑的一些基本问题？
小可若有所思，说：嗯……既然很多众包平台是要支付劳动报酬的，那么最起码的众包算法应该要尽量的省钱吧？
Mr. 王笑着说：没错，这是一方面。另外，众包也要能很好地吸引工人有兴趣参与到任务中。下面的例子可以归结为一个实体识别。你先来看看这张表。
小可：购物网站上的商品名和价格表。
Mr. 王：发现了什么特点吗？
小可：比如r1 和r2 这两个商品，虽然它们的商品名是不同的，但是分析来看，它们应该是同一个东西，都是16GB 白色版的iPad 2。
Mr. 王：不错，这种情况在C2C 购物网站上非常普遍，很多相同商品的说法不同或者一些参数的顺序不同，甚至很多卖家的商品名里面还包含着广告词。
小可笑了，说：哈哈，两个同样的商品，一个商品名是××× 如假包换，一个商品名是××× 包邮这样吧？
Mr. 王：是的，其实我们希望完成的任务就是能进行一个聚集或者说聚类，将对应的现实世界中的相同实体的商品放在一类中。在实际完成个任务时，最基本的有两个选择：由机器来做，或者由人来做。由机器来做主要的方法就是基于相似度的。
小可：就是比较两个商品名有多么相似吧？把两个商品名看作是一些词的集合，看看这两个集合有多么相似。
Mr. 王：没错，一般来说会用一些相似度函数，比如Jaccard，它就是用两个集合的交集和并集的比来衡量两个集合的相似度的。然后设定一个阈值，高于这个阈值的，我们就认为它们是同一个商品。至于阈值的确定，可以通过一些机器学习或者数据挖掘的方法，求出合适的阈值。
Mr. 王：如果由人来做，最基本的想法就是，设立一些题目，这些题目给出两个商品名，让用户回答这两个商品名是不是同一个东西。你来分析一下，这样的方法复杂度如何？
小可：如果有n 个商品名，逐一进行匹配的话，就需要O(n2) 级别的计算量。
Mr. 王：如果一个HIT 给0.01 元，有10000 个商品呢？
小可：100000000×0.01=1000000 元。这个开销可太大了，做这么简单的工作要花上这么多钱，太不值得了。
Mr. 王：所以我们尝试改进它，提出一种基于簇的HIT。我们并不将商品两两进行匹配，而是将几个商品名放在一起，让用户选择其中哪几个是一类的。如果每次给用户k 个商品名，那么一次就可以完成k2 个对的识别，也就是说，任务量的复杂度可以下降到O(n2/k2)。假如有10000 个商品名，每一次给用户20 个商品名呢？
小可：n2/k2 = 100002 / 202，再乘以0.01 元，这样花费就小多了，只需花费2500 元就可以解决这个问题。
Mr. 王：从这个问题可以看出，人和机器是各有利弊的，机器的特点在于，节约金钱成本，而且处理时间比较快；而人的特点在于标注的质量比较高。所以众包算法期待的就是能结合机器和人的优点，使得成本、时间和质量都达到一个比较好的结果。
小可：那么具体要怎么结合呢？
Mr. 王：其实众包算法中包含的思想就是混合人和机器的工作流程。首先用机器去做一个预处理，可以用前面的某个相似度函数，如Jaccard ；但这次我们不去寻找那些相似度较高的商品名，而是排除那些相似度太低，也就是小于一定的阈值，我们认为已经不可能是同一类的这样的商品名。然后将剩下的部分交给人去进行识别。相应的，也可以使用前面提到的基于对的HIT 和基于簇的HIT。基于对的HIT 可能没有太多的问题，但是基于簇的HIT 还是有很多方面的东西需要考虑。
小可：比如簇的大小？
Mr. 王：没错，因为一次用户可以接受的任务中包含商品名的数量是有限的，比如一次给用户100 个商品名，那用户看起来眼都花了，就会造成匹配的质量大幅下降。也就是说，簇的大小存在一个阈值。另外，每一簇的东西要尽可能地“像一点”。
小可：否则，有可能一簇有10 个商品名，结果分出10 组来，它们当中没有一样的东西，这样人工进行识别就失去意义了。
Mr. 王：还有一个问题，就是对于任意两个商品名，它们至少应该同时出现在一个簇里一次。也就是说，要给这两个商品名被识别出是一个商品的机会；否则，结果中就丢失了一条记录。
小可：想不到就连众包里面都有这样的优化问题。那么它怎么解决呢？
Mr. 王：在一些文献中给出了这种问题的解法，就是将这些商品名抽象成一个图。
比如r1 和r2 的相似度大于某个阈值，我们认为它们存在成为同一个商品的可能，就在图上画一条线；其余的依此类推。这样的话，连通分量有两种：一种是小连通分量，比如r8 和r9 ；另一种是较大的连通分量，比如图中其余的部分。此时这个问题就变成了图的划分问题。比如在这个图中，我们就可以将其划分为以下三个部分。
想一想，根据我们前面形式化的内容，三个簇应该满足什么条件？
小可：首先，应该满足每个簇的大小不大于簇的大小阈值k ；其次，所有的簇都应该包含图中的每一条边。这样就能保证给每两个商品名被识别出是一个商品的机会。
Mr. 王：发现这样的划分方法是一个NP-hard 问题。要解决它，提出这个问题的论文作者给出了名为“双层法”的解决方法。比如对于上面的图，设k=4。对于较小的连通分量，不需要考虑，因为它可以被放进一个簇中；对于较大的连通分量，是必然要对其进行划分的。
这里我们使用一个贪心算法来对大簇进行划分。使用下图作为例子。
首先，我们找到一个度最大的点，此图中就是r4。然后，对和r4 相连的点进行标注，标注包括两部分：和簇内点相连的边数、和簇外点相连的边数。
这个序对从意义上反映了它和簇的关联程度。接下来选择和簇内关联度高的点。簇内关联度是一样的，那么选择和簇外关联度低的点，相对来讲，这样的点和这个簇的连接比和其他的簇的连接更紧密，比如这里的r6。
接下来用同样的方法，选择r5。这里要注意，选择r6 对其他点的标注对没有影响，而r5 则不同，需要与之相连的r3 和簇内点相连的边数进行更新。
于是我们选择r3。此时第一个簇就生成了。
但是这里要注意，虽然r3,r4,r5,r6 已经生成了一个簇，但是边<r7,r4>,<r2,r3> 仍未被包含进这个簇中，这样这个簇就没有给r7 和r4 商品名是同一个商品的机会，所以我们仍要在图中的剩下部分保留<r7,r4>,<r2,r3> 这两条边。剩下的5 个点，可以继续划分，方法是一样的。
至此，我们就成功地将所有的大连通分量都划分成了较小的连通分量。剩下的工作就是尽可能地将这些小的连通分量进行组合，形成不大于k=4 的簇，问题也就相应地解决了。
下期精彩预告
经过学习，我们了解了一下了解众包的算法例析。在下一期中，我们将进一步研究一下众包的具体应用，具体的运用到时间中国去解析。更多精彩内容，敬请关注灯塔大数据，每周五不见不散呦！
文章来源：灯塔大数据
文章编辑：秦革