複数データ領域間共通構造マイニングの提案

複数データ領域間共通構造マイニングの提案

Common Structure Mining over Multiple Data Domains

原口誠

∗1

Makoto HARAGUCHI

笹原 啓佑

∗1

Keisuke SASAHARA

∗1

_{北海道大学 情報科学研究科}

Graduate School of Information Science and Technology, Hokkaido University

In this report, we propose a method for finding common structural similarities over a given family of relational databases. The similarities among databases are represented as relational queries with their answers at least for a certain number of databases. Then, from the answers to the queries, we can observe that entities instantiated to the variables in queries share role similarities showing how they appear in relations of databases. We use this simple fact to construct cross-clusters over several databases. The clustering method we present here is designed for the clusters to involve entities to be matched in the structural similarities. Then, regarding the cluster names as variable in the target relational query, we enumerate possible connected sets of primitive patterns with the variables such that those patterns are realizable in a certain number of databases. The sets of primitive patterns thus obtained are the relational queries for common structural similarities over certain number of databases.

1.

はじめに

本稿では，複数個の関係データベース（以下ＤＢ）を与え， ＤＢ間で成り立つ部分的な構造類似性を，実体(entity)が持つ ロールに関する類似性（ロール類似性）に着目して求める方法 を提案する．具体的には，実体関連モデル(entity-relationship model)における実体間関係のインスタンスをイベントと捉え， ２つのイベントが実体を共有するとき，イベントを接続する エッジを張ったグラフを考える．すなわち，イベントを頂点と するグラフであり，以下イベントグラフと呼ぶ．また，ロール とは実体が関係スキーマのどの属性でＤＢにおいて現れるかを 示し，実体aが関係スキーマr(A1, ..., An)のインスタンスt に対し，t.Aj= aであるときaはrにおいてロールAj を担 うと本稿では言う．このように与えられた複数のＤＢに対し， 本稿がターゲットとする共通構造とはイベントグラフ（の一部） を汎化して得られる変数Xjを持つ素パターンr(X1, ..., Xn) の集合で下記の条件を満たすものとする． 結束性： 素パターンを頂点，それらが変数共有するとき隣接 すると定めたグラフにおいて素パターン集合は連結サブ グラフを形成する．具体には，連鎖からクリークまで幅 広く表現できる 連結 k-Plexであることを要請する． ロール類似性： 素パターン集合中の変数 X はＤＢ毎に異な る実体に具体化され，各ＤＢにおいて該当するイベント が成立する．これは，実体がそれらの関係において同じ ロールを担うことを意味する（ロール類似性）．本稿に おいては，素パターンとして，構文的に可能な全ての述 語形r(X1, ..., Xn)を考えるのではなく，予めロール類似 性による実体の類似クラスを求め，変数は対応する類似 クラス中の実体に束縛することを要請する．このことに より，素パターン集合を記述する際の部品としての変数 と素パターンの数を抑制し，また，k-Plex列挙における 制約として利用する．なお，クラスタ―は複数ＤＢに跨 るクラスタ―であるから，特に，クロスクラスタ―と呼 連絡先:メールアドレスは[email protected] び，ヒントに基づいた局所相関推論[11]で求める．これ は，多様な汎化構造の中からピンポイントに求めるため に用いるが，理屈としては，ヒント無しの通常のクラス タリングであっても良い． 最小支持度規範と実現可能性： 素パターン集合V における変 数をＤＢに現れる実体に代入したとき，その具体化が最 小支持数 K 個以上のＤＢのイベントとして現れること を要請する．この要請を満たす連結素パターン集合を k-CPlex として定め，k-CPlexが本稿で求めるＤＢ群に 対する共通汎化構造を表現する．実現可能性により， k-CPlexは具体化可能なＤＢのイベントグラフに対する共 通汎化となることに注意する． 図1: ＲＤＢ族と共通汎化構造 関係インスタンスをイベントと呼ぶことには多少の議論が必 要だが，関係rと実体aj間に関係インスタンスr(a1, ..., an) が成り立つことを 『a1, ..., an 間に r という出来事が生起し た』と解釈することにする．このことは，今回の提案が，２つ の物語の共通性を検出する研究 （極大類比[8, 7, 6]） から派 人工知能学会研究会資料 SIG-FPAI-B803-15 － 83 －

生しており，登場人物等の実体ai間の関係rをイベントと呼 んだことに由来している．また，イベントグラフの部分同型・ 部分マッチングという意味では，グラフの数を２個から複数個 へと拡張したものになっている．

1.1

グラフマッチングと本研究の立場

ＤＢ間共通汎化構造の問題は，ＤＢが持つイベントグラフ のマッチング問題を解くことになるので，まず，グラフのマッ チング問題について概観し，本研究の立ち位置を明らかにし たい． グラフのマッチング問題は伝統的に最適化手法を用いたもの も多く，例えば，２つの無向グラフの頂点の対応付けで隣接関 係をできるだけ保存する写像を隣接行列の固有値分解と内積総 和最大化で解く手法[5, 4]がある．さらに，特徴ベクトルを持 つ「ランドマーク」を頂点としたグラフから２つの画像間の構 造類似性を同じく頂点の積空間における最適化により求める研 究もある[?]. ２部グラフのマッチングを求める整数計画法ソ ルバー（輸送問題）やハンガリアン法も最適化問題として定式 化されている．いずれの方法を用いるとしても，基本的には頂 点対からなる積の空間を考えることになり，元のグラフの頂点 数が増加した場合，もしくは，複数のグラフに拡張したときの タプルの空間を考えるとき，計算上，組み合わせの深刻な増加 をもたらす．極大類比[8]においてもしかりであり，グラフの 問題としては極大類比は積空間におけるマッチングであった． 本稿の提案とはクロスクラスタ―の導入により「積から和」へ の変換 （次の節1.2）を行い，計算負荷を軽減させる試みと 言えるだろう． 一方，グラフマイニングとして捉えることができる関連研究 としては，サブグラフ同型問題[2]や関係構造マッチング問題 [1]を挙げることができる．前者の手法は，所与のベースグラ フをターゲットグラフへ埋め込む問題を列挙問題としてとらえ ており，本稿における複数ＤＢのどれか一つをベースグラフと して指定し，それ以外のＤＢへの埋め込みを考える場合は利用 可能である．複数ＤＢ間での部分同型が既知であれば，部分に 限定した誘導サブグラフからのサブグラフ同型問題になるが， その部分を求めるタスクが本研究では本質的であり，それゆえ に，サブグラフ同型問題は手法としては使えない．また，関係 構造マッチング[1]の手法は，２つのグラフの頂点対からなる 積空間におけるクリークで，もとのグラフへ埋め込めるものを 探すことができる．積空間がスパースであれば，強力なクリー ク列挙エンジン[10]を用いて問題解決できるが，本研究で欲 しいサブグラフの形状はクリークとは限らない．欲しいものは 基本的にはイベントの連鎖（パス）であり，連鎖を構成するイ ベント集合が疑似クリークもしくはクリークであればなお良い との立場をとる．その理由により，本研究におけるサブグラフ としては，連鎖からクリークまでを表現できる連結k-Plex [9] を拡張したk-CPlexを導入する．ただし，非接続数上限を定 めるパラメータkは比較的に小さなkを想定し，クリーク列 挙に準じた速度で列挙し，長い連鎖が必要な場合は後処理によ り短い連鎖の組み合わせで算出することを想定している．また 同じ理由により，サイズ上限制約（最大サイズk + 1） を課 し，その範囲での連鎖から（擬似）クリークまでを列挙対象と する．

1.2

積から和へ： クロスクラスタ―

前小節で述べたように，２個の対象領域（グラフ）に対して は，各ＤＢが持つグラフの頂点対を頂点とするグラフを考え， 後者のグラフにおけるサブグラフを求める方式が多かった．本 研究においては，元のグラフの頂点は内部情報を有するイベン トであり，イベントを構成する対象領域に跨る実体を結びつけ る操作も必要になる．実体のマッチング（対応づけ）とそれに 基づいたイベントのマッチングの両者を同時に，特に，前者の マッチングを積空間で考えるのは計算上の負荷が大きいという 難点を抱えていた． 本研究で提案する解決策とは，実体の対やタプルではなく， 複数のＤＢが持つ実体の和集合を考え，目標とする共通汎化構 造で必要となる実体のグルーピングを実体集合の和集合の中 のクラスタ―として予め荒く求め，共通汎化構造中の変数は， 対応するクラスタ―中の実体に対する代入だけに限定するこ とにある．クラスタリングは，前節で述べたように，ヒントに 基づく局所相関推論を用い，複数のＤＢ上で対応させたい実 体の集合を小規模のヒントとして与える．実体の対応付けの 根拠は，実体間関係において担うロールが似ているとの類似 性（ロール類似性）であり，したがって，行には関係とロール （関係スキーマにおける属性名）の対を，列にはＤＢの実体を とった行列に対し局所相関推論を施す．具体には，ヒントで与 えた列の相似・類似関係を支持する行の一部分（エビデンス 行）を抽出し，エビデンス行に制限したときの 列（実体）の 類似度によりヒントに出現しない実体の類似関係を導出する． （クロス）クラスタ―はこの類似度によるクラスタリングの結 果である．筆者らの過去の実験において，クロスクラスタ―の 精度は高いとは一般に言えず，「ゴミ」が多数含まれてくるこ とが既に分かっている．ただし，本稿の最終目標はあくまでも 共通構造汎化を得ることであり，素パターン集合に対する実現 可能性制約によりクロスクラスタ―中のゴミが素パターン集 合の実現可能性制約により無効化されるように構造汎化手順 を設計している．この意味で，クラスタ―はターゲットとなる 汎化構造の代入として現れる実体を含んでいれば十分であり， よって，クラスタ―の粒度は大き目の方が経験則としては安全 であろう．逆に言えば，粒度の小さなクロスクラスタ―を用い た場合，汎化構造が極めて少数もしくは存在しないこともあ りえることに注意しておく．これは，ヒントとして与える実体 集合族に対しても言え，ヒントがＤＢ族に照らして「非現実」 な場合は，解が存在しないこともありえる．これらの問題は， 構造類似検索の際に与えるヒントの適切さや類似性を決めるパ ラメータの設定問題として今後の課題としておく．

2.

ＤＢ群とヒントからの局所相関推論

所与のＲＤＢの族 _{D = {D}1, ..., DN} が与えられ，各Dj は実体関連モデルに従うとする．Djは実体の属性を表す表を 一般に有するが，本稿の手法ではそれらにアクセスはしない． 実体の属性情報も勘案した共通汎化構造の話は今後の課題と しておく．また，異なるDi, Djにおいて，同じ実体名が現れ たとしても，それは異なる実体であると仮定する．すなわち， 全ての実体はそれがどのＤＢの実体かを示すデータベースＩＤ を付与し区別する．さらに，関係のインスタンスはいわゆるナ ル（null）値を含んでいても構わないが，ナル値は実体の外 部キーではないので，あったとしても本稿における処理におい ては無視される． 関係r(A1, ..., An)のインスタンスt = r(a1, ..., an)に対し， 実体aj に対し，列 aj の < r, Aj > 行にビットを立てたも のを考える．一般には頻度等の重みでも良いがブール値でも 良い． こうして与えられたＤＢ群_Dに対するロール情報の行列R に対し，ユーザはいくつかの実体集合の族_Hをヒントとして 与える．_Hに属する実体集合_{a1, ..., am}は複数のＤＢに跨 － 84 －

る小規模のクロスクラスタ―であり，ユーザの視点では 相互 に類似関係にある，すなわちai∼ ajとの宣言である． このヒントと「整合的な」他の実体bi, bjに対する相似・類 似関係に拡張し推論する．そのために，所与のデータ行列X の行を近似できる（行の）生成系を，ヒント中の実体集合の実 体を_Hが規定するグラフ位相において近接したもの（エビデ ンス生成系）と，そうではないもの（非エビデンス生成系）の ２種類にわけ，X の行を両者の線形和で近似する．エビデン ス生成系の係数ベクトルが小さくないものを，ヒントと関連 したエビデンス行として認定し，X の行をエビデンス行に制 限した部分行列 Y を得る．Y の列のうち，Hに出現する列 （実体）は，関連行でみれば十分に近接したベクトルであるこ とを期待できるので，Hの実体集合毎に平均化した列ベクト ルを列の生成系（等化空間生成系）としてそのまま用いる．Y の残りの列を，等化空間生成系とそれ以外の列生成系の線形和 で近似し，等化空間における座標ベクトルが近接しているとき に，ヒントHに照らして相似・類似していると推論する．等 化空間座標は，非負行列分解における部分空間法を用いれば， 係数ベクトルとして計算できることも，文献[12]や前回研究 会[11]で報告したとおりである．結局，等化空間におけるク ラスタリングを行い，目的のクロスクラスタ―を抽出する． 節1.2で述べたように，パターン中の変数に対する代入は， 対応するクロスクラスタに属する実体に制限されており，以 降，クロスクラスタ―名と対応する変数名を同一視し，Ai等 で表すことにする．例えば，Di∈ Dの実体集合をe(Di)とす ると，素パターンr(A, B)がDiに於いて具体化可能とは，あ

る(a, b)∈ (e(Di)∩ A) × (e(Di)∩ B)が存在し，r(a, b)がイ

ンスタンスとしてDiの表に出現することを意味する．ナル値 を含む場合，および，部分属性リストに対する含意を考慮し， パターンのD∈ Dへの具体化を厳密には下記で定義する． D への具体化 rをD∈ Dの表とし，属性リスト(A1, ..., An)の部分リスト を(As1, ..., Asm)（m≤ n）とする．表記を簡略化するため， 部分リストに制限した関係を以下，rs₁,...,smと表記する．ただ し，sjは 属性の属性リストにおける序数である．素パターン rs1,...,sm(As1, ..., Asm)がD に具体化できるとは,あるe(D) の実体a1, a2, ..., amとrのインスタンスr(b1, ..., bn)でbsj = ajなるものが存在することと定める．rs₁,...,sm(a1, ..., am)もr のインスタンスと呼ぶ．As_j を変数とみたときの代入は_{Asj = aj}である．また，bk (k̸= sj)は ナル値でも良い．

3.

共通汎化構造のマイニング

最終的なターゲットは，素パターンr(A1, ..., An)の集合枚 挙である．ただし，Aiはクロスクラスタ―名で，それをその まま変数名としても用いる．また，節1. で述べた最小支持度 規範に基づく データベース数の下限 K が与えられていると する．まず，単項述語形r(A)に対し，実現可能なデータベー ス数がK 個未満な場合は，r(A)を拡張した任意の素パター ンは目的の共通汎化構造の厚生要素とはなりえない．このこと に注意し，まず，素パターンの要素となる原子素パターンから 述べる．

3.1

素パターンとＩＰＣ演算

原子素パターン: 単項述語形rs(A)で，K 個以上のＤＢに実現可能なもの．つ まり，K個以上のＤＢD に対し，rs(a) なるa∈ e(D) ∩ A が存在する．この条件を満たさないものは，原子素パターンと しては登録されない． 次に，原子素パターンを組み合わせて，素パターンを形成す る演算子を定義する．これは，同じ 関係名rに対する単項述語 形を組み合わせて引数が２以上の素パターンを形成するための 操作である．ちなみにIPCとはInner Predicate Composition

の略記である． 素パターン形成のためのIPC 演算 まず，原子素パターンは素パターンであり，IPCは素パター ンと原子素パターンを合成した素パターンを返す． (1)入力素パターンと原子素パターンは同じ関係のパターン， つまり，rs1,...,sm(A1, ..., Am)とrs(As)の構文を持ち，共に 実現可能，つまり最低K個のＤＢで具体化を持つことを前提 とする．構文制約として，s̸= sj(1≤ j ≤ m)を要請するが，

r1,2(A, B)とr3(A)からr1,2,3(A, B, A)のような素パターン

を形成するために，あるjに対し，s = sjであっても良い． (2) IPCの出力はp = rs₁,...,sm,s(A1, ..., Am, As)である．た だし，素パターンpは，最低K個のＤＢで実現可能でなけれ ばならない．この条件は，各Dにおけるrs₁,...,sm(A1, ..., Am) のインスタンス(a1, ..., am)の表とrs(As)のインスタンスの 表に対し，pをクエリーとして各ＤＢに投げ，最低でもK個 のＤＢに対し非空の答えが返るときに限り，IPC演算は成功

する．例えば，r1,2(A, B)とr3(A)の場合，r123(a, b, a)がイ

ンスタンスとして存在する実体a, bを持つＤＢがK個以上あ れば良い．素パターンを構成する原子素パターンの数が増加す るに従い，実現可能なデータベースの数は減少し，最小支持度 規範に対しIPC演算は逆単調性を持つことに注意する．

3.2

パターンと k-CPlex

さて，素パターンはその定義から原子素パターンri(Ai)の 集合とみることができた．共通汎化構造とは，素パターンの集 合で最小支持度規範を満たすものである．よって，一般には例 えば {r12(A, B), r24(C, A), q12(D, A)} のように，同一の関係を持つ異なる素パターンを含んで良い． これは，クロスクラスタA, B, C, Dの要素a, b, c, dで， r12(a, b), r24(c, a), q12(d, a) なるものが最低K 個以上のＤＢで存在することを意味する． 原子素パターンとして表現すれば

{{r1(A), r2(B)}, {r2(C), r4(A)}, {q1(D), q2(A)}}

となり，原子素パターンの集合族を重複なく列挙しながら，要 素集合に対してIPCを適用し，最小支持度規範をみなすもの を求めればよいことに気づく．一般論としてはそれでよいが， 本稿においては，原子素パターンの集合族の列挙ではなく，集 合列挙により構文的に制限されたパターン列挙を提案する．す なわち，下記のk-CPlexの重複のない枚挙を考える． k-CPlex V の定義 原子素パターンの集合V 中，同一の関係を持つ原子素パター ンは全てIPC演算を適用することを仮定する．この仮定のもと に，V 中に出現する関係名をm個とすると，丁度m個の素パ ターンをV は表現していることになる．これらの素パターン をp1, ..., pmとしたとき，pi, pjが変数を共有するときにエッ ジを張ったグラフにおいて，{p1, ..., pm}は連結k-Plexであ － 85 －

り，かつ，p1, ..., pmの連言クエリーをＤＢに投げたとき，最 低K個のＤＢに対して非空の答えが返るとき，V をk-CPlex と定める．k-CPlex V は，V を真に含む原子素パターン集合 で最小支持度規範と実現可能性制約を満たすものが存在しない とき，極大であると言う． 例えば，原子素パターン集合 V ={p1(A), p2(B), q1(B), q2(C), r1(C), r2(A)}は {p(a, b), q(b, c), r(c, a)} ⊆ D1 {p(x, y), q(y, z), r(z, x)} ⊆ D3 かつ a, x∈ A, b, y ∈ B, c, z ∈ C であれば K = 2のもとで1-CPlex（クリーク）である．素パターン集 合としては_{p12(A, B), q12(B, C), r12(C, A)}である． 節1.1で述べたk-Plex性は，あくまでもIPC演算で合成 された素パターン集合に対する制約であり，原子素パターンに 対するものではないことに注意する．そうした違いはあるが， 極大（連結）k-CPlex列挙における候補集合の定義は，極大連 結k-Plexに対するものと全く同様であり，原子素パターンを 基本要素とする重複のない集合列挙をベースに，暫定k-CPlex に追加可能な候補（原子素パターン）を順次組み合わせるだけ で極大k-CPlexの列挙エンジンを容易に設計できる．具体的 には，連結k-CPlex V に対する候補原子素パターンpi(A)と しては，下記の２種類のものを考えれば十分である． • ケース１（既存の関係）：pはV 中の関係名として既に 使われている． この場合，pi(A) はIPC演算の対象となるのみであり， 素パターン集合のk-Plex性には影響を及ぼさない．す なわち，IPC 演算により関係pの素パターンを更新し， V ∪ {pi(A)}が 最低K 個のDBで実現可能であれば， pi(A)はV に対する候補となる • ケース２ （新規の関係）：pi(A)の関係名pはV 中の関 係名として出現していない． この場合，pi(A)は特に素パターンとして，追加後のV∪

{pi(A)}は素パターン集合とみたとき，連結k-Plexでな

ければならない．言うまでもなく，最低K 個のDBで 実現されなければならない． 連結k-CPlexの実際の疑似コードは，候補集合の定義からほ ぼ自明なので省略する．ただし，k-CPlexを採用した最大の理由 は，k +1個の頂点（素パターン）からなる長さkの連鎖を表現 できることであった．それ故に，素パターン数上限をk +1に設 定する．その限りにおいて，素パターン集合が擬似クリークとな ることを許す．先に掲げた{p12(A, B), q12(B, C), r12(C, A)} はk = 2に対し共通汎化構造を示すことになる．

4.

今後の課題

本稿における共通汎化構造マイニングにおいては(1)クロ スクラスタ―による実現可能性制約に従わせること，および， (2)小さなkを想定したk-CPlex列挙の両者が設計上の最重 要ポイントであった． まず(2)に関しては，長い連鎖はユーザーにとって判読が困 難であり，短い連鎖でないと出力の分析が難しいであろうとの 見解に基づいている．計算論的には，長い連鎖を許すk-Plex 列挙では，クリーク列挙とは異なり，非接続の組み合わせ問 題が生じ，もとの素パターンの隣接関係にもよるが計算負荷 が一気に増大するという点も考慮にいれて今回の設計を行っ た．どの程度のkが必要になるかは，データに依存するので， Knowledge Graphで用いられるＤＢやテキストから定義され るＤＢ等，様々な対象データに対して実験を重ね，より適切な 設計を試みる予定である．さらには，離散組み合わせ的な頂 点集合列挙ではなく，局所クラスタ―を摂動させて得られる DBSCANクラスタ―も有望であり，この設計も行う予定であ る．ただし，局所クラスタ―の定義によっては極めて大きなク ラスタ―が算出されるケースも多く，この課題を克服する必要 性があるだろう． 次に，(1)に関しては，ユーザの視点に応じた類似検索問題 そのものであり，ユーザが与えたヒントを現有のデータに照ら してその適切さをアドバイスするメカニズムが必要になるだろ う．あえて言えば，情報検索におけるフィードバック機構であ り，筆者にとっては喫緊の課題である．

参考文献

[1] Pelillo, M. : A Unifying Framework for Relational Structure Matching , 4th Int’l Conf. on Pattern Recog-nition (Volume:2 ) , 1316 - 1319 vol.2 (1998)

[2] Barrow, H. G. et al: Subgraph isomorphism, matching relational structures and maximal cliques, Information Processing Letters, Vol. 4, pp. 83─84（1976）．

[3] Zhou, F. et al: IEEE Conf. on Computer Vision and Pattern Recognition (2013).

[4] Ferrer, M. et al: Evaluation of Spectral-Based Methods for Median Graph Computation”, LNCS 2007, 4478, 580-587 (2007)

[5] Umeyama,S.: An Eigendecomposition Approach to Weighted Graph Matching Problems. Trans Patt Anal Mach Int, Vol. 10, No. 5, Sep 1988.

[6] Yoshioka, M. et al : Towards Constructing Story Databases Using Maximal Analogies Between Stories, Springer-LNAI 3359, pp. 243-255 (2005).

[7] Haraguchi, M. et al: Discovery of Maximal Analo-gies between Stories, DS’02, LNAI-2534, pp 324–331 (2002).

[8] Haraguchi, M.: Towards a Mathematical Theory of Analogy, Bull. Informatics and Cybernetics, 21,29-56 (1985)

[9] Okubo, Y. et al: Structural Change Pattern Mining Based on Constrained Maximal k-Plex Search, LNAI 7569, pp. 284 - 298 (2012).

[10] Tomita, E.: Efficient Algorithms for Finding Maxi-mum and Maximal Cliques and Their Applications, LNCS 10167, 3–15 (2017).

[11] 笹原 その他: 局所相関推論とＮＭＦ，第108回ＦＰＡＩ

研究会予稿集, 2–5 (2019).

[12] Zhai, H et al: A Linear Algebraic Inference for Feature Association, 12th KICSS, IEEE CPS, 102 – 107 (2017).