계층 클러스터링

시리즈의 일부
기계 학습 및 데이터 마이닝
문제 분류 클러스터링 회귀 이상 검출 데이터 클리닝 자동 ML 어소시에이션 규칙 강화 학습 구조화된 예측 기능 엔지니어링 기능 학습 온라인 학습 준지도 학습 비지도 학습 순위 매기기 학습 문법 유도
지도 학습 (분류 • 회귀) 의사결정 트리 앙상블 배깅 부스팅 랜덤 포레스트 k-NN 선형 회귀 네이비 베이즈 인공신경망 로지스틱 회귀 분석 퍼셉트론 관련 벡터 머신(RVM) 서포트 벡터 머신(SVM)
클러스터링 버치 치유하다 계층적 k자형 기대 최대화(EM) DBSCAN 광학 평균 이동
치수 축소 인자 분석 CCA ICA LDA NMF PCA PGD t-SNE
구조화된 예측 그래픽 모델 베이즈 네트 조건부 랜덤 필드 히든 마르코프
이상 검출 k-NN 국소 특이치 계수
인공신경망 자동 인코더 인지 컴퓨팅 딥 러닝 딥 드림 다층 퍼셉트론 RNN LSTM GRU ESN 저장고 계산 제한 볼츠만 기계 GAN somerset. 컨볼루션 뉴럴 네트워크 유넷 트랜스포머 비전. 스파이킹 뉴럴 네트워크 메모리 트랜지스터 전기화학 RAM(ECRAM)
강화 학습 Q-러닝 사사 시간차(TD) 멀티 에이전트 셀프 플레이
인간과의 학습 액티브 러닝 크라우드 소싱 휴먼 인 더 루프
모델 진단 학습 곡선
이론. 커널 머신 바이어스-분산 트레이드오프 컴퓨터 학습 이론 경험적 리스크 최소화 오컴 러닝 PAC 학습 통계학 학습 VC 이론
기계학습장 NeurolIPS ICML ML JMLR ArXiv:cs.LG
관련 기사 인공지능 용어집 기계 학습 연구를 위한 데이터 세트 목록 기계학습의 개요
v t

데이터 마이닝 및 통계에서 계층 클러스터화(계층 클러스터 분석 또는 HCA라고도 함)는 클러스터의 계층을 구축하려는 클러스터 분석 방법입니다.계층형 클러스터링 전략은 일반적으로 다음 두 가지 유형으로 나뉩니다.

• 집적:이는 "상향식" 접근 방식입니다. 각 관찰은 자체 클러스터에서 시작되며 계층 위로 이동함에 따라 클러스터 쌍이 병합됩니다.
• 분할:이는 "하향식" 접근 방식입니다. 모든 관찰은 하나의 클러스터에서 시작되며 계층 아래로 이동할 때 분할이 반복적으로 수행됩니다.

일반적으로 병합과 분할은 탐욕스러운 방식으로 결정됩니다.계층적 군집^[1] 분석 결과는 일반적으로 덴드로그램으로 표시됩니다.

계층형 응집 클러스터링(HAC)의 표준 알고리즘은 시간 복잡도가 O${\displaystyle ({n\mathrm{}}^{}}$ 3$)$ {$displaystyle {O}}(n^{3})$이고 $\delta {\displaystyle \mathrm{}({n\mathrm{}}^{}}$ 2$)$ {$displaystyle \Omega(n^{2})}$ 메모리가$$ 필요하므로 매체 데이터 세트에도 너무 느립니다.단, 일부 특수한 경우 단일 링크의 경우^[2] SLINK, 완전 링크 클러스터링을 위한^[3] CLINK 등 최적의 효율적인 응집 방법($복잡도{\displaystyle \mathcal{}}$O$($2) {$displaystyle {mathcal {O}}(n^{2$이 알려져 있다.히프를 사용하면 일반적인 케이스의 실행시간을 O${\displaystyle ({n\mathrm{}}^{}}$ ${\displaystyle 2}$ log$$n$$)(\$displaystyle {O}(n^{2}\log$ n$)$로 줄일 수 있습니다.이는 메모리 요구량을 더욱 증가시키는 비용으로 전술한${\displaystyle }O{\displaystyle \mathcal{}}$(${\displaystyle {n\mathrm{}}^{}}$ 3$)$ style$(\displaystyle$ {$O}(n^{$3})을 $개선$한 것입니다$.$대부분의 경우 이 접근 방식은 메모리 오버헤드가 너무 커서 실제로 사용할 수 없습니다.

단일 링크의 특수한 경우를 제외하고 최적의 솔루션을 찾을 수 있는 알고리즘은 없습니다$($ ($2{\displaystyle \mathcal{}{}^{}}$n$$) \ $display$ { \ $mathcal${ $O}$ ; ($2$ ^ { $n$} $）$ 。

완전 검색을 사용한 분할 클러스터링은 O$)$ {$displaystyle {O}(2^{n$이지만, k-평균과 같이 분할을 선택할 때 보다 빠른 경험적 분석을 사용하는 것이 일반적입니다.

클러스터의 차이점

어떤 군집을 결합해야 하는지(집적용) 또는 어느 군집을 분할해야 하는지(분할용)를 결정하려면 관측치 집합 간의 차이를 측정하는 측정이 필요합니다.계층적 클러스터링의 대부분의 방법에서 이는 적절한 메트릭(관측 쌍 사이의 거리 측정)과 집합 내 관측 쌍별 거리의 함수로서 집합의 차이를 지정하는 연결 기준을 사용함으로써 달성된다.

미터법

적절한 메트릭을 선택하면 클러스터 형상에 영향을 줍니다.일부 요소는 다른 메트릭보다 상대적으로 서로 가까울 수 있기 때문입니다.예를 들어, 맨해튼 거리 메트릭에서 2차원에서 원점(0,0)과 (0.5,0.5) 사이의 거리는 원점과 (0,1) 사이의 거리와 동일하지만, 유클리드 거리 메트릭에서는 후자가 훨씬 크다.

계층형 클러스터링에 일반적으로 사용되는 메트릭은 다음과 같습니다.^[4]

이름	공식
유클리드 거리	$({displaystyle\a-b\_{2}={sum_{i}(a_{i}-b_{i})^{2}})$
유클리드 거리 제곱	${\displaystyle \ a-b\_{2}^{2}=\sum _{i}(a_{i}-b_{i})^{2}}$
맨해튼(또는 도시 블록) 거리	${\displaystyle \ a-b\_{1}=\sum _{i} a_{i}-b_{i} }$
최대 거리(또는 체비셰프 거리)	$\ displaystyle \ a - b \ { \ infty } = \ max _ { i }a _ { i } - b _ { i }$
마할라노비스 거리	${\displaystyle \sqrt{(a}}$ -${\displaystyle \sqrt{{}^{}b}}$ )${\displaystyle \sqrt{{\mathrm{}}^{}{}^{}}}$S${\displaystyle \sqrt{{}^{}}}$- ${\displaystyle \sqrt{1^{}}}$( a${\displaystyle \sqrt{}}$-$$ ){ $displaystyle${$sqrt${ ( $a$ - b $)^{$ \ $top$}S$^{$ -$1$ ( a - b )$$} 。S는 공분산 행렬입니다.

텍스트 또는 기타 숫자가 아닌 데이터의 경우 해밍 거리 또는 Levenshtein 거리와 같은 메트릭이 자주 사용됩니다.

유클리드 및 맨해튼 거리는 p = 1(맨하탄) 및 p = 2(유클리드)인 일반화된 민코프스키 거리의 특수한 경우이다.

몇 가지 다른 차이점 척도가 존재한다.특히 상관 기반 거리 - Pearson, Eisen cosine, Spearman, Kendall 상관 거리 - 유전자 발현 데이터 분석에 널리 사용된다.상관 기반 거리는 상관 계수를 1에서 빼서 정의됩니다.엄밀히 말하면 상관 기반의 거리는 메트릭으로 사용할 수 없지만 그 제곱근은 ^[5]메트릭으로 사용할 수 있습니다.

건강 심리학 연구에서 클러스터 분석의 리뷰는 그 연구 영역에서 출판된 연구에서 가장 일반적인 거리 척도가 유클리드 거리 또는 유클리드 ^{[citation needed]}거리 제곱이라는 것을 발견했다.

연계 기준

연결 기준은 관측치 집합 사이의 거리를 관측치 쌍별 거리의 함수로 결정합니다.

두 관측치 집합 A와 B 사이에 일반적으로 사용되는 연결 기준은 다음과 같습니다.^[6][7]

이름	공식
최대 또는 완전한 링크 클러스터링	$(\displaystyle \max \,\{,d(a,b):a\in A,b\in B,\})$
최소 또는 단일 링크 클러스터링	$(\displaystyle\min\{,d(a,b):a\in A,b\in B,\}..}$
Unweighted Average Link Clustering(또는 UPGMA)	$({displaystyle {frac {1}{A\cdot B }}\sum _{a\in A}\sum _{b\in B}d(a,b)}$
가중 평균 링크 클러스터링(또는 WPGMA)	${\displaystyle d(i\cup j,k)=paramfrac {d(i,k)+d(j,k)}{2}}}$
중심 연결 클러스터링(UPGMC)	${\displaystyle d}$( ${\displaystyle {}_{}}$ ${\displaystyle A_{}}$, ${\displaystyle {}_{}{B}_{}}$) { $displaystyle$d ( $c$_ {$A$ , c$_$ { $B$$$} ) 。${\displaystyle {여기}_{}}$서$$c A { \ $displaystyle c$_ { $A$$$} $c$ b b b b$$는 각각 클러스터 A와 B의 중심입니다.
최소 에너지 클러스터링	${{displaystyle {frac {2}{nm}\sum _{i,j=1}^{n,m}\a_{i}-b_{j}\{2}-{frac {1}{n}\sum _{i,j=1}^{n}\a_{j}_2-frac {2-{frac}$

여기서 d는 선택한 메트릭입니다.기타 연계 기준은 다음과 같습니다.

• 모든 클러스터 내 분산의 합계.
• 병합되는 클러스터의 분산 증가(Ward 기준).^[8]
• 후보 클러스터가 같은 분산 함수(V 링크)에서 생성될 확률.
• k-근접근 그래프에 대한 인-도 및 아웃-도 곱(그래프 도 연결).^[9]
• 두 ^[10][11][12]클러스터를 병합한 후 일부 클러스터 설명자(즉, 클러스터의 품질을 측정하기 위해 정의된 수량)의 증가량입니다.

논의

계층적 군집화에는 유효한 거리 측정값을 사용할 수 있다는 분명한 이점이 있습니다.사실 관측치 자체는 필요하지 않습니다. 사용되는 것은 거리의 행렬뿐입니다.

응집 군집 분석 예제

예를 들어, 이 데이터를 군집화하고 유클리드 거리를 거리 메트릭이라고 가정합니다.

계층적 군집화 덴드로그램은 다음과 같습니다.

지정된 높이로 트리를 자르면 선택한 정밀도로 파티션 클러스터링이 제공됩니다.이 예에서는 덴드로그램의 두 번째 행(위에서)을 잘라내면 클러스터 {a} {b c} {d e} {f}이(가) 생성됩니다.세 번째 행 다음에 잘라내면 클러스터 {a} {b c} {d e f}이(가) 생성되며, 클러스터 수는 적지만 클러스터 수는 더 큽니다.

이 메서드는 클러스터를 순차적으로 병합하여 개별 요소에서 계층을 구축합니다.이 예에서는 6개의 요소 {a} {b} {c} {d} {e} 및 {f}이(가) 있습니다.첫 번째 단계는 클러스터에서 병합할 요소를 결정하는 것입니다.일반적으로 선택한 거리에 따라 가장 가까운 두 요소를 취하려고 합니다.

임의로 이 단계에서 거리 행렬을 구성할 수도 있습니다. 여기서 i번째 행 j번째 열의 숫자는 i번째와 j번째 요소 사이의 거리입니다.그런 다음 클러스터화가 진행됨에 따라 클러스터가 병합되고 거리가 업데이트될 때 행과 열이 병합됩니다.이는 이러한 유형의 클러스터링을 구현하는 일반적인 방법으로 클러스터 간의 거리를 캐싱할 수 있는 이점이 있습니다.단순한 집적 클러스터링 알고리즘은 단일 링크 클러스터링 페이지에 설명되어 있습니다. 다양한 유형의 링크에 쉽게 적응할 수 있습니다(아래 참조).

가장 가까운 두 요소 b와 c를 병합했다고 가정하면 이제 클러스터 {a}, {b, c}, {d}, {e} 및 {f}이(가) 있으며 이러한 요소를 추가로 병합하려고 합니다.그러기 위해서는 {a}과(와) {b c} 사이의 거리를 측정하여 두 클러스터 간의 거리를 정의해야 합니다.일반적으로 두 $클러스터{\displaystyle \mathcal{}}$ A$(\$와 B$(\$ 사이의$$ 거리는 다음 중 하나입니다.

• 각 클러스터의 요소 간 최대 거리(완전 링크 클러스터링이라고도 함):

$\displaystyle \max\{,d(x,y):x\in {mathcal {A}},y\in {mathcal {B}},\}.}$

• 각 클러스터의 요소 간 최소 거리(단일 링크 클러스터링이라고도 함):

$(\displaystyle\min\,d(x,y):x in {mathcal {A}},y\ in {mathcal {B}},\}).}$

• 각 군집의 요소 간 평균 거리(UPGMA 등에서 사용되는 평균 링크 클러스터링이라고도 함):

${\displaystyle {1\over {\mathcal {A}}\cdot {\mathcal {B}}}\sum _{x\in\mathcal {A}\sum _{y}d(x,y)}$

• 모든 클러스터 내 분산의 합계.
• 병합되는 클러스터의 분산 증가(Ward의 메서드^[8])
• 후보 클러스터가 같은 분산 함수(V 링크)에서 생성될 확률.

최소 거리가 일치할 경우 쌍이 랜덤으로 선택되므로 구조적으로 서로 다른 여러 덴드로그램을 생성할 수 있습니다.또는 연결된 모든 쌍이 동시에 결합되어 고유한 ^[13]덴드로그램이 생성될 수 있습니다.

군집 수가 충분히 적은 경우(숫자 기준) 군집화를 중지할지를 언제든지 결정할 수 있습니다.또, 일부의 링크에서는, 이전의 집적보다 클러스터간의 거리가 멀어져, 클러스터가 Marge 하기에는 너무 멀면 클러스터링을 정지할 수 있습니다(거리 기준).그러나, 이것은 예를 들어, 이른바 반전^[14](반전, 울트라메트릭에서 이탈)이 발생할 수 있는 중심 연결의 경우는 아니다.

분할 클러스터화시키는 클러스터링

분할 클러스터링의 기본 원리는 DIANA(^[15]Divisive ANAolysis Clustering) 알고리즘으로 발표되었습니다.처음에는 모든 데이터가 동일한 클러스터에 있으며 가장 큰 클러스터는 모든 개체가 분리될 때까지 분할됩니다.각 클러스터를 분할하는${\displaystyle {}^{}}$에는 O($)$ {$displaystyle$O(2$^{n$})가$$ $있으므로{\displaystyle }$ 휴리스틱스가 필요합니다.DIANA는 평균 차이가 가장 큰 개체를 선택한 후 나머지 개체보다 새 클러스터에 더 가까운 개체를 모두 이 클러스터로 이동합니다.

소프트웨어

오픈 소스 구현

• ALGLIB는 O(n²) 메모리와 O(n†) 실행 시간을 사용하여 C++ 및 C#에 여러 계층 클러스터링 알고리즘(싱글 링크, 완전 링크, 워드)을 구현합니다.
• ELKI는 여러 계층 클러스터링 알고리즘, 다양한 연계 전략을 포함하고 있으며 효율적인 SLINK,^[2] CLINK^[3] 및 Anderberg 알고리즘, 덴드로그램으로부터의 유연한 클러스터 추출 및 기타 다양한 클러스터 분석 알고리즘을 포함합니다.
• Julia는 Clustering.jl ^[16]패키지 내에 구현되어 있습니다.
• MATLAB에 대한 GNU 아날로그인 옥타브는 함수 "linkage"에서 계층적 클러스터링을 구현합니다.
• Orange는 데이터 마이닝 소프트웨어 스위트이며 대화형 덴드로그램 시각화를 통한 계층형 클러스터링을 포함하고 있습니다.
• R에는 계층 클러스터링 ^[18]기능을 제공하는 내장 함수^[17] 및 패키지가 있습니다.
• SciPy는 효율적인 SLINK 알고리즘을 포함하여 Python에 계층형 클러스터링을 구현합니다.
• skikit-learn은 또한 Python에서 계층형 클러스터링을 구현합니다.
• Weka에는 계층적 군집 분석이 포함됩니다.

상업용 실장

• MATLAB에는 계층적 군집 분석이 포함됩니다.
• SAS는 PROC 클러스터에 계층형 클러스터 분석을 포함합니다.
• Mathematica에는 계층형 클러스터링 패키지가 포함되어 있습니다.
• NCSS에는 계층 클러스터 분석이 포함됩니다.
• SPSS에는 계층형 클러스터 분석이 포함됩니다.
• Qlucore Omics 탐색기에는 계층형 클러스터 분석이 포함되어 있습니다.
• 통계분석에는 계층적 군집 분석이 포함됩니다.
• CrimeStat에는 지리정보시스템에 대한 그래픽 출력을 가진 가장 가까운 인접 계층형 클러스터 알고리즘이 포함되어 있습니다.

「 」를 참조해 주세요.

레퍼런스

추가 정보

• Kaufman, L.; Rousseeuw, P.J. (1990). Finding Groups in Data: An Introduction to Cluster Analysis (1 ed.). New York: John Wiley. ISBN 0-471-87876-6.
• Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2009). "14.3.12 Hierarchical clustering". The Elements of Statistical Learning (2nd ed.). New York: Springer. pp. 520–8. ISBN 978-0-387-84857-0. Archived from the original (PDF) on 2009-11-10. Retrieved 2009-10-20.