Assignment 02



In [1]:

    
import json
import os
import nltk
import string
import re
import pandas as pd
from IPython.display import display
import numpy as np
import math

a) Implement a crawler

Der Crawler wurde mit Hilfe der Bibliothek 'scrapy' geschrieben. Die dazu implementierte Anwendung ist im Verzeichnis ~/sitespider zu finden und der eigentliche Crawler in der Datei ~/sitespider/sitespider/spiders/site_spider.py. Der Code dazu sieht wie folgt aus:

# -*- coding: utf-8 -*-
import scrapy
import re
import json


class SiteSpiderSpider(scrapy.Spider):
    name = 'site_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):
        id = response.url.split('/')[-1].split('.')[0]

        with open("sites/%s.json" % id, 'w') as f:
            data = {'id': id,
                    'text': "".join(line for line in response.css('body::text').extract()),
                    'url': response.url,
                    'back_links': [link.split('.')[0] for link in response.css('a::attr(href)').extract()]
                    }

            json.dump(data, f)

        for next_page in response.css('a::attr(href)').extract():
            yield response.follow(next_page, callback=self.parse)

Die Klasse SiteSpiderSpider erbt von der Klasse scrapy.Spider. So kann die geschriebene Klasse später als Crawler benutzen werden.

Das Attribut name identifizieren den Crwaler und wird dazu benutzt, den Crawler später über die Konsole aufzurufen. Das Attribut start_urls legt fest, welche URLs vom Crawler initial angefragt werden sollen. Die Methode parse() nimmt dann anschließend die Rückgabe jeder Anfrage entgegen und bearbeitet diese. Da die Methode parse() die default Callback-Methode ist, muss diese nicht explizit angegeben werden.

Die parse()-Methode erzeugt einen String, der die Anfrage eindeutig beschreibt. Dieser Wert wird anschließend als Dateiname für die Datei verwendet, in der die Daten der Anfrage gespeichert werden. Gewähltes Fromat ist hierbei JSON. In der Datei selber wird die Id der Anfrage, der eigentliche Text ohne HTML-Tags, die URL und alle auf der Seite gefundenen Links als Array gespeichert. Anschließend wird für alle auf der Seite gefundenen Links derselbe Prozess mittels der Methode response.follow() angestoßen.

b) Crawl all reachable documents starting from the following URLs

Der implementierte Crawler kann mittels des Konsolen-Befehls 'scrapy crawl site_spider' in dem Verzeichniss ~/sitespider aufgerufen werden. Die resultierenden Dateien sind in dem Unterordner ~/sitespider/sites/* zu finden

c) Calculate the PageRanks of the downloaded pages

Folgend werden die PageRanks der heruntergeladenen Seiten berechnet.

Variablen

Folgende Variablen werden verwendet:

directory: Ordner, in dem die resultierenden Dateien liegen
files: resultierende Dateien
pages: Dictionary-Array, wobei jedes Dictionary jeweils eine Seite repräsentiert



In [2]:

    
directory = 'sitespider/sites'
files = [x[2] for x in os.walk(directory)][0]
pages = []

Importierung der analysierten Seiten

Im folgenden Code-Block werden die resultierenden Dateien einzeln ausgelesen und in der Variablen pages gespeichert.



In [3]:

    
for file in files:
    with open("%s/%s" % (directory, file)) as json_data:
        pages += [json.load(json_data)]

Konstanten

Die folgenden Konstenten sind vorgegeben bzw. müssen zuvor berechnet werden:

n = Anzahl der betrachteten Seiten
t = Teleportationsrate
d = Dämpfungsfaktor
δ = Abbruchswert



In [4]:

    
n = len(pages)
t = 0.05
d =  1 - t
δ = 0.04

Funktionen

PageRank-Funktion

Die Funktion calculate_page_rank() berechnet den PageRank für die übergebene Seite page_i. Folgende Formel wurde dabei implementiert:

$$ r_{k+1}(p_i) = d * \bigg ( \displaystyle\sum_{p_j \in B_{pi}} \frac{r_k(p_j)}{|p_j|} + \displaystyle\sum_{p_j,|p_j|=0} \frac{r_k(p_j)}{N} \bigg ) + \frac{t}{N} $$



In [5]:

    
def calculate_page_rank(page_i):
    sum_result = 0  
    for page_j in pages:
        if page_i['id'] in page_j['back_links']:
            sum_result += page_j['rank'] / len(page_j['back_links'])
        if len(page_j['back_links']) == 0:
            sum_result += page_j['rank'] / n
    return d * sum_result + t / n

Hilfe-Funktionen

Die Funktion initialize() initialisiert alle Seiten mit einem Start-PageRank, der sich durch die Division von eins durch die Anzahl aller Seiten berechnet. Zudem setzt sie den folgenden PageRank auf None.



In [6]:

    
def initialize():
    for page in pages:
        page['rank'] = 1/n
        page['rank+1'] = None

Die Funktion termination_condition() gibt einen boolischen Wert zurück, der sagt, ob die Abbruchbedingung erfüllt ist oder nicht. Im Falle, dass es keine zwei Vergleichswerte gibt, also rank+1 gleich None ist, wird False zurückgegeben, ansonsten wird der Rückgabewert mit folgender Formel berechnet:

$$ \sum_{p_i,i \in 1,...,N} abs(r_{k+1}(p_i) - r_k(p_i)) <= \delta $$



In [7]:

    
def termination_condition():
    delta = 0
    for page in pages:
        if page['rank+1'] is None:
            return False
        else:
            delta += abs(page['rank+1'] - page['rank'])
    return  delta <= δ

Die Funktion set_ranks() setzt, wenn rank+1 nicht None ist, für alle Seiten den älteren PageRank-Wert rank auf den aktuellen PageRank-Wert rank+1.



In [8]:

    
def set_ranks():
    for page in pages:
        if  page['rank+1'] is not None:
            page['rank'] = page['rank+1']

Berechnung der PageRanks für alle Dokumente

Im folgenden Code-Block wird zunächst die Methode initialize() aufgerufen, um alle Seiten mit einem initalen PageRank-Wert zu initialisieren. Anschließend wird so lange die While-Schleife durchlaufen, bis die Abbruchsbedingung erfüllt ist. Innerhalb der While-Schleife wird zunächst die Methode set_ranks() aufgerufen, um alle alten PageRanks auf den aktuellen Stand zu setzen. Anschließend wird jede Seite durchlaufen, wobei jeweils der nächste PageRank für die aktuelle Seite berechnet wird und in der Variablen rank+1 gespeichert wird.



In [9]:

    
initialize()
while not termination_condition():
    set_ranks()
    for page in pages:
        page['rank+1'] = calculate_page_rank(page)

Speichern der PageRanks

Die Resultate werden in der Datei rank.txt gespeichert. Dabei steht in der Datei zunächst die Id der Seite und anschließend der eigentliche PageRank-Wert.



In [10]:

    
with open('rank.txt', 'w') as f:
    for page in pages:
        f.write("%s: %s\n" % (page['id'], page['rank+1']))

Überprüfung der Summe aller PageRanks

Als Abschluß wird die Summe aller PageRanks berechnet, um zu prüfen, ob dieser Wert ungefähr 1 entspricht.



In [11]:

    
rank_sum = 0
for page in pages:
    rank_sum += page['rank+1']
print(rank_sum)









    



0.9999999999999998

d) Build a tf-Index for the words contained in the documents

Im folgenden Abschnitt wird ein TF-Index für alle Wörter, die in den Dokumenten (Seiten) auftauchen, berechnet.

Variablen

Folgende Variablen werden verwendet:

tf_dict: Dictionary, das den TF-Index repräsentiert
term_set: Set, bestehend aus allen vorkommenden Begriffen innerhalb der Dokumente
stopwords: Liste von Stopwörtern
exclude: Set von Zeichen, die entfernt werden sollen
porter: Stemmer, der zum Finden der Wortstämme verwendet werden soll; in dem Fall der nltk-Porter-Stemmer



In [12]:

    
tf_dict = {}
term_set = set()
stopwords = []
exclude = set(string.punctuation)
porter = nltk.PorterStemmer()

Funktionen

Gewichtete Term-Frequency

Die Funktion get_weighted_tf() brechnet mittels der folgenden Formel die gewichtete Term-Frequency für den übergebenen Term im Bezug auf das Dokument, mit der übergebenen Dokumenten-Id.

$$ w_{t,d} = \begin{cases} 1 + log_{10}(tf_{t,d}) & \quad \text{if } tf_{t,d} > 0\\ 0 & \quad \text{otherwise}\\ \end{cases} $$



In [13]:

    
def get_weighted_tf(doc_id, term):
    if term in tf_dict[doc_id]:
        if tf_dict[doc_id][term] == 0:
            return 0
        else:
            return 1 + math.log10(tf_dict[doc_id][term])
    else:
        return 0

Initalisierung der Stopwörter

Im folgenden Code-Block werden die Stopwörter aus der Datei stop_words.txt ausgelesen und in der Variablen stopwords gespeichert.



In [14]:

    
with open('stop_words.txt') as line:
    stopwords += re.sub('[^a-zA-Z0-9,]', '', line.read()).split(',')

Berechnung aller vorkommenden Wörter

Um alle vorkommenden Wörter zu berechnen, werden alle Texte der Dokumente durchlaufen und mittels des nltk-Wörter-Tokinisierers tokinisiert. Jedes resultierende Wort wird anschließend analysiert und sofern es kein Zeichen oder ein Stopwort ist, dem term_set hinzugefügt.



In [15]:

    
for page in pages:
    for term in nltk.word_tokenize(page['text']):
        if term not in exclude and term not in stopwords:
            term_set.add(porter.stem(term).lower())

Berechnung des Term-Frequency-Indexes

Um den Term-Frequency-Indexes aufzustellen, wird jedes Dokument durchlaufen, wobei zunächst für jedes Wort aus dem term_set ein Wert von 0 initialisiert wird. Anschließend wird jedes Wort innherhalb des Dokumentes analysiert und, sofern es sich um kein Zeichen oder Stopwort handelt, der passende Zähler um eins erhöht.



In [16]:

    
for page in pages:
    tf_dict[page['id']] = {}
    for term in term_set:
        tf_dict[page['id']][term] = 0
    for term in nltk.word_tokenize(page['text']):
        if term not in exclude and term not in stopwords:
            tf_dict[page['id']][porter.stem(term).lower()] += 1

Speichern des Term-Frequency-Indexes

Das Resultat wird in der Datei index.txt gespeichert. Dabei stellt jede Zeile ein Wort und jede Spalte ein Dokument dar.



In [17]:

    
tf_df = pd.DataFrame(tf_dict)
tf_df.to_csv('index.txt', header=True, index=True, sep=';')

e) Implement a function search to search for documents containing given words

Folgend wird ein TF-Index für alle Wörter innerhalb der Dokumente (Seiten) berechnet.

Variablen

Folgende Variablen werden verwendet:

df_dict: Dictionary, das für jedes Wort die Anzahl festhält, in wie vielen Dokumenten das Wort vorkommt und die Dokumenten, in denen es vorkommt.



In [18]:

    
df_dict = {}

Funktionen

Gewichtete Inverse-Document-Frequency

Die Funktion get_weighted_idf() berechnet mittels der folgenden Formel die gewichtete Inverse-Document-Frequency für den übergebenen Term.

$$ w_t = \begin{cases} log_{10}( \frac{N}{df_t}) & \quad \text{if } df_t > 0\\ 0 & \quad \text{otherwise}\\ \end{cases} $$



In [19]:

    
def get_weighted_idf(term):
    if term in df_dict:
        if df_dict[term]['count'] == 0:
            return 0
        else:
            return math.log10( n / df_dict[term]['count'])
    else:
        return 0

Gewichteter TF-IDF-Wert

Die Funktion get_weighted_tf_idf() brechnet mittels der folgenden Formel den gewichteten TF-IDF-Wert für den übergebenen Term im Bezug auf das Dokument mit der übergebenen Dokumenten-Id.

$$ \text{tf-idf}_{t,d} = tf_{t,d} \times idf_t $$



In [20]:

    
def get_weighted_tf_idf(doc_id, term):
    return get_weighted_tf(doc_id, term) * get_weighted_idf(term)

Search

Die Funktion search() brechnet für jede Seite einen Wert, der aussagt, wie gut die jeweilge Seite zu den gesuchten Termen passt. Dabei berechnet sich der Wert ohne Einbeziehung des PageRanks wie folgt:

$$ \text{Score}(q, d) = \sum_{t \in q} \text{tf-idf}_{t,d}$$

Mit Einbeziehung des PageRanks berechnet sich der Wert wie folgt:

$$ \text{Score}(q, d) = \sum_{t \in q} \text{tf-idf}_{t,d} \times PageRank_d $$



In [21]:

    
def search(terms, page_rank=False):
    result = {}
    for page in pages:
        result[page['id']] = 0
        for term in terms:
            result[page['id']] += get_weighted_tf_idf(page['id'], porter.stem(term).lower())
            if page_rank:
                result[page['id']] *= page['rank+1']
    return result

Berechnung der Document-Frequency für jedes Wort

Zur Berechnung der Document-Frequency werden alle Seiten durchlaufen, wobei jedes Wort des Textes der Seite betrachtet wird. Sofern das Wort kein Zeichen oder Stopwort ist und noch nicht im df_dict vorkommt, wird es neu mit der Document-Frequency 1 und der Dokumenten-Id angelegt. Existiert das Wort bereits im df_dict, wird nur dann die Document-Frequency um eins erhöht, wenn die aktuelle Dokumenten-Id noch nicht existiert.



In [22]:

    
for page in pages:
    for term in nltk.word_tokenize(page['text']):
        if term not in exclude and term not in stopwords:
            if porter.stem(term).lower() in df_dict and page['id'] not in df_dict[porter.stem(term).lower()]['documents']:
                df_dict[porter.stem(term).lower()]['count'] += 1
                df_dict[porter.stem(term).lower()]['documents'] += [page['id']]
            elif porter.stem(term).lower() not in df_dict:
                df_dict[porter.stem(term).lower()] = {'count': 1,
                                                      'documents': [page['id']]
                                                     }

Suche mit TF-IDF und anschließende Speicherung

Gesucht wird nach folgenden Termen:

token
index
classification
classification, token



In [23]:

    
search_terms = [['token'],['index'],['classification'],['classification', 'token']]

Im folgenden Code-Block wird jeder Such-Term durchgegangen und der jeweilige Wert für jedes Dokument berechnet. Der Wert setzt sich aus dem TF-IDF-Wert zusammen. Anschließend wird das Ergebnis in der Datei pageranke_search.txt gespeichert.



In [24]:

    
with open('tfidf_search.txt', 'w') as f:
    for search_term in search_terms:
        f.write('Suchwort: %s\n\n' % ', '.join(search_term))
        result = search(search_term)
        for key in result:
            f.write("%s: %s\n" % (key, result[key]))
        f.write('\n\n')

f) Extend your search function and include PageRank to score the documents

Suche mit TF-IDF und PageRank und anschließende Speicherung

Gesucht wird nach folgenden Termen:

token
index
classification
classification, token



In [25]:

    
search_terms = [['token'],['index'],['classification'],['classification', 'token']]

Im folgenden Code-Block wird jeder Such-Term durchgegangen und der jeweilige Wert für jede Seite berechnet. Der Wert setzt sich aus dem TF-IDF-Wert und PageRank zusammen. Anschließend wird das Ergebnis in der Datei pageranke_search.txt gespeichert.



In [26]:

    
with open('pageranke_search.txt', 'w') as f:
    for search_term in search_terms:
        f.write('Suchwort: %s\n\n' % ', '.join(search_term))
        result = search(search_term, page_rank=True)
        for key in result:
            f.write("%s: %s\n" % (key, result[key]))
        f.write('\n\n')