- 데이터마이닝 특론 보고서 -

대용량 데이터를 처리하기 위한 EM Survey

제출자

이름 : 김완섭

학번 : 00344026

* 내용

1. 서론

2. 군집 알고리즘 일반

3. K-Means 군집 알고리즘

3.1 K-Means Overview

3.2 K-Means 설명

3.3 K-Means 예제 적용

4. EM(Expectation Maximization) Algorithm

4.1 EM Overview

4.2 EM Detail

5. Scalable EM Alorithm

6. References

1. 서론

군집화 기법(Clustering)은 데이터마이닝의 주요 기법 중 하나로서 많은 데이터들을 비슷한 성격의 데이터들로 구분하는 알고리즘이다. 분류 알고리즘과 달리 군집화는 비교사(Unsupervised) 알고리즘에 속한다. 군집 알고리즘으로 대표적으로 사용되는 알고리즘으로서 K-Means 알고리즘과 EM(Expectation Maximization) 알고리즘을 들 수 있다. K-Means와 EM은 반복적인 모델 정제 과정을 통해 최적의 군집을 찾는 다는 면에서 유사하다. 그러나 K-Means 알고리즘이 데이터 간의 거리를 계산할 때 유클리디언(Euclidean) 거리 계산 방법을 사용하는 것과는 달리 EM은 통계적인 방법을 사용하므로 EM 알고리즘이 더욱 효과적인 기능을 제공하여 많이 사용된다.

그러나 최근 데이터의 크기가 증가하면서 기존의 메모리 기반 알고리즘은 한계를 가진다. 기본적인 K-Means, EM 알고리즘은 모든 데이터를 메모리에 상주시키고 작업하는 것을 기본개념으로 하기 때문이다. 또한 수행과정에서 원본 데이터를 자주 스캔(Scan)하는 과정으로 인해 수행 시간이 매우 오래 걸리거나 메모리 수행 중의 문제가 정상적인 수행이 어려운 경우가 많다.

본 Survey에서는 기본적인 K-Means와 EM 알고리즘에 대해서 설명하고 대용량 데이터를 처리하기 위한 EM 알고리즘인 SEM(Scalable EM) 알고리즘에 대해서 설명하고자 한다. K-Means 알고리즘과 EM 알고리즘은 매우 많이 언급되고 활용되는 알고리즘이기 때문에 본 문서에서 설명을 위해 가능한 자세히 설명하였고 마지막 부분에서 대용량 처리를 위한 알고리즘을 설명한다.

Datamining 교제의 Clustering 파트를 분석하였고, 대용량을 처리하기 위한 내용은 논문을 참고하였다.

2. 군집 알고리즘 일반 (Clustering Algorithm Overview)

군집은 같은 군집 내의 객체들과는 비슷하고, 다른 군집의 객체들과는 상이한 데이터 객체들의 집합이다. 지금까지 많은 군집 알고리즘들이 제안되었다. 군집 알고리즘들은 접근 방식에 따라 아래와 같은 종류로 구분될 수 있다. [참고. DM T&C]

∙ 분할 기법 (Partitioning method)

∙ 계층적 기법 (Hierachical method)

∙ 밀도기반 기법 (Density-based method)

∙ 격자기반 기법 (Grid-based method)

∙ 모델 기반 기법 (Model-based method)

∙ 분할 기법(Partitioning Method)는 n개의 레코드를 k개(k<=n)의 군집으로 분할한다. 이 때 각 군집은 적어도 하나의 레코드를 포함해야 한다. 또한 하나의 레코드는 하나의 군집에 포함되는 것을 기본으로 하나 통계적인 기법을 사용할 때는 하나의 레코드가 가중치를 가지고 여러 군집에 소속될 수 있다. 레코드가 하나의 군집에만 소속되는 것을 Hard Clustering이라고 하며, 레코드가 여러 군집에 소속되는 것을 Soft Clustering이라고 한다. K-Means, EM, Fuzzy K-Means 등의 알고리즘이 분할 기법에 속한다.

그림1. Hard Clustering	그림2. Soft Clustering

- 계층적 기법(Hierarchical method)은 주어진 레코드들을 계층적으로 군집화한다. 접근 방식에 따라 Allgomerative 방식과 Divisive 방식으로 구분된다. Allgomerative 방식은 초기에 모든 레코드들을 하나의 군집으로 시작하여 점차 묶어가는 방식을 사용하며, Divisive 방식은 초기에 전체 레코드셋을 하나의 군집으로 시작하여 이 군집을 나누는 방식을 사용한다. BRICH, CURE, Chameleon 알고리즘들이 계층적 기법에 속한다.

- 밀도기반 기법(Density-based method)는 밀도(density) 개념을 사용하여 군집을 수행한다. 이웃 레코드들의 밀도가 어느 정도 이상이 될 때 이 레코드들을 연결하는 방식으로 군집을 형성해 간다. 즉, 주어진 군집 내에서 각 데이터의 일정한 반경 안에 최소한 몇 개 이상의 레코드가 존재하는 가를 계산한다. DBSCAN, OPTICS 등의 알고리즘이 밀도기반 기법에 속한다.

- 격자기반 기법(Grid-based method)는 레코드의 공간을 격자구조로 분해한 후 각 격자에서 군집을 시작하고 그 후에 이들을 결합하는 방식을 사용한다. STING, CLIQUE, Wave-Cluster등의 알고리즘이 격자기반 기법에 속한다.

- 모델기반 기법(Model-based method)는 각 군집에 모델을 생성하고 각 모델에 적합한 데이터들을 포함시킨다. 이 방법에서는 데이터의 분포를 표현할 수 있는 질량함수를 사용하는 것이 보통이다. COBWEB 알고리즘이 모델기반 기법에 속한다.

이 문서에서 언급하고자 하는 K-Means 알고리즘이나 EM(Expectation Maximization) 알고리즘은 분할 기법에 속한다. 분할 기법(Partitioning methods)는 주어진 데이터들을 일정한 개수의 군집 K개로 분할하는 방법이다. 분할 기법은 분할 개수 k에 대하여 초기 분할을 생성한다. 그리고 분할을 향상시키기 위한 시도로 객체를 하나의 그룹에서 다른 그룹으로 이동시키는 반복직인 재-배정기법(iterative relocation technique)을 사용한다. 군집 결과를 평가하기 위한 기준(Cluster Validity) 같은 군집 안에 있는 객체들은 비슷하고, 다른 군집에 있는 객체와는 차이가 크도록 했는가를 평가하는 것이다.

3. K-Means 알고리즘

3.1 K-Means 알고리즘 일반

n개의 객체를 가진 데이터베이스와 k개의 군집의 수가 주어졌을 때 분할 알고리즘은 군집에 해당하는 k개의 분할(k<=n)을 만든다. 초기 군집은 임의로 생성되었기 때문에 좋은 군집이 아니지만 반복적인 정제과정을 통하여 최적의 모델을 찾는다. K-Means 알고리즘은 아래와 같다.

Input : The number of k and a database containing n objects

Output : A set of k clusters that minimize the squared-error criterion.

Method :

(1) arbitarily choose k objects as the initial cluster centers

(2) repeat

(3) (re)assign each object to the cluster to which the object is the most similar

based on the mean value of the objects in the cluster.

(4) update the cluster mean, ie, calculate the mean value of the object for

each cluster

(5) until no change;

[표1. k-means 알고리즘]

K-Means 알고리즘은 입력 값으로 K를 취하고 군집 내 유사성은 높고 군집끼리의 유사성은 낮도록 n개 객체들의 집합을 k개의 군집으로 분할한다. 군집 유사성은 군집의 중심점(Centroid)와 소속된 객체들과의 거리를 평균하여 측정한다.

K-Means 알고리즘은 군집의 중심점을 나타내는 값으로 임의의 k개를 선택한다. 남겨진 객체들은 선택된 k개의 중심점들과의 거리를 계산하여 가장 가까운 군집에 할당한다. 그리고 각 군집에 새로운 군집중심(평균)을 구한다. 이 과정을 중심점의 이동이 없을 때 까지 즉 중심점이 수렴할 때까지 반복한다. 일반적으로 제곱오차(squared-error) 기준이 사용되며 다음과 같이 정의된다.

.......... (식1)

여기서 E는 모든 데이터들의 제곱오차를 합한 값이다. p는 주어진 레코드를 나타내는 것이고, mi는 군집, Ci는 평균이다. 이러한 기준은 결과로 나온 k개의 군집을 가능한 압축 혹은 분리되도록 하는 것이다.

알고리즘은 제곱오차함수를 최소화하도록 k개의 분할을 만든다. 이 기법은 전체 데이터개수가 n이고, k가 군집의 수, t가 반복의 수 일 때 알고리즘의 복잡도가 O(nkt)이기 때문에 큰 데이터 집합을 다루는데 상대적으로 효율적이고 확장적용 가능하다. 그러나 K-Means 기법은 군집의 평균이 정의되어있을 때만 적용할 수 있다. 데이터가 범주형의 특성을 포함하고 있을 때의 적용될 수 없다. 사용자가 군집의 개수 k를 미리 정해야 하는 단점이 있으며 군집의 크기가 상이한 군집을 찾는 데에도 적절하지 않다. 게다가  작은 수의 데이터가 사실상 평균값에 영향을 미칠 수 있기 때문에 잡음 값(Noise)이나 이상치(Outlier) 데이터에 민감하고 적절하게 처리하지 못하는 단점이 있다.

3.2 K-Means 알고리즘 적용 예

K-Means 알고리즘을 간단한 예를 들어 설명하고자 한다. 예제로 사용할 데이터는 아래와 같다. 각 레코드는 하나의 회사의 정보를 의미한다. 필드는 2개로써 하나는 회사의 소득(Income)이고, 하나는 Brand Loyalty(로열매 지출액)을 의미한다. 표1의 데이터를 2차원 챠트로 보면 그림1과 같다. 그림을 통해 직관적으로 분석해보면 2차원 공간 상에서 상단 4개의 레코드들이 하나의 군집으로 묶이고 하단의 2개가 하나의 군집으로 묶이는 것이 적절함을 볼 수 있다. 상단 4개의 레코드는 수입(Income)이 낮으면서 Loyalty를 많이 지불하는 회사 특성이 있고, 하단 2개의 레코드는 수입이 높고 Loyalty를 적제 지불하는 회사 특성이 있음을 파악할 수 있다.

ID	Income	Brand loyalty
1	150	50
2	130	53
3	90	80
4	120	85
5	115	70
6	126	76

[표2] K-Means 예제 데이터

[그림3] 표1 데이터의 2차원 분포

K-Means의 첫 단계로 임의의 군집 중심을 선택한다. K=2로 하여 두개의 군집을 만들고자 한다. seed가 1번, 3번 레코드를 선택하였다. 이제 모든 레코드들에 대해서 군집 중심인 1번과 3번과의 거리를 계산하여 가까운 점으로 군집을 할당한다. 먼저 모든 레코드들과 거리를 계산하면 아래와 같다.

ID	ID1과의 거리	ID3과의 거리
1	0.0	67.1
2	20.2	48.3
3	67.1	0.0
4	46.1	30.4
5	40.3	26.9
6	35.4	36.2

[표3] 반복1에서의 중심점과의 거리 계산

[그림4] 군집의 재할당

표1에서 계산된 군집 중심과의 거리에 의하여 각 레코드들을 재할당하는 그림을 보여준다. 군집1에는 1,2,6 레코드가 포함되었고, 군집2에는 3,4,5 레코드가 포함되었다. 이제 할당된 레코드들을 평균하여 새로운 군집의 중심을 찾는다.

군집	군집1	군집2
소속개체	1, 2, 6	3, 4, 5
중심(Centroid)	(59.6, 135.3)	(78.3, 108.3)

[표4] 군집 중심 변경

[그림5] 데이터들의 재할당

표1에서 구해진 새로운 군집 중심으로 모든 레코드들을 재할당하면 그림1과 같이 군집의 형태가 변경된다. 이제 다시 군집의 중심을 계산해 보면 더 이상 군집 중심(평균)값의 변화(이동)이 나타나지 않기 때문에 K-Means 알고리즘은 여기서 종료하게 된다.

이 예제 데이터에서 K-Means 알고리즘의 단점에 대해서 언급하고자 한다. 만약 데이터에 회사의 주소라는 범주형 필드가 있다고 했을 때 이것을 처리해 줄 수 없다. 또한 Income이 원화 만원 단위로(W) 단위이고 Loyalty가 외화($) 단위로 저장된다면 Loyalty의 값의 범위가 큰 차이를 나타내기 때문에 Income은 무시되고 Loyalty에 의해서만 군집이 형성되는 문제가 있다. 또한 만약 소득이 300이고, Loyalty가 20인 새로운 데이터가 추가됐다고 했을 때 이러한 이상치 값(레코드)로 인하여 군집의 형태가 크게 변경되는 단점이 있다.

다음 장에서 소개하고자 하는 EM 알고리즘은 이러한 K-Means의 단점들은 많은 부분 보완하고 있다.

4. Basic EM 알고리즘

4.1 Basic EM 알고리즘

EM 알고리즘은 1958년에 Hartley에 의해서 처음 제안되었고 1977년에 Dempster에 의해서 체계화되어 된 군집 알고리즘이다. EM 알고리즘은 K-Means 알고리즘과 마찬가지로 초기 모델을 생성한 후 반복 정제과정을 통하여 모델을 최적화된 모델을 생성해간다. EM 알고리즘은 반복 정제 과정을 통하여 각 객체들이 혼합 모델(Mixture Model)에 속할 가능성(Probability)을 조정하여 최적의 모델을 생성해 간다.  K-Means 알고리즘에서는 유클리디언(Euclidean) 거리 함수를 사용하는 반면에 EM 알고리즘은 log-likelihood 함수를 사용하여 모델의 적합성을 평가한다. 즉, K-Means가 거리 기반 군집 방법인 것에 비하여 EM은 확률 기반 군집(Probability-based clustering)이라고 한다.

4.2 EM 알고리즘

EM 알고리즘은 분할 기법에 속하는 군집 알고리즘으로 K-Means 알고리즘과 사실상 유사한 접근 방식을 사용한다. 그러나 K-Means가 거리를 사용하여 적합도를 평가하는 것과 달리 EM 알고리즘은 확률을 사용하여 적합도를 평가하는 점이 가장 큰 차이점이다. 확률 기반 군집은 데이터의 분포에 대해 혼합 모델(Mixture Model)을 사용한다. 여기서 하나의 군집은 하나의 데이터 분포를 의미한다. 확률 기반 군집에서는 하나의 레코드가 여러 개의 모델에 속할 수 있다. 이 때 속하는 정도는 가중치(확률)로서 주어지게 된다.

4.2.1 Mixture Model

EM 알고리즘은 Finite Mixture Model 통계 개념에 기반하고 있다. Mixture 하는 것은 여러 개의 확률 분포를 혼합된 것을 의미한다. 군집의 개수가 k라고 하면 k개의 확률 분포를 갖는 것을 의미한다. EM 알고리즘에서는 각 레코드들은 여러 개의 확률 분포 모델(군집)에 속하는 가중치를 가지고 배정된다.

일반적으로 데이터들은 여러 개의 속성 필드들을 가지고 있다. 그래서 하나의 통계 모델은 각 속성들의 확률 모델들의 집합을 의미한다. 그러나 Mixture Model의 이해를 쉽게 돕기 위하여 간단한 데이터 셋을 가지고 설명하고자 한다.

예를 들어 다음과 같은 데이터들이 있다고 하자. 이 데이터는 “Data Mining, Morgan Kaufmann” 교제 220p의 예제 데이터를 사용한 것이다. 여기서 A, B는 클래스를 데이터의 클래스를 의미하는 것이다. 예를 들어 이 숫자가 수학점수를 의미한다고 하고 A, B는 서로 다른 반을 의미한다고 해보자.

A 51	B 62	B 64	A 48	A 39	A 51
A 43	A 47	A 51	B 64	B 62	A 48
B 62	A 52	A 52	A 51	B 64	B 64
B 64	B 64	B 62	B 63	A 52	A 42
A 45	A 51	A 49	A 43	B 63	A 48
A 42	B 65	A 48	B 65	B 64	A 41
A 46	A 48	B 62	B 66	A 48
A 45	A 49	A 43	B 65	B 64
A 45	A 46	A 40	A 46	A 48

[표5] Mixture Model 설명 데이터

이 데이터의 분포를 분석해 보면 A반의 수학점수는 평균이 50이고, 분산이 5인 것을 알 수 있다. 반면 B반의 수학점수는 평균이 65이고 분산이 2이다. 전체 데이터에서 클래스 A와 B가 차지하는 비율(확률)은 각각 0.6, 0.4이다. 이 것을 표로 분석한 것은 아래와 같다. 이것을 Finite Mixture Model 이라고 한다.

.......... (식2)

.......... (식3)

각 확률 모델은 데이터가 포아송 분포 또는 정규 분포를 따른다는 가정하에서 평균과 표준편차로 모델을 생성한다. (식2)은 모든 레코드들의 평균을 구하는 식이고, (식3)는  레코드들의 분산을 구하는 식이다. 분산을 구하는 식에서 n으로 나누지 않고 n-1로 나누는 것은 전체데이터가 아니라 샘플링을 했을 때에 통계학에서 사용하는 방법이다.

.......... (식4)

(식3)은 레코드 어떤 x가 주어졌을 때 그 레코드가 클래스 A에 속할 확률을 의미한다. 여기서 는 클래스 A에 대한 정규분포 함수를 의미한다.

.......... (식5)

(식4)는 주어진 데이터가 평균  , 분산  인 정규 분포를 따른 다고 했을 때 레코드 가 그 분포(클러스터)에 속할 가능성은 얼마인가를 계산하는 함수이다. (식4)를 그림으로 나타내면 아래 (그림5)과 같다.

[그림6] 평균  , 분산  인 정규 분포

그림에서 Y축은 로 x가 해당 분포에 속할 가능성(Probability)을 의미한다. 즉 x가 평균에 가까울 수록 높은 값을 가지게 된다. EM에서는 k 개의 정규분포 모델(군집)을 만들고 각 레코드들을 k 개의 정규 분포 함수에 적용하여 가장 가능성이 높은 것에 가중치를 높게 부여하는 개념을 사용한다.

[그림7] 정규분포 함수의 적용 예

위 그림은 데이터의 분포를 정규 분포식에 적용하는 것을 설명하는 그림이다. 그림1의 상단그림은 데이터의 분포와 정규 분포식이 적합하지 않을 경우이다. 이 경우 각 레코드들을 p(x) 함수에 적용시키면 결과적으로 작은 값들을 결과로 얻게 된다. 반면에 그림1의 하단 그림은 데이터의 분포가 주어진 정규분포에 대체로 적합한 경우이다. 이 데이터들을 밀도함수 p(x)에 적용하면 높은 값을 얻게 되는 것을 설명한다.

[그림8] EM의 밀도함수 모델의 변화 예

위 그림은 데이터가 군집을 5개로 하고 EM을 적용했을 때의 적합한 모델을 찾아가는 과정을 그림으로 보여준다. 초기에는 모델은 데이터의 분포에 적합하지 못하지만 반복(Iteration) 과정을 통하여 주어진 데이터에 적합한 모델을 찾아가는 것을 설명한다.

4.2.1 N차원 밀도함수 (N-Dimensional Probability Density Function)

위의 식1은 데이터의 속성을 1개만 고려했을 때의 확률함수를 의미한다. 데이터에서 속성의 개수가 N개 일때, 즉 N-Dimension 공간에서 활용하기 위해서는 각각의 확률함수를 결합하는 것이 필요하다. 아래와 식과 같이 각각의 확률 값들을 모두 곱(Product)하여 최종적인 확률밀도 함수를 사용할 수 있다.

.......... (식6)

밀도함수에서 차원의 수가 증가할수록 최종적인 밀도 함수 값은 작아지게 된다. 따라서 최종적인 가중치(Weight)로 사용하기 위해서는 이 값을 조정하는 것이 필요하다. 이 때 하나의 레코드가 k개의 군집에 속할 가능성의 합이 1이 되도록 하기 위하여 아래의 수식을 사용한다.

.......... (식7)

4.2.2 EM(Expectation Maximization) 알고리즘

아래 표는 EM 알고리즘을 설명한다.

Input : Cluster number k, a database, Stopping tolerance

Output : A set of k clusters with weight that maximize Log-likelihood function.

(1) Expectation Step

For each database record x,

Compute the membership probability of x in each cluster h = 1,...,k.

(2) Maximization Step

Update mixture model parameter (probability weight)

(3) Stopping criteria

If stop criteria is satisfied stop

Else set j = j+1 and goto (1)

[표6] EM 알고리즘

EM 알고리즘도 수행 전에 군집의 개수, k와 종료 조건으로 을 입력받는다. 알고리즘은 크게 E-Step과 M-Step으로 구분된다. E-Step (Expectation Step)에서는 k개의 확률 분포(군집)에 대하여 각 레코드들이 속할 확률을 계산하여 weight 로 변환하여 배정한다. 다음 M-Step (Maximization Step)에서는 모델을 업데이트 한다. EM에서의 모델은 정규분포를 가정하기 때문에 이 과정은 새로 배정된 레코드들의 평균과 표준편차를 변경한다. 이때 각 레코드들이 소석 정도(Weight)를 가지기 때문에 가중치를 고려하여 계산한다. 위 알고리즘은 설명하는 논문에 따라 약간씩 표현 방법이 다르다. 아래 표2와 같이 알고리즘을 기술할 수도 있다. 이해를 돕기 위해 추가한다.

(1) Initialization

- Assign random probability

(2) Maximization Step

- Re-create cluster model

- Re-compute the parameter (mean, variance)

(3) Expectation Step

- Update record's weight

(4) Stopping criteria

Calculate log-likelihood, If the value saturate, exit, else Goto Step 2

[표7] EM 알고리즘

4.2.3 초기 군집의 생성

EM 알고리즘은 초기 모델은 무직위로 생성한다. EM에서의 모델은 각 가중치를 갖는 데이터들의 집합을 의미한다. 이 데이터들의 평균과 분산을 계산하여 수식적인 모델을 생성하는 것이다. 아래 표는 군집의 개수가 k개 이고 레코드가 n개 일때 각 레코드들을 임의의 가중치를 부여하여 각 군집에 소속시킨 내용을 보여주고 있다.

ID	C1	C2	...	Ck
1	0.12	0.43	...	0.09
2	0.73	0.05	...	0.12
3	0.14	0.21	...	0.51
...	...	...	...	...
n	0.25	0.29	...	0.17

[표1] 임의로 생성된 가중치 모델

이 표에서 각 레코드들이 군집에 속할 가중치의 합은 1은 되도록 한다. 반복 과정을 통해서도 Likelihood 함수을 계산한 후 이 가중치로 변경할 때 이 값들의 합이 1이 되도록 해야 한다.

.......... (식8)

(식8)은 데이터를 k개의 군집으로 구분할 때 한 레코드가 각 레코드가 k개의 군집에 속할 가중치(Weight)의 합이 1이 되어야 함을 정의한다.

4.2.2 Likelihood Function

EM에서는 모델의 적합성을 평가하기 위해  Likelihood 함수를 사용한다. K-Means에서 유클리디언 거리를 계산하는 반면 EM에서는 Likelihood 함수를 사용하여 화률적인 적합성을 평가한다. EM 알고리즘은 Likelihood 값을 최대화하는 것을 목표로 한다. 반복과정을 수행함에 따라 Likelihood 값은 점차로 커지게 된다. 이 값의 변화가 어느 정도 이하로 줄어들게 되면 알고리즘을 종료한다.

E-Step과 M-Step을 반복하는 과정을 통해 Likelihood 값이 변경되는 것을 논문에서는 다음 그림으로 설명하고 있다. 이 그림은 설명을 돕기 위해 입력 데이터가 두개의 수치형 필드로 구성된 간단한 데이터를 적용했을 때의 그림을 보여준다.

[그림9] 반복1회	[그림10] 반복2회
[그림11] 반복3회	[그림12] 반복4회

그림9은 초기 모델의 모습을 보여준다. 그림10, 그림11, 그림12는 반복과정을 1회, 2회, 3회 거침을 통하여 모델이 데이터에 적합하도록 변경되고 있음을 시각적으로 보여준다. 그림9, 그림10의 초기 모양에서는 분산이 커서 넓게 퍼져있는 그래프를 그리는 반복 점차로 그림11, 그림12에서는 분산이 작아져서 확률 그래프가 좁고 높게 변경된 것을 확인할 수 있다.

"The Expectation Maximization Algorithm, 2001" 에서는 EM을 좀더 이하하기 쉽게 도식화하여 설명하고 있다.

[그림12] Likelihood function of two component

4.2.2 Log-Likelihood Function

EM은 종료조건을 평가하기 위해 Likelihood 값에 Log 함수를 적용한 Log-Likelihood 함수를 사용한다. log 함수를 사용하는 이유는 Likelihood 값이 일정값 수준으로 향상되면 수렴을 허용하기 위해서이다.

.......... (식9)

4.2.2 종료조건

EM 알고리즘은 위에서 정의한 Log-Likelihood Function 값이 일정한 값으로 수렴할 때 즉 값이 변화가 초기에 지정한 값보다 작아 질 때 종료한다. 아래 그림은 반복 횟수에 따라 Q값(Log-Likelihood) 값이 어떻게 변화되는 가를 보여준다.

[그림13] Log-Likelihood의 수렴 그래프

5. Scalable EM 알고리즘

5.1 대용량 처리의 필요성

군집 알고리즘에서 대용량 처리를 위한 변경을 요구된다. 기존의 군집 알고리즘은 여러 차례의 데이터베이스 전체를 스캔 과정을 거친다. 대용량의 데이터를 스캔하는 것은 시간이 많이 소요되는 작업이므로 이 횟수를 최대한 줄이는 것이 요구된다. 또한 기존의 알고리즘들은 메모리 기반으로 수행되기 때문에 시스템의 메모리를 처리용량을 초과하는 데이터베이스를 군집할 수 없는 문제가 있다. 이러한 문제를 해결하기 위해 보통 데이터를 샘플링하여 군집 알고리즘을 수행하는 방법을 사용한다. SEM 논문에서는 전체 데이터를 사용하면서 대용량 데이터를 처리할 수 있는 방법을 제안한다.

5.2 SEM 알고리즘

SEM 논문에서 제안하는 개념은 데이터는 크게 세 가지로 구분하여 다르게 처리하는 것이다.

∙ Retained set R

∙ Discard set B

∙ Compressed set C

- Retained set R  : 데이터의 군집에 포함할 성격이 불분명하여 아직 요약되지 못하고 메모리(버퍼) 상에 남아있어야 하는 데이터들

- Discard set B : 특정 클러스터에 속할 가능성이 확정적이어서 더 이상 유지해야할 필요가 없는 데이터들.

- Compressed set C : 메모리(버퍼)에 유지되지만 원본 그대로 저장하지 않고 유사한 성격을 갖는 데이터들을 압축하여 저장한다. 하나의 중심되는 레코드를 저장하며 가중치를 높여서 저장하는 방식을 취한다. 데이터를 1차, 2차 압축하는 과정을 거친다.

(1) Set  so that memory for  equals the buffer size. Set

(2) Apply ExEM to , updating  to

(3) Partition singleton data points in

(3.1) Indentify subsets updating single Gaussian components

Augment  incorporating sufficient statistics from these subsets,

remove subset from

(3.2) Identify subsets updating Gaussian components as as group.

Augment  incorporating sufficient statistics from these subsets,

remove subsets from

(4) Stopping Criteria

If j > 1 and , terminate. If , terminate

(databased D has been fully scanned). Otherwise set , go to 1.

[표8] SEM 알고리즘

6. References

1) The Expectation Maximization Algorithm, Frank Dellart, Febraray 2002.

2) Scaling EM(Expectation Maximization) Clustering to Large Databases

Fayyad, October 1999.

3) A Gentle Tutorial of the EM Algorithm and its Application to Parameter

Estimation for Gaussian Mixture and Hidden Markov Models.

4) Data Minining, Witten Frank, Morgan Kaufmann

5) Data Mining Tutorial, Roiger, Geatz.

6) DataMining Concept and technology, Han Kamber.