|
116 виде таким образом, чтобы каждая строка представляла отдельную транзакцию, а столбцы соответствовали рассматриваемым элементам. В ячейках таблицы могут находиться либо «1», если соответствующий столбцу элемент присутствовал в транзакции, и «О» в противном случае. Помимо этого, перед началом анализа ЛПР задает минимально допустимые значения поддержки (minsupport) и достоверности (minconfidence). Это делается для того, чтобы сократить набор сгенерированных правил и исключить, генерацию «тривиальных» правил, которые известны и без анализа. Алгоритм APriori включает в себя два этапа, на первом из которых происходит генерация часто встречающихся наборов элементов (кандидатов), поддержка которых больше или равна minsupport, а на втором генерация правил из полученных наборов элементов с достоверностью, большей или равной minconfidence. Идея алгоритма использует свойство поддержки, в котором сказано, что поддержка любого набора элементов не может превышать минимальной поддержки любого из его подмножеств. Т.е., если какое-то из множеств рассматриваемых элементов не имеет необходимой поддержки, то все его супермножества также исключаются из рассмотрения. На первом этапе определяются одноэлементные множества, удовлетворяющие значению minsupport. После этого начинается поиск кэлементных кандидатов (значение к задается ЛПР перед началом анализа), также удовлетворяющих этому ограничению. Процесс поиска часто встречающихся наборов в алгоритме APriori показан на рис. 37. В приведенном коде формирование очередного ^-элементного множества на основании набора (&-7,)-элементных множеств происходит с помощью процедуры apriori_gen. В ней новое ^-элементное множество получается за счет дополнения существующего (^-^-элементного множества за счет добавления элемента из другого (&-7)-элементного множества. После того, как часто встречающиеся последовательности, удовлетворяющие ограничениям minsupport и minconfldence определены, из них извлекаются правила. Для этого в каждом часто встречающемся множестве F находятся все его непустые |
отдельную транзакцию, а столбцы соответствовали рассматриваемым элементам. В ячейках таблицы могут находиться либо «1», если соответствующий столбцу элемент присутствовал в транзакции, и «О» в противном случае. Помимо этого, перед началом анализа ЛПР задает минимально допустимые значения поддержки (minsupport) и достоверности (minconfidence). Это делается для того, чтобы сократить набор сгенерированных правил и исключить, генерацию «тривиальных» правил, которые известны и без анализа. Алгоритм APriori включает в себя два этапа, на первом из которых происходит генерация часто встречающихся наборов элементов (кандидатов), поддержка которых больше или равна minsupport, а на втором — генерация правил из полученных наборов элементов с достоверностью, большей или равной minconfidence. Идея алгоритма использует свойство поддержки, в котором сказано, что поддержка любого набора элементов не может превышать минимальной поддержки любого из его подмножеств. Т.е., если какое-то из множеств рассматриваемых элементов не имеет необходимой поддержки, то все его супермножества также исключаются из рассмотрения. На первом этапе определяются одноэлементные множества, удовлетворяющие значению minsupport. После этого начинается поиск кэлементных кандидатов (значение к задается ЛПР перед началом анализа), также удовлетворяющих этому ограничению. Процесс поиска часто встречающихся наборов в алгоритме APriori показан на рис. 14. В приведенном коде формирование очередного Аг-элементного множества на основании набора (Я:-У)-элементных множеств происходит с помощью процедуры apriori_gen. В ней новое А>элементное множество получается за счет дополнения существующего (Я:-7)-элемеитного множества за счет добавления элемента из другого (£-/)-элементного множества. 59 После того, как часто встречающиеся последовательности, удовлетворяющие ограничениям minsupport и minconfidence определены, из них извлекаются правила. Для этого в каждом часто встречающемся множестве F находятся все его непустые подмножества. Для каждого из этих множеств s справедливо следующее правило: s =>(F —s), если достоверность правила conf(s =>(F—s)) = supp(F)/supp(s) не меньше порога minconfidence. Однако, решение задачи поиска ассоциативных правил возможно и с применением математического аппарата искусственных нейронных сетей (ИНС). ИНС так же, как и ассоциативное правило, может использоваться для предсказания появления в векторе транзакции некоторых элементов, в зависимости от наличия в этом же векторе других элементов. Причем, в отличие от ассоциативного правила, указывающего на статистическую зависимость между левой и правой частями, аппарат ИНС позволяет получить аналитическую зависимость между упомянутыми элементами. Получение аналитической зависимости становится возможным, если рассматривать правую часть ассоциативного правила, как функцию от оставшихся элементов вектора транзакции, а ИНС, как способ аппроксимации этой функции. В этом случае нахождение ассоциативных правил может происходить с применением ИНС, на вход которой подается вектор транзакции, а единственный выходной сигнал которой предсказывает появление элементов правой части правила в этом же векторе. Главное отличие от рассмотренного ранее алгоритма APriori заключается в том, что при использовании ИНС необходимо заранее выбрать правую часть правила, т.е. совокупность элементов транзакции, для которой можно попытаться выяснить существует ли для нее левая часть правила или нет. Такой подход позволяет избежать длительного анализа полученного множества ассоциативных правил в поисках того, которое отражает интересующую исследователя зависимость. Пользователь может сразу выдвинуть предположение о структуре правой части правила, указав тем самым, какие 61 |