在不知道元素总数的情况下从数据流中随机拆分元素

Question

给定“分割比例”，我试图将数据集随机分为两组。问题是，我事先不知道数据集包含多少个项目。我的库从输入流中一个接一个地接收数据，并且期望将数据返回到两个输出流。理想情况下，应将所得的两个数据集精确地拆分为给定的拆分比率。

插图：

                            ??? stream A
 input stream ??? LIBRARY ???
                            ??? stream B

例如，给定分流比30/70，流A有望从输入流中接收30％的元素，而流B剩余的70％。订单必须保留。

---

到目前为止，我的想法是：

理念1：为每个元素“掷骰子”

一个明显的方法是：对于每个元素，算法都会随机决定该元素应该进入流A还是流B。问题是，结果数据集可能与预期的分割率相去甚远。给定的拆分率50/50，所得数据拆分可能会相去甚远（甚至可能100/0是非常小的数据集）。目的是使所得的分光比尽可能接近所需的分光比。

想法2：使用缓存并随机化缓存的数据

另一个想法是在传递元素之前先缓存固定数量的元素。这将导致缓存1000个元素并改组数据（或其对应的索引以保持顺序稳定），将它们拆分并传递结果数据集。这应该工作得很好，但是我不确定对于大型数据集，随机化是否真的是随机的（我想看分布时会出现模式）。

两种算法都不是最优的，所以希望您能对我有所帮助。

---

背景

这是关于基于层的数据科学工具的，其中每个层都通过流从上一层接收数据。在传递数据之前，希望该层将数据（向量）拆分为训练和测试集。输入数据的范围可以从几个元素到一个永无止境的数据流（因此，这些流）。该代码是用JavaScript开发的，但是这个问题更多的是关于算法而不是实际的实现。

Answer 1

您可以在概率偏离所需速率时对其进行调整。

这是一个示例以及对各种调整概率级别的测试。随着我们增加调整，我们看到分流器与理想比率的偏差较小，但这也意味着它的随机性较小（知道之前的值，您可以预测下一个值）。

// rateStrictness = 0 will lead to "rolling the dice" for each invocations
// higher values of rateStrictness will lead to strong "correcting" forces
function* splitter(desiredARate, rateStrictness = .5) {
	let aCount = 0, bCount = 0;

	while (true) {

		let actualARate = aCount / (aCount + bCount);
		let aRate = desiredARate + (desiredARate - actualARate) * rateStrictness;
		if (Math.random() < aRate) {
			aCount++;
			yield 'a';
		} else {
			bCount++;
			yield 'b';
		}
	}
}

let test = (desiredARate, rateStrictness) => {
	let s = splitter(desiredARate, rateStrictness);
	let values = [...Array(1000)].map(() => s.next().value);
	let aCount = values.map((_, i) => values.reduce((count, v, j) => count + (v === 'a' && j <= i), 0));
	let aRate = aCount.map((c, i) => c / (i + 1));
	let deviation = aRate.map(a => a - desiredARate);
	let avgDeviation = deviation.reduce((sum, dev) => sum + dev, 0) / deviation.length;
	console.log(`inputs: desiredARate = ${desiredARate}; rateStrictness = ${rateStrictness}; average deviation = ${avgDeviation}`);
};

test(.5, 0);
test(.5, .25);
test(.5, .5);
test(.5, .75);
test(.5, 1);
test(.5, 10);
test(.5, 100);

Answer 2

掷骰子两次怎么样：首先决定是否应该随机选择流，或者是否应该考虑比率。然后对于第一种情况，掷骰子，对于第二种情况，取比率。一些伪代码：

  const toA =
    Math.random() > 0.5 // 1 -> totally random, 0 -> totally equally distributed
      ? Math.random() > 0.7
      :  (numberA / (numberA + numberB) > 0.7);

这只是我的一个想法，我还没有尝试过......