聚类方法（Clustering）

2020-07-13 16:07:02 浏览数 (1)

  • 聚类：依据样本特征的相似度或距离，将其归并到若干个“类”或“簇”的数据分析问题
  • 聚类目的：通过得到的类或簇来发现数据的特点或对数据进行处理，在数据挖掘、模式识别等领域有着广泛的应用
  • 聚类 属于无监督学习，因为只是根据样本的相似度或距离将其进行归类，而类或簇事先并不知道

1. 聚类基本概念

1.1 相似度、距离

  • 有多种相似度或距离的定义
  • 相似度直接影响聚类的结果，其选择很关键

闵可夫斯基距离 ：

d_{ij} = bigg(sumlimits_{k=1}^m |x_{ki} - x_{kj}|^p bigg)^{frac{1}{p}}

, 距离越大，相似度越小

p=1

, 曼哈顿距离

p=2

, 欧式距离

p=infty

, 切比雪夫距离，

d_{ij} = maxlimits_k |x_{ki} - x_{kj}|

马哈拉诺比斯距离： 考虑各个分量（特征）之间的相关性，与各个分量的尺度无关，距离越大，相似度越小

d_{ij}=[(x_i-x_j)^TS^{-1}(x_i-x_j)]^{1/2}, quad S 为样本协方差矩阵

马氏距离是欧氏距离的推广。

相关系数：其绝对值越接近1，越相似；越接近0，越不相似

r_{ij}=frac{sumlimits_{k=1}^m(x_{ki }- bar x_i)(x_{kj}- bar x_j)}{bigg[sumlimits_{k=1}^m(x_{ki }- bar x_i)^2sumlimits_{k=1}^m(x_{kj}- bar x_j)^2 bigg]^{1/2}}

夹角余弦： 夹角余弦越接近于1，表示样本越相似；越接近于0，表示样本越不相似

s_{ij} = frac{sumlimits_{k=1}^m x_{ki}x_{kj}}{bigg[ sumlimits_{k=1}^m x_{ki}^2 sumlimits_{k=1}^m x_{kj}^2bigg]^{1/2}}
  • 从距离的角度看，A和B比A和C更相似
  • 从相关系数的角度看，A和C比A和B更相似
  • 进行聚类时，选择适合的距离或相似度非常重要

1.2 类、簇

  • 聚类得到的类或簇，本质是样本的子集
  • 如果假定一个样本只能属于一个类，或类的交集为空集，称为硬聚类（hard clustering）
  • 如果一个样本可以属于多个类，或类的交集不为空集，称为软聚类（soft clustering）

类、簇定义

dij≤Td_{ij} le Tdij​≤T ，最常用，且能推出下面的

1nG−1∑xj∈Gdij≤Tfrac{1}{n_G-1}sumlimits_{x_j in G}d_{ij} le TnG​−11​xj​∈G∑​dij​≤T

1nG(nG−1)∑xi∈G∑xj∈Gdij≤T,dij≤Vfrac{1}{n_G(n_G-1)}sumlimits_{x_i in G}sumlimits_{x_j in G}d_{ij} le T ,quad d_{ij} le VnG​(nG​−1)1​xi​∈G∑​xj​∈G∑​dij​≤T,dij​≤V

d_{ij} le T

，最常用，且能推出下面的

frac{1}{n_G-1}sumlimits_{x_j in G}d_{ij} le T
frac{1}{n_G(n_G-1)}sumlimits_{x_i in G}sumlimits_{x_j in G}d_{ij} le T ,quad d_{ij} le V

类的特征：

  • 类的均值（中心）：
bar x_G = frac{1}{n_G}sumlimits_{i=1}^{n_G}x_i
  • 类的直径：
D_G = maxlimits_{x_i,x_j in G} d_{ij}
  • 类的样本散布矩阵：
A_G=sumlimits_{i=1}^{n_G}(x_i-bar x_G)(x_i-bar x_G)^T
  • 类的样本协方差矩阵：
S_G=frac{1}{m-1}A_G=frac{1}{m-1}sumlimits_{i=1}^{n_G}(x_i-bar x_G)(x_i-bar x_G)^T, m样本维数

1.3 类之间的距离

  • 最短距离或单连接：
D_{pq} = min {d_{ij}|x_i in G_p,x_j in G_q}
  • 最长距离或完全连接：
D_{pq} = max {d_{ij}|x_i in G_p,x_j in G_q}
  • 中心距离：
D_{pq} = d_{bar x_pbar x_q}
  • 平均距离：
D_{pq} = frac{1}{n_p n_q}sumlimits_{x_i in G_p}sumlimits_{x_j in G_q}d_{ij}

2. 层次聚类

  • 层次聚类 假设类别之间 存在层次结构，将样本聚到层次化的类中
  • 层次聚类：有聚合（agglomerative）或自下而上（bottom-up）聚类、分裂（divisive）或自上而下（top-down）聚类 两种方法
  • 每个样本只属于 一个类，所以层次聚类属于 硬聚类

聚合聚类：

  • 将每个样本 各自分到一个类
  • 之后将相距最近的两类合并，建立一个新的类
  • 重复上一步直到满足停止条件；得到层次化的类别

分裂聚类：

  • 将所有样本分到一个类
  • 之后将已有类中相距最远的样本分到两个新的类
  • 重复上一步直到满足停止条件；得到层次化的类别。

聚合聚类的具体过程如下：

  • 对给定的样本集合，开始将每个样本分到一个类
  • 按照一定规则，例如 类间距离最小，将 最 满足规则条件的两个类进行合并
  • 反复上一步，每次减少一个类，直到满足停止条件，如 所有样本聚为一类

聚合聚类需要预先确定三要素：

  • （1）距离或相似度（闵可夫斯基距离、马哈拉诺比斯距离、相关系数、夹角余弦）
  • （2）合并规则（类间距离最小，可以是 最短距离、最长距离、中心距离、平均距离）
  • （3）停止条件（类的个数达到阈值（极端情况类的个数是1）、类的直径超过阈值）

3. K均值聚类

k均值 聚类：是基于样本集合划分的聚类算法

  • 将样本集合划分为 k 个子集，构成 k 个类
  • 将 n 个样本分到 k 个类中，每个样本到其所属类的中心的距离最小
  • 每个样本只能属于一个类，是硬聚类

3.1 模型

n 个样本 划分成 k 个类，类之间的交集为空（硬聚类）

3.2 策略

策略：通过损失函数的最小化 选取 最优的划分 或 函数

C^*
  • 样本距离：欧氏距离，
d(x_i,x_j)=||x_i-x_j||^2
  • 损失函数：样本与其类属的中心的距离总和，
W(C) = sumlimits_{l=1}^ksumlimits_{C(i)=l} ||x_i-bar x_l||^2
  • 本质：求解最优化问题
C^* = argminlimits_C W(C) = argminlimits_C sumlimits_{l=1}^ksumlimits_{C(i)=l} ||x_i-bar x_l||^2

n 个样本 划分成 k 个类，组合数是指数级的，其最优解求解是 NP 困难问题，常用迭代求解

3.3 算法

k均值聚类 的算法是迭代的过程，每次迭代包括两个步骤

  • 首先随机选择 k 个类的中心（选 k 个样本），将其余样本逐个指派到与其最近的中心的类中，得到一个聚类结果
  • 然后更新每个类的样本的均值，作为类的新的中心
  • 重复以上步骤，直到收敛

3.4 算法特性

1. 总体特点

  • 基于划分的聚类方法
  • 类别数 k 事先指定
  • 以欧氏距离平方表示样本之间的距离
  • 以中心或样本的 均值 表示类别
  • 以 样本 和 其所属类的中心 之间的 距离的总和 为最优化目标函数
  • 得到的类别是平坦的、非层次化的
  • 是迭代算法，不能 保证得到全局最优

2. 收敛性

  • k均值 聚类属于启发式方法，不能 保证收敛到全局最优
  • 初始中心的选择 会 直接影响聚类结果
  • 类中心在聚类的过程中会发生移动，但是往往不会移动太大，因为在每一步，样本被分到与其最近的中心的类中

3. 初始类的选择

  • 选择不同的初始中心，会得到不同的聚类结果
  • 初始中心的选择，比如 可以用层次聚类对样本进行聚类，得到k个类时停止。然后从每个类中选取一个与中心距离最近的点

4. 类别数k的选择

  • k 值需要预先指定，而在实际应用中最优k值是不知道的
  • 解决方法：尝试不同的k值，检验聚类的质量，推测最优的k值
  • 聚类结果的质量：可以用类的平均直径来衡量
  • 一般地，类别数变小时，平均直径会增加；类别数变大超过某个值以后，平均直径会不变；而这个值正是最优的k值
  • 可以采用二分查找，快速找最优的k值

4. sklearn.cluster

sklearn.cluster 官网介绍了10种聚类算法。

4.1 sklearn.cluster.KMeans k均值聚类

sklearn.cluster.KMeans 官网参数介绍

代码语言：javascript复制
class sklearn.cluster.KMeans(n_clusters=8, init='k-means  ', n_init=10,
max_iter=300, tol=0.0001, precompute_distances='auto', verbose=0,
random_state=None, copy_x=True, n_jobs=None, algorithm='auto')

主要参数：

  • n_clusters, default=8 类的个数，即k值
  • init：{‘k-means ’, ‘random’} 初始中心选择，默认选项更好
  • n_init, default=10 多次初始化，然后聚类，最后取最好的聚类结果
  • max_iter, default=300 单次聚类的最大迭代次数
  • tol, default=1e-4 迭代停止精度
  • precompute_distances：‘auto’ or bool, default=’auto’ 预先计算距离
  • algorithm：{“auto”, “full”, “elkan”}, default=”auto” 迭代算法. The classical EM-style algorithm is “full”. The “elkan” variation is more efficient by using the triangle inequality, but currently doesn’t support sparse data. “auto” chooses “elkan” for dense data and “full” for sparse data.

代码示例：

代码语言：javascript复制
from sklearn.cluster import KMeans
import numpy as np
# 书上例题
X = np.array([[0, 2], [0, 0], [1, 0], [5, 0], [5, 2]])
kms = KMeans(n_clusters=2).fit(X)
print(kms.labels_)
print(kms.cluster_centers_)

运行结果：

代码语言：javascript复制
[0 0 0 1 1]
[[0.33333333 0.66666667]
 [5.         1.        ]]

4.2 Hierarchical clustering 层次聚类

sklearn.cluster.AgglomerativeClustering

代码语言：javascript复制
class sklearn.cluster.AgglomerativeClustering(n_clusters=2, affinity='euclidean',
memory=None, connectivity=None, compute_full_tree='auto', linkage='ward',
distance_threshold=None)

官方代码示例

聚类算法

0 人点赞