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.
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.
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.
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
Ici, nous expliquerons chaque bloc.
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.
À 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.
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.
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.
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