Нахождение наименьшего набора критериев уникальности

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) даст мне уникальный объект.

Это звучит как известная проблема,с известным решением, но я не смог найти правильную формулировку проблемы, чтобы позволить мне Google его.

Answer 1

Это действительно известная проблема в AI - выбор функций. Есть много алгоритмов для этого просто Google "выбор функции" "искусственный интеллект".

Основная проблема заключается в том, что когда набор выборок велик, вам необходимо использовать эвристические методы, чтобы найти решение в разумные сроки.

---

Выбор функций в Data Mining

Основная идея выбора функции заключается в выборе подмножества ввода переменные за счет исключения функций с небольшим или без предиктивного информация.

Answer 2

Свобода выбора цели необычна.Если цель указана, то это, по сути, проблема set cover .Вот два соответствующих экземпляра бок о бок.

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-твердости.Мне вспоминается ситуация с проблемой Хунта (в основном теоретическая формулировка выбора признаков).

Answer 3

Ваша проблема может быть определена следующим образом:

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

, где 1 1 1 называется вектором объектов, а A - классом объектов. Затем вы можете использовать деревья решений (с сокращением), чтобы найти набор правил для классификации объектов. Таким образом, если ваша цель состоит в том, чтобы автоматически определить набор критериев для идентификации объекта A, вы можете наблюдать путь в дереве решений, который ведет к A.

Если у вас есть доступ к MATLAB , получить дерево решений для ваших данных действительно легко.

Answer 4

Я не знаю, насколько легко это можно перевести в алгоритм, но с использованием SQL, который уже установлен на основе, он может выглядеть следующим образом

• построить таблицу со всеми возможными комбинациями столбцов из входной таблицы
• выберите все комбинации, которые кажутся равными количеству записей, присутствующих во входной таблице, как отдельные комбинации.

SQL Script

;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)