K-means 구현 과제

1 개요[ | ]

K-means 구현 과제

임의의 점 100개를 3차원 평면에 배치
K값 설정 (클러스터 수)
100개의 점 중에서 K개의 점을 임의로 선택함(K집합). K=3
[1] 선택되지 않은 점들은 K집합의 점들 중 가장 가까운 점 선택

즉, k개의 클러스터 구성됨

[2] 구성된 클러스터 내 점들로 평균을 구해서 가장 적합한 대표점 찾음(K집합 재구성)
[1]~[2] 과정을 10번 반복하며, 각 클러스터 대표점과 클러스터 내의 점들간 거리의 합을 출력

2 구현 예시[ | ]

import random
import numpy as np

######## settings
sample_size = 100
K = 3
iteration = 10

######## functions
def manhattan_distance(point1, point2):
    x1, y1, z1 = point1
    x2, y2, z2 = point2
    distance = abs(x1 - x2) + abs(y1 - y2) + abs(z1 - z2)
    return distance

def find_nearest_group_index(point, key_points):
    min_distance = 99999
    nearest_group = -1
    for idx, key_point in enumerate(key_points):
        distance = manhattan_distance(point, key_point)
        #print('distance between', point, key_point)
        #print('distance=', distance)
        if distance < min_distance:
            min_distance = distance
            nearest_group = idx
    return nearest_group

def find_nearest_point( point, points, exceptional_points=[] ):
    min_distance = 99999
    nearest_point = None
    for idx, point in enumerate(points):

        distance = manhattan_distance(point, mean_point)

        # except self
        if distance == 0:
            continue

        # except duplicate with exceptional_points
        duplicate = False
        for exceptional_point in exceptional_points :
            if( np.array_equal(point, exceptional_point)):
                duplicate = True
        if duplicate:
            continue

        # is that min?
        if distance < min_distance:
            min_distance = distance
            nearest_point = point
    #print( 'point=', point )
    #print( 'nearest_point=', nearest_point )
    return nearest_point


######## main program

#### init part

# generate 100 points
points = np.random.randint(sample_size, size=(sample_size, K))
#print( points )

# init - select random K key_points
idx = random.sample(range(sample_size), K)
key_points = points[idx,:]
#print( np.array(key_points) )


#### iteration part

for i in range(iteration):
    # [1] find nearest group and grouping
    groups = [[],[],[]]
    for point in points:
        group_index = find_nearest_group_index( point, key_points )
        #print( 'group_index=', group_index )
        groups[group_index].append( point )


    # [2-1] get mean_points
    mean_points = []
    for group in groups:
        np_group = np.array(group)
        #print( np_group )
        mean_points.append( np_group.mean(axis=0) )
    #print( mean_points )


    # [2-2] find new key_points
    key_points = []
    for mean_point in mean_points:
        key_points.append( find_nearest_point( mean_point, points, key_points ) )

    print( 'iteration=', i, 'key_points=', key_points)

'''
iteration= 0 key_points= [array([81, 86, 47]), array([36, 64, 61]), array([77, 23, 48])]
iteration= 1 key_points= [array([85, 77, 53]), array([36, 64, 61]), array([77, 23, 48])]
iteration= 2 key_points= [array([85, 77, 53]), array([26, 67, 53]), array([57, 13, 63])]
iteration= 3 key_points= [array([85, 77, 53]), array([26, 67, 53]), array([57, 13, 63])]
iteration= 4 key_points= [array([85, 77, 53]), array([26, 67, 53]), array([57, 13, 63])]
iteration= 5 key_points= [array([85, 77, 53]), array([26, 67, 53]), array([57, 13, 63])]
iteration= 6 key_points= [array([85, 77, 53]), array([26, 67, 53]), array([57, 13, 63])]
iteration= 7 key_points= [array([85, 77, 53]), array([26, 67, 53]), array([57, 13, 63])]
iteration= 8 key_points= [array([85, 77, 53]), array([26, 67, 53]), array([57, 13, 63])]
iteration= 9 key_points= [array([85, 77, 53]), array([26, 67, 53]), array([57, 13, 63])]
'''

3 같이 보기[ | ]