An Enhanced Density and Grid based Spatial Clustering Algorithm for Large Spatial Database

김호석,김경배,배해영,Gao, Song,Kim, Ho-Seok,Xia, Ying,Kim, Gyoung-Bae,Bae, Hae-Young 한국정보처리학회 2006 정보처리학회논문지D Vol.13 No.5

Spatial clustering, which groups similar objects based on their distance, connectivity, or their relative density in space, is an important component of spatial data mining. Density-based and grid-based clustering are two main clustering approaches. The former is famous for its capability of discovering clusters of various shapes and eliminating noises, while the latter is well known for its high speed. Clustering large data sets has always been a serious challenge for clustering algorithms, because huge data set would make the clustering process extremely costly. In this paper, we propose an enhanced Density-Grid based Clustering algorithm for Large spatial database by setting a default number of intervals and removing the outliers effectively with the help of a proper measurement to identify areas of high density in the input data space. We use a density threshold DT to recognize dense cells before neighbor dense cells are combined to form clusters. When proposed algorithm is performed on large dataset, a proper granularity of each dimension in data space and a density threshold for recognizing dense areas can improve the performance of this algorithm. We combine grid-based and density-based methods together to not only increase the efficiency but also find clusters with arbitrary shape. Synthetic datasets are used for experimental evaluation which shows that proposed method has high performance and accuracy in the experiments. 공간 데이터마이닝 분야에서 객체간의 거리, 연결성, 상대적인 밀도를 기반으로 비슷한 객체들을 하나의 그룹으로 묶는 공간 클러스터링은 중요한 컴포넌트이다. 공간 클러스터링 알고리즘은 밀도 기반 클러스터링과 격자 기반 클러스터링 알고리즘 등으로 나눌 수 있다. 밀도 기반 클러스터링 알고리즘은 다양한 모양과 크기의 클러스터를 구분할 수 있으며, 잡음을 제거할 수 있는 장점을 가지고 있는 반면에, 격자 기반 클러스터링 처리속도가 빠르다는 장점을 가지고 있다. 하지만, 대량의 공간 데이터 집합을 클러스터링 하는 것은 데이터 처리 비용이 급격하게 증가하기 때문에 클러스터링 처리 결과에 큰 영향을 준다. 본 논문은 대용량의 공간 데이터베이스에서 공간 객체간의 고밀도 영역을 식별하여 잡음을 제거하기 위한 수치데이터 값과 기본 격자간격 개수를 정의하는 확장된 밀도-격자 기반 클러스터링 알고리즘을 제안한다. 제안 알고리즘은 고밀도 영역 식별을 위하여 threashold(DT)를 정의하였으며, 격자 및 밀도 기반 기법의 장점을 이용하여 임의의 객체 클러스터링을 식별할 수 있는 성능을 향상시켰다. 성능평가에서 기존의 클러스터링 알고리즘과의 다양한 비교 평가 실험을 통하여, 제안 알고리즘이 빠르고 정확한 데이터 클러스터링 결과를 나타냄을 보인다.

Spatial regression and estimation of disease risks: A clustering‐based approach

Feng, Wenning,Lim, Chae Young,Maiti, Tapabrata,Zhang, Zhen Wiley Subscription Services, Inc., A Wiley Company 2016 Statistical analysis and data mining Vol.9 No.6

<P>Detection of clustering and estimation of incidence risks are important and useful in public health and epidemiological research. The popular spatial regression models for disease risks, such as conditional autoregressive (CAR) models, assume a known spatial dependence structure for the error distribution and a set of common regression parameters for the mean structure. While it is often difficult to justify the structural assumption on spatial dependence, the assumption on a common regression surface may not be practical for a large spatial domain. We conceptualize a study region as a union of spatially connected clusters where a cluster is composed of geographically adjacent regions. We propose a regression model with cluster‐wise varying regression parameters. Our model is able to capture a spatial clustering structure, while the corresponding cluster‐wise regression parameters are estimated given the estimated clustering configuration. The proposed model is flexible in terms of regional and global shrinking as well as the number of clusters, cluster memberships and cluster locations. We develop an algorithm based on the reversible jump Markov chain Monte Carlo (MCMC) method for model estimation. The numerical study shows effectiveness of the proposed methodology. The method is computationally efficient and thus amenable to <I>large</I> datasets. © 2016 Wiley Periodicals, Inc. Statistical Analysis and Data Mining: The ASA Data Science Journal, 2016</P>

마할라노비스 거리를 이용한 다변량 공간 클러스터 분석

이몽현 한국지도학회 2012 한국지도학회지 Vol.12 No.2

This paper introduces an approach for analyzing multivariate spatial cluster/outlier in local scale. Even though spatial cluster/outlier has various definitions, the fundamental of spatial cluster/outlier is based on spatial association. Existing methods for measuring local spatial association had a limitation of applying multiple numbers of variables. Univariate local spatial association measures such as local Moran’s Ii, local Geary’s Ci and Getis and Ord’s Gi * are widely used, and bivariate local spatial association measures are already developed; Cross Moran and Lee’s Li. However, the measures are not used for measuring spatial association among three or more variables. This is a critical limitation when spatial variation with the complex multi-dimensional approaches is explained and described. The measure in this paper, multivariate local spatial association measure, is based on Mahalanobis Distance (MD) and it enables distinguishing spatial similarities and differences among multiple numbers of data sets simultaneously. MD considers variables’ means, variances and co-variances and allows measuring the variables’distribution. It is the same concept as distance measuring with Euclidean Distance but improved. Significance of MD could be tested because it is following chi-square distribution when the variables are multi-normal. Local MD is applied to demographic variables, in- and out-migration in Seoul Metropolitan Area. The spatial variation of multivariables could be identified by chi-squared p-value map, and a local MD map is provided to show the detected spatial clusters or outliers at a given significance level. 본 연구는 로컬 단위에서의 다변량 공간적 클러스터와 아웃라이어에 대한 분석에 대하여 논한다. 공간적 클러스터나 아웃라이어는 그 접근 방법이나 쓰임에 따라 다양한 정의를 내릴 수 있으나, 공간적 연관성을 기반으로 한다는 점에서는 근본적인 공통점이 있다. 그러나 현존하는 공간 연관성 척도들은 투입할 수 있는 변수의 수가 한정적이기 때문에 다변량 상황에서 공간적 연관성을 측정할 수 있는 방법에 대한 연구가 필요하다. 다변량 local 공간 연관성 척도의 개발을 위해, 본 연구에서는 두 집단간 분리 정도에 대한 측정이 가능한 마할라노비스 거리를 이용하였다. 마할라노비스 거리는 변수의 평균, 분산 그리고 변수간 공분산을 고려하여 계산이 된다. 본 연구에서 고안된 로컬 마할라노비스 거리는 해당 지역의 변수 벡터와 주변지역 변수의 평균 값 벡터를 통해 계산이 되며, 이를 수도권 지역 동읍면 단위에서 인구 전입/전출의 변수에 대해 적용하였다. 해당 단위에서의 공간적 변동은카이제곱 p값 지도를 통해 확인할 수 있으며, 유의성 검정을 실시한 로컬 마할라노비스 거리 지도를 통해 인구 유출입 차원에서의 공간적 클러스터와 아웃라이어를 확인할 수 있다.

Multivariate Spatial Cluster Analysis Using Mahalanobis Distance

Monghyeon Lee 한국지도학회 2012 한국지도학회지 Vol.12 No.2

본 연구는 로컬 단위에서의 다변량 공간적 클러스터와 아웃라이어에 대한 분석에 대하여 논한다. 공간적 클러스터나 아웃라이어는 그 접근 방법이나 쓰임에 따라 다양한 정의를 내릴 수 있으나, 공간적 연관성을 기반으로 한다는 점에서는 근본적인 공통점이 있다. 그러나 현존하는 공간 연관성 척도들은 투입할 수 있는 변수의 수가 한정적이기 때문에 다변량 상황에서 공간적 연관성을 측정할 수 있는 방법에 대한 연구가 필요하다. 다변량 local 공간 연관성 척도의 개발을 위해, 본 연구에서는 두 집단간 분리 정도에 대한 측정이 가능한 마할라노비스 거리를 이용하였다. 마할라노비스 거리는 변수의 평균, 분산 그리고 변수간 공분산을 고려하여 계산이 된다. 본 연구에서 고안된 로컬 마할라노비스 거리는 해당 지역의 변수 벡터와 주변지역 변수의 평균 값 벡터를 통해 계산이 되며, 이를 수도권 지역 동읍면 단위에서 인구 전입/전출의 변수에 대해 적용하였다. 해당 단위에서의 공간적 변동은 카이제곱 p값 지도를 통해 확인할 수 있으며, 유의성 검정을 실시한 로컬 마할라노비스 거리 지도를 통해 인구 유출입 차원에서의 공간적 클러스터와 아웃라이어를 확인할 수 있다. This paper introduces an approach for analyzing multivariate spatial cluster/outlier in local scale. Even though spatial cluster/outlier has various definitions, the fundamental of spatial cluster/outlier is based on spatial association. Existing methods for measuring local spatial association had a limitation of applying multiple numbers of variables. Univariate local spatial association measures such as local Moran’s Ii, local Geary’s Ci and Getis and Ord’s Gi * are widely used, and bivariate local spatial association measures are already developed; Cross Moran and Lee’s Li. However, the measures are not used for measuring spatial association among three or more variables. This is a critical limitation when spatial variation with the complex multi-dimensional approaches is explained and described. The measure in this paper, multivariate local spatial association measure, is based on Mahalanobis Distance (MD) and it enables distinguishing spatial similarities and differences among multiple numbers of data sets simultaneously. MD considers variables’ means, variances and co-variances and allows measuring the variables’ distribution. It is the same concept as distance measuring with Euclidean Distance but improved. Significance of MD could be tested because it is following chi-square distribution when the variables are multi-normal. Local MD is applied to demographic variables, in- and out-migration in Seoul Metropolitan Area. The spatial variation of multivariables could be identified by chi-squared p-value map, and a local MD map is provided to show the detected spatial clusters or outliers at a given significance level.

Spark 기반 공간 분석에서 공간 분할의 성능 비교

양평우(Yang, Pyoung Woo),유기현(Yoo, Ki Hyun),남광우(Nam, Kwang Woo) 대한공간정보학회 2017 대한공간정보학회지 Vol.25 No.1

본 논문은 인 메모리 시스템인 Spark에 기반 한 공간 빅 데이터 분석 프로토타입을 구현하고, 이를 기반으로 공간 분할 알고리즘에 따른 성능을 비교하였다. 클러스터 컴퓨팅 환경에서 빅 데이터의 컴퓨팅 부하를 균형 분산하기 위해, 빅 데이터는 일정 크기의 순차적 블록 단위로 분할된다. 기존의 연구에서 하둡 기반의 공간 빅 데이터 시스템의 경우 일반 순차 분할 방법보다 공간에 따른 분할 방법이 효과적임이 제시되었다. 하둡 기반의 공간 빅 데이터 시스템들은 원 데이터를 그대로 공간 분할된 블록에 저장한다. 하지만 제안된 Spark 기반의 공간 분석 시스템에서는 검색 효율성을 위해 공간 데이터가 메모리 데이터 구조로 변환되어 공간 블록에 저장되는 차이점이 있다. 그러므로 이 논문은 인 메모리 공간 빅 데이터 프로토타입과 공간 분할 블록 저장 기법을 제시하였다, 또한, 기존의 공간 분할 알고리즘들을 제안된 프로토타입에서 성능 비교를 하여 인 메모리 환경인 Spark 기반 빅 데이터 시스템에서 적합한 공간 분할 전략을 제시하였다. 실험에서는 공간 분할 알고리즘에 대한 질의 수행 시간에 대하여 비교를 하였고, BSP 알고리즘이 가장 좋은 성능을 보여주는 것을 확인할 수 있었다. In this paper, we implement a spatial big data analysis prototype based on Spark which is an in-memory system and compares the performance by the spatial split algorithm on this basis. In cluster computing environments, big data is divided into blocks of a certain size order to balance the computing load of big data. Existing research showed that in the case of the Hadoop based spatial big data system, the split method by spatial is more effective than the general sequential split method. Hadoop based spatial data system stores raw data as it is in spatial-divided blocks. However, in the proposed Spark-based spatial analysis system, there is a difference that spatial data is converted into a memory data structure and stored in a spatial block for search efficiency. Therefore, in this paper, we propose an in-memory spatial big data prototype and a spatial split block storage method. Also, we compare the performance of existing spatial split algorithms in the proposed prototype. We presented an appropriate spatial split strategy with the Spark based big data system. In the experiment, we compared the query execution time of the spatial split algorithm, and confirmed that the BSP algorithm shows the best performance.

Data Analysis Technique for Massive Spatial Data Using Hadoop

Minwuk Jeon,Byoung-Woo Oh 보안공학연구지원센터 2016 International Journal of Database Theory and Appli Vol.9 No.8

The spatial data set has much useful information, but the amount of volume is massive and the type is complex. It makes hard to analyze the spatial data. There are software tools for general data. Hadoop is one of the tools to process the big data. Hadoop can be used to analyze the large amount of spatial data. This paper proposed a data analysis technique for massive spatial data using Hadoop. We extend the grid based clustering algorithm to use Hadoop. The grid based clustering algorithm makes clusters with cells. Each cell has a number that counts contained objects. Only the cells who had the sufficient population can be join in clusters. The other cells ignored as noise. This paper proposed to enhance performance using Hadoop. In order to evaluate the enhancement of performance, the execution time is measured and compared. As the result, the proposed algorithm is 1.8 times faster than the original grid based clustering algorithm.

공간객체의 영향력을 고려한 클러스터링 알고리즘의 설계와 구현

김병철 한국콘텐츠학회 2006 한국콘텐츠학회논문지 Vol.6 No.12

본 논문은 공간객체의 영향력을 고려한 클러스터링을 위한 알고리즘인 DBSCAN-SI를 제안한다.DBSCAN-SI는 기존의 DBSCAN과 DBSCAN-W를 확장한 것으로 공간클러스터링 시 비공간 속성들을 영향력으로 변환한다. DBSCAN-SI는 클러스터링에 사용되는 속성에 의한 영향력이 클수록 클러스터에 포함될 확률을 높여주어, 단지 공간적인 거리뿐만이 아니라 영향력의 크기를 반영하여 군집화를 수행하기 위한 알고리즘이다. 이 논문에서 제안한 클러스터링 기법은 주변에 있는 객체들이 특정 속성 중심으로 보았을 때, 영향력이 큰 객체임에도 불구하고 주변에 객체가 드물게 있으므로 인하여 클러스터에서 배제되게 되는 기존 알고리즘의 단점을 보완해 줄 수 있다. This paper proposes DBSCAN-SI that is an algorithm for clustering with influences of spatial objects. DBSCAN-SI that is extended from existing DBSCAN and DBSCAN-W converts from non-spatial properties to the influences of spatial objects during the spatial clustering.It increases probability of inclusion to the cluster according to the higher the influences that is affected by the properties used in clustering and executes the clustering not only respect the spatial distances, but also volume of influences.For the perspective of specific property-centered, the clustering technique proposed in this paper can makeup the disadvantage of existing algorithms that exclude the objects in spite of high influences from cluster by means of being scarcely close objects around the cluster.

Labeling Big Spatial Data: A Case Study of New York Taxi Limousine Dataset

AlBatati, Fawaz,Alarabi, Louai International Journal of Computer ScienceNetwork S 2021 International journal of computer science and netw Vol.21 No.6

Clustering Unlabeled Spatial-datasets to convert them to Labeled Spatial-datasets is a challenging task specially for geographical information systems. In this research study we investigated the NYC Taxi Limousine Commission dataset and discover that all of the spatial-temporal trajectory are unlabeled Spatial-datasets, which is in this case it is not suitable for any data mining tasks, such as classification and regression. Therefore, it is necessary to convert unlabeled Spatial-datasets into labeled Spatial-datasets. In this research study we are going to use the Clustering Technique to do this task for all the Trajectory datasets. A key difficulty for applying machine learning classification algorithms for many applications is that they require a lot of labeled datasets. Labeling a Big-data in many cases is a costly process. In this paper, we show the effectiveness of utilizing a Clustering Technique for labeling spatial data that leads to a high-accuracy classifier.

수도권 환경계획을 위한 초미세먼지 농도의 공간 군집특성과 고농도지역 분석

임철희,박득희 한국환경복원기술학회 2022 한국환경복원기술학회지 Vol.25 No.1

Social interest in the fine particulate matter has increased significantly since the 2010s, and various efforts have been made to reduce it through environmental plans and policies. To support such environmental planning, in this study, spatial cluster characteristics of fine particulate matter (PM2.5) concentrations were analyzed in the metropolitan area to identify high-risk areas spatially, and the correlation with local environmental characteristics was also confirmed. The PM2.5 concentration for the recent 5 years (2016-2020) was targeted, and representative spatial statistical methods Getis–Ord Gi* and Local Moran’s I were applied. As a result of the analysis, the cluster form was different in Getis–Ord Gi* and Local Moran’s I, but they show high similarity in direction, therefore complementary results could be obtained. In the high concentration period, the hotspot concentration of the Getis–Ord Gi* method increased, but in Local Moran's I, the HH region, the high concentration cluster, showed a decreasing trend. Hotspots of the Getis–Ord Gi* technique were prominent in the Pyeongtaek-Hwaseong and Yeoju-Icheon regions, and the HH cluster of Local Moran’s I was located in the southwest, and the LL cluster was located in the northeast. As in the case of the metropolitan area, in the results of Seoul, there was a phenomenon of division between the northeast and southwest regions. The PM2.5 concentration showed a high correlation with the elevation, vegetation greenness and the industrial area ratio. During the high concentration period, the relation with vegetation greenness increased, and the elevation and industrial area ratio increased in the case of the annual average. This suggests that the function of vegetation can be maximized at a high concentration period, and the influence of topography and industrial areas is large on average. This characteristic was also confirmed in the basic statistics for each major cluster. The spatial clustering characteristics of PM2.5 can be considered in the national land and environmental plan at the metropolitan level. In particular, it will be effective to utilize the clustering characteristics based on the annual average concentration, which contributes to domestic emissions.

공간상관성을 고려한 회귀계수의 베이지안 군집모형을 이용한 국내 당뇨병 유병률 자료 분석

홍소진(Sojin Hong),강다연(Dayun Kang),최정순(Jungsoon Choi) 한국데이터정보과학회 2018 한국데이터정보과학회지 Vol.29 No.3

공간자료를 이용한 회귀모형에서는 공간적 상관성을 가지는 임의성분 (random component)을 추가하여 공간적 상관구조를 설명하며 회귀계수는 주어진 공간영역 (spatial domain) 내에서 고정되어 있다는 가정을 일반적으로 한다. 이는 비록 종속변수의 공간적 상관성은 설명이 되지만, 종속변수에 대한 설명변수의 영향력이 지역마다 일정하다는 의미로 해석할 수 있다. 하지만, 공간자료의 특성상 회귀계수 자체가 공간상관성을 가질 수도 있고, 더불어 소지역마다 서로 다른 값을 가질 수도 있다. 최근, Lawson 등 (2014)은 이러한 회귀계수에 대해 공간상관성을 고려한 이산 군집모형을 제안하고 암생존 자료에 적용하였다. 이때, 복잡한 공간 상관구조를 고려하기 위하여 베이지안 계층적 모형이 사용되었다. 본 연구에서는 2014년 국내 252개 시군구별 당뇨병 유병률 자료에 대하여 처음으로 공간상관성을 고려한 모형을 제시하였으며, 나아가 회귀계수에 대한 공간상관성을 고려한 이산 군집화 모형을 적합하였다. 공간상관성을 고려하지 않은 모형을 비교모형으로 적합하여 제시한 모형의 성능을 비교분석 하였다. In spatial regression modeling, it is commonly assumed that spatial random components are considered to explain the spatial dependency structures and regression coefficient is constant over the entire spatial domain. However, the regression coefficient may have spatial dependency structures and be different depending on the sub-regions. Recently, Lawson et al. (2014) proposed Bayesian discrete clustering methods of spatially dependent regression coefficients and applied them to cancer survival dataset. Bayesian hierarchical approach was utilized to explain the complicated spatial dependent structures. In this paper, we first analyze the diabetes prevalence data for the entire 252 administrative districts of South Korea in 2014 year using spatially-dependent regression coefficient clustering models. We evaluate the performance of the proposed spatial models with the non-spatial model.