Поиск частых элементов произведения частичных порядков и ассоциативные правила

Abstract

Один из известных способов нахождения частых наборов атрибутов при поиске ассоциативных правил в бинарной базе данных основан на построении FP-дерева (Frequent Pattern Growth Tree). В случае небинарных данных, как правило, осуществляется бинаризация значений каждого небинарного атрибута по некоторому числовому порогу и задача сводится к построению классического FP-дерева. Результат существенно зависит от выбора указанных порогов. В работе предлагается модифицировать конструкцию классического FP-дерева путём введения для каждого небинарного атрибута дополнительной вершины, названной полной и содержащей информацию о возможных вариантах бинаризации значений этого атрибута. Новая модель FP-дерева названа полным FP-деревом. Рассматриваются вопросы применения полного FP-дерева для анализа небинарных данных при условии, что на значениях атрибутов заданы частичные порядки. Приводятся иллюстративные модельные примеры. One of the known ways to find frequent sets of attributes when searching for association rules in a binary database is based on the construction of a FP-tree (Frequent Pattern Growth Tree). In the case of binary data, as a rule, the values of each non-binary attribute are binarized by some numerical threshold and the problem is reduced to the construction of a classical FP-tree. The result depends significantly on the choice of the specified thresholds. The paper proposes to modify the construction of the classical FP-tree by introducing an additional vertex for each non-binary attribute, called a full vertex and containing information about possible variants for binarization of the values of this attribute. The new FP-tree model is named full FP-tree. We consider the application of the full FP-tree for nonbinary data analysis, provided that partial orders are specified on the attribute values. Illustrative model examples are given.