Soru Büyük dizeler dizisinde benzer dizgiler grupları bulma


Benzerliği ile karakterize bir dizi altgrup olan oldukça geniş bir dizi dizim var (100). Tez gruplarını makul derecede verimli bulabilecek bir algoritma bulmaya / tasarlamaya çalışıyorum.

Örnek olarak, giriş listesi sol tarafta ve çıktı grupları sağda diyelim.

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 

Bunu makul bir şekilde çözmek için herhangi bir yol biliyor mu?

Benzer dizeleri bulmak için standart yöntem, Levenshtein mesafesi gibi görünüyor, ama ben burada her dizeyi diğer dizelerle karşılaştırmak zorunda kalmadan, burada iyi bir şekilde nasıl kullanabileceğimi göremiyorum ve sonra bir şekilde bir fark üzerinde karar veremiyorum. İki dizenin aynı grupta olup olmadığına karar vermek için eşik.

Bir alternatif, dizgileri bir tamsayıya doğru işleyen bir algoritma olacaktır; burada, benzer dizgiler, sayı çizgisinde birbirine yakın olan tamsayılar için karmadır. Bir tane var ise, hangi algoritmanın olacağını hiç bilmiyorum.

Herhangi bir düşünce / işaretçisi var mı?


GÜNCELLEŞTİRME: @Will A: Belki de isimler ilk düşündüğüm kadar iyi bir örnek değildi. Bir başlangıç ​​noktası olarak, çalışacağım verilerde, bir dizedeki küçük bir değişimin, bir gruptan diğerine atlamayacağını varsayabilirim.


36
2017-07-25 13:13


Menşei


Algoritmanızın, her birinin bir öncekinden çok farklı olduğu dizilerle başa çıkmasını nasıl istiyorsun, ama ilki sonuncusuyla çok farklı mı? - Eric
İyi soru. Bir başlangıç ​​noktası olarak, çok fazla endişelenmiyorum çünkü dizilerden oluşan grupların beklediğim verilerde makul olarak farklı olmasını bekliyorum. Ayrıca, gruplandırmaya yardımcı olmak için listedeki her varlık için en az bir başka boyuta (zaten sayısal olan) sahip olacağımı eklemeliyim, bu nedenle dize karşılaştırma kısmı% 100 mükemmel olmak zorunda değildir. - latentflip


Cevaplar:


Bir diğer popüler yöntem dizeleri Jaccard endeksi ile ilişkilendirmektir. İle başla http://en.wikipedia.org/wiki/Jaccard_index.

Sizinki gibi bir sorunu çözmek için Jaccard endeksini (ve diğer birkaç yöntemi) kullanmayla ilgili bir makale:

http://matpalm.com/resemblance/


20
2017-07-25 13:24



Sadece dizeleri bir dizi sözcük olarak ele alırsanız (yani, sözcüklerin sırası ya da önemsizliği önemlidir). Sipariş önemliyse, Levenshtein mesafesi (Roma tarafından belirtildiği gibi) çok daha doğrudur (hesaplamak için çok daha yavaştır). - Dimitris Andreou


Çözmeyi denediğiniz problem tipik clusterization sorun.

Basit bir şekilde başla K-Means algoritma ve elemanlar ve kümeler merkezleri arasındaki mesafeyi hesaplamak için bir fonksiyon olarak Levenshtein mesafesini kullanın.

BTW, Levenshtein mesafe hesaplama algoritması Apache Commons StringUtils'te uygulanmaktadır - StringUtils.getLevenshteinDistance 

K-Means'ın temel problemi, küme sayısını (terimlerinize göre alt gruplar) belirtmenizdir. Yani, 2 seçeneğiniz olacaktır: K-Means'i bazı euristiklerle geliştirin veya küme sayısını belirtmeyi gerektirmeyen başka bir küme algoritması kullanın (ancak bu algoritma daha kötü performans gösterebilir ve uygulamayı uygulamaya karar verirseniz uygulamada çok zor olabilir) kendin).


6
2017-07-25 13:20



"Gruplaşmanın", yapmaya çalıştığım şey için doğru kelime olmadığını biliyordum. Bu bağlantılar da oldukça kullanışlı görünüyor. Teşekkürler! - latentflip


Eğer gerçek telaffuz edilebilir kelimelerden bahsediyorsak, onların (başlangıç) metafon yardım edebilir:

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
2017-07-25 13:37





Verdiğiniz örnekte, Levenshtein mesafesinin "Bonny Smith" in "Jonny Smith" e "çok benzer" olacağı ve neredeyse kesinlikle aynı sınıfta değerlendirileceği için uygun olmayacağını düşünüyorum.

Bence bu isimlere (eğer isimlerle çalışıyorsa), eş anlamlı isimlerden (örn. "John", "Jon", "Jonny", "Johnny" vb.) Bakış açılarına ve bunlara göre eşleştirmeye ihtiyacınız var. .


1
2017-07-25 13:21



William -> Bill ... Eğer gerçek bir dünya problemiyse, o zaman çözümü hiç de önemsiz değildir ve dilbilimde ve muhtemelen halihazırda doldurulmuş DB'lerde bazı araştırmalar yapılmasını gerektirir. - Roman


Böyle bir problemi çözdüm, her şeyden önce metni normalleştirdim ve InC gibi tüm dizgeye değer dizgesinden çıktım. ABD’nin ...

Bu belirsiz kelimeler sizin tarafınızdan tanımlanmalıdır.

Normalleştikten sonra Jaro Winkler mesafesini kullanarak isimlere göre bir inceleme yürütüyorum ve sonuçları benzer nesnelerin bir listesiyle bir nesnede yuvarladım.

Gerçekten iyiydi.

Bunu java'da 30 bin kişilik isimle çalıştırdım.

Umarım bu fikir bir diğeri için faydalı olacaktır.


1
2017-09-01 23:14





İşte bir Levenshtein fonksiyonu için SQL kodu:

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

-2
2018-02-03 04:52