王 駿，黃德才

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

1 引 言

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

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

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

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

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

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

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

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

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

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

2 相關(guān)定義

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

2.1 位置不確定性對象

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

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

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

定義2.(二元聯(lián)系數(shù)) 設(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í)數(shù)，b為非負(fù)實(shí)數(shù)，統(tǒng)稱為聯(lián)系數(shù)u的聯(lián)系分量.

定義3.(聯(lián)系數(shù)加法)設(shè)有兩個(gè)聯(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ù)之和仍然是一個(gè)聯(lián)系數(shù).

定義4.(聯(lián)系數(shù)減法) 設(shè)有兩個(gè)聯(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ù)之差仍然是一個(gè)聯(lián)系數(shù).

定義5.(聯(lián)系數(shù)乘法) 設(shè)有兩個(gè)聯(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ù)之積仍然是一個(gè)聯(lián)系數(shù).

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

(5)

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

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

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

這種方法存在一個(gè)缺陷，如圖1：

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

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

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

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

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

(6)

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

定義9.(態(tài)勢值) 給定一個(gè)二元聯(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)系距離大小衡量) 如果給定一個(gè)聯(lián)系數(shù)u=a+bi，表示兩個(gè)不確定性O(shè)1，O2對象的聯(lián)系距離，則可以用該聯(lián)系數(shù)的確定性值a和態(tài)勢值Shi(u)的和：

Shiv(u)=a+Shi(u)

(8)

來反應(yīng)這兩個(gè)對象的距離大小，shiv值越大，代表親密性越低，距離越大.

用公式(8)來反應(yīng)不確定性對象間的距離，是能夠很好的體現(xiàn)出不確定性對象間的聯(lián)系程度的，比單單用期望距離來衡量要更有嚴(yán)謹(jǐn)性與可靠性.給出兩個(gè)不確定性對象O1，O2，假設(shè)都是二維空間對象，根據(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的兩個(gè)對象相距甚遠(yuǎn)，因此它們的聯(lián)系距離的確定性值明顯較之圖3中要大，即聯(lián)系數(shù)的聯(lián)系距離確定性值a12占主導(dǎo)，則圖2中的shiv明顯大于圖3中的shiv，也即親密性較低，這也和圖直觀期望的結(jié)果一致；圖4圖5中兩組對象的平均距離，即聯(lián)系距離的確定性值a12相差不大，這時(shí)候我們要考慮聯(lián)系距離的變化趨勢Shi(u12)，由于圖4中的兩個(gè)對象距離變化范圍較之圖5要大，即不確定性值b要大，因此其Shi(u12)較之圖5要小，而從直觀角度講，圖4中的兩個(gè)對象親密概率更高；所以當(dāng)聯(lián)系距離的確定性值a12大小不占絕對優(yōu)勢，差不多的時(shí)候，可以加入Shi(u12)的值作為參考，這樣圖4中的shiv就相對圖5中的shiv要小，即圖4中的一對對象比圖5中的分布情況更為親密相似；因此對于一個(gè)聯(lián)系距離u=a+bi，用a+Shi(u)來代表其聯(lián)系距離的大小，它不但能夠反映不確定性對象的整體位置，而且當(dāng)整體位置相差不大的時(shí)候，還能夠根據(jù)不確定變化的范圍來精細(xì)衡量不確定性對象間的相似性，這是比較合理且有效的.

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

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

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

2.4 聚類過程中所用的定義

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

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

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

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

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

3 UCNDBSCAN聚類方法

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

3.1 算法描述

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

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

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

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

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

ShivM()；

Step1.ForS中所有對象

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

End for；

Step2.ForSR中所有對象

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

ForSR中所有對象

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

End for；

End For；

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

ShivM矩陣；

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

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

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

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

Step0.令C=φ

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

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

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

ForXP中對象

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

End for；

將C1加入到C中；

End if；

Else

直接標(biāo)X1為訪問過；

End else；

End for；

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

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

4 UCNDBSCAN實(shí)驗(yàn)及性能

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

4.1 UCI數(shù)據(jù)實(shí)驗(yàn)

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

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

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

數(shù)據(jù)集.UCI機(jī)器學(xué)習(xí)數(shù)據(jù)集Iris和Wine數(shù)據(jù)集：

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

Wine數(shù)據(jù)集含有13種屬性，分別描述13種不同意大利葡萄酒的化學(xué)分析結(jié)果，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個(gè)樣本；一共有14列，其中，第一列為類標(biāo)志屬性，共有三類，分別記為“1”，“2”，“3”；后面的13列為每個(gè)樣本的對應(yīng)屬性的樣本值.其中第1類有59個(gè)樣本，第2類有71個(gè)樣本，第3類有48個(gè)樣本.

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

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

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

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

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

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

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

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

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

圖6至圖11展示了每個(gè)算法其參數(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，這是一個(gè)相對能得到較高值聚類精度，且不失合理性的參數(shù)值.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.3 性能分析

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

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

對于EXPDBSCAN，是通過計(jì)算兩個(gè)對象的樣本點(diǎn)對之間的平均距離來當(dāng)做距離衡量標(biāo)準(zhǔn)，因此計(jì)算O1和O2間的距離，需要s1*s2次樣本點(diǎn)間距離計(jì)算；而計(jì)算一次樣本點(diǎn)間的距離就需要2T-1次加減，T次乘法，1次根號運(yùn)算.

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

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

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

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

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

4.4 小結(jié)

本章節(jié)對UCNDBSCAN算法進(jìn)行了實(shí)驗(yàn)與性能分析；結(jié)果顯示，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算法的計(jì)算復(fù)雜度非常低，大大低于目前同類算法，因此其可操作性非常強(qiáng)，性能很高.

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

5 總 結(jié)

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

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

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