A distance metric that may enhance prediction, clustering, and outlier detection in datasets with many dimensions and with various densities
On this article I describe a distance metric referred to as Shared Nearest Neighbors (SNN) and describe its utility to outlier detection. I’ll additionally cowl rapidly its utility to prediction and clustering, however will give attention to outlier detection, and particularly on SNN’s utility to the ok Nearest Neighbors outlier detection algorithm (although I may also cowl SNN’s utility to outlier detection extra usually).
This text continues a sequence on outlier detection, together with articles on Frequent Patterns Outlier Issue, Counts Outlier Detector, Doping, and Distance Metric Studying. It additionally consists of one other excerpt from my e-book Outlier Detection in Python.
In knowledge science, when working with tabular knowledge, it’s a quite common activity to measure the distances between rows. That is completed, for instance, in some predictive fashions reminiscent of KNN: when predicting the goal worth of an occasion utilizing KNN, we first determine essentially the most related information from the coaching knowledge (which requires having a method to measure the similarity between rows). We then have a look at the goal values of those related rows, with the concept the take a look at file is most certainly to have the identical goal worth as nearly all of essentially the most related information (for classification), or the typical goal worth of essentially the most related information (for regression).
Just a few different predictive fashions use distance metrics as nicely, for instance Radius-based strategies reminiscent of RadiusNeighborsClassifier. However, the place distance metrics are utilized by far essentially the most typically is with clustering. In actual fact, distance calculations are nearly common in clustering: to my information, all clustering algorithms rely ultimately on calculating the distances between pairs of information.
And distance calculations are utilized by many outlier detection algorithms, together with most of the hottest (reminiscent of kth Nearest Neighbors, Native Outlier Issue (LOF), Radius, Native Outlier Chances (LoOP), and quite a few others). This isn’t true of all outlier detection algorithms: many determine outliers in fairly alternative ways (for instance Isolation Forest, Frequent Patterns Outlier Issue, Counts Outlier Detector, ECOD, HBOS), however many detectors do make the most of distance calculations between rows in a method or one other.
Clustering and outlier detection algorithms (that work with distances) sometimes begin with calculating the pairwise distances, the distances between each pair of rows within the knowledge. At the least that is true in precept: to execute extra effectively, distance calculations between some pairs of rows could also be skipped or approximated, however theoretically, we fairly often begin by calculating an n x n matrix of distances between rows, the place n is the variety of rows within the knowledge.
This, then, requires having a method to measure the distances between any two information. However, as lined in a associated article on Distance Metric Studying (DML), it may be troublesome to find out an excellent means to determine how related, or dissimilar, two rows are.
The commonest methodology, no less than with numeric knowledge, is the Euclidean distance. This could work fairly nicely, and has sturdy intuitive attraction, significantly when viewing the info geometrically: that’s, as factors in house, as could also be seen in a scatter plot reminiscent of is proven beneath. In two dimensional plots, the place every file within the knowledge is represented as a dot, it’s pure to view the similarity of information by way of their Euclidean distances.
Nevertheless, actual world tabular knowledge typically has very many options and one of many key difficulties when coping with that is the curse of dimensionality. This manifests in a variety of methods, however one of the vital problematic is that, with sufficient dimensions, the distances between information begin to grow to be meaningless.
Within the plots proven right here, now we have a degree (proven in crimson) that’s uncommon in dimension 0 (proven on the x-axis of the left pane), however regular in dimensions 1, 2, and three. Assuming this dataset has solely these 4 dimensions, calculating the Euclidean distances between every pair of information, we’d see the crimson level as having an unusually giant distance from all different factors. And so, it may reliably be flagged as an outlier.
Nevertheless, if there have been a whole lot of dimensions, and the crimson level is pretty typical in all dimensions in addition to dimension 0, it couldn’t reliably be flagged as an outlier: the massive distance to the opposite factors in dimension 0 could be averaged in with the distances in all different dimensions and would ultimately grow to be irrelevant.
This can be a enormous difficulty for predictive, clustering, and outlier detection strategies that depend on distance metrics.
SNN is used at occasions to mitigate this impact. Nevertheless, I’ll present in experiments beneath, the place SNN is handiest (no less than with the kth Nearest Neighbors outlier detector I take advantage of beneath) is just not essentially the place there are a lot of dimensions (although that is fairly related too), however the place the density of the info varies from one area to a different. I’ll clarify beneath what this implies and the way it impacts some outlier detectors.
SNN is used to outline a distance between any two information, the identical as Euclidean, Manhattan, Canberra, cosine, and any variety of different distance metrics. Because the identify implies, the precise distances calculated must do with the variety of shared neighbors any two information have.
On this method, SNN is kind of totally different from different distance metrics, although it’s nonetheless extra just like Euclidean and different customary metrics than is Distance Metric Studying. DML seeks to search out logical distances between information, unrelated to the precise magnitudes of the values within the rows.
SNN, alternatively, truly begins by calculating the uncooked distances between rows utilizing an ordinary distance metric. If Euclidean distances are used for this primary step, the SNN distances are associated to the Euclidean distances; if cosine distances are used to calculate the uncooked distance, the SNN distances are associated to cosine distances; and so forth.
Nevertheless, earlier than we get into the small print, or present how this can be utilized to outlier detection, we’ll take a fast have a look at SNN for clustering, because it’s truly with clustering analysis that SNN was first developed. The final course of described there’s what’s used to calculate SNN distances in different contexts as nicely, together with outlier detection.
The terminology could be barely complicated, however there’s additionally a clustering methodology sometimes called SNN, which makes use of SNN distances and works very equally to DBSCAN clustering. In actual fact, it may be thought of an enhancement to DBSCAN.
The principle paper describing this may be seen right here: https://www-users.cse.umn.edu/~kumar001/papers/siam_hd_snn_cluster.pdf. Although, the concept of enhancing DBSCAN to make use of SNN goes again to a paper written by Jarvis-Patrick in 1973. The paper linked right here makes use of an analogous, however improved strategy.
DBSCAN is a powerful clustering algorithm, nonetheless broadly used. It’s capable of deal with nicely clusters of various styles and sizes (even fairly arbitrary shapes). It may well, although, battle the place clusters have totally different densities (it successfully assumes all clusters have related densities). Most clustering algorithms have some such limitations. Okay-means clustering, for instance, successfully assumes all clusters are related sizes, and Gaussian Combination Fashions clustering, that every one clusters have roughly Gaussian shapes.
I received’t describe the complete DBSCAN algorithm right here, however as a really fast sketch: it really works by figuring out what it calls core factors, that are factors in dense areas, that may safely be thought of inliers. It then identifies the factors which might be shut to those, creating clusters round every of the core factors. It runs over a sequence of steps, every time increasing and merging the clusters found to this point (merging clusters the place they overlap). Factors which might be near current clusters (even when they aren’t near the unique core factors, simply to factors which were added to a cluster) are added to that cluster. Finally each level is both in a single cluster, or is left unassigned to any cluster.
As with outlier detection, clustering can even battle with excessive dimensional datasets, once more, as a result of curse of dimensionality, and significantly the break-down in customary distance metrics. At every step, DBSCAN works primarily based on the distances between the factors that aren’t but in clusters and people in clusters, and the place these distance calculations are unreliable, the clustering is, in flip, unreliable. With excessive dimensions, core factors could be indistinguishable from some other factors, even the noise factors that actually aren’t a part of any cluster.
As indicated, DBSCAN additionally struggles the place totally different areas of the info have totally different densities. The difficulty is that DBSCAN makes use of a world sense of what factors are shut to one another, however totally different areas can fairly fairly have totally different densities.
Take, for instance, the place the info represents monetary transactions. This will embody gross sales, expense, payroll, and different varieties of transactions, every with totally different densities. The transactions could also be created at totally different charges in time, could have totally different greenback values, totally different counts, and totally different ranges of numeric values. For instance, it could be that there are a lot of extra gross sales transactions than expense transactions. And the ranges in greenback values could also be fairly totally different: maybe the biggest gross sales are solely about 10x the dimensions of the smallest gross sales, however the largest bills 1000x as giant because the smallest. So, there could be fairly totally different densities within the gross sales transactions in comparison with bills.
Assuming several types of transactions are positioned in numerous areas of the house (if, once more, viewing the info as factors in high-dimensional house, with every dimension representing a characteristic from the info desk, and every file as a degree), we could have a plot reminiscent of is proven beneath, with gross sales transactions within the lower-left and bills within the upper-right.
Many clustering algorithms (and plenty of predictive and outlier detection algorithms) may fail to deal with this knowledge nicely given these variations in density. DBSCAN could depart all factors within the upper-right unclustered if it goes by the general common of distances between factors (which can be dominated by the distances between gross sales transactions if there are a lot of extra gross sales transactions within the knowledge).
The objective of SNN is to create a extra dependable distance metric, given excessive dimensionality and ranging density.
The central concept of SNN is: if level p1 is near p2 utilizing an ordinary distance metric, we will say that probably they’re truly shut, however this may be unreliable. Nevertheless, if p1 and p2 even have most of the similar nearest neighbors, we could be considerably extra assured they’re really shut. Their shared neighbors could be mentioned to verify the similarity.
Utilizing shared neighbors, within the graph above, factors within the upper-right could be appropriately acknowledged as being in a cluster, as they sometimes share most of the similar nearest neighbors with one another.
Jarvis-Patrick defined this by way of a graph, which is a helpful method to have a look at the info. We will view every file as a degree in house (as within the scatter plot above), with an edge between every pair indicating how related they’re. For this, we will merely calculate the Euclidean distances (or one other such metric) between every pair of information.
As graphs are sometimes represented as adjacency matrices (n x n matrices, the place n is the variety of rows, giving the distances between every pair of rows), we will view the method by way of an adjacency matrix as nicely.
Contemplating the scatter plot above, we could have an n x n matrix reminiscent of:
Level 1 Level 2 Level 3 ... Level n
Level 1 0.0 3.3 2.9 ... 1.9
Level 2 3.3 0.0 1.8 ... 4.0
Level 3 2.9 1.8 0.0 ... 2.7
... ... ... ... ... ...
Level n 1.9 4.0 2.7 ... 0.0
The matrix is symmetric throughout the principle diagonal (the gap from Level 1 to Level 2 is identical as from Level 2 to Level 1) and the distances of factors to themselves is 0.0 (so the principle diagonal is totally zeros).
The SNN algorithm is a two-step course of, and begins by calculating these uncooked pair-wise distances (usually utilizing Euclidean distances). It then creates a second matrix, with the shared nearest neighbors distances.
To calculate this, it first makes use of a course of referred to as sparcification. For this, every pair of information, p and q, get a hyperlink (can have a non-zero distance) provided that p and q are every in one another’s ok nearest neighbors lists. That is easy to find out: for p, now we have the distances to all different factors. For some ok (specified as a parameter, however lets assume a worth of 10), we discover the ten factors which might be closest to p. This will or could not embody q. Equally for q: we discover it’s ok nearest neighbors and see if p is one among them.
We now have a matrix like above, however with many cells now containing zeros.
We then contemplate the shared nearest neighbors. For the required ok, p has a set of ok nearest neighbors (we’ll name this set S1), and q additionally has a set of ok nearest neighbors (we’ll name this set S2). We will then decide how related p and q are (within the SNN sense) primarily based on the dimensions of the overlap in S1 and S2.
In a extra sophisticated kind, we will additionally contemplate the order of the neighbors in S1 and S2. If p and q not solely have roughly the identical set of nearest neighbors (for instance, they’re each near p243, p873, p3321, and p773), we could be assured that p and q are shut. But when, additional, they’re each closest to p243, then to p873, then to p3321, after which to p773 (or no less than have a fairly related order of closeness), we could be much more assured p and q are related. For this text, although, we’ll merely rely the variety of shared nearest neighbors p and q have (throughout the set of ok nearest neighbors that every has).
The thought is: we do require an ordinary distance metric to begin, however as soon as that is created, we use the rank order of the distances between factors, not the precise magnitudes, and this tends to be extra secure.
For SNN clustering, we first calculate the SNN distances on this method, then proceed with the usual DBSCAN algorithm, figuring out the core factors, discovering different factors shut sufficient to be in the identical cluster, and rising and merging the clusters.
There are no less than two implementations of SNN clustering accessible on github: https://github.com/albert-espin/snn-clustering and https://github.com/felipeangelimvieira/SharedNearestNeighbors.
Regardless of its origins with clustering (and its continued significance with clustering), SNN as a distance metric is, as indicated above, related to different areas of machine studying, together with outlier detection, which we’ll return to now.
Earlier than describing the Python implementation of the SNN distance metric, I’ll rapidly current a easy implementation of a KNN outlier detector:
import pandas as pd
from sklearn.neighbors import BallTree
import statisticsclass KNN:
def __init__(self, metric='euclidian'):
self.metric = metric
def fit_predict(self, knowledge, ok):
knowledge = pd.DataFrame(knowledge)
balltree = BallTree(knowledge, metric=self.metric)
# Get the distances to the ok nearest neighbors for every file
knn = balltree.question(knowledge, ok=ok)[0]
# Get the imply distance to the ok nearest neighbors for every file
scores = [statistics.mean(x[:k]) for x in knn]
return scores
Given a second desk of knowledge and a specified ok, the fit_predict() methodology will present an outlier rating for every file. This rating is the typical distance to the ok nearest neighbors. A variation on this, the place the most distance (versus the imply distance) to the ok nearest neighbors is used, is usually referred to as kth Nearest Neighbors, whereas this variation is commonly referred to as ok Nearest Neighbors, although the terminology varies.
The majority of the work right here is definitely completed by scikit-learn’s BallTree class, which calculates and shops the pairwise distances for the handed dataframe. Its question() methodology returns, for every component handed within the knowledge parameter, two issues:
- The distances to the closest ok factors
- The indexes of the closest ok factors.
For this detector, we want solely the distances, so take component [0] of the returned construction.
fit_predict() then returns the typical distance to the ok closest neighbors for every file within the knowledge body, which is an estimation of their outlierness: the extra distant a file is from its closes neighbors, the extra of an outlier it may be assumed to be (although, as indicated, this works poorly the place totally different areas have totally different densities, which is to say, totally different common distances to their neighbors).
This might not be a production-ready implementation, however does present the fundamental concept. A full implementation of KNN outlier detection is supplied in PyOD.
Utilizing SNN distance metrics, an implementation of a easy outlier detector is:
class SNN:
def __init__(self, metric='euclidian'):
self.metric = metricdef get_pairwise_distances(self, knowledge, ok):
knowledge = pd.DataFrame(knowledge)
balltree = BallTree(knowledge, metric=self.metric)
knn = balltree.question(knowledge, ok=ok+1)[1]
pairwise_distances = np.zeros((len(knowledge), len(knowledge)))
for i in vary(len(knowledge)):
for j in vary(i+1, len(knowledge)):
if (j in knn[i]) and (i in knn[j]):
weight = len(set(knn[i]).intersection(set(knn[j])))
pairwise_distances[i][j] = weight
pairwise_distances[j][i] = weight
return pairwise_distances
def fit_predict(self, knowledge, ok):
knowledge = pd.DataFrame(knowledge)
pairwise_distances = self.get_pairwise_distances(knowledge, ok)
scores = [statistics.mean(sorted(x, reverse=True)[:k]) for x in pairwise_distances]
min_score = min(scores)
max_score = max(scores)
scores = [min_score + (max_score - x) for x in scores]
return scores
The SNN detector right here can truly even be thought of a KNN outlier detector, merely utilizing SNN distances. However, for simplicity, we’ll discuss with the 2 outliers as KNN and SNN, and assume the KNN detector makes use of an ordinary distance metric reminiscent of Manhattan or Euclidean, whereas the SNN detector makes use of an SNN distance metric.
As with the KNN detector, the SNN detector returns a rating for every file handed to fit_predict(), right here the typical SNN distance to the ok nearest neighbors, versus the typical distance utilizing an ordinary distance metric.
This class additionally offers the get_pairwise_distances() methodology, which is utilized by fit_predict(), however could be referred to as straight the place calculating the pairwise SNN distances is helpful (we see an instance of this later, utilizing DBSCAN for outlier detection).
In get_pairwise_distances(), we take component [1] of the outcomes returned by BallTree’s question() methodology, because it’s the closest neighbors we’re considering, not their particular distances.
As indicated, we set all distances to zero until the 2 information are throughout the closest ok of one another. We then calculate the precise SNN distances because the variety of shared neighbors throughout the units of ok nearest neighbors for every pair of factors.
It will be doable to make use of a measure reminiscent of Jaccard or Cube to quantify the overlap within the nearest neighbors of every pair of factors, however on condition that each are of the identical measurement, ok, we will merely rely the dimensions of the overlap for every pair.
Within the different supplied methodology, fit_predict(), we first get the pairwise distances. These are literally a measure of normality, not outlierness, so these are reversed earlier than returning the scores.
The ultimate rating is then the typical overlap with the ok nearest factors for every file.
So, ok is definitely getting used for 2 totally different functions right here: it’s used to determine the ok nearest neighbors in step one (the place we calculate the KNN distances, utilizing Euclidean or different such metric) and once more within the second step (the place we calculate the SNN distances, utilizing the typical overlap). It’s doable to make use of two totally different parameters for these, and a few implementations do, typically referring to the second as eps (this comes from the historical past with DBSCAN the place eps is used to outline the utmost distance between two factors for one to be thought of in the identical neighborhood as the opposite).
Once more, this isn’t essentially production-ready, and is way from optimized. There are strategies to enhance the velocity, and that is an lively space of analysis, significantly for step one, calculating the uncooked pairwise distances. The place you’ve very giant volumes of knowledge, it could be crucial to have a look at alternate options to BallTree, reminiscent of faiss, or in any other case velocity up the processing. However, for reasonably sized datasets, code reminiscent of right here will usually be adequate.
I’ve examined the above KNN and SNN outlier detectors in a variety of methods, each with artificial and actual knowledge. I’ve additionally used SNN distances in a variety of outlier detection tasks through the years.
On the entire, I’ve truly not discovered SNN to essentially work ideally to KNN with respect to excessive dimensions, although SNN is preferable at occasions.
The place I’ve, nevertheless, seen SNN to offer a transparent profit over customary KNN is the place the info has various densities.
To be extra exact, it’s the mix of excessive dimensionality and ranging densities the place SNN tends to most strongly outperform different distance metrics with KNN-type detectors, extra so than if there are simply excessive dimensions, or simply various densities.
This may be seen with the next take a look at code. This makes use of (pretty) easy artificial knowledge to current this extra clearly.
def test_variable_blobs(nrows=1000, ncols=500, nclusters=60, outlier_multiplier=2.0, ok=30, metric='manhattan'):
np.random.seed(1)# ########################################################
# Create the take a look at knowledge
# Decide the dimensions of every cluster
n_samples_arr = []
remaining_count = nrows
for i in vary(nclusters-1):
cluster_size = np.random.randint(1, remaining_count // (nclusters - i))
n_samples_arr.append(cluster_size)
remaining_count -= cluster_size
n_samples_arr.append(remaining_count)
# Decide the density of every cluster
cluster_std_arr = []
for i in vary(nclusters):
cluster_std_arr.append(np.random.uniform(low=0.1, excessive=2.0))
# Decide the middle location of every cluster
cluster_centers_arr = []
for i in vary(nclusters):
cluster_centers_arr.append(np.random.uniform(low=0.0, excessive=10.0, measurement=ncols))
# Create the pattern knowledge utilizing the required cluster sizes, densities, and places
x, y = make_blobs(n_samples=n_samples_arr,
cluster_std=cluster_std_arr,
facilities=cluster_centers_arr,
n_features=ncols,
random_state=0)
df = pd.DataFrame(x)
# Add a single identified outlier to the info
avg_row = [x[:, i].imply() for i in vary(ncols)]
outlier_row = avg_row.copy()
outlier_row[0] = x[:, 0].max() * outlier_multiplier
df = pd.concat([df, pd.DataFrame([outlier_row])])
df = df.reset_index()
# ########################################################
# Examine customary distance metrics to SNN
# Calculate the outlier scores utilizing customary KNN
scored_df = df.copy()
knn = KNN(metric=metric)
scored_df['knn_scores'] = knn.fit_predict(df, ok=ok)
# Calculate the outlier scores utilizing SNN
snn = SNN(metric=metric)
scored_df['snn_scores'] = snn.fit_predict(df, ok=ok)
# Plot the distribution of scores for each detectors and present
# the rating for the identified outlier (in context of the vary of
# scores assigned to the complete dataset)
fig, ax = plt.subplots(nrows=1, ncols=2, figsize=(12, 4))
sns.histplot(scored_df['knn_scores'], ax=ax[0])
ax[0].axvline(scored_df.loc[nrows, 'knn_scores'], shade='crimson')
sns.histplot(scored_df['snn_scores'], ax=ax[1])
ax[1].axvline(scored_df.loc[nrows, 'snn_scores'], shade='crimson')
plt.suptitle(f"Variety of columns: {ncols}")
plt.tight_layout()
plt.present()
On this methodology, we generate take a look at knowledge, add a single, identified outlier to the dataset, get the KNN outlier scores, get the SNN outlier scores, and plot the outcomes.
The take a look at knowledge is generated utilizing scikit-learn’s make_blobs(), which creates a set of high-dimensional clusters. The one outlier generated shall be outdoors of those clusters (and also will have, by default, one excessive worth in column 0).
A lot of the complication within the code is in producing the take a look at knowledge. Right here, as a substitute of merely calling make_blobs() with default parameters, we specify the sizes and densities of every cluster, to make sure they’re all totally different. The densities are specified utilizing an array of normal deviations (which describes how unfold out every cluster is).
This produces knowledge reminiscent of:
This exhibits solely 4 dimensions, however sometimes we’d name this methodology to create knowledge with many dimensions. The identified outlier level is proven in crimson. In dimension 0 it has an excessive worth, and in most different dimensions it tends to fall outdoors the clusters, so is a powerful outlier.
Testing could be completed, with:
test_variable_blobs(nrows=1000, ncols=20, nclusters=1, ok=30, metric='euclidean')
test_variable_blobs(nrows=1000, ncols=100, nclusters=5, ok=30, metric='euclidean')
test_variable_blobs(nrows=1000, ncols=250, nclusters=10, ok=30, metric='euclidean')
test_variable_blobs(nrows=1000, ncols=400, nclusters=15, ok=30, metric='euclidean')
test_variable_blobs(nrows=1000, ncols=450, nclusters=20, ok=30, metric='euclidean')
test_variable_blobs(nrows=1000, ncols=500, nclusters=20, ok=30, metric='euclidean')
test_variable_blobs(nrows=1000, ncols=750, nclusters=20, ok=30, metric='euclidean')
test_variable_blobs(nrows=1000, ncols=1000, nclusters=20, ok=30, metric='euclidean')
test_variable_blobs(nrows=1000, ncols=2000, nclusters=20, ok=30, metric='euclidean')
test_variable_blobs(nrows=1000, ncols=3000, nclusters=20, ok=30, metric='euclidean')test_variable_blobs(nrows=1000, ncols=20, nclusters=1, ok=30)
test_variable_blobs(nrows=1000, ncols=100, nclusters=5, ok=30)
test_variable_blobs(nrows=1000, ncols=250, nclusters=10, ok=30)
test_variable_blobs(nrows=1000, ncols=400, nclusters=15, ok=30)
test_variable_blobs(nrows=1000, ncols=450, nclusters=20, ok=30)
test_variable_blobs(nrows=1000, ncols=500, nclusters=20, ok=30)
test_variable_blobs(nrows=1000, ncols=750, nclusters=20, ok=30)
test_variable_blobs(nrows=1000, ncols=1000, nclusters=20, ok=30)
test_variable_blobs(nrows=1000, ncols=2000, nclusters=20, ok=30)
test_variable_blobs(nrows=1000, ncols=3000, nclusters=20, ok=30)
This primary executes a sequence of assessments utilizing Euclidean distances (utilized by each the KNN detector, and for step one of the SNN detector), after which executes a sequence of assessments utilizing Manhattan distances (the default for the test_variable_blobs() methodology) —utilizing Manhattan for each for the KNN detector and for step one with the SNN detector.
For every, we take a look at with rising numbers of columns (starting from 20 to 3000).
Beginning with Euclidian distances, utilizing solely 20 options, each KNN and SNN work nicely, in that they each assign a excessive outlier rating to the identified outlier. Right here we see the distribution of outlier scores produced by every detector (the KNN detector is proven within the left pane and the SNN detector in the fitting pane) and a crimson vertical line indicating the outlier rating given to the identified outlier by every detector. In each instances, the identified outlier obtained a considerably increased rating than the opposite information: each detectors do nicely.
However, utilizing Euclidean distances tends to degrade rapidly as options are added, and works fairly poorly even with solely 100 options. That is true with each the KNN and SNN detectors. In each instances, the identified outlier obtained a reasonably regular rating, not indicating any outlierness, as seen right here:
Repeating utilizing Manhattan distances, we see that KNN works nicely with smaller numbers of options, however breaks down because the numbers of options will increase. KNN does, nevertheless, do significantly better with Manhattan distances that Euclidean as soon as we get a lot past about 50 or so options (with small numbers of options, nearly any distance metric will work fairly nicely).
In all instances beneath (utilizing Manhattan & SNN distances), we present the distribution of KNN outlier scores (and the outlier rating assigned to the identified outlier by the KNN detector) within the left pane, and the distribution of SNN scores (and the outlier rating given to the identified outlier by the SNN detector) in the fitting pane.
With 20 options, each work nicely:
With 100 options, KNN remains to be giving the identified outlier a excessive rating, however not very excessive. SNN remains to be doing very nicely (and does in all instances beneath as nicely):
With 250 options the rating given to the identified outlier by KNN is pretty poor and the distribution of scores is odd:
With 500 options:
With 1000 options:
With 2000 options:
With 3000 options:
With the KNN detector, even utilizing Manhattan distances, we will see that the distribution of scores is kind of odd by 100 options and, extra relevantly, that by 100 options the KNN rating given to the identified outlier is poor: a lot too low and never reflecting its outlierness.
The distribution of SNN scores, alternatively, stays cheap even as much as 3000 options, and the SNN rating given to the identified outlier stays very excessive up till nearly 2000 options (for 2000 and 3000 options, it’s rating is excessive, however not fairly the highest-scored file).
The SNN detector (primarily the KNN outlier detection algorithm with SNN distances) labored far more reliably than KNN with Manhattan distances.
One key level right here (outdoors of contemplating SNN distances) is that Manhattan distances could be far more dependable for outlier detection than Euclidean the place now we have giant numbers of options. The curse of dimensionality nonetheless takes have an effect on (all distance metrics ultimately break down), however a lot much less severely the place there are dozens or a whole lot of options than with Euclidean.
In actual fact, whereas very appropriate in decrease dimensions, Euclidean distances can break down even with reasonable numbers of options (typically with as few as 30 or 40). Manhattan distances is usually a fairer comparability in these instances, which is what is completed right here.
Usually, we ought to be conscious of evaluations of distance metrics that evaluate themselves to Euclidean distances, as these could be deceptive. It’s customary to imagine Euclidean distances when working with distance calculations, however that is one thing we should always query.
Within the case recognized right here (the place knowledge is just clustered, however in clusters with various sizes and densities), SNN did strongly outperform KNN (and, impressively, remained dependable even to shut to 2000 options). This can be a extra significant discovering on condition that we in comparison with KNN primarily based on Manhattan distances, not Euclidean.
Nevertheless, in lots of different situations, significantly the place the info is in a single cluster, or the place the clusters have related densities to one another, KNN can work in addition to, and even ideally to, SNN.
It’s not the case that SNN ought to at all times be favoured to different distance metrics, solely that there are situations the place it may well do considerably higher.
In different instances, different distance metrics may go ideally as nicely, together with cosine distances, Canberra, Mahalanobis, Chebyshev, and so forth. It is rather typically price experimenting with these when performing outlier detection.
The place KNN breaks down right here is, very like the case when utilizing DBSCAN for clustering, the place totally different areas (on this case, totally different clusters) have totally different densities.
KNN is an instance of a kind of detector generally known as a international outlier detector. Should you’re aware of the concept of native and international outliers, the concept is said, however totally different. On this case, the ‘international’ in international outlier detector means that there’s a international sense of regular. This is identical limitation described above with DBSCAN clustering (the place there’s a international sense of regular distances between information). Each file within the knowledge is in comparison with this evaluation of regular. Within the case of KNN outlier detectors, there’s a international sense of the conventional common distance to the ok nearest neighbors.
However, this international norm is just not significant the place the info has totally different densities in numerous areas. Within the plot beneath (repeated from above), there are two clusters, with the one within the lower-left being far more dense that the one within the upper-right.
What’s related, by way of figuring out outliers, is how shut a degree is to its neighbors relative to what’s regular for that area, not relative to what’s regular within the different clusters (or within the dataset as an entire).
That is the issue one other necessary outlier detector, Native Outlier Issue (LOF) was created to unravel (the unique LOF paper truly describes a scenario very very like this). Opposite to international outlier detectors, LOF is an instance of a native outlier detector: a detector that compares factors to different factors within the native space, to not the complete dataset, so compares every level to an area sense of what’s regular. Within the case of LOF, it compares every level to an area sense of the typical distance to the close by factors.
Native outlier detectors additionally present a helpful strategy to figuring out outliers the place the densities differ all through the info house, which I cowl in Outlier Detection in Python, and I’ll attempt to cowl in future articles.
SNN additionally offers an necessary resolution to this downside of various densities. With SNN distances, the adjustments in density aren’t related. Every file right here is in contrast towards a world customary of the typical variety of shared neighbors a file has with its closest neighbors. This can be a fairly sturdy calculation, and capable of work nicely the place the info is clustered, or simply populated extra densely in some areas than others.
On this article, we’ve appeared primarily on the KNN algorithm for outlier detection, however SNN can be utilized with any outlier detector that’s primarily based on the distances between rows. This consists of Radius, Native Outlier Issue (LOF), and quite a few others. It additionally consists of any outlier detection algorithm primarily based on clustering.
There are a variety of how to determine outliers utilizing clustering (for instance, figuring out the factors in very small clusters, factors which might be removed from their cluster facilities, and so forth). Right here, although, we’ll have a look at a quite simple strategy to outlier detection: clustering the info after which figuring out the factors not positioned in any cluster.
DBSCAN is among the clustering algorithms mostly used for the sort of outlier detection, because it has the handy property (not shared by all clustering algorithms) of permitting factors to not be positioned in any cluster.
DBSCAN (no less than scikit-learn’s implementation) additionally permits us to simply work with SNN distances.
So, in addition to being a helpful clustering algorithm, DBSCAN is broadly used for outlier detection, and we’ll use it right here as one other instance of outlier detection with SNN distances.
Earlier than utilizing SNN distances, although, we’ll present an instance utilizing DBSCAN because it’s extra typically used to determine outliers in knowledge (right here utilizing the default Euclidean distances). This makes use of the identical dataset created above, the place the final row is the only identified outlier.
clustering = DBSCAN(eps=20, min_samples=2).match(df.values)
print(clustering.labels_)
print(pd.Collection(clustering.labels_).value_counts())
The parameters for DBSCAN can take some experimentation to set nicely. On this case, I adjusted them till the algorithm recognized a single outlier, which I confirmed is the final row by printing the labels_ attribute. The labels are:
[ 0 1 1 ... 1 0 -1]
-1 signifies information not assigned to any cluster. As nicely, value_counts() indicated there’s just one file assigned to cluster -1. So, DBSCAN works nicely on this instance. Which implies we will’t enhance on it through the use of SNN, however this does present a transparent instance of utilizing DBSCAN for outlier detection, and ensures the dataset is solvable utilizing clustering-based outlier detection.
To work with SNN distances, it’s essential to first calculate the pairwise SNN distances (DBSCAN can’t calculate these by itself). As soon as these are created, they are often handed to DBSCAN within the type of an n x n matrix.
Right here we calculate the SNN pairwise distances:
snn = SNN(metric='manhattan')
pairwise_dists = snn.get_pairwise_distances(df, ok=100)
print(pairwise_dists)
The pairwise distances seem like:
array([[ 0., 0., 0., ..., 0., 57., 0.],
[ 0., 0., 0., ..., 0., 0., 0.],
[ 0., 0., 0., ..., 0., 0., 0.],
...,
[ 0., 0., 0., ..., 0., 0., 0.],
[57., 0., 0., ..., 0., 0., 0.],
[ 0., 0., 0., ..., 0., 0., 0.]])
As a fast and easy method to reverse these distances (to be higher suited to DBSCAN), we name:
d = pd.DataFrame(pairwise_dists).apply(lambda x: 1000-x)
Right here 1000 is just a worth bigger than any within the precise knowledge. Then we name DBSCAN, utilizing ‘precomputed’ because the metric and passing the pairwise distances to suit().
clustering = DBSCAN(eps=975, min_samples=2, metric='precomputed').match(d.values)
print(clustering.labels_)
show(pd.Collection(clustering.labels_).value_counts())
Once more, this identifies solely the only outlier (just one file is given the cluster id -1, and that is the final row). Usually, DBSCAN, and different instruments that settle for ‘precomputed’ because the metric can work with SNN distances, and probably produce extra sturdy outcomes.
Within the case of DBSCAN, utilizing SNN distances can work nicely, as outliers (known as noise factors in DBSCAN) and inliers are inclined to have nearly all of their hyperlinks damaged, and so outliers find yourself in no clusters. Some outliers (although outliers which might be much less excessive) can have some hyperlinks to different information, however will are inclined to have zero, or only a few, shared neighbors with these, so will get excessive outlier scores (although not as excessive as these with no hyperlinks, as is acceptable).
This could take some experimenting, and in some instances the worth of ok, in addition to the DBSCAN parameters, will should be adjusted, although to not an extent uncommon in outlier detection — it’s frequent for some tuning to be crucial.
SNN is just not as broadly utilized in outlier detection because it ideally could be, however there’s one well-known detector that makes use of it: SOD, which is supplied within the PyOD library.
SOD is an outlier detector that focusses on discovering helpful subspaces (subsets of the options accessible) for outlier detection, however does use SNN as a part of the method, which, it argues within the paper introducing SOD, offers extra dependable distance calculations.
SOD works (just like KNN and LOF), by figuring out a neighborhood of ok neighbors for every level, identified with SOD because the reference set. The reference set is discovered utilizing SNN. So, neighborhoods are recognized, not through the use of the factors with the smallest Euclidean distances, however by the factors with essentially the most shared neighbors.
The authors discovered this tends to be sturdy not solely in excessive dimensions, but additionally the place there are a lot of irrelevant options: the rank order of neighbors tends to stay significant, and so the set of nearest neighbors could be reliably discovered even the place particular distances usually are not dependable.
As soon as now we have the reference set for a degree, SOD makes use of this to find out the subspace, which is the set of options that specify the best quantity of variance for the reference set. And, as soon as SOD identifies these subspaces, it examines the distances of every level to the info middle, which then offers an outlier rating.
An apparent utility of SNN is to embeddings (for instance, vector representations of photos, video, audio, textual content, community, or knowledge of different modalities), which are inclined to have very excessive dimensionality. We have a look at this in additional depth in Outlier Detection in Python, however will point out right here rapidly: customary outlier detection strategies meant for numeric tabular knowledge (Isolation Forest, Native Outlier Issue, kth Nearest Neighbors, and so forth), truly are inclined to carry out poorly on embeddings. The principle motive seem like the excessive numbers of dimensions, together with the presence of many dimensions within the embeddings which might be irrelevant for outlier detection.
There are different, well-established strategies for outlier detection with embeddings, for instance strategies primarily based on auto-encoders, variational auto-encoders, generative adversarial networks, and a variety of different strategies. As nicely, it’s doable to use dimensionality discount to embeddings for simpler outlier detection. These are additionally lined within the e-book and, I hope, a future Medium article. As nicely, I’m now investigating using distance metrics aside from Euclidean, cosine, and different customary metrics, together with SNN. If these could be helpful is presently below investigation.
Just like Distance Metric Studying, Shared Nearest Neighbors shall be dearer to calculate than customary distance metrics reminiscent of Manhattan and Euclidean distances, however could be extra sturdy with giant numbers of options, various densities, and (because the SOD authors discovered), irrelevant options.
So, in some conditions, SNN is usually a preferable distance metric to extra customary distance metrics and could also be a extra applicable distance metric to be used with outlier detection. We’ve seen right here the place it may be used as the gap metric for kth Nearest Neighbors outlier detection and for DBSCAN outlier detection (in addition to when merely utilizing DBSCAN for clustering).
In actual fact, SNN can, be used with any outlier detection methodology primarily based on distances between information. That’s, it may be used with any distance-based, density-based, or clustering-based outlier detector.
We’ve additionally indicated that SNN is not going to at all times work favorably in comparison with different distance metrics. The difficulty is extra sophisticated when contemplating categorical, date, and textual content columns (in addition to probably different varieties of options we may even see in tabular knowledge). However even contemplating strictly numeric knowledge, it’s fairly doable to have datasets, even with giant numbers of options, the place plain Manhattan distances work ideally to SNN, and different instances the place SNN is preferable. The variety of rows, variety of options, relevance of the options, distributions of the options, associations between options, clustering of the info, and so forth are all related, and it often can’t be predicted forward of time what is going to work finest.
SNN is just one resolution to issues reminiscent of excessive dimensionality, various density, and irrelevant options, however is is a great tool, straightforward sufficient to implement, and very often price experimenting with.
This text was simply an introduction to SNN and future articles could discover SNN additional, however usually, when figuring out the gap metric used (and different such modeling selections) with outlier detection, the most effective strategy is to make use of a method referred to as doping (described on this article), the place we create knowledge just like the actual knowledge, however modified so to comprise sturdy, however real looking, anomalies. Doing this, we will attempt to estimate what seems to be handiest at detecting the kinds of outliers you could have.
Right here we used an instance with artificial knowledge, which might help describe the place one outlier detection strategy works higher than one other, and could be very helpful (for instance, right here we discovered that when various the densities and rising the variety of options, SNN outperformed Manhattan distances, however with constant densities and low numbers of options, each did nicely). However, utilizing artificial, as necessary as it’s, is just one step to understanding the place totally different approaches will work higher for knowledge just like the info you’ve. Doping will are inclined to work higher for this goal, or no less than as a part of the method.
As nicely, it’s usually accepted in outlier detection that no single detector will reliably determine all of the outliers you’re considering detecting. Every detector will detect a reasonably particular kind of outlier, and fairly often we’re considering detecting a variety of outliers (the truth is, very often we’re merely in figuring out something that’s statistically considerably totally different from regular — particularly when first analyzing a dataset).
On condition that, it’s frequent to make use of a number of detectors for outlier detection, combining their outcomes into an ensemble. One helpful method to extend range inside an ensemble is to make use of quite a lot of distance metrics. For instance, if Manhattan, Euclidean, SNN, and presumably even others (maybe Canberra, cosine, or different metrics) all work nicely (all producing totally different, however smart outcomes), it could be worthwhile to make use of all of those. Usually although, we’ll discover that just one or two distance metrics produce significant outcomes given the dataset now we have and the varieties of outliers we’re considering. Though not the one one, SNN is a helpful distance metric to strive, particularly the place the detectors are struggling when working with different distance metrics.
All photos by creator.