機(jī)器學(xué)習(xí)、人工智能各類KNN算法層出不窮，DBSCAN具有強(qiáng)代表性，它是一個(gè)基于密度的聚類算法，最大的優(yōu)點(diǎn)是能夠把高密度區(qū)域劃分為簇，能夠在高噪聲的條件下實(shí)現(xiàn)對(duì)目標(biāo)的精準(zhǔn)識(shí)別，但該算法當(dāng)前已遠(yuǎn)不能滿足人們對(duì)于高效率、高精準(zhǔn)度的算法要求，由此FDBSCAN算法應(yīng)運(yùn)而生。

01

FDBSCAN聚類算法在KD-樹的加持下，時(shí)間復(fù)雜度達(dá)到了O(nlogn)，目標(biāo)識(shí)別效率已指數(shù)級(jí)別上升。

02

Kd-樹：它是一種樹形結(jié)構(gòu)，主要應(yīng)用于多維空間關(guān)鍵數(shù)據(jù)的搜索。由于他的增加、刪除、查詢時(shí)間復(fù)雜度都是O(logn)，所以才造就了FDBSCAN算法的高效率。

想必大家對(duì)于樹形結(jié)構(gòu)也不是特別陌生，但是對(duì)于四維及以上的樹形結(jié)構(gòu)，就難以體現(xiàn)其具體的結(jié)構(gòu)了。kd-樹的三維立體空間如下圖所示：

03

FDBSCAN算法的高效就體現(xiàn)在它使用了KD樹作為自己遍歷數(shù)據(jù)的工具，通過樹形結(jié)構(gòu)，能夠最大限度的提高遍歷效率。在算法執(zhí)行之前，首先對(duì)待處理數(shù)據(jù)創(chuàng)建Kd-樹，使用KD樹自有的空間搜索算法來(lái)進(jìn)行數(shù)據(jù)劃分。可以看到整個(gè)數(shù)據(jù)劃分流程圖：

04

下面對(duì)FDBSCAN算法偽代碼進(jìn)行展示：

FDBSCAN算法偽代碼：

DBSCAN(D, eps, MinPts)

C = 0 //類別標(biāo)示

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

mark P as visited //已經(jīng)訪問

NeighborPts = regionQuery(P, eps) //計(jì)算這個(gè)點(diǎn)的鄰域

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

mark P as NOISE //標(biāo)記為噪音數(shù)據(jù)

else //作為核心點(diǎn)，根據(jù)該點(diǎn)創(chuàng)建一個(gè)類別

C = next cluster

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

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

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

for each point P' in NeighborPts //然后針對(duì)核心店鄰域內(nèi)的點(diǎn)，如果該點(diǎn)沒有被訪問

if P' is not visited

mark P' as visited //進(jìn)行訪問

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

if sizeof(NeighborPts') >= MinPts

NeighborPts = NeighborPts joined with NeighborPts'

if P' is not yet member of any cluster //如果鄰域內(nèi)點(diǎn)不是核心點(diǎn)，并且無(wú)類別，比如噪音數(shù)據(jù)，則加入此類別

add P' to cluster C

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

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

機(jī)器學(xué)習(xí)、深度學(xué)習(xí)、圖像識(shí)別、人工智能、大數(shù)據(jù)、區(qū)塊鏈、互聯(lián)網(wǎng)+等各種新興技術(shù)層出不窮，人們對(duì)于算法的效率、精度要求也是越來(lái)越嚴(yán)格。各位大佬們，傳統(tǒng)DBSCAN聚類算法對(duì)于一個(gè)高分辨率，數(shù)以千百萬(wàn)級(jí)的像素點(diǎn)的圖像來(lái)說(shuō)，是遠(yuǎn)遠(yuǎn)不夠的，那就讓FDBSCAN算法來(lái)助你一臂之力吧！

最后：在我的V ：atstudy-js，可以免費(fèi)領(lǐng)取一份10G軟件測(cè)試工程師面試寶典文檔資料。以及相對(duì)應(yīng)的視頻學(xué)習(xí)教程免費(fèi)分享！其中包括了有基礎(chǔ)知識(shí)、Linux必備、Shell、互聯(lián)網(wǎng)程序原理、Mysql數(shù)據(jù)庫(kù)、抓包工具專題、接口測(cè)試工具、測(cè)試進(jìn)階-Python編程、Web自動(dòng)化測(cè)試、APP自動(dòng)化測(cè)試、接口自動(dòng)化測(cè)試、測(cè)試高級(jí)持續(xù)集成、測(cè)試架構(gòu)開發(fā)測(cè)試框架、性能測(cè)試、安全測(cè)試等。