[CS246] BFR Algorithm: Extension of k-means to large data

 

 

Motivation

k-mean 알고리즘은 모든 데이터를 메모리에 올리고 클러스터링 알고리즘을 수행한다.

그러나 현실세계의 데이터는 너무 커서(데이터베이스로 관리 등) 메인메모리에 올릴 수 없다.

BFR 알고리즘을 매우 큰 데이터(disk-resident data sets)에 k-mean 클러스터링을 적용하는 알고리즘이다.

 

BFR은 논문의 세 저자 Paul S. Bradley, Usama M. Fayyad, Cory A. Reina의 앞글자를 딴 것이다.

(논문: Scaling Clustering Algorithms to Large Database)

논문에서 설명한 BFR 알고리즘 개요

BFR Overview

Assume

모든 클러스터는 axis-aligned ellipse이다. (그러나 각 axis마다 표준편차가 다른 것은 허용된다)

Clusters are axis-aligned ellipses (Stanford CS246, MMDS textbook)

Idea

data point를 모두 저장하는 대신, 그룹의 summary statistics를 저장한다.

 

Discard set (DS)

centroid에 충분히 가까운 점이어서 클러스터를 형성하고, cluster summary를 만드는 집합.

discard라 부르는 이유는 cluster에서 discard되는 것이 아니라 memory에서 discard된다는 뜻이다.

 

Compressed set (CS)

데이터들 끼리는 뭉쳐있어 summary를 만들지만 어떠한 centroid와도 가까이 있지 않은 집합. 

어떤 centroid와도 충분히 가깝지 않기에 CS에 속한 점들은 어떤 클러스터에 속하지 않는다.

minicluster라고도 부른다.

 

Retained set (RS)

cluster에 속하지도 않고, 다른 점들과도 가까이 있지 않아서 CS에도 속하지 않는 집합.

이들은 메인 메모리에 남아있다.

Points in the discard, compressed, and retained sets (Stanford CS246)

Summarizing Sets of Points

$d$: 데이터 차원

$N$: DS 또는 CS에 속한 데이터의 개수

$\text{SUM}$: 모든 점의 같은 차원 내의 합

$\text{SUMSQ}$: 모든 점의 같은 차원 내의 제곱 합

※ $\text{SUM}_i = \sum_{k \in C}(x_k)_i, \ \text{SUMSQ}_i = \sum_{k \in C}(x_k)_i^2 $

 

따라서 각 DS와 CS는 $(2d+1)$개의 값만 (메인 메모리에) 저장하면 된다.

또한 분산 역시 쉽게 계산할 수 있다. $i$번째 차원의 분산은 $\text{Var}=E[X^2] - E[X]^2 = \text{SUMSQ}_i/N - (\text{SUM}_i/N)^2$ 을 이용하여 구한다.

 

Example

어떤 클러스터가 3개의 점 $(5, 1),\ (6,-2),\ (7,0)$으로 이루어진다 하자. 

그러면 $N=3$이고 SUM, SUMSQ 벡터는 $\text{SUM}=[18,-1],\ \text{SUMSQ}=[110, 5]$이다.

클러스터의 centroid는 $\text{SUM}/N=[6, -\frac{1}{3}]$ 이다.

각 차원마다 분산과 표준편차를 구하면 다음과 같다.

$\text{Var}_1 = (110/3)-(18/3)^2=(110/3)-(324/9)=2/3=0.667,\ \text{Sd}_1=\sqrt{0.667}=0.816$

$\text{Var}_2 = (5/3)-(-1/3)^2=14/9=1.56,\ \text{Sd}_2=\sqrt{1.56}=1.25$

반응형

BFR Algorithm: Process

1. Initialize k-clusters(centroids)
2. for each chunk (=a bag of points) in data
    for each point in chunk
        3. 클러스터에 충분히 가까우면, 해당 클러스터에 새로운 데이터 할당
    4. 남아있는 점들로 새로운 클러스터를 만든다.
        이렇게 생긴 클러스터는 CS이고, 여전히 outlier가 되는 점들은 RS가 된다.
    5. 새로운 클러스터들이 기존 $k$개의 클러스터로 합칠 수 있으면 합친다.
Last round: CS과 RS를 가장 가까운 클러스터로 편입시킨다. (merge하지 않는 것도 방법이다)

Selection of the initial centroids

k-mean 알고리즘과 마찬가지로, k개의 클러스터를 미리 정할 필요가 있다.

크게 3가지 방법이 제안된다.

 

(1) 그냥 랜덤하게 $k$개의 점 선택

(2) 작은 random sample을 구하고, 이들을 클러스터로 간주한다.

(3) 먼저 1개의 점을 랜덤하게 선택한다. 그리고 $(k-1)$개의 점 중에서 이전 단계에서 선택한 점에서 가장 거리가 먼 점을 고른다. (각 클러스터끼리의 거리는 멀도록 하는 것과 유사함)

 

How Close is Close Enough?

이제 디스크로부터 읽은 데이터가 기존 클러스터와 충분히 가까우면(?) 클러스터로 편입시킨다고 했다.

그러면 얼마나 가까워야 충분히 가까운 것인가?

BFR 알고리즘에서는 Mahalanobis distance (마할라노비스 거리)를 제안한다. Mahalonobis distance는 다변량 분포에서 상관관계를 고려한 거리라고 생각하면 되겠다. (두 변수가 독립이라면 유클리드 거리와 동일하다.)

 

BFR 알고리즘에서 클러스터는 평균이다. 즉 BFR에서 Mahalanobis distance는 정규화된 유클리드 거리라고 해석해도 되겠다.

 

$d$차원 데이터에 대하여 주어진 데이터를 $x=[x_1, \dots, x_d]$, centroid를 $c=[c_1, \dots, c_d]$라 하면

\[ d_{M}(x, c) = \sqrt{ (x-c)^\top S^{-1} (x-c) } = \sqrt{\sum_{i=1}^{d} \left( \cfrac{x_i - c_i}{\sigma_i} \right)^2} \]

 

즉 $d(x,c)$가 특정 threshold보다 작으면 해당 클러스터에 편입시킨다.

이때 $d$차원 데이터가 가우시안이라면(BFR 알고리즘의 가정) $1\sigma=\sqrt{d}$임을 이용하여 threshold를 정할 수 있다.

Euclidean distance and Mahalanobis distance