Übung 5: HITS Startwerte?

Moderator: Web Mining

Benutzeravatar
michasch
DON'T PANIC
Beiträge: 42
Registriert: 2. Okt 2004 20:47
Wohnort: Dieburg
Kontaktdaten:

Übung 5: HITS Startwerte?

Beitrag von michasch »

Im Gegensatz zum PageRank-Algorithmus der durch die Einbeziehung des Faktors 1/N nach ein paar Iterationen gegen sinnvolle Werte konvergiert kann ich aus den Folien nicht herauslesen wie die Authority- bzw. Hubwerte zu initialisieren sind, damit man auch mit dem HITS-Algorithmus arbeiten kann. Da die Werte ja zirkelbezüglich berechnet werden führt eine Initialisierung mit 0 zu einer ewigen Berechnung von 0-Werten, was mich nicht wirklich weiterbringt.
- Wo finde ich Informationen darüber, mit welchem Wert ich h(x) und a(x) intialisieren (iterative Variante) muss? (evtl. 1/N ???)
Auch das Normalisieren ist auf den Folien zwar erwähnt, aber nicht erläutert.
- Wie müssen die Werte h(x) und a(x) normalisiert werden?

Gruß,
michasch
Ich denke, also bin ich - manche sind trotzdem.

eneldo
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 220
Registriert: 19. Mai 2006 13:06
Kontaktdaten:

Re: Übung 5: HITS Startwerte?

Beitrag von eneldo »

Hallo,
die nötigen Informationen findest du auf Seite 10 der Folien http://www.ke.informatik.tu-darmstadt.d ... -graph.pdf
- der a und h Vektor wird mit (z.B.) 1 initialisiert (erste Zeile im Pseudocode)
- für die Normalisierung verwendet man die Betragssummennorm, so daß nachträglich die Summe der Vektorkomponenten 1 ergibt (siehe Zeile 4f und 7f)

Gruß
Eneldo

Benutzeravatar
michasch
DON'T PANIC
Beiträge: 42
Registriert: 2. Okt 2004 20:47
Wohnort: Dieburg
Kontaktdaten:

Re: Übung 5: HITS Startwerte?

Beitrag von michasch »

Hallo,

danke für die rasche Antwort. Es hilft ein wenig weiter, klärt aber noch nicht alle Fragen.
Ich hatte Herrn Fürnkanz so verstanden, dass a(v) und h(u) reele Zahlen und keine Vektoren sind (links neben dem Pseudocodekasten auf Folie 10). Sie sind ja auch ohne Vektorpfeil dargestellt und auch leichter zu vergleichen wie Vektoren: Wie wird bestimmt welche Authority wichtiger ist, wenn man die Authorities nur als Vektoren gegeben hat? Bei reelen Zahlen nimmt man einfach die Größere...
Auch in der Übungsaufgabe ist ja angegeben, dass man bei der iterativen Variante abbrechen soll, sobald sich die Zahlen nicht mehr als 1/10000 ändern. Das klingt für mich mehr nach reelen Zahlen denn nach Vektoren.
E ist laut Folie 10 die Nachbarschaftsmatrix. Sind die Startknoten dabei die Zeilen oder die Spalten?
Wofür stehen die Vektoren a_0 und h_0 im Pseudocode? Die tauchen sonst auch nirgends auf.

Grüße,
michasch
Ich denke, also bin ich - manche sind trotzdem.

TheAcid
Erstie
Erstie
Beiträge: 16
Registriert: 1. Nov 2004 21:49
Kontaktdaten:

Re: Übung 5: HITS Startwerte?

Beitrag von TheAcid »

michasch hat geschrieben: Ich hatte Herrn Fürnkanz so verstanden, dass a(v) und h(u) reele Zahlen und keine Vektoren sind (links neben dem Pseudocodekasten auf Folie 10). Sie sind ja auch ohne Vektorpfeil dargestellt und auch leichter zu vergleichen wie Vektoren: Wie wird bestimmt welche Authority wichtiger ist, wenn man die Authorities nur als Vektoren gegeben hat? Bei reelen Zahlen nimmt man einfach die Größere...
a und h sind auch für jeden Knoten reelle Zahlen. In dem Pseudocode werden sie aber als Vektor geschrieben, was den Algo auch sehr erleichtert. Dabei ist für den a-Vektor der erste Eintrag einfach der Authority-Score vom ersten Node etc. Du hast also nur einen a-Vektor und einen h-Vektor.
michasch hat geschrieben: E ist laut Folie 10 die Nachbarschaftsmatrix. Sind die Startknoten dabei die Zeilen oder die Spalten?
AFAIK ist in einer Adjazenzmatrix die Zeile der Start und die Spalte das Ziel, oder?
michasch hat geschrieben: Wofür stehen die Vektoren a_0 und h_0 im Pseudocode? Die tauchen sonst auch nirgends auf.
Das haben wir uns auch gefragt und letztlich für nen Druckfehler gehalten. Es könnte ja der a-Vektor vor der ersten Iteration sein, aber das macht keinen Sinn (wäre 1-Vektor, daher keine Veränderung in den Iterationen).
In four short steps we can erase this

Benutzeravatar
michasch
DON'T PANIC
Beiträge: 42
Registriert: 2. Okt 2004 20:47
Wohnort: Dieburg
Kontaktdaten:

Re: Übung 5: HITS Startwerte?

Beitrag von michasch »

Ok, so macht das Sinn. Danke!

Ich habe jetzt a_0 bzw. h_0 so interpretiert, dass diese den Zustand des Vektors zu Beginn des Schleifendurchlaufs repräsentieren. Das simuliert das "gleichzeitige" aktualisieren der beiden Vektoren. Da zu dem Zeitpunkt, wo h_0 bzw. a_0 verwendet werden h ja schon modifiziert wurde, verfälscht das ggf. die Ergebnisse.
Ich denke, also bin ich - manche sind trotzdem.

Antworten

Zurück zu „Web Mining“