Многие ко многим и написание полуумного алгоритма сопоставления

0

Я изучаю программу с Ruby on Rails, и до сих пор я достиг своей сложнейшей задачи. У меня есть две таблицы, каждая из которых содержит список бизнес-категорий (I.E. Thai Food Restaurant, Plumber, магазин канцелярских товаров). Эти две таблицы взяты из двух разных API, где я по существу выступаю в роли посредника между ними. Они перечисляют более или менее одинаковые типы категорий, но часто они будут выражать его по-разному (I.E. автообслуживание кузова и покраска VS ремонт кузова автомобиля и живопись).

Моя первая цель заключалась в разработке модели для этой задачи. Я решил "много для многих" и протестировал его, вручную сопоставив две строки. Готово. Проверено. Высокий.

Моя вторая цель - написать алгоритм для сопоставления строк из двух таблиц друг с другом, придавая приоритет, основанный на подобии. Я предполагаю, что большая часть работы может быть выполнена в MySQL. Вот мой псевдокод:

for each row in table 1
    split phrase up into words by spaces

    SELECT name, id FROM joined_table
        SELECT name, id FROM table2 AS word1 WHERE name LIKE '% word1 %'
        SELECT name, id FROM table2 AS word2 WHERE name LIKE '% word2 %'
        SELECT name, id FROM table2 AS word3 WHERE name LIKE '% word3 %'
        JOIN word1, word2, word3 WHERE word1.id == word2.id 
                                    OR word2.id == word3.id
        order by count of matches of each word

    insert relationships into map table
end

Я никогда раньше не разрабатывал алгоритм поиска, поэтому любая помощь, которую вы могли бы оказать, очень ценится. Мне очень интересно это понять, но я подумал, что доберусь до меня и получаю советы от профессионалов.

Ура!

Обновление: Сотрудник рекомендовал, чтобы я просмотрел веб-сайт механический турк, который оказался быть наиболее экономичным способом сопоставления категорий. Все, что мне нужно было сделать, это построить простую форму, и она разорвалась примерно на 3,00 доллара за тысячу матчей.

Теги:
algorithm
search

2 ответа

0
Лучший ответ

У вас нет полного ответа, есть предложения.

Если я понимаю, что вы пытаетесь сделать, я думаю, что это может быть трудно полностью автоматизировать.

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

С самого начала предположим, что некоторые матчи будут легкими, некоторые трудно, и что потребуется несколько правил.

Ваше первое правило может быть "точная совпадение совпадений фразы", ​​и, возможно, правило "максимизировать совпадение слов", которое вы описываете, может быть хорошим как второе правило. Но у вас могут быть ложные совпадения. В примере, который вы цитируете, слово, которое не соответствует - auto versus car - довольно важно для понимания того, что существует совпадение.

Вам нужно будет иметь какой-то способ обработки категорий, которые не имеют эквивалента на другой стороне, которые, вероятно, будут в наборе из 15K.

Когда вы получаете обновления данных, сравнивайте новые и старые и обрабатываете только изменения - минимизируете работу.

Поделиться
0

Вы не должны этого делать.

Лучший способ - нормализовать ваши данные, а затем просто сопоставить его

если "auto" == "автомобиль", затем измените все "автомобиль" на "авто". Подобно тому, как вы конвертируете все из смешанного к верхнему или нижнему регистру.

Сохраняйте фактическое значение, "нормализуйте" данные и сохраните их, затем вы можете сопоставить нормализованные данные.

Это также позволяет вам иметь "произвольно" сложные правила нормализации, чем то, что доступно в SQL, и вы также запускаете его только один раз, а не для каждого запроса.

Изменить - для комментариев.

Как насчет этого.

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

Пропустите все данные и выполните некоторую базовую текстовую обработку свободной формы. Нормализовать регистр, вытеснять "неинтересные" слова или "останавливать" слова, как их называют. Вы можете найти основы для такого рода обработки в Интернете. Это не сложно.

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

Хорошей вещью в этой точке является создание инвертированной таблицы индексов. Например, если у вас есть 3 записи со словом "auto", у вас есть 3 строки в инвертированной таблице индексов:

"auto", 123
"auto", 456
"auto", 789

Если вы хотите найти, какие строки имеют "авто", вы присоединяетесь к этой индексной таблице.

Теперь вы повторяете свой набор данных.

Вы конвертируете свой текст, используя описанную выше технику, то есть нормализуете текст и теперь имеете список "интересных" слов.

Вы используете свой инвертированный индекс, чтобы найти все подходящие строки, которые являются даже потенциальными кандидатами для соответствия, т.е. все строки, которые содержат хотя бы одно из слов в вашем "интересном" списке.

Наконец, вы затем нормализуете текст этих строк, пересекаете свой набор интересных слов и их интересный набор. Это дает вам количество совпадающих слов. Затем вы можете сделать что-то просто, как "количество совпадающих слов/количество слов в кандидате" до базового процентного рейтинга.

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

Кроме того, эту работу можно выполнить итеративно. Вам не нужно повторно обрабатывать весь набор данных.

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

Должно быть довольно быстро в конце.

Поделиться
  • 0
    Уилл, это интересный момент, и я уверен, что это очень хороший метод для такого рода задач. Хотя я не уверен, что это применимо ... Во-первых, в одной из таблиц содержится более 15 тысяч строк, поэтому для нормализации всех этих слов потребуется много человеко-часов. Во-вторых, мне нужно выполнить это только один раз (или один раз при каждом обновлении таблицы), чтобы заполнить мою таблицу модели соединения, тогда все дело только в том, чтобы Rails выполнял cat1.cat2, что является простым запросом. Спасибо за ваш вклад. Если вы думаете, что я неправ, непременно сообщите мне. Спасибо за ваше время : )

Ещё вопросы

Сообщество Overcoder
Наверх
Меню