Ranking de tokens usando TF-IDF en C#

En este artículo, vamos a usar TF-IDF (del inglés Term frequency – Inverse document frequenc) para observar la importancia de las palabras (en adelante tokens) en un documento dentro de una colección de documentos. El código es muy simple y hay que tener en cuenta que, para mayor número de documentos, se debe realizar un código mucho más eficiente.

Introducción

Descargar fuentes 1.5MB

Veamos la definición de TF-IDF según wikipedia:

«Tf-idf (del inglés Term frequency – Inverse document frequency), frecuencia de término – frecuencia inversa de documento (o sea, la frecuencia de ocurrencia del término en la colección de documentos), es una medida numérica que expresa cuán relevante es una palabra para un documento en una colección. Esta medida se utiliza a menudo como un factor de ponderación en la recuperación de información y la minería de texto. El valor tf-idf aumenta proporcionalmente al número de veces que una palabra aparece en el documento, pero es compensada por la frecuencia de la palabra en la colección de documentos, lo que permite manejar el hecho de que algunas palabras son generalmente más comunes que otras.

Variaciones del esquema de peso tf-idf son empleadas frecuentemente por los motores de búsqueda como herramienta fundamental para medir la relevancia de un documento dada una consulta del usuario, estableciendo así una ordenación o ranking de los mismos. Tf-idf puede utilizarse exitosamente para el filtrado de las denominadas stop-words (palabras que suelen usarse en casi todos los documentos), en diferentes campos como la clasificación y resumen de texto.

Una de las funciones de ranking más sencillas se calcula como la suma de los valores tf-idf de cada término de la consulta. Muchas funciones de ranking más complejas constituyen variaciones de este simple modelo.»

Comenzamos

La colección de documentos

Para desarrollar el ejemplo, he usado una serie de documentos que definen enfermedades (qué es, causas, síntomas, diagnostico, tratamiento, etc...). Estos datos están guardados en una base de datos MongoDB. La colección MongoDB se llama Documents. En ella, se guarda el título de la enfermedad y una serie de secciones, cada una con su titulo y su texto. En este estudio vamos a trabajar con todo el texto del documento para realizar el ranking de los tokens. Contamos con, aproximadamente, 120 documentos, que no es mucho pero vale para el ejemplo.

Ejemplo de la estructura de un documento

Extracción de los tokens

Vamos a guardar una lista de tokens en base de datos con la siguiente estructura

					
/// <summary>
/// Represents a token in a document
/// </summary>
public class Token
{
	/// <summary>
	/// Document in wich a token apperas
	/// </summary>
	[BsonRepresentation(BsonType.String)]
	[BsonRequired]
	[BsonElement("Document")]
	public string Document { get; set; }

	/// <summary>
	/// Token of a document
	/// </summary>
	[BsonRepresentation(BsonType.String)]
	[BsonRequired]
	[BsonElement("Token")]
	public string Word { get; set; }

	/// <summary>
	/// Number of times the token appears in the document
	/// </summary>
	[BsonRepresentation(BsonType.Int32)]
	[BsonRequired]
	[BsonElement("Count")]
	public int Count { get; set; }

	/// <summary>
	/// NUmber of times the most seen token of the document appears
	/// </summary>
	[BsonRepresentation(BsonType.Int32)]
	[BsonRequired]
	[BsonElement("Max")]
	public int Max { get; set; }

	/// <summary>
	/// Normalized frequency of the token in document (Count / Max)
	/// </summary>
	[BsonRepresentation(BsonType.Double)]
	[BsonRequired]
	[BsonElement("TF")]
	public double TF { get; set; }

	/// <summary>
	/// Total number of documents in the collection
	/// </summary>
	[BsonRepresentation(BsonType.Int32)]
	[BsonRequired]
	[BsonElement("DN")]
	public int DN { get; set; }

	/// <summary>
	/// Number of documents where the token is
	/// </summary>
	[BsonRepresentation(BsonType.Int32)]
	[BsonRequired]
	[BsonElement("CN")]
	public int CN { get; set; }

	/// <summary>
	/// IDF [Log(DN/(1+CN))]
	/// </summary>
	[BsonRepresentation(BsonType.Double)]
	[BsonRequired]
	[BsonElement("IDF")]
	public double IDF { get; set; }

	/// <summary>
	/// TF-IDF value of the token in document [TF*IDF]
	/// </summary>
	[BsonRepresentation(BsonType.Double)]
	[BsonRequired]
	[BsonElement("TFIDF")]
	public double TFIDF { get; set; }
}

Expongo abajo la clase que realiza el proceso.

					
public class Parser
{
	public List<Document> Documents { get; set; }

	public Parser()
	{
		this.Initialize();
	}

	/// <summary>
	/// read all the documents from database
	/// </summary>
	private void Initialize()
	{
		DocumentProvider documentProvider = new DocumentProvider();
		this.Documents = documentProvider.GetAll();
	}

	internal void Execute()
	{
		List<Token> tokenList = new List<Token>();

		//Insert the tokens of documents anr count
		foreach (Document doc in this.Documents)
		{
			foreach (Section secc in doc.Sections)
			{
				List<string> tokens = Generics.ExtractTokens(secc.Text);

				foreach (string word in tokens)
				{
					if (tokenList.Any(x => x.Document == doc.Title && x.Word == word))
					{
						tokenList.First(x => x.Document == doc.Title && x.Word == word).Count++;
					}
					else
					{
						tokenList.Add(new Token()
						{
							Document = doc.Title,
							Word = word,
							Count = 1
						});
					}
				}
			}
		}

		//Save the other properties
		foreach (Token item in tokenList)
		{
			if (item.Max == 0)
			{
				item.Max = (from elto in tokenList
							   where elto.Document == item.Document
							   select elto.Count).Max();
				item.TF = Convert.ToDouble(item.Count) / Convert.ToDouble(item.Max);
			}
			item.DN = tokenList.GroupBy(x => x.Document).Count();
			item.CN = tokenList.Where(x => x.Word == item.Word).Count();
			item.IDF = Convert.ToDouble(Math.Log10(item.DN / (item.CN)));
			item.TFIDF = item.TF * item.IDF;
		}

		//Save in database
		TokenProvider tokenProvider = new TokenProvider();
		tokenList.ForEach(item => tokenProvider.Insert(item));
	}
}

En primer lugar, Obtenemos todos los documentos y lo almacenamos en una lista. El método Execute realiza el procesado.

El primer paso es crear la lista de tokens y rellenarla. Para ello, por cada sección de cada documento extrae todos los tokens y los añade a la lista de tokens o suma una aparición del token.

					
foreach (Document doc in this.Documents)
{
	foreach (Section secc in doc.Sections)
	{
		List<string> tokens = Generics.ExtractTokens(secc.Text);

		foreach (string word in tokens)
		{
			if (tokenList.Any(x => x.Document == doc.Title && x.Word == word))
			{
				tokenList.First(x => x.Document == doc.Title && x.Word == word).Count++;
			}
			else
			{
				tokenList.Add(new Token()
				{
					Document = doc.Title,
					Word = word,
					Count = 1
				});
			}
		}
	}
}

En segundo lugar procesa cada token y añade las propiedades. Por facilitar estudios futuros, se guardan todos los valores en propiedades.
En primer lugar, vamos a realizar la normalización de las apariciones del token dentro del documento. Con ello se evita una predisposición hacia los documentos largos. Para ello vamos a dividir la frecuencia bruta del token por la frecuencia máxima del término que más aparece en el documento:

					
        Count
TF  =  -------
         Max

La frecuencia inversa del documento lo obtenemos dividiendo el número total de documentos por el número de documentos que contienen el término, y se toma el logaritmo de ese cociente:

					
             DN
IDF  =  log ----
             CN

Todo esto se realiza en una segunda vuelta.

					
//Save the other properties
foreach (Token item in tokenList)
{
	if (item.Max == 0)
	{
		item.Max = (from elto in tokenList
					   where elto.Document == item.Document
					   select elto.Count).Max();
		item.TF = Convert.ToDouble(item.Count) / Convert.ToDouble(item.Max);
	}
	item.DN = tokenList.GroupBy(x => x.Document).Count();
	item.CN = tokenList.Where(x => x.Word == item.Word).Count();
	item.IDF = Convert.ToDouble(Math.Log10(item.DN / (item.CN)));
	item.TFIDF = item.TF * item.IDF;
}

Finalmente, guardamos en base de datos

Conclusión

Una vez realizado el proceso, podemos ver un ranking de tokens por cada documento. Con esto, podemos distinguir cuáles son los tokens más descriptivos del documento y cuales son menos. Como se puede ver, Se podrían haber usado stop-words para eliminar palabras comunes o realizar Stemming para trabajar sólo con las raíces de las palabras.

Si usamos un valor de bias para establecer los que mejor describen a cada documento, obtendremos los atributos o tags que describen a cada documento. Este valor de decisión puede ser calculado usando cualquiera de las técnicas de machine learning. Lo importante es que podemos obtener los atributos descriptivos de, por ejemplo, una lista de artículos para una tienda virtual, los cuales pueden ser luegos usados para realizar recomendaciones. O podemos obtener las stop-words para filtros de mail (siempre usando un conjunto de datos adecuado).