目次


XML データ・マイニング

第 3 回 XML 文書のクラスタリングによるデータ・マイニングの改善

動的 XML 文書のクラスターに対する変更を評価することで、データ・マイニングを迅速に行う

Comments

コンテンツシリーズ

このコンテンツは全#シリーズのパート#です: XML データ・マイニング

このシリーズの続きに乞うご期待。

このコンテンツはシリーズの一部分です:XML データ・マイニング

このシリーズの続きに乞うご期待。

XML データ・マイニングに関する連載の第 3 回目となる今回の記事では、XML 文書のクラスタリングに関するいくつかの概念を説明し、公開された後にそのコンテンツまたは構造が変更される XML 文書をクラスタリングするための作業を紹介します。実際のアプリケーションでは、XML 文書のバージョン間で行われる変更の数を予測することはできません。変更が行われた後に、最初のクラスタリング・ソリューションが使用できなくなる可能性は常に存在します。XML 文書に伴うこの陳腐化に対処するため、今回の記事では変更後に新しい XML 文書のクラスターを効率的に再計算する方法を説明します。この方法を理解して実際に適用できるように、記事ではステップバイステップで事例を説明します。

基本となる概念

クラスタリングとはデータ・マイニング・タスクの 1 つであり、(通常は距離の測定値を使用して) データ・セット内で高密度の領域を探すタスクのことです。別の言葉で表現すると、クラスタリングとは、類似したデータ・アイテムがクラスターと呼ばれるセットにグループ分けされるように、データを区分けするプロセスであると言えます。

XML 文書のクラスタリングは、他のどのタイプのデータ・セットのクラスタリングとも異なります。その理由は、XML の階層構造にあります。これまで、XML ならではのクラスタリング手法として、構造面に基づく XML 文書のクラスタリング、セマンティックな面に基づく XML 文書のクラスタリング、スキーマレスな XML 文書のクラスタリング、リンクされた XML 文書のクラスタリングなどが提案されています。さまざまなタイプの XML クラスタリングについて、詳しくは連載の第 1 回を読んでください。この記事では、階層的 (距離に基づく) XML クラスタリング手法を用いた、構造面による XML のクラスタリングに焦点を当てます。

距離に基づくクラスタリング手法では、まず、所定のセットから各オブジェクトが 1 つのクラスターに割り当てられます。次に、クラスターのペアの間での距離が計算され、最短距離にあるクラスター (最も類似したクラスター) がグループにまとめられて新しい (より大きな) クラスターを形成します。言い換えると、2 つの XML 文書のペアの類似度が、他の XML 文書とのペアの類似度よりも高い場合、この 2 つの文書間の距離は他よりも短いということになり、この 2 つを同じクラスターのメンバーにすることができます。

図 1 に、XML 文書の類似性の概念を例示する 3 つの XML 文書を示します。3 つの文書のうち、2 つの文書 (文書 DA と DB) はかなり類似していますが、文書 DC は DA と DB のどちらにも似ていません。文書 DA および DB には、2 人の生徒に関する情報として、学年 (Year)、科目 (Subjects)、試験 (Exams)、生徒名 (Student) が記載されています。文書 DC が記載しているのは、本に関する情報 (タイトル (Title)、ISB 番号 (ISB)、2 人の著者の名前 (Authors)) です。

図 1. 似ている XML 文書と似ていない XML 文書の例
似ている XML 文書と似ていない XML 文書の例を示す図
似ている XML 文書と似ていない XML 文書の例を示す図

図 1 では、生徒の詳細に関するクエリーは、該当する文書 (つまり、文書 DA と DB) にのみ適用され、異なる種類の情報が含まれる他の文書 (DC) には適用されません。直観的に、文書 DA と DB は同じクラスターにグループ化される一方、文書 DC は単独で 1 つのクラスターとなります。

XML 文書間の距離と XMLDelta

それぞれ 2 つのツリーとして表される 2 つの XML 文書、D1 と D2 があるとします。この場合、この 2 つの文書間の距離 d(D1, D2) を決めるのは、最小の総コストを持つ上に、ある文書を別の文書に変換することができる基本操作のセット (挿入、更新、削除) です。

例えば、図 1 の文書 DA と文書 DB の間の距離を決定するには、まず DA を DB に (前方) 変換することができる基本操作のセットを見つけてから、次に DB を DA に (後方) 変換することができる基本操作のセットを見つけます。この 2 つの基本操作セットについて、それぞれのコストを計算した後、総コストが最小のセットを選択します。

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 --> DB) = d (DB --> DA) = 5

この例の場合、両方の基本操作セットの総コストは同じであるため、どちらのセットを選択するのでも構いません。

動的 XML 文書 (複数バージョンの XML 文書とも呼ばれます) の場合、文書の新しいバージョンは、実際には前の文書バージョンをある程度更新することによって得られた新規 XML 文書です。通常、この更新を行うには、XML 文書の前のバージョンに基本操作 (つまり、挿入、更新、および削除) の組み合わせを適用します。これらの操作を全体として見ると、差分の形になります。XML の差分を話題にするときには、これが XML 文書の 2 つの連続したバージョンの間での違いを意味していることはご存知でしょう。差分のコストは、差分の中に記載された上述の操作の組み合わせの総コストです。

動的 (複数バージョンの) XML 文書のクラスタリング

動的 XML 文書をクラスタリングするときには、基本的に以下の 2 つの選択肢があります。

  • 選択肢 A。従来の手法である選択肢 A は、単純明快なものです。この選択肢では、1 つ以上の文書が変更されたときに、セットに含まれる XML 文書の各ペアを比較して、すべての XML 文書間の新しい距離を計算し直します。この選択肢は、文書に適用された変更のレベルについてはまったく区別しないことから、明らかにコストがかかります。したがって、XML 文書のバージョンが、前のバージョンと比べてわずかな違いしかない場合、あるいはまったく違いがない場合には、文書の比較には冗長で不要な作業を伴うことになります。
  • 選択肢 B。この選択肢については、この記事で詳細に説明します。この選択肢では、XML 文書の各ペアに関して前に計算された距離 (変更が行われる前の文書間の距離) に加え、一定の期間にわたって行われた一連の変更を使用します。図 2 に、選択肢 B で必要となるステップを要約します。
    図 2. 変更に基づいて、動的 XML 文書の間の距離を再評価するステップの要約
    変更に基づいて、動的 XML 文書の間の距離を再評価するステップの要約図
    変更に基づいて、動的 XML 文書の間の距離を再評価するステップの要約図

図 2 に示す選択肢 B で使用される方法は、主に以下の 2 つのフェーズに分けることができます。

  • 第 1 フェーズ: 初期の距離計算。このフェーズは 1 度だけ行われ、繰り返されることはありません。第 1 フェーズでは、以下のステップを行います。
    1. XML 文書のそれぞれのペアの間の距離を決定して保管します。
    2. 文書のペアを両方向 (前方および後方) に変換するための最小コストを計算し、保管します。
  • 第 2 フェーズ: 距離の再評価。このフェーズは、変更後に定期的に実行されるようにスケジューリングすることも、文書間の最新の距離を知る必要があるときに実行することもできます。このフェーズでは、以下のステップを行います。
    1. 第 1 フェーズで計算した距離、または第 2 フェーズの最新の実行結果から計算した距離のマトリクスを取得します。
    2. 最後に距離を評価したときのタイムスタンプから現在のタイムスタンプまでに行われた変更一式を取得します。
    3. 方程式に、前回または初期の距離、最小コストの変換方向 (前方または後方)、文書間の変更一式を組み込んで、各距離を再計算します。

上記から明らかなように、プロセスの第 2 フェーズで最も重要なのは、データ・セットに含まれる XML 文書のバージョンのペアごとに新しい距離を再計算するステップです。距離の再評価が必要な 2 つの XML 文書には例外なく、以下の 2 つの異なるシナリオが存在します。

  • 2 つの文書のうち、一方の文書だけが変更されている場合
  • 2 つの文書が両方とも変更されている場合

それぞれのシナリオでは、文書に適用する操作のタイプに関して詳細な検討が行われますが、この記事ではこれらの検討事項についての詳しい説明はしません。追加情報および詳細な説明については、「参考文献」を参照してください。

事例研究

この例で使用する XML 文書は、ある銀行での顧客取引を表すものです。この銀行は、口座を開設する顧客ごとに 1 つの XML 文書を作成し、新しい取引が入力されるたびに文書の新しいバージョンを作成します。各バージョンには、取引の日付が <trans_date> 要素によって示されます。ここで、2008年 1月 01日の時点で 3 人の顧客に関する 3 つの文書があるとします (文書 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>

その後、2008年 1月 15日に、2 番目の顧客と 3 番目の顧客のそれぞれに対して 1 つの追加取引が入力されたとします。その結果、文書 D2 と D3 には新しいバージョンとして、それぞれ D*2 と D*3 が作成されます (リスト 2 を参照)。

リスト 2. サンプル XML 文書 (D2) の連続した 2 つのバージョン
<?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 に、この事例研究で使用する 3 番目の文書の変更前と変更後 (D3 および D*3) を記載します。

リスト 3. サンプル XML 文書 (D3) の連続した 2 つのバージョン
<?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>

この事例研究の目的は、2008年 1月 01日の時点での初期クラスターが、2008年 1月 15日に顧客の新しい取引が入力された後に、どのように変更されるのかを明らかにすることです。

第 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 ではいずれも各ノードに追加される一意の ID を省略し、操作については、それぞれに対応する値を使用しています。

表 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 は 1 つのクラスター (C1BC: BC は変更前 (Before Changes) を表します) にグループ化し、D3 は別個のクラスター (C2BC) にすることができます。

図 3 に、第 1 フェーズが終了した時点でのクラスタリング構成を示します。破線は文書 D2 および D3 に新しいバージョンがあることを表すため、変更後に新しいクラスターを決定しなければなりません。したがって、この手法での次のフェーズが必要です。

図 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) を使用して計算します。

上記の距離を再評価する中で、いくつもの操作が対応したり、置換操作が見つかったりします。例えば、操作 Update (<amount>, '100', '200')Delete (<amount>, '200') と対応する場合、置換操作は Delete (<amount>, '100') となります。別の言葉に置き換えると、対応する両方の操作を XML 文書に適用した結果が、同じ初期の XML 文書に置換操作を適用した結果と同じになるということです。操作の対応や置換がどのように定義されているかについての詳細な情報は「参考文献」を参照してください。

図 4 に、d'(D1 -->D*2) の最終コストが算出されるまでの流れを視覚的に表現します。

図 4. 変更後の新しい距離 d' (D1 --> D*2) を計算するプロセスの視覚的表現
変更後の新しい距離 d' (D1 --> D*2) を計算するプロセスの視覚的表現
変更後の新しい距離 d' (D1 --> D*2) を計算するプロセスの視覚的表現

この例の場合、他の操作と対応させることができなかった操作は 11 ありました。そのため、これらの操作はそれぞれが持つコストでカウントされます。一方、8 つの操作は 4 つの補完操作で置き換えられ、2 つの操作は互いに入れ替わる結果となりました。したがって、この新しい距離に関わっているすべての操作の各コストを合計すると、11 + 4 + 0 = 15 となります。つまり、新しい距離 d'(D1 --> D*2) は 15 です。

距離 d'(D1 -->D*3) についても、同様のロジックで計算します。図 5 に、関連する操作を示します。

図 5. 変更後の新しい距離 d' (D1 --> D*3) を計算するプロセスの視覚的表現
変更後の新しい距離 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) を計算するプロセスの視覚的表現
変更後の新しい距離 d'(D*2 --> D*3) を計算するプロセスの視覚的表現

以上のステップによって得られた結果から、変更後の新しいクラスタリング構成は図 7 のようになります。クラスターが変更されていることに注目してください。今度は、新しいバージョンの D2 と D3 がクラスターを構成する一方、文書 D1 (これは、変更されていません) は単独で別個のクラスターを構成しています。

図 7. 変更後のクラスタリング構成
変更後のクラスタリング構成を示す図
変更後のクラスタリング構成を示す図

まとめ

今回の記事では、距離に基づく手法を使用して動的 XML 文書をクラスタリングする方法を説明しました。距離に基づく手法とは具体的には、初期文書が変更された後に、動的 XML 文書のバージョン間の距離を決定するための手法です。この手法は、XML 文書の変更後に距離を再計算してクラスターを再評価するために必要な操作の数を大幅に減らすことから、時間の点でも、コストの点でも効果的であることは明らかです。

この記事および事例研究では、意図的に XML 文書を単純にしてバージョンの数を少なく抑えましたが、これよりもバージョン数が多く、バージョン間での違いが多数ある複雑な文書の場合でも、同じステップに従ってください。


ダウンロード可能なリソース


関連トピック

  • XML データ・マイニング: 第 1 回 さまざまな XML データ・マイニング手法の調査」: この連載の第 1 回では入門編として、XML 文書に隠された知識をマイニングする技術と手法を紹介しています。データ・マイニング、情報の階層構造、そして要素の相関関係について学んでください。
  • XML データ・マイニング: 第 2 回 XML 相関ルールのマイニング」: この全 3 回からなる連載の第 2 回で、XML データ分析の一側面である XML データ・マイニングについて掘り下げ、静的 XML 相関ルールおよび動的 XML 相関ルールについて、さらにはマイニング対象の XML 文書が公開された後に変更される場合にバージョン・ベースの相関ルールを作成する方法について学んでください。
  • Intelligent Dynamic XML Documents Clustering」(L.I. Rusu、W. Rahayu、D. Taniar 共著、沖縄での 22nd International Conference on Advanced Information Networking and Applications (AINA 2008) の議事録に掲載、IEEE Computer Society): 公開された後に変更される、クラスタリングされた動的 XML 文書のペアの距離を再評価する際に、冗長な計算を回避するための効率的な方法を調べてください。
  • Storage Techniques for Multi-versioned XML Documents」(L.I. Rusu、W. Rahayu、D. Taniar 共著、インド・ニューデリーでの 13th International Conference on Database Systems for Advanced Applications (DASFAA 2008) の議事録に掲載): 動的 XML 文書の 4 つの保管方法を読んで、評価してください。
  • Partitioning Methods for Multi-version XML Data Warehouses」(L.I. Rusu、W. Rahayu、D. Taniar 共著、Distributed and Parallel Databases, 25(1-2) に掲載、Springer、2009年4月): 複数のパーティショニング手法を使用して XML データウェアハウスを構築する方法を学ぶとともに、XML データウェアハウスのさまざまなクエリー・タイプを評価してください。
  • developerWorks の XML エリア: DTD、スキーマ、XSLT を含め、XML 分野でのスキルを磨くための資料を見つけてください。広範な技術に関する記事とヒント、チュートリアル、標準、そして IBM Redbooks については、XML 技術文書一覧を参照してください。
  • IBM XML 認定: XML や関連技術の IBM 認定技術者になる方法について調べてください。
  • Twitter での developerWorks: 今すぐ登録して developerWorks のツイートをフォローしてください。
  • developerWorks podcasts: ソフトウェア開発者向けの興味深いインタビューとディスカッションを聞いてください。
  • IBM 製品の評価版: DB2、Lotus、Rational、Tivoli、および WebSphere のアプリケーション開発ツールとミドルウェア製品を体験するには、評価版をダウンロードするか、IBM SOA Sandbox のオンライン試用版を試してみてください。

コメント

コメントを登録するにはサインインあるいは登録してください。

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=XML
ArticleID=818623
ArticleTitle=XML データ・マイニング: 第 3 回 XML 文書のクラスタリングによるデータ・マイニングの改善
publish-date=05312012