(57)【要約】  【課題】  データマイニングによって得られる情報を効果的に提示するグラフィックス表示システムおよびその方法を提供する。  【解決手段】  階層型データにおける各ノードの属性を所定の集計条件に基づいて集計する集計処理部１００と、この集計処理部１００による集計結果に対して所定のフィルタリング条件に基づいてフィルタリング処理を行い、階層型データ中から表示対象ノードを選択するフィルタリング処理部２００と、このフィルタリング処理部２００にて選択された表示対象ノードを構成要素とし、階層型データの階層構造を反映させると共に、各ノードに対応するデータの属性を所定の視覚化要素で表現したグラフィックス・イメージを生成する視覚化処理部３００とを備える。  【選択図】  図２
2005085166.tif 000002
【特許請求の範囲】
【請求項１】
階層型データを、階層構造を視覚的に表現して図示するグラフィックス・イメージ生成装置において、
前記階層型データにおける各ノードの属性を所定の集計条件に基づいて集計する集計処理部と、
前記集計処理部による集計結果に対して所定のフィルタリング条件に基づいてフィルタリング処理を行い、前記階層型データ中から表示対象ノードを選択するフィルタリング処理部と、
前記フィルタリング処理部にて選択された前記表示対象ノードを構成要素とし、前記階層型データの階層構造を反映させたグラフィックス・イメージを生成する視覚化処理部と
を備えることを特徴とするグラフィックス・イメージ生成装置。
【請求項２】
前記集計処理部は、前記階層型データにおける所定のノードに対して、当該ノード自身の属性に対する集計結果である集計値を得ると共に、当該ノードの子孫ノードの属性に対する集計値を当該ノードの集計値に集約させた集約集計値を求めることを特徴とする請求項１に記載のグラフィックス・イメージ生成装置。
【請求項３】
前記フィルタリング処理部は、所定のフィルタリング条件に基づいて表示対象でないと判断したノードに対して、当該ノードの集計値を前記集約集計値に置き換えて、再度当該ノードを表示対象ノードとするか否かを判断することを特徴とする請求項２に記載のグラフィックス・イメージ生成装置。
【請求項４】
前記フィルタリング処理部は、前記集計処理部における集計条件に対する適応の度合に基づいて、前記階層型データの各ノードに対して前記集約集計値を用いた表示対象ノードとするか否かの判断を行う際の、各ノードへの着目順を決定することを特徴とする請求項３に記載のグラフィックス・イメージ生成装置。
【請求項５】
前記視覚化処理部は、前記フィルタリング処理部によるフィルタリング処理後の表示対象ノードに対して、前記集計処理部による集計結果に基づいて、当該ノードの属性を表す棒グラフを配置したグラフィックス・イメージを生成することを特徴とする請求項１に記載のグラフィックス・イメージ生成装置。
【請求項６】
前記視覚化処理部は、前記表示対象ノードに配置する前記棒グラフの形状を、底面部分を個々の前記表示対象ノードの表示形状に対応させ、高さ方向に向かって次第に断面積が大きくなる略錐体とすることを特徴とする請求項５に記載のグラフィックス・イメージ生成装置。
【請求項７】
前記視覚化処理部は、前記表示対象ノードを表現する所定の図形要素を、前記階層型データの階層構造を表現する入れ子状に配置したグラフィックス・イメージを生成することを特徴とする請求項１に記載のグラフィックス・イメージ生成装置。
【請求項８】
前記視覚化処理部は、以前に生成したグラフィックス・イメージをテンプレートとして前記表示対象ノードの配置を決定し、新規のグラフィックス・イメージを生成することを特徴とする請求項７に記載のグラフィックス・イメージ生成装置。
【請求項９】
データベースに蓄積されたデータ群を解析するデータ解析装置において、
階層構造を有する所定のカテゴリ体系にて分類されたデータの属性を所定の集計条件に基づいて集計する集計処理部と、
前記集計処理部による集計結果を用い、所定のフィルタリング条件に基づいて、前記カテゴリ体系に対するフィルタリング処理を行い、当該フィルタリング条件における有効なカテゴリを選択するフィルタリング処理部と、
前記フィルタリング処理部にて選択された前記有効なカテゴリを構成要素とし、当該有効なカテゴリに含まれるデータの属性を所定の視覚化要素で表現したグラフィックス・イメージを生成し表示出力する解析結果出力部と
を備えることを特徴とするデータ解析装置。
【請求項１０】
前記集計処理部は、前記カテゴリ体系における所定のカテゴリに対して、当該カテゴリのみに含まれたデータの属性に対する集計結果である当該カテゴリの集計値を得ると共に、当該カテゴリの下位カテゴリに含まれたデータの属性に対する集計値を当該カテゴリに集約させた集約集計値を求め、
前記フィルタリング処理部は、所定のフィルタリング条件に基づいて有効でないと判断したカテゴリに対して、当該カテゴリの集計値を前記集約集計値に置き換えて、再度当該カテゴリを有効なカテゴリとするか否かを判断することを特徴とする請求項９に記載のデータ解析装置。
【請求項１１】
前記視覚化処理部は、前記フィルタリング処理部によるフィルタリング処理後の前記有効なカテゴリに対して、前記集計処理部による集計結果に基づいて、当該有効なカテゴリに含まれるデータの属性を表す棒グラフを配置したグラフィックス・イメージを生成することを特徴とする請求項９に記載のデータ解析装置。
【請求項１２】
前記視覚化処理部にて表示出力された前記グラフィックス・イメージの視覚化要素に対する所定の入力操作を、当該視覚化要素に対応するデータが含まれるカテゴリを指定するイベントとして抽出するイベント抽出部をさらに備え、
前記フィルタリング処理部は、前記イベント抽出部にて抽出された所定のカテゴリの指定情報に基づいてフィルタリング処理を行うことを特徴とする請求項９に記載のデータ解析装置。
【請求項１３】
階層型データを、階層構造を視覚的に表現して図示するグラフィックス・イメージ生成方法において、
前記階層型データにおける各データの属性を所定の集計条件に基づいて集計し、所定の記憶手段に格納する第１のステップと、
集計の結果に対して所定のフィルタリング条件に基づいてフィルタリング処理を行い、前記階層型データ中から表示対象ノードを選択し、選択された表示対象ノードの情報を所定の記憶手段に格納する第２のステップと、
前記表示対象ノードを構成要素とし、前記階層型データの階層構造を反映させたグラフィックス・イメージを生成する第３のステップと
を含むことを特徴とするグラフィックス・イメージ生成方法。
【請求項１４】
前記第１のステップでは、前記階層型データにおける所定のノードに対して、当該ノード自身の属性に対する集計結果である集計値を得ると共に、当該ノードの子孫ノードの属性に対する集計値を当該ノードの集計値に集約させた集約集計値を求め、
前記第２のステップでは、所定のフィルタリング条件に基づいて表示対象でないと判断したノードに対して、当該ノードの集計値を前記集約集計値に置き換えて、再度当該ノードを表示対象ノードとするか否かを判断することを特徴とする請求項１３に記載のグラフィックス・イメージ生成方法。
【請求項１５】
データベースに蓄積されたデータ群を解析するデータ解析方法において、
階層構造を有する所定のカテゴリ体系にて分類されたデータの属性を所定の集計条件に基づいて集計し、所定の記憶手段に格納する第１のステップと、
集計の結果を用い、所定のフィルタリング条件に基づいて、前記カテゴリ体系に対するフィルタリング処理を行い、当該フィルタリング条件における有効なカテゴリを選択し、選択された当該有効なカテゴリの情報を所定の記憶手段に格納する第２のステップと、
前記有効なカテゴリを構成要素とし、当該有効なカテゴリに含まれるデータの属性を所定の視覚化要素で表現したグラフィックス・イメージを生成し表示出力する第３のステップと
を含むことを特徴とするデータ解析方法。
【請求項１６】
表示出力された前記グラフィックス・イメージの視覚化要素に対する所定の入力操作を、当該視覚化要素に対応するデータが含まれるカテゴリを指定するイベントとして抽出する第４のステップと、
抽出された前記カテゴリの指定情報に基づいてフィルタリング処理を行い、前記フィルタリング条件における有効なカテゴリを選択し、選択された当該有効なカテゴリの情報を所定の記憶手段に格納する第５のステップと、
前記有効なカテゴリを構成要素とし、当該有効なカテゴリに含まれるデータの属性を所定の視覚化要素で表現したグラフィックス・イメージを生成し表示出力する第６のステップと
をさらに含むことを特徴とする請求項１５に記載のデータ解析方法。
【請求項１７】
コンピュータを、
階層型データを、階層構造を視覚的に表現して図示するグラフィックス・イメージ生成装置において、
階層型データにおける各データの属性を所定の集計条件に基づいて集計する集計処理手段と、
前記集計処理手段による集計結果に対して所定のフィルタリング条件に基づいてフィルタリング処理を行い、前記階層型データ中から表示対象ノードを選択するフィルタリング処理手段と、
前記フィルタリング処理手段にて選択された前記表示対象ノードを構成要素とし、前記階層型データの階層構造を視覚的に表現したグラフィックス・イメージを生成する視覚化処理手段として
機能させることを特徴とするプログラム。
【請求項１８】
前記集計処理手段では、前記階層型データにおける所定のノードに対して、当該ノード自身の属性に対する集計結果である集計値を得ると共に、当該ノードの子孫ノードの属性に対する集計値を当該ノードの集計値に集約させた集約集計値を求め、
前記フィルタリング処理手段では、所定のフィルタリング条件に基づいて表示対象でないと判断したノードに対して、当該ノードの集計値を前記集約集計値に置き換えて、再度当該ノードを表示対象ノードとするか否かを判断することを特徴とする請求項１７に記載のプログラム。
【請求項１９】
前記フィルタリング処理手段では、前記集計処理手段における集計条件に対する適応の度合に基づいて、前記階層型データの各ノードに対して前記集約集計値を用いた表示対象ノードとするか否かの判断を行う際の、各ノードへの着目順を決定することを特徴とする請求項１８に記載のプログラム。
【請求項２０】
コンピュータを、
階層構造を有する所定のカテゴリ体系にて分類されたデータの属性を所定の集計条件に基づいて集計する集計処理手段と、
前記集計処理手段による集計結果を用い、所定のフィルタリング条件に基づいて、前記カテゴリ体系に対するフィルタリング処理を行い、当該フィルタリング条件における有効なカテゴリを選択するフィルタリング処理手段と、
前記フィルタリング処理手段にて選択された前記有効なカテゴリを構成要素とし、当該有効なカテゴリに含まれるデータの属性を所定の視覚化要素で表現したグラフィックス・イメージを生成し表示出力する視覚化処理手段として
機能させることを特徴とするプログラム。
【請求項２１】
前記コンピュータを、前記視覚化処理手段にて表示出力された前記グラフィックス・イメージの視覚化要素に対する所定の入力操作を、当該視覚化要素に対応するデータが含まれるカテゴリを指定するイベントとして抽出するイベント抽出手段として、さらに機能させ、
前記フィルタリング処理手段の機能として、前記イベント抽出手段にて抽出された所定のカテゴリの指定情報に基づいて、フィルタリング処理を行うことを特徴とする請求項２０に記載のプログラム。
【請求項２２】
請求項１７から請求項２１のいずれかに記載のプログラムを、コンピュータが読み取り可能に記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、階層型データのグラフィックス・イメージを生成するグラフィックス表示技術に関する。
【背景技術】
【０００２】
コンピュータを用いたデータベースシステムの普及に伴い、膨大なデータの中から所望の情報を抽出するデータマイニングシステムについても、従来から種々の提案がなされている。
例えば、論文等のドキュメントファイルを対象としたテキストマイニングシステムには、文書中に含まれるカテゴリ情報、単語、単語間の係り受け関係などを用いて、大量のドキュメントからそこに含まれる知見を発見するための機能を有するものがある（例えば、非特許文献１参照）。
【０００３】
例えば、米国立医療図書館では、１１００万件（２００２年９月現在）にも及ぶバイオメディカル論文を蓄積している。この組織では、MeSHTermと呼ばれるカテゴリ体系を定義し、各論文に対してどのカテゴリに属するかを付与されていて、検索等に用いることができる。１つの文書には、複数のカテゴリが付与されている。このカテゴリ体系は、階層構造を有しており、全てのノードを合わせると合計３８０００ノード（２００２年９月現在）にも及ぶ巨大な階層カテゴリである。
バイオメディカル論文を対象とする非特許文献１に記載されたテキストマイニングシステムIBM TAKMI for biomedical documents（略称：MedTAKMIシステム）では、このような階層構造を対象とした分析機能を実装しており、木構造のカテゴリ体系内で、１つのノード（カテゴリ）を指定することで、その子孫の全ノードのカテゴリを含む文書の総数を集計して分析を行うことができる。
【０００４】
また、複数のデータ要素が階層を持って整理されたこの種のデータ群（以下、階層型データと称す）をグラフィックス表示する技術も種々提案されている（例えば、非特許文献２〜５参照）。
非特許文献２に開示されたHyperbolic Tree法による従来技術は、双曲空間にツリー構造を配置することで、データの階層構造とデータ要素間のリンク構造の両方を表現する。
非特許文献３に開示されたTreemap法による従来技術は、階層型データが表示される画面空間を縦方向・横方向に交互に切り分け、切り分けられた領域を個々のデータ要素に対応づけることにより、データの階層構造を表現する。
非特許文献４、５に開示された従来のグラフィックス表示技術は、まず最下位階層を構成するデータのアイコンを長方形等の図形で囲み、次にその図形の集合を囲む図形を作成して上位階層を表現し、更にその上位階層の図形の集合を囲む図形を作成する、という処理を最上位階層まで反復することで、データを画面空間に配置する。
【０００５】
【非特許文献１】松澤裕史、長野徹、村上明子、竹内広宣、武田浩一、神田靖、「バイオメディカル文献データベースを対象とするテキストマイニングシステム MedTAKMI」、日本ソフトウェア科学会 データマイニングワークショップ、２００２年９月
【非特許文献２】Hao M. C., Hsu M., DayalU., and Krug A., Web-based Visualization of Large Hierarchical Graphs Using Invisible Links in a Hyperbolic Space, HP Laboratories Palo Alto, HPL-2000-2.
【非特許文献３】Ben Shneiderman、“Treemapsfor space-constrained visualization of hierarchies”、２００３年５月２１日、［平成１５年６月１９日検索］、インターネット＜URL : http://www.cs.umd.edu/hcil/treemap-history/index.shtml＞
【非特許文献４】伊藤、梶永、池端、「データ宝石箱：大規模階層型データのグラフィックスショーケース」、情報処理学会グラフィックスとＣＡＤ研究報告、2001-CG-104、2001
【非特許文献５】山口、伊藤、「データ宝石箱II〜位置情報テンプレートを用いた大規模階層型データのグラフィックスショーケース」、情報処理学会グラフィクスとＣＡＤ研究会、2002-CG-108、2002
【発明の開示】
【発明が解決しようとする課題】
【０００６】
上記のように、データマイニングシステムは、膨大なデータを解析して、かかるデータに含まれる種々の知見を得るための機能を有するが、対象とするデータベースが大規模であると、得られた情報をユーザに対してどのように提示するかが問題となる。
例えば、上述したテキストマイニングシステムIBM TAKMI for biomedical documentsで米国立医療図書館の論文に対してテキストマイニングを行う場合、米国立医療図書館が規定するカテゴリ体系は公開されているので、論文データベースを分析する研究者（分析者）は、調査対象とすべきカテゴリを大抵は把握している。分析者にとって、約４万個ものノードの中から知見を含むノードが無いかをしらみ潰しに調べたり、関連するノードを辿りながら全てのノードを調べたりすることは難しく、通常は、よく知っているカテゴリだけを分析対象とすることが多い。
【０００７】
しかしながら、データマイニングの観点から、他のカテゴリに注目すべき知見が含まれている場合には、これを提示することが望ましい。例えば、いくつかのカテゴリに関連する情報に関して、最初からよく知っている特定のカテゴリを調べてしまうと、その情報が関連する他のカテゴリには気づかないことがあり得る。このような場合、分析をどのノードから始めれば良いかを提示し、データベースのカテゴリ体系全体を分析者が俯瞰できるような機能を提示することが望ましい。
【０００８】
上述したグラフィックス表示技術を用いることによって、階層構造を持つデータ要素をユーザが俯瞰的に眺められるような出力が可能となるが、数千、数万に及ぶデータ全てをそのまま表示した場合、必ずしもユーザが見やすいものとは言えない。
非特許文献２に開示されたHyperbolic Tree法による従来技術は、放射状のツリー構造の周縁に最下層の個々のデータ要素が配置されるため、数千、数万といった数のデータ要素を表示することは困難である。
また、非特許文献３に開示されたTreemap法による従来技術も、比較的大規模な階層型データに向いた階層型データのグラフィックス表示手法であるが、数千、数万といった数のデータ要素を表示しようとすると、データ要素に対応づけられる最小単位の表示領域が小さくなりすぎて視認性が低下してしまう。
【０００９】
非特許文献４、５に開示された従来技術では、個々のデータ要素に対応する図形に、当該データの属性を表す棒グラフを表示する機能を備えている。この機能を用いると、複数のカテゴリに関係する情報を検索条件とした場合、いくつかのカテゴリ中の特定のデータ要素に対応する棒グラフが周囲から突出するなど、データ要素と検索条件である情報との関係の把握が容易となる。しかし、この場合も、やはり数千、数万ものデータに関して棒グラフを表示すると、個々の棒グラフが混雑してしまい、視認性が低下するという問題がある。
【００１０】
そこで本発明は、上記の課題に鑑み、データマイニングによって得られる情報を効果的に提示するグラフィックス表示システムおよびその方法を提供することを目的とする。
また本発明は、大規模な階層型データ全体を俯瞰的に概観することを可能としながら、個々のデータ要素や特定のカテゴリに含まれるデータの属性を表示する際の視認性を向上させることを、他の目的とする。
【課題を解決するための手段】
【００１１】
上記の目的を達成する本発明は、階層型データを、階層構造を視覚的に表現して図示する、次のように構成されたグラフィックス・イメージ生成装置として実現される。すなわち、このグラフィックス・イメージ生成装置は、階層型データにおける各ノードの属性を所定の集計条件に基づいて集計する集計処理部と、この集計処理部による集計結果に対して所定のフィルタリング条件に基づいてフィルタリング処理を行い、階層型データ中から表示対象ノードを選択するフィルタリング処理部と、このフィルタリング処理部にて選択された表示対象ノードを構成要素とし、階層型データの階層構造を反映させたグラフィックス・イメージを生成する視覚化処理部とを備えることを特徴とする。
【００１２】
より詳細には、この集計処理部は、階層型データにおける所定のノードに対して、ノード自身の属性に対する集計結果である集計値を得ると共に、かかるノードの子孫ノードの属性に対する集計値をかかるノードの集計値に集約させた集約集計値を求める。また、フィルタリング処理部は、所定のフィルタリング条件に基づいて表示対象でないと判断したノードに対して、かかるノードの集計値を集約集計値に置き換えて、再度かかるノードを表示対象ノードとするか否かを判断する。
またフィルタリング処理部は、集計処理部における集計条件に対する適応の度合に基づいて、階層型データの各ノードに対して集約集計値を用いた表示対象ノードとするか否かの判断を行う際の、各ノードへの着目順を決定する。
【００１３】
また、上記の目的を達成する本発明は、データベースに蓄積されたデータ群を解析する、次のように構成されたデータ解析装置としても実現される。このデータ解析装置は、階層構造を有する所定のカテゴリ体系にて分類されたデータの属性を所定の集計条件に基づいて集計する集計処理部と、この集計処理部による集計結果を用い、所定のフィルタリング条件に基づいて、カテゴリ体系に対するフィルタリング処理を行い、かかるフィルタリング条件における有効なカテゴリを選択するフィルタリング処理部と、このフィルタリング処理部にて選択された有効なカテゴリを構成要素とし、この有効なカテゴリに含まれるデータの属性を所定の視覚化要素で表現したグラフィックス・イメージを生成し表示出力する解析結果出力部とを備えることを特徴とする。
【００１４】
さらに詳細には、この集計処理部は、カテゴリ体系における所定のカテゴリに対して、かかるカテゴリのみに含まれたデータの属性に対する集計結果である集計値を得ると共に、かかるカテゴリの下位カテゴリに含まれたデータの属性に対する集計値を集約させた集約集計値を求める。また、フィルタリング処理部は、所定のフィルタリング条件に基づいて有効でないと判断したカテゴリに対して、かかるカテゴリの集計値を集約集計値に置き換えて、再度、有効なカテゴリとするか否かを判断する。
このデータ解析装置は、視覚化処理部にて表示出力されたグラフィックス・イメージの視覚化要素に対する所定の入力操作を、視覚化要素に対応するデータが含まれるカテゴリを指定するイベントとして抽出するイベント抽出部をさらに備える構成とすることができる。この場合、フィルタリング処理部は、このイベント抽出部にて抽出された所定のカテゴリの指定情報に基づいてフィルタリング処理を行う。
【００１５】
また本発明は、上述した、集計処理部による処理、フィルタリング処理部による処理、視覚化処理部による処理を各々ステップとするグラフィックス・イメージ生成方法、あるいは、集計処理部による処理、フィルタリング処理部による処理、解析結果出力部による処理を各々ステップとするデータ解析方法としても実現される。
さらに本発明は、コンピュータを制御して上述したグラフィックス・イメージ生成装置、あるいはデータ解析装置として機能させるプログラムとしても実現される。このプログラムは、磁気ディスクや光ディスク、半導体メモリ、その他の記録媒体に格納して配布したり、ネットワークを介して配信したりすることにより、提供することができる。
【発明の効果】
【００１６】
以上のように構成された本発明によれば、データ解析における階層型データのフィルタリングの技術と情報視覚化の技術とを組み合わせたことによって、大規模な階層型データ全体を俯瞰的に概観しながら、個々のデータ要素や特定のカテゴリの属性を高い視認性を持たせて表示するグラフィックス・イメージを生成することができる。
また、本発明によれば、与えられた集計条件やフィルタリング条件に基づいて行われたデータ解析の結果を適切に反映したグラフィックス・イメージを出力することにより、データマイニングによって得られる情報を効果的に提示することができる。
【発明を実施するための最良の形態】
【００１７】
以下、添付図面を参照して、本発明を実施するための最良の形態（以下、実施形態）について詳細に説明する。
まず本発明の概要を説明する。本発明は、コンピュータシステムを用いて、階層型データを解析し、解析結果を視覚的に表現したグラフィックス・イメージを生成する。グラフィックス・イメージの種類としては、階層型データを表現可能なものであれば、種々のものを用いることができるが、以下に説明する本実施形態では、階層を表す領域を入れ子状に組み合わせることによって階層構造を２次元的に表現する手法を用いることとする。
【００１８】
入れ子構造のグラフィックス・イメージを生成する手順は、次のようにする。まず、最下位の階層に位置するデータ要素をグラフィックス・イメージが生成される空間（ディスプレイ装置に表示される空間、以下、ディスプレイ空間と称す）上に配置し、次に、このデータ要素の集合を内包する領域を形成して１つ上の階層を表現する。また、このようにして得られた領域の集合を適切にディスプレイ空間上に配置し直し、この領域の集合を内包するさらに大きな領域を形成してさらに１つ上の階層を表現する。かかる処理を再帰的に繰り返し、階層型データの最上位の階層まで表現する。
すなわち本発明では、階層型データを下位階層から上位階層に向かって順に配置していくことにより、階層型データのグラフィックス・イメージを生成する。
【００１９】
図１は、本実施形態による階層型データのグラフィックス表示を行うグラフィックス・イメージ生成装置（あるいはデータ解析を行うデータ解析装置）としてのコンピュータシステムの構成を示す図である。
図１を参照すると、コンピュータシステム１０は、グラフィックス表示処理をプログラム制御により実行する処理装置（ＣＰＵ）１１と、処理装置１１を制御するプログラムを格納した主メモリ１２と、処理装置１１により生成された階層型データのグラフィックス・イメージを表示するためのビデオメモリ１３及びディスプレイ装置１４と、処理対象である階層型データやグラフィックス・イメージを生成するために用いられる各種のデータを格納した磁気ディスク装置等の記憶装置１５とを備える。
【００２０】
処理装置１１は、主メモリ１２に格納されたプログラムに制御されて、記憶装置１５から処理対象となる階層型データを読み出し、そのグラフィックス・イメージ（イメージデータ）を生成してビデオメモリ１３に格納する。そして、ビデオメモリ１３に格納されたグラフィックス・イメージがディスプレイ装置１４にて表示される。主メモリ１２は、処理装置１１によるグラフィックス・イメージの生成処理の過程で、後述するセルやクラスタを一時的に格納するスタックとしても用いられる。また反対に、主メモリ１２に格納されたプログラムやデータは、記憶装置１５に適宜退避することができる。
なお、図１には、本実施形態を実現するための構成のみが図示されている。実際には、図示の構成の他に、各種の命令やデータを入力するためのキーボードやマウスなどの入力装置、音声出力機構や各種の周辺機器、ネットワークに対するインターフェイスなどが設けられていることは言うまでもない。また、階層型データを含む各種のデータは、上記のように記憶装置１５から読み出すほか、ネットワークなどを介して外部から入力しても良い。
【００２１】
図２は、本実施形態によるグラフィックス・イメージ生成装置の機能構成を示す図である。
図２を参照すると、本実施形態のグラフィックス・イメージ生成装置は、階層型データを集計処理する集計処理部１００と、集計処理部１００の集計結果に基づいてフィルタリング処理を行うフィルタリング処理部２００と、グラフィックス・イメージを生成する視覚化処理部３００とを備える。
【００２２】
階層型データは、個々の実体データ（例えば、米国立医療図書館の論文データベースにおける各論文）と、階層構造を規定するカテゴリ体系（例えば、米国立医療図書館の論文データベースにおけるMeSHTerm）とに分けて把握することができるが、本実施形態では、カテゴリ体系をグラフィックス・イメージによる表示対象として扱う（以下、表示対象である階層型データとしてのカテゴリ体系を階層カテゴリと称す）。
図３は、階層カテゴリの例を示す図である。
図示のように、階層カテゴリは、ルートノードから分岐した階層構造を示す。各ノードに記入されている数字Ｘ／Ｙにおいて、Ｙ（分母）は当該ノードのカテゴリに属する全データの件数を示し、Ｘ（分子）は当該ノードのカテゴリに属するデータのうちで所定の集計条件を満たすデータの件数を示す。所定の集計条件で絞る前にＹ件であった適合データが集計条件で絞り込むことでＸ件となった場合、Ｘ／Ｙの比率が高いものほど、当該ノードのカテゴリと集計条件との相関が強いと言える（ただし、件数の少ないものはノイズと判断すべきである）。
【００２３】
図２に示すように、実体データ及び階層カテゴリは、データ格納部４００に格納されている。データ格納部４００は、上述したように、図１に示したコンピュータシステム１０の記憶装置１５にて実現しても良いし、ネットワークを介してアクセス可能な外部装置であっても良い。各実体データには、階層カテゴリにて示されるカテゴリ体系のどのカテゴリに属するかを示す情報が付与されているものとする。また、１つの実体データが複数のカテゴリに属する場合もある。
【００２４】
集計処理部１００は、例えば図１に示したコンピュータシステム１０の処理装置１１にて実現され、データ格納部４００から実体データとその階層カテゴリとを入力し、所定の集計条件に基づいて各カテゴリに含まれる実体データの属性に関する集計処理を行う。例えば、実体データが論文等のテキストファイルである場合には、所定の文字列を集計条件とすることにより、各カテゴリに属す実体データのうちで当該文字列を含むものを集計することができる。また、階層カテゴリの全件が集計される集計条件を指定することもできる。この場合、図３に示した階層カテゴリにおいて、Ｘ＝Ｙとなる。
本実施形態では、所定の集計条件が与えられた場合に、個々のカテゴリに関して当該集計条件を満たす実体データが集計されて各カテゴリの集計値とされると共に、集計された個々のカテゴリの下位に位置するカテゴリ（集計されたカテゴリに対応するノードの子孫ノード）における当該集計条件を満たす実体データの集計値を集約した値（以下、集約集計値）も算出される。以上のようにして得られた各ノードの属性である集計結果（集計値及び集約集計値）は、例えば図１の主メモリ１２や記憶装置１５に保持され、フィルタリング処理部２００に利用される。
【００２５】
フィルタリング処理部２００は、例えば図１に示したコンピュータシステム１０の処理装置１１にて実現され、処理対象である階層型データ（階層カテゴリ）に対して集計処理部１００による集計結果を用いてフィルタリング処理を行う。フィルタリング処理とは、階層型データの要素である各カテゴリの集計値に対して一定の閾値を設定し、その閾値を越えるカテゴリを当該フィルタリング条件における有効なカテゴリとして、グラフィックス・イメージの表示対象とする変換処理である。
上述したように、本実施形態では、階層型データの個々のノードに対して当該ノードに対応するカテゴリ自身の集計値が与えられると共に、当該ノードの子孫ノードの集計値を集約した集約集計値も与えられている。したがって、フィルタリング処理によって所定のノードがグラフィックス・イメージに表示されない場合であっても、その上位ノードが表示されるならば、当該所定のノードの属性を当該上位ノードの表示に反映させることが可能である。
【００２６】
階層型データのグラフィックス・イメージを生成する手法は、後述する視覚化処理部３００による手法を含め、種々考えられるが、個々のノードの属性を表現する手法として、各ノードの属性を表す棒グラフを表示することができる。すなわち、当該ノードを底面として棒グラフを立て、その高さや形状、色彩等でセルに対応するカテゴリのノードの属性を表現する（以下では、属性の表現手段として棒グラフの高さと色とを用いる場合を例として説明する）。例えば、米国立医療図書館の論文データベースの例では、棒グラフの高さで各カテゴリに含まれる文書ファイルの数を表し、色でIBM TAKMI for biomedical documentsの相対頻度を表すといったことができる。なお、相対頻度とは、絞り込まれた文書ファイルに対するキーワードの出現比率を全体の文書ファイル中での出現比率で除算した結果であり、どれだけ、そのキーワードが条件と強い相関を持つかを示す基準となる。
【００２７】
フィルタリング処理の実行に先立って、フィルタリング処理部２００は、まず集計処理部１００による集計結果に基づいて各カテゴリにおけるノードの属性を表現する棒グラフの高さと色とを決定する。また、フィルタリング処理におけるフィルタリング条件（属性と閾値）を入力しておく。グラフィックス・イメージを生成する際の表示パラメータとなるフィルタリング条件は、棒グラフの高さ（一定以上の高さのものを表示等）や色（特定の色のものを表示等）を特定しても良いし、集計値に対応する数値で指定しても良い。
図４は、フィルタリング処理部２００によるフィルタリング処理の流れを示すフローチャートである。
図４に示すように、フィルタリング処理部２００は、階層型データの全てのノードに対して、各ノード自身の属性の集計値を対象として、棒グラフの高さ及び色によって示される属性値が与えられたフィルタリング条件を越えているかどうかを判断し、各ノードの表示非表示を決定する（ステップ４０１）。
【００２８】
次に、フィルタリング処理部２００は、ステップ４０１で非表示とされたノードの属性値を、当該ノード自身の属性の集計値から子孫ノードの属性の集計値を含む集約集計値に置き換える（ステップ４０２）。そして、非表示となっている全ノードに対して、当該ノードからリーフ（末端、最下位ノード）までの全ての子孫ノードが非表示になっているかを調べる（ステップ４０３）。所定のノードに関して、そこから下位の全てのノードが非表示となっている場合、当該所定のノードにおける属性値（集約集計値）がフィルタリング条件を越えているかどうかを判断し、当該所定のノードに対する表示非表示を決定する（ステップ４０４）。
以上のようにして得られたフィルタリング処理の結果（表示対象ノードの情報）は、例えば図１の主メモリ１２や記憶装置１５に保持され、視覚化処理部３００に利用される。
【００２９】
以上説明したように、フィルタリング処理を介することにより、階層型データの各ノードに対して、所定の属性が所定の閾値を越える場合にのみグラフィックス・イメージに表示することが可能となる。そして、かかる属性は、表示されるノードの下位階層のノードにおける属性を、必要に応じて反映させたものとなる。すなわち、所定のカテゴリとその下位の複数のカテゴリに着目すると、所定の属性に関して集計値が低いためにフィルタリング処理によって所定のカテゴリ及びその下位のカテゴリの全てがフィルタリング条件の閾値を越えない場合であっても、それら全ての集計値を集約することでフィルタリング条件の閾値を超えるならば、所定のカテゴリはグラフィックス・イメージに表示されることとなる。
【００３０】
例えば、米国立医療図書館の論文データベース等におけるカテゴリ体系で、「筋肉痛」というカテゴリの下位に「脚の筋肉痛」、「腰の筋肉痛」等のカテゴリがある場合を考える。この場合、所定の集計条件に合致し、「脚の筋肉痛」、「腰の筋肉痛」等の下位カテゴリのそれぞれに属する論文の数がフィルタリング条件の閾値に達していなくても、上位の「筋肉痛」のカテゴリに含まれる論文（下位カテゴリに属する論文が全て加算されることとなる）の数がフィルタリング条件の閾値を越えるならば、「筋肉痛」というカテゴリがノード（セル）としてグラフィックス・イメージに表示されることとなる。
【００３１】
図５は、図３に示した階層カテゴリを対象として、フィルタリング処理の作用を説明する図である。
図５（Ａ）は、件数が３件以上でＸ／Ｙの比率が６０％以上のノードの属性を表示するというフィルタリング条件に基づいて、表示されるノードを示している。同図において、太枠で示した白抜きのノードは、このフィルタリング条件を満たすので、属性を示す棒グラフが表示される。また、白抜きのノードは、子孫ノードにフィルタリング条件を満たすノードが存在するため、上位階層としての表示のみが行われる。斜線を付したノードは、フィルタリング条件を満足しないので表示されない。
【００３２】
ここで、図中の破線で囲んだノードに着目する。この３つのノード５ａ、５ｂ、５ｃのうち、ノード５ａはノード５ｂ、５ｃの上位ノードであり、ノード５ｂ、５ｃのカテゴリは、ノード５ａのカテゴリに包含される。しかし、ノード５ｂ、５ｃにおける集計条件との相関を示す集計値は各ノードに記入されており、ノード５ａには、ノード５ｂ、５ｃに含まれないデータに関する集計値が記入されている。
これらのノードの値をこのまま評価すれば、確かに各ノード５ａ、５ｂ、５ｃはいずれもフィルタリング条件を満たしていない。しかし上記のように、ノード５ａは本来ノード５ｂ、５ｃの上位ノードであるので、ノード５ａに関して、ノード５ｂ、５ｃを加味して集計値を評価すべきである。
【００３３】
そこで上述したように、本実施形態では、階層構造の上位のノードに対して、当該ノード自身の集計値に加えて、その下位ノードの集計値を集約した集約集計値を与えておき、下位ノードが全て非表示となっている場合に、当該ノードの集約集計値がフィルタリング条件を越えているかどうかが判断される。
図５（Ｂ）は、図５（Ａ）の下位カテゴリにおいて、下位ノードを持つ全てのノードに集約集計値を付した状態を示している。各ノードの近傍に記述された数字（Ｐ／Ｑ）は、子ノードの集計値を集約した値であり、Ｑ（分母）は当該ノードのカテゴリに属する全データの件数を示し、Ｐ（分子）は当該ノードのカテゴリに属するデータのうちで所定の集計条件を満たすデータの件数を示す。この図で先のノード５ａに着目すると、集約集計値が５／８であり、件数が３件以上でＸ／Ｙの比率が６０％以上のノードの属性を表示するというフィルタリング条件を満足するので、このノード５ａに対して属性を示す棒グラフが表示されることとなる。
【００３４】
視覚化処理部３００は、例えば図１に示したコンピュータシステム１０の処理装置１１及び記憶装置１５にて実現され、データ格納部４００から階層カテゴリを入力し、集計処理部１００による集計結果およびフィルタリング処理部２００によるフィルタリング処理の結果に基づいてグラフィックス・イメージを生成する。すなわち、集計処理部１００およびフィルタリング処理部２００による階層型データに対するデータ解析の結果を、視覚的な表現で表示出力する解析結果出力手段である。データ解析の結果を、階層型データ全体を俯瞰するように表示しつつ、個々のノード（カテゴリ）の属性についても参照しやすい形で表現することにより、データマイニング等によって得られる情報を効果的に提示することが可能となる。
【００３５】
上述したように、本実施形態では、階層を表す領域を入れ子状に組み合わせる手法によって、階層型データ（階層カテゴリ）のグラフィックス・イメージを生成する。このグラフィックス・イメージにおいて、階層型データにおける個々のデータ要素（表示される最下層のノードに対応するカテゴリ）をセルと称し、同じ大きさの正方形で表現する。
また、当該データ要素に対する分類などを示す上位階層のノード（上位のカテゴリ）をクラスタと称し、セル及び下位階層のクラスタを内包する長方形で表現する。すなわち、このグラフィックス・イメージは、単一のもしくは多重に配置された長方形のクラスタと、クラスタ内に配置された正方形セルとで構成される。ただし、このグラフィックス・イメージを生成する段階では、このセル及びクラスタは、入れ子状に配列された単なる正方形及び長方形の図形データであるため同様に扱うことができる。したがって、以下の説明において、このセルとクラスタとを特に区別する必要がない場合は、ノードと総称して説明する。以下の説明では、本実施形態において種々の大きさを取り得る長方形のクラスタを配置する場合を主として説明するが、上述のように、セルとクラスタとは区別なく扱われるのであり、セルが同じ大きさに限定されない場合は同様の説明が成り立つことは言うまでもない。
【００３６】
図６は、視覚化処理部３００の機能構成を示す図である。
図６に示すように、視覚化処理部３００は、階層型データにおける各階層のノードに関して配置順を決定するソート部３１０と、ソート部３１０にて決定された順番にしたがって階層型データのノードを配置するノード配置部３２０と、ソート部３１０及びノード配置部３２０による階層型データのノードの配置を当該階層型データの下位階層から順に再帰的に実行させる配置制御部３３０と、棒グラフ生成部３４０と、テンプレート保持部３５０とを備える。
【００３７】
図６に示した構成において、ソート部３１０は、所定のクラスタを示す長方形内に当該クラスタの下位階層のクラスタまたはセルを配置する場合に、当該クラスタまたはセルの配置順を決定（ソート）する。
配置順は、テンプレート保持部３５０に格納されたテンプレートに基づいて決定される。ここで、テンプレートの概念について説明する。
図７は、テンプレートの概念を示す図である。
図７（Ａ）は、９個のノードを持つ１階層に対するテンプレートの例を示す。ノードの位置情報であるテンプレートは、大きさがノードを配置すべき領域（配置領域、この配置領域の詳細については後述）の大きさに一致しており、所定の座標（例えばｘ−ｙ座標）が設定されている。そして、この座標値により、配置領域内におけるノードを配置すべき位置を特定することができる。テンプレート作成時点では９個のノードを表す長方形の大きさは知らなくてもよい。また、テンプレート上で配置に粗密差が生じていても差し支えない。図７（Ｂ）は、テンプレートに基づいて各ノードに対応し所定の大きさを持つ９個の長方形を配置した結果を示す。各長方形は、テンプレートに記述された位置関係をできるだけ保持し、かつ互いに重なることなく、占有面積の拡大を抑えながら配置されていることが分かる。
【００３８】
本実施形態では、同一の階層型データに対して集計条件やフィルタリング条件を変えながら複数のグラフィックス・イメージを生成する場合、後述するノードの再配置により個々のノードや棒グラフを見やすくする操作を行う場合に、最初乃至直前に生成したグラフィックス・イメージ自身（以下、元イメージと称す）をテンプレートとして用いることができる。すなわち、元イメージに配置されている個々のセルの位置を座標化し、この座標を基準として、新規のグラフィックス・イメージを構成するノードを配置していく。これにより、集計条件やフィルタリング条件の異なるグラフィックス・イメージを生成した場合や、ノードの再配置を行った場合でも、対応するノードをできるだけ同じ位置に配置することができる。
【００３９】
さて、ソート部３１０は、まず、ノードを配置する配置領域（テンプレートと同じ大きさ）の４頂点の座標値を、（−１，−１）、（１，−１）、（１，１）、（−１，１）として正規化する。この状態を図８に示す。そして、所定の基準にしたがって、当該テンプレートの座標値にて配置位置が指定されているノードの配置順を決定する。配置順を決める基準は、テンプレートにて特定される各ノードの配置位置の意味等に応じて適宜設定することができるが、例えば、ｘ座標値の小さい順、正規化された座標値における原点に近い順などとすることができる。
【００４０】
テンプレートが存在しない場合、及びテンプレートにない（新たに追加された）ノードを配置する場合は、原則として面積の大きなものから順に配置するように決定される。本実施形態では、データ要素に対応する各セルは同じ大きさの正方形であるので、配置順は任意に決定することができるが、データ要素の内容をセルの大きさに反映させる表現手法を取る場合は、同様にセルの大きさに応じて配置順が決定される。クラスタまたはセルの配置順を示すソート結果は、主メモリ１２や処理装置１１内のレジスタに一時的に格納される。
【００４１】
ノード配置部３２０は、階層型データのノード（クラスタまたはセル）を、ソート部３１０によりソートされた順番にしたがって、ディスプレイ空間に配置する。ノードの配置位置は、次の判断基準に基づいて判断される。
［基準１］すでに配置されている長方形群とまったく重ならない位置。
［基準２］テンプレートに記述された参照位置との距離Ｄができるだけ小さい位置。
［基準３］当該長方形の配置による占有領域の拡大量Ｓができるだけ小さい位置。
このうち、［基準１］を必ず満たし、かつ［基準２］［基準３］をできるだけ満たす位置を探索する。本実施の形態では、ａＤ＋ｂＳの値が最小である位置（ａ、ｂはユーザにより定義される定数）を、［基準２］［基準３］を最も満足する位置であるとみなす。ａ、ｂを適宜に設定することにより、［基準２］と［基準３］のどちらを重視するかを制御することができる。
【００４２】
また、テンプレートが存在しない場合、本実施形態のノード配置部３２０は、ソート部３１０によりソートされた順番にしたがい、次の方針によって、ディスプレイ空間に長方形を配置する。
（１）ディスプレイ空間の中心から順に、既に配置されている長方形に隣り合うように配置する。
（２）既に配置されている長方形の隙間に配置できる場合は、その隙間に配置する。
本実施の形態では、（２）の方針において必要となる、長方形を配置できるような隙間を高速に探す処理を実現するために、長方形の中心点を結ぶ三角メッシュを用いた処理を実行する。この三角メッシュは、Delaunay条件を満たすものとする。
さらに、本実施形態では、階層型データのノードを下位階層から上位階層へ順次配置していくため、ノード配置部３２０が所定の階層のクラスタを配置する場合、当該クラスタの下位階層のクラスタまたはセルが既に配置されている。そこで、ノード配置部３２０は、所定のクラスタを配置する際に、当該クラスタを表す長方形とその内部に既に配置されている下位階層のクラスタまたはセルを表す長方形または正方形との相対的な位置関係を保存し、すなわちこれらの図形を合わせて１つの図形として扱い、配置を行う。
【００４３】
配置制御部３３０は、ソート部３１０及びノード配置部３２０により階層型データの階層ごとに行われるクラスタまたはセルの配置処理を、下位階層から上位階層へと再帰的に繰り返して実行させることにより、階層型データ全体のグラフィックス・イメージを生成する。生成されたグラフィックス・イメージは、図１に示したビデオメモリ１３に格納され、ディスプレイ装置１４にて表示される。
また、本実施形態では、フィルタリング処理部２００のフィルタリング処理によってグラフィックス・イメージに表示されるノードを制御することができるが、表示パラメータであるフィルタリング条件を変更することにより、表示されるノードを動的に変更することができる。配置制御部３３０は、フィルタリング処理部２００においてフィルタリング条件を変更してフィルタリング処理が行われた場合は、ソート部３１０及びノード配置部３２０を制御して、各ノードを再配置した上でグラフィックス・イメージを再生成する。
【００４４】
棒グラフ生成部３４０は、配置制御部３３０にて配置されたセル（最下位のノード）に対し、集計処理部１００による集計結果およびフィルタリング処理部２００によるフィルタリング処理の結果に基づき、当該セルに対応するカテゴリのノードの属性を表現する棒グラフを生成する。上述したように、棒グラフの高さや色といった表示属性と各カテゴリのノードの属性とが対応付けられる。この棒グラフは、グラフィックス・イメージの表示の際に対応するセル上に表示される。
また本実施形態では、フィルタリング処理部２００のフィルタリング処理により、グラフィックス・イメージの表示構成が動的に変更された場合、必要に応じて棒グラフを整形することができる。棒グラフの整形の具体的な内容については後述する。
【００４５】
テンプレート保持部３５０は、例えば図１に示したコンピュータシステム１０の記憶装置１５にて実現され、ノード配置部３２０によるノードの配置に際して参照されるテンプレートを保持している。本実施の形態では、上述したように任意の規則にしたがってテンプレートを作成することにより、データ要素の位置に意味を持たせたり、類似する意味を持つデータに対して類似する配置結果を得たりすることが可能となる。なお、以前に作成したグラフィックス・イメージをテンプレート保持部３５０に格納しておき、次のグラフィックス・イメージの作成時にテンプレートとして用いることができる。
【００４６】
次に、上記構成に基づく階層型データのグラフィックス・イメージの生成処理について説明する。
まず、三角メッシュを用いた長方形（クラスタ）の配置位置の探索について詳細に説明する。
本実施の形態では、既に幾つかの長方形が配置されている場合に、配置された長方形が疎である領域を検出し、その領域に次の長方形を置く、という処理を反復することで、小さな配置面積に長方形群を配置する。そこで、長方形が疎である領域を抽出するために、長方形を配置する配置領域に、既に配置された長方形の中心点を結ぶ三角メッシュを生成する。この三角メッシュにおいて大きな三角形要素が生成された領域では、長方形が疎である可能性が高いので、その領域に新しい長方形を配置することを試みる。三角形要素の大きさを判定する基準としては、三角形要素の外接円の半径、内接円の半径、３辺の長さの最大値などを用いることができる。以下では、外接円の半径を基準として三角形要素の大きさを判定する場合を例として説明する。
【００４７】
ところで、この配置領域は、配置される長方形（クラスタ）の上位階層のクラスタを表現する長方形となる領域（この意味での配置領域を図形領域と称す）である。したがって、初期的には、ディスプレイ空間の適当な位置に４個のダミー頂点を置いて長方形の領域を配置領域として設定し、その配置領域の４頂点ｖ1、ｖ2、ｖ3、ｖ4の座標値を、（−１，−１）、（１，−１）、（１，１）、（−１，１）とする。これに対角線を１本引くことで、２個の三角メッシュ要素から構成される三角メッシュを生成する。この時点では、まだ長方形が置かれていないので、長方形の配置領域を２つの三角形に分けるような三角メッシュが生成される。そして、長方形が配置されるごとに、当該長方形の中心を新たな頂点として追加しながら三角メッシュを細かくしていく。
また、初期状態では、既に配置されている長方形は存在しないので、最初に配置する長方形は配置領域における任意の位置に置くことができる。ただしこの場合、上述した（１）の方針にしたがって、長方形はダミー頂点で示された配置領域の中心に置かれることとする。
【００４８】
図９は、既に配置された長方形の中心点を連結する三角メッシュにおける所定の三角形要素の外接円を示す図である。
Delaunay条件を満たす三角メッシュにおいて、図９において破線で示した外接円の内部に他の三角形要素の頂点は存在しない。したがって、外接円の大きい三角形要素の周辺では、三角形要素の頂点の密度が小さいと推測できる。所定の領域において、三角形要素の頂点の密度が小さいことは、長方形の個数が少ないことを意味する。
【００４９】
図１０は、三角メッシュの三角形要素を隣接するダミー頂点の数で分類した様子を示す図である。
ここで、三角形要素にダミー頂点が隣接するとは、当該三角形要素の頂点がダミー頂点と一致していることを意味する。したがって、三角形要素に隣接するダミー頂点の数は０から３個の間である（ただし、ダミー頂点の数が３個（すなわち三角形要素の全ての頂点がダミー頂点）の場合とは、ダミー頂点で示された配置領域を対角線で二分する三角メッシュが生成されている場合であり、さらに細かい三角メッシュが生成されている図１０の例では、三角形要素に隣接するダミー頂点の数は最大で２個となっている）。これによれば、ダミー頂点は三角メッシュの最も外側に存在するので、隣接するダミー頂点の数の多い三角形要素は三角メッシュが生成された領域の外側に存在し、隣接するダミー頂点の数が少ない三角形要素ほど当該領域の内側に存在していることがわかる。したがって、できるだけ隣接するダミー頂点の数が少ない三角形要素の位置に長方形を配置することで、小さいスペースに長方形をまとめて配置することができ、配置領域の拡大を抑えることができる。
【００５０】
次に、三角メッシュの内部領域にノードを表す長方形（以下、単に長方形と記す）を１個ずつ順番に配置する。上述したように、本実施の形態では、長方形の配置位置を指定するテンプレートの座標値に基づいて長方形の配置順が決められる。図１１に示すように、長方形ｒ1、ｒ2がすでに配置されているとすると、この長方形ｒ1、ｒ2に対して隙間をあけずに、かつテンプレート座標値に近い位置に次の長方形を配置する。
本実施形態では、テンプレート上の正規化された座標値にできるだけ近い三角メッシュ要素から順に抽出し、その三角メッシュ要素の内部に複数個の候補位置を設定する。そして、この候補位置に対して長方形の配置を試みる。これを抽出されたいくつかの三角メッシュ要素について反復して、［基準１］を満たしかつａＤ＋ｂＳ値が最小である候補位置を特定し、その位置を長方形の配置場所に決定する。
【００５１】
図１２は、長方形の配置位置を決定するための三角メッシュ要素の抽出方法を説明する図である。
図１２に示すように、まず新しく配置する長方形のテンプレート上の座標値を内部に包括する三角メッシュ要素を特定する（図１２（Ａ）参照）。この三角メッシュ要素を出発点にして、隣接関係の幅優先探索によって三角メッシュ要素を抽出する（図１２（Ｂ）参照）。そして、この抽出順にしたがって長方形の候補位置を算出する。三角メッシュ要素をテンプレート座標値から近い順に処理している関係上、ａＤ値は処理が進むにつれて大きくなる傾向にある。そこで本実施の形態では、ａＤ値がすでに記録されているａＤ＋ｂＳ値の最小値を超えた時点で、反復処理を終了する。
【００５２】
図１３は、抽出された１個の三角メッシュ要素に長方形を配置する候補位置を求める方法を説明する図である。
図１３に示すように、長方形の配置候補位置を算出するために、まず三角メッシュ要素の頂点とその対辺を結ぶ線分を、一定のサンプリング間隔をおいて生成する。その線分上で、すでに配置された長方形と接する位置を、新しい長方形の中心点の候補位置とし、ここに長方形の配置を試みる。ある三角メッシュ要素の内部における候補位置がｍ個あるときに、本開示書では候補位置をｃ1〜ｃmと記述する。このとき、次のいずれかの処理を行う。
・長方形ｒiの中心点ｖi+4を候補位置ｃjに配置したとき、長方形ｒiがすでに配置された他の長方形と重なるようであれば、候補位置ｃjには長方形を配置しない。
・候補位置ｃjにおけるａＤ＋ｂＳの値を算出する。Ｓの値には、長方形領域の面積や、４辺の長さの総計などを用いる。算出したａＤ＋ｂＳの値が、長方形ｒiに対して算出されたすべての値の中で最小であれば、その値を（ａＤ＋ｂＳ）minとして記録する。それと同時に、候補位置ｃjを位置ｃminとして記録する。
以上の処理を、三角メッシュ要素ごとに反復する。そして、反復を終了した時点で記録された位置ｃminに、長方形の中心点ｖi+4を配置する。
【００５３】
テンプレートが存在しない場合、最初の長方形を任意の位置に配置した後、次のようにして他の長方形を配置していくことができる。
図１４は、長方形を配置する対象として選択された三角形要素に長方形を置く手法を説明する図である。
図１４に示す例は、破線で示した２個の長方形がすでに配置されており、かつ隣接するダミー頂点の数が１個であるような三角形要素を長方形の配置位置とした場合の処理を示す。この場合、選択された三角形要素の中心点と当該三角形要素のダミー頂点以外の頂点とを結ぶ線分（図１４（Ａ）の線分５０１または線分５０２）上に、新たに配置する長方形の中心点を置き、かつ当該新たに配置する長方形が既に配置されている長方形に隣接するように、配置する。すなわち図１４（Ｂ）に実線で示した２つの長方形のいずれかの位置に配置することとなる。
【００５４】
次に、長方形を配置するために配置領域を拡大する処理を説明する。
本実施の形態では、次の２つのケースにおいて、配置領域の４頂点ｖ1、ｖ2、ｖ3、ｖ4のいずれかを移動して、配置領域を拡大する。
１）上記の処理により決定した位置ｃminに配置した長方形ｒiが、４頂点ｖ1、ｖ2、ｖ3、ｖ4によって構成される配置領域をはみ出しているとき。
２）位置ｃminがまったく記録されないとき。言い換えれば［基準１］を満たす候補位置がまったく見つからなかったとき。このときは領域を拡大した後に、候補位置の算出処理からやり直す。
図１５は、上の２つのケースにおける配置領域の拡大方法を概略的に示す図である。それぞれ、配置領域の４頂点を適宜移動し、配置対象である長方形が配置領域内に治まるように、配置領域が拡大されている。配置領域を拡大した場合は、テンプレート上における三角メッシュの頂点座標値を再度正規化する。
【００５５】
図１６は、上記のように構成された本実施形態によるグラフィックス・イメージの生成処理の全体的な流れを説明するフローチャートである。
図１６を参照すると、まず処理対象の階層型データである階層カテゴリがデータ格納部４００から視覚化処理部３００に読み込まれ（ステップ１６０１）、各カテゴリのノードがディスプレイ空間に配置される（ステップ１６０２）。この時点で生成された初期的なグラフィックス・イメージは、視覚化処理部３００のテンプレート保持部３５０に保持される。
【００５６】
一方、集計処理部１００に所定の集計条件が入力されると（ステップ１６０３）、続いて階層カテゴリと階層カテゴリによって分類される実体データとがデータ格納部４００から集計処理部１００に読み込まれ、集計条件に基づいたデータ件数の集計が行われる（ステップ１６０４）。上述したように、各カテゴリのノードに対して、当該ノード自身の集計値と、その子孫ノードの集計値を集約した集約集計値とが算出されて付与される。集計結果は、例えば図１に示した主メモリ１２や記憶装置１５等の記憶手段に格納される。
なお、図１６では、ステップ１６０１、１６０２でノードを配置した後に、ステップ１６０３、１６０４で集計処理を行うように記載されているが、これらの処理は独立しているので、必ずしもこの順に限らず、集計処理を先に行っても良いし、２つの処理を並列に行っても良い。
【００５７】
次に、集計処理部１００の集計結果と階層カテゴリとがフィルタリング処理部２００に入力され、フィルタリング条件（表示パラメータ）を用いたフィルタリング処理が行われて、表示対象ノードが決定される（ステップ１６０５）。フィルタリング処理の内容は、図４を参照して説明したとおりである。
【００５８】
次に、フィルタリング処理部２００によるフィルタリング処理の結果に基づいて、視覚化処理部３００により、まず階層カテゴリの各ノードに対して当該ノード自身の属性を表現する棒グラフの高さと色とが決定される（ステップ１６０６）。そして、ステップ１６０２で生成されたグラフィックス・イメージにおける各表示対象ノード上に棒グラフが配置される（ステップ１６０７）。このとき、フィルタリング処理の結果に応じて、必要ならばノードの再配置や棒グラフの整形が行われる。
棒グラフが配置された後、生成されたグラフィックス・イメージは、ビデオメモリ１３に格納され、ディスプレイ装置１４に表示出力される（ステップ１６０８）。
【００５９】
ユーザは、ディスプレイ装置１４にて表示されたグラフィックス・イメージを参照し、必要ならばフィルタリング条件（表示パラメータ）を様々に変更してグラフィックス・イメージを再生成させる操作（ステップ１６０５〜１６０８）を繰り返すことにより、所望の（見やすい）グラフィックス・イメージを得ることができる。
本実施形態の視覚化処理部３００は、上述したように、テンプレートを用いてノードの配置位置をある程度制限してグラフィックス・イメージを生成することができる。そのため、フィルタリング条件を変更しながらグラフィックス・イメージの生成を繰り返す場合も、以前に生成した同一の階層カテゴリに対するグラフィックス・イメージをテンプレートとして用いることにより、対応するノードが概ね同じ位置にあるグラフィックス・イメージを生成することができる。
【００６０】
図１７は、このフィルタリング処理による階層型データにおける表示対象ノードの変化と、視覚化の結果（グラフィックス・イメージ）の変化とを対応付けて示す図である。なお、図１７において、グラフィックス・イメージは、棒グラフを立体的に表示するため、ディスプレイ空間を斜め方向の視点から見た状態で表示されている。
図１７に示す階層型データは、２階層からなり、２つの上位ノードのうち一方には４つの下位ノードが存在し、他方には２つの下位ノードが存在する。図１７（Ａ）は、フィルタリング処理前もしくは全ての下位ノードの属性がフィルタリング条件を満足した状態を示しており、６つの下位ノード全てが表示対象ノードとなっている。したがって、グラフィックス・イメージでは、上位ノードを表す２つのクラスタ内に、それぞれ下位ノードに対応するセルが配置され、全部で６つの棒グラフが表示されている。
図１７（Ｂ）は、フィルタリング処理が行われた結果、図示の階層型データの左半分に関して、上位ノードが表示対象ノードとなった状態を示している。したがって、グラフィックス・イメージでは、図１７（Ａ）で４つの棒グラフが表示されていたクラスタに、当該クラスタに対応する上位ノードの属性（集約集計値）を表現する棒グラフが表示されている。
図１７（Ｃ）は、フィルタリング処理が行われた結果、全ての下位ノードの属性がフィルタリング条件を満足せず、２つの上位ノードが表示対象ノードとなった状態を示している。したがって、グラフィックス・イメージでは、図１７（Ａ）で上位ノードを表した２つのクラスタに、それぞれ対応する上位ノードの属性（集約集計値）を表現する棒グラフが表示されている。
【００６１】
また、図１６に示した処理は、１つの集計条件を満たすデータについて、フィルタリング処理を行ってグラフィックス・イメージを生成する処理の流れについて示しているが、同じ階層カテゴリに対して、様々な集計条件を入力してグラフィックス・イメージを生成する操作を繰り返すことにより、新たな知見を得るといった利用も可能である。集計条件を変えることによって、たとえフィルタリング条件を固定したとしても、生成されるグラフィックス・イメージが大きく変わることは言うまでもない。
【００６２】
このように、フィルタリング処理を行うことによって、大規模なデータベースのグラフィックス・イメージを表示する場合にも、適宜下位のカテゴリを間引いて、かつ間引いた下位カテゴリの属性を失わず上位カテゴリに反映させて、全体を俯瞰しやすい形で表示することが可能となる。
【００６３】
さて、データマイニングなどの分析結果は、視覚的に得られた特徴量からだけ知見を得るものではなく、表示された点、線、棒などの視覚化要素をマウスクリックしてノードに該当する実体データを取得する、ラベルを表示させるなどの対話的な操作が非常に有益であり、重要である。このような拡張的な機能を付与する場合には、フィルタリング処理を行って表示される要素を削減するだけでなく、グラフィックス・イメージを適宜整形して、全体を俯瞰しやすくすることや、注目すべき視覚的要素をクリックしやすくすることが効果的である。
【００６４】
そこで、本実施形態で生成されるグラフィックス・イメージを用いてＧＵＩ（Graphical User Interface）を提供することを考える。
ＧＵＩの機能として、グラフィックス・イメージに表示された棒グラフや各ノード（セル及びクラスタ）を示す長方形をクリックすることにより、対応するノードを指定する機能が提供されるものとする。この機能は、例えば図１８に示すように、グラフィックス・イメージに表示された点、線、棒などの視覚化要素がマウスクリックされたことをイベントとして抽出するイベント抽出部５００を、図２に示した本実施形態のグラフィックス・イメージ生成装置に付加することで実現される。このイベント抽出部５００は、例えば、図１に示したコンピュータシステム１０の処理装置１１にて実現することができる。
また、このＧＵＩ機能を用いた操作として、所定のノードを指定し、指定ノードよりも集計値が高いノードを表示対象ノードとするといった操作が実現されるものとする。
【００６５】
このＧＵＩを用いた操作を実現するために、前処理として、フィルタリング処理により表示対象ノードを選択する際のノードに着目する順番を決定する。具体的には、例えば次のようにしてノードへの着目順を決定することができる。
まず、フィルタリング条件として集計値に対する閾値を仮定し、かかる閾値でフィルタリング処理を行った場合に下位ノードの集計値が集約されることとなる上位ノードを探索する。この探索を、閾値を低い値から高い値へ順次上げながら繰り返す。これにより、探索されたノードに対し、探索された順に低い順番を付与する。すなわち、最初に探索されたノードが最下位で、最後に探索されたノードが１位であり、これは集計処理部１００における集計条件に対する各ノードの適応の度合を示すと言える。そして順位をつけられた親ノードに対して、当該親ノード自身の集計値と、集約集計値を記録する。
これにより、各ノードに関して、フィルタリング処理によって表示対象ノードが探索される際の順番が決定された。したがって、所定のフィルタリング条件が与えられれば、この順番に従って、各ノードが当該フィルタリング条件を満足するか否かが判断され、表示対象とするか否かが決定されることとなる。
【００６６】
以上の前処理が行われた階層型データに関してグラフィックス・イメージが生成され、例えば図１に示すディスプレイ装置１４に表示されたものとする。ユーザが、表示されたグラフィックス・イメージを参照し、所定のノードの長方形または棒グラフをマウスクリックすると、イベント抽出部５００が、このマウスクリックを、クリックされた長方形や棒グラフに対応するノードを指定するイベントとして抽出し、フィルタリング処理部２００に通知する。フィルタリング処理部２００は、イベント抽出部５００から所定のノードに対する指定情報の通知を受け取ると、階層型データのルートノードから下位ノードへ向かって、上記の前処理で決定された順番でノードを探索し、マウスクリックによって指定されたノードまでを表示対象ノードとする。そして、視覚化処理部３００により、新たな表示対象ノードを要素とするグラフィックス・イメージの生成が行われる。
以上のようにして、グラフィックス・イメージの所定のノードがマウスクリックされた場合に、ノードよりも集計値が高いノードを表示対象ノードとするグラフィックス・イメージを再生成するというＧＵＩ操作が実現される。
【００６７】
また、グラフィックス・イメージの長方形や棒グラフをマウスクリックすることによって、クリックされた長方形や棒グラフに対応するノードが指定されるので、階層カテゴリにおける指定されたノードに該当する実体データ（例えば、文書ファイル）をデータ格納部４００から読み出すといったＧＵＩ操作を実現することも容易である。
さらに、ＧＵＩ操作ではないが、上述した前処理によって表示対象ノードを探索する際の探索順を決定しておけば、例えば、集計値の上位ｘ個分のノードを表示するといったフィルタリング条件を与えることにより、階層型データのルートノードから下位ノードへ向かって、上記の前処理で決定された順番でノードを探索し、指定された個数に達した時点で探索を終了し、探索されたノードを表示対象ノードとしてグラフィックス・イメージを生成するといった操作も可能である。
【００６８】
本実施形態によるグラフィックス・イメージの生成処理では、上述したように、階層型データのフィルタリングの技術と情報視覚化の技術とを組み合わせたことによって、生成されたグラフィックス・イメージの表示上の過密さが解消され、重要度の低いデータに目を奪われることなく、重要度の高いデータだけに着目することが容易となる。しかしながら、フィルタリング処理により重要度の低いノードの表示を削除しただけでは、大規模なデータの全体を俯瞰するためにズームアウトした表示結果では、各ノードにおける棒グラフの表示が細くなってしまい、色や高さを識別しにくい、クリックしにくい、等の不具合が残る。
【００６９】
図１９は所定の階層カテゴリを対象データとして生成されたグラフィックス・イメージの例を示す図、図２０は図１９と同一の階層カテゴリを対象データとして所定のフィルタリング処理を実行した上で生成されたグラフィックス・イメージの例を示す図である。なお、これらの図において、グラフィックス・イメージは、棒グラフを立体的に表示するため、ディスプレイ空間を斜め方向の視点から見た状態で表示されている。
両図を比較すると、図２０の方が表示ノードが少なく、画面表示上の過密さが解消されて見やすい画像となっている。しかし、個々のノード上に表示された棒グラフは図１９と同様に細いままであり、必ずしも棒グラフによって表現されるノードの属性を判別しやすいとは言えない。
【００７０】
そこで、フィルタリング処理により重要度の低いノードが非表示となって全体に疎となったグラフィックス・イメージに対して、所定の変換を行うことにより、棒グラフの色や高さや位置を認識しやすくすることを考える。そのための手法として、本実施形態では、棒グラフの形状を変形する手法（手法１）と、表示ノード数に合わせてノードを再配置する手法（手法２）とを提案する。
【００７１】
手法１：棒グラフの整形による手法
棒グラフを見やすくする第１の手法では、各棒グラフを高さ方向に向かって次第に断面積が大きくなる逆ピラミッド型の四角錐（元の棒グラフが四角柱である場合）で表現する。棒グラフの頂上部分を太く表示することで、ユーザが視認しやすい表現が実現されると共に、底面部分を細く（ノードに対応する大きさで）表示することで、個々のノードの階層構造上の位置が理解しやすくなっている。
図２１は、図２０のグラフィックス・イメージにおける各ノード上に表示された棒グラフを整形した様子を示す図である。
図２１と図２０とを比較すると、棒グラフを四角錐で表現したことにより、各棒グラフの色や高さが認識しやすくなっている。また、このグラフィックス・イメージを用いてＧＵＩを提供する場合にも、棒グラフをマウスクリックして対応するノードを指定する操作が容易になる。
なお、ここでは棒グラフを四角錐で表現するとしたが、元の棒グラフの断面形状に応じて、円錐、三角錐等の形状（錐体）が適宜用いられることは言うまでもない。
【００７２】
手法２：ノードの再配置による手法
棒グラフを見やすくする第２の手法では、表示対象ノードを、隙間を詰めて再配置することにより、グラフィックス・イメージのサイズ（ルートノードに対応する長方形のサイズ）を縮小する。そして、ノードが再配置されたグラフィックス・イメージをズームインして表示することにより、個々のノードの表示サイズを相対的に拡大する。各ノードの表示サイズが大きくなったことにより、棒グラフも太く表示されることとなり、ユーザが視認しやすい表現が実現される。
図２２は、所定の階層型データに関して生成されたグラフィックス・イメージの例を示す図である。
図２２（Ａ）は、フィルタリング処理を行わずにグラフィックス・イメージを生成した状態であり、図２２（Ｂ）は、所定のフィルタリング処理を実行した上でグラフィックス・イメージを生成した状態である。この２図を比較すると、図２２（Ｂ）では、表示ノードが減ったことによって、個々のノードの属性を吟味しやすくなっている。しかし、このままでは、ノード間の隙間が大きいため、画面に無駄な（全く情報を含まない）領域が多い。また、データ規模がもっと大きい場合には、個々のノードの表示サイズが小さくなり（棒グラフが細くなり）、属性を吟味しにくくなることが想定される。そこで、図２２（Ｃ）に示すように、図２２（Ｂ）の表示ノードを再配置して隙間を詰め、改めてグラフィックス・イメージを生成することにより、画面の無駄な領域を減らすと共に、各ノードの表示サイズを拡大する。これにより、各棒グラフの色や高さが一層認識しやすくなる。また、グラフィックス・イメージを用いてＧＵＩを提供する場合にも、棒グラフをマウスクリックして対応するノードを指定する操作が容易になる。
なお、このようなノードの再配置を行う場合、生成されたグラフィックス・イメージを吟味するために、再配置前後で各ノードの相対位置が大きく変わらないようにすることが重要である。本実施形態では、視覚化処理部３００において、テンプレートを用いたグラフィックス・イメージの生成が行われるので、再配置前のグラフィックス・イメージをテンプレートとして用いて再配置後のグラフィックス・イメージを生成することにより、この要求を満たすことができる。
【００７３】
なお、上述した本実施形態では、生成されたグラフィックス・イメージをビデオメモリ１３に格納した後、ディスプレイ装置１４にて表示することとしているが、ビデオメモリ１３に格納されたグラフィックス・イメージのデータをＣＡＤ（Computer Aided Design）システムなどで利用することもできる。
また、本実施形態では、視覚化処理部３００が、階層を表す領域を入れ子状に組み合わせることによって階層構造を表現したグラフィックス・イメージを生成することとしたが、本実施形態による集計処理及びフィルタリング処理は、Hyperbolic Tree法やTreemap法など、階層型データを描画可能な種々のグラフィックス・イメージを生成する場合にも有効である。
【図面の簡単な説明】
【００７４】
【図１】本実施形態による階層型データのグラフィックス表示を行うグラフィックス・イメージ生成装置としてのコンピュータシステムの構成を示す図である。
【図２】本実施形態によるグラフィックス・イメージ生成装置の機能構成を示す図である。
【図３】本実施形態の処理対象である階層カテゴリの例を示す図である。
【図４】本実施形態のフィルタリング処理部によるフィルタリング処理の流れを示すフローチャートである。
【図５（Ａ）】図３に示した階層カテゴリを対象として、フィルタリング処理の作用を説明する図であり、所定のフィルタリング条件の下に表示対象ノードを選択した様子を示す図である。
【図５（Ｂ）】図３に示した階層カテゴリを対象として、フィルタリング処理の作用を説明する図であり、集約集計条件に基づいて表示対象ノードを選択し直した様子を示す図である。
【図６】本実施形態の視覚化処理部の機能構成を示す図である。
【図７】本実施形態によるグラフィックス・イメージの生成に用いられるテンプレートの概念を示す図である。
【図８】テンプレートに基づき配置領域の４頂点の座標値を正規化した状態を示す図である。
【図９】グラフィックス・イメージのノードを表す長方形の配置に用いられる三角メッシュの三角形要素の外接円を示す図である。
【図１０】三角メッシュの三角形要素を隣接するダミー頂点の数で分類した様子を示す図である。
【図１１】テンプレートを用いた長方形の配置方法を説明する図である。
【図１２】長方形の配置位置を決定するための三角メッシュ要素の抽出方法を説明する図である。
【図１３】抽出された１個の三角メッシュ要素に長方形を配置する候補位置を求める方法を説明する図である。
【図１４】長方形を配置する対象として選択された三角形要素に長方形を置く手法を説明する図である。
【図１５】長方形を配置するために配置領域を拡大する処理を説明する図である。
【図１６】本実施形態によるグラフィックス・イメージの生成処理の全体的な流れを説明するフローチャートである。
【図１７】本実施形態のフィルタリング処理による階層型データにおける表示対象ノードの変化と、視覚化結果の変化とを対応付けて示す図である。
【図１８】生成されたグラフィックス・イメージを用いてＧＵＩを提供可能とするグラフィックス・イメージ生成装置の機能構成を示す図である。
【図１９】本実施形態により所定の階層カテゴリを対象データとして生成されたグラフィックス・イメージの例を示す図である。
【図２０】図１９と同一の階層カテゴリを対象データとして所定のフィルタリング処理を実行した上で生成されたグラフィックス・イメージの例を示す図である。
【図２１】図２０のグラフィックス・イメージにおける各ノード上に表示された棒グラフを整形した様子を示す図である。
【図２２】所定の階層型データに関して生成されたグラフィックス・イメージに対してフィルタリング処理を行い、ノードの再配置を行った例を示す図である。
【符号の説明】
【００７５】
１０…コンピュータシステム、１１…処理装置（ＣＰＵ）、１２…主メモリ、１３…ビデオメモリ、１４…ディスプレイ装置、１５…記憶装置、１００…集計処理部、２００…フィルタリング処理部、３００…視覚化処理部、３１０…ソート部、３２０…ノード配置部、３３０…配置制御部、３４０…棒グラフ生成部、３５０…テンプレート保持部、４００…データ格納部
【図１】
2005085166.tif 000003
【図２】
2005085166.tif 000004
【図３】
2005085166.tif 000005
【図４】
2005085166.tif 000006
【図５（Ａ）】
2005085166.tif 000007
【図５（Ｂ）】
2005085166.tif 000008
【図６】
2005085166.tif 000009
【図７】
2005085166.tif 000010
【図８】
2005085166.tif 000011
【図９】
2005085166.tif 000012
【図１０】
2005085166.tif 000013
【図１１】
2005085166.tif 000014
【図１２】
2005085166.tif 000015
【図１３】
2005085166.tif 000016
【図１４】
2005085166.tif 000017
【図１５】
2005085166.tif 000018
【図１６】
2005085166.tif 000019
【図１７】
2005085166.tif 000020
【図１８】
2005085166.tif 000021
【図１９】
2005085166.tif 000022
【図２０】
2005085166.tif 000023
【図２１】
2005085166.tif 000024
【図２２】
2005085166.tif 000025