算法的想法？对列表进行随机排序，强调多样性

Question

我有一个包含 [ID, ATTR1, ATTR2, ATTR3] 的项目表。我想选择大约一半的项目，但尝试获得未聚集的随机结果集。换句话说，ATTR1 值、ATTR2 值和 ATTR3 值的分布相当均匀。这并不一定代表数据的整体，换句话说，总表可能通常集中在某些属性值上，但我想选择一个更多样化的子集。这些属性并不相互关联，因此 ATTR1 和 ATTR2 之间并不存在真正的相关性。

例如，假设 ATTR1 =“状态”。我希望子集中的每个行项目都来自不同的州，即使在整个集合中，我的大部分数据都集中在几个州。对于其他两个属性来说，这也同时成立。 （我意识到有些表可能无法实现这一点，但有足够的数据，不可能没有解决方案）

对于有效算法有什么想法吗？谢谢！我什至不知道如何搜索这个:)

（顺便说一句，如果这需要对整个集合进行预先计算或索引，只要我可以快速提取随机变化的子集，那就可以了）

Answer 1

有趣的问题。既然您想要大约一半的列表，那么这样如何：-

创建一个包含完全随机选择的一半值的列表。计算每个选定项目的 ATTR1、ATTR2、ATTR3 值的直方图。

:loop

现在随机选择当前列表中的一个项目和不在当前列表中的项目。

如果新项目增加了直方图中唯一属性数量的“熵”，请保留它并更新直方图以反映您刚刚所做的更改。

重复 N/2 次或更多，具体取决于您想要强制其覆盖每个值而不是随机的程度。您还可以使用“模拟退火”并逐渐改变接受交换的概率 - 从“有时允许交换，即使它会使情况变得更糟”开始到“仅在增加多样性时才交换”。

Answer 2

我不知道（希望知道的人能回答）。我想到的是：为 MCMC 制定一个分布，将最大的权重放在子集上'种类'。

Answer 3

假设表中的项目通过某种形式的 id 进行索引，我将在循环中迭代表中一半的项目，并使用随机数生成器来获取数字。

Answer 4

恕我直言

寻找多样性很困难，但生成多样性却很容易。

所以我们可以生成多种组合
然后在表中搜索具有这些组合的记录。

如果表已排序，那么搜索也会变得容易。

示例 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')

但是假设您的表非常大（否则为什么需要算法；）并且数据分布相当均匀，在实际场景中会出现更多命中。在这种虚拟情况下，有太多的失误，这使得算法看起来效率低下。

Answer 5

我们假设 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，该列表会清空，因此我们从 tree["a"]["d"] 中删除条目 "e": []，这会清空 tree["a"][ "d"]，所以我们依次删除。在一个好的实现中，每个项目应该花费 O(属性#) 的时间。

编辑：为了重复使用，请在收集整个样本后将项目重新插入树中。这不会影响渐近运行时间。

Answer 6

想法＃2。

计算原始表上每个属性的直方图。

对于每个项目，计算其唯一性得分 = p(ATTR1) xp(ATTR2) xp(ATTR3)（乘以它所具有的每个属性的概率）。

按独特性排序。

为随机数选择一条概率分布曲线，范围从仅选取集合前半部分中的值（阶跃函数）到在整个集合中均匀选取值（一条平坦线）。在这种情况下，也许 1/x 曲线可能适合您。

使用您选择的概率曲线从排序列表中选择值。

这使您可以通过调整用于生成随机数的概率曲线来将其偏向更独特的值或更均匀。

Answer 7

以您的示例为例，为每个可能的“状态”分配一个数值（例如，1 到 9 之间）。对其他属性执行相同操作。

现在，假设每个属性的可能值不超过 10 个，请将 ATTR3 的值乘以 100，ATTR2 的值乘以 1000，ATTR1 的值乘以 10000。将结果相加，您最终会得到类似于以下内容的模糊散列：该项目。大约

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

这里的优点是您知道 10000 到 19000 之间的值具有相同的“State”值；换句话说，第一个数字代表 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 = ...
日：12,300
电子：11,400
F：10,900

你知道你所有的值都有相同的 ATTR1； 2 个具有相同的 ATTR2（即 B 和 C）；和 2 具有相同的 ATTR3 (B, E)。

当然，这是假设我正确理解你想要做什么。毕竟是周六晚上。

ps：是的，我可以使用“10”作为第一个乘数，但示例会更混乱；是的，这显然是一个幼稚的例子，这里有很多可能的优化，留给读者作为练习

Answer 8

这是一个非常有趣的问题，我可以看到很多应用程序。特别是对于测试软件：您会获得许多“主流”交易，但只需要一个来测试它是否有效，并且在选择获取极其多样化的样本时您会更愿意。

我不认为你真的需要直方图结构，或者至少只需要一个二进制结构（不存在/存在）。

{ 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, ...]

该列表将包含 N 元素。

现在您希望从此列表中选择 K 元素。如果 K 小于 N 就可以了，否则我们将重复列表 i 次，这样 K <= N* i 且 i 当然是最小的，所以 i = ceil(K/N) （请注意，尽管如果 K <= N，其中i == 1）。

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

最后，在那里选择一个谓词，并寻找一个满足它的元素……这就是随机性真正发挥作用的地方，而我在这里还不够。

两点注释：

• 如果 K > N 您可能愿意实际选择每个谓词 i-1 次，然后从谓词列表中随机选择以完成您的选择。从而确保即使是最不常见的元素也能得到过度表达。
• 这样，属性完全不相关，您可能愿意选择模式，因为您永远无法通过选择第三个元素 3 来获得元组 (1,2,3) >，因此也许一种改进是将一些相关属性分组在一起，尽管出于效率原因它可能会增加生成的谓词数量
• ，但如果您希望进行有效的选择，则应该按谓词类别创建表。