Как определить минимальный набор параметров, описывающих набор данных

Question

У меня есть куча регрессионных тестовых данных. Каждый тест представляет собой список сообщений (ассоциативных массивов), отображающих имена полей сообщений для значений. В этих данных много повторений.

Например

test1 = [ 
     { sender => 'client', msg => '123', arg => '900', foo => 'bar', ... }, 
     { sender => 'server', msg => '456', arg => '800', foo => 'bar', ... }, 
     { sender => 'client', msg => '789', arg => '900', foo => 'bar', ... }, 
    ] 

Я хотел бы представлять данные поля (в виде дерева решений минимальной глубины?) Таким образом, что каждое сообщение может быть программно регенерировать использованием минимального числа параметров. Например, в приведенном выше

• Foo всегда «Бар», так что мне не нужно упомянуть, что
• отправитель и клиент взаимосвязаны, поэтому мне нужно только упомянуть один или другой
• и сообщ каждый раз разный

Так что я хотел бы, чтобы иметь возможность восстанавливать эти сообщения с программой по линии

write_msg('client', '123') 
write_msg('server', '456') 
write_msg('client', '789') 

, где функция write_msg будет состоять из вложенных операторов if или подфункций, используя параметры.

Основываясь на моих исходных данных, как я могу определить «самый важный» набор параметров, то есть те, которые позволят мне воссоздать мой набор данных, используя наименьшее количество аргументов?

Answer 1

Следующие документы описывают algortithms для обнаружения функциональных зависимостей:

Ю. Huhtala, Дж Kärkkäinen, П. Porkka, и Х. Тойвонен. TANE: эффективный алгоритм обнаружения функциональности и приблизительные зависимости. Компьютерный журнал, 42 (2): 100-111, 1999, doi:10.1093/comjnl/42.2.100.

I. Savnik and P. A. Flach. Bottom-up индукция функциональных зависимостей от отношений. В Proc. AAAI-93 Семинар: знаний Discovery в базах данных, страницы 174-185, Вашингтон, округ Колумбия, США, 1993.

С. Висс, С. Giannella и Е. Робертсон. FastFDs: A Эвристический, глубинный Алгоритм для функции Mining Зависимости от экземпляров отношений. В Proc. Складирование данных и обнаружение знаний, страницы 101-110, Мюнхен, Германия, 2001, doi:10.1007/3-540-44801-2.

Hong Yao and Howard J. Hamilton. «Функциональные зависимости от данных». Data Mining and Knowledge Discovery, 2008, doi:10.1007/s10618-007-0083-9.

Там также была некоторая работа по выявлению многозначные зависимости:

I. Шавник и П. А. Флэч. «Discovery Mutlivalued Dependencies от Отношения». Интеллектуальный анализ данных журнал, 4 (3): 195-211, IOS Press, 2000.

Answer 2

Это очень похоже на Database Normalization.

У вас есть отношение (набор тестовых данных) и некоторые известные функциональные зависимости ({sender} => arg, {} => foo и, возможно, {msg} => отправитель. Если порядок тестов важен, add {testNr} => msg.) и вы хотите устранить избыточность.

Относитесь к тестовому набору в виде таблицы базы данных, применяйте правила нормализации и создавайте эквивалентные функции (getArgFromSender (отправитель) и т. Д.) Для каждого соединения.

Answer 3

Если количество полей и записей мало:

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

Если вы можете жить с довольно хорошим выбором полей:

начать предполагая, что вам нужно все поля. Затем выберите произвольное поле и посмотрите, можно ли его устранить; если это возможно, перечеркните его из набора полей. В противном случае выберите другое поле наугад и повторите попытку. Если вы обнаружите, что никакие поля не могут быть устранены, вы найдете разумный набор полей. Если бы вы выбрали другие поля, вы можете найти лучшее решение. Вы можете повторить всю процедуру несколько раз и выбрать наилучшее решение, если хотите. Такой подход называется hill climbing.

(я подозреваю, что эта проблема NP complete, то есть мы, вероятно, не знаем эффективного и мощного решения, поэтому не стоит терять сон, пытаясь придумать идеальное решение.)