數據挖掘中數據集稀疏性的影響

Question

我想問一下使用距離矩陣（歐幾里得）時，數據集中的稀疏性（大多數維度中的多個零值）如何影響搜索效率或準確性。我已經在ANN和FLANN中測試了這些稀疏數據集，並且導致我在很長一段時間內搜索與密集數據集相比最近的鄰居。這是爲什麼？

Answer 1

這是一個非常寬泛的問題，沒有具體細節就很難回答。但讓我試試看。

尋找歐氏空間中的最近鄰一般需要大約m * n個計算，其中m是維數，n是樣本數。您可以用m * n繪製每個數據集的時間統計數據，並查看它們的比較結果。

對於稀疏數據集，您還可以以字典格式存儲示例。在這種情況下，平均時間約爲k * logk * n計算，其中k是非零元素的平均數（假設字典以每個特徵的隨機訪問時間爲logk的方式存儲）如果使用類似散列表logk部分幾乎不明顯）。

Answer 2

這取決於你的實現。您使用什麼，例如，在距離計算中使用稀疏優化？歐幾里德距離不是稀疏向量最明顯的距離，順便說一句。