12. Clustering and Image Segmentation

자신이 속한 집단이 어디인지 알고, 적합한 집단에 속해서 발전하는 것은 중요한 것이 아닐까

 

 

📌 clustering

• 유사한 성격을 가진 sample들을 묶어 그룹으로 형성하는 것
• 사전에 label이 주어지지 않는 unsupervised learning(비지도 학습)이다(classification은 data와 label을 같이주는 supervised learning이다)
• e.g.) data grouping, image segmentation
• method
  • k-means, agglomerative Hierarchical Clustering, Mean Shift

 

 

📌 clustering : Task Definition

• training data set을 통해서 학습된 모델은 test data(new data)가 들어오면 클러스터링된 k개의 군집(D)에 속할 확률을 구한 후 그 확률이 가장 큰 i값을 찾아서 new data이 들어가야 할 subset을 지정해준다

 

 

📌 Image segmentation

• goal : 이미지를 유사한 영역으로 나는 것
• 하나의 이미지 내에서 의미적으로나 인지적으로 유사한 영역을 찾는 것이다

 

 

📌 Normalized cuts for segmentation

• 픽셀 하나를 노드로 보고 이미지를 하나의 graph로 생각할 때, 노드 사이를 적절하게 cut(관련성이 낮은 weight를 자르는 것)하는 것이다

• goal
  • 군집 간 (A, B)의 유사도를 최소화하는 것
  • 군집 내 원소들의 유사도를 최대화하는 것

 

 

📌 Superpixel

• 유사성을 지닌 픽셀들을 일정 기준에 따라 묶어서 만든 하나의 커다란 픽셀을 의미한다
• 활용할 경우 image에서 의미있는 경계를 찾아 분류할 수 있다
• 정사각형 모양이 가장 편하지만 image의 경계선과 많이 다르기 때문에 정사각형으로 자르는 것은 현실적으로 어렵다

 

 

📌 Clustering Methods: K-means Algorithm

• K : 데이터 셋에서의 클러스터(부분 집합)의 수
• Means : 각 데이터로부터 그 데이터가 속한 클러스터의 중심까지의 평균 거리
• goal
  • mean의 값 최소화(해당 클러스터 내의 데이터들은 매우 유사하다는 것)
• 알고리즘
  1. 임의로 K개의 중심점을 아무 곳에 랜덤하게 설정한다
  2. 각각의 데이터에서 가장 가까운 중심점의 군집의 원소로 지정한다 (이 과정을 거치면 k개의 군집이 만들어질 것이다)
  3. 형성된 k개의 군집에 대하여 mean이 작아지도록 중심점을 다시 설정한다
  4. 2, 3번 과정을 반복하여 클러스터의 중심까지의 평균거리가 최소화되어 더 이상 중심점을 업데이트 할 수 없을 때까지 반복한다

step 1, 2

step 3

$$ J = \sum^N_{n=1}\sum^K_{i=1}r_{ni}||x_n-m_i||^2 $$

• sum of variances of every clusters
• J(large) : large variance(클러스터에 있는 데이터들이 퍼져있다)
• J(small) : small variance(클러스터에 있는 데이터들이 모여있다)
• 목적함수 J를 줄이는 것이 핵심

 

 

📌 Initial center vector 설정이 중요한 이유

• 최적화하는데 반복횟수가 initial center vector에 따라 차이가 난다. 즉, 알고리즘 성능에 매우 중요한 영향을 미친다

 

 

📌 Hierarchical Clustering

• k-means 알고리즘처럼 k가 주어지면 좋지만, 그렇지 않은 경우 사용하는 clustering이다
• HCA(계층적 군집 분석)은 말 그대로 데이터 하나하나를 계층에 따라 순차적으로 클러스터링 하는 기법이다
• Agglomerative(덩어리가 되는) Hierarchical Clustering
  • 데이터가 모두 나눠져있는 상태에서, 작은 단위로부터 클러스터링을 시작하여 모든 데이터가 한 덩어리가 될 때까지 반복하는 bottom-up방식으로 진행하는 것
  • 가장 거리가 가까운 데이터를 찾고, 이들을 묶고, 모든 데이터가 하나의 클러스터로 묶일 때까지 계속 반복한다

• Dendrogram(덴드로그램)
  • HCA의 수행과정을 표현한 것이다
  • 먼저 묶일수록, 수평선의 높이가 낮다
   

2개의 cluster로 나눈 경우

 

 

📌 Distance of clusters for merging

• 최단연결법
  • 각 클러스터 내의 원소들 사이의 거리가 가장 짧은 것을 두 클러스터 사이의 거리라고 생각하는 방법
• 최장연결법
  • 각 클러스터 내의 원소들 사이의 거리가 가장 먼 것을 두 클러스터 사이의 거리라고 생각하는 방법
  • 이상치에 민감하고 계산량이 많다
  • 가장 거리가 먼 클러스터를 묶어준다는 의미는 아니다. 클러스터를 merge할 때는 무조건 거리가 가까운 것끼리 해주어야 한다(유사한 데이터를 묶어주는 것이 목적이니까)
• 평균연결법
  • 각 원소들 간의 전체 거리를 다 계산한 후 평균값을 클러스터 간의 거리로 보는 방법
  • 이상치에 덜 민감하지만, 계산량이 많다
• 중심연결법
  • 각 클러스터에 대해 중심을 구하고, 그 중심 간의 거리를 계산하는 방법
  • 이상치에 덜 민감하고, 계산량도 적다
• 와드 연결법
  • 두 개의 클러스터를 하나로 보았을 때의 중심과 각 클러스터의 원소들 간의 거리를 클러스터 간의 거리로 보는 방법

 

 

📌 Mean Shift

• 데이터 집합의 밀도 분포를 기반으로 객체를 고속으로 추적하는 알고리즘
• sample window 내에서 데이터의 밀도가 가장 높은 곳으로 평균을 이동하는 알고리즘
• 임의로 sample window(파란색 영역)을 설정하고, 거기에서 무게중심(주황색 점)을 찾는다
• 이 과정을 반복하다보면, 목표 객체를 추적할 것

빨간색 점 - sample window, mean-shift 알고리즘을 적용하면 밀도가 가장 높은 곳으로 점들이 모인다

 

• 장점
  • 일반화되고 실용적인 알고리즘
  • 영역의 모양과 숫자에 대해 유연하여 많은 곳에 적용 가능
  • 이상치에 덜 민감하다
• 단점
  • sample window의 사이즈를 미리 결정해야 한다
  • 사이즈에 따라 정확한 peak를 찾지 못하거나, local minimum에 빠질 수 있다
  • 물체와 배경의 색깔이 유사(밀도가 낮다는 뜻)하면 알고리즘의 성능이 떨어진다
• 사용 분야
  • segmentation을 많이 하는 경우, 객체 추적, 클러스터링