클러스터링을 이용한 데이터베이스 다중 검색 시스템 설계

홍창표 韓南大學校 大學院 2001 국내석사

최근 인터넷을 통해서 접근 가능한 정보의 양적인 팽창이 폭발적으로 늘어나고 있다. 이러한 상황에서 검색은 사용자에게 최소의 시간으로 최대의 양질의 정보를 제공할 수 있는 시스템이 필요로 되고 있다. 이러한 문제점을 해결하기 위해서 본 논문에서는 사용자에게 보다 편리하고 보다 양질의 정보를 최소의 시간 내에 제공하기 위해서 대용량의 문서를 분류/요약/클러스터링/필터링 등의 기술을 통하여 사용자가 원하는 형태로 가공/분류하여 실시간에 제공하는 시스템을 설계하였다. 본 논문에서 질의어에 대한 클러스터링과 색인 기법을 이용하여 문서 이외에 데이터베이스에 저장되어 있는 정보를 정확하고 다양하게 결과를 보여줄 수 있는 시스템을 설계하였다. 설계된 시스템은 먼저 대용량의 문서분류를 위하여 수동으로 단어사전을 구축하고 각 클러스터링 과정을 거치면서 검색된 문서에 대해서 자동 클러스터링을 수행하여 유산관련 단어사전을 확장시키는 방향을 제시되었고 각 문서에 대한 유사도를 측정하여 검색한 문서에 대해서 사용자가 검색한 질의어에 얼마나 부합하는지를 사용자에게 보여주고 있다. 사용자가 검색 시스템에 대해 질의어를 입력하면 시스템에서는 질의어를 분석하여 질의어의 유사관련 단어들을 추출하고 이미 이전에 질의된 질의어라면 색인표를 찾아 그에 해당하는 결과 값을 가져오면 된다. 그렇지 않은 경우 클러스터링은 데이터베이스에 대해서 해당 질의어에 대한 검색을 시도하여 결과값을 반환하여 가져온다. 가져온 결과값에 값을 구성하는 색인어들로 문서에 대한 특성벡터를 추출하고 모든 문서쌍에 대하여 특성벡터를 이용하여 유사도를 측정한 후 가장 유사도가 높은 문서쌍을 클러스터링을 행하고 클러스터링된 결과를 검색결과 사이의 유사도 계산에 반영한다. 사전에 등록되어 있는 색인과 검색 질의어에 클러스터링을 이용하여 단어간의 유사도를 측정한 후 그 유사도 값을 사용자에게 보여준다. 자동분류 모듈은 결과값의 내용과 특성을 분석하여 유사한 특성을 갖는 결과값들을 같은 클래스로 자동 분류하는 모듈로써 정의된 분류체계에 대하여 각 결과값들에 대한 분류코드 값을 자동 할당하는 작업을 수행한다. 각 분류에 대하여 해당하는 결과값 집합을 구축하고 결과값 집합으로부터 각 분류를 대표하는 용어정보를 추출한 후 추출된 용어 정보와 각 결과값 특성벡터(색인어)를 비교하여 가장 부합되는 분류에 할당하고 결과값 분류된 결과를 이용하여 분류를 대표하는 용어정보를 조정(feedback)하게 된다. 본 논문에서 설계한 시스템은 질의어에 대한 유사 단어 사전을 구축하고 유사 단어 사전에 의미적으로 결부되는 단어들에 대해서는 질의를 행함으로써 보다 많은 결과를 찾을 수 있으며 사용자로 하여금 보다 정확하면서도 원하는 정보를 얻을 수 있을 것이다. 또한 질의한 질의어에 대해서는 문서분류를 통하여 질의에 대한 결과 값을 색인화하여 이후 다시 같을 질의어에 대해서는 데이터베이스 또는 문서를 검색하는 것이 아니라 색인된 정보를 가져오므로 보다 빠르게 검색을 수행하게된다.

점진적 프로젝션 기반의 고차원 데이터 클러스터링 기법

李慧明 명지대학교 2001 국내박사

데이터 마이닝을 위한 방법론 중에서 클러스터링은 데이터 집합에 대해 유사한 특징을 가진 객체들을 집단화하는데 사용되는 매우 유용한 분석 방법이다. 따라서 데이터베이스의 많은 응용분야에서 대용량 고차원 데이터의 클러스터링을 요구하고 있으며, 클러스터링 알고리즘에 대한 연구가 활발히 진행되고 있다. 그러나 대부분의 클러스터링 알고리즘들은 고차원 공간에서 데이터가 갖는 고유의 희소성에 의해 성능이 급격히 저하되는 경향이 있다. 더욱이, 고차원 데이터는 상당한 양의 잡음 데이터를 포함하고 있으므로 알고리즘의 추가적인 효과성 문제를 야기한다. 그러므로 고차원 데이터의 구조와 특성을 지원하는 적합한 클러스터링 기법이 요구된다. 본 논문에서는 고차원 공간에서 클러스터링의 효율성 및 효과성 문제를 극복하기 위한 새로운 클러스터링 알고리즘 CLIP (CLustering based on Incremental Projection)을 제안한다. CLIP은 선형변환 프로젝션을 이용하며, 클러스터 형성에 밀접하게 연관된 부분공간에서 클러스터를 탐사한다. CLIP 알고리즘은 클러스터링에 관한 전반부와 클러스터 정제에 관한 후반부로 구성된다. CLIP 알고리즘의 전반부는 각 1차원적 부분 공간에서의 클러스터링에 기본을 두고 있으나, 점진적인 프로젝션을 이용하여 고차원 클러스터를 탐사한다. 이와 같이 CLIP은 1차원 클러스터들의 곱집합을 찾아 고차원 클러스터로 정의하며, 연산을 획기적으로 줄인다. 그러나 이 집합은 클러스터를 포함할 뿐 아니라 잡음도 포함할 수 있다. CLIP 알고리즘의 후반부는 전반부에서 찾은 곱집합에 반복적인 2차원 프로젝션을 적용하여 클러스터의 고차원적 잡음을 제거하고, 클러스터 형태를 구체화한다. 또한 밀도 임계값을 변화시키면서 사용자가 원하는 수준의 클러스터를 조사한다. 제안하는 CLIP 알고리즘을 평가하기 위해 이론적 증명 및 다양한 실험을 통하여 성능을 입증하였다. 알고리즘의 실험 결과는, 입력 데이터의 차원이나 데이터 개수의 증가에 따라 선형적임을 보이며 기존의 부분차원 알고리즘보다 약 10배에서 100배 정도 빠른 처리 속도를 보였다. 또한 전체차원 기반의 알고리즘으로는 식별하지 못했던 고차원 공간의 클러스터를 모두 조사할 수 있다. 클러스터 정제 단계에서는 사용자가 원하는 수준의 클러스터 및 복잡한 구조의 클러스터가 조사되었다. Clustering is one of the most useful methods in data mining by grouping objects with similar characteristics in a data set. In particular, high dimensional data clustering is strongly needed in many applications of database, and researches on clustering algorithms are in progress actively. However, most of clustering algorithms tend to degenerate rapidly by the nature of sparsity in high dimensional data. Because the high dimensional data also contain a significant amount of noise, it causes additional ineffectiveness of algorithms. So, we need a clustering method that handles the structure and characteristics of high dimensional data. In this thesis, we propose a new clustering algorithm called CLIP(CLustering based on Incremental Projection) that overcomes ineffectiveness and inefficiency of the existing clustering algorithms on the high dimensional space. CLIP uses the linear transformation projection and it is the method of finding a closely correlated set of a cluster as a product of sets in the subspaces. CLIP algorithm has two parts; the first part is for clustering and the second one is for cluster refinement. The first part of CLIP algorithm is based on clustering on each one dimensional subspace but we use the incremental projection to recover high dimensional clusters. By changing density threshold, users can find clusters at the level of density wanted. By doing that, we find product sets of one dimensional clusters and it reduces the computational cost significantly at the same time. Those product sets contain all the high dimensional clusters, but they may contain noises. The second part of CLIP is to remove high dimensional noises by applying two dimensional projections iteratively on the already found product sets. It will also specify the shape of clusters. To evaluate the CLIP algorithm, we demonstrate its performance through a theoretical proof and a series of experiments. The results show that the computational cost depends linearly on the number of data and the dimensionality of data. Our algorithm performs 10-100 times faster than the existing subspace algorithm. Moreover, our algorithm can discover all the clusters on high dimensional space, some of which would not be identified with algorithms based on the full dimensional clustering. In the cluster refining phase, it can even identify clusters of complicated shapes.

시계열 빅데이터 분류 및 클러스터링 기법과 응용

오규협 경희대학교 대학원 2017 국내박사

디지털 기기의 발전으로 다양한 정보가 생성되고 있으며 매해 생성되는 데이터는 증가하고 있다. 다양한 종류로 생성되는 모든 데이터는 분석을 위해 수집 및 저장하고 이러한 데이터들을 ‘빅데이터’라고 한다. 빅데이터의 발전으로 시계열 데이터(Time-Series) 또한 다양하게 생성 및 수집되고 있다. 시계열이란 일정간격으로 배치된 데이터의 수열을 의미하며 일정간격으로 수집되는 데이터를 시계열 데이터라고 한다. 하지만 데이터 수집 기간에 늘어남에 따라 크기가 증가하고 데이터의 종류에 따라 특징이 다른 특성으로 인해 특징을 추출하기는 어렵다. 본 논문에서는 시계열 데이터를 분석하기 위해서 분류 및 클러스터링 기법과 지리적 클러스터링 기법을 제시하였다. 시계열 데이터의 분류를 위하여 CNN 기반 모형과 1-NN DTW 기반 모형을 제안하였고 제안된 모형을 서울시 대중교통 데이터와 공공데이터를 사용하여 검증하였다. 시계열 데이터의 클러스터링을 위하여 대칭형 쿨백 라이블러와 K-메도이드를 활용한 기법을 제시하였다. 제시된 기법을 서울시 대중교통 데이터를 사용하여 분석하였다. 마지막으로 이동거리와 이동량을 기반으로 한 지리적 클러스터링 기법을 제안하였고 서울시 대중교통 데이터로 분석하였다. With the development of digital devices, a variety of information is being generated and the amount of data generated each year is increasing. All data generated in various categories are collected and stored for analysis, and these data are called 'big data'. With the development of big data, time-series data are also variously generated and collected. Time series refers to a sequence of data arranged at regular intervals, and data collected at regular intervals is called time series data. However, as the data collection period increases then the size increases and it is difficult to extract the feature due to the different characteristics depending on the type of data. In this paper, classification and clustering techniques and geographic clustering techniques are presented to analyze time series data. In order to classify time series data, a CNN-based model and a 1-NN DTW-based model were proposed and the proposed model was verified using public transportation data and public data in Seoul. In order to clustering the time series data, a scheme using symmetric Kullback Libler and K-medoids was proposed. The proposed technique was analyzed using public transportation data of Seoul. Finally, we propose a geographic clustering method based on travel distance and travel distance and analyze it with Seoul public transport data.

선형모델을 이용한 측위데이터의 클러스터링기법 실증연구

남권모 경일대학교 대학원 2017 국내박사

본 연구에서는 복잡한 오차의 원인으로 인한 부정합성 때문에 개별적으로 정확도를 판단하기 어려운 측위데이터를 대상으로 정합성을 판단할 수 있는 효율적인 클러스터링 기법을 도출하는 것을 목적으로 하였다. 이와 관련하여 본 연구에서는 클러스터링 기법을 제안하였고 개발한 SW를 통해 실증하였다. 연구의 내용을 요약하면 다음과 같다. 첫째, 안정적인 군집 결과를 도출하기 위해서 군집에 앞서 이상점의 판별, 변수의 결정, 데이터 표준화 등과 같은 데이터 전처리 알고리즘이 필요하였다. 이상점 제거와 관련하여 이상치 판단 기준이 모호한 경우에는 점차적으로 수렴이 가능한 반복 구조를 이용하여 통계적 기각역 범위 기준으로 이상점 판별이 가능하였다. 둘째, 본 연구에서는 K-Means, GMM, LMC의 클러스터링 기법, 좌표변환 기능을 포함하는 클러스터링 SW 기법을 구현하였으며 이를 통해 LMC의 실효성을 검증하였다. 셋째, 복잡한 오차가 내포되어 있는 데이터를 대상으로 클러스터링 기법에 대한 효율성을 검토하였다. K-Means은 그리드 셀에 의해 초기값을 설정하는 방법이 임의 선정 방법보다 안정적이었으며 데이터 현황 파악에 이용될 수 있으나 데이터 경향이나 특성을 파악하는데 무리였다. 특히 복잡한 데이터에 대해 사전 정제 없이는 군집 구성에 실패하거나 왜곡현상이 나타났다. GMM(Gaussian mixture model) 기법의 경우에는 K-Means의 결과를 이용하여 초기 컴포넌트를 선정하는 방법이 비교적 안정적 있었다. K-Means보다 데이터의 특성과 경향을 파악하는 능력이 뛰어났다. 그러나 군집 외곽 경계에서 모호성이 나타났으며 이상점에 민감하여 사전 데이터 정제 없이는 그 결과를 신뢰할 수 없었다. 넷째, 선형모델에 의하여 클러스터링을 구성하는 LMC(Linear Model Cluster)모델을 새롭게 제안하였다. 이 방법은 불균질 데이터를 대상으로 자체적으로 노이즈 판별이 가능하였으며 데이터에 내포된 경향이나 특성에 따라 군집을 형성하였다. 다섯째, 지적도면 세계측지계 변환 실증 실험에서 불균질이 심화된 지역을 대상으로 LMC기법을 적용하여 정합도 기준에 부합하는 성과를 산출할 수 있었다. 본 연구를 통해 복잡한 오차가 내포된 데이터의 클러스터링에서는 LMC기법이 효율적이었다. 자료의 재해석이 필요한 분야에서 적용할 수 있을 것으로 판단되었다. 본 연구에서는 측위데이터를 대상으로 한정하였는데 향후 빅데이터의 자료 처리 분야로 확대하는 연구가 필요할 것으로 사료되었다.

실루엣 평가함수와 확률적 거리 비율을 적용한 효율적인 담금질 기법(ESA)을 이용한 데이터 클러스터링

백준영 강원대학교 대학원 2020 국내석사

Clustering is a problem belonging to NP-Hard as a method for finding meaningful data distribution and patterns by dividing a large group of data into several groups with similar properties by measuring similarity between individuals. Simulated Annealing (SA) is an algorithm for searching for the optimal solution in a large function with a complex search space. The quenching technique has an excellent search effect for the global optimal solution, but the search speed is slow due to its algorithm characteristics. The silhouette valid index can determine the appropriate number of clusters while minimizing the distance in the cluster and also considering the distance between the clusters, but has a disadvantage in that it takes a lot of computation time. The purpose of this paper is to propose an efficient SA data clustering method that uses the silhouette valid index to determine the appropriate number of clusters and generates several solutions that consider the distance ratio between data stochastically, using the best solution as the initial solution. For experimentation and verification, Ruspini data and Soybean, Iris, Wine, Glass, Thyroid, Breast Cancer, Vowel, Cloud, and CMC data in UCI dataset were used, and the existing SA algorithm and computation time were compared. 클러스터링은 용량이 큰 데이터 셋으로부터 개체들 간의 유사도 측정을 통해 유사한 속성을 가진 몇 개의 그룹으로 나눔으로써 유의미한 데이터 분포 및 패턴을 찾기 위한 방법으로 NP-Hard에 속하는 문제이다. 담금질 기법(SA, Simulated Annealing)은 해 탐색 공간이 복잡하고 큰 함수에서 최적해를 탐색하기 위한 알고리즘이다. 담금질 기법은 전역 최적해를 탐색 효과가 뛰어나지만, 그 알고리즘 특성상 탐색 속도가 느리다. 실루엣 평가 함수는 클러스터 내의 거리는 최소화함과 동시에, 클러스터 간의 거리 또한 고려하여 적절한 클러스터 수를 결정할 수 있지만, 계산 시간이 다소 많이 소요된다는 단점이 있다. 본 논문의 목적은 실루엣 평가 함수를 이용하여 적절한 클러스터 수를 결정하고 데이터 간의 거리 비율을 확률적으로 고려한 여러 해들을 생성하여 그중 가장 좋은 해를 초기 해로 사용하는 효율적인 SA 데이터 클러스터링 방법을 제안하는 것이다. 실험 및 검증을 위해 Ruspini 데이터와 UCI Dataset에 있는 Soybean, Iris, Wine, Glass, Thyroid, Breast Cancer, Vowel, Cloud, CMC 데이터를 사용하였고, 기존의 SA 알고리즘과 계산 시간을 중점으로 비교하였다.

이동체 데이터베이스를 위한 디클러스터링 정책의 설계 및 구현

홍은석 부산대학교 2004 국내석사

이동체 데이터베이스에서 이동체 궤적의 양은 엄청나게 많아서 기존의 단일 디스크 기반에서는 특정 영역의 질의에 대한 빠른 응답과 처리율의 향상을 볼 수 없다. 따라서 고성능 질의 처리를 위한 시스템의 성능 향상을 위해서는 병렬 처리 기법의 도입이 필요하다. 이런 병렬 처리 기법 중, 기존의 디클러스터링 방법에서는 시간이 지남에 따라 연속적으로 보고되는 이동체 특성을 고려하지 않고 있다. 그러므로 대용량 이동체 데이터에 대하여 고성능 질의 처리를 위한 새로운 디클러스터링 방법이 필요하다. 이 논문에서는 대용량 이동체 데이터베이스에 대한 고성능 질의 처리를 위한 새로운 디클러스터링 정책을 제시하였다. 이동체 데이터의 MBB(Minimum Bounding Box) 중 공간 좌표에 대한 근접성만을 고려하여 하나의 SD(SemiAllocation Disk)값을 설정하고 그 값과 시간 도메인을 다시 고려하여 근접성을 계산함으로써 디클러스터링을 한다. 또한 디스크 별 부하 균등화를 고려하여 보다 정확한 디클러스터링 효과를 가지도록 하였다. 이와 같이 이동체의 시공간 특성을 고려한 새로운 디클러스터링 정책으로 시스템의 성능을 향상 시킬 수 있다. 성능평가를 통해서 기존의 Round-Robin 방법보다는 5%, 10% 영역 질의 에서 평균 15% 정도의 성능향상을 보였으며 Spatial Proximity 방법보다는 평균 6%의 성능향상을 보였다. Because there are so many spatial-temporal data in Moving Object Databases, a single disk system can not gain the fast response time and total throughput. So it is needed to take a parallel processing system for the high effectiveness query process. In these existing parallel processing systems, it does not consider characters of moving object data. Moving object data have to be thought about continuous report to the Moving Object Databases. So it is necessary think about the new Declustering System for the high effectiveness processing system. This paper proposes the new Declustering Policies of Moving object data for high effectiveness query processing. At first, consider a spatial part of MBB(Minimum Bounding Box) then take a SD(SemiAllocation Disk) value. Second time, consider a SD value and time value which is node made at together as SDT-Proximity. And for more accuracy Declustering effect, consider a Load Balancing. Evaluation shows performance improvement of average 15% compare with Round-Robin method about 5% and 10% query area. And performance improvement of average 6% compare with Spatial Proximity method.

시공간 데이터를 위한 클러스터링 기법의 성능 비교

강나영 이화여자대학교 과학기술대학원 2003 국내석사

최근 데이터 양이 급증하면서 데이터 마이닝에 대한 연구가 활발하게 진행되고 있다. 특히 GPS 데이터, 감시 카메라의 궤적 데이터, 기상 데이터들과 같은 다양한 응용시스템으로부터 수집된 시공간 데이터를 분석하고자 하는 시공간 데이터 마이닝 연구에 대한 관심이 더욱더 높아지고 있다. 기존 연구들에서는 SOM, K-means, 응집 계층 알고리즘과 같은 일반적인 클러스터링 기법들을 적용하여 시공간 데이터 마이닝을 수행하고 있다. 하지만 이러한 알고리즘들이 실제적으로 시공간 데이터에 이러한 기법들을 적용하는데 있어서 어느 정도의 성능을 보장할 수 있는지 혹은 데이터의 시공간속성에 따라 적절한 마이닝 알고리즘을 선택하기 위한 기준이 무엇인지 등에 대한 연구는 미흡한 실정이다. 본 논문에서는 기존의 시공간 데이터 마이닝 연구에서 주로 사용되어 온 알고리즘인 SOM을 분석하여 SOM 기반 마이닝 모듈을 개발한다. 그리고 K-means 와 응집 계층 알고리즘과의 성능 비교를 통해 SOM 이 시공간 마이닝에 있어서 어느 정도의 성능을 보장하는지를 균질도, 분리도, 반면영상 너비, 정확도의 네 가지 기준에서 분석한다. 또한 시공간 데이터의 경우 입력 데이터의 속성에 따라 이러한 평가 기준 수치가 클러스터링 결과의 정확성 및 성능을 제대로 나타내지 못하는 경우가 발생할 수 있다는 점을 고려하여 시공간 데이터의 클러스터링 결과를 위한 특화된 가시화 모듈을 개발하고 이를 통해 결과 비교 및 분석을 수행한다. With the growth in the size of datasets, data mining has recently become an important research topic. Especially, interests about spatio-temporal data mining has been increased which is a method for analyzing massive spatio-temporal data collected from a wide variety of applications like GPS data, trajectory data of surveillance system and earth geographic data. In the former approaches, conventional clustering algorithms such as K-means, Agglomerative Hierarchical algorithm and SOM are commonly applied as spatio-temporal data mining techniques. However, researches on the performance of these approaches when they actually applied to spatio-temporal data mining and on what is the proper data mining algorithm for the input data sets considering the spatio-temporal properties, is sparse at present. In this thesis, we analyze SOM, which is the popular clustering algorism applied to clustering analysis in data mining area, and develop the spatio-temporal data mining module based on it. In addition, we analyze the clustering results of SOM and compare it with those of K-means and Agglomerative Hierarchical algorithm in the aspects of homogeneity, separation, separation, silhouette width and accuracy. We also develop specialized visualization module for more accurate interpretation of mining result. This is because, without considering the properties of spatio-temporal data, numerical criterions of performance evaluation may not show properly the accuracy and performance of clustering results.

버블업: 시간적 이벤트 데이터의 유사성 분석을 위한 시각화 시스템

GUO WEN JUN 아주대학교 일반대학원 2018 국내박사

시간적 이벤트 데이터(temporal event data)는 다양한 분야에서 점점 더 많은 관심을 받고 있다. 시간적 이벤트 데이터의 이벤트들이 발생한 시간에 따라 이벤트들의 패턴이나 유사성에 대한 비교 및 분석을 통해서 이벤트의 새로운 구성을 식별하고, 유저에게 향후 의사 결정을 할 때도 많은 도움을 줄 수 있다. 기존에 연구들이 시간의 흐름에 따라 변화하는 이벤트들에 집중적으로 연구를 이루어졌지만 최근에 반복을 인해 생긴 종단적인(longitudinal) 시간의 변화에 대한 연구도 많아지고 있다. 본 연구에서는 종단적인 시간성을 가진 시간적 이벤트 데이터에 비교 분석에 대한 최적화된 시각화 시스템을 제안하고자 한다. 또한 시스템의 활용 사례 연구와 사용성 평가를 통해 다음과 같은 효과를 검증하였다. 첫째, ‘BubbleUp’ 시스템의 시각화 알고리즘 설계와 프로토타입을 구현하고, 추가 인터랙션 기능과 사용자 인터페이스를 개발하였다. 둘째, 클러스터링을 통해 데이터의 잠재적인 패턴 도출이 가능하여 데이터에 대한 탐색이 보다 쉬워졌다. 셋째, 사용자가 타깃을 선택하면 시스템에서 유사한 결과와 유사하지 않는 결과에 대해 제시해 줄뿐만 아니라 사용자가 원하는 분포 범위를 자유롭게 설정할 수 있으며, 설정된 범위기준으로 유사한 결과를 유사도 결과 랭킹 리스트와 함께 제공해 준다. 넷째, 머신러닝을 통해 현재의 데이터들을 기반으로, 향후 결과에 대한 예측과 분석이 가능하였다. “BubbleUp”시스템을 통해서 종단적인 시간적 이벤트 데이터의 유사성, 군집화, 예측에 대한 통합적인 분석을 직관적으로 가능하게 제공하였다. Temporal event data is receiving increasing attention in a variety of fields. It is also helpful to identify a new configuration through comparison and analysis of patterns and similarities of events according to the change of time of temporal event data. Previous studies have focused on events that changed over time, but more and more research is being done on the changes in longitudinal time caused by repetition. In this research, an optimized "BubbleUp" visualization system for analyzing similarity of longitudinal temporal event data was proposed and developed. The visualization system was used to verify the following effects through case studies and usability evaluations. First, a visualization algorithm and user prototype of the BubbleUp system were implemented; furthermore, additional interaction functions and user interface were developed. User-friendly interaction has made it easier to identify similar relationships with other data to suit user needs. Second, the system facilitated the searching of data and it was possible to derive the potential pattern of data through clustering. Third, when the user selected the target, the system not only presented similar and dissimilar results but also freely set the similarity distribution range desired by the user. Similar results were also provided in the similarity result view with the similarity result rank list based on the set range. Fourth, it provided a means of comparing and analyzing future result effectively by predicting data through machine learning. Therefore, through this study, we confirmed that the BubbleUp system is a novel visualization system that intuitively enables integrated analysis of similarity, clustering, and prediction of longitudinal temporal event data.

빅데이터 클러스터링을 위한 인공벌군집 알고리즘

강범수 강원대학교 대학원 2019 국내석사

Data clustering is a problem that belongs to NP-Hard and determines the group by measuring the similarity of the entities in the dataset. The Artificial Bee Colony(ABC) is an algorithm that motivates how honey bee finds good honey. The ABC algorithm has a intelligence method to find the global optimal solution in data clustering problem within limited computational time. However, it has a disadvantage that it is slow to search. Therefore, it needs to study to efficiently search the global optimal solution in a limited time. The objective of this paper is to propose a combined artificial bee colony with K-means that has Euclidean distance and Silhouette as a function. I used Iris, Wine, Glass, Vowel, Cloud, Breast cancer data from UCI data sets and Ruspini data for experiment and verification. 데이터 클러스터링은 NP-Hard에 속하는 문제로 데이터 셋에 있는 개체들의 유사도를 측정하여 그룹을 결정하는 문제이다. 인공벌군집(ABC, Artificial Bee Colony) 알고리즘은 벌이 좋은 꿀을 찾아나가는 방법을 모티브로한 알고리즘이다. 인공벌군집 알고리즘은 전역 최적해를 탐색하는 효과가 뛰어난 대신 탐색하는 속도가 느리다는 단점이 있다. 따라서 제한된 시간에서 효율적으로 전역 최적해를 탐색하기 위한 연구가 필요하다. 본 논문의 목적은 유클리드 거리(Euclidean distance)와 실루엣(Silhouette)을 목적함수로 하는 K-means와 인공벌군집 알고리즘을 융합한 데이터 클러스터링 방법을 제안하는 것이다. 실험과 검증을 위해 UCI데이터 셋에 있는 Iris, Wine, Glass, Vowel, Cloud, Breast Cancer 데이터와 Ruspini 데이터를 사용하였다. 유클리드 거리를 목적함수로 하는 융합 인공벌군집 알고리즘은 KABCK(K-means + ABC + K-means), KABC(K-means + ABC), ABCK(ABC + K-means), ABC, K-means를 실험을 통해 비교하였고 실루엣을 목적함수로 하는 융합 인공벌군집 알고리즘은 KABC(K-means + ABC)와 실험 비교 하였다.

그룹특징기반 슬라이딩 윈도우 클러스터링기법 성능분석

양주연 숙명여자대학교 대학원 2018 국내석사

대용량 데이터의 발생과 처리가 대중화되면서 대용량 데이터 스트림 처리에 대한 수요가 급격하게 증가하고 있다. 이 수요에 따라 다양한 대용량 데이터 처리 기술이 개발되고 변화하고 있다. 한 분야로 주목받고 있는 방식은 슬라이딩 윈도우를 사용한 데이터 스트림 클러스터링이다. 슬라이딩 윈도우를 사용한 데이터 스트림 클러스터링은 윈도우가 이동할 때마다 새로운 클러스터를 생성한다. 기존에 알려진 슬라이딩 윈도우 상의 클러스터링 기법은 코어셋(Coreset)을 중심으로 데이터 스트림 클러스터링을 구현하고 있다. 이 코어셋을 다양한 형태로 변형하여 슬라이딩 윈도우 상에서 진행되는 클러스터링의 효율성을 개선하고자 하는 알고리즘이 다수 존재한다. 논문에서는 코어셋을 활용한 그룹특징을 이용한 알고리즘에서 발견한 개선이 가능한 요소를 변경하였다. 그리고 이를 통해 제안 알고리즘과 기존 알고리즘과의 파라미터에 따른 성능 비교 실험을 진행하였다. 개선된 사항에 대해 논하여 두 알고리즘을 비교하고 실험자에게 파라미터에 따른 이용 방향을 제시한다. Demand for processing large data streams is growing rapidly with the generation and processing of large volumes of data becoming popular. A variety of large data processing technologies are being developed and changing according to this demand. One area of interest is data stream clustering with sliding windows. Data stream clustering with sliding windows creates a new cluster every time the window moves. Previously known clustering techniques on sliding windows implement data stream clustering based on coreset. There are a number of algorithms that want to transform this coreset into various forms to improve the efficiency of clustering over a sliding window. In the thesis, we changed the reformable elements found in algorithms using group features by coresets. Through this test, we conducted a performance comparison test based on the parameters of the proposed algorithm and the existing algorithm. Discuss improvements, compare the two algorithms and present direction of use according to parameters to the Expeditor.