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

羅來源+孫國(guó)寶

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

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

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

1 引言

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

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

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

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

數(shù)據(jù)不確定性產(chǎn)生的原因復(fù)雜，李雪等人6[13]將不確定數(shù)據(jù)產(chǎn)生的原因分為兩類，一類是被動(dòng)的不確定性，另一類是主動(dòng)的不確定性。被動(dòng)不確定性主要由原始數(shù)據(jù)因?yàn)樽陨砣笔А⒉痪_等；主動(dòng)不確定性數(shù)據(jù)產(chǎn)生的原因則是人為對(duì)原始數(shù)據(jù)進(jìn)行處理，例如對(duì)數(shù)據(jù)進(jìn)行擾動(dòng)以達(dá)到數(shù)據(jù)隱私保護(hù)的目的而形成的數(shù)據(jù)。

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

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

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

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

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

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

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

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

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

（2） 對(duì)于不確定二元組和，則稱和為同點(diǎn)二元組，記為；反之則稱和為異點(diǎn)二元組，記為。

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

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

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

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

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

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

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

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

3.1 UK-means算法

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

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

表示的是實(shí)例到簇心的歐氏距離。

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

3. 2 UK-medoids算法

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

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

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

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

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

5總結(jié)

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

參考文獻(xiàn)：

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

[2] 李堅(jiān).不確定性問題初探[D]. 中國(guó)社會(huì)科學(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ìn)展[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]， 機(jī)械工業(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.