<jupyter_start><jupyter_text>Outliers detectionNotebook and DSbox lib packaged by [<NAME>](https://www.linkedin.com/in/vlevorato/).GitHub: https://github.com/vlevorato/dsbox  Univariate data: application to  time seriesExamples of application for using median and FFT filtering on a small dataset.  Data importThe data used for this tutorial are taken from the Numenta Anomaly Benchmark (NAB). GitHub: https://github.com/numenta/NAB**real Ad Exchange**Online advertisement clicking rates, where the metrics are cost-per-click (CPC) and cost per thousand impressions (CPM).*<NAME>., <NAME>., <NAME>., & <NAME>. (2017). Unsupervised real-time anomaly detection for streaming data. Neurocomputing, Available online 2 June 2017, ISSN 0925-2312, https://doi.org/10.1016/j.neucom.2017.04.070*<jupyter_code>df = pd.read_csv('https://github.com/numenta/NAB/raw/master/data/realAdExchange/exchange-3_cpc_results.csv')
df['timestamp'] = pd.to_datetime(df['timestamp'])
df = df.set_index('timestamp')
df.head(3)
# taken from https://github.com/numenta/NAB/blob/master/labels/combined_labels.json
anomalies_dates= ["2011-07-14 10:15:01",
        "2011-07-20 10:15:01",
        "2011-08-13 10:15:01"]
for i in range(0, len(anomalies_dates)):
  anomalies_dates[i] = pd.to_datetime(anomalies_dates[i])
df['anomaly'] = df.index.map(lambda x: 1 if x in anomalies_dates else 0)
df['anomaly_viz'] = df.index.map(lambda x: 1 if x in anomalies_dates else np.nan)
plt.plot(df['value'])
plt.plot(df['anomaly_viz']*df['value'], marker='o', linewidth=0, color='red', label='anomaly')
plt.title('Ad Exchange')
plt.legend()
plt.show()<jupyter_output><empty_output><jupyter_text>Median filtering techniqueIt can be used to detect outliers and also to denoise some signal (mean can be used also in some cases).In 2D, median filtering is widely used in image denoising:It can be applied also in one dimension as we'll see in this tutorial:**Wikipedia definition:**The median filter is a nonlinear digital filtering technique, often used to remove noise from an image or signal. Such noise reduction is a typical pre-processing step to improve the results of later processing (for example edge detection on an image). Median filtering is very widely used in digital image processing because, under certain conditions, it preserves edges while removing noise , also having applications in signal processing.**Algorithm description:**The main idea of the median filter is to run through the signal entry by entry, replacing each entry with the median of neighboring entries. The pattern of neighbors is called the "window", which slides, entry by entry, over the entire signal. For 1D signals, the most obvious window is just the first few preceding and following entries, whereas for 2D (or higher-dimensional) signals such as images, more complex window patterns are possible (such as "box" or "cross" patterns). Note that if the window has an odd number of entries, then the median is simple to define: it is just the middle value after all the entries in the window are sorted numerically. For an even number of entries, there is more than one possible median.<jupyter_code>from dsbox.ml.outliers import MADOutliers
mad_outliers = MADOutliers()
outliers = mad_outliers.fit_predict(df[['value']])
df['outliers'] = outliers
df['outliers'] = df['outliers'].map(lambda x: 1 if x else np.nan)
plt.plot(df['value'])
plt.plot(df['anomaly_viz']*df['value'], marker='o', linewidth=0, color='red', label='Anomaly')
plt.plot(df['outliers']*df['value'], marker='x', linewidth=0, color='purple', label='Detected outliers')
plt.title('Ad Exchange')
plt.legend()
plt.show()<jupyter_output><empty_output><jupyter_text>In our first experiment, the outliers detection is too sensitive: first, it takes all the data as one window, and second, the `cutoff` parameter is set to 2 by default. It corresponds to the amount of times the residuals relative to the median exceed the ratio to the Median Absolute Deviation.In a full unsupervised task, the strategy is to produce result, confront them to an expert (in that case, the anomaly labelling), and then trying to do better. We can consider this problem (finding the good window size and cutoff) as an optimization problem that can be handled with techniques like *Grid search* or *Bayesian optimization*. We don't use these techniques here to simplify the explanations.Let's try with a less sensitive cutoff:<jupyter_code>mad_outliers = MADOutliers(cutoff=10)
outliers = mad_outliers.fit_predict(df[['value']])
df['outliers'] = outliers
df['outliers'] = df['outliers'].map(lambda x: 1 if x else np.nan)
plt.plot(df['value'])
plt.plot(df['anomaly_viz']*df['value'], marker='o', linewidth=0, color='red', label='Anomaly')
plt.plot(df['outliers']*df['value'], marker='x', linewidth=0, color='purple', label='Detected outliers')
plt.title('Ad Exchange')
plt.legend()
plt.show()<jupyter_output><empty_output><jupyter_text>Much better ! But let's try again:<jupyter_code>mad_outliers = MADOutliers(cutoff=15, window=500)
outliers = mad_outliers.fit_predict(df[['value']])
df['outliers'] = outliers
df['outliers'] = df['outliers'].map(lambda x: 1 if x else np.nan)
plt.plot(df['value'])
plt.plot(df['anomaly_viz']*df['value'], marker='o', linewidth=0, color='red', label='Anomaly')
plt.plot(df['outliers']*df['value'], marker='x', linewidth=0, color='purple', label='Detected outliers')
plt.title('Ad Exchange')
plt.legend()
plt.show()<jupyter_output><empty_output><jupyter_text>It seems that we won't get better, but it's still acceptable. Of course, this example is simple, and finding the best parameters depends on the context.  FFT filtering techniqueThe idea is to isolate high frequencies in frequency domain, i.e. fast variations.Formula of the DFT (Discrete Fourier Transform):A little more simple with a FFT example:Application to image (low frequencies pass => loosing high contrast difference, i.e. details):**FFT Wikipedia definition:**A fast Fourier transform (FFT) algorithm computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IFFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in the frequency domain and vice versa. An FFT rapidly computes such transformations by factorizing the DFT matrix into a product of sparse (mostly zero) factors. As a result, it manages to reduce the complexity of computing the DFT from $O(n^2)$, which arises if one simply applies the definition of DFT, to $O(n.log(n))$, where n is the data size.<jupyter_code>from dsbox.ml.outliers import FFTOutliers
fft_outliers = FFTOutliers()
outliers = fft_outliers.fit_predict(df[['value']])
df['outliers'] = outliers.values
df['outliers'] = df['outliers'].map(lambda x: 1 if x else np.nan)
plt.plot(df['value'])
plt.plot(df['anomaly_viz']*df['value'], marker='o', linewidth=0, color='red', label='Anomaly')
plt.plot(df['outliers']*df['value'], marker='x', linewidth=0, color='purple', label='Detected outliers')
plt.title('Ad Exchange')
plt.legend()
plt.show()<jupyter_output><empty_output><jupyter_text>Without tuning the parameters, the outliers expulsed by the FFT are too many. Let's try with differents parameters:<jupyter_code>fft_outliers = FFTOutliers(freq_cut_index=300, outlier_proportion=0.005)
outliers = fft_outliers.fit_predict(df[['value']])
df['outliers'] = outliers.values
df['outliers'] = df['outliers'].map(lambda x: 1 if x else np.nan)
plt.plot(df['value'])
plt.plot(df['anomaly_viz']*df['value'], marker='o', linewidth=0, color='red', label='Anomaly')
plt.plot(df['outliers']*df['value'], marker='x', linewidth=0, color='purple', label='Detected outliers')
plt.title('Ad Exchange')
plt.legend()
plt.show()<jupyter_output><empty_output><jupyter_text>Almost there, but it will be difficult to obtain better results.  Multivariate data: KC2 program defects  Data importOne of the NASA Metrics Data Program defect data sets. Data from software for science data processing. Data comes from McCabe and Halstead features extractors of source code. These features were defined in the 70s in an attempt to objectively characterize code features that are associated with software quality.source: https://www.openml.org/d/1063*<NAME>. and <NAME>. (2005) The PROMISE Repository of Software Engineering Databases. School of Information Technology and Engineering, University of Ottawa, Canada.*<jupyter_code>raw_data = pd.read_csv('https://www.openml.org/data/get_csv/53946/kc2.csv', header=0)
raw_data.head()
raw_data.shape
target_id = 'problems'
target_value = 'yes'

raw_data[target_id].value_counts()<jupyter_output><empty_output><jupyter_text>Data preparation<jupyter_code>X = raw_data.sample(len(raw_data))
X = X.reset_index(drop=True)
X[target_id] = X[target_id].map(lambda x: 1 if x == target_value else 0)
y = X[target_id]
del X[target_id]
y_true = y<jupyter_output><empty_output><jupyter_text>As we'll used outlier detection techniques based on clustering, it is preferable to normalize data.<jupyter_code>from sklearn.preprocessing import MinMaxScaler
mms = MinMaxScaler()
X = pd.DataFrame(mms.fit_transform(X),columns=X.columns)
X.head(3)<jupyter_output><empty_output><jupyter_text>Unsupervised outliers detection<jupyter_code>from sklearn.metrics import roc_curve, auc

def auc_outliers_estimator(X, y_true, estimator):
    estimator.fit(X)
    y_test = estimator.predict_proba(X)
    fpr, tpr, _ = roc_curve(y_true, y_test)
    return auc(fpr, tpr)<jupyter_output><empty_output><jupyter_text>Each estimator has its own approach to detect outliers. See documentation for further explanations.<jupyter_code>from dsbox.ml.outliers import CovarianceOutliers
from dsbox.ml.outliers import GMMOutliers
from dsbox.ml.outliers import ClusteringOutliers
from dsbox.ml.outliers import KMeansOneClusterOutliers
score_per_estimator = {}
score = auc_outliers_estimator(X,y_true,CovarianceOutliers())
score_per_estimator['CovarianceOutlier'] = score
print(score)
score = auc_outliers_estimator(X,y_true,GMMOutliers())
score_per_estimator['GMMOutlier'] = score
print(score)
from sklearn.cluster import DBSCAN

# can be tricky to parametrize
score = auc_outliers_estimator(X,y_true,
                       ClusteringOutliers(cluster_estimator=DBSCAN(min_samples=15,eps=0.05), strategy='unclustered'))
score_per_estimator['ClusteringOutlier_unclustered'] = score
print(score)
from sklearn.cluster import MiniBatchKMeans

# can be instable due to random_state (try random_state=2... )
score = auc_outliers_estimator(X,y_true,
ClusteringOutliers(cluster_estimator=MiniBatchKMeans(n_clusters=10, random_state=0), 
                                         strategy='size'))
score_per_estimator['ClusteringOutlier_size'] = score
print(score)
score = auc_outliers_estimator(X,y_true,
ClusteringOutliers(cluster_estimator=MiniBatchKMeans(n_clusters=7, random_state=0), 
                                         strategy='frontier'))
score_per_estimator['ClusteringOutlier_frontier'] = score
print(score)
from sklearn.cluster import AgglomerativeClustering

score = auc_outliers_estimator(X,y_true,
                       ClusteringOutliers(cluster_estimator=AgglomerativeClustering(n_clusters=40), 
                                         strategy='density'))
score_per_estimator['ClusteringOutlier_density'] = score
print(score)
pd.DataFrame({'auc' : score_per_estimator}).sort_values('auc', ascending=False)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11338126972991933, 'fraction_numerical': 0.013065591020694493, 'mean_word_length': 6.195583596214511, 'pattern_counts': {'":': 0, '<': 52, '<?xml version=': 0, '>': 53, 'https://': 8, 'lorem ipsum': 0, 'www.': 3, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '11', 'dir': 'jupyter-structured-clean-dedup', 'id': '459436', 'license': 'Apache-2.0', 'n_tokens_mistral': 3837, 'n_tokens_neox': 3459, 'n_words': 1081, 'path': 'notebooks/OutliersDetection.ipynb', 'repo_name': 'Pandinosaurus/dsbox', 'size': '11434'}