Clustering
Distance
거리는 어떤 사물이나 장소가 공간적으로 얼마나 멀리 떨어져 있는가를 수치로 나타낸 것
Euclidian Distance
Manhattan Distance
Cosine Distance
두 Vector들 사이의 각도를 계산함
Vector의 크기는 무시하되 Vector의 방향의 차이만 계산함
Cosine Distance는 어떤 개수의 차원에도 적용이 가능하여 흔히 다차원의 양수 공간에서의 유사도 측정에 자주 이용됨
(eg 정보 검색 및 텍스트 마이닝 분야에서, 단어 하나 하나는 각각의 차원을 구성하고 문서는 각 단어가 문서에 나타나는 횟수로 표현되는 Vector 값을 가짐. 이러한 다차원 공간에서 Cosine Distance는 두 문서의 유사를 측정하는 매우 유용한 방법으로 사용됨)
Cosine Distance는 Data mining 분야에서 Clustering 들 간의 응집도를 측정하는 방법으로도 사용됨
Minkowski Distance
m차원 민코프스키 공간에서의 거리
m = 1일때 맨하탄 거리와 같고 m = 2일 때 유클리디안 거리와 같음
m이 정수는 아니어도 되지만 반드시 1보다는 커야 함
Chebychev Distance
한 점으로부터 인접한 8개의 모든 셀들을 같은 거리로 처리하는 것
맨하탄은 인접한 4개 셀을 같은 거리로 처리함
Levenshtein Distance
Edit Distance (편집거리) 라고도 불림
두 개의 문자열 A, B가 주어졌을 때 두 문자열이 얼마나 유사한지를 알아낼 수 있는 알고리즘
: 문자열 A가 문자열 B와 같아지기 위해서는 몇 번의 연산을 진행해야 하는지 계산하는 것
Mahalanobis Distance
다변량 데이터에서 분포의 형태를 고려하여 거리를 계산함
변수들간 모두 독립적이고 Variance가 1로 정규화된다면 마할라노비스 거리는 유클리디안 거리와 같아짐
K-Means
Clustering은 비지도학습에 속하며 K-Means 알고리즘은 데이터를 K개의 군집으로 묶어주는 알고리즘
Step 1: 군집의 개수 K 설정
Step 2: 초기 중심점 설정
Step 3: 데이터를 군집에 할당 (배정)
Step 4: 중심점 재설정 (갱신)
Stpe 5: 데이터를 군집에 재할당 (배정)
Step 1: 군집의 개수 K 설정
데이터를 준비한 뒤 가장 먼저 해야 할 것은 사람이 군집의 개수를 결정해야 함
K-means 알고리즘의 한계점 중에 하나
(군집의 개수 설정을 어떻게 하냐에 따라 결과가 크게 달라지며, 터무니 없는 결과가 나올 수 있음)
군집의 개수를 몇 개로 설정할 것인가?
- Rule of thumb
- Elbow Method
- 정보 기준 접근법 Information Criterion Approach
Step 2: 초기 중심점 설정
K개의 초기 중심점 (Center of Cluster, Centroid)을 설정하는 단계
K-means 알고리즘은 초기 중심점으로 어떤 값을 선택하는가에 따라 성능이 크게 달라짐
중심점 설정하는 방법
- Randomly Select
- Maually assign
- K-means ++ (실제 사용되는 초기 중심 값 설정하는 방법)
Step 3: 데이터를 군집에 할당 (배정)
거리 상 가장 가까운 군집 (중심점)으로 주어진 데이터를 할당 또는 배정하는 단계
거리 측정 방법은 일반적으로 유클리디안 거리로 측정
Step 4: 중심점 재설정 (갱신)
C1, C2, C3 각각의 중심점은 그 군집의 속하는 데이터들의 가장 중간 (평균)에 위치한 지점으로 재설정
중심점 C1은 데이터 1, 2의 평균인 지점으로 C2는 데이터 3, 4의 평균인 지점으로, 중심점 C3는 데이터 5, 6의 평균인 지점으로 갱신됨
Step 5: 데이터를 군집에 재할당 (배정)
더 이상 중심점의 이동이 없을 때까지 Step 4와 Step 5를 반복함
Hierarchical Clustering
K-means와 달리 군집 수K를 사전에 정하지 않아도 학습을 수행할 수 있음
개체들이 결합되는 순서를 나타내는 트리 형태의 구조인 덴드로그램 (Dendrogram)
덴드로그램 생성한 후 적절한 수준에서 트리를 자르면 전체 데이터를 몇 개 군집으로 나눌 수 있게 됨
Step 1: HC를 수행하려면 모든 개체들 간 거리 Distance나 유사도 Similarity가 이미 계산되어 있어야 함
Step 2: 거리가 가까운 관측치들끼리 차례대로 군집으로 묶음
Step 3: 군집과 데이터 (군집) 간 거리를 다시 계산함
유사도 테이블 업데이트 후 묶어줌
Step 4: 분석 대상 관측치가 하나도 없으면 학습을 종료
K-means와 달리 사전에 군집수 k를 설정할 필요 없음
덴드로그램의 최상층을 끊어주면 A,D,C와 B 두 개 군집이 도출 됨
두번째 층을 끊으면 A,D와 C,B 이렇게 3개의 군집이 나옴
HC의 경우 계싼 복잡성은 O(n^3)으로 K-means보다 무거운 편임
Spectral Clustering
[Graph구축 → Graph Edge Cut]
Spectral Clustering을 수행하기 위해서는 데이터를 그래프로 변환하기 위해 인접행렬 (Adjacency Matrix)을 만들어야 함
인접행렬을 만들 때 보통 가우시안 커널 (Gaussian kernel)을 많이 사용함
무방향 가중치 그래프 (Undirected Weighted Graph)를 사용함
Grahp 구축
- Fully connected graph란 모든 노드 (데이터)가 엣지로 연결돼 있는 그래프를 칭함
- ε-neighborhood graph란 거리가 ε보다 가까운 엣지들만 살리고 나머지는 끊어버린 그래프
- K-NN Graph는 각 노드 주변 K개 이웃들만 엣지로 연결하고 나머지 엣지는 끊어놓은 그래프
- ε-neighborhood graph는 노드의 밀도가 높은 지역에선 엣지가 지나치게 많이 발생하고, 밀도가 낮은 지역에선 엣지가 하나도 없는 노드가 발생
- K-NN Graph는 끊기는 노드가 발생하진 않지만, 군집이 극단적으로 멀리 떨어져 있는 경우 군집과 군집 사이는 연결되지 않는 경우가 발생
- 일반적으로 그래프를 구축할 때는 ε-neighborhood graph를 먼저 구축한 뒤 K-NN Graph를 적용하여 엣지가 없는 노드도 연결하는 방식을 씀
- 그럼에도 불구하고 군집 사이가 너무 멀어서 연결이 안되는 경우 발생할 수 있는데, 이럴 때는 Minimun spanning tree 방법도 자주 사용
(Spanning Tree는 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안됨)
Graph Cut 지표
Graph Cut 은 Graph를 특정 기준에 의해 두 개 이상의 Subgraph로 나눈 것을 의미함
Subgraph가 바로 Spectral Clustering의 학습 결과물인 군집이 되는 것
- Cut (A, B): A에서 B로 향하는 엣지들의 가중치 합 (0.1 + 0.2 = 0.3)
- Cut (A, A): A에서 A로 향하는 엣지들의 가중치 합 (0.8 + 0.8 + 0.6 = 2.2)
- Cut (B, B): B에서 B로 향하는 엣지들의 가중치 합 (0.8 + 0.8 + 0.7 = 2.3)
- Vol(A): A에 속한 노드에 연결된 엣지드르이 모든 가중치 합
[0.8+0.6+0.1] + [0.8+0.8] + [0.2+0.6+0.8] = 4.7 → Vol(A) = Cut(A,A) + Cut(A,B)
- Vol(B): B에 속한 노드에 연결된 엣지들의 모든 가중치 합
[0.1+0.8+0.8] + [0.8+0.7] + [0.2+0.7+0.8] = 4.9 → Vol(B) = Cut(B,B) + Cut(A,B)
- Minimum Cut Method
Graph를 A와 B라는 Subgraph로 나눌 때 끊어지는 엣지들의 가중치가 최소가 되도록 하는 방법
DBSCAN
K-means나 Hierarchical Clustering의 경우 군집 간의 거리를 이용한 Clustering 기법
DBSCAN은 밀도 기반의 기법이며 세밀하게 몰려 있어서 밀도가 높은 부분을 Clustering하는 기법
Density-Based Spatial Clustering of APplications with Noise
- 점 p가 있다고 할 때, 점 p에서부터 거리 e(epsilon) 내에 점이 m (minPls)개 있으면 하나의 군집으로 인식함
따라서 e와 m이 Hyperparameter
K-means와 같이 Cluster의 수를 정하지 않아도 됨
Cluster의 밀도에 따라 Cluster를 서로 연결하기 때문에 기하학적인 모양을 갖는 군집을 잘 찾을 수도 있음
DBSCAN을 활용하여 이상치를 발견할 수 있음
DBSCAN은 Cluster 결과가 이상치에 영향을 받지 않음
다양한 모양의 Cluster 패턴도 잘 잡아 낼 수 있음
구현이 비교적 쉬움
고차원 데이터에 대해서 잘 작동하지 않음
Sparse Data에 대해 결과가 좋지 못함
**DBSCAN (Density-Based Spatial Clustering of Applications with Noise)**은 **밀도 기반 클러스터링** 알고리즘으로, 밀집된 데이터 포인트를 클러스터로 묶고, 밀도가 낮은 지역의 포인트를 노이즈로 간주하여 처리하는 클러스터링 기법입니다. 다른 클러스터링 알고리즘과 달리, **데이터의 밀도**에 기반해 클러스터를 형성하고, 데이터의 **비선형 분포**도 잘 처리할 수 있다는 장점이 있습니다.
DBSCAN은 특히 **비정형 클러스터**나 **잡음(noise)**가 포함된 데이터에서 잘 작동하며, 클러스터의 모양을 가정하지 않고 클러스터링을 수행할 수 있는 특징이 있습니다.
### DBSCAN의 주요 개념:
#### 1. **밀도(density)** 개념:
DBSCAN은 데이터 포인트의 밀도를 기준으로 클러스터를 형성합니다. 밀도는 각 포인트 주변에 얼마나 많은 다른 포인트가 있는지에 따라 결정됩니다.
- **Epsilon (ε)**: 두 점 간의 최대 거리를 나타내는 매개변수입니다. 이 거리가 가까운 점들은 같은 클러스터에 속할 가능성이 높습니다.
- **MinPts**: 하나의 클러스터가 되기 위해서 최소한으로 필요한 데이터 포인트 수입니다. 이 수보다 많은 데이터 포인트가 일정 거리(ε) 내에 있으면 그 데이터 포인트는 **핵심점(core point)**로 분류됩니다.
#### 2. **핵심점(Core Point)**, **경계점(Border Point)**, **노이즈 포인트(Noise Point)**:
DBSCAN은 데이터 포인트를 세 가지로 구분합니다.
- **핵심점(Core Point)**: 반경 ε 이내에 **최소 MinPts 이상의 이웃이 있는** 데이터 포인트입니다. 이 포인트는 클러스터의 중심이 될 수 있습니다.
- **경계점(Border Point)**: 반경 ε 이내에 **MinPts 이하의 이웃**을 가지지만, 다른 핵심점의 이웃에 포함된 데이터 포인트입니다. 경계점은 클러스터의 외곽에 위치합니다.
- **노이즈 포인트(Noise Point)**: 핵심점이나 경계점에 속하지 않으며, 밀도가 낮은 곳에 위치한 포인트입니다. 이 포인트는 어떤 클러스터에도 속하지 않고 **잡음**으로 간주됩니다.
#### 3. **작동 원리**:
DBSCAN의 작동 방식은 다음과 같습니다.
1. 임의의 데이터 포인트를 선택하고, 그 주변의 **ε** 거리 내에 얼마나 많은 이웃 포인트가 있는지 확인합니다.
2. 이웃 포인트가 **MinPts** 이상이면, 해당 포인트를 핵심점으로 분류하고 클러스터 형성을 시작합니다. 해당 포인트를 중심으로 주변의 이웃을 확장하여 같은 클러스터에 포함시킵니다.
3. 해당 포인트의 이웃이 **MinPts** 미만일 경우, 해당 포인트는 노이즈로 간주됩니다.
4. 이 과정을 반복하여 모든 데이터 포인트를 방문하고, 클러스터와 노이즈를 완성합니다.
#### 4. **하이퍼파라미터**:
DBSCAN은 두 가지 주요 하이퍼파라미터가 있습니다.
- **Epsilon (ε)**: 두 점 사이의 최대 거리로, 이 거리가 클수록 더 넓은 범위의 포인트가 같은 클러스터에 속할 가능성이 높습니다. ε 값을 너무 작게 설정하면 클러스터가 잘 형성되지 않고, 너무 크게 설정하면 여러 클러스터가 하나의 클러스터로 병합될 수 있습니다.
- **MinPts**: 하나의 클러스터로 간주되기 위해 필요한 최소 포인트 수입니다. 일반적으로 **MinPts ≥ 차원의 수 + 1**로 설정하는 것이 권장됩니다. 데이터의 특성에 따라 적절한 값을 조정할 필요가 있습니다.
### DBSCAN의 장점:
1. **클러스터 수를 미리 설정할 필요가 없음**: K-means처럼 클러스터의 수를 미리 지정할 필요가 없으며, 데이터의 밀도에 따라 클러스터가 자동으로 형성됩니다.
2. **잡음 처리**: 데이터에 포함된 **잡음(noise)**나 이상값(outlier)을 자동으로 탐지하고 배제할 수 있습니다.
3. **비선형 클러스터**: DBSCAN은 **비선형적인 클러스터**를 잘 탐지할 수 있습니다. 즉, 구형이 아닌 다양한 형태의 클러스터를 찾는 데 유리합니다.
4. **확장성**: 매우 큰 데이터셋에 대해서도 효율적으로 작동하며, 밀도 기반으로 클러스터를 찾기 때문에 복잡한 데이터셋에서도 성능이 좋습니다.
### DBSCAN의 단점:
1. **ε와 MinPts에 민감**: 적절한 **ε**와 **MinPts** 값을 찾는 것이 중요합니다. 이 값들이 적절하지 않으면 클러스터가 잘못 형성되거나, 너무 많은 노이즈가 검출될 수 있습니다.
2. **밀도가 균일하지 않은 데이터에 취약**: 서로 다른 밀도를 가진 클러스터가 존재할 경우, DBSCAN은 이를 잘 구분하지 못할 수 있습니다. 예를 들어, 한 클러스터는 밀도가 높고, 다른 클러스터는 밀도가 낮을 경우 문제가 발생할 수 있습니다.
3. **고차원 데이터에서의 어려움**: 고차원 데이터에서는 거리 기반 측정이 부정확해지는 문제가 발생할 수 있으며, ε 값을 설정하는 것도 어려워질 수 있습니다.
### 예시:
DBSCAN은 다음과 같은 경우 유용할 수 있습니다.
- **지리적 데이터 분석**: 예를 들어, 지리 좌표 데이터에서 군집을 탐지할 때 DBSCAN을 사용해 특정 지역에서의 밀집된 위치 정보를 찾을 수 있습니다.
- **이상값 탐지**: 금융 데이터에서 거래 기록 중 이상 거래나 비정상 패턴을 탐지할 수 있습니다.
- **비정형 클러스터링**: 데이터가 구형으로 분포되지 않고, 복잡한 패턴을 가진 클러스터를 탐지하는 경우에 적합합니다.
### DBSCAN의 요약:
- DBSCAN은 밀도 기반 클러스터링 알고리즘으로, 밀집된 데이터 포인트를 클러스터로 묶고, 밀도가 낮은 포인트는 잡음으로 간주합니다.
- **Epsilon**과 **MinPts**라는 두 가지 주요 파라미터를 사용하여 클러스터를 형성합니다.
- 비선형적인 클러스터를 찾는 데 강점을 가지며, 노이즈와 이상값 탐지에 적합한 알고리즘입니다.
- 하지만, 파라미터 설정이 중요하고, 밀도가 균일하지 않으면 성능이 저하될 수 있습니다.
HDBSCAN
DBSCAN은 Local density에 대한 정보를 반영해 줄 수 없으며 Data들의 계층적 구조를 반영한 Clustering이 불가능함
HDBSCAN의 경우 더 이상 epsilon이 필요하지 않음
Hierarchical Density - Based Spatial Clustering of Applications with Noise
Transform the space according to the density/sparsity
Build the minimum spanning tree of the distance weighted graph
Construct a cluster hierarchy of connected components
Condense the cluster hierarchy based on minimum cluster size
Extract the stable clusters from the condensed tree
Transform the space according to the density / sparsity
: Distance를 더 Robust하게 만들어주는 작업
core(a): a의 이웃과의 거리
core(b): b의 이웃과의 거리
d(a,b): a,b의 자체 거리
dense한 지점의 data는 core가 매우 작기 때문에 d(a,b0 값을 사용하고, dense가 낮은 지점의 경우 core의 주변 정보를 사용하게 됨
distance의 robustness를 늘리고, 최종적으로는 더 효율적인 clustering을 가능하게 함
Build the minimim spanning tree of the distance weighted graph
: Robust Distance를 계산한 정보를 가지고 Minimum spanning tree를 구축함
: Spanning Tree는 모든 정점들이 연결 되어 있어야 하고 사이크릉ㄹ 포함해서는 안됨
Contrsuct a cluster hierarchy of connected components
: 계층 Hierarchy를 만드는 과정 중 하나
: Robust Distance의 Cut을 점점 높여가며 하나씩 Graph의 Edge를 끊어 나감
: 그리고 만들어진 Minimum spanning tree를 가장 가까운 거리부터 묶어줌
(HC에서 군집들 간 거리르 계싼해서 묶어주는 것과 같은 원리)
Condense the cluster hierarchy based on minimum cluster size
: Robust Distance가 0.4 이하로는 거의 모든 데이터가 1개로 떨어져 나오는 지저분한 상황이 발생함
이러한 경우 Noise처럼 보일 수 있음
: 따라서 minimum size 이상의 크기를 가진 component들만 남게 만든다
minimum size는 HDBSCAN의 Hyperparameter
DBSCAN은 Dense를 제대로 못잡아 내고 주변에 있는 데이터를 전부 Noise 처리를 함
(epsilon의 문제가 발생함)
Clustering 평가 지표
Clustering 평가 지표를 활용하여 Clustering의 결과를 확인해야 함
- Clustering 결과에 대한 평가지표는 확실한 것이 없음
- Clustering은 비지도 학습이기 때문에 정답과 비교할 수 없기 때문
Elbow point 찾기
Clustering의 결과 평가 지표는 크게 3개의 카테고리가 존재함
1. External: 우리가 알고 있는 정답 Label과 비교해봄
2. Internal: Cluster들의 공간들을 확인해보는 방법
3. Relative: Cluster의 공간과 Cluster들 간 떨어진 정도를 가지고 판단할 수 있음
Dunn Index
: 만약 Clustering이 잘 작동했다면 (1) 값은 커야하며, (2) (3) 값은 작아야 함
: 군집 간 거리의 최소 값(좌측)을 분자, 군집 내 요소 간 거리의 최대 값 (우측)을 분모로 하는 지표
: 군집 간 거리는 멀수록, 군집 내 분산은 작을 수록 좋은 군집화 결과라고 말해주는 지표
Silhouette Score
: Dunn Index의 경우 Clustering의 유효성을 검증하기 위한 하나의 값이 있음
: Silhouette Score는 개체별로 그 적합성이 평가됨 (값이 1에 가까울수록 군집화가 잘 되었다고 판단함)
