Search

Clustering is one of the most important unsupervised machine learning tasks. It is widely used to solve problems of intrusion detection, text analysis, image segmentation etc. Subspace clustering is the most important method for high-dimensional data clustering. In order to solve the problem of parallel subspace clustering for high-dimensional big data, this paper proposes a parallel subspace clustering algorithm based on spark named PSubCLUS which is inspired by SubCLU, a classical subspace clustering algorithm. While Spark is the most popular big data parallel processing platform currently, PSubCLUS uses the Resilient Distributed Datasets (RDD) provided by Spark to store data points in a distributed way. The two main performing stages of this algorithm, one-dimensional subspace clustering and iterative clustering, can be executed in parallel on each worker node of cluster. PSubCLUS also uses a repartition method based on the number of data points to achieve load balancing. Experimental results show that PSubCLUS has good parallel speedup and ideal load balancing effect, which is suitable for solving the parallel subspace clustering of high-dimensional big data.

In the era of big data, it is increasingly common that large amount of data is generated across multiple distributed sites and cannot be gathered into a centralized site for further analysis, which invalidates the assumption of traditional clustering techniques based on centralized models. The major challenge is that these distributed datasets cannot be trivially merged due to issues such as privacy concerns, limited network bandwidth among sites and limited computational capacity of a single site. To tackle this challenge, we propose an efficient distributed clustering scheme using boundary information (DCUBI), which features good flexibility and scalability. The main procedure of DCUBI consists of three steps: local-global-local. Firstly, each local site extracts the boundary points from its own local data and applies traditional clustering on boundary points only. Secondly, labeled boundary points from each site are sent to the central site as local representatives where boundary and cluster fusion is conducted to form the global clustering model. Finally, the global boundary and cluster information is sent back to each local site for refined local clustering. To demonstrate the effectiveness of DCUBI, we plug the well-known DBSCAN algorithm into DCUBI and comprehensive experiments are conducted using datasets with different properties. Experiment results clearly verify the quality of clustering by DCUBI as well as its superior time efficiency when the volume of data in each site is large. Furthermore, other popular clustering techniques especially those with high time complexity such as spectral clustering and affinity propagation clustering are also plugged into DCUBI to demonstrate the flexibility of the proposed scheme.

This paper proposes an improved adaptive density-based spatial clustering of applications with noise (DBSCAN) algorithm based on genetic algorithm and MapReduce parallel computing programming framework to improve the poor clustering effect and low efficiency of the DBSCAN algorithm, which due to experiential solving parameters. The size of Intensive Interval Threshold minPts and Scan Radius Eps would be rational planned by genetic algorithm iterative optimization, and it is secondary statute processing with the similarity and variability of the dataset and the efficient computing power of Hadoop Cluster. The data could be reasonable serialization, and the efficient adaptive parallel clustering could be achieved ultimately. Through the experimental results, it is shown that the proposed algorithm in this paper has higher clustering accuracy and execution efficiency than that of the comparison baselines. The trend will continue to grow with the increased volume of dataset. The improved algorithm provides a more accurate implementation method for the threshold of DBSCAN algorithm, and realizes the specific calculation process, which provides practice support for the realization of DBSCAN.

Density Based Spatial Clustering of Applications with Noise (DBSCAN), a well-known Density-Based Clustering Algorithm is a advanced data clustering method with various applications in numerous fields like Satellites images, X-ray crystallography, Anomaly Detection in Temperature Data. But its run time R(n2) complexity draws a major challenge. In this research paper, we propose a new unique algorithm called Real Time Density Based Clustering RTDBC to minimize the problems in DBSCAN. In proposed algorithms, objects are allotted into clusters using labels representatives than the method of propagating directly to reduce propagation time of label considerably. In contrast, RTDBC produce fast result and continuous process of runtime and additionally users are permitted to suspend for testing the result and continue as to enhance good results.

This research introduces a new method for the identification of local retail agglomerations within Great Britain, implementing a modification of the established density based spatial clustering of applications with noise (DBSCAN) method that improves local sensitivity to variable point densities. The variability of retail unit density can be related to both the type and function of retail centers, but also to characteristics such as size and extent of urban areas, population distribution, or property values. The suggested method implements a sparse graph representation of the retail unit locations based on a distance-constrained k-nearest neighbor adjacency list that is subsequently decomposed using the Depth First Search algorithm. DBSCAN is iteratively applied to each subgraph to extract the clusters with point density closer to an overall density for each study area. This innovative approach has the advantage of adjusting the radius parameter of DBSCAN at the local scale, thus improving the clustering output. A comparison of the estimated retail clusters against a sample of existing boundaries of retail areas shows that the suggested methodology provides a simple yet accurate and flexible way to automate the process of identifying retail clusters of varying shapes and densities across large areas; and by extension, enables their automated update over time.

Anomaly is an important and influential element in Wireless Sensor Networks that affects the integrity of data. On account of the fact that these networks cannot be supervised, this paper, therefore, deals with the problem of anomaly detection. First, the three features of temperature, humidity, and voltage are extracted from the network traffic. Then, network data are clustered using the density-based spatial clustering of applications with noise (DBSCAN) algorithm. It also analyzes the accuracy of DBSCAN algorithm input data with the help of density-based detection techniques. This algorithm detects the points in regions with low density as anomaly. By using normal data, it trains support vector machine. And, finally, it removes anomalies from network data. The proposed algorithm is evaluated by the standard and general data set of Intel Berkeley Research lab (IRLB). In this paper, we could obliterate DBSCAN's problem in selecting input parameters by benefiting from coefficient correlation. The advantage of the proposed algorithm over previous ones is in using soft computing methods, simple implementation, and improving detection accuracy through simultaneous analysis of those three features.

The main purpose of the process of data mining is to extract useful information from a huge amount of dataset. As one of the most important tasks in data mining, clustering is the process of grouping object attributes and features such that the data objects in one group are more similar than data objects in another group. It is a form of unsupervised learning that means how data should be grouped the data objects (similar types) together will be not known in advance. The algorithms used for clustering are k-means algorithm, k-medoid algorithm, k-nearest neighbour algorithm, k-mode algorithm etc. The K-Mode Algorithm is an eminent algorithm which is an extension of the K-Means Algorithm for clustering data set with categorical attributes and is famous for its simplicity and speed. The ‘Simple Matching Dissimilarity’ measure is used instead of Euclidean distance and the ‘Mode’ of clusters is used instead of ‘Means’. In this paper, review on the K-Mode Algorithm is done.

At SIGMOD 2015, an article was presented with the title “DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation” that won the conference’s best paper award. In this technical correspondence, we want to point out some inaccuracies in the way DBSCAN was represented, and why the criticism should have been directed at the assumption about the performance of spatial index structures such as R-trees and not at an algorithm that can use such indexes. We will also discuss the relationship of DBSCAN performance and the indexability of the dataset, and discuss some heuristics for choosing appropriate DBSCAN parameters. Some indicators of bad parameters will be proposed to help guide future users of this algorithm in choosing parameters such as to obtain both meaningful results and good performance. In new experiments, we show that the new SIGMOD 2015 methods do not appear to offer practical benefits if the DBSCAN parameters are well chosen and thus they are primarily of theoretical interest. In conclusion, the original DBSCAN algorithm with effective indexes and reasonably chosen parameter values performs competitively compared to the method proposed by Gan and Tao.

DBSCAN is a method proposed in 1996 for clustering multi-dimensional points, and has received extensive applications. Its computational hardness is still unsolved to this date. The original KDD‚96 paper claimed an algorithm of O ( n log n ) ”average runtime complexity„ (where n is the number of data points) without a rigorous proof. In 2013, a genuine O ( n log n )-time algorithm was found in 2D space under Euclidean distance. The hardness of dimensionality d ≥3 has remained open ever since. This article considers the problem of computing DBSCAN clusters from scratch (assuming no existing indexes) under Euclidean distance. We prove that, for d ≥3, the problem requires ω( n 4/3 ) time to solve, unless very significant breakthroughs—ones widely believed to be impossible—could be made in theoretical computer science. Motivated by this, we propose a relaxed version of the problem called ρ- approximate DBSCAN , which returns the same clusters as DBSCAN, unless the clusters are ”unstable„ (i.e., they change once the input parameters are slightly perturbed). The ρ-approximate problem can be settled in O ( n ) expected time regardless of the constant dimensionality d . The article also enhances the previous result on the exact DBSCAN problem in 2D space. We show that, if the n data points have been pre-sorted on each dimension (i.e., one sorted list per dimension), the problem can be settled in O ( n ) worst-case time. As a corollary, when all the coordinates are integers, the 2D DBSCAN problem can be solved in O ( n log log n ) time deterministically, improving the existing O ( n log n ) bound.

Many advanced clustering techniques are effective in dealing datasets in complicated situations. However, when facing large datasets, which are increasingly common in the era of big data, the time requirements of most existing techniques can quickly become intolerable. To tackle this challenge, in this paper, we propose Scalable Clustering Using Boundary Information (SCUBI), a highly flexible and scalable clustering scheme. The idea of SCUBI is to identify the boundary points of the original dataset in the first place and then group boundary points into suitable clusters using existing clustering techniques. Finally, the rest points are assigned to the same cluster as their nearest boundary points. To demonstrate the effectiveness and scalability of SCUBI, we plug the well-known DBSCAN algorithm into SCUBI. Comprehensive experiments are conducted using datasets with up to two million data points to compare the clustering results and time efficiency between DBSCAN and SCUBI-DBSCAN. Experimental results show that our method can obtain almost identical clustering results as the standard DBSCAN while achieving orders of magnitude speedup especially on large datasets, which confirms the scalability of SCUBI. Experiments are also performed on other clustering algorithms with high time complexity to verify the flexibility of SCUBI.

In big data situation, to detect clusters of different size and shape is a challenging and imperative task. Density based clustering approaches have been widely used in many areas of science due to its simplicity and the ability to detect clusters of different sizes and shapes over the last several years. With diverse conversion on categorical data, a modified version of the DBSCAN algorithm is proposed to cluster mixed data, noted as density based clustering algorithm for mixed data with integration of entropy and probability distribution (EPDCA). Optional and various conversions are provided for clustering process with adaptability. Some benchmark data sets from UCI have been selected for testing the capability and validity of EPDCA. It was shown that the clustering results of EPDCA are considerably improved, especially on automatically number of clusters formed, noise discovery and time elapsed to form clusters.

By combining linear discriminant analysis and Kmeans into a coherent framework, a dimension reduction algorithm was recently proposed to select the most discriminative subspace. This algorithm utilized the clustering method to generate cluster labels and after that employed discriminant analysis to do subspace selection. However, we found that this algorithm only considers the information of global structure, and does not take into account the information of local structure. In order to overcome the shortcoming mentioned above, this paper presents a dimension reduction algorithm preserving both global and local clustering structure. Our algorithm is an unsupervised linear dimension reduction algorithm suitable for the data with cloud distribution. In the proposed algorithm, the Kmeans clustering method is adopted to generate the clustering labels for all data in the original space. And then, the obtained clustering labels are utilized to describe the global and local clustering structure. Finally, the objective function is established to preserve both the local and global clustering structure. By solving this objective function, the projection matrix and the corresponding subspace are yielded. In this way, the global and local information of the clustering structure are integrated into the process of the subspace selection, in fact, the structure discovery and the subspace selection are performed simultaneously in our algorithm. Encouraging experimental results are achieved on the artificial dataset, real-life benchmark dataset and AR face dataset.

The density based notion for clustering approach is used widely due to its easy implementation and ability to detect arbitrary shaped clusters in the presence of noisy data points without requiring prior knowledge of the number of clusters to be identified. Density-based spatial clustering of applications with noise (DBSCAN) is the first algorithm proposed in the literature that uses density based notion for cluster detection. Since most of the real data set, today contains feature space of adjacent nested clusters, clearly DBSCAN is not suitable to detect variable adjacent density clusters due to the use of global density parameter neighborhood radius Nrad and minimum number of points in neighborhood Npts. So the efficiency of DBSCAN depends on these initial parameter settings, for DBSCAN to work properly, the neighborhood radius must be less than the distance between two clusters otherwise algorithm merges two clusters and detects them as a single cluster. Through this paper: 1) We have proposed improved version of DBSCAN algorithm to detect clusters of varying density adjacent clusters by using the concept of neighborhood difference and using the notion of density based approach without introducing much additional computational complexity to original DBSCAN algorithm. 2) We validated our experimental results using one of our authors recently proposed space density indexing (SDI) internal cluster measure to demonstrate the quality of proposed clustering method. Also our experimental results suggested that proposed method is effective in detecting variable density adjacent nested clusters.

Many application scenarios involve sequential data, but most existing clustering methods do not well utilize the order information embedded in sequential data. In this paper, we study the subspace clustering problem for sequential data and propose a new clustering method, namely ordered sparse clustering with block-diagonal prior (BD-OSC). Instead of using the sparse normalizer in existing sparse subspace clustering methods, a quadratic normalizer for the data sparse representation is adopted to model the correlation among the data sparse coefficients. Additionally, a block-diagonal prior for the spectral clustering affinity matrix is integrated with the model to improve clustering accuracy. To solve the proposed BD-OSC model, which is a complex optimization problem with quadratic normalizer and block-diagonal prior constraint, an efficient algorithm is proposed. We test the proposed clustering method on several types of databases, such as synthetic subspace data set, human face database, video scene clips, motion tracks, and dynamic 3-D face expression sequences. The experiments show that the proposed method outperforms state-of-the-art subspace clustering methods.

In this paper, we propose a real-time image superpixel segmentation method with 50 frames/s by using the density-based spatial clustering of applications with noise (DBSCAN) algorithm. In order to decrease the computational costs of superpixel algorithms, we adopt a fast two-step framework. In the first clustering stage, the DBSCAN algorithm with color-similarity and geometric restrictions is used to rapidly cluster the pixels, and then, small clusters are merged into superpixels by their neighborhood through a distance measurement defined by color and spatial features in the second merging stage. A robust and simple distance function is defined for obtaining better superpixels in these two steps. The experimental results demonstrate that our real-time superpixel algorithm (50 frames/s) by the DBSCAN clustering outperforms the state-of-the-art superpixel segmentation methods in terms of both accuracy and efficiency.

The DBSCAN algorithm is a well-known density-based clustering approach particularly useful in spatial data mining for its ability to find objects' groups with heterogeneous shapes and homogeneous local density distributions in the feature space. Furthermore, it can be suitable as scaling down approach to deal with big data for its ability to remove noise. Nevertheless, it suffers for some limitations, mainly the inability to identify clusters with variable density distributions and partially overlapping borders, which is often a characteristics of both scientific data and real-world data. To this end, in this work, we propose three fuzzy extensions of the $$\textit{DBSCAN}$$DBSCAN algorithm to generate clusters with distinct fuzzy density characteristics. The original version of $$\textit{DBSCAN}$$DBSCAN requires two precise parameters (minPts and $$\epsilon $$∈) to define locally dense areas which serve as seeds of the clusters. Nevertheless, precise values of both parameters may be not appropriate in all regions of the dataset. In the proposed extensions of $$\textit{DBSCAN}$$DBSCAN, we define soft constraints to model approximate values of the input parameters. The first extension, named $$\textit{Fuzzy Core DBSCAN}$$Fuzzy CoreDBSCAN, relaxes the constraint on the neighbourhood's density to generate clusters with fuzzy core points, i.e. cores with distinct density; the second extension, named $$\textit{Fuzzy Border DBSCAN}$$Fuzzy BorderDBSCAN, relaxes $$\epsilon $$∈ to allow the generation of clusters with overlapping borders. Finally, the third extension, named $$\textit{Fuzzy DBSCAN}$$Fuzzy DBSCAN subsumes the previous ones, thus allowing to generate clusters with both fuzzy cores and fuzzy overlapping borders. Our proposals are compared w.r.t. state of the art fuzzy clustering methods over real-world datasets.

Paper presents the work on development and validation of spatio-temporal clustering technique called ST-OPTICS.Emphasis has also been laid down on validation using performance indices.Capable to handle all types of dimensions i.e. spatial, non-spatial and temporal.It gives micro level clusters, agglomeration has been done for better visualization and interpretation.Results (average runtime & quality of clusters) found to be better than existing technique. Spatio-temporal data mining (STDM) is a process of the extraction of implicit knowledge, spatial and temporal relationships, or other patterns not explicitly stored in spatio-temporal databases. As data are growing not only from static view point, but they also evolve spatially and temporally which is dynamic in nature that is the reason why this field is now becoming very important field of research. In addition, spatio-temporal (ST) data tend to be highly auto-correlated, which leads to failure of assumption of independence, which is there in Gaussian distribution model. Vital issues in spatio temporal clustering technique for earth observation data is to obtain clusters of, good quality, arbitrary shape, problem of nested clustering and their validation. The present paper addresses these issues and proposes their solutions. In this direction, an attempt has been made to develop a clustering algorithm named as "Spatio-Temporal - Ordering Points to Identify Clustering Structure (ST-OPTICS)" which is modified version of existing density based technique - "Ordering Points to Identify Clustering Structure (OPTICS)". Experimental work carried out is analysed and found that quality of clusters obtained and run time efficiency are much better than existing technique i.e. ST-DBSCAN. In order to improve the visualization and the interpretation of obtained micro level clusters, sincere effort has been put in to merge the obtained clusters using agglomerative approach. Performance evaluation is done in both ways i.e. qualitatively and quantitatively for cross validating the results. Results show performance improvement of proposed ST-OPTICS clustering technique compared to ST-DBSCAN algorithm.

Density based clustering methods are proposed for clustering spatial databases with noise. Density Based Spatial Clustering of Applications with Noise (DBSCAN) can discover clusters of arbitrary shape and also handles outliers effectively. DBSCAN obtains clusters by finding the number of points within the specified distance from a given point. It involves computing distances from given point to all other points in the dataset. The conventional index based methods construct a hierarchical structure over the dataset to speed-up the neighbor search operations. The hierarchical index-structures fail to scale for datasets of dimensionality above 20. In this paper, we propose a novel graph-based index structure method Groups that accelerates the neighbor search operations and also scalable for high dimensional datasets. Experimental results show that the proposed method improves the speed of DBSCAN by a factor of about 1.5-2.2 on benchmark datasets. The performance of DBSCAN degrades considerably with noise due to unnecessary distance computations introduced by noise points while the proposed method is robust to noise by pruning out noise points early and eliminating the unnecessary distance computations. The cluster results produced by our method are exactly similar to that of DBSCAN but executed at a much faster pace. A graph-based index structure is built for speeding up neighbor search operations.No additional inputs are required to build the index structure.Proposed method is scalable for high-dimensional datasets.Handles noise effectively to improve the performance of DBSCAN.

Clustering image pixels is an important image segmentation technique. While a large amount of clustering algorithms have been published and some of them generate impressive clustering results, their performance often depends heavily on user-specified parameters. This may be a problem in the practical tasks of data clustering and image segmentation. In order to remove the dependence of clustering results on user-specified parameters, we investigate the characteristics of existing clustering algorithms and present a parameter-free algorithm based on the DSets (dominant sets) and DBSCAN (Density-Based Spatial Clustering of Applications with Noise) algorithms. First, we apply histogram equalization to the pairwise similarity matrix of input data and make DSets clustering results independent of user-specified parameters. Then, we extend the clusters from DSets with DBSCAN, where the input parameters are determined based on the clusters from DSets automatically. By merging the merits of DSets and DBSCAN, our algorithm is able to generate the clusters of arbitrary shapes without any parameter input. In both the data clustering and image segmentation experiments, our parameter-free algorithm performs better than or comparably with other algorithms with careful parameter tuning.

Our method automatically detects the correct number of clusters.Our method does not need any prior knowledge to choose the cluster centers.Our method retains only one input parameter to process the data.Our method has a robust performance on the DGF problem. Recently a delta-density based clustering (DDC) algorithm was proposed to cluster data efficiently by fast searching density peaks. In the DDC method, the density and a new-defined criterion delta-distance are utilized. The examples with anomalously large delta-density values are treated as cluster centers, then the remaining are assigned the same cluster label as their neighbor with higher density. However there are two challenges for the DDC algorithm. First, no rules are available to judge density-delta values as "anomalously large" or not. Second, the decision graph might produce the redundant examples with "anomalous large" density-delta values, as we define as the "decision graph fraud" problem. In this paper, an improved and automatic version of the DDC algorithm, named as 3DC clustering, is proposed to overcome those difficulties. The 3DC algorithm is motivated by the divide-and-conquer strategy and the density-reachable concept in the DBSCAN framework. It can automatically find the correct number of clusters in a recursive way. Experiments on artificial and real world data show that the 3DC clustering algorithm has a comparable performance with the supervised-clustering baselines and outperforms the unsupervised DDCs, which utilize the novelty detection strategies to select the "anomalously large" density-delta examples for cluster centers.

New simple and fast method for robust background image estimation from video stream is offered. The method is based on Markov Random Field, Belief Propagation and DBSCAN algorithms. The usage of cyclic graph MRF model of nonoverlapping image patches with narrow set of background hypotheses generated by DBSCAN algorithm provides faster convergence of Belief Propagation with accuracy comparable to the state-of-art methods

As a research branch of data mining, clustering, as an unsupervised learning scheme, focuses on assigning objects in the dataset into several groups, called clusters, without any prior knowledge. Density-Based Spatial Clustering of Applications with Noise (DBSCAN) is one of the most widely used clustering algorithms for spatial datasets, which can detect any shapes of clusters and can automatically identify noise points. However, there are several troublesome limitations of DBSCAN: (1) the performance of the algorithm depends on two specified parameters, e and MinPts in which e represents the maximum radius of a neighborhood from the observing point and MinPts means the minimum number of data points contained in such a neighborhood. (2) The time consumption for searching the nearest neighbors of each object is intolerable in the cluster expansion. (3) Selecting different starting points results in quite different consequences. (4) DBSCAN is unable to identify adjacent clusters of various densities. In addition to these restrictions about DBSCAN mentioned above, the identification of border points is often ignored. In our paper, we successfully solve the above problems. Firstly, we improve the traditional locality sensitive hashing method to implement fast query of nearest neighbors. Secondly, several definitions are redefined on the basis of the influence space of each object, which takes the nearest neighbors and the reverse nearest neighbors into account. The influence space is proved to be sensitive to local density changes to successfully reduce the amount of parameters and identify adjacent clusters of different densities. Moreover, this new relationship based on the influence space makes the insensitivity to the ordering of inputting points possible. Finally, a new concept-core density reachable based on the influence space is put forward which aims to distinguish between border objects and noisy objects. Several experiments are performed which demonstrate that the performance of our proposed algorithm is better than the traditional DBSCAN algorithm and the improved algorithm IS-DBSCAN.

Data clustering is a method of putting same data object into group. A clustering rule does partitions of a data set into many groups supported the principle of maximizing the intra-class similarity and minimizing the inter-class similarity. Finding clusters in object, particularly high dimensional object, is difficult when the clusters are different shapes, sizes, and densities, and when data contains noise and outliers. This paper provides a new clustering algorithm for normalized data set and proven that our new planned clustering approach work efficiently when dataset are normalized.

This paper proposes a subspace clustering algorithm with automatic feature grouping for clustering high-dimensional data. In this algorithm, a new component is introduced into the objective function to capture the feature groups and a new iterative process is defined to optimize the objective function so that the features of high-dimensional data are grouped automatically. Experiments on both synthetic data and real data show that the new algorithm outperforms the FG-k-means algorithm in terms of accuracy and choice of parameters. HighlightsWe study the problem of subspace clustering with feature grouping.We propose a k-means-type algorithm by incorporating feature grouping into the objective function.The algorithm is able to determine feature groups automatically.Experiments on synthetic and real data show that the algorithm performs well.

This research introduces extremely fast and scalable clustering algorithm.The proposed algorithm detects automatically clusters number.Furthermore, this algorithm uses three insensitive tuning parameters. Clustering multi-dense large scale high dimensional numeric datasets is a challenging task duo to high time complexity of most clustering algorithms. Nowadays, data collection tools produce a large amount of data. So, fast algorithms are vital requirement for clustering such data. In this paper, a fast clustering algorithm, called Dimension-based Partitioning and Merging (DPM), is proposed. In DPM, first, data is partitioned into small dense volumes during the successive processing of dataset dimensions. Then, noise is filtered out using dimensional densities of the generated partitions. Finally, merging process is invoked to construct clusters based on partition boundary data samples. DPM algorithm automatically detects the number of data clusters based on three insensitive tuning parameters which decrease the burden of its usage. Performance evaluation of the proposed algorithm using different datasets shows its fastness and accuracy compared to other clustering competitors.

Data clustering plays an important role in partitioning the large set of data objects into known/unknown number of groups or clusters so that the objects in each cluster are having high degree of similarity while objects in different clusters are dissimilar to each other. Recently a number of data clustering methods are explored by using traditional methods as well as nature inspired swarm intelligence algorithms. In this paper, a new data clustering method using modified bat algorithm is presented. The experimental results show that the proposed algorithm is suitable for data clustering in an efficient and robust way.

Entropy weighting used in some soft subspace clustering algorithms is sensitive to the scaling parameter. In this paper, we propose a novel soft subspace clustering algorithm by using log-transformed distances in the objective function. The proposed algorithm allows users to choose a value of the scaling parameter easily because the entropy weighting in the proposed algorithm is less sensitive to the scaling parameter. In addition, the proposed algorithm is less sensitive to noises because a point far away from its cluster center is given a small weight in the cluster center calculation. Experiments on both synthetic datasets and real datasets are used to demonstrate the performance of the proposed algorithm.

Speaker diarization is the task of determining the speakers for unlabeled data, and DBSCAN (Density-Based Spatial Clustering of Applications with Noise) has been widely used in the field of speaker diarization for its simplicity and computational efficiency. One challenging issue, however, is that if different clusters in non-spatial dataset are adjacent to each other, over-clustering may occur which subsequently degrades the performance of DBSCAN. In this paper, we identify the drawbacks of DBSCAN and propose a new density clustering algorithm based on local distribution property around object. Variable density criterions for local density and spreadness of object are used for effective data clustering. We compare the proposed algorithm to DBSCAN in terms of clustering accuracy. Experimental results confirm that the proposed algorithm exhibits higher accuracy than DBSCAN without over-clustering and confirm that the new approach based on local density and object spreadness is efficient.

Graphics processing units (GPUs) have been utilized to improve the processing speed of many conventional data mining algorithms. DBSCAN, a popular clustering algorithm that has been often used in practice, was extended to execute on a GPU. However, existing GPU-based DBSCAN extensions still have impediments in that the distances from all objects need to be repeatedly computed to find the neighbor objects and the objects and intermediate clustering results are stored in costly off-chip memory of the GPU. This paper proposes CudaSCAN, a novel algorithm that improves the efficiency of DBSCAN by making better use of the GPU. CudaSCAN consists of three phases: (1) partitioning the entire dataset into sub-regions of size of an integer multiple of the on-chip shared memory size in the GPU; (2) local clustering within sub-regions in parallel; and (3) merging the local clustering results. CudaSCAN allows an overlap between sub-regions to ensure independent, parallel local clustering in each sub-region, which in turn enables for objects and/or intermediate results to be stored in on-chip shared memory that has an access cost a few hundred times cheaper than that of off-chip global memory. The independence also enables for merging to be parallelized. This paper proves the correctness of CudaSCAN, and according to our extensive experiments, CudaSCAN outperforms CUDA-DClust, a previous GPU-based DBSCAN extension, by up to 163.6 times.

This paper discusses on the research on granular computing from 2012 to 2014.We defined four perspectives of classification schemes to map the selected studies.A total of 112 relevant published articles in established journals have been studied.39% of the relevant articles belong to a rough set framework.Fuzzy-GrC algorithm has outperformed other clustering algorithms in experiments. Granular computing has attracted many researchers as a new and rapidly growing paradigm of information processing. In this paper, we apply systematic mapping study to classify the granular computing researches to discover relative derivations to specify its research strength and quality. Our search scope is limited to the Science Direct and IEEE Transactions papers published between January 2012 and August 2014. We defined four perspectives of classification schemes to map the selected studies that are focus area, contribution type, research type and framework. Results of mapping the selected studies show that almost half of the research focused area belongs to category of data analysis. In addition, most of the selected papers belong to proposing the solutions in research type scheme. Distribution of papers between tool, method and enhancement categories of contribution type are almost equal. Moreover, 39% of the relevant papers belong to the rough set framework. The results show that there is little attention paid to cluster analysis in existing frameworks to discover granules for classification. We applied five clustering algorithms on three datasets from UCI repository to compare the form of information granules, and then classify the patterns and define them to a specific class based on their geometry and belongings. The clustering algorithms are DBSCAN, c-means, k-means, GAk-means and Fuzzy-GrC and the comparison of information granules are based on the coverage, misclassification and accuracy. The survey of experimental results mostly shows Fuzzy-GrC and GAk-means algorithm superior to other clustering algorithms; while, c-means clustering algorithm shows inferior to other clustering algorithms.

Propose a grid-based clustering algorithm, which is efficient O(N?log??N).Take the idea of region growing in image processing into the clustering algorithm.Significantly faster than k-means variants, such as litekmeans and PRS, spectral clustering, DBSCAN and Greedy EM.The clustering results are comparable to the other clustering algorithms.It is very suitable for real geo-spatial data sets. Geo-spatial data with geographical information explodes as the development of GPS-devices. The data contains certain patterns of users. To dig out the patterns behind the data efficiently, a grid-growing clustering algorithm is introduced. The proposed algorithm takes use of a grid structure, and a novel clustering operation is presented, which considers a grid growing method on the grid structure. The grid structure brings the benefit of efficiency. For large geo-spatial data, the algorithm has competitive strength on the running time. The total time complexity of the algorithm is O(N?log??N), where the time complexity mainly comes from the seed selection step. The grid-growing clustering algorithm is useful when the number of clusters is unknown since the algorithm requires no parameter on the number of clusters. The clusters detected could have arbitrary shapes. Furthermore, sparse areas are treated as outliers/noises in the algorithm. An empirical study on several data sets indicates that the proposed algorithm works much more efficiently than other popular clustering algorithms.

The basic DBSCAN (Density-Based Spatial Clustering of Applications with Noise) algorithm uses minimum number of input parameters, very effective to cluster large spatial databases but involves more computational complexity. The present paper proposes a new strategy to reduce the computational complexity associated with the DBSCAN by efficiently implementing new merging criteria at the initial stage of evolution of clusters. Further new density based clustering (DBC) algorithms are proposed considering correlation coefficient as similarity measure. These algorithms though computationally not efficient, found to be effective when there is high similarity between patterns of dataset. The computations associated with DBC based on correlation algorithms are reduced with new cluster merging criteria. Test on several synthetic and real datasets demonstrates that these computationally efficient algorithms are comparable in accuracy to the traditional one. An interesting application of the proposed algorithm has been demonstrated to identify the regional hazard regions present in the seismic catalog of Japan.

The paper presents the hybrid model of the objective clustering inductive technology based on complex using of the self-organizing SOTA and the density DBSCAN clustering algorithms. The inductive methods of complex systems analysis were used as the basis to implement the objective clustering inductive technology of gene expression profiles. To estimate the clustering quality for equal power subsets (include the same quantity of pairwise similar objects) the complex multiplicative criterion was calculated as the combination of the Calinski-Harabasz criterion and WB-index. The external clustering quality criterion is calculated as the normalized difference of the internal clustering quality criteria for the equal power subsets. The final decision concerning the determination of the optimal parameters of the clustering algorithm operation is done based on the maximum value of the Harrington desirability function that takes into account both the character of the objects and the clusters distribution in various clustering and the difference between clustering, which are implemented on the equal power subsets. The studied data grouping within the framework of the objective clustering inductive technology was performed in two stages. Firstly, the studied gene expression profiles were grouped with the use DBSCAN clustering algorithm. Then, the obtained set of gene expression profiles was divided into two clusters using SOTA clustering algorithm. This step-by-step procedure of the data clustering crates the conditions to save more useful information for following data processing.

Recent benchmark studies show that MPI-based distributed implementations of DBSCAN, e.g., PDSDBSCAN, outperform other implementations such as apache Spark etc. However, the communication cost of MPI DBSCAN increases drastically with the number of processors, which makes it inefficient for large scale problems. In this paper, we propose PS-DBSCAN, a parallel DBSCAN algorithm that combines the disjoint-set data structure and Parameter Server framework, to minimize communication cost. Since data points within the same cluster may be distributed over different workers which result in several disjoint-sets, merging them incurs large communication costs. In our algorithm, we employ a fast global union approach to union the disjoint-sets to alleviate the communication burden. Experiments over the datasets of different scales demonstrate that PS-DBSCAN outperforms the PDSDBSCAN with 2-10 times speedup on communication efficiency. We have released our PS-DBSCAN in an algorithm platform called Platform of AI (PAI) in Alibaba Cloud.

Technological advancements in todays information age has helped the researchers to capture digital footprints of humans with regards to their daily activities. These logs of information posses valuable information for the data analytics who process it to find hidden pattern and unique behavior. Among the many algorithms k-means clustering is one of the very popular and widely used algorithm in the field of data mining and machine learning. k-means provides natural segments of dataset provided for clustering. It uses proximity to assign data points to a specific cluster, here the criteria of allocation is the minimum distance from the cluster center. Unfortunately, the rate of data growth has not been met by the speed of the algorithms. A number of hardware based solutions have been proposed to increase the processing power of different algorithms. In this paper, we present a novel algorithm for k-mean clustering which exploits the data redundancy occurring in the dataset. The proposed algorithm performs computations for the available unique items in the dataset and uses its frequency to finalize the results. Furthermore, FPGA based hardware architecture for the proposed algorithm is also presented in the paper. The performance of the proposed algorithm and its hardware implementation is evaluated using execution time, speedup and throughput. The proposed architecture provides speedup of 23 times and 2600 times against sequential hardware architecture and software implementation with a very small area requirement.

In today’s scenario, there is quick evolution in each field which contains majority and distinctive sorts of information. In order to differentiate sample data from the other, the amalgamation of data mining techniques with other useful algorithms is done. Android development is one of the major arena where there is tremendous need to execute these calculations. Combining frequent pattern calculation with clustering is extremely efficacious for android. In this paper the work is done in two levels, initial stage concentrates on generation of clusters and final stage deals with finding the frequent patterns.

Data stream clustering is an active area of research in big data. It refers to clustering constantly arriving new data records and updating existing cluster patterns and outliers in light of the newly arriving data. Density-based algorithms for solving this problem have the promise for finding arbitrary shape clusters and detecting anomalies without prior knowledge of the number of clusters. In this paper, a new incremental algorithm known as Enhanced Density-based Data Stream (EDDS) is developed to overcome limitations with the existing solutions. The algorithm detects clusters and outliers in an incoming data chunk, merges new clusters from the chunk with the existing clusters, and filters out new outliers for the next round. It modified the traditional DBSCAN algorithm to summarise each cluster in terms of a set of surface-core points. The algorithm applies the density-reachable concept of DBSCAN as its merging strategy and prunes the internal core points using a heuristic solution. The algorithm also removes the aged core points and outliers depending on a fading function. The paper investigates three versions of the algorithm for three possible representations of clusters where either all core points are maintained (EDDS-I), only core points of the new clusters from the incoming chunk are kept (EDDS-II), or only the surface-core points of the cluster shapes are kept (EDDS-III) to examine the balance between the efficiency gain for the algorithm and the amount of overhead time committed for pruning internal core points. The algorithm was evaluated on selected datasets using various quality measures. The experimental results indicate improvements in terms of clustering correctness with a comparable time complexity over the existing solutions for solving the same kind of problems.

In this paper, we proposed a DBSCAN-based clustering algorithm called NNDD-DBSCAN with the main focus of handling multi-density datasets and reducing parameter sensitivity. The NNDD-DBSCAN used a new distance measuring method called nearest neighbor density distance (NNDD) which makes the new algorithm can clustering properly in multi-density datasets. By analyzing the relationship between the threshold of nearest neighbor density distance and the threshold of nearest neighborcollection, we give a heuristic method to find the appropriate nearest neighbor density distance threshold and reducing parameter sensitivity. Experimental results show that the NNDD-DBSCAN has a good robustadaptation and can get the ideal clustering result both in single density datasets and multi-density datasets.

DBSCAN, a density-based clustering method for multi-dimensional points, was proposed in 1996. Since then, it has received extensive applications, while its computational hardness is still unsolved to this date. The original KDD’96 paper claimed an algorithm of O(n log n) “average run time complexity” (where n is the number of data points) without a rigorous proof. In 2013, a genuine O(n log n)- time algorithm was found in 2D space under the Euclidean distance. The hardness of dimensionality d ≥ 3 has remained open ever since.This thesis considers the problem of computing DBSCAN clusters from scratch (assuming no existing indexes) under the Euclidean distance. We prove that, for d ≥ 3, the problem requires Ω(n 4/3) time to solve, unless very significant breakthroughs—ones widely believed to be impossible—could be made in theoretical computer science. Motivated by this, we propose a relaxed version of the problem called ρ-approximate DBSCAN, which returns the same clusters as DBSCAN, unless the clusters are “unstable” (i.e., they change once the input parameters are slightly perturbed). The ρ- approximate problem can be settled in O(n) expected time regardless of the constant dimensionality d.The thesis also enhances the previous result on the exact DBSCAN problem in 2D space. We show that, if the n data points have been pre-sorted on each dimension (i.e., one sorted list per dimension), the problem can be settled in O(n) worst-case time. As a corollary, when all the coordinates are integers, the 2D DBSCAN problem can be solved in O(n log log n) time deterministically, improving the existing O(n log n) bound.Given the popular usage of density-based clustering approach in many applications demanding data updates, this thesis further investigates the algorithmic principles for dynamic clustering by DBSCAN. Surprisingly, we prove that the ρ-approximate version suffers from the very same hardness when the dataset is fully dynamic, namely, when both insertions and deletions are allowed. We also show that this issue goes away as soon as tiny further relaxation is applied, yet still ensuring the same quality of ρ-approximate DBSCAN. Our algorithms guarantee near-constant update processing, and outperform existing approaches by a factor over two orders of magnitude.The last part of the thesis targets the scenario that the dataset cannot fit in main memory. The core contribution of this part is to show that, for any d-dimensional grid graph with n vertices, we can always compute in O(sort(n)) I/Os—where sort(n) is the I/O complexity of sorting n elements—a multiway vertex separator that serves the same algorithmic purposes as the well-known separator of [Maheshwari and Zeh, SICOMP’08] for a planar graph. This finding leads to (i) an algorithm that performs L∞ density-based clustering (and hence, approximate Lp density-based clustering for any constant p > 0) with near-linear I/Os in any fixed dimensionality, and (ii) improved algorithms for several fundamental problems on 2D grid graphs: connected components (CC), single source shortest path (SSSP), and breadth-first search (BFS). In particular, the improvement on the CC problem owes also to disproving a common belief that 2D grid graphs were sparse under edge contractions.

The aim of this paper is to propose a method to cluster GPS data corresponding to driving destinations. A new DBSCAN-based algorithm is proposed to group stationary GPS traces, collected prior to end of trips, into destination clusters. While the original DBSCAN clustering algorithm uses a global threshold as a closeness measure in data space, we develop a method to set local thresholds values for data points; this is important because the GPS data proximity strongly depends on the density of the street grid around each point. Specifically, the spread of GPS coordinates in parking lots can vary substantially between narrow (personal parking lot) and wide (parking lot of a shopping mall) depending on the destinations. To characterize the parking lot diversities at each destination, we introduce the concept of using a local threshold value for each data point. The local threshold values are inferred from road graph density using a map database. Moreover, we propose a mutual reachability constraint to preserve the insensitivity of DBSCAN with respect to the ordering of the points. The performance of the proposed clustering algorithm has been evaluated extensively using trips of actual cars in Sweden, and some of the results are presented here.

We suggested the modification of DBSCAN clustering algorithm for vertically partitioned big data. This modification provides privacy of the information which is transmitted via telecommunication channels between nodes of big data storage. This modification is founded on organization of secure channel which is based on homomorfic and asymmetric encryption. The first one is used for hiding the information and the second one is used for creation the encryption channel. Suggested privacy preserving DBSCAN clustering algorithm provides data confidentiality at all steps of DBSCAN algorithm.

Dynamic clustering---how to efficiently maintain data clusters along with updates in the underlying dataset---is a difficult topic. This is especially true for density-based clustering, where objects are aggregated based on transitivity of proximity, under which deciding the cluster(s) of an object may require the inspection of numerous other objects. The phenomenon is unfortunate, given the popular usage of this clustering approach in many applications demanding data updates. Motivated by the above, we investigate the algorithmic principles for dynamic clustering by DBSCAN, a successful representative of density-based clustering, and ρ-approximate DBSCAN, proposed to bring down the computational hardness of the former on static data. Surprisingly, we prove that the ρ-approximate version suffers from the very same hardness when the dataset is fully dynamic, namely, when both insertions and deletions are allowed. We also show that this issue goes away as soon as tiny further relaxation is applied, yet still ensuring the same quality---known as the ``sandwich guarantee''---of ρ-approximate DBSCAN. Our algorithms guarantee near-constant update processing, and outperform existing approaches by a factor over two orders of magnitude.

In this paper, an adaptive hierarchical clustering method based on DBSCAN algorithm is proposed to get information better from Automatic Identification System, and to be aware of traffic situation on water scientifically. In order to deal with the uneven distribution of ship trajectories, the paper proposes a method of hierarchical clustering and a statistical method to determine parameters according to the data set itself. After experiments, it is proven that the method can identify ship trajectories by their similarity as clusters, and result conforms to the actual traffic flow, thus, the method can provide assistant decision-making in the field of waterway construction, maritime control and so on.

In this paper, an exact and proactive technique is created to distinguish Distributed Denial of Service (DDoS) attacks. This is achieved by using an entropy concept to measure abnormal traffic changes according to the phases of the attack. This traffic is then clustered by using a modified DBSCAN algorithm, and the centroids for the resulting clusters are then used as patterns for efficient distance-based classification to detect DDoS attacks. The experimental results showed that the classification based on DBSCAN centroids achieved accuracy of more than (98%). This system is characterized by processing and analyzing high-speed network traffic (by using entropy), discovering and accurately identifying types of DDoS attacks to reduce false alarms, and early detecting DDoS attacks in real time.