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

七、密度聚類概述

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

分析

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

八、DBSCAN算法

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

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

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

DBSCAN算法基本概念 (一) ：

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

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

MinPts定義核心點(diǎn)時的閾值，也簡記為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)對應(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)對應(yīng)稠密區(qū)域邊緣的點(diǎn)：

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

分析 - 概念二

DBSCAN算法基本概念 (三) ：

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

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

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

分析 - 概念三

DBSCAN算法基本概念 (四) ：

簇(cluster)：一個基于密度的簇是最大的密度相連對象的集合C；滿足以下兩個條件：
1、Maximality：若x屬于C，而且y是從x密度可達(dá)的，那么y也屬于C。
2、Connectivity：若x屬于C，y也屬于C，則x和y是密度相連。

九、DBSCAN算法流程

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

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

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

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

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

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

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

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

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

M=4，形成了2個聚簇分類

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

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

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

MDCA概念 (一) ：

最大密度點(diǎn)：

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

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

分析 - MDCA概念一

MDCA概念 (二) ：

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

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

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

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

一、將數(shù)據(jù)集劃分為基本簇。
1、對數(shù)據(jù)集X選取最大密度點(diǎn)P_max，形成以最大密度點(diǎn)為核心的新簇C_i，按照距離排序計(jì)算出序列S_pmax,對序列的前M個樣本數(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₀。

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

三、處理剩余節(jié)點(diǎn)，歸入最近的簇。
最常用、最簡單的方式是：將剩余樣本對象歸入到最近的簇。

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

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