- 一連のパラメーターの測定値には一定の数（1600万を超えないと想定できます）があります。 セット内のパラメーターの数は2〜5です。
- パラメーターの測定は比較的成功する可能性があります-その結果は真に近くなります（パラメーターと分布のタイプは不明です）、または成功しません-結果はランダムになります（再び不明な分布パラメーター）。 成功したかどうかを単一の測定から判断することはできません。
- 凝縮点が存在すると仮定できます。 品質が類似している（正式に定義されていない）ものが複数ある場合は、どれでも発行できます。
- 答えはソースデータの1つのパスで与えられなければなりません：それらを再計算するか、全体を保存します-高価です。
- そして、いつものように、私はアルゴリズムがよりシンプルに見え、より速く動作することを望んでいます。
簡単にするために、測定されたパラメーター値は0〜1の実数であると想定できます。5つのパラメーターの場合は小数点以下3桁、4つ以下のパラメーターの場合は4以上の解像度が得られます。
多数の開始点が、処理ポイントのペアに基づくメソッドを疑わしくすることは明らかです。 最も近い地点までの距離を効果的に検索する場合でも、顕著な実装作業が必要になります。
ヒストグラムの構築も簡単ではありません。目的のセルサイズでさえも事前にはわかりません。 たとえば、すべての測定結果が直径0.1のボールになり、成功したものはサイズ0.003の領域に局在化する可能性があります。 そして、この領域の位置を与える必要があります（N次元空間で！）
N次元の点の凝縮が別々の座標上の点の投影の凝縮の位置から復元できることを期待して、個々のパラメーターの分布のヒストグラムを構築することができますが、バックアップとしてこのオプションを残すことをお勧めします：パラメーターの関係に関する情報を失うことは危険であり、投影は肥厚の寄生領域。
私にとって最も有望だと思われたオプションは、 kdツリーの使用です 。 バイナリツリーを構築する場合、各ノードは座標の1つに従って空間領域を2つの部分に分割することに対応し（座標はサイクル-x 1 、x 2 、...、x k 、x 1 、x 2 、...）でソートされ、ポイントの数を見つけますそれは各領域に該当します。そうすることができます。
ポイントNとします。たとえば、K = [sqrt（N）]またはK = [N 2/3 ]のように、Nより小さい値Kを選択します。 少なくともKポイントを含む最小ボリュームの領域（つまり、ツリーの最大深度にある領域）を見つけます。 そのようなエリアが複数ある場合は、ほとんどのポイントがあるエリアを選びます。 その後、さらにポイントが存在する半分を選択するたびに、それを半分に分割し始めます（さらにツリーを下っていきます）。 シートに到達したとき（たとえば、一点まで）、それを回答として発行します。
このアルゴリズムが凝縮の主な領域を失い、代わりにいくつかの局所異常を選択するか、または応答として凝縮の中心から遠く離れた点を与える例を見つけることができますが、ほとんどの場合、その答えは多かれ少なかれ期待できます十分。 残念ながら、kdツリーの構築は高価であり、多くのメモリを消費します。 ポイントごとに8バイトを割り当てる準備はできていますが、これ以上のコストは望ましくありません。
時間とメモリを節約するために、kdツリーを暗黙的に構築することにしました。
ポイント（x 1 、x 2 、...、x k ）があるとします。 その座標をバイナリシステムで記述します
x 1 = 0.x 11 x 12 x 13 ...
x 2 = 0.x 21 x 22 x 23 ...
x 3 = 0.x 31 x 32 x 33 ...
...
そして、64ビット整数を構築します
P = x 11 x 21 ... x k1 x 12 ... x k2 ...
この数値は、ツリーを介してレベル64の深さまでのパスを表します。 さらに、必要な精度でポイントの座標を復元できます。
すべてのポイントのコードPを昇順で並べ替えると、ツリーのトラバーサルの順にポイントが取得されます。 任意の2点P aおよびP bについて、共通の子孫を持つ最も深いノードを見つけるのは簡単です。数P a ^ P bの最上位の非ゼロビットを見つけるだけで十分です。 そして、この表現上の問題のすべての必要な断片は、いくつかの行で解決されます。
少なくともK個のポイントを含む最小ポイントが位置するレベルを検索します。
ulong mask=ulong.MaxValue; K--; for(int i=K;i<m_np;i++) mask=Math.Min(mask,m_Arr[i]^m_Arr[iK]);
ここで、m_Arrはコードの配列、m_npはその中に埋められた要素の数、maskはその上位ビットが目的のレベルを決定する数です。
最大数のポイントを含む見つかったレベルのエリアを検索します（少なくともKがあることがわかっています）。
mask=InvMask(mask); int ms=0,me=0; for(int i=0;i<m_np-K;i++){ ulong a=m_Arr[i]; int h=i+K; if(((a^m_Arr[h])&mask)==0){ while(h<m_np-1 && ((a^m_Arr[h+1])&mask)==0) h++; K=hi; ms=i; me=i=h; } }
ここで、InvMask（マスク）は、マスクmaskの最も古い非ゼロビットよりも上位のすべてのビットに1を含むマスクの計算です。 ms-目的の領域の始まりとme-その終わりを計算します。
より重い子孫を検索します。
int h=(ms+me)/2; ulong samp=m_Arr[h]; ulong cb=samp^m_Arr[ms],ce=samp^m_Arr[me]; if(cb>ce) { ms=h; ce=InvMask(ce); while(ms>0 && ((m_Arr[ms-1]^samp)&ce)==0) ms--; } else { me=h; cb=InvMask(cb); while(me<m_np-1 && ((m_Arr[me+1]^samp)&cb)==0) me++; }
ここでは、降下は必ずしも1レベルではありません。
したがって、凝縮を検索するタスクは解決されます。
プログラム全体が100行に収まり、ソース（C＃内）がここにあります 。
実際のタスクには、もう少し複雑な定式化があります。 パラメータの変化の範囲は事前にはわかりません。さらに、サンプルの測定値が計画された1600万を超える可能性があり、「良好な」測定値が最後に近づく可能性があります。 ただし、アルゴリズムを少し変更するだけで、これらの問題に対処できます。 たとえば、配列内の場所がなくなり、ポイントが流れ続ける場合、すでにダイヤルされたコードの配列をソートして間引くことができます-これは、凝縮の位置と品質に影響しません。
結論として-作業のいくつかの例（2つのパラメーター、10 ^ 5および10 ^ 7ポイント-1つの実際の例といくつかの合成例）。 （見つかった位置を明確にするために）アルゴリズムを改善する必要があり、実際のケースではあまりにも慎重であり、より単純なソリューションで十分であることがわかります。 しかし、少し安全にプレイしたいです。
