Algorithm for constructing a non-redundant minimax basis of strong associative rules.pdf При поиске ассоциативных правил анализируемое множество данных обычно описывается бинарным контекстом - матрицей, строки которой отвечают объектам предметной области, а столбцы - признакам этих объектов. Единичное значение элемента матрицы трактуется как наличие у объекта соответствующего признака, а нулевое - как его отсутствие. Бинарное представление данных существенно расширяет математический аппарат для их исследования. Многие современные методы поиска строгих ассоциативных правил базируются на свойствах замкнутых множеств [1, 2]. Строгие ассоциативные правила имеют достоверность 1 и представляют интерес для тех приложений, где требуется высокая степень уверенности в установленных зависимостях между данными, например в информационной безопасности и анализе компьютерных сетей [3, 4]. Главная проблема при поиске ассоциативных правил - это огромное число правил, возникающих при анализе больших контекстов. Для решения этой проблемы используются различные меры значимости. С их помощью правила фильтруются и для анализа предъявляются только те, для которых значения мер значимости превышают заданные пороговые значения. Подобная фильтрация, конечно, уменьшает число правил, но не решает проблему размерности полностью. Часто после фильтрации всё равно остается значительное число правил, при этом многие из них избыточные. Ассоциативное правило считается избыточным, если его удаление из множества правил не приводит к потере информации о связях между данными в рассматриваемой предметной области. Множество ассоциативных правил, не содержащее избыточных (в некотором смысле) правил, принято называть базисом. В настоящее время известен ряд алгоритмов, позволяющих строить различные базисы для строгих ассоциативных правил. Наиболее значимыми базисами являются канонический и минимаксный. Канонический базис (или базис Дюкена - Гига) состоит из минимального числа строгих ассоциативных правил, рекуррентно описываемых в терминах псевдосодержаний [5]. Канонический базис математически глубоко исследован, однако все предложенные на сегодняшний день алгоритмы его построения в большей степени представляют теоретический, чем практический интерес. Минимаксный базис состоит из строгих ассоциативных правил, имеющих минимальную посылку и максимальное следствие. Для построения минимаксного базиса имеются хорошо апробированные практикой алгоритмы, к которым относится алгоритм Close [6]. В данной работе предлагается алгоритм MClose, расширяющий возможности алгоритма Close. Алгоритм MClose формирует для бинарного контекста неизбыточное множество минимаксных строгих ассоциативных правил. Для описания сути предлагаемого алгоритма введём необходимые понятия и обозначения. Пусть для предметной области определены два непустых конечных множества G и M объектов и признаков соответственно. Предполагаем, что все объекты в G и признаки в M различны. Пусть задано отношение I С G х M инцидентности между G и M. Тройку K = (G, M, I) принято называть контекстом предметной области. Считаем, что существование в I пары (g,m) означает, что объект g имеет признак m, и наоборот, признак m присущ объекту g. Выберем два произвольных элемента g Е G и m Е M. Определим для них два отображения ф и -: 0(g) = {m Е M : (g,m) Е I} - множество признаков, присущих объекту g; -(m) = {g Е G : (g,m) Е I} - множество объектов, которые обладают признаком m. Отображения ф и - обобщаются на A С G и B С M следующим образом: ф(А) = П 0(g) = {m Е M : Vg Е A ((g,m) Е I)}, -(B) = П -(m) = {g Е G : Vm Е B ((g,m) Е I)}. Таким образом, ф(А) -множество признаков, общих для всех объектов из A; -(B) - множество объектов, которые обладают всеми признаками из B. Если для отображений ф и - применить единое обозначение (•)', то формулы для ф(А), - (B) записываются так: А' = П g' = {m Е M : Vg Е A ((g, m) Е I)}, (ПА B' = П m' = {g Е G : Vm Е B ((g, m) Е I)}. Из определения этих отображений вытекают свойства, которые формально можно выразить в виде следующих утверждений. Утверждение 1. Для всякого контекста K = (G, M, I) и любых B1,B2 С M верны следующие свойства: - антимонотонность: если B1 С B2, то B2' С B1'; - экстенсивность: B1 С B1'', где B1'' = ((B1)') С M. Утверждение 2. Для всякого контекста K = (G,M, I) и любых A1,A2 С G верны следующие свойства: - антимонотонность: если A1 С A2, то A2' С A1'; - экстенсивность: A1 С A1'', где A1'' = ((A1)') С G. В силу утверждений 1 и 2, отображения ф и - составляют пару соответствий Галуа между множествами 2G и 2м, частично упорядоченными по включению [1]. Двойное применение отображения «'» определяет оператор замыкания на 2м в алгебраическом смысле [2]. Множество признаков B С M, для которого B = B", называется замкнутым относительно оператора «

Скачать электронную версию публикации