面向不確定數(shù)據(jù)的近似骨架啟發(fā)式聚類(lèi)算法.pdf

1、不確定數(shù)據(jù)聚類(lèi)是傳統(tǒng)數(shù)據(jù)挖掘的擴(kuò)展，具有廣泛的應(yīng)用背景和研究?jī)r(jià)值，受到研究者們廣泛的關(guān)注。不確定數(shù)據(jù)聚類(lèi)問(wèn)題屬于典型的NP難解問(wèn)題，并表現(xiàn)出了典型的NP難解問(wèn)題的特點(diǎn)。通常很難在多項(xiàng)式時(shí)間內(nèi)獲得NP難解問(wèn)題的全局最優(yōu)解，研究者們經(jīng)常把聚類(lèi)問(wèn)題描述成組合優(yōu)化問(wèn)題，并設(shè)計(jì)啟發(fā)式聚類(lèi)算法對(duì)不確定數(shù)據(jù)聚類(lèi)進(jìn)行求解?，F(xiàn)有的啟發(fā)式不確定數(shù)據(jù)聚類(lèi)算法中，UK-means和UK-Med oids算法都屬于基于切割不確定數(shù)據(jù)聚類(lèi)算法，它們具有容易理解和實(shí)

2、現(xiàn)簡(jiǎn)單等特點(diǎn)，得到廣泛的關(guān)注和應(yīng)用，但同時(shí)它們也具有對(duì)初始解敏感的缺點(diǎn)，這嚴(yán)重影響了聚類(lèi)質(zhì)量。為了解決基于切割的不確定數(shù)據(jù)算法對(duì)初始解敏感的問(wèn)題，本文深入研究了不確定數(shù)據(jù)聚類(lèi)問(wèn)題表現(xiàn)出的NP難解性質(zhì)，分析了該問(wèn)題的解空間的特征，并在近似骨架理論的基礎(chǔ)上，提出了一種近似骨架啟發(fā)式聚類(lèi)算法APPGCU(APProximate backbone Guided heuristic Clustering algorithm for Uncerta

3、indata)。該算法流程如下:首先對(duì)原不確定數(shù)據(jù)集完成M次采樣，在采樣后的規(guī)模較小的M個(gè)不確定數(shù)據(jù)集上分別執(zhí)行隨機(jī)初始簇心的UK-Medoids算法得到M個(gè)局部最優(yōu)解;然后通過(guò)對(duì)M個(gè)局部最優(yōu)解求交集得到近似骨架，并從中提取出初始簇心;最后從初始簇心開(kāi)始，使用UK-Medoids算法啟發(fā)式搜索出聚類(lèi)結(jié)果。該算法充分利用了近似骨架在啟發(fā)式算法設(shè)計(jì)中表現(xiàn)出的優(yōu)異性能，根據(jù)不確定數(shù)據(jù)聚類(lèi)的特點(diǎn)設(shè)計(jì)了高效聚類(lèi)算法。在充足的仿真和實(shí)際數(shù)據(jù)集中的實(shí)