Anomaly Detection + Distances

Question 1

What is DTW and how does it work?

Answer 1

Dynamic Type Warping or sequence alignment aligns time-series non-linearly in time, and finds the best match.

Question 2

How can you create an Isolation forrest?

Answer 2

Repeat N times:
* Randomly pick a feature (dimension) f
* Split said f at random between [min, max]
* Continue until all leafs contain singletons
* The path length to reach a leaf is the isolation score
* Average this length over all trees to get the anomaly score

Question 3

What are the two main ways to approach anomaly detection?

Answer 3

• Distance-based: a point is anomalous when it is far from other points
• Density-based: a point is anomalous when it is in a low density region

Question 4

How to compute local reachability density (lrd)?

Answer 4

lrd = #nn/sum of distances from point to the neighbours

Question 5

How to compute local outlier factor (lof)?

Answer 5

lof = (1/#nn) * (sum of lrd of neighbours)/lrd of point

Question 6

What is a residual?

Answer 6

The difference between the expected and real value

Question 7

What is PCA

Answer 7

Principal Component Analysis reduces the dimension of data by finding the principal vectors that capture most of the data’s patterns

Question 8

Why is PCA useful for anomaly detection?

Answer 8

Outliers have variability in the smallest component (that should be constant)
The set of feature it finds should explain most of the variance. If Datapoints vary in unexplained dimensions are anomalous.

Question 9

How does dimensionality reduction find outliers in general?

Answer 9

Abnormal data will map to abnormal code, so when reconstructing, this will give us a more clear view of the anomalies.

Question 10

What is edit distance?

Answer 10

The amount of changes required to a series to be equal to another series.

Question 11

What are the properties of a distance metric?

Answer 11

d > 0
d(a,b) = 0 iff a == b
d(a,b) = d(b,a)
d(a,c) <= d(a,b) + d(b,c)

Question 12

How does K-means work?

Answer 12

Randomly choose cluster centers for how many clusters you want.

Find the nearest neighbours -> compute centroid and assign each observation to the cluster with the closest center to the observation.

Iterate until the cluster assignments stop changing.

Question 13

How does hierarchical clustering work?

Answer 13

Treat each observation as a cluster.
Find the closest two clusters and merge. Repeat until all points belong to one cluster.
Create dendrogram -> remove links from top until you have as many clusters as you want.

Question 14

What are the types of cluster distance?

Answer 14

Single linkage: distance between closest points from the different clusters

Compllete linkage: distance between the furthest points in the clusters

Average linkage: average distance between all pairs of points.

Ward distance: difference between the total within cluster sum of squares for the two clusters separately, and the within cluster ss result from merging the two clusters in one cluster

Question 15

Does hierarchical clustering need the distance to be a metric?

Answer 15

Single, complete, and average linkage only require symmetry and non-negative properties

Ward and centroid-based require euclidean distance since they minimize squared error.

Question 16

How does DBSCAN work?

Answer 16

Classify points as Core, Border, and Noise, based on a radius e and a t expected neighbours.

Core: if number of points at distance e or less is >= t but has core in circle

Border: if -//- is < t but has no core in circle

Only requires symmetry and non-negative

Question 17

Graph based (spectral) clustering

Answer 17

Construct neighbourhood graph G, based on the distance of the points being below a threshold, or nearest neighbors. Set the weight on the edges as the distance. Find communities using graph mining. Return found communitie as clusters.

Question 18

When is a clustering considered good in terms of inter and intra - cluster distances?

Answer 18

When the Intra/Inter ratio is small.

Question 19

What is CURE?

Answer 19

Cluster using representatives is useful for non-centroid clustering. Since is it very expensive, we can select a couple of points to represent a cluster (prototyping)

Question 20

What does BFR do?

Answer 20

• aimts to minimize time and space required by l-means
• points can be assigned to three sets:
  > discard set - assigned to a pre-existing cluster
  > compressed set - mini-clusters
  > retained set - outliers, points that do not belong to any cluster

Question 21

What do we require for a cluster in BFR?

Answer 21

• N - the number of data points in the cluster
• SUM - a vector containing with sums of all feature values
• SUMSQ - a vector with sums of squared feature values

With these we can keep track of the centroid of the cluster, and compute a threshold for cluster membership.

Question 22

What are the 3 types of anomalyes?

Answer 22

Point: a singular datapoint is anomalous w.r.t to the rest of the data.
Contextual: Detectable depending on context. Using sliding windows and the assumption that the next datapoint should be close to the previous, large leaps are considered anomalous
Collective: The individual instances within the collective anomaly are not anomalour by themselves. They require a relationship among data instances (sequential, spatial, graph). Also detected with sliding windows.

Question 23

What is hamming distance?

Answer 23

The number of different bits in two bit strings.

Question 24

What does the silhouette 1 and -1 values correlate with.

Answer 24

1 is good clustering, -1 is mixed