(57)【要約】      （修正有）【課題】データが時間とともに相当に進展するときのクラスタの質を向上させる。【解決手段】データ・ストリームのデータのクラスタリングを行うテクニックが提供されている。最初に、データ・ストリームからオンライン統計が作成される。その後、オンライン統計のオフライン・プロセッシングが、オフライン・プロセッシングが必要であるか、あるいは望ましいときに行われる。オンライン統計は、データ・ストリームからのデータ・ポイントの受け取り、およびデータ・グループの形成ならびに更新を介して作成することができる。オフライン・プロセッシングは、サンプリングされたデータ・ポイントの周囲においてデータ・ポイントのグループの再クラスタリングによって行うことができ、新しく形成されたクラスタがレポートされる。【選択図】      図２
2005100363.tif 000002
【特許請求の範囲】
【請求項１】
データ・ストリームのデータのクラスタリングを行う方法であって：
前記データ・ストリームからオンライン統計を作成するステップ；および、
前記オンライン統計のオフライン・プロセッシングを、オフライン・プロセッシングが必要であるか、あるいは望ましいときに行うステップ；
を含む方法。
【請求項２】
さらに、オフライン・プロセッシングが必要であるか否か、あるいは望ましいか否かを決定するステップを含むものとする、請求項１に記載の方法。
【請求項３】
前記オンライン統計を作成するステップは：
前記データ・ストリームからデータ・ポイントを受け取るステップ；および、
前記データ・ストリームから前記オンライン統計を更新するステップ；
を含むものとする、請求項１に記載の方法。
【請求項４】
前記オンライン統計を更新するステップは：
前記データ・ポイントにもっとも近いデータ・ポイントのグループを見つけ出すステップ；
前記もっとも近いグループまでの距離がスレッショルドより大きいか否かを決定するステップ；
前記もっとも近いグループまでの前記距離が前記スレッショルドより大きい場合には、前記データ・ポイントを有する新しいグループを作成するステップ；
前記もっとも近いグループまでの前記距離が前記スレッショルドより小さい場合には、前記データ・ポイントを前記もっとも近いグループへ追加するステップ；および、
作成した場合には前記新しいグループの、あるいは前記データ・ポイントを追加した場合には前記もっとも近いグループの前記統計を更新するステップ；
を含むものとする、請求項３に記載の方法。
【請求項５】
前記オフライン・プロセッシングを行うステップは：
定義済みの数のデータ・ポイントをサンプリングするステップ；
前記サンプリングしたデータ・ポイントの周囲においてデータ・ポイントのグループの再クラスタリングを行うステップ；
サンプリングおよび再クラスタリングの追加の反復が必要であるか否かを決定するステップ；
追加の反復が必要である場合には、前記再クラスタリングを行ったデータ・ポイントのグループの中心軌跡として前記サンプリングしたポイントの再定義を行った後に、前記再定義を行った前記サンプリングしたポイントの周囲においてデータ・ポイントのグループの再クラスタリングを行うステップ；および、
前記再クラスタリングにおいて形成されたクラスタのレポートを行うステップ；
を含むものとする、請求項１に記載の方法。
【請求項６】
前記オフライン・プロセッシングを行うステップは、前記オンライン統計を使用してより高いレベルのクラスタを作成するステップを含むものとする、請求項１に記載の方法。
【請求項７】
前記オンライン統計は、より低いレベルのクラスタであるとする、請求項６に記載の方法。
【請求項８】
前記オンライン統計を使用してより高いレベルのクラスタを作成する前記ステップは、より低いレベルのクラスタの再クラスタリングを行うステップを含むものとする、請求項７に記載の方法。
【請求項９】
前記オフライン・プロセッシングを行うステップは、前記オンライン統計を使用してデータ・ストリームの進展をモニタするステップを含むものとする、請求項１に記載の方法。
【請求項１０】
前記オンライン統計を使用してデータ・ストリームの進展をモニタする前記ステップは、２つの異なる対象期間における前記オンライン統計を比較するステップを含むものとする、請求項９に記載の方法。
【請求項１１】
前記オンライン統計を使用してデータ・ストリームの進展をモニタする前記ステップは：
指定された対象期間に関してオンライン統計の減算を行うステップ；および、
前記減算後の統計に基づいて進展の分類を決定するステップ；
を含むものとする、請求項９に記載の方法。
【請求項１２】
さらに、ピラミッド状の分布に依存する特定の時間においてオンライン統計をストアするステップを含むものとする、請求項１に記載の方法。
【請求項１３】
データ・ストリームのデータのクラスタリングを行う装置であって：
メモリ；および、
前記メモリに結合された少なくとも１つのプロセッサであり：
（ｉ）前記データ・ストリームからオンライン統計を作成する作用；および、
（ｉｉ）前記オンライン統計のオフライン・プロセッシングを、オフライン・プロセッシングが必要であるか、あるいは望ましいときに行う作用；
をもたらすプロセッサ；
を備える装置。
【請求項１４】
前記少なくとも１つのプロセッサは、さらに、オフライン・プロセッシングが必要であるか否か、あるいは望ましいか否かを決定する作用をもたらすものとする、請求項１３に記載の装置。
【請求項１５】
前記オンライン統計を作成する作用は：
前記データ・ストリームからデータ・ポイントを受け取る作用；および、
前記データ・ストリームから前記オンライン統計を更新する作用；
をもたらすものとする、請求項１３に記載の装置。
【請求項１６】
前記オンライン統計を更新する作用は：
前記データ・ポイントにもっとも近いデータ・ポイントのグループを見つけ出す作用；
前記もっとも近いグループまでの距離がスレッショルドより大きいか否かを決定する作用；
前記もっとも近いグループまでの前記距離が前記スレッショルドより大きい場合には、前記データ・ポイントを有する新しいグループを作成する作用；
前記もっとも近いグループまでの前記距離が前記スレッショルドより小さい場合には、前記データ・ポイントを前記もっとも近いグループへ追加する作用；および、
作成した場合には前記新しいグループの、あるいは前記データ・ポイントを追加した場合には前記もっとも近いグループの前記統計を更新する作用；
をもたらすものとする、請求項１５に記載の装置。
【請求項１７】
前記オフライン・プロセッシングを行う作用は：
定義済みの数のデータ・ポイントをサンプリングする作用；
前記サンプリングしたデータ・ポイントの周囲においてデータ・ポイントのグループの再クラスタリングを行う作用；
サンプリングおよび再クラスタリングの追加の反復が必要であるか否かを決定する作用；
追加の反復が必要である場合には、前記再クラスタリングを行ったデータ・ポイントのグループの中心軌跡として前記サンプリングしたポイントの再定義を行った後に、前記再定義を行った前記サンプリングしたポイントの周囲においてデータ・ポイントのグループの再クラスタリングを行う作用；および、
前記再クラスタリングにおいて形成されたクラスタのレポートを行う作用；
をもたらすものとする、請求項１３に記載の装置。
【請求項１８】
前記オフライン・プロセッシングを行う作用は、前記オンライン統計を使用してより高いレベルのクラスタを作成する作用をもたらすものとする、請求項１３に記載の装置。
【請求項１９】
前記オンライン統計は、より低いレベルのクラスタであるとする、請求項１３に記載の装置。
【請求項２０】
前記オンライン統計を使用してより高いレベルのクラスタを作成する前記作用は、より低いレベルのクラスタの再クラスタリングを行う作用をもたらすものとする、請求項１９に記載の装置。
【請求項２１】
前記オフライン・プロセッシングを行う作用は、前記オンライン統計を使用してデータ・ストリームの進展をモニタする作用をもたらすものとする、請求項１３に記載の装置。
【請求項２２】
前記オンライン統計を使用してデータ・ストリームの進展をモニタする前記作用は、２つの異なる対象期間における前記オンライン統計を比較する作用をもたらすものとする、請求項２１に記載の装置。
【請求項２３】
前記オンライン統計を使用してデータ・ストリームの進展をモニタする前記作用は：
指定された対象期間に関してオンライン統計の減算を行う作用；および、
前記減算後の統計に基づいて進展の分類を決定する作用；
をもたらすものとする、請求項２１に記載の装置。
【請求項２４】
前記少なくとも１つのプロセッサは、さらに、ピラミッド状の分布に依存する特定の時間においてオンライン統計をストアする作用をもたらすものとする、請求項１３に記載の装置。
【請求項２５】
データ・ストリームのデータのクラスタリングを行うための製品であって、１ないしは複数のプログラムを含むマシン可読メディアを含み、前記プログラムは、実行されたときに：
前記データ・ストリームからオンライン統計を作成するステップ；および、
前記オンライン統計のオフライン・プロセッシングを、オフライン・プロセッシングが必要であるか、あるいは望ましいときに行うステップ；
を具体化するものである製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データのクラスタリングに関し、より詳細に述べれば、生成済みオンライン統計およびオフライン・プロセッシングを介した進展しているデータ・ストリームのクラスタリングに関する。
【背景技術】
【０００２】
近年のハードウエア・テクノロジの進歩によって会社ならびに組織は、日常のトランザクション（たとえば、バンキング、クレジット・カード、証券、テレコミュニケーション等）を自動的に、かつ迅速に記録することが可能になった。その種のプロセスの記録は、際限のないレートで成長する大量のデータを招いている。この絶え間のないデータの到来は、データ・ストリームと呼ばれる。データ・ストリームについては、広い応用範囲におけるその使用から、近年、広範に研究されている：たとえば、非特許文献１、非特許文献２、非特許文献３、および非特許文献４を参照されたい。
【０００３】
データ・ストリームのクラスタリングは、与えられたデータ・ポイントのセットを、１ないしは複数の類似のデータ・ポイントのグループに区分編成する。クラスタリングについては、データベース、データ・マイニングおよび統計コミュニティにおいて広範に研究されている：たとえば、非特許文献５、非特許文献６、非特許文献７、非特許文献８、および非特許文献９を参照されたい。クラスタリングは、データ・ストリーム環境に関しても研究されている：たとえば非特許文献３および非特許文献４を参照されたい。
【０００４】
データ・ストリームのクラスタリングは、大量のデータの出現に帰着することから、ほとんどの伝統的なクラスタリングの手法が役に立たなくなる。近年、データ・ストリームとともに使用するためのワン−パス・クラスタリング手法が開発された。しかしながら、数年の間にデータ・ストリームに関して提供された単純なワン−パス・クラスタリング手法は、結果が、ストリームの古い履歴によって左右されることになるというものである。
【０００５】
別の現存する、データ・ストリームのクラスタリングのための手法は、全体のデータ・ストリームにわたってクラスタの演算を行う：たとえば非特許文献４を参照されたい。これらのテクニックは、データ・ストリームのクラスタリングを、ワン−パス・クラスタリング手法の変形として見ている。その種のテクニックが多くのクラスタリング応用に有用となることもあるが、データ・ストリームのクラスタリングが、データ・ストリームに関連して念入りな定義を必要とする。データ・ストリームは、時間とともに連続的に進展するデータを有する無限プロセスとして見るべきである。その結果、基礎をなすクラスタもまた時間とともに少なからず変化することがある。クラスタの性質は、それらの演算が行われる瞬間をはじめ、それらが測定される時間的対象期間に依存して変化することがある。たとえばユーザが、前の月、年、または最近の１０年間に生じたクラスタの調査を希望することがあるが、そのそれぞれは、かなり異なることがあり得る。
【０００６】
データ・ストリームは、本質的に、手法の設計にワン−パスの制約を課する。従来の手法を使用し、種類の異なる時間的対象期間にわたるクラスタ演算に柔軟性を提供することは非常に困難になっている。たとえば、ストリーム・ベースのｋ平均手法（たとえば、非特許文献４を参照されたい）の直接拡張は、可能性のあるすべての時間的対象期間にわたるクラスタリング手法の中間結果の同時維持を必要とする。この種の演算負荷は、データ・ストリームの進行とともに増加し、急速にオンライン実装に関するボトルネックとなり得る。しかも、多くの場合においては、アナリストが以前の時点におけるクラスタの決定、および現在のクラスタとそれらの比較を望むことがある。このことは、さらに大きなブックキーピングを必要とし、それが高速データ・ストリームをたちどころに非現実的なものとする可能性がある。
【０００７】
演算の経過に優先してデータ・ストリームを改訂することができないことから、クラスタリング手法は、重要な詳細が失われないように、相当量の情報を維持する必要がある。たとえば、ｋ平均手法の連続バージョンは、当該手法の実行を通して必要に応じて変化もしくは併合されるクラスタ中心の数を維持する：たとえば非特許文献４を参照されたい。このアプローチは、ｋ平均アプローチがデータ・ポイントの到来の順序に対して非常に敏感であることから、ストリームの特性が時間的に進展する場合に予測不能となる。たとえば、２つのクラスタ中心が併合されると、その後に当該ストリームの進展によって分割が必要になったときに、情報を与える形でクラスタを分割する方法がなくなる。
【０００８】
【非特許文献１】Ｂ．Ｂａｂｃｏｃｋ（Ｂ．バブコック）ほか「Ｍｏｄｅｌｓ  ａｎｄ  Ｉｓｓｕｅｓ  ｉｎ  Ｄａｔａ  Ｓｔｒｅａｍ  Ｓｙｓｔｅｍｓ（データ・ストリーム・システムにおけるモデルおよび問題）」ＡＣＭ  ＰＯＤＳコンファレンス、２００２年
【非特許文献２】Ｐ．Ｄｏｍｉｎｇｏｓ（Ｐ．ドミンゴス）ほか「Ｍｉｎｉｎｇ  Ｈｉｇｈ−Ｓｐｅｅｄ  Ｄａｔａ  Ｓｔｒｅａｍｓ（高速データ・ストリームのマイニング）」ＡＣＭ  ＳＩＧＫＤＤコンファレンス、２０００年
【非特許文献３】Ｓ．Ｇｕｈａ（Ｓ．グーハ）ほか「Ｃｌｕｓｔｅｒｉｎｇ  Ｄａｔａ  Ｓｔｅａｍｓ（データ・ストリームのクラスタリング）」ＩＥＥＥ  ＦＯＣＳコンファレンス、２０００年
【非特許文献４】Ｌ．Ｏ’Ｃａｌｌａｇｈａｎ（Ｌ．オカラガン）ほか「Ｓｔｒｅａｍｉｎｇ−Ｄａｔａ  Ａｌｇｏｒｉｔｈｍｓ  Ｆｏｒ  Ｈｉｇｈ−Ｑｕａｌｉｔｙ  Ｃｌｕｓｔｅｒｉｎｇ（高品質クラスタリングのためのストリーミング−データ・アルゴリズム）」ＩＣＤＥコンファレンス、２００２年
【非特許文献５】Ｐ．Ｂｒａｄｌｅｙ（Ｐ．ブラッドレー）ほか「Ｓｃａｌｉｎｇ  Ｃｌｕｓｔｅｒｉｎｇ  Ａｌｇｏｒｉｔｈｍｓ  ｔｏ  Ｌａｒｇｅ  Ｄａｔａｂａｓｅｓ（大規模データベースへのクラスタリング・アルゴリズムのスケーリング）」ＳＩＧＫＤＤコンファレンス、１９９８年
【非特許文献６】Ｓ．Ｇｕｈａ（Ｓ．グーハ）ほか「ＣＵＲＥ：Ａｎ  Ｅｆｆｉｃｉｅｎｔ  Ｃｌｕｓｔｅｒｉｎｇ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｌａｒｇｅ  Ｄａｔａｂａｓｅｓ（ＣＵＲＥ：大規模データベースのための効率的なクラスタリング・アルゴリズム）」ＡＣＭ  ＳＩＧＭＯＤコンファレンス、１９９８年
【非特許文献７】Ｒ．Ｎｇ（Ｒ．ング）ほか「Ｅｆｆｉｃｉｅｎｔ  ａｎｄ  Ｅｆｆｅｃｔｉｖｅ  Ｃｌｕｓｔｅｒｉｎｇ  Ｍｅｔｈｏｄｓ  ｆｏｒ  Ｓｐａｔｉａｌ  Ｄａｔａ  Ｍｉｎｉｎｇ（空間的データ・マイニングのための効率的かつ効果的なクラスタリング方法）」Ｖｅｒｙ  Ｌａｒｇｅ  Ｄａｔａ  Ｂａｓｅｓ（超大規模データ・ベース）コンファレンス、１９９４年
【非特許文献８】Ｒ．Ｄｕｂｅｓ（デューブス）ほか「Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｃｌｕｓｔｅｒｉｎｇ  Ｄａｔａ（データのクラスタリングのためのアルゴリズム）」Ｐｒｅｎｔｉｃｅ  Ｈａｌｌ（プレンティス・ホール；ニュージャージー州）１９９８年
【非特許文献９】Ｌ．Ｋａｕｆｍａｎ（Ｌ．コフマン）ほか「Ｆｉｎｄｉｎｇ  Ｇｒｏｕｐｓ  ｉｎ  Ｄａｔａ  −−  Ａｎ  Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｃｌｕｓｔｅｒ  Ａｎａｌｙｓｉｓ（データのグループを見つける−−クラスタ分析入門）」Ｗｉｌｅｙ  Ｓｅｒｉｅｓ  ｉｎ  Ｐｒｏｂａｂｉｌｉｔｙ  ａｎｄ  Ｍａｔｈ  Ｓｃｉｅｎｃｅｓ（ワイリー・シリーズ：確率および数理科学）１９９０年
【非特許文献１０】Ｔ．Ｚｈａｎｇ（Ｔ．ザング）ほか「ＢＩＲＣＨ：Ａｎ  Ｅｆｆｉｃｉｅｎｔ  Ｄａｔａ  Ｃｌｕｓｔｅｒｉｎｇ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｖｅｒｙ  Ｌａｒｇｅ  Ｄａｔａｂａｓｅｓ（超大規模データベースのための効果的なデータ・クラスタリング方法）」ＡＣＭ  ＳＩＧＭＯＤコンファレンス、１９９６年
【発明の開示】
【発明が解決しようとする課題】
【０００９】
したがって、データが時間とともに相当に進展するときのクラスタの質を向上させることが必要になっている。また、ストリームの様々な部分にわたるクラスタの発見および探究において、より大きな機能性の存在も求められている。
【課題を解決するための手段】
【００１０】
本発明は、データ・クラスタリング・テクニックに関する。より詳細に述べれば、本発明は、生成済みオンライン統計およびオフライン・プロセッシングを介した進展しているデータ・ストリームのクラスタリングに関する。
【００１１】
たとえば、本発明の１つの側面においては、データ・ストリームのデータのクラスタリングを行うテクニックが、次に示すステップを含む。まず、オンライン統計がデータ・ストリームから作成される。続いて、当該オンライン統計のオフライン・プロセッシングが、オフライン・プロセッシングが必要であるとき、もしくは望ましいときに実行される。
【００１２】
好適にも本発明のテクニックは、ユーザが容易にアクセス可能であり、かつマネージ可能な方法に従って、効率的かつ効果的にデータ・ストリームのクラスタリングを行う。
【００１３】
本発明のテクニックのもう１つの特性は、ユーザ定義時間期間にわたるクラスタの演算におけるその柔軟性である。それに加えて、本発明のテクニックは、データ・ストリームの、前の時点におけるクラスタと現在のクラスタの比較を提供する。ユーザは、データ・ストリームの様々な部分にわたって、発見ならびに探究を行うことができる。
【００１４】
以上の、およびそのほかの本発明の目的、特徴、ならびに利点については、例として示す以下の実施態様の詳細な説明を添付図面とともに考察することによって明らかなものとなるであろう。
【発明を実施するための最良の形態】
【００１５】
以下の説明においては、一例のデータ処理システム・アーキテクチャを使用して本発明の例証を行う。しかしながらここで理解される必要があるが、本発明が特定のシステム・アーキテクチャとの使用に限定されることはない。むしろ本発明は、より一般的に、効率的かつ効果的なデータ・ストリームのクラスタリングを行うことが望ましい任意のデータ処理システムに適用可能である。
【００１６】
データ・ストリームのクラスタリングを行うために、データの局所性に関する統計的情報が、マイクロ−クラスタという点から維持される。これらの統計的データ・ポイントは、クラスタの特徴ベクトルの時間的拡張として定義されている：たとえば、非特許文献１０を参照されたい。マイクロ−クラスタは、それらの加法的特性に起因してデータ・ストリームのクラスタリング内において使用される。マイクロ−クラスタは、特定のパターンに従う時間に属するスナップショットとしてストアされる。このパターンは、ストレージ要件と、異なる時間的対象期間からの要約統計を呼び戻す機能の間の効果的なトレード−オフを提供する。その後、マイクロ−クラスタ内の要約情報がオフライン・コンポーネントによって使用されるが、それが、時間的対象期間もしくはクラスタリングの粒状度等の広範多様なユーザ入力に依存する。
【００１７】
したがって本発明によれば、データ・ストリームのクラスタリングがオンライン・マイクロ−クラスタリング・コンポーネントとオフライン・マクロ−クラスタリング・コンポーネントに分離される。オンライン・マイクロ−クラスタリング・コンポーネントは、高速データ・ストリームにおける適切な要約統計のストレージのための効率的な手法を採用する。オフライン・コンポーネントは、必要時にクラスタの迅速な理解をユーザに提供するために、そのほかのユーザ入力とともにこれらの要約統計を使用する。オフライン・コンポーネントは、要約統計を入力として使用することから効率的である。この２段階アプローチは、様々な時間期間にわたってクラスタの進展の性質を探究する柔軟性をユーザーに提供する。
【００１８】
ここで、データ・ストリームが、タイムスタンプＴ１．．．Ｔｋ．．．に到来する多次元レコードＸ１．．．Ｘｋ．．．のセットを包含するものとする。各Ｘｉは、ｄ個の次元を含む多次元レコードであり、Ｘｉ＝ｘｉ１．．．ｘｉｄとして表される。
【００１９】
タイムスタンプＴｉ１．．．Ｔｉｎを伴うｄ次元のポイントＸｉ１．．．Ｘｉｎのセットに関するマイクロ−クラスタは、２・ｄ＋３タプル（ＣＦ２ｘ，ＣＦ１ｘ，ＣＦ２ｔ，ＣＦ１ｔ，ｎ）として定義され、それにおいて｛ＣＦ２ｘ｝および｛ＣＦ１ｘ｝は、それぞれｄ個のエントリのベクトルに対応する。これらのエントリのそれぞれは、次に示すように定義される。
・各次元に関して、データ値の平方の合計が｛ＣＦ２ｘ｝内に維持される。つまり｛ＣＦ２ｘ｝は、ｄ個の値を含む。｛ＣＦ２ｘ｝のｐ番目のエントリは次式に等しい：
【数１】
2005100363.tif 000003
・各次元に関して、データ値の合計が｛ＣＦ１ｘ｝内に維持される。つまり｛ＣＦ１ｘ｝は、ｄ個の値を含む。｛ＣＦ１ｘ｝のｐ番目のエントリは次式に等しい：
【数２】
2005100363.tif 000004
・タイムスタンプＴｉ１．．．Ｔｉｎの平方の合計が｛ＣＦ２ｔ｝内に維持される。
・タイムスタンプＴｉ１．．．Ｔｉｎの合計が｛ＣＦ１ｔ｝内に維持される。
・データ・ポイントの数がｎ内に維持される。
【００２０】
マイクロ−クラスタの定義は、クラスタの特徴ベクトルの時間的な拡張となる。ポイントＣのセットに関するマイクロ−クラスタは、ＣＦＴ（Ｃ）によって表される。この要約情報は、異なるデータ・ポイントにわたって加算的な方法で表すことが可能であり、そのことからデータ・ストリームの手法に関して自然な選択であると言える。与えられた時点において、データ・ストリーム内の支配的なマイクロ−クラスタに関する統計的な情報は、この手法によって維持される。この手法は、非常に多数のマイクロ−クラスタが、以前の方法に比較して効率的に維持されることを保証する：たとえば非特許文献４を参照されたい。オンライン更新手法の高い粒状度は、進展しているデータ・ストリームにおいて、はるかに良好な質のクラスタの提供が可能となることを保証する。
【００２１】
マイクロ−クラスタは、ストリーム内の特定の瞬間にストアされ、スナップショットと呼ばれる。オフライン・マクロ−クラスタリング手法は、より高いレベルのクラスタを特定の時間的対象期間にわたって作成するために、より細かいレベルのマイクロ−クラスタを使用する。ユーザには、クロック時がｔｃのときの長さｈの履歴に基づいてストリーム内のクラスタを見つけ出すという希望が許される。このマクロ−クラスタリング手法は、長さｈの履歴または時間的対象期間内において、より高いレベルのクラスタを見つけ出すために、スナップショットｔｃおよび（ｔｃ−ｈ）としてストアされているマイクロ−クラスタの減法特性を使用する。減法特性は、このマイクロ−クラスタリング表現の非常に重要な特性であり、それにより、異なる時間的対象期間にわたってより高いレベルのクラスタを生成することが可能になる。すべての時点のそれぞれにおけるスナップショットをストアすることが可能ではないため、マイクロ−クラスタがストアされる特定の時点を選択することが重要になる。これらの特定の時点を選択するねらいは、任意のユーザ指定時間的対象期間（ｔｃ−ｈ，ｔｃ）においてクラスタが近似できることの保証である。
【００２２】
ピラミッド状の時間フレーム内において、スナップショットが、新しさに応じ、異なるレベルの粒状度でストアされる。スナップショットは、１からｌｏｇ（Ｔ）までの間を変化することのできる異なる次数に分類され、それにおいてＴは、ストリームの開始から経過したクロック時間とする。スナップショットの特定のクラスの次数は、スナップショットが維持される時間的な粒状度のレベルを定義する。異なる次数のスナップショットは、次のように維持される。
・ｉ次のスナップショットは、時間間隔ａｉにおいて生じ、それにおいてａは、ａ≧１とする整数である。より具体的には、ｉ次の各スナップショットは、そのストリームの開始からのクロック値が正確にａｉによって割り切れる瞬間に獲得される。クロック時の１単位は、粒状度の最小レベルである。つまり０次のスナップショットは、粒状度の最小レベルにおける時間間隔に相当する。
・任意の与えられた瞬間において、最後のａ＋１個の次数ｉのスナップショットがストアされる。
【００２３】
上記の定義は、スナップショットのストレージにおいてかなりの冗長性を考慮している。たとえばクロック時８は、２０、２１、２２、および２３（これにおいてａ＝２）によって割り切れる。したがって、クロック時８のマイクロ−クラスタの状態は、同時に、次数０、次数１、次数２、および次数３のスナップショットに対応する。
【００２４】
ここでまず図１を参照すると、本発明の一実施態様に従った手法の採用に適したハードウエアによる具体化を例示したブロック図が示されている。これに示されているように、この例のシステムは、大規模ネットワーク１０を介してサーバ２０へ結合されるクライアント・デバイスを含む。サーバ２０は、メイン・メモリ４０ならびにディスク５０が結合される中央処理ユニット（ＣＰＵ）３０を含むことができる。ここでは、複数のクライアントが大規模ネットワーク１０を介してサーバ２０とインタラクション可能であることを仮定する。ここで認識されるように、ネットワーク１０は、たとえばインターネットまたはワールド・ワイド・ウェブ等の公衆情報ネットワークとすることができるが、それに代えてクライアントとサーバが、プライベート・ネットワーク、ローカル・エリア・ネットワーク、またはそのほかの適切なネットワークを介して接続されるようにしてもよい。
【００２５】
本発明のデータ・クラスタリング演算は、サーバ２０上のＣＰＵ  ３０において実行され、１ないしは複数のクライアント・デバイスへ渡される。クライアント・デバイスは、データ・ストリームの各種特性に関してクエリを行い、サーバ２０がそれに応答する。処理されることになるデータ・セットのすべてもしくは一部が、処理の間にわたってディスク５０上にストアされる。メイン・メモリ４０は、処理の間に作成された統計の一部もしくはすべてをストアするために使用される。結果は、要求を行っているクライアント・デバイスへ返される。
【００２６】
好ましい一実施態様においては、これに述べているような本発明の手法を実施するためのインストラクションもしくはコードを含むソフトウエア・コンポーネントが、サーバに関して上述した１ないしは複数のメモリ・デバイス内にストアされ、かつＣＰＵ  ３０による使用、部分的もしくは全体的なロード、および実行に応じられるようにすることができる。
【００２７】
図２を参照すると、本発明の一実施態様に従った、オンライン・マイクロ−クラスタリングとオフライン・マクロ−クラスタリングの相関手法を例示したフローチャートが示されている。この手法は、ステップ２００において開始し、それにおいてデータ・ストリームが入力される。ステップ２１０においては、このデータ・ストリームからデータ・ポイントを受け取られる。このデータ・ポイントは、ステップ２２０におけるオンライン統計の更新に使用される。このオンライン・マイクロ−クラスタリングのステップについては、より詳細が図３に記述されている。ステップ２３０においては、クラスタの分析を目的としてオフライン処理が必要となるか否かが決定される。オフライン処理が必要となる場合には、それがステップ２４０において実行される。このオフライン・マクロ−クラスタリングのステップについては、より詳細が図４に記述されている。その後、この手法はステップ２１０へ戻る。オフライン処理が必要とならない場合には、この手法が直接ステップ２１０へ戻る。データ・ストリームからそれ以上のデータ・ポイントが受け取られなくなると、ステップ２５０においてこの手法が終了する。
【００２８】
図３は、本発明の一実施態様に従った、マイクロ−クラスタの維持手法を例示したフローチャートである。この図は、図２のステップ２２０の詳細な記述と考えることができる。この手法は、ステップ３００において開始し、それにおいてデータ・ストリームからデータ・ポイントが入力される。ステップ３１０においては、到来データ・ポイントにもっとも近いデータ・ポイントのグループが探し出される。ステップ３２０においては、このもっとも近いグループに対する距離が、ユーザ指定スレッショルドより大きいか否かについて決定される。この距離がそのスレッショルドより大きい場合には、ステップ３３０において、単一のデータ・ポイントを伴った新しいグループが作成される。新しいグループは、グループがまったく存在しない場合にも作成される。距離がスレッショルドより小さい場合には、ステップ３３５において、もっとも近いグループへそのデータ・ポイントが追加される。いずれの場合においても、更新後のグループもしくは新しいグループがステップ３４０において更新される。グループ統計の更新においては、マイクロ−クラスタ内のデータ・ポイントのカウントが更新される。それに加えて、適切な時間ウインドウが経過すると、スナップショットが明示的にストアされる。この手法は、ステップ３５０において終了する。
【００２９】
次に図４を参照すると、本発明の一実施態様に従った、より高いレベルのクラスタの作成手法を例示したフローチャートが示されている。より高いレベルのマクロ−クラスタは、図３のきめの細かいマイクロ−クラスタから作られる。このステップは、ユーザがデータ・ストリーム内のより高いレベルのクラスタのピクチャを希望したときに、オフライン・プロセスとして実行される。またこの手法は、図２におけるステップ２４０の詳細な記述と考えることもできる。この手法は、ステップ４００において開始する。ステップ４１０においては、本発明のテクニックがｋ個の代表擬似ポイントのサンプリングを行う。ステップ４２０においては、代表擬似ポイントの周囲においてマイクロ−クラスタ・グループの再クラスタリングが行われる。各マイクロ−クラスタ・グループは、もっとも近い代表擬似ポイントへ割り当てられる。この手法は、反復プロセスである。この種の反復の回数は、ユーザがアプリオリに決定する。ステップ４３０においては、さらに反復が必要か否かについて決定する。さらに反復が必要な場合には、ステップ４４０において、再クラスタリング済みポイントの中心軌跡として代表擬似ポイントが再定義される。続いてこの手法は、ステップ４２０へ戻る。それ以上の反復が必要ない場合には、この手法が、ステップ４５０において、再クラスタリング手法によって見つけられた対応するクラスタのレポートを行う。これらのクラスタは、ユーザ指定時間期間にわたって作成されるようにすることも可能であり、その場合には、その時間期間にわたる関連グループを決定し、その後それらのクラスタを再形成する。この手法は、ステップ４６０において終了する。
【００３０】
ここで図５を参照すると、本発明の一実施態様に従った、マイクロ−クラスタの進展の分析手法を例示したフローチャートが示されている。この方法は、ステップ５００において開始する。ステップ５１０においては、適切な時間的対象期間にわたって減算手法が実施される。この減算手法においては、以前の時間的対象期間に関するマイクロ−クラスタ統計が、現在のマイクロ−クラスタ統計から減じられる。ステップ５２０においては、この手法が、減算後の統計に基づいて進展の分類を決定する。たとえば、あるクラスタ・グループが時間ｔ１において存在し、時間ｔ２＞ｔ１において存在しない場合には、そのグループが期間（ｔ１，ｔ２）内に削除されたことが意味される。これに対して、ｔ１＞ｔ２であれば、新しいグループがその期間（ｔ１，ｔ２）内に作成されたことが意味される。この手法はステップ５３０において終了する。
【００３１】
したがって、ここに説明したように、本発明は、大規模の進展しているデータ・ストリームのクラスタリングを行うための効果的かつ効率的な方法を提供する。この方法は、現存するテクニック、すなわち時間にわたって変化するプロセスとしてストリームを見るのではなく、一度に全体のストリームのクラスタリングを試みるテクニックに対して明らかな利点を有する。クラスタリング・モデルは、進展する環境内において異なる時間的対象期間にわたるデータ・ストリーム・クラスタの特徴決定に広範多様な機能を提供する。これは、オンライン統計データ収集コンポーネントと、オフライン分析コンポーネントの間の労力の慎重な分配を介して達成される。このように、この手法は、リアルタイムの変化する環境においてアナリストに相当の柔軟性を提供する。
【００３２】
以上、添付図面を参照して本発明の例示的な実施態様を説明してきたが、本発明がそのままの形でこれらの実施態様に限定されないこと、および本発明の範囲もしくは精神から逸脱することなく当業者によってこのほかの各種の変更ならびに修正が行われ得ることを理解する必要がある。
【００３３】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００３４】
（１）データ・ストリームのデータのクラスタリングを行う方法であって：前記データ・ストリームからオンライン統計を作成するステップ；および、前記オンライン統計のオフライン・プロセッシングを、オフライン・プロセッシングが必要であるか、あるいは望ましいときに行うステップ；を含む方法。
（２）さらに、オフライン・プロセッシングが必要であるか否か、あるいは望ましいか否かを決定するステップを含むものとする、上記（１）に記載の方法。
（３）前記オンライン統計を作成するステップは：前記データ・ストリームからデータ・ポイントを受け取るステップ；および、前記データ・ストリームから前記オンライン統計を更新するステップ；を含むものとする、上記（１）に記載の方法。
（４）前記オンライン統計を更新するステップは：前記データ・ポイントにもっとも近いデータ・ポイントのグループを見つけ出すステップ；前記もっとも近いグループまでの距離がスレッショルドより大きいか否かを決定するステップ；前記もっとも近いグループまでの前記距離が前記スレッショルドより大きい場合には、前記データ・ポイントを有する新しいグループを作成するステップ；前記もっとも近いグループまでの前記距離が前記スレッショルドより小さい場合には、前記データ・ポイントを前記もっとも近いグループへ追加するステップ；および、作成した場合には前記新しいグループの、あるいは前記データ・ポイントを追加した場合には前記もっとも近いグループの前記統計を更新するステップ；を含むものとする、上記（３）に記載の方法。
（５）前記オフライン・プロセッシングを行うステップは：定義済みの数のデータ・ポイントをサンプリングするステップ；前記サンプリングしたデータ・ポイントの周囲においてデータ・ポイントのグループの再クラスタリングを行うステップ；サンプリングおよび再クラスタリングの追加の反復が必要であるか否かを決定するステップ；追加の反復が必要である場合には、前記再クラスタリングを行ったデータ・ポイントのグループの中心軌跡として前記サンプリングしたポイントの再定義を行った後に、前記再定義を行った前記サンプリングしたポイントの周囲においてデータ・ポイントのグループの再クラスタリングを行うステップ；および、前記再クラスタリングにおいて形成されたクラスタのレポートを行うステップ；を含むものとする、上記（１）に記載の方法。
（６）前記オフライン・プロセッシングを行うステップは、前記オンライン統計を使用してより高いレベルのクラスタを作成するステップを含むものとする、上記（１）に記載の方法。
（７）前記オンライン統計は、より低いレベルのクラスタであるとする、上記（６）に記載の方法。
（８）前記オンライン統計を使用してより高いレベルのクラスタを作成する前記ステップは、より低いレベルのクラスタの再クラスタリングを行うステップを含むものとする、上記（７）に記載の方法。
（９）前記オフライン・プロセッシングを行うステップは、前記オンライン統計を使用してデータ・ストリームの進展をモニタするステップを含むものとする、上記（１）に記載の方法。
（１０）前記オンライン統計を使用してデータ・ストリームの進展をモニタする前記ステップは、２つの異なる対象期間における前記オンライン統計を比較するステップを含むものとする、上記（９）に記載の方法。
（１１）前記オンライン統計を使用してデータ・ストリームの進展をモニタする前記ステップは：指定された対象期間に関してオンライン統計の減算を行うステップ；および、前記減算後の統計に基づいて進展の分類を決定するステップ；を含むものとする、上記（９）に記載の方法。
（１２）さらに、ピラミッド状の分布に依存する特定の時間においてオンライン統計をストアするステップを含むものとする、上記（１）に記載の方法。
（１３）データ・ストリームのデータのクラスタリングを行う装置であって：メモリ；および、前記メモリに結合された少なくとも１つのプロセッサであり：（ｉ）前記データ・ストリームからオンライン統計を作成する作用；および、（ｉｉ）前記オンライン統計のオフライン・プロセッシングを、オフライン・プロセッシングが必要であるか、あるいは望ましいときに行う作用；をもたらすプロセッサ；を備える装置。
（１４）前記少なくとも１つのプロセッサは、さらに、オフライン・プロセッシングが必要であるか否か、あるいは望ましいか否かを決定する作用をもたらすものとする、上記（１３）に記載の装置。
（１５）前記オンライン統計を作成する作用は：前記データ・ストリームからデータ・ポイントを受け取る作用；および、前記データ・ストリームから前記オンライン統計を更新する作用；をもたらすものとする、上記（１３）に記載の装置。
（１６）前記オンライン統計を更新する作用は：前記データ・ポイントにもっとも近いデータ・ポイントのグループを見つけ出す作用；前記もっとも近いグループまでの距離がスレッショルドより大きいか否かを決定する作用；前記もっとも近いグループまでの前記距離が前記スレッショルドより大きい場合には、前記データ・ポイントを有する新しいグループを作成する作用；前記もっとも近いグループまでの前記距離が前記スレッショルドより小さい場合には、前記データ・ポイントを前記もっとも近いグループへ追加する作用；および、作成した場合には前記新しいグループの、あるいは前記データ・ポイントを追加した場合には前記もっとも近いグループの前記統計を更新する作用；をもたらすものとする、上記（１５）に記載の装置。
（１７）前記オフライン・プロセッシングを行う作用は：定義済みの数のデータ・ポイントをサンプリングする作用；前記サンプリングしたデータ・ポイントの周囲においてデータ・ポイントのグループの再クラスタリングを行う作用；サンプリングおよび再クラスタリングの追加の反復が必要であるか否かを決定する作用；追加の反復が必要である場合には、前記再クラスタリングを行ったデータ・ポイントのグループの中心軌跡として前記サンプリングしたポイントの再定義を行った後に、前記再定義を行った前記サンプリングしたポイントの周囲においてデータ・ポイントのグループの再クラスタリングを行う作用；および、前記再クラスタリングにおいて形成されたクラスタのレポートを行う作用；をもたらすものとする、上記（１３）に記載の装置。
（１８）前記オフライン・プロセッシングを行う作用は、前記オンライン統計を使用してより高いレベルのクラスタを作成する作用をもたらすものとする、上記（１３）に記載の装置。
（１９）前記オンライン統計は、より低いレベルのクラスタであるとする、上記（１３）に記載の装置。
（２０）前記オンライン統計を使用してより高いレベルのクラスタを作成する前記作用は、より低いレベルのクラスタの再クラスタリングを行う作用をもたらすものとする、上記（１９）に記載の装置。
（２１）前記オフライン・プロセッシングを行う作用は、前記オンライン統計を使用してデータ・ストリームの進展をモニタする作用をもたらすものとする、上記（１３）に記載の装置。
（２２）前記オンライン統計を使用してデータ・ストリームの進展をモニタする前記作用は、２つの異なる対象期間における前記オンライン統計を比較する作用をもたらすものとする、上記（２１）に記載の装置。
（２３）前記オンライン統計を使用してデータ・ストリームの進展をモニタする前記作用は：指定された対象期間に関してオンライン統計の減算を行う作用；および、前記減算後の統計に基づいて進展の分類を決定する作用；をもたらすものとする、上記（２１）に記載の装置。
（２４）前記少なくとも１つのプロセッサは、さらに、ピラミッド状の分布に依存する特定の時間においてオンライン統計をストアする作用をもたらすものとする、上記（１３）に記載の装置。
（２５）データ・ストリームのデータのクラスタリングを行うための製品であって、１ないしは複数のプログラムを含むマシン可読メディアを含み、前記プログラムは、実行されたときに：前記データ・ストリームからオンライン統計を作成するステップ；および、前記オンライン統計のオフライン・プロセッシングを、オフライン・プロセッシングが必要であるか、あるいは望ましいときに行うステップ；を具体化するものである製品。
【図面の簡単な説明】
【００３５】
【図１】本発明の一実施態様に従った手法の採用に適したハードウエアによる具体化を例示したブロック図である。
【図２】本発明の一実施態様に従った、オンライン・マクロ−クラスタリングとオフライン・マクロ−クラスタリングの相関手法を例示したフローチャートである。
【図３】本発明の一実施態様に従った、マイクロ−クラスタの維持手法を例示したフローチャートである。
【図４】本発明の一実施態様に従った、より高いレベルのクラスタの作成手法を例示したフローチャートである。
【図５】本発明の一実施態様に従った、マイクロ−クラスタの進展の分析手法を例示したフローチャートである。
【符号の説明】
【００３６】
１０  大規模ネットワーク
２０  サーバ
３０  中央処理ユニット（ＣＰＵ）
４０  メイン・メモリ
５０  ディスク
【図１】
2005100363.tif 000005
【図２】
2005100363.tif 000006
【図３】
2005100363.tif 000007
【図４】
2005100363.tif 000008
【図５】
2005100363.tif 000009