# EliNAC: Autoencoder Approach for Electronic Invoices Data Clustering
## 3 ELINAC: ELICronic INvoices Autoencoder Clustering
### ELINAC's Clustering  
After the autoencoder processes the input data in ELINAC, we have our output data, where every row with a description has a value corresponding to its reconstruction error. The next step is applying our hypotheses that similar descriptions are already grouped by having similar reconstruction errors, and all that is left to do is to find these clusters and label them. Figure 5 shows how the reconstruction error increases for the first 150 rows by sorting the reconstruction value from the lowest to the highest value. It is observed that the data presents itself in \"steps\". Some of them are long, meaning that there are many similar descriptions, while others are short but also very high when only a few similar descriptions differ more from others. To be considered the start of a new cluster, the reconstruction error increase between two rows has to be higher than a threshold value used for comparison between every row. The process used for searching and labeling the clusters based on the autoencoder output in ELINAC is described in Algorithm 1. Keeping in mind that efficient time is one of the desirable factors for our clustering, the algorithm was based on the binary search algorithm because of its average-case complexity of \(O(\log N)\). The logarithmic complexity  
Figure 5: Visualization of clusters in a reconstruction error sample. is applied in the range of possible threshold \(T\), meaning the main loop has a complexity of \(O(\log T)\). For each iteration, the algorithm runs through every dataset row (lines 9 to 17), adding an extra \(O(N)\) complexity for every repetition. Therefore, the final complexity of our algorithm comes to \(O(I*N)\), where \(I\) represents the iterations of the while loop (average number of iterations when applying \(O(\log T)\)), and \(N\) is the dataframe size. The average value of \(I\) in our experiments was 10.5. Even when changing the values of _den_ (denominator value used to search the threshold ranging from 100 to 10,000), the number of clusters and the size of the dataset never surpassed 20 iterations. Therefore, the size of \(I\) does not scale with the value of \(N\), which would make the algorithm's final complexity \(O(N)\). ```
1:\(target\geq 0\)\(\triangleright\) Target amount of clusters
2:\(df\
eq NULL\)\(\triangleright\) Dataframe
3:\(den\gets 4000\)\(\triangleright\) Denominator of the threshold
4:\(flag\gets 0\)\(\triangleright\) Stop flag
5:\(clusters\gets 0\)\(\triangleright\) Clusters found
6:\(max\gets 0\)\(\triangleright\) Maximum denominator
7:\(min\gets 0\)\(\triangleright\) Minimum denominator
8:while\(clusters\
eq target\)and\(den\
eq flag\)do
9:\(clusters\gets 0\)
10:\(flag\gets den\)
11:forrow in df do
12:\(row.shifted\gets row.error.shift(1)\)
13:if\(row.error\geq row.shifted*1+(1/den)\)then
14:\(row.cluster\gets 1\)
15:\(clusters\gets clusters+1\)
16:else
17:\(row.cluster\gets 0\)
18:endif
19:endfor
20:if\(clusters>target\)then
21:\(max\gets den\)
22:\(den\leftarrow(max+min)/2\)
23:elseif\(max\
eq 0\)then
24:\(min\gets den\)
25:\(den\leftarrow(max+min)/2\)
26:else
27:\(den\gets den*2\)
28:endif
29:endwhile
```  
**Algorithm 1** Cluster algorithm. The main difference between the binary search algorithm and ELINAC's is that we do not have the start and end values used when searching a list. To solve this problem, Algorithm 1 initializes with a denominator value (_den_) (line 1), which is the value used to find the threshold. Based on the initial denominator value and the minimum (_min_) as 0, the algorithm runs its first iteration to check if the number of clusters found is higher or lower than our target (line 18). If higher, it assigns the initial max as the denominator in line 19, and if lower, it doubles the denominator value in line 25 until the condition in line 18 passes and the maximum (_max_) value is updated in line 19. Now that we know the maximum and minimum limits for our denominator, the algorithm looks for the middle.