‘High-density anomalies’ – De meest gekke normale gevallen in een dataset

Overheden, commerciële organisaties en onderzoeksinstituten verzamelen tegenwoordig een grote rijkdom aan data. Anomaliedetectie (AD) verwijst naar het analyseren van deze gegevensverzamelingen om ongebruikelijke gevallen te ontdekken. Een anomalie is een geval, of een groep gevallen, die op de een of andere manier afwijkt van de rest en niet goed past in de algemene patronen in de data. Deze ‘anomalies’ worden ook vaak aangeduid als ‘outliers’ (uitbijters), ‘deviants’, ‘novelties’ of ‘discords’. Anomaliedetectie kan gebruikt worden voor uiteenlopende doelen, zoals datakwaliteitsanalyses, fraudedetectie, beveiliging, procesmonitoring en datapreparatie.

Gevallen in de data (rijen, datapunten, ‘cases’ of ‘records’) worden doorgaans als ongebruikelijker beschouwd als ze met meer attributen afwijken of meer extreme of zeldzame waarden aannemen. Echter, het wordt ook erkend dat anomalieën kunnen afwijken op maar één of enkele attributen, terwijl de andere attributen juist geen ongewoon gedrag laten zien.

Een speciale afwijking in dit opzicht is de high-density anomaly (HDA). Dit is een geval dat afwijkt van de norm, maar voor wat betreft een aantal attributen ook in een gebied van de data ligt met een hoge dichtheid – in andere woorden is gepositioneerd tussen of is een lid van de meest normale gevallen. High-density anomalies kunnen geïnterpreteerd worden als afwijkingen die zich verschuilen in normaliteit, of zich verstoppen achter grote aantallen. Ze ‘proberen’ hun afwijking te maskeren door het meest normale gedrag te vertonen dat mogelijk is voor hun situatie. In tegenstelling tot traditionele anomalieën, die typisch worden gezien als geïsoleerde gevallen in een gebied in de dataset met een lage dichtheid, verschuilen high-density anomalies zich juist tussen de meest normale en veelvoorkomende datapunten. Ze worden als zodanig ook niet gedetecteerd door traditionele, standaard AD algoritmen, of, als dat toch het geval is, krijgen een bescheiden anomaliescore toebedeeld. Het vinden van HDA-gevallen impliceert het vinden van een oplossing voor het probleem van het balanceren tussen afwijkend en gewoon gedrag. Figuur 1 toont een aantal voorbeelden.

In het algemeen is een HDA aanpak vooral van belang als de dataset groot is en de analist zijn of haar kostbare tijd niet moet verdoen met ‘false positives’ (de zogenaamde oninteressante ruisgevallen).

Een dataset kan een grote hoeveelheid typen anomalieën herbergen (zie de publicatie “On the Nature and Types of Anomalies: A Review” voor een volledig overzicht van typen en van vijf fundamentele dimensies die de aard van anomalieën definiëren). Als we louter kijken naar de meest basale en natuurlijke vorm van HDA’s, dan zijn er maar enkele typen die zich ook kunnen manifesteren als high-density anomaly. Echter, in principe zouden alle anomalieën een HDA kunnen zijn als er aanvullende attributen in ogenschouw worden genomen.

Er zijn verschillende methoden om high-density anomalies te detecteren. Het HDA onderzoeksartikel introduceert twee algoritmische methoden. Dit betreffen raamwerken in de zin dat ze, als onderdeel van het algehele HDA detectieproces, gebruik maken van bestaande algemene AD algoritmen (bijvoorbeeld k-Nearest Neighbors, LOF of SECODA).

• Iterative Partial Push (IPP): Deze methode gaat iteratief door de dataset heen om zo de low-density gevallen uit de verzameling van anomalieën te filteren.
• Harmonic Mean Detection of HDAs (HMDH): Deze methode berekent een (gewogen of ongewogen) harmonisch gemiddelde van de scores voor normaliteit en abnormaliteit.

Meer informatie kan gevonden worden in het onderzoeksartikel, en de code om deze methoden te draaien kan gevonden worden op www.foorthuis.nl (zie de sectie ‘SECODA resources for R’).

De methoden zijn geëvalueerd middels diverse gegenereerde datasets en een geanonimiseerde steekproef uit de Polisadministratie. De evaluatie heeft aangetoond dat met name de Iterative Partial Push methode goed werkt en consistent goede resultaten voor alle datasets laat zien. Zonder ze te gebruiken in de context van de IPP- of HMDH-raamwerken kunnen veel traditionele, algemene AD algoritmen (zoals KNN, LOF en SECODA) de HDA’s vaak ook tot op zekere hoogte identificeren. Echter, in grote sets leveren deze algoritmen te veel ‘false positives’ op om praktisch bruikbaar te zijn. De reden hiervoor is dat de daadwerkelijke high-density anomalies ‘gemaskeerd’ worden door de geïsoleerde ruisgevallen (die nu ook als anomalieën worden beschouwd), hetgeen het zeer lastig maakt ze effectief te detecteren. Om alleen HDA’s te detecteren is het daarom nodig een pure HDA methode te gebruiken, zoals IPP of HMDH.

Het diagram hieronder toont de verschillen tussen het gebruiken van een traditioneel niet-HDA algoritme (links) en de IPP-methode die zich direct richt op het vinden van HDA’s (rechts).

References

• Akoglu, L., Tong, H., Koutra, D. (2015). Graph-Based Anomaly Detection and Description: A Survey. Data Mining and Knowledge Discovery 29, 3, pp. 626-688.
• Boddy, R., Smith, G. (2009). Statistical Methods in Practice: For Scientists and Technologists. Chichester, John Wiley & Sons.
• Eberle, W., Holder, L. (2007). Discovering Structural Anomalies in Graph-Based Data. In Proceedings of the 7th IEEE International Conference on Data Mining, Workshops (ICDM 2007), USA.
• Foorthuis R.M. (2020). Algorithmic Frameworks for the Detection of High-Density Anomalies. Presented at IEEE SSCI CIDM 2020 (Symposium on Computational Intelligence in Data Mining), December 2020, Canberra Australia.
• Foorthuis R.M. (2019). All or In-cloud: How the Identification of Six Types of Anomalies is Affected by the Discretization Method. In: Atzmueller M., Duivesteijn W. (eds). Artificial Intelligence. BNAIC 2018. Springer, Communications in Computer and Information Science, Vol. 1021, pp 25-42. DOI: 10.1007/978-3-030-31978-6_3
• Foorthuis, R.M. (2018). A Typology of Data Anomalies. In: Springer CCIS 854, Proceedings of the 17th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU 2018), Cádiz, Spain. DOI: 10.1007/978-3-319-91476-3_3
• Foorthuis, R.M. (2017). SECODA: Segmentation- and Combination-Based Detection of Anomalies. In: Proceedings of the 4th IEEE International Conference on Data Science and Advanced Analytics (DSAA 2017), Tokyo, Japan, pp. 755-764. DOI: 10.1109/DSAA.2017.35
• Foorthuis, R.M. (2020). On the Nature and Types of Anomalies: A Review. arXiv preprint, arXiv:2007.15634.
• Foorthuis, R.M. (2019). (Un)certain Anomalies in Income Data. Presented at the Mini-Symposium on Uncertainty in Data-Driven Systems, Utrecht University, January 28th 2019. DOI: 10.13140/RG.2.2.25232.76801
• Müller, E., Assent, I., Iglesias, P., Mülle, Y., Böhm, K. (2012). Outlier Ranking via Subspace Analysis in Multiple Views of the Data. In Proceedings of the 12th IEEE International Conference on Data Mining, Brussels, Belgium.
• Tan, P., Steinbach, M., Kumar, V. (2006). Introduction to Data Mining. Boston: Addison-Wesley.