k-means

partitioning a dataset into k distinct clusters based on similarity measures. It aims to minimize the within-cluster sum of squares (WCSS) or the average squared distance between data points and their assigned cluster centroids 通过样本间的相似性对数据集进行聚类，使类内差距最小化，类间差距最大化

过程

  • 选择初始化的 k 个样本作为初始聚类中心

  • 针对数据集中每个样本, 计算它到 k 个聚类中心的距离并将其分到距离最小的聚类中心所对应的类中

  • 针对每个类别 ，重新计算它的聚类中心 （即属于该类的所有样本的质心）；

  • 重复上面 2 3 两步操作，直到达到某个中止条件（迭代次数、最小误差变化等

评价

  • 可以通过衡量簇内差异来衡量聚类的效果：Inertia

    • a.它的计算太容易受到特征数目的影响。

    • b.它不是有界的，Inertia是越小越好，但并不知道何时达到模型的极限，能否继续提高。

    • c.它会受到超参数K的影响，随着K越大，Inertia必定会越来越小，但并不代表模型效果越来越好。

    • d.Inertia 对数据的分布有假设，它假设数据满足凸分布，并且它假设数据是各向同性的，所以使用Inertia作为评估指标，会让聚类算法在一些细长簇、环形簇或者不规则形状的流形时表现不佳。

  • 轮廓系数

PCA

  • explained variance ratio

  • create new uncorrelated variables that successively maximize variance by solving an eigenvalue/eigenvector problem.

  • reduce the dimensionality of dataset, increase interpretability while minimize information loss

  • pros: no need of prior; reduce overfitting (by reduce #variables in the dataset); visualizable

  • cons: data standardization is a prerequisite; information loss

问答

  • cons

    • 对outlier敏感

  • k means 如何选择k

    • scree plot: 横坐标n_cluster, 纵坐标intra-cluster variance (区分 inter-cluster variance)

  • 怎么判断clustering效果好不好

    • 聚类评价指标: Purity, NMI, RI, Precision(查准率), Recall(查全率), F, ARI, Accuracy(正确率)

  • k-means和KNN的区别

    • k-means无监督，KNN有监督

  • signal-to-variance ratio

  • K-means为什么是收敛的

  • K-means 怎么初始化 K-means++

  • EM方法为什么是收敛的

code

# https://gancode.com/2021/03/01/6933952373303803912.html
import numpy as np
import random

class KMeans:
    def __init__(self, n_clusters=3, random_state=0):
        assert n_clusters >=1, " must be valid"
        self._n_clusters = n_clusters
        self._random_state = random_state
        self._center = None  # cluster中心, n_cluster * n_feature
        self.cluster_centers_ = None

    def distance(self, M, N):
        return (np.sum((M - N) ** 2, axis = 1))** 0.5

    def _generate_labels(self, center, X):
        return np.array([np.argmin(self.distance(center, item)) for item in X])

    def _generate_centers(self, labels, X):
        return np.array([np.average(X[labels == i], axis=0) for i in np.arange(self._n_clusters)])

    def fit_predict(self, X, n_iters=1000, tol=1e-4):
        # X: 样本, n_sample * n_feature
        k = self._n_clusters

        # 设置随机数
        if self._random_state:
            random.seed(self._random_state)

        # 生成随机中心点的索引
        center_index = [random.randint(0, X.shape[0]) for _ in np.arange(k)]
        center = X[center_index]
        # print('init center: ', center)

        while n_iters > 0:
            # 记录上一个迭代的中心点坐标
            last_center = center

            # 根据上一批中心点，计算各个点所属的类
            labels = self._generate_labels(last_center, X)
            self.labels_ = labels

            # 新的中心点坐标
            center = self._generate_centers(labels, X)
            # if np.linalg.norm(center - self.cluster_centers_) < tol:
            #     break
            self.cluster_centers_ = center

            # 如果新计算得到的中心点，和上一次计算得到的点相同，说明迭代已经稳定了。
            if (last_center == center).all():
                self.labels_ = self._generate_labels(center, X)
                break

            n_iters = n_iters - 1
        return self

时间复杂度： O(tkmn) ，t 为迭代次数，k 为簇的数目，n 为样本点数，m 为样本点维度 空间复杂度： O(m(n+k)) ，k 为簇的数目，m 为样本点维度，n 为样本点数

# PCA: np.linalg.norm

参考

Previous无监督Next强化学习

Last updated