一種新的位置不確定性聚類算法UCNDBSCAN

王 駿，黃德才

(浙江工業(yè)大學 計算機科學與技術學院，杭州 310023) E-mail：wjxy588@163.com

1 引 言

在現(xiàn)代的許多應用領域中，像給移動性對象領域[1]或者傳感器領域[2]進行聚類操作時，只有不確定性對象是可用的.舉例子來說，比如在給手機移動端對象進行聚類操作時，一個持有手機的人是持續(xù)不斷的變換著他的空間位置的，因此精確的手機端位置是不可獲取的；又比如在無線傳感器環(huán)境監(jiān)測應用中，無線傳感器網(wǎng)絡極度受限的系統(tǒng)資源(如網(wǎng)絡帶寬和電能供給)只能夠實現(xiàn)數(shù)據(jù)以離散的方式進行采集，自然界變化的連續(xù)性與數(shù)據(jù)采樣的離散性之間的矛盾決定了從外部世界獲得的數(shù)據(jù)本質上是隨時間增長的不確定性數(shù)據(jù)，因此在對相關數(shù)據(jù)進行處理時必須考慮數(shù)據(jù)的不確定性，才有可能獲得正確的處理結果，這對傳統(tǒng)的數(shù)據(jù)處理方法提出了新的挑戰(zhàn).

從不確定性數(shù)據(jù)的表現(xiàn)形式，大致可將其分為實例存在不確定性，屬性不確定性和位置不確定性三類.

實例存在不確定性[3](Existential Uncertainty)也稱元組存在不確定性或數(shù)據(jù)對象存在不確定性，即一個數(shù)據(jù)元組存在與否具有一定的不確定性，通常用一個概率值來表示.實例存在不確定性通常簡稱為存在不確定性.

一個元組的存在不確定性一般可采用點概率模型(point probability case).在這種模型中，元組的屬性值是確定的，而元組的存在具有不確定性，并用一個[0，1]之間的概率值來表示.

屬性級不確定性[4](Attribute Level Uncertainty)也稱屬性值的不確定性，它是指一個屬性的取值存在不確定性.在元組數(shù)目和數(shù)據(jù)模型己經(jīng)確定的前提下，通常用概率密度函數(shù)或其它統(tǒng)計量來描述屬性的不確定信息.這種不確定性又可以根據(jù)屬性的類型，分為數(shù)值不確定性和非數(shù)值不確定性.

本文研究的數(shù)據(jù)位置不確定性數(shù)據(jù)，它有區(qū)別于傳統(tǒng)的數(shù)值屬性級不確定性數(shù)據(jù).這一類數(shù)據(jù)的應用需求隨處可見.比如，在野生動物園中，需要分析動物之間的群體親密性和疏遠性；則可以把每個動物看做一個研究對象，由于動物在動物園中的位置是不固定的，因此需要在一段時間內，把一個動物所到過的所有地點區(qū)域結合起來看做一個不確定對象，也就是位置不確定性對象；然后對所有動物進行位置不確定性聚類分析，來比較群體親密性.對于這一類的問題，就是位置不確定性數(shù)據(jù)聚類問題.

目前已有的位置不確定性聚類算法主要以UK-Kmeans聚類[5]算法為基礎，延伸出一系列改進版本[6-11]，但核心思想是一致的：簡單地將中心點與數(shù)據(jù)對象點距離的期望值應用到K-Means算法中，這忽略了不確定性對象的變化范圍對聚類的影響；因此，文獻[12]提出了以區(qū)間數(shù)表示對象的UIDK-Means算法，文獻[13]提出了以聯(lián)系數(shù)表示對象的UCNK-Means算法，這一類算法考慮到了對象變化范圍對聚類效果的影響，但是由于基于K-Means算法，雖然聚類簡單快速，但是具有不適宜發(fā)現(xiàn)非凸形狀簇、無法區(qū)分噪聲和離群點，參數(shù)敏感等缺點；而且UCNK-Means在定義不確定性對象間距離衡量標準的時候，有一些遺留問題，所定義的距離標準會使得部分對象分布狀況無法很好的根據(jù)密度去識別.后來，基于DBScan的密度不確定性聚類算法被相繼提出，其中主要以FDBScan[14]為主；這一類方法能夠更好的發(fā)現(xiàn)任意形狀的簇，并且能夠發(fā)現(xiàn)離群點，很好的克服了基于K-Means所留下的缺點，但是它們仍然以概率密度函數(shù)的方式進行對象的表示，并且仍然沒有考慮數(shù)據(jù)變化的范圍影響，且計算代價較大.

而聯(lián)系數(shù)理論[15]是在集對分析SPA(set pair analysis)[16-19]理論的基礎上延伸出來的一種新的處理不確定性問題的新理論方法和數(shù)學工具.它是集對中衡量不確定的一個重要指標.所謂集對實際是指具有聯(lián)系的兩個集合組成的對，這兩個集合對具有同一性(同)和差異性(異)2個屬性，并通過一個二元聯(lián)系數(shù)來描述這種同異的特性.引進聯(lián)系數(shù)的最初目的是為了應用上的方便，其理論意義則在于拓廣了數(shù)的概念.一方面它把可確定數(shù)與所在范圍的數(shù)與值聯(lián)系起來，另一方面它把宏觀層次上的確定量和微觀層次上的不確定量聯(lián)系起來.雖然聯(lián)系數(shù)u=a+bi的表達形式是統(tǒng)一的，但a，b和i的語義可根據(jù)所研究問題的實際背景具體定義和解釋.

目前，聯(lián)系數(shù)已經(jīng)取得了廣泛的應用，如文獻[20]，用聯(lián)系數(shù)來解決屬性值為區(qū)間數(shù)的多屬性決策問題；如文獻[21]，用聯(lián)系數(shù)來解決準則權重不完全確定的群決策問題；如文獻[22]，用聯(lián)系數(shù)解決了信任表達中的模糊性和不確定性難題，為主觀信任評價和決策研究提供了一種有價值的新思路，如文獻[23]，用聯(lián)系數(shù)來很好的融入考慮等級標準邊界的模糊性，從而給出水資源系統(tǒng)評價的新方法.

因此，針對這一系列遺留問題以及聯(lián)系數(shù)這一數(shù)學工具的特性，本文基于DBSCAN算法，提出一種新的基于聯(lián)系數(shù)的不確定性密度聚類算法UCNDBSCAN.該方法用聯(lián)系數(shù)[15]表示對象，并自定義聯(lián)系數(shù)運算法則以及定義新的對象間距離-聯(lián)系距離，然后根據(jù)聯(lián)系數(shù)的態(tài)勢值理論來衡量聯(lián)系距離的大小，兼顧不確定性數(shù)據(jù)的整體性和變化范圍，從而為運用DBSCAN聚類提供距離衡量標準；并且，本文借用OPTICS算法的核心距離概念，對傳統(tǒng)DBSCAN算法進行改進，在DBSCAN的基礎上進一步減少參數(shù)數(shù)量，使得算法對參數(shù)的敏感性、依賴性更低.經(jīng)過實驗仿真后，發(fā)現(xiàn)該新方法不但大大減小了計算復雜度，而且在聚類精度上有提高，聚類效果優(yōu)秀，參數(shù)敏感性低，可操作性強.

2 相關定義

本部分對本文所提出的算法中所用到的一些概念進行定義.

2.1 位置不確定性對象

對于位置不確定性對象，如下定義：

2.2 聯(lián)系數(shù)

以下定義聯(lián)系數(shù)的基本概念，以及聯(lián)系數(shù)的一些運算：

定義2.(二元聯(lián)系數(shù)) 設用u表示二元聯(lián)系數(shù)[21]，則有：

u=a+bi

(1)

式子(1)中，a稱為確定性聯(lián)系分量，或者同一度，b稱為不確定性聯(lián)系分量，也稱為差異度，i是不確定性聯(lián)系分量系數(shù)，i∈[-1,1]，a為實數(shù)，b為非負實數(shù)，統(tǒng)稱為聯(lián)系數(shù)u的聯(lián)系分量.

定義3.(聯(lián)系數(shù)加法)設有兩個聯(lián)系數(shù)，u1=a1+b1i，u2=a2+b2i，則二元聯(lián)系數(shù)加法[15]如下：

u1+u2=(a1+b1i)+(a2+b2i)=(a1+a2)+(b1+b2)i

(2)

因此，聯(lián)系數(shù)之和仍然是一個聯(lián)系數(shù).

定義4.(聯(lián)系數(shù)減法) 設有兩個聯(lián)系數(shù)，u1=a1+b1i，u2=a2+b2i，則二元聯(lián)系數(shù)減法如下：

u1-u2=(a1+b1i)-(a2+b2i)(a1-a2)+(b1+b2)i

(3)

因此，聯(lián)系數(shù)之差仍然是一個聯(lián)系數(shù).

定義5.(聯(lián)系數(shù)乘法) 設有兩個聯(lián)系數(shù)，u1=a1+b1i，u2=a2+b2i，則二元聯(lián)系數(shù)乘法為：

u1×u2=(a1+b1i)×(a2+b2i)

=a1a2+(a1b2+a2b1)i+b1b2i2a1a2+b1b2i

(4)

因此，聯(lián)系數(shù)之積仍然是一個聯(lián)系數(shù).

定義6.(聯(lián)系數(shù)根號運算) 設一個聯(lián)系數(shù)，u=a+bi，則二元聯(lián)系數(shù)根號運算為：

(5)

因此，聯(lián)系數(shù)根號運算后仍然是一個聯(lián)系數(shù).

2.3 位置不確定性數(shù)據(jù)的聯(lián)系數(shù)表示

在如文獻[6-11]中，采用概率密度函數(shù)來表示一個不確定性對象；一個不確定性對象的一個維度對應一個概率密度函數(shù)；較為常見的是采用高斯分布來模擬數(shù)據(jù)的不確定性分布，而高斯分布的均值和方差，采取的是不確定性數(shù)據(jù)的維度樣本數(shù)據(jù)集的平均值和方差.

這種方法存在一個缺陷，如圖1：

在圖1中，不確定性對象O1的可能存在區(qū)域是馬蹄形帶狀，按照概率密度函數(shù)的計算方式，均值存在與位置P1附近，因此P1附近位置的點會有較大的概率，即權重，P2位置會因為與P1距離較遠，所得權重較小；但實際上，P2是真正在O1的可能存在區(qū)域內，而P1處于O1可能存在區(qū)域外，理論上P2應該比P1具有更大的存在概率或權重.

圖1 不確定性對象分布Fig.1 Uncertain object distribution

事實上，簡單的用高斯分布來模擬數(shù)據(jù)點的位置存在概率，是不精確的，因為不確定性對象的客觀存在概率是不可獲知的，簡單的由位置均值和變化方差來求得高斯分布模擬其概率，是一種理想狀態(tài)下的結果，且只是針對于凸形的數(shù)據(jù)區(qū)域；與其花代價去得到一個不精確的存在概率去作為距離加權運算，倒不如去除概率加權，視作區(qū)域內數(shù)據(jù)等概率，并用類圓形區(qū)域去表示不確定性對象，不但簡化運算，而且精度不會降低.

因此本文用聯(lián)系數(shù)來表示不確定性對象：

對于apq和bpq的計算方式，來源于聯(lián)系數(shù)聯(lián)系分量的含義；對于一個二元聯(lián)系數(shù)u=a+bi，a表示聯(lián)系數(shù)的確定性部分，b表示聯(lián)系數(shù)的不確定性部分；對于一個距離范圍來講，其確定性部分是其距離的平均值，不確定性部分是其距離平均值到距離最大值，最小值的距離半徑；而i是分量系數(shù)，i∈[-1,1]，但在計算過程中i不會取某個固定值，全程保留了聯(lián)系數(shù)的不確定特性，這也是基于聯(lián)系數(shù)表示不確定性對象的最大優(yōu)勢；因此就有了定義7中對于的不確定性對象的聯(lián)系數(shù)計算方式.

(6)

因此，兩個不確定性對象間的聯(lián)系距離，是一個二元聯(lián)系數(shù).

定義9.(態(tài)勢值) 給定一個二元聯(lián)系數(shù)，u=a+bi，則二元聯(lián)系數(shù)的態(tài)勢值記為：

(7)

為該聯(lián)系數(shù)的態(tài)勢值.通常來說，Shi(u)越大，代表該聯(lián)系數(shù)u所表示的不確定性變化趨勢越大；反之，則表示不確定性變化趨勢越小.

定義10.(聯(lián)系距離大小衡量) 如果給定一個聯(lián)系數(shù)u=a+bi，表示兩個不確定性O1，O2對象的聯(lián)系距離，則可以用該聯(lián)系數(shù)的確定性值a和態(tài)勢值Shi(u)的和：

Shiv(u)=a+Shi(u)

(8)

來反應這兩個對象的距離大小，shiv值越大，代表親密性越低，距離越大.

用公式(8)來反應不確定性對象間的距離，是能夠很好的體現(xiàn)出不確定性對象間的聯(lián)系程度的，比單單用期望距離來衡量要更有嚴謹性與可靠性.給出兩個不確定性對象O1，O2，假設都是二維空間對象，根據(jù)定義7，8 與公式(6)求得聯(lián)系距離u12=a12+b12i；則其勢值為Shi(u12)=a12/b12；考慮下面幾種情況，如圖2，3，4，5：

圖2 不確定性對象分布案例Fig.2 Uncertain object distribution case圖3 不確定性對象分布案例Fig.3 Uncertain object distribution case

圖2圖3中，圖2的兩個對象相距甚遠，因此它們的聯(lián)系距離的確定性值明顯較之圖3中要大，即聯(lián)系數(shù)的聯(lián)系距離確定性值a12占主導，則圖2中的shiv明顯大于圖3中的shiv，也即親密性較低，這也和圖直觀期望的結果一致；圖4圖5中兩組對象的平均距離，即聯(lián)系距離的確定性值a12相差不大，這時候我們要考慮聯(lián)系距離的變化趨勢Shi(u12)，由于圖4中的兩個對象距離變化范圍較之圖5要大，即不確定性值b要大，因此其Shi(u12)較之圖5要小，而從直觀角度講，圖4中的兩個對象親密概率更高；所以當聯(lián)系距離的確定性值a12大小不占絕對優(yōu)勢，差不多的時候，可以加入Shi(u12)的值作為參考，這樣圖4中的shiv就相對圖5中的shiv要小，即圖4中的一對對象比圖5中的分布情況更為親密相似；因此對于一個聯(lián)系距離u=a+bi，用a+Shi(u)來代表其聯(lián)系距離的大小，它不但能夠反映不確定性對象的整體位置，而且當整體位置相差不大的時候，還能夠根據(jù)不確定變化的范圍來精細衡量不確定性對象間的相似性，這是比較合理且有效的.

圖4 不確定性對象分布案例Fig.4 Uncertain object distribution case圖5 不確定性對象分布案例Fig.5 Uncertain object distribution case

本文中Shiv()的距離衡量標準定義，是使本文算法相較之基于傳統(tǒng)不確定性對象距離計算以及基于區(qū)間數(shù)的不確定性數(shù)據(jù)聚類算法更為凸顯優(yōu)勢的一個重要創(chuàng)新點；傳統(tǒng)的不確定性距離計算方式，采用在兩個不確定性對象內隨機取樣本點，然后計算兩個對象樣本點間的距離的平均值，作為兩個不確定性對象的最終距離值；這種方式只能區(qū)分圖1圖2中平均距離相差較大的對象分布，對于圖4，圖5中平均距離相差不多，但是變化范圍不一致的情況，無法進一步區(qū)分.

在區(qū)間數(shù)中，把兩個對象O1,O2，在x維度上的距離定義一個區(qū)間數(shù)[a，b]，然后用一個自定義的權值factor，用factor*a+(1-factor)*b來表示對象在O1,O2，在x維度上的最終距離值；這種距離表示法，實質上是一種取距離變化均值的表現(xiàn)，對于圖2，圖3中的組合分布可以區(qū)分，但是圖4，圖5中的組合分布就無法很好的區(qū)分；而本文基于聯(lián)系數(shù)的方法，則可以完全克服這一缺陷；因此，基于區(qū)間數(shù)的聚類算法，無論結合k-means或者DBSCAN，都沒有基于聯(lián)系數(shù)的方法更為有效.

2.4 聚類過程中所用的定義

定義11.(ε-領域) 給定一個對象集S和實數(shù)ε>0，則對于任意X∈S，稱ε(X)={Y|Y∈S，Shiv(uXY)≤ε}為X在S中的ε-領域，簡稱X的ε-領域.

定義12.(核心對象) 對于給定的參數(shù)Minpts和ε，以及任意的X∈S，如果|ε(X)|≥MinPts，則稱X是S關于參數(shù)Minpts和ε的一個核心點，簡稱X為核心點或核心對象.

定義13.(直接密度可達) 對于任意Y，X∈S，如果X是一個核心點，且Y∈ε(X)，則稱點Y從X出發(fā)關于參數(shù)Minpts和ε是直接密度可達的，簡稱從X到Y是直接密度可達的.

定義14.(密度可達) 如果S存在一個對象鏈X1，X2，…，Xn，X1=X，Xn=Y，且從Xi(1≤i≤n-1)到Xi+1是直接密度可達的，則稱從X到Y是密度可達的.

定義15.(核心距離) 給出參數(shù)Minpts，X∈S，計算X到S中其他對象的Shiv值，按照從小到大排序，其中第Minpts個Shiv值稱為對象X在S中的核心距離，簡稱X的核心距離.

3 UCNDBSCAN聚類方法

UCNDBSCAN算法同樣也是基于DBSCAN的，運用聯(lián)系數(shù)表示對象，加入自定義的聯(lián)系距離，進行聚類運算.

3.1 算法描述

UCNDBSCAN算法其實可以大致分為兩大塊：一是數(shù)據(jù)預處理，參數(shù)準備階段；二是算法執(zhí)行階段；兩塊偽代碼分別如下：

算法1.數(shù)據(jù)預處理，參數(shù)準備

輸入：數(shù)據(jù)對象集S={X1，X2，…，Xn}和參數(shù)Minpts；

輸出：聯(lián)系數(shù)集合SR，聯(lián)系矩陣RDM，距離衡量矩陣shivM，參數(shù)ε；

Step0.初始化一個聯(lián)系數(shù)集合SR={}；聯(lián)系距離矩陣RDM=()，距離衡量值矩陣

ShivM()；

Step1.ForS中所有對象

從S中取出一個對象X1，用聯(lián)系數(shù)表示不確定性對象，記錄在SR中；

End for；

Step2.ForSR中所有對象

取出一個對象的聯(lián)系數(shù)形式u1；

ForSR中所有對象

取出一個對象的聯(lián)系數(shù)形式u2，運用定義8中公式(6)，計算u1和u2間的聯(lián)系距離，記錄在RDM中；

End for；

End For；

Step3.根據(jù)公式(7)，(8)將RDM矩陣轉換成

ShivM矩陣；

Step4.根據(jù)參數(shù)Minpts和定義15獲取S中每個對象的核心距離，然后求平均值，作為參數(shù)ε，用來為后面的計算核心對象做準備；

算法2.UCNDBSCAN算法執(zhí)行

輸入：數(shù)據(jù)對象集S={X1，X2，…，Xn}，參數(shù)Minpts，參數(shù)ε，聯(lián)系數(shù)集合SR，聯(lián)系矩陣RDM，距離衡量矩陣shivM

輸出：達到密度要求的聚類C={C1，C2，…，Ck}和離群點集合SC={SX1，SX2，…，SXn}；

Step0.令C=φ

Step1.ForS中所有未訪問過的對象

取出一個對象X1，根據(jù)參數(shù)Minpts，參數(shù)ε和矩陣ShivM來判斷X1是否為核心對象(定義12)；

IfX1是核心對象且X1不在C的任何簇中.則標記X1為訪問過，并且為X1建立一個新簇C1，簇中當前就一個對象X1；初始化一個集合XP={}，表示X1密度可達的對象集合；從S中尋找X1直接密度可達(定義13)的對象，放入XP中，并將這些對象標記為訪問過；

ForXP中對象

取出XP中的一個對象X2，將X2加入到C1中，并判斷X2是否是核心對象；若是，從S中尋找到X2直接密度可達的且沒有被訪問過的所有對象，放入XP中，然后標記這些對象為訪問過，并從XP中刪除X2；若不是，直接從XP中刪除X2即可；

End for；

將C1加入到C中；

End if；

Else

直接標X1為訪問過；

End else；

End for；

Step2.輸出簇集合C，S中剩余的對象都為離群點，全部加入SC集合并輸出.

因此，完整的UCNDBSCAN算法只需要先根據(jù)算法一執(zhí)行，再根據(jù)算法二執(zhí)行即可得到結果.

4 UCNDBSCAN實驗及性能

部分主要從聚類實驗以及性能分析兩個方面來展現(xiàn)UCNDBSCAN算法的核心競爭力-高精度，低計算復雜度，低參數(shù)敏感性.

4.1 UCI數(shù)據(jù)實驗

本部分實驗主要對UCNDBSCAN算法進行iris，wine兩個數(shù)據(jù)集上的聚類實驗，實驗中將UCNDBSCAN算法與EXPDBSCAN和FDBSCAN算法進行對比，主要從兩個角度：

1)每種算法參數(shù)變化對算法聚類精度的影響，從而比較其參數(shù)敏感性；

2)對每種算法選取其精度較高時的參數(shù)值，聚類多次后，比較每種算法的平均精度，從而比較其絕對聚類精度大小.

數(shù)據(jù)集.UCI機器學習數(shù)據(jù)集Iris和Wine數(shù)據(jù)集：

其中Iris(Iris是一種鶯尾屬植物)數(shù)據(jù)集總共有150個數(shù)據(jù)點，每個數(shù)據(jù)點含有Iris花的萼片長度、萼片寬度、花瓣長度和花瓣寬度等4種屬性，一共有3列，其中，第一列為類標志屬性，共有三類，分別記為“1”，“2”，“3”；后面的3列為每個樣本的對應屬性的樣本值；總共分為3個簇，每個簇含有50個數(shù)據(jù)點.

Wine數(shù)據(jù)集含有13種屬性，分別描述13種不同意大利葡萄酒的化學分析結果，13種成分分別為：Alcohol，Malicacid，Ash，Alcalinity of ash，Magnesium，Total phenols，F(xiàn)lavanoids，Nonflavanoid phenols，Proanthocyanins，Color intensity，Hue，OD280/OD315 of diluted wines，Proline；每行代表一種酒的樣本，共有178個樣本；一共有14列，其中，第一列為類標志屬性，共有三類，分別記為“1”，“2”，“3”；后面的13列為每個樣本的對應屬性的樣本值.其中第1類有59個樣本，第2類有71個樣本，第3類有48個樣本.

聚類精度.對于不確定性數(shù)據(jù)的聚類，為了把聚類結果與給定數(shù)據(jù)集的參考分類結果進行比較，本文采用文獻[24]所介紹的質量評估方法QAPC，該方法能夠較合理的評估聚類結果和參考分類結果之間的相似度.

在Iris和Wine數(shù)據(jù)集上分別對EXPDBSCAN，F(xiàn)DBSCAN和UCNDBSCAN進行聚類，并用QAPC進行聚類精度評估，期間，還對以上三種算法各自參數(shù)變化對聚類結果影響進行了比較.

EXPDBSCAN采用傳統(tǒng)的不確定性對象距離衡量方式，通過計算不確定性對象間的樣本點對平均距離值作為對象間的距離值，然后加入DBSCAN進行聚類.

FDBSCAN的對象間距離衡量方式較為復雜，首先計算出不確定性對象每個維度上的屬性均值和方差，然后用高斯分布來表示該維度上的分布函數(shù)，通過高斯分布均值方差加減原則，最后用一個高斯分布來表示對象間某個維度x上的距離分布；則給定一個距離值s后，能夠得出兩個對象在x維度上距離為s的分布概率，如果這個概率大于給出的閾值的話，表示該維度上兩個對象是相連的；按照該方法，可以用DBSCAN繼續(xù)對其進行聚類.

本文首先需要對UCI數(shù)據(jù)集進行不確定性化，本文采用的不確定性化方法如下：

對于一個對象Op，原先是一個確定性點，假設為2維數(shù)據(jù)，則可表示為(xp，yp)，對每一個維度進行不確定化，轉化為一個區(qū)間數(shù)[ap-bp，ap+bp]，其中ap為該區(qū)間的中點，bp為該區(qū)間半徑；如對于xp而言，在區(qū)間[xp-0.2*xp，xp+0.2*xp]間產(chǎn)生一個隨機數(shù)作為apx，然后在區(qū)間數(shù)[0.2*xp，0.3*xp]間產(chǎn)生一個隨機數(shù)作為bpx，則xp的不確定性范圍可表示為[apx-bpx，apx+bpx]，同理yp可轉化為[apy-bpy，apy+bpy]；因此對于Op對象不確定性化結束.

算法的參數(shù)及含義如表1.

由表1可以發(fā)現(xiàn)，在參數(shù)數(shù)目方面，UCNDBSCAN聚類算法有著獨到的優(yōu)勢.

表1 算法及其對應參數(shù)Table 1 Algorithm and parameter

圖6至圖11展示了每個算法其參數(shù)對算法的聚類精度影響.

圖6 EXPDBSCAN在Iris數(shù)據(jù)集上聚類精度隨參數(shù)變化曲線Fig.6 Curve of clustering precision on the Iris data for EXPDBSCAN圖7 EXPDBSCAN在Wine數(shù)據(jù)集上聚類精度隨參數(shù)變化曲線Fig.7 Curve of clustering precision on the Wine data for EXPDBSCAN圖8 FDBSCAN在Iris數(shù)據(jù)集上聚類精度隨參數(shù)變化曲線Fig.8 Curve of clustering precision on the Iris data for FDBSCAN圖9 FDBSCAN在Wine數(shù)據(jù)集上聚類精度隨參數(shù)變化曲線Fig.9 Curve of clustering precision on the Wine data for FDBSCAN

對于圖8，圖9中對于FDBSCAN的聚類，參數(shù)概率閾值p本文取值0.5，這是一個相對能得到較高值聚類精度，且不失合理性的參數(shù)值.

由圖6，圖8，圖10可以得知，在Iris數(shù)據(jù)集上，EXPDBSCAN算法精度在minpts一定的時候，r-distance較小時候變化較大，后期較為穩(wěn)定，但隨著minpts參數(shù)變化精度變化較大；FDBSCAN算法參數(shù)最多，且每一類參數(shù)變化對精度影響都較大，很難趨于穩(wěn)定狀態(tài)；而UCNDBSCAN算法參數(shù)類型最少，且聚類精度會隨參數(shù)變化只有一小段波動，但是隨著參數(shù)增大，逐漸趨于穩(wěn)定，整體上隨參數(shù)變化精度影響最小.

由圖7，圖9，圖11可以得知，UCNDBSCAN算法無論是在精度穩(wěn)定性還是在整體聚類精度上，都絕對領先其他兩種聚類算法.為了更精確的對比三種算法的聚類質量精度，本文對iris，wine各進行了20次數(shù)據(jù)不確定性化，每次不確定性化后，三種聚類算法在兩種數(shù)據(jù)集上各進行一次聚類；最后，每種聚類算法在每個數(shù)據(jù)集上各進行了20次聚類，計算每種算法每個數(shù)據(jù)集20次聚類精度的平均值并進行比較，其中每種算法的聚類精度都取使得該算法在參數(shù)設定后達到最大精度時的精度值；結果如圖12.

從圖中可以明顯的看出，雖然不同數(shù)據(jù)集上對于聚類精度表現(xiàn)有所差異，但是UCNDBSCAN算法的平均聚類精度要高于其余兩種算法.

圖10 UCNDBSCAN在Iris數(shù)據(jù)集上聚類精度隨參數(shù)變化曲線Fig.10 Curve of clustering precision on the Iris data for UCNDBSCAN

圖11 UCNDBSCAN在Wine數(shù)據(jù)集上聚類精度隨參數(shù)變化曲線Fig.11 Curve of clustering precision on the Wine data for UCNDBSCAN

圖12 Iris，Wine數(shù)據(jù)集上三種算法20次聚類平均精度比較Fig.12 Compare of clustering precision on Iris，wine data for the three Algorithm

4.2 自定義數(shù)據(jù)實驗

本部分實驗，采用自定義的數(shù)據(jù)，隨機產(chǎn)生不確定性數(shù)據(jù)，然后對其進行UCNDBSCAN的聚類.

數(shù)據(jù)按照以下方式產(chǎn)生不確定數(shù)據(jù)：

在二維平面中，生成20個對象，對于每一個對象Op，首先在[0，800]范圍上生成2個值，分別記作xp，yp，然后在[50，200]范圍內生成2個值，作為區(qū)域半徑，記作rxp，ryp；這樣Op就可以表示為Op=([xp-rxp，xp+rxp]，[yp-ryp，yp+ryp])，為了能夠在二維圖中表示，在對象Op區(qū)域內隨機生成10個樣本點.

案例1.對象分布如圖13：

圖13中，一種字母代表一個對象，一個字母代表該字母所表示的對象的一個樣本點，因此可以看出圖中總共有A～T20個對象，每個對象有10個樣本點.

對該數(shù)據(jù)集進行UCNDBSCAN聚類，選擇聚類參數(shù)Minpts=4，聚類結果如圖13中線條包裹所示，形成2個簇，簇1集合為{S，E，H，L，T，O，A，Q，M，D，R，I}，簇2集合為{K，F(xiàn)，N，J，C} 其余為離群點{B，G，P}.

案例2.對象分布如圖14：

對該數(shù)據(jù)集進行UCNDBSCAN聚類，選擇聚類參數(shù)Minpts=3，聚類結果如圖14中線條包裹所示，形成4個簇，簇1集合為{P，A，P，L}，簇2集合為{G，Q，I，J，T}，簇3集合為{N，M，S}，簇4集合為{F，E，K，H}，其余為離群點{D，C，R，O}.

案例3.對象分布如圖15：

圖13 自定義數(shù)據(jù)UCNDBSCAN聚類結果Fig.13 Clustering result of UCNDBSCAN on the self-defining data

圖14 自定義數(shù)據(jù)UCNDBSCAN聚類結果Fig.14 Clustering result of UCNDBSCAN on the self-defining data

圖15 自定義數(shù)據(jù)UCNDBSCAN聚類結果Fig.15 Clustering result of UCNDBSCAN on the self-defining data

對該數(shù)據(jù)集進行UCNDBSCAN聚類，選擇聚類參數(shù)Minpts=4，聚類結果如圖15中線條包裹所示，形成4個簇，簇1集合為{T，B，E}，簇2集合為{O，K，P}，簇3集合為{H，R，L，M}，簇4集合為{D，N，J，F(xiàn)，C，G}，其余為離群點{A，S，I，Q}.

因此，從以上3個案例可以直觀地看出，UCNDBSCAN的聚類效果還是非常理想的，和直觀期望聚類結果基本一致.

4.3 性能分析

基于密度的算法，像EXPDBSCAN，F(xiàn)DBSCAN和UCNDBSCAN都是基于DBSCAN的算法，一旦確定了對象間的距離衡量標準，接下去的步驟幾乎都一致，所以他們的時間復雜度都是O(n2).所以，關鍵是比較得到兩個對象間的距離衡量標準的計算復雜度大小.

假設兩個T維不確定性對象O1，O2，分別含有s1和s2個樣本點數(shù)據(jù)：

對于EXPDBSCAN，是通過計算兩個對象的樣本點對之間的平均距離來當做距離衡量標準，因此計算O1和O2間的距離，需要s1*s2次樣本點間距離計算；而計算一次樣本點間的距離就需要2T-1次加減，T次乘法，1次根號運算.

對于FDBSCAN，首先需要用概率密度函數(shù)(高斯分布)來表示出不確定性對象，如O1，有s1個樣本點，則計算高斯分布均值需要(s1-1)*T次加減，T次除法；計算高斯分布方差還需要額外s1*(s1-1)*T次加減，s1*T次乘法，T次除法；然后計算對象間距離概率密度函數(shù)的均值，還需一次T維空間的歐式距離計算，再加2T次加法；計算對象間距離概率密度函數(shù)的方差，還需要s1*s2次乘法和s1*s2次加減，然后給定一個距離閾值，去查表獲取概率值.

對于UCNDBSCAN算法，首先需要將兩個不確定性對象表示成聯(lián)系數(shù)，需要2T次加減，2T次乘除；然后可以得到兩個對象間的聯(lián)系距離，需要4T-1次加減，2T次乘法，1次根號運算，最后用1次除法和1次加法就可以算出該聯(lián)系距離的值.

如表2整理出了各算法計算一次對象間距離所需要的計算復雜度：

表2 計算一次對象間距離的復雜度(T維)Table 2 Complexity of computing one pair objects

表2中可以很清楚的看到，F(xiàn)DBSCAN的計算復雜度最高，UCNDBSCAN的計算復雜度是最低的，它避免了許多樣本點間的點對距離計算和概率密度函數(shù)的估算，因此計算上大大優(yōu)化了復雜度.

4.4 小結

本章節(jié)對UCNDBSCAN算法進行了實驗與性能分析；結果顯示，UCNDBSCAN算法與目前存在的一些算法相比，具有如下核心競爭力：

1)由4.1小節(jié)的圖6至圖11分析可得，UCNDBSCAN算法的參數(shù)數(shù)量少，且參數(shù)敏感性低，較為穩(wěn)定；

2)由4.1小節(jié)的圖12和4.2小節(jié)分析可得，UCNDBSCAN算法的精度非常高，聚類效果非常好，超出現(xiàn)有同類算法的聚類精度與效果；

3)由4.3小節(jié)分析可得，UCNDBSCAN算法的計算復雜度非常低，大大低于目前同類算法，因此其可操作性非常強，性能很高.

4)第四章實驗部分是針對同一類算法-基于DBSCAN的不確定性聚類算法進行比較分析；由于基于聯(lián)系數(shù)的不確定性聚類，之前有過基于k-Means的聚類算法-UCNK-Means；因為基于k-Means的聚類算法不具有發(fā)現(xiàn)離群點和任意形狀簇的優(yōu)勢，本文實驗部分不在對UCNK-Means和UCNDBSCAN進行比較；UCNDBSCAN相對與UCNK-Mean的優(yōu)勢是顯而易見的：能夠發(fā)現(xiàn)離群點和任意形狀的簇.

5 總 結

鑒于針對基于密度的位置型不確性數(shù)據(jù)的聚類問題，目前存在的主流算法有以EXPDBSCAN為代表以樣本點間期望距離作為對象間距離衡量標準和以FDBSCAN為代表以概率密度函數(shù)表示對象，通過求概率值作為對象間距離衡量標準這兩大類做法.但是EXPDBSCAN這一類算法，單純用樣本點間期望作為距離衡量標準，沒有考慮距離變化趨勢對不確定性數(shù)據(jù)聚類結果的影響，有失準確性；而FDBSCAN一類算法運用概率密度函數(shù)，求得對象間距離概率密度函數(shù)來獲取概率值，理論上合理性較好，但是計算操作復雜度非常復雜，且所需參數(shù)較多，實用性并非很高.

針對以上問題，本文提出了以聯(lián)系數(shù)表示對象的UCNDBSCAN算法，經(jīng)過了實驗展示和結果分析，證明了該算法大幅度的降低了計算復雜度，性能高；兼顧了不確定性對象的整體性和變化性，因此聚類精度更高，區(qū)別性更強；而且減少了參數(shù)輸入數(shù)量，精度受參數(shù)影響較小，參數(shù)敏感性低，同時還能識別離群點.

本文證明了基于聯(lián)系數(shù)的不確定性對象表示，可以很好解決聚類問題，并且能夠在減少計算復雜度以及提高聚類精度上有顯著效果.進一步的研究，可以繼續(xù)運用聯(lián)系數(shù)表示不確定性數(shù)據(jù)來進行數(shù)據(jù)流的聚類.