聚类（kmeans，DBSCAN，OPTICS）

2020-05-27 本文已影响0人 Jasmine晴天和我

聚类

K-means聚类

样本集 $D={x_1,x_2,...,x_m}$ ，聚类簇数k。

从D中随机选择k个样本作为初始均值向量 ${\mu_1,\mu_2,...,\mu_k}$

令 $C_i=\varnothing(1\leq i\leq k)$

for j =1,2,...m

计算样本 $x_j$ 与各均值向量 $\mu_i$ 的距离

距离最近的均值向量，就确定了 $x_j$ 的簇标记，并加入相应的簇中。

计算新的均值向量，继续按照上述步骤划分，直到均值向量不再被更新。

形象的解释：

1.首先输入 k 的值，即我们指定希望通过聚类得到 k 个分组；
2、从数据集中随机选取 k 个数据点作为初始大佬（质心）；
3、对集合中每一个小弟，计算与每一个大佬的距离，离哪个大佬距离近，就跟定哪个大佬。
4、这时每一个大佬手下都聚集了一票小弟，这时候召开选举大会，每一群选出新的大佬（即通过算法选出新的质心）。
5、如果新大佬和老大佬之间的距离小于某一个设置的阈值（表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛），可以认为我们进行的聚类已经达到期望的结果，算法终止。
6、如果新大佬和老大佬距离变化很大，需要迭代3~5步骤。

参考链接：https://www.cnblogs.com/qingyunzong/p/9760913.html

DBSCAN密度聚类

给定参数 $\epsilon$ ,minpts

核心对象：若 $x_i$ 的 $\epsilon$ 邻域内至少包含minpts个样本，则 $x_i$ 是一个核心对象。

密度直达：若 $x_j$ 位于 $x_i$ 的 $\epsilon$ 邻域内，并且 $x_i$ 是核心对象，则称 $x_j$ 由 $x_i$ 密度直达。

密度可达：对于 $x_j$ 与 $x_i$ ，若存在样本序列 $p_1,p_2,...p_n$ 其中 $p_1=x_i,p_n=x_j$ 且 $p_{i+1}$ 由 $p_i$ 密度直达，则称 $x_j$ 与 $x_i$ 密度可达。

密度相连：对 $x_j$ 与 $x_i$ ，若存在 $x_k$ 使得 $x_j$ 与 $x_i$ 均由 $x_k$ 密度可达，则称 $x_j$ 与 $x_i$ 密度相连。

边界点：如果一个对象在其半径eps内含有点的数量小于minpts，但是该对象落在核新对象的邻域内，则该对象为边界点。

簇：由密度可达关系导出的最大的密度相连样本集合。

若x是核心对象，由x密度可达的所有样本组成的集合X就是满足连接性与最大性的簇

先找到满足核心对象的集合 $\Omega$ ，从 $\Omega$ 中随机选取一个核心对象作为种子，找到由它密度可达的所有样本，这就构成了第一个聚类簇，并将刚刚选取的核心对象从 $\Omega$ 中去除，如此类推，直到 $\Omega$ 为空。

optics

只有核心对象有核心距离和可达距离。

核心距离：如果样本对象 $x_i$ 是核心对象，那么 $x_i$ 的核心距离，就是使样本 $x_i$ 能够成为核心对象的最小半径值 $\epsilon$ 参数。使得 $x_i$ 成为核心对象的最小距离，不是之前设定的 $\epsilon$ 参数，核心距离小于等于 $\epsilon$ 参数，样本 $x_i$ 的 $\epsilon$ 邻域内可能有多于minpts个样本，但是我们只取半径范围内恰好有minpts样本的半径值 $\epsilon$ 作为其核心距离。

可达距离： $x_i$ 和p的可达距离指：核心距离和两点欧式距离的最大值。

image.png

样本 $x_i$ 与样本 $p_1$ 的可达距离：在核心距离 $\epsilon^{'}$ 与 $p_1$ 欧几里得距离选较大的那个，选择核心距离。

样本 $x_i$ 与样本 $p_2$ 的可达距离：在核心距离 $\epsilon^{'}$ 与 $p_2$ 欧几里得距离选较大的那个，选择欧几里得距离。

密度越大，从相邻节点直接密度可达的距离就越小。optics算法用一个可达距离升序排列的有序种子队列迅速定位稠密空间的数据对象。

较稠密簇中的对象在簇排序中相互靠近；

一个对象的最小可达距离给出了一个对象连接到一个稠密簇的最短路径。

min_samples:一个点要成为核心点其邻域内至少点的数量

max_eps：最大半径

metric：距离矩阵，设置使用哪些距离，例如欧氏距离，曼哈顿距离等。如果使用自己定义的距离，需要设置为"precomputed"，然后对距离矩阵进行训练。

p:p=1曼哈顿距离，p=2欧式距离，任意的p使用闵式距离。

cluster_method:从可达性和排序结果，提取簇的方法，可以选择"xi"或者'dbscan'

eps：半径

xi：确定可达性图上的最小陡度，构成集群边界。

步骤：（根据不同的max_eps设定，最后得到的结果不同，eps基本不对算法结果产生影响）

1.先找出所有的核心对象，放在核心对象队列中。当max_eps设置默认为inf时，所有的点都能成为核心对象；当max_eps设置的较小时，就有一些点无法成为核心对象并且可能也不是其他核心对象的直接可达对象，这些点的可达距离全部为inf。

2.在核心对象队列中随机选择一个核心对象，第一个被处理的点是不存在可达距离的，所以设置其可达距离为inf。其在原数据集中的次序放入结果序列中，找到全部的直接密度可达点，并计算所有直接可达点的可达距离，放进有序队列中，按照可达距离升序排列。如果核心对象队列中的元素都已经被处理，算法结束。

3.在有序队列中选择可达距离最小的点，其在原数据集中的次序放入结果队列中，并将其在有序队列中删除。若有序队列为空，则算法结束。

3.1 判断该点是否是核心对象，如果是，找到其所有的直接密度可达点，如果其密度可达点已存在于有序队列中，并且此时的可达距离小于旧的可达距离，则用新的可达距离取代旧的可达距离。并且将有序列表中的点按照可达距离重新排序。

3.2如果不是核心对象，则寻找第二小的直接可达点。其在原数据集中的次序放入结果队列中，并将其在有序队列中删除，并按照3.1处理该点。

本文章参考了多位博主的文章，如有雷同麻烦联系我删除。

聚类（kmeans，DBSCAN，OPTICS）

聚类

K-means聚类

DBSCAN密度聚类

optics

猜你喜欢

热点阅读