(57)【要約】【課題】データがより効果的に視覚化されるようにカテゴリ属性を順序付けする技法を提供する。【解決手段】本発明の一実施形態によれば、順序付けアルゴリズムは、（ａ）離散順序付け問題を連続最適化問題に変換するステップと、（ｂ）連続最適化問題を解くステップと、（ｃ）最も近い離散解に最適な連続解をマッピングするステップとを含む。【選択図】図３
2004532453.tif 000002
【特許請求の範囲】
【請求項１】
データ処理システム中においてデータ・セットに関連する１つまたは複数の属性のカテゴリ値を順序付けするコンピュータに基づく方法であって、
前記データ・セットに関連する前記１つまたは複数の属性の前記カテゴリ値を取得するステップと、
前記データ・セットに関連する前記１つまたは複数の属性の前記カテゴリ値を順序付けするタスクを連続最適化順序付け問題として形成するステップと、
前記連続最適化順序付け問題に対する少なくとも１つの連続順序付け解を計算するステップと、
前記計算された連続順序付け解の少なくとも一部分をデータ視覚化システムに従って使用できるようにするステップと
を含む方法。
【請求項２】
前記計算された連続順序付け解を連続空間から離散空間にマッピングするステップをさらに含む請求項１に記載の方法。
【請求項３】
前記カテゴリ値を順序付けするタスクを連続最適化順序付け問題として形成する前記ステップが、前記１つまたは複数の前記属性のカテゴリ値に基づいて類似度行列を計算するステップを含む、請求項１に記載の方法。
【請求項４】
前記類似度行列が１つまたは複数のマルチ集合演算に基づく、請求項３に記載の方法。
【請求項５】
前記１つまたは複数のマルチ集合演算が２つのタイプの類似度測定値を計算することを含み、第１のタイプが同じ属性からの２つのカテゴリ値の間で計算される類似度であり、第２のタイプが異なる属性からの２つのカテゴリ値の間で計算される類似度である、請求項４に記載の方法。
【請求項６】
前記カテゴリ値を順序付けするタスクを連続最適化順序付け問題として形成する前記ステップが、前記類似度行列からラプラス行列を計算するステップをさらに含む請求項３に記載の方法。
【請求項７】
前記連続最適化順序付け問題に対する少なくとも１つの連続順序付け解を計算する前記ステップが、前記ラプラス行列の最小の正の固有値を見つけるステップをさらに含む、請求項６に記載の方法。
【請求項８】
前記連続最適化順序付け問題に対する少なくとも１つの連続順序付け解を計算する前記ステップが、前記ラプラス行列の前記最小の正の固有値から対応する最適な固有ベクトルを得るステップをさらに含む、請求項７に記載の方法。
【請求項９】
前記データ視覚化システムに従って前記解を使用できるようにする前に、前記最適な固有ベクトルに関連した対応する値に応じて前記カテゴリ値を順序付けするステップをさらに含む、請求項８に記載の方法。
【請求項１０】
前記カテゴリ値が複数の属性に関連し、前記カテゴリ値を順序付けするタスクを連続最適化順序付け問題として形成する前に、前記複数の属性に関連する前記カテゴリ値をオブジェクトの集合にマッピングして前記形成するステップおよび計算するステップが前記オブジェクトの集合に関して実施されるようにするステップをさらに含む、請求項１に記載の方法。
【請求項１１】
前記取得するステップ、形成するステップおよび計算するステップが、前記データ視覚化システムの前処理操作に関連して実施される、請求項１に記載の方法。
【請求項１２】
前記取得するステップ、形成するステップ、および計算するステップが前記データ視覚化システムのデータ管理モジュールに関連して実施される、請求項１に記載の方法。
【請求項１３】
前記取得するステップ、形成するステップ、および計算するステップが前記データ視覚化システムのデータ・ビューア・モジュールに関連して実施される、請求項１に記載の方法。
【請求項１４】
データ処理システム中においてデータ・セットに関連する１つまたは複数の属性のカテゴリ値を順序付けするコンピュータに基づく方法であって、
前記データ・セットに関連する前記１つまたは複数の属性の前記カテゴリ値を取得するステップと、
各頂点が順序付けされる前記カテゴリ値であり一辺の重みが連結された頂点の類似度を表す元のグラフ構造として前記カテゴリ値をモデル化するステップと、
１つまたは複数のより粗いグラフ構造からなる階層的シーケンスによって前記元のグラフ構造を近似するステップであって、同様に局所的な構造を有する各頂点がより粗いグラフ構造における１つの頂点にマージされるステップと、
連続最適化順序付け操作に従って最も粗いグラフ構造を順序付けするステップと、
前記最も粗いグラフ構造の前記順序付けを前記元のグラフ構造まで逆伝播するステップと、
前記元のグラフ構造に関連する前記伝播された順序付けの少なくとも一部分をデータ視覚化システムに従って使用できるようにするステップと
を含む方法。
【請求項１５】
データ・セットに関連する１つまたは複数の属性のカテゴリ値を順序付けするデータ処理装置であって、
（ｉ）前記データ・セットに関連する前記１つまたは複数の属性の前記カテゴリ値を取得し、（ｉｉ）前記データ・セットに関連する前記１つまたは複数の属性の前記カテゴリ値を順序付けするタスクを連続最適化順序付け問題として形成し、（ｉｉｉ）前記連続最適化順序付け問題に対する少なくとも１つの連続順序付け解を計算し、（ｉｖ）前記計算された連続順序付け解の少なくとも一部分をデータ視覚化システムに従って使用できるように動作する少なくとも１つのプロセッサ
を含む装置。
【請求項１６】
前記プロセッサがさらに、前記計算された連続順序付け解を連続空間から離散空間にマッピングするように動作する請求項１５に記載の装置。
【請求項１７】
前記カテゴリ値を順序付けするタスクを連続最適化順序付け問題として形成することが、前記１つまたは複数の属性の前記カテゴリ値に基づいて類似度行列を計算することを含む、請求項１５に記載の装置。
【請求項１８】
前記類似度行列が１つまたは複数のマルチ集合演算に基づくものである請求項１７に記載の装置。
【請求項１９】
前記１つまたは複数のマルチ集合演算が２つのタイプの類似度測定値を計算することを含み、第１のタイプが同じ属性からの２つのカテゴリ値の間で計算される類似度であり、第２のタイプが異なる属性からの２つのカテゴリ値の間で計算される類似度である、請求項１８に記載の装置。
【請求項２０】
前記カテゴリ値を順序付けするタスクを連続最適化順序付け問題として形成することが、前記類似度行列からラプラス行列を計算することをさらに含む、請求項１７に記載の装置。
【請求項２１】
前記連続最適化順序付け問題に対する少なくとも１つの連続順序付け解を計算することが、前記ラプラス行列の最小の正の固有値を見つけることを含む、請求項２０に記載の装置。
【請求項２２】
前記連続最適化順序付け問題に対する少なくとも１つの連続順序付け解を計算することが、前記ラプラス行列の前記最小の正の固有値から対応する最適な固有ベクトルを得ることをさらに含む、請求項２１に記載の装置。
【請求項２３】
前記プロセッサがさらに、前記解を前記データ視覚化システムに従って使用できるようにする前に、前記最適な固有ベクトルに関連する対応する値に従って前記カテゴリ値を順序付けするように動作する、請求項２２に記載の装置。
【請求項２４】
前記カテゴリ値が複数の属性に関連し、前記プロセッサがさらに、前記カテゴリ値を順序付けするタスクを連続最適化順序付け問題として形成する前に、前記複数の属性に関連する前記カテゴリ値をオブジェクトの集合にマッピングして、前記形成するステップおよび計算するステップが前記オブジェクトの集合に関して実施されるように動作する、請求項１５に記載の装置。
【請求項２５】
前記プロセッサが、前記取得するステップ、形成するステップ、および計算するステップを前記データ視覚化システムの前処理操作に関連して実施する請求項１５に記載の装置。
【請求項２６】
前記プロセッサが、前記取得するステップ、形成するステップ、および計算するステップを前記データ視覚化システムのデータ管理モジュールに関連して実施する請求項１５に記載の装置。
【請求項２７】
前記プロセッサが、前記取得するステップ、形成するステップ、および計算するステップを前記データ視覚化システムのデータ・ビューア・モジュールに関連して実施する請求項１５に記載の装置。
【請求項２８】
データ・セットに関連する１つまたは複数の属性のカテゴリ値を順序付けするデータ処理装置であって、
（ｉ）前記データ・セットに関連する前記１つまたは複数の属性の前記カテゴリ値を取得し、（ｉｉ）各頂点が前記順序付けされるカテゴリ値であり一辺の重みが連結される頂点の類似度を表す元のグラフ構造として前記カテゴリ値をモデル化し、（ｉｉｉ）１つまたは複数のより粗いグラフ構造からなる階層的シーケンスによって前記元のグラフ構造を近似し、同様に局所的な構造を有する各頂点がより粗いグラフ構造における１つの頂点にマージされ、（ｉｖ）連続最適化順序付け操作に従って最も粗いグラフ構造を順序付けし、（ｖ）前記最も粗いグラフ構造の前記順序付けを前記元のグラフ構造まで逆伝播し、（ｖｉ）前記元のグラフ構造に関連する前記伝播された順序付けの少なくとも一部分をデータ視覚化システムに従って使用できるように動作する少なくとも１つのプロセッサ
を含む装置。
【請求項２９】
データ・セットに関連する１つまたは複数の属性のカテゴリ値を順序付けするためのコンピュータ・プログラムであって、実行時に
前記データ・セットに関連する前記１つまたは複数の属性の前記カテゴリ値を取得するステップと、
前記データ・セットに関連する前記１つまたは複数の属性の前記カテゴリ値を順序付けするタスクを連続最適化順序付け問題として形成するステップと、
前記連続最適化順序付け問題に対する少なくとも１つの連続順序付け解を計算するステップと、
前記計算された連続順序付け解の少なくとも一部分をデータ視覚化システムに従って使用できるようにするステップと
を実施するプログラム。
【請求項３０】
データ・セットに関連する１つまたは複数の属性のカテゴリ値を順序付けするためのコンピュータ・プログラムであって、実行時に
前記データ・セットに関連する前記１つまたは複数の属性の前記カテゴリ値を取得するステップと、
各頂点が順序付けされる前記カテゴリ値であり一辺の重みが連結された頂点の類似度を表す元のグラフ構造として前記カテゴリ値をモデル化するステップと、
１つまたは複数のより粗いグラフ構造からなる階層的シーケンスによって前記元のグラフ構造を近似するステップであって、同様に局所的な構造を有する各頂点がより粗いグラフ構造における１つの頂点にマージされるステップと、
連続最適化順序付け操作に従って最も粗いグラフ構造を順序付けするステップと、
前記最も粗いグラフ構造の前記順序付けを前記元のグラフ構造まで逆伝播するステップと、
前記元のグラフ構造に関連する前記伝播された順序付けの少なくとも一部分をデータ視覚化システムに従って使用できるようにするステップと
を実施するプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、データ探索および解析技法に関し、詳細には、そうしたデータ探索および解析技法で使用するためにカテゴリ・データを順序付けし視覚化するシステムおよび方法に関する。
【背景技術】
【０００２】
大量のデータからの情報を伝達し解釈する際には、視覚表現がますます重要になっている。これは、人間の視覚が、意味のあるパターンおよび空間的関係の識別に極めて優れていることが知られているからである。優れた効果的な視覚表現は、人間の視覚能力を最大限活用するように情報を提示し、したがって、データに隠された意味のある傾向および異常を明らかにすることができる。実際のデータ・セットにおける多数のデータ属性はカテゴリをなす。カテゴリ値はオブジェクトのカテゴリを伝達する。通常は、カテゴリ値には関連する自然な順序も距離もない。たとえば、ホスト名、イベント名、イベント重大度などの属性を有するイベントの時間的シーケンスを表すデータ・セットを考える。おそらく、イベント重大度の意味のある順序を定義することはできるが、距離とホスト名およびイベント名の順序とを定義する自然な方法はない。視覚化を構築する際にその固有の幾何的特性を直接利用することによる数値データの視覚化に関しては多くの研究が行われてきたが、カテゴリ・データ中の構造の視覚化および抽出についての研究ははるかに少ない。明らかに、属性値に順序がないと複雑度が増大する。これは、カテゴリ値を完全に順序付けできるやり方は指数関数的に多く存在するからである。しかし、そうした順序すべてが等しく有効な視覚化をもたらす可能性は極めて低い。MaおよびHellersteinはこの問題を明らかにし、カテゴリ・データを効果的に視覚化するには順序付けアルゴリズムの質が決定的であることを示した。これについては、欧州特許出願第００３０９２１．９号；Ｓ・マ（S.Ma）およびＪ・Ｌ・ヘラースタイン（J.L. Hellerstein）、「視覚化を向上させるためのカテゴリ・データの順序付け（Orderingcategorical data to improve visualization）」、情報視覚化に関するＩＥＥＥシンポジウム会議録（Proceedingsof the IEEE Symposium on Information Visualization）、1999年；およびＳ・マ（S. Ma）およびＪ・Ｌ・ヘラースタイン（J.L.Hellerstein）、「EventBrowser：イベント管理のためのイベント・データの探索的分析（EventBrowser: exploratoryanalysis of event data for event management）」、ディーエスオーエム（DSOM）1999年を参照されたい。
【０００３】
カテゴリ値を順序付けすることの重大性を示すために、前述の開示においてMaおよびHellersteinにより使用されたものと同じデータ・セットを検討する。このデータ・セットは、１６０のホストが２０のイベント・タイプを使って３日間にわたって生成した１０，０００件を超えるイベントを含む。図１にデータ・セットの散布図を示す。図でｘ軸およびｙ軸はイベントの時間およびホスト名（たとえば、コンピュータ装置からなるネットワーク内のホストの識別子（ＩＤ））をそれぞれ表す。この図では、ホスト名がカテゴリをなすため、それらを何らかの方法で（ｙ軸上の）幾何的座標にマッピングする必要がある。図１のホスト名の順序はホスト名のランダムな順列である。そのランダムな順序付け方式のために、残念ながら図１の散布図によって生じる結果は特に何かを明らかにするものではない。したがって、データ・セットのより高品質の視覚化を提供するためには、何らかのより優れた順序付けまたはマッピングが必要とされることが明白である。
【０００４】
前述の開示においてMaおよびHellersteinによって扱われ、また本発明の中心でもある主要な問題は、効果的な視覚化をもたらすマッピングをいかに見つけるかである。明らかに、そのようなマッピング構築の背後にある指針は、幾何的近接性を利用してオブジェクト間の関係を捉えることである。すなわち、類似の関連するオブジェクトが互いに近くに配置されるようにすることが望ましい。
【０００５】
多数の研究および商業製品で、カテゴリ・データ・セットに視覚化技法を適用している。たとえば、Ｍ・Ｏ・ワード（M.O. Ward）、「XmdvTool：複数の多変数データ視覚化の方法の統合（XmdvTool: Integratingmultiple methods for visualizing multivariate data）」、情報視覚化会議録（Proceedings ofthe Conference on Visualization）（米国カリフォルニア州ロスアラミトス（Los Alamitos、CA、USA））ＩＥＥＥコンピュータ学会プレス（IEEEComputer Society Press）、326〜336頁、1994年10月；IBM社のDiamondソフトウェア、および１９９９年７月２７日に出願の、「Systemsand Methods for Exploratory Analysis of Data for Event Management」という名称の米国特許出願第０９／３５９，８７４号などがある。そうした成果は４つのクラスに分類することができる。
【０００６】
簡単な一手法は、補助的な数値属性に基づいてカテゴリ値を順序付けすること、またはそれらの値をアルファベット順に順序付けすることである。前述の例では、ホスト名をそれらがデータ・セットで最初に出現する時間によって順序付けすることができる。この手法は、システムによって生成されるイベントの順序に何らかの因果関係があるという想定に基づくものである。しかし、この手法は視覚的タスクに関連しておらず、したがって、一般に、最高の視覚化品質を提供することができない。この手法に関連する性能は、データ・セットのサイズおよび複雑度が増すにつれて悪化する。
【０００７】
第２のクラスは、主に、クラスタ化に基づく手法に焦点を合わせたものである。これについては、たとえば、Ｖ・ギアンティ（V. Gianti）他、「CACTUS：要約を使ったカテゴリ・データのクラスタリング（CACTUS: Clusteringcategorical data using summaries）」、第５回知識発見およびデータ・マイニングに関するＡＣＭ  ＳＩＧＫＤＤ国際会議会議録（Proceedingsof the Fifth ACM SIGKDD International Conference on Knowledge Discovery andData Mining）、エーシーエム・プレス（ACM Press）、73〜83頁、1999年8月；Ｄ・ギブソン（D. Gibson）他、「カテゴリ・データのクラスタリング：動的システムに基づく手法（Clusteringcategorical data: An approach based on dynamic systems）」、第２４回巨大データベース（ＶＬＤＢ）に関する国際会議会議録（Proceedingsof the 24th International Conference on Very Large Data Bases, VLDB）、311〜322頁、1998年8月；Ｓ・グーハ（S.Guha）他、「Rock：カテゴリをなす属性のためのロバスト・クラスタリング・アルゴリズム（Rock: a robust clusteringalgorithm for categorical attributes）」、第１５回データ・エンジニアリングに関する国際会議会議録（Proc. of the15th Int. Conf. on Data Eng.）、1999年；およびＳ・マ（S. Ma）およびＪ・Ｌ・ヘラースタイン（J.L.Hellerstein）、「視覚化を向上させるためのカテゴリ・データの順序付け（Ordering categorical data to improvevisualization）」、情報視覚化に関するＩＥＥＥシンポジウム会議録（Proceedings of the IEEE Symposium onInformation Visualization）、1999年を参照されたい。
【０００８】
クラスタ化はデータ・セットを洞察する自然な方法である。しかし、視覚化のためには、その値に３つの問題が影響を与える。第１に、クラスタは幾何的空間内で識別できるが、クラスタ記述は依然として順序付けされない。クラスタを順序付けし視覚化しかつ各クラスタ内の要素を順序付けし視覚化するためには、何らかの自明でない追加の方法が必要である。第２に、大部分のクラスタ化アルゴリズムでは、特定の、通常は非常に構造化されたクラスタ形状（たとえば、前述のCACTUS手法の長方形領域など）が好ましく、データ・セットにクラスタ化傾向が全くない可能性がある場合でも、常にデータをその形状のクラスタに分割しようとする傾向がある。特に、CACTUS手法は、前述のGibson手法が、属性の何らかのサブセット上で重複する射影を有するクラスタなど、クラスタのいくつかの自然なクラスを発見できないことを示した。データのクラスタ化構造について何らかの仮定を行うことは、構造を抽出するためにクラスタ化アルゴリズムを使用するという全体の目的に反すると感じられる。本発明は、データについて事前の仮定を一切行わずにその順序を明らかにする技法を対象とする。そのために、本発明は最適化フレームワークを使ってこの問題を定式化する。
【０００９】
アルゴリズムの第２のクラスに関連して、前述の米国特許出願第０９／３５９，８７４号で提案された第３の手法は、階層的順序付けに基づくものである。この手法は、（何らかの類似度関数に関して）最も近い１対の点の反復的グループ化を実施し、その対を単一の点で置き換える。したがって、これらの点は、ネストされて順序付けされたサブセットの厳密な階層に形成される。任意の２つのサブセット間の最短経路の長さは、それらの類似性の度合いに対応する。全体的な順序付け構築が、ボトムアップ方式で再帰的にサブセットの対の局所的な順序付けに還元される。この手法では、各点が関連付けられる複数の異なる方式を厳密に階層的なツリーが反映できず、この状況は、データのサイズおよび複雑度が増すにつれてより厳しくなる。第２に、階層的順序付けは事実上決定論的である（各点がグループ化された後は、そのグループ化、すなわちその順序付けを再評価する機会が与えられない）。
【００１０】
第４の手法は、多次元スケーリング（multidimensional scaling、ＭＤＳ）や、Ｃ・ファロウツォス（C. Faloutsos）他、「FastMap：従来型データ・セットおよびマルチメディア・データ・セットの索引付け、データ・マイニングおよび視覚化のための高速アルゴリズム（FastMap:A fast algorism for indexing, data-mining and visualization of traditional andmultimedia data sets）」、1995年データ管理に関するＡＣＭ  ＳＩＧＭＯＤ国際会議会議録（カリフォルニア州サンノゼ）（Proceedingsof the 1995 ACM SIGMOD International Conference on Management of Data (San Jose、California)）、163〜174頁、1995年5月などの射影法を用いるものである。これらの技法にはその目標に関連する根本的な限界がある。ＭＤＳは、（類似度関数に関する）元データの諸点間の距離をできるだけ忠実に保つデータの低次元視覚表現を生成する。問題は、視覚探索の場合、通常は、何を探すのかが事前に知られていないため適当な類似度関数がないことである。したがって、特定の類似度関数に関する距離を保存すること自体を目標とするのでなく、その順序がある妥当な類似度関数に対して整合性を持つようにする必要がある。すなわち、点ｕがｗよりもｖに類似している場合、それらの順序においてｕをｗよりもｖの近くにマッピングする必要がある。ただし、類似度の実際の比率を保存することを目標とするのではない。換言すると、その順序を、（何らかの特定の類似度関数に関して測定される距離について）距離保存的とするのではなく、トポロジ保存的とすることがより望ましい。さらに、ＭＤＳは大規模なデータ・セットの場合は法外に高くつき、新規の点を既存の射影に増分的にマッピングすることができない（新規の点を追加した後で、基本的にマッピング全体を再計算する必要がある）。
【特許文献１】
欧州特許出願第００３０９２１．９号
【特許文献２】
米国特許出願第０９／３５９，８７４号
【非特許文献１】
Ｓ・マ（S. Ma）およびＪ・Ｌ・ヘラースタイン（J.L.Hellerstein）、「視覚化を向上させるためのカテゴリ・データの順序付け（Ordering categorical data to improvevisualization）」、情報視覚化に関するＩＥＥＥシンポジウム会議録（Proceedings of the IEEE Symposium onInformation Visualization）、1999年
【非特許文献２】
Ｓ・マ（S. Ma）およびＪ・Ｌ・ヘラースタイン（J.L.Hellerstein）、「EventBrowser：イベント管理のためのイベント・データの探索的分析（EventBrowser: exploratoryanalysis of event data for event management）」、ディーエスオーエム（DSOM）1999年
【非特許文献３】
Ｍ・Ｏ・ワード（M.O. Ward）、「XmdvTool：複数の多変数データ視覚化の方法の統合（XmdvTool:Integrating multiple methods for visualizing multivariate data）」、情報視覚化会議録（Proceedingsof the Conference on Visualization）（米国カリフォルニア州ロスアラミトス（Los Alamitos、CA、USA））ＩＥＥＥコンピュータ学会プレス（IEEEComputer Society Press）、326〜336頁、1994年10月
【非特許文献４】
Ｖ・ギアンティ（V. Gianti）他、「CACTUS：要約を使ったカテゴリ・データのクラスタリング（CACTUS:Clustering categorical data using summaries）」、第５回知識発見およびデータ・マイニングに関するＡＣＭ  ＳＩＧＫＤＤ国際会議会議録（Proceedingsof the Fifth ACM SIGKDD International Conference on Knowledge Discovery andData Mining）、エーシーエム・プレス（ACM Press）、73〜83頁、1999年8月
【非特許文献５】
Ｄ・ギブソン（D. Gibson）他、「カテゴリ・データのクラスタリング：動的システムに基づく手法（Clusteringcategorical data: An approach based on dynamic systems）」、第２４回巨大データベース（ＶＬＤＢ）に関する国際会議会議録（Proceedingsof the 24th International Conference on Very Large Data Bases, VLDB）、311〜322頁、1998年8月
【非特許文献６】
Ｓ・グーハ（S. Guha）他、「Rock：カテゴリをなす属性のためのロバスト・クラスタリング・アルゴリズム（Rock:a robust clustering algorithm for categorical attributes）」、第１５回データ・エンジニアリングに関する国際会議会議録（Proc.of the 15th Int. Conf. on Data Eng.）、1999年
【非特許文献７】
Ｃ・ファロウツォス（C. Faloutsos）他、「FastMap：従来型データ・セットおよびマルチメディア・データ・セットの索引付け、データ・マイニングおよび視覚化のための高速アルゴリズム（FastMap:A fast algorism for indexing, data-mining and visualization of traditional andmultimedia data sets）」、1995年データ管理に関するＡＣＭ  ＳＩＧＭＯＤ国際会議会議録（カリフォルニア州サンノゼ）（Proceedingsof the 1995 ACM SIGMOD International Conference on Management of Data (San Jose、California)）、163〜174頁、1995年5月
【非特許文献８】
Ｗ・Ｅ・ドーナス（W.E. Donath）他、「グラフ分割アルゴリズムおよび結合行列の固有ベクトルに基づくコンピュータ論理（Algorithmsfor partitioning graphs and computer logic based on eigenvectors of connectionmatrices）」、アイビーエム技術開示報告（IBM Technical Disclosure Bulletin）15 1972年、第3号、938〜944頁
【非特許文献９】
Ｍ・フィードラー（M. Fiedler）、「グラフの代数的結合性（Algebraicconnectivity of graphs）」、チェコスロバキア数学ジャーナル（Czecheslovak Mathematical Journal）23（1973年）、第98号、298〜305頁
【非特許文献１０】
Ｋ・Ｍ・ホール（K.M. Hall）、「ｒ次元２次配置アルゴリズム（Anr-dimensional quadratic placement algorithm）」、経営科学（Management Science）17（1970年）、第3号、219〜229頁
【非特許文献１１】
Ｇ・カリピス（G.Karypis）他、「マルチレベル・ハイパーグラフ分割：ＶＬＳＩドメインにおける応用例（Multilevelhypergraph partitioning: Applications in VLSI domain）」、テクニカル・レポート（Tech. report）、ミネソタ州立大学コンピュータ・サイエンス学部（Universityof Minnesota, Department of Computer Science）、1997年、第３４回設計自動化会議（34th DesignAutomation Conference）における縮約版
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明は、データをより効果的に視覚化するようにカテゴリ属性を順序付けする技法を提供する。
【課題を解決するための手段】
【００１２】
本発明の第１の態様においては、データ・セットに関連する１つまたは複数の属性のカテゴリ値を順序付けする、コンピュータに基づく技法は、以下の諸ステップ／操作を含む。まず、順序付けされるカテゴリ値を取得する。これらのカテゴリ値を与え、カテゴリ値を順序付けするタスクを連続最適化順序付け問題として定式化する。タスクを連続最適化順序付け問題として定式化した後で、連続最適化順序付け問題に対する少なくとも１つの連続した（好ましくは最適な）順序付け解を計算する。この技法はまた、計算された連続順序付け解を連続空間から離散空間にマッピングすることを含むこともできる。計算された連続順序付け解の少なくとも一部分を、データ視覚化システムに従って使用することができる（すなわち、ユーザに示すことができる）。
【００１３】
一実施形態においては、カテゴリ値を順序付けするタスクを連続最適化順序付け問題として形成するステップ／操作は、１つまたは複数の属性のカテゴリ値に基づく類似度行列の計算を含むことができる。類似度行列は１つまたは複数のマルチ集合演算に基づくものとすることができる。１つまたは複数のマルチ集合演算は、２つのタイプの類似度測定値の計算を含むことができる。第１のタイプは同じ属性からの２つのカテゴリ値間で計算される類似度であり、第２のタイプは異なる属性からの２つのカテゴリ値間で計算される類似度である。さらに、カテゴリ値を順序付けするタスクを連続最適化順序付け問題として形成するステップ／操作は、類似度行列からラプラス行列を計算することを含むことができる。次いで、連続最適化順序付け問題に対する少なくとも１つの連続順序付け解を計算するステップ／操作は、ラプラス行列の最小の正の固有値を見つけ、その後、そのラプラス行列の最小の正の固有値から対応する最適な固有ベクトルを得ることを含むことができる。次いで、その最適な固有ベクトルに関連した対応する値に従って、カテゴリ値を順序付けすることができる。
【００１４】
本発明の第２の態様においては、複数の属性に関連するカテゴリ値を順序付けする技法が提供される。こうした技法によれば、カテゴリ値を順序付けするタスクを連続最適化順序付け問題として形成する前に、前述の形成するステップ／操作および計算するステップ／操作がオブジェクトの集合に従って実施されるように、複数の属性に関連するカテゴリ値をオブジェクトの集合にマッピングする。
【００１５】
本発明の第３の態様においては、データ・セットに関連する１つまたは複数の属性のカテゴリ値を順序付けする多階層フレームワーク技法は、以下の諸ステップ／操作を含む。まず、順序付けされるカテゴリ値を取得する。これらのカテゴリ値が与えられたものとして、各頂点が順序付けされるカテゴリ値であり、一辺の重みが連結される頂点の類似度を表す、元のグラフ構造としてカテゴリ値をモデル化する。次いで、この元のグラフ構造を１つまたは複数のより粗いグラフ構造からなる階層的シーケンスによって近似する。ここで、より粗いグラフ構造において同様に局所的な構造を有する各頂点が１つの頂点にマージされる。その最も粗いグラフ構造を連続最適化順序付け操作に従って順序付けする。その最も粗いグラフ構造の順序付けが、元のグラフ構造にまで逆伝播され、伝播された元のグラフ構造に関連する順序付けの少なくとも一部分をデータ視覚化システムに従って使用することができる。
【００１６】
本発明の上記およびその他の目的、特徴および利点は、以下の本発明の例示的実施形態の詳細な説明を添付の図面と併せ読めば明らかになるであろう。
【発明を実施するための最良の形態】
【００１７】
本発明は、データをより効果的に視覚化するようにカテゴリ属性を順序付けする技法を提供する。その際、以下で例を引いて説明するように、本発明は以下の３つの問題に焦点を当てるものと考えることができる。
【００１８】
（１）高速かつ効果的なアルゴリズムをいかに策定するか。カテゴリ・データを順序付けする問題は、組合せ最適化問題として定式化することができる。これはNP-hard問題である。これは、最適解が多項式時間内に得られる可能性が極めて低いことを示唆する。その結果、大部分の研究が組合せヒューリスティックに依拠していたため、準最適解しか得られなかった。たとえば、前述のMaおよびHellersteinの研究では、順序付け問題をハミルトン経路問題(HamiltonianPath problem)に還元し、欲張りヒューリスティック（greedy heuristic）を使ってハミルトン経路への近似を発見し、次いでその近似で順序付けを定義した。しかし、ヒューリスティック・アルゴリズムは、非常に非効率的であり、あるいは最適解を提供しないことがある（通常、アルゴリズムの実行時間とそのアルゴリズムによって見つかる近似の接近度との間にはトレードオフがある）。その他の研究では、たとえば、前述のGibsonの研究における動的システムの手法や力指向配置（forcedirected placement）など局所的な改善技法を提供している。そうした探索戦略では通常、比較的小さいグラフ中で多くの意味のある連結およびパターンを捉えようとするが、これらの戦略について十分な理論的理解は得られていない。せいぜい、いくつかの特殊事例の理論的解析があるに過ぎず、一般理論はまだ開発されていない。順序付けの質およびそのアルゴリズムの収束に要する時間について論じることは周知のように困難である。これらすべての理由により、近似の保証を得ることは困難である。本発明によれば、扱いにくい組合せ定式化を回避できる根本的に異なる方式で順序付け問題を定式化する。
【００１９】
（２）複数のカテゴリ属性を有するデータをいかに順序付けするか。現実のデータはしばしば、複数のカテゴリ属性を持つことがある。たとえば、１つのシステム・イベントは少なくとも２つのカテゴリ属性、すなわちイベント・タイプおよびホスト名を持つ。３次元散布図などの視覚化技法および並列座標グラフ（parallel coordinate graphs）は、多次元データの探索を可能にする。明らかに、これらの技法を使ってより多くの次元を効果的に視覚化するには、対応するカテゴリ属性を順序付けする必要がある。
【００２０】
（３）大量のデータを処理するために順序付けアルゴリズムをいかにスケールアップするか。今日、１つのデータベースに大量のデータが格納されることは珍しくない。これは情報を発見するための貴重な機会を提供する。しかし、大量のデータを処理する場合、データに対して直線的にスケーリングする効率のよいアルゴリズムを策定するという大きな難問が生じる。小規模のデータ向けに設計されたアルゴリズムは、大量のデータを解析するときに障害が生じることがある。
【００２１】
本発明は、これら３つの問題、並びにその他の問題に対処する、カテゴリ・データを順序付けする新規の手法を提供する。
【００２２】
効率的かつ効果的なアルゴリズムを得るために、前述の定式化の組合せ複雑度を回避する異なる手法を策定する。本発明の１つの重要な着想は、順序付け問題を連続最適化問題として定式化することである。したがって、本発明の順序付けアルゴリズムは３つのステップ、すなわち、（ａ）離散順序付け問題を連続最適化問題に変換するステップと、（ｂ）連続最適化問題を解くステップと、（ｃ）最適な連続解を最も近い離散解にマッピングするステップとを含むことができる。（ａ）を実施するためには、対応する離散式における離散的制約を緩和する。すなわち、最適な順序付けを見つけるのではなく、元のカテゴリ値を実数にマッピングする、最適な連続マッピングを見つけるようとする。ステップ（ｂ）では、（ａ）で得られた連続最適化問題を解く。
【００２３】
以下の各実施形態では、本明細書で定式化する連続最適化が、元の離散問題がNP-hardであっても、それを扱いやすくする特殊な構造を有することを示す。これにより、最適解を与えるスペクトル・アルゴリズムを策定できるようになる。たとえば、本発明のアルゴリズムは、データのグラフ表現から導出される特定の行列に関するスペクトルの（代数的）情報を使用する。本発明のアルゴリズムは、Ｗ・Ｅ・ドーナス（W.E.Donath）他、「グラフ分割アルゴリズムおよび結合行列の固有ベクトルに基づくコンピュータ論理（Algorithms for partitioninggraphs and computer logic based on eigenvectors of connection matrices）」、アイビーエム技術開示報告（IBMTechnical Disclosure Bulletin）15 1972年、第3号、938〜944頁；およびＭ・フィードラー（M. Fiedler）、「グラフの代数的結合性（Algebraicconnectivity of graphs）」、チェコスロバキア数学ジャーナル（Czecheslovak Mathematical Journal）23（1973年）、第98号、298〜305頁におけるグラフ区分化問題のために開発された代数ツールを一般化し、それを使って順序付け問題を解くことができるようにする。最後に、連続解を得た後、ステップ（ｃ）でそれらの連続値を離散空間にマッピングする。連続問題に対する解が最適であっても、その解を最も近い離散点にマッピングすることによって必ずしも最適な離散解が得られない（が、適切な近似を提供する）ことに留意する。しかし、データ・セットの順序を確立する問題は、区分化を確立することとは根本的に異なる。すなわち、この緩和は、それ自体で意味のある貴重な視覚化を提供する。したがって、連続解を元の離散空間にマッピングすることは必須ではない。
【００２４】
次に、前述の複数の属性を扱うアルゴリズムをいかに一般化するかを論じる。現実のデータにはしばしば複数の属性がある。複数の属性値の関係を探索するために多くの視覚化技法が開発されてきた。たとえば、３次元散布図を使用すると３次元を描くことができる。平行図（parallel plot）は一連の平行軸を使用し、各平行軸が単一の属性ドメインを表す。連続する軸上の値を連結するまっすぐな線分は、そのデータ・セットが（対応する属性の値として）これらの値両方を含む少なくとも１つのエントリを有することを示す。順序付け問題は、視覚化を向上させるように各軸上の属性値をマッピングすることを含む（通常、その目標は辺の交差数を最小限にすることである）。同時に順序付けする必要のあるカテゴリ属性が２つ以上あるため、各属性の順序が単独で満足のいくものでならないだけでなく、その順序がそれ以外の順序に対しても互いに満足のいくものでなければならないことによって、個々での状況が複雑化されることに留意されたい。各属性ドメインを別々に順序付けするのではなく、本発明では、すべての属性ドメイン値を単一の線上の値にマッピングすることを意味する「異種」線形順序付けを作成する。これは、すべての順序付けが相互に同期を保つという問題を有利に解決する。特定の属性ドメインの値のマッピングを取得する場合、本発明では、異種マッピング（異種マッピングは複数の同種マッピングに分割される）中の対応するエントリを取得する。
【００２５】
スペクトル・アルゴリズムは一般に高品質の順序付けを生成するが、他の方法よりも高くつくことがある。疎行列の場合、ランチョス反復法（Lanczoz iteration）によって、対称固有値問題が予想時間Ｏ（ｎ１．４）内に解決される。実際問題として、極度に大きいデータ・セットの場合はこれでは遅いことがある。しかも、実際の大規模データ・セットからのグラフは通常、高度に過剰決定されており、ほぼ同一の隣接構造を持つ複数の頂点を含むことがある。大量データを扱えるように本発明のアルゴリズムを拡張するために、グラフ区分化問題用の多階層順序付けフレームワークを策定する。その一般的な着想は、より小さくより粗いグラフからなるシーケンスによって元のグラフを近似することである。次レベルのより粗いグラフは、類似の隣接構造を有するすべての頂点を単一の多重頂点（multi-vertex）にまとめることによって形成する。その最も粗いグラフを順序付けする。次いで、その各中間グラフからなるシーケンスに次々と内挿する（とともにグラフを微細化する（uncoarsen）に従ってその順序付けを精緻化する）ことによって、生成された順序を元のグラフまで逆伝播する。その際、グラフのサイズを線形的に縮小するため、時間が大いに節約される。
【００２６】
要約すると、本発明は、（１）順序付け問題を解くための効率的なスペクトル・アルゴリズムと、（２）複数のカテゴリ属性を処理する新規の技法と、（３）アルゴリズムを非常に大きなデータ向けに拡張する一般的な階層的方式とのうちの１つまたは複数を含む、カテゴリ・データを順序付けする技法を提供する。
【００２７】
本発明の別の興味深い特徴は、数値解析者は固有ベクトルを探すことを仕事としているので、たとえば、ＩＢＭ社のESSL Libraryなど、そのために容易に使用できるソフトウェアが多数あることであることに留意されたい。
【００２８】
詳細な説明の以下の部分では、本発明の例示的実施形態の説明を提供する。まず、視覚化システムの観点から順序付け問題について述べ、次いで、本発明を実装するための例示的アルゴリズムを詳細に述べる。
【００２９】
図２に、たとえば、その実施形態が「EventBrowser」と呼ばれる、１９９９年７月２７日出願の、「Systemsand Methods for Exploratory Analysis of Data for Event Management」という名称の前述の米国特許出願第０９／３５９，８７４号に記載されるシステムなどの一般的な視覚化システムを示す。この視覚化システムは、データ・ソース２１０、データ管理モジュール２２０、ビューア２３０という３つの主要な構成要素を備える。データ・ソースは視覚化されるデータを記憶する。データ管理モジュールは、基本的なデータ照会操作を提供し、メモリ内データを保持し、ビューア間の対応関係を提供する。ビューアは、視覚化技法（たとえば散布図）や集計技法など、事前定義された手法を使ってデータを視覚化する機構を提供する。また、ビューアはエンド・ユーザとの対話も行う。
【００３０】
図３、図４、図５に本発明の順序付け技法を異なる方式で用いることができる３つの視覚化システムを示す。すなわち、本発明の方法を用いる順序付けアルゴリズムまたはエンジンは、以下で詳細に説明するように、異なる利点を生み出すために、視覚化システム中の異なる場所で実装することができる。
【００３１】
図３に、本発明の順序付け機構または順序付けエンジン２４０を視覚化システムのデータ処理段階の一部として使用できることを示す。すなわち、順序付けエンジンは、データ管理モジュール２２０とビューア２３０による使用の前に、データ・ソース２１０でデータに作用する。そうしたシステムの１つの利点は、順序付け機構が視覚化システムから見えないため、その順序付け機構を使用するように既存の視覚化システムを変更する必要がないことである。この実装形態は、データが十分に理解されており比較的安定している用途に適している。すなわち、類似のレポートが生成でき、それらが毎回同じ順序付けアルゴリズムを使用するように、データを解析するプロセスが固定される。
【００３２】
図４に、本発明の順序付けエンジン（アルゴリズム）２４０を視覚化システムのデータ管理モジュール２２０の一部として組み込んだシステムを示す。この実装形態は、順序付けアルゴリズムをより柔軟に使用できるようにする。というのは、複数のビューアに対する複数の順序付けアルゴリズムをサポートすることができ、オンザフライで順序付けを行うことができるからである。
【００３３】
図５に、順序付けエンジン２４０をビューア２３０の一部として実装したシステムを示す。この実装形態はデータ管理モジュール２２０の変更を全く必要としない。加えてこのシステムでは、単に特別なビューアを作成することによって、ユーザ（または用途）の特定のニーズを満たすように順序付けアルゴリズムを適合させることが容易になる。
【００３４】
要約すると、図３、図４、図５には、視覚化システムを使用して本発明の順序付け機構を実装する３つの異なる方式が示してある。どのシステム実装形態を使用するかの選択は主として用途によって異なることを理解されたい。
【００３５】
次に、本発明の順序付けアルゴリズムの詳細な説明に移る。まず、改めて問題を表明し、基本的な順序付け用スペクトル・アルゴリズムを提示する。次いで、複数のカテゴリ属性をいかに扱うかを論じる。最後に、大量のデータを処理するための多階層方式を策定する。
【００３６】
最初に、いくつかの概念を導入する。順序付けされるｎ個のオブジェクトを｛ｏ１，ｏ２，・・・，ｏｎ｝で表す。オブジェクトｏｉとｏｊの類似度をｓ（ｉ，ｊ）で表す。順序付け問題は、Σｉ，ｊｓ（ｉ，ｊ）（π（ｉ）−π（ｊ））２を最小化する順列π｛１，・・・，ｎ｝を見つけることを含む。
【００３７】
明らかに、この最適化関数は、類似のオブジェクトを近い位置に配置するよう促す。すなわち、２つのオブジェクトが類似している、すなわちｓ（ｉ，ｊ）が大きい場合、これら２つのオブジェクトは近い位置に配置される、すなわち（π（ｉ）−π（ｊ））２が小さくなるはずである。上記の式が離散最適化問題であり、NP-hard問題であることに留意されたい。これは、その最適解が多項式時間内に得られる可能性が極めて低いことを示唆する。したがって、本発明では、実際の配置｛ｘ１，・・・ｘｎ｝を見つけることによってこの離散最適化問題を連続最適化問題に変換し、その正規化のための制約条件Σｉｘ（ｉ）２＝１に従ってΣｉ，ｊｓ（ｉ，ｊ）（ｘ（ｉ）−ｘ（ｊ））２を最小化するようにする。
【００３８】
ここで、実数ｘｉはオブジェクトｏｉの配置である。最適な配置ベクトルＸ＝｛ｘ１，・・・ｘｎ｝を取得した後は、対応するｘ座標によってそれらのオブジェクトを順序付けすることができる。目的関数は、ＸＴＸ＝１を条件とするＸＴＬＸの最小化として書き換えることができることに留意されたい。式中、Ｌ＝Ｄ−Ｓである。ＸＴは最適な配置ベクトルＸの転置を表し、Ｌはラプラス行列を表すことを理解されたい。行列Ｄは、要素ｄｉｉ＝Σｊｓ（ｉ，ｊ）を有するｎ×ｎの対角行列であり、Ｓはｎ×ｎの類似度行列である。ｓ（ｉ，ｊ）は、類似度行列Ｓのｉ行ｊ列の要素を表すことを理解されたい。この連続配置問題の解は最小の正の固有値に関連するラプラス行列の固有ベクトルであることが知られている。これについては、Ｋ・Ｍ・ホール（K.M. Hall）、「ｒ次元２次配置アルゴリズム（An r-dimensional quadratic placementalgorithm）」、経営科学（Management Science）17（1970年）、第3号、219〜229頁を参照されたい。
【００３９】
前述の背景技術を用いて、本発明の一実施形態による例示的な順序付け用スペクトル・アルゴリズムについて述べる。このアルゴリズムの概略を図６に示す。このアルゴリズムへの入力として未処理のオブジェクト・データを使用することを理解されたい。この未処理データは、たとえば、前述した１６０のホストが２０のイベント・タイプを使って３日間にわたって生成した１０，０００件を超えるイベントを含むデータ・セットなどのデータ・セットとすることができ、その場合、順序付けまたはマッピングされるオブジェクトはホスト名である。
【００４０】
まず、ステップ３１０で、離散順序付け問題を連続最適化問題に変換する。すなわち、ステップ３１０では類似度行列Ｓとラプラス行列Ｌを計算することによって、その問題を連続最適化問題として定式化する。以下に類似度行列Ｓを計算する例示的方法について述べる。ラプラス行列Ｌは前述の関係式、Ｌ＝Ｄ−Ｓに従って計算することができ、ＤがＳから算出されるように、要素ｄｉｉ＝Σｊｓ（ｉ，ｊ）を有するｎ×ｎの対角行列としてＤを定義する。
【００４１】
次いで、ステップ３２０では連続最適化問題を解く。これは、Ｌの最小の正の固有値を見つけ、次いで，対応する最適な固有ベクトルＸを得ることによって行われる。この対応する最適な固有ベクトルは、当分野の技術者に知られている任意の従来技術で得ることができることを理解されたい。次いで、ステップ３３０で、最適な固有ベクトルＸに関連する、対応するｘ値によってオブジェクトを順序付けする。すなわち、オブジェクトの新しい順序は｛ｏｉ１，ｏｉ２，・・・，ｏｉｎ｝であり、ここでｘｉ１≦ｘｉ２≦・・・≦ｘｉｎである。したがって、この結果が元のオブジェクトの順序にマッピングされる。
【００４２】
図７に、図１の散布図で視覚化されているものと同じデータ・セットに上記の順序付けアルゴリズムを適用した結果を示す。この場合もやはり、目標はホストをｙ軸上に配置することである。ｘ軸は時間である。図中の座標（ｘ，ｙ）における点は、時間ｘにｙ番目のホストによって生成されたイベントを表す。図１も図７も同じデータ・セットを表すが、それぞれが異なるホストの順序を使用する。図１のホストの順序はランダムに割り当てられる。これに対して図７のホストの順序は図６に記載される順序付けアルゴリズムに従って決定される。明らかに分かるように、図７はデータに関するより多くの情報を提供する。たとえば、図７の順序付けは（この散布図の上部にある雲状の集合部分に示されるような）パターンおよびホストのさまざまな挙動を示し、したがって、イベント・データのより高品質の視覚化を提供する。
【００４３】
次に、本発明の一実施形態に従って複数のカテゴリ属性をいかに順序付けするかを示す。ここで、本発明では、すべての属性値の単一のオブジェクトの集合に対する１対１のマッピングを作成する。たとえば、２つの属性ＡおよびＢがあるとする。Ａは、ａ１とａ２の２つの値をもつ。Ｂはｂ１とｂ２の２つの値をもつ。ここで、ａ１をｏ１に、ａ２をｏ２に、ｂ１をｏ３に、ｂ２をｏ４にマッピングすることができる。ただし、｛ｏ１，ｏ２，ｏ３，ｏ４｝はオブジェクトの集合である。このようにして、複数の属性値を順序付けする問題を単一のオブジェクト集合を順序付けする問題に還元する。図６の状況で、前述のスペクトル・アルゴリズムを使ってオブジェクトの集合を順序付けした後で、オブジェクトの順序を対応する属性値の順序にマッピングする。前述の例における最適な順序付けが｛ｏ３，ｏ２，ｏ４，ｏ１｝であることが分かったと想定する。次いで、属性ＡおよびＢの値を、ｏ２がｏ１の前にあるため、｛ａ２，ａ１｝に順序付けし、｛ｂ１，ｂ２｝についても同様に順序付けする。図８にこの手順を詳しく示す。図示のように、ステップ４１０では各属性の値をオブジェクトにマッピングし、オブジェクトの各対ごとの類似度を計算する。ステップ４２０では、順序付け用スペクトル・アルゴリズムを実行し（図６）、順序付けされたオブジェクトの集合を得る。ステップ４３０ではその結果を反対に各属性にマッピングする。
【００４４】
本発明によれば、順序付けされるオブジェクトは１つまたは複数のカテゴリ属性値に対応する。前述のアルゴリズムを使用するためには、任意の２つのカテゴリ属性値の類似度測定法を定義する必要がある。前述のMaおよびHellersteinの研究は、イベント・データのカテゴリ値の類似度をその時間情報に基づいていかに測定するかを論じている。本発明では、マルチ集合演算に基づく類似度測定法を策定する。たとえば、データがｋ個の属性：Ａ１，・・・，Ａｋを持ち、それらのドメインがＤ１，・・・，Ｄｋであると想定する。明らかに、２つのタイプの類似度、すなわち、（１）属性内類似度および（２）属性間類似度の測定法を定義する必要がある。前者は同じ属性からの２つのカテゴリ値の間の類似度を測定する。後者は、２つの異なる属性からの２つのカテゴリ値の間の類似度を測定する。属性間類似度を得るために、
【００４５】
【数１】
2004532453.tif 000003
【００４６】
をデータの集合とし、そのｉ番目の属性が値ｘをもつものとする。属性間類似度Ｓ（ｕｉ,ｖｊ）（ｕ∈Ｄｉかつｖ∈Ｄｊ）は次式で計算することができる。
【００４７】
【数２】
2004532453.tif 000004
【００４８】
同様に、属性内類似度を得るために、
【００４９】
【数３】
2004532453.tif 000005
【００５０】
と置く。属性内類似度Ｓ（ｕｉ,ｖｉ）（ｕｉおよびｖｉはｉ番目の属性からの２つの値である）は、次式で定義することができる。
【００５１】
【数４】
2004532453.tif 000006
【００５２】
次に、本発明による例示的な多階層フレームワークに従って、大量のデータをいかに処理するかを論じる。本発明の順序付け用多階層スペクトル・アルゴリズムを例示するために、各頂点が順序付けされるカテゴリ値である疎の異種グラフとしてデータをモデル化する。一辺の重みは連結された頂点の類似度（連結された各頂点が同じ属性ドメインに属する場合は属性内類似度、それ以外の場合は属性間類似度）を表す。本発明では、多階層戦略によって大きな元のグラフを順序付けする。すなわち、より小さく粗いグラフからなるシーケンスによって元のグラフを近似する。同様に局所的な構造を有する頂点の集合がより粗いグラフ中の１つの頂点にマージされる。次いで、最も粗いグラフを順序付けし、粗いグラフの順序付けを保存するように中間グラフからなるシーケンスに次々と内挿することによって、元のグラフに至るまでその順序付けを逆伝播する。そのためには、本発明の基本のアルゴリズムを、１つの頂点が元のグラフにおける頂点の集合を表すことができる、頂点に重みがあるグラフに拡張する必要がある。
【００５３】
たとえば、より粗いグラフのｉ番目の頂点が、元のグラフのｗｉ個の頂点を表すものとする。アルゴリズムを多重頂点に基づくグラフに拡張する自然な方式は、ｗｉ個の頂点を最適化問題の制約条件に組み込むことである。変更された最適化問題を以下のように表すことができる。ＷＸＴＷＸ＝１を条件としてＸＴＬＸを最小化する。式中Ｗはｗｉ２を持つ対角行列であり、ｗｉは、Ｇで多重頂点ｉによって表される元のグラフの頂点の数である。元の式に比べると、上記の最適化では制約条件が
【００５４】
【数５】
2004532453.tif 000007
に変更される。上記の最適化問題の最適解は、Ｌ’の０でない最初の固有ベクトルである
と示すことができる。ここで、Ｌ’＝Ｗ−１Ｌである。
【００５５】
前述の元のK.M. Hallアルゴリズムを実際のデータ・セットに適用する際の問題は、この元のK.M.Hallアルゴリズムによって、特に原点の周囲において各点が極度のアグロメレーション（agglomeration凝集状態）になる順序付けが生じることである。これは、その構築で使用される固有ベクトルが通常、正規化のための制約条件によって、少数の大きな成分を有しているからである。これによって残りの各座標が０に近づき、したがって、視覚空間が高度に散乱した領域になる。その結果、０でない最小の固有値に対応する固有ベクトルを選択することにより必ずしも適切な視覚化が得られるとは限らないことになる。したがって、本発明では、固有ベクトルの選択時に２つの構造的制約を課すことによって、そうした縮退を回避する変更形態を提供する。第１の制約条件は、選択された固有ベクトルのすべての要素がデータ・セットのサイズの関数であるユーザ定義の閾値（たとえば０.０５など）よりも大きいことである。第２の制約条件は、選択された固有ベクトルの任意の２つの要素間の差がユーザ定義の閾値（たとえば０.１など）よりも大きいことである。これら２つの制約条件は、基本的に、配置ベクトルが情報理論的な意味で有意である、すなわち、最小エントロピーが高くなければならないと規定する。
【００５６】
図９に、本発明の一実施形態による多階層順序付けアルゴリズムの流れ図を示す。図示のように、このアルゴリズムは４つのステップを含む。
【００５７】
ステップ５１０で、アルゴリズムは順序付けされるカテゴリ値の異種グラフＧ０を構築する。異種グラフの各ノードはカテゴリ値を表す。辺は連結された２つのノードの類似度を表す。
【００５８】
ステップ５２０で、アルゴリズムは、より粗いグラフＧｉ+１における多重頂点と呼ばれる１つの新規のノードに、Ｇｉの頂点の集合をまとめることによって、グラフ（元のグラフＧ０から始まる）Ｇ０，Ｇ１・・・Ｇｋからなる階層を作成する。この多重頂点の重みはそれが表す元のノード数である。次いでＧｉ+１は、次にグラフ粗略化（coarsening）を繰り返す際の入力グラフとして機能する。この粗略化段階は、十分に小さいグラフが得られたとき、たとえば、１００ノード以下のグラフ・サイズに達したときに完了する。
【００５９】
ステップ５３０で、アルゴリズムは、スペクトル・アルゴリズム（図６）を使って（上記のＧｋで示す）階層中で最小の（最も粗い）グラフの前述の多重頂点を順序付けする。
【００６０】
ステップ５４０で、アルゴリズムは、中間グラフからなるシーケンスに次々とＧｋの順序付けをＧ０に至るまで逆伝播または内挿し、アルゴリズムが進むに従って順序付けを精緻化する。
【００６１】
前述の多階層アルゴリズムが適切に機能する理由がいくつかある。第１に、粗略化する段階で、グラフの瑣末で冗長な詳細部分が隠され、データに関する最も重大な連結度情報だけが保存される。これによって適切な初期順序を見つけることができるようになり、その結果が元のグラフに伝播されていくに従ってその順序を繰り返し精緻化することができる。第２の理由は、元のグラフよりもはるかに小さいグラフ上で順序が計算されるので、この多階層手法では計算が著しく高速になることである。これでこのアルゴリズムを極めて大容量のデータにまで拡張することが可能になる。事実、最も粗いグラフを順序付けするのに必要な時間は重要な問題ではなくなり、したがって、この手法を実装するシステムは、高くつく（が非常に効果的な）順序付けアルゴリズムでさえも使用することができる。最後に、（最後の微細化段階時の）多階層精緻化で初期の順序付けの質が改善される。基本的に、本発明のスペクトル・アルゴリズムは、グラフの全体を見て素早く適切な初期順序を見つけ、次いで、この順序を元のグラフまで遡って射影していくに従ってこの順序を局所的に精緻化する。したがって、この手法は、異なるレベルの粒度でグラフを処理することによって、全体的手法と局所的手法の両方の長所を併せもつ。
【００６２】
以下の説明ではさらに、上記のアルゴリズムのステップ５２０および５４０がいかに動作するかについて述べる。各ステップにはさまざまな選択肢がある。ここで述べるのはそのうちのいくつかに過ぎない。実際の選択肢は用途に応じて決定することができる。本明細書中の教示によれば、当分野の技術者はその他の実装形態を理解するであろう。
【００６３】
粗略化段階では、類似性の高い隣接構造を有する頂点のサブセットが、次レベルのより粗いグラフの多重頂点に再帰的にマージされる。この粗略化方式が導き出されたのは、実際のデータ・セットが高度に過剰決定されており、複数の頂点がほぼ同一の連結性を持ち得ることによるものである。おおよその目安として、頂点の数は１回の粗略化で３分の１に減少する。この比率は、データに最初にどれだけの冗長性が含まれていたかを明示する。２頂点の隣接構造の類似度は、それらの正規化された隣接ベクトルの間の（すなわち、グラフの類似度行列の対応する各行の間の）ユークリッド距離として測定することができる。粗略化を実施する度に、対ごとの類似度が特定の閾値よりも大きい頂点の集合が１つの多重頂点にまとめられる。多重頂点の重みはそれが含む頂点の重みの総和に設定する。元のグラフの各頂点の重みは１に設定する。２つの多重頂点ＡおよびＢを連結する辺の重みは、Ａのある頂点からＢのある頂点までのすべての辺の重みの総和に設定する（得られる粗いグラフの重みは再正規化されていることに留意されたい）。これによって、より粗いグラフの連結性がより微細なグラフの連結性から継承されることが保証される。その結果、最も粗いグラフは、元のグラフの多くの重要な連結特性を保存する。マージされるべき頂点のサブセットを見つけるための素朴な手法は、シーケンス中のすべてのグラフの類似度行列を計算することである。明らかに、この手法は計算的に高くつく（最初のグラフの類似度行列を計算するだけでＯ（ｎ２）の時間がかかる）。本発明では、グラフの高度に連結された構成要素を近似する、ランダム化されたアルゴリズムを使ってこのサブセットを計算する。マッチング理論やコンピュータ・ビジョンなどにおいて、いくつかのそうしたランダム化されたアルゴリズムが知られている。一例示的実施形態では、Karypis他によりグラフ区分化において実施されたヘビー・クリーク・マッチング・アルゴリズム（heavy cliquematching algorithm）の変形形態を使用する。これについては、Ｇ・カリピス（G.Karypis）他、「マルチレベル・ハイパーグラフ分割：ＶＬＳＩドメインにおける応用例（Multilevelhypergraph partitioning: Applications in VLSI domain）」、テクニカル・レポート（Tech. report）、ミネソタ州立大学コンピュータ・サイエンス学部（Universityof Minnesota, Department of Computer Science）、1997年、第３４回設計自動化会議（34th DesignAutomation Conference）における縮約版を参照されたい。
【００６４】
前述のスペクトル・アルゴリズムによって最も粗いグラフの各ノードの順序を確立した後で、元のグラフに至るまで中間グラフからなるシーケンスに次々とその順序を逆伝播する。一般に、次レベルのより微細なグラフの順序は、より粗いグラフの順序を順守しなければならない。より粗いグラフの各頂点は次レベルのより微細なグラフの多重頂点になるので、１レベル遡って射影することは、単に各多重頂点内の各頂点を順序付けすることに還元される。多重頂点が大きい場合は、スペクトル・アルゴリズムを使ってこの多重頂点の対応するノードを順序付けすることができる。ただし、この順序付けはそのグラフの残りの部分との関係において構築されなければならない。最適な結果は、このスペクトル・アルゴリズムの再帰的な適用を局所的精緻化ヒューリスティックと組み合わせることによって実現されることが分かった。一例示的手法は、公知のレイリー商反復法（Rayleigh Quotient Iteration）を使用することである。
【００６５】
図１０に、例を引いてこの多階層アルゴリズムを示す。この例では、７つのオブジェクト｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ｝を順序付けする必要がある。元のグラフＧ０を図の左側に示す。１つのノードは順序付けされる１つのオブジェクトを表す。１辺は連結された２つのノードの類似度を表す。上記で論じたように、類似の局所的構造を有するノードは、たとえばグラフＧ１などの粗いグラフにおける１つの多重頂点にマージされる。たとえば、｛Ａ，Ｂ，Ｃ｝および｛Ｄ，Ｅ，Ｆ｝は、多重頂点ＨおよびＧにそれぞれマージされる。次いで、局所的ヒューリスティックと共にスペクトル・アルゴリズムを使用して最も粗いグラフを順序付けする。この例では順序｛Ｇ，Ｊ，Ｈ｝を得る。最後に、すべての多重頂点を展開することによってこの結果を逆伝播する必要がある。この例では、Ｈに関連する｛Ａ，Ｂ，Ｃ｝と、Ｇに関連する｛Ｄ，Ｅ，Ｆ｝をさらに順序付けする必要がある。これは、本発明のスペクトル・アルゴリズムを適用することによって実施することができる。最終的な結果は｛Ｇ，Ｆ，Ｄ，Ｅ，Ａ，Ｂ，Ｃ｝である。
【００６６】
前述の本発明の順序付けの粗略化および精緻化を実施するために使用する方法の実際の選択は用途に応じてなされることを理解されたい。したがって、本明細書中の教示によれば、当分野の技術者はさまざまな用途に応じた実装形態を実現するであろう。
【００６７】
次に図１１を参照すると、本発明の順序付けアルゴリズムの１つまたは複数を実装するための例示的なコンピュータ・システムを示す構成図が示されている。このコンピュータ・システムは、メモリ７０４および入出力装置７０６に作用するように結合されたプロセッサ７０２を含むことができる。本明細書で使用する「プロセッサ」という用語は、たとえば、１つのＣＰＵ（中央処理装置）またはその他の処理回路あるいはその両方を含むものなど、任意の処理装置を含むものであると理解されたい。本明細書で使用する「メモリ」という用語は、たとえば、ＲＡＭ、ＲＯＭ、固定記憶装置（ハード・ドライブなど）、取り外し可能記憶装置（ディスケットなど）、フラッシュ・メモリなど、プロセッサまたはＣＰＵに関連するメモリを含むものである。さらに、本明細書で使用する「入出力装置」という用語は、たとえば、処理装置にデータを入力するための１つまたは複数の入力装置（キーボード、マウスなど）、または処理装置に関連する結果を提示するための１つまたは複数の出力装置（ＣＲＴディスプレイ、プリンタなど）またはエンド・ユーザ向けグラフィカル・ユーザ・インタフェースあるいはその両方、あるいは入力装置と出力装置の両方を含むものである。たとえば、本発明の順序付けアルゴリズムに従って生成される視覚化をエンド・ユーザが見るためのものをディスプレイとすることができる。また、「プロセッサ」は複数の処理装置を指すことができ、処理装置に関連するさまざまな要素を他の処理装置と共用することができる。
【００６８】
したがって、本明細書に記載する、本発明の方法を実施するための命令またはコードを含むソフトウェア・コンポーネント（たとえば、１つまたは複数のプログラム）を、製造品として１つまたは複数の関連する記憶装置（たとえば、ＲＯＭ、固定または取り外し可能メモリ）に記憶しておき、利用しようとするときに、一部または全部を（ＲＡＭなどに）ロードし、プロセッサによって実行させることができる。したがって、好ましくは、図１１に示すハードウェア実装形態、ならびに図２から図５に示す視覚化システムの各要素を使って順序付けエンジン２４０を実装することができ、そこで、本発明の１つまたは複数の順序付けアルゴリズムを用いることができることを理解されたい。
【００６９】
以上、本明細書において添付の図面を参照して本発明の例示的実施形態を説明してきたが、本発明はそれらの通りの実施形態に限定されるものではなく、本発明の範囲または精神を逸脱することなく当分野の技術者が本発明においてさまざまな他の変更および改変を加えることができることを理解されたい。
【図面の簡単な説明】
【００７０】
【図１】ｙ軸がホストＩＤ（識別子）を表し、ｘ軸が時間を表し、ホストＩＤがランダムに割り当てられる散布図である。
【図２】一般的な視覚化システムを示す構成図である。
【図３】データ処理の一部として本発明による順序付け機構を使用するシステムを示す構成図である。
【図４】データ管理の一部として本発明による順序付け機構を使用するシステムを示す構成図である。
【図５】ビューアの一部として本発明による順序付け機構を使用するシステムを示す構成図である。
【図６】本発明の一実施形態による順序付け用スペクトル・アルゴリズムを示す流れ図である。
【図７】ｙ軸がホストＩＤ（識別子）を表し、ｘ軸が時間を表し、本発明の一実施形態による順序付け用スペクトル・アルゴリズムに従ってホストＩＤが割り当てられる散布図である。
【図８】本発明の一実施形態による、複数の属性を処理する順序付け用スペクトル・アルゴリズムを示す流れ図である。
【図９】本発明の一実施形態による、大規模なデータ・セットを処理する順序付け用多階層スペクトル・アルゴリズムを示す流れ図である。
【図１０】本発明の一実施形態による順序付け用多階層スペクトル・アルゴリズムの結果の一例を示す図である。
【図１１】本発明による１つまたは複数の順序付けアルゴリズムと共に使用するためのハードウェア実装形態の例を示す図である。
【図１】
2004532453.tif 000008
【図２】
2004532453.tif 000009
【図３】
2004532453.tif 000010
【図４】
2004532453.tif 000011
【図５】
2004532453.tif 000012
【図６】
2004532453.tif 000013
【図７】
2004532453.tif 000014
【図８】
2004532453.tif 000015
【図９】
2004532453.tif 000016
【図１０】
2004532453.tif 000017
【図１１】
2004532453.tif 000018
【国際公開パンフレット】
2004532453.tif 000019
2004532453.tif 000020
2004532453.tif 000021
2004532453.tif 000022
2004532453.tif 000023
2004532453.tif 000024
2004532453.tif 000025
2004532453.tif 000026
2004532453.tif 000027
2004532453.tif 000028
2004532453.tif 000029
2004532453.tif 000030
2004532453.tif 000031
2004532453.tif 000032
2004532453.tif 000033
2004532453.tif 000034
2004532453.tif 000035
2004532453.tif 000036
2004532453.tif 000037
2004532453.tif 000038
2004532453.tif 000039
2004532453.tif 000040
2004532453.tif 000041
2004532453.tif 000042
2004532453.tif 000043
2004532453.tif 000044
2004532453.tif 000045
2004532453.tif 000046
2004532453.tif 000047
2004532453.tif 000048
2004532453.tif 000049
2004532453.tif 000050
2004532453.tif 000051
【国際公開パンフレット（コレクトバージョン）】
2004532453.tif 000052
【国際調査報告】
2004532453.tif 000053
2004532453.tif 000054