컨센서스 클러스터링

컨센서스 클러스터링은 복수의 클러스터링 알고리즘에서 얻은 결과를 집계(잠재적으로 상충되는)하는 방법이다.클러스터 앙상블^[1] 또는 클러스터링(또는 파티션)의 집합이라고도 하며, 특정 데이터 집합에 대해 여러 가지 (입력) 클러스터링을 획득하여 기존 클러스터링보다 어떤 의미에서 더 잘 맞는 단일(컨센서스) 클러스터링을 찾기를 원하는 상황을 가리킨다.^[2]따라서 컨센서스 클러스터링은 다른 출처 또는 동일한 알고리즘의 다른 실행에서 나오는 동일한 데이터 집합에 대한 클러스터링 정보를 조정하는 문제다.최적화 문제로 주조할 때 컨센서스 클러스터링은 중위수 파티션으로 알려져 있으며,^[3] 입력 클러스터링 수가 3개인 경우에도 NP-완전한 것으로 나타났다.^[4]감독되지 않은 학습을 위한 컨센서스 클러스터링은 감독된 학습에서 앙상블 학습과 유사하다.null

기존 클러스터링 기법의 문제

• 현재의 클러스터링 기법은 모든 요구사항을 적절하게 다루지 않는다.
• 많은 차원과 많은 수의 데이터 항목을 처리하는 것은 시간 복잡성 때문에 문제가 될 수 있다.
• 방법의 효과는 "거리"의 정의에 따라 달라진다(거리 기반 클러스터링의 경우)
• 분명한 거리 측정이 존재하지 않으면 반드시 'define'해야 하는데, 이것은 특히 다차원 공간에서는 항상 쉽지 않다.
• 클러스터링 알고리즘의 결과(대부분의 경우 임의적일 수 있는 것 자체)는 다른 방식으로 해석될 수 있다.

컨센서스 클러스터링 사용에 대한 정당성

기존의 모든 클러스터링 기법에는 잠재적인 단점이 있다.이는 특히 군집 수에 대한 지식이 없는 경우 결과의 해석을 어렵게 할 수 있다.클러스터링 방법은 초기 클러스터링 설정에도 매우 민감하여 비중요 데이터가 비반복적 방법으로 증폭될 수 있다.클러스터 분석에서 극히 중요한 문제는 클러스터링 결과의 검증, 즉 클러스터링 기법에 의해 제공되는 클러스터(클러스터 번호 및 클러스터 할당)의 중요성에 대한 신뢰도를 얻는 방법이다.외부 목표 기준(감독된 분석에서 알려진 클래스 라벨과 동일)이 결여되면, 이 검증은 다소 이해하기 어려워진다.SOM과 k-평균 군집화와 같은 반복 강하 군집화 방법은 단일하게 정의된 군집과 군집 경계를 제공함으로써 계층적 군집화의 일부 단점을 우회한다.컨센서스 클러스터링은 클러스터링 알고리즘의 여러 런에 걸친 합의를 나타내고, 데이터의 클러스터 수를 결정하고, 발견된 클러스터의 안정성을 평가하는 방법을 제공한다.또한 이 방법은 초기 조건에 대한 민감도를 설명하기 위해 무작위 재시작(예: K-평균, 모델 기반 베이시안 클러스터링, SOM 등)으로 클러스터링 알고리즘의 다중 실행에 대한 합의를 나타내는 데 사용할 수 있다.클러스터 번호, 구성원 자격 및 경계를 검사하는 시각화 도구에 대한 데이터를 제공할 수 있다.그러나 계층적 군집화 덴드로그램의 직관적 시각적 매력이 결여되어 있으며, 군집 수를 선험적으로 선택해야 한다.null

몬티 컨센서스 클러스터링 알고리즘

그 몬티 합의 algorithm[5]클러스터링은 가장 인기 있는 합의 클러스터링 알고리즘과 집단들의 수, K{K\displaystyle}. 클러스터에 포인트의 N{N\displaystyle}전체 데이터를 감안할 때 결정에 사용된다, 이 알고리즘 데이터 클러스터링 리샘플링 각각 K{\displays에서 일한다.tyl$e K}$과($와{\displaystyle )}$ ${\displaystyle N}$× N {\$displaystyle$ N$\times$ N$}$ 일치$$ 행렬을 계산하며, 여기서 각 요소는 두 표본이 함께 군집화된 시간의 분율을 나타낸다.완벽하게 안정된 행렬은 0과 1로 구성되며, 이는 모든 표본 쌍이 항상 함께 군집화하거나 모든 재샘플링 반복에 걸쳐 함께 군집화하지 않음을 나타낸다.컨센서스 매트릭스의 상대적 안정성은 최적의 $K{\displaystyle }$ ${\displaystyle K}$을(를) 추론하는 데 사용할 수 있다$.$

More specifically, given a set of points to cluster, ${\displaystyle D=\{e_{1},e_{2},...e_{N}\}}$, let ${\displaystyle D^{1},D^{2},...,D^{H}}$ be the list of ${\displaystyle H}$ perturbed (resampled) datasets of the original dataset ${\displayst$$yle D$ $그리고{\displaystyle {}^{}}$ M ${\displaystyle h^{}}$ ${\$은(는) 클러스터링 알고리즘을 데이터 $집합{\displaystyle {}^{}}$ ${\displaystyle D^{}}$ h$${\$displaystyle$ D$^{h}$에 적용한 결과로 발생하는 $N{\displaystyle }$ ${\displaystyle X}$ ${\displaystyle N}$ ${\displaystyle NXN}$ 연결$$ 매트릭스를 나타낸다$$$.$$M{\displaystyle {}^{}}$ ${\displaystyle h^{}}$ ${\$의 항목은 다음과 같이 정의된다$$.

${\displaystyle M^{h}(i,j)={\begin{case}1,&{\text{if}}{\text}{points i와 j는 동일한 클러스터에 속함}\0,&\text{otherwise}\case}}}}}$

Let ${\displaystyle I^{h}}$ be the ${\displaystyle N\times N}$ identicator matrix where the ${\displaystyle (i,j)}$-th entry is equal to 1 if points ${\displaystyle i}$ and ${\displaystyle j}$ are in the same perturbed dataset ${\displaystyle D^{h}}$, and 0 otherwise.표시기 매트릭스는 정상화 단계를 위해 각 재샘플링 반복 중에 선택된 표본을 추적하는 데 사용된다.합의 매트릭스 $C{\displaystyle }$ ${\$displaystyle C$}은($는) 모든 혼란된 데이터 집합의 모든 연결 매트릭스의 정규화된 합으로 정의되며$$, 다른 매트릭스는 모든 $K{\displaystyle }$ ${\displaystyle K}$에 대해 계산된다$.$

${\displaystyle C(i,j)=\왼쪽({\frac {\textstyle \sum \{h=1}^{H}M^{h}(i,j)\displaystyle }{\sum _{h=1}^{H}I^{h}(i,j)}}}\오른쪽)}$

합의 행렬의 항목$({\displaystyle }$i$$ ,${\displaystyle j}$) ${\displaystyle(i,j)}$은(는) i ${\displaystyle i}$와 $j{\displaystyle }$ ${\displaystyle j}$이(가) 함께 선택된 총 횟수로 함께 군집화된 수입니다.행렬은 대칭이며 각 요소는 [${\displaystyle }$0${\displaystyle ,}$ ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle [0,1]$ 범위 내에서 정의된다$.$ 일치 행렬은 시험할$$ 각 $K{\displaystyle }$ ${\displaystyle$ K$}$에 대해 계산되며, 각 행렬의 안정성은 행렬이 완벽한 안정성의 행렬(제로와 0만)을 향해 얼마나 떨어져 있는가에 대한 최적성을 결정하는 데 사용된다.L $K{\displaystyle }$ ${\displaystyle K$ $K{\displaystyle }$ ${\displaystyle K}$의 합의 행렬의 안정성을 정량화하는 한 가지 방법은 CDF 곡선을 조사하는 것이다(아래 참조).null

몬티 컨센서스 클러스터링 알고리즘의 과해석 가능성

몬티 컨센서스 클러스터링은 클러스터를 식별하는 강력한 도구가 될 수 있지만, 옌바바바오ğ루 등에서도 알 수 있듯이 주의해서 적용할 필요가 있다.^[6] 몬티 컨센서스 클러스터링 알고리즘은 단일 분포에서 도출된 null 데이터세트의 우연한 분할의 명백한 안정성을 주장할 수 있으며, 따라서 실제 연구에서 클러스터 안정성의 과도한 해석으로 이어질 가능성이 있는 것으로 나타났다.^[6][7]클러스터가 잘 분리되지 않을 경우, 합의된 클러스터링이 없을 때 명백한 구조를 결론짓거나, 미묘할 때 클러스터 안정성을 선언할 수 있다.거짓 양성 클러스터를 확인하는 것은 클러스터 연구 전반에 걸쳐 공통적인 문제로서, ^[8]SigClust와^[8] GAP 통계학 같은 방법으로 해결되었다.^[9]그러나 이러한 방법은 항상 적절하지 않을 수 있는 null 모형에 대한 특정 가정에 의존한다.null

şenbaovau et al은 몬티 $알고리즘$의 K ${\displaystyle K}$이(가) 저조한 성능을 판단하기 위해 원래 델타 K 메트릭을 시연하고, CDF 곡선을 사용하여 합의 행렬의 안정성을 측정하기 위한 새로운 상위 메트릭을 제안했다.컨센서스 매트릭스의 CDF 곡선에서 왼쪽 아래 부분은 거의 함께 군집화되지 않은 표본 쌍을 나타내고 오른쪽 위 부분은 거의 항상 군집화된 표본 쌍을 나타내며, 중간 부분은 서로 다른 군집화 실행에서 애매한 할당을 가진 표본 쌍을 나타낸다.모호한 군집화(PAC) 점수 측정의 비율은 이 중간 세그먼트를 정량화하고, u는₁ 0에 가까운 값이고 u는₂ 1에 가까운 값(예: u₁=0.1과 u₂=0.9)인 간격(u₁, u₂) u[0, 1]에 해당하는 일치 지수를 가진 표본 쌍의 비율로 정의된다.PAC 값이 낮으면 중간 세그먼트가 평평하다는 것을 나타내며, 순서가 지정된 클러스터링 실행에서 불협화음 할당 비율이 낮다.따라서 PAC가 가장 낮은 $K{\displaystyle }$ ${\displaystyle K}$ 값으로$$ 최적의 클러스터 수를 추정할 수 있다.^[6][7]null

관련업무

1. 클러스터링 앙상블(Strehl and Ghosh):그들은 이 문제에 대해 다양한 공식화를 고려했는데, 그 중 대부분은 문제를 하이퍼그래프 분할 문제로 축소한다.공식화 중 하나에서 그들은 상관 군집화 문제와 동일한 그래프를 고려했다.그들이 제안한 해결책은 멀리 떨어져 있는 두 개의 노드를 병합할 때의 벌칙을 고려하지 않는 그래프의 최고의 k-파티션을 계산하는 것이다.^{[citation needed]}null

2. 클러스터링 집합(Fern 및 Brodley):그들은 무작위 투영을 통해 얻은 소프트 클러스터링 집합에 클러스터링 통합 아이디어를 적용했다.그들은 응집 알고리즘을 사용했고 서로 다른 노드를 병합하는 것에 대해 불이익을 주지 않았다.^{[citation needed]}null

3. 프레드와 제인:그들은 k-평균 알고리즘의 다중 런을 결합하기 위해 단일 연결 알고리즘을 사용할 것을 제안했다.^{[citation needed]}null

4. 다나 크리스토퍼와 댄 시모비치:그들은 군집화 집합과 범주형 데이터의 군집화 사이의 연관성을 관찰했다.그들은 정보 이론적 거리 측정법을 제안했고, 최적의 통합 솔루션을 찾기 위한 유전자 알고리즘을 제안하였다.^{[citation needed]}null

5. Topchy 등:그들은 클러스터링 집계를 최대우도 추정 문제로 정의했고, 합의된 클러스터링을 찾기 위한 전자파 알고리즘을 제안했다.^{[citation needed]}null

하드 앙상블 클러스터링

Strehl과 Ghosh의 이 접근법은 이러한 분할을 결정한 특징이나 알고리즘에 접근하지 않고 개체 집합의 다중 분할을 하나의 통합된 클러스터링으로 결합하는 문제를 도입한다.그들은 높은 품질의 합의 기능을 얻기 위해 이 문제를 해결하기 위한 세 가지 접근법을 논의한다.이들의 기법은 계산 비용이 낮기 때문에 아래에서 논의한 각 기법을 평가하고 그 결과를 객관적 기능과 비교함으로써 최선의 해결책에 도달할 수 있다.null

효율적인 컨센서스 기능

1.군집 기반 유사성 분할 알고리즘(CSPA)

CSPA에서 두 데이터 포인트 사이의 유사성은 두 포인트가 함께 군집화된 앙상블의 구성 요소 군집 수에 정비례하는 것으로 정의된다.직관은 유사한 두 데이터 포인트가 많을수록 구성 요소 군집이 두 데이터 포인트를 동일한 클러스터에 배치할 확률이다.CSPA는 가장 간단한 경험적 경험이지만, 계산과 저장 복잡성은 모두 n으로 2차적이다. SC3는 CSPA 유형 알고리즘의 예다.^[10]다음의 두 가지 방법은 계산적으로 비용이 덜 든다.

2. 하이퍼그래프 분할 알고리즘(HGPA)

HGPA 알고리즘은 이전의 방법과는 다른 개념의 클러스터링을 찾는 접근방식을 취한다.클러스터 앙상블 문제는 최소 개수의 흥분을 줄여 하이퍼그래프를 분할하는 것으로 공식화된다.하이퍼그래프 분할 패키지 시스템인 hMETIS를 활용한다.null

3. 메타클러스터 알고리즘(MCLA)

MCLA(meta-Clustering algorithm)는 클러스터링 클러스터를 기반으로 한다.첫째, 클러스터 통신 문제를 해결하려고 노력한 다음 투표를 사용하여 최종 합의 클러스터에 데이터 포인트를 배치한다.군집 대응 문제는 앙상블의 개별 군집화에서 확인된 군집을 그룹화하여 해결한다.클러스터링은 METIS와 스펙트럼 클러스터링을 사용하여 수행된다.null

소프트 클러스터링 앙상블

푸네라와 고쉬는 하드 클러스터링 앙상블의 아이디어를 소프트 클러스터링 시나리오로 확장했다.소프트 앙상블의 각 인스턴스는 구성 요소 군집화 알고리즘에서 얻은 r 후방 멤버십 확률 분포의 결합으로 표현된다.두 확률 분포 사이의 "거리"를 계산하는 Kullback-Leibler (KL) 차이를 사용하여 두 인스턴스 간의 거리 측정을 정의할 수 있다.null

1. SSPA

sCSPA는 유사성 행렬을 계산하여 CSPA를 확장한다.각 물체는 치수 공간의 한 점으로 시각화되며, 각 차원은 클러스터에 속하는 확률에 해당한다.이 기법은 먼저 사물을 라벨 공간으로 변환한 다음 사물의 유사성을 나타내는 벡터 사이의 도트 제품을 해석한다.null

2. sMCLA

sMCLA는 소프트 클러스터링을 입력으로 수용하여 MCLA를 확장한다. sMCLA의 작업은 다음 단계로 나눌 수 있다.

• 클러스터의 소프트 메타 그래프 구성
• 클러스터를 메타 클러스터로 그룹화
• 가중치를 사용하여 메타 클러스터 축소
• 오브젝트 경쟁

3. sHBGF

HBGF는 앙상블을 노드로 클러스터와 인스턴스(instance)를, 인스턴스(instance)와 인스턴스(instance)가 속한 클러스터(cluster) 사이의 가장자리를 갖는 초당적 그래프로 나타낸다.^[11]그래프 분할 알고리즘 METIS는 분할할 그래프 가장자리의 가중치를 허용하기 때문에 이 접근법은 소프트 앙상블을 고려하도록 사소한 방법으로 조정할 수 있다.sHBGF에서 그래프에는 n + t 정점이 있으며 여기서 t는 기초 군집의 총 수입니다.null

4. 베이시안 컨센서스 클러스터링(BCC)

BCC는 다른 입력 데이터나 다른 확률 모델에 의해 정의되는 복수의 소스 클러스터링이 합의 클러스터링에 느슨하게 부합한다고 가정하는 소프트 컨센서스 클러스터링에 대한 베이시안 모델을 완전히 정의한다.^[12]별도 군집의 전면 후측과 합의 군집화는 Gibbs 표본을 통해 동시에 유추된다.null

원천

참조

• 알렉산더 스트렐과 J.Ghosh, Cluster 앙상블 – JMLR(Journal on Machine Learning Research) 2002, 3, 583–617의 여러 파티션을 결합하기 위한 지식 재사용 프레임워크.
• 쿠날 푸네라, 조이딥 고쉬.소프트 클러스터링의 컨센서스 기반 앙상블.
• 아리스티드 기오니스, 하이키 마닐라, 파나야오티스 사파라스.클러스터링 통합. 제21차 데이터 엔지니어링 국제 컨퍼런스(ICDE 2005)
• 왕홍준, 한후이산, 아린담 배너지.베이시안 클러스터 앙상블^{[permanent dead link]}, 데이터 마이닝에 관한 SIAM 국제회의, SDM 09
• 남응우옌, 리치 카루아나.컨센서스 클러스터링.제7회 IEEE 데이터 마이닝 국제 컨퍼런스.
• 알렉산더 토피, 아닐 K. 자인, 윌리엄 펀치.클러스터링 앙상블: 컨센서스 및 취약한 파티션의 모델.IEEE 데이터 마이닝 국제회의, ICDM 03 & SIAM 데이터 마이닝 국제회의, SDM 04