machine-learning - 二进制特征和局部敏感哈希 (LSH)

Question

我正在研究 FLANN，一个用于近似最近邻搜索的库。

对于 LSH 方法，它们表示一个对象(搜索空间中的点)，如无符号整型数组。我不确定他们为什么这样做，而不是将一个点简单地表示为一个 double 组(这将表示一个点在多维向量空间中)。可能是因为 LSH 用于二进制特征？有人可以分享更多关于 unsigned int 的可能用途吗这个案例？如果每个功能只需要 0 和 1，为什么要使用 unsigned int？

谢谢

Answer 1

请注意，我将引用最新的 FLANN 版本，即撰写本文时的 flann-1.8.3。

For the LSH method they represent an object (point in search space), as an array of unsigned int

不:这是错误的。 LshIndex 类包含一个实现 LSH 索引的 buildIndexImpl 方法。由于 LSH 基本上是哈希表的集合，因此有效索引发生在 LshTable 类上。

基本索引方法，即一次索引一个特征向量(也称为描述符或点)的方法是:

/** Add a feature to the table
 * @param value the value to store for that feature
 * @param feature the feature itself
 */
void add(unsigned int value, const ElementType* feature) {...}

注意:buildIndexImpl 方法使用替代版本，该版本仅迭代功能，并在每个功能上调用上述方法。

正如你所看到的，这个方法有 2 个参数，它们是一对 (ID, Descriptor):

1. value 是 unsigned int 表示特征向量唯一数字标识符(也称为特征索引)
2. feature 表示特征向量本身

如果您查看实现，您会发现第一步包括对描述符值进行哈希处理以获得相关的存储桶键(= 指向存储此描述符 ID 的存储桶的槽的标识符):

BucketKey key = getKey(feature);

实际上，getKey 哈希函数仅针对二进制描述符实现，即可以表示为 unsigned char 数组的描述符:

// Specialization for unsigned char
template<>
inline size_t LshTable<unsigned char>::getKey(const unsigned char* feature) const {...}

Maybe because LSH is used for binary features?

是的:如上所述，FLANN LSH 实现在 Hamming space 中工作。对于二进制描述符。

如果您要使用具有实际值的描述符(在R**d中)，您应该引用original paper其中包括如何将特征向量转换为二进制字符串以便使用汉明空间和哈希函数的详细信息。

Can someone share more about the possible use of unsigned int in this case? Why unsigned int if you only need a 0 and 1 for each feature?

参见上文:unsigned int值仅用于存储每个特征向量的相关ID。