> For the complete documentation index, see [llms.txt](https://riverallzero.gitbook.io/summary/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://riverallzero.gitbook.io/summary/data-mining/clustering.md).

# Clustering

### hierarchical

![](/files/i2ZzmNVfMNZgfRAZz6Ff)

* 각 데이터 point를 cluster로 간주하고, 가장 가까운 cluster들을 반복적으로 병합(상향 방식)하여 클러스터를 형성한다.
* 결과적으로 dendrogram 형태의 계층 구조를 생성하여 클러스터 간의 관계를 시각적으로 표현할 수 있다.

### k-means

![](/files/Jk62rjHlgrFmJC8D3MDV)

1. 초기 k개의 centroid를 랜덤으로 부여한다.
2. 각 포인트를 가장 가까운 centroid와 연결하여 클러스터를 형성한다.
3. 클러스터가 형성된 후, 각 클러스터의 새로운 centroid를 계산한다.
4. centroid가 바뀌지 않을 때까지(즉, 수렴할 때까지) 2단계와 3단계를 반복한다.

* 적절한 k는 클러스터의 포인트들과 centroid 간 거리의 평균이 급격하게 감소한 후 조금씩 감소할 때로 결정한다.
* centroid와 포인트 간의 거리가 좁을수록 잘 클러스터링된 것이다.
* 초기 centroid의 위치가 클러스터링의 결과에 큰 영향을 미친다.

#### score

* $$SSE = \sum\_{i} \sum\_{x \in C\_i}(x-m\_i)^2$$, 낮을수록 cluster안의 point들이 잘 뭉쳐있다는 의미
* $$SSB = \sum\_{i} |C\_i|(m-m\_i)^2$$, 클수록 cluster이 잘 구분된다는 의미
* $$C\_i$$: i-th cluster
* $$m\_i$$: centroid of $$C\_i$$
* $$|C\_i|$$: size of cluster i
* $$m$$: mean of all points

### spectral(graph)

![](/files/mXVcHmS1w16BeFddWnXW)

1. $$L$$ matrix를 생성한다.
2. $$L$$의 eigen value($$\lambda$$)와 eigen vecotr($$x$$)를 찾는다.
3. $$\lambda\_2$$의 벡터로 매핑한다.
4. 매핑된 1차원 벡터 값을 정렬하고 분리한다.

#### graph cut

![](/files/Rd89loLkwW6ZYurBakFv)

* $$m$$: number of edges of the graph
* $$cut(A)=\sum\_{i \in A, j \notin A}W\_{ij}$$
* $$vol(A)=2\*{number \ of \ edges \ insde A + cut(A)}$$
* $$\varnothing(A)=\frac{cut(A)}{min(vol(A), 2m-vol(A))}$$

#### matrix

* $$A$$(adjacency matrix): 인접한 노드를 1로 표현
* $$D$$(degree matrix): 노드의 차수를 값으로 하는 대각행렬
* $$L$$(laplacian matrix): $$D - A$$
  * L의 모든 eigen value는 0 이상이고, $$x^TLx=\sum{ij}L\_{ij}x\_ix\_j \geq 0$$과 $$L=N^TN$$을 만족한다.
  * L에서 찾은 eigen value와 vector에 대해 $$\lambda\_2=min\_x\frac{x^TMx}{x^Tx}$$를 만족한다. 이때 $$\lambda\_2$$는 graph cut을 수행할 때 유용한 경계 값을 제공한다.

**eigen value & vector**

* $$\lambda: det(A-I\lambda)=0$$
* $$X: (A-I\lambda)v=0$$