(57)【特許請求の範囲】
【請求項１】
コンピュータが、Ｎ次元空間に属する複数のアイテムと、前記Ｎ次元空間の各次元にそれぞれ対応する少なくともＮ個の写像変数と、をメモリに記憶し、
前記コンピュータが、前記複数のアイテムを、前記Ｎ次元空間から２次元空間への第１写像または前記Ｎ次元空間から３次元空間への第２写像によって、前記２次元空間又は前記３次元空間に属する複数の像としてディスプレイ上に表示し、
Ｎは３より大きく、
前記第１写像および第２写像は、それぞれ、前記少なくともＮ個の写像変数を含み、
明確さの尺度は、前記２次元空間または前記３次元空間において、（ｉ）同一のグループに関連付けられるグループ化された前記複数の像の間の第１距離、（ｉｉ）異なるグループに関連付けられるグループ化された前記複数の像の間の第２距離を含み、
前記コンピュータが、前記第１距離の減少および前記第２距離の増大の少なくとも一方が実現されるように、前記少なくともＮ個の写像変数のうち、少なくとも１つの写像変数を自動的に調整することによって、前記複数の像の少なくとも１つのグループの前記明確さの尺度を改善し、
前記コンピュータが、前記複数のアイテムを、自動的に調整された前記写像変数に基づいて更新された前記第１写像または前記第２写像によって更新された前記複数の像として、前記ディスプレイ上に再表示する、
クラスタリング方法。
【請求項２】
前記第１写像または前記第２写像の前記少なくとも１つの写像変数が、調整可能であるものとして表され、
前記第１写像または前記第２写像の前記少なくとも１つの写像変数が、固定であるものとして表され、
前記コンピュータが、固定であるものとして表される前記少なくとも１つの写像変数を調整することなく、調整可能であるものとして表される前記少なくとも１つの写像変数を自動調整し、
前記コンピュータが、前記少なくとも１つの写像変数が固定であるか、または調整可能であるかを選択するユーザ入力値と、前記複数の像が属する少なくとも１つのグループを定義するユーザ入力値と、を含む前記少なくとも１つの写像変数に関するユーザ入力値を受信する、
請求項１に記載のクラスタリング方法。
【請求項３】
前記コンピュータが実行する前記ディスプレイ上での前記複数の像の表示および再表示は、
前記複数のアイテムの、前記２次元空間の上のスター座標への前記第１写像による第１の像を表示することと、
前記複数のアイテムの、前記３次元空間の上の球面座標への前記第２写像による第２の像を表示することと、
前記複数のアイテムの、前記第１の像又は前記第２の像のいずれかを選択的に表示することと、
のいずれかである、請求項１に記載のクラスタリング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
以下は、情報技術分野に関し、さらに詳細には、クラスタリング、カテゴリ分類および関連技術に関する。
【背景技術】
【０００２】
アイテムのクラスタリングは、情報技術において一般的なタスクである。種々のアプリケーションにおける「アイテム」なる語は、文書、画像、データエントリ、音声ファイルまたはコンテンツ、サウンドドラックを伴う、または伴わない映像ファイルまたはコンテンツ、インターネットのＵＲＬ、ローカルエリアネットワーク（ＬＡＮ）のコンテンツ、ハードドライブまたは他の格納媒体などを指しうる。各アイテムは、複数の次元の情報によって特徴付けられる。各次元は、グループ化されることになっているアイテムを記述する特徴を指す。１つの手法において、グループ化されることになっているアイテムは、列が個別のアイテムに対応し、行が次元に対応する（またはその逆）表状の形態に表現され得る。半教師付きクラスタリングまたは教師付きクラスタリング（後者は、カテゴリ分類と呼ばれることもある）において、一部またはすべてのアイテムが、クラスまたはグループラベルまたは注釈を有しうる。クラスタリングアルゴリズムは通常、類似性の何らかの表示に基づいて「似ているアイテム」のグループにアイテムを割り当てる。データ集合は、アイテムの数、次元の数またはその両方の点に関して大きい可能性がある。
【０００３】
自動化クラスタリング用の既存のアルゴリズムには、Ｋ−平均法およびその変形、主成分分析、フィッシャー判別分析など挙げられる。既存の自動化クラスタリングアルゴリズムは、理想的に望ましいものより堅牢さに欠け、不規則な形状のグループ化または他の任意の形状のグループ化のために不十分な結果を生成することがある。既存の自動化クラスタリングアルゴリズムにおけるユーザインタラクションもまた、通常は初期状態のユーザ選択に制限される。自動化クラスタリングアルゴリズムが不十分な結果を生成する場合には、ユーザの唯一のオプションは、最初から異なる初期状態を用いて、自動化クラスタリングをリスタートすることであってもよい。
【０００４】
これらの困難さに関して、手動クラスタリングが用いられることがある。人間行為者による手動クラスタリングは、労働集約的であるという欠点を有し、結果の品質が、人間行為者の技能および労力に著しく左右される。一般に、人間行為者の場合には、有用なグループを識別するために、多数の次元を有する多数のアイテムによってソートすることが困難である。
【０００５】
第３の手法は、対話型視覚クラスタリングである。これらの手法において、アイテムのＮ次元収集（Ｎは、アイテムを特徴付ける際に用いられる次元の数である）が、人間行為者によってさらに容易に視覚化される２次元空間または３次元空間に写像される。写像は、２次元写像または３次元写像において視覚的に認識可能なグループ化を生成するために、人間行為者によって調整され得る写像変数を使用する。この手法の例は、スター座標視覚クラスタリング法であり、各次元は、選択された角度（θによって示される）および単位長さ（αによって示される）を含む写像変数を用いて２次元写像空間に写像される。次元値（ｘ1p，ｘ2p，．．．，ｘNp）を有するＮ次元空間におけるアイテムＰは、２次元スター座標空間における原点から始め、形式［（αi・ｘip・ｃｏｓ（θi）），（αi・ｘip・ｓｉｎ（θi））］Tのベクトルを加算することによって、２次元スター座標空間における点Ｑ（ｘ，ｙ）に写像される。式中、θiおよびαiはｉ次元の写像変数であり、ｘipはアイテムＰのｉ次元の値であり、ベクトルの和はＮ次元の場合にはｉ＝［１，．．．，Ｎ］に関する。
【０００６】
対話型視覚クラスタリングは、アイテムの適切なグループ化を識別する際に、人間行為者を支援するための機構を提供する。例えば、スター座標視覚化において、略同一の角度θの値を有する２次元は一般に、共に統合される。他方、αの値を調整することは、対応する次元の視覚化に対する寄与を制御する。θおよびαの変数に変更を加えるときには、候補グループのアイテムは、候補グループの視覚的追跡を可能にする特徴的な色または形状によって示すことができる。
【特許文献１】米国特許第６３８０９３７号明細書
【特許文献２】米国特許第６５６２０７７号明細書
【特許文献３】米国特許第６７２８９３２号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００７】
対話型視覚クラスタリングは、手動クラスタリングに対する補助であり、したがって、同一の欠陥を保持する。この手法は、依然として労働集約的であり、結果の品質が、人間行為者の技能および労力に依然として左右される。対話型視覚化は、有用なグループ化を識別するために、アイテムによってソートする際に人間行為者を支援する。しかし、対話型視覚クラスタリングの支援がある場合であっても、多数のアイテム、次元またはその両方を扱うことは依然として困難である。視覚化のθ変数とα変数との間の連係およびアイテムの次元は、把握することが困難である可能性がある。したがって、人間行為者にとって、視覚化における特定のグループを明確にするために、写像変数をどれほど最適に調整するかは明確ではない可能性がある。
【課題を解決するための手段】
【０００８】
本願明細書における例示の実施例として開示された一部の例示の実施形態において、１つまたは複数の格納媒体は、クラスタ化されることになっているアイテムのＮ次元から２次元または３次元への写像を表示するために実行可能であり、Ｎが３より大きく、写像がＮ次元の写像変数を有する視覚写像ソフトウェアと、２次元写像または３次元写像におけるアイテムの１つまたは複数のグループの明確さの尺度を改善するために、少なくともいくつかの写像変数を自動的に調整するように構成される自動化調整ソフトウェアと、を含むソフトウェアを格納する。
【０００９】
本願明細書における例示の実施例として開示された一部の例示の実施形態において、クラスタリングシステムは、クラスタ化されることになっているアイテムのＮ次元から２次元または３次元への写像を表示するように構成され、Ｎが３より大きく、写像がＮ次元の写像変数を有する視覚写像サブシステムと、写像変数に関してユーザ入力値を受信するように構成され、ユーザ入力値が、選択された写像変数が固定であるか、または調整可能であるかを選択し、ユーザ入力値が選択されたグループと選択されたアイテムを関連付けるユーザインターフェイスサブシステムと、２次元写像または３次元写像におけるアイテムの１つまたは複数のグループの明確さの尺度を改善するために、固定された写像変数を調整することなく、調整可能な写像変数を調整するように構成される調整サブシステムと、を備える。
【００１０】
本願明細書における例示の実施例として開示された一部の例示の実施形態において、クラスタリング方法は、クラスタ化されることになっているアイテムのＮ次元から２次元または３次元への写像を表示し、Ｎが３より大きいことと、クラスタ化されることになっているアイテムの選択されたアイテムのグループ化して、アイテムの１つまたは複数のグループを定義することと、２次元写像または３次元写像におけるアイテムの１つまたは複数のグループの明確さの尺度を改善するために、少なくとも１つの写像変数を調整するように自動化調整アルゴリズムを適用することと、調整された写像変数を用いてクラスタ化されることになっているアイテムの更新されたＮ次元から２次元または３次元への写像を表示することと、を含む。
【発明を実施するための最良の形態】
【００１１】
図１を参照すると、クラスタリングシステムは、少なくとも１つのプロセッサを有するコンピュータ１０と、グラフィカルディスプレイ１２と、キーボード１４およびマウス１６を含むユーザ入力デバイスと、１つまたは複数の格納媒体２０と、を含み、格納媒体は図１において図式的に示される。コンピュータ１０の少なくとも１つのプロセッサは、図１には示されていない。いくつかの適切なプロセッサとしては、シングルコア、デュアルコア、クアドコアまたは別様に構成されるマイクロプロセッサ、マイクロコントローラなどが挙げられる。示されたグラフィカルディスプレイ１２は、液晶ディスプレイ（ＬＣＤ）、プラズマディスプレイ、陰極線管（ＣＲＴ）ディスプレイ、投影型ディスプレイなどであってもよい。ユーザ入力デバイス１４、１６は、例示の実施例であり、薄膜キーパッド、トラックボール、タッチパッド、音声認識入力などの他のユーザ入力デバイスによって補足または置換され得る。
【００１２】
１つまたは複数の格納媒体２０としては、ランダムアクセスメモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、ハードディスク、光学ディスクなどを挙げることができる。１つまたは複数の格納媒体２０は、クラスタ化されることになっているアイテム２２および写像変数２４の表現を含むデータを格納する。アイテム２２の表現は、例えば、行（または列）がアイテムを表し、列（または行）が次元を表す表状の表現をはじめとする実質的に任意のフォーマットをとることができる。アイテム２２の表現は、関係データベース表、スプレッドシート表などの形態をとることができる。アイテム自体は、１つまたは複数の格納媒体２０に格納されてもよく、格納されてなくてもよい。例えば、一部の実施形態において、アイテムは、ハードディスクに格納されるファイルであってもよく、アイテム２２の表現は、これもハードディスクに格納されるアイテムの指数であってもよい。他の実施形態において、アイテムは、ＵＲＬアドレスによって表現されるウェブサイトであってもよく、１つまたは複数の格納媒体２０は、それ自体はウェブサイトを格納しないサーチエンジンサーバである。一部の実施形態において、アイテム２２の表現はまた、アイテム自体を含むことも検討され、種々の次元の値は、使用時にアイテムから計算されるか、または種々の次元の値は、アイテムに注釈または他の方法で関連付けられる。アイテム２２の表現は、本願明細書ではいくつかの場所にあり、さらにコンパクトにアイテム２２と呼んでもよい。しかし、アイテムの表現を格納し、各アイテムの次元の値を格納または容易に導出することができるほど十分であることは理解すべきである。アイテム２２は、グループ識別またはラベルによって部分的または全体的に注釈を付けてもよい。通常の手法において、アイテム２２は、最初はラベル付けされていないか、または少数のアイテムのみがラベル付けされる。クラスタリングが進むと、追加のラベルが加えられて、アイテム２２を関心がある一定の次元に関して類似の値などの類似性を有するグループにクラスタ化するラベル付けを決定するために、妥当性の検査がなされる。注釈は、アイテムの表状表現の列に適切に格納される。アイテムの表現がアイテム自体を含む場合には、アイテム自体がグループラベルによって注釈され得る。
【００１３】
写像変数２４は、Ｎ次元から２次元または３次元への視覚写像サブシステムソフトウェア３０によってアクセスまたは用いられる。本願明細書で用いられるとき、「ソフトウェア」なる語は、ソフトウェアの目的であるタスクを実行するようにコンピュータまたは他のディジタルシステムを構成するために、コンピュータまたは他のディジタルシステムによって実行可能な命令の集まりまたは集合を包含することを意図している。本願明細書で用いられるとき、「ソフトウェア」なる語は、ＲＡＭ、ハードディスク、光学ディスクなどの格納媒体に格納されるそのような命令を包含することを意図し、ＲＯＭなどに格納されるソフトウェアであるいわゆる「ファームウェア」を包含することも意図している。そのようなソフトウェアは、種々の態様で体系化されてもよく、ライブラリとして体系化されたソフトウェア構成要素、リモートサーバなどに格納されるインターネットに基づくプログラム、ソースコード、解釈コード、目的コード、直接的に実行可能なコードなどを含んでもよい。
【００１４】
本願明細書で用いられるとき、「システム」および「サブシステム」なる語は、例えば、アナログ、ディジタルまたは混合したアプリケーション特有の集積回路（ＡＳＩＣ）などのハードウェアとして純粋に具体化されるシステムおよびサブシステム、図１に示されているようなシステムなどのコンピュータまたは他のディジタルデバイスなどのハードウェアおよび上記のハードウェアで実行可能なソフトウェアの組み合わせとして具体化されるシステム、またはそのようなシステムおよびサブシステムの組み合わせを包含することを意図している。したがって、例えば、コンピュータ１０およびコンピュータ１０で実行できる視覚写像サブシステムソフトウェア３０は、共に、視覚写像サブシステムを定義する。さらに、本願明細書で用いられるとき、機能を「実現することを実行可能にするソフトウェアを格納する格納媒体」なる言い回しは、上記の機能を実現するために、コンピュータまたは他のディジタルデバイスで実行可能なソフトウェアを格納する任意の格納媒体を包含することを意図している。適切な格納媒体の例としては、ＲＡＭ、ＲＯＭ、ハードディスク、光学ディスク、ウェブに基づくサーバなどが挙げられる。
【００１５】
図１の例示のクラスタリングシステムは、他のクラスタリングタスクを行うための他のサブシステムを含む。次元選択サブシステムソフトウェアは、例示の実施例において、次元選択サブシステムソフトウェア３２を共に備えたコンピュータ１０として具体化される。次元選択サブシステムソフトウェアは、例示の実施例において、次元選択サブシステムソフトウェア３２を共に備えたコンピュータ１０として具体化される。ユーザインターフェイスサブシステムソフトウェアは、例示の実施例において、ユーザインターフェイスサブシステムソフトウェア３４を共に備えたコンピュータ１０として具体化される。自動化写像変数調整サブシステムは、例示の実施例において、自動化写像変数調整サブシステム３６を共に備えたコンピュータ１０として具体化される。他の実施形態において、クラスタリングシステムは、追加のサブシステムまたは他のサブシステムを含んでもよく、種々のサブシステムは、さまざまに集積または体系化され得る。さらに、一定のサブシステムは、一部の実施形態において、省略されてもよい。例えば、次元選択サブシステムは、省略されてもよく、そのような場合には、アイテムのすべての次元がクラスタリングに用いられるか、またはユーザインターフェイスサブシステムによってユーザによって選択された次元が、クラスタリングに用いられる。
【００１６】
実施例として本願明細書に示された図１のクラスタリングシステムにおいて、視覚写像サブシステムは、クラスタ化されることになっているアイテム２２のＮ次元から２次元スター座標への写像をディスプレイ１２に表示するように構成され、Ｎは３より大きく、写像はＮ次元に関して示されたθおよびαのスター座標写像２４を有する。例示の図１において、写像変数２４は、Ｎ次元に対応するＮ列および５行、すなわち（ｉ）１〜Ｎまで続く次元指数、（ｉｉ）°(degree)の単位で指定されるθ写像変数に関する値、（ｉｉｉ）θ写像変数が固定であるかどうか（他のオプションは調整可能である）を示すブール変数、（ｉｖ）α写像変数に関する値および（ｖ）α写像変数が固定であるかどうかを示すブール代数を有する表として図式的に示されている。他の実施形態において、例えば、平行移動スケーリング変数α（スター座標写像サブシステムのα変数に対応する）および２つの角度変数θおよびφを含む写像変数が球面座標を含みうる楕円３次元写像サブシステムなどの他の視覚写像サブシステムが使用されてもよい。視覚写像サブシステムソフトウェア３０は、個別のアイテムを表現するために、通常、黒丸、白丸、黒四角、白四角などの記号を用いて、ディスプレイ１２に２次元または３次元への写像のグラフィカルレンダリングを可能にするのに十分なコードを含む。３次元写像の場合において、表示される写像は、３次元レンダリングおよび任意に３次元レンダリング空間によるユーザ選択スライスを含むことができる。表示される写像は、写像による投影または線に沿った位置に対するアイテムの密度のプロットなどの写像の部分の他の表現を任意に含む。一部の実施形態において、２次元または３次元への写像のグラフィカルレンダリングを可能にするのに十分なコードは、写像ディスプレイのラスタ化などの一定の機能を実現するためにダイナミックリンクライブラリ（ＤＬＬ）または他のシステムレベルソフトウェアへのコールを含みうる。さらに一般的には、ソフトウェア３０、３２、３４、３６のいずれも、システムレベルのコードまたは一定の機能を実現するためにサーバまたは他の位置に存在する他のソフトウェアへのコールを呼び出しうる。
【００１７】
図１を引き続き参照し、さらに図２を参照すると、図１の例示のクラスタリングシステムによって適切に行われるクラスタリング方法が、記載される。初期プロセス操作４０において、次元選択サブシステムは、クラスタ化されることになっているアイテム２２を特徴付ける次元のより大きな集合からクラスタリングのために用いられるＮ次元を選択するために任意に呼び出される。アイテム２２が多数の次元によって特徴付けられる場合には、クラスタリングにおいてより少ない関連する次元を用いないことが好都合である場合がある。手動の手法において、ユーザは、１つまたは複数の次元を手動によって選択または非選択を行うことができる。他の実施形態において、次元選択サブシステムは、自動的に次元選択を行うために呼び出される。例えば、主成分分析（ＰＣＡ）は、線形的な態様でアイテム２２の次元数を減少させるために用いることができる。ＰＣＡ手法は、共分散行列の固有値によって（または線形変換後の初期データにおける「広がり」によって）次元をランク付け、上位ランクの次元を選択可能にする。別の手法において、フィッシャー判別分析（ＦＤＡ）は、線形的な態様で次元を減らすために用いることができる。別の手法において、次元とクラスラベルとの間の非線形的なエントロピーに基づくインタラクションが、次元をランク付けるために用いることができる。他の次元選択技術もまた、用いることができる。アイテム２２の表現に注釈をつけるいくつかの初期のグループラベルがある場合には、ＦＤＡまたは他の次元削減アルゴリズムは、Ｎ次元を選択する際に、そのようなグループ化を任意に利用することができる。
【００１８】
視覚化操作４２において、視覚写像サブシステムは、クラスタ化されることになっているアイテム２２のＮ次元から２次元または３次元への写像を表示するために呼び出される。図２において、スター座標写像は、２次元スター座標位置Ｑ（ｘ，ｙ）に写像される１つのアイテムＰ（ｘ1，ｘ2，ｘ3，ｘ4，ｘ5，ｘ6）（この例ではＮ＝６）に関して図式的に示した操作４２の挿入物において示されている。クラスタリングに関して、一般に多くのアイテムがあり、したがって、スター座標視覚写像において多くの点Ｑがある。さらに、Ｐ（ｘ1，ｘ2，ｘ3，ｘ4，ｘ5，ｘ6）からＱ（ｘ，ｙ）に写像するために、２次元写像空間において共に追加されるベクトルは、例示の目的のために、図式的に示した操作４２の挿入物において示されているが、アイテム２２の反復的視覚（例えばスター座標）写像において通常は示されない。Ｎ次元を有する点Ｐからスター座標空間における点Ｑ（ｘ，ｙ）への例示のスター座標写像は、
【００１９】
【数１】
0005294738.tif 000002
【００２０】
によって与えられる。式中、θiおよびαiはｉ次元のスター座標写像変数であり、Ｎは次元数であり、ｘipはアイテムＰのｉ次元の値である。式（１）は、スター座標空間の中心が（０，０）であると仮定する。
【００２１】
写像変数２４は通常、適切な値に初期化される。スター座標を使用する一部の実施形態において、写像変数の初期値は、すべての次元に関してαi＝１であり、次元指数ｉが１〜Ｎまで続く場合には、θi＝３６０・（ｉ−１）／Ｎであり、θiの単位は°(degree)である。例えば、Ｎ＝２４の場合には、最初に、θ1＝０°，θ2＝１５°，．．．，θ24＝３４５°である。ランダム化された初期化をはじめとする他の初期化が検討される。
【００２２】
人間行為者、すなわちユーザは、操作４２によって示されるクラスタ化されることになっているアイテムのグラフィカル表示されたＮ次元から２次元または３次元への写像を再検討することができる。ユーザは、どのように進めるかについて、操作４４で決定を行う。
【００２３】
第１の決定経路５０において、ユーザは、クラスタリングプロセスを前に進めるために、１つまたは複数の操作を行うことを選ぶ。ここで、ユーザは、１つまたは複数の写像変数２４の手動調整、固定または調整可能などの１つまたは複数の写像変数２４の選択、１つまたは複数のアイテム２２に関するグループ注釈の追加、消去または修正など、操作５２において１つまたは複数の変更を行うために、ユーザインターフェイスサブシステムを使用する。一部の実施形態において、ユーザは、写像変数が固定であると設定するか、または調製可能であると設定するかに関係なく、写像変数を手動で調整することができる。そのような実施形態において、「固定された」設定は、自動化写像変数調整サブシステムによって行われる自動化調整にのみ影響を及ぼす。他の実施形態において、ユーザは、固定された写像変数を手動で調整することができない。選択された写像変数の手動調整を行う（すなわち、スター座標視覚化を使用する例示の実施形態において、１つまたは複数のθ変数および／またはα変数を調整する）ことによって、ユーザは、写像における一定の次元の影響を強調または低減することができるか、または一定の次元を共に統合させることができる。α変数を調整することは、スター座標写像におけるスケーリング変換を生成し、ユーザに対応する次元軸の長さを変更させ、したがって、スター座標視覚化における対応する次元の寄与を増大または減少させることができる。θ変数を調整することは、回転変換を生成し、スター座標視覚化における次元軸の方向を修正し、したがって、対応する次元を他の次元と多少、相関させる。例えば、多次元が略同一の方向の点（すなわち類似のθが割り当てられる）まで回転される場合には、次元の寄与は、視覚化において効率的に統合される。結果として、これらの変換は、スター座標視覚化においてアイテムの配置図の再構成を提供する。さらに、選択されたアイテムにグループ注釈を追加することによって、ユーザは、スター座標写像におけるアイテムに対応する記号に印を付けることができる。視覚写像サブシステムは、アイテムのグループを示すために、少なくとも１つの形状および色によってコード化される記号によって表現されるアイテムによって写像を表示する。これにより、ユーザが、次のα変換およびθ変換においてグループのアイテムを追跡することを可能にする。これは、変換の結果としての新たな変数の元で、クラスタがどのように再配分されるかを調べるのに有用である。一部の実施形態において、ユーザインターフェイスサブシステムは、アイテムの選択されたグループの少なくとも１つのアイテムを含む２次元または３次元の点または部分のユーザ入力による記述の受信を可能にする。例えば、ユーザは、グループに追加されることになっているアイテムを表現する点の周囲の包含ループを描画してもよい。
【００２４】
例示の第１の決定経路５０において、ユーザはまた、クラスタリングの特徴の妥当性を検査するために妥当性検査操作５４を行うことを選ぶことができる。例えば、ユーザは、アイテムの類似性の定量的な尺度を得るために、グループのアイテムに関して相関計算を計算することができる。一部の実施形態において、妥当性検査操作５４は、省略される。
【００２５】
一旦、ユーザが第１の決定経路５０を介して所望の手動変更を行うと、プロセスは、アイテム２２の更新される２次元または３次元視覚写像を提供するために、図形レビュー操作４２に戻る。ユーザは、さらなる手動変更を行い、したがって、写像を反復的に改善し、グループの識別、ラベル付けおよび妥当性検査を行うために、第１の決定経路５０を再び選択することができる。
【００２６】
単独で操作を行う手動の第１の経路５０は、労働集約的であり、人間行為者の技能および労力に左右されるという欠点を有する。したがって、ユーザは、選択されてもよい第２の決定経路６０を備える。第２の決定経路６０は、自動化経路である。ユーザインターフェイスサブシステムは、ユーザが固定または調整可能であるものとしての写像変数の指定を更新可能にするために、操作６２を再び呼び出す。（一部の実施形態において、操作６２は、省略され、手動検査経路５０は、そのような更新を行うために用いられる）。操作６４において、調整サブシステムソフトウェア３６を含む調整サブシステムは、調整可能な写像変数を調整するために呼び出されるが、２次元または３次元写像におけるアイテムの１つまたは複数のラベル付けされたグループの明確さの尺度を改善するために、固定された写像変数を調整することはない。一部の実施形態において、写像変数の自動化調整操作６４は、反復プロセスである。自動化調整操作６４は、前の選択動作６２において行われるように固定された写像変数および調整可能な写像変数の選択を除き、ユーザインタラクションを呼び出さない。自動化調整操作６４が終了すると、プロセスは、所定の場所における自動化調整６４中に行われた写像変数に対する修正によって、アイテム２２の更新された２次元または３次元視覚写像を提供するために、図形レビュー操作４２に戻る。ユーザが自動化調整の結果に完全に満足していない場合には、ユーザは次に、さらなる変更を手動で行うために、手動の第１の決定経路５０を選択することができる。さらにまたはあるいは、ユーザは、別の自動化調整を開始するために、恐らく、固定された写像変数および調整可能な写像変数の異なる選択によって、自動化された第２の決定経路６０を再び選択することができる。
【００２７】
このように、ユーザは、第１の決定経路５０による手動調整と、第２の決定経路６０による自動化調整との間で必要に応じて交替し、クラスタリングを反復的に行うことができる。この手法は、ユーザの介入を制限または削減する既存の自動化クラスタリング技術と、労働集約的であり、ユーザの技能および専門知識に大きく左右される手動の反復的視覚クラスタリング技術と、に関する大きな改善である。図１および図２の手法は、自動化経路６０による自動化方法の速度および使いやすさに関して、利点を提供する。同時に、自動化クラスタリングの欠点は、ユーザが一定の写像変数を固定であると設定し、ユーザが適切であると考えるときに、追加の手動調整を行うことによって、自動化クラスタリングを制限することを可能にする手動経路５０を介して克服される。
【００２８】
図１および図２の手法の利点は、労働集約的であり、技能に左右されるという欠点を被る手動の反復的視覚クラスタリング技術と比較することによっても分かる。手動経路５０に加えて、自動化経路６０を提供することによって、クラスタリングの労働集約性は、著しく低減される。自動化クラスタリングは、最初は、調整可能に残した写像変数の大部分またはすべてに関して用いることができる。この初期の自動化クラスタリングは、デフォルトの初期写像変数値によって、または写像変数値のランダム化された初期化によって達成されるより実質的によい結果に到達する可能性が高く、したがって、手動クラスタリングの早期段階において通常必要な多数の試行およびエラーを削減する。ユーザは次に、この初回通過自動化結果を調整して改善するために、手動経路５０を使用することができる。ユーザが行き詰まるようになり、写像を改善する確率が高いさらなる手動調整を識別することができない場合には、この時点で、調整可能である状態で残った１つのみまたは少数の写像変数によって、ユーザが行き詰まらないようにするために、自動化写像からの支援を得るために、ユーザは、自動化経路６０を再び呼び出すことができる。したがって、経路５０による反復的視覚クラスタリングおよび経路６０による半自動化クラスタリングの混成した組み合わせが、いずれかの技術のみによって達成されるように実質的に高速で成功するクラスタリングを生成する相互作用を提供する。
【００２９】
各反復において、図形レビュー操作４２は、手動または自動的に調整される変数によって視覚写像を更新し、手動経路５０による任意の新たなグループラベル付けまたは更新されたグループラベル付けを組み込むために反復され、ユーザは決定要求４４によって再び提示される。ユーザは、すべてのアイテムまたは少なくとも関心のあるアイテムが、写像において適切であるように見え、任意に妥当性検査操作５４の妥当性検査判断基準を満たすグループに割り当てられるまで、必要に応じて手動経路５０または自動化経路６０を適用するための決定５０を行う。一旦、ユーザが満足すると、ユーザは、操作７２においてグループ化を格納させる出口経路７０を選択するか、または、他の出口操作に新たなグループ化によって、サーチエンジンデータベース、ハードディスク指数などの更新などを行わせる。
【００３０】
図１の例示のクラスタリングシステムおよび図２に示されるクラスタリングシステムを用いる例示の方法について記載したが、自動化写像変数調整サブシステムによって適切に行われる例示のプロセスが記載されている。好都合なことに、この調整が行われる。すなわち、この調整は、アイテムのＮ次元空間のより高い次元数ではなく、２次元または３次元写像空間において動作する。したがって、自動化写像変数調整サブシステムは、写像サブシステムによって行われるＮ次元から２次元または３次元への写像によって提供される次元の減少を活かし、開示された混成システムにおける対話型視覚クラスタリングの特徴および自動化クラスタリングの特徴との間の実質的に好都合な相互作用を再び実証する。
【００３１】
図３を参照すると、操作８０において、明確さの尺度が、２次元または３次元写像におけるアイテムの１つまたは複数のグループに関して計算される。明確さの尺度は、例えば、アイテムまたはグループラベルを有するアイテムの表現に注釈を付けることによって、グループに関連付けられているそれらのアイテムのみに基づいて計算される。一部の実施形態におけるグループの数は、１グループ程度に少なくてもよい。一部の実施形態において、明確さの尺度は、同一のグループに関連付けられるアイテムの２次元または３次元写像における類似性の尺度を組み込む。改善は、自動化された調整によって同一グループのアイテムの中で増大した類似性を示す類似性のこの尺度に対応する。さらにまたはあるいは、一部の実施形態において、一部の実施形態において、明確さの尺度は、異なるグループに関連付けられるアイテムの２次元または３次元写像における類似性の尺度を組み込む。ここでの改善は、自動化された調整によって異なるグループのアイテムの間で増大した相違点を示す相違点のこの尺度に対応する。少なくとも２つの異なるグループがある場合には、この相違点の尺度が適用可能である。
【００３２】
図３に示される反復的手法において、明確さの尺度の偏微分もまた、操作８２における調製可能な変数のそれぞれに対してそれぞれ計算される。偏微分は、調整操作８４において用いられ、スター座標写像の場合には固定されたθ変数およびα変数などの任意の固定された写像変数を調整することなく、計算された偏微分に基づいて、スター座標写像の場合には調整可能なθ変数およびα変数などの調整可能な写像変数を自動的に調整する。操作８４は、勾配降下法またはその変形、マルクワルトアルゴリズムなどの種々の反復的調整アルゴリズムを用いることができる。調整操作８４の生産量は、調整可能な写像変数の１つまたは複数に関する調整される値である。演算８６において、明確さの更新された尺度は、２次元または３次元写像におけるアイテムの１つまたは複数のグループに関して計算される。
【００３３】
ループ決定操作８８において、現在の反復が反復調整のための終了判断基準を満たしたかどうかが決定される。適切な終了判断基準は、例えば、初期操作８０と比べるか、または（後の反復において）前の反復の更新操作８６において達成される明確さの尺度と比較した更新操作８６において達成される明確さの尺度における改善を含みうる。別の適切な終了判断基準は、操作８４において決定された調整に関連してもよく、終了は、最大の割合の調整が連続反復に関する閾値の割合未満である場合に適切である。ループ決定操作８８が、反復的改善が続行すべきであると決定する場合には、流れは、新たな偏微分を計算するために、操作８２に戻るように移動する。ループ決定操作８８が、反復的改善が終了すべきであると決定する場合には、流れは、ユーザが調整された写像をレビュー可能にするために図２の図形レビュー操作４２に戻るように移動する。
【００３４】
図３を参照して適切な反復的調整アルゴリズムプロセスの流れについて記載したが、ここで、そのような反復的調整アルゴリズムにおいて用いられうる一部の例示の操作および尺度が、記載される。図３のアルゴリズムのほか、次に記載される例示の操作および尺度は、例示の実施例として提供され、他のプロセスの流れ、動作および尺度もまた、２次元または３次元写像空間における自動化調整操作６４を行う際に用いることができる。
【００３５】
以下の例示の操作および明確さの尺度において、少なくとも少量のグループラベル付けが、すでに行われたと仮定される。すなわち、グループ化されることになっているアイテム２２の少なくとも一部のアイテムは、グループと関連付けられているものとしてラベル付けされるか、またはラベル付けされたグループに属する一定の確率を有するものとしてラベル付けされるかのいずれかであるものとして仮定される。このグループラベル付けデータは通常、手動経路５０を介した１つまたは複数の前の反復によってもたらされるが、一部の実施形態において、初めに入力されたようなアイテム２２の表現は、グループラベル付け情報を含みうる。
【００３６】
１つの手法において、スター座標θおよびαに関する最適な投影距離測定基準は、３つ以上のクラスおよび１つの投影された次元に対するフィッシャー判別分析（ＦＤＡ）の一般化である正準変量を用いることによって、得ることができる。２次元投影に関する正準変量は、以下のように得ることができる。各クラスに関して、共分散行列Ｓkおよび平均μkが形成される。重み付け共分散行列Ｓは、以下のように定義される。
【００３７】
【数２】
0005294738.tif 000003
【００３８】
式中、Ｎkは、クラスまたはグループｋにおけるデータ要素の数であり、ｃは検討中のクラスまたはグループの総数である。データ集合の平均μおよび各クラスｋに関するμkを用いて、行列ＳBは、以下のように形成される。
【００３９】
【数３】
0005294738.tif 000004
【００４０】
２次元空間に投影するために、最適な投影行列Ｗは、Ｓ-1ＳBの２つの最初の固有ベクトルによって形成される。一旦、投影行列Ｗ＝｛ｗij｝（指数ｉ＝１，２および指数ｊ＝１，．．．，Ｎ）が得られると、行列式ＭT＝Ｗは、以下の形態で、要素に関する分解によって解かれる。
【００４１】
【数４】
0005294738.tif 000005
【００４２】
ｗi1およびｗi2がいずれもゼロでない場合には、θiおよびαiに関する一意の解が存在する。特に、
【００４３】
【数５】
0005294738.tif 000006
【００４４】
である。ｗi1＝０であり、ｗi2がゼロに等しくない場合には、θiはπ／２に設定される。θi＝０である場合には、αiの値は、以下のように与えられる。
【００４５】
【数６】
0005294738.tif 000007
【００４６】
言い換えれば、投影行列Ｗが０列を有していない場合には、スター座標視覚化に関してθおよびαの一意の集合に対応する。この手法の欠点は、写像変数を計算するために、Ｎ次元空間において操作することである。結果として、Ｓ-1ＳBに関する固有ベクトルを得ることは、大きな集合の次元、すなわちＮの大きな値に関して計算に費用がかかる可能性がある。また、この手法において、この場合には、明確さの尺度として機能する改善した投影距離測定基準を生じるために、調整は反復的ではなく、調整可能なθ写像変数およびα写像変数に関して調整される値が、非反復的に計算されることを留意されよう。
【００４７】
反復的である別の手法において、投影距離測定基準Ｍは、初期のＮ次元空間においてではなく、２次元スター座標写像空間におけるデータ集合を分離する明確さの尺度として求められる。以下の手法において、ガウス分布の仮定は、行われない。距離測定基準は、相違のあるアイテムの間の距離を増大させると同時に、類似のアイテムの間の距離を減少させようとする関数を最適化することによって、類似性および相違点のペアの集合から得られる。投影距離測定基準Ｍは、以下のように投影または写像される２次元スター座標空間における２つのアイテムｘ1，ｘ2の間の距離として適切に定義される。
【００４８】
【数７】
0005294738.tif 000008
【００４９】
以下において、集合Ｓの各要素が、同一のグループに関連付けられるアイテムのペアである場合には、類似性のペアの集合は、Ｓとして定義される。集合Ｄの各要素が、異なるグループに関連付けられるアイテムのペアである場合には、相違点のペアの集合もまた、Ｄとして定義される。１つの手法において、投影距離測定基準Ｍは、集合Ｓに基づく類似性の尺度および集合Ｄに基づく相違点の尺度を含む無制約最適化問題として公式化される。この手法において、類似性の尺度は、Ｉｎ（Ｍ）で表され、グループ内の項Ｉｎ（Ｍ）とも本願明細書では呼ばれ、以下によって与えられる。
【００５０】
【数８】
0005294738.tif 000009
【００５１】
同様に、相違点の尺度は、Ｅｘ（Ｍ）で表され、グループ内の項Ｅｘ（Ｍ）とも本願明細書では呼ばれ、以下によって与えられる。
【００５２】
【数９】
0005294738.tif 000010
【００５３】
明確さの尺度は、この実施例の場合にはＪ（Ｍ）と表され、グループ内の距離尺度Ｉｎ（Ｍ）の削減によって（すなわち、同一グループに関連付けられるアイテムの増大する類似性によって）、またはグループ内の距離尺度Ｅｘ（Ｍ）の増大によって（すなわち、異なるグループに関連付けられるアイテムの増大する相違点によって）、改善されるように構成される。Ｉｎ（Ｍ）の類似性の距離の項およびＥｘ（Ｍ）相違点の距離の項から構成され得る明確さの一部の例示の尺度は、以下を含む。
【００５４】
【数１０】
0005294738.tif 000011
【００５５】
【数１１】
0005294738.tif 000012
【００５６】
【数１２】
0005294738.tif 000013
【００５７】
【数１３】
0005294738.tif 000014
【００５８】
などである。
【００５９】
数式１０〜１３の任意の１つに記載される明確さの尺度は、図３に図式的に示される反復的調整方法における明確さの尺度として用いることができる。それを行うために、Ｊ（Ｍ）の偏微分が、調整可能な写像変数のそれぞれに対してそれぞれ操作８２において計算される。Ｉｎ（Ｍ）およびＥｘ（Ｍ）の両方が、計算可能な偏微分を有する。グループ内の差の項Ｉｎ（Ｍ）に関する偏微分を計算するために、ｋ＝１，２および指数ｌ＝１，．．．，Ｎであるとき、行列Ｍは、Ｍ＝｛ｍkl｝として適切に表現される。この代入によって、数式８は、以下のように書き直すことができる。
【００６０】
【数１４】
0005294738.tif 000015
【００６１】
式中
【００６２】
【数１５】
0005294738.tif 000016
【００６３】
である。要素に関する偏微分を得るために、対称条件βlnS＝βnlSは、
【００６４】
【数１６】
0005294738.tif 000017
【００６５】
を生じるように用いることができる。Ｅｘ（Ｍ）に関する偏微分は、類似の態様で容易に計算される。したがって、数式１０〜１３の任意の１つに記載される明確さの尺度Ｊ（Ｍ）に関して極小値を求め、その結果、調整可能な写像変数に関する改善した値を得るために、図３の反復方法は、操作８４において行われる勾配降下法または別の最小化アルゴリズムによって、用いることができる。
【００６６】
制約付き最適化手法において、明確さの尺度は、グループ内の距離の項Ｉｎ（Ｍ）のみとして解釈されるが、堅牢さを確保するために、１より大きいか、または１に等しいＥｘ（Ｍ）を必要とするように制約を加えられる。したがって、この場合には、最適化は、制約条件Ｅｘ（Ｍ）≧１を受けるＩｎ（Ｍ）を最小化する。
【００６７】
さらに例示の実施例として、制約付き最適化は、数式１０に記載される明確さの尺度Ｊ（Ｍ）を用いて行われるが、以下の制約条件を受ける。
【００６８】
【数１７】
0005294738.tif 000018
【００６９】
式中、Ｔthは、０と１の間の閾値である。この制約条件は、１つの次元のみに沿って広がる傾向があるθiの分布を考慮しない。
【図面の簡単な説明】
【００７０】
【図１】クラスタリングシステムを図式的に示す。
【図２】図１のクラスタリングシステムを用いて実行されるクラスタリング方法を図式的に示す。
【図３】図２の方法の自動調整構成要素の実施形態を図式的に示す。
【図１】
0005294738.tif 000019
【図２】
0005294738.tif 000020
【図３】
0005294738.tif 000021