태그: 군집분석

Affinity Propagation #

Affinity Propagation은 데이터 포인트들 간의 메시지 전달을 통해 클러스터의 중심(exemplar)을 자동으로 선택하는 클러스터링 알고리즘이다. 클러스터의 수를 미리 정하지 않고도 데이터의 구조에 따라 적절한 수의 클러스터를 자동으로 결정한다.

주요 개념 #

• Exemplar: 각 클러스터를 대표하는 실제 데이터 포인트이다.
• Responsibility: 데이터 포인트 i가 포인트 k를 exemplar로 선택하는 정도를 나타낸다.
• Availability: 포인트 k가 포인트 i의 exemplar가 되기에 적합한 정도를 나타낸다.
• Preference: 각 데이터 포인트가 exemplar가 될 가능성을 나타내는 값이다.

알고리즘 특징 #

• 실제 데이터 포인트를 클러스터의 중심으로 사용한다.
• 클러스터의 수를 자동으로 결정한다.
• 모든 데이터 포인트가 exemplar가 될 수 있다.
• 메시지 전달 방식을 통해 최적의 exemplar를 찾는다.

장점과 단점 #

• 장점

BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) #

BIRCH는 대용량 데이터셋을 효율적으로 처리할 수 있는 계층적 클러스터링 알고리즘이다. 메모리 사용량을 최소화하면서 점진적으로 클러스터를 구성하며, CF(Clustering Feature) 트리 구조를 사용하여 데이터를 요약한다.

주요 개념 #

• CF (Clustering Feature): 클러스터의 요약 정보를 담고 있는 3개 값의 튜플 (N, LS, SS)이다.
  • N: 클러스터 내 데이터 포인트의 수
  • LS: 데이터 포인트들의 선형 합
  • SS: 데이터 포인트들의 제곱 합
• CF Tree: 클러스터링 특징들을 계층적으로 저장하는 균형 트리 구조이다.
• 임계값 (Threshold): 새로운 데이터 포인트가 기존 클러스터에 병합될지 결정하는 기준이다.

알고리즘 특징 #

• 메모리 효율적이며 대용량 데이터를 처리할 수 있다.
• 단일 스캔으로 클러스터링을 수행한다.
• 점진적(incremental) 클러스터링이 가능하다.
• 구형(spherical) 클러스터에 가장 적합하다.

장점과 단점 #

• 장점

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) #

DBSCAN은 밀도 기반 클러스터링 알고리즘이다. 데이터의 밀도에 따라 클러스터를 형성한다. 이 알고리즘은 군집의 형태가 불규칙하거나 크기가 다양할 때 효과적으로 동작하며, 노이즈 데이터(이상치)를 효과적으로 분리할 수 있다.

주요 개념 #

• 반경 (ε, Epsilon): 각 데이터 포인트 주변에서 이웃을 찾기 위한 최대 거리이다.
• 최소 샘플 수 (minPts): 클러스터를 형성하기 위해 필요한 최소 데이터 포인트 수이다.
• 핵심 포인트 (Core Point): 주변 반경 내에 최소 샘플 수 이상의 데이터 포인트가 존재하는 데이터 포인트이다.
• 경계 포인트 (Border Point): 핵심 포인트의 이웃이지만, 자체적으로는 최소 샘플 수를 만족하지 못하는 데이터 포인트이다.
• 노이즈 (Noise/Outlier): 어느 클러스터에도 속하지 않는 데이터 포인트이다.

알고리즘 동작 원리 #

상세 단계 #

1. 이웃 탐색: 모든 데이터 포인트에 대해, 반경 ε 내에 있는 이웃 데이터 포인트의 수를 계산한다.
2. 핵심 포인트 식별: 최소 샘플 수(minPts)보다 많은 이웃을 가진 포인트를 핵심 포인트로 식별한다.
3. 클러스터 형성: 핵심 포인트를 중심으로 인접한 핵심 포인트와 경계 포인트를 확장하며 클러스터를 형성한다.
4. 노이즈 분류: 어떤 클러스터로도 확장되지 않은 포인트는 노이즈로 분류한다.

의사코드 #

DBSCAN(D, ε, minPts):
    C = 0  // 클러스터 번호
    for each point p in D:
        if p is visited:
            continue
        mark p as visited
        NeighborPts = regionQuery(p, ε)
        if |NeighborPts| < minPts:
            mark p as NOISE
        else:
            C = C + 1
            expandCluster(p, NeighborPts, C, ε, minPts)

expandCluster(p, NeighborPts, C, ε, minPts):
    add p to cluster C
    for each point p' in NeighborPts:
        if p' is not visited:
            mark p' as visited
            NeighborPts' = regionQuery(p', ε)
            if |NeighborPts'| >= minPts:
                NeighborPts = NeighborPts joined with NeighborPts'
        if p' is not yet member of any cluster:
            add p' to cluster C

매개변수 선택 방법 #

ε (Epsilon) 값 선택 #

1. k-distance 그래프 방법:
   • 각 포인트에서 k번째 최근접 이웃까지의 거리를 계산
   • k-distance를 오름차순으로 정렬하여 그래프를 그림
   • 그래프에서 “무릎점(knee point)“을 찾아 ε 값으로 설정

# k-distance 그래프 예제
from sklearn.neighbors import NearestNeighbors
import matplotlib.pyplot as plt

def find_epsilon(X, k=4):
    neigh = NearestNeighbors(n_neighbors=k)
    nbrs = neigh.fit(X)
    distances, indices = nbrs.kneighbors(X)
    
    # k번째 이웃까지의 거리만 선택
    k_distances = distances[:, k-1]
    k_distances = np.sort(k_distances)
    
    plt.plot(k_distances)
    plt.ylabel('k-NN distance')
    plt.xlabel('Data Points sorted by distance')
    plt.title('k-distance Graph')
    plt.show()
    
    return k_distances

minPts 값 선택 #

• 일반적인 규칙: minPts = 2 × 차원수
• 최소값: 차원수 + 1
• 2D 데이터: 보통 4개 이상 권장
• 고차원 데이터: 더 큰 값 필요

Python 구현 예제 #

scikit-learn 사용 #

from sklearn.cluster import DBSCAN
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
import numpy as np

# 샘플 데이터 생성
X, _ = make_blobs(n_samples=300, centers=4, n_features=2, 
                  random_state=42, cluster_std=0.60)

# DBSCAN 적용
dbscan = DBSCAN(eps=0.3, min_samples=10)
cluster_labels = dbscan.fit_predict(X)

# 결과 시각화
plt.figure(figsize=(10, 8))
unique_labels = set(cluster_labels)
colors = plt.cm.Spectral(np.linspace(0, 1, len(unique_labels)))

for k, col in zip(unique_labels, colors):
    if k == -1:
        # 노이즈 포인트는 검은색으로 표시
        col = 'black'
        marker = 'x'
    else:
        marker = 'o'
    
    class_member_mask = (cluster_labels == k)
    xy = X[class_member_mask]
    plt.plot(xy[:, 0], xy[:, 1], marker, markerfacecolor=col,
             markeredgecolor='k', markersize=6)

plt.title('DBSCAN Clustering')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()

print(f"발견된 클러스터 수: {len(set(cluster_labels)) - (1 if -1 in cluster_labels else 0)}")
print(f"노이즈 포인트 수: {list(cluster_labels).count(-1)}")

직접 구현 #

import numpy as np
from scipy.spatial.distance import cdist

class DBSCANCustom:
    def __init__(self, eps=0.5, min_samples=5):
        self.eps = eps
        self.min_samples = min_samples
    
    def fit_predict(self, X):
        n_points = len(X)
        labels = np.full(n_points, -1)  # -1은 노이즈를 의미
        cluster_id = 0
        
        # 모든 포인트 간의 거리 계산
        distances = cdist(X, X)
        
        for i in range(n_points):
            if labels[i] != -1:  # 이미 처리된 포인트
                continue
            
            # 이웃 찾기
            neighbors = self._find_neighbors(distances, i)
            
            if len(neighbors) < self.min_samples:
                labels[i] = -1  # 노이즈로 분류
            else:
                # 새 클러스터 시작
                labels = self._expand_cluster(X, distances, labels, i, 
                                            neighbors, cluster_id)
                cluster_id += 1
        
        return labels
    
    def _find_neighbors(self, distances, point_idx):
        return np.where(distances[point_idx] <= self.eps)[0]
    
    def _expand_cluster(self, X, distances, labels, point_idx, 
                       neighbors, cluster_id):
        labels[point_idx] = cluster_id
        i = 0
        
        while i < len(neighbors):
            neighbor_idx = neighbors[i]
            
            if labels[neighbor_idx] == -1:  # 노이즈였던 경우
                labels[neighbor_idx] = cluster_id
            elif labels[neighbor_idx] == -1:  # 미분류 상태
                labels[neighbor_idx] = cluster_id
                
                # 새로운 이웃들 찾기
                new_neighbors = self._find_neighbors(distances, neighbor_idx)
                if len(new_neighbors) >= self.min_samples:
                    neighbors = np.concatenate([neighbors, new_neighbors])
            
            i += 1
        
        return labels

다른 클러스터링 알고리즘과의 비교 #

실제 응용 분야 #

1. 이미지 분할 #

from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler
import cv2

def image_segmentation_dbscan(image_path):
    # 이미지 로드 및 전처리
    img = cv2.imread(image_path)
    img = cv2.cvtColor(img, cv2.COLOR_BGR2RGB)
    
    # 픽셀 데이터 reshape
    pixel_data = img.reshape(-1, 3)
    
    # 정규화
    scaler = StandardScaler()
    pixel_data_scaled = scaler.fit_transform(pixel_data)
    
    # DBSCAN 적용
    dbscan = DBSCAN(eps=0.3, min_samples=50)
    labels = dbscan.fit_predict(pixel_data_scaled)
    
    # 결과 이미지 생성
    segmented_img = labels.reshape(img.shape[:2])
    
    return segmented_img, labels

2. 고객 세그멘테이션 #

def customer_segmentation(customer_data):
    # 특성 선택 및 정규화
    features = ['annual_spending', 'frequency', 'recency']
    X = customer_data[features]
    
    scaler = StandardScaler()
    X_scaled = scaler.fit_transform(X)
    
    # DBSCAN 적용
    dbscan = DBSCAN(eps=0.5, min_samples=5)
    clusters = dbscan.fit_predict(X_scaled)
    
    # 결과 분석
    customer_data['cluster'] = clusters
    
    return customer_data

3. 이상 탐지 #

def anomaly_detection(sensor_data):
    # DBSCAN을 이용한 이상 탐지
    dbscan = DBSCAN(eps=0.3, min_samples=10)
    labels = dbscan.fit_predict(sensor_data)
    
    # 노이즈로 분류된 포인트들을 이상값으로 간주
    anomalies = sensor_data[labels == -1]
    
    return anomalies, labels

성능 평가 지표 #

1. 실루엣 계수 (Silhouette Score) #

from sklearn.metrics import silhouette_score

def evaluate_dbscan(X, labels):
    # 노이즈 포인트 제외하고 계산
    mask = labels != -1
    if len(set(labels[mask])) > 1:
        score = silhouette_score(X[mask], labels[mask])
        return score
    else:
        return -1  # 클러스터가 1개 이하인 경우

2. 조정 랜드 지수 (Adjusted Rand Index) #

from sklearn.metrics import adjusted_rand_score

def compare_clustering(true_labels, pred_labels):
    return adjusted_rand_score(true_labels, pred_labels)

장점과 단점 #

장점 #

• 임의 형태의 클러스터: 클러스터의 모양이 불규칙해도 효과적으로 동작한다.
• 노이즈 처리: 노이즈나 이상치를 효과적으로 분리할 수 있다.
• 클러스터 수 자동 결정: 사전에 클러스터 수를 지정할 필요가 없다.
• 강건성: 이상값에 대해 강건하다.

단점 #

• 매개변수 민감성: 데이터의 밀도가 크게 차이나는 경우, 적절한 ε 값을 찾기 어렵다.
• 고차원 문제: 고차원 데이터에서는 성능이 저하될 수 있다 (차원의 저주).
• 밀도 변화: 밀도가 크게 다른 클러스터들을 동시에 찾기 어렵다.
• 메모리 사용량: 모든 포인트 간의 거리를 계산해야 하므로 메모리 사용량이 클 수 있다.

변형 알고리즘 #

HDBSCAN (Hierarchical DBSCAN) #

• 계층적 밀도 기반 클러스터링
• 다양한 밀도의 클러스터를 효과적으로 처리
• 더 안정적인 클러스터 추출

import hdbscan

def hdbscan_clustering(X):
    clusterer = hdbscan.HDBSCAN(min_cluster_size=10)
    cluster_labels = clusterer.fit_predict(X)
    return cluster_labels

OPTICS (Ordering Points To Identify Clustering Structure) #

• DBSCAN의 확장 버전
• 클러스터 추출을 위한 순서 정보 제공
• 다양한 밀도 레벨에서 클러스터 분석 가능

실습 과제 #

1. 매개변수 최적화: k-distance 그래프를 이용하여 최적의 ε 값을 찾아보세요.
2. 실제 데이터 적용: 실제 데이터셋(예: Iris, Wine)에 DBSCAN을 적용하고 결과를 분석해보세요.
3. 성능 비교: DBSCAN과 K-Means의 성능을 다양한 데이터셋에서 비교해보세요.
4. 이상 탐지: DBSCAN을 이용한 이상 탐지 시스템을 구현해보세요.

DBSCAN은 데이터의 밀도 기반 특성을 살리고 노이즈를 효과적으로 다루고자 할 때 매우 유용한 알고리즘이다. 특히 클러스터의 형태가 불규칙하거나 이상값이 많은 실제 데이터에서 뛰어난 성능을 보인다.

Gaussian Mixture Model (GMM) #

Gaussian Mixture Model (GMM)은 각 클러스터를 다변량 가우시안 분포로 모델링하는 확률적 클러스터링 기법이다. EM (Expectation-Maximization) 알고리즘을 사용하여 각 클러스터의 평균, 공분산, 혼합 계수를 추정하고, 데이터가 각 클러스터에 속할 확률을 계산한다.

특징 #

• 클러스터가 타원형인 경우에도 유연하게 모델링할 수 있다.
• 데이터에 대한 확률적 해석을 제공한다.
• 초기값 및 클러스터의 수 설정에 민감할 수 있다.

GMM은 데이터의 분포를 확률적으로 모델링하여 복잡한 클러스터 구조를 파악하는 데 유용하다.

K중심값 (K-means) #

K-means는 데이터마이닝과 기계학습에서 가장 널리 사용되는 클러스터링(군집화) 알고리즘 중 하나다. 영어 원어인 “K-means"는 한국어로 K중심값 또는 K평균 등으로 번역되기도 하지만, 현업에서는 주로 “케이민즈"라고 원어 그대로 부르는 경우가 많다. 본 문서에서도 혼동을 피하기 위해 K-means로 표기한다.

여기서 “K"는 사용자가 미리 정하는 군집(클러스터)의 개수를 의미하며, “means"는 각 군집의 중심값(평균값, 대푯값)을 의미한다. 다만, K-means에서의 “mean"은 통계적 의미의 평균이라기보다는, 각 군집을 대표하는 중심점(centroid)이라는 개념에 더 가깝다.

K-means의 핵심은 데이터를 K개의 그룹으로 나누되, 각 그룹 내의 데이터들이 서로 최대한 비슷하도록(즉, 중심점과의 거리가 최소가 되도록) 군집을 형성하는 것이다. 이 알고리즘은 간단하면서도 효과적이어서, 고객 세분화, 이미지 분할, 이상치 탐지 등 다양한 분야에서 널리 활용된다.

Mean Shift #

Mean Shift는 비모수적(non-parametric) 밀도 기반 클러스터링 알고리즘으로, 데이터의 확률 밀도 함수의 모드(mode)를 찾아 클러스터를 형성한다. 각 데이터 포인트를 확률 밀도가 가장 높은 지점으로 이동시켜 클러스터의 중심을 찾는다.

주요 개념 #

• 커널 밀도 추정: 각 데이터 포인트 주변의 확률 밀도를 추정한다.
• 그래디언트 상승: 밀도 함수의 그래디언트 방향으로 데이터 포인트를 이동시킨다.
• 모드 탐색: 확률 밀도 함수의 극값(모드)을 찾아 클러스터 중심으로 설정한다.

알고리즘 단계 #

1. 각 데이터 포인트에서 시작한다.
2. 주변 윈도우 내의 데이터 포인트들의 평균을 계산한다.
3. 현재 포인트를 계산된 평균 위치로 이동시킨다.
4. 수렴할 때까지 2-3단계를 반복한다.
5. 같은 모드로 수렴하는 포인트들을 하나의 클러스터로 그룹화한다.

장점과 단점 #

• 장점

OPTICS (Ordering Points To Identify the Clustering Structure) #

OPTICS는 DBSCAN의 확장된 형태로, 다양한 밀도를 가진 클러스터를 효과적으로 찾을 수 있는 밀도 기반 클러스터링 알고리즘이다. DBSCAN과 달리 고정된 ε 값 대신 클러스터링 순서(ordering)를 생성하여 다양한 밀도 수준에서 클러스터를 추출할 수 있다.

주요 개념 #

• 핵심 거리 (Core Distance): 특정 포인트가 핵심 포인트가 되기 위한 최소 반경이다.
• 도달 거리 (Reachability Distance): 한 포인트에서 다른 포인트로의 도달 가능성을 나타내는 거리이다.
• 클러스터링 순서: 데이터 포인트들의 처리 순서로, 도달 거리를 기준으로 정렬된다.

알고리즘 특징 #

• DBSCAN보다 유연하여 다양한 밀도의 클러스터를 동시에 처리할 수 있다.
• 클러스터링 결과를 시각화하여 데이터 구조를 이해하기 쉽다.
• 매개변수 설정이 DBSCAN보다 상대적으로 용이하다.

장점과 단점 #

• 장점

Ward 연결법 (Ward Linkage) #

Ward 연결법은 계층적 클러스터링에서 사용되는 연결 기준(linkage criterion) 중 하나로, 클러스터 내 분산의 증가를 최소화하는 방향으로 클러스터를 병합하는 방법이다. 이 방법은 비교적 균등한 크기의 구형 클러스터를 생성하는 경향이 있다.

주요 개념 #

• 클러스터 내 제곱합 (Within-cluster Sum of Squares, WSS): 각 클러스터 내 데이터 포인트들과 클러스터 중심 간의 거리 제곱합이다.
• Ward 거리: 두 클러스터를 병합했을 때 증가하는 WSS의 양을 의미한다.
• 분산 최소화: 병합 시 전체 분산의 증가량을 최소화하는 것을 목표로 한다.

알고리즘 특징 #

• 각 단계에서 클러스터 내 분산의 증가를 최소화하는 두 클러스터를 병합한다.
• 덴드로그램(dendrogram)을 생성하여 계층적 구조를 시각화할 수 있다.
• 비교적 균등한 크기의 클러스터를 형성하는 경향이 있다.
• 구형에 가까운 클러스터에 가장 적합하다.

계산 방법 #

두 클러스터 A와 B를 병합할 때의 Ward 거리는 다음과 같이 계산된다:

계층적 군집화 (Hierarchical Clustering) #

계층적 군집화는 데이터를 계층적인 트리 구조(dendrogram)로 표현하여 클러스터를 구성하는 방법이다. 주요 방식은 두 가지가 있다:

1. 병합적 방법 (Agglomerative): 각 데이터 포인트를 개별 클러스터로 시작하여, 가장 유사한 클러스터들을 반복적으로 병합한다.
2. 분할적 방법 (Divisive): 전체 데이터를 하나의 클러스터로 시작하여, 점진적으로 클러스터를 분할해 나간다.

알고리즘 작동 원리 #

병합적 방법 (Agglomerative) 단계 #

1. 각 데이터 포인트를 개별 클러스터로 초기화
2. 모든 클러스터 쌍 간의 거리를 계산
3. 가장 가까운 두 클러스터를 병합
4. 새로운 클러스터와 다른 클러스터 간의 거리를 다시 계산
5. 모든 데이터가 하나의 클러스터가 될 때까지 2-4단계를 반복

거리 측정 방법 #

클러스터 간의 거리를 측정하는 다양한 방법이 있다:

스펙트럴 클러스터링 (Spectral Clustering) #

스펙트럴 클러스터링은 그래프 이론과 선형 대수학을 기반으로 하는 클러스터링 알고리즘이다. 데이터를 그래프로 표현하고, 그래프의 라플라시안 행렬의 고유벡터(eigenvector)를 사용하여 클러스터를 형성한다.

주요 개념 #

• 유사도 그래프: 데이터 포인트들을 노드로, 유사도를 엣지로 표현한 그래프이다.
• 라플라시안 행렬: 그래프의 구조적 특성을 나타내는 행렬이다.
• 고유벡터: 라플라시안 행렬의 고유벡터를 사용하여 차원을 축소한 후 클러스터링을 수행한다.

알고리즘 단계 #

1. 데이터 포인트 간의 유사도를 계산하여 유사도 행렬을 구성한다.
2. 유사도 행렬로부터 라플라시안 행렬을 계산한다.
3. 라플라시안 행렬의 고유벡터를 구한다.
4. 가장 작은 k개의 고유값에 해당하는 고유벡터로 새로운 특성 공간을 구성한다.
5. 새로운 특성 공간에서 K-means 등의 클러스터링을 수행한다.

장점과 단점 #

• 장점