Trigonaliser / Traingulariser une matrice binaire

[Bigot Anthony]

Bonjour,

je cherche depuis un moment une fonction qui permet de trier une matrice selon les deux dimensions sans toucher aux valeurs (comme par combinaisons linéaires par exemple).

Je suis certain que quelqu'un s'est déjà penché sur le sujet...

Exemple :

Code : Tout sélectionner

mat1
     [,1] [,2] [,3]
[1,]    1    0    0
[2,]    1    0    1
[3,]    1    1    1

mat2
     [,1] [,2] [,3]
[1,]    1    1    1
[2,]    0    1    1
[3,]    0    0    1


J'ai regardé heatmap mais je n'obtiens les même résultats qu'avec une cah (distance de manhattan, critère de ward).

Peu importe que les "1" se retrouvent au deuss ou dessous ed la première ou de la seconde diagonale... une fois le tri fait, c'est assez facile à faire.

Si personne ne s'y est collé, je prendrai le temps (à un moment) de chercher mes vieux cours à ce sujet et implementer l'algo.

Merci

________________
Edit : la matrice de départ n'est pas forcément carrée

[Renaud Lancelot]

C'est ça ?

Code : Tout sélectionner

> mat1 <- rbind(c(1,0,0), c(1,0,1), c(1,1,1))
> mat1
     [,1] [,2] [,3]
[1,]    1    0    0
[2,]    1    0    1
[3,]    1    1    1
> colindex <- order(colSums(mat1), decreasing = FALSE)
> rowindex <- order(rowSums(mat1), decreasing = TRUE)
> mat1[rowindex, colindex]
     [,1] [,2] [,3]
[1,]    1    1    1
[2,]    0    1    1
[3,]    0    0    1

[Bigot Anthony]

On dirait bien... merci, j'avais bien eu l'idée d'utiliser les sommes en ligne et en colonne...

j'ai déjà eu des problèmes similaires avec des matrices non binaires pour lesquelles ce n'est pas applicable. (cf un vieux post).

Je teste de suite.


Merci !!

_________________
Edit : Impressionnant, je retombe exactement sur mes classes de la CAH sans faire d'autre tri.

[Bigot Anthony]

J'ai réfléchi à nouveau au problème, il me semblait bien que l'utilisation de la somme en ligne et en colonne possait problème.

Dans le cas de matrice simple, cela fonctionne.

Par contre si on a une matrice come suit (une fois triée):

Code : Tout sélectionner

0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 1 1 1
0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0


Si on a une idée a priori du partitionnement, on peut prcéder par étape en triant les sous matrices, mais ça devient compliqué sur un gros jeu de données.

Si on a pas d'idée a priori par contre...

J'ai vu des échanges sur l'utilisation de méthodes de recuit pour ce genre de tri, ça parle à quelqu'un?

Merci

[Renaud Lancelot]

Est-ce que ça n'est pas simplement un pb de classification ?

[Bigot Anthony]

J'ai essayé avec la heatmap, rien de concluant sur le tri proposé.

Et avec une classif en ligne et une classif en colonne (séparées) les (individus à l'intérieur des) clusters ne sont pas triés ; je me vois ma fair la petite manipulation des colSums sur chacun des croisement de cluster puis aggréger les données...



________________
EDIT : je suis passé sur une autre étude donc je laisse un tomber pour l'instant; j'y reviendrai parce que ça m'interesse

[François Bonnot]

Bonjour,

On peut utiliser la fonction suivante qui ordonne les lignes puis les colonnes et itère jusqu'à ce que lignes et colonnes soient ordonnées (car ordonner les colonnes peut modifier l'ordre les lignes et réciproquement):

Code : Tout sélectionner

ordonne <- function(m) {
    for (i in 1:100) { # on n'arrive jamais à 100
        print(i); flush.console()
        or1 <- order(apply(m,1,paste,collapse='')) # ordre des lignes
        m <- m[or1,]  # permutation des lignes
        or2 <- order(apply(m,2,paste,collapse='')) # ordre des colonnes
        if (all(or2==1:ncol(m))) # arrêt si les colonnes sont triées
            return(m)
        m <- m[,or2] # permutation des colonnes
    }
    print("nombre max d'iterations dépassé") # ça n'arrive jamais
}

Remarque: pour trier en ordre décroissant, il faut ajouter "decreasing=TRUE" dans les deux appels à order(); il ne suffit pas d'inverser l'ordre des lignes et des colonnes dans le résultat.

Exemple 1:

Code : Tout sélectionner

> (m0 <- matrix(c(1,1,1,0,0,1,0,1,1),ncol=3))
     [,1] [,2] [,3]
[1,]    1    0    0
[2,]    1    0    1
[3,]    1    1    1
> ordonne(m0)
[1] 1
[1] 2
     [,1] [,2] [,3]
[1,]    0    0    1
[2,]    0    1    1
[3,]    1    1    1

Exemple 2:

Code : Tout sélectionner

m <- matrix(c(
0,0,0,0,0,0,1,1,1,
0,0,0,0,0,0,1,1,1,
0,0,0,0,0,0,1,1,1,
0,0,0,1,1,1,0,0,0,
0,0,0,1,1,1,0,0,0,
0,0,0,1,1,1,0,0,0,
1,1,1,0,0,0,0,0,0,
1,1,1,0,0,0,0,0,0,
1,1,1,0,0,0,0,0,0),ncol=9,byrow=TRUE)
m0 <- m[sample(1:9),sample(1:9)]
m0
ordonne(m0)

Exemple 3:

Code : Tout sélectionner

n <- 1000
m0 <- matrix(sample(c(0,1),n*n,replace=TRUE),nrow=n)
m1 <- ordonne(m0)

ça marche (même avec des matrices qui ne contiennent pas que des 0 et des 1) mais je ne comprends pas pourquoi !

1) Toute matrice peut-elle être ordonnée sur les lignes et les colonnes par simple permutation?
2) Pourquoi l'algorithme converge-t-il toujours?
3) Pourquoi le nombre d'itérations ne dépasse-t-il jamais quatre?
Mais on s'éloigne de R...