On the non-redundant representation of the minimax basis of strong associations.pdf Введение При поиске ассоциативных правил анализируемое множество данных обычно описывается бинарным контекстом - матрицей, строки которой отвечают объектам предметной области, а столбцы - признакам этих объектов. Единичное значение элемента матрицы трактуется как наличие у объекта соответствующего признака, а нулевое - как его отсутствие. Бинарное представление данных существенно расширяет математический аппарат для их исследования. Современные методы поиска ассоциативных правил базируются преимущественно на анализе формальных понятий и теории вероятностей [1-3]. Анализ формальных понятий, как прикладная ветвь алгебраической теории решёток, является удобным математическим аппаратом описания методов поиска ассоциативных правил [4 - 6]. Главная проблема при поиске ассоциативных правил - это огромное число правил, возникающих при анализе больших контекстов. Для решения этой проблемы используются различные меры значимости правил. С их помощью правила фильтруются и для анализа предъявляются только те, для которых значения мер превышают заданные пороговые значения. Подобная фильтрация, конечно, уменьшает число правил, но не решает проблему размерности полностью. Часто после фильтрации всё равно остаётся значительное число правил, при этом многие из них избыточные. Ассоциативное правило считается избыточным, если его удаление из множества правил не приводит к потере информации о связях между данными в рассматриваемой предметной области. Множество ассоциативных правил, не содержащее избыточных (в некотором смысле) правил, принято называть базисом. Существуют различные формальные определения избыточных ассоциативных правил и методы их устранения [7]. Наиболее развиты методы устранения избыточности для строгих ассоциативных правил. Для таких ассоциативных правил имеется плотная параллель с функциональными зависимостями из теории реляционных баз данных [8]. Строгие ассоциативные правила имеют достоверность, равную единице, и представляют интерес для приложений, где требуется высокая степень уверенности в установленных зависимостях между данными, например, в информационной безопасности, анализе компьютерных сетей и медицине [9-11]. В настоящее время известен ряд алгоритмов, позволяющих строить различные базисы для строгих ассоциативных правил. Наиболее значимыми базисами являются канонический и минимаксный. Канонический базис (или базис Дюкена - Гига) состоит из минимального числа строгих ассоциативных правил, рекуррентно описываемых в терминах псевдосодержаний [12]. Канонический базис математически глубоко исследован, однако все предложенные на сегодняшний день алгоритмы его построения в большей степени представляют теоретический, чем практический интерес [13]. Минимаксный базис состоит из строгих ассоциативных правил, имеющих минимальную посылку и максимальное следствие [14]. Для минимаксного базиса имеются хорошо апробированные алгоритмы, к которым относится алгоритм Close [7, 15]. Исследования показали, что в построенных канонических и минимаксных базисах остаётся некоторая избыточность, которая может быть устранена на основе выводимостей, подобных аксиомам Амстронга, известным в теории реляционных баз данных для функциональных зависимостей. В данной работе для строгих ассоциативных правил предложен алгоритм MClose, расширяющий возможности алгоритма Close. Алгоритм MClose позволяет в процессе построения минимаксного базиса устранять избыточность с сохранением поддержки и достоверности без дополнительного обращения к исходному бинарному контексту. Доказаны выводимости, обосновывающие корректность алгоритма MClose. Доказательство этих выводимостей - основной результат работы. 1. Основные термины и обозначения анализа формальных понятий Приведём термины и обозначения, традиционно применяемые в анализе формальных понятий [4 - 6]. Пусть для предметной области определены два непустых конечных множества G и M объектов и признаков соответственно (от немецких слов Gegenstande - объект, Merkmale - признак). Предполагаем, что все объекты в G и признаки в M различны. Пусть задано отношение I С G х M инцидентности между G и M. Тройку K = (G, M, I) принято называть формальным контекстом (или просто контекстом) предметной области. Считаем, что существование в I пары (g,m) означает, что объект g имеет признак m, и наоборот - признак m присущ объекту g. Выберем в K = (G, M, I) два произвольных элемента g G G и m G M. Определим для них два отображения ф и -: ф(д) = {m G M : (g, m) G I} , -(m) = {g G G : (g, m) G I} , где ф^) -множество признаков, присущих объекту g, а -(m) -множество объектов, обладающих признаком m. Отображения ф и - обобщаются на A С G и B С M следующим образом: ф(А) = П ФЫ = {m G M : Vg G A ((g,m) G I)} , -(B) = П -(m) = {g G G : Vm G B ((g, m) G I)} . Отсюда ф(А) -множество признаков, общих для всех объектов из A, а - (B) -множество объектов, которые обладают всеми признаками из B. Отображения ф и - определены так, что если Ai, A2 С G и Bi, B2 С M, то ф(А1 U A2) = ф(Al) П ф(A2), -(Bi U B2) = -(Bi) П -(B2). Целесообразно положить, что ф(0) = M и -(0) = G: пустому множеству объектов присущи все признаки из M и каждый объект рассматриваемого контекста K обладает пустым множеством признаков. Если для отображений ф и - применить единое обозначение (•)', то формулы для ф^), - (B), ф^1 U A2) и - (B1 U B2) записываются так: A' = П g' = {m G M : Vg G A ((g,m) G I)} ; (1) B' = П m' = {g G G : Vm G B ((g, m) G I)} ; (2) m£B (Ai U A2)' = Ai' П A2'; (3) (Bi U B2)' = Bi' П B2'. (4) Если g Е G и m Е M, то обозначения g' и m' традиционно служат сокращённой формой записи множеств ф(д) = {g} и ф(т) = {m} соответственно. Из определения отображений «'» вытекают свойства, которые формально можно выразить в виде следующих утверждений. Утверждение 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м - системами всех подмножеств множеств G и M соответственно, частично упорядоченными по теоретико-множественному включению [4, 5]. Известно, что для соответствий Галуа ф и ф справедливы равенства [5] ф(ф(ф(Л))) = ф(Л), ф(ф(ф^ ))) = ф^) или, то же самое, в единых обозначениях ((A')')' = (A'')' = A', ((B')')' = (B'')' = B'. (5) Двойное применение отображения «'» определяет оператор замыкания на 2M в алгебраическом смысле [4]. Ему свойственны: - рефлексивность: для любого B С M всегда B С B''; - монотонность: если B1 С B2 С M, то B1'' С B2'' С M; - идемпотентность: для любого B С M всегда (B'')'' = B''. Справедливость этих свойств вытекает из утверждений 1 и 2. Если B = B'', то множество признаков B С M называется замкнутым относительно оператора «''» в контексте K. Множество B'' = ф(ф^)) можно трактовать как набор признаков, которые всегда появляются в объектах контекста K вместе с признаками из B, причём это множество является наибольшим по включению в пределах K. Очевидно, что (0)'' = ф(ф(0)) = G', где G' - множество признаков, свойственных всем объектам контекста K. Если B' = 0, то всегда B" = ф(ф^)) = ф(0) = M. Если B' = 0, то, исходя из (1)-(4), замыкание для B С M можно вычислить за один просмотр контекста K по формуле B" = n {g' : B С д'} . (6) gee В анализе формальных понятий пара множеств (A,B), A С G, B С M, таких, что A' = B и B' = A, называется формальным понятием контекста K = (G, M, I) с объёмом A и содержанием B [6]. В формальном понятии (A,B) множества A и B всегда замкнуты относительно «''» в этом контексте: A = A'' и B = B''. С помощью формальных понятий возможно концептуальное (или понятийное) моделирование различных предметных областей [3, 6]. Замкнутые множества также нашли широкое применение в поиске ассоциативных правил [7, 14, 15]. 2. Ассоциативные правила и основные меры их значимости Ассоциативным правилом на множестве признаков контекста K = (G, M, I) называется упорядоченная пара множеств r = (X, Y), X, Y С M. Принято ассоциативное правило r = (X, Y) записывать в виде X ^ Y, здесь множества X и Y называют посылкой (или причиной) и заключением (или следствием) соответственно [16]. В анализе ассоциативных правил часто полагают, что посылка и заключение - непустые непересекающиеся множества. С формальных позиций эти ограничения несущественны. Применительно к заданному контексту K всякое ассоциативное правило X Y количественно характеризуется с помощью поддержки 5(X ^ Y) и достоверности Y (X ^ Y) [17]. Эти числовые функции определяются через понятие поддержки множества признаков. Поддержка 5(X) множества признаков X С M в контексте K = (G,M, I) -отношение числа объектов, которым присущи признаки X, к общему числу объектов, представленных в этом контексте: 5(X) = |X'|/|G|. (7) Таким образом, 5(X) -частота встречаемости в контексте K объектов, имеющих признаки X. Из формулы (7) следует, что для любого X С M значение 5(X) неизменно находится в естественных границах 0 ^ 5(X) ^ 1. (8) Чем ближе значение 5(X) к 1, тем большее число объектов рассматриваемого контекста обладает всеми признаками из X. В силу антимонотонности отображения «'» поддержка множества признаков также удовлетворяет свойству антимонотонности: для всякого контекста K = (G, M, I) и любых X, Y С M при X С Y верно неравенство 5(Y) ^ 5(X). (9) Согласно (9), поддержка множества признаков не может превышать поддержки любого из его подмножеств. Так, для произвольного X С M всегда 0 ^ 5(M) ^ 5(X) ^ 5(0) = 1. Множество признаков X С M называется частым в контексте K = (G, M, I), если его поддержка больше или равна заданному пороговому значению 50 Е [0,1]. Если 5(X) ^ 50 и X = X", то X называется частым замкнутым множеством признаков в K. Частые множества и частые замкнутые множества признаков традиционно служат основой для поиска ассоциативных правил в заданном контексте. Следует отметить, что в худшем случае число частых замкнутых множеств признаков контекста K совпадает с числом частых множеств признаков и экспоненциально зависит от |M| . Однако на практике обычно число частых замкнутых множеств значительно меньше числа частых множеств. Примеры контекстов с полиномиальным относительно | M| числом частых замкнутых множеств можно найти в [15]. Использование следующего утверждения позволяет при поиске ассоциативных правил вместо частых множеств признаков применять частые замкнутые множества и тем самым сокращать пространство поиска ассоциативных правил. Утверждение 3. Для всякого контекста K = (G, M, I) и любого множества X С M поддержка X" совпадает с поддержкой множества X: 5(X") = 5(X). Доказательство. Пусть X С M - произвольное множество признаков контекста K = (G, M, I). Тогда, исходя из (5) и (7), имеем равенство *(X ") = |(X ")'|/|G| = |X '|/|G| = £(X). Утверждение доказано. ■ Таким образом, если $(X) ^ $0, то ^(X") ^ $0, т.е. замыкание частого множества признаков также является частым. Поддержкой £(X ^ Y) ассоциативного правила X ^ Y относительно контекста K = (G, M, I) называется величина £(X ^ Y) = £(X U Y) = |(X U Y)'|/|G|, (10) указывающая, какая доля объектов этого контекста имеет признаки X U Y. Достоверность y(X ^ Y) ассоциативного правила X ^ Y относительно контекста K определяется как отношение числа объектов, обладающих всеми признаками из X U Y, к числу объектов, которым свойственны только признаки X: Y(X ^ Y) = |(X U Y)'|/|X'|. Достоверность ассоциативного правила через функцию поддержки выражается формулой Y(X ^ Y) = £(X ^ Y)/£(X) = £(X U Y)/£(X). (11) Заметим, что достоверность определяется формулой (11) только для тех ассоциативных правил X ^ Y, для которых $(X) = 0. Если $(X) = 0 (в контексте нет ни одного объекта, обладающего признаками X), то, согласно (8) и (9), $(X U Y) = 0. В этом особом случае полагают y(X ^ Y) = 1. Исходя из (7)-(11), достоверность ассоциативного правила X ^ Y при произвольных X, Y С M всегда находится в границах 0 ^ y(x ^ Y) ^ 1. Чем ближе значение y(X ^ Y) к 1, тем с большей уверенностью можно сказать, что признаки Y появляются в объектах рассматриваемого контекста вместе с признаками X. Ассоциативное правило X ^ Y называется минимаксным в контексте K = = (G, M, I), если для K не существует другого ассоциативного правила X* ^ Y*, такого, что X* С X и Y С Y* и £(X* ^ Y*) = £(X ^ Y), y(x* ^ Y*) = y(x ^ Y). Пусть заданы контекст K = (G, M, I) и $0, y0 -вещественные числа из [0, 1]. Будем говорить, что X ^ Y является ($0, y0)-ассоциативным правилом в K, если выполняются два условия: £o ^ £(X ^ Y) ^ 1; (12) Yo ^ y(x ^ Y) ^ 1. (13) Величины и Yo играют роль пороговых значений для поддержки и достоверности соответственно. При = 0 условие (12) отражает естественные границы поддержки. Данная ситуация свидетельствует о том, что нет ограничений на частоту появления признаков X U Y в K. При 70 = 1 условие (13) приводит к равенству 7(X ^ Y) = 1. В этом случае имеем ($0,1)-ассоциативное правило, которое будем называть строгим ассоциативным правилом. Таким образом, строгое ассоциативное правило - правило с достоверностью 1 и любой ненулевой поддержкой. Заметим, что ассоциативные правила с нулевой поддержкой и нулевой достоверностью не имеют практической ценности и поэтому не рассматриваются. 3. Свойства строгих ассоциативных правил Известен критерий наличия в контексте строгого ассоциативного правила [6]. Приведём его с доказательством. Утверждение 4. Достоверность ассоциативного правила X ^ Y относительно контекста K = (G, M, I) равна 1 тогда и только тогда, когда X' С Y' (или Y С X"). Доказательство. Согласно формуле (11), равенство 7(X ^ Y) = 1 верно тогда и только тогда, когда $(XUY) = $(X), или, то же самое, когда (X U Y)' = X'. В силу (4) имеем (X U Y) = X' П Y'. Равенство X' П Y' = X' возможно тогда и только тогда, когда X' С Y'. Предположим, что X' С Y'. По утверждениям 1 и 2 всегда Y С Y'', а при X' С Y' верно включение Y'' С X''. Отсюда Y С X''. Тогда в силу антимонотонности отображения «'» имеем (X'')' С Y'. С учётом (5) верно X' С Y'. ■ Заметим, что утверждение 4 тривиальным образом выполняется для X ^ X'' во всяком контексте K и при любом X С M. Рассмотрим некоторые частные случаи утверждения 4, важные с точки зрения устранения избыточности в множестве строгих ассоциативных правил. Случай 1: ассоциативные правила вида X ^ Y при любых Y С X С M. В силу антимонотонности отображения «'» при Y С X справедливо включение X' С Y'. Условие утверждения 4 выполняется, поэтому 7(X ^ Y) = 1. Таким образом, если в ассоциативном правиле заключение является подмножеством посылки, то такое правило имеет достоверность 1 в любом контексте K с поддержкой $(X). Подобные строгие ассоциативные правила не несут в себе информации о существенных отношениях между множествами признаков X и Y, кроме естественного отношения «целое и часть целого», поэтому их следует считать тривиальными и не принимать во внимание. В частности, ассоциативные правила вида 0 ^ 0, M ^ Y и X ^ 0 при любых X, Y С M относятся к тривиальным строгим правилам. Случай 2: ассоциативные правила вида 0 ^ Y при 0 = Y С M. Для всякого контекста K = (G, M, I) и Y С M всегда Y' С G. Кроме того, ^(0) = = 0' = G и $(0) = 1. Поэтому для правила 0 ^ Y имеем Y(0 ^ Y) = $(0 U Y)/$(0) = $(Y). Исходя из утверждения 4, равенство 7(0 ^ Y) = 1 имеет место тогда и только тогда, когда 0' С Y'. Поскольку ^(0) = 0' = G, то 0' С Y' верно лишь при G = Y'. Таким образом, строгое ассоциативное правило 0 ^ Y при Y = 0 имеет поддержку $(0) = 1 и отражает наличие жёсткого ограничения на контекст K: все объекты, представленные в этом контексте, обязательно обладают множеством признаков Y. Рассмотрим строгое ассоциативное правило X ^ Y .В силу (11) его поддержка всегда совпадает с поддержкой его посылки: $(X ^ Y) = $(X). Если $(X) ^ $0, то также $(X ^ Y) ^ $0. Если после какого-либо изменения правила X ^ Y результирующее правило имеет поддержку не менее $(X), то говорят, что такое изменение сохраняет поддержку исходного правила. Докажем свойства строгих ассоциативных правил, которые позволяют из одних строгих ассоциативных правил вывести другие строгие ассоциативные правила (с сохранением или без сохранения поддержки). Лемма 1. Пусть в контексте K = (G, M, I) множество X С M имеет поддержку 8(X) ^ 80. Тогда для контекста K при любом Y С X всегда справедливо строгое ассоциативное правило X ^ Y с поддержкой 8(X ^ Y) ^ 80. Доказательстео. При Y С X в силу антимонотонности отображения «'» всегда X' С YТогда по утверждению 4 ассоциативное правило X ^ Y является строгим. В силу (11) для него 8(X ^ Y) = 8(X) ^ 80. ■ Лемма 2. Если для контекста K = (G, M, I) справедливо строгое ассоциативное правило X ^ Y с поддержкой 8 (X), то при любом Z С M для этого контекста также верно строгое ассоциативное правило X U Z ^ Y с поддержкой 8(X U Z) ^ 8(X). Доказательстео. Воспользуемся утверждением 4 и свойством монотонности оператора замыкания. Так как X ^ Y является строгим ассоциативным правилом в K, то Y С X" и 8(X U Y) = 8(X). При X С X U Z верно включение X" С (X U Z)". Следовательно, Y С (X U Z)". Это означает, что для K справедливо строгое ассоциативное правило X U Z ^ Y и для него 8(X U Z U Y) = 8(X U Z). Отсюда с учётом антимонотонности поддержки имеем 8(X U Z) = 8(X U Z U Y) ^ 8(X U Y) = 8(X). Лемма доказана. ■ Лемма 2 отражает возможность пополнения посылки для строгого ассоциативного правила, но без гарантии сохранения поддержки. Особо следует отметить случай, когда расширение посылки строгого ассоциативного правила сохраняет поддержку этого правила. Следствие 1. Если для контекста K = (G, M, I) справедливо строгое ассоциативное правило X ^ Y с поддержкой 8(X), то при любом Z С Y для этого контекста также справедливо строгое ассоциативное правило X U Z ^ Y с поддержкой 8(X). Доказательство. Если y(X ^ Y) = 1, то по лемме 2 также y(X U Z ^ Y) = 1. Значит, верны равенства 8(X ^ Y) = 8(X U Y) = 8(X), 8(X U Z ^ Y) = 8(X U Z U Y) = 8(X U Z). Отсюда при Z С Y имеем 8(X U Z ^ Y) = 8(X U Z U Y) = 8(X U Y) = 8(X). ■ Лемма 3. Пусть в контексте K = (G, M, I) множество X С M имеет поддержку 8(X) ^ 80. Если для K справедливы строгие ассоциативные правила X ^ Y и X ^ Z, то для этого контекста также справедливо строгое ассоциативное правило X ^ Y U Z с поддержкой 8(X) ^ 80. Доказательство. По утверждению 4, поскольку X ^ Y и X ^ Z являются строгими ассоциативными правилами в K, выполняются включения Y С X" и Z С С XЗначит, Y U Z С X", что достаточно для выполнимости строгого ассоциативного правила X ^ Y U Z в заданном контексте. В данном случае 8(X ^ Y U Z) = 8(X) ^ 80, т. е. свойство аддитивности сохраняет поддержку исходных правил. ■ Легко убедиться, что свойства рефлексивности и пополнения невыполнимы для произвольных (80, y0)-ассоциативных правил. Однако следующее свойство, называемое проективностью, выполняется для любых (80, y0)-ассоциативных правил. Лемма 4. Если для K = (G, M, I) справедливо ($o, Yo)-ассоциативное правило X ^ Y, то при любых Z С Y и Y = 0 для этого контекста также верно ($o,Yo)-ассоциативное правило X ^ Z. Доказательство. Поскольку Z С Y и Y = 0, то Y можно представить в виде Y = ZU(Y\Z). Тогда, согласно условию (12) и антимонотонности функции поддержки, имеем £о ^ £(X U Y) = £(X U (Z U (Y\Z))) = £((X U Z) U (Y\Z)) ^ £(X U Z). Значит, $(X ^ Z) удовлетворяет условию (12). Аналогично, полагая, что $(X) = 0, получаем Yo ^ y(x ^ Y) = £(X U Y)/£(X) ^ 5(X U Z)/£(X) = y(X ^ Z). Следовательно, y(x ^ Z) удовлетворяет условию (13). При #(X) = 0 всегда y(x ^ ^ Y) = 1 при любом Y, в том числе и Z С Y. Применительно к строгим ассоциативным правилам лемма доказывается тривиальным образом. Если для контекста K справедливо строгое ассоциативное правило X ^ Y, то Y С X". Значит, при любых Z С Y и Y = 0 справедливо включение Z С X". Следовательно, X ^ Z является строгим ассоциативным правилом в K. Кроме того, 5(X ^ Y) = £(X), £(X ^ Z) = £(X). Если £(X) ^ й, то 5(X ^ Z) ^ fo. Лемма доказана. ■ Лемма 4 отражает тот факт, что правую часть всякого ($0, Yo)-ассоциативного правила можно «расщепить» до отдельного признака, сохраняя при этом поддержку и достоверность в заданных границах. Для строгих ассоциативных правил леммы 3 и 4 констатируют равноценность различных эквивалентных форм записи этих правил. Следствие 2. Представление строгого ассоциативного правила X ^ Y U Z эквивалентно его представлению в виде двух строгих ассоциативных правил X ^ Y и X ^ Z, при этом £(X ^ Y U Z) = £(X ^ Y) = £(X ^ Z) = £(X). Лемма 5. Если для контекста K = (G, M, I) справедливы строгие ассоциативные правила X ^ Y и Y ^ W и $(X) ^ $o, то какими бы ни были X, Y, W С M, для этого контекста также справедливо строгое ассоциативное правило X ^ W с поддержкой

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

Витяев Е. Е., Демин А. В., Пономарев Д. К. Вероятностное обобщение формальных понятий // Программирование. 2012. №5. С. 18-34.

Городецкий В. И., Самойлов В. В. Ассоциативный и причинный анализ и ассоциативные байесовские сети // Тр. СПИИРАН. 2009. Вып. 9. С. 13-65.

Кузнецов С. О. Автоматическое обучение на основе анализа формальных понятий // Автоматика и телемеханика. 2001. №10. С. 3-27.

Биркгоф Г., Барти Т. Современная прикладная алгебра. СПб.: Лань, 2005. 400 с.

Гуров С. И. Булевы алгебры, упорядоченные множества, решетки: определения, свойства, примеры. М.: Книжный дом «ЛИБРОКОМ», 2013. 352 с.

Ganter B. and Wille R. Formal Concept Analyses: Mathematical Foundations. Springer Science and Business Media, 2012. 314 p.

Pasquier N., Bastide Y., TaouiR., and Lakhal L. Generating a condensed representation for association rules // J. Intelligent Inform. Systems. 2005. V. 24. No. 1. P. 29-60.

Майер Д. Теория реляционных баз данных. М.: Мир, 1987. 608 с.

Батура Т. В. Модели и методы анализа компьютерных социальных сетей // Программные продукты и системы. 2013. №3. С. 130-137.

Платонов В. В., Семенов П. О. Методы сокращения размерности в системах обнаружения сетевых атак // Проблемы информационной безопасности. Компьютерные системы. 2012. №3. С. 40-45.

Ilayaraja M. and Meyyappan T. Mining medical data to identify frequent diseases using Apriori algorithm // Pattern Recognition, Informatics and Mobile Engineering (PRIME), IEEE, 2013. P. 194-199.

Duquenne V. and Obiedkov S. A. Attribute-incremental construction of the canonical implication basis // Ann. Math. Artif. Intelligence. 2007. V.49. No. 1. P. 77-99.

Rudolph S. Some notes on pseudo-closed sets // LNCS. 2007. V.4390. P. 151-165.

Zaki M. J. and Hsiao C.-J. Efficient algorithms for mining closed itemsets and their lattice structure // IEEE Trans. Knowledge Data Eng. 2005. V. 17. No. 4. P. 462-478.

Uno T., Asai T., Uchida Y., and Arimura H. An efficient algorithm for enumerating closed patterns in transaction databases // LNCS. 2004. V. 3245. P. 16-31.

Zhang C. and Zhang S. Association Rules Mining. Springer, 2002. 240 p.

Geng L. and Hamilton H. J. Interestingness measures for data mining: a survey // ACM Computing Surveys. 2006. V. 38. No. 3. Article 9.