1、畢業設計（論文）外文資料翻譯系 部： 計算機科學與技術系 專 業： 計算機科學與技術 姓 名： 洪維坤 學 號： 0807012215 外 文 出 處： Proceeding of Workshop on the （用外文寫） of Artificial,Hualien,TaiWan,2005 指導老師評語：簽名：年 月 日不確定性數據挖掘：一種新的研究方向Michael Chau1, Reynold Cheng2, and Ben Kao31：商學院，香港大學，薄扶林，香港2：計算機系，香港理工大學九龍湖校區，香港3：計算機科學系，香港大學，薄扶林，香港摘要由于不精確測量、過時的來源或抽樣誤

2、差等原因，數據不確定性常常出現在真實世界應用中。目前，在數據庫數據不確定性處理領域中，很多研究結果已經被發表。我們認為，當不確定性數據被執行數據挖掘時，數據不確定性不得不被考慮在內，才能獲得高質量的數據挖掘結果。我們稱之為“不確定性數據挖掘”問題。在本文中，我們為這個領域可能的研究方向提出一個框架。同時，我們以UK-means聚類算法為例來闡明傳統K-means算法怎么被改進來處理數據挖掘中的數據不確定性。1.引言由于測量不精確、抽樣誤差、過時數據來源或其他等原因，數據往往帶有不確定性性質。特別在需要與物理環境交互的應用中，如：移動定位服務15和傳感器監測3。例如：在追蹤移動目標（如車輛或人）

3、的情境中，數據庫是不可能完全追蹤到所有目標在所有瞬間的準確位置。因此，每個目標的位置的變化過程是伴有不確定性的。為了提供準確地查詢和挖掘結果，這些導致數據不確定性的多方面來源不得不被考慮。在最近幾年里，已有在數據庫中不確定性數據管理方面的大量研究，如：數據庫中不確定性的表現和不確定性數據查詢。然而，很少有研究成果能夠解決不確定性數據挖掘的問題。我們注意到，不確定性使數據值不再具有原子性。對于使用傳統數據挖掘技術，不確定性數據不得不被歸納為原子性數值。再以追蹤移動目標應用為例，一個目標的位置可以通過它最后的記錄位置或通過一個預期位置（如果這個目標位置概率分布被考慮到）歸納得到。不幸地是，歸納得到

4、的記錄與真實記錄之間的誤差可能會嚴重也影響挖掘結果。圖1闡明了當一種聚類算法被應用追蹤帶有不確定性位置的移動目標時所發生的問題。圖1（a）表示一組目標的真實數據，而圖1（b）則表示記錄的已過時的這些目標的位置。如果這些實際位置是有效的話，那么它們與那些從過時數據值中得到的數據集群有明顯差異。如果我們僅僅依靠記錄的數據值，那么將會很多的目標可能被置于錯誤的數據集群中。更糟糕地是，一個群中的每一個成員都有可能改變群的質心，因此導致更多的錯誤。圖1 數據圖圖1.（a）表示真實數據劃分成的三個集群（a、b、c）。（b）表示的有些目標（隱藏的）的記錄位置與它們真實的數據不一樣，因此形成集群a、b、c和c

5、”。注意到a集群中比a集群少了一個目標，而b集群中比b集群多一個目標。同時，c也誤拆分會為c和c”。(c)表示方向不確定性被考慮來推測出集群a，b和c。這種聚類產生的結果比（b）結果更加接近（a）。我們建議將不確定性數據的概率密度函數等不確定性信息與現有的數據挖掘方法結合，這樣在實際數據可利用于數據挖掘的情況下會使得挖掘結果更接近從真實數據中獲得的結果。本文研究了不確定性怎么通過把數據聚類當成一種激勵范例使用使得不確定性因素與數據挖掘相結合。我們稱之為不確定性數據挖掘問題。在本文中，我們為這個領域可能的研究方向提出一個框架。文章接下來的結構如下。第二章是有關工作綜述。在第三章中，我們定義了不確

6、定性數據聚類問題和介紹我們提議的算法。第四章將呈現我們算法在移動目標數據庫的應用。詳細地的實習結果將在第五章解釋。最后在第六章總結論文并提出可能的研究方向。2.研究背景近年來，人們對數據不確定性管理有明顯的研究興趣。數據不確定性被為兩類，即已存在的不確定生和數值不確定性。在第一種類型中，不管目標或數據元組存在是否，數據本身就已經存在不確定性了。例如，關系數據庫中的元組可能與能表現它存在信任度的一個概率值相關聯1,2。在數據不確定性類型中，一個數據項作為一個封閉的區域,與其值的概率密度函數（PDF）限定了其可能的值3,4,12,15。這個模型可以被應用于量化在不斷變化的環境下的位置或傳感器數據的

7、不精密度。在這個領域里，大量的工作都致力于不精確查找。例如，在5中，解決不確定性數據范圍查詢的索引方案已經被提出。在4中，同一作者提出了解決鄰近等查詢的方案。注意到，所有工作已經把不確定性數據管理的研究結果應用于簡化數據庫查詢中，而不是應用于相對復雜的數據分析和挖掘問題中。在數據挖掘研究中，聚類問題已經被很好的研究。一個標準的聚類過程由5個主要步驟組成：模式表示，模式定義，模式相似度量的定義，聚類或分組，數據抽象和造工評核10。只有小部分關于數據挖掘或不確定性數據聚類的研究被發表。Hamdan與Govaert已經通過運用EM算法解決使混合密度適合不確定性數據聚類的問題 8。然而，這個模型不能任

8、意地應用于其他聚類算法因為它相當于為EM定制的。在數據區間的聚類也同樣被研究。像城區距離或明考斯基距離等不同距離測量也已經被用來衡量兩個區間的相似度。在這些測量的大多數中，區間的概率密度函數并沒有被考慮到。另外一個相關領域的研究就是模糊聚類。在模糊邏輯中的模糊聚類研究已經很久遠了13。在模糊聚類中,一個是數據簇由一組目標的模糊子集組成。每個目標與每個簇都有一個“歸屬關系度”。換言之，一個目標可以歸屬于多個簇，與每個簇均有一個度。模糊C均值聚類算法是一種最廣泛的使用模糊聚類方法2,7。不同的模糊聚類方法已被應用在一般數據或模糊數據中來產生的模糊數據簇。他們研究工作是基于一個模糊數據模型的，而我們

9、工作的開展則基于移動目標的不確定性模型。3.不確定數據的分類在圖2中，我們提出一種分類法來闡述數據挖掘方法怎么根據是否考慮數據不準確性來分類。有很多通用的數據挖掘技術，如: 關聯規則挖掘、數據分類、數據聚類。當然這些技術需要經過改進才能用于處理不確定性技術。此外，我們區分出數據聚類的兩種類型：硬聚類和模糊聚類。硬聚類旨在通過考慮預期的數據來提高聚類的準確性。另一方面，模糊聚類則表示聚類的結果為一個“模糊”表格。模糊聚類的一個例子是每個數據項被賦予一個被分配給數據簇的任意成員的概率。圖2. 不確定性數據挖掘的一種分類 例如，當不確定性被考慮時，會發生一個有意思的問題，即如何在數據集中表示每個元組

10、和關聯的不確定性。而且，由于支持和其他指標的概念需要重新定義，不得不考慮改進那些著名的關聯規則挖掘算法(如Apriori)。同樣地，在數據分類和數據聚集中，傳統算法由于未將數據不確定性考慮在內而導致不能起作用。不得不對聚類質心、兩個目標的距離、或目標與質心的距離等重要度量作重新定義和進行更深的研究。4不確定性數據聚類實例在這個章節中，我們將以不確定性數據挖掘的例子為大家介紹我們在不確定性數據聚類中的研究工作。這將闡明我們在改進傳統數據挖掘算法以適合不確定性數據問題上的想法。4.1 問題定義用S表示V維向量xi的集合，其中i=1到n，這些向量表示在聚類應用中被考慮的所有記錄的屬性值。每個記錄oi

11、與一個概率密度函數fi(x)相聯系，這個函數就是oi屬性值x在時間t時刻的概率密度函數。我們沒有干涉這個不確定性函數的實時變化，或記錄的概率密度函數是什么。平均密度函數就是一個概率密度函數的例子，它描述“大量不確定性”情景中是最糟的情況3。另一個常用的就是高斯分布函數，它能夠用于描述測量誤差12,15。聚類問題就是在數據集簇Cj（j從1到K）找到一個數據集C，其中Cj由基于相似性的平均值cj構成。不同的聚類算法對應不對的目標函數，但是大意都是最小化同一數據集目標間的距離和最大化不同數據集目標間的距離。數據集內部距離最小化也被視為每個數據點之間距離xi以及xi與對應的Cj中平均值cj距離的最小化

12、。在論文中，我們只考慮硬聚類，即，每個目標只分配給一個一個集群的一個元素。4.2 均值聚類在精確數據中的應用這個傳統的均值聚類算法目的在于找到K(也就是由平均值cj構成數據集簇Cj)中找到一個數據集C來最小化平方誤差總和（SSE）。平方誤差總和通常計算如下： (1)| . |表示一個數據點xi與數據集平均值cj的距離試題。例如，歐氏距離定義為： (2)一個數據集Ci的平均值（質心）由下面的向量公式來定義： (3)均值聚類算法如下：1. Assign initial values for cluster means c1 to cK2. repeat3. for i = 1 to n do4.

13、Assign each data point xi to cluster Cj where | cj - xi | is the minimum.5. end for6. for j = 1 to K do7. Recalculate cluster mean cj of cluster Cj8. end for9. until convergence10. return C 收斂可能基于不同的質心來確定。一些收斂性判別規則例子包括：（1）當平方誤差總和小于某一用戶專用臨界值，（2）當在一次迭代中沒有一個目標再分配給不同的數據集和（3）當迭代次數還達到預期的定義的最大值。4.3 K-means

14、聚類在不確定性數據中的應用為了在聚類過程中考慮數據不確定性，我們提出一種算法來實現最小化期望平方誤差總和E(SSE)的目標。注意到一個數據對象xi由一個帶有不確定性概率密度f(xi)的不確定性區域決定。給定一組數據群集，期望平方誤差總和可以計算如下： (4)數據集平均值可以如下給出: (5)我們到此將提出一種新K-means算法，即UK-means，來實現不確定性數據聚類。1. Assign initial values for cluster means c1 to cK2. repeat3. for i = 1 to n do4. Assign each data point xi to

15、cluster Cj where E(| cj - xi |) is the minimum.5. end for6. for j = 1 to K do7. Recalculate cluster mean cj of cluster Cj8. end for9. until convergence10. return CUK-mean聚類算法與K-means聚類算法的最大不同點在于距離和群集的計算。特別地，UK-means基于數據不確定性模型來計算預期的距離和數據集質心。同時，收斂可按照不同的標準來定義。注意到如果收斂依賴于下平方誤差，那么在方程式（4）中E(SSE)應該替代SSE使用。在

16、第4步中，常常很困難用代數方法來確定E(| cj - xi |)，特別地，各種各樣的幾何圖形不確定性區域（如，線，圓）和不同的不確定性概率密度函數意味著需要使用數值積分法。鑒于此，比較容易獲得的E(| cj - xi |2)用來替代E(| cj - xi |)。這使我們能夠確定在聚類任務（即步驟4）中使用簡單的代數表達式。5一個案例研究和評估5.1線性移動不確定性數據聚類在最后一章提出的UK-means算法可適用于任意一個不確定性區域和概率密度函數。為了證明方法的可行性，我們將描述所推薦的算法是如何運用于特定于在平面空間中移動的目標的不確定性模型。我們也會介紹算法的評估結果。這個算法已被應用于

17、一個含有單向線性移動不確定性的模型中。在這個模型里，我們需要讓每一目標在某一方向移動的位置均勻地分布在一段直線上。假設我們在一個質心c=(p,q)和一個數據對象x被指定在一個線性不確定的均勻分布的區域中。讓線性不確定性線段的終結點為（a,b）和（c,d）。這樣這個線性方程式可用參數表示為（a+t(c-a),b+t(d-b)），其中t屬于0,1。使用f(t)表示不確定性概率密度函數。同時，不確定性線段的距離表示為。 我們可以得到： (6)其中B = 2(c - a) (a - p) + (d - b) (b - q)C = (p - a) 2 + (q - b) 2如果函數f(t)是均勻分布的，

18、那么當f(t)=1時，上面的公式就變成： (7)從而我們就能很容易為均勻分布的線性移動不確定性計算出期望平方距離。這些公式很容易被UK-means算法用于決定群集分配。但是，均勻分布的應用在這里僅僅是一個特定的例子。當概率密度函數不是均勻分布時（如，高斯分布），采樣技術可能被用來估計E(| cj -xi |)。5.2實驗實驗的開展是為了評估UK-means算法的可行性。我們目標是研究考慮數據不確定性是否會提高聚類質量。我們模擬以下情景：一個可以追蹤一組移動目標位置的系統已經拍了一組反應這些目標位置的快照。這個位置數據存在記錄集中。其中的每個對象都有著一定的不確定性。我們使用這些不確定性因素來捕

19、捉不確定性信息。接下來我們來比較兩種聚類方法的不同之外：（1）把K-means方法應用于記錄中和把UK-means方法應用于記錄中+不確定性。更具體地說，我們首先一個100100的二維空間產生一組隨機數據點作為記錄。對于每個數據點，我們根據單向線性不確定性模型為其隨機產生不確定性。一個目標的不確定性規格包括不確定性的類型（雙向線性）、目標能夠移動的最小距離d以及目標能夠移動的方向。接下來，這些目標的真實位置就根據記錄和不確定性來模擬目標已經從累存記錄中的原始位置偏移來產生。特別地，對于每個數據點，我們把它的位置記錄在案，然后隨機產生一個數據決定目標可能的移動距離。如果它屬于自由移動（多向）或雙

20、向不確定性，那么我們將產生另外一個數據來決定目標可能的移動方向。我們使用實際值來表示這些目標的位置。理論上，一個系統需要知道實際情況且把K-means方法應用于實際位置中。盡量不是實際的，但是這個聚類結果卻可視為聚類結果質量的一個很好的參照。因此，我們計算和比較以下數據集的聚類輸出結果：(1)記錄（使用傳統K-means）(2)記錄+不確定性（使用UK-means）(3)真實值（使用傳統K-means）為了核實UK-means算法在產生的數據群集接近從真實數據中產生的數據集群中的作用，我們采用廣泛使用的用來計算聚類結果間相似度的調整蘭德指數（ARI）16。ARI值越高，則兩個聚類結果相似度越高

21、。我們將對由（2）與（3）產生的數據群集間的ARI指數和（1）與（3）產生的數據群集間的ARI指數進行比較。目標的個數(n)、群集的個數（K）以及目標可能移動的最小距離（d）這三個參數的值在實驗中將改變。表1呈現是當保持n=1000和K=20時改變d的值所得到的不同實驗結果。在不同的參數組合情況下，我們做了500次的實驗。每一次實驗，我們事先生成記錄、不確定性度、實際值的組合。這些數據組合是同時在三種聚類過程中被使用。相同的質心集合也被同時使用到三種聚類過程中，這樣可以避免由K-means方法和UK-means方法初始條件引起的偏差。每一次實驗，我們允許K-means方法（1）中和（3）中）和

22、UK-means方法（2）中）在一直運行到當在群集中的所有目標在兩次連續迭代中沒有變化時或迭代次數達到10000次時才結束。調整蘭德指數和時間間隔由分別的UK-means方法和K-means方法500次實驗取平均值得到。從表1可以看到，在應用于記錄數據中，UK-means算法的調整蘭德指數始終比傳統K-means算法高。成對測試結果表明，在所有的設置條件下（每一個用例中p 0.000001）兩種方法的調整蘭德指數值不同之處是明顯的。這個結果表明，由UK-means算法得到的數據群集更接近于從真實世界獲得的數據群集。換言 ，UK-means算法能獲得一個數據群集，而這個數據群集是從真實世界可利用

23、數據中得到數據群集的一個較好的預測。表1. 實驗結果D2.557.5102050ARI(UK-means)0.7330.6890.6520.6320.5060.311ARI(K-means)0.7000.6260.5730.5230.3510.121改進0.0330.0630.0790.1090.1550.189改進百分比4.77%10.03%13.84%20.82%44.34%155.75%在效率方面，我們發現UK-means方法比K-means方法需要更多的計算時間，但是它常常只需要合理數量的額外時間。這是合乎情理的，因為它考慮了不確定性使得聚類質量更好。我們通過給n、K及d賦予不同的值且

24、保持其他變量恒定來進行深入地實驗。在所有情況下，我們發現UK-means方法比傳統的K-means方法改進了，而且兩者的差異有統計學意義（如圖所示每一種情況試驗結果）。我們的初步研究表明當不確定性程度增加時，UK-means算法的改進度也就越高。另一方面，除了當群集的個數非常小的時候，目標的個數和群集的個數對UK-means算法的作用是不會有大的影響。6. 總結與展望傳統的數據挖掘算法沒有考慮數據項中固有的不確定性而且產生的挖掘結果與真實世界的數據不相符。在本論文中，我們提出了在不確定性數據挖掘領域研究的一個分類方法。同時我們以UK-means算法作為案例研究和闡明該算法是如何被應用的。隨著由

25、先進傳感器設備帶來的現實數據日益復雜，我們相信不確定性數據挖掘是一個重要和有意義的研究領域。感謝我們要感謝Jackey Ng（香港大學），David Cheung（香港大學），Edward Hung（香港理工大學），和Kevin Yip（耶魯大學）的寶貴建議。參考文獻1. Barbara, D., Garcia-Molina, H. and Porter, D. “The Management of Probabilistic Data,” IEEE Transactions on Knowledge and Data Engineering, 4(5), 1992.2. Bezdek, J.

26、 C. Pattern Recognition with Fuzzy Objective Function Algorithms. Plenum Press, New York(1981).3. Cheng, R., Kalashnikov, D., and Prabhakar, S. “Evaluating Probabilistic Queries over Imprecise Data,”Proceedings of the ACM SIGMOD International Conference on Management of Data, June 2003.4. Cheng, R.,

27、 Kalashnikov, D., and Prabhakar, S. “Querying Imprecise Data in Moving Object Environments,”IEEE Transactions on Knowledge and Data Engineering, 16(9) (2004) 1112-1127.5. Cheng, R., Xia, X., Prabhakar, S., Shah, R. and Vitter, J. “Efficient Indexing Methods for Probabilistic Threshold Queries over U

28、ncertain Data,” Proceedings of VLDB, 2004.6. de Souza, R. M. C. R. and de Carvalho, F. de A. T. “Clustering of Interval Data Based on CityBlock Distances,” Pattern Recognition Letters, 25 (2004) 353365.7. Dunn, J. C. “A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Sepa

29、rated Clusters,” Journal of Cybernetics, 3 (1973) 32-57.8. Hamdan, H. and Govaert, G. “Mixture Model Clustering of Uncertain Data,” IEEE International Conference on Fuzzy Systems (2005) 879-884.9. Ichino, M., Yaguchi, H. “Generalized Minkowski Metrics for Mixed Feature Type Data Analysis,” IEEE Tran

30、sactions on Systems, Man and Cybernetics, 24(4) (1994) 698708.10. Jain, A. and Dubes, R. Algorithms for Clustering Data. Prentice Hall, New Jersey (1988).11. Nilesh N. D. and Suciu, D. “Efficient Query Evaluation on Probabilistic Databases,” VLDB (2004) 864-875.12. Pfoser D. and Jensen, C. “Capturin

31、g the Uncertainty of Moving-objects Representations,” Proceedings of the SSDBM Conference, 123132, 1999.13. Ruspini, E. H. “A New Approach to Clustering,” Information Control, 15(1) (1969) 22-32.14. Sato, M., Sato, Y., and Jain, L. Fuzzy Clustering Models and Applications. Physica-Verlag, Heidelberg

32、(1997).15. Wolfson, O., Sistla, P., Chamberlain, S. and Yesha, Y. “Updating and Querying Databases that Track Mobile Units,” Distributed and Parallel Databases, 7(3), 1999.16. Yeung, K. and Ruzzo, W. “An Empirical Study on Principal Component Analysis for Clustering Gene Expression Data,” Bioinforma

33、tics, 17(9) (2001) 763-774.Uncertain Data Mining: A New Research DirectionMichael Chau1, Reynold Cheng2, and Ben Kao31: School of Business, The University of Hong Kong, Pokfulam, Hong Kong2: Department of Computing, Hong Kong Polytechnic University Kowloon, Hong Kong3: Department of Computer Science

34、, The University of Hong Kong, Pokfulam, Hong KongEmails: mchaubusiness.hku.hk, .hk, kaocs.hku.hkAbstractData uncertainty is often found in real-world applications due to reasons such as imprecise measurement, outdated sources, or sampling errors. Recently, much research has b

35、een published in the area of managing data uncertainty in databases. We propose that when data mining is performed on uncertain data, data uncertainty has to be considered in order to obtain high quality data mining results. We call this the Uncertain Data Mining problem. In this paper, we present a

36、 framework for possible research directions in this area. We also present the UK-means clustering algorithm as an example to illustrate how the traditional K-means algorithm can be modified to handle data uncertainty in data mining.1. IntroductionData is often associated with uncertainty because of

37、measurement inaccuracy, sampling discrepancy,outdated data sources, or other errors. This is especially true for applications that require interaction with the physical world, such as location-based services 15 and sensor monitoring 3. For example,in the scenario of moving objects (such as vehicles

38、or people), it is impossible for the database to track the exact locations of all objects at all time instants. Therefore, the location of each object is associated with uncertainty between updates 4. These various sources of uncertainty have to be considered in order to produce accurate query and m

39、ining results.In recent years, there has been much research on the management of uncertain data in databases, such as the representation of uncertainty in databases and querying data with uncertainty. However, little research work has addressed the issue of mining uncertain data. We note that with u

40、ncertainty, data values are no longer atomic. To apply traditional data mining techniques, uncertain data has to be summarized into atomic values. Taking moving-object applications as an example again, the location of an object can be summarized either by its last recorded location, or by an expecte

41、d location (if the probability distribution of an objects location is taken into account). Unfortunately, discrepancy in the summarized recorded values and the actual values could seriously affect the quality of the mining results. Figure 1 illustrates this problem when a clustering algorithm is app

42、lied to moving objects with location uncertainty. Figure 1(a) shows the actual locations of a set of objects, and Figure 1(b) shows the recorded location of these objects, which are already outdated. The clusters obtained from these outdated values could be significantly different from those obtaine

43、d as if the actual locations were available (Figure 1(b). If we solely rely on the recorded values, many objects could possibly be put into wrong clusters. Even worse, each member of a cluster would change the cluster centroids, thus resulting in more errors.Figure 1Figure 1. (a) The real-world data

44、 are partitioned into three clusters (a, b, c). (b) The recorded locations of some objects (shaded) are not the same as their true location, thus creating clusters a, b, c and c. Note that a has one fewer object than a, and b has one more object than b. Also, c is mistakenly split into c and c. (c)

45、Line uncertainty is considered to produce clusters a, b and c. The clustering result is closer to that of (a) than (b).We suggest incorporating uncertainty information, such as the probability density functions (pdf) of uncertain data, into existing data mining methods so that the mining results cou

46、ld resemble closer to the results obtained as if actual data were available and used in the mining process (Figure 2(c).In this paper we study how uncertainty can be incorporated in data mining by using data clustering as a motivating example. We call this the Uncertain Data Mining problem. In this

47、paper, we present a framework for possible research directions in this area.The rest of the paper is structured as follows. Related work is reviewed in Section 2. In Section 3 we define the problem of clustering on data with uncertainty and present our proposed algorithm. Section 4 presents the appl

48、ication of our algorithm to a moving-object database. Detailed experiment results are shown in Section 5. We conclude our paper and suggest possible research directions in Section 6.2. Research BackgroundIn recent years, there is significant research interest in data uncertainty management. Data unc

49、ertainty can be categorized into two types, namely existential uncertainty and value uncertainty. In the first type it is uncertain whether the object or data tuple exists or not. For example, a tuple in a relational database could be associated with a probability value that indicates the confidence

50、 of its presence1,11. In value uncertainty, a data item is modelled as a closed region which bounds its possible values, together with a probability density function (pdf) of its value 3,4,12,15. This model can be used to quantify the imprecision of location and sensor data in a constantly-evolving

51、environment.Most works in this area have been devoted to “imprecise queries”, which provide probabilistic guarantees over correctness of answers. For example, in 5, indexing solutions for range queries over uncertain data have been proposed. The same authors also proposed solutions for aggregate que

52、ries such as nearest-neighbor queries in 4. Notice that all these works have applied the study of uncertain data management to simple database queries, instead of to the relatively more complicated data analysis and mining problems.The clustering problem has been well studied in data mining research

53、. A standard clustering process consists of five major steps: pattern representation, definition of a pattern similarity metric, clustering or grouping, data abstraction, and output assessment 10. Only a few studies on data mining or data clustering for uncertain data have been reported. Hamdan and

54、Govaert have addressed the problem of fitting mixture densities to uncertain data for clustering using the EM algorithm 8. However, the model cannot be readily applied to other clustering algorithms and is rather customized for EM.Clustering on interval data also has been studied. Different distance

55、 measures, like city-block distance or Minkowski distance, have been used in measuring the similarity between two intervals 6,9. The pdf of the interval is not taken into account in most of these metrics. Another related area of research is fuzzy clustering. Fuzzy clustering has been long studied in

56、 fuzzy logic 13. In fuzzy clustering, a cluster is represented by a fuzzy subset of a set of objects. Each object has a “degree of belongingness” for each cluster. In other words, an object can belong to more than one cluster, each with a different degree. The fuzzy c-means algorithm was one of the

57、most widely used fuzzy clustering method 2,7. Different fuzzy clustering methods have been applied on normal data or fuzzy data to produce fuzzy clusters 14. While their work is based on a fuzzy data model, our work is developed based on the uncertainty model of moving objects.3. Taxonomy of Uncertain Data MiningIn Figure 2, we propose a taxonomy to illustrate how data mining methods can be classified bas