2

のアイテムのテーブルがあります[ID, ATTR1, ATTR2, ATTR3]。アイテムの約半分を選択したいのですが、クラスター化されていないランダムな結果セットを取得しようとしています。言い換えると、ATTR1 値、ATTR2 値、および ATTR3 値がかなり均一に広がっています。これは必ずしもデータ全体を表しているとは限りません。つまり、全体のテーブルは一般的に特定の属性値に集中している可能性がありますが、より多様なサブセットを選択したいと考えています。属性は相互に関連していないため、ATTR1 と ATTR2 の間に実際の相関関係はありません。

例として、ATTR1 = "State" を想像してください。セット全体ではほとんどのデータがいくつかの州に集中していても、サブセット内の各項目を異なる州のものにしたいと考えています。そして、これは他の 2 つの属性にも同時に当てはまります。(一部のテーブルではこれが可能にならない場合があることは認識していますが、十分なデータがあるため、解決策がない可能性は低いです)

効率的なアルゴリズムのアイデアはありますか? ありがとう！私はこれを検索する方法さえ本当に知りません:)

(ちなみに、これが事前計算またはセット全体のインデックス付けを必要とする場合でも、ランダムに変化するサブセットをすばやく引き出すことができる限り、問題ありません)

4

8 に答える 8

1

興味深い問題です。リストの約半分が必要なので、これはどうですか:-

完全に無作為に選択された半分の値のリストを作成します。選択した項目ごとに、ATTR1、ATTR2、ATTR3 の値のヒストグラムを計算します。

：ループ

現在のリストにあるアイテムとそうでないアイテムをランダムに選択します。

新しいアイテムがヒストグラム内の一意の属性の数の「エントロピー」を増加させる場合は、それを保持し、行った変更を反映するようにヒストグラムを更新します。

ランダムではなく、すべての値をカバーする方向にどれだけ強制的に移動させたいかに応じて、N/2 回、またはそれ以上繰り返します。また、「シミュレートされたアニーリング」を使用して、スワップを受け入れる確率を徐々に変更することもできます。「悪化してもスワップを許可する場合がある」から「多様性が増す場合にのみスワップする」までです。

于 2010-03-20T19:57:10.843 に答える
0

テーブル内のアイテムが何らかの形式の id によってインデックス付けされていると仮定すると、ループ内でテーブル内のアイテムの半分を反復処理し、乱数ジェネレーターを使用して番号を取得します。

于 2010-03-20T18:41:15.710 に答える
0

私見では

Finding variety is difficult but generating it is easy.

したがって、さまざまな組み合わせを生成し、それらの組み合わせを持つレコードのテーブルを検索できます。

テーブルがソートされていれば、検索も簡単になります。

サンプルの Python コード:

d = {}
d[('a',0,'A')]=0
d[('a',1,'A')]=1
d[('a',0,'A')]=2
d[('b',1,'B')]=3
d[('b',0,'C')]=4
d[('c',1,'C')]=5
d[('c',0,'D')]=6
d[('a',0,'A')]=7

print d

attr1 = ['a','b','c']
attr2 = [0,1]
attr3 = ['A','B','C','D']

# no of items in
# attr2 < attr1 < attr3

# ;) reason for strange nesting of loops

for z in attr3:
    for x in attr1:
        for y in attr2:
            k = (x,y,z)
            if d.has_key(k):
                print '%s->%s'%(k,d[k])
            else:
                print k

出力：

('a', 0, 'A')->7
('a', 1, 'A')->1
('b', 0, 'A')
('b', 1, 'A')
('c', 0, 'A')
('c', 1, 'A')
('a', 0, 'B')
('a', 1, 'B')
('b', 0, 'B')
('b', 1, 'B')->3
('c', 0, 'B')
('c', 1, 'B')
('a', 0, 'C')
('a', 1, 'C')
('b', 0, 'C')->4
('b', 1, 'C')
('c', 0, 'C')
('c', 1, 'C')->5
('a', 0, 'D')
('a', 1, 'D')
('b', 0, 'D')
('b', 1, 'D')
('c', 0, 'D')->6
('c', 1, 'D')

ただし、テーブルが非常に大きく（そうでなければ、なぜアルゴリズムが必要になるのでしょうか;）、データがかなり均一に分散されていると仮定すると、実際のシナリオではより多くのヒットが発生します。このダミーのケースでは、ミスが多すぎて、アルゴリズムが非効率的に見えます。

于 2010-03-20T19:15:16.903 に答える
0

わかりません（知っている人が答えてくれることを願っています）。頭に浮かぶのは次のとおりです。「バラエティ」のあるサブセットに最も重点を置いて、MCMCのディストリビューションを作成します。

于 2010-03-20T18:30:52.347 に答える
0

あなたの例を引き継いで、可能なすべての「状態」に数値を割り当てます（たとえば、1から9の間）。他の属性についても同じことを行います。

ここで、各属性の可能な値が 10 を超えないと仮定して、ATTR3 の値を 100、ATTR2 を 1000、ATTR1 を 10000 で乗算します。結果を合計すると、次の漠然としたハッシュに似たものになります。アイテム。何かのようなもの

10,000 * |ATTR1| + 1000 * |ATTR2| + 100 * |ATTR3|

ここでの利点は、10000 から 19000 までの値が同じ「状態」値を持つことを知っていることです。つまり、最初の桁は ATTR1 を表します。ATTR2 およびその他の属性についても同様です。

すべての値をソートし、バケツソートのようなものを使用してタイプごとに 1 つ選択し、考慮している数字がまだ選択されていないことを確認できます。

例: 最終値が

A: 15,700 = 10,000 * 1 + 1,000 * 5 + 100 * 7 B: 13,400 = 10,000 * 1 + 1,000 * 3 + 100 * 4 C: 13,200 = ... D: 12,300 E: 11,400 F: 10,900

すべての値が同じ ATTR1 であることがわかっています。2つは同じATTR2（BとC）です。および 2 は同じ ATTR3 (B、E) を持っています。

もちろん、これは、あなたが何をしたいのかを正しく理解していることを前提としています。やっぱり土曜日の夜です。

ps: はい、最初の乗数として '10' を使用することもできましたが、この例はもっと乱雑でした。はい、明らかに単純な例であり、ここには多くの可能な最適化があり、読者への演習として残されています。

于 2010-03-20T21:22:49.500 に答える
0

ATTR1、ATTR2、および ATTR3 が独立した確率変数 (一様確率項目上) であると仮定しましょう。(ATTR1、ATTR2、および ATTR3 がほぼ独立している場合、このサンプルは各属性でほぼ均一である必要があります。) 属性が均一に分布している 1 つの項目 (VAL1、VAL2、VAL3) をサンプリングするには、セットから VAL1 を均一に無作為に選択します。 ATTR1 = VAL1 の項目に対して ATTR2 の値のセットから VAL2 を一様にランダムに選択し、ATTR1 = VAL1 および ATTR2 = VAL2 の項目に対して ATTR3 の値のセットから VAL3 を一様にランダムに選択します。

個別のアイテムのサンプルを取得するには、上記の手順を繰り返し適用し、選択後に各アイテムを削除します。おそらく、これを実装する最良の方法はツリーでしょう。たとえば、

ID    ATTR1 ATTR2 ATTR3
1     a     c     e
2     a     c     f
3     a     d     e
4     a     d     f
5     b     c     e
6     b     c     f
7     b     d     e
8     b     d     f
9     a     c     e

その場合、ツリーは JavaScript オブジェクト表記で、

{"a": {"c": {"e": [1, 9], "f": [2]},
       "d": {"e": [3], "f": [4]}},
 "b": {"c": {"e": [5], "f": [6]},
       "d": {"e": [7], "f": [8]}}}

削除は再帰的に行われます。id 4 をサンプリングすると、リーフ レベルでリストから削除されます。このリストは空なので、tree["a"]["d"] からエントリ "f": [] を削除します。ここで 3 を削除すると、そのリストから 3 が削除され、空になります。したがって、tree["a"]["d"] からエントリ "e": [] を削除し、tree["a"][ を空にします。 "d"] ということで、順番に削除していきます。適切な実装では、各項目に O(属性の数) の時間がかかるはずです。

編集: 繰り返し使用するには、サンプル全体が収集された後にアイテムをツリーに再挿入します。これは、漸近的な実行時間には影響しません。

于 2010-03-20T19:20:45.923 に答える
0

アイデア＃2。

元のテーブルの各属性のヒストグラムを計算します。

各項目について、一意性スコア = p(ATTR1) xp(ATTR2) xp(ATTR3) を計算します (属性ごとに確率を掛けます)。

一意性で並べ替えます。

セットの前半の値のみを選択する (ステップ関数) からセット全体で均等に値を選択する (フラット ライン) まで、乱数の確率分布曲線を選択します。この場合、1/x 曲線がうまくいくかもしれません。

選択した確率曲線を使用して、並べ替えられたリストから値を選択します。

これにより、乱数の生成に使用する確率曲線を調整するだけで、よりユニークな値またはより均一な値にバイアスをかけることができます。

于 2010-03-20T20:04:47.063 に答える
0

これは非常に興味深い問題で、多くのアプリケーションが見られます。特にソフトウェアをテストする場合: 多くの「メインフロー」トランザクションを取得しますが、それが機能することをテストするために必要なのは 1 つだけであり、非常に多様なサンプルを取得することを選択する場合に好まれます。

ヒストグラム構造が本当に必要だとは思わないか、少なくともバイナリ構造 (不在/存在) だけが必要だと思います。

{ ATTR1: [val1, val2], ATTR2: [i,j,k], ATTR3: [1,2,3] }

これは、述語のリストを生成するために実際に使用されます。

Predicates = [ lambda x: x.attr1 == val1, lambda x: x.attr1 == val2,
               lambda x: x.attr2 == i, ...]

このリストには、sayN要素が含まれます。

K次に、このリストから要素を選択します。がそれよりK小さい場合は問題ありません。それ以外の場合は、リストの時間Nを複製します。iK <= N*iii = ceil(K/N)K <= Ni == 1

i = ceil(K/N)
Predz = Predicates * i # python's wonderful

そして最後に、そこで述語を取り上げ、それを満たす要素を探します...それは実際にランダム性が発生する場所であり、私はここで十分ではありません.

2 つの注意事項:

  • 各述語を実際に選択してから、述語のリストからランダムに選択して、選択を締めくくるK > Nことを厭わない場合。i-1したがって、最も一般的でない要素でさえも過剰な表現を保証します。
  • (1,2,3)属性はこのように完全に相関していません。3番目の要素であるを選択してもタプルを取得できないため、パターンを選択しても構わないと思って3いるかもしれません。生成された述語の
  • 効率的な選択が必要な場合は、効率上の理由から、述語カテゴリごとにテーブルを用意する必要があります。
于 2010-03-23T14:57:43.833 に答える