Stemming

Según la wikipedia Stemming es un método para reducir una palabra a su raíz o (en inglés) a un stem o lema. Hay algunos algoritmos de stemming que ayudan en sistemas de recuperación de información. Stemming aumenta el recall que es una medida sobre el número de documentos que se pueden encontrar con una consulta. Por ejemplo una consulta sobre bibliotecas también encuentra documentos en los que solo aparezca bibliotecario porque el stem de las dos palabras es bibliotec. Mas información en la Wikipedia.

Lematización

Existe otro método llamado Lematización que se diferencia del Stemming en que dada una forma flexionada (es decir, en plural, en femenino, conjugada, etc), halla el lema que por convenio se acepta como representante de todas las formas flexionadas de una misma palabra. Es decir, el lema de una palabra es la palabra que nos encontraríamos como entrada en un diccionario tradicional: singular para sustantivos, masculino singular para adjetivos, infinitivo para verbos. Por ejemplo, decir es el lema de dije, pero también de diré o dijéramos; guapo es el lema de guapas; mesa es el lema de mesas. Mas información en la Wikipedia.

Implementación de Stemming en Python

Es posible realizar Stemming mediante un algoritmo que use reglas gramaticales de derivación morfológica para el idioma en cuestión, o bien usando un diccionario informatizado que asocie a cada forma su lema (palabra) representante. Para el primera solución Snowball (Github) es un pequeño lenguaje de procesamiento implementado en ANSI C para la creación y uso de algoritmos de stemming. Después disponemos de PyStemmer (Github) que es un wrapper de Snowball para python.

Instala PyStemmer con Pip

pip install pystemmer

Nota: Si durante la instalación de PyStemmer se produce un error de este estilo es porque PyStemmer necesita un compilador de C++ para Python. Sigue las instrucciones :

error: Microsoft Visual C++ 9.0 is required (Unable to find vcvarsall.bat). 
Get it from http://aka.ms/vcpython27

Test:

# idiomas disponibles
>>> import Stemmer
>>> print(Stemmer.algorithms())
[u'danish', u'dutch', u'english', u'finnish', u'french', u'german', u'hungarian',
 u'italian', u'norwegian', u'porter', u'portuguese', u'romanian', u'russian',
 u'spanish', u'swedish', u'turkish']

# stem de la palabra en inglés 'cycling'
>>> import Stemmer
>>> stemmer = Stemmer.Stemmer('english')
>>> print(stemmer.stemWord('cycling'))
cycl

# stem de varias palabras en inglés 
>>> import Stemmer
>>> stemmer = Stemmer.Stemmer('english')
>>> print(stemmer.stemWords(['cycling', 'cyclist']))
['cycl', 'cyclist']

# Permite codificación UTF-8
>>> import Stemmer
>>> stemmer = Stemmer.Stemmer('english')
>>> print(stemmer.stemWords(['cycling', u'cyclist']))
['cycl', u'cyclist']

# Por defecto la caché de palabras es de 10000, pero
# se puede modificar
>>> import Stemmer
>>> print(stemmer.maxCacheSize)
10000
>>> stemmer.maxCacheSize = 1000
>>> print(stemmer.maxCacheSize)
1000

# Otro ejemplo en español
>>> import Stemmer
>>> stemmer = Stemmer.Stemmer('spanish')
>>> print stemmer.stemWords(['camionero','camiones','camion','camionera'])
>>> print stemmer.stemWords(['frutal','frutas','frutivoro','abcde'])
['camioner', 'camion', 'camion', 'camioner']
['frutal', 'frut', 'frutivor', 'abcde']

Ejemplo busqueda por palabra clave

import Stemmer

pelis = {u"La reina de Montana": u"Sierra Nevada Jones llega a Montana con su padre para tomar posesión de unas tierras que han pertenecido a sus familias durante generaciones",
         u"La carpa invisible": u"Historia de una circo familiar Los Magote Pablo el director y maestro de ceremonias su esposa la payasa y acróbata Margarita y sus hijos",
         u"Familia": u"Santiago después de levantarse baja a la cocina donde lo espera su familia para felicitarlo es su cumpleaños"}
keywrd = "familiar"

stemmer = Stemmer.Stemmer('spanish')
lemkw = stemmer.stemWord(keywrd)
print "keyword:", keywrd
print "keyword lem:", lemkw
print
for peli in pelis:
    lems = stemmer.stemWords(pelis[peli].split())
    print "title:",
    print "argument", pelis[peli]
    print "argument lem:", lems
    if lemkw in lems:
        print "keyword lem", lemkw, "encontrado en argument lem"
    print

Resultado:

keyword: familiar
keyword lem: famili

title: argument Historia de una circo familiar Los Magote Pablo el director y maestro de ceremonias su esposa la payasa y acróbata Margarita y sus hijos
argument lem: [u'Histori', u'de', u'una', u'circ', u'famili', u'Los', u'Magot', u'Pabl', u'el', u'director', u'y', u'maestr', u'de', u'ceremoni', u'su', u'espos', u'la', u'payas', u'y', u'acrobat', u'Margarit', u'y', u'sus', u'hij']
keyword lem famili encontrado en argument lem

title: argument Sierra Nevada Jones llega a Montana con su padre para tomar posesión de unas tierras que han pertenecido a sus familias durante generaciones
argument lem: [u'Sierr', u'Nev', u'Jon', u'lleg', u'a', u'Montan', u'con', u'su', u'padr', u'par', u'tom', u'posesion', u'de', u'unas', u'tierr', u'que', u'han', u'pertenec', u'a', u'sus', u'famili', u'durant', u'gener']
keyword lem famili encontrado en argument lem

title: argument Santiago después de levantarse baja a la cocina donde lo espera su familia para felicitarlo es su cumpleaños
argument lem: [u'Santiag', u'despues', u'de', u'levant', u'baj', u'a', u'la', u'cocin', u'dond', u'lo', u'esper', u'su', u'famili', u'par', u'felicit', u'es', u'su', u'cumplea\xf1']
keyword lem famili encontrado en argument lem

Como se puede apreciar en el ejemplo al buscar por la palabra clave familiar encuentra coincidencias en el argumento de las tres peículas: familiar, familias y familia.

Este es un ejemplo muy simple. Se podria mejorar eliminando previamente las palabras vacias (stop words), ordenar el resultado según número de coincidencias mediante un algoritmo Tf-idf, o un sistema de retroalimentación aportada por el usuario para indicar la relevancia de los resultados como Rocchio y así mejorar las busquedas.

overstemming y understemming

El stemning presenta dos problemas básicos. El overstemming cuando se reduce demasiado se representa con un mismo stem formas que deberían ser representadas con varios stems y el understemming cuando se reduce poco y se obtienen distintas formas para representar unicamente a una.

Un ejemplo

import Stemmer

stemmer = Stemmer.Stemmer('spanish')
lems = stemmer.stemWords(["familiar", "familias", "familia", "familiares",
                          "familiaridad", "familiaridades"])
print lems
lems = stemmer.stemWords(lems)
print lems

Resultado

['famili', 'famili', 'famili', 'familiar', 'familiar', 'familiar']
['famili', 'famili', 'famili', 'famili', 'famili', 'famili']

Del ejemplo vemos que si aplico dos veces stemming, coinciden las seis formas. Si se aplica sólo una vez se produce un efecto de understemming.