データベースに 5000 人のユーザーがいるとします。ユーザー行には、性別列、出身地列、ステータス (既婚/未婚) 列があります。
これらの条件を満たすランダムなサブセット (100 人のユーザーとしましょう) を生成する方法:
これらの条件は独立しています。つまり、次のようにすることはできません。
この世代にアルゴリズムはありますか？
内訳は正確である必要がありますか、それとも概算である必要がありますか? 通常、このようなサンプルを生成する場合は、何らかの統計調査を行っているため、おおよそのサンプルを生成するだけで十分です。
これを行う方法は次のとおりです。
関数 genRandomIndividual() を持っています。
個体を生成するたびに、ランダム関数を使用して性別を選択します - 確率 40% の男性
再びランダム関数を使用して出生地を選択します (間隔 0-1 で実数を生成し、0-.5 の場合は米国を選択し、.5-.7 の場合は &K、.7-.9 の場合はカナダを選択します。それ以外はオーストラリア）。
ランダム関数を使用して結婚ステータスを選択します (0-.7 の場合は 0-1 で生成し、それ以外の場合は結婚していません)。
一連の特性を取得したら、これらの特性を満たす最初の個人をデータベースで検索し、それらをサンプルに追加して、データベースに既に追加されていることを示すタグを付けます。サンプルサイズを満たすまでこれを続けます。
特性を満たす個体は存在しない可能性があります。次に、代わりに新しいランダムな個体を生成します。世代は独立しており、必要な確率に従って特性を生成するため、最終的には、指定された確率に従ってランダムに生成された個体で正しいサイズのサンプル サイズが得られます。
これらの条件を満たすサブセットを見つけることができない場合があることに注意することが重要です。例を挙げると、データベースにアメリカ人男性のみとオーストラリア人女性のみが含まれているとします。明らかに、分布の制約を満たすサブセットを生成できませんでした。
次のようなことを試すことができます：
交換するかどうかを決定するためのメトリックとして、目的の分布までの距離の二乗和をおそらく使用します。
それがセットをランダムに保つ頭に浮かぶものです。求めているディストリビューションに一致するサブセットがない場合があることに注意してください。
（同じことを行うためのはるかに簡単で効率的な方法を考えたので、私の投稿を完全に書き直しました（実際には、新しいものを書き、古いものを削除しました）。）
私はあなたが実際に正確な比率を望んでいると仮定していて、平均してそれらを満足させるだけではありません。これは非常に簡単な方法ですが、データによっては実行に時間がかかる場合があります。
まず、元のデータを整理して、タイプの各組み合わせに簡単にアクセスできるようにします。つまり、既婚の米国人男性を1つの山に、未婚の米国人男性を別の山にグループ化します。次に、 p個の条件があり、 k個の要素を選択すると仮定して、それぞれサイズkのp個の配列を作成します。1つの配列は1つの条件を表します。各配列の要素を、必要な比率で、その条件のタイプにします。したがって、あなたの例では、性別配列には40人の男性と60人の女性が含まれます。
ここで、各p配列を個別にシャッフルします（実際には、必要に応じて1つの配列をシャッフルしないでおくことができます）。次に、インデックスiごとに、選択された要素のタイプをインデックスiのシャッフルされたp配列から組み合わせて取得し、元のグループの残りのタイプからランダムにそのようなタイプを1つ選択して、選択された要素を削除します。そのタイプの要素が残っていない場合、アルゴリズムは失敗しているため、配列を再シャッフルして、要素の選択を再開します。
これを使用するには、最初に条件が完全に満たされていることを確認する必要があります。そうしないと、無限にループするだけです。正直なところ、条件が満たされていることを確認する簡単な方法はわかりませんが、元のデータの要素数がkに比べて多く、分布があまり偏っていない場合は、解決策があるはずです。また、条件を満たす方法が少ない場合は、見つけるのに時間がかかる場合があります。メソッドは確率1で終了しますが、実行時間に設定できる上限はありません。
私にとっては形式主義と出版を意味するので、アルゴリズムは強すぎる言葉かもしれませんが、正確な比率でサブセットを選択する方法があり（パーセンテージがサンプル宇宙からの被験者の整数をもたらすと仮定します）、他の方法よりもはるかに簡単です提案されたソリューション。私は1つを構築し、それをテストしました。
ところで、ここで応答が遅くなって申し訳ありませんが、最近は時間が限られています。ハードコーディングされたソリューションをかなり迅速に作成し、それ以来、適切な汎用実装にリファクタリングしてきました。忙しくてまだ終わっていませんが、これ以上返事を遅らせたくありませんでした。
メソッド:
基本的に、各行を個別に検討し、条件によって各列の値を選択する余地があるかどうかに基づいて、選択可能かどうかを判断します。
そのために、各列ルール (例: 男性 40%、女性 60%) を個別のターゲットと見なします (例: 希望するサブセット サイズが 100 の場合、男性 40 人、女性 60 人を探します)。女性）。それぞれカウンターを作ります。
次に、サブセットを作成するか、一致するものが見つからずにサンプル ユニバースのすべての行を調べるまで、ループします (その後の動作については以下を参照してください)。これは疑似コードのループです。
- Randomly select a row.
- Mark the row examined.
- For each column constraint:
* Get the value for the relevant column from the row
* Test for selectability:
If there's a value target for the value,
and if we haven't already selected our target number of incidences of this value,
then the row is selectable with respect to this column
* Else: the row fails.
- If the row didn't fail, select it: add it to the subset
それが核心です。ルールに一致するサブセットを提供するか、そうしないか...一致が見つからない場合に何が起こるかを教えてくれます。
満足できない:
他の人が指摘したように、任意のサンプル ユニバースの任意のルール セットを満たすことが常に可能であるとは限りません。ルールが有効であり (各値のパーセンテージの合計が 100 になる)、サブセットのサイズがユニバースのサイズよりも小さく、ユニバースに、選択された各値を持つ十分な数の個人が含まれており、ターゲットに到達する場合でも、失敗する可能性があります。値は実際には独立して配布されません。
サンプル ユニバースのすべての男性がオーストラリア人である場合を考えてみましょう。この場合、オーストラリア人を選択できる数だけ男性を選択でき、その逆も同様です。したがって、選択したすべてのオーストラリア人が男性であったとしても、一連の制約 (サブセット サイズ: 100; 男性: 40%; オーストラリア人 10%) は、そのようなユニバースからはまったく満たすことができません。
制約を変更すると (サブセット サイズ: 100; 男性: 40%; オーストラリア人 40%)、一致するサブセットを作成できる可能性がありますが、選択するオーストラリア人はすべて男性でなければなりません。制約を再度変更すると (サブセット サイズ: 100; 男性: 20%; オーストラリア人 40%)、一致するサブセットを作成できる可能性があります。この場合）。
この後者の場合、選択順序が重要になります。ランダム シードによっては、成功する場合もあれば、失敗する場合もあります。
このため、アルゴリズムは再試行する準備ができている必要があります (そして私の実装はそうしています)。私はこれを忍耐力テストと考えています。問題は、制約がサンプル母集団と互換性がないと判断する前に、何回失敗しても構わないと思っているかということです。
適合性
この方法は、説明したように、OP のタスク (特定の基準に一致するランダムなサブセットを選択する) に適しています。「与えられた基準でサブセットを形成する ことは可能ですか」というわずかに異なる質問への回答には適していません。
これについての私の理由は単純です。アルゴリズムがサブセットを見つけられない状況は、データに未知の連鎖が含まれている場合、または基準がサンプル ユニバースから非常に限られた数のサブセットを許可している場合です。このような場合、サブセットの使用は統計分析にとって疑わしいものであり、少なくともさらに考えなければなりません。
しかし、部分集合を形成できるかどうかという質問に答えるためには、この方法は非決定論的で非効率的です。他の人が提案した、より複雑なシャッフル アンド ソート アルゴリズムのいずれかを使用することをお勧めします。
事前検証:
すべてのサブセットが満たされるわけではないことを発見したときの当面の考えは、いくつかの初期検証を実行し、おそらくデータを分析して、回答可能か、条件付きでのみ回答可能かを確認することです。
私の立場は、各列ルールが有効であること (つまり、列のパーセンテージの合計が 100 になるか、十分に近いこと) と、サブセット サイズがユニバース サイズよりも小さいことを最初に検証する以外に、価値のある事前の検証は他にないということです。やっています。選択した値ごとに宇宙に十分な数の個人が含まれていることを確認する必要があるかもしれない (たとえば、宇宙には実際に 40 人の男性と 60 人の女性がいる) という議論をすることができますが、私はそれを実装していません。
それ以外では、母集団の関連性を特定するための分析自体に時間がかかるため、再試行回数を増やして実行するだけで十分な結果が得られる可能性があります。多分それは、統計の背景について話す私の不足です。
部分和の問題ではない
この問題は部分集合問題に似ていると考えられています。これは微妙ではあるが、かなり異なると私は主張する. 私の推論は次のとおりです: 部分集合和の問題では、部分集合がルールを満たしているかどうかの質問に答えるために、部分集合を形成してテストする必要があります: 追加する前に個々の要素をテストすることは (特定のエッジ条件を除いて) 不可能ですそれをサブセットにします。
ただし、OPの質問については可能です。後で説明するように、行をランダムに選択して個別にテストできます。これは、それぞれの重みが 1 であるためです。