Cookies op Tweakers

Tweakers maakt gebruik van cookies, onder andere om de website te analyseren, het gebruiksgemak te vergroten en advertenties te tonen. Door gebruik te maken van deze website, of door op 'Ga verder' te klikken, geef je toestemming voor het gebruik van cookies. Wil je meer informatie over cookies en hoe ze worden gebruikt, bekijk dan ons cookiebeleid.

Meer informatie
Toon posts:

[alg] Grote database doorzoeken op overeenkomsten *

Pagina: 1
Acties:

Onderwerpen


  • Data-base
  • Registratie: maart 2007
  • Laatst online: 04-01-2019
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
  • Registratie: december 2001
  • Laatst online: 10:16

RobIII

Admin Devschuur®

^ Romeinse 3 ja!

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 :P

RobIII wijzigde deze reactie 14-03-2007 01:25 (29%)

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Roses are red Violets are blue, Unexpected ‘{‘ on line 32.

Over mij


  • MSalters
  • Registratie: juni 2001
  • Laatst online: 21-02 22:13
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.

Man hopes. Genius creates. Ralph Waldo Emerson
Never worry about theory as long as the machinery does what it's supposed to do. R. A. Heinlein


  • DOT
  • Registratie: oktober 2002
  • Laatst online: 16-04-2016
quote:
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
  • Registratie: maart 2007
  • Laatst online: 04-01-2019
quote:
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 :P
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
  • Registratie: november 2005
  • Laatst online: 12-02 07:01
quote:
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

petersmit.eu


  • ACM
  • Registratie: januari 2000
  • Niet online

ACM

Software Architect

Werkt hier

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.

Saai uitzicht in je tuin? Hang er een foto voor!


  • Data-base
  • Registratie: maart 2007
  • Laatst online: 04-01-2019
quote:
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 :)
Pagina: 1


Apple iPhone 11 Microsoft Xbox Series X LG OLED C9 Google Pixel 4 CES 2020 Samsung Galaxy S20 4G Sony PlayStation 5 Nintendo Switch Lite

'14 '15 '16 '17 2018

Tweakers vormt samen met Hardware Info, AutoTrack, Gaspedaal.nl, Nationale Vacaturebank, Intermediair en Independer DPG Online Services B.V.
Alle rechten voorbehouden © 1998 - 2020 Hosting door True