羅來源+孫國寶

摘要：近年來，在無線射頻識別、地球信息系統(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 文獻標識碼：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ā)了學術(shù)界和工業(yè)界對新型的不確定數(shù)據(jù)管理技術(shù)的興趣。不確定數(shù)據(jù)，即帶有不確定性（uncertainty）的數(shù)據(jù)。不確定性是針對確定性而言的，是對確定性的否定。在經(jīng)典科學的理解上，把確定性（certainty）理解為一個現(xiàn)象或事件結(jié)果的出現(xiàn)是唯一的、確定的。因此，不確定性則是對這種唯一性的否定，即當某一事件即使遵循某一規(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ù)挖掘得到可利用的知識是當前研究的熱點，聚類分析研究是不確定數(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為一張某研究所新生注冊中，新生孫山的入學信息調(diào)查表，由于該同學字跡潦草等原因致使學號一欄可能是756，也有可能是156，僅從圖2a無法得出真實的學號數(shù)據(jù)。在政治面貌一欄中由于污漬涂寫錯誤等原因致使政治面貌一欄結(jié)果也無法獲得。本次調(diào)查孫山的面貌數(shù)據(jù)和學號數(shù)據(jù)看作為不確定數(shù)據(jù)，并且這兩項不確定性被稱為屬性不確定。

圖2b所示，該研究所收到的另外一張學號為113的調(diào)查表，政治面貌缺失，姓名一欄為缺失，我們將無法確定學號為113的該名學生是沒有完成這個表格還是因為某種原因該生并沒有到校注冊，那么可以將學號為113的學生的調(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)督學習，在模式識別和機器學習等領(lǐng)域具有廣泛的應(yīng)用背景8[15]。聚類的目標是把有限的無標簽的對象集劃分為多個“相似的”簇（clustering）集，而“相似性”體現(xiàn)了數(shù)據(jù)本質(zhì)的類別屬性。在引文[12]中，作者引入了帶坐標移動散布點的例子，很好地引出了不確定數(shù)據(jù)聚類的概念。

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

通過數(shù)學表達式對不確定數(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)，當每個不確定數(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)實例到簇心的距離期望表示，而且其中誤差平方和準則函數(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ù)雜度過高嚴重影響算法的實用性。面對這個問題，當前所提出的解決方法主要是采用多種剪枝策略，壓縮不確定實例的規(guī)模從而降低算法的計算當量，但往往會失去一部分不確定實例，降低聚類質(zhì)量。

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

5總結(jié)

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

參考文獻：

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

[2] 李堅.不確定性問題初探[D]. 中國社會科學院研究生院， 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]. 西安電子科技大學， 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.