로그인
로그인

계층적 클러스터링

계층적 군집화(Hierarchical Clustering)는 군집화 알고리즘의 기본 아이디어로, 분류할 모든 관측값(또는 표본)을 초기 군집화 그룹으로 간주한 후 특정 군집화 기준에 따라 이 군집화 그룹을 계층적으로 분류하는 것입니다. 특정 종료 조건이 충족될 때까지 회전합니다.

2023-12-23 14:06:33에 편집됨

슈퍼직장인

최근 작업 더 많은 작업 보기>>

계층적 클러스터링

슈퍼직장인

최근 작업 더 많은 작업 보기>>

추천 사항
개요

패턴 인식
- 9
슈퍼직장인
기계 학습 알고리즘 엔지니어 스킬 트리
- 7
슈퍼직장인
머신러닝 알고리즘 엔지니어
- 47
슈퍼직장인
기계 학습을 위한 기본 회귀 알고리즘
- 9
슈퍼직장인
신경망 모델의 일반적인 유형 및 응용
- 12
슈퍼직장인
신경망 및 딥러닝 순환 신경망
- 7
슈퍼직장인
신경망과 딥러닝 컨볼루셔널 신경망
- 8
슈퍼직장인
신경망과 딥러닝의 기초
- 12
슈퍼직장인
컴퓨터 데이터 마이닝 코스
- 13
슈퍼직장인
앙상블 학습
- 7
슈퍼직장인

계층적 클러스터링

소개

알고리즘 아이디어: 특정 조건이 충족될 때까지 특정 방법에 따라 계층을 나눕니다.

삽화:

두 가지 계층적 클러스터링 방법

응집 방법

알고리즘 아이디어: 상향식, 먼저 각 개체를 클러스터로 처리한 다음 모든 개체가 하나의 클러스터에 있거나 특정 종료 조건을 충족할 때까지 클러스터를 점점 더 큰 클러스터로 병합합니다.

알고리즘 단계

1단계: 각 샘플 사이의 거리 계산

2단계: 거리가 가장 작은 두 샘플을 하나의 범주, 즉 클러스터 C1로 묶습니다.

3단계: 다른 샘플에서 C1까지의 거리 계산

클러스터 간 거리 측정 방법

방법 1: 최단 거리 방법(클러스터 Ci와 클러스터 Cj의 샘플 간 최소 거리를 클러스터 간 거리로 사용)

방법 2: 최장 거리 방법(클러스터 Ci와 클러스터 Cj의 샘플 간 최대 거리를 클러스터 간 거리로 사용)

방법 3: 클래스 평균 방법(클러스터 Ci와 클러스터 Cj에 포함된 모든 샘플 간의 거리의 평균을 클러스터 간 거리로 사용)

방법 4: 중심법(클러스터 Ci와 클러스터 Cj의 중심점 사이의 거리(클러스터 내 샘플의 평균값)를 클러스터 간 거리로 사용)

4단계: 모든 객체가 클러스터에 있거나 특정 종료 조건을 충족할 때까지 2단계와 3단계를 반복합니다.

삽화:

분할 방법

알고리즘 아이디어: 하향식, 먼저 모든 개체를 동일한 클러스터에 배치한 다음 각 개체가 자체 클러스터를 형성하거나 특정 종료 조건을 충족할 때까지 점차적으로 개체를 점점 더 작은 클러스터로 나눕니다.

알고리즘 단계

1단계: 모든 샘플을 하나의 클러스터로 그룹화하고, 각 샘플 사이의 거리를 계산하고, 거리가 가장 먼 두 샘플을 선택합니다.

2단계: 가장 멀리 있는 두 개의 샘플을 두 개의 클러스터로 나누고 두 클러스터에 대한 다른 샘플의 거리를 계산합니다.

거리 측정 방법은 응집 방법과 완전히 동일합니다.

3단계: 다른 샘플을 더 가까운 클러스터로 나누기

4단계: 각 개체가 클러스터를 형성하거나 특정 종료 조건을 충족할 때까지 2단계와 3단계를 반복합니다.

삽화:

계층적 클러스터링의 장점과 단점

이점

거리와 규칙 유사성은 정의하기 쉽습니다.

클러스터 수를 미리 지정할 필요가 없습니다.

클래스의 계층적 관계를 발견할 수 있습니다.

결점

계산 복잡도가 너무 높고 데이터 양이 너무 많아 적용할 수 없습니다.

모델은 이상치에 더 민감합니다.

클러스터 모양은 사슬 모양인 경향이 있습니다.

최적화

계층적 군집화 데이터가 너무 커서 사용할 수 없는 문제를 목표로 함

방법: 다단계 클러스터링 기술을 사용하여 증분 방식으로 클러스터링을 수행하여 클러스터링 시간을 대폭 단축합니다. 즉, BIRCH 알고리즘

증분: 각 데이터 포인트의 클러스터링 결정은 글로벌 데이터 포인트가 아닌 현재 처리된 데이터 포인트를 기반으로 합니다.

BIRCH 알고리즘

알고리즘 원리: 클러스터링 기능은 3-튜플을 사용하여 클러스터에 대한 관련 정보를 얻습니다. 클러스터링은 분기 인자 및 클러스터 직경의 제약 조건을 충족하는 클러스터링 기능 트리를 구성하여 얻습니다.

여러 개념

클러스터링 기능(CF)

정의: CF는 (N, LS, SS)로 표현될 수 있는 삼중항이다. 그 중 N은 이 CF에 있는 샘플 수를 나타내고, LS는 이 CF에 있는 샘플 포인트의 각 특징 차원의 합 벡터를 나타내고, SS는 이 CF에 있는 샘플 포인트의 각 특징 차원에 대한 제곱의 합을 나타냅니다.

속성: 선형 관계를 만족합니다. 즉, CF1 CF2=(N1 N2,LS1 LS2,SS1 SS2)

예: 특정 CF에 5개의 2차원 특징 샘플 (3,4), (2,6), (4,5), (4,7), (3,8)이 포함되어 있다고 가정합니다.

CF의 N=5

CF의 LS=(3 2 4 4 3,4 6 5 7 8)=(16,30)

CF의 SS=(3^2 2^2 4^2 4^2 3^2 4^2 6^2 5^2 7^2 8^2)=54 190=244

클러스터 기능 트리(CF-트리)

정의: 리프 노드는 클러스터이고, 리프가 아닌 노드는 자손의 CF 합계를 저장합니다.

CF 트리의 매개변수

리프가 아닌 노드의 최대 수: B(분기 인자)

각 리프 노드에 포함된 최대 CF 수: L

리프 노드의 각 CF에 대한 최대 반경 임계값: T

CF 트리 생성 프로세스

1단계: 첫 번째 샘플을 읽고 이를 새로운 삼중선 LN1에 통합합니다.

삽화:

2단계: 두 번째 샘플을 읽습니다. 이전 샘플과 같이 반경 T의 구 내에 있으면 동일한 삼중선으로 설정하고, 그렇지 않으면 새 삼중선 LN2를 생성합니다.

삽화:

3단계: 새 샘플이 LN1 노드에 가장 가깝지만 더 이상 SC1, SC2, SC3의 초구형 반경 T 및 L=3 내에 있지 않은 경우 분할해야 합니다.

삽화:

4단계: LN1의 모든 CF 튜플 중에서 가장 멀리 있는 두 개의 CF를 찾아 이 두 개의 새 리프 노드의 시드 CF로 만든 다음 LN1 노드의 모든 CF sc1, sc2, sc3과 LN1의 새 요소를 추가합니다. 그룹 sc6은 두 개의 새로운 리프 노드로 나뉩니다.

삽화:

5단계: 종료 조건이 충족될 때까지 2, 3, 4단계를 반복합니다.

장점과 단점

이점

클러스터링 속도가 빠르고 노이즈 포인트 식별이 가능합니다.

선형 확장성, 우수한 클러스터링 품질

결점

숫자 데이터만 처리할 수 있습니다.

데이터 입력 순서에 민감

클러스터가 구형이 아닌 경우에는 제대로 작동하지 않습니다.