Change search
ReferencesLink to record
Permanent link

Direct link
PRAAG Algorithm in Anomaly Detection
KTH, School of Electrical Engineering (EES).
2016 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Anomaly detection has been one of the most important applications of datamining, widely applied in industries like financial, medical,telecommunication, even manufacturing. In many scenarios, data are in theform of streaming in a large amount, so it is preferred to analyze the datawithout storing all of them. In other words, the key is to improve the spaceefficiency of algorithms, for example, by extracting the statistical summary ofthe data. In this thesis, we study the PRAAG algorithm, a collective anomalydetection algorithm based on quantile feature of the data, so the spaceefficiency essentially depends on that of quantile algorithm.Firstly, the master thesis investigates quantile summary algorithms thatprovides quantile information of a dataset without storing all the data point.Then, we implement the selected algorithms and run experiments to test theperformance. Finally, the report focuses on experimenting on PRAAG tounderstand how the parameters affect the performance and compare it withother anomaly detection algorithms.In conclusion, GK algorithm provides a more space efficient way to estimatequantiles than simply storing all data points. Also, PRAAG is effective in termsof True Prediction Rate (TPR) and False Prediction Rate (FPR), comparingwith a baseline algorithm CUSUM. In addition, there are many possibleimprovements to be investigated, such as parallelizing the algorithm.

Abstract [sv]

Att upptäcka avvikelser har varit en av de viktigaste tillämpningarna avdatautvinning (data mining). Det används stor utsträckning i branscher somfinans, medicin, telekommunikation, och även tillverkning. I många fallströmmas stora mängder data och då är det mest effektivt att analysera utanatt lagra data. Med andra ord är nyckeln att förbättra algoritmernasutrymmeseffektivitet till exempel genom att extraheraden statistiskasammanfattning avdatat. PRAAGär en kollektiv algoritm för att upptäckaavvikelser. Den ärbaserad på kvantilenegenskapernai datat, såutrymmeseffektiviteten beror i huvudsak på egenskapernahoskvantilalgoritmen.Examensarbetet undersöker kvantilsammanfattande algoritmer som gerkvantilinformationen av ett dataset utan att spara alla datapunkter. Vikommer fram till att GKalgoritmenuppfyllervåra krav. Sedan implementerarvialgoritmerna och genomför experiment för att testa prestandan. Slutligenfokuserar rapporten påexperiment på PRAAG för att förstå hur parametrarnapåverkar prestandan. Vi jämför även mot andra algoritmer för att upptäckaavvikelser.Sammanfattningsvis ger GK ett mer utrymmeseffektiv sätt att uppskattakvantiler än att lagra alla datapunkter. Dessutom är PRAAG, jämfört med enstandardalgoritm (CUSUM), effektiv när det gäller True Prediction Rate (TPR)och False Prediction Rate (FPR). Det finns fortfarande flertalet möjligaförbättringar som ska undersökas, t.ex. parallelisering av algoritmen.

Place, publisher, year, edition, pages
2016. , 50 p.
Series
EES Examensarbete / Master Thesis, TRITA-EE 2016:104
Keyword [en]
Anomaly detection, Collective Anomaly, Algorithm, Data Mining 1
Keyword [sv]
Detektion av avvikelser, kollektiv avvikelse, algorithm, datautvinning
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:kth:diva-194193OAI: oai:DiVA.org:kth-194193DiVA: diva2:1038685
External cooperation
SICS
Examiners
Available from: 2016-10-19 Created: 2016-10-19 Last updated: 2016-11-15Bibliographically approved

Open Access in DiVA

fulltext(2091 kB)12 downloads
File information
File name FULLTEXT01.pdfFile size 2091 kBChecksum SHA-512
2811b9ca2e7d404a8adffc50108306c33c26d242564e36845a882a1c21e14a2ae4020ff426cd8661b95b802b3bbe53abd2dda4693461ad97422a1f179e6df553
Type fulltextMimetype application/pdf

By organisation
School of Electrical Engineering (EES)
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 12 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 11 hits
ReferencesLink to record
Permanent link

Direct link