はじめに

さまざまな分野で、データを表現、保管、交換するための言語として XML が選ばれる傾向が強くなってきています。XML で表現される情報の量が急増するなか、多くの人々が XML 文書の保管や分析に関する問題を解決するための実用的な手法を模索しています。そこで、この連載の「第 1 回 さまざまな XML データ・マイニング手法の調査」では、XML 文書に対して、そこに隠された知識をマイニングするための手法をいくつか紹介しました。

今回の記事では、XML 相関ルールを発見する手法を (リレーショナル・データから相関ルールを発見する手法と対比させて) 説明します。そのなかで、公開された後にコンテンツが変更される XML 文書から XML 相関ルールを抽出してその有効性を評価する手法を紹介します。また具体的な例を記載することで、リレーショナル・データから相関ルールを発見する方法と XML 文書から相関ルールを発見する方法との違い、さらには新しい XML データ・マイニング手法について理解する助けとなるようにします。

上に戻る

リレーショナル・データに対して相関ルールをマイニングする手法

第 1 回では、1993年に提起され、その翌年に Agrawal 氏と Srikant 氏によって詳細が確定された、相関ルールについて説明しました (「参考文献」を参照)。相関ルールは、リレーショナル・データを対象に、マーケット・バスケット分析で一連のトランザクションから抽出できる興味深い関係を見つけ出すために考え出されたものです。この種の情報を抽出するためのアルゴリズムは、Apriori アルゴリズムとして知られています。Apriori アルゴリズムでは、支持度 (support) および確信度 (confidence) という概念を以下のように使用します。

個別のアイテムのセットを I、トランザクションのセットをD とします。ここで、トランザクション・セット D を構成するトランザクション T には、I からのアイテムだけが含まれます。すると、相関ルール R は「X ⇒ Y」という形で表される関係になります。X と Y は、I に含まれる別個のアイテムです。相関ルール R のトランザクション・セット D での支持度 s は、「D のトランザクションの s% がアイテム X とアイテム Y の両方を含む」ことを意味し、確信度 c は、「アイテム X を含む D のトランザクションの c% がアイテム Y も含む」ことを意味します。

マーケット・バスケット分析での相関ルールの一例は、「製品 X を購入するユーザーが、製品 Y も購入するというパターンは、トランザクションの s% で発生し、その確信度は c% である」というものです。

リレーショナル・データにおけるトランザクションとアイテム

相関ルールの概念は当初、リレーショナル・データを対象に導入されました。リレーショナル・データのコンテキストでは、トランザクションはテーブル内のレコードであり、アイテムはテーブル内の属性の値です。したがって、トランザクションのセットは、同じ属性 (テーブルの列フィールド) を共有するレコードのセットで提供されます。

図 1 は、テーブル内のトランザクション・セットを視覚的に表した図です。ここでのタスクは、X と Y という 2 つのアイテム (属性) の値の間にある相関関係を相関ルールとしてマイニングすることです。この例のトランザクション・セットは、X と Y が順不同で含まれるいくつかのトランザクションと、X または Y のいずれか一方のみが含まれるトランザクションで構成されています。

上に戻る

XML 文書に対して相関ルールをマイニングする手法

XML 文書に対して相関ルールをマイニングする場合、リレーショナル・データに対してマイニングする場合とは勝手が違ってきます。XML フォーマットでは、リレーショナル・データとは異なる方法で情報を構造化できるためです。一般に、XML 相関ルールを発見するということは、1 つ以上の XML 文書のサブ構造の間にある関係を見つけることを意味します。

XML 相関ルールの場合のトランザクションとアイテム

静的 XML 相関ルールをマイニングする場合、現在は XML データに対応したトランザクションとアイテムの概念が採用されています。トランザクション・セットは、XML 文書に対して特定のパスを求めるクエリーを実行することで作られた複合ノードのリストとして提供されます。つまり、1 つの複合ノードが 1 つのトランザクションとなります。一方、アイテムはトランザクション・ノードの単なる子ノードです。

リレーショナル・データの場合、テーブルから抽出されるトランザクションには、常に一定の数のアイテムが含まれます。テーブル内に存在する属性すなわち列の数は変わらないためです。一方、XML トランザクションに含まれるアイテムの数は、文書内でのネストの深さ、そしてその文書が XML スキーマに従っているかどうかによって変わってきます。リレーショナル・データと同じような見方をすれば、XML 文書のルートからネストされているすべてのパスはレコードです。したがって、文書に含まれるすべてのノードの子は、同じ深さつまり同様のタグを持つ他のレコードと関連するレコードと見なされます (詳細については「参考文献」を参照)。

図 2 に示す例では、<staff_member> ノード (John Brown と Mellisa White) のそれぞれがトランザクション (transactions) であり、<publi_what>、<publi_where>、および<publi_when> の各ノードがアイテム (items) です。各 staff_member トランザクションには、スタッフ・メンバーの名前の下に 1 つ以上の出版物があり、出版物のそれぞれに publi_what、publi_where、および publi_when アイテムが含まれます。(図 2 の XML 文書をテキストで表現したバージョンを見るにはここをクリックしてください。)

XML 相関ルールのコンテキスト、条件部、および結論部

XML 相関ルールのコンテキストとは、実際にマイニングする XML 文書のセクションのことです。場合によっては、XML 文書に含まれるすべての情報をマイニングする必要はないこともあります。したがって、コンテキスト選択とは、ユーザーが XML トランザクションのセットに制約を定義できることを意味します。

図 3 に示すコンテキスト選択の一例では、2007年以降に研究出版物を出版したスタッフ・メンバーを表すトランザクション (点線で丸く囲ったトランザクション) のみがマイニング対象として選択されています。この例で 2007年以降に出版したのは Mellissa White のみです。

XML 相関ルールが X ⇒ Y の関係を意味する場合 (リレーショナル・データに対する手法と同様ですが、XML 文書の場合は 2 つの複合ノードの間の相関関係です)、X がルールの条件部を表し、Y がルールの結論部を表します。条件部と結論部は、常にルールのコンテキストに対して定義されます。同様に、ルールの支持度と確信度は、定義されたコンテキストに対してのみ計算されます。

例えば、図 3 のトランザクションのコンテキストが、2007年以降ではなく 2001年以降に研究出版物を出版したすべてのスタッフ・メンバーを対象とするように設定されていたとします。図 4 に、その場合の XML 相関ルールの条件部 (body) と結論部 (head) の一例を示します。このルールでは、<publi_what> (「Data mining book」という値が、ルールの条件部) と <publi_where> (「ABC publishing」という値が、ルールの結論部) との間の仮想的な関係を扱っています。

XML 相関ルールの例

図 5 に、ツリー形式で表現された XML 文書 (department.xml) の例を示します。この文書では、研究出版物を学生 (student) によるものとスタッフ・メンバー (staff) によるものとでグループ分けし、各グループには出版物 (publication) に関する詳細情報としてタイトル (publi_what)、出版社 (publi_where)、出版年 (publi_when) に関する詳細を含めています。ここでは XML 相関ルールをマイニングする一般的な概念を説明するために、<from_date> ノードと <to_date> ノードは空であるという想定にして、動的ではなく静的な XML 文書にしています。

以下の 2 つの XML 相関ルールでは、図 5 に示した文書を例に、トランザクション、アイテム、コンテキスト、条件部、結論部の概念を具体的に説明します。

XML 相関ルールの例 1

2006年以降に出版されたスタッフの研究出版物に関する情報から、相関ルールを発見したいとします。その場合に、以下のルールが得られたとします。

「2006年以降に XYZ ジャーナルに研究出版物を出版したスタッフ・メンバーは、ABC ドメインでのプロジェクトにも取り組んでいる。」

図 6 には、この例での以下の概念が表現されています。

• コンテキスト (context) は、<staff> のすべての複合ノードで指定されます。それは、学生による出版物ではなく、スタッフによる出版物をマイニングすることが要件となっていたためです。
• コンテキストの選択 (context selection) で指しているのは、<publi_when> の値が 2005 より大きい出版物レコードを選択することです。
• <staff> ノードは、それぞれが 1 つのトランザクションです。<staff> ノードは複合ノードであり、子ノードが含まれます。
• <staff> 複合ノードの子となっている、研究出版物 (publication) および研究プロジェクト (project) に関係する単純ノードは、いずれもアイテムです。つまり、以下のパスにあるノードがアイテムに該当します。
  • 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 パスにあるノードが、ルールの結論部 (head) を形成します。
• staff/project/domain パスにあるノードが、ルールの条件部 (body) を形成します。
  
  図 6. 例 1 における XML 相関ルールの概念
  
  
  

XML 相関ルールの例 2

今度は、学生とスタッフの研究出版物すべてに関する情報から相関ルールを発見したいとします。その場合に、以下のルールが得られたとします。

「ABC 出版社から出版した学生は、研究プロジェクトでスタッフとの共同研究も行っている。」

図 7 には、この例での以下の概念が示されています。

• コンテキスト (context) は、すべての <students> および <staff> の複合ノードで指定されます。これは、スタッフのみ、あるいは学生のみの出版物をマイニングするという要件がなかったためです。
• コンテキスト選択は定義されていないため、上記で定義されたコンテキストのすべてが考慮されます。
• <personal> を構成する複合ノードのそれぞれが、1 つのトランザクションです。
• <student> および <staff> の複合ノードの子となっている、研究出版物 (publication) およびプロジェクト (projcet) に関係する単純ノードはいずれもアイテムです。つまり、以下のパスにあるノードがアイテムに該当します。
  • 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 パスにあるノードが、ルールの結論部 (head) を形成します。
• staff/project/collab パスにあるノードが、ルールの条件部 (body) を形成します。
  
  図 7. 例 2 における XML 相関ルールの概念
  
  
  

例 1 と例 2 からわかるように、XML 文書に対して相関ルールをマイニングする場合のトランザクションおよびアイテムの概念には柔軟性があります。

図 5、図 6、および図 7 に示した文書の例は静的であると考えられ、<from_date> 要素と <to_date> 要素は無視されましたが、この 2 つのノードが空ではなく、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 相関ルールを基に、数々の変更が行われた後に、これらのルールがどのように機能するのかを判断するとします。つまり、引き続き有効な初期ルール、無効になった初期ルール、あるいは変更後に出現した新しいルールを識別するという問題があるということです。

この問題に対処する 1 つの方法は、変更後の文書のバージョンで、相関ルールのマイニング・アルゴリズムを実行することです。けれども、このプラクティスが功を奏す場合はそれほど多くありません。例えば、バージョン間での変更が少ないか、あるいは重要な変更ではないために、初期の相関ルールに大きな影響を及ぼさなければ、このプラクティスでは新しい相関ルールを見つけることができません。また、変更によって相関ルールの支持度と確信度が増減する一方、相関ルール全体の有効性には影響がない場合も同じで、検出アルゴリズムを何度実行しても、有用な出力は得られないでしょう。

一連の変更が行われた最終的なバージョンで相関ルール検出アルゴリズムを完全に実行し直さなくても、初期バージョンの有効な相関ルールに変更が及ぼす影響を検討することによって、新しい有効な XML 相関ルールを明らかにすることができます。図 8 に、このセクションで取り上げる例で使用する動的 XML 文書を示します。この図に示されているのは、4 日間にわたるオンライン・ショップのカタログです。このオークション・サイトでの売り手と買い手のアクティビティー (製品の追加または回収、価格の変更、詳細の更新など) により、カタログは毎日変わっています。(図 8 をテキストで表現したバージョンを見るにはここをクリックしてください。)

この例の目的は、(変更前の) 初期 XML ルールをどのようにマイニングしたかを説明することではなく、動的 XML 相関ルールをマイニングする手順を説明することです。初期ルールをマイニングするには、これまでの研究による任意の XML 固有の相関ルール・アルゴリズムを使用することができます。

ステップ 1. 準備

このステップは、時刻 T0 に行われたことを前提とします。

• ルールで許容される最小の支持度および確信度は、それぞれ min_sup = 22%、min_conf = 30% に、暫定の支持度および確信度は、それぞれ prov_sup = 18%、prov_ conf = 20% に設定されています。
• 次の 2 つの XML 相関ルールが発見されました。
  • Re =「ウォークマンが販売されているときには、携帯電話も販売されている」。このルールの支持度 (Re) は 25%、確信度 (Re) は 33% です。
  • Rp =「バーベキュー用品セットが販売されているときには、スーツケースも販売されている」。このルールの支持度 (Rp) は 20%、確信度 (Rp) は 25% です。
• 上記のルールを得るために、マイニングの対象となったトランザクションの合計数は 20 であったとします。

以上の結果から、以下のことがわかります。

• min_sup < 支持度 (Re) であり、min_conf < 確信度 (Re) であることから、Re は有効なルールです。
• prov_sup < 支持度 (Rp) < min_sup であり、prov_conf < 確信度 (Rp) < min_conf であることから、Rp は暫定的なルールです。

Re および Rp ルールの有効性は、オークション・サイトのカタログが図 8 のように変更されていた 4 日間が過ぎた後に確認する必要があります。

ステップ 2. バージョン・ベースの相関ルールのマイニング

次のタスクは、catalogue.xml 文書の差分を統合した文書を作成し、C1 (T0 から T1 までの変更)、C2 (T1 から T2 までの変更)、C3 (T2 から T3 までの変更) の変更セットを抽出することです。図 9 に、図 8 に示した文書の 4 つのバージョンの差分を統合した文書を示します (図 9 をテキストで表現したバージョンを見るにはここをクリックしてください)。統合された差分文書を作成する方法についての詳細は、「参考文献」を参照してください。

表 1 に、上記の統合された差分文書に含まれる文書の変更内容を記載します。製品が変更されたと見なすのは、製品が削除または追加されたときであることに注意してください。

簡潔にするために、この例ではバージョンを 4 つに絞っていますが、当然、上記の手順で統合された差分文書は、これよりも多くのバージョンがある場合により有効に働きます。

ステップ 1 では、変更前に Re および Rp を得るためにマイニングの対象としたトランザクションの合計数 (D) は 20 であるという前提にしました。変更セット C1、C2、および C3 には、4 つのトランザクションがあります。したがって、変更後にマイニングの対象とするトラザクションの新たな合計数 (D') は、20 + 4 = 24 です。

有効なルール Re の新しい支持度と確信度は、図 10 のステップに従って計算します。(図 10 をテキストで表現したバージョンを見るにはここをクリックしてください。)

暫定的なルール Rp の新しい支持度と確信度の値は、図 11 のステップに従って計算します。(図 11 をテキストで表現したバージョンを見るにはここをクリックしてください。)

図 10 と図 11 の結果に示されているように、ルール Re の新しい支持度 (12.5%) は必須の最小支持度だけでなく、暫定支持度レベルも下回っているため、このルールの有効性は失われています。同じことは、ルール Rp にも認められます。これは、以前は暫定的なルールでしたが、新しい支持度 (16.66%) は暫定支持度レベルに達していません。ただし、ルール Rp の確信度レベル (23.5%) は、暫定確信度レベルを上回っています。

上に戻る

まとめ

この記事で取り上げた例は小規模なものであり、実際のマイニング・アプリケーションに考えられるすべてのシナリオを網羅してはいません。けれども、マイニングの対象とした XML 文書が変更された後に、この例で提案したフレームワークを適用してバージョン・ベースの相関ルールを判断する方法は明らかにしました。

今回の記事では、XML 文書から相関ルールを発見するために、XML データ・マイニングで使用されるいくつかの概念について学びました。そして静的 XML 相関ルールの例を検討した後、動的 XML 相関ルールの例もひと通り説明しました。動的 XML 相関ルールの場合、XML 文書には複数のバージョンがあり、あるバージョンから次のバージョンに更新される際の変更の数は変動します。

この連載の第 3 回では、複数バージョンの XML 文書のクラスタリングについて詳しく探ります。お楽しみに。

参考文献

学ぶために

• 「第 1 回 さまざまな XML データ・マイニング手法の調査」: この連載の第 1 回では入門編として、XML 文書に隠された知識をマイニングする技術と手法を紹介しています。データ・マイニング、情報の階層構造、そして要素の相関関係について学んでください。
  
  
• 「Extracting Variable Knowledge from Multiversioned XML Documents」(L.I. Rusu、W. Rahayu、D. Taniar 共著、2006年): 初期 XML 文書から発見した情報が、文書のコンテンツや構造が変更されると、どのように変更されるのかを判断する革新的手法について読んでください。
  
  
• 「Mining Changes from Versions of Dynamic XML Documents」(L.I. Rusu、W. Rahayu、D. Taniar 共著、2006年): 統合された差分に含まれる情報を使用して、動的 XML 文書のバージョン間で変更された部分から相関ルールをマイニングする単純な手法について学んでください。
  
  
• 「Mining association rules between sets of items in large databases」(R. Agrawal、T. Imielinski、A.N. Swami 共著、1993年): 大規模データベースに保管されたアイテム間の相関ルールとして顕著なものをすべて生成する効率的なアルゴリズムについて読んでください。
  
  
• 「Deriving General Association Rules from XML Data」(Q. Ding、K. Ricords、J. Lumpkin 共著、2003年): XML データから一般的な相関ルールを抽出するという問題に対処する方法、そしてこのタスクを行うために提案されている手法を学んでください。
  
  
• New to XML: XML を学ぶために必要なリソースを入手してください。
  
  
• developerWorks の XML エリア: DTD、スキーマ、XSLT を含め、XML 分野でのスキルを磨くための資料を見つけてください。広範な技術に関する記事とヒント、チュートリアル、標準、そして IBM Redbooks については、XML ライブラリーを参照してください。
  
  
• IBM XML 認定: XML や関連技術の IBM 認定技術者になる方法について調べてください。
  
  
• developerWorks の Technical events and webcasts: これらのセッションで最新情報を入手してください。
  
  
• Twitter での developerWorks: 今すぐ登録して developerWorks のツイートをフォローしてください。
  
  
• developerWorks podcasts: ソフトウェア開発者向けの興味深いインタビューとディスカッションを聞いてください。
  
  
• developerWorks オンデマンド・デモ: 初心者向けの製品のインストールおよびセットアップから熟練開発者向けの高度な機能に至るまで、さまざまに揃ったデモを見てください。
  
  

製品や技術を入手するために

• IBM 製品の評価版: DB2、Lotus、Rational、Tivoli、および WebSphere のアプリケーション開発ツールとミドルウェア製品を体験するには、評価版をダウンロードするか、IBM SOA Sandbox のオンライン試用版を試してみてください。
  
  

議論するために

• developerWorks プロフィール: 今すぐ developerWorks で自分のプロフィールを作って、ウォッチ・リストをセットアップしてください。
  
  
• XML ゾーンのディスカッション・フォーラム: XML 関連のフォーラムに参加してください。
  
  
• developerWorks コミュニティー: ここでは他の developerWorks ユーザーとのつながりを持てる他、開発者が主導するブログ、フォーラム、グループ、ウィキを調べることができます。
  
  

著者について

Laura Rusu は、オーストラリア・メルボルンの La Trobe 大学で 2009年、コンピューター・サイエンスの博士課程を修了しました。博士論文の主題は、XML データのウェアハウジングおよびマイニングです。彼女が提案した XML データ・ウェアハウジングおよびマイニングの革新的手法の数々は、いくつもの国際会議で紹介され、国際的な学術専門誌にも詳細な文書が掲載されています。共著書には『Mining association Rules from XML Documents』があり、データ・マイニングおよびウェアハウジング技術に関する本の編集も行っています。彼女は学会、研究分野、そして IT 業界で経験を積んでいます。

この記事を評価する

コメント

上に戻る

目次

• はじめに
• リレーショナル・データに対して相関ルールをマイニングする手法
• XML 文書に対して相関ルールをマイニングする手法
• 動的 XML 相関ルール
• まとめ
• 参考文献
• 著者について
• コメント