.

그림, 실습코드 등 학습자료 출처 : https://datascienceschool.net

# Affinity Propagation

• Affinity Propagation의 최종결과는 케이미노이드와 비슷한 결과가 나온다. 있는 데이터중에 어떤 것이 센트로이가 된다. 여기서는 센트로이드라는 말을 안쓰고 대표데이터라고 부른다. 모든데이터가 대표데이터로 쓸 수 있는데 누가 더 대표성이 높은가 업데이트를 해가면서 이 데이터들간에 나를 대표할 데이터는 어떤 데이터다라고 하나 선택해야한다.

• 여기서는 두가지 계수를 구한다. 하나는 responsibility, 다른 하나는 availability이다. responsibility는 i번째 데이터가 존재하면 그 i번째 데이터의 대표는 k다라고 할 수 있는 근거, 확률, 신뢰도를 말한다. k 번째 데이터가 i번째 데이터의 대표가 되어야 한다는 근거이다. 여기서 i와 k는 같을 수도 있다.

• availability는 위와 반대개념이다.responsibility는 대표로 뽑힌 데이터 후보입장에서의 근거인것이고, availability는 i번째 데이터가 k번째 데이터를 뽑는 이유를 나타내는 것이다.

• 실제로는 아래와 같이 두가지를 계속 alternating을 하면서 계산을 한다. 메트릭스들이 있으면 특정 두개의 메트릭스를 계산하고 r메트릭스 a메트릭스 r메트릭스 a메트릭스 이런식으로 교대로 계산을 해내간다.

\[\ r(i, k) \leftarrow s(i, k) - \max_{k' \neq k} ( a(i, k') + s(i, k'))\] \[\ a(i, k) \leftarrow \min(0, r(k, k) + \sum_{i' \neq i,k} r(i', k))\] \[\ s(i,k) = -|| x_i - x_k ||^2\]

• 여기서 s는 유사도를 나타낸다. 그래서 위의 식을 보면 알 수 있듯이 각 데이터간에 유사도는 계산이 되어 있어야 한다. 그 유사도를 바탕으로 r이랑 a를 계속 교대로 계산해야한다. Affinity Propagation는 하이퍼파라미터가 직접적으로 들어가지는 않는데 최초의 r메트릭스를 어떤 상수값으로 정해주면 이 r은 자기가 자기를 뽑는 responsibility를 하이퍼파라미터로 쓰게 되면 최종적으로 몇개의 클러스터로 수렴하게 나아간다.

• 위에서 언급한 이 하이퍼파라미터를 크게 주게되면 다들 자기가 잘났다고 대표가 많아지게 된다. 클러스터의 갯수가 증가하게 된다. 이 초기값을 적게주면 반대로 클러스터의 갯수가 감소하게 된다.

• 하이퍼파라미터가 조금 복잡하게 되어 있기는 하지만 클러스터의 갯수를 직접적으로 정하지는 않는다.

# mean-shift

• 그밖에 ski-learn에 구현된 클러스터링 기법들을 알아보면 mean-shift방법이 있다. 이 방법은 kmeans와 비슷한 형태이다. kmeans와 dbscan의 중간정도로 보면 된다. mean-shift도 계층적 클러스터링처럼 모든 데이터가 다 클러스터이다. 그 다음에 dbscan처럼 이웃을 결정한다. 처음에는 클러스터의 센터를 자기자신으로 정하고 이웃들을 평균하여 그 이웃들의 중심으로 클러스터의 센터를 옮겨준다.

• 처음에는 데이터 개수가 n개면 n개의 센트로이드가 있는데 이 센트로이드들이 위치를 옮기게 된다. 그다음에 센트로이드간에 최소거리를 정해서 최소거리보다 작게 센트로이드들이 붙은경우 얘네들은 합쳐져서 새로운 센트로이드가 된다. 이 센트로이드 들이 가운데로 몰리는 경향을 보인다.

# spectral clustering

• dbscan처럼 데이터들이 있으면 데이터들이 연결이 되어 있다고 가정을 한다. 연결이 되어 있으면 하나의 클러스터링으로 보는데 이 연결된 것 데이터들중에 어딘가를 끊는다. 끊으면 두개 이상의 클러스터로 바뀌게 되는데 어디를 끊어야지 제일 좋은가 라는 것을 그래프컷이라는 어떤 목적함수를 설정해서 그래프컷이 가장 큰값이 되도록 어디를 끊을지 설정한다.

# 버치

• 데이터가 있으면 데이터를 반드시 두개혹은 세개 클러스터로 만들게 되는데 맨처음에 데이터가 두개가 있고 새로운 데이터 하나가 들어온다고 하면 이 새로운 데이터가 어디에 붙을지 결정을 한다. 그 다음에 하나가 들어오면 또 어디에 붙을지 결정하고 그래서 팀이 두팀으로 나누어져 있고 새로운 데이터가 들어오면 어디에 붙을지 결정하다가 어느 일정개수 이상이되면 또 클러스터링을 쪼개게된다.

• 버치는 수학적으로 어떤 목적함수가 있는 것은 아니다. 일종에 알고리즘 같은 것이다. 왜 이 모델을 쓰냐면 데이터가 너무 많아서 흔히 말하는 빅데이터를 다룰때 사실 지금까지 나온 모든방법들은 못쓴다. 왜냐하면 대부분의 방법들이 데이터간의 거리를 구해야 하는데 그게 불가능하기 때문이다. 이 버치라는 방법은 정확한 어떤 수학적인 클러스터링은 아니지만 클러스터링을 나눌 수는 있기때문에 장점이 있다.

# 이미지 압축에서의 클러스터링

• 이미지를 컴퓨터에 저장하려면 픽셀하나하나에 대해서 rgb데이터를 다 저장해야한다. 이미지 픽셀수 x 3 만큼 저장을 해야한다. 이 rgb의 3차원 데이터를 클러스터링을 사용하면 비슷한 색깔로 묶을 수 있다. k는 3인 kmeans 클러스터링을 하라고 하면 비슷한 색깔끼리 묶여서 데이터가 압축이 되는 효과를 나타낸다. 다만 이런방식은 데이터가 비슷한 색깔끼리 묶이게 되기때문에 아주 정확한 데이터 정보는 손실될 수 밖에 없다.