encontrar grupos de cadenas similares en un amplio conjunto de cadenas

Question

que tienen un razonablemente grande conjunto de cadenas (por ejemplo 100) que tiene una serie de subgrupos caracterizados por su similitud. Estoy tratando de encontrar/diseñar un algoritmo que encuentre esos grupos razonablemente eficiente.

A modo de ejemplo digamos que la lista de entrada está a la izquierda abajo, y los grupos de salida están a la derecha.

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 

¿Alguien sabe de alguna manera de resolver esto razonablemente eficiente?

El método estándar para encontrar cadenas similares parece ser la distancia de Levenshtein, pero no veo cómo puedo hacer un buen uso de eso aquí sin tener que comparar cada cadena con cada cadena de la lista, y de alguna manera decidir sobre un umbral de diferencia para decidir si las dos cadenas están en el mismo grupo o no.

Una alternativa sería un algoritmo que hashes cuerdas hacia abajo para un número entero, donde cadenas similares hash para números enteros que están muy juntos en la línea de número. No tengo ni idea de qué algoritmo que sería, sin embargo, incluso si uno existe

¿Alguien tiene alguna idea/punteros?

---

ACTUALIZACIÓN: @Will R: Tal vez los nombres no eran un ejemplo tan bueno como pensé por primera vez. Como punto de partida, creo que puedo suponer que en los datos con los que trabajaré, un pequeño cambio en una cadena no hará que salte de un grupo a otro.

Answer 1

Otro método popular es asociar las cuerdas por su índice de Jaccard. Comience con http://en.wikipedia.org/wiki/Jaccard_index.

Aquí hay un artículo sobre el uso del Jaccard-índice (y un par de otros métodos) para resolver un problema como la suya:

http://matpalm.com/resemblance/

Answer 2

El problema que estamos tratando de resolver es un problema típico clusterization.

Comience con el algoritmo simple K-Means y use la distancia Levenshtein como una función para calcular la distancia entre los elementos y los centros de clusters.

Por cierto, el algoritmo de cálculo de la distancia Levenshtein se implementa en Apache Commons StringUtils - StringUtils.getLevenshteinDistance

El principal problema de K-medias es que se debe especificar el número de grupos (subgrupos en sus términos). Por lo tanto, tendrá 2 opciones: mejorar K-Means con algún euristic o usar otro algoritmo de clusterización que no requiera especificar el número de clusters (pero ese algoritmo puede mostrar un peor rendimiento y puede ser muy difícil en la implementación si decide implementarlo) tú mismo).

Answer 3

Por el ejemplo que das, creo que la distancia de Levenshtein sería inadecuada, ya que "Bonny Smith" sería "muy similar" a "Jonny Smith" y casi con seguridad terminaría siendo considerado en la misma clase.

Creo que necesita acercarse a esto (si trabaja con nombres) desde el punto de vista de ciertos nombres que tienen sinónimos (por ejemplo, "John", "Jon", "Jonny", "Johnny", etc.) y coincidencia basada en estos.

Answer 4

Si estamos hablando de palabras pronunciables reales, comparando la (inicio de) su metaphone podría ser de ayuda:

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 5

Aquí está el código SQL para una función 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, @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 

Answer 6

He resuelto un problema como ese, antes que nada normalicé el texto, y salgo de las palabras de cadena sin valor para toda la cadena, como InC. DE EE.UU. ...

Estas palabras no válidas deben ser definidas por usted.

Después de normalizar corro una inspección por nombres utilizando la distancia Jaro Winkler, y busqué a tientas los resultados en un objeto con una lista de objetos similares.

Fue realmente bueno.

me corrieron esto en Java en un 30K nombres de las personas

espero que esta idea va a ser útil para alguien