パターン分類装置およびパターン分類方法
【課題】複数のパターンを分類可能なパターン分類装置およびパターン分類方法を提供する。
【解決手段】クエリ発行部１４は、グラフＧ内のサブグラフを検索するためのＮ個のパターンにおける第１ノードに対し、互いに異なるＭ個のキーワードを含ませて、Ｎ×Ｍ個の検索パターンを生成し（Ｓ１１）、グラフＧから各検索パターンに合致するサブグラフを検索する（Ｓ１５）。パターン分類部１５は、検索されたサブグラフにおける第２ノード内のインスタンスに基づいてＮ個のパターンを分類する（Ｓ１９）。
【解決手段】クエリ発行部１４は、グラフＧ内のサブグラフを検索するためのＮ個のパターンにおける第１ノードに対し、互いに異なるＭ個のキーワードを含ませて、Ｎ×Ｍ個の検索パターンを生成し（Ｓ１１）、グラフＧから各検索パターンに合致するサブグラフを検索する（Ｓ１５）。パターン分類部１５は、検索されたサブグラフにおける第２ノード内のインスタンスに基づいてＮ個のパターンを分類する（Ｓ１９）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パターン分類装置およびパターン分類方法に関するものである。
【背景技術】
【０００２】
近年にあっては、大量のデータソースがコンピュータネットワーク上に存在しており、複数のデータソースを結合して、単一のデータソースからでは抽出できない情報を取り出す、データウェアハウスなどの技術が注目を集めている。
【０００３】
一方、異なる複数のデータソースから得られた情報を統一的に扱うための枠組みとして、グラフ表現できるデータモデルであるRDF(Resource Description Framework)を用いたセマンティックWeb技術も注目されている。
【０００４】
セマンティックWebでは、SPARQLなどのRDFクエリ言語を用いて検索用のパターン（以下、単にパターンという）のマッチングによって必要な情報を検索するRDF検索技術などが提唱されている。
【０００５】
非特許文献１は、キーワード文字列を含む自然文を検索するシステムにおいて、検索結果が類似するキーワードを類似するクエリとし、類似クエリごとに分類及び、ユーザに類似クエリを提案する仕組みを提供する技術を開示している。しかし、以下の問題があった。
【０００６】
これらの技術で言われるクエリは、パターンの検索キーワード変数に相当するものであり、パターンに相当する部分については一切言及されていない。そのため、パターンの分類を行うことはできない。
【０００７】
例えば、非特許文献２では、対象グラフ集合の特性を反映した構造類似性の提案がなされ、そこでは、特徴的な部分構造を用いて、構造的な類似性を定義し、部分グラフの類似性判定を行う。
【０００８】
しかし、この技術は、ラベル無し無向グラフを対象としており、そのままRDFなどのラベル有り有向グラフへ適用することはできないのである。
【０００９】
RDFなどのノードとアークにラベルを持つグラフ構造データに対する検索を行うためのクエリとして用いるパターンを選択する際に、グラフの構造が複雑であると、意図する検索を行うことができるパターンを探し出すことが困難になるため、パターンを効率的に選択可能にする必要がある。
【００１０】
特に複数の異なるデータソースから結合したグラフの場合には、グラフ中に意味的な重複が含まれ、意味的に類似する異なる構造のパターンが多数存在するため、取捨選択作業が煩雑になる。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】小野田透、湯本高行、角谷和俊、「検索傾向の部分的な類似に基づくトピッククラスタリング」、日本データベース学会論文誌 Vol.7, No.3, pp.49-54, 2008年12月
【非特許文献２】和田貴久、大野博之、稲積宏誠、「対象グラフ集合の特性を反映した構造類似性の提案」、日本データベース学会Letters Vol.6, No.1, pp.185-188，2007年6月
【発明の概要】
【発明が解決しようとする課題】
【００１２】
本発明は、上記に鑑みなされたものであり、その目的とするところは、複数のパターンを分類可能なパターン分類装置およびパターン分類方法を提供することにある。
【課題を解決するための手段】
【００１３】
上記の課題を解決するために、本発明に係るパターン分類装置は、インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースと、前記グラフ内のサブグラフを検索するためのＮ個のパターンにおける第１ノードに対し、互いに異なるＭ個のキーワードを含ませて、Ｎ×Ｍ個の検索パターンを生成し、前記グラフから前記各検索パターンに合致するサブグラフを検索するグラフ検索手段と、前記検索されたサブグラフにおける第２ノード内のインスタンスを使用して前記Ｎ個のパターンにおける２つのパターンからなる組み合わせのそれぞれについて類似の度合いを求め、当該類似の度合いに基づいて前記Ｎ個のパターンを分類するパターン分類手段とを備えることを特徴とする。
【００１４】
また、本発明に係るパターン分類方法は、インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースを備えるパターン分類装置が行うパターン分類方法であって、前記パターン分類装置のグラフ検索手段が、前記グラフ内のサブグラフを検索するためのＮ個のパターンにおける第１ノードに対し、互いに異なるＭ個のキーワードを含ませて、Ｎ×Ｍ個の検索パターンを生成し、前記グラフから前記各検索パターンに合致するサブグラフを検索し、前記パターン分類装置のパターン分類手段が、前記検索されたサブグラフにおける第２ノード内のインスタンスを使用して前記Ｎ個のパターンにおける２つのパターンからなる組み合わせのそれぞれについて類似の度合いを求め、当該類似の度合いに基づいて前記Ｎ個のパターンを分類することを特徴とする。
【００１５】
前記パターン分類手段は、前記Ｎ個のパターンを、前記類似の度合いに基づいて、1つ以上のパターンを含むパターンクラスタに分類するものであって、前記各キーワードにつき、２つのパターンの一方に当該キーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＡ、当該２つのパターンの他方に当該キーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＢとして、
類似判定値＝｜Ａ∩Ｂ｜÷｜Ａ∪Ｂ｜
ただし、
Ａ、Ｂが共に空集合でなく、
｜Ａ∩Ｂ｜は、ＡとＢの積集合の中のインスタンス数、
｜Ａ∪Ｂ｜は、ＡとＢの和集合の中のインスタンス数、
を計算した場合、
前記各キーワードに対応する類似判定値の中のｋ個（０＜ｋ≦Ｋ：ただしＫは前記キーワードの個数）以上が所定のしきい値以上となる当該２つのパターンを、互いに類似するパターンとして、同一のパターンクラスタに含ませるようにしてもよい。
【００１６】
あるいは、前記パターン分類手段は、以下のように処理を行ってもよい。
まず、前記Ｎ×Ｍ個の検索パターンから、該当のサブグラフを得られなかった検索で使用された検索パターンを除外する。
次に、２つの各パターンに共通のキーワードを含ませて得た検索パターンから共にサブグラフが得られた場合には当該２つのパターンを関連づけ、互いに関連づけられた複数のパターンから得られ且つ除外されていない検索パターンに含まれた１つ以上のキーワードをキーワードクラスタと定義し、他のパターンと関連づけられていない単一のパターンから得られ且つ除外されていない検索パターンに含まれた１つ以上のキーワードをキーワードクラスタと定義し、前記複数のキーワードを１つ以上のキーワードクラスタに分類する。
次に、前記各キーワードクラスタから１つのキーワードを選択するとともに、該選択されるキーワードを含み且つ除外されていない検索パターンの数が最も多くなるようにする。
次に、前記各キーワードクラスタにつき、選択されたキーワードを含み且つ除外されていない検索パターンを生成するために使用された１つ以上のパターンを選択する。
次に、前記選択された１つ以上のパターンに含まれ且つ互いに類似する複数のパターンをパターンクラスタと定義し、前記選択された１つ以上のパターンに含まれ且つ他のパターンと類似しない単一のパターンをパターンクラスタと定義し、前記選択された１つ以上のパターンを１つ以上のパターンクラスタに分類するとともに、前者のパターンクラスタに含まれるいずれの２パターンも、前記２パターンの一方に前記選択されたキーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＡ、前記２パターンの他方に前記選択されたキーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＢとした場合、
類似判定値＝｜Ａ∩Ｂ｜÷｜Ａ∪Ｂ｜
ただし、
Ａ、Ｂが共に空集合でなく、
｜Ａ∩Ｂ｜は、ＡとＢの積集合の中のインスタンス数、
｜Ａ∪Ｂ｜は、ＡとＢの和集合の中のインスタンス数、
が所定のしきい値以上となるようにする。
【発明の効果】
【００１７】
本発明によれば、パターンの第１ノードにキーワードを含ませて得られる検索パターンに合致するサブグラフを検索し、そのサブグラフにおける第２ノード内のインスタンスを検索結果として得る場合のパターンを分類でき、パターンの数を実質的に低減することができる。また、パターンをユーザに選択させる場合などにおいて、ユーザはパターンを容易に選択することができる。
【図面の簡単な説明】
【００１８】
【図１】本実施の形態に係るグラフ検索装置の構成図である。
【図２】グラフＧの一部を例示した図である。
【図３】ＲＤＦ／ＸＭＬ形式のデータ、その元データおよびこの形式のデータによるサブグラフを例示した図である。
【図４】パターンをグラフ化して例示した図である。
【図５】パターンを分類する動作を示すシーケンス図である。
【図６】パターンの分類でクラスを選択し、しきい値を指定する際に表示される画面を示す図である。
【図７】パターンを分類する際に生成された検索パターンを示す図である。
【図８】パターンを分類する際に検索されたサブグラフを示す図である。
【図９】ノードのインスタンスを検索する動作を示すシーケンス図である。
【図１０】インスタンスの検索でクラスを選択する際に表示される画面を示す図である。
【図１１】インスタンスの検索でパターンを選択し、キーワードを入力する際に表示される画面を示す図である。
【図１２】検索されたインスタンスを表示する画面を示す図である。
【図１３】パターンを分類する別な方法の説明で使用するパターンとキーワードを示す図である。
【図１４】その方法におけるステップＳ１９の動作を示すフローチャートである。
【図１５】その方法におけるパターンの除外、関連づけ、キーワードの選択の様子を示す図である。
【図１６】その方法においてインスタンスの集合が構成される様子を示す図である。
【図１７】その方法において３３０個のパターンを分類した結果を示す図である。
【図１８】その分類により得られた１つのパターンクラスタに含まれるパターンを示す図である。
【発明を実施するための形態】
【００１９】
以下、本発明の実施の形態を図面を参照して説明する。なお、同一または類似のものには同一符号を付与し、重複説明を省略する。
【００２０】
図１は、本実施の形態に係るグラフ検索装置の構成図である。
グラフ検索装置１は、ユーザ端末２に接続され、ユーザ端末２には、表示装置３が接続されている。
【００２１】
グラフ検索装置１は、表示装置３に表示される入力用インタフェースと出力用インタフェースを生成しユーザ端末２に送信するユーザインタフェース１１と、インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベース１２と、サブグラフの検索に用いられるパターンが記憶されるパターンデータベース１３と、サブグラフやパターンを検索するクエリ発行部１４と、パターンを分類するパターン分類部１５と、分類により得られるパターンクラスタが記憶されるパターンクラスタデータベース１６とを備える。
グラフ検索装置１は、パターン分類部１５を備えることからわかるように、パターン分類装置としても機能する。
【００２２】
図２は、グラフデータベース１２に記憶されたデータ群を全て使って表示できるグラフＧの一部を例示した図である。
【００２３】
グラフデータベース１２に記憶されたデータ群を全て使って、図２に一部を例示したグラフＧ、つまり互いに異なるインスタンスをもつノード間がラベルをもつアークによって接続され且つ当該インスタンスのクラスが定義されたグラフＧ、を表示することができる。逆にいえば、グラフＧを表示するための過不足ないデータ群がグラフデータベース１２に記憶されている。以下、そのデータ群を便宜的にグラフＧという。また、なんらかのグラフ、サブグラフ（なんらかのグラフそのものまたはそれに含まれるグラフ）、パス（分岐および閉ループをもたないグラフ）などをクラスを含めて表示するための過不足ないデータ群を便宜的にグラフ、サブグラフ、パスなどという。
【００２４】
ラベルとは、アークの種類を識別する識別子であり、クラスとは、各インスタンスが属する概念を示すノードであり、インスタンスとは、クラス以外の個々の事物を示すノードである。
【００２５】
グラフＧでは、例えば、「政治」や「山本幸子」などのインスタンスをもつノードが、「ｔｈｅｍｅ：担当者」などのラベルをもつアークで接続される。また、グラフＧでは、ノードにそのインスタンス「政治」などの概念であるクラス「テーマ」などが定義される。
【００２６】
図３に示すように、「論文Ｆ」で示され、その元データの著者が山田太郎でり、題名が「Ｂ技術入門」であり、キーワードがＢ技術である、元データは、グラフデータベース１２では、ＲＤＦ／ＸＭＬ形式のデータとなって、グラフデータベース１２に記憶され、これがグラフＧのサブグラフをなす。「ＲＤＦのグラフ表現」と題されたものは、このサブグラフをグラフィカルに表現したものである。ＲＤＦについては、以下の文献に記載されている。
【００２７】
「Resource Description Framework(RDF)Model and Syntax Specification」, Ora Lassia, Ralph R.Swick編,[online], インターネット<URL:http://www.w3.org/TR/1999/REC-rdf-syntax-19990222/>
「RDF Vocabulary Description Language 1.0: RDF Schema」, Dan Brickley, R.V.Guha編,[online], インターネット<URL:http://www.w3.org/TR/rdf-schema/>
図１に戻り、パターンデータベース１３には、サブグラフの検索に用いられるパターンが記憶される。
【００２８】
図４は、パターンデータベース１３に記憶されたパターンのうちの３パターンをグラフ化して例示した図である。
【００２９】
パターンは、グラフデータベース１２に記憶されるデータ群（グラフＧ）の一部をなすデータ群と同様なものであり、それを本図のようにグラフ化できるので、便宜的にはグラフと言えるが、パターンは表示するものではなく、表示されるグラフの検索に使用されるものである。なお、データ群である実際のパターンを逐一説明するのは冗長なのでグラフ化されたパターンで便宜的に説明する。
【００３０】
一般的にパターンでは、ノードやアークの一部はインスタンスやラベルをもち、残りはそれらをもたない。そして、インスタンスやラベルをもたないノードやアークには変数が設定される。変数は、図に示すように、？とそれに後続する単語からなる。
【００３１】
ここでは、クラス「テーマ」が定義されたノードを一方の端位置に有し、クラス「組織」が定義されたノードを他方の端位置に有し、各ノードがインスタンスをもたず、各アークがラベルをもつ、パターンＰ１、Ｐ２、Ｐ３が、パターンデータベース１３に記憶されていることとする。これらは、いずれもテーマから組織を知るためのパターンであり、パターンＰ１は、「テーマが属する組織」という意味を有し、パターンＰ２は、「テーマの責任者が属する組織」という意味を有し、パターンＰ３は、「テーマの担当者が属する組織」という意味を有する。
【００３２】
このようなパターンによって、あるグラフから検索されるサブグラフは、以下の条件を備えるものである。
【００３３】
つまり、検索されるのは、（１）そのグラフまたはそのサブグラフであって、（２）パターンの構造を過不足なく有し、（３）パターン内でのインスタンスやラベルを過不足なく有し、つまりパターン内でのインスタンスやラベルをもつノードやアークの位置に等しい位置にあるノードやアークが当該インスタンスに等しいインスタンスやラベルを有するものである。
【００３４】
（３）の条件を補足すれば、例えば、パターンの一方端にあるノードのインスタンスを「Ａ」とすると、少なくとも検索されるサブグラフの一方端にあるノードのインスタンスも「Ａ」でなければならず、また、パターンの一方端にあるノードに接続される唯一のアークのラベルを「Ｂ」とすると、当該サブグラフの一方端にあるノードに接続される唯一のアークのラベルも「Ｂ」でなければならず、こうしたインスタンスやラベルのマッチングが、パターン内でのインスタンスやラベルをもつ全てのノードとアークにおいて必要なのである。
【００３５】
なお、パターンにより、このようにしてサブグラフを検索することを、パターンに合致する（マッチするともいう）サブグラフを検索するという。
【００３６】
図１に戻り、クエリ発行部１４は、パターンデータベース１３からパターンを検索する。また、クエリ発行部１４は、グラフＧのサブグラフを検索する。
【００３７】
グラフ検索装置１は、各部（データベース含む）でデータの送受信（受け渡し）が可能であればよい。つまり、各部を、同一のコンピュータに配置してもよいし、複数のコンピュータに分散配置してもよい。また、これらコンピュータをグラフ検索装置やパターン分類装置として動作させるコンピュータプログラムを通信回線を介して送受信してもよい。また、このコンピュータプログラムを、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどの記録媒体に記録し、その記録媒体を流通させてもよい。
【００３８】
（本実施の形態の動作）
図５は、グラフ検索装置１においてパターンを分類する動作を示すシーケンス図である。
【００３９】
グラフ検索装置１では、ユーザインタフェース１１が入力用インタフェースを生成し、それをユーザ端末２に送信して（Ｓ１）、図６で示すように表示させる（Ｓ３）。
【００４０】
ここで、ユーザが、例えば、新聞社などの中で、「政治」というテーマに関連する社内などの組織がどこかを知りたいとする。また、ユーザは、パターン同士の類似の判定を厳しめにしたく、その程度が、１を最大とした場合には、「０．７」であると考えていることとする。
【００４１】
この例では、ユーザの操作により、「テーマ」という情報（クラス「テーマ」という）、「組織」という情報（クラス「組織」という）が、入力用インタフェースに含まれた情報から選択されたこととする。
【００４２】
また、ユーザ端末２では、ユーザの操作により、「０．７」という値（しきい値「０．７」という）が指定されたこととする。
【００４３】
ユーザ端末２は、これらのパラメータをグラフ検索装置１に送信する（Ｓ５）。
【００４４】
グラフ検索装置１では、クエリ発行部１４が、クラス「テーマ」を含む検索構文であるクエリをグラフデータベース１２に送信し、これにより、クラス「テーマ」が定義されたノード内のインスタンス（ここでは、インスタンス「政治」、「歴史」、「科学」（以下、それぞれキーワードＫ１、Ｋ２、Ｋ３という））をグラフデータベース１２から検索する（Ｓ７）。
【００４５】
クエリ発行部１４は、クラス「テーマ」とクラス「組織」を含む検索構文であるクエリをパターンデータベース１３に送信し、これにより、パターンＰ１、Ｐ２、Ｐ３をパターンデータベース１３から検索する（Ｓ９）。
【００４６】
次に、クエリ発行部１４が、パターンＰ１、Ｐ２、Ｐ３における、クラス「テーマ」が定義されたノード（第１ノードという）に対し、各キーワードＫ１、Ｋ２、Ｋ３を含ませて、３（パターン数）×３（キーワード数）個（合計９個）のパターン（以下、検索パターンＰ１１〜Ｐ３３という）を生成する（Ｓ１１）。
【００４７】
図７は、これらの検索パターンを示す図である。
【００４８】
この図では、クラスを図示省略している。例えば、検索パターンＰ１１は、パターンＰ１の第１ノードにキーワードＫ１「政治」をインスタンスとして含ませたものである。
検索パターンＰ１２は、パターンＰ１の第１ノードにキーワードＫ１「歴史」をインスタンスとして含ませたものである。
検索パターンＰ１３は、パターンＰ１の第１ノードにキーワードＫ１「科学」をインスタンスとして含ませたものである。
検索パターンＰ２１は、パターンＰ２の第１ノードにキーワードＫ１「政治」をインスタンスとして含ませたものである。
検索パターンＰ２２は、パターンＰ２の第１ノードにキーワードＫ１「歴史」をインスタンスとして含ませたものである。
検索パターンＰ２３は、パターンＰ２の第１ノードにキーワードＫ１「科学」をインスタンスとして含ませたものである。
検索パターンＰ３１は、パターンＰ３の第１ノードにキーワードＫ１「政治」をインスタンスとして含ませたものである。
検索パターンＰ３２は、パターンＰ３の第１ノードにキーワードＫ１「歴史」をインスタンスとして含ませたものである。
検索パターンＰ３３は、パターンＰ３の第１ノードにキーワードＫ１「科学」をインスタンスとして含ませたものである。
【００４９】
図５に戻り、クエリ発行部１４が、検索パターンＰ１１〜Ｐ３３をクエリに変換し、それをグラフデータベース１２に送信することで、その検索パターンにマッチするサブグラフをグラフＧから取得する（Ｓ１５）。
【００５０】
ここでは、検索パターンＰ１１〜Ｐ３３から、図８に示すようなサブグラフＳＧ（Ｐ１１）〜ＳＧ（Ｐ３３）がそれぞれ取得されたこととする。
【００５１】
図５に戻り、クエリ発行部１４は、パターンＰ１、Ｐ２、Ｐ３、サブグラフＳＧ（Ｐ１１）〜ＳＧ（Ｐ３３）、しきい値「０．７」、クラス「組織」をパターン分類部１５に与える（Ｓ１７）。
【００５２】
パターン分類部１５は、サブグラフ、しきい値、クラスに基づいて、パターンを分類し（Ｓ１９）、分類結果をパターンクラスタデータベース１６に格納する（Ｓ２１）。
【００５３】
ここで、ステップＳ１９を詳述する。
パターン分類部１５は、パターンＰ１〜Ｐ３を１以上のパターンクラスタに分類する。ここでは、複数の類似するパターンを含む集合、または、他のパターンと類似しない単一のパターンをパターンクラスタという。したがって、パターン分類部１５は、例えば、パターンＰ１、Ｐ２を含むパターンクラスタと、パターンＰ３を含むパターンクラスタを生成する。
【００５４】
このとき、パターン分類部１５は、パターンＰ１〜Ｐ３における全てのパターンの組み合わせにつき、以下のような処理を行う。
【００５５】
パターンＰ１、Ｐ２の組の例を説明する。
パターン分類部１５は、パターンＰ１にキーワードＫ１を含ませた検索パターンＰ１１に合致する１つ以上のサブグラフ（ここではサブグラフＳＧ（Ｐ１１））におけるクラス「組織」が定義されたノード（第２ノードという）内のインスタンスの集合（ここでは「○○グループ」のみ）をＲ１１、パターンＰ２にキーワードＫ１を含ませた検索パターンＰ２１に合致する１つ以上のサブグラフ（ここではサブグラフＳＧ（Ｐ２１））におけるクラス「組織」が定義されたノード（第２ノード）内のインスタンスの集合（ここでは「○○グループ」）をＲ２１として、
Ｒ１１、Ｒ２１が共に空集合でないなら、パターンＰ１、Ｐ２、キーワードＫ１に関し、
類似判定値Ｔ（Ｐ１、Ｐ２、Ｋ１）＝｜Ｒ１１∩Ｒ２１｜÷｜Ｒ１１∪Ｒ２１｜
ただし、
｜Ｒ１１∩Ｒ２１｜は、Ｒ１１とＲ２１の積集合の中のインスタンス数、
｜Ｒ１１∪Ｒ２１｜は、Ｒ１１とＲ２１の和集合の中のインスタンス数、
を計算し、類似判定値Ｔ（Ｐ１、Ｐ２、Ｋ１）がしきい値「０．７」以上か否かを判定する。
【００５６】
ここで、類似判定値Ｔ（Ｐ１、Ｐ２、Ｋ１）におけるＰ１、Ｐ２、Ｋ１は、パターンＰ１、Ｐ２、キーワードＫ１に関するものという意味である。以下に説明する類似判定値についても同様である。
【００５７】
さて、ここでは、パターンＰ１、Ｐ２、キーワードＫ１について、類似判定値Ｔ（Ｐ１、Ｐ２、Ｋ１）を計算し、しきい値「０．７」以上か否かを判定するのである。
【００５８】
Ｒ１１∩Ｒ２１は、「○○グループ」を含むので、｜Ｒ１１∩Ｒ２１｜＝１である。
Ｒ１１∪Ｒ２１は、「○○グループ」を含むので、｜Ｒ１１∪Ｒ２１｜＝１である。
よって、類似判定値Ｔ（Ｐ１、Ｐ２、Ｋ１）＝１÷１＝１となり、しきい値「０．７」以上と判定される。
【００５９】
同様に、パターン分類部１５は、パターンＰ１、Ｐ２、キーワードＫ２について、類似判定値Ｔ（Ｐ１、Ｐ２、Ｋ２）を計算し、しきい値「０．７」以上か否かを判定する。
積集合は、「○○グループ」を含むので、積集合の中のインスタンス数＝１である。
和集合は、「○○グループ」を含むので、和集合の中のインスタンス数＝１である。
よって、類似判定値Ｔ（Ｐ１、Ｐ２、Ｋ２）＝１÷１＝１となり、しきい値「０．７」以上と判定される。
【００６０】
同様に、パターン分類部１５は、パターンＰ１、Ｐ２、キーワードＫ３について、類似判定値Ｔ（Ｐ１、Ｐ２、Ｋ３）を計算し、しきい値「０．７」以上か否かを判定する。
積集合は、空集合なので、積集合の中のインスタンス数＝０である。
和集合は、「××グループ」、「△△グループ」を含むので、和集合の中のインスタンス数＝２である。
よって、類似判定値Ｔ（Ｐ１、Ｐ２、Ｋ３）＝０となり、しきい値「０．７」未満と判定される。
【００６１】
次に、パターン分類部１５は、例えば、３つの類似判定値の中のｋ個（０＜ｋ≦Ｋ：ただしＫはキーワードの個数（ここでは「３」）である。）以上がしきい値「０．７」以上であったか否かを判定し、ｋ個以上がしきい値以上であったなら、パターンＰ１、Ｐ２は類似していると判定する。なお、ｋの値は、パラメータとして入力してもよいし、既定値であってもよい。
【００６２】
例えば、ｋ＝１なら、３つの類似判定値の中の少なくとも１つがしきい値以上なら、パターンＰ１、Ｐ２は類似していると判定される。
例えば、ｋ＝３なら、３つの類似判定値の中の全てがしきい値以上なら、パターンＰ１、Ｐ２は類似していると判定される。
【００６３】
なお、類似判定値を計算する際、計算対象の２つの集合の一方または両方に空集合なら、その計算はスキップされる。つまり、スキップなしで、３つの類似判定値が計算される場合だけでなく、それより少ない１つまたは２つの類似判定値が計算される場合もあるのである。
【００６４】
このようにして、パターン分類部１５は、例えば、パターンＰ１、Ｐ２を含むパターンクラスタと、パターンＰ３を含むパターンクラスタを生成する（Ｓ１９）。
【００６５】
パターン分類部１５は、各パターンクラスタ（分類結果）をパターンクラスタデータベース１６に格納する（Ｓ２１）。ここでは、２つ以上のパターンを含むパターンクラスタのみならず、１つのパターンのみを含むパターンクラスタもパターンクラスタデータベース１６に格納される。
【００６６】
図９は、グラフ検索装置１においてグラフＧからノードのインスタンスを検索する動作を示すシーケンス図である。
【００６７】
ユーザインタフェース１１は、入力用インタフェースを生成し、それをユーザ端末２に送信して（Ｓ５１）、図１０に示すように表示させる（Ｓ５３）。
【００６８】
ここで、ユーザは、例えば、パターンを分類する際のユーザであり、「政治」というテーマに関連する社内などの組織がどこかを知りたいとする。
【００６９】
ここでは、ユーザの操作により、「テーマ」という情報（クラス「テーマ」という）、「組織」という情報（クラス「組織」という）が、入力用インタフェースに含まれた情報から選択されたこととする。
【００７０】
ユーザ端末２は、これらパラメータをグラフ検索装置１に送信する（Ｓ５５）。
【００７１】
グラフ検索装置１では、クエリ発行部１４が、クラス「テーマ」とクラス「組織」を含む検索構文であるクエリをパターンデータベース１３に送信し、これにより、パターンＰ１、Ｐ２、Ｐ３をパターンデータベース１３から検索する（Ｓ５９）。
【００７２】
次に、クエリ発行部１４は、パターンクラスタデータベース１６を参照し、パターンＰ１、Ｐ２を含むパターンクラスタがあるので、検索されたパターンＰ１、Ｐ２の一方である、例えばパターンＰ２を除外し（Ｓ６０）、パターンＰ２を除いた２つのパターンＰ１、Ｐ３をユーザインタフェース１１に与える。
【００７３】
ステップＳ６０では、パターンデータベース１３から複数のパターンを含むパターンクラスタを検索し、ステップＳ５９で検索された複数のパターンから、当該パターンクラスタ内の複数のパターンに合致する複数のパターンを選択し、選択された複数のパターンのうちの任意の１つ以上を残して、残りを除外する。
【００７４】
詳しくは、例えば、最も長いパターンを残すようにしてもよい。シンプルでわかりやすいパターンだからである。
また、検索結果が空でなく且つキーワードが多いパターンを残すようにしてもよい。検索結果が得やすいパターンだからである。
また、検索結果が空でなく且つキーワードが少ないパターンを残すようにしてもよい。厳密な検索結果が得やすいパターンだからである。
また、こうした取捨選択をオペレータが判断してもよい。
【００７５】
ユーザインタフェース１１は、入力用インタフェースを生成し、それをユーザ端末２に送信して（Ｓ６１）、図１１に示すように表示させる（Ｓ６３）。ここでは、パターンＰ１、Ｐ３が表示されるが、図１１では、クラスやアークのラベルなどを図示せず、簡易的に示している。
【００７６】
これに対して、ユーザがユーザ端末２にパターンＰ１の選択指示、キーワード「政治」を入力し、ユーザ端末２は、これらパラメータをグラフ検索装置１に送信する（Ｓ６５）。
【００７７】
グラフ検索装置１では、クエリ発行部１４が、選択されたパターンＰ１における、クラス「テーマ」が定義されたノードに対し、キーワード「政治」を含ませて、検索パターン（つまり、図７の検索パターンＰ１１）を生成する（Ｓ６７）。
【００７８】
クエリ発行部１４は、検索パターンＰ１１をクエリに変換し、それをグラフデータベース１２に送信することで、その検索パターンにマッチするサブグラフ（つまり、図８のサブグラフＳＧ（Ｐ１１））をグラフＧから取得する（Ｓ７１）。
【００７９】
次に、クエリ発行部１４は、サブグラフＳＧ（Ｐ１１）におけるクラス「組織」が定義されたノード内のインスタンス（つまり、「○○グループ」）を取り出し、ユーザインタフェース１１に与える（Ｓ７３）。
【００８０】
ユーザインタフェース１１は、出力用インタフェースを生成し、それをユーザ端末２に送信して（Ｓ７５）、図１２に示すように表示させる（Ｓ７７）。
【００８１】
したがって、ユーザは、３つのパターンＰ１、Ｐ２、Ｐ３から１つを選択するのでなく、２つのパターンＰ１、Ｐ３から１つを選択すればよいので、利便性が向上する。
【００８２】
なお、ここでは、１つのパターンを選択したが、２つ以上のパターンを選択してもよい。この際であっても、例えば、選択候補を少なくでき、その少ない選択候補から２つ以上のパターンを選択すればよいので、利便性が向上する。
【００８３】
なお、パターン分類部１５は、複数のパターンを１以上のパターンクラスタに分類する際に、別な方法を用いてもよい。
【００８４】
以下、その一例を説明する。なお、説明のない点については、上記の実施例と同様である。
【００８５】
ここでは、便宜上、図１３に示すように、前述のパターンＰ１などの代わりに、５つのパターンＰ１０１〜Ｐ１０５を使用し、前述のキーワードＫ１などの代わりに、５つのキーワードＫ１１〜Ｋ１５を使用することとする。
【００８６】
図５のステップＳ１１では、クエリ発行部１４は、パターンＰ１０１〜Ｐ１０５における第１ノードに対し、各キーワードＫ１１〜Ｋ１５を含ませて、５（パターン数）×５（キーワード数）個（合計２５個）の検索パターンＰ１０１１〜Ｐ１０５５という）を生成する（Ｓ１１）。
【００８７】
クエリ発行部１４が、検索パターンＰ１０１１〜Ｐ１０５５をクエリに変換し、それをグラフデータベース１２に送信することで、その検索パターンにマッチするサブグラフをグラフＧから取得する（Ｓ１５）。
【００８８】
クエリ発行部１４は、パターンＰ１０１〜Ｐ１０５、サブグラフ、しきい値「０．７」、クラス「組織」をパターン分類部１５に与える（Ｓ１７）。
【００８９】
パターン分類部１５は、サブグラフ、しきい値、クラスに基づいて、パターンを分類し（Ｓ１９）、分類結果をパターンクラスタデータベース１６に格納する（Ｓ２１）。
【００９０】
ここで、ステップＳ１９を詳述する。ステップ１９では、パターン分類部１５は、パターンＰ１０１〜Ｐ１０５を１以上のパターンクラスタに分類する。
【００９１】
図１４は、そのステップＳ１９の動作を示すフローチャートである。
【００９２】
パターン分類部１５は、まず、検索パターンＰ１０１１〜Ｐ１０５５から、該当のサブグラフを得られなかった検索で使用された検索パターンを除外する（Ｓ１９１）。
【００９３】
図１５に示すように、パターン分類部１５は、×印のついた升目に該当する検索パターンを除外する。
【００９４】
次に、パターン分類部１５は、図１５において枠線Ｙ１で囲って示したように、２つの各パターン（例えば、パターンＰ１０１、Ｐ１０２）に共通のキーワード（例えば、キーワードＫ１１）を含ませて得た検索パターン（例えば、検索パターンＰ１０１１、Ｐ１０２１）から共にサブグラフが得られた場合には当該２つのパターン（パターンＰ１０１、Ｐ１０２）を互いに関連づける（Ｓ１９３）。
【００９５】
図１５において、枠線Ｙ２で囲って示したように、４つのパターンＰ１０１〜Ｐ１０４は互いに関連づけられる。
【００９６】
また、パターン分類部１５は、互いに関連づけられた複数のパターンから得られ且つ除外されていない検索パターンに含まれた１つ以上のキーワードをキーワードクラスタと定義する（Ｓ１９５）。図１５によれば、キーワードＫ１１〜Ｋ１４がキーワードクラスタ（キーワードクラスタＣ１という）と定義される。
【００９７】
また、パターン分類部１５は、他のパターンと関連づけられていない単一のパターンから得られ且つ除外されていない検索パターンに含まれた１つ以上のキーワードをキーワードクラスタと定義する（Ｓ１９５）。図１５によれば、キーワードＫ１５がキーワードクラスタ（キーワードクラスタＣ２という）と定義される。
【００９８】
次に、パターン分類部１５は、各キーワードクラスタＣ１、Ｃ２から１つのキーワードを選択する（Ｓ１９７）。その際に、パターン分類部１５は、選択されるキーワードを含み且つ除外されていない検索パターンの数が最も多くなるようにする。図１５によれば、キーワードクラスタＣ１、Ｃ２からそれぞれキーワードＫ１１、Ｋ１４が選択される。
【００９９】
次に、パターン分類部１５は、キーワードクラスタＣ１につき、選択されたキーワードＫ１１を含み且つ除外されていない検索パターンＰ１０１１、Ｐ１０２１、Ｐ１０３１を生成するために使用された１つ以上のパターンＰ１０１、Ｐ１０２、Ｐ１０３を選択する（Ｓ１９９）。
【０１００】
また、パターン分類部１５は、キーワードクラスタＣ２につき、選択されたキーワードＫ１４を含み且つ除外されていない検索パターンＰ１０５５を生成するために使用された１つ以上のパターンＰ１０５を選択する（Ｓ１９９）。
【０１０１】
なお、キーワードクラスタＣ１については、パターンＰ１０１、Ｐ１０２、Ｐ１０３が選択され（Ｓ１９９）、パターンＰ１０４は選択されなかったが、このように選択されなかったパターンが複数ある場合には、そのような複数のパターンを、このステップＳ１９と同様にして、１以上のパターンクラスタに分類してもよい。
【０１０２】
さて、次に、パターン分類部１５は、選択されたパターンＰ１０１、Ｐ１０２、Ｐ１０３に含まれ且つ互いに類似する複数のパターンをパターンクラスタと定義し、パターンＰ１０１、Ｐ１０２、Ｐ１０３に含まれ且つ他のパターンと類似しない単一のパターンをパターンクラスタと定義し、パターンＰ１０１、Ｐ１０２、Ｐ１０３を１つ以上のパターンクラスタに分類する（Ｓ１９１１）。
【０１０３】
ここで、パターン分類部１５は、パターンＰ１０１、Ｐ１０２、Ｐ１０３のような、複数のパターンを含むパターンクラスタに含まれるいずれの２パターンも、その２つのパターンについて求めた類似判定値が予め定めた条件を満たすようにする。
【０１０４】
パターンＰ１０１、Ｐ１０２の例を説明する。
【０１０５】
パターン分類部１５は、パターンＰ１０１にキーワードＫ１１を含ませた検索パターンＰ１０１１に合致する１つ以上のサブグラフにおけるクラス「組織」が定義されたノード（第２ノードという）内のインスタンスの集合をＲ１０１、パターンＰ１０２にキーワードＫ１１を含ませた検索パターンＰ１０２１に合致する１つ以上のサブグラフにおけるクラス「組織」が定義されたノード（第２ノード）内のインスタンスの集合をＲ１０２として、
類似判定値Ｔ（Ｐ１０１、Ｐ１０２）＝｜Ｒ１０１∩Ｒ１０２｜÷｜Ｒ１０１∪Ｒ１０２｜
ただし、
｜Ｒ１０１∩Ｒ１０２｜は、Ｒ１０１とＲ１０２の積集合の中のインスタンス数、
｜Ｒ１０１∪Ｒ１０２｜は、Ｒ１０１とＲ１０２の和集合の中のインスタンス数、
を計算し、類似判定値がしきい値「０．７」以上となるようにする。
【０１０６】
ここで、類似判定値Ｔ（Ｐ１０１、Ｐ１０２）におけるＰ１０１、Ｐ１０２は、パターンＰ１、Ｐ２に関するものという意味である。
【０１０７】
類似判定値がしきい値未満なら、パターンＰ１０１、Ｐ１０２は、１つのパターンクラスタには含まれないこととなる。
【０１０８】
例えば、図１６に示すように、Ｒ１０１がインスタンス「Ａ部門」、「Ｂ部門」を含み、Ｒ１０２がインスタンス「Ａ部門」、「Ｂ部門」、「Ｃ部門」を含むすると、Ｒ１０１∩Ｒ１０２は、「Ａ部門」と「Ｂ部門」を含むので、｜Ｒ１０１∩Ｒ１０２｜＝２である。
【０１０９】
Ｒ１０１∪Ｒ１０２は、「Ａ部門」と「Ｂ部門」と「Ｃ部門」を含むので、｜Ｒ１０１∪Ｒ１０２｜＝３である。
【０１１０】
よって、類似判定値Ｔ（Ｐ１０１、Ｐ１０２）＝２÷３≒０．６７となり、例えば、しきい値が「０．６」なら、そのしきい値以上と判定される。これにより、パターンＰ１０１、Ｐ１０２は１つのパターンクラスタに含まれることとなる。例えば、しきい値が「０．９」なら、そのしきい値未満と判定される。これにより、パターンＰ１０１、Ｐ１０２は１つのパターンクラスタに含まれないこととなる。
【０１１１】
このようにして、パターン分類部１５は、例えば、２つのパターンＰ１０１、Ｐ１０２を含むパターンクラスタと、１つのパターンＰ１０３を含むパターンクラスタを生成する。
【０１１２】
また、パターン分類部１５は、パターンＰ１０５についても同様のことを行うが、この場合、パターンＰ１０５がパターンクラスタとなる。
【０１１３】
これまでの説明では、便宜的に、３つまたは４つのパターンを分類する例を示したが、実際には、例えば、３００個程度のパターンを分類することが多い。
【０１１４】
上記の別な方法を用いて、その際のしきい値を「０．８」として、３３０個のパターンを分類すると、例えば、図１７に示すような結果が得られた。
【０１１５】
まず、３３０個のパターンから１７２個のパターンクラスタが得られた。１個のパターンを含むパターンクラスタの数は１１６であった。２個のパターンを含むパターンクラスタの数は３５であった。以下、パターンクラスタ中のパターンの数とパターンクラスタの数の関係は、図に示す通りであった。
【０１１６】
図１８は、図１７の矢印Ｙ３で示すパターンクラスタ内の９個のパターンを示す図である。
【０１１７】
これらのパターンは互いに類似しているので、クエリ発行部１４は、ステップＳ５９で、この３３０個のパターンを検索したなら、その３３０個に含まれる、図の９個のパターンから１つを選択する。同様にして、クエリ発行部１４は、３３０個を１７２個に絞り込むのである。
【０１１８】
そして、ステップＳ６３で１７２個が表示されたら、ユーザは、所望のパターンを１７２個のパターンから選択すればよく、つまり、３３０個のパターンから選択する必要はないので、利便性が向上する。
【０１１９】
以上説明したように、本実施の形態によれば、インスタンスをもつノード間がアークによって接続されたグラフＧが記憶されるグラフデータベース１２と、グラフＧ内のサブグラフを検索するためのＮ個のパターンにおける第１ノードに対し、互いに異なるＭ個のキーワードを含ませて、Ｎ×Ｍ個の検索パターンを生成し（Ｓ１１）、グラフＧから各検索パターンに合致するサブグラフを検索する（Ｓ１５）グラフ検索手段（クエリ発行部１４）と、検索されたサブグラフにおける第２ノード内のインスタンスを使用してＮ個のパターンにおける２つのパターンからなる組み合わせのそれぞれについて類似の度合いを求め、当該類似の度合いに基づいてＮ個のパターンを分類する（Ｓ１９）パターン分類手段（パターン分類部１５）とを備えることで、パターンの第１ノードにキーワードを含ませて得られる検索パターンに合致するサブグラフを検索し、そのサブグラフにおける第２ノード内のインスタンスを検索結果として得る場合のパターンを分類でき、パターンの数を実質的に低減することができる。また、パターンをユーザに選択させる場合などにおいて、ユーザはパターンを容易に選択することができる。
【０１２０】
また、パターン分類手段は、Ｎ個のパターンを、類似の度合いに基づいて、1つ以上のパターンを含むパターンクラスタに分類するものであって、各キーワードにつき、２つのパターンの一方に当該キーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＡ、当該２つのパターンの他方に当該キーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＢとして、
類似判定値＝｜Ａ∩Ｂ｜÷｜Ａ∪Ｂ｜
ただし、
Ａ、Ｂが共に空集合でなく、
｜Ａ∩Ｂ｜は、ＡとＢの積集合の中のインスタンス数、
｜Ａ∪Ｂ｜は、ＡとＢの和集合の中のインスタンス数、
を計算した場合、
前記各キーワードに対応する類似判定値の中のｋ個（０＜ｋ≦Ｋ：ただしＫは前記キーワードの個数）以上が所定のしきい値以上となる当該２つのパターンを同一のパターンクラスタに含ませるので、パターンの数を実質的に低減することができる。また、パターンをユーザに選択させる場合などにおいて、ユーザはパターンを容易に選択することができる。
【０１２１】
また、パターン分類手段は、Ｎ×Ｍ個の検索パターンから、該当のサブグラフを得られなかった検索で使用された検索パターンを除外し（Ｓ１９１）、２つの各パターンに共通のキーワードを含ませて得た検索パターンから共にサブグラフが得られた場合には当該２つのパターンを関連づけ（Ｓ１９３）、互いに関連づけられた複数のパターンから得られ且つ除外されていない検索パターンに含まれた１つ以上のキーワードをキーワードクラスタと定義し（Ｓ１９５）、他のパターンと関連づけられていない単一のパターンから得られ且つ除外されていない検索パターンに含まれた１つ以上のキーワードをキーワードクラスタと定義し（Ｓ１９５）、複数のキーワードを１つ以上のキーワードクラスタに分類し、各キーワードクラスタから１つのキーワードを選択するとともに、該選択されるキーワードを含み且つ除外されていない検索パターンの数が最も多くなるようにし（Ｓ１９７）、各キーワードクラスタにつき、選択されたキーワードを含み且つ除外されていない検索パターンを生成するために使用された１つ以上のパターンを選択し（Ｓ１９９）、選択された１つ以上のパターンに含まれ且つ互いに類似する複数のパターンをパターンクラスタと定義し、選択された１つ以上のパターンに含まれ且つ他のパターンと類似しない単一のパターンをパターンクラスタと定義し、選択された１つ以上のパターンを１つ以上のパターンクラスタに分類する（Ｓ１９１１）とともに、前者のパターンクラスタに含まれるいずれの２パターンも、２パターンの一方に選択されたキーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＡ、前記２パターンの他方に前記選択されたキーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＢとした場合、
類似判定値＝｜Ａ∩Ｂ｜÷｜Ａ∪Ｂ｜
ただし、
Ａ、Ｂが共に空集合でなく、
｜Ａ∩Ｂ｜は、ＡとＢの積集合の中のインスタンス数、
｜Ａ∪Ｂ｜は、ＡとＢの和集合の中のインスタンス数、
が所定のしきい値より大きくなるようにするので、パターンの数を実質的に低減することができる。また、パターンをユーザに選択させる場合などにおいて、ユーザはパターンを容易に選択することができる。
【符号の説明】
【０１２２】
１…グラフ検索装置
２…ユーザ端末
３…表示装置
１１…ユーザインタフェース
１２…グラフデータベース
１３…パターンデータベース
１４…クエリ発行部
１５…パターン分類部
１６…パターンクラスタデータベース
【技術分野】
【０００１】
本発明は、パターン分類装置およびパターン分類方法に関するものである。
【背景技術】
【０００２】
近年にあっては、大量のデータソースがコンピュータネットワーク上に存在しており、複数のデータソースを結合して、単一のデータソースからでは抽出できない情報を取り出す、データウェアハウスなどの技術が注目を集めている。
【０００３】
一方、異なる複数のデータソースから得られた情報を統一的に扱うための枠組みとして、グラフ表現できるデータモデルであるRDF(Resource Description Framework)を用いたセマンティックWeb技術も注目されている。
【０００４】
セマンティックWebでは、SPARQLなどのRDFクエリ言語を用いて検索用のパターン（以下、単にパターンという）のマッチングによって必要な情報を検索するRDF検索技術などが提唱されている。
【０００５】
非特許文献１は、キーワード文字列を含む自然文を検索するシステムにおいて、検索結果が類似するキーワードを類似するクエリとし、類似クエリごとに分類及び、ユーザに類似クエリを提案する仕組みを提供する技術を開示している。しかし、以下の問題があった。
【０００６】
これらの技術で言われるクエリは、パターンの検索キーワード変数に相当するものであり、パターンに相当する部分については一切言及されていない。そのため、パターンの分類を行うことはできない。
【０００７】
例えば、非特許文献２では、対象グラフ集合の特性を反映した構造類似性の提案がなされ、そこでは、特徴的な部分構造を用いて、構造的な類似性を定義し、部分グラフの類似性判定を行う。
【０００８】
しかし、この技術は、ラベル無し無向グラフを対象としており、そのままRDFなどのラベル有り有向グラフへ適用することはできないのである。
【０００９】
RDFなどのノードとアークにラベルを持つグラフ構造データに対する検索を行うためのクエリとして用いるパターンを選択する際に、グラフの構造が複雑であると、意図する検索を行うことができるパターンを探し出すことが困難になるため、パターンを効率的に選択可能にする必要がある。
【００１０】
特に複数の異なるデータソースから結合したグラフの場合には、グラフ中に意味的な重複が含まれ、意味的に類似する異なる構造のパターンが多数存在するため、取捨選択作業が煩雑になる。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】小野田透、湯本高行、角谷和俊、「検索傾向の部分的な類似に基づくトピッククラスタリング」、日本データベース学会論文誌 Vol.7, No.3, pp.49-54, 2008年12月
【非特許文献２】和田貴久、大野博之、稲積宏誠、「対象グラフ集合の特性を反映した構造類似性の提案」、日本データベース学会Letters Vol.6, No.1, pp.185-188，2007年6月
【発明の概要】
【発明が解決しようとする課題】
【００１２】
本発明は、上記に鑑みなされたものであり、その目的とするところは、複数のパターンを分類可能なパターン分類装置およびパターン分類方法を提供することにある。
【課題を解決するための手段】
【００１３】
上記の課題を解決するために、本発明に係るパターン分類装置は、インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースと、前記グラフ内のサブグラフを検索するためのＮ個のパターンにおける第１ノードに対し、互いに異なるＭ個のキーワードを含ませて、Ｎ×Ｍ個の検索パターンを生成し、前記グラフから前記各検索パターンに合致するサブグラフを検索するグラフ検索手段と、前記検索されたサブグラフにおける第２ノード内のインスタンスを使用して前記Ｎ個のパターンにおける２つのパターンからなる組み合わせのそれぞれについて類似の度合いを求め、当該類似の度合いに基づいて前記Ｎ個のパターンを分類するパターン分類手段とを備えることを特徴とする。
【００１４】
また、本発明に係るパターン分類方法は、インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースを備えるパターン分類装置が行うパターン分類方法であって、前記パターン分類装置のグラフ検索手段が、前記グラフ内のサブグラフを検索するためのＮ個のパターンにおける第１ノードに対し、互いに異なるＭ個のキーワードを含ませて、Ｎ×Ｍ個の検索パターンを生成し、前記グラフから前記各検索パターンに合致するサブグラフを検索し、前記パターン分類装置のパターン分類手段が、前記検索されたサブグラフにおける第２ノード内のインスタンスを使用して前記Ｎ個のパターンにおける２つのパターンからなる組み合わせのそれぞれについて類似の度合いを求め、当該類似の度合いに基づいて前記Ｎ個のパターンを分類することを特徴とする。
【００１５】
前記パターン分類手段は、前記Ｎ個のパターンを、前記類似の度合いに基づいて、1つ以上のパターンを含むパターンクラスタに分類するものであって、前記各キーワードにつき、２つのパターンの一方に当該キーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＡ、当該２つのパターンの他方に当該キーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＢとして、
類似判定値＝｜Ａ∩Ｂ｜÷｜Ａ∪Ｂ｜
ただし、
Ａ、Ｂが共に空集合でなく、
｜Ａ∩Ｂ｜は、ＡとＢの積集合の中のインスタンス数、
｜Ａ∪Ｂ｜は、ＡとＢの和集合の中のインスタンス数、
を計算した場合、
前記各キーワードに対応する類似判定値の中のｋ個（０＜ｋ≦Ｋ：ただしＫは前記キーワードの個数）以上が所定のしきい値以上となる当該２つのパターンを、互いに類似するパターンとして、同一のパターンクラスタに含ませるようにしてもよい。
【００１６】
あるいは、前記パターン分類手段は、以下のように処理を行ってもよい。
まず、前記Ｎ×Ｍ個の検索パターンから、該当のサブグラフを得られなかった検索で使用された検索パターンを除外する。
次に、２つの各パターンに共通のキーワードを含ませて得た検索パターンから共にサブグラフが得られた場合には当該２つのパターンを関連づけ、互いに関連づけられた複数のパターンから得られ且つ除外されていない検索パターンに含まれた１つ以上のキーワードをキーワードクラスタと定義し、他のパターンと関連づけられていない単一のパターンから得られ且つ除外されていない検索パターンに含まれた１つ以上のキーワードをキーワードクラスタと定義し、前記複数のキーワードを１つ以上のキーワードクラスタに分類する。
次に、前記各キーワードクラスタから１つのキーワードを選択するとともに、該選択されるキーワードを含み且つ除外されていない検索パターンの数が最も多くなるようにする。
次に、前記各キーワードクラスタにつき、選択されたキーワードを含み且つ除外されていない検索パターンを生成するために使用された１つ以上のパターンを選択する。
次に、前記選択された１つ以上のパターンに含まれ且つ互いに類似する複数のパターンをパターンクラスタと定義し、前記選択された１つ以上のパターンに含まれ且つ他のパターンと類似しない単一のパターンをパターンクラスタと定義し、前記選択された１つ以上のパターンを１つ以上のパターンクラスタに分類するとともに、前者のパターンクラスタに含まれるいずれの２パターンも、前記２パターンの一方に前記選択されたキーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＡ、前記２パターンの他方に前記選択されたキーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＢとした場合、
類似判定値＝｜Ａ∩Ｂ｜÷｜Ａ∪Ｂ｜
ただし、
Ａ、Ｂが共に空集合でなく、
｜Ａ∩Ｂ｜は、ＡとＢの積集合の中のインスタンス数、
｜Ａ∪Ｂ｜は、ＡとＢの和集合の中のインスタンス数、
が所定のしきい値以上となるようにする。
【発明の効果】
【００１７】
本発明によれば、パターンの第１ノードにキーワードを含ませて得られる検索パターンに合致するサブグラフを検索し、そのサブグラフにおける第２ノード内のインスタンスを検索結果として得る場合のパターンを分類でき、パターンの数を実質的に低減することができる。また、パターンをユーザに選択させる場合などにおいて、ユーザはパターンを容易に選択することができる。
【図面の簡単な説明】
【００１８】
【図１】本実施の形態に係るグラフ検索装置の構成図である。
【図２】グラフＧの一部を例示した図である。
【図３】ＲＤＦ／ＸＭＬ形式のデータ、その元データおよびこの形式のデータによるサブグラフを例示した図である。
【図４】パターンをグラフ化して例示した図である。
【図５】パターンを分類する動作を示すシーケンス図である。
【図６】パターンの分類でクラスを選択し、しきい値を指定する際に表示される画面を示す図である。
【図７】パターンを分類する際に生成された検索パターンを示す図である。
【図８】パターンを分類する際に検索されたサブグラフを示す図である。
【図９】ノードのインスタンスを検索する動作を示すシーケンス図である。
【図１０】インスタンスの検索でクラスを選択する際に表示される画面を示す図である。
【図１１】インスタンスの検索でパターンを選択し、キーワードを入力する際に表示される画面を示す図である。
【図１２】検索されたインスタンスを表示する画面を示す図である。
【図１３】パターンを分類する別な方法の説明で使用するパターンとキーワードを示す図である。
【図１４】その方法におけるステップＳ１９の動作を示すフローチャートである。
【図１５】その方法におけるパターンの除外、関連づけ、キーワードの選択の様子を示す図である。
【図１６】その方法においてインスタンスの集合が構成される様子を示す図である。
【図１７】その方法において３３０個のパターンを分類した結果を示す図である。
【図１８】その分類により得られた１つのパターンクラスタに含まれるパターンを示す図である。
【発明を実施するための形態】
【００１９】
以下、本発明の実施の形態を図面を参照して説明する。なお、同一または類似のものには同一符号を付与し、重複説明を省略する。
【００２０】
図１は、本実施の形態に係るグラフ検索装置の構成図である。
グラフ検索装置１は、ユーザ端末２に接続され、ユーザ端末２には、表示装置３が接続されている。
【００２１】
グラフ検索装置１は、表示装置３に表示される入力用インタフェースと出力用インタフェースを生成しユーザ端末２に送信するユーザインタフェース１１と、インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベース１２と、サブグラフの検索に用いられるパターンが記憶されるパターンデータベース１３と、サブグラフやパターンを検索するクエリ発行部１４と、パターンを分類するパターン分類部１５と、分類により得られるパターンクラスタが記憶されるパターンクラスタデータベース１６とを備える。
グラフ検索装置１は、パターン分類部１５を備えることからわかるように、パターン分類装置としても機能する。
【００２２】
図２は、グラフデータベース１２に記憶されたデータ群を全て使って表示できるグラフＧの一部を例示した図である。
【００２３】
グラフデータベース１２に記憶されたデータ群を全て使って、図２に一部を例示したグラフＧ、つまり互いに異なるインスタンスをもつノード間がラベルをもつアークによって接続され且つ当該インスタンスのクラスが定義されたグラフＧ、を表示することができる。逆にいえば、グラフＧを表示するための過不足ないデータ群がグラフデータベース１２に記憶されている。以下、そのデータ群を便宜的にグラフＧという。また、なんらかのグラフ、サブグラフ（なんらかのグラフそのものまたはそれに含まれるグラフ）、パス（分岐および閉ループをもたないグラフ）などをクラスを含めて表示するための過不足ないデータ群を便宜的にグラフ、サブグラフ、パスなどという。
【００２４】
ラベルとは、アークの種類を識別する識別子であり、クラスとは、各インスタンスが属する概念を示すノードであり、インスタンスとは、クラス以外の個々の事物を示すノードである。
【００２５】
グラフＧでは、例えば、「政治」や「山本幸子」などのインスタンスをもつノードが、「ｔｈｅｍｅ：担当者」などのラベルをもつアークで接続される。また、グラフＧでは、ノードにそのインスタンス「政治」などの概念であるクラス「テーマ」などが定義される。
【００２６】
図３に示すように、「論文Ｆ」で示され、その元データの著者が山田太郎でり、題名が「Ｂ技術入門」であり、キーワードがＢ技術である、元データは、グラフデータベース１２では、ＲＤＦ／ＸＭＬ形式のデータとなって、グラフデータベース１２に記憶され、これがグラフＧのサブグラフをなす。「ＲＤＦのグラフ表現」と題されたものは、このサブグラフをグラフィカルに表現したものである。ＲＤＦについては、以下の文献に記載されている。
【００２７】
「Resource Description Framework(RDF)Model and Syntax Specification」, Ora Lassia, Ralph R.Swick編,[online], インターネット<URL:http://www.w3.org/TR/1999/REC-rdf-syntax-19990222/>
「RDF Vocabulary Description Language 1.0: RDF Schema」, Dan Brickley, R.V.Guha編,[online], インターネット<URL:http://www.w3.org/TR/rdf-schema/>
図１に戻り、パターンデータベース１３には、サブグラフの検索に用いられるパターンが記憶される。
【００２８】
図４は、パターンデータベース１３に記憶されたパターンのうちの３パターンをグラフ化して例示した図である。
【００２９】
パターンは、グラフデータベース１２に記憶されるデータ群（グラフＧ）の一部をなすデータ群と同様なものであり、それを本図のようにグラフ化できるので、便宜的にはグラフと言えるが、パターンは表示するものではなく、表示されるグラフの検索に使用されるものである。なお、データ群である実際のパターンを逐一説明するのは冗長なのでグラフ化されたパターンで便宜的に説明する。
【００３０】
一般的にパターンでは、ノードやアークの一部はインスタンスやラベルをもち、残りはそれらをもたない。そして、インスタンスやラベルをもたないノードやアークには変数が設定される。変数は、図に示すように、？とそれに後続する単語からなる。
【００３１】
ここでは、クラス「テーマ」が定義されたノードを一方の端位置に有し、クラス「組織」が定義されたノードを他方の端位置に有し、各ノードがインスタンスをもたず、各アークがラベルをもつ、パターンＰ１、Ｐ２、Ｐ３が、パターンデータベース１３に記憶されていることとする。これらは、いずれもテーマから組織を知るためのパターンであり、パターンＰ１は、「テーマが属する組織」という意味を有し、パターンＰ２は、「テーマの責任者が属する組織」という意味を有し、パターンＰ３は、「テーマの担当者が属する組織」という意味を有する。
【００３２】
このようなパターンによって、あるグラフから検索されるサブグラフは、以下の条件を備えるものである。
【００３３】
つまり、検索されるのは、（１）そのグラフまたはそのサブグラフであって、（２）パターンの構造を過不足なく有し、（３）パターン内でのインスタンスやラベルを過不足なく有し、つまりパターン内でのインスタンスやラベルをもつノードやアークの位置に等しい位置にあるノードやアークが当該インスタンスに等しいインスタンスやラベルを有するものである。
【００３４】
（３）の条件を補足すれば、例えば、パターンの一方端にあるノードのインスタンスを「Ａ」とすると、少なくとも検索されるサブグラフの一方端にあるノードのインスタンスも「Ａ」でなければならず、また、パターンの一方端にあるノードに接続される唯一のアークのラベルを「Ｂ」とすると、当該サブグラフの一方端にあるノードに接続される唯一のアークのラベルも「Ｂ」でなければならず、こうしたインスタンスやラベルのマッチングが、パターン内でのインスタンスやラベルをもつ全てのノードとアークにおいて必要なのである。
【００３５】
なお、パターンにより、このようにしてサブグラフを検索することを、パターンに合致する（マッチするともいう）サブグラフを検索するという。
【００３６】
図１に戻り、クエリ発行部１４は、パターンデータベース１３からパターンを検索する。また、クエリ発行部１４は、グラフＧのサブグラフを検索する。
【００３７】
グラフ検索装置１は、各部（データベース含む）でデータの送受信（受け渡し）が可能であればよい。つまり、各部を、同一のコンピュータに配置してもよいし、複数のコンピュータに分散配置してもよい。また、これらコンピュータをグラフ検索装置やパターン分類装置として動作させるコンピュータプログラムを通信回線を介して送受信してもよい。また、このコンピュータプログラムを、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどの記録媒体に記録し、その記録媒体を流通させてもよい。
【００３８】
（本実施の形態の動作）
図５は、グラフ検索装置１においてパターンを分類する動作を示すシーケンス図である。
【００３９】
グラフ検索装置１では、ユーザインタフェース１１が入力用インタフェースを生成し、それをユーザ端末２に送信して（Ｓ１）、図６で示すように表示させる（Ｓ３）。
【００４０】
ここで、ユーザが、例えば、新聞社などの中で、「政治」というテーマに関連する社内などの組織がどこかを知りたいとする。また、ユーザは、パターン同士の類似の判定を厳しめにしたく、その程度が、１を最大とした場合には、「０．７」であると考えていることとする。
【００４１】
この例では、ユーザの操作により、「テーマ」という情報（クラス「テーマ」という）、「組織」という情報（クラス「組織」という）が、入力用インタフェースに含まれた情報から選択されたこととする。
【００４２】
また、ユーザ端末２では、ユーザの操作により、「０．７」という値（しきい値「０．７」という）が指定されたこととする。
【００４３】
ユーザ端末２は、これらのパラメータをグラフ検索装置１に送信する（Ｓ５）。
【００４４】
グラフ検索装置１では、クエリ発行部１４が、クラス「テーマ」を含む検索構文であるクエリをグラフデータベース１２に送信し、これにより、クラス「テーマ」が定義されたノード内のインスタンス（ここでは、インスタンス「政治」、「歴史」、「科学」（以下、それぞれキーワードＫ１、Ｋ２、Ｋ３という））をグラフデータベース１２から検索する（Ｓ７）。
【００４５】
クエリ発行部１４は、クラス「テーマ」とクラス「組織」を含む検索構文であるクエリをパターンデータベース１３に送信し、これにより、パターンＰ１、Ｐ２、Ｐ３をパターンデータベース１３から検索する（Ｓ９）。
【００４６】
次に、クエリ発行部１４が、パターンＰ１、Ｐ２、Ｐ３における、クラス「テーマ」が定義されたノード（第１ノードという）に対し、各キーワードＫ１、Ｋ２、Ｋ３を含ませて、３（パターン数）×３（キーワード数）個（合計９個）のパターン（以下、検索パターンＰ１１〜Ｐ３３という）を生成する（Ｓ１１）。
【００４７】
図７は、これらの検索パターンを示す図である。
【００４８】
この図では、クラスを図示省略している。例えば、検索パターンＰ１１は、パターンＰ１の第１ノードにキーワードＫ１「政治」をインスタンスとして含ませたものである。
検索パターンＰ１２は、パターンＰ１の第１ノードにキーワードＫ１「歴史」をインスタンスとして含ませたものである。
検索パターンＰ１３は、パターンＰ１の第１ノードにキーワードＫ１「科学」をインスタンスとして含ませたものである。
検索パターンＰ２１は、パターンＰ２の第１ノードにキーワードＫ１「政治」をインスタンスとして含ませたものである。
検索パターンＰ２２は、パターンＰ２の第１ノードにキーワードＫ１「歴史」をインスタンスとして含ませたものである。
検索パターンＰ２３は、パターンＰ２の第１ノードにキーワードＫ１「科学」をインスタンスとして含ませたものである。
検索パターンＰ３１は、パターンＰ３の第１ノードにキーワードＫ１「政治」をインスタンスとして含ませたものである。
検索パターンＰ３２は、パターンＰ３の第１ノードにキーワードＫ１「歴史」をインスタンスとして含ませたものである。
検索パターンＰ３３は、パターンＰ３の第１ノードにキーワードＫ１「科学」をインスタンスとして含ませたものである。
【００４９】
図５に戻り、クエリ発行部１４が、検索パターンＰ１１〜Ｐ３３をクエリに変換し、それをグラフデータベース１２に送信することで、その検索パターンにマッチするサブグラフをグラフＧから取得する（Ｓ１５）。
【００５０】
ここでは、検索パターンＰ１１〜Ｐ３３から、図８に示すようなサブグラフＳＧ（Ｐ１１）〜ＳＧ（Ｐ３３）がそれぞれ取得されたこととする。
【００５１】
図５に戻り、クエリ発行部１４は、パターンＰ１、Ｐ２、Ｐ３、サブグラフＳＧ（Ｐ１１）〜ＳＧ（Ｐ３３）、しきい値「０．７」、クラス「組織」をパターン分類部１５に与える（Ｓ１７）。
【００５２】
パターン分類部１５は、サブグラフ、しきい値、クラスに基づいて、パターンを分類し（Ｓ１９）、分類結果をパターンクラスタデータベース１６に格納する（Ｓ２１）。
【００５３】
ここで、ステップＳ１９を詳述する。
パターン分類部１５は、パターンＰ１〜Ｐ３を１以上のパターンクラスタに分類する。ここでは、複数の類似するパターンを含む集合、または、他のパターンと類似しない単一のパターンをパターンクラスタという。したがって、パターン分類部１５は、例えば、パターンＰ１、Ｐ２を含むパターンクラスタと、パターンＰ３を含むパターンクラスタを生成する。
【００５４】
このとき、パターン分類部１５は、パターンＰ１〜Ｐ３における全てのパターンの組み合わせにつき、以下のような処理を行う。
【００５５】
パターンＰ１、Ｐ２の組の例を説明する。
パターン分類部１５は、パターンＰ１にキーワードＫ１を含ませた検索パターンＰ１１に合致する１つ以上のサブグラフ（ここではサブグラフＳＧ（Ｐ１１））におけるクラス「組織」が定義されたノード（第２ノードという）内のインスタンスの集合（ここでは「○○グループ」のみ）をＲ１１、パターンＰ２にキーワードＫ１を含ませた検索パターンＰ２１に合致する１つ以上のサブグラフ（ここではサブグラフＳＧ（Ｐ２１））におけるクラス「組織」が定義されたノード（第２ノード）内のインスタンスの集合（ここでは「○○グループ」）をＲ２１として、
Ｒ１１、Ｒ２１が共に空集合でないなら、パターンＰ１、Ｐ２、キーワードＫ１に関し、
類似判定値Ｔ（Ｐ１、Ｐ２、Ｋ１）＝｜Ｒ１１∩Ｒ２１｜÷｜Ｒ１１∪Ｒ２１｜
ただし、
｜Ｒ１１∩Ｒ２１｜は、Ｒ１１とＲ２１の積集合の中のインスタンス数、
｜Ｒ１１∪Ｒ２１｜は、Ｒ１１とＲ２１の和集合の中のインスタンス数、
を計算し、類似判定値Ｔ（Ｐ１、Ｐ２、Ｋ１）がしきい値「０．７」以上か否かを判定する。
【００５６】
ここで、類似判定値Ｔ（Ｐ１、Ｐ２、Ｋ１）におけるＰ１、Ｐ２、Ｋ１は、パターンＰ１、Ｐ２、キーワードＫ１に関するものという意味である。以下に説明する類似判定値についても同様である。
【００５７】
さて、ここでは、パターンＰ１、Ｐ２、キーワードＫ１について、類似判定値Ｔ（Ｐ１、Ｐ２、Ｋ１）を計算し、しきい値「０．７」以上か否かを判定するのである。
【００５８】
Ｒ１１∩Ｒ２１は、「○○グループ」を含むので、｜Ｒ１１∩Ｒ２１｜＝１である。
Ｒ１１∪Ｒ２１は、「○○グループ」を含むので、｜Ｒ１１∪Ｒ２１｜＝１である。
よって、類似判定値Ｔ（Ｐ１、Ｐ２、Ｋ１）＝１÷１＝１となり、しきい値「０．７」以上と判定される。
【００５９】
同様に、パターン分類部１５は、パターンＰ１、Ｐ２、キーワードＫ２について、類似判定値Ｔ（Ｐ１、Ｐ２、Ｋ２）を計算し、しきい値「０．７」以上か否かを判定する。
積集合は、「○○グループ」を含むので、積集合の中のインスタンス数＝１である。
和集合は、「○○グループ」を含むので、和集合の中のインスタンス数＝１である。
よって、類似判定値Ｔ（Ｐ１、Ｐ２、Ｋ２）＝１÷１＝１となり、しきい値「０．７」以上と判定される。
【００６０】
同様に、パターン分類部１５は、パターンＰ１、Ｐ２、キーワードＫ３について、類似判定値Ｔ（Ｐ１、Ｐ２、Ｋ３）を計算し、しきい値「０．７」以上か否かを判定する。
積集合は、空集合なので、積集合の中のインスタンス数＝０である。
和集合は、「××グループ」、「△△グループ」を含むので、和集合の中のインスタンス数＝２である。
よって、類似判定値Ｔ（Ｐ１、Ｐ２、Ｋ３）＝０となり、しきい値「０．７」未満と判定される。
【００６１】
次に、パターン分類部１５は、例えば、３つの類似判定値の中のｋ個（０＜ｋ≦Ｋ：ただしＫはキーワードの個数（ここでは「３」）である。）以上がしきい値「０．７」以上であったか否かを判定し、ｋ個以上がしきい値以上であったなら、パターンＰ１、Ｐ２は類似していると判定する。なお、ｋの値は、パラメータとして入力してもよいし、既定値であってもよい。
【００６２】
例えば、ｋ＝１なら、３つの類似判定値の中の少なくとも１つがしきい値以上なら、パターンＰ１、Ｐ２は類似していると判定される。
例えば、ｋ＝３なら、３つの類似判定値の中の全てがしきい値以上なら、パターンＰ１、Ｐ２は類似していると判定される。
【００６３】
なお、類似判定値を計算する際、計算対象の２つの集合の一方または両方に空集合なら、その計算はスキップされる。つまり、スキップなしで、３つの類似判定値が計算される場合だけでなく、それより少ない１つまたは２つの類似判定値が計算される場合もあるのである。
【００６４】
このようにして、パターン分類部１５は、例えば、パターンＰ１、Ｐ２を含むパターンクラスタと、パターンＰ３を含むパターンクラスタを生成する（Ｓ１９）。
【００６５】
パターン分類部１５は、各パターンクラスタ（分類結果）をパターンクラスタデータベース１６に格納する（Ｓ２１）。ここでは、２つ以上のパターンを含むパターンクラスタのみならず、１つのパターンのみを含むパターンクラスタもパターンクラスタデータベース１６に格納される。
【００６６】
図９は、グラフ検索装置１においてグラフＧからノードのインスタンスを検索する動作を示すシーケンス図である。
【００６７】
ユーザインタフェース１１は、入力用インタフェースを生成し、それをユーザ端末２に送信して（Ｓ５１）、図１０に示すように表示させる（Ｓ５３）。
【００６８】
ここで、ユーザは、例えば、パターンを分類する際のユーザであり、「政治」というテーマに関連する社内などの組織がどこかを知りたいとする。
【００６９】
ここでは、ユーザの操作により、「テーマ」という情報（クラス「テーマ」という）、「組織」という情報（クラス「組織」という）が、入力用インタフェースに含まれた情報から選択されたこととする。
【００７０】
ユーザ端末２は、これらパラメータをグラフ検索装置１に送信する（Ｓ５５）。
【００７１】
グラフ検索装置１では、クエリ発行部１４が、クラス「テーマ」とクラス「組織」を含む検索構文であるクエリをパターンデータベース１３に送信し、これにより、パターンＰ１、Ｐ２、Ｐ３をパターンデータベース１３から検索する（Ｓ５９）。
【００７２】
次に、クエリ発行部１４は、パターンクラスタデータベース１６を参照し、パターンＰ１、Ｐ２を含むパターンクラスタがあるので、検索されたパターンＰ１、Ｐ２の一方である、例えばパターンＰ２を除外し（Ｓ６０）、パターンＰ２を除いた２つのパターンＰ１、Ｐ３をユーザインタフェース１１に与える。
【００７３】
ステップＳ６０では、パターンデータベース１３から複数のパターンを含むパターンクラスタを検索し、ステップＳ５９で検索された複数のパターンから、当該パターンクラスタ内の複数のパターンに合致する複数のパターンを選択し、選択された複数のパターンのうちの任意の１つ以上を残して、残りを除外する。
【００７４】
詳しくは、例えば、最も長いパターンを残すようにしてもよい。シンプルでわかりやすいパターンだからである。
また、検索結果が空でなく且つキーワードが多いパターンを残すようにしてもよい。検索結果が得やすいパターンだからである。
また、検索結果が空でなく且つキーワードが少ないパターンを残すようにしてもよい。厳密な検索結果が得やすいパターンだからである。
また、こうした取捨選択をオペレータが判断してもよい。
【００７５】
ユーザインタフェース１１は、入力用インタフェースを生成し、それをユーザ端末２に送信して（Ｓ６１）、図１１に示すように表示させる（Ｓ６３）。ここでは、パターンＰ１、Ｐ３が表示されるが、図１１では、クラスやアークのラベルなどを図示せず、簡易的に示している。
【００７６】
これに対して、ユーザがユーザ端末２にパターンＰ１の選択指示、キーワード「政治」を入力し、ユーザ端末２は、これらパラメータをグラフ検索装置１に送信する（Ｓ６５）。
【００７７】
グラフ検索装置１では、クエリ発行部１４が、選択されたパターンＰ１における、クラス「テーマ」が定義されたノードに対し、キーワード「政治」を含ませて、検索パターン（つまり、図７の検索パターンＰ１１）を生成する（Ｓ６７）。
【００７８】
クエリ発行部１４は、検索パターンＰ１１をクエリに変換し、それをグラフデータベース１２に送信することで、その検索パターンにマッチするサブグラフ（つまり、図８のサブグラフＳＧ（Ｐ１１））をグラフＧから取得する（Ｓ７１）。
【００７９】
次に、クエリ発行部１４は、サブグラフＳＧ（Ｐ１１）におけるクラス「組織」が定義されたノード内のインスタンス（つまり、「○○グループ」）を取り出し、ユーザインタフェース１１に与える（Ｓ７３）。
【００８０】
ユーザインタフェース１１は、出力用インタフェースを生成し、それをユーザ端末２に送信して（Ｓ７５）、図１２に示すように表示させる（Ｓ７７）。
【００８１】
したがって、ユーザは、３つのパターンＰ１、Ｐ２、Ｐ３から１つを選択するのでなく、２つのパターンＰ１、Ｐ３から１つを選択すればよいので、利便性が向上する。
【００８２】
なお、ここでは、１つのパターンを選択したが、２つ以上のパターンを選択してもよい。この際であっても、例えば、選択候補を少なくでき、その少ない選択候補から２つ以上のパターンを選択すればよいので、利便性が向上する。
【００８３】
なお、パターン分類部１５は、複数のパターンを１以上のパターンクラスタに分類する際に、別な方法を用いてもよい。
【００８４】
以下、その一例を説明する。なお、説明のない点については、上記の実施例と同様である。
【００８５】
ここでは、便宜上、図１３に示すように、前述のパターンＰ１などの代わりに、５つのパターンＰ１０１〜Ｐ１０５を使用し、前述のキーワードＫ１などの代わりに、５つのキーワードＫ１１〜Ｋ１５を使用することとする。
【００８６】
図５のステップＳ１１では、クエリ発行部１４は、パターンＰ１０１〜Ｐ１０５における第１ノードに対し、各キーワードＫ１１〜Ｋ１５を含ませて、５（パターン数）×５（キーワード数）個（合計２５個）の検索パターンＰ１０１１〜Ｐ１０５５という）を生成する（Ｓ１１）。
【００８７】
クエリ発行部１４が、検索パターンＰ１０１１〜Ｐ１０５５をクエリに変換し、それをグラフデータベース１２に送信することで、その検索パターンにマッチするサブグラフをグラフＧから取得する（Ｓ１５）。
【００８８】
クエリ発行部１４は、パターンＰ１０１〜Ｐ１０５、サブグラフ、しきい値「０．７」、クラス「組織」をパターン分類部１５に与える（Ｓ１７）。
【００８９】
パターン分類部１５は、サブグラフ、しきい値、クラスに基づいて、パターンを分類し（Ｓ１９）、分類結果をパターンクラスタデータベース１６に格納する（Ｓ２１）。
【００９０】
ここで、ステップＳ１９を詳述する。ステップ１９では、パターン分類部１５は、パターンＰ１０１〜Ｐ１０５を１以上のパターンクラスタに分類する。
【００９１】
図１４は、そのステップＳ１９の動作を示すフローチャートである。
【００９２】
パターン分類部１５は、まず、検索パターンＰ１０１１〜Ｐ１０５５から、該当のサブグラフを得られなかった検索で使用された検索パターンを除外する（Ｓ１９１）。
【００９３】
図１５に示すように、パターン分類部１５は、×印のついた升目に該当する検索パターンを除外する。
【００９４】
次に、パターン分類部１５は、図１５において枠線Ｙ１で囲って示したように、２つの各パターン（例えば、パターンＰ１０１、Ｐ１０２）に共通のキーワード（例えば、キーワードＫ１１）を含ませて得た検索パターン（例えば、検索パターンＰ１０１１、Ｐ１０２１）から共にサブグラフが得られた場合には当該２つのパターン（パターンＰ１０１、Ｐ１０２）を互いに関連づける（Ｓ１９３）。
【００９５】
図１５において、枠線Ｙ２で囲って示したように、４つのパターンＰ１０１〜Ｐ１０４は互いに関連づけられる。
【００９６】
また、パターン分類部１５は、互いに関連づけられた複数のパターンから得られ且つ除外されていない検索パターンに含まれた１つ以上のキーワードをキーワードクラスタと定義する（Ｓ１９５）。図１５によれば、キーワードＫ１１〜Ｋ１４がキーワードクラスタ（キーワードクラスタＣ１という）と定義される。
【００９７】
また、パターン分類部１５は、他のパターンと関連づけられていない単一のパターンから得られ且つ除外されていない検索パターンに含まれた１つ以上のキーワードをキーワードクラスタと定義する（Ｓ１９５）。図１５によれば、キーワードＫ１５がキーワードクラスタ（キーワードクラスタＣ２という）と定義される。
【００９８】
次に、パターン分類部１５は、各キーワードクラスタＣ１、Ｃ２から１つのキーワードを選択する（Ｓ１９７）。その際に、パターン分類部１５は、選択されるキーワードを含み且つ除外されていない検索パターンの数が最も多くなるようにする。図１５によれば、キーワードクラスタＣ１、Ｃ２からそれぞれキーワードＫ１１、Ｋ１４が選択される。
【００９９】
次に、パターン分類部１５は、キーワードクラスタＣ１につき、選択されたキーワードＫ１１を含み且つ除外されていない検索パターンＰ１０１１、Ｐ１０２１、Ｐ１０３１を生成するために使用された１つ以上のパターンＰ１０１、Ｐ１０２、Ｐ１０３を選択する（Ｓ１９９）。
【０１００】
また、パターン分類部１５は、キーワードクラスタＣ２につき、選択されたキーワードＫ１４を含み且つ除外されていない検索パターンＰ１０５５を生成するために使用された１つ以上のパターンＰ１０５を選択する（Ｓ１９９）。
【０１０１】
なお、キーワードクラスタＣ１については、パターンＰ１０１、Ｐ１０２、Ｐ１０３が選択され（Ｓ１９９）、パターンＰ１０４は選択されなかったが、このように選択されなかったパターンが複数ある場合には、そのような複数のパターンを、このステップＳ１９と同様にして、１以上のパターンクラスタに分類してもよい。
【０１０２】
さて、次に、パターン分類部１５は、選択されたパターンＰ１０１、Ｐ１０２、Ｐ１０３に含まれ且つ互いに類似する複数のパターンをパターンクラスタと定義し、パターンＰ１０１、Ｐ１０２、Ｐ１０３に含まれ且つ他のパターンと類似しない単一のパターンをパターンクラスタと定義し、パターンＰ１０１、Ｐ１０２、Ｐ１０３を１つ以上のパターンクラスタに分類する（Ｓ１９１１）。
【０１０３】
ここで、パターン分類部１５は、パターンＰ１０１、Ｐ１０２、Ｐ１０３のような、複数のパターンを含むパターンクラスタに含まれるいずれの２パターンも、その２つのパターンについて求めた類似判定値が予め定めた条件を満たすようにする。
【０１０４】
パターンＰ１０１、Ｐ１０２の例を説明する。
【０１０５】
パターン分類部１５は、パターンＰ１０１にキーワードＫ１１を含ませた検索パターンＰ１０１１に合致する１つ以上のサブグラフにおけるクラス「組織」が定義されたノード（第２ノードという）内のインスタンスの集合をＲ１０１、パターンＰ１０２にキーワードＫ１１を含ませた検索パターンＰ１０２１に合致する１つ以上のサブグラフにおけるクラス「組織」が定義されたノード（第２ノード）内のインスタンスの集合をＲ１０２として、
類似判定値Ｔ（Ｐ１０１、Ｐ１０２）＝｜Ｒ１０１∩Ｒ１０２｜÷｜Ｒ１０１∪Ｒ１０２｜
ただし、
｜Ｒ１０１∩Ｒ１０２｜は、Ｒ１０１とＲ１０２の積集合の中のインスタンス数、
｜Ｒ１０１∪Ｒ１０２｜は、Ｒ１０１とＲ１０２の和集合の中のインスタンス数、
を計算し、類似判定値がしきい値「０．７」以上となるようにする。
【０１０６】
ここで、類似判定値Ｔ（Ｐ１０１、Ｐ１０２）におけるＰ１０１、Ｐ１０２は、パターンＰ１、Ｐ２に関するものという意味である。
【０１０７】
類似判定値がしきい値未満なら、パターンＰ１０１、Ｐ１０２は、１つのパターンクラスタには含まれないこととなる。
【０１０８】
例えば、図１６に示すように、Ｒ１０１がインスタンス「Ａ部門」、「Ｂ部門」を含み、Ｒ１０２がインスタンス「Ａ部門」、「Ｂ部門」、「Ｃ部門」を含むすると、Ｒ１０１∩Ｒ１０２は、「Ａ部門」と「Ｂ部門」を含むので、｜Ｒ１０１∩Ｒ１０２｜＝２である。
【０１０９】
Ｒ１０１∪Ｒ１０２は、「Ａ部門」と「Ｂ部門」と「Ｃ部門」を含むので、｜Ｒ１０１∪Ｒ１０２｜＝３である。
【０１１０】
よって、類似判定値Ｔ（Ｐ１０１、Ｐ１０２）＝２÷３≒０．６７となり、例えば、しきい値が「０．６」なら、そのしきい値以上と判定される。これにより、パターンＰ１０１、Ｐ１０２は１つのパターンクラスタに含まれることとなる。例えば、しきい値が「０．９」なら、そのしきい値未満と判定される。これにより、パターンＰ１０１、Ｐ１０２は１つのパターンクラスタに含まれないこととなる。
【０１１１】
このようにして、パターン分類部１５は、例えば、２つのパターンＰ１０１、Ｐ１０２を含むパターンクラスタと、１つのパターンＰ１０３を含むパターンクラスタを生成する。
【０１１２】
また、パターン分類部１５は、パターンＰ１０５についても同様のことを行うが、この場合、パターンＰ１０５がパターンクラスタとなる。
【０１１３】
これまでの説明では、便宜的に、３つまたは４つのパターンを分類する例を示したが、実際には、例えば、３００個程度のパターンを分類することが多い。
【０１１４】
上記の別な方法を用いて、その際のしきい値を「０．８」として、３３０個のパターンを分類すると、例えば、図１７に示すような結果が得られた。
【０１１５】
まず、３３０個のパターンから１７２個のパターンクラスタが得られた。１個のパターンを含むパターンクラスタの数は１１６であった。２個のパターンを含むパターンクラスタの数は３５であった。以下、パターンクラスタ中のパターンの数とパターンクラスタの数の関係は、図に示す通りであった。
【０１１６】
図１８は、図１７の矢印Ｙ３で示すパターンクラスタ内の９個のパターンを示す図である。
【０１１７】
これらのパターンは互いに類似しているので、クエリ発行部１４は、ステップＳ５９で、この３３０個のパターンを検索したなら、その３３０個に含まれる、図の９個のパターンから１つを選択する。同様にして、クエリ発行部１４は、３３０個を１７２個に絞り込むのである。
【０１１８】
そして、ステップＳ６３で１７２個が表示されたら、ユーザは、所望のパターンを１７２個のパターンから選択すればよく、つまり、３３０個のパターンから選択する必要はないので、利便性が向上する。
【０１１９】
以上説明したように、本実施の形態によれば、インスタンスをもつノード間がアークによって接続されたグラフＧが記憶されるグラフデータベース１２と、グラフＧ内のサブグラフを検索するためのＮ個のパターンにおける第１ノードに対し、互いに異なるＭ個のキーワードを含ませて、Ｎ×Ｍ個の検索パターンを生成し（Ｓ１１）、グラフＧから各検索パターンに合致するサブグラフを検索する（Ｓ１５）グラフ検索手段（クエリ発行部１４）と、検索されたサブグラフにおける第２ノード内のインスタンスを使用してＮ個のパターンにおける２つのパターンからなる組み合わせのそれぞれについて類似の度合いを求め、当該類似の度合いに基づいてＮ個のパターンを分類する（Ｓ１９）パターン分類手段（パターン分類部１５）とを備えることで、パターンの第１ノードにキーワードを含ませて得られる検索パターンに合致するサブグラフを検索し、そのサブグラフにおける第２ノード内のインスタンスを検索結果として得る場合のパターンを分類でき、パターンの数を実質的に低減することができる。また、パターンをユーザに選択させる場合などにおいて、ユーザはパターンを容易に選択することができる。
【０１２０】
また、パターン分類手段は、Ｎ個のパターンを、類似の度合いに基づいて、1つ以上のパターンを含むパターンクラスタに分類するものであって、各キーワードにつき、２つのパターンの一方に当該キーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＡ、当該２つのパターンの他方に当該キーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＢとして、
類似判定値＝｜Ａ∩Ｂ｜÷｜Ａ∪Ｂ｜
ただし、
Ａ、Ｂが共に空集合でなく、
｜Ａ∩Ｂ｜は、ＡとＢの積集合の中のインスタンス数、
｜Ａ∪Ｂ｜は、ＡとＢの和集合の中のインスタンス数、
を計算した場合、
前記各キーワードに対応する類似判定値の中のｋ個（０＜ｋ≦Ｋ：ただしＫは前記キーワードの個数）以上が所定のしきい値以上となる当該２つのパターンを同一のパターンクラスタに含ませるので、パターンの数を実質的に低減することができる。また、パターンをユーザに選択させる場合などにおいて、ユーザはパターンを容易に選択することができる。
【０１２１】
また、パターン分類手段は、Ｎ×Ｍ個の検索パターンから、該当のサブグラフを得られなかった検索で使用された検索パターンを除外し（Ｓ１９１）、２つの各パターンに共通のキーワードを含ませて得た検索パターンから共にサブグラフが得られた場合には当該２つのパターンを関連づけ（Ｓ１９３）、互いに関連づけられた複数のパターンから得られ且つ除外されていない検索パターンに含まれた１つ以上のキーワードをキーワードクラスタと定義し（Ｓ１９５）、他のパターンと関連づけられていない単一のパターンから得られ且つ除外されていない検索パターンに含まれた１つ以上のキーワードをキーワードクラスタと定義し（Ｓ１９５）、複数のキーワードを１つ以上のキーワードクラスタに分類し、各キーワードクラスタから１つのキーワードを選択するとともに、該選択されるキーワードを含み且つ除外されていない検索パターンの数が最も多くなるようにし（Ｓ１９７）、各キーワードクラスタにつき、選択されたキーワードを含み且つ除外されていない検索パターンを生成するために使用された１つ以上のパターンを選択し（Ｓ１９９）、選択された１つ以上のパターンに含まれ且つ互いに類似する複数のパターンをパターンクラスタと定義し、選択された１つ以上のパターンに含まれ且つ他のパターンと類似しない単一のパターンをパターンクラスタと定義し、選択された１つ以上のパターンを１つ以上のパターンクラスタに分類する（Ｓ１９１１）とともに、前者のパターンクラスタに含まれるいずれの２パターンも、２パターンの一方に選択されたキーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＡ、前記２パターンの他方に前記選択されたキーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＢとした場合、
類似判定値＝｜Ａ∩Ｂ｜÷｜Ａ∪Ｂ｜
ただし、
Ａ、Ｂが共に空集合でなく、
｜Ａ∩Ｂ｜は、ＡとＢの積集合の中のインスタンス数、
｜Ａ∪Ｂ｜は、ＡとＢの和集合の中のインスタンス数、
が所定のしきい値より大きくなるようにするので、パターンの数を実質的に低減することができる。また、パターンをユーザに選択させる場合などにおいて、ユーザはパターンを容易に選択することができる。
【符号の説明】
【０１２２】
１…グラフ検索装置
２…ユーザ端末
３…表示装置
１１…ユーザインタフェース
１２…グラフデータベース
１３…パターンデータベース
１４…クエリ発行部
１５…パターン分類部
１６…パターンクラスタデータベース
【特許請求の範囲】
【請求項１】
インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースと、
前記グラフ内のサブグラフを検索するためのＮ個のパターンにおける第１ノードに対し、互いに異なるＭ個のキーワードを含ませて、Ｎ×Ｍ個の検索パターンを生成し、前記グラフから前記各検索パターンに合致するサブグラフを検索するグラフ検索手段と、
前記検索されたサブグラフにおける第２ノード内のインスタンスを使用して前記Ｎ個のパターンにおける２つのパターンからなる組み合わせのそれぞれについて類似の度合いを求め、当該類似の度合いに基づいて前記Ｎ個のパターンを分類するパターン分類手段と
を備えることを特徴とするパターン分類装置。
【請求項２】
前記パターン分類手段は、
前記Ｎ個のパターンを、前記類似の度合いに基づいて、1つ以上のパターンを含むパターンクラスタに分類するものであって、
前記各キーワードにつき、２つのパターンの一方に当該キーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＡ、当該２つのパターンの他方に当該キーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＢとして、
類似判定値＝｜Ａ∩Ｂ｜÷｜Ａ∪Ｂ｜
ただし、
Ａ、Ｂが共に空集合でなく、
｜Ａ∩Ｂ｜は、ＡとＢの積集合の中のインスタンス数、
｜Ａ∪Ｂ｜は、ＡとＢの和集合の中のインスタンス数、
を計算した場合、
前記各キーワードに対応する類似判定値の中のｋ個（０＜ｋ≦Ｋ：ただしＫは前記キーワードの個数）以上が所定のしきい値以上となる当該２つのパターンを同一のパターンクラスタに含ませる
ことを特徴とする請求項１記載のパターン分類装置。
【請求項３】
インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースを備えるパターン分類装置が行うパターン分類方法であって、
前記パターン分類装置のグラフ検索手段が、前記グラフ内のサブグラフを検索するためのＮ個のパターンにおける第１ノードに対し、互いに異なるＭ個のキーワードを含ませて、Ｎ×Ｍ個の検索パターンを生成し、前記グラフから前記各検索パターンに合致するサブグラフを検索し、
前記パターン分類装置のパターン分類手段が、前記検索されたサブグラフにおける第２ノード内のインスタンスを使用して前記Ｎ個のパターンにおける２つのパターンからなる組み合わせのそれぞれについて類似の度合いを求め、当該類似の度合いに基づいて前記Ｎ個のパターンを分類する
ことを特徴とするパターン分類方法。
【請求項４】
前記パターン分類手段は、
前記Ｎ個のパターンを、前記類似の度合いに基づいて、1つ以上のパターンを含むパターンクラスタに分類するものであって、
前記各キーワードにつき、２つのパターンの一方に当該キーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＡ、当該２つのパターンの他方に当該キーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＢとして、
類似判定値＝｜Ａ∩Ｂ｜÷｜Ａ∪Ｂ｜
ただし、
Ａ、Ｂが共に空集合でなく、
｜Ａ∩Ｂ｜は、ＡとＢの積集合の中のインスタンス数、
｜Ａ∪Ｂ｜は、ＡとＢの和集合の中のインスタンス数、
を計算した場合、
前記各キーワードに対応する類似判定値の中のｋ個（０＜ｋ≦Ｋ：ただしＫは前記キーワードの個数）以上が所定のしきい値以上となる当該２つのパターンを同一のパターンクラスタに含ませる
ことを特徴とする請求項３記載のパターン分類方法。
【請求項５】
請求項１または２記載のパターン分類装置としてコンピュータを動作させるコンピュータプログラム。
【請求項１】
インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースと、
前記グラフ内のサブグラフを検索するためのＮ個のパターンにおける第１ノードに対し、互いに異なるＭ個のキーワードを含ませて、Ｎ×Ｍ個の検索パターンを生成し、前記グラフから前記各検索パターンに合致するサブグラフを検索するグラフ検索手段と、
前記検索されたサブグラフにおける第２ノード内のインスタンスを使用して前記Ｎ個のパターンにおける２つのパターンからなる組み合わせのそれぞれについて類似の度合いを求め、当該類似の度合いに基づいて前記Ｎ個のパターンを分類するパターン分類手段と
を備えることを特徴とするパターン分類装置。
【請求項２】
前記パターン分類手段は、
前記Ｎ個のパターンを、前記類似の度合いに基づいて、1つ以上のパターンを含むパターンクラスタに分類するものであって、
前記各キーワードにつき、２つのパターンの一方に当該キーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＡ、当該２つのパターンの他方に当該キーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＢとして、
類似判定値＝｜Ａ∩Ｂ｜÷｜Ａ∪Ｂ｜
ただし、
Ａ、Ｂが共に空集合でなく、
｜Ａ∩Ｂ｜は、ＡとＢの積集合の中のインスタンス数、
｜Ａ∪Ｂ｜は、ＡとＢの和集合の中のインスタンス数、
を計算した場合、
前記各キーワードに対応する類似判定値の中のｋ個（０＜ｋ≦Ｋ：ただしＫは前記キーワードの個数）以上が所定のしきい値以上となる当該２つのパターンを同一のパターンクラスタに含ませる
ことを特徴とする請求項１記載のパターン分類装置。
【請求項３】
インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースを備えるパターン分類装置が行うパターン分類方法であって、
前記パターン分類装置のグラフ検索手段が、前記グラフ内のサブグラフを検索するためのＮ個のパターンにおける第１ノードに対し、互いに異なるＭ個のキーワードを含ませて、Ｎ×Ｍ個の検索パターンを生成し、前記グラフから前記各検索パターンに合致するサブグラフを検索し、
前記パターン分類装置のパターン分類手段が、前記検索されたサブグラフにおける第２ノード内のインスタンスを使用して前記Ｎ個のパターンにおける２つのパターンからなる組み合わせのそれぞれについて類似の度合いを求め、当該類似の度合いに基づいて前記Ｎ個のパターンを分類する
ことを特徴とするパターン分類方法。
【請求項４】
前記パターン分類手段は、
前記Ｎ個のパターンを、前記類似の度合いに基づいて、1つ以上のパターンを含むパターンクラスタに分類するものであって、
前記各キーワードにつき、２つのパターンの一方に当該キーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＡ、当該２つのパターンの他方に当該キーワードを含ませた検索パターンに合致する１つ以上のサブグラフにおける第２ノード内のインスタンスの集合をＢとして、
類似判定値＝｜Ａ∩Ｂ｜÷｜Ａ∪Ｂ｜
ただし、
Ａ、Ｂが共に空集合でなく、
｜Ａ∩Ｂ｜は、ＡとＢの積集合の中のインスタンス数、
｜Ａ∪Ｂ｜は、ＡとＢの和集合の中のインスタンス数、
を計算した場合、
前記各キーワードに対応する類似判定値の中のｋ個（０＜ｋ≦Ｋ：ただしＫは前記キーワードの個数）以上が所定のしきい値以上となる当該２つのパターンを同一のパターンクラスタに含ませる
ことを特徴とする請求項３記載のパターン分類方法。
【請求項５】
請求項１または２記載のパターン分類装置としてコンピュータを動作させるコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公開番号】特開２０１１−３９８３８（Ｐ２０１１−３９８３８Ａ）
【公開日】平成２３年２月２４日（２０１１．２．２４）
【国際特許分類】
【出願番号】特願２００９−１８７３７７（Ｐ２００９−１８７３７７）
【出願日】平成２１年８月１２日（２００９．８．１２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年２月２４日（２０１１．２．２４）
【国際特許分類】
【出願日】平成２１年８月１２日（２００９．８．１２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]