Abstract-I detta dokument föreslås en ny definition av avståndsbaserad avvikelse och en algoritm, kallad HilOut, utformad för att effektivt upptäcka de översta n outliers av en stor och högdimensionell datauppsättning. Med tanke på ett heltal k definieras vikten av en punkt som summan av de avstånd som skiljer den från dess k närmaste granne. Outlier är de punkter poäng de största värdena på vikt. Algoritmen HilOut använder sig av begreppet rymdfyllningskurva för att linearisera datamängden, och den består av två faser. Den första fasen ger en ungefärlig lösning, inom en grov faktor, efter genomförandet av högst d 1 sorter och skanning av datamängden, med temporal kostnad quadratic i d och linjär i N och i k, där d är antalet dimensioner av datamängden och N är antalet punkter i datamängden. Under denna fas isolerar algoritmen kandidaten för att vara avvikande och minskar detta vid varje iteration. Om storleken på den här uppsättningen blir n, slutar algoritmen att rapportera den exakta lösningen. I den andra fasen beräknas den exakta lösningen med en slutlig genomsökning som ytterligare undersöker de kandidatavvikelser som återstod efter den första fasen. Experimentella resultat visar att algoritmen alltid stannar, rapporterar den exakta lösningen, under den första fasen efter mycket mindre än d 1 steg. Vi presenterar både en in-minnes- och diskbaserad implementation av HilOut-algoritmen och en grundlig skalningsanalys för verkliga och syntetiska datamängder som visar att algoritmen skalar väl i båda fallen.
Angiulli och Pizzuti REF definierade ett objekts avvikande poäng som summan av avstånden mellan objektet och dess närmaste grannar.
Outlier mining in large high-dimensional data sets
{'venue': 'IEEE Transactions on Knowledge and Data Engineering', 'journal': 'IEEE Transactions on Knowledge and Data Engineering', 'mag_field_of_study': ['Mathematics', 'Computer Science']}