适合这个简单机器学习问题的算法有哪些？

Question

我有一个我认为很简单的机器学习问题。

基本问题是：我会不断收到一个新物体和关于这个物体的一些描述。例如：新物体是 'bob'，描述是 ['高','老','搞笑']。接下来，我需要用某种机器学习的方法，找到之前处理过的物体中，描述最相似的10个或更少的物体，比如说，过去相似的物体是 ['frank','steve','joe']。然后，我有一个算法可以直接判断这些物体是否真的和bob相似，比如说，正确的物体是 ['steve','joe']。接着，这个分类器会根据这些成功匹配的反馈进行训练。然后这个过程会对新的物体重复进行。

这里是伪代码：

Classifier=new_classifier()

while True:
    new_object,new_object_descriptions = get_new_object_and_descriptions()
    past_similar_objects = Classifier.classify(new_object,new_object_descriptions)
    correct_objects = calc_successful_matches(new_object,past_similar_objects)
    Classifier.train_successful_matches(object,correct_objects)

不过，有一些条件可能会限制我能用的分类器：

• 会有数百万个物体被放入这个分类器，所以分类和训练需要能够很好地扩展到数百万种物体类型，并且还要快速。我觉得这就不适合像垃圾邮件分类器那种只适合两种类型（垃圾邮件或非垃圾邮件）的分类器。（更新：如果有问题，我可能可以把这个数量缩小到几千个物体，而不是几百万个。）

• 再次强调，当有数百万个物体需要分类时，我更看重速度，而不是准确性。

• 更新：分类器应该根据过去的训练反馈返回10个（或更少）最相似的物体。如果没有这个限制，分类器就可以简单地返回所有过去的物体，这样就太简单了 :)

那么，有哪些不错且快速的机器学习算法可以用来解决这个问题呢？

注意：calc_successful_matches这个距离计算非常耗费资源，所以我才想用一个快速的机器学习算法，先猜测哪些物体可能接近，然后再进行耗时的计算。

Answer 1

你真的需要用机器学习算法来解决这个问题吗？你是用什么标准来判断相似度的？你提到了对象的维度，那每个人的特征集合大小呢？特征类型有没有上限？我可能会尝试这样的做法：

1) 创建一个字典，把特征映射到一个名字列表，叫做 map。

对于每个人 p：

对于 p 的每个特征 t：

map[t].add(p);

2) 然后当我想找出最接近的人时，我会用我的字典创建一个新的临时字典：

这个字典把名字映射到计数，叫做 cnt。

对于我关注的人的每个特征 t：

对于 map[t] 中的每个人 p：

cnt[p]++;

最后，计数最高的条目就是最接近的人。

---

这样做的好处是 map 只需要创建一次。如果每个人的特征不多，而可用的特征类型又很多，那么这个算法应该会很快。

Answer 2

你可以使用向量空间模型（http://en.wikipedia.org/wiki/Vector_space_model）。我觉得你想要了解的是如何给不同的描述词加权，以判断两个对象的描述向量有多接近，比如说用一种简化的互信息来衡量。这种方法效率很高，因为你可以通过词汇来生成向量，这样就不需要比较那些没有共同特征的对象了。简单的模型会为每个词设置一个可调的权重（这个权重可以是针对每个向量的，也可以是针对每个词的，或者两者都有），同时还会有一个阈值。向量空间模型是一种广泛使用的技术（比如在Apache Lucene中，你可能会用到这个工具来解决你的问题），所以你可以通过进一步的搜索了解很多相关信息。

让我用一个简单的例子来说明。假设有一个人bob，他的描述是：['高','老','有趣']，我会找到：

frank: ['年轻','矮','有趣']
steve: ['高','老','脾气坏']
joe: ['高','老']

因为我维护了一个哈希表，把有趣这个词映射到{frank,...}，高这个词映射到{steve, joe,...}，老这个词映射到{steve, joe,...}。

我会计算一些类似于总体互信息的东西：共享标签的权重/ bob的标签的权重。如果这个权重超过了阈值，我就把他们加入到列表中。

在训练过程中，如果我犯了错误，我会修改共享标签。如果我的错误是把frank包括进来了，我就会降低有趣这个词的权重；而如果我错过了steve或joe，我就会增加高和老这两个词的权重。

你可以根据需要让这个模型变得更加复杂，比如可以为词的组合设置权重。

Answer 3

有一个算法看起来符合你的需求，可能和约翰统计学家提到的类似，叫做语义哈希。这个算法的基本思路是训练一个深度信念网络（这是一种被称为“神经网络2.0”的神经网络，当前是个热门研究领域），把一个物体的描述列表转化成二进制数字的哈希值。这样，数字之间的汉明距离就能表示相似的物体。因为这个过程只需要进行位运算，所以速度很快，而且可以用来创建一种最近邻算法，自然能扩展到很多类别。这是非常先进的技术。不过，缺点是理解和实现起来不简单，还需要调整一些参数。作者在这里提供了一些Matlab代码这里。另一个相对容易实现的算法，和这个算法关系密切，叫做局部敏感哈希。

现在你提到你有一个计算代价高的距离函数想要快速近似，我想到了另一个很有趣的算法，叫做Boostmap。这个算法使用提升技术来创建一个快速的度量，来近似一个计算起来比较复杂的度量。从某种意义上说，它和上面的想法类似，但使用的算法不同。这个论文的作者还有几篇关于相关技术的论文，质量都不错（发表在顶级会议上），你可以去看看。