Генерирование правил

Исследования, посвященные генерации правил, в основном фокусируются на новых алгоритмах (дающих больше типов ассоциативных правил) и интересности правил. Более новые алгоритмы в основном используют новые стратегии, такие, как параллельные вычисления [7] и Evolutionary Algorithm (EA) [8]. Более новые типы правил добавляются размерность и качество в традиционные булевые типы правил. Примеры - количественные ассоциативные правила [1] и временные ассоциативные правила [5]. Новые критерии интересности [6, 10] имеют тенденцию быть более объективными, чем поддержка и достоверность.

Большинство ассоциативных правил сгенерировано путем подсчета количества транзакций, в которых правило встречается в базе данных - достоверности. Интуитивно ясно, что набор часто встречающихся элементов можно разделить на части и проводить подсчеты в параллель. Вместе с тремя параллельными алгоритмами для поиска наиболее часто встречающихся наборов элементов, в [7] представлена параллельная реализация процесса генерации правил, использующая указанный подход.

В последние годы, алгоритм EA был широко одобрен во многих научных областях. EA заимствует механизмы биологической эволюции и применяет их для решения проблем. Особенно хорошо он подходит для поисковых и оптимизационных проблем, так что проблема поиска ассоциативных правил как раз подходит для решения этим алгоритмом. В [8] EA был использован для генерации ассоциативных правил. Популяция часто встречающихся наборов бралась в качестве начальной популяции. Использование EA включает пересечение и мутацию этих наборов; популяция эволюционирует так, что в ней остаются только наборы, наилучшим образом удовлетворяющие функции пригодности (fitness function). Когда в популяции остается желаемое количество часто встречающихся наборов, алгоритм останавливается. Это оригинальный путь генерирования/поиска ассоциативных правил подходит для пересекающихся интервалов в различных наборах. Например, один набор может иметь интервал [10, 20], а другой [15, 25]. Здесь имеется разительный контраст по сравнению с другими технологиями, которые разделяют атрибуты на непересекающиеся интервалы. Правила, которые попадают в пересечения двух интервалов могут быть не найдены из-за потери информации. Алгоритм EA позволяет найти новые правила.

Были проведены, так же, исследования касательно типов ассоциативных правил. В начале исследований, посвященных data mining, доминировали булевые ассоциативные правила. Позже, фокус сместился на количественные ассоциативные правила. Количественные ассоциативные правила - это правила над количественными и категориальными атрибутами, подобно возрасту и семейному положению. Поиск таких правил включает разделение диапазона значений атрибутов на части, при этом информация при таком разделении может теряться. В [1] предложен алгоритм поиска количественных ассоциативных правил, основанный на Apriori. Там же вводится частичная завершенность (partial completeness) для изменения потерь информации при разделении и "больше чем ожидаемый" интерес (“greater than expected” interest) в качестве меры интересности. Частичная завершенность прямо пропорциональная потерям информации. Получая минимальное значение поддержки и частичной завершенности от пользователя, система может определить необходимое количество разделений. Количественное правило интересно только, если оно имеет "больше чем ожидаемую" поддержку и/или достоверность, указанную пользователем. Алгоритм масштабируется линейно с экспериментальными данными [1].

Размерность времени одна из тех, что существует для всех транзакций. Поэтому, она должна быть включена в процесс поиска часто встречающихся наборов, особенно, когда не все элементы существуют в течение всего периода, который охватывают собранные данные. В [5] введена концепция времени путем ограничения поиска часто встречающихся наборов согласно времени жизни элементов. Там же введена концепция временной поддержки в дополнение к обычной поддержке и достоверности. Время жизни элемента определяется как первый и последний момент времени появления элемента в базе данных. Временная поддержка - это ширина минимального интервала. Таким образом, правило рассматривается в том случае, если оно имеет достаточно высокие значения поддержки и временной поддержки. Побочным продуктом данного подхода является то, что старые, устаревшие наборы элементов, могут быть отброшены.

Любая ассоциация, найденная указанными выше алгоритмами, может быть правилом. Качество этих правил измеряется достоверностью. Однако, только те правила, достоверность которых выше определенного уровня, интересны и заслуживают внимания. Большинство алгоритмов определяют интересность в терминах величин поддержки и достоверности, указанных пользователем. Проблема в том, что эти алгоритмы полагаются на то, что пользователи смогут задать подходящие значения. Новый алгоритм, названый APACS2 [6], не требует от пользователя каких-либо догадок, но использует объективно интересные значения, называемые регулируемой разницей (adjusted difference). Более того, APACS2 может обнаруживать как позитивные, так и негативные ассоциативные правила. В [10] представлена новая концепция связанности (relatedness) как альтернативного подхода для определения интересности.

APACS2 использует регулируемую разницу как объективную меру интересности. Регулируемая разница определяется в терминах стандартизированной разницы (standardized difference ) и оценки максимальной правдоподобности (maximum likelihood estimate). Детали, касательно статистической теории, можно посмотреть в [16] . Если величина регулируемой разницы выше, чем 1.96, т.е. 95% нормального распределения, ассоциация рассматривается как существенно различная и, следовательно, интересная. Если регулируемая разница положительная, это означает, что правило вероятно, и наоборот. Направленная природа регулируемой разницы дает новую размерность поиску ассоциативных правил.

Интересность может быть субъективной, если применяются значения поддержки и достоверности, или объективной, если используется регулируемая разница, подобно [6]. Противоположная концепции - связность (relatedness), - была введена в [10] для того, чтобы исследовать соотношение между двумя элементами, на основе частоты их совместного появления в транзакциях и контекста. Связность предназначена для использования вместо интересности для количественных правил.

У связности есть три компонента: (1) среднее предсказывающая способность присутствия одного элемента при присутствии другого; (2) интенсивность появления пар элементов в присутствии других элементов; (3) замещаемость другого элемента для элемента в паре элементов. Эти три меры составляют силу связности в терминах частоты правила по отношению к другим элементам.

Исследование генерации правил начиналось с простых булевских типов с использованием субъективных значений поддержки и достоверности. Нынче оно включает различные типы правил с объективными мерами, подобно регулируемым разностям и связностям. Новые исследования добавили количественные и качественные аспекты генерации правил. Качество улучшено за счет использования объективных мер качества правил. Количество увеличено за счет применения оригинальных методологий, позволяющих осуществлять поиск правил в пересекающихся интервалах и находить негативные ассоциации.

Удивительно, что эта тема более не исследуется. Качество найденных правил в системе так же, если не более, важно, как скорость и масштабируемость алгоритмов поиска правил, поскольку реальная ценность Data mining - находить именно интересные правила. Только интересные правила полезны при принятии решений. Неинтересные или тривиальные правила можно получить из базы данных быстрее, но они - не интересны. Поэтому, больше усилий должно быть вложено в исследование более объективных мер, так чтобы поиск ассоциативных правил не требовал параметров, был более оперативным, а значит и менее субъективным и более качественным. Следуя этим путем, эксперты предметных областей смогут сфокусироваться на интерпретации правил вместо того, чтобы беспокоиться, как настроить параметры алгоритма, чтобы получить имеющие смысл правила.

С появлением все новых и новых типов данных, например, мультимедийных данных, больше исследований может проводиться для определения новых типов ассоциативных правил. Это позволит проанализировать новые шаблоны поведения и сделать новые предсказания. Способность профилирования мультимедийных данных в raw-формат (формат необработанных данных) может найти практическое применение в медицине или, даже, в национальной безопасности.

Выводы

Тема поиска ассоциативных правил изучается свыше десяти лет. Множество фундаментальных исследований уже проведено. Большое внимание было сфокусировано на производительности и масштабируемости алгоритмов, но недостаточно внимания было уделено качеству (интересности) генерируемых правил. В следующие десятилетия, внимание сфокусируется на практическом применении исследований в различных областях нашей жизни, например, генетических исследованиях, медицине, национальной безопасности и т.п.

По мере интеграции баз данных и с увеличением содержащихся в них наборов данных, поиску алгоритмов, позволяющих сканировать больше и быстрее, будет уделяться меньше внимание. Наоборот, распределенным алгоритмам, позволяющим разделять нагрузку в вычислительных сетях, внимания должно уделяться все больше.

Чем больше данных создается вне традиционных баз данных, data mining и поиск правил перерастут сканирование таблиц баз данных и начнут работать с данными в raw-формате, например, с видеоклипами. Вопросы производительности и масштабируемости станут еще более важны. Новые типы данных могут быть необходимы для продвижения новых типов анализа данных. Так же могут потребоваться более объективные меры интересности, чтобы эксперты предметных областей могли избежать манипуляций с критериями поиска правил при получении желаемых результатов.

Поиск ассоциативных правил будет оставаться благодатной темой для исследований. На основе исследований и развития в последнее десятилетие, в нем сформировались и выделились области, которые должны колоссально измениться в ближайшее десятилетие.