聚类算法
聚类算法
Nuyoah聚类算法
聚类的概念:
-
聚类是一个无监督问题,我们在分类的时候没有哪一类的标签了
-
聚类:相似的东西分到了一组
-
难点:如何评估,如何调参
K-MEANS算法
基本概念
-
要得到簇的个数,需要指定K值,例如上图所示,它的K值就是3
-
质心:均值,即向量各维度取平均即可,就是各个簇最中心的点
-
距离的度量:这里有两种方法:
- 欧氏距离:sqrt[(x1-x2)^2 + (y1-y2)^2 ……]
- 余弦相似度:以原点为起始点,需要比较的两个点为终止点,做向量,求这两个向量的余弦,余弦约小这两个点越相似
- 我们一般使用欧氏距离来计算两点的距离
- 我们在计算的时候应该先吧数据标准化,为了防止不同维度上数据差距,导致的误差,标准化之后,可以让他们变化范围尽可能的缩小,不影响我们计算
-
要优化的目标:
其中最外层的是从1 到 K 相加, 最里层是每一个类中每一个点到质心的距离
我们想要的是 在每一个类中属于该类的点到该类的质心的距离和最小
工作流程
-
这是我们的初始数据分布图。现在假设我们把它分为两类 K = 2
-
当我们确定分完的类数之后,会随机生成K个点 然后 开始遍历我们的每一个数据点,分别到这K个点的距离,取较小的哪一个然后把它分为哪一类
-
这是我们分完之后出现的类别,计算完之后会初步分成两类
-
分完之后我们就要跟新 质点, 寻找每一类的中心点然后把哪一个点设置为新的质点
-
然后重新进行距离的计算,从新分类
-
分完类之后从新更新质点, 然后在分类,直到质点稳定为止
优势和劣势
-
优势:
- 简单,快速,适合常规数据集
-
劣势:
-
K值难以确定,如果给你一个分布不均匀的数据集的化,我们很难确定我们要分为几类,我们上面的数据集,是一个特例
-
复杂度与样本呈现线性关系,因为我们每一次进行迭代的时候会算所有数据到样本点之间的距离,所以我们分的类越多,计算复杂度越高
-
很难发现任意形状的簇
-
DBSCAN 算法
基本概念:(Density-Based Spatial Clustering of Applications with Noise)
-
核心对象:若某个点的密度达到算法设定的阈值则其为核心点。(即r邻域内点的数量不小于minPts)
-
邻域内的距离阈值:设定的半径r
-
直接密度可达:若点p在点q的r邻域内,且q是核心点,则p-q是直接密度可达
-
密度可达:若有一个点的序列为q0,q1,q2,q3…qk,对任意的qi - qi-1是直接密度可达的,则称从q0到qk是密度可达的,这实际上是直接密度可达的“传播”
就像这个图我设置其中A表示的红点 都是密度可达的, 其中 BC 表示边界点 N 表示离群点
-
密度相连,若从某个核心点出发点q和点k都是密度可达的,则称点q和点k是密度相连的
-
边界点:属于某一个类的非核心点,不能够发展下线了
-
噪声点:不属于任何一类簇的点,从任何一个核心点出发都是密度不可达的
工作流程
- 参数的输入
- 参数D:输入数据集
- 参数ε : 指定半径
- Minpts:密度阈值
- 工作流程
- 标记所有的对象为unvisited(未被访问的)
- Do
- 随机选择一个 unvisited对象p
- 标记p为visited
- if p的ε邻域内至少有MinPts个对象
- 创建一个新簇C,并把p添加到C中
- 令N为p的ε邻域中对象的集合
- For N中的每一个点p
- if p 是unvisited的
- 标记p为visited
- if p的ε邻域内至少有Minpta个对象,把这些对象添加到N中
- 如果p还不是任何簇中的成员,把p添加到C
- if p 是unvisited的
- EndFor
- 输入C
- Else 标记p为噪声
- Until 没有标记为unvisited的对象
- 参数的选择
- 半径ε可以根据K距离来设定:照突变点,
- K距离:给定数据集P = {p(i); i = 0,1,…n},计算p(i)到集合D中子集S中所有点之间的距离,距离按照从小到大的顺序排序,d(k)就被称为k-距离
- MinPts:k-距离中的值,一般取小一些,多次尝试
- 半径ε可以根据K距离来设定:照突变点,
优势和劣势
-
优势:
-
不需要指定簇的个数
-
可以发现任意形状的簇
-
擅长找到离群点(检测任务)
-
两个参数就够了
-
-
劣势:
- 高维数据有点困难(需要先降维)
- 参数难以选择(参数对结果的影响非常大)
- Sklearn 中效率比较慢(数据削减工作)
K-Means算法的实现
我们先创建一个K-Meansl类
1 | import numpy as np |
测试:
1 | import pandas as pd |