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

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

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

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

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

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

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

7、確定域的硬 C均值聚類算法，包括U-aHCM和U-sqHCM，U-aHCM算法是離線更新聚類中心(即批更新聚類中心)，而 U-sqHCM是在線更新聚類中心(即當有一個數(shù)據(jù)對象從一個分配到另一聚類中，則更新數(shù)據(jù)對象變動的兩個聚類)；第二類是基于不確定域的模糊 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)為了解決基于超矩形不確定域聚類算法中不適定問題(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)對數(shù)據(jù)對象稀疏化，從而更能發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)關系。
　　(4)為了表達模糊 C均值聚類算法中隸屬函數(shù)的不確定性，本論文結(jié)合直覺模糊集理論與方法提出了基于直覺模糊集的聚類算法，包括基于基于直覺模糊集的模糊 C