K-평균 알고리즘

K평균 클러스터링(K-Means Clustering)

---

 클러스터링이란 데이터에 주어진 레이블이 주어지지 않은 경우에, 데이터 간의 유사도를 판별하여 데이터를 그룹 별로 나누는 것을 말한다. K평균 알고리즘은 n개의 d차원 입력 데이터가 주어졌을 때, n개의 데이터를 k개의 집합으로 분할하여, 최종적으로는 각 그룹의 중심점-데이터 간의 거리의 제곱합의 최소화를 하는 알고리즘이다. 각 데이터 점 사이의 거리는 유클리드 거리를 사용한다.

 K 평균 알고리즘의 흐름은 다음과 같다.

1. 각 데이터와 클러스터의 중심 까지의 거리를 계산해 각 클러스터에 데이터를 할당한다
   
2. 각 클러스터의 무게중심을 재설정 한다
   
   
3. 클러스터의 변화가 존재하지 않을때까지 반복한다

 K평균 알고리즘은 초기에 클러스터의 무게중심을 설정하는 방법에 따라 성능이 바뀐다. 초기화 기법으로는 각 데이터를 임의의 클러스터에 할당하는 랜덤 파티션 기법과, 임의의 k개의 데이터 점을 초기 무게중심으로 설정하는 Forgy기법이 존재한다. 이번 코드에서는 Forgy기법을 이용하여 초기화 하도록 한다.

import math
import random

def Euclidean_Distance(p:list, q:list)->float:

    summation = 0

    if len(p) != len(q):
        raise ValueError

    for x,y in zip(p,q):
        summation += (x-y)**2

    return math.sqrt(summation)

def Allocate_Cluster(input_data:list, centroid:list)->int:

    distance_list = []

    for center in centroid:
        distance_list.append(Euclidean_Distance(input_data,center))

    return distance_list.index(min(distance_list))

def Update_centroid(cluster:list)->list:

    new_centroid = []
    m = 0

    for group in cluster:
        tmp = []
        if len(group) == 0:
            pass
        else:

            for x in range(len(group[0])):
                for i in range(len(group)):
                    m += group[i][x]
                tmp.append(m/len(group))

            new_centroid.append(tmp)

    return new_centroid

def k_nearest_clustering(k:int, input_data:list, option="Forgy"):
    clustered = False

    if option == "Forgy":
        centroid = random.sample(input_data,k)

        new_cluster = [[] for _ in centroid]

        while not clustered:
            cluster = [[] for _ in centroid]

            for data in input_data:
                cluster[Allocate_Cluster(data,centroid)].append(data)

            if cluster == new_cluster:
                return centroid
            else:
                new_cluster = cluster
                centroid = Update_centroid(cluster)