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

Question

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

插图:

                            ┌─► stream A
 input stream ──► LIBRARY ──┤
                            └─► stream B

例如，给定 30/70 的拆分比率，预计流 A 将从输入流中接收 30% 的元素，而流 B 将接收剩余的 70%。订单必须保持不变。

---

到目前为止我的想法:

想法 1:为每个元素“掷骰子”

显而易见的方法:对于每个元素，算法随机决定该元素是应该进入流 A 还是流 B。问题是，生成的数据集可能与预期的拆分比相去甚远。给定 50/50 的拆分比率，生成的数据拆分可能相去甚远(对于非常小的数据集甚至可能是 100/0)。目标是使生成的分流比尽可能接近所需的分流比。

思路二:使用缓存并随机化缓存数据

另一个想法是在传递之前缓存固定数量的元素。这将导致缓存 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);