Spectrométrie de masse et métabolomique

Spectrométrie de masse et métabolomique

Application de l’apprentissage automatique

Introduction

Ce chapitre sera consacré aux résultats découlant de l’application de l’apprentissage automatique aux données de spectrométrie de masse. Il contient aussi les résultats d’une nouvelle méthode qui a été développée au cours de cette maîtrise.

Méthodes à noyau

Il faut par contre introduire les différents algorithmes utilisés. Un type d’algorithme qui fut utilisé au cours des travaux présentés ici est la classe des méthodes à noyau. Ces méthodes furent utilisées mal-gré le fait qu’elles ne sont pas parcimonieuses et ni interprétables, ce qui est une des caractéristiques recherchées dans ce projet. Par contre, les méthodes à noyau sont aisément adaptées aux problèmes auxquelles elles sont appliquées. Dans ce type de méthode, l’élément principal est la fonction de noyau (kernel function) qui projette les exemples d’apprentissage dans une dimensionnalité supérieure afin de pouvoir mieux séparer les classes d’exemples Boser et collab. (1992). Un exemple de ce procédé est présenté à la figure 2.1.
On cherche à avoir une fonction qui permet de faire le produit scalaire entre les vecteurs de caracté-ristiques des exemples sans avoir en mémoire les vecteurs de caractéristiques dans l’espace de dimen-sionnalité supérieure (que l’on dénote usuellement f ), ce qui est une caractéristique additionnelle des méthodes à noyau. On cherche en fait à obtenir directement la matrice de taille n par n, où n est le nombre d’exemples dans l’ensemble d’entraînement. On nomme cette matrice la matrice de Gram. C’est en se basant sur cette matrice que les algorithmes utilisant les méthodes à noyau peuvent faire de la classification. Cette matrice représente en fait une mesure de similarité entre les exemples, c’est-à-dire que si k(x; x0) est grand alors les deux exemples x et x0 sont similaires et proches dans l’espace du noyau et si k(y; y0) est petit, ou même négatif dans certains cas, alors les exemples y et y0 sont dissimilaires et donc éloignés dans l’espace du noyau.
k(x; x0) = f (x) f (x0) (2.1)
L’algorithme utilisant les méthodes à noyau le plus répandu est l’algorithme des machines à vecteur de support (Support Vector Machine, SVM) Cortes et Vapnik (1995); Chang et Lin (2011); Fan et col-lab. (2008). Cet algorithme cherche à tracer un séparateur linéaire entre les exemples de l’ensemble d’entraînement des différentes classes. Un séparateur linéaire est un séparateur ayant une dimension de moins que l’espace des caractéristiques des exemples. Par exemple, un séparateur linéaire est une ligne droite dans le cas où les exemples ont deux dimensions ou caractéristiques. Un séparateur li-néaire est un hyperplan à deux dimensions dans le cas où les exemples ont trois dimensions pour les décrire. Par contre, l’algorithme du SVM tente de tracer le séparateur linéaire dans l’espace du noyau fourni. Comme un noyau est de plus haute dimensionnalité des données, le séparateur devient non-linéaire dans l’espace de base des exemples. On peut voir un exemple de cet effet dans les figures 2.1 et 2.2.
De plus, l’algorithme du SVM cherche à maximiser la marge du séparateur avec les exemples. La notion de marge est une notion importante pour minimiser les risques de surapprentissage. L’algo-rithme cherche à trouver le séparateur linéaire qui divise les deux classes dans l’espace du noyau et qui maximise la marge, soit la distance entre le séparateur et les exemples qui en sont le plus près. Le séparateur se retrouvera donc à une distance égale entre au moins un exemple de chacune des deux classes. Un exemple visuel est présenté dans la figure 2.2. Les exemples qui se retrouvent à la distance minimale du séparateur et qui définissent le séparateur sont appelés les vecteurs de support.
Un avantage que comportent le SVM et les algorithmes utilisant les noyaux est qu’il est possible de choisir différents noyaux plus adaptés au problème étudié, voire d’en mettre au point de nouveaux. Par contre, cet algorithme présente aussi un inconvénient. Alors que, dans le projet présent, les algorithmes plus parcimonieux sont privilégiés, l’algorithme du SVM n’est pas du tout parcimonieux. Le fait d’utiliser un noyau fait qu’il faut considérer toutes les caractéristiques d’un exemple et la classification va en fait dépendre de la comparaison d’un nouvel exemple avec les vecteurs de support. Malgré cet inconvénient, cette méthode est répandue et performante, en plus d’avoir l’avantage d’être flexible. Elle a donc été incluse dans les tests de ce projet.

Machine à couverture d’ensembles

L’algorithme qui a été le plus privilégié pour ce projet est sans doute l’algorithme de la machine à couverture d’ensembles (Set Covering Machine, abbrévié SCM) Marchand et Taylor (2002). La force de cet algorithme et la raison pour laquelle il est privilégié dans ces travaux est qu’il met l’accent sur la parcimonie. Cet algorithme est très parcimonieux au niveau du nombre de caractéristiques des exemples utilisés pour la prédiction, ce qui rend la classification facilement interprétable. Le SCM cherche à classifier les exemples en utilisant des règles simples. L’exemple le plus simple de ces règles est la souche de décision, qui a été utilisée au cours de ce projet avec le SCM. Une souche de décision est une règle où l’on prend une caractéristique d’un exemple et on y applique un seuil. On obtient la forme xi > z où z est une valeur soit observée ou arbitraire. xi dénote la caractéristique i d’un exemple x. Le SCM cherche donc la règle ayant la plus grande utilité sur les exemples de l’ensemble d’entraînement. L’utilité est définie comme le nombre d’exemples négatifs qui sont bien classés moins le nombre d’exemples positifs qui sont mals classés par cette règle, pondérée par un paramètre p qui est déterminé par validation croisée.
Uh = jQhj p jRhj;
Où Uh est l’utilité de la règle h, Qh est le nombre d’exemples négatifs bien classifiés et Rh est le nombre d’exemples positifs mal classés. Lorsque la règle optimale a été trouvée, le SCM va ensuite retirer tous les exemples négatifs qui sont bien classés et les exemples positifs mal classés de l’ensemble d’entraî-nement, avant de faire une autre itération. L’algorithme peut s’arrêter sous deux conditions : soit il n’y a plus d’exemples négatifs à classifier, soit l’algorithme atteint le maximum de règles permises, qui est aussi un paramètre déterminé par validation croisée. Le fait d’avoir un nombre maximal de règles permises est aussi une manière de réguler le surapprentissage.
Finalement, les règles retenues par l’algorithme sont combinées de deux façons possibles. La première façon est par la conjonction, c.-à-d., le prédicteur ainsi produit est le prédicteur booléen consistant en la conjonction de toutes les règles retenues. La seconde façon consiste à produire une disjonction de toutes ces règles. Une disjonction correspond à un ou exclusif en logique. Par exemple, afin de classifier un exemple par un ensemble de règles disjointes, cet exemples doit répondre à une et une seule de ces règles.
L’algorithme du SCM a donc un avantage clair pour le projet décrit ici qui est sa parcimonie et son interprétabilité. La parcimonie du SCM résulte en un très petit nombre de caractéristiques, soit des pics dans un spectre de masse dans notre cas, qui établit un lien prédictif entre les classes. De plus, l’algorithme fournit une organisation logique entre les caractéristiques utilisées par la classification. Effectivement, les deux types d’organisations logiques des règles du SCM fonctionnent très bien dans un contexte biologique. Une conjonction de caractéristiques indique que plusieurs molécules sont nécessaires afin de faire la différence entre les deux classes, ce qui est un cas courant en biologie. Le cas d’une disjonction est aussi très compatible. De trouver un classificateur ayant une disjonction entre deux pics par exemple pourrait indiquer que deux voies métaboliques distinctes sont impliquées dans la différence entre les classes.

Arbres de décision

Un autre algorithme utilisé dans ce projet est l’algorithme des arbres de décision (decision trees) Breiman et collab. (1983). Plus précisément, les arbres de classification sont utilisés ici. L’algorithme d’apprentissage par arbre de décision fonctionne en séparant les données par une série de règles du même type que celles utilisées pour le SCM. On peut en fait voir les souches de décisions, mentionnées dans le cadre de l’algorithme du SCM, comme des arbres de décision avec une seule règle, soit une profondeur de 1. Un exemple d’un de ces arbres est présenté à la figure 2.3. L’algorithme des arbres de décision va ainsi faire un arbre de la forme suivante. On commence à la racine de l’arbre. On a une première décision basée sur une caractéristique des exemples, de la forme xi > z. Selon le résultat de la comparaison, on suit l’arc correspondant dans l’arbre. On peut ensuite arriver à un nouveau noeud. Si c’est le cas, on répète le processus avec la règle encodée dans ce noeud. Si l’on arrive à une feuille, c.-à-d. un noeud terminal sans arc sortant, cette feuille indique dans quelle classe est l’exemple considéré.
Comme tous les autres algorithmes, il y a un risque de surapprentissage avec cet algorithme. On peut facilement former un arbre avec trop de noeuds, trop profond et qui ne généralisera pas à d’autres exemples. Pour pallier ce problème, on utilise la validation croisée pour déterminer les meilleurs para-mètres pour l’algorithme. Les paramètres disponibles dans l’implémentation de cet algorithme qui fut utilisé sont la profondeur maximale de l’arbre et le nombre d’exemples minimum à séparer par noeud Pedregosa et collab. (2011). On utilise donc la validation croisée afin de trouver une combinaison de ces paramètres qui sera performante sur l’ensemble d’entraînement et sera capable de généraliser.
De manière semblable au SCM, on peut voir l’arbre de décision comme un mélange plus complexe de disjonctions et conjonctions de règles. L’algorithme des arbres de décision est aussi un algorithme avantageux pour le projet étant donné qu’il est aussi très parcimonieux et interprétable, surtout com-paré aux méthodes à noyaux ou aux réseaux de neurones. L’arbre de décision a par contre tendance à être moins parcimonieux que le SCM. De plus, sa capacité à organiser les règles de décision de manière plus complexe peut l’aider dans certains cas ou rendre le classificateur moins interprétable.

Forêt d’arbres décisionnels

Un dernier algorithme d’apprentissage utilisé au courant de ce projet est celui des forêts d’arbres déci-sionnels, parfois appelés forêts d’arbres aléatoires, ou random forest Breiman (2001). Cet algorithme fait partie de la classe d’algorithmes d’apprentissage que l’on nomme les méthodes d’ensemble. Les méthodes d’ensemble sont des méthodes qui tentent d’obtenir une meilleure performance en prédic-tion en utilisant un vote de majorité de plusieurs autres algorithmes. Dans le cas des forêts d’arbres décisionnels, un vote de majorité est fait sur un ensemble d’arbres de décisions.
L’algorithme génère un nombre d’arbres de décisions. Les arbres sont générés sur un sous-ensemble d’exemples, tirés par méthode bootstrap, c’est-à-dire en pigeant aléatoirement des exemples avec remise, dans l’ensemble d’entraînement. Ensuite, au moment de calculer les règles à chaque noeud, l’algorithme va prendre un sous-ensemble aléatoire des caractéristiques des exemples et l’utiliser pour choisir la règle. On entraîne ainsi un nombre d’estimateurs spécifié. Pour faire une prédiction, on montre l’exemple à classifier à chacun des arbres estimateurs, qui vont chacun prédire une classe. On fait ensuite un vote de majorité de ces classificateurs avec un poids uniforme, c’est-à-dire que chacun des votants a un poids équivalent aux autres.
Les forêts d’arbres décisionnels sont utilisées dans ce projet pour les raisons suivantes. Une première est que c’est un algorithme populaire et généralement performant. Il est aussi très rapide à entraîner. Cet algorithme a aussi une tendance assez faible à surapprendre et son design est fait pour diminuer le surapprentissage des arbres le composant. Un inconvénient par rapport aux arbres de décision et au SCM est que cet algorithme n’est pas très parcimonieux et n’est pas du tout interprétable.

Le noyau à boîtes chevauchantes pour l’algorithme du SVM

Motivation et preuve de noyau

Au cours du projet, l’idée d’un nouveau noyau adapté aux défis du travail avec des données de spectro-mètre de masse est revenue à plusieurs reprises. Finalement, une idée s’est imposée. Elle est inspirée d’une méthode déjà existante en traitement de données de spectrométrie de masse. Cette technique se nomme le binning. Simplement, cette méthode consiste à compenser pour le désalignement des pics de plusieurs spectres en regroupant plusieurs pics dans une distance spécifiée en un seul, que l’on nomme un bin, ou une boîte. Un exemple est présenté à la figure 2.4. Une manière simple de l’implé-menter est d’arrondir d’une ou deux décimales les masses en uma mesurées par un spectromètre et de sommer les pics qui se retrouvent à la même masse.
Certains problèmes sont présents dans cette méthode. Un premier est la possibilité qu’un pic homo-logue entre deux spectres se retrouve dans des bins différents. En reprenant l’exemple du paragraphe précédent, on peut imaginer un pic x1 de masse 201.1234 Da qui ait une déviation dans un autre spectre x2 avec une masse de 201.1239 Da. Le fait d’arrondir pourrait amener la masse de x1 à 201.123 Da et celle de x2 à 201.124 Da. Un autre problème avec l’approche par arrondissement est que les variances aléatoires d’un spectre sont relatives à la masse et donc on aura une déviation plus grande avec de plus grandes masses. Cet inconvénient peut être pallié si l’on imagine les bins comme étant d’une taille fixe en ppm, mais il restera tout de même le fait que des pics peuvent se retrouver d’un bord et de l’autre de la frontière entre deux bins.
C’est donc dans cette optique que nous avons eu l’idée de mettre au point un nouveau noyau pour l’algorithme du SVM basé sur l’idée des bins. Pour régler le problème des pics sur la frontière entre les bins, un nouveau paramètre de chevauchement a été introduit. Dans ce noyau, on représente donc un spectre par une série de boîtes d’une taille constante en ppm, donc dont la taille va augmenter à travers le spectre lorsque la masse augmente, et qui se chevauchent partiellement. Un exemple de cette représentation est montré à la figure 2.5.
Afin d’être utilisable avec les méthodes à noyau tel que l’algorithme du SVM, il faut faire la preuve que le nouveau noyau, baptisé le noyau à boîtes chevauchantes (Overlapping Bin Kernel, abbrévié OBK), est effectivement un noyau. La caractéristique principale des noyaux est présentée à l’équation 2.1. Dans le cas de l’OBK, la preuve est simple. Avec les paramètres de taille de bin et de chevauchement, on peut décrire explicitement le vecteur de caractéristique dans le noyau, puisqu’on connaît le point de départ (la masse la plus petite que l’on a acquise dans l’ensemble des spectres), la taille de chaque boîte et le chevauchement entre chaque boîte. Ainsi, si l’on sait exactement la forme du vecteur f (x) pour tout x et donc que f (x0) aura la même forme pour tout x0, il s’ensuit directement que pour k(x; x0) = f (x) f (x0), la mesure de similarité k est donc bien une fonction noyau (c.-à-d., une fonction représentant un produit scalaire dans l’espace vectoriel des caractéristiques). Il peut donc être utilisé par l’algorithme du SVM.
Il est à noter qu’une conséquence de l’utilisation de ce noyau est qu’il n’est plus nécessaire d’appliquer l’algorithme d’alignement décrit au chapitre précédent. Il est aussi théoriquement possible que ce noyau rende redondante l’application de masses de verrouillages, réelles ou virtuelles. Par contre, il faut utiliser des tailles de boîtes beaucoup plus grandes afin de compenser pour les déviations corrigées par masses de verrouillage. Cela entraîne un risque que la taille de boîte soit trop grande et plus assez spécifique pour servir de bonne fonction de comparaison. En général, la taille des boîtes et le chevauchement seront des hyperparamètres qui seront choisis par validation croisée afin d’éviter un surapprentissage.
Il est aussi à noter que, malgré que le fait que les objectifs de ce projet favorisent l’application d’al-gorithmes parcimonieux et dont le modèle est interprétable, cette méthode est utilisée en conjonction avec l’algorithme du SVM et n’est donc pas du tout parcimonieuse ou interprétable. Par contre, l’ob-jectif plus général du projet est de classifier des échantillons de produits sanguins selon leur spectre de masse. Il semble alors qu’il ne faut pas laisser passer une opportunité de mettre au point une nouvelle méthode adaptée aux données et donc prometteuse pour la classification, même si elle ne répond pas à toutes les caractéristiques privilégiées.

Présentation de l’algorithme

De premiers tests ont été pratiqués avec une première version très directe et peu optimisée de l’al-gorithme, afin de vérifier si l’approche avait un bon potentiel. L’algorithme 6 présente une partie commune à la première implémentation et aux versions subséquentes, c’est-à-dire la construction de la matrice de Gram entre les différents exemples. Cette matrice est la matrice de comparaison entre les échantillons, nécessaire et utilisée par l’algorithme du SVM.
Algorithm 6 Construction de la matrice de Gram
Require: Un ensemble de m spectres
Créer une matrice de taille m m, la matrice de Gram for i = 0 to m do
for j = i to m do
Comparer le spectre i et le spectre j avec le noyau à boîtes chevauchantes Stocker la valeur de noyau retournée aux indices [i, j] et [ j,i]
end for
end for
return La matrice de Gram
La méthode de construction de matrices de Gram présentée à l’algorithme 6 est standard. Il faut construire une matrice de comparaison entre toutes les paires d’exemples, où chaque exemple est un spectre. On construit donc un tableau de taille m m pour stocker les valeurs du noyau lorsqu’on a m spectres. On parcourt ensuite les exemples, en faisant toutes les comparaisons. Notez qu’Algo-rithme 6 est sous-optimal, le fait de faire toutes les comparaisons n’est pas la meilleure façon de calculer le noyau OBK. Nous allons d’abord proposer une façon légèrement plus efficace (et surtout mieux détaillée) de faire ce calcul (Algorithme 7) que nous améliorerons à la sous-section suivante. En fait, pour accélérer la méthode, on ne calcule que les valeurs pour la moitié supérieure du tableau, puisque la comparaison entre un exemple x et y sera la même qu’entre y et x. Cela permet d’accélérer cette étape d’un facteur près de deux. L’algorithme 7 va donc présenter la première implémentation du noyau.
Algorithm 7 Première implémentation du noyau à boîtes chevauchantes
Require: Deux spectres, s1 et s2
Require: Un paramètre de taille de boîtes, en ppm, s
Require: Un paramètre de chevauchement, w
Require: Une masse de départ et une masse finale, md et m f
La masse de départ est déterminée par la masse minimale de l’acquisition des spectres. La masse finale doit être déterminée sur l’ensemble des spectres utilisés. Il nous faut donc la masse de plus grande taille observée dans tous les spectres.
for i = 1 to 2 do
Créer un vecteur contenant les valeurs de boîtes vi
Trouver les pics de si dans la boîte b1 = [md ; md + md s] et ajouter la somme de leurs intensités au vecteur vi
while m f 2= b j do
b j = [m j; m j + m j s] où m j = mi 1 + (mi 1 s) w
Trouver les pics de si dont la masse est dans la boîte b j et ajouter la somme de leurs intensités
au vecteur vi
end while
end for . On a à ce point les vecteurs des valeurs des boîtes des deux spectres
. La valeur à tout indice donné j dans chacune de ces listes équivaut à la même boîte dans les deux spectres.
return v1 v2
Décrivons ici l’algorithme 7 en plus de détail. Une première spécification à apporter est au niveau des masses de départ et de fin des boîtes. Il faut que, dans toutes les comparaisons de spectres, on ait exactement les mêmes boîtes définies. Étant donné que les boîtes correspondent aux éléments du vecteur f (x), il nous faut absolument que tous les f soient identiques au niveau de leur composition. Si l’on définissait les boîtes selon les plus petites masses et plus grandes masses observées dans les deux exemples d’une comparaison, on aurait des vecteurs différents à chaque comparaison et donc nous n’aurions pas un noyau.
Ensuite, on crée la première boîte et l’on somme tout pic se trouvant dans cette boîte. Si aucun ne s’y trouve, on confère une valeur de 0 à cette boîte. On cherche les pics selon une recherche binaire où les bornes sont les masses limites de la boîte. Cela fonctionne puisque nous gardons la liste des pics ordonnée par leurs masses. De plus, la recherche binaire s’opère de manière efficace, avec un pire cas de O(log n) où n est le nombre de pics dans le spectre. Une fois le contenu de la boîte sommé, on stocke cette somme en mémoire.
Après qu’on ait terminé la première boîte, on avance à la prochaine. On peut calculer la masse de départ de la nouvelle boîte à partir de la taille et du chevauchement. On répète alors la même procédure qu’à la première boîte à cette nouvelle boîte et toutes les boîtes subséquentes. Le critère d’arrêt est que l’on atteigne une boîte qui inclut dans sa fenêtre la masse finale générale aux exemples.
Lorsque ce procédé a été fait sur les deux spectres à comparer, on fait le produit scalaire entre les deux vecteurs de caractéristiques. On itère sur chacune des caractéristiques des vecteurs et on multiplie chacune des boîtes homologues ensemble avant de sommer tous les résultats. On a ainsi le produit scalaire entre les vecteurs. Ce produit est la mesure de similarité entre les deux spectres.
Cette implémentation contient plusieurs inconvénients. Le premier est d’ailleurs que l’on explicite le vecteur f des exemples en mémoire. Cela requiert une grande quantité de mémoire vive et de temps de calcul afin d’ajouter des éléments et en temps d’accès. De plus, la complexité de l’algorithme dépend fortement, dans cette implémentation, du nombre de boîtes nécessaire pour couvrir les spectres, donc essentiellement des paramètres de taille et de chevauchement. Un autre problème de cette implémen-tation est qu’il faut constamment aller chercher les pics dans le spectre. Même avec un algorithme de recherche efficace tel que la recherche binaire, une recherche est nécessaire pour chaque boîte. Plusieurs seront d’ailleurs inutile si aucun pic ne se trouve dans la boîte cible.

Table des matières

Introduction 
0.1 Spectrométrie de masse et métabolomique
0.2 Apprentissage automatique
0.3 Contexte des travaux et hypothèses
1 Méthodes de traitement des données de spectrométrie de masse 
1.1 Introduction
1.2 Alignement des pics
1.3 Correction des déviations par masse de verrouillage virtuelles
1.4 Amélioration des algorithmes
1.5 Conclusion
2 Application de l’apprentissage automatique 
2.1 Introduction
2.2 Le noyau à boîtes chevauchantes pour l’algorithme du SVM
2.3 Application d’algorithmes existants à la spectrométrie de masse
2.4 Conclusion
Conclusion 
A Annexe
A.1 Données supplémentaires au chapitre 1
Bibliographie

Télécharger le rapport complet