본문으로 이동

클러스터 분석

위키백과, 우리 모두의 백과사전.
군집 분석 결과는 사각형을 세 개의 군집으로 나누어 색칠한 것으로 나타난다.

클러스터 분석(cluster analysis) 또는 군집 분석 또는 클러스터링(clustering) 또는 군집화는 자료 집합의 대상들을 그룹으로 분할하여, 같은 그룹(이 그룹을 군집 또는 클러스터라고 함) 내의 대상들이 다른 그룹의 대상들보다 서로 더 많은 유사성(분석가가 정의한 특정한 의미에서)을 보이도록 하는 데이터 분석 기법이다. 이는 탐색적 자료 분석의 주요 과제이자 패턴 인식, 이미지 분석, 정보 검색, 생물정보학, 데이터 압축, 컴퓨터 그래픽스, 기계 학습 등 여러 분야에서 사용되는 일반적인 통계적 데이터 분석 기법이다.

클러스터 분석은 하나의 특정 알고리즘이라기보다 일련의 알고리즘과 과제들을 통칭한다. 이는 무엇을 군집으로 간주하고 어떻게 이를 효율적으로 찾을 것인지에 대한 이해가 서로 크게 다른 다양한 알고리즘을 통해 달성될 수 있다. 일반적인 군집의 개념에는 군집 구성원 사이의 거리가 작은 그룹, 데이터 공간의 밀집된 영역, 구간 또는 특정 확률 분포 등이 포함된다. 따라서 클러스터링은 다목적 최적화 문제로 공식화될 수 있다. 적절한 군집 알고리즘과 매개변수 설정(사용할 거리 함수, 밀도 임계값 또는 예상 군집 수와 같은 매개변수 포함)은 개별 자료 집합과 결과의 의도된 용도에 따라 달라진다. 클러스터 분석 자체는 자동화된 과제가 아니라, 시행착오를 수반하는 지식 발견 또는 대화형 다목적 최적화의 반복적인 과정이다. 결과가 원하는 특성을 얻을 때까지 데이터 전처리와 모델 매개변수를 수정해야 하는 경우가 많다.

클러스터링 외에도 자동 통계적 분류, 수리분류학, 보트리올로지(botryology, 그리스어: βότρυς '포도'에서 유래), 유형학적 분석, 커뮤니티 탐지 등 유사한 의미를 지닌 용어들이 다수 존재한다. 미묘한 차이는 주로 결과의 용도에 있다. 데이터 마이닝에서는 결과물인 그룹 자체가 관심의 대상인 반면, 자동 분류에서는 결과물의 식별 능력이 관심의 대상이다.

클러스터 분석은 1932년 드라이버(Driver)와 크로버(Kroeber)에 의해 인류학에서 기원하였으며[1], 1938년 조셉 주빈[2]과 1939년 로버트 트라이언[3]에 의해 심리학에 도입되었다. 또한 1943년부터 레이몬드 카텔이 성격심리학의 특질 이론 분류에 유명하게 사용하였다.[4]

정의

[편집]

"군집"이라는 개념은 정확하게 정의될 수 없는데, 이것이 군집 알고리즘이 매우 많은 이유 중 하나이다.[5] 공통 분모는 데이터 객체들의 그룹이라는 점이다. 그러나 연구자마다 서로 다른 군집 모델을 사용하며, 이러한 각 군집 모델에 대해 다시 서로 다른 알고리즘이 존재할 수 있다. 서로 다른 알고리즘에 의해 발견된 군집의 개념은 그 특성이 상당히 다양하다. 이러한 "군집 모델"을 이해하는 것이 다양한 알고리즘 간의 차이를 이해하는 핵심이다. 전형적인 군집 모델은 다음과 같다.

  • 연결성 모델(Connectivity models): 예를 들어, 계층적 군집화는 거리 연결성을 기반으로 모델을 구축한다.
  • 무게 중심 모델(Centroid models): 예를 들어, K-평균 알고리즘은 각 군집을 하나의 평균 벡터로 나타낸다.
  • 분포 모델(Distribution models): 군집은 기댓값 최대화 알고리즘에서 사용되는 다변량 정규분포와 같은 통계적 분포를 사용하여 모델링된다.
  • 밀도 모델(Density models): 예를 들어, DBSCAN, OPTICS 및 HDBSCAN은 군집을 데이터 공간에서 연결된 밀집 영역으로 정의한다.
  • 부분공간 모델(Subspace models): 바이클러스터링(공군집화 또는 2개 모드 군집화라고도 함)에서 군집은 군집 구성원과 관련 속성 모두를 사용하여 모델링된다.
  • 그룹 모델(Group models): 일부 알고리즘은 결과에 대해 정교한 모델을 제공하지 않고 단지 그룹화 정보만 제공한다.
  • 그래프 기반 모델(Graph-based models): 클릭, 즉 그래프 내의 모든 두 노드가 간선으로 연결된 노드들의 부분집합은 군집의 원형적인 형태로 간주될 수 있다. 완전 연결 요구 사항을 완화한 것(일부 간선이 누락될 수 있음)은 HCS 군집화 알고리즘에서와 같이 준클릭(quasi-clique)으로 알려져 있다.
  • 부호형 그래프 모델: 부호형 그래프의 모든 경로는 간선 부호들의 곱에서 파생된 부호를 가진다. 균형 이론의 가정 하에서, 간선들은 부호를 바꿀 수 있으며 이는 이분 그래프(bifurcated graph)로 이어진다. 더 약한 "군집 가능성 공리"(정확히 하나의 음수 간선을 가진 순환이 없음)는 두 개 이상의 군집이나 양수 간선만 있는 부분 그래프를 결과로 낸다.[6]
  • 신경망 모델(Neural models): 가장 잘 알려진 비지도 학습 신경망은 자기조직화 지도이며, 이러한 모델들은 대개 위 모델 중 하나 이상과 유사한 특성을 갖는다. 신경망이 주성분 분석 또는 독립 성분 분석의 형태를 구현할 때는 부분공간 모델을 포함하기도 한다.

"군집화"는 기본적으로 이러한 군집들의 집합이며, 대개 자료 집합의 모든 객체를 포함한다. 또한, 군집들 사이의 관계, 예를 들어 서로 중첩된 군집들의 계층 구조를 명시할 수도 있다. 군집화는 다음과 같이 대략적으로 구분할 수 있다.

  • 하드 군집화(Hard clustering): 각 객체가 군집에 속하거나 속하지 않음
  • 소프트 군집화(Soft clustering, 또는 퍼지 군집화): 각 객체가 특정 정도(예: 군집에 속할 가능성)로 각 군집에 속함

또한 다음과 같은 더 미세한 구분이 가능하다.

  • 엄격한 분할 군집화(Strict partitioning clustering): 각 객체가 정확히 하나의 군집에 속함
  • 이상치를 포함한 엄격한 분할 군집화: 객체가 어느 군집에도 속하지 않을 수 있으며, 이 경우 이상치로 간주됨
  • 중첩 군집화(Overlapping clustering, 또는 대안적 군집화, 다중 뷰 군집화): 객체가 둘 이상의 군집에 속할 수 있음 (보통 하드 군집 수반)
  • 계층적 군집화: 하위 군집에 속한 객체는 상위 군집에도 속함
  • 부분공간 군집화: 중첩 군집화이면서도, 고유하게 정의된 부분공간 내에서는 군집들이 중첩되지 않을 것으로 예상됨

알고리즘

[편집]

위에서 언급한 바와 같이, 군집화 알고리즘은 군집 모델에 따라 분류될 수 있다. 지금까지 발표된 군집화 알고리즘은 100개가 넘을 것으로 추정되므로, 다음 개요에서는 가장 두드러진 사례들만 나열한다. 모든 알고리즘이 군집에 대한 모델을 제공하는 것은 아니며, 따라서 쉽게 분류되지 않을 수도 있다. 위키백과에 설명된 알고리즘의 개요는 알고리즘 목록#통계학에서 찾을 수 있다.

객관적으로 "올바른" 군집화 알고리즘은 존재하지 않으며, 언급된 바와 같이 "군집화는 보는 사람의 눈에 달려 있다."[5] 실제로 군집화에 대한 공리적 접근 방식은 어떤 군집화 방법도 다음 세 가지 근본적인 특성을 동시에 만족시킬 수 없음을 보여준다. 규모 불변성(scale invariance, 거리의 비례적 축척에 따라 결과가 변하지 않음), 풍부성(richness, 데이터의 가능한 모든 분할이 달성될 수 있음), 그리고 거리와 군집 구조 간의 일관성(consistency)이 그것이다.[7] 특정 문제에 가장 적합한 군집화 알고리즘은 수학적으로 하나의 군집 모델을 다른 모델보다 선호해야 할 이유가 없는 한, 대개 실험적으로 선택되어야 한다. 특정 종류의 모델을 위해 설계된 알고리즘은 일반적으로 근본적으로 다른 종류의 모델을 포함하는 자료 집합에서는 실패한다.[5] 예를 들어, K-평균은 비볼록(non-convex) 군집을 찾을 수 없다.[5] 대부분의 전통적인 군집화 방법은 군집이 구형, 타원형 또는 볼록한 모양을 띤다고 가정한다.[8]

연결성 기반 군집화 (계층적 군집화)

[편집]

계층적 군집화로도 알려진 연결성 기반 군집화는 객체들이 멀리 있는 객체보다 가까이 있는 객체와 더 관련이 있다는 핵심 아이디어를 기반으로 한다. 이러한 알고리즘은 거리에 따라 "객체"를 연결하여 "군집"을 형성한다. 군집은 주로 군집의 각 부분을 연결하는 데 필요한 최대 거리로 설명될 수 있다. 거리에 따라 서로 다른 군집이 형성되며, 이는 덴드로그램을 사용하여 나타낼 수 있다. 여기서 "계층적 군집화"라는 일반적인 명칭이 유래되었다. 이 알고리즘들은 자료 집합의 단일 분할을 제공하는 대신, 특정 거리에서 서로 병합되는 군집들의 광범위한 계층 구조를 제공한다. 덴드로그램에서 y축은 군집이 병합되는 거리를 표시하고, x축은 군집이 섞이지 않도록 객체들을 배치한다.

연결성 기반 군집화는 거리를 계산하는 방식에 따라 달라지는 일련의 방법들이다. 일반적인 거리 함수의 선택 외에도, 사용자는 연결 기준(군집이 여러 객체로 구성되므로 거리를 계산할 후보가 여러 개 있음)을 결정해야 한다. 대중적인 선택으로는 단일 연결 군집화(최단 거리), 완전 연결 군집화(최장 거리), UPGMA 또는 WPGMA(평균 연결 군집화)가 있다. 또한, 계층적 군집화는 응집형(단일 요소에서 시작하여 군집으로 결합) 또는 분할형(전체 자료 집합에서 시작하여 분할)일 수 있다.

이러한 방법들은 자료 집합의 고유한 분할을 생성하지 않으며, 사용자가 계층 구조에서 적절한 군집을 선택해야 한다. 이상치에 대해 그리 견고하지 않은데, 이상치는 별도의 군집으로 나타나거나 심지어 다른 군집들이 병합되게 만들기도 한다(특히 단일 연결 군집화에서 나타나는 "연쇄 현상"으로 알려져 있음). 일반적인 경우 복잡도는 응집형 군집화의 경우 𝒪(n3), 분할형 군집화의 경우 𝒪(2n−1)이며[9], 이로 인해 대규모 자료 집합에서는 너무 느리다. 일부 특수한 경우, 최적의 효율적인 방법(복잡도 𝒪(n2))이 알려져 있다. 단일 연결의 경우 SLINK[10], 완전 연결 군집화의 경우 CLINK[11]가 그것이다.

무게 중심 기반 군집화

[편집]

무게 중심 기반 군집화에서 각 군집은 중심 벡터로 표현되며, 이 벡터가 반드시 자료 집합의 구성원일 필요는 없다. 군집의 수가 k로 고정되었을 때, K-평균 군집화는 최적화 문제로서 공식적인 정의를 제공한다. 즉, 군집으로부터의 거리 제곱합이 최소화되도록 k개의 군집 중심을 찾고 객체들을 가장 가까운 군집 중심에 할당하는 것이다.

최적화 문제 자체는 NP-난해로 알려져 있어, 일반적인 접근 방식은 근사 해만을 찾는 것이다. 특히 잘 알려진 근사 방법은 로이드 알고리즘이며[12], 종종 단순히 "K-평균 알고리즘"으로 불린다(비록 다른 알고리즘이 이 이름을 먼저 도입했지만). 그러나 이는 지역 최적해만을 찾을 뿐이므로, 서로 다른 무작위 초기화를 사용하여 여러 번 실행하는 것이 일반적이다. K-평균의 변형들은 대개 여러 실행 중 최선의 결과를 선택하거나, 무게 중심을 자료 집합의 구성원으로 제한(K-메도이드), 중앙값 선택(K-중앙값 군집화), 초기 중심을 덜 무작위하게 선택(K-평균++), 또는 퍼지 군집 할당을 허용(퍼지 C-평균)하는 등의 최적화를 포함한다.

대부분의 K-평균 유형 알고리즘은 군집의 수인 k를 사전에 지정해야 하며, 이는 이 알고리즘들의 가장 큰 단점 중 하나로 간주된다. 또한, 이 알고리즘들은 객체를 항상 가장 가까운 무게 중심에 할당하기 때문에 대략적으로 비슷한 크기의 군집을 선호하며, 이는 종종 군집 경계가 부적절하게 잘리는 결과를 낳는다. 이는 주로 알고리즘이 군집 경계가 아닌 군집 중심을 최적화하기 때문에 발생한다. 무게 중심 기반 군집화 알고리즘의 단계는 다음과 같다.

  1. 무작위로 k개의 서로 다른 군집을 선택한다. 이들은 개선될 초기 무게 중심이다.
  2. 관측값 집합 (x1, x2, ..., xn)에 대하여, 각 관측값을 제곱 유클리드 거리가 가장 작은 무게 중심에 할당한다. 결과적으로 고유한 관측값들을 포함하는 k개의 구별된 그룹이 생긴다.
  3. 무게 중심을 다시 계산한다(K-평균 알고리즘 참조).
  4. 새로운 무게 중심이 이전 반복의 무게 중심과 동일하면 종료한다. 그렇지 않으면 알고리즘을 반복한다. 무게 중심이 아직 수렴하지 않은 것이다.

K-평균은 몇 가지 흥미로운 이론적 특성을 가진다. 첫째, 데이터 공간을 보로노이 다이어그램으로 알려진 구조로 분할한다. 둘째, 개념적으로 최근접 이웃 분류와 가까워 기계 학습에서 인기가 높다. 셋째, 모델 기반 군집화의 변형으로 볼 수 있으며, 로이드 알고리즘은 아래에서 논의할 이 모델에 대한 기댓값 최대화 알고리즘의 변형으로 볼 수 있다.

K-평균 및 K-메도이드와 같은 무게 중심 기반 군집화 문제는 운영 연구 및 계산 기하학 커뮤니티의 전형적인 문제인 비제약 미터릭 시설 배치 문제의 특수한 사례이다. 기본 시설 배치 문제에서 과제는 주어진 소비자 집합에 최적으로 서비스를 제공하기 위한 최적의 창고 위치를 찾는 것이다. 여기서 "창고"를 군집 무게 중심으로, "소비자 위치"를 군집화할 데이터로 볼 수 있다. 이를 통해 시설 배치 문헌의 잘 개발된 알고리즘 솔루션을 무게 중심 기반 군집화 문제에 적용하는 것이 가능해진다.

모델 기반 군집화

[편집]

통계학과 가장 밀접하게 관련된 군집화 프레임워크는 분포 모델에 기반한 모델 기반 군집화이다. 이 접근 방식은 데이터를 확률 분포의 혼합에서 발생하는 것으로 모델링한다. 이는 군집이 몇 개인지, 어떤 군집화 방법이나 모델을 사용할지, 그리고 이상치를 어떻게 탐지하고 처리할지에 대한 질문에 원칙적인 통계적 답변을 제공한다는 장점이 있다.

이러한 방법들의 이론적 기반은 훌륭하지만, 모델 복잡성에 제약을 두지 않으면 과적합 문제를 겪는다. 더 복잡한 모델은 대개 데이터를 더 잘 설명할 수 있기 때문에, 적절한 모델 복잡성을 선택하는 것이 본질적으로 어렵다. 표준적인 모델 기반 군집화 방법에는 공분산 행렬의 고윳값 분해에 기반한 더 절약적인 모델이 포함되며, 이는 과적합과 데이터에 대한 충실도 사이의 균형을 제공한다.

하나의 두드러진 방법은 가우시안 혼합 모델(기댓값 최대화 알고리즘 사용)이다. 여기서 자료 집합은 대개 무작위로 초기화되고 매개변수가 데이터를 더 잘 맞추도록 반복적으로 최적화되는 고정된 수(과적합 방지용)의 가우시안 분포로 모델링된다. 이는 지역 최적해로 수렴하므로 여러 번 실행하면 서로 다른 결과가 나올 수 있다. 하드 군집화를 얻기 위해 객체들은 대개 가장 속할 가능성이 높은 가우시안 분포에 할당되며, 소프트 군집화의 경우에는 이것이 필요하지 않다.

분포 기반 군집화는 속성 간의 상관 관계와 의존성을 포착할 수 있는 복잡한 군집 모델을 생성한다. 그러나 이러한 알고리즘은 사용자에게 추가적인 부담을 준다. 많은 실제 자료 집합에 대해 간결하게 정의된 수학적 모델이 없을 수 있기 때문이다(예: 가우시안 분포를 가정하는 것은 데이터에 대한 다소 강한 가정이다).

밀도 기반 군집화

[편집]

밀도 기반 군집화에서[13] 군집은 나머지 자료 집합보다 밀도가 높은 영역으로 정의된다. 군집을 분리하는 데 필요한 희소한 영역의 객체들은 대개 노이즈 및 경계점으로 간주된다.

가장 대중적인[14] 밀도 기반 군집화 방법은 DBSCAN이다.[15] 많은 최신 방법과 대조적으로, 이는 "밀도 도달 가능성"이라 불리는 잘 정의된 군집 모델을 특징으로 한다. 연결 기반 군집화와 유사하게, 이는 특정 거리 임계값 내의 점들을 연결하는 것을 기반으로 한다. 그러나 이는 밀도 기준(원래 변형에서는 이 반경 내의 다른 객체의 최소 수로 정의됨)을 만족하는 점들만 연결한다. 군집은 밀도로 연결된 모든 객체(다른 많은 방법과 달리 임의의 모양의 군집을 형성할 수 있음)와 이러한 객체의 범위 내에 있는 모든 객체로 구성된다. DBSCAN의 또 다른 흥미로운 특성은 복잡성이 상당히 낮고(데이터베이스에 대한 선형적인 범위 질의가 필요함), 매 실행마다 본질적으로 동일한 결과(핵심 점과 노이즈 점에 대해서는 결정론적 알고리즘이지만 경계 점에 대해서는 아님)를 발견하므로 여러 번 실행할 필요가 없다는 것이다. OPTICS[16]는 범위 매개변수인 ε에 대해 적절한 값을 선택해야 하는 필요성을 제거한 DBSCAN의 일반화 버전으로, 연결 군집화와 관련된 계층적 결과를 생성한다. DeLi-Clu[17](Density-Link-Clustering)는 단일 연결 군집화와 OPTICS의 아이디어를 결합하여 ε 매개변수를 완전히 제거하고 R 트리 인덱스를 사용하여 OPTICS보다 성능을 개선했다. HDBSCAN[18]은 DBSCAN을 계층적 군집화 알고리즘으로 변환한 후 군집의 안정성에 기반하여 평면 군집을 추출하는 기법을 사용하여 이를 확장한다.

DBSCAN과 OPTICS의 주요 단점은 군집 경계를 감지하기 위해 밀도 하강이 발생할 것을 기대한다는 점이다. 예를 들어 인공 데이터에서 흔히 볼 수 있는 중첩된 가우시안 분포가 있는 자료 집합의 경우, 군집 밀도가 연속적으로 감소하기 때문에 이 알고리즘들이 생성하는 군집 경계는 종종 임의적으로 보일 수 있다. 가우시안 혼합 자료 집합에서 이러한 알고리즘은 이러한 유형의 데이터를 정밀하게 모델링할 수 있는 EM 군집화와 같은 방법보다 거의 항상 성능이 뒤처진다.

커널 밀도 추정에 기반하여 각 객체를 인근의 가장 밀집된 영역으로 이동시키는 군집화 접근 방식인 평균 이동(Mean-shift)도 있다. 결국 객체들은 밀도의 지역 극대값으로 수렴한다. K-평균 군집화와 유사하게 이러한 "밀도 어트랙터(attractors)"는 자료 집합의 대표 역할을 할 수 있지만, 평균 이동은 DBSCAN과 유사하게 임의의 모양의 군집을 탐지할 수 있다. 값비싼 반복 절차와 밀도 추정으로 인해 평균 이동은 일반적으로 DBSCAN이나 K-평균보다 느리다. 그 외에도 다차원 데이터에 대한 평균 이동 알고리즘의 적용은 커널 밀도 추정의 매끄럽지 않은 동작으로 인해 방해를 받으며, 이는 군집 꼬리 부분의 과도한 파편화를 초래한다.[17]

격자 기반 군집화

[편집]

격자 기반 기법은 다차원 자료 집합에 사용된다.[19] 이 기법에서는 격자 구조를 생성하고 격자(셀이라고도 함)를 바탕으로 비교를 수행한다. 격자 기반 기법은 속도가 빠르고 계산 복잡도가 낮다. 격자 기반 군집화 방법에는 STING과 CLIQUE의 두 가지 유형이 있다. 격자 기반 군집화 알고리즘의 단계는 다음과 같다.

  1. 데이터 공간을 유한한 수의 셀로 나눈다.
  2. 이전에 탐색하지 않은 셀 'c'를 무작위로 선택한다.
  3. 'c'의 밀도를 계산한다.
  4. 'c'의 밀도가 임계 밀도보다 큰 경우
    1. 셀 'c'를 새로운 군집으로 표시한다.
    2. 'c'의 모든 이웃 셀의 밀도를 계산한다.
    3. 이웃 셀의 밀도가 임계 밀도보다 큰 경우, 해당 셀을 군집에 추가하고 임계 밀도보다 큰 밀도를 가진 이웃이 없을 때까지 4.2와 4.3단계를 반복한다.
  5. 모든 셀을 탐색할 때까지 2, 3, 4단계를 반복한다.
  6. 종료한다.

최근의 발전

[편집]

최근 몇 년 동안 기존 알고리즘의 성능을 개선하기 위해 상당한 노력이 기울여졌다.[20][21] 그중에는 CLARANS와 BIRCH가 있다. 최근 더 큰 자료 집합(빅 데이터)을 처리해야 할 필요성이 커짐에 따라, 성능을 위해 생성된 군집의 의미론적 의미를 어느 정도 희생하려는 경향이 늘어났다. 이는 거대한 자료 집합을 효율적으로 처리할 수 있는 캐노피 군집화(canopy clustering)와 같은 전처리 군집화 방법의 개발로 이어졌으나, 결과물인 "캐노피"는 단지 자료 집합의 대략적인 전분할일 뿐이며, 이후 K-평균 군집화와 같은 기존의 느린 방법으로 분할을 분석해야 한다.

고차원 데이터의 경우, 기존 방법 중 상당수가 차원의 저주로 인해 실패하는데, 이는 고차원 공간에서 특정 거리 함수를 문제 있게 만든다. 이로 인해 부분공간 군집화(일부 속성만 사용되고 군집 모델이 군집의 관련 속성을 포함하는 방식)와 속성들의 상관 관계를 제공하여 모델링할 수 있는 임의로 회전된("상관된") 부분공간 군집을 찾는 상관 군집화에 초점을 맞춘 새로운 고차원 데이터용 군집화 알고리즘이 개발되었다.[22] 이러한 군집화 알고리즘의 예로는 CLIQUE와 SUBCLU가 있다.

밀도 기반 군집화 방법(특히 DBSCAN/OPTICS 계열 알고리즘)의 아이디어가 부분공간 군집화(HiSC, 계층적 부분공간 군집화 및 DiSH)와 상관 군집화(HiCO, 계층적 상관 군집화, "상관 연결성"을 사용하는 4C, 계층적 밀도 기반 상관 군집을 탐색하는 ERiC)에 맞게 조정되었다.

상호정보에 기반한 여러 군집화 시스템이 제안되었다. 하나는 마리나 메일러(Marina Meilă)의 정보 변이 지표이며, 다른 하나는 계층적 군집화를 제공한다.[23] 유전 알고리즘을 사용하면 상호정보를 포함한 광범위한 적합 함수를 최적화할 수 있다.[24] 또한 컴퓨터 과학과 통계물리학의 최근 발전인 신뢰전파는 새로운 유형의 군집화 알고리즘 생성으로 이어졌다.[25]

평가 및 사정

[편집]

군집 결과의 평가(또는 "검증")는 군집화 자체만큼이나 어렵다.[26] 대중적인 접근 방식에는 군집화 결과가 단일 품질 점수로 요약되는 "내부" 평가, 군집화를 기존의 "최적표준" 분류와 비교하는 "외부" 평가, 인간 전문가에 의한 "수동" 평가, 그리고 의도된 응용 분야에서 군집화의 유용성을 평가하는 "간접" 평가가 있다.[27]

내부 평가 지표는 지표 자체가 군집화 목표로 간주될 수 있는 함수를 나타낸다는 문제점이 있다. 예를 들어, 실루엣 계수에 따라 자료 집합을 군집화할 수 있지만, 이를 위한 알려진 효율적인 알고리즘이 없다. 평가를 위해 이러한 내부 지표를 사용하면 최적화 문제의 유사성을 비교하게 될 뿐이며[27], 군집화가 얼마나 유용한지를 반드시 나타내는 것은 아니다.

외부 평가도 비슷한 문제를 안고 있다. 만약 "최적표준" 라벨이 있다면 군집화할 필요가 없을 것이며, 실제 응용에서는 대개 그러한 라벨이 없다. 반면, 라벨은 자료 집합의 가능한 분할 중 하나만을 반영할 뿐이며, 이는 다른 그리고 어쩌면 더 나은 군집화가 존재하지 않음을 의미하지 않는다.

따라서 이러한 접근 방식 중 어느 것도 군집화의 실제 품질을 최종적으로 판단할 수 없으며, 매우 주관적인 인간의 평가가 필요하다.[27] 그럼에도 불구하고 이러한 통계는 나쁜 군집화를 식별하는 데 꽤 유익할 수 있지만,[28] 주관적인 인간 평가를 무시해서는 안 된다.[28]

내부 평가

[편집]

군집화 결과가 군집화된 데이터 자체를 기반으로 평가될 때 이를 내부 평가라고 한다. 이러한 방법들은 대개 군집 내 유사도가 높고 군집 간 유사도가 낮은 군집을 생성하는 알고리즘에 가장 좋은 점수를 부여한다. 군집 평가에 내부 기준을 사용할 때의 한 가지 단점은 내부 지표에서 높은 점수가 반드시 효과적인 정보 검색 응용으로 이어지지는 않는다는 점이다.[29] 또한, 이 평가는 동일한 군집 모델을 사용하는 알고리즘에 편향되어 있다. 예를 들어, K-평균 군집화는 본질적으로 객체 거리를 최적화하므로 거리 기반 내부 기준은 결과 군집을 과대평가할 가능성이 높다.

따라서 내부 평가 지표는 한 알고리즘이 다른 알고리즘보다 성능이 나은 상황에 대한 통찰을 얻는 데 가장 적합하지만, 이것이 한 알고리즘이 다른 알고리즘보다 더 유효한 결과를 낸다는 것을 의미하지는 않는다.[5] 이러한 지수로 측정된 유효성은 데이터 세트에 이러한 종류의 구조가 존재한다는 주장에 달려 있다. 어떤 종류의 모델을 위해 설계된 알고리즘은 자료 집합이 근본적으로 다른 모델 세트를 포함하거나 평가 지표가 근본적으로 다른 기준을 측정한다면 성공할 가능성이 없다.[5] 예를 들어, K-평균 군집화는 볼록한 군집만 찾을 수 있으며 많은 평가 지표는 볼록한 군집을 가정한다. 비볼록 군집이 있는 자료 집합에서 K-평균을 사용하거나 볼록성을 가정하는 평가 기준을 사용하는 것은 타당하지 않다.

클러스터 분석 결과를 사정하기 위해 다음과 같은 여러 내부 군집 점수를 사용할 수 있다. 실루엣 계수, 데이비스-볼딘 지수, 던 지수, 칼린스키-하라바즈 지수, 섀넌 엔트로피, 갭 통계량(Gap statistic) 등.[30]

많은 내부 평가 지표는 같은 군집의 항목들이 서로 다른 군집의 항목들보다 더 유사해야 한다는 직관에 기반한다.[31]: 115–121  예를 들어, 내부 기준을 바탕으로 군집 알고리즘의 품질을 사정하는 데 다음 방법들을 사용할 수 있다.

데이비스-볼딘 지수

[편집]

데이비스-볼딘 지수는 다음 공식으로 계산할 수 있다. DB=1n∑i=1nmaxj≠i(σi+σjd(ci,cj)) 여기서 n은 군집 수, ci는 군집 i의 무게 중심, σi는 군집 i의 모든 원소에서 무게 중심 ci까지의 평균 거리, d(ci,cj)는 무게 중심 ci와 cj 사이의 거리이다. 군집 내 거리가 낮고(군집 내 유사도 높음) 군집 간 거리가 높은(군집 간 유사도 낮음) 군집을 생성하는 알고리즘은 낮은 데이비스-볼딘 지수를 갖게 되므로, 이 지수가 가장 작은 알고리즘이 이 기준에 따라 가장 좋은 알고리즘으로 간주된다.

던 지수

[편집]

던 지수는 조밀하고 잘 분리된 군집을 식별하는 것을 목표로 한다. 이는 군집 간 최소 거리에 대한 군집 내 최대 거리의 비율로 정의된다. 각 군집 분할에 대해 던 지수는 다음 공식으로 계산할 수 있다.[32]

D=min1≤i<j≤nd(i,j)max1≤k≤nd′(k),

여기서 d(i,j)는 군집 i와 j 사이의 거리를 나타내고, d '(k)는 군집 k의 군집 내 거리를 측정한다. 두 군집 사이의 군집 간 거리 d(i,j)는 군집의 무게 중심 사이의 거리와 같이 다양한 거리 측정값일 수 있다. 마찬가지로 군집 내 거리 d '(k)는 군집 k 내의 임의의 두 원소 사이의 최대 거리와 같이 다양한 방식으로 측정될 수 있다. 내부 기준은 높은 군집 내 유사성과 낮은 군집 간 유사성을 추구하므로, 던 지수가 높은 군집을 생성하는 알고리즘이 더 바람직하다.

실루엣 계수는 같은 군집의 원소들에 대한 평균 거리와 다른 군집의 원소들에 대한 평균 거리를 대조한다. 실루엣 값이 높은 객체는 잘 군집화된 것으로 간주되고, 값이 낮은 객체는 이상치일 수 있다. 이 지수는 K-평균 군집화와 잘 작동하며, 최적의 군집 수를 결정하는 데에도 사용된다.[33]

군집 곡선 아래 면적 (AUCC)

이 메트릭은 객체 쌍을 고려한다. 쌍 사이의 거리를 점수 함수로 사용하고, 쌍들이 같은 군집에 있는지 여부를 고려하여 진양성(true positive), 진음성(true negative), 위음성(false negative), 위양성(false positive) 쌍을 정의한다. 이 지수는 0.5의 기댓값과 결과의 시각화를 포함하여 지도 학습 시나리오의 AUC와 동일한 특성을 차용한다.[34]

외부 평가

[편집]

외부 평가에서는 알려진 클래스 라벨이나 외부 벤치마크와 같이 군집화에 사용되지 않은 데이터를 기반으로 군집화 결과를 평가한다. 이러한 벤치마크는 사전 분류된 항목 집합으로 구성되며, 종종 (전문가) 인간에 의해 생성된다. 따라서 벤치마크 집합은 평가를 위한 최적표준으로 간주될 수 있다.[26] 이러한 유형의 평가 방법은 군집화가 미리 결정된 벤치마크 클래스에 얼마나 가까운지를 측정한다. 그러나 클래스가 내부 구조를 가질 수 있고, 제시된 속성이 군집의 분리를 허용하지 않을 수 있으며, 클래스에 이상치가 포함될 수 있기 때문에 이것이 실제 데이터에 적절한지, 아니면 실제 정답이 있는 합성 자료 집합에만 적합한지에 대해서는 최근 논의가 있어 왔다.[35] 또한 지식 발견의 관점에서 기지의 지식을 재현하는 것이 반드시 의도된 결과가 아닐 수도 있다.[35] 클래스 라벨과 같은 메타 정보가 이미 군집화 과정에서 사용되는 제약 군집화의 특별한 시나리오에서는 평가를 위해 정보를 따로 떼어 두는 것이 간단하지 않다.[36]

분류 과제를 평가하는 데 사용되는 변형들로부터 여러 지표가 채택되었다. 단일 데이터 포인트에 클래스가 올바르게 할당된 횟수를 세는 대신(진양성으로 알려짐), 이러한 쌍 계수 지표는 실제로 같은 군집에 있는 각 데이터 포인트 쌍이 같은 군집에 있을 것으로 예측되는지 사정한다.[26]

내부 평가와 마찬가지로 여러 외부 평가 지표가 존재한다.[31]: 125–129  예를 들면 다음과 같다.

순도 (Purity)

[편집]

순도는 군집이 단일 클래스를 포함하는 정도를 측정하는 지표이다.[29] 그 계산은 다음과 같이 생각할 수 있다. 각 군집에 대해 해당 군집에서 가장 흔한 클래스의 데이터 포인트 수를 센다. 이제 모든 군집에 대해 이 합계를 구하고 전체 데이터 포인트 수로 나눈다. 공식적으로, N개의 데이터 포인트를 분할하는 군집 집합 M과 클래스 집합 D가 주어졌을 때 순도는 다음과 같이 정의될 수 있다.

1N∑m∈Mmaxd∈D|m∩d|

이 지표는 군집이 많은 것에 대해 불이익을 주지 않으며, 군집이 많을수록 높은 순도를 내기 쉬워진다. 각 데이터 포인트를 각자의 군집에 넣으면 순도 점수 1은 항상 가능하다. 또한 순도는 불균형한 데이터에서 잘 작동하지 않는데, 성능이 저조한 군집화 알고리즘조차도 높은 순도 값을 줄 수 있기 때문이다. 예를 들어, 1000개의 데이터 세트가 999개의 포인트를 포함하는 클래스와 1개의 포인트를 포함하는 클래스로 구성된 경우, 가능한 모든 분할은 최소 99.9%의 순도를 갖게 된다.

랜드 지수 (Rand index)

[편집]

랜드 지수[37]는 군집화 알고리즘에 의해 반환된 군집이 벤치마크 분류와 얼마나 유사한지를 계산한다. 다음 공식으로 계산할 수 있다.

RI=TP+TNTP+FP+FN+TN

여기서 TP는 진양성 수, TN은 진음성 수, FP는 위양성 수, FN은 위음성 수이다. 여기서 세는 대상은 올바른 쌍 할당 수이다. 즉, TP는 예측 분할과 정답 분할 모두에서 함께 군집화된 포인트 쌍의 수이고, FP는 예측 분할에서는 함께 군집화되었으나 정답 분할에서는 그렇지 않은 포인트 쌍의 수 등이다. 자료 집합의 크기가 N이면 TP+TN+FP+FN=(N2)이다. 랜드 지수의 한 가지 문제는 위양성과 위음성에 동일한 가중치를 부여한다는 점이다. 이는 일부 군집화 응용에서 바람직하지 않은 특성일 수 있다. F-척도가 이 문제를 다루며, 우연을 보정한 수정 랜드 지수도 마찬가지이다.

F-척도 (F-measure)

[편집]

F-척도는 매개변수 β≥0를 통해 재현율에 가중치를 둠으로써 위음성의 기여도를 조절하는 데 사용될 수 있다. 정밀도와 재현율(둘 다 그 자체로 외부 평가 지표임)을 다음과 같이 정의하자. P=TPTP+FP R=TPTP+FN 여기서 P는 정밀도 비율이고 R은 재현율 비율이다. F-척도는 다음 공식을 사용하여 계산할 수 있다.[29] Fβ=(β2+1)⋅P⋅Rβ2⋅P+R β=0일 때 F0=P이다. 즉, β=0일 때 재현율은 F-척도에 영향을 주지 않으며, β를 높이면 최종 F-척도에서 재현율에 부여되는 가중치가 늘어난다. 또한 TN은 고려되지 않으며 0부터 제한 없이 변할 수 있다.

자카드 지수 (Jaccard index)

[편집]

자카드 지수는 두 자료 집합 간의 유사성을 정량화하는 데 사용된다. 자카드 계수는 0과 1 사이의 값을 가진다. 지수가 1이면 두 자료 집합이 동일함을 의미하고, 0이면 자료 집합에 공통 원소가 없음을 나타낸다. 자카드 지수는 다음 공식으로 정의된다. J(A,B)=|A∩B||A∪B|=TPTP+FP+FN 이는 단순히 두 집합에 공통적인 고유 원소 수를 두 집합에 있는 전체 고유 원소 수로 나눈 것이다. 여기서도 TN은 고려되지 않는다.

다이스 지수 (Dice index)

[편집]

다이스 대칭 척도는 TN을 무시하면서 TP에 가중치를 두 배로 부여한다. DSC=2TP2TP+FP+FN

파울크스-맬로우스 지수 (Fowlkes–Mallows index)

[편집]

파울크스-맬로우스 지수[38]는 군집화 알고리즘이 반환한 군집과 벤치마크 분류 사이의 유사성을 계산한다. 파울크스-맬로우스 지수 값이 높을수록 군집과 벤치마크 분류가 더 유사하다는 뜻이다. 다음 공식으로 계산할 수 있다. FM=TPTP+FP⋅TPTP+FN 여기서 TP는 진양성 수, FP는 위양성 수, FN은 위음성 수이다. FM 지수는 정밀도 P와 재현율 R의 기하 평균이며, 따라서 G-척도라고도 불린다. 반면 F-척도는 이들의 조화 평균이다.[39][40] 또한 정밀도와 재현율은 월리스(Wallace) 지수 BI 및 BII로도 알려져 있다.[41] 재현율, 정밀도 및 G-척도의 우연 정규화 버전은 정보성(Informedness), 표식성(Markedness) 및 매튜스 상관 계수에 대응하며 카파와 강하게 연관된다.[42]

Chi 지수

[편집]

Chi 지수[43]는 카이제곱 통계량을 적용하여 군집화 결과를 측정하는 외부 검증 지수이다. 이 지수는 라벨이 군집 전반에 걸쳐 가능한 한 희소하게 분포되어 있다는 점, 즉 각 군집이 가능한 한 적은 종류의 라벨을 가지고 있다는 점에 대해 긍정적인 점수를 부여한다. Chi 지수 값이 높을수록 결과 군집과 사용된 라벨 사이의 관계가 크다는 것을 의미한다.

상호정보는 두 군집 사이의 비선형 유사성을 감지할 수 있는 정보 이론적 척도로, 군집화와 정답 분류 사이에 얼마나 많은 정보가 공유되는지를 측정한다. 정규화 상호정보는 군집 수의 변화에 따른 편향을 줄인 우연 보정 변형군이다.[26]

혼동 행렬은 분류(또는 군집화) 알고리즘의 결과를 신속하게 시각화하는 데 사용될 수 있다. 이는 군집이 최적표준 군집과 얼마나 다른지를 보여준다.

유효성 척도 (V-measure)

[편집]

유효성 척도(V-measure)는 군집의 동질성과 완전성을 결합한 지표이다.[44]

군집 경향성

[편집]

군집 경향성을 측정하는 것은 군집화를 시도하기 전, 군집화할 데이터에 군집이 어느 정도 존재하는지 측정하는 것이며 초기 테스트로 수행될 수 있다. 한 가지 방법은 데이터를 무작위 데이터와 비교하는 것이다. 평균적으로 무작위 데이터에는 군집이 없어야 한다.

홉킨스 통계량에는 여러 공식이 있다.[45] 전형적인 공식은 다음과 같다.[46] X를 d차원 공간에 있는 n개의 데이터 포인트 집합이라고 하자. 구성원이 xi인 m≪n개의 데이터 포인트의 무작위 표본(비복원)을 고려한다. 또한 균등 무작위 분포를 가진 m개의 데이터 포인트 집합 Y를 생성한다. 이제 두 가지 거리 측정값을 정의한다. ui는 yi∈Y로부터 X에서의 최근접 이웃까지의 거리이고, wi는 xi∈X로부터 X에서의 최근접 이웃까지의 거리이다. 그러면 홉킨스 통계량은 다음과 같이 정의된다.
H=∑i=1muid∑i=1muid+∑i=1mwid,
이 정의에 따르면, 균등 무작위 데이터는 0.5에 가까운 값을 갖는 경향이 있고, 군집화된 데이터는 1에 더 가까운 값을 갖는 경향이 있다.
그러나 단일 가우시안만을 포함하는 데이터도 1에 가까운 점수를 받게 되는데, 이 통계량은 다봉성이 아니라 균등 분포로부터의 편차를 측정하기 때문이다. 이로 인해 이 통계량은 응용 분야에서 대체로 유용하지 않다(실제 데이터는 결코 균등에 가깝지 않기 때문).

응용

[편집]

생물학, 계산 생물학 및 생물정보학

[편집]
식물 및 동물 생태학
클러스터 분석은 불균일한 환경에서 생물 공동체(군집)의 공간적 및 시간적 비교를 설명하고 수행하는 데 사용된다. 또한 식물 계통분류학에서 여러 속성을 공유하는 종, 속 또는 그 이상의 수준에서 인위적인 계통수나 생물체(개체) 군집을 생성하는 데 사용된다.
전사체학
군집화는 HCS 군집화 알고리즘에서와 같이 관련 발현 패턴을 가진 유전자 그룹(공발현 유전자라고도 함)을 구축하는 데 사용된다.[47][48] 이러한 그룹에는 특정 대사경로의 효소와 같이 기능적으로 관련된 단백질이나 공동 조절되는 유전자가 포함되는 경우가 많다. 발현 서열 태그(EST)나 DNA 마이크로어레이를 사용한 고효율 실험은 유전체학의 일반적인 측면인 유전체 주석(genome annotation)을 위한 강력한 도구가 될 수 있다.
서열 분석
서열 군집화는 상동 서열을 유전자 가족으로 그룹화하는 데 사용된다.[49] 이는 생물정보학 및 일반적인 진화생물학에서 매우 중요한 개념이다. 유전자 중복에 의한 진화를 참조하라.
고효율 유전자형 분석 플랫폼
군집화 알고리즘은 유전자형을 자동으로 할당하는 데 사용된다.[50]
인류 유전 군집화
유전 데이터의 유사성은 인구 구조를 추론하기 위한 군집화에 사용된다.
의학촬영
PET 스캔에서 클러스터 분석은 여러 목적을 위해 3차원 이미지 내의 서로 다른 유형의 조직을 구별하는 데 사용될 수 있다.[51]
항균 활성 분석
클러스터 분석은 항생제 내성 패턴을 분석하거나, 작용 기전에 따라 항균 화합물을 분류하거나, 항균 활성에 따라 항생제를 분류하는 데 사용될 수 있다.
IMRT 분할
군집화는 플루언스 맵(fluence map)을 구별된 영역으로 나누어 MLC 기반 방사선 치료에서 전달 가능한 필드로 변환하는 데 사용될 수 있다.

비즈니스 및 마케팅

[편집]
시장 조사
클러스터 분석은 설문 및 테스트 패널의 다변량 데이터를 다룰 때 시장 조사에서 널리 사용된다. 시장 조사원들은 클러스터 분석을 사용하여 일반 소비자 층을 시장 세그먼트로 분할하고, 서로 다른 소비자/잠재 고객 그룹 사이의 관계를 더 잘 이해하며, 시장세분화, 제품 포지셔닝, 신제품 개발 및 테스트 시장 선택에 사용한다.
쇼핑 항목 그룹화
군집화는 웹에서 사용 가능한 모든 쇼핑 항목을 고유한 제품 세트로 그룹화하는 데 사용될 수 있다. 예를 들어, eBay의 모든 항목을 고유한 제품으로 그룹화할 수 있다(eBay에는 SKU 개념이 없음).
사회 연결망 분석
사회 연결망 연구에서 군집화는 대규모 사람들 집단 내의 커뮤니티를 인식하는 데 사용될 수 있다.
검색 결과 그룹화
파일 및 웹사이트의 지능형 그룹화 과정에서 군집화는 구글과 같은 일반 검색 엔진에 비해 더 관련성 있는 검색 결과 세트를 생성하는 데 사용될 수 있다. 현재 Clusty와 같은 여러 웹 기반 군집화 도구가 있다. 또한 검색어가 매우 다른 대상을 가리킬 수 있는 경우 더 포괄적인 결과 세트를 반환하는 데 사용될 수도 있다. 용어의 각기 다른 용도는 고유한 결과 군집에 대응하며, 순위 알고리즘이 각 군집에서 상위 결과를 선택함으로써 포괄적인 결과를 반환할 수 있게 한다.[52]
슬리피 맵(Slippy map) 최적화
플리커의 사진 지도 및 기타 지도 사이트들은 지도의 마커 수를 줄이기 위해 군집화를 사용한다. 이는 속도를 높이고 시각적 혼란을 줄여준다.
소프트웨어 진화
군집화는 분산된 기능을 재구성하여 코드의 레거시 속성을 줄이는 데 도움이 되므로 소프트웨어 진화에 유용하다. 이는 구조 재조정의 한 형태이며 따라서 직접적인 예방 유지보수의 방법이다.
영상 분할
영상 분할은 디지털 이미지를 여러 의미 있는 영역이나 세그먼트로 나누어 이미지 표현을 단순화하거나 변경하여 분석하기 쉽게 만드는 과정이다. 이러한 세그먼트는 서로 다른 객체, 객체의 일부 또는 배경 영역에 대응할 수 있다. 목표는 이미지의 모든 픽셀에 라벨을 할당하여 유사한 속성을 가진 픽셀들이 함께 그룹화되도록 하는 것이다.
이 과정은 의학촬영, 컴퓨터 비전, 위성 영상과 같은 분야와 얼굴 인식, 사진 편집과 같은 일상적인 응용에서 사용된다.
알래스카 베어 호수 위의 오로라
알래스카 베어 호수 위의 오로라
Polarlicht 2 kmeans 16 large
k = 16으로 K-평균 군집화를 실행한 후의 이미지
영상 분할에서의 군집화:
군집화는 영상 분할에서 중요한 역할을 한다. 라벨이 지정된 데이터 없이 유사성에 따라 픽셀을 군집으로 그룹화한다. 이러한 군집들은 이미지 내의 세그먼트를 정의한다.
영상 분할에 가장 흔히 사용되는 군집화 알고리즘은 다음과 같다.
  1. K-평균 알고리즘: 가장 인기 있고 간단한 방법 중 하나이다. 픽셀을 특징 공간(대개 색상이나 강도로 정의됨)의 데이터 포인트로 취급하고 k개의 군집으로 그룹화한다. 각 픽셀은 가장 가까운 군집 중심에 할당되고, 중심은 반복적으로 업데이트된다.
  2. 평균 이동 군집화(Mean shift): 사전에 군집 수를 지정할 필요가 없는 비모수적 방법이다. 특징 공간에서 데이터 포인트가 밀집된 영역을 찾아 군집을 식별한다.
  3. 퍼지 C-평균: 픽셀을 정확히 하나의 군집에 할당하는 K-평균과 달리, 퍼지 C-평균은 각 픽셀이 다양한 소속도로 여러 군집에 속할 수 있게 한다.
진화 알고리즘
군집화는 진화 알고리즘의 개체군 내에서 서로 다른 니치(niches)를 식별하여, 진화하는 종이나 아종 사이에 번식 기회가 더 고르게 분산될 수 있도록 하는 데 사용될 수 있다.
추천 시스템
추천 시스템은 개인의 과거 행동과 현재 선호도를 바탕으로 항목, 제품 또는 다른 사용자를 제안한다. 이러한 시스템은 동일한 군집 내 다른 사용자들의 선호도와 활동을 분석하여 사용자의 알려지지 않은 선호도를 예측하기 위해 군집화 알고리즘을 사용하기도 한다. 클러스터 분석만이 추천 시스템의 유일한 접근 방식은 아니며, 예를 들어 그래프 이론을 활용하는 시스템도 있다. 클러스터 분석을 활용하는 추천 알고리즘은 대개 세 가지 주요 범주 중 하나에 속한다. 협업 필터링, 콘텐츠 기반 필터링, 그리고 협업 및 콘텐츠 기반의 하이브리드 방식이다.


협업 필터링 추천 알고리즘
협업 필터링은 사용자 행동, 선호도 및 활동에 대한 대량의 데이터를 분석하여 타인과의 유사성을 바탕으로 사용자가 무엇을 좋아할지 예측한다. 사용자가 항목에 점수를 매기는 패턴을 탐지하고 유사한 사용자나 항목을 별도의 "이웃"으로 그룹화한다. 그런 다음 동일한 이웃 내의 타인으로부터 콘텐츠 평점을 활용하여 추천이 생성된다. 알고리즘은 상황에 따라 사용자 기반 또는 항목 기반 그룹화에 집중할 수 있다.[53]
추천 시스템의 기본적이고 일반적인 접근 방식과 군집화를 활용하는 방법을 보여주는 흐름도


콘텐츠 기반 필터링 추천 알고리즘
콘텐츠 기반 필터링은 항목 설명과 사용자의 선호도 프로필을 사용하여 사용자가 이전에 좋아했던 항목과 유사한 특성을 가진 항목을 추천한다. 항목 군집 또는 "이웃"의 특징 벡터 사이의 거리를 평가한다. 사용자의 과거 상호작용은 가중 특징 벡터로 표현되며, 이는 이러한 군집들과 비교된다. 추천은 사용자의 선호도와 거리가 가장 가까운 것으로 평가된 군집을 식별함으로써 생성된다.[53]


하이브리드 추천 알고리즘
하이브리드 추천 알고리즘은 특정 사용 사례의 요구 사항을 더 잘 충족하기 위해 협업 필터링과 콘텐츠 기반 필터링을 결합한다. 어떤 경우에는 이 접근 방식이 더 효과적인 추천으로 이어진다. 일반적인 전략에는 (1) 협업 및 콘텐츠 기반 필터링을 별도로 실행하고 결과를 결합하기, (2) 한 가지 접근 방식에 다른 방식의 특정 기능을 추가하기, (3) 두 하이브리드 방법을 하나의 모델로 통합하기 등이 있다.[53]
마르코프 연쇄 몬테카를로 방법
군집화는 종종 대상 분포에서 극값을 찾고 특성화하는 데 활용된다.
이상 탐지
이상치/이상치는 대개 명시적이든 암묵적이든 데이터의 군집 구조와 관련하여 정의된다.
자연어 처리
군집화는 어휘적 중의성을 해결하는 데 사용될 수 있다.[52]
데브옵스
군집화는 데브옵스 팀의 효과성을 분석하는 데 사용되어 왔다.[54]

사회 과학

[편집]
사회 과학에서의 서열 분석
클러스터 분석은 예를 들어 가정 생활 궤적, 직업 경력, 일상적 또는 주간 시간 사용 패턴을 식별하는 데 사용된다.
범죄 분석
클러스터 분석은 특정 유형의 범죄 발생률이 더 높은 지역을 식별하는 데 사용될 수 있다. 일정 기간 동안 유사한 범죄가 발생한 이러한 구별된 영역 또는 "핫스팟"을 식별함으로써 법 집행 자원을 더 효과적으로 관리할 수 있다.
교육 데이터 마이닝
클러스터 분석은 예를 들어 유사한 특성을 가진 학교나 학생 그룹을 식별하는 데 사용된다.
유형학
여론 조사 데이터에서 퓨 리서치 센터(Pew Research Center)와 같은 프로젝트는 정치 및 마케팅에서 유용할 수 있는 의견, 습관 및 인구 통계의 유형을 식별하기 위해 클러스터 분석을 사용한다.

기타

[편집]
필드 로보틱스
군집화 알고리즘은 물체를 추적하고 센서 데이터에서 이상치를 탐지하기 위한 로봇 상황 인식에 사용된다.[55]
계량화학
구조적 유사성 등을 찾기 위해, 예를 들어 3,000개의 화학 화합물이 90개의 위상 지수 공간에서 군집화되었다.[56]
기후학
날씨 체계나 선호되는 해면 기압 대기 패턴을 찾기 위해 사용된다.[57]
금융
클러스터 분석은 주식을 섹터별로 군집화하는 데 사용되어 왔다.[58]
석유 지질학
클러스터 분석은 저류층 특성을 평가하기 위해 누락된 시추공 코어 데이터나 누락된 로그 곡선을 재구성하는 데 사용된다.
지질화학
서로 다른 샘플 위치에서 화학적 특성의 군집화에 사용된다.

같이 보기

[편집]

각주

[편집]
  1. ↑ Driver and Kroeber (1932). 《Quantitative Expression of Cultural Relationships》. 《University of California Publications in American Archaeology and Ethnology》. Quantitative Expression of Cultural Relationships (Berkeley, CA: University of California Press). 211–256쪽. 2020년 12월 6일에 원본 문서에서 보존된 문서. 2019년 2월 18일에 확인함.
  2. ↑ Zubin, Joseph (1938). 《A technique for measuring like-mindedness.》 (영어). 《The Journal of Abnormal and Social Psychology》 33. 508–516쪽. doi:10.1037/h0055441. ISSN 0096-851X.
  3. ↑ Tryon, Robert C. (1939). 《Cluster Analysis: Correlation Profile and Orthometric (factor) Analysis for the Isolation of Unities in Mind and Personality》. Edwards Brothers.
  4. ↑ Cattell, R. B. (1943). 《The description of personality: Basic traits resolved into clusters》. 《Journal of Abnormal and Social Psychology》 38. 476–506쪽. doi:10.1037/h0054116.
  5. 1 2 3 4 5 6 Estivill-Castro, Vladimir (2002년 6월 20일). 《Why so many clustering algorithms – A Position Paper》. 《ACM SIGKDD Explorations Newsletter》 4. 65–75쪽. doi:10.1145/568574.568575. S2CID 7329935.
  6. ↑ James A. Davis (May 1967) "Clustering and structural balance in graphs", Human Relations 20:181–7
  7. ↑ Kleinberg, Jon (2002). 《An Impossibility Theorem for Clustering》 (PDF). Advances in Neural Information Processing Systems. MIT Press.
  8. ↑ Gao, Caroline X.; Dwyer, Dominic; Zhu, Ye; Smith, Catherine L.; Du, Lan; Filia, Kate M.; Bayer, Johanna; Menssink, Jana M.; Wang, Teresa; Bergmeir, Christoph; Wood, Stephen; Cotton, Sue M. (2023년 9월 1일). 《An overview of clustering methods with guidelines for application in mental health research》. 《Psychiatry Research》 327. doi:10.1016/j.psychres.2023.115265. hdl:10481/84538. ISSN 0165-1781. PMID 37348404.
  9. ↑ Everitt, Brian (2011). 《Cluster analysis》. Chichester, West Sussex, U.K: Wiley. ISBN 9780470749913.
  10. ↑ Sibson, R. (1973). 《SLINK: an optimally efficient algorithm for the single-link cluster method》 (PDF). 《The Computer Journal》 16 (British Computer Society). 30–34쪽. doi:10.1093/comjnl/16.1.30.
  11. ↑ Defays, D. (1977). 《An efficient algorithm for a complete link method》. 《The Computer Journal》 20 (British Computer Society). 364–366쪽. doi:10.1093/comjnl/20.4.364.
  12. ↑ Lloyd, S. (1982). 《Least squares quantization in PCM》. 《IEEE Transactions on Information Theory》 28. 129–137쪽. doi:10.1109/TIT.1982.1056489. S2CID 10833328.
  13. ↑ Kriegel, Hans-Peter; Kröger, Peer; Sander, Jörg; Zimek, Arthur (2011). 《Density-based Clustering》. 《WIREs Data Mining and Knowledge Discovery》 1. 231–240쪽. doi:10.1002/widm.30. S2CID 36920706.
  14. ↑ Microsoft academic search: most cited data mining articles 보관됨 2010-04-21 - 웨이백 머신: 2010년 4월 18일 접속 기준 DBSCAN이 24위
  15. ↑ Ester, Martin; Kriegel, Hans-Peter; Sander, Jörg; Xu, Xiaowei (1996). 〈A density-based algorithm for discovering clusters in large spatial databases with noise〉. Simoudis, Evangelos; Han, Jiawei; Fayyad, Usama M. (편집). 《Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96)》. AAAI Press. 226–231쪽. ISBN 1-57735-004-9.
  16. ↑ Ankerst, Mihael; Breunig, Markus M.; Kriegel, Hans-Peter; Sander, Jörg (1999). 〈OPTICS: Ordering Points To Identify the Clustering Structure〉. 《ACM SIGMOD international conference on Management of data》. ACM Press. 49–60쪽. CiteSeerX 10.1.1.129.6542.
  17. 1 2 Achtert, E.; Böhm, C.; Kröger, P. (2006). 〈DeLi-Clu: Boosting Robustness, Completeness, Usability, and Efficiency of Hierarchical Clustering by a Closest Pair Ranking〉. 《Advances in Knowledge Discovery and Data Mining》. Lecture Notes in Computer Science. 119–128쪽. CiteSeerX 10.1.1.64.1161. doi:10.1007/11731139_16. ISBN 978-3-540-33206-0.
  18. ↑ Campello, Ricardo J. G. B.; Moulavi, Davoud; Sander, Joerg (2013). Pei, Jian; Tseng, Vincent S.; Cao, Longbing; Motoda, Hiroshi; Xu, Guandong (편집). 《Density-Based Clustering Based on Hierarchical Density Estimates》 (영어). 《Advances in Knowledge Discovery and Data Mining》 (Berlin, Heidelberg: Springer). 160–172쪽. doi:10.1007/978-3-642-37456-2_14. ISBN 978-3-642-37456-2.
  19. ↑ Aggarwal, Charu C.; Reddy, Chandan K. (편집). 《Data Clustering : Algorithms and Applications》. ISBN 978-1-315-37351-5. OCLC 1110589522.
  20. ↑ Sculley, D. (2010). 《Web-scale k-means clustering》. Proc. 19th WWW.
  21. ↑ Huang, Z. (1998). 《Extensions to the k-means algorithm for clustering large data sets with categorical values》. 《Data Mining and Knowledge Discovery》 2. 283–304쪽. doi:10.1023/A:1009769707641. S2CID 11323096.
  22. ↑ Kriegel, Hans-Peter; Kröger, Peer; Zimek, Arthur (July 2012). 《Subspace clustering》. 《Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery》 2. 351–364쪽. doi:10.1002/widm.1057. S2CID 7241355.
  23. ↑ Kraskov, Alexander; Stögbauer, Harald; Andrzejak, Ralph G.; Grassberger, Peter (2003년 12월 1일). “Hierarchical Clustering Based on Mutual Information”. arXiv:q-bio/0311039.
  24. ↑ Auffarth, B. (July 18–23, 2010). 《Clustering by a Genetic Algorithm with Biased Mutation Operator》. 《Wcci Cec》 (IEEE).
  25. ↑ Frey, B. J.; Dueck, D. (2007). 《Clustering by Passing Messages Between Data Points》. 《Science》 315. 972–976쪽. Bibcode:2007Sci...315..972F. CiteSeerX 10.1.1.121.3145. doi:10.1126/science.1136800. PMID 17218491. S2CID 6502291.
  26. 1 2 3 4 Pfitzner, Darius; Leibbrandt, Richard; Powers, David (2009). 《Characterization and evaluation of similarity measures for pairs of clusterings》. 《Knowledge and Information Systems》 19 (Springer). 361–394쪽. doi:10.1007/s10115-008-0150-6. S2CID 6935380.
  27. 1 2 3 Feldman, Ronen; Sanger, James (2007년 1월 1일). 《The Text Mining Handbook: Advanced Approaches in Analyzing Unstructured Data》. Cambridge Univ. Press. ISBN 978-0521836579. OCLC 915286380.
  28. 1 2 Weiss, Sholom M.; Indurkhya, Nitin; Zhang, Tong; Damerau, Fred J. (2005). 《Text Mining: Predictive Methods for Analyzing Unstructured Information》. Springer. ISBN 978-0387954332. OCLC 803401334.
  29. 1 2 3 Manning, Christopher D.; Raghavan, Prabhakar; Schütze, Hinrich (2008년 7월 7일). 《Introduction to Information Retrieval》. Cambridge University Press. ISBN 978-0-521-86571-5.
  30. ↑ Chicco, Davide; Campagner, Andrea; Spagnolo, Andrea; Ciucci, Davide; Jurman, Giuseppe (2025). 《The Silhouette coefficient and the Davies-Bouldin index are more informative than Dunn index, Calinski-Harabasz index, Shannon entropy, and Gap statistic for unsupervised clustering internal evaluation of two convex clusters》. 《PeerJ Computer Science》 11. 1–49쪽. doi:10.7717/peerj-cs.3309.
  31. 1 2 《Knowledge Discovery in Databases – Part III – Clustering》 (PDF), Heidelberg University, 2017, 2022년 9월 25일에 원본 문서 (PDF)에서 보존된 문서, 2026년 1월 9일에 확인함
  32. ↑ Dunn, J. (1974). 《Well separated clusters and optimal fuzzy partitions》. 《Journal of Cybernetics》 4. 95–104쪽. doi:10.1080/01969727408546059.
  33. ↑ Peter J. Rousseeuw (1987). 《Silhouettes: A graphical aid to the interpretation and validation of cluster analysis》. 《Journal of Computational and Applied Mathematics》 20. 53–65쪽. doi:10.1016/0377-0427(87)90125-7.
  34. ↑ Jaskowiak, Pablo A.; Costa, Ivan G.; Campello, Ricardo J. G. B. (2022년 5월 1일). 《The area under the ROC curve as a measure of clustering quality》 (영어). 《Data Mining and Knowledge Discovery》 36. 1219–1245쪽. doi:10.1007/s10618-022-00829-0. ISSN 1573-756X.
  35. 1 2 Färber, Ines; Günnemann, Stephan; Kriegel, Hans-Peter; Kröger, Peer; Müller, Emmanuel; Schubert, Erich; Seidl, Thomas; Zimek, Arthur (2010). 〈On Using Class-Labels in Evaluation of Clusterings〉 (PDF). Fern, Xiaoli Z.; Davidson, Ian; Dy, Jennifer (편집). 《MultiClust: Discovering, Summarizing, and Using Multiple Clusterings》. ACM SIGKDD.
  36. ↑ Pourrajabi, M.; Moulavi, D.; Campello, R. J. G. B.; Zimek, A.; Sander, J.; Goebel, R. (2014). 〈Model Selection for Semi-Supervised Clustering〉. 《Proceedings of the 17th International Conference on Extending Database Technology (EDBT)》. 331–342쪽. doi:10.5441/002/edbt.2014.31.
  37. ↑ Rand, W. M. (1971). 《Objective criteria for the evaluation of clustering methods》. 《Journal of the American Statistical Association》 66 (American Statistical Association). 846–850쪽. arXiv:1704.01036. doi:10.2307/2284239. JSTOR 2284239.
  38. ↑ Fowlkes, E. B.; Mallows, C. L. (1983). 《A Method for Comparing Two Hierarchical Clusterings》. 《Journal of the American Statistical Association》 78. 553–569쪽. doi:10.1080/01621459.1983.10478008. JSTOR 2288117.
  39. ↑ Powers, David (2003). 《Recall and Precision versus the Bookmaker》. International Conference on Cognitive Science. 529–534쪽.
  40. ↑ Arabie, P. (1985). 《Comparing partitions》. 《Journal of Classification》 2. 1985쪽. doi:10.1007/BF01908075. S2CID 189915041.
  41. ↑ Wallace, D. L. (1983). 《Comment》. 《Journal of the American Statistical Association》 78. 569–579쪽. doi:10.1080/01621459.1983.10478009.
  42. ↑ Powers, David (2012). 《The Problem with Kappa》. European Chapter of the Association for Computational Linguistics. 345–355쪽.
  43. ↑ Luna-Romera, José María; Martínez-Ballesteros, María; García-Gutiérrez, Jorge; Riquelme, José C. (June 2019). 《External clustering validity index based on chi-squared statistical test》 (영어). 《Information Sciences》 487. 1–17쪽. doi:10.1016/j.ins.2019.02.046. hdl:11441/132081. S2CID 93003939.
  44. ↑ Rosenberg, Andrew, and Julia Hirschberg. "V-measure: A conditional entropy-based external cluster evaluation measure." Proceedings of the 2007 joint conference on empirical methods in natural language processing and computational natural language learning (EMNLP-CoNLL). 2007. pdf
  45. ↑ Hopkins, Brian; Skellam, John Gordon (1954). 《A new method for determining the type of distribution of plant individuals》. 《Annals of Botany》 18 (Annals Botany Co). 213–227쪽. doi:10.1093/oxfordjournals.aob.a083391.
  46. ↑ Banerjee, A. (2004). 〈Validating clusters using the Hopkins statistic〉. 《2004 IEEE International Conference on Fuzzy Systems (IEEE Cat. No.04CH37542)》 1. 149–153쪽. doi:10.1109/FUZZY.2004.1375706. ISBN 978-0-7803-8353-1. S2CID 36701919.
  47. ↑ Johnson, Stephen C. (1967년 9월 1일). 《Hierarchical clustering schemes》 (영어). 《Psychometrika》 32. 241–254쪽. doi:10.1007/BF02289588. ISSN 1860-0980. PMID 5234703. S2CID 930698.
  48. ↑ Hartuv, Erez; Shamir, Ron (2000년 12월 31일). 《A clustering algorithm based on graph connectivity》. 《Information Processing Letters》 76. 175–181쪽. doi:10.1016/S0020-0190(00)00142-3. ISSN 0020-0190.
  49. ↑ Remm, Maido; Storm, Christian E. V.; Sonnhammer, Erik L. L. (2001년 12월 14일). 《Automatic clustering of orthologs and in-paralogs from pairwise species comparisons11Edited by F. Cohen》. 《Journal of Molecular Biology》 314. 1041–1052쪽. doi:10.1006/jmbi.2000.5197. ISSN 0022-2836. PMID 11743721.
  50. ↑ Botstein, David; Cox, David R.; Risch, Neil; Olshen, Richard; Curb, David; Dzau, Victor J.; Chen, Yii-Der I.; Hebert, Joan; Pesich, Robert (2001년 7월 1일). 《High-Throughput Genotyping with Single Nucleotide Polymorphisms》 (영어). 《Genome Research》 11. 1262–1268쪽. doi:10.1101/gr.157801. ISSN 1088-9051. PMC 311112. PMID 11435409.
  51. ↑ Filipovych, Roman; Resnick, Susan M.; Davatzikos, Christos (2011). 《Semi-supervised Cluster Analysis of Imaging Data》. 《NeuroImage》 54. 2185–2197쪽. doi:10.1016/j.neuroimage.2010.09.074. PMC 3008313. PMID 20933091.
  52. 1 2 Di Marco, Antonio; Navigli, Robert (2013). 《Clustering and Diversifying Web Search Results with Graph-Based Word Sense Induction》. 《Computational Linguistics》 39. 709–754쪽. doi:10.1162/COLI_a_00148. S2CID 1775181.
  53. 1 2 3 Beregovskaya, Irina; Koroteev, Mikhail (2021). “Review of Clustering-Based Recommender Systems”. arXiv:2109.12839 [cs.IR].
  54. ↑ 2022 Accelerate State of DevOps Report (PDF) (보고서). Google Cloud's DevOps Research and Assessment (DORA). 2022년 9월 29일. 8, 14, 74쪽.
  55. ↑ Bewley, A. 외. 《Real-time volume estimation of a dragline payload》. 《IEEE International Conference on Robotics and Automation》 2011. 1571–1576쪽.
  56. ↑ Basak, S.C.; Magnuson, V.R.; Niemi, C.J.; Regal, R.R. (1988). 《Determining Structural Similarity of Chemicals Using Graph Theoretic Indices》. 《Discr. Appl. Math.》 19. 17–44쪽. doi:10.1016/0166-218x(88)90004-2.
  57. ↑ Huth, R. 외 (2008). 《Classifications of Atmospheric Circulation Patterns: Recent Advances and Applications》 (PDF). 《Ann. N.Y. Acad. Sci.》 1146. 105–152쪽. Bibcode:2008NYASA1146..105H. doi:10.1196/annals.1446.019. PMID 19076414. S2CID 22655306.
  58. ↑ Arnott, Robert D. (1980년 11월 1일). 《Cluster Analysis and Stock Price Comovement》. 《Financial Analysts Journal》 36. 56–62쪽. doi:10.2469/faj.v36.n6.56. ISSN 0015-198X.