Improvement of Thinking Theme Discovery Algorithm on Density-Based Clustering

Xuedong Gao,Lei Zou,Zengju Li 보안공학연구지원센터 2015 International Journal of Database Theory and Appli Vol.8 No.1

In traditional data mining process, the definition of mining objects and analysis tasks are all decided artificially based on the analysts’ knowledge and experience. To achieve intelligent data analysis, a method called thinking theme discovery technology is proposed to imitate humans’ thinking models. Since traditional thinking theme discovery algorithm is based on hierarchical clustering, the efficiency of which is far from acceptable with the increasing of data amounts. This paper improves the efficiency of the algorithm on density-based clustering method. With five complex network datasets and one commercial theme dataset, the experimental results show that both the effectiveness and efficiency of the algorithm are improved.

Fast density-based clustering through dataset partition using graphics processing units

Loh, W.K.,Yu, H. Elsevier science 2015 Information sciences Vol.308 No.-

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.

겨울철 일 단위 노면온도 패턴에 대한 군집분석

황영은,전상아,이민아,윤상후 한국자료분석학회 2022 Journal of the Korean Data Analysis Society Vol.24 No.2

The temperature of the road surface is important for road safety during the winter season. Slip vehicle accidents could occur when the road surface temperature drops below zero. It is known that the road surface temperature is on average 3~5℃ lower than the atmospheric temperature, but the actual observation data differs depending on the weather conditions. Therefore, the daily pattern of the difference between the atmospheric temperature and the road surface temperature is to be clustered. The research data is road meteorological information collected from stationary observation equipment in Jeollabuk-do from November 2017 to December 2020. The daily road surface temperature patterns were clustered after quality control through the climate range test, time variability test, and Kalman filter state model. Gaussian mixed clustering analysis, density-based clustering, and functional cluster analysis were considered. Gaussian mixed clustering analysis was explained well, as a result of evaluating the relationship between the clusters and daily weather information using a decision tree with 5-fold cross-validation. 도로 표면의 온도는 겨울철 도로안전을 위해 중요한 정보이다. 노면온도가 영하로 내려가면 결빙, 적설, 해빙 등에 따른 미끄럼 사고가 발생하기 때문이다. 일반적으로 노면온도는 대기온도에 비하여 평균 3~5℃ 낮다고 알려졌으나 실 관측자료는 기상 상황에 따른 차이가 있다. 따라서 노면온도와 대기온도 간 차이의 패턴을 일 단위로 군집화하고자 한다. 연구자료는 2017년 11월 5일부터 2020년 12월 31일까지 전라북도 지역의 고정식 관측장비로부터 수집된 도로 기상정보이다. 수집한 자료는 관측 시간 단위가 동일하지 않아 기후 범위 검사, 시간 변동성 검사, 칼만 필터 상태모형을 통해 품질관리 후 일 단위 노면온도 패턴을 군집화하였다. 일 단위 노면온도와 대기온도 간 차이는 3개의 주성분으로 축약하여 노면온도와 대기온도 간 패턴을 파악하기 위한 군집분석을 시행하였다. 군집분석 방법으로 가우시안 혼합 군집분석, 밀도기반 군집분석, 그리고 함수적 군집분석이 고려되었다. 군집분석 결과와 일 단위 기상정보 간 관계를 의사결정나무와 5겹 교차검증으로 평가한 결과 가우시안 혼합 군집분석으로부터 생성된 군집이 일 단위 기상정보로 가장 잘 설명되었다.

Density-based Outlier Detection in Multi-dimensional Datasets

Xite Wang,Zhixin Cao,Rongjuan Zhan,Mei Bai,Qian Ma,Guanyu Li 한국인터넷정보학회 2022 KSII Transactions on Internet and Information Syst Vol.16 No.12

Density-based outlier detection is one of the hot issues in data mining. A point is determined as outlier on basis of the density of points near them. The existing density-based detection algorithms have high time complexity, in order to reduce the time complexity, a new outlier detection algorithm DODMD (Density-based Outlier Detection in Multidimensional Datasets) is proposed. Firstly, on the basis of ZH-tree, the concept of micro-cluster is introduced. Each leaf node is regarded as a micro-cluster, and the micro-cluster is calculated to achieve the purpose of batch filtering. In order to obtain n sets of approximate outliers quickly, a greedy method is used to calculate the boundary of LOF and mark the minimum value as LOF i . Secondly, the outliers can filtered out by LOF i , the real outliers are calculated, and then the result set is updated to make the boundary closer. Finally, the accuracy and efficiency of DODMD algorithm are verified on real dataset and synthetic dataset respectively.

오표지된 진단 데이터를 위한 지도 군집화 기술 기반 진단 성능법 향상

김현재,오현석,윤병동(Byeng D. Youn) 대한기계학회 2016 대한기계학회 춘추학술대회 Vol.2016 No.12

This study proposes an approach to increasing performance of fault diagnosis by recovering lost fault log that exists in dataset. The main technique of the work is supervised clustering to find potential fault log. Supervised DBSCAN (Density based spatial clustering of application with noise) is newly proposed is a combination of density-based approach and supervised clustering. The supervised DBSCAN finds potential fault log from normal log overcoming few clustering-related problems. Among the potential fault log, determine helpful samples to enhance diagnosis accuracy utilizing genetic algorithm (GA). As a case study, a reliability dataset of rotor system with journal bearing is used. The novelty of this proposed method is a presentation of usefulness lies in corrupted dataset with lost fault log in the manner of recovering fault log. using the methodology. From the case studies, we could conclude that the methodology could differentiate the faulty condition from the normal one.

Density-based geodesic distance for identifying the noisy and nonlinear clusters

Yu, J.,Kim, S.B. Elsevier science 2016 Information sciences Vol.360 No.-

<P>Clustering analysis can facilitate the extraction of implicit patterns in a dataset and elicit its natural groupings without requiring prior classification information. For superior clustering analysis results, a number of distance measures have been proposed. Recently, geodesic distance has been widely applied to clustering algorithms for nonlinear groupings. However, geodesic distance is sensitive to noise and hence, geodesic distance-based clustering may fail to discover nonlinear clusters in the region of the noise. In this study, we propose a density-based geodesic distance that can identify clusters in nonlinear and noisy situations. Experiments on various simulation and benchmark datasets are conducted to examine the properties of the proposed geodesic distance and to compare its performance with that of existing distance measures. The experimental results confirm that a clustering algorithm with the proposed distance measure demonstrated superior performance compared to the competitors; this was especially true when the cluster structures in the data were inherently noisy and nonlinearly patterned. (C) 2016 Elsevier Inc. All rights reserved.</P>

Approximate Clustering on Data Streams Using Discrete Cosine Transform

Yu, Feng,Oyana, Damalie,Hou, Wen-Chi,Wainer, Michael Korea Information Processing Society 2010 Journal of information processing systems Vol.6 No.1

In this study, a clustering algorithm that uses DCT transformed data is presented. The algorithm is a grid density-based clustering algorithm that can identify clusters of arbitrary shape. Streaming data are transformed and reconstructed as needed for clustering. Experimental results show that DCT is able to approximate a data distribution efficiently using only a small number of coefficients and preserve the clusters well. The grid based clustering algorithm works well with DCT transformed data, demonstrating the viability of DCT for data stream clustering applications.

CCTV 기반 화염의 특성과 밀도 기반 공간 클러스터링을 이용한 화재 감지 방법

주영훈,최준선 대한전기학회 2022 전기학회논문지 Vol.71 No.4

In this study, we propose fire detection method using CCTV-based flame features and density-based spatial clustering with noise (DBSCAN). To do this, first, the 1st candidate region using the color of the flame image is extracted and the 2nd candidate region using the high-frequency region and background removal is extracted. Next, the extracted 1st candidate region and 2nd candidate region are merged, and the clustering region is extracted using DBSCAN. And then, the method for judging flame and rhinitis through the number of blocks passing through the movement trajectory of the central point of the clustering region extracted using DBSCAN is proposed. Finally, the applicability of the method proposed in this paper is reviewed through experiments in indoor and outdoor environments.

계층 발생 프레임워크를 이용한 군집 계층 시각화

신동화(DongHwa Shin),이세희(Sehi L’Yi),서진욱(Jinwook Seo) 한국정보과학회 2015 정보과학회 컴퓨팅의 실제 논문지 Vol.21 No.6

군집화 알고리즘은 그 종류에 따라 만들어낼 수 있는 군집의 종류와 보여줄 수 있는 정보의 수준이 차이가 난다. 밀도기반 군집화 알고리즘은 데이터 분포 상의 임의의 모양을 가진 군집을 잘 잡아내지만 보여줄 수 있는 계층정보가 매우 적거나 없는 수준이고, 반면 계층적 군집화 알고리즘은 자세한 계층 정보를 보여주지만 구 모양의 군집 외에는 잘 잡아내지 못한다. 이 논문에서는 이러한 두 군집화 방식의 대표적 알고리즘인 OPTICS와 응집 계층 군집화 알고리즘의 장점만을 취하는 계층 발생 프레임워크를 제시하고 이와 더불어 효과적 데이터 분석을 위한 여러 시각화, 상호작용 기법을 지원하는 시각적 분석 애플리케이션을 제공한다. There are many types of clustering algorithms such as centroid, hierarchical, or density-based methods. Each algorithm has unique data grouping principles, which creates different varieties of clusters. Ordering Points To Identify the Clustering Structure (OPTICS) is a well-known density-based algorithm to analyze arbitrary shaped and varying density clusters, but the obtained clusters only correlate loosely. Hierarchical agglomerative clustering (HAC) reveals a hierarchical structure of clusters, but is unable to clearly find non-convex shaped clusters. In this paper, we provide a novel hierarchy generation framework and application which can aid users by combining the advantages of the two clustering methods.

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

김병철 한국콘텐츠학회 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.