В мире программирования и анализа данных алгоритмы играют решающую роль в эффективном решении различных задач. Одним из таких алгоритмов, получивших популярность, является алгоритм FuzzyWuzzy, также известный как алгоритм fuzz. Несмотря на свое шутливое название, FuzzyWuzzy служит серьезной цели, предоставляя средства для сравнения и сопоставления строк, даже если они не совсем идентичны. В этом посте мы погрузимся в увлекательный мир нечеткости и разберемся в работе алгоритма FuzzyWuzzy.
Что такое нечеткость и как она работает?
Представьте, что у вас есть список имен, и вам нужно найти совпадения в этом списке. Однако из-за человеческой ошибки или непоследовательного ввода данных имена могут не всегда точно совпадать. Здесь в игру вступает нечеткость. Нечеткость позволяет нам обрабатывать эти вариации и находить приблизительные совпадения между строками, принимая во внимание сходство, а не строгое равенство.
Сходство строк означает, насколько две строки похожи друг на друга. Например, слова «яблоко» и «яблоки» очень похожи, потому что отличаются всего одной буквой. С другой стороны, слова «яблоко» и «банан» не очень похожи, потому что у них очень разные буквы.
Нечеткое сопоставление — это метод, используемый для поиска похожих строк, даже если они не совсем совпадают. Это похоже на поиск совпадений, которые достаточно близки, даже если они имеют некоторые различия. Это может быть полезно в различных приложениях, таких как поиск похожих слов, исправление орфографических ошибок или сравнение имен.
Библиотека thefuzz — это библиотека Python, предоставляющая инструменты для нечеткого сопоставления строк. Один из важных компонентов в этой библиотеке называется «python-Levenshtein». Это модуль в библиотеке, который реализует определенный алгоритм, называемый расстоянием Левенштейна.
Расстояние Левенштейна — это мера разницы между двумя строками. Он вычисляет минимальное количество операций, необходимых для преобразования одной строки в другую. Этими операциями могут быть вставка символа, удаление символа или замена символа. Чем меньше расстояние Левенштейна, тем более похожи строки.
Давайте посмотрим на пример, чтобы понять это лучше. Предположим, у нас есть две строки: «котенок» и «сидит». Расстояние Левенштейна между этими двумя строками равно 3, потому что нам нужно выполнить три операции:
1. Замените «k» в слове «котенок» на «s»: «сидит».
2. Замените букву «e» в слове «sitten» на «i»: «sittin».
3. Вставьте букву «g» в конце слова «sittin»: «сидит».
В этом примере расстояние Левенштейна, равное 3, указывает на то, что «котенок» и «сидит» очень похожи.
Помимо расстояния Левенштейна, в библиотеке фазз используются и другие алгоритмы нечеткого сопоставления.
Другие нечеткие алгоритмы:
- Простое соотношение:
from fuzzywuzzy import fuzz string1 = "apple" string2 = "apples" similarity_ratio = fuzz.ratio(string1, string2) print(similarity_ratio) # Output: 91The simple ratio algorithm calculates the similarity ratio by comparing the number of matching characters and the total number of characters in both strings. It does not consider partial matches or word order.
Алгоритм простого отношения вычисляет отношение сходства, сравнивая количество совпадающих символов и общее количество символов в обеих строках. Он не учитывает частичные совпадения или порядок слов.
2. Частичное соотношение:
from fuzzywuzzy import fuzz string1 = "apple" string2 = "apples and bananas" partial_ratio = fuzz.partial_ratio(string1, string2) print(partial_ratio) # Output: 100
Алгоритм частичного соотношения учитывает частичные совпадения и ищет наиболее подходящую подстроку в более длинной строке. В этом примере, несмотря на то, что вторая строка содержит дополнительные слова, совпадающая подстрока «яблоко» приводит к идеальному частичному соотношению.
3. Коэффициент сортировки токенов:
from fuzzywuzzy import fuzz string1 = "apple banana" string2 = "banana apple" token_sort_ratio = fuzz.token_sort_ratio(string1, string2) print(token_sort_ratio) # Output: 100
Алгоритм коэффициента сортировки токенов разбивает обе строки на отдельные слова, сортирует их в алфавитном порядке, а затем вычисляет коэффициент сходства. Он нечувствителен к порядку слов. В этом примере слова «яблоко» и «банан» совпадают в обеих строках, что обеспечивает идеальное совпадение.
4. Соотношение набора токенов:
from fuzzywuzzy import fuzz string1 = "apple banana banana apple" string2 = "banana apple" token_set_ratio = fuzz.token_set_ratio(string1, string2) print(token_set_ratio) # Output: 100
Алгоритм отношения набора токенов разбивает обе строки на отдельные слова, игнорируя дубликаты, а затем вычисляет отношение сходства. Он также нечувствителен к порядку слов. В этом примере слова «яблоко» и «банан» совпадают в обеих строках, что обеспечивает идеальное совпадение.
5. Коэффициент частичного набора токенов:
from fuzzywuzzy import fuzz string1 = "apple banana orange" string2 = "banana orange" partial_token_set_ratio = fuzz.partial_token_set_ratio(string1, string2) print(partial_token_set_ratio) # Output: 100
Алгоритм частичного соотношения наборов токенов представляет собой комбинацию алгоритмов частичного отношения и отношения наборов токенов. Он размечает обе строки, игнорирует дубликаты и находит наиболее подходящее подмножество в более длинной строке. В этом примере слова «банан» и «апельсин» идеально совпадают, что приводит к высокому соотношению.
6. Процесс:
Кроме того, библиотека fuzz предоставляет функцию process.extract(), которую можно использовать для извлечения лучших совпадений из списка вариантов на основе целевой строки. Вот пример:
from fuzzywuzzy import fuzz, process
choices = ["apple", "banana", "orange", "pineapple"]
target = "appl"
best_matches = process.extract(target, choices, limit=2)
print(best_matches) # Output: [('apple', 90), ('pineapple', 53)]
Как я использовал это в своем проекте?
Во время моего проекта прогнозирования цен на недвижимость в Бангалоре я столкнулся с общей проблемой объединения названий мест с небольшими вариациями написания. Чтобы упростить эту задачу, я обратился к алгоритму FuzzyWuzzy, мощному методу сопоставления строк. Используя функцию token_sort_ratio из библиотеки FuzzyWuzzy, я автоматизировал процесс консолидации, достигнув точных результатов и сэкономив значительное время.
Для реализации алгоритма FuzzyWuzzy я создал пользовательскую функцию с именем Similarity_check_df. Эта функция принимает два списка, основные и второстепенные, представляющие основные и второстепенные имена местоположений. Сравнивая версии этих имен в нижнем регистре с помощью token_sort_ratio, функция вычисляет показатель сходства. Если оценка превышает указанный порог, функция обновляет словарь совпадений с наиболее похожим основным местоположением. Результаты сортируются по частоте и возвращаются в виде консолидированного кадра данных.
Использование FuzzyWuzzy и token_sort_ratio позволило мне эффективно решить проблему повторяющихся названий мест, упростив процесс прогнозирования цен на недвижимость в Бангалоре.
Если вам интересно, ниже приведен код функции:
# Creating a new function using fuzzywuzzy to find out the similarity between the location names
def similarity_check_df(majors, minors, threshold, dataframe_column):
matches = {}
for minor in minors:
for major in majors:
similarity = fuzz.token_sort_ratio(minor.lower(), major.lower())
if similarity >= threshold:
if minor not in matches or similarity > matches[minor][1]:
times = dataframe_column.value_counts()[minor]
matches[minor] = (major, similarity, times)
sorted_matches = sorted(matches.items(), key=lambda x: x[1][2], reverse=True)
results = []
for minor, (major, similarity, times) in sorted_matches:
results.append([minor, major, times, similarity])
df_check = pd.DataFrame(results, columns=['minor_location', 'major_location', 'frequency', 'similarity_score'])
return df_check
Выход:
Не стесняйтесь проверить весь мой проект в моем профиле GitHub, нажав на ссылку ниже
https://github.com/Hariikm/Property-Price-Prediction-ML
Заключение
В заключение отметим, что алгоритм FuzzyWuzzy — это мощный инструмент для поиска похожих строк, даже если они не совсем совпадают. Это помогает нам очищать беспорядочные данные, связывать похожие записи и улучшать такие задачи, как проверка орфографии и подсказки слов. Используя FuzzyWuzzy, мы можем лучше сравнивать и сопоставлять строки в наших проектах программирования. Это полезный инструмент, который любят программисты, специалисты по данным и исследователи, поскольку он упрощает работу с реальными данными. Итак, примите силу пуха и исследуйте его удивительные возможности!
