(57)【要約】      （修正有）【課題】産業用途においてセンサーから取得されたデータ点をクラスターに分割する方法及び信号雑音除去等の信号のグラフに基づく処理方法を提供する。【解決手段】入力データのデータ点３０１が、このデータのラプラシアン行列を最初に求めることによって処理される３１０。このラプラシアン行列のスペクトルは、正の固有値の引き付けスペクトルと、負の固有値の反発スペクトルと、０の固有値の中立スペクトルとを含む。処理のための操作が、ラプラシアン行列を用いるとともに、引き付けスペクトル、反発スペクトル及び中立スペクトルについての情報を用いて決定される３２０。この情報は、これらのスペクトルと、これらのスペクトルから導出された性質とを含む。次に、決定された操作が実行３３０され、処理されたデータ３０２が生成される。【選択図】図３
2016004579.tif 000002
【特許請求の範囲】
【請求項１】
入力データを処理する方法であって、該入力データは、データ点からなり、各データ点は、前記データ内の要素であり、該方法は、
前記データのラプラシアン行列を求めるステップであって、該ラプラシアン行列のスペクトルは、正の固有値の引き付けスペクトルと、負の固有値の反発スペクトルと、０の固有値の中立スペクトルとを含む、ステップと、
前記ラプラシアン行列を用いるとともに、前記引き付けスペクトル、前記反発スペクトル、及び前記中立スペクトルに関する情報を用いて、前記処理のための操作を決定するステップであって、前記情報は、前記スペクトルと、該スペクトルから導出された性質とを含む、ステップと、
前記操作を実行して、処理されたデータを生成するステップと、
前記処理されたデータを出力するステップと
を含み、各前記ステップは、１つ又は複数のプロセッサが実行する、方法。
【請求項２】
前記処理は、クラスター解析、予測解析、パターン認識、相関ルール学習、異常検出、分類、モデル化、要約、サンプリング、及び圧縮のうちの１つ又はそれらの組み合わせである、請求項１に記載の方法。
【請求項３】
前記データは信号であり、該信号の前記処理は、品質改善、フィルタリング、サンプリング、圧縮、及び特徴抽出、並びにそれらの組み合わせからなる群から選択される、請求項１に記載の方法。
【請求項４】
前記ラプラシアン行列は、グラフラプラシアン行列であり、該グラフラプラシアン行列は、グラフを用いて表される前記データについて求められ、前記方法は、
前記データのグラフ隣接行列を求めるステップであって、該グラフ隣接行列は、該グラフ隣接行列のエントリーを用いて求められ、該エントリーは、あらゆるデータ点を他の各データ点と対比較することによって求められ、該エントリーは、類似のデータ点のペアの場合には正であり、本質的に異なるデータ点のペアの場合には負であり、無相関のデータ点のペアの場合には０であり、該エントリーの振幅は、正の場合には前記類似度のレベルを定量化したものであり、負の場合には差異を定量化したものである、ステップと、
前記グラフ隣接行列をグラフ次数行列から減算することによって前記グラフラプラシアン行列を求めるステップであって、前記グラフ次数行列は、対角行列として求められ、該対角行列のいずれの対角エントリーも、該対角エントリーを有する同じ行における前記グラフ隣接行列の行の和である、ステップと、
を含む、請求項１に記載の方法。
【請求項５】
前記データ点は、ベクトルであり、前記データ点の対比較は、相関又は共分散に基づいて決定され、該相関及び該共分散は、２つの前記ベクトルが正に相関しているのか、負に相関しているのか、又は無相関であるのかに応じて、前記グラフ隣接行列の前記エントリーが正、負、又は０となるように、前記ベクトル間の一次従属を定量化する、請求項４に記載の方法。
【請求項６】
前記ベクトルは、時系列データの特徴ベクトルである、請求項５に記載の方法。
【請求項７】
前記ラプラシアン行列を前記求めるステップ及び前記操作を前記決定するステップは、波動方程式の振動モデルに基づき、
前記データを表す前記振動モデルを求めるステップであって、前記振動モデルは、振動を受けて相互作用する準粒子で構成された系を記述したものであり、前記振動モデルの各準粒子は、前記データ点のうちの１つに対応し、前記振動モデルの相互作用係数は、前記データ点の対比較によって求められ、前記ペア内の前記データ点が類似している場合には、前記相互作用は引き付けであるとともに前記相互作用係数は正であり、又は、前記ペア内の前記データ点が比較可能でないときは、前記相互作用は存在しないとともに前記相互作用係数は０であり、又は、前記ペア内の前記データ点が本質的に異なるときは、前記相互作用は反発であるとともに前記相互作用係数は負であり、前記相互作用の強度及び前記相互作用係数の振幅は、類似度又は差異のレベルを表す、ステップと、
前記波動方程式の前記振動モデルの固有モードを求めるステップであって、該固有モードは、固有値問題の固有ベクトルである、ステップと、
前記固有値問題から前記ラプラシアン行列を求めるステップと、
前記モデルの近似解に基づいて前記操作を決定するステップと、
を含む、請求項１に記載の方法。
【請求項８】
前記振動モデルは、質量体及びバネからなる質量体バネ系を表し、前記質量体は、前記準粒子であり、前記バネの剛性は、前記質量体の前記相互作用によって求められ、相互作用が引き付けであるとき、前記バネは、前記２つの質量体を引き付け、前記相互作用が反発であるとき、前記バネは、前記２つの質量体を反発させ、
前記質量体バネ系は、横振動を受け、該横振動は、前記質量体が、前記質量体バネ系の平面に対して垂直の方向にのみ動くことを可能にする、請求項７に記載の方法。
【請求項９】
前記ラプラシアン行列を前記求めるステップ及び前記操作を前記決定するステップは、拡散方程式の濃度拡散モデルに基づくものであって、
前記データを表す前記拡散方程式の前記濃度拡散モデルを求めるステップであって、前記濃度拡散モデルは、濃縮又は拡散を受けて相互作用する準粒子で構成された系であり、前記濃度拡散モデルの各準粒子は、前記データ内の点に対応し、モデル準粒子相互作用伝導係数は、前記データ点の対比較によって求められ、前記ペア内の前記データ点が類似している場合には、前記相互作用は拡散性であるとともに前記相互作用伝導係数は正であり、又は、前記ペア内の前記データ点が比較可能でない場合には、前記相互作用は存在しないとともに前記相互作用伝導係数は０であり、又は、前記ペア内の前記データ点が本質的に異なるときは、前記相互作用は濃縮性であるとともに前記相互作用伝導係数は負であり、前記相互作用の強度及び前記相互作用係数の振幅は、類似度又は差異のレベルを表す、ステップと、
前記拡散方程式の前記濃度拡散モデルの固有モードを求めるステップであって、該固有モードは、固有値問題の固有ベクトルである、ステップと、
前記ラプラシアン行列を前記固有値問題の行列として求めるステップと、
前記モデルの近似解に基づいて前記操作を決定するステップと
を更に含む、請求項１に記載の方法。
【請求項１０】
前記ラプラシアン行列は、グラフラプラシアン行列であり、該グラフラプラシアン行列は、前記グラフを用いて表される前記データについて求められる、請求項７又は９に記載の方法。
【請求項１１】
前記グラフラプラシアン行列の前記固有ベクトルに１つ又は複数の制約を課すこと、
を更に含み、前記１つ又は複数の制約は、
特定の固有ベクトルの構成要素を０に設定することと、
固有ベクトルの構成要素のスパース性を課すことと、および、
前記固有ベクトルが所与のベクトルの集合に対して垂直であることを要求すること、
のうちの１つ又はそれらの組み合わせである、請求項１０に記載の方法。
【請求項１２】
前記操作を前記決定するステップは、
前記ラプラシアン行列の選択される固有値及び対応する固有ベクトルを決定するステップであって、前記選択される固有値は、前記引き付けスペクトル、前記反発スペクトル、前記中立スペクトル、前記引き付けスペクトルの対象となる固有値、前記反発スペクトルの対象となる固有値、及び、前記中立スペクトルの対象となる固有値のうちの１つ又はそれらの組み合わせに基づいている、ステップと、
前記ラプラシアン行列と、該ラプラシアン行列の前記選択された固有値及び前記対応する固有ベクトルとを用いて前記操作を決定するステップと
を更に含む、請求項１に記載の方法。
【請求項１３】
前記操作は、前記選択された固有ベクトルによって求められる部分空間上への射影及び前記選択された固有ベクトルへの近似を改善する反復方法のうちの一方又はそれらの組み合わせを用いて決定される、請求項１２に記載の方法。
【請求項１４】
前記反復方法は、クルイロフに基づく反復方法、近似クルイロフに基づく反復方法、有理クルイロフ部分空間、近似有理クルイロフ部分空間、部分空間反復方法、及びそれらの組み合わせからなる群から決定される、請求項１３に記載の方法。
【請求項１５】
前記反復方法のパラメーターは、前記選択された固有値に基づいて求められる、請求項１２に記載の方法。
【請求項１６】
前記クラスター解析は、クラスターを求め、前記操作を前記決定するステップは、
前記反発スペクトルの全ての固有値又は最小の固有値、前記中立スペクトルの全て又は一部分、及び前記引き付けスペクトルの最小の固有値、並びにそれらの組み合わせからなる群から選択される前記ラプラシアン行列の固有値を求めるステップと、
閾値を用いて、前記選択された固有値内のギャップを求めるステップと、
前記ギャップよりも小さい側に位置する前記選択された固有値に対応する前記ラプラシアン行列の前記固有ベクトルの集合を求めるステップと、
前記固有ベクトルの前記集合内の前記固有ベクトルの構成要素の符号及び振幅を解析することによって、前記データ内のプリクラスターを求めるステップであって、前記対応する構成要素が類似しているとき、前記データ点は、同じプリクラスターに割り当てられる、ステップと、
前記プリクラスターの前記グラフの接続性を解析することによって、前記クラスターを求めるステップであって、前記データ点が、前記プリクラスターによって求められるサブグラフにおいて接続されているとき、前記データ点は、同じクラスターに割り当てられる、ステップと
を更に含む、請求項２に記載の方法。
【請求項１７】
所定の数の再帰ステップ及び前記クラスターのサイズに関する閾値のうちの一方又はそれらの組み合わせを用いて、終了条件に達するまで、各クラスターを新たなデータとして扱うことによって、請求項１６に記載の方法を再帰的に繰り返すこと
を更に含む、請求項１６に記載の方法。
【請求項１８】
前記ギャップよりも小さい固有値が１つだけあり、
前記対応する固有ベクトルは、正の符号及び負の符号の双方の構成要素を有する固有ベクトルの集合における唯一の固有ベクトルであり、
前記プリクラスターは、同じ符号を有する構成要素をグルーピングすることによって求められる、請求項１６に記載の方法。
【請求項１９】
前記データ点が前記クラスターに属する確率の行列を求めること、
を更に含み、前記行列内の各列は、前記データ点が各クラスターに属する確率を表し、前記行列の列の範囲は、前記ラプラシアン行列の前記固有ベクトルの前記集合のスパンを近似する、請求項１６に記載の方法。
【請求項２０】
前記１つ又は複数のプロセッサは、少なくとも１つのプロセッサ、マルチコアコンピュータープロセッサユニット、グラフィックス処理ユニット、フィールドプログラマブルゲートアレイ、及び専用並列コンピュータークラスターの組み合わせを含む、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の分野は、データ解析及び信号処理であり、より詳細には、産業用途においてセンサーから取得されたデータ点をクラスターに分割すること、及び信号雑音除去等の信号のグラフに基づく処理である。
【背景技術】
【０００２】
スペクトル分割を介したデータクラスタリング
データ取得技術、データ通信技術、及びデータ記憶技術のコストが急速に減少することによって、大量のデータを蓄積することが経済的に実現可能になっている。そのようなデータの使用法のうちの１つは、機械設備又は電気設備内の欠陥を示す場合がある異常状態の自動化された発見（automated discovery）である。そのような欠陥は、脆い又は壊れた構成要素、正しくない動作シーケンス、通常でない動作状態等を含み得る。ほとんどの場合、そのような異常状態を即座に発見することが、労働者及び顧客の安全性の確保、材料の浪費の最小化、又は更に大きな破局故障を回避するための保守の実行のために非常に望ましい。正常な動作限界は、データ駆動型手法によって得ることができる。このデータ駆動型手法では、データ変数が、保証された正常な状態の下で測定され、正常な動作範囲の記述子がこのデータから抽出される。
【０００３】
スペクトル分割を介したデータクラスタリングは、高品質のクラスターを生成することで知られている、異常検出における最新のツールである。スペクトル分割の計算部分は、固有値問題の数値解法部である。データの多変量統計及びクラスタリングでは、スペクトル分割技法は、クラスタリング前に、データの類似度行列又は関連行列のスペクトル（固有値）を利用して次元削減（dimensionality reduction）を行い、次元を少なくする。この類似度行列は、入力として提供され、データ集合内の点の各ペアの相対類似度の定量的評価からなる。グラフ分割の重要な用途には、科学計算、例えば、マルチプロセッサシステムにおけるタスクスケジューリングが含まれる。近年、グラフ分割問題は、ソーシャルネットワーク及び生体ネットワークにおけるクリークのクラスタリング及び検出に適用されていることから、重要性が増している。
【０００４】
Ｎ個のデータ点の集合が与えられると、類似度行列（２次元アレイ）は、ｉ及びｊによってインデックス付けされたこの集合内の点の間の類似度の尺度を表すエントリーａｉｊを有するＮ×Ｎ行列Ａとして定義することができる。類似度行列は、データ点の間の類似度を表すスコアの行列とみなすことができる。類似度行列は、それらの対応するものである距離行列から一般に求められる。この距離行列は、点の集合の、ペアにされた距離を含む行列である。概ねの関係は、距離が大きい場合に類似度は小さく、距離が小さい場合に類似度は大きいということである。
【０００５】
一般に、データクラスタリング問題は、グラフ分割問題として定式化される。グラフ分割問題は、グラフＧを、特定の性質を有するそれよりも小さな構成要素に分割することが可能なようなＮ個の頂点Ｖ及びＭ個のエッジＥを有するグラフＧ＝（Ｖ，Ｅ）の形で表されるデータに対して定義される。例えば、ｋ分割は、頂点集合をｋ個のそれよりも小さな構成要素に分割する。良好な分割は、分離された構成要素間のエッジの数が少ない分割として定義される。一様なグラフ分割は、構成要素がほぼ同じサイズであるとともに構成要素間の接続の数が相対的に少なくなるように、グラフを構成要素に分割することからなるタイプのグラフ分割問題である。
【０００６】
グラフ隣接行列Ａは、エントリーａｉｊ＝ｗｉｊ≧０を有する。ここで、ｗｉｊ≧０は、ノードｉとノードｊとの間のエッジの重みである。次数行列Ｄは、行ｉの各対角エントリーがノードｉのノード次数を表す対角行列である。グラフのラプラシアン行列Ｌは、Ｌ＝Ｄ−Ａとして定義される。Ｌの２番目に小さな固有値λ≧０に対応するＬの固有ベクトルは、フィードラー（Fiedler）ベクトルと呼ばれ、固有ベクトルのエントリーの符号に基づいて、グラフＧを２つのクラスターにのみ二分する。
【０００７】
図１は、従来技術のスペクトル二分法の１つの例を示している。図１におけるグラフは、接続されておらず、２つのサブグラフ１０１  Ｇ（１，２，３）及び１０２  Ｇ（４，５）を有する。全ての可視のエッジは、同じ重み１を有する。グラフラプラシアン１０３は、５×５行列である。
【０００８】
Ｌのフル固有値分解は、１０４によって与えられる。行列Ｖのいずれの列も、Ｅにおいて与えられる固有値に対応する固有ベクトルである。例えば、最小の固有値１０５は０である。２番目に小さな固有値はλである。
【０００９】
対応する固有ベクトル１０７を有する１０６も、この例では０である。固有ベクトル１０７の最初の３つの構成要素であるノードｉｄ  １，２及び３は０であるが、一方、ノードｉｄ  ４及び５を有する最後の２つは負であり、これは、このグラフをサブグラフ１０１  Ｇ（１，２，３）及び１０２  Ｇ（４，５）に二分することを提案している。サブグラフ１０１  Ｇ（１，２，３）及び１０２  Ｇ（４，５）は、互いに接続されていないので、この二分は最適である。
【００１０】
図２には、同じく重み１を有する１つの新たなエッジ２１１を有することのみを除いて、図１とほとんど同じグラフが示されている。更新されたグラフラプラシアン２０３は、依然として５×５行列であるが、幾つかの更新されたエントリーを有する。Ｌのフル固有値分解は、２０４によって与えられる。行列Ｖのいずれの列も、Ｅにおいて与えられる固有値に対応する固有ベクトルである。例えば、最小の固有値２０５は、グラフラプラシアンの場合に常に予想されるように、依然として０である。２番目に小さな固有値λ２０６は、対応する固有ベクトル２０７を有するこの例では非ゼロ（nonzero）である。固有ベクトル２０７の最初の３つの構成要素であるノードｉｄ  １，２及び３は正であるが、一方、ノードｉｄ  ４及び５を有する最後の２つは負であり、これは、このグラフをサブグラフ１０１  Ｇ（１，２，３）及び１０２  Ｇ（４，５）に二分することを示唆している。このように、この例におけるスペクトラルクラスタリングは、フィードラーベクトル２０７を用いて、グラフを、均衡の取れた２つの構成要素に二分する。一方の構成要素１０１は、フィードラーベクトル２０７内の正の構成要素に対応する頂点｛１，２，３｝を有し、他方の構成要素１０２は、フィードラーベクトル２０７内の負の構成要素に対応する頂点｛４，５｝を有する。
【００１１】
従来のスペクトラルクラスタリング手法の主な制限は、例えば、その構成が、データ集合内の点の各ペアの相対類似度の定量的評価を記述する距離に基づいているとき、基本的には、非負（nonnegative）でなければならないグラフエッジの重みに基づくその定義に組み込まれている。グラフエッジの非負の重みは、非負のエントリーを有するグラフ隣接行列Ａをもたらす。
【００１２】
多くの実際上の問題、例えば、時系列のための異常検出では、データ点は、それらの対比較（pairwise comparison）に相関の使用を可能にする特徴ベクトル又は特徴関数を表す。しかしながら、この相関は、負である可能性がある。すなわち、より一般的には、データ集合内の点は、互いを対比すると、類似していない可能性があり、例えば、或る量は、別の量が減少すると増加するようになっている。
【００１３】
従来のスペクトラルクラスタリングでは、そのような場合に対処して利用することができる唯一の可能な手段は、データ点のこの反相関（anticorrelation）、すなわち、負の相関（negative correlation）を、非相関（uncorrelation）、すなわち、０の相関に取り替えることである。この取り替えによって、グラフ隣接行列内の対応する負のエントリーは０に変更され、従来のスペクトラルクラスタリングを進めることが可能になるが、有効な比較は無効になる。したがって、非負のエントリーだけでなく負のエントリーも有するグラフ隣接行列Ａによって表される、相関したデータ及び非相関のデータ並びに反相関のデータを直接扱うデータクラスタリングスペクトル分割方法を提供することが必要とされている。
【００１４】
グラフ信号処理
信号処理における広範囲の用途が、データの幾何構造を記述するグラフの頂点上に表すことができるデータを示している。これらの用途には、社会構造物、エネルギー構造物、及び運搬用構造物、並びにセンサーネットワーク、更には合成画像及び自然画像、ビデオ、並びに医療画像及びハイパースペクトル（hyper-spectral）画像が含まれる。グラフ信号処理ツールは、従来の画像処理用途及びビデオ処理用途において用いられてきた。
【００１５】
例えば、画像処理用途の場合、画像内のピクセルをグラフ内のノードとして取り扱うことができる一方、それらのノードを接続するエッジ上の重みは、それらのエッジによって接続されたピクセルの類似度の尺度を表す。画像又は画像スライス内の全てのピクセルが、単一のグラフを共有し、１つのグラフスペクトル領域内で処理される。グラフ内の接続構造が定義された後、多くの場合、空間ペナルティ及び強度距離ペナルティを用いて、重みｗｉｊ≧０が各グラフエッジに割り当てられる。
【００１６】
グラフの隣接行列Ａは、エントリーａｉｊ＝ｗｉｊ≧０を有する対称Ｎ×Ｎ行列であり、対角次数行列は、Ｄ：＝ｄｉａｇ｛ｄ１，ｄ２，．．．，ｄＮ｝である。グラフラプラシアン行列Ｌ＝Ｄ−Ａは、対称半正定値（symmetric positive semi-definite）であり、したがって、固有値分解Ｌ＝ＵΛＵＴが認められる。ここで、Ｕは、固有ベクトルの正規直交集合を形成する列を有する直交行列であり、Λ＝ｄｉａｇ｛λ１，．．．，λＮ｝は、全て非負の対応する固有値から構成される行列である。
【００１７】
ラプラシアン行列の固有値及び固有ベクトルは、グラフ信号のスペクトル解釈を提供し、この場合、固有値は、グラフフーリエ周波数として扱うことができ、固有ベクトルは、一般化されたフーリエモードとして扱うことができる。グラフスペクトルフィルタリングＨを、グラフスペクトル領域における画像処理の目的で設計することができる。ここで、Ｈは、対角行列であり、通常、Ｈ＝ｈ（Λ）として与えられる。ここで、ｈ（λ）は、フィルターを決定する実数変数λの実数値関数である。頂点領域における対応するグラフフィルターＨは、Ｈ＝ｈ（Ｌ）＝ＵＨＵＴとして表すことができる。
【００１８】
グラフ信号処理用及びスペクトル分割を介したデータクラスタリングの目的用のグラフ隣接行列Ａ及びグラフラプラシアン行列Ｌは、同様に構築され、グラフの重みが非負でなければならないという前提に起因した同じ制限を共有する。この前提をなくすことによってこの制限を取り除き、正の類似度及び負の類似度の双方を生成するデータ比較方法をグラフに基づくデータ処理に用いることを可能にする必要がある。
【発明の概要】
【発明が解決しようとする課題】
【００１９】
本発明の実施の形態は、入力データを処理する方法を提供する。この入力データは、データ点からなり、各データ点は、データ内の要素である。このデータのラプラシアン行列が求められる。このラプラシアン行列は、グラフラプラシアン行列として求めることができる。このラプラシアン行列は、正の固有値の引き付けスペクトル（attractive spectrum）と、負の固有値の反発スペクトル（repulsive spectrum）と、０の固有値の中立スペクトル（neutral spectrum）とを有する。
【００２０】
グラフに基づく従来のデータ処理方法は、非負のスペクトルのみを有するラプラシアン行列を用い、これによって、従来のデータ処理方法は、負の類似度が可能であり望ましい多くの用途にとって不適切なものになっている。したがって、本発明は、負のスペクトルがラプラシアン行列において許容されるときに、データ処理の品質が改善されるという認識に基づいている。
【００２１】
本方法は、ラプラシアン行列を用いるとともに、引き付けスペクトル、反発スペクトル、及び中立スペクトルについての情報を用いて、データの処理のための操作を決定することによって継続する。この情報は、これらのスペクトルと、例えば、スペクトル内の最大値若しくは最小値、スペクトルに存在する固有値の数、又はスペクトル内の固有値密度等のこれらのスペクトルから導出された性質とを含む。次に、本方法は、入力データに対して操作を実行して、処理されたデータを出力として生成する。
【００２２】
本発明の主な認識は、機械式振動モデルを解析することによってもたらされている。バネ質量体の系では、しっかりと接続された質量体は、低周波数自由振動で同期して動く傾向を有する。系の低周波数振動モードの種々の質量体に対応する構成要素の符号を解析することによって、クラスターを求めることが可能になる。
【００２３】
機械式振動モデルは、全てのバネが、質量体間で引力（attracting force）を生み出すように事前に緊張されているときは、従来のクラスタリングを記述することができる。本発明は、２つの質量体間に斥力（repulsive force）を生み出すようにバネのうちの幾つかを事前に緊張させることもできるという認識に基づいている。グラフ分割として定式化されるデータクラスタリングに関して、それは、隣接行列内の負のエントリーに対応する。隣接行列内の負のエントリーは、従来のグラフスペクトラルクラスタリングでは許容されていない。しかしながら、反発バネを有するバネ質量体の系の機械式振動のモデルは、本発明においては有効である。
【００２４】
バネ質量体の系では、引き付けられる質量体は、低周波数自由振動で同じ方向に互いに同期して動く傾向を有する一方、反発している質量体は、反対方向に同期して動く傾向を有する。斥力は、幾つかの質量体を反発させて引き離す不安定な定在波が存在するという新たな現象を生み出す。この反発現象は有利であり、負の類似度を有するデータ点を区別することによってデータ処理の品質を高める。
【００２５】
本方法の主な用途には、クラスター解析、予測解析、パターン認識、相関ルール学習、異常検出、分類、モデル化、要約、サンプリングに加えて、信号品質改善、フィルタリング、圧縮、サンプリング、特徴抽出、及び信号雑音低減が含まれる。
【図面の簡単な説明】
【００２６】
【図１】従来技術のクラスタリングの概略図である。
【図２】従来技術のクラスタリングの概略図である。
【図３】本発明の実施形態によるラプラシアン行列のスペクトルを用いてデータを処理する方法の流れ図である。
【図４】本発明の実施形態によるラプラシアン行列のスペクトルの概略図である。
【図５】本発明の実施形態によるデータ点をクラスタリングする方法の流れ図である。
【図６】（ａ）従来技術によるグラフ二分と（ｂ）本発明の実施形態によるグラフ二分とを比較した図である。
【図７】本発明の実施形態による準粒子を用いた波動方程式の振動モデルの概略図である。
【図８】本発明の実施形態による引き付けバネ及び反発バネを有する振動モデルの概略図である。
【図９】図１０と比較するために、従来技術の質量体バネモデルを用いた質量体のクラスターの変位を示した概略図である。
【図１０】図９と比較するために、本発明の実施形態によるモデルを用いた質量体のクラスターの変位を示した概略図である。
【発明を実施するための形態】
【００２７】
図３に示すように、本発明の実施形態は、入力データ３０１を処理する方法を提供する。ここで、入力データは、データ点からなり、各データ点は、データ内の要素である。
【００２８】
本方法は、データのラプラシアン行列Ｌ  ３１１を求める（３１０）。スペクトルの詳細について、図４を参照して説明することにする。従来のグラフに基づくデータ処理は、非負のスペクトルのみを有するラプラシアン行列を用いる。本発明は、負のスペクトルも許容されるとき、データ処理の品質が改善されるという認識に基づいている。
【００２９】
次に、ラプラシアン行列を用いてデータを処理するための操作（operation）３２１が、引き付けスペクトル（attractive spectrum）、反発スペクトル（repulsive spectrum）、及び、中立スペクトル（neutral spectrum）についての情報を用いて決定される（３２０）。詳細については図４を参照されたい。この情報は、これらのスペクトルと、例えば、スペクトル内の最大値若しくは最小値、スペクトルに存在する固有値の数、又はスペクトル内の固有値密度等のこれらのスペクトルから導出された性質とを含む。
【００３０】
操作が決定されると、次に、この操作が、入力データ３０１に対して実行され、処理されたデータ３０２を生成する。この処理されたデータ３０２が、本方法の出力である。これらのステップは、当該技術分野において知られているように、バスによってメモリ及び入力／出力インターフェースに接続された１つ又は複数のコンピュータープロセッサにおいて実行することができる。
【００３１】
ラプラシアン行列のスペクトル
図４は、ラプラシアン行列Ｌのスペクトルの概略図である。このスペクトルは、実数４００のライン上にある固有値４０４として定義される。ラプラシアン行列Ｌは対称であり、したがって、固有値は全て実数である。スペクトルは、正の固有値の引き付けスペクトル４０１と、負の固有値の反発スペクトル４０２と、０の固有値の中立スペクトル４０３とを含む。中立スペクトル４０３は、値が０に等しい複数の場合もあり得る固有値４１０からなる。引き付けスペクトルは、ギャップ４０５を有し、固有値４０６は、このギャップよりも小さい。
【００３２】
本方法について、２つの主な用途タイプが特定される。第１のタイプは、クラスター解析、予測解析、パターン認識、相関ルール学習、異常検出、分類、モデル化、要約、サンプリング、及び圧縮のうちの１つ又はそれらの組み合わせを目的としたデータ処理である。本明細書は、この第１のタイプのデータ処理の例としてクラスター解析及び異常検出に的を絞る。
【００３３】
第２のタイプの用途は、データが信号であり、これらの信号の処理が品質改善、フィルタリング、サンプリング、圧縮、及び特徴抽出、並びにそれらの組み合わせからなる群から選択される場合を含む。データ品質改善及び信号フィルタリングの特定の例として信号雑音低減を含む第２のタイプのデータ処理の例が提供される。これらの双方は、グラフに基づいている。
【００３４】
１つの実施形態では、ラプラシアン行列Ｌは、グラフラプラシアン行列として求められる。このグラフラプラシアン行列は、グラフを用いて表されるデータについて求められる。データを表すグラフの一般的な例は、データ点がグラフ頂点を表し、グラフエッジが当該グラフエッジの重みに関連付けられている場合のものである。グラフエッジの重みは、あらゆるデータ点を他の各データ点と相互に対比較したものを表すグラフ隣接行列Ａ内のエントリーとしての役割を果たす。
【００３５】
無向グラフ（undirected graph）Ｇ＝（Ｖ，Ｅ）は、エッジの集合Ｅ＝｛（ｉ，ｊ，ｗｉｊ）｝，ｉ，ｊ∈Ｖによって接続されたノードとも呼ばれる頂点の集合Ｖ＝｛１，２，．．．，Ｎ｝を含む。ここで、（ｉ，ｊ，ｗｉｊ）は、重みｗｉｊに関連付けられたノードｉとノードｊとの間のエッジを表し、この重みは、正、０、又は負とすることができる。負の重みが存在することが、全ての重みが非負でなければならない従来技術との主な相違である。ノードｉの次数ｄｉは、ノードｉに接続されたエッジの重みの和である。負の重みのために、少なくとも幾つかの次数は０である場合があり、そのため、次数の反転に基づく従来の正規化されたグラフラプラシアン行列は、定義することができない。
【００３６】
更なる実施形態では、データのグラフ隣接行列が、当該グラフ隣接行列のエントリーを用いて求められ、これらのエントリーは、あらゆるデータ点を他の各データ点と対比較することによって求められる。エントリーは、類似のデータ点のペアの場合には正であり、本質的に異なるデータ点のペアの場合には負であり、無相関のデータ点のペアの場合には０であり、エントリーの振幅は、正の場合には類似度のレベルを定量化したものであり、負の場合には差異を定量化したものである。
【００３７】
次に、グラフラプラシアン行列が、グラフ次数行列からグラフ隣接行列を減算することによって求められる。このグラフ次数行列は、対角行列として求められ、この対角行列のいずれの対角エントリーも、その対角エントリーを有する同じ行におけるグラフ隣接行列の行の和である。
【００３８】
グラフ隣接行列Ａ内の負のエントリーを直接取り扱うことができるスペクトル分割方法について説明することにする。この方法は、対称な類似度行列Ａを用いて、その頂点が問題領域における個々の変数に対応し、２つの変数ｉ及びｊの間のエッジが重みａｉｊを有するグラフのグラフラプラシアンＬ＝Ｄ−Ａを形成する。従来の方法とは対照的に、重みａｉｊは負とすることができる。
【００３９】
図５は、本発明の実施形態によるデータ点１０１をクラスタリングする方法を示している。これらのデータ点は、互いに対比較され（５１０）、例えばデータ点の相関として求められる正及び負のエントリー５１２を有するペアワイズ類似度行列５１１が求められる。この類似度行列は、固有値５２２を有するグラフラプラシアン行列Ｌ  ５２１を求めるためのグラフ隣接行列Ａとして用いられる。選択される固有値の固有ベクトル５５０が決定される（５３０）。次に、データ点が、選択された固有ベクトル５５０を用いてクラスター５４１にクラスタリングされ（５４０）、例えば、選択された固有ベクトル５５０の構成要素の符号を用いてクラスタリングされる。本方法は、１つ又は複数のプロセッサ３００において実行することができる。
【００４０】
グラフ隣接行列内に非負のエントリー及び負のエントリーを許容する、図５に記述されたクラスタリング方法は、データ点のペアが本質的に異なる状況をグラフ隣接行列において明示的に表すことができ、したがって、その後のデータ処理の品質が改善されるので有利である。従来技術では、グラフ隣接行列内のエントリーは、全て非負でなければならず、これによって、多くの実際的な用途において利用可能な負のデータの比較が認められない。
【００４１】
例えば、実用上重要な場合は、データ点が、或る基礎となる元データの特徴ベクトルであるか、又はそれ自体がベクトルそのものである場合である。１つの実施形態では、データ点の対比較は、相関又は共分散に基づいて求められる。この相関及び共分散は、２つのベクトルが正に相関しているのか、負に相関しているのか、又は無相関であるのかに応じて、グラフ隣接行列のエントリーが正、負、又は０となるように、ベクトル間の一次従属を定量化する。この実施形態は、相関又は共分散がデータ点の少なくとも幾つかのペアについては負であっても、相関又は共分散をデータ比較に直接用いることで、その後のデータ処理の品質が改善される可能性があるので、有利である。従来技術では、ベクトルは、通常、全て非負のエントリーを有するグラフ隣接行列をもたらすカーネル距離関数を用いて比較される。
【００４２】
別の実施形態では、ベクトルは、時系列データの特徴ベクトルであり、これは、データ処理の実用上重要な例のうちの１つである。例えば、時系列データ内の異常を検出することはよく行われている。
【００４３】
正のエントリー及び負のエントリーの双方を有するグラフ隣接行列は、正の固有値及び負の固有値を有するグラフラプラシアンをもたらすことができる。これとは対照的に、従来のグラフラプラシアンは、非負の固有値のみを有する非負定値（nonnegative definite）である。なぜならば、従来のグラフに基づくデータ処理における従来のグラフ隣接行列には、非負の値しか許容されないからである。従来の手法においては、グラフラプラシアンの負の固有値の反発スペクトルの存在が可能ではなく、従来のグラフに基づくデータ処理に用いられる従来のツールを変更する必要が生じる。
【００４４】
図６（ａ）及び図６（ｂ）は、従来技術のグラフ二分を本発明の実施形態によるグラフ二分と比較したものである。図６（ａ）の従来技術では、負の重みを有するグラフエッジが除去される（６０１）。なぜならば、隣接行列内の負のエントリーは、従来技術では許容されず、０に取り替える必要があるからである。グラフ内に負の重みを有するグラフエッジが維持される（６０２）と、それらの負の固有値は、良好な分割６１０をもたらす。なぜならば、負の重みを有するグラフエッジは、分割に反発するからである。詳細については図８を参照されたい。
【００４５】
本発明は、グラフラプラシアンが負の固有値の反発スペクトルを有するとき、グラフは、モデルを用いて記述することができるという認識に部分的には基づいている。これらのモデルの例には、波動方程式の振動モデル及び拡散方程式の濃度拡散モデルの２つの例が考えられる。
【００４６】
図７に示すように、１つの実施形態では、ラプラシアン行列を求めることは、波動方程式の振動モデルに基づく。当該求めることは、次の３つのステップを含む：
データを表す振動モデルを求めるステップであって、ここで、振動モデルは、振動を受けて相互作用する準粒子７０１で構成された系を記述したものであり、振動モデルの各準粒子は、データ点のうちの１つに対応し、振動モデルの相互作用係数は、データ点の対比較によって求められるものであって、ペア内のデータ点が類似している場合には、相互作用は引き付け（７０３）であるとともに相互作用係数は正であり、又は、ペア内のデータ点が比較可能でないときは、相互作用は存在しない（７０４）とともに相互作用係数は０であり、又は、ペア内のデータ点が本質的に異なるときは、相互作用は反発（７０２）であるとともに相互作用係数は負であって、相互作用の強度及び相互作用係数の振幅は、類似度又は差異のレベルを表す、ステップ；
波動方程式の振動モデルの固有モードを求めるステップであって、この固有モードは、固有値問題の固有ベクトルである、ステップ；および
固有値問題からラプラシアン行列を求めるステップ。
【００４７】
図８に示すように、異なる実施形態において、振動モデルは、質量８０１体及びバネ８０３、８０４からなる質量体バネ系を表し、質量体は、準粒子であり、バネの剛性は、質量体の相互作用によって求められ、相互作用が引き付けであるとき、引き付けバネ８０４は、２つの質量体を引き付け、相互作用が反発であるとき、反発バネ８０３は、２つの質量体を反発させ、質量体バネ系は、横振動を受け、この横振動は、質量体が質量体バネ系の平面８０２に対して垂直な横方向８０５にのみ動くことを可能にする。
【００４８】
異なる実施形態が第２の代替的なモデルを表しており、ラプラシアン行列を求めることは、拡散方程式の濃度拡散モデルに基づく。当該求めることは、次の３つのステップを含む：
データを表す拡散方程式の濃度拡散モデルを求めるステップであって、濃度拡散モデルは、濃縮又は拡散を受けて相互作用する準粒子で構成された系であり、濃度拡散モデルの各準粒子は、データ内の点に対応し、モデル準粒子相互作用伝導係数は、データ点の対比較によって求められるものであって、ペア内のデータ点が類似している場合には、相互作用は拡散性であるとともに相互作用伝導係数は正であり、又は、ペア内のデータ点が比較可能でない場合には、相互作用は存在しないとともに相互作用伝導係数は０であり、又は、ペア内のデータ点が本質的に異なるときは、相互作用は濃縮性であるとともに相互作用伝導係数は負であって、相互作用の強度及び相互作用係数の振幅は、類似度又は差異のレベルを表す、ステップと；
拡散方程式の濃度拡散モデルの固有モードを求めるステップであって、固有モードは、固有値問題の固有ベクトルである、ステップと；および
ラプラシアン行列を固有値問題の行列として求めるステップ。
【００４９】
非常に異なるにもかかわらず、波動方程式の振動モデル及び拡散方程式の濃度拡散モデルが、定在波（standing waves）と呼ばれることもある、それらの固有モードを求めることは、時間変数及び空間変数を分離した後は、同じ固有値問題に還元することができることが分かる。
【００５０】
したがって、別の実施形態では、波動方程式の振動モデル及び拡散方程式の濃度拡散モデルにおけるラプラシアン行列は、グラフラプラシアン行列として求めることができ、このグラフラプラシアン行列は、グラフを用いて表されるデータについて求められ、したがって、これらのモデルは、グラフに基づくデータ処理に結び付けられる。この認識によって、２つのモデルのうちのいずれかの解の時間依存の挙動の解析に基づくデータ処理という目的において、ラプラシアン行列における反発スペクトルをどのように扱うのかを求めることが可能になる。
【００５１】
例えば、波動方程式の振動モデルでは、反発スペクトルにおける負の固有値に対応するいずれの固有モードも、構成要素間の相互作用が反発であるとき、それらの構成要素の振動の振幅を増加させることに寄与する。構成要素の振動の振幅の増加は、それらの構成要素がデータクラスタリングという目的において同じクラスターに現われる可能性が低いことを示すものである。この増加は、クラスターを求めることをより単純にするので有利である。この議論も、反発スペクトルが、引き付けスペクトルと比較して、更には中立スペクトルと比較しても、より重要であることを示唆し、したがって、クラスタリングに関連した以下の実施形態において優先的に取り扱われるべきである。
【００５２】
データ分割という目的において、反発固有モードの構成要素の振動の振幅の有利な増加は、図９及び図１０に示されている。図９及び図１０は、それぞれ図６（ａ）及び図６（ｂ）と相補的である。図９は、引き付けバネ８０４のみを有する従来技術の振動モデルを示している。系の中央における平衡状態９１０からの質量体８０１の変位９０５は比較的小さく、そのため、クラスター９０１は、検出するのが困難である。
【００５３】
図１０では、反発バネ８０３が、系の中央における平衡状態１０１０からの質量体の変位を増加させ、したがって、クラスター１００１は、従来技術のクラスター９０１と比較して検出するのがより容易であるとともに検出の信頼性がより高い。
【００５４】
１つ又は複数の制約をグラフラプラシアン行列の固有ベクトルに課す可能性について更に説明することにする。これらの１つ又は複数の制約は、特定の固有ベクトルの構成要素を０に設定すること、固有ベクトルの構成要素のスパース性を課すこと、および、固有ベクトルが所与のベクトルの集合に対して垂直であることを要すること、のうちの１つ又はそれらの組み合わせである。これらの制約は、準教師（セミ・スーパーバイザー）付きの学習をグラフに基づくデータ処理に組み込む機会をデータ科学者に与えるので、当該制約を有することは有利である。例えば、当該制約は、類似のデータに対して以前実行されたデータ処理手順から得ることができる。
【００５５】
次に、データ処理の操作を決定する幾つかの実施形態を、ラプラシアン行列の様々なスペクトルを異なって取り扱う必要があるという認識に基づいて手短に要約することにする。１つの実施形態では、この操作を決定することは、次の２つのステップを含む：
ラプラシアン行列の選択される固有値及び対応する固有ベクトルを決定するステップであって、選択される固有値は、引き付けスペクトル、反発スペクトル、中立スペクトル、引き付けスペクトルの対象となる固有値、反発スペクトルの対象となる固有値、及び、中立スペクトルの対象となる固有値のうちの１つ又はそれらの組み合わせに基づいている、ステップ；および、最後に、
ラプラシアン行列並びにラプラシアン行列の上記選択された固有値及び上記対応する固有ベクトルを用いて操作を決定するステップ。
当該固有値は、データ処理の特定の操作の必要性に応じて目標とされる。例えば、信号を表すデータの低域通過のグラフに基づくフィルタリングの場合、対象となる固有値は、図４に示すように、存在する場合には、反発スペクトルから開始する、帯域閾値を用いたギャップ４０５よりも小さい４０６のラプラシアン行列の最小の固有値となる。
【００５６】
更なる実施形態は、選択された固有ベクトルによって求められる部分空間上への射影、及び、選択された固有ベクトルへの近似を改善する反復方法、のうちの一方又はそれらの組み合わせを用いて操作を決定する。
【００５７】
部分空間は、例えば、対象となる固有値に対応する選択された固有ベクトルのスパンへの近似とすることができる。この手順の効率の鍵となるものは、行列Ｌの対象となる固有値を高速に求めることである。これは、例えば、ランチョス（Lanczos）方法又は局所最適ブロック前処理付き共役勾配（ＬＯＢＰＣＧ：Locally Optimal Block Preconditioned Conjugate Gradient）方法によって行うことができる。ランチョス方法及びＬＯＢＰＣＧ方法は、メモリ内に行列Ｌ全体を必要とせず、行列Ｌに所与のベクトルを乗算した結果のみを必要とする。これらの方法のこの特性によって、これらの方法は、非常に高い次元の固有値解析問題に適用可能になり、類似度行列全体をメモリに記憶する必要がなくなり、したがって、その結果、非常に大きな行列サイズへのスケーラビリティ（scalability）が得られる。
【００５８】
別の実施形態において、反復方法は、例えば、クルイロフ（Krylov）に基づく反復方法、近似クルイロフに基づく反復方法、有理クルイロフ部分空間、近似有理クルイロフ部分空間、部分空間反復方法、及びそれらの組み合わせからなる群から決定される。クルイロフに基づく反復方法は、例えば、行列を用いない形式（matrix-free fashion）で実施することができ、ラプラシアン行列の記憶を必要とせず、逆に、ラプラシアン行列とベクトルとの積を得る機能へのアクセスしか必要としないので有利である。例えば、有理クルイロフ部分空間は、複雑なフィルター関数の高品質の近似を可能にするので有利である。
【００５９】
例えば、低域通過フィルター及び高域通過フィルターのうちの一方又はそれらの組み合わせに関心がある場合、次数（ｋ＋１）のクルイロフ部分空間がＫ＝ｓｐａｎ｛ｂ，Ｌｂ，．．．，Ｌｋｂ｝として定義されるクルイロフ部分空間射影技法を用いることができる。初期ベクトルｂは、例えば、入力信号とすることができる。クルイロフ部分空間は、極端な固有値に対応する固有ベクトルを良好に近似することができ、したがって、高域通過フィルター及び低域通過フィルターのための適切な選択肢である。
【００６０】
このフィルターは、有理クルイロフ部分空間及びそれらの近似に基づいて構築することもできる。下記の数式で定義される有理クルイロフ部分空間Ｋｒは、極端な固有値と対照的な、内部の固有値を良好に推定し、それによって、帯域通過フィルター及び帯域阻止フィルター（band reject filter）の設計を可能にしている。
【００６１】
【数１】
2016004579.tif 000003
【００６２】
別の重要な実施形態は、選択された固有値に基づいて反復方法のパラメーターを求める。これは、固有値がデータから求められ、これによって、反復方法のパラメーターがデータに柔軟に適応し、したがって、速度及び品質の双方の点で操作（operation）の性能が高まる可能性があるので有利である。
【００６３】
最適な多項式低域通過フィルターの一例は、チェビシェフ（Chebyshev）多項式に基づいている。具体的には、次数ｋのチェビシェフ多項式ｈｋ−ＣＨＥＢを区間［ａ，ｂ］にわたる阻止帯域（stop band）とともに用いることができる。チェビシェフ多項式の構成は、例えば、次数ｋのチェビシェフ多項式
【数２】
2016004579.tif 000004
の根をｉ＝１．．．ｋについて区間［−１，１］にわたり求め、次いで、線形変換を用いてそれらの根を区間［ａ，ｂ］にシフトさせることで、多項式ｈｋ−ＣＨＥＢの根ｒｉを取得し、ｘｉ＝ｒｉｘｉ−１−Ｌｘｉ−１の値をｉ＝１，．．．，ｋについて反復的に求めることによって処理された信号ｘ＊ｋを計算することによって得ることができる。ここで、ｘ０は、入力信号である。チェビシェフ多項式に基づくこの例における新規な点は、ラプラシアン行列Ｌが半正定値でなく、そのため、区間［ａ，ｂ］の選択に注意深くなる必要があるということである。従来技術では、ラプラシアン行列Ｌのスペクトルは、常に非負であり、ラプラシアンが正規化されている場合、２によって制限されている。Ｌの反発スペクトルが存在するとき、一般にラプラシアンも正規化することができない。Ｌの全スペクトル上の境界が、負の固有値からなる反発スペクトルを含めて考慮され、フィルター設計において区間［ａ，ｂ］の端点の値が求められる。例えば、反発スペクトルに対応する固有モードを増幅し、ａ＝０を設定し、ラプラシアン行列Ｌの引き付けスペクトルの上限としてｂの値を求めるようにフィルターが設計される。
【００６４】
次の一連の実施形態は、クラスター解析を取り扱っている。反発スペクトルには、中立スペクトルと比較して優先権が与えられるべきであり、ましてや引き付けスペクトルと比較するとなおさら優先権が与えられるべきである。このため、１つの実施形態では、操作を決定することは、さらに次の５つのステップを含む：
反発スペクトルの全ての固有値又は最小の固有値、中立スペクトルの全て又は一部分、及び、引き付けスペクトルの最小の固有値、並びに、それらの組み合わせからなる群から選択されるラプラシアン行列の固有値を求めるステップ；
閾値を用いて、選択された固有値内のギャップ４０６を求めるステップ；
ギャップよりも小さい側に位置する選択された固有値に対応するラプラシアン行列の固有ベクトルの集合を求めるステップ；
固有ベクトルの集合内の固有ベクトルの構成要素の符号及び振幅を解析することによって、データ内のプリクラスター（pre-clusters）を求めるステップであって、対応する構成要素が類似しているとき、データ点は、例えばｋ平均クラスタリングを用いて、同じプリクラスターに割り当てられる、ステップ；及び
プリクラスターのグラフの接続性を解析することによって、クラスターを求めるステップであって、データ点が、プリクラスターによって求められるサブグラフにおいて接続されているとき、データ点は、同じクラスターに割り当てられる、ステップ。
【００６５】
プリクラスターを求める方法は、バネ質量体の系において、引き付けられている質量体は、低周波数自由振動では同じ方向に互いに同期して動く傾向を有するのに対して、反発している質量体は、反対方向に同期して動く傾向を有するという直感とよく一致する。斥力を有し、質量体を反発させて引き離す不安定な固有モードが存在するという認識は、従来の最新の技術においては利用可能でない。なぜならば、不安定な固有モードは、ラプラシアン行列の全ての固有値が設計によって非負である従来の手法とは対照的なラプラシアン行列の負の固有値に対応するからである。
【００６６】
従来技術とは対照的に、反発スペクトルの存在は、接続されない場合があるプリクラスターをもたらすことができる。クラスターをプリクラスターの接続された構成要素として求める追加のステップが必要となる。提案された実施形態の異なる新規なものは、対角次数行列がその対角上で０の値を有する場合があり、従来の正規化カットシャイ−マリック（normalized-cuts Shi-Malik）方法の定式化を機能させなくする場合があるということである。なぜならば、従来の正規化されたグラフラプラシアン行列を定義することができないからである。
【００６７】
この操作を単独で適用しても、十分なクラスターが得られない場合があり、そのため、異なる実施形態は、所定の数の再帰ステップ及びクラスターのサイズに関する閾値のうちの一方又はそれらの組み合わせを用いた終了条件に達するまで、あらゆるクラスターを新たなデータとして扱うことによって本方法を再帰的に繰り返すことを提案する。
【００６８】
別の実施形態は、本方法の１つの重要な特定の例を取り扱う。この例では、ギャップよりも小さな固有値が１つだけあり、対応する固有ベクトルは、正の符号及び負の符号の双方の構成要素を有する固有ベクトルの集合における唯一の固有ベクトルである。この場合、プリクラスターは、同じ符号を有する構成要素をグルーピングすることによって求められ、したがって、構成要素の類似度を求める特定の例を提供する。
【００６９】
或る用途では、クラスターは、排他的である必要はなく、その代わり、クラスターの確率的記述を求めることが所望される。１つの実施形態は、データ点がクラスターに属する確率の行列を求める。この行列内のいずれの列も、データ点がいずれのクラスターにも属する確率を表し、この行列の列の範囲は、ラプラシアン行列の固有ベクトルの集合のスパンを近似する。
【００７０】
ステップのうちの１つ又はそれらの組み合わせは、１つ又は複数のコンピュータープロセッサを用いて実行することができる。これらのコンピュータープロセッサには、少なくとも１つのプロセッサ、マルチコアコンピュータープロセッサユニット、グラフィックス処理ユニット、フィールドプログラマブルゲートアレイ、及び専用並列コンピュータークラスターの組み合わせが含まれる。
【図１】
2016004579.tif 000005
【図２】
2016004579.tif 000006
【図３】
2016004579.tif 000007
【図４】
2016004579.tif 000008
【図５】
2016004579.tif 000009
【図６】
2016004579.tif 000010
【図７】
2016004579.tif 000011
【図８】
2016004579.tif 000012
【図９】
2016004579.tif 000013
【図１０】
2016004579.tif 000014
【外国語明細書】
2016004579.tif 000015
2016004579.tif 000016
2016004579.tif 000017
2016004579.tif 000018
2016004579.tif 000019
2016004579.tif 000020
2016004579.tif 000021
2016004579.tif 000022
2016004579.tif 000023
2016004579.tif 000024
2016004579.tif 000025
2016004579.tif 000026
2016004579.tif 000027
2016004579.tif 000028
2016004579.tif 000029
2016004579.tif 000030
2016004579.tif 000031
2016004579.tif 000032
2016004579.tif 000033
2016004579.tif 000034
2016004579.tif 000035
2016004579.tif 000036
2016004579.tif 000037
2016004579.tif 000038
2016004579.tif 000039
2016004579.tif 000040
2016004579.tif 000041
2016004579.tif 000042
2016004579.tif 000043
2016004579.tif 000044
2016004579.tif 000045
2016004579.tif 000046
2016004579.tif 000047
2016004579.tif 000048
2016004579.tif 000049
2016004579.tif 000050
2016004579.tif 000051
2016004579.tif 000052
2016004579.tif 000053
2016004579.tif 000054
2016004579.tif 000055
2016004579.tif 000056