Zoekmachine bouw

[Verwijderd]

Context
Ik ben samen met een medestudent bezig met een afstudeerproject. Het afstudeerproject is het maken van een kennisbank voor artikelen, personen, bedrijven, commentaren, een FAQ etc. We hebben een vrij solide database ontwerp gemaakt, een strikt gescheiden MVC ontwerp voor de backend en interface.

Een van de onderdelen van de kennisbank is de zoekmachine. De zoekmachine moet van een gegeven term relevante resultaten in alle objecten in de database kunnen geven (een persoon, een bedrijf of een artikel bv). Een artikel heeft bijvoorbeeld een body en/of een attachment. De zoekmachine zoekt ook in attachments (HTML-, Word-, PDF bestanden etc).

Ontwerp

Het ontwerp van de database is zo generiek mogelijk gemaakt, zodat het eenvoudig toegepast kan worden als kennisbank van diverse onderwerpen. In grote lijnen is een gedeelte van de database als volgt:

OBJECT
objectid
creationdate
modifydate

ARTICLE
objectid --> OBject.objectid
Title
Abstract
Body

PERSON
Objectid --> Object.objectid
Name
Address
Telephone

ATTACHMENT
Objectid --> Object.objectid
FileType
FileName
Path

OBJECT_ATTACHMENT #Link tabel om artikelen en attachments te linken
Objectid1
Objectid2

INTERN_LINK #Link tabel om artikelen te linken
Objectid1
Objectid2

Zoekmachine

Ik heb mijn zoekmachine als volgt opgebouwd. Er is een lijst met tabelnamen, hiervan vraag ik alle velden op:

1) Ik lex alle termen die in de velden voorkomen

2) Van elke term bepaal ik de Term Frequency

3) Ik zet de term, met de Term Frequency in een 'indextabel'

4) Nu heb ik alle termen uit alle objecten uit de database. Nu loop ik de indextabel af

5) Voor elke term bepaal ik nu de Term Frequency - Inverse Document Frequency

6) Ik bepaal daarna voor elke term het gewicht (komt het in een titel voor weeg het zwaarder dan in een body bv)

7) Ik neem het product van het gewicht en de TFIDF ( = totaalgewicht)

Ik verwijder alle termen met een lager totaalgewicht dan een bepaalde drempel

9) Ik heb nu een index van alle termen die in de database voorkomen, met het gewicht van die term en bij welk object het hoort

Bij een zoekopdracht kan ik nu eenvoudig een select statement uitvoeren als

code:

'SELECT ObjectId FROM INDEXDATA WHERE Term LIKE '%<zoekterm%' ORDER BY Totaalgewicht''

Dit werkt op zich correct. Ik krijg redelijk relevante zoekresultaten terug.

Vragen

Deze werkwijze heb ik bedacht door wat manieren te combineren, namelijk TFIDF en Termgewicht. Ik wil dit nog combineren met Pagerank

Welke manieren hebben jullie toegepast om relevante zoekresultaten te vinden? Ik kan me bijvoorbeeld indenken dat je de spreiding van een term over een document bepaald, en deze ook meeweegt. Als ik Google mag geloven zijn er tientallen, zoniet honderden algorithmes die meetellen... Ik heb moeite een goed document te vinden over het bouwen van een goede zoekmachine.

Wat vinden jullie van de hierboven beschreven manier?

Wat voor tips hebben jullie nog meer over het bouwen van een index van een zoekmachine?

Hoe ga je normaliter om met meerdere zoektermen? Ik kan bijvoorbeeld (bij 2 zoektermen) apart zoeken naar beide termen, en een intersectie van de resultaten als resultaat teruggeven. Maar dit kan weer niet als men de beide termen bij elkaar wil zoeken (zoals Google bv). Dan zou ik de hele context van een term moeten cachen.

Alle tips over zoekmachinebouw zijn welkom

[Alarmnummer]

Zoek eens op Lucene en Nutch voor meer informatie.

Welk platform ga je gebruiken? Java/.net ?

[Verwijderd]

Alarmnummer schreef op dinsdag 19 december 2006 @ 08:55:
Zoek eens op Lucene en Nutch voor meer informatie.

Welk platform ga je gebruiken? Java/.net ?

De index aanleggen word gedaan mbv Python (in mijn ogen, de taal bij uitstek voor dit soort taken). Als databaseserver gebruiken we (helaas) MySQL (had zelf liever Postgresql gebruikt, maar zitten met beperkingen bij de opdrachtgever)

[ Voor 17% gewijzigd door Verwijderd op 19-12-2006 10:12 ]

[Alarmnummer]

Verwijderd schreef op dinsdag 19 december 2006 @ 10:10:
[...]
De index aanleggen word gedaan mbv Python (in mijn ogen, de taal bij uitstek voor dit soort taken).

Tja.. persoonlijk denk ik dat scripting talen toch minder interessant zijn voor dit soort problemen ivm performance en robuustheid. Maar ik heb het gevoel dat we dan in een totaal oninteressante holy war terecht komen (en ja, ik weet dat google veel met python doet).

Er is trouwens wel een Python versie van Lucene (als ik het me goed weet te herinneren).

Als databaseserver gebruiken we (helaas) MySQL (had zelf liever Postgresql gebruikt, maar zitten met beperkingen bij de opdrachtgever)

Aha ok. Maar kijk in ieder geval even naar Lucene en alle documentatie die er bij zit. Ook op de mailinglist is erg veel gepost over allerlei problemen. Lucene in action is trouwens ook zeker een aanrader.

[ Voor 7% gewijzigd door Alarmnummer op 19-12-2006 11:04 ]

[Compusmurf]

-

[ Voor 100% gewijzigd door Compusmurf op 19-12-2006 11:27 . Reden: foutje ]

[BestTested!]

Verwijderd schreef op maandag 18 december 2006 @ 20:19:
Context
.....Welke manieren hebben jullie toegepast om relevante zoekresultaten te vinden? Ik kan me bijvoorbeeld indenken dat je de spreiding van een term over een document bepaald, en deze ook meeweegt. Als ik Google mag geloven zijn er tientallen, zoniet honderden algorithmes die meetellen... Ik heb moeite een goed document te vinden over het bouwen van een goede zoekmachine.

Ik heb toevallig voor mijn bachelor ook een klein onderzoekje moeten doen. Gaat over het zoeken/matchen van documenten in een help-desk database.
Keyword Identification for Service-Desk Call Classification

Misschien heb je er iets aan. Hoewel het wetenschappelijk niet erg goed in mekaar zit, geeft het wel een overzichtje van mogelijke algoritmes die je kan gebruiken om je performace te verbeteren. Zo kwam er namelijk uit dat het verwijderen van stopwoorden met behulp van een stopwoorden-lijst toch een redelijke grote (positieve) invloed heeft, ook al zou TF-IDF hier geen last van stopwoorden moeten hebben. Meer bevindingen vind je in de conclusie.

Voor goede documenten/boeken kan je mijn referenties misschien eens nakijken.

[Verwijderd]

BestTested! schreef op dinsdag 19 december 2006 @ 21:31:
[...]


Ik heb toevallig voor mijn bachelor ook een klein onderzoekje moeten doen. Gaat over het zoeken/matchen van documenten in een help-desk database.
Keyword Identification for Service-Desk Call Classification

Misschien heb je er iets aan. Hoewel het wetenschappelijk niet erg goed in mekaar zit, geeft het wel een overzichtje van mogelijke algoritmes die je kan gebruiken om je performace te verbeteren. Zo kwam er namelijk uit dat het verwijderen van stopwoorden met behulp van een stopwoorden-lijst toch een redelijke grote (positieve) invloed heeft, ook al zou TF-IDF hier geen last van stopwoorden moeten hebben. Meer bevindingen vind je in de conclusie.

Voor goede documenten/boeken kan je mijn referenties misschien eens nakijken.

Bedankt, dat is erg behulpzaam. Ik zal het doorlezen, super!

Waar ik ook erg benieuwd naar ben is hoe men bepaalt wat de drempelwaarde is waarbij je bepaalt welke TFIDF waarden relevant zijn, en welke 'stopwoorden'/irrelevante termen zijn? Zet je deze vast, of word deze dynamisch bepaald door de gemiddelde TFIDF waarde en het aantal documenten in de corpus?

Ik gebruik nu een combinatie, ik test de termen tegen een lijst van bekende stopwoorden, en daarna bepaal ik de TFIDF waarde van de overgebleven termen

[ Voor 4% gewijzigd door Verwijderd op 19-12-2006 22:53 ]

[BestTested!]

Verwijderd schreef op dinsdag 19 december 2006 @ 22:53:
[...]


Bedankt, dat is erg behulpzaam. Ik zal het doorlezen, super!

Waar ik ook erg benieuwd naar ben is hoe men bepaalt wat de drempelwaarde is waarbij je bepaalt welke TFIDF waarden relevant zijn, en welke 'stopwoorden'/irrelevante termen zijn? Zet je deze vast, of word deze dynamisch bepaald door de gemiddelde TFIDF waarde en het aantal documenten in de corpus?

Ik gebruik nu een combinatie, ik test de termen tegen een lijst van bekende stopwoorden, en daarna bepaal ik de TFIDF waarde van de overgebleven termen

De lijst met stopwoorden, is een vaste lijst, afkomstig van het Snowball project (NL bijdrage door Kraaij, '94). Een waarde voor de TF-IDF threshold heb ik niet gebruikt, ik heb het omgekeerd, alleen de beste x werden gebruikt.

Dit is mijn manier geweest, er zijn natuurlijk ook andere manieren te vinden.

[Verwijderd]

BestTested! schreef op dinsdag 19 december 2006 @ 23:47:
[...]


De lijst met stopwoorden, is een vaste lijst, afkomstig van het Snowball project (NL bijdrage door Kraaij, '94). Een waarde voor de TF-IDF threshold heb ik niet gebruikt, ik heb het omgekeerd, alleen de beste x werden gebruikt.

Dit is mijn manier geweest, er zijn natuurlijk ook andere manieren te vinden.

Toevallig gebruik ik dezelfde lijst, maar die kan evt later aangevuld worden. Op het moment werk ik op dezelfde manier, de hoge TFIDF waarde worden opgevraagd, de lage waarden komen helemaal onderaan de zoekresultaten dan. Het probleem van deze aanpak is dat de tabel waarde termen geindexeerd staan gigantisch word (heb nu +/- 250 documenten, dit resulteert al in een term indextabel van meer dan 400.000 records), en er komen uiteindelijk enkele duizenden documenten in, dus dan meer dan een miljoen termen in de indextabel. Ik wil deze indextabel opschonen door alle termen met een TFIDF waarde kleinder dan de drempel te verwijderen om de SELECT statements sneller te laten verlopen. Alleen heb ik moeite om de goede drempel te vinden (je wil geen relevante informatie kwijtraken)

[Verwijderd]

Wat ik begrijp uit deze opzet is dat het zoeken alleen mogelijk is op basis van een enkele zoekterm. Tegenwoordig zoeken mensen op een combinatie van meerdere zoektermen. De aanpak lijkt mij daarom ook nogal kort door de bocht.
Zelf gebruik ik voor de website voetbaltribune.nl een eigen aangepast variant van het Vector Space Model in combinatie met een Probablistisch Model.
Vector Space Model benadert documenten en zoekqueries als vectoren. Alle documenten zijn een vector in een N-dimensionale ruimte. De dimensie N is het aantal unieke woorden van het document. Dit geldt ook voor de zoekquery. Het VSM gaat er vanuit dat hoe kleiner de hoek tussen een query-vector en een document-vector is, hoe groter de similarity.

Wat in jou situatie geschikter lijkt is de volgende database structuur. In eerste instantie kan nog prima gewerkt worden zonder TF*IDF, maar voldoet de TF prima. Wanneer de document collectie statisch is, kan gekozen worden voor TF*IDF, maar bij een dynamische collectie legt het een grote slag op performance; ieder extra document heeft namelijk invloed op de TF*IDF van alle termen.

`index`
pk_index_id
fk_item_id
fk_word_id
frequency

`word`
pk_word
word
word_stemmed

`item`
pk_item_id
fk_object_id
length (de lengte van de vector van dit item, die bereken je als je het item indexeert vanwege performance)

Met de wiskundige formule; (A . / (|| A || x || B ||) bereken je vervolgens de similarity van een query B tegen een document A. Kost wel wat rekenwerk, maar dan heb je ook wat. Bij voetbaltribune.nl gebruik ik in princiepe dit algoritme om te bepalen of een nieuw nieuwsbericht al eerder geplaatst is en dus over hetzelfde onderwerp gaan.

Is dit ongeveer waar je aan zit te denken?

[Verwijderd]

Verwijderd schreef op woensdag 20 december 2006 @ 22:00:
Wat ik begrijp uit deze opzet is dat het zoeken alleen mogelijk is op basis van een enkele zoekterm. Tegenwoordig zoeken mensen op een combinatie van meerdere zoektermen. De aanpak lijkt mij daarom ook nogal kort door de bocht.
Zelf gebruik ik voor de website voetbaltribune.nl een eigen aangepast variant van het Vector Space Model in combinatie met een Probablistisch Model.
Vector Space Model benadert documenten en zoekqueries als vectoren. Alle documenten zijn een vector in een N-dimensionale ruimte. De dimensie N is het aantal unieke woorden van het document. Dit geldt ook voor de zoekquery. Het VSM gaat er vanuit dat hoe kleiner de hoek tussen een query-vector en een document-vector is, hoe groter de similarity.

Wat in jou situatie geschikter lijkt is de volgende database structuur. In eerste instantie kan nog prima gewerkt worden zonder TF*IDF, maar voldoet de TF prima. Wanneer de document collectie statisch is, kan gekozen worden voor TF*IDF, maar bij een dynamische collectie legt het een grote slag op performance; ieder extra document heeft namelijk invloed op de TF*IDF van alle termen.

`index`
pk_index_id
fk_item_id
fk_word_id
frequency

`word`
pk_word
word
word_stemmed

`item`
pk_item_id
fk_object_id
length (de lengte van de vector van dit item, die bereken je als je het item indexeert vanwege performance)

Met de wiskundige formule; (A . / (|| A || x || B ||) bereken je vervolgens de similarity van een query B tegen een document A. Kost wel wat rekenwerk, maar dan heb je ook wat. Bij voetbaltribune.nl gebruik ik in princiepe dit algoritme om te bepalen of een nieuw nieuwsbericht al eerder geplaatst is en dus over hetzelfde onderwerp gaan.

Is dit ongeveer waar je aan zit te denken?

Dit is ook zeker interessant, aangezien ik nu aanloop tegen het berekenen van TFIDF op een dynamische corpus. Ik moet 1) of van de hele corpus opnieuw de TFIDF uitrekenen of 2) met een hoop querys proberen dynamisch de TFIDF van de veranderde documenten uit te rekenen. Ik had idd naar het Vector Space Model gekeken, en het lijkt ook wel interessant te worden op deze manier

[Croga]

Verwijderd schreef op maandag 18 december 2006 @ 20:19:
Ontwerp

Het ontwerp van de database is zo generiek mogelijk gemaakt, zodat het eenvoudig toegepast kan worden als kennisbank van diverse onderwerpen. In grote lijnen is een gedeelte van de database als volgt:

OBJECT
objectid
creationdate
modifydate

ARTICLE
objectid --> OBject.objectid
Title
Abstract
Body

PERSON
Objectid --> Object.objectid
Name
Address
Telephone

ATTACHMENT
Objectid --> Object.objectid
FileType
FileName
Path

OBJECT_ATTACHMENT #Link tabel om artikelen en attachments te linken
Objectid1
Objectid2

INTERN_LINK #Link tabel om artikelen te linken
Objectid1
Objectid2

Ik zet grote vraagtekens bij de opbouw van je database.

Zoals je het nu ingericht hebt zijn alle tabellen (behalve de link tabellen) afhankelijk van het object ID. In feite zijn dus alle velden properties van het object. Dat betekend dus dat het ook gewoon in 1 tabel mag staan (aangezien alle velden afhankelijk zijn van dezelfde sleutel).
Dat betekend ook dat je Object link tabel overbodig is. Je "INTERN_LINK" tabel zie ik geen nut voor.

Dit betekend dus ook dat 1 persoon slechts 1 object kan aanmaken, of bij ieder object opnieuw zijn gegevens moet registreren. Ook dat lijkt mij niet juist.

Mischien is het slim de indeling van de database nog eens na te kijken. Als je daar moeite mee hebt volg dan gewoon de normalisatie procedure stap voor stap. Als er daarna nog zaken zijn die simpelweg onpractisch zijn kun je die alsnog aanpassen.

[Verwijderd]

Croga schreef op donderdag 21 december 2006 @ 09:54:
[...]


Ik zet grote vraagtekens bij de opbouw van je database.

Zoals je het nu ingericht hebt zijn alle tabellen (behalve de link tabellen) afhankelijk van het object ID. In feite zijn dus alle velden properties van het object. Dat betekend dus dat het ook gewoon in 1 tabel mag staan (aangezien alle velden afhankelijk zijn van dezelfde sleutel).
Dat betekend ook dat je Object link tabel overbodig is. Je "INTERN_LINK" tabel zie ik geen nut voor.

Dit betekend dus ook dat 1 persoon slechts 1 object kan aanmaken, of bij ieder object opnieuw zijn gegevens moet registreren. Ook dat lijkt mij niet juist.

Mischien is het slim de indeling van de database nog eens na te kijken. Als je daar moeite mee hebt volg dan gewoon de normalisatie procedure stap voor stap. Als er daarna nog zaken zijn die simpelweg onpractisch zijn kun je die alsnog aanpassen.

Ik volg je niet helemaal.

Het klopt inderdaad dat alle personen, artikelen, attachments etc. Object uitbreiden. (het gepresenteerde model is niet volledig, maar het was om aan te geven hoe de opbouw in elkaar zat). Een persoon is dus ook een 'object'. Hierdoor is het voor het zoeken eenvoudig om zoekresultaten uit alle soorten objecten weer te geven (een term kan voorkomen in een persoon, of in een attachment of artikel bijvoorbeeld).

de INTERN_LINK is om objecten te linken. Dit kan zijn een artikel aan een ander artikel, een persoon aan een artikel etc. De attachment link tabel is om het eenvoudiger te maken om te laten zien wat voor attachments bij een artikel (pdfje met een boek bv) of een persoon (een cv) horen.

Ik begrijp niet helemaal hoe je erbij komt dat een persoon maar 1 object mag aanmaken (een artikel heeft bijvoorbeeld een author, die linkt naar een persoon).

Nogmaals, het model zoals ik eerst beschreven heb is niet volledig, maar het was meer om de structuur aan te geven (alle artikelen, personen, attachments etc zijn objecten).

[Croga]

Verwijderd schreef op vrijdag 22 december 2006 @ 18:31:
Het klopt inderdaad dat alle personen, artikelen, attachments etc. Object uitbreiden. (het gepresenteerde model is niet volledig, maar het was om aan te geven hoe de opbouw in elkaar zat). Een persoon is dus ook een 'object'. Hierdoor is het voor het zoeken eenvoudig om zoekresultaten uit alle soorten objecten weer te geven (een term kan voorkomen in een persoon, of in een attachment of artikel bijvoorbeeld).

Waarom gebruik je dan voor ieder type object dezelfde sleutel? Dat gaat gegarandeerd mis....

Ofwel: Noem de sleutel van Persoon geen "ObjectID" maar gewoon "PersoonID". En zorg dat de tabel voor een artikel uitgebreid wordt zodat duidelijk is welke koppelingen er zijn.
De manier waarop het er nu staat is enorm verwarrend en zal dus bij eventueel onderhoud een vertragende factor zijn, ofwel: geld kosten. Door duidelijkheid in het ontwerp op te nemen zorg je dat onderhoud van de applicatie makkelijker wordt waardoor TCO omlaag gaat. Afijn; mischien heb ik iets teveel ervaring met de "business" kant

[BestTested!]

Om weer even terug te komen op het zoeken zelf:

Verwijderd schreef op woensdag 20 december 2006 @ 01:33:
[...]
... Het probleem van deze aanpak is dat de tabel waarde termen geindexeerd staan gigantisch word (heb nu +/- 250 documenten, dit resulteert al in een term indextabel van meer dan 400.000 records), en er komen uiteindelijk enkele duizenden documenten in, dus dan meer dan een miljoen termen in de indextabel. ...

En... welkom bij mijn Master Thesis onderwerp. Ik had precies hetzelfde probleem bij mijn onderzoek. Daarom ga ik nu verder door een paar niet-lineaire dimensie reducties uit te proberen zoals Isomap, locally linear embeddings en multidimensional scaling (waarom niet lineair? dat hebben anderen al gedaan, PCA, LSI). Heb al een aantal bronnen met veelbelovende resultaten. Het blijkt dat je met 2 dimensies bijna alle je belangrijke data kan omvatten.
(Spatial Visualisation of Document Similarity, Navarro, link heb ik zo niet)

Ik heb verder nog een Chi-squared test gedaan om de lijst nog meer in te slinken, redelijk eenvoudig/snel. Misschien eens de moeite om het te proberen. Enkel is dit echter meer een vorm van symptoom-bestrijding dan het probleem echt bij de oorzaak aan te pakken.

Verwijderd schreef op woensdag 20 december 2006 @ 22:00:
....
Met de wiskundige formule; (A . / (|| A || x || B ||) bereken je vervolgens de similarity van een query B tegen een document A. Kost wel wat rekenwerk, maar dan heb je ook wat. Bij voetbaltribune.nl gebruik ik in princiepe dit algoritme om te bepalen of een nieuw nieuwsbericht al eerder geplaatst is en dus over hetzelfde onderwerp gaan.....

Jouw formule geeft de cosinus afstand tussen twee punten, dit is inderdaad een veel gebruikte methode voor afstanden tussen documenten (zie ook mijn paper ). Welke ook vaak worden gebruikt om documenten te vergelijken zijn: dot-product similarity, shared-words similarity en overlap similarity