BFR Algorithm

BFR Algorithm (Bradley-Fayyad-Reina)

K-means의 경우 데이터 집합이 메모리에 올라갈 수 있는 사이즈일 때만 사용 가능하기 때문에, BFR알고리즘은 K-means를 변형하여 매우 큰 데이터 집합을 다룰 수 있게 한다.

 

 

BFR 알고리즘은 유클리드 공간에서 정규분포(가우시안 분포)를 따른다고 가정하는데, 클러스터들이 centroid 주변에 분산되었다고 생각하면 된다. 

 

• 다른 차원에서의 표준 편차는 다양할 수 있다. → x축, y축으로 볼 때 각 그래프를 보는 관점이 다름
• 2차원 그래프에서는 표준편차가 높을수록 넓은 산 모양이고, 낮을수록 좁은 산 모양이다.

 

BFR 알고리즘의 과정은 다음과 같다.

 

1) 디스크에서 메인 메모리가 가득찰만큼 데이터를 읽는다

2) 이전 메모리의 대부분의 점들은 간단한 통계정보를 추출하고 디스크로 내보낸다

3) 초기 로드 시 최초의 k centroid를 선택한다

    : k개의 random point들을 잡고, 이전에 선택한 점에서 최대한 멀리 k-1개 점을 더 선택한다

 

Three Classes of Points

 

Discard Set (DS)

 

• centroid에 충분히 가까워 그 cluster에 할당될 수 있는 데이터 포인트의 집합
• 클러스터에 할당되고 나면 버려짐

 

Compressed set (CS)

 

• 어떤 centroid와는 가깝지 않지만 서로 그룹핑이 되는 데이터포인트의 집합
• 이러한 점들은 서로 합쳐지지만 하나의 클러스터로 할당되지는 않음 (summarized but not assigned)
• 이 점들도 summary 정보를 유지하고 버림

 

Retained set (RS)

 

• Compression set으로 할당되기를 기다리는 고립된 점들
• 이 점들은 DS와 CS 둘다 할당될 수 없으며 메인 메모리에 유지된다.

 

Summarizing Sets of Points

DS와 CS는 다음 정보를 유지한다.

• N = 클러스터 내 점들의 개수
• SUM = i번째 요소는 i차원에서 점들의 좌표의 합을 의미하는 벡터
• SUMSQ = i번째 요소는 i번째 차원에서 좌표의 제곱의 합을 의미하는 벡터

 

우리의 목표는 count, centroid, STDEV(표준편차)를 이용하여 clustering하는 것이며, 차원 수가 d라고 정의될 때 각 클러스터의 크기는 2d + 1 로 표현된다.

• N = count
• Sum / N = 각 차원의 평균
• ( SUMSQ / N ) - (SUM / N)^2 = 차원 i에서 DS의 분산(variance) → 분산의 제곱근의 합이 표준편차(Standard deviation)

 

그렇다면 왜 직접 표준편차와 centroid 값을 직접 유지하지 않는 것일까?

 

Processing the Memory-Load of Point 

 

1) centroid에 충분히 가까운 점들은 DS와 클러스터에 넣은 후 N, SUM, SUMSQ를 업데이트한 후 버린다

2) centroid에 가깝지 않은 점들을 모아서 cluster가 만들어지면 CS에 넣고, outlier의 경우 RS에 넣는다 (RS는 다음 반복에서 사용O)

3) 새로 만들어진 CS는 기존의 CS와 합칠 것인지 고려한다

4) DS와 CS에 할당된 점들은 메인 메모리에서 버린다 (written out to secondary memory)

5) 마지막 반복인 경우 CS와 RS를 다음과 같이 처리할 수 있다.

• CS와 RS를 outlier로 생각하고 클러스터링 하지 않는다
• RS안의 각 점을 가장 가까운 centroid cluster로 할당한다
• 각 CS를 가장 가까운 centroid cluster와 합친다

 

A Few Question...

앞서 BFR알고리즘이 메모리 로드하는 법을 살펴보았는데 centroid에 "충분히 가깝다"는 기준과 어떻게 CS끼리 합치는지에 의문점이 생기게 된다.

 

Q1 ) How Close is Close Enough ?

우리는 새로운 점을 클러스터에 넣거나 버릴 때의 기준이 필요한데, 이에 BFR은 두 가지 방법을 제공한다.

첫 번째는 현재 가장 가까운 centroid에 속한 점들에 높은 확률을 부여하는 것이다. 두 번째는 * Mahalanobis distance가 임계값 내에 존재하면 클러스터에 점을 할당하는 것이다.

 

 

* Mahalanobis distance 구하는 방법

 

 

 

 

 

 

 

 

 

 

1. y (i번째 point와 i번째 centroid 간의 거리)를 구한 후 표준편차로 나누어준다  

    → 여기서 y는 거리가 표준편차에 몇 배인지를 나타냄

 2. y의 제곱의 합을 구한다

 3. y에 루트를 씌운다

 

 

Mahalanobis distance를 이용하여 클러스터에 할당하는 방법

 

• 점과 centroid간의 Mahalanobis distance 계산하여 그 거리가 최소가 되는 cluster를 고른다
• 계산한 Mahalanobis distance가 임계값보다 작은 경우에만 클러스터에 p를 할당한다.

 

Q2 ) Should two Cs clusters be combined ?

두 CS를 합치는 기준은 간단하다. 합치는 subcluster의 분산을 구하여 그 분산이 임계값보다 작으면 합치면 된다. 우리는 N, SUM, SUMSQ를 유지하고 있기 때문에 분산값을 쉽게 구할 수 있게 된다.

 

 

Problem with BFR / K-means

• k-means와 BFR의 경우 클러스터가 정규분포를 따른다고 가정하는데, 일부 데이터들은 정규분포를 따르지 않는다.
• 타원이나 임의의(arbitrary) 모양이라면 잘 작동하지 않는다
• outlier에 취약하다