聚类算法之K-means

Python,算法,机器学习 2017-12-26

起步

所谓聚类( Clustering ),就是将相似的事物聚集在一 起,而将不相似的事物划分到不同的类别的过程,是数据分析之中十分重要的一种手段。与此前介绍的决策树,支持向量机不同的监督学习不同,聚类算法是非监督学习( unsupervised learning ),在数据集中,并不清楚具体的类别。

K-means算法介绍

K-means 算法是数据挖掘十大经典算法之一。由于该算法的效率高,所以在对大规模数据进行聚类时被广泛应用。目前,许多算法均围绕着该算法进行扩展和改进。

kmeans.jpg

k-means 算法接受一个参数 k ,表示将数据集中的数据分成 k 个聚类。在同一个聚类中,数据的相似度较高;而不同聚类的数据相似度较低。k-means 算法的步骤为:

  • 步骤一:选择任意 k 个数据,作为各个聚类的质心,(ps:质心也可以理解为中心的意思),执行步骤二;
  • 步骤二:对每个样本进行分类,将样本划分到最近的质心所在的类别,执行步骤三;
  • 步骤三:取各个聚类的中心点作为新的质心,执行步骤二进行迭代。

迭代的结束条件

  • 当新的迭代后的聚类结果没有发生变化;
  • 当迭代次数达到预设的值。

算法步骤的流程图:

Image.png

相似性度量

对于类聚,怎样计算两个数据点的相似性,在空间坐标中,我们可以采用欧式距离来进行判断,距离越近,就表示数据点越“相似”。欧式距离表示为:

d(x,y) = \sqrt{\sum_{i=0}^n(x_i-y_i)^2}

对应的python代码:

import math

def euler_distance(point1: list, point2: list) -> float:
    """
    计算两点之间的欧拉距离,支持多维
    """
    distance = 0.0
    for a, b in zip(point1, point2):
        distance += math.pow(a - b, 2)
    return math.sqrt(distance)

python 实现K-means

根据算法步骤,我们可以用代码来实现,大概有 50 行:

import random
import numpy as np
import collections

class K_means(object):
    def __init__(self, k: int, max_iter=10):
        self.k = k
        self.max_iter = 10      # 最大迭代次数
        self.data_set = None    # 训练集
        self.labels = None      # 结果集

    def init_centroids(self) -> list:
        """
        从训练集中随机选择 k 个点作为质点
        """
        point_num = np.shape(self.data_set)[0]
        random_index = random.sample(list(range(point_num)), self.k)
        centroids = [self.data_set[i] for i in random_index]
        return centroids

    def fit(self, data_set):
        self.data_set = data_set
        point_num = np.shape(data_set)[0]
        self.labels = [ -1 ] * point_num            # 初始化结果集
        centroids = self.init_centroids()           # 初始化随机质点
        old_centroids = []                          # 上一次迭代的质点
        step = 0                                    # 当前迭代次数
        while not self.should_stop(old_centroids, centroids, step):
            old_centroids = np.copy(centroids)
            step += 1
            for i, point in enumerate(data_set):
                self.labels[i] = self.get_closest_index(point, centroids)
            centroids = self.update_centroids()

    def get_closest_index(self, point, centroids):
        min_dist = math.inf # 初始设为无穷大
        label = -1
        for i, centroid in enumerate(centroids):
            dist = euler_distance(centroid, point)
            if dist < min_dist:
                min_dist = dist
                label = i
        return label

    def update_centroids(self):
        """
        取各类的中心设为新的质点
        """
        collect = collections.defaultdict(list)
        for i, label in enumerate(self.labels):
            collect[label].append(self.data_set[i])

        centroids = []
        for i in range(self.k):
            centroids.append(np.mean(collect[i], axis=0))
        return centroids

    def should_stop(self, old_centroids, centroids, step) -> bool:
        """
        判断是否停止迭代,停止的条件是 新分类结果与原来一致或者已达到设置的迭代次数
        """
        if step > self.max_iter:
            return True
        return np.array_equal(old_centroids, centroids)

测试对比

将我们手写的代码与 sklearn 中的对于,数据集使用模块提供的虹膜数据:

from sklearn import cluster, datasets

iris = datasets.load_iris()
my_k = K_means(4)
my_k.fit(iris.data)
print(np.array(my_k.labels))

sk = cluster.KMeans(4)
sk.fit(iris.data)
print(sk.labels_)

得到输出:

[2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 3 0 3 0 3 0 3 3 3 3 0 3 0 0 3 0 3 0 3 0 0
 0 0 0 0 0 3 3 3 3 0 3 0 0 0 3 3 3 0 3 3 3 3 3 0 3 3 1 0 1 1 1 1 3 1 1 1 0
 0 1 0 0 1 1 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 0 1 1 1 0 0
 1 0]
[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 3 0 3 0 3 0 3 3 3 3 0 3 0 3 3 0 3 0 3 0 0
 0 0 0 0 0 3 3 3 3 0 3 0 0 0 3 3 3 0 3 3 3 3 3 0 3 3 2 0 2 2 2 2 3 2 2 2 0
 0 2 0 0 2 2 2 2 0 2 0 2 0 2 2 0 0 2 2 2 2 2 0 0 2 2 2 0 2 2 2 0 2 2 2 0 0
 2 0]

聚类的结果几乎一致,还是不错的。

K-means优缺点

优点:

  • 速度快,复杂度低,为 O(Nkq),N是数据总量,k是类别,q是迭代次数。一般来讲k、q会比N小得多,那么此时复杂度相当于 O(N) ,在各种算法中是算很小的;
  • 原理简单,易于理解。

缺点:

  • 对异常点敏感;
  • 局部最优解而不是全局优,(分类结果与初始点选取有关);
  • 不能发现非凸形状的聚类。

附录

本次实验的代码:kmeans_example.py


本文由 hongweipeng 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。

如果对您有用,您的支持将鼓励我继续创作!