09 聚類算法 - 層次聚類
10 聚類算法 - 代碼案例四 - 層次聚類(BIRCH)算法參數(shù)比較

七铛纬、密度聚類概述

1、密度聚類方法的指導(dǎo)思想: 只要樣本點(diǎn)的密度大于某個(gè)閾值唬滑，則將該樣本添加到最近的簇中告唆。
2棺弊、這類算法可以克服基于距離的算法只能發(fā)現(xiàn)凸聚類的缺點(diǎn)，可以發(fā)現(xiàn)任意形狀的聚類擒悬，而且對(duì)噪聲數(shù)據(jù)不敏感模她。
3、計(jì)算復(fù)雜度高懂牧，計(jì)算量大侈净。

分析

常用算法：
1、具有噪聲的基于密度的聚類方法 - DBSCAN
2僧凤、密度最大值算法 - MDCA

八畜侦、DBSCAN算法

DBSCAN(Density-Based Spatial Clustering of Applications with Noise) - 具有噪聲的基于密度的聚類方法

一個(gè)比較有代表性的基于密度的聚類算法，相比于基于劃分的聚類方法和層次聚類方法躯保，DBSCAN算法將簇定義為密度相連的點(diǎn)的最大集合旋膳，能夠?qū)⒆銐蚋呙芏鹊膮^(qū)域劃分為簇，并且在具有噪聲的空間數(shù)據(jù)商能夠發(fā)現(xiàn)任意形狀的簇途事。

DBSCAN算法的核心思想是：用一個(gè)點(diǎn)的ε鄰域內(nèi)的鄰居點(diǎn)數(shù)衡量該點(diǎn)所在空間的密度验懊，該算法可以找出形狀不規(guī)則的cluster，而且聚類的時(shí)候事先不需要給定cluster的數(shù)量尸变。

DBSCAN算法基本概念 (一) ：

ε鄰域(ε neighborhood义图，也稱為Eps)：給定對(duì)象在半徑ε內(nèi)的區(qū)域

密度(density)：ε鄰域中x的密度，是一個(gè)整數(shù)值召烂，依賴于半徑ε

MinPts定義核心點(diǎn)時(shí)的閾值歌溉，也簡記為M

核心點(diǎn)(core point)：如果p(x)>=M,那么稱x為X的核心點(diǎn)；記由X中所有核心點(diǎn)構(gòu)成的集合為Xc骑晶，并記Xnc=X\Xc表示由X中所有非核心點(diǎn)構(gòu)成的集合痛垛。直白來講，核心點(diǎn)對(duì)應(yīng)于稠密區(qū)域內(nèi)部的點(diǎn)桶蛔。

DBSCAN算法基本概念 (二) ：

邊界點(diǎn)(border point): 如果非核心點(diǎn)x的ε鄰域中存在核心點(diǎn)匙头，那么認(rèn)為x為X的邊界點(diǎn)。由X中所有的邊界點(diǎn)構(gòu)成的集合為Xbd仔雷。直白來將蹂析，邊界點(diǎn)對(duì)應(yīng)稠密區(qū)域邊緣的點(diǎn)：

噪音點(diǎn)(noise point)：集合中除了邊界點(diǎn)和核心點(diǎn)之外的點(diǎn)都是噪音點(diǎn)，所有噪音點(diǎn)組成的集合叫做Xnoi碟婆；直白來講电抚，噪音點(diǎn)對(duì)應(yīng)稀疏區(qū)域的點(diǎn)。

分析 - 概念二

DBSCAN算法基本概念 (三) ：

直接密度可達(dá)(directly density-reachable)：給定一個(gè)對(duì)象集合X竖共，如果y是在x的ε鄰域內(nèi)蝙叛，而且x是一個(gè)核心對(duì)象，可以說對(duì)象y從對(duì)象x出發(fā)是直接密度可達(dá)的公给。

密度可達(dá)(density-reachable)：如果存在一個(gè)對(duì)象鏈p1,p2,..pm,如果滿足pi+1是從pi直接密度可達(dá)的借帘，那么稱pm是從p1密度可達(dá)的蜘渣。

密度相連(density-connected)：在集合X中，如果存在一個(gè)對(duì)象o肺然，使得對(duì)象x和y是從o關(guān)于ε和m密度可達(dá)的蔫缸，那么對(duì)象x和y是關(guān)于ε和m密度相連的。

分析 - 概念三

DBSCAN算法基本概念 (四) ：

簇(cluster)：一個(gè)基于密度的簇是最大的密度相連對(duì)象的集合C际起；滿足以下兩個(gè)條件：
1拾碌、Maximality：若x屬于C，而且y是從x密度可達(dá)的街望，那么y也屬于C倦沧。
2、Connectivity：若x屬于C它匕，y也屬于C展融，則x和y是密度相連。

九豫柬、DBSCAN算法流程

算法流程：
1告希、如果一個(gè)點(diǎn)x的ε鄰域包含多余m個(gè)對(duì)象，則創(chuàng)建一個(gè)x作為核心對(duì)象的新簇烧给；
2燕偶、尋找并合并核心對(duì)象直接密度可達(dá)的對(duì)象；
3础嫡、沒有新點(diǎn)可以更新簇的時(shí)候指么，算法結(jié)束。

算法特征描述:
1榴鼎、每個(gè)簇至少包含一個(gè)核心對(duì)象伯诬。
2、非核心對(duì)象可以是簇的一部分巫财，構(gòu)成簇的邊緣盗似。
3、包含過少對(duì)象的簇被認(rèn)為是噪聲平项。

看上圖赫舒，順便回顧知識(shí)點(diǎn)：
A->B: 密度可達(dá)。
B->A: 密度相連闽瓢。(B->A走不過去)
A->A附近的點(diǎn)：直接密度可達(dá)接癌。
所以只要密度可達(dá)，必然密度相連扣讼。但是密度相連不一定能推出密度可達(dá)缺猛。

上圖中，只要A和A附近的點(diǎn)直接密度可達(dá)，就可以歸為一類枯夜。所以紅點(diǎn)之間可以形成一個(gè)簇弯汰。
此外艰山，B和C點(diǎn)都與A點(diǎn)密度相連湖雹，所以能可以歸入這個(gè)簇。

所以構(gòu)建算法的思路是：先找核心點(diǎn)曙搬，然后再把邊界找到摔吏。將核心點(diǎn)和邊界點(diǎn)歸入一個(gè)簇。

DBSCAN算法優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：
1纵装、不需要事先給定cluster的數(shù)目征讲。
2、可以發(fā)現(xiàn)任意形狀的cluster橡娄。
3诗箍、能夠找出數(shù)據(jù)中的噪音，且對(duì)噪音不敏感挽唉。
4滤祖、算法只需要兩個(gè)輸入?yún)?shù)。
5瓶籽、聚類結(jié)果幾乎不依賴節(jié)點(diǎn)的遍歷順序匠童。

缺點(diǎn)：
1、DBSCAN算法聚類效果依賴距離公式的選取塑顺，最常用的距離公式為歐幾里得距離汤求。但是對(duì)于高維數(shù)據(jù)，由于維數(shù)太多严拒，距離的度量已變得不是那么重要扬绪。維度災(zāi)難 02 聚類算法 - 相似度距離公式、維度災(zāi)難

2裤唠、DBSCAN算法不適合數(shù)據(jù)集中密度差異很小的情況勒奇。

M=4，形成了2個(gè)聚簇分類

十巧骚、密度最大值聚類算法(MDCA)

MDCA(Maximum Density Clustering Application)算法基于密度的思想引入劃分聚類中赊颠，使用密度而不是初始點(diǎn)作為考察簇歸屬情況的依據(jù)，能夠自動(dòng)確定簇?cái)?shù)量并發(fā)現(xiàn)任意形狀的簇劈彪；另外MDCA一般不保留噪聲竣蹦，因此也避免了閾值選擇不當(dāng)情況下造成的對(duì)象丟棄情況。

MDCA算法的基本思路是尋找最高密度的對(duì)象和它所在的稠密區(qū)域沧奴；MDCA算法在原理上來講痘括，和密度的定義沒有關(guān)系，采用任意一種密度定義公式均可，一般情況下采用DBSCAN算法中的密度定義方式纲菌。

MDCA概念 (一) ：

最大密度點(diǎn)：

有序序列: 根據(jù)所有對(duì)象與pmax的距離對(duì)數(shù)據(jù)重新排序：

密度閾值density₀挠日；當(dāng)節(jié)點(diǎn)的密度值大于密度閾值的時(shí)候，認(rèn)為該節(jié)點(diǎn)屬于一個(gè)比較固定的簇翰舌，在第一次構(gòu)建基本簇的時(shí)候嚣潜，就將這些節(jié)點(diǎn)添加到對(duì)應(yīng)簇中，如果小于這個(gè)值的時(shí)候椅贱，暫時(shí)認(rèn)為該節(jié)點(diǎn)為噪聲節(jié)懂算。

分析 - MDCA概念一

MDCA概念 (二) ：

簇間距離：對(duì)于兩個(gè)簇C1和C2之間的距離，采用兩個(gè)簇中最近兩個(gè)節(jié)點(diǎn)之間的距離作為簇間距離庇麦。

聚簇距離閾值dist₀：當(dāng)兩個(gè)簇的簇間距離小于給定閾值的時(shí)候计技，這兩個(gè)簇的結(jié)果數(shù)據(jù)會(huì)進(jìn)行合并操作。

M值：初始簇中最多數(shù)據(jù)樣本個(gè)數(shù)山橄。

MDCA算法聚類過程步驟如下：

一垮媒、將數(shù)據(jù)集劃分為基本簇。
1航棱、對(duì)數(shù)據(jù)集X選取最大密度點(diǎn)P_max睡雇，形成以最大密度點(diǎn)為核心的新簇C_i，按照距離排序計(jì)算出序列S_pmax,對(duì)序列的前M個(gè)樣本數(shù)據(jù)進(jìn)行循環(huán)判斷丧诺，如果節(jié)點(diǎn)的密度大于等于density₀入桂，那么將當(dāng)前節(jié)點(diǎn)添加C_i中；
2驳阎、循環(huán)處理剩下的數(shù)據(jù)集X抗愁，選擇最大密度點(diǎn)P_max，并構(gòu)建基本簇C_i+1呵晚，直到X中剩余的樣本數(shù)據(jù)的密度均小于density₀蜘腌。

二、使用凝聚層次聚類的思想饵隙，合并較近的基本簇撮珠，得到最終的簇劃分。
在所有簇中選擇距離最近的兩個(gè)簇進(jìn)行合并金矛，合并要求是：簇間距小于等于dist₀,如果所有簇中沒有簇間距小于dist₀的時(shí)候芯急，結(jié)束合并操作。

三驶俊、處理剩余節(jié)點(diǎn)娶耍，歸入最近的簇。
最常用饼酿、最簡單的方式是：將剩余樣本對(duì)象歸入到最近的簇榕酒。

分析 - MDCA算法聚類過程步驟

12 聚類算法 - 代碼案例五 - 密度聚類(DBSCAN)算法案例