机器学习-二进制特征和位置敏感散列(LSH)

Question

我正在学习FLANN，一个近似最近邻搜索库。

对于LSH方法，它们表示一个对象(搜索空间中的点)，如一个无符号整型数组。我不确定他们为什么这样做，而不是这样做将一个点简单地表示为双精度数组(这将表示一个点)在多维向量空间中)。也许是因为LSH用于二进制文件特征吗?有人能分享更多关于unsigned int in的可能用法吗这种情况下吗?如果每个特性只需要0和1，为什么要unsigned int ?

谢谢

Answer 1

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

对于LSH方法，它们表示一个对象(搜索空间中的点)，作为unsigned int

数组

不:这是错误的。LshIndex类包含一个buildIndexImpl方法来实现LSH索引。由于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方法使用替代版本，它只是迭代功能，并在每个功能上调用上述方法。

你可以看到这个方法有两个参数，它们是一对(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 {...}

可能是因为LSH用于二进制特征?

是:如上所述，FLANN LSH实现在二进制描述符的汉明空间中工作。

如果你要使用实值描述符(在R**d中)，你应该参考原始论文，其中包括如何将特征向量转换为二进制字符串以使用汉明空间和哈希函数的详细信息。

有人能分享更多关于unsigned int在this中的可能用法吗案例?如果每个特性只需要0和1，为什么要unsigned int ?

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