3

我有一个具有如下属性的数据集：

Marital_status = {M,S,W,D}
IsBlind = {Y,N}
IsDisabled = {Y,N}
IsVetaran = {Y,N}

等等。大约有 200 个这样的变量。

我需要一种算法来生成属性组合，一次只有一个值。

换句话说，我的第一个组合是：

Marital_status = M, IsBlind = Y, IsDisabled = Y, IsVeteran = Y

下一组将是：

Marital_status = M, IsBlind = Y, IsDisabled = Y, IsVeteran = N

我尝试使用一个简单的组合生成器，将每个属性的每个值都视为一个属性本身。它不起作用，因为组合中包含相互排斥的选择，并且可能的组合数量非常大（准确地说是133873417996074857185490633899939406700260683726864088366400）

您能否建议一种算法（最好用 Java 编码）？

谢谢！！

4

3 回答 3

5

寻找另一种方式。如果您有 200 个变量，并且每个变量至少有 2 个选项，那么您将有 >= 2^200 个组合。如果您每纳秒生成一个组合，则枚举 2^200 个选项大约需要 10^43 年。

于 2009-10-02T20:54:02.463 回答
5

正如其他人（以及您自己）所指出的那样，不可能对此进行详尽的测试。

我建议你采取抽样方法，并用它进行测试。你有很强的理论背景，所以你将能够在互联网上找到自己的方式来找到和理解这一点。

但让我举一个小例子。现在，我将忽略可能的参数“集群”（密切相关）。

  • 创建一个数据样本，其中包含所有 200 个参数的所有可能值。这种详尽性确保不会忘记任何参数值。

    它不必预先创建，可以通过循环创建值。

  • 对于一个数据的每个样本，您需要添加其他值。一种简单的方法是选择要测试每个样本的次数（例如 N = 100）。对于一个数据的每个样本，您将随机生成 N 次其他值。

如果使用所有 200 个参数有 1000 个可能的值，并且 N=100，那将给我们 100K 次测试。

您可以通过多种方式详细说明这个基本思想：

  • 如果您希望您的测试是可重复的，您可以只生成一次，存储它，然后在以后的所有测试中重复使用相同的集合。
  • 您可以控制您的分布，以便每个值都被选择了相当多的次数。
  • 在现实生活中，所有 200 个参数都不会没有连接。许多参数实际上会与其他一些参数相关联，因为找到这些值的概率是不均匀的。
    我不会像以前那样只对一个参数进行初始穷举集，而是在一组连接的参数上运行穷举集。
于 2009-10-03T06:36:55.447 回答
3

正如基思指出的那样，如果没有排除的组合，组合的数量将是不可能的，这将使您的需求无法满足。但是，由于您已经说过您有互斥的选择，因此解决方案空间会更小。

小了多少？取决于有多少选择是互斥的。我建议在太努力之前做一些数学运算。

假设有足够多的选择是排他的，你仍然必须从本质上暴力破解它，但你不太可能找到一个现有的、有用的算法。

这让我想到了一个问题：您这样做的原因是什么 - 详尽的测试？听起来不错，但您可能会发现这是不可能的。我自己也遇到过这个问题，最后，你很可能会被迫结合一些精心挑选的“边缘”案例，再加上一些准随机选择的其他案例。

阅读了您上面的评论后，您对“互斥”的定义似乎与我不同，我担心您可能会遇到问题。

因此，给定的患者既不是盲人也不是盲人。伟大的。但这不是我（我怀疑这里的其他人）在你提到互斥时所理解的。

通过这些，我说的是，例如，如果失明，不能是非残疾人，或类似的东西。

如果您的属性之间没有大量相互排斥的相互关系来限制它们的组合，您将无法完成详尽的测试。

于 2009-10-02T21:23:23.323 回答