第八章密度聚類法主要內(nèi)容密度聚類法基于密度的聚類DBSCAN算法(DensityBasedSpaicalClusteringofApplicationswithNoise)OPTICS算法OrderingPointsToIdenfifytheClusteringStructure問題：數(shù)據(jù)往往存在著密度不均勻的情況，有的區(qū)域稠密，有的區(qū)域密度很低。是否可以利用空間中數(shù)據(jù)點的密集程度來實現(xiàn)聚類？8.1基于密度的聚類基于密度的聚類的基本思想：通過計算樣本密度及樣本之間的連通性來進行聚類。其前提假設(shè)為聚類內(nèi)部的密度高于類外的密度，且類內(nèi)的噪聲密度低于所有類別外的密度。問題：數(shù)據(jù)往往存在著密度不均勻的情況，K-means算法存在何種問題？8.1基于密度的聚類

8.1基于密度的聚類基本概念：（2）直接密度可達；（3）密度可達；

8.2DBSCAN算法基本概念：（4）密度相連；（5）聚類；

8.2DBSCAN算法

分析三種不同數(shù)據(jù)分布情況下的DBSCAN算法過程。8.2DBSCAN算法8.2.1算法基本流程（1）

分析DBSCAN聚類過程8.2DBSCAN算法8.2.1算法基本流程（2）算法討論問題：一個聚類產(chǎn)生的開始點為？噪聲點符合什么條件？x鄰域中的哪些點被認為和x同類？Queue_list存儲了哪些點？為何要對搜索Queue_list的鄰域？3.2.3是否是一個遞歸過程？DBSCAN受哪些因素影響？鄰域搜索速度如何提升？算法復(fù)雜度如何計算？是否存在某個數(shù)據(jù)點同時可能同時屬于兩個相鄰類？訪問數(shù)據(jù)點的順序是否影響分類？

8.2DBSCAN算法

8.3OPTICS聚類問題1：聚類的任務(wù)除了將數(shù)據(jù)分為不同的組別，分析分類結(jié)果的數(shù)據(jù)特性，如何生成一種基于密度的聚類結(jié)構(gòu)所表征的有序的數(shù)據(jù)排序？問題2：DBSCAN如何處理聚類時數(shù)據(jù)密度發(fā)生變化的情況？

8.3OPTICS聚類

8.3OPTICS聚類算法流程

分析OPTICS算法過程8.3OPTICS聚類

分析種子列表更新過程8.3OPTICS聚類

8.3OPTICS聚類8.3.2識別聚類結(jié)構(gòu)OPTICS算法的結(jié)果表示為如下形式：設(shè)DB是一個包含n個數(shù)據(jù)點的集合。OPTICS算法生成點的一個排序o:{1…n}→DB，以及相應(yīng)的可達距離r:{1…n}→R

0。問題：如何分析數(shù)據(jù)的結(jié)構(gòu)？是否存在子集？（1）可達區(qū)域和參數(shù)-18.3OPTICS聚類（1）可達區(qū)域和參數(shù)-2

8.3OPTICS聚類（2）從聚類序列中生成聚類結(jié)構(gòu)結(jié)合OPTICS對數(shù)據(jù)點的排序方式可知，聚類在可達性圖中表現(xiàn)為凹陷形式。第一個以不那么陡峭的點A開始，在陡峭的點B結(jié)束，而第三個以非常陡峭的C開始、陡峭的D結(jié)束。為了捕捉不同程度的陡峭度。如何定義陡度？8.3OPTICS聚類定義：陡度點，陡度區(qū)

8.3OPTICS聚類

聚類分析條件(1)-(2)指出聚類開始于

陡度下降區(qū)D，終止于陡度上升區(qū)域U；條件3(a)說明每個聚類至少包含MinPts個點；條件3(b)指出聚類中所有點的可達距離必須比D中第一個點和U區(qū)之后第一個點的可達距離小%；條件(4)定義了起點和終止點。

8.3OPTICS聚類如何聚類？

基于上述定義，通過遍歷可達性圖，查找符合陡升和陡降條件的區(qū)間，將這些區(qū)間鏈接起來形成聚類，并為這些聚類建立父子關(guān)系來表現(xiàn)層次結(jié)構(gòu)。改進方法：基于陡度下降區(qū)檢索的聚類算法（數(shù)據(jù)集，數(shù)據(jù)個數(shù)n）While（索引index<n）IF（一個新的陡度向下區(qū)開始于index）

將該區(qū)加入陡度下降區(qū)域集合SDASet，取其右側(cè)數(shù)據(jù)點繼續(xù)執(zhí)行；ELSEIF（一個新的陡度向上區(qū)開始于index）將該區(qū)與SDASet中的每一個陡度向下區(qū)合并，檢查合并結(jié)果是否滿足聚類條件，如果滿足，則將其保存，取該陡度區(qū)的右側(cè)對象繼續(xù)執(zhí)行；ELSEindex+1分析：（1）一個新的陡度向下區(qū)開始于index，意味著什么？（2）一個新的陡度向上區(qū)開始于index，意味著什么？（3）為何能形成聚類？實際上許多組合并不能形成真正的聚類，因此采用兩種算法優(yōu)化計算過程：一是去除掉不可能形成真正聚類的組合，二是去除對所有點的循環(huán)。8.3OPTICS聚類聚類抽取算法（數(shù)據(jù)集）1.設(shè)陡度下降區(qū)域集合SDASets=

2.設(shè)聚類集合ClusterSets=

3.設(shè)index=0,mib=04.WHILE(index<n)4.1mib=max(mib,r(index))4.2IF(index為陡度下降區(qū)域D的起始點)4.2.1更新mib-values并過濾陡度下降區(qū)域集合SDASets

4.2.2設(shè)置D.mib=0

4.2.3增加D到SDASets

4.2.4令index=D的終點+1，mib=r(index)4.3ELSE(index為陡度上升區(qū)域U的起始點)4.3.1更新mib-values并過濾陡度下降區(qū)域集合SDASets

4.3.2令index=U的終點+1；mib=r(index)

4.3.3對每一個集合SDASets中的下降區(qū)域D：IF(D和U的組合是有效的，且同時滿足聚類條件)

計算[s,e]并將當前聚類加入聚類集合ClusterSets4.4ELSEindex=index+15.返回聚類集合ClusterSets算法討論Min_values是記錄了SDASets中每個下降區(qū)域D與當前索引點的中間最大值、中間最小值，以及SDASets中最后一個陡度區(qū)終止點與當前索引之間的（全局）中間最大值、（全局）最小值；

8.3OPTICS聚類

OPTICS優(yōu)勢：1.OPTICS適用于任何類型的數(shù)據(jù)集，無論是低維還是高維，稀疏或密集。2.對數(shù)據(jù)分布的適應(yīng)性：通過自動適應(yīng)數(shù)據(jù)的變化密度，OPTICS可以識別不同規(guī)模和形狀的聚類；3.可擴展性：通過使用高效的索引結(jié)構(gòu)和優(yōu)化的算法設(shè)計，OPTICS能夠處理非常大的數(shù)據(jù)集。本章總結(jié)DBSCAN、OPTICS算法的核心概念、實現(xiàn)細節(jié)、優(yōu)勢。DBSCAN是一種參數(shù)敏感的算法，需要用戶事先知道數(shù)據(jù)的密度分布，并手動調(diào)整參數(shù)來適應(yīng)不同的數(shù)據(jù)集。OPTIC