Как квази сопоставить два вектора строк (в R)?

Я не уверен, как это следует называть, поэтому, пожалуйста, поправьте меня, если вы знаете лучший термин.

У меня есть два списка. Один из 55 элементов (например, вектор строк), другой из 92. Имена элементов похожи, но не идентичны.

Я хочу , чтобы найти лучший кандидат S в 92 списке элементов в списке 55 (я затем пройти через него и выбрать правильную установку).

Как это можно сделать?

У меня были идеи, где:

1. Просмотреть все те, которые соответствуют (используя что-то список? Матч)
2. Попробуйте использовать матрицу расстояний между векторами строк, но я не уверен, как ее лучше определить (количество одинаковых букв, как насчет порядка строк?)

Так какой пакет / функции / область исследований решает такую ​​задачу и как?

Обновление: вот пример векторов, которые я хочу сопоставить

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"
) 

У меня были похожие проблемы. (видно здесь: https://stackoverflow.com/questions/2231993/merging-two-data-frames-using-fuzzy-approximate-string-matching-in-r )

Большинство рекомендаций, которые я получил, провалились:

pmatch(), и agrep(), grep()- grepl()это три функции, которые, если вы потратите время на просмотр, предоставят вам некоторое представление о приближенном сопоставлении строк либо с помощью приблизительной строки, либо с помощью приблизительного регулярного выражения.

Не видя струн, сложно дать вам пример того, как их сопоставить. Если бы вы могли предоставить нам пример данных, я уверен, что мы могли бы прийти к решению.

Другой вариант, который я нашел, работает хорошо, это сгладить строки, tolower()глядя на первую букву каждого слова в строке и затем сравнивая. Иногда это работает без проблем. Тогда есть более сложные вещи, такие как расстояния, упомянутые в других ответах. Иногда они работают, иногда они ужасны - это действительно зависит от условий.

Можем ли мы их увидеть?

Обновить

Похоже, agrep () поможет большинству из них. Обратите внимание, что agrep () - это просто реализация R расстояния Левенштейна.

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

Некоторые не вычисляют, хотя, я даже не уверен, является ли Ferroplasm acidaramus таким же, как Ferroglobus placidus DSM 10642, например:

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

Я думаю, что вы можете быть немного SOL для некоторых из них, и, возможно, лучше всего создать индекс с нуля. то есть ,. Создайте таблицу с номерами идентификаторов для vec55, а затем вручную создайте ссылку на идентификаторы в vec55 в vec91. Я знаю, это больно, но многое можно сделать с помощью agrep ().

Существует много способов измерения расстояний между двумя строками. Два важных (стандартных) подхода, широко применяемых в R, это расстояние Левенштейна и Хэмминга. Первый доступен в пакете «MiscPsycho», а второй - в «e1071». Используя их, я просто вычислил бы матрицу парных расстояний 92 на 55, а затем продолжил оттуда (то есть лучшим кандидатом на совпадение для строки «1» в списке 1 является строка «x» из списка 2 с наименьшим расстоянием до строки «1»). «).

Кроме того , существует функция сравнения () в пакете RecordLinkage , что , кажется, разработан , чтобы сделать то , что вы хотите , и использует так называемый Яро-Винклер расстояние , которое кажется более подходящим для выполнения этой задачи под рукой, но я не имел опыта работы с ним ,

РЕДАКТИРОВАТЬ: я редактирую свой ответ, чтобы включить комментарий Брэндона, а также код Тала, чтобы найти соответствие «Aeropyrum pernix», первой записи vec55 :

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

В дополнение к полезному ответу Квака, позвольте мне добавить несколько простых принципов и идей. Хороший способ определить метрику - рассмотреть, как строки могут отличаться от своих целей. «Редактировать расстояние» полезно, когда вариация представляет собой комбинацию типографских ошибок, таких как транспонирование соседей или неправильный ввод одной клавиши.

Другой полезный подход (с немного другой философией) состоит в отображении каждой строки в одного представителя класса связанных строк. Метод « Soundex » делает это: код Soundex для слова представляет собой последовательность из четырех символов, кодирующих основную согласную и группы похожих по звучанию внутренних следствий. Используется, когда слова являются фонетическими опечатками или вариантами друг друга. В примере приложения вы выбираете все целевые слова, чей код Soundex равен коду Soundex для каждого тестового слова. (Там может быть ноль или несколько целей, выбранных таким образом.)

Я бы также посоветовал вам проверить N-граммы и расстояние Дамерау – Левенштейна помимо других предложений Квака.

В этой статье сравнивается точность нескольких различных расстояний редактирования, упомянутых здесь (и высоко цитируется в соответствии с Google ученым).

Как вы можете видеть, есть много разных подходов к этому, и вы можете даже комбинировать разные метрики (статья, которую я связал, рассказывает об этом немного). Я думаю, что Левенштейн и связанные с ним метрики имеют наиболее интуитивный смысл, особенно если ошибки происходят из-за человеческой типизации. N-граммы также просты и имеют смысл для данных, которые не являются именами или словами на слово.

В то время как soundex является опцией, небольшая работа, которую я видел (которая, по общему признанию, очень мала), soundex не работает так же хорошо, как Левенштайн или другие расстояния редактирования для сопоставления имен. И Soundex ограничен фонетическими фразами, которые, вероятно, вводят люди, набирающие текст, где Левенштейн и N-граммы имеют потенциально более широкую область действия (особенно N-грамм, но я ожидаю, что расстояние Левенштейна также будет лучше для несловесных слов).

Я не могу помочь с пакетами, но концепция N-грамм довольно проста (я недавно сделал макрос SPSS, чтобы делать N-грамм, но для такого небольшого проекта я бы просто пошел с уже созданными пакетами в R другие постеры предложили). Вот пример вычисления расстояния Левенштейна в питоне.

Я исследовал некоторые пакеты и способы, как решить эту проблему, и я думаю, что лучший кандидат fuzzywuzzyR пакет.

Пакет fuzzywuzzyR является реализацией нечеткого соответствия строк пакета fuzzywuzzy python. Он использует расстояние Левенштейна для расчета различий между последовательностями. Более подробную информацию о функциональности fuzzywuzzyR можно найти в блоге и в пакете Vignette.

Я сделал простое решение для вашей проблемы, но есть небольшой улов. Вы должны установить Python и, если вы используете Winodows, также необходимо установить некоторые инструменты сборки для Visual Studio . Вы должны выбрать это:

• Windows 10 SDK 10.0.17763.0 и MSVC v140
• Инструменты сборки VS 2015 C ++ (v 14v00)

Решение простое. Основная функция ExtractOneвозвращает список из двух значений. Первая - это совпадение одной строки, а вторая - соответствующая оценка (в диапазоне от 0 до 100). fuzzywuzzyRПакет обеспечивает также другие функции , которые могут быть полезны. Основную документацию можно найти здесь . Я надеюсь, что этот код поможет решить проблему.

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)   
}

Выход:

[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"       

На основе функции adist

Вычислить приблизительное расстояние между символьными векторами. Расстояние - это обобщенное расстояние Левенштейна (правка), дающее минимально возможное взвешенное количество вставок, удалений и подстановок, необходимых для преобразования одной строки в другую.

Функция stringdistиз одноименного пакета имеет несколько методов (см. ?stringdist):

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

При этом вы можете выбрать максимальное расхождение (порог):

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

Этот информационный кадр показывает первый вектор в первом векторе столбца, наилучшее совпадение второго вектора в сопоставлении столбца, его расстояние в расхождении столбца и все значимые совпадения, упорядоченные в отсортированных сопоставлениях столбца, как в OP.