In [1]:
from subprocess import check_output
import json
from pprint import pprint
import numpy as np
import pandas as pd
from math import log
import re
!ls
Im Rahmen dieser Belegarbeit sollte eine einfache Suchengine implementiert werden.
Dabei waren folgende Schritte abzuarbeiten:
In [2]:
from IPython.display import IFrame
IFrame("./graded02.pdf", width=900, height=1250)
Out[2]:
Der Crawler wurde mit der Bibliothek Scrapy umgesetzt. Es wurde sich hier gegen eine Einrichtung eines Projektes und für eine Scriptbasierte Lösung entschieden.
Um die Ausführung über das Notebook zu regeln, wurde über das MagicFlag %%writefile die Klasse in eine Datei geschrieben und der Aufruf über von Scrapy über subprocess umgesetzt.
Die Klasse HtwSpider implementiert über die Einstiegspunkte, die Extraktionsanweisungen sowie dem gewünschten Link-Verhalten den Crawler.
Dabei werden der Titel, der Text und die ausgehenden Links aller Seiten gespeichert, die von den EInstiegspunkten aus eirreichbar sind.
In [3]:
%%writefile ./my_spider.py
# %%writefile ./my_spider.py
# %load ./my_spider.py
import scrapy
import json
class HtwSpider(scrapy.Spider):
name = 'htw_spider'
start_urls = [
'http://people.f4.htw-berlin.de/~zhangg/pages/teaching/pages/d01.html',
'http://people.f4.htw-berlin.de/~zhangg/pages/teaching/pages/d06.html',
'http://people.f4.htw-berlin.de/~zhangg/pages/teaching/pages/d08.html'
]
def parse(self, response):
# - Extracting the needed attributes.
title = response.xpath('//title/text()').extract()[0]
text = ' '.join([t.strip() for t in response.xpath('//body/text()').extract()]).strip()
hrefs = [l.split('.')[0] for l in response.xpath('//a/@href').extract()]
# - Printing the extracted data for logging.
print("\n ----DATA\n\n%s\n" % json.dumps({title : {'text': text,
'refs' : hrefs }}))
# - Yielding the extracted dataset as dict
yield {'title': title,
'text': text,
'refs' : hrefs }
# - Here we find the actual spider.
# - This goes through all a_hrefs and scrapes the needed data.
for next_page in response.xpath('//a/@href').extract():
if next_page is None:
continue
next_page = response.urljoin(next_page)
yield scrapy.Request(next_page, callback=self.parse)
In [4]:
# - Here we call the scrapy process.
#
# - This is needed to call this inside the notebook.
# - Scrapy concatenates all outputs (with destroying the json)
# so we need to remove it first.
!rm ./my_spider.json
# - Executing the spider.
pout = check_output('scrapy runspider my_spider.py -o my_spider.json', shell=True)
# - Writing the output into logfile.
with open('./my_spider.log', 'w') as logfile:
logfile.write(pout.decode("utf-8"))
Einlesen der Daten
In [5]:
# - Reading the Data from json into python obj-structure.-
with open('./my_spider.json') as infile:
data = json.loads(''.join([line.strip() for line in infile.readlines()]))
# - Removing all duplicates
data = list({d['title']:d for d in data}.values())
df = pd.DataFrame.from_dict(data)
df.index = df['title']
df
Out[5]:
Definition der Datenstrukturen
Um die Berechung zu vereinfachen, wurde die Datenhaltung in Form eines Graphen angeordnet.
Dabei hält jeder Knoten die ein- und ausgehenden Kanten, seinen Namen und die für die Berechung benötigten Platzhalter für das Zwischenspeichern der Ergebnisse. Auf Grund der rekursiven Struktur der Berechnungen müssen die Werte bereits belegt sein.
Hierbei ist es wichtig, dass die Variablen rank eine vollständige Wahrscheinlichkeitsverteilung $\left(\sum n \in N = 1\right)$ beschreiben.
In [6]:
delta = 0.04
N = len(data)
t = 0.05
d = 1-t
graph = [ # - The graph of the web.
# Rank' is mocked with the purpose of simplifying the calculations.
{
'node': d['title'],
'out': d['refs'],
'in' : [n['title'] for n in data if d['title'] in n['refs']],
'rank': 1.0 / N, # (1 / n) \leq 1 \forall n \in \mathbb{N}
'rank_': 1.0 + delta # mocking rank_
}
for d in data ]
print('\n\nInitial graph:\n')
pd.DataFrame.from_dict(graph)
Out[6]:
Definition des Algorithmus zur Berechung des PageRank eines Knoten
$$ r_{k+1}(p_i) = d \cdot \left( \sum_{pj \in B_{p_i}} \frac{r_k(pj)}{|pj|} + \sum_{pj,\,|pj|=0} \frac{r_k(p_j)}{N} \right) + \frac{t}{N} $$
In [7]:
# - Get the amount of all outgoing refs of pj
out_len = lambda pj: [len(page['out']) for page in graph if page['node'] == pj][0]
# - Extract the rank of pj.
get_rank = lambda pj: [p['rank'] for p in graph if p['node'] == pj][0]
# - Calculate pagerank of node pi.
_r = lambda pi: (
d * (
np.sum( [ get_rank(pj) / out_len(pj) for pj in pi['in'] ] ) +
np.sum( [ get_rank(pj['node']) / N for pj in graph if out_len(pj['node']) == 0 ] )
) + (t / N) )
Berechnungen in Iterationen
Die Berechnung erfolgt so lange bis die Abbruchbedingung erfüllt ist.
Es gilt folgende Abbruchbedingung:
$$ \left(\sum \left(| r^{(i)} -r'^{(i)}|\right) >= \delta\right);\,\,\,\, \forall r, r' \in g $$
In [8]:
# - The iterations of the pageranks
while not np.sum( [ abs(g['rank'] - g['rank_']) for g in graph ] ) < delta :
for node in graph:
node['rank_'], node['rank'] = node['rank'], _r(node)
Ausgabe der errechneten Daten
In [9]:
# - Put the calcuated data inside a DataFrame.
df = pd.DataFrame(graph)
df.index = df['node']
# ... writing it to file ...
df[['node', 'rank']].to_csv('rank.txt', index=False)
# ... and do some printing.
pprint(df['rank'])
print("Σ ----------------")
pprint(np.sum(df['rank']))
Tokenizing
Folgende Arbeitsschritte wurden hier abgearbeitet:
In [10]:
# - Extracting stopwords from file
with open('./stop_words.txt') as infile:
lines = infile.readlines()
stopwords = [word.strip("'").strip()
for line in lines
for word in line.split(', ')
if word.strip("'").strip() != '']
tokenize = lambda d: [re.compile('[\W_]+').sub('', w.lower()) for w in d.split() if w not in stopwords]
docs = [{'title': d['title'], 'words': tokenize(d['text'])} for d in data ]
Indexing
Es wird ein inversed Index aufgebaut.
Dabei werden die absoluten Vorkommen der Therme $w$ in den jeweiligen Dokumenten $d$ gespeichert.
In [11]:
words = [word for doc in docs for word in doc['words']]
iindx = pd.DataFrame.from_dict({ doc['title']: [
doc['words'].count(word) for word in words ]
for doc in docs })
iindx.index = words
iindx = iindx[~iindx.index.duplicated(keep='first')]
iindx.to_csv('index.txt')
iindx.head(10)
Out[11]:
Term Freqency
Hier wurde sich für eine logarithmisch normierte Term Freqency entschieden.
Damit gilt:
$$ \mbox{log_freq}(w, d) = \begin{cases} 1 + log10 tf(w,d) & \mbox{für}\,\,\,\,\,\,\,\,\,\,\,\,\,\, tf(w,d) > 0 \\ 0 & \mbox{sonst} \\ \end{cases} $$bei $tf(w,d) := $ absolutes Vorkommen des Terms $w$ in Dokument $d$.
Die Term Frequency steht bereits im Index und muss nur ausgelesen werden.
Inversed Document Frequency
Ist definiert als $$\frac{\mbox{Anzahl der Dokumente} (N)}{\mbox{Anzahl der Dokumente welche Term w enthalten }(df(w)) }$$
Eine Normierung erfolgt mit $\log_{10} df(w)$
Scoring und Suchfunktion
Das scoring der Dokumente eines spezifischen Terms kann über die Funktion search(words) ermittelt werden.
Dabei ist es auch möglich, Listen von Termen anzugeben. Diese werden über $A \land B$ verbunden.
In [12]:
idx = pd.read_csv('./index.txt', index_col=0)
def log_freq(word, doc):
tf = int(idx[doc].loc[word])
return 1+log(tf, 10) if tf > 0 else 0
def idf(word):
N = idx.shape[0]
df = np.sum(idx.loc[word].map(lambda x: 0 if x == 0 else 1))
return log ( (N / df), 10)
tfidf = lambda w,d : (log_freq(w, d) * idf(w))
weights = lambda w : [ {d: tfidf(w,d)}
for d in idx.columns.values.tolist() ]
pd.DataFrame.from_dict([{word: weights(word) for word in words}])
tfiidx = pd.DataFrame.from_dict({ doc['title']: [
tfidf(word, doc['title']) for word in words ]
for doc in docs })
tfiidx.index = words
tfiidx = tfiidx[~tfiidx.index.duplicated(keep='first')]
In [13]:
def search (words):
assert type(words) == list
# - The weights are calculatet by
return pd.DataFrame([tfiidx.loc[w] for w in words]).product()
s_terms = [['tokens'], ['index'], ['classification'], ['tokens', 'classification']]
search_df = pd.DataFrame([search(t) for t in s_terms])
search_df.index=[' AND '.join(s) for s in s_terms]
In [14]:
search_df
Out[14]:
In [15]:
search_df.to_csv('tfidf_search.txt')
In [16]:
r = pd.read_csv('rank.txt', index_col=0)
s = pd.read_csv('tfidf_search.txt', index_col=0)
score = pd.DataFrame(r.values * s.T.values, index=r.index, columns=s.index).T
score.to_csv('pageranke_search.txt')
score
Out[16]: