유전자 발현의 행동 유사성을 위한 양자 클러스터링 알고리즘을 이용한 암 예측을 위한 생물정보학적 접근법

요약

이 프로토콜은 하이브리드 양자 K-Means 알고리즘을 사용하여 암 분류를 위한 유전자 발현 데이터를 클러스터링하여 최적의 클러스터 수를 자동으로 감지하고 효율적으로 분리하여 노이지 중규모 양자(NISQ) 장치에서 생물정보학 응용 분야를 발전시키는 것을 목표로 합니다.

초록

본 연구는 암성 및 비암성 유전자 발현 데이터를 분류하기 위한 자동 클러스터 검출을 지원하는 하이브리드 양자 K-평균 클러스터링 알고리즘을 도입합니다. 이 방법은 상태 인코딩을 위한 양자 다기능 매핑, 스왑 테스트 기반 양자 거리 추정, 그리고 양자 구배 기반 최적화를 활용하여 클러스터 내 분산을 최소화하여 최적의 클러스터 수를 동적으로 식별합니다. 초기 중심체는 확률-비례 거리 전략을 통해 선택되어 안정성과 정확도를 향상시킵니다. 유방암 데이터셋에 적용할 때, 이 접근법은 기존의 양자 K-평균 알고리즘을 능가하여 실루엣 점수 0.641(0.601과 비교), 칼린스키-하라바스 지수는 766.57(617.65와 비교), 데이비스-볼딘 지수는 0.659(0.704와 비교)를 달성했습니다. 이 결과들은 우수한 클러스터 조짐성과 분리를 나타냅니다. 제안된 알고리즘은 반복적 최적화로 인해 시간 복잡도 O (N×K_max×M_obs) 가 약간 더 높지만, 클러스터링 정확도, 오류 감소, 실용적 실현 가능성에서 사전 정의된 K 양자 K-평균보다 훨씬 뛰어난 성능을 보입니다. 고차원 데이터 처리 효율성과 양자 잡음에 대한 회복력은 특히 유전자 발현 프로필을 이용한 암 분류 분야에서 실제 생물정보학 응용에 잠재력을 보여줍니다.

서론

생의공학, 생물정보학, 통계학, 사회과학, 경제학에서 클러스터링은 데이터를 의미 있고 동질적인 그룹으로 조직하는 기본 기법입니다. 예를 들어, 위상적 데이터 분석(TDA)은 암 유전자 발현 데이터셋에 적용되어 고차원 공간에서 구조적 패턴을 드러내는 데 사용되었습니다.¹, 클러스터링은 유사도가 높은 객체는 동일한 클러스터 내에 배치되고, 서로 다른 객체는 서로 다른 클러스터에 할당되도록 데이터를 조직합니다. 이는 비지도 학습에 해당하며 라벨이 붙은 학습 데이터가 필요하지 않습니다.

지난 수십 년간 수많은 군집화 알고리즘이 개발되었습니다. 고전적 접근법으로는 분할 기반 클러스터링²˒³, 밀도 기반 클러스터링 ^4,5, 계층적 클러스터링 ^6,7, 격자 기반 클러스터링⁸˒⁹, 모델 기반 클러스터링¹⁰이 있습니다. 이 방법들에 대한 리뷰는 장점과 한계를 강조합니다. 특정 맥락에서는 효과적이지만, 대부분의 고전 알고리즘은 고차원적이고 노이즈가 있거나 불규칙하게 분포된 데이터에는 어려움을 겪습니다. 따라서 모든 데이터 타입에서 최적의 성능을 내는 보편적 클러스터링 방법은 존재하지 않습니다.

이러한 문제를 해결하기 위해 양자 클러스터링은 유망한 대안으로 떠올랐습니다¹². 고전 알고리즘과 달리, 양자 영감 접근법은 중첩, 얽힘 및 기타 양자역학 원리를 활용하여 데이터 공간을 보다 효율적으로 탐색합니다. 이 패러다임은 고차원적이고 잡음이 많은 데이터셋을 다룰 때 고전적 군집화보다 잠재적 장점을 보여주면서^{연구 커뮤니티 내에서} 점점 더 받아들여지고 있습니다. 그럼에도 불구하고, 기존의 양자 클러스터링 방법은 미리 정의된 클러스터 수나 불안정한 중심체 초기화 때문에 실용적으로 견고성이 떨어지는 경우가 많습니다.

이 연구에서는 네 가지 혁신을 포함하는 새로운 분할 기반 하이브리드 양자 K-평균 클러스터링 알고리즘을 도입합니다: (i) 유전자 발현 데이터를 고차원 힐베르트 공간에 인코딩하는 양자 다기능 매핑; (ii) 무작위 초기화에 비해 안정성을 개선하는 확률 비례 거리 기반 중심체 초기화; (iii) 정확한 유사성 측정을 위한 스왑 테스트 기반 양자 거리 추정; 그리고 (iv) 클러스터 내 분산을 최소화하여 최적의 클러스터 수를 동적으로 결정하는 양자 구배 기반 최적화. 이러한 기여는 제안된 방법을 이전의 양자 클러스터링 접근법과 구^{별하여 견}고성, 확장성, 실제 생물정보학 시나리오에서의 적용성을 높인다.

유전자 발현 데이터를 클러스터링하는 것은 생물정보학에서 매우 중요한 과제로, 특히 유전적 프로필을 기반으로 암세포와 비암세포를 구분하는 데 중요합니다. 전통적인 군집화 방법인 고전적 K-평균은 유전자 발현 데이터셋의 고차원적 특성 때문에 종종 어려움을 겪어 분류가 최적이 되지 않습니다. 이러한 도전을 극복하기 위해, 우리는 양자 특징 매핑과 확률적 중심체 초기화를 활용하여 우수한 클러스터링 성능을 달성하는 Quantum K-Means Algorithm(최적 클러스터 결정)을 도입합니다. 이 알고리즘은 유전자 발현 데이터를 효율적으로 클러스터링할 뿐만 아니라, 최적의 클러스터 수를 자동으로 결정하여 서로 다른 암 아형을 식별할 수 있게 합니다

제안된 알고리즘은 암성 및 비암성 유전자 발현 프로필을 모두 포함하는 데이터셋에 적용되며, 행동 유사성에 따라 이를 클러스터링하여 효과를 평가합니다.

프로토콜

1. 양자 특징 매핑

고전 데이터 포인트를 양자 상태로 인코딩하는 것은 양자 힐베르트 공간으로 매핑함으로써 이루어지며, 양자 컴퓨터가 효율적으로 접근하고 조작할 수 있습니다¹⁶˒^17,19. 이 과정은 고전 데이터를 힐베르트 공간에 삽입하는 비선형 양자 특징 지도를 사용합니다(그림 1). 고정된 양자 회로 특징 맵은 입력 데이터 포인트를 양자 상태¹⁷로 변환하며, 변분 회로는^{측정 기저}를 적응시켜 기계 학습 작업을 가능하게 합니다. 변분 회로는 하이브리드 양자-고^{전 기법}을 통해 최적화된 매개변수화된 양자 게이트 집합으로 구성됩니다.

그림 1: 양자 힐베르트 공간에서의 특징 매핑. 이 그림의 더 큰 버전을 보시려면 여기를 클릭해 주세요.

2. 목표 점과 중심체를 큐비트로 인코딩

데이터 포인트의 특징을 인코딩하기 위해서는 U3 게이트를 사용해 회전을 수행해야 합니다.

이 방법은 큐비트를 양의 z축에서 θ 라디안으로, 양의 x축에서 Φ 라디안을 회전시킵니다.

모든 큐비트는 인코딩 과정이 시작되기 전에 ∣0 상태에서 초기화되었습니다. 각 유전자 발현 값은 범위 [0,1]로 정규화되었고, θ_i=πx_i의 관계를 사용하여 회전 각도로 변환되었습니다. 각 큐비트에 매개변수화된 유니터리 게이트가 적용되어 해당 특징을 인코딩했으며, 이는 qc.u(theta_i, pi, pi, qubit_index 연산을 사용해 Qiskit에서 구현되었습니다). 여러 특징이 인코딩될 때, 회전 절차를 적절한 큐비트 간에 반복하여 다중 특징 표현을 만들었습니다. 이 연산 이후, 결과적으로 생성된 양자 상태 ∣ψ』는 힐베르트 공간에서 인코딩된 특징 벡터를 나타낸다. 이 단계에서는 측정이 이루어지지 않았으며, 준비된 상태는 이후 유사성 추정을 위해 예약되었다.

3. 양자 상태 비교

양자 실험의 결과는 양자 물리학에서 설명하듯 큐비트가 본질적으로 불안정하기 때문에 본질적으로 무작위적입니다. 따라서 결론과 예측은 확률과 불확실성의 관점에서 표현되어야 합니다. 따라서 명확한 결론을 내리는 것은 진정한 도전 과제입니다. 그러나 고려 중인 양자 상태가 순수할 때, 상태 간 차이(0이 아닌 확률로)는 실험²⁴˒²⁵를 통해 명확하게 예측할 수 있다.

두 양자 상태인 ∣ψ〉와 ∣φ〉는 먼저 각각 다른 양자 레지스터에 로드되었다. 그 후 ∣0" 상태에서 안실라 큐비트가 초기화되어 스왑 작업을 제어했습니다. 제어 SWAP 연산이 실행되기 전에 안실라에 중첩 상태로 하기 위해 하다마르 게이트가 적용되었습니다. 프레드킨(CSWAP) 게이트는 앙실라를 제어 큐비트로, 두 개의 데이터 레지스터를 타겟으로 사용하여 상태 간 간섭을 가능하게 했습니다. 이 작업 후, 간섭 패턴을 완성하기 위해 두 번째 하다마르 게이트가 안실라에 적용되었습니다. 오직 앙실라 큐비트만 측정되었고, 그 측정 결과는 두 상태 간의 유사성을 인코딩했다. 상태가 동일할 때, 안실라는 확률 1로 결과 0을 냈고, 직교 상태는 확률 0.5로 결과를 냈다.

그림 2: 확률 기반 비교의 그림, 상태 ρ와 ξ가 다르면 관측된 확률 분포 는 P_E⁻ \ P_E⁺에 속한다. 이 그림의 더 큰 버전을 보시려면 여기를 클릭해 주세요.

밀도 연산자 ρ는 Tr[ρ] = 1이고 ρ ≥ 0인 양자 상태 ρ ∈ S(H)에 연관된다. 여기서 힐베르트 공간 H와 연관된 시스템의 모든 상태 S(H)의 집합입니다. 양의 연산자 값 측도(POVM)는 양자 통계적 특징 측정으로, 양의 연산자 E₁, ... , E_n 을 E로 (H에 작용함) 및 항등식 I = 로 구성한 양자 통계적 특징 측정입니다. 확률 분포 는 각 상태 ρ ∈ S(H)에 대해 측정 E를 할당하며, 여기서 p_j = tr[E_jρ]≥ 0 그리고 = 1²⁶이다.

4. 스왑 기반 양자 상태 비교

양자 계산에서 SWAP 테스트 절차를 통해 두 양자 상태 간의 차이를 측정할 수 있습니다. 이 방법은 Barenco 등에 의해 처음 도입되었습니다.²⁷세였으며, 이후 존 와트러스, 로널드 드 울프, 해리 버먼, 리처드 ^클리브에 의해 재발견되었다. SWAP 테스트는 양자 컴퓨팅과 양자 기계 학습에 적용되었습니다 ^{15, 29}.

SWAP 검정은 ∣ψ φ'와 ∣'를 입력 상태로 받아들이고, 확률 1/2 - 1/2〈φ,ψ ^2〉2를 출력하며, 두 상태의 내적의 제곱을 추정^합니다.

서킷 설명

시스템의 두 상태 ∣φ』와 ∣ψ』을 고려하면, 처음의 프로토콜은 ∣0,φ,ψ이다. 다마르 게이트를 적용한 후 상태는 ∣0,φ,ψ + ∣1,φ,ψ로 바뀝 니다. CSWAP 게이트는 상태를 (0,φ,ψ + ∣1,ψ,φ)로 변환합니다. 두 번째 아다마르 게이트 이후에는 상태가 1/2(|0,φ,ψ〉 + ∣1,φ,ψ + |0,ψ,φ - ∣1,ψ,φ〉)= 1/2∣0〉(|φ,ψ〉 + |ψ,φ〉) +  1/2|1〉(|φ,ψ - |ψ,φ〉)가 된다. 첫 번째 큐비트를 측정하면, 결과 0이 될 확률은 P(첫 번째 큐비트 = 0) = 1/2이다 (〈φ|〈ψ| + 〈ψ|φ|)이다. 1/2 (|φ,ψ〉 + |ψ,φ) = 1/2 + 1/2 |〈ψ|φ². ψ와 φ가 직교일 때(|〈ψ|ϕ〉|² = 0), 그렇다면 0을 얻을 확률은 1/2가 된다. 상태가 동일할 경우 (|〈ψ|ϕ〉|² = 1) 이때 0이 될 확률은 1이다. ²⁴

그림 3: (a) 극반대 상태를 가진 프레드킨 게이트 회로, (b) 확률 측정 그래프의 출력, (c) 하다마드 게이트가 있는 프레드킨 게이트 회로, (d) 측정된 확률 그래프의 출력. 이 그림의 더 큰 버전을 보시려면 여기를 클릭해 주세요.

회로는 하나의 앙실라 큐비트와 양자 상태 ∣ψ〉 및 ∣φ』를 인코딩하는 두 개의 레지스터를 사용했다. 모든 큐비트는 인코딩 단계가 시작되기 전에 초기화되었습니다. 유전자 발현 특징들은 특징 매핑 절차를 통해 해당 레지스터에 인코딩되었습니다. 앙실라 큐비트에 하다마르 게이트가 적용되어 중첩을 생성한 후, 두 상태 레지스터 간에 제어를 받아 제어된 SWAP 연산이 수행되었습니다. 간섭 패턴을 완성하기 위해 두 번째 하다마르 게이트가 앙실라에 적용되었고, 이후 앙실라 큐비트가 측정되었다. 두 인코딩된 상태가 동일할 때, 앙실라는 일관되게 결과 0을 생성했다. 상태가 직교일 때, 산실라는 확률 0.5로 결과를 얻었다. 부분적으로 유사한 상태의 경우, 0이 될 확률은 0.5에서 1 사이였으며, 이는 상태 간 유사도의 정도를 반영합니다.

5. 양자 거리 추정

고전 데이터 분석에서는 유클리드 거리 또는 맨해튼 거리 ^2,3과 같은 측정을 사용하여 데이터 점 간 거리를 직접 계산할 수 있습니다. 양자 컴퓨터의 큐비트의 경우, 양자 상태의 확률적 특성 때문에 이 작업이 더 복잡합니다. 위상 차이와 확률 진폭은 측정할 수 있지만, 두 벡터 사이의 거리로 직접 표현할 수는 ^없다.

군집 형성을 위해서는 군집 중심체에 대한 데이터 점들의 상대적 위치를 평가하는 것이^{필요합니다.} 각 큐비트를 적절한 클러스터에 할당하려면, 해당 클러스터 중심체와의 근접성을 나타내는 매개변수를 정의해야 합니다.

이를 위해 유사도와 양의 상관관계를 가진 매개변수가 도입되어, 기존 거리 측정값 ^15,30의 대안으로 기능합니다.

거리 추정 과정은 정규화된 양자 상태 ∣Ψ》와 0초기화된 보조 큐비트 ∣q₀"에서 시작되었다. 목표는 ∣q₁로 인코딩된 새로운 데이터 포인트와 ∣q₂로 인코딩된 클러스터 중심체 사이의 거리를 추정하는 것이었습니다. 간섭 패턴에 필요한 중첩을 준비하기 위해 앙실라 큐비트에 하다마르 게이트가 적용되어 상태 ( ∣0 + ∣1》 ) ⊗ ∣Ψ』 를 생성했다. 그 후 제어-SWAP(프레드킨) 게이트가 적용되어 앙실라를 두 인코딩 상태와 얽히고 겹침이 측정 결과에 영향을 미치도록 했습니다. 이 연산은 상태 ( ∣0 ⊗ ∣Ψ〉 + ∣1》 ⊗ F_스왑(∣Ψ))을 생성했으며, 이후 앙실라의 측정을 통해 내곱 기반 거리를 추출할 수 있었다.

회로 구현 및 출력

이 양자 회로는 위상 부호화를 사용하여 유전자 발현 데이터를 큐비트로 인코딩하고, 이후 제어-스왑(CSwap) 게이트(스왑 테스트¹²)를 통해 두 유전자 발현 상태를 비교합니다.

필요한 중첩을 생성하기 위해 모든 큐비트(q₀에서 q₄)에 하다마르 게이트를 적용하여 모든 기저 상태의 동일한 중첩 |Ψ〉 = 이 초기화를 통해 여러 유전자 발현 값에 대한 병렬 계산이 가능해집니다. 각 큐비트는 위상 회전을 거치며, θ_x는 매핑된 유전자 발현 값에 해당합니다. 큐비트 q_{1-q 4}에 적용된 유니터리 연산자 U(θ,π,π)는 개별 유전자의 발현 수준을 인코딩하며, 각 각도 θ는 유전자 발현의 변형된 버전을 나타냅니다. 이 절차는 위상 부호화를 통해 고전적 생물학적 데이터를 양자 상태로 매핑하여 고차원 양자 공간 내에 여러 유전자를 표현할 수 있게 합니다^.

CSwap 게이트는 인코딩된 상태를 얽히는 데 사용됩니다. 보조 큐비트 q₀ 이 제어 역할을 하여 q₁과_{q 4} 의 상태가 바뀌었는지 여부를 결정합니다. 유사한 양자 상태는 q₀에서 구성적 간섭을 생성하여 ∣0을 측정할 확률을 높인다. 반대로, 서로 다른 상태일수록 ∣1을 측정할 확률이 증가한다. q₀ 에 이어 하다마르 게이트를 적용하면 진폭 간섭이 보장되어, 측정을 통해 유사성 정보를 추출할 수 있습니다.

두 양자 상태 ∣ψ』와 ∣φ』가 서로 다른 유전자 발현 데이터셋을 나타낸다고 가정하자, |ψ = ∑_ia_i |i〉, |φ = ∑_ib_i |i』 .

스왑 테스트는 이들 간의 충실도(내부 내역)를 평가합니다:

P (0) = ,

여기서 ∣〈ψ∣φ〉∣은 내적을 나타냅니다. P(0)≈ 1이면, 상태는 유사하다; P(0) ≈ 0.5 이하라면, 두 개는 다릅니다.

이 프레임워크는 정상 조직과 병든 조직 등 환자 또는 실험 조건 간 데이터셋 비교를 가능하게 합니다. 이는 양자 기계 학습 모델 내에서 고차원 데이터를 클러스터링하는 효율적인 기반을 제공합니다. 스왑 테스트는 양자 상태 간 유사성을 식별하는 것을 지원하며, 이는 샘플을 의미 있는 클러스터로 그룹화하는 데 활용될 수 있습니다^.

그림 4: 데이터 점과 중심체 간 거리 측정 회로. 이 그림의 더 큰 버전을 보시려면 여기를 클릭해 주세요.

그림 5: 확률 측정 그래프 출력. 이 그림의 더 큰 버전을 보시려면 여기를 클릭해 주세요.

먼저 데이터 포인트가 양자 상태 ∣ψ』에 인코딩되었고, 해당 클러스터 중심체가 상태 ∣φ》에 인코딩되었다. 앞서 설명한 스왑 테스트 절차를 실행하여 이 두 상태를 비교하고, 앙실라 측정 확률 P(0)를 기록했습니다. 상태 간의 충실도는 F=∣〈ψ∣φ〉∣²로 얻어졌고, 양자 거리는 D (ψ,φ) = 로 정의되었다. D가 작을수록 데이터 포인트가 양자 특징 공간에서 중심에 더 가깝다는 의미였다.

6. 초기 중심체 선택

클러스터 중심체의 초기화는 K-평균 클러스터링의 안정성과 정확성에 매우 중요합니다. 무작위 선택은 중심체가 분포가 부실하여 수렴 속도가 느리고 결과가 최적이 되지 않을 수 있습니다. 이 문제를 해결하기 위해 K-Means++ 전략²⁰ 에서 영감을 받은 확률-비례 거리 방법이 사용되었습니다. 양자 강화 접근법에서는 SWAP 테스트를 기반으로 한 양자 거리 추정기를 사용하여 거리를 평가하여 선택한 중심점이 기본 데이터 분포를 더 잘 나타내도록 보장합니다. 이 전략은 클러스터 분리를 강화하고 특히 고차원 데이터셋에서 알고리즘의 견고성을 향상시킵니다.

중심체 초기화 과정은 무작위로 한 데이터 포인트를 선택해 첫 번째 중심체로 사용하는 것으로 시작되었습니다. 이 중심체와 남은 모든 데이터 점 사이의 양자 거리는 양자 거리 추정 절차를 통해 계산되었다. 이 거리 값을 바탕으로 각 점에 가장 가까운 중심체로부터의 제곱 거리에 비례하는 선택 확률을 부여하는 확률 분포가 생성되었습니다. 이 분포에 따라 새로운 중심체를 샘플링하고, 원하는 중심체 수 K가 얻을 때까지 이 과정을 반복했습니다. 이 방법은 무작위 선택보다 훨씬 나은 분리를 가진 초기 중심체 집합을 생성했다.

7. 양자 분산 계산

군집 분산은 중심점 주변의 데이터 점들의 조밀함을 정량화하여 군집 품질을 평가하는 데 중요한 지표입니다. 고전적 K-평균에서 분산은 데이터 점과 할당된 중심점 간의 평균제곱 거리로 계산됩니다. 양자 강화 접근법에서는 이 거리들을 SWAP 테스트를 통해 양자 거리 추정기를 사용하여 양자 상태 간의 충실도 기반 유사성을 계산합니다. 각 클러스터 내 거리를 제곱 값으로 합하고 클러스터 크기로 정규화하면, 클러스터 내 응집력 정도를 반영하는 분산 값을 얻습니다. 이 분산을 최소화하면 더 촘촘하고 의미 있는 군집이 형성되며, 이는 암과 비암 샘플을 구분하는 데 특히 중요한 고차원 유전자 발현 데이터셋에서 중요합니다.

클러스터 할당은 양자 거리 추정을 사용하여 각 인코딩된 양자 데이터 점을 가장 가까운 중심체에 할당하여 수행되었습니다. 각 클러스터 C_k에 대해, 각 데이터 점과 그 중심체 사이의 양자 거리 D(ψ_{i,C k})가 계산되었다. 클러스터 내 분산은 각 클러스터의 집단성을 측정하는 를 사용하여 계산했습니다. 전체 분산은 모든 클러스터 간 개별 분산을 합산하여 얻어졌습니다. 이 총 분산 값은 최적의 클러스터 수를 결정하고 전체 클러스터링 성능을 평가하기 위해 기록되었습니다.

8. 양자 구배 기반 최적화

최적의 클러스터 수(K)를 결정하는 것은 클러스터링 작업에서 근본적인 도전 과제입니다. 전통적인 K-평균은 K 가 미리 정의되어야 하며, 이는 종종 과밀화(under-clustering) 또는 과다 클러스터링(over-clustering)으로 이어집니다. 양자 강화 접근법에서는 QGBO(QGBO) 를 통합하여 최적의 클러스터 수를 적응적으로 식별합니다. 알고리즘은 K를 반복적으로 증가시키고, 각 단계마다 분산을 재계산하며, 분산 감소(ΔV)를 평가합니다. 분산 개선이 임계값 이하로 떨어지면 군집화가 종료됩니다. 양자 기울기는 매개변수-변환 규칙을 사용하여 계산되며, 이는 양자 회로의 기대값 미분을 추정합니다. 이 접근법은 최종 클러스터 수가 정확성과 효율성을 균형 있게 유지하여, 생물학적 아형의 실제 수가 사전에 알려지지 않은 생물정보학 응용 분야에서 특히 유용합니다.

클러스터링 과정은 K=1에서 시작되었으며, 양자 분산 계산 절차를 사용해 총 분산 V(K) 를 계산했습니다. 클러스터 수는 K+1로 증가했고, 분산 V(K+1) 는 재계산되었습니다. 분산 감소인 ΔV=V(K)−V(K+1)는 추가 클러스터가 데이터의 집소성을 계속 향상시키는지 평가했습니다. ΔV 가 미리 정의된 임계값 아래로 떨어지면 반복이 중단되었으며, 이는 K 를 추가로 늘려도 의미 있는 개선이 없었음을 나타냅니다. 변분 게이트가 포함된 매개변수화된 양자 회로가 구성되어 분산 추세의 곡률 변화를 모니터링했으며, 이 정보는 클러스터 최적화 과정을 안내했습니다. 분산 감소가 안정화되어 집단이 조밀하고 잘 분리된 집단이 되는 K의 값 으로 최적의 군집 수가 선택되었습니다.

9. 클러스터 분산 계산 및 V_리스트에 저장

안정 클러스터가 형성되면, 알고리즘은 각 클러스터의 소소성을 측정하기 위해 클러스터 분산을 계산합니다. 주어진 클러스터에 대한 분산 V_kj 는 클러스터 내 각 데이터 포인트와 클러스터 중심체 사이의 거리를 사용하여 결정됩니다:

여기서 x는 유전자 발현 샘플, C_i는 클러스터, C_ci는 클러스터 _{C i}의 중심점, V_kj는 k 클러스터가 포함된 j^번째 반복 동안 기록된 분산을 나타냅니다.

이 분산 은 V_리스트에 저장되며, 이후 최적의 클러스터 수를 결정하는 데 사용됩니다.

10. 최적의 클러스터 수 결정

최적의 클러스터 수를 찾기 위해 알고리즘은 여러 차례 반복하며 서로 다른 시작 조건을 관찰합니다. 주요 단계는 다음과 같습니다:

알고리즘은 먼저 K의 다양한 값에 대해 계산된 분산 목록에서 최소 분산 값을 식별했습니다. 연속된 클러스터 카운트 간 분산 감소는 ΔV=∣V_k−_{V k−1}∣이라는 식으로 측정되었으며, V_k 는 K 클러스터의 분산을, V_k−1 은 K−1 클러스터의 분산을 나타냈다. 감소 ΔV가 미리 정의된 임계값 이하로 떨어져 군집 형성 개선이 무시할 수 있을 정도로 미미하면 절차가 종료되었습니다. 그렇지 않으면 클러스터 수를 점차 늘리고, 최적의 클러스터 수에 도달할 때까지 계산을 반복했습니다.

11. 암 및 비암 분류에 대한 군집 최종 확정

최적의 클러스터 수 K 가 결정되면, 최종 클러스터 집합은 유전자 발현 데이터 내에서 서로 다른 그룹을 나타냅니다. 일반적으로 알고리즘은 두 가지 주요 군집을 생성합니다:

한 군집은 암세포를 나타내며(악성 종양과 관련된 뚜렷한 유전자 발현 서명으로 표시됨).

정상 유전자 발현 프로필을 가진 비암세포를 나타내는 클러스터 중 하나.

제안된 양자 K-평균 군집화 알고리즘에 사용되는 매개변수, 변수, 상수는 표 1에 나열되어 있습니다. 데이터셋 차원을 정의하고, 클러스터 수 K를 설정하며, 프로세스를 안내할 수 있도록 정지 기준과 최적화 임계값을 적용하세요. 재현성을 보장하기 위해 한 번의 샷 수와 무작위 시드 같은 계산 설정을 설정하세요. 확률 기반 선택 방법으로 중심을 초기화하고 수렴할 때까지 반복적으로 업데이트합니다. 표는 클러스터 라벨, 중심점, 최적 K, 평가 지표, 시각화 플롯 등 기대 출력도 명시합니다.

카테고리	매개변수	가치 / 디폴트	주석
데이터셋	유방암 데이터셋	569개의 샘플× 32개의 특징(2개의 PCA 성분으로 축소)	PCA에 의한 차원 감소
클러스터 수	K	동적 모드, 처음에는 1명, 최대 5명까지	분산 감소를 이용한 최적화
최대 군집	K맥스	5	탐색의 상한
득점당 슛 수	N	1024	회로 실행별 측정값
내성 중단	ε	1 × 10^-14	분산 수렴 기준
분산 기울기 임계값	ΔV	9.9 × 10^-4	최적화를 위한 스톱핑 임계값
관찰	몹 자비구	3	클러스터 크기별 독립 실행
반복 한계	–	10	실행당 최대 중심체 업데이트 단계
무작위 시드	–	42	재현성을 보장합니다
기대 출력	–	클러스터 라벨, 중심점, 최적 K, 평가 지표, 플롯	.csv 파일과 .png 파일로 내보내기
클러스터 간 분산	V리스트	비어 있어	최적 K 감지
중심 j	CJ	함수별로 초기화됨(점들의 거리 제곱에 비례하는 확률에 기반함)	반복적으로 업데이트하고 최종 중심을 저장합니다

표 1: 재료, 소프트웨어 및 재현성 설정

스텝	함수 / API (코드에서)	작전	예상 결과
특징 인코딩	QC.U(쎄타, 파이, 파이, 큐비트)	정규화된 고전 특징을 큐비트 회전으로 인코딩합니다	큐비트 상태
SWAP 테스트 / 양자 거리	get_Distance(x, y) 사용: qc.cswap()	3-큐비트 회로 구축 (안실라 + 두 상태)	동일 → P(0) ≈ 1.0; 직교 → P(0) ≈ 0.5
회로 실행	AerSimulator를 사용한 샘플러V2 (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-평균 알고리즘은 양자 특징 매핑을 활용하여 최적의 클러스터 수를 동적으로 식별하는 양자 강화 클러스터링 방법이다.¹⁹ 절차는 모든 데이터 포인트를 단일 클러스터에 속하는 것으로 간주하는 것으로 시작한다. 클러스터 K 의 수는 점진적으로 증가합니다. 클러스터 중심은 점 간 거리에 따라 확률적으로 초기화되며, 이후 각 데이터 포인트는 가장 가까운 중심점에 할당되어 K 개의 클러스터를 형성합니다. 클러스터 분산이 계산되고 중심점이 업데이트됩니다. 이 재할당 과정은 추가 변경이 없을 때까지 반복됩니다.

이 알고리즘은 여러 반복에 걸친 분산을 평가하며, 서로 다른 클러스터 수에 대응하는 분산 값을 저장합니다. K 의 최적 값은 분산 감소 ΔV를 모니터링하면서 분산을 최소화하여 결정됩니다. ΔV가 무시할 정도로 작아지면 절차가 종료됩니다; 그렇지 않으면 K 를 증가시키고 클러스터링 과정이 다시 시작됩니다. 이 적응형 전략은 특히 고차원 특징 공간에서 데이터의 효율적이고 정확한 분할을 보장합니다.

그림 6: 제안된 하이브리드 양자 K-평균 클러스터링 절차의 흐름도로, 양자 특징 매핑, 중심체 초기화, 반복적 클러스터 할당, 양자 분산 계산, 분산 기반 수렴 검사, 그리고 최적의 클러스터 수의 양자 기울기 지원 선택을 보여줍니다. 이 그림의 더 큰 버전을 보시려면 여기를 클릭해 주세요.

다음 단계들은 암 및 비암 유전자 발현 데이터를 클러스터링하는 양자 K-평균 알고리즘을 개략적으로 설명합니다.

알고리즘: 양자 K-평균 알고리즘을 이용한 암세포와 비암세포의 유전자 발현 데이터를 클러스터링하기

1단계: 양자 특징 매핑(다중 특징 인코딩).
2단계: 처음에 모든 데이터 포인트가 같은 클러스터에 속한다고 가정하면, K=1의 값을 설정합니다(여기서 K:는 최적 클러스터의 번호, V:는 클러스터 분산, ΔV는 분산 감소).
3단계: 중심 초기화 (데이터 포인트 간 거리의 확률 비율을 사용하여 초기 중심점을 선택).
4단계: 각 데이터 포인트를 가장 가까운 중심체에 할당하면, 미리 정의된 'K' 클러스터가 형성됩니다.
5단계: 클러스터 분산을 계산하고 각 클러스터의 새로운 중심점을 배치합니다.
6단계: 4단계를 반복하는데, 즉 각 데이터포인트를 각 클러스터의 가장 가까운 새로운 중심체로 재할당하는 것입니다.
7단계: 재배정이 발생하면 5단계로 가고, 그 후에는 8단계로 가세요.
8단계: 이제 클러스터 C_j(클러스터 중 'k' 없는 'j' 번째 반복)를 얻고, 분산 V_kj= 를 계산합니다. 여기서 'x'는 클러스터 C_i에 속하는 데이터 포인트, C_ci는 클러스터 C_i의 클러스터 중심자입니다. V_목록에 분산 V_kj를 기록하고, 3단계의 새로운 센터들(몇 번, 예를 들어 'j' 횟수, 1 ≤ j ≤ M_obsrv)에서 같은 'K'로 클러스터링을 다시 시작하세요.
9단계: 클러스터의 'K' 수를 가진 V_리스트 에서 최소 분산 V를 찾는다.
10단계: ΔV (ΔV = |V_k - V_k-1|, 여기서 V_k: 는 클러스터의 'K' 없는 분산, V_k-1: 클러스터의 'K-1' 없음과의 분산입니다). 만약 ΔV가 양자 구배 기반 최적화(Quantum Gradient Based Optited, 대규모 축소)라면, FINISH 아니면 K를 증가시키고 (K=K+1) 새로운 'K'로 3단계로 넘어갑니다.
11단계: 클러스터는 준비되었고 최적의 클러스터 수는 'K'입니다.

양자 특징 매핑 알고리즘

알고리즘 1: 양자 특징 매핑

입력: P 가 각각의 양자 상태 |ψ』와 |Φ를 가리킨다.
결과물: | 〈 ψ | Φ〉 |²
알고리즘 단계:
1단계: 큐비트를 취해 0으로 초기화합니다; Hadamard 게이트를 적용하고 Z 기저에서 X축으로 회전시킵니다.
Step 2: 특징 1에 대한 데이터 포인트 값에 따라 라디안 내에서 φ(0 ≤ φ ≤ π )를 설정합니다.
φ = 2*rad(^cos-1)(d₀)), 여기서 d₀ 은 특징 1의 데이터 값을, d₀ 은 [0, 1]∈ 나타냅니다.
3단계: 우리는 특징 2에 대한 데이터 점의 값에 따라 θ (0 ≤ θ ≤ π )를 라디안 내에 설정합니다.
θ = 2 * Rad(^Cos-1(D₁)), 여기서 d₁ 은 특징 2와 D₁ 의 데이터 값을 나타냅니다 [0, 1]∈.
4단계: 우리는 U3 양자 게이트를 사용하여 데이터 포인트의 특징을 인코딩하는 회전을 구현합니다.

이 방식은 큐비트 Φ를 양의 x축에 대해 회전시키고, θ 라디안을 양의 z축에 대해 회전시킵니다.

양자 상태 알고리즘 비교

알고리즘 2: 양자 상태 비교

입력: 양자 상태 |ψ』와 |q₂』 각각 두 큐비트 |q₁』와 |Φ』
결과물: | 〈ψ|Φ』 |²
알고리즘 단계:
1단계: 큐비트 A를 안실라로 간주하고 상태 |0으로 초기화하기》
2단계: 큐비트 A에 하다마르 게이트 적용
3단계: |q₁ 〉와 |q₂ 〉 큐비트(상태에 대해 |ψ 그리고 |Φ"), A를 제어 큐비트로
4단계: 큐비트 A에 하다마르 게이트 적용
5단계: Z를 기준으로 측정 A를 측정하고 측정 결과를 M으로 기록한다
귀환 M을 |의 추정치로 〈 ψ|Φ 〉 |²

k-평균 클러스터링을 위한 양자 거리 추정기 알고리즘

알고리즘 3: 양자 거리 추정기 및 새로운 클러스터 중심체 선택

입력: 데이터 포인트의 P 노, 클러스터 중심체의 K 노, 각각의 양자 상태 |ψ 그리고 |Φ》
결과물: 데이터 포인트와 연관된 새로운 군집 중심체
알고리즘 단계:
i는 1에서 P까지 범위에 속한다:
i^번째 데이터 포인트를 골라 |q_i 에 기록하세요
j가 1에서 K까지 범위에 있을 때:
j^개의 클러스터 중심체를 선택하고 |q_j 에 설정하세요
양자 상태 |q_i 와 |q_j 비교즉, j^번째 중심점을 가진 i^번째 큐비트를 사용하여 M 내에서 측정값을 (M_i, j)로 기록합니다.
끝
M에서 최소 거리(M_min ,min)를 찾고, min을 |q_i의 새로운 중심점으로 삼 습니다그리고 C_i로 기록한다
끝
귀환 C는 우리의 새로운 중심체 목록입니다

M= |q_i "i" ith 큐비트로부터의 모든 클러스터 중심체 거리 목록
C = |q_i 의 새로 계산된 최소 거리 클러스터 중심체 C_i 목록; ∀_{(i∈{1,...,P})}

초기 중심체 선택 알고리즘

알고리즘 4: 데이터 점 간 거리의 확률 비율을 이용해 초기 중심점을 계산한다

입력: m no 데이터포인트 (X₁,_{X 2},...,X_m), 각 양자 상태 |ψ 그리고 |Φ》
출력: K개의 초기 중심체를 가진 집합 S를 반환한다
알고리즘 단계:
1단계: 데이터 점 X_i (1 ≤ i ≤ m)에서 무작위로 한 점 X를 선택하여 집합 S에 더합니다
2단계: 모든 X_i에 대해 양자 거리 추정기를 사용해 X_i 사이의 거리와 S 내 가장 가까운 중심점 사이의 거리를 계산하고 거리를 D_dist(X_i)로 설정합니다
3단계: 0과 D_거리(X₁)² + D_거리 (X₂)² + ...+ D_거리 (X_m)² 사이에서 균등하게 숫자 Y를 선택한다
4단계: 다음과 같은 유일한 정수 i를 찾는다.
D_구역 (X₁)² + D_구역 (_{X 2})² + ...+ D_구역 (_{X i})^² >= Y > D_구역 (X₁)² + D_구역 (X₂)² + ...+ D_구역 (X_i-1)^²
5단계: X_i 더하기
6단계: K 중심체가 발견될 때까지 2 – 4단계를 반복합니다

귀환 S는 초기 중심점으로서

양자 분산 계산 알고리즘

알고리즘 5: 양자 분산 계산

입력: 각 양자 상태 | ψ 그리고 |Φ》
출력: 데이터 포인트의 분산을 반환합니다.
알고리즘 단계:
토탈 분산 ← 0
i는 1에서 K까지 범위에 속한다:
클러스터된 중심을 하나 골라서 |q_i 에 설정하세요 "
totalVariancei ← 0, M ← 0
모든 J에 대해 ∈ P, 클러스터 중심체 i와 연관됨:
j^번째 데이터 포인트를 선택하고 |q_j 에 설정하세요 :』
양자 상태 |q_i 와 |q_j 비교즉, j^번째 데이터 포인트를 가진 I^번째 중심체를 설정하고 M_j 단위로 측정값을 기록하는 것입니다
M ← M + Mj
끝
totalVariance_i ← [C_i는 i^번째 클러스터; |C_i | 는 i ^번째 클러스터의 데이터 점의 집합이며, D_k는 C_i 및 M_k ∈ 데이터 점입니다
C_i 에서 D_k 사이의 중심체 사이의 거리입니다.
토탈 분산 ← totalVariance + totalVariancei
끝
총 분산 반환

양자 구배 기반 최적화 알고리즘 (클러스터의 최적 수 얻기)

양자 구배 기반 최적화 단계는 클러스터 내 분산이 K가 증가함에 따라 어떻게 변하는지를 모니터링하여 최적의 클러스터 수를 결정합니다. 연속된 K 값들의 분산을 계산하고 그 값들 간의 변화를 평가합니다. 분산 감소가 미리 정의된 임계값 이하로 떨어지면, 추가 클러스터는 더 이상 집소성을 개선하지 못하며, 해당 K가 최적으로 선택됩니다. 이 곡률 기반 기준은 데이터 내 자연스러운 구조가 과도한 분할 없이 포착되는 지점에서 클러스터링이 멈추도록 보장합니다.

알고리즘 6: 양자 구배 기반 최적화

입력:
단일 큐비트 회전 게이트 R_Y(θ)를 가진 매개변수화된 양자 회로 QC(θ)입니다.
양자 관측 가능 값 = Z (파울리-Z 기대값).
매개변수 값 θ의 범위입니다.
결과물: 기대값 〈Z〉의 2차 미분 f′′(θ)이다.
알고리즘 단계:
1단계: 단일 큐비트 양자 회로 QC(θ)를 다음과 같이 초기화합니다:
매개변수화된 회전 게이트 R_Y(θ).
계산(Z) 기준에서의 측정.
2단계: 함수를 정의하라: 기대값(θ) Evaluate_ 즉 , f′(θ) =
매개변수 θ를 회로에 결합하세요.
N발로 양자 시뮬레이터에서 회로를 실행 하세요.
결과 확률 P(0)와 P(1)를 측정합니다.
기대값 계산:
f(θ)=P(0)−P(1)
3단계: 매개변수 이동 규칙을 사용하여 2차 미분을 계산합니다:
이동 값 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 지수)의 세 가지 표준 지수를 사용하여 평가되었습니다. 실루엣 점수는 클러스터 간 분리를 측정하며 , 여기서 i_c 는 평균 클러스터 내 거리, n_c 는 평균 가장 가까운 클러스터 거리입니다. 범위는 ...

토론

본 연구는 고차원 유전자 발현 데이터를 사용하여 암 및 비암성 샘플을 분류하기 위해 특별히 설계된 최적 클러스터 검출 기능을 갖춘 새로운 하이브리드 양자 K-평균 클러스터링 알고리즘을 제안합니다. 이 접근법은 양자 다기능 매핑, 스왑 테스트 기반 양자 거리 추정, 양자 구배 기반 최적화를 통합하여 최적의 클러스터 수를 동적으로 결정합니다. 기존의 K-평균 알고리즘이 미리 정의된 클러스터 수를 필요로 하고 초기 중심 선택에 민감한 것과 달리, 제안된 방법은 안정성과 수렴을 보장하기 위해 확률-비례 중심체 초기화를 사용합니다.

최적의 클러스터 결정이 포함된 양자 K-평균 알고리즘은 양자 특징 매핑과 확률적 중심체 초기화를 활용하여 유전자 발현 프로필과 같은 복잡한 데이터셋에서 클러스터링 성능을 향상시킵니다. 양자 원리를 클러스터링 파이프라인에 통합함으로써 이 방법은 그룹 간 분리를 개선하고 고...

재료

이 논문에 사용된 재료 목록

이름	회사	카탈로그 번호	댓글
애플 맥북 프로 (M1 칩)	애플 주식회사	-	8코어 CPU / 8코어 GPU, 16코어? GB 통합 메모리 & mdash; 로컬 시뮬레이션에 사용
유방암 유전자 발현 데이터셋	캐글	-	569개의 샘플, 32개의 특징(연구 내 PCA로 축소됨)
macOS Monterey (운영 체제)	애플 주식회사	12.6.9	로컬 머신에서 사용되는 런타임 환경
수학 (파이썬 표준 라이브러리)	파이썬 소프트웨어 재단	내장형	기본 수학 함수
매트플롯립	MatplotLib 커뮤니티	3.8.4	플롯 작성 및 시각화
NoiseModel, QuantumError, ReadoutError (Qiskit Aer)	IBM / Qiskit 프로젝트	Aer 0.13.3의 일부입니다	현실적인 양자 잡음을 시뮬레이션하는 데 사용됩니다
넘버피	넘파이 개발자들	1.26.4	수치 연산과 배열 조작
판다	판다스 개발팀	2.2.2	데이터 처리, 입출력 및 표 형식 연산
파이썬	파이썬 소프트웨어 재단	3.10.12	Jupyter / IPython 환경에서 사용되는 프로그래밍 언어
키스킷 아에르	IBM / Qiskit 프로젝트	0.13.3	노이즈 모델링과 실행이 가능한 시뮬레이터 백엔드입니다
Qiskit IBM 런타임 & ndash; 세션, SamplerV2	IBM / Qiskit 프로젝트	0.41.1	시뮬레이터에서 회로를 위한 실행 프레임워크
키스킷 테라	IBM / Qiskit 프로젝트	0.45.0	회로 구성 및 변환을 위한 양자 프레임워크
시킷-학습	Scikit-Learn 개발자	1.4.2	PCA, 클러스터링 지표, 데이터 전처리