Applying K-means with Triangle Inequality on Apache Flink, with Applications in Intrusion Detection

Abstract

K-means er en av de mest brukte kluster-algoritmene, men den fungerer på en relativt naiv måte og majoriteten av distansekalkulasjonene den utfører er unødvendige. Tidligere forskning har bevist at ved å utnytte triangelaksiomet er det mulig å unngå majoriteten av disse distansekalkulasjonene og samtidig ende opp med de samme klustrene. I denne avhandlingen justerer vi k-means algoritmen slik at den kan fungere med et rammeverket for parallell prosessering kalt Apache Flink. I tillegg til dette vil vi evaluere ytelsen til både den originale k-means algoritmen og k-means som utnytter triangelaksiomet, fra et inntrengings og deteksjonssystem perspektiv.

Ytelseevalueringen blir gjennomført ved å følge kvantitative forskningsmetoder og vi bruker et oppsett under eksperimentene hvor vi tester begge algoritmene på det samme datasettet. Under eksperimentene bruker vi et datasett med nettverkstrafikk laget for å evaluere inntrengings og deteksjonssystemer kalt NSL KDD. To eksperimenter ble gjennomført. Ett eksperiment hvor vi holdt antall iterasjoner likt, men endret på antall kluster. I det andre eksperimentet holdt vi antall kluster likt, men endret på antall iterasjoner. Begge disse eksperimentene ble gjennomført med varierende grad av parallellisme.

Resultatene viser at når man bruker k-means med triangelaksiomet og bruker mange klustre finnes det ingen ytelsesforbedringer, snarere tvert imot. Et stort antall klustre førte til mye ekstraarbeid for iterasjonsfunksjonen i Apache Flink. Ved å bruke et mindre antall klustre og kjøre programvaren med flere parallelle instanser så observerte vi en økning i ytelse på 8.8% med k-means med triangelaksiomet i motsetning til den originale k-means algoritmen. Videre, når vi evaluerte k-means med triangelaksiomet med et varierende antall iterasjoner observerte vi bedre ytelse for alle testede verdier i forhold til den originale k-means algoritmen. Fra et inntrengings og deteksjonssystem perspektiv er dette lovende, da det ofte er et mindre antall klustre som brukes. Vi anbefaler likevel videre forskning for å minimere ekstraarbeidet i iterasjonsfunksjonen og dermed øke ytelsen ytterligere.

The well known clustering algorithm k-means is quite naive in its operation and many of the distance calculations it performs are unnecessary. Earlier research has shown that by exploiting the triangle inequality theorem the majority of distance calculations can be avoided, while still providing the same clustering result. In this thesis we aim to adjust k-means exploiting triangle inequality to operate on the parallel processing framework Apache Flink. Additionally, we evaluate the performance of both k-means and k-means with triangle inequality in an intrusion detection system environment.

The performance is evaluated by using a quantitative research approach where we apply a within-subjects research design to collect data. In the experiment we utilize the well known NSL KDD intrusion detection dataset. Two main experiments were performed. One where we kept the number of iterations static and varied the number of clusters, and a second experiment where we kept the number of clusters static and varied the number of iterations. Both experiments were repeated with a varying degree of parallelism.

Our results show that for a large number of clusters there are no increase in performance when clustering with k-means exploiting triangle inequality. A large number of clusters caused a large overhead in the iteration function of Apache Flink. However, with a lower amount of clusters and when performing the clustering over many parallel instances, a performance increase of up to 8.8% is observed. Furthermore, when evaluating the algorithms with a varying number of iterations we observed that there was a performance increase for all iteration values. The increase was most significant for a lower number of iterations. In an intrusion detection setting where a low number of clusters are used, the results are promising, but further research is needed in order to reduce the overhead and increase the performance further.