k-means 알고리즘 [파이썬]

알고리즘

가장 간단한 지도학습 분류(classification) 알고리즘이 kNN(k-Nearest Neighbor)이라면, 가장 간단한 비지도학습 군집(clustering) 알고리즘은 k-means 클러스터링을 꼽을 수 있다.

비지도학습이기 때문에 k-means 클러스터링은 레이블이 없는 데이터들만으로도 작동한다.

 

k-means 클러스터링은 데이터를 k개의 클러스터(cluster)로 분류해주는데, 다음과 같은 알고리즘으로 작동한다. 

 

1) 사용자로부터 입력받은 k의 값에 따라, 임의로 클러스터 중심(centroid) k개를 설정해준다.

2) k개의 클러스터 중심으로부터 모든 데이터가 얼마나 떨어져 있는지 계산한 후에, 가장 가까운 클러스터 중심을 각 데이터의 클러스터로 정해준다.  

3) 각 클러스터에 속하는 데이터들의 평균을 계산함으로 클러스터 중심을 옮겨준다.  

4) 보정된 클러스터 중심을 기준으로 2, 3단계를 반복한다.

5) 더이상 클러스터 중심이 이동하지 않으면 알고리즘을 종료한다. 

 

소스 코드

import math
import random

class kmeans():
    def __init__(self, k):
        self.table=[[1,1],[2,1],[1,2],[5,5],[6,5],[5,6],[7,7]]  #입력 데이터
        self.k=k
    def RandomCentroid(self): #첫 임의의 중심점 설정
        temp = set()
        for i in self.table:
            for j in i:
                temp.add(j)
        nomal=list(temp) # 중복을 제거한 리스트 생성
        cenrtoid = []
        for i in range(self.k):
            m = []
            for j in range(2): #(x,y) 좌표값
                m.append(random.randrange(min(nomal), max(nomal))) # 범위 내 랜덤 좌표 
            cenrtoid.append(m)
        print("회전 = 0")
        for i in range(len(cenrtoid)): 
            print("k = {}번째 집단의 중점 \t {}".format(i, cenrtoid[i]))
        return cenrtoid # 첫 중점 반환
    
    def findNearestCentroid(self, cenrtoid, tb): #근처 중심점 찾기
        d=[]
        for i in cenrtoid:
            total = 0
            for j in range(2): # x, y  유클라디안 거리 계산
                total += pow(tb[j]-i[j],2)
            d.append(math.sqrt(total)) 
        idx = d.index(min(d)) # 클러스터에서 최소값에 속한 인덱스 추가
        return idx
        
    def create_cluster(self, cenrtoid): # 클러스터 분류
        cluster = [[],[]]
        for i in range(len(self.table)):
            idx = self.findNearestCentroid(cenrtoid, self.table[i]) # 근처 클러스터에 속한 좌표 반환
            cluster[idx].append(i) # 해당 클러스터에 속한 좌표 추가
        return cluster  # 클러스터 반환
    
    def setpoint(self, cluster): # 새로운 중점 찾기
        total = [[],[]] # 새로운 중점
        avg = [[],[]] # 평균 좌표
        for i in range(self.k): # k번
            x=0
            y=0
            for j in cluster[i]: # 각 클러스터에 속한 x ,y값 합치기
                x += self.table[j][0]
                y += self.table[j][1]
            total[i].append(x)
            total[i].append(y)
        
        for i in range(self.k): #k번만큼 새로운 중점 갱신
            for j in range(2): # x,y
                try:  # 한 집단만 있을 경우 error 발생
                    avg[i].append(round(total[i][j]/len(cluster[i]),2)) 
                except Exception as e: #중점이 0,0 으로 수렴하는 경우
                    return False  # error 발생 시 False 리턴해서 다시 new_mid_point() 호출
        return avg
            
if __name__=='__main__':
    aaaaaa = kmeans(2)
    mid_point=aaaaaa.RandomCentroid() #  첫 중점
    cnt = 0
    temp =[] #기존 중점 저장
    while(temp != mid_point):
        cnt+=1
        temp = mid_point
        new_cs = aaaaaa.create_cluster(mid_point) # 클러스터 갱신
        aaaaaa.table[i]
        
        for i in range(len(new_cs)): # 클러스터 집단 출력
            print('k = {} 집단 :'.format(i) , end='')
            for j in range(len(new_cs[i])):
                print(aaaaaa.table[new_cs[i][j]], end='')
            print("")
        
            
        mid_point = aaaaaa.setpoint(new_cs) # 새로운 중점 구하기
        if mid_point == False: # 중점이 한곳에 몰릴경우
            mid_point=aaaaaa.RandomCentroid()
        print("\n회전 = {}".format(cnt))   # 새로 생성된 중점과 클러스터 출력 
        for i in range(len(mid_point)): 
            print("k = {}번째 집단의 중점 \t {}".format(i, mid_point[i]))
    print("중점의 변화 없음!!")

결과 화면

참고 사이트

https://sogogi1000inbun.tistory.com/95