Dies ist der Artikel am 15. Tag des Nextremer Adventskalenders 2016.
2016 ist fast vorbei, aber auch dieses Jahr gab es viele Neuigkeiten. Ist Donald Trumps Sieg bei den Präsidentschaftswahlen nicht eines der wirkungsvollsten Ereignisse?
Ich sehe es oft im Fernsehen, aber ich habe die Rede nicht richtig gehört, also werde ich die Rede lesen. Da ich jedoch nicht gut Englisch kann, verwende ich den Zusammenfassungsalgorithmus, um ihn auf etwa 3 Zeilen zu reduzieren.
Es gibt zwei Möglichkeiten, um zusammenzufassen.
Die generativen Zusammenfassungen sind sehr schwierig, und die meisten der derzeit hauptsächlich untersuchten sind selektive Vorbehalte. Der diesmal implementierte LexRank gehört ebenfalls zur extraktiven Zusammenfassung und extrahiert wichtige Sätze im Satz.
LexRank ist ein von PageRank inspirierter Zusammenfassungsalgorithmus. PageRank ist ein Algorithmus, der von den Google-Gründern L.Page und S.Brin entwickelt wurde, um die Bedeutung von Webseiten zu bestimmen. Die Wichtigkeit der Seite wurde bestimmt, indem die Linkstruktur im Internet wie folgt dargestellt wurde.
Knoten: Webseite
Rand: Link
Knotenbedeutung:
1.Von vielen Seiten verlinkte Seiten sind wichtige Seiten
2.Von wichtigen Seiten verlinkte Seiten sind wichtige Seiten
Wie PageRank erfasst auch LexRank Sätze als Grafik.
Knoten: Anweisung
Rand: Ähnlichkeit zwischen zwei Sätzen(1 | 0)
Knotenbedeutung:
1.Sätze, die vielen Sätzen ähnlich sind, sind wichtig
2.Sätze, die wichtigen Sätzen ähnlich sind, sind wichtige Sätze
Der Grad der Ähnlichkeit ist hier einfach, wie sehr die beiden Sätze ein gemeinsames Wort haben.
LexRank bewertet die Bedeutung nur anhand der Diagrammstruktur. Als es 2004 erfunden wurde, zeigte es die beste Genauigkeit in DUC2004. Es ist sehr interessant, ohne semantische Analyse mit hoher Genauigkeit zusammenfassen zu können.
Die Formel für LexRank lautet wie folgt.
Input:Array S bestehend aus n Anweisungen,Kosinusähnlichkeitsschwelle t
Output:Array L mit LexRank-Bewertungen für jeden Satz
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
(Zitat: "LexRank: Graphbasierte lexikalische Zentralität als herausragende Rolle bei der Textzusammenfassung" Alogorithmus 3)
idf-modifizierter Cosinus ist eine Ähnlichkeitsberechnung zwischen zwei Sätzen.
PowerMethod ist eine PageRank-Berechnung.
ist.
Lassen Sie uns diesen Algorithmus nun tatsächlich in Python implementieren.
import math
import numpy
def lex_rank(sentences, n, t):
"""
Fassen Sie den Text mit LexRank zusammen.
@param sentences: list
Satz([[w1,w2,w3],[w1,w3,w4,w5],..]Liste der Sätze wie)
@param n: int
Anzahl der in einem Satz enthaltenen Sätze
@param t: float
Kosinus-Ähnlichkeitsschwelle(default 0.1)
@return : list
LexRank
"""
cosine_matrix = numpy.zeros((n, n))
degrees = numpy.zeros((n,))
l = []
# 1.Erstellen einer benachbarten Matrix
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.LexRank-Berechnung
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)
Dieses Programm ist von Funktion
Hier erklären wir jeden Block.
Die benachbarte Matrix ist eine Matrix zur Darstellung von Graphen. Der Graph wird durch Ersetzen von 1 ausgedrückt, wenn zwischen den Knoten eine Kante vorhanden ist, und 0, wenn diese nicht vorhanden ist. Wenn in LexRank die Ähnlichkeit zwischen zwei Sätzen gleich oder größer als der Schwellenwert t ist, werden sie durch eine Kante verbunden.
Die Implementierung der Ähnlichkeit ist wie folgt.
def idf_modified_cosine(sentences, sentence1, sentence2):
"""
Berechnen Sie die Kosinusähnlichkeit zwischen zwei Sätzen
@param sentence1: list
Satz 1([w1,w2,w3]Wortliste wie)
@param sentence2: list
Satz 2([w1,w2,w3]Wortliste wie)
@param sentences: list
Satz([[w1,w2,w3],[w1,w3,w4,w5],..]Wortliste wie)
@return : float
Kosinusähnlichkeit
"""
tf1 = compute_tf(sentence1)
tf2 = compute_tf(sentence2)
idf_metrics = compute_idf(sentences)
return cosine_similarity(sentence1, sentence2, tf1, tf2, idf_metrics)
TF ist die Häufigkeit des Auftretens von Wörtern in einem Satz. (Je wichtiger es ist) IDF ist die Häufigkeit des Auftretens von Wörtern im gesamten Dokument. (Je weniger es ist, desto wichtiger ist es) Die Kosinusähnlichkeit ist der Kosinus der Ähnlichkeit zwischen Vektoren.
Ich denke, dass viele Leute davon wissen, deshalb werde ich kurz nur die Implementierung veröffentlichen.
from collection import Counter
def compute_tf(sentence):
"""
TF berechnen
@param sentence: list
Satz([w1,w2,w3]Wortliste wie)
@return : list
TF-Liste
"""
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):
"""
Suchen Sie nach der maximalen Häufigkeit des Auftretens von Wörtern
@param terms: list
Häufigkeit des Auftretens von Wörtern
@return : int
Maximale Häufigkeit des Auftretens von Wörtern
"""
return max(terms.values()) if terms else 1
def compute_idf(sentences):
"""
Berechnen Sie den IDF-Wert eines Wortes in einem Satz
@param sentences: list
Satz([[w1,w2,w3],[w1,w3,w4,w5],..]Wortliste wie)
@return: list
IDF-Liste
"""
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):
"""
Berechnen Sie die Kosinusähnlichkeit
@param sentence1: list
Satz 1([w1,w2,w3]Wortliste wie)
@param sentence2: list
Satz 2([w1,w2,w3]Wortliste wie)
@param tf1: list
TF Liste von Satz 1
@param tf2: list
TF Liste von Satz 2
@param idf_metrics: list
IDF Liste der Sätze
@return : float
Kosinusähnlichkeit
"""
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
Wenn schließlich die Kosinusähnlichkeit t oder größer ist, ersetzen Sie 1, um die benachbarte Matrix zu vervollständigen.
Als nächstes finden wir den LexRank basierend auf der hier erstellten Matrix.
Von hier aus wird LexRank basierend auf der in 1 erhaltenen benachbarten Matrix berechnet. Teilen Sie zunächst jedes Element der benachbarten Matrix durch Grad (Reihenfolge der Knoten) und konvertieren Sie es in eine Wahrscheinlichkeitsmatrix.
Basierend auf dieser Wahrscheinlichkeitsmatrix finden wir dann die stationäre Markov-Verteilung. Da die Markov-Kette aperiodisch ist und garantiert konvergiert, wird die Transpositionsmatrix mit dem Leistungsmultiplikationsverfahren multipliziert und der iterative Prozess wird wiederholt, bis sie ε oder weniger wird. Der hier schließlich berechnete Eigenvektor ist der LexRank.
Die Implementierung ist wie folgt.
def power_method(cosine_matrix, n, e):
"""
Mach die Power-Methode
@param scosine_matrix: list
Wahrscheinlichkeitsmatrix
@param n: int
Anzahl der Sätze in einem Satz
@param e: float
Toleranz ε
@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
Damit ist die Wichtigkeitsberechnung durch LexRank abgeschlossen. Je größer der Wert der entsprechenden Bewertungen ist, desto höher ist die Bedeutung des Satzes.
Lassen Sie uns nun zusammenfassen. Um [die Rede von Herrn Trump zum Zeitpunkt des Sieges der Präsidentschaftswahlen] zusammenzufassen (http://www.vox.com/policy-and-politics/2016/11/9/13569124/donald-trump-wins-2016-presidential- Wahlsieg-Rede-Transkript).
# 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.
#Tolle Leute.
#Großartige, unglaubliche Eltern, großartige Brüder und Schwestern.
#Wir werden bald für das amerikanische Volk arbeiten. Wir werden in der Hoffnung arbeiten, dass Sie sehr stolz auf den Präsidenten sind.
Ja, ich werde mein Bestes für den Präsidenten geben! Sie können die Begeisterung spüren.
In diesem Artikel habe ich einen automatischen Zusammenfassungsalgorithmus implementiert und die Rede von Herrn Trump zusammengefasst. LexRank scheint für die Textanalyse nützlich zu sein, da Sie Sätze mit Grafiken erfassen können. Morgen werde ich weiterhin etwas mit Zusammenfassung + Übersetzung schreiben.
LexRank: Graph-based Lexical Centrality as Salience in Text Summarization miso-belica/sumy Document Summarization PART-2: LEXRank (Modified Pagerank) based Document Summarization Random Walk on Graph und Google Page Rank Automatische Zusammenfassung (Wikipedia) Automatische Methode zur Zusammenfassung von Texten unter Verwendung der Verarbeitung natürlicher Sprache
Recommended Posts