0x01 K-Means

聚类分析试图将相似对象归入同一簇,将不相似对象归到不同簇

K-Means是发现给定数据集的k个簇的算法。簇个数k是用户给定的,每一个簇通过其质心,即簇中所有点的中心来描述

优点:

  • 容易实现

缺点:

  • 可能收敛到局部最小值,在大规模数据集上收敛较慢

适用数据类型:

  • 数值型数据

步骤:

  • 随机确定k个初始点作为质心
  • 将数据集中的每个点分配到一个簇中

可使用任意距离度量方法,性能会受度量方法不同影响

0x02 算法实现

  • 计算距离
def distEclud(vecA, vecB):
    '''
    计算两个向量的欧式距离
    :param vecA:
    :param vecB:
    :return:
    '''
    return sqrt(sum(power(vecA - vecB, 2)))
  • 构建随机质心集合
def randCent(dataSet, k):
    '''
    构建K个随机质心的集合
    :param dataSet: 
    :param k: 
    :return: 
    '''
    n = shape(dataSet)[1]
    centroids = mat(zeros((k,n)))
    for j in range(n):
        minJ = min(dataSet[:,j]) 
        rangeJ = float(max(dataSet[:,j]) - minJ)
        centroids[:, j] = mat(minJ + rangeJ * random.rand(k,1))
    return centroids
  • K-Means算法
def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
    '''
    :param dataSet: 数据集
    :param k: 簇个数
    :param distMeas: 计算距离的函数
    :param createCent: 创建初始质心的函数
    :return:
    '''
    m = shape(dataSet)[0]
    clusterAssment = mat(zeros((m, 2))) #一列存储簇索引值, 一列存储误差
    centroids = createCent(dataSet, k)
    clusterChanged = True
    while clusterChanged:
        clusterChanged = False
        for i in range(m):
            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):
            ptsInClust = dataSet[nonzero(clusterAssment[:, 0].A==cent)[0]]
            centroids[cent, :] = mean(ptsInClust, axis=0)
    return centroids, clusterAssment

  • Bisecting K-Means

解决K-均值算法收敛于局部最小值的问题

  • 首先将所有点作为一个簇,然后将该簇一分为二
  • 选择其中一个簇继续进行划分,选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SSE的值

SSE:用于度量聚类效果的指标

def biKmeans(dataSet, k, distMeas=distEclud):
    '''

    :param dataSet:
    :param k:
    :param distMeas:
    :return:
    '''
    m = shape(dataSet)[0]
    clusterAssment = mat(zeros((m, 2)))
    centroid0 = mean(dataSet, axis=0).tolist()[0] #创建一个初始簇
    centList = [centroid0]
    for j in range(m): #计算每个点到质心的误差
        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

0x03 实例1

pass


参考

[1] https://www.manning.com/books/machine-learning-in-action