[논문] DBSCAN 리뷰 : Density Based Spatial Clustering of Applications with Noise

DBSCAN은 오직 한 개의 input parameter를 필요로하며, 사용자에게 적절한 값을 결정할 수 있도록 지원한다.
우리는 SEQUOIA 2000 benchmark의 실제 데이터와 합성 데이터를 사용하여 DBSCAN의 효과와 효율성에 대한 실험적인 평가를 수행했다.
우리의 실험의 결과

(1) DBSCAN은 잘 알려진 알고리즘인 CLARANS보다 임이의 모양의 클러스터를 발견하는데 훨씬 더 효율적이며,

(2) 효율면에서도 100배 이상 우수한 것으로 나타났다.

Keywords : Clustering Algorithms, Arbitrary Shape of Clusters, Efficiency on Large Spatial Databases, Handling Nlj4-275oise.

1. Introduction

수많은 응용프로그램들은 공간과 관련된 데이터들을 관리해야한다.
Spatial Database Systems(SDBS)는 공간 데이터 관리를 위한 데이터베이스 시스템이다.
위성 이미지, X-ray 또는 기타 자동 장비에서 더욱더 많은 양의 데이터가 얻어진다.
그러므로, 공간 데이터베이스에서 자동화 된 지식의 발견이 점점 더 중요해지고 있다.
데이터베이스에서 지식 발견에 대한 여러 task들은 문헌에 정의되어 왔다.
본 논문에서 고려되는 task는 클래스 식별이다. 즉, 데이터베이서의 객체를 의미있는 서브클래스들로 그룹화하는 것이다.
예를들어, 지구 관측 데이터베이스에서 일부 강(river)에 따른 집들의 클래스를 그룹화 할 수 있다.

클러스터링 알고리즘은 클래스 식별 작업에 적합하다.
하지만, 대규모 공간 데이터베이스에 적용하기에는 다음과 같은 요구사항이 따라온다.

(1) input parameter를 결정하기 위한 최소한의 도메인 지식이 필요하다.

왜냐하면, 대규모 데이터베이스를 다룰 때는 사전에 적절한 값을 알 수 없기 때문이다.

(2) 임의의 모양을 가진 클러스터를 발견해야 한다.

왜냐하면, 공간 데이터베이스에서 클러스터의 모양은 구형, 선형, 길쭉한 모양 등 다양하기 때문이다.

(3) 큰 데이터베이스에서 우수한 효율성을 제공해야 한다.

잘 알려진 클러스터링 알고리즘들은 위의 요구사항들을 해결할 솔루션을 제공하지 않는다.
본 논문에서, 우리는 새로운 클러스터링 알고리즘 DBSCAN을 제시한다.
DBSCAN은 오직 하나의 input parameter만을 필요로하며, 사용자가 적절한 값을 결정할 수 있도록 지원한다.
DBSCAN은 임의의 모양의 클러스터를 발견한다.
마지막으로, DBSCAN은 대규모 공간 데이터베이스에서 효율적이다.

2. Clustering Algorithms

>> 클러스터링이란? 바로가기

클러스터링 알고리즘에는 두 가지 유형이 있다.

- Partitioning algorithm

- hierarchical algorithm

Partitioning algorithm은 n개의 객체를 가지는 데이터베이스 D를 k개의 클러스터 집합으로 파티션을 구성하는 것이다.

- 이때, k는 이 알고리즘의 input parameter이다. 즉, 불행히도 많은 응용프로그램에서 사용할 수 없는 도메인 지식이 필요하다.

이 Partitioning algorithm은 일반적으로 D의 초기 파티션으로 시작한 다음, 목적함수를 최적화하기 위해 반복적으로 control한다.

즉, 데이터베이스 D에 대해 임의의 초기 cluster를 지정한 다음, 알고리즘을 반복하면서 최적화한다.

각 군집의 대표 객체는 클러스터의 중심(K-menas algorithm) 또는 클러스터 안에서 중심 주변에 위치한 객체 중 하나(K-medoid algorithm)로 표시된다.
결과적으로, Partitioning algorithm은 2단계 절차로 진행된다.

(1) 먼저, 목적함수를 최소화 하는 K를 정한다.

(2) 각 객체들을 대표 객체와 가장 가까운 클러스터에 할당한다.

두 번째 단계는 파티션은 voronoi diagram과 동일하며, 각 클러스터는 voronoi cell을 포함하고 있다는 점을 의미한다.
따라서 Partitioning algorithm에 의해 찾아진 모든 클러스터의 모양은 볼록하며 매우 제한적이다.

Ng & Han (1994)은 공간 데이터베이스에서 Partitioning algorithm을 탐색한다.
향상된 k-medoid 알고리즘인 CLARANS (Clustering Large Applications based on RANdomized Search)이 도입되었다.
실험에 따르면, CLARANS은 수천개의 객체를 가지는 데이터베이스에서 효율적이다.
Ng &Han (1994)은 또한 데이터베이스에서 클러스터의 개수 k를 정하는 방법에 대해서 논의한다.
그들은 k=2에서 k=n까지 각각 CLARANS를 한 번씩 실행하라고 제안한다.
발견된 각 군집에 대해 실루엣 계수(silhouette coefficient)가 계산되고, 최종적으로 최대 실루엣 계수를 가지는 클러스터링(k)이 선택된다.
하지만 불행히도, 이 접근방법의 run time은 n이 클 때 금지된다. CLARANS의 run time은 O(n)이기 때문이다.

즉, n이 커질 수록 시간이 오래 걸리기 때문이다.

CLARANS은 가정한다. 군집화된 모든 객체들은 main memory에 동시에 상주할 수 있다.

Hierarchical algorithms은 데이터베이스 D의 계층적인 분해(decomposition)를 만든다.
계층적 분해는 dendrogram으로 표현되는데, 트리는 각 서브셋이 오직 하나의 객체로 구성될 때까지 D를 반복적으로 분할한다.

즉, n개의 객체를 n개로 분해한다.

이러한 계층에서, 각 트리의 노드는 D의 클러스터를 나타낸다.
dendrogram은 각 단계에서 클러스터를 병합하거나 나눔으로써 잎에서 뿌리까지(응집 방식) 또는 뿌리에서 잎으로(분할 방식) 생성 될 수 있다.
Partitioning 알고리즘과 달리 hierarchical 알고리즘은 k를 input으로 필요로하지 않는다.
그러나, 언제 병합 또는 분할 프로세스를 종료해야 하는지 나타내는 종료조건을 정의해야 한다.
예를 들어 응집 방식에서 종료조건은 모든 클러스터 Q 사이의 임계 거리 이다.

지금까지 hierarchical 클러스터링 알고리즘의 주요 문제점은 종료 조건에 대한 적절한 파라미터를 도출하는 것이 어렵다는 것이다.
즉, 클러스터를 나누는데 충분히 작음과 동시에 군집이 두 개로만 나뉘지 않을 정도의 충분히 큰 값인 의 값이다.
최근에, 신호 처리 영역에서 자동으로 종료조건을 도출하는 hierarchical 알고리즘 Ejcluster가 제시되었다.
이 알고리즘이 주요 아이디어는 "충분히 작은"단계로 첫번째 포인트에서 두번째 포인트로 갈 수 있는 같은 클러스터에 속하는 두 개의 포인트가 존재하는 것이다.
Ejcluster는 분열 방식을 따른다.
그것은 어떠한 도메인 지식도 필요없다.
게다가, 실험에 따르면 그것은 볼록하지 않은 클러스터를 발견하는데 매우 효율적이다.
하지만, Ejcluster의 computational cost은 각 두 포인트들의 거리를 계산해야 하기 때문에 O(n2)이다.
즉, 대용량 데이터베이스에는 적절하지 않다.

Jain(1988)은 k-차원의 point set에서 클러스터를 식별하기 위해 밀도 기반 접근방식을 탐색한다.
데이터 셋은 다수의 비 중첩 셀(nonoverlapping cells)로 분할되고 히스토그램이 구성된다.
상대적으로 높은 빈도의 포인트를 가진 셀들은 잠재적인 클러스터의 중심이며, 클러스터간 경계는 히스토그램에 "valley"에 해당한다.
이 방법에는 모든 모양의 클러스터를 식별하는 기능이 있다.
하지만, 다차원 히스토그램을 저장하고 검색하기 위한 공간 및 런타임 요구사항이 엄청 날 수 있다.
공간 및 런타임 요구 사항이 최적화 되더라도, 이러한 접근 방식의 성능은 셀의 크기에 따라 결정된다.

3. A Density Based Notion of Clusters

<figure 1>에 묘사된 샘플 포인트들은 보면, 클러스터에 속하지 않는 포인트와 노이즈 포인트를 쉽고 명화하게 감지할 수 있다.

우리가 클러스터를 인식하는 주요 이유는 각 클러스터 내에 점들의 밀도가 외부 클러스터에 비해 상당히 높기 때문이다. 즉, 각 클러스터끼리 점들이 모여있기 때문이다.
또한, 노이즈 영역의 밀도는 모든 클러스터의 밀도보다 낮다.

다음으로, 우리는 공간 S에 k-차원에 데이터베이스 D에 포인트들에서 "클러스터"와 "노이즈"에 대한 직관적인 개념을 공식화한다.
우리의 클러스터 개념과 DBSCN알고리즘은 2D 또는 3D 유클리디안 공간 뿐 아니라, 일부 고차원 공간에도 적용된다.
주요 아이디어는 주어진 반경에 이웃하는 클러스터의 각 포인트들은 최소한의 포인트 수를 포함해야 한다.
즉, 이웃의 밀도는 어떤 임계값을 초과해야 한다.

일정 반경안에 일정 개수의 포인트가 존재해야 클러스터라 정의한다.

이웃의 모양은 dist(p,q)라 표시되는 두 점 p와 q에 대한 거리 함수에 따라 결정된다.
예를들어, 2D 공간에서 Manhattan 거리를 사용하는 경우, 이웃의 모양은 직사각형이다.
우리의 방식은 어떠한 거리 함수에도 작동하기때문에, 특정 응용 분야에도 적합한 함수가 선택될 수 있다.
적절한 시각화를 위해, 모든 예시는 2D공간에서 유클리디안 거리로 사용된다.

정의1) (Eps-neighborhood of a point) : 포인트 p의 Eps-neighborhood,

= : 점 p와 일정한 거리 내에 있는 점 q들

단순히 접근하면, 클러스터에 각 점들은 최소 개수(MinPts)의 Eps-neighborhood 점들이 있어야 한다.

즉, 한 점 주변 일정 거리 안에 최소 개수(MinPts)이상의 점들이 있어야 클러스터가 형성된다.

하지만, 이 접근은 클러스터에는 두 종류의 점이 존재하기 때문에 실패한다.

(1) core points : 클러스터 안에 포인트

(2) border points : 클러스터의 경계에 있는 포인트

일반적으로, border point의 Eps-neighborhood는 core point에 비해 현저히 적은 점을 포함한다.
따라서, 동일한 클러스터에 속하는 모든 포인트를 포함 시키려면 최소 포인트 수(MinPts)를 상대적으로 낮은 값으로 설정해야한다.

<논문에 없는 예시 그림>

core point를 기준으로 Eps-neighborhood 안에 7 points가 존재하며,

border point를 기준으로는 4 points가 존재한다.

만약 MinPts를 core point기준으로 7로 했다면, 끝 쪽에 있는 포인트들은 같은 클러스터로 형성되지 않을 것이다.

그러나, 이 값은 각 클러스터마다(- 특히, 노이즈가 있는 경우) 특성화된 값이 아니다.
그러므로, 클러스터 C에 있는 모든 포인트 p에 대해, p는 C에 있는 Eps-neighborhood인 q(in C)들을 최소 포인트 개수 이상 필요로한다.

즉, 클러스터 안에 있는 모든 포인트들은 다 일정 거리 이내에 최소 개수 이상의 포인트들이 있어야 한다.

예를 들어, 위 그림에서 Eps=1, MinPts=3이라 할 때, 모든 포인트들의 반경 1안에 3개의 점이 존재해야 그 포인트들이 하나의 클러스터로 묶인다는 뜻이다.

정의2) (directly density-reachable) : 다음과 같은 상황일 때 포인트 p는 q에 directly density-reachable이다.

1)

2)

분명히, directly density-reachable은 core point의 쌍에서는 대칭적이다.
하지만, 일반적으로 core point와 border point에서는 대칭적이지 않다.
Figure 2는 비대칭적인 케이스를 보여준다.

point q는 Eps안에 MinPts이상의 포인트들이 존재하기 때문에 q는 p에 directly density-reachable하지만,

p는 Eps안에 MinPts이상의 포인트들이 존재하지 않기 때문에, Eps안에 q가 있어도 directly density-reachable하지 않다.

정의3) (density-reachable) : 다음과 같은 상황일 때 p는 q에 density-reachable하다.

- points 에서, 각 이 에 density-reachable

Density-reachability는 directly density-reachablility를 확장한 개념이다.
이 관계는 전이적이지만, 대칭은 아니다.
Figure 3은 비대칭 사례에 대해서 보여준다.

일반적으로 대칭은 아니지만, density-reachability는 core points에 대해 대칭이다.

같은 클러스터 C에 두 border points는 서로 density-reachable할 수 없다. 왜냐하면, core points의 조건(Eps안에 MinPts이상의 포인트 존재한다는 조건)이 두 border point에 유지 될 수 없기 때문이다.
하지만, C안에는 두 border point에 density-reachable한 core point가 꼭 있어야 한다.
따라수 우리는 이러한 border points의 관계를 다루는 density-connectivity 개념을 소개한다.

정의4) (density-connection) : 다음과 같은 상황일 때 point p는 point q에 density-connected 하다.

- p와 q가 density-reachable한 point o가 존재

Density-connectivity 는 대칭적인 관계이다.
density reachable인 포인트에서, density-connectivity 관계는 반사적이다.

이제, density-based(밀도 기반) 클러스터의 개념을 정의할 수 있다.
직관적으로, 클러스터는 최대 density-reachability인 density-connected포인트들로 정의된다.
노이즈는 주어진 클러스트에 상대적으로 정의된다.
노이즈는 단순히 D의 클러스터에 속하지 않는 포인트 집합이다.

정의5) (cluster) : D를 포인트들의 데이터베이스라 할 때, 클러스터 C는 다음과 같이 정의된다.

1) 모든 p,q에 대해, 이고 q가 p에 density-reachable하면 (Maximality)

2) 모든 p,q에 대해, p가 q에 density-connected. (Connectivity)

정의6) (noise) : , ... , 가 데이터베이스 D의 클러스터라 할 때, 어떤 클러스터 에도 속하지 않는 point들의 집합을 noise라 하자. 즉,

클러스터 C에 관하여.

Eps와 MinPts는 다음과 같은 이유로 최소 MinPts points를 포함한다.
C는 최소 한 포인트 p를 포함하므로, p는 어떤 point o(p와 같은 수도 있음)를 통해 자체적으로 density-connected여야 한다.
따라서 최소 o는 core point 조건을 만족해야하고, 동시에 o의 Eps-neighborhood는 최소 MinPts 포인트여야 한다.

다음 정리는 클러스터링 알고리즘의 정확성을 검증하는데 중요한 것이다.
직관적으로, 그들은 다음을 진술한다.
매개변수 Eps와 MinPts가 주어지면, 2단계 접근 방식을 통해 클러스터를 발견 할 수 있다.

(1) 먼저, 데이터베이스에서 core point 조건을 만족하는 임의의 포인트를 seed로 선택한다.

(2) 다음, 그 seed로 부터 density-reachable한 모든 포인트를 검색한다.

정리1) p를 D의 point이며, 라 하자.

그리고 를 cluster라 하자.

- 클러스터 C가 core point 중 하나에 의해 고유하게 결정된다는 것은 분명하지 않다.

- 하지만, C의 각 포인트는 모든 C의 core point로 부터 density-reachable하기 때문에,

클러스터 C는 C의 임의의 core point로부터 density-reachable한 포인트들을 포함한다.

정리2) C를 클러스터라 하고, p를 인 임의의 포인트라 하자.

Then C는 이다.

4. DBSCAN : Density Based Spatial Clustering of Applications with Noise

이번 section에서는 정의5와 6에따른 공간 데이터베이스에서 클러스터와 노이즈를 찾는 DBSCAN(Density Based Spatial Clustering of Applications with Noise) 알고리즘을 소개한다.
이상적으로는, 각 클러스터에 Eps와 MinPts의 적절한 parameter와 각 클러스터에서 최소 한 포인트 이상을 알아야 한다.
그럼, 적절한 parameter를 사용하여 주어진 포인트에서 density-reachable한 모든 포인트들을 검색할 수 있다.
하지만, 데이터베이스에 모든 클러스터에 대해서 사전에 이 정보들을 얻기는 쉽지않다.
하지만, "가장 얇은" 즉, 가장 밀도가 낮은 클러스터의 parameter Eps와 MinPts를 결정할 간단하고 효과적인 휴리스틱(불충분한 시간이나 정보로 인하여 합리적인 판단을 할 수 없거나, 체계적이면서 합리적인 판단이 굳이 필요하지 않은 상황에서 사람들이 빠르게 사용할 수 있는 어림짐작의 방법)(4.2 section에 제시)이 있다.
따라서, DBSCAN은 모든 클러스터에 대해 Eps와 MinPts를 같은 값으로 사용한다.
"가장 얇은"클러스터의 density parameters는 노이즈로 간주되지 않는 가장 낮은 밀도를 지정하는 global parameters가 적합한 후보이다.

즉, 가장 적은 point를 갖는 클러스터를 잘 정의할 수 있는 Eps와 MinPts를 지정해야 한다,

4.1 The Algorithm

클러스터를 찾기위해, DBSCAN은 임의의 포인트 p에서 시작한다. 그리고 p에서부터 density-reachable한 모든 포인트들을 검색한다.
만약 p가 core point라면, 이 절차는 클러스터를 생성한다. (정리2 참고.)
만약 p가 border point라면, p에서부터 density-reachable한 포인트는 없고, DBSCAN은 데이터베이스에 다음 포인트를 탐색한다.

Eps와 MinPts에 대해서 global한 값(모든 클러스터에 대해 같은 값)을 쓰기때문에, DBSCAN은 만약, 다른 밀도의 두 클러스터가 가까울 경우에는 정의5에따라 하나로 병합할 수 있다.
두 세트 , 사이의 거리를 라 하자.
그럼, 가장 얇은 클러스터(가장 적은 point 수를 갖는 클러스터)의 밀도를 갖는 두 세트의 포인트는 두 세트 사이의 거리가 Eps보다 큰 경우에만 서로 분리된다.
결과적으로, MinPts 값이 높이 감지 된 클러스터에는 DBSCAN의 재귀 호출이 필요할 수 있다.
그러나, DBSCAN을 재귀적으로 적용하면 우아하고 매우 효율적인 기본 알고리즘이 생성되므로 단점이 아닙니다.
또한, 클러스터의 포인트의 재귀 클러스터링은 쉽게 탐지할 수 있는 어떠한 조건에서만 필요하다.

DBSCAN알고리즘은 쉬운 이해를 위해 논문이 아닌 위키피디아를 참조했다.

출처 : https://en.wikipedia.org/wiki/DBSCAN

DBSCAN(DB, disFunc, eps, minPts) {

C = 0    /* 클러스터에 포함되는 point 수 */

DB안에 포함되는 각각의 포인트 P에 대하여 {

만약, P에 라벨이 있다면    /* P가 이미 속한 클러스터가 있다면 skip */

continue

N = DB안에서 P와 eps거리 안에 있는 포인트들

만약 N의 개수가 minPts 보다 작으면, {

P의 라벨 = Noise

continue

}

C = C + 1       /* N의 개수가 minPts보다 크면 해당 P는 클러스터에 포함 */

P의 라벨은 C            /* N의 개수가 minPts보다 크면 해당 P는 클러스터에 포함 */

S = N에서 P가 빠진 집합

S에 포함된 각 포인트 Q에 대하여 {

만약, Q의 라벨이 노이즈면

Q의 라벨 = C

만약, Q의 라벨이 이미 정의되어있다면

continue

Q의 라벨 = C

N = DB안에서 Q와 eps거리 안에 있는 포인트들

만약 N의 개수가 minPts보다 크면

S = S와 N의 합집합

}

}

}

4.2 Determining the Parameters Eps and MinPts

이 section에서는 데이터베이스에서 "가장 얇은"클러스터의 parameter Eps 및 MinPts를 결정하는 간단하지만 효과적인 휴리스틱을 개발한다.
이 휴리스틱은 다음 관찰을 기반으로한다.
d를 포인트 p와 k번째로 가장가까운 이웃사이의 거리라하자.
그럼, p의 d-neighborhood는 거의 모든 점 p에 대해 정확히 k + 1 개의 점을 포함한다.

ex) if k=1, p와 d(p와 가장 가까운 포인트와의 거리)에 있는 포인트는 2개(p 포함)이다.

p의 d-neighborhood는 만약, 몇몇 포인트들이 p와 정확히 같은 거리 d를 가질 때 k+1 이상의 포인트를 포함한다.
또한 군집의 한 점에 대해 k를 변경해도 d가 크게 변경되지는 않는다.
이것은 k = 1,2, 3 ....에 대해 p의 k 번째 가까운 이웃이 대략 직선에 위치하는 경우에만 발생하며, 이는 일반적인 경우에 해당되지 않는다.

주어진 k에 대해서 데이터베이스 D에 대해 k-dist 함수를 실수(real number)로 정의하고, 각 포인트를 k 번째로 가까운 이웃 포인트와의 거리로 매핑한다.

즉 k-dist 함수는 각 포인트로부터 k번째 가까운 포인트와의 거리이다.

데이터베이스의 포인트들을 k-dist값으로 내림차순으로 정렬 할 때, 이 함수의 그래프는 데이터베이스의 density 분포에 대한 힌트를 제공한다.
이 그래프를 sorted k-dist graph라 부른다.
만약, 임의의 점 p를 선택하고 Eps를 k-dist(p)로, MinPts를 k로 선정한다면 k-dist 값 보다 작거나 같은 모든 포인트들이 core point가 된다.

즉, 임의의 포인트 p로부터 k번째 가까운 포인트와의 거리를 Eps로, k를 MinPts로 지정한다면, k번째 가까운 포인트와의 거리가 Eps보다 작거나 같은 모든 포인트들이 core point가 된다.

만약, D의 "가장 얇은"군집에서 k-dist 값의 최대값으로 임계점을 찾을 수 있으면, 원하는 매개 변수 값을 갖게된다.
임계점은 sorted k-dist graph의 첫 번째 "밸리"에서 첫 번째 포인트이다. (figure 4 참조)

x축 : 데이터베이스의 모든 포인트에 대해 k-dist값을 계산한 후 내림차순 정렬

y축 : 각 포인트에 대한 k-dist 값

첫 번째 밸리에 해당하는 k-dist값이 Eps가 된다.

높은 k-dist값(threshold의 왼쪽)을 갖는 모든 포인트들은 noise로 간주되며, 다른 모든 점들(th의 오른쪽)은 클러스터로 할당된다.

일반적으로, 자동으로 첫 번째 "밸리"를 감지하는 것은 어렵지만, 사용자가 그래픽 표현으로 밸리를 보는 것은 상대적으로 간단하다.
그러므로, 임계점을 결장하기 위한 상호식 접근 방식을 따르도록 제안한다.

DBSCAN은 두 가지 파라미터, Eps와 MinPts가 필요하다.
하지만, 실험에 따르면 k>4에 대한 k-dist 그래프는 4-dist 그래프와 크게 다르지 않으며, 더 많은 계산이 필요하다.
그러므로, 모든 데이터베이스(2차원 데이터에 대하여)에 대해 MinPts를 4로 설정하여 MinPts 파라미터를 제거한다.
DBSCAN의 파라미터 Eps를 결정하기 위한 다음의 상호식 접근 방식을 제안한다.

데이터베이스의 4-dist graph를 계산하고 표시한다.
만약 사용자가 noise의 percentage를 알 수 있다면, 이 percentage는 입력되고, 시스템은 임계점에 대한 제안을 얻는다.
사용자는 제안된 임계값을 받아드리거나, 다른 지점을 임계값으로 선택한다. 임계값의 4-dist값은 DBSCAN의 Eps로 사용된다.

5. Performance Evaluation

이번 section에서는 DBSCAN의 성능을 평가한다.
CLARANS는 KDD를 위해 설계된 최초이자 유일한 클러스터링 알로기즘이기 때문에 CLARANS와 DBSCAN의 성능을 비교한다.
향후 연구에서는 classical density based clustering algorithms와 비교할 것이다.
DBSCAN은 C++로 구현했다.
모든 실험은 HP 735/100 워크스테이션에서 실행되었다.
synthetic 샘플 데이터베이스와 SEQUOIA 2000 benchmark의 데이터베이스를 모두 사용했다.

효율성(정확도) 측면에서 DBSCAN과 CLARANS를 비교하기 위해, figure 1에서 묘사된 3개의 synthetic 샘플 데이터베이서를 사용한다.

DBSCAN와 CLARANS은 다른 타입의 클러스터링 알고리즘이기 때문에, 분류 정확도에 대한 공통적인 측정 방법이 없다.
따라서, 육안 검사를 통해 두 알고리즘의 정확도를 평가한다.
샘플 데이터베이스 1 에는, 크기가 크게 다른 4개의 공 모양 클러스터가 있다.
샘플 데이터베이스 2 에는, 볼록하지 않은 모양의 4개의 클러스터가 있다.
샘플 데이터베이스 3 에는, noise가 있는 모양과 크기가 다른 4개의 클러스터가 있다.
두 클러스터링 알고리즘의 결과르르 보여주기 위해 각 클러스터를 다른 색상으로 시각화한다.
CLARANS에 advantage를 주기 위해 k=4로 설정했다.
CLARANS가 발견한 클러스터는 figure 5에 설명되어있다.

DBSCAN의 경우 샘플 데이터베이스 1, 2의 noise는 0%로, 3은 10%로 설정했다.
DBSCAN이 발견한 클러스터링은 figure 6에 표시되어있다.

DBSCAN은 정의5에 따라 모든 클러스터들을 발견하고, noise points를 발견한다.
그러나, CLARANS은 클러스터가 상대적으로 크거나, 다른 클러스터에 가까운 경우 클러스터를 분할한다.
또한, CLARANS은 noise에 대한 명시적인 개념이 없다.
대신, 모든 포인트가 가장 가까운 medoid에 할당된다.

DBSCAN과 CLARANS의 효율성을 시험하기 위해, SEQUOIA 2000 benchmark 데이터를 사용한다.
SEQUOIA 2000 benchmark 데이터베이스는 지구 과학 과제를 대표하는 실제 데이터 셋을 사용한다.
데이터베이스에는 4가지 타입의 데이터가 있다.

raster data (TV에서 영상 신호가 없을 때 나타나는 희게 빛나는 화면)
point data
polygon data (다각형 데이터)
directed graph data

point data는 미국 지질 조사의 지명 정보 시스템에서 추출한 62,584개의 캘리포니아 랜드 마크 이름과 위치가 포함된다.
point data는 약 2.1M 바이트이다.
전체 데이터에 대한 CLARANS의 런타임이 매우 길기때문에, SEQUIOA 2000 point data에서 전체 데이터를 대표하는 2% ~ 20%의 subset을 추출했다.
DBSCAN과 CLARANS의 런타임 비교는 table1에 표시되어있다.

실험 결과는 DBSCAN의 런타임이 포인트 수와 선형관계(정비례)보다 약간 높다는 것을 보여준다.
그러나 CLARANS의 런타임은 (포인트 수^2)에 가깝다.
결과는 DBSCAN이 데이터베이스 크기가 커짐에 따라 250에서 1900 사이의 비율로 CLARANS보다 성능이 우수함을 보여준다.

6. Conclusions

클러스터링 알고리즘은 공간 데이터베이스에서 클래스 식별 작업에 적합하다.
그러나, 유명한 알고리즘들은 큰 공간 데이터베이스에 적용될 때 심각한 단점이 있다.
본 논문에서는 밀도 기반 클러스터 개념에 의존하는 알고리즘인 DBSCAN을 제시했다.
오직 하나의 input parameter만을 필요로하며, 사용자에게 적절한 값을 결정할 수 있도록 지원한다.
우리는 SEQUOIA 2000 벤치 마크의 합성 데이터와 실제 데이터에 대한 성능 평가를 수행했다.
이 실험의 결과는 DBSCAN이 유명한 알고리즘인 CLARANS보다 임의의 모양의 클러스터를 발견하는 데 훨씬 더 효과적이라는 것을 보여준다.
또한, 실험 결과 DBSCAN은 효율면에서 CLARANS보다 100배 이상 우수한 것으로 나타났다.

향후 연구는 다음과 같은 문제를 고려해야 한다.

1) 본 연구는 point object만 고려했으나, 공간 데이터베이스는 다각형과 같은 확장된 object가 포함될 수 있다.

DBSCAN을 일반화하기 위해 다각형 데이터베이스의 Eps-neighborhood에서 밀도의 정의를 개발해야한다.

2) 고차원 feature 공간에 대한 DBSCAN의 적용을 조사해야 한다.

특히, 이러한 응용에서 k-dist 그래프의 모양이 탐구되어야한다.

저작자표시

'AI > 논문' 카테고리의 다른 글

[논문] FGSM 설명 : EXPLAINING AND HARNESSING ADVERSARIAL EXAMPLES (6)	2019.09.24
[논문] GoogleNet - Inception 리뷰 : Going deeper with convolutions (0)	2019.08.27
[논문] GAN 리뷰 : Generative Adversarial Nets (0)	2019.02.22
[논문] ADGAN 리뷰 : ANOMALY DETECTION WITH GENERATIVE ADVERSARIAL NETWORKS (1)	2018.12.04
[논문] SRGAN 리뷰 : Photo-Realistic Single Image Super-Resolution Using a Generative Adversarial Network (2)	2018.11.05

현재글[논문] DBSCAN 리뷰 : Density Based Spatial Clustering of Applications with Noise

슈퍼짱짱