# Unsupervised Novelty Detection Using Deep Autoencoders with Density Based Clustering
## 3 Methodology
### Density Based Clustering for Novelty Detection  
Density-based clustering locates regions of high density that are separated from one another by regions of low density [2]. DBSCAN [31] is a basic, simple and effective density-based clustering algorithm and it can find arbitrarily shaped clusters. In this algorithm, a user specifies two parameters eps which determine a maximum radius of the neighborhood and minPts which determine a minimum number of points in the eps of point. To automatically adjust the value of the eps parameter, we used the K-dist plot method [31] to calculate the nearest neighboring space for each point. The main idea is that if the point is contained in any cluster, its K-dist value is less than the size of the cluster and in the absence of any cluster, the value of K-dist will be high. Therefore, we have calculated the K-dist value for all points and placed it in ascending order and have chosen the optimal eps for the initial maximum change. When grouping the data via DBSCAN clustering algorithm, some points do not remain a part of any cluster. In the proposed method, we have considered data points which do not include any clusters as one whole cluster. After grouping of extracted low dimensional feature space (2D), find out which clusters are the novelty. DBSCAN algorithm cannot provide a degree of novelty score [32]. So, we use a final error threshold obtained from the second AE model to make a novelty detection. If the majority of instances of the cluster exceed the threshold, the whole cluster is considered a novelty. Algorithm 2's computational complexity is defined as:  
* Calculate nearest neighbors is O(dn\({}^{3}\)) where d is dimension and n is the number of samples
* DBSCAN clustering is O(n\({}^{2}\))
* Identify novelty is O(n)  
In Algorithm 2 shows how to discover novelty step by step:  
```
1:Input: Set of points Z, {\(Z_{i=1}^{n}\)}, set op points X, {\(X_{i=1}^{n}\)}
2:Output: X, {\(X_{i=1}^{n}\)} #with decision
3:nbrs \(\leftarrow\) NearestNeighbors (n_neighbors=3).fit (Z)
4:distance \(\leftarrow\) nbrs.kneighbors (Z)
5:distance.sort()
6:eps \(\leftarrow\) first extreme value of distance
7:cluster \(\leftarrow\) dbscan(Z, eps)
8: n_clusters \(\leftarrow\) len(cluster.labels_)
9:X[labels] \(\leftarrow\) cluster.labels_
10:dict_error \(\leftarrow\) |
11:for i=0 to n_clusters do
12:bool_values \(\leftarrow\) (X [labels_] == i )
13:cluster_i set \(\leftarrow\) Z[boolvalues]
14:n_instance_in_cluster_i = len(cluster_i_set)
15: error_count = 0
16:for j in n_instance_in_cluster_i do
17:if cluster_i set[j] > final_threshold
18:error_count \(\leftarrow\) error_count + 1
19:endif
20:endfor
21:dict_error[i] \(\leftarrow\) error_count
22:endfor
23:for i=0 to n_clusters do
24:cluster_i \(\leftarrow\) X[db_labels == i]
25:n_of_instance \(\leftarrow\) len(cluster_i)
26:if n_of_instance * 0.5 less than or equal to dict_error.get(i)
27:X.update[ all rows in cluster, labels ] = 1 #novelty
28:else
29:X. update[ all rows in cluster, labels ] = 0 #normal
30:endif
31:endfor
32:return X
```  
**Algorithm 2** Identify novelty. We have summarized the general architecture solutions in Algorithm 3 and the dimensionality reduction and have identified the novelties that are contained in it, which have been summarized in Algorithms 1 and 2. ```
1:Input: Set of points \(\mathrm{X}\), \(\{\mathrm{X}_{i=1}^{n}\}\)
2:Output: \(\mathrm{Y}\), \(\{\mathrm{Y}_{i=1}^{n}\}\) #decision
3:\(\mathrm{Z}\leftarrow\) Dimensionality reduction(\(\mathrm{X}\))
4:\(\mathrm{Y}\leftarrow\) Identify novelty(\(\mathrm{Z}\))
5:return\(\mathrm{Y}\)
```  
**Algorithm 3** DAE-DBC algorithm. High-dimensional data can cause problems for data mining and analysis [24]; also, this curse of dimensionality problem introduced by [PERSON] [33]. To avoid this problem, we have proposed a method instead of grouping directly the input data, to group the low dimensional representation of the input. The advantage of the proposed method is that by calculating the error threshold in two stages, making it more precise novelty detection.