[alg] Grote database doorzoeken op overeenkomsten *

[Data-base]

Goedendag,

Voor een soort van anti-fraude systeem moet ik een invoerbestand vergelijken met een grote database om te kijken naar mogelijke overeenkomsten. Het probleem is echt dat ik dus een stuk tekst (zeg een 500 woorden) moet vergelijken met ong een duizendtal artikelen van tussen de 200 en 2000 woorden. Echter kan ik hier geen fatsoenlijke algoritme voor vinden/bedenken.
Het enige wat enigszins in de buurt komt is Karp-Rabin (wat woorden hasht en dan hashes vergelijkt, als ik het goed begrepen heb?). Echter, het is te onnauwkeurig om per zin te hashen en te vergelijken(1 woord hoeft maar anders te zijn en de hash matcht niet) en te traag om per woord te vergelijken en aantal matches bij te houden.
Iemand nog ideeen over hoe ik dit aan kan pakken?

Oops, "database" mist in de topictitel

[RobIII]

Ik zou eens kijken naar Fuzzy string searching -> Similarity functions. Misschien dat je daar iets in kunt vinden? Ik heb dit niet helemaal gelezen en/of geanalyseerd, maar misschien heeft de auteur wel een punt

[ Voor 29% gewijzigd door RobIII op 14-03-2007 01:25 ]

[MSalters]

Hier zou je zonder problemen een M.Sc. thesis over kunnen schrijven, als je dataset groter zou zijn.

Grofweg gezegd is de truc om een afstandsmaat te definieren, vervolgens de afstanden te bepalen tot de de andere artikelen, en dan te kijken of deze verdacht laag is. Dat kan in dit geval behoorlijk brute-force. Laat het bepalen van zo'n afstandsmaat 2 seconden duren, dan nog zijn 1000 matches minder dan een uur CPU tijd, plus het is embarrassingly parallel.

Ik vermoed echter dat het geen 2 seconden hoeft te duren. Filter veelvoorkomende en weinig relevante woorden, pas "stemming" toe, bouw een woordindex op voor de resterende woorden(en voor bonuspunten, link synoniemen) en je kunt elke zin vervolgens als een vector zien.

[Verwijderd]

MSalters schreef op woensdag 14 maart 2007 @ 20:55:
Ik vermoed echter dat het geen 2 seconden hoeft te duren. Filter veelvoorkomende en weinig relevante woorden, pas "stemming" toe, bouw een woordindex op voor de resterende woorden(en voor bonuspunten, link synoniemen) en je kunt elke zin vervolgens als een vector zien.

Maar als je het zo geavanceerd maakt, krijg je dan niet dat op een gegeven moment een tekst ook hetzelfde wordt gezien als deze hetzelfde argument uitlegt van een stelling? Dat lijkt me niet echt wenselijk. Bij wetenschappelijk denken zullen er ongetwijfeld dezelfde argumenteringen zijn. Deze gebruiken dan een andere zinsbouw, en synoniemen voor veel woorden.

[Data-base]

RobIII schreef op woensdag 14 maart 2007 @ 01:22:
Ik zou eens kijken naar Fuzzy string searching -> Similarity functions. Misschien dat je daar iets in kunt vinden? Ik heb dit niet helemaal gelezen en/of geanalyseerd, maar misschien heeft de auteur wel een punt

Hmm, zoiets zocht ik inderdaad. Ik zal het zeker doorlezen. Heb nu ook een aantal artikelen op acm gevonden. Ziet er veel belovend uit.

MSalters: Denk dat wat dot zegt idd wel voorkomt als ik het zo geavanceed maak. Het moet zo zijn dat teksten over precies dezelfde onderwerp niet gematcht moeten worden. Enkel als de teksen inhoudelijk en qua zinsbouw en opmaak overeen komen.

Bedankt voor de reacties kan weer vooruit. Andere reacties zijn natuurlijk nog welkom

[Pete]

Data-base schreef op donderdag 15 maart 2007 @ 12:36:
... Het moet zo zijn dat teksten over precies dezelfde onderwerp niet gematcht moeten worden. Enkel als de teksen inhoudelijk en qua zinsbouw en opmaak overeen komen....

Waarom niet de gelijkende teksten eerst opzoeken en dan met dat select aantal teksten gaan kijken of er zinmatches in zitten? Op die manier kun je eerst de grote bulk data verkleinen tot een kleiner probleem

[ACM]

Zo'n distance matrix is trouwens vrij eenvoudig in een SQL-omgeving te bouwen (mogelijk zelfs in mysql), ook met een sparse matrix (geen 0-en opslaan). Ik heb het zelf in postgresql gebouwd om uit 43k van onze eigen nieuwspostings dmv K-Means een binaire boom van clusters (op elkaar lijkende documenten) te maken. Het geheel heb jij op zich niet zo veel aan, maar de distance-calculatie (document - cluster afstand) is prima te gebruiken om van een nieuw document te bepalen op welke in de al bestaande dataset hij lijkt. En ook die distance-calculatie kan in SQL (iig in postgresql).

Dat opzoeken van de afstand van een document tot een cluster kon ik - als ik het me goed herinner - in de orde van grootte van zo'n 1000 document-clusterafstanden per seconde uit drukken op een vrij eenvoudige sempron doos. Met documenten die gemiddeld meer unieke woorden hebben wordt het natuurlijk lastiger, maar zodra je stopwoorden en te unieke termen laat vervallen uit je matrix moet je een heel eind kunnen komen.

Als je dan een serie documenten hebt gevonden die op basis van de individuele termen sterk op elkaar lijken kan je vervolgens nog moeilijkere algoritmen loslaten. Je kan ook proberen te achterhalen wat diverse universiteiten gebruiken om te bekijken of een ingestuurde paper wel door de student zelf is geschreven.

[Data-base]

phsmit schreef op donderdag 15 maart 2007 @ 15:23:
[...]


Waarom niet de gelijkende teksten eerst opzoeken en dan met dat select aantal teksten gaan kijken of er zinmatches in zitten? Op die manier kun je eerst de grote bulk data verkleinen tot een kleiner probleem

Dat doe ik al. Initieel moet ik meer dan 100k records. Pak eerst die records die relevant zijn