Approche bioinformatique de la prédiction du cancer utilisant l’algorithme de clustering quantique pour la similarité comportementale dans l’expression génique

Résumé

Ce protocole vise à regrouper les données d’expression génique pour la classification du cancer à l’aide d’un algorithme hybride Quantum K-Means qui détecte automatiquement le nombre optimal de clusters et les sépare efficacement, faisant progresser les applications de bioinformatique sur les dispositifs Noisy Intermediate-Scale Quantum (NISQ).

Résumé

Cette étude introduit un algorithme hybride de clusterisation quantique K-Means avec détection automatique de clusters pour classifier les données d’expression génique cancéreuse et non cancéreuse. La méthode utilise la cartographie quantique multi-caractéristiques pour l’encodage d’état, l’estimation quantique basée sur le test de swap, et l’optimisation basée sur le gradient quantique pour identifier dynamiquement le nombre optimal de clusters en minimisant la variance intra-cluster. Les centroïdes initiaux sont sélectionnés à l’aide d’une stratégie probabilité-distance proportionnelle, améliorant la stabilité et la précision. Appliquée aux ensembles de données sur le cancer du sein, cette approche dépasse l’algorithme K-Means quantique existant, atteignant un score Silhouette de 0,641 (contre 0,601), un indice Calinski-Harabasz de 766,57 (contre 617,65) et un indice de Davies-Bouldin de 0,659 (contre 0,704). Ces résultats indiquent une compacité et une séparation supérieures des groupes. Bien que l’algorithme proposé présente une complexité temporelle O légèrement supérieure (N×_{K max}×_{M obs}) grâce à l’optimisation itérative, il surpasse nettement les K-Means quantiques prédéfinis K en termes de précision de clusterisation, de réduction des erreurs et de faisabilité pratique. Son efficacité dans la gestion de données de haute dimension et sa résilience au bruit quantique soulignent son potentiel pour des applications réelles en bioinformatique, en particulier dans la classification du cancer à l’aide de profils d’expression génique.

Introduction

En génie biomédical, bioinformatique, statistiques, sciences sociales et économie, le regroupement est une technique fondamentale pour organiser les données en groupes homogènes significatifs. Par exemple, l’analyse topologique des données (TDA) a été appliquée aux ensembles de données d’expression génique du cancer pour révéler des schémas structurels dans des espaces de haute dimension¹. Le clustering organise les données de manière à placer des objets à forte similarité dans le même groupe, tandis que des objets dissemblables sont assignés à des groupes différents. Cela relève de l’apprentissage non supervisé et ne nécessite pas de données d’entraînement indiquées.

Au cours des dernières décennies, de nombreux algorithmes de regroupement ont été développés. Les approches classiques incluent le regroupement basé sur^{partition 2}˒³, le regroupement basé sur^{la densité 4,5}, le regroupement hiérarchique ^6,7, le regroupement basé sur la^{grille 8}˒⁹, et le regroupement basé sur modèle¹⁰. Les critiques de ces méthodes mettent en avant leurs forces mais aussi leurs limites¹¹. Bien qu’efficaces dans certains contextes, la plupart des algorithmes classiques peinent à gérer des données de haute dimension, bruiteuses ou distribuées de façon irrégulière. Par conséquent, il n’existe pas de méthode universelle de regroupement qui fonctionne de manière optimale sur tous les types de données.

Pour relever ces défis, le clustering quantique s’est imposé comme une alternative prometteuse¹². Contrairement aux algorithmes classiques, les approches inspirées du quantique exploitent la superposition, l’intrication et d’autres principes de la mécanique quantique pour explorer les espaces de données de manière plus efficace. Ce paradigme est de plus en plus accepté au sein de la communauté scientifique¹³˒¹⁴˒¹⁵˒¹⁶˒¹⁷˒¹⁸, car il démontre des avantages potentiels par rapport au clustering classique dans la gestion de jeux de données à haute dimension et bruitants. Néanmoins, les méthodes de clustering quantique existantes souffrent souvent de comptages de clusters prédéfinis ou d’initialisation instable du centroïde, ce qui réduit leur robustesse dans les applications pratiques.

Dans ce travail, un nouvel algorithme hybride de clustering quantique K-Means basé sur partitions est introduit, incorporant quatre innovations distinctes : (i) la cartographie quantique multi-caractéristiques pour coder des données d’expression génique dans l’espace de Hilbert haute dimension ; (ii) initialisation basée sur la distance proportionnelle à la probabilité, améliorant la stabilité par rapport à l’initialisation aléatoire ; (iii) Estimation quantique basée sur le test de swap pour une mesure précise de similarité ; et (iv) l’optimisation basée sur le gradient quantique pour déterminer dynamiquement le nombre optimal de clusters en minimisant la variance intra-cluster. Ces contributions distinguent la méthode proposée des approches précédentes de regroupement^{quantique 19,20}, améliorant la robustesse, l’évolutivité et l’applicabilité dans des scénarios réels de bioinformatique.

Le regroupement des données d’expression génique est une tâche cruciale en bioinformatique, notamment pour distinguer les cellules cancéreuses des cellules non cancéreuses à partir de leurs profils génétiques. Les méthodes traditionnelles de regroupement, telles que les K-Means classiques, peinent souvent à gérer la nature à haute dimension des ensembles de données d’expression génique, ce qui conduit à une classification sous-optimale. Pour surmonter ces défis, nous introduisons l’algorithme quantique K-Means avec détermination optimale de cluster, qui exploite la cartographie quantique des caractéristiques et l’initialisation probabiliste du centroïde pour obtenir des performances de clustering supérieures. Cet algorithme regroupe non seulement efficacement les données d’expression génique, mais détermine aussi automatiquement le nombre optimal de clusters, permettant d’identifier des sous-types de cancer distincts

L’algorithme proposé est appliqué à des ensembles de données contenant à la fois des profils d’expression génique cancéreuse et non cancéreuse, en les regroupant selon la similarité comportementale afin d’évaluer son efficacité.

Protocole

1. Cartographie quantique des caractéristiques

L’encodage de points de données classiques en états quantiques est réalisé en les cartographiant dans un espace de Hilbert quantique, qui peut être efficacement accédé et manipulé par un ordinateur^{quantique 16}˒^17,19. Ce processus utilise une application de caractéristiques quantiques non linéaire qui englobe des données classiques dans l’espace de Hilbert (Figure 1). Une carte de caractéristiques fixe du circuit quantique transforme les points de données d’entrée en^{états quantiques 17}, tandis que les circuits variationnels permettent des tâches d’apprentissage automatique en adaptant la base^{de mesure 22}. Un circuit variationnel se compose d’un ensemble de portes quantiques paramétrées, optimisées par des techniques hybrides quantique-classique²³.

Figure 1 : Cartographie des caractéristiques dans l’espace quantique de Hilbert. Veuillez cliquer ici pour voir une version agrandie de cette figurine.

2. Encodage du point cible et des centroïdes en qubits

Pour encoder les caractéristiques de nos points de données, nous devons effectuer des rotations en utilisant des portes U3.

Cela fait tourner les θ radians du qubit par rapport à l’axe z positif, et des radians φ par rapport à l’axe x positif.

Tous les qubits étaient initialisés dans l’état ∣0〉 avant le début du processus d’encodage. Chaque valeur d’expression génique a été normalisée à l’intervalle [0,1] et convertie en angle de rotation à l’aide de la relation θ_i=πx_i. Une porte unitaire paramétrée était ensuite appliquée à chaque qubit pour encoder la caractéristique correspondante, implémentée dans Qiskit à l’aide de l’opération qc.u(theta_i, pi, pi, qubit_index). Lorsque plusieurs caractéristiques étaient encodées, la procédure de rotation était répétée sur les qubits appropriés pour créer une représentation multi-caractéristiques. Après ces opérations, l’état quantique résultant ∣ψ〉 représentait le vecteur de caractéristiques codé dans l’espace de Hilbert. Aucune mesure n’a été effectuée à cette étape, car l’état préparé était réservé à une estimation ultérieure de la similarité.

3. Comparaison des états quantiques

Les résultats des expériences quantiques sont intrinsèquement aléatoires car les qubits sont instables par nature, comme décrit en physique quantique. Par conséquent, les conclusions et prédictions doivent être exprimées en termes de probabilités et d’incertitudes. Tirer des conclusions sans ambiguïté représente donc un véritable défi. Cependant, lorsque les états quantiques considérés sont purs, les différences entre états (avec une probabilité non nulle) peuvent être prédites sans ambiguïté par^{expérimentation 24˒25}.

Deux états quantiques, ∣ψ〉 et ∣φ〉, ont d’abord été chargés dans des registres quantiques séparés. Un qubit ancilla était alors initialisé dans l’état ∣0〉 pour contrôler l’opération de swap. Une porte de Hadamard a été appliquée à l’ancilla pour la placer en superposition avant l’exécution de l’opération contrôlée-SWAP. La porte Fredkin (CSWAP) utilisait l’ancilla comme qubit de contrôle et les deux registres de données comme cibles, permettant des interférences entre les états. Après cette opération, une seconde porte de Hadamard a été appliquée à l’ancilla pour compléter le schéma d’interférence. Seul le qubit ancilla a été mesuré, et son résultat de mesure a codé la similarité entre les deux États. Lorsque les états étaient identiques, l’ancilla donnait le résultat 0 avec probabilité 1, tandis que les états orthogonaux produisaient le résultat 0 avec une probabilité 0,5.

Figure 2 : Illustration de la comparaison basée sur la probabilité, si les états ρ et ξ sont différents, alors la distribution de probabilité observée appartient à P_E⁻ \ P_E⁺. Veuillez cliquer ici pour voir une version agrandie de cette figurine.

L’opérateur de densité ρ est associé à tout état quantique ρ ∈ S(H), tel que tr[ρ] = 1 et ρ ≥ 0. Ici, ensemble de tous les états S(H) d’un système qui sera associé à l’espace de Hilbert H. La mesure à valeur d’opérateur positif (POVM) est une mesure des caractéristiques statistiques quantiques qui est un ensemble d’opérateurs positifs E₁, . . . ,_{E n} comme E (qui agissent sur H) et l’identité I = . Une distribution de probabilité attribue la mesure E à chaque état ρ ∈ S(H) où_{p j} = tr[_{E j}ρ]≥ 0 et =^{1 26}.

4. Comparaison des états quantiques basés sur le swap

La différence entre deux états quantiques peut être mesurée à l’aide de la procédure de test SWAP en calcul quantique. Cette méthode a été introduite pour la première fois par Barenco et al.²⁷ et redécouvert plus tard par John Watrous, Ronald de Wolf, Harry Buhrman et Richard ^{Cleve 28}. Le test SWAP a été appliqué à l’informatique quantique et à l’apprentissage automatique ^{quantique 15, 29}.

Le test SWAP prend ∣ψ〉 et ∣φ〉 comme états d’entrée et produit 1 (une variable aléatoire de Bernoulli) avec une probabilité de 1/2 - 1/2〈φ,ψ〉² , ce qui estime le produit scalaire carré ^{des deux états 30}.

Explication du circuit

Considérons deux états ∣φ〉 et ∣ψ〉 du système, le protocole au début est ∣0,φ,ψ〉. Après l’application de la porte de Hadamard, l’état passe à ∣0,φ,ψ〉 + ∣1,φ,ψ〉. La porte CSWAP transforme l’état en (0,φ,ψ〉 + ∣1,ψ,φ〉). Après la deuxième porte de Hadamard, l’état devient 1/2(|0,φ,ψ〉 + ∣1,φ,ψ〉 + |0,ψ,φ〉 - ∣1,ψ,φ〉)= 1/2∣0〉(|φ,ψ〉 + |ψ,φ〉) +  1/2|1〉(|φ,ψ〉 - |ψ,φ〉). Le premier qubit est alors mesuré, la probabilité d’obtenir un résultat 0 est P(Premier qubit = 0) = 1/2 (〈φ|〈ψ| + 〈ψ|〈φ|) 1/2 (|φ,ψ〉 + |ψ,φ〉) = 1/2 + 1/2 |〈ψ|φ〉|². Si ψ et φ sont orthogonales (|〈ψ|ϕ〉|² = 0), alors la probabilité d’obtenir 0 est de 1/2. Si les états sont identiques (|〈ψ|ϕ〉|² = 1) alors la probabilité d’obtenir 0 est de 1. ²⁴

Figure 3 : (a) Circuit de la grille de Fredkin avec état polaire opposé, (b) Sortie du graphe mesuré par probabilité, (c) Circuit de la porte de Fredkin avec porte de Hadamard, (d) Sortie du graphe mesuré par probabilité. Veuillez cliquer ici pour voir une version agrandie de cette figurine.

Le circuit utilisait un qubit ancilla ainsi que deux registres encodant les états quantiques ∣ψ〉 et ∣φ〉. Tous les qubits étaient initialisés avant le début de la phase d’encodage. Les caractéristiques d’expression génique étaient ensuite encodées dans les registres respectifs à l’aide de la procédure de mappage des caractéristiques. Une porte de Hadamard était appliquée au qubit ancilla pour créer une superposition, après quoi une opération de SWAP contrôlé était effectuée entre les deux registres d’état, avec l’ancilla comme contrôle. Une seconde porte de Hadamard a été appliquée à l’ancilla pour compléter le motif d’interférence, et le qubit ancilla a ensuite été mesuré. Lorsque les deux états codés étaient identiques, l’ancilla produisait systématiquement le résultat 0. Lorsque les états étaient orthogonaux, l’ancilla donnait le résultat avec une probabilité de 0,5. Pour des états partiellement similaires, la probabilité d’obtenir 0 se situait entre 0,5 et 1, reflétant le degré de similarité entre les états.

5. Estimation de la distance quantique

En analyse de données classique, les distances entre les points de données peuvent être calculées directement à l’aide de mesures telles que la distance euclidienne ou de Manhattan ^2,3. Dans le cas des qubits sur un ordinateur quantique, cette tâche est plus complexe en raison de la nature probabiliste des états quantiques. Bien que les différences de phase et les amplitudes de probabilité puissent être mesurées, elles ne peuvent pas être directement représentées par des distances entre deux vecteurs ^{24, 26}.

Pour le regroupement, il est nécessaire d’évaluer les positions relatives des points de données par rapport aux centroïdes^{du cluster 13}. Pour assigner chaque qubit au groupe approprié, un paramètre doit être défini servant d’indicateur de proximité au centroïde correspondant du cluster.

Pour y parvenir, un paramètre est introduit qui correspond positivement à la similarité, fonctionnant ainsi comme une alternative aux mesures conventionnelles de distance ^15,30.

Le processus d’estimation de distance commençait avec un état quantique normalisé ∣Ψ〉 et un qubit auxiliaire initialisé à zéro ∣_{q 0}〉. L’objectif était d’estimer la distance entre le nouveau point de données codé en ∣_{q 1}〉 et un centroïde de cluster codé en ∣_{q 2}〉. Pour préparer la superposition requise pour le motif d’interférence, une porte de Hadamard a été appliquée au qubit ancilla, produisant l’état ( ∣0〉 + ∣1〉 ) ⊗ ∣Ψ〉 ). Une porte contrôlée-SWAP (Fredkin) était alors appliquée avec l’ancilla comme contrôle, ce qui intriquait l’ancille avec les deux états codés et permettait à leur chevauchement d’influencer le résultat de la mesure. Cette opération produisait l’état ( ∣0〉 ⊗ ∣Ψ〉 + ∣1〉 ⊗_{F swap}(∣Ψ〉) ), à partir duquel la distance basée sur le produit intérieur pouvait être extraite par une mesure ultérieure de l’ancilla.

Implémentation et sortie du circuit

Ce circuit quantique code les données d’expression génique en qubits en utilisant le codage de phase et compare ensuite deux états d’expression génique via la porte Controlled-Swap (CSwap), également connue sous le nom de Test Swap¹².

Pour créer la superposition requise, des portes d’Hadamard sont appliquées à tous les qubits (q₀ à_{q 4}), ce qui donne une superposition égale de tous les états de base |Ψ〉 = , Cette initialisation permet un calcul parallèle sur plusieurs valeurs d’expression génique. Chaque qubit subit alors une rotation de phase, , où θ_x correspond à la valeur d’expression génique mappée. Les opérateurs unitaires U(θ,π,π) appliqués aux qubits q_{1-q 4} codent les niveaux d’expression des gènes individuels, chaque angle θ représentant une version transformée de l’expression d’un gène. Cette procédure mappe des données biologiques classiques en états quantiques via le codage de phase, permettant de représenter plusieurs gènes dans un espace quantique^{de haute dimension 6}.

Les portes CSwap sont ensuite utilisées pour comparer les états encodés en les intriquant. Le qubit auxiliaire q₀ agit comme le contrôle, déterminant si les états de q₁ à_{q 4} sont inversés. Des états quantiques similaires génèrent une interférence constructive en q₀, ce qui entraîne une probabilité plus élevée de mesurer ∣0〉. Inversement, les états dissemblables augmentent la probabilité de mesurer ∣1〉. Une porte de Hadamard ultérieure sur q₀ assure l’interférence d’amplitude, permettant l’extraction d’informations de similarité par mesure.

Supposons que deux états quantiques ∣ψ〉 et ∣φ〉 représentent des ensembles de données d’expression génique distincts, |ψ〉 = ∑i a_i |i〉, |φ〉 = ∑_ib_i |i〉 .

Le test de swap évalue la fidélité (produit interne) entre eux :

P (0) = ,

Où ∣〈ψ∣φ〉∣ désigne le produit scalaire. Si P(0) ≈ 1, les états sont similaires ; si P(0) ≈ 0,5 ou moins, ils sont différents.

Ce cadre permet de comparer les ensembles de données entre patients ou conditions expérimentales (par exemple, tissu normal vs. malade). Il fournit une base efficace pour regrouper des données de haute dimension dans des modèles d’apprentissage automatique quantique. Le test de swap permet d’identifier les similitudes entre états quantiques, ce qui peut être utilisé pour regrouper les échantillons en clusters^{significatifs 4}.

Figure 4 : Circuit de mesure de la distance entre les points de données et les centroïdes. Veuillez cliquer ici pour voir une version agrandie de cette figurine.

Figure 5 : Résultat du graphique mesuré par probabilité. Veuillez cliquer ici pour voir une version agrandie de cette figurine.

Un point de données était d’abord encodé dans l’état quantique ∣ψ〉 et le centroïde correspondant du cluster était encodé dans l’état ∣φ〉. La procédure de test d’échange décrite précédemment a ensuite été exécutée pour comparer ces deux états, et la probabilité de mesure annexe P(0) a été enregistrée. La fidélité entre les états était obtenue par F=∣〈ψ∣φ〉∣², et la distance quantique était définie comme D (ψ,φ) = . Une valeur plus faible de D indiquait que le point de données était plus proche du centroïde dans l’espace des caractéristiques quantiques.

6. Sélection initiale du centroïde

L’initialisation des centroïdes de cluster est cruciale pour la stabilité et la précision du clustering K-Means. La sélection randomisée peut produire des centroïdes mal distribués, conduisant à une convergence lente et à des résultats sous-optimaux. Pour résoudre ce problème, une méthode de distance proportionnelle à probabilités inspirée de la stratégie^{K-Means++ 20} est employée. Dans l’approche améliorée par quantique, les distances sont évaluées à l’aide de l’Estimateur de distance quantique basé sur le test SWAP, garantissant que les centroïdes sélectionnés représentent mieux la distribution des données sous-jacente. Cette stratégie améliore la séparation des clusters et la robustesse algorithmique, en particulier dans les ensembles de données à haute dimension.

Le processus d’initialisation du centroïde commençait par sélectionner au hasard un point de données pour servir de premier centroïde. La distance quantique entre ce centroïde et chaque point de données restant a ensuite été calculée à l’aide de la procédure d’estimation quantique. Sur la base de ces valeurs de distance, une distribution de probabilité a été créée dans laquelle chaque point se voyait attribuer une probabilité de sélection proportionnelle à sa distance au carré du centre-centre le plus proche. De nouveaux centroïdes ont été échantillonnés selon cette distribution, et la procédure a été répétée jusqu’à obtenir le nombre désiré de centroïdes K. Cette approche produisait un ensemble initial de centroïdes avec une séparation nettement meilleure que la sélection aléatoire.

7. Calcul de la variance quantique

La variance de cluster quantifie la compacité des points de données autour de leurs centroïdes, ce qui en fait un indicateur crucial pour évaluer la qualité du clustering. Dans les K-moyennes classiques, la variance est calculée comme la distance moyenne au carré entre les points de données et leurs centroïdes assignés. Dans l’approche améliorée par quantique, ces distances sont obtenues à l’aide de l’estimateur de distance quantique (via le test SWAP), qui calcule les similarités basées sur la fidélité entre états quantiques. En additionnant les distances carrées au sein de chaque groupe et en normalisant par la taille du groupe, on obtient une valeur de variance qui reflète le degré de cohésion intra-groupe. Minimiser cette variance garantit des clusters plus serrés et plus significatifs, ce qui est particulièrement important dans les ensembles de données d’expression génique à haute dimension pour distinguer les échantillons cancéreux et non cancéreux.

L’attribution de cluster était effectuée en assignant chaque point de données quantique codé au centroïde le plus proche à l’aide d’une estimation quantique de la distance. Pour chaque cluster C_k, la distance quantique D(ψ_{i,C k}) entre chaque point de données et son centroïde était calculée. La variance au sein du groupe a ensuite été calculée à l’aide de , qui mesurait la compacité de chaque groupe. La variance totale a été obtenue en additionnant les variances individuelles de tous les groupes. Cette valeur totale de variance a été enregistrée pour déterminer le nombre optimal de clusters et pour évaluer la performance globale du clustering.

8. Optimisation basée sur le gradient quantique

Déterminer le nombre optimal de clusters (K) est un défi fondamental dans les tâches de clustering. Les K-Means traditionnelles exigent que K soit prédéfini, ce qui conduit souvent à un sous-regroupement ou à un sur-regroupement. Dans notre approche améliorée par le quantique, nous intégrons l’optimisation basée sur le gradient quantique (QGBO) pour identifier de manière adaptative le nombre optimal de clusters. L’algorithme augmente itérativement K, recalcule la variance à chaque étape et évalue la réduction de la variance (ΔV). Lorsque les améliorations de la variance tombent en dessous d’un seuil, le regroupement est interrompu. Le gradient quantique est calculé à l’aide de la règle du décalage paramétrique, qui estime les dérivées des valeurs d’espérance provenant de circuits quantiques. Cette approche garantit que le nombre final de clusters équilibre précision et efficacité, ce qui la rend particulièrement utile dans les applications de bioinformatique où le nombre réel de sous-types biologiques n’est pas connu à l’avance.

Le processus de regroupement commençait avec K=1, et la variance totale V(K) était calculée à l’aide de la procédure de calcul de la variance quantique. Le nombre d’amas a alors été augmenté à K+1, et la variance V(K+1) a été recalculée. La réduction de la variance, ΔV=V(K)−V(K+1), a été évaluée afin de déterminer si des groupes supplémentaires continuaient d’améliorer la compacité des données. L’itération s’est arrêtée lorsque ΔV est tombé en dessous du seuil prédéfini, indiquant que d’autres augmentations de K n’ont pas apporté d’améliorations significatives. Un circuit quantique paramétré avec des portes variationnelles a été construit pour surveiller les variations de courbure dans la tendance de la variance, et ces informations ont guidé le processus d’optimisation du cluster. Le nombre optimal de clusters a été choisi comme la valeur de K à laquelle la réduction de la variance s’est stabilisée, aboutissant à des clusters compacts et bien séparés.

9. Calcul de la variance de cluster et stockage dans_{la liste} V

Une fois les clusters stables formés, l’algorithme calcule la variance des clusters pour mesurer la compacité de chaque cluster. La variance_{V kj} pour un groupe donné est déterminée en utilisant les distances entre chaque point de données du groupe et le centroïde du cluster :

où : x représente un échantillon d’expression génique, C_i représente un groupe, C_ci est le centroïde du groupe C_i, V_kj représente la variance enregistrée pour la ^j-ième itération avec k grappes.

Cette variance est stockée dans une _liste de liste V, qui sera ensuite utilisée pour déterminer le nombre optimal de clusters.

10. Détermination du nombre optimal de groupes

Pour trouver le nombre optimal de clusters K, l’algorithme effectue plusieurs itérations, observant différentes conditions de départ. Les étapes clés incluent :

L’algorithme a d’abord identifié la valeur minimale de variance à partir de la liste des variances calculées pour différentes valeurs de K. La réduction de la variance entre les décomptes successifs de grappes a ensuite été mesurée à l’aide de l’expression ΔV=∣V_k−V_k−1∣, où V_k désignait la variance pour K grappes et V_k−1 représentait la variance pour K −1 groupes. Si la réduction ΔV descendait en dessous du seuil prédéfini, indiquant une amélioration négligeable du regroupement, la procédure s’arrêtait. Sinon, le nombre de clusters était incrémenté, et le calcul répété jusqu’à atteindre le nombre optimal de clusters.

11. Finalisation des clusters pour la classification du cancer et des non-cancers

Une fois le nombre optimal de clusters K déterminé, l’ensemble final de clusters représente des groupes distincts dans les données d’expression génique. Typiquement, l’algorithme donne lieu à deux clusters principaux :

Un groupe représentant des cellules cancéreuses (marquées par des signatures d’expression génique distinctes associées à une malignité).

Un groupe représentant des cellules non cancéreuses (contenant des profils d’expression génique normaux).

Les paramètres, variables et constantes utilisés dans l’algorithme proposé de regroupement Quantum K-Means sont listés dans le Tableau 1. Définissez les dimensions du jeu de données, définissez le nombre de clusters K, et appliquez des critères d’arrêt et des seuils d’optimisation pour guider le processus. Configurez les paramètres de calcul tels que le nombre de tirs par exécution et les graines aléatoires pour garantir la reproductibilité. Initialiser les centroïdes en utilisant une méthode de sélection basée sur la probabilité et les mettre à jour itérativement jusqu’à convergence. Le tableau précise également les résultats attendus, y compris les labels de cluster, les centroïdes, le K optimal, les métriques d’évaluation et les graphiques de visualisation.

Catégorie	Paramètre	Valeur / Par défaut	Notes
Jeu de données	Ensemble de données sur le cancer du sein	569 échantillons × 32 fonctionnalités (réduites à 2 composants PCA)	Réduction de dimensionnalité avec l’ACP
Nombre d’amas	K	Dynamique, initialement 1, jusqu’à 5	Optimisé par réduction de variance
Groupes maximaux	Kmax	5	Borne supérieure pour la recherche
Tirs par point	N	1024	Mesures par exécution de circuit
Tolérance d’arrêt	ε	1 × 10^-14	Critère de convergence de la variance
Seuil de pente de variance	ΔV	9.9 × 10^-4	Seuil d’arrêt pour l’optimisation
Observations	Mobsrv	3	Exécutions indépendantes par taille de cluster
Limite d’itération	–	10	Nombre maximal d’étapes de mise à jour du centroïde par exécution
Graine aléatoire	–	42	Assure la reproductibilité
Résultats attendus	–	Étiquettes de clusters, centroïdes, K optimal, métriques d’évaluation, graphiques	Exporté en fichiers .csv et .png
Variances entre groupes	Vlist	vide	Détecte l’optimal K
Centroïde j	CJ	initialisé par fonction (basé sur des probabilités proportionnelles aux distances carrées des points)	Mise à jour itérative et stocke les centroïdes finaux

Tableau 1 : Matériaux, logiciels et réglages de reproductibilité

Pas	Fonction / API (à partir de votre code)	Action	Résultat attendu
Codage de caractéristiques	qc.u(theta, pi, pi, qubit)	Encoder la caractéristique classique normalisée en rotation des qubits	État des qubits
Test SWAP / distance quantique	get_Distance(x, y) utilisant qc.cswap()	Construction d’un circuit à 3 qubits (ancilla + deux états)	Identique → P(0) ≈ 1.0 ; → orthogonale P(0) ≈ 0,5
Exécution du circuit	SamplerV2 avec AerSimulator (1024 plans)	Exécuter le circuit sur simulateur avec transpilation (niveau opt 1)	Distribution de probabilité pour le qubit ancilla
Initialisation du centroïde	initialize_centroids_kmeans_pp(pointe, k)	Sélectionnez des centroïdes initiaux proportionnels à la distance	Centroïdes de départ divers
Réaffectation de cluster	find_nearest_neighbour(pointe, centroïdes)	Attribuer des points au centre de bafouage le plus proche	Adhésions de cluster stables
Calcul de la variance	calculate_variance(centre, centers_distance)	Calculer la variance intra-cluster	La variance diminue à chaque itération
Pente de variance	grad_slope(k, V_k, k-1, V_k-1)	Comparez ΔV avec ε = 1e-14 et le seuil de pente ΔV ≤ 0,000099	K optimal détecté
Visualisation	matplotlib.pyplot, plot_histogram	Attribution de clusters et résultats quantiques	Diagrammes de points PCA, diagrammes de variance, histogrammes
Calcul métrique	silhouette_score, calinski_harabasz_score, davies_bouldin_score	Évaluer la qualité du clustering	Silhouette ≈ 0,64, CH ≈ 766, DB ≈ 0,65

Tableau 2 : Détails de l’implémentation exécutable de l’algorithme proposé.

Implémentation et algorithmes

L’algorithme Quantum K-Means avec Détermination Optimale de Cluster est une méthode de clustering améliorée par le quantum qui identifie dynamiquement le nombre optimal de clusters tout en utilisant la cartographie quantique des caractéristiques¹⁹ La procédure commence par considérer tous les points de données comme appartenant à un seul cluster. Le nombre de clusters K augmente alors progressivement. Les centres de cluster sont initialisés probabilisticement selon les distances interpoints, après quoi chaque point de données est assigné à son centroïde le plus proche, formant K clusters. La variance de groupe est ensuite calculée, et les centroïdes sont mis à jour. Ce processus de réattribution est répété de manière itérative jusqu’à ce qu’aucun autre changement ne se produise.

L’algorithme évalue la variance sur plusieurs itérations, en stockant des valeurs de variance correspondant à différents décomptes de clusters. La valeur optimale de K est déterminée en minimisant la variance tout en surveillant la réduction de la variance ΔV. Si ΔV devient négligeablement petit, la procédure prend fin ; sinon, K est incrémenté et le processus de clustering redémarre. Cette stratégie adaptative assure un partitionnement efficace et précis des données, en particulier dans les espaces de caractéristiques à haute dimension.

Figure 6 : Organigramme de la procédure proposée de clustering quantique hybride K-Means, montrant la cartographie quantique des caractéristiques, l’initialisation du centroïde, l’affectation itérative de clusters, le calcul de variance quantique, la vérification de convergence basée sur la variance et la sélection assistée par gradient quantique du nombre optimal de clusters. Veuillez cliquer ici pour voir une version agrandie de cette figurine.

Les étapes suivantes décrivent l’algorithme Quantum K-Means pour regrouper les données d’expression génique du cancer et non cancéreuses.

Algorithme : Regroupement des données d’expression génique des cellules cancéreuses et non cancéreuses à l’aide de l’algorithme quantique K-Means

Étape 1 : Cartographie quantique des caractéristiques (codage multi-fonctionnalités).
Étape 2 : En supposant qu’initialement tous les points de données appartiennent au même groupe, on fixe la valeur de K=1 (Où K : est le nombre de groupes optimaux, V : est la variance du groupe et ΔV : réduction de la variance).
Étape 3 : Initialiser les centres (choisir les points centraux initiaux en utilisant la proportion de probabilité des distances entre les points de données).
Étape 4 : Attribuez à chaque point de données leur centroïde le plus proche, ce qui formera les groupes prédéfinis « K ».
Étape 5 : Calculez la variance du groupe et placez un nouveau centroïde pour chaque groupe.
Étape 6 : Répétez l’étape 4, ce qui signifie réassigner chaque point de données au nouveau centroïde le plus proche de chaque cluster.
Étape 7 : Si une réaffectation a lieu, alors passez à l’étape 5 sinon allez à l’étape 8.
Étape 8 : Nous obtenons maintenant le cluster _{C j} (« j’ième itération avec « k » nombre de clusters) et calculons la variance V_kj= , où « x » : point de données appartient au cluster C_i, et C_ci : centroïde de cluster du cluster C_i. Tenez un registre de la variance V_kj dans _{la liste} V et recommencez à regrouper avec de nouveaux centres à partir de l’étape 3 (quelques fois non de temps, c’est-à-dire « j », où 1 ≤ j ≤ M_obsrv) avec le même « K ».
Étape 9 : Trouver la variance minimale V à partir de_{la liste} V avec « K » nombre de clusters.
Étape 10 : Calculer ΔV (ΔV = |V_k -_{V k-1}|, où V_k : est la variance avec 'K' non des amas et V_k-1 : est la variance avec 'K-1' non des clusters), si ΔV est Optimisé Basé sur le Gradient Quantique (réduction énorme), alors FINISH sinon augmente K (K=K+1) et passe à l’étape 3 avec un nouveau 'K'.
Étape 11 : Les Clusters sont prêts et le nombre optimal de clusters est « K ».

Algorithme de cartographie des caractéristiques quantiques

Algorithme 1 : Cartographie des caractéristiques quantiques

Entrées : P pointe chacun des états quantiques |ψ〉 et |Φ〉
Sortie : Une estimation de | 〈 ψ | Φ〉 |²
Étapes de l’algorithme :
Étape 1 : Nous prenons un qubit et l’initialisons par zéro ; appliquer la porte de Hadamard et la faire pivoter de la base Z vers l’axe X.
Step 2 : Nous fixons φ (0 ≤ φ ≤ π ) en radian selon la valeur du point de données par rapport à la caractéristique 1.
φ = 2*rad(^cos-1)(d₀)), où d₀ représente les valeurs de données des caractéristiques 1 et d₀ ∈ [0, 1].
Étape 3 : Nous fixons θ (0 ≤ θ ≤ π ) en radian selon la valeur du point de données par rapport à la caractéristique 2.
θ = 2 * rad(^cos-1(d₁)), où d₁ représentent les valeurs de données des caractéristiques 2 et d₁ ∈ [0, 1].
Étape 4 : Nous utilisons la porte quantique U3 pour implémenter les rotations en encodant les caractéristiques des points de données.

Cela fait pivoter Φ radian du qubit par rapport à l’axe des x positifs et de θ par rapport à l’axe z positif.

Algorithme de comparaison des états quantiques

Algorithme 2 : Comparaison des états quantiques

Entrées : Deux qubits, |_{q 1}〉 et |q₂〉, chacun des états quantiques |ψ〉 et |Φ〉
Sortie : Une estimation de | 〈ψ|Φ〉 |²
Étapes de l’algorithme :
Étape 1 : Considérer le qubit A comme un accessoire et l’initialiser par état |0〉
Étape 2 : Appliquer la porte de Hadamard sur le qubit A
Étape 3 : Appliquer le CSWAP sur le qubit |_{q 1} 〉 et |q₂ 〉 (sur l’état|ψ〉 et |Φ〉), avec A comme qubit de contrôle
Étape 4 : Appliquer la porte de Hadamard sur le qubit A
Étape 5 : Mesurez A dans sur la base de Z et enregistrez le résultat de la mesure comme M
Retour M comme notre estimation de | 〈 ψ|Φ 〉 |²

Algorithme de regroupement quantique-distance-pour-k-moyennes

Algorithme 3 : Estimateur de distance quantique et choix du nouveau centroïde de cluster

Entrées : P no de points de données et K no de centroïdes de cluster, chacun des états quantiques |ψ〉 et |Φ〉
Sortie : Nouveau centroïde regroupé associé aux points de données
Étapes de l’algorithme :
pour i dans l’allant de 1 à P :
Choisissez^{i le} point de données et enregistrez-le sur |_{q i} 〉
pour j dans la plage de 1 à K :
Choisissez j^le centroïde regroupé et réglez-le sur |_{q j} 〉
Comparer les états quantiques |q_i 〉 et |q_j 〉 c’est-à-dire i^i-thème qubit^{avec j th} centroïde et enregistrer la mesure en M comme (M_{, i}, j)
fin pour
Trouver la distance minimale (M_min ,min) de M et l’ensemble min est le nouveau centroïde de |q_i 〉 et l’enregistrer en C_i
fin pour
Retour C comme nouvelle liste de centroïdes

M= liste de toutes les distances de centroïde regroupés à partir de |_{q i} 〉 i-ième qubit
C = liste de tous les nouveaux centroïdes clusters à distance minimale C_i de |q_i 〉 ; ∀_{(i∈{1,...,P})}

Algorithme de sélection initiale du centroïde

Algorithme 4 : Calculer les points centriformes initiaux en utilisant la proportion de probabilité des distances entre les points de données

Entrées : m nombre de points de données (X₁, X₂,...,X_m), chacun des états quantiques |ψ〉 et |Φ〉
Sortie : retourner un ensemble S avec K centroïdes initiaux
Étapes de l’algorithme :
Étape 1 : Choisissez un point X au hasard parmi les points de données X_i (1 ≤ i ≤ m) et ajoutez-le à l’ensemble S
Étape 2 : Pour tout X_i, calculer la distance entre X_i à l’aide de l’estimateur de distance quantique et le point centroïde le plus proche dans S et définir la distance comme_{D dist}(X_i)
Étape 3 : Choisir un nombre Y uniformément entre 0 et D_dist(_{X 1})² + D_dist (X₂)² + ...+ D_dist (X_m)²
Étape 4 : Trouver un entier unique i tel que
D_dist (X₁)² + D_dist (X₂)² + ...+ D_dist (X_i)² >= Y >_{D dist} (X₁)² + D_dist (X₂)² + ...+ D_dist (X_i-1)²
Étape 5 : Ajouter X_i à S
Étape 6 : Jusqu’à ce que les centroïdes K soient trouvés, répétez les étapes 2 à 4

Retour S comme points centriques initiaux

Algorithme de calcul de variance quantique

Algorithme 5 : Calculer la variance quantique

Entrées : P nombre de points de données, chacun des états quantiques | ψ〉 et |Φ〉
Sortie : retourner la variance des points de données
Étapes de l’algorithme :
totalVariance ← 0
pour i dans une allure de 1 à K :
Choisissez^le centroïde regroupé et réglez-le sur |q_i 〉
totalVariancei ← 0, M ← 0
pour tout J ∈ P, associé au centroïde du cluster i :
Choisissez j^le point de données et réglez-le sur |_{q j} 〉
Comparer les états quantiques |q_i 〉 et |q_j 〉 c’est-à-dire^{i le} centroïde avec j^ième point de données et enregistrer la mesure en_{M j}
M ← M + Mj
fin pour
totalVariance_i ← [C_i est le^i-ème groupe ; |C_i | est le nombre de points de données^{dans le i} groupe, D_k est le point de données ∈ C_i &_{M k}
est la distance entre le centroïde de C_i et D_k]
totalVariance ← totalVariance + totalVariancei
fin pour
total de rendement Variance

Algorithme d’optimisation basé sur le gradient quantique (Obtenir le nombre optimal de clusters)

L’étape d’optimisation basée sur le gradient quantique détermine le nombre optimal de clusters en surveillant comment la variance intra-cluster change à mesure que K augmente. Calculer la variance pour les valeurs consécutives de K et évaluer le changement entre elles. Lorsque la réduction de la variance descend en dessous du seuil prédéfini, les groupes supplémentaires n’améliorent plus la compacité, et le K correspondant est sélectionné comme optimal. Ce critère basé sur la courbure garantit que le regroupement s’arrête au point où la structure naturelle des données est capturée sans surpartitionnement.

Algorithme 6 : Optimisation basée sur le gradient quantique

Entrées :
Un circuit quantique paramétré QC(θ) avec une porte de rotation à un qubit R_Y(θ).
Un observable quantique = Z (valeur d’espérance de Pauli-Z).
Une plage de valeurs de paramètres θ.
Sortie : La dérivée seconde f′′(θ) de la valeur espérée 〈Z〉 par rapport à θ.
Étapes de l’algorithme :
Étape 1 : Initialiser un circuit quantique à un qubit QC(θ) avec :
Une porte de rotation paramétrée_{R Y}(θ).
Mesure sur la base computationnelle (Z).
Étape 2 : Définissons la fonction Evaluate_ Espérance(θ), c’est-à-dire f′(θ) =
Liez le paramètre θ au circuit.
Exécutez le circuit sur un simulateur quantique avec N tirs.
Mesurez les probabilités de résultat P(0) et P(1).
Calculer la valeur espérée :
f(θ)=P(0)−P(1)
Étape 3 : Calculez la dérivée seconde à l’aide de la règle du décalage de paramètre :
Fixez la valeur de décalage s =
Calculer les valeurs d’espérance aux points décalés :
f(θ+s), f(θ), f(θ−s)
Calculons la dérivée seconde :
f ′′(θ) =
Étape 4 : f ′′(θ) pour analyser le comportement de réduction de la variance.

Les détails de la mise en œuvre de l’approche de clustering quantique proposée sont fournis dans le Tableau 2. Le tableau précise les fonctions exécutables et les API utilisées à chaque étape de l’algorithme, y compris l’encodage de caractéristiques dans les circuits quantiques, l’exécution du test SWAP pour l’estimation de la distance, l’initialisation du centroïde, la réaffectation itérative du cluster et l’évaluation de la variance/ΔV. Les paramètres d’exécution du circuit, tels que l’utilisation de SamplerV2 avec le backend AerSimulator à 1024 tirs et le niveau 1 d’optimisation de transpilation, sont également listés. De plus, le tableau présente les méthodes de visualisation appliquées pour générer les diagrammes de points PCA, les diagrammes de variance et les histogrammes, ainsi que les métriques d’évaluation de regroupement (silhouette_score, calinski_harabasz_score et davies_bouldin_score). En détaillant des fonctions et API spécifiques au niveau de commande, le tableau assure la reproductibilité de toutes les étapes de calcul de l’algorithme proposé.

Résultats

Un bon groupe dépendra de divers facteurs tels que la distance de séparation entre les groupes, la distance de groupe, le critère du rapport de variance, etc. Ainsi, la performance de regroupement a été évaluée à l’aide de trois indices standards : le score Silhouette, l’indice Calinski-Harabasz (indice CH) et l’indice Davies-Bouldin (indice DB). Le score de silhouette m...

Discussion

Cette étude propose un nouvel algorithme hybride de clustering quantique K-Means avec détection optimale de clusters, spécifiquement conçu pour classer les échantillons cancéreux et non cancéreux à partir de données d’expression génique de haute dimension. Cette approche intègre la cartographie quantique multi-caractéristiques, l’estimation de distance quantique basée sur le test de swap, et l’optimisation basée sur le gradient quantique pour déterminer dynamiquement le ...

Matériaux

Liste des matériaux utilisés dans cet article

Nom	Entreprise	Numéro de catalogue	Commentaires
Apple MacBook Pro (puce M1)	Apple Inc.	-	8 cœurs CPU / 8 cœurs GPU, 16 ? GB Unified Memory & mdash ; Utilisé pour la simulation locale
Jeu de données sur l’expression génique du cancer du sein	Kaggle	-	Ensemble de données comprenant 569 échantillons, 32 caractéristiques (réduites via PCA dans l’étude)
macOS Monterey (système d’exploitation)	Apple Inc.	12.6.9	Environnement d’exécution utilisé sur une machine locale
mathématiques (bibliothèque standard Python)	Fondation Python Software	Intégré	Fonctions mathématiques de base
Matplotlib	Communauté Matplotlib	3.8.4	Tracé et visualisation
NoiseModel, QuantumError, ReadoutError (Qiskit Aer)	Projet IBM / Qiskit	partie d’Aer 0.13.3	Utilisé pour simuler un bruit quantique réaliste
NumPy	Développeurs NumPy	1.26.4	Opérations numériques et manipulation de tableaux
Pandas	Équipe de développement de Pandas	2.2.2	Gestion des données, E/S, opérations tabulaires
Python	Fondation Python Software	3.10.12	Langage de programmation, utilisé dans l’environnement Jupyter / IPython
Qiskit Aer	Projet IBM / Qiskit	0.13.3	Backend simulateur, avec modélisation et exécution du bruit
Qiskit IBM Runtime &ndash ; Session, SamplerV2	Projet IBM / Qiskit	0.41.1	Cadre d’exécution pour circuits dans le simulateur
Qiskit Terra	Projet IBM / Qiskit	0.45.0	Cadre quantique pour la construction et la transpilation de circuits
scikit-learn	Développeurs SciKit-Learn	1.4.2	PCA, métriques de clustering, prétraitement des données