我想问一下,使用距离矩阵(欧几里得)时,数据集中的稀疏性(大多数维度中存在多个零值)将如何影响搜索效率或准确性。我已经在 ANN 和 FLANN 中测试了此类稀疏数据集,与密集数据集相比,这导致我需要很长时间来搜索其最近的邻居。为什么会这样?
最佳答案
这是一个非常广泛的问题,没有具体细节很难回答。但让我尝试一下。
在欧氏空间中查找最近邻通常需要大约 m*n 次计算,其中 m 是维度数,n 是样本数。您可以使用 m*n 绘制每个数据集的时间统计数据,并查看它们的比较情况。
对于稀疏数据集,您还可以以字典格式存储样本。在这种情况下,平均时间大约为 k*logk*n 计算,其中 k 是非零元素的平均数量(假设字典以每个特征的随机访问时间为 logk 的方式存储。如果您使用哈希表之类的东西logk 部分几乎不明显)。
关于algorithm - 数据挖掘中数据集稀疏性的影响,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9623646/