K均值算法

一、基本原理

K-均值算法属于无监督的聚类算法，所谓无监督就是原始数据集中的分类标签是未知的，聚类的意思为将相似的对象归到同一个簇中。k指的是将数据集分成几个簇，而均值的意思是，判断是否为相同类别的标准为数据的均值。
K-均值算法首先随机确定k个初始点作为质心(均值)，然后计算数据集中每个点和每个质心的距离，并将其分配给距离最近的质心的类别中，这样就会产生了k个类别，然后再更新每个类别的质心，重复计算，直到每个类别的质心不在变化或满足迭代次数。
伪代码为：

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

二、算法实现

准备数据集

3.275154	2.957587   
-3.344465	2.603513   
0.355083	-3.376585   
1.852435	3.547351
...
2.960769	3.079555
-3.275518	1.577068
0.639276	-3.412840

数据集由一系列的二维坐标构成，用制表符隔开，首先用open函数打开文本文件，然后将其放入python列表中。
程序实现：

from numpy import *

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

程序说明：
map(function, iterable, ...)：将可迭代对象iterable执行函数function，即对可迭代对象中的每一个元素都进行一次函数调用，得到新的可迭代对象。python3中map()函数返回的是迭代器，所以要在前面调用list()函数将其转换为列表。
函数首先打开原始数据文件，然后用制表符隔开数据并添加到列表中，因为后面需要对其进行数值计算，而readlines()函数返回的列表元素是字符串，所以要利用map()函数将其全部转换为浮点数类型。最后添加至返回值列表中。

随机生成质心

k均值的核心就是不断的更新质心，但最开始的质心通常是随机生成的，且必须要在原始数据集的范围内，即要保证在最小值和最大值之间。
程序实现：

def randCent(dataSet, k):
    n = shape(dataSet)[1]  # 返回数据集的列数
    centroids = mat(zeros((k, n)))  # 初始化质心为0
    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

程序说明：
mat()：将数据转为矩阵形式。array()：将数据转为数组形式。矩阵：二维数据，数组：多维数据。numpy中默认的数据形式为数组形式。
首先计算出数据每列的最小和最大值，然后得到取值范围，从而确定随机数。k为质心的个数。

1 2	range = max - min i = min + range * (0,1) # 在(min,max)范围内

距离计算

K均值算法需要将其数据集中的数据分配给距离最近的质心的类别中，常用的距离计算公式为平面内点之间的距离公式。
图
程序实现：

1 2	def distEclud(vecA, vecB): return sqrt(sum(power(vecA - vecB, 2)))

当然也可以用其他的距离计算公式。

k均值算法

程序实现：

def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
    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
        for cent in range(k):   
            ptsInClust = dataSet[nonzero(clusterAssment[:, 0].A == cent)[0]]   
            centroids[cent, :] = mean(ptsInClust, axis=0)  # 更新每个类别的质心
    return centroids, clusterAssment

程序说明：
该函数一共有4个输入参数，第一个为数据集dataSet，第二个为分类类别数目，第三个为距离计算公式，第四个为创建初始质心的函数。返回值为质心坐标和簇分配结果矩阵(类别标签结果和与质心的误差)。
首先初始化簇分配结果矩阵为0并随机产生k个质心。函数主体一共有3层循环，第一层循环为while循环，其循环条件为：clusterChanged，即任一点的簇分配结果的类别标签是否改变，也就是每个数据的前后2次分类结果都是同一类就跳出while循环，否则需要继续分类。首先将其设为false，然后进入第二层的for循环判断，该层for循环会遍历数据集中的每一行数据，首先初始化距离和类别标签，然后进入第三层的for循环判断，该层for循环会判断每一行数据属于哪一类的类别标签，首先计算质心坐标和数据集中每一行数据的距离，并和minDist判断大小，一共判断k次，即有多少个类别就判断多少次，从而找到哪个类别和质心的距离最小，并设置为该类别。每做完一次第三层循环，都会判断一次终止条件是否满足，即如果之前判断的类别标签和现在的结果不是一致的，则仍需要继续分类，也就是现在的质心还不稳定，数据集中还存在不稳定的分类结果。
每遍历完一次完整的数据集都需要重新计算每个类别的质心。 clusterAssment[:, 0]表示簇分配结果的第一列，即每行数据的类别标签，.A表示将结果转换为矩阵形式，然后判断是否等于相应的类别(k表示分类数目，也相当于类别标签，比如k为3，表示一共3类，类别为0，1，2)，nonzero()返回非0元素的索引，也就是返回是该类别的数据的索引，然后根据索引找到dateSet数据中的数据。也就是分别找到簇分配结果矩阵中的每个类别对应的原始数据集的数据。这里[0]表示的是nonzero()函数有很多返回值，我们需要的是其索引值，也就是第1个返回值。得到每一类的数据后，在进行均值计算，得到每一类的新的质心。

程序结果

质心坐标：

1
2
3

[[ 2.93386365  3.12782785]
 [-2.94737575  3.3263781 ]
 [-0.45965615 -2.7782156 ]]  # 每一类质心的坐标

簇分配结果矩阵：

[[0.00000000e+00 1.45461050e-01]
 [1.00000000e+00 6.80213825e-01]
 [2.00000000e+00 1.02184582e+00]
...
 [0.00000000e+00 3.05416591e-03]
 [1.00000000e+00 3.16776316e+00]
 [2.00000000e+00 1.61040000e+00]]

第一列为分类结果，0表示第一类，以此类推，第二列为每类数据与该类质心的误差。