(57)【特許請求の範囲】
【請求項１】
カテゴリに属する文書を記憶する文書カテゴリ記憶手段と、パス検索手段と、結果出力手段とを有し、カテゴリに属する文書間に張られたハイパーリンクをたどって起点となる文書から終点となる文書にたどり着くパスを求める経路探索装置の経路探索方法であって、
前記パス検索手段が行う、ハイパーリンクに重みを付与し、ハイパーリンクの重みの値を用いて、重みつき有向グラフを経路探索し、前記起点となる文書から前記終点となる文書にいたるパスを求めるパス検索過程と、
前記結果出力手段が行う、前記パス検索過程で得たパスを出力する結果出力過程と、からなり、
前記ハイパーリンクの重みは、
リンク元文書のカテゴリの特徴ベクトルとリンク先文書のカテゴリの特徴ベクトルとによる類似度である関連度と、リンク先文書のカテゴリの特徴ベクトルとリンク先文書の特徴ベクトルとによる類似度である適合度と、の乗算によるものである
ことを特徴とする経路探索方法。
【請求項２】
前記リンク先文書が複数のカテゴリに属しているとき、前記経路探索において用いる前記ハイパーリンクの重みの算出において、リンク先文書が属するカテゴリ毎に算出されるそれぞれの重みのうち最大の重みの値を用いる
ことを特徴とする請求項１に記載の経路探索方法。
【請求項３】
カテゴリに属する文書間に張られたハイパーリンクをたどって起点となる文書から終点となる文書にたどり着くパスを求める経路探索装置であって、
前記カテゴリに属する文書を記憶する文書カテゴリ記憶手段と、
前記ハイパーリンクで張られたリンク元文書のカテゴリの特徴ベクトルとリンク先文書のカテゴリの特徴ベクトルとによる類似度である関連度と、リンク先文書のカテゴリの特徴ベクトルとリンク先文書の特徴ベクトルとによる類似度である適合度と、の乗算により、前記ハイパーリンクの重みを算出する重み算出手段と、
前記ハイパーリンクの重みの値を用いて、重みつき有向グラフを経路探索し、前記起点となる文書から前記終点となる文書にいたるパスを求めるパス検索手段と、
前記パス検索過程で得たパスを出力する結果出力手段と、
を備えることを特徴とする経路探索装置。
【請求項４】
前記パス検索手段は、前記リンク先文書が複数のカテゴリに属しているとき、前記経路探索において用いる前記ハイパーリンクの重みの算出において、リンク先文書が属するカテゴリ毎に算出されるそれぞれの重みのうち最大の重みの値を用いる
ことを特徴とする請求項３に記載の経路探索装置。
【請求項５】
請求項１または請求項２の何れか１項に記載の経路探索方法をコンピュータに実行させるプログラム。
【請求項６】
請求項５のプログラムを記録した、コンピュータが読取可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、他の文書を参照するハイパーリンクの情報を有する大量の文書データ集合における最短経路を探索する最短経路探索方法、最短経路探索装置、記録媒体及びプログラムに関する。
【０００２】
【従来の技術】
近年、インターネットなどのコンピュータネットワークを通じて、大量の電子化された文書をやり取りしたり、不特定他数を対象にした情報発信ができるようになっている。そのため、そのような文書情報を対象に、個人が必要とする情報を検索できるようなサービスが不特定多数を対象にネットワーク上で実現されている。
【０００３】
コンピュータネットワーク上で表現された文書では、その特徴を生かした表現が利用されている。そのなかでも、ＷＷＷ（World Wide Web）と呼ばれる文書は、図２に示すように、なんらかの情報を書き記すだけではなく、他のコンピュータ上に存在する他の人が書いた文書を参照するための「ハイパーリンク」の機能がある。これは、他の文書を信頼して自分の記している情報を補完したり、同じ内容の文書を指すときなどに利用される。特に、お互いの文書を参照する場合には、それらの文書あるいは文書群の内容に非常に関連がある。
【０００４】
また、図３にリンク機能を持たせた可視情報を示す。従来、利用者は、目的の文書にたどり着くために、リンクに付与された可視情報を頼りに、経験と勘のみでリンクを選び、目的とする文書にたどり着いていた。図３では、文書Ａにおける「プロの財テクノウハウ」や「実践財テク大学」などの可視情報を頼りに、リンクを選んでいた。
【０００５】
【発明が解決しようとする課題】
従来は、経験と勘のみでリンクを選んでいた。利用者はなるべくリンクをたどる回数が少ない状態で目的文書に到達したい。リンクをたどる経路をパスと呼び、たどる回数が最小なパスを最短パスとよぶ。しかし、従来は、経験と勘のみでリンクを選んでいたので、結果として、リンクをたどる回数が多くなる確率が高く、利用者の利便性が低下していた。
【０００６】
図４にハイパーテキストの空間例を示す。例えば、図４で文書Ａから文書Ｌにたどりつくのに、Ａ，Ｂ，Ｅ，Ｄ，Ｇ，Ｋ，Ｌと６回のリンクをたどることもあった。
図４に示すように、探索空間が有限であれば（ここでいう有限とは、利用者が許容し得る時間内にパスを見つけることを意味する）、探索空間を網羅するように探索し、最短パスを見つけることができる。しかし、ＷＷＷのような探索空間は有限ではなく、最短パスを求めることはできないでいた。
本発明はこのような事情に鑑みてなされたものであり、文書間に張られたハイパーリンクをたどってある文書から他の有る文書を探索する際に、最短経路で探索することができる最短経路探索方法、最短経路探索装置、記録媒体及びプログラムを提供することを目的とする。
【０００７】
【課題を解決するための手段】
上記目的を達成するために、本発明は、カテゴリに属する文書を記憶する文書カテゴリ記憶手段と、パス検索手段と、結果出力手段とを有し、カテゴリに属する文書間に張られたハイパーリンクをたどって起点となる文書から終点となる文書にたどり着くパスを求める経路探索装置の経路探索方法であって、前記パス検索手段が行う、ハイパーリンクに重みを付与し、ハイパーリンクの重みの値を用いて、重みつき有向グラフを経路探索し、前記起点となる文書から前記終点となる文書にいたるパスを求めるパス検索過程と、前記結果出力手段が行う、前記パス検索過程で得たパスを出力する結果出力過程と、からなり、前記ハイパーリンクの重みは、リンク元文書のカテゴリの特徴ベクトルとリンク先文書のカテゴリの特徴ベクトルとによる類似度である関連度と、リンク先文書のカテゴリの特徴ベクトルとリンク先文書の特徴ベクトルとによる類似度である適合度と、の乗算によるものであることを特徴とする経路探索方法である。
【０００９】
また本発明は、上述の経路探索方法において、前記リンク先文書が複数のカテゴリに属しているとき、前記経路探索において用いる前記ハイパーリンクの重みの算出において、リンク先文書が属するカテゴリ毎に算出されるそれぞれの重みのうち最大の重みの値を用いることを特徴とする。
【００１０】
また本発明は、カテゴリに属する文書間に張られたハイパーリンクをたどって起点となる文書から終点となる文書にたどり着くパスを求める経路探索装置であって、前記カテゴリに属する文書を記憶する文書カテゴリ記憶手段と、前記ハイパーリンクで張られたリンク元文書のカテゴリの特徴ベクトルとリンク先文書のカテゴリの特徴ベクトルとによる類似度である関連度と、リンク先文書のカテゴリの特徴ベクトルとリンク先文書の特徴ベクトルとによる類似度である適合度と、の乗算により、前記ハイパーリンクの重みを算出する重み算出手段と、前記ハイパーリンクの重みの値を用いて、重みつき有向グラフを経路探索し、前記起点となる文書から前記終点となる文書にいたるパスを求めるパス検索手段と、前記パス検索過程で得たパスを出力する結果出力手段と、を備えることを特徴とする経路探索装置である。
【００１２】
また本発明は、上述の経路探索装置において、前記パス検索手段は、前記リンク先文書が複数のカテゴリに属しているとき、前記経路探索において用いる前記ハイパーリンクの重みの算出において、リンク先文書が属するカテゴリ毎に算出されるそれぞれの重みのうち最大の重みの値を用いることを特徴とする。
【００１３】
また本発明は、上述の経路探索方法をコンピュータに実行させるプログラムである。
【００１４】
また本発明は、上述のプログラムを記録した、コンピュータが読取可能な記録媒体である。
【００１５】
本発明は、部分探索空間での探索を繰り返し、部分探索空間で文書間の重みが最も高いパスをつなげることによって、全体のパスとする手法を用いる。最短パスの保証はないが最短パスにより近いパスを見つけることとなり、利用者の利便性が向上する。
具体的には、文書を分類するためのディレクトリを作成し、経路を求めたい２つの文書を入力すると、ディレクトリを活用して文書間の重みを算出し、重みに基づいて、パスを探索し、最終的なパスを結果として出力する。
【００１６】
パス探索をさらに詳しく説明すると、探索の起点文書を設定し、この起点文書からのリンク先文書を抽出し、起点文書とリンク先文書の同者に関してこれら文書が属するカテゴリ（ディレクトリの１つの分野）を決め、起点文書とリンク先文書間の重みを求め、重みに基づいて最適なパスを決める。
【００１７】
ディレクトリ入力部は、ディレクトリを作成する。文書は、少なくともひとつのカテゴリ（ディレクトリの１つの分野）に属し、重みの算出に活用される。
検索条件入力部では、経路を求めたい２つの文書などの検索条件を入力する。
パス検索部では、入力された２つの文書のパスを求め、
結果出力部では、パス検索部で得られた結果を表示する。
また、パス検素部の起点設定部では、探索の起点文書を設定し、
リンク先文書抽出部では、起点文書からのリンク先文書を抽出する。
カテゴリ決定部では、起点文書とリンク先文書の属するカテゴリを決め、
重み抽出部では、起点文書とリンク先文書の重みを求める。
パス決定記録部では、重みから最適なパスを決定し、これを保存し、
探索終了判定部では、探索の継続を判断する。
【００１８】
【発明の実施の形態】
以下、本発明の実施の形態を、図面を参照して詳細に説明する。なお、本発明の実施の形態を説明する全図において、同一要素には同一符号を付け、重複する説明を省略する。
図１に本発明の実施の形態に係る最短経路探索装置の構成を示す。同図において、最短経路探索装置は、はディレクトリ入力部１０１と、検索条件入力部１０２と、パス検索部１０３と、結果出力部１０４とを有している。
また、パス検索部１０３は、起点設定部２０１と、リンク先文書抽出部２０２と、カテゴリ決定部２０３と、重み算出部２０４と、パス決定記録部２０５と、探索終了判定部２０６とを有している。
【００１９】
また、図５、図６は、本発明の実施の形態に係る最短経路探索装置の処理フローであり、番号は図１のブロック図と対応し、同一の番号のものが、その処理を行う手段とステップとなっている。
ディレクトリ入力部１０１では、別途用意しておいたディレクトリの構成情報、および、自動分類するためのカテゴリに割り当てられるサンプルとなる文書を入力する。例えば、図７のようなディレクトリを作成する。
検索条件入力部１０２では、パスを求めたい２つの文書を指示する。例えば、文書Ａ，文書Ｂなどと入力する。
【００２０】
パス検索部１０３では、検索条件入力部１０２で入力された文書Ａ、文書Ｂ間におけるなるべく短いパスを、前記ディレクトリのカテゴリ間の関連度と、文書とカテゴリ間の適合度を用いて各ハイパーリンクの重みを計算し、その重みを用いて探索する。任意の文書Ａから任意の文書Ｂへの最短のパスを求める際に、ハイパーリンクの重みの値を用いて、重みつき有効グラフから最短経路を探索するＡ*アルゴリズム（「人工知能の基礎知識」太原著，近代科学社 1988 を参照）などを適応する。これにより、横型探索や縦型探索といった最短経路の探索手法（「人工知能の基礎知識」太原著，近代科学社 1988 を参照）より効率的にパスを捜し出すことが可能となる。
【００２１】
結果出力部１０４では、パス探索部１０３で求めた最短のパスの情報を出力、表示する。
以上で、全体の流れを説明した。これからさらに、パス検索部１０３によるパス検素について詳細を説明するが、その前に、パス検索は、文書間の重みに基づいて行うので、重みの算出方法について説明する。重みを求めるために必要となる文書の特徴ベクトル、カテゴリの特徴ベクトル、文書がカテゴリに適している度合いを示す適合度、カテゴリ間の関係の強さを示す関連度についても説明する。
【００２２】
文書は予め用意したディレクトリに自動分類される。文書の自動分類に関しては、特願平１０−２８１６２１（“情報自動分類方法および装置と情報自動分類プログラムを記録した記録媒体”杉崎ほか）の「従来の技術」として解説している手法などが使える。簡単に解説すると、まず文書内に存在する単語とその出現頻度情報から特徴ベクトルを作成する。文書ｉ内に存在する単語ｋの値wwikは、wwik＝文書ｉでの単語ｋの出現回数log（全文書数／単語ｋが出現する文書数）
とし、文書ｉの特徴ベクトルveciは、
veci ＝（wwi1，…，wwik，…，wwin）             （１）
とする。
【００２３】
ただし、ｎは全文書内に出現する全単語数である（特徴ベクトルの作成に関しては、“Automatic Text Processing” Gerard Salton， ADDISON−WESLEY pub． 1989を参照）。
同様に、サンプル文書内に存在する単語とその出現頻度情報からカテゴリｘの特徴ベクトルcatevxを作成する。カテゴリの特徴ベクトルにおける各要素の値は、割り当てられているサンプル文書の特徴ベクトルの対応する要素の平均値とする。
【００２４】
文書の特徴ベクトルとカテゴリの特徴ベクトルとの成す角を利用して三角関数cosθを計算し、その値から文書の各カテゴリに対する適合度（どれくらい「そのカテゴリに属する」という判断が適切か）を定義できる。文書ｉとカテゴリｘとの適合度をrelixと表現することにする。三角関数cosθを用いる場合は、relixの取りうる値は０から１の間となり、１が最も適合度が高いということになる。
また、各カテゴリ間でカテゴリの関連度を定義する。カテゴリｘとカテゴリｙの関連度をCaterelxyとする。自動で計算する場合は、カテゴリの特徴ベクトルの成す角を利用して三角関数cosθをカテゴリ間の関連度とする（特願平１０−２８１６２１の「カテゴリ間ヘの距離を導入する」を参照）。
【００２５】
カテゴリ間の関連度と、文書の各カテゴリの適合度を用いて、ある文書（iとする）に別の文書（jとする）について張られているハイパーリンクに対して重みを定義する。カテゴリｘに割り当てられた文書ｉからカテゴリｙに割り当てられた文書ｊに張られたハイパーリンクの重みwijを
wij＝Caterelxy・reljy                  （２）
とする。
ハイパーリンクの重みの例について図８を参照して説明する。
【００２６】
文書Ａがカテゴリ「Ｔ社」に属し、適合度＝０．７とし、文書Ｄがカテゴリ「純文学」に属し適合度＝０．９とする。「Ｔ社」と「純文学」の関連度＝０．１１とすると、文書Ａから文書Ｄへのリンクの重みは０．０９９（０．１１＊０．９）となる。
文書が属するカテゴリは１つとは限らない。複数存在する場合がある。こういった場合は、最大の重みを採用する。図９は文書間における経路が複数である場合におけるハイパーリンクの重みの例を示している。同図において、文書Ｄがカテゴリ「純文学」と「パーツ」に属している。「純文学」経由の重みは０．０９９（０．１１＊０．９）であり、「パーツ」経由の重みは０．１２（０．３＊０．４）であるので、重みとして値が大きい０．１２を採用する。
【００２７】
次に、パス検索部１０３におけるパス検索について説明する。全体としては、部分探索空間においてハイパーリンクの重みから最適なパスを定め、部分探索空間での探索を繰り返し、全体のパスを決めるという手法である。
図１０で文書Ａから文書Ｌへのパスを求める場合について説明する。図１０における数値は重みを示し、大きい値ほど、望ましいパスであることを示す。
パス検索部１０３では、まず、起点設定部２０１において、探索の起点を設定する。１回目は、探索条件として入力された文書であり、２回目以降は、前回の部分探索の解である。例えば、図１０では文書Ａとなる。
【００２８】
次いで、リンク先文書抽出部２０２では、起点文書からハイパーリンクが張られている文書を抽出する。図１０では文書Ｂと文書Ｃが抽出される。カテゴリ決定部２０３では、起点文書とリンク先文書に関し、自動分類技術を用いてカテゴリを決め、文書とカテゴリ間の適合度を求める。
この例では、文書Ａ、文書Ｂ、文書Ｃの属するカテゴリを決め、適合度を求める。
さらに、重み算出部２０４では、カテゴリ決定部２０３で得た結果と、カテゴリ間の関連度からハイパーリンクの重みを式（２）により計算する。図１０には、計算された結果としての重みが記載されている。
【００２９】
パス決定記録部２０５では、計算された重みを比較し、最適なパスを決め、最適なパスを記録する。図１０に示す例では、文書Ａから文書Ｂへのハイパーリンクの重みは０．４であり、文書Ａから文書Ｃへのハイパーリンクの重みは０．５であるので、文書Ａから文書Ｃへのハイパーリンクを選択し、それを記録する。
さらに、探索終了判定部２０６では、選択した文書が目的の文書かどうかをチェックし、目的の文書であれは処理を終了し、そうでなければステップ２０１に戻り、再度探索を行う。
【００３０】
図１０に示す例では、文書Ｌに到達していないので、再度探索を行う。
２回目以降の探索では、前回の探索結果を反映して処理を進める。図１０に示す例では、１回目の探索結果の文書Ｃを起点として、２回目の探索を行う。文書Ｅと文書Ｆが比較され、文書Ｆが選ばれる。以上の処理を繰り返し、文書Ｌとなるまで行う。
また、２回目以降の、ハイパーリンクの重みの選択は、既に選択してきたパスの重みをすべて掛け合わせて累積して重みの大きいハイパーリンクを探索する。
こうして、図１０の例では、Ａ，Ｃ，Ｆ，Ｉ，Ｌの経路が解として求められる。これら探索の過程を図１１にまとめる。網掛け行が部分探索での最適解を示す。
【００３１】
なお、関連度を、どの段階で算出するかに関しては、計算時間と記憶メモリ量とのトレードオフから決めるものである。部分探索毎に毎回計算する方法（計算時間がかかる）もあれば、ディレクトリ入力段階で計算し記録しておいてこの記録された値を利用するやり方（記憶メモリ量が多い）もある。
また、関連度は個別に人為的に値を指定してもよい。この場合は、ディレクトリ入力過程で行う。部分探索の手法に関しては、従来技術であるので、細かな説明はこれ以上行わないが、簡単に補足すると、リンク先が複数段の部分探索空間で探索を行ってもよい。
【００３２】
また、部分探索で解を複数個保持しながら探索を進めてもよい。また、探索終了条件として、処理時間や探索回数を採用してもよい。これら、他の探索のやり方は、システム固定で処理する方法もあれば、利用者が、探索条件入力過程で指定する方法もある。
【００３３】
また、図１に示した最短経路探索装置の機能を実現するための、図５、図６に示す最短経路探索プログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによりパス探索を行ってもよい。
【００３４】
すなわち、文書間に張られたハイパーリンクをたどってある文書から他のある文書まで最短のパスを経由するようにパスを探索するための最短経路探索プログラムであって、前記最短経路探索プログラムは、文書を分類するためのディレクトリ入力ステップと、経路を求めたい２つの文書を少なくとも含む索条件の指示を行う検索条件入力ステップと、前記入力された２つの文書間の経路を求めるパス検索ステップと、前記パス検索過程で得た結果を出力する結果出力ステップとからなる最短経路探索プログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録された最短経路探索プログラムをコンピュータシステムに読み込ませ、実行することによりパス探索を行ってもよい。
【００３５】
また、上記記録媒体に記録された最短経路探索プログラムにおいて、前記パス検索ステップは、探索の起点文書を設定する起点設定ステップと、起点文書に対するリンク先文書を抽出するリンク先文書抽出ステップと、前記起点文書とリンク先文書の両者に関し、これらの文書が属するカテゴリをそれぞれ決定するカテゴリ決定ステップと、文書間の重みを、すべてのリンク先文書について計算する重み算出ステップと、前記算出された重みを比較し、起点文書からリンク先文書への最適なパスを決定し、該パスを記録するパス決定記録ステップと、探索をさらに続けるか否かを判定する探索終了判定ステップとからなることを特徴とする。
【００３６】
なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可般媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。
【００３７】
さらに、「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの(伝送媒体ないしは伝送波)、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含むものとする。
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００３８】
【発明の効果】
以上説明したように、本発明では、文書間の重みに着目してパスを求めるので、的はずれな（選択回数が極端に多くなるような）パスが提示される確率は低く、的確なパス（最短パスに近いパス）を提示する確率が高くなる。
また、部分空間に区切って探索を行うので、処理時間も利用者が許容できる範囲内に抑えることが可能となる。
【図面の簡単な説明】
【図１】  本発明の実施の形態に係る最短経路探索装置の構成を示すブロック図。
【図２】  ハイパーリンクの機能を示す説明図。
【図３】  ハイパーリンクの機能を実現する可視情報を示す説明図。
【図４】  ハイパーテキストの探索空間を示す説明図。
【図５】  図１に示す最短経路探索装置の処理内容を示すフローチャート。
【図６】  図５におけるパス検索処理の詳細を示すフローチャート。
【図７】  ディレクトリの一例を示す説明図。
【図８】  ハイパーリンクの重みの例を示す説明図。
【図９】  探索経路が複数ある場合のハイパーリンクの重みの例を示す説明図。
【図１０】  ハイパーテキストの探索空間の一例をハイパーリンクの重みと共に示す説明図。
【図１１】  ハイパーテキストのパス検索時における部分探索の過程を示す説明図。
【符号の説明】
１０１  ディレクトリ入力部
１０２  探索条件入力部
１０３  パス検索部
１０４  結果出力部
２０１  起点設定部
２０２  リンク先文書抽出部
２０３  カテゴリ決定部
２０４  重み算出部
２０５  パス決定記録部
２０６  探索終了判定部
【図１】
0003913495.tif 000002
【図２】
0003913495.tif 000003
【図３】
0003913495.tif 000004
【図４】
0003913495.tif 000005
【図５】
0003913495.tif 000006
【図６】
0003913495.tif 000007
【図７】
0003913495.tif 000008
【図８】
0003913495.tif 000009
【図９】
0003913495.tif 000010
【図１０】
0003913495.tif 000011
【図１１】
0003913495.tif 000012