聚类笔记

  • 计算距离的时候,可以增加系数;

1. 前言

聚类算法本不在计划内,那为什么又学习它了呢,最主要的是看到了在任意多边形K均分案例中的应用,而这个应用也正是目前工作所需要的。

相比于前边几个算法,聚类算法会好理解一些。下边先来看看聚类的几个基本概念。设X为n个样本,每个样本m个特征的样本集合(m×n矩阵)。

  • 距离或相似度

    1. 闵可夫斯基距离

      image-20220801163036428

      p=2时,为欧式距离;

      p=1为曼哈顿距离;

      p=∞为切比雪夫距离,时等价于各坐标数值差的绝对值 的最大值。 max |xki - xkj|

    2. 马哈拉诺比距离

      设S为X的协方差矩阵

      image-20220801163827859

      当S为单位矩阵是,马氏距离就是欧式距离,所以马氏距离是欧式距离的推广。

    3. 相关系数

      image-20220801163952373

    4. 余弦夹角

      image-20220801164023705

      若数据经过中心化,余弦夹角就是相关系数

      猜测:因高维空间的距离表示不好,故用相似度表示更好

      在高维空间,密度大、距离小等不好衡量 => 维数灾难

  • 设T为给定的正数,若集合G中任意两个样本xi,xj, 有 dij <= T,则称G为一个类。

    类中的概念有,类的均值(类中心)、类的直径(最大样本距离)、样本协方差矩阵。

  • 类间距

    这个可以选择的包括:最短距离、最长距离、中心距离、平均距离。

    ps: 我觉得中心距离不错

2. 层次聚类

层次聚类可分成聚合聚类、分类聚类,二者相似,这里只介绍聚合聚类。

基本思路:开始时将每个样本分到一个类,之后将相距最近的两类合并,建立一个新的类,重复次操作直到满足停止条件。

描述:

  1. 计算n个样本两两之间的距离 dij ,用矩阵表示
  2. 构造n个类,每个类只包含一个样本
  3. 合并类间距最小的两个类,构建一个新类
  4. 计算新类与当前各类的距离
  5. 若类的个数达到条件,终止计算

聚类算法的复杂度是O(n3 m),其中m是样本维数,n是样本个数。样本大时,算法不快。

3. K均值聚类

基本思路:通过迭代将样本分到k个类中,使得每个样本与其所属的中心最近,得到k个平坦的,非层次化的类别。

描述:

根据不同的初始中心,会得到不同的聚类结果

K值的选择:

实际过程中k值是不知道,尝试用不同的k值聚类,检测各自得到聚类结果,推测最优的k值。一般的,类别数变小时,平均直径会增加;类别数变大超过某个值后,平均直径会不变。

对大量数据时,算法可保持高效率。O(mnk)

当类近似为高斯分布时,它的效果较好。

对噪声敏感

4. 密度聚类:DBSCAN

一个基于密度的簇是最大的密度相连对象的集合。

密度聚类中,根据密集程度不同,将点分成:核心点、边界点、噪音点三种。

image-20220801153335707

核心点: 周边包括n个及以上点(直接密度可达);

边界点:周边不够n个点,单它与核心点有交集(密度相连),边界点自身可能也是核心点,边界点可能是多个核心点的边界点;

噪声点:周边也不够n个点,且与核心点无交集;

这样密度聚类就有两个变量:最小距离(衡量周边)与点数n(point)。

密度可达:如果存在一个对象链,使后一个点是前一个点的直接密度可达,则最终构成了密度可达。

描述:

  1. 如果一个点p的d-邻域包含多余n个对象,则建立一个p作为核心对象的新簇;
  2. 寻址、合并该核心点所有密度可达的点;
  3. 没有新点,算法结束。

密度聚类可以用作去噪声。

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×