(57)【要約】【課題】階層型クラスタに対する逐次的なデータ更新に対して再クラスタリングを行なわずに階層型クラスタ構造の適正を維持させる。【解決手段】クラスタリング装置として、分類対象とするデータ群について階層的クラスタリングを実行して階層型クラスタを出力する階層化データ分類手段と、データ群に新規に更新を受け付けて逐次的に、階層型クラスタに更新内容のデータを更新ノードとして反映させると共に、階層型クラスタ内での変更が加わったクラスタについて識別処理して、識別結果に基づいて該クラスタ階層を分割もしくは維持もしくは他の階層との統合を判定処理し、判定結果に基づいた階層型クラスタに階層構造を再構成処理して出力するデータ更新手段と、を有する構成とする。【選択図】図１
2014174797.tif 000002
【特許請求の範囲】
【請求項１】
分類対象とするデータ群について階層的クラスタリングを実行して階層型クラスタを出力する階層化データ分類手段と、
前記データ群に新規に更新を受け付けて逐次的に、前記階層型クラスタに更新内容のデータを更新ノードとして反映させると共に、前記階層型クラスタ内での変更が加わったクラスタについて識別処理して、識別結果に基づいて該クラスタ階層を分割もしくは維持もしくは他の階層との統合を判定処理し、判定結果に基づいた階層型クラスタに階層構造を再構成処理して出力するデータ更新手段と、
を有することを特徴とするクラスタリング装置。
【請求項２】
請求項１記載のクラスタリング装置であって、
前記データ更新手段は、
前記階層型クラスタに前記更新ノードを反映させた後に、前記階層型クラスタ内での変更が加わったクラスタについて該クラスタ内のノード群の関連性と該クラスタと他のクラスタとの関連性とを識別処理して、該クラスタ階層の分割又は他の階層との統合の処理内容を決定する
ことを特徴とするクラスタリング装置。
【請求項３】
請求項２記載のクラスタリング装置であって、
前記データ更新手段は、既存ノード変更手段と、既存ノード削除手段と、クラスタ統合手段とを含み、
前記既存ノード変更手段は、既存のデータ集合から更新するデータを前記更新ノードとして識別して該当ノードを変更すると共に、更新前の階層型クラスタの各クラスタとの関連性を取得して、所属先となる全てのクラスタを決定して関連付け、
前記既存ノード削除手段は、既存のデータ集合から削除するデータを前記更新ノードとして識別して該当ノードを削除し、
前記クラスタ統合手段は、前記既存ノード変更手段又は前記既存ノード削除手段による前記更新ノードの反映後に、変更が加わったクラスタについて、クラスタ統合条件を満たすと判別した際に、該当クラスタと残りの各クラスタとの関連性を識別すると共に、識別した関連性に基づいてデータの更新に伴い更新されたクラスタとクラスタ統合条件を満たしたクラスタとを統合処理する
ことを特徴とするクラスタリング装置。
【請求項４】
請求項３記載のクラスタリング装置であって、
前記データ更新手段は、新規ノード追加手段と、クラスタ分割手段とを更に含み、
前記新規ノード追加手段は、既存のデータ集合に追加する新たなデータを前記更新ノードとして識別すると共に、更新前の階層型クラスタの各クラスタとの関連性を取得して、所属先となる全てのクラスタを決定し、
前記クラスタ分割手段は、前記新規ノード追加手段、前記既存ノード変更手段もしくは前記クラスタ統合手段の何れかによる前記更新ノードの反映後に、変更が加わったクラスタについて、クラスタ分割条件を満たした判別した際に、当該クラスタ内の各ノード間の関連性を取得すると共に、該関連性を反映させてノード群を２組に分割処理する
ことを特徴とするクラスタリング装置。
【請求項５】
請求項３又は４に記載のクラスタリング装置であって、
前記クラスタ統合条件として、該当クラスタ内のノード数が閾値以下になった、他のクラスタとの関連性を示す距離が閾値以下になった、或いはこれらを複数組み合わせた条件の何れかを用いる
ことを特徴とするクラスタリング装置。
【請求項６】
請求項４又は５に記載のクラスタリング装置であって、
前記クラスタ分割条件として、該当クラスタ内のノード数が閾値以上になった、クラスタ内のノード間の関連性を示す距離の最大値が閾値以上になった、或いはこれらを複数組み合わせた条件の何れかを用いる
ことを特徴とするクラスタリング装置。
【請求項７】
請求項１ないし６の何れか一項に記載のクラスタリング装置であって、
前記データ更新手段は、カウンタを有してなり、
前記階層型クラスタの再構成処理を実行する回数若しくは実行した回数をカウントし、該カウント値が所定数を超えた際に、前記カウント開始後に発生した更新ノードに関連するクラスタに属する全データについて再クラスタリングを実行させる
ことを特徴とするクラスタリング装置。
【請求項８】
請求項１ないし６の何れか一項に記載のクラスタリング装置であって、
前記データ更新手段は、カウンタを有してなり、
前記階層型クラスタの再構成処理を実行する回数若しくは実行した回数をカウントし、該カウント値が所定数を超えた際に、全データ集合への再クラスタリングを実行させる
ことを特徴とするクラスタリング装置。
【請求項９】
分類対象とするデータ群について階層的クラスタリングを実行して生成された階層型クラスタを有して、前記データ群に新規に更新を受け付けて逐次的に、
前記階層型クラスタに更新内容のデータを更新ノードとして反映させ、
前記階層型クラスタ内での変更が加わったクラスタについて識別処理して、識別結果に基づいて該クラスタ階層を分割もしくは維持もしくは他の階層との統合を判定処理し、
判定結果に基づいた階層型クラスタに階層構造を再構成処理して記憶手段に出力する
ことを特徴とする情報処理システムによる階層クラスタリング再構成方法。
【請求項１０】
情報処理システムの制御部を、
分類対象とするデータ群について階層的クラスタリングを実行して生成された階層型クラスタを更新対象として識別している環境で、前記データ群に新規に更新を受け付けて逐次的に、
前記階層型クラスタに更新内容のデータを更新ノードとして反映させると共に、前記階層型クラスタ内での変更が加わったクラスタについて識別処理して、識別結果に基づいて該クラスタ階層を分割もしくは維持もしくは他の階層との統合を判定処理し、判定結果に基づいた階層型クラスタに階層構造を再構成処理して記憶手段に出力する
データ更新手段、
として動作させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ集合を指標に基づき分類するデータ分類技術に関し、詳しくは、階層的クラスタ構造を有した分類結果にデータ集合を分類するクラスタ分類技術に関する。
【背景技術】
【０００２】
昨今、大量に存在するデータ集合を自動的に分類するための手法として、何らかの指標に沿ってデータ集合をいくつかのまとまりに分けるクラスタリングが用いられている。
【０００３】
このようなクラスタリングを行なう技術は、例えば特許文献１に記載されている。  
特許文献１に記載された文書分類装置は、分類対象たる文書（文書ＩＤ、作成時刻（登録時刻）、タイトル及び本文をデータとして保持）群を、任意に指定した指標に基づいて過去に存在した距離が近い文書とツリー構造を持たせるようにデータ集合の関連性をデータ化した後に、該関連性に従ってクラスタリング処理を実施し、加えて、任意の２つの日時を指定して、その間に属する文書群のみをクラスタリング結果を再構築して出力する。
このように動作させることで、所望期間の文書群の抽出とその関連性（元のツリー構造に現われていた関連性が踏まえられている）が認知可能に図表化して示せるようになり、多量の情報整理に役立つ。
【０００４】
また、データ数が膨大な場合には、データ集合を階層的に分類した階層的クラスタ構造が用いられることがある。階層的クラスタ構造は、分類結果を参照する際に関連性の認知度の向上や、情報処理としての速度向上などに利点がある。
【０００５】
このような階層的クラスタリングを行なう技術は、例えば特許文献２に記載されている。  
特許文献２に記載したデータ分類装置は、分類対象たるデータ集合の階層的クラスタ構造を有した分類結果から、各クラスタを代表するデータを適切に抽出処理する方法を開示している。この方法によれば、上位層でも中心的な位置付けとなる１つのデータを導出できる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００８−２３４４８２号公報
【特許文献２】特開２０１１−００３１５６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記した特許文献１や特許文献２に記載されているクラスタリング手法はそれぞれ利点を有している。
【０００８】
一方で、クラスタリング手法を能率よく運用する際に一つの指標として、分類に要する時間（処理リソース量）や、データの追加や削除などの運用性について考えなければならない。この運用性と 分類結果である階層構造を含むクラスタ構造の適切性について、両立を図ることが必要である。この問題は、分類対象のデータ量が増えれば増えるほど大きな問題となる。  
具体的に問題を述べれば、階層的分類が行われたデータ集合に対して新規にデータを追加した際に、新規に追加されたデータと既存のデータ集合との組み合わせの集合に対して再度階層化クラスタリングを行なう必要が生じる。また、データの削除、変更も同様であり、単純に削除するのみや変更するのみでは、分類結果に与えた影響が反映されないこととなる。この場合にもクラスタ構造や階層構造の適切性について担保する際に変更後のデータ集合に再クラスタリングを行う必要が生じる。
【０００９】
しかしながら、大量のデータをクラスタリングするには一般的に膨大な計算リソースを消費することとなるため、新規に追加等のデータ更新を行なった際に再クラスタリングを避ける得る追加方法が望まれる。
【００１０】
例えば、上記した特許文献２には、階層的クラスタ構造において、クラスタ作成後の新規データの追加や既存データの変更、削除等に伴う階層的クラスタの再構成方法について述べられていない。このため、特許文献２に記載された文書分類装置で、新規にデータ更新を行なった際にクラスタ構造と階層構造の適切性について担保する場合に再クラスタリングを行う必要が生じる。さもしなければ、分類指標に基づくと異なるクラスタや階層に属すべきデータが変更前の元クラスタと元階層に存在することになる。結果、多量の処理リソースがデータ更新の際に再クラスタリングのために生じるシステムと成っている。
【００１１】
換言すれば、既存の階層的クラスタリング手法は、頻繁にデータ更新されるデータ集合に対する階層的クラスタ分類には向かない側面を有している。この課題について既存技術を踏まえつつ解決を図る。
【００１２】
本発明は、上記課題に鑑み、分類した階層型クラスタに対して新たにデータ更新を都度行う際に階層型クラスタへのデータ更新と共に階層型クラスタの階層を調整する階層クラスタリング装置、階層クラスタリング再構成方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明に係るクラスタリング装置は、分類対象とするデータ群について階層的クラスタリングを実行して階層型クラスタを出力する階層化データ分類手段と、前記データ群に新規に更新を受け付けて逐次的に、前記階層型クラスタに更新内容のデータを更新ノードとして反映させると共に、前記階層型クラスタ内での変更が加わったクラスタについて識別処理して、識別結果に基づいて該クラスタ階層を分割もしくは維持もしくは他の階層との統合を判定処理し、判定結果に基づいた階層型クラスタに階層構造を再構成処理して出力するデータ更新手段と、を有することを特徴とする。
【００１４】
また、本発明に係る情報処理システムによる階層クラスタリング再構成方法は、分類対象とするデータ群について階層的クラスタリングを実行して生成された階層型クラスタを有して、前記データ群に新規に更新を受け付けて逐次的に、前記階層型クラスタに更新内容のデータを更新ノードとして反映させ、前記階層型クラスタ内での変更が加わったクラスタについて識別処理して、識別結果に基づいて該クラスタ階層を分割もしくは維持もしくは他の階層との統合を判定処理し、判定結果に基づいた階層型クラスタに階層構造を再構成処理して記憶手段に出力することを特徴とする。
【００１５】
また、本発明に係るプログラムは、情報処理システムの制御部を、分類対象とするデータ群について階層的クラスタリングを実行して生成された階層型クラスタを更新対象として識別している環境で、前記データ群に新規に更新を受け付けて逐次的に、前記階層型クラスタに更新内容のデータを更新ノードとして反映させると共に、前記階層型クラスタ内での変更が加わったクラスタについて識別処理して、識別結果に基づいて該クラスタ階層を分割もしくは維持もしくは他の階層との統合を判定処理し、判定結果に基づいた階層型クラスタに階層構造を再構成処理して記憶手段に出力するデータ更新手段、として動作させることを特徴とする。
【発明の効果】
【００１６】
本発明によれば、分類した階層型クラスタに対して新たにデータ更新を都度行う際に階層型クラスタへのデータ更新と共に階層型クラスタの階層を調整する階層クラスタリング装置、階層クラスタリング再構成方法およびプログラムを提供できる。
【図面の簡単な説明】
【００１７】
【図１】本発明の実施形態にかかるシステム構成図である。
【図２】階層クラスタリング装置１のデータ更新部２０にかかる処理動作を例示するフローチャートである。
【図３】データ更新部２０の構成例を示すブロック図である。
【図４】階層型クラスタ情報の一例を模式的に示した説明図である。
【図５】新規ノード追加手段２１の処理動作例を示すフローチャートである。
【図６】既存ノード更新手段２２の処理動作例を示すフローチャートである。
【図７】既存ノード削除手段２３の処理動作例を示すフローチャートである。
【図８】クラスタ統合手段２４の処理動作例を示すフローチャートである。
【図９】クラスタ分離手段２５の処理動作例を示すフローチャートである。
【図１０】階層クラスタリング装置１の構成例を示したブロック図である。
【発明を実施するための形態】
【００１８】
本発明の実施形態を図１及び図２を参照して説明する。
【００１９】
図１は、実施形態の階層クラスタリング装置１を示したシステム構成図である。階層クラスタリング装置１は、パーソナルコンピュータ等のプログラムに従って動作する情報処理装置によって実現すればよい。  
図１には、階層型クラスタを生成するデータ集合（元データ）を記憶保持するデータベース２と、生成物たる階層型クラスタを生成及び更新する階層クラスタリング装置１と、生成及び更新された階層型クラスタを使用者に提示する提示装置３とが記載されている。
【００２０】
階層クラスタリング装置１は、データベース２に保持された分類対象とするデータ群についてデータ個々をノードとして階層的クラスタリングを実行する階層化データ分類部１０と、データベース２に新規に更新を受け付けた際に、生成済みの階層型クラスタについて階層構造の見直しを含めて更新処理するデータ更新部２０とを備える。階層クラスタリング装置１は、適宜 生成又は更新した階層的クラスタを提示装置３に出力する。なお、出力する階層的クラスタは、階層クラスタリング装置１内に準備された記憶手段（バッファやメモリ、補助記憶領域）に一時記憶する構成としてもよい。また、提示装置３に提示させる為に表示手段（表示プログラムやパッチなど）を有していても良いし、他の汎用プログラムを用いて生成又は更新した階層的クラスタを描写や印刷などを行なえるように構成されてもよい。
【００２１】
階層化データ分類部１０は、階層型クラスタを得るどのような手法を用いてもよい。例えば、特許文献２で開示したデータ分類方法を用いてもよいし、他の方法を用いてもよい。階層化データ分類部１０は、データベース２からクラスタリングを行なうデータ集合を取得して階層型クラスタを生成する。この生成した階層型クラスタは、提示装置３に出力されると共に、データ集合の更新に合わせて、階層型クラスタの更新を行なえるようにする為に、データ更新部２０が取得可能に保持される。この保持行為は、階層化データ分類部１０が行ってもよいし、データ更新部２０が行ってもよい。また、他にデータベースを用いて行なうこととしてもよい。
【００２２】
データ更新部２０は、データベース２（データ集合）の更新を受け付けつけて逐次的に、階層型クラスタに更新内容のデータを更新ノードとして反映させる処理を行う。この処理では、更新ノードと作成済みの階層型クラスタの各要素（クラスタ、ノード）との関連性を反映させて、更新ノードを反映させる位置を導出する。なお、ここで用いられる要素間の関連性は、階層化データ分類部１０で階層型クラスタを生成した際に用いた関連性を用いることが望ましい。
【００２３】
次に、データ更新部２０は、上記処理によって、階層型クラスタ内での変更が加わったクラスタについて要素間の関連性を識別処理する。この識別結果に基づいて、変更が加わったクラスタを維持するか、クラスタ階層を分割するか、他の階層と統合するかを判定処理して、その階層構造を得るために必要に応じた再構成処理を加え、更新後の階層型クラスタを記憶手段に蓄積したり、提示装置３に出力する。なお、統合条件と分割条件について、後に幾つか実施例を用いて例示する。
【００２４】
データベース２は、階層クラスタリング装置１と同一筐体内もしくは別途準備された記憶装置であって、内部インタフェースや通信ネットワークを介して階層クラスタリング装置１と接続されている。なお、階層クラスタリング装置１内に取り込まれても構わない。このデータベース２に記憶保持されたデータ集合から階層型クラスタが生成される。また、人間や他の情報処理装置からの入力や、データの自動収集、自動更新などの様々な入力手段によって、データ集合が更新された際に、階層クラスタリング装置１がデータ更新部２０を動作させる。なお、データベース２とデータ更新部２０との連携タイミングは、必ずしも完全に一致している必要はなく、データベース２が更新されたタイミング、人間が階層クラスタリング装置１を操作したタイミング、人間が階層クラスタの更新を指示したタイミングなどの所要タイミングを受けて、更新された順に逐次的に階層クラスタの更新処理を実行すればよい。
【００２５】
提示装置３は、一般的なモニタやプリンタなどである。また、提示装置３側に提示用プログラムを有していてもよい。
【００２６】
次に、階層クラスタリング装置１の処理動作について説明する。なお、階層化データ分類部１０によるクラスタリング処理は説明を省略する。以下ではデータ更新部２０の処理動作例について説明する。
【００２７】
図２は、データ更新部２０にかかる階層クラスタリング装置１の処理動作を例示したフローチャートである。データ更新部２０は、階層化データ分類部１０または以前にデータ更新部２０自身が更新した階層クラスタを、データ集合の更新に合わせて更新する。
【００２８】
データベース２（データ集合）が更新されて階層型クラスタを更新する際に、階層クラスタリング装置１と成る情報処理システムの制御部は、更新データの反映と反映先のクラスタを特定する（Ｓ１０１）。
【００２９】
次に、制御部は、特定したクラスタに関する要素間の関連性を識別する（Ｓ１０２）。この処理により、更新ノードが現在の階層型クラスタに与える階層構造に関した影響が生じる箇所（範囲）を判別処理する。
【００３０】
次に、制御部は、更新ノードが反映されるクラスタについて、階層的構造を維持するか、統合するか、分割するかを、クラスタ分割条件とクラスタ統合条件を参照して判定処理する（Ｓ１０３）。
【００３１】
制御部は、階層構造を維持する際には、階層型クラスタの定義済みの階層構造を変更せずに、反映した更新ノードに関するノード間やノード−クラスタ間、クラスタ間の情報を整理して、更新された階層型クラスタを生成する（Ｓ１０４）。
【００３２】
一方、制御部は、階層構造を統合する際には、更新されたノード（更新ノード）に関するクラスタと他の要素との関連性を識別処理することにより、該識別結果より統合に適する統合先クラスタや、更新ノードが含まれていたクラスタ内や統合先クラスタ内、隣接クラスタ内から他のクラスタへ移動させるノードやその個数などを判別して、クラスタ間の統合、統合と共に所要ノードのクラスタ移動等をクラスタ統合条件に則して実行して、更新された階層型クラスタを生成する（Ｓ１０５）。
【００３３】
他方、制御部は、階層構造を分離する際には、更新されたノード（更新ノード）に関するクラスタ内要素との関連性を識別処理することにより、該識別結果より分離に適するノード分けを判別して、クラスタ内の分離をクラスタ分割条件に則して実行して、更新された階層型クラスタを生成する（Ｓ１０６）。なお、上記識別処理に、更新ノードと隣接クラスタとの関連性、更新するクラスタと隣接クラスタとの関連性、更には隣接クラスタに属する各ノードとの更新するクラスタ若しくは更新ノードの関連性を反映させて、分割後の接続関係や、分割後のクラスタ内への他のクラスタからのノード移動を実行してもよい。
【００３４】
次に、制御部は、更新した階層型クラスタを記憶手段への書き込みや出力手段への送出を実行する（Ｓ１０７）。
【００３５】
このように階層クラスタリング装置１を動作させることにより、データ更新部２０が新規に更新を受け付けて逐次的に動的な階層型クラスタの再構成を、データ更新範囲を限定して実施する。このことにより、全データへの再クラスタリングを行う場合に比べ、演算リソース量を抑えられる。
【００３６】
なお、データ更新部２０は、カウンタを内在して、階層型クラスタの再構成処理を実行する回数若しくは実行した回数をカウントすることを行なって処理方法を変更しても良い。このカウント値は、所定数を超えた際に、全データ集合への再クラスタリングを階層化データ分類部１０に実行させることに使用できる。また、全データ集合に変えて、カウント開始後に発生した更新ノードに関連した全クラスタに属する全データについて再クラスタリングを実行させるようにしてもよい。
【００３７】
また、カウントする際に、階層構造の維持、階層の分離、他階層との統合それぞれに所定係数を定義して、カウント値の蓄積度合いに差を与えるとより運用性に優れたタイミングを導出できる。
【００３８】
また、上記カウント値に基づいた再サンプリングを実行する際にも操作者への許諾を求める構成としてもよい。また、閾値とするカウント値も再サンプリングの実行を促す閾値と自動実行する閾値とを設けてもよい。
【００３９】
次に、上記実施形態のデータ更新部２０のより具体的な構成例とより具現化した処理例を示して、本発明を説明する。  
図３は、実施例にかかるデータ更新部２０の構成を示すブロック図である。  
図３を参照すると、データ更新部２０は、新規ノード追加手段２１、既存ノード変更手段２２、既存ノード削除手段２３、クラスタ統合手段２４、クラスタ分割手段２５を含み、構成されている。
【００４０】
新規ノード追加手段２１は、ユーザの操作や自動更新などにより入力手段を介して入力された新規データ（更新データ）に対して、入力された更新データの値や属性などに則して階層型クラスタの適切な位置に追加する機能を備えている。  
既存ノード変更手段２２は、入力手段を介してデータの有する値や属性などが変更された更新データを、その更新データの値や属性などに則して階層型クラスタの適切な位置に移動する機能を備えている。  
既存ノード削除手段２３は、入力手段を介して削除されたデータを、階層型クラスタから削除する機能を備えている。
【００４１】
クラスタ統合手段２４は、既存ノード変更手段２２または既存ノード削除手段２３により、階層内のノード数が閾値以下になる、他クラスタとの差異を示す値が閾値以下になるなどのクラスタ統合条件を満たした場合に、その他の適切な層と統合する機能を備えている。  
クラスタ分割手段２５は、新規ノード追加手段２１、既存ノード変更手段２２またはクラスタ統合手段２４により、階層内のノード数が閾値以上になる、階層内のデータのばらつきが閾値以上になるなどのクラスタ分割条件を満たした場合、その層を２つに分割する機能を備えている。
【００４２】
図４は、階層的にクラスタリングを行った結果である階層型クラスタ情報を模式的に示した一例である。  
丸印がデータ集合に含まれる各データを表している個々のノードである。データ集合に階層的にクラスタリングを実施した結果として、図示されるようにc1〜c3及びc1-1〜c3-5のように階層構造を有するクラスタ分類を行なっている。なお、c1-1内には３つのデータがあるが、この３つのデータがクラスタc1-1に所属するノード（即ちこのクラスタに属するデータ）である。また、クラスタc1内部にはクラスタc1-1〜c1-4が含まれており、クラスタc1がクラスタc1-1〜c1-4の上位クラスタであることを示している。  
このように、階層型クラスタ情報では、任意のノードは複数階層に亘って複数のクラスタに属することがある。このような各ノード（データ）の位置と所属階層等を適切に追加、削除する。
【００４３】
次に、図３に示したデータ更新部２０の処理動作について、図５、図６、図７、図８、図９に示す各手段のフローチャートを用いて説明する。
【００４４】
図５、図６、図７は、データ反映手段として動作する新規ノード追加手段２１、既存ノード更新手段２２及び既存ノード削除手段２３に関するフローチャートである。図８、図９は、階層調整手段として動作するクラスタ統合手段２４及びクラスタ分離手段２５に関するフローチャートである。
【００４５】
データ更新部２０は、データ反映手段として機能する際に、以下のように動作する。
【００４６】
入力された更新データを識別して新規ノードとする更新データであった際に、新規ノード追加手段２１は、入力されたデータを新規ノード追加キューに追加（ステップＳ２１１）後に、新規ノード追加キューを参照して追加された更新データの内容を識別する（ステップＳ２１２）。  
次に、新規ノード追加手段２１は、更新ノード（データ）と各クラスタとの関連性を取得(ステップＳ２１３)して、この関連性を示す値から、この階層で所属するクラスタを決定する(ステップＳ２１４)。関連性を示すものとして、Ｗｅｂページ間のハイパーリンクのような明示的な関連性や、各データ間の類似度や相関係数から算出される関連性などが例示できる。他の関連性を指標として用いても構わない。  
次に、新規ノード追加手段２１は、現在チェックしている層より下位の層があるか判別（ステップＳ２１５）して、下位層がある場合には、１つ下の層に移動（ステップＳ２１６）し、ステップＳ２１３とステップＳ２１４とを繰り返して、更新データの影響範囲を判別する。
【００４７】
入力された更新データを識別して既存ノードの更新であった際に、既存ノード変更手段２２は、入力された該当データのノードを検索(ステップＳ２２１)後に、該当ノードを更新された値に変更する(ステップＳ２２２)。  
次に、既存ノード変更手段２２は、更新ノード（該当ノード）を現在の所属クラスタから除外(ステップＳ２２３)した後に、更新ノードと各クラスタとの関連性を取得(ステップＳ２２４)して、この関連性を示す値から、この階層で更新後に所属するクラスタを決定する(ステップＳ２２５)。関連性を示す指標は、新規ノード追加手段２１と同様のものを用いる。  
次に、既存ノード変更手段２２は、現在チェックしている層より下位の層があるか判別（ステップＳ２２６）して、下位層がある場合には、１つ下の層に移動（ステップＳ２２７）し、ステップＳ２２４とステップＳ２２５を繰り返して、更新データの影響範囲を判別する。
【００４８】
入力された更新データが既存ノードを削除であった際に、既存ノード削除手段２３は、該当ノードを検索(ステップＳ２３１)し、該当ノードを各所属クラスタから削除する(ステップＳ２３２)。
【００４９】
次に、データ更新部２０は、階層調整手段として機能する際に、以下のように動作する。
【００５０】
クラスタ統合手段２４は、クラスタ統合条件を満たすか判定（Ｓ２４１）して条件を満たした場合に、この階層での該当クラスタと各クラスタとの関連性を取得 (ステップＳ２４２)し、取得した関連性を示す値からこの階層で統合するクラスタを決定する(ステップＳ２４３)。クラスタ統合条件例としては、該当クラスタ内のノード数が閾値以下になった、他のクラスタとの関連性を示す距離が閾値以下になった、或いはこれらを複数組み合わせた条件などを与えればよい。  
次に、クラスタ統合手段２４は、現在チェックしている層より上位の層があるか判別（ステップＳ２４４）して、上位層がある場合には、１つ上の層に移動（ステップＳ２４５）し、上位のクラスタに対してもクラスタ統合条件を満たすか判定する。
【００５１】
また、クラスタ分割手段２５は、クラスタ分割条件を満たすか判定（Ｓ２５１）して条件を満たした場合に、この階層での該当する既存クラスタ内の更新ノードを含む各ノード間の関連性を取得(ステップＳ２５２)すると共に分割先とするクラスタを新規に作成 (ステップＳ２５３)し、取得した関連性を示す距離が最も遠い値であった２つのノードを選択して、既存クラスタと新規クラスタに所属先を振り分ける(ステップＳ２５４)。  
次に、クラスタ分割手段２５は、振り分け後の既存クラスタ内の更新ノードを含む各ノードと、新規クラスタ及び既存クラスタの関連性を取得(ステップＳ２５５)し、取得した関連性を示す値から各ノードの所属するクラスタを決定する(ステップＳ２５６)。クラスタ分割条件例としては、該当クラスタ内のノード数が閾値以上になった、クラスタ内のノード間の関連性を示す距離の最大値が閾値以上になった、或いはこれらを複数組み合わせた条件を与えればよい。  
次に、クラスタ分割手段２５は、現在チェックしている層より上位の層があるか判別（ステップＳ２５７）して、上位層がある場合には、１つ上の層にチェックを移動（ステップＳ２５８）し、上位のクラスタに対してもクラスタ分割条件を満たすか判定する。
【００５２】
このようにデータ更新部２０の構成及び処理動作させることで、先行技術にある階層型クラスタ分類処理では行えなかった、クラスタリング後の構造型クラスタへのデータ追加、変更、削除が容易になる。これは、逐次的なデータ追加、変更、削除に伴う動的なクラスタの再構成を、データ追加等が行われた範囲に限定して実施することを実施しており、全データへの再クラスタリングを行う場合に比べ、演算リソース量を抑えられる。
【００５３】
尚、階層クラスタリング装置の各部は、ハードウェアとソフトウェアの組み合わせを用いて実現すればよい。ハードウェアとソフトウェアとを組み合わせた形態では、ＲＡＭに本発明にかかる階層的クラスタリング用プログラムが展開され、このプログラムに基づいて制御部（ＣＰＵ）等のハードウェアを動作させることによって、各部を各種手段として実現する。また、前記プログラムは、記憶媒体に固定的に記録されて頒布されても良い。当該記録媒体に記録されたプログラムは、有線、無線、又は記録媒体そのものを介して、メモリに読込まれ、制御部等を動作させる。尚、記録媒体を例示すれば、オプティカルディスクや磁気ディスク、半導体メモリ装置、ハードディスクなどが挙げられる。
【００５４】
上記実施形態を別の表現で説明すれば、階層クラスタリング装置として動作させる情報処理システムを、ＲＡＭに展開された上記プログラムに基づき、階層化データ分類手段、データ更新手段としてＣＰＵを動作させることで実現することが可能である。また、新規ノード追加手段、既存ノード更新手段、既存ノード削除手段、クラスタ統合手段、クラスタ分離手段も同様である。
【００５５】
以上、実施形態を図示して説明したが、そのブロック構成やプログラムの分離併合、手順の入れ替えなどの変更は本発明の趣旨および説明される機能を満たせば自由であり、上記説明が本発明を限定するものではない。
【００５６】
例えば、図１０に例示するように、データベースを内在するする構成としたり、クラスタリング用のプログラムと更新用のプログラムを分割したりすることも可能である。
【００５７】
以上説明したように、本発明によれば、分類した階層型クラスタに対して新たにデータ更新を都度行う際に階層型クラスタへのデータ更新と共に階層型クラスタの階層を調整する階層クラスタリング装置、階層クラスタリング再構成方法およびプログラムを提供できる。
【００５８】
また、上記の実施形態の一部又は全部は、以下のようにも記載されうる。尚、以下の付記は本発明をなんら限定するものではない。  
［付記１］
分類対象とするデータ群について階層的クラスタリングを実行して階層型クラスタを出力する階層化データ分類手段と、
前記データ群に新規に更新を受け付けて逐次的に、前記階層型クラスタに更新内容のデータを更新ノードとして反映させると共に、前記階層型クラスタ内での変更が加わったクラスタについて識別処理して、識別結果に基づいて該クラスタ階層を分割もしくは維持もしくは他の階層との統合を判定処理し、判定結果に基づいた階層型クラスタに階層構造を再構成処理して出力するデータ更新手段と、
を有することを特徴とするクラスタリング装置。
【００５９】
［付記２］
上記付記記載のクラスタリング装置であって、
前記データ更新手段は、
前記階層型クラスタに前記更新ノードを反映させた後に、前記階層型クラスタ内での変更が加わったクラスタについて該クラスタ内のノード群の関連性と該クラスタと他のクラスタとの関連性とを識別処理して、該クラスタ階層の分割又は他の階層との統合の処理内容を決定する
ことを特徴とするクラスタリング装置。
【００６０】
［付記３］
上記付記記載のクラスタリング装置であって、
前記データ更新手段は、既存ノード変更手段と、既存ノード削除手段と、クラスタ統合手段とを含み、
前記既存ノード変更手段は、既存のデータ集合から更新するデータを前記更新ノードとして識別して該当ノードを変更すると共に、更新前の階層型クラスタの各クラスタとの関連性を取得して、所属先となる全てのクラスタを決定して関連付け、
前記既存ノード削除手段は、既存のデータ集合から削除するデータを前記更新ノードとして識別して該当ノードを削除し、
前記クラスタ統合手段は、前記既存ノード変更手段又は前記既存ノード削除手段による前記更新ノードの反映後に、変更が加わったクラスタについて、クラスタ統合条件を満たすと判別した際に、該当クラスタと残りの各クラスタとの関連性を識別すると共に、識別した関連性に基づいてデータの更新に伴い更新されたクラスタとクラスタ統合条件を満たしたクラスタとを統合処理する
ことを特徴とするクラスタリング装置。
【００６１】
［付記４］
上記付記記載のクラスタリング装置であって、
前記データ更新手段は、新規ノード追加手段と、クラスタ分割手段とを更に含み、
前記新規ノード追加手段は、既存のデータ集合に追加する新たなデータを前記更新ノードとして識別すると共に、更新前の階層型クラスタの各クラスタとの関連性を取得して、所属先となる全てのクラスタを決定し、
前記クラスタ分割手段は、前記新規ノード追加手段、前記既存ノード変更手段もしくは前記クラスタ統合手段の何れかによる前記更新ノードの反映後に、変更が加わったクラスタについて、クラスタ分割条件を満たした判別した際に、当該クラスタ内の各ノード間の関連性を取得すると共に、該関連性を反映させてノード群を２組に分割処理する
ことを特徴とするクラスタリング装置。
【００６２】
［付記５］
上記付記記載のクラスタリング装置であって、
前記クラスタ統合条件として、該当クラスタ内のノード数が閾値以下になった、他のクラスタとの関連性を示す距離が閾値以下になった、或いはこれらを複数組み合わせた条件の何れかを用いる
ことを特徴とするクラスタリング装置。
【００６３】
［付記６］
上記付記記載のクラスタリング装置であって、
前記クラスタ分割条件として、該当クラスタ内のノード数が閾値以上になった、クラスタ内のノード間の関連性を示す距離の最大値が閾値以上になった、或いはこれらを複数組み合わせた条件の何れかを用いる
ことを特徴とするクラスタリング装置。
【００６４】
［付記７］
上記付記記載のクラスタリング装置であって、
前記データ更新手段は、カウンタを有してなり、
前記階層型クラスタの再構成処理を実行する回数若しくは実行した回数をカウントし、該カウント値が所定数を超えた際に、全データ集合への再クラスタリングを実行させる
ことを特徴とするクラスタリング装置。
【００６５】
［付記８］
上記付記記載のクラスタリング装置であって、
前記データ更新手段は、カウンタを有してなり、
前記階層型クラスタの再構成処理を実行する回数若しくは実行した回数をカウントし、該カウント値が所定数を超えた際に、前記カウント開始後に発生した更新ノードに関連するクラスタに属する全データについて再クラスタリングを実行させる
ことを特徴とするクラスタリング装置。
【００６６】
［付記９］
分類対象とするデータ群について階層的クラスタリングを実行して生成された階層型クラスタを有して、前記データ群に新規に更新を受け付けて逐次的に、
前記階層型クラスタに更新内容のデータを更新ノードとして反映させ、
前記階層型クラスタ内での変更が加わったクラスタについて識別処理して、識別結果に基づいて該クラスタ階層を分割もしくは維持もしくは他の階層との統合を判定処理し、
判定結果に基づいた階層型クラスタに階層構造を再構成処理して記憶手段に出力する
ことを特徴とする情報処理システムによる階層クラスタリング再構成方法。
【００６７】
［付記１０］
上記付記記載の階層クラスタリング再構成方法であって、
前記情報処理システムは、
前記階層型クラスタに前記更新ノードを反映させた後に、前記階層型クラスタ内での変更が加わったクラスタについて該クラスタ内のノード群の関連性と該クラスタと他のクラスタとの関連性とを識別処理して、該クラスタ階層の分割又は他の階層との統合の処理内容を決定する
ことを特徴とする階層クラスタリング再構成方法。
【００６８】
［付記１１］
上記付記記載の階層クラスタリング再構成方法であって、
前記情報処理システムは、
既存ノードを変更する際に、既存のデータ集合から更新するデータを前記更新ノードとして識別して該当ノードを変更すると共に、更新前の階層型クラスタの各クラスタとの関連性を取得して、所属先となる全てのクラスタを決定して関連付け、
または、既存ノードを削除する際に、既存のデータ集合から削除するデータを前記更新ノードとして識別して該当ノードを削除し、
既存ノードの変更又は削除の反映と共に、
変更が加わったクラスタについて、クラスタ統合条件を満たすと判別した際に、該当クラスタと残りの各クラスタとの関連性を識別すると共に、識別した関連性に基づいてデータの更新に伴い更新されたクラスタとクラスタ統合条件を満たしたクラスタとを統合処理する
ことを特徴とする階層クラスタリング再構成方法。
【００６９】
［付記１２］
上記付記記載の階層クラスタリング再構成方法であって、
前記情報処理システムは、
新規ノードを追加する際に、既存のデータ集合に追加する新たなデータを前記更新ノードとして識別すると共に、更新前の階層型クラスタの各クラスタとの関連性を取得して、所属先となる全てのクラスタを決定し、
または、既存ノードを変更する際に、既存のデータ集合から更新するデータを前記更新ノードとして識別して該当ノードを変更すると共に、更新前の階層型クラスタの各クラスタとの関連性を取得して、所属先となる全てのクラスタを決定して関連付け、
または、既存ノードを削除する際に、既存のデータ集合から削除するデータを前記更新ノードとして識別して該当ノードを削除し、
必要に応じて、変更が加わったクラスタについて、クラスタ統合条件を満たすと判別した際に、該当クラスタと残りの各クラスタとの関連性を識別すると共に、識別した関連性に基づいてデータの更新に伴い更新されたクラスタとクラスタ統合条件を満たしたクラスタとを統合処理し、
既存ノードの追加、変更、統合の何れかの反映と共に、変更が加わったクラスタについて、クラスタ分割条件を満たした判別した際に、当該クラスタ内の各ノード間の関連性を取得すると共に、該関連性を反映させてノード群を２組に分割処理する
ことを特徴とする階層クラスタリング再構成方法。
【００７０】
［付記１３］
上記付記記載の階層クラスタリング再構成方法であって、
前記クラスタ統合条件として、該当クラスタ内のノード数が閾値以下になった、他のクラスタとの関連性を示す距離が閾値以下になった、或いはこれらを複数組み合わせた条件の何れかを用いる
ことを特徴とする階層クラスタリング再構成方法。
【００７１】
［付記１４］
上記付記記載の階層クラスタリング再構成方法であって、
前記クラスタ分割条件として、該当クラスタ内のノード数が閾値以上になった、クラスタ内のノード間の関連性を示す距離の最大値が閾値以上になった、或いはこれらを複数組み合わせた条件の何れかを用いる
ことを特徴とする階層クラスタリング再構成方法。
【００７２】
［付記１５］
上記付記記載の階層クラスタリング再構成方法であって、
前記情報処理システムは、カウンタを有してなり、
前記階層型クラスタの再構成処理を実行する回数若しくは実行した回数をカウントし、該カウント値が所定数を超えた際に、全データ集合への再クラスタリングを実行させる
ことを特徴とする階層クラスタリング再構成方法。
【００７３】
［付記１６］
上記付記記載の階層クラスタリング再構成方法であって、
前記情報処理システムは、カウンタを有してなり、
前記階層型クラスタの再構成処理を実行する回数若しくは実行した回数をカウントし、該カウント値が所定数を超えた際に、前記カウント開始後に発生した更新ノードに関連するクラスタに属する全データについて再クラスタリングを実行させる
ことを特徴とする階層クラスタリング再構成方法。
【００７４】
［付記１７］
情報処理システムの制御部を、
分類対象とするデータ群について階層的クラスタリングを実行して生成された階層型クラスタを更新対象として識別している環境で、前記データ群に新規に更新を受け付けて逐次的に、
前記階層型クラスタに更新内容のデータを更新ノードとして反映させると共に、前記階層型クラスタ内での変更が加わったクラスタについて識別処理して、識別結果に基づいて該クラスタ階層を分割もしくは維持もしくは他の階層との統合を判定処理し、判定結果に基づいた階層型クラスタに階層構造を再構成処理して記憶手段に出力する
データ更新手段、
として動作させることを特徴とするプログラム。
【００７５】
［付記１８］
上記付記記載のプログラムであって、
前記データ更新手段を、
前記階層型クラスタに前記更新ノードを反映させた後に、前記階層型クラスタ内での変更が加わったクラスタについて該クラスタ内のノード群の関連性と該クラスタと他のクラスタとの関連性とを識別処理して、該クラスタ階層の分割又は他の階層との統合の処理内容を決定する
ように動作させることを特徴とするプログラム。
【００７６】
［付記１９］
上記付記記載のプログラムであって、
前記データ更新手段を、既存ノード変更手段と、既存ノード削除手段と、クラスタ統合手段として動作させると共に、
前記既存ノード変更手段が、既存のデータ集合から更新するデータを前記更新ノードとして識別して該当ノードを変更すると共に、更新前の階層型クラスタの各クラスタとの関連性を取得して、所属先となる全てのクラスタを決定して関連付け、
前記既存ノード削除手段が、既存のデータ集合から削除するデータを前記更新ノードとして識別して該当ノードを削除し、
前記クラスタ統合手段が、前記既存ノード変更手段又は前記既存ノード削除手段による前記更新ノードの反映後に、変更が加わったクラスタについて、クラスタ統合条件を満たすと判別した際に、該当クラスタと残りの各クラスタとの関連性を識別すると共に、識別した関連性に基づいてデータの更新に伴い更新されたクラスタとクラスタ統合条件を満たしたクラスタとを統合処理する
ように動作させることを特徴とするプログラム。
【００７７】
［付記２０］
上記付記記載のプログラムであって、
前記データ更新手段を、新規ノード追加手段と、クラスタ分割手段として更に動作させると共に、
前記新規ノード追加手段が、既存のデータ集合に追加する新たなデータを前記更新ノードとして識別すると共に、更新前の階層型クラスタの各クラスタとの関連性を取得して、所属先となる全てのクラスタを決定し、
前記クラスタ分割手段が、前記新規ノード追加手段、前記既存ノード変更手段もしくは前記クラスタ統合手段の何れかによる前記更新ノードの反映後に、変更が加わったクラスタについて、クラスタ分割条件を満たした判別した際に、当該クラスタ内の各ノード間の関連性を取得すると共に、該関連性を反映させてノード群を２組に分割処理する
ように動作させることを特徴とするプログラム。
【００７８】
［付記２１］
上記付記記載のプログラムであって、
前記クラスタ統合条件として、該当クラスタ内のノード数が閾値以下になった、他のクラスタとの関連性を示す距離が閾値以下になった、或いはこれらを複数組み合わせた条件の何れかを用いる
ことを特徴とするプログラム。
【００７９】
［付記２２］
上記付記記載のプログラムであって、
前記クラスタ分割条件として、該当クラスタ内のノード数が閾値以上になった、クラスタ内のノード間の関連性を示す距離の最大値が閾値以上になった、或いはこれらを複数組み合わせた条件の何れかを用いる
ことを特徴とするプログラム。
【００８０】
［付記２３］
上記付記記載のプログラムであって、
前記データ更新手段を、
前記階層型クラスタの再構成処理を実行する回数若しくは実行した回数をカウントし、該カウント値が所定数を超えた際に、全データ集合への再クラスタリングを実行させる
ように動作させることを特徴とするプログラム。
【００８１】
［付記２４］
上記付記記載のプログラムであって、
前記データ更新手段を、
前記階層型クラスタの再構成処理を実行する回数若しくは実行した回数をカウントし、該カウント値が所定数を超えた際に、前記カウント開始後に発生した更新ノードに関連するクラスタに属する全データについて再クラスタリングを実行させる
ように動作させることを特徴とするプログラム。
【符号の説明】
【００８２】
１    階層クラスタリング装置（階層クラスタリングシステム）
２    データベース（記憶手段）
３    提示装置（提示手段）
１０  階層化データ分類部（階層化データ分類手段）
２０  データ更新部（データ更新手段）
２１  新規ノード追加手段
２２  既存ノード更新手段
２３  既存ノード削除手段
２４  クラスタ統合手段
２５  クラスタ分離手段
【図１】
2014174797.tif 000003
【図２】
2014174797.tif 000004
【図３】
2014174797.tif 000005
【図４】
2014174797.tif 000006
【図５】
2014174797.tif 000007
【図６】
2014174797.tif 000008
【図７】
2014174797.tif 000009
【図８】
2014174797.tif 000010
【図９】
2014174797.tif 000011
【図１０】
2014174797.tif 000012