學點高端技術：基于密度的聚類算法——FDBSCAN算法

機器學習、人工智能各類KNN算法層出不窮，DBSCAN具有強代表性，它是一個基于密度的聚類算法，最大的優點是能夠把高密度區域劃分為簇，能夠在高噪聲的條件下實現對目標的精準識別，但該算法當前已遠不能滿足人們對于高效率、高精準度的算法要求，由此FDBSCAN算法應運而生。

01

FDBSCAN聚類算法在KD-樹的加持下，時間復雜度達到了O(nlogn)，目標識別效率已指數級別上升。

02

Kd-樹：它是一種樹形結構，主要應用于多維空間關鍵數據的搜索。由于他的增加、刪除、查詢時間復雜度都是O(logn)，所以才造就了FDBSCAN算法的高效率。

想必大家對于樹形結構也不是特別陌生，但是對于四維及以上的樹形結構，就難以體現其具體的結構了。kd-樹的三維立體空間如下圖所示：

03

FDBSCAN算法的高效就體現在它使用了KD樹作為自己遍歷數據的工具，通過樹形結構，能夠最大限度的提高遍歷效率。在算法執行之前，首先對待處理數據創建Kd-樹，使用KD樹自有的空間搜索算法來進行數據劃分。可以看到整個數據劃分流程圖：

04

下面對FDBSCAN算法偽代碼進行展示：

FDBSCAN算法偽代碼：

DBSCAN(D, eps, MinPts)

C = 0 //類別標示

for each unvisited point P in dataset D //遍歷

mark P as visited //已經訪問

NeighborPts = regionQuery(P, eps) //計算這個點的鄰域

if sizeof(NeighborPts) < MinPts //不能作為核心點

mark P as NOISE //標記為噪音數據

else //作為核心點，根據該點創建一個類別

C = next cluster

expandCluster(P, NeighborPts, C, eps, MinPts) //根據該核心店擴展類別

expandCluster(P, NeighborPts, C, eps, MinPts)

add P to cluster C //擴展類別，核心店先加入

for each point P' in NeighborPts //然后針對核心店鄰域內的點，如果該點沒有被訪問

if P' is not visited

mark P' as visited //進行訪問

NeighborPts' = regionQuery(P', eps) //如果該點為核心點，則擴充該類別

if sizeof(NeighborPts') >= MinPts

NeighborPts = NeighborPts joined with NeighborPts'

if P' is not yet member of any cluster //如果鄰域內點不是核心點，并且無類別，比如噪音數據，則加入此類別

add P' to cluster C

regionQuery(P, eps) //計算鄰域

return all points within P's eps-neighborhood

kdtree (list of points pointList, int depth) {

var tree_node node;

node.location := median;

node.leftChild := kdtree(points in pointList before median, depth+1);

node.rightChild := kdtree(points in pointList after median, depth+1);

return node;

05

機器學習、深度學習、圖像識別、人工智能、大數據、區塊鏈、互聯網+等各種新興技術層出不窮，人們對于算法的效率、精度要求也是越來越嚴格。各位大佬們，傳統DBSCAN聚類算法對于一個高分辨率，數以千百萬級的像素點的圖像來說，是遠遠不夠的，那就讓FDBSCAN算法來助你一臂之力吧！

最后：在我的V ：atstudy-js，可以免費領取一份10G軟件測試工程師面試寶典文檔資料。以及相對應的視頻學習教程免費分享！其中包括了有基礎知識、Linux必備、Shell、互聯網程序原理、Mysql數據庫、抓包工具專題、接口測試工具、測試進階-Python編程、Web自動化測試、APP自動化測試、接口自動化測試、測試高級持續集成、測試架構開發測試框架、性能測試、安全測試等。