外文翻譯不確定性數(shù)據(jù)挖掘：一種新的研究方向

1、畢業(yè)設計（論文）外文資料翻譯系 部： 計算機科學與技術系 專 業(yè)： 計算機科學與技術 姓 名： 洪維坤 學 號： 0807012215 外 文 出 處： proceeding of workshop on the （用外文寫） of artificial,hualien,taiwan,2005 指導老師評語：簽名：年 月 日 11 不確定性數(shù)據(jù)挖掘：一種新的研究方向不確定性數(shù)據(jù)挖掘：一種新的研究方向michael chau1, reynold cheng2, and ben kao31：商學院，香港大學，薄扶林，香港2：計算機系，香港理工大學九龍湖校區(qū)，香港3：計算機科學系，香港大學，薄扶林，

2、香港摘要由于不精確測量、過時的來源或抽樣誤差等原因，數(shù)據(jù)不確定性常常出現(xiàn)在真實世界應用中。目前，在數(shù)據(jù)庫數(shù)據(jù)不確定性處理領域中，很多研究結果已經(jīng)被發(fā)表。我們認為，當不確定性數(shù)據(jù)被執(zhí)行數(shù)據(jù)挖掘時，數(shù)據(jù)不確定性不得不被考慮在內(nèi)，才能獲得高質(zhì)量的數(shù)據(jù)挖掘結果。我們稱之為“不確定性數(shù)據(jù)挖掘”問題。在本文中，我們?yōu)檫@個領域可能的研究方向提出一個框架。同時，我們以uk-means聚類算法為例來闡明傳統(tǒng)k-means算法怎么被改進來處理數(shù)據(jù)挖掘中的數(shù)據(jù)不確定性。1.引言由于測量不精確、抽樣誤差、過時數(shù)據(jù)來源或其他等原因，數(shù)據(jù)往往帶有不確定性性質(zhì)。特別在需要與物理環(huán)境交互的應用中，如：移動定位服務15和傳感器

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

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

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

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

7、量化在不斷變化的環(huán)境下的位置或傳感器數(shù)據(jù)的不精密度。在這個領域里，大量的工作都致力于不精確查找。例如，在5中，解決不確定性數(shù)據(jù)范圍查詢的索引方案已經(jīng)被提出。在4中，同一作者提出了解決鄰近等查詢的方案。注意到，所有工作已經(jīng)把不確定性數(shù)據(jù)管理的研究結果應用于簡化數(shù)據(jù)庫查詢中，而不是應用于相對復雜的數(shù)據(jù)分析和挖掘問題中。在數(shù)據(jù)挖掘研究中，聚類問題已經(jīng)被很好的研究。一個標準的聚類過程由5個主要步驟組成：模式表示，模式定義，模式相似度量的定義，聚類或分組，數(shù)據(jù)抽象和造工評核10。只有小部分關于數(shù)據(jù)挖掘或不確定性數(shù)據(jù)聚類的研究被發(fā)表。hamdan與govaert已經(jīng)通過運用em算法解決使混合密度適合不確定

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

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

10、有意思的問題，即如何在數(shù)據(jù)集中表示每個元組和關聯(lián)的不確定性。而且，由于支持和其他指標的概念需要重新定義，不得不考慮改進那些著名的關聯(lián)規(guī)則挖掘算法(如apriori)。同樣地，在數(shù)據(jù)分類和數(shù)據(jù)聚集中，傳統(tǒng)算法由于未將數(shù)據(jù)不確定性考慮在內(nèi)而導致不能起作用。不得不對聚類質(zhì)心、兩個目標的距離、或目標與質(zhì)心的距離等重要度量作重新定義和進行更深的研究。4不確定性數(shù)據(jù)聚類實例在這個章節(jié)中，我們將以不確定性數(shù)據(jù)挖掘的例子為大家介紹我們在不確定性數(shù)據(jù)聚類中的研究工作。這將闡明我們在改進傳統(tǒng)數(shù)據(jù)挖掘算法以適合不確定性數(shù)據(jù)問題上的想法。4.1 問題定義用s表示v維向量xi的集合，其中i=1到n，這些向量表示在聚類應

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

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

13、 for i = 1 to n do4. 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 收斂可能基于不同的質(zhì)心來確定。一些收斂性判別規(guī)則例子包括：（1）當平方誤差總和小于某一用戶專用臨界值，（2）當在一次迭代中沒有一個目標再分配給不同的數(shù)據(jù)集和（3）當?shù)螖?shù)還達到

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

15、ach data point xi to 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基于數(shù)據(jù)不確定性模型來計算預期的距離和數(shù)據(jù)集質(zhì)心。同時，收斂可按照不同的標準來定義。注意到如果收斂依賴于下平方誤差，那么在方程式

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

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

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

19、定的不確定性。我們使用這些不確定性因素來捕捉不確定性信息。接下來我們來比較兩種聚類方法的不同之外：（1）把k-means方法應用于記錄中和把uk-means方法應用于記錄中+不確定性。更具體地說，我們首先一個100×100的二維空間產(chǎn)生一組隨機數(shù)據(jù)點作為記錄。對于每個數(shù)據(jù)點，我們根據(jù)單向線性不確定性模型為其隨機產(chǎn)生不確定性。一個目標的不確定性規(guī)格包括不確定性的類型（雙向線性）、目標能夠移動的最小距離d以及目標能夠移動的方向。接下來，這些目標的真實位置就根據(jù)記錄和不確定性來模擬目標已經(jīng)從累存記錄中的原始位置偏移來產(chǎn)生。特別地，對于每個數(shù)據(jù)點，我們把它的位置記錄在案，然后隨機產(chǎn)生一個數(shù)據(jù)

20、決定目標可能的移動距離。如果它屬于自由移動（多向）或雙向不確定性，那么我們將產(chǎn)生另外一個數(shù)據(jù)來決定目標可能的移動方向。我們使用實際值來表示這些目標的位置。理論上，一個系統(tǒng)需要知道實際情況且把k-means方法應用于實際位置中。盡量不是實際的，但是這個聚類結果卻可視為聚類結果質(zhì)量的一個很好的參照。因此，我們計算和比較以下數(shù)據(jù)集的聚類輸出結果：(1)記錄（使用傳統(tǒng)k-means）(2)記錄+不確定性（使用uk-means）(3)真實值（使用傳統(tǒng)k-means）為了核實uk-means算法在產(chǎn)生的數(shù)據(jù)群集接近從真實數(shù)據(jù)中產(chǎn)生的數(shù)據(jù)集群中的作用，我們采用廣泛使用的用來計算聚類結果間相似度的調(diào)整蘭德指數(shù)

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

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

23、eans算法能獲得一個數(shù)據(jù)群集，而這個數(shù)據(jù)群集是從真實世界可利用數(shù)據(jù)中得到數(shù)據(jù)群集的一個較好的預測。表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%在效率方面，我們發(fā)現(xiàn)uk-means方法比k-means方法需要更多的計算時間，但是它常常只需要合理數(shù)量的額外時間。這是合乎情理的，因為它考

24、慮了不確定性使得聚類質(zhì)量更好。我們通過給n、k及d賦予不同的值且保持其他變量恒定來進行深入地實驗。在所有情況下，我們發(fā)現(xiàn)uk-means方法比傳統(tǒng)的k-means方法改進了，而且兩者的差異有統(tǒng)計學意義（如圖所示每一種情況試驗結果）。我們的初步研究表明當不確定性程度增加時，uk-means算法的改進度也就越高。另一方面，除了當群集的個數(shù)非常小的時候，目標的個數(shù)和群集的個數(shù)對uk-means算法的作用是不會有大的影響。6. 總結與展望傳統(tǒng)的數(shù)據(jù)挖掘算法沒有考慮數(shù)據(jù)項中固有的不確定性而且產(chǎn)生的挖掘結果與真實世界的數(shù)據(jù)不相符。在本論文中，我們提出了在不確定性數(shù)據(jù)挖掘領域研究的一個分類方法。同時我們以u

25、k-means算法作為案例研究和闡明該算法是如何被應用的。隨著由先進傳感器設備帶來的現(xiàn)實數(shù)據(jù)日益復雜，我們相信不確定性數(shù)據(jù)挖掘是一個重要和有意義的研究領域。感謝我們要感謝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 engin

26、eering, 4(5), 1992.2. bezdek, j. 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

27、of data, june 2003.4. cheng, r., 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 probab

28、ilistic threshold queries over uncertain 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 us

29、e in detecting compact well-separated 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 featur

30、e type data analysis,” ieee transactions 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. pf

31、oser d. and jensen, c. “capturing 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 applicat

32、ions. physica-verlag, heidelberg(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 g

33、ene expression data,” bioinformatics, 17(9) (2001) 763-774. 12uncertain data mining: a new research directionuncertain 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, ho

34、ng kong polytechnic university kowloon, hong kong3: department of computer science, 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 imprecis

35、e measurement, outdated sources, or sampling errors. recently, much research has been 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 re

36、sults. we call this the "uncertain data mining" problem. in this paper, we present a 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 u

37、ncertainty in data mining.1. introductiondata is often associated with uncertainty because of 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 service

38、s 15 and sensor monitoring 3. for example,in the scenario of moving objects (such as vehicles 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

39、 various sources of uncertainty have to be considered in order to produce accurate query and mining 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. howev

40、er, little research work has addressed the issue of mining uncertain data. we note that with uncertainty, 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

41、location of an object can be summarized either by its last recorded location, or by an expected 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 quali

42、ty of the mining results. figure 1 illustrates this problem when a clustering algorithm is applied 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 cl

43、usters obtained from these outdated values could be significantly different from those obtained 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

44、the cluster centroids, thus resulting in more errors.figure 1figure 1. (a) the real-world data 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 o

45、bject than a, and b has one more object than b. also, c is mistakenly split into c and c. (c) 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 funct

46、ions (pdf) of uncertain data, into existing data mining methods so that the mining results could 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 dat

47、a clustering as a motivating example. we call this the uncertain data mining problem. in this 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 clust

48、ering on data with uncertainty and present our proposed algorithm. section 4 presents the application 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

49、 recent years, there is significant research interest in data uncertainty management. data uncertainty 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

50、relational database could be associated with a probability value that indicates the confidence 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

51、 can be used to quantify the imprecision of location and sensor data in a constantly-evolving 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

52、 uncertain data have been proposed. the same authors also proposed solutions for aggregate queries 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 ana

53、lysis and mining problems.the clustering problem has been well studied in data mining research. 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 fe

54、w studies on data mining or data clustering for uncertain data have been reported. hamdan and 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

55、rather customized for em.clustering on interval data also has been studied. different distance 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. a

56、nother related area of research is fuzzy clustering. fuzzy clustering has been long studied in 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 mo

57、re than one cluster, each with a different degree. the fuzzy c-means algorithm was one of the 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