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

Question

У меня достаточно большой набор строк (скажем, 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: Возможно, имена не были таким хорошим примером, как я сначала подумал. В качестве отправной точки я думаю, что могу предположить, что в данных, с которыми я буду работать, небольшое изменение в строке не заставит ее перейти из одной группы в другую.

Answer 1

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

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

http://matpalm.com/resemblance/

Answer 2

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

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

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

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

Answer 3

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

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

Answer 4

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

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

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

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

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

Надеюсь, эта идея кому-нибудь пригодится

Answer 5

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

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

Answer 6

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

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

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

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

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

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

Answer 7

Вот код SQL для функции Левенштейна:

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, @str_2_itr+@str_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, @str_2_itr+@str_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