寻找最小的唯一性条件集合

Question

我有一组具有属性的对象。我想找到最简单的一组条件，可以精确地指定其中一个对象（我不在乎是哪个对象）。

例如，给出{a=1，b=1，c=1}，{a=1，b=2，c=1}，{a=1，b=1，c=2}，指定b==2（或c==2）将给我一个唯一的对象。

同样，给定{a=1，b=1，c=1}，{a=1，b=2，c=2}，{a=1，b=2，c=1}，指定b==2和c==2（或b==1 && c==1或b==2 && c==1）将给我一个唯一的对象。

这听起来像是一个已知的问题，有一个已知的解决方案，但我还没有找到正确的问题表述方式，以便让我进行谷歌搜索。

- Rasmus Faber

---

所以，假设给定一个对象，你想找到最小的一组条件来将它与集合分离开来？例如，给定 {a=1, b=1, c=1}，{a=1, b=2, c=1}，{a=1, b=1, c=2} 和对象 {a=1, b=2, c=1}，解决方案将是 b==2 吗？ - Jacob

@Jacob：不，我想要一组最小的标准，可以将任何对象与该集合分离。 - Rasmus Faber

“any”是什么意思？你是说每个对象需要一组不同的标准吗？ - Jacob

@Jacob：我想不出任何例子，不等式比等式能够产生更少的标准。我有什么疏忽吗？ - Rasmus Faber

这是一个非常有趣的问题。最后一个问题（可能）：输入的定义域是什么（整数，实数等）？ - Jacob

Answer 1

这是人工智能中已知的问题之一 - 特征选择。有许多算法可以做到这一点，只需在Google上搜索“特征选择”“人工智能”。

主要问题在于，当样本集很大时，需要使用某种启发式方法才能在合理的时间内得出解决方案。

特征选择的主要想法是通过消除具有很少或没有预测信息的特征来选择输入变量的子集。

有关数据挖掘中的特征选择，请参阅此处。

- OSH

---

+1 我希望你不介意，我在你的回答中加入了一些关于特征选择的解释。 - Lieven Keersmaekers

Answer 2

选择目标的自由有点不寻常。如果指定了目标，则本质上就是set cover problem。下面是两个对应的实例并排放置。

A={1,2,3} B={2,4} C={3,4} D={4,5}

0: {a=0, b=0, c=0, d=0}  # separate 0 from the others
1: {a=1, b=0, c=0, d=0}
2: {a=1, b=1, c=0, d=0}
3: {a=1, b=0, c=1, d=0}
4: {a=0, b=1, c=1, d=1}
5: {a=0, b=0, c=0, d=1}

尽管集合覆盖是NP难问题，但您的问题有一个O(m^{log n + O(1)} poly(n))算法，其中m是属性数量，n是项目数量（最优标准集大小不超过log n），这使得NP难度证明变得不太可能。我想起了Junta problem（基本上是特征选择的理论形式化）的情况。

- Per

Answer 3

我不知道这个怎么容易地转换成算法，但是使用SQL，它已经是基于集合的，可以像这样进行：

• 构建一个包含输入表中所有可能列组合的表
• 选择所有出现次数等于输入表中存在的记录数量的不同组合。

SQL脚本

;WITH q (a, b, c) AS (
  SELECT '1', '1', '1'
  UNION ALL SELECT '1', '2', '2'
  UNION ALL SELECT '1', '2', '1'
  UNION ALL SELECT '1', '1', '2'
)
SELECT  col
FROM    (
          SELECT val = a, col = 'a'  FROM q
          UNION ALL SELECT b, 'b' FROM q
          UNION ALL SELECT c, 'c' FROM q
          UNION ALL SELECT a+b, 'a+b' FROM q
          UNION ALL SELECT a+c, 'a+c' FROM q
          UNION ALL SELECT b+c, 'b+c' FROM q
          UNION ALL SELECT a+b+c, 'a+b+c' FROM q
        ) f
GROUP BY
        col        
HAVING
        COUNT(DISTINCT (val)) = (SELECT COUNT(*) FROM q)

- Lieven Keersmaekers

Answer 4

您的问题可以定义如下：

1 1 1 -> A
1 2 1 -> B
1 1 2 -> C
.
.

其中1 1 1被称为特征向量，A是对象类。然后，您可以使用决策树（带修剪）来找到一组规则来分类对象。因此，如果您的目标是自动决定识别对象A的一组标准，那么您可以观察导致A的决策树上的路径。

如果您可以访问MATLAB，那么获取数据的决策树非常容易。

- Jacob