N次元空間にいくつかのxデータポイントがある場合、それらのxポイントのサブセットを記述できる固定長表現を見つけようとしていますか? たとえば、s 部分集合の平均はその部分集合を表すことができますが、その部分集合のみに固有ではありません。つまり、空間内の他の点が同じ平均を生成する可能性があるため、平均は一意の識別子ではありません。ポイントの数に依存せずにポイントを説明できる独自の尺度を誰か教えてもらえますか?
2 に答える
0
任意のサブセットは、長さ のビット マスクによって識別できます。ここで、対応する要素がサブセットに属している場合、ceiling(lg(x))ビットiは 1 です。xの関数ではない固定長表現はありません。
編集
私は間違っていた。PCAは、この問題の次元削減を実行する良い方法ですが、一部のセットでは機能しません。
ただし、ほとんどできます。ここで、「ほぼ」はジョンソン・リンデンシュトラウス補題によって正式に定義されますでは、指定された大きな次元Nに対して、はるかに低い次元nが存在し、各点をNからnにマッピングする線形変換が存在し、ユークリッド距離を維持します。元からの誤差ε内のセットのすべてのポイントのペア間。このような線形変換は JL 変換と呼ばれます。
言い換えれば、あなたの問題は、ポイントの各ペアが少なくともεで区切られているポイントのセットに対してのみ解決可能です。この場合、JL Transform は 1 つの解決策を提供します。さらに、 N、nおよびεの間には関係が存在し(補題を参照)、たとえば、N = 100 の場合、JL Transform は各点を 5D ( n = 5)の点にマッピングでき、一意に識別できます。各サブセットは、元のセット内のポイントのペア間の最小距離が少なくとも ~2.8 である (つまり、ポイントが十分に異なる) 場合に限ります。
nはNと、元のセット内のポイントのペア間の最小距離のみに依存することに注意してください。ポイントxの数に依存しないため、いくつかの制約はありますが、問題の解決策です。
于 2015-08-12T01:53:04.470 に答える