k-Means(二分k-均值算法）

在上一节中我们已经讲了k-均值算法，当时我们选取的质心是随机选取的，没有什么依据，所以聚类的结果很可能出现误差，为了降低这种误差的出现我们今天来研究一种优化的k-均值算法----二分k--均值算法，看到名称我们就能明白在每次划分的时候都是将数据划分成俩份，直到达到我们要求的聚类数。怎么来分？选取哪一堆数据来分？需要我们计算，这里我们引入一个叫做误差平方和的指标，这个指标越小就代表所分的数据越准确。在上一节中我们有一个矩阵来存储分类后的索引以及到质心的距离。把所有到质心的点的距离求和就是误差平方和，每次选取误差平方和最大的那堆数据进行划分。‘

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],:]
            centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas)
            sseSplit = sum(splitClustAss[:,1])
            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) 
        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]
        centList.append(bestNewCents[1,:].tolist()[0])
        clusterAssment[nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:]= bestClustAss
    return mat(centList), clusterAssment

这里输入数据同样是数据集和要聚类的个数以及距离计算函数。首先开始创建一个初始簇，接着for循环计算出距离。进入while循环直到划分出指定个簇。在for循环里尝试划分每一个簇，然后计算每个簇的误差值，以及剩余数据的误差值，如果这两个误差之和小于最小误差就将这个划分保存下来，并将这个误差作为最小误差。接着就是更新簇的分配结果，直到分配够指定的簇结束。