K-means聚类算法

一，原理

k-means算法以数据间的距离作为数据对象相似性度量的标准，因此选择计算数据间距离的计算方式对最后的聚类效果有显著的影响，常用计算距离的方式有：余弦距离、欧式距离、曼哈顿距离等。本文以欧式距离为例（会一种，其余也就会了）。
欧式距离公式：

例子：若数据为)其计算欧式距离如下(可理解为D表示维度，i,j表示行数)：
通过计算（1）当前点与每个组中心之间的距离，对每个数据点进行分类，然后归到与距离最近的中心的组中。
基于迭代后的结果，计算每一类内，所有点的平均值，作为新簇中心。

Ck表示第k类，|Ck|表示第k类中数据对象的个数。类心迭代过程如下：

k-means的优点是速度非常快，因为我们真正要做的就是计算点和组中心之间的距离；计算量少！因此，它具有线性复杂性o（n）。
另一方面，k-means有两个缺点。首先，您必须先确定聚类的簇数量。理想情况下，对于一个聚类算法，我们希望它能帮我们解决这些问题，因为它的目的是从数据中获得一些洞察力。k-均值也从随机选择聚类中心开始，因此它可能在算法的不同运行中产生不同的聚类结果。因此，结果可能不可重复，缺乏一致性。K中位数是与K均值相关的另一种聚类算法，除了不使用平均值重新计算组中心点之外，我们使用组的中位数向量。这种方法对异常偏离值不太敏感（因为使用了中值），但对于较大的数据集来说要慢得多，因为在计算中值向量时，每次迭代都需要排序。

二，代码

直接使用K-means聚类函数：

#coding=utf-8
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
#读取txt
X=[]
f=open('AA.txt')
for v in f:
	X=append([float(v.split(',')[1]),float(v.split(','[2])])
X = np.array(X)
#类簇的数量
n_clusters = 5
#现在把数据和对应的分类书放入聚类函数中进行聚类
cls = KMeans(n_clusters).fit(X)
#X中每项所属分类的一个列表
cls.labels_
#画图
markers = ['^', 'x', 'o', '*', '+']
for i in range(n_clusters):
  members = cls.labels_ == i
  plt.scatter(X[members, 0], X[members, 1], s=60, marker=markers[i], c='b', alpha=0.5)
plt.title(' ')
plt.show()

用原理写代码：

import numpy as np
import matplotlib.pyplot as plt
# 加载数据
def loadDataSet(fileName):
    data = np.loadtxt(fileName,delimiter='\t')
    return data
# 欧氏距离计算
def distEclud(x,y):
    return np.sqrt(np.sum((x-y)**2))  # 计算欧氏距离
# 为给定数据集构建一个包含K个随机质心的集合
def randCent(dataSet,k):
    m,n = dataSet.shape
    centroids = np.zeros((k,n))
    for i in range(k):
        index = int(np.random.uniform(0,m)) #
        centroids[i,:] = dataSet[index,:]
    return centroids 
# k均值聚类

def KMeans(dataSet,k):
    m = np.shape(dataSet)[0]  #行的数目
    # 第一列存样本属于哪一簇
    # 第二列存样本的到簇的中心点的误差
    clusterAssment = np.mat(np.zeros((m,2)))
    clusterChange = True
    # 第1步 初始化centroids
    centroids = randCent(dataSet,k)
    while clusterChange:
        clusterChange = False
        # 遍历所有的样本（行数）
        for i in range(m):
            minDist = 100000.0
            minIndex = -1
            # 遍历所有的质心
            #第2步 找出最近的质心
            for j in range(k):
                # 计算该样本到质心的欧式距离
                distance = distEclud(centroids[j,:],dataSet[i,:])
                if distance < minDist:
                    minDist = distance
                    minIndex = j
            # 第 3 步：更新每一行样本所属的簇
            if clusterAssment[i,0] != minIndex:
                clusterChange = True
                clusterAssment[i,:] = minIndex,minDist**2
        #第 4 步：更新质心
        for j in range(k):
            pointsInCluster = dataSet[np.nonzero(clusterAssment[:,0].A == j)[0]]  # 获取簇类所有的点
            centroids[j,:] = np.mean(pointsInCluster,axis=0)   # 对矩阵的行求均值
    print("Congratulations,cluster complete!")
    return centroids,clusterAssment
def showCluster(dataSet,k,centroids,clusterAssment):
    m,n = dataSet.shape
    if n != 2:
        print("数据不是二维的")
        return 1
    mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
    if k > len(mark):
        print("k值太大了")
        return 1
    # 绘制所有的样本
    for i in range(m):
        markIndex = int(clusterAssment[i,0])
        plt.plot(dataSet[i,0],dataSet[i,1],mark[markIndex])
    mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb']
    # 绘制质心
    for i in range(k):
        plt.plot(centroids[i,0],centroids[i,1],mark[i])
        plt.show()
dataSet = loadDataSet("test.txt")
k = 4
centroids,clusterAssment = KMeans(dataSet,k)
showCluster(dataSet,k,centroids,clusterAssment)