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