python - tablas - Encontrar la combinación "mejor" para un conjunto

pandas python tutorial español pdf

Question

Tengo un conjunto, sentences , que contiene oraciones del idioma inglés en forma de cadenas. Deseo crear un subconjunto de sentences , sentences2 , que contiene oraciones que contienen solo 20 palabras únicas. Por supuesto, hay muchos, muchos subconjuntos de este tipo, pero estoy buscando el "mejor" y por "mejor" me refiero a ese subconjunto donde todas las palabras tienen la mayor representación posible en sentences2 .

El siguiente ejemplo, aclarará aún más lo que quiero decir con "mejor":

Si tuviera que filtrar sentences para este conjunto de palabras:

(i,you,do,think,yes,dont,can,it,good,cant,but,am,why,where,now,no,know,here,feel,are)

Me gustaría obtener lo siguiente:

sentences2 = set(("where are you now", "here i am", "can you do it", "yes i can", "but can i do it", "no you cant", "do you feel good", "yes i do", "why are you here", "i dont know", "i think i know why", "you dont think", "yes i do", "no you dont", "i dont think you think", "i feel good", "but i am good", "i cant do it now", "yes you can", "but i cant", "where do you think i am"))

y aquí cada palabra se representa al menos dos veces, como podemos ver si usamos un contador en las oraciones2:

c = collections.Counter({''i'': 13, ''you'': 10, ''do'': 6, ''think'': 5, ''dont'': 4, ''can'': 4, ''good'': 3, ''but'': 3, ''am'': 3, ''it'': 3, ''cant'': 3, ''yes'': 3, ''know'': 2, ''no'': 2, ''here'': 2, ''why'': 2, ''feel'': 2, ''are'': 2, ''now'': 2, ''where'': 2})

Si cada palabra está representada al menos dos veces, podemos decir que este conjunto de 20 palabras tiene una puntuación de 2.

score = min(c.values())

Sin embargo, el siguiente conjunto:

(i,you,he,do,think,yes,dont,can,it,good,cant,but,am,why,where,now,no,here,she,are)

tiene un puntaje de 5, ya que si lo uso para filtrar sentences , obtengo una sentences2 donde cada palabra se representa al menos cinco veces.

Así que busco la puntuación más alta posible para todas las combinaciones posibles de 20 palabras.

Aquí está mi intento de resolver este problema:

sentences = ... # all the sentences in my text
common_words = ... # the hundred most common words in the text
result_size = 20

highest_score = 0
for sample in itertools.combinations(common_words, result_size):

    sentences2 = list(filter(lambda s: set(s).issubset(sample), sentences))
    c = Counter([j for i in sentences2 for j in i])

    if len(c.values()) and min(c.values()) > highest_score:
        # this is the set with the highest score to date
        print(c)
        highest_score = min(c.values())

Sin embargo, este algoritmo tardará una eternidad en calcularse, con 5.3598337040381E + 20 combinaciones si no me equivoco. ¿Puede sugerirme cómo podría resolver esto con un algoritmo mucho más rápido?

Tenga en cuenta que el conjunto resultante puede contener menos de 20 palabras y que esto es completamente correcto. Por ejemplo, c.values() en mi algoritmo no tiene que coincidir con el tamaño de result_size .

También tenga en cuenta que estoy esperando que las palabras del conjunto resultante se encuentren entre las cien palabras principales ( common_words contiene 100 valores). Esto también es por diseño.

Answer 1

Buscaría una forma de agrupación de datos para acelerar la búsqueda en cada prueba de 20 palabras.

Los datos que importan son las palabras únicas en una oración.

2 oraciones se pueden considerar cercanas si la distancia del jaccard es pequeña. La distancia jaccard es 1 - (tamaño de (intersección de palabras en oraciones)) / (tamaño de (unión de palabras en oraciones)).

Debido a que la distancia jaccard es métrica (cumple con la desigualdad de triángulos), se puede construir un índice de m-tree que permita encontrar más rápidamente las oraciones.

A partir de esta base puede producirse la agrupación (los mejores resultados estarán cerca uno del otro).

Finalmente, mediante la iteración de cada oración y la búsqueda de los K vecinos más cercanos, puede encontrar un conjunto de hasta 20 palabras que podrían usarse. Esto le dará un valor diferente a K (oraciones que comparten las mejores 20 palabras).

Probablemente usaría una base de datos para apoyar esta select union select intersection y la select intersection permitiendo la configuración de pruebas

Answer 2

Le sugiero que pruebe el enfoque a continuación. No tengo ninguna prueba matemática de que produzca la "puntuación" absolutamente mejor, o incluso alguna otra "medida de bondad", pero creo que puede ayudarlo, a menos que, por supuesto, el caso requiera que realmente pruebe y encuentre el absolutamente mejor

No hablo python, pero la estrategia y la consiguiente implementación son lo suficientemente simples como para no requerir siquiera un pseudocódigo para explicar. Sin embargo, usaré unas pocas palabras, no porque sea muy complicado, sino para ser claro (espero).

Necesitará un método para diagonalizar una matriz, o al menos para encontrar el vector propio correspondiente al valor propio más grande. No todos los idiomas proporcionan de forma nativa un método para eso. En C ++ puedes usar la librería Eigen. En C #, que solía probar, conecté MathNet. En python, no tengo ni idea. Los requisitos para la instalación de diagonalización / vector propio son limitados: la matriz es siempre real, simétrica, todos los elementos son positivos. Sin embargo, aunque los elementos diagonales son al menos tan grandes como cualquier otro en su fila / columna, la matriz ciertamente no es "diagonal-dominante".

El problema que presentas puede, en abstracto, formularse para enteros, no palabras, lo que lo hace más conveniente (para mí ...) formular e implementar (pero, por lo demás, es bastante irrelevante). De hecho, solo necesitamos sus "palabras comunes", por lo tanto 100 enteros [0..99], y usted configura una vez el mapa entre palabras y enteros simplemente colocando las palabras en una matriz o lista y usando su índice.

Como nota al margen: es probable que la estrategia sea (mucho) más adecuada para su aplicación de idioma que para un problema completamente generalizado con enteros en los que podría construir una entrada difícil "maliciosamente". La razón es que esencialmente explotaremos las correlaciones por pares, si las hay, entre los elementos (palabras dentro de la misma oración), mientras que las correlaciones predominantemente fuertes para triples, cuádruples, ... podrían hacerlo menos eficiente (pero Haré algo por los triples). Obviamente, en un lenguaje bien formado esperaría correlaciones: "am" suele aparecer junto con "I", y mientras que "have" puede ser en total más frecuente que "has", tan pronto como encuentre "he "podría ser más probable que también obtenga un" tiene "que" tener "en la misma oración. Y así.

Algunas definiciones están en orden.

NCommon es el número de elementos en tus common_words (ic 100). Las palabras comunes "son" los enteros [0..NCommon-1].

NMaxSet es su límite de problemas (ic 20) el número máximo de ''palabras'' que está dispuesto a usar, finalmente.

F es un filtro: la colección de ''palabras'' que está utilizando para definir qué oraciones se incluyen en alguna colección. Al final, debe haber adaptado su filtro de modo que F.Count no exceda a NMaxSet.

M (N) es una matriz cuadrada de NxN; Los índices de fila y columna están en [0..N-1]

S (F) es la colección de oraciones (de la entrada del problema) que satisfacen un filtro F. Una "oración" es aquí siempre una colección de números enteros en el rango [0..NCommon-1], vea arriba. Las palabras duplicadas en la misma oración son irrelevantes (descripción del problema) y tales duplicaciones se eliminan de nuestras oraciones enteras.

Aquí vamos.

I. Preparación.

Inicialice una matriz MCommon = M (NCommon). Cree el filtro FCommon que contiene todas las palabras comunes.

Filtra la entrada, eliminando palabras duplicadas en oraciones. Esto produce un conjunto de oraciones S0 = S (FCommon), que es su entrada "real": todo lo que es irrelevante se ha eliminado.

Sobre la marcha, mientras acepta oraciones en S0, complete la matriz MCommon: {para (j en oración): para (k en oración): M (j, k) + = 1}. La matriz es simétrica, por lo que puede rellenar el triángulo superior derecho y reflejar al final en el triángulo inferior izquierdo.

Una vez completado el escaneo, M [j, k] es el número de k-ocurrencias en ''oraciones'' que contienen j (y viceversa: la matriz es simétrica). M [k, k] es el recuento total de k en todas las oraciones en S juntas. M es la matriz de correlación (por pares), que le indica la probabilidad de que se produzca una combinación {j, k} en el conjunto de oraciones subyacentes S.

(Siempre, cuando se trata de tales matrices: si al final, hay columnas vacías (y, por tanto, filas): elimine estas columnas y filas, eliminando simultáneamente la entrada correspondiente en el Filtro que subyace a la matriz, como es obvio No juegue un papel. A partir de ahora asumiremos que se ha hecho (a menos que se indique lo contrario), es decir, no hay ninguna columna / fila en la matriz vacía.

II. Calcular el resultado (enfoque principal, refinaremos a continuación):

Calcule el vector propio E de MCommon que corresponde al valor propio más alto: E es una matriz (vector) con coeficientes NCommon.

Establecer NTarget = NSetMax

Determine cuáles son los coeficientes más grandes de NTarget en E. No nos interesan sus valores, sino sus índices. Ponga estos índices juntos: definen un nuevo filtro F (NTarget).

Ejecute S0 a través del nuevo filtro para producir STarget. Cuente todas las apariciones de ''palabra'', encuentre su mínimo: ese es su valor de "calidad de ajuste". Puede hacerlo, por ejemplo, calculando también el MTarget asociado y escaneando los valores diagonales de MTarget [k, k]. Puede parecer que implica un esfuerzo adicional innecesario, ya que también está calculando los elementos fuera de la diagonal, pero veremos que MTarget puede ser útil en los refinamientos de seguimiento.

III. Refinamientos.

A) Necesitamos verificar si eliminando uno o más elementos del filtro F (NsetMax), reduciéndolo a algún NTarget más pequeño que NSetMax, obtendríamos un mejor valor de puntuación. Esto requiere algo de cuidado: es muy posible que la eliminación de DOS (o 3, ...) elementos mejore la puntuación, pero la eliminación de cualquiera de ellos la deteriore.

Tomemos un primer disparo (y bastante razonable) en este problema.

Mientras produce STarget, también llena una nueva matriz MTarget (verá, es útil ...), como hizo con MCommon antes. El tamaño es NTarget. Obtener su eigenvector de mayor valor propio. Determine el coeficiente MÁS PEQUEÑO. Eliminar del filtro el índice correspondiente.

Filtrar de nuevo (como entrada, puede, por supuesto, usar la colección STarget) y calcular la puntuación. Si es mejor: marcar / recordar. En todos los casos (mejora o no) continúe de la misma manera, reduciendo el filtro uno por uno hasta que no quede nada.

B) Uno puede esperar que la razón, como se explica brevemente, para el enfoque "cauteloso" para reducir aún más el filtro debajo de NSetMax, uno a la vez, también se aplique en cierta medida al primer paso donde reducimos F (NCommon) a F (NTarget = NMaxSet) en una gran huelga.

Para dar cabida a esto, podemos ir de NCommon a NMaxSet en pasos. Para no incurrir en una sobrecarga de cómputo, no tomaremos medidas del tamaño 1, sino que cada vez, por ejemplo, se reducirá en un 10% o algo similar.

Entonces, en II arriba, no establezca NTarget inmediatamente en NSetMax, pero (por ejemplo) establezca NTarget = 90. Construya el filtro correspondiente, aplique el filtro a S0, dando S1, produzca también la matriz M1, obtenga su vector propio (el mayor valor propio ). Repetir: establece NTarget = 80, 70, 60 y así sucesivamente. En etapas posteriores, puede volverse aún más cauteloso, reduciendo de 40 a 35 a 30 a 28 a 26 ... En cada paso en que se basa y utiliza los resultados del anterior, para explotar de manera óptima la reducción en tamaño y esfuerzo computacional.

Todo el tiempo que desee controlar si los coeficientes NSetMax (valor final en esta parte del algoritmo) más grandes siempre se producen con los mismos índices o no. Esto proporcionará cierta información sobre si el resultado final es confiable: la estabilidad, o no, del filtro final esperado contra el camino algorítmico hacia él.

C) Considere la situación en la que hemos reducido a NSetMax e investigue si debería reducirse aún más en un enfoque de uno en uno. (Lo mismo puede aplicarse en las etapas finales de (B), si, al acercarse a NSetMax desde arriba, va "uno a la vez" tan pronto como se acerca a NSetMax.)

Supongamos que hay durante esta fase del algoritmo, en su colección (anterior o posterior) de STarget, ciertos PAREJAS de ''palabras'', de modo que eliminar dicho par específico del filtro mejoraría las cosas, mientras que ninguno de sus coeficientes individuales en el vector propio es la más pequeña. No estoy seguro de si esto es posible o no, pero veamos cómo podemos manejarlo. Si (sus) pruebas muestran que es irrelevante, en una implementación final puede eliminar esta característica del algoritmo.

Supongamos que tenemos algunos NTarget, un filtro asociado FTarget y matriz MTarget. (El orden de los elementos (''palabras'') en el filtro siempre es igual (por supuesto) al orden de las filas y columnas en la matriz.)

Desde MTarget podemos deducir directamente alguna información sobre lo que sucedería si elimináramos el elemento j-th del filtro. Por supuesto, la fila j-th y la columna j-th en la matriz se vuelven vacías (todos los cero). Más interesante aún, M [j, k] presenta cuántas veces aparece el elemento k en todas las oraciones que contienen el elemento j juntos. Entonces, cuando eliminamos todo j (al eliminarlo del filtro), sabemos de antemano que en la nueva matriz resultante resultante de MR, el elemento MReduced [k, k] disminuirá precisamente por ese valor M [j, k]. (Por cierto, esto proporciona una forma alternativa de determinar qué elemento eliminar (si opta por eliminar solo uno): el mínimo {j: M [j, j]} es la puntuación del conjunto S asociado, y de M podemos calcular cómo TODOS los elementos diagonales cambiarían al eliminar un elemento j particular, permitiendo una precomputación de la puntuación resultante)

Aquí, sin embargo, nos gustaría saber cómo se vería afectado el puntaje al eliminar algunos PARES de elementos, j y k. Ahora necesitamos determinar cómo se afecta M [p, p] para todos los p que no son j o k. Esto, no puede calcular directamente desde M: eliminar j afecta a la fila k y si bien sabemos cómo cambia [kk], y cualquier otro [p, p], no sabemos cómo cambiaría [k, p], que es necesario para calcular cómo ALSO (''posteriormente'') eliminar k cambiará [p, p]. Tenga en cuenta, por cierto, que debe ser irrelevante para el resultado final, ya sea que elimine primero jy luego k o viceversa, o ambos simultáneamente.

Para esto necesitamos algún tipo de ''derivado''. Afortunadamente, podemos calcular y procesar eso sin demasiado esfuerzo computacional (dado que NTarget ya es bastante pequeño, aproximadamente 20).

Considere un ''filtro de reducción'' G (F; j) relacionado con el filtro F actual, definido simplemente como procesamiento F pero ignorando el elemento j. Con G calculamos, de la misma manera que siempre, una ''matriz de reducción'' N (G), donde por conveniencia en la discusión (y la implementación) mantenemos el mismo tamaño (sin eliminar la columna / fila vacía). Por supuesto, en dicha matriz N, la fila j-th y la columna j-th están vacías. Sus elementos diagonales tendrán valores como se explicó anteriormente (podríamos haberlos calculado desde M directamente). Sin embargo, ahora también tenemos todos los elementos fuera de la diagonal que resultan de la eliminación de j.

Desde N (G {F; j}) ahora podemos determinar qué pasaría si eliminamos TAMBIÉN el artículo k, vea la explicación anterior sobre cómo obtener la puntuación esperada de una matriz actual. Por lo tanto, esto permite calcular la puntuación al eliminar el par {j, k}.

Si el tamaño del conjunto es 20, tenemos que calcular 20 N (G (F; j)) matrices, un esfuerzo relativamente pequeño, supongo (su colección de oraciones también será ahora mucho más pequeña que originalmente). Luego, teniendo todos los N, calcule para cada uno de los 20 * 19/2 pares únicos las puntuaciones de remoción de pares resultantes y estará en la posición de elegir qué PAR (en lugar del elemento individual) eliminar de un filtro. Puede comparar eso, sobre la marcha, contra la reducción por ''uno a la vez'' y tomar las decisiones apropiadas sobre cómo reducir sistemáticamente el filtro en busca de una mejor puntuación. Hay muchas maneras de hacer esta comparación. Una relativamente simple sería: calcular una reducción a partir de un par primero y luego de uno solo (en total 3 elementos). Compare contra primero eliminando uno solo y luego un par. Elija el mejor de estos dos, pero realice desde esa elección solo el primer paso (ya sea uno o dos) y repita el procedimiento.

Tenga en cuenta que al usar estos filtros "derivados" G, las matrices N y los cálculos previos de puntuación que se explican, usted trae efectivamente correlaciones entre los TRÍPULOS de los elementos: usted determina qué sucede para todos {j, k, p} con la frecuencia de p en quitando tanto j como k. Esta idea puede, por supuesto, extenderse para incorporar cuádruples y más allá, pero (a) no creo que prácticamente ayude mucho, y (b) cuanto más avance en este camino, más rápido aumentará el esfuerzo computacional. . Incluso dudo que traer los "triples" como se explica aquí sea relevante, pero no soy un experto en idiomas y, aparte de un pequeño esfuerzo de programación adicional, no hay inconveniente importante.

D) La columna vertebral de la estrategia se basa en el vector propio con el valor propio más grande para señalar los elementos relevantes para filtrar posteriormente. Por supuesto, puede suceder que dos o más valores propios sean "casi" iguales y los vectores propios correspondientes puedan apuntar a conjuntos de elementos completamente diferentes al analizar sus componentes más grandes. En ese caso, valdrá la pena "ramificar", es decir, ir con uno de ellos, trabajar hasta el final, y luego rehacer todo con sus competidores y ver si producen un mejor resultado. Aquí surge un problema si encuentra muchas sucursales (en varios puntos del camino hacia una solución). Esto no es probable que ocurra, pero la implementación debe tener alguna estrategia para enfrentarlo de una manera práctica si esto sucede. Le sugiero que primero deje una bifurcación, pero que sí supervise la aparición de valores propios más grandes "competitivos" para emitir una advertencia al usuario. Alternativamente, puede implementar un manejo de dicha ramificación, pero sea muy estricto con respecto a lo que el programa considerará "casi igual", o establezca un límite en cuanto al número de sucursales que se van a investigar (en total), lo que reduce la posibilidad que el tiempo de cómputo se agota.

Tengo que dejarlo aquí (por falta de tiempo ...), espero haber explicado suficientemente la idea, así como algunos detalles y mejoras a tener en cuenta.

No he tenido tiempo de organizar por mí mismo oraciones relevantes de ''lenguaje real'' como información y prueba contra eso. He programado los pasos básicos en C #, probados contra "enteras aleatorias de enteros", con algunos sesgos para forzar que ciertas "palabras" ocurran más a menudo que otras, pero sin preocuparse por las correlaciones entre "palabras" dentro de "oraciones". Los resultados me parecieron bastante razonables, pero no tuve tiempo para analizarlos ampliamente.

Dada la falta de estructura en las secuencias "aleatorias" que he usado como entrada, mientras que se espera que el lenguaje real muestre correlaciones significativas por pares, que la estrategia explota, tengo una gran esperanza de que pueda ser útil para usted para echar un vistazo a

[EDITADO] Nota agregada: en lo anterior he sido ocasionalmente descuidado al hablar de "j", "k" y así sucesivamente. Lamento eso. A veces, "j" se refiere a la entrada j-th de algo (una fila de Matrix, un índice en una lista de filtros), a veces se refiere al VALOR correspondiente en (normalmente) un filtro. Por ejemplo, un filtro puede contener 18 elementos, numerados (índices) 0..17, pero sus VALORES siempre se refieren a la lista de palabras comunes comunes, por lo que pueden ser {3, 15, 29, 30, 31, 40, ... }. Luego, cuando dice "eliminar j del filtro", generalmente significará "eliminar la entrada j-th del filtro (y esa entrada puede tener cualquier valor de [0..NCommon-1]). Al APLICAR un filtro con una oración, compara los VALORES en el filtro con los valores de la oración. Espero que el contexto, en combinación con una comprensión justa de la línea de razonamiento, siempre aclare lo que realmente significa.

[EDITADO: algunos resultados de las pruebas] He ejecutado mi implementación de C #, utilizando el algoritmo anterior (más o menos: la mayoría, pero no todas las mejoras / detalles descritos) para obtener una impresión de lo que produciría.

Para el aporte tomé 4 libros (texto simple) del proyecto Gutenberg. En total (solo) 27k oraciones, 380k palabras (20k diferentes), por lo que es una muestra bastante pequeña.

La lista de palabras comunes según lo determinado a partir de esa entrada comenzó con "the", "of", "y", "to" ... (cuando se clasifica según la frecuencia de aparición en la entrada total).

El algoritmo filtró 14 palabras ("i", "what", "do", "you", "it", "yes", ...) para producir un "set-quality-value" "óptimo" de 8 ( Se encontraron 139 oraciones con solo esas 14 palabras).

Como desconfiaba de la suposición de que solo se usarían 100 "palabras comunes", a priori se me permitieron 500 palabras comunes, en lugar de 100, y entre las palabras que llegaron al filtro final, 4 fueron de frecuencia numerado por encima de 100 ("sí", "saber", "decir", "pensar"): "sí", por ejemplo, fue # 224 en la lista general si tuviera que ordenarlos por ocurrencia en todas las entradas, presumiblemente la base para "palabras comunes".

Answer 3

NP-duro por reducción de CLIQUE (asumiendo que reemplazamos 20 con un parámetro). Dado un gráfico en el que estamos buscando un k-clique, asigne a cada vértice una palabra única, forme la oración de dos palabras correspondiente a cada borde, e intente seleccionar k elija 2 oraciones que incluyan cada palabra k - 1 vez.

Hay que pensar si hay un algoritmo con una complejidad parametrizada razonable.

Answer 4

No estoy seguro de si es posible encontrar la mejor solución en menos de un tiempo exponencial, es posible que el problema no tenga suficiente estructura. Pero aquí hay una heurística para encontrar una solución "buena".

Creo que la forma de hacer esto es comenzar con el conjunto de wordset tiene el tamaño 0, y agregarle palabras una por una de forma "inteligente" con un máximo de 20. Tenga en cuenta que para un conjunto de wordset_n determinado, la puntuación de cada palabra individual puede solo aumenta o permanece igual cuando se agrega una nueva palabra. La única forma en que el conjunto de wordset_(n+1) puede tener una puntuación más baja que el wordset_n de wordset_n es si la palabra (n + 1) reduce el mínimo. Por lo tanto, nos limitamos a agregar solo palabras que incrementen el mínimo o lo mantengan igual (pero vea una explicación a continuación).

Así que para una primera aproximación,

1. Ordena las palabras en common_words por frecuencia en sentences .
2. Agregue las palabras que wordset con mayor frecuencia al wordset palabras hasta que el puntaje sea distinto de cero.
3. Busque el árbol de posibles conjuntos de wordset construidos agregando solo palabras que aumenten o mantengan la puntuación del nodo anterior (máx N = 20). Por lo tanto, una ruta hacia abajo en este árbol será conjunto de wordset_n , conjunto de wordset_(n+1) , conjunto de palabras_ (n + 2) `con cada nodo que consiste en el nodo anterior más una palabra nueva.
4. Elige el nodo de la hoja con la puntuación más alta.

En una segunda aproximación, a) es posible que desee probar varias combinaciones para el paso 2. 100 eligió 3 es 162000, lo cual no está fuera de discusión. b) Además, para el paso 3, puede querer mirar hacia adelante dos pasos, no solo uno, es decir, solo rechazar una palabra para el lugar n + 1 en el conjunto de wordset si, después de todas las posibilidades para la palabra n + 2, la puntuación sigue siendo más bajo que el wordset_n de wordset_n . Esto podría ayudar si hay anti-correlaciones, es decir, es poco probable que una oración corta con un verbo contenga otro. Finalmente, c) si este método aún es computacionalmente prohibitivo, puede restringir aún más la construcción de árboles cerrando ramas donde la (n + 1) th no eleva el puntaje en una cantidad determinada.

Si las distribuciones de las palabras en las sentences son relativamente independientes entre sí, o solo muestran correlaciones positivas, este método puede proporcionarle algo muy parecido al óptimo.

Answer 5

Descargo de responsabilidad: no ha especificado las características de los datos, por lo que mi respuesta asumirá que no es demasiado grande (más de 1,000,000 de oraciones, cada una como máximo de 1,000). Además, la descripción es un poco complicada y es posible que no haya entendido bien el problema.

Solución:
En lugar de centrarse en diferentes combinaciones, ¿por qué no crea un hashMap ( dict en python) para las 100 palabras que usa con mayor frecuencia, luego atraviesa la matriz de frases y para cada palabra en cada oración, aumenta su valor correspondiente (si es ya dentro del dict).
Al final, simplemente ordene este hashMap de acuerdo con el número de ocurrencias (valor) de cada palabra (clave), luego use las 20 más frecuentes.
Complejidad:
Una mirada rápida a los algoritmos, da:
Atravesando N oraciones, atravesando cada una con M palabras, aumentando el valor de hashMap. al final, ordenar una matriz de (palabra, ocurrencias) pares. lo cual es despreciable (el tamaño de hashMap es constante, 100 palabras de uso frecuente) y extrae las primeras 20.
Complejidad de tiempo: O (N * M)
Complejidad de espacio: O (1) (no necesitamos almacenar las oraciones, solo tenemos el hashMap)

Código de muestra:
Aquí hay un codigo psuedo rapido:

word_occur_dict = {#initialized with frequent words as keys, and zero as value for all}
for sentence in sentences:    #for each sentence
    sentence_words = sentence.split(" ")    #construct the word list
    for word in sentence_words:        #for each word
        if word in word_occur_dict:         #if it is a frequent word, increase value
            word_occur_dict[word]++
final_result = sort_dict(word_occur_dict)[:20] #returns list of tuples

Código Python:

import operator

common_words = ["do","think","yes","dont","can","it","good","cant","but","am","why","where","now","no","know","here","feel","are","i","you","he","she"]
common_words_dict = {}
sentences = ["where are you now", "here i am", "can you do it", "yes i can", "but can i do it", "no you cant", "do you feel good", "yes i do", "why are you here", "i dont know", "i think i know why", "you dont think", "yes i do", "no you dont", "i dont think you think", "i feel good", "but i am good", "i cant do it now", "yes you can", "but i cant", "where do you think i am"]

for w in common_words:    #initialize the dict
    common_words_dict[w] = 0    

for sentence in sentences:    #for each sentence
    sentence_words = sentence.split(" ")    #construct the word list
    for word in sentence_words:        #for each word
        if word in common_words_dict:         #if it is a frequent word, increase value
            common_words_dict[word] = common_words_dict[word]+1

sorted_word_dict = sorted(common_words_dict.items(), key=operator.itemgetter(1))

print sorted_word_dict[::-1][:20]

Por cierto, ''él'' y ''ella'' no aparecen en ninguna parte de las oraciones, pero usted dijo que la siguiente combinación de palabras tiene una puntuación de 5

(Yo, tú, él, haz, piensa, sí, no, no puedo, bueno, no puedo, pero soy, por qué, dónde, ahora, no, aquí, ella, están)

He malinterpretado el problema.

Crédito al vencimiento: : ordene un diccionario de Python por valor

Answer 6

El PASO 1 debe ser crear una estructura de datos que tenga solo las palabras en las oraciones que aparecen en common_words . La estructura también puede tener el número de veces que aparece la palabra y un conjunto de números enteros que hacen referencia a las oraciones en que se encuentra la palabra.

counts[..., {
  word:string,
  count:number,
  ids:Set<number>
}, ...]

Algún pseudo código

countsMap = Map()
For i = 0 To sentences.Size - 1
  sentence = sentences[i]
  For Each word in sentence
    If Not countsMap.Contains(word) Then
      countsMap.Add(word, {word:word, count:0, ids:Set()})
    End If
    value = wordMap.Get(word)
    If Not value.ids.Contains(i) Then
      value.Count++
      value.ids.Add(i)
      countsMap[word] = value
    End If
  Next
Next
counts = countsMap.Values

Idealista PASO 2 Si tiene suerte y el tipo de datos de conteos contiene <40 entradas, puede hacer una búsqueda exhaustiva de las combinaciones de C (n, 20) en un tiempo razonable con una sola computadora C (38, 20) ~ = 33billion . Esto implicaría iterar sobre las combinaciones y la intersección de los conjuntos de identificadores juntos, el tamaño final establecido es su puntaje mínimo.

Algún pseudo código

bestScore = 0
bestCombo = null
For Each combo in Combinations(counts, 20)
  score = combo.Reduce((prev, curr) => prev.ids.Intersect(curr.ids)).Size
  If bestScore < score Then
    bestScore = score
    bestCombo = combo
  End If
Next

PASO 2 realista En la mayoría de los casos, sus conteos contendrán más de 40 palabras únicas, en cuyo caso tendrá que conformarse con una mejor estimación / aproximación. Probablemente haría algo como usar el código anterior, pero en lugar de Pick 20 use Pick 2, ordene sus resultados descendiendo por la puntuación y tome 10.

Algún pseudo código

list = []
For Each combo in Combinations(counts, 2)
  score = combo[0].ids.Intersect(combo[1].ids).Size
  list.Add( { score:score, words:[ combo[0].word, combo[1].word ] } )
Next
// sort descending by score
list.Sort((a, b) => b.score - a.score)
// grab the 20 best words
result = Set()
i = 0
While result.Size < 20
  result.Add(list[i].words[0])
  result.Add(list[i].words[1])
  i = i + 1
End While

¿Obtendrás una puntuación final mayor a 1? Estadísticamente, eso dependería de cuántas palabras y oraciones únicas haya, pero probablemente no.

EDITAR Una nota de implementación y corrección. La intersección de los conjuntos de identificadores de oraciones en las que aparecen las palabras te dará una puntuación mínima de menos 1 (cero indexado) . Por ejemplo, "Perro" está en las oraciones 1 y 2; "Gato" está en las oraciones 2 y 3 ";" Rana "está en la oración 4; la intersección de [1,2] / / [2,3] / / [4] = [], pero la puntuación mínima es 1 resultado. Tamaño () + 1. De la misma manera, solo "Perro" y "Gato" [1,2] / / [2,3] = [2] tiene un tamaño establecido de 1, pero la puntuación mínima es 2.