Модель ассоциативных правил

 Рассмотрим некоторое множество . Уровнем поддержки (support level) множества X на базе транзакций D понимается величина Supp(X), равная доле транзакций, содержащих все элементы из этого множества:

,

где |Z| означает мощность множества Z, N=|D|.

Для определения часто встречающихся наборов данных (frequent itemset) задается минимальный уровень поддержки minsupp. Набор данных X называется часто встречающимся в базе транзакций D , если Supp(X)>minsupp.

Ассоциативным правилом называется импликация X=>Y, где ,  и . Из такого правила мы устанавливаем закономерность следующего вида: "Если в транзакции встретился набор элементов X, то можно сделать вывод, что в этой же транзакции должен появиться набор элементов Y". Установление таких закономерностей дает нам возможность находить правила, называемые ассоциативными.

Пусть нам дана база транзакций D и известно, в какие группы (таксоны) входят элементы. Тогда можно извлекать из данных правила, связывающие группы с группами, отдельные элементы с группами и т.д. Обобщенным ассоциативным правилом называется импликация X=>Y, где ,  и  и где ни один из элементов, входящих в набор Y, не является предком ни одного элемента, входящего в X.

Рассмотрим далее наиболее важные характеристики ассоциативных правил.

Поддержка правила X=>Y  представляет собой количество транзакций, содержащих совместно X и Y:

S(X=>Y)=S( ).

 Аналогично определяется уровень поддержки и минимальный уровень поддержки ассоциативного правила. Уровень поддержки правила X=>Y определяет вероятность совместного появления наборов X и Y:

Supp(X=>Y)=Supp( )= ,

где P(A) – вероятность события A, P(A,B) – совместная вероятность событий A и B.

Достоверность правила показывает какова вероятность того, что из X следует Y. Правило X=>Y справедливо с достоверностью (confidence) c, если c% транзакций из D, содержащих X, также содержат Y,

Сonf(X=>Y) = Supp( )/Supp(X ) =P( | ),

где P(A|B) – условная вероятность выполнения события A при условии выполнения события B.

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

Кроме уровня поддержки и достоверности интерес вызывают следующие характеристики:

а) корреляция (correlation) показывает наличие статистической взаимосвязи появления наборов X и Y:

;

б) интересность (улучшение, lift = interest) показывает, полезнее ли правило случайного угадывания: если интересность больше единицы, то это значит, что с помощью правила предсказать наличие набора Y вероятнее, чем случайное угадывание, если меньше единицы, то наоборот:

;

в) убежденность(conviction) можно интерпретировать как отношение вероятности случайного угадывания к вероятности отсутствии набора Y приналичии набора X, если убежденность больше 1, тоэто значит, что с помощью правила предсказать отсутствие набора Y вероятнее, чем случайное угадывание;

г) полная уверенность(all-confidence) определяет отношение поддержки набора к максимуму поддержки его элементов:

All-confidence(A)= ;

д) плечо (leverage) показывает, насколько больше доля наборов при совместном появлении, чем при условии случайного выбора элементов:

 .