K 평균 군집화 알고리즘은 데이터분석에서 가장 주요하고 기초적으로 쓰이는 알고리즘으로, 점처럼 모여서 떨어진 모양의 데이터를 분류할때 요긴합니다.

https://github.com/ahrism10M501/eon_assignment/tree/main/week_1

정해진 클러스터 수로 무작위 데이터를 지정한다음 각 클러스터와 특정 데이터 사이의 거리를 계산해 가장 가까운 순서대로 군집화 합니다

코드 설명

class Distance:
    @staticmethod
    def euclidean(p1, p2):
        # (p1 - p2).shape (1500, 3, 2)
        # print(np.sqrt(np.sum((p1 - p2)**2, axis=2)).shape) # 1500, 3
        # print(np.sqrt(np.sum((p1 - p2)**2, axis=2))[:5]) # dim=1에 각 k에 대한 거리 결과 들어감
        return np.sqrt(np.sum((p1 - p2)**2, axis=2))
    
    @staticmethod
    def manhattan(p1, p2):
        return np.sum(np.abs(p1-p2), axis=2)
    
    @staticmethod    
    def cosine(p1, p2):
        return np.dot(p1, p2) / np.linalg.norm(p1)*np.linalg.norm(p2)

k_means를 진행하면서 각 점과 점 사이의 거리를 측정하기 위한 거리 함수를 정의했습니다.

클래스를 따로 만든 이유는 다양한 거리 공식으로 k_means를 수행해보기 위함 입니다. p1과 p2는 문자 그대로 이뤄지되 인자로 입력되는 두 매트릭스 형식이 넘파이 브로드캐스팅 기능을 수행 할 수 있어야만 합니다.

k-means의 경우 수행을 위해서 1대 다수를 비교해야 하므로 고민이 있었습니다.

distance = dist_fn(ds[:, np. newaxis, :], cent[np.newaxis, :, :])

거리를 구하는 두 행렬입니다. ds는 (1500, 2) 의 차원을 가지는 점들의 행렬로 1500개의 점이 (x, y) 값으로 연결되어 있습니다. 만약 3차원이라면 (1500,3)으로 1500개의 점이 (x, y, z)로 묶일겁니다.

cent 는 데이터셋 내부에서 랜덤으로 뽑은 k개의 점입니다. 이 점을 기준으로 각 포인트 사이의 거리를 비교하고, 군집화하고, 새로운 centroid를 정합니다.

rand_idx = np.random.choice(ds.shape[0], k)
centroid = ds[rand_idx, :] # cent - (3, 2)

저는 k-means 함수를 인터페이스로 실질적인 계산은 _calc_distances에서 진행했습니다

def _calc_distances(ds, cent, dist_fn, k, threshold):
    while True:
        # 중앙값(cent)와 포인트 간의 거리 구하기
        # 브로드 캐스팅 이용! -> 제대로 이해하기
        distance = dist_fn(ds[:, np. newaxis, :], cent[np.newaxis, :, :])
        # (1500, 1, 2) <> (1, 3, 2) => (1500, 3) 왜냐하면 한번 3차원에 대해 덧셈 수행 혹은 dot product
        # 그러고 보니, 이 함수를 지나고서도 왜 1500, 2 쉐잎이지?
        
        # 제일 작은 값들의 인덱스 찾아주고, 새로운 k를 위한 공간 만들기
        k_label = np.argmin(distance, axis=1)
        # print(k_label.shape)
        # print(k_label[:10])
        new_cent = np.zeros_like(cent)
        
        # 각 k 군집에 따른 평균 구하기 -> 새로운 센터
        for i in range(k):
            new_cent[i] = np.mean(ds[k_label==i], axis = 0)
            
        # 수렴
        if np.all(np.abs(new_cent - cent) < threshold):
            break
        cent = new_cent
        
    return (ds, k_label, cent)

들어온 두 행렬은 브로드캐스팅을 위해 np.newaxis로 새로운 차원을 만든다. 이를 통해 우리 똑똑한 넘파이가 x,y 가 담긴 차원의 각 거리를 구해준다.

k_label은 구한 거리 중에서 제일 작은 값의 위치(인덱스)을 찾는다. 이건 각 포인트를 군집에 넣어주기 위함이다. distance를 구할 때 ds.shape = (1500, 2), cent.shape = (3, 2) 이다. 이를 (1500, 1, 2)[n_samples, newaxis, point] 과 (1, 3, 2)[newaxis, num_k, point] 로 만들어 연산을 진행한다.

각 1500개 점들에 3 포인트와의 거리가 저장된다. 즉 (1500, 3, 2) 로 저장되며 여기서 3이 각 센터와의 거리를 표시한것.

이 세 차원에서 각 차원 중 가장 작은 값의 위치를 찾고, 이를 라벨링 함과 동시에, 그 평균을 구해 센터를 업데이트 한다. 이때 라벨은 0, 1, 2, …, num_k의 유니크한(고유한) 값을 가진다.

이를 여러 반복해 이전 센터와 갱신된 센터의 차이가 threshold 이하라면 (센터가 거의 움직이지 않는다면) 분류를 마무리한다.