데이터 집합의 클러스터 수 결정

데이터 집합의 클러스터 수를 결정하는 것은 k-평균 알고리즘에서처럼 k로 표기되는 수량으로, 데이터 클러스터링에서 자주 발생하는 문제로서, 실제로 클러스터링 문제를 해결하는 과정과는 구별되는 문제다.

특정 종류의 클러스터링 알고리즘(특히 k-평균, k-medoids 및 기대-최대화 알고리즘)에 대해서는 일반적으로 k라고 하는 매개변수가 있어 검출할 클러스터 수를 지정한다.DBSCAN과 광학 알고리즘과 같은 다른 알고리즘은 이 매개변수의 사양을 요구하지 않는다. 계층적 클러스터링은 문제를 완전히 방지한다.

k의 정확한 선택은 데이터 집합의 점 분포의 형태와 규모, 사용자의 원하는 클러스터링 해상도에 따라 해석이 애매한 경우가 많다.또한, 벌점 없이 k를 증가시키면, 각 데이터 점을 자체 군집으로 간주할 경우(즉, k가 데이터 점의 수와 동일한 경우, n) 결과 군집화의 오차량이 항상 감소한다.직관적으로 k의 최적 선택은 단일 클러스터를 사용하는 데이터의 최대 압축과 각 데이터 지점을 자체 클러스터에 할당함으로써 최대 정확도 사이의 균형을 맞출 것이다.데이터 집합의 속성에 대한 사전 지식으로부터 적절한 k 값이 명확하지 않은 경우에는 어떻게든 선택해야 한다.이 결정을 내리는 방법에는 몇 가지 범주가 있다.

엘보법

팔꿈치 방법은 설명한 분산의 백분율을 군집 수의 함수로 본다.다른 클러스터를 추가하는 것이 데이터에 대한 더 나은 모델링이 되지 않도록 여러 클러스터를 선택해야 한다.더 정확히 말하면, 군집 수에 대해 군집들에 의해 설명되는 분산 비율을 나타낸다면, 첫 번째 군집들은 많은 정보를 추가하지만(많은 분산을 나타냄) 어느 시점에서 한계 이득은 감소하여 그래프에 각도를 제공할 것이다.군집 수는 이 지점에서 선택되므로 "팔꿈치 기준"이 선택된다.이 "팔꿈치"는 항상 모호하지 않게 식별될 수 없으며,^[1] 이 방법을 매우 주관적이고 신뢰할 수 없게 만든다.이를 극복하기 위해 2021년 '팔꿈치 강도'라는 수량이 도입돼 클러스터 수를 자동화하는 데 성공했음을 입증했다.^[2]설명되는 분산 비율은 F-검정이라고도 하는 총 분산에 대한 그룹 간 분산 비율이다.이 방법의 약간의 변동은 군내 분산의 곡면성을 나타낸다.^[3]

그 방법은 로버트 L에 의한 추측으로 추적할 수 있다. 1953년 ^[4]쏜디케

X-평균 군집화

통계 및 데이터 마이닝에서 X-평균 군집화는 AIC(Akaike Information Criteria, AIC) 또는 BIC(Bayesian Information Criteria, BIC)와 같은 기준에 도달할 때까지 반복적으로 분할을 시도하고 최상의 분할을 유지함으로써 클러스터 할당을 재조정하는 k-평균 군집화 군집화 군집화 변종화다.^[5]

정보기준접근법

클러스터 수를 결정하는 또 다른 방법 집합은 클러스터링 모델에 대한 우도 함수를 만들 수 있는 경우 Akaike 정보 기준(AIC), 베이지안 정보 기준(BIC) 또는 이탈도 정보 기준(DIC)과 같은 정보 기준이다.예를 들면 다음과 같다.k-평균 모델은 가우스 혼합물 모델이며 가우스 혼합물 모델에 대한 가능성을 구성하여 정보 기준 값을 결정할 수 있다.^[6]

정보-이론적 접근법

요율 왜곡 이론은 정보이론적 표준에 의해 오류를 최소화하면서 효율성을 극대화하는 클러스터 수를 결정하는 '점프(jump)' 방식이라고 불리는 k를 선택하는 데 적용됐다.^[7]알고리즘의 전략은 1에서 n 사이의 모든 k 값에 대해 k-평균과 같은 표준 군집화 알고리즘을 실행하고, 그 결과 군집화의 왜곡(아래 설명)을 계산하여 입력 데이터에 대한 왜곡 곡선을 생성하는 것이다.그런 다음 왜곡 곡선은 데이터의 치수성에 기초하여 선택한 음의 힘에 의해 변환된다.결과값으로 점프한 다음 k에 대한 합리적인 선택을 의미하며, 가장 큰 점프는 최선의 선택을 나타낸다.

일부 입력 데이터의 군집화 왜곡은 공식적으로 다음과 같이 정의된다.Let the data set be modeled as a p-dimensional random variable, X, consisting of a mixture distribution of G components with common covariance, Γ. If we let ${\displaystyle c_{1}\ldots c_{K}}$ be a set of K cluster centers, with ${\displaystyle c_{X}}$ the closest center to a given sample of X, then the minimum 데이터에 K 센터를 장착할 때 치수당 평균 왜곡:

${\displaystyle d_{K}={\frac {1}{p}\min _{c_{1}\ldots c_{K}}{E[(X-c_{X}})^{{}}{\frac {1}\min _{c_{X}}}}^{{{}}}}}}}}}T}\감마 ^{-1}(X-c_{X})}}}}}}}$

이것은 또한 X와 가장 가까운 클러스터 $센터{\displaystyle {}_{}}$ $[\$ 사이의 차원당 평균 마할라노비스 거리이기도 하다$.$ 가능한 모든 클러스터 센터 세트에 대한 최소화가 엄청나게 복잡하기 때문에, 표준 클러스터링 알고리즘 a를 사용하여 클러스터 센터 세트를 생성하여 실제로 왜곡을 계산한다.결과를 사용하여 왜곡을 계산한다.p-차원 데이터 포인트 X의 입력 세트를 사용한 점프 방법에 대한 유사 코드는 다음과 같다.

JumpMethod(X):Let Y = (p/2) 목록 D를 초기화(n+1 크기) D[0] = 0 k = 1 ...n: k 클러스터가 있는 클러스터 X(예: k-평균이 있는 클러스터 X) let d = 결과 클러스터링 D[k] = d^(-Y) 정의 J(i) = D[i] - D[i-1] J(k)를 최대화하는 k를 1에서 n 사이에 반환

변환력 $Y{\displaystyle }$=${\displaystyle }$( ${\displaystyle p}$/ ${\displaystyle 2\mathrm{}}$) ${\displaystyle Y=(p/2)}$의 선택은 비율 왜곡 이론의 결과를 이용한 점증적 추론에 의해 동기 부여된다$$.데이터 X에 임의의 p-차원 가우스 분포를 단일하게 하고, 0보다 큰 일부 α에 대해 $고정{\displaystyle }$ K${\displaystyle }$=${\displaystyle {}^{}}$ α ${\displaystyle p^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle K=\lfloor \lfloor }$을$($를) 두십시오.그러면 p가 무한대로 가면서 한계에 있는 K 군집들의 군집화의 왜곡은 ${\displaystyle {\mathrm{\alpha }}^{}}$- 2 ${\$ 무증상으로는 전력에 대한 군집화의 왜곡$({\displaystyle }$- ${\displaystyle p\mathrm{}}$/ 2${\displaystyle }$) ${\displaystyle(-p/2$)이$$${\displaystyle {\alpha }^{}}$ p ${\$에 비례한다는$$ 것을 알 수 있는데, 정의상으로는 }이 $된다$근접하게 군집 K의 수입니다.즉, 단일 가우스 분포의 경우 실제 군집 수를 초과하여 K를 증가시키면(하나여야 함) 왜곡이 선형적으로 증가하게 된다.이러한 행동은 여러 분포 성분의 혼합의 일반적인 경우에 중요하다.

X를 공통 공분산과 함께 G p-차원 가우스 분포의 혼합물이 되도록 하자.그러면 G보다 작은 고정 K에 대해 p가 무한대로 갈 때 군집화의 왜곡은 무한하다.직관적으로 이것은 정확한 수의 군집화보다 적은 군집화가 점증적으로 고차원적인 데이터를 설명할 수 없어서 왜곡이 제한 없이 증가함을 의미한다.If, as described above, K is made an increasing function of p, namely, ${\displaystyle K=\lfloor \alpha ^{p}\rfloor }$, the same result as above is achieved, with the value of the distortion in the limit as p goes to infinity being equal to ${\displaystyle \alpha ^{-2}}$. Correspondingly, there is the same pro변형된 왜곡과 군집 수 K 사이의 좌현 관계.

위의 결과를 종합하면, 충분히 높은 p 값에 대해 변환된 ${\displaystyle {왜곡}_{}^{}}$ d $K{\displaystyle {}_{}^{}}$- ${\displaystyle {p\mathrm{}}_{}^{}}$/ 2 ${\$이 K < G의 경우 약 0이다가$$ 갑자기 점프하여 K ≥ G의 선형적으로 증가하기 시작함을 알 수 있다.K를 선택하기 위한 점프 알고리즘은 실제 군집 수에 가장 가능성이 높은 값을 식별하기 위해 이러한 동작을 사용한다.

방법에 대한 수학적 지원은 점증적 결과의 관점에서 제공되지만, 알고리즘은 합리적인 차원성을 가진 다양한 데이터 집합에서 잘 작동하도록 실증적으로 검증되었다.위에서 설명한 국부적 점프 방법 외에도, 끊어진 선법이라고 알려진 동일한 변환된 왜곡 값을 사용하여 K를 선택하는 두 번째 알고리즘이 존재한다.깨진 선법은 이론상 K < G의 X축을 따라, 그리고 K g G의 변형된 왜곡도의 선형적으로 증가하는 위상을 따라 두 선 세그먼트의 단순한 최소 제곱 오차선 적합을 수행하여 변환된 왜곡의 그래프에서 점프를 식별한다.끊어진 선법은 결정이 국소적이 아니라 글로벌하다는 점에서 점프 방법보다 더 견고하지만 가우스 혼합물 성분의 가정에 의존하는 반면 점프 방법은 완전히 비모수적이며 일반적인 혼합물 분포에 대해 실행 가능한 것으로 나타났다.

실루엣 방식

데이터의 평균 실루엣은 군집의 자연 수를 평가하는 또 다른 유용한 기준이다.데이터 인스턴스의 실루엣은 클러스터 내의 데이터와 얼마나 밀접하게 일치하는지, 그리고 기준점으로부터의 평균 거리가 가장 낮은 클러스터와 얼마나 느슨하게 일치하는지 나타내는 척도다.^[8]1에 가까운 실루엣은 기준점이 적절한 클러스터에 있음을 의미하고 -1에 가까운 실루엣은 기준점이 잘못된 클러스터에 있음을 의미한다.유전자 알고리즘과 같은 최적화 기법은 가장 큰 실루엣을 발생시키는 군집 수를 결정하는 데 유용하다.^[9]정확한 클러스터 수에서 실루엣이 극대화될 가능성이 더 높은 방식으로 데이터를 다시 스케일링할 수도 있다.^[10]

교차 검증

또한 교차 검증 프로세스를 사용하여 군집 수를 분석할 수 있다.이 과정에서 데이터는 v 파트로 분할된다.그런 다음 각 부품을 시험 세트, 다른 v - 1 훈련 세트에서 계산한 클러스터링 모델, 그리고 시험 세트에 대해 계산된 목표 함수 값(예: k-평균 중심까지의 거리 제곱의 합계)으로 한 번에 따로 둔다.이러한 v 값은 각 대체 클러스터 수에 대해 계산 및 평균을 산출하고, 클러스터 수의 추가 증가는 목표 기능의 작은 감소로 이어질 수 있도록 선택된 클러스터 수를 계산한다.^[11]

텍스트 데이터베이스에서 클러스터 수 찾기

텍스트 데이터베이스에서 D 매트릭스(m by n, m: 문서 수, n: 용어 수)에 의해 문서에 의해 정의된 문서 수집은 대략 m ${\displaystyle \frac{}{}}$ ${\displaystyle \frac{t}{}}$ ${\${\$tfrac {mn}{t}}$ 공식으로 추정할 수 있다. 여기서$$ t는 D의 0이 아닌 항목 수입니다.D에서 각 행과 각 열에는 0이 아닌 요소가 하나 이상 포함되어야 한다는 점에 유의하십시오.^[12]

커널 매트릭스 분석

커널 매트릭스는 입력 정보의 근접성을 정의한다.예를 들어 가우스 방사상 기준 함수에서 피쳐 스페이스라고 하는 고차원 공간에서 입력의 도트 곱을 결정한다.형상공간에서 데이터가 더 선형적으로 분리될 수 있게 되고, 따라서 선형 알고리즘이 더 높은 성공으로 데이터에 적용될 수 있다고 생각된다.

따라서 최적의 클러스터 수를 찾기 위해 커널 매트릭스를 분석할 수 있다.^[13]메소드는 커널 매트릭스의 고유값 분해에 의해 진행된다.그런 다음 고유값과 고유 벡터를 분석하여 입력 분포의 압축도를 측정한다.마지막으로 그래프가 그려지며, 여기서 그림의 팔꿈치는 데이터 집합의 최적 군집 수를 나타낸다.이전 방법과 달리 이 기법은 클러스터링 a-priori를 수행할 필요가 없다.데이터에서 직접 군집 수를 찾는다.

갭 통계량

Robert Tibshirani, Guenther Walter, Trevor Hastie는 갭 통계를 통해 데이터 집합의 군집 수를 추정할 것을 제안했다.^[14]갭 통계량은 이론적 근거에 기초하여 데이터의 null 기준 분포에서 예상되는 제곱합에서 클러스터 중심 주위의 합동 군집 내 제곱합이 얼마나 먼지를 측정한다.기대값은 원본 데이터의 특성에 대한 null 참조 데이터를 시뮬레이션하여 추정하지만 그 안에 클러스터가 없다.최적 군집 수는 관측된 제곱합이 null 기준보다 가장 먼 k 값으로 추정한다.

이전의 많은 방법들과 달리, 갭 통계는 우리에게 좋은 클러스터링이 있는 k의 값이 없다는 것을 말해줄 수 있다.

갭 통계는 R의 클러스터 패키지에서^[15] clusGap 함수로 구현된다.

참조

추가 읽기

• 랄프 바그너, 소렌 W. 숄츠, 라인홀드 데커(2005):시장 세분화의 클러스터 수, in: 다니엘 바이어, 라인홀드 데커, Lars Schmidt-Thieme(에드): 데이터 분석 및 의사결정 지원, 베를린, 스프링거, 157–176.

외부 링크

• 클러스터그램 – 클러스터 진단 그림 - (k) 군집 수(R 코드)를 선택하는 시각적 진단을 위한 그림
• k-평균 분석을 위한 최적의 k 값을 결정하는 8가지 방법 – k-평균 군집 분석을 위한 k의 최적 값을 계산하는 여러 방법에 대한 R 코드가 포함된 스택 오버플로 응답
• 파티셔닝 및 클러스터링: 수업은 몇 개?HAL 서버에서 사용 가능한 무료 세미나 논문, id=hal-02124947: 두 가지 비모수적 방법(바이브라이오그래픽 참조가 제공됨), 숫자 변수(필수적으로 유클리드적이지 않은 거리 배열이 있는 작업), 범주형 변수(최적 파티셔닝, 서명된 차이도 작동함)에 대한 방법.