Scaling up the DBSCAN Algorithm for Clustering Large Spatial Databases Based on Sampling Technique

Clustering, in data mining, is a useful technique for discovering interesting data distributions and patterns in the underlying data, and has many application fields, such as statistical data analysis, pattern recognition, image processing, and etc. We combine sampling technique with DBSCAN algorithm to cluster large spatial databases, and two sampling based DBSCAN (SDBSCAN) algorithms are developed. One algorithm introduces sampling technique inside DBSCAN, and the other uses sampling procedure outside DBSCAN. Experimental results demonstrate that our algorithms are effective and efficient in clustering large scale spatial databases.

Using Greedy algorithm： DBSCAN revisited Ⅱ

The density-based clustering algorithm presented is different from the classical Density-Based Spatial Clustering of Applications with Noise (DBSCAN) (Ester et al., 1996), and has the following advantages: first, Greedy algorithm substitutes for R*-tree (Bechmann et al., 1990) in DBSCAN to index the clustering space so that the clustering time cost is decreased to great extent and I/O memory load is reduced as well; second, the merging condition to approach to arbitrary-shaped clusters is designed carefully so that a single threshold can distinguish correctly all clusters in a large spatial dataset though some density-skewed clusters live in it. Finally, authors investigate a robotic navigation and test two artificial datasets by the proposed algorithm to verify its effectiveness and efficiency.

An Innovative K-Anonymity Privacy-Preserving Algorithm to Improve Data Availability in the Context of Big Data

The development of technologies such as big data and blockchain has brought convenience to life,but at the same time,privacy and security issues are becoming more and more prominent.The K-anonymity algorithm is an effective and low computational complexity privacy-preserving algorithm that can safeguard users’privacy by anonymizing big data.However,the algorithm currently suffers from the problem of focusing only on improving user privacy while ignoring data availability.In addition,ignoring the impact of quasi-identified attributes on sensitive attributes causes the usability of the processed data on statistical analysis to be reduced.Based on this,we propose a new K-anonymity algorithm to solve the privacy security problem in the context of big data,while guaranteeing improved data usability.Specifically,we construct a new information loss function based on the information quantity theory.Considering that different quasi-identification attributes have different impacts on sensitive attributes,we set weights for each quasi-identification attribute when designing the information loss function.In addition,to reduce information loss,we improve K-anonymity in two ways.First,we make the loss of information smaller than in the original table while guaranteeing privacy based on common artificial intelligence algorithms,i.e.,greedy algorithm and 2-means clustering algorithm.In addition,we improve the 2-means clustering algorithm by designing a mean-center method to select the initial center of mass.Meanwhile,we design the K-anonymity algorithm of this scheme based on the constructed information loss function,the improved 2-means clustering algorithm,and the greedy algorithm,which reduces the information loss.Finally,we experimentally demonstrate the effectiveness of the algorithm in improving the effect of 2-means clustering and reducing information loss.

GRAPH SPARSIFICATION BY UNIVERSAL GREEDY ALGORITHMS

Graph sparsification is to approximate an arbitrary graph by a sparse graph and is useful in many applications,such as simplification of social networks,least squares problems,and numerical solution of symmetric positive definite linear systems.In this paper,inspired by the well-known sparse signal recovery algorithm called orthogonal matching pursuit(OMP),we introduce a deterministic,greedy edge selection algorithm,which is called the universal greedy approach(UGA)for the graph sparsification problem.For a general spectral sparsification problem,e.g.,the positive subset selection problem from a set of m vectors in R n,we propose a nonnegative UGA algorithm which needs O(mn^(2)+n^(3)/ϵ^(2))time to find a 1+ϵ/β/1-ϵ/β-spectral sparsifier with positive coefficients with sparsity at most[n/ϵ^(2)],where β is the ratio between the smallest length and largest length of the vectors.The convergence of the nonnegative UGA algorithm is established.For the graph sparsification problem,another UGA algorithm is proposed which can output a 1+O(ϵ)/1-O(ϵ)-spectral sparsifier with[n/ϵ^(2)]edges in O(m+n^(2)/ϵ^(2))time from a graph with m edges and n vertices under some mild assumptions.This is a linear time algorithm in terms of the number of edges that the community of graph sparsification is looking for.The best result in the literature to the knowledge of the authors is the existence of a deterministic algorithm which is almost linear,i.e.O(m^(1+o(1)))for some o(1)=O((log log(m))^(2/3)/log^(1/3)(m)).Finally,extensive experimental results,including applications to graph clustering and least squares regression,show the effectiveness of proposed approaches.

Identification of Convective and Stratiform Clouds Based on the Improved DBSCAN Clustering Algorithm

A convective and stratiform cloud classification method for weather radar is proposed based on the density-based spatial clustering of applications with noise(DBSCAN)algorithm.To identify convective and stratiform clouds in different developmental phases,two-dimensional(2D)and three-dimensional(3D)models are proposed by applying reflectivity factors at 0.5°and at 0.5°,1.5°,and 2.4°elevation angles,respectively.According to the thresholds of the algorithm,which include echo intensity,the echo top height of 35 dBZ(ET),density threshold,andεneighborhood,cloud clusters can be marked into four types:deep-convective cloud(DCC),shallow-convective cloud(SCC),hybrid convective-stratiform cloud(HCS),and stratiform cloud(SFC)types.Each cloud cluster type is further identified as a core area and boundary area,which can provide more abundant cloud structure information.The algorithm is verified using the volume scan data observed with new-generation S-band weather radars in Nanjing,Xuzhou,and Qingdao.The results show that cloud clusters can be intuitively identified as core and boundary points,which change in area continuously during the process of convective evolution,by the improved DBSCAN algorithm.Therefore,the occurrence and disappearance of convective weather can be estimated in advance by observing the changes of the classification.Because density thresholds are different and multiple elevations are utilized in the 3D model,the identified echo types and areas are dissimilar between the 2D and 3D models.The 3D model identifies larger convective and stratiform clouds than the 2D model.However,the developing convective clouds of small areas at lower heights cannot be identified with the 3D model because they are covered by thick stratiform clouds.In addition,the 3D model can avoid the influence of the melting layer and better suggest convective clouds in the developmental stage.

Approaches for Scaling DBSCAN Algorithm to Large Spatial Databases

The huge amount of information stored in databases owned by corporations (e.g., retail, financial, telecom) has spurred a tremendous interest in the area of knowledge discovery and data mining. Clustering, in data mining, is a useful technique for discovering interesting data distributions and patterns in the underlying data, and has many application fields, such as statistical data analysis, pattern recognition, image processing, and other business applications. Although researchers have been working on clustering algorithms for decades, and a lot of algorithms for clustering have been developed, there is still no efficient algorithm for clustering very large databases and high dimensional data. As an outstanding representative of clustering algorithms, DBSCAN algorithm shows good performance in spatial data clustering. However, for large spatial databases, DBSCAN requires large volume of memory support and could incur substantial I/O costs because it operates directly on the entire database. In this paper, several approaches are proposed to scale DBSCAN algorithm to large spatial databases. To begin with, a fast DBSCAN algorithm is developed, which considerably speeds up the original DBSCAN algorithm. Then a sampling based DBSCAN algorithm, a partitioning-based DBSCAN algorithm, and a parallel DBSCAN algorithm are introduced consecutively. Following that, based on the above-proposed algorithms, a synthetic algorithm is also given. Finally, some experimental results are given to demonstrate the effectiveness and efficiency of these algorithms.

Genetic-Based Keyword Matching DBSCAN in IoT for Discovering Adjacent Clusters

As location information of numerous Internet of Thing(IoT)devices can be recognized through IoT sensor technology,the need for technology to efficiently analyze spatial data is increasing.One of the famous algorithms for classifying dense data into one cluster is Density-Based Spatial Clustering of Applications with Noise(DBSCAN).Existing DBSCAN research focuses on efficiently finding clusters in numeric data or categorical data.In this paper,we propose the novel problem of discovering a set of adjacent clusters among the cluster results derived for each keyword in the keyword-based DBSCAN algorithm.The existing DBSCAN algorithm has a problem in that it is necessary to calculate the number of all cases in order to find adjacent clusters among clusters derived as a result of the algorithm.To solve this problem,we developed the Genetic algorithm-based Keyword Matching DBSCAN(GKM-DBSCAN)algorithm to which the genetic algorithm was applied to discover the set of adjacent clusters among the cluster results derived for each keyword.In order to improve the performance of GKM-DBSCAN,we improved the general genetic algorithm by performing a genetic operation in groups.We conducted extensive experiments on both real and synthetic datasets to show the effectiveness of GKM-DBSCAN than the brute-force method.The experimental results show that GKM-DBSCAN outperforms the brute-force method by up to 21 times.GKM-DBSCAN with the index number binarization(INB)is 1.8 times faster than GKM-DBSCAN with the cluster number binarization(CNB).

基于航迹数据的改进DBSCAN聚类算法研究

为研究模拟训练航迹数据聚类,针对基于密度的噪声应用空间聚类(DBSCAN)算法参数选取不精准、聚类准确度不高的问题,提出一种改进的DBSCAN聚类算法.首先,通过KNN算法计算邻域半径并得到用于DBSCAN聚类的初始化核心数据对象,实现粗聚类;其次,根据数据对象的特点,加入航向特征进行二次聚类,既解决了DBSCAN算法随机初始化核心点和参数选取难的问题,又加入能够反映数据方向的特征;最后,进行了仿真实验.实验结果表明,改进DBSCAN算法比传统DBSCAN算法具有更好的聚类效果.

基于离群点检测和自适应参数的三支DBSCAN算法

针对经典的DBSCAN算法存在难以确定全局最优参数和误判离群点的问题,该算法首先从选择最优参数角度出发,通过数据集的分布特征生成Eps和MinPts列表,将两个列表中的参数进行全组合操作,把不同的参数组合依次进行聚类,从而寻找准确率最高点对应的参数。最后从离群点角度出发,将三支决策思想与离群点检测LOF算法进行结合。该算法与多种聚类算法进行效果对比分析,结果表明该算法能够全自动化选择全局最优参数,并提高聚类算法的准确性。

A novel fast classification filtering algorithm for LiDAR point clouds based on small grid density clustering

Clustering filtering is usually a practical method for light detection and ranging(LiDAR)point clouds filtering according to their characteristic attributes.However,the amount of point cloud data is extremely large in practice,making it impossible to cluster point clouds data directly,and the filtering error is also too large.Moreover,many existing filtering algorithms have poor classification results in discontinuous terrain.This article proposes a new fast classification filtering algorithm based on density clustering,which can solve the problem of point clouds classification in discontinuous terrain.Based on the spatial density of LiDAR point clouds,also the features of the ground object point clouds and the terrain point clouds,the point clouds are clustered firstly by their elevations,and then the plane point clouds are selected.Thus the number of samples and feature dimensions of data are reduced.Using the DBSCAN clustering filtering method,the original point clouds are finally divided into noise point clouds,ground object point clouds,and terrain point clouds.The experiment uses 15 sets of data samples provided by the International Society for Photogrammetry and Remote Sensing(ISPRS),and the results of the proposed algorithm are compared with the other eight classical filtering algorithms.Quantitative and qualitative analysis shows that the proposed algorithm has good applicability in urban areas and rural areas,and is significantly better than other classic filtering algorithms in discontinuous terrain,with a total error of about 10%.The results show that the proposed method is feasible and can be used in different terrains.

融合改进DBSCAN聚类和多种进化策略的改进蝗虫优化算法

针对蝗虫优化算法复杂高维问题收敛精度不高、寻优能力不强、难以跳出局部最优的缺陷,提出一种融合改进DBSCAN聚类和多种进化策略的改进蝗虫优化算法(GOA)。首先,引入多核加权距离度量和动态并行运算策略,以提高改进DBSCAN高维数据聚类效率。其次,利用改进DBSCAN可以对任意形状数据集进行聚类的优势,对蝗虫种群进行聚类分析,并为蝗虫个体赋予核心点、边界点和孤立点等空间属性。最后,综合考虑种群空间特性和个体间进化程度差异性,设计多种蝗虫个体进化策略,以更好地提升算法全局寻优能力。典型复杂、高维测试函数以及经典TSP问题仿真结果表明:改进后的GOA在收敛精度上更具优势。

一种基于DBSCAN算法改进的稳健AdaBoost回归模型

传统的AdaBoost.R2算法在AdaBoost算法思想的基础上将回归问题转化为二分类问题,取得了较好的估计效果。但该算法对异常点敏感,在迭代过程中会将异常点的权重不断加大,导致模型的稳健性较差。提出一种改进的AdaBoost算法,称为AdaBoost.DBSCAN。首先,通过DBSCAN聚类算法对观测点进行分类;然后,分别针对正常点和异常点,采用不同的权重控制策略进行控制,保证异常点的权重在迭代过程中无法以指数速率增长,同时能较大程度地保存样本信息。模拟和实际应用结果表示,与传统的AdaBoost.R2、AdaBoost.RT算法以及AdaBoost.RS算法相比,该算法具有良好的稳健性,在含有不同比例异常点的数据集中都能够获得较好的表现。

Hybrid Clustering Algorithms with GRASP to Construct an Initial Solution for the MVPPDP

Mobile commerce(m-commerce)contributes to increasing the popularity of electronic commerce(e-commerce),allowing anybody to sell or buy goods using a mobile device or tablet anywhere and at any time.As demand for e-commerce increases tremendously,the pressure on delivery companies increases to organise their transportation plans to achieve profits and customer satisfaction.One important planning problem in this domain is the multi-vehicle profitable pickup and delivery problem(MVPPDP),where a selected set of pickup and delivery customers need to be served within certain allowed trip time.In this paper,we proposed hybrid clustering algorithms with the greedy randomised adaptive search procedure(GRASP)to construct an initial solution for the MVPPDP.Our approaches first cluster the search space in order to reduce its dimensionality,then use GRASP to build routes for each cluster.We compared our results with state-of-the-art construction heuristics that have been used to construct initial solutions to this problem.Experimental results show that our proposed algorithms contribute to achieving excellent performance in terms of both quality of solutions and processing time.

基于DBSCAN聚类算法的卫星数据分区异常检测

随着我国第一颗电磁监测卫星的发射,卫星探测的海量数据不断涌现,探究空间载荷数据变化特征已成为当前研究热点。为了对张衡一号卫星LAP载荷数据进行异常检测,该文将处理后的数据按地理纬度划分为南纬50°到南纬20°,南纬20°到北纬20°,北纬20°到北纬50°三个区域,依次采用DBSCAN密度聚类算法进行聚类异常检测。结果表明,该方法可用于对LAP数据的异常检测。DBSCAN密度聚类算法可用于检测卫星异常数据,为检测卫星探测数据异常、研究空间数据变化特征提供思路参考。

DBSCAN算法的研究与应用

本文主要对基于密度的聚类算法中的经典DBSCAN算法进行了研究,首先从算法理论层面对DBSCAN算法进行了阐述分析,然后利用DBSCAN算法进行仿真实验,最后对各地区的就业率进行了分析。

基于改进DBSCAN省级电力物资仓库聚类的配送车辆路径优化研究

鉴于电力物资仓库分布点过多且较为分散,其多起点路径配送优化问题比较复杂,文中提出了一种改进DBSCAN聚类算法来简化电力物资多仓库配送车辆路径的两阶段方法。首先,将区域所有仓库进行聚类划分,得到若干个仓库簇,由此将多起点路径配送优化问题转化为多个仓库簇的单起点路径配送优化问题。然后,使用改进C-W法对模型进行求解。最后,以浙江省电力物资仓库作为配送实例,验证了文中所提两阶段方法及算法的可用性和可行性。

面向大规模数据的DBSCAN加速算法综述

DBSCAN(density-based spatial clustering of applications with noise)是应用最广的密度聚类算法之一.然而,它时间复杂度过高(O(n^(2))),无法处理大规模数据.因而,对它进行加速成为一个研究热点,众多富有成效的工作不断涌现.从加速目标上看,这些工作大体上可分为减少冗余计算和并行化两大类;就具体加速手段而言,可分为6个主要类别:基于分布式、基于采样化、基于近似模糊、基于快速近邻、基于空间划分以及基于GPU加速技术.根据该分类,对现有工作进行了深入梳理与交叉比较,发现采用多重技术的融合加速算法优于单一加速技术;近似模糊化、并行化与分布式是当前最有效的手段;高维数据仍然难以应对.此外,对快速化DBSCAN算法在多个领域中的应用进行了跟踪报告.最后,对本领域未来的方向进行了展望.

Metaheuristic Based Clustering with Deep Learning Model for Big Data Classification

Recently,a massive quantity of data is being produced from a distinct number of sources and the size of the daily created on the Internet has crossed two Exabytes.At the same time,clustering is one of the efficient techniques for mining big data to extract the useful and hidden patterns that exist in it.Density-based clustering techniques have gained significant attention owing to the fact that it helps to effectively recognize complex patterns in spatial dataset.Big data clustering is a trivial process owing to the increasing quantity of data which can be solved by the use of Map Reduce tool.With this motivation,this paper presents an efficient Map Reduce based hybrid density based clustering and classification algorithm for big data analytics(MR-HDBCC).The proposed MR-HDBCC technique is executed on Map Reduce tool for handling the big data.In addition,the MR-HDBCC technique involves three distinct processes namely pre-processing,clustering,and classification.The proposed model utilizes the Density-Based Spatial Clustering of Applications with Noise(DBSCAN)techni-que which is capable of detecting random shapes and diverse clusters with noisy data.For improving the performance of the DBSCAN technique,a hybrid model using cockroach swarm optimization(CSO)algorithm is developed for the exploration of the search space and determine the optimal parameters for density based clustering.Finally,bidirectional gated recurrent neural network(BGRNN)is employed for the classification of big data.The experimental validation of the proposed MR-HDBCC technique takes place using the benchmark dataset and the simulation outcomes demonstrate the promising performance of the proposed model interms of different measures.

基于改进DBSCAN-RNN的电力负荷建模及可调特征提取

针对面向能源消纳的电力负荷实时调控需求,以电热水器为例建立调控模型,提出一种改进DBSCANRNN算法的电力负荷可调特征提取与可调潜力挖掘方法。以改进DBSCAN聚类结果作为RNN输入获得一种深度学习新策略,基于改进DBSCAN-RNN进行电器群设定温度与天气温度、电器负荷功率的建模,考虑用户电器使用习惯,输出输入量对电器实际功率的影响因子以及电器可调功率与真实功率对应的状态方程参数。某市电热水器群实际数据结果表明所提方法可正确有效地获取海量电热水器群聚合负荷模型及其可调功率。

基于DBSCAN聚类的退役动力电池深度配组方法

退役动力电池在梯次利用时,因单体一致性差异较大,常难以满足使用要求。综合考量退役动力电池动态特性和静态特性,提出一种改进的多参数DBSCAN聚类算法对退役动力电池进行深度配组。对比实验表明,与Kmeans++聚类的结果相比,采用该方法聚类后电池最大容量差减少了86.04%;循环充放电实验表明,采用该方法得到的电池组充电性能提高约3%~5%,其放电量更大,其容量衰减速率降低了64.96%。该方法可有效提高电池组内单体的一致性并延长电池组的使用寿命。