Wie kann man quasi zwei Vektoren von Strings (in R) zuordnen?

Ich bin mir nicht sicher, wie dies bezeichnet werden soll. Bitte korrigieren Sie mich, wenn Sie einen besseren Begriff kennen.

Ich habe zwei Listen. Eines von 55 Elementen (z. B. ein Vektor von Zeichenfolgen), das andere von 92. Die Elementnamen sind ähnlich, aber nicht identisch.

Ich wünsche den besten Kandidaten finden s in der 92 - Liste , um die Elemente in der 55 - Liste (ich werde dann durch sie gehen und den korrekten Sitz wählen).

Wie geht das?

Ich hatte Ideen, wo ich:

1. Alle Übereinstimmungen anzeigen (mithilfe einer Liste? Übereinstimmungen)
2. Versuchen Sie es mit einer Abstandsmatrix zwischen den Zeichenfolgenvektoren, aber ich bin nicht sicher, wie ich sie am besten definieren soll (Anzahl identischer Buchstaben, was ist mit der Reihenfolge der Zeichenfolgen?)

Welches Paket / Funktionen / Forschungsfeld befasst sich mit einer solchen Aufgabe und wie?

Update: Hier ist ein Beispiel für die Vektoren, die ich abgleichen möchte

vec55 <- c("Aeropyrum pernix", "Archaeoglobus fulgidus", "Candidatus_Korarchaeum_cryptofilum", 
"Candidatus_Methanoregula_boonei_6A8", "Cenarchaeum_symbiosum", 
"Desulfurococcus_kamchatkensis", "Ferroplasma acidarmanus", "Haloarcula_marismortui_ATCC_43049", 
"Halobacterium sp.", "Halobacterium_salinarum_R1", "Haloferax volcanii", 
"Haloquadratum_walsbyi", "Hyperthermus_butylicus", "Ignicoccus_hospitalis_KIN4", 
"Metallosphaera_sedula_DSM_5348", "Methanobacterium thermautotrophicus", 
"Methanobrevibacter_smithii_ATCC_35061", "Methanococcoides_burtonii_DSM_6242"
)
vec91 <- c("Acidilobus saccharovorans 345-15", "Aciduliprofundum boonei T469", 
"Aeropyrum pernix K1", "Archaeoglobus fulgidus DSM 4304", "Archaeoglobus profundus DSM 5631", 
"Caldivirga maquilingensis IC-167", "Candidatus Korarchaeum cryptofilum OPF8", 
"Candidatus Methanoregula boonei 6A8", "Cenarchaeum symbiosum A", 
"Desulfurococcus kamchatkensis 1221n", "Ferroglobus placidus DSM 10642", 
"Halalkalicoccus jeotgali B3", "Haloarcula marismortui ATCC 43049", 
"Halobacterium salinarum R1", "Halobacterium sp. NRC-1", "Haloferax volcanii DS2", 
"Halomicrobium mukohataei DSM 12286", "Haloquadratum walsbyi DSM 16790", 
"Halorhabdus utahensis DSM 12940", "Halorubrum lacusprofundi ATCC 49239", 
"Haloterrigena turkmenica DSM 5511", "Hyperthermus butylicus DSM 5456", 
"Ignicoccus hospitalis KIN4/I", "Ignisphaera aggregans DSM 17230", 
"Metallosphaera sedula DSM 5348", "Methanobrevibacter ruminantium M1", 
"Methanobrevibacter smithii ATCC 35061", "Methanocaldococcus fervens AG86", 
"Methanocaldococcus infernus ME", "Methanocaldococcus jannaschii DSM 2661", 
"Methanocaldococcus sp. FS406-22", "Methanocaldococcus vulcanius M7", 
"Methanocella paludicola SANAE", "Methanococcoides burtonii DSM 6242", 
"Methanococcus aeolicus Nankai-3", "Methanococcus maripaludis C5", 
"Methanococcus maripaludis C6", "Methanococcus maripaludis C7", 
"Methanococcus maripaludis S2", "Methanococcus vannielii SB", 
"Methanococcus voltae A3", "Methanocorpusculum labreanum Z", 
"Methanoculleus marisnigri JR1", "Methanohalobium evestigatum Z-7303", 
"Methanohalophilus mahii DSM 5219", "Methanoplanus petrolearius DSM 11571", 
"Methanopyrus kandleri AV19", "Methanosaeta thermophila PT", 
"Methanosarcina acetivorans C2A", "Methanosarcina barkeri str. Fusaro", 
"Methanosarcina mazei Go1", "Methanosphaera stadtmanae DSM 3091", 
"Methanosphaerula palustris E1-9c", "Methanospirillum hungatei JF-1", 
"Methanothermobacter marburgensis str. Marburg", "Methanothermobacter thermautotrophicus str. Delta H", 
"Nanoarchaeum equitans Kin4-M", "Natrialba magadii ATCC 43099", 
"Natronomonas pharaonis DSM 2160", "Nitrosopumilus maritimus SCM1", 
"Picrophilus torridus DSM 9790", "Pyrobaculum aerophilum str. IM2", 
"Pyrobaculum arsenaticum DSM 13514", "Pyrobaculum calidifontis JCM 11548", 
"Pyrobaculum islandicum DSM 4184", "Pyrococcus abyssi GE5", "Pyrococcus furiosus DSM 3638", 
"Pyrococcus horikoshii OT3", "Staphylothermus hellenicus DSM 12710", 
"Staphylothermus marinus F1", "Sulfolobus acidocaldarius DSM 639", 
"Sulfolobus islandicus L.D.8.5", "Sulfolobus islandicus L.S.2.15", 
"Sulfolobus islandicus M.14.25", "Sulfolobus islandicus M.16.27", 
"Sulfolobus islandicus M.16.4", "Sulfolobus islandicus Y.G.57.14", 
"Sulfolobus islandicus Y.N.15.51", "Sulfolobus solfataricus P2", 
"Sulfolobus tokodaii str. 7", "Thermococcus gammatolerans EJ3", 
"Thermococcus kodakarensis KOD1", "Thermococcus onnurineus NA1", 
"Thermococcus sibiricus MM 739", "Thermofilum pendens Hrk 5", 
"Thermoplasma acidophilum DSM 1728", "Thermoplasma volcanium GSS1", 
"Thermoproteus neutrophilus V24Sta", "Thermosphaera aggregans DSM 11486", 
"Vulcanisaeta distributa DSM 14429", "uncultured methanogenic archaeon RC-I"
) 

Ich hatte ähnliche Probleme. (hier zu sehen: https://stackoverflow.com/questions/2231993/merging-two-data-frames-using-fuzzy-approximate-string-matching-in-r )

Die meisten Empfehlungen, die ich erhalten habe, waren:

pmatch()Und agrep(), grep(), grepl()sind drei Funktionen, wenn Sie sich die Zeit nehmen Sie einen Einblick in ungefähre String - Matching durch ungefähre Zeichenfolge oder ungefähre Regex entweder zur verfügung , um zu schauen.

Ohne die Zeichenfolgen zu sehen, ist es schwierig, Ihnen ein anschauliches Beispiel für die Zuordnung zu geben. Wenn Sie uns einige Beispieldaten zur Verfügung stellen könnten, sind wir sicher, dass wir zu einer Lösung kommen könnten.

Eine andere Option, die ich für gut befunden habe, besteht darin, die Zeichenfolgen zu reduzieren, tolower()den ersten Buchstaben jedes Worts in der Zeichenfolge zu betrachten und dann zu vergleichen. Manchmal funktioniert das problemlos. Dann gibt es kompliziertere Dinge wie die Entfernungen, die in anderen Antworten erwähnt werden. Manchmal funktionieren diese, manchmal sind sie schrecklich - es kommt wirklich auf die Saiten an.

Können wir sie sehen?

Aktualisieren

Es sieht so aus, als würde agreep () für die meisten von ihnen den Trick machen. Beachten Sie, dass agreep () nur die Implementierung von Levenshtein distance durch R ist.

agrep(vec55[1],vec91,value=T)

Einige berechnen zwar nicht, ich bin mir nicht mal sicher, ob Ferroplasmacidaramus mit Ferroglobus placidus DSM 10642 identisch ist, zum Beispiel:

agrep(vec55[7],vec91,value=T) 

Ich denke, dass Sie für einige von ihnen ein bisschen SOL sind, und vielleicht ist es die beste Wahl, einen Index von Grund auf neu zu erstellen. dh. Erstellen Sie eine Tabelle mit ID-Nummern für vec55 und erstellen Sie dann manuell einen Verweis auf die IDs in vec55 in vec91. Schmerzhaft, ich weiß, aber vieles kann mit agreep () erledigt werden.

Es gibt viele Möglichkeiten, Abstände zwischen zwei Saiten zu messen. Zwei wichtige (Standard-) Ansätze, die in R weit verbreitet sind, sind der Levenshtein- und der Hamming-Abstand. Ersteres ist im Paket 'MiscPsycho' und letzteres in 'e1071' verfügbar. Mit diesen würde ich einfach eine 92 x 55-Matrix paarweiser Abstände berechnen und dann von dort fortfahren (dh die beste Kandidatenübereinstimmung für die Zeichenfolge "1" in Liste 1 ist die Zeichenfolge "x" aus Liste 2 mit dem geringsten Abstand zur Zeichenfolge "1 ").

Alternativ gibt es eine Funktion compare () im Paket RecordLinkage, die so konzipiert zu sein scheint, dass sie das tut, was Sie wollen, und die so genannte Jaro-Winkler- Distanz verwendet, die für die jeweilige Aufgabe angemessener zu sein scheint, aber ich habe keine Erfahrung damit .

BEARBEITEN: Ich bearbeite meine Antwort so, dass sie Brandons Kommentar sowie Tals Code enthält, um eine Übereinstimmung mit "Aeropyrum pernix", dem ersten Eintrag von vec55, zu finden :

agrep(vec55[1],vec91,ignore.case=T,value=T,max.distance = 0.1, useBytes = FALSE)
[1] "Aeropyrum pernix K1"

Lassen Sie mich einige einfache Prinzipien und Ideen hinzufügen, um Kwaks nützliche Antwort zu ergänzen. Ein guter Weg, um die Metrik zu bestimmen, besteht darin, zu berücksichtigen, wie die Zeichenfolgen von ihrem Ziel abweichen können. "Abstand bearbeiten" ist nützlich, wenn die Variation eine Kombination von Tippfehlern ist, z. B. das Vertauschen von Nachbarn oder das falsche Eingeben eines einzelnen Schlüssels.

Ein weiterer nützlicher Ansatz (mit einer etwas anderen Philosophie) besteht darin, jede Zeichenfolge einem Vertreter einer Klasse verwandter Zeichenfolgen zuzuordnen. Die " Soundex " -Methode führt dies aus: Der Soundex-Code für ein Wort ist eine Folge von vier Zeichen, die den Hauptkonsonanten und Gruppen von ähnlich klingenden internen Konsequenzen codieren. Es wird verwendet, wenn Wörter phonetische Rechtschreibfehler oder Varianten voneinander sind. In der Beispielanwendung würden Sie alle Zielwörter abrufen, deren Soundex-Code dem Soundex-Code für jedes Prüfwort entspricht. (Auf diese Weise können null oder mehrere Ziele abgerufen werden.)

Ich würde auch vorschlagen, dass Sie sich neben den anderen Vorschlägen von Kwak auch die N-Gramme und die Damerau-Levenshtein- Distanz ansehen.

Dieser Artikel vergleicht die Genauigkeit einiger hier genannter Bearbeitungsabstände (und wird laut Google Scholar in hohem Maße zitiert).

Wie Sie sehen, gibt es viele verschiedene Möglichkeiten, um dies zu erreichen, und Sie können sogar verschiedene Metriken kombinieren (das Papier, das ich mit Gesprächen über dieses kleine Stück verknüpft habe). Ich denke, das Levenshtein und verwandte Metriken machen den intuitivsten Sinn, besonders wenn Fehler aufgrund menschlicher Eingabe auftreten. N-Gramme sind auch einfach und sinnvoll für Daten, bei denen es sich nicht um Namen oder Wörter handelt.

Obwohl Soundex eine Option ist, funktioniert Soundex bei der Arbeit, die ich gesehen habe (die zugegebenermaßen eine sehr kleine Menge ist), nicht so gut wie Levenshstein oder andere Bearbeitungsentfernungen für übereinstimmende Namen. Und der Soundex ist auf phonetische Ausdrücke beschränkt, die wahrscheinlich von menschlichen Schreibmaschinen eingegeben werden, wobei Levenshtein und N-Gramm einen potenziell breiteren Anwendungsbereich haben (insbesondere N-Gramm, aber ich würde erwarten, dass der Levenshtein-Abstand auch für Nichtwörter besser ist).

Ich kann nicht helfen, was Pakete angeht, aber das Konzept von N-Gramm ist ziemlich einfach (ich habe kürzlich ein SPSS-Makro erstellt, um N-Gramm zu erstellen, aber für ein so kleines Projekt würde ich einfach die bereits erstellten Pakete verwenden R die anderen Plakate haben vorgeschlagen). Hier ist ein Beispiel für die Berechnung der Levenshtein-Distanz in Python.

Ich habe einige Pakete und Möglichkeiten zur Lösung dieses Problems recherchiert und denke, der beste Kandidat ist das fuzzywuzzyRPaket.

Das fuzzywuzzyR-Paket ist eine Implementierung des fuzzywuzzy- Python-Pakets, die mit einer Fuzzy-Zeichenfolge übereinstimmt . Es verwendet den Levenshtein-Abstand, um die Unterschiede zwischen Sequenzen zu berechnen. Weitere Details zur Funktionalität von fuzzywuzzyR finden Sie im Blog-Post und im Paket Vignette.

Ich habe die einfache Lösung für Ihr Problem gemacht, aber es gibt einen kleinen Haken. Sie müssen Python installieren und wenn Sie Winodows verwenden, müssen Sie auch einige Build-Tools für Visual Studio installieren . Sie müssen diese auswählen:

• Windows 10 SDK 10.0.17763.0 und MSVC v140
• VS 2015 C ++ Build-Tools (Version 14v00)

Die Lösung ist einfach. Die Hauptfunktion ExtractOnegibt eine Liste mit zwei Werten zurück. Das erste ist eine Zeichenfolgeübereinstimmung und das zweite ist die entsprechende Punktzahl (im Bereich von 0 bis 100). Das fuzzywuzzyRPaket bietet auch andere Funktionen, die nützlich sein können. Die Hauptdokumentation finden Sie hier . Ich hoffe, dieser Code hilft, das Problem zu lösen.

library(fuzzywuzzyR)

# The Fuzzy initialization
init_proc = FuzzUtils$new()
PROC = init_proc$Full_process # class process-method
PROC1 = tolower # base R function
init_scor = FuzzMatcher$new()
SCOR = init_scor$WRATIO    
init <- FuzzExtract$new()

match_strings <- function(vector_to_process, base_vector){  
  new_vec = c()
  for(i in 1:length(vector_to_process)){      
    new_word <- init$ExtractOne(string = vector_to_process[i], sequence_strings = base_vector, processor = PROC1, scorer = SCOR, score_cutoff = 0L)
    new_vec[i] <- new_word[[1]]
  }     
  return(new_vec)
}

# Check if all python modules are available
if (check_availability()){    
  new_vec <- match_strings(vec55, vec91)
  print(new_vec)   
}

Ausgabe:

[1] "Aeropyrum pernix K1"                                 "Archaeoglobus fulgidus DSM 4304"                    
[3] "Candidatus Korarchaeum cryptofilum OPF8"             "Candidatus Methanoregula boonei 6A8"                
[5] "Cenarchaeum symbiosum A"                             "Desulfurococcus kamchatkensis 1221n"                
[7] "Thermoplasma volcanium GSS1"                         "Haloarcula marismortui ATCC 43049"                  
[9] "Halobacterium sp. NRC-1"                             "Halobacterium salinarum R1"                         
[11] "Haloferax volcanii DS2"                              "Haloquadratum walsbyi DSM 16790"                    
[13] "Hyperthermus butylicus DSM 5456"                     "Ignicoccus hospitalis KIN4/I"                       
[15] "Metallosphaera sedula DSM 5348"                      "Methanothermobacter thermautotrophicus str. Delta H"
[17] "Methanobrevibacter smithii ATCC 35061"               "Methanococcoides burtonii DSM 6242"       

Basierend auf funktion adist

Berechnen Sie den ungefähren Zeichenfolgenabstand zwischen Zeichenvektoren. Der Abstand ist ein verallgemeinerter Levenshtein-Abstand (edit), der die minimale, möglicherweise gewichtete Anzahl von Einfügungen, Löschungen und Ersetzungen angibt, die erforderlich sind, um eine Zeichenfolge in eine andere umzuwandeln

Die Funktion stringdistaus einem gleichnamigen Paket hat mehrere Methoden (siehe ?stringdist):

method = c ("osa", "lv", "dl", "hamming", "lcs", "qgram", "cosine", "jaccard", "jw", "soundex")

Hiermit können Sie die maximale Abweichung (Schwelle) auswählen:

firstvector<-vec55
secondvector<-vec91

match<-character()
threshold<-14 # max 14 characters of divergence
mindist<-integer()
sortedmatches<-character()

for (i in 1:length(firstvector) ) {
  matchdist<-adist(firstvector[i],secondvector)[1,]
  # matchdist<-stringdist(firstvector[i],secondvector) # several methods available

  matchdist<-ifelse(matchdist>threshold,NA,matchdist)
  sortedmatches[i]<-paste(secondvector[order(matchdist, na.last=NA)], collapse = ", ")
  mindist[i]<- tryCatch(ifelse(is.integer(which.min(matchdist)),matchdist[which.min(matchdist)],NA), error = function(e){NA})
  match[i]<-ifelse(length(secondvector[which.min(matchdist)])==0,NA,
                  secondvector[which.min(matchdist)] )
}
res<-data.frame(firstvector=firstvector,match=match,divergence=mindist, sortedmatches=sortedmatches, stringsAsFactors = F)
res

Dieser Datenrahmen zeigt den ersten Vektor in der Spalte firstvector, die beste Übereinstimmung des zweiten Vektors in der Spaltenübereinstimmung, den Abstand in der Spaltendivergenz und alle signifikanten Übereinstimmungen, die in Spaltensortierungsübereinstimmungen wie im OP geordnet sind.