(57)【要約】【課題】無駄な正解付与及びクラスタリング操作を行わない文書分類支援装置を提供する。【解決手段】プロセッサと、前記プロセッサに接続されるメモリと、を備え、与えられた正しい分類先に基づいて、複数の文書を分類する文書分類装置は、入力部と、分類制御部と、発散度計算部と、進捗度計算部と、を備え、前記入力部は、ユーザから入力された文書の前記正しい分類先を受け付け、前記分類制御部は、前記文書の正しい分類先に基づいて、前記複数の文書を複数のグループに分類し、前記発散度計算部は、前記分類によって前記グループが変化した文書数によって示される発散度を算出し、前記進捗度計算部は、前記分類の進捗度を算出し、前記分類制御部によって文書を分類した結果と、前記発散度計算部によって算出された発散度と、文書分類装置は、前記進捗度計算部によって算出された進捗度とを表示する。【選択図】図１
2010182253.tif 000002
【特許請求の範囲】
【請求項１】
プロセッサと、前記プロセッサに接続されるメモリと、を備え、与えられた正しい分類先に基づいて、複数の文書を分類する文書分類装置であって、
入力部と、分類制御部と、発散度計算部と、進捗度計算部と、を備え、
前記入力部は、ユーザから入力された文書の前記正しい分類先を受け付け、
前記分類制御部は、前記文書の正しい分類先に基づいて、前記複数の文書を複数のグループに分類し、
前記発散度計算部は、前記分類によって前記グループが変化した文書数によって示される発散度を算出し、
前記進捗度計算部は、前記分類の進捗度を算出し、
前記分類制御部によって文書を分類した結果と、前記発散度計算部によって算出された発散度と、前記進捗度計算部によって算出された進捗度とを表示するためのデータを生成することを特徴とする文書分類装置。
【請求項２】
前記発散度計算部は、１回の分類ごとの前記発散度を前記グループごとに算出し、
複数回の前記分類において算出された前記発散度を一つの画面に表示するためのデータを生成することを特徴とする請求項１に記載の文書分類装置。
【請求項３】
前記進捗度計算部は、前記算出された発散度と、前記分類の回数と、前記正しい分類先が入力された文書数とに基づいて前記進捗度を算出することを特徴とする請求項１に記載の文書分類装置。
【請求項４】
前記分類した結果と、前記算出された発散度と、前記算出された進捗度とを１回の分類ごとに表示するためのデータを生成することを特徴とする請求項１に記載の文書分類装置。
【請求項５】
前記分類によって所属する文書の数が変化したグループと、所属する文書の数が変化しなかったグループとを識別可能に表示するためのデータを生成することを特徴とする請求項１に記載の文書分類装置。
【請求項６】
プロセッサと、前記プロセッサに接続されるメモリと、を備え、与えられた正しい分類先に基づいて、複数の文書を分類する文書分類装置における文書分類方法であって、
前記文書分類方法は、
前記プロセッサが、ユーザから入力された文書の前記正しい分類先を受け付け、
前記プロセッサが、前記文書の正しい分類先に基づいて、前記複数の文書を複数のグループに分類し、
前記分類結果を前記メモリに格納し、
前記プロセッサが、前記分類によって前記グループが変化した文書数によって示される発散度を算出し、
前記プロセッサが、前記分類の進捗度を算出し、
前記プロセッサが、前記メモリに、前記分類した結果と、前記算出された発散度と、前記算出された進捗度とを格納し、
前記プロセッサが、前記分類した結果と、前記算出された発散度と、前記算出された進捗度とを表示するためのデータを生成することを特徴とする文書分類方法。
【請求項７】
前記プロセッサが、１回の分類ごとの前記発散度を前記グループごとに算出し、
前記プロセッサが、複数回の前記分類において算出された前記発散度を一つの画面に表示するためのデータを生成することを特徴とする請求項６に記載の文書分類方法。
【請求項８】
前記プロセッサが、前記算出された発散度と、前記分類の回数と、前記正しい分類先が入力された文書数とに基づいて前記進捗度を算出することを特徴とする請求項６に記載の文書分類方法。
【請求項９】
前記プロセッサが、前記分類した結果と、前記算出された発散度と、前記算出された進捗度とを１回の分類ごとに表示するためのデータを生成することを特徴とする請求項６に記載の文書分類方法。
【請求項１０】
前記プロセッサが、前記分類によって所属する文書の数が変化したグループと、所属する文書の数が変化しなかったグループとを識別可能に表示するためのデータを生成することを特徴とする請求項６に記載の文書分類方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書分類装置に関し、特に制約付きクラスタリングを用いた文書分類装置に関する。
【背景技術】
【０００２】
従来、文書検索システムなどによって収集された大量の文書を、各々の文書の内容に従って、いくつかのカテゴリに分類する場合、クラスタリング（集団化）などの機械的な方法を用いて、大量の文書を自動的に分類する方法が一般的に用いられる。機械的な方法による文書の分類とは、文書の中に存在する単語の出現頻度に基づいた特徴量を、その文書のベクトルの要素とし、その文書が持つベクトルと、他の文書が持つベクトルの類似度等に基づいて、文書を分類する方法である。
【０００３】
クラスタリングの代表的な方法には、Ｋ−Ｍｅａｎｓ法がある。Ｋ−Ｍｅａｎｓ法は、予め設定したクラスタ（集団）の数をｋ個とした場合、以下の操作によってデータ集合を分類する方法である（例えば、非特許文献１参照）。なお、クラスタリングとは、文書の集団化、又は文書の分類の意である。
【０００４】
１．文書の集合の中から、ｋ個の個体（文書）をランダムに決定し、各クラスタの重心とする。
【０００５】
２．集合の中の各個体と、重心との距離（もしくは、類似度）を、各々の個体のベクトルに基づいて算出し、最も近い重心のクラスタに分類する。
【０００６】
３．上記２．において作成したクラスタの、各々のクラスタにおける新たな重心をランダムに決定し、各個体と新たな重心との距離（もしくは、類似度）を算出する。
【０００７】
４．上記２．において用いた重心と、３．において決定した新たな重心との移動距離（例えば、（旧重心−新重心）2の総和）がある閾値以下でなければ２．へ戻る。
【０００８】
５．Ｋ−Ｍｅａｎｓ法の終了。
【０００９】
Ｋ−Ｍｅａｎｓ法によるクラスタリングは、一度に大量の文書を分類できるが、重心をランダムに決定することによって、分類する精度が十分ではない場合が多く、ユーザの意図どおりに分類された結果にならない場合が多い。
【００１０】
これに対して、ユーザが意図する分類を、制約として、クラスタリングに組み込むことで、分類する精度を向上させる方法がある。つまり、任意の文書の正解、すなわち任意の文書が所属するべき分類先を、ユーザがその文書に付与し、それらの正解が付与された文書を教師データとすることによって、クラスタリングの精度を向上させる方法がある。この方法は、制約付きクラスタリング（もしくは、半教師有りクラスタリング）と呼ばれている（例えば、非特許文献２参照）。
【００１１】
この制約付きクラスタリングの利用は、クラスタリングの精度を効率的に向上させる。例えば、制約付きクラスタリングを利用したクラスタリング方法、すなわち分類方法に、学習型分類方法がある。
【００１２】
学習型分類方法は、非特許文書１に記載されているＫ−Ｍｅａｎｓ法に基づいて、文書の集合に対して、ユーザによる正解の付与を含む制約付きクラスタリングを繰り返すことによって、クラスタリングの結果をユーザが意図する分類へ近付けていく方法である。
【００１３】
また、学習型分類方法には、Ｋ−Ｍｅａｎｓ法の他に、ファジイクラスタリングに基づく学習型分類方法（例えば、特許文献１参照）、又はサポートベクトルマシンに基づく学習型分類方法（例えば、特許文献２参照）などがある。
【００１４】
ファジイクラスタリングを用いた学習型分類方法は、Ｋ−Ｍｅａｎｓ法によるクラスタリングと同様に、あらかじめ与えられた数のクラスタにおいて、各々の代表となる個体を定め、全体の集合の中の各個体と、代表となる個体との関係において、所属率を算出する。ファジイクラスタリングを用いた場合、各個体は、各クラスタに対して所属率、すなわち、どれくらい所属するかの数値を各々持つ。しかし、ファジイクラスタリングを用いた場合、ユーザにとって各個体がどのクラスタに所属するのかが曖昧になり、ユーザが意図した分類とならない場合が多い。
【００１５】
サポートベクトルマシンを用いた学習型分類方法は、二つのクラスのいずれかに属する事例を正解の事例とし、未知の事例がいずれのクラスに属する事例かを、正解の事例に基づいて判定する分類方法である。サポートベクトルマシンに基づく学習型分類方法は、正解の事例を作成する作業を必要とし、この作業に大きなコストを必要とする。また、基本的には二つのクラスを識別する方法であるため、複数のクラスに識別することができない。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】特開平９−３０５５６６公報
【特許文献２】特開２００４−０２１５９０公報
【非特許文献】
【００１７】
【非特許文献１】Ｔｒｅｖｏｒ  Ｈａｓｔｉｅ、外２名、"Ｔｈｅ  Ｅｌｅｍｅｎｔｓ  ｏｆ  Ｓｔａｔｉｓｔｉｃａｌ  Ｌｅａｒｎｉｎｇ：Ｄａｔａ  Ｍｉｎｉｎｇ，  Ｉｎｆｅｒｅｎｃｅ，  ａｎｄ  Ｐｒｅｄｉｃｔｉｏｎ"、ＵＳＡ、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、２００３年
【非特許文献２】Ｓｕｇａｔｏ  Ｂａｓｕ、外２名、"Ｓｅｍｉ−ｓｕｐｅｒｖｉｓｅｄ  Ｃｌｕｓｔｅｒｉｎｇ  ｂｙ  Ｓｅｅｄｉｎｇ"、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １９ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ、２００２年、ｐｐ．１９−２６
【非特許文献３】Ｃｈｒｉｓｔｏｐｈｅｒ  Ｄ．  Ｍａｎｎｉｎｇ、＆  Ｈｉｎｒｉｃｈ  Ｓｃｈｕｔｚｅ、"Ｆｏｕｎｄａｔｉｏｎｓ  ｏｆ  Ｓｔａｔｉｓｔｉｃａｌ  Ｎａｔｕｒａｌ  Ｌａｎｇｕａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ"、ＵＳＡ、ＭＩＴ  Ｐｒｅｓｓ、１９９９年
【発明の概要】
【発明が解決しようとする課題】
【００１８】
従来の学習型分類方法を用いた場合、クラスタリングの精度を向上するための、ユーザが正解を付与すべき文書の適切な量を、ユーザは予測することができない。このため、ユーザは、文書に正解を付与する操作を無駄に続けてしまう場合がある。
【００１９】
例えば、ユーザが任意の文書に正解を付与し、それら正解を付与された文書に基づいた制約付きクラスタリングを繰り返すような学習型分類方法（つまり、正解付与→制約付きクラスタリング→正解付与→制約付きクラスタリング→．．．の繰り返しにより、文書を正しい分類先に仕分けていく操作）は、以下のように、無駄な正解の付与が続けられる。
【００２０】
繰り返し行われる制約付きクラスタリングの，最初の段階においては、ユーザが文書に正解を付与するほど、正解が付与された文書数以上にクラスタリングの精度が向上していく。例えば、ある文書の集合に５件の正解を付与した（正解が付与された文書の量：５）場合、制約付きクラスタリングにより（５＋Ａ）件の文書が正解に分類される。この（正解が付与された文書の量＋Ａ）は、一度の制約付きクラスタリングにより、正しい分類先にクラスタリングされた文書数を示し、Ａは制約付きクラスタリングの学習効果と呼ばれる。
【００２１】
制約付きクラスタリングの学習効果の値Ａは、正解の付与を始める最初の段階においては大きな値である。しかし、正解の付与とクラスタリングとを繰り返し、ある一定の正解が付与された文書の量に達すると、制約付きクラスタリングの精度は、与えた正解が付与された文書の量以上に上がらなくなる。つまり、一定の正解が付与された文書の量に達すると、学習効果Ａは０に近い値になってしまう。
【００２２】
ユーザは、制約付きクラスタリングの精度が上がらなくなる量がどの程度であるかを知る手掛かりを持たない。このため、制約付きクラスタリングによる学習効果Ａが０であることにユーザは気付かず、無駄な正解の付与とクラスタリングとの操作を繰り返し続けてしまう。
【００２３】
上記のように、学習効果Ａが０であることに気付かなかい場合、ユーザは文書の全件に正解を付与してしまう事態も考えられる。本来、クラスタリングに代表される自動分類手法は、文書全件の中身を精査して仕分ける作業を軽減することが目的であるため、これでは意味がない。
【００２４】
本発明は、最も制約付きクラスタリングの精度が上がる正解を付与する文書の量を、ユーザに認知させることを目的とする。
【課題を解決するための手段】
【００２５】
本発明の代表的な一例を示せば以下の通りである。すなわち、プロセッサと、前記プロセッサに接続されるメモリと、を備え、与えられた正しい分類先に基づいて、複数の文書を分類する文書分類装置は、入力部と、分類制御部と、発散度計算部と、進捗度計算部と、を備え、前記入力部は、ユーザから入力された文書の前記正しい分類先を受け付け、前記分類制御部は、前記文書の正しい分類先に基づいて、前記複数の文書を複数のグループに分類し、前記発散度計算部は、前記分類によって前記グループが変化した文書数によって示される発散度を算出し、前記進捗度計算部は、前記分類の進捗度を算出し、前記分類制御部によって文書を分類した結果と、前記発散度計算部によって算出された発散度と、文書分類装置は、前記進捗度計算部によって算出された進捗度とを表示するためのデータを生成する。
【発明の効果】
【００２６】
本発明の一実施形態によると、ユーザは、文書の分類の際に無駄な正解の付与とクラスタリングとを繰り返さない。
【図面の簡単な説明】
【００２７】
【図１】本発明の実施形態の文書分類支援装置を示したブロック図である。
【図２】本発明の実施形態の情報端末における文書分類の処理を示したフローチャートである。
【図３】本発明の実施形態の文書分類支援装置のクラスタリング結果表示画面を示した説明図である。
【図４】本発明の実施形態の文書データＤＢに含まれるテーブルを示した説明図である。
【図５】本発明の実施形態の文書インデックスＤＢに含まれるテーブルを示した説明図である。
【図６】本発明の実施形態のクラスタリングの処理を示したフローチャートである。
【図７】本発明の実施形態のクラスタリング前後での、各文書のクラスタラベルの変化を示した説明図である。
【図８】本発明の実施形態の分類作業進捗度を表示する画面を示した説明図である。
【図９】本発明の実施形態のクラスタリングの繰り返しによる、クラスタ発散度の履歴を表示する画面を示した図である。
【図１０】本発明の実施形態のクラスタリングによる各分類の文書のクラスタラベルの変化を示した説明図である。
【発明を実施するための形態】
【００２８】
本発明の実施形態において、ユーザによって正解を付与された文書による制約付きクラスタリングの学習効果と、クラスタリングにおける各文書の所属するクラスタの変化、すなわち、クラスタラベルの変化とは、高い相関がある。本実施形態において、制約付きクラスタリングによる学習効果が０になる場合の指標を、制約付きクラスタリングが収束するまでにクラスタラベルが変化した文書数の総和値によって示す。
【００２９】
なお、クラスタラベルとは、分類された文書群の個々を識別する識別子である。文書には、分類された先の文書群を示すクラスタラベルが付与される。
【００３０】
また、本発明の実施形態において用いる制約付きクラスタリング方法は、Ｋ−Ｍｅａｎｓ法である。
【００３１】
図１は、本発明の実施形態の文書分類支援装置を示すブロック図である。
【００３２】
本発明の実施形態の文書分類支援装置は、情報端末１０と、文書データＤＢ１１０及び文書インデックスＤＢ１１１の２つのデータベースと、ネットワーク１１２とを備える。情報端末１０及び２つのデータベースは、ネットワーク１１２によって接続されているが、情報端末１０が２つのデータベースを備えてもよい。
【００３３】
情報端末１０は、ＣＰＵ１０１と、メモリ１０２と、キーボード及びマウス１０３と、ディスプレイ１０４と、データ通信部１０９とを備える計算機である。また、情報端末１０は、機械分類制御部１０５、クラスタ発散度計算部１０６、進捗度計算部１０７、及び文書表示部１０８の機能を提供するプログラムを含む。
【００３４】
ＣＰＵ１０１は、機械分類制御部１０５、クラスタ発散度計算部１０６、進捗度計算部１０７及び文書表示部１０８の機能を持つプログラムを実行することによって、文書分類の処理を実行する。メモリ１０２は、ＣＰＵ１０１によって実行されるプログラム及びプログラムを実行するために必要なデータを一時的に記憶する。
【００３５】
キーボード及びマウス１０３は、ユーザが情報を入力する装置である。ディスプレイ１０４には、クラスタリング結果、後述するクラスタ発散度、及び後述する分類作業進捗度等が表示される。
【００３６】
機械分類制御部１０５は、情報端末１０に入力された文書を、クラスタリングする。クラスタ発散度計算部１０６は、クラスタリングの処理において、後述するクラスタ発散度を算出する。進捗度計算部１０７は、クラスタリングの処理において、後述する分類作業進捗度を算出する。文書表示部１０８は、クラスタリングの結果、後述するクラスタ発散度、及び後述する分類作業進捗度等を、ディスプレイ１０４に表示させる。
【００３７】
データ通信部１０９は、情報端末１０がネットワーク１１２を介してデータ通信をするインターフェースであり、例えば、ＴＣＰ／ＩＰプロトコルによって通信可能なＬＡＮカードである。情報端末１０は、データ通信部１０９を介してネットワーク１１２に接続された二つのデータベースと通信する。
【００３８】
文書データＤＢ１１０には、文書に関する情報が含まれる。文書データＤＢ１１０は、著者、又は書名などの書誌情報の検索に加え、文書全文の検索も可能にする。
【００３９】
文書インデックスＤＢ１１１には、文書とキーワードと出現頻度との対応関係が含まれる。文書インデックスＤＢ１１１は、ある文書が含むキーワードリストを提供する。
【００４０】
図２は、本発明の実施形態の情報端末における文書分類の処理を示したフローチャートである。
【００４１】
図２において、機械分類制御部１０５、クラスタ発散度計算部１０６、進捗度計算部１０７及び文書表示部１０８によって実行される文書分類の処理の概要を説明する。
【００４２】
まず、ユーザは、キーボード及びマウス１０３によって、予め文書検索システム等で収集した文書の集合を文書分類支援装置に入力する。この際、ユーザは、文書の集合に加えて、クラスタの数などのクラスタリングの条件を入力してもよい。クラスタリングの条件には、クラスタの数の他に、例えば、各クラスタを説明する代表的なキーワードなどがある。なお、入力されたキーワードに基づいて、重心を定めてもよい。入力された文書の集合は、文書データＤＢ１１０及び文書インデックスＤＢ１１１に格納される。
【００４３】
機械分類制御部１０５は、文書インデックスＤＢ１１１から、文書の集合内の各文書のキーワードと出現頻度とを取得する（Ｓ２０１）。
【００４４】
次に、機械分類制御部１０５は、Ｓ２０１において取得された各文書のキーワードの出現頻度に従ってクラスタリングをする。続いて、クラスタ発散度計算部１０６は、クラスタ発散度を算出する（Ｓ２０２）。クラスタ発散度の算出方法は、図６及び図７を用いて後述する。
【００４５】
次に、Ｓ２０２において得られたクラスタ発散度と文書への正解が付与された数とから、進捗度計算部１０７は、分類作業進捗度を算出する。分類作業進捗度の算出方法は、図８を用いて後述する。続いて、文書表示部１０８は、Ｓ２０２におけるクラスタリングの結果、Ｓ２０２において算出されたクラスタ発散度、及び分類作業進捗度をディスプレイ１０４に表示する（Ｓ２０３）。
【００４６】
ディスプレイ１０４に表示される画面の具体例は、図３にて後述する。なお、Ｓ２０３における分類作業の進捗度は、文書の集合を最初に入力した直後においては、まだ正解が付与されていないため、正解が付与された数を０として算出される。
【００４７】
ユーザは、Ｓ２０３においてディスプレイ１０４に表示されたクラスタリングの結果であるクラスタ発散度、及び分類作業進捗度に基づいて、文書分類の作業の終了可否を判定する（Ｓ２０４）。なお、ユーザは、クラスタ発散度が十分低い値になったか否か、又は、分類作業進捗度が、十分高い値になったか否かによって、終了の可否を判定する。
【００４８】
Ｓ２０４において判定されたクラスタリングの結果が、ユーザにとって所望の結果ではなく、ユーザによって情報端末１０に、分類の作業は終了不可であると入力された場合（Ｓ２０４において、Ｎｏと判定された場合）、ユーザは、各クラスタ内の文書に正解を付与する（Ｓ２０５）。Ｓ２０５の後、文書分類の処理は、Ｓ２０２に戻る。
【００４９】
なお、文書に正解を付与する操作には、正しく分類された文書に正しく分類された文書であることを明示する「固定」操作と、誤って分類された文書に正しいクラスタを指定する「移動」操作がある。
【００５０】
Ｓ２０４において判定されたクラスタリングの結果が、ユーザにとって所望の結果であり、ユーザによって情報端末１０に、分類の作業は終了可能であると入力された場合（Ｓ２０４において、Ｙｅｓと判定された場合）、本発明の文書分類支援装置を用いた文書分類作業を終了する。
【００５１】
以下において、Ｓ２０３におけるクラスタリングの結果の表示画面、文書データＤＢ１１０及び文書インデックスＤＢ１１１の詳細、並びに図２のＳ２０２及びＳ２０３に伴う算出の詳細を説明する。
【００５２】
図３は、本発明の実施形態の文書分類支援装置のクラスタリング結果表示画面３０１を示した説明図である。
【００５３】
クラスタリング結果表示画面３０１は、クラスタリング結果を表示する領域と、分類作業進捗度及びクラスタ発散度を表示する領域とを含む。また、クラスタリングする（図２のＳ２０２）ためのクラスタリングボタン３０２、正しく分類された文書に正しく分類された文書であることを明示するための固定ボタン３０３、及び誤って分類された文書に正しいクラスタを指定するための移動ボタン３０４が、クラスタリング結果表示画面３０１に含まれる。
【００５４】
クラスタリング結果を表示する領域は、クラスタリング結果表３０５を含む。クラスタリング結果表３０５は、縦軸と横軸との２つの軸によって文書の分類結果を表示する。縦軸と横軸とは、それぞれ異なる観点によって文書の集合を分類した結果である。例えば、横軸は、クラスタリングによって分類した結果であり、縦軸は文書データＤＢ１１０に格納した文書の書誌情報によって分類した結果であってもよい。また、縦軸及び横軸の両方が、クラスタリングによって分類した結果であってもよい。ユーザは、クラスタリング結果表３０５によって、クラスタリングの結果、各々の文書がどの分類に所属したのかを認識する。
【００５５】
縦分類３０６と横分類３０７とは、縦軸及び横軸のそれぞれにおける分類の名前を示す。文書リスト３０８には、縦分類３０６及び横分類３０７に所属する文書の名前がリスト表示される。
【００５６】
固定チェックボックス３０９は、固定チェックボックス３０９に対応する文書の所属分類が正しい場合、ユーザが「固定」したい文書を選択する。そして、ユーザが固定ボタン３０３を操作することによって、選択された文書の固定チェックボックス３０９にチェックが入力される。
【００５７】
また、固定チェックボックス３０９に対応する文書の所属分類が誤っている場合、ユーザは「移動」したい文書を選択し、移動ボタン３０４を操作することによって「移動」操作をする。ユーザは、移動ボタン３０４を操作することによって正しい分類先を指定し、選択された文書は指定した分類先に移動され、選択された文書の固定チェックボックス３０９に自動的にチェックが入力される。
【００５８】
なお、「移動」操作は、ユーザが移動ボタン３０４を操作した後、選択された文書の新たな分類先を指定する画面が表示され、ユーザが表示された画面に分類先を入力することによって、選択された文書は新たな分類先に移動し、固定チェックボックス３０９にチェックが自動的に入力されてもよい。また、ユーザがドラッグアンドドロップによって、選択された文書の表示を視覚的に新たな分類先に移動させ、移動ボタン３０４を操作した後に、選択された文書の固定チェックボックス３０９にチェックが入力されてもよい。
【００５９】
図２に示すＳ２０５の処理は、ユーザが固定ボタン３０３及び移動ボタン３０４によって、各文書に固定及び移動の操作をすることによって実行される。
【００６０】
進捗度・クラスタ発散度表示領域は、進捗度表示部３１０とクラスタ発散度履歴表示部３１１とを含む。
【００６１】
進捗度表示部３１０は、進捗度計算部１０７によって算出された分類作業進捗度を表示する。ユーザは、進捗度表示部３１０の表示によって、文書に対するクラスタリングの進捗を認識することができる。
【００６２】
クラスタ発散度履歴表示部３１１は、クラスタ発散度計算部１０６によって算出された、表示した時点における各クラスタリング処理で得たクラスタ発散度、すなわち、クラスタラベルが変化した文書数の総和値を表示する。ユーザは、クラスタ発散度履歴表示部３１１の表示によって、各々のクラスタリングにおいて、クラスタラベルが変化した文書の数を認識することができる。
【００６３】
分類作業進捗度の算出方法は図８を用いて後述し、クラスタ発散度の算出方法は図６及び図７を用いて後述する。
【００６４】
次に、図２に示す処理において使用されるデータベースのデータを説明する。
【００６５】
図４は、本発明の実施形態の文書データＤＢ１１０に含まれるテーブルを示した説明図である。
【００６６】
文書データＤＢ１１０における文書データを格納するテーブルは、文書番号４０１、著者４０２、発行年４０３、分類４０４及び全文４０５を含む。
【００６７】
文書番号４０１は、格納される文書の識別子である。著者４０２は、文書の著者名である。発行年４０３は、文書が発行された年である。分類４０４は、文書に付与された分類である。全文４０５は、文書の全文の内容である。なお、図４に示すテーブルの列要素は、対象文書の種類よって、追加または、変更されてもよい。
【００６８】
図５は、本発明の実施形態の文書インデックスＤＢ１１１に含まれるテーブルを示した説明図である。
【００６９】
文書インデックスＤＢ１１１には、文書中のキーワードによって文書をクラスタリングするためのインデックス５０１が含まれる。
【００７０】
インデックス５０１は、文書とクラスタとの類似度を算出するために使用される。
【００７１】
インデックス５０１は、文書番号５０２と、リスト５０３を含む。文書番号５０２は、格納される文書の識別子である。文書データＤＢ１１０における文書番号４０１と同じ値を示す。
【００７２】
リスト５０３は、（キーワード番号、頻度）の対を含む。キーワード番号は、対応する文書が含むキーワードの識別子である。頻度は、キーワードが文書中に出現する回数（出現頻度）である。
【００７３】
キーワードと出現頻度とに基づいて、類似度を算出することができる（例えば、「情報検索アルゴリズム」北研二他著、共立出版、２００２年発行  を参照）。例えば、あるキーワードの出現頻度が同程度の文書間には、高い類似度が算出される。
【００７４】
以下、図２に示すＳ２０２におけるクラスタ発散度の算出方法と、Ｓ２０３における分類作業進捗度の算出方法との詳細について説明する。
【００７５】
まず、図２に示すＳ２０２におけるクラスタリングには、Ｋ−Ｍｅａｎｓ法に基づく制約付きクラスタリングが用いられる。クラスタ発散度は、この制約付きクラスタリングと同時にクラスタ発散度計算部１０６によって算出される。Ｓ２０２における処理の詳細を図６に示す。
【００７６】
図６は、本発明の実施形態のクラスタリングの処理を示したフローチャートである。
【００７７】
文書の集合が情報端末１０に入力された（Ｓ２０１）、又は、図３に示す固定ボタン３０２及び移動ボタン３０４を用いて文書に正解を付与された（Ｓ２０５）後に、ユーザがクラスタリング結果表示画面３０１におけるクラスタリングボタン３０２を操作すると、Ｓ２０２が開始される。機械分類制御部１０５は、Ｓ２０２の処理の中で、文書の集合と文書インデックスＤＢ１１１に含まれるデータとによって、制約付きクラスタリングを実行する。
【００７８】
クラスタ発散度計算部１０６は、Ｓ２０２における制約付きクラスタリングが実行される前に、クラスタ発散度の値を０にする（Ｓ６０１）。クラスタ発散度計算部１０６は、各文書のクラスタラベルを保存する（Ｓ６０２）。本実施形態のクラスタラベルは、クラスタリング結果表３０５の縦分類３０６及び横分類３０７の分類名に対応する。
【００７９】
Ｓ６０２の処理の後、機械分類制御部１０５がクラスタリングを実行する（Ｓ６０３）。クラスタリングにはＫ−Ｍｅａｎｓ法に基づく制約付きクラスタリングを用いる。制約付きクラスタリングのアルゴリズムを、以下に示す。
【００８０】
１．図３に示す固定チェックボックス３０９に、チェックが入力された文書があるクラスタは、そのクラスタの中で、チェックが入力された文書全てを用いて重心を算出する。チェックが入力された文書が無いクラスタは、そのクラスタに所属する全ての文書を用いて重心を算出する。
【００８１】
２．各文書と重心との類似度を算出し、類似度が最も高い、すなわち最も近いことを示した重心のクラスタに、各文書を分類する。ただし、固定チェックボックス３０９にチェックが入力された文書は、類似度によって分類せず、クラスタラベルをそのまま維持する。
【００８２】
３．２．において分類されたクラスタに所属する文書の中で、新たな重心を算出する。
【００８３】
上記１．〜３．の制約付きクラスタリングが終了すると、クラスタ発散度計算部１０６は、Ｓ６０２において保存した各文書のクラスタラベルと、Ｓ６０３において得た各文書の新たなクラスタラベルとを比較し、クラスタラベルが変化した文書数を算出し、算出された文書数をクラスタ発散度に加算する。さらに、クラスタ発散度計算部１０６は、クラスタごとのクラスタラベルが変わった文書数も算出し、クラスタごとに算出された文書数をクラスタごとのクラスタ発散度に加算する（Ｓ６０４）。
【００８４】
図７は、本実施形態のクラスタリング前後における、各文書のクラスタラベルの変化を示した説明図である。
【００８５】
図７は、２０件の文書を、クラスタ数を３としてクラスタリングした場合の結果である。
【００８６】
左表７０１は、クラスタリング前の各文書のクラスタラベルの一覧であり（すなわち、Ｓ６０２において保存されたクラスタラベルに相当）、右表７０２は、クラスタリング結果後のクラスタラベルの一覧である（すなわち、Ｓ６０４において得られたクラスタラベルに相当）。
【００８７】
左表７０１と右表７０２とを比較すると、文書番号４、５、６、９、１０、１１、１２、１３、１９、２０を示す１０個の文書のクラスタラベルが変化したため、クラスタ発散度計算部１０６は、クラスタ発散度に１０を加算する。また、クラスタ１において２個（文書番号１９、２０）、クラスタ３において３個（文書番号４、５、６）、クラスタ３において５個（文書番号９、１０、１１、１２、１３）の文書のクラスタラベルが変化したため、クラスタ発散度計算部１０６は、各々のクラスタの各々のクラスタ発散度に加算する。
【００８８】
Ｓ６０４の後、機械分類制御部１０５は、クラスタリングが収束しているか否かを判定する（Ｓ６０５）。本実施形態の収束判定の方法には、例えば、非特許文献１に開示されるＫ−Ｍｅａｎｓ法における収束判定方法を用いる。すなわち、本実施形態の収束判定方法は、各々のクラスタリングによって得られる重心の変化量の閾値を管理者が予め定め、各々のクラスタリングによって得られる重心の変化量と、定められた閾値とに基づいて、収束しているか否かを判定する方法である。
【００８９】
Ｓ６０５において、クラスタリングは収束していないと判定された場合（Ｓ６０５においてＮｏを判定された場合）、Ｓ６０２からの同じ処理が繰り返される。Ｓ６０５において、クラスタリングは収束したと判定された場合は（Ｓ６０５においてＹｅｓと判定された場合）、図６に示すクラスタリングの処理を終了する。
【００９０】
Ｓ２０２におけるクラスタリングは、Ｓ６０５において収束されたと判定されるまで繰り返される（この繰り返しをループと呼ぶ）。例えば、ループが５回発生し、各々のループにおけるクラスタ発散度が、１０、９、６、４、０であった場合、最終的なクラスタ発散度は、（１０＋９＋６＋４＋０）＝２９となる。クラスタごとのクラスタ発散度の算出方法も、同じ算出方法である。
【００９１】
Ｓ２０２におけるクラスタリング処理が終了した後、文書表示部１０８は、クラスタ発散度と、後述する方法によって算出された分類作業進捗度とを表示する（Ｓ２０３）。
【００９２】
図２及び図６に示す処理によって、ユーザは、クラスタリングごとのクラスタ発散度と、分類作業進捗度を認識することができる。
【００９３】
分類作業進捗度は、進捗度計算部１０７によって数１を用いて算出される。
【００９４】
【数１】
2010182253.tif 000003
【００９５】
数１に示すクラスタ発散度は、Ｓ２０２において得られたクラスタ発散度である。数１に示すループ数は、図６に示すＳ６０２からＳ６０５の繰り返し数である。数１に示す固定文書数は、クラスタリング結果表３０５に表示された文書のうち、固定チェックボックス３０９にチェックが入力されている文書の数である。数１に示す全文書数は、文書全体に含まれる文書の数である。
【００９６】
数１に示すαは、クラスタリングとユーザの正解を付与する操作との、どちらを重視するかを示す重み係数であり、本発明の実施形態における文書分類支援装置の管理者が、予め設定してもよいし、ユーザが指定してもよい。αは、設定される値の範囲を、０≦α≦１．０とされるのが望ましい。
【００９７】
分類作業進捗度は、二つの指標に基づいて定められる。一つの指標は、分類対象となる文書の集合の何割に正解を付与したのか（正解付与進捗度）、であり、もう一つの指標は、クラスタリングによってどの程度ユーザが意図する分類になっているのか（クラスタリング安定度）、という点である。数１の分類作業進捗度の計算式において、分子の左側の項が、「文書の集合の何割に正解を付与したのか」に相当し、右側の項がどの程度ユーザが意図する分類になっているのか」に相当する。
【００９８】
αの値は、管理者が正解付与進捗度と、クラスタリング安定度との、二つの指標のどちらを重要とするかによって定められる。正解付与進捗度を重要としたい場合、管理者は、αの値を大きくし、クラスタリング安定度を重要としたい場合は、管理者は、αの値を小さくする。
【００９９】
数１に示す計算式によって求められる分類作業進捗度が、大きい値である場合、ユーザは、分類作業は進んでいると判定し、小さい場合は、分類作業は進んでいないと判定する。
【０１００】
なお、分類作業進捗度の表示方法は、図３に示す分類作業進捗度表示部３１０に示すように、数１に示す計算式に従って１つの結果を表示するが、数１の計算式の分子の２つの項を分けて、表示してもよい。つまり、分類作業進捗度表示部３１０を、図８に示す画面によって別々に表示してもよい。
【０１０１】
図８は、本発明の実施形態の分類作業進捗度を表示する画面を示した説明図である。
【０１０２】
図８に示す画面は、正解付与進捗度と、クラスタリング安定度とを表示する。図８に示す画面を用いる場合、正解付与進捗度の数値が大きいほど、分類作業が進んでいることを示し、クラスタリング安定度の数値が小さいほど、分類作業が進んでいることを示す。
【０１０３】
図９は、本発明の実施形態のクラスタリングの繰り返しによる、クラスタ発散度の履歴を表示する画面を示した説明図である。
【０１０４】
本実施形態においては、クラスタ発散度の履歴を棒グラフによって表す。
【０１０５】
図９に示す説明図の横軸は、一回のクラスタリング処理（Ｓ２０２の処理を一回分に相当）によって得たクラスタ発散度の値を示す。１回目、２回目、．．．、ｎ回目の表示は、文書への正解を付与し、クラスタリング（Ｓ２０２からＳ２０５）の繰り返し作業のうちの何回目に得た結果であるかを示す。
【０１０６】
図９に示す説明図の縦軸は、対応するクラスタリングにおいて得られたクラスタ発散度の値である。図９に示す説明図は、文書の集合を３つのクラスタに分類した場合であり、棒グラフは、各分類（クラスタリングにおけるそれぞれのクラスタに対応）に対応したクラスタ発散度の内訳を色によって識別できるように表示する。
【０１０７】
図９に示す表示によって、ユーザは、クラスタリング処理を繰り返すほど（横軸の左から右へ進むほど）棒グラフが低くなる、すなわちクラスタ発散度が０に近づくことを確認し、文書の集合の分類が、ユーザが意図する分類に近づいていることを、認識することが可能となる。
【０１０８】
さらに、ユーザは、各分類のクラスタ発散度から、どの分類がクラスタリングが収束していないか、すなわち、文書に正解を付与することが不十分であるか否かを確認できるため、どの分類に重点的に正解を付与すべきか方針を立てることができる。なお、正解の付与が不十分である分類は、クラスタリングを繰り返してもクラスタ発散度が減少しにくい。
【０１０９】
図１０は、本発明の実施形態のクラスタリングによる各分類の文書のクラスタラベルの変化を示した説明図である。
【０１１０】
図１０は、図３に示すクラスタリング結果表３０５とは別の、クラスタリング結果表３０５の表示である。図１０に示すクラスタリング結果表３０５によって、ユーザは、クラスタリングによって縦分類及び横分類に所属する文書に変化があった分類を認識する。
【０１１１】
図１０に示すクラスタリング結果表３０５の値の表示は、値１００１及び背景１００２で示される。
【０１１２】
値１００１は、クラスタリング結果表３０５における縦分類及び横分類に所属する文書の件数を示す
背景１００２は、クラスタリングの前後で文書件数に変化のあった分類の背景色を変化させることによって、変化のあった分類を強調する。強調される分類は、その分類に、クラスタリング前には無かった文書が新たに加わった分類である。従って、クラスタリングによって他分類へ文書が移動したことによって、所属する文書の件数が減少したのみの分類は、強調されない。また、クラスタリング前と比較して、所属する文書件数が減少し、新たな文書が追加された分類は、強調される。
【０１１３】
なお、文書が所属する分類の変化は、図６に示すＳ６０２の処理において保存されたクラスタリング前の分類と、Ｓ６０４の処理においてクラスタリング後の分類とを比較することによって、判定される。
【０１１４】
なお、図１０に示すクラスタリング結果表３０５は、所属する文書の件数を表示し、背景１００２を強調しているが、図３に示すクラスタリング結果表３０５の文書のリストを表示し、背景を強調してもよい。
【０１１５】
前述したように、本発明の実施形態によると、分類作業進捗度を表示することによって、ユーザは、文書へ正解を付与した数とクラスタ発散度に基づいたクラスタリング安定度との両方を加味した分類作業の進捗の程度を認識でき、クラスタリングに効果のない正解の付与の操作とクラスタリング操作とを繰り返す無駄を省くことが可能となる。
【０１１６】
また、クラスタリングによる分類の変化を、分類ごとに表示することによって、どの分類に正解を付与していくべきか方針を立てやすくなり、効果的なクラスタリングが可能となる。
【符号の説明】
【０１１７】
１０    情報端末
１０１  ＣＰＵ
１０２  メモリ
１０３  キーボード・マウス
１０４  ディスプレイ
１０５  機械分類制御部
１０６  クラスタ発散度計算部
１０７  進捗度計算部
１０８  文書表示部
１０９  データ通信部
１１０  文書データＤＢ
１１１  文書インデックスＤＢ
１１２  ネットワーク
【図１】
2010182253.tif 000004
【図２】
2010182253.tif 000005
【図４】
2010182253.tif 000006
【図５】
2010182253.tif 000007
【図６】
2010182253.tif 000008
【図７】
2010182253.tif 000009
【図１０】
2010182253.tif 000010
【図３】
2010182253.tif 000011
【図８】
2010182253.tif 000012
【図９】
2010182253.tif 000013