(57)【特許請求の範囲】
【請求項１】
コンピュータが、記憶部に記憶されたプログラムをＣＰＵに実行させることにより実現する因果関係要約方法であって、
コンピュータが、
文の集合を入力し、各文をノードとして、前記集合中の２つの文の間に因果関係または前記集合中の２つの文の間の類似度の高さに応じた重みが添えられたエッジを前記ノード間に生成し、
前記ノード及び前記エッジを有する前記グラフデータ中のノード集合を、切断される前記エッジの重みの和が最も小さくなるように、予め指定した数のクラスタに分解し、
各クラスタ内で因果関係を持たないようにノードを統合する縮約処理を実行する
ことを特徴とする因果関係要約方法。
【請求項２】
コンピュータが、
２つの文の間の類似度を記憶部に記憶されたシソーラスを用いて算出する
請求項１記載の因果関係要約方法。
【請求項３】
コンピュータが、
記憶部に記憶された上位語辞書または同義語辞書を用いて、一方の文の単語の上位語または同義語が他方の文に存在するかどうかを調べ、当該他方の文に存在する当該上位語または当該同義語の数に応じた類似度を算出する
請求項２記載の因果関係要約方法。
【請求項４】
コンピュータが、
縮約処理が施されたグラフデータを対象として、当該グラフデータのクラスタ内のノードに共通する単語、または、記憶部に記憶された辞書において当該クラスタ内の単語の共通の上位語のうち最も低い位置にある単語をラベルとして出力する
請求項１から請求項３のうちのいずれか１項に記載の因果関係要約方法。
【請求項５】
文の集合を入力し、各文をノードとして、前記集合中の２つの文の間に因果関係または前記集合中の２つの文の間の類似度の高さに応じた重みが添えられたエッジを前記ノード間に生成するグラフ作成部と、
前記ノード及び前記エッジを有する前記グラフデータ中のノード集合を、切断される前記エッジの重みの和が最も小さくなるように、予め指定した数のクラスタに分解するグラフカット処理部と、
各クラスタ内で因果関係を持たないようにノードを統合する縮約処理を実行するグラフ縮約部とを備えた
ことを特徴とする因果関係要約装置。
【請求項６】
グラフ作成部は、２つの文の間の類似度をシソーラスを用いて算出する
請求項５記載の因果関係要約装置。
【請求項７】
縮約処理が施されたグラフデータを対象として、当該グラフデータのクラスタ内のノードに共通する単語、または、当該クラスタ内の単語の共通の上位語のうち最も低い位置にある単語をラベルとして出力するラベル作成部を備えた
請求項５または請求項６記載の因果関係要約装置。
【請求項８】
記憶部に記憶された因果関係要約プログラムであって、
コンピュータのＣＰＵに、
文の集合を入力し、各文をノードとして、前記集合中の２つの文の間に因果関係または前記集合中の２つの文の間の類似度の高さに応じた重みが添えられたエッジを前記ノード間に生成する処理と、
前記ノード及び前記エッジを有する前記グラフデータ中のノード集合を、切断される前記エッジの重みの和が最も小さくなるように、予め指定した数のクラスタに分解する処理と、
各クラスタ内で因果関係を持たないようにノードを統合する縮約処理と
を実行させるための因果関係要約プログラム。
【請求項９】
コンピュータのＣＰＵに、
２つの文の間の類似度を記憶部に記憶されたシソーラスを用いて算出させる
請求項８記載の因果関係要約プログラム。
【請求項１０】
コンピュータのＣＰＵに、
縮約処理が施されたグラフデータを対象として、当該グラフデータのクラスタ内のノードに共通する単語、または、記憶部に記憶された辞書において当該クラスタ内の単語の共通の上位語のうち最も低い位置にある単語をラベルとして出力させる
請求項８または請求項９記載の因果関係要約プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、因果関係を表現した複数の自然言語文を入力し、複数の因果関係を要約するグラフ構造を出力する因果関係要約方法、因果関係要約装置及び因果関係要約プログラムに関する。
【背景技術】
【０００２】
自然言語には因果関係に関する記述が多く含まれる。因果関係は、一つの文章にまとまっていないことも多く、人間が、ある事象に関する因果関係を把握するためには、複数の文章を注意深く読む必要がある。そこで、人間が複数の文章に含まれる因果関係を把握するために、因果関係をグラフ構造として可視化し要約する装置が開発されている。
【０００３】
例えば、特許文献１には、格フレームを用いて自然言語文の入力文書群から事象を抽出し、事象同士に挟まれた接続詞を手がかりに事象間の因果関係を抽出することが記載されている。さらに、特許文献１に記載された発明によれば、予め因果関係の構成要素となるオブジェクトの階層関係を人手で構築しておくことによって、同一とみなすべき事象をまとめることができる。例えば、自動車の構成部品を「燃料系統」と「電気系統」に分け、さらに「電気系統」の構成要素として「ヘッドライト」「車幅ランプ」という包含関係を事前に階層構造として与えておく。「ヘッドライトの破損」と「車幅ランプの減灯」はいずれも「電気系統の故障」であるとまとめることができる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００４−１２６６４１号公報
【非特許文献】
【０００５】
【非特許文献１】On spectral clustering: Analysis and an algorithm. A. Y. Ng, M. I. Jordan, and Y. Weiss. In T. Dietterich, S. Becker and Z. Ghahramani, Advances in Neural Information Processing Systems (NIPS) 14, 2002.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、特許文献１に記載された発明は、因果関係を考慮したまとめ上げをしていない。そのため、間違った因果関係が生成されてしまう可能性があるという問題点がある。他の一般的な技術においても、予め事象文同士を上位語などでまとめ上げる際に、因果関係を考慮していない。このため、事象文同士をまとめ上げる時点では、事象文間の因果関係を考慮しておらず、間違った粒度のまとめ上げが行われることがあるという問題点がある。
【０００７】
上記の問題点を、図１０の因果関係データの例を用いて説明する。図１０は、因果関係データの例を示す説明図である。図１０には、４つの原因文と４つの結果文の例が示されている。各行が、１つの因果関係を表す。このとき、結果文Ｒ１〜Ｒ４をまとめ上げることを考える。４つの結果文をどこまでまとめ上げるかは固定的ではない。例えば、Ｒ１〜Ｒ４を一つのまとまりとし、「家電の売上げが上昇」という意味粒度でまとめ上げてもよい。または、Ｒ１とＲ２のみをまとめ「エアコンの売上げが上昇」「扇風機の売上げが上昇」「液晶ＴＶの売上げが上昇」の三つのまとまりを作ってもよい。また、Ｒ１〜Ｒ３をまとめて、「冷房機器の売上げが上昇」と「液晶ＴＶの売上げが上昇」という２つのまとまりを作ってもよい。これらのまとめ上げのどれが正しいかは不明である。
【０００８】
図１１は、一般的手法による間違ったグラフ要約結果の例を示す説明図である。図１１は、図１０に示すデータに基づいてＲ１〜Ｒ４をまとめ上げ、Ｃ１〜Ｃ３がまとめ上げた例を示す図である。図１１には、「平均気温が高い」と「家電の売上げが上昇する」という関係と、「ワールドカップが開催される」と「家電の売上げが上昇する」という関係が示されている。しかし、これらの因果関係は正しい因果関係ではない。「平均気温が上昇する」こと、または、「ワールドカップが開催される」こと、によってすべての家電の売上げが上昇するとは言えないためである。
【０００９】
本発明は、原因文と結果文との複数の組が与えられた場合に、原因文や結果文をまとめ上げる際に、精度の高い因果関係を生成できる因果関係要約方法、因果関係要約装置及び因果関係要約プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明による因果関係要約方法は、コンピュータが、記憶部に記憶されたプログラムをＣＰＵに実行させることにより実現する因果関係要約方法であって、コンピュータが、文の集合を入力し、各文をノードとして、前記集合中の２つの文の間に因果関係または前記集合中の２つの文の間の類似度の高さに応じた重みが添えられたエッジを前記ノード間に生成し、前記ノード及び前記エッジを有する前記グラフデータ中のノード集合を、切断される前記エッジの重みの和が最も小さくなるように、予め指定した数のクラスタに分解し、各クラスタ内で因果関係を持たないようにノードを統合する縮約処理を実行することを特徴とする。
【００１１】
また、本発明による因果関係要約装置は、文の集合を入力し、各文をノードとして、前記集合中の２つの文の間に因果関係または前記集合中の２つの文の間の類似度の高さに応じた重みが添えられたエッジを前記ノード間に生成するグラフ作成部と、前記ノード及び前記エッジを有する前記グラフデータ中のノード集合を、切断される前記エッジの重みの和が最も小さくなるように、予め指定した数のクラスタに分解するグラフカット処理部と、各クラスタ内で因果関係を持たないようにノードを統合する縮約処理を実行するグラフ縮約部とを備えたことを特徴とする。
【００１２】
また、本発明による因果関係要約プログラムは、記憶部に記憶された因果関係要約プログラムであって、コンピュータのＣＰＵに、文の集合を入力し、各文をノードとして、前記集合中の２つの文の間に因果関係または前記集合中の２つの文の間の類似度の高さに応じた重みが添えられたエッジを前記ノード間に生成する処理と、前記ノード及び前記エッジを有する前記グラフデータ中のノード集合を、切断される前記エッジの重みの和が最も小さくなるように、予め指定した数のクラスタに分解する処理と、各クラスタ内で因果関係を持たないようにノードを統合する縮約処理とを実行させる。
【発明の効果】
【００１３】
本発明によれば、原因文と結果文との複数の組が与えられた場合に、原因文や結果文をまとめ上げる際に、精度の高い因果関係を生成することができる。
【図面の簡単な説明】
【００１４】
【図１】本発明による因果関係要約装置の実施形態の構成を示すブロック図である。
【図２】本発明による因果関係要約装置の実施形態の処理手順を示すフローチャートである。
【図３】概念辞書の例を示す説明図である。
【図４】統合グラフ作成部が出力する行列データの例を示す説明図である。
【図５】統合グラフ作成部の出力結果の一例を示すグラフ図である。
【図６】グラフ縮約部の処理の一部の処理手順を示すフローチャートである。
【図７】グラフ縮約部の出力結果の１つ目の例を示すグラフ図である。
【図８】グラフ縮約部の出力結果の２つ目の例を示すグラフ図である。
【図９】ラベル作成部が出力するグラフ要約結果の例を示す説明図である。
【図１０】因果関係データの例を示す説明図である。
【図１１】一般的手法による間違ったグラフ要約結果の例を示す説明図である。
【発明を実施するための形態】
【００１５】
実施形態．
図１は、本発明による因果関係要約装置の実施形態の構成を示すブロック図である。本実施形態の因果関係要約装置は、統合グラフ作成部１、グラフカット処理部２、グラフ縮約部３及びラベル作成部４を有する。
【００１６】
統合グラフ作成部１は、因果関係を持つ原因文と結果文の集合である因果関係データ５を入力する。そして、統合グラフ作成部１は、入力した因果関係データ５の各文をノードとし、ノード間に、２文間に因果関係がある場合と、または文間に高い類似性がある場合に、因果関係又は類似度の高さに応じた重みが添えられたエッジを作成することで統合グラフを作成する。また、類似度の算出において、例えば、後述する概念辞書６を用いる。
【００１７】
グラフカット処理部２は、統合グラフ作成部１によって作成された統合グラフを入力する。そして、グラフカット処理部２は、入力した統合グラフ中のノード集合を、予め指定した数（Ｋ個）のクラスタに分解するグラフカットを行い、ノードについて作成されたＫ個のクラスタと統合グラフを出力する。このグラフカットは、切断されるエッジの重みの和が小さくなるように行われる。
【００１８】
グラフ縮約部３は、グラフカット処理部が出力したＫ個のクラスタと統合グラフのデータを入力する。そして、グラフ縮約部３は、Ｋ個の各クラスタ内において、因果関係を持たないように複数のノードを結合する縮約処理を行い、縮約グラフを出力する。
【００１９】
ラベル作成部４は、グラフ縮約部３により縮約されたグラフデータ、原因文と結果文の集合である因果関係データ５、および概念辞書６を入力し、各ノードに対応するラベルを生成する。
【００２０】
次に、本実施形態の因果関係要約装置の処理手順をフローチャートを用いて説明する。図２は、本発明による因果関係要約装置の実施形態の処理手順を示すフローチャートである。
【００２１】
まず、統合グラフ作成部１に因果関係データが入力されると、統合グラフ作成部１は、因果関係データ内の各文をノードとするグラフを表現した行列データＧの初期化を行う（ステップＳ０１）。行列データＧは、因果関係データ内の全文数をｎとする場合にｎ行ｎ列のサイズを持つ行列で表現される。ｉ行ｊ列目の要素ｇ（ｉ，ｊ）は、文ｉと文ｊの間のエッジを表現しており、エッジが無い場合を０、エッジがある場合にはその重みを表現した値を持つ。ステップＳ０１では、すべての値が０である行列データＧが生成される。
【００２２】
次に、統合グラフ作成部１は、因果関係データ内において因果関係が存在する２文を順に読み込み、エッジを作成する（ステップＳ０２）。この処理では、行列データＧに対して、文ｉと文ｊの間に因果関係がある場合、ｇ（ｉ，ｊ）＝１が代入される。
【００２３】
次に、統合グラフ作成部１は、因果関係データ内から因果関係の無い任意の二文を抽出し、類似度を計算し、その二文の類似度が予め設定された閾値αより大きい場合に、その二文間にエッジを作成する（ステップＳ０３）。または、ステップＳ０３において、全ての文間の類似度のうち、類似度が高い上位Ｎ個（Ｎは予め定めた値とする）の文間にエッジを作成してもよい。
【００２４】
類似度の算出方法を、具体的に説明する。文ｘ、文ｙの間の類似度は、例えば、次の計算式（１）によって計算される。
Ｓｉｍ（ｘ，ｙ）＝｜Ｗ（ｘ）∧Ｗ（ｙ）｜／｜Ｗ（ｘ）∨Ｗ（ｙ）｜  ・・・式（１）
式（１）において、Ｗ（ｚ）は文ｚに含まれる単語の集合を意味する。また、単語とは、文に対し、形態素解析処理やＮグラムの切り出しなどにより得られる文内の部分文字列を意味する。よって｜Ｗ（ｘ）∧Ｗ（ｙ）｜は、文ｘと文ｙに共通して登場する単語の数を意味し、｜Ｗ（ｘ）∨Ｗ（ｙ）｜は文ｘまたは文ｙに登場する単語の数を意味する。なお、例えば同義語辞書を用いて、異なる単語であっても同義であれば同じ単語であるとみなし、上記の計算を行ってもよい。
【００２５】
また、文間の類似度を計算する際に、例えば、シソーラスなどの単語の概念辞書６を用いる。図３は、概念辞書６の例を示す説明図である。図３に示す概念辞書６は、単語の意味の包含関係を定義した辞書を示しており、各楕円が単語、楕円間の矢印が包含関係を表現している。図３に示す関係から、例えば、エアコンおよび扇風機は冷房機器の一つであり、冷房機器は家電の一つであるという関係が読み取れる。また、液晶ＴＶはＡＶ機器の一つであり、ＡＶ機器は家電の一つであるという関係が読み取れる。
【００２６】
このような単語の包含関係を用いた文間の類似度Ｓｉｍ’（ｘ，ｙ）の計算方法は、次の式（２）のように表される。
Ｓｉｍ’（ｘ，ｙ）＝（Ｓｉｍ（ｘ，ｙ）＋｜Ａ（ｘ）∧Ａ（ｙ）｜／｜Ａ（ｘ）∨Ａ（ｙ）｜）／２  ・・・式（２）
式（２）において、Ａ（ｚ）は文ｚ内に登場する単語の、概念辞書上の先祖（矢印方向に繰り返し辿ることで到達できる単語）の集合を意味する。
【００２７】
統合グラフ作成部１は、類似度Ｓｉｍ（ｘ，ｙ）または類似度Ｓｉｍ’（ｘ，ｙ）が、例えば、予め定めた閾値αより大きい場合に行列データＧのｇ（ｘ，ｙ）にその類似度を設定する。図４は、統合グラフ作成部１が出力する行列データの例を示す説明図である。図５は、統合グラフ作成部１の出力結果の一例を示すグラフ図である。図５において、各楕円は各文を表すノードを表し、楕円間の線はエッジを表し、エッジに添えられた数はエッジの重みを表している。
【００２８】
図４に示す値は、式（２）を用いた計算によって導かれた値である。一例として、図３を参照して、Ｓｉｍ’（Ｒ１，Ｒ３）及びＳｉｍ’（Ｒ１，Ｒ４）の計算を説明する。
【００２９】
Ｓｉｍ’（Ｒ１，Ｒ３）は、以下のように計算される。Ｒ１，Ｒ３に含まれる単語Ｗ（Ｒ１），Ｗ（Ｒ３）は、形態素解析を行い名詞を抽出する処理により、下記のように抽出される。
Ｗ（Ｒ１）＝｛エアコン，売上げ，上昇｝
Ｗ（Ｒ３）＝｛扇風機，売上げ，上昇｝
これより、
Ｗ（Ｒ１）∧Ｗ（Ｒ３）＝｛売上げ，上昇｝
Ｗ（Ｒ１）∨Ｗ（Ｒ３）＝｛エアコン，扇風機，売上げ，上昇｝
であるため、
Ｓｉｍ（Ｒ１，Ｒ３）＝２／４＝１／２
となる。
【００３０】
図３に示す例では、先祖ノードＡ（Ｒ１），Ａ（Ｒ３）は、
Ａ（Ｒ１）＝Ａ（Ｒ３）＝｛冷房機器，家電｝
である。また、
｜Ａ（ｘ）∧Ａ（ｙ）｜／｜Ａ（ｘ）∨Ａ（ｙ）｜＝１
となる。
以上より、
Ｓｉｍ’（Ｒ１，Ｒ３）＝（１／２＋１）／２＝０．７５（＝約０．８）となる。
【００３１】
Ｓｉｍ’（Ｒ１，Ｒ４）は、以下のように計算される。Ｒ４に含まれる語句Ｗ（Ｒ４）は、
Ｗ（Ｒ４）＝｛液晶ＴＶ，売上げ，上昇｝
である。
これより、
Ｗ（Ｒ１）∧Ｗ（Ｒ４）＝｛売上げ，上昇｝
Ｗ（Ｒ１）∨Ｗ（Ｒ４）＝｛エアコン，液晶ＴＶ，売上げ，上昇｝
である。よって、
Ｓｉｍ（Ｒ１，Ｒ４）＝２／４＝１／２
となる。
【００３２】
図３に示す例では、先祖ノードＡ（Ｒ１），Ａ（Ｒ４）は、それぞれ、
Ａ（Ｒ１）＝｛冷房機器，家電｝
Ａ（Ｒ４）＝｛ＡＶ機器，家電｝
である。また、
Ａ（Ｒ１）∧Ａ（Ｒ４）＝｛家電｝
Ａ（Ｒ１）∨Ａ（Ｒ４）＝｛冷房機器，ＡＶ機器，家電｝
である。よって、
｜Ａ（ｘ）∧Ａ（ｙ）｜／｜Ａ（ｘ）∨Ａ（ｙ）｜＝１／３となる。
以上より、
Ｓｉｍ’（Ｒ１，Ｒ４）＝（１／２＋１／３）／２＝５／１２（＝約０．４）
となる。
【００３３】
なお、シソーラスのうち、上位語辞書を用いてＳｉｍ’（ｘ，ｙ）の類似度計算が行われたが、同義語辞書を用いて類似度計算を行ってもよい。同義語辞書は、各単語について同義の語を定義したものである。例えば、「エアコン」について、「エアーコンディショナー」、「Ａｉｒ  Ｃｏｎｄｉｔｉｏｎｅｒ」、「クーラー」などの語が記載される。例えば、同義語を用いた計算式の例としては次の式が挙げられる。
Ｓｉｍ＿ｓｙｎｏｎｙｍ（ｘ，ｙ）＝｜Ｓ（ｘ）∧Ｓ（ｙ）｜／｜Ｓ（ｘ）∨Ｓ（ｙ）｜  ・・・式（３）
Ｓ（ｘ）は、文ｘに含まれる単語について同義語辞書から得られる同義語の集合である。また、同義語辞書と上位語辞書とを併用してもよい。
【００３４】
次に、グラフカット処理部２は、統合グラフ作成部１が作成した行列データＧを元に、グラフを予め定められた数（Ｋ個）に分解するグラフカット処理を行う（ステップＳ０４）。グラフカット処理は、グラフ中のノードをＫ個に分ける処理である。グラフカット処理として、例えば、非特許文献１のSpectralClusteringアルゴリズムを用いることができる。SpectralClusteringアルゴリズムは、次のようにグラフ分割処理を行う。
【００３５】
１．行列データＧより、次数行列Ｄを求める。
次数行列Ｄとは対角行列であり、各ｉ行ｉ列目の要素Ｄ（ｉ，ｉ）が文ｉの次数（エッジの数）になっている行列である。Ｄ（ｉ，ｉ）は、行列データＧのｉ行目の非ゼロ要素の数を数えることによって計算される。
【００３６】
２．分解用行列Ｘを計算する。
Ｘは、次の式（４）によって計算される行列である。
Ｘ＝Ｉ−Ｄ−１／２ＧＤ−１／２  ・・・式（４）
式（４）において、Ｉは単位行列を示す。因果関係データ内の全文数をｎとした場合、Ｉは、ｎ行ｎ列の単位行列となる。
【００３７】
３．行列Ｘに対して、Ｋ個の固有値と固有ベクトルを計算する。
【００３８】
４．固有値が０以外の値を持つＫ−１個の固有ベクトルを元に、各文に対してＫ−１次元の縮約ベクトルＹを作成する。文ｉの縮約ベクトルＹｉはＫ−１個の固有ベクトルのｉ番目の値の要素を持つベクトルである。
【００３９】
５．文の集合を縮約ベクトルＹを用いてクラスタリングする。クラスタリング手法として、例えばＫ−ｍｅａｎｓ法を用いる。そして、クラスタリングした結果得られた文のクラスタを出力する。
【００４０】
SpectralClusteringアルゴリズムは、グラフを分割する際に、疎なエッジ（重みが少ないエッジ）を切断するアルゴリズムである。このため、クラスタ間に因果関係や類似度を示すエッジが少なく、クラスタ内に因果関係や類似度を示すエッジが多く含まれるように、統合グラフをＫ個に分解することが可能である。
【００４１】
グラフカット処理部２は、Ｋ個のノードのリストを出力する。例えば、図４に示すデータを元にＫ＝４として分割したノードのリストは、｛Ｃ１，Ｃ２，Ｃ３｝、｛Ｃ４｝、｛Ｒ１，Ｒ２，Ｒ３｝、｛Ｒ４｝の４つのリストになる。また、Ｃ１，Ｃ２，Ｃ３とＲ１，Ｒ２との間に因果関係があるので、｛Ｃ１，Ｃ２，Ｃ３，Ｒ１，Ｒ２｝、｛Ｃ４｝、｛Ｒ３｝、｛Ｒ４｝の４つのリストになる場合がある。
【００４２】
いずれの場合であっても、グラフカット処理部２の出力したリスト内には同一内容のノード、所定の条件を満たし類似するノード又は因果関係のあるノードしか含まれないので、例えば｛Ｃ１，Ｃ２，Ｃ３，Ｒ１，Ｒ２，Ｒ３，Ｒ４｝というような間違ったまとめ上げがされることはない。
【００４３】
次に、グラフ縮約部３は、グラフカット処理部２が出力したノードのリストを元にグラフの縮約処理を行う（ステップＳ０５）。グラフの縮約処理は、グラフカット処理部２が出力したノードのリストを調べ、因果関係を持たないノード同士をまとめ上げる処理である。ここでは、あるリストｌｉｓｔ内にＭ個のノードが含まれるとして、グラフの縮約処理の処理手順を説明する。
【００４４】
グラフ縮約部３は、まず、入力のリスト内に因果関係が一つでもあるかどうかを調べる。因果関係が一つも無い場合、そのリストを一つのクラスタとしてそのまま出力する。例えば、入力のリストが｛Ｃ１，Ｃ２，Ｃ３｝である場合、これらは一つにまとめられるため、｛Ｃ１−Ｃ２−Ｃ３｝が一つのノードとしてまとめられるべきとして出力される。
【００４５】
図６は、グラフ縮約部３の処理の一部の処理手順を示すフローチャートである。図６を参照し、因果関係が一つでもある場合の処理の手順を説明する。グラフ縮約部３は、まずＭ個のｂｕｆｆｅｒ配列を空の状態に初期化して、変数Ｐを０で初期化する（ステップＳ０５１）。次に、ｌｉｓｔ内が空であるかどうかを調べる（ステップＳ０５２）。空である場合、グラフ縮約部３は、その時点でのｂｕｆｆｅｒ配列を調べ、空でないｂｕｆｆｅｒをクラスタとして出力する（ステップＳ０５３）。
【００４６】
ｌｉｓｔ内が空でない場合、グラフ縮約部３は、ｌｉｓｔから先頭のノードを取り出し、ｘとする（ステップＳ０５４）。さらに、グラフ縮約部３は、ｂｕｆｆｅｒ配列の０番目からＰ−１番目を調べ、ｘが因果関係を持たないｂｕｆｆｅｒを探す（ステップＳ０５５）。そのようなｂｕｆｆｅｒが見つかった場合には、グラフ縮約部３は、そのｂｕｆｆｅｒにノードを追加する（ステップＳ０５６）。その後、ステップＳ０５２に戻る。
【００４７】
ステップＳ０５５において、ｘが因果関係を持たないｂｕｆｆｅｒがもし見つからない場合には、グラフ縮約部３は、Ｐ番目のｂｕｆｆｅｒに新たにｘを追加し、Ｐを１増加させる（ステップＳ０５７）。その後、処理Ｓ０５２に戻る。
【００４８】
図６に示されるグラフ縮約部３の処理を、具体例を用いて説明する。例えば、｛Ｃ１，Ｃ２，Ｃ３，Ｒ１，Ｒ２｝がｌｉｓｔ内にある場合、ステップＳ０５２において、ｌｉｓｔは空ではないと判定されるので、ステップＳ０５４に進む。そして、ステップＳ０５４において、ｌｉｓｔからＣ１が取り出されｘとされる。Ｐ＝０であるため、ステップＳ０５５及びＳ０５６の処理がスキップされる。そして、ステップＳ０５７でｂｕｆｆｅｒ［０］にｘ（Ｃ１）が追加され、Ｐ＝１となる。
【００４９】
ステップＳ０５２に戻り、ｌｉｓｔは空ではないので、ステップＳ０５４に進み、ｌｉｓｔからＣ２が取り出されｘとされる。そして、ステップＳ０５５の判定において、ｘ（Ｃ２）がｂｕｆｆｅｒ［０］内の全ノード（Ｃ１）と因果関係がないと判定され、ｂｕｆｆｅｒ［０］にｘ（Ｃ２）が追加されて（ステップＳ０５６）、ｂｕｆｆｅｒ［０］が｛Ｃ１，Ｃ２｝となる。
【００５０】
ステップＳ０５２に戻り、ｌｉｓｔは空ではないので、ステップＳ０５４に進み、ｌｉｓｔからＣ３が取り出されｘとされる。そして、ステップＳ０５５の判定において、ｘ（Ｃ３）がｂｕｆｆｅｒ［０］内の全ノード（Ｃ１，Ｃ２）と因果関係がないと判定され、ｂｕｆｆｅｒ［０］にｘ（Ｃ３）が追加されて（ステップＳ０５６）、ｂｕｆｆｅｒ［０］が｛Ｃ１，Ｃ２，Ｃ３｝となる。
【００５１】
ステップＳ０５２に戻り、ｌｉｓｔは空ではないので、ステップＳ０５４に進み、ｌｉｓｔからＲ１が取り出されｘに代入される。そして、ステップＳ０５５では、ｘ（Ｒ１）がｂｕｆｆｅｒ［０］内の全ノード（Ｃ１，Ｃ２，Ｃ３）と因果関係があると判定され、ステップＳ０５７に進む。ステップＳ０５７でｂｕｆｆｅｒ［１］にｘ（Ｒ１）が追加され、Ｐ＝１であるので、Ｐに１加算されてＰ＝２となる。この時点で、ｂｕｆｆｅｒ［０］が｛Ｃ１，Ｃ２，Ｃ３｝であり、ｂｕｆｆｅｒ［１］が｛Ｒ１｝となる。
【００５２】
ステップＳ０５２に戻り、ｌｉｓｔは空ではないので、ステップＳ０５４に進み、ｌｉｓｔからＲ２が取り出されｘとされる。そして、ステップＳ０５５の判定において、ｘ（Ｒ２）がｂｕｆｆｅｒ［１］内の全ノード（Ｒ１）と因果関係がないと判定され、ｂｕｆｆｅｒ［１］にｘ（Ｒ２）が追加される。（ステップＳ０５６）。この時点で、ｂｕｆｆｅｒ［０］が｛Ｃ１，Ｃ２，Ｃ３｝であり、ｂｕｆｆｅｒ［１］が｛Ｒ１，Ｒ２｝となる。
【００５３】
ステップＳ０５２に戻り、ｌｉｓｔは空となっているので、ステップＳ０５３に進み、ｂｕｆｆｅｒ［０］に格納されている｛Ｃ１，Ｃ２，Ｃ３｝と、ｂｕｆｆｅｒ［１］に格納されている｛Ｒ１，Ｒ２｝が出力される。
【００５４】
このように、｛Ｃ１，Ｃ２，Ｃ３，Ｒ１，Ｒ２｝内のまとめ上げでは、Ｃ１とＲ１との間に因果関係があり、Ｃ２とＲ２の間に因果関係があるため、｛Ｃ１−Ｃ２−Ｃ３｝と、｛Ｒ１−Ｒ２｝の２つのクラスタが出力される。これにより、各クラスタ内には因果関係のないノードのみが統合された状態となる。
【００５５】
さらに、グラフ縮約部３は、統合グラフ作成部１が作成したグラフデータを入力し、グラフデータの因果関係に基づき、クラスタ間のエッジを出力する。クラスタ間のエッジは、次の手順により作成される。クラスタＡ内の任意のノードとクラスタＢ内の任意のノードが因果関係を持つ場合、グラフ縮約部３は、クラスタＡとクラスタＢとの間にエッジを作成する。
【００５６】
図７は、グラフ縮約部３の出力結果の１つ目の例を示すグラフ図である。例えば、グラフ縮約部３が｛Ｃ１，Ｃ２，Ｃ３｝、｛Ｃ４｝、｛Ｒ１，Ｒ２，Ｒ３｝、｛Ｒ４｝の４つのリストを入力する。この場合、グラフ縮約部３は、図６に示した処理において、Ｃ１−Ｃ２−Ｃ３、Ｃ４、Ｒ１−Ｒ２−Ｒ３、Ｒ４の四つのクラスタを出力する。さらに、グラフ縮約部３は、クラスタ間のエッジとして、クラスタＣ１−Ｃ２−Ｃ３からクラスタＲ１−Ｒ２−Ｒ３へのエッジと、クラスタＣ４からクラスタＲ４へのエッジを作成する。図７に示すグラフは、この結果をグラフで表現したものである。
【００５７】
図８は、グラフ縮約部３の出力結果の２つ目の例を示すグラフ図である。例えば、グラフ縮約部３が｛Ｃ１，Ｃ２，Ｃ３，Ｒ１，Ｒ２｝、｛Ｃ４｝、｛Ｒ３｝、｛Ｒ４｝の４つのリストを入力する。この場合、｛Ｃ１，Ｃ２，Ｃ３，Ｒ１，Ｒ２｝内のまとめ上げ処理では、Ｃ１とＲ１との間に因果関係があり、Ｃ２とＲ２との間に因果関係があるため、Ｃ１−Ｃ２−Ｃ３と、Ｒ１−Ｒ２の２つのクラスタが生成される。よって、この四つのリストからＣ１−Ｃ２−Ｃ３、Ｒ１−Ｒ２、Ｃ４、Ｒ３、Ｒ４の５つのクラスタが作成される。さらに、グラフ縮約部３は、クラスタ間のエッジとして、クラスタＣ１−Ｃ２−Ｃ３からクラスタＲ１−Ｒ２及びＲ３へのエッジと、クラスタＣ４からクラスタＲ４へのエッジを作成する。図８に示すグラフは、この結果をグラフで表現したものである。
【００５８】
最後に、ラベル作成部４は、グラフ縮約部３により作成されたクラスタと因果関係データ５とを元に各クラスタのラベルを作成する（図２のステップＳ０６）。ラベルの作成は、クラスタ内の各文に対して形態素解析などで名詞や自立語を抽出した上で、クラスタ内の文に共通して登場する語、または概念辞書６のシソーラス上の先祖ノードを取り出すことで行われる。
【００５９】
ラベル作成部４は、グラフ縮約部３により作成されたクラスタ内の複数のノード内に、共通する単語があれば、それをラベルとして出力する。また、単語の包含関係を示す概念辞書を用いて、当該クラスタ内の単語の共通の上位語があれば、その上位後のうち、より低い位置にある単語をラベルとして出力する。
【００６０】
図９は、ラベル作成部４が出力するグラフ要約結果の例を示す説明図である。図９に示す要約結果は、図７に示されたグラフ構造に基づくものである。例えば、ラベル作成部４は、Ｃ１−Ｃ２−Ｃ３で構成されるクラスタに対して、共通する単語を用いて「平均気温、高い」というラベルを生成する。また、ラベル作成部４は、Ｒ１−Ｒ２−Ｒ３で構成されるクラスタに対して、共通の上位語である「冷房機器」と、共通の単語である「売上げ、上昇」とを用いて、「冷房機器、売上げ、上昇」というラベルを生成する。また、ラベル作成部４は、Ｃ４で構成されるクラスタに対して、「ワールドカップ、開催」というラベルを生成する。また、ラベル作成部４は、Ｒ４で構成されるクラスタに対して、「液晶ＴＶ、売上げ、上昇」というラベルを生成する。なお、仮に、Ｒ１−Ｒ２でクラスタが構成された場合、ラベル作成部４は、共通の単語を用いて「エアコン、売上げ、上昇」というラベルを生成する。
【００６１】
次に、本実施形態の因果関係要約装置を実現する具体的なハードウェア構成例を説明する。本実施形態の因果関係要約装置を実現するハードウェア構成は、例えば、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、主記憶部、出力部、入力部及び補助記憶部を含む構成である。主記憶部は、例えばＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）等のメインメモリであって、データの作業領域やデータの一時退避領域として用いられる。出力部は、例えば液晶ディスプレイ装置等の表示装置、又はプリンタ等の印刷装置であり、データを出力する機能を有する。入力部は、例えばキーボードやマウス等の入力デバイスであり、データを入力する機能を有する。補助記憶部は、例えばＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）やハードディスク装置等である。
【００６２】
補助記憶部は、統合グラフ作成部１、グラフカット処理部２、グラフ縮約部３及びラベル作成部をそれぞれ実現するプログラム、因果関係データ５、並びに概念辞書６を記憶する。入力部は、各プログラム、因果関係データ５及び概念辞書６等を入力するために用いられる。ＣＰＵは、各プログラムを実行する際に、主記憶部に一時的にプログラムを読み込み、主記憶部内の各プログラムを実行することで上記の処理を実現する。そして、出力部は、各プログラムの処理結果を出力する。
【００６３】
次に、具体的な実施例を用いて本実施形態の因果関係要約装置の動作を説明する。因果関係データとして図１０に示す例を用いる。図１０に示す因果関係データが統合グラフ作成部１に入力されると、統合グラフ作成部１は、その因果関係に基づき、Ｃ１とＲ１の間のエッジ、Ｃ２とＲ２の間のエッジ、Ｃ３とＲ３の間のエッジおよびＣ４とＲ４の間のエッジを生成する。さらに、統合グラフ作成部１は、これらの８つの文間の類似度を計算し、類似度に応じてノード間にエッジを作成する。また、各エッジには因果関係又は類似度の高さに応じた重みが添えられる。統合グラフ作成部１が出力するグラフの例は、図５に示されている。また、このグラフを表現した行列データは、図４に示されている。
【００６４】
次に、グラフカット処理部２は、図４に示すデータを元に、切断されるエッジの重みの和が小さくなるようグラフを分割するグラフカット処理を行う。クラスタの個数としてＫ＝４が設定されている場合、グラフカット処理部２は、グラフを４つに分割することにより、｛Ｃ１，Ｃ２，Ｃ３｝、｛Ｃ４｝、｛Ｒ１，Ｒ２，Ｒ３｝、｛Ｒ４｝の４つのクラスタを出力する。
【００６５】
次に、グラフ縮約部３は、｛Ｃ１，Ｃ２，Ｃ３｝、｛Ｃ４｝、｛Ｒ１，Ｒ２，Ｒ３｝、｛Ｒ４｝の４つのクラスタを元にグラフの縮約を行う。この例では、グラフ縮約部３は、入力したクラスタをそのままＣ１−Ｃ２−Ｃ３、Ｃ４、Ｒ１−Ｒ２−Ｒ３、Ｒ４の四つのクラスタに変換する。また、グラフ縮約部３は、｛Ｃ１，Ｃ２，Ｃ３，Ｒ１，Ｒ２｝、｛Ｃ４｝、｛Ｒ３｝、｛Ｒ４｝の４つのクラスタを入力した場合であっても図６に示す処理により、Ｃ１−Ｃ２−Ｃ３、Ｃ４、Ｒ１−Ｒ２−Ｒ３、Ｒ４の四つのクラスタに変換する。これにより、クラスタ内に因果関係を持つノードが存在しない状態となる。
【００６６】
さらに、グラフ縮約部３は、クラスタ間のエッジとして、クラスタＣ１−Ｃ２−Ｃ３からクラスタＲ１−Ｒ２−Ｒ３へのエッジと、クラスタＣ４からクラスタＲ４へのエッジを作成する。この結果をグラフで表現すると、図７に示すように表現される。
【００６７】
最後にラベル作成部４は、これらの４つのクラスタに対して、因果関係データ５と概念辞書６とを参照することで、下記の４つのラベルを作成する。
・Ｃ１−Ｃ２−Ｃ３："平均気温、高い"
・Ｃ４："ワールドカップ、開催"
・Ｒ１−Ｒ２−Ｒ３："冷房機器、売上げ、上昇"
・Ｒ４："液晶ＴＶ、売上げ、上昇"
以上の処理により、ラベル作成部４は、図９に示すグラフ要約結果を出力する。
【００６８】
本実施形態の因果関係要約装置は、類似度のエッジと因果関係のエッジを組み合わせた統合グラフを作成し、類似度及び因果関係を考慮したグラフカット処理と因果関係を考慮した縮約処理を行う。そのため、類似度と因果関係をまとめて扱うことができ、因果関係が強く、類似度の高い部分を全体最適化の観点でまとめ上げることができる。また、原因文が似た結果文や結果文が似た原因文をうまくまとめ上げることができ、その結果、要約結果に誤った因果関係が生成されにくい。
【００６９】
なお、上記の各実施形態では、以下の（１）から（３）に示すような因果関係要約装置も開示されている。
【００７０】
（１）文の集合中の２つの文の間の類似度をシソーラスを用いて算出する因果関係要約装置。
【００７１】
（２）因果関係要約装置において、予め用意された上位語辞書または同義語辞書（例えば、概念辞書６）を用いて、一方の文の単語の上位語または同義語が他方の文に存在するかどうかを調べ、当該他方の文に存在する当該上位語または当該同義語の数に応じた類似度を算出するように構成されていてもよい。
【００７２】
（３）因果関係要約装置において、縮約処理が施されたグラフデータを対象として、当該グラフデータのクラスタ内のノードに共通する単語、または、当該クラスタ内の単語の共通の上位語のうち最も低い位置にある単語をラベルとして出力するラベル作成部（例えば、ラベル作成部４）を備えるように構成されていてもよい。
【産業上の利用可能性】
【００７３】
本発明によれば、故障診断などの原因を検索するような作業を行う際に、ユーザに文書集合のグラフ要約を提供することができ、ユーザの情報探索作業を効率化することができる。
【符号の説明】
【００７４】
１  統合グラフ作成部
２  グラフカット処理部
３  グラフ縮約部
４  ラベル作成部
５  因果関係データ
６  概念辞書
【図１】
0005834883.tif 000002
【図２】
0005834883.tif 000003
【図３】
0005834883.tif 000004
【図４】
0005834883.tif 000005
【図５】
0005834883.tif 000006
【図６】
0005834883.tif 000007
【図７】
0005834883.tif 000008
【図８】
0005834883.tif 000009
【図９】
0005834883.tif 000010
【図１０】
0005834883.tif 000011
【図１１】
0005834883.tif 000012