Интеллектуальный анализ XML-данных: Часть 2. Поиск ассоциативных правил в XML-данных

Поиск ассоциативных правил в статических и динамических XML-документах

Вторая статья этого цикла посвящена поиску ассоциативных правил в XML-документах. Поиск ассоциативных правил в XML-документах отличается от поиска правил в реляционных данных. Информация XML-документов может быть структурирована по-разному ввиду гибкости языка и иерархической организации. Эта статья знакомит также с понятием динамических ассоциативных правил. Рассматривается подход к поиску ассоциативных правил в изменяющихся XML-документах без повторного выполнения всего алгоритма поиска ассоциативных правил.

02 мая 2012 г. - Добавлены ссылки на 3-ю часть настоящей статьи во врезках во Введении и Заключении, а также в разделе Ресурсы.

Лаура Ирина Русу, руководитель группы разработки, консультант по DW и BI, Computershare Technology Services Australia, La Trobe University Australia

Фото Лауры Ирины РусуЛаура Русу (Laura Rusu) получила степень доктора информатики в Университете Ла-Троуб (Мельбурн, Австралия) в 2009 году, защитив диссертацию по хранению и интеллектуальному анализу XML-данных. Предложила несколько новых методов хранения и интеллектуального анализа XML-данных, представив их на ряде международных конференций и опубликовав более подробные работы в международных рецензируемых журналах. Написала главу книги, посвященную ассоциативным правилам для данных, добываемых из XML-документов, и редактировала книгу по технологиям хранения и интеллектуального анализа данных. Опыт Лауры представляет собой сочетание академических знаний, научных исследований и практической работы в ИТ-отрасли. С ней можно связаться по адресу: Laura.Rusu@acsmail.net.au.



20.06.2012

Введение

XML все больше становится предпочтительным языком представления, хранения данных и обмена данными во многих областях. Ввиду быстрого роста объемов информации, представленной в XML-формате, люди ищут рациональные методы решения задач хранения и анализа XML-документов. В первой статье этого цикла, "Несколько подходов к интеллектуальному анализу XML-данных", мы рассмотрели некоторые методы поиска скрытых знаний в XML-документах.

Из этой статьи вы узнаете об особенностях поиска ассоциативных правил XML (в отличие от поиска ассоциативных правил в реляционных данных). Мы также рассмотрим метод оценки достоверности ассоциативных правил XML, полученных из XML-документов, содержание которых меняется со временем. Эти различия и новый метод анализа данных XML иллюстрируются на нескольких примерах.


Поиск ассоциативных правил в реляционных данных

В первой части обсуждались ассоциативные правила, введенные Агравалом и Срикантом в 1993 году (Agrawal and Srikant, см. раздел Ресурсы) для реляционных данных с целью определения интересных соотношений, которые можно извлечь из набора транзакций при анализе потребительской корзины. Алгоритм для извлечения этого типа знаний называется алгоритмом Apriori. В нем используются понятия поддержки и достоверности.

Если есть набор отдельных элементов I и набор транзакций D, где любая транзакция T из D содержит только элементы из I, ассоциативным правилом R называется импликация "X к Y," где X и Y ― не связанные между собой элементы из I. Правило R имеет поддержку S в D, если s% транзакций из D содержат оба элемента X и Y, и достоверность c, если c% транзакций из D, содержащих X, содержат также и Y.

Например, ассоциативным правилом при анализе потребительской корзины будет: "Те, кто покупает продукт X, также покупают продукт Y, и это происходит в s% транзакций с достоверностью c%".

Транзакции и элементы при реляционном подходе

Понятие ассоциативных правил было введено для реляционных данных. В этом контексте транзакция представляет собой запись в таблице, а элемент — значение атрибута таблицы. Следовательно, набор транзакций представляет собой набор записей с одними и теми же атрибутами (столбцы и поля таблицы).

На рисунке 1 дано визуальное представление набора транзакций в таблице, и задача состоит в поиске ассоциативного правила как корреляции между значениями для двух предметов (атрибутов) X и Y. Образец набора транзакций демонстрирует несколько позиций, содержащих X и Y, которые расположены в произвольном порядке. Другие элементы набора включают либо X, либо Y.

Рисунок 1. Набор транзакций и элементов при реляционном подходе
Транзакции и элементы при реляционном подходе

Поиск ассоциативных правил в XML

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

Транзакции и элементы ассоциативных правил XML

В работах по анализу статических XML-документов используются концепции транзакций и элементов XML-данных. Набор транзакций представляет собой список сложных узлов, сформированных посредством запросов к XML-документам по определенным путям; один сложный узел образует транзакцию. Элементы – это простые узлы, дочерние по отношению к узлу транзакции.

В реляционных данных транзакция, извлеченная из таблицы, всегда содержит фиксированное количество элементов: число атрибутов, или столбцов, таблицы. XML-транзакция может иметь различное количество элементов в зависимости от уровня вложенности в документ и XML-схемы. Все вложенные пути в XML-документе, начиная с корня, можно представить как записи. Для любого узла документа каждый потомок рассматривается как запись, относящаяся к другим записям, расположенным на той же глубине или имеющим аналогичные теги (подробнее см. в разделе Ресурсы).

На рисунке 2 показан пример, где каждый узел <staff_member> (здесь Джон Браун и Мелисса Уайт) – это транзакции, а каждый узел <publi_what>, <publi_where> или <publi_when> - элемент. Каждая транзакция staff_member содержит одну или несколько публикаций под именем соответствующего сотрудника. Каждая публикация содержит элементы publi_what, publi_where и publi_when. (см. текстовую версию XML-документа из рисунка 2.)

Рисунок 2. Транзакции и элементы в XML-документе
Пример транзакций и элементов в XML-документе

Контекст, тело и голова ассоциативных правил XML

Контекст ассоциативных правил XML ― это анализируемые разделы XML-документов. Иногда нет необходимости анализировать всю информацию, содержащуюся в XML-документе. Следовательно, выбор контекста зависит от способности пользователей определить ограничения для множества XML-транзакций.

На рисунке 3 показан пример выделения контекста. Для анализа выбираются только те транзакции, которые относятся к сотрудникам, опубликовавшим работы после 2006 года. В данном случае только Меллисса Уайт публиковалась после 2006 года.

Рисунок 3. Выбор контекста в XML-документе
Пример выбора контекста в XML-документе

Если ассоциативное правило XML является импликацией X к Y (аналогично реляционному подходу, но между двумя сложными XML-узлами), то X - это тело правила, а Y - его голова. Тело и голова всегда определяются в контексте правила. Аналогично, поддержка и достоверность правила рассчитываются по отношению к определенному контексту.

Предположим, что контекст транзакций, отраженных на рисунке 3, охватывает всех сотрудников, которые публиковались после 2000, а не 2006 года. На рисунке 4 показан пример тела и головы того ассоциативного правила XML, в котором найдена гипотетическая связь между <publi_what> (значение "Data mining book" – это тело правила) и <publi_where> (значение "ABC publishing" – голова правила).

Рисунок 4. Тело и голова в XML-документе
Пример тела и головы в XML-документе

Примеры ассоциативных правил XML

На рисунке 5 показан пример XML-документа (department.xml) в виде дерева. Документ содержит данные о научных публикациях студентов и сотрудников, включая сведения о том, что, где и когда они публиковали. В целях рассмотрения общих концепций поиска ассоциативных правил XML предположим, что узлы <from_date> и <to_date> пусты, так что это статический, а не динамический XML-документ.

Рисунок 5. Статический XML-документ в виде дерева
Пример статического XML-документа в виде дерева

Следующие два ассоциативных правила XML иллюстрируют понятия транзакции, элемента, контекста, тела и головы правила с использованием документа, показанного на рисунке 5.

Пример 1 ассоциативного правила XML
Предположим, что нужно найти ассоциативные правила в информации о научных публикациях сотрудников, публиковавшихся после 2005 года. Пусть получено следующее правило:

"Сотрудники, публиковавшиеся после 2005 года в журнале XYZ, также ведут проекты в области ABC".

Рисунок 6 иллюстрирует концепции этого примера:

  • контекст содержит все сложные узлы <staff>, потому что требовалось найти публикации сотрудников, но не студентов;
  • выбор контекста означает выбор тех записей о публикациях, в которых значение <publi_when> больше 2005;
  • каждый узел <staff> - это транзакция; узел <staff> сложный и имеет другие дочерние узлы;
  • все простые узлы в составе сложного узла <staff>, относящиеся к научным публикациям и проектам, являются элементами – то есть узлами на следующих путях:
    • staff/publication/publi_what;
    • staff/publication/publi_where;
    • staff/publication/publi_when;
    • staff/project/name;
    • staff/project/domain;
    • staff/project/collab;
  • узлы на пути staff/publication/publi_where образуют голову правила;
  • узлы на пути staff/project/domain образуют тело правила.
    Рисунок 6. Ассоциативные правила XML в примере 1
    Визуальное представление ассоциативных правил XML из примера 1
Пример 2 ассоциативного правила XML
Предположим, что нужно найти ассоциативные правила в информации о научных публикациях сотрудников и студентов в целом. Пусть получено следующее правило:

"Студенты, публиковавшиеся в издании ABC, также сотрудничают с сотрудниками по научно-исследовательским проектам.

Рисунок 6 иллюстрирует концепции этого примера:

  • контекст содержит все сложные узлы <students> и <staff>, потому что не требовалось искать публикации только сотрудников или только студентов;
  • никакого выбора контекста нет, потому что рассматривается весь контекст, определенный выше;
  • каждый сложный узел <personal> является транзакцией;
  • все простые узлы в составе сложных узлов <staff> и <student>, относящиеся к научным публикациям и проектам, являются элементами, или узлами на следующих путях:
    • student/publication/publi_what;
    • student/publication/publi_where;
    • student/publication/publi_when;
    • staff/publication/publi_what;
    • staff/publication/publi_where;
    • staff/publication/publi_when;
    • staff/project/name;
    • staff/project/domain;
    • staff/project/collab;
  • узлы на пути student/publication/publi_where образуют голову правила;
  • узлы на пути staff/project/collab образуют тело правила.
    Рисунок 7. Ассоциативные правила XML в примере 2
    Визуальное представление ассоциативных правил XML из примера 2

Как видно из примеров 1 и 2, концепции транзакции и элемента при поиске ассоциативных правил в XML-документах обладают гибкостью.

Пример документа, показанного на рисунке 5, рисунке 6 и рисунке 7, считается статическим, и элементы <from_date> и <to_date> игнорируются. Предположим, что эти два узла не пустые, а получают значения в зависимости от срока действия XML-документа. Например, каждый год может создаваться новая версия документа department.xml. Версия 2007 года будет иметь <from_date>01/01/2007</from_date> и <to_date>31/12/2007</to_date>. Ассоциативные правила, описанные выше, будут справедливы только для 2007 года. Любые старые правила (обнаруженные в версиях XML-документа за предыдущие годы) могут быть или не быть таким же, как правила 2007 года. Таким образом, ассоциативные правила для динамических (многоверсионных) XML-документов требуют особого способа оценки их действительности в последующих версиях документа. Эти правила называются динамическими и обсуждаются в следующем разделе.


Динамические ассоциативные правила XML

В реальных приложениях ассоциативные правила, выявленные в первоначальной версии динамических XML-документов, зависят от количества и интенсивности изменений между последовательными версиями документа. Об ассоциативных правилах динамических XML-документов после ряда изменений можно судить по влиянию исторических изменений на первоначальные правила.

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

Один из способов решения этой задачи - выполнение алгоритма поиска ассоциативных правил по отношению к версиям документов после внесения изменений. Однако во многих случаях это неэффективно - например, когда изменений между версиями не много или они не критичны и не оказывают значительного реального влияния на первоначальные ассоциативные правила. То же самое справедливо, когда изменения влияют только на увеличение или уменьшение значений поддержки и достоверности для правил, но не на их действительность в целом. Алгоритм поиска будет выполняться снова и снова, не давая полезных новых результатов.

Рассматривая влияние изменений на первоначальный набор действительных правил, можно определить новые действительные ассоциативные правила XML после ряда изменений без повторного применения полного алгоритма поиска ассоциативных правил к окончательной версии. На рисунке 8 показан динамический XML-документ, используемый для этого примера. Он содержит каталог интернет-магазина за четыре дня. Каталог каждый день разный, так как он отражает деятельность продавцов и покупателей на сайте (добавляются или удаляются товары, меняются цены, обновляются описания и т.д.). (См. текстовую версию рисунка 8.)

Рисунок 8. Динамический XML-документ четырех последовательных версий
Пример динамического XML-документа четырех последовательных версий

Цель этого примера заключается в том, чтобы показать шаги по поиску динамических ассоциативных правил XML – а не то, как были найдены первоначальные правила XML (до внесения изменений). Первоначальные правила можно найти, используя любой известный алгоритм поиска ассоциативных правил XML.

Шаг 1: Подготовка

Для данного примера предположим, что этот шаг был выполнен в момент времени T0:

  • минимальная поддержка и достоверность, принятые для правил, установлены как min_sup = 22%, min_conf = 30%, prov_sup = 18% и prov_ conf = 20%;
  • были обнаружены следующие два ассоциативных правила XML:
    • Re = "когда в продаже есть аудиоплеер, в продаже есть также мобильный телефон" с поддержкой (Re) = 25% и достоверностью (Re) = 33%;
    • Rp = "когда в продаже есть набор инструментов для барбекю, в продаже есть также чемодан" с поддержкой (Rp) = 20% и достоверностью (Rp) = 25%.
  • Предположим, что общее число транзакций, проанализированных для получения вышеуказанных правил, составило 20.

Из этих результатов видно, что:

  • Re - это действительное правило, потому что min_sup < поддержки (Re) и min_conf < достоверности (Re);
  • Rp - это условное правило, потому что prov_sup < поддержки (Rp) < min_sup и prov_conf < достоверности (Rp) < min_conf.

Нужно проверить действительность правил Re и Rp по истечении четырехдневного периода, за который каталог товаров сайта изменился, как показано на рисунке 8.

Шаг 2: Поиск ассоциативных правил на основе версий

Следующая задача состоит в том, чтобы построить сводный дельта-документ для catalogue.xml и извлечь наборы изменений C1 (между T0 и T1), C2 (между T1 и T2) и C3 (между T2 и T3). На рисунке 9 показан сводный дельта-документ для четырех версий документа, представленного на рисунке 8. (См. текстовую версию рисунка 9.) Более подробную информацию о построении сводных дельта-документов см. в разделе Ресурсы.

Рисунок 9. Сводный дельта-документ для версий XML-документа, показанного на рисунке 8
Сводный дельта-документ для версий XML-документа, показанного на рисунке 8

В таблице 1 приведены изменения документа, содержащиеся в сводном дельта-документе. Обратите внимание на изменения значения Product при удалении или добавлении товаров.

Таблица 1. Изменения динамического XML-документа из примера
Набор измененийПериодичность выхода версийСодержание изменений
C1С T0 на T1Цена - изменилась
Товар "mobile phone" - исключен
Цена - удалена
C2С T1 на T2Товар "suitcase" - добавлен
Цена - изменилась
Статус - изменен
C3С T2 на T3Название - изменилось
Товар "mobile phone" - исключен
Цена - изменилась
Товар "bbq set" - добавлен

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

На шаге 1 предполагалось, что общее число транзакций (D), найденных до внесения изменений для получения Re и Rp, составило 20. Набор изменений C1, C2 и C3 содержит четыре транзакции. Новое общее число транзакций после изменений (D') составляет 20 + 4 = 24.

Новые значения поддержки и достоверности для действительного правила Re рассчитывается с помощью действий, показанных на рисунке 10. (См. текстовую версию рисунка 10.)

Рисунок 10. Вычисление новых значений поддержки и достоверности для действительного ассоциативного правила
Вычисление новых значений поддержки и достоверности для действительного ассоциативного правила

Новые значения поддержки и достоверности для условного правила Rp рассчитывается с помощью действий, показанных на рисунке 11. (См. текстовую версию рисунка 11.)

Рисунок 11. Вычисление новых значений поддержки и достоверности для условного ассоциативного правила
Вычисление новых значений поддержки и достоверности для условного ассоциативного правила

Как показано в результатах на рисунке 10 и рисунке 11, правило Re больше не действительно, потому что его новая поддержка (12,5%) ниже заданного минимального уровня поддержки и даже ниже условного уровня. Тот же результат можно наблюдать для правила Rp, которое раньше было условным, а теперь его уровень поддержки (16,66%) опустился ниже уровня условной поддержки. Однако уровень достоверности правила Rp (23,5%) выше условного уровня.


Заключение

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

В этой статье рассматривается несколько концепций, используемых в интеллектуальном анализе XML-данных для обнаружения ассоциативных правил в XML-документах. Мы привели примеры статических ассоциативных правил XML. Мы рассмотрели также пример динамических ассоциативных правил XML с многоверсионными XML-документами и разным количеством изменений от одной версии к другой.

В третьей статье этого цикла мы рассмотрим задачу кластеризации многоверсионных XML-документов.

Ресурсы

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=XML
ArticleID=822062
ArticleTitle=Интеллектуальный анализ XML-данных: Часть 2. Поиск ассоциативных правил в XML-данных
publish-date=06202012