データマイニングにおけるデータセットのスパース性の影響

Question

距離行列（ユークリッド）を使用する場合、データセット（ほとんどの次元で複数のゼロ値）でスパース性が検索効率または精度にどのように影響するかをお尋ねします。私はANNとFLANNでこのような疎なデータセットをテストしましたが、密なデータセットと比較して、最も近い近隣を検索するのは非常に長い時間でした。なぜこれはそうですか？

Answer 1

これは非常に幅広い質問であり、具体的な説明がなくても答えにくいです。しかし、私はそれを試してみましょう。

ユークリッド空間の最近傍を求めるには一般に、約m * n回の計算が必要です。ここで、mは次元数、nはサンプル数です。各データセットの時間統計をm * nでプロットし、それらの比較方法を見ることができます。

スパースデータセットの場合は、サンプルを辞書形式で保存することもできます。その場合、平均時間はおおよそk * logk * nの計算になります。ここでkは非ゼロ要素の平均数です（辞書が各機能のランダムアクセス時間がlogkになるように格納されていると仮定します）。 logkの部分はほとんど目立たない）。

Answer 2

これは実装によって大きく異なります。あなたは何を使用しますか？例えば、距離計算に疎最適化を使用しますか？ユークリッド距離は、スパースベクトルの最も合理的な距離ではありません。