【正文】 的研究。而且， 由于支持和其他指標(biāo)的概念需要重新定義，不得不考慮改進(jìn)那些 著名的關(guān)聯(lián)規(guī)則挖掘算法 (如 Apriori)。模糊聚類的一個(gè)例子是每個(gè)數(shù)據(jù)項(xiàng)被賦予一個(gè)被分配給數(shù)據(jù)簇的任意成員的概率 。硬聚類旨在通過(guò) 考慮 預(yù)期的數(shù)據(jù)來(lái)提高聚類的準(zhǔn)確性。當(dāng)然這些技術(shù)需要經(jīng)過(guò)改進(jìn)才能用于處理不確定性技術(shù)。 在圖 2中，我們提出一種分類法來(lái)闡述數(shù)據(jù)挖掘方法怎么根據(jù)是否考慮數(shù)據(jù)不準(zhǔn)確性來(lái)分類。 不同的模糊聚 類方法已被應(yīng)用在一般數(shù)據(jù)或模糊數(shù)據(jù)中來(lái)產(chǎn)生的模糊數(shù)據(jù)簇。換言之，一個(gè)目標(biāo)可以歸屬于多個(gè)簇， 與每個(gè)簇均有一個(gè)度 。 在模糊聚 類中 ,一個(gè)是數(shù)據(jù)簇 由一 組目標(biāo)的模糊子集組成 。另外一個(gè)相關(guān)領(lǐng)域的研究就是模糊聚類。像城區(qū)距離或 明考斯基距離 等不同距離測(cè)量也已經(jīng)被用來(lái)衡量?jī)蓚€(gè)區(qū)間的相似度。 然而，這個(gè)模型不能任意地應(yīng)用于其他聚類算法因 為 它相當(dāng)于為 EM 定制的。只有小部分關(guān)于數(shù)據(jù)挖掘或不確定性數(shù)據(jù)聚類的研究被發(fā)表。 在數(shù)據(jù)挖掘研究中，聚類問(wèn)題已經(jīng)被很好的研究。在 [4]中，同一作者提出了解決鄰近等查詢的方案。在這個(gè)領(lǐng)域里，大量的工作都致力于不精確查找。在數(shù)據(jù)不確定性類型中， 一個(gè)數(shù)據(jù)項(xiàng)作為一個(gè)封閉的區(qū)域 ,與其值的概率密度函數(shù)（ PDF）限定了其可能的值 [3,4,12,15]。在 第一種類型中，不管目標(biāo)或數(shù)據(jù)元組存在是否，數(shù)據(jù)本身就已經(jīng)存在不確定性了。 近年來(lái)，人們對(duì)數(shù)據(jù)不確定性管理有明顯的研究興趣。詳細(xì)地的實(shí)習(xí)結(jié)果將在第五章解釋。在第三章中，我們定義了不確定性數(shù)據(jù)聚類問(wèn)題和介紹我們提議的算法。 文章接下來(lái)的結(jié)構(gòu)如下。我們稱之為不確定性數(shù)據(jù)挖掘問(wèn)題。 我們建議將不確定性數(shù)據(jù)的概率密度函數(shù)等不確定性信息與現(xiàn)有的數(shù)據(jù)挖掘方法結(jié)合，這樣在實(shí)際數(shù)據(jù)可利用于數(shù)據(jù)挖掘的情況下會(huì)使得挖掘結(jié)果更接近從真實(shí)數(shù)據(jù)中獲得的結(jié)果。 (c)表示方向不確定性被考慮來(lái)推測(cè)出集群 a’， b’和 c。注意到 a’集群中比 a 集群少了一個(gè)目標(biāo)，而 b’集群中比 b 集群多一個(gè)目標(biāo)。 圖 1 數(shù)據(jù)圖 圖 1.（ a）表示真實(shí)數(shù)據(jù) 劃分成的三個(gè)集群（ a、 b、 c）。如果我們僅僅依靠記錄的數(shù)據(jù)值，那么將會(huì)很多的目標(biāo)可能被置于錯(cuò)誤的數(shù)據(jù)集群中。 不確定性數(shù)據(jù)挖掘：一種新的研究方向 2 圖 1（ a）表示一組目標(biāo)的真實(shí)數(shù)據(jù)，而圖 1（ b）則表示記錄的已過(guò)時(shí)的這些目標(biāo)的位置。不幸地是，歸納得到的記錄與真實(shí)記錄之間的誤差可能會(huì)嚴(yán)重也影響挖掘結(jié)果。 對(duì)于使用傳統(tǒng)數(shù)據(jù)挖掘技術(shù)，不確定性數(shù)據(jù)不得不被歸納為原子性數(shù)值。然而，很少有研究成果能夠解決不確定性數(shù)據(jù)挖掘的問(wèn)題。為了提供準(zhǔn)確地查詢和挖掘結(jié)果，這些導(dǎo)致數(shù)據(jù)不確定性的多方面來(lái)源不得不被考慮。例如：在追蹤移動(dòng)目標(biāo)（如車輛或人）的情境中，數(shù)據(jù)庫(kù)是不可能完全追蹤到所有目標(biāo)在所有瞬間的準(zhǔn)確位置。 由于測(cè)量不精確、抽樣誤差、過(guò)時(shí)數(shù)據(jù)來(lái)源或其他等原因，數(shù)據(jù)往往帶有不確定性性質(zhì)。在本文中，我們?yōu)檫@個(gè)領(lǐng)域可能的研究方向提出一個(gè)框架。我們認(rèn)為，當(dāng)不確定性數(shù)據(jù)被執(zhí)行數(shù)據(jù)挖掘時(shí)，數(shù)據(jù)不確定性不 得不被考慮在內(nèi)，才能獲得高質(zhì)量的數(shù)據(jù)挖掘結(jié)果。 畢業(yè)設(shè)計(jì)（論文）外文資料翻譯 系 部： 計(jì)算機(jī)科學(xué)與技術(shù)系 專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 姓 名： 洪維坤 學(xué) 號(hào)： 0807012215 外 文 出 處： Proceeding of Workshop on the （用外文寫(xiě)） of Artificial,Hualien,TaiWan,2021 指導(dǎo)老師評(píng)語(yǔ)： 簽名： 年 月 日 不確定性數(shù)據(jù)挖掘：一種新的研究方向 1 不確定性數(shù)據(jù)挖掘：一種新的研究方向 Michael Chau1, Reynold Cheng2, and Ben Kao3 1：商學(xué)院，香港大學(xué)， 薄扶林 ，香港 2：計(jì)算機(jī)系，香港理工大學(xué)九龍湖校區(qū)，香港 3：計(jì)算機(jī)科學(xué)系，香港大學(xué)， 薄扶林 ，香港 摘要 由于 不精確 測(cè)量、過(guò)時(shí)的來(lái)源 或抽 樣誤差等原因， 數(shù)據(jù)不確定性 常常出現(xiàn)在真實(shí)世界應(yīng)用中。目前，在數(shù)據(jù)庫(kù)數(shù)據(jù)不確定性處理領(lǐng)域中，很多研究結(jié)果已經(jīng)被發(fā)表。我們稱之為“不確定性數(shù)據(jù)挖掘”問(wèn)題。同時(shí)，我們以 UKmeans聚類算法為例來(lái)闡明傳統(tǒng) Kmeans算法怎么被改進(jìn)來(lái)處理數(shù)據(jù)挖掘中的數(shù)據(jù)不確定性。特別在需要與物理環(huán)境交互的應(yīng)用中，如：移動(dòng)定位服務(wù) [15]和傳感器監(jiān)測(cè) [3]。因 此，每個(gè)目標(biāo)的位置的變化過(guò)程是伴有不確定性的。 在最近幾年里，已有在數(shù)據(jù)庫(kù)中不確定性數(shù)據(jù)管理方面的大量研究，如：數(shù)據(jù)庫(kù)中不確定性的表現(xiàn)和不確定性數(shù)據(jù)查詢。 我 們注意到 ，不確定性 使 數(shù)據(jù) 值 不再 具有原子性 。再以追蹤移動(dòng)目標(biāo)應(yīng)用為例，一個(gè)目標(biāo)的位置可以通過(guò)它最后的記錄位置或通過(guò)一個(gè)預(yù)期位置（如果這個(gè)目標(biāo)位置概率分布被考慮到）歸納 得到。圖 1闡明了當(dāng)一種聚類算法被應(yīng)用追蹤帶有不確定性位置的移動(dòng)目標(biāo)時(shí)所發(fā)生的問(wèn)題。如果這些實(shí)際位置是有效的話，那么它們與那些從過(guò)時(shí)數(shù)據(jù)值中得到的數(shù)據(jù)集群有明顯差異。更糟糕地是，一個(gè)群中的每一個(gè)成員都有可能改變?nèi)旱馁|(zhì)心，因此導(dǎo)致更多的錯(cuò)誤。（ b）表示的有些目標(biāo)（隱藏的）的記錄位置與它們真實(shí)的數(shù)據(jù)不一樣，因此形成集群 a’、 b’、 c’和 c”。同時(shí)， c 也誤拆分會(huì)為 c’和 c”。這種聚類產(chǎn)生的結(jié)果比（ b）結(jié)果更加接近（ a）。 本文研究了不 確定性怎么通過(guò)把數(shù)據(jù)聚類當(dāng)成一種激勵(lì)范例使用使得不確定性因素與數(shù)據(jù)挖掘相結(jié)合。在本文中，我們?yōu)檫@個(gè)領(lǐng)域可能的研究方向提出一個(gè)框架。第二章是有關(guān)工作綜述。第四章將呈現(xiàn)我們算法在移動(dòng)目標(biāo)數(shù)據(jù)庫(kù)的應(yīng)用。最后在第六章總結(jié)論文并提出可能的研究方向。數(shù)據(jù)不確定性被為兩類，即已存在的不確定生和數(shù)值不確定性。例如，關(guān)系數(shù)據(jù)庫(kù)中的元組可能與能表現(xiàn)不確定性數(shù)據(jù)挖掘：一種新的研究方向 3 它存在信任度的一個(gè)概率值相關(guān)聯(lián) [1,2]。這個(gè)模型可以被應(yīng)用于量化在不斷變化的環(huán)境下的位置或傳感器數(shù)據(jù)的不精密度。例如，在 [5]中，解決不確定性數(shù)據(jù)范圍查詢的索引方案已經(jīng)被提出。注意到，所有 工作已經(jīng)把不確定性數(shù)據(jù)管理的研究結(jié)果應(yīng)用于簡(jiǎn)化數(shù)據(jù)庫(kù)查詢中，而不是應(yīng)用于相對(duì)復(fù)雜的數(shù)據(jù)分析和挖掘問(wèn)題中。一個(gè)標(biāo)準(zhǔn)的聚類過(guò)程由 5個(gè)主要步驟組成：模式表示，模式定義，模式相似度量的定義，聚類或分組，數(shù)據(jù)抽象和 造工 評(píng) 核 [10]。Hamdan 與 Govaert 已經(jīng)通過(guò) 運(yùn) 用 EM 算法 解決使混合密度適合不確定性數(shù)據(jù)聚類的問(wèn)題 [8]。在數(shù)據(jù)區(qū)間的聚類也同樣被 研究。在這些測(cè)量的大多數(shù)中，區(qū)間的概率密度函數(shù)并沒(méi)有被考慮到。在模糊邏輯中的模糊聚類研究已經(jīng)很久遠(yuǎn)了 [13]。 每個(gè)目標(biāo)與每個(gè)簇都有一個(gè)“歸屬關(guān)系度”。 模糊 C均 值聚類算 法 是 一 種最廣泛的使用模糊聚類方法 [2,7]。他們研究工作是基于一 個(gè)模糊數(shù)據(jù)模型的，而我們工作的開(kāi)展則基于移動(dòng)目標(biāo)的不確定性模型。有很多通用的數(shù)據(jù)挖掘技術(shù)，如 : 關(guān)聯(lián)規(guī)則挖掘、數(shù)據(jù)分類、數(shù)據(jù)聚類。此外，我們區(qū)分出數(shù)據(jù)聚類的兩種類型：硬聚類和模糊聚類。 另一方面，模糊聚類則表示聚類的結(jié)果為一個(gè)“模糊”表格。 不確定性數(shù)據(jù)挖掘：一種新的研究方向 4 圖 2. 不確定性數(shù)據(jù)挖掘的一種分類 例如，當(dāng)不確定性被考慮時(shí)，會(huì)發(fā)生一個(gè)有意思的問(wèn)題，即如何 在數(shù)據(jù)集中表示 每個(gè)元組和關(guān)聯(lián)的不確定性。同樣地，在數(shù)據(jù)分類和數(shù)據(jù)聚集中，傳統(tǒng)算法由于未將數(shù)據(jù)不確定性考慮在內(nèi)而導(dǎo)致不能起 作用。 4．不確定性數(shù)據(jù)聚類實(shí)例 在這個(gè)章節(jié)中，我們將以不確定性數(shù)據(jù)挖掘的例子為大家介紹我們?cè)?不確定性數(shù)據(jù)聚類中的研究工作。 問(wèn)題定義 用 S 表示 V維向量 xi的集合，其中 i=1 到 n，這些向量表示在聚類應(yīng)用中被考慮的所有記錄的屬性值。我們沒(méi)有干涉這個(gè)不確定性函數(shù)的實(shí)時(shí)變化，或記錄的概率密度函數(shù)是什么。另一個(gè)常用的就是高斯分布函數(shù)，它能夠用于描述測(cè) 量誤差 [12,15]。不同的聚類算法對(duì)應(yīng)不對(duì)的目標(biāo)函數(shù)，但是大意都是最小化同一數(shù)據(jù)集目標(biāo)間的距離和最大化不同數(shù)據(jù)集目標(biāo)間的距離。在論文中， 我 們只考慮 硬聚 類 ，即，每個(gè) 目標(biāo)只分配給 一個(gè)一個(gè)集群 的一個(gè)元素 。平方誤差總和通常計(jì)算如下： ??? ? ?Kj x ijji xc1 C2 (1) || . ||表示一個(gè)數(shù)據(jù)點(diǎn) xi與數(shù)據(jù)集平均值 cj的距離試題。一些收斂性判別規(guī)則例子包括：（ 1）當(dāng)平方誤差總和小于某一用戶專用臨界值，（ 2）當(dāng)在一次迭代中沒(méi)有一個(gè)目標(biāo)再分配給不同的數(shù)據(jù)集和（ 3）當(dāng)?shù)螖?shù)還達(dá)到預(yù)期的定義的最大值。注意到一個(gè)數(shù)據(jù)對(duì)象 xi 由一個(gè)帶有不確定性概率密度f(wàn)(xi)的不確定性區(qū)域決定。 1. Assign initial values for cluster means c1 to cK 2. repeat 3. for i = 1 to n do 4. Assign each data point xi to cluster Cj where E(|| cj xi ||) is the minimum. 5. end for 6. for j = 1 to K do 7. Recalculate cluster mean cj of cluster Cj 8. end for 9. until convergence 10. return C UKmean 聚類算法與 Kmeans 聚類算法的最大不同點(diǎn)在于距離和群集的計(jì)算。同時(shí)，收斂可按照不同的標(biāo)準(zhǔn)來(lái)定義。 在第 4 步中，常常很困難用代數(shù)方法來(lái)確定 E(|| cj xi ||)，特別地，各種各樣的幾何圖形不確定性區(qū)域（如，線，圓）和不同的不確定性概率密度函數(shù)意味著需要使用數(shù)值積分法。這使我們能夠確定在聚類任務(wù)（即步驟 4）中使用簡(jiǎn)單的代數(shù)表達(dá)式。為了證明方法的可行性，我們將描述所推薦的算法是如何運(yùn)用于特定于在平面空間中移動(dòng)的目標(biāo)的不確定性模型。這個(gè)算法已被應(yīng)用于一個(gè)含有單向線性移動(dòng)不確定性的模型中。 假設(shè)我們?cè)谝粋€(gè)質(zhì)心 c=(p,q)和一個(gè)數(shù)據(jù)對(duì)象 x被指定在一個(gè)線性不確定的均勻分布的區(qū)域中。這樣這個(gè)線性方程式可用參數(shù)表示為（ a+t(ca),b+t(db)），其中 t 屬于 [0,1]。同時(shí)，不確定性線段的距離表示為 ? ? ? ?22 bdacD ???? 。這些公式很容易被 UKmeans 算法用于決定群集分配。當(dāng)概率密度函數(shù)不是均勻分布時(shí)（如，高斯分布），采樣技術(shù)可能被用來(lái)估計(jì) E(|| cj xi ||)。我們目標(biāo)是研究考慮數(shù)據(jù)不確定性是否會(huì)提高聚類質(zhì)量。這個(gè)位置數(shù)據(jù)存在記錄集中。我們使用這些不確定性因素來(lái)捕捉不確定性信息。更具體地說(shuō)，我們首先 一個(gè) 100100不確定性數(shù)據(jù)挖掘：一種新的研究方向 8 的二 維 空 間產(chǎn)生一組隨機(jī)數(shù)據(jù)點(diǎn)作為記錄。一個(gè)目標(biāo)的不確定性規(guī)格包括不確定性的類型（雙向線性）、目標(biāo)能夠移動(dòng)的最小距離 d 以及目標(biāo)能夠移動(dòng)的方向。特別地，對(duì)于每個(gè)數(shù)據(jù)點(diǎn)，我們把它的位置記錄在案，然后隨機(jī)產(chǎn)生一個(gè)數(shù)據(jù)決定目標(biāo)可能的移動(dòng)距離。我們使用實(shí)際值來(lái)表示這些目標(biāo)的位置。盡量不是實(shí)際的，但是這個(gè)聚類結(jié)果卻可視為聚類結(jié)果質(zhì)量的一個(gè)很好的參照。 ARI 值越高，則兩個(gè)聚類結(jié)果相似度越高。 目標(biāo)的個(gè)數(shù) (n)、群集的個(gè)數(shù)（ K）以及目標(biāo)可能移動(dòng)的最小距離（ d）這三個(gè)參數(shù)的值在實(shí)驗(yàn)中將改變。在不同的參數(shù)組合情況下，我們做了 500 次的實(shí)驗(yàn)。這些數(shù)據(jù)組合是同時(shí)在三種聚類過(guò)程中被使用。每一次實(shí)驗(yàn)，我們?cè)试SKmeans 方法（（ 1）中和（ 3）中）和 UKmeans 方法（（ 2）中）在一直運(yùn)行到當(dāng)在群集中的所有目標(biāo)在兩次連續(xù)迭代中沒(méi)有變化時(shí)或迭代次數(shù)達(dá)到 10000 次時(shí)才結(jié)束。 從表 1 可以看到，在應(yīng)用于記錄數(shù)據(jù)中， UKmeans 算法的調(diào)整蘭德指數(shù)始終比傳統(tǒng) Kmeans 算法高。 這個(gè)結(jié)果表明，由UKmeans 算法得到的數(shù)據(jù)群集更接近于從真實(shí)世界獲得的數(shù)據(jù)群集。 不確定性數(shù)據(jù)挖掘：一種新的研究方向 9 表 1. 實(shí)驗(yàn)結(jié)果 D 5 10 20 50 ARI(UKmeans) ARI(Kmeans) 改進(jìn) 改進(jìn)百分比 % % % % % % 在效率方面，我們發(fā)現(xiàn) UKmeans 方法比 Kmeans 方法需要更多的計(jì)算時(shí)間，但是它常常只需要合理數(shù)量的額外時(shí)間。 我們通過(guò)給 n、 K 及 d 賦予不同的值且保持其他變量恒定來(lái)進(jìn)行深入地實(shí)驗(yàn)。我們的 初步研究表明當(dāng)不確定性程度增加時(shí)， UKmeans 算法的改進(jìn)度也就越高。 6. 總結(jié)與展望 傳統(tǒng)的數(shù)據(jù)挖掘算法沒(méi)有考慮數(shù)據(jù)項(xiàng)中固有的不確定性而且產(chǎn)生的挖掘結(jié)果與真實(shí)世界的數(shù)據(jù)不相符。同時(shí)我們以 UKmeans 算法作為案例研究和闡明該算法是如何被應(yīng)用的。 感謝 我 們要感謝 Jackey Ng（香港大學(xué)）， David Cheung（香港大學(xué)）， Edward Hung（香港理工大學(xué)），和 Kevin Yip（耶 魯大學(xué) ）的寶 貴建