Press "Enter" to skip to content

详解聚类算法的实现思路,以及在 D2C 布局中的应用

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

聚类是统计数据分析的一门技术,在许多邻域收到广泛的应用,包括机器学习,数据挖掘,图像分析等等。聚类就是把相似的对象分成不同的组别或者更多的子集,从而让每个子集的成员对象都有相似的一些属性。

 

所谓聚类算法,其实就是将一对没有标签的数据自动划分成几类的方法。在应用场景上,聚类能帮助我们解决很多计算机中的分类问题,常见的如:颜色类别分类、空间坐标中的密度分类、电商中的人群特征分类。除了分类问题外,它也能帮助我们实现“异常检查”,什幺是异常检查?我们可以理解为找噪点,通俗来说就是在一锅粥里面找出那些老鼠屎。

 

本篇文章主要是给大家介绍 聚类算法的实现原理 以及 聚类算法是如何应用在 D2C 设计稿生成代码中 。

 

1. DBSCAN 聚类算法

 

DBSCAN – 具有噪声的基于密度的聚类算法 。和 K-Means 这种只适合凸样本集的聚类相比,DBSCAN 既可以凸样本集,也适用于非凸样本集。它可以对散乱的样本基于一定的相似性进行分类,即在 不确定蔟数目 的情况下,根据样本的紧密程度进行 蔟 的划分。举个例子:

 

我们需要把“100、101、123、98、200、203、220”这堆数据进行聚类。 成蔟最小值为 2 的话, 此时如果我们设置的 聚类密度阈值为 30 。那幺“100、101、123、98” 和 “200、203、220”将会分成 2 蔟。 当 聚类密度阈值为 10 。那幺“100、101、98”、“200、203”、分成 2 个蔟,“123”、“220”则属于 噪声点(异常数据)

 

1.1 核心思想

 

DBSCAN 算法主要是找出样本点中所有的密集区域,我们称这些密集区域为 聚类蔟 。那幺不在密集区域内的样本点,我们称为 噪声点 。所以 DBSCAN 除了能帮你做分类外,也能找出“一锅粥里面的老鼠屎”

 

1.2 算法参数

 

1.3 点的类别

 

1.4 点的关系

 

1.5 算法实现步骤

 

由密度可达关系导出的 最大密度相连 的样本集合,即为我们最终聚类的一个类别,或者说一个簇。在实现上我们可以分为以下 4 步:

 

步骤 1:选择任意一个没有类别的核心地点作为初始点。 步骤 2:找出这个核心点能够 密度可达 的样本集合,也就是找出这个核心点邻域内的所有边界点,这时就可以成为一个聚类蔟。 步骤 3:继续找另外一个没有类别的核心点继续重复步骤 2 的操作。 步骤 4:直到所有的点

 

来点比较生动的例子:你可以假设一群人里面有个做传销的人(_核心点_),要发展下线,需要先找 N 个人(_minPoints_),于是他就在身边(_邻域_)去找人发展下线,那幺下线(边界点)就会继续找下线,直到身边没人。

 

2. 布局算法与 DBSCAN 的结合

 

简单介绍完 DBSCAN 的算法概念和算法实现后,我们讲一下聚类算法在 Deco 布局算法中的应用场景。

 

布局算法核心其实就是成组 ,如何基于设计稿每个模块的 位置信息和大小尺寸 来判断是否能组成成组是关键,简单来说,就是如何准确的把一堆节点拿个 DIV 套住。

 

如上图所示,设计稿上存在 11 个白色区块节点的节点,而我们肉眼去看, 以每个节点之间的紧密距离关系来作为依据 ,上半部分和下半部分是分开的。但是这仅限于我们的视觉,那如何让机器的视觉也认为是分开的呢?我们需要刚刚提到的 DBSCAN 聚类算法进行蔟的生成 ,那幺我们的目标是让上半部分会形成一个聚类蔟,下半部分也组成一个聚类蔟。

 

刚刚我们提到 DBSCAN 是 点到点之间的欧式距离作为紧密关系的依据 ,那幺在节点上来看的话,我们转变下思路,改为 区块与区块之间的最短距离作为紧密关系的依据

 

2.1 点状距离 > 区块距离

 

其实获取区块之间的最短距离比较简单,有三种情况

 

第一种:两个区块相交,那幺距离其实就是 0 了 第二种:A 区块与 B 区块是在其 上/下/左/右 的,那幺只需要获取两者之间的间距位置即可 第三种:A 区块与 B 区块是在其 左上/左下/右上/右下 的,那幺采用 勾股定理 获取下两者相对的顶点之间斜线的距离即可

 

改造之后的效果就是下图的样子,我们根据聚类算法的实现,最终就可以把上下 2 个分成 2 个聚类蔟

 

2.2 邻域半径推导

 

DBSCAN 聚类算法除了输入中,有 样本数据集 、 数据对象数目阈值 MinPoints 、 邻域半径 Eps ,那幺带布局算法中, 邻域半径 Eps 到底设多少才是合适的值呢?总不能是个固定值吧。有些模块间距的整体大一点,有些间距小一点,我们在实际布局对区块做聚合的时候需要求出这个 动态的邻域半径 Eps 。

 

第一步:我们对样本数据集之间的距离先做一个统计,先求出这 5 个区块它们之间的最短距离。

 

第二步:然后我们根据距离矩阵表,我们可以得出每个模块与其最相近模块之间的最短距离

 

第三步:在这堆数据中,我们需要提取 占比更多,比较有效的数据 作为我们的 Eps 值,剔除掉一些干扰项。

 

我们根据标准差的计算公式,我们取 1 倍标准差作为过滤项,筛选出符合多数样本的数据集,拿[5、5、5、5、100]求它的标准差,我们可以得出,总体标准偏差 38,平均值为 24

 

那我们取一倍标准差作为依据,可以得出在一倍标准差的范围内,取数最大值为 24 + 38 = 62,那幺我们就可以拿 62 作为我们在这个样本集的 邻域半径 Eps 。

 

2.3 算法优化

 

基于上述的算法改造,其实我们已经完成 比较靠谱 的在布局上实现模块聚类以及拆分。那幺在实际算法的运用上,还会针对 邻域半径 Eps 动态生成 做一个在布局实际场景的优化:

 

比如像下面这种布局:水平间距为 5、垂直间距为 10

 

那幺如果根据 最短距离标准差 的形式,那其实 8 个模块它们的最短距离都是 5,最终算出来 Eps 也是 5,那幺很有可能就会把上下两行分割开了。

 

所以我们在实际运用上,在 生成标准差样本 过程中,根据一定的规则,把水平距离的“10”也考虑进去,并作为标准差的样本进行计算。

 

3. 总结

 

本篇文章主要介绍了 DBSCAN 的实现原理,在介绍中并有给出具体的代码实现,这块大家感兴趣的话网上也有很多具体的代码实现逻辑。目的主要是给大家讲聚类算法的实现思路,以及在聚类算法在 D2C 上布局上的的应用落地。除了 DBSCAN 这种基于密度聚类算法外,其实还有很多算法也可在 D2C 布局算法上等待我们的挖掘。

 

引用文献:

[1] [DBSCAN密度聚类算法] ( https://www.cnblogs.com/pinard/p/6208966.html )
[2] [DBSCAN聚类算法——机器学习(理论+图解+python代码)] ( https://blog.csdn.net/huacha__/article/details/81094891 )
[3] [DBSCAN详解] ( https://blog.csdn.net/hansome_hong/article/details/107596543 )

作者:AzuFF 来源: https:// jelly.jd.com/article/61 db90889b585d01b13fcf73

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注