[Data Mining] 8. Subspace Clustering - Density Based Method

◉ Curse of Dimensionality 

 

Subspace Clustering을 해야하는 이유는 무엇일까?

 

Data들의 Dimension (데이터의 attribute 개수)이 커지면 커질수록, 각 Data 들 간의 차이는 모두 비슷해진다. 이것을 Curse of Dimesionality라고 한다. 

 

Raymond	M	Hong Kong	170	computer
Sidney	M	Seoul	170	violin
Justin	F	Hong Kong	180	flute

 

위 데이터를 보았을때, 성별만 보면, Raymond, Sidney를 하나, Justin을 하나 이렇게 클러스터를 지을 수 있다.

하지만 전체 데이터를 모두 고려해보면, Raymond - Sidney 나 Raymond-Justin 이나 Sidney - Justin 이나 모두 비슷한 Euclidean distance를 가지고 있어서, 정확한 클러스터링이 어렵다.

 

따라서, 우리는 클러스터링시에, 차원을 낮추어 클러스터링하는 Subspace Clustering 기법이 필요하다.

 

Subspace Clustering 에는 크게 3가지 방법이 있다.

 

1. Density Based method,

 

2. Entropy Based Method,

 

3. Transformation Based Method

 

하나씩 차근히 살펴보자.

 

◉ Subspace Clustering

 

 두개의 Column을 기준으로 Cluster을 형성했을때, 어떤 Attribute에서는 Cluster 성격을 띄우지만 다른 Attribute에서는 Cluster의 성격을 띄우지 않는 경우가 있다. 아래와 같이, History 점수는 분산되어있지만, Computer 점수는 특정 구역에 모여있다.

Subspace Clustering 감 잡기

그래서 아래와 같이 각 데이터들을 관심있는 축으로 내려버린다. 

Subspace Clustering

 

 

 

 

 

◉ Subspace Clsutering - Density Unit based Method

 

크게 두가지 Step으로 이루어져있다.

 

Step 1 : Dense 한 부분을 찾는 과정

 

Step 2 : Step1 에서 찾은 부분들이 인접하다면, 붙여서 Cluster 을 형성하는 과정.

 

 

 - Step 1 

Property : N 차원에서 High Density 라면, N-1 차원에서도 분명 High Density 이다. 

 

위 Property 를 역이용해서 아래와 같은 전제에서 Apriori algorithm을 적용할 수 있다.

 

➤ 1 차원에서 High Density인 요소들로 시작해서 Apriori Algorithm을 돌리면, 모든 차원의 High Density 부분을 찾아낼 수 있다.

 

Threshold 는 User defined variable 이다. 아래 예시에서는 T=20%로 한다. 

 

Density unit based method 1

총 10개의 Data 중 T=20% 보다 큰 그리드를 클러스터라고 칭할 수 있다.

 

하지만 위 그림에서 어떤 Subspace(Age/Income)이 위에서 정한 Cluster에 상응하는 Cluster인지는 모른다.  

 

따라서 데이터들을 각 축으로 Project 해본다.

 

Density based approach 2

각 축에 project 했을때, 그리드에서 T=20%가 넘으므로, Income, Age에서도 모두 Cluster을 형성한다고 말할 수 있다.

 

 

이 방법은 앞에서 Large Item set을 찾을때 사용했던 Apriori approach 를 동일하게 사용해서 적용할 수 있다.

 

 

Apriori method in Density based approach

개별 Subspace 에서 시작해서, Dimesion을 하나 하나 올려가며, 어느 차원까지 Cluster을 형성할 수 있는지 알 수 있게된다. 

 

Question? 

 하지만, 데이터베이스에서 많은 속성들 중, 연산을 하는 attribute의 순서에 따라서 결과가 달라질거같은데....?

=> No, L1 계산시에 Database 에 있는 모든 attribute들을 다 계산한다. => 헷갈리지말자, 하지만 Database update할때 다시 다해야될듯?

 

- Step 2 

 

Apriori Algorithm 을 사용해서 모든 High Density 요소들을 얻을수 있었다.

 

이제 그 요소들이 인접하면 붙여서 Cluster 을 만들고, 인접하지 않는다면 개별 Cluster로 분류한다.