Как определить минимальный набор параметров, описывающих набор данных
У меня есть набор данных регрессионного теста. Каждый тест - это просто список сообщений (ассоциативных массивов), отображающий имена полей сообщения в значения. В этих данных много повторений.
Например
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, поэтому мне не нужно об этом упоминать
- отправитель и клиент взаимосвязаны, поэтому мне нужно упомянуть только один или другой
- и сообщение каждый раз разное
Поэтому я хотел бы иметь возможность восстанавливать эти сообщения с помощью программы, подобной
write_msg( 'client', '123' )
write_msg( 'server', '456' )
write_msg( 'client', '789' )
где функция write_msg будет состоять из вложенных операторов if или вызовов подфункций с использованием параметров.
На основе моих исходных данных, как я могу определить «наиболее важный» набор параметров, то есть те, которые позволят мне воссоздать мой набор данных с использованием наименьшего количества аргументов?
Ответы 3
Это очень похоже на Нормализация базы данных.
У вас есть отношение (ваш набор тестовых данных) и некоторые известные функциональные зависимости ({sender} => arg, {} => foo и, возможно, {msg} => sender. Если порядок тестов важен, добавьте {testNr} => msg.), и вы хотите устранить дублирование.
Рассматривайте свой тестовый набор как таблицу базы данных, примените правила нормализации и создайте эквивалентные функции (getArgFromSender (отправитель) и т. д.) Для каждого соединения.
Если количество полей и записей невелико:
Грубая сила, перебирая каждую комбинацию полей, и для каждой комбинации определяет, есть ли в списке несколько элементов, которые соответствуют одному и тому же значению.
Если вы можете жить с довольно хорошим выбором полей:
Начните с предположения, что вам нужны все поля. Затем выберите поле случайным образом и посмотрите, можно ли его исключить; если можно, вычеркните его из набора полей. В противном случае выберите случайным образом другое поле и повторите попытку. Если вы обнаружите, что ни одно из полей не может быть удалено, значит, вы нашли разумный набор полей. Если бы вы сначала выбрали другие поля, возможно, вы найдете лучшее решение. Вы можете повторить всю процедуру несколько раз и при желании выбрать лучшее решение. Такой подход называется скалолазание.
(Я подозреваю, что это проблема НП завершена, т.е. мы, вероятно, не знаем эффективного и мощного решения, поэтому не стоит терять сон, пытаясь придумать идеальное решение.)
В следующих статьях описаны алгоритмы обнаружения функциональных зависимостей:
Y. Huhtala, J. Kärkkäinen, P. Porkka, and H. Toivonen. TANE: An efficient algorithm for discovering functional and approximate dependencies. The Computer Journal, 42(2):100–111, 1999, doi:10.1093/comjnl/42.2.100.
I. Savnik and P. A. Flach. Bottom-up induction of functional dependencies from relations. In Proc. AAAI-93 Workshop: Knowledge Discovery in Databases, pages 174–185, Washington, DC, USA, 1993.
C. Wyss, C. Giannella, and E. Robertson. FastFDs: A Heuristic-Driven, Depth-First Algorithm for Mining Functional Dependencies from Relation Instances. In Proc. Data Warehousing and Knowledge Discovery, pages 101–110, Munich, Germany, 2001, doi:10.1007/3-540-44801-2.
Hong Yao and Howard J. Hamilton. "Mining functional dependencies from data." Data Mining and Knowledge Discovery, 2008, doi:10.1007/s10618-007-0083-9.
Также была проведена некоторая работа по обнаружению многозначных зависимостей:
I. Savnik and P. A. Flach. "Discovery of Mutlivalued Dependencies from Relations." Intelligent Data Analysis Journal, 4(3):195–211, IOS Press, 2000.
Хм. Я рад видеть, что эта проблема действительно сложна, и я не мучился без причины. Спасибо за сбор этих ссылок.