Machine Learning in Action ch.10.2 & 10.3 k-mean clustering

10.2 후처리로 군집 성능 개선하기

후처리를 통해 사용자가 정의한 k에 의해 생기는 오류들을 줄일 수 있다.

위 플롯은 3개의 군집을 가진 데이터 집합으로 k-means 를 수행한 결과이다.

결과는 처참하다.

그 이유는 k-means가 전체 최소점이 아닌 지역 최소점에 수렴했기 때문이다.

할당된 군집의 질을 측정하는 데 사용되는 방법으로 SSE(제곱 오류의 합)가 있다.

이 문제를 해결하기 위해 후처리를 사용한다.

즉, SSE가 가장 높은 군집을 두 개의 군집으로 분할하는 것이다.

10.3 양분하는  k-means 

지역 최소점에 수렴하여 오류를 발생시키는 문제점을 극복하기 위해 양분하는 k-means가 개발되었다.

이것은 하나의 군집을 두 개로 분할한다. 

그리고 분할된 군집을 선택한다.

 그 군집은 SSE가 최소일 때 결정된다.

def biKmeans(dataSet, k, distMeas=distEclud):
    m = shape(dataSet)[0]
    clusterAssment = mat(zeros((m,2)))
    centroid0 = mean(dataSet, axis=0).tolist()[0]
    centList =[centroid0] #create a list with one centroid
    for j in range(m):#calc initial Error
        clusterAssment[j,1] = distMeas(mat(centroid0), dataSet[j,:])**2
    while (len(centList) < k):
        lowestSSE = inf
        for i in range(len(centList)):
            ptsInCurrCluster = dataSet[nonzero(clusterAssment[:,0].A==i)[0],:]#get the data points currently in cluster i
            centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas)
            sseSplit = sum(splitClustAss[:,1])#compare the SSE to the currrent minimum
            sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1])
            print "sseSplit, and notSplit: ",sseSplit,sseNotSplit
            if (sseSplit + sseNotSplit) < lowestSSE:
                bestCentToSplit = i
                bestNewCents = centroidMat
                bestClustAss = splitClustAss.copy()
                lowestSSE = sseSplit + sseNotSplit
        bestClustAss[nonzero(bestClustAss[:,0].A == 1)[0],0] = len(centList) #change 1 to 3,4, or whatever
        bestClustAss[nonzero(bestClustAss[:,0].A == 0)[0],0] = bestCentToSplit
        print 'the bestCentToSplit is: ',bestCentToSplit
        print 'the len of bestClustAss is: ', len(bestClustAss)
        centList[bestCentToSplit] = bestNewCents[0,:].tolist()[0]#replace a centroid with two best centroids
        centList.append(bestNewCents[1,:].tolist()[0])
        clusterAssment[nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:]= bestClustAss#reassign new clusters, and SSE
    return mat(centList), clusterAssment

처음에 데이터 집합의 중심을 계산하고 모든 중심을 저장할 하나의 리스트를 생성한다. 

이제 모든 점들을 순회하면서 각 점과 중심 간의 오류를 계산한다.

이제 반복문을 돌면서 군집을 분할한다.

약간 세포분열 느낌이다.

분할할 때 SSE를 비교하면서 분할하므로 더 정교하고 정확한 군집화를 할 것이다.

양분하는 k-means 를 사용하면 위와 같은 정교한 군집화를 볼 수 있을 것이다.

이러한 군집 할당은 항상 좋은 군집들을 생성해 낸다.