Machine Learning in Action ch.10.1 k-mean clustering

clustering 은 군집화로서 비지도 학습의 한 유형이다.

비지도 학습은 목적 변수가 없어서 무엇을 찾아야 하는지 알지 못하는 경우에 사용한다.

군집화는 유사성을 띄는 데이터끼리 군집을 이루어 분류된다.

그래서 때로는 군집화를 비지도 분류라고도 한다.

분류와 차이점은 미리 정해놓은 분류 항목이 없다는 것이다.

군집화에는 여러 가지 종류가 존재한다.

많이 있지만 주로 사용되는 종류는 3가지이다.

1. k-means

2. bisecting k-means

3. hierarchical clustering

군집화에도 몇 가지 문제점이 존재하는데 이 문제점들은 후처리(postprocessing)을 통해 해결할 것이다.

10.1 k-means clustering 알고리즘

k-means 는 간단히 말하면 주어진 데이터 집합 안에서 사용자가 정의한 k개의 군집을 찾고자하는 알고리즘이다.

http://youtu.be/IuRb3y8qKX4

위의 링크는 유튜브인데  k-means에 대해 설명을 잘 했다.

def distEclud(vecA, vecB):
    return sqrt(sum(power(vecA - vecB, 2))) #la.norm(vecA-vecB)

def randCent(dataSet, k):
    n = shape(dataSet)[1]
    centroids = mat(zeros((k,n)))#create centroid mat
    for j in range(n):#create random cluster centers, within bounds of each dimension
        minJ = min(dataSet[:,j])
        rangeJ = float(max(dataSet[:,j]) - minJ)
        centroids[:,j] = mat(minJ + rangeJ * random.rand(k,1))
    return centroids

첫번째 함수는 유클리드 거리를 계산하는 함수이다.

두번째 함수는 k개의 중심을 원소로 하는 하나의 집합을 생성하는 함수이다.

위 함수들은 계산을 도와주는 함수들이었고 이제 k-means 함수를 보자.

def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
    m = shape(dataSet)[0]
    clusterAssment = mat(zeros((m,2)))#create mat to assign data points
                                      #to a centroid, also holds SE of each point
    centroids = createCent(dataSet, k)
    clusterChanged = True
    while clusterChanged:
        clusterChanged = False
        for i in range(m):#for each data point assign it to the closest centroid
            minDist = inf; minIndex = -1
            for j in range(k):
                distJI = distMeas(centroids[j,:],dataSet[i,:])
                if distJI < minDist:
                    minDist = distJI; minIndex = j
            if clusterAssment[i,0] != minIndex: clusterChanged = True
            clusterAssment[i,:] = minIndex,minDist**2
        print centroids
        for cent in range(k):#recalculate centroids
            ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]#get all the point in this cluster
            centroids[cent,:] = mean(ptsInClust, axis=0) #assign centroid to mean
    return centroids, clusterAssment

이 알고리즘은 k 개의 중심을 생성하고 각 점을 가까운 중심에 할당한다.

그런 다음 중심을 다시 계산한다. 이러한 과정은 점들에 의해 군집들의 변화가 멈출 때까지 되풀이된다.