聚類算法的維度分析.pdf

1、本文主要研究不同維度條件下聚類分析的特點(diǎn)、需求以及相應(yīng)的對(duì)策和解決方法。針對(duì)低維度、高維度全空間和高維度子空間聚類這三個(gè)問(wèn)題分別提出了新的算法。 在低維度聚類方面，提出了GDMS聚類算法。算法的主要貢獻(xiàn)是：1、提出了探針窗口過(guò)濾法來(lái)檢測(cè)數(shù)據(jù)的分布特性，通過(guò)選取不同的濾波函數(shù)得到不同密度、不同屬性的聚類簇，通過(guò)選擇探針的不同運(yùn)動(dòng)方式，實(shí)現(xiàn)精度和效率的統(tǒng)一。2、提出了一個(gè)新的數(shù)學(xué)形態(tài)學(xué)算子來(lái)提取聚類簇，算子的精度優(yōu)于以往使用的開(kāi)、閉

2、算子。3、將尺度空間理論和形態(tài)學(xué)相結(jié)合，聚類結(jié)果是一個(gè)多尺度的、層次化的結(jié)構(gòu)。4、算法支持含障礙物的聚類。算法的特點(diǎn)是：計(jì)算復(fù)雜度與數(shù)據(jù)量成線性關(guān)系；能夠發(fā)現(xiàn)任意形狀的聚類；對(duì)噪聲不敏感；算法對(duì)網(wǎng)格尺寸有一定的適應(yīng)性；能夠區(qū)分不同密度的聚類簇；能夠區(qū)分特定屬性聚類簇；層次化的聚類結(jié)果有利于用戶的理解、解釋。 在高維度全空間聚類方面，提出了MDCLUS、IMDCLUS和PMDCLUS算法以提高聚類速度。1、采用蒙特卡絡(luò)法獲取核心對(duì)

3、象，降低了聚類的運(yùn)算量。定量地給出了抽樣率的最小估計(jì)值，以避免小聚類簇的丟失和大聚類簇的斷裂。提出了標(biāo)簽散列法合并聚類簇，合并的計(jì)算量與數(shù)據(jù)量成線性關(guān)系。2、實(shí)現(xiàn)了增量聚類。3、實(shí)現(xiàn)了分布式并行化處理。算法的特點(diǎn)是：能夠發(fā)現(xiàn)任意形狀的聚類簇：對(duì)噪聲不敏感；與DBSCAN算法相比速度明顯提高：運(yùn)算量與維度成線性關(guān)系；能夠在局域網(wǎng)中的多臺(tái)計(jì)算機(jī)上以分布式方式同時(shí)聚類；支持增量聚類，速度相對(duì)于重新聚類有大幅度提升。 在高維度子空間聚類

4、方面，提出了活躍空間和活躍網(wǎng)格的算法。主要貢獻(xiàn)有：1、證明了聚類簇區(qū)域的密度、連通性、覆蓋度都具有向下封閉性。2、提出了自上而下的搜索方法。3、提出了基于活躍軸數(shù)量的噪聲過(guò)濾法。4、在網(wǎng)格大小固定的基礎(chǔ)上擴(kuò)展為網(wǎng)格大小自適應(yīng)。5、實(shí)現(xiàn)了分布式的并行化聚類。6、提出了以層次化的樹(shù)形結(jié)構(gòu)組織聚類子空間和聚類簇的方法。算法的主要特點(diǎn)有：既能發(fā)現(xiàn)全空間聚類簇也能發(fā)現(xiàn)子空間聚類簇；算法的計(jì)算量與數(shù)據(jù)對(duì)象個(gè)數(shù)、數(shù)據(jù)空間維度數(shù)以及聚類簇維度數(shù)分別近似