Voraussetzung für diese Lektion ist die Lektion Vorverarbeitung von Texten.
Um Dokumente oder Texte effizient zu bearbeiten, zu archivieren und auffindbar zu machen, ist es oft notwendig, sie in vordefinierte Kategorien einzusortieren. Man kann Mails automatisch in verschiedenen Postfächer einsortieren (Spam oder nicht-Spam), eingehende Post verschenenen ABteilungen eines Unternehmens zuordnen, Konferenzbeiträge zu verschiedenen Tracks einer Konferenz usw. Diese Klassifikation funktioniert für Texte oft sehr gut, wenn wir einige wenige bis zu einige Tausende Klassen haben, für die jeweils ausreichend Beispiele vorhanden sind. In dieser Lektion trainieren wir einen Classifier der aus rchtig klassifizierten Beispielen lernt. Nebenbei sehen wir, wie wir über eine Internetschnittstelle eine große Anzahl von Dokumenten eines Hochschulservers herunterladen können um ein eigenes Corpus aufzubauen.
Die Texte in unserem Beispiel sind deutschsprachige Abstracts von Dissertationen der TU Berlin; die Klassen sind die Fakultäten, an denen die Dissertationen verfasst wurden.
Zunächst lesen wir alle Texte ein. Als Merkmale für einen Text nehmnen wir die Frequenz (Häufigkeit durch Gesamtzahl der Wörter) der Lemmata der Wörter aus den offenen Klassen. Sicherheitshalber filtern wir auch Stop-wörter heraus.
Fast alle Universitäten Fachhochschulen und Forschungsinstitute haben einen Publikationsserver, auf dem wissenschaftliche Aufsätze, Dissertationen usw. veröffentlicht werden. Die meisten dieser Server haben eine OAI-PMH (Open Archives Initiative -- Protocol for Metadata Harvesting; siehe https://www.openarchives.org/OAI/openarchivesprotocol.html) Schnittstelle, über die sämtliche Daten heruntergeladen werden können. Diese Schnittstellen machen wir uns zu Nutze, um ein Corpus von Abstracts von Doktorarbeiten zu erstellen. Wir nehmen in deisem Beispiel deutschsprachige Abstracts der TU Berlin. In den Metadaten ist jeweils vermerkt an welche Fakultät die Arbeit eingereicht wurde. Hiermit haben wir eine schöne und leicht überprüfbare Klassifikationsaufgabe: wir verscuhen einen Classifier zu trainieren, der die Fakultät an Hand des Abstracts bestimmen kann.
Wir fragen dem Server erst eine Liste aller verfügbarer Publikationen. Wir bekommen ein Ergebnis in XML. Wie üblich bei Abfragen an Webservern mit möglicherweise langen Ergebnislisten, bekommen wir nur einen Teil der Ergebnisse und ein sogenanntes Resumption Token, mit der wir den nächsten Teil de Ergebnisse bekommen können.
import requests
import xml.etree.ElementTree as ET
def get_oai_ids(server):
ns = {'oai':'http://www.openarchives.org/OAI/2.0/'}
ids = []
response = requests.get(
server,
params={
'verb': 'ListIdentifiers',
'metadataPrefix': 'oai_dc'
}
)
while(response.status_code == requests.codes.ok):
xmlroot = ET.fromstring(response.text)
ids.extend([id.text for id in xmlroot.findall('./oai:ListIdentifiers/oai:header/oai:identifier',ns) ])
rts = xmlroot.findall('./oai:ListIdentifiers/oai:resumptionToken',ns)
if len(rts) == 0:
break
rt = rts[0].text
response = requests.get(
server,
params={
'verb': 'ListIdentifiers',
'resumptionToken': rt
}
)
return ids
tu_ids = get_oai_ids('https://depositonce.tu-berlin.de/oai/request')
Wir schauen uns mal einige Erbnisse an:
print(len(tu_ids))
print(tu_ids[:5])
ns = {'oai':'http://www.openarchives.org/OAI/2.0/',
'oai_dc' : 'http://www.openarchives.org/OAI/2.0/oai_dc/',
'dc' : 'http://purl.org/dc/elements/1.1/'
}
def getAbstract(recid):
ns = {'oai':'http://www.openarchives.org/OAI/2.0/',
'oai_dc' : 'http://www.openarchives.org/OAI/2.0/oai_dc/',
'dc' : 'http://purl.org/dc/elements/1.1/'
}
response = requests.get(
'https://depositonce.tu-berlin.de/oai/request',
params={
'verb': 'GetRecord',
'metadataPrefix': 'oai_dc',
'identifier':recid
}
)
record_root = ET.fromstring(response.text)
#print(response.text)
title = [t.text for t in record_root.findall('./oai:GetRecord/oai:record/oai:metadata/oai_dc:dc/dc:title',ns)]
abstract = [t.text for t in record_root.findall('./oai:GetRecord/oai:record/oai:metadata/oai_dc:dc/dc:description',ns)]
pubtype = [t.text for t in record_root.findall('./oai:GetRecord/oai:record/oai:metadata/oai_dc:dc/dc:type',ns)]
lang = [t.text for t in record_root.findall('./oai:GetRecord/oai:record/oai:metadata/oai_dc:dc/dc:language',ns)]
contributors = [t.text for t in record_root.findall('./oai:GetRecord/oai:record/oai:metadata/oai_dc:dc/dc:contributor',ns)]
return lang, title, abstract, pubtype, contributors
Wir schauen uns ein willkürliches Abstract an:
print(getAbstract(tu_ids[34]))
Wir schreiben eine Funktion, um aus der Lister der 'Contributors' die Fakultät zu ermitteln und testen diese Funktion:
import re
def get_faculty(contributors):
for contributor in contributors:
match = re.search(r'Fakultät [IVX]+',contributor)
if(match):
return match.group(0)
return None
lang, title, abstract, pubtype, contributors = getAbstract(tu_ids[34])
get_faculty(contributors)
Wir können jetzt alle Publikationen herunterladen und speichern, wenn es sich um ein deutschsprachiges Abstract einer Dissertattion handelt. Wir speichern die Abstracts jeder Fakultät in einem eigenen Verzeichnis.
import codecs
import os
def download_diss_abstracts(docids,directory):
for docid in docids:
try:
lang, title, abstract, pubtype, contributors = getAbstract(docid)
except:
print('Fehler: ', docid, 'konnte nicht geladen werden.')
continue
fak = get_faculty(contributors)
if fak and 'de' in lang and 'Doctoral Thesis' in pubtype:
text = title[0] + '\n' + abstract[0]
match = re.search('/([0-9]*)',docid)
if not os.path.exists(directory + '/' + fak):
os.makedirs(directory + '/' + fak)
fname = directory + '/' + fak + '/abstr-' + match.group(1) + '.txt'
file = codecs.open(fname,'w','utf-8')
file.write(text)
file.close
download_diss_abstracts(tu_ids,'Corpora/TUB')
Zuerst lesen wir alle Texten wieder ein. Das geht wesentlcih schneller als die Abfrage über die OAI-PMH Schnittstelle. Wenn wir öfters mit den Texten arbeiten, ist es also sinnvoll, wenn wir sie nicht jedesmal von dem Server herunterladen müssen.
import glob
import codecs
import html
import nltk
import pprint
import treetaggerwrapper
import collections
from nltk.corpus import stopwords
def read_data(verzeichnis):
data = {}
for v in glob.glob(verzeichnis+"\*"):
c = v[len(verzeichnis)+1:]
for datei in glob.glob(v +"\*.txt"):
textfile = codecs.open(datei, "r", "utf-8")
text = html.unescape(textfile.read()) #Texte sind nicht ganz sauber gespeichert!
textfile.close()
textlist = data.get(c,[])
textlist.append(text)
data[c] = textlist
return data
textdata = read_data("Corpora/TUB")
Wir brauchen jetzt möglichst viele Texte zum Lernen und einige Texte, die wir nachher nutzen um den Classifier zu testen. Diese Test-Texte dürfen wir natürlich nicht beim Lernen nutzen und müssen wir getrennt halten. Wir wählen diese Texte willkürlich aus, wobei wir aber gleich viele Texte aus jeder Klasse nehmen.
Gleichzeitig ändern wir auch die Struktur der Daten. Wir arbeiten jetzt mit einer flachen Liste weiter. Jedes Dokument wird als Paar bestehend aus Merkmale und Klasse (Fakultät in unserem Fall) gespeichert.
import random
def splitsets(classifiedtexts):
test = []
train = []
for cl in classifiedtexts:
textlist = classifiedtexts[cl]
random.shuffle(textlist)
test.extend([(txt,cl) for txt in textlist[:15]])
train.extend([(txt,cl) for txt in textlist[15:]])
return test, train
text_test, text_train = splitsets(textdata)
Statt einen Text braucht ein Classifier eine Liste von Merkmalen und für jedes Merkmal einen Wert. Eien Person kann mann zum Beispiel durch Merkmale wie Alter, Länge, Gewicht und IQ beschreiben. Um eine konkrete Person zu beschreiben, brauchen wir dann Werte (für die Beispiele Zahlen) für die Merkmale. Einen Text können wir über Wortfrequenzen beschreiben: jedes deutsche Wort is ein Merkmal. Die Werte dieser Merkmale sind die Häufigkeiten für alle Wörter im Text.
Wenn wir einen Text so beschreiben, lassen wir die Reihenfolge der Wörter ausser Acht. Wir betrachten eine Text also als eine Menge (genau genommen: Multimenge; englisch: Bag) von Wörtern. Einen Bag of Words also. Es gehen hierbei natürlich wesentliche Aspekte des Textes verloren, viele Eigenschaften bleiben aber auch erhalten. Gerade wenn es um die thematische Einordnung von Texten geht, funtioniert das Bag of Words-Model sehr gut.
Wir zählen nicht alle Wörter, sonder nur die Wörter die einen thematischen Bezug haben. Stopwörter kommen in allen Texten, unabhängig vom Thema, häufig vor. Auch andere Funktionswörter tragen wenig zur richtigen Klassifikation bei. Funktionswörter sind die Wörter, die einer geschlossenen Wortklasse angehören. Geschlossene Wortklassen sind die Klassen, die aus einer relativ kleine feste Menge von Wörtern bestehen, wie Artikel, Präposition oder Hilfsverb.
Man beacht bitte, dass dieses Vorgehen nicht in allen Fällen gleich sein muss. Wenn man Texte verschiedenen Autoren oder Schreibstile zuordnen will, können die Frequenzen von Stopwörtern, Pronomina, Artikel usw. durchaus hilfreich sein.
Für das Thema des Textes ist es auch unerheblich in welcher Form ein Wort vorkommt. Deswegen lemmatisieren wer die Texte und zählen die Lemmata statt die Wörter. Das es weniger Lemmata als Wörter gibt, reduzieren wir so auch die Menge der Merkmale und bekommen eine zuverlässigere Statistik. Für die Analyse des Textes nutzen wir also die un bereits bekannte Vorverarbeitung mit Tokenisierung, Lemmatisierung und POS-Tagging.
import nltk
import pprint
import html
import treetaggerwrapper
import collections
from nltk.corpus import stopwords
stopwords = set(stopwords.words('german'))
ttagger = treetaggerwrapper.TreeTagger(TAGLANG='de')
data = []
wordlist = []
def closed_class(pos):
if pos[0] == '$':
return True
elif pos in ["APPR", "APPRART", "APPO", "APZR", "ART", "KOUI", "KOUS", "KON", "KOKOM", "PDS", "PDAT", "PIS", "PIAT", "PIDAT", "PPER", "PPOSS", "PPOSAT", "PRELS", "PRELAT", "PRF", "PWS", "PWAT", "PWAV", "PAV", "PTKZU", "PTKNEG", "VAFIN", "VAIMP", "VAINF", "VAPP", "VMFIN", "VMINF", "VMPP"]:
return True
return False
def features_from_text(text):
tlen = 0
wordcounts = collections.Counter()
sentences = nltk.sent_tokenize(text)
for sent in sentences:
tokens = nltk.tokenize.word_tokenize(sent,language='german')
tags = ttagger.tag_text(tokens,tagonly=True)
tags2 = treetaggerwrapper.make_tags(tags);
lemmata_sent = [lemma for (word,pos,lemma) in tags2 if not closed_class(pos) and not word in stopwords]
#lemmata.extend(lemmata_sent)
tlen += len(lemmata_sent)
wordcounts.update(lemmata_sent)
return {w:(float(wordcounts[w])/float(tlen)) for w in wordcounts}
feat_train = [(features_from_text(text),cl) for (text,cl) in text_train]
feat_test = [(features_from_text(text),cl) for (text,cl) in text_test]
Wir schauen uns die Merkmale eines Textes an:
pprint.pprint(feat_train[1])
Wir können jetzt die Ähnlichkeit zwischen zwei Dokumenten berechnen, zum Beispiel mit dem Cosinus: wenn wir jedes Wort als eine Dimension betrachten, ist ein Text ein Punkt, oder ein Vektor im hochdimensionalen Wortraum. Der Winkel zwischen den Merkmalsvektoren ist ein gutes Maß für die Ähnlichkeit der Vektoren. In der Praxis berechnen wir nie den Winkel, sondern hören auf, wenn wir den Cosinus berechnet haben.
Für zwei Merkmalsvektoren $a$ und $b$ gilt: $$ cos(a,b) = \frac{\sum_i a_i b_i}{\sqrt{\sum_i a_i^2}\sqrt{\sum_i b_i^2}} $$
import math
def cosinus(a,b):
return sum([a[k]*b[k] for k in a if k in b]) / (math.sqrt(sum([a[k]**2 for k in a])) * math.sqrt(sum([b[k]**2 for k in b])))
Wir vergleichen jetzt mal die Ähnlichkeit von zwei willkürlichen Dokumenten aus einer Klasse mit der Ähnlichkeit von zwei Dokumenten aus unterschiedlichen Klassen.
d1,c1 = feat_train[34]
d2,c2 = feat_train[35]
d3,c3 = feat_train[325]
print(c1,c2,c3)
print(cosinus(d1,d2))
print(cosinus(d1,d3))
print(cosinus(d2,d3))
Bevor wir jetzt einen Classifier testen, fragen wir uns, welche Ergebnisse wir von einem Classifier erwarten können. Was wäre z.B. eine Untergrenze für die Qualität, die wir erwarten können?
Ein absolut trivialer Classifier würde immer die gleiche Klasse vorhersagen. In vielen Fällen kann das aber schon zu einem sehr guten Ergebnis führen! Ein Sinnvoller Classifier sollte aber ein besseres Ergebnis liefern. Wenn wir einen solchen trivialen Classifier bauen, ist der sinnvollste Wahl für die Klasse, die immer vorhergesagt wird natürlich die größte Klasse. Deswegen wird der Classifier ein Majority Classifier genannt.
In den Testdaten sind alle Klassen gleich groß. Es ist also egal, welche Klasse vorhergesagt wird. Der majority Classifier wird immer $\frac{1}{7}$ oder 14% der Abstracts koorekt klassifizieren.
Ein sehr einfaches Klassifikationsverfahren ist das k-Nearest-Neighbors (kNN) oder k-Nächste-Nachbarn-Verfahren.
Im Training machen wir nichts, ausser das Speichern aller Beispiele. In der Klassifikation suchen wir die k Nachbarn, die dem zu klassifizierenden Element am ähnlichsten sind. Dieser Schritt ist natürich sehr aufwändig! Die Klasse, die unter diesen Nachbarn am häufigsten Vertreten ist, ist der Vorschlag für das zu klassifizierende Element.
def kNN(features,k,train):
similarities = []
for d,c in train:
similarities.append((c,cosinus(d,features)))
similarities = sorted(similarities,key= lambda x:x[1],reverse=True)
cnt = collections.Counter({c:sim for (c,sim) in similarities[:k]})
most_likely = cnt.most_common(1)
return most_likely[0][0]
Wir versuchen es einfach mal:
f,c = feat_test[86]
print("Korrekt wäre:",c)
vorhersage = kNN(f,3,feat_train)
print("Vorhersage ist:",vorhersage)
Wir testen jetzt mal systematisch alle Testdaten
n = 0
correct = 0
for f,c in feat_test:
p = kNN(f,1,feat_train)
n+= 1
if p==c:
correct+=1
print("{0:.1f} Prozent korrekt".format(100* float(correct)/float(n)))
Das ist schon gar nicht so schlecht, wenn auch nicht sehr beeidruckend. Das Ergebnis ist aber deutlich besser, als das, was wir mit Raten oder mit dem Majority Classifier hätten erreichen können.
Wo sind aber die Fehler aufgetreten? Un diese Frage zu beantworten, ise eine Konfusionsmatrix sehr hilfreich. NLTK hat eine Funktion zum erstellen eines Konfusionsmatrizen:
gold = [c for f,c in feat_test]
test = [kNN(f,2,feat_train) for f,c in feat_test]
cm = nltk.ConfusionMatrix(gold, test)
print(cm)
Wir haben jetzt Wortfrequenzen als Merkmalswerte genommen. Hierdurch werden alle Wörter gleichermaßen berücksichtigt. Das Auftreten eines seltenen Wortes sagt aber viel mehr über einen Text aus, als das auftreten eines gewöhnlichen Wortes. Anders gesagt: wenn zwei Texte das gleiche seltene Wort enthalten, ist es wahrscheinlich, dass sie zur gleichen Klasse gehören. Wenn das gleiche gewöhnliche Wort vorkommt, sagt das nicht so viel aus.
Damit seltene Wörter stärker berücksichtigt werden, bekommen diese meistens ein größeres Gewicht. Dies wird dadurch erreicht, dass tf.idf Werte statt Wortfrequenzen benutzt werden.
Die Idee hinter tf.idf ist, dass ein Term umso besser characterisiert, wenn er in weniger Dokumenten vorkommt. Diese Idee führt zurück auf Hans Peter Luhn (1957) und Karen Spärck Jones (1972). Es gibt verschiedene Formulierungen und Berechnungsweisen für den tf.idf-Wert eines Wortes und auch die Herleitung der Formel ist umstritten. Es gibt verschiedene komplizierte statistische Herleitungen. Klar ist aber, dass das tf.idf-Maß ein sehr gutes und fast unschlagbares Maß für die Relevant eines Wortes in einem Dokument ist.
Der tf.idf Wert für ein Wort besteht aus zwei Komponenten:
Die Inverse Dokumentfrequenz bezieht sich immer auf eine Dokumentsammlung. Die Qualität des idf-Wertes ist also abhängig von der Qualität und Größe der Dokumentsammlung.
Für ein Term $t$ aus einer Sammlung $D$ ist die Dokumentfrequenz jetzt einfach die Fraktion der Dokumente, in denen $t$ vorkommt. Wenn $N_{D,t}$ die Zahl der Dokumente aus $D$ ist, in denen $t$ vorkommt, dann $$ df_{D,t} = \frac{N_{D,t}}{|D|} $$ Die inverse Dokumentfrequenz ist jetzt definiert durch: $$ idf_{D,t} = \frac{1}{df_{D,t}} = \frac{|D|}{N_{D,t}} $$
Da die Gewichte dieser Formel zu extrem sind, nutzt man meistens eine leicht modifizierte Formel, die im Kontext von IR übrigens auch statistisch hergeleitet werden kann: $$ idf_{D,t} = 1 + log \frac{|D|}{N_{D,t}} $$
Die Termfrequenz eines Terms $t$ in einem Dokument $d$ ist schlicht die Anzahl der Vorkommen von $t$ in $d$ dividiert durch die Länge (Anzahl der Wörter) von $d$: $$ tf_{t,d} = \frac{N_{d,t}}{|d|} $$
Wenn wir jetzt beide Werte miteinande multiplizieren, berücksichtigen wir sowohl die Häufigkeit im Dokument, wie der 'Seltenheitswert' in der Dokumentensammlung:
$$ tf.idf(D,d,t) = tf_{t,d} \cdot idf_{D,t} $$Im Nachfolgenden nutzen wir die Trainingsmenge zur Berechnung der Dokumentfrequenzen. Wenn wir jetzt tf.idf-Werte für Wörter aus der Testmenge, die nicht in der Trainingsmenge vorkommen, berechnen, müssten wir durch Null dividieren. Um dieses Problem zu umgehen, nutzen wir für die Dokumemtfrequenz ein naives Add-One oder Laplace Smoothing.
nrOfDocs = len(feat_train)
docfreq = collections.Counter()
for (wfreq,c) in feat_train:
docfreq.update(wfreq.keys())
def tfidf_transform(data):
tdata = []
for (wfreq,c) in data:
tfidf = {}
for w in wfreq:
tfidf[w] = wfreq[w] * math.log(nrOfDocs/float(1+docfreq[w]))
tdata.append((tfidf,c))
return tdata
tfidf_train = tfidf_transform(feat_train)
tfidf_test = tfidf_transform(feat_test)
Wir versuchen es nochmal und bekommen tatsächlich ein etwas besseres Ergebnis.
n = 0
correct = 0
for f,c in tfidf_test:
p = kNN(f,1,tfidf_train)
n+= 1
if p==c:
correct+=1
print("{0:.1f} Prozent korrekt".format(100* float(correct)/float(n)))
Ein Verfahren, das bei der Klassifikation wesentlich effizienter ist, aber nach einem ähnlichem Prizip funktioniert, ist der Nearest Centroid Klassifikator. Wir erstellen jetzt für jede Klasse ein Musterdokument. Dieses Dokument hat für jedes Merkmal die Durchschnittswerte aller Dokumente aus einer Klasse. Für ein neues Dokument suchen wir jetzt das nächste Zentrum.
def get_centers(data):
centers = {}
class_sizes = {}
for featmap,c in data:
center = centers.get(c,{})
class_sizes[c] = 1 + class_sizes.get(c,0)
for ft in featmap:
freq = featmap[ft]
center[ft] = freq + center.get(ft,0)
centers[c] = center
for cls in centers:
center = centers[cls]
for f in center:
center[f] /= class_sizes[cls]
return centers
cls_centers = get_centers(tfidf_train)
def nearest_centroid(f,centers):
similarities = [(c,cosinus(f,centers[c])) for c in centers]
return sorted(similarities,key= lambda x:x[1],reverse=True)[0][0]
fs,c = tfidf_test[9]
nearest_centroid(fs,cls_centers)
n = 0
correct = 0
for f,c in tfidf_test:
p = nearest_centroid(f,cls_centers)
n+= 1
if p==c:
correct+=1
print("{0:.1f} Prozent korrekt".format(100* float(correct)/float(n)))
Das ist jetzt schon ziemlich gut. Schauen wir uns das Ergebnis jetzt etwas näher an:
gold = [c for f,c in tfidf_test]
test = [nearest_centroid(f,cls_centers) for f,c in tfidf_test]
cm = nltk.ConfusionMatrix(gold, test)
print(cm)