萬靜 鄭龍君 何云斌 李松

摘 要：如何降低不確定數(shù)據(jù)對高維數(shù)據(jù)聚類的影響是當(dāng)前的研究難點(diǎn)。針對由不確定數(shù)據(jù)與維度災(zāi)難導(dǎo)致的聚類精度低的問題，采用先將不確定數(shù)據(jù)確定化，后對確定數(shù)據(jù)聚類的方法。在將不確定數(shù)據(jù)確定化的過程中，將不確定數(shù)據(jù)分為值不確定數(shù)據(jù)與維度不確定數(shù)據(jù)，并分別處理以提高算法效率。采用結(jié)合期望距離的K近鄰（KNN）查詢得到對聚類結(jié)果影響最小的不確定數(shù)據(jù)近似值以提高聚類精度。在得到確定數(shù)據(jù)之后，采用子空間聚類的方式避免維度災(zāi)難的影響。實(shí)驗(yàn)結(jié)果證明，基于Clique的高維不確定數(shù)據(jù)聚類算法（UClique）在UCI數(shù)據(jù)集上有較好的表現(xiàn)，有良好的抗噪聲能力和伸縮性，在高維數(shù)據(jù)上能得到較好的聚類結(jié)果，在不同的不確定數(shù)據(jù)集實(shí)驗(yàn)中能夠得到較高精度的實(shí)驗(yàn)結(jié)果，體現(xiàn)出算法具有一定的健壯性，能夠有效地對高維不確定數(shù)據(jù)集聚類。

關(guān)鍵詞：高維;不確定;Clique算法;K近鄰

中圖分類號(hào)：TP311.13

文獻(xiàn)標(biāo)志碼：A

Subspace clustering algorithm for high dimensional uncertain data

WAN Jing*，ZHENG Longjun，HE Yunbin，LI Song

School of Computer Science and Technology， Harbin University of Science and Technology， Harbin Heilongjiang 150080， China

Abstract：

How to reduce the impact of uncertain data on high dimensional data clustering is the difficulty of current research. Aiming at the problem of low clustering accuracy caused by uncertain data and curse of dimensionality， the method of determining the uncertain data and then clustering the certain data was adopted. In the process of determining the uncertain data， uncertain data were divided into value uncertain data and dimension uncertain data， and were processed separately to improve algorithm efficiency.KNearest Neighbor （KNN） query combined with expected distance was used to obtain the approximate value of uncertain data with the least impact on the clustering results， so as to improve the clustering accuracy. After determining the uncertain data， the method of subspace clustering was adopted to avoid the impact of the curse of dimensionality. The experimental results show that highdimensional uncertain data clustering algorithm based on Clique for Uncertain data （UClique） has good performance on UCI datasets， has good antinoise performance and scalability， can obtain better clustering results on high dimensional data， and can achieve the experimental results with higher accuracy on different uncertain datasets， showing that the algorithm is robust and can effectively cluster high dimensional uncertain data.

Key words：

highdimension; uncertain; Clique （Clique for all data） algorithm;KNearest Neighbor （KNN）

0?引言

數(shù)據(jù)挖掘已經(jīng)被廣泛應(yīng)用到日常生活與工作中，在諸多領(lǐng)域都扮演著重要的角色，例如交通[1]、醫(yī)療[2]、金融[3]、制藥[4]等。聚類是數(shù)據(jù)挖掘中的一種無先驗(yàn)條件的無監(jiān)督分析方法。將數(shù)據(jù)集中的數(shù)據(jù)根據(jù)各自的特征分成不同的簇，簇間盡可能相異，簇內(nèi)盡可能相似。聚類的方法多種多樣，經(jīng)典的聚類方法有基于劃分的聚類方法[5]、基于層次的聚類方法[6]、基于網(wǎng)格的聚類方法[7]、基于密度的聚類方法[8]，還有基于模型的聚類方法[9]。伴隨著學(xué)者們的努力研究，新的聚類方法被提出，例如高維數(shù)據(jù)的聚類方法[10]、圖像聚類[11]等。

高維數(shù)據(jù)的聚類容易受到維度災(zāi)難的影響，傳統(tǒng)的聚類方法不能有效地對高維數(shù)據(jù)聚類。經(jīng)過國內(nèi)外學(xué)者的不斷研究，高維數(shù)據(jù)的聚類方法可以被分為以下3種：基于降維的聚類[12]、基于子空間的聚類和其他的聚類方法[13]。子空間聚類方法是選出部分?jǐn)?shù)據(jù)作為高維數(shù)據(jù)的子空間，在子空間上聚類代替在整個(gè)數(shù)據(jù)集上聚類。子空間聚類在加權(quán)方法上分為軟子空間聚類算法與硬子空間聚類算法，在搜索方法上可分為自下而上的子空間聚類算法與自上而下的子空間聚類算法。

Liu等[14]提出基于SMDM（Selfadapted Mixture Distance Measure）的聚類算法，解決了不確定數(shù)據(jù)聚類效率低的問題，算法提出了自適應(yīng)的混合距離，降低了不確定數(shù)據(jù)對聚類結(jié)果的影響。算法在聚類效果、伸縮性等方面有良好的表現(xiàn)，由于算法中核密度估計(jì)的計(jì)算量較大，算法在對高維數(shù)據(jù)聚類時(shí)效果不明顯。針對高維數(shù)據(jù)的維度災(zāi)難問題，Goyal等[15]提出了ENCLUS（ENtropybased CLUStering）算法，證明了在普通的低秩子空間聚類效果更好，算法采用ORT（Optimal Rigid Transform）得到更適合的子空間集合，但文中大量的對子空間優(yōu)化步驟影響了算法的效率，導(dǎo)致算法的伸縮性較差。由于高維數(shù)據(jù)聚類過程精度都難以得到保證，Zhang等[16]提出lLMSC（linear Latent Multiview Subspace Clustering）算法與gMLSC（generalized Latent Multiview Subspace Clustering）算法，采用對多個(gè)視圖的潛在表示來探索數(shù)據(jù)點(diǎn)之間的關(guān)系，可以有效處理噪聲。引入神經(jīng)網(wǎng)絡(luò)來探索更廣泛的關(guān)系，可以有效提高聚類精度。但是針對不同類別的數(shù)據(jù)，算法的效果不夠理想，因?yàn)榫€性模型不足以在任何情況下模擬不同視圖之間的相關(guān)性，而且無法得到全局最優(yōu)解，因此算法的普適性較差。隨后Zhu等[17]提出CSSub（Clustering by Shared Subspaces）算法，該算法提出新的子空間聚類框架，使相鄰的核心點(diǎn)能夠根據(jù)它們共享的子空間數(shù)量聚類，將候選子空間選擇和聚類劃分為兩個(gè)獨(dú)立的過程，算法的普適性得到提高。但是受到了子空間聚類的限制，算法對子空間的質(zhì)量比較敏感。針對這個(gè)問題，Li等[18]提出基于CLF（Cauchy Loss Function）的子空間聚類算法，提出了采用CLF抑制噪聲，減小噪聲對算法的影響。算法從理論上證明了阻效應(yīng)，能夠保持原始數(shù)據(jù)的局部結(jié)構(gòu)，提高子空間的質(zhì)量，但算法對參數(shù)c和λ敏感。為了避免算法對參數(shù)的敏感問題，Chen等[19]提出SSSC（Structured Sparse Subspace Clustering）算法。算法定義了一個(gè)新的分組效應(yīng)集群（GroupingEffectWithinCluster， GEWC），并結(jié)合分割矩陣提出了一種新的懲罰方法，避免參數(shù)影響的同時(shí)，提高了算法的聚類精度。而范虹等[20]提出基于煙花算法優(yōu)化的軟子空間聚類算法（Soft Subspace Clustering based on Fireworks Optimization Algorithm， FWASSC）算法，設(shè)計(jì)了新的目標(biāo)函數(shù)，彌補(bǔ)了對噪聲敏感的缺點(diǎn)，設(shè)計(jì)了新的隸屬度計(jì)算方法，提高了聚類精度。同時(shí)傅文進(jìn)等[21]從全局結(jié)構(gòu)到局部結(jié)構(gòu)的子空間聚類方法（Global structure and Local structure of data for Subspace Clustering， GLSC）算法，利用高斯核函數(shù)對l2范數(shù)加權(quán)，得到了較好的聚類結(jié)果。文獻(xiàn)[19-21]算法的共同問題是大量迭代計(jì)算導(dǎo)致算法耗時(shí)較長。

本文采用子空間聚類算法對高維不確定數(shù)據(jù)聚類。Clique算法是經(jīng)典的子空間聚類算法，適合對高維數(shù)據(jù)聚類，但是并不適合對不確定數(shù)據(jù)聚類。針對高維不確定數(shù)據(jù)的聚類問題，根據(jù)Clique算法提出改進(jìn)。高維不確定數(shù)據(jù)分為維度不確定與值不確定兩種情況：維度不確定又分為部分?jǐn)?shù)據(jù)維度不確定與數(shù)據(jù)集維度不確定;值不確定分為值模糊與缺失值。針對這4種情況下分別提出算法：在針對高維部分?jǐn)?shù)據(jù)不確定的情況下采用結(jié)合均值和方差的Clique算法;在針對高維數(shù)據(jù)集維度不確定的情況下，通過計(jì)算維度之間的相關(guān)性得到確定的維度集合，結(jié)合Clique算法聚類;針對高維數(shù)據(jù)的值模糊與存在缺失值的情況，提出結(jié)合K近鄰（KNearest Neighbor，KNN）算法的Clique算法。

本文的貢獻(xiàn)主要有4個(gè)方面：

1）針對高維不確定數(shù)據(jù)中，部分?jǐn)?shù)據(jù)維度不確定的情況提出了針對維度不確定數(shù)據(jù)的Clique（Clique for Uncertain Dimension of Partial Data， UDPClique）算法，根據(jù)不同維度的維度特點(diǎn)，將不確定數(shù)據(jù)劃分到相應(yīng)維度。

2）針對數(shù)據(jù)集維度不確定的高維不確定數(shù)據(jù)提出針對維度不確定數(shù)據(jù)集的Clique（Clique for Uncertain Dimensions of Datasets， UDDClique）算法，根據(jù)維度之間的關(guān)聯(lián)程度判斷不確定維度的確定程度，得到確定的維度。

3）針對空間位置模糊的高維不確定數(shù)據(jù)提出針對模糊數(shù)據(jù)的Clique（Clique for Fuzzy Value range， UFVClique）算法，根據(jù)不確定數(shù)據(jù)在確定數(shù)據(jù)集中的K近鄰分布情況判斷不確定數(shù)據(jù)的所屬網(wǎng)格，利用網(wǎng)格的鄰近性聚類。

4）針對存在缺失值的高維不確定數(shù)據(jù)提出針對缺失數(shù)據(jù)的Clique（Clique for Missing Values， UMVClique）算法，根據(jù)不確定數(shù)據(jù)在確定數(shù)據(jù)集中的K近鄰，填補(bǔ)缺失值。

1?基礎(chǔ)知識(shí)

定理1?反單調(diào)性[22]。如果數(shù)據(jù)集S在k-1維空間是密集的，那么在任意的k維空間中數(shù)據(jù)集S也是密集的。

定義1?最近鄰（Nearest Neighbor，NN）查詢[23]。給定數(shù)據(jù)對象集合P和一個(gè)查詢點(diǎn)q，最近鄰查詢就是在集合P中找到一個(gè)數(shù)據(jù)對象子集，滿足下面條件：

NN（q）={p∈P|o∈P，

dist（q，p）≤dist（q，o）}（1）

定義2?K近鄰查詢[23]。給定數(shù)據(jù)對象集合P和一個(gè)查詢點(diǎn) q，K最近鄰查詢就是在集合P中找到K個(gè)數(shù)據(jù)，這K個(gè)數(shù)據(jù)距離q的距離小于其他數(shù)據(jù)距離q的距離。

定義3?空間不確定數(shù)據(jù)[24]。在m維空間Rm中，給定一組不確定空間數(shù)據(jù)對象O={o1，o2，…，on}，距離函數(shù)d：R2m→R，對于每個(gè)不確定空間數(shù)據(jù)對象oi，都有一個(gè)概率密度函數(shù)fi：Rm→R定義不確定對象的分布。根據(jù)概率密度函數(shù)得到：fi（x）≥0，x∈Rm，∫x∈Rmfi（x）dx=1通過期望距離衡量不確定對象的相似度。

定義4?期望距離[24]。不確定空間對象oi和任意點(diǎn)p的期望距離定義：

ED（oi，p）=∫x∈Aifi（x）Dist（x，p）dx; p∈Rk（2）

假設(shè)A={A1，A2，…，Ak}是一個(gè)有界、全部有序域的集合，S=A1，A2，…，Ak是一個(gè)k維的數(shù)值空間，其中A1，A2，…，Ak表示S的k個(gè)維。k維數(shù)據(jù)X=〈x1，x2，…，xk〉表示S上的數(shù)據(jù)在t時(shí)刻的一個(gè)點(diǎn)集，其中xi=〈xi1，xi2，…，xik〉表示一個(gè)數(shù)據(jù)點(diǎn)，xij為數(shù)據(jù)點(diǎn)xi的第j維的值。

定義5?子空間[25]。數(shù)值空間Sub=At1×At2×…×Atg，其中g(shù)小于維數(shù)k，并且當(dāng)i

定義6?多維度關(guān)聯(lián)[26]。維度是具有某一相同特征數(shù)據(jù)的集合，多維度則是從不同層次、不同角度呈現(xiàn)數(shù)據(jù)，數(shù)據(jù)之間可以有交叉。

2?維度不確定聚類算法

高維數(shù)據(jù)的不確定性可以分為值不確定和維度不確定，針對維度不確定的情況采用子空間聚類算法。

2.1?部分?jǐn)?shù)據(jù)維度不確定的子空間聚類算法

日常生活中存在一些維度不確定的高維數(shù)據(jù)，這些數(shù)據(jù)在數(shù)據(jù)集中是游離的，在聚類過程中會(huì)降低聚類精度。本節(jié)針對這種情況提出UDPClique算法。

高維數(shù)據(jù)中存在部分?jǐn)?shù)據(jù)不確定的情況，針對數(shù)據(jù)的維度不確定導(dǎo)致聚類精度低的問題， 提出UDPClique算法。根據(jù)不確定數(shù)據(jù)在不同維度的差異，可以判斷出不確定數(shù)據(jù)的維度分布，可以將不確定數(shù)據(jù)確定化。采用Clique算法對確定的數(shù)據(jù)集聚類。

高維數(shù)據(jù)集中的數(shù)據(jù)的特點(diǎn)與維度相關(guān)，不同維度中的數(shù)據(jù)特點(diǎn)不同。針對這一情況，按照維度特點(diǎn)將不確定數(shù)據(jù)劃分到最相似的維度中，可以最大限度地減小不確定數(shù)據(jù)對聚類精度的影響。雖然存在劃分錯(cuò)誤的可能，但由于劃分是符合維度的數(shù)據(jù)特點(diǎn)，所以對聚類精度的影響不大。

假設(shè)存在不確定數(shù)據(jù)ui={a1，a2，…，aj}，其中i代表不確定數(shù)據(jù)在數(shù)據(jù)集中的位置，a1，a2，…，aj代表不確定數(shù)據(jù)j個(gè)維度的值?？梢酝ㄟ^計(jì)算不確定數(shù)據(jù)在各個(gè)維度與維度均值的差異來判斷不確定數(shù)據(jù)的維度劃分。差異的計(jì)算公式為：

mk（ai）=|ai-k|（3）

其中：mk（ai）代表在第k個(gè)維度的差異值，k代表在第k個(gè)維度的均值。

將數(shù)據(jù)集的維度按照方差大小排列，方差計(jì)算公式為：

Vak=1nk∑nki=1（dk（i）-k）2（4）

其中：Vak為第k個(gè)維度的方差，dk（i）表示第k個(gè)維度中第i個(gè)數(shù)據(jù)的值，k為第k個(gè)維度的均值，nk表示第k個(gè)維度的數(shù)據(jù)總數(shù)。

均值和方差可以有效體現(xiàn)一個(gè)數(shù)據(jù)集的數(shù)據(jù)特征，方差可以反映出數(shù)據(jù)集的密集程度，方差越小的數(shù)據(jù)集越密集，方差越大的數(shù)據(jù)集越稀疏。均值可以在一定程度上體現(xiàn)數(shù)據(jù)集中數(shù)據(jù)的分布情況，但會(huì)受到數(shù)據(jù)集的密集程度的影響。方差小的數(shù)據(jù)集，其均值所體現(xiàn)的數(shù)據(jù)集的位置分布更準(zhǔn)確，方差大的數(shù)據(jù)集，其均值所體現(xiàn)的數(shù)據(jù)集位置分布準(zhǔn)確性較低。根據(jù)這兩點(diǎn)，將不確定數(shù)據(jù)未知維度的值劃分到更相似的維度，能夠最大限度地保證聚類精度。但首先要按照數(shù)據(jù)集方差從大到小的順序依次劃分不確定數(shù)據(jù)的維度。保證密集的維度首先被劃分，密集的維度均值的代表性強(qiáng)，對劃分的準(zhǔn)確度要求高; 而稀疏的維度，對劃分的準(zhǔn)確度要求低。

算法1的具體步驟為：首先將數(shù)據(jù)分為確定數(shù)據(jù)和不確定數(shù)據(jù)，并將確定數(shù)據(jù)按維度劃分，得到維度集。采用式（4）計(jì)算每個(gè)維度集方差，并按照方差大小排列維度集，采用式（3）計(jì)算每個(gè)維度集的均值，根據(jù)均值將不確定數(shù)據(jù)劃分維度。得到確定數(shù)據(jù)集，采用Clique算法對確定數(shù)據(jù)集聚類。

算法1?UDPClique（）。

輸入?數(shù)據(jù)集C={d1，d2，…，dn};

輸出?聚類結(jié)果。

程序前

begin

1） 將C中的確定數(shù)據(jù)存入CE集合，將C中的不確定數(shù)據(jù)存入U(xiǎn)CE集合;

2） 將CE集合中的數(shù)據(jù)按照維度劃分維度集合;

3） 根據(jù)距離計(jì)算式（4）計(jì)算各個(gè)維度集合的方差;

4） 將維度集合按照方差從小到大的順序排列;

5） 根據(jù)式（3）按順序計(jì)算不確定數(shù)據(jù)各個(gè)未知維度值與各個(gè)維度的差異，并將不確定數(shù)據(jù)劃分到差異最小的維度中;

6） 將不確定數(shù)據(jù)從UCE集合中刪除;

7） 不斷重復(fù)步驟3）～6），直到UCE集合為空;

8） Clique（CE）;

end

程序后

由文獻(xiàn)[23]可得步驟8）Clique算法的時(shí)間復(fù)雜度為O（ck+kn），其中k為數(shù)據(jù)集維數(shù)，n為數(shù)據(jù)集數(shù)據(jù)總數(shù)，c為簇的個(gè)數(shù);步驟1）、2）的時(shí)間復(fù)雜度為O（n）;步驟3）～7）的時(shí)間復(fù)雜度為O（kn+k）。那么算法1的時(shí)間復(fù)雜度為O（（c+1）k+（2k+1）n）。

2.2?數(shù)據(jù)集維度不確定子空間聚類算法

針對數(shù)據(jù)集維度不確定的高維數(shù)據(jù)提出UDDClique聚類算法，利用維度之間的關(guān)聯(lián)性得到數(shù)據(jù)集的確定維度，并采用Clique算法對數(shù)據(jù)集聚類。

日常生活中經(jīng)常會(huì)碰到記錄散亂的數(shù)據(jù)，數(shù)據(jù)中存在缺失值、臟數(shù)據(jù)等情況。這種情況大量出現(xiàn)在高維數(shù)據(jù)中的某一維度或多個(gè)維度中，數(shù)據(jù)集的維度確定性降低，聚類質(zhì)量會(huì)受到影響。高維數(shù)據(jù)具有稀疏性，當(dāng)數(shù)據(jù)集的維度不確定時(shí)，數(shù)據(jù)集的稀疏程度會(huì)受影響，聚類的難度增加。高維數(shù)據(jù)的維度之間具有相關(guān)性，相關(guān)的維度之間存在相應(yīng)的關(guān)聯(lián)規(guī)則，如果某一個(gè)維度和多個(gè)維度具有強(qiáng)的關(guān)聯(lián)性，那么這個(gè)維度存在的可能性就比較高，對于數(shù)據(jù)集來講這個(gè)維度的信息比較重要，對聚類分析幫助比較大。根據(jù)這個(gè)特點(diǎn)對數(shù)據(jù)集維度不確定的數(shù)據(jù)聚類。

定義7?維度相關(guān)度。存在高維數(shù)據(jù)集C={d1，d2，…，dn}，數(shù)據(jù)集C中擁有維度a與維度b。假設(shè)維度a中一共存在n個(gè)數(shù)據(jù)在維度b中也能夠找到，那么維度a與維度b的相關(guān)度為n。記為：

co（a|b）=co（b|a）=n（5）

定義8?維度關(guān)聯(lián)度。存在高維數(shù)據(jù)集C，數(shù)據(jù)集C中擁有維度a與其他維度。維度a與其他維度的相關(guān)度的和，為維度a與數(shù)據(jù)集C的關(guān)聯(lián)度。公式為：

co（a）=∑ki=1co（a|i）; i≠a（6）

其中：a為第a個(gè)維度，k為數(shù)據(jù)集的維數(shù)。

采用數(shù)據(jù)集矩陣計(jì)算各個(gè)維度的相關(guān)度。數(shù)據(jù)集矩陣的生成方式：以數(shù)據(jù)作為矩陣橫軸，以維度作為豎軸。每一個(gè)數(shù)據(jù)在存在的維度上為1，不存在的維度上為0， 這樣矩陣每一列代表一個(gè)數(shù)據(jù)存在于哪些維度，每一行代表每一個(gè)維度擁有哪些數(shù)據(jù)。通過矩陣可以很方便地得到維度密度與維度相關(guān)度。維度密度是維度中集合數(shù)據(jù)的個(gè)數(shù)，記為da（a代表在第a個(gè)維度）。

在針對高維數(shù)據(jù)的子空間聚類算法中，維度密度是子空間生成的一個(gè)標(biāo)準(zhǔn)。在針對高維不確定數(shù)據(jù)時(shí)，維度密度無法體現(xiàn)維度存在的可能性。在維度密度的基礎(chǔ)上結(jié)合維度相關(guān)度，即可以保證數(shù)據(jù)量足夠多，足以保證維度的確定性。可選維度公式為：

chi=coi×di（7）

高維數(shù)據(jù)聚類算法的計(jì)算復(fù)雜，子空間聚類方法通過在子數(shù)據(jù)集的聚類來減小計(jì)算量，子空間中的數(shù)據(jù)要在一定程度上能夠代替整個(gè)數(shù)據(jù)集。首先子空間中的數(shù)據(jù)要足夠多，才有聚類分析的價(jià)值; 其次子空間中的數(shù)據(jù)要足夠重要，無關(guān)的數(shù)據(jù)只會(huì)增加聚類的復(fù)雜性。在高維不確定數(shù)據(jù)集中，維度集確定性也是子空間選擇數(shù)據(jù)的標(biāo)準(zhǔn)，不確定數(shù)據(jù)會(huì)增加聚類的時(shí)間并降低聚類精度。根據(jù)子空間數(shù)據(jù)的特點(diǎn)選取子空間，將維度密度大而且關(guān)聯(lián)性強(qiáng)的維度用作生成子空間。保證了子空間中有足夠多并足夠重要的數(shù)據(jù)，數(shù)據(jù)的確定性也得到了保證。采用均值作為維度選擇閾值，維度關(guān)聯(lián)度是在維度密度的基礎(chǔ)上得到的，維度關(guān)聯(lián)度大的維度維度密度必然大，反之則不成立。針對這一點(diǎn)，根據(jù)式（7）得到的數(shù)據(jù)會(huì)呈現(xiàn)明顯的兩極分化，以均值作為閾值可以有效區(qū)分維度之間的差異。計(jì)算公式為：

ε=1k∑ki=1ch（i）（8）

在得到確定維度并生成確定數(shù)據(jù)集后，采用Clique算法對確定數(shù)據(jù)集聚類。結(jié)合維度相關(guān)性將不確定維度確定化可以最大限度地提高聚類精度。根據(jù)式（8）將適合聚類的維度選擇出來，生成確定數(shù)據(jù)集，針對確定的高維數(shù)據(jù)集Clique算法可以有效地聚類。

算法2步驟：首先生成數(shù)據(jù)矩陣，從矩陣中可以得到每個(gè)維度的維度密度，可以得到維度之間的相關(guān)度，并計(jì)算維度關(guān)聯(lián)度。通過計(jì)算維度關(guān)聯(lián)度與維度密度可以得到維度準(zhǔn)確性，并依據(jù)維度確定性得到確定維度。用Clique算法對確定的數(shù)據(jù)集聚類。

算法2?UDDClique（）。

輸入?數(shù)據(jù)集C={d1，d2，…，dn};

輸出?聚類結(jié)果。

程序前

begin

1） 以維度作為豎軸，以數(shù)據(jù)作為橫軸生成數(shù)據(jù)矩陣;

2） 根據(jù)式（5），計(jì)算維度相關(guān)度;

3） 根據(jù)式（6），計(jì)算維度關(guān)聯(lián)度;

4） 根據(jù)式（7），計(jì)算維度確定性;

5） 不斷循環(huán)步驟2）～4），直到得到所有維度的確定性;

6） 根據(jù)式（8），計(jì)算確定性閾值，并根據(jù)閾值選出確定維度存入集合CE;

7） Clique（CE）;

end

程序后

由文獻(xiàn)[23]可得步驟7）Clique算法的時(shí)間復(fù)雜度為O（ck+kn），k為數(shù)據(jù)集維數(shù)，n為數(shù)據(jù)集數(shù)據(jù)總數(shù)，c為簇的個(gè)數(shù)。假設(shè)數(shù)據(jù)集擁有k個(gè)維度，擁有n個(gè)數(shù)據(jù)：步驟1）生成矩陣的時(shí)間復(fù)雜度為O（n）;步驟2）～5）得到每個(gè)維度的維度相關(guān)度、維度關(guān)聯(lián)度、維度確定性所需要的時(shí)間復(fù)雜度為O（n）;步驟6）計(jì)算維度確定性閾值并得到確定維度的時(shí)間復(fù)雜度為O（k），那么算法2的時(shí)間復(fù)雜度為O（（c+1）k+（k+2）n）。

3?值不確定子空間聚類算法

2.1節(jié)、2.2節(jié)主要分析了高維不確定數(shù)據(jù)中的數(shù)據(jù)集維度不確定和部分?jǐn)?shù)據(jù)維度不確定兩種情況。本章針對高維不確定數(shù)據(jù)中的數(shù)值模糊和數(shù)據(jù)值缺失問題，分別提出了相應(yīng)的聚類算法。

3.1?數(shù)據(jù)值模糊聚類

在高維數(shù)據(jù)中的模糊數(shù)據(jù)會(huì)降低聚類精度，增加聚類的難度。本文提出結(jié)合KNN算法的子空間算法UFVClique，解決高維數(shù)據(jù)集中數(shù)據(jù)模糊的聚類問題。

高維不確定數(shù)據(jù)中的值模糊問題為主要的研究目標(biāo)，不確定數(shù)據(jù)的維數(shù)是確定的。不確定數(shù)據(jù)由一組概率樣本數(shù)據(jù)點(diǎn)定義，概率樣本數(shù)由隨機(jī)采樣生成。針對高維不確定數(shù)據(jù)集，采用先劃分子空間再將不確定數(shù)據(jù)確定化的方法，減少計(jì)算步驟。針對各個(gè)子空間中的不確定數(shù)據(jù)，采用式（2）計(jì)算不確定數(shù)據(jù)的距離，并結(jié)合KNN算法的網(wǎng)格劃分方法，將不確定數(shù)據(jù)確定化。在得到確定數(shù)據(jù)集后由Clique算法對確定數(shù)據(jù)集聚類。如圖1所示， 圖中不確定數(shù)據(jù)沒有確定的位置。

圖中不確定數(shù)據(jù)沒有確定的位置，實(shí)線標(biāo)識(shí)范圍是不確定數(shù)據(jù)可能出現(xiàn)的范圍，點(diǎn)代表確定數(shù)據(jù)。

根據(jù)Clique算法首先劃分子空間并對子空間作網(wǎng)格劃分處理。由于本節(jié)中不確定數(shù)據(jù)的維度是確定的，子空間劃分與網(wǎng)格劃分過程并不會(huì)受到不確定數(shù)據(jù)的影響。

采用KNN算法在子空間內(nèi)查找距離不確定數(shù)據(jù)最近的K個(gè)數(shù)據(jù)，并根據(jù)這K個(gè)數(shù)據(jù)的網(wǎng)格歸屬情況劃分不確定數(shù)據(jù)。不確定數(shù)據(jù)與確定數(shù)據(jù)的距離計(jì)算由式（2）給出。根據(jù)不確定數(shù)據(jù)到確定數(shù)據(jù)的距離，可以得到不確定數(shù)據(jù)對于確定數(shù)據(jù)所屬網(wǎng)格的網(wǎng)格歸屬度，公式為：

griBl（i，s）=∏k∈gri（s）rd（i，K） （9）

其中：i為不確定數(shù)據(jù)，s為網(wǎng)格，K為網(wǎng)格內(nèi)的確定數(shù)據(jù)，d（i，K）為不確定數(shù)據(jù)i到確定數(shù)據(jù)K的距離，r為網(wǎng)格最長邊長度。判斷一個(gè)不確定數(shù)據(jù)是否屬于一個(gè)網(wǎng)格的條件有兩個(gè)：一是，網(wǎng)格中的數(shù)據(jù)與不確定數(shù)據(jù)的距離;二是，網(wǎng)格中數(shù)據(jù)的個(gè)數(shù)。只有當(dāng)網(wǎng)格中的數(shù)據(jù)距離不確定數(shù)據(jù)足夠近而且足夠多時(shí)，才能判定不確定數(shù)據(jù)屬于這個(gè)網(wǎng)格。式（9）根據(jù)網(wǎng)格鄰近性，以網(wǎng)格邊長作為距離比較標(biāo)準(zhǔn)，使不相鄰網(wǎng)格的網(wǎng)格歸屬度小于1。通過Clique算法的密集網(wǎng)格選取過程將稀疏網(wǎng)格排除。在網(wǎng)格密度與網(wǎng)格距離上保證了不確定數(shù)據(jù)網(wǎng)格劃分的準(zhǔn)確性。

通過計(jì)算不確定數(shù)據(jù)與K個(gè)最近鄰數(shù)據(jù)所屬網(wǎng)格的網(wǎng)格歸屬度得到不確定數(shù)據(jù)的網(wǎng)格歸屬度集合：

bel（i）=

{griBl（i，s1），griBl（i，s2），…，griBl（i，sK）}（10）

其中：griBl（i，sK）為不確定數(shù)據(jù)在網(wǎng)格sK的網(wǎng)格歸屬度。根據(jù)不確定數(shù)據(jù)的網(wǎng)格歸屬度集合，計(jì)算Max（griBl（i，sK））是否大于1：如果大于1，那么將不確定數(shù)據(jù)數(shù)據(jù)劃分到這個(gè)網(wǎng)格中;如果小于1，那么不確定數(shù)據(jù)為孤立數(shù)據(jù)，不作劃分。

采用KNN算法的不確定數(shù)據(jù)網(wǎng)格劃分方法將所有不確定數(shù)據(jù)劃分到相應(yīng)網(wǎng)格中，生成確定數(shù)據(jù)集，并采用Clique算法聚類。針對不確定數(shù)據(jù)采用KNN算法將不確定數(shù)據(jù)確定化，可以最大限度地避免由不確定數(shù)據(jù)引起的聚類精度低的問題。根據(jù)k個(gè)數(shù)據(jù)的分布情況判斷不確定數(shù)據(jù)的分布，比只根據(jù)期望距離判斷不確定數(shù)據(jù)的分布準(zhǔn)確性高。Clique算法可以有效地針對確定的高維數(shù)據(jù)集聚類。

算法3的具體步驟：按照Clique算法選取密集維度生成子空間并在子空間內(nèi)劃分網(wǎng)格。采用KNN算法結(jié)合式（9）、（10）計(jì)算不確定數(shù)據(jù)的網(wǎng)格歸屬，利用網(wǎng)格的鄰近性，將不確定數(shù)據(jù)確定化。當(dāng)數(shù)據(jù)集中不存在不確定數(shù)據(jù)時(shí)，采用Clique算法將數(shù)據(jù)集聚類。

算法3?UFVClique（）。

輸入?數(shù)據(jù)集C={d1，d2，…，dn};

輸出?聚類結(jié)果。

程序前

begin

1）自下而上地查找密集單元;

2）將子空間內(nèi)的數(shù)據(jù)分為確定數(shù)據(jù)集CE與不確定數(shù)據(jù)集UCE;

3）根據(jù)距離計(jì)算公式計(jì)算不確定數(shù)據(jù)的K個(gè)最近鄰數(shù)據(jù);

4）根據(jù)式（9）、（10）計(jì)算不確定數(shù)據(jù)的網(wǎng)格歸屬度以及網(wǎng)格歸屬度集合;

5）根據(jù)網(wǎng)格歸屬度集合將不確定數(shù)據(jù)劃分到相應(yīng)網(wǎng)格，并從UCE集合中刪除;

6）不斷循環(huán)3）～5），直到UCE集合為空;

7） Clique（CE）;

end

程序后

步驟1）的時(shí)間復(fù)雜度為O（n），n為數(shù)據(jù)集中數(shù)據(jù)個(gè)數(shù)。步驟2：劃分?jǐn)?shù)據(jù)集的時(shí)間復(fù)雜度為O（n）。由文獻(xiàn)[22]可得，步驟3）KNN的時(shí)間復(fù)雜度為O（nlogn），n為數(shù)據(jù)集數(shù)據(jù)總數(shù)。假設(shè)數(shù)據(jù)集的維數(shù)為k，數(shù)據(jù)規(guī)模為n，存在m個(gè)不確定數(shù)據(jù)。那么步驟3）～6）查找m個(gè)不確定數(shù)據(jù)的KNN時(shí)間復(fù)雜度為O（mnlogn），將不確定數(shù)據(jù)確定化的時(shí)間復(fù)雜度為O（k）。由文獻(xiàn)[23]可得步驟7）Clique算法的時(shí)間復(fù)雜度為O（ck+kn）。算法3的時(shí)間復(fù)雜度為O（（c+1）k+（k+1）n+mnlogn）。

3.2?數(shù)據(jù)值模糊聚類

數(shù)據(jù)在錄入時(shí)會(huì)產(chǎn)生缺失值，導(dǎo)致數(shù)據(jù)的確定性下降。傳統(tǒng)處理數(shù)據(jù)缺失值的方法有4種：丟棄缺失值、填補(bǔ)缺失值、預(yù)測缺失值和直接分析。針對存在缺失值的高維數(shù)據(jù)集聚類算法，提出UMVClique算法，采用KNN的方式填補(bǔ)缺失值生成確定數(shù)據(jù)集，采用Clique算法對確定的數(shù)據(jù)集聚類。

定義9?數(shù)據(jù)維度缺失度。存在高維缺失值a，a在n個(gè)維度存在空值，那么n就是a的數(shù)據(jù)維度缺失度，簡稱缺失度。

根據(jù)定理1可以推出，k-1維確定數(shù)據(jù)的最近鄰也是k維不確定數(shù)據(jù)的最近鄰，可以根據(jù)不確定數(shù)據(jù)在確定維度的K個(gè)最近鄰，填補(bǔ)不確定數(shù)據(jù)的缺失值，保障了數(shù)據(jù)集的完整，避免了聚類精度的丟失。UMVClique算法主要分為3個(gè)步驟：首先根據(jù)Clique算法生成子空間，其次將子空間內(nèi)的缺失值填補(bǔ)，最后采用Clique算法對確定數(shù)據(jù)集聚類。

首先計(jì)算不確定數(shù)據(jù)的缺失度，并將不確定數(shù)據(jù)按照缺失度從小到大的順序排列。缺失度高的數(shù)據(jù)填補(bǔ)難度高，同理缺失度高的數(shù)據(jù)填補(bǔ)準(zhǔn)確度低，先對缺失度低的不確定數(shù)據(jù)填補(bǔ)，可以在一定程度上保障填補(bǔ)的準(zhǔn)確性并縮短填補(bǔ)時(shí)間。

查找距離不確定數(shù)據(jù)在確定維度的K個(gè)最近的數(shù)據(jù)，m代表密集維度的個(gè)數(shù)，n代表不確定數(shù)據(jù)所缺失的維數(shù)。由于不確定數(shù)據(jù)在m-n維中的值是確定的，采用歐氏距離計(jì)算在單個(gè)維度中兩個(gè)數(shù)據(jù)的距離，那么在m-n維中不確定數(shù)據(jù)與確定數(shù)據(jù)的距離計(jì)算公式為：

dm-n（u，c）=∑m-ni=1（ui-ci）2（11）

其中：ui為不確定數(shù)據(jù)在第i維的值，ci為確定數(shù)據(jù)在第i維的值。

根據(jù)式（11）計(jì)算不確定數(shù)據(jù)在m-n維的K個(gè)最近鄰數(shù)據(jù)，并根據(jù)這K個(gè)數(shù)據(jù)填補(bǔ)第n維中缺失數(shù)據(jù)，計(jì)算公式為：

dj（u）=1K∑m-ni=1ai（12）

其中j為不確定數(shù)據(jù)所在的存在空值的維度，根據(jù)式（12）將缺失值填補(bǔ)。

采用式（11）計(jì)算不確定數(shù)據(jù)在無缺失值的維度的K近鄰，并根據(jù)式（12）填補(bǔ)不確定數(shù)據(jù)，生成確定數(shù)據(jù)集，采用Clique算法將確定數(shù)據(jù)集聚類，Clique算法可以有效地對高維數(shù)據(jù)集聚類。

算法4的具體步驟：先將數(shù)據(jù)集中的缺失部分填補(bǔ)，再將數(shù)據(jù)集聚類。填補(bǔ)的過程為，先將數(shù)據(jù)集分為兩個(gè)部分，一部分為缺失值，另一部分為確定數(shù)據(jù)。將缺失值按缺失度從小到大的順序排列，并按順序?qū)⑷笔е蹬c確定數(shù)據(jù)集中的數(shù)據(jù)比較，將相似度最大的K個(gè)確定數(shù)據(jù)的均值填補(bǔ)到缺失值中，得到確定數(shù)據(jù)并放入確定數(shù)據(jù)集中，直到?jīng)]有缺失值存在時(shí)再對數(shù)據(jù)集聚類。

算法4?UMVClique（）。

輸入?數(shù)據(jù)集C={d1，d2，…，dn};

輸出?聚類結(jié)果。

程序前

begin

1）將數(shù)據(jù)集分為兩部分一部分是確定數(shù)據(jù)集CE，另一部分是不確定數(shù)據(jù)集UCE;

2） 計(jì)算UCE集合中所有數(shù)據(jù)的缺失度;

3） 按缺失度從小到大的順序?qū)CE集合中的數(shù)據(jù)排序;

4） 結(jié)合式（11），按順序找出不確定數(shù)據(jù)的K個(gè)最近鄰;

5） 結(jié)合式（12）計(jì)算K個(gè)最近鄰在缺失值所在維度的數(shù)據(jù)均值M。

6） 將M填入缺失值，填補(bǔ)后的缺失值從UCE集合中刪除，填入CE集合中;

7） 不斷循環(huán)步驟4）～6），直到UCE集合為空;

8） Clique（CE）;

end

程序后

由文獻(xiàn)[23]可得，步驟8）Clique算法的時(shí)間復(fù)雜度為O（ck+kn），k為數(shù)據(jù)集維數(shù)，n為數(shù)據(jù)集數(shù)據(jù)總數(shù)，c為簇的個(gè)數(shù)。由文獻(xiàn)[22]可得，步驟4）KNN的時(shí)間復(fù)雜度為O（nlogn），n為數(shù)據(jù)集數(shù)據(jù)總數(shù)。步驟1）的時(shí)間復(fù)雜度為O（n）。步驟2）～3）的時(shí)間復(fù)雜度為O（m）。步驟4）～7）計(jì)算不確定數(shù)據(jù)在k-1維的KNN數(shù)據(jù)的時(shí)間復(fù)雜度為O（m（k-1）×（n-1）logn）。填補(bǔ)缺失值的時(shí)間復(fù)雜度為O（km），那么算法4的時(shí)間復(fù)雜度為O（m（（k-1）（n-1）logn+k+2）+ck+（k+1）n）。

4?基于子空間的復(fù)雜高維不確定數(shù)據(jù)聚類算法

在2.1節(jié)與2.2節(jié)中，針對部分?jǐn)?shù)據(jù)維度不確定與數(shù)據(jù)集維度不確定的情況，分別采用均值和方差與維度相似的方法將不確定數(shù)據(jù)確定化，并由Clique算法對確定的數(shù)據(jù)集聚類。在3.1節(jié)、3.2節(jié)中，針對數(shù)據(jù)值模糊與缺失值的情況，采用KNN算法將不確定數(shù)據(jù)確定化，并采用Clique算法對確定數(shù)據(jù)集聚類。

針對復(fù)雜的高維不確定數(shù)據(jù)提出UClique算法。算法可以對復(fù)雜的高維不確定數(shù)據(jù)聚類，結(jié)合算法1、2、3、4各自的特點(diǎn)對復(fù)雜的高維不確定數(shù)據(jù)聚類。

針對復(fù)雜的高維不確定數(shù)據(jù)，按照先確定維度后確定數(shù)據(jù)的方式。高維數(shù)據(jù)中維度是數(shù)據(jù)值的載體，先對維度確定化有利于減少計(jì)算步驟。在將不確定維度確定化的過程中，首先確定數(shù)據(jù)集的維度再確定部分?jǐn)?shù)據(jù)的維度。高維數(shù)據(jù)集聚類過程中首先要降維，不確定維度確定化過程可以和降維過程同時(shí)進(jìn)行，有利于減小算法的時(shí)間復(fù)雜度。高維模糊數(shù)據(jù)的聚類涉及大量的期望距離計(jì)算，對缺失值的聚類過程比對模糊數(shù)據(jù)的聚類要快，而且填補(bǔ)缺失值是在劃分子空間之后在網(wǎng)格化分之前，模糊數(shù)據(jù)確定化是在網(wǎng)格化分之后。所以在將不確定數(shù)據(jù)值的確定化過程中，先填補(bǔ)缺失值，后將模糊數(shù)據(jù)網(wǎng)格化。例如在數(shù)據(jù)集維度不確定而且存在缺失值時(shí)，可以首先采用UDDClique算法得到確定的維度，再采用UMVClique算法將缺失值填補(bǔ)得到確定數(shù)據(jù)集，最后采用Clique算法將確定數(shù)據(jù)集聚類。同樣在其他的情況混合出現(xiàn)時(shí)，可以分別采用相應(yīng)的解決方法對數(shù)據(jù)聚類。

算法5的具體步驟：首先判斷數(shù)據(jù)集是否存在維度不確定，如果有判斷是數(shù)據(jù)集的維度不確定還是部分?jǐn)?shù)據(jù)維度不確定。數(shù)據(jù)集維度不確定，采用算法2; 部分?jǐn)?shù)據(jù)不確定采用算法1。如果只是數(shù)據(jù)不確定，判斷是數(shù)據(jù)模糊還是有空值，如果是數(shù)據(jù)模糊，采用算法3; 如果是有缺失值，采用算法4。流程如圖2所示。

算法5?UClique（）。

輸入?數(shù)據(jù)集C={d1，d2，…，dn};

輸出?聚類結(jié)果。

程序前

begin

1） 判斷C中是否存在不確定維度，是則執(zhí)行步驟2），否則執(zhí)行步驟3）;

2） 采用UDDClique算法得到確定維度;

3） 判斷C中是否存在維度不確定數(shù)據(jù)，是則執(zhí)行步驟4），否則執(zhí)行步驟5）;

4） 采用UDPClique算法得到不確定數(shù)據(jù)的確定維度;

5） 判斷C中是否存在缺失數(shù)據(jù)，是則執(zhí)行步驟6），否則執(zhí)行步驟7）;

6） 采用UMVClique算法填補(bǔ)缺失值;

7） 判斷C中是否存在模糊數(shù)據(jù)，是則執(zhí)行步驟8），否則執(zhí)行步驟9）;

8） 采用UFVClique算法將不確定數(shù)據(jù)劃分到確定網(wǎng)格中;

9） Clique（C）;

end

程序后

假設(shè)數(shù)據(jù)集的維數(shù)為s，數(shù)據(jù)規(guī)模為n，存在m個(gè)不確定數(shù)據(jù)。根據(jù)UDPClique算法的時(shí)間復(fù)雜度，那么步驟4）和步驟9）的時(shí)間復(fù)雜度為O（cs+sn+mn+km）。根據(jù)UDDClique算法的時(shí)間復(fù)雜度，那么步驟2）和步驟9）的時(shí)間復(fù)雜度為O（k+n+ck+kn）。根據(jù)UFVClique算法的時(shí)間復(fù)雜度，那么步驟8）和步驟9）的時(shí)間復(fù)雜度為O（（c+1）k+（k+1）n+mnlogn）。根據(jù)UMVClique算法的時(shí)間復(fù)雜度，那么步驟6）和步驟9）的時(shí)間復(fù)雜度為O（m（（k-1）（n-1）logn+k+2）+ck+（k+1）n）。由于步驟1）、3）、5）、7）為判斷條件時(shí)間復(fù)雜度為O（1）。那么算法5的時(shí)間復(fù)雜度為：O（m（（k-1）（n-1）logn+k+2）+ck+（k+1）n）。

5?實(shí)驗(yàn)

為了檢驗(yàn)本文算法的準(zhǔn)確性和效率，本文的實(shí)驗(yàn)環(huán)境是2.5GHz Intel i5 CPU，內(nèi)存4GB，操作系統(tǒng)為Window7。實(shí)驗(yàn)數(shù)據(jù)采用的是UCI（University of CaliforniaIrvine）數(shù)據(jù)庫中的數(shù)據(jù)集Iris、Wine、Seed、Zoo。由于UCI數(shù)據(jù)集是經(jīng)典的測試機(jī)器學(xué)習(xí)數(shù)據(jù)集，具有信息完整、數(shù)據(jù)種類多的特點(diǎn)，適合根據(jù)不同的實(shí)驗(yàn)類型測試算法的各方面數(shù)據(jù)。本文主要考察高維數(shù)據(jù)集測試算法在高維數(shù)據(jù)中的表現(xiàn)，還被用于生成不同類型的不確定數(shù)據(jù)集，測試算法針對存在不確定數(shù)據(jù)的高維數(shù)據(jù)集中的表現(xiàn)。數(shù)據(jù)集的類別數(shù)與實(shí)例數(shù)由表1給出。

本文采用不同的方式生成不同的不確定數(shù)據(jù)集，以對算法進(jìn)行多方面的測量。由于ENCLUS算法針對不確定數(shù)據(jù)能夠得到良好的聚類結(jié)果，F(xiàn)DBSCANSMDM（Fast DBSCAN algorithmSMDM）算法針對高維數(shù)據(jù)能夠得到良好的聚類結(jié)果，實(shí)驗(yàn)過程中選取文獻(xiàn)[15]中的ENCLUS算法與文獻(xiàn)[14]中的FDBSCANSMDM算法作為比較算法。分別測量算法在不同的不確定數(shù)據(jù)集之下聚類精度、CPU時(shí)間、算法的伸縮性以及抗噪聲能力。每組實(shí)驗(yàn)重復(fù)10次取均值作為最終的實(shí)驗(yàn)結(jié)果，并提供方差作為對算法準(zhǔn)確魯棒性的參考。

表2是UClique算法，F(xiàn)DBSCANSMDM算法與ENCLUS算法在UCI數(shù)據(jù)集上的比較。由實(shí)驗(yàn)結(jié)果可以看出，ENCLUS算法、FDBSCANSMDM算法和UClique算法按照準(zhǔn)確率由高到低的順序依次排列，三個(gè)算法準(zhǔn)確率差距小，從整體上看三個(gè)算法的準(zhǔn)確率都很高。而且三個(gè)算法的準(zhǔn)確率方差較小，算法具有較好的魯棒性。但是在所用時(shí)間上，ENCLUS算法、UClique算法和FDBSCANSMDM算法按照所用時(shí)間從短到長的順序排列。UClique算法存在大量將不確定數(shù)據(jù)確定化步驟，例如針對數(shù)據(jù)集維度不確定時(shí)的維度選擇方法等，可以將不確定數(shù)據(jù)確定化，起到規(guī)范數(shù)據(jù)集的作用。但是在針對少量不確定數(shù)據(jù)存在的數(shù)據(jù)集，起到的作用小，效果不明顯，大量時(shí)間用在不確定數(shù)據(jù)確定化和距離函數(shù)計(jì)算上。FDBSCANSMDM采用雙加權(quán)的方式對不確定數(shù)據(jù)聚類，對高維數(shù)據(jù)不敏感，面對高維不確定數(shù)數(shù)據(jù)集，所消耗的時(shí)間較長而且聚類效果不明顯。

圖3是最近鄰個(gè)數(shù)K的取值對UClique算法精度影響的實(shí)驗(yàn)結(jié)果，可以看出：在K值取5～15時(shí)，精度單調(diào)遞增;在K取20時(shí)，精度下降。由此可以推斷出K的最佳取值范圍在10～15。

采用4種方式生成4種不同的不確定數(shù)據(jù)集。不確定數(shù)據(jù)集1為維度不確定數(shù)據(jù)集，在確定數(shù)據(jù)集中任取2個(gè)維度a，b。將維度a中的數(shù)據(jù)任意去掉一半生成新的維度a′，將維度b中的任意一半添加到b中生成新的維度b′，將維度a中的任意一半數(shù)據(jù)與維度b中的任意一半數(shù)據(jù)混合生成維度c′，并任取（0，1]中任意數(shù)值作為維度存在度映射到數(shù)據(jù)集的所有維度上。不確定數(shù)據(jù)集2為部分?jǐn)?shù)據(jù)維度不確定數(shù)據(jù)集，在確定數(shù)據(jù)集中任取k個(gè)數(shù)據(jù)生成不確定數(shù)據(jù)。k為數(shù)據(jù)集維數(shù)，任?。?，1]中任意數(shù)值作為維度存在度映射到每個(gè)不確定數(shù)據(jù)所存在的維度上。不確定數(shù)據(jù)集3為數(shù)值模糊數(shù)據(jù)集，在每個(gè)維度上任取數(shù)據(jù)集中2%的數(shù)據(jù)按照文獻(xiàn)[24]中不確定數(shù)據(jù)集生成方法生成數(shù)值模糊數(shù)據(jù)集。不確定數(shù)據(jù)集4為缺失值數(shù)據(jù)集，在每個(gè)維度上任取1%的數(shù)據(jù)將其數(shù)值定義為缺失值。

圖4（a）是三種算法對4種高維不確定數(shù)據(jù)集的聚類精度實(shí)驗(yàn)結(jié)果。數(shù)據(jù)集1是高維維度不確定數(shù)據(jù)集，數(shù)據(jù)集2是高維部分?jǐn)?shù)據(jù)維度不確定數(shù)據(jù)集，數(shù)據(jù)集3是高維值模糊數(shù)據(jù)集，數(shù)據(jù)集4是高維缺失值數(shù)據(jù)集。從圖中可以看出，在數(shù)據(jù)集1～3中算法聚類精度按照Uclique、FDBSCANSMDM和ENCLUS從高到低的順序排列，而數(shù)據(jù)集4中稍有不同。4個(gè)數(shù)據(jù)集都是高維不確定數(shù)據(jù)集，ENCLUS算法適合對高維數(shù)據(jù)集的聚類，針對不確定數(shù)據(jù)聚類效果差，而FDBSCANSMDM算法適合針對不確定數(shù)據(jù)集聚類，針對高維數(shù)據(jù)聚類效果較差。數(shù)據(jù)集4是缺失值數(shù)據(jù)集，F(xiàn)DBSCANSMDM和ENCLUS算法的聚類效果較差。UClique算法針對這4種數(shù)據(jù)集可以有效地聚類，在聚類精度上UClique算法最高。

圖4（b）是三個(gè)算法在4個(gè)不確定數(shù)據(jù)集上的時(shí)間實(shí)驗(yàn)，在所用時(shí)間上FDBSCANSMDM、UClique和ENCLUS按照從多到少的順序排列。UClique算法中計(jì)算期望距離和將不確定數(shù)據(jù)確定化需要大量的計(jì)算，占用了較長時(shí)間，而FDBSCANSMDM算法中對加權(quán)等步驟占用了較長時(shí)間，F(xiàn)DBSCANSMDM針對高維數(shù)據(jù)聚類效果較差。

采用仿真數(shù)據(jù)集來進(jìn)行接下來的實(shí)驗(yàn)，仿真數(shù)據(jù)集的特點(diǎn)是用戶可以通過輸入?yún)?shù)來控制數(shù)據(jù)集的維度、結(jié)構(gòu)、大小和在各個(gè)維度上的取值范圍等等。分別測試數(shù)據(jù)規(guī)模、噪聲、維數(shù)對算法精度的影響，實(shí)驗(yàn)結(jié)果如圖5。

由圖5所示，在數(shù)據(jù)規(guī)模不斷增加的情況下，三種算法的聚類精度都在不斷下降，并逐漸收斂。UClique算法與ENCLUS算法采用子空間聚類的方法，對于大規(guī)模數(shù)據(jù)有一定的免疫能力，F(xiàn)DBSCANSMDM算法也對數(shù)據(jù)規(guī)模不敏感，所以在數(shù)據(jù)規(guī)模達(dá)到一定程度之后聚類精度會(huì)逐漸平穩(wěn)， 可以得出UClique算法伸縮性良好。

在數(shù)據(jù)規(guī)模與維數(shù)不變的情況下，噪聲不斷增加，三種算法的精度按UClique、FDBSCANSMDM和ENCLUS從大到小的順序排列。在噪聲不斷增加的情況下，三種算法精度都有不同程度的下降但是整體下降幅度小，具有較好的穩(wěn)定性?？梢缘贸鯱Clique算法對噪聲有一定的耐受性。

在數(shù)據(jù)規(guī)模不變的情況下，維數(shù)不斷增加，三種算法的精度按UClique、FDBSCANSMDM和ENCLUS從大到小的順序排列。在維數(shù)不斷增加的情況下，三種算法的精度都有不同程度的下降但是整體下降幅度小，聚類精度一直維持在較高的標(biāo)準(zhǔn)。可以得出UClique算法的維數(shù)伸縮性良好。

6?結(jié)語

針對高維不確定數(shù)據(jù)中的不同情況分別提出了解決方法：針對高維數(shù)據(jù)中部分?jǐn)?shù)據(jù)維度不確定的情況，提出了UDPClique算法，采用結(jié)合均值和方差將不確定數(shù)據(jù)確定化;針對數(shù)據(jù)集維度不確定的高維不確定數(shù)據(jù)提出了UDDClique算法，采用計(jì)算維度相似度的方式得到數(shù)據(jù)集的確定維度;針對值范圍模糊的高維不確定數(shù)據(jù)提出UFVClique算法，采用KNN算法判斷不確定數(shù)據(jù)的所歸屬的網(wǎng)格;針對含有缺失值高維不確定數(shù)據(jù)提出了UMVClique算法，采用KNN算法填補(bǔ)缺失值。最終采用Clique算法對確定數(shù)據(jù)集聚類。最后提出了UClique算法，針對復(fù)雜的高維不確定數(shù)據(jù)聚類。經(jīng)理論分析與實(shí)驗(yàn)驗(yàn)證，本文算法可以很好地對高維不確定數(shù)據(jù)聚類，算法的伸縮性與抗噪聲能力較好。

參考文獻(xiàn) （References）

[1]?CRISTBAL T， PADRN G， QUESADAARENCIBIA A， et al. Systematic approach to analyze travel time in roadbased mass transit systems based on data mining[J]. IEEE Access， 2018， 6：32861-32873.

[2]? JEZEWSKI M， CZABANSKI R， LESKI J M. Fuzzy classifier based on clustering with pairs ofεhyperballs and its application to support fetal state assessment[J]. Expert Systems with Applications， 2019， 118（15）：109-126.

[3]? CHARLES V， TSOLAS I E， GHERMAN T. Satisficing data envelopment analysis： a Bayesian approach for peer mining in the banking sector[J]. Annals of Operations Research， 2018，269（1/2）： 81-102.

[4]? FERRERO E， AGARWAL P. Connecting genetics and gene expression data for target prioritisation and drug repositioning[J]. Biodata Mining， 2018， 11（1）：7.

[5]? FRNTI P， SIERANOJA S.Kmeans properties on six clustering benchmark datasets[J]. Applied Intelligence， 2018， 48（12）： 4743-4759.

[6]? TRIPATHI A， PANWAR K. Modified CURE algorithm with enhancement to identify number of clusters[J]. International Journal of Artificial Intelligence and Soft Computing， 2016，5（3）：226-240.

[7]? ZHENG Z， MA Y， ZHENG H， et al. UGC： realtime， ultrarobust feature correspondence via unilateral gridbased clustering[J]. IEEE Access， 2018， 6： 55501-55508.

[8]? SEYEDI S A， LOTFI A， MORADI P， et al. Dynamic graphbased label propagation for density peaks clustering[J]. Expert Systems with Applications，2019， 115： 314-328.

[9]? YANG M S， LAI C Y. A robust EM clustering algorithm for Gaussian mixture models [J]. Pattern Recognition， 2012， 45（11）：3950-3961.

[10]? BRODINOV??， ZAHARIEVA M， FILZMOSER P， et al. Clustering of imbalanced highdimensional media data[J]. Advances in Data Analysis & Classification， 2017， 12（2）：261-284.

[11]? ZHU W， YAN Y. Joint linear regression and nonnegative matrix factorization based on selforganized graph for image clustering and classification[J].IEEE Access， 2018， 6： 38820-38834.

[12]? AAMARI E， LEVRARD C. Stability and minimax optimality of tangential delaunay complexes for manifold reconstruction[J]. Discrete & Computational Geometry， 2018， 59（4）： 923-971.

[13]? WANG Y， DUAN X， LIU X， et al. A spectral clustering method with semantic interpretation based on axiomatic fuzzy set theory[J]. Applied Soft Computing， 2018， 64： 59-74.

[14]? LIU H， ZHANG X， ZHANG X， et al. Selfadapted mixture distance measure for clustering uncertain data[J]. KnowledgeBased Systems， 2017， 126：33-47.

[15]? GOYAL P， KUMARI S， SINGH S， et al. A parallel framework for gridbased bottomup subspace clustering[C]// Proceedings of the 2016 IEEE International Conference on Data Science and Advanced Analytics. Piscataway： IEEE， 2016：331-340.

[16]? ZHANG C，F(xiàn)U H， HU Q， et al. Generalized latent multiview subspace clustering[EB/OL].[2018-03-20]. https：//ieeexplore.ieee.org/document/8502831.

[17]? ZHU Y， TING K M， CARMAN M J . Grouping points by shared subspaces for effective subspace clustering[J]. Pattern Recognition， 2018， 83： 230-244.

[18]? LI X， LU Q， DONG Y， et al. Robust subspace clustering by cauchy loss function[J]. IEEE Transactions on Neural Networks and Learning Systems， 2018， 30（7）： 2067-2078.

[19]? CHEN H， WANG W， FENG X. Structured sparse subspace clustering with groupingeffectwithincluster[J]. Pattern Recognition， 2018， 10（83）：107-118.

[20]? 范虹，侯存存，朱艷春，等.煙花算法優(yōu)化的軟子空間MR圖像聚類算法[J].軟件學(xué)報(bào)，2017，28（11）：3080-3093. （FAN H， HOU C C， ZHU Y C， et al. Soft subspace algorithm for MR image clustering based on fireworks optimization algorithm[J]. Journal of Software， 2017， 28（11）： 3080-3093.）

[21]? 傅文進(jìn)，吳小俊.基于l_2范數(shù)的加權(quán)低秩子空間聚類[J].軟件學(xué)報(bào)，2017，28（12）：3347-3357.（FU W J， WU X J. Weighted low rank subspace clustering based on l_2 norm[J]. Journal of Software， 2017， 28（12）： 3347-3357.）

[22]? SEIDL T. Nearest neighbor classification[M]// Data Mining in Agriculture. Berlin： Springer， 2009： 83-106.

[23]? ALTMAN N S. An introduction to kernel and nearestneighbor nonparametric regression[J]. American Statistician， 1992， 46（3）：175-185.

[24]? 肖宇鵬，何云斌，萬靜，等.基于模糊C均值的空間不確定數(shù)據(jù)聚類[J].計(jì)算機(jī)工程，2015，41（10）：47-52.（XIAO Y P， HE Y B， WAN J， et al. Clustering of space uncertain data based on fuzzy Cmeans[J]. Computer Engineering， 2015， 41（10）： 47-52.）

[25]? 周曉云， 孫志揮， 張柏禮， 等. 高維數(shù)據(jù)流子空間聚類發(fā)現(xiàn)及維護(hù)算法[J]. 計(jì)算機(jī)研究與發(fā)展， 2006， 43（5）：834-840.（ZHOU X Y， SUN Z H， ZHANG B L，et al. An efficient discovering and maintenance algorithm of subspace clustering over high dimensional data streams[J]. Journal of Computer Research and Development， 2006， 43（5）： 834-840.）