1.前言

聚類(lèi)是統(tǒng)計(jì)數(shù)據(jù)分析的一門(mén)技術(shù)，在許多領(lǐng)域受到廣泛的應(yīng)用，包括機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、圖像分析等等。聚類(lèi)就是把相似的對(duì)象分成不同的組別或者更多的子集，從而讓每個(gè)子集的成員對(duì)象都有相似的一些屬性。

所謂聚類(lèi)算法，其實(shí)就是將一對(duì)沒(méi)有標(biāo)簽的數(shù)據(jù)自動(dòng)劃分成幾類(lèi)的方法。在應(yīng)用場(chǎng)景上，聚類(lèi)能幫助我們解決很多計(jì)算機(jī)中的分類(lèi)問(wèn)題，常見(jiàn)的如：顏色類(lèi)別分類(lèi)、空間坐標(biāo)中的密度分類(lèi)、電商中的人群特征分類(lèi)。除了分類(lèi)問(wèn)題外，它也能幫助我們實(shí)現(xiàn)“異常檢查”，什么是異常檢查?我們可以理解為找噪點(diǎn)，通俗來(lái)說(shuō)就是在一鍋粥里面找出那些老鼠屎。

本篇文章主要是給大家介紹聚類(lèi)算法的實(shí)現(xiàn)原理以及聚類(lèi)算法是如何應(yīng)用在 D2C 設(shè)計(jì)稿生成代碼中。

2.DBSCAN 聚類(lèi)算法

DBSCAN - 具有噪聲的基于密度的聚類(lèi)算法。和 K-Means 這種只適合凸樣本集的聚類(lèi)相比，DBSCAN 既可以凸樣本集，也適用于非凸樣本集。它可以對(duì)散亂的樣本基于一定的相似性進(jìn)行分類(lèi)，即在不確定蔟數(shù)目的情況下，根據(jù)樣本的緊密程度進(jìn)行蔟的劃分。舉個(gè)例子：

我們需要把“100、101、123、98、200、203、220”這堆數(shù)據(jù)進(jìn)行聚類(lèi)。成蔟最小值為 2的話， 此時(shí)如果我們?cè)O(shè)置的聚類(lèi)密度閾值為 30。那么“100、101、123、98” 和 “200、203、220”將會(huì)分成 2 蔟。當(dāng)聚類(lèi)密度閾值為 10。那么“100、101、98”、“200、203”、分成 2 個(gè)蔟，“123”、“220”則屬于噪聲點(diǎn)(異常數(shù)據(jù))。

2.1 核心思想

DBSCAN 算法主要是找出樣本點(diǎn)中所有的密集區(qū)域，我們稱(chēng)這些密集區(qū)域?yàn)榫垲?lèi)蔟。那么不在密集區(qū)域內(nèi)的樣本點(diǎn)，我們稱(chēng)為噪聲點(diǎn)。所以 DBSCAN 除了能幫你做分類(lèi)外，也能找出“一鍋粥里面的老鼠屎”。

2.2 算法參數(shù)

2.3 點(diǎn)的類(lèi)別

2.4 點(diǎn)的關(guān)系

2.5 算法實(shí)現(xiàn)步驟

由密度可達(dá)關(guān)系導(dǎo)出的最大密度相連的樣本集合，即為我們最終聚類(lèi)的一個(gè)類(lèi)別，或者說(shuō)一個(gè)簇。在實(shí)現(xiàn)上我們可以分為以下 4 步：

步驟 1：選擇任意一個(gè)沒(méi)有類(lèi)別的核心地點(diǎn)作為初始點(diǎn)；

步驟 2：找出這個(gè)核心點(diǎn)能夠密度可達(dá)的樣本集合，也就是找出這個(gè)核心點(diǎn)鄰域內(nèi)的所有邊界點(diǎn)，這時(shí)就可以成為一個(gè)聚類(lèi)蔟；

步驟 3：繼續(xù)找另外一個(gè)沒(méi)有類(lèi)別的核心點(diǎn)繼續(xù)重復(fù)步驟 2 的操作；

步驟 4：直到所有的點(diǎn)。

來(lái)點(diǎn)比較生動(dòng)的例子：你可以假設(shè)一群人里面有個(gè)做傳銷(xiāo)的人(核心點(diǎn))，要發(fā)展下線，需要先找 N 個(gè)人(minPoints)，于是他就在身邊(鄰域)去找人發(fā)展下線，那么下線(邊界點(diǎn))就會(huì)繼續(xù)找下線，直到身邊沒(méi)人。

3.布局算法與 DBSCAN 的結(jié)合

簡(jiǎn)單介紹完 DBSCAN 的算法概念和算法實(shí)現(xiàn)后，我們講一下聚類(lèi)算法在 Deco 布局算法中的應(yīng)用場(chǎng)景。

布局算法核心其實(shí)就是成組，如何基于設(shè)計(jì)稿每個(gè)模塊的位置信息和大小尺寸來(lái)判斷是否能組成成組是關(guān)鍵，簡(jiǎn)單來(lái)說(shuō)，就是如何準(zhǔn)確的把一堆節(jié)點(diǎn)拿個(gè)DIV套住。

如上圖所示，設(shè)計(jì)稿上存在 11 個(gè)白色區(qū)塊節(jié)點(diǎn)的節(jié)點(diǎn)，而我們?nèi)庋廴タ?，以每個(gè)節(jié)點(diǎn)之間的緊密距離關(guān)系來(lái)作為依據(jù)，上半部分和下半部分是分開(kāi)的。但是這僅限于我們的視覺(jué)，那如何讓機(jī)器的視覺(jué)也認(rèn)為是分開(kāi)的呢?我們需要?jiǎng)倓偺岬降腄BSCAN 聚類(lèi)算法進(jìn)行蔟的生成，那么我們的目標(biāo)是讓上半部分會(huì)形成一個(gè)聚類(lèi)蔟，下半部分也組成一個(gè)聚類(lèi)蔟。

剛剛我們提到 DBSCAN 是點(diǎn)到點(diǎn)之間的歐式距離作為緊密關(guān)系的依據(jù)，那么在節(jié)點(diǎn)上來(lái)看的話，我們轉(zhuǎn)變下思路，改為 區(qū)塊與區(qū)塊之間的最短距離作為緊密關(guān)系的依據(jù) 。

3.1 點(diǎn)狀距離 > 區(qū)塊距離

其實(shí)獲取區(qū)塊之間的最短距離比較簡(jiǎn)單，有三種情況：

第一種：兩個(gè)區(qū)塊相交，那么距離其實(shí)就是 0 了；

第二種：A 區(qū)塊與 B 區(qū)塊是在其上/下/左/右的，那么只需要獲取兩者之間的間距位置即可；

第三種：A 區(qū)塊與 B 區(qū)塊是在其左上/左下/右上/右下的，那么采用勾股定理獲取下兩者相對(duì)的頂點(diǎn)之間斜線的距離即可。

改造之后的效果就是下圖的樣子，我們根據(jù)聚類(lèi)算法的實(shí)現(xiàn)，最終就可以把上下 2 個(gè)分成 2 個(gè)聚類(lèi)蔟：

3.2 鄰域半徑推導(dǎo)

DBSCAN 聚類(lèi)算法除了輸入中，有樣本數(shù)據(jù)集、數(shù)據(jù)對(duì)象數(shù)目閾值 MinPoints、鄰域半徑 Eps，那么帶布局算法中，鄰域半徑 Eps到底設(shè)多少才是合適的值呢?總不能是個(gè)固定值吧。有些模塊間距的整體大一點(diǎn)，有些間距小一點(diǎn)，我們?cè)趯?shí)際布局對(duì)區(qū)塊做聚合的時(shí)候需要求出這個(gè)動(dòng)態(tài)的鄰域半徑 Eps。

第一步：我們對(duì)樣本數(shù)據(jù)集之間的距離先做一個(gè)統(tǒng)計(jì)，先求出這 5 個(gè)區(qū)塊它們之間的最短距離。

第二步：然后我們根據(jù)距離矩陣表，我們可以得出每個(gè)模塊與其最相近模塊之間的最短距離。

第三步：在這堆數(shù)據(jù)中，我們需要提取占比更多，比較有效的數(shù)據(jù)作為我們的 Eps 值，剔除掉一些干擾項(xiàng)。

我們根據(jù)標(biāo)準(zhǔn)差的計(jì)算公式，我們?nèi)?1 倍標(biāo)準(zhǔn)差作為過(guò)濾項(xiàng)，篩選出符合多數(shù)樣本的數(shù)據(jù)集，拿[5、5、5、5、100]求它的標(biāo)準(zhǔn)差，我們可以得出，總體標(biāo)準(zhǔn)偏差 38，平均值為 24。

那我們?nèi)∫槐稑?biāo)準(zhǔn)差作為依據(jù)，可以得出在一倍標(biāo)準(zhǔn)差的范圍內(nèi)，取數(shù)最大值為 24 + 38 = 62，那么我們就可以拿 62 作為我們?cè)谶@個(gè)樣本集的鄰域半徑 Eps。

3.3 算法優(yōu)化

基于上述的算法改造，其實(shí)我們已經(jīng)完成比較靠譜的在布局上實(shí)現(xiàn)模塊聚類(lèi)以及拆分。那么在實(shí)際算法的運(yùn)用上，還會(huì)針對(duì)鄰域半徑 Eps 動(dòng)態(tài)生成做一個(gè)在布局實(shí)際場(chǎng)景的優(yōu)化：

比如像下面這種布局：水平間距為 5、垂直間距為 10：

那么如果根據(jù)最短距離標(biāo)準(zhǔn)差的形式，那其實(shí) 8 個(gè)模塊它們的最短距離都是 5，最終算出來(lái) Eps 也是 5，那么很有可能就會(huì)把上下兩行分割開(kāi)了。

所以我們?cè)趯?shí)際運(yùn)用上，在生成標(biāo)準(zhǔn)差樣本過(guò)程中，根據(jù)一定的規(guī)則，把水平距離的“10”也考慮進(jìn)去，并作為標(biāo)準(zhǔn)差的樣本進(jìn)行計(jì)算。

4.技術(shù)落地

以上技術(shù)已經(jīng)落地在 Deco 智能代碼生成項(xiàng)目上，Deco 是我們團(tuán)隊(duì)在「前端智能化」方向上的探索，其聚焦設(shè)計(jì)稿一鍵生成多端代碼這一切入點(diǎn)，實(shí)現(xiàn)將 Sketch/Photoshop 等設(shè)計(jì)稿進(jìn)行解析并直接生成多端代碼(Taro/React/Vue)的能力。Deco 可以使前端工程師不需要花大量精力關(guān)注設(shè)計(jì)稿，大大節(jié)約了開(kāi)發(fā)成本，為輸出更多的多端頁(yè)面提供了有力的支持，也為業(yè)務(wù)降本增效帶來(lái)了巨大動(dòng)力。

在過(guò)去的一年里，Deco 已在京東的兩次大促中成功落地，在個(gè)性化活動(dòng)會(huì)場(chǎng)的搭建中，研發(fā)效率提升達(dá)到了 48%。

感興趣的同學(xué)可以移步 Deco官網(wǎng)[1] 進(jìn)行體驗(yàn)。另外也給大家附上 Deco 體驗(yàn)的保姆級(jí)教程。

5.總結(jié)

本篇文章主要介紹了 DBSCAN 的實(shí)現(xiàn)原理，在介紹中并有給出具體的代碼實(shí)現(xiàn)，這塊大家感興趣的話網(wǎng)上也有很多具體的代碼實(shí)現(xiàn)邏輯。目的主要是給大家講聚類(lèi)算法的實(shí)現(xiàn)思路，以及在聚類(lèi)算法在 D2C 上布局上的的應(yīng)用落地。除了 DBSCAN 這種基于密度聚類(lèi)算法外，其實(shí)還有很多算法也可在 D2C 布局算法上等待我們的挖掘。