This is part 1 of my summary of my recent learnings on unsupervised machine learning for anomaly detection algorithms.

My background in writing this is that I took Data 100, EE 127, and the beginning parts of a few ML and DL courses back in uc berkeley cs undergrad.

I’m working on a Congested Network Detection project so I wanted to share my learning journey in the spirit of learning in public

This is from 2016 so it’s not exactly hot but in the spirit of pick up what the put down I’ll be putting the models from this paper into my casual simpler terms so it might be easier for college or new grads like me to read through if you don’t have too much background. If you’d like a more academic version of this article, this might be good.

If you don’t have a CS or math background I’ve included many links so you can jump in the rabbit hole and learn adjacent topics to get an idea of what the terms mean.

I didn’t know this, but turns out there are further types within unsupervised learning, and we’ll go from left to right:

This is not the standard k-nn I learned in data 100 as that is for CLASSIFYING

essentially, given a data point you choose k of the nearest neighbors around you.

then you either take

A: the kth neighbors distance (this is called kth-NN)

B: the k neighbors average distance (called k-NN)

to that single data point to give an anomaly score for that point.

the higher the anomaly score, the more likely that point is an anomaly.

Often we choose 10 < k < 50

in CLASSIFICATION I learned in data 100 we used cross-validation to find a good k value. However we are missing labels here so we can’t do that :(

Here’s a nice graph from the paper of k-NN in action!

See from this graph how the k-NN can’t detect the weirdos close to the groupies and have small balls ;(

in order to find these local weirdos hiding behind the clusters we introduce LOF!

now we have a new score to highlight local outliers using density as follows:

1. find the k nearest records for data point x

2. we calculate the Local Reachability Density (LRD) as follows:

d_k( . ) is the reachability distance (usually the euclidean <read: logical> distance from point x to o, members of the set of nearest neighbors N_k of x).

we divide by the cardinality <read: size of the set> of the set of nearest neighbors, N_k

we then take the inverse of this normalized score so smaller LRD = less density ＆ vice versa

Finally we take a sum of the comparisons of the LRD of point x with the LRD of it’s k neighbors and normalize again to get the LOF:

so the LOF score is the sum of the ratio of local densities of k neighbors compared to a single point x

which means similar density points get around a point of 1 because it’s nearly dividing my the same numbers.

if an point is less dense than the others, you get a large score ;)

since we are using only k neighbors to say if a point is an anomaly, you’ll get a large amount of false positive global anomalies if you’re looking for that.

for global weirdos go back to 1A) k-nn

the author of the algo also reccomends you take an ensemble approach <read: you group up a bunch of methods> of taking the max of finding the LOF up to some uppebound of a k value for every point.

but we have a weakness!!!!!

(oh no)

taking the euclidian distance <read: the geometric point to point distance> assumes data is usually distributed spherically round each other. this is because in 2D - distances the same distance is around a radius from that point. This same problem occurs in n-dimensions for n > 2

here are the sad facts ;(

So instead we use a shortest path using a “chaining distance” which still seems relavent today

$chaining disntace = d_chain(x, y) = d(x, y) * (k-2) / (k-1)$

where

• k = number of nearest neighbors used

• d(x, y) = distance between x and y

the minimum sum of all distances connecting all k neighbors and the instance is written in the paper but I couldn’t find the original paper on google scholar and claude.ai gave me the equation above and it seems legit

another down side of LOF is that fails to score points at the border of two different clusters of varying density.

we tackle this problem by looking at the reverse neighbors! so confusing.

but graphically this is intuitive as above. it takes in the neighborhoods of all the clusters around them so it takes an average of the happening around the point.

note that the reverse neighbor set can contain any amount, depending on the data.

scores are more accurate here with various density clusters close to eachother

thats perfect for binary labels.

but where do we set the cut off to say what is an anomaly? it’s not clear ;(

so we output the probability that a point is an outlier instead of a direct score ;)

we use some neat tricks to make the function spit out probabilities:

1. since distances are always positive, LoOp assumes distributions are Half-Gaussian. Which means we can use the standard deviation, called the Probablistic Set Distance (PSD) as the estimation for density of points.

We normalize and get the following equation. you can see the short paper here to get into the detailed proofs and how we got here:

to simplify you can think of

1. PLOF as the actual density around some point o

2. nPLOF as the standard deviation of the PLOF values (and root(2) as a normalizing constant)

3. erf = gaussian error function = cdf of gaussian that turns he input into a probability

4. we ignore negatives

so percentages seem more accurate then scores.

but maybe not.

if we have a 100% confidence, what does that mean? are we really that certain?

the whole issue above is some how we need to choose the perfect value for the hyper parameter k in our Nearest Neighbor approach.

instead we use a maximization approach

essentially, we use all possible values of k and take the max score, much like the ensemble method recommended for LoF.

view the details here bc its very mathy

however, removing the k problem comes w a price -O-

we take $O(n**3)$ time ;(((( <read: so sad>

hehehe use quad trees to approximate >;) the aLOCI math is here

now we got O(NLdg + NL(dg + 2d)) as run time !!!!!

where

d = number of dimensions (features we have per data point)

L = tree depth

N = input size (as usual)

g = number of quad trees to be used

but not yet!

sometimes its good, some times its bad <read: its like a human>

it turns out you need N trees instead of g

so we have O(N**2) for a reliable output ;(

next, we’ll take a look into using clustering techniques to avoid using k-values as a possible way to get away from the mystery k problem! <read: special k>

subscribe to stay updated on the next post!