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

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 всегда 'bar', поэтому мне не нужно упоминать об этом
• отправитель и клиент взаимосвязаны, поэтому мне нужно упомянуть только одну или другую
• и MSG каждый раз разные

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

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

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

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

Answer 1

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

Y. Huhtala, J. Kärkkäinen, P. Porkka, и Х. Тойвонен. ТАНЕ: Эффективный алгоритм обнаружения функционала и примерные зависимости. The Компьютерный журнал , 42 (2): 100–111, 1999, doi: 10.1093 / comjnl / 42.2.100 .

I. Савник и П. А. Флач. Вверх дном индукция функциональных зависимостей из отношений. В учеб. AAAI-93 Мастерская: Открытие знаний в базах данных , страницы 174–185, Вашингтон, округ Колумбия, США, 1993.

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

Хонг Яо и Говард Дж. Гамильтон. «Майнинг функциональных зависимостей от данных». Data Mining и Knowledge Discovery , 2008, doi: 10.1007 / s10618-007-0083-9 .

Была также проделана определенная работа по обнаружению многозначных зависимостей:

I. Савник и П. А. Флач. «Discovery Mutlivalued Зависимости от Отношения. " Интеллектуальный анализ данных Журнал , 4 (3): 195–211, IOS Press , 2000.

Answer 2

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

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

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

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

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

Answer 3

Это выглядит очень похоже на Нормализация базы данных .

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

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