Time Series Data Cleaning: A Survey <s> C. DENSITY-BASED SPATIAL CLUSTERING OF APPLICATIONS WITH NOISE <s> Clustering algorithms are attractive for the task of class identification in spatial databases. However, the application to large spatial databases rises the following requirements for clustering algorithms: minimal requirements of domain knowledge to determine the input parameters, discovery of clusters with arbitrary shape and good efficiency on large databases. The well-known clustering algorithms offer no solution to the combination of these requirements. In this paper, we present the new clustering algorithm DBSCAN relying on a density-based notion of clusters which is designed to discover clusters of arbitrary shape. DBSCAN requires only one input parameter and supports the user in determining an appropriate value for it. We performed an experimental evaluation of the effectiveness and efficiency of DBSCAN using synthetic data and real data of the SEQUOIA 2000 benchmark. The results of our experiments demonstrate that (1) DBSCAN is significantly more effective in discovering clusters of arbitrary shape than the well-known algorithm CLAR-ANS, and that (2) DBSCAN outperforms CLARANS by a factor of more than 100 in terms of efficiency. <s> BIB001 </s> Time Series Data Cleaning: A Survey <s> C. DENSITY-BASED SPATIAL CLUSTERING OF APPLICATIONS WITH NOISE <s> Dirty data commonly exist. Simply discarding a large number of inaccurate points (as noises) could greatly affect clustering results. We argue that dirty data can be repaired and utilized as strong supports in clustering. To this end, we study a novel problem of clustering and repairing over dirty data at the same time. Referring to the minimum change principle in data repairing, the objective is to find a minimum modification of inaccurate points such that the large amount of dirty data can enhance the clustering. We show that the problem can be formulated as an integer linear programming (ILP) problem. Efficient approximation is then devised by a linear programming (LP) relaxation. In particular, we illustrate that an optimal solution of the LP problem can be directly obtained without calling a solver. A quadratic time approximation algorithm is developed based on the aforesaid LP solution. We further advance the algorithm to linear time cost, where a trade-off between effectiveness and efficiency is enabled. Empirical results demonstrate that both the clustering and cleaning accuracies can be improved by our approach of repairing and utilizing the dirty data in clustering. <s> BIB002
The DBSCAN BIB001 algorithm is a clustering method based on density-reachable relationship, which divides the region with sufficient density into clusters and finds clusters of arbitrary shape in the spatial database with noise and defines the cluster as the largest set of points connected by density. Then the algorithm defines the cluster according to the set density threshold as the basis for dividing the cluster, that is, when the threshold is satisfied, it can be considered as a cluster. The principle of DBSCAN algorithm: (1) DBSCAN searches for clusters by checking the Eps neighborhood of each point in the data set. If the Eps neighborhood of point p contains more points than MinPts, create a cluster with p as the core object; (2) Then, DBSCAN iteratively aggregates objects that are directly reachable from these core objects. This process may involve the consolidation of some density-reachable clusters; (3) When no new points are added to any cluster, the process ends. Where MinPts is the minimum number of neighbor points that a given point becomes the core object in the neighborhood, Eps is the neighborhood radius. For instance, Eps is 0.5 and MinPts is 3, for a given data set, the effect of clustering is as shown in Figure 7 . Some noise points can be repaired and clustered into classes adjacent to them. Recent research BIB002 has shown that after repairing erroneous data. They also perform cleaning experiments on GPS data based on DBSCAN, the accuracy of clustering on spatial data can be improved. But this method cannot solve continuous errors and needs further improvement.