本プロトコルは、最適なクラスター数を自動的に検出し効率的に分離するハイブリッド量子K-Meanアルゴリズムを用いてがん分類のための遺伝子発現データをクラスタリングし、ノイズの多い中間スケール量子(NISQ)デバイスでのバイオインフォマティクス応用を推進することを目的としています。
研究記事
遺伝子発現における行動的類似性のための量子クラスタリングアルゴリズムを用いたがん予測へのバイオインフォマティクスアプローチ
この記事について
サマリー
要約
本研究は、がん性および非がん性遺伝子発現データを分類するための自動クラスタ検出を備えたハイブリッド量子K-Meansクラスタリングアルゴリズムを導入します。この手法は、状態符号化のための量子多特徴マッピング、スワップテストに基づく量子距離推定、量子勾配ベース最適化を用いて、クラスタ内分散を最小化して最適なクラスタ数を動的に特定します。初期重心は確率比例距離戦略で選択され、安定性と精度が向上します。乳がんデータセットに適用すると、この手法は既存の量子K-Meansアルゴリズムを上回り、シルエットスコア0.641(0.601より)、Calinski-Harabasz指数766.57(617.65より)、Davies-Bouldin指数0.659(0.704)を達成しています。これらの結果は、優れたクラスターのコンパクト性と分離を示しています。提案されたアルゴリズムは反復最適化により時間計算量O(最大N×K×のobs)がやや高いものの、クラスタリング精度、誤差削減、実用実現可能性において、あらかじめ定義されたK量子K平均を大きく上回る性能を発揮しています。高次元データの処理効率と量子ノイズへの耐性は、特に遺伝子発現プロファイルを用いたがん分類における実際のバイオインフォマティクス応用の可能性を示しています。
概要
生体医工学、バイオインフォマティクス、統計学、社会科学、経済学において、クラスタリングはデータを意味のある均質なグループに組織化するための基本的な手法です。例えば、トポロジカルデータ解析(TDA)は、高次元空間における構造パターンを明らかにするためにがん遺伝子発現データセットに適用されています。1、クラスタリングは、類似度の高いオブジェクトを同じクラスタ内に配置し、異なるオブジェクトを異なるクラスタに割り当てるようにデータを整理します。これは教師なし学習に該当し、ラベル付きトレーニングデータは必要ありません。
過去数十年にわたり、多数のクラスタリングアルゴリズムが開発されてきました。古典的なアプローチには、分割ベースのクラスタリング2˒3、密度ベースのクラスタリング4,5、階層的クラスタリング6,7、グリッドベースのクラスタリング8˒9、モデルベースのクラスタリング10があります。これらの手法のレビューでは、その強みと限界が強調されています。特定の文脈では効果的ですが、ほとんどの古典的アルゴリズムは高次元、ノイズ、または不規則分布のデータには苦労します。したがって、すべてのデータ型で最適に動作する普遍的なクラスタリング手法は存在しません。
これらの課題に対処するために、量子クラスタリングは有望な代替案として浮上しています¹²。古典的アルゴリズムとは異なり、量子着想アプローチは重ね合わせ、エンタングルメント、その他の量子力学の原理を活用し、データ空間をより効率的に探索します。このパラダイムは、高次元かつノイズの多いデータセットの扱いにおいて古典的なクラスタリングに比べて潜在的な利点を示し、研究コミュニティ内でますます受け入れられています。それにもかかわらず、既存の量子クラスタリング手法は、あらかじめ定義されたクラスタ数や不安定な重心初期化に悩まされることが多く、これが実用的応用における堅牢性を低下させます。
本研究では、4つの異なる革新を取り入れた新しい分割ベースのハイブリッド量子K-Meansクラスタリングアルゴリズムを導入します。(i) 遺伝子発現データを高次元ヒルベルト空間に符号化するための量子多特徴マッピング;(ii) 確率比例距離ベースの重心初期化により、ランダム初期化と比較して安定性が向上します。(iii) 正確な類似度測定のためのスワップテストベースの量子距離推定;(iv) クラスタ内分散を最小化して最適クラスタ数を決定する量子勾配ベース最適化。これらの貢献により、提案された手法は従来の量子クラスタリング手法19,20と区別され、堅牢性、スケーラビリティ、そして現実世界のバイオインフォマティクスシナリオでの適用性が向上しています。
遺伝子発現データのクラスタリングはバイオインフォマティクスにおいて重要な課題であり、特に遺伝的プロファイルに基づいてがん細胞と非がん細胞を区別するために重要です。従来のクラスタリング手法、例えば古典的なK平均法は、遺伝子発現データセットの高次元性質に苦労し、分類が最適とは言えません。これらの課題を克服するために、Quantum K-Meansアルゴリズム(Quantum K-Means Algorithm with Optimal Cluster Determination)を導入します。これは、量子特徴マッピングと確率的重心初期化を活用し、優れたクラスタリング性能を実現します。このアルゴリズムは遺伝子発現データを効率的にクラスタリングするだけでなく、最適なクラスター数を自動的に決定し、異なるがんサブタイプの同定を可能にします
提案されたアルゴリズムは、がん性および非がん性遺伝子発現プロファイルを含むデータセットに適用され、行動の類似性に基づいてクラスタリングして効果を評価します。
アクセスが制限されています。このコンテンツを表示するにはログインするか、トライアルを開始してください。
プロトコル
1. 量子特徴写像
古典的なデータ点を量子状態に符号化することは、それらを量子ヒルベルト空間に写すことで実現され、量子コンピュータ16˒17,19によって効率的にアクセス・操作できます。この過程では、古典データをヒルベルト空間に埋め込む非線形量子特徴写像を用います(図1)。固定された量子回路特徴マップは入力データ点を量子状態17に変換し、変分回路は測定基底22を適応させることで機械学習タスクを可能にします。変分回路は、ハイブリッド量子-古典的手法によって最適化されたパラメータ化された量子ゲートの集合で構成されています。
図1:量子ヒルベルト空間における特徴写像。 この図の拡大版はこちらをクリックしてご覧ください。
2. ターゲット点と重心を量子ビットに符号化する
データ点の特徴を符号化するには、U3ゲートを用いて回転を行う必要があります。
これにより、量子ビットは正のz軸からθラジアン、正のx軸からΦラジアンが回転します。
すべての量子ビットは符号化プロセス開始前に∣0」状態で初期化されました。各遺伝子発現値は範囲[0,1]に正規化され、回転角の関係式θi=πxiを用いて変換されました。その後、パラメータ化されたユニタリゲートが各量子ビットに適用され、対応する特徴を符号化しました。これはQiskitでqc.u(theta_i, pi, pi, qubit_index)演算を用いて実装されました。複数の特徴が符号化された場合、回転手順を適切なキュービット間で繰り返して多特徴表現を作成しました。これらの演算の後、得られる量子状態 ∣ψ』 はヒルベルト空間における符号化された特徴ベクトルを表しました。この段階では測定は行われず、準備状態は後続の類似性推定のために予約されていました。
3. 量子状態の比較
量子実験の結果は本質的にランダムです。なぜなら、量子ビットは量子物理学で説明されるように本質的に不安定だからです。したがって、結論や予測は確率と不確実性の観点から表現されなければなりません。したがって、明確な結論を導き出すことは真の課題となります。しかし、検討対象となる量子状態が純粋であれば、状態間の差異(ゼロでない確率で)は実験24˒25によって明確に予測できます。
2つの量子状態、∣ψ〉と∣φ〉は、まず別々の量子レジスタにロードされました。その後、∣0」状態でスワップ操作を制御するためにアンシラ量子ビットが初期化されました。制御スワップ操作を実行する前に、アンシラにハダマールゲートをかけて重ね合わせを行った。Fredkin(CSWAP)ゲートはアンシラを制御量子ビットとして、2つのデータレジスタをターゲットとして用い、状態間の干渉を可能にしていました。この操作の後、干渉パターンを完成させるためにアンシラに2つ目のハダマールゲートが適用されました。アンシラ量子ビットのみが測定され、その測定結果は両状態の類似性を符号化しました。状態が同一の場合、アンシラは確率1で結果0を生み出し、直交状態は確率0.5で結果を生み出しました。
図2:確率に基づく比較の図示。状態ρとξが異なる場合、観測される確率分布はPE− \ PE+に属します。 この図の拡大版はこちらをクリックしてご覧ください。
密度演算子ρは、tr[ρ] = 1かつρ ≥ 0 を満たす任意の量子状態 ρ ∈ S(H) に関連付けられます。ここで、ヒルベルト空間Hに対応する系のすべての状態S(H)の集合です。正作用素値測度(POVM)は、正の演算子E1, ... ,E n をE(Hに作用させる)と恒等式 I = 
の集合である量子統計的特徴測定です。確率分布 
は、pj = tr[Ejρ]≥ 0 かつ 
= 126 の各状態 ρ ∈ S(H) に対して測定値を割り当てます。
4. SWAPベースの量子状態比較
2つの量子状態の差は、量子計算におけるSWAPテスト手順を用いて測定できます。この方法はバレンコらによって最初に導入されました。その後、ジョン・ワトラス、ロナルド・デ・ウルフ、ハリー・バーマン、リチャード・クレーブによって再発見されました。SWAPテストは量子コンピューティングや量子機械学習に応用されています 15, 29.
SWAP検定は ∣ψ』と ∣φ』を入力状態とし、出力する確率1(ベルヌーイ確率変数)1/2 - 1/2 の『φ,ψ』2 を用い、2つの状態の二乗内積を推定します 30。
回路の説明
系の2つの状態∣φ〉と∣ψ』を考えると、最初のプロトコルは∣0,φ,ψです。ハダマールゲートを適用した後、状態は
∣0,φ,ψ』 + ∣1,φ,ψ』に変化します。CSWAPゲートは状態を(0,φ,ψ』 + ∣1,ψ,φ』に変換します。2回目のハダマール門の後、状態は1/2(|0,φ,ψ〉 + ∣1,φ,ψ〉 + |0,ψ,φ - ∣1,ψ,φ〉)= 1/2∣0〉(|φ,ψ〉 + |ψ,φ〉) + 1/2|1〉(|φ,ψ - |ψ,φ〉)。最初の量子ビットを測定すると、結果0が得られる確率はP(First qubit = 0) = 1/2(〈φ|〈ψ| + 〈ψ|φ|))である。 1/2 (|φ,ψ〉 + |ψ,φ〉) = 1/2 + 1/2 |〈ψ|φ〉|2. ψ と φ が直交する場合(|〈ψ|ϕ〉|2 = 0)の場合、0が得られる確率は1/2となります。状態が同一であれば(|〈ψ|ϕ〉|2 = 1) なら、0を得る確率は1です。24
図3:(a) 極性相反状態のフレドキンゲート回路、(b) 確率測定グラフの出力、(c) ハダマールゲートを持つフレドキンゲート回路、(d) 測定確率グラフの出力。 この図の拡大版はこちらをクリックしてご覧ください。
回路は1つのアンシラ量子ビットと、量子状態∣ψ〉および∣φ〉を符号化する2つのレジスタを使用していました。すべての量子ビットは符号化段階開始前に初期化されました。その後、遺伝子発現の特徴は特徴マッピング手順を用いてそれぞれのレジスターに符号化されました。アンシラ量子ビットにハダマールゲートを適用して重ね合わせを作り、その後アンシラを制御として2つの状態レジスタ間で制御SWAP操作が行われました。干渉パターンを完成させるために2つ目のハダマールゲートがアンシラに適用され、その後アンシラキュービットが測定されました。2つの符号化状態が同一の場合、アンシラは一貫して結果0を生み出しました。状態が直交する場合、アンシラは確率0.5で結果を導き出しました。部分的に類似した状態の場合、0が得られる確率は0.5から1の間にあり、状態間の類似度を反映しています。
5. 量子距離推定
古典的なデータ解析では、データ点間の距離はユークリッド距離やマンハッタン距離2,3などの指標を用いて直接計算できます。量子コンピュータ上の量子ビットの場合、量子状態の確率的な性質によりこの作業はより複雑になります。位相差や確率振幅は測定可能ですが、2つのベクトル間の距離として直接表現することはできません。
クラスタリングには、クラスタ重心13に対するデータ点の相対位置を評価する必要があります。各量子ビットを適切なクラスタに割り当てるためには、対応するクラスタ重心への近接を示すパラメータを定義する必要があります。
これを実現するために、類似度と正の相関を持つパラメータが導入され、従来の距離測度15,30の代替として機能します。
距離推定の過程は、正規化された量子状態 ∣Ψ』とゼロ初期化された補助量子ビット ∣q0』から始まりました。目的は、∣q1で符号化された新しいデータ点と、∣q2で符号化されたクラスタ重心との距離を推定することでした。干渉パターンに必要な重ね合わせを準備するために、アンシラ量子ビットにハダマールゲートを適用し、状態 ( ∣0〉 + ∣1〉 ) ⊗ ∣Ψ』 を生成しました。その後、アンシラを制御として制御されたSWAP(フレッドキン)ゲートが適用され、アンシラを2つの符号化状態と絡めて重なり合うことで測定結果に影響を与えました。この操作は状態 ( ∣0〉 ⊗ ∣Ψ〉 + ∣1〉 ⊗ Fswap(∣Ψ』)を生み出し、アンシラの後続測定を通じて内積に基づく距離を抽出することができました。
回路実装と出力
この量子回路は位相符号化を用いて遺伝子発現データをキュービットに符号化し、その後、制御スワップ(CSwap)ゲート(スワップテスト12)を通じて2つの遺伝子発現状態を比較します。
必要な重ね合わせを作成するために、すべての量子ビット(q0からq4)にハダマールゲートを適用し、すべての基底状態|Ψ〉 = 
の等重ね合わせを実現します。この初期化により、複数の遺伝子発現値に対する並列計算が可能になります。各量子ビットは位相回転
を受け、θx はマッピングされた遺伝子発現値に対応します。量子ビットq1からq4に適用されるユニタリ演算子U(θ,π,π)は個々の遺伝子の発現レベルをコードし、各角度θは遺伝子の発現の変換版を表します。この手法は位相符号化を通じて古典的な生物学的データを量子状態にマッピングし、高次元量子空間に複数の遺伝子を表現できるようにします。
CSwapゲートはエンコード状態をエンタングルすることで比較するために使われます。補助的な量子ビットq0は制御として働き、q1からq 4の状態が入れ替わるかどうかを判定します。類似の量子状態は q0 に建設的干渉を生じ、∣0 を測定する確率が高まります。逆に、異種状態は∣1』を測定する確率を高めます。q0に続くハダマールゲートは振幅干渉を保証し、測定を通じて類似情報を抽出することを可能にします。
2つの量子状態∣ψ〉と∣φ』が異なる遺伝子発現データセットを表していると仮定します。|ψ〉 = ∑iai |i〉, |φ = ∑ibi |i』。
スワップテストは、それらの間の忠実度(内積)を評価します。
P (0) = 
、
ここで∣〈ψ∣φ〉∣は内積を表します。P(0) ≈ 1 の場合、状態は類似しています。P(0)≈0.5以下であれば、両者は異質です。
このフレームワークにより、患者や実験的状態(例:正常組織と病変組織)を比較することが可能となります。量子機械学習モデル内で高次元データをクラスタリングするための効率的な基盤を提供します。スワップテストは量子状態間の類似性の特定を支援し、サンプルを意味のあるクラスタにまとめるために利用できます。
図4:データ点と重心間の距離測定回路。 この図の拡大版はこちらをクリックしてご覧ください。
図5:測定確率グラフの出力。 この図の拡大版はこちらをクリックしてご覧ください。
まずデータ点が量子状態∣ψ〉に符号化され、対応するクラスター重心が状態∣φ』に符号化されました。先に説明したスワップテスト手順を実行し、これら2つの状態を比較し、アンシラ測定確率P(0)を記録しました。状態間の忠実度はF=∣〈ψ∣φ〉∣2として得られ、量子距離はD (ψ,φ) = 
と定義された。Dの値が小さいほど、そのデータ点が量子特徴空間の重心に近いことを示します。
6. 初期重心選択
クラスタ重心の初期化は、K-平均クラスタリングの安定性と正確性にとって極めて重要です。ランダム化選択は重心の分布が不十分で、収束が遅く最適でない結果をもたらすことがあります。この問題に対処するため、K-Means++戦略20 に着想を得た確率比例距離法が用いられています。量子強化アプローチでは、SWAPテストに基づく量子距離推定器を用いて距離を評価し、選ばれた重心が基礎となるデータ分布をより正確に表していることを保証します。この戦略はクラスタ分離を強化し、特に高次元データセットにおいてアルゴリズムの堅牢性を向上させます。
重心の初期化プロセスは、最初の重心としてランダムに1つのデータ点を選んで始まりました。この重心と残りのすべてのデータ点との量子距離は、量子距離推定手法を用いて計算されました。これらの距離値に基づき、各点に最も近い重心からの距離の二乗に比例した選択確率を割り当てる確率分布が作成されました。この分布に従って新しい重心をサンプリングし、この手順を繰り返して望ましい重心数Kが得られました。このアプローチはランダム選択よりもはるかに優れた初期重心セットを生成しました。
7. 量子分散計算
クラスタ分散は、重心周辺のデータ点のコンパクトさを定量化するため、クラスタリングの品質を評価する上で重要な指標です。古典的なK平均では、分散はデータ点と割り当てられた重心間の平均二乗距離として計算されます。量子強化アプローチでは、これらの距離は量子距離推定器(SWAPテストを通じて)を用いて得られ、量子状態間の忠実度に基づく類似性を計算します。各クラスター内の距離を二乗で合計し、クラスタサイズで正規化することで、クラスタ内の凝集度を反映した分散値を得られます。この分散を最小化することで、より緊密で意味のあるクラスターが確保され、これは高次元遺伝子発現データセットにおいて、がんと非がんのサンプルを区別する上で特に重要です。
クラスタ割り当ては、各符号化された量子データポイントを量子距離推定を用いて最も近い重心に割り当てることで行われました。各クラスターCkに対して、各データ点とその重心との間の量子距離D(ψi,C k)が計算されました。クラスタ内分散は
を用いて計算され、各クラスタのコンパクト度を測定しました。全分散は、すべてのクラスター間の個別分散を合計して得られました。この総分散値は、最適なクラスタ数の決定や全体のクラスタリング性能の評価のために記録されました。
8. 量子勾配ベース最適化
クラスタの最適数(K)を決定することはクラスタリング作業における基本的な課題です。従来のK-平均法では K があらかじめ定義されている必要があり、しばしば過クラスタリングや過クラスタ化につながります。量子強化アプローチでは、 量子勾配ベース最適化(QGBO) を統合し、最適なクラスタカウントを適応的に特定します。アルゴリズムは Kを反復的に増加させ、各ステップで分散を再計算し、分散の減少(ΔV)を評価します。分散の改善が閾値を下回ると、クラスタリングは終了します。量子勾配は パラメータシフト則を用いて計算され、これは量子回路からの期待値の微分を推定します。このアプローチにより、最終的なクラスター数が正確さと効率のバランスを取ることが保証され、生物学的サブタイプ数が事前に分からないバイオインフォマティクスの応用において特に有用です。
クラスタリングのプロセスはK=1で始まり、量子分散計算手順を用いて総分散V(K)を計算しました。クラスタ数はK+1に増加し、分散V(K+1)が再計算されました。分散の減少、ΔV=V(K)−V(K+1)は、追加のクラスタがデータのコンパクトさを向上させ続けるかどうかを評価するために評価されました。反復はΔVがあらかじめ定められた閾値を下回った時点で停止し、Kのさらなる増加は意味のある改善をもたらさなかったことを示しています。分散トレンドの曲率変化を監視するために変分ゲートを持つパラメータ化された量子回路が構築され、この情報がクラスタ最適化プロセスの指針となりました。分散削減が安定し、コンパクトでよく分離されたクラスタが得られるKの値として最適なクラスタ数が選ばれました。
9. クラスタ分散の計算とVリストへの保存
安定したクラスタが形成されると、アルゴリズムはクラスタ分散を計算し、各クラスタのコンパクトさを測定します。特定のクラスタにおける分散Vkj は、クラスタ内の各データ点とクラスタ重心間の距離を用いて決定されます。
ここで:xは遺伝子発現サンプル、Ciはクラスター、CciはクラスターCiの重心、Vkjはk個クラスタを含むj回目の反復で記録された分散を表します。
この分散はリスト Vリストに保存され、後に最適なクラスタ数を決定するために使われます。
10. 最適なクラスター数の決定
クラスタKの最適数を求める ために、アルゴリズムは複数の反復を行い、異なる開始条件を観察します。主なステップは以下の通りです:
アルゴリズムはまず、 異なるKの値に対して計算された分散のリストから最小分散値を特定しました。その後、連続したクラスター数間の分散減少は、ΔV=∣Vk−V k−1∣という式で測定されました。ここで Vk は K 個クラスタの分散、Vk−1 は K−1 クラスタの分散を表しました。ΔVの減少があらかじめ定められた閾値を下回り、クラスタリングの改善がほとんど見られない場合、手順は終了しました。それ以外の場合はクラスター数を増やし、最適なクラスタ数に達するまで計算を繰り返しました。
11. がんおよび非がん分類のクラスターの最終決定
最適なクラスター数Kが決定されると、最終的なクラスターは遺伝子発現データ内の異なるグループを表します。通常、このアルゴリズムは2つの主要なクラスタを導き出します。
1つはがん細胞を表しており、悪性腫瘍に関連する異なる遺伝子発現シグネチャーで示されます。
1つは非がん細胞(正常な遺伝子発現プロファイルを含む)を表します。
提案された量子K-Meansクラスタリングアルゴリズムで用いられるパラメータ、変数、定数は 表1に記載されています。データセットの次元を定義し、クラスタ数 Kを設定し、停止基準と最適化閾値を適用してプロセスを導きます。1回のショット数やランダムシードなどの計算設定を設定して再現性を確保しましょう。確率ベース選択法で重心を初期化し、収束するまで反復的に更新します。また、クラスタラベル、重心、最適 K、評価指標、可視化プロットなどの期待出力も指定されています。
| カテゴリー | パラメータ | 価値/デフォルト | 注記 |
| データセット | 乳がんデータセット | 569サンプル×32の特徴(2つのPCA成分に縮小) | PCAによる次元減少 |
| クラスターの数 | K | 動的、最初は1、最大5 | 分散削減による最適化 |
| 最大クラスター | Kmax | 5 | 探索の上限 |
| 1ランあたりのシュート数 | N | 1024 | 回路の実行ごとの測定値 |
| 耐性の停止 | ε | 1 × 10^-14 | 分散収束基準 |
| 分散傾き閾値 | ΔV | 9.9 × 10^-4 | 最適化のための停止閾値 |
| 観察 | モブスラバー | 3 | クラスタサイズごとの独立ラン |
| 反復回数の限界 | – | 10 | 1回のランごとの最大重心更新ステップ数 |
| ランダムシード | – | 42 | 再現性を確保する |
| 期待出力 | – | クラスタラベル、重心、最適K、評価指標、プロット | .csvファイルおよび.pngファイルとしてエクスポート |
| クラスター間の分散 | Vリスト | 空っぽ | 最適 K を検出します |
| 重心 j | CJ | 関数によって初期化(点の距離の二乗に比例した確率に基づく) | 反復的に更新し、最終重心を保存します |
表1:材料、ソフトウェア、再現性設定
| ステップ | 関数/API(あなたのコードより) | 戦闘 | 予想結果 |
| 特徴符号化 | QC.U(シータ、π、π、キュービット) | 正規化された古典特徴量を量子ビット回転に符号化します | 量子ビット状態 |
| SWAPテスト/量子距離 | qc.cswap() を使ったget_Distance(x, y) | 3量子ビット回路(アンシラ+2状態)を構築する | P(0)≈1.0→同一;直交→ P(0) ≈ 0.5 |
| 回路の実行 | SamplerV2 with AerSimulator(1024ショット) | シミュレーターでトランスピレーション(OPTレベル1)で回路を実行 | アンシラ量子ビットの確率分布 |
| 重心の初期化 | initialize_centroids_kmeans_pp(ポイント、k) | 距離に比例した初期重心を選択します | 多様な開始重心 |
| クラスター再割り当て | find_nearest_neighbour(ポイント、重心) | 最も近い重心に点を割り当てる | 安定クラスタのメンバーシップ |
| 分散計算 | calculate_variance(センター、centers_distance) | クラスタ内分散を計算します | 分散は反復ごとに減少します |
| 分散傾き | grad_slope(k, V_k, k-1, V_k-1) | ΔVを ε = 1e-14 および傾き閾値 ΔV 0.000099 ≤と比較してください。 | 検出された最適K |
| 可視化 | matplotlib.pyplot、plot_histogram | プロットクラスタ割り当てと量子結果 | PCA散布図、分散プロット、ヒストグラム |
| 計量計算 | silhouette_score、calinski_harabasz_score、davies_bouldin_score | クラスタリングの品質を評価する | シルエット≈ 0.64、CH ≈ 766、DB ≈ 0.65 |
表2:提案アルゴリズムの実行可能な実装詳細。
実装とアルゴリズム
最適クラスタ決定を用いた量子K-平均アルゴリズムは、量子特徴マッピングを用いて最適なクラスタ数を動的に特定する量子強化クラスタリング手法です。19 この手順は、すべてのデータ点を単一のクラスタに属するものとして考えることから始まります。その後、 クラスターK の数は徐々に増加します。クラスタセンターは点間距離に基づいて確率的に初期化され、その後各データ点は最も近い重心に割り当てられ、 K クラスターが形成されます。その後クラスタ分散が計算され、重心が更新されます。この再割り当てプロセスは、これ以上の変更が起こらなくなるまで繰り返し行われます。
このアルゴリズムは複数回の反復にわたる分散を評価し、異なるクラスタカウントに対応する分散値を保存します。 K の最適値は分散削減ΔVを監視しながら分散を最小化することで決定されます。ΔVが無視できるほど小さくなると、その手続きは終了します。そうでなければ 、K が増え、クラスタリングプロセスが再開されます。この適応戦略により、特に高次元特徴空間におけるデータの効率的かつ正確な分割が保証されます。
図6:提案されたハイブリッド量子K-平均クラスタリング手順のフローチャート。量子特徴マッピング、重心初期化、反復クラスタ割り当て、量子分散計算、分散に基づく収束チェック、最適クラスタ数の量子勾配支援選択を示している。 この図の拡大版はこちらをクリックしてご覧ください。
以下のステップでは、がんおよび非がん遺伝子発現データをクラスタリングするための量子K-Meansアルゴリズムの概要を示します。
アルゴリズム:量子K-平均アルゴリズムを用いたがん細胞および非がん細胞の遺伝子発現データをクラスタリングする
ステップ1: 量子特徴写像(多機能符号化)。
ステップ2: 最初にすべてのデータ点が同じクラスタに属していると仮定し、K=1の値を設定します(ここで、K:は最適クラスタのno、V:はクラスタ分散、ΔV:分散の減少)。
ステップ3: 中心の初期化(データ点間の距離の確率比率を使って初期中心点を選択する)。
ステップ4: 各データポイントを最も近い重心に割り当て、それがあらかじめ定義された「K」クラスターを形成します。
ステップ5: クラスタ分散を計算し、各クラスタの新しい重心を配置します。
ステップ6: ステップ4を繰り返します。つまり、各データポイントを各クラスターの新しい最も近い重心に再割り当てすることを意味します。
ステップ7: もし再割り当てがあれば、ステップ5に進み、それ以降はステップ8に進みます。
ステップ8:次にクラスタCj(クラスタのkを含む'j'回の反復)を計算し、分散Vkj= 
を計算します。ここで「x':データ点はクラスターCi、Cci:クラスターCiのクラスタ重心です。分散V kjをVリストに記録し、ステップ3の新しいセンター(例えば1 ≤ j ≤ Mobsrv)で同じKでクラスタリングを再開します。
ステップ9: クラスタの「K」を用いてVリスト から最小分散Vを求める。
ステップ10:ΔV を計算します (ΔV = |Vk - Vk-1|(ここでVk:クラスタの分散はK-1、クラスターはK-1)との間の分散です。もしΔVが量子勾配ベース最適化(大幅な還元)であれば、FINISHでなければKを増やし(K=K+1)、新しいKでステップ3に進みます。
ステップ11: クラスターは準備完了しており、最適なクラスター数は「K」です。
量子特徴写像アルゴリズム
アルゴリズム1: 量子特徴マッピング
入力: P はそれぞれの量子状態|ψ』と『|Φ』を点示します。
出力: | の推定値〈 ψ |Φ〉 |2
アルゴリズムのステップ:
ステップ1: 量子ビットをゼロで初期化します。ハダマールゲートを適用し、Z軸基底からX軸に回転させます。
Sの基準2: 特徴1に関するデータ点の値に基づいてラジアンでφ(0≤ φ ≤ π)を設定します。
φ = 2*rad(cos-1)(d0))、ここで d0 は特徴1のデータ値、d0 は[0, 1]∈を表します。
ステップ3: 特徴2に関するデータ点の値に基づいて、θ(0 ≤ θ ≤ π)をラジアンで設定します。
θ = 2 * rad(Cos-1(d1)))であり、 ここでd1 は特徴2とd1 のデータ値∈[0, 1]を表します。
ステップ4: U3量子ゲートを使って回転を実装し、データポイントの特徴を符号化します。
これにより、量子ビットΦを正のx軸に対して、θラジアンを正のz軸に対して回転させます。
量子状態アルゴリズムの比較
アルゴリズム2: 量子状態の比較
入力: 2つの量子ビット |q1』と|q2』 それぞれの量子状態 |ψ〉 と |Φ』
出力: | の推定値〈ψ|Φ』 |2
アルゴリズムのステップ:
ステップ1:キュービットAをアンシラとして考え、状態|0で初期化する」
ステップ2: 量子ビットAにハダマールゲートを適用する
ステップ3:|q1 と|q2 τ キュービット(状態上|ψ と |Φ』)、制御量子ビットはAです
ステップ4: 量子ビットAにハダマールゲートを適用する
ステップ5: Zを基に測度Aを測定し、測定結果をMとして記録します
帰還 M を | の推定値として 〈 ψ|Φ 〉 |2
k平均クラスタリングのための量子距離推定アルゴリズム
アルゴリズム3: 量子距離推定器と新しいクラスタ重心の選択
入力:データ点のPノ、クラスター重心のKノ、それぞれの量子状態|ψ と |Φ』
出力: データポイントに関連する新しいクラスタ化された重心
アルゴリズムのステップ:
iは1からPの範囲で次のように述べられます。
i番目のデータポイントを選んで|qi に記録する
jが1からKの範囲で次のようになる:
j個のクラスタ重心を選んで|qj に設定してください
量子状態 |qi 〉 と |qj を比較する 〉すなわち、j番目の重心を持つ i個の量子ビットで、M の測定値を (Mi, j) として記録します。
終わり
Mから最小距離(Mmin , min)を求め、minを|qi の新しい重心と定め ますそしてCiとして記録します
終わり
帰還 Cは新しい重心リスト
M= |qi 第i量子ビットからのすべてのクラスタ化された重心距離のリスト
C = |qi の新たに計算された最小距離クラスタリング重心C i の一覧;∀(i∈{1,...,P})
初期重心選択アルゴリズム
アルゴリズム4: データ点間の距離の確率比率を用いて初期重心点を計算する
入力: m はデータ点(X1,X 2,...,Xm)のそれぞれ、量子状態 |ψ と |Φ』
出力: K個の初期重心を持つ集合Sを返す
アルゴリズムのステップ:
ステップ1: データ点X i からランダムに一点 X を選び(1 ≤ i ≤ m) を集合 S に加えます。
ステップ2: すべての Xi について、量子距離推定器を用いて Xi と S 内の最も近い重心点の距離を計算し、距離を Ddist(Xi) と設定します。
ステップ3:0からDの差(X1)2 + Dの差(X2)2 + ...+ Dの差(Xm)2の間で一様に数Yを選ぶ
ステップ4: 次の一意整数iを見つける
Dディスト( X1)2 + Dディスタント (X2)2 + ...+ Dディスタント (Xi)2 >= Y >Dディスト( X1)2 + Dディスタント (X2)2 + ...+ Dディ スタント(Xi-1)2
ステップ5: SにX、i を加える
ステップ6:K重心が見つかるまで、ステップ2から4を繰り返します
帰還 Sを初期重心点として
量子分散計算アルゴリズム
アルゴリズム5: 量子分散の計算
入力: Pは各量子状態| ψ と |Φ』
出力: データポイントの分散を返します
アルゴリズムのステップ:
totalVariance ← 0
iは1からKの範囲で次のように表されます:
i番目のクラスタ中心点を選んで|qi に設定します
totalVariancei ← 0, M ← 0
すべての j ∈に P、クラスター中心体iに関連する:
j番目のデータポイントを選んで|qj に設定します
量子状態 |qi 〉 と |qj を比較する 〉すなわち、第1重心と第j個のデータ点を設置し、測定をMjに記録します。
M ← M + Mj
終わり
totalVariancei ← 
[Ci は第i個クラスタ; |Ci |は第i個クラスタのデータ点の集合であり、DkはCi と Mk ∈データ点です
はC、i 、D、kの重心間の距離です。
totalVariance ← totalVariance + totalVariancei
終わり
total varianceを返す
量子勾配ベース最適化アルゴリズム(クラスタの最適値を得る)
量子勾配に基づく最適化ステップは、Kが増加するにつれてクラスタ内の分散がどのように変化するかを監視することで、最適なクラスタ数を決定します。連続したKの値の分散を計算し、それらの間の変化を評価します。分散の減少があらかじめ定められた閾値を下回ると、追加のクラスタはもはやコンパクトさを改善せず、対応するKが最適として選ばれます。この曲率ベースの基準により、データ内の自然な構造が過剰分割なく捕捉された地点でクラスタリングが停止することを保証します。
アルゴリズム6: 量子勾配ベース最適化
入力:
パラメータ化された量子回路 QC(θ)で、単一の量子ビット回転ゲートRY(θ)を持つ。
量子観測 
= Z (パウリ-Z期待値)です。
パラメータ値の範囲θ。
出力: 期待値 § Z の二階微分 f′′(θ) を θ に関するものである。
アルゴリズムのステップ:
ステップ1: 単一量子ビット量子回路 QC(θ)を以下で初期化します:
パラメータ化された回転ゲートRY(θ)です。
計算(Z)ベースでの測定。
ステップ2:関数 Evaluate_ 期待値(θ)を定義します。すなわち f′(θ) =
パラメータθを回路に割り当てます。
N 回の ショットで量子シミュレーターで回路を実行。
結果確率 P(0)および P(1)を測定します。
期待値を計算する:
f(θ)=P(0)−P(1)
ステップ3: パラメータシフトの規則を用いて二階微分を計算します:
シフト値 s = を設定します 
シフトした点での期待値を計算します:
f(θ+s)、f(θ)、f(θ−s)
2階微分を計算します:
f ′′(θ) = 
ステップ4: 分散削減挙動を解析するためのf ′′(θ)。
提案された量子クラスタリング手法の実装詳細は表2に示されています。この表は、アルゴリズムの各段階で使用される実行可能な関数とAPIを指定しており、量子回路への特徴符号化、距離推定のためのSWAPテストの実行、重心の初期化、反復的なクラスタ再割り当て、分散/ΔV評価などが含まれます。また、1024ショットでのAerSimulatorバックエンドでのSamplerV2使用やトランスパイレーション最適化レベル1などの回路実行パラメータも記載されています。さらに、表はPCA散乱図、分散プロット、ヒストグラムの生成に用いられた可視化手法とクラスタリング評価指標(silhouette_score、calinski_harabasz_score、davies_bouldin_score)を示しています。特定のコマンドレベルの関数やAPIを詳細に示すことで、提案されたアルゴリズムのすべての計算ステップの再現性を確保しています。
アクセスが制限されています。このコンテンツを表示するにはログインするか、トライアルを開始してください。
結果
良いクラスターは、クラスタ間の距離、クラスタ内の距離、分散比の基準など、さまざまな要因に依存します。クラスタリング性能は、シルエットスコア、カリンスキー・ハラバズ指数(CH指数)、デイヴィス・ボールディン指数(DB Index)の3つの標準指標を用いて評価されました。シルエットスコアは、
としてクラスタ間の分離を測定し、icは平均クラスタ内距離、ncは平均最接近クラスタ距離です。値は-1から+1の範囲で、+1付近の値はコンパクトでよく分離されたクラスターを...
アクセスが制限されています。このコンテンツを表示するにはログインするか、トライアルを開始してください。
ディスカッション
本研究は、高次元遺伝子発現データを用いてがんおよび非がん性サンプルを分類するために特別に設計された、最適なクラスター検出を備えた新しいハイブリッド量子K-meansクラスタリングアルゴリズムを提案します。このアプローチは、量子多特徴マッピング、スワップテストに基づく量子距離推定、 量子勾配ベース最適化を統合し、最適なクラスタ数を動的に決定します。従来のK-Meansアルゴリズムがクラスタ数をあらかじめ定め、初期重心選択に敏感であるのに対し、提案された手法は安定性と収束を保証するために確率比例重心の初期化を用いています。
最適クラスタ決定を備えた量子K-Meansアルゴリズムは、量子特徴マッピングと確率的重心初期化を活用し、遺伝子発現プロファイルなど複雑なデータセットでのクラスタリング性能を向上させます。量子原理をクラスタリングパイプラインに組み込むことで、この手法はグループ間の分離を改善し、高次元データ解析における堅牢性を提供します。...
アクセスが制限されています。このコンテンツを表示するにはログインするか、トライアルを開始してください。
開示事項
著者たちには利益相反はありません。
謝辞
著者らは、オープンアクセスの遺伝子発現データセットや量子シミュレータの利用により、この研究の実用的な検証が可能になったことを認めています。
アクセスが制限されています。このコンテンツを表示するにはログインするか、トライアルを開始してください。
材料
| 名前 | 会社 | カタログ番号 | コメント |
|---|---|---|---|
| Apple MacBook Pro(M1チップ) | アップル社 | - | 8コアCPU/8コアGPU、16コア?GB Unified memory & mdash;局所シミュレーションに使用 |
| 乳がん遺伝子発現データセット | カグル | - | サンプル569、特徴32(研究ではPCAで縮小)を含むデータセット |
| macOS Monterey(オペレーティングシステム) | アップル社 | 12.6.9 | ローカルマシン上で使用されるランタイム環境 |
| 数学(Python標準ライブラリ) | Pythonソフトウェア財団 | 内蔵 | 基本的な数学的関数 |
| Matplotlib | Matplotlibコミュニティ | 3.8.4 | プロット作成と可視化 |
| NoiseModel, QuantumError, ReadoutError (Qiskit Aer) | IBM / Qiskitプロジェクト | Aer 0.13.3の一部 | 現実的な量子ノイズのシミュレーションに使用されます |
| NumPy | NumPy 開発者 | 1.26.4 | 数値演算と配列操作 |
| パンダ | パンダス開発チーム | 2.2.2 | データ処理、I/O、表形式操作 |
| パイソン | Pythonソフトウェア財団 | 3.10.12 | Jupyter / IPython環境で使用されるプログラミング言語 |
| キスキット・アエル | IBM / Qiskitプロジェクト | 0.13.3 | シミュレーターのバックエンド、ノイズモデリングと実行機能 |
| Qiskit IBM Runtime –セッション、SamplerV2 | IBM / Qiskitプロジェクト | 0.41.1 | シミュレータ回路の実行フレームワーク |
| キスキット・テラ | IBM / Qiskitプロジェクト | 0.45.0 | 回路構築とトランスパイレーションのための量子的枠組み |
| scikit-learn | Scikit-Learn 開発者 | 1.4.2 | PCA、クラスタリング指標、データ前処理 |
参考文献
- Mehta, V., Agarwal, M., Kaliyar, R. K. A comprehensive and analytical review of text clustering techniques. Int. J. Data Sci. Anal. 18 (3), 239-258 (2024).
- Bezdek, J. C. Pattern recognition with fuzzy objective function algorithms. , Springer Science & Business Media. (2013).
- MacQueen, J. Classification and analysis of multivariate observations. 5th Berkeley Symposium on Mathematical Statistics and Probability, , Univ. California. 281-297 (1967).
- Ester, M., Kriegel, H. P., Sander, J., Xu, X. A density-based algorithm for discovering clusters in large spatial databases with noise. KDD, 96 (34), 226-231 (1996).
- Roy, S., Bhattacharyya, D. K. An approach to find embedded clusters using density based techniques. Distributed Computing and Internet Technology (ICDCIT 2005), , Springer. 523-535 (2005).
- Guha, S., Rastogi, R., Shim, K. CURE: An efficient clustering algorithm for large databases. ACM SIGMOD Rec. 27 (2), 73-84 (1998).
- Zhang, T., Ramakrishnan, R., Livny, M. BIRCH: An efficient data clustering method for very large databases. ACM SIGMOD Rec. 25 (2), 103-114 (1996).
- Agrawal, R., Gehrke, J., Gunopulos, D., Raghavan, P. Automatic subspace clustering of high dimensional data for data mining applications. Proc. 1998 ACM SIGMOD Int. Conf. Management of Data, , 94-105 (1998).
- Wang, W., Yang, J., Muntz, R. STING: A statistical information grid approach to spatial data mining. VLDB, 97, 186-195 (1997).
- Theodoridis, S., Koutroumbas, K. Pattern recognition. , Elsevier. (2006).
- Mitsuda, N., et al. Approximate complex amplitude encoding algorithm and its application to data classification problems. Phys. Rev. A. 109 (5), 052423(2024).
- Horn, D., Gottlieb, A. Algorithm for data clustering in pattern recognition problems based on quantum mechanics. Phys. Rev. Lett. 88 (1), 018702(2001).
- Von Luxburg, U. A tutorial on spectral clustering. Stat. Comput. 17 (4), 395-416 (2007).
- Schölkopf, B., Smola, A., Müller, K. R. Nonlinear component analysis as a kernel eigenvalue problem. Neural Comput. 10 (5), 1299-1319 (1998).
- Schuld, M., Sinayskiy, I., Petruccione, F. An introduction to quantum machine learning. Contemp. Phys. 56 (2), 172-185 (2015).
- Schuld, M., Killoran, N. Quantum machine learning in feature Hilbert spaces. Phys. Rev. Lett. 122 (4), 040504(2019).
- Lloyd, S., Schuld, M., Ijaz, A., Izaac, J., Killoran, N. Quantum embeddings for machine learning. arXiv preprint. arXiv:2001.03622, (2020).
- Shao, J., Ahmadi, Z., Kramer, S. Prototype-based learning on concept-drifting data streams. Proc. 20th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, , 412-421 (2014).
- Lloyd, S., Mohseni, M., Rebentrost, P. Quantum algorithms for supervised and unsupervised machine learning. arXiv preprint. arXiv:1307.0411, (2013).
- Arthur, D., Vassilvitskii, S. K-means++: The advantages of careful seeding. Proc. 18th Annual ACM-SIAM Symp. Discrete Algorithms, , 1027-1035 (2007).
- Havlíček, V., et al. Supervised learning with quantum-enhanced feature spaces. Nature. 567 (7747), 209-212 (2019).
- Qi, J., Yang, C. H., Chen, S. Y. C., Chen, P. Y. Quantum machine learning: An interplay between quantum computing and machine learning. arXiv preprint. arXiv:2411.09403, (2024).
- Kang, M. S., Heo, J., Choi, S. G., Moon, S., Han, S. W. Implementation of SWAP test for two unknown states in photons via cross-Kerr nonlinearities under decoherence effect. Sci. Rep. 9 (1), 6167(2019).
- Barnett, S. M., Chefles, A., Jex, I. Comparison of two unknown pure quantum states. Phys. Lett. A. 307 (4), 189-195 (2003).
- Andersson, E., Curty, M., Jex, I. Experimentally realizable quantum comparison of coherent states and its applications. Phys. Rev. A. 74 (2), 022304(2006).
- Filippov, S. N., Ziman, M. Probability¬based comparison of quantum states. Phys. Rev. A. 85 (6), 062301(2012).
- Barenco, A., et al. Stabilization of quantum computations by symmetrization. SIAM J. Comput. 26 (5), 1541-1557 (1997).
- Buhrman, H., Cleve, R., Watrous, J., De Wolf, R. Quantum fingerprinting. Phys. Rev. Lett. 87 (16), 167902(2001).
- Kang, M. S., Heo, J., Choi, S. G., Moon, S., Han, S. W. Implementation of SWAP test for two unknown states in photons via cross-Kerr nonlinearities under decoherence effect. Sci. Rep. 9 (1), 6167(2019).
- De Wolf, R. Quantum computing: Lecture notes. arXiv preprint. arXiv:1907.09415, (2019).
- Mashatola, L., Kader, Z., Abdulla, N., Kaur, M. Enhancing the Vietoris-Rips simplicial complex for topological data analysis: Applications in cancer gene expression datasets. Int. J. Data Sci. Anal. , 1-18 (2024).
アクセスが制限されています。このコンテンツを表示するにはログインするか、トライアルを開始してください。
再版と許可
このJoVE記事のテキストまたは図の再利用許可をリクエスト
許可をリクエスト