我有一个项目表[ID, ATTR1, ATTR2, ATTR3]。我想选择大约一半的项目，但尝试获得一个未聚集的随机结果集。换句话说，ATTR1 值、ATTR2 值和 ATTR3 值的分布相当均匀。这不一定代表整个数据，换句话说，总表可能通常集中在某些属性值上，但我想选择一个更多样化的子集。这些属性不是相互关联的，因此 ATTR1 和 ATTR2 之间没有真正的关联。
例如，假设 ATTR1 = "State"。我希望我的子集中的每个行项目都来自不同的州，即使在整个集合中，我的大部分数据都集中在几个州。并且对于其他两个属性也同样如此。（我意识到有些表可能无法做到这一点，但有足够的数据，不太可能没有解决方案）
关于有效算法的任何想法？谢谢！我什至不知道如何搜索这个:)
（顺便说一句，如果这需要对整个集合进行预计算或索引，也可以，只要我能快速抽出随机变化的子集）
有趣的问题。既然你想要大约一半的列表，那么这个怎么样： -
创建一个完全随机选择的一半值的列表。计算每个选定项目的 ATTR1、ATTR2、ATTR3 值的直方图。
：环形
现在随机选择一个在当前列表中的项目和一个不在的项目。
如果新项目增加了直方图中唯一属性数量的“熵”，请保留它并更新直方图以反映您刚刚所做的更改。
重复 N/2 次或更多次，具体取决于您想要强制它移动到覆盖每个值而不是随机的程度。你也可以使用“模拟退火”并逐渐改变接受交换的概率——从“有时允许交换，即使它变得更糟”到“只有在它增加多样性时才交换”。
恕我直言
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')
但是假设你的表非常大（否则你为什么需要算法；）并且数据分布相当均匀，在实际场景中会有更多的命中。在这个虚拟案例中，有太多的失误使算法看起来效率低下。
让我们假设 ATTR1、ATTR2 和 ATTR3 是独立随机变量（在一个统一的随机项上）。（如果 ATTR1、ATTR2 和 ATTR3 只是近似独立，那么这个样本在每个属性中应该是近似均匀的。）要采样一个属性均匀分布的项目（VAL1、VAL2、VAL3），从集合中随机均匀地选择 VAL1在 ATTR1 的值中，从 ATTR2 的值集合中均匀随机选择 VAL2，而不是 ATTR1 = VAL1 的项目，从 ATTR3 的值集合中均匀随机选择 VAL3，而不是 ATTR1 = VAL1 和 ATTR2 = VAL2 的项目。
要获得不同项目的样本，请重复应用上述过程，在选择后删除每个项目。实现这一点的最佳方法可能是一棵树。例如，如果我们有
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 进行采样，那么我们会在叶级从其列表中删除它。这个列表是空的，所以我们从树[“a”][“d”]中删除条目“f”：[]。如果我们现在删除 3，那么我们从它的列表中删除 3，它清空，所以我们从树 [“a”][“d”] 中删除条目“e”：[]，它清空树 [“a”][ "d"]，所以我们依次删除。在一个好的实现中，每个项目都应该花费时间 O(# of attributes)。
编辑：为了重复使用，收集整个样本后将项目重新插入树中。这不会影响渐近运行时间。
这是一个非常有趣的问题，我可以看到许多应用程序。尤其是对于测试软件：您会获得许多“主流”事务，但只需要一个来测试它是否有效，并且在选择获取极其多样化的样本时您更愿意。
我不认为你真的需要直方图结构，或者至少只需要一个二进制结构（不存在/存在）。
{ 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就可以了，否则我们将复制列表i时间，所以当然，K <= N*i并且i最少，所以i = ceil(K/N)（请注意，尽管 if K <= N, with ，但它仍然有效i == 1）。
i = ceil(K/N)
Predz = Predicates * i # python's wonderful
最后，在那里选择一个谓词，并寻找一个满足它的元素......这就是随机性实际发生的地方，而我在这里还不够。
两个备注：
K > N您可能愿意实际选择i-1每个谓词的时间，然后从谓词列表中随机选择以结束您的选择。从而确保即使是最不常见的元素的过度表示。(1,2,3)通过选择第三个元素来获得元组3，因此也许一种改进是将一些相关属性组合在一起，尽管它可能会增加数量生成的谓词接管您的示例，为每个可能的“状态”分配一个数值（例如，在 1 和 9 之间）。对其他属性执行相同操作。
现在，假设每个属性的可能值不超过 10 个，将 ATTR3 的值乘以 100，ATTR2 的值等于 1000，ATTR1 的值等于 10000。将结果相加，您最终会得到类似于模糊哈希的结果该项目。就像是
10,000 * |ATTR1| + 1000 * |ATTR2| + 100 * |ATTR3|
这里的好处是您知道 10000 和 19000 之间的值具有相同的“状态”值；换句话说，第一位数字代表ATTR1。ATTR2 和其他属性相同。
您可以对所有值进行排序，并使用诸如桶排序之类的方法为每种类型选择一个，检查您正在考虑的数字是否尚未被选择。
一个例子：如果你的最终值是
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”作为第一个乘数，但这个例子会更混乱；是的，这显然是一个幼稚的例子，这里有很多可能的优化，留给读者作为练习
想法#2。
计算原始表上每个属性的直方图。
对于每个项目计算它的唯一性分数 = p(ATTR1) xp(ATTR2) xp(ATTR3) （乘以它具有的每个属性的概率）。
按唯一性排序。
为您的随机数选择一条概率分布曲线，范围从仅选取集合前半部分的值（阶梯函数）到在整个集合中均匀选取值（一条平线）。在这种情况下，也许 1/x 曲线可能适合您。
使用您选择的概率曲线从排序列表中选择值。
这允许您仅通过调整用于生成随机数的概率曲线将其偏向更多唯一值或更多均匀性。
我不知道（我希望知道的人会回答）。这就是我想到的：为MCMC制作一个分布，将最大权重放在具有“多样性”的子集上。
假设表中的项目由某种形式的 id 索引，我将在一个循环中遍历表中的一半项目，并使用随机数生成器来获取数字。