一種不精確數據的聚類挖掘方法
2009-01-01 00:00:00李清峰周鮮成王莉周偉林
計算機應用研究 2009年3期
（1.湖南商學院 計算機與電子工程系， 長沙 410205; 2.中南大學 信息科學與工程學院， 長沙 410083）
摘 要：在聚類過程中考慮到數據的非確定性，提出了一種改進的K平均算法——FK算法。FK算法思想是減小總均方誤差的期望值E(SSE)，需特別說明的是對數據對象xi 采用在非確定區域內用非確定密度概率函數pdf f(xi)進行描述。用FK算法對非確定運動模式的運動對象進行了分析，實驗表明考慮數據的非確定因素，在聚類分析處理時有比較精確的結果。
關鍵詞：非精確數據； K平均算法； FK聚類算法； 密度概率函數
中圖分類號：TP391 文獻標志碼：A
文章編號：10013695(2009)03088703
Algorithm in clustering location datafor uncertain data mining
LI Qingfeng1，2， ZHOU Xiancheng1，2， WANG Li1，2， ZHOU Weilin1
（1.Dept. of Computer Electronic Engineering， Hunan Business College， Changsha 410205， China; 2.School of Information Science Engineering，Central South University， Changsha 410083， China)
Abstract:To consider data uncertainty in the clustering process， this paper proposed a FKmeans clustering algorithm that enhanced the Kmeans algorithm tothe goal of minimizing the expected sum of squared errors E(SSE). Specially noted that a data object xi was specified by an uncertainty region with an uncertainty pdf f(xi). This paper applied FKmeans to the particular pattern of movingobject uncertainty. Experimental results show that by considering uncertainty， the clustering algorithm can produce more accurate results.
Key words：data uncertainty; Kmeans algorithm ; FKmeans clustering algorithm; pdf
現實生活中數據的不精確性是固定存在的，如距離測量數據、傳感器檢測數據等。由于測量偏差、取樣精度及非實時性等往往使得到的數據出現一定的誤差，這種數據稱為噪聲數據。對噪聲數據處理已經有了多種較成熟的方法，但對不確定數據的挖掘工作做得還比較少。由于不確定性，數據不再具有確定值的粒子特性，傳統的數據挖掘技術多是對確定數據的分析處理，因此采用這些技術之前應平滑數據、去掉噪聲。對噪聲數據處理的方法不同，將對數據挖掘的結果有較大的影響。圖1描述了不確定性位置的運動物體的一種聚類算法，如果僅僅考慮表面記錄的數值，許多物體將可能被劃入錯誤的類，甚至有可能會改變各類的聚類質心，導致一系列的錯誤。對這種問題通常采用的技術是歸納不確定的數據信息，例如用統計概率密度函數，這樣能使數據挖掘的結果更接近現實的情況。本文研究了怎樣對不確定數據進行歸納合并，以便使聚類挖掘結果更準確，同時提出了一種基于K中心點聚類的新算法。
圖1(a)中現實的數據由三個聚類點(a， b， c)構成；(b)中分析記錄的數據時，可能會推導出四個聚類（a′，b′，c′ and c″）；(c)中當運用線性不確定性進行分析時，推導的結果是a′， b′ and c三個聚類，顯而易見，這個結果與（b）中分析相比更接近真實的數據聚類（a）。
1 相關的工作
近年來不確定數據的分析處理研究逐漸引起了人們的關注和興趣。很多研究致力于非精確數據的查詢，以便發現可信度比效高的結果。例如，在文獻[1]中， Cheng等人提出了在序列范圍內查詢非精確數據的解決思想， 他們在文獻[2]中又提出了在最鄰近序列查詢聚類序列的方法。 現在這些研究結果主要是應用在單一數據庫序列的非精確數據管理領域，還沒有涉及到更復雜數據庫的分析和挖掘等問題的研究。聚類在數據挖掘中的作用是很大的，但在對非精確數據的聚類分析和數據挖掘的研究工作還進行得比較少。 Hamdan等人[3]用EM算法對混合型高密度數據庫的非精確數據聚類進行了探索，然而EM算法的約束條件多、局限性大，在其他環境條件下的使用受到了限制。與此相關的另一種探索是模糊聚類，在模糊聚類中一簇表示成模糊數據集，每個對象根據不同的屬性或分類等級可能聚類到不同的簇。目前，K平均模糊聚類算法是應用較廣泛的方法。
K平均算法以K為參數，把n個對象分為k個簇，以使簇內具有較高的相似度，而簇間的相似度較低。相似性的計算根據一個簇中對象的平均值（被看做簇的重心）來進行。其算法處理流程如下：a)隨機地選擇k個對象，每個對象初始地代表了一個簇的平均值或中心；對剩余的每個對象，根據其與各個簇中心的距離，將它賦予最近的簇。b)重新計算每個簇的平均值，不斷重復這個過程，直到準則函數收斂。通常，采用平方誤差準則，其定義為
E=∑ki=1∑p∈ci∣p-mi∣2。其中：E是數據庫中所有對象的平方誤差的總和；p是空間中的點，表示給定的數據對象；mi是簇ci的平均值（p和mi均是多維的）。這個準則試圖使生成的結果簇盡可能地緊湊和獨立。
算法描述：K平均。劃分的K平均算法基于簇中對象的平均值。
輸入：簇的數目k和包含n個對象的數據庫。
輸出：k個簇，使平方誤差準則最小。
方法：
a）任意選擇k個對象作為初始的簇中心;
b）repeat;
c)根據簇中對象的平均值，將每個對象（重新）賦予最類似的簇;
d）更新簇的平均值，即計算每個簇中對象的平均值;
e)until不再發生變化。
該算法嘗試找出使平方誤差函數值最小的k個劃分。當結果簇是密集的，而簇與簇之間區別明顯時，它的效果較好。對處理大數據集，該算法是相對可伸縮的和高效率的，因為它的復雜度是O(nkt)。其中：n是所有對象的數目；k是簇的數目；t是迭代的次數。通常k< 2 對不確定數據的聚類算法分析 2.1 問題的分析 本文介紹基于密度分布函數的聚類算法。該算法主要基于下面的思想： a）每個數據點的影響可以用一個數學函數來形式化地模擬，它描述了一個數據點在鄰域內的影響，被稱為影響函數（influence function）； b)數據空間的整體密度可以被模型化為所有數據點的影響函數的總和； c）然后聚類可以通過確定密度吸引點（density attractor）來得到，這里的密度吸引點是全局密度函數的局部最大。 假設x和y是d維特征空間Fd中的對象。數據對象y對x的影響函數是一個函數fBy，它是根據一個基本的影響函數fBy（x）=fB(x，y)來定義的。原則上，影響函數可以是一個任意的函數，它由某個鄰域內的兩個對象之間的距離來決定。距離函數d(x，y)應當是自反的和對稱的，例如歐幾里德距離函數。它用來計算一個方波影響函數（square wave influence function）: fsquare(x，y)=0 if d(x，y)＞δ1 otherwise 或者一個高斯影響函數fGauss(x，y)=λd(x，y)2/2δ2。 在一個對象x(x∈Fd)上的密度函數被定義為所有數據點的影響函數之和。給定n個數據對象，D={x1，…，xn}∈Fd，在x上的密度函數定義為fDB(x)= ∑ni=1fBxi(x)。 例如，根據高斯影響函數得出的密度函數是FDGauss(x)=∑ni=1λ-d(x，y)2/2δ2。 根據密度函數，能夠定義該函數的梯度和密度吸引點（全局密度函數的局部最大）。一個點x是被一個密度吸引點x*的，如果存在一組點x0，x1，…，xk，x0=x，xk=x*，對0＜i＜k，xi-1的梯度是在xi的方向上。對一個連續的和可微的影響函數，一個用梯度指導的爬山算法能用來計算一組數據點的密度吸引點。 基于這些概念，能夠形式化地定義中心定義簇（centerdefined cluster）和任意形狀的簇（arbitraryshape cluster）。密度吸引點x*的中心定義簇是一個被x*密度吸引的子集C，在x*的密度函數不小于一個閾值ξ；否則（即如果它的密度函數數值小于ξ）它被認為是孤立點。一個任意形狀的簇是子集C的集合，每一個是密度吸引的，有不小于閾值ξ的密度函數值，并從每個區域到另一個均存在一條路徑P，該路徑上每個點的密度函數值都不小于ξ。 2.2 算法介紹 設S是V維向量xi的集合，這里i=1 to n表示數據記錄的各屬性值，每個數據記錄oi有個相應的密度概率函數(pdf) fi(x)，這里fi(x)表示對象oi的屬性值x 隨時間t變化的關系。聚類的目的是找出聚類集C，其集合類Cj（這時j=1 to K）中每個數據元素具有相似性，不同類之間的數據元素具有較大差異。不同的聚類算法采用不同的目標函數，以找出高度相似的簇類。降低簇類內部的差別是指將屬于Cj類的數據元素xi間的差距減小。 在聚類過程中考慮到數據的非確定性，本文提出的算法思想是減小總均方誤差的期望值E(SSE)（expected sum of squared errors）。需說明的是本文對數據對象xi采用在非確定區域內用非確定密度概率函數pdf f(xi)進行描述。 對給定的一個簇類， C′j的總均方誤差值SSE采用式(1)計算： E(∑kj=1∑i∈cj‖Cj-Xi‖2=∑kj=1∑i∈cj‖Cj-Xi‖f(xi)dxi（1） 這里‖#8226;‖是數據元素xi和一個簇cj的距離。 簇按式(2)劃分： Cj=E(1/｜cj｜ ∑i∈cjXi)=1/｜cj｜ ∑i∈cj∫xi f(xi)dxi（2） 對非確定數據的聚類，本文提出的一種新K平均算法，叫做FK算法。算法如下： a)Assign initial values for cluster means c1 to cK b)repeat c)for i = 1 to n do d)Assign each data xi to cluster Cj where E(‖cj-xi‖) is the minimum e)end for f)for j= 1 to K do g)Recalculate cluster mean cj of cluster Cj h)end for i)untilconvergence j)return C FK算法與傳統的K平均算法的主要不同在于數據距離的計算方法和簇的聚類方法。FK算法計算均方誤差的期望值和簇的質點是建立在非確定數據模式上的，算法的收斂可按不同的標準來要求。在d)步中， 對代數式E(‖cj-xi‖)的確定比較困難，尤其是非確定數據域的幾何形狀（線條域、圓形域等）的確定； 同時，不同的非確定數據密度概率函數pdf f(xi)采用不同的積分方式也是必要的，這里采用的是期望值差的平方E(‖cj-xi‖2)， 主要是這樣處理比較方便。 3 FK聚類算法在運動物體分析中的應用 FK算法的主要優越性在于可應用于任何非確定數據和密度概率函數。 這里介紹FK聚類算法物體在二維空間不確定運動模式分析中的應用。根據文獻[1，4]，有兩種不確定的運動模式，即線性運動和自由運動。在線性運動中，假設一個物體以小于Vmax速度沿一個固定方向運動，但不確定的線性運動模式可能是單向的或雙向的。非確定的自由運動模式假設運動對象在某區域內以小于Vmax的速度運動。設物體運動的初始位置是(h，k)，初始時間是t0， 物體位于以半徑為Vmax #8226;(t-t0)的圓圈內，假設這里有一個質心c=(p， q)，線段的端點是(a，b)和(c，d)，則直線方程可以用兩點(a+t(c-a)，b+t(d-b))確定，這里t取值為 [0，1]，非確定數據密度概率函數pdf為f(t)，同時線段的距離可表示為D=(c-a)2+(d-b)2則有： E(‖c-x‖2)=∫10f(t)(D2t2+Bt+c) dt（3） 這里B=2[(c-a)(a-p)+(d-b)(b-q)]，C=(p-a)2+(q-b)2。若f(t)是相同的，使其歸一化成為f(t)=1， 則上式變為 E(‖c-x‖2)=d2/3+b/2+c（4） 對非確定的自由運動模式，假設有一個質心c=(p，q)和一個數據對象x在圓的不確定區域范圍內，圓中心為(h，k)半徑為R，且圓的非確定數據密度概率函數為f(r，θ)。那么有 E(‖c-x‖2)=∫R0∫2π0f(r，θ)(A cos θ+B sin θ+c)dθdr 其中：A=2r(h-p)；B=2r(k-q)；C=r2+(h-p)2+(k-q)2。 這樣較方便地計算出不確定的兩種運動模式，即線性運動和自由運動的距離平方期望值。 這里限定同樣的運動區域只是作為樣例來介紹。 當數據密度概率函數是個變化函數(如高斯函數等)時，可采用相同的方法計算E(‖cj-xi‖)。 4 實驗 在本文實驗中，模仿一個游戲情節，對一組運動對象的運動軌跡進行了快照記錄，這些存儲在數據庫記錄中的位置數據標記為recorded，每個運動對象按不確定運動模式運動的數據本文標記為uncertainty。本文比較了兩種聚類算法：a）應用K平均算法分析recorded數據；b)應用FK算法分析recorded+uncertainty數據。首先在100×200的二維空間內抽取一組隨機數據稱為recorded數據；然后對每個數據點根據選定的不確定運動模式抽取其數據，稱為uncertainty數據，同時也將模仿的游戲情節中運動對象的實際位置數據記錄下來，稱為actual數據。進而從下面的數據能計算和比較出聚類結果：a)recorded(用K平均算法分析)；b)recorded+uncertainty(用FK算法分析)；c)actual(用K平均算法分析)。 這里使用修正域指數ARI（adjusted rand index ) 檢測聚類結果的相似性。 ARI 值越大表明兩個聚類的相似等級越高， 本文比較了用b）和c）算法進行聚類結果的ARI值，以及用a）和c）算法進行聚類結果的API值。由于篇幅有限，這里只對單向的不確定的線性運動模式作介紹。設共有n個對象，聚類數為k，在本實驗中設一個對象最大的運動距離d是可變的，表1列出了在n=1 000和K=20的條件下改變d后不同的實驗結果。對每次設定的不同參數，筆者都進行了500次實驗，將分析結果取平均值。每次實驗首先抽取recorded、 uncertainty和actual 類不同的數據，對每類數據采用三種不同的聚類算法進行分析，為避免偏差不同的聚類算法，運動對象的質心均取相同的值。 從實驗數據可以看出，在處理recorded 數據時FK算法的ARI系數要大于傳統的K平均算法的ARI系數據。 同時本文對兩種運動模式進行了相同參數數據的實驗(均設p＜0.000 001)，從ARI值的差別可看出對真實有效的數據FK算法能分析出比較理想的聚類結果。 表1 實驗結果 d1.52.557.5102050 ARI（FK算法）0.7400.7330.6890.6520.6320.5060.311 ARI（K平均算法）0.7150.7000.6260.5730.5230.3510.121 % ofimprovement3.584.7710.0313.8420.8244.34155.75 5 結束語 在非精確數據的關聯分析中，為了提高聚類的精確性，在分析K平均算法的基礎上提出了FK算法，雖然在本文中只對具有相同分布狀態的非精確數據聚類進行分析，但算法可推廣至其他分布狀態（如采用抽樣技術等）數據的聚類分析。同時筆者認為在本文引用的一些概念如期望值距離、數據密度概率函數等可應用到其他的聚類算法（如最小鄰近聚類法、自組織圖法）中，也可應用到其他數據挖掘技術（如分類算法）中。 FK算法與其他聚類算法相比主要有如下的優點：a）它有一個堅實的數學基礎，概括了其他的聚類算法，包括基于劃分的、層次的及基于位置的方法。b）對于有大量噪聲的不確定數據集合，它有良好的聚類特性。c）對高維數據集合的任意形狀聚類，它給出了簡潔的數學描述。d）它使用了網格單元，只保存關于實際包含數據點的網格單元的信息。它以一個基于樹的存取結構來管理這些單元，因此比一些有影響的算法（如DBSCAN算法）速度要快。但是，該算法要求對密度參數σ和噪聲閾值ξ進行仔細的選擇，因為這樣的參數選擇可能顯著地影響聚類結果的質量。 參考文獻： [1]CHENG R， XIA X， PRABHAKAR S，et al.Efficient indexing methods for probabilistic threshold queries over uncertain data[C]//Proc of VLDB. 2004:876887. [2]CHENG R， KALASHNIKOV D V， PRABHAKAR S. Querying imprecise data in moving object environments[J].IEEE Trans on Knowledge and Data Engineering， 2004，16(9):11121127. [3]HAMDAN H， GOVAERT G. Mixture model clustering of uncertain data[C]//Proc of IEEE International Conference on Fuzzy Systems. 2005:879884. [4]WOLFSON O， SISTLA P， CHAMBERLAIN S，et al. Updating and querying databases that track mobile units[J]. Distributed and Parallel Databases， 1999，7(3):14351439. [5]BEZDEK J C. Pattern recognition with fuzzy objective function algorithms[M]. New York:Plenum Press， 1981:154161. [6]CHAU M， CHENG R， KAO B. Uncertain data mining: a new research direction[C]//Proc of Workshop on the Sciences of the Artificial. 2005:546553. [7]YEUNG K， RUZZO W. An empirical study on principal component analysis for clustering gene expression data[J]. Bioinformatics， 2001，17(9):763774. [8]修宇，王士同，吳錫生，等. 方向相似性的聚類方法DSCM[J].計算機研究與發展，2006，43（8）：14251431. [9]郝紅衛，蘇榮偉. 基于K近鄰決策邊界的特征提取[J]. 模式識別與人工智能，2007（5）：649652.
