关于机器学习:Kmeans聚类算法

K-means 聚类算法

聚类

在无监督学习中, 训练样本的标记信息是未知的, 指标是通过对无标记训练样本的学习来揭示数据的外在性质及法则, 为进一步的数据分析提供根底，此类学习工作中钻研最多、利用最广的是“聚类”(clustering)

聚类试图将数据集中的样本划分为若干个通常是不相交的子集, 每个子集称为一个“簇”(cluster)

通过这样的划分, 每个簇可能对应于一些潜在的概念(类别), 需阐明的是, 这些概念对聚类算法而言当时是未知的, 聚类过程仅能主动造成簇构造, 簇所对应的概念语义需由使用者来把握

对于簇的残缺定义尚未达成共识，传统的定义如下

• 同一簇中的实例必须尽可能类似
• 不同簇中的实例必须尽可能不同
• 类似度和相异度的度量必须分明并具备实际意义

性能度量

聚类性能度量大抵有两类

• 将聚类后果与某个参考模型进行比拟, 称为“内部指标”(external index)
• 间接考查聚类后果而不利用任何参考模型, 称为“外部指标”(internalindex)

内部指标

对数据集 $D=\\left\\{\\boldsymbol{x}_{1}, \\boldsymbol{x}_{2}, \\ldots, \\boldsymbol{x}_{m}\\right\\},$ 假设通过聚类给出的族划分为 $\\mathcal{C}=\\left\\{C_{1},C_{2}, \\ldots, C_{k}\\right\\},$ 参考模型给出的族划分为 $\\mathcal{C}^{*}=\\left\\{C_{1}^{*}, C_{2}^{*}, \\ldots, C_{s}^{*}\\right\\} .$ 相应地, 令 $\\boldsymbol{\\lambda}$ 与 $\\lambda^{*}$ 别离示意与 $\\mathcal{C}$ 和 $\\mathcal{C}^{*}$ 对应的族标记向量. 咱们将样本两两配对思考, 定义

$$
\begin{aligned}
a &\left.=|S S|, \quad S S=\left\{\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \mid \lambda_{i}=\lambda_{j}, \lambda_{i}^{*}=\lambda_{j}^{*}, i<j\right)\right\} \\
b &\left.=|S D|, \quad S D=\left\{\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \mid \lambda_{i}=\lambda_{j}, \lambda_{i}^{*} \neq \lambda_{j}^{*}, i<j\right)\right\} \\
c &\left.=|D S|, \quad D S=\left\{\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \mid \lambda_{i} \neq \lambda_{j}, \lambda_{i}^{*}=\lambda_{j}^{*}, i<j\right)\right\} \\
d &\left.=|D D|, \quad D D=\left\{\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \mid \lambda_{i} \neq \lambda_{j}, \lambda_{i}^{*} \neq \lambda_{j}^{*}, i<j\right)\right\}
\end{aligned}
$$

其中汇合 $S S$ 蕴含了在 $\\mathcal{C}$ 中隶属于雷同族且在 $\\mathcal{C}^{*}$ 中也隶属于雷同族的样本

汇合 $S D$ 蕴含了在 $\\mathcal{C}$ 中隶属于雷同族但在 $\\mathcal{C}^{*}$ 中隶属于不同族的样本

汇合 $D S$ 蕴含了在 $\\mathcal{C}$ 中隶属于 不同族但在 $\\mathcal{C}^{*}$ 中隶属于雷同族的样本

汇合 $DD$ 蕴含了在 $\\mathcal{C}$ 中隶属于不同族在 $\\mathcal{C}^{*}$ 中也隶属于不同族的样本

可计算出上面这些聚类性能度量内部指标

• Jaccard 系数

$$
\mathrm{JC}=\frac{a}{a+b+c}
$$

• FM 指数（Fowlkes and Mallows Index,FMI）

$$
\mathrm{FMI}=\sqrt{\frac{a}{a+b} \cdot \frac{a}{a+c}}
$$

• Rand 指数(Rand Index,RI)

$$
\mathrm{RI}=\frac{2(a+d)}{m(m-1)}
$$

显然上述性能度量的后果值均在 [0，1] 区间，值越大越好

外部指标

思考聚类后果的族划分 $\\mathcal{C}=\\left\\{C_{1}, C_{2}, \\ldots, C_{k}\\right\\},$ 定义

$$
\begin{aligned}
\operatorname{avg}(C) &=\frac{2}{|C|(|C|-1)} \sum_{1 \leqslant i<j \leqslant|C|} \operatorname{dist}\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \\
\operatorname{diam}(C) &=\max _{1 \leqslant i<j \leqslant|C|} \operatorname{dist}\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \\
d_{\min}\left(C_{i}, C_{j}\right) &=\min _{\boldsymbol{x}_{i} \in C_{i}, \boldsymbol{x}_{j} \in C_{j}} \operatorname{dist}\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \\
d_{\operatorname{cen}}\left(C_{i}, C_{j}\right) &=\operatorname{dist}\left(\boldsymbol{\mu}_{i}, \boldsymbol{\mu}_{j}\right)
\end{aligned}
$$

其中，dist $(\\cdot, \\cdot)$ 用于计算两个样本之间的间隔

$\\boldsymbol{\\mu}$ 代表族 $C$ 的中心点 $\\boldsymbol{\\mu}=$ $\\frac{1}{|C|} \\sum_{1 \\leqslant i \\leqslant|C|} \\boldsymbol{x}_{i}$

显然, $\\operatorname{avg}(C)$ 对应于族 $C$ 内样本间的均匀间隔 $, \\operatorname{diam}(C)$ 对应于族 $C$ 内样本间的最远距离 $, d_{\\min}\\left(C_{i}, C_{j}\\right)$ 对应于族 $C_{i}$ 与族 $C_{j}$ 最近样本间的间隔 $, d_{\\mathrm{cen}}\\left(C_{i}, C_{j}\\right)$ 对应于族 $C_{i}$ 与族 $C_{j}$ 中心点间的间隔.

可计算出上面这些聚类性能度量外部指标

• DB 指数(Davies-Bouldin Index, DBI)

$$
\mathrm{DBI}=\frac{1}{k} \sum_{i=1}^{k} \max _{j \neq i}\left(\frac{\operatorname{avg}\left(C_{i}\right)+\operatorname{avg}\left(C_{j}\right)}{d_{\mathrm{cen}}\left(\mu_{i}, \mu_{j}\right)}\right)
$$

• Dunn 指数(Dunn Index, DI)

$$
\mathrm{DI}=\min _{1 \leqslant i \leqslant k}\left\{\min _{j \neq i}\left(\frac{d_{\min}\left(C_{i}, C_{j}\right)}{\max _{1 \leqslant l \leqslant k} \operatorname{diam}\left(C_{l}\right)}\right)\right\}
$$

显然, DBI 的值越小越好, 而 DI 则相同, 值越大越好

间隔度量

可参考 k - 近邻算法（KNN）中距离度量局部

常见的聚类算法

原型聚类

原型聚类亦称“基于原型的聚类”(prototype-based clustering)

假如聚类构造能通过一组原型（指样本空间中具备代表性的点）刻画, 通常情景下，算法先对原型进行初始化, 而后对原型进行迭代更新求解. 采纳不同的原型示意、不同的求解形式将产生不同的算法，上面是几种驰名的原型聚类算法

• k-means
• 学习向量量化（Learning Vector Quantization,LVQ）
• 高斯混合聚类（Mixture-of-Guassian）

档次聚类

档次聚类 (hierarchical clustering) 试图在不同档次对数据集进行划分，从而造成树形的聚类构造

数据集的划分可采纳“自底向上”的聚合策略，它将最类似的两个点合并，直到所有点都合并到一个群集中为止

也可采纳“自顶向下 ” 的分拆策略，它以所有点作为一个簇开始，并在每一步拆分类似度最低的簇，直到仅剩下单个数据点

在分层聚类中，聚类数（k）通常由用户预先确定，通过在指定深度切割树状图来调配聚类，从而失去 k 组较小的树状图

与许多分区聚类技术不同，分层聚类是 确定性 过程，这意味着当您对雷同的输出数据运行两次算法时，聚类调配不会扭转

档次聚类办法的 长处 包含

• 它们通常会揭示无关数据对象之间的更具体的信息。
• 它们提供了 可解释的树状图。

档次聚类办法的 毛病 包含

• 算法复杂度高
• 对 乐音 和异样值 很敏感

基于密度的聚类

基于密度的聚类依据区域中数据点的密度确定聚类调配, 在高密度的数据点被低密度区域分隔的中央调配簇

与其余类别的聚类不同，该办法不须要用户指定群集数量，而是有一个基于间隔的参数充当可调阈值来确定是否将靠近的点视为簇成员

DBSCAN 是一种驰名的密度聚类算法，它基于一组畛域参数来刻画样本分布的严密水平

基于密度的聚类办法的 长处 包含

• 他们善于辨认 非类圆型 簇。
• 它们能够抵制 异样值。

基于密度的聚类办法的 毛病 包含

• 它们不太适宜在 高维空间中聚类
• 很难确定 密度不同的 簇。

K-means

k 均值聚类算法（k-means clustering algorithm）是一种迭代求解的聚类分析算法

它试图将数据集划分为 K 个不同的非重叠子组(簇)，其中每个数据点只属于一个组

同时使得簇内数据点尽可能类似，还要尽可能放弃簇之间的差别

聚类调配的品质是通过计算质心 收敛 后的平方误差和（sum of the squared error,SSE）来确定的，或者与先前的迭代调配相符

SSE 定义为每个点与其最靠近的质心的欧几里德间隔平方的总和，k-means 的目标是尝试最小化该值

下图显示了在同一数据集上两次不同的k -means 算法运行的前五个迭代中的质心和 SSE 更新：

此图的目标是表明质心的初始化是重要的一步，随机初始化步骤导致 k -means 算法 不确定，这意味着如果您在同一数据集上运行两次雷同的算法，则簇调配将有所不同

钻研人员通常会对整个 k 均值算法进行几次初始化，并从具备最低 SSE 的初始化

工作形式

1. 指定簇数 K
2. 首先对数据集 shuffle，而后为质心随机抉择 K 个 数据点

3. 一直迭代，直到质心没有变动，即数据点调配给群集的操作没有扭转

   • 计算数据点和所有质心之间的平方间隔之和
   • 将每个数据点调配给最近的群集（质心）
   • 通过获取属于每个群集的所有数据点的平均值，计算群集的质心

k-means 解决问题的办法称为冀望最大化（Expectation Maximization,EM）
指标函数是

$$
E=\sum_{i=1}^{k} \sum_{\boldsymbol{x} \in C_{i}}\left\|\boldsymbol{x}-\boldsymbol{\mu}_{i}\right\|_{2}^{2}
$$

其中 $\\mu_{i}=\\frac{1}{|C_{i}|} \\sum_{x \\in C_{i}} x$ 是族 $C_{i}$ 的均值向量
最小化指标函数并不容易, 找到它的最优解需考查样本集 $D$ 所有可能的族划分, 这是一个 $\\mathrm{NP}$ 难问题

因而 k -means 算法采纳了贪婪策略, 通过迭代优化来近似求解

Tips

• 类别数 $k$ 值须要预先指定，而在理论利用中最优的 $k$ 值是不晓得的, 解决这个问题的一个办法是尝试用不同的 $k$ 值聚类, 测验各自失去聚类后果的品质, 揣测最优的 $k$ 值
• 因为包含 kmeans 在内的聚类算法应用基于间隔的度量来确定数据点之间的相似性，因而倡议对数据进行标准化
• 因为 kmeans 算法可能停留在部分最优而不收敛于全局最优，因而不同的初始化可能导致不同的聚类，倡议应用不同的质心初始化来运行算法，并抉择产生较低 SSE 的运行后果

找到适合的 K

上面将介绍两个指标，这些指标可能使咱们更间接的察看 k 的取值

肘部法令（Elbow Method)

k-means 是以最小化样本与质点平方误差作为指标函数，将每个簇的质点与簇内样本点的平方间隔误差和称为畸变水平(distortions)，那么，对于一个簇，它的畸变水平越低，代表簇内成员越严密，畸变水平越高，代表簇内构造越涣散

畸变水平会随着类别的减少而升高，但对于有肯定区分度的数据，在达到某个临界点时畸变水平会失去极大改善，之后迟缓降落，这个临界点就能够思考为聚类性能较好的点

存在当曲线是枯燥递加的时依然很难找出适合的簇数的可能

轮廓系数（Silhouette Coefficient）

轮廓系数是聚类联合和拆散程序的评估指标，它基于两个因素来量化数据点适宜其调配的簇的水平

1. 数据点与簇中其余点的间隔有多近
2. 数据点与其余簇中的点有多远

计算距同一簇中所有数据点的均匀间隔 $a_i$
计算到最近的簇中所有数据点的均匀间隔 $b_i$

$$
\frac{b^{i}-a^{i}}{\max \left(a^{i}, b^{i}\right)}
$$

轮廓系数值介于 - 1 和 1 之间，越靠近 1 示意样本所在簇正当

若近似为 0，则阐明样本在两个簇的边界上

毛病

如果簇是类圆形的，那么 Kmeans 算法是能够胜任的，它总是尝试在质心四周结构一个不错的球形

但这这意味着，当群集具备简单的几何形态时，Kmeans 的体现不好，如下

不出所料，kmeans 无奈找出两个数据集的正确聚类

然而，如果咱们应用核办法，将其转换为高维示意从而使数据线性可拆散，则能够帮忙 kmeans 完满地聚类此类数据集

实现代码

# coding = utf-8

import numpy as np

class KMeans:

    def __init__(self,n_clusters, max_iters=100, random_state=666):
        """初始化 Kmeans 模型"""
        self.n_clusters = n_clusters
        self.max_iters = max_iters
        self.random_state = random_state

    def initializ_centroids(self, X):
        np.random.RandomState(self.random_state)
        random_idx = np.random.permutation(X.shape[0])
        centroids = X[random_idx[:self.n_clusters]]
        return centroids

    def compute_centroids(self, X, labels):
        centroids = np.zeros((self.n_clusters, X.shape[1]))
        for k in range(self.n_clusters):
            centroids[k, :] = np.mean(X[labels == k, :], axis=0)
        return centroids

    def compute_distance(self, X, centroids):
        distance = np.zeros((X.shape[0], self.n_clusters))
        for k in range(self.n_clusters):
            row_norm = np.linalg.norm(X - centroids[k, :], axis=1)
            distance[:, k] = np.square(row_norm)
        return distance

    def find_closest_cluster(self, distance):
        return np.argmin(distance, axis=1)


    def compute_sse(self, X, labels, centroids):
        distance = np.zeros(X.shape[0])
        for k in range(self.n_clusters):
            distance[labels == k] = np.linalg.norm(X[labels == k] - centroids[k], axis=1)
        return np.sum(np.square(distance))

    def fit(self, X):
        self.centroids = self.initializ_centroids(X)
        for i in range(self.max_iters):
            old_centroids = self.centroids
            distance = self.compute_distance(X, old_centroids)
            self.labels = self.find_closest_cluster(distance)
            self.centroids = self.compute_centroids(X, self.labels)

            if np.all(old_centroids == self.centroids):
                break
        self.error = self.compute_sse(X, self.labels, self.centroids)
        return self

    def predict(self, X_predict):
        distance = self.compute_distance(X, old_centroids)
        return self.find_closest_cluster(distance)

if __name__ == '__main__':
    from sklearn.datasets import make_blobs
    from sklearn.preprocessing import StandardScaler
    features, true_labels = make_blobs(
        n_samples=200,
        n_features=2,
        centers=3,
        cluster_std=2.75,
        random_state=42
    )
    scaler = StandardScaler()
    scaled_features = scaler.fit_transform(features)

    kmeans = KMeans(
        n_clusters=3,
        max_iters=300,
        random_state=42
    )
    kmeans.fit(scaled_features)

参考

机器学习 - 周志华

K-Means Clustering in Python: A Practical Guide

K-means Clustering: Algorithm, Applications, Evaluation Methods, and Drawbacks