Okej, låt oss börja prata om DBSCAN.
Density-based spatial clustering of applications with noise (DBSCAN) är en välkänd algoritm för dataklustering som ofta används inom datautvinning och maskininlärning.
Baserat på en uppsättning punkter (låt oss tänka i ett tvådimensionellt rum som exemplifieras i figuren), grupperar DBSCAN punkter som ligger nära varandra baserat på ett avståndsmått (vanligen euklidiskt avstånd) och ett minsta antal punkter. Den markerar också som outliers de punkter som befinner sig i områden med låg densitet.
Parametrar:
DebSCAN-algoritmen kräver i princip 2 parametrar:
eps: anger hur nära punkterna ska vara varandra för att anses ingå i ett kluster. Det innebär att om avståndet mellan två punkter är lägre eller lika med detta värde (eps) anses dessa punkter vara grannar.
minPoints: det minsta antalet punkter för att bilda ett tätt område. Om vi till exempel ställer in parametern minPoints som 5 behöver vi minst 5 punkter för att bilda en tät region.
Parameteruppskattning:
Parameteruppskattningen är ett problem för varje datautvinningsuppgift. För att välja bra parametrar måste vi förstå hur de används och ha åtminstone en grundläggande förkunskap om den datamängd som kommer att användas.
eps: Om eps-värdet som väljs är för litet kommer en stor del av datamängden inte att klustras. Den kommer att betraktas som outliers eftersom inte uppfyller antalet punkter för att skapa en tät region. Å andra sidan, om det valda värdet är för högt kommer kluster att slås samman och majoriteten av objekten kommer att vara i samma kluster. eps bör väljas baserat på avståndet i datasetet (vi kan använda en k-distansgraf för att hitta det), men i allmänhet är små eps-värden att föredra.
minPoints: Som en allmän regel kan ett minimum minPoints härledas från ett antal dimensioner (D) i datamängden, som minPoints ≥ D + 1. Större värden är vanligtvis bättre för datamängder med brus och bildar mer signifikanta kluster. Minsta värde för minPoints måste vara 3, men ju större datamängden är, desto större värde för minPoints bör väljas.
Du kan läsa mer om parameteruppskattning här.
Varför ska vi använda DBSCAN?
DebSCAN-algoritmen bör användas för att hitta associationer och strukturer i data som är svåra att hitta manuellt men som kan vara relevanta och användbara för att hitta mönster och förutsäga trender.
Clusteringmetoder används vanligtvis inom biologi, medicin, samhällsvetenskap, arkeologi, marknadsföring, teckenigenkänning, ledningssystem och så vidare.
Låtsas oss tänka på en praktisk användning av DBSCAN. Anta att vi har en e-handel och vill förbättra vår försäljning genom att rekommendera relevanta produkter till våra kunder. Vi vet inte exakt vad våra kunder letar efter, men utifrån en datamängd kan vi förutsäga och rekommendera en relevant produkt till en specifik kund. Vi kan tillämpa DBSCAN på vår datamängd (baserad på e-handelsdatabasen) och hitta kluster baserat på de produkter som användarna har köpt. Med hjälp av dessa kluster kan vi hitta likheter mellan kunderna, till exempel om kund A har köpt 1 penna, 1 bok och 1 sax och kund B har köpt 1 bok och 1 sax, kan vi rekommendera 1 penna till kund B. Detta är bara ett litet exempel på användning av DBSCAN, men den kan användas i många tillämpningar inom flera områden.
Hur kan vi enkelt implementera den?
Som jag redan har skrivit (tips: tro inte på allt jag skriver) är DBSCAN en välkänd algoritm, därför behöver du inte oroa dig för att implementera den själv. Du kan använda ett av de bibliotek/paket som finns på internet. Här är en lista över länkar där du kan hitta DBSCAN-implementationen: Matlab, R, R, R, Python, Python.
Jag har också utvecklat en applikation (på portugisiska) för att förklara hur DBSCAN fungerar på ett didaktiskt sätt. Applikationen skrevs i C++ och du kan hitta den på Github.