Question : quel est le meilleur type de données dans mysql pour stocker un vecteur colonne de dim 2500?
 
L'idée derrière ça est de pouvoir faire faire par mysql du calcul (si c'est possible) dans le contexte de l'implémentation d'une LSI, cf mon autre topic qui n'a pas un franc succès http://forum.hardware.fr/hfr/Progr [...] 8058_1.htm peut-être par ce que le titre n'inspire pas grand monde. C'est pourquoi je vais découper ma grosse question sur la LSI en questions plus petites comme celle de ce topic.

C'est quoi "un vecteur colonne" ? Un tableau à une dimension ?
 
Si c'est le cas, vu qu'il contient 2500 éléments, pour moi il faut impérativement passer par une sous-table.
 
Tu peux tenter la sérialisation binaire de ton objet dans un BLOB, mais MySQL ne saura pas l'utiliser pour faire des calculs.

oui, un vecteur colonne, c'est une matrice n lignes par 1 colonne.
Je ne sais aps si t'as jeté un oeil au sujet que j'ai lié, mais j'ai une table de documents (leur fiche avec certaines méta-données) et à chaque document, je veux lui associer un vecteur colonne.
Le but est de pouvoir faire des requête du genre "trouves moi tous les docs dont le cosinus entre leur vecteur colonne et celui du doc fourni en entrée est >= à un seuil donné (ex : 0.90)".

Je me dis que pour le coup, j'aurais peut-être intérêt à faire une table qui contiendrait tous les cosinus précalculés entre 2 docs. Dans la mesure où ces cosinus ne vont pas changer...

J'ai regardé un peu ton topic, mais je pige rien
 
Tu fais un index server ? C'est quoi ces histoires de comparer les cosinus de deux documents ?
 
Sinon, entre table des vecteurs ou donnée sérialisée, la question qui se pose repose principalement sur ces deux questions :
Qui va faire les calculs ?
- Si c'est le SGBD, alors pas de question à se poser : une table
- Si c'est l'application consommatrice, alors point de vue performances d'un BLOB contenant la matrice sérialisée sera bien plus performant (d'autant qu'il semblerait que tu bosses en C++, donc la sérialisaion d'une matrice est plutôt aisée car ne demande pas de traîtement particulier : lecture/écriture en binaire directement en mémoire)
Ces calculs risquent-ils d'être fais dans plusieurs applications ?
- Si seule une application a besoin de l'information, alors les données sérialisées ne poseront pas de problème, dans la mesure où tu n'as pas de problème de portabilité
- Si plusieurs applications risquent d'avoir besoin de l'info, donc potentiellement plusieurs langages différents, alors la sérialisation va poser le problème de la portabilité (type de base ? représentation des nombres en mémoire ? etc.)

La théorie est pas très compliquée.
Etape 1 : on extrait un certain nombre de mots pertinents de documents à indexer et on compte leurs occurrences dans chaque doc. Le résultat est une matrice (on va l'appeler A)où les lignes représentent les termes (mots lemmenisés, c'est-à-dire sous leur forme la plus simple afin de bine compter toutes les occurrence d'un même mot, ex : aime, aimerons, aimeraient, aima, aimée, aimées représentent le même concept d'un point de vue sémantique -> le verbe aimer, son lemme est "aim" ) et les colonne le docs.
Etape 2 : on applique le tf-idf sur les nb d'occurrences trouvés ( http://en.wikipedia.org/wiki/Tf-idf ) histoire de lisser un peu ces nbs.
Etape 3 : on calcule A'*A = X ce qui nous donne une matrice carrée de taille plus petite que celle initiale puisqu'en général, y'a beaucoup plus de termes que de docs.
Etape 4 : on calcule la SVD (valeurs et vecteurs propres) de X (bonjour le temps de calcul pour une matrice de 2500*2500, surtout en php )
Etape 5 : on garde que les premiers valeurs/vecteurs propres les plus importants et on va calculer la transformée de X par Y = Uk*Sigmak*Vk' où k représente les k premiers vecteurs propres. Ainsi, chaque colonne de la nouvelle matrice Y va correspondre à un doc (son vecteur colonne).
 
Le but de la LSI est de permettre une indexation "sémantique" des documents. Ainsi, lorsqu'un utilisateur saisit une requête (avec des mots), cette requête est considérée comme un document et va subir la même transformation Uk*Sigmak*Vk' ce qui va donner un vecteur colonne. Pour savoir quels sont les documents qui se rapprochent le plus de la requête utilisateur, il suffit de calculer le cosinus entre ce vecteur colonne et celui de chaque document dans la bd et de ne remonter que ceux qui sont > à un seuil (> 0.80 par ex). En effet, cos(0) = 1 donc les 2 vecteurs sont identiques.
 
C'est plus clair?
 
Par contre, pour l'instant, je suis parti dans du tout php/mysql.

Pour répondre à test questions maintenant :
- y'a qu'1 appli (intranet en php) qui va utiliser cette base
- j'aurais bien aimé déléguer le calcul au sgbd mais je vois pas du tout comment faire faire du calcul matriciel à Mysql avec des données contenues dans une table Tu la verrais comme la table?
- pour la sérialisation, un blob oui et j'utilise la fonction serialize() de php Dans ce cal là, c'est php qui va mouliner.
 
Tu connaîtrais pas par hasard un .exe pour Linux/Windows qui fasse du calcul matriciel et fonctionnant en ligne de commande?

Moi et les math, on a divorcé en 2nde Je te raconte pas la dèch pour avoir un Bac Scientifique et faire des études d'info avec une moyenne de 4 en maths
 
Donc ne me parle pas de calculs de matrices, me souvient avoir été réveillé par un avion qui a passé le mur du son au dessus de la fac en plein court de math. Le prof expliquait un truc à propos de multiplication de matrices ou je sais pas quoi. Je me suis empressé de me rendormir
 
Par contre, choses sûres :
1/ Généralement, les SGBD disposent de quelques fonctions de calculs. Mais souvent très limitée. Tu n'auras donc pour ainsi dire aucune chance de pouvoir faire de genre de calculs directement dans une requête SQL en bénéficiant de fonctions internes
2/ Il faudra donc passer par du PL/SQL. Il s'agit d'un langage procédurale supporté par différents SGBD (PL/SQL c'est pour Oracle, T-SQL c'est pour SQL Server, PG/SQL c'est pour PostGreSQL, pour MySQL je sais pas comment ça s'appelle, mais ça existe depuis la version 5.1 au moins). Le souci de ce langage, c'est que même s'il est "compilé", il est très loin d'arriver à la cheville d'une fonction native en terme de performances.
3/ Grossomodo les mêmes soucis en PHP
4/ A mon avis, t'es bon pour écrire une lib en C, Java ou autre, et l'appeler depuis ton code PHP si t'as besoin d'un temps de réponse correct.
 
Sinon, poste la tronche d'une de tes fonctions de calcul de matrice (un truc simple si possible) histoire que je me fasse une idée de tes besoins.
 
De base, je dirais 3 colonnes :
- document_id   (identifiant du document)
- number_indice (position dans la matrice)
- value             (valeur du nombre)
 
M'enfin tu me fait peur à vouloir faire ce genre de calculs en PHP ou en SQL
Tu peux toujours tenter de faire un bench mais bon... Pas convaincu quant aux temps de réponse.
 
 
PS : Pourquoi tu n'utilises pas un service d'indexation pré-existant ? MySQL par exemple sait parfaitement indexer des documents de la façon que tu décris, avec des algo certainement bien plus évolués. Sous Windows tu as aussi Index Server (ne nécessite pas de base de données, présent d'office sous Windows) et les Indexing Services de SQL Server (présents sur la version 2005 Express SP1).

t'as des SGBD genre postgres qui ont un type array[]

ouais. mais le souci c'est que niveau portabilité c'est moyen.
après tout dépend si l'appli doit effectivement être aisément portable ou non...
 
idem pour l'hébergement : mysql + php, les yeux fermés tu trouves des hébergeurs à plus savoir qu'en fait qui proposent ça. postresql c'est moins évident.
 
ceci dit, vu que je recommande l'utilisation d'une lib externe écrite dans un autre langage pour faire les calculs, effectivement le souci de l'hébergement se posera, donc après...
 
 
(ah pis j'y pense... le connecteur php supporte le type array[] ? oledb aussi ? parceque mine de rien c'est un problème qui peut se poser assez rapidement )

Je vais reprendre ma réponse que j'avais fait à flo850.

 
Vous voyez la différence?
 
La LSI a aussi d'autres applications, comme trouver un synonyme d'un mot (pas à tous les coup mais pour un algo complètement automatique, c'est pas mal).
Ex tiré d'une étude sur LSI. Pour l'exam du Toefl, il y a environ 80 questions sur des synonymes : on donne un mot et faut trouver parmi une liste de 4 ou 5 mots celui qui a le sens le plus proche. Avec un algo classique reposant sur des mots-clés, celui-ci obtient un score d'environ 35%. Le score moyen des élèves qui passent ce genre d'exam est d'environ 64%. En appliquant une LSI en prenant comme base documentaire une encyclopédie (en anglais bien entendu), l'algo obtient un score aux environs de 64%!
 
Voici l'étude en question (cf p.21-22) : http://lsirwww.epfl.ch/courses/dis [...] 94-270.pdf

 
t'enflammes pas, c'est pas pour un site perso, c'est pour un intranet dans une boîte avec php4/mysql 3.23.x (mais je peux passer à php5/mysql 5) et j'ai une bonne latitude pour les libs/softs qu'il faut installer sur le serveur (il est dédié à mon intranet + 2 autres de mes applis aussi en php).  

Je comprends pas tas question. Tu veux que je pose le code source en PHP qui permet de calculer une SVD? Ca prend plusieurs centaines de lignes! Voici un lien sur la lib que j'utilise : http://www.phpmath.com/build02/JAMA/docs/download.php  
Faut regarder le fichier SingularValueDecomposition.php. Ca, c'est ce qui permet de calculer ma SVD. Par contre, si c'est pour l'exploitation de la SVD, c'est un bête calcul d'angle que font 2 vecteurs de dimension n (ici, n=2500 et non pas 2 ou 3 comme en 1ère S ou terminale ).
 

Tu n'y es pas. Un document est une COLONNE de ma matrice SVD (cf vecteur colonne), pas une simple valeur. C'est bien là mon pb pour modéliser dans une bd.
 

J'ai déjà lancé un bench sur un GX260 (dell) : 2.6Go et boosté à 1Go de Ram : pour une matrice de 500x500, faut 20 mins, mais pour du 2500x2500 faut environ 2j (estimé par qq autres tests et une regression en x^3, c'est ce bench que je suis en train de vérifier en ce moment même)!  

Non pas tout ça. Juste savoir quand tu fais les calculs comment tu isoles les nombres à utiliser (genre "je match le nombre d'indice I de ma matrice M1 avec le nombre d'indice J de ma matrice M2", si I = J ou I <> J ça peut poser des problèmes).
 

Fait abstraction de l'algo et des calculs.
J'ai du mal à piger comment ton document est une colonne de ta matrice, si ta matrice n'a qu'une seule colonne
 
On est bien d'accord que "à 1 document correspond 1 matrice d'une colonne" ?
 
Donc si c'est le cas, la structure que j'ai donné est bonne : t'as une table "document", avec un identifiant, et un champ text par exemple, qui contient le corps du document.
Et une seconde table "matrice" dont l'identifiant est le tuple (doc_id, indice) avec doc_id une clé étrangère pointant sur l'identifiant de la table document, et indice le numéro d'indice du nombre dans ta matrice.
 
Après, via une requête très simple, tu peux récupérer les données des matrices de tes documents très facilement.
 

Euh... Bah si c'est du one shot et qu'après tu touches plus jamais à tes documents c'est pas gênant. Si tu rajoutes/modifies des documents régulièrement, ça va pas le faire
D'autant que j'imagine que le même traîtement en C demande quelques minutes.
Dans tous les cas, ne demande pas au SGBD de faire ce traîtement, tu va le foutre à genoux

Ouais mais PostGreSQL, c'est pas MySQL
Donc ça t'oblige à avoir deux SGBD sur le même serveur (pas terrible niveau performances et montée en charge) ou un serveur dédié.

Je récapitule pour qu'on parle bien tous de la même chose.
Au départ, j'ai une matrice de m termes (mots) par n documents. Je bidouille cette matrice puis j'applique une SVD. Cette SVD me donne 4 "choses" :
- les valeurs propres
- les vecteurs propres à gauche (matrice carrée U  de n*n)
- la matrice des valeurs propres (matrice diagonale Sigma de n*n)
- les vecteurs propres à droite (matrice carrée V de n*n)
Tout ça, je vais le stocker dans un fichier txt à priori (cf http://forum.hardware.fr/hfr/Progr [...] m#t1612927 )
 
Pour chaque doc, je vais calculer son vecteur colonne (dim n*1 donc) via une formule donnée ici : http://en.wikipedia.org/wiki/Latent_semantic_analysis (fin du § Derivation). Ca, faut que je le stocke dans ma bd et donc, que je trouve un bon "format", une bonne structure pour pouvoir ensuite calculer le degré de proximité entre mes documents dans ma bd et ma requête, transformée elle aussi en vecteur colonne.
Ce calcul de proximité se fait sur la base de l'angle que font un vecteur colonne d'un doc et le vecteur colonne de ma requête utilisateur, c'est à dire le cosinus, grâce au produit scalaire, comme le montre cet article : http://fr.wikipedia.org/wiki/Produit_scalaire
Rappel : si V1 et V2 sont 2 vecteurs de même dimension et . représente le produit scalaire et |V1| = norme de V1 alors
V1.V2 = |V1|*|V2|*Cos(a) ou a est l'angle entre V1 et V2
Par cette formule, on peut calculer facilement Cos(a)
 
C'est plus clair comme ça?
 
De ce fait, je ne comprends pas ce que tu entends par "indice le numéro d'indice du nombre dans ta matrice"... Par contre, oui, on est bien d'accord que "à 1 document correspond 1 matrice d'une colonne" ? => ta matrice à n lignes mais 1 colonne => vecteur colonne
 
Et je ne compte pas passer à postgres.
 
ps : je ne stocke pas le contenu du doc dans ma bd, mais juste le lien pointant sur le fichier associé

 
C'est jamais qu'un calcul de produit scalaire. C'est pas très violent. Mon pb est plutôt comment stocker mes vecteurs colonnes pour pouvoir calculer ce produit scalaire
 
C'est pour ça que je me demandais si ça valait pas le coup de calculer une fois pour toute les cos(a) de tous les docs 2 à 2.
 
Sinon, pour info, mes docs ne changent pas puisqu'ils sont enregistrés dans ma BD qu'une fois qu'ils sont prêt à être diffusés (GED).

Le prend pas mal, mais... Non. Rien pigé à partir du moment où t'as commencé à parler de "matrice de termes (mots)".
 
Je te dis, fait abstraction de l'algo et des traîtements.
 
Un SGBD ça stock des données, donc moi je parle en type de base.
C'est quoi cette matrice, elle contient quoi ?
En quoi elle concerne MySQL si c'est les 4 autres trucs que tu stockes ?
Et ces 4 trucs en question, c'est quoi "au juste" (une série de nombres ? d'autre chose ? qui sont rattachés à quoi et comment ?)
 

Exemple simple.
 
Le document c:\mes documents\toto.txt a une matrice {1;12;3}
 
Moi je suggère :
Table DOCUMENT
ID
PATH
 
Table MATRICE
DOC_ID
INDICE
VALUE
 
Donc dans "document", tu vas te retrover avec une ligne :
ID  PATH
1  c:\mes documents\toto.txt
 
(logique quoi...)
 
Ensuite, dans ta table matrice...
Une matrice, vu que c'est un tableau, en C par exemple tu aurais un truc du genre :
tab[0] = 1;
tab[1] = 12;
tab[2] = 3;
 
l'indice c'est... ben l'indice quoi... le truc entre []
 
Donc dans ta table MATRICE t'as :
DOC_ID INCIDE VALUE
1      0      1
1      1      12
1      2      3
 
C'est plus clair comme ça ?
 
Ainsi, quand tu cherches la matrice d'un document :
 
select m.value
from document d
inner join matrice m on m.doc_id = d.id
where d.path = 'c:\mes documents\toto.txt'
order by m.indice
 
=> Ca te retourne les nombres de ta matrice sous forme de lignes triées comme au départ dans ton code.
 
Après, en SQL, tu pourras effectivement faire un certain nombre de traîtements en amont de ton programme, mais pour ça il fait éclater tes notions de transformations matricielles en langage que je comprends si tu veux un coup de main, parceque tu peux me parler de "valeurs propres", moi je sais pas ce que c'est
 

Oui, donc le coup du type array[] suggéré par Taz (parfait pour stocker une matrice) n'est pas possible dans ton cas.
 

Ouais, mais ça change rien ça de toute façon
 
PS : tu m'as toujours pas répondu : pourquoi tu utilises pas un service d'indexation "tout fait" ?

Mmmm, chais plus ce que c'est un produit scalaire (bah ouais, quand tu pionces en cours et que 10 ans après tu t'en es toujours pas servit, c'est dur de mémoriser )
 
A priori, je dirais "vivi c'est pas compliqué" mais bon... Un SGBD il te fait un produit cartésien les yeux fermé, mais sorti de ça...
En gros, un SGBD, ça fait de l'algèbre, oui, mais de l'algèbre ensembliste. Donc les calculs d'algèbre... je sais plus le nom, y sait pas faire (du moins, il est pas prévu pour, donc faut lui expliquer gentillement)

Ca veut donc dire (pour simplifier) que ton doc toto.txt a 1 occurrence du mot1, 12 occurrences du mot2 et 3 du mot3.
 
Pour mieux comprendre mon histoire de matrice termes*docs, regarde le § "Application aux langues naturelles" de cet article : http://fr.wikipedia.org/wiki/D%C3% [...] i%C3%A8res
 
ps : tu verras aussi qu'une SVD peut servir dans la reconnaissance de formes et la compression
 

Oui, effectivement, c'est plus clair et ca devrait me permettre de faire assez facilement le calcul du produit scalaire X.Y = x1*y1 + x2*y2 +...+xn*yn où x et y représentent respectivement les coordonnées des vecteurs X et Y dans un espace à n dimensions => X {x1,x2...,xn} et Y{y1,y2,...,yn}
De ce fait, dans cette table, je vais avoir 2500 doc * 2500 coordonnées => 6 250 000 enregistrements et à chaque fois que je rajoute 1 doc, ça me rajoute 2500 lignes dans cette table. La procédure d'ajout risque pas de trop ramer?
 

Parce qu'un service d'indexation repose uniquement sur des mots-clés et pas sur l'aspect sémantique des mots d'un document et des relations qui existent entre eux. On est en plein dans le domaine de la linguistique là.

6 millions de lignes, évidement ça va pas se faire en 5 minutes
 
mais bon, mysql est réputé extrêment performant pour ce genre de choses, donc je suis confiant. à mon avis l'insertion des lignes sera insignifiante par rapport à la durée des calculs (je suis resté bloqué sur tes deux jours ) au pire 6 millions de lignes c'est 1 heure pour les ajouter dans access

La phase de calcul de la SVD qui dure 2j et celle du calcul vecteurs associés aux docs puis leur insertion dans la bd ne se feront qu'une fois pour toute.
La SVD, je peux la lancer sur un autre serveur, c'est pas un pb. Le calcul des vecteurs associés aux docs aussi. Y'a juste leur insertion dans la bd de prod : ça, je peux lancer cette opération par le cron le soir. Au matin, ça devrait être ok.
 
Mon interrogation porte juste sur le temps qu'il faut pour insérer 2500 lignes dans une table à chaque fois que j'insère un nouveau doc.
 
Pour info, y'a pas de suppression (où très rarement).
 
Extrait du fichier pdf de l'étude citée précédemment :

 
Tu vois, c'est normal qu'une svd prenne beaucoup de temps. Moi, j'ai pas 10 stations SUN SPARCstation à ma disposition    J'ai qu'un PIV 2.6 Ghz
Et eux, ils se posent pas la question : fichiers texte de 3 Go

Ben inserrer 2500 lignes, ça va prendre plusieurs secondes, voir quelques minutes.
Si c'est un traîtement non ponctuel, ça va évidement être ennuyeux pour l'utilisateur.
 
Ensuite, générer des fichiers PHP qui contienent ces infos, ça va certainement prendre plus de temps (donc faut relativiser )
 
Pour ce qui est de l'écriture direct au format binaire dans un fichier, par contre, c'est ce qui sera le plus rapide, dans tous les cas.

Ben les fichiers php, je peux les générer sur un autre serveur, c'est pas gênant. Y'aurait plus qu'à les lire de temps en temps quand un nouveau doc est inséré dans la bd ou qu'en un utilisateur lancerait une recherche.

J'avais pas vu cette discussion moi. (je comprend mieux pourquoi MagicBuzz parlais de doc dans l'autre discussion )
Avec php, si t'insères 2500 lignes en 2500 requêtes, il te faudra peut être plusieurs minutes sur un vieux PC. Si t'insères 2500 lignes de trois colonnes numériques en une requête, ça sera fait en quelques seconde.  
 
Pour te donner une idée de la vitesse, pour remplir une table de type inodb, j'ai déjà créé plus de 16.5 millions de lignes en 20 minutes soit presque 14 milles lignes par seconde sur un athlon 1 ghz alors que mysql n'était pas le seul à pomper des ressources.