Интеллектуальный анализ XML-данных: Часть 3. Кластеризация XML-документов для повышения качества интеллектуального анализа данных

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

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

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

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



21.06.2012

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

Исходные идеи

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

Методы кластеризации

В области кластеризации метрических или пространственных данных проделана большая работа и предложены несколько типов алгоритмов. Вот некоторые из них:

  • алгоритмы сегментации;
  • иерархические алгоритмы;
    • однозвенная кластеризация (или метод минимального расстояния);
    • полнозвенная кластеризация (или метод максимального расстояния);
    • среднезвенная кластеризация;
  • алгоритмы на основе плотности.

Подробнее об этих методах см. в разделе Ресурсы.

Кластеризация XML-документа отличается от кластеризации наборов данных любого другого типа ввиду иерархической структуры XML. Было предложено несколько подходов к кластеризации XML данных, таких как кластеризация XML-документов по структуре, семантическая XML-кластеризация, кластеризация бессхемных XML-документов и кластеризация связанных XML-документов. Подробнее различные типы XML-кластеризации рассматриваются в части 1 настоящего цикла статей. Эта статья посвящена структурной кластеризации XML-документов с использованием метода иерархической XML-кластеризации (на основе расстояния).

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

Для иллюстрации идеи схожести XML-документов на рисунке 1 изображены три XML-документа, два из которых весьма подобны (документы DA и DВ), тогда как документ DC не подобен ни DA, ни DB. Документы DA и DВ) содержат сведения о двух студентах, включая год обучения, предметы и сданные экзамены, а также имена этих студентов. Документ DC содержит сведения о книге, включая название, номер ISB и имена двух авторов.

Рисунок 1. Пример подобных и разнородных XML-документов
Пример подобных и разнородных XML-документов

Из рисунка 1 видно, что любые запросы, касающиеся сведений о студентах, применимы только к соответствующим документам (то есть DA и DВ), но не к другим документам, содержащим сведения другого рода, таким как DC. Интуитивно понятно, что документы DA и DB группируются в кластер, в то время как DC образует отдельный кластер.

Расстояние между XML-документами и XMLDelta

Если представить два XML-документа – D1 и D2 – в виде двух деревьев, то расстояние между этими двумя документами, обозначаемое как d(D1, D2 ), определяется набором основных операций (insert, update, delete) с наименьшей общей стоимостью, который позволяет преобразовать один документ в другой.

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

d(DA --> DB)={update(Student, John, Mary), update(year, 2, 3), insert(Exams), insert (Subject, Drama), insert (Subject, Music)} and d(DB --> DA)={ update(Student, John, Mary), update(year, 2, 3), delete(Exams), delete(Subject), delete(Subject)}

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

d (DA --> D B) = d (DB --> DA) = 5

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

В случае динамических (или многоверсионных) XML-документов каждая новая версия документа, по сути, представляет собой новый XML-документ, полученный путем определенного редактирования предыдущей версии документа. Это редактирование обычно выполняется путем применения набора основных операций (insert, update и delete) к предыдущей версии XML-документа. Если рассмотреть эти операции в целом, то они образуют так называемый дельта-документ. Когда говорят о дельта-документе XML, имеется в виду разница между двумя последовательными версиями XML-документа. Стоимость дельта-документа - это общая стоимость всех операций, упомянутых выше и используемых в дельта-документе.


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

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

  • Вариант А. Традиционный метод, вариант А, довольно прост. При изменении одного или нескольких документов определяются новые расстояния между всеми XML-документами путем сравнение каждой пары XML-документов в наборе. Очевидно, что этот вариант может оказаться слишком дорогостоящим, потому что он не учитывает объем изменений в документах. Если версия XML-документа лишь немного отличается или совсем не отличаются от предыдущей версии, то при сравнении будут затрачены излишние и ненужные усилия.
  • Вариант В. Это вариант, который подробно описан в настоящей статье. В нем используются расстояния, рассчитанные ранее для каждой пары XML-документов (то есть расстояния между документами до внесения изменений), плюс набор изменений, которые произошли за определенный период времени. На рисунке 2 приведено краткое описание шагов, выполняемых при подходе В.
    Рисунок 2. Краткое описание шагов по переоценке расстояния между динамическими XML-документами на основе изменений
    Краткое описание шагов по переоценке расстояния между динамическими XML-документами на основе изменений

Методологию, используемую для варианта B в соответствии с рисунком 2, можно разделить на две основные части:

  • Часть 1: первоначальный расчет расстояний. Обратите внимание, что это одноразовый, не повторяющийся этап.
    1. Определение и сохранение расстояний между каждой парой XML-документов.
    2. Расчет и сохранение минимальной стоимости преобразования каждой пары документов в обоих направлениях – туда и обратно.
  • Часть 2: Переоценка расстояний. Этот этап можно запланировать на регулярное выполнение после внесения изменений или запускать его, когда нужно узнать последнее значение расстояния между документами.
    1. Извлечение матрицы расстояний, рассчитанных ранее в ходе части 1 процесса или при последнем выполнении части 2.
    2. Получение набора изменений между метками времени последних известных расстояний и текущей меткой времени.
    3. Пересчет каждого расстояния, содержащегося в уравнении для предыдущего или первоначального расстояния, направления преобразования (вперед или назад) с минимальной стоимостью и набора изменений между документами.

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

  • изменяется только один документ из пары;
  • изменяются оба документа.

Для каждого сценария существуют дальнейшие соображения, связанные с типом операций, применяемых к документам; однако эти детали не рассматриваются в настоящей статье. См. раздел Ресурсы.


Пример

XML-документы, используемые в этом примере, представляют собой операции клиентов банка. Банк создает один XML-документ для каждого клиента, который открывает счет, а затем новую версию этого документа каждый раз, когда проводится новая операция. Каждая версия имеет дату операции, отраженную в элементе >_date<. Предположим, что по состоянию на 01 января 2008 года для трех клиентов существуют три документа (документы D1, D2 и D3). В листинге 1 показан документ D1.

Листинг 1. Пример XML-документа (D1) для случая динамической кластеризации
<?xml version="1.0" encoding="UTF-8"?> 
<customer> 
    <name>cust1</name> 
    <street>street1</street> 
    <city>;city1</city> 
    <transaction> 
        <trans_date>01/01/2008</trans_date> 
        <deposit> 
            <bank_account>BA1</bank_account>>
            <BSB>BSB1</BSB>
            <acc_name>ACC1</acc_name>
            <amount>100</amount>
        </deposit> 
    </transaction> 
</customer>

Затем, 15 января 2008 года, была выполнена еще одна операция для второго и третьего клиентов. В результате у документов D2 и D3 появились новые версии - D*2 и D*3 соответственно (см. листинг 2).

Листинг 2. Пример двух последовательных версий XML-документа (D2)
<?xml version="1.0" encoding="UTF-8"?> 
<customer> 
    <name>cust2</name> 
    <street>street2</street> 
    <city>city2</city> 
    <transaction> 
        <trans_date>01/01/2008</trans_date> 
        <deposit 
            ><bank_account>BA2</bank_account> 
            <BSB>BSB2</BSB> 
            <acc_name>ACC2</acc_name> 
            <amount>200</amount> 
            <balance>1000</balance> 
        </deposit> 
    </transaction> 
</customer> 
******************************************************************************* 
<?xml version="1.0" encoding="UTF-8"?> 
<customer> 
    <name>cust2</name> 
    <street>street2</street> 
    <city>city2</city> 
    <transaction> 
        <trans_date>15/01/2008</trans_date> 
        <withdrawal> 
            <bank_account>BA2</bank_account> 
            <BSB>BSB2</BSB> 
            <acc_name>ACC2</acc_name> 
            <amount>400</amount> 
            <balance>800</balance> 
        </withdrawal> 
    </transaction> 
</customer>

В листинге 3 показан третий документ до и после изменений (D3 и D*3).

Листинг 3. Пример двух последовательных версий XML-документа (D3)
<?xml version="1.0" encoding="UTF-8"?> 
<customer> 
    <name>cust3</name> 
    <street>street3</street> 
    <city>city3</city> 
    <transaction> 
        <trans_date>01/01/2008</trans_date> 
        <withdrawal> 
            <bank_account>BA3</bank_account> 
            <BSB>BSB3</BSB> 
            <acc_name>ACC3<acc_name> 
            <amount>50</amount> 
        </withdrawal>
    </transaction> 
</customer>
******************************************************************************* 
<?xml version="1.0" encoding="UTF-8"?> 
<customer> 
    <name>cust3</name> 
    <street>street3</street> 
    <city>city3</city> 
    <transaction> 
        <trans_date>15/01/2008</trans_date> 
        <withdrawal> 
            <bank_account>BA3</bank_account> 
            <BSB>BSB3</BSB> 
            <acc_name>ACC3</acc_name> 
            <amount>50</amount> 
            <balance>500</balance>
        </withdrawal> 
    </transaction>
</customer>

Цель этого примера - показать, как первоначальные кластеры, существовавшие на 01 января 2008 года, изменились после проведения новых операций 15 января 2008 года.

Часть 1: первоначальный расчет расстояний.

Как уже отмечалось, на этом этапе вычисляется расстояние между документами до внесения изменений для определения первоначального состава кластеров. Для целей данного примера предположим, что стоимость каждой из основных операций равна 1.

В таблице 1, таблице 2 и таблице 3 показаны необходимые операции и расстояния (общая стоимость операций) для каждой пары документов из приведенного примера.

Таблица 1. Первоначальное расстояние для пары XML-документов D1 и D2
d (D1 --> D2)
Update (<name>, 'cust1', 'cust2')
Update (<street>, 'street1', 'street2')
Update (<city>, 'city1', 'city2')
Update (<bank_account>, 'BA1', 'BA2')
Update (<BSB>, 'BSB1', 'BSB2')
Update (<acc_name>, 'ACC1', 'ACC2')
Update (<amount>, '100', '200')
Insert (<balance>, '1000')
d (D1 --> D2) = 8

Для наглядности в таблице 1, таблице 2 и таблице 3 уникальные идентификаторы каждого узла опущены, и перечислены только операции с соответствующими значениями.

Таблица 2. Первоначальное расстояние для пары XML-документов D1 и D3
d (D1 --> D3)
Update (<name>, 'cust1', 'cust3')
Update (<street>, 'street1', 'street3')
Update (<city>, 'city1', 'city3')
Delete (<deposit>)
Delete (<bank_account>, 'BA1')
Delete (<BSB>, 'BSB1')
Delete (<acc_name>, 'ACC1)
Delete (<amount>, '100')
Insert (<withdrawal>)
Insert (<bank_account>, 'BA3')
Insert (<BSB>, 'BSB3')
Insert (<acc_name>, 'ACC3')
Insert (<amount>, '50')
d (D1 --> D3) = 13

Как видите, наименьшим является исходное расстояние между D1 и D2.

Таблица 3. Первоначальное расстояние для пары XML-документов D2 и D3
d (D2 --> D3)
Update (<name>, 'cust2', 'cust3')
Update (<street>, 'street2', 'street3')
Update (<city>, 'city2', 'city3')
Delete (<deposit>)
Delete (<bank_account>, 'BA2')
Delete (<BSB>, 'BSB2')
Delete (<acc_name>, 'ACC2')
Delete (<amount>, '200')
Delete (<balance>, '1000')
Insert (<withdrawal>)
Insert (<bank_account>, 'BA3')
Insert (<BSB>, 'BSB3')
Insert (<acc_name>, 'ACC3')
Insert (<amount>, '50')
d (D2 --> D3) = 14

Основываясь на простом методе иерархической кластеризации, документы D1 и D2 можно сгруппировать в кластер (CВС1, где ВС означает before changes [до изменений]), в то время как D3 образует отдельный кластер – СВС2.

На рисунке 3 показано расположение кластеров в конце этапа 1. Пунктирные линии показывают, что документы D2 и D 3 имеют новые версии, и нужно определить новые кластеры после внесения изменений. Это делается на следующем этапе метода.

Рисунок 3. Первоначальный состав кластеров для приведенного примера
Первоначальный состав кластеров для приведенного примера

Часть 2: Переоценка расстояний

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

Во-первых, нужно получить набор изменений (дельта-документов) между версиями документов. В данном случае это Δ(D2 -->D*2) и Δ(D3 -->D*3). Затем эти дельта-документы используются для определения новых расстояний между измененными XML-документами.

В таблице 4 показан набор операций для Δ(D2 -->D*2).

Таблица 4. Операции, включенные в дельта-документы для XML-документа D2
Δ(D2 --> D*2)
Update (<trans_date>, '01/01/2008', '15/01/2008')
Delete <deposit>)
Delete (<bank_account>, 'BA2')
Delete (<BSB>, 'BSB2')
Delete (<acc_name>, 'ACC2')
Delete (<amount>, '200')
Delete (<balance>, '1000')
Insert (<withdrawal>)
Insert (<bank_account>, 'BA2')
Insert (<BSB>, 'BSB2')
Insert (<acc_name>, 'ACC2')
Insert (<amount>, '400')
Insert (<balance>, '800')

В таблице 5 показан набор операций для Δ(D3 -->D*3).

Таблица 5. Операции, включенные в дельта-документы для XML-документа D3
Δ(D3 --> D*3)
Update (<trans_date>, '01/01/2008', '15/01/2008')
Insert (<balance>, '500')

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

  • d'(D1 --> D*2), с использованием d(D1 --> D2) и Δ(D2 --> D*2)
  • d'(D1 --> D*3) с использованием d(D1 --> D3) и Δ(D3 --> D*3)
  • d'(D*2 --> D*3) с использованием d(D2 --> D3), Δ(D2--> D*2) и Δ(D3 --> D*3)

При переоценке этих расстояний некоторые операции могут быть совместными (matched), а другие заменяющими (replacement) – например, операция Update (<amount>, '100', '200')совместна с Delete (<amount>, '200'), и в этом случае заменяющей будет операция Delete (<amount>, '100'). Другими словами, результат применения обеих совместных операций к XML-документу тот же, что и результат применения заменяющей операции к первоначальному XML-документу. Подробнее об определении совместных и заменяющих операций см. в разделе Ресурсы.

На рисунке 4 приведено визуальное представление окончательного расчета стоимости для d'(D1 -->D*2).

Рисунок 4. Визуальное представление процесса вычисления нового расстояния d' (D1-->D*2) после внесения изменений.
Визуальное представление процесса вычисления нового расстояния после внесения изменений

В данном случае 11 операций не удается совместить с другими операциями, поэтому они учитываются со своей стоимостью, восемь операций заменены четырьмя дополнительными операциями и две операции перешли одна в другую. Следовательно, сумма стоимости всех операций, приводящих к новому расстоянию, равна 11 + 4 + 0 = 15 . Таким образом, новое расстояние составляет d'(D1 -->D*2) = 15.

С помощью аналогичной логики вычисляется расстояние d'(D1 -->D*3). На рисунке 5 показаны участвующие операции.

Рисунок 5. Визуальное представление процесса вычисления нового расстояния d' (D1-->D*3) после внесения изменений
Визуальное представление процесса вычисления нового расстояния d'(D1 -->D*3) после внесения изменений

Последний шаг по переоценке расстояния заключается в расчете d'(D*2 --> D*3). На рисунке 6 показаны участвующие операции.

Рисунок 6. Визуальное представление процесса вычисления нового расстояния d'(D*2 --> D*3) после внесения изменений
Визуальное представление процесса вычисления нового расстояния d'(D*2 -->D*3) после внесения изменений

Исходя из полученных результатов, на рисунке 7 показан новый состав кластеров после внесения изменений. Обратите внимание, что кластеры изменились, и теперь документы D2 и D3 в их новых версиях образуют кластер, тогда как документ D1 (который не изменился), образует отдельный кластер.

Рисунок 7. Состав кластеров после внесения изменений
Состав кластеров после внесения изменений

Заключение

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

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

Ресурсы

  • Оригинал статьи
  • Часть 1. Несколько подходов к интеллектуальному анализу XML-данных: в первой статье этого цикла содержится введение в добычу скрытых знаний из XML-документов. Она знакомит читателей с интеллектуальным анализом данных, иерархической структурой информации и связями между элементами.
  • Часть 2. Поиск ассоциативных правил в XML-данных: углубление в интеллектуальный анализ XML-данных, один из аспектов общего анализа XML-данных. Об ассоциативных правилах в статических и динамических XML-документах и о способах создания ассоциативных правил на основе версий, когда анализируемые XML-документы меняются.
  • Intelligent Dynamic XML Documents Clustering [L.I. Rusu, W. Rahayu, and D. Taniar, published in Proceedings of the 22nd International Conference on Advanced Information Networking and Applications (AINA 2008), IEEE Computer Society, Okinawa, Japan]: об эффективном способе избежать избыточных вычислений при переоценке попарных расстояний между кластеризованными динамическими XML-документами, изменяющимися во времени.
  • Storage Techniques for Multi-versioned XML Documents [L.I. Rusu, W. Rahayu, and D. Taniar, published in Proceedings of the 13th International Conference on Database Systems for Advanced Applications (DASFAA 2008), New Delhi, India]: четыре способа хранения динамических XML-документов.
  • Partitioning Methods for Multi-version XML Data Warehouses [L.I. Rusu, W. Rahayu, and D. Taniar, published in Distributed and Parallel Databases, 25(1-2), Springer, April 2009]: как создать 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=822294
ArticleTitle=Интеллектуальный анализ XML-данных: Часть 3. Кластеризация XML-документов для повышения качества интеллектуального анализа данных
publish-date=06212012