k - mean 알고리즘 구현

k-means 알고리즘 작업 과정 설명 은 다음 과 같다.  초기 화: 집합 수 k, 초기 집합 중심 x, 교체 횟수 또는 수렴 조건.  우선 n 개 데이터 대상 에서 임의로 선택 k 개 대상 을 초기 집합 중심 으로 하기;나머지 대상 에 대해 서 는 이러한 집합 중심 과 의 싱크로 율 (거리) 에 따라 가장 비슷 한 (집합 중심 이 대표 하 는) 집합 에 배분 한다.  그 다음 에 모든 새로운 집합 중심 (이 집합 에서 모든 대상 의 평균 값) 을 계산한다.  또한 수렴 조건 이나 교체 횟수 를 만족 시 킬 때 까지 위의 과정 을 반복 한다.  목표: 각 집합 자체 가 가능 한 한 치밀 하고 각 집합 간 에 가능 한 한 분리 합 니 다.
#################################################

import random
import time

t1 = time.time()

dataset = []
with open('iries.txt', 'r') as f:
    for line in f:
        ds = tuple([ float(x) for x in line.split() ])
        dataset.append(ds)

#for x in  dataset:
#    print x[0], x[1], x[2], x[3]
#


def distance(x, y):
    z = 0
    for i in range(4):
        z = z + pow((x[i] - y[i]), 2)

    return pow(z, 0.5)

#print distance(dataset[1], dataset[2])

def get_means(ds):
    a = b = c = d = 0.0
    l = len(ds)
    for x in ds:
        a += x[0]
        b += x[1]
        c += x[2]
        d += x[3]

    return (a/l, b/l, c/l , d/l)

def gettotaldistance(clusters):
    '''
    [[(1,2,3,4), [(2,3,4,5),(3,4,5,6)...]], [(6,7,8,9),[...]],...]
    '''
    sum = 0
    for cluster in clusters:
        for point in cluster[1]:
            sum += distance(cluster[0], point)
    return sum

def push_into_cluster(clusters, point):
    c = 0
    d = distance(clusters[0][0], point)
    for x in range(1, len(clusters)):
        temp = distance(clusters[x][0], point)
        if temp < d:
            d = temp
            c = x

    clusters[c][1].append(point)

def kmeans(k = 3):
    rn_center = random.sample(dataset, k)
    clusters = []
    for x in rn_center:
        clusters.append([x, []])
    print clusters
 

    oldtotal = 999999999

    while True:
        for point in dataset:
            push_into_cluster(clusters, point)

        for cluster in clusters:
            cluster[0] = get_means(cluster[1])

        newtotal = gettotaldistance(clusters)
        if oldtotal - newtotal > 1:
            oldtotal = newtotal
            for cluster in clusters:
                cluster[1] = []
        else:
            print '============================'
            for x in clusters:
                print '-------------------------'
                print x[0]
            break


kmeans(k = 5)

print time.time() - t1

그 중에서 iries. txt 는 http://www.codeforge.cn/read/186226/irises.txt__html
다음은 pprocess 모듈 을 사용 하여 병렬 계산 한 k - maeans 알고리즘 입 니 다. 그러나 그다지 좋 지 않 습 니 다. 조금 만 병렬 계산 을 사 용 했 습 니 다. 병렬 계산 에 익숙 하지 않 습 니 다.

import random
import time
import pprocess

t1 = time.time()

limit = 2 #core num
dataset = []
with open('iries.txt', 'r') as f:
    for line in f:
        ds = tuple([ float(x) for x in line.split() ])
        dataset.append(ds)

#for x in  dataset:
#    print x[0], x[1], x[2], x[3]
#


def distance(x, y):
    z = 0
    for i in range(4):
        z = z + pow((x[i] - y[i]), 2)

    return pow(z, 0.5)

#print distance(dataset[1], dataset[2])

def get_means(ds):
    a = b = c = d = 0.0
    l = len(ds)
    for x in ds:
        a += x[0]
        b += x[1]
        c += x[2]
        d += x[3]

    return (a/l, b/l, c/l , d/l)

def gettotaldistance(clusters):
    '''
    [[(1,2,3,4), [(2,3,4,5),(3,4,5,6)...]], [(6,7,8,9),[...]],...]
    '''
    td = 0
    results = pprocess.Map(limit = limit)
    calc = results.manage(pprocess.MakeParallel(distance))

    for cluster in clusters:
        for point in cluster[1]:
            calc(cluster[0], point)

    
    td = sum(results)
    print '------------------', results, td
    return td

def push_into_cluster(clusters, point):
    
    #results = pprocess.pmap(lambda x: distance(x, point), [ y[0] for y in clusters], limit = limit)
    #print '#########', results
    #minvalue = min(results)
    #print minvalue

    c = 0
    d = distance(clusters[0][0], point)
    for x in range(1, len(clusters)):
        temp = distance(clusters[x][0], point)
        if temp < d:
            d = temp
            c = x

    clusters[c][1].append(point)

def kmeans(k = 3, eps = 1):
    rn_center = random.sample(dataset, k)
    clusters = []
    for x in rn_center:
        clusters.append([x, []])
    print clusters
 

    oldtotal = 999999999

    while True:
        for point in dataset:
            push_into_cluster(clusters, point)

        for cluster in clusters:
            cluster[0] = get_means(cluster[1])

        newtotal = gettotaldistance(clusters)
        if oldtotal - newtotal > eps:
            oldtotal = newtotal
            for cluster in clusters:
                cluster[1] = []
        else:
            print '============================'
            for x in clusters:
                print '-------------------------'
                print x[0]
            break


kmeans(k = 5, eps = 0.5)

print time.time() - t1