kmeans聚类算法

前言

kmeans是一种聚类算法

其简单，易用

在机器学习，数据挖掘领域常常应用

原理

众所周知聚类就是要对一堆杂乱无章的数据进行分类合并

假设我们有数据集dataset，并且将其聚类为k个簇
kmeans聚类算法的思想有如下几步

第一步

首先在数据集随机挑选k个点，分别作为这k个簇的质心

第二步

其余的点根据欧式距离公式，找到离其自身最近的质心
并合并为一类

第三步

现在我们已经初步的到聚类过的样本集合

然后我们取每个样本集合的均值点作为新的质心
重新进行聚类

第四步

各样本点根据新的质心再进行回归

直到样本点分类不再发生改变

算法实现

网上也有很多算法实现
这里我找到一篇比较有效率的代码
下面是该博客地址
https://blog.csdn.net/xufive/article/details/101448969
我在其源代码上增加了一些注释
话不多说直接上代码

import numpy as np
import time
import matplotlib.pyplot as plt


def kmeans(ds, k):
    """
    kmeans聚类算法
    :param ds: 数据集,形式为ndarray(m, n) 即m个样本，每个样本有 n 个属性值
    :param k: 指定分簇数量
    :return:
    """
    m, n = ds.shape
    result = np.empty(m, dtype=np.int) # 产生一个有随机元素的指定大小的矩阵
    cores = ds[np.random.choice(np.arange(m), k ,replace=False)] # 从m个样本随机挑选k个作为core

    while True:
        d = np.square(np.repeat(ds, k, axis=0).reshape(m, k, n) - cores)
        """
        np.repeat是将一个矩阵展开成行向量
        第二个参数指定要复制多少
        这里就是展开数据集
        因为有k个质心
        然后分别计算对应的距离差值
        """
        distance = np.sqrt(np.sum(d, axis=2)) # 在第二维度累加，即形状由(m, k, n)变为(m, k)
        index_min = np.argmin(distance, axis=1) # 找距离最小值

        if (index_min == result).all():
            # 这个条件就是样本聚类没有发生改变
            return result, cores # 返回聚类结果，以及质心

        result[:] = index_min

        for i in range(k):
            # 取质心集合的平均值做为新的质心
            items = ds[result==i] # 找出当前质心对应的数据集
            cores[i] = np.mean(items, axis=0) # 取质心平均值作为新的质心进行迭代


def create_data_set(*cores):
    """生成k-means聚类测试用数据集"""

    ds = list()
    for x0, y0, z0 in cores:
        x = np.random.normal(x0, 0.1 + np.random.random() / 3, z0)
        y = np.random.normal(y0, 0.1 + np.random.random() / 3, z0)
        ds.append(np.stack((x, y), axis=1))

    return np.vstack(ds)


k = 4
ds = create_data_set((0,0,2500), (0,2,2500), (2,0,2500), (2,2,2500))

t0 = time.time()
result, cores = kmeans(ds, k)
t = time.time() - t0

plt.scatter(ds[:,0], ds[:,1], s=1, c=result.astype(np.int))
plt.scatter(cores[:,0], cores[:,1], marker='x', c=np.arange(k))
plt.show()

print(u'使用kmeans算法，1万个样本点，耗时%f0.3秒'%t)