面向不確定性數(shù)據(jù)的聚類算法研究.pdf

1、聚類作為數(shù)據(jù)挖掘/知識(shí)發(fā)現(xiàn)的基礎(chǔ)方法，其應(yīng)用涉及工程領(lǐng)域(如機(jī)器學(xué)習(xí)、模式識(shí)別、信號(hào)處理、信息壓縮)、計(jì)算機(jī)科學(xué)(包括Web挖掘、信息檢索、圖像分割等)、生命醫(yī)學(xué)領(lǐng)域的基因功能識(shí)別與疾病診斷、天文與地球?qū)W(星體分類、地理地貌分析等)、社會(huì)科學(xué)領(lǐng)域(人的行為模式分析、社會(huì)網(wǎng)絡(luò)分析、犯罪心理學(xué)、考古發(fā)現(xiàn)等)以及經(jīng)濟(jì)領(lǐng)域中的客戶特征與購(gòu)買(mǎi)模式分析、企業(yè)分類和股票趨勢(shì)分析等。在聚類的廣泛應(yīng)用中，由于測(cè)量不精確、采樣誤差、過(guò)時(shí)數(shù)據(jù)源以及人們的認(rèn)知

2、不足等造成數(shù)據(jù)本身存在模糊、隨機(jī)等各種不確定性。數(shù)據(jù)的不確定性給數(shù)據(jù)的聚類分析帶來(lái)巨大挑戰(zhàn)。一方面，在傳統(tǒng)數(shù)據(jù)預(yù)處理中采用消除數(shù)據(jù)的不確定成分，往往會(huì)影響聚類結(jié)果的質(zhì)量，另一方面，已有的面向確定性數(shù)據(jù)聚類算法中引入數(shù)據(jù)的不確定性特征會(huì)帶來(lái)算法復(fù)雜性問(wèn)題。
　　聚類作為數(shù)據(jù)挖掘的重要領(lǐng)域，在不確定數(shù)據(jù)聚類技術(shù)方面也得到了廣泛研究。學(xué)者們通過(guò)采用概率密度函數(shù)對(duì)不確定對(duì)象進(jìn)行建模并擴(kuò)展已有聚類算法，提出了包括K-Means算法的改進(jìn)版本

3、 UK-Means、改進(jìn)的EM算法、基于密度的FDBSCAN算法以及面向?qū)哟尉垲惖腇OPTICS算法；Benjamin等結(jié)合蒙特卡洛數(shù)據(jù)庫(kù)系統(tǒng)中的可能世界方法對(duì)不確定數(shù)據(jù)進(jìn)行聚類；而Aggarwal和Yu針對(duì)數(shù)據(jù)流中不確定數(shù)據(jù)設(shè)計(jì)了相應(yīng)算法UMicro，Chau等應(yīng)用UK-Means算法解決移動(dòng)對(duì)象的不確定聚類，并產(chǎn)生較好結(jié)果。
　　上述算法的共同基礎(chǔ)在于將不確定性成分(概率密度函數(shù)表示)引入距離度量中，勢(shì)必引起在期望距離計(jì)算時(shí)，

4、增加算法的時(shí)間復(fù)雜度，同時(shí)距離的近似計(jì)算也制約了算法的擴(kuò)展性。在相關(guān)文獻(xiàn)中通過(guò)計(jì)算公式進(jìn)行變換(類似力學(xué)中的平行軸定理)、最小——最大剪枝法以及切面函數(shù)法來(lái)簡(jiǎn)化上述期望距離的計(jì)算復(fù)雜度，但由于采用松弛約束條件的方法以求得計(jì)算量的減少，往往導(dǎo)致算法的擴(kuò)展能力較弱。不確定數(shù)據(jù)聚類研究作為未來(lái)發(fā)展趨勢(shì)，其所面對(duì)的最直接的挑戰(zhàn)，就是數(shù)據(jù)規(guī)模(聚類計(jì)算要處理的)呈指數(shù)倍的增長(zhǎng)。目前在針對(duì)可能世界實(shí)例的聚合查詢(相當(dāng)于聚類)研究，主要涉及Top-k

5、聚合算法，分別采用分枝定界、計(jì)算松弛降低計(jì)算復(fù)雜性。由于數(shù)據(jù)采集技術(shù)、數(shù)據(jù)庫(kù)技術(shù)以及Internet等技術(shù)的發(fā)展，在巨量數(shù)據(jù)上進(jìn)行聚類分析凸顯其重要性。已有的聚類算法擴(kuò)展到大規(guī)模數(shù)據(jù)上，常常采用隨機(jī)采樣、數(shù)據(jù)壓縮、基于格的方法、分而治之等方法解決計(jì)算時(shí)間或存儲(chǔ)空間上復(fù)雜度。另外聚類的研究對(duì)多屬性、多特征的高維、動(dòng)態(tài)變化(如隨時(shí)間變化)數(shù)據(jù)是學(xué)術(shù)界關(guān)注的另一種計(jì)算的復(fù)雜性，如對(duì)基因數(shù)據(jù)、金融數(shù)據(jù)、衛(wèi)星圖像數(shù)據(jù)以及Web文檔數(shù)據(jù)聚類分析。維

6、度詛咒(curse of dimensionality)使得聚類中許多距離函數(shù)計(jì)算在高維空間不再有效。
　　本文針對(duì)不確定數(shù)據(jù)環(huán)境下，研究了如何對(duì)不確定數(shù)據(jù)進(jìn)行表達(dá)、不確定數(shù)據(jù)間相似性度量，在此基礎(chǔ)上，提出了面向不確定數(shù)據(jù)集的聚類算法，并對(duì)算法有效性進(jìn)行驗(yàn)證。具體內(nèi)容包括:
　　(1)提出了不確定域的概念和基于不確定域的幾種聚類算法。在建立不確定域的概念基礎(chǔ)上，提出了兩類聚類算法和基于不確定域的聚類有效性度量。第一類是基于不

7、確定域的硬 C均值聚類算法，包括U-aHCM和U-sqHCM，U-aHCM算法是離線更新聚類中心(即批更新聚類中心)，而 U-sqHCM是在線更新聚類中心(即當(dāng)有一個(gè)數(shù)據(jù)對(duì)象從一個(gè)分配到另一聚類中，則更新數(shù)據(jù)對(duì)象變動(dòng)的兩個(gè)聚類)；第二類是基于不確定域的模糊 C均值聚類算法，也包括兩種:U-sFCM和U-eFCM。這些算法基于提出的數(shù)據(jù)的不確定域概念較好地處理數(shù)據(jù)的不確定性。
　　(2)提出了基于超矩形的數(shù)據(jù)不確定域概念和基于超矩形

8、不確定域的聚類算法?；诔匦尾淮_定域聚類算法能夠更靈活處理數(shù)據(jù)的不確定性和發(fā)現(xiàn)不同形狀與大小的聚類(簇)，本論文主要提出了三類基于超矩形不確定域的聚類算法:SU-aHCM與 SU-sHCM、SU-sFCM與SU-eFCM以及SU-sPCM與 SU-ePCM。
　　(3)為了解決基于超矩形不確定域聚類算法中不適定問(wèn)題(ill-posed problem)，提出了基于正則化的超矩形不確定域概念，構(gòu)建了兩類基于Lx正則化的超矩形不確定

9、域聚類算法。一類是基于L2正則化的超矩形不確定域模糊 C均值聚類算法(L2-SU-sFCM與 L2-SU-eFCM)，另一類基于L1正則化的超矩形不確定域模糊 C均值聚類算法(L1-SU—sFCM與 L1-SU—eFCM)，該算法體現(xiàn)對(duì)數(shù)據(jù)對(duì)象稀疏化，從而更能發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)關(guān)系。
　　(4)為了表達(dá)模糊 C均值聚類算法中隸屬函數(shù)的不確定性，本論文結(jié)合直覺(jué)模糊集理論與方法提出了基于直覺(jué)模糊集的聚類算法，包括基于基于直覺(jué)模糊集的模糊 C