Algorithme tableau creux => tableau plein

Version imprimable

30/03/2011, 09h37
tbagwell

Algorithme tableau creux => tableau plein

Bonjour,

Je ne sais pas si je suis dans la bonne rubrique mais je vous expose tout de même mon problème.

J'ai un tableau où il y x individus et y variables, et ce tableau est creux, ie il y a beaucoup de cases vides.
Je cherche à obtenir à partir de ce tableau, un tableau plein de taille x'<x et y'<y, qui soit le plus grand possible.
L'algorithme doit donc permettre de supprimer certaines lignes et certaines colonnes de manière à obtenir un tableau plein de taille maximale.

Si quelqu'un à une idée de comment faire, ça m'aiderai énormément.

Merci.
30/03/2011, 12h53
Franck Dernoncourt

Peux-tu donner un exemple stp ? Car si le tableau transformé ne doit contenir aucune case vide, alors il n'y a aucune garantie qu'on puisse en faire un : cela nécessite d'avoir pour hypothèse que le nombre de cases creuses est le même sur chaque ligne et chaque colonne.

De même, je vois pas ce que tu entends par "le plus grand possible".

Egalement, comment avoir l'assurance que x'<x et y'<y ? On peut très bien avoir x'<x et y'==y non ?

J'ai aussi quelques autres questions, mais c'est plus simple que tu donnes un exemple je pense :)
30/03/2011, 13h56
tbagwell

Oui pour la taille du tableau à obtenir on peut prendre des bornes plus larges x'<=x et y'<=y.

Ce que j'entends par "le plus grand possible", c'est maximiser la taille x'y' avec éventuellement comme contraintes:
- un nombre minimal d'individus
- un nombre minimal de variables

Exemple, avec NA=case vide:
http://img42.imageshack.us/img42/6473/tabtut.jpg

Idéalement par la suite il faudrait un paramètre d=%de cases vides autorisées. Cela sera un paramètre pour l'algorithme. (en pratique d<5%)
Pour d=0 => tableau plein.

J'ai besoin de construire cet algo, car par la suite je vais devoir appliquer des méthodes statistiques, qui soit fonctionnent uniquement que lorsqu'il n'y aucune valeur manquante, soit peuvent être utilisées mais avec un nombre restreint de valeurs manquantes
30/03/2011, 15h37
Nebulix

Ce que tu viens de faire :
- renoncer à étudier v4 car elle a trop de cases vides
- renoncer aux individus à qui il reste une case vide
tu peux adapter le trop et le une à ton goût
30/03/2011, 16h58
Tidus159

Re,

Bien que ce ne soit pas de l'ordre de l'algorithme, j'aimerais faire remarquer qu'en statistiques il est généralement mauvais d'enlever des individus ou variables car il manque quelques données.
(Il y a des tests statistiques pour vérifier que justement ces suppressions sont cohérentes et ne faussent pas le tests.)
L'absence de données est un problème récurrent en statistiques et nécessite souvent une réflexion (pourquoi la donnée est absente, pourquoi ne pas mettre la moyenne des données à la place, mettre une valeur arbitraire, etc.).

@+.
30/03/2011, 17h26
tbagwell

Citation:

Envoyé par Tidus159

Re,

Bien que ce ne soit pas de l'ordre de l'algorithme, j'aimerais faire remarquer qu'en statistiques il est généralement mauvais d'enlever des individus ou variables car il manque quelques données.
(Il y a des tests statistiques pour vérifier que justement ces suppressions sont cohérentes et ne faussent pas le tests.)
L'absence de données est un problème récurrent en statistiques et nécessite souvent une réflexion (pourquoi la donnée est absente, pourquoi ne pas mettre la moyenne des données à la place, mettre une valeur arbitraire, etc.).

@+.

Oui je suis bien d'accord. En fait j'ai plusieurs fichiers à analyser, et dans certains il y a presque 80% de données manquantes inégalement réparties suivant les variables et les individus.
Il est donc nécessaire de réaliser une première étape de suppression, avant d'utiliser par exemple les méthodes d'imputation.
Certains fichiers ont plus de 200 variables, donc j'aimerai éviter de tout faire à la main.

euh...

Bêtement un histogramme pour chaque dimension...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
pour i = 0 jusqu'à NLignes
 
    HistoLigne[i] = 0 
 
    pour j = 0 jusqu'à NColonnes
        si  case (i,j) différent de 0
              HistoColonne(j) = 1
              HistoLigne(i) = 1
        fin si
    fin pour
 
fin pour 
 
newNLignes = 0
pour i = 0 jusqu'à NLignes
     si HistoLigne(i) différent de 0
         newNLignes = newNLignes + 1
     fin si
fin pour
 
newNColonnes = 0
pour i = 0 jusqu'à NColonnes
     si HistoColonne(i) différent de 0
         newNColonnes = newNColonnes + 1
     fin si
fin pour
 
 
New Matrice = (newNLignes, NewNColonnes)

PS: et ensuite pour remplir cette nouvelle matrice :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
iligne = 0
 
pour i = 0 jusqu'à NLignes
 
    si HistoLigne(i) différent de 0
 
          icolonne = 0
 
          pour j = 0 jusqu'à NColonnes
             si  case (i,j) différent de 0
                 newcase(iligne, icolonne) = case(i,j)
                 icolonne = icolonne + 1
            fin si
          fin pour
 
          iligne = iligne + 1
 
     fin si
 
fin pour

Merci pour vos réponses.
En fait le plus simple c'est d'utiliser le logiciel R.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
> data <- matrix(1:50, ncol = 5)
> dimnames(data) <- list(paste(1:10, sep = ""), paste("v", 1:5, sep = ""))
> data[c(5, 12, 23, 35, 37, 38, 50)] <- NA
> 
> data
   v1 v2 v3 v4 v5
1   1 11 21 31 41
2   2 NA 22 32 42
3   3 13 NA 33 43
4   4 14 24 34 44
5  NA 15 25 NA 45
6   6 16 26 36 46
7   7 17 27 NA 47
8   8 18 28 NA 48
9   9 19 29 39 49
10 10 20 30 40 NA
> data <- data[,colSums((!is.na(data))/dim(data)[1])>0.75 ]
> data <- data[rowSums((is.na(data))/x)==0,]
> data
  v1 v2 v3 v5
1  1 11 21 41
4  4 14 24 44
6  6 16 26 46
7  7 17 27 47
8  8 18 28 48
9  9 19 29 49
>

01/04/2011, 18h17
Aleph69

Bonjour,

pour trouver un bon compromis entre ce que dis Tidus et ce que tu souhaites faire, je te conseille d'éliminer uniquement des lignes et surtout pas les colonnes (je pars du principe que les variables sont en colonne et les exemples en ligne). Tu vas réduire la taille de ton échantillon mais pas la dimension de ton problème : ça te permettra de mieux conserver la quantité d'information dont tu disposes.
01/04/2011, 18h43
souviron34

cela est-il valable si toute une ligne (ou toute une colonne) manque ?
01/04/2011, 23h51
Aleph69

La question n'a pas de sens puisque si une ligne ou une colonne ne contient que des valeurs manquantes, elle ne contient aucune information.