量子クラスタリング

量子クラスタリング(QC) は、量子力学の概念的および数学的ツールを使用するデータ クラスタリングアルゴリズムのクラスです。QC は密度ベースのクラスタリングアルゴリズムのファミリーに属し、クラスターはデータ ポイントの密度が高い領域によって定義されます。

QCは2001年にDavid HornとAssaf Gottliebによって初めて開発されました。^[1]

n 次元データ空間内の点の集合が与えられると、QC は各点を、空間内の各点の位置を中心とした幅 (標準偏差) sigma の多次元ガウス分布で表します。これらのガウス分布は合計され、データ セット全体に対する単一の分布が作成されます。(このステップはカーネル密度推定の特定の例であり、Parzen-Rosenblatt ウィンドウ推定量とも呼ばれます。) この分布は、データ セットの量子力学的波動関数であると考えられます。簡単に言えば、波動関数は、空間内のデータ ポイントが存在する可能性のある場所を一般化して記述したものです。

QC は次に、量子ポテンシャルの概念を導入します。時間に依存しないシュレーディンガー方程式を使用して、データ セットの波動関数を安定した解として持つポテンシャル面が構築されます。ポテンシャル面の詳細は、波動関数の対応する詳細よりも、シグマ (ガウス分布の幅) の変化に対して堅牢です。この利点は、QC 開発の当初の動機の 1 つです。

潜在的な表面はデータ セットの「ランドスケープ」であると考えられており、ランドスケープ内の「低い」ポイントはデータ密度の高い領域に対応します。次に、QC は勾配降下法を使用して各データ ポイントをランドスケープ内で「下り坂」に移動し、ポイントが近くの最小値に集まるようにして、データ セット内のクラスターを明らかにします。

QC には、各データ ポイントの周囲のガウス分布の幅シグマである、単一の主要なハイパーパラメータがあります。シグマが十分に小さい場合、すべてのデータ ポイントはランドスケープ内で独自のくぼみを定義し、ポイントは移動しないため、クラスターは作成されません。シグマが十分に大きい場合、ランドスケープは 1 つの滑らかなボウルになり、すべてのデータ ポイントはランドスケープ内の単一のグローバル最小値に集まります。これらの極端な値の間のシグマ値の範囲を調べると、構造の階層など、データ セットの固有の構造に関する情報が得られます。シグマ値が小さいほど、よりきめの細かいローカル構造が明らかになり、シグマ値が大きいほど、全体的なグローバル構造が明らかになります。QC アルゴリズムは、シグマの推奨値または「正しい」値を指定しません。

2009年にマーヴィン・ワインスタインとデビッド・ホーンによって開発された^[2] 動的量子クラスタリング（DQC）は、基本的なQCアルゴリズムをいくつかの点で拡張します。

DQC は QC と同じポテンシャル ランドスケープを使用しますが、古典的な勾配降下法を量子進化法に置き換えます。これを行うには、各データ ポイントを再び個別の波動関数 (幅 sigma の多次元ガウス分布) で表します。次に、時間依存のシュレーディンガー方程式を使用して、指定された量子ポテンシャルにおける各波動関数の経時的進化を計算します。より正確には、小さな時間ステップ値が導入され、波動関数の進化が各時間ステップで繰り返し計算され、各ステップの後にデータ ポイントの新しい予測位置が計算されます。このプロセスにより、各ポイントのデータ空間を通る軌跡が構築されます。進化は、すべてのポイントの移動が停止するまで継続されます。

重要なのは、量子力学のエーレンフェスト定理によれば、この量子発展は、実際には、点が期待通りにポテンシャル地形内を下って移動することと等しいということです。「期待通りに」という部分が重要なのは、古典物理学とは異なり、点の動きはその点の位置におけるポテンシャルの勾配によってのみ左右されるわけではないからです。その代わりに、点の波動関数は地形全体に広がり (ガウス分布は点の位置を中心とします)、波動関数とポテンシャルの複雑な相互作用によって点の動きが決まります。大まかな類推として、地形のうち点の現在の位置より下にある領域は、点を「引き付け」ます。その引き付けは、領域が低いほど強く、点から遠いほど弱くなります。同様に、地形の上方にある領域は点を「反発」します。

したがって、各ポイントの量子進化は、ポテンシャルにおける非局所的な勾配降下法の一種として機能します。この非局所性により、トンネル効果が発生する可能性があります。トンネル効果では、ポイントは、より低い最小値に向かう途中で、ポテンシャル障壁を無視または通過するように見えます。非凸勾配降下法の最大の問題は、ポイントが降下するときに動けなくなる可能性のある、小さくて興味のない局所的最小値が多数存在することです。(この問題は、次元の数が増えるにつれて悪化する傾向があり、これは次元の呪いの一部です。) DQC の非局所勾配降下法とトンネル効果の使用は、この問題の解決策を示しています。

DQC では、時間ステップと各データ ポイントの質量 (トンネル動作の程度を制御) という 2 つの新しいハイパーパラメータが導入されています。シグマの調整は新しいデータ セットを理解する上で不可欠ですが、時間ステップと質量は通常、適切なデフォルト値のままにしておいても、有用な結果が得られます。

量子進化アプローチの重要な欠点は、各ポイントごとにポテンシャル ランドスケープ全体とのやり取りが行われるため、進化の時間的複雑さがデータ ポイントの数に左右されることです。大規模なデータ セットの場合、計算時間はすぐに手に負えなくなります。必要に応じて、DQC はデータ セットから限られた数のポイントを選択して基礎として機能させることで、この問題に対処します(次のセクションを参照)。 ${\displaystyle O(n^{3})}$${\displaystyle O(n^{2})}$

n個のポイントのデータ セットの場合、DQC は基礎となる計算で使用するためにn 個の量子固有状態のセットを作成します。固有状態は正規直交であり、それぞれが各データ ポイントを表すガウス分布の線形結合です。

nが大きい場合、ポテンシャルの作成と個々の点の発展はどちらも であるため、n個の固有状態の使用は計算上扱いにくくなります。この問題を解決するために、DQC では次のように、より限定された基底の選択が可能です。基底として機能するには、基底点がデータセットが占める空間にまたがるようにb 個のデータ ポイント ( b < n ) を選択します。(これは複数の方法で実行できます。重要な目標は、基底点が互いにできるだけ離れるように選択することです。) 次に、DQC はこれらのb個の基底点を使用して b 個の固有状態を構築します。これらの固有状態は基底点を完全に表します。これらはすべての非基底点を表すためにも使用されますが、それらの表現は不完全です。情報の損失はシグマに相対的です。特定の基底に対して、シグマは、基底が非基底点をある程度の妥当な精度で表すために使用できるように十分に大きく選択する必要があります。ある意味では、選択された基底のサイズは、データの構造を「表示」するために使用される「解像度」と考えることができます。 ${\displaystyle O(n^{3})}$

最大の妥当な基底サイズは、利用可能なコンピューティング リソースと、結果を待つ時間の長さによって異なります。2020 年現在、エンタープライズ レベルのコンピューティング リソースにアクセスできない場合、扱いやすい最大の基底サイズは通常 1,500 ～ 2,000 ポイントの範囲です。

DQC は各データ ポイントの軌道を計算し、すべてのデータ ポイントが同時に軌道に沿って移動するアニメーション化された (「動的な」) 視覚化を作成できます。これらのアニメーションは、各ポイントの最終目的地だけでなく、途中の各軌道全体の情報も表示します。特に、アニメーションは特定のクラスターにつながるチャネルの存在を明らかにすることができます (ランドスケープのメタファーでは、これらの構造は川床や湖と考えることができます)。特定の視覚化は最大 3 つの空間次元に制限されていますが、チャネルやその他の構造の外観により、3 次元以上で何が起こっているかを「見る」ことができます。

PCA座標系の使用は、これらの視覚化に役立ちます。最初の 3 つの PCA 次元の軌跡を表示すると、1 つの視覚化に可能な限り多くの情報が詰め込まれます。

これらの軌跡の 3D 視覚化は、軌跡を 3 次元に埋め込むものではありません。軌跡はデータ空間と同じ次元を持ちますが、これは 3 よりもはるかに大きい場合が多く、視覚化は単に高次元の動きを 3D で表示したものにすぎません。

チャネル (「川床」) には、2 つの異なる意味があります。まず、チャネルをサブクラスターとして扱うことができます。サブクラスターでは、異なるサブクラスターがさまざまな方向からメイン クラスターに加わります。次に、チャネルを回帰として扱うことができます。つまり、特定の時間におけるチャネル上の位置 (または、クラスターの中心への到着順序) が、関心のあるメタデータと相関している可能性があります。

QCの変種は、生物学、^{[1] [2 ] [3] [4] [5] [6} ]地質学、^{[3] [7]}物理学、^{[3] [4] [8]}金融、^[3]工学、^[4]経済学など、多くの分野の現実世界のデータに適用されてきました。^{[9]これらのアプリケーションでは、量子ポテンシャルの}すべての根を見つけるための包括的な数学的分析も行われてきました。^[10]

• ビデオ (YouTube.com): 「複雑で高次元のデータから隠れた構造を探る」、マーヴィン・ワインスタイン (SETI トーク)
• ビデオ (YouTube.com): 「大規模で複雑、高密度な生データに隠された驚くべき構造の発見」、マーヴィン・ワインスタイン (SETI トーク)
• ビデオ (YouTube.com): 「量子クラスタリング - 物理学にヒントを得たクラスタリング アルゴリズム」、Sigalit Bechler
• ビデオ (YouTube.com): 「複雑なデータセットからの量子洞察」、Marvin Weinstein (Google での講演)