Résumons le discours de Donald Trump en trois lignes avec l'algorithme de synthèse automatique LexRank

Ceci est l'article sur le 15ème jour du Calendrier de l'Avent Nextremer 2016.

2016 est presque terminée, mais il y avait aussi beaucoup de nouvelles cette année. La victoire de Donald Trump à l'élection présidentielle n'est-elle pas l'un des événements les plus marquants?

Je le vois souvent à la télévision, mais je n'ai pas bien entendu le discours, alors je vais lire le discours. Cependant, je ne suis pas bon en anglais, alors j'utilise l'algorithme de résumé pour le réduire à environ 3 lignes.

introduction

Il existe deux manières principales de résumer.

Les synthèses génératives sont très difficiles, et la plupart de celles actuellement étudiées sont essentiellement des réserves sélectives. LexRank implémenté cette fois fait également partie du résumé extractif et extrait les phrases importantes de la phrase.

Qu'est-ce que LexRank?

LexRank est un algorithme de synthèse inspiré du PageRank. Le PageRank est un algorithme conçu par les fondateurs de Google L.Page et S.Brin pour déterminer l'importance des pages Web. L'importance de la page a été déterminée en saisissant la structure des liens sur Internet comme le graphique suivant.

Nœud: page Web
Bord: Lien
Importance du nœud:
	1.Les pages liées à de nombreuses pages sont des pages importantes
	2.Les pages liées à des pages importantes sont des pages importantes

Comme le PageRank, LexRank capture également les phrases sous forme de graphique.

Nœud: déclaration
Edge: similitude entre deux phrases(1 | 0)
Importance du nœud:
	1.Les phrases similaires à de nombreuses phrases sont importantes
	2.Les phrases similaires aux phrases importantes sont des phrases importantes

Le degré de similitude ici est simplement combien les deux phrases ont un mot commun.

LexRank n'évalue l'importance que par la structure du graphe, mais lorsqu'il a été inventé en 2004, il se vantait de la meilleure précision dans DUC2004. Il est très intéressant de pouvoir résumer avec une grande précision sans analyse sémantique.

La formule de LexRank est la suivante.

Input:Tableau S composé de n instructions,Seuil de similarité cosinus t
Output:Tableau L contenant les scores LexRank pour chaque phrase

Array CosineMatrix[n][n];
Array Degree[n];
Array L[n];

for i <- 1 to n do
	for j <- 1 to n do
		CosineMatrix[i][j] = idf-modified-cosine(S[i], S[j]);
		if CosineMatrix[i][j] > t then
			CosineMatrix[i][j] = 1;
			Degree[i]++;
		end
		else
			CosineMatrix[i][j] = 0;
		end
	end
end
for i <- 1 to n do
	for j<- 1 to n do
		CosineMatrix[i][j] = CosineMatrix[i][j] / Degree[i]
	end
end

L = PowerMethod(CosineMatrix, n, ε);

return L

(Citation: "LexRank: la centralité lexicale basée sur des graphes comme saillance dans la synthèse de texte" Alogorithme 3)

ʻIdf-modified-cosineest un calcul de similarité entre deux phrases. PowerMethod` est un calcul de PageRank. est.

Maintenant, implémentons cet algorithme en Python.

la mise en oeuvre

import math
import numpy

def lex_rank(sentences, n, t):
	"""
Résumez le texte avec LexRank.
	@param	sentences: list
Phrase([[w1,w2,w3],[w1,w3,w4,w5],..]Liste de phrases comme)
	@param	n: int
Nombre de phrases contenues dans une phrase
	@param	t: float
Seuil de similarité cosinus(default 0.1)
	@return	: list
		LexRank
	"""
    cosine_matrix = numpy.zeros((n, n))
    degrees = numpy.zeros((n,))
    l = []
	
	 # 1.Créer une matrice adjacente
    for i in range(n):
        for j in range(n):
            cosine_matrix[i][j] = idf_modified_cosine(sentences, sentences[i], sentences[j])
            if cosine_matrix[i][j] > t:
                cosine_matrix[i][j] = 1
                degrees[i] += 1
            else:
                cosine_matrix[i][j] = 0

    # 2.Calcul du LexRank
    for i in range(n):
        for j in range(n):
            cosine_matrix[i][j] = cosine_matrix[i][j] / degrees[i]
            
    ratings = power_method(cosine_matrix, n)
    
    return zip(sentences, ratings)

Ce programme est par fonction

  1. Création d'une matrice adjacente
  2. Calcul du LexRank Il est divisé en 2 blocs.

Ici, nous expliquerons chaque bloc.

1. Création d'une matrice adjacente

La matrice adjacente est une matrice de représentation graphique. Le graphe est exprimé en substituant 1 s'il y a une arête entre les nœuds et 0 s'il n'existe pas. Dans LexRank, si la similitude entre deux phrases est égale ou supérieure au seuil t, elles sont reliées par une arête.

La mise en œuvre de la similitude est la suivante.

def idf_modified_cosine(sentences, sentence1, sentence2):
	"""
Calculer la similitude cosinus entre deux phrases
	@param	sentence1: list
Phrase 1([w1,w2,w3]Liste de mots comme)
	@param	sentence2: list
Phrase 2([w1,w2,w3]Liste de mots comme)
	@param	sentences: list
Phrase([[w1,w2,w3],[w1,w3,w4,w5],..]Liste de mots comme)
	@return : float
Similitude cosinus
	"""
    tf1 = compute_tf(sentence1)
    tf2 = compute_tf(sentence2)
    idf_metrics = compute_idf(sentences)
    return cosine_similarity(sentence1, sentence2, tf1, tf2, idf_metrics)

TF est la fréquence d'apparition des mots dans une phrase. (Plus c'est important) IDF est la fréquence d'occurrence des mots dans tout le document. (Moins c'est, plus c'est important) La similarité cosinus est le cosinus de la similitude entre les vecteurs.

Je pense que beaucoup de gens connaissent ces derniers, donc je ne posterai brièvement que la mise en œuvre.

from collection import Counter


def compute_tf(sentence):
	"""
Calculer TF
	@param	sentence: list
Phrase([w1,w2,w3]Liste de mots comme)
	@return : list
Liste TF
	"""
    tf_values = Counter(sentence)
    tf_metrics = {}
    
    max_tf = find_tf_max(tf_values)
    
    for term, tf in tf_values.items():
        tf_metrics[term] = tf / max_tf

    return tf_metrics


def find_tf_max(terms):
	"""
Rechercher la fréquence maximale d'occurrence des mots
	@param	terms: list
Fréquence d'occurrence des mots
	@return : int
Fréquence maximale d'occurrence des mots
	"""
    return max(terms.values()) if terms else 1


def compute_idf(sentences):
	"""
Calculer la valeur IDF d'un mot dans une phrase
	@param sentences: list
Phrase([[w1,w2,w3],[w1,w3,w4,w5],..]Liste de mots comme)
	@return: list
Liste IDF
	"""
    idf_metrics = {}
    sentences_count = len(sentences)

    for sentence in sentences:
        for term in sentence:
            if term not in idf_metrics:
                n_j = sum(1 for s in sentences if term in s)
                idf_metrics[term] = math.log(sentences_count / (1 + n_j))

    return idf_metrics
    
    
def cosine_similarity(sentence1, sentence2, tf1, tf2, idf_metrics):
	"""
Calculer la similitude cosinus
	@param	sentence1: list
Phrase 1([w1,w2,w3]Liste de mots comme)
	@param	sentence2: list
Phrase 2([w1,w2,w3]Liste de mots comme)
	@param	tf1: list
Liste TF de la phrase 1
	@param	tf2: list
Liste TF de la phrase 2
	@param	idf_metrics: list
Liste des phrases IDF
	@return : float
Similitude cosinus
	"""
    unique_words1 = set(sentence1)
    unique_words2 = set(sentence2)
    common_words = unique_words1 & unique_words2

    numerator = sum((tf1[t] * tf2[t] * idf_metrics[t] ** 2) for t in common_words)
    denominator1 = sum((tf1[t] * idf_metrics[t]) ** 2 for t in unique_words1)
    denominator2 = sum((tf2[t] * idf_metrics[t]) ** 2 for t in unique_words2)

    if denominator1 > 0 and denominator2 > 0:
        return numerator / (math.sqrt(denominator1) * math.sqrt(denominator2))
    else:
        return 0.0    

Enfin, si la similitude cosinus est t ou plus, remplacez 1 pour compléter la matrice adjacente.

Ensuite, nous trouverons le LexRank basé sur la matrice créée ici.

2. Calcul du LexRank

À partir de là, LexRank est calculé sur la base de la matrice adjacente obtenue en 1. Tout d'abord, divisez chaque élément de la matrice adjacente par degré (ordre des nœuds) et convertissez-le en matrice de probabilité.

Ensuite, sur la base de cette matrice de probabilité, nous trouverons la distribution stationnaire de Markov. Puisque la chaîne de Markov est apériodique et que sa convergence est garantie, la matrice de transposition est multipliée par la méthode de multiplication de puissance et le processus itératif est répété jusqu'à ce qu'il devienne ε ou moins. Le vecteur propre finalement calculé ici est le LexRank.

La mise en œuvre est la suivante.

def power_method(cosine_matrix, n, e):
	"""
Faites la méthode de puissance
	@param	scosine_matrix: list
Matrice de probabilité
	@param	n: int
Nombre de phrases dans une phrase
	@param	e: float
Tolérance ε
	@return: list
		LexRank
	"""
    transposed_matrix = cosine_matrix.T
    sentences_count = n
    
    p_vector = numpy.array([1.0 / sentences_count] * sentences_count)
    
    lambda_val = 1.0
    
    while lambda_val > e:
        next_p = numpy.dot(transposed_matrix, p_vector)
        lambda_val = numpy.linalg.norm(numpy.subtract(next_p, p_vector))
        p_vector = next_p
    
    return p_vector

Ceci termine le calcul de l'importance par LexRank. Plus la valeur des notes correspondantes est élevée, plus la peine est importante.

Résumé du résultat

Maintenant, résumons en fait. Pour résumer [le discours de M. Trump lors de la victoire à l'élection présidentielle](http://www.vox.com/policy-and-politics/2016/11/9/13569124/donald-trump-wins-2016-presidential- élection-victoire-discours-transcription).

# lex_rank(document)
Great people.
Great brothers, sisters, great, unbelievable parents.
We're going to get to work immediately for the American people, and we're going to be doing a job that hopefully you will be so proud of your president.

#Des gens formidables.
#Des parents formidables et incroyables, de grands frères et sœurs.
#Nous travaillerons bientôt pour le peuple américain. Nous travaillerons dans l'espoir que vous serez très fier du président.

Ouais, eh bien, je ferai de mon mieux pour le président! Vous pouvez sentir l'enthousiasme.

À la fin

Dans cet article, j'ai implémenté un algorithme de synthèse automatique et résumé le discours de M. Trump. LexRank semble être utile pour l'analyse de texte car vous pouvez capturer des phrases avec des graphiques. Demain, je continuerai à écrire quelque chose en résumé + traduction.

Les références

LexRank: Graph-based Lexical Centrality as Salience in Text Summarization miso-belica/sumy Document Summarization PART-2: LEXRank (Modified Pagerank) based Document Summarization Marche aléatoire sur graphique et classement de page Google Résumé automatique (wikipedia) Méthode de synthèse automatique de texte utilisant le traitement du langage naturel

Recommended Posts

Résumons le discours de Donald Trump en trois lignes avec l'algorithme de synthèse automatique LexRank
Résumer la valeur commerciale des sites EC à l'aide de l'algorithme de synthèse automatique LexRank
Trier en Python. Pensons ensuite à l'algorithme.