Поиск групп похожих строк в большом наборе строк

У меня есть достаточно большой набор строк (скажем, 100), который имеет несколько подгрупп, характеризующихся их сходством. Я пытаюсь найти/разработать алгоритм, который бы нашел эти группы разумно эффективно.

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

Input                           Output
-----------------               -----------------
Jane Doe                        Mr Philip Roberts
Mr Philip Roberts               Phil Roberts     
Foo McBar                       Philip Roberts   
David Jones                     
Phil Roberts                    Foo McBar        
Davey Jones            =>         
John Smith                      David Jones      
Philip Roberts                  Dave Jones       
Dave Jones                      Davey Jones      
Jonny Smith                     
                                Jane Doe         

                                John Smith       
                                Jonny Smith

Кто-нибудь знает какие-либо способы решения этой проблемы эффективно?

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

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

Есть ли у кого-нибудь мысли/указатели?

UPDATE: @Will A: Возможно, имена были не таким хорошим примером, как я думал сначала. В качестве отправной точки я думаю, что могу предположить, что в данных, с которыми я буду работать, небольшое изменение в строке не заставит ее переходить из одной группы в другую.

Ответ 1

Другим популярным методом является привязка строк по индексу Jaccard. Начните с http://en.wikipedia.org/wiki/Jaccard_index.

Вот статья об использовании Jaccard-index (и нескольких других методов) для решения такой проблемы, как ваша:

http://matpalm.com/resemblance/

Ответ 2

Проблема, которую вы пытаетесь решить, является типичной проблемой кластеризации.

Начните с простого алгоритма K-средних и используйте расстояние Левенштейна как функцию для расчета расстояния между элементами и центрами кластеров.

Кстати, алгоритм вычисления расстояния Левенштейна реализован в Apache Commons StringUtils - StringUtils.getLevenshteinDistance

Основная проблема K-Means заключается в том, что вы должны указать количество кластеров (подгрупп в ваших терминах). Таким образом, у вас будет 2 варианта: улучшить K-Means с помощью некоторой эвристики или использовать другой алгоритм кластеризации, который не требует указания номера кластеров (но этот алгоритм может показать худшую производительность и может быть очень трудным в реализации, если вы решите его реализовать) сам).

Ответ 3

Если мы говорим о реальных произносимых словах, сравнение (начало) их metaphone могло бы помочь:

MRFLPRBRTS: Mr Philip Roberts
FLRBRTS: Phil Roberts   
FLPRBRTS: Philip Roberts 
FMKBR: Foo McBar      
TFTJNS: David Jones    
TFJNS: Dave Jones     
TFJNS: Davey Jones    
JNT: Jane Doe       
JNSM0: John Smith     
JNSM0: Jonny Smith

Ответ 4

Для примера, который вы даете, я считаю, что расстояние Левенштейна было бы непригодным, поскольку "Бонни Смит" был бы "очень похож" на "Джонни Смит" и почти наверняка оказался бы в том же классе.

Я думаю, вам нужно подходить к этому (если работает с именами) с точки зрения некоторых имен, имеющих синонимы (например, "Джон", "Джон", "Джонни", "Джонни" и т.д.) и сопоставление на основе этих данных.

Ответ 5

Я решил такую проблему, во-первых, я нормализовал текст и вывел из строки слова без значения для всей строки, как InC. США...

Это ненадлежащие слова должны быть определены вами.

После нормализации я запускаю проверку по именам, используя расстояние Яро Винклера, и сгруппировал результаты в объект со списком похожих объектов.

Это было действительно хорошо.

Я запустил это в Java с именами людей 30K

Я надеюсь, что эта идея будет полезна для кого-то

Ответ 6

Есть решение этой проблемы, задокументированное в java-библиотеке с открытым исходным кодом для нечеткого сопоставления https://github.com/intuit/fuzzy-matcher

Идея состоит в том, чтобы разбить имена в словах (токены) и использовать алгоритм сопоставления текста, чтобы найти сходство в словах (например, Soundex, Jaccard или Lavenshtiein).

Затем используйте оценку, найденную по каждому слову, и усредните оценку по каждому имени.

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

Эта библиотека опирается на эквивалентность и транзитивное свойство алгоритма сопоставления. Где, если "Дэвид" совпадает с "Дейви", подразумевается обратное совпадение, и вам не нужно запускать эти совпадения.

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

Ответ 7

Вот код SQL для функции Levenshtein:

CREATE FUNCTION [Levenshtein](@str_1 nvarchar(4000), @str_2 nvarchar(4000))
RETURNS int
AS

BEGIN
 DECLARE    @str_1_len int
        ,   @str_2_len int
        ,   @str_1_itr int
        ,   @str_2_itr int
        ,   @str_1_char nchar
        ,   @Levenshtein int
        ,   @LD_temp int
        ,   @cv0 varbinary(8000)
        ,   @cv1 varbinary(8000)

SELECT  @str_1_len = LEN(@str_1)
    ,   @str_2_len = LEN(@str_2)
    ,   @cv1 = 0x0000
    ,   @str_2_itr = 1
    ,   @str_1_itr = 1
    ,   @Levenshtein = 0


WHILE @str_2_itr <= @str_2_len

SELECT  @cv1 = @cv1 + CAST(@str_2_itr AS binary(2))
    ,   @str_2_itr = @str_2_itr + 1

WHILE @str_1_itr <= @str_1_len
BEGIN
    SELECT  @str_1_char = SUBSTRING(@str_1, @str_1_itr, 1)
        ,   @Levenshtein = @str_1_itr
        ,   @cv0 = CAST(@str_1_itr AS binary(2))
        ,   @str_2_itr = 1

    WHILE @str_2_itr <= @str_2_len
    BEGIN
        SET @Levenshtein = @Levenshtein + 1
        SET @LD_temp = CAST(SUBSTRING(@cv1, @[email protected]_2_itr-1, 2) AS int) +
        CASE WHEN @str_1_char = SUBSTRING(@str_2, @str_2_itr, 1) THEN 0 ELSE 1 END
        IF @Levenshtein > @LD_temp SET @Levenshtein = @LD_temp
        SET @LD_temp = CAST(SUBSTRING(@cv1, @[email protected]_2_itr+1, 2) AS int)+1
        IF @Levenshtein > @LD_temp SET @Levenshtein = @LD_temp
        SELECT @cv0 = @cv0 + CAST(@Levenshtein AS binary(2)), @str_2_itr = @str_2_itr + 1
    END

SELECT @cv1 = @cv0, @str_1_itr = @str_1_itr + 1
END

RETURN @Levenshtein
END