Artificial Intelligence #09 K-Means Clustering

김서영·2024년 10월 30일

Artificial Intelligence 인공지능 2판

인공지능

목록 보기

8/13

1. Unsupervised Learning (비지도 학습)

Label(정답)이 없는 data를 학습하는 방법

clustering(군집화)는 대표적인 비지도 학습
이외에 차원 축소, 생성 모델 등 다양한 방법 존재

Clustering

Label이 없는 data들 내에서 비슷한 특징이나 패턴을 가진 data들 끼리 군집화한 후 어떤 군집에 속하는지 추론하는 방법
(대표적인 Clustering Algorithm으로 K-Means Clustering이 있다)

2. K-Means Clustering

$K$ 값이 주어져 있을 때, $n$ 개의 데이터들을 $K$ 개의 클러스터로 묶는 알고리즘

$K$ : 군집의 수 (number of cluster)
$means$ : 평균

~~(데이터의 평균을 활용하여 $K$ 개의 군집으로 묶는다는 의미)~~

Initialization

random으로 $K$ 개의 centeroid 를 생성 { $c^1, c^2, ... , c^k$ }

특정 조건이 발생할 때까지 다음 2 step을 반복

Assignment step

각 데이터의 cluster membership을 결정

Refitting step

각 centroid를 cluster member의 중심으로 이동

Result

사진 출처

Local minima 문제

Kmeans Algorithm은 Centroid의 초기 상태에 따라 성능이 달라질 수 있음

3. K-Means Clustering 실습

: Hard Coding / sklearn을 이용한 Coding

데이터 생성

import numpy as np
import matplotlib.pyplot as plt

data=[]
for i in range(30):
  data.append([np.random.uniform(40,60), np.random.uniform(40,60),0])
  data.append([np.random.uniform(50,120), np.random.uniform(50,120), 1])
  data.append([np.random.uniform(100,190), np.random.uniform(90,160), 2])

data=np.array(data)

plt.scatter(data[:,0], data[:,1])
plt.show()

Centroid initialization

$K$ 값을 받아서 centroid $K$ 개를 만들고 Numpy Random을 이용하여 각 centroid 의 position 초기화

def initialization(k):
  centroid=[]
  for i in range(k):
    centroid.append([np.random.uniform(4,190), np.random.uniform(4,190)])
  return np.array(centroid)

centroid = initialization(3)
print(centroid)

plt.scatter(centroid[:, 0], centroid[:, 1], color='red')
plt.scatter(data[:,0], data[:,1])
plt.title('Data Points and Centroids')
plt.show()

Distance function

두 변수 a,b가 입력되면 변수 간에 거리를 계산하여 return 하는 함수
~~(np.sum을 사용함으로써 feature의 수가 뭐든 사용할 수 있음)~~

def distance(a,b):
  return np.sqrt(np.sum((a-b)**2))

K-Means Algorithm

def k_means(data, centroid):
  k=len(centroid)
  n=len(data)
  x_n=[]

  #assignment step
  for i in range(n):
    D=[0]*k
    for c in range(k):
      D[c]=(distance(data[i, 0:2], centroid[c, :]))
    x_n.append(np.argmin(D))
  x_n=np.array(x_n)

  #refitting
  for i in range(k):
    index=np.where(x_n==i)[0]
    mu=np.mean(data[index, 0:2], axis=0)
    centroid[i]=mu
  
  return centroid, x_n
  
for i in range(50):
  new_centroid, x_n = k_means(data, centroid)
  plt.scatter(new_centroid[:, 0], new_centroid[:, 1], color='red')
  plt.scatter(data[:,0], data[:,1])
  plt.title(f'Loop = {i} Data Points and Centroids')
  plt.show()