高維不確定數據的子空間聚類算法

萬靜 鄭龍君 何云斌 李松

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

關鍵詞：高維;不確定;Clique算法;K近鄰

中圖分類號：TP311.13

文獻標志碼：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?引言

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

高維數據的聚類容易受到維度災難的影響，傳統的聚類方法不能有效地對高維數據聚類。經過國內外學者的不斷研究，高維數據的聚類方法可以被分為以下3種：基于降維的聚類[12]、基于子空間的聚類和其他的聚類方法[13]。子空間聚類方法是選出部分數據作為高維數據的子空間，在子空間上聚類代替在整個數據集上聚類。子空間聚類在加權方法上分為軟子空間聚類算法與硬子空間聚類算法，在搜索方法上可分為自下而上的子空間聚類算法與自上而下的子空間聚類算法。

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

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

本文的貢獻主要有4個方面：

1）針對高維不確定數據中，部分數據維度不確定的情況提出了針對維度不確定數據的Clique（Clique for Uncertain Dimension of Partial Data， UDPClique）算法，根據不同維度的維度特點，將不確定數據劃分到相應維度。

2）針對數據集維度不確定的高維不確定數據提出針對維度不確定數據集的Clique（Clique for Uncertain Dimensions of Datasets， UDDClique）算法，根據維度之間的關聯程度判斷不確定維度的確定程度，得到確定的維度。

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

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

1?基礎知識

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

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

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

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

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

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

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

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

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

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

定義6?多維度關聯[26]。維度是具有某一相同特征數據的集合，多維度則是從不同層次、不同角度呈現數據，數據之間可以有交叉。

2?維度不確定聚類算法

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

2.1?部分數據維度不確定的子空間聚類算法

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

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

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

假設存在不確定數據ui={a1，a2，…，aj}，其中i代表不確定數據在數據集中的位置，a1，a2，…，aj代表不確定數據j個維度的值。可以通過計算不確定數據在各個維度與維度均值的差異來判斷不確定數據的維度劃分。差異的計算公式為：

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

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

將數據集的維度按照方差大小排列，方差計算公式為：

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

其中：Vak為第k個維度的方差，dk（i）表示第k個維度中第i個數據的值，k為第k個維度的均值，nk表示第k個維度的數據總數。

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

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

算法1?UDPClique（）。

輸入?數據集C={d1，d2，…，dn};

輸出?聚類結果。

程序前

begin

1） 將C中的確定數據存入CE集合，將C中的不確定數據存入UCE集合;

2） 將CE集合中的數據按照維度劃分維度集合;

3） 根據距離計算式（4）計算各個維度集合的方差;

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

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

6） 將不確定數據從UCE集合中刪除;

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

8） Clique（CE）;

end

程序后

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

2.2?數據集維度不確定子空間聚類算法

針對數據集維度不確定的高維數據提出UDDClique聚類算法，利用維度之間的關聯性得到數據集的確定維度，并采用Clique算法對數據集聚類。

日常生活中經常會碰到記錄散亂的數據，數據中存在缺失值、臟數據等情況。這種情況大量出現在高維數據中的某一維度或多個維度中，數據集的維度確定性降低，聚類質量會受到影響。高維數據具有稀疏性，當數據集的維度不確定時，數據集的稀疏程度會受影響，聚類的難度增加。高維數據的維度之間具有相關性，相關的維度之間存在相應的關聯規則，如果某一個維度和多個維度具有強的關聯性，那么這個維度存在的可能性就比較高，對于數據集來講這個維度的信息比較重要，對聚類分析幫助比較大。根據這個特點對數據集維度不確定的數據聚類。

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

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

定義8?維度關聯度。存在高維數據集C，數據集C中擁有維度a與其他維度。維度a與其他維度的相關度的和，為維度a與數據集C的關聯度。公式為：

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

其中：a為第a個維度，k為數據集的維數。

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

在針對高維數據的子空間聚類算法中，維度密度是子空間生成的一個標準。在針對高維不確定數據時，維度密度無法體現維度存在的可能性。在維度密度的基礎上結合維度相關度，即可以保證數據量足夠多，足以保證維度的確定性。可選維度公式為：

chi=coi×di（7）

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

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

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

算法2步驟：首先生成數據矩陣，從矩陣中可以得到每個維度的維度密度，可以得到維度之間的相關度，并計算維度關聯度。通過計算維度關聯度與維度密度可以得到維度準確性，并依據維度確定性得到確定維度。用Clique算法對確定的數據集聚類。

算法2?UDDClique（）。

輸入?數據集C={d1，d2，…，dn};

輸出?聚類結果。

程序前

begin

1） 以維度作為豎軸，以數據作為橫軸生成數據矩陣;

2） 根據式（5），計算維度相關度;

3） 根據式（6），計算維度關聯度;

4） 根據式（7），計算維度確定性;

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

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

7） Clique（CE）;

end

程序后

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

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

2.1節、2.2節主要分析了高維不確定數據中的數據集維度不確定和部分數據維度不確定兩種情況。本章針對高維不確定數據中的數值模糊和數據值缺失問題，分別提出了相應的聚類算法。

3.1?數據值模糊聚類

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

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

圖中不確定數據沒有確定的位置，實線標識范圍是不確定數據可能出現的范圍，點代表確定數據。

根據Clique算法首先劃分子空間并對子空間作網格劃分處理。由于本節中不確定數據的維度是確定的，子空間劃分與網格劃分過程并不會受到不確定數據的影響。

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

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

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

通過計算不確定數據與K個最近鄰數據所屬網格的網格歸屬度得到不確定數據的網格歸屬度集合：

bel（i）=

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

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

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

算法3的具體步驟：按照Clique算法選取密集維度生成子空間并在子空間內劃分網格。采用KNN算法結合式（9）、（10）計算不確定數據的網格歸屬，利用網格的鄰近性，將不確定數據確定化。當數據集中不存在不確定數據時，采用Clique算法將數據集聚類。

算法3?UFVClique（）。

輸入?數據集C={d1，d2，…，dn};

輸出?聚類結果。

程序前

begin

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

2）將子空間內的數據分為確定數據集CE與不確定數據集UCE;

3）根據距離計算公式計算不確定數據的K個最近鄰數據;

4）根據式（9）、（10）計算不確定數據的網格歸屬度以及網格歸屬度集合;

5）根據網格歸屬度集合將不確定數據劃分到相應網格，并從UCE集合中刪除;

6）不斷循環3）～5），直到UCE集合為空;

7） Clique（CE）;

end

程序后

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

3.2?數據值模糊聚類

數據在錄入時會產生缺失值，導致數據的確定性下降。傳統處理數據缺失值的方法有4種：丟棄缺失值、填補缺失值、預測缺失值和直接分析。針對存在缺失值的高維數據集聚類算法，提出UMVClique算法，采用KNN的方式填補缺失值生成確定數據集，采用Clique算法對確定的數據集聚類。

定義9?數據維度缺失度。存在高維缺失值a，a在n個維度存在空值，那么n就是a的數據維度缺失度，簡稱缺失度。

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

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

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

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

其中：ui為不確定數據在第i維的值，ci為確定數據在第i維的值。

根據式（11）計算不確定數據在m-n維的K個最近鄰數據，并根據這K個數據填補第n維中缺失數據，計算公式為：

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

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

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

算法4的具體步驟：先將數據集中的缺失部分填補，再將數據集聚類。填補的過程為，先將數據集分為兩個部分，一部分為缺失值，另一部分為確定數據。將缺失值按缺失度從小到大的順序排列，并按順序將缺失值與確定數據集中的數據比較，將相似度最大的K個確定數據的均值填補到缺失值中，得到確定數據并放入確定數據集中，直到沒有缺失值存在時再對數據集聚類。

算法4?UMVClique（）。

輸入?數據集C={d1，d2，…，dn};

輸出?聚類結果。

程序前

begin

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

2） 計算UCE集合中所有數據的缺失度;

3） 按缺失度從小到大的順序對UCE集合中的數據排序;

4） 結合式（11），按順序找出不確定數據的K個最近鄰;

5） 結合式（12）計算K個最近鄰在缺失值所在維度的數據均值M。

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

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

8） Clique（CE）;

end

程序后

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

4?基于子空間的復雜高維不確定數據聚類算法

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

針對復雜的高維不確定數據提出UClique算法。算法可以對復雜的高維不確定數據聚類，結合算法1、2、3、4各自的特點對復雜的高維不確定數據聚類。

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

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

算法5?UClique（）。

輸入?數據集C={d1，d2，…，dn};

輸出?聚類結果。

程序前

begin

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

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

3） 判斷C中是否存在維度不確定數據，是則執行步驟4），否則執行步驟5）;

4） 采用UDPClique算法得到不確定數據的確定維度;

5） 判斷C中是否存在缺失數據，是則執行步驟6），否則執行步驟7）;

6） 采用UMVClique算法填補缺失值;

7） 判斷C中是否存在模糊數據，是則執行步驟8），否則執行步驟9）;

8） 采用UFVClique算法將不確定數據劃分到確定網格中;

9） Clique（C）;

end

程序后

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

5?實驗

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

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

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

圖3是最近鄰個數K的取值對UClique算法精度影響的實驗結果，可以看出：在K值取5～15時，精度單調遞增;在K取20時，精度下降。由此可以推斷出K的最佳取值范圍在10～15。

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

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

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

采用仿真數據集來進行接下來的實驗，仿真數據集的特點是用戶可以通過輸入參數來控制數據集的維度、結構、大小和在各個維度上的取值范圍等等。分別測試數據規模、噪聲、維數對算法精度的影響，實驗結果如圖5。

由圖5所示，在數據規模不斷增加的情況下，三種算法的聚類精度都在不斷下降，并逐漸收斂。UClique算法與ENCLUS算法采用子空間聚類的方法，對于大規模數據有一定的免疫能力，FDBSCANSMDM算法也對數據規模不敏感，所以在數據規模達到一定程度之后聚類精度會逐漸平穩， 可以得出UClique算法伸縮性良好。

在數據規模與維數不變的情況下，噪聲不斷增加，三種算法的精度按UClique、FDBSCANSMDM和ENCLUS從大到小的順序排列。在噪聲不斷增加的情況下，三種算法精度都有不同程度的下降但是整體下降幅度小，具有較好的穩定性。可以得出UClique算法對噪聲有一定的耐受性。

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

6?結語

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

參考文獻 （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，FU 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]? 范虹，侯存存，朱艷春，等.煙花算法優化的軟子空間MR圖像聚類算法[J].軟件學報，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]? 傅文進，吳小俊.基于l_2范數的加權低秩子空間聚類[J].軟件學報，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均值的空間不確定數據聚類[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]? 周曉云， 孫志揮， 張柏禮， 等. 高維數據流子空間聚類發現及維護算法[J]. 計算機研究與發展， 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.）