• 검색 결과가 없습니다.

7.1 군집분석

N/A
N/A
Protected

Academic year: 2022

Share "7.1 군집분석 "

Copied!
28
0
0

로드 중.... (전체 텍스트 보기)

전체 글

(1)

비즈니스 인텔리전스

를 위한

데이터마이닝

7장 군집분석 및 k-근접 이웃기법

(2)

7.1 군집분석

7.2 군집분석 방법

7.3 k-NN 예측기

7.4 k-NN 알고리즘의 장점과 단점

목차

(3)

7.1 군집분석(Clustering Analysis)

개요

다변량 자료를 각 특성의 유사성에 따라 여러 그룹(군집 또는 집락)으로 나누는 통계적 기법중의 하나.

군집의 개수, 내용, 구조가 파악되지 않은 상태에서 특성을 파 악하며, 군집들 간의 관계를 분석(탐색적 통계분석)

P개

N

P차원

N개의 점

(4)

7.1 군집분석(Clustering Analysis)

유사성

개체간의 유사성을 수량적으로 측정하는 데는 개체 간의 거리(distance)가 쓰임

자료행렬

p 개의 변수로 이루어진 n 개 개체(관측치)의 관측자료를 다음 과 같이 표현하자.

(5)

7.1 군집분석(Clustering Analysis)

거리의 척도

(6)

7.1 군집분석(Clustering Analysis)

군집분석방법

계층적 군집방법(Hierarchical Clustering Method) : 응집방 법과 분해방법이 있다.

최단 연결법(Single Linkage Method)

최장 연결법(Complete Linkage Method)

평균 연결법(Average Linkage Method)

중심 연결법(Centroid Linkage Method)

중위수 연결법(Median Linkage Method)

Ward의 방법

비계층적 군집방법(Non-Hierarchical Clustering Method)

K-means Clustering

Fuzzy K-means Clustering

신경망 응용 Clustering

(7)

7.1 군집분석(Clustering Analysis)

최단 연결법(Single Linkage Method)

두 군집 U 와 V 사이의 거리 d (UV)를 각 군집에 속하는 임의의 두 개체들 사이 의 거리 중 최단거리로 정의하여 가장 유사성이 큰 군집을 묶어 나가는 방법

최장 연결법(Complete Linkage Method)

두 군집 U 와 V사이의 거리 d UV를 각 군집에 속하는 임의의 두 개체들 사이의 거리 중 최장거리로 정의하여 가장 유사성이 큰 군집을 묶어 나가는 방법

최단 연결법이 고립된 군집을 찾는데 유용하다면, 최장연결법은 군집들의 응집 성에 중점

Average Linkage Method

군집과 군집사이의 거리를 다른 군집에 속하는 모든 객체들 간 거리의 평균

Centroid Method

두 군집의 Centroid(중심)간의 거리

(8)

7.1 군집분석(Clustering Analysis)

비계층적 군집방법

계보적으로 군집을 형성시키지 않고 개체들을 몇 개 의 군집으로 구분

초기에 부적절한 병합(분리)이 일어났을 때 회복 가능

군집의 수를 사전에 정의하는 경우가 많음

개체의 수가 많을 때 유용

(9)

7.1 군집분석(Clustering Analysis)

K-means Clustering

거리 행렬을 필요로 하지 않으므로 규모가 큰 자료에 적용이 용이

단계마다 어느 군집에 할당된 개체의 소속이 변하지 않는 계층적 군집법과는 달리 매 단계마다 개체가 할 당되는 군집이 다를 수 있다.

K-nearest neighbor

이웃 : 서로 가까이 있는 레코드들의 행위는 유사하다 .

임의의 레코드에 있는 예측값에 대하여 과거 데이터 베이스에서 이와 유사한 예측변수 값들을 찾아 가장 가까운 K개의 레코드의 값의 평균을 예측 값으로 사 용하는 것

(10)

7.2 군집분석 방법

A good clustering method will produce high quality clusters with

high intra-class similarity

low inter-class similarity

The quality of a clustering result depends on both the similarity measure used by the method and its

implementation.

The quality of a clustering method is also measured by its ability to discover some or all of the hidden patterns.

(11)

Data matrix

(two modes)

Dissimilarity matrix

(one mode)

xnp nf ...

x n1 ...

x

...

...

...

...

...

xip if ...

x i1 ...

x

...

...

...

...

...

x1p 1f ...

x 11 ...

x

0 ...

) 2 , ( )

1 , (

: :

:

) 2 , 3 ( )

...

n d n

d

0 d

d(3,1

0 d(2,1)

0

7.2 군집분석 방법

(12)

The K-Means Clustering Method

Given k, the k-means algorithm is implemented in 4 steps:

Partition objects into k nonempty subsets

Compute seed points as the centroids of the

clusters of the current partition. The centroid is the center (mean point) of the cluster.

Assign each object to the cluster with the nearest seed point.

Go back to Step 2, stop when no more new assignment.

7.2 군집분석 방법

(13)

The K-Means Clustering Method

Example

0 1 2 3 4 5 6 7 8 9 10

0 1 2 3 4 5 6 7 8 9 10

0 1 2 3 4 5 6 7 8 9 10

0 1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

7.2 군집분석 방법

(14)

Hierarchical Clustering

Use distance matrix as clustering criteria. This metho d does not require the number of clusters k as an inp ut, but needs a termination condition

Step 0 Step 1 Step 2 Step 3 Step 4

b

d c

e

a a b

d e

c d e

a b c d e

agglomerative (AGNES)

divisive

7.2 군집분석 방법

(15)

7.3 k -NN 분류기 (범주형 결과값)

K-최근접이웃기법(K-nearest neighbor)의 기본사상은 분류하고자 하는 새로운 레코드와 유사한 학습용 데이터 집합에 있는 k개의 관찰치를 확인하는 것이다.

그런 다음에 이러한 유사(인접)한 레코드들을 사용하여 새로운 레코드를 이들 이 웃한 자료들 중에서 우세한 집단으로 분류한다. 새로운 레코드에 대한 예측변수 들의 값은 로 표시한다. 예측변수의 공간에서 분류되는 레코드 와 유사하거나 가까이에 있는 레코드들, 즉 에 근접한 값을 가지 는 레코드들을 학습용 데이터에서 찾는다. 그 다음에는 이러한 근사 레코드들이 속하는 집단을 분류하고자 하는 레코드의 집단으로 할당한다.

여기서 가장 중요한 문제는 예측변수값에 기초하여 레코드들 사이의 거리를 어떻 게 측정하는가에 있다. 거리를 계산하는 가장 일반적인 방법은 유클리드

(Euclidean) 거리이다. 두 레코드 와 사이의 유 클리드 거리는 다음과 같다.

(X X1, 2,...,Xp)

1, 2,..., p X X X

(x1 u1) (2 + x2 u2)2 + + (xp up )2

1, 2, , p

x x x u u1, 2,,up

(16)

k의 선택

K는 새로운 레코드를 분류하는 데 사용되는 근접 이웃의 수이다.

K=1은 하나의 가장 근접한 레코드를 사용한다는 의미이다.

K=5는 5개의 가장 근접한 레코드를 사용한다는 의미이다.

전형적으로 k의 값은 검증 데이터에서 가장 낮은 오류율 을 가진 것을 선택한다.

(17)

예제 3: 승차식 잔디깍기 기계

어느 승차식 잔디깍기 기계 제조회사는 한 도시의 주거 세대들을 잔디깍기 기계를 구입할 가능성이 있는 세대와 구매 가능성이 없 는 세대로 분류하는 방법을 찾고자 한다. 예비의 무작위 표본은 그 도시의 12명의 소유자와 12명의 비소유자로 출발한다(표 7.1 참조).

우선, 데이터를 학습용 데이터(18개의 주거 세대)와 평가용 데이 터(6개의 주거 세대)로 분할한다.

(18)

예제 3: 승차식 잔디깍기 기계

(19)

예제 3: 승차식 잔디깍기 기계(계속)

(20)

k의 선택

k>1인 k를 선택하는 것의 장점은 k가 큰 값을 가질수록 학습용 데이 터에 존재하는 잡음으로 인해서 발생하는 과적합화의 위험을 줄여주 는 잡음의 평활화가 나타난다.

k가 너무 작으면 데이터의 잡음을 적합시킬 수 있다. 그러나, k가 너 무 크면 k최근접이웃 알고리즘의 가장 중요한 장점인 데이터의 지역 적 구조를 파악할 수 있는 능력을 놓칠 수 있다.

최대의 k값은 n(=학습용 데이터 집합의 레코드의 수)이다. 이 사례 에서는 의 값에 관계없이 모든 레코드를 단순히 학습용 데이터에서 가장 다수인 집단으로 분류한다. 이러한 결과는 단순 규 칙의 결과와 일치한다.

(X X1, 2,..., Xp)

(21)

7.4 k-NN 예측기 (수치형 결과값)

IBk (Instance-based k)

분석가가 임의의 k를 선택하여 입력

(22)

7.4 k-NN 예측기 (수치형 결과값)

평가 방법 선택과 목표변수 선정

(23)

7.4 k-NN 예측기 (수치형 결과값)

결과

(24)

7.4 k-NN 예측기 (수치형 결과값)

리프트 도표와 ROC곡선

(25)

7.4 k-NN 예측기 (수치형 결과값)

k-NN의 아이디어는 연속형의 값을 예측하는 것(다중 선형회귀모형 의 경우처럼)으로 쉽게 확대될 수 있다. 집단을 결정하기 위해서 근 접이웃 레코드들의 다수 집단을 선택하는 대신에 예측치를 결정하기 위해 k개의 최근접이웃 레코드들의 평균 반응값을 선택한다.

대체로 이 평균값은 가중평균값이 사용되며 예측이 요구되는 레코드 로부터 거리가 멀어질수록 이들 레코드의 반응값에 대한 가중치는 줄어들게 된다.

(26)

7.4 k-NN 알고리즘의 장점과 단점

장점

모형의 단순성과 더불어 파라미터에 대한 가정이 거의 없다는 것이다.

충분히 큰 학습용 집합이 존재 할 때 이 기법의 성과는 매우 높은 성과 를 나타낸다. 특히 다수의 예측변수값의 조합을 통해 각 집단이 특징지 워질 때 그러하다. 예를 들어 비행기 연착 사례에서 연착 비행기 및 정 시도착 비행기를 결정하는 요인인 항공기-도착지-출발시각 등의 다수 요인간의 조합이 가능하다.

(27)

7.4 k-NN 알고리즘의 장점과 단점(계속)

단점

첫째, 회귀모형과 같은 파라미터기반 모형의 경우처럼 학습용 데이터로 부터 파라미터를 추정하기 위한 시간이 필요하지 않지만, 대규모의 학습 용 집합에서 최근접이웃들을 찾는데 드는 시간은 매우 클 수 있다. 이러 한 어려움을 극복하기 위한 주요 해결방안들은 다음과 같다.

주성분분석과 같은 차원축소 기법을 이용하여 축소된 차원으로 적용됨으로 써 근접이웃들에 대한 거리를 계산하는데 필요한 시간을 줄일 수 있다.

최근접이웃을 확인하는데 걸리는 시간을 빠르게 하기 위해 검색 나무와 같 은 상세한 데이터 구조를 사용하는 것이다. 이 접근방법은 종종 최대에 가까 운 근접한 이웃들을 허용하여 속도를 향상시킨다.

최근접이웃을 검색하는 시간을 빠르게 하기 위해 학습용 데이터 중에서 중 복 되거나 거의 중복에 가까운 데이터들을 제거하는 것이다. 일례로는 모두 동일한 집단에 속하는 레코드들로 둘러 쌓여 있기 때문에 분류에 대한 영향 을 미치지 않는 학습용 집합에 있는 레코드들을 제거하는 것이다.

(28)

7.4 k-NN 알고리즘의 장점과 단점(계속)

단점(계속)

둘째, 예측변수의 갯수 p가 증가함에 따라서 이에 필요한 만큼 학 습용 집합에서 요구되는 레코드의 수는 기하급수적으로 크게 증 가한다.

학습용 집합의 크기가 p에 따라서 기하급수적으로 증가하지 않는다 면 최근접이웃과의 예상거리는 p가 커짐에 따라서 급격하게 증가하 게 된다. 이러한 현상은 모든 분류, 예측 및 군집 분석에 관련된 기본 적인 문제로서 차원의 저주(curse of dimensionality)로 불리운다.

이것은 곧 예측변수중 일부를 선택하는 방법을 통하거나 주성분분석, 특이값 분해(singular value decomposition), 그리고 요인분석과 같 은 방법을 이용하여 예측변수들을 결합시킴으로써 예측변수들의 공 간 차원을 줄이려고 노력하는 이유이다. 인공지능관련 문헌에서는 차 원축소는 종종 요인선택(factor selection) 또는 특성추출(feature extraction)로 불리운다.

참조

관련 문서