利用K-均值聚类算法对未标注数据分组（一）

概述

• 优点：容易实现
• 缺点：可能收敛到局部最小值，在大规模数据集上收敛较慢
• 适用数据类型：数值型数据

聚类是一种无监督学习，将相似的对象归到一个簇中。K-均值（K-means）聚类算法，可以发现k个不同的簇，且每个簇的中心采用簇中所含值的均值计算而成。

K-means聚类算法实现

K-均值是发现给定数据集的k个簇的算法，k由用户给定。

K-means算法工作流程：

1. 随机选定k个初始点作为质心（即簇中所有点的中心）
2. 为数据集中每个点找到距其最近的质心，并将其分配到该质心所对应的簇
3. 每个簇的质心更新为该簇所有点的平均值

伪代码如下：

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

代码实现：

import numpy as np

# 加载数据集
def loadDataSet(fileName):
    dataMat = []
    fr = open(fileName)
    for line in fr.readlines():
        curLine = line.strip().split('\t')
        fltLine = list(map(float, curLine))
        dataMat.append(fltLine)
    return dataMat

# 计算两个向量的欧式距离
def distEclud(vecA, vecB):
    return np.sqrt(np.sum(np.power(vecA - vecB, 2)))

# 随机质心
def randCent(dataSet, k):
    n = dataSet.shape[1]
    centroids = np.mat(np.zeros((k,n)))
    for j in range(n):
        minJ = min(dataSet[:, j])
        rangeJ = float(max(dataSet[:, j]) - minJ)
        centroids[:, j] = minJ + rangeJ * np.random.rand(k, 1)
    return centroids

def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
    m = dataSet.shape[0]
    clusterAssment = np.mat(np.zeros((m,2)))     # 用于记录聚类
    centroids = createCent(dataSet, k)
    clusterChanged = True
    while clusterChanged:
        clusterChanged = False
        # 遍历所有点
        for i in range(m):
            minDist = np.inf
            minIndex = -1
            # 寻找最近的质心
            for j in range(k):
                distJI = distMeas(centroids[j,:], dataSet[i,:])
                if distJI < minDist:
                    minDist = distJI
                    minIndex = j
            # 点所属簇发生改变的话将clusterChanged改为True
            if clusterAssment[i, 0] != minIndex:
                clusterChanged = True
            clusterAssment[i, :] = minIndex, minDist ** 2
        print(centroids)
        # 更新质心的位置
        for cent in range(k):
            ptsInClust = dataSet[np.nonzero(clusterAssment[:,0].A == cent)[0]]
            centroids[cent, :] = np.mean(ptsInClust, axis=0)
    return centroids, clusterAssment

kMeans()函数接受4个输入函数，只有数据集及簇的数目是必需的，而用来计算距离和创建初始随机质心的函数都是可选的。

簇分配结果矩阵clusterAssment包含两列：一列记录簇索引值，第二列存储误差。这里的误差指当前点到簇质心的距离，后面会用来评价聚类效果。

接下来用一个数据集来展示一下。

data = np.mat(loadDataSet('testSet.txt'))
myCentroids, clustAssing = kMeans(data, 4)

输出如下：

[[ 0.58416761  4.95307752]
 [ 1.65859849 -0.32066583]
 [-3.08249088  0.60763474]
 [-2.3709823  -3.100304  ]]
[[ 1.75060988  3.63551582]
 [ 3.05395587 -1.49072096]
 [-2.65218135  2.62294929]
 [-3.01169468 -3.01238673]]
[[ 2.54391447  3.21299611]
 [ 2.8692781  -2.54779119]
 [-2.46154315  2.78737555]
 [-3.38237045 -2.9473363 ]]
[[ 2.6265299   3.10868015]
 [ 2.80293085 -2.7315146 ]
 [-2.46154315  2.78737555]
 [-3.38237045 -2.9473363 ]]

一共输出4次质心，也就是说，经过4次迭代后kMeans算法收敛。

下图是数据集聚类结果的可视化，簇中心用十字表示。