数据挖掘中数据集稀疏性的影响

Question

我想问一下使用距离矩阵（欧几里得）时，数据集中的稀疏性（大多数维度中的多个零值）如何影响搜索效率或准确性。我已经在ANN和FLANN中测试了这些稀疏数据集，并且导致我在很长一段时间内搜索与密集数据集相比最近的邻居。这是为什么？

Answer 1

这是一个非常宽泛的问题，没有具体细节就很难回答。但让我试试看。

寻找欧氏空间中的最近邻一般需要大约m * n个计算，其中m是维数，n是样本数。您可以用m * n绘制每个数据集的时间统计数据，并查看它们的比较结果。

对于稀疏数据集，您还可以以字典格式存储示例。在这种情况下，平均时间约为k * logk * n计算，其中k是非零元素的平均数（假设字典以每个特征的随机访问时间为logk的方式存储）如果使用类似散列表logk部分几乎不明显）。

Answer 2

这取决于你的实现。您使用什么，例如，在距离计算中使用稀疏优化？欧几里德距离不是稀疏向量最明显的距离，顺便说一句。