# Clustering on the Chicago Array of Things: Spotting Anomalies in the Internet of Things Records
## 3 Methodology
### Algorithms  
The K-Means algorithm was first introduced in [29]. It is closely related to Lloyd's algorithm in [30], which generates Voronoi diagrams and was originally created for pulse-code modulation. In K-Means, \(k\) random points are chosen as centroids of the desired \(k\) clusters. The distance from each remaining point is then calculated between the centroids. After all points are assigned to exactly one cluster, the centroid is then calculated again. The process continues for several steps or until points are not re-partitioned. The distance calculation used is the Euclidean distance (or \(L_{2}\) norm).  
The K-Means algorithm is simple but effective. However, it is not guaranteed to obtain globally optimal clusters. For a more detailed description of K-means, please see [29].  
The DBSCAN algorithm was introduced in [31] and relies on clusters based on density rather than distance to a centroid. Multiple definitions are used to define density in [31], but the core rules are as follows:  
* A single parameter, \(minPts\), is used to determine density. This determines the minimal number of points any other point is density-connected to.
* Density connectivity: a point is density-connected to another point if there is an unbreakable chain of points from \(p\) to \(q\); here, each point in the \(p\)-\(q\) chain is, at most, \(\epsilon\) apart in distance.  
DBSCAN then merges clusters that are close to one another. This is performed by finding the smallest \(p\)-\(q\) distance where \(p\) is in one cluster and \(q\) is in another. The clusters are merged (i.e., combined to form a larger cluster) if this smallest distance is \(<=\epsilon\).  
The benefits to using DBSCAN over other methods are it does not rely on defining the number of clusters, the distance calculation can be different (unlike K-Means, which generally requires \(L_{2}\) distance), and the number of parameters to test is reduced to 2: \(\epsilon\) and \(minPts\). These hyper-parameters are global. The values can then be chosen through evaluation or a heuristic posed in [31] relying on distance from an arbitrary point \(p\) to its k-nearest neighbors. For a more detailed description of DBSCAN, please see [31].  
Hierarchical DBSCAN (H-DBSCAN) is introduced in [32]. It is a variation of DBSCAN and relies on a minimal spanning tree (MST) to generate a hierarchy for more advanced clustering. To generate this hierarchy, a new metric, the mutual reachability distance, is the maximal value of the core distances (\(\epsilon\)) of points \(p\), \(q\), or the distance between them. In contrast to the original DBSCAN algorithm, rather than merging clusters close together, H-DBSCAN starts with one cluster and uses the MST to split clusters off by sorting the MST by edge distance and splitting points off that match edge values. A new cluster is formed if the points split off have at least \(minPts\). This process iterates until all points have been split from the MST. Each new cluster keeps a reference to its parent cluster.  
From here, a stability value can be generated for each cluster. The stability of a leaf cluster (a cluster with no children) is compared against the stability of the parent cluster. If the child's stabilities are higher than the parent cluster's stability, these stability values propagate to the next parent until root. Otherwise, the parent cluster's stability propagates. In this way, there are no multiple clusters representing the same point. H-DBSCAN can also specify outliers in the data using information calculated for each point as the point was being placed into a cluster. For more information, a detailed description can be found in [33].