스펙트럼 클러스터링

다변량 통계량에서 스펙트럼 군집화 기법은 데이터의 유사성 행렬의 스펙트럼(유전자 값)을 사용하여 더 적은 차원으로 군집화하기 전에 치수 감소를 수행한다.유사도 행렬은 입력으로 제공되며 데이터 집합에서 각 점 쌍의 상대적 유사성에 대한 정량적 평가로 구성된다.

영상 분할에 적용할 때 스펙트럼 클러스터링은 분할 기반 객체 분류라고 한다.

정의들

열거된 데이터 포인트 집합이 주어진 경우 유사도 $행렬$은 대칭 행렬 A ${\displaystyle A}$로 정의될 수 있으며$,$ $여기$서 ${\displaystyle {\mathrm{Ai}}_{}}$ j${\displaystyle {}_{}0}$ 0$${\$displaystyle A_{ij}\geq$0}은 $지수{\displaystyle }$ i$${\$displaystyle$ i$$$}$ $및{\displaystyle }$ j ${\displaystyle j}$을 가진 데이터 포인트 간의 유사도를 나타낸다$$$.$스펙트럼 클러스터링에 대한 일반적인 접근방식은 $A{\displaystyle }$ {\$displaystyle A}$의 라플라시안 행렬의 관련 고유 벡터에 대해 표준 클러스터링 방법(그런 방법은 많이 있다, k-평균은 아래에서 논의된다$.)$을 사용하는 것이다. 수학적 해석이 다른 라플라시안을 정의하는 방법에는 여러 가지가 있으며, 따라서 클러스터링은해석도 다르다.관련성이 있는 고유 벡터는 값이 0인 최소 고유값을 제외하고 라플라크의 최소 몇 개의 고유값에 해당하는 것이다.계산 효율을 위해, 이러한 고유 벡터는 종종 라플라시안 함수의 최대 몇 개의 고유값에 해당하는 고유 벡터로 계산된다.

라플라시안 행렬

스펙트럼 클러스터링은 질량 스프링 시스템의 분할과 관련이 있는 것으로 잘 알려져 있으며, 각 질량은 데이터 포인트와 연관되며 각 스프링 강성은 스프링 시스템에서와 같이 두 관련 데이터 포인트의 유사성을 설명하는 가장자리의 중량에 해당한다.구체적으로는 질량-스프링 시스템의 횡단 진동 모드를 기술하는 고유값 문제가 다음과 같이 정의된 그래프 라플라시안 행렬의 고유값 문제와 정확히 동일하다는 것이 고전적 참조의 설명이다.

${\displaystyle L}$ ${\displaystyle :=}$ ${\displaystyle D}$- A ${\displaystyle$ L$:=D-A$

여기서 $D{\displaystyle }$ ${\displaystyle D}$은(는) 대각 행렬이다.

${\displaystyle D_{i}=\sum _{j}A_{ij}.}$

질량 스프링 시스템에서 스프링에 의해 밀접하게 연결된 질량은 분명히 저주파 진동 모드에서 평형 위치에서 함께 이동하므로 그래프 라플라시안의 최소 고유값에 해당하는 고유 벡터의 구성요소를 질량의 의미 있는 군집화에 사용할 수 있다.예를 들어, 그림의 2차원 스프링 시스템에서 모든 스프링과 질량이 동일하다고 가정하면, 시스템 오른쪽에서 가장 느슨하게 연결된 질량이 시스템이 흔들릴 때 가장 큰 진폭으로 나머지 질량과 반대 방향으로 이동할 것으로 직관적으로 예상할 수 있다.xpectation은 가장 작은 고유값에 해당하는 그래프 라플라시아의 고유 벡터 성분, 즉 가장 작은 진동 주파수를 분석하여 확인할 것이다.

라플라시안 행렬 정규화

정상화의 목표는 라플라시안 매트릭스의 대각선 입력을 모두 단위가 되게 하고, 그에 따라 대각선 입력을 스케일 아웃하는 것이다.가중 그래프에서, 정점은 연결된 가장자리의 수가 적지만 단위 무게와 연결된 가장자리의 수가 많으므로 큰 정도를 가질 수 있다.

일반적으로 표준화된 스펙트럼 클러스터링 기법은 지안보 시와 지텐드라 말릭이 도입하는 표준화된 컷팅 알고리즘 또는 시-말릭 알고리즘으로,^[2] 영상 분할에 일반적으로 사용된다.이 파티션은 두${\displaystyle {}_{}{}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$, B$$2${\displaystyle {}_{}}$) {\$displaystyle(B_{1},B_{2})$로 분할되며, 이는 다음과 같이 정의된 대칭 정규화된 라플라시안의 두 번째 가장 작은 고유값에 해당하는$$ 고유 $벡터{\displaystyle }$ v ${\displaystyle v}$에 기반한다.

${\displaystyle L^{\text{norm}}:=I-D^{-1/2}AD^{-1/2}.}$

벡터 $v{\displaystyle }$ ${\displaystyle v}$은(는) 대칭 정규화된 $인접{\displaystyle {}^{}}$ 행렬 D${\displaystyle {}^{}}$- 1${\displaystyle {}^{}}$/ ${\displaystyle 2^{}}$ ${\displaystyle A^{}}$- ${\displaystyle 1^{}}$/ 2${\displaystyle {}^{}}$. ${\displaystyle D^{-1/2}$의 두 번째로 큰 고유값에 해당하는 고유 벡터이기도$$ 하다.$AD^{-1/2}.$$}$

무작위 보행(또는 왼쪽) 표준화된 라플라시안은 다음과 같이 정의된다.

${\displaystyle L^{\text{rw}:=D^{-1}L=I-D^{-1}A}$

스펙트럼 클러스터링에도 사용할 수 있다.수학적으로 동등한 알고리즘은 무작위 보행 정규화된 $인접{\displaystyle }$ 행렬 P${\displaystyle }$= ${\displaystyle {}^{}}$- ${\displaystyle 1^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle P=D^{-1}A}$의 가장 큰 고유 값에 해당하는$$ 고유 벡터 $u{\displaystyle }$ ${\displaystyle u}$을(를) 취한다$.$

대칭적으로 정규화된 라플라시안의 $고유벡터$ v ${\displaystyle v}$과(와) 좌측 정규화된 라플라시안의 고유벡터$$ $u{\displaystyle }$ ${\displaystyle u}$은($와{\displaystyle {}^{}}$) ID D${\displaystyle {}^{}}$- 1${\displaystyle {}^{}}$/ ${\displaystyle {}^{}}$= ${\displaystyle u.}$ ${\displaystyle D^{-1/$2}$v=u$와 관련이 있다$.$$}$

스펙트럼 임베딩을 통한 군집 분석

$$한 고유 벡터의$$ $n{\displaystyle }$ ${\displaystyle$ $k}$ 행렬$$$$ V ${\displaystyle k}$을(를) 알면 $원래{\displaystyle }$ $n{\displaystyle }$ ${\displaystyle n}$ 데이터$$ 포인트의 $매핑$이 V ${\$displaystyle $V}$ 행을 사용하여 k ${\$$displaystyle$ k$}$차원$$ 벡터 공간에 수행됨$.$ 이제e 분석은 다양한 $방법$으로$$수행될 수 $있는$ k {\displaystyle $k}$ 구성요소를$$ 가진 벡터로 축소된다.

가장 간단한 사례 $k{\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle k=1}$에서$,$ 피들러 벡터라고 불리는$$선택된 단일 고유 벡터 $v{\displaystyle }$ ${\displaystyle v}$은 두 번째로 작은 고유값에 해당한다.$v$${\displaystyle }$, ${\displaystyle$ v$,}$의 구성 요소를 사용하면 $v{\displaystyle }$ ${\displaystyle v}$의 구성 요소가 양수인$$ 모든 점을 $세트{\displaystyle {}_{}}$B + ${\$에 배치할$$ 수 있으며, 나머지는 B${\displaystyle {}_{}}$- ${\$에$$그래프를 양분하고 두 개의 레이블로 데이터 포인트에 라벨을 붙일 수 있다.이러한 신호 기반 접근방식은 질량 스프링 모델을 통한 스펙트럼 클러스터링의 직관적인 설명을 따른다. 즉, 피들러 $벡터{\displaystyle }$ v ${\displaystyle v}$이(가) 나타내는 저주파 진동 모드에서는 상호 강하게 연결된 질량으로 식별된 단일 클러스터 데이터 지점이 한 방향으로 이동하는 반면, 보완 클론에서는 서로 이동한다.남은 질량으로 식별된 uster 데이터 지점은 반대 방향으로 함께 이동한다.알고리즘은 동일한 방식으로 하위 집합을 반복적으로 분할하여 계층적 클러스터링에 사용할 수 있다.

일반적인 케이스 > ${\displaystyle k>1}$에서 모든 벡터 클러스터링 기법을 사용할 수 있다(예: DBSCAN).

알고리즘

기본 알고리즘

1. Laplacian L ${\displaystyle$ L$}($또는 정규화된 Laplacian) 계산
2. 첫 번째 $k{\displaystyle }$ ${\displaystyle k}$ 고유$$ 벡터($L{\displaystyle }$ ${\displaystyle L}$의 k ${\displaystyle k}$ 최소$$ 고유값에 해당하는 고유 벡터$)$를 계산하십시오.
3. 첫 번째 k ${\displaystyle k}$ 고유 벡터에$$ 의해 형성된 행렬을 고려하십시오. l ${\displaystyle$ l$}$ -th$$ 행은 그래프 노드 $l{\displaystyle }$ ${\displaystyle l}$의 특징을 정의함
4. 이러한 기능을 기반으로 그래프 노드 클러스터링(예: k-평균 클러스터링 사용)

유사성 매트릭스 $A{\displaystyle }$ ${\displaystyle A}$이(가) 아직 명시적으로 구성되지 않은$$ 경우, Lanczos 알고리즘에서와 같이 매트릭스 없는 매트릭스(명시적으로 유사성 매트릭스를 조작하거나 계산하지 않음) 방식으로 해당 고유치 문제에 대한 솔루션을 수행하면 스펙트럼 클러스터링의 효율이 개선될 수 있다.

대형 그래프의 경우 (정규화된) 그래프 라플라시안 행렬의 두 번째 고유값은 종종 조건이 좋지 않아 반복적 고유값 솔버의 수렴이 느리게 된다.전제조건화는 매트릭스 프리 LOBPCG 방식과 같이 융합을 가속화하는 핵심 기술이다.스펙트럼 군집화는 대형 그래프에서 먼저 공동체 구조를 파악한 뒤 군집화함으로써 성공적으로 적용됐다.^[4]

스펙트럼 클러스터링은 비선형 치수성 감소와 밀접한 관련이 있으며, 국소선형 임베딩과 같은 치수 감소 기법을 사용해 소음이나 특이치의 오류를 줄일 수 있다.^[5]

비용.

$ny{\displaystyle }$ {\$displaystyle n}$의 함수로서 데이터 포인트의 수를 나타냄으로써$$$ny{\displaystyle }$ ${\displaystyle n}$의 함수로서 메모리 풋프린트와 계산 시간 또는 수행된 산술 연산(AO)의 수를 추정하는 것이 중요하다$.$ 스펙트럼 클러스터링의 알고리즘에 관계 없이, 두 가지 주요 비용이 드는 항목은 그래프 랩의 구성이다.라키안 및 스펙트럼 내장을 위한 $k{\displaystyle }$ ${\displaystyle$k} 고유 벡터를$$ 결정한다.고유 벡터의 $n{\displaystyle }$ ${\displaystyle$ n$}-$ {\$displaystyle k}$ 행렬에서$$ 라벨을 결정하는 $마지막{\displaystyle }$ 단계는 일반적으로 ${\displaystyle \mathrm{kn}}$ ${\displaystyle kn}$AO만을$$ 필요로 하는 가장 비용이 적게 들고 메모리에 있는 라벨의 $n{\displaystyle }$ ${\$$displaystyle$ $n}$ $$} 벡터만 생성하는 것이다.

모든 거리 또는 상관 기반 클러스터링 방법에서 그래프를 구성할 필요가 흔하다.고유 벡터 계산은 스펙트럼 클러스터링에만 한정된다.

그래프 Laplacian 구성

그래프는 인접 행렬로 구성될 수 있으며 일반적으로 인접 행렬로 구성된다.구조는 매트릭스 없이 수행될 수 있다. 즉, 그래프의 매트릭스를 명시적으로 형성하지 않고 AO도 없다.메모리 공간을 늘리지 않고 인접 매트릭스 대신 수행할 수도 있다.어느 쪽이든, 그래프 Laplacian을 구성하는 비용은 $기본적$으로 n ${\displaystyle n}$ $$ ${\displaystyle n}$ 그래프$$ 인접 행렬을 구성하는 비용에 의해 결정된다.

더욱이, 정규화된 라플라시안은 정규화된 인접 행렬과 정확히 동일한 고유 벡터를 가지고 있지만, 고유값의 순서가 역전되어 있다.따라서 정규화된 라플라시안의 최소 고유값에 해당하는 고유 벡터를 계산하는 대신, 라플라시안 행렬에 대한 언급조차 하지 않고 정규화된 인접 행렬의 최대 고유값에 해당하는 고유 벡터를 동등하게 계산할 수 있다.

예를 들어, RBF 커널을 사용하여 그래프 인접 행렬을 순진하게 구성하면 고밀도가 유지되므로, 매트릭스의 $n{\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\$$displaystyle$ n$^{2$}}개 항목$$ 각각을 결정하기 $위해{\displaystyle {}^{}}$ n 2 ${\$displaystyle $n^{2}}$개의 메모리와$$ n ${\displaystyle {2\mathrm{}}^{}}$ ${\$$displaystyle n^{$2}}$개$의 AO가$$ 필요하다.나이스트롬 방법은^[6] 유사성 행렬의 근사치를 위해 사용될 수 있지만, 근사 행렬은 원소 양성이^[7] 아니며, 즉 거리 기반 유사성으로 해석할 수 없다.

그래프 인접 행렬을 희소 행렬로 구성하는 알고리즘은 일반적으로 가장 가까운 이웃 검색에 기초하며, 가장 가까운 이웃에 대해 주어진 데이터 포인트의 근처를 추정하거나 표본으로 추출하고 인접 행렬의 0이 아닌 항목만 비교하여 계산한다.따라서 선택한 가장 가까운 이웃의 수는 0이 아닌 항목 수를 결정하며, $종종{\displaystyle }$ 고정되어 n ${\displaystyle$ n$}$ $$ ${\displaystyle n}$ 그래프$$ 인접 행렬의 메모리 풋프린트가 $O{\displaystyle (n)}$ ${\displaystystyle O(n$ $오직$ O${\displaystyle (n)}$ ${\displaystysty O(n)$ 순차 산술 연산을 수행하도록 한다.s는 $0$이${\displaystyle \mathrm{아닌}}$O ($$n ) {\$displaystyle O($n$$$)}$ 항목을 계산하는 데 필요하며, 계산은 사소한 병렬로 실행할 수 있다.

고유 벡터 계산

그래프 Laplacian의 선택한 값의(k개체,<>n{\displaystyle k<,<>n})행렬{k\displaystyle}은 n{n\displaystyle}-by- k컴퓨팅의 비용은 정상적으로 n의 곱셈의 비용에{n\displaystyle} 벡터에 의해-by- n{n\displaystyle}그래프Laplacian 매트릭스 비례한다., varies 그래프 라플라시안 행렬이 밀도가 높은지 희박한지 여부.밀도가 높은 경우 $비용$은 O (${\displaystyle {n\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$) ${\displaystyle O(n^{2})}$ 입니다$.$문헌 비용 $O{\displaystyle ({n\mathrm{}}^{}}$ 3${\displaystyle {}^{}}$) ${\displaystyle O(n^{3})$에서 매우 일반적으로 인용되는 것은 $k{\displaystyle }$= ${\displaystyle n}$ ${\displaystyle k=n}$을 선택하는 데서 비롯되며$$$$, 예를 들어, Fiedler 벡터에 의해 결정된$$ 계층적 스펙트럼 $클러스터링{\displaystyle }$k = ${\displaystyle 1}${\$displaystyle k=1}$에서 명백히 오도 된다.

그 n의 희박한 경우 n{n\displaystyle}그래프Laplacian 행렬 O(n){O(n)\displaystyle}을 합했을 때 항목matrix-vector 제품의 원가고 따라서 k개체를 n{n\displaystyle}-by- k{k\displaystyle}컴퓨팅의,<>-by- n{\displaystyle k<,<>n}행렬{n\displaystyle}.선택한고유 벡터는 $O{\displaystyle }$ (${\displaystyle n}$) ${\displaystyle O(n)}$ AO이며$$ 메모리 $풋프린트$도 O${\displaystyle }$(${\displaystyle n)}$ ${\displaystyle O(n)}$뿐입니다.$$ 두 개 모두 $클러스터링{\displaystyle }$ n$${\$displaystyn}$ 데이터$$ 포인트의 복잡성이 가장 낮은 최적의 한계입니다.더욱이 LOBPCG와 같은 매트릭스 프리 고유값 솔버는 분산 메모리가 있는 다중 GPU에서 효율적으로 병렬로 실행될 수 있어 스펙트럼 클러스터링이 유명한 고품질 클러스터뿐만 아니라 최고의 성능까지 얻을 수 있다.^[8]

소프트웨어

스펙트럼 클러스터링을 구현하는 무료 소프트웨어는 다중 사전설정이^[11] 있는 LOBPCG를^[10] 이용한 Scikit-learn, ARPACK을 이용한 Scikit-learn^[9], 전력 반복법을 이용한 의사 고유 벡터 클러스터링용 MLlib,^[13] R과 같은 대규모 오픈 소스 프로젝트에서 이용할 수 있다.^[14]

다른 클러스터링 방법과의 관계

스펙트럼 군집화의 이면에 있는 아이디어는 즉시 명백하지 않을 수 있다.다른 방법과의 관계를 강조하는 것이 유용할 수 있다.특히 커널 클러스터링 방법의 맥락에서 설명할 수 있는데, 이는 다른 접근법과의 몇 가지 유사성을 드러낸다.^[15]

k-평균과의 관계

가중 커널 k-평균 문제는^[16] 객관적 기능을 스펙트럼 클러스터링 문제와 공유하는데, 이는 다단계 방법에 의해 직접 최적화할 수 있다.^[17]

DBSCAN과의 관계

연결된 그래프 구성요소를 결정하는 사소한 경우 - 가장자리가 잘리지 않는 최적의 클러스터 - 스펙트럼 클러스터링은 밀도 연결 구성요소를 찾는 DBSCAN 클러스터링의 스펙트럼 버전과도 관련이 있다.^[18]

군집 비교 방법

라비 칸난, 산토시 펨팔라, 아드리안 베타^[19] 등은 주어진 군집의 질을 규정하는 바이크리테리아 대책을 제안했다.그들은 각 군집(군집화에서)의 전도성이 적어도 α이고 군집간 에지의 무게가 그래프에 있는 모든 에지의 총 무게의 최대 ε 부분인 경우 군집화는 (α, ε) 클러스터라고 말했다.그들은 또한 같은 논문에서 두 개의 근사 알고리즘을 살펴본다.

역사 및 관련 문헌

스펙트럼 클러스터링은 오랜 역사를 가지고 있다.^{[20][21][22][23][24][2][25]}기계학습법으로서의 스펙트럼 클러스터링은 시앤말릭과^[2] 응, 요르단, 와이스가 대중화했다.^[25]

스펙트럼 클러스터링과 관련된 아이디어와 네트워크 측정도 클러스터링 문제와 분명히 다른 다수의 애플리케이션에서 중요한 역할을 한다.예를 들어, 스펙트럼 파티션이 더 강한 네트워크는 사회학과 경제학에서 사용되는 의견 상승 모델로 수렴하는 데 더 오랜 시간이 걸린다.^[26][27]

참고 항목

• 선호도 전파
• 커널 주성분 분석
• 군집 분석
• 스펙트럼 그래프 이론

참조