인공지능개론 | Clustering

⚠ Before reading the post ⚠

본 포스팅은 컴퓨터 공학 계열 전공자 대학교 4학년에서 대학원생 기준으로 작성하였습니다.
기본적인 자료구조나 알고리즘 내용은 생략하였습니다.

Clustering | 클러스터링

KNN에서 배운 바와 같이 비슷한 개체를 묶어서 분류하는 방법이다. 대표적인 Unsupervised learning의 형태로, labed된 데이터가 필요없는 학습 방법이다.
클러스터링은 보통 검색 엔진에 활용되는데, 유사한 단어가 출현이 기대되는 검색된 문서들끼리 같은 클러스터로 묶이게 된다.

Representation & Similarity

document 클러스터링 하기 전 몇 가지:

문서 표현: 비슷한 벡터 공간에 존재 여부에 따라 인지
유사도 혹은 거리: cosine similarity, euclidean distance

어떤 것을 사용하느냐에 따라서도 중요하지만 클러스트의 적당한 크기인지도 중요하다.

Clustering Algorithm

클러스러링 알고리즘은 크게 두 가지로 나뉜다.

Flat Algorithm: 랜덤한 파티션 나누기가 특징, iteration마다 점차 좋아지는 결과를 보이는 것이 특징이다. 대표적으로 K-means가 있다.
Hierarchical Algorithm: 트리 형태로 클러스터링하는 것이 특징이다. 아래에서 위로 융합하면서 올라오거나 혹은 위에서 아래로 나뉘면서 나뉘는 두 가지 형태로 존재한다.

Flat Algorithm - K-means

문서 표현이 실수 벡터라고 가정하자.
클러스터는 기본적으로 centroid를 기반하여 유클리드 거리에 기반하여 인스턴스들을 재할당하게 된다. 여기서 centroid는 기준이 되는 지점의 평균 혹은 중력이라고 생각하면 된다. 아래 이미지 참고.

대략적인 순서는 아래와 같다. (n:document vector num. m: vector dimension)

임의의 K개 seed를 선택한다. 결과에 따라 다르게 나타므로 (1) 초기화 시 heurstic을 이용하여 가장 멀리 떨어진 벡터를 선택하거나 (2) 좋은 방향으로 재할당하도록 여러 번 시도해본다. (이전에 배운 local search 방법과 유사하다.)
거리 계산( $O(m)$ )에서 거리가 짧은 seed들을 같은 클러스터로 K개 할당( $O(Kn)$ )한다. ( $O(Knm)$ )
centroid를 계산( $O(nm)$ )하고 2.로 돌아간다. 이 때 terminal condition으로 iteration의 수를 고정한다던가, cluster나 centroid가 더 이상 변화하지 않은 모습을 보일 때(state-never-change) 종료한다. 물론 예외는 있는데, centroid가 동일하다고 해서 아래와 같이 같은 결과가 비추어지지는 않는다.

cluster 계산 완료

iteration(I)이 끝나면 최종적으로 $O(IKnm)$ 이므로 시간복잡도가 선형적인 것을 알 수 있다! Clustering 방법은 다음 포스팅에서 다루어보게 될 EM 알고리즘과도 밀접해 있는데, 이는 다음 시간에 알아볼 예정이다.

Hierarchical Clustering Algorithm - Bottom-up

Bottom-up은 더 큰 클러스터로 융합해서 올라가는 것이 특징이다. 알고리즘의 대략적인 순서는 아래와 같다.

N개의 개체들을 클러스터에 포함한다.
‼ 클러스터 유사도를 계산한다.
더 큰 클러스터로 포함(Combine Cluster)시킨다. 2. 반복

‼ 클러스터간 유사도 계산 방법(intercluster similarity)으로 3가지 정도 존재한다. A-F 6개의 object들의 15개 조합을 중심으로 예제와 함께 확인하자!

single-link clustering: 가장 가까운 cluster간의 거리 pair을 대표 거리로 선정한다. 소개한 방법 중에서 가장 좋은 best case이다.

위 사진에서 AF가 가장 유사도가 크므로 먼저 하나로 묶는다. 소거되는 순서는 위 표를 따라 소거된다.

이미지에 그대로 적힌 것처럼 유사도가 가장 높은 것과 비교하면서 올라가게 된다(=Combine cluster). 다 계산된 형태에서 similarity threshold에 따라 클러스터로 묶이게 된다. 여기서 이해가 안될 것 같아 설명!

Q. 2.에서는 왜 B가 0.8로 바뀌었는가?

어렵게 생각할 필요없다! F가 A와 동일한 클러스터 레벨이며, BA보다 BF의 유사도가 더 크므로 더 큰 유사도로 갱신이 된 것 뿐이다. 이런 방법으로 테이블이 계속 갱신된다.

similarity level이 그 이상끼리 클러스터로 묶이는 모습을 확인해볼 수 있다.

complete-link clustering: 가장 유사도가 낮은 pair을 선정한다. 위와 반대로 worst case.

위와는 반대로 같이 묶이게 될 때 가장 작은 유사도 값으로 테이블이 갱신된다. 또한, 갱신된 테이블 2.에서 가장 높은 유사도를 가진 BE가 묶이게 된다. 이전 방법에서는 unbalenced tree 형태를 보였다면, 이번 방법에서는 갱신된 테이블의 유사도가 가장 높은 부분에서 클러스터링 하게 되므로 balenced tree 형태를 가지게 된다.

마찬가지로 다음 가장 높은 유사도를 가진 부분이 C와 D 부분이므로 표의 내림차순 순서상 C를 먼저 연결한다. AF보다 BCE쪽의 유사도가 D입장에서는 더 높으므로 BCDE와 함께 묶이게 된다.

사실상 마지막은 부가적인 계산은 필요 없다. 전체적인 트리에서 similarity threshold별 나눌 수 있는 것을 확인해볼 수 있다.

group average-link clustering: single-link와 complete-link의 평균을 이용한 방법

여기서는 자세하게 다루지는 않음.

Wrap up & Conclusion

클러스터링은 두 가지 방법으로 Flat algorithm으로 K-means를, Hierarchical algorithm 방법으로 bottom-up 방법에 대해서 배워보았다.

K-means: K개의 centroid 중심으로 다른 centroid 유사도에 비해 가장 높은 유사도(혹은 가까운 거리)를 가진 개체를 자신의 군집으로 분류하는 방법이다. cluster가 더 이상 변동이 없을 때까지거나 iteration까지 계속 이어지게 되는데, 문제는 centroid 초기화할 때 마다 local search처럼 결과 각기 다른 결과를 보인다는 단점이 있다. 이런 점은 거리가 먼 centroid들을 선택하는 방법이 있으나, 굳이 K개라고 boundary를 설정해야 되는 번거로운 점이 있다. 시간이 선형적이다는 점에서는 장점.
Hirarchical algorithm: N개의 object의 pair 유사도를 먼저 계산 후 묶어서 또 다시 개체들간 유사도를 재계산하여 가장 높은 유사도를 다시 선택하여 큰 클러스터 형태로 combine 하는 방법이다. combine 방법(intercluster similarity)으로는 3가지를 배웠다.
- single-link clustering: 가장 높은 유사도끼리 묶고 높은 유사도 중심으로 테이블을 갱신해 나가는 방법이다. 완성된 결과물은 unbalenced tree 형태.
- complete-link clustering: 높은 유사도를 같은 클러스터로 선택하되, 테이블 갱신 시에는 유사도가 낮은 방향으로 갱신이 된다. combine 시에는 갱신된 테이블 중 가장 높은 유사도가 높은 pair을 선택하여 갱신하게 된다.
- group average-link clustering

완성된 트리를 토대로 similarity threshold에 따라 클러스터로 묶을 수 있다.

따지고 보면 크게 어려운 내용은 아닌데, 개인적으로 배운 내용 중 많아서 힘들었다..ㅠㅠ
너무 막 써 내려간 포스팅이라 틀린 부분이나 모호한 부분은 댓글을 다시면, 친절히 답변해드리겠습니다 ㅠ