羅來源+孫國寶

摘要：近年來，在無線射頻識別、地球信息系統(tǒng)等領(lǐng)域中大量出現(xiàn)了不確定數(shù)據(jù)。不確定數(shù)據(jù)的研究早在上世紀八十年代就已經(jīng)開始，但早期的不確定數(shù)據(jù)的研究方向主要集中在不確定數(shù)據(jù)管理、不確定數(shù)據(jù)查詢等。不確定數(shù)據(jù)的聚類分析，正成為研究熱點。目前，不確定數(shù)據(jù)聚類研究主要通過對經(jīng)典聚類算法進行擴展。該文首先對不確定數(shù)據(jù)進行了概述，以及對基于劃分的不確定聚類算法進行了介紹，最后對未來發(fā)展趨勢進行了探討以及總結(jié)。

關(guān)鍵詞：不確定數(shù)據(jù)；聚類；擴展；概述；基于劃分

中圖分類號：TP393 文獻標(biāo)識碼：A 文章編號：1009-3044（2017）01-0215-03

1 引言

近年來，隨著技術(shù)的進步和人們對數(shù)據(jù)采集和處理技術(shù)深入地研究，不確定數(shù)據(jù)（uncertain data）得到廣泛的重視。在許多現(xiàn)實的應(yīng)用中，例如：經(jīng)濟、軍事、物流、金融、電信等領(lǐng)域，數(shù)據(jù)的不確定性普遍存在，不確定數(shù)據(jù)扮演關(guān)鍵角色1[1]。傳統(tǒng)的數(shù)據(jù)管理技術(shù)卻無法有效管理不確定數(shù)據(jù)，這就引發(fā)了學(xué)術(shù)界和工業(yè)界對新型的不確定數(shù)據(jù)管理技術(shù)的興趣。不確定數(shù)據(jù)，即帶有不確定性（uncertainty）的數(shù)據(jù)。不確定性是針對確定性而言的，是對確定性的否定。在經(jīng)典科學(xué)的理解上，把確定性（certainty）理解為一個現(xiàn)象或事件結(jié)果的出現(xiàn)是唯一的、確定的。因此，不確定性則是對這種唯一性的否定，即當(dāng)某一事件即使遵循某一規(guī)律運動也不能最終出現(xiàn)唯一的結(jié)果2[2]。例如，多次投擲一枚骰子，骰子有六面分別有六個不同的點數(shù)，每一次投擲的結(jié)果都是六個點數(shù)其中的一個，但具體是哪一個點數(shù)無法確定，那么就可以稱每一次投擲的結(jié)果就是不確定的。

不確定數(shù)據(jù)的研究從上世紀八十年代末就已經(jīng)開始了，其中主要的研究方向包括：不確定數(shù)據(jù)的表示與模型3[3-6]、不確定數(shù)據(jù)查詢4[7-10]等。目前，不確定數(shù)據(jù)正呈爆炸式增長，如圖1所示描述了隨著數(shù)據(jù)規(guī)模的增加，不確定數(shù)據(jù)所占的比例也相應(yīng)地增加，其中紅線表示在數(shù)據(jù)中不確定數(shù)據(jù)所占的比例。截止到2015年，世界上80%的數(shù)據(jù)是不確定的[11]。對于大量不確定數(shù)據(jù)進行數(shù)據(jù)挖掘得到可利用的知識是當(dāng)前研究的熱點，聚類分析研究是不確定數(shù)據(jù)挖掘的重要組成部分。聚類就是將多個數(shù)據(jù)對象構(gòu)成的集合分成若干相似對象的子集合的過程。不確定數(shù)據(jù)聚類算法的研究最早在2005年被提出，由M.Chau和鄭振剛等人5[12]提出并對不確定數(shù)據(jù)挖掘進行了定義。

2 不確定數(shù)據(jù)聚類

2.1 不確定數(shù)據(jù)概述

數(shù)據(jù)不確定性產(chǎn)生的原因復(fù)雜，李雪等人6[13]將不確定數(shù)據(jù)產(chǎn)生的原因分為兩類，一類是被動的不確定性，另一類是主動的不確定性。被動不確定性主要由原始數(shù)據(jù)因為自身缺失、不精確等；主動不確定性數(shù)據(jù)產(chǎn)生的原因則是人為對原始數(shù)據(jù)進行處理，例如對數(shù)據(jù)進行擾動以達到數(shù)據(jù)隱私保護的目的而形成的數(shù)據(jù)。

如圖2a為一張某研究所新生注冊中，新生孫山的入學(xué)信息調(diào)查表，由于該同學(xué)字跡潦草等原因致使學(xué)號一欄可能是756，也有可能是156，僅從圖2a無法得出真實的學(xué)號數(shù)據(jù)。在政治面貌一欄中由于污漬涂寫錯誤等原因致使政治面貌一欄結(jié)果也無法獲得。本次調(diào)查孫山的面貌數(shù)據(jù)和學(xué)號數(shù)據(jù)看作為不確定數(shù)據(jù)，并且這兩項不確定性被稱為屬性不確定。

圖2b所示，該研究所收到的另外一張學(xué)號為113的調(diào)查表，政治面貌缺失，姓名一欄為缺失，我們將無法確定學(xué)號為113的該名學(xué)生是沒有完成這個表格還是因為某種原因該生并沒有到校注冊，那么可以將學(xué)號為113的學(xué)生的調(diào)查數(shù)據(jù)稱為不確定數(shù)據(jù)，而且為存在級不確定。即按表現(xiàn)形式數(shù)據(jù)不確定性可以分為存在級不確定性和屬性級不確定性。存在級不確定性指某實例是否存在是不確定的，屬性級不確定性指實例屬性值是不確定的7[14]。

不確定數(shù)據(jù)聚類的研究是繼不確定數(shù)據(jù)模型與表示、不確定數(shù)據(jù)管理和不確定數(shù)據(jù)查詢后又一個不確定數(shù)據(jù)研究領(lǐng)域的熱點。

2.2 不確定數(shù)據(jù)聚類

聚類（cluster）被視作為無監(jiān)督學(xué)習(xí)，在模式識別和機器學(xué)習(xí)等領(lǐng)域具有廣泛的應(yīng)用背景8[15]。聚類的目標(biāo)是把有限的無標(biāo)簽的對象集劃分為多個“相似的”簇（clustering）集，而“相似性”體現(xiàn)了數(shù)據(jù)本質(zhì)的類別屬性。在引文[12]中，作者引入了帶坐標(biāo)移動散布點的例子，很好地引出了不確定數(shù)據(jù)聚類的概念。

如圖3所示，圖中散布點表示的移動對象，散布點的坐標(biāo)表示對象當(dāng)前的坐標(biāo)。圖3a為根據(jù)真實坐標(biāo)聚類成3個簇 。圖3b為在時間間隔之前的記錄坐標(biāo)，同樣根據(jù)對象坐標(biāo)進行聚類對當(dāng)前坐標(biāo)進行預(yù)測，然而得到的結(jié)果是四個簇，與圖3a真實坐標(biāo)聚類明顯不同。其原因在于，聚類過程中，并未將對象坐標(biāo)的改變考慮其中。假設(shè)在對圖3b記錄坐標(biāo)數(shù)據(jù)進行聚類時，將每個對象移動的趨勢考慮進去，用概率密度函數(shù)pdf （probability density function）表示每個對象的坐標(biāo)，再進行聚類得到的結(jié)果如圖3c所示，和圖3a真實的聚類結(jié)果非常接近。

通過數(shù)學(xué)表達式對不確定數(shù)據(jù)對象及聚類進行定義如下：

定義1：給定n維向量空間：

（1） 點以概率出現(xiàn)在事件中，則稱為維空間一個不確定點或不確定實例。稱 為不確定實例二元組。

（2） 對于不確定二元組和，則稱和為同點二元組，記為；反之則稱和為異點二元組，記為。

定義2：對n維向量空間中，任意不確定實例的集合滿足，不確定實例出現(xiàn)概率之和為1，即：

則可稱集合為n維向量空間中的不確定對象。

如圖4所示，在某2維向量空間中， 表示的是一組由6個不確定實例組成不確定實例二元組的集合，且 。集合，即可稱為2維空間的一個不確定對象。

與確定數(shù)據(jù)相似，不確定數(shù)據(jù)對象的聚類過程也是將相似的對象劃分到對應(yīng)簇中，把相異的對象劃到不同簇內(nèi)，表1給出了不確定數(shù)據(jù)對象聚類的形式化描述：

同樣，我們也可以用散布圖對不確定數(shù)據(jù)聚類進行描述如圖5所示，散布點表示不確定對象所對應(yīng)的不確定實例，實線表示的為不確定對象，圖5中共有5個數(shù)據(jù)對象，對這5個數(shù)據(jù)對象進行聚類分析，得到2個簇和，和為對應(yīng)簇心，如圖虛線所示。

不難發(fā)現(xiàn)，當(dāng)每個不確定數(shù)據(jù)對象都只有一個實例的情況下，不確定數(shù)據(jù)聚類就退化成為傳統(tǒng)確定數(shù)據(jù)的聚類。不確定數(shù)據(jù)聚類相較傳統(tǒng)確定數(shù)據(jù)聚類的不同在于對聚類對象新增了不確定因素，而不確定因素正是由不確定對象的多個實例造成的。目前不確定數(shù)據(jù)聚類研究的成果主要為基于劃分的不確定數(shù)據(jù)聚類以及改進算法。

3基于劃分的不確定聚類算法

不確定數(shù)據(jù)聚類研究的主要路線，是對傳統(tǒng)聚類算法針對不確定數(shù)據(jù)的擴展，其中基于劃分的不確定拒類是重要研究成果?；趧澐值牟淮_定聚類算法包括Chau等人提出的UK-means算法和Gullo等人9[16]提出的UK-medoids算法。

3.1 UK-means算法

UK-means 算法與K-means 算法的過程大致相同，算法假定不確定對象，相應(yīng)不確定實例區(qū)域由概率密度函數(shù) 表示。不確定對象到簇心的距離，由對象所對應(yīng)不確定實例到簇心的距離的期望表示。將各個數(shù)據(jù)對象劃分到離它最近的簇，然后重新計算簇心，進行迭代直至算法收斂。UK-means 算法步驟如表2所示：

UK-means算法與K-means算法的不同在于：不確定數(shù)據(jù)對象與簇心的距離是由對象所對應(yīng)實例到簇心的距離期望表示，而且其中誤差平方和準(zhǔn)則函數(shù)為：

表示的是實例到簇心的歐氏距離。

算法每次迭代，不確定對象與簇心的期望距離都要被計算一次，對于個不確定數(shù)據(jù)對象聚類成k個簇，UK-means算法要在每次迭代中需要計算次距離期望，正是由距離期望的計算導(dǎo)致UK-means算法效率很低。算法的使用場景也受到限制，例如，算法使用確定的單個數(shù)據(jù)點作為簇中心，這在不確定數(shù)據(jù)中聚類中容易丟失數(shù)據(jù)的不確定信息，從而影響了聚類質(zhì)量。針對這個問題，Gullo等人提出了UK-medoids算法。

3. 2 UK-medoids算法

基于K-medoids算法擴展的另一個基于劃分的不確定聚類算法UK-medoids，選擇真實的不確定對象做為簇中心進行聚類。由于簇中心是在實際輸入的數(shù)據(jù)對象之中選擇，只需對各個數(shù)據(jù)對象之間的距離做一次計算。UK-medoids算法步驟如表3所示。

UK-medoids算法優(yōu)點在于，減少了距離期望的計算次數(shù)。引文[13]實驗證明，對于同一數(shù)據(jù)集，UK-medoids算法的聚類精度和效率要比UK-means算法高。

4 不確定聚類所面臨的挑戰(zhàn)

與傳統(tǒng)的面向確定性數(shù)據(jù)的聚類分析相比，不確定性數(shù)據(jù)聚類主要在以下兩個方面面臨著挑戰(zhàn)。首先面臨著聚類算法的時間復(fù)雜度過高的挑戰(zhàn)，也是目前不確定數(shù)據(jù)聚類實際應(yīng)用時，所面臨的最直接的挑戰(zhàn)，對象數(shù)量的增加導(dǎo)致不確定實例數(shù)量呈指數(shù)倍的增加。算法的時間復(fù)雜度過高嚴重影響算法的實用性。面對這個問題，當(dāng)前所提出的解決方法主要是采用多種剪枝策略，壓縮不確定實例的規(guī)模從而降低算法的計算當(dāng)量，但往往會失去一部分不確定實例，降低聚類質(zhì)量。

不確定數(shù)據(jù)對象維度的增加，同樣是不確定聚類所面臨的巨大挑戰(zhàn)。高維不確定聚類需要解決的不僅在于算法復(fù)雜度方面的增加，更在于建立數(shù)據(jù)模型來表示不確定對象、相似性度量函數(shù)以及有效的降維，維度之咒不僅是聚類所面臨的挑戰(zhàn)同樣也是其他計算機學(xué)科所面臨的挑戰(zhàn)。

5總結(jié)

本文首先對不確定數(shù)據(jù)進行了概述，形式化描述了不確定數(shù)據(jù)對象、不確定聚類。并詳細地介紹了基于劃分的不確定數(shù)據(jù)聚類算法。文末對不確定聚類所面臨的挑戰(zhàn)進行了闡述。

參考文獻：

[1] 周傲英.不確定性數(shù)據(jù)管理技術(shù)研究綜述[J]. 計算機學(xué)報， 2009， 01：1-16.

[2] 李堅.不確定性問題初探[D]. 中國社會科學(xué)院研究生院， 2006.

[3] Aggarwal C C. Managing and Mining Uncertain Data[M]. Springer Publishing Company， Incorporated， 2009.

[4] Sarma A D. Working Models for Uncertain Data. [C]. ICDE. IEEE Computer Society， 2010：7-7.

[5] Aggarwal C C. Models for Incomplete and Probabilistic Information[M]. Current Trends in Database Technology – EDBT 2006. Springer Berlin Heidelberg， 2010：278-296.

[6] Sadri F. Modeling uncertainty in databases[C]. International Conference on Data Engineering， 1991. Proceedings. 1991：122-131.

[7] Sen P. Representing and Querying Correlated Tuples in Probabilistic Databases[C]. IEEE International Conference on Data

Engineering. 2007：596-605.

[8] Dalvi N. Efficient Query evaluation on Probabilistic Databases[C]. Thirtieth International Conference on Very Large Data Bases. 2004：864-875.

[9] Dalvi N. Answering Queries from Statistics and Probabilistic Views. [C]. International Conference on Very Large Data Bases， Trondheim， Norway， August 30 - September. 2005：805-816.

[10] Burdick D. OLAP over uncertain and imprecise data[J]. Vldb Journal International Journal on Very Large Data Bases， 2007，16（1）：123-144.

[11] 陳靜玉. 面向不確定數(shù)據(jù)流的聚類和模式挖掘技術(shù)研究[D]. 西安電子科技大學(xué)， 2014.

[12] Michael Chau. Uncertain Data Mining： An Example in Clustering Location Data[C]. Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. Springer-Verlag， 2006：199-204.

[13] 李雪， 不確定數(shù)據(jù)挖掘技術(shù)研究進展[J]， 2009.

[14] Aggarwal C C. A Survey of Uncertain Data Algorithms and Applications[J]. IEEE Transactions on Knowledge & Data Engineering， 2009， 21（5）：609-623.

[15] 數(shù)據(jù)挖掘：概念與技術(shù)[M]， 機械工業(yè)出版社， 2007.

[16] F. Gullo， G. Ponti， and A. Tagarelli. Clustering uncertain data via K-medoids[C]. In Proc. SUM Conf.， pages 229–242， 2008.