聚類算法在 D2C 布局中的應(yīng)用
1.前言
聚類是統(tǒng)計(jì)數(shù)據(jù)分析的一門技術(shù)，在許多領(lǐng)域受到廣泛的應(yīng)用，包括機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、圖像分析等等。聚類就是把相似的對象分成不同的組別或者更多的子集，從而讓每個子集的成員對象都有相似的一些屬性。
所謂聚類算法，其實(shí)就是將一對沒有標(biāo)簽的數(shù)據(jù)自動劃分成幾類的方法。在應(yīng)用場景上，聚類能幫助我們解決很多計(jì)算機(jī)中的分類問題，常見的如：顏色類別分類、空間坐標(biāo)中的密度分類、電商中的人群特征分類。除了分類問題外，它也能幫助我們實(shí)現(xiàn)“異常檢查”，什么是異常檢查?我們可以理解為找噪點(diǎn)，通俗來說就是在一鍋粥里面找出那些老鼠屎。
本篇文章主要是給大家介紹聚類算法的實(shí)現(xiàn)原理以及聚類算法是如何應(yīng)用在 D2C 設(shè)計(jì)稿生成代碼中。
2.DBSCAN 聚類算法
DBSCAN - 具有噪聲的基于密度的聚類算法。和 K-Means 這種只適合凸樣本集的聚類相比，DBSCAN 既可以凸樣本集，也適用于非凸樣本集。它可以對散亂的樣本基于一定的相似性進(jìn)行分類，即在不確定蔟數(shù)目的情況下，根據(jù)樣本的緊密程度進(jìn)行蔟的劃分。舉個例子：
我們需要把“100、101、123、98、200、203、220”這堆數(shù)據(jù)進(jìn)行聚類。成蔟最小值為 2的話， 此時如果我們設(shè)置的聚類密度閾值為 30。那么“100、101、123、98” 和 “200、203、220”將會分成 2 蔟。當(dāng)聚類密度閾值為 10。那么“100、101、98”、“200、203”、分成 2 個蔟，“123”、“220”則屬于噪聲點(diǎn)(異常數(shù)據(jù))。
2.1 核心思想
DBSCAN 算法主要是找出樣本點(diǎn)中所有的密集區(qū)域，我們稱這些密集區(qū)域?yàn)榫垲愝?。那么不在密集區(qū)域內(nèi)的樣本點(diǎn)，我們稱為噪聲點(diǎn)。所以 DBSCAN 除了能幫你做分類外，也能找出“一鍋粥里面的老鼠屎”。
2.2 算法參數(shù)
參數(shù) | 說明 |
鄰域半徑 Eps： | 指的是每個樣本點(diǎn)的搜索半徑，在搜索半徑內(nèi)掃描到的其他樣本點(diǎn)，我們可以理解為被掃描到的樣本點(diǎn)與中心點(diǎn)是相近的。 |
最小點(diǎn)數(shù)目 minpoints： | 能聚合成簇的最小樣本數(shù)目，可以理解為每個蔟需要的最少樣本數(shù)。在上圖上，我們可以看到紅色、藍(lán)色在半徑 R 內(nèi)均掃描到的樣本點(diǎn)>最小點(diǎn)數(shù)目 minpoints，而黃色僅掃描的數(shù)量比 minpoints 要少。 |
2.3 點(diǎn)的類別
類別 | 說明 |
核心點(diǎn) | 鄰域半徑 Eps 內(nèi)樣本點(diǎn)的數(shù)目 >= 最小點(diǎn)數(shù)目 minpoints 的點(diǎn) |
邊界點(diǎn) | 不屬于核心點(diǎn)但在某個核心點(diǎn)的鄰域內(nèi)的點(diǎn) |
噪聲點(diǎn) | 既不是核心點(diǎn)也不是邊界點(diǎn) |
2.4 點(diǎn)的關(guān)系
關(guān)系 | 說明 |
密度直達(dá) | A 為核心點(diǎn)，B 在 A 的鄰域 Eps 內(nèi)，那么 A 到 B 密度直達(dá)。任何核心點(diǎn)到其鄰域 Eps 內(nèi)的邊界點(diǎn)都是密度直達(dá)。 |
密度可達(dá) | 如果存在核心點(diǎn) C、D、E、F。C 到 D 密度直達(dá)，D 到 F 密度直達(dá)，E 到 F 密度直達(dá)。那么我們可以稱 C 到 F密度可達(dá)。而 F(核心點(diǎn))到 G (邊界點(diǎn))也是密度直達(dá)，C 到 G 也是密度可達(dá)。 |
密度相連 | 如果存在核心點(diǎn)使得樣本點(diǎn) X 跟樣本點(diǎn) Y 都密度可達(dá)，那么我們稱 X 與 Y 密度相連。 |
非密度相連 | 不屬于密度相連的話就是非密度相連，非密度相連的兩個點(diǎn)屬于不同的蔟，或者其中為噪聲點(diǎn)。 |
2.5 算法實(shí)現(xiàn)步驟
由密度可達(dá)關(guān)系導(dǎo)出的最大密度相連的樣本集合，即為我們最終聚類的一個類別，或者說一個簇。在實(shí)現(xiàn)上我們可以分為以下 4 步：
步驟 1：選擇任意一個沒有類別的核心地點(diǎn)作為初始點(diǎn)；
步驟 2：找出這個核心點(diǎn)能夠密度可達(dá)的樣本集合，也就是找出這個核心點(diǎn)鄰域內(nèi)的所有邊界點(diǎn)，這時就可以成為一個聚類蔟；
步驟 3：繼續(xù)找另外一個沒有類別的核心點(diǎn)繼續(xù)重復(fù)步驟 2 的操作；
步驟 4：直到所有的點(diǎn)。
來點(diǎn)比較生動的例子：你可以假設(shè)一群人里面有個做傳銷的人(核心點(diǎn))，要發(fā)展下線，需要先找 N 個人(minPoints)，于是他就在身邊(鄰域)去找人發(fā)展下線，那么下線(邊界點(diǎn))就會繼續(xù)找下線，直到身邊沒人。
3.布局算法與 DBSCAN 的結(jié)合
簡單介紹完 DBSCAN 的算法概念和算法實(shí)現(xiàn)后，我們講一下聚類算法在 Deco 布局算法中的應(yīng)用場景。
布局算法核心其實(shí)就是成組，如何基于設(shè)計(jì)稿每個模塊的位置信息和大小尺寸來判斷是否能組成成組是關(guān)鍵，簡單來說，就是如何準(zhǔn)確的把一堆節(jié)點(diǎn)拿個DIV套住。
如上圖所示，設(shè)計(jì)稿上存在 11 個白色區(qū)塊節(jié)點(diǎn)的節(jié)點(diǎn)，而我們?nèi)庋廴タ?，以每個節(jié)點(diǎn)之間的緊密距離關(guān)系來作為依據(jù)，上半部分和下半部分是分開的。但是這僅限于我們的視覺，那如何讓機(jī)器的視覺也認(rèn)為是分開的呢?我們需要剛剛提到的DBSCAN 聚類算法進(jìn)行蔟的生成，那么我們的目標(biāo)是讓上半部分會形成一個聚類蔟，下半部分也組成一個聚類蔟。
剛剛我們提到 DBSCAN 是點(diǎn)到點(diǎn)之間的歐式距離作為緊密關(guān)系的依據(jù)，那么在節(jié)點(diǎn)上來看的話，我們轉(zhuǎn)變下思路，改為 區(qū)塊與區(qū)塊之間的最短距離作為緊密關(guān)系的依據(jù) 。
3.1 點(diǎn)狀距離 > 區(qū)塊距離
其實(shí)獲取區(qū)塊之間的最短距離比較簡單，有三種情況：
第一種：兩個區(qū)塊相交，那么距離其實(shí)就是 0 了；
第二種：A 區(qū)塊與 B 區(qū)塊是在其上/下/左/右的，那么只需要獲取兩者之間的間距位置即可；
第三種：A 區(qū)塊與 B 區(qū)塊是在其左上/左下/右上/右下的，那么采用勾股定理獲取下兩者相對的頂點(diǎn)之間斜線的距離即可。
改造之后的效果就是下圖的樣子，我們根據(jù)聚類算法的實(shí)現(xiàn)，最終就可以把上下 2 個分成 2 個聚類蔟：
3.2 鄰域半徑推導(dǎo)
DBSCAN 聚類算法除了輸入中，有樣本數(shù)據(jù)集、數(shù)據(jù)對象數(shù)目閾值 MinPoints、鄰域半徑 Eps，那么帶布局算法中，鄰域半徑 Eps到底設(shè)多少才是合適的值呢?總不能是個固定值吧。有些模塊間距的整體大一點(diǎn)，有些間距小一點(diǎn)，我們在實(shí)際布局對區(qū)塊做聚合的時候需要求出這個動態(tài)的鄰域半徑 Eps。
第一步：我們對樣本數(shù)據(jù)集之間的距離先做一個統(tǒng)計(jì)，先求出這 5 個區(qū)塊它們之間的最短距離。
模塊 1 | 模塊 2 | 模塊 3 | 模塊 4 | 模塊 5 | |
模塊 1 | - | 5 | 5 | 7 | 210 |
模塊 2 | 5 | - | 7 | 5 | 100 |
模塊 3 | 5 | 7 | - | 5 | 214 |
模塊 4 | 7 | 5 | 5 | - | 107 |
模塊 5 | 210 | 100 | 214 | 107 | - |
第二步：然后我們根據(jù)距離矩陣表，我們可以得出每個模塊與其最相近模塊之間的最短距離。
模塊 | 模塊 1 | 模塊 2 | 模塊 3 | 模塊 4 | 模塊 5 |
最短距離 | 5 | 5 | 5 | 5 | 100 |
第三步：在這堆數(shù)據(jù)中，我們需要提取占比更多，比較有效的數(shù)據(jù)作為我們的 Eps 值，剔除掉一些干擾項(xiàng)。
我們根據(jù)標(biāo)準(zhǔn)差的計(jì)算公式，我們?nèi)?1 倍標(biāo)準(zhǔn)差作為過濾項(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 作為我們在這個樣本集的鄰域半徑 Eps。
3.3 算法優(yōu)化
基于上述的算法改造，其實(shí)我們已經(jīng)完成比較靠譜的在布局上實(shí)現(xiàn)模塊聚類以及拆分。那么在實(shí)際算法的運(yùn)用上，還會針對鄰域半徑 Eps 動態(tài)生成做一個在布局實(shí)際場景的優(yōu)化：
比如像下面這種布局：水平間距為 5、垂直間距為 10：
那么如果根據(jù)最短距離標(biāo)準(zhǔn)差的形式，那其實(shí) 8 個模塊它們的最短距離都是 5，最終算出來 Eps 也是 5，那么很有可能就會把上下兩行分割開了。
所以我們在實(shí)際運(yùn)用上，在生成標(biāo)準(zhǔn)差樣本過程中，根據(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é)約了開發(fā)成本，為輸出更多的多端頁面提供了有力的支持，也為業(yè)務(wù)降本增效帶來了巨大動力。
在過去的一年里，Deco 已在京東的兩次大促中成功落地，在個性化活動會場的搭建中，研發(fā)效率提升達(dá)到了 48%。
感興趣的同學(xué)可以移步 Deco官網(wǎng)[1] 進(jìn)行體驗(yàn)。另外也給大家附上 Deco 體驗(yàn)的保姆級教程。
5.總結(jié)
本篇文章主要介紹了 DBSCAN 的實(shí)現(xiàn)原理，在介紹中并有給出具體的代碼實(shí)現(xiàn)，這塊大家感興趣的話網(wǎng)上也有很多具體的代碼實(shí)現(xiàn)邏輯。目的主要是給大家講聚類算法的實(shí)現(xiàn)思路，以及在聚類算法在 D2C 上布局上的的應(yīng)用落地。除了 DBSCAN 這種基于密度聚類算法外，其實(shí)還有很多算法也可在 D2C 布局算法上等待我們的挖掘。
