K-均值聚类算法(K-Means)

算法思路

算法目的

对于样本集$D=\lbrace x_1,x_2,x_3....x_n\rbrace$，"k均值"算法就是针对聚类划分$C=\lbrace C_1,C_2,C_3....C_k\rbrace$最小化平方误差
$$
E=\sum_{i=1}^{k}\sum_{x\in C_i}\left | x_i-u_i\right |^2
$$
其中
$$
u_i=\frac{1}{|C_i|}\sum_{x\in C_i}x
$$
是簇$C_i$的均值向量。从上述公式中可以看出，该公式刻画了簇内样本围绕簇均值向量的紧密程度，$E$值越小簇内样本的相似度越高。

算法核心

K-means聚类算法是一种迭代求解的聚类分析算法，其步骤是随机选取K个对象作为初始的聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本，聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有（或最小数目）对象被重新分配给不同的聚类，没有（或最小数目）聚类中心再发生变化，误差平方和局部最小。

算法流程(自然语言)

创建k个点作为起始质心（通常随机选择）
当任意一个点的簇分配结果发生改变时：
        对数据集中的每个点：
                对每个质心：
                计算质心与数据点之间的距离
         将数据点分配到距离其最近的簇
对每一个簇，计算簇中所有点的均值并将均值作为质心

优缺点

优点：

1. 原理比较简单，实现也是很容易，收敛速度快
2. 当结果簇是密集的，而簇与簇之间区别明显时, 它的效果较好
3. 主要需要调参的参数仅仅是簇数k

缺点：

1. K值需要预先给定，很多情况下K值的估计是非常困难的
2. K-Means算法对初始选取的质心点是敏感的，不同的随机种子点得到的聚类结果完全不同 ，对结果影响很大
3. 对噪音和异常点比较的敏感。用来检测异常值
4. 采用迭代方法，可能只能得到局部的最优解，而无法得到全局的最优解

算法优化-二分K-均值算法

算法核心

二分K-Means算法首先将所有点作为一个簇，然后将该簇一分为二。之后选择其中一个簇继续进行划分，选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SSE的值。上述基于SSE的划分过程不断重复，直到得到用户指定的簇数目为止。

算法流程

将所有点看成一个簇
   当簇数目小于k时
        对于每一个簇：
            计算总误差
            在给定的簇上面进行K-均值聚类（k=2）
    计算将该簇一分为二后的总误差
    选择使得误差最小的那个簇进行划分操作

优点

1. 二分K均值算法可以加速K-means算法的执行速度，因为它的相似度计算少了
2. 克服K-means收敛于局部最小，但是不能保证每次都是全局最优，因为在簇一分为二的时候也存在了随机初始点的情况，所以只能保证是比K-Means算法更优

代码

import numpy as np
import matplotlib.pyplot as plt


def loaddata(filename):
    data = []
    with open(filename) as fr:
        while True:
            line = fr.readline()
            if line:
                linearr = line.strip().split()
                mask_x = [float(x) for x in linearr]
                data.append(mask_x)
            else:
                break
                pass
    return data


def disteclud(mata, matb):
    return np.sqrt(np.sum(np.power(mata - matb, 2)))


def randcent(datamat, k):
    n = np.shape(datamat)[1]
    centroids = np.mat(np.zeros((k, n)))
    for j in range(n):
        minj = np.min(datamat[:, j])
        maxj = np.max(datamat[:, j])
        centroids[:, j] = np.random.uniform(minj, maxj, (k, 1))
    return centroids


def kmeans(dataset, k, distmeas=disteclud, creatcent=randcent):
    m = np.shape(dataset)[0]
    clusterassment = np.mat(np.zeros((m, 2)))
    centroids = creatcent(dataset, k)
    clusterchanged = True
    while clusterchanged:
        clusterchanged = False
        for i in range(m):
            mindist = float('inf')
            minindex = -1
            for j in range(k):
                distj = distmeas(centroids[j, :], dataset[i, :])
                if distj < mindist:
                    mindist = distj
                    minindex = j
            if clusterassment[i, 0] != minindex:
                clusterchanged = True
            clusterassment[i, :] = minindex, mindist ** 2
        for cent in range(k):
            ptsinclust = dataset[np.nonzero(clusterassment[:, 0].A == cent)[0]]
            centroids[cent, :] = np.mean(ptsinclust, axis=0)
    return centroids, clusterassment


def bikmeans(dataset, k, distmeas=disteclud):
    m,n = np.shape(dataset)
    clusterassment = np.mat(np.zeros((m, 2)))
    centroid0 = np.mean(dataset, axis=0).tolist()[0]
    cenlist = [centroid0]
    for j in range(m):
        clusterassment[j, 1] = distmeas(np.mat(centroid0), dataset[j:]) ** 2
    while len(cenlist) < k:
        lowestsee = float('inf')
        for i in range(len(cenlist)):
            ptsincurrcluster = dataset[np.nonzero(clusterassment[:, 0].A == i)[0]]
            centroidmat, split = kmeans(ptsincurrcluster, 2, distmeas)
            ssesplit = np.sum(split[:, 1])
            ssenosplit = np.sum(dataset[np.nonzero(clusterassment[:, 0].A != i)[0], 1])
            if (ssesplit + ssenosplit) < lowestsee:
                bestcenttosplit = i
                bestcentroidmat = centroidmat
                bestclustass = split.copy()
                lowestsee = ssesplit + ssenosplit
        bestclustass[np.nonzero(bestclustass[:, 0].A == 1)[0], 0] = len(cenlist)
        bestclustass[np.nonzero(bestclustass[:, 0].A == 0)[0], 0] = bestcenttosplit
        cenlist[bestcenttosplit] = bestcentroidmat[0, :].tolist()[0]
        cenlist.append((bestcentroidmat[1, :]).tolist()[0])
        clusterassment[np.nonzero(clusterassment[:, 0].A == bestcenttosplit)[0], :] = bestclustass
    return np.mat(cenlist), clusterassment


def plotDataSet(centroids, clusterassment, data, k):
    colorValue = ['y', 'g', 'b', 'm']
    markers = []
    xcentroids = centroids[:, 0].tolist()
    ycentroids = centroids[:, 1].tolist()
    n = len(data)
    x = [[] for i in range(k)]
    y = [[] for i in range(k)]
    for j in range(n):
        y[int(clusterassment[j, :].tolist()[0][0])].append(data[j][1])
        x[int(clusterassment[j, :].tolist()[0][0])].append(data[j][0])
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.scatter(xcentroids, ycentroids, marker="s", s=20, c='red')
    for i in range(k):
        ax.scatter(x[i], y[i], s=20, c=colorValue[i % 4])
    plt.title('DataSet')
    plt.xlabel('X')
    plt.show()


if __name__ == "__main__":
    data = loaddata('testSet2.txt')
    datamat = np.mat(data)
    centroids, clusterassment = bikmeans(datamat, 3)
    plotDataSet(centroids, clusterassment, data, 3)

总结

K-Means比较简单，篇幅也比较小，下一个应该是跟数据挖掘有关的Apriori算法(著名的例子就是纸尿裤和啤酒放一起卖得更好),继续加油