K 均值聚类

算法交替执行以下两个步骤：

• 将每个数据点分配给最近的簇中心
• 将每个簇中心设置为所分配的所有数据点的平均值，如果簇的分配不再发生改变，那么算法结束。

优点

• K 均值不仅相对容易理解和实现，而且运行速度也相对较快。
• K 均值可以轻松扩展到大型数据集
• scikit-learn 甚至在 MiniBatchKMeans 类中包含了一种更具可扩展性的变体，可以处理非常大的数据集。

缺点

• 需要人工预先确定初始 K 值，且该值和真实的数据未必吻合。
• 分类结果严重依赖于分类中心的初始化。通常进行多次k-means，然后选择最优的那次作为最终聚类结果。
• 结果不一定是全局最优的，只能保证局部最优。
• 对噪声敏感。因为簇的中心是取平均，因此聚类簇很远地方的噪音会导致簇的中心点偏移。
• 无法解决不规则形状的聚类。
• 无法处理离散特征，如：国籍、性别 等。

k-means 性质：

• k-means 实际上假设数据是呈现球形分布，实际任务中很少有这种情况。与之相比，GMM 使用更加一般的数据表示，即高斯分布。
• k-means 假设各个簇的先验概率相同，但是各个簇的数据量可能不均匀。
• k-means 使用欧式距离来衡量样本与各个簇的相似度。这种距离实际上假设数据的各个维度对于相似度的作用是相同的。
• k-means 中，各个样本点只属于与其相似度最高的那个簇，这实际上是硬 分簇。
• k-means 算法的迭代过程实际上等价于EM 算法。具体参考EM 算法章节。

3、算法调优

• 数据归一化和离群点处理
• 合理选择 K 值

K 值选择方法：

• 手肘法：是一个经验方法，缺点就是不能够自动化。
• Gap Statistic 方法：只需要找到最大的 Gap Statistic 所对应的 K 即可。Gap（K）可以视为随机样本的损失和实际样本的损失之差。
• 采用核函数：通过一个非线性映射，将输入空间中的数据点映射到高位的特征空间中，并在新的特征空间进行聚类。非线性映射增加了数据点线性可分的概率，从而在经典聚类算法失效的情况下，通过引入核函数可以达到更为准确的聚类结果。

4、算法改进

• K-means++：解决 k-means 严重依赖于分类中心初始化的问题
• k-modes：解决 k-means 无法处理离散特征的问题
• k-medoids：解决k-means 对噪声敏感的问题。
• mini-batch k-means：主要用于减少 k-means 的计算时间
• ISODATA：K值不确定可以使用
• 二分均值聚类：层次聚类

K-means++

它主要解决 k-means 严重依赖于分类中心初始化的问题。 已经选取了 n(0<n<k) 个初始聚类中心，距离当前 n 个聚类中心越远的点会有更高的概率被选为第 n+1 个聚类中心。在选取第一个聚类中心（n=1）时同样通过随机的方法。

image.png

k-modes

主要解决 k-means 无法处理离散特征的问题

image.png

k-medoids
主要解决k-means 对噪声敏感的问题。

image.png

mini-batch k-means
主要用于减少 k-means 的计算时间。mini-batch k-means 算法每次训练时随机抽取小批量的数据，然后用这个小批量数据训练。这种做法减少了 k-means 的收敛时间，其效果略差于标准算法。

image.png

二分均值聚类

• 一种用于度量聚类效果的指标是 SSE，SSE 值越小表示数据点越接近于它们的质心，聚类效果也越好。因为对误差取了平方，因此更加重视那些远离中心的点。
• 一种肯定可以降低 SSE值的方式是增加簇的个数，但违背了聚类的目标，聚类的目标是在保持簇数目不变的情况下提高簇的质量。
• 一种方法是将具有最大 SSE 值的簇分为两个簇。具体实现时可以将最大簇包含的点过滤出来并在这些点上运行 K-均值算法，其中 k 设为 2.

def biKmeans(dataSet,k,distMeas=distEclud):
    m=np.shape(dataSet)[0]
    clusterAssment=np.mat(np.zeros((m,2)))
    centroid0=np.mean(dataSet,axis=0).tolist()[0]
    centList=[centroid0]
    for j in range(m):
        clusterAssment[j,1]=distMeas(np.mat(centroid0),dataSet[j,:])**2
    while(len(centList)<k):
        lowestSSE=np.inf
        for i in range(len(centList)):
            ptsInCurrCluster=dataSet[np.nonzero(clusterAssment[:,0].A==i)[0],:]
            centroidMat,splistClusterAss=kMeans(ptsInCurrCluster,2,distMeas)
            sseSplist=np.sum(splistClusterAss[:,1])
            sseNotSplit=np.sum(clusterAssment[np.nonzero(clusterAssment[:,0].A!=i)[0],1])
            print('sseSplit, and notSplit:',sseSplist,sseNotSplit)
            if(sseSplist+sseNotSplit<lowestSSE):
                bestCentToSplit=i
                bestNewCents=centroidMat
                bestClustAss=splistClusterAss.copy()
                lowestSSE=sseSplist+sseNotSplit
        bestClustAss[np.nonzero(bestClustAss[:,0].A==1)[0],0]=len(centList)
        bestClustAss[np.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,:]
        centList.append(bestNewCents[1,:])
        clusterAssment[np.nonzero(clusterAssment[:,0].A==bestCentToSplit)[0],:]=bestClustAss
    return centList , clusterAssment

通过迭代方式寻找 K 个簇的一种划分方案，使得聚类结果对应的代价函数最小。

ISODATA

当 K 值的大小不确定时，可以使用 ISODATA 算法。
ISODATA 的全称是迭代自组织数据分析法。当属于某个类别的样本数过少，把该类别去除；当属于某个类别的样本数过多、分散度较大时，把该类分为两个子类别。在 K-means 基础上增加两个操作，一是分裂操作，对应着增加聚类中心数；二是合并操作，对应着减少聚类中心数。

超参数设定：

• 预期的聚类中心数目 K 。具体地，最终输出的聚类中心数目常见范围是 K 的一半或两倍 K。
• 每个类别要求的最少样本数目 N。如果分裂后会导致某个子类别所包含样本数目小于该阈值，就不会对该类别进行分裂操作
• 最大方差 Sigma。用于控制某个类别中样本的分散程度。当样本分散程度超过这个阈值，且分裂后满足上条规则，进行分裂操作。
• 两个聚类中心之间所允许最小距离 D。如果两个类靠的非常近，小于该阈值时，则对这两个类进行合并操作。

算法实现

from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans

X,y=make_blobs(random_state=1)

kmeans=KMeans(n_clusters=3)
kmeans.fit(X)
print('Cluster memberships:\n{}'.format(kmeans.labels_))
# 预测
print(kmeans.predict(X))
# 质心
print(kmeans.cluster_centers_)