sous Trouver un motif dans une matrice dans R



r filtrer données (4)

J'ai une matrice 8 xn, par exemple

set.seed(12345)
m <- matrix(sample(1:50, 800, replace=T), ncol=8)
head(m)

     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
[1,]   37   15   30    3    4   11   35   31
[2,]   44   31   45   30   24   39    1   18
[3,]   39   49    7   36   14   43   26   24
[4,]   45   31   26   33   12   47   37   15
[5,]   23   27   34   29   30   34   17    4
[6,]    9   46   39   34    8   43   42   37

Je voudrais trouver un certain modèle dans la matrice, par exemple je voudrais savoir où je peux trouver un 37, suivi dans la ligne suivante par un 10 et un 29 et la ligne après par un 42

Cela se produit, par exemple, aux lignes 57:59 de la matrice ci-dessus

m[57:59,]
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
[1,]  *37   35    1   30   47    9   12   39
[2,]    5   22  *10  *29   13    5   17   36
[3,]   22   43    6    2   27   35  *42   50

Une solution (probablement inefficace) consiste à obtenir toutes les lignes contenant 37

sapply(1:nrow(m), function(x){37 %in% m[x,]})

Et puis utilisez quelques boucles pour tester les autres conditions.

Comment pourrais-je écrire une fonction efficace pour ce faire, qui peut être généralisée à tout modèle donné par l'utilisateur (pas nécessairement sur 3 lignes, avec des "trous" possibles, avec un nombre variable de valeurs dans chaque ligne, etc.)?

EDIT: pour répondre à différents commentaires

  • J'ai besoin de trouver le modèle EXACT
  • L'ordre dans la même rangée n'a pas d'importance (si cela rend les choses plus faciles, les valeurs peuvent être commandées dans chaque rangée)
  • Les lignes doivent être adjacentes.
  • Je veux obtenir la position (de départ) de tous les motifs renvoyés (c'est-à-dire, si le motif est présent plusieurs fois dans la matrice, je veux plusieurs valeurs de retour).
  • L'utilisateur entrerait le modèle via une interface graphique, je n'ai pas encore décidé comment. Par exemple, pour rechercher le modèle ci-dessus, il peut écrire quelque chose comme

37;10,29;42

; représente une nouvelle ligne et sépare les valeurs sur la même ligne. De même, nous pouvons chercher

50,51;;75;80,81

Signification 50 et 51 dans la ligne n, 75 dans la ligne n + 2, et 80 et 81 dans la ligne n + 3

https://src-bin.com


Answer #1

Voici une façon d'utiliser sapply :

which(sapply(seq(nrow(m)-2),
             function(x)
               isTRUE(37 %in% m[x,] & 
                      which(10 == m[x+1,]) < which(29 == m[x+1,]) & 
                      42 %in% m[x+2,])))

Le résultat contient tous les numéros de ligne où la séquence commence:

[1] 57

Answer #2

Voici une fonction généralisée:

PatternMatcher <- function(data, pattern, idx = NULL) {
  p <- unlist(pattern[1])
  if(is.null(idx)){
    p <- unlist(pattern[length(pattern)])
    PatternMatcher(data, rev(pattern)[-1], 
                   idx = Filter(function(n) all(p %in% intersect(data[n, ], p)),
                                1:nrow(data)))
  } else if(length(pattern) > 1) {
    PatternMatcher(data, pattern[-1], 
                   idx = Filter(function(n) all(p %in% intersect(data[n, ], p)), 
                                idx - 1))
  } else
    Filter(function(n) all(p %in% intersect(data[n, ], p)), idx - 1)
}

C'est une fonction récursive qui réduit le pattern à chaque itération et vérifie seulement les lignes qui vont juste après celles identifiées dans l'itération précédente. La structure de liste permet de passer le motif de manière pratique:

PatternMatcher(m, list(37, list(10, 29), 42))
# [1] 57
PatternMatcher(m, list(list(45, 24, 1), 7, list(45, 31), 4))
# [1] 2
PatternMatcher(m, list(1,3))
# [1] 47 48 93

Edit: L'idée de la fonction ci-dessus semble bien: vérifier toutes les lignes pour le pattern[[1]] vectoriel pattern[[1]] et obtenir les indices r1 , puis vérifier les lignes r1+1 pour le pattern[[2]] et obtenir r2 , etc. vraiment beaucoup de temps à la première étape en passant par toutes les rangées. Bien sûr, chaque étape prendrait beaucoup de temps avec par exemple m <- matrix(sample(1:10, 800, replace=T), ncol=8) , c'est-à-dire quand il n'y a pas beaucoup de changement dans les indices r1 , r2 .. Donc, voici une autre approche, ici PatternMatcher ressemble beaucoup, mais il existe une autre fonction matchRow pour trouver des lignes qui ont tous les éléments de vector .

matchRow <- function(data, vector, idx = NULL){
  if(is.null(idx)){
    matchRow(data, vector[-1], 
             as.numeric(unique(rownames(which(data == vector[1], arr.ind = TRUE)))))
  } else if(length(vector) > 0) {
    matchRow(data, vector[-1], 
             as.numeric(unique(rownames(which(data[idx, , drop = FALSE] == vector[1], arr.ind = TRUE)))))
  } else idx
}
PatternMatcher <- function(data, pattern, idx = NULL) {
  p <- pattern[[1]]
  if(is.null(idx)){
    rownames(data) <- 1:nrow(data)
    p <- pattern[[length(pattern)]]
    PatternMatcher(data, rev(pattern)[-1], idx = matchRow(data, p))
  } else if(length(pattern) > 1) {
    PatternMatcher(data, pattern[-1], idx = matchRow(data, p, idx - 1))
  } else
    matchRow(data, p, idx - 1)
}

Comparaison avec la fonction précédente:

library(rbenchmark)
bigM <- matrix(sample(1:50, 800000, replace=T), ncol=8)
benchmark(PatternMatcher(bigM, list(37, c(10, 29), 42)), 
          PatternMatcher(bigM, list(1, 3)), 
          OldPatternMatcher(bigM, list(37, list(10, 29), 42)), 
          OldPatternMatcher(bigM, list(1, 3)), 
          replications = 10,
          columns = c("test", "elapsed"))
#                                                  test elapsed
# 4                 OldPatternMatcher(bigM, list(1, 3))   61.14
# 3 OldPatternMatcher(bigM, list(37, list(10, 29), 42))   63.28
# 2                    PatternMatcher(bigM, list(1, 3))    1.58
# 1       PatternMatcher(bigM, list(37, c(10, 29), 42))    2.02

verybigM1 <- matrix(sample(1:40, 8000000, replace=T), ncol=20)
verybigM2 <- matrix(sample(1:140, 8000000, replace=T), ncol=20)
benchmark(PatternMatcher(verybigM1, list(37, c(10, 29), 42)), 
          PatternMatcher(verybigM2, list(37, c(10, 29), 42)), 
          find.combo(verybigM1, convert.gui.input("37;10,29;42")),
          find.combo(verybigM2, convert.gui.input("37;10,29;42")),          
          replications = 20,
          columns = c("test", "elapsed"))
#                                                      test elapsed
# 3 find.combo(verybigM1, convert.gui.input("37;10,29;42"))   17.55
# 4 find.combo(verybigM2, convert.gui.input("37;10,29;42"))   18.72
# 1      PatternMatcher(verybigM1, list(37, c(10, 29), 42))   15.84
# 2      PatternMatcher(verybigM2, list(37, c(10, 29), 42))   19.62

Aussi maintenant l'argument pattern devrait être comme list(37, c(10, 29), 42) au lieu de list(37, list(10, 29), 42) . Et enfin:

fastPattern <- function(data, pattern)
  PatternMatcher(data, lapply(strsplit(pattern, ";")[[1]], 
                    function(i) as.numeric(unlist(strsplit(i, split = ",")))))
fastPattern(m, "37;10,29;42")
# [1] 57
fastPattern(m, "37;;42")
# [1] 57  4
fastPattern(m, "37;;;42")
# [1] 33 56 77

Answer #3

Peut-être que cela aidera quelqu'un, mais en ce qui concerne les commentaires, je pensais à ce qui suit:

PatternMatcher <- function(data, ...) {
  Selecting procedure here.
}

PatternMatcher(m, c(1, 37, 2, 10, 2, 29, 4, 42))

La deuxième partie alimentée à la fonction consiste, dans l'ordre, à la ligne où elle devrait commencer, suivie de la valeur, puis de la deuxième ligne et de la deuxième valeur. Vous pouvez maintenant aussi dire par exemple la 8ème ligne après la ligne initiale avec la valeur 50.

Vous pouvez même étendre ceci pour demander des coordonnées X, Y spécifiques par valeur (donc 3 éléments passés à la fonction par valeur).


Answer #4

Edit: Maintenant, j'ai ajouté une fonction plus généralisée:

Voici une solution qui donne toutes les combinaisons possibles: expand.grid toutes les positions des quatre nombres, puis j'utilise expand.grid pour obtenir toutes les combinaisons de position et ensuite filter the meaningless en vérifiant si chaque ligne de la matrice est égale à la rangée correspondante la matrice triée.

set.seed(12345)
m <- matrix(sample(1:50, 800, replace=T), ncol=8)
head(m)
get_grid <- function(in_mat, vec_num) {
    v.idx <- sapply(vec_num, function(idx) {
        which(apply(in_mat, 1, function(x) any(x == idx)))
    })
    out <- as.matrix(expand.grid(v.idx))
    colnames(out) <- NULL
    out
}

out <- get_grid(m, c(37, 10, 29, 42))
out.s <- t(apply(out, 1, sort))

idx <- rowSums(out == out.s)
out.f <- out[idx==4, ]

> dim(out.f)
[1] 2946    4

> head(out.f)
     [,1] [,2] [,3] [,4]
[1,]    1   22   28   36
[2,]    4   22   28   36
[3,]    6   22   28   36
[4,]    9   22   28   36
[5,]   11   22   28   36
[6,]   13   22   28   36

Ce sont les indices de rang de l'occurrence des nombres dans cet ordre (37, 10, 29, 42).

De ceci, vous pouvez vérifier n'importe quelle combinaison que vous souhaitez. Par exemple, la combinaison que vous avez demandée peut être accomplie par:

cont.idx <- apply(out.f, 1, function(x) x[1] == x[2]-1 & x[2] == x[4]-1)
> out.f[cont.idx,]
[1] 57 58 58 59