1 |
1
전체 데이터 공간(entire data space)을 복수의 지역 공간(local region)들로 분할하는 공간 분할(space-partitioning) 단계;상기 복수의 지역 공간들을 중심으로 맵리듀스(MapReduce) 환경에서 분산된 맵 및 리듀스 태스크들(Map and Reduce tasks)을 사용하여 복수의 지역 최종 클러스터(local final cluster)들을 생성하는 클러스터링(clustering) 단계; 및상기 복수의 지역 최종 클러스터들을 병합하여 최종 클러스터를 생성하는 정제(refining) 단계를 포함하는 CF+ 트리를 사용한 맵리듀스 기반 분산 군집화 방법
|
2 |
2
제1항에 있어서, 상기 공간 분할 단계는샘플 객체들을 이용하여 상기 전체 데이터 공간을 상기 리듀스 태스크의 개수에 대응되는 지역 공간들로 분할하는 단계를 포함하는 것을 특징으로 하는 CF+ 트리를 사용한 맵리듀스 기반 분산 군집화 방법
|
3 |
3
제2항에 있어서, 상기 공간 분할 단계는상기 샘플 객체들에 대해 K-평균++(K-means++) 알고리즘을 적용하여 클러스터링을 수행한 결과로서 생성되는 클러스터들을 상기 지역 공간들에 대응시킴으로써 상기 분할을 수행하는 단계를 포함하는 것을 특징으로 하는 CF+ 트리를 사용한 맵리듀스 기반 분산 군집화 방법
|
4 |
4
제3항에 있어서, 상기 공간 분할 단계는상기 복수의 지역 공간들에 대응되는 클러스터들의 중심(centroid)을 해당 지역 공간의 공간 중심(region centroid)으로 정의하는 단계를 포함하는 것을 특징으로 하는 CF+ 트리를 사용한 맵리듀스 기반 분산 군집화 방법
|
5 |
5
제4항에 있어서, 상기 공간 중심은상기 클러스터링 단계에서 상기 맵 및 리듀스 태스크들에 브로드캐스팅(broadcasting)되는 것을 특징으로 하는 CF+ 트리를 사용한 맵리듀스 기반 분산 군집화 방법
|
6 |
6
제1항에 있어서, 상기 맵 태스크는입력된 객체들을 기초로 CF+(Clustering Feature) 트리를 구축하고 해당 CF+ 트리의 미세 클러스터(MC, Micro Cluster)들을 가장 가까운 공간 중심을 담당하는 리듀스 태스크로 전달하는 것을 특징으로 하는 CF+ 트리를 사용한 맵리듀스 기반 분산 군집화 방법
|
7 |
7
제6항에 있어서, 상기 리듀스 태스크는입력된 미세 클러스터(MC)들을 기초로 CF+ 트리를 구축하고 해당 CF+ 트리와 기 설정된 임계값을 이용하여 ERC 단계를 통해 지역 최종 클러스터들을 생성하는 것을 특징으로 하는 CF+ 트리를 사용한 맵리듀스 기반 분산 군집화 방법
|
8 |
8
제7항에 있어서, 상기 리듀스 태스크는상기 입력된 미세 클러스터(MC)들 중에서 지역 간 경계를 중심으로 정의되는 경계 영역과 중첩되는 경계 MC를 결정하는 것을 특징으로 하는 CF+ 트리를 사용한 맵리듀스 기반 분산 군집화 방법
|
9 |
9
제8항에 있어서, 상기 리듀스 태스크는상기 지역 간 경계와 연관된 공간 중심 쌍에 대해 특정 미세 클러스터(MC)를 스칼라 프로젝션(scalar projection)하여 해당 특정 미세 클러스터(MC)가 상기 경계 MC인지 여부를 결정하는 것을 특징으로 하는 CF+ 트리를 사용한 맵리듀스 기반 분산 군집화 방법
|
10 |
10
제9항에 있어서, 상기 리듀스 태스크는상기 특정 미세 클러스터의 평균 반지름과, 상기 특정 미세 클러스터의 중심을 상기 공간 중심 쌍을 구성하는 두개의 공간 중심들 사이의 직선으로 스칼라 프로젝션한 결과를 합산하여 제1 거리를 산출하는 단계;상기 두개의 공간 중심들 사이의 거리를 2로 나누어 제2 거리를 산출하는 단계; 및상기 제1 및 제2 거리들 간의 차이가 상기 임계값보다 작은 경우 상기 특정 미세 클러스터를 상기 경계 MC로 결정하는 단계를 통해 동작하는 것을 특징으로 하는 CF+ 트리를 사용한 맵리듀스 기반 분산 군집화 방법
|
11 |
11
제8항에 있어서, 상기 정제 단계는상기 클러스터링 단계의 경계 MC들을 이용하여 정제된 CF+ 트리(refining CF+ tree)를 구축하는 단계를 포함하고,상기 정제된 CF+ 트리의 경계 MC들 각각은 서로 병합되지 않고 해당 경계 MC와 연관되는 리듀스 태스크의 ID 및 지역 최종 클러스터의 ID를 포함하는 것을 특징으로 하는 CF+ 트리를 사용한 맵리듀스 기반 분산 군집화 방법
|
12 |
12
제11항에 있어서, 상기 정제 단계는상기 정제된 CF+ 트리와 상기 임계값을 이용하여 상기 ERC 단계를 통해 상기 경계 MC들의 집합을 생성하는 단계를 포함하는 것을 특징으로 하는 CF+ 트리를 사용한 맵리듀스 기반 분산 군집화 방법
|
13 |
13
제12항에 있어서, 상기 정제 단계는상기 경계 MC들의 집합을 기초로 상기 복수의 지역 최종 클러스터들을 병합한 결과로서 전역 최종 클러스터들을 생성하여 상기 최종 클러스터로서 제공하는 단계를 포함하는 것을 특징으로 하는 CF+ 트리를 사용한 맵리듀스 기반 분산 군집화 방법
|
14 |
14
제7항 또는 제12항에 있어서, 상기 ERC 단계는트리를 기초로 상기 임계값 내에서 선형적으로 인접한 미세 클러스터(MC)들을 그룹화 하여 미세 클러스터 세그먼트(MCS, Micro Cluster Segment)를 생성하는 분할 과정(partition step); 및미세 클러스터 세그먼트(MCS) 간 거리(IMD)가 상기 임계값 이내인 미세 클러스터 세그먼트들을 그룹화 하여 미세 클러스터 세그먼트 집합을 생성하는 정제 과정(refinement step)을 포함하는 것을 특징으로 하는 CF+ 트리를 사용한 맵리듀스 기반 분산 군집화 방법
|
15 |
15
전체 데이터 공간(entire data space)을 복수의 지역 공간(local region)들로 분할하는 공간 분할(space-partitioning) 수행부;상기 복수의 지역 공간들을 중심으로 맵리듀스(MapReduce) 환경에서 분산된 맵 및 리듀스 태스크들(Map and Reduce tasks)을 사용하여 복수의 지역 최종 클러스터(local final cluster)들을 생성하는 클러스터링(clustering) 수행부; 및상기 복수의 지역 최종 클러스터들을 병합하여 최종 클러스터를 생성하는 정제(refining) 수행부를 포함하는 CF+ 트리를 사용한 맵리듀스 기반 분산 군집화 장치
|