Categorización de palabras y valores de categoría

Question

Hoy se estableció un problema de algoritmo en clase, como "si encuentra una solución, no tiene que hacer este tema". ASÍ, por supuesto, todos pensamos que lo intentaríamos.

Básicamente, nos proporcionaron una base de datos de 100 palabras y 10 categorías. No hay coincidencia entre las palabras o las categorías. Así que básicamente es una lista de 100 palabras y 10 categorías.

Tenemos que "colocar" las palabras en la categoría correcta, es decir, tenemos que "descubrir" cómo poner las palabras en la categoría correcta. Por lo tanto, debemos "entender" la palabra, y luego ponerlo en la categoría más adecuada algorthmically.

es decir, una de las palabras es "pescar" la categoría "deporte" -> por lo que entraría en esta categoría. Existe una superposición entre las palabras y las categorías, de tal manera que algunas palabras pueden entrar en más de una categoría.

Si lo resolvemos, tenemos que aumentar el tamaño de la muestra y la persona con el "mejor"% de coincidencia gana.

¿Alguien tiene CUALQUIER idea de cómo comenzar algo como esto? O cualquier recurso? Preferiblemente en C#?

Incluso una palabra clave DB o algo podría ser útil? ¿Alguien sabe de alguno gratis?

Answer 1

Respuesta realmente mala (no demuestra "comprensión") - pero como una puñalada loca puedes pegar google (a través del código) para (por ejemplo) "Pesca + Deporte", "Pesca + Cocina", etc. une cada palabra y categoría) - ¡y deja que Google gane! es decir, la combinación con la mayoría de los "éxitos" recibe elegidos ...

Por ejemplo (resultados): primeros

weather: fish 
sport: ball 
weather: hat 
fashion: trousers 
weather: snowball 
weather: tornado 

Con el código (TODO: añadir ;-P enhebrado):

static void Main() { 
    string[] words = { "fish", "ball", "hat", "trousers", "snowball","tornado" }; 
    string[] categories = { "sport", "fashion", "weather" }; 

    using(WebClient client = new WebClient()){ 
     foreach(string word in words) { 
      var bestCategory = categories.OrderByDescending(
       cat => Rank(client, word, cat)).First(); 
      Console.WriteLine("{0}: {1}", bestCategory, word); 
     } 
    } 
} 

static int Rank(WebClient client, string word, string category) { 
    string s = client.DownloadString("http://www.google.com/search?q=%2B" + 
     Uri.EscapeDataString(word) + "+%2B" + 
     Uri.EscapeDataString(category)); 
    var match = Regex.Match(s, @"of about \<b\>([0-9,]+)\</b\>"); 
    int rank = match.Success ? int.Parse(match.Groups[1].Value, NumberStyles.Any) : 0; 
    Debug.WriteLine(string.Format("\t{0}/{1} : {2}", word, category, rank)); 
    return rank; 
} 

Answer 2

Supongo que el problema permite el uso de datos externos, porque de lo contrario no puedo concebir una forma de deducir el significado de las palabras de forma algorítmica.

Tal vez se podría hacer algo con una base de datos de sinónimos, y buscando distancias mínimas entre las palabras 'palabra' y 'categoría'.

Answer 3

Lo primero que pensé fue aprovechar los datos externos. Escriba un programa que google-búsquedas de cada palabra, y toma la "categoría" que aparece primero/más alto en los resultados de búsqueda :)

Eso podría considerarse una trampa, sin embargo.

Answer 4

Podría hacer un algoritmo personalizado para trabajar específicamente en esos datos, por ejemplo, las palabras que terminan en 'ing' son verbos (participio presente) y podrían ser deportes.

Cree un conjunto de reglas de categorización como la anterior y vea qué tan alta es la precisión que obtiene.

EDIT:

robar el base de datos de Wikipedia (que es libre de todos modos) y obtener la lista de artículos en cada uno de sus diez categorías. Cuente las ocurrencias de cada una de sus 100 palabras en todos los artículos de cada categoría, y la categoría con la mayor "densidad de palabras clave" de esa palabra (por ejemplo, pesca) gana.

Answer 5

Antes que nada necesitas texto de muestra para analizar, para obtener la relación de las palabras. Una categorización con latent semantic analysis se describe en Latent Semantic Analysis approaches to categorization.

Un enfoque diferente sería la categorización de texto ingenua de bayes. Se necesita texto de muestra con la categoría asignada. En un paso de aprendizaje, el programa aprende las diferentes categorías y la probabilidad de que una palabra ocurra en un texto asignado a una categoría, ver bayes spam filtering. No sé qué tan bien funciona con palabras sueltas.

Answer 6

Parece que podría usar algún tipo de clasificación Bayesiana como se usa en spam filtering. Pero esto aún requeriría "datos externos" en forma de algún tipo de base de texto que proporcione contexto.

Sin eso, el problema es imposible de resolver. No es un problema de algoritmo, es un problema de IA. Pero incluso AI (y la inteligencia natural también, para el caso) necesita algún tipo de información para aprender.

Sospecho que el profesor te está dando un problema imposible para hacerte entender en qué diferentes niveles puedes pensar sobre un problema.

La pregunta clave aquí es: ¿quién decide qué clasificación es "correcta"? ¿En qué se basa esta decisión? ¿Cómo podría reproducirse esta decisión programáticamente y qué datos de entrada necesitaría?

Answer 7

Fire this teacher.

La única solución a este problema es ya tener la solución al problema. Es decir. necesita una tabla de palabras clave y categorías para construir su código que coloque palabras clave en categorías.

A menos que, como sugiera, agregue un sistema que "entiende" el inglés. Esta es la persona sentada frente a la computadora o un sistema experto.

Si está construyendo un sistema experto y ni siquiera lo sabe, el profesor no es bueno para dar problemas.

Answer 8

Google está prohibido, pero tienen casi una solución perfecta - Google Sets.

Porque necesita entender la semántica de las palabras que necesita fuentes de datos externas. Puede intentar usar WordNet. O quizás podría intentar usar Wikipedia - encuentre la página para cada palabra (o tal vez solo para las categorías) y busque otras palabras que aparezcan en la página o en las páginas vinculadas.

Answer 9

Utilice un conjunto de datos grande categorizado ya existente como RCV1 para entrenar a su sistema de elección. Podría hacerlo peor que start reading existing research and benchmarks.

aparte de Google existen otros conjuntos de datos 'enciclopédicos" se puede construir de, algunas de ellas organizadas como conjuntos de datos públicos en Amazon Web Services, como una instantánea completa del idioma Inglés Wikipedia.

ser creativo. No es otros datos, además de Google.

Answer 10

Bueno, no puedes usar Google, pero puedes usar Yahoo, Ask, Bing, Ding, Dong, Kong ... Haría algunos pases. Primero consulta los 100. palabras contra 2-3 motores de búsqueda, tomar los primeros artículos resultantes (y es un umbral para experimentar con. 5 es un buen comienzo, creo) y escanear el texto. En particular, buscaré las 10 categorías.Si una categoría aparece más de x tiempo (x nuevamente es un umbral con el que debe experimentar) es una coincidencia. En función de ese umbral x (es decir, cuántas veces aparece una categoría en el texto) y cómo puede aparecer entre las páginas y superiores en usted, puede asignar un peso a un par palabra-categoría. para una mejor precisión, puede hacer otro pase con los motores de búsqueda que no sean de Google con el par palabra-categoría (con una relación AND) y aplicar el número de páginas resultantes al peso de ese par. Simplemente asumen que el par de palabra-categoría con mayor peso es el correcto (suponiendo que incluso tendrá más de una opción). También puede asignar varias palabras a una categoría múltiple si las ponderaciones están lo suficientemente cerca (tal vez el umbral z). Basado en eso, puede introducir cualquier cantidad de palabras y cualquier cantidad de categorías. Y ganarás tu desafío. También creo que este método es bueno para evaluar el peso de AdWords potenciales en la publicidad. pero eso es otro tema ....

Buena suerte

Harel

Answer 11

uso (ya sea en línea o descargar) WordNet, y encontrar el número de relaciones que tiene que seguir entre las palabras y cada categoría.

Answer 12

Mi enfoque ingenuo:

1. Crear un archivo de texto grande como this (read the article for inspiration)
2. Para cada palabra, escanear el texto y cada vez que coinciden con esa palabra, contar las 'categorías' que aparecen en N (máximo, aka radio) posiciones izquierda y derecha de la misma.
3. Es probable que la palabra pertenezca a la categoría con el mejor contador.

Answer 13

Mi intento sería utilizar el conjunto de herramientas de CRM114 para proporcionar una forma de analizar un gran corpus de texto. Entonces puede utilizar las coincidencias para dar una suposición.

Answer 14

Parece que tiene un par de opciones aquí, pero en su mayor parte, creo que si quiere datos precisos, necesitará usar alguna ayuda externa. Dos opciones que puedo pensar serían hacer uso de una búsqueda de diccionario, o crowdsourcing.

En lo que respecta a una búsqueda de diccionario, puede ir a la base de datos, consultarla y analizar los resultados para ver si uno de los nombres de categoría se muestra en la página. Por ejemplo, si busca "red", encontrará "color" en la página y, de la misma manera, buscar "fishing" devuelve "deporte" en la página.

Otro, un poco más fuera de la caja de opción sería hacer uso de multitud de abastecimiento, considere lo siguiente:

1. principio en más o menos al azar la asignación de pares de nombre y valor.
2. Muestra los resultados.
3. Cargue los resultados en Amazon Mechanical Turk (AMT) para obtener comentarios de los seres humanos sobre el funcionamiento de los pares.
4. Ingrese los resultados de la evaluación AMT nuevamente en el sistema junto con las asignaciones aleatorias.
5. Si todo fue aprobado, entonces terminamos.
6. De lo contrario, conserve las visitas correctas y trátelas para ver si se puede establecer algún patrón, genere un nuevo conjunto de pares nombre-valor.
7. Volver al paso 3.

Concedido esto implicaría alguna desembolso económico, pero también podría ser una de las versiones más simples y precisos de los datos que se va obtener de forma bastante fácil.

Answer 15

Sí, me gustaría el enfoque de wordnet. Consulte este tutorial en WordNet-based semantic similarity measurement. Puede consultar Wordnet en línea en princeton.edu (google it) por lo que debería ser relativamente fácil codificar una solución para su problema. Espero que esto ayude,

X.

Answer 16

Tal vez usted está haciendo todo esto demasiado duro.

Obviamente, necesita una referencia externa de algún tipo para clasificar la probabilidad de que X esté en la categoría Y. ¿Es posible que esté probando su pensamiento "fuera de la caja" y que USTED podría ser la referencia externa? Es decir, el algoritmo es una simple cuestión de recorrer cada categoría y cada palabra y preguntarle a USTED (o a quien se sienta en la terminal) si la palabra X está en la categoría Y mostrada. Hay algunas variaciones simples sobre este tema, pero todas ellas Implica pasar el nudo gordiano simplemente cortándolo.

O no ... depende del maestro.

Answer 17

Raspe delicious.com y la búsqueda de cada palabra, mirando a la etiqueta cuenta colectivas, etc.

No hay mucho más que pueda decir acerca de eso, pero delicioso es viejo, enorme, muy-muy marcados y contiene una gran cantidad de la información semántica actual relevante de la cual extraer. Sería muy fácil construir una base de datos semántica de esta manera, utilizando su lista de palabras como base de raspado.

El conocimiento está en las etiquetas.

Answer 18

Como no necesitas asistir al tema cuando resuelves este 'enigma' no se supone que sea fácil, creo. Sin embargo me gustaría hacer algo como esto (dicho de una manera muy simplista)

construir una red neuronal que le dan una cierta entrada (a e) libro (, algunos (e) los libros) => ningún Google necesita

esta red clasifica las palabras (las redes neuronales son excelentes para la clasificación 'insegura'). Creo que simplemente puede saber qué palabra pertenece a cada categoría debido a las ocurrencias en el texto. (es probable que se mencione "pesca" cerca de "deportes"). Después de un poco de entrenamiento de la red neuronal, debe "vincular" las palabras a las categorías.

Answer 19

Problema interesante. Lo que estás viendo es clasificación de palabras. Si bien puede aprender y utilizar métodos tradicionales de recuperación de información como LSA y la categorización basada en eso, no estoy seguro si esa es su intención (si es así, ¡por favor! :)

Como usted dice puede usar datos externos, sugiero usar wordnet y su enlace entre palabras. Por ejemplo, usando wordnet,

# S: (n) **fishing**, sportfishing (the act of someone who fishes as a diversion) 
* direct hypernym/inherited hypernym/sister term 
     o S: (n) **outdoor sport, field sport** (a sport that is played outdoors) 
     + direct hypernym/inherited hypernym/sister term 
      # S: (n) **sport**, athletics 
      (an active diversion requiring physical exertion and competition) 

Lo que vemos aquí es una lista de relaciones entre palabras. El término pesca se relaciona con deporte al aire libre, que se relaciona con deporte.

Ahora, si obtiene la deriva - es posible utilizar esta relación para calcular una probabilidad de clasificar "pesca" a "deporte", por ejemplo, en función de la distancia lineal de la palabra cadena, o el número de apariciones , et al. (Debería ser trivial encontrar recursos sobre cómo construir medidas de similitud usando wordnet. Cuando el prof dice "no usar google", supongo que quiere decir programáticamente y no como un medio para obtener información para leer)

en cuanto a C# con wordnet - ¿qué tal http://opensource.ebswift.com/WordNet.Net/

Answer 20

Usted puede ser capaz de poner utilizar la base de datos de WordNet, crear una cierta métrica para determinar cuán estrechamente vinculado dos palabras (la palabra y la categoría) son y luego elegir el mejor categoría para poner la palabra en.

Answer 21

Puede implementar un algoritmo de aprendizaje para hacer esto usando un método monte carlo y comentarios humanos. Haga que el sistema categorice aleatoriamente las palabras, luego solicite que las vote como "coincidencia" o "no coincidencia". Si coincide, la palabra se categoriza y se puede eliminar. De lo contrario, el sistema lo excluye de esa categoría en futuras versiones, ya que sabe que no pertenece allí. Esto obtendrá resultados muy precisos.

Esto funcionará para el problema de 100 palabras con bastante facilidad. Para el problema más grande, puede combinar esto con conjeturas educadas para que el proceso funcione más rápido. Aquí, como muchas personas mencionadas anteriormente, necesitarán fuentes externas. El método de google probablemente funcione mejor, ya que Google ya ha trabajado mucho, pero, salvo eso, puedes, por ejemplo, extraer datos de tu cuenta de Facebook usando las API de Facebook y tratar de averiguar qué palabras son estadísticamente más probables. para aparecer con palabras previamente categorizadas.

De cualquier manera, sin embargo, esto no se puede hacer sin algún tipo de entrada externa que en algún momento proviene de un ser humano. A menos que quiera ser descarado y, por ejemplo, defina las categorías por algún valor serializado contenido en el texto ascii para el nombre: P