Diversi risultati dall'implementazione LOF in ELKI e RapidMiner

Question

Ho scritto la mia implementazione di LOF e sto provando a confrontare i risultati con le implementazioni in ELKI e RapidMiner, ma tutti e 3 danno risultati diversi! Sto cercando di capire perché.

Il mio set di dati di riferimento è monodimensionale, 102 valori reali con molti duplicati. Proverò a postarlo qui sotto.

In primo luogo, l'implementazione RapidMiner. I punteggi LOF sono molto diversi da ELKI e dai miei risultati; molti tornano con un LOF di infinito. Questa implementazione è stata confermata corretta?

I miei risultati sono simili a ELKI, ma non ottengo esattamente gli stessi valori di LOF. Da una rapida scansione dei commenti nel codice sorgente ELKI, penso che questo possa essere dovuto alle differenze nel modo in cui viene calcolato il k-vicinato.

Nella carta LOF, il parametro MinPts (altrimenti chiamato k) specifica il numero minimo. di punti da includere nel k-quartiere. Nell'implementazione ELKI, penso che stiano definendo il k-vicinato come esattamente k punti piuttosto che tutti i punti all'interno della distanza k o della distanza k-distinta. Qualcuno può confermare esattamente come ELKI costruisce il k-quartiere? Inoltre c'è una variabile privata che permette al punto stesso di essere incluso nel suo stesso vicinato, ma sembra che il default non lo includa.

Qualcuno sa di un set di dati di riferimento pubblico che ha i punteggi LOF allegati ai fini della convalida?

--- più dettagli seguono ---

Riferimento: Elki codice sorgente è qui:

http://elki.dbs.ifi.lmu.de/browser/elki/trunk/src/de/lmu/ifi/dbs/elki/algorithm/outlier/lof/LOF.java

RapidMiner codice sorgente è qui:

http://code.google.com/p/rapidminer-anomalydetection/source/browse/trunk/src/de/dfki/madm/anomalydetection/evaluator/nearest_neighbor_based/LOFEvaluator.java

Qui è il mio set di dati di prova:

4,32323 5,12595 5,12595 5,12595 5,12595 5,7457 5,7457 5,7457 5,7457 5,7457 5,7457 5,97766 5,97766 6,07352 6,07352 6,12015 6,12015 6,12015 6,44797 6,44797 6,48131 6,48131 6,48131 6,48131 6,48131 6,48131 6,6333 6,6333 6,6333 6,70872 6,70872 6,70872 6,70872 6,70872 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,10361 7,10361 7,10361 7,10361 7,10361 7,10361 7,10361 7,10361 7,15651 7,1 5651 7,15651 7,15651 7,15651 7,15651 7,15651 7,15651 8,22598 8,22598 8,22598 8,22598 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538

Per esempio, ricevo il seguente punteggio LOF per il primo numero (4,32,323 mila):

• RapidMiner: infinito (con MinPts limiti inferiore/superiore impostati su 10.100)
• Elki: 2.6774 (con k = 10 e distfunction/reachdistfunction impostato di default)
• mia realizzazione: 1,9531

Alcune maggiori dettagli su quello che la mia applicazione sta facendo:

1. MinPts è 10, così ho' Sto trovando i 10 vicini distinti del punto. Quindi il vicinato di 4.32323 è in realtà 48 punti, da 5.12595 a 6.77579.
2. Questo mi dà una distanza k-distinta di 2,45256
3. Sto calcolando la distanza raggiungibilità del primo prossimo come 1,58277
4. Sto calcolando la LRD del campione come 1/(99,9103/48)
5. Somma di LRD (o)/LRD (p) per tutti i 48 vicini è 93,748939
6. Dividere per 48 per ottenere un LOF di 1,9531

Answer 1

io non sono davvero sorpreso differiscono. Potresti anche aggiungere l'implementazione di LOF di Weka e probabilmente otterrai un'altra risposta.

Ecco un'altra differenza da aggiungere alle equazioni: per quanto ne so, l'implementazione di rapidminer unisce i punti con le stesse coordinate. Ma forse, hanno dimenticato di prendere in considerazione questi pesi durante il calcolo dei vicini più vicini!

Nel contesto del database classico, è possibile che non unisca le coordinate duplicate in un'unica osservazione. Sono ancora record di database validi e devono essere contati come record completi.

Non so se alcuni di questi eseguono un preelaborazione automatica dei dati come riscalare il set di dati.

L'implementazione ELKI è stata verificata rispetto a un certo numero di esempi di libri di testo che usiamo per l'insegnamento.

Tuttavia, nell'algoritmo ci sono casi d'angolo che non sono fissi al 100%, quindi c'è spazio per la differenza anche nelle implementazioni "letterali" dell'algoritmo. Hai già eseguito in tre di questi:

1. Come per il trattamento di punti duplicati: A) aggregato, B) goccia, C) considerano diverso

   Da un punto di data mining di vista, C è corretta, e A (se implementato correttamente) è un'ottimizzazione che può farti risparmiare calcoli a distanza inutili. B è la vista matematica comune, ma non ha molto senso per un contesto di database. Se ho due "John Doe", sono la stessa persona?

2. Definizione di k vicini più vicini e k-distanza.

   La definizione normale di k-distance è: la distanza minima, tale che almeno k osservazioni siano contenute. Quando si esclude il punto di interrogazione, si ottiene inverval fino a 5.7457 dal punto di partenza: ci sono altre 10 osservazioni in un raggio di 5.7457 - 4.32323.

   I k vicini più vicini sono generalmente definiti come qualsiasi punto all'interno di questa distanza, che può essere maggiore di k.Ma poi tutti gli oggetti aggiuntivi devono avere la stessa distanza del kth! Sembra come se RapidMiner utilizza esattamente k, che non si allinea con la pubblicazione LOF (vedi definizione 4 nella pubblicazione LOF!)

   E 'davvero i vicini più vicini k (compresi i legami, ma a parte questo non di più di k oggetti), non il più piccolo distinto distanza. Da dove hai preso il "distinto"?

   Le definizioni 3 e 4 nella pubblicazione LOF sono piuttosto chiare sugli usi LOF del kNN.

   Il vostro vicinato di 48 oggetti non è quindi corretto.

3. cosa fare se ci sono più di MinPts duplicare punti (un'implementazione letterale produrrà una divisione per zero, ma per ovvie ragioni il punto dovrebbe essere dato un LOF di 1,0)

   Questo è forse ciò che è succede a Rapidminer.

E poi c'è distanza raggiungibilità: questo è davvero difficile , perché non è una distanza matematica. È asimmetrico.

La raggiungibilità della prima osservazione dal secondo sembra essere il k-distanza del secondo, che da un rapido sguardo (no doppio controllo) reach-dist(x[0], x[1]) = max(5.97766 - 5.12595, 5.12595 - 4.32323) = 0.80272

Vedere my extensive tutorial slides on outlier detection per un passo-passo dimostrazione passo passo di come calcolare LOF. Per quanto posso dire, questo è letteralmente LOF. Non tocca tutti i casi d'angolo, ma motiva il design dell'algoritmo LOF ed è abbastanza esauriente.

Answer 2

Se si utilizza l'estensione di rilevamento anomalie per RapidMiner [1] (non il LOF incorporato), si otterranno i risultati corretti. Il LOF incorporato è rotto. Questi sono gli stessi risultati di ELKI. Questa implementazione è molto più veloce di ELKI perché è multi-threat e utilizza anche molta meno memoria. Può anche gestire i duplicati (anche più di k + 1), dove ELKI lancia eccezioni. (Sulla base di k-distinta)

migliore, Hans

[1] http://marketplace.rapid-i.com/UpdateServer/faces/product_details.xhtml?productId=rmx_anomalydetection