JPH11259509A

JPH11259509A - 情報検索分類方法および情報検索分類システム

Info

Publication number: JPH11259509A
Application number: JP10060915A
Authority: JP
Inventors: Hiroyuki Kaji; 博行梶; Yasutsugu Morimoto; 康嗣森本; Toshiko Aizono; 敏子相薗
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1998-03-12
Filing date: 1998-03-12
Publication date: 1999-09-24

Abstract

(57)【要約】【課題】クラスタリングに要する計算量を十分に小さ
くすることができない。【解決手段】検索質問による検索技術とクラスタリン
グ技術とを組み合わせて、情報の検索分類を行う構成と
し、特に、ターム相関抽出部１ｄにより、文書ファイル
１０ａ内の文書の集合から、タームの相関に関する知識
を予め抽出して（ターム毎にこのタームと相関の高いタ
ームを相関度を付与して）ターム相関ファイル１０ｄに
登録しておき、ユーザの検索質問に対応して文書を検索
する場合、入力タームと相関の高いタームをターム相関
ファイル１０ｄから抽出し、その相関度に基づきクラス
タリングし、さらにこのタームのクラスタに基づき、検
索質問に対応して検索した文書をクラスタリングする。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、クラスタリングに
よる情報の検索、分類技術に係わり、特に、検索結果を
高速に分類するのに好適な情報検索分類方法および情報
検索分類システムに関するものである。

【０００２】

【従来の技術】計算機（コンピュータ）技術の進歩と共
に、大量の文書を蓄積したデータベースから、ユーザの
情報要求に適合する文書を検索する情報検索システムが
さまざまな分野で利用されるようになってきた。このよ
うな情報検索システムでは、一般に、ユーザが情報要求
を表わすタームを用いて検索質問を入力することが必要
である。

【０００３】しかし、情報要求を的確に表すタームを想
起することはユーザにとって必ずしも容易でない。ま
た、ユーザが思いつくタームは高々数個であることが多
い。そのため、大量の文書を蓄積したシステムでは、検
索される文書の数もかなり多くなり、その中には適合文
書と不適合文書が混在する。

【０００４】このような問題に対処するために、検索質
問と文書の関連度を計算して、関連度の大きい順に出力
するシステムもある。しかし、適合文書が全て上位にラ
ンクされることにはならない。このため、検索された文
書の中から適合文書を選び出すためのユーザ負荷が非常
に大きい。

【０００５】このような、検索質問に応答する形式のシ
ステムではなく、データベース全体をブラウジングしな
がら情報要求に適合する文書を探し出すという新しい考
え方のシステムも提案されている。この技術は、ユーザ
が情報要求を持っているが、その内容が必ずしも明確で
ないというような状況に適したものであり、D.R.Cuttin
g,et al., "Scatter／Gather: A Cluster−based Appro
ach to Browsing Large Document Collections," Proce
edings of the 15th International Conference on Inf
ormation Retrieval, pp. 318−329（1992 June, Copen
hagen）に述べられているシステムがその例である。

【０００６】この技術では、システム側で、データベー
スに蓄積された文書を文書間の類似度に基づいてクラス
タリングし、ユーザに提示する。ユーザは、情報要求に
関連のありそうなクラスタを選択する。この選択に基づ
き、システムは、選択されたクラスタの文書を対象とし
て、さらにクラスタリングを実行し、その結果をユーザ
に提示する。このようなインタラクションを通じて、情
報要求に適合する文書を含むクラスタに絞り込んでいく
ことができる。

【０００７】しかし、この技術には次のような問題点が
ある。すなわち、データベース全体のクラスタリングか
らスタートすると、最初のうちは、かなり多様な文書を
含み、特徴が不明確なクラスタしか得られないことが多
い。また、対話性がこの技術の本質であるが、それを損
なわない応答時間を達成することは容易でない。

【０００８】このクラスタリング処理の計算量について
は次の通りである。ｎ個の要素（ここでは文書）をクラ
スタリングする処理は、一般に、全ての要素対について
の類似度計算を含め、ｎ²のオーダーの計算量になる。
計算量を削減するため、上記Scatter／Gatherでは、ｎ
個の要素を一括してクラスタリングせずに、ｎ個の要素
からランダムに選んだｍ個の要素をクラスタリングして
クラスタの種を生成する第１ステップと、（ｎ−ｍ）個
の要素をそれぞれ最も近いクラスタに振り分ける第２ス
テップに分ける技術を提案している。

【０００９】このようにすることにより、第１ステップ
はｍ²のオーダー、第２ステップは（ｎ−ｍ)×ｃのオー
ダーの計算量になり、ｎ個の要素を一括してクラスタリ
ングするよりは計算量が小さくなる。尚、ｃはクラスタ
の種の数である。しかし、この技術では、良いクラスタ
リング結果を得るには、ｍはｎに比例した値にしなけれ
ばならない。従って、実時間の文書クラスタリングとい
う意味では、十分な解決策とはいえない。

【００１０】

【発明が解決しようとする課題】解決しようとする問題
点は、従来の技術では、クラスタリングに要する計算量
を十分に小さくすることができない点である。本発明の
目的は、これら従来技術の課題を解決し、高速な情報の
検索分類が可能な情報検索分類方法および情報検索分類
システムを提供することである。

【００１１】

【課題を解決するための手段】上記目的を達成するた
め、本発明の情報検索分類方法および情報検索分類シス
テムは、検索質問による検索技術とクラスタリング技術
とを組み合わせて、情報の検索分類を行う構成とし、特
に、文書ファイルに蓄積した文書の集合から、タームの
相関に関する知識を予め抽出して（ターム毎に、このタ
ームと相関の高いタームを、その相関度を付与して）登
録しておき、ユーザがタームを用いて入力した検索質問
に対応して文書を検索する場合に、ユーザが入力したタ
ームと相関の高いタームを、予め登録しておいたターム
から抽出し、ターム間の相関度に基づきクラスタリング
し、さらに、このタームのクラスタに基づき、検索質問
に対応して検索した文書をクラスタリングする。そし
て、この文書クラスタを表示してユーザの選択を待ち、
ユーザが選択したクラスタに関してのタームのクラスタ
リング、および、文書のクラスタリングを繰り返す。こ
のように、ユーザの検索質問からスタートして、この検
索質問に用いたタームと、その相関タームに基づき、検
索した関連文書のクラスタリングとクラスタ選択のサイ
クルを繰り返すので、クラスタリングに要する処理時間
を短くでき、ユーザは、効率良く適合文書に到達するこ
とができる。

【００１２】

【発明の実施の形態】以下、本発明の実施例を、図面に
より詳細に説明する。図１は、本発明の情報検索分類シ
ステムの本発明に係る構成の一実施例を示すブロック図
であり、図２は、図１における情報検索分類システムを
構成するコンピュータの構成例を示すブロック図であ
る。

【００１３】図２に示すように、本例の情報検索分類シ
ステムは、ＣＰＵ（Central Processing Unit）を具備
して蓄積プログラム方式によるコンピュータ処理を行う
処理装置２１と、ＲＡＭからなる記憶装置２２、ハード
ディスク等に格納した検索分類対象の文書を処理装置２
１に入力する文書入力装置２３、キーボードやマウス等
からなる入力装置２４、および、ＣＲＴ（Cathode Ray
Tube）等からなる表示装置２５からなるコンピュータで
構成される。

【００１４】処理装置２１では、図１における蓄積サブ
システム１および検索サブシステム２の処理を実行し、
記憶装置２２には、図１における文書ファイル１０ａ、
文書特徴ファイル１０ｂ、インデクスファイル１０ｃ、
およびターム相関ファイル１０ｄが記憶される。文書入
力装置２３は、文書データを入力するための装置であ
り、ハードディスク駆動装置以外にも、文書データの入
手媒体に応じて、ＣＤ−ＲＯＭ駆動装置やフロッピーデ
ィスク駆動装置などが用いられる。入力装置２４と表示
装置２５により、ユーザは、検索サブシステムとの対話
方式での操作を行う。

【００１５】このような構成のコンピュータの処理装置
２１において、ＣＤ−ＲＯＭ駆動装置等を介して、本発
明に係わる情報検索分類方法の手順を光ディスクに記録
したプログラムをロードすることにより、図１の蓄積サ
ブシステム１における各処理部（文書登録部１ａ、文書
特徴抽出部１ｂ、インデクスファイル生成部１ｃ、ター
ム相関抽出部１ｄ）と検索サブシステム２における関連
ターム選出部２ａ、タームクラスタ生成部２ｂ、文書検
索部２ｃ、文書クラスタ生成部２ｄ、文書クラスタ表示
制御部２ｅなどのモジュールが構成される

【００１６】以下、図１に従って、本例の情報検索分類
システムの構成を説明する。本図１において、１は予め
情報の検索分類に用いるファイルを生成して蓄積するた
めの蓄積サブシステム、２は蓄積サブシステム１で蓄積
している各ファイルを用いて情報の検索分類処理を行う
検索サブシステムである。

【００１７】蓄積サブシステム１は、文書登録部１ａ、
文書特徴抽出部１ｂ、インデクスファイル生成部１ｃお
よびターム相関抽出部１ｄを有し、各部の処理結果は、
それぞれ、文書ファイル１０ａ、文書特徴ファイル１０
ｂ、インデクスファイル１０ｃ、ターム相関ファイル１
０ｄに登録される。蓄積サブシステム１の各部（文書登
録部１ａ、文書特徴抽出部１ｂ、インデクスファイル生
成部１ｃ、ターム相関抽出部１ｄ）の処理について説明
する前に、それらの部が作成するファイルについて図３
〜図６を用いて説明する。

【００１８】図３は、図１における文書ファイルのレコ
ード構成例を示す説明図であり、図４は、図１における
文書特徴ファイルのレコード構成例を示す説明図、図５
は、図１におけるインデクスファイルのレコード構成例
を示す説明図、そして、図６は、図１におけるターム相
関ファイルのレコード構成例を示す説明図である。

【００１９】図３に示すように、文書ファイル１０ａ
は、文書ＩＤ３１と文書の内容であるテキストデータ３
２を含むレコードから構成される。文書ＩＤをキーとし
て、当該文書ＩＤを持つレコードに直接アクセスできる
構造のファイルである。そのような構造のファイルは、
Ｂトリーインデクスを作成する方法や、ハッシングによ
る方法など、さまざまな技術により実現することがで
き、これらの技術は公知であるので、説明は省略する。

【００２０】図４に示すように、文書特徴ファイル１０
ｂは、文書ＩＤ４１と文書のタームベクトル４２を含む
レコードから構成される。タームベクトル４２は、ター
ム４２ａと当該タームの重み４２ｂの組のリストであ
る。文書ＩＤ４１をキーとしてレコードに直接アクセス
できる構造のファイルである。

【００２１】図５に示すように、インデクスファイル１
０ｃは、ターム５１とターム出現文書情報５２を含むレ
コードから構成される。ターム出現文書情報５２は、文
書ＩＤ５２ａと当該文書におけるターム５１の重み５２
ｂの組のリストである。ターム５１をキーとしてレコー
ドに直接アクセスできる構造のファイルである。

【００２２】図６に示すように、ターム相関ファイル１
０ｄは、ターム６１と相関ターム情報６２を含むレコー
ドから構成される。相関ターム情報６２は、ターム６２
ａと相関度６２ｂの組のリストである。ターム６１をキ
ーとしてレコードに直接アクセスできる構造のファイル
である。

【００２３】次に、図１における蓄積サブシステム１の
各部（文書登録部１ａ、文書特徴抽出部１ｂ、インデク
スファイル生成部１ｃ、ターム相関抽出部１ｄ）の処理
を説明する。文書登録部１ａは、図２の文書入力装置２
３から文書を一つずつ読み込み、文書ＩＤを付与し、文
書のテキストデータと共に文書ファイル１０ａに出力す
る。

【００２４】文書特徴抽出部１ｂは、文書ファイル１０
ａ中の各文書を読み出し、テキストデータから、ターム
とその出現頻度を求め、その結果に基づいて各文書にお
ける各タームの重みを計算する。そして、各文書につい
て、重みが予め定めた閾値以上であるタームを選択し、
重みと共に文書特徴ファイル１０ｂに出力する。ここ
で、タームの重みはtf−idf（term frequency − inver
se document frequency）の考え方に基づいて計算す
る。

【００２５】すなわち、文書diにおけるタームtjの重み
w（di,tj）を次式で計算する。 w（di,tj）＝fi,j×log（N／nj）ここで、fi,jは、文書diにおけるタームtjの出現頻度、
Nは、文書ファイル中の文書数、njは、タームtjが出現
した文書数である。

【００２６】インデクスファイル生成部１ｃは、文書特
徴ファイル１０ｂを読み込み、転置ファイルを生成す
る。すなわち、文書特徴ファイル１０ｂでは、文書毎
に、タームとそのタームの当該文書における重みの組の
リストを記憶しているのに対し、インデクスファイル生
成部１ｃでは、ターム毎に、文書とその文書における当
該タームの重みの組のリストを記憶する。このようなレ
コードを作成してインデクスファイル１０ｃに出力す
る。

【００２７】ターム相関抽出部１ｄは、文書ファイル１
０ａ中の文書を読み出し、テキストデータ３２から共起
するタームの組とその共起頻度を求め、その結果に基づ
いてターム間の相関度を計算する。各タームについて、
相関度が予め定めた閾値以上であるタームを選択し、相
関度と共にターム相関ファイル１０ｄに出力する。

【００２８】共起するタームは、ウインドウ共起の定義
に基づいて抽出する。すなわち、テキスト中でタームt
の出現位置からの距離がW語以内の位置にタームt'が出
現するとき、tとt'が共起していると考える。Wはウイン
ドウのサイズで、予め値を定めておく。テキストに沿っ
てウインドウを移動させながら、共起するタームの組を
抽出してその頻度をカウントする。

【００２９】また、ターム間の相関度としては相互情報
量を計算する。すなわち、タームtiとタームtjの相関度
α（ti,tj）を次の式（数１）で計算する。

【数１】ここで、f（ti）はタームtiの出現頻度、g（ti,tj）は
タームtiとタームtjの共起頻度である。

【００３０】次に、図１における検索サブシステム２に
ついて、図７を用いて説明する。図７は、図１における
検索サブシステムの詳細な構成例を示すブロック図であ
る。本例の検索サブシステムは、検索質問読込み部２
ｆ、文書検索部２ｃ、関連ターム選出部２ａ、タームク
ラスタ抽出部２ｂ、文書クラスタ生成部２ｄ、文書クラ
スタ表示制御部２ｅ、クラスタ番号読込み部２ｇ、およ
びターム集合・文書集合縮小部２ｈから構成されてい
る。

【００３１】検索質問読込み部２ｆとクラスタ番号読込
み部２ｇは、図２の入力装置２４からのユーザの入力を
待って処理を開始する。また、関連ターム選出部２ａ、
タームクラスタ抽出部２ｂ、文書検索部２ｃ、文書クラ
スタ生成部２ｄ、文書クラスタ表示制御部２ｅ、および
ターム集合・文書集合縮小部２ｈは、必要なデータを他
の部から受け取ると処理を開始する。

【００３２】以下、これらの検索サブシステムの各部
（関連ターム選出部２ａ、タームクラスタ抽出部２ｂ、
文書検索部２ｃ、文書クラスタ生成部２ｄ、文書クラス
タ表示制御部２ｅ、検索質問読込み部２ｆ、クラスタ番
号読込み部２ｇ、ターム集合・文書集合縮小部２ｈ）の
処理について説明する前に、各部の間で授受するデータ
（検索質問データ１０ｅ、検索文書集合データ１０ｆ、
関連ターム集合データ１０ｇ、タームクラスタデータ１
０ｈ、文書クラスタデータ１０ｉ、クラスタ番号データ
１０ｊ）の構造について、図８〜図１３を用いて説明す
る。

【００３３】図８は、図７における検索質問データの構
成例を示す説明図であり、図９は、図７における検索文
書集合データの構成例を示す説明図、図１０は、図７に
おける関連ターム集合データの構成例を示す説明図、図
１１は、図７におけるタームクラスタデータの構成例を
示す説明図、図１２は、図７における文書クラスタデー
タの構成例を示す説明図、そして、図１３は、図７にお
けるクラスタ番号データの構成例を示す説明図である。

【００３４】図８に示すように、検索質問データ１０ｅ
は、１個の論理オペレータ８１と１個以上のターム８２
から構成される。論理オペレータ８１の値は、「ＡＮ
Ｄ」、「ＯＲ」、または、空白である。図９に示すよう
に、検索文書集合データ１０ｆは、０個以上の文書ＩＤ
９１から構成される。

【００３５】図１０に示すように、関連ターム集合デー
タ１０ｇは、０個以上のターム１０１から構成される。
図１１に示すように、タームクラスタデータ１０ｈは、
Ｌ個のクラスタそれぞれに対応するレコードからなり。
各レコードはクラスタ番号１１１と１個以上のターム１
１２から構成される。

【００３６】図１２に示すように、文書クラスタデータ
１０ｉは、Ｌ個のクラスタそれぞれに対応するレコード
からなり、各レコードはクラスタ番号１２１、および、
１組以上の文書ＩＤ１２２と類似度１２３の組から構成
される。図１３に示すように、クラスタ番号データ１０
ｊは、１個以上のクラスタ番号１３１から構成される。

【００３７】次に、このような各データに対する図７の
検索サブシステムにおける各部の処理動作を説明する。
検索質問読込み部２ｆは、図２の入力装置２４から検索
質問を読み込み、検索質問データ１０ｅの論理オペレー
タ８１とターム８２に値を出力する。本例では、検索質
問の形式を１個のターム、複数タームの論理積、複数タ
ームの論理和の３通りに限定する。また、それぞれの場
合の論理オペレータ８１とターム８２の値は以下の通り
とする。

【００３８】検索質問が１個のタームである場合、すな
わちｑ＝t₁の場合、論理オペレータ８１は空白とし、t₁
をターム８２にセットする。また、検索質問が複数ター
ムの論理積である場合、すなわちｑ＝t₁∧t₂∧‥∧tpの
場合、論理オペレータ８１はＡＮＤとし、t₁,t₂,‥,tp
をターム８２にセットする。また、検索質問が複数ター
ムの論理和である場合、すなわちｑ＝t₁∨t₂∨‥∨tpの
場合、論理オペレータ８１はＯＲとし、t₁,t₂,‥,tpを
ターム８２にセットする。

【００３９】文書検索部２ｃは、検索質問データ１０ｅ
を読み込み、ターム８２をキーとしてインデクスファイ
ル１０ｃのレコードを検索し、図５のターム出現文書情
報５２に文書ＩＤが記されている文書と検索質問との関
連度を計算し、関連度の大きい文書の文書ＩＤを検索文
書集合データ１０ｆに出力する。

【００４０】文書（ｄ）と検索質問（ｑ）との関連度Ｒ
(d,ｑ)は、論理オペレータ８１の値に応じて以下のよう
に計算する。論理オペレータが空白の場合、すなわちｑ
＝t₁の場合、Ｒ(d,ｑ)＝ｗ(d,t₁) 論理オペレータがＡＮＤの場合、すなわちｑ＝t₁∧t₂∧
‥∧tpの場合、Ｒ(d,ｑ)＝min{ｗ(d,t₁)，ｗ(d,t₂)，‥，ｗ(d,tp）｝論理オペレータがＯＲの場合、すなわちｑ＝ｔ_１∨t₂∨
‥∨tpの場合、Ｒ(d,ｑ)＝max{ｗ(d,t₁)，ｗ(d,t₂)，‥，ｗ(d,tp）} ここで、ｗ(d,t）の値は次の通りである。

【００４１】タームｔをキーとして検索したインデクス
ファイル１０ｃのレコード中の文書ＩＤ５２ａが文書
(ｄ)を含んでいれば、対応する重み５２ｂをｗ(d,t)の
値とする。また、タームｔをキーとして検索したインデ
クスファイル１０ｃのレコード中の文書ＩＤ５２ａが文
書ｄを含んでいなければ、ｗ(d,t)の値は０にする。

【００４２】このようにして求めた関連度Ｒ(d,ｑ)に基
づく検索文書集合の決定は、検索文書集合の大きさの上
限Ｍと関連度の下限θ₁を予め定めておくことにより行
う。すなわち、Ｒ(d,ｑ)＞θ₁を満たす範囲内で、Ｒ(d,
ｑ)の大きい順に最大M個の文書を選択する。選択された
文書d₁,d₂,‥,dmの文書ＩＤを検索文書集合データ１０
ｆとして出力する。

【００４３】関連ターム選出部２ａは、検索質問データ
１０ｅを読み込み、図８におけるターム８２をキーとし
てターム相関ファイル１０ｄのレコードを検索し、図６
における相関ターム情報６２に含まれるタームと検索質
問との相関度を計算し、相関度の大きいタームを関連タ
ーム集合データ１０ｇに出力する。

【００４４】ターム(ｔ)と検索質問(ｑ)との相関度Ａ
(t,ｑ)は、図８の論理オペレータ８１の値に応じて以下
のように計算する。論理オペレータが空白の場合、すな
わちｑ＝t₁の場合、Ａ(t,ｑ)＝α(t,t₁）論理オペレータがＡＮＤの場合、すなわちｑ＝t₁∧t₂‥
∧tpの場合、Ａ(t,ｑ)＝min{α(t,t₁)，α(t,t₂)，‥，α(t,tp）} 論理オペレータがＯＲの場合、すなわちｑ＝t₁∨t₂‥∨
tpの場合、Ａ(t,ｑ)＝max{α(t,t₁)，α(t,t₂)，‥，α(t,tp）｝

【００４５】ここで、α（ｔ，ｔｉ）の値は次の通りで
ある。タームtiをキーとして検索したターム相関ファイ
ル１０ｄのレコードの相関ターム情報６２中のターム６
２ａにタームｔが含まれていれば、対応する相関度６２
ｂをα(t,ti)の値とする。タームtiをキーとして検索し
たターム相関ファイル１０ｄのレコードの相関ターム情
報６２中のターム６２ａにタームｔが含まれていなけれ
ば、α(t,ti)の値は０にする。

【００４６】相関度Ａ(t,ｑ)に基づく関連ターム集合の
決定は、関連ターム集合の大きさの上限Ｋと相関度の下
限θ₂を予め定めておくことにより行う。すなわち、Ａ
(t,ｑ)＞θ₂を満たす範囲内で、Ａ(t,ｑ)の大きい順に
最大Ｋ個のタームを選択する。選択されたタームt₁,t₂,
‥,tkを関連ターム集合データ１０ｇとして出力する。

【００４７】タームクラスタ抽出部２ｂは、関連ターム
集合データ１０ｇを読み込み、さらに関連ターム集合に
属するターム相互間の相関度をターム相関ファイル１０
ｄから読み込む。これに基づいて関連ターム集合をクラ
スタリングし、得られたクラスタをタームクラスタデー
タ１０ｈに出力する。クラスタリングの方法として、本
例では凝集的なクラスタリング法の一つであるグループ
平均法を用いる。生成するクラスタの数は予め定めた値
Ｌとする。

【００４８】クラスタリングすべき関連ターム集合が{t
₁，t₂，‥，tk}であるとする。このとき、次の手順でＬ
個のクラスタを生成する。まず、初期状態として、ｋ個
のクラスタＣ₁＝{t₁}，Ｃ₂＝{t₂}，‥，Ｃk＝{tk}を作
る。そして、クラスタの総数がＬと等しくなるまで、次
の処理を繰り返す。相関度が最大であるクラスタの対を
選んで一つのクラスタにマージする。

【００４９】ここで、クラスタＣとＤの相関度αc(C,D)
を、次の式（数２）で定義する。ただし、α(t,u)は二
つのタームt,uの相関度である。

【数２】

【００５０】文書クラスタ生成部２ｄは、検索文書集合
データ１０ｆに文書ＩＤが記されている文書の各々につ
いて、文書特徴ファイル１０ｂからタームベクトルを読
み出し、タームクラスタデータ１０ｈ中の各クラスタと
の類似度を計算する。各文書を類似度が最大のタームク
ラスタに割り当てることによって、タームクラスタを種
にした文書クラスタを生成する。その結果を文書クラス
タデータ１０ｉに出力する。

【００５１】文書のタームベクトルとタームクラスタの
類似度は次のようにして計算する。まず、文書特徴ファ
イル１０ｂから読み出した文書ｄのタームベクトル（図
４のタームベクトル４２）を、類似度計算のため、次の
ようなベクトル表現ｄに形式変換する。ここで、関連タ
ーム集合が{t₁，t₂，‥，tk}であるとしている。文書ｄ
のタームベクトル４２がタームｔiを含んでいるなら
ば、その重みをベクトルｄの第ｉ要素の値とする。文書
ｄのタームベクトル４２がタームｔiを含んでいなけれ
ば、ベクトルｄの第ｉ要素の値は０にする。

【００５２】次に、タームクラスタＣのベクトル表現ｃ
を次のようにして作成する。ここでも関連ターム集合が
{t₁，t₂，‥，tk}であるとしている。タームクラスタＣ
がタームｔiを含んでいるならば、ベクトルｃの第ｉ要
素の値を１にする。また、タームクラスタＣがタームｔ
iを含んでいなければ、ベクトルｃの第ｉ要素の値を０
にする。このようにして作成した二つのベクトルｄ,ｃ
を用い、文書ｄとタームクラスタＣの類似度ρ(d,C)を
次式で計算する。 ρ(d,C)＝d×c／(|d|×｜ｃ｜）

【００５３】文書クラスタ表示制御部２ｅは、文書クラ
スタデータ１０ｉ中の文書クラスタの各々について、ダ
イジェストを図２の表示装置２５に出力する。ダイジェ
ストは、文書クラスタを特徴付けるタームのリストと文
書クラスタを代表する文書である。前者として、ターム
クラスタデータ１０ｈのレコードで、文書クラスタと同
一のクラスタ番号を持つものを出力する。後者として
は、文書クラスタデータ１０ｉの当該文書クラスタのレ
コード中、図１２における類似度１２３の最大値に対応
する文書ＩＤ１２２を持つ文書を採用する。

【００５４】その文書のテキストデータ（図３に示すテ
キストデータ３２）を文書ファイル１０ａから読み出
し、その最初の部分（予め定めた文字数分）を出力す
る。このようにして出力した文書クラスタダイジェスト
の例を図１４に示す。図１４は、図７における文書クラ
スタ表示制御部により表示された文書クラスタダイジェ
ストの表示例を示す説明図である。本例では、検索質問
データにおけるタームに「半導体」が指定された場合
の、検索、分類結果が示されており、例えば、クラスタ
１として、キーワードの欄には各タームクラスタ（「日
米」，「通商」，・・・」）が、また、文書クラスタと
して文書１と文書２がそれぞれの内容の一部と共に表示
されている。

【００５５】図７の説明に戻り、クラスタ番号読込み部
２ｇは、図２の入力装置２４からユーザが入力するクラ
スタ番号を読み込み、クラスタ番号データ１０ｊに値を
セットする。ターム集合・文書集合縮小部２ｈは、ター
ムクラスタデータ１０ｈから、クラスタ番号データ１０
ｊ中のクラスタ番号と同一のクラスタ番号を持つレコー
ドを読込む。そして、読込んだレコードに記されている
タームの和集合を求め、関連ターム集合データ１０ｇに
出力する。同様に、文書クラスタデータ１０ｉから、ク
ラスタ番号データ１０ｊ中のクラスタ番号と同一のクラ
スタ番号を持つレコードを読込み、読込んだレコードに
記されている文書ＩＤの和集合を求め、検索文書集合デ
ータ１０ｆに出力する。

【００５６】以上、検索サブシステムにおける各部の処
理を説明したが、検索サブシステム全体としては次のよ
うに処理を行う。ユーザが図２の入力装置２４から検索
質問を入力すると、検索質問読込み部２ｆ、文書検索部
２ｃ、関連ターム選出部２ａ、タームクラスタ抽出部２
ｂ、文書クラスタ生成部２ｄ、文書クラスタ表示制御部
２ｅが順次動作して、検索質問との関連度が大きい文書
を複数のクラスタに分類した結果を図２の表示装置２５
に表示する。

【００５７】ユーザが、表示されたクラスタから、情報
要求に関連の強そうなクラスタを選択し、その番号を入
力装置２４から入力すると、クラスタ番号読込み部２
ｇ、およびターム集合・文書集合縮小部２ｈ、タームク
ラスタ抽出部２ｂ、文書クラスタ生成部２ｄ、文書クラ
スタ表示制御部２ｅが順次動作して、選択されたクラス
タを、より小さなクラスタに分類し、その結果を表示装
置２５に表示する。このようなクラスタを選択して細分
類する処理を必要なだけ繰り返すことによって、ユーザ
は適合文書を探し出すことができる。

【００５８】クラスタリングの計算量については次の通
りである。検索された文書をクラスタリングするために
本例で導入した処理部は、関連ターム選出部２ａ、ター
ムクラスタ抽出部２ｂ、および文書クラスタ生成部２ｄ
である。そして、関連ターム選出部２ａの計算量は、検
索質問に含まれるターム数をｔとすると、ｔのオーダー
である。また、タームクラスタ抽出部２ｂの計算量は、
関連ターム集合のターム数をｋとするとｋ^２のオーダー
である。さらに、文書クラスタ生成部２ｄの計算量は、
検索文書集合の文書数をｍ、タームクラスタの数をＬと
するとｍ×Ｌのオーダーである。

【００５９】ここで、ｔやＬの値はｍに比べて非常に小
さい。また、ｋは一定の値に設定して良く、検索文書集
合の文書数ｍとして許容すべき値よりは十分小さくでき
る。しかも、タームクラスタ抽出部２ｂの計算量でｋ²
に掛ける係数は小さい。なぜなら、ターム間の相関度は
計算済みでターム相関ファイル１０ｄに記憶されている
からである。以上より、本例の文書クラスタリングの計
算量が、検索文書集合を直接クラスタリングする方法
（計算量はｍ²のオーダー）に比べて小さいことは明ら
かである。

【００６０】本例の利点として、さらに次のことがあげ
られる。文書クラスタが生成された段階で、文書クラス
タを特徴付けるタームのリストが既に得られている。従
って、文書クラスタからダイジェストを作る処理を別途
行わなくて良い。

【００６１】図１５および図１６は、本発明の情報検索
分類方法に係わる一実施例を示すフローチャートであ
る。まず、図１５において、蓄積サブシステムとして次
の処理を行う。図１の文書特徴抽出部１ｂにより、文書
ファイル１０ａ中の各文書に出現するタームと出現頻度
を抽出し（ステップ１５０１）、それに基づいて、各文
書におけるタームの重みを計算し（ステップ１５０
２）、重みが予め定めた値以上であるようなタームと重
みの組を要素とするタームベクトルを文書特徴ファイル
１０ｂに出力する（ステップ１５０３）。そして、ター
ム相関抽出部１ｄにより、文書ファイル中の文書から共
起するタームの組と共起頻度を抽出し（ステップ１５０
４）、共起頻度に基づきターム間の相関を計算して結果
をターム相関ファイル１０ｄに出力する（ステップ１５
０５）。

【００６２】このようにしてデータを蓄積した後、図１
６において、検索サブシステムとして次の処理を行な
う。ユーザが検索質問を入力すると（ステップ１５０
６）、図７における検索質問読込み部２ｆにより、これ
を読込む（ステップ１５０７）。次に、文書検索部２ｃ
により、インデクスファイル１０ｃを参照して、検索質
問と文書の関連度を計算して関連度の大きい文書を選択
し、選択した文書ＩＤを検索文書集合データ１０ｆとし
て出力する（ステップ１５０８）。また、関連ターム選
出部２ａにより、ターム相関ファイル１０ｄを参照し
て、検索質問と相関の強いタームを選出し、関連ターム
集合データ１０ｇとして出力する（ステップ１５０
９）。

【００６３】さらに、タームクラスタ抽出部２ｂによ
り、ターム相関ファイル１０ｄを参照して、関連ターム
集合データ１０ｇをクラスタリングし、相互に相関の強
いタームからなる複数のタームクラスタを抽出してター
ムクラスタデータ１０ｈとして出力する（ステップ１５
１０）。そして、文書クラスタ生成部２ｈにより、検索
文書集合データ１０ｆの各文書について、文書特徴ファ
イル１０ｂからタームベクトルを読み出して（ステップ
１５１１）、タームベクトルと各タームクラスタの類似
度を計算し（ステップ１５１２）、最も類似度の高いタ
ームクラスタに文書を割り当てることによって、ターム
クラスタを種にした文書クラスタを生成する（ステップ
１５１３）。

【００６４】そして、文書クラスタ表示制御部２ｅによ
り、生成された文書クラスタの各々について、種になっ
たタームクラスタ、および、このタームクラスタとの類
似度が最大の文書を表示する（ステップ１５１４）。ユ
ーザは、この表示をみて、情報要求に関連の強そうな一
つあるいはいくつかのクラスタを選択する（ステップ１
５１５）。

【００６５】すると、クラスタ番号読込み部２ｇによ
り、ユーザが選択したクラスタ番号を読込み（ステップ
１５１６）、ターム集合・文書集合縮小部２ｈにより、
選択された文書クラスタの種になったタームクラスタの
和集合を求めて、関連ターム集合データ１０ｇをこれで
置き換え（ステップ１５１７）、また、選択された文書
クラスタの和集合を求めて、検索文書集合データ１０ｆ
をこれで置き換える（ステップ１５１８）。その後、ス
テップ１５１０に戻り、このように置き換えた関連ター
ム集合データおよび検索文書集合データを用いたクラス
タリングを繰り返す。

【００６６】以上、図１〜図１６を用いて説明したよう
に、本実施例の情報検索分類システムおよび情報検索分
類方法では、全体を蓄積サブシステム１と検索サブシス
テム２とに分け、蓄積サブシステム１を、図１に示すよ
うに、文書ファイル１０ａ中の各文書の内容を特徴付け
るタームベクトルを抽出する文書特徴抽出部１ｂと、文
書ファイル１０ａ中の文書を解析してタームの相関に関
する知識を抽出し、ターム相関ファイル１０ｄに記憶す
るターム相関抽出部１ｄとを含むように構成する。

【００６７】また、検索サブシステム２を、図７に示す
ように、ユーザの検索質問を読込む検索質問読込み部２
ｆ、読込んだ検索質問に関連の強い文書を検索する文書
検索部２ｃ、ターム相関ファイル１０ｄを参照して、検
索質問と相関の強いタームを関連タームとして選出する
関連ターム選出部２ａ、ターム相関ファイルを参照し
て、関連タームの集合から複数のタームクラスタを抽出
するタームクラスタ抽出部２ｂ、検索された文書のター
ムベクトルと抽出されたタームクラスタとの類似度を計
算して、文書を最も類似度の大きいタームクラスタに割
り当てることにより、文書クラスタを生成する文書クラ
スタ生成部２ｄ、生成された文書クラスタのダイジェス
トとして、文書クラスタの種になったタームクラスタ、
および、このタームクラスタとの類似度が最大の文書
（の一部）を表示する文書クラスタ表示制御部２ｅ、文
書クラスタのうちの一つあるいはいくつかをユーザに選
択させるクラスタ番号読込み部２ｇ、選択された文書ク
ラスタの種になったタームクラスタの和集合で関連ター
ムの集合を置き換え、また選択された文書クラスタの和
集合で検索文書の集合を置き換えるターム集合・文書集
合縮小部２ｈにより構成する。

【００６８】このような構成により、本例の情報検索分
類システムでは、ユーザが検索質問を入力すると、検索
質問との関連度が大きい文書を検索して、相互に類似度
の高い文書からなるクラスタを抽出し、クラスタのダイ
ジェストを表示する。そして、表示したクラスタから、
ユーザが情報要求に関連の強そうなクラスタを選択する
と、処理を戻し、選択されたクラスタから、より小さな
クラスタを抽出し、そのダイジェストを表示する。

【００６９】このように、タームによる検索とクラスタ
リングを組合わせることにより、ユーザが想起した検索
質問からスタートして、クラスタリングとクラスタ選択
のサイクルを繰り返し、適合文書を含むクラスタを段階
的に絞っていくことにより、ユーザは効率良く適合文書
に到達することができる。また、検索された文書の数に
あまり影響されない高速なクラスタリングが可能であ
り、従来技術のように対話性を損なうことがない。尚、
本発明は、図１〜図１６を用いて説明した実施例に限定
されるものではなく、その要旨を逸脱しない範囲におい
て種々変更可能である。

【００７０】

【発明の効果】本発明によれば、クラスタリングに要す
る計算量を十分に小さくすることができ、高速な情報の
検索分類が可能となり、ユーザは、対話的操作のストレ
スを感じることなく、所望の情報を効率良く探し出すこ
とができる。

【図面の簡単な説明】

【図１】本発明の情報検索分類システムの本発明に係る
構成の一実施例を示すブロック図である。

【図２】図１における情報検索分類システムを構成する
コンピュータの構成例を示すブロック図である。

【図３】図１における文書ファイルのレコード構成例を
示す説明図である。

【図４】図１における文書特徴ファイルのレコード構成
例を示す説明図である。

【図５】図１におけるインデクスファイルのレコード構
成例を示す説明図である。

【図６】図１におけるターム相関ファイルのレコード構
成例を示す説明図である。

【図７】図１における検索サブシステムの詳細な構成例
を示すブロック図である。

【図８】図７における検索質問データの構成例を示す説
明図である。

【図９】図７における検索文書集合データの構成例を示
す説明図である。

【図１０】図７における関連ターム集合データの構成例
を示す説明図である。

【図１１】図７におけるタームクラスタデータの構成例
を示す説明図である。

【図１２】図７における文書クラスタデータの構成例を
示す説明図である。

【図１３】図７におけるクラスタ番号データの構成例を
示す説明図である。

【図１４】図７における文書クラスタ表示制御部により
表示された文書クラスタダイジェストの表示例を示す説
明図である。

【図１５】本発明の情報検索分類方法に係わる一実施例
を示すフローチャートの蓄積サブシステム処理部分であ
る。

【図１６】本発明の情報検索分類方法に係わる一実施例
を示すフローチャートの検索サブシステム処理部分であ
る。

【符号の説明】

１：蓄積サブシステム、１ａ：文書登録部、１ｂ：文書
特徴抽出部、１ｃ：インデクスファイル生成部、１ｄ：
ターム相関抽出部、２：検索サブシステム、２ａ：関連
ターム選出部、２ｂ：タームクラスタ生成部、２ｃ：文
書検索部、２ｄ：文書クラスタ生成部、２ｅ：文書クラ
スタ表示制御部、２ｆ：検索質問読込み部、２ｇ：クラ
スタ番号読込み部、２ｈ：およびターム集合・文書集合
縮小部、１０ａ：文書ファイル、１０ｂ：文書特徴ファ
イル、１０ｃ：インデクスファイル、１０ｄ：ターム相
関ファイル、１０ｅ：検索質問データ、１０ｆ：検索文
書集合データ、１０ｇ：関連ターム集合データ、１０
ｈ：タームクラスタデータ、１０ｉ：文書クラスタデー
タ、１０ｊ：クラスタ番号データ、２１：処理装置、２
２：記憶装置、２３：文書入力装置、２４：入力装置、
２５：表示装置、３１：文書ＩＤ、３２：テキストデー
タ、４１：文書ＩＤ、４２：タームベクトル、４２ａ：
ターム、４２ｂ：重み、５１：ターム、５２：ターム出
現文書情報、５２ａ：文書ＩＤ、５２ｂ：重み、６１：
ターム、６２：相関ターム情報、６２ａ：ターム、６２
ｂ：相関度、８１：論理オペレータ、８２：ターム、９
１：文書ＩＤ、１０１：ターム、１１１：クラスタ番
号、１１２：ターム、１２１：クラスタ番号、１２２：
文書ＩＤ、１２３：類似度、１３１：クラスタ番号。

Claims

【特許請求の範囲】

【請求項１】文書ファイルに蓄積した文書の集合か
ら、入力された検索質問に関連の強い文書を、上記検索
質問に含まれたタームとの関連に基づき検索して分類す
る装置の情報検索分類方法であって、予め、上記文書フ
ァイルに蓄積した文書の集合からタームの相関に関する
情報を抽出して登録する第１のステップと、上記検索質
問に関連の強いものとして検索した文書の集合から、上
記タームの相関に関する情報を利用して、文書クラスタ
を生成する第２のステップとを有し、上記文書クラスタ
別に検索分類結果を出力することを特徴とする情報検索
分類方法。
【請求項２】請求項１に記載の情報検索分類方法にお
いて、上記出力した文書クラスタからユーザが選択した
文書クラスタに含まれる文書を対象として、上記第２の
ステップによる上記文書クラスタの生成を繰り返すこと
を特徴とする情報検索分類方法。
【請求項３】文書ファイルに蓄積した文書の集合か
ら、入力された検索質問に関連の強い文書を、上記検索
質問に含まれたタームとの関連に基づき検索して分類す
る装置の情報検索分類方法であって、予め、上記文書フ
ァイルに蓄積した文書の集合からタームの相関に関する
情報を抽出して登録する第１のステップと、上記ターム
の相関に関する情報を利用して、上記検索質問に含まれ
たタームに関連するタームを選択し、該選択したターム
の集合からタームクラスタを生成する第２のステップ
と、上記タームクラスタを種として、上記検索質問に関
連の強いものとして検索した文書の集合から、文書クラ
スタを生成する第３のステップとを有し、上記文書クラ
スタ別に検索分類結果を出力することを特徴とする情報
検索分類方法。
【請求項４】請求項３に記載の情報検索分類方法にお
いて、上記第２のステップは、上記検索質問に含まれた
タームに関連するタームを、上記第１のステップで抽出
したタームの相関に関する情報に基づき選出し、選出し
たタームの集合から上記タームクラスタを上記タームの
相関に関する情報に基づき生成することを特徴とする情
報検索分類方法。
【請求項５】請求項３、もしくは、請求項４のいずれ
かに記載の情報検索分類方法において、上記第３のステ
ップは、上記検索された文書に予め対応付けられたター
ムの集合と上記タームクラスタとの類似度を求め、最も
類似度の大きいタームクラスタに上記文書を割り当てる
ことにより、上記文書クラスタを生成することを特徴と
する情報検索分類方法。
【請求項６】請求項３から請求項５のいずれかに記載
の情報検索分類方法において、上記出力した文書クラス
タからユーザが選択した文書クラスタに含まれる文書、
および、上記ユーザが選択した文書クラスタの種となっ
たタームクラスを対象として、上記第２のステップによ
る上記タームの相関に関する情報を利用した上記ターム
クラスタの生成と、上記第３のステップによる上記ター
ムクラスタを種とした上記文書クラスタの生成を繰り返
すことを特徴とする情報検索分類方法。
【請求項７】請求項３から請求項６のいずれかに記載
の情報検索分類方法において、上記文書クラスタの種に
なったタームクラスタを、上記文書クラスタ別の検索分
類結果の一情報として出力することを特徴とする情報検
索分類方法。
【請求項８】請求項１から請求項７のいずれかに記載
の情報検索分類方法において、上記第１のステップは、
文書中の予め定めたサイズ内で共起するタームの組と共
起頻度を求め、上記共起頻度に基づき上記ターム間の相
関度を算出し、上記相関度が予め定めた値を超えるター
ムの組を相関度を付与して対応付け、上記タームの相関
に関する情報を抽出することを特徴とする情報検索分類
方法。
【請求項９】請求項１から請求項８のいずれかに記載
の情報検索分類方法において、上記文書クラスタに含ま
れる文書の一部を、上記文書クラスタ別の検索分類結果
の一情報として出力することを特徴とする情報検索分類
方法。
【請求項１０】文書ファイルに蓄積した文書の集合か
ら、入力された検索質問に関連の強い文書を、上記検索
質問に含まれるタームとの関連に基づき検索し分類する
情報検索分類システムであって、予め、上記文書ファイ
ルに蓄積した文書の集合からタームの相関に関する情報
を抽出して登録する登録手段と、上記検索質問に含まれ
るタームに関連するタームを上記登録手段から選出し、
相互に相関の強いタームからなる複数のタームクラスタ
を生成するタームクラスタ生成手段と、上記検索質問に
関連の強い文書を上記文書ファイルから検索して、類似
度の最も高い上記タームクラスタに割り当てて、上記タ
ームクラスタを種とした文書のクラスタを生成する文書
クラスタ生成手段と、上記文書のクラスタ毎に、該文書
のクラスタの種となった上記タームのクラスタと文書の
一部をユーザに提示する提示手段とを有することを特徴
とする情報検索分類システム。
【請求項１１】請求項１０に記載の情報検索分類シス
テムにおいて、上記登録手段は、文書中の予め定めたサ
イズ内で共起するタームの組と共起頻度を求め、上記共
起頻度に基づき上記ターム間の相関度を算出し、上記相
関度が予め定めた値を超えるタームの組を相関度を付与
して対応付け、上記タームの相関に関する情報を抽出す
る手段からなることを特徴とする情報検索分類システ
ム。
【請求項１２】請求項１０、もしくは、請求項１１の
いずれかに記載の情報検索分類システムにおいて、上記
タームクラスタ生成手段による上記タームクラスタの生
成に用いるタームと、上記文書クラスタ生成手段による
上記文書のクラスタの生成に用いる文書を、上記提示手
段で提示した各文書のクラスタからユーザが選択したク
ラスタのタームおよび文書に絞り込む手段を設け、上記
提示手段での提示および上記ユーザによる文書のクラス
タの選択を繰り返すことにより、上記文書クラスタの絞
り込みを行うことを特徴とする情報検索分類システム。