by
Apr 27. 2020
가까운 것끼리 묶어주기, k-means는 누가 만든 것
[야만인] 인공지능 탄생의 뒷이야기
레이블 label(꼬리표, 식별자)이 있는 데이터로부터 모델을 만들어
레이블이 없는 데이터의 레이블을 예측하는 것을
머신러닝 machine learning에서는 지도학습 supervised learning의 '분류 classification'라고 합니다.
온라인 쇼핑몰이나 대선 캠프처럼
고객이나 상품, 유권자에 대한 레이블이 없고,
심지어 몇 개의 그룹으로 나누어야 하는 지도 알 수 없는 경우라면
어떻게 분류할 수 있을까요?
이렇게 레이블이 없는 데이터 내부의 패턴과 구조를 발견하는 것을
비지도학습 unsupervised learning이라고 하는데
그 중에서도 비슷한 속성끼리 묶어주는 알고리즘을
군집화 clustering라고 합니다.
k-means는 군집화 문제를 해결하는
가장 간단한 비지도학습 알고리즘 중 하나입니다.
k-means 알고리즘을 간단하게 설명해보겠습니다.
1) 주어진 데이터에서 찾아내고자 하는 k개의 군집을 결정합니다.
2) k개의 다른 포인트를 임의로 결정합니다. 이를 초기 군집이라고 합니다.
3) 각 데이터별로 k개의 초기 군집까지의 거리를 계산합니다. 그리고 가장 가까운 거리에 있는 군집에 해당 데이터를 할당합니다.
4) 할당이 끝나면 각 군집의 대표지점을 구합니다. 대표지점은 평균일 수도 있고, 중간값일 수도 있습니다. 이렇게 구한 대표지점과 남은 각 데이터 사이의 거리를 기반으로 다시 데이터를 군집에 할당합니다.
5) 4)의 과정을 더 이상 할당된 군집의 대표지점이 변하지 않을 때까지 반복합니다.
1950년대부터 1970년대까지 통신기술과 컴퓨터가 빠른 속도로 발달하면서
각 분야에서 데이터를 군집화하기 위한 알고리즘이 따로따로 발전하게 됩니다.
당시에는 지금처럼 인터넷을 통한 논문검색이 없어서
다른 분야에서 연구된 아이디어를 모르고 각기 발전하는 경우가 많았습니다.
백프로퍼게이션 backpropagation 알고리즘도
1986년 럼멜하트 David Everett Rumelhart가 논문으로 발표했지만
나중에 알고보니 이미 1969년 제어계측학 분야에서 위치 호 Yu-Chi Ho가 사용했었고,
1974년 폴 워보스 Paul Werbos가 박사학위 논문으로 발표한 아이디어에도 있었습니다.
k-means라는 용어는 1967년 제임스 맥퀸 James B. MacQueen에 의해 처음 쓰여졌습니다.
이 아이디어는 1956년 휴고 스타인하우스 Hugo Steinhaus로부터 시작된 것입니다.
그런데 알고보니 1957년 벨 연구소의 스튜어트 로이드 Stuart P. Lloyd가 펄스 부호 변조(Pulse-Code Modulation; PCM) 분야에서 이미 개발하여 사용 중인 알고리즘이었고,
1965년 생물학 분야에서 에드워드 포지 Edward W. Forgy가 비슷한 알고리즘을 발표하기도 했습니다.
그래서 컴퓨터과학 분야에서는 k-means를
로이드 Lloyd 알고리즘 또는 로이드-포지 Lloyd-Forgy 알고리즘으로 부르기도 합니다.
이렇듯 서로 다른 분야에서 발전한 알고리즘이나
현재 머신러닝에서는 굉장히 많이 쓰는 알고리즘입니다.
