(57)【要約】【課題】文書群がクラスタリングされて得られるクラスタ群のクラスタ数を簡単に増やす。【解決手段】クラスタ生成装置１０は、Ｋ’個のクラスタを取得するクラスタ取得部１１と、分割処理を行ってＫ’個から（Ｋ’＋１）個のクラスタを生成するクラスタ生成部１２とを有する。分割処理では、上記各クラスタを、分割用キーワードを含む文書の集合である第１のクラスタと、含まない文書の集合である第２のクラスタとに仮想的に分割し、各第２のクラスタについて、当該第２のクラスタに含まれる各キーワードの、当該第２のクラスタの特徴を表す度合いを示す第２の度合い値を算出し、第２の度合い値に基づき１個のクラスタを仮想的に分割した通りに分割する。クラスタを分割する分割用キーワードは、当該クラスタに含まれるキーワードのうち、当該クラスタ内の全ての文書に含まれるものを除く、当該クラスタ内の最も多くの文書に含まれるキーワードである。【選択図】図１
2008204374.tif 000002
【特許請求の範囲】
【請求項１】
文書群がクラスタリングされて得られるＫ’個（Ｋ’は２以上の整数）のクラスタを取得するクラスタ取得手段と、
分割処理を行って、前記取得されたＫ’個のクラスタから（Ｋ’＋１）個のクラスタを生成するクラスタ生成手段と、を有し、
前記分割処理は、
前記Ｋ’個のクラスタの各々を、分割用キーワードを含む文書の集合である第１のクラスタと、前記分割用キーワードを含まない文書の集合である第２のクラスタとに仮想的に分割する処理と、
前記第２のクラスタの各々について、当該第２のクラスタに含まれる各キーワードの、当該第２のクラスタの特徴を表す度合いを示す第２の度合い値を算出する処理と、
前記第２の度合い値に基づき、前記Ｋ’個のクラスタのうち１個のクラスタを、前記仮想的に分割した通りに２つのクラスタに分割する処理と、を含み、
前記クラスタを仮想的に分割するための分割用キーワードは、当該クラスタに含まれるキーワードのうち、当該クラスタ内の全ての文書に含まれるキーワードを除く、当該クラスタ内の最も多くの文書に含まれるキーワードである、
ことを特徴とするクラスタ生成装置。
【請求項２】
文書群を所定のクラスタリング処理によりクラスタリングして、予め指定されたクラスタ数Ｋ（Ｋは２以上の整数）以下のＫ’個（Ｋ’は２以上の整数）のクラスタを生成する第１のクラスタ生成手段と、
前記生成されたクラスタの個数Ｋ’が前記指定されたクラスタ数Ｋに満たない場合に、分割処理を（Ｋ−Ｋ’）回行って、前記Ｋ’個のクラスタからＫ個のクラスタを生成する第２のクラスタ生成手段と、を有し、
前記１回目の分割処理では、前記Ｋ’個のクラスタが処理対象とされ、前記ｎ回目（２≦ｎ≦（Ｋ−Ｋ’））の分割処理では、（ｎ−１）回目の分割処理後の（Ｋ’＋ｎ−１）個のクラスタが処理対象とされ、
前記分割処理は、
前記処理対象の複数のクラスタの各々を、分割用キーワードを含む文書の集合である第１のクラスタと、前記分割用キーワードを含まない文書の集合である第２のクラスタとに仮想的に分割する処理と、
前記第２のクラスタの各々について、当該第２のクラスタに含まれる各キーワードの、当該第２のクラスタの特徴を表す度合いを示す第２の度合い値を算出する処理と、
前記第２の度合い値に基づき、前記処理対象の複数のクラスタのうち１個のクラスタを、前記仮想的に分割した通りに２つのクラスタに分割する処理と、を含み、
前記クラスタを仮想的に分割するための分割用キーワードは、当該クラスタに含まれるキーワードのうち、当該クラスタ内の全ての文書に含まれるキーワードを除く、当該クラスタ内の最も多くの文書に含まれるキーワードである、
ことを特徴とするクラスタ生成装置。
【請求項３】
請求項１または２に記載のクラスタ生成装置であって、
前記２つのクラスタに分割する処理では、前記第２の度合い値のうち最大のものに対応するクラスタを分割することを特徴とするクラスタ生成装置。
【請求項４】
請求項１または２に記載のクラスタ生成装置であって、
前記分割処理は、前記第１のクラスタの各々について、当該第１のクラスタに含まれる各キーワードの、当該第１のクラスタの特徴を表す度合いを示す第１の度合い値を算出する処理をさらに含み、
前記２つのクラスタに分割する処理では、前記第１および第２の度合い値に基づいて分割を行う、
ことを特徴とするクラスタ生成装置。
【請求項５】
請求項４に記載のクラスタ生成装置であって、
前記２つのクラスタに分割する処理は、
前記処理対象の複数のクラスタの各々について、前記第１の度合い値の最大値と前記第２の度合い値の最大値との和を算出する処理と、
前記算出された和のうち最大のものに対応するクラスタを分割する処理と、
を含むことを特徴とするクラスタ生成装置。
【請求項６】
文書群がクラスタリングされて得られるＫ’個（Ｋ’は２以上の整数）のクラスタを取得するクラスタ取得手段と、
分割処理を行って、前記取得されたＫ’個のクラスタから（Ｋ’＋１）個のクラスタを生成するクラスタ生成手段と、を有し、
前記分割処理は、
前記Ｋ’個のクラスタの各々を、分割用キーワードを含む文書の集合である第１のクラスタと、前記分割用キーワードを含まない文書の集合である第２のクラスタとに仮想的に分割する処理と、
前記第１のクラスタの各々について、当該第１のクラスタに含まれる各キーワードの、当該第１のクラスタの特徴を表す度合いを示す第１の度合い値を算出する処理と、
前記第１の度合い値に基づき、前記Ｋ’個のクラスタのうち１個のクラスタを、前記仮想的に分割した通りに２つのクラスタに分割する処理と、を含み、
前記クラスタを仮想的に分割するための分割用キーワードは、当該クラスタに含まれるキーワードのうち、当該クラスタ内の全ての文書に含まれるキーワードを除く、当該クラスタ内の最も多くの文書に含まれるキーワードである、
ことを特徴とするクラスタ生成装置。
【請求項７】
文書群を所定のクラスタリング処理によりクラスタリングして、予め指定されたクラスタ数Ｋ（Ｋは２以上の整数）以下のＫ’個（Ｋ’は２以上の整数）のクラスタを生成する第１のクラスタ生成手段と、
前記生成されたクラスタの個数Ｋ’が前記指定されたクラスタ数Ｋに満たない場合に、分割処理を（Ｋ−Ｋ’）回行って、前記Ｋ’個のクラスタからＫ個のクラスタを生成する第２のクラスタ生成手段と、を有し、
前記１回目の分割処理では、前記Ｋ’個のクラスタが処理対象とされ、前記ｎ回目（２≦ｎ≦（Ｋ−Ｋ’））の分割処理では、（ｎ−１）回目の分割処理後の（Ｋ’＋ｎ−１）個のクラスタが処理対象とされ、
前記分割処理は、
前記処理対象の複数のクラスタの各々を、分割用キーワードを含む文書の集合である第１のクラスタと、前記分割用キーワードを含まない文書の集合である第２のクラスタとに仮想的に分割する処理と、
前記第１のクラスタの各々について、当該第１のクラスタに含まれる各キーワードの、当該第１のクラスタの特徴を表す度合いを示す第１の度合い値を算出する処理と、
前記第１の度合い値に基づき、前記処理対象の複数のクラスタのうち１個のクラスタを、前記仮想的に分割した通りに２つのクラスタに分割する処理と、を含み、
前記クラスタを仮想的に分割するための分割用キーワードは、当該クラスタに含まれるキーワードのうち、当該クラスタ内の全ての文書に含まれるキーワードを除く、当該クラスタ内の最も多くの文書に含まれるキーワードである、
ことを特徴とするクラスタ生成装置。
【請求項８】
請求項６または７に記載のクラスタ生成装置であって、
前記２つのクラスタに分割する処理では、前記第１の度合い値のうち最大のものに対応するクラスタを分割することを特徴とするクラスタ生成装置。
【請求項９】
請求項２または７に記載のクラスタ生成装置であって、
前記所定のクラスタリング処理は、
単位クラスタリング処理を（Ｋ’−１）回行って、前記文書群から（Ｋ’−１）個のクラスタを生成する処理と、
前記文書群のうち前記（Ｋ’−１）個のクラスタの何れにも属していない文書群を１個のクラスタとする処理と、を含み、
前記単位クラスタリング処理は、前記文書群のうち未だ何れのクラスタにも属していない文書を未分類文書と呼ぶとき、前記文書群に属する各文書から抽出されるキーワードのうち最も多くの未分類文書に含まれるキーワードを含む未分類文書の集合を新たなクラスタとする処理である、
ことを特徴とするクラスタ生成装置。
【請求項１０】
請求項２または７に記載のクラスタ生成装置であって、
前記所定のクラスタリング処理は、
単位クラスタリング処理をＫ’回行って、前記文書群からＫ’個のクラスタを生成する処理と、
前記文書群のうち前記Ｋ’個のクラスタの何れにも属していない各文書を前記Ｋ’個のクラスタに分類する処理と、を含み、
前記単位クラスタリング処理は、前記文書群のうち未だ何れのクラスタにも属していない文書を未分類文書と呼ぶとき、前記文書群に属する各文書から抽出されるキーワードのうち最も多くの未分類文書に含まれるキーワードを含む未分類文書の集合を新たなクラスタとする処理である、
ことを特徴とするクラスタ生成装置。
【請求項１１】
コンピュータに、
文書群がクラスタリングされて得られるＫ’個（Ｋ’は２以上の整数）のクラスタを取得する手順と、
分割処理を行って、前記取得されたＫ’個のクラスタから（Ｋ’＋１）個のクラスタを生成する手順と、を実行させ、
前記分割処理は、
前記Ｋ’個のクラスタの各々を、分割用キーワードを含む文書の集合である第１のクラスタと、前記分割用キーワードを含まない文書の集合である第２のクラスタとに仮想的に分割する処理と、
前記第２のクラスタの各々について、当該第２のクラスタに含まれる各キーワードの、当該第２のクラスタの特徴を表す度合いを示す第２の度合い値を算出する処理と、
前記第２の度合い値に基づき、前記Ｋ’個のクラスタのうち１個のクラスタを、前記仮想的に分割した通りに２つのクラスタに分割する処理と、を含み、
前記クラスタを仮想的に分割するための分割用キーワードは、当該クラスタに含まれるキーワードのうち、当該クラスタ内の全ての文書に含まれるキーワードを除く、当該クラスタ内の最も多くの文書に含まれるキーワードである、
ことを特徴とするクラスタ生成プログラム。
【請求項１２】
コンピュータに、
文書群を所定のクラスタリング処理によりクラスタリングして、予め指定されたクラスタ数Ｋ（Ｋは２以上の整数）以下のＫ’個（Ｋ’は２以上の整数）のクラスタを生成する手順と、
前記生成されたクラスタの個数Ｋ’が前記指定されたクラスタ数Ｋに満たない場合に、分割処理を（Ｋ−Ｋ’）回行って、前記Ｋ’個のクラスタからＫ個のクラスタを生成する手順と、を実行させ、
前記１回目の分割処理では、前記Ｋ’個のクラスタが処理対象とされ、前記ｎ回目（２≦ｎ≦（Ｋ−Ｋ’））の分割処理では、（ｎ−１）回目の分割処理後の（Ｋ’＋ｎ−１）個のクラスタが処理対象とされ、
前記分割処理は、
前記処理対象の複数のクラスタの各々を、分割用キーワードを含む文書の集合である第１のクラスタと、前記分割用キーワードを含まない文書の集合である第２のクラスタとに仮想的に分割する処理と、
前記第２のクラスタの各々について、当該第２のクラスタに含まれる各キーワードの、当該第２のクラスタの特徴を表す度合いを示す第２の度合い値を算出する処理と、
前記第２の度合い値に基づき、前記処理対象の複数のクラスタのうち１個のクラスタを、前記仮想的に分割した通りに２つのクラスタに分割する処理と、を含み、
前記クラスタを仮想的に分割するための分割用キーワードは、当該クラスタに含まれるキーワードのうち、当該クラスタ内の全ての文書に含まれるキーワードを除く、当該クラスタ内の最も多くの文書に含まれるキーワードである、
ことを特徴とするクラスタ生成プログラム。
【請求項１３】
コンピュータに、
文書群がクラスタリングされて得られるＫ’個（Ｋ’は２以上の整数）のクラスタを取得する手順と、
分割処理を行って、前記取得されたＫ’個のクラスタから（Ｋ’＋１）個のクラスタを生成する手順と、を実行させ、
前記分割処理は、
前記Ｋ’個のクラスタの各々を、分割用キーワードを含む文書の集合である第１のクラスタと、前記分割用キーワードを含まない文書の集合である第２のクラスタとに仮想的に分割する処理と、
前記第１のクラスタの各々について、当該第１のクラスタに含まれる各キーワードの、当該第１のクラスタの特徴を表す度合いを示す第１の度合い値を算出する処理と、
前記第１の度合い値に基づき、前記Ｋ’個のクラスタのうち１個のクラスタを、前記仮想的に分割した通りに２つのクラスタに分割する処理と、を含み、
前記クラスタを仮想的に分割するための分割用キーワードは、当該クラスタに含まれるキーワードのうち、当該クラスタ内の全ての文書に含まれるキーワードを除く、当該クラスタ内の最も多くの文書に含まれるキーワードである、
ことを特徴とするクラスタ生成プログラム。
【請求項１４】
コンピュータに、
文書群を所定のクラスタリング処理によりクラスタリングして、予め指定されたクラスタ数Ｋ（Ｋは２以上の整数）以下のＫ’個（Ｋ’は２以上の整数）のクラスタを生成する手順と、
前記生成されたクラスタの個数Ｋ’が前記指定されたクラスタ数Ｋに満たない場合に、分割処理を（Ｋ−Ｋ’）回行って、前記Ｋ’個のクラスタからＫ個のクラスタを生成する手順と、を実行させ、
前記１回目の分割処理では、前記Ｋ’個のクラスタが処理対象とされ、前記ｎ回目（２≦ｎ≦（Ｋ−Ｋ’））の分割処理では、（ｎ−１）回目の分割処理後の（Ｋ’＋ｎ−１）個のクラスタが処理対象とされ、
前記分割処理は、
前記処理対象の複数のクラスタの各々を、分割用キーワードを含む文書の集合である第１のクラスタと、前記分割用キーワードを含まない文書の集合である第２のクラスタとに仮想的に分割する処理と、
前記第１のクラスタの各々について、当該第１のクラスタに含まれる各キーワードの、当該第１のクラスタの特徴を表す度合いを示す第１の度合い値を算出する処理と、
前記第１の度合い値に基づき、前記処理対象の複数のクラスタのうち１個のクラスタを、前記仮想的に分割した通りに２つのクラスタに分割する処理と、を含み、
前記クラスタを仮想的に分割するための分割用キーワードは、当該クラスタに含まれるキーワードのうち、当該クラスタ内の全ての文書に含まれるキーワードを除く、当該クラスタ内の最も多くの文書に含まれるキーワードである、
ことを特徴とするクラスタ生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クラスタ生成装置およびクラスタ生成プログラムに関する。
【背景技術】
【０００２】
文書群を複数のクラスタに分類するクラスタリング技術がある（例えば、特許文献１〜６参照）。クラスタリング技術の一つとして、階層型クラスタリング法がある。
【０００３】
【特許文献１】特開２００３−３４５８１１号公報
【特許文献２】特開２００５−０６３１５７号公報
【特許文献３】特開２００２−１８３１７１号公報
【特許文献４】特開２００１−３０６５９４号公報
【特許文献５】特開２０００−３０５９５０号公報
【特許文献６】特開２００１−０９２８４１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
文書群がクラスタリングされて得られるクラスタ群のクラスタ数を簡単に増やすことが可能なクラスタ生成装置またはクラスタ生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明に係るクラスタ生成装置は、文書群がクラスタリングされて得られるＫ’個（Ｋ’は２以上の整数）のクラスタを取得するクラスタ取得手段と、分割処理を行って、前記取得されたＫ’個のクラスタから（Ｋ’＋１）個のクラスタを生成するクラスタ生成手段と、を有し、前記分割処理は、前記Ｋ’個のクラスタの各々を、分割用キーワードを含む文書の集合である第１のクラスタと、前記分割用キーワードを含まない文書の集合である第２のクラスタとに仮想的に分割する処理と、前記第２のクラスタの各々について、当該第２のクラスタに含まれる各キーワードの、当該第２のクラスタの特徴を表す度合いを示す第２の度合い値を算出する処理と、前記第２の度合い値に基づき、前記Ｋ’個のクラスタのうち１個のクラスタを、前記仮想的に分割した通りに２つのクラスタに分割する処理と、を含み、前記クラスタを仮想的に分割するための分割用キーワードは、当該クラスタに含まれるキーワードのうち、当該クラスタ内の全ての文書に含まれるキーワードを除く、当該クラスタ内の最も多くの文書に含まれるキーワードである、ことを特徴とする。
【０００６】
また、本発明に係るクラスタ生成装置は、文書群を所定のクラスタリング処理によりクラスタリングして、予め指定されたクラスタ数Ｋ（Ｋは２以上の整数）以下のＫ’個（Ｋ’は２以上の整数）のクラスタを生成する第１のクラスタ生成手段と、前記生成されたクラスタの個数Ｋ’が前記指定されたクラスタ数Ｋに満たない場合に、分割処理を（Ｋ−Ｋ’）回行って、前記Ｋ’個のクラスタからＫ個のクラスタを生成する第２のクラスタ生成手段と、を有し、前記１回目の分割処理では、前記Ｋ’個のクラスタが処理対象とされ、前記ｎ回目（２≦ｎ≦（Ｋ−Ｋ’））の分割処理では、（ｎ−１）回目の分割処理後の（Ｋ’＋ｎ−１）個のクラスタが処理対象とされ、前記分割処理は、前記処理対象の複数のクラスタの各々を、分割用キーワードを含む文書の集合である第１のクラスタと、前記分割用キーワードを含まない文書の集合である第２のクラスタとに仮想的に分割する処理と、前記第２のクラスタの各々について、当該第２のクラスタに含まれる各キーワードの、当該第２のクラスタの特徴を表す度合いを示す第２の度合い値を算出する処理と、前記第２の度合い値に基づき、前記処理対象の複数のクラスタのうち１個のクラスタを、前記仮想的に分割した通りに２つのクラスタに分割する処理と、を含み、前記クラスタを仮想的に分割するための分割用キーワードは、当該クラスタに含まれるキーワードのうち、当該クラスタ内の全ての文書に含まれるキーワードを除く、当該クラスタ内の最も多くの文書に含まれるキーワードである、ことを特徴とする。
【０００７】
本発明の一態様では、前記２つのクラスタに分割する処理では、前記第２の度合い値のうち最大のものに対応するクラスタを分割する。
【０００８】
また、本発明の一態様では、前記分割処理は、前記第１のクラスタの各々について、当該第１のクラスタに含まれる各キーワードの、当該第１のクラスタの特徴を表す度合いを示す第１の度合い値を算出する処理をさらに含み、前記２つのクラスタに分割する処理では、前記第１および第２の度合い値に基づいて分割を行う。
【０００９】
また、本発明の一態様では、前記２つのクラスタに分割する処理は、前記処理対象の複数のクラスタの各々について、前記第１の度合い値の最大値と前記第２の度合い値の最大値との和を算出する処理と、前記算出された和のうち最大のものに対応するクラスタを分割する処理と、を含む。
【００１０】
また、本発明に係るクラスタ生成装置は、文書群がクラスタリングされて得られるＫ’個（Ｋ’は２以上の整数）のクラスタを取得するクラスタ取得手段と、分割処理を行って、前記取得されたＫ’個のクラスタから（Ｋ’＋１）個のクラスタを生成するクラスタ生成手段と、を有し、前記分割処理は、前記Ｋ’個のクラスタの各々を、分割用キーワードを含む文書の集合である第１のクラスタと、前記分割用キーワードを含まない文書の集合である第２のクラスタとに仮想的に分割する処理と、前記第１のクラスタの各々について、当該第１のクラスタに含まれる各キーワードの、当該第１のクラスタの特徴を表す度合いを示す第１の度合い値を算出する処理と、前記第１の度合い値に基づき、前記Ｋ’個のクラスタのうち１個のクラスタを、前記仮想的に分割した通りに２つのクラスタに分割する処理と、を含み、前記クラスタを仮想的に分割するための分割用キーワードは、当該クラスタに含まれるキーワードのうち、当該クラスタ内の全ての文書に含まれるキーワードを除く、当該クラスタ内の最も多くの文書に含まれるキーワードである、ことを特徴とする。
【００１１】
また、本発明に係るクラスタ生成装置は、文書群を所定のクラスタリング処理によりクラスタリングして、予め指定されたクラスタ数Ｋ（Ｋは２以上の整数）以下のＫ’個（Ｋ’は２以上の整数）のクラスタを生成する第１のクラスタ生成手段と、前記生成されたクラスタの個数Ｋ’が前記指定されたクラスタ数Ｋに満たない場合に、分割処理を（Ｋ−Ｋ’）回行って、前記Ｋ’個のクラスタからＫ個のクラスタを生成する第２のクラスタ生成手段と、を有し、前記１回目の分割処理では、前記Ｋ’個のクラスタが処理対象とされ、前記ｎ回目（２≦ｎ≦（Ｋ−Ｋ’））の分割処理では、（ｎ−１）回目の分割処理後の（Ｋ’＋ｎ−１）個のクラスタが処理対象とされ、前記分割処理は、前記処理対象の複数のクラスタの各々を、分割用キーワードを含む文書の集合である第１のクラスタと、前記分割用キーワードを含まない文書の集合である第２のクラスタとに仮想的に分割する処理と、前記第１のクラスタの各々について、当該第１のクラスタに含まれる各キーワードの、当該第１のクラスタの特徴を表す度合いを示す第１の度合い値を算出する処理と、前記第１の度合い値に基づき、前記処理対象の複数のクラスタのうち１個のクラスタを、前記仮想的に分割した通りに２つのクラスタに分割する処理と、を含み、前記クラスタを仮想的に分割するための分割用キーワードは、当該クラスタに含まれるキーワードのうち、当該クラスタ内の全ての文書に含まれるキーワードを除く、当該クラスタ内の最も多くの文書に含まれるキーワードである、ことを特徴とする。
【００１２】
本発明の一態様では、前記２つのクラスタに分割する処理では、前記第１の度合い値のうち最大のものに対応するクラスタを分割する。
【００１３】
また、本発明の一態様では、前記所定のクラスタリング処理は、単位クラスタリング処理を（Ｋ’−１）回行って、前記文書群から（Ｋ’−１）個のクラスタを生成する処理と、前記文書群のうち前記（Ｋ’−１）個のクラスタの何れにも属していない文書群を１個のクラスタとする処理と、を含み、前記単位クラスタリング処理は、前記文書群のうち未だ何れのクラスタにも属していない文書を未分類文書と呼ぶとき、前記文書群に属する各文書から抽出されるキーワードのうち最も多くの未分類文書に含まれるキーワードを含む未分類文書の集合を新たなクラスタとする処理である。
【００１４】
また、本発明の一態様では、前記所定のクラスタリング処理は、単位クラスタリング処理をＫ’回行って、前記文書群からＫ’個のクラスタを生成する処理と、前記文書群のうち前記Ｋ’個のクラスタの何れにも属していない各文書を前記Ｋ’個のクラスタに分類する処理と、を含み、前記単位クラスタリング処理は、前記文書群のうち未だ何れのクラスタにも属していない文書を未分類文書と呼ぶとき、前記文書群に属する各文書から抽出されるキーワードのうち最も多くの未分類文書に含まれるキーワードを含む未分類文書の集合を新たなクラスタとする処理である。
【００１５】
本発明に係るクラスタ生成プログラムは、コンピュータに、文書群がクラスタリングされて得られるＫ’個（Ｋ’は２以上の整数）のクラスタを取得する手順と、分割処理を行って、前記取得されたＫ’個のクラスタから（Ｋ’＋１）個のクラスタを生成する手順と、を実行させ、前記分割処理は、前記Ｋ’個のクラスタの各々を、分割用キーワードを含む文書の集合である第１のクラスタと、前記分割用キーワードを含まない文書の集合である第２のクラスタとに仮想的に分割する処理と、前記第２のクラスタの各々について、当該第２のクラスタに含まれる各キーワードの、当該第２のクラスタの特徴を表す度合いを示す第２の度合い値を算出する処理と、前記第２の度合い値に基づき、前記Ｋ’個のクラスタのうち１個のクラスタを、前記仮想的に分割した通りに２つのクラスタに分割する処理と、を含み、前記クラスタを仮想的に分割するための分割用キーワードは、当該クラスタに含まれるキーワードのうち、当該クラスタ内の全ての文書に含まれるキーワードを除く、当該クラスタ内の最も多くの文書に含まれるキーワードである、ことを特徴とする。
【００１６】
また、本発明に係るクラスタ生成プログラムは、コンピュータに、文書群を所定のクラスタリング処理によりクラスタリングして、予め指定されたクラスタ数Ｋ（Ｋは２以上の整数）以下のＫ’個（Ｋ’は２以上の整数）のクラスタを生成する手順と、前記生成されたクラスタの個数Ｋ’が前記指定されたクラスタ数Ｋに満たない場合に、分割処理を（Ｋ−Ｋ’）回行って、前記Ｋ’個のクラスタからＫ個のクラスタを生成する手順と、を実行させ、前記１回目の分割処理では、前記Ｋ’個のクラスタが処理対象とされ、前記ｎ回目（２≦ｎ≦（Ｋ−Ｋ’））の分割処理では、（ｎ−１）回目の分割処理後の（Ｋ’＋ｎ−１）個のクラスタが処理対象とされ、前記分割処理は、前記処理対象の複数のクラスタの各々を、分割用キーワードを含む文書の集合である第１のクラスタと、前記分割用キーワードを含まない文書の集合である第２のクラスタとに仮想的に分割する処理と、前記第２のクラスタの各々について、当該第２のクラスタに含まれる各キーワードの、当該第２のクラスタの特徴を表す度合いを示す第２の度合い値を算出する処理と、前記第２の度合い値に基づき、前記処理対象の複数のクラスタのうち１個のクラスタを、前記仮想的に分割した通りに２つのクラスタに分割する処理と、を含み、前記クラスタを仮想的に分割するための分割用キーワードは、当該クラスタに含まれるキーワードのうち、当該クラスタ内の全ての文書に含まれるキーワードを除く、当該クラスタ内の最も多くの文書に含まれるキーワードである、ことを特徴とする。
【００１７】
また、本発明に係るクラスタ生成プログラムは、コンピュータに、文書群がクラスタリングされて得られるＫ’個（Ｋ’は２以上の整数）のクラスタを取得する手順と、分割処理を行って、前記取得されたＫ’個のクラスタから（Ｋ’＋１）個のクラスタを生成する手順と、を実行させ、前記分割処理は、前記Ｋ’個のクラスタの各々を、分割用キーワードを含む文書の集合である第１のクラスタと、前記分割用キーワードを含まない文書の集合である第２のクラスタとに仮想的に分割する処理と、前記第１のクラスタの各々について、当該第１のクラスタに含まれる各キーワードの、当該第１のクラスタの特徴を表す度合いを示す第１の度合い値を算出する処理と、前記第１の度合い値に基づき、前記Ｋ’個のクラスタのうち１個のクラスタを、前記仮想的に分割した通りに２つのクラスタに分割する処理と、を含み、前記クラスタを仮想的に分割するための分割用キーワードは、当該クラスタに含まれるキーワードのうち、当該クラスタ内の全ての文書に含まれるキーワードを除く、当該クラスタ内の最も多くの文書に含まれるキーワードである、ことを特徴とする。
【００１８】
また、本発明に係るクラスタ生成プログラムは、コンピュータに、文書群を所定のクラスタリング処理によりクラスタリングして、予め指定されたクラスタ数Ｋ（Ｋは２以上の整数）以下のＫ’個（Ｋ’は２以上の整数）のクラスタを生成する手順と、前記生成されたクラスタの個数Ｋ’が前記指定されたクラスタ数Ｋに満たない場合に、分割処理を（Ｋ−Ｋ’）回行って、前記Ｋ’個のクラスタからＫ個のクラスタを生成する手順と、を実行させ、前記１回目の分割処理では、前記Ｋ’個のクラスタが処理対象とされ、前記ｎ回目（２≦ｎ≦（Ｋ−Ｋ’））の分割処理では、（ｎ−１）回目の分割処理後の（Ｋ’＋ｎ−１）個のクラスタが処理対象とされ、前記分割処理は、前記処理対象の複数のクラスタの各々を、分割用キーワードを含む文書の集合である第１のクラスタと、前記分割用キーワードを含まない文書の集合である第２のクラスタとに仮想的に分割する処理と、前記第１のクラスタの各々について、当該第１のクラスタに含まれる各キーワードの、当該第１のクラスタの特徴を表す度合いを示す第１の度合い値を算出する処理と、前記第１の度合い値に基づき、前記処理対象の複数のクラスタのうち１個のクラスタを、前記仮想的に分割した通りに２つのクラスタに分割する処理と、を含み、前記クラスタを仮想的に分割するための分割用キーワードは、当該クラスタに含まれるキーワードのうち、当該クラスタ内の全ての文書に含まれるキーワードを除く、当該クラスタ内の最も多くの文書に含まれるキーワードである、ことを特徴とする。
【発明の効果】
【００１９】
請求項１に記載の発明によれば、文書群がクラスタリングされて得られるクラスタ群のクラスタ数を簡単に増やすことが可能となる。
【００２０】
請求項２に記載の発明によれば、文書群を所定のクラスタリング処理によりクラスタリングした際、生成されたクラスタ数が予め指定されたクラスタ数に満たない場合であっても、生成されたクラスタを分割し、予め指定されたクラスタ数のクラスタを得ることが可能となる。
【００２１】
請求項３に記載の発明によれば、第２の度合い値に応じた妥当性の高いクラスタの分割を行うことが可能となる。
【００２２】
請求項４に記載の発明によれば、第１および第２の度合い値に基づくクラスタの分割を行うことが可能となる。
【００２３】
請求項５に記載の発明によれば、第１および第２の度合い値に応じた妥当性の高いクラスタの分割を行うことが可能となる。
【００２４】
請求項６に記載の発明によれば、文書群がクラスタリングされて得られるクラスタ群のクラスタ数を簡単に増やすことが可能となる。
【００２５】
請求項７に記載の発明によれば、文書群を所定のクラスタリング処理によりクラスタリングした際、生成されたクラスタ数が予め指定されたクラスタ数に満たない場合であっても、生成されたクラスタを分割し、予め指定されたクラスタ数のクラスタを得ることが可能となる。
【００２６】
請求項８に記載の発明によれば、第１の度合い値に応じた妥当性の高いクラスタの分割を行うことが可能となる。
【００２７】
請求項９に記載の発明によれば、文書群を少ない計算量でクラスタリングすることが可能となる。
【００２８】
請求項１０に記載の発明によれば、文書群を少ない計算量でクラスタリングすることが可能となる。
【００２９】
請求項１１に記載の発明によれば、文書群がクラスタリングされて得られるクラスタ群のクラスタ数を簡単に増やすことが可能となる。
【００３０】
請求項１２に記載の発明によれば、文書群を所定のクラスタリング処理によりクラスタリングした際、生成されたクラスタ数が予め指定されたクラスタ数に満たない場合であっても、生成されたクラスタを分割し、予め指定されたクラスタ数のクラスタを得ることが可能となる。
【００３１】
請求項１３に記載の発明によれば、文書群がクラスタリングされて得られるクラスタ群のクラスタ数を簡単に増やすことが可能となる。
【００３２】
請求項１４に記載の発明によれば、文書群を所定のクラスタリング処理によりクラスタリングした際、生成されたクラスタ数が予め指定されたクラスタ数に満たない場合であっても、生成されたクラスタを分割し、予め指定されたクラスタ数のクラスタを得ることが可能となる。
【発明を実施するための最良の形態】
【００３３】
以下、本発明の実施の形態を図面に従って説明する。
【００３４】
［第１の実施の形態］
図１は、第１の実施の形態に係るクラスタ生成装置１０の構成の一例を示すブロック図である。図１において、クラスタ生成装置１０は、クラスタ取得部１１とクラスタ生成部１２とを有する。
【００３５】
クラスタ取得部１１は、文書群がクラスタリングされて得られるＫ’個（Ｋ’は２以上の整数）のクラスタを取得する。ここで、上記文書群は、分類対象である複数の文書の集合である。文書としては、例えば、特許文献、論文、またはＷｅｂページなどの文書が挙げられる。また、タグ文書等として撮影者や撮影条件等の文字文書が一体とされる画像ファイルもこの文書の一例として挙げられる。上記クラスタリングは、本実施の形態では、後述するキーワードの有無に基づく分類である。ただし、上記Ｋ’個のクラスタは、階層型クラスタリングなど、他の分類手法により得られたものであってもよい。上記クラスタは、文書群がクラスタリングされて得られる文書の集合である。
【００３６】
クラスタ生成部１２は、分割処理を行って、クラスタ取得部１１により取得されたＫ’個のクラスタから（Ｋ’＋１）個のクラスタを生成する。
【００３７】
以下、上記分割処理の第１〜第３の例を説明する。以下の説明では、上記文書群から抽出されたキーワード、すなわち上記文書群に属する各文書から抽出されたキーワードを、キーワードＫＷｉ（ｉ＝１，２，・・・，Ｍ）と表す。ここで、ｉ≠ｊであれば、ＫＷｉ≠ＫＷｊである。
【００３８】
図２は、分割処理の第１の例を示すフローチャートである。図３は、分割処理の第１の例を示す概念図である。以下、図２，３を参照して、分割処理の第１の例を説明する。
【００３９】
図２において、分割処理は、処理Ｓ１１〜Ｓ１３を含む。図３において、上記Ｋ’個のクラスタは、クラスタＣｋ（ｋ＝１，２，・・・，Ｋ’）と表されている。
【００４０】
処理Ｓ１１では、クラスタ生成部１２は、Ｋ’個のクラスタＣｋの各々を、分割用キーワードを含む文書の集合である第１のクラスタＣ１ｋと、上記分割用キーワードを含まない文書の集合である第２のクラスタＣ２ｋとに仮想的に分割する。
【００４１】
ここで、上記のクラスタＣｋを仮想的に分割するための分割用キーワードは、当該クラスタＣｋに含まれるキーワードのうち、当該クラスタＣｋ内の全ての文書に含まれるキーワードを除く、当該クラスタＣｋ内の最も多くの文書に含まれるキーワードである。例えば、クラスタ生成部１２は、クラスタＣｋに含まれるキーワードの各々について、当該キーワードが当該クラスタＣｋ内の何個の文書に出現するかを計数する。そして、クラスタ生成部１２は、計数された個数が当該クラスタＣｋ内の文書の個数と一致するキーワードを除き、計数された個数が最大であるキーワードを分割用キーワードに決定する。
【００４２】
処理Ｓ１２では、クラスタ生成部１２は、上記第２のクラスタＣ２ｋ（ｋ＝１，２，・・・，Ｋ’）の各々について、当該第２のクラスタＣ２ｋに含まれる各キーワードＫＷｉの、当該第２のクラスタＣ２ｋの特徴を表す度合いを示す第２の度合い値Ｓ２（ｋ，ｉ）を算出する。ここで、第２の度合い値Ｓ２（ｋ，ｉ）は、当該キーワードＫＷｉが当該第２のクラスタＣ２ｋの特徴をどの程度表しているかを示す値であり、クラスタＣ２ｋにおけるキーワードＫＷｉのスコアとも呼ばれる。本実施の形態では、第２の度合い値Ｓ２（ｋ，ｉ）は、下記式（１）により算出される。
【００４３】
【数１】
2008204374.tif 000003
【００４４】
ここで、Ｆ２（ｋ，ｉ）は、第２のクラスタＣ２ｋに属する文書の中でキーワードＫＷｉを含む文書の数を第２のクラスタＣ２ｋに属する文書の総数で除したものである。また、Ｆ１（ｋ，ｉ）は、第１のクラスタＣ１ｋに属する文書の中でキーワードＫＷｉを含む文書の数を第１のクラスタＣ１ｋに属する文書の総数で除したものである。また、Ｆ（ｊ，ｉ）は、クラスタＣｊ（１≦ｊ≦Ｋ’かつｊ≠ｋ）に属する文書の中でキーワードＫＷｉを含む文書の数をクラスタＣｊに属する文書の総数で除したものである。また、Πの項は、数列（１．０−Ｆ（ｊ，ｉ））（ｊ＝１，２，・・・，Ｋ’、ｊ≠ｋ）の積を意味する。
【００４５】
ただし、第２の度合い値Ｓ２（ｋ，ｉ）は、ＴＦ／ＩＤＦ(Term Frequency / Inverse Document Frequency)やエントロピーなどを利用した他の算出方法により算出されてもよい。
【００４６】
以下の説明では、第２のクラスタＣ２ｋにおける第２の度合い値Ｓ２（ｋ，ｉ）の最大値を当該第２のクラスタＣ２ｋの特徴語スコアと称し、当該特徴語スコアを与えるキーワードを当該第２のクラスタＣ２ｋの特徴語と称する。クラスタにおける特徴語は、例えば、当該クラスタには高頻度で出現して、他のクラスタには殆ど出現しないキーワードである。
【００４７】
処理Ｓ１３では、クラスタ生成部１２は、上記処理Ｓ１２で算出された第２の度合い値Ｓ２（ｋ，ｉ）に基づき、Ｋ’個のクラスタＣｋ（ｋ＝１，２，・・・，Ｋ’）のうち１個のクラスタを、上記処理Ｓ１１で仮想的に分割した通りに２つのクラスタに分割する。本実施の形態では、クラスタ生成部１２は、上記処理Ｓ１２で算出された第２の度合い値Ｓ２（ｋ，ｉ）のうち最大のものに対応するクラスタを分割する。具体的には、クラスタ生成部１２は、Ｋ’個の第２のクラスタＣ２ｋの特徴語スコアを比較し、最大の特徴語スコアを持つ第２のクラスタＣ２ｋｍａｘ（１≦ｋｍａｘ≦Ｋ’）を特定し、当該特定された第２のクラスタＣ２ｋｍａｘの元のクラスタＣｋｍａｘを分割する。図３の例では、ｋｍａｘ＝３であり、クラスタＣ３が分割されている。
【００４８】
図４は、分割処理の第２の例を示すフローチャートである。図５は、分割処理の第２の例を示す概念図である。以下、図４，５を参照して、分割処理の第２の例を説明する。
【００４９】
図４において、分割処理は、処理Ｓ２１〜Ｓ２４を含む。図５において、上記Ｋ’個のクラスタは、クラスタＣｋ（ｋ＝１，２，・・・，Ｋ’）と表されている。
【００５０】
処理Ｓ２１では、クラスタ生成部１２は、上記第１の例の処理Ｓ１１と同様に、Ｋ’個のクラスタＣｋの各々を、分割用キーワードを含む文書の集合である第１のクラスタＣ１ｋと、上記分割用キーワードを含まない文書の集合である第２のクラスタＣ２ｋとに仮想的に分割する。
【００５１】
処理Ｓ２２では、クラスタ生成部１２は、上記第１の例の処理Ｓ１２と同様に、上記第２のクラスタＣ２ｋ（ｋ＝１，２，・・・，Ｋ’）の各々について、当該第２のクラスタＣ２ｋに含まれる各キーワードＫＷｉの、当該第２のクラスタＣ２ｋの特徴を表す度合いを示す第２の度合い値Ｓ２（ｋ，ｉ）を算出する。
【００５２】
処理Ｓ２３では、クラスタ生成部１２は、上記第１のクラスタＣ１ｋ（ｋ＝１，２，・・・，Ｋ’）の各々について、当該第１のクラスタＣ１ｋに含まれる各キーワードＫＷｉの、当該第１のクラスタＣ１ｋの特徴を表す度合いを示す第１の度合い値Ｓ１（ｋ，ｉ）を算出する。ここで、第１の度合い値Ｓ１（ｋ，ｉ）は、当該キーワードＫＷｉが当該第１のクラスタＣ１ｋの特徴をどの程度表しているかを示す値であり、クラスタＣ１ｋにおけるキーワードＫＷｉのスコアとも呼ばれる。本実施の形態では、第１の度合い値Ｓ１（ｋ，ｉ）は、下記式（２）により算出される。
【００５３】
【数２】
2008204374.tif 000004
【００５４】
ここで、Ｆ１（ｋ，ｉ）は、第１のクラスタＣ１ｋに属する文書の中でキーワードＫＷｉを含む文書の数を第１のクラスタＣ１ｋに属する文書の総数で除したものである。また、Ｆ２（ｋ，ｉ）は、第２のクラスタＣ２ｋに属する文書の中でキーワードＫＷｉを含む文書の数を第２のクラスタＣ２ｋに属する文書の総数で除したものである。また、Ｆ（ｊ，ｉ）は、クラスタＣｊ（１≦ｊ≦Ｋ’かつｊ≠ｋ）に属する文書の中でキーワードＫＷｉを含む文書の数をクラスタＣｊに属する文書の総数で除したものである。また、Πの項は、数列（１．０−Ｆ（ｊ，ｉ））（ｊ＝１，２，・・・，Ｋ’、ｊ≠ｋ）の積を意味する。
【００５５】
ただし、第１の度合い値Ｓ１（ｋ，ｉ）は、ＴＦ／ＩＤＦやエントロピーなどを利用した他の算出方法により算出されてもよい。
【００５６】
以下の説明では、第１のクラスタＣ１ｋにおける第１の度合い値Ｓ１（ｋ，ｉ）の最大値を当該第１のクラスタＣ１ｋの特徴語スコアと称し、当該特徴語スコアを与えるキーワードを当該第１のクラスタＣ１ｋの特徴語と称する。
【００５７】
処理Ｓ２４では、クラスタ生成部１２は、上記算出された第２の度合い値Ｓ２（ｋ，ｉ）および第１の度合い値Ｓ１（ｋ，ｉ）に基づき、Ｋ’個のクラスタＣｋ（ｋ＝１，２，・・・，Ｋ’）のうち１個のクラスタを、上記処理Ｓ２１で仮想的に分割した通りに２つのクラスタに分割する。本実施の形態では、クラスタ生成部１２は、処理対象の複数のクラスタであるＫ’個のクラスタＣｋの各々について、第１の度合い値の最大値（すなわち第１のクラスタの特徴語スコア）と第２の度合い値の最大値（すなわち第２のクラスタの特徴語スコア）との和Ｓｋを算出し、算出された和Ｓｋのうち最大のものに対応するクラスタを分割する。具体的には、クラスタ生成部１２は、Ｋ’個の和Ｓｋを比較し、最大の和Ｓｋｍａｘ（１≦ｋｍａｘ≦Ｋ’）を持つクラスタＣｋｍａｘを特定し、当該クラスタＣｋｍａｘを分割する。図５の例では、ｋｍａｘ＝３であり、クラスタＣ３が分割されている。
【００５８】
図６は、分割処理の第３の例を示すフローチャートである。図７は、分割処理の第３の例を示す概念図である。以下、図６，７を参照して、分割処理の第３の例を説明する。
【００５９】
図６において、分割処理は、処理Ｓ３１〜Ｓ３３を含む。図７において、上記Ｋ’個のクラスタは、クラスタＣｋ（ｋ＝１，２，・・・，Ｋ’）と表されている。
【００６０】
処理Ｓ３１では、クラスタ生成部１２は、上記第１の例の処理Ｓ１１と同様に、Ｋ’個のクラスタＣｋの各々を、分割用キーワードを含む文書の集合である第１のクラスタＣ１ｋと、上記分割用キーワードを含まない文書の集合である第２のクラスタＣ２ｋとに仮想的に分割する。
【００６１】
処理Ｓ３２では、クラスタ生成部１２は、上記第２の例の処理Ｓ２３と同様に、上記第１のクラスタＣ１ｋ（ｋ＝１，２，・・・，Ｋ’）の各々について、当該第１のクラスタＣ１ｋに含まれる各キーワードＫＷｉの、当該第１のクラスタＣ１ｋの特徴を表す度合いを示す第１の度合い値Ｓ１（ｋ，ｉ）を算出する。
【００６２】
処理Ｓ３３では、クラスタ生成部１２は、上記処理Ｓ３２で算出された第１の度合い値Ｓ１（ｋ，ｉ）に基づき、Ｋ’個のクラスタＣｋ（ｋ＝１，２，・・・，Ｋ’）のうち１個のクラスタを、上記処理Ｓ３１で仮想的に分割した通りに２つのクラスタに分割する。本実施の形態では、クラスタ生成部１２は、上記処理Ｓ３２で算出された第１の度合い値Ｓ１（ｋ，ｉ）のうち最大のものに対応するクラスタを分割する。具体的には、クラスタ生成部１２は、Ｋ’個の第１のクラスタＣ１ｋの特徴語スコアを比較し、最大の特徴語スコアを持つ第１のクラスタＣ１ｋｍａｘ（１≦ｋｍａｘ≦Ｋ’）を特定し、当該特定された第１のクラスタＣ１ｋｍａｘの元のクラスタＣｋｍａｘを分割する。図７の例では、ｋｍａｘ＝３であり、クラスタＣ３が分割されている。
【００６３】
なお、本実施の形態において、クラスタ生成装置１０は、関連語辞書（シソーラス）を用いて、互いに同義である２つのキーワード、互いに類義である２つのキーワード、または互いに関連する２つのキーワードを、互いに同一のキーワードとみなして上記の処理を行ってもよい。
【００６４】
［第２の実施の形態］
図８は、第２の実施の形態に係るクラスタ生成装置２０の構成の一例を示すブロック図である。図８において、クラスタ生成装置２０は、文書群取得部２１、キーワード取得部２２、第１のクラスタ生成部２３、第２のクラスタ生成部２４、スコア算出部２５、および出力部２６を有する。
【００６５】
文書群取得部２１は、処理対象となる元の文書群を取得する。元の文書群に属する文書としては、例えば、特許文献、論文、またはＷｅｂページなどの文書が挙げられる。文書群取得部２１は、キーワード検索などによりＷｅｂ上から文書を収集してもよいし、予めデータベースに蓄えられている文書を取得してもよい。以下、元の文書群に属する文書をＰｉ（ｉ＝１，２，・・・，Ｎ）とする。Ｎは元の文書群に属する文書の数である。
【００６６】
キーワード取得部２２は、上記元の文書群に属する各文書から抽出されるキーワードを取得する。キーワード取得部２２は、上記元の文書群の各文書からキーワードを抽出してもよいし、別の装置やモジュールによって抽出されたキーワードを受け取ってもよい。ここで、キーワードは、例えば文書の内容を反映する語句であり、例えば形態素解析などで抽出される文書中に出現する単語である。なお、本実施の形態においても、クラスタ生成装置２０は、関連語辞書を用いて、互いに同義である２つのキーワード、互いに類義である２つのキーワード、または互いに関連する２つのキーワードを、互いに同一のキーワードとみなして処理を行ってもよい。
【００６７】
第１のクラスタ生成部２３は、上記取得されたキーワードに基づき、上記元の文書群を所定のクラスタリング処理によりクラスタリングして、予め指定されたクラスタ数Ｋ（Ｋは２以上の整数）以下のＫ’個（Ｋ’は２以上の整数）のクラスタを生成する。本実施の形態では、クラスタ生成装置２０は、ユーザから上記クラスタ数Ｋの指定を受け付ける。ただし、上記クラスタ数Ｋは、クラスタ生成装置２０により決定されてもよいし、固定的に決められた値であってもよい。なお、上記所定のクラスタリング処理については、後に詳しく説明する。
【００６８】
第２のクラスタ生成部２４は、上記生成されたクラスタの個数Ｋ’が上記予め指定されたクラスタ数Ｋに満たない場合に、分割処理を（Ｋ−Ｋ’）回行って、上記Ｋ’個のクラスタからＫ個のクラスタを生成する。当該第２のクラスタ生成部２４による分割処理については、後に詳しく説明する。
【００６９】
スコア算出部２５は、第１のクラスタ生成部２３または第２のクラスタ生成部２４により生成されたＫ個のクラスタの各々について、当該クラスタにおける各キーワードのスコアを算出し、算出結果に基づいて当該クラスタにおける特徴語および特徴語スコアを求める。このスコア算出部２５の処理については、後に詳しく説明する。
【００７０】
出力部２６は、上記クラスタ生成処理やスコア算出部２５による処理の結果を出力する。例えば、出力部２６は、各クラスタに属する文書、各クラスタに属する文書の数、各クラスタの特徴語、各クラスタの特徴語スコアを出力する。出力部２６は、上記結果を、表示装置に表示させてもよいし、印刷装置に印刷させてもよいし、記憶装置に記憶させてもよい。
【００７１】
なお、上記クラスタ生成装置２０の各部の処理結果は、例えば、当該装置２０の内部または外部の不図示の記憶部に記憶され、当該記憶部の内容は、上記各部の処理に用いられる。
【００７２】
図９は、第２の実施の形態に係るクラスタ生成装置２０の動作手順の一例を示すフローチャートである。以下、図９を参照して、クラスタ生成装置２０の動作を説明する。
【００７３】
クラスタ生成装置２０は、処理対象となる元の文書群を取得する（Ｓ４１）。
【００７４】
ついで、クラスタ生成装置２０は、上記取得された元の文書群に属する各文書から抽出されるキーワードを取得する（Ｓ４２）。
【００７５】
ついで、クラスタ生成装置２０は、上記取得されたキーワードに基づき、所定のクラスタリング処理により上記元の文書群をクラスタリングしてＫ’個のクラスタを生成する（Ｓ４３）。
【００７６】
ついで、クラスタ生成装置２０は、上記生成されたクラスタ数Ｋ’が予め指定されたクラスタ数Ｋと一致するか否かを判断する（Ｓ４４）。
【００７７】
一致すると判断された場合（Ｓ４４：ＹＥＳ）、処理はステップＳ４６に進む。
【００７８】
一方、一致しないと判断された場合（Ｓ４４：ＮＯ）、すなわち生成されたクラスタの個数が予め指定されたクラスタ数Ｋに満たない場合、クラスタ生成装置２０は、クラスタ数を１つ増加させる分割処理を行い（Ｓ４５）、処理をステップＳ４４に戻す。
【００７９】
上記ステップＳ４５において、１回目の分割処理では、ステップＳ４３で生成されたＫ’個のクラスタが処理対象とされ、ｎ回目（２≦ｎ≦（Ｋ−Ｋ’））の分割処理では、（ｎ−１）回目の分割処理後の（Ｋ’＋ｎ−１）個のクラスタが処理対象とされる。
【００８０】
したがって、上記ステップＳ４３で生成されたクラスタの個数Ｋ’が予め指定されたクラスタ数Ｋに満たなかった場合には、ステップＳ４５の分割処理が（Ｋ−Ｋ’）回実行され、Ｋ個のクラスタが生成された後に、処理がステップＳ４６に進む。
【００８１】
ステップＳ４６では、クラスタ生成装置２０は、上記生成されたＫ個のクラスタの各々について、当該クラスタにおける各キーワードのスコアを算出し、算出結果に基づいて当該クラスタにおける特徴語および特徴語スコアを求める。
【００８２】
具体的には、クラスタ生成装置２０は、下記式（３）により、Ｋ個のクラスタＣｉ（ｉ＝１，２，・・・，Ｋ）の各々について、当該クラスタＣｉにおける各キーワードＫＷｊ（ｊ＝１，２，・・・，Ｍ）のスコアＳ（ｉ，ｊ）を算出する。
【００８３】
【数３】
2008204374.tif 000005
【００８４】
ここで、Ｆ（ｉ，ｊ）は、クラスタＣｉに属する文書のうちキーワードＫＷｊを含む文書の数をクラスタＣｉに属する文書の総数で除したものである。すなわち、Ｆ（ｉ，ｊ）は、クラスタＣｉの中に含まれる文書で、キーワードＫＷｊを含むものの割合である。また、Πの項は、数列（１．０−Ｆ（ｋ，ｊ））（ｋ＝１，２，・・・，Ｋ、ｋ≠ｉ）の積を意味する。
【００８５】
ただし、スコアＳ（ｉ，ｊ）は、ＴＦ／ＩＤＦやエントロピーなどを利用した他の算出方法により算出されてもよい。
【００８６】
そして、クラスタ生成装置２０は、Ｋ個のクラスタＣｉ（ｉ＝１，２，・・・，Ｋ）の各々について、当該クラスタＣｉにおけるスコアＳ（ｉ，ｊ）の最大値Ｓ（ｉ，ｊｍａｘ）を特徴語スコアとし、これを与えるキーワードＫＷｊｍａｘを特徴語とする。
【００８７】
ついで、クラスタ生成装置２０は、各クラスタの特徴語や特徴語スコアなど、上記処理の結果を出力する（Ｓ４７）。
【００８８】
以下、上記キーワード取得部２２の処理、上記第１のクラスタ生成部２３によるクラスタリング処理、および上記第２のクラスタ生成部２４による分割処理について、具体的に説明する。なお、以下の説明において、各変数の値は不図示の記憶部に記憶されるものとする。
【００８９】
（キーワード取得部２２の処理）
キーワード取得部２２は、元の文書群に属する各文書から抽出されるキーワードを取得し、取得されたキーワードを変数ＫＷｉ（ｉ＝１，２，・・・，Ｍ）に代入する。ここで、Ｍはキーワードの総数であり、キーワードＫＷｉに重複はない。すなわち、ｉ≠ｊであれば、ＫＷｉ≠ＫＷｊである。ここで、キーワード取得部２２は、上記キーワード群ＫＷｉを作成する際に、事前に関連語辞書（シソーラス）などでキーワードをまとめる処理を実施してもよい。
【００９０】
ついで、キーワード取得部２２は、各キーワードＫＷｉの出現回数をカウントする。本実施の形態では、キーワードの出現回数は、元の文書群に属する文書のうち当該キーワードを含む文書の数である。したがって、あるキーワードＫＷｉが元の文書群のうちｎ個の文書に出現する場合、当該キーワードＫＷｉの出現回数はｎとされる。
【００９１】
ついで、キーワード取得部２２は、キーワード群を出現回数が大きい順に並べ替え（ソート）し、ソート後のキーワード群を新たに変数ＫＷｉ（ｉ＝１，２，・・・，Ｍ）に代入する。ソート後、キーワード取得部２２は、各キーワードＫＷｉの出現回数を、変数Ｆｉ（ｉ＝１，２，・・・，Ｍ）に代入する。このとき、ｉ＜ｊであれば、Ｎ≧Ｆｉ≧Ｆｊ≧１となる。
【００９２】
（第１のクラスタ生成部２３によるクラスタリング処理）
図１０は、第１のクラスタ生成部２３によるクラスタリング処理の第１の例を示すフローチャートである。図１０において、クラスタリング処理は、処理Ｓ５１と処理Ｓ５２とを含む。
【００９３】
処理Ｓ５１では、第１のクラスタ生成部２３は、単位クラスタリング処理を（Ｋ’−１）回行って、元の文書群から（Ｋ’−１）個のクラスタＣ１〜ＣＫ’−１を生成する。
【００９４】
ここで、上記単位クラスタリング処理は、元の文書群のうち未だ何れのクラスタにも属していない文書を未分類文書と呼ぶとき、元の文書群に属する各文書から取得されるキーワードのうち最も多くの未分類文書に含まれるキーワードを含む未分類文書の集合を新たなクラスタとする処理である。
【００９５】
例えば、１回目の単位クラスタリング処理では、第１のクラスタ生成部２３は、元の文書群に属する全文書を未分類文書とし、キーワードＫＷｉのうち最も多くの未分類文書に出現するキーワードを特定し、当該キーワードを含む未分類文書の集合を新たなクラスタＣ１とする。ついで、２回目の単位クラスタリング処理では、第１のクラスタ生成部２３は、元の文書群に属する文書のうちクラスタＣ１に属するもの以外を未分類文書とし、キーワードＫＷｉのうち最も多くの未分類文書に出現するキーワードを特定し、当該キーワードを含む未分類文書の集合を新たなクラスタＣ２とする。以後同様に、ｋ回目の単位クラスタリング処理では、第１のクラスタ生成部２３は、元の文書群に属する文書のうちクラスタＣ１〜Ｃｋ−１の何れかに属するもの以外を未分類文書とし、キーワードＫＷｉのうち最も多くの未分類文書に出現するキーワードを特定し、当該キーワードを含む未分類文書の集合を新たなクラスタＣｋとする。
【００９６】
第１のクラスタ生成部２３は、所定の終了条件が満たされるまで上記単位クラスタリング処理を繰り返し行い、結果的に（Ｋ’−１）個のクラスタＣ１〜ＣＫ’−１を生成する。ここで、上記所定の終了条件には、
（ａ）（Ｋ−１）個のクラスタが生成されたこと
（ｂ）未分類文書がなくなったこと
があり、第１のクラスタ生成部２３は、上記条件（ａ）または（ｂ）のいずれかが満たされると単位クラスタリング処理の繰り返しを停止させる。
【００９７】
第１のクラスタ生成部２３は、上記終了条件（ａ）、（ｂ）、または所定の停止条件のいずれかが満たされたときに単位クラスタリング処理の繰り返しを停止させてもよい。所定の停止条件としては、例えば、最も多くの未分類文書に含まれるキーワードを含む未分類文書の数が所定の閾値より少ないことや、未分類文書の総数が所定の閾値より少なくなったことなどが挙げられる。所定の停止条件は、クラスタ生成処理の際にユーザに指定されてもよいし、予め固定的に設定されていてもよい。
【００９８】
処理Ｓ５２では、第１のクラスタ生成部２３は、元の文書群のうち処理Ｓ５１で生成された（Ｋ’−１）個のクラスタＣ１〜ＣＫ’−１の何れにも属していない文書の集合を新たな１個のクラスタＣＫ’とする。
【００９９】
図１１は、クラスタリング処理の第１の例の具体的な処理例を示すフローチャートである。
【０１００】
ステップＳ６１では、変数の初期化処理を行う。この初期化処理では、ｋ＝１，Ｐｊ＿ｉｄ＝０（ｊ＝１，２，・・・，Ｍ）とされる。ここで、変数Ｐｊ＿ｉｄの値は、文書Ｐｊが属するクラスタのクラスタ番号を示し、Ｐｊ＿ｉｄ＝０は文書Ｐｊが未分類文書であることを示す。
【０１０１】
ステップＳ６２では、Ｍ個のキーワードＫＷｉ（ｉ＝１，２，・・・，Ｍ）のうち出現回数Ｆｉが最も大きいキーワードを選択し、当該キーワードをＫＷｉｍａｘとする。
【０１０２】
ステップＳ６３では、変数ｊに１を代入する。
【０１０３】
ステップＳ６４では、文書ＰｊがキーワードＫＷｉｍａｘを含み、かつＰｊ＿ｉｄ＝０であれば、変数Ｐｊ＿ｉｄに変数ｋの値を代入する。すなわち、文書ＰｊがキーワードＫＷｉｍａｘを含み、かつ文書Ｐｊが未分類文書であれば、当該文書Ｐｊをｋ番目のクラスタＣｋに属させる。
【０１０４】
ステップＳ６５では、変数ｊの値に１を加える。
【０１０５】
ステップＳ６６では、変数ｊが文書数Ｎより大きいか否かを判断し、大きくなければステップＳ６４に戻り、大きければステップＳ６７に進む。すなわち、文書群に属する全ての文書Ｐｊ（ｊ＝１，２，・・・，Ｎ）について、ステップＳ６４の処理が繰り返し行われる。これにより、キーワードＫＷｉｍａｘを含む全ての未分類文書がクラスタＣｋに分類される。
【０１０６】
ステップＳ６７では、変数ｉに１を代入し、変数ｊに１を代入する。
【０１０７】
ステップＳ６８では、文書ＰｊがクラスタＣｋに属するか否かを判断し、すなわちＰｊ＿ｉｄ＝ｋか否かを判断し、属する場合にはステップＳ６９に進み、属さない場合にはステップＳ７３に進む。
【０１０８】
ステップＳ６９では、キーワードＫＷｉが文書Ｐｊに含まれるか否かを判断し、含まれる場合にはステップＳ７０に進み、含まれない場合にはステップＳ７１に進む。
【０１０９】
ステップＳ７０では、変数Ｆｉの値から１を引く。すなわち、文書ＰｊがクラスタＣｋに属し、当該文書ＰｊにキーワードＫＷｉが存在すれば、出現回数Ｆｉを１引く。
【０１１０】
ステップＳ７１では、変数ｉの値に１を加える。
【０１１１】
ステップＳ７２では、変数ｉがキーワード数Ｍより大きいか否かを判断し、大きくなければステップＳ６９に戻り、大きければステップＳ７３に進む。すなわち、全てのキーワードＫＷｉ（ｉ＝１，２，・・・，Ｍ）について、ステップＳ６９，Ｓ７０の処理が繰り返し行われる。
【０１１２】
ステップＳ７３では、変数ｉに１を代入し、変数ｊの値に１を加える。
【０１１３】
ステップＳ７４では、変数ｊが文書数Ｎより大きいか否かを判断し、大きくなければステップＳ６８に戻り、大きければステップＳ７５に進む。すなわち、全ての文書Ｐｊ（ｊ＝１，２，・・・，Ｎ）について、ステップＳ６８〜Ｓ７３の処理が繰り返し行われる。これにより、元の文書群のうち未だ何れのクラスタにも属していない未分類文書の集合における、各キーワードＫＷｉ（ｉ＝１，２，・・・，Ｍ）の出現回数Ｆｉが生成されることになる。なお、この処理の結果、Ｆｉは０となり得る。
【０１１４】
ステップＳ７５では、変数ｋの値に１を加える。
【０１１５】
ステップＳ７６では、変数ｋが（Ｋ−１）より大きいか否かを判断し、大きくなければステップＳ７７に進み、大きければステップＳ７８に進む。すなわち、生成されたクラスタ数が（Ｋ−１）個に達していなければステップＳ７７に進み、達していればステップＳ７８に進む。
【０１１６】
ステップＳ７７では、Ｐｊ＿ｉｄ（ｊ＝１，２，・・・，Ｎ）の値に基づき、未分類文書が存在するか否かを判断し、存在すればステップＳ６２に戻り、存在しなければ処理を終了させる。
【０１１７】
したがって、ステップＳ６２〜Ｓ７５の処理は、（Ｋ−１）個のクラスタが作成されるまで、または未分類文書がなくなるまで、繰り返し行われる。
【０１１８】
ステップＳ７８では、ｊ＝１，２，・・・，Ｎの各々について、Ｐｊ＿ｉｄ＝０であれば、変数Ｐｊ＿ｉｄにＫを代入する。すなわち、全ての未分類文書の集合をＫ番目のクラスタＣＫとする。
【０１１９】
なお、先述したとおり、所定の停止条件が満たされたとき、ステップＳ６２〜Ｓ７５の処理の繰り返しを停止させてもよい。この場合、停止時点で１〜ｋ番目のクラスタＣ１〜Ｃｋが作成されていれば、未分類文書の集合は（ｋ＋１）番目のクラスタＣｋ＋１とされる。
【０１２０】
図１２は、第１のクラスタ生成部２３によるクラスタリング処理の第２の例を示すフローチャートである。図１２において、クラスタリング処理は、処理Ｓ８１と処理Ｓ８２とを含む。
【０１２１】
処理Ｓ８１では、第１のクラスタ生成部２３は、単位クラスタリング処理をＫ’回行って、元の文書群からＫ’個のクラスタＣ１〜ＣＫ’を生成する。
【０１２２】
ここで、上記単位クラスタリング処理は、上記第１の例と同様に、元の文書群のうち未だ何れのクラスタにも属していない文書を未分類文書と呼ぶとき、元の文書群に属する各文書から取得されるキーワードのうち最も多くの未分類文書に含まれるキーワードを含む未分類文書の集合を新たなクラスタとする処理である。
【０１２３】
第１のクラスタ生成部２３は、所定の終了条件が満たされるまで上記単位クラスタリング処理を繰り返し行い、結果的にＫ’個のクラスタＣ１〜ＣＫ’を生成する。ここで、上記所定の終了条件には、
（ａ）Ｋ個のクラスタが生成されたこと
（ｂ）未分類文書がなくなったこと
があり、第１のクラスタ生成部２３は、上記条件（ａ）または（ｂ）のいずれかが満たされると単位クラスタリング処理の繰り返しを停止させる。
【０１２４】
第１のクラスタ生成部２３は、上記終了条件（ａ）、（ｂ）、または所定の停止条件のいずれかが満たされたときに単位クラスタリング処理の繰り返しを停止させてもよい。所定の停止条件としては、例えば、最も多くの未分類文書に含まれるキーワードを含む未分類文書の数が所定の閾値より少ないことや、未分類文書の総数が所定の閾値より少なくなったことなどが挙げられる。所定の停止条件は、クラスタ生成処理の際にユーザに指定されてもよいし、予め固定的に設定されていてもよい。
【０１２５】
処理Ｓ８２では、第１のクラスタ生成部２３は、元の文書群のうち処理Ｓ８１で生成されたＫ’個のクラスタＣ１〜ＣＫ’の何れにも属していない各文書を上記Ｋ’個のクラスタＣ１〜ＣＫ’に分類する。
【０１２６】
本実施の形態では、第１のクラスタ生成部２３は、何れのクラスタにも属していない文書Ｐｊと、生成されたクラスタＣｋ（ｋ＝１，２，・・・，Ｋ’）との距離に基づき、文書Ｐｊを、当該文書Ｐｊと最も距離が近いクラスタＣｋに分類する。ここで、文書ＰｊとクラスタＣｋとの距離は、例えば、クラスタＣｋの特徴ベクトルＸｋと文書Ｐｊの特徴ベクトルｘｊとの距離である。特徴ベクトルＸｋは、例えばクラスタＣｋの重心ベクトルである。文書Ｐｊの特徴ベクトルｘｊは、例えば、当該文書Ｐｊにおける各キーワードＫＷｉ（ｉ＝１，２，・・・，Ｍ）の有無を各成分とするＭ次元のベクトルである。例えば、文書Ｐｊの特徴ベクトルｘｊの第ｐ成分は、当該文書ＰｊがキーワードＫＷｐを含む場合には「１」、含まない場合には「０」となる。本実施の形態では、文書内でのキーワードの影響力を均一にする観点より、各特徴ベクトルｘｊは、長さが１となるように規格化される。
【０１２７】
ただし、第１のクラスタ生成部２３は、上記以外の方法で未分類文書を分類してもよい。例えば、第１のクラスタ生成部２３は、分類対象の文書Ｐｊと、既にクラスタに属している各文書との距離に基づき、既にクラスタに属している文書のうち、分類対象の文書Ｐｊとの距離が小さい上位Ｙ個（Ｙは２以上の整数）の文書を特定し、特定されたＹ個の文書が最も多く属するクラスタに、分類対象の文書Ｐｊを分類してもよい。ここで、２つの文書の距離、例えば２つの文書の特徴ベクトルの距離は、予め計算されて記憶部に記憶されていてもよいし、分類の際に計算されてもよい。
【０１２８】
図１３は、クラスタリング処理の第２の例の具体的な処理例を示すフローチャートである。
【０１２９】
図１３において、ステップＳ９１〜Ｓ１０５は、図１１のステップＳ６１〜Ｓ７５と同様である。
【０１３０】
ステップＳ１０６では、変数ｋがＫより大きいか否かを判断し、大きくなければステップＳ１０７に進み、大きければステップＳ１０８に進む。すなわち、生成されたクラスタ数がＫ個に達していなければステップＳ１０７に進み、達していればステップＳ１０８に進む。
【０１３１】
ステップＳ１０７では、Ｐｊ＿ｉｄ（ｊ＝１，２，・・・，Ｎ）の値に基づき、未分類文書が存在するか否かを判断し、存在すればステップＳ９２に戻り、存在しなければ処理を終了させる。
【０１３２】
したがって、ステップＳ９２〜Ｓ１０５の処理は、Ｋ個のクラスタが作成されるまで、または未分類文書がなくなるまで、繰り返し行われる。
【０１３３】
ステップＳ１０８では、各クラスタＣｉ（ｉ＝１，２，・・・，Ｋ）の特徴ベクトルＸｉを算出する。
【０１３４】
ステップＳ１０９では、変数ｊに１を代入する。
【０１３５】
ステップＳ１１０では、Ｐｊ＿ｉｄ＝０か否かを判断し、Ｐｊ＿ｉｄ＝０であればステップＳ１１１に進み、そうでなければステップＳ１１３に進む。
【０１３６】
ステップＳ１１１では、文書Ｐｊの特徴ベクトルｘｊと各特徴ベクトルＸｉとの距離を計算し、距離が最小となる特徴ベクトルＸｉｍｉｎ（１≦ｉｍｉｎ≦Ｋ）を特定する。
【０１３７】
ステップＳ１１２では、変数Ｐｊ＿ｉｄにｉｍｉｎを代入する。すなわち、文書Ｐｊを、当該文書Ｐｊとの距離が最小であるクラスタＣｉｍｉｎに分類する。
【０１３８】
ステップＳ１１３では、変数ｊの値に１を加える。
【０１３９】
ステップＳ１１４では、変数ｊが文書数Ｎより大きいか否かを判断し、大きくなければステップＳ１１０に戻り、大きければ処理を終了させる。すなわち、文書群に属する全ての文書Ｐｊ（ｊ＝１，２，・・・，Ｎ）について、ステップＳ１１０〜Ｓ１１３の処理が繰り返し行われる。これにより、全ての未分類文書がクラスタＣ１〜ＣＫの何れかに分類される。
【０１４０】
なお、先述したとおり、所定の停止条件が満たされたとき、ステップＳ９２〜Ｓ１０５の処理の繰り返しを停止させてもよい。この場合、停止時点で１〜ｋ番目のクラスタＣ１〜Ｃｋが作成されていれば、停止時点での各未分類文書は、クラスタＣ１〜Ｃｋのうち当該未分類文書と最も距離が近いクラスタに分類される。
【０１４１】
（第２のクラスタ生成部２４による分割処理）
例えば、キーワードの総数が少ない場合や、ユーザにより指定されたクラスタ数Ｋが大きい場合、小さいクラスタの生成を抑制する観点より単位クラスタリング処理が停止された場合などに、第１のクラスタ生成部２３により生成されるクラスタの個数Ｋ’が予め指定されたクラスタ数Ｋに満たない場合が生じ得る。このような場合には、第２のクラスタ生成部２４による分割処理が行われる。
【０１４２】
第２のクラスタ生成部２４による分割処理は、（Ｋ−Ｋ’）回繰り返し行われる。１回目の分割処理では、Ｋ’個のクラスタが処理対象とされ、ｎ回目（２≦ｎ≦（Ｋ−Ｋ’））の分割処理では、（ｎ−１）回目の分割処理後の（Ｋ’＋ｎ−１）個のクラスタが処理対象とされる。以下の分割処理の説明では、処理対象の複数のクラスタを、Ｃｋ（ｋ＝１，２，・・・，ｋ’）と表す。ここで、Ｋ’≦ｋ’≦（Ｋ−１）である。
【０１４３】
図１４は、第２のクラスタ生成部２４による分割処理の第１の例を示すフローチャートである。図１４において、分割処理は、処理Ｓ１２１〜Ｓ１２３を含む。
【０１４４】
処理Ｓ１２１では、第２のクラスタ生成部２４は、処理対象の複数のクラスタＣｋの各々を、分割用キーワードを含む文書の集合である第１のクラスタＣ１ｋと、上記分割用キーワードを含まない文書の集合である第２のクラスタＣ２ｋとに仮想的に分割する。当該処理Ｓ１２１は、図２の処理Ｓ１１と同様の処理である。ただし、当該処理Ｓ１２１は、クラスタＣｋ（ｋ＝１，２，・・・，ｋ’）を処理対象とする点で、クラスタＣｋ（ｋ＝１，２，・・・，Ｋ’）を処理対象とする処理Ｓ１１と異なる。
【０１４５】
処理Ｓ１２２では、第２のクラスタ生成部２４は、上記第２のクラスタＣ２ｋ（ｋ＝１，２，・・・，ｋ’）の各々について、当該第２のクラスタＣ２ｋに含まれる各キーワードＫＷｉの、当該第２のクラスタＣ２ｋの特徴を表す度合いを示す第２の度合い値Ｓ２（ｋ，ｉ）を算出する。当該処理Ｓ１２２は、図２の処理Ｓ１２と同様の処理である。ただし、当該処理Ｓ１２２は、第２の度合い値Ｓ２（ｋ，ｉ）（ｋ＝１，２，・・・，ｋ’）を算出する点で、第２の度合い値Ｓ２（ｋ，ｉ）（ｋ＝１，２，・・・，Ｋ’）を算出する処理Ｓ１２と異なる。
【０１４６】
処理Ｓ１２３では、第２のクラスタ生成部２４は、上記処理Ｓ１２２で算出された第２の度合い値Ｓ２（ｋ，ｉ）に基づき、ｋ’個のクラスタＣｋ（ｋ＝１，２，・・・，ｋ’）のうち１個のクラスタを、上記処理Ｓ１２１で仮想的に分割した通りに２つのクラスタに分割する。本実施の形態では、第２のクラスタ生成部２４は、上記処理Ｓ１２２で算出された第２の度合い値Ｓ２（ｋ，ｉ）のうち最大のものに対応するクラスタを分割する。当該処理Ｓ１２３は、図２の処理Ｓ１３と同様の処理である。ただし、当該処理Ｓ１２３は、クラスタＣｋ（ｋ＝１，２，・・・，ｋ’）を処理対象とする点で、クラスタＣｋ（ｋ＝１，２，・・・，Ｋ’）を処理対象とする処理Ｓ１３と異なる。
【０１４７】
上記分割処理により、クラスタ数が１つ増加し、（ｋ’＋１）個のクラスタＣｋ（ｋ＝１，２，・・・，ｋ’，ｋ’＋１）が生成される。
【０１４８】
図１５は、第２のクラスタ生成部２４による分割処理の第２の例を示すフローチャートである。図１５において、分割処理は、処理Ｓ１３１〜Ｓ１３４を含む。
【０１４９】
処理Ｓ１３１では、第２のクラスタ生成部２４は、上記第１の例の処理Ｓ１２１と同様に、ｋ’個のクラスタＣｋの各々を、分割用キーワードを含む文書の集合である第１のクラスタＣ１ｋと、上記分割用キーワードを含まない文書の集合である第２のクラスタＣ２ｋとに仮想的に分割する。
【０１５０】
処理Ｓ１３２では、第２のクラスタ生成部２４は、上記第１の例の処理Ｓ１２２と同様に、上記第２のクラスタＣ２ｋ（ｋ＝１，２，・・・，ｋ’）の各々について、当該第２のクラスタＣ２ｋに含まれる各キーワードＫＷｉの、当該第２のクラスタＣ２ｋの特徴を表す度合いを示す第２の度合い値Ｓ２（ｋ，ｉ）を算出する。
【０１５１】
処理Ｓ１３３では、第２のクラスタ生成部２４は、上記第１のクラスタＣ１ｋ（ｋ＝１，２，・・・，ｋ’）の各々について、当該第１のクラスタＣ１ｋに含まれる各キーワードＫＷｉの、当該第１のクラスタＣ１ｋの特徴を表す度合いを示す第１の度合い値Ｓ１（ｋ，ｉ）を算出する。当該処理Ｓ１３３は、図４の処理Ｓ２３と同様の処理である。ただし、当該処理Ｓ１３３は、第１の度合い値Ｓ１（ｋ，ｉ）（ｋ＝１，２，・・・，ｋ’）を算出する点で、第１の度合い値Ｓ１（ｋ，ｉ）（ｋ＝１，２，・・・，Ｋ’）を算出する処理Ｓ２３と異なる。
【０１５２】
処理Ｓ１３４では、第２のクラスタ生成部２４は、上記算出された第２の度合い値Ｓ２（ｋ，ｉ）および第１の度合い値Ｓ１（ｋ，ｉ）に基づき、ｋ’個のクラスタＣｋ（ｋ＝１，２，・・・，ｋ’）のうち１個のクラスタを、上記処理Ｓ１３１で仮想的に分割した通りに２つのクラスタに分割する。本実施の形態では、第２のクラスタ生成部２４は、処理対象の複数のクラスタであるｋ’個のクラスタＣｋの各々について、第１の度合い値の最大値（すなわち第１のクラスタの特徴語スコア）と第２の度合い値の最大値（すなわち第２のクラスタの特徴語スコア）との和Ｓｋを算出し、算出された和Ｓｋのうち最大のものに対応するクラスタを分割する。具体的には、第２のクラスタ生成部２４は、ｋ’個の和Ｓｋを比較し、最大の和Ｓｋｍａｘ（１≦ｋｍａｘ≦ｋ’）を持つクラスタＣｋｍａｘを特定し、当該クラスタＣｋｍａｘを分割する。当該処理Ｓ１３４は、図４の処理Ｓ２４と同様の処理である。ただし、当該処理Ｓ１３４は、クラスタＣｋ（ｋ＝１，２，・・・，ｋ’）を処理対象とする点で、クラスタＣｋ（ｋ＝１，２，・・・，Ｋ’）を処理対象とする処理Ｓ２４と異なる。
【０１５３】
上記分割処理により、クラスタ数が１つ増加し、（ｋ’＋１）個のクラスタＣｋ（ｋ＝１，２，・・・，ｋ’，ｋ’＋１）が生成される。
【０１５４】
図１６は、第２のクラスタ生成部２４による分割処理の第３の例を示すフローチャートである。図１６において、分割処理は、処理Ｓ１４１〜Ｓ１４３を含む。
【０１５５】
処理Ｓ１４１では、第２のクラスタ生成部２４は、上記第１の例の処理Ｓ１２１と同様に、ｋ’個のクラスタＣｋの各々を、分割用キーワードを含む文書の集合である第１のクラスタＣ１ｋと、上記分割用キーワードを含まない文書の集合である第２のクラスタＣ２ｋとに仮想的に分割する。
【０１５６】
処理Ｓ１４２では、第２のクラスタ生成部２４は、上記第２の例の処理Ｓ１３３と同様に、上記第１のクラスタＣ１ｋ（ｋ＝１，２，・・・，ｋ’）の各々について、当該第１のクラスタＣ１ｋに含まれる各キーワードＫＷｉの、当該第１のクラスタＣ１ｋの特徴を表す度合いを示す第１の度合い値Ｓ１（ｋ，ｉ）を算出する。
【０１５７】
処理Ｓ１４３では、第２のクラスタ生成部２４は、上記処理Ｓ１４２で算出された第１の度合い値Ｓ１（ｋ，ｉ）に基づき、ｋ’個のクラスタＣｋ（ｋ＝１，２，・・・，ｋ’）のうち１個のクラスタを、上記処理Ｓ１４１で仮想的に分割した通りに２つのクラスタに分割する。本実施の形態では、第２のクラスタ生成部２４は、上記処理Ｓ１４２で算出された第１の度合い値Ｓ１（ｋ，ｉ）のうち最大のものに対応するクラスタを分割する。具体的には、第２のクラスタ生成部２４は、ｋ’個の第１のクラスタＣ１ｋの特徴語スコアを比較し、最大の特徴語スコアを持つ第１のクラスタＣ１ｋｍａｘ（１≦ｋｍａｘ≦ｋ’）を特定し、当該特定された第１のクラスタＣ１ｋｍａｘの元のクラスタＣｋｍａｘを分割する。当該処理Ｓ１４３は、図６の処理Ｓ３３と同様の処理である。ただし、当該処理Ｓ１４３は、クラスタＣｋ（ｋ＝１，２，・・・，ｋ’）を処理対象とする点で、クラスタＣｋ（ｋ＝１，２，・・・，Ｋ’）を処理対象とする処理Ｓ３３と異なる。
【０１５８】
上記分割処理により、クラスタ数が１つ増加し、（ｋ’＋１）個のクラスタＣｋ（ｋ＝１，２，・・・，ｋ’，ｋ’＋１）が生成される。
【０１５９】
図１７は、第２のクラスタ生成部２４による分割処理の第１の例の具体的な処理例を示すフローチャートである。
【０１６０】
ステップＳ１５１では、現在のクラスタ数を示す変数ｋに、第１のクラスタ生成部２３により生成されたクラスタの個数であるＫ’を代入する。
【０１６１】
ステップＳ１５２では、変数の初期化処理を行う。この初期化処理では、ｉ＝１，Ｓｍａｘ＝０とされる。
【０１６２】
ステップＳ１５３では、クラスタＣｉに含まれるキーワードのうち、当該クラスタＣｉ内の全ての文書に含まれるキーワードを除く、当該クラスタＣｉ内の最も多くの文書に含まれるキーワードＫＷｔｍｐを特定する。このキーワードＫＷｔｍｐは、クラスタＣｉを分割するための分割用キーワードとなる。
【０１６３】
ステップＳ１５４では、クラスタＣｉに属する文書群を、キーワードＫＷｔｍｐを含む文書の集合である第１のクラスタＣ１ｉと、キーワードＫＷｔｍｐを含まない文書の集合である第２のクラスタＣ２ｉとに仮想的に分割する。
【０１６４】
ステップＳ１５５では、第２のクラスタＣ２ｉの特徴語スコアＳ’（ｉ）を算出する。具体的には、例えば上記式（１）により、第２のクラスタＣ２ｉにおける各キーワードのスコアを算出し、スコアの最大値を特徴語スコアＳ’（ｉ）とする。
【０１６５】
ステップＳ１５６では、上記算出された特徴語スコアＳ’（ｉ）がＳｍａｘより大きいか否かを判断し、Ｓｍａｘより大きければステップＳ１５７に進み、そうでなければステップＳ１５８に進む。
【０１６６】
ステップＳ１５７では、変数Ｓｍａｘに特徴語スコアＳ’（ｉ）を代入し、変数ｉｍａｘにｉを代入する。
【０１６７】
ステップＳ１５８では、変数ｉに１を加える。
【０１６８】
ステップＳ１５９では、変数ｉの値が変数ｋの値より大きいか否かを判断し、大きくなければステップＳ１５３に戻り、大きければステップＳ１６０に進む。すなわち、現在存在する全てのクラスタＣｉ（ｉ＝１，２，・・・，ｋ）について、ステップＳ１５３〜Ｓ１５８の処理が行われる。そして、ステップＳ１６０に進む際には、変数Ｓｍａｘの値は、特徴語スコアＳ’（ｉ）（ｉ＝１，２，・・・，ｋ）の最大値となっており、変数ｉｍａｘの値は、当該最大値に対応するクラスタのクラスタ番号となっている。
【０１６９】
ステップＳ１６０では、クラスタＣｉｍａｘをＣ１ｉｍａｘとＣ２ｉｍａｘとに分割し、クラスタ数を１つ増加させる。そして、当該分割後の（ｋ＋１）個のクラスタを、新たにクラスタＣｉ（ｉ＝１，２，・・・，ｋ＋１）とする。具体的には、変数Ｐｊ＿ｉｄ（ｊ＝１，２，・・・，Ｎ）の値を変更することにより、文書Ｐｊにクラスタ番号を振りなおす。
【０１７０】
ステップＳ１６１では、現在のクラスタ数を示す変数ｋに１を加える。
【０１７１】
ステップＳ１６２では、変数ｋの値がＫと等しいか否かを判断し、等しくない場合にはステップＳ１５２に戻り、等しい場合には処理を終了させる。すなわち、クラスタ総数がＫ個になるまで、ステップＳ１５２〜Ｓ１６１の処理が繰り返される。
【０１７２】
なお、上記ステップＳ１５３において、クラスタＣｉに含まれるキーワードのうち、当該クラスタＣｉ内の全ての文書に含まれるキーワードを除く、当該クラスタＣｉ内の最も多くの文書に含まれるキーワードを特定できない場合には、ステップＳ１５４の処理はスキップされ、ステップＳ１５５において変数Ｓ’（ｉ）に０が与えられる。したがって、当該クラスタＣｉは分割されない。
【０１７３】
なお、上記第１および第２の実施の形態において、クラスタ生成装置１０，２０はコンピュータであり、その機能は、ＲＯＭ(Read Only Memory)やハードディスク装置等の記録媒体に記録されたプログラムがメインメモリに読み出されてＣＰＵ(Central Processing Unit)により実行されることによって実現される。上記のプログラムは、ＣＤ−ＲＯＭ等の記録媒体に記録されて提供されることも可能であるし、データ信号として通信により提供されることも可能である。
【０１７４】
ただし、クラスタ生成装置の物理的な構成は、特に限定されない。例えば、クラスタ生成装置の機能は、ハードウェアのみにより実現されてもよい。また、クラスタ生成装置は、物理的に別々の装置により実現されてもよいし、物理的に１つの装置により実現されてもよい。
【０１７５】
なお、本発明は、上記実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内で種々変更することができる。例えば、上記第１および第２の実施の形態において、クラスタを２つに分割する処理に関し、分割後のクラスタに属する文書の数が所定数よりも少なくなる分割は行わない、という制限を設けてもよい。
【図面の簡単な説明】
【０１７６】
【図１】第１の実施の形態に係るクラスタ生成装置の構成の一例を示すブロック図である。
【図２】分割処理の第１の例を示すフローチャートである。
【図３】分割処理の第１の例を示す概念図である。
【図４】分割処理の第２の例を示すフローチャートである。
【図５】分割処理の第２の例を示す概念図である。
【図６】分割処理の第３の例を示すフローチャートである。
【図７】分割処理の第３の例を示す概念図である。
【図８】第２の実施の形態に係るクラスタ生成装置の構成の一例を示すブロック図である。
【図９】第２の実施の形態に係るクラスタ生成装置の動作手順の一例を示すフローチャートである。
【図１０】第１のクラスタ生成部によるクラスタリング処理の第１の例を示すフローチャートである。
【図１１】クラスタリング処理の第１の例の具体的な処理例を示すフローチャートである。
【図１２】第１のクラスタ生成部によるクラスタリング処理の第２の例を示すフローチャートである。
【図１３】クラスタリング処理の第２の例の具体的な処理例を示すフローチャートである。
【図１４】第２のクラスタ生成部による分割処理の第１の例を示すフローチャートである。
【図１５】第２のクラスタ生成部による分割処理の第２の例を示すフローチャートである。
【図１６】第２のクラスタ生成部による分割処理の第３の例を示すフローチャートである。
【図１７】第２のクラスタ生成部による分割処理の第１の例の具体的な処理例を示すフローチャートである。
【符号の説明】
【０１７７】
１０，２０  クラスタ生成装置、１１  クラスタ取得部、１２  クラスタ生成部、２１  文書群取得部、２２  キーワード取得部、２３  第１のクラスタ生成部、２４  第２のクラスタ生成部、２５  スコア算出部、２６  出力部。
【図１】
2008204374.tif 000006
【図２】
2008204374.tif 000007
【図３】
2008204374.tif 000008
【図４】
2008204374.tif 000009
【図５】
2008204374.tif 000010
【図６】
2008204374.tif 000011
【図７】
2008204374.tif 000012
【図８】
2008204374.tif 000013
【図９】
2008204374.tif 000014
【図１０】
2008204374.tif 000015
【図１１】
2008204374.tif 000016
【図１２】
2008204374.tif 000017
【図１３】
2008204374.tif 000018
【図１４】
2008204374.tif 000019
【図１５】
2008204374.tif 000020
【図１６】
2008204374.tif 000021
【図１７】
2008204374.tif 000022