6. Distance Based Learners

• supervised learning technique for both

  • regression

  • classification

• can also be used for unsupervised anomaly detection

• a single hyperparameter k -> number of neighbors

• find decision surfaces in space

• -> so that new point can be classified

• classify new point based on its neoghborhood

• -> no training phase

• -> (training) datapoints are model themselves

algo:

• for new datapoint

  • compute distance to all other datapoints

  • select k nearest instances

  • assign class by majority vote

• sum the difference of all vector elements power p

• take p-th root of it

• -> the higher p, the more it becomes a square

• high k -> higher bias -> herd

• low k -> higher variance -> respect locality

• training O(1) (we only have the datapoints… -> no actual training phase…)

• classifying O(n) (compute distance to all n datapoints…)

• 2 vs 2 vs 1…

• we have training data with (x1, x2) y

• -> classify new instance by averaging over k-nearest points y value…

• given: dataset without labels (no y value)

• for all xi: calculate li: mean distance to nearest k-neighbors

• define some threshold C

  • all xi for which li < C are normal

  • while all points for which li >= C are anomalous (GREATER EQUAL)

• two points further away still count into the k neighbors

• -> i.e. outlying cluster of 4 points would be normal as they have themselves as k near neighbors…

• density based spatial clustering of applications with noise

• -> unsupervised anomaly detection technique

• group together points that are closely packed

• marking points as outliers that lie alone in low-density regions

• given:

  • distance epsilon (similar to C -> threshold)

  • integer m (similar to K)

mark different point classes:

• core point

• directly reachabnle point

• outliers

• point p

• where at least m points are within distance epsilon

• point q is directly reachable

• if it is within distance epsilon of core point

• points which are not reachable

• no need to specify number of clusters beforehand (contrary to e.g. k-means)

• can find arbitrary, non linearly separable clusters

• requires only two parameters

  • m

  • epsilon

• not entirely deterministic

  • border points reachable from two clusters may be part of either cluster

  • depending on order of data processing

• curse of dimensionality

• m:

  • the higher

    • the less and smaller the clusters

    • the more the outliers

• distance epsilon:

  • if too small

    • data will not be clustered

  • if too large

    • no outliers

• rule of thumb:

  • m = 2*dim

use an algorithm

1. find distance to nearest neighbor (not neighborsss) for all points and sort

2. plot results: instances on x, epsilon on y axis

3. select epsilon where “change is most pronounced”

=> meaning of (x,y) in plot:

• i.e. (200, 0.19)

  • 199 points have their nearest neighbors closer than 0.19

• calculate distance to m nearest neighbors

• sum up and divide by m

• -> create list of distances and sort

• -> plot with y-axis being the distance

• -> x-axis being the instances of the (sorted) list…

• -> again, choose point with most pronounced change as good distance choice

• increasing sparsity

• distance measure loses meaning

• increased computational complexity

• overfitting

• volume of space increases exponentially

• data points become more spread out

• harder to identify meaningful clusters or neighborhoods

• in high dimensional spaces

• -> distance between pairs of points become increasingly more similar

• one can still say in which direction we get closer…

• DBSCAN and KNN cannot use L2 (or any Lp) for large d

• -> use fractional metrics (0 < L < 1) also not really good

  • not real metrics, triangle inequality not satisfied

  • also susceptible to curse of dimensionality

• L1 dampens effect but does not remove it

• cosine similiarty

  • disadvantage: no triangle inequality

• practical solution:

  • dimensionality reduction

• autoencoder

• PCA

• feature selection