Tengo el siguiente problema: Tengo una lista muy larga de palabras, posiblemente nombres, apellidos, etc. Necesito agrupar esta lista de palabras, de manera que palabras similares, por ejemplo, palabras con una distancia de edición (Levenshtein) similar, aparezcan en el mismo clúster. Por ejemplo, "algoritmo" y "alogrithm" deberían tener muchas posibilidades de aparecer en el mismo clúster.
Conozco bien los métodos clásicos de clustering no supervisado como el clustering de k-means, el clustering de EM en la literatura de reconocimiento de patrones. El problema es que estos métodos trabajan con puntos que residen en un espacio vectorial. En este caso, tengo a mano palabras de cuerda. Parece que, la cuestión de cómo representar las cadenas en un espacio vectorial numérico y calcular las "medias" de los clusters de cadenas no está suficientemente contestada, según mis esfuerzos de estudio hasta ahora. Un enfoque ingenuo para atacar este problema sería combinar la agrupación k-Means con la distancia Levenshtein, pero la pregunta sigue siendo "¿Cómo representar las "medias" de las cadenas?". Existe un peso llamado como peso TF-IDF, pero parece que está relacionado principalmente con el área de clustering de "documentos de texto", no para el clustering de palabras individuales. Parece que existen algunos algoritmos especiales de agrupación de cadenas, como el de http://pike.psu.edu/cleandb06/papers/CameraReady_120.pdf
Mi búsqueda en esta área continúa, pero quería obtener ideas de aquí también. ¿Qué recomendaríais en este caso, alguien conoce algún método para este tipo de problema?