03-29 07:21
Notice
Recent Posts
Recent Comments
관리 메뉴

Scientific Computing & Data Science

[Artificial Intelligence / Machine Learning] k-means with R 본문

Artificial Intelligence/Machine Learning

[Artificial Intelligence / Machine Learning] k-means with R

cinema4dr12 2016. 1. 2. 17:46

Written by cinema4dr12

이전에 Supervised Learning의 기법 중 하나로서 k-Nearest Neighbor(kNN) 알고리즘에 대하여 살펴본 바가 있다.

이번 글에서는 Unsupervised Learning의 기법 중 하나인 k-means 알고리즘과 예제를 R을 이용하여 살펴보도록 하겠다.

Clustering이란, 분류가 되어 있지 않는 데이터 집합들을 그룹화 하는 것으로, 이미 데이터의 분류 기준이 정해져 있는 상태에서 새로운 데이터를 어느 집합으로 분류할 것인가를 정하는 classification과 대비된다.


그렇다면 clustering이란 무엇인가?

[1] Clustering이란 다음 기준을 만족하여 데이터를 분류하는 것이다:

(1) Class 내에서는 데이터 간 유사성이 높다.

(2) Class 간의 데이터 끼리는 유사성이 낮다.

[2] 데이터로부터 클래스 라벨과 클래스의 개수를 직접 찾는 것이다.

[3] 오브젝트들 간 자연스러운 집합을 찾는 것이다.


이전 글에서 k-NN에 대하여 살펴본 바가 있는데 이것은 classification 알고리즘의 일종이다. Classification이 이미 class 또는 그룹이 정의되어 있는 상태에서 새로운 데이터가 어디 속하는지 찾아내는 작업이라면 clustering이란 주어진 데이터만으로 그룹을 찾아내는 작업이라 할 수 있다.

우선 이론적인 배경을 살펴보도록 하겠다. 


표준 k-means 알고리즘은 1957년 Hugo Steinhaus와 Stuart Lloyd의 의해 각각 개발되었으나, 그 당시에는 "k-means"라고 불려지지 않았다. 1967년 James MacQueen이 처음으로 "k-means"라는 용어를 사용하기 시작하였으며, 1982년까지는 Bell Labs에서만 출간되었다.

새로운 버전의 알고리즘은 60년대와 70년대의 이 알고리즘의 발명가 및 개발자의 이름을 따서 Hartigan-Wong, Lloyd, Forgy로 명명되었다. R의 k-means 함수의 기본 알고리즘은 Hartigan-Wong이며 기본 알고리즘도 충분한 성능을 지닌다.

보다 최근의 알고리즘인 k-means++은 2007년 David Arthur과 Sergei Vassilvitskii(현재 Google에서 근무)에 의해 개발되었으며, 초기 seed를 최적화하여 k-means의 수렴 문제에 대한 해결을 하고자 하였다.


Part 1- Basic Concept

다음과 같이 n개의 데이터 집합을 X라고 정의하자.



각각 d개의 feature를 갖는 벡터 xi



이며, 따라서,



이다. 한편 cluster 집합 c는



으로 정의되며, 오차제곱합(the sum of squared error)은 다음과 같이 정의된다:



여기서, i 번째 데이터에 대한 j 번째 변수값이며, k 번째 cluster에 대한 j 번째 평균(mean)값이다.


k-means 알고리즘은 이 오차제곱합을 최소화하는 알고리즘이다.


Part 2 - Algorithm

k-means 알고리즘은 다음과 같다:

1.  k개의 centroid를 임의로 정한다.

2.  각 데이터 포인트를 가장 가까운 centroid에 할당한다.

3.  Cluster 내에서 모든 데이터 포인트들의 평균값을 계산하여 새로운 centroid로 정한다.

4.  가장 가까운 centroid로 데이터 포인트들을 할당한다.

5.  데이터 포인트들이 새로운 centroid로 할당되지 않을 때까지 또는 최대 반복계산(iterations)에 도달할 때까지 3과 4의 과정을 반복한다.


Part 3 - Examples

예제에 사용할 데이터는 R에 내장된 데이터인 "mtcars"이다.

R에서 k-means를 계산하는 함수는 kmeans()이며, 각 arguments는 Help를 참고하기 바란다.


이해를 돕기 위해 2D 플롯이 가능한 우선 2개의 feature에 대한 예제를 소개한다.


Example #1: 2 features - mpg & cyl



Example #2: all-features


                     mpg cyl  disp  hp drat    wt  qsec vs am gear carb cluster
Mazda RX4           21.0   6 160.0 110 3.90 2.620 16.46  0  1    4    4       4
Mazda RX4 Wag       21.0   6 160.0 110 3.90 2.875 17.02  0  1    4    4       4
Datsun 710          22.8   4 108.0  93 3.85 2.320 18.61  1  1    4    1       2
Hornet 4 Drive      21.4   6 258.0 110 3.08 3.215 19.44  1  0    3    1       3
Hornet Sportabout   18.7   8 360.0 175 3.15 3.440 17.02  0  0    3    2       3
Valiant             18.1   6 225.0 105 2.76 3.460 20.22  1  0    3    1       4
Duster 360          14.3   8 360.0 245 3.21 3.570 15.84  0  0    3    4       1
Merc 240D           24.4   4 146.7  62 3.69 3.190 20.00  1  0    4    2       2
Merc 230            22.8   4 140.8  95 3.92 3.150 22.90  1  0    4    2       4
Merc 280            19.2   6 167.6 123 3.92 3.440 18.30  1  0    4    4       4
Merc 280C           17.8   6 167.6 123 3.92 3.440 18.90  1  0    4    4       4
Merc 450SE          16.4   8 275.8 180 3.07 4.070 17.40  0  0    3    3       3
Merc 450SL          17.3   8 275.8 180 3.07 3.730 17.60  0  0    3    3       3
Merc 450SLC         15.2   8 275.8 180 3.07 3.780 18.00  0  0    3    3       3
Cadillac Fleetwood  10.4   8 472.0 205 2.93 5.250 17.98  0  0    3    4       5
Lincoln Continental 10.4   8 460.0 215 3.00 5.424 17.82  0  0    3    4       5
Chrysler Imperial   14.7   8 440.0 230 3.23 5.345 17.42  0  0    3    4       5
Fiat 128            32.4   4  78.7  66 4.08 2.200 19.47  1  1    4    1       2
Honda Civic         30.4   4  75.7  52 4.93 1.615 18.52  1  1    4    2       2
Toyota Corolla      33.9   4  71.1  65 4.22 1.835 19.90  1  1    4    1       2
Toyota Corona       21.5   4 120.1  97 3.70 2.465 20.01  1  0    3    1       2
Dodge Challenger    15.5   8 318.0 150 2.76 3.520 16.87  0  0    3    2       3
AMC Javelin         15.2   8 304.0 150 3.15 3.435 17.30  0  0    3    2       3
Camaro Z28          13.3   8 350.0 245 3.73 3.840 15.41  0  0    3    4       1
Pontiac Firebird    19.2   8 400.0 175 3.08 3.845 17.05  0  0    3    2       5
Fiat X1-9           27.3   4  79.0  66 4.08 1.935 18.90  1  1    4    1       2
Porsche 914-2       26.0   4 120.3  91 4.43 2.140 16.70  0  1    5    2       2
Lotus Europa        30.4   4  95.1 113 3.77 1.513 16.90  1  1    5    2       2
Ford Pantera L      15.8   8 351.0 264 4.22 3.170 14.50  0  1    5    4       1
Ferrari Dino        19.7   6 145.0 175 3.62 2.770 15.50  0  1    5    6       4
Maserati Bora       15.0   8 301.0 335 3.54 3.570 14.60  0  1    5    8       1
Volvo 142E          21.4   4 121.0 109 4.11 2.780 18.60  1  1    4    2       2

각 cluster별로 분류한 결과는 다음과 같다:


> cl1
                mpg cyl disp  hp drat   wt  qsec vs am gear carb cluster
Duster 360     14.3   8  360 245 3.21 3.57 15.84  0  0    3    4       1
Camaro Z28     13.3   8  350 245 3.73 3.84 15.41  0  0    3    4       1
Ford Pantera L 15.8   8  351 264 4.22 3.17 14.50  0  1    5    4       1
Maserati Bora  15.0   8  301 335 3.54 3.57 14.60  0  1    5    8       1


> cl2
                mpg cyl  disp  hp drat    wt  qsec vs am gear carb cluster
Datsun 710     22.8   4 108.0  93 3.85 2.320 18.61  1  1    4    1       2
Merc 240D      24.4   4 146.7  62 3.69 3.190 20.00  1  0    4    2       2
Fiat 128       32.4   4  78.7  66 4.08 2.200 19.47  1  1    4    1       2
Honda Civic    30.4   4  75.7  52 4.93 1.615 18.52  1  1    4    2       2
Toyota Corolla 33.9   4  71.1  65 4.22 1.835 19.90  1  1    4    1       2
Toyota Corona  21.5   4 120.1  97 3.70 2.465 20.01  1  0    3    1       2
Fiat X1-9      27.3   4  79.0  66 4.08 1.935 18.90  1  1    4    1       2
Porsche 914-2  26.0   4 120.3  91 4.43 2.140 16.70  0  1    5    2       2
Lotus Europa   30.4   4  95.1 113 3.77 1.513 16.90  1  1    5    2       2
Volvo 142E     21.4   4 121.0 109 4.11 2.780 18.60  1  1    4    2       2
 
> cl3
                   mpg cyl  disp  hp drat    wt  qsec vs am gear carb cluster
Hornet 4 Drive    21.4   6 258.0 110 3.08 3.215 19.44  1  0    3    1       3
Hornet Sportabout 18.7   8 360.0 175 3.15 3.440 17.02  0  0    3    2       3
Merc 450SE        16.4   8 275.8 180 3.07 4.070 17.40  0  0    3    3       3
Merc 450SL        17.3   8 275.8 180 3.07 3.730 17.60  0  0    3    3       3
Merc 450SLC       15.2   8 275.8 180 3.07 3.780 18.00  0  0    3    3       3
Dodge Challenger  15.5   8 318.0 150 2.76 3.520 16.87  0  0    3    2       3
AMC Javelin       15.2   8 304.0 150 3.15 3.435 17.30  0  0    3    2       3


> cl4
               mpg cyl  disp  hp drat    wt  qsec vs am gear carb cluster
Mazda RX4     21.0   6 160.0 110 3.90 2.620 16.46  0  1    4    4       4
Mazda RX4 Wag 21.0   6 160.0 110 3.90 2.875 17.02  0  1    4    4       4
Valiant       18.1   6 225.0 105 2.76 3.460 20.22  1  0    3    1       4
Merc 230      22.8   4 140.8  95 3.92 3.150 22.90  1  0    4    2       4
Merc 280      19.2   6 167.6 123 3.92 3.440 18.30  1  0    4    4       4
Merc 280C     17.8   6 167.6 123 3.92 3.440 18.90  1  0    4    4       4
Ferrari Dino  19.7   6 145.0 175 3.62 2.770 15.50  0  1    5    6       4


> cl5
                     mpg cyl disp  hp drat    wt  qsec vs am gear carb cluster
Cadillac Fleetwood  10.4   8  472 205 2.93 5.250 17.98  0  0    3    4       5
Lincoln Continental 10.4   8  460 215 3.00 5.424 17.82  0  0    3    4       5
Chrysler Imperial   14.7   8  440 230 3.23 5.345 17.42  0  0    3    4       5
Pontiac Firebird    19.2   8  400 175 3.08 3.845 17.05  0  0    3    2       5


Comments