Введение

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

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

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

В начало

Интеллектуальный анализ XML-данных

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

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

Основные различия между статическими и динамическими XML-документами:

Наличие срока действия

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

Постоянство отображаемой информации

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

На рисунке 1 показан пример схемы статического XML-документа в формате WSDL.

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

На рисунке 2 показан пример схемы динамического XML-документа в формате WSDL.

На рисунке 2 узел <AsAtDate> содержит срок действия данных каждой версии XML-документа. Вместо одного узла данных для указания времени действия можно использовать два узла для указания диапазона дат (например, <from_date> и <to_date>). Как правило, изменения в XML-документах делают их динамическими. Каждый набор изменений в оригинальной версии XML-документа приводит к созданию нового XML-документа. Новый XML-документ будет рассматриваться как новая версия оригинального документа.

В начало

Интеллектуальный анализ статических XML-документов

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

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

Большая часть работ по поиску ассоциативных правил в статических XML-документах связана с использованием XML-ориентированных алгоритмов, основанных на алгоритме Apriori. Однако существует и ряд других подходов.

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

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

• Один алгоритм извлечения ассоциативных правил из XML, предложенный авторами Wan и Dobbie (см. раздел Ресурсы), по сути, является реализацией алгоритма Apriori с использованием языка XQuery. С помощью этого алгоритма XML-данные можно анализировать непосредственно, без предварительной обработки XML-документа. Преобразование в другой формат не требуется. Однако с помощью реализации XQuery поиск значительных наборов элементов в процессе анализа ведется медленнее, чем при использовании реализации на основе C++. В XQuery-реализации возможности редактирования, необходимые для данного алгоритма, ограничены.
• Метод, предложенный Daniele Braga и коллегами (см. раздел Ресурсы), основан на алгоритме Apriori и ищет ассоциативные правила в три основных этапа: предварительная обработка данных, извлечения ассоциативных правил и пост-обработка ассоциативных правил. Авторы вводят следующие понятия:
  • контекст ассоциативного правила;
  • выбор контекста;
  • тело;
  • голова.
  В соотношении X -->Y X - это тело, a Y - голова ассоциативного правила. Тело и голова всегда определяются в контексте правила. Поддержка и достоверность рассчитываются и имеют смысл только в установленным контексте. На рисунке 3 показан пример XML-документа в виде дерева с выделенными контекстом, телом и головой.
  
  Рисунок 3. XML-документ с контекстом, телом и головой
  
  
  
• Метод, предложенный Ling Feng и коллегами (см. раздел Ресурсы), не базируется на алгоритме Apriori и предлагает различные концепции преобразования транзакций и элементов в древовидную структуру XML-документов. Цель заключается в том, чтобы обнаруживать ассоциативные правила не в одном документе, а в коллекции XML-документов. Таким образом, каждый XML-документ (дерево) соответствует записи в базе данных (транзакции), а каждый XML-фрагмент (поддерево) соответствует элементу транзакции. При этом подходе пытаются обнаружить ассоциативные правила не среди просто структурированных элементов, а среди деревьев XML-документов. Каждое дерево называется элементом структуры деревьев и представляет собой укорененное, упорядоченные дерево, узлы которого делятся на основные (без исходящих из них ребер) и сложные (внутренние узлы с одним или несколькими исходящими ребрами).

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

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

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

Кластеризация статических XML-документов

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

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

• Алгоритм S-GRACE (см. раздел Ресурсы) кластеризует XML-документы по структуре с помощью структурных графов (s-графов). S-граф ― это направленный граф, который содержит краткое описание узлов и ребер деревьев XML-документов, а также отношения между родительскими и дочерними узлами. S-GRACE применяет к s-графу, полученному из данного набора XML-документов, иерархический алгоритм кластеризации.
• Общий агломерационный иерархический алгоритм кластеризации, предложенный De Francesca и коллегами (см. раздел Ресурсы), решает задачу кластеризации XML-документов параметрическим способом. При наличии подходящей меры расстояния алгоритм находит оптимальных представителей кластеров. Представитель кластера - это XML-документ, который отражает структурное содержание кластера. Таким образом, задача сводится главным образом к вычислению представителя кластера путем сопоставления деревьев, слияния деревьев и обрезания объединенных деревьев.

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

• Yoon предложил подход (см. раздел Ресурсы), при котором каждый XML документ, который необходимо кластеризовать по ePaths, разбивается на части. ePaths — это полные пути, начиная с корня XML-документа, по которым наиболее глубоко вложенным элементом может быть только простой элемент (содержащий значение и не содержащий дочерних элементов).

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

• Метод, предложенный Shen и Wang (см. раздел Ресурсы), извлекает из XML-документов, которые могут быть основаны на XML-схеме или нет, макропути, причем каждый макропуть состоит из трех элементов: последовательности путей, последовательности атрибутов и последовательности содержаний. Степень подобия между этими макропутями соответствует степени подобия между анализируемыми XML-документами.

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

• Метод, предложенный Theodore Dalamagas и коллегами (см. раздел Ресурсы), рассматривает XML-документы как упорядоченные деревья. Их алгоритм сокращает уровень вложенности и повторяемости, а затем вычисляет расстояние редактирования дерева для каждой пары структурных описаний. Кластеризация основана на расстоянии между структурными описаниями.
• Метод Nierman и Jagadish (см. раздел Ресурсы) вычисляет расстояние между двумя XML-документами с помощью пяти операций над XML-деревом: relabel, insert, delete, insertTree и deleteTree. Две последние операции позволяют вырезать и вставлять целые разделы XML-документа. Можно также определить допустимые последовательности операций редактирования и использовать их в алгоритме динамического программирования для вычисления расстояния между парами XML-документов из заданного набора.
• Более поздний метод Xing, Xia и Guo (см. раздел Ресурсы) вычисляет подобие между двумя XML-документами, рассчитывая расстояние редактирования между двумя XML-документами и их схемой. Из каждого документа извлекается схема, и расстояние между двумя XML-документами рассчитывается как среднее расстояние между каждым XML-документом и схемой, извлеченной из другого XML-документа пары.

Таблица 2 содержит краткий обзор подходов к кластеризации статических XML-документов.

В начало

Анализ динамических XML-документов

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

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

Поиск ассоциативных правил в многоверсионных XML-документах все еще находится в зачаточном состоянии. Алгоритм Weighted-FPgrowth (см. раздел Ресурсы) направлен на решение этой проблемы. Он извлекает ассоциативные правила из разностей XML-структур, или XSD-AR, в три этапа.

1. Создание базы данных разностей структур.
2. Поиск часто встречающихся шаблонов поддеревьев.
3. Получение ассоциативных правил.

Разности XML-структур – это структурные различия между последовательными версиями динамического XML-документа. Алгоритм Weighted-FPgrowth также определяет концепции степени изменения, частоты изменений и шаблона часто встречающихся поддеревьев.

Я предлагаю два разных способа поиска ассоциативных правил в динамических XML-документах (см. раздел Ресурсы).

• Интересные знания (в данном случае ассоциативные правила) из набора исторических версий XML-документов.

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

• Ассоциативные правила, извлеченные из фактических изменений между версиями XML-документов.

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

Кластеризация динамических XML-документов

Работ по кластеризации динамических XML-документов не много. Ниже излагаются две возможности.

• Один из методов, предложенный мной и моими коллегами (см. раздел Ресурсы), ― это переоценка расстояния между кластеризованными динамическими XML-документами после их изменения и расчет влияния этих изменений на первоначальные расстояния.
• Другой метод, предложенный Nayak и Xu (см. раздел Ресурсы), - это последовательности кластеров XML-документов. Для данной последовательности, или потока, XML-документов рассчитывается расстояние между каждым входящим XML-документом и существующими кластерами с использованием структуры уровней. Это расстояние определяется путем сопоставления узлов входящего документа с узлами существующих кластеров. Таким образом, подобие для отдельных документов кластера определяется на уровне кластера, а не попарно.

В таблице 3 кратко излагаются подходы к анализу динамических XML-документов.

В начало

Заключение

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

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

Ресурсы

Научиться

• Оригинал статьи
  
  
• Часть 2. Поиск ассоциативных правил в XML-данных: углубление в интеллектуальный анализ XML-данных, один из аспектов общего анализа XML-данных. Об ассоциативных правилах в статических и динамических XML-документах и о способах создания ассоциативных правил на основе версий, когда анализируемые XML-документы меняются.
  
  
• Часть 3. Кластеризация XML-документов для повышения качества интеллектуального анализа данных: безызбыточная методология перерассчета новых кластеров XML-документов после их изменения. Метод и его применение иллюстрируются наглядным примером.
  
  
• Extracting Variable Knowledge from Multiversioned XML Documents (L.I. Rusu, W. Rahayu, and D. Taniar, 2006a): о новом методе определения того, как знания, выявленные в первоначальных XML-документах, меняются во времени при изменении содержания и/или структуры документов.
  
  
• Mining Changes from Versions of Dynamic XML Documents (L.I. Rusu, W. Rahayu, and D. Taniar, 2006b): о простом методе поиска ассоциативных правил по изменениям между версиями динамических XML-документов с использованием информации, содержащейся в сводном дельта-документе.
  
  
• Intelligent Dynamic XML Documents Clustering (L.I. Rusu, W. Rahayu, and D. Taniar, 2008): эффективный способ переоценки попарных расстояний между кластеризованными динамическими XML-документами, которые меняются во времени, без выполнения избыточных вычислений, но с учетом ранее известных расстояний и набора изменений, которые могли повлиять на версии документов.
  
  
• Data mining and XML documents (R. Nayak, R. Witt, and A. Tonev, 2002): о таксономии интеллектуального анализа XML-документов как ступени для дальнейших исследований в этой области.
  
  
• Fast Algorithms for Mining Association Rules (M.H. Marzahuy and A.A. Mitwaly, 2005): о проблеме выявления ассоциативных правил между элементами в большой базе данных торговых операций. Для решения этой задачи предлагаются два новых алгоритма, которые принципиально отличаются от известных.
  
  
• Mining Association Rules from XML data (D. Braga, A. Campi, M. Klemettinen, and P.L. Lanzi, 2002): обзор ассоциативных правил из XML-документов и обсуждение новых проблем и возможностей для сообщества специалистов по интеллектуальному анализу данных.
  
  
• Discovering Interesting Information in XML with Association Rules (D. Braga, A. Campi, and S. Ceri, 2003): введение в ассоциативные правила для XML-данных. Предлагается новый оператор на основе XPath и синтаксиса XQuery, который позволяет выразить сложные задачи интеллектуального анализа данных в компактной и интуитивно понятной форме.
  
  
• Mining Association Rules from Structural Deltas of Historical XML Documents (L. Chen, S.S. Bhowmick, and L.T. Chia, 2004): о последовательности изменений в структурах XML-документа, которая позволяет выяснить, какие поддеревья в XML-структуре часто изменяются вместе.
  
  
• Clustering XML Documents by Structure (T. Dalamagas, T. Cheng, K.J. Winkel, and T. Sellis, 2004): применение методов кластеризации к структурно подобным XML-документам.
  
  
• Distance-based Clustering of XML Documents (F. De Francesca, G. Gordano, R. Ortale, and A. Tagarelli, 2003): о новой методологии кластеризации XML-документов, сосредоточенной на понятии представителя XML-кластеры (прототипа XML-документа, в котором сосредоточены наиболее важные особенности набора XML-документов в пределах кластера).
  
  
• An XML–Enabled Association Rules Framework (L. Feng, T. Dillon, H. Wiegand, and E. Chang, 2003): расширенная среда ассоциативных правил с поддержкой XML, достаточно гибкая и мощная, чтобы представлять как просто, так и сложно структурированные ассоциативные отношения между XML-данными.
  
  
• An Efficient and Scalable Algorithm for Clustering XML Documents by Structure (W. Liang, D.W. Cheung, N. Mamoulis, and S-M Yiu, 2004): обзор иерархического алгоритма (S-GRACE) кластеризации XML-документов на основе структурной информации в данных.
  
  
• XCLS: A Fast and Effective Clustering Algorithm for Heterogeneous XML Documents (R. Nayak and S. Xu, 2006): о новом алгоритме кластеризации XML-документов по аналогичным структурам.
  
  
• Evaluating Structural Similarity in XML Documents (H. Nierman and V. Jagadish, 2002): о мере расстояния редактирования дерева, подходящей для этой задачи, принимая во внимание такие проблемы XML, как факультативные и вложенные элементы.
  
  
• Clustering Schemaless XML Documents (Y. Shen and B. Wang, 2003): о семантическом кластеризации бессхемных XML-документов, которых становится все больше.
  
  
• Clustering XML Documents Based on Structural Similarity (G. Xing, Z. Xia, and J. Guo, 2007): о среде кластеризации XML-документов на базе структурного подобия между XML-документами.
  
  
• Extracting Association Rules from XML documents using XQuery (J.W. Wan and G. Dobbie, 2003): как находить ассоциативные правила в любом XML-документе, используя только язык запросов XQuery, без всякой предварительной и последующей обработки.
  
  
• Mining association rules from XML data using XQuery (J.W. Wan and G. Dobbie, 2004): как извлекать ассоциативные правила из XML-документов с помощью XQuery без какой-либо предварительной или последующей обработки. О XQuery-реализации хорошо известного алгоритма Apriori.
  
  
• XQuery: о языке XML-запросов, рекомендованном W3C.
  
  
• BitCube: A Three-Dimensional Bitmap Indexing for XML Documents (J.P. Yoon, V. Raghavan, V. Chakilam, and L. Kerschberg, 2001): о том, как представлять и индексировать коллекцию XML-документов с помощью метода растровой индексации.
  
  
• Mining Association Rules from Structural Deltas of Historical XML Documents (L. Chen, S. S. Bhowmick, and L.T. Chia, 2004): поиск ассоциативных правил нового типа в последовательности изменений XML-структуры, т.н. дельта-ассоциативных правил XML-структуры (XML Structural Delta Association Rule - XSD-AR).
  
  
• Только знакомитесь с XML? Эти ресурсы необходимы для изучения XML.
  
  
• Раздел портала developerWorks, посвященный XML: ресурсы, необходимые для совершенствования навыков в области XML, включая DTD, схемы и XSLT. Библиотека литературы по XML: широкий спектр технических статей и советов, руководств, стандартов и документации IBM.
  
  
• Сертификация специалистов IBM по XML: как стать сертифицированным разработчиком IBM по XML и связанным с ним технологиям.
  
  
• developerWorks в Твиттере: присоединяйтесь и следите за твитами портала developerWorks.
  
  

Обсудить

• Профиль developerWorks: создайте свой профиль и настройте список наблюдения.
  
  

Об авторе

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

Оценить эту статью

Комментарии

В начало

Содержание

• Введение
• Интеллектуальный анализ XML-данных
• Интеллектуальный анализ статических XML-документов
• Анализ динамических XML-документов
• Заключение
• Ресурсы
• Об авторе
• Комментарии